青蛙過河，我哪一步理解錯了。。。遞歸變漢諾塔

1）一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，石柱L面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，石柱R面積也只容得下一只青蛙落腳。
2）有一隊青蛙從小到大編號：1，2，…，n。
3）初始時：青蛙只能趴在左岸的石頭 L 上，按編號一個落一個，小的落在大的上面---不允許大的在小的上面。
4）在小溪中有S個石柱、有y片荷葉。
5）規(guī)定：溪中的每個石柱上如果有多只青蛙也是大在下、小在上，每個荷葉只允許一只青蛙落腳。
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;

}

我找到的答案都如上所示，是個遞歸問題?？墒钱斒鶖?shù)量是3或3以上是，不是變成漢諾塔了嗎，不是可以跳無數(shù)只到對岸嗎？？
0片荷葉，3根石柱不是不止8只嗎？？我理解問題哪里理解錯了嗎》

回答

編輯回答

拼未來

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 柱，之后無法再繼續(xù)跳更多青蛙，最后 L 柱往 R 柱跳 1 只，A 柱跳 1 只，B 柱跳 2 只（這里需要先在 A 柱跳完后往 A 跳一次，再跳 R 柱），總共 4 只
n = 3 時，其實基本可以看出遞歸的規(guī)律了，比如接著上面的情況，多了一個 C 柱，那么這個柱子可以先從 L 柱跳一只青蛙下來，之后河中其余柱子上的青蛙均跳至 C 柱，C 柱上的青蛙就等于 1（A柱青蛙） + 2（B柱青蛙） + 1（L柱新跳下來的青蛙）= 4，然后 B 柱按上一種情況可知是 2，A 柱是 1，最終至多跳 1 + 2 + 4 + 1 = 8 只
n = 4 時，按上面的規(guī)律就能知道，D 柱上先從 L 柱跳 1 只，然后其余柱子的青蛙跳過來，總共 8 只，然后至多跳 1 + 2 + 4 + 8 + 1 = 16 只
...（略）

這個過程似乎和漢諾塔很像，但是不是漢諾塔。

最后在這個基礎之上來考慮荷葉不為 0 的情況，由于荷葉上只能跳 1 只青蛙，相當于只是將問題的規(guī)模放大了，所以最后答案是荷葉數(shù)量 + 1（直接跳到 R 柱的那個青蛙）之后按河中柱子的個數(shù)依次乘以 2。

2017年10月15日 06:50

編輯回答

款爺

7）當青蛙從左岸的L上跳走后就不允許再跳回來；同樣，從左岸L上跳至右岸R，或從溪中荷葉、溪中石柱跳至右岸R上的青蛙也不允許再離開。
就是這個條件導致不能完全等同于漢諾塔

2017年1月22日 10:51

編輯回答

舊城人

漢諾塔與本題的區(qū)別是, 本題的最終目標只允許進入一次, 而漢諾塔可以來回進出. 如果R柱子一旦上去就沒法下來, 如果沒有柱子, 只有荷葉, 那么 R 住子上可以站的數(shù)量等于荷葉的數(shù)量 + 1, 這個很容易理解, 如果再加一根珠子, 那么數(shù)量就多一倍. 依次類推.

2017年5月31日 04:49

編輯回答