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

Question

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 片荷叶的情况下，最多能跳过多少只青蛙？

---

include<iostream>

using namespace std;

int cross_river(int S, int y)
{

if(0 == S)
    return y + 1;
else
    return 2 * cross_river(S-1, y);

}
int main()
{

int S, y;
cout << "Please input the number of 石柱 and 荷叶 leaves:" << endl;
cin >> S >> y;
cout << "Number of frogs: " << cross_river(S, y) << endl;
system("pause");
return 0;

}

---

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

Answer 1

7）当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。
就是这个条件导致不能完全等同于汉诺塔

Answer 2

汉诺塔与本题的区别是, 本题的最终目标只允许进入一次, 而汉诺塔可以来回进出. 如果R柱子一旦上去就没法下来, 如果没有柱子, 只有荷叶, 那么 R 住子上可以站的数量等于荷叶的数量 + 1, 这个很容易理解, 如果再加一根珠子, 那么数量就多一倍. 依次类推.

Answer 3

谁能告诉我0荷叶，3石柱，到底能跳过多少只青蛙？？？我找到的答案都是8只。
这是个递归问题。我想知道这题的答案》》我的答案是无数只。。数不清。。

Answer 4

0 荷叶，n 柱子这么想，假设河中有 n 个柱子：

• n = 0 时，至多有 1 只青蛙直接跳到 R 柱，这个不用解释
• n = 1 时，由于河中多了一个落脚的地方，那么这个柱子（A 柱）可以先从 L 柱至多跳 1 只青蛙下来，然后这个 A 柱和 L 柱总共至多可以跳 2 只青蛙至 R 柱
• n = 2 时，由于河中又多了一个柱子（B 柱），那么可以先从 L 柱跳 1 只青蛙到 B 柱，之后 A 柱的青蛙也可以跳到 B 柱上，然后 B 柱上有 2 只青蛙，然后 L 柱再跳 1 只青蛙至 A 柱，之后无法再继续跳更多青蛙，最后 L 柱往 R 柱跳 1 只，A 柱跳 1 只，B 柱 跳 2 只（这里需要先在 A 柱跳完后往 A 跳一次，再跳 R 柱），总共 4 只
• n = 3 时，其实基本可以看出递归的规律了，比如接着上面的情况，多了一个 C 柱，那么这个柱子可以先从 L 柱跳一只青蛙下来，之后河中其余柱子上的青蛙均跳至 C 柱，C 柱上的青蛙就等于 1（A柱青蛙） + 2（B柱青蛙） + 1（L柱新跳下来的青蛙）= 4，然后 B 柱按上一种情况可知是 2，A 柱是 1，最终至多跳 1 + 2 + 4 + 1 = 8 只
• n = 4 时，按上面的规律就能知道，D 柱上先从 L 柱跳 1 只，然后其余柱子的青蛙跳过来，总共 8 只，然后至多跳 1 + 2 + 4 + 8 + 1 = 16 只
• ...（略）

这个过程似乎和汉诺塔很像，但是不是汉诺塔。

最后在这个基础之上来考虑荷叶不为 0 的情况，由于荷叶上只能跳 1 只青蛙，相当于只是将问题的规模放大了，所以最后答案是荷叶数量 + 1（直接跳到 R 柱的那个青蛙） 之后按河中柱子的个数依次乘以 2。