Question

ACM的一道问题。。。

火车沿途也不是所有站台都停靠，偶尔也是会跳过一些小站的。可以跳过一些小站，但是绝对不能连续跳过两站及以上，否则又要成为众矢之的了。现在，某条线上一共有m个站台（火车初始停靠在第一站），想知道一共有多少种停站方案可供选择，你能解决这个问题吗？
Input
输入数据首先包含一个整数N（N<=40），表示测试实例的个数，然后是N行数据，每行包含一个整数M（2<=M<=40）,表示该线站台的数量。
Output
每组输出仅有一行，包含一个整数，表示可供选择的方案数。
Sample Input
2
2
3Sample Output
12
HINT
样例说明：
第一个2表示n为2，即一共有两组数据（实际测试数据不止两组）；
第二个2表示第一组数据m为2，即一共有两站，而火车初始停靠在第一站，所以只有一种方案；
最后的3表示第二组数据m为3，即一共有三站，火车可以先开到第二站再到第三站，也可以直接开到第三站，所以有两种方案。

Answer 1

典型的斐波那契数列，有2中方法。
迭代：
#include <iostream>
using std::cin;using std::cout;
using std::endl;

int main(){
int n(0), m(0);
cin>>n;
while(n>0)
{
int feb[2]={1,1};
cin>>m;
if(2==m)cout<<1<<endl;
else if(m>2)
{
for(int i(2);i<m;++i)
{
int tmp(feb[1]);
feb[1]+=feb[0];
feb[0]=tmp;
}
cout<<feb[1]<<endl;
}
--n;
}
}

递归：
#include <iostream>
using std::cin;using std::cout;
using std::endl;

int feb(const int &n)
{
if(2==n||1==n)return 1;
else if(n>2)
{
return feb(n-1)+feb(n-2);
}
return 0;
}
int main()
{
int n(0), m(0);
cin>>n;
while(n>0)
{
cin>>m;
cout<<feb(m)<<endl;
--n;
}
return 0;
}

追问

写上注释行么，我想用二进制数字做，貌似c 不能定义二进制数字。。。这道题数学上是怎么解释的，原理是什么

Answer 2

很简单的动态规划。
dp[i]表示第i个站有多少种方案。
则有：
dp[1]=dp[2]=1;
dp[i]=dp[i-1]+dp[i-2];
以此类推

追问

为什么，不理解呀，

追答

很容易理解
第i个站只有两种到达方案
一是在i-1个站然后过了一个站停下的，这时候方案数就是第i-1个站的方案数。
二是第i-2过了两个站停下的，这时候方案数就是第i-2个站的方案数。
所以第i个站的方案数就是
第i-1个站的方案数 + 第i-2个站的方案数
我为了简便用了dp[i]表示第i个站有多少种方案
第一个站和第二个站的方案数显然都是1
则是：dp[1]=dp[2]=1;
后面的站就可以根据前面讲的理由去递推了
即：dp[i]=dp[i-1]+dp[i-2];
懂了么