「プロジェクトオイラー問１０４」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１０４」(2014/03/07 (金) 08:39:06) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20104

*Problem 104 「両端がパンデジタルなフィボナッチ数」 †
フィボナッチ数列は再帰的な関係によって定義される:

Fn = Fn−1 + Fn−2
F541 (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. そして, F2749 (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

Fkが, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき, kを求めよ.


解法
足し算を繰り返すとある桁以下は上位９桁に影響を与えなくなってきます。
上位１７桁くらいとっておけばまず安全に上位９桁を正確に算出できます。
安全マージンを取って上位２０桁以下は切り捨て。
として計算しました。
Ｃ++などでは１6桁くらいで計算するとよいでしょう
下位９桁はＭｏｄをとればよいだけです。


 num_cut(FL3,FL2,FL3,FL2):-FL3 <10^20,!.
 num_cut(FL3,FL2,FL33,FL22):-!,FL33 is FL3//10,FL22 is FL2//10.
 
 check(List):-!,
 	sort(List,[49,50,51,52,53,54,55,56,57]).
 
 
 calc(K,_,FL2,_,FR2):-
 	number_codes(FL2,ListL),
 	FR22 is FR2 mod 10^9,
 	number_codes(FR22,ListR),
 	[X1,X2,X3,X4,X5,X6,X7,X8,X9|_]=ListL,
 	check([X1,X2,X3,X4,X5,X6,X7,X8,X9]),
 	check(ListR),
 	!,
 	write(K).
 calc(K,FL1,FL2,FR1,FR2):-
 	FL3 is (FL1+FL2),
 	num_cut(FL3,FL2,FL33,FL22),
 	FR3 is (FR1+FR2) mod 10^9,
 	K1 is K+1,
 	!,
 	calc(K1,FL22,FL33,FR2,FR3).
 
 main104:-
 	calc(2,1,1,1,1).