※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

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

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

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

+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)
+	.