Ackermann函数详解
Ackermann函数要求如下：
我们需要知道的是这个函数的时间复杂度增长的非常非常快，A（2，3）和A（5，0）应该差了几百个量级。
咱们也不多废话，直接上多种代码解释吧。上对应代码把。
解法1： 常规递归（只适合输入量很小的情况）
这个就是无限递归了，如果输入量是 2 3，这种很容易就出答案，因为很容易算。
但是这个代码只适合不限制时间的情况下进行操作。大家可以尝试用这个代码用A（5,0）来处理，会发现出不了结果，直接程序卡死了。
代码语言：javascript复制#include<iostream>
#include<cmath>
using namespace std;
int A(int i,int j)
{
if(i>0&&j>0){
return A(i-1,A(i,j-1));
}
else if(i==0){
return j 1;
}
else{
return A(i-1,1);
}
}
int main()
{
int a,b;
cin >> a>>b;
int ans = A(a,b);
cout << ans 00000009<<endl;
}解法2：堆栈解法
创建一个数组，当成一个堆栈。也是一种常见解法。
但是这种如果做A（5，0）也是出不了结果，会超出时间。
代码语言：javascript复制#include<iostream>
using namespace std;
int A(int m,int n)
{
int a[100000];
int i=0;
while(1){
if(0==m){
if(0==i){
return n;
}
n ;
m=a[i--];
}
if(0==n){
m--;
n ;
}
if( 0!=m && 0!=n){
a[ i]=m-1;
n--;
}
}
}
int main()
{
int m,n;
cin >> m >> n;
int b=A(m,n);
cout<<b <<endl;;
return 0;
}解法3：优化递归（记忆数组）
直接开数组进行算过的存起来，然后进行优化，相当于剪枝。
但是需要注意二维数组开的时候，一维开小一些，二维开10的6次方就够用。
我最开始开2000x2000的数组，一直出错，因为二维马上就不够了。
大家可以观察这个数组，把记忆数组一维开小一些，就能解决了。
代码语言：javascript复制#include <iostream>
using namespace std;
const int mod = 1000000009;
const int MAXN = 10;
const int MAXN2 = 1000000;
int memo[MAXN][MAXN2];
int A(int i, int j) {
if (i ==0) return (j 1) % mod;
if (j ==0) return A(i-1, 1);
if (memo[i][j] != 0) {
return memo[i][j];
}
int result = A(i-1, A(i, j-1));
memo[i][j] = result;
return result;
}
int main() {
int a, b;
cin >> a >> b;
int ans = A(a, b);
cout << ans << endl;
return 0;
}解法4：数学归纳法（数学公式）
其实我们可以看到，这个用数学归纳法，可以进行数学归纳。
归纳的话，我们只归纳到3的层次，大家感兴趣可以自己往后推。
代码语言：javascript复制#include<iostream>
#include<cmath>//pow函数
using namespace std;
int main(){
int m,n;
cin>>m>>n;
if(m==0) cout<<n 1<<endl;
if(m==1) cout<<n 2<<endl;
if(m==2) cout<<2*n 3<<endl;
if(m==3) cout<<pow(2,n 3)-3<<endl;
}这种就是数学归纳法，但是只限制于输入的m在3以内。
