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

プロジェクトオイラー問３９ - (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).