標籤: 暫無標籤

  我們最常用的也是最直接的方法就是遞歸,這個方法在上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];


  }

上一篇[鬼哭狼嚎]    下一篇 [acdsee photo editor]

相關評論

同義詞:暫無同義詞