8_3_ackermann.c

gc:高级程序员考试用书的c程序源文件

# include <stdio.h>
# define MAXN 8000
typedef struct node {
	int n;
	double x,y;
}NODE;

NODE stack[MAXN];
int top,deb,depth;

/*顺序存储栈的进栈函数*/
int push(NODE stack[],int maxn,int *toppt,NODE x)     /*进栈函数*/
{
	if (*toppt >= maxn) return 1; /*栈满,进栈失败返回1 */
	stack[*toppt] = x;                     /*完成进栈运算   */
	++ *toppt;
	if (*toppt > depth) depth = *toppt;
	return 0;                               /*进栈成功,返回0 */
}

/*顺序存储栈的出栈函数*/
int pop(NODE stack[],int *toppt,NODE *cp)
{
	if(*toppt == 0) return 1;                                /*栈空,出栈失败返回1 */
	-- *toppt;
	*cp = stack[*toppt];                                  /*完成出栈运算 */
	return 0;                                             /*出栈成功,返回0*/

}

double A(NODE node)
{
	int k; double B;
	NODE tnode;
	top = 0;depth = 0;
	push(stack,MAXN,&top,node);                     /* 将node进栈*/
	do {                                            /*循环计算至栈空*/
		tnode = stack[top-1];                       /*读栈顶结点的值存入tnode*/
		while (tnode.n != 0 && tnode.y !=0) {       /*递推,将计算结果进栈*/
			/* 修改栈顶结点的参数,并求得新结点进栈*/
			stack[top-1].n--;stack[top-1].y = stack[top-1].x;
			stack[top-1].x = -1.0;                         /*表示x值不定*/
			tnode.y -= 1.0;
			if(push(stack,MAXN,&top,tnode)) return -1.0;    /*将tnode进栈*/
		}
		if (deb) {
			for (k = 0 < top-10? top-10:0;k<top;k++)
				printf("N = %4d,x = %8f,y = %8f\n",stack[k].n,stack[k].x,stack[k].y);
			scanf("% * c");
		}

		/*退栈,并将取得的栈顶结点的值存入tnode*/
		pop(stack,&top,&tnode);
		/*计算:B = A(tnode) */
		if (tnode.n == 0) B = tnode.x + 1.0;
		else if (tnode.n == 1) B = tnode.x;
		else if (tnode.n == 2) B = 0.0;
		else if (tnode.n == 3) B = 1.0;
		else B = 2.0;
		if(top) stack[top-1].x = B;             /*栈非空将栈顶结点的x值改为B*/
	}while (top);                       /*栈非空*/
	return B;                           /*返回B*/

}


void main()
{
	char c;//我添加的代码
	NODE node1 = {3,1,2},node2 = {3,2,5},node3 = {4,3,2};
	printf("DEB?      "); scanf("%d",&deb);
	printf("A(3,2,2) = %f",A(node1));
	printf("\t%d\n",depth);
	scanf("% * c");
	printf("A(3,2,5) = %f",A(node2));
	printf("\t%d\n",depth);
	scanf("%c",&c);//我添加的代码
	scanf("% * c");
	printf("A(4,3,2) = %f",A(node3));
	printf("\t%d\n",depth);
}