泥庭

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の係数とを別々に計算するのが正しいのだろうね。今度やってみよう。

広告

コメントする »

まだコメントはありません。

RSS feed for comments on this post. TrackBack URI

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

WordPress.com で無料サイトやブログを作成.

%d人のブロガーが「いいね」をつけました。