递归递推之 青蛙过河

题目大概：

青蛙从a岸移动到b岸，小溪中有s个石头，y个荷叶。石头和荷叶都只能容纳一只青蛙，但石头上可以在大青蛙上放小青蛙，而荷叶上不行。刚开始青蛙小的放在大的上面，都在a岸，然后移动到b岸，从a岸离开或者到达b岸后不能回返，问最多有多少青蛙到达b岸。

思路：

a[n]为有n个石头的青蛙数。 1  如果有s=0个石头，m个荷叶，很显然，可以移动m+1个青蛙。 2  如果有s=1个石头，m个荷叶，那么m个荷叶上的青蛙可以移动到石头上，而石头上也可以放最大的那个青蛙，然后再进行s=0时的操作，共有2*（m+1）个。 3  如果有s=2个石头，m个荷叶，那么第2个石头上，也可以先放最大的青蛙，然后把荷叶上的青蛙放到第二个人石头上，然后第一个石头也是这样，这时，每个石头上都有m+1个青蛙，但是石头上的青蛙是可以重新放回荷叶的，于是，可以把第二个石头上的青蛙放回荷叶，这样就可以把青蛙都移动到第一个石头上，而第二个石头上就可以再放m+1个青蛙，然而根据步骤一，荷叶和b岸也可以放m+1个青蛙，于是一共有2*2（m+1）个， 4 观察会发现，第n个石头上的青蛙数是有n-1个石头上的青蛙数之和，即a[n-1], 于是a[n]=2*a[n-1]。从s=0到s=n有n个2,，所有a[n]=2ˆn*（m+1）。

感想：

题目想起来麻烦但代码简单。

代码：

#include <iostream>

using namespace std;


int main()
{int n,m;
while(cin>>n>>m)
{int t=1;
for(int i=0;i<n;i++)
{t=t*2;
}
cout<<(m+1)*t<<endl;

}

return 0;
}