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

[Adamzyg]

你们连代码都搞出来了，我说一下我用用的思路：
先架设有N个阶梯，到达每一个阶梯的走法是Sn，你跨上第N个阶梯的方法有2种

   1. 从Sn-1跨一步上Sn
   2. 从Sn-2跨2步到Sn

所以，跨上Sn的公式是
  Sn = Sn-1 + Sn-2
其中S2 = 1，S3 = 2

这个公式需要演绎一下，将Sn-2移到左边
Sn - Sn-2 = Sn-1
然后左边从n=4开始左右两边求和，就是：
Sn - Sn-2 = Sn-1
Sn-1 - Sn-3 = Sn-2
Sn-2 - Sn-4 = Sn-3
... - ... = ...
S5 - S3 = S4
S4 - S2 = S3

Sn - S3 -S2 = S3 + S4 +... +Sn-1
Sn = S2 + S3 + S4 +... + Sn-1 + S3 = Σ </wiki/%CE%A3>n-1 + S3

这样算出来，第11阶梯的数确实是89了。有问题大家斧正哈！


在 2010年4月14日 上午3:10，dhyang <dhyang555在gmail.com>写道：

> 在 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;
> }
>
>
>
>
>
> _______________________________________________
> Chinese mailing list
> Chinese at lists.fedoraproject.org
> https://admin.fedoraproject.org/mailman/listinfo/chinese
>