「プロジェクトオイラー問9」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問9」(2014/02/13 (木) 01:21:18) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
Problem 9 「特別なピタゴラス数」 †
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
解法
原始ピタゴラス数を求める公式はWikiにある通りです。
原始ピタゴラス数の三辺 a+b+cが1000の約数になればそれを1000/(a+b+c)倍した三角形が答えです。
C++ならmとnの2重ループとするところをPrologでこれを再帰の探索に翻訳して解きます。
mが大きくなればcは単調増加しますので、m^2+1^2が1000を超えればa+b+cは1000を超えてしまうので探索を打ち切ります。
nも同様にm^2+n^2が1000を超えれば探索を打ち切ります。
後はこれをコードにするだけです。
gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
calc(M,N,A,B,C):-
A is 2*M*N,
B is M*M-N*N,
C is M*M+N*N.
is_over(M,N):-
calc(M,N,_,_,C),
(C>1000;M=<N).
is_calcOK(M,N):-
(M-N) mod 2=:=1,
gcd(M,N,G),
G=:=1,
M>N.
searchN(M,N,_):-
is_over(M,N),
!,
fail.
searchN(M,N,Result):-
is_calcOK(M,N),
calc(M,N,A,B,C),
1000 mod (A+B+C)=:=0,
!,
Mult is 1000//(A+B+C),
Result is A*B*C*(Mult^3).
searchN(M,N,Result):-
!,
N1 is N+1,
searchN(M,N1,Result).
searchM(M,_):-
is_over(M,1),
!,
fail.
searchM(M,Result):-
searchN(M,1,Result).
searchM(M,Result):-
M1 is M+1,
searchM(M1,Result).
main9:-
searchM(2,Ans),write(Ans).
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
Problem 9 「特別なピタゴラス数」 †
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
解法
原始ピタゴラス数を求める公式はWikiにある通りです。
原始ピタゴラス数の三辺 a+b+cが1000の約数になればそれを1000/(a+b+c)倍した三角形が答えです。
C++ならmとnの2重ループとするところをPrologでこれを再帰の探索に翻訳して解きます。
mが大きくなればcは単調増加しますので、m^2+1^2が1000を超えればa+b+cは1000を超えてしまうので探索を打ち切ります。
nも同様にm^2+n^2が1000を超えれば探索を打ち切ります。
後はこれをコードにするだけです。
betweenを使った解法。
gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
calc(M,N,A,B,C):-
A is 2*M*N,
B is M*M-N*N,
C is M*M+N*N.
is_over(M,N):-
calc(M,N,_,_,C),
(C>1000;M=<N).
is_calcOK(M,N):-
(M-N) mod 2=:=1,
gcd(M,N,G),
G=:=1,
M>N.
search(ABC):-
between(2,40,M),
M1 is M-1,
between(1,M1,N),
(is_over(M,N)->!,fail;true),
is_calcOK(M,N),
calc(M,N,A,B,C),
1000 mod (A+B+C)=:=0,
ABC is A*B*C*(1000/(A+B+C))^3.
main9:-search(Ans),write(Ans).
原理主義的に再帰を使った解法。
コードが膨らんでいる。
gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
calc(M,N,A,B,C):-
A is 2*M*N,
B is M*M-N*N,
C is M*M+N*N.
is_over(M,N):-
calc(M,N,_,_,C),
(C>1000;M=<N).
is_calcOK(M,N):-
(M-N) mod 2=:=1,
gcd(M,N,G),
G=:=1,
M>N.
searchN(M,N,_):-
is_over(M,N),
!,
fail.
searchN(M,N,Result):-
is_calcOK(M,N),
calc(M,N,A,B,C),
1000 mod (A+B+C)=:=0,
!,
Mult is 1000//(A+B+C),
Result is A*B*C*(Mult^3).
searchN(M,N,Result):-
!,
N1 is N+1,
searchN(M,N1,Result).
searchM(M,_):-
is_over(M,1),
!,
fail.
searchM(M,Result):-
searchN(M,1,Result).
searchM(M,Result):-
M1 is M+1,
searchM(M1,Result).
main9:-
searchM(2,Ans),write(Ans).