「プロジェクトオイラー問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).

表示オプション

横に並べて表示:
変化行の前後のみ表示: