数据结构题集-第三章-栈和队列-Ackerman函数

Ackerman函数

说明
3.27 已知Ackerman函数的定义如下
- （1）递归算法如下
- （2）非递归算法如下
- （3） $akm (2, 1)$ 时栈的变化过程如下

说明

本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

3.27 已知Ackerman函数的定义如下

$akm(m,n)=\begin{cases} akm(m-1,akm(m,n-1))\quad &m\neq{0},n\neq{0}\\ akm(m-1,1) &m\neq{0},n=0\\ n+1 &m=0 \end{cases}$
（1）写出递归算法；
（2）写出非递归算法；
（3）根据非递归算法，画出求 $akm (2, 1)$ 时栈的变化过程。

解：

（1）递归算法如下

int akm(int m,int n){int a,g;if(m==0) a=n+1;else if(n==0) a=akm(m-1,1);else{g=akm(m,n-1);a=akm(m-1,g);}return a;
}

（2）非递归算法如下

#include<stdio.h>
#define STACK_SIZE 50000
typedef struct{int mval;int nval;
} ElemType;typedef struct{int top;
} Stack;ElemType space[STACK_SIZE];void init_stack(Stack *ps){ps->top=0;
}int stack_empty(Stack s){return !s.top;
}void push(Stack *ps,ElemType e){if(ps->top>=STACK_SIZE) return;space[ps->top++]=e;
}void pop(Stack *ps,ElemType *pe){if(ps->top<=0) return;*pe=space[--ps->top];
}int get_top(Stack s,ElemType *pe){if(s.top<=0) return 0;else{*pe=space[s.top-1];return 1;}
}int akm(int m,int n){int a,g;if(m==0) a=n+1;else if(n==0) a=akm(m-1,1);else{g=akm(m,n-1);a=akm(m-1,g);}return a;
}void print_space(Stack s){int i;for(i=0;i<STACK_SIZE;i++){if(i==s.top)printf("[");printf("{%d,%d}",space[i].mval,space[i].nval);if(i==s.top)printf("]");}printf("\n");
}int akm_nonr(int m,int n){Stack s;ElemType e,et;init_stack(&s);e.mval=m;e.nval=n;push(&s,e);do{if(!get_top(s,&e)) break;while(e.mval){if(!get_top(s,&e)) break;while(e.nval){e.nval--;push(&s,e);}pop(&s,&e);e.mval--;e.nval=1;push(&s,e);}if(s.top>1){pop(&s,&e);et.nval=e.nval;pop(&s,&e);e.mval--;e.nval=et.nval+1;push(&s,e);}if(!get_top(s,&et)) break;}while(s.top>1||et.mval>0);pop(&s,&et);//print_space(s);return et.nval+1;
}int main(){int m,n;m=2,n=1;do{printf("%d\n",akm(m,n));printf("%d\n",akm_nonr(m,n));scanf("%d %d",&m,&n);}while(m>0&&n>0);return 0;
}

这里的非递归算法并没有按照书后的答案走捷径，
严格使用栈的操作，
每当需要改变栈顶元素的值，
都是先出栈，改了以后就入栈。

（3） $akm (2, 1)$ 时栈的变化过程如下

对栈中元素的操作	栈的内容[方括号中间是栈顶元素]
push({2,1})	[{2,1}]
push({2,0})	{2,1}[{2,0}]
change top value	{2,1}[{1,1}]
push({1,0})	{2,1}{1,1}[{1,0}]
change top value	{2,1}{1,1}[{0,1}]
pop() to e={0,1}	{2,1}[{1,1}]
change top value	{2,1}[{0,2}]
pop() to e={0,2}	[{2,1}]
change top value	[{1,3}]
push({1,2})	{1,3}[{1,2}]
push({1,1})	{1,3}{1,2}[{1,1}]
push({1,0})	{1,3}{1,2}{1,1}[{1,0}]
change top value	{1,3}{1,2}{1,1}[{0,1}]
pop() to e={0,1}	{1,3}{1,2}[{1,1}]
change top value	{1,3}{1,2}[{0,2}]
pop() to e={0,2}	{1,3}[{1,2}]
change top value	{1,3}[{0,3}]
pop() to e={0,3}	[{1,3}]
change top value	[{0,4}]
pop() to e={0,4}	result=4+1=5