« 2016年3月 | トップページ | 2016年5月 »

2016年4月 7日 (木)

「ディビジョン・ナイン問題」の高度じゃないコード

先月初めの連続記事からちょっと間が開きましたが「高度じゃないコード」シリーズその10、「ディビジョン・ナイン問題」です。

1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。
標準入力から、自然数 n(1 ≦ n ≦ 20)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

数学の問題をプログラミングで解こう!「ディビジョン・ナイン」問題解説

9の倍数と言われてまず思いつくのが、9で割った余りは各桁の和を9で割った余り、つまり、各桁の和が9で割り切れる数字は9の倍数ということです。1~4の数字を組み合わせて9・18・27・・・という9の倍数になる組み合わせを求めるわけです。例えば、n桁の4進数と考えると、各桁の数字は0~3となりますが1足すことで1~4となるので、n桁の4進数の各桁の和に桁数を加えたものが9の倍数かどうかを調べることになります。ただし、最大20桁の4進数となると、420で約1.1兆通りの数字を逐一調べるのは効率が悪く、タイムアウトになるのは目に見えています。

この考え方のままで効率よく計算させる方法は残念ながら思いつかなかったので、とりあえず、9で割った余りが0~8になる数字がそれぞれ幾つあるかを、桁数を1桁づつ増やしながら調べていくことにしました。

さて、1桁増えた場合の処理ですが、2通りの方法が考えられます。ループで変化させる数値を、増えた桁の数1~4にするか余りの数0~8にするかです。そう、「プラス・マイナス・ゼロ問題」の高度じゃないコードの時と同じです。今回、前者を選ぶと、同じ配列要素に値を4回に分けて足すことになるので、それに伴い値の初期化も必要になります。後者を選ぶと、1つの配列要素の計算は1回でできるので、値の初期化も不要になります。私は後者を選びましたが、実装次第でどちらが短くなるかは変わりますね。まぁ、今回はコードゴルフは考えてないので・・・。

そして、1桁増えた時の計算方法は次のようなものになります。
・余り0の数は、1桁増える前の余り8(+1)・余り7(+2)・余り6(+3)・余り5(+4)の数の和
・余り1の数は、1桁増える前の余り0(+1)・余り8(+2)・余り7(+3)・余り6(+4)の数の和
・余り2の数は、1桁増える前の余り1(+1)・余り0(+2)・余り8(+3)・余り7(+4)の数の和
・余り3の数は、1桁増える前の余り2(+1)・余り1(+2)・余り0(+3)・余り8(+4)の数の和
・余り4の数は、1桁増える前の余り3(+1)・余り2(+2)・余り1(+3)・余り0(+4)の数の和
・余り5の数は、1桁増える前の余り4(+1)・余り3(+2)・余り2(+3)・余り1(+4)の数の和
・余り6の数は、1桁増える前の余り5(+1)・余り4(+2)・余り3(+3)・余り2(+4)の数の和
・余り7の数は、1桁増える前の余り6(+1)・余り5(+2)・余り4(+3)・余り3(+4)の数の和
・余り8の数は、1桁増える前の余り7(+1)・余り6(+2)・余り5(+3)・余り4(+4)の数の和

なお、私のコード中では0桁の場合に余り0が1通りのみをスタートとしましたが、1桁の場合に余り1~4がそれぞれ1通りというのをスタートにした方がわかりやすいかもしれません。もちろん、どちらにしても、ループの回数が1回変わるだけで結果は同じになりますが・・・。

続きを読む "「ディビジョン・ナイン問題」の高度じゃないコード"

| | コメント (1) | トラックバック (0)

« 2016年3月 | トップページ | 2016年5月 »