« 「マヨイドーロ問題」の高度じゃないコード | トップページ | 「スクエア・カルテット問題」の高度じゃないコード »

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 とやってしまってかなり悩んだのは内緒です・・・。

しかし、この方法はケアレスミスが起きやすいです。現に、実際に計算してみると結果が違っていて、見直して修正ということを数回繰り返してようやく上の正しい式になりました。でも、本当は、こういう面倒な作業こそコンピュータにやらせたいですね。

なので、今度は、手作業によるパラメータの計算をやめ、2つの式の掛け算をする関数を作ってみることにしました。全ての組み合わせを計算し、ルートの中身が 30, 15, 10, 6, 5, 3, 2 の2乗になったら、ルートの外に出して、対応したパラメータに結果を加算するというやり方です。答えが合っていることを確認して、再提出したコードを示します。

最初の、だらだらと長い式が並ぶコードと比べると、かなりすっきりしました。

解説や他の方の書かれたコードを見ると、Ruby では行列のべき乗がサポートされているので、それを利用してもいいようです。私は、まず C で作ってみるので、C でサポートされてない行列のべき乗なんて全く思いつきませんでしたが・・・。ちなみに、Cで書いて提出した最初のコードがこれです。すぐにオーバーフローしてしまうので、パラメータを計算するごとに 107 での剰余を取っています。

|

« 「マヨイドーロ問題」の高度じゃないコード | トップページ | 「スクエア・カルテット問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/62941439

この記事へのトラックバック一覧です: 「ルート・パワー問題」の高度じゃないコード:

« 「マヨイドーロ問題」の高度じゃないコード | トップページ | 「スクエア・カルテット問題」の高度じゃないコード »