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

プロジェクトオイラー問61」(2014/02/21 (金) 15:29:52) の最新版変更点

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

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2061 *Problem 61 「巡回図形数」 † 三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される. 三角数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ... 四角数 P4,n=n2 1, 4, 9, 16, 25, ... 五角数 P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ... 六角数 P6,n=n(2n-1) 1, 6, 15, 28, 45, ... 七角数 P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ... 八角数 P8,n=n(3n-2) 1, 8, 21, 40, 65, ... 3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている 4桁の数の組で上の2つの性質をもつはこの組だけである. 三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ. 解法 全探索でいい気もしますが。 一応動的計画法で解いてみました。 巡回するのでどの数から初めても問題ありません。 よって三角数を最初にして。 その後は - 三角数の1000と100の位、 - 使用済みのn角数をビットで管理 - 一番最後に選んだ数の下2桁 この3つを主キーに、そこまでの合計値を主キーに対する値として動的計画法で回します。 n個だけ角数から選んだ状態からn+1個選んだ状態を計算します。 解が唯一であるというヒントを頼りに、主キーが同じになったものは一つだけ残して他は廃棄します。 効率化できたかどうかは微妙なところです。 ps3(N,N3):- N3 is (N*(N+1))//2. ps4(N,N4):- N4 is N^2. ps5(N,N5):- N5 is (N*(N*3-1))//2. ps6(N,N6):- N6 is N*(2*N-1). ps7(N,N7):- N7 is (N*(5*N-3))//2. ps8(N,N8):- N8 is N*(3*N-2). ps(Siki,[P1,P2]):- between(1,200,N), call(Siki,N,Pa), 1000=<Pa, Pa=<9999, P1 is Pa//100, P2 is Pa mod 100. ps_w(Siki,Result):- findall(R,ps(Siki,R),Result). one_calc([Top,Bits,Tail,Sum],Ps,[Top,Bits1,Tail1,Sum1]):- between(0,5,No), (Bits /\ (1<<No))=:=0, Bits1 is Bits \/ (1<<No), nth0(No,Ps,P), member([Tail,Tail1],P), Sum1 is Sum+Tail*100+Tail1. next_calc(DP,Ps,Result):- member(E,DP), one_calc(E,Ps,Result). myunion([],Set,[Set]):-!. myunion([[Top,Bits,Tail,_]|Rest],[Top,Bits,Tail,Sum],Result):- !, myunion(Rest,[Top,Bits,Tail,Sum],Result). myunion([Set|Rest],Set1,[Set1|Result]):- !, myunion(Rest,Set,Result). to_seed([],[]):-!. to_seed([[Top,Tail]|Rest],[[Top,1,Tail,Sum]|Result]):- Sum is Top*100+Tail, to_seed(Rest,Result). ok_list([],[]):-!. ok_list([[Top,_,Top,Sum]|Rest],[Sum|Result]):- !, ok_list(Rest,Result). ok_list([_|Rest],Result):- !, ok_list(Rest,Result). dp(6,DP,_):- !, ok_list(DP,Ans), write(Ans). dp(Deep,DP,Ps):- !, findall(Re,next_calc(DP,Ps,Re),NextDP), sort(NextDP,[Top|NextDP1]), myunion(NextDP1,Top,NextDP2), Deep1 is Deep+1, dp(Deep1,NextDP2,Ps). main61:- ps_w(ps3,Ps3), ps_w(ps4,Ps4), ps_w(ps5,Ps5), ps_w(ps6,Ps6), ps_w(ps7,Ps7), ps_w(ps8,Ps8), PsAll =[Ps3,Ps4,Ps5,Ps6,Ps7,Ps8], to_seed(Ps3,Seed), dp(1,Seed,PsAll) .

表示オプション

横に並べて表示:
変化行の前後のみ表示: