「プロジェクトオイラー問３８」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問３８」(2014/02/15 (土) 17:52:22) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*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).
Problem 38 「パンデジタル倍数」 †
192 に 1, 2, 3 を掛けてみよう.
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.
同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.
整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?
解法
まずは1を書けるのですから求める先頭数字は9であることを期待します。
xを何らかの一文字の数字とすると
9xの場合、*１*２,*３,*4,で２桁 ３桁 ３桁 ３桁と計11桁で９桁が得られません。
9xxも *１,*２,*３で３桁４桁４桁 計１１桁です。
9ｘｘｘｘ*1、*２で１０桁を超えます。
よって残るのは9ｘｘｘの４桁となります。
ここからはｎ桁目を9ｘｘｘの左からｎ桁目とします。
まず9ｘｘｘ*1と9ｘｘｘ*２の結合を考えると
9xxx18xxx
となります。
すると２桁目は繰り上がると18が19になるので5,6,7,8,9は入りませんし0は0*1＝0でパンデジタル数の条件に反します。
２桁目は2か３か4しか入りませんが4は２倍すると8で8とかぶり３桁目からの桁上りがあると9になりこれもダメ。
よって２桁目は２か３となります。
３桁目と４桁目は2,3,6,7しか入りません。
ここから大きな数から検討します。
２桁目が３だとします。
３桁目が7だと繰り上がって２桁目は3*２+1＝7で7が重複するので駄目です。
３桁目が6だと４桁目は5を作るために7となります。
9367 18734
で7が重複します。
３桁目が２だと。
5を作るために４桁目を7にしないといけません。
よって答えは
9327と18654
932718654となります。
9より小さい数を１桁目に持ってくると必ず932718645より小さくなるのでこれですべての場合を検討したことになります。
