Ackerman(m,n)函数的非递归.doc

题目：已知Ackerman函数的定义如下： n+1 m=0 Ackerman= Ackerman(m-1,1) n = 0 m 0 Ackerman(m-1,Ackerman(m,n-1)) m 0 n 0 设计思想： m,n成对出现，将其作为一个组合，通过栈保存； 然后分三部分处理（如题所示）； 通过笔算观察： i、当计算“m0，n0”时，总是先计算n--(m--是返回计算才用的)直到算到“m0，n=0”； ii、计算到“m0，n=0”时需要计算“m=m-1，n=1”的情况; iii、当计算到“m=0”时，就开始考虑出口的处理（u.m=0，跳出循环）以及结果的存储（t）、返回（u.m=u.m-1;u.n=t;）了 29 13 5 3 3 5 2 非递归算法： #includeiostream using namespace std; class elem //栈中元素类型的定义 { public: int m; int n; public: elem(){} elem(int x,int y) { m=x; n=y; } void output() { coutm\tn\n; } }; class stack //类栈的定义 { private: elem e[30]; int top; public: stack(){ top=-1; } bool isempty(); bool isoverflow(); void push(elem); int GetTop(); void pop(); elem GetElem(int); void output(); }; bool stack::isempty() //判断栈是否为空。 { if(top==-1) { cout栈已空,无需出栈的数据!\n; return 1; } else return 0; } bool stack::isoverflow() //判断栈是否已满 { if(top==29) { cout栈已满,无法继续进栈!; return 1; } else return 0; } void stack::push(elem x) //进栈操作 { if(!isoverflow()) { top++; e[top]=x; } } int stack::GetTop() //返回top的值。 { return top; } void stack::pop() //修改top指针,相当于元素出栈。 { if(top=-1) return; 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 m,int n) //Ackerman函数 { int t; //用来存最后结果，也暂时存中间值呢。 stack s; elem u(m,n); s.push(u); u.output(); do { if(m0 || m=4 || n0) { cout输入数据有误,请查证!!!\n\n; exit(1); } while(u.m0 u.n0) { u.n--; s.push(u); //s.output(); } while(u.n==0 m0) { s.pop(); u=s.GetElem(s.GetTop()); u.m--; u.n=1; s.push(u); //s.output(); } while(u.m==0) //注意两个pop()函数的运用,缺一不可; { t=u.n+1; s.pop(); u=s.GetElem(s.GetTop()); if(u.