矩阵快速幂
2022/3/19 23:39:25
本文主要是介绍矩阵快速幂,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一. 斐波那契数列引出矩阵快速幂技巧
斐波那契数列的递推式:F(N) = F(N-1) + F(N-2),二阶递推式
计算矩阵的n-2次方时间复杂度为O(logN)
class Solution { public int fib(int n) { if(n == 0)return 0; if(n== 1 || n==2)return 1; //假设矩阵从1和2开始,F1=1,F2=1 int times = n-2; int[][] base = new int[2][2]; base[0][1] =1; base[0][0] = 1; base[1][0] = 1; int[][] res = mutiply(base, times); return 1*res[0][0] + 1*res[1][0]; } public int[][] mutiply(int[][] base, int times){ int[][] temp = base;//基 int[][] res = new int[2][2];//先让返回结果等于单位阵 res[0][0] = 1; res[1][1] = 1; for(; times != 0; times >>= 1){ if((times & 1) == 1){ res = help(res, temp); } temp = help(temp, temp); } return res; } //矩阵自乘 public int[][] help(int[][] a, int[][] b){ int[][] res = new int[2][2]; for(int i = 0; i < 2; i++){//遍历a的行 for(int j = 0; j < 2; j++){//遍历b的列 for(int k = 0; k < 2; k++){ res[i][j] += a[i][k] * b[k][j]; } } } return res; } }
二. 推广到i阶递推式
i阶递推公式都可以通过矩阵快速幂技巧将时间复杂度降为O(logN)
题目一:达标字符串
尝试:
递推函数:F(i),还有i个位置的字符需要填写,返回达标字符串的个数,默认第i-1个位置填写1
1)第k个位置填写1,F(i-1)
2)第k个位置填写0,则第k+1个位置必须填写1,F(i-2)
得到递推公式 F(i) = F(i-1) + F(i-2)
题目二:母牛繁殖问题
一:A
二:A B
三:A B C
四:A B C D
五:A B C D E F
递推式:F(N) = F(N-1) + F(N-3)
F(N-3)表示第N年已经成熟的牛的个数
public static int method(int n) { int[][] base = new int[3][3]; //[0 1 0] //[2 0 1] //[0 0 0] base[0][1] = 1; base[1][0] = 2; base[1][2] = 1; int[][] res = multiply(base, n-3); return 3 * res[0][0] + 2 * res[1][0] + res[2][0]; } public static int[][] multiply(int[][] base, int times){ int[][] res = new int[3][3]; //单位阵 res[0][0]=1; res[1][1]=1; res[2][2]=1; for(;times != 0; times >>= 1){ if((times & 1) == 1){ res = help(res, base);//res * base } base = help(base, base); } return res; } public static int[][] help(int[][] a, int[][] b){ int[][] res = new int[3][3]; for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ for(int k = 0; k < 3; k++){ res[i][j] += a[i][k] * b[k][j]; } } } return res; }
题目三:铺瓷砖问题
假设地板规模为2 * N,一块瓷砖的大小为 1*2,一共有多少种铺瓷砖的方法
F(n) = F(n-1) + F(n-2)
这篇关于矩阵快速幂的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?