如下图，通常大家都用公式一来计算斐波那契数列的，其实还有通项公式二：一个非常牛叉的内比公式，号称是用无理数表示有理数(且是整数)的典范。
只一行代码能计算数列全部项
预定义两个宏常量，使代码更简洁些：
#include <iostream> #include <iomanip> #include <cmath> using namespace std; #define M_SQRT5 2.2360679774997896964091736687313 #define M_1pSQRT5_2 1.6180339887498948482045868343656 size_t Fibo(size_t n) { return (size_t)round((pow(M_1pSQRT5_2,n)-pow(1-M_1pSQRT5_2,n))/M_SQRT5); } size_t fibo(size_t n) //引入定义式作比较 { size_t f, f1, f2; f = f1 = f2 = 1; for (auto i=3; i<=n; ++i){ f = f1 + f2; if (f<f2){ //设置溢出条件 f=0; break; } f1 = f2; f2 = f; } return f; } int main(void) { for (long n=1;n<=100;n++) cout<<n<<"\t= "<<setprecision(18)<<Fibo(n)<<"\t"<<fibo(n) <<"\t"<<(Fibo(n)==fibo(n)?"True":"False")<<endl; return 0; }
测试结果： 1 = 1 1 True 2 = 1 1 True 3 = 2 2 True 4 = 3 3 True 5 = 5 5 True 6 = 8 8 True 7 = 13 13 True 8 = 21 21 True 9 = 34 34 True 10 = 55 55 True 11 = 89 89 True 12 = 144 144 True 13 = 233 233 True 14 = 377 377 True 15 = 610 610 True 16 = 987 987 True 17 = 1597 1597 True 18 = 2584 2584 True 19 = 4181 4181 True 20 = 6765 6765 True 21 = 10946 10946 True 22 = 17711 17711 True 23 = 28657 28657 True 24 = 46368 46368 True 25 = 75025 75025 True 26 = 121393 121393 True 27 = 196418 196418 True 28 = 317811 317811 True 29 = 514229 514229 True 30 = 832040 832040 True 31 = 1346269 1346269 True 32 = 2178309 2178309 True 33 = 3524578 3524578 True 34 = 5702887 5702887 True 35 = 9227465 9227465 True 36 = 14930352 14930352 True 37 = 24157817 24157817 True 38 = 39088169 39088169 True 39 = 63245986 63245986 True 40 = 102334155 102334155 True 41 = 165580141 165580141 True 42 = 267914296 267914296 True 43 = 433494437 433494437 True 44 = 701408733 701408733 True 45 = 1134903170 1134903170 True 46 = 1836311903 1836311903 True 47 = 2971215073 2971215073 True 48 = 4807526976 4807526976 True 49 = 7778742049 7778742049 True 50 = 12586269025 12586269025 True 51 = 20365011074 20365011074 True 52 = 32951280099 32951280099 True 53 = 53316291173 53316291173 True 54 = 86267571272 86267571272 True 55 = 139583862445 139583862445 True 56 = 225851433717 225851433717 True 57 = 365435296162 365435296162 True 58 = 591286729879 591286729879 True 59 = 956722026041 956722026041 True 60 = 1548008755920 1548008755920 True 61 = 2504730781961 2504730781961 True 62 = 4052739537881 4052739537881 True 63 = 6557470319842 6557470319842 True 64 = 10610209857723 10610209857723 True 65 = 17167680177565 17167680177565 True 66 = 27777890035288 27777890035288 True 67 = 44945570212853 44945570212853 True 68 = 72723460248141 72723460248141 True 69 = 117669030460994 117669030460994 True 70 = 190392490709135 190392490709135 True 71 = 308061521170129 308061521170129 True 72 = 498454011879264 498454011879264 True 73 = 806515533049393 806515533049393 True 74 = 1304969544928657 1304969544928657 True 75 = 2111485077978050 2111485077978050 True 76 = 3416454622906706 3416454622906707 False 77 = 5527939700884755 5527939700884757 False 78 = 8944394323791463 8944394323791464 False 79 = 14472334024676218 14472334024676221 False 80 = 23416728348467676 23416728348467685 False 81 = 37889062373143896 37889062373143906 False 82 = 61305790721611584 61305790721611591 False 83 = 99194853094755488 99194853094755497 False 84 = 160500643816367040 160500643816367088 False 85 = 259695496911122528 259695496911122585 False 86 = 420196140727489600 420196140727489673 False 87 = 679891637638612096 679891637638612258 False 88 = 1100087778366101632 1100087778366101931 False 89 = 1779979416004713728 1779979416004714189 False 90 = 2880067194370815488 2880067194370816120 False 91 = 4660046610375529472 4660046610375530309 False 92 = 7540113804746344448 7540113804746346429 False 93 = 12200160415121872896 12200160415121876738 False 94 = 0 0 True 95 = 0 0 True 96 = 0 0 True 97 = 0 0 True 98 = 0 0 True 99 = 0 0 True 100 = 0 0 True -------------------------------- Process exited after 1.111 seconds with return value 0 请按任意键继续. . .
从运行结果可知：内比公式可以精确计算到第75项，从76项开始long double型的精度不够用了，到94项和递推算法一样溢出。
如不强求返回值一定是整数，可以改成long doubel型函数，一直到1475项溢出；当然只有前75项是精确值，之后的都是约数。
代码修改后，如下：
#include <iostream> #include <iomanip> #include <cmath> using namespace std; #define M_SQRT5 2.2360679774997896964091736687313 #define M_1pSQRT5_2 1.6180339887498948482045868343656 long double Fibo(size_t n) { return round((pow(M_1pSQRT5_2,n)-pow(1-M_1pSQRT5_2,n))/M_SQRT5); } int main(void) { for (long n=1;n<=100;n++) cout<<n<<"\t= "<<setprecision(21)<<Fibo(n)<<endl; cout << "... ..." << endl; for (long n=1470;n<=1480;n++) cout<<n<<"\t= "<<setprecision(21)<<Fibo(n)<<endl; return 0; }
测试结果：
1 = 1
2 = 1
3 = 2
4 = 3
5 = 5
6 = 8
7 = 13
8 = 21
9 = 34
10 = 55
11 = 89
12 = 144
13 = 233
14 = 377
15 = 610
16 = 987
17 = 1597
18 = 2584
19 = 4181
20 = 6765
21 = 10946
22 = 17711
23 = 28657
24 = 46368
25 = 75025
26 = 121393
27 = 196418
28 = 317811
29 = 514229
30 = 832040
31 = 1346269
32 = 2178309
33 = 3524578
34 = 5702887
35 = 9227465
36 = 14930352
37 = 24157817
38 = 39088169
39 = 63245986
40 = 102334155
41 = 165580141
42 = 267914296
43 = 433494437
44 = 701408733
45 = 1134903170
46 = 1836311903
47 = 2971215073
48 = 4807526976
49 = 7778742049
50 = 12586269025
51 = 20365011074
52 = 32951280099
53 = 53316291173
54 = 86267571272
55 = 139583862445
56 = 225851433717
57 = 365435296162
58 = 591286729879
59 = 956722026041
60 = 1548008755920
61 = 2504730781961
62 = 4052739537881
63 = 6557470319842
64 = 10610209857723
65 = 17167680177565
66 = 27777890035288
67 = 44945570212853
68 = 72723460248141
69 = 117669030460994
70 = 190392490709135
71 = 308061521170129
72 = 498454011879264
73 = 806515533049393
74 = 1304969544928657
75 = 2111485077978050
76 = 3416454622906706
77 = 5527939700884755
78 = 8944394323791463
79 = 14472334024676218
80 = 23416728348467676
81 = 37889062373143896
82 = 61305790721611584
83 = 99194853094755488
84 = 160500643816367040
85 = 259695496911122528
86 = 420196140727489600
87 = 679891637638612096
88 = 1100087778366101632
89 = 1779979416004713728
90 = 2880067194370815488
91 = 4660046610375529472
92 = 7540113804746344448
93 = 12200160415121872896
94 = 19740274219868217344
95 = 31940434634990088192
96 = 51680708854858301440
97 = 83621143489848410112
98 = 135301852344706695168
99 = 218922995834555138048
100 = 354224848179261800448
... ...
1470 = 7.28360130920160113816e+306
1471 = 1.17851144787914223854e+307
1472 = 1.90687157879930235235e+307
1473 = 3.08538302667844459089e+307
1474 = 4.99225460547774819064e+307
1475 = inf
1476 = inf
1477 = inf
1478 = inf
1479 = inf
1480 = inf
--------------------------------
Process exited after 1.065 seconds with return value 0
请按任意键继续. . .
long double的精度只够用到73项，但long long的宽度够用到93项，我们可以利用斐波那契数列性质 F(n)=F(n-m)*F(m-1)+F(n-m+1)*F(m) 把用内比公式的函数参数最大值也拉升到93：
#include <string> #include <cmath> #define M_SQRT5 2.2360679774997896964091736687313 #define M_1pSQRT5_2 1.6180339887498948482045868343656 size_t intFib(size_t n) { return n>93?0:(n>75?intFib(n-75)*intFib(74)+intFib(n-74)*intFib(75):(size_t)round((pow(M_1pSQRT5_2,n)-pow(1-M_1pSQRT5_2,n))/M_SQRT5)); } string strFib(size_t n) { return n>93?"":to_string(n>75?intFib(n-75)*intFib(74)+intFib(n-74)*intFib(75):intFib(n)); }
