Prolog 中的数字分解
Number decomposition in Prolog
我是 Prolog 的新手,我有以下问题:如何将自然数 N 分解为一个列表,其中包含总和等于 N 的连续自然数?
例如:
N=10, R=[1,2,3,4];
N=80, R=[14, 15, 16, 17, 18];
N=99, R=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
R=[7, 8, 9, 10, 11, 12, 13, 14, 15]
R=[14, 15, 16, 17, 18, 19]
R=[32, 33, 34]
R=[49, 50]
编辑:
我尝试在不使用默认方法的情况下构建列表,到目前为止我设法写了这篇文章:
cand([H|_],H).
cand([_|T],E):-
cand(T,E).
suma([],0).
suma([H|T],S):-
suma(T,Temp),
S is Temp+H.
list(0,[]).
list(N,[Nr|R]):-
Nr is N-1,
list(Nr,R).
generate(_,_,A,_,A).
generate(N,L,[H|T],S,R):-
S<N,
cand(L,E),
not(cand([H|T],E)),
E=:=H-1,
suma([H|T],S),
generate(N,L,[E,H|T],S,R).
start(N,Rez):-
list(N,L),
cand(L,E1),
cand(L,E2),
E2=:=E1-1,
generate(N,L,[E2,E1],0,Rez).
但不知为何,无论我输入多少数字,结果始终是空列表。
使用clpfd constraints 发现解决方案比你展示的多:
:- use_module(library(clpfd)).
n_list(N, Ls) :-
L #=< N,
L #> 0,
indomain(L),
length(Ls, L),
Ls ins 0..N,
foldl(consecutive, Ls, _, _),
sum(Ls, #=, N),
label(Ls).
consecutive(A, Prev, A) :- A #= Prev + 1.
示例:
?- n_list(10, Ls).
Ls = [10] ;
Ls = [1, 2, 3, 4] ;
Ls = [0, 1, 2, 3, 4] ;
false.
另一个例子:
?- n_list(80, Ls).
Ls = [80] ;
Ls = [14, 15, 16, 17, 18] ;
false.
我把让它变得更快作为你的练习。
这是 的后续。
想要速度吗?像这样使用冗余约束!
n_list(N, Ls) :-
L #=< N,
L #> 0,
L0 #= L-1,
N0 #= (L0*L0+L0)//2,
N #= N0+K*L,
K #>= 0,
indomain(L),
length(Ls, L),
Ls ins 0..N,
foldl(consecutive, Ls, _, _),
sum(Ls, #=, N),
label(Ls).
没有冗余约束的运行时:
?- time((N in 1..100,indomain(N),n_list(N,_),false)).
% 1,048,270,907 inferences, 85.594 CPU in 85.552 seconds (100% CPU, 12247032 Lips)
false.
具有冗余约束的运行时:
?- time((N in 1..100,indomain(N),n_list(N,_),false)).
% 10,312,514 inferences, 0.834 CPU in 0.833 seconds (100% CPU, 12369051 Lips)
false.
我是 Prolog 的新手,我有以下问题:如何将自然数 N 分解为一个列表,其中包含总和等于 N 的连续自然数?
例如:
N=10, R=[1,2,3,4];
N=80, R=[14, 15, 16, 17, 18];
N=99, R=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
R=[7, 8, 9, 10, 11, 12, 13, 14, 15]
R=[14, 15, 16, 17, 18, 19]
R=[32, 33, 34]
R=[49, 50]
编辑: 我尝试在不使用默认方法的情况下构建列表,到目前为止我设法写了这篇文章:
cand([H|_],H).
cand([_|T],E):-
cand(T,E).
suma([],0).
suma([H|T],S):-
suma(T,Temp),
S is Temp+H.
list(0,[]).
list(N,[Nr|R]):-
Nr is N-1,
list(Nr,R).
generate(_,_,A,_,A).
generate(N,L,[H|T],S,R):-
S<N,
cand(L,E),
not(cand([H|T],E)),
E=:=H-1,
suma([H|T],S),
generate(N,L,[E,H|T],S,R).
start(N,Rez):-
list(N,L),
cand(L,E1),
cand(L,E2),
E2=:=E1-1,
generate(N,L,[E2,E1],0,Rez).
但不知为何,无论我输入多少数字,结果始终是空列表。
使用clpfd constraints 发现解决方案比你展示的多:
:- use_module(library(clpfd)).
n_list(N, Ls) :-
L #=< N,
L #> 0,
indomain(L),
length(Ls, L),
Ls ins 0..N,
foldl(consecutive, Ls, _, _),
sum(Ls, #=, N),
label(Ls).
consecutive(A, Prev, A) :- A #= Prev + 1.
示例:
?- n_list(10, Ls). Ls = [10] ; Ls = [1, 2, 3, 4] ; Ls = [0, 1, 2, 3, 4] ; false.
另一个例子:
?- n_list(80, Ls). Ls = [80] ; Ls = [14, 15, 16, 17, 18] ; false.
我把让它变得更快作为你的练习。
这是
n_list(N, Ls) :- L #=< N, L #> 0, L0 #= L-1, N0 #= (L0*L0+L0)//2, N #= N0+K*L, K #>= 0, indomain(L), length(Ls, L), Ls ins 0..N, foldl(consecutive, Ls, _, _), sum(Ls, #=, N), label(Ls).
没有冗余约束的运行时:
?- time((N in 1..100,indomain(N),n_list(N,_),false)). % 1,048,270,907 inferences, 85.594 CPU in 85.552 seconds (100% CPU, 12247032 Lips) false.
具有冗余约束的运行时:
?- time((N in 1..100,indomain(N),n_list(N,_),false)). % 10,312,514 inferences, 0.834 CPU in 0.833 seconds (100% CPU, 12369051 Lips) false.