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

[Devil Wang]

看错了，是你算15的耗时也不到.。

2010/4/14 Devil Wang <wxjeacen在gmail.com>

> 也不知道发过去的图片有没有被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
>



-- 
Thanks & Regards

Linux Developer : Devil Wang