遞歸乘法

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加到結果中。