递归乘法

Question

我跟着这个http://www.cs.berkeley.edu/~vazirani/algorithms/chap1.pdf（页面底部24）。在这本书中，作者描述了Al Khwarizmi乘法算法。这里是我的实施

static int RecMultiply(int x, int y) 
{ 
    if (y == 0) 
     return 0; 
    int z = RecMultiply(x, y/2); 
    if (y % 2 == 0) 
     return 2 * z; 
    else 
     return x + 2 * z; 
} 

我已经通过代码几次，我只是没有grokking它。为什么底部其他部分将x添加到2 * z？在我看来，z既被用作运行总数，也被用作本书算法中的“右列”数字。有人可以打破这个代码并解释它吗？

Answer 1

由于乘法是简单的重复加法，如果y是成对，则可以将它除以2，然后将x乘以2。 （所以，2 * 2 = 2 + 2.2 * 3 = 2 + 2 + 2,2 * 4 = 2 + 2 + 2 + 2 ....）
如果y是奇数，则可以减1得到一对y，你需要添加一个x（基本上是1 * y）。

这里有一个细目：

RecMultiply(5,5) : 
+- z = RecMultiply(5,2) 
| return 5 + 2 * z (=20 +5 =25) 
| 
| 
+-- RecMultiply(5,2) : 
    +- z = RecMultiply(5,1) 
    | return 2 * z (=10) 
    | 
    +-- RecMultiply(5,1) : 
     +- z = RecMultiply(5,0) 
     | return 5 + 0 
     | 
     +---RecMultiply(5,0) : 
      return 0 

RecMultiply(5,4) : 
+- z = RecMultiply(5,2) 
| return 2 * z (=) 
| 
+-- RecMultiply(5,2) : 
     +- z = RecMultiply(5,1) 
     | return 2 * z (=10) 
     | 
     +-- RecMultiply(5,1) : 
      +- z = RecMultiply(5,0) 
      | return 5 + 0 
      | 
      +---RecMultiply(5,0) : 
       return 0 

所以，基本上，递归位后（即通吃对乘法护理），你可能需要添加另一个y，其在上述第一种情况，是第一次通话为5）。

请注意y=1的特殊情况，意思是x*1，在我们的例子中显然是5。同样的逻辑适用。

你可能想看看它这个样子，如果它可以帮助：

static int RecMultiply(int x, int y) 
{ 

    switch (y) 
    { 
     case 0: 
      return 0; 
      break; 

     case 1: 
      return x; 
      break; 

     default: 
      return (y%2 ==0) ? RecMultiply(x, y/2) 
          : x + RecMultiply(x, y/2); 
      break; 
    } 
} 

我认为这表示在更容易理解的方式+1（或奇数的情况下）。

Answer 2

这很简单。

Z通过乘以x和y的一半来计算。

如果y为偶数的奇偶校验的（如果部分）返回2 * Z = 2 * X * Y/2 = X * Y（其是原始请求）

如果y为奇数奇偶校验的（否则部分）返回2 * z + x。为什么我们添加x？那是因为y/2对于偶数和跟随奇数是相同的。所以Z会是一样的。但是，如果我们检测这部分是否奇数或偶数，并且在奇数的情况下我们再将x加到结果中。