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

1）一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，石柱L面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，石柱R面積也只容得下一只青蛙落腳。
2）有一隊(duì)青蛙從小到大編號(hào)：1，2，…，n。
3）初始時(shí)：青蛙只能趴在左岸的石頭 L 上，按編號(hào)一個(gè)落一個(gè)，小的落在大的上面---不允許大的在小的上面。
4）在小溪中有S個(gè)石柱、有y片荷葉。
5）規(guī)定：溪中的每個(gè)石柱上如果有多只青蛙也是大在下、小在上，每個(gè)荷葉只允許一只青蛙落腳。
6）對(duì)于右岸的石柱R，與左岸的石柱L一樣允許多個(gè)青蛙落腳，但須一個(gè)落一個(gè)，小的在上，大的在下。
7）當(dāng)青蛙從左岸的L上跳走后就不允許再跳回來(lái)；同樣，從左岸L上跳至右岸R，或從溪中荷葉、溪中石柱跳至右岸R上的青蛙也不允許再離開(kāi)。
問(wèn)題：在已知小溪中有 s 根石柱和 y 片荷葉的情況下，最多能跳過(guò)多少只青蛙？

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;

}

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

回答

編輯回答

拼未來(lái)

0 荷葉，n 柱子這么想，假設(shè)河中有 n 個(gè)柱子：

n = 0 時(shí)，至多有 1 只青蛙直接跳到 R 柱，這個(gè)不用解釋
n = 1 時(shí)，由于河中多了一個(gè)落腳的地方，那么這個(gè)柱子（A 柱）可以先從 L 柱至多跳 1 只青蛙下來(lái)，然后這個(gè) A 柱和 L 柱總共至多可以跳 2 只青蛙至 R 柱
n = 2 時(shí)，由于河中又多了一個(gè)柱子（B 柱），那么可以先從 L 柱跳 1 只青蛙到 B 柱，之后 A 柱的青蛙也可以跳到 B 柱上，然后 B 柱上有 2 只青蛙，然后 L 柱再跳 1 只青蛙至 A 柱，之后無(wú)法再繼續(xù)跳更多青蛙，最后 L 柱往 R 柱跳 1 只，A 柱跳 1 只，B 柱跳 2 只（這里需要先在 A 柱跳完后往 A 跳一次，再跳 R 柱），總共 4 只
n = 3 時(shí)，其實(shí)基本可以看出遞歸的規(guī)律了，比如接著上面的情況，多了一個(gè) C 柱，那么這個(gè)柱子可以先從 L 柱跳一只青蛙下來(lái)，之后河中其余柱子上的青蛙均跳至 C 柱，C 柱上的青蛙就等于 1（A柱青蛙） + 2（B柱青蛙） + 1（L柱新跳下來(lái)的青蛙）= 4，然后 B 柱按上一種情況可知是 2，A 柱是 1，最終至多跳 1 + 2 + 4 + 1 = 8 只
n = 4 時(shí)，按上面的規(guī)律就能知道，D 柱上先從 L 柱跳 1 只，然后其余柱子的青蛙跳過(guò)來(lái)，總共 8 只，然后至多跳 1 + 2 + 4 + 8 + 1 = 16 只
...（略）

這個(gè)過(guò)程似乎和漢諾塔很像，但是不是漢諾塔。

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

2017年10月15日 06:50

編輯回答

款爺

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

2017年1月22日 10:51

編輯回答

舊城人

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

2017年5月31日 04:49

編輯回答