[FZH] 出个小题，大家娱乐下

[dhyang]

在 2010-04-14三的 00:31 +0800，LI Rui Bin写道：
> 用Python简单编了个递归来算，结果15阶是987种走法，耗时0.137s；25阶是 
> 121393种走法，耗时0.575s；35阶是 14930352种走法，但耗时56.001s。
> 
> 这种增量……
> 
> On 04/13/2010 09:02 PM, Devil Wang wrote:
> > 有N个台阶，每次只能跨1步或者2步.
> >
> > 问走到第100阶台阶的时候总共有多少种走法.

今晚居然失眠了，总想刚才的算法，确实存在很大的漏洞，其实不是一个排列问
题，我一上来就联想到排列，所以岀了个搞笑的算法。

我的新算法是这样的：
设为N（偶数）个台阶，如果全部都是2步，则需要N／2次。
如果全部都是1步，则需要N 次。
则从N／2到N 共N／2＋1种组合
不失一般性：
设某一组合有2＊i个1步，则有N／2－i个2步；
2＊i个1步将一个抽象空间分为2＊i＋1个部分；
将N／2－i个两步随机分入2＊i＋1个空间；
则该组合共有（2＊i＋1）＊（N／2－i）种走法；
而第一种和最后一种组合分别只有一种走法，单独计算。
for example：
如果N＝2， 则有两种走法，两个1步，和1个两步。 
如果N＝4  则有五种走法，22，1111，112，121，211
……

[yang在fedora test]$ vi 102.cpp
[yang在fedora test]$ g++ -o 102 102.cpp
[yang在fedora test]$ ./102
2
2
[yang在fedora test]$ ./102
4
5
[yang在fedora test]$ ./102
10
52
[yang在fedora test]$ ./102
100
42877
[yang在fedora test]$ 

可见，N为10的时候，有52种走法。
而不是98种。
N=100,有42877种走法。希望各位大牛各抒己见。

用C＋＋编制程序如下：
//102.cpp
#include <iostream>
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
for(int i=1;i<n/2;++i)  
{
int j=2*i+1; 
sum+=j*(n/2-i);
}
sum+=2;  //第一种组合和最后一种组合单独计算
cout<<sum<<endl;
return 0;
}