1

我不明白为什么这个乘法的递归定义是有效的。
我得到了添加部分，但在这种情况下“A”的值如何。代码如下：

add(0,X,X).
add(s(X),Y,Z):-add(X,s(Y),Z).

mult(0,X,0).
mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z).
4

2 回答 2

5

要理解谓词，请尝试“阅读”它们所说的内容。

首先阅读add/3定义...

add(0,X,X).

添加0到X结果中X。

add(s(X),Y,Z):-add(X,s(Y),Z).

添加s(X)（的后继X）到Y结果Z 如果添加X到s(Y)（的后继Y）导致Z。

如果我们将后继者视为加 1，那么这就是说(X + 1) + Y结果为ZifX + (Y + 1)结果为Z。这在逻辑上是显而易见的，但似乎无处可去。但是，我们会注意到这个逻辑与基本情况密切相关，add(0,X,X)因为递归情况将通过每次迭代删除单个连续来减少0第一个参数，直到第一个参数变为.

现在让我们尝试mult/3...

mult(0,X,0).

乘以结果0_X0

这似乎很明显。

mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z).

X如果乘以Y结果为 ，Z 则乘以Xby的后继Y结果为A，并Y与A结果相加Z。

如果您将后继者视为加 1，那么这就是说if (X+1)*Yis和is 。这是有道理的，因为is which would be 。ZX*YAA+YZ(X+1)*Y(X*Y)+YA+Y

于 2017-04-09T01:48:35.230 回答
3

在这种情况下，A是 的值(X-1) * Y。您使用规则递归地找到此值，mult然后将其添加到Y规则add中以获得最终结果。它将乘法写为X * Y = (X - 1) * Y + Y

真正最终发生的是它调用add X时间，并且每一次它都会添加Y到最终结果（从零开始）。这是利用乘法作为重复加法。这是手动跟踪：

  1. mult(3, 2, Z)
    初次通话

  2. mult(2, 2, A_1), add(2, A_1, Z)
    减去 1 帧X

  3. mult(1, 2, A_2), add(2, A_2, A_1)
    再次。

  4. mult(0, 2, A_3), add(2, A_3, A_2)
    最后一次

  5. mult(0, 2, A_3)
    只有一种可能性，因为零无法匹配s(x)。A_3设置为 0。

  6. mult(0, 2, 0), add(2, 0, A_2)
    第 4 步，但A_3被替换。我们现在知道A_2必须是 2。

  7. mult(1, 2, 2), add(2, 2, A_1)
    第 3 步，但A_2被替换。我们现在知道A_1必须是 4。

  8. mult(2, 2, 4), add(2, 4, Z)
    第 2 步，但A_1被替换。我们现在知道Z必须是 6，最后的结果。

对于第 2 步到第 4 步，您正在向下计数，以找出需要重复加法操作的次数。第 5 步是基本情况，最终结果从零开始。在步骤 6 到 8 中执行加法。这给出了结果Z = 6 = 2 + 2 + 2

于 2017-04-09T04:44:12.400 回答