0

我试图弄清楚如何将两个表示为列表的二进制数相加。例如：addNumbers([1,0,1], [1,1,0,0], X)。应该返回 X = [1,0,0,0,1]。

我们不大声使用cuts(!) 来解决这个问题。所以我知道我必须实现一个加法器。现在我已经添加了用它需要的谓词实现的数字：

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 作为 2 个二进制数字的总和，并将 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).

任何帮助/建议将不胜感激。

干杯

4

1 回答 1

2

你在一个很好的轨道上。您的主要问题是了解典型的 Prolog 递归。

但首先，您的二进制函数：它们是正确的，但是像这样更容易且更具可读性（无论如何您都错过了这个）：

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

在myOr第四种情况下，您的拼写错误：您用小写“o”拼写了它。有了这个定义，你adder确实可以正常工作！

现在，关于递归：你真的需要从 LSB 开始，否则你甚至不知道要添加哪些位，因为数字不一定是相同的长度。幸运的是，您可以通过将调用包装在reverses 中轻松做到这一点：

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

这是 Prolog 中相当常见的模式： 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).

看看append的结果怎么不是上面的X1（另一个中间变量），而是X？这是因为它是最终的结果，它会在调用栈中一直与同一个 X 统一，这样它就变成了整个 addNumbers/5 调用的输出！

不过，我没有完成它，因此您还剩下一些（少量）工作：此外，基本情况还需要考虑 Cin ......

于 2012-11-19T07:35:12.247 回答