Fibonacci數(shù)列<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

v? Fibonacci背景知識

斐波那契:比薩德列奧納多，又稱斐波那契（Leonardo Pisano ,Fibonacci, Leonardo Bigollo，1175年-1250年），意大利數(shù)學(xué)家，西方第一個研究斐波那契數(shù)，并將現(xiàn)代書寫數(shù)和乘數(shù)的位值表示法系統(tǒng)引入歐洲。

v? Fibonacci 引出

斐波那契在《算盤書》中提出了一個有趣的兔子問題：一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔都不死，那么一年以后可以繁殖多少對兔子？

我們不妨拿新出生的一對小兔子分析一下：第一個月小兔子沒有繁殖能力，所以還是一對；兩個月后，生下一對小兔總數(shù)共有兩對； 三個月以后，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對；

類推表如下：

?????????????? 經(jīng)過月數(shù)	0	1	2	3	4	5	6	7	8	9	10	11	12
?????????????? 幼仔對數(shù)	1	0	1	1	2	3	5	8	13	21	34	55	89
?????????????? 成兔對數(shù)	0	1	1	2	3	5	8	13	21	34	55	89	144
?????????????? 總體對數(shù)	1	1	2	3	5	8	13	21	34	55	89	144	233

?

?????? 從一年的總體對數(shù)中可以發(fā)現(xiàn),從第二個月開始，其數(shù)量是前兩個月的數(shù)量的和，所以得出遞推公式為：

F(n)=F(n-1)+F(n-2)(n>=2)???? (1)

v? Fibonacci數(shù)列的性質(zhì)

1． F(n)=F(n-1)+F(n-2)

2.? 其任意一項平方數(shù)為其前項和后項的積加一或者減一

?? ?F(n)*F(n)=F(n-1)*F(n+1)+/-1

3.任取相鄰的四個斐波那契數(shù)，中間兩數(shù)之積（內(nèi)積）與兩邊兩數(shù)之積（外積）相差1

v? Fibonacci數(shù)列的程序?qū)崿F(xiàn)

1.? 遞歸實現(xiàn)?

static int Fib1(int n)
????????????????{
????????????????????????int []result = new int[]{ 0, 1 };
????????????????????????if(n<2) return result[n];
????????????????????????return Fib1(n-1)+Fib1(n-2);
????????????????}
2． 非遞歸實現(xiàn)(迭代法)

static int Fib2(int n)????
????????????????{
????????????????????????int[] result = new int[] { 0, 1 };

????????????????????????if (n < 2) return result[n];

????????????????????????int n1=0,n2=1,retTemp=0;

????????????????????????for (int i = 2; i <=n; i++)
????????????????????????{
????????????????????????????????retTemp = n1 + n2;
????????????????????????????????n1 = n2;
????????????????????????????????n2 = retTemp;
????????????????????????}
????????????????????????return retTemp;
????????????????}
2． 創(chuàng)新法(矩陣公式)

存在一個Fibonacii的矩陣恒等式，其形式如下所示：

??????? 對于F(n)來說，只需要求右邊的矩陣的n次冪，然后F(n-1)即為所求結(jié)果的第一行第一列的值。

?????? 對于右邊的矩陣的n次冪可以將n化為：

public static Matrix MatrixPower(int n)
????????????????????????{
????????????????????????????????Debug.Assert(n > 0);
????????????????????????????????Matrix matrix = new Matrix();

????????????????????????????????if (n == 1)
????????????????????????????????{
????????????????????????????????????????return matrix=new Matrix(1,1,1,0);
????????????????????????????????}
????????????????????????????????if(n%2==0)
????????????????????????????????{
????????????????????????????????????????matrix = MatrixPower(n / 2);
????????????????????????????????????????matrix = MatrixMuti(matrix, matrix);????
????????????????????????????????}
????????????????????????????????if (n % 2 == 1)
????????????????????????????????{
????????????????????????????????????????matrix = MatrixPower((n-1) / 2);
????????????????????????????????????????matrix = MatrixMuti(matrix, matrix);
????????????????????????????????????????matrix = MatrixMuti(matrix, new Matrix(1, 1, 1, 0));
????????????????????????????????}
????????????????????????????????return matrix;
????????????????????????}
? 利用Fibonacci矩陣恒等式方法就Fibonacci數(shù)列： internal class MaxtrixBy
????????????????{

????????????????????????public struct Matrix
????????????????????????{
????????????????????????????????public int m00, m01, m10, m11;
????????????????????????????????public Matrix(int _m00, int _m01, int _m10, int _m11)????
????????????????????????????????{
????????????????????????????????????????m00 = _m00;
????????????????????????????????????????m01 = _m01;
????????????????????????????????????????m10 = _m10;
????????????????????????????????????????m11 = _m11;
????????????????????????????????}
????????????????????????}
????????????????????????public static Matrix MatrixMuti(Matrix m1, Matrix m2)
????????????????????????{
????????????????????????????????return new Matrix(m1.m00 * m2.m00 + m1.m10 * m2.m01, m1.m00 * m2.m10 + m1.m10 * m2.m11,
????????????????????????????????????????????????????????????m1.m10 * m2.m00 + m1.m11 * m2.m01, m1.m10 * m2.m00 + m1.m11 * m2.m11);
????????????????????????????????????????????????????????????
????????????????????????}
????
????????????????????????public static Matrix MatrixPower(int n)
????????????????????????{
????????????????????????????????Debug.Assert(n > 0);
????????????????????????????????Matrix matrix = new Matrix();

????????????????????????????????if (n == 1)
????????????????????????????????{
????????????????????????????????????????return matrix=new Matrix(1,1,1,0);
????????????????????????????????}
????????????????????????????????if(n%2==0)
????????????????????????????????{
????????????????????????????????????????matrix = MatrixPower(n / 2);
????????????????????????????????????????matrix = MatrixMuti(matrix, matrix);????
????????????????????????????????}
????????????????????????????????if (n % 2 == 1)
????????????????????????????????{
????????????????????????????????????????matrix = MatrixPower((n-1) / 2);
????????????????????????????????????????matrix = MatrixMuti(matrix, matrix);
????????????????????????????????????????matrix = MatrixMuti(matrix, new Matrix(1, 1, 1, 0));
????????????????????????????????}
????????????????????????????????return matrix;
????????????????????????}

????????????????????????public static int Fib3(int n)
????????????????????????{
????????????????????????????????int[] result = new int[] { 0, 1 };
????????????????????????????????if(n<2) return result[n];
???????????????????????????? // MaxtrixBy matrixby=new MaxtrixBy();
????????????????????????????????Matrix m = MaxtrixBy.MatrixPower(n - 1);
????????????????????????????????return m.m00;
????????????????????????}
????????????????}
3． 運行效率分析

?	遞歸表示	迭代法	矩陣恒等式
時間復(fù)雜度	O(2 exp n)	O(n)	O(logn)

轉(zhuǎn)載于:https://blog.51cto.com/jizhonglee/1151077

總結(jié)

以上是生活随笔為你收集整理的Fibonacii数列，兔子问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。