「プロジェクトオイラー問57」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問57 - (2014/02/19 (水) 16:38:19) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2057
Problem 57 「平方根の近似分数」 †
2の平方根は無限に続く連分数で表すことができる.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?



解法
定義通り実装します。
一回繰り返し計算するごとに1を足して答えを確定し、既約分数にしてからketaで桁数を比較しています。
桁数比較は文字列のリストに変換してその長さを比較しています。

 
 gcd(0, B, B).
 gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
 
 keta(U2,D2):-
 	number_codes(U2,UL),
 	number_codes(D2,DL),
 	length(UL,LenU),
 	length(DL,LenD),
 	LenU>LenD.
 
 calc(1001,_,_,_):-
 	!,
 	fail.
 calc(_,U,D,1):-
 	D1 is D,
 	U1 is U+D,
  	gcd(U1,D1,G),
 	U2 is U1//G,
 	D2 is D1//G,
 	keta(U2,D2).
 
 calc(Deep,U,D,Result):-
 	U1 is U+D*2,
 	D1 is D,
 	gcd(U1,D1,G),
  	D2 is U1//G,
 	U2 is D1//G,
 	Deep1 is Deep+1,
 	calc(Deep1,U2,D2,Result).
 
 main57:-
 	findall(C,calc(1,1,2,C),Counts),
 	length(Counts,Ans),
 	write(Ans).