« 2015年11月 | トップページ | 2016年1月 »

2015年12月26日 (土)

「ルート・パワー問題」の高度じゃないコード

はい、「高度じゃないコード」シリーズその2です(^_^;)。今回のお題は「ルート・パワー問題」です。

数学の問題をプログラミングで解こう!「ルート・パワー」問題解説

与えられた自然数 n ( 1 ≦ n ≦ 1010 ) に対し、( 1 + √2 + √3 + √5 )n を計算し、有理数の項の値を求めよという問題です。ただし、普通に計算すると、前回の「マヨイドーロ問題」のように、使用する言語によって通常計算で扱える整数の制限から難易度が上がるので、ここでは、107 で割った余りを答えればいいことになっています。

まず、ループで1回ごとに ( 1 + √2 + √3 + √5 ) を掛けていく計算だと、最大で 1010 回となることから、制限時間の1秒以内には到底終わりそうにありません。そこで、掛け算の筆算の要領で計算していくことにしました。初期値を 1(0乗)とし、2進数に直した n の最上位ビットより順番に、ビットが0の場合はそれまでの計算結果の単なる2乗(×2)、ビットが1の場合は2乗したものに ( 1 + √2 + √3 + √5 ) を掛けます(×2+1)。それを、最下位ビットまで繰り返します。こうすることで、0乗から始まって最終結果は n乗となるわけです。また、この方法ではループ回数は34回以下となります。

さて、( 1 + √2 + √3 + √5 )n を計算することで、最初からある √2, √3, √5 以外に、それらの積である √6, √10, √15 と √30 が出現します。そこで、p[] という配列を使って次のような形で考えてみることにします。

p[0] + p[1] * √2 + p[2] * √3 + p[3] * √5 + p[4] * √6 + p[5] * √10 + p[6] * √15 + p[7] * √30

ということで、作るべきは、この式を2乗する処理と、この式に ( 1 + √2 + √3 + √5 ) を掛ける処理の2つです。最初に、手計算による結果を式に直すという方法をとってみました。つまり、上記の式を2乗した時と、( 1 + √2 + √3 + √5 ) を掛けた時に、各パラメータ p[] がどうなるのかを手作業で計算し式に直しました。

いつものように C言語で作成し、勉強のために、それを Ruby に移植して提出したコードを示します。もっとスマートに書けると思いますが、初めて作った Ruby のコードということで勘弁してください。最初、p = t.dup の部分を、単に p = t とやってしまってかなり悩んだのは内緒です・・・。

続きを読む "「ルート・パワー問題」の高度じゃないコード"

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

2015年12月21日 (月)

「マヨイドーロ問題」の高度じゃないコード

最近、CodeIQというサイトに嵌ってます。出題される問題を、好きなプログラム言語で解くコードを作成して挑戦するというものです。ただ、ほとんどの問題は、その問題やコードについてブログ等で公開することは禁じられているんですが、時々、挑戦期間終了後に限り、それが許可された問題があります。「マヨイドーロ問題」はそのような問題の1つです。

結城浩の「マヨイドーロ問題」解説

今回の問題は自動採点といって、使用言語を選択してコードを入力すれば、サーバー側でコンパイル・実行し、自動的にテスト数値が入力されそれに対する出力をチェックし、全部のテスト数値について答えが合っていたら正解となります。まずは、いつも挑戦に使っているC言語で書いてみました。今回の問題には、出題されるテスト数値の上限が書かれていないので、結果がどれぐらいの値になるか不明ですが、今までの例だと、32bit整数だとオーバーフローして、64bit整数だとOKなことが多かったので、64bit整数でコーディングしました。

ところが、100までの数値では正解を出せましたが、その次のいきなり10倍になった1000であえなく死亡。しかも、その後にはラスボス2015というとんでもない数値の化け物が控えていました。仕方ないので、32bit符号なし整数を連結して多倍長計算するようにコーディングしました。といっても、必要だったのは、連結整数同士の加算と10進表示の2つぐらいです。

続きを読む "「マヨイドーロ問題」の高度じゃないコード"

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

« 2015年11月 | トップページ | 2016年1月 »