「プロジェクトオイラー問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(0,0):-!,fail.
keta(U2,0):-U2>0,!.
keta(U2,D2):-
U3 is U2//10,
D3 is D2//10,
keta(U3,D3).
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).
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).