Ackermann函數和遞歸

我試圖用Java編寫遞歸Ackermann函數。但是我認爲我在某個地方出錯了！任何人都可以看看，檢查並指出我的方向是否正確，以糾正我的代碼？謝謝！Ackermann函數和遞歸

Ackermann

我的代碼的問題是，在我寫的，我想，如果有什麼n ==可0和m == 0，有沒有爲這個區域？這會落在if（m == 0）之下還是它需要它自己的if語句？

我的以下解決方案是否正確？如果我以不同的順序給出相同的數字，它會給出不同的結果，我不確定這是否意味着這種情況。

public static int ackermann(int m, int n) { 

     if (m == 0) { 

      return n + 1; 

     } else if ((m > 0) && (n == 0)) { 

      return ackermann(m-1, n); 

     } else if ((m > 0) && (n > 0)) { 

      return ackermann(m-1, ackermann(m,n-1)); 

     } else { 

      return 0; 

     } 

    }

我想到了一些，我想我更加錯了。如果你不知道我做了什麼，我將每個if語句都給出了相反的結果，因爲我認爲如果以不同的方式給出m和n值，以下代碼將起作用。這顯然不能，但有人可以試圖解釋我出錯的地方嗎？

public static int ackermann(int m, int n) { 

     if (m == 0) { 

      return n + 1; 

     } else if (n == 0) { 

      return m + 1; 

     } else if ((m > 0) && (n == 0)) { 

      return ackermann(m-1, n); 

     } else if ((n > 0) && (m == 0)) { 

      return ackermann(n-1, m); 

     } else if ((m > 0) && (n > 0)) { 

      return ackermann(m-1, ackermann(m,n-1)); 

     } else if ((n > 0) && (m > 0)) { 

      return ackermann(n-1, ackermann(n, m-1)); 

     } else { 

      return 0; 

     } 

    }

來源

2012-01-01 mino

你最後的'else'應該拋出'InvalidArgumentException'。 – SLaks 2012-01-01 16:18:18

我認爲你的第一個版本幾乎是正確的。我稍微修改：

public static int ackermann(int m, int n) { 
    if (m < 0 || n < 0) { 
     throw new IllegalArgumentException("Non-negative args only!"); 
    } 

    if (m == 0) { 
     return n + 1; 
    } else if (n == 0) { 
     return ackermann(m-1, 1); // Corrected! 
    } else { 
     // perforce (m > 0) && (n > 0) 
     return ackermann(m-1, ackermann(m,n-1)); 
    } 
}

的m == 0 && n == 0情況下，應包括在m == 0情況。

編輯：請注意Ackermann function只爲非負參數定義。特別是，ackermann(0, -1)應該拋出異常。因此，您不能只將最後的else子句轉換爲throw。

來源

2012-01-01 16:21:16

您的第一個'else'可以讀取其他的if（n == 0）{'因爲'm'必須是'> 0'' else else。 – OldCurmudgeon 2012-01-01 18:54:42

@保羅 - 好。我修改了代碼。 – 2012-01-04 18:18:19

的 '如果m = 0' 規則適用對於n的所有值，因此A（0,0）爲1

的 '其他' 子句只能用於如果m和n分別爲在進入功能時都是負面的，這可以被診斷爲例外。事實上，如果m或n是負數，你應該診斷錯誤。或者，由於A（m，n）否則不會返回零，因此可以將0表示爲錯誤信號。

請注意，評估A（m，n）所需的堆棧深度與答案相同 - 並且A（m，n）非常快地變得非常大。不要費神去嘗試評估A（4，4）;你的電腦沒有足夠的內存。

來源

2012-01-01 16:18:32

實際上，阿克曼函數僅限於非負參數。（它沒有被定義，例如，對於m == 0，n == -1。） – 2012-01-01 16:30:11

同意：但Java代碼採用帶符號整數，所以在被調用時可能會被濫用 - 也許代碼應該診斷。 – 2012-01-01 17:29:56

我的觀點很簡單，就是當代碼按照（0，-1）調用時，會高興地返回0。修改'else'子句並不足以解決這個問題。 – 2012-01-01 17:39:19

這部分是錯誤的：

} else if ((m > 0) && (n == 0)) { 
     return ackermann(m-1, n);

這應該是A（米 - 1，1）

來源

2012-01-01 16:19:08 SLaks

第一片段是行，除了它返回ackermann(m-1, n)代替ackermann(m-1, 1)在第二種情況下。默認情況下，應該永遠不會發生，應該拋出一個IllegalStateException以防其實際發生。

來源

2012-01-01 16:20:51

有趣的是，所有的答案，你的問題在第一個版本中指出你的錯誤，但沒有任何關於第二個版本的大錯誤說

else if (n == 0) { 
     return m + 1; 
    }

其中，爲正整數，與

條件等同

else if ((m > 0) && (n == 0)) { 
     return ackermann(m-1, n); 
    }

所以你的函數將返回m + 1個但不阿克曼（M-1，1），其應爲第二種情況（（M> 0）& &（N == 0））。

來源

2017-12-16 01:37:33

Ackermann函數和遞歸

回答

相關問題