青蛙过河,我哪一步理解错了。。。递归和汉诺塔

2018-08-24 00:14:11 +08:00
 9torres

1 )一条小溪尺寸不大,青蛙可以从左岸跳到右岸,在左岸有一石柱 L,石柱 L 面积只容得下一只青蛙落脚,同样右岸也有一石柱 R,石柱 R 面积也只容得下一只青蛙落脚。 2 )有一队青蛙从小到大编号:1,2,…,n。 3 )初始时:青蛙只能趴在左岸的石头 L 上,按编号一个落一个,小的落在大的上面---不允许大的在小的上面。 4 )在小溪中有 S 个石柱、有 y 片荷叶。 5 )规定:溪中的每个石柱上如果有多只青蛙也是大在下、小在上,每个荷叶只允许一只青蛙落脚。 6 )对于右岸的石柱 R,与左岸的石柱 L 一样允许多个青蛙落脚,但须一个落一个,小的在上,大的在下。 7 )当青蛙从左岸的 L 上跳走后就不允许再跳回来;同样,从左岸 L 上跳至右岸 R,或从溪中荷叶、溪中石柱跳至右岸 R 上的青蛙也不允许再离开。 问题:在已知小溪中有 s 根石柱和 y 片荷叶的情况下,最多能跳过多少只青蛙?

//a 石柱 b 荷叶

#include <stdio.h> int number(int a,int b) { if(a==0) //因为 s=0 时,数目已知所以当作递归结束条件(两个未知数) return b; else return 2*number(a-1,b); //每一个都是前一个两倍,直到 a==0 } int main() { int s,y; while(scanf("%d%d",&s,&y)!=EOF) { printf("%d\n",number(s,y+1)); } return 0;

}

我找到的答案都如上所示,是个递归问题。可是当石柱数量是 3 或 3 以上是,不是变成汉诺塔了吗,不是可以跳无数只到对岸吗?? 0 片荷叶,3 根石柱不是不止 8 只吗??我理解问题哪里理解错了吗》

还有这代码发出去就没按我的格式了,能排版吗,刚来的萌新。

1774 次点击
所在节点    问与答
11 条回复
CEBBCAT
2018-08-24 00:25:16 +08:00
代码把 gist 链接发过来就 OK
9torres
2018-08-24 00:32:54 +08:00
@CEBBCAT 那这道题我哪里理解错了亲。。
CEBBCAT
2018-08-24 00:40:27 +08:00
@9torres 我不想看 23333
CEBBCAT
2018-08-24 00:47:13 +08:00
@9torres 读起来有点晕晕乎乎的,主要是怎么跳,约束条件是什么不明白,睡了
nomoon
2018-08-24 04:04:20 +08:00
第一根和最后一根石柱跳上去后不能往回跳,所以不是汉诺塔吧
Xs0ul
2018-08-24 04:32:52 +08:00
可以在中间三个石柱玩汉诺塔,但是排出来的也是从大到小,没法变成右岸的从大到小。除非中间能让你倒着排从小到大的,才能一个个移到右岸
xuanbg
2018-08-24 07:37:18 +08:00
汉诺塔是可以搬回来的吧
9torres
2018-08-24 09:01:04 +08:00
@nomoon 那当有 5 根石柱时,中间 3 根不是又变成汉诺塔了。。。
9torres
2018-08-24 09:03:50 +08:00
@Xs0ul 那 0 荷叶 3 石柱可以跳几只啊。。我的答案是无数只,反正不止 8 只,我数出有 9,10 只的情况了。。
9torres
2018-08-24 09:09:15 +08:00
@Xs0ul 汉诺塔下大上小。你能把最大那只跳到第三根石柱,那跳的时候也可以选择直接跳到对岸而不是第三根石柱,剩下的依次类推依次把大的跳到第三根石柱改为跳到对岸。。
nomoon
2018-09-08 02:47:12 +08:00
@9torres 看起来是好像可以算汉诺塔,题目本来就是长这样么?有原题链接么?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/482701

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX