此文記錄阿克曼函數(shù)的遞歸和非遞歸的實(shí)現(xiàn)，以及我對(duì)阿卡曼函數(shù)的認(rèn)識(shí)。

阿克曼函數(shù)定義

Ackermann(m,n)函數(shù)定義如下：
Ackermann(0,n) = n+1;
Ackermann(m,0) = Ackermann(m-1,1);
Ackermann(m,n) = Ackermann(m-1,Ackermann(m,n-1)),m>0,n>0。

遞歸實(shí)現(xiàn)

思路：遞歸實(shí)現(xiàn)就很簡(jiǎn)單了，因?yàn)榻o出了表達(dá)式，確定邊界m==0后，直接往上套。
代碼：

public static long solve_rec(long m,long n){if(m == 0){return n+1;}else if(m > 0 && n == 0){return solve_rec(m-1,1);}else{return solve_rec(m-1,solve_rec(m,n-1));}}

非遞歸實(shí)現(xiàn)

思路：用棧來(lái)模擬遞歸實(shí)現(xiàn)阿克曼函數(shù)求解。先往棧中放入需要求解的ack(m,n)，判斷m,n的狀態(tài)來(lái)進(jìn)行pop和push。說(shuō)的很模糊，詳情見代碼。(思路來(lái)自該博客:https://blog.csdn.net/xiaofei_it/article/details/51524754)
舉例：以計(jì)算Ackermann(2,1)為例，結(jié)合代碼食用更加，ack為一個(gè)類，見后面詳細(xì)代碼。(關(guān)于圖中的res可以沒(méi)有描述清楚，以棧頂?shù)膔es為每次操作的結(jié)果)

代碼：

//思路：使用棧來(lái)模擬遞歸函數(shù)public static long solve(long m,long n){Stack<Ack> stack = new Stack<>();stack.push(new Ack(m,n)); //放入要求解的ack//res用來(lái)記錄ack(0,n)的值//如果res大于0，則說(shuō)明當(dāng)前的函數(shù)層層調(diào)用(push)已經(jīng)到底了，開始pop了。long res = -1;while(!stack.empty()){Ack ack = stack.peek(); //對(duì)棧頂?shù)腶ck進(jìn)行分析if(ack.m == 0){ //m為0,則求解出ack(0,n)的結(jié)果賦給res，并移出stackres = ack.n+1;stack.pop();}else if(ack.n == 0 && ack.m > 0){if(res < 0) {stack.push(new Ack(ack.m-1,1)); //res小于0，Ackermann(m,0) = Ackermann(m-1,1);}else {stack.pop(); //res大于0，則說(shuō)明已經(jīng)計(jì)算過(guò)了，可以pop}}else{if(ack.data < 0){ //還沒(méi)有賦值，只有維if(res < 0){stack.push(new Ack(ack.m,ack.n-1)); //計(jì)算Ackermann(m,n)所需要的Ackermann(m,n-1)}else {ack.data = res; //設(shè)置data是為了判斷是否被計(jì)算res = -1; //重置為1stack.push(new Ack(ack.m-1,ack.data));//Ackermann(m,n) = Ackermann(m-1,Ackermann(m,n-1))，這里的Ackermann(m,n-1)為data}}else{stack.pop(); //已經(jīng)計(jì)算出來(lái)的ack值被用到了，所以就pop出來(lái)}}}return res;}

詳細(xì)代碼

import java.util.Stack;public class Ackermann{public static void main(String[] args) {System.out.println(solve(2,1));System.out.println(solve_rec(2,1));}//思路：遞歸方法public static long solve_rec(long m,long n){if(m == 0){return n+1;}else if(m > 0 && n == 0){return solve_rec(m-1,1);}else{return solve_rec(m-1,solve_rec(m,n-1));}}//思路：使用棧來(lái)模擬遞歸函數(shù)。有點(diǎn)難理解public static long solve(long m,long n){Stack<Ack> stack = new Stack<>();stack.push(new Ack(m,n)); //放入要求解的ack//res用來(lái)記錄ack(0,n)的值//如果res大于0，則說(shuō)明當(dāng)前的函數(shù)層層調(diào)用(push)已經(jīng)到底了，開始pop了。long res = -1;while(!stack.empty()){Ack ack = stack.peek(); //對(duì)棧頂?shù)腶ck進(jìn)行分析if(ack.m == 0){ //m為0,則求解出ack(0,n)的結(jié)果賦給res，并移出stackres = ack.n+1;stack.pop();}else if(ack.n == 0 && ack.m > 0){if(res < 0) {stack.push(new Ack(ack.m-1,1)); //res小于0，Ackermann(m,0) = Ackermann(m-1,1);}else {stack.pop(); //res大于0，則說(shuō)明已經(jīng)計(jì)算過(guò)了，可以pop}}else{if(ack.data < 0){ //還沒(méi)有賦值，只有維if(res < 0){stack.push(new Ack(ack.m,ack.n-1)); //計(jì)算Ackermann(m,n)所需要的Ackermann(m,n-1)}else {ack.data = res; //設(shè)置data是為了判斷是否被計(jì)算res = -1; //重置為1stack.push(new Ack(ack.m-1,ack.data));//Ackermann(m,n) = Ackermann(m-1,Ackermann(m,n-1))，這里的Ackermann(m,n-1)為data}}else{stack.pop(); //已經(jīng)計(jì)算出來(lái)的ack值被用到了，所以就pop出來(lái)}}}return res;}}class Ack{public long m;public long n;public long data;public Ack(long m, long n) {this.m = m;this.n = n;this.data = -1;} }

扯淡

做這道算法題時(shí)，題目很簡(jiǎn)陋(就一個(gè)ack函數(shù)，且沒(méi)有給出范圍！！！)，并不知道這是阿克曼函數(shù)，以前也沒(méi)有聽聞過(guò)(比較孤陋寡聞。。。)。有趣的就是，當(dāng)我寫好這個(gè)遞歸代碼時(shí)，我隨便用了(5,3)作為例子來(lái)跑一下。等了一下說(shuō)是棧溢出，我就感覺(jué)可能是代碼哪個(gè)地方寫錯(cuò)了。我就測(cè)試了一下(2,1)和(2,5)兩個(gè)例子發(fā)現(xiàn)沒(méi)有問(wèn)題。然后我就隨便在一個(gè)地方加上了一個(gè)print，發(fā)現(xiàn)一直在循環(huán)，這就讓我懷疑是不是代碼寫錯(cuò)了(因?yàn)槲也皇莗rint中間的結(jié)果)，我又檢查了一遍邏輯發(fā)現(xiàn)沒(méi)有錯(cuò)誤啊。
然后我就百度了一下，才發(fā)現(xiàn)這是阿克曼函數(shù)，百度百科給出的一句話“阿克曼函數(shù)它的輸出值增長(zhǎng)速度非常快，僅是對(duì)于(4,3)的輸出已大得不能準(zhǔn)確計(jì)算。”當(dāng)時(shí)我就震驚了(內(nèi)心os:啥叫大的不能計(jì)算。我也沒(méi)看出它有這么大)，然后看到關(guān)于阿卡曼函數(shù)的科普，給我的感覺(jué)就是，真tm大。大概有這么大：
Ackermann( 0 , n ) = n + 1
Ackermann ( 1 , n ) = n + 2
Ackermann ( 2 , n ) = 2n + 3
Ackermann ( 3 , n ) = 2^(3+n) - 3
Ackermann ( 4 , 0 ) = 2^4 - 3
Ackermann ( 4 , 1 ) = 2 ^ (2 ^ 4) - 3 = 2^16 -3
Ackermann ( 4 , 2 ) = 2^ (2^ (2^ 4)) - 3 = 2^65536 - 3
…
要知道java中的long類型最大值也就2^64-1。
我不禁回想起斐波拉契數(shù)列的第5000項(xiàng)也不過(guò)1000多位數(shù)(計(jì)算Fibonacci的第5000項(xiàng))，而Ackermann(4,2)就有19729位數(shù)。兩者完全不是一個(gè)數(shù)量級(jí)的。我還企圖計(jì)算Ackermann(5,3)，算它幾個(gè)世紀(jì)未必算出來(lái)。還是要多讀書多看報(bào)才能避免自己的無(wú)知。?_?

總結(jié)

以上是生活随笔為你收集整理的阿克曼函数实现（Java代码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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