阿克曼函數(shù)Ackerman

同樣是算法課后小作業(yè)，之前還沒見過這個函數(shù)（是我孤陋寡聞了）

阿克曼函數(shù)（Ackermann）是非原始遞歸函數(shù)的例子。它需要兩個自然數(shù)作為輸入值，輸出一個自然數(shù)。它的輸出值增長速度非常快，僅是對于(4,3)的輸出已大得不能準確計算。

遞歸公式

上代碼，這是遞歸方法，acm用這個方法的話通常會超時，因為一般m=3這個數(shù)就很大要算很多次的，所以一般m都取0~3

public static long ackerman(long m, long n) {if (m < 0 || n < 0)return -1;else if (m == 0)return n + 1;else if (m > 0 && n == 0)return ackerman(m - 1, 1);else //m>0 and n>0return ackerman(m - 1, ackerman(m, n - 1));}

m只能取0、1、2、3，這樣就可以把m的所有情況列出來了
推導m=1時要結合m=0時推
推導m=2時用m=1時 同理可得到
m=0 n+1;
m=1 n+2;
m=2 2n+3
m=3 dp[3][i]=2dp[3][i-1]+3;

public static long ackerman(long m, long n) {if (n == 0)return ackerman(m - 1, 1);else if (m == 0)return n + 2;else if (m == 1)return n + 2;else if (m == 2)return 2 * n + 3;else if (m == 3)return ackerman(m, n - 1) * 2 + 3;}

有幫助請點個贊謝謝！！

總結

以上是生活随笔為你收集整理的阿克曼函数Ackerman的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。