DouKaku? 4852 katsu: 普通にfindallすると、スタックオー...(魔方分割数)

Comment detail

普通に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

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.

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq