关于阿克曼函数的非递归算法 满意加300 C语言高手求解 在线等

Question

先看一下标准阿克曼函数的实现
akm(m, n) = n + 1; (m = 0时)
akm(m - 1, 1); (n = 0时)
akm(m - 1, akm(m, n - 1)); （m != 0且n != 0时)

int akm_nonrecursive(int m, int n)
{
int m1[50], n1[50], cp;

cp = 0;
m1[0] = m;
n1[0] = n;

do {
while (m1[cp] >; 0) { /* 压栈, 直到m1[cp] = 0 */
while (n1[cp] >; 0) { /* 压栈, 直到n1[cp] = 0 */
cp++;
m1[cp] = m1[cp - 1];
n1[cp] = n1[cp - 1] - 1;
}
/* 计算akm(m - 1, 1),当n = 0时 */
m1[cp] = m1[cp] - 1;
n1[cp] = 1;
}
/* 改栈顶为akm(m - 1, n + 1),当m = 0时 */
cp--;
m1[cp] = m1[cp] - 1;
n1[cp] = n1[cp + 1] + 1;
} while (cp >; 0 || m1[cp] >; 0);

return n1[0] + 1;
}
现在将阿克曼函数变化一下
补充为————注意看：将阿克曼函数稍稍变化：akm2(n,x,y)=
x+1; (n=0)
x; (n=1,y=0)
0; (n=2,y=0)
1; (n=3,y=0)
2; (n>3,y=0)
akm2(n-1,akm2(n,x,y-1),x) (n!=0,y!=0)

模拟上面问题中的算法 将新的函数的程序实现代码写出来

同样利用二叉树！！！！！！！！！！！！！！！！！！！！

+300分

Answer 1

楼主如果要加300分，可能要开2贴了，因为1贴最多只能200分，追加最多只能50分。

你给的那个解法，写的本来就有问题。
不信，你自己试试这个程序：

#include<stdio.h>

//非递归解法
int akm_nonrecursive(int m, int n)
{
int m1[50], n1[50], cp;

cp = 0;
m1[0] = m;
n1[0] = n;

do {
while (m1[cp] > 0) { /* 压栈, 直到m1[cp] = 0 */
while (n1[cp] > 0) { /* 压栈, 直到n1[cp] = 0 */
cp++;
m1[cp] = m1[cp - 1];
n1[cp] = n1[cp - 1] - 1;
}
/* 计算akm(m - 1, 1),当n = 0时 */
m1[cp] = m1[cp] - 1;
n1[cp] = 1;
}
/* 改栈顶为akm(m - 1, n + 1),当m = 0时 */
cp--;
m1[cp] = m1[cp] - 1;
n1[cp] = n1[cp + 1] + 1;
} while (cp > 0 || m1[cp] > 0);

return n1[0] + 1;
}

int main()
{
printf("%d\n",akm_nonrecursive(0,2));
printf("%d\n",akm_nonrecursive(2,0));
printf("%d\n",akm_nonrecursive(2,3));
return 0;
}本回答被提问者采纳

Answer 2

int f(int n,int x,int y)
{
int n1[100],x1[100],y1[100];
int cp=0;
n1[0]=n ; x1[0]=x; y1[0]=y;
do{
if(n1[cp]==0)
{
cp--;
n1[cp]--;
y1[cp]=x1[cp]; //根据计算函数 每次x移到y的位置
x1[cp]=x1[cp+1]+1;
}
else{
while(y1[cp]>0)
{
cp++;
n1[cp]=n1[cp-1];
x1[cp]=x1[cp-1];
y1[cp]=y1[cp-1]-1;
}
cp--;
y1[cp]=x1[cp];
if(n1[cp]==0) x1[cp]=x1[cp+1]+1;
if(n1[cp]==1) x1[cp]=x1[cp+1];
if(n1[cp]==2) x1[cp]=0;
if(n1[cp]==3) x1[cp]=1;
if(n1[cp]>=3) x1[cp]=2;
n1[cp]--;
}
}while(cp>0||n1[cp]>0);
return x1[0]+1;
}