当m*n=0时, f(m,n)=m+n+1;
当m*n!=0时,f(m,n)=f(m-1,f(m,n-1))
用C++编程~!!!
谢谢各位!!
[此贴子已经被作者于2006-4-9 16:20:35编辑过]
我自己做出来了!!
#include<iostream>
using namespace std;
#define NULL 0
class stacknode
{
private:
int data;
stacknode* link;
public:
stacknode(int item,stacknode*next=NULL){data=item;link=next;}
friend class stack;
};
class stack
{
private:
stacknode* top;
public:
stack(){top=NULL;}
void push(int item);
void pop(int &m);//弹出栈顶元素,并将该元素的值赋给m
bool IsEmpty(){return top==NULL;}
~stack();
};
stack::~stack()
{
stacknode* p;
while(top!=NULL)
{
p=top;
top=top->link;
delete p;
}
}
void stack::push(int item)
{
stacknode* p=new stacknode(item,top);
top=p;
}
void stack::pop(int &m)
{
m=top->data;
stacknode* p=top;
top=top->link;
delete p;
}
int function(int mm,int nn)
{
stack f;
int m=mm;
int n=nn;
while(!f.IsEmpty()||m*n!=0)
if(m*n==0) //
{
n=m+n+1;
f.pop(m);
}
else
{
f.push(m-1); //若m*n!=0,则函数继续向后展开
n=n-1;
}
return m+n+1;
}
void main()
{
cout<<function(2,1)<<endl;
}
还有一种方法::(现发过来,希望能帮助其他人)
#include<iostream>
using namespace std;
int function1(int m,int n)
{
int top=-1;
int stack[100];
stack[++top]=m;stack[++top]=n;
while(top>0)
if(stack[top-1]*stack[top]==0)
{
stack[top-1]=stack[top-1]+stack[top]+1;
top--;
}
else
{
stack[top+1]=stack[top]-1;
stack[top]=stack[top-1];
stack[top-1]=stack[top-1]-1;
top++;
}
return stack[top];
}
void main()
{
cout<<function1(1,2)<<endl;
}
楼主的有点麻烦,给个更简便的非递归算法:[CODE]
#include <stdio.h>
int f(int m,int n) { /*递归形式*/
if(m*n) return f(m-1,f(m,n-1));
return m+n+1;
}
int fd(int m,int n) { /*非递归形式(用while-if形式实现)*/
int s[5000],i=0;
while(m*n||i) {
if(m*n) s[i++]=m,--n;
else if(i) n=m+n+1,m=s[--i]-1;
}
return m+n+1;
}
main() {
printf("f:%d,fd:%d\n",f(3,4),fd(3,4));
}
[/CODE]