Double recursion function

Ackermann Function is defined as

ack(0,n) = n + 1
ack(m,0) = ack( m-1, 1)
ack(m,n) = ack( m – 1, ack( m, n – 1 ))


For example
ack( 1, 1 )
= ack ( 0, ack ( 1, 0 ) )
= ack ( 0 , ack( 0, 1 ) )
= ack ( 0, 2 )
= 3

Try to work out ack( 1 , 2 ) and ack ( 1, 3 ) by hand.

Write a program that will accept two parameters and display the value of the corresponding Ackermann function. For example:


$ ack 1 1

The Ackermann value of ack(1,1) is 3

Using your program, try to find out the values of ack(2,3), ack(3,2) and ack(4,2).
WARNING!!!! It may not be as easy as it looks

这个怎么复杂法?有点类似编译原理里面的语法分析

int ack(int m,int n)
{
    if(m==0&&n==0) return 0;
    if(m==0) return n+1;
    if(n==0) return (ack(m-1,1));
    return ack(m-1, ack(m, n-1));
}


////////////////////////////////
我的程序很失败。。。算不出，呵呵

[[it] 本帖最后由 woshiyun 于 2008-10-16 12:57 编辑 [/it]]

LS的程序显然是不太有效的。注意LZ贴出来内容的最后一句话。

不过，不鼓励帮别人做作业。同时鄙视一下标题党。

溢出了，不准备写了……

[[it] 本帖最后由 StarWing83 于 2008-10-17 13:45 编辑 [/it]]

还是递归的思想。因为问题的求解跟问题的规模N有关。

版主啊！你那结果怎么做出来的啊，帮帮忙吧

递归式直接转换成递推做就可以啊。

我晕。。。我记忆化dp,怎么得不到SW的答案-.-

发现了。。。记忆dp没问题。。。数组越界了....在白度里面找到。。ack(4,2)=2^65536 − 3..计算机跑不动...