文档章节

矩阵快速幂的JAVA实现

旺仔没馒头
 旺仔没馒头
发布于 2017/09/03 16:14
字数 421
阅读 7
收藏 0

矩阵快速幂

题目描述:

给定一个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次幂。

© 著作权归作者所有

共有 人打赏支持
旺仔没馒头
粉丝 4
博文 20
码字总数 16560
作品 0
济南
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
android图像处理系统1.3

android图像处理系统1.3 该版本由很大的更新。在处理图像的方式上,我引入了java中的矩阵类(Matrix)。该类由http://math.nist.gov/javanumerics/jama/提供。实现了矩阵的加、减、乘、转置、矩...

长平狐
2012/10/08
108
0
Python才是人工智能AI的首选编程语言,你值得拥有……

在所有编程语言里,Python并不算萌新,从1991年发布第一个版本,至今已经快30年了。 最近几年,随着人工智能概念的火爆,Python迅速升温,成为众多AI从业者的首选语言。 根据数据平台 Kaggle...

M耀文
2018/05/19
0
0
JAVA 持有对象——容器初探

引言 如果一个程序只包含固定数量的且其生命周期都是已知对象,那么这是一个非常简单的程序——《think in java》 了解容器前,先提出一个问题,ArrayList和LinkedList谁的处理速度更快呢? ...

jiangmitiao
2015/08/01
0
2
Effective Java 第三版——47. 优先使用Collection而不是Stream来作为方法的返回类型

Tips 《Effective Java, Third Edition》一书英文版已经出版,这本书的第二版想必很多人都读过,号称Java四大名著之一,不过第二版2009年出版,到现在已经将近8年的时间,但随着Java 6,7,8...

M104
2018/09/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
36分钟前
2
0
IntelliJ IDEA 第一个 Scala 程序

IntelliJ 安装完成 Scala 插件后,你需要尝试使用 IntelliJ 来创建并且运行第一个程序。 通常这个程序只是简单的输出 Hello World。 创建一个新工程 在文件下面选择新建,然后选择创建工程。...

honeymose
40分钟前
2
0
mysql分表,分区的区别和联系

一,什么是mysql分表,分区 什么是分表,从表面意思上看呢,就是把一张表分成N多个小表,具体请看mysql分表的3种方法 什么是分区,分区呢就是把一张表的数据分成N多个区块,这些区块可以在同...

吴伟祥
43分钟前
1
0
csapp 习题 - 如何实现异或 exclusive-or

阅读 csapp v3 时,练习题 2.13 很有意思。练习题描述如下。 位设置是对于参数 mask 中每一个为 1 的位,那么参数 x 中相应位则被设置为 1 ;位清除是对于参数 mask 中每一个为 1 的位,那么...

ylme
昨天
5
0
Amino——产品迭代

兴趣部落产品迭代 时间 版本号 更新内容 备注 2019年1月2日 v3.1.1 支持定制部落首页的内容tab,酋长可以将精华、相册、分类添加到部落首页啦。 支持申请酋长,酋长可以直接推送优质话题,快...

铸剑为犁413
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部