【背景】
【思路1-递归】
- int Fibonacci(int n){
- if(n <= 2){
- return n;
- }
- return Fibonacci(n - 1) + Fibonacci(n - 2);
- }
进一步优化：
当n增大到一定数值，Fibonacci数列值会溢出，并且花费时间很长。
- long long Fibonacci(int n){
- if(n <= 2){
- return n;
- }
- return Fibonacci(n - 1) + Fibonacci(n - 2);
- }
【思路2-递推关系式的优化】
- long long Fibonacci(int n){
- long long* Fibonacci = (long long*)malloc(sizeof(long long)*(n+1));
- Fibonacci[0] = 0;
- Fibonacci[1] = 1;
- for(int i = 2;i <= n;i++){
- Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];
- }
- return Fibonacci[n];
- }
该思路的另一种实现方法：
- long long Fibonacci(int n){
- int i;
- long long fibonacciA = 0;
- long long fibonacciB = 1;
- long long fibonacciC;
- if(n == 0){
- return 0;
- }
- else if(n == 1){
- return 1;
- }
- for(i = 2;i <= n;i++){
- fibonacciC = fibonacciA + fibonacciB;
- fibonacciA = fibonacciB;
- fibonacciB = fibonacciC;
- }
- return fibonacciC;
- }
【思路3-求解通项公式】
- int Fibonacci(int n) {
- double s = sqrt(5);
-
- return floor((pow((1+s)/2, n) - pow((1-s)/2, n))/s + 0.5);
- }
当n增大到一定数值，Fibonacci数列值会溢出。因为floor返回小于或者等于指定表达式的最大整数
【思路4-分支策略】
- #include <iostream>
- #include <malloc.h>
- #include <stdio.h>
- using namespace std;
-
- void MatrixMulti(long long matrix[2][2],long long matrix2[2][2]){
- long long a = matrix[0][0] * matrix2[0][0] + matrix[0][1] * matrix2[1][0];
- long long b = matrix[0][0] * matrix2[0][1] + matrix[0][1] * matrix2[1][1];
- long long c = matrix[1][0] * matrix2[0][0] + matrix[1][1] * matrix2[1][0];
- long long d = matrix[1][0] * matrix2[0][1] + matrix[1][1] * matrix2[1][1];
- matrix[0][0] = a;
- matrix[0][1] = b;
- matrix[1][0] = c;
- matrix[1][1] = d;
- }
-
- long long Fibonacci(int value){
- if(value == 0){
- return 0;
- }
- long long A[2][2] = {1,1,1,0};
-
- long long Matrix[2][2] = {1,0,1,0};
- int n = value - 1;
- for(; n ;n >>= 1){
-
- if(n&1){
- MatrixMulti(Matrix,A);
- }
- MatrixMulti(A,A);
- }
- return Matrix[0][0];
- }
-
- int main() {
- int i,n,height;
- while(scanf("%d",&n) != EOF){
- long long result;
- for(i = 0;i <= n;i++){
- result = Fibonacci(i);
- printf("%lld\n",result);
- }
- }
- return 0;
- }
该思路另一种解析：
编程之美之斐波那契数列
原文：http://www.cnblogs.com/ghostll/p/3532767.html
