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

プロジェクトオイラー問７５ - (2014/03/02 (日) 06:26:56) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2075


*Problem 75 「1通りの整数直角三角形」 †
ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Lを鉄線の長さとする. 直角三角形を作るときに1通りの折り曲げ方しか存在しないような L ≤ 1,500,000 の総数を答えよ.

注: この問題は最近変更されました. あなたが正しいパラメータを使っているか確認してください.


解法
原始ピタゴラス数とそれを相似拡大したもの全てを求め、そのリストをソートして一個しかないものを抽出します。
Ｐｒｏｌｏｇ言語なので集合の概念から攻めますがＣ++ならもうちょっと賢い方法がありそうです。


 gcd(0, B, G) :- G is abs(B).
 gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).
 
 count_one([],_,1,1):-!.
 count_one([],_,_,0):-!.
 count_one([L|Ls],L,Count,Result):-
 	!,
 	Count1 is Count+1,
 	count_one(Ls,L,Count1,Result).
 count_one([L|Ls],_,1,Result):-
 	!,
 	count_one(Ls,L,1,Re),
 	Result is Re+1.
 count_one([L|Ls],_,_,Result):-
 	count_one(Ls,L,1,Result).
 
 searchBai(L,_,_):-L>1500000,!,fail.
 searchBai(L,_,L).
 searchBai(L,Add,Result):-
 	L1 is L+Add,
 	searchBai(L1,Add,Result).
 
 searchN(M,L1):-
 	between(1,M,N),
 	N<M,
 	((M-N) mod 2)=:=1,
  	gcd(N,M,G),
 	G=:=1,
 	L is 2*M*(M+N),
 	(L>1500000 -> !,fail;true),
 	searchBai(L,L,L1)
  	.
 
 searchM(L1):-
 	between(2,4000,M),
  	searchN(M,L1).
 
 main75:-
 	findall(L1,searchM(L1),Lens),
 	msort(Lens,[L|Lens1]),
 	count_one(Lens1,L,1,Ans),
 	write(Ans).