• 趣学算法|斐波那契 矩阵算法


    14天阅读挑战赛
    努力是为了不平庸~
    算法学习有些时候是枯燥的,这一次,让我们先人一步,趣学算法!

    算法知识点

    矩阵乘法特征:

    1,当矩阵A的列数等于矩阵B的行数时,A与B可以相乘。

    2,矩阵C的行数等于矩阵A的行数,C的列数等于B的列数。

    3,乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。

    算法题目来源

    斐波那契数列又称“斐波那契神奇数列”,是由13世纪的意大利数学家斐波那契提出的,当时是和兔子的繁殖问题有关的,它是一个很重要的数学模型。

    算法题目描述

    有小兔一对,若第二个月它们成年,第三个月生下小兔一对,以后每月生产一对小兔,而所生小兔亦在第二个月成年,第三个月生产另一对小兔,以后亦每月生产小兔一对,假定每产一对小兔必为一雌一雄,且均无死亡,试问一年后共有小兔几对?

    算法推导

    矩阵法斐波那契
    F(1) = F(2) = 1
    F(n) = F(n-1)+F(n-2)
    
    矩阵转化:
    [F(n) F(n-1)] 
    = [F(n-1)+F(n-2) F(n-1)+0]
    = [[1 1] [1 0]]   *  [F(n-1) F(n-2)]
    = [[1 1] [1 0]]   *  [F(n-2)+F(n-3) F(n-3)+0]
    = [[1 1] [1 0]]^2 *  [F(n-2) F(n-3)]
    = [[1 1] [1 0]]^2  *  [F(n-3)+F(n-4) F(n-4)+0]
    = [[1 1] [1 0]]^3 *  [F(n-3) F(n-4)]
    .......
    = [F(2) F(1)] * [[1 1] [1 0]]^(n-2) 
    

    算法实现

    1. /**
    2. * 矩阵法斐波那契
    3. * F(1) = F(2) = 1
    4. * F(n) = F(n-1)+F(n-2)
    5. * [F(n) F(n-1)]
    6. * = [F(n-1)+F(n-2) F(n-1)+0]
    7. * = [[1 1] [1 0]] * [F(n-1) F(n-2)]
    8. * = [[1 1] [1 0]] * [F(n-2)+F(n-3) F(n-3)+0]
    9. * = [[1 1] [1 0]]^2 * [F(n-2) F(n-3)]
    10. * = [[1 1] [1 0]]^2 * [F(n-3)+F(n-4) F(n-4)+0]
    11. * = [[1 1] [1 0]]^3 * [F(n-3) F(n-4)]
    12. * .......
    13. * = [[1 1] [1 0]]^(n-2) * [F(2) F(1)]
    14. * @param n
    15. * @return
    16. */
    17. public static double matrixFbnq(int n){
    18. if(n==1){
    19. return 1;
    20. }
    21. if(n == 2){
    22. return 1;
    23. }
    24. double[][] a = new double[2][2];
    25. a[0][0] = 1;
    26. a[0][1] = 1;
    27. a[1][0] = 1;
    28. a[1][1] = 0;
    29. Matrix matrix = new Matrix(a);
    30. Matrix b = Matrixs.mutils(matrix,n-2);
    31. double[][] c = new double[2][1];
    32. c[0][0] = 1;
    33. c[1][0] = 1;
    34. Matrix e = Matrixs.mutil(b,new Matrix(c));
    35. return e.getMatrix()[0][0];
    36. }
    1. public class Matrix{
    2. // 矩阵
    3. private double[][] matrix;
    4. // m x n
    5. private int m;
    6. private int n;
    7. public double[][] getMatrix() {
    8. return matrix;
    9. }
    10. public Matrix() {
    11. }
    12. public Matrix(double[][] matrix) {
    13. this.matrix = matrix;
    14. this.m=matrix.length;
    15. this.n=matrix[0].length;
    16. }
    17. public Matrix(int m, int n) {
    18. this.matrix=new double[m][n];
    19. this.m=m;
    20. this.n=n;
    21. }
    22. public void setMatrix(double[][] matrix) {
    23. this.matrix = matrix;
    24. this.m=matrix.length;
    25. this.n=matrix[0].length;
    26. }
    27. public int getM() {
    28. return m;
    29. }
    30. public void setM(int m) {
    31. this.m = m;
    32. }
    33. public int getN() {
    34. return n;
    35. }
    36. public void setN(int n) {
    37. this.n = n;
    38. }
    39. @Override
    40. public String toString() {
    41. return "Matrix{" +
    42. "matrix=" + Arrays.toString(matrix) +
    43. '}';
    44. }
    45. }
    1. /**
    2. * 矩阵的幂运算
    3. * @param m 矩阵对象
    4. * @param count 运算次数
    5. * @return 如果矩阵不是方阵,则矩阵无法进行
    6. */
    7. public static Matrix mutils(Matrix m,int count)
    8. {
    9. if(m==null||m.getM()!=m.getN()){
    10. return null;
    11. }
    12. double[][] matrix = m.getMatrix();
    13. Matrix result = new Matrix(matrix);
    14. // [A]^count
    15. for (int i=0;i1;i++)
    16. {
    17. result = Matrixs.mutil(result,new Matrix(matrix));
    18. }
    19. return result;
    20. }
    21. /**
    22. * 实现矩阵的乘法
    23. * @param p1 矩阵1
    24. * @param p2 矩阵2
    25. * @return 如果矩阵不可乘,返回null
    26. */
    27. public static Matrix mutil(Matrix p1,Matrix p2)
    28. {
    29. if (p1==null||p2==null)
    30. {
    31. return null;
    32. }
    33. if (p1.getN()!=p2.getM())
    34. {
    35. // 矩阵不可乘
    36. return null;
    37. }
    38. double[][] m1 = p1.getMatrix();
    39. double[][] m2 = p2.getMatrix();
    40. // 矩阵可乘
    41. double [][] m =new double[p1.getM()][p2.getN()];
    42. for (int i=0;i
    43. {
    44. for (int j=0;j
    45. {
    46. double a=0;
    47. // 核心
    48. for (int k=0;k
    49. {
    50. a+=m1[i][k]*m2[k][j];
    51. }
    52. m[i][j]=a;
    53. }
    54. }
    55. return new Matrix(m);
    56. }

  • 相关阅读:
    RSA系列第1篇:RSA 介绍
    Dreamweaver教程从入门到精通 html篮球网站制作 学生静态网页作业源码模板
    flink 基于flink-sql-connector-elasticsearch6二次开发思路
    链式设计模式——装饰模式和职责链模式
    读后感-雷军2022年度演讲全文
    Golang Sync.WaitGroup 使用及原理
    Web 攻击的日志分析:初学者指南
    瑞芯微:基于RK3568的深度估计模型部署
    NeurIPS 2022 | 利用名词到代词的蒸馏以理解动词,面向任务的实例分割注意力模型
    LVS + KeepAlived实现高可用负载均衡
  • 原文地址:https://blog.csdn.net/fjza1168/article/details/127541204