Пролог - Бинарное сложение?

Мне нужно написать предикат Prolog, который вычисляет сумму 2 двоичных чисел, представленных в списке. Списки уже перевернуты, например ([0,1] base 2) = (2 base 10).

Он должен работать с режимом binary_plus (+, +, -), например

?- binary_plus([1,1],[1],X).
X = [0,0,1].

и с режимом binary_plus (-, -, +), например

?- binary_plus(X,X,[0,1]).
X = [1].

Мне запрещено использовать знак сокращения, findall, отрицание или if-then-else.

Вот мой код:

is_binary([]).
is_binary([X]):- X is 1.
is_binary([X|Xs]):-
    append(_,[1],Xs),
    member(X,[0,1]),    
    is_binary(Xs).

binary_plus([],X,X):-
    is_binary(X).
binary_plus(X,[],X):- 
    is_binary(X).

binary_plus([0|Xs],[Y|Ys],[Y|Zs]):-
    binary_plus(Xs,Ys,Zs).
binary_plus([1|Xs],[0|Ys],[1|Zs]):-
    binary_plus(Xs,Ys,Zs).
binary_plus([1|Xs],[1|Ys],[0|Zs]):-
    binary_plus(Xs,[1],Ws),
    binary_plus(Ws,Ys,Zs).

Я не знаю, в чем я ошибаюсь, потому что есть некоторые странные проблемы, которые я не могу решить, поэтому, если бы кто-то мог мне помочь, я был бы признателен. Спасибо.


binary addition prolog
person DaniLiat    schedule 31.03.2015    source источник
comment
is_binary([X]):- X is 1. должно быть is_binary([X]) :- X = 1. или лучше, is_binary([1]).. Термин X is 1 - это присвоение выражения. Несмотря на то, что это работает, =/2 предназначен для объединения, а это то, что вам нужно.   -  person lurker    schedule 01.04.2015
comment
+1 за очень разумное требование не использовать !/0, if-then-else и т. Д.! Эти конструкции обычно делают ваши программы немонотонными и менее общими.   -  person mat    schedule 01.04.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вот мой взгляд на двоичное сложение без чего-либо. Я понимаю, что вы не должны использовать clpfd:

binary_plus(A,B,C) :- binary_plus_0(A,B,C).

binary_plus_0([],    [],    []).
binary_plus_0([],    [B|Bs],[B|Bs]).
binary_plus_0([A|As],[],    [A|As]).
binary_plus_0([A|As],[B|Bs],[C|Cs]) :- binary_plus_0(A,B,C,As,Bs,Cs).

binary_plus_0(0,0,0,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs).
binary_plus_0(0,1,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs).
binary_plus_0(1,0,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs).
binary_plus_0(1,1,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs).

binary_plus_1([],    [],    [1]).
binary_plus_1([],    [B|Bs],Cs)     :- binary_plus_0([1],[B|Bs],Cs).
binary_plus_1([A|As],[],    Cs)     :- binary_plus_0([A|As],[1],Cs).
binary_plus_1([A|As],[B|Bs],[C|Cs]) :- binary_plus_1(A,B,C,As,Bs,Cs).

binary_plus_1(0,0,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs).
binary_plus_1(0,1,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs).
binary_plus_1(1,0,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs).
binary_plus_1(1,1,1,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs).
person repeat    schedule 01.04.2015
comment
В SWI-Prolog остается точка выбора:? - binary_plus ([0,1,1], [0,0,1], X). Х = [0, 1, 0, 1]; ложный. :-( :-( - person Mostowski Collapse; 12.04.2019
comment
В моей системе Prolog запрос режима (+, +, -) не оставляет точки выбора. Но запрос (+, -, +) дает некоторые ненормализованные результаты:? - binary_plus ([0,1,1], X, [0,1,0,1]). X = [0,0,1]; X = [0,0,1,0]. Может это можно исправить? - person Mostowski Collapse; 12.04.2019

arrow_upward
3
arrow_downward

При описании списков всегда используйте нотацию DCG. Например, в вашем случае подумайте о том, чтобы написать это как:

:- use_module(library(clpfd)).

binary_addition(Xs, Ys, As) :-
        phrase(binary_addition_(Xs, Ys, 0), As).

binary_addition_([], [], 0)     --> [].
binary_addition_([], [], 1)     --> [1].
binary_addition_([X|Xs], [], C) --> binary_addition_([X|Xs], [C], 0).
binary_addition_([], [Y|Ys], C) --> binary_addition_([C], [Y|Ys], 0).
binary_addition_([X|Xs], [Y|Ys], C0) -->
        { [X,Y] ins 0..1,
          Sum #= X + Y + C0 },
        sum_carry(Sum, C),
        binary_addition_(Xs, Ys, C).

sum_carry(0, 0) --> [0].
sum_carry(1, 0) --> [1].
sum_carry(2, 1) --> [0].

Примеры запросов и их решения:

?- binary_addition([1,0],[0,1,1], Sum).
Sum = [1, 1, 1] .

?- binary_addition([1,1],[1,0,1], Sum).
Sum = [0, 0, 0, 1] .

?- binary_addition([0,1],[1,1], Sum).
Sum = [1, 0, 1] .

Обратите внимание, что это также работает в другом направлении:

?- binary_addition(Xs, Ys, [1,1]).
Xs = [1, 1],
Ys = [] ;
Xs = [],
Ys = [1, 1] ;
Xs = [_G2510, 1],
Ys = [_G2522],
_G2510 in 0..1,
_G2510+_G2522#=1,
_G2522 in 0..1 ;
etc.

Вы можете просто добавить reverse/2 цель к binary_addition/3, если хотите обратный список.

person mat    schedule 31.03.2015
comment
Большое спасибо за быстрый ответ !! но я только начал работать с прологом, и мне не разрешено использовать такую ​​технику. Я отредактировал свой пост. - person DaniLiat; 01.04.2015
comment
@DaniLiat, решение мата не содержит никаких конструкций, о которых ваши вопросы говорят, что вам не разрешено использовать. - person lurker; 01.04.2015