Herd Sums(4)
最短コードが狙えるアルゴリズム(上)
前回説明したアルゴリズムはすばらしい。しかし私は満足しない。この問題は、組み合わせの個数を答えるだけの問題なのだから、もっと単純な方法があるのではないか。
今まで書いたコードを元に、私は入力値1〜40位に対する出力をすべて調べた。
一際目を引くのは、入力値
in: out
- -
1: 2
2: 2
3: 2
4: 1
5: 2
6: 2
7: 2
8: 1
9: 3
10: 2
11: 2
12: 2
13: 2
14: 2
15: 4
16: 1
17: 2
18: 3
19: 2
20: 2
21: 4
22: 2
23: 2
24: 2
25: 3
26: 2
27: 4
28: 2
29: 2
30: 4
31: 2
32: 1
33: 4
34: 2
35: 4
36: 3
37: 2
38: 2
39: 4
『この問題は、2がポイントだ！』
入力値が5の場合、出力は2
入力値を5の2倍である10にしたときも、出力は2
10をさらに2倍した20でも、やはり出力は2
in: out
- -
5: 2
10: 2
20: 2
この特徴は、どの入力にも当てはまる、たとえば入力値9なら、
というようにいくら2をかけても出力はすべて3になるのだ。
in: out
- -
9: 3
18: 3
36: 3
因数に2をいくら持っていても、結果には何の作用もない。ということがわかった。
つづく
