※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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).