關于阿克曼函數(akermann）非遞歸算法的一點見解

• 0
• 阿克曼函數的形式
• 分析
• 如何寫代碼
• 解決辦法
• 代碼
• 1

0

這個星期，數據結構與算法的陳老師布置了一道題目，要求用非遞歸的算法計算阿克曼函數。在百度上找了很多個網址，都沒有找到我想要的答案。于是，在我做出來之后，打算與大家分享一下我自己的想法。不足之處，請多多指教！

阿克曼函數的形式

如下圖是我從《數據結構與程序設計》翻譯版描述的阿克曼函數。
看到阿克曼函數的這個形式，毫無疑問第一個想到的肯定是用遞歸的算法。但是如果不用遞歸的算法，事情就變得麻煩起來了。

分析

說到用其它的算法代替遞歸算法，大部分第一個想到的肯定是使用循環，我第一個想到的也是循環，這是正確的。但是這個問題比較特殊，特殊之處就在于它的問題的出現是線性的。也就是說，你想要解決上一個問題，你只需要解決這一個問題；你想要解決這一個問題，你只需要解決下一個問題。注意我這里的用詞：只需要！！！遞歸的實現其實就是一個堆棧出棧的過程。

下面就以計算A(2,1)的例子分析。如下圖。

（注：這個圖上的元素應該從下往上看，像堆棧一樣）
如圖，我們要解決A(2,1)，就得解決A(1,A(2,0))；要解決A(1,A(2,0))，就得解決A(2,0)… 以此類推，直到我們得到一個m=0的元素A(0,1)，A(0,1)解決了之后，它的結果可以一直回到原來要解決的問題A(1,A(2,0))，也即是A(1,3)。往后同樣分析，要解決A(1,3)，就得先解決A(0,A(1,2))；要解決A(0,A(1,2))，就得先解決A(1,2)…直到我們最終推出A(2,1)的結果為止，最終的結果是5。

如何寫代碼

從上面的分析，我們可以發現：
（1）每一個需要計算的元素是一個個向上地堆棧，直到遇到m=0的情況，此時A(0,n)可以計算出一個整數，之后就是出棧的操作。
（2）A(m,A(m1,m2))，這種情況在棧中是比較特殊的情況，當這里的m=0時，棧就能繼續出棧了；但是m≠0的時候，我們還得繼續向上堆棧。

解決辦法

（1）聲明兩個棧s1、s2。
　　 s1存儲m
　　 s2存儲n
（2）遇到A(m,A(m1,m2))這種情況的時候，將n存儲為-1，這是為了后面出棧的算法能夠識別特殊情況，并且做出相應的處理。
（3）聲明m和n，用于動態存儲并操作m值和n值，這是因為在（2）的要求下，n可能在棧s2中存為-1，此時存儲的值是一個待定值。

代碼

#include<iostream> #include<stack> using namespace std; int asker(int m, int n) {stack<int> s1;stack<int> s2;s1.push(m);s2.push(n);while (!s1.empty()){while (m != 0){if (n == 0){m = m - 1;n = 1;s1.push(m);s2.push(n);}else{n = n - 1;s1.push(m - 1);s2.push(-1);}}n = n + 1;while ((!s1.empty())&& (s2.top() != -1)){s1.pop();s2.pop();}if(!s1.empty()){m = s1.top();s2.pop();s2.push(n);}}return n; } void main() {cout << asker(2, 1); }

1

這是我第一次寫博客，有很多不足之處。代碼是趕出來的，所以會有很多地方使用不當，請大家幫我指出錯誤！

總結

以上是生活随笔為你收集整理的关于阿克曼函数(akermann）非递归算法的一点见解 c++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。