Java 蓝桥杯 ALGO_60_矩阵乘方思路

谁践踏了优雅 2022-10-22 04:12 196阅读 0赞

本题原是 Java 蓝桥杯 ALGO\_60 题，刚拿到没有思路，在网上找到一篇大佬写的跟本题高度相关的参考题，故而本着我学习、我传播的精神，我就开始了很无脑的依葫芦画瓢运动，我对代码的理解全部在下面了。不过还是遇到了一个让我很迷惑的问题，那就是题目中的a （Ab%m=(A(b-1)%m)\***a**%m） 到底是什么呢？我也有一些猜想，不过在未能够验证自身代码的逻辑及细节是否正确的情况下，我也只能够做一下简单的猜想，但是并不能去证得正确的对a的解到底是什么。原本是很不好意思发这篇文章的，但是也非常想请各位大佬能够给点点拨！！！求大佬指点！！！

## 参考题代码理解： ##

**题目：矩阵求幂**  
给定一个N阶矩阵A，输出A的M次幂（M为非负整数）  
第一行是一个正整数N、M (1< =N< =30，0< =M< =5)，表示矩阵A的阶数和要求的幂数  
接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

--------------------

/**
      @author MingxuDeng
     
      2021年4月3日
     
      State：unsolved
    
      Hint:   矩阵求幂
       给定一个N阶矩阵A，输出A的M次幂（M为非负整数）
      	
      	第一行是一个正整数N、M (1< =N< =30，0< =M< =5)，表示矩阵A的阶数和要求的幂数
    	
    	接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
    
     
      Idea:
    
     */
    import java.util.Scanner;
    
    public class 矩阵乘方 {
        
    	public static void main(String[] args) {
        
    		Scanner scanner = new Scanner(System.in);
    		int N = scanner.nextInt();					//N阶
    		int M = scanner.nextInt();					//M次幂
    		int[][] a = new int[N][N];					//用二维数组a接收矩阵A
    		int[][] c = new int[N][N];					//二维数组c接收矩阵A,并用于存储结果矩阵
    		int i,j;
    		for (i = 0; i < N; i++) {
        	//用二维数组a接收矩阵A
    			for (j = 0; j < N; j++) {
        
    				a[i][j] = c[i][j]= scanner.nextInt();//快捷录入矩阵数据，这里让两个矩阵的数据直接相等，方便 M>1 时结果的计算
    			}
    		}
    		//矩阵乘法
    		if (M == 0) {
        								//当M=0时结果为单位矩阵（直接打印一个N阶的单位矩阵即可）
    			for (i = 0; i < N; i++) {
        
    				for(j = 0; j < N; j++) {
        
    					if (i == j) {
        
    						System.out.print(1 + " ");//当目前打印的横纵坐标相等时，即是在主对角线之上，即打印1
    					} else {
        
    						System.out.print(0 + " ");//当目前打印的横纵坐标不相等时，即是没有在主对角线上，即打印0即可
    					}
    				}
    				System.out.println();
    			}
    		} else if (M == 1) {
        						//当M=1时结果为原来的矩阵（M=1，即：矩阵A的1次幂，就是A本身）
    			for (i = 0; i < N; i++) {
        	//打印矩阵A（二维数组）中的数据即可
    				for(j = 0; j < N; j++) {
        
    					System.out.print(c[i][j] + " ");
    				}
    				System.out.println();
    			}
    		} else {
        							//当M>1时即为M个矩阵A相乘的结果，这里用到了矩阵乘法运算
    			/**
    			 * 矩阵乘法（假设两个都是2阶矩阵）：
    			 * 				A、B两个二阶矩阵相当于2*2的二维数组如A中的元素坐标可以理解为分别有：{(a11,a12),(a21,a22)},B同理。
    			 * 
    			 * 		A、C 两个矩阵相乘结果等于：
    			 * 								|(a11*b11+a12*b21),(a11*b12+a12*b22)|
    			 * 							A*C=|									|
    			 * 								|(a21*b11+a22*b21),(a21*b12+a22*b22)|
    			 */
    			for (int m = 1; m < M; m++) {
        	//最外层控制M次幂，m从1开始或m<M -1都可以，不要乘多一次
    				int[][] temp = new int[N][N];//定义一个临时二维数组，用来存放每一步乘法运算中结果矩阵中的对应位置的计算结果
    				for (i = 0; i < N; i++) {
        		//i控制行
    					for (j = 0; j < N; j++) {
        	//j控制列
    						int sum = 0;
    						//每次for循环到这里， i、j的值都不变，就可以再使用一个for循环，
    						//进行对上例中A*C相乘时对应四个位置中的某一个位置存放的数值的计算
    						for (int k = 0; k < N; k++) {
        
    							sum += a[i][k] * c[k][j];//求得结果矩阵中坐标为（i，j）的位置的值，存放到sum中
    						}
    						temp[i][j] = sum;//将sum的值存到临时矩阵temp中去。
    					}
    				}
    				c = temp;//乘法运算结束，将计算结果放到矩阵c中
    			}
    			for (i = 0; i < N; i++) {
        			//打印结果矩阵C
    				for (j = 0; j < N; j++) {
        
    					System.out.print(c[i][j] + " ");
    				}
    				System.out.println();
    			}
    		}
    	}
    }

--------------------

## 问题描述： ##

给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。

其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。

要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。

下面给出一种较快的算法(用A^b表示A的b次方)：

若b=0， 则A^b%m=I%m。其中I表示单位矩阵。  
|  
　　 若b为偶数，则Ab%m=(A(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。  
|  
　　 若b为奇数，则Ab%m=(A(b-1)%m)\*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。

这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2x2的矩阵，m不大于10000。  
输入格式  
　　 输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。  
输出格式  
　　 输出两行，每行两个整数，表示A^b%m的值。  
样例输入  
2 2  
1 1  
0 1  
样例输出  
1 0  
0 1

Idea:  
1.有二阶矩阵A、一个非负整数b和一个正整数m，求A的b次方除m的余数。  
2.注意是矩阵的乘方运算，  
3.对m的取模可以在对矩阵进行输出时进行。  
4.

package Algo;
    
    import java.util.Scanner;
    
    /**
      @author MingxuDeng
     
      2021年4月3日
     
      State：unsolved
    
      Hint:矩阵乘方
      问题描述
    　　 给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。
    
    　　 其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。
    
    　　 要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。
           
           下面给出一种较快的算法(用A^b表示A的b次方)：
           
    　　 	若b=0，	    则A^b%m=I%m。其中I表示单位矩阵。
    		|
    　　 	若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。
    		|
    　　 	若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。
    　　 
    
    	这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2x2的矩阵，m不大于10000。
    输入格式
    　　 输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。
    输出格式
    　　 输出两行，每行两个整数，表示A^b%m的值。
    样例输入
    		2 2
    		1 1
    		0 1
    样例输出
    		1 0
    		0 1
     
      Idea:
      			1.有二阶矩阵A、一个非负整数b和一个正整数m，求A的b次方除m的余数。
      			2.注意是矩阵的乘方运算，
      			3.对m的取模可以在对矩阵进行输出时进行。
      			4.
    
     */
    public class ALGO_60_矩阵乘方 {
        
    
    	public static void main(String[] args) {
        
    		Scanner s=new Scanner(System.in);
    		//输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。
    		int b,m;
    		b=s.nextInt();m=s.nextInt();
    		int[][]A=new int[2][2];int [][]B=new int[2][2];
    		int[][]I={
        {
        1,0},{
        0,1}};
    		int[][]R=new int[2][2];//两行，每行两个整数，表示A^b%m的值。
    		for(int i=0;i<2;i++){
        
    			for(int j=0;j<2;j++){
        
    				A[i][j]=B[i][j]=s.nextInt();
    			}
    		}
    		
    		//乘方运算
    		if(b==0){
        //若b=0，	    则A^b%m=I%m。其中I表示单位矩阵。（直接打印一个N阶的单位矩阵即可）
    			int i,j,N=2;
    			for (i = 0; i < N; i++) {
        
    				for(j = 0; j < N; j++) {
        
    					if (i == j) {
        
    						System.out.print(1 + " ");//当目前打印的横纵坐标相等时，即是在主对角线之上，即打印1
    					} else {
        
    						System.out.print(0 + " ");//当目前打印的横纵坐标不相等时，即是没有在主对角线上，即打印0即可
    					}
    				}
    				System.out.println();
    			}
    		}else{
        //若b!=0
    			switch(b%2){
        //若b为偶数，则 A^b%m=(A^(b/2)%m)^2%m ，即：先把 A乘b/2次方 对m求余，然后 再平方 后 对m求余 。
    				case 0:{
        
    					int t=b/2;
    					for(int M=1;M<t;M++){
        
    						int[][] temp = new int[2][2];//定义一个临时二维数组，用来存放每一步乘法运算中结果矩阵中的对应位置的计算结果
    						for(int i=1;i<2;i++){
        //控制行
    							for(int j=0;j<2;j++){
        //控制列
    								int sum=0;
    								for(int k=0;k<2;k++){
        
    									sum += A[i][k] * B[k][j];//求得结果矩阵中坐标为（j,k）的位置的值，存放到sum中
    								}
    								temp[i][j] = sum%m;//将sum的值存到临时矩阵temp中去。
    							}
    							R=temp;//乘法运算结束，将计算结果放到矩阵c中
    						}
    					}
    					
    					//上面将 A^(b/2)%m 部分计算完毕，下面对后面的()^2%m 部分进行计算
    					
    					A=B=R;//更新A、B中的值，否则因子没变的话得到的就不是正确的答案。下面只乘一次
    					for(int M=1;M<2;M++){
        
    						for(int i=0;i<2;i++){
        //控制行
    							int[][] temp = new int[2][2];//定义一个临时二维数组，用来存放每一步乘法运算中结果矩阵中的对应位置的计算结果
    							for(int j=0;j<2;j++){
        //控制列
    								int sum=0;
    								for(int k=0;k<2;k++){
        
    									sum += A[i][k] * B[k][j];//求得结果矩阵中坐标为（j,k）的位置的值，存放到sum中
    								}
    								temp[i][j] = sum%m;//将sum的值存到临时矩阵temp中去。
    							}
    							R=temp;//乘法运算结束，将计算结果放到矩阵c中
    						}
    					}
    					break;}
    					
    				case 1:{
        //若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求 A乘 b-1 次方 对m求余，然后 再乘A后 对m求余。
    					int t=b-1;
    					for(int M=0;M<t;M++){
        
    						for(int i=1;i<2;i++){
        //控制行
    							int[][] temp = new int[2][2];//定义一个临时二维数组，用来存放每一步乘法运算中结果矩阵中的对应位置的计算结果
    							for(int j=0;j<2;j++){
        //控制列
    								int sum=0;
    								for(int k=0;k<2;k++){
        
    									sum += A[j][k] * B[k][j];//求得结果矩阵中坐标为（j,k）的位置的值，存放到sum中
    								}
    								temp[i][j] = sum%m;//对每一个值进行对m的取模
    							}
    							R=temp;//乘法运算结束，将计算结果放到矩阵c中
    						}
    					}
    					//已完成计算：A^(b-1)%m   待完成运算：()*a%m,下面将临时结果R中的值全部给B和A
    					A=B=R;
    					for(int M=0;M<t;M++){
        
    						int[][] temp = new int[2][2];
    						for(int i=1;i<2;i++){
        
    							int sum=0;
    							for(int j=0;j<2;j++){
        
    								for(int k=0;k<2;k++){
        
    								sum += A[j][k] * B[k][j];//求得结果矩阵中坐标为（j,k）的位置的值，存放到sum中
    								}
    								//temp[i][j]=sum*a%m;//此处需要注意的是，题目中说是a，但是通篇都没有说明a到底是什么？小D猜测可能是：b、2、m
    							}
    							R=temp;
    						}
    					}
    				break;}
    				default:
    					break;
    			}
    		}
    		
    		//输出两行，每行两个整数，表示A^b%m的值。
    		for (int i = 0; i < 2; i++) {
        			//打印结果矩阵C
    			for (int j = 0; j < 2; j++) {
        
    				System.out.print(R[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    }