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

[Devil Wang]

也不知道发过去的图片有没有被block住。


-BASH-4.0.35$ cat src/main.cpp
#include "BigInteger.h"
#include<iostream>
#define N 3000
#include <ctime>
#include <cstdio>
using namespace std;
int main(int argc,char *argv[])
{
    int m;
    cin>>m;
    time_t start,end;
    start=clock();
    BigInteger buf[N+2]={BigInteger::ZERO,BigInteger::ONE,BigInteger(2)};
    for(int i=3;i<=N+1;i++)
    {
        buf[i]=buf[i-1]+buf[i-2];
    }
    cout<<buf[m]<<endl;
    end=clock();
    printf("Run Time: %10lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    return 0;
}

-BASH-4.0.35$ ./outcome
3000
664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
Run Time:   0.130000
-BASH-4.0.35$


发下我的算法。

简单 DP ,比递归高效多了，算3000的耗时才是你算30的耗时.

2010/4/14 LI Rui Bin <cheeseli在hotmail.com>

> 用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阶台阶的时候总共有多少种走法.
> >
> >
> >
>
> _______________________________________________
> Chinese mailing list
> Chinese at lists.fedoraproject.org
> https://admin.fedoraproject.org/mailman/listinfo/chinese
>



-- 
Thanks & Regards

Linux Developer : Devil Wang