算术谜题序言

Question

我必须在该列表中的数字之间加上 + 和 - 才能获得提供的数字。例如 12-34 = -22。我是这样做的：

arit(L, Ls, S) :- arit(L, Ls, S, 0).
arit([], [], R, R).

arit([E|L], Ls, R, S) :- 
    S1 is S + E, 
    Ls = [+|[E|Ns]], 
    arit(L, Ns, R, S1).

arit([E|L], Ls, R, S) :- 
    S1 is S - E, 
    Ls = [-|[E|Ns]], 
    arit(L, Ns, R, S1).


arit([E|L], Ls, R, S) :- 
    S1 is (S*10 + E), 
    Ls=[E|Ns], 
    arit(L, Ns, R, S1).

有效，但答案重复（如 1+2+3 和 +1+2+3）。也许有人知道如何优化它？编辑。此代码根本不起作用，请查看答案。

Answer 1

实际上，您的代码无法正常工作。要确认这一事实，请尝试以下查询：

?- put_arit2([1,2,3,4], L, 22).
false.

很容易检查，[-,1,2,+,3,4] 是正确答案。

因此，我建议采用以下解决方案（在 SWI-Prolog 中）：

定义一个可以生成所有可能列表（带运算符）的谓词。
将每一个可能的列表转化为对应的算术表达式，并检查其是否具有所需的值。

% putop(+List, -ListWithOperators)

putop([], []).
putop(L, [O|D]) :-
    member(O, [+,-]),
    append([X|A], B, L), % split list into two sublists, such that first one is not empty 
    append([X|A], C, D), % append first sublist with the sublist that will be obtained recursively
    putop(B, C).

% putop(+List, -ListWithOperators, +DesiredValue)

putop(L, E, V) :-
     putop(L, E),                   % obtain list with operators
     atomic_list_concat(E, A),      % transform list into an atom
     read_term_from_atom(A, T, []), % transfom atom into a term
     V is T.                        % check whether term has the desired value

示例：

?- putop([1,2,3,4], L, 22).
L = [-, 1, 2, +, 3, 4] ;
false.

?- putop([1,2,3,4,5,6,7,8,9], L, 4).
L = [+, 1, +, 2, -, 3, 4, +, 5, +, 6, +, 7, +, 8, +, 9] ;
L = [+, 1, 2, +, 3, -, 4, +, 5, -, 6, -, 7, -, 8, +, 9] ;
L = [+, 1, 2, +, 3, -, 4, -, 5, +, 6, -, 7, +, 8, -, 9] ;
L = [+, 1, 2, -, 3, +, 4, +, 5, -, 6, -, 7, +, 8, -, 9] ;
L = [+, 1, 2, -, 3, +, 4, -, 5, +, 6, +, 7, -, 8, -, 9] ;
L = [+, 1, 2, -, 3, +, 4, 5, -, 6, 7, +, 8, +, 9] ;
L = [+, 1, 2, -, 3, -, 4, -, 5, -, 6, -, 7, +, 8, +, 9] ;
L = [+, 1, 2, -, 3, 4, -, 5, 6, -, 7, +, 8, 9] ;
L = [-, 1, +, 2, +, 3, 4, +, 5, 6, -, 7, 8, -, 9] ;
L = [-, 1, +, 2, 3, +, 4, 5, +, 6, -, 7, 8, +, 9] ;
L = [-, 1, -, 2, +, 3, 4, -, 5, +, 6, 7, -, 8, 9] ;
L = [-, 1, -, 2, 3, -, 4, +, 5, 6, -, 7, -, 8, -, 9] ;
L = [-, 1, 2, +, 3, +, 4, +, 5, -, 6, -, 7, +, 8, +, 9] ;
L = [-, 1, 2, +, 3, +, 4, -, 5, +, 6, +, 7, -, 8, +, 9] ;
L = [-, 1, 2, +, 3, -, 4, +, 5, +, 6, +, 7, +, 8, -, 9] ;
L = [-, 1, 2, +, 3, -, 4, -, 5, -, 6, 7, +, 8, 9] ;
L = [-, 1, 2, -, 3, -, 4, +, 5, -, 6, +, 7, +, 8, +, 9] ;
L = [-, 1, 2, -, 3, 4, +, 5, 6, -, 7, -, 8, +, 9] ;
false.

[编辑] 如果您不想使用内置谓词 atomic_list_concat/2 和 read_term_from_atom/3，那么您需要创建自己的谓词用于评估数字和运算符列表的谓词。

putop(L, E, V) :-
     putop(L, E),
     evaluate(E, V).

putop([], []).
putop(L, [O|D]) :-
    member(O, [+,-]),
    append([X|A], B, L),
    append([X|A], C, D),
    putop(B, C).

evaluate(List, Value) :-
    evaluate(List, 0, Value).

evaluate([], Value, Value).
evaluate([Operator|List], Accumulator, Value) :-
    operand(List, 0, Operand, Rest),
    add(Operator, Accumulator, Operand, NewAccumulator),
    evaluate(Rest, NewAccumulator, Value).

operand([], Accumulator, Accumulator, []).
operand([+|Rest], Accumulator, Accumulator, [+|Rest]).
operand([-|Rest], Accumulator, Accumulator, [-|Rest]).
operand([Digit|Rest], Accumulator, Value, List) :-
    Digit \= +,
    Digit \= -,
    NewAccumulator is 10*Accumulator + Digit,
    operand(Rest, NewAccumulator, Value, List).

add(+, Accumulator, Operand, NewAccumulator) :-
    NewAccumulator is Accumulator + Operand.
add(-, Accumulator, Operand, NewAccumulator) :-
    NewAccumulator is Accumulator - Operand.

算术谜题序言

Arithmetic puzzle prolog

prolog