アルゴリズムを考える際の思考方法

#はじめに
所属している会社で、課題を解くアルゴリズムを考え、その処理速度を競う会が開かれた。
その課題を題材に、アルゴリズムを考える際の思考の仕方を解説してみる。
プログラムを知らない人でも理解できるよう心掛けた。

#課題について
日本の硬貨1円、5円、10円、50円、100円、500円をそれぞれｎ枚持っている際に、表現できる金額の組み合わせの数を、なるべく短い処理時間で算出せよ。
ただし、0円は組み合わせに含めない。
n=2 の場合、1円を2枚、5円を2枚、10円を2枚、50円を2枚、100円を2枚、500円を2枚持っていることになり、この硬貨を使って表現できる金額として、例えば1円、6円、666円、1332円など、何パターンもあり、その組み合わせ数を求める。
ただし、5円が2枚の10円と、10円が1枚の10円は同じ金額の組み合わせと考え、2ケースとせず、1ケースと考える。

#最初は課題を簡略化して考える
硬貨がたくさんあってわかりづらいし、nとか言われても漠然としているので、硬貨の種類を減らし、かつnも固定して考える。
使う硬貨は1円と5円だけにし、硬貨の枚数（n）は2枚、その組み合わせを考える。
0は金額の組み合わせに含めないとか、同じ金額になる組み合わせは重複してカウントしないとかのルールもとりあえず忘れる。

#組み合わせを書いてみる
いきなりプログラムを書くのではなく、実際、手で計算したらどうなるかをやってみる。
組み合わせとして、1円を0枚、5円を0枚の0円の組み合わせが考えられる。
組み合わせを考える場合は、どちらかの軸を固定して、パターンを洗い出し、軸を固定した状態ですべてのパターンが洗い出せたら、今度は軸を変えてパターンを洗い出す。
今回の場合は1円を軸に考える。そうすると、以下のパターンを洗い出すことができる。

No.	1円の枚数	5円の枚数	金額
1	0	0	0
2	0	1	5
3	0	2	10
4	1	0	1
5	1	1	6
6	1	2	11
7	2	0	2
8	2	1	7
9	2	2	12

全部で9パターンあった。

#手で書いた結果から計算式を類推する
9パターンということは、3×3っぽい。
手で書いた表をみても、1円は0～2の3回繰り返し、5円も0～2の3回繰り返しているので、3×3で9通りの計算でよさそう。

#簡略化した課題をちょこっと拡張する
計算方法が見えてきたら、簡略化した課題を拡張して、同じルールで計算できるか試してみる。
さっきは、(1円の枚数+1)×(5円の枚数+1)で計算できたので、10円の硬貨を増やしても同じ方法で計算できるか試してみる。
(枚数+1としているのは0もあるので枚数+1となる）
1円、5円、10円がそれぞれ2枚ずつで考える。

No.	1円の枚数	5円の枚数	10円の枚数	金額
1	0	0	0	0
2	0	0	1	10
3	0	0	2	20
4	0	1	0	5
5	0	1	1	15
6	0	1	2	25
7	0	2	0	10
8	0	2	1	20
9	0	2	2	30
10	1	0	0	1
11	1	0	1	11
12	1	0	2	21
13	1	1	0	6
14	1	1	1	16
15	1	1	2	26
16	1	2	0	11
17	1	2	1	21
18	1	2	2	31
19	2	0	0	2
20	2	0	1	12
21	2	0	2	22
22	2	1	0	7
23	2	1	1	17
24	2	1	2	27
25	2	2	0	12
26	2	2	1	22
27	2	2	2	32

27通り。さっきと同じ計算式を当てはめてみると、
(1円の枚数+1)×(5円の枚数+1)×(10円の枚数+1) = 3×3×3 = 27
となり、同じ計算式で計算できることがわかった。

上の表をみてもわかる通り、硬貨の種類が増えれば増えるほど、枚数を掛けていけばよいことがわかる。
1円～500円すべての硬貨が2枚あった場合の組み合わせ数は、
(1円の枚数+1)×(5円の枚数+1)×(10円の枚数+1)×(50円の枚数+1)×(100円の枚数+1)×(500円の枚数+1) = 3×3×3×3×3×3 = 729通りとなる。

#条件が簡単なうちにプログラムを書いてみる
課題を簡略した状態でとりあえずプログラムを書いてみる。
課題が難しくなると頭が混乱してどこから書いていいのかわからなくなるので、プログラムの骨組みを作りたいときは、課題を簡略した状態で書く。
でも、そのまま書いてしまうと、ただの掛け算のプログラムになってしまう。
今回は、同一金額は1ケースとしてカウントしないといけないため、硬貨の組み合わせごとに金額を計算できるようにしておく必要がある。
（上の27通りの金額を出力するプログラムを作成するイメージ）

組み合わせの掛け算というのは、多重ループ（for分の入れ子）であらわすことができる。

sample.py

# 硬貨の枚数はそれぞれ2枚
n = 2
# 1円の枚数分繰り返し 
#   rangeは、0～指定した数-1の繰り返し用の配列を生成するイメージ
#   0～2の数が生成される
for n1 in range(n+1):
    # 5円の枚数分繰り返し
    for n5 in range(n+1):
        # 10円の枚数分繰り返し
        for n10 in range(n+1):
            kingaku = n10*10 + n5*5 + n1*1
            print("1円 {}枚 5円 {}枚 10円 {}枚 金額 {}".format(n1, n5, n10, kingaku))

出力結果は、上の27通りの表のとおり。

#あとは難しそうな処理を１つ１つ考えていく
同一金額は1ケースとしてカウントする、という処理を考える。
単純に考えれば、計算した金額を配列に追加していき、すでに配列に同じ金額が格納されていたら追加せず、最終的に配列の数を数えれば同一金額で重複している分はカウントせずに件数を求めることができる。

しかし、おそらくこの方法は遅い。今回は処理速度を競うため、処理速度の速いアルゴリズムを考える必要がある。

#アルゴリズムが思い浮かばないときは、出力結果を眺めてみる
同一金額の発生には何か法則があるかもしれないと考え、同一金額を除外しない出力結果を眺めてみる。
（上の27通りのパターン）
出力結果を眺めると、最初に重複が登場するのは、
・No.7の10円、No.8の20円。
・No.16の11円、No.17の21円。
・No.25の12円、No.26の22円。
数が少ないので法則性が見出しにくいが、重複するときは連続して重複するため、何かしらの法則があることが推測される。

#出力結果に法則がありそうなら出力結果を並び替えてみる
金額の重複に着目して法則を見いだす場合、金額が昇順に並んでいたほうがわかりやすい。
金額を小さい順から並べるためには、ループの順番を変更する。
今のループの順番は、1円 > 5円 > 10円　となっており、1円が一番外のループになっている。
そのため、計算される金額が、0円、10円・・・16円、1円・・・のようにばらばらになってしまっている。
ループの順番を、10円 > 5円 > 1円に変更すると、以下の表のような順番で出力される。

No.	10円の枚数	5円の枚数	1円の枚数	金額
1	0	0	0	0
2	0	0	1	1
3	0	0	2	2
4	0	1	0	5
5	0	1	1	6
6	0	1	2	7
7	0	2	0	10
8	0	2	1	11
9	0	2	2	12
10	1	0	0	10
11	1	0	1	11
12	1	0	2	12
13	1	1	0	15
14	1	1	1	16
15	1	1	2	17
16	1	2	0	20
17	1	2	1	21
18	1	2	2	22
19	2	0	0	20
20	2	0	1	21
21	2	0	2	22
22	2	1	0	25
23	2	1	1	26
24	2	1	2	27
25	2	2	0	30
26	2	2	1	31
27	2	2	2	32

そうすると、重複は
・No.10、No.11、No.12
・No.19、No.20、No.21
なんとなく以下の法則が見えてきた。
・重複は、硬貨の(枚数+1)の分、連続して発生する
・重複が発生するときは、今まで計算した金額の最大値以下の金額になるとき

#発見した法則はたまたまかもしれない
今回たまたま上記のような法則になったけど、法則通りにならない場合があるかを考える。
とりあえず、プログラムにしやすそうな「重複が発生するときは、今まで計算した金額の最大値以下の金額になるとき」について考えてみる。
重複の金額を抜き出すと、以下のような表になる。

No.	10円の枚数	5円の枚数	1円の枚数	金額
7	0	2	0	10
8	0	2	1	11
9	0	2	2	12
10	1	0	0	10
11	1	0	1	11
12	1	0	2	12
16	1	2	0	20
17	1	2	1	21
18	1	2	2	22
19	2	0	0	20
20	2	0	1	21
21	2	0	2	22

No.7は、5円が2枚で10円、No.10は、10円が1枚で10円。
10円のループが0枚のときに、すでに5円が2枚で10円を計算しているためNo.10で重複になる。
パターンとして、5円が10円の代わりになった場合に重複することがわかる。
であれば、5円が10円の代わりにならないケースがあるかを考える。
枚数(n）が1枚の場合は、5円は10円の代わりにならない。n=1の場合の組み合わせは以下のようになる。

No.	10円の枚数	5円の枚数	1円の枚数	金額
1	0	0	0	0
2	0	0	1	1
3	0	1	0	5
4	0	1	1	6
5	1	0	0	10
6	1	0	1	11
7	1	1	0	15
8	1	1	1	16

そもそも重複が発生しない。

枚数(n）が4枚の場合は、1円は5円の代わりにならない。n=4の場合で、（数が多いので）1円と5円の組み合わせは以下のようになる。

No.	5円の枚数	1円の枚数	金額
1	0	0	0
2	0	1	1
3	0	2	2
4	0	3	3
5	0	4	4
6	1	0	5
7	1	1	6
8	1	2	7
9	1	3	8
10	1	4	9
11	2	0	10
12	0	1	11
	・・・	・・・	・・・

仮に、3円玉と5円玉がある世界だった場合、常に3円玉は5円玉の代わりにならない。n=2の場合で、3円と5円の組み合わせは以下のようになる。

No.	5円の枚数	3円の枚数	金額
1	0	0	0
2	0	1	3
3	0	2	6
4	1	0	5
5	1	1	8
6	1	2	11

重複は発生しないが、No.4で金額が前回(6円）よりも小さくなってしまっている。
そのため、この法則は、5円が10円の代わりをする場合、つまり、硬貨のように、カレントの硬貨（例えば5円）が上位の硬貨（5円の上位は10円）の約数（10円を5円で割り切れる）になっている場合しか成り立たないことがわかる。

ついでに、2円玉と3円玉と5円玉がある世界だった場合、n=2の場合で、2円と3円と5円の組み合わせは以下のようになる。

No.	5円の枚数	3円の枚数	2円の枚数	金額
1	0	0	0	0
2	0	0	1	2
3	0	0	2	4
4	0	1	0	3
5	0	1	1	5
6	0	1	2	7
7	0	2	0	6
8	0	2	1	8
9	0	2	2	10
10	1	0	0	5
11	1	0	1	7
12	1	0	2	9
13	1	1	0	8
14	1	1	1	10
15	1	1	2	12
16	1	2	0	11
17	1	2	1	13
18	1	2	2	15
19	2	0	0	10
20	2	0	1	12
21	2	0	2	14
22	2	1	0	13
23	2	1	1	15
24	2	1	2	17
25	2	2	0	16
26	2	2	1	18
27	2	2	2	20

2円+3円が5円の代わりになるため重複が発生するが、5円を3円で割り切れないため法則が当てはまらない。

#法則を発見してからそうなる理由を考える
上のケースでなんとなくわかってきたが、上位硬貨が下位硬貨すべてで割り切れる前提で、下位硬貨または下位硬貨の組み合わせが上位硬貨の代わりになる場合に、上位硬貨の計算時に重複が発生する。
例えば、10円0枚・5円2枚・1円0枚や、10円0枚・5円1枚・1円5枚が10円玉1枚の代わりになるため、10円1枚・5円0枚・1円0枚の金額計算時に重複が発生する。
重複が発生するということは、金額が小さい順に計算しているため、今まで計算した金額と同じか、それ以下になるということになる。
ループの順番から、10円が1枚になるループよりも前に5円が2枚になるループが発生するので、重複が発生するときは今まで計算した金額を超えることはないと考えることもできる。
5円のときも同様で、5円が2枚になるループよりも前に、5円が1枚、1円が5枚になるループが発生する。

上記法則を適用してプログラムを作成する。

sample.py

# 硬貨の枚数はそれぞれ2枚
n = 2
# 最大金額
max_kingaku = -1
# 10円の枚数分繰り返し 
#   rangeは、0～指定した数-1の繰り返し用の配列を生成するイメージ
#   0～2の数が生成される
for n10 in range(n+1):
    # 5円の枚数分繰り返し
    for n5 in range(n+1):
        # 1円の枚数分繰り返し
        for n1 in range(n+1):
            kingaku = n10*10 + n5*5 + n1*1
            if kingaku > max_kingaku:
                print("10円 {}枚 5円 {}枚 1円 {}枚 金額 {}".format(n10, n5, n1, kingaku))
                max_kingaku = kingaku

あとは、50円、100円、500円の硬貨を増やして、ケースをカウントし、0円のケースを除外すれば完成となる。

sample.py

# 硬貨の枚数はそれぞれ2枚
n = 2
# 最大金額
max_kingaku = -1
count = 0
for n500 in range(n+1):
    for n100 in range(n+1):
        for n50 in range(n+1):
            # 10円の枚数分繰り返し 
            #   rangeは、0～指定した数-1の繰り返し用の配列を生成するイメージ
            #   0～2の数が生成される
            for n10 in range(n+1):
                # 5円の枚数分繰り返し
                for n5 in range(n+1):
                    # 1円の枚数分繰り返し
                    for n1 in range(n+1):
                        kingaku = n500*500 + n100*100 + n50*50 + n10*10 + n5*5 + n1*1
                        if kingaku > max_kingaku:
                            max_kingaku = kingaku
                            count = count + 1
# 0円のケースを除外
count = count - 1

#処理を速くする場合はループを減らす
処理を速くするために、極力ループ回数を減らすことを考える。

・重複は、硬貨の(枚数+1)の分、連続して発生する

という法則を掘り下げて考えると、ループの削減につながりそう。
また、条件を単純にして考える（1円、5円、10円のみ）。
5円が10円の代わりをするときは重複するので、10円が1枚の場合は5円が0枚のケースを計算する必要がない。
n=2で、10円が1枚、5円が0枚、1円が0～2枚のケースは、すべて5円が2枚のケースで計算済である。
10円が2枚の場合も、5円が0枚のケースは、10円1枚、5円2枚で計算しているため、計算済である。
つまり、10円が1枚以上の場合は、5円が0枚のときのループをスキップできる。

No.	10円の枚数	5円の枚数	1円の枚数	金額
7	0	2	0	10
8	0	2	1	11
9	0	2	2	12
10	1	0	0	10
11	1	0	1	11
12	1	0	2	12
13	1	1	0	15
14	1	1	1	16
15	1	1	2	17

#少しずつ条件を変えて、ループをスキップできる条件を特定していく
1円の場合も上記のルールが成立するか確認する。
1円が5円の代わりになるのは、n=5以上の場合なので、n=5で確認する。

No.	10円の枚数	5円の枚数	1円の枚数	金額
1	0	0	0	0
2	0	0	1	1
3	0	0	2	2
4	0	0	3	3
5	0	0	4	4
6	0	0	5	5
7	0	1	0	5
8	0	1	1	6
9	0	1	2	7
10	0	1	3	8
11	0	1	4	9
12	0	1	5	10
13	0	2	0	10
14	0	2	1	11
15	0	2	2	12
16	0	2	3	13
17	0	2	4	14
18	0	2	5	15

同じように、5円が1枚以上の場合は、1円が0枚のときのループをスキップできる。

5円が2枚で、10円の代わりになるということは、5円が4枚(n=4)で10円が2枚の代わりになり、そうすると5円が2枚までのループをスキップできる可能性がある。

No.	10円の枚数	5円の枚数	1円の枚数	金額
1	0	0	0	0
2	0	0	4	4
3	0	1	4	9
4	0	2	4	14
5	0	3	4	19
6	0	4	4	24
7	1	0	4	14
8	1	1	4	19
9	1	2	4	24
10	1	3	0	25

予想通り、10円が1枚以上の場合、5円が2枚以下のループはスキップできる。

n=2とn=4を確認したので、n=3の場合も確認する。

No.	10円の枚数	5円の枚数	1円の枚数	金額
1	0	0	0	0
2	0	0	3	3
3	0	1	3	8
4	0	2	3	13
5	0	3	3	18
6	1	0	3	13
7	1	1	3	18
8	1	2	0	20

10円が1枚以上の場合、5円が1枚以下のループはスキップできる。
条件を変えていくと、スキップできる枚数は、nによって変わってくることがわかる。
nによって変わるということは何かしらの計算式が成り立つということになる。

実際の値を当てはめると、以下の式が成り立つ。
5円を計算し始める枚数 = n + 1 - (10/5) = n - 1
1円を計算し始める枚数 = n + 1 - (5/1) = n - 4
n=2の場合、5円は1枚目から計算し、1円はマイナスになるため、0枚目から計算する。
n=5の場合、5円は4枚目から計算し、1円は1枚目から計算する。

プログラムを書いてみる。

sample.py

# 硬貨の枚数はそれぞれ2枚
n = 2
# 最大金額
max_kingaku = -1
count = 0

# 計算し始める枚数
st100=n+1-int(500/100)
if st100 < 0:
    st100 = 0
st50=n+1-int(100/50)
if st50 < 0:
    st50 = 0
st10=n+1-int(50/10)
if st10 < 0:
    st10 = 0
st5=n+1-int(10/5)
if st5 < 0:
    st5 = 0
st1=n+1-int(5/1)
if st1 < 0:
    st1 = 0

# 500円の繰り返し
for n500 in range(n+1):
    # ループが0の場合は重複を考えない
    if n500 == 0:
        rst100 = 0
    else:
        rst100 = st100
    # 100円の繰り返し
    for n100 in range(rst100,n+1):
        if n100 == 0:
            rst50 = 0
        else:
            rst50 = st50
        # 50円の繰り返し
        for n50 in range(rst50,n+1):
            if n50 == 0:
                rst10 = 0
            else:
                rst10 = st10
            # 10円の繰り返し
            for n10 in range(rst10,n+1):
                if n10 == 0:
                    rst5 = 0
                else:
                    rst5= st5
                # 5円の枚数分繰り返し
                for n5 in range(rst5,n+1):
                    if n5 == 0:
                        rst1 = 0
                    else:
                        rst1= st1
                    # 1円の枚数分繰り返し
                    for n1 in range(rst1,n+1):
                        # 重複分をスキップしているので、計算する必要がない
                        count = count + 1
# 0円のケースを除外
count = count - 1
print ("{}".format(count))

#ループなしにすることを考える
ここからは課題実施時に間に合わなかった分になる。

上記のようにループの中で計算しないのであれば、ループ処理にしなくてもケース数がカウントできるはずである。
ざっくり言えば、上記のプログラムは、上位の硬貨が0枚の場合はカレントの硬貨は0枚から計算し、上位の硬貨が1枚以上の場合は、カレントの硬貨はn+1-(上位硬貨/カレント硬貨)枚から計算している。
つまり、上位の硬貨が0枚になる組み合わせと上位の硬貨が1枚以上になる組み合わせを求めればループなしで組み合わせを計算できる。
また、n=2で10円と5円と1円で考えてみると、
10円が0枚になるケースは1回、10円が1枚以上になるケースは2回
5円を0枚～2枚でカウントするのは10円が0枚のときの1回。
5円を1枚～2枚でカウントするのは10円が1枚以上の2回。
10円と5円だけの組み合わせだった場合、5円の繰り返し回数は、
1×3 + 2×2 = 7 (10円が0のときの1回×5円3回分 + 10円が1以上のときの2回×5円2回分)
1円も同じように考えると、
1円を0枚から2枚でカウントするのは5円が0枚～2枚のときの3回
1円の繰り返し回数は5円の繰り返し回数×1円の繰り返し回数になる。
また、1円の繰り返し回数は金額の組み合わせ回数でもある。
7 × 3 = 21 (5円の繰り返し回数 × 1円の繰り返し回数)
これをプログラムにすると以下のようになる（500円まで拡張したもの）。

sample.py

# 枚数を入力
n = 2

# 100円の開始INDEX算出
st100 = n + 1 - int(500/100)
if st100 < 0:
    st100=0
# 50円の開始INDEX算出
st50 = n + 1 - int(100/50)
if st50 < 0:
    st50=0
# 10円の開始INDEX算出
st10 = n + 1 - int(50/10)
if st10 < 0:
    st10=0
# 5円の開始INDEX算出
st5 = n + 1 - int(10/5)
if st5 < 0:
    st5=0
# 1円の開始INDEX算出
st1 = n + 1 - int(5/1)
if st1 < 0:
    st1=0

count = 0

#500円が0から始まる回数
bc500=1
#500円の繰り返し回数
bl500=n+1

#100円が0から始まる回数
if st100 > 0:
    # 100円のスタートが0以外の場合は、500円が0になる回数
    bc100 = bc500
else:
    # 100円のスタートが0の場合は500円の繰り返し回数
    bc100 = bl500

# 100円の繰り返し回数
# 500円が0から始まる回数×100円の回数＋500円が0以外の回数×100円の回数（重複除外版）
bl100 = bc500*(n+1) + (bl500-bc500)*(n+1-st100) 

#50円が0から始まる回数、50円の繰り返し回数
if st50 > 0:
    bc50 = bc100
else:
    bc50 = bl100
bl50 = bc100*(n+1) + (bl100-bc100)*(n+1-st50) 

# 10円が0から始まる回数、10円の繰り返し回数
if st10 > 0:
    bc10 = bc50
else:
    bc10 = bl50
bl10 = bc50*(n+1) + (bl50-bc50)*(n+1-st10) 

# 5円が0から始まる回数、5円の繰り返し回数
if st5 > 0:
    bc5 = bc10
else:
    bc5 = bl10
bl5 = bc10*(n+1) + (bl10-bc10)*(n+1-st5) 

# 1円が0から始まる回数、1円の繰り返し回数
if st1 > 0:
    bc1 = bc5
else:
    bc1 = bl5
bl1 = bc5*(n+1) + (bl5-bc5)*(n+1-st1) 

# 0円を除外
count = bl1 - 1

print("硬貨{}枚ずつの金額の組み合わせは、{}です。".format(n,count))                    

#まとめ
アルゴリズムが思いつかないときは、条件を単純化したり、データを眺めたり、条件を少しずつ変えたりしていくと、法則らしきものが見えてくる。見えてきた法則が正しいと仮定してプログラムを組めば、法則の理由が見えてくる。