首页 > 试题广场 >

仔细阅读以下一段递归的函数定义，回答问题。

[填空题]

仔细阅读以下一段递归的函数定义：

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

请问ack(3,3)的返回值是1。

查看答案及解析

在拧螺丝的起司很愉快

ack(0,n) = n+1，ack(0,1)=2,ack(1,0)=ack(0,1)=2

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

An = An-1 + 1 推出递推公式为An=n+1,即ack(1,n)=n+2

ack(2,n) = ack(1,ack(2,n-1))=ack(2,n-1)+2

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

类似的：ack(2,n)= 2n+3

ack(3,n) = ack(2,ack(3,n-1))= 2ack(3,n-1)+3

ack(3,n) + 3 = 2(ack(3,n-1) + 3)

ack(3,0) = 5

等比公式：ack(3,n)=2^(3(n-1))-3

故：ack(3,3)=61

http://blog.csdn.net/gpengtao/article/details/7438587 这里的ack(1,n)求错了

发表于 2015-08-14 15:51:43 回复(1)

王俊超

1,ack(1,n)=ack(0,ack(1,n-1))+1 =ack(1,n-1)+1; //递推式

2，ack(2,n)=ack(1,ack(2,n-1)) =ack(2,n-1)+2; //递推式

3,ack(3,n)=ack(2,ack(3,n-1)) =2*ack(3,n-1)+3; //递推式

发表于 2015-08-05 11:55:34 回复(0)

势在必得

Ackman 函数。具体解法见http://blog.csdn.net/gpengtao/article/details/7438587

发表于 2015-07-01 22:55:06 回复(0)

사나이

(0,n)->n+1

(1,n)->n+2:

(1,0)->(0,1)->2
(1,1)->(0, (1, 0))->3
(1,2)->(0, (1, 1))->4
(1,n)->(0, (1, n-1))->(1,n-1)+1

(2,n)->2n+3:

(2,n)->(1, (2, n-1))->(2, n-1)+2
(2,0)->(1, 1)->3
(2,1)->(2, 0)+2->5
(2,2)->(2,1)+2 ->7

(3,n)->(2, (3, n-1)->2*(3, n-1)+3
(3,0)->(2,1)->5
(3,1)->2*(3, 0)+3->13
(3,2)->2*(3,1)+3->29
(3,3)->2*(3,2)+3->61

发表于 2015-10-20 15:53:19 回复(0)

新世纪的神

直接用程序跑了一遍，考递归也不用这么多层吧

发表于 2016-07-03 20:24:38 回复(0)

雪中漫步

ack(0,n) = n+1，ack(0,1)=2,ack(1,0)=ack(0,1)=2

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

An = An-1 + 1 推出递推公式为An=n+1,即ack(1,n)=n+2

ack(2,n) = ack(1,ack(2,n-1))=ack(2,n-1)+2

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

类似的：ack(2,n)= 2n+3

ack(3,n) = ack(2,ack(3,n-1))= 2ack(3,n-1)+3

ack(3,n) + 3 = 2(ack(3,n-1) + 3)

ack(3,0) = 5
琼华的最后等比公式求错了，比如n=0时求的ack(3,0)为负数，实际为5，故上面错了.

应该是ack(3,n)=2^(n+3)-3 ！！

发表于 2016-04-01 01:52:38 回复(4)

PaperFish

求到一半发现自己的笔都写没墨了，算了，瞎蒙一个

发表于 2017-03-22 11:59:53 回复(0)

Echo001

推导通项公式------

计算量太大了~~~

发表于 2016-08-26 17:43:00 回复(0)

huixieqingchun

用递推公式可以更好更直观的解题。

发表于 2016-05-12 13:29:04 回复(0)

提交观点

问题信息

腾讯递归

上传者：子若无双

难度：

9条回答 418收藏 6980浏览

仔细阅读以下一段递归的函数定义，回答问题。

问题信息

热门推荐

相关试题