「プロジェクトオイラー問75」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問75」の最新版変更点

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

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

+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 の総数を答えよ.
+
+注: この問題は最近変更されました. あなたが正しいパラメータを使っているか確認してください.
+
+
+解法
+原始ピタゴラス数とそれを相似拡大したもの全てを求め、そのリストをソートして一個しかないものを抽出します。
+Prolog言語なので集合の概念から攻めますがC++ならもうちょっと賢い方法がありそうです。
+
+
+ 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).