Ackermann函式

阿克曼函式（Ackermann）是非原始遞歸函式的例子。它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高，僅是對於(4,3)的輸出已大得不能準確計算。

我們最常用的也是最直接的方法就是遞歸，這個方法在上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&#91;top--&#93;;
m = stack&#91;top&#93;;
if ( m == 0 )
{
stack&#91;top&#93; = n+1;
}
else if( m > 0 && n == 0)
{
stack&#91;top++&#93; = m - 1;
stack&#91;top&#93; = 1;
}
else if( m > 0 && n > 0)
{
stack&#91;top++&#93; = m - 1;
stack&#91;top++&#93; = m;
stack&#91;top&#93; = 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&#91;pos--&#93;;
m=stack&#91;pos&#93;;
if(m==0)
stack&#91;pos&#93;=n+1;
if(m!=0&&n==0)
{
stack&#91;pos++&#93;=m-1;
stack&#91;pos&#93;=1;
}
if(m!=0&&n!=0)
{
stack&#91;pos++&#93;=m-1;
stack&#91;pos++&#93;=m;
stack&#91;pos&#93;=n-1;
}
}
return stack[0];
}