几只青蛙可过河? - 辕门射虎 - 轩辕春秋文化论坛 20周年


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#1

发表于 2004-10-26 23:23 资料主页文集短消息只看该作者

河内塔是一个经典的小游戏没玩过的朋友去电子词典文曲星上玩玩看下面推出资料片加强版条件虽然很多但如果你玩过就会发现很多是废话

大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。

青蛙的站队和移动方法规则如下：
1。每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）；
2。一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点；
3。青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上；
4。青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；
5。青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；
6。假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。
7。荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。
8。每一步只能移动一只青蛙，并且移动后需要满足站队规则；
9。在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。
青蛙希望最终能够全部移动到D上，并完成站队。

设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。
例如，在m=1且 n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），共跳动9步（试着玩一玩）

呵呵别被样子吓到了这道题不是很难的各位

[广告] 真诚支持说岳，携手共创辉煌


	god_wolf

组别	士兵
级别	牙门将军
功绩	5
帖子	521
编号	6045
注册	2004-3-16

#2

发表于 2004-10-28 08:36 资料主页短消息只看该作者

例如，在m=1且 n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），共跳动9步

不能回跳,4只怎么过河啊?思路受限,还望告之.

[广告] 真诚支持说岳，携手共创辉煌


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#3

发表于 2004-10-28 12:16 资料主页文集短消息只看该作者

开始
1
2
3
4
A  S1  Y1 D
第一步
2
3
4    1
A  S1  Y1 D
第二步
3
4 2 1
A  S1  Y1 D
第三步
3 1
4 2
A  S1  Y1 D
第四步
1
4 2 3
A  S1  Y1 D
第五步
1
2 3 4
A  S1  Y1  D
第六步
1       3
2       4
A  S1  Y1 D
第七步
         3
2 1 4
A  S1  Y1 D
第八步
            2
            3
      1 4
A  S1  Y1 D
第九步
            1
            2
            3
            4
A  S1  Y1 D

此题为A级题目

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	god_wolf

组别	士兵
级别	牙门将军
功绩	5
帖子	521
编号	6045
注册	2004-3-16

#4

发表于 2004-10-29 03:18 资料主页短消息只看该作者

哈哈,没注意看题,原来可以直接跳的,我以为一定要先跳到中间呢

[广告] 《精忠报国岳飞传完整版》火热发布


	龙笑酒粥

组别	士兵
级别	忠义校尉
功绩	3
帖子	283
编号	1245
注册	2003-10-3

#5

发表于 2004-10-29 11:17 资料主页短消息只看该作者

(n+2m+1)*n/2+m+1

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#6

发表于 2004-10-29 13:43 资料主页文集短消息只看该作者

楼上答案错误同时另外说明
解出结果后请附上解题方法方为有效解答

[广告] 《精忠报国岳飞传完整版》火热发布


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#7

发表于 2004-10-30 10:42 资料主页文集短消息只看该作者

三天了，我来答吧。

观察得知，青蛙过河的跳的总次数为奇数，即为2k+1次。前k次把除了最大的青蛙全都跳到河中间，第(k+1)次最大的青蛙跳到对面，后k次把河中间的青蛙跳到对面。
即能过河的青蛙数为河中间最多站的青蛙数+1。
令f(m,n)＝河中间最多站的青蛙数=能过河的青蛙数-1。
每个荷叶站一个
f(m,0)=m
每增加一个石墩，能多站一倍多一个，即新石墩上站一个，然后把其他荷叶和石墩上的全部垒到新石墩上去。
f(m,n)=2f(m,n-1)+1
故：f(m,n)=(m+1)*(2^n)-1
能过河的青蛙数=f(m,n)+1=(m+1)*(2^n)

[广告] 《精忠报国岳飞传完整版》火热发布