社群資訊
費氏數列的 時間複雜度
(高顯忠, sjgau4311@gmail.com, 2011-11-10 08:16)
1樓
/*
1, 1, 1.000000000000000000, 0.000
2, 2, 2.000000000000000000, 0.000
3, 3, 1.500000000000000000, 0.000
4, 5, 1.666666666666666700, 0.000
5, 8, 1.600000000000000100, 0.000
6, 13, 1.625000000000000000, 0.000
7, 21, 1.615384615384615400, 0.000
8, 34, 1.619047619047619100, 0.000
9, 55, 1.617647058823529400, 0.000
10, 89, 1.618181818181818200, 0.000
11, 144, 1.617977528089887600, 0.000
12, 233, 1.618055555555555600, 0.000
13, 377, 1.618025751072961400, 0.000
14, 610, 1.618037135278514600, 0.000
15, 987, 1.618032786885246000, 0.000
16, 1597, 1.618034447821681900, 0.000
17, 2584, 1.618033813400125300, 0.000
18, 4181, 1.618034055727554100, 0.000
19, 6765, 1.618033963166706400, 0.000
20, 10946, 1.618033998521803300, 0.000
21, 17711, 1.618033985017358000, 0.000
22, 28657, 1.618033990175597100, 0.000
23, 46368, 1.618033988205325000, 0.000
24, 75025, 1.618033988957902100, 0.000
25, 121393, 1.618033988670443100, 0.000
26, 196418, 1.618033988780242600, 0.000
27, 317811, 1.618033988738303100, 0.000
28, 514229, 1.618033988754322500, 0.000
29, 832040, 1.618033988748203600, 0.000
30, 1346269, 1.618033988750540800, 0.000
31, 2178309, 1.618033988749648200, 0.000
32, 3524578, 1.618033988749989000, 0.015
33, 5702887, 1.618033988749858900, 0.047
34, 9227465, 1.618033988749908700, 0.047
35, 14930352, 1.618033988749889600, 0.078
36, 24157817, 1.618033988749896900, 0.141
37, 39088169, 1.618033988749894000, 0.234
38, 63245986, 1.618033988749895100, 0.359
39, 102334155, 1.618033988749894700, 0.624
40, 165580141, 1.618033988749894900, 0.998
41, 267914296, 1.618033988749894900, 1.591
42, 433494437, 1.618033988749894900, 2.590
43, 701408733, 1.618033988749894900, 4.212
44, 1134903170, 1.618033988749894900, 6.817
45, 1836311903, 1.618033988749894900, 10.920
46, -1323752223, -0.720875479180510430, 17.660
.
.
.
*/
// --------------------------------------------------------
#include <cstdlib>
#include <iostream>
using namespace std;
// ------------------------------------
#include "ccc.h"
int f(int no)
{
// 0, 1, 2, 3
// 1, 1, 2, 3, . . .
if (no <= 1) {
return 1;
}
else {
return (f(no-2) + f(no-1));
}
}// end of f()
// ------------------------------------
int main(int argc, char *argv[])
{
int n1, n2, no, t1;
double r1, dt;
for (no=1;no<=60;no++) {
n1= f(no);
time1(&t1);
n2= f(no-1);
time2(t1, &dt);
r1= ((double) n1)/((double) n2);
printf("%3ld, %12ld, %22.18lf, %7.3lf \n",
no, n1, r1, dt);
}
pause();
return 0;
}// end of main()