矩阵快速幂的JAVA实现
矩阵快速幂的JAVA实现
旺仔没馒头 发表于3个月前
矩阵快速幂的JAVA实现
  • 发表于 3个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: 给定一个n\*n的矩阵,求该矩阵的k次幂,即P^k

矩阵快速幂

题目描述:

给定一个n*n的矩阵,求该矩阵的k次幂,即P^k。

如何快速的算出一个矩阵的N次幂呢,举个例子,比如A^19 => (A^16)*(A^2)*(A^1)显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n),不仅这样,因子间也是存在某种联系的。 比如A^4能通过(A^2)*(A^2)得到,A^8又能通过(A^4)*(A^4)得到,这点也充分利用了现有的结果作为有利条件。 下面举个例子进行说明:现在要求A^156,而156(10)=10011100(2) 也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128) 考虑到因子间的联系,我们从二进制10011100中的最右端开始计算到最左端。
以下代码就是其实现方式:

public class MatrixMulti {

    public static long[][] mut(int k,int n,long[][] A){
        long [][] res = new long[n][n];
        for(int i = 0 ; i < res.length ;i++){
            for(int j = 0 ; j< res[i].length ;j++){
                if(i==j){
                    res[i][j] = 1;
                }else{
                    res[i][j] = 0;
                }
            }
        }
        while(k!=0){
            if((k&1)==1) res = f(res,A);
            k>>=1;
            A = f(A,A);
        }
        return res;
    }
    public static long[][] f(long[][] A,long[][] B){
        long res[][] = new long[A.length][B.length];
        for(int i = 0 ; i < res.length ;i++){
            for(int j = 0 ; j< res[i].length ;j++){
                for(int k = 0 ; k < A[0].length ;k++){
                    res[i][j] += A[i][k]*B[k][j];
                }
            }
        }
        return res;
    }

}

其中函数f(),是定义了矩阵的乘法运算,在矩阵中,单位矩阵就是相当于常数1,在函数mut()中,最主要的就是while循环里的代码,运用了分治的思想,快速的计算矩阵的n次幂。

标签: Java
共有 人打赏支持
粉丝 2
博文 10
码字总数 7962
×
旺仔没馒头
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: