logo标签列表

用操作符（+，-，/，*）在Prolog中查找列表中的目标数字

prolog
3
任务是找到是否存在一种从给定列表选出数字和运算符的组合，可以得到目标数字。不允许使用模块。 numbers([3,4,1,2], 7) → true。（因为 4 + 3 = 7） numbers([1,7,7,3], 24) → true。（因为 (7 - 3) * (7 - 1) = 24）
尝试在列表中查找目标数字，但未能找到更进一步的解决方案。
1
你没有指定允许使用的运算符。 - damianodamiano
2个回答
3

在https://professor-fish.blogspot.com/2009/11/countdown-with-prolog.html的基础上构建

solve_countdown(Ns, SumWanted, TsUniq) :-
    findall(T, (
        any_comb(Ns, Sub),
        num_combs(Sub, T),
        SumWanted is T
    ), Ts),
    sort(Ts, TsUniq).

any_comb(_, []).
any_comb([H|T], [E|Comb]) :-
    select(E, [H|T], Lst0),
    any_comb(Lst0, Comb).

num_combs([N], N).
num_combs(As, T) :-
    split_list_in_2(As, As1, As2),
    num_combs(As1, T1),
    num_combs(As2, T2),
    % Break symmetry, since 5+2 is same as 2+5
    (   T1 @=< T2,
        (   T = T1 + T2
        ;   T1 > 1, T = T1 * T2
        )
    ;   T = T1 - T2
    ;   T = T1 / T2
    ),
    R is T,
    integer(R),
    R @> 0.

split_list_in_2([H1, H2|T], [H1|Start], Remainder) :-
    split_list_in_2_(T, H2, Start, Remainder).
    
split_list_in_2_(L, H2, [], [H2|L]).
split_list_in_2_([H|T], H2, [H2|Start], Remainder) :-
    split_list_in_2_(T, H, Start, Remainder).

在SWI-Prolog中的结果：

?- time(solve_countdown([1,7,7,3], 24, Ts)).
% 10,996 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 5236642 Lips)
Ts = [3*(1+7), (7-1)*(7-3)].

select/3 代码 在这里。

2
挤柠檬。我得到了一个稍微快一点的版本。 这个逻辑复制了这篇论文： https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf 但是增加了前向检查：
% solve(+Integer, -Term, +Integer, +List, -List)
solve(1, N, N, P, Q) :- !, select(N, P, Q).
solve(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve2(I, E, A, P, H),
   forward(E, A, F, B, G, N),
   solve(L, F, B, H, Q).

forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B.
forward(E, A, F, B, E-F, N) :- A > N, B is A-N.
forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B, A =\= 1.
forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N, B =\= 1.

% solve2(+Integer, -Term, -Integer, +List, -List)
solve2(1, N, N, P, Q) :- !, select(N, P, Q).
solve2(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve2(I, E, A, P, H),
   solve2(L, F, B, H, Q),
   combine(E, A, F, B, G, N).

combine(E, A, F, B, E+F, N) :- A =< B, N is A+B.
combine(E, A, F, B, E-F, N) :- A > B, N is A-B.
combine(E, A, F, B, E*F, N) :- A =< B, A =\= 1, N is A*B.
combine(E, A, F, B, E/F, N) :- B =\= 1, A mod B =:= 0, N is A div B.

使用 SWI-Prolog 9.1.4 运行的示例：

% time((between(1,6,N), solve(N, E, 999, [1,3,5,10,25,50], _), fail; true)).
% % 2,618,953 inferences, 0.234 CPU in 0.242 seconds (97% CPU, 11174199 Lips)
% true.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接