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).

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年02月13日 01:21