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

[dhyang]

在 2010-04-14三的 11:01 +1000，Caius 'kaio' Chance写道：
> 
> A： 100 階只有 1 次兩步，是 99 種不同。這是 nPr 不是 nCr。
> B： 100 階只有 2 次兩步，是 97 + 96 + .. + 2 + 1 種不同，這是 ( 97 +
> 1 ) * [ ( 97 + 1
> ) / 2 ] ；即是
> 
> ( 階數 - 走兩步次數 ) * [ ( 階數 - 走兩步次數 ) / 2 ]
> 
> C： 100 階只有 2 次兩步，是 ( 97 + 96 + .. + 2 + 1 ) + ( 96 + 95 + ..
> + 2 + 1 )
> + ( 95 + 95 + .. + 2 + 1) + .. + ( 2 + 1 ) + ( 1 ) 。
> 
> 我想如果連幾何級數都抽象化不到，就真的要用微分了吧？太忙，暫時擱下。 


我的新算法是这样的：
设为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;
}