Ackermann函数
我们最常用的也是最直接的方法就是递归，这个方法在上C语言课的时候就用过了，不过递归的解决能力显然是很低效的，由于Ackermann函数是双递归方式，用while循环来转化也不大可能。第二种方法就是用栈来模拟递归。方法如下：
#include<stdio.h>
long stack[1000000];
int ackermann(int m, int n);
int main()
{
int m, n;
while(scanf("%d%d", &m, &n) != EOF)
{
printf("%d", ackermann(m, n));
}
return 0;
}
int ackermann(int m, int n)
{
int top = 1;
stack[0] = m;
stack[1] = n;
while(top)
{
n = stack[top--];
m = stack[top];
if ( m == 0 )
{
stack[top] = n+1;
}
else if( m > 0 && n == 0)
{
stack[top++] = m - 1;
stack[top] = 1;
}
else if( m > 0 && n > 0)
{
stack[top++] = m - 1;
stack[top++] = m;
stack[top] = n-1;
}
}
return stack[0];
}
不过这种方法的效率也不高，当m=2，n太大时，或m=3时，执行时间也很长，将近10秒，甚至更长，直至栈溢出。
我们换用第三种方法，直接推到公式。
A(0, n) = n+1;
A(1, n) = A(0, A(1, n-1))
= A(1, n-1) + 1
= A(1, n-2) + 2
= n + 2;
A(2, n) = A(1, A(2, n-1))
= A(2, n-1) + 2
= A(2, n-2) + 2*2
= 2*n + 3;
A(3, n) = A(2, A(3, n-1))
= A(3, n-1)*2 +3
= 5*2^n + 3*2^(n-1) + … 3*2 + 3
= 经过拆项，合并
= 2^(n+3) – 3
经推导
A(4,1) = 65533
A(4,2) = A(3, A(4, 1)) = 2^(A(4, 1) + 3) – 3 = 2^65536 – 3
于是，在计算机能表示的数范围内，我们可以用公式来求出Ackermann函数的值。
Ackerman函数递归求解：
#include <iostream>
#include <cstdlib>
using namespace std;
long ackman(long m, long n);
int main(int argc, char *argv[])
{
long m,n;
cin>>m>>n;
cout<<ackman(m,n);
system("PAUSE");
return 0;
}
long ackman(long m, long n)
{
long stack[10000];
int pos=1;
stack[0]=m;stack[1]=n;
while(pos)
{
n=stack[pos--];
m=stack[pos];
if(m==0)
stack[pos]=n+1;
if(m!=0&&n==0)
{
stack[pos++]=m-1;
stack[pos]=1;
}
if(m!=0&&n!=0)
{
stack[pos++]=m-1;
stack[pos++]=m;
stack[pos]=n-1;
}
}
return stack[0];
}