斐波那契数列 (Fibonacci)
又称黄金分割数列，因数学家列昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：
1、1、2、3、5、8、13、21、34……
在数学上，斐波那契数列以如下被以递推的方法定义：
F(1) = 1，F(2) = 1 F(n) = F(n - 1) + F(n - 2) (n ≥ 3，n ∈ N*)
简单来讲就是：数列中第3项开始，任一项的值都等于它前两项之和。
用数列定义，可以计算出各种 unsigned 无符号整数类型在溢出之前最多能输出到数列的第几项？ 答案是24、47、93：
#include <iostream> #include <limits> using namespace std; #define outFibonacci(nType) { int i = 1;\ while (i++)\ if (Fibonacci<nType>(i+1)==Fibonacci<nType>(i+2)){\ cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\ break;\ }\ cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\ } template<typename _T> _T Fibonacci(_T n){ _T f, f1, f2; f = f1 = f2 = 1; for (auto i=3; i<=n; ++i){ f = f1 + f2; if (f<f2){ //设置溢出条件 f=-1; break; } f1 = f2; f2 = f; } return f; } int main(void) { outFibonacci(unsigned short); outFibonacci(unsigned int); outFibonacci(unsigned long); //与上一类型输出相同 outFibonacci(unsigned long long); outFibonacci(size_t); //在我的系统上与上一类型输出相同 return 0; }
输出结果：
F(24) = 46368 Max Num = 65535 F(47) = 2971215073 Max Num = 4294967295 F(47) = 2971215073 Max Num = 4294967295 F(93) = 12200160415121876738 Max Num = 18446744073709551615 F(93) = 12200160415121876738 Max Num = 18446744073709551615 --------------------------------
Process exited after 0.6217 seconds with return value 0
请按任意键继续. . .
注：上述代码中有一个函数 numeric_limits<TypeName>::max() 计算数据类型的最大值，需要头文件#include <limits>；numeric_limits<TypeName>::min() 则是计算数据类型的最小值。
