一個騰訊筆試題

採用C編程，代碼如下：

#include

#define MAX 500

struct STACK

{

int m;

int n;

};

struct STACK S[MAX];

int akm1(int m, int n);

int akm(int m, int n);

void main()

{

int m,n;

int a,b;

printf("please input two data (m,n)n");

scanf("%d,%d",&m,&n);

a=akm (m,n);

b=akm1(m,n);

printf("n recursion=%d non-recursion=%dn",a,b);

}

// 遞歸的模擬

int akm(int m, int n)

{

if(m*n==0)

return m+n+1 ;

else

{

return akm(m-1, akm(m,n-1));

}

}//akm

//非遞歸算法: int akm1(int m, int n)

{

int top =0;

S[top].m=m; /*S[MAX]為附設棧,top為棧頂指針*/

S[top].n=n;

if (m*n==0) //m+n+1;

return m+n+1;

do //f(m-1,f(m,n-1)) S[i] save m and n-1; 遞歸的模擬

{

while (S[top].m) //m-->0

{

S[top].n=S[top].n-1;

while(S[top].n) //n-->0

{

top++;

S[top].m=S[top-1].m ;

S[top].n=S[top-1].n-1;

}

S[top].m--; //when n=0, m=m-1.

S[top].n=S[top].m+2; // n=m+2

}

if(top>0) // m=0,f(m,n)

{

top--;

S[top].m--;

S[top].n=S[top+1].n+1;

}

}

while(top!=0||S[top].m!=0);

return S[top].n+1; //m*n!=0;

}//akm1

待解決問題，當m逐漸增大時，棧很快便會溢出，得不出結果。只有當m值較小時，才能計算出結果。

下面是模擬騰訊給出的樣式 改進的'程序：

int akm2(int m, int n)

{

int top ,f;

int ST[MAX]={0}; /*S[MAX]為附設棧,top為棧頂指針*/

top=0;

if (m*n==0)

return m+n+1;

do //f(m-1,f(m,n-1)) S[i] save m ; 模擬遞歸

{

if (m*n!=0)//當m*n!=0時，進行壓棧處理

{

ST[top++]=m;

n--;

}

else //m*n=0

{

f=m+n+1;

if (top>0)

{

ST[top]=ST[--top]-1; //出棧操作

}

m=ST[top];//修改m,n的值

n=f;

}

}

while(top!=0||ST[top]!=0);

return f+1; //m*n!=0; 返回值

}