Ackerman(nm)函数的非递归算法.doc

题目：已知Ackerman函数的定义如下： A（1,0）=2 n=1,m=0 Ackerman= A（0,m）=1 n=0,m=0 A（n,0）=n+2 m=0,n=2 A（A（n-1，m）,m-1） m,n=1 设计思想： m,n成对出现，将其作为一个组合，通过栈保存。 然后分4部分处理（如题所示）； 通过笔算研究规律： I、当计算“m,n=1”时，总是先n--(“m--”是到出口返回才计算的)，直到算到“n=0，m=0”的第一个出口； II、此时进入第二段函数，开始返回计算，相当于A(n-1,m)置1，m--； III、当m减到0时，如果n=1,进入第一段函数; 如果n=2，进入第三段； 4 2 2 , 2 2 2 4 4 非递归算法： #includeiostream using namespace std; class elem //栈中元素类型的定义 { public: int n; int m; public: elem(){} elem(int x,int y) { n=x; m=y; } void output() { coutn\tm\n; } }; class stack //栈的定义 { private: elem *e; int msize; int top; public: stack(int); bool isempty(); bool isoverflow(); void push(elem); int GetTop(); void pop(); elem GetElem(int); void output(); }; stack::stack(int n) //构造函数 { msize=n; e=new elem[msize]; top=-1; } bool stack::isempty() //判断栈是否为空 { if(top==-1) { cout该栈已空!\n; return 1; } else return 0; } bool stack::isoverflow() //判断栈是否溢出 { if(top==msize-1) { cout该栈已满!\n; return 1; } else return 0; } void stack::push(elem x) //数据入栈 { if(!isoverflow()) e[++top]=x; } int stack::GetTop() //获得top的值 { return top; } void stack::pop() //数据出栈，不弹出元素。 { top--; } elem stack::GetElem(int top) //获得当前top值指向的数据元素 { return e[top]; } void stack::output() //输出栈中的数据 { for(int i=0;i=top;i++) e[i].output(); cout\n; } int A(int n,int m) //Ackerman函数 { elem u; u.n=n; u.m=m; stack s(20); int t; s.push(u); while(s.GetTop()!=-1) { if(n0 || m0 ||(n=3 m3) ||(n=4 m=3)) //注意两个越界的条件（3,4）和（4,3） { cout\n输入数据有误,请查证!\n\n; exit(1); } if(u.n==1 u.m==0) //用if/while皆可； { s.pop(); if(s.GetTop()==-1) //对n=1,m=0的情况特殊处理 return 2; u=s.GetElem(s.GetTop()); u.n=2; u.m--; s.pop(); s.push(u);