「プロジェクトオイラー問３９」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問３９」(2014/02/15 (土) 17:52:04) の最新版変更点

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

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

*Problem 39 「整数の直角三角形」 †
辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000 のとき解の数が最大になる p はいくつか?


解法
周長1000以下の原始ピタゴラス数とその定数倍のリストを得て出現回数をカウントするだけです。


 gcd(0, B, B).
 gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
 
 calc_ok(M,N):-
 	((M-N) mod 2)=:=1,
 	gcd(M,N,G),
 	G=:=1
 	.
 calc(M,N,Result):-
 	Result is M^2+N^2+2*M*N+M^2-N^2.
 
 loopN(M,N,_):-
 	M=<N,
 	!,
 	fail.
 
 loopN(M,N,_):-
 	calc(M,N,Len),
 	Len>1000,
 	!,
 	fail.
 loopN(M,N,Result):-
  	calc_ok(M,N),
 	calc(M,N,Len),
  	between(1,1000,Bai),
 	Result is Len*Bai,
 	(Result>1000 -> !,fail;true).
 
 loopM(Result):-
 	between(1,31,M),
 	loopN(M,1,Result).
 count([],C,[C]):-!.
 count([X|Xs],[C,X],Result):-
 	!,
 	C1 is C+1,
  	count(Xs,[C1,X],Result).
 count([X|Xs],C,[C|Result]):-
 	!,
 	count(Xs,[1,X],Result).
 
 main39:-
 	findall(Len,loopM(Len),Lens),
 	msort(Lens,Lens1),
  	[Top|Lens2]=Lens1,
 	count(Lens2,[1,Top],AnsList),
 	msort(AnsList,AnsList1),
 	write(AnsList1).