Бинарное сложение Пролога без сокращений(!)

Я пытаюсь понять, как сложить вместе два двоичных числа, которые представлены в виде списков. Например: addNumbers([1,0,1], [1,1,0,0], X). должен вернуть X = [1,0,0,0,1].

Мы не вслух используем сокращения(!) для решения этой проблемы. Итак, я знаю, что мне нужно реализовать своего рода сумматор. Прямо сейчас я добавляю цифры, реализованные с необходимыми предикатами:

addDigits(A,B,X,Y) :- myXor(A,B,X), myAnd(A,B,Y).

myAnd(A,B,R) :- A == 1, B == 1, R is 1.
myAnd(A,B,R) :- A == 0, B == 0, R is 0.
myAnd(A,B,R) :- A == 1, B == 0, R is 0.
myAnd(A,B,R) :- A == 0, B == 1, R is 0.
myOr(A,B,R) :- A == 0, B == 0, R is 0.
myOr(A,B,R) :- A == 0, B == 1, R is 1.
myOr(A,B,R) :- A == 1, B == 0, R is 1.
myor(A,B,R) :- A == 1, B == 1, R is 1.

Это правильно возвращает X как сумму двух двоичных цифр и Y как перенос. Теперь я знаю, что мне это нужно для моего сумматора. Теперь, чтобы реализовать addDigits, я застрял. В настоящее время это то, что у меня есть, но не работает. ПРИМЕЧАНИЕ. Подсказка была началом LSB, но в настоящее время я этого не делаю.

addNumbers([HA|TA],[HB|TB],X) :- adder(HA,HB,Cin,Sum,Cout,X),
    append(Sum, X, X),
    addNumbers(TA,TB,X).

adder(X,Y,Cin,Sum,Cout) :- addDigits(X,Y,Sum1,Carry1),
    addDigits(Sum1, Cin, Sum, Carry2),
    myOr(Carry1, Carry2, Cout).

Любая помощь/предложения будут оценены.

Ваше здоровье


binary addition prolog
person topched    schedule 19.11.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы на правильном пути. Ваша главная проблема состоит в том, чтобы понять типичную рекурсию Пролога.

Но сначала ваши бинарные функции: они верны, но так проще и читабельнее (вам все равно не хватает этой):

myXor(1,0,1).
myXor(0,1,1).
myXor(1,1,0).
myXor(0,0,0).

В вашем myOr в четвертом регистре опечатка: вы написали его со строчной "о". С этим определением ваш adder действительно работает правильно!

Теперь о рекурсии: начинать действительно нужно с LSB, иначе можно даже не знать, какие биты добавлять, ведь числа не обязательно имеют одинаковую длину. К счастью, вы можете легко сделать это, заключив вызов в reverses:

addNumbers(N1, N2, Sum) :- 
    reverse(N1, N12), 
    reverse(N2, N22),
    addNumbers(N12, N22, 0, [], Sum0),
    reverse(Sum0, Sum).

Это довольно распространенный шаблон в Прологе: addNumbers/3 вызывает addNumbers/5 с дополнительными параметрами, необходимыми для рекурсии. «0» — это начальный перенос, [] — накопитель результата. Вот addNumbers/5 с некоторыми изменениями по сравнению с вашей версией:

addNumbers([HA|TA],[HB|TB],Cin,X0,X) :- 
    adder(HA,HB,Cin,Sum,Cout),
    append(X0, [Sum], X1),
    addNumbers(TA,TB,Cout,X1,X).

Во-первых, обратите внимание, что здесь вам нужно получить Cin в качестве входного параметра! Кроме того, у нас есть X0 в качестве переменной-«аккумулятора», то есть она увеличивается с каждым рекурсивным вызовом. Последний вызов будет иметь результат, поэтому он может попасть в выходную переменную. Для этого вам также понадобятся базовые случаи:

addNumbers([],B,Cin,X0,X) :- % TODO: Respect Cin
    append(X0,B,X).
addNumbers(A,[],Cin,X0,X) :- % TODO: Respect Cin
    append(X0,A,X).

Видите, как результатом добавления является не X1 (еще одна промежуточная переменная), как указано выше, а X? Это потому, что это окончательный результат, и он будет объединен с одним и тем же X на всем протяжении стека вызовов, и таким образом он станет выходом всего вызова addNumbers/5!

Однако я оставил его незавершенным, так что для вас осталась некоторая (небольшая) работа: также базовые случаи должны учитывать Cin...

person firefrorefiddle    schedule 19.11.2012