魔方分割数
Posted feedbacks - Prolog
普通にfindallすると、スタックオーバーフローするので、数だけ数えるようにしています。 副作用を使っているのは、数を数える部分だけで、本質的なところではないので、許して下さい。 あんまり早くなくて残念。 実行時間 N=4の場合、 $ time pl -qs 108-1.pl 392 real 0m0.049s user 0m0.043s sys 0m0.006s N=5の場合 $ time pl -qs 108-1.pl 3245664 real 13m27.466s user 13m19.891s sys 0m0.909s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | maho(N,R):-SS is integer(N ^ 2),
S is integer((SS + 1) * SS / 2 / N),
seq(SS,Lx),
reverse(Lx,Lxx),
C=c(0),
(gen(N,S,Lxx,_,_),
countup(C),
fail
;C=c(R)).
countup(C):-arg(1,C,N0),succ(N0,N1),nb_setarg(1,C,N1).
gen_list(1,V,[1],[V]).
gen_list(X,V,[0|L],[0|T]):-
succ(X1,X),
gen_list(X1,V,L,T).
gen(N,_,[V],L,T):-!,
gen_list(N,V,L,T).
gen(N,S,[I|Is],L,T):-
gen(N,S,Is,Ls,T0),
addH(N,S,Ls,T0,I,L,T).
addH(_,_,[],_,_,_):-fail.
addH(N,S,[L|Ls],[T|Ts],I,[L1|Ls],[T1|Ts]):-
Ls\=[0|_],
L1 is L + 1,
T1 is T + I,
(L1=N,S=T1;T1<S,L1<N).
addH(N,S,[L|Ls],[T|Ts],I,[L|Lss],[T|Tss]):-
addH(N,S,Ls,Ts,I,Lss,Tss).
seq(0,[]).
seq(N,[N|L]):-
succ(N1,N),
seq(N1,L).
:-maho(5,C),write(C),nl,halt.
|
xsd
#4702()
Rating8/8=1.00
たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。
ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。
なお、数え上げるときの注意として、
・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの
・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
[ reply ]