V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
9torres
V2EX  ›  问与答

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

  •  
  •   9torres · 2018-08-24 00:14:11 +08:00 · 1762 次点击
    这是一个创建于 2282 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 只吗??我理解问题哪里理解错了吗》

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

    11 条回复    2018-09-08 02:47:12 +08:00
    CEBBCAT
        1
    CEBBCAT  
       2018-08-24 00:25:16 +08:00 via Android
    代码把 gist 链接发过来就 OK
    9torres
        2
    9torres  
    OP
       2018-08-24 00:32:54 +08:00
    @CEBBCAT 那这道题我哪里理解错了亲。。
    CEBBCAT
        3
    CEBBCAT  
       2018-08-24 00:40:27 +08:00 via Android
    @9torres 我不想看 23333
    CEBBCAT
        4
    CEBBCAT  
       2018-08-24 00:47:13 +08:00 via Android
    @9torres 读起来有点晕晕乎乎的,主要是怎么跳,约束条件是什么不明白,睡了
    nomoon
        5
    nomoon  
       2018-08-24 04:04:20 +08:00
    第一根和最后一根石柱跳上去后不能往回跳,所以不是汉诺塔吧
    Xs0ul
        6
    Xs0ul  
       2018-08-24 04:32:52 +08:00
    可以在中间三个石柱玩汉诺塔,但是排出来的也是从大到小,没法变成右岸的从大到小。除非中间能让你倒着排从小到大的,才能一个个移到右岸
    xuanbg
        7
    xuanbg  
       2018-08-24 07:37:18 +08:00
    汉诺塔是可以搬回来的吧
    9torres
        8
    9torres  
    OP
       2018-08-24 09:01:04 +08:00
    @nomoon 那当有 5 根石柱时,中间 3 根不是又变成汉诺塔了。。。
    9torres
        9
    9torres  
    OP
       2018-08-24 09:03:50 +08:00
    @Xs0ul 那 0 荷叶 3 石柱可以跳几只啊。。我的答案是无数只,反正不止 8 只,我数出有 9,10 只的情况了。。
    9torres
        10
    9torres  
    OP
       2018-08-24 09:09:15 +08:00
    @Xs0ul 汉诺塔下大上小。你能把最大那只跳到第三根石柱,那跳的时候也可以选择直接跳到对岸而不是第三根石柱,剩下的依次类推依次把大的跳到第三根石柱改为跳到对岸。。
    nomoon
        11
    nomoon  
       2018-09-08 02:47:12 +08:00
    @9torres 看起来是好像可以算汉诺塔,题目本来就是长这样么?有原题链接么?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5777 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 02:25 · PVG 10:25 · LAX 18:25 · JFK 21:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.