网站开发 行业动态,上海到北京机票,苏州网页设计电话,建设网银登录网站斐波那契数列
先来简单介绍一下斐波那契数列#xff1a; 斐波那契数列是指这样一个数列#xff1a;1#xff0c;1#xff0c;2#xff0c;3#xff0c;5#xff0c;8#xff0c;13#xff0c;21#xff0c;34#xff0c;55#xff0c;89……这个数列从第3项开始 斐波那契数列是指这样一个数列1123581321345589……这个数列从第3项开始 每一项都等于前两项之和。
现在要求斐波那契数列的第n项如果用Java代码层面来讲就是下面这样。
一个for循环声明一个变量累加到第n项即可。 O ( N ) O(N) O(N)的时间复杂度。但这并不是最优解最优解的时间复杂度是 O ( L o g N ) O(LogN) O(LogN)。
最优解怎么得到的是根据上面斐波那契数列的递推式 F ( n ) F ( n − 1 ) F ( n − 2 ) F(n) F(n - 1) F(n - 2) F(n)F(n−1)F(n−2)
这是一项严格的递推式在告诉初始值的情况下如果后面的每一项都按照严格的递推式可以推出来那都有 O ( L o g N ) O(LogN) O(LogN)的方法。
那什么没有 O ( L o g N ) O(LogN) O(LogN)的方法呢 比如说有一个左数列。得到这个左数列的第n项。
给定的信息比如有一个 boolean[] b {T , T , F , F , T , T , T}。 对于左数列来说第一项是1第二项也是1之后的每一项根据是T还是F来进行表达。 如果当前项是 F 则 F ( n ) F ( n − 1 ) F(n) F(n - 1) F(n)F(n−1) 如果当前项是 T则 F ( n ) F ( n − 1 ) F ( n − 2 ) F(n) F(n - 1) F(n - 2) F(n)F(n−1)F(n−2)。以此来决定下一项值是什么。
所以根据公式第三项 1第四项 1第五项 2 以此类推…。这种就没有 O ( L o g N ) O(LogN) O(LogN)的方法因为会根据不同的条件进行条件转移。
斐波那契数列就是没有条件转移的严格递推式。这种都有 O ( L o g N ) O(LogN) O(LogN)的方法。 线性代数
如果 F ( n ) F ( n − 1 ) F ( n − 2 ) F(n) F(n - 1) F(n - 2) F(n)F(n−1)F(n−2)第n项和 F(n - 1) 和 F(n - 2)是严格关系那在公式中减的最多的常数是2那就可以说它是一个二阶递推依然是以斐波那契数列来举例。
已知斐波那契数列的第一项 F(1) 1第二项 F(2) 1那一定会存在下面这个关系 ∣ F 3 , F 2 ∣ ∣ F 2 , F 1 ∣ × ∣ a b c d ∣ |F_3,F_2| |F_2,F_1| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right| ∣F3,F2∣∣F2,F1∣× acbd 没有为什么龟腚
同样的斐波那契数列的第四项F(4)和第三项F(3) 的行列式一定等于下面的式子(abcd为相同的2 * 2矩阵)。 ∣ F 4 , F 3 ∣ ∣ F 3 , F 2 ∣ × ∣ a b c d ∣ |F_4,F_3| |F_3,F_2| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right| ∣F4,F3∣∣F3,F2∣× acbd
那这个2 * 2矩阵的abcd是什么呢 接下来我们算一下
因为斐波那契数列的前几项我们都是已知的所以可以先列出来 F(1) 1, F(2) 1F(3) 2F(4) 3接下来我们带入到式子中。 ∣ F 3 , F 2 ∣ ∣ F 2 , F 1 ∣ × ∣ a b c d ∣ − ∣ 2 , 1 ∣ ∣ 1 , 1 ∣ × ∣ a b c d ∣ |F_3,F_2| |F_2,F_1| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right| -|2,1| |1,1| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right| ∣F3,F2∣∣F2,F1∣× acbd −∣2,1∣∣1,1∣× acbd
矩阵乘法 F 2 ∗ a F 1 ∗ c F 3 F_2 * a F_1 * c F_3 F2∗aF1∗cF3 F 2 ∗ b F 1 ∗ d F 2 F_2 * b F_1 * d F_2 F2∗bF1∗dF2
带入进来就是 { a c 2 b d 1 (1) \begin{cases} a c 2 \\ b d 1 \end{cases} \tag{1} {ac2bd1(1) 一个式子不够求不出来再次带入下一个公式 ∣ F 4 , F 3 ∣ ∣ F 3 , F 2 ∣ × ∣ a b c d ∣ − ∣ 3 , 2 ∣ ∣ 2 , 1 ∣ × ∣ a b c d ∣ |F_4,F_3| |F_3,F_2| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right|-|3,2| |2,1| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right| ∣F4,F3∣∣F3,F2∣× acbd −∣3,2∣∣2,1∣× acbd
矩阵乘法 F 3 ∗ a F 2 ∗ c F 4 F_3 * a F_2 * c F_4 F3∗aF2∗cF4 F 3 ∗ b F 2 ∗ d F 3 F_3 * b F_2 * d F_3 F3∗bF2∗dF3
带入进来就是 { 2 a c 3 2 b d 2 (2) \begin{cases} 2a c 3 \\ 2b d 2 \end{cases} \tag{2} {2ac32bd2(2) 求出a 1 , b 1 c 1 d 0
再次带入验证一下 ∣ F 5 , F 4 ∣ ∣ F 4 , F 3 ∣ × ∣ a b c d ∣ − ∣ F 5 , F 4 ∣ ∣ 3 , 2 ∣ × ∣ 1 1 1 0 ∣ |F_5,F_4| |F_4,F_3| \times\left| \begin{matrix} a b \\ c d \end{matrix} \right|-|F_5,F_4| |3,2| \times\left| \begin{matrix} 1 1 \\ 1 0 \end{matrix} \right| ∣F5,F4∣∣F4,F3∣× acbd −∣F5,F4∣∣3,2∣× 1110
矩阵乘法 F 4 ∗ a F 3 ∗ c F 5 F_4 * a F_3 * c F_5 F4∗aF3∗cF5 F 4 ∗ b F 3 ∗ d F 4 F_4 * b F_3 * d F_4 F4∗bF3∗dF4 3 2 5 3 2 5 325 3 0 3 3 0 3 303 求出F(5) 5 F(4) 3。 证明我们求出的abcd是对的。
根据上面的公式可以列出 { ∣ F 3 , F 2 ∣ ∣ F 2 , F 1 ∣ × ∣ 矩阵 ∣ ∣ F 4 , F 3 ∣ ∣ F 3 , F 2 ∣ × ∣ 矩阵 ∣ ∣ F 5 , F 4 ∣ ∣ F 4 , F 3 ∣ × ∣ 矩阵 ∣ . . . . . ∣ F n , F n − 1 ∣ ∣ F n − 1 , F n − 2 ∣ × ∣ 矩阵 ∣ \begin{cases} |F_3,F_2| |F_2,F_1| \times |矩阵|\\ |F_4,F_3| |F_3,F_2| \times|矩阵|\\ |F_5,F_4| |F_4,F_3| \times |矩阵|\\ .....\\ |F_n,F_{n-1}| |F_{n-1},F_{n-2}| \times|矩阵| \end{cases} ⎩ ⎨ ⎧∣F3,F2∣∣F2,F1∣×∣矩阵∣∣F4,F3∣∣F3,F2∣×∣矩阵∣∣F5,F4∣∣F4,F3∣×∣矩阵∣.....∣Fn,Fn−1∣∣Fn−1,Fn−2∣×∣矩阵∣
推导一下将相同的值带入可得出 ∣ F n , F n − 1 ∣ ∣ F 2 , F 1 ∣ × ∣ 相同矩阵 ∣ n − 2 |F_n,F_{n-1}| |F_2,F_1| \times\left| \begin{matrix} 相同矩阵 \end{matrix} \right|^{n-2} ∣Fn,Fn−1∣∣F2,F1∣× 相同矩阵 n−2
再次回到求斐波那契数列第n项的问题。
我们目前已经推导出了最后的公式那想要求斐波那契数列第n项的关键点是不是在于求矩阵的n - 2次方只要矩阵的某次方算的足够快第n项是不是求的就足够快 如何让一个数的次方算的足够快
在求得矩阵某次方之前我们先来看看如何让一个普通的数比如说 1 0 75 10^{75} 1075这个数算的足够快
先来搞定这个数相同的逻辑用在矩阵上那同样矩阵也会非常快
利用二进制 1 0 75 10^{75} 1075如果是75个10相乘那这是一个 O ( N ) O(N) O(N)的问题不够快。
首先将幂数75拆分成对应的二进制为0100101164 8 2 1 再让变量 t 1 0 1 10^1 101t不断的和自己相乘变成 1 0 2 10^2 102、 1 0 4 10^4 104、 1 0 8 10^8 108… t 不断的追赶75不断的和自己相乘那追赶75的一共追赶多少次 O ( L o g N ) O(LogN) O(LogN)次。
接下来将 变量t 和75的二进制进行融合。
t 没和自己相乘之前是 1 0 1 10^1 101我们总的结果 result一开始是1这时候看01001011二进制中1的位置是有值的说明这个值是我结果需要的那就用 result * t ( 1 0 1 10^1 101)
再接着往下来01001011中2的位置也是1代表这个位置也是结果需要的将此时的 t 也乘进来。 继续往下此时来到了01001011中的44的二进制为0代表结果不被需要不需要就不乘这个数t继续和自己相乘。 继续向下来到了01001011中的8。同样也是被需要的将 1 0 8 10^8 108加到结果中。 依次类推继续向下16 32 对应的2进制位置都为0都不需要这两个数直到来到了 1 0 64 10^{64} 1064次方将需要的数都乘到结果中就是最终答案。 t 在不断和自己相乘的过程中按位判断要不要添加到结果中去。
为什么这么做
其实追根究底是一个二分的过程只不过自己二分的过程没有二进制提供的优良。 求一个数字的n次方我们已经解决了 那矩阵呢 同理
求一个矩阵的75次方
将矩阵的幂数进行二进制拆分那在求 1 0 75 10^{75} 1075时先搞了result 1如果这个数被需要就乘到结果中那换到矩阵中是不是只要将result 的 1 变成矩阵中代表 1 的数就行了。t 同样也是变成 矩阵的 1次方 矩阵的2次方不断和自己相乘。
单位矩阵
单位矩阵中对角线上都是1剩下位置都是0就代表着1 。 ∣ 1 0 0 0 1 0 0 0 1 ∣ \left| \begin{matrix} 1 0 0 \\ 0 1 0 \\ 0 0 1 \end{matrix} \right| 100010001
矩阵乘法 当矩阵A的列数等于矩阵B的行数时A与B可以相乘。 矩阵C的行数等于矩阵A的行数C的列数等于B的列数。 乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和
所以A是一个 m × n 的矩阵B是一个 n × p 的矩阵C是一个 m × p 的矩阵。 ∣ 1 2 3 4 ∣ ∗ ∣ 5 6 7 8 ∣ ∣ 1 ∗ 5 2 ∗ 7 1 ∗ 6 2 ∗ 8 3 ∗ 5 4 ∗ 7 3 ∗ 6 4 ∗ 8 ∣ \left| \begin{matrix} 1 2 \\ 3 4 \\ \end{matrix} \right| * \left| \begin{matrix} 5 6 \\ 7 8 \end{matrix} \right| \left| \begin{matrix} 1 * 5 2 * 7 1 * 6 2* 8 \\ 3 * 5 4 * 7 3 * 6 4 * 8 \end{matrix} \right| 1324 ∗ 5768 1∗52∗73∗54∗71∗62∗83∗64∗8
代码 因为是两个矩阵相乘2 * 2的矩阵相得到的也一定是个2 * 2的矩阵要求的是第F(n)项根据上面的公式可以得出 F n F 1 ∗ a F 2 ∗ c Fn F_1 * a F_ 2 * c FnF1∗aF2∗c 。 F(1) 1 F2 (1) 所以我们最终结果只需要 res[0][0] res[1][0] 即可。 public static int f2(int n){if (n 0){return 0;}if (n 1 || n 2){return 1;}//斐波那契数列的单位矩阵int[][] base {{1,1},{1,0}};int[][] res matrixPower(base,n - 2);return res[0][0] res[1][0];}public static int[][] matrixPower(int[][] m, int p) {int[][] res new int[m.length][m[0].length];for (int i 0; i res.length; i) {res[i][i] 1;}// res 矩阵中的1int[][] t m;// 矩阵1次方for (; p ! 0; p 1) {if ((p 1) ! 0) {res product(res, t);}t product(t, t);}return res;}// 两个矩阵乘完之后的结果返回public static int[][] product(int[][] a, int[][] b) {int n a.length;int m b[0].length;int k a[0].length; // a的列数同时也是b的行数int[][] ans new int[n][m];for(int i 0 ; i n; i) {for(int j 0 ; j m;j) {for(int c 0; c k; c) {ans[i][j] a[i][c] * b[c][j];}}}return ans;}
