Fibonacci斐波那契数列,也叫兔子数列,从第3项开始,每一项是前2项之和。递归定义如下:
F
i
b
(
n
)
=
{
0
,
n
=
0
1
,
n
=
1
F
i
b
(
n
−
1
)
+
F
i
b
(
n
−
2
)
,
n
>
=
2
Fib(n)=\left\{\begin{array}{l} \qquad \qquad 0\qquad \qquad \qquad ,n=0 \\ \qquad \qquad 1\qquad \qquad \qquad , n=1 \\ Fib(n-1)+Fib(n-2), n>=2 \end{array}\right.
Fib(n)=⎩⎨⎧0,n=01,n=1Fib(n−1)+Fib(n−2),n>=2
Fibonacci斐波那契数列的前几项,依次为:0,1,1,2,3,5,8,21,34,…
斐波那契数列,有通项公式,如下:
F i b ( n ) = [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] / 5 \mathrm{Fib}(n)=\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] / \sqrt{5} Fib(n)=[(21+5 )n−(21−5 )n]/5
斐波那契数列的计算方法,有很多种,每种方法的时间复杂度、空间复杂度相差较大,具体如下:
算法对比 | 时间复杂度 | 空间复杂度 |
---|---|---|
普通递归 | O(2^n) | O(n) |
尾递归 | O(n) | O(n) |
使用循环 | O(n) | O(1) |
通项公式 | O(logn) | O(1) |
//fib.cpp
#include <iostream> #include <iomanip> #include <cmath> using namespace std; //普通递归实现 long Fib(long n) { if (n < 2) return n; else return Fib(n - 1) + Fib(n - 2); } //尾递归实现 long Fib2(long first,long second,long n) { if (n == 0) return 0; if (n == 1 || n == 2) return 1; if (n == 3) return first + second; return Fib2(second, first + second, n - 1); } //循环实现 long Fib3(long n) { if (n == 0) return 0; long first = 1, second = 1; long ret = 0; for (long i = 3; i <= n; i++){ ret = first + second; first = second; second = ret; } return second; } #define Half_Sqrt5 1.1180339887498948482045868343656 #define All_Sqrt5 2.2360679774997896964091736687313 //用通项公式实现 long Fib4(long n) { if (n < 2) { return n; } return (long)(round((pow(0.5+Half_Sqrt5,n) - pow(0.5-Half_Sqrt5,n))/All_Sqrt5)); } int main(){ //---- fib(6) = 8 int Fib6a = Fib(6); cout << "Fib6a= " << Fib6a << endl; int Fib6b = Fib2(1,1,6); cout << "Fib6b= " << Fib6b << endl; int Fib6c = Fib3(6); cout << "Fib6c= " << Fib6c << endl; int Fib6d = Fib4(6); cout << "Fib6d= " << Fib6d << endl; system("pause"); return 0; }
效果如下:
//fib_test.go
package yufa import ( "fmt" "math" "testing" ) //普通递归实现 func Fib(n int64) (res int64) { if n < 2 { return n } else { return Fib(n-1)+Fib(n-2) } } //尾递归实现 func Fib2(first,second,n int64)(res int64){ if n == 0 { return 0 } else if n==1 || n==2 { return 1 } else if n== 3 { return first+second } return Fib2(second, first+second, n-1) } //循环实现 func Fib3(n int64) (res int64) { if n == 0 { return 0 } var first,second int64 = 1,1 var ret,i int64 = 0,0 for i=3; i<=n;i++ { ret = first + second first = second second = ret } return second } const ( Half_Sqrt5 = 1.1180339887498948482045868343656 All_Sqrt5 = 2.2360679774997896964091736687313 ) //四舍五入 func round(x float64) (res int64) { return int64(math.Floor(x+0.5)) } //用通项公式实现 func Fib4(n int64) (res int64) { if n <= 1 { return n } res = round((math.Pow(0.5+Half_Sqrt5,float64(n)) - math.Pow(0.5-Half_Sqrt5,float64(n)))/All_Sqrt5) return res } func TestFib(t *testing.T) { var Fib6a int64 = Fib(6) var Fib6b int64 = Fib2(1,1,6) var Fib6c int64 = Fib3(6) var Fib6d int64 = Fib4(6) fmt.Println("Fib6a= ",Fib6a) fmt.Println("Fib6b= ",Fib6b) fmt.Println("Fib6c= ",Fib6c) fmt.Println("Fib6d= ",Fib6d) }
效果如下:
[1] 力扣.斐波那契数列的6种解法.2019
[2] latex公式编辑