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

プロジェクトオイラー問9 - (2014/02/12 (水) 17:28:27) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 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)倍した三角形が答えです。
+原始ピタゴラス数の三辺 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).