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

[dhyang]

在 2010-04-14三的 08:38 +0800，nvstp写道：
> 不是这么算的吧，只准走两步，那只有1种走法，不可能只准走一个一步，这样
> 走不了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;
}