2012-01-01 52 views
4

我試圖用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; 

     } 

    } 
+0

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

回答

5

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

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

+0

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

+0

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

1

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

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

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

+0

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

+0

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

+0

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

5

這部分是錯誤的:

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

這應該是A(米 - 1,1)

0

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

2

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

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))。