藍橋杯：VIP試題 基礎練習 矩陣乘法

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

　　給定一個N階矩陣A，輸出A的M次幂（M是非負整數）

　　例如：

　　A =

　　1 2

　　3 4

　　A的2次幂

　　7 10

　　15 22

　　

輸入格式

　　第一行是一個正整數N、M（1<=N<=30, 0<=M<=5），表示矩陣A的階數和要求的幂數

　　接下來N行，每行N個絕對值不超過10的非負整數，描述矩陣A的值

　　

輸出格式

　　輸出共N行，每行N個整數，表示A的M次幂所對應的矩陣。相鄰的數之間用一個空格隔開

　　

樣例輸入

2 2

1 2

3 4

樣例輸出

7 10

15 22

#include<iostream>
	#include<cstdio> 
	using namespace std;
	
	
	int main(){
		int n,m;
		cin>>n>>m;
		int a[31][31]={0};//輸入進來的數組 
		int t[31][31]={0};//用來計算幾次幂的數組 
		int other[31][31]={0};//用來中轉資料的數組
		
		for(int i = 1; i <= n;i++){
			for(int j = 1; j <= n;j++){
				cin>>a[i][j]; 
			}			
		}
		 
		for(int i = 1; i <= n;i++){
			for(int j = 1; j <= n;j++){
				t[i][j]=a[i][j]; 
			}			
		} 
			//	當零次幂時，為機關矩陣 
			if(m == 0){
					for(int i = 1; i <= n;i++){
						for(int j = 1; j <= n;j++){
							if(i == j) cout<<1<<" ";
							else cout<<0<<" ";
						}
						cout<<endl;
					}	
			}
			//	當一次幂時，為本身
			else if(m == 1){
				for(int i = 1; i <= n;i++){
					for(int j = 1; j <= n;j++){
						printf("%d ",a[i][j]);
						//cout<<a[i][j]<<" "; 
					}	
					cout<<endl;		
				}
			}
			/*
			
			1 2
			3 4
			*/
			//	當多次幂時，便為矩陣乘法 
			else{
				/*每次幂的計算都是乘以原數組a*/ 
				while(m-1){//m=2實際就隻進行1次乘法， m=3實際進行2次乘法，是以是m-1 
					for(int i = 1; i <= n;i++){
						for(int j = 1; j <= n;j++){
							int temp = 0;
							/*計算i行j列的元素值*/ 
							for(int k = 1;k <= n;k++){	
														
								temp = temp + t[i][k]*a[k][j];
																 							
							}
							other[i][j] = temp;	//将計算好的 i行j列的元素值先存放至中轉站處 
												
						}				
					}
					/*将中轉數組的資料移放至t數組中，以供下次輸出結果或進行下次計算*/ 
					for(int i = 1; i <= n;i++){
						for(int j = 1; j <= n;j++){
							t[i][j]=other[i][j]; 
						}			
					}					
					m--; 
					
				}
				/*輸出m次幂後的答案*/ 
				for(int i = 1; i <= n;i++){
					for(int j = 1; j <= n;j++){
						printf("%d ",t[i][j]);
						//cout<<a[i][j]<<" "; 
					}	
					cout<<endl;		
				}								
				
			} 
		return 0;
	}