一个腾讯笔试题

采用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; 返回值

}