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

プロジェクトオイラー問９ - (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++ならｍとｎの２重ループとするところをProloｇでこれを再帰の探索に翻訳して解きます。
ｍが大きくなればｃは単調増加しますので、ｍ^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).