泥庭

2010年10月3日

Project Euler 304

Filed under: Project Euler — タグ: — yone64 @ 4:08 AM

たまたま問題公開直前にサイトにアクセスしていたので、チャレンジしてみた。

(問題は↓)
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20304

数学的なアプローチが全然思いつかないので、超強引にプログラムを書いて実行。
1014より大きな素数は、時間がかかるものの、まだ答えが出るが、フィボナッチ数列の1014番目とか無理でした。半日まわして、やっと1012番目。
仕方がないので、順列でフィボナッチはあきらめる。別の方法で。。。

フィボナッチ数列は一般項があるらしい。(Wikipedia)

Fn = (βn – αn) / √5
β = (1 + √5) / 2
α = (1 – √5) / 2

でも、素直にMath.Sqrtとか、Math.Powとかに突っ込んでも有効桁数の問題で1014乗とか正しく計算出来なさそう。
整数項と√5の係数とを別々に計算するのが正しいのだろうね。今度やってみよう。

広告

WordPress.com Blog.