Ackerman函数的栈实现

一、Ackerman函数：

ackerman函数的定义如下：

二、Ackerman函数的递归实现：

利用递归来实现ackerman函数是比较简单的：

1 /*Sample Input: 
 2   0 1
 3   1 1
 4   
 5   Sample Output:
 6   2
 7   3
 8 */
 9 
10 #include<bits/stdc++.h>
11 using namespace std;
12 
13 int akm(int m, int n){
14     if(m == 0)return n+1;
15     if(m != 0 && n == 0)return akm(m-1, 1);
16     if(m != 0 && n != 0)return akm(m-1, akm(m, n-1));
17 }
18 
19 int main(){
20     int m, n;
21     while(cin >> m >> n){
22         cout << akm(m ,n) << endl;
23     }
24 }

三、利用栈来实现Ackerman函数：

我们可以使用栈来模拟递归函数的过程，下列代码中，使用栈st来保存每个递归函数的参数m，tmp用来保存每个递归函数的返回值：

1 /*Sample Input: 
 2   0 1
 3   1 1
 4   
 5   Sample Output:
 6   2
 7   3
 8 */
 9 
10 #include<bits/stdc++.h>
11 using namespace std;
12 
13 int akm(int m, int n){
14     stack<int>st;
15     int tmp;
16     while(true){
17         while(m > 0){
18             if(n == 0){
19                 m--;
20                 n = 1;
21             }
22             else{
23                 st.push(m - 1);
24                 n--;
25             }
26         }
27         tmp = n + 1;
28         if(st.empty())break;
29         else{
30             m = st.top();
31             n = tmp;
32         }
33         st.pop();
34     }
35     
36     return tmp;
37 }
38 
39 int main(){
40     int m, n;
41     while(cin >> m >> n){
42         cout << akm(m ,n) << endl;
43     }
44 }

//End
原文链接: https://www.cnblogs.com/Vincent-Bryan/p/5976277.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍