[编程题]矩阵幂
- 热度指数：16653 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
给定一个n*n的矩阵，求该矩阵的k次幂，即P^k。
输入描述:
第一行：两个整数n（2<=n<=10）、k（1<=k<=5），两个数字之间用一个空格隔开，含义如上所示。 接下来有n行，每行n个正整数，其中，第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且（0<=Pij<=10）。另外，数据保证最后结果不会超过10^8。
输出描述:
对于每组测试数据，输出其结果。格式为： n行n列个整数，每行数之间用空格隔开，注意，每行最后一个数后面不应该有多余的空格。
示例1
输入
2 2 9 8 9 3 3 3 4 8 4 9 3 0 3 5 7 5 2 4 0 3 0 1 0 0 5 8 5 8 9 8 5 3 9 6 1 7 8 7 2 5 7 3
输出
153 96 108 81 1216 1248 708 1089 927 504 1161 1151 739 47 29 41 22 16 147 103 73 116 94 162 108 153 168 126 163 67 112 158 122 152 93 93 111 97
矩阵快速幂板题
#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 20; //矩阵最大行列数
using namespace std;
struct Mat
{
int mat[maxn][maxn]; //矩阵
int row, col; //矩阵行列数
};
Mat mod_mul(Mat a, Mat b, int p) //矩阵乘法
{
Mat ans;
ans.row = a.row;
ans.col = b.col;
memset(ans.mat, 0, sizeof(ans.mat));
for (int i = 0; i < ans.row; i++)
for (int j = 0; j < ans.col; j++)
for (int k = 0; k < a.col; k++)
{
ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
ans.mat[i][j] %= p;
}
return ans;
}
Mat mod_pow(Mat a, int k, int p) //矩阵快速幂
{
Mat ans;
ans.row = a.row;
ans.col = a.col;
for (int i = 0; i < a.row; i++)
for (int j = 0; j < a.col; j++)
ans.mat[i][j] = (i == j);
while (k)
{
if (k & 1)
ans = mod_mul(ans, a, p);
a = mod_mul(a, a, p);
k >>= 1;
}
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
Mat m;
int n, k;
while (~scanf("%d%d", &n, &k))
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &m.mat[i][j]);
m.col = m.row = n;
Mat ans = mod_pow(m, k, 10e8);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (j != 0)
printf(" ");
printf("%d", ans.mat[i][j]);
}
printf("\n");
}
}
return 0;
}
发表于 2019-02-20 17:03:09
回复(1)
#include<stdio.h>
int main()
{
int i,j,n,m,k,a[20][20],result[20][20];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
result[i][j]=a[i][j];
}
while(--m)
{
int c[20][20]={0};//过渡数组
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
c[i][j]+=result[i][k]*a[k][j];//重点
for(i=0;i<n;i++)
for(j=0;j<n;j++)
result[i][j]=c[i][j];
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",result[i][j]);
printf("\n");
}
}
return 0;
}
发表于 2020-05-06 15:10:13
回复(0)
#include<bits/stdc++.h>
int main(){
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
int a[10][10],b[10][10],c[10][10];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
c[i][j]=a[i][j];
}
for(int i=0;i<k-1;i++){
for(int l=0;l<n;l++)
for(int j=0;j<n;j++)
b[l][j]=c[l][j];
for(int j=0;j<n;j++)
for(int l=0;l<n;l++){
int temp=0;
for(int m=0;m<n;m++)
temp+=a[j][m]*b[m][l];
c[j][l]=temp;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
printf("%d ",c[i][j]);
printf("\n");
}
}
}
发表于 2019-03-22 11:33:09
回复(1)
#include<stdio.h>
#include<string.h>
typedef long long ll;
int main(){
ll a[100][100];
ll b[100][100];
ll c[100][100];
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%lld",&a[i][j]);
b[i][j]=a[i][j];//将a赋值给b
}
while(k-1){//矩阵k次方
memset(c,0,sizeof(c));//要每次将c置0，c暂存结果
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int m=0;m<n;m++)
c[i][j]+=b[i][m]*a[m][j];//保存每一次结果
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
b[i][j]=c[i][j];//b存最终结果
k--;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=0)
printf(" ");
printf("%lld",b[i][j]);
}
printf("\n");
}
return 0;
}
发表于 2019-01-22 11:37:52
回复(0)
二维数组本质还是一维数组，且
a[i][j]=a[n*i+j]
因为1≤k≤5，故无需用到快速幂
#include <stdio.h>
#include <stdlib.h>
void matrix_multiply(int *a,int *b,int *c,int n) // a*b=c
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
c[n*i+j]=0;
for(int k=0; k<n; k++)
{
c[n*i+j]+=a[n*i+k]*b[n*k+j];
}
}
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
int *a=(int*)malloc(sizeof(int)*n*n);
int *b=(int*)malloc(sizeof(int)*n*n);
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
scanf("%d",&a[n*i+j]);
b[n*i+j]=a[n*i+j];
}
}
int *t=(int*)malloc(sizeof(int)*n*n);
for(int i=2; i<=k; i++)
{
matrix_multiply(b,a,t,n);
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
b[n*i+j]=t[n*i+j];
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
printf("%d ",b[n*i+j]);
}
printf("\n");
}
}
return 0;
}
编辑于 2020-03-01 19:48:04
回复(0)
#include<iostream>
using namespace std;
#define max_len 10
//第一次不细心，没咋看输出格式-_-晕
int a[max_len][max_len];//用全局变量以保证函数运行后，变量的值不会丢失
int b[max_len][max_len];//保存最初始矩阵的值
void mutiple(int a[max_len][max_len],int n)
{
int sum[n][n];
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
{
sum[i][j] = 0;
for(int k = 0;k < n;k++)
{
sum[i][j] += a[i][k] * b[k][j]; //计算的重点，用j进行列的更新
}
}
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
a[i][j] = sum[i][j];//对a数组进行重新赋值，以保存计算的结果
}
int main(void)
{
int n,k;
while(cin >> n >> k)
{
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
cin >> a[i][j];
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
b[i][j] = a[i][j];
for(int i = 1;i < k;i++)//进行K次幂运算
mutiple(a,n);
for(int i = 0;i < n;i++)
{
//cout << endl;
for(int j = 0;j < n;j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
return 0;
}
发表于 2021-02-15 16:20:28
回复(0)
#include <iostream>
using namespace std;
/*给定一个n*n的矩阵，求该矩阵的k次幂，即P^k。（2<=n<=10）、k（1<=k<=5）
Pij且（0<=Pij<=10）。另外，数据保证最后结果不会超过10^8*/
class matrix
{
public:
//matrix() {}//无参构造
matrix(int r, int c)//有参构造
{
this->row = r;
this->col = c;
this->mat = new int*[r];//初始化矩阵空间
for (int k = 0; k < r; k++)
this->mat[k] = new int[c];
}
matrix(const matrix &m)//因为类开辟了堆区空间，重写拷贝构造
{
this->row = m.row;
this->col = m.col;
this->mat = new int*[row];
for (int i = 0; i < this->row; i++)
{
this->mat[i] = new int[col];
for (int j = 0; j < this->col; j++)
this->mat[i][j] = m.mat[i][j];
}
}
matrix& operator=(const matrix& m)//重载赋值操作符
{
this->row = m.row;
this->col = m.col;
if (mat == NULL)//如果堆区为空，则开辟
{
this->mat = new int* [row];
for (int k = 0; k < row; k++)
mat[k] = new int[col];
}
for (int i = 0; i < this->row; i++)
{
for (int j = 0; j < this->col; j++)
this->mat[i][j] = m.mat[i][j];
}
return *this;
}
void init_matrix()
{
this->mat = new int* [row];//初始化矩阵空间
for (int i = 0; i < this->row; i++)
{
this->mat[i] = new int[col];
for (int j = 0; j < this->col; j++)
cin >> this->mat[i][j];//输入矩阵
}
}
void dispaly()
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
cout << this->mat[i][j] << " ";
cout << endl;
}
}
~matrix()//析构堆区空间
{
for (int i = 0; i < this->row; i++)
if (mat[i] != NULL)
{
delete[] mat[i];
mat[i] = NULL;//防止野指针
}
if (mat != NULL)
{
delete[] mat;
mat = NULL;
}
}
//private://类含有指向堆区的指针成员，会产生深拷贝问题，要重写拷贝构造和=赋值操作符
int** mat;
int row, col;
};
matrix operator*(const matrix &a, const matrix &b)
{
if (a.row != b.col || a.col != b.row)
{
cout << "矩阵大小不匹配" << endl;
exit(0);
}
matrix result(a.row, a.col);
for (int k = 0; k < a.row; k++)
{
for (int i = 0; i < a.row; i++)
{
int sum = 0;
for (int j = 0; j < a.col; j++)
sum += a.mat[k][j] * b.mat[j][i];
result.mat[k][i] = sum;
}
}
return result;
}
matrix matrix_pow(matrix &a, int k) //矩阵快速幂
{
matrix ans(a.row ,a.col);
for (int i = 0; i < ans.row; i++)
for (int j = 0; j < ans.col; j++)
if (i == j)
ans.mat[i][j] = 1;
else
ans.mat[i][j] = 0;
while (k != 0)
{
if (k % 2 == 1)
ans = ans * a;
a = a * a;
k /= 2;
}
return ans;
}
void test1()
{
int n, k;
while (cin >> n >> k)
{
matrix m(n,n);
m.init_matrix();
//matrix ans(n,n);
matrix ans = matrix_pow(m, k);
ans.dispaly();
}
}
int main()
{
test1();
return 0;
} 用了类，虽然有点麻烦，但正好学习一下深拷贝问题
编辑于 2020-05-08 12:03:11
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
int size = scanner.nextInt(), pow = scanner.nextInt();
int[][] num = new int[size][size];
for(int j = 0; j < num.length; j++)
for(int k = 0; k < num.length; k++)
num[j][k] = scanner.nextInt();
int[][] nums = powSquel(num, pow);
for(int j = 0; j < nums.length; j++) {
for(int k = 0; k < nums.length; k++) {
System.out.print(nums[j][k]);
if(k != nums.length - 1) System.out.print(" ");
}
System.out.println();
}
}
}
private static int[][] powSquel(int[][] num, int pow) {
int[][] nums = new int[num.length][num.length];
nums = num;
while(pow > 1) {
int[][] nums1 = new int[num.length][num.length];
for(int i = 0; i < num.length; i++)
for(int j = 0; j < num.length; j++)
for(int k = 0; k < num.length; k++)
nums1[i][j] += nums[i][k] * num[k][j];
nums = nums1;
pow--;
}
return nums;
}
}
发表于 2020-03-08 20:30:35
回复(0)
#include <iostream>
#include <array>
using namespace std;
typedef array<array<int,10>,10> node;
node data,ans,temp;
int n,k;
node mul(const node& x1,const node& x2){//矩阵乘法
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int sum=0;
for(int k=0;k<n;k++)
sum = sum +x1[i][k]*x2[k][j];
temp[i][j]= sum;
}
}
return temp;
}
void init(){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i==j) ans[i][j]=1;
else ans[i][j]=0;
}
int main(){
while (cin>>n>>k)
{
init();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>data[i][j];
while(k!=0){
if(k%2)
ans = mul(ans,data);
k=k/2;
data = mul(data,data);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j==n-1)
cout<<ans[i][j];
else
cout<<ans[i][j]<<' ';
}
cout<<endl;
}
}
return 0;
} 矩阵快速幂，把一次矩阵乘法看做一个基本单位，时间复杂度logn
编辑于 2020-03-03 21:45:30
回复(0)
//思路，矩阵的幂次，由于我刚在练手快速幂所以想到矩阵的幂能不能也用快速幂的方法，把矩阵整体当成一个数来求幂
//这个时候想到重载*号，内部细节重载，外部看起来和普通*号的用法一样
//重载运算符号可以少写几个函数 原谅我的偷懒 嘿嘿嘿
#include<iostream>
using namespace std;
struct shu//定义一个结构保存数组和重载*号
{
int a[10][10] = {0};//全部置零
shu operator*(const shu& c)//重载*号
{
shu temp;
for (int i = 0; i < 10; i++)//经典的矩阵乘法的3重循环
for (int j = 0; j < 10; j++)
for (int k = 0; k < 10; k++)
temp.a[i][j] += a[i][k] * c.a[k][j];//一行乘一列
return temp;
}
};
int main()
{
int n, k;
while (cin >> n >> k)
{
shu m,temp;//快速幂中 我们会使用一个temp来保存我们最后求到的结果，且temp初始化=1；
for (int i = 0; i < n; i++)//那么矩阵中相当于普通整数的1的是什么呢 答案是单位阵
temp.a[i][i] = 1;//所以这里先定义一个单位阵作为‘1‘；主线为1，其余为0的矩阵
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> m.a[i][j];
while (k)//这里就是经典的快速幂的方法了
{
if (k % 2 == 1)
{
temp = temp*m;
}
k /= 2;
m = m * m;
}
for (int i = 0; i < n; i++)//注意只遍历到n-1过，过了n-1的元素全是0了
{
for (int j = 0; j < n; j++)
cout << temp.a[i][j] << " ";
cout << endl;
}
}
}
编辑于 2020-03-02 22:59:41
回复(0)
#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> cro_matrix(vector<vector<int>> a,vector<vector<int>> b,int n){
vector<vector<int>> sum(n,vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum[i][j] = 0;
for(int k=0;k<n;k++)
sum[i][j]+=a[i][k]*b[k][j];
}
}
return sum;
}
vector<vector<int>> cur_pow_matrix(vector<vector<int>> a,int n,int k){
if(k==2){
return cro_matrix(a,a,n);
}
else{
if(k==1){
return a;
}
else{
vector<vector<int>> b( cur_pow_matrix(a,n,k/2));
b = cro_matrix(b,b,n);
if(k%2==1){
b = cro_matrix(a,b,n);
}
return b;
}
}
}
int main(void){
int n,k;
while(cin>>n>>k){
int temp;
vector<vector<int>> a(n,vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>temp;
a[i][j] = temp;
}
}
vector<vector<int>> b(cur_pow_matrix(a,n,k));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j==0)
cout<<b[i][j];
else{
cout<<" "<<b[i][j];
}
}
cout<<endl;
}
}
return 0;
}
发表于 2020-02-29 20:07:13
回复(0)
/* 开始在想这可怎么算，每次一个n^3
灵光一现，快速幂啊
author@RH
time：2019/9/7/23：48
*/
#include <stdio.h>
using namespace std;
int matrix[10][10];
int c[10][10];
int result[10][10];
int n;
int k;
void mul(int(*a)[10], int(*b)[10]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = 0;
for (int k = 0; k < n; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return;
}
void copy(int (*a)[10], int (*b)[10]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = b[i][j];
}
}
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]);
result[i][j] = 0;
}
result[i][i] = 1;
}
while (k != 0) {
if (k % 2 == 1) {
mul(result, matrix);
copy(result, c);
}
mul(matrix, matrix);
copy(matrix, c);
k /= 2;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
}
return 0;
}
发表于 2019-09-07 23:48:47
回复(0)
#include <iostream>
#include <stdio.h>
using namespace std;
int num[10][10];
int result[10][10];
int mid[10][10];
int chengji(int a[][10],int b[][10],int x,int y,int n);
int chengji(int a[][10],int b[][10],int x,int y,int n){
int r=0;
int i1=0;
int j1=0;
while(n!=0){
r=r+a[x][i1]*b[j1][y];
i1++;
j1++;
n--;
}
return r;
}
int main()
{
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&num[i][j]);
result[i][j]=num[i][j];
}
}
//k次
for(int x=1;x<k;x++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mid[i][j]=result[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j]=chengji(mid,num,i,j,n);
}
}
}
//print result
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=(n-1)){
printf("%d ",result[i][j]);
}else
printf("%d",result[i][j]);
}
printf("\n");
}
}
return 0;
}
#include <stdio.h>
using namespace std;
int num[10][10];
int result[10][10];
int mid[10][10];
int chengji(int a[][10],int b[][10],int x,int y,int n);
int chengji(int a[][10],int b[][10],int x,int y,int n){
int r=0;
int i1=0;
int j1=0;
while(n!=0){
r=r+a[x][i1]*b[j1][y];
i1++;
j1++;
n--;
}
return r;
}
int main()
{
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&num[i][j]);
result[i][j]=num[i][j];
}
}
//k次
for(int x=1;x<k;x++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mid[i][j]=result[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j]=chengji(mid,num,i,j,n);
}
}
}
//print result
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=(n-1)){
printf("%d ",result[i][j]);
}else
printf("%d",result[i][j]);
}
printf("\n");
}
}
return 0;
}
发表于 2019-03-04 13:17:50
回复(0)
#include<iostream>
typedef long long ll;//因为矩阵乘积中的元素有可能超过int 的表示范围
void mul(ll result[11][11],ll a[11][11],int n){
int i,j,k;
int c[11][11];
for(i=0;i<n;i++){
for(j=0;j<n;j++) c[i][j]=0;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
for(k=0;k<n;k++) c[i][j]+=result[i][k]*a[k][j];
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++) result[i][j]=c[i][j];
}
}
int main(){
int n,k;
ll a[11][11],result[11][11];
while(scanf("%d%d",&n,&k)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lld",&a[i][j]);
result[i][j]=a[i][j];//输入矩阵a 并复制给矩阵result
}
}
for(int i=0;i<k-1;i++) mul(result,a,n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d",result[i][j]);
if(j==n-1) printf("\n");
else printf(" ");
}
}
}
return 0;
}
typedef long long ll;//因为矩阵乘积中的元素有可能超过int 的表示范围
void mul(ll result[11][11],ll a[11][11],int n){
int i,j,k;
int c[11][11];
for(i=0;i<n;i++){
for(j=0;j<n;j++) c[i][j]=0;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
for(k=0;k<n;k++) c[i][j]+=result[i][k]*a[k][j];
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++) result[i][j]=c[i][j];
}
}
int main(){
int n,k;
ll a[11][11],result[11][11];
while(scanf("%d%d",&n,&k)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lld",&a[i][j]);
result[i][j]=a[i][j];//输入矩阵a 并复制给矩阵result
}
}
for(int i=0;i<k-1;i++) mul(result,a,n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d",result[i][j]);
if(j==n-1) printf("\n");
else printf(" ");
}
}
}
return 0;
}
发表于 2019-02-01 23:03:20
回复(0)
#include<stdio.h>
int main(){
int i,j,k,n,t;
int a[11][11];
int b[11][11];
int c[11][11];
while(scanf("%d%d",&n,&k)!=EOF){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
b[i][j]=a[i][j];
c[i][j]=a[i][j];
}
}
for(t=1;t<k;t++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
int sum=0;
for(int r=1;r<=n;r++){
sum=sum+b[i][r]*a[r][j];
}
c[i][j]=sum;
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
b[i][j]=c[i][j];
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(j==1){
printf("%d",b[i][j]);
}
else printf(" %d",b[i][j]);
}
printf("\n");
}
}
}
发表于 2019-01-10 20:01:44
回复(2)
#include <iostream>
using namespace std;
int main()
{
int n, k;
int a[10][10];//输入矩阵
int b[10][10];//输出矩阵
int c[10][10];//暂存结果
cin >> n >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
//计算n阶矩阵的k次幂.
int sum = 0;
while(--k)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum = 0;
for (int w = 0; w < n; w++)
{
sum += b[i][w] * a[w][j];
}
c[i][j] = sum;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
b[i][j] = c[i][j];
}
}
}
//输出计算结果.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << b[i][j] << ' ';
}
cout << endl;
}
return 0;
}
using namespace std;
int main()
{
int n, k;
int a[10][10];//输入矩阵
int b[10][10];//输出矩阵
int c[10][10];//暂存结果
cin >> n >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
//计算n阶矩阵的k次幂.
int sum = 0;
while(--k)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum = 0;
for (int w = 0; w < n; w++)
{
sum += b[i][w] * a[w][j];
}
c[i][j] = sum;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
b[i][j] = c[i][j];
}
}
}
//输出计算结果.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << b[i][j] << ' ';
}
cout << endl;
}
return 0;
}
编辑于 2019-01-05 17:30:49
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, k;
while (cin >> n >> k){
int a[12][12] = { { 0 } };
int result[12][12] = { { 0 } };
for (int i = 0; i < n; i++){
result[i][i] = 1;
}
for (int i = 0; i<n; i++){
for (int j = 0; j<n; j++){
cin >> a[i][j];
}
}
for (int i = 0; i<k; i++){
int temp[12][12] = { { 0 } };
for (int j = 0; j<n; j++){
for (int k = 0; k<n; k++){
for (int l = 0; l<n; l++){
temp[j][k] += result[j][l] * a[l][k];
}
}
}
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
result[j][k] = temp[j][k];
}
}
}
for (int i = 0; i<n; i++){
for (int j = 0; j<n; j++){
cout << result[i][j] << " ";
}
cout << endl;
}
}
}
发表于 2018-09-13 20:38:18
回复(0)
#include<iostream>
using namespace std;
int main()
{
int n,k;
while(cin>>n>>k)
{
int mat1[11][11],matrix[11][11];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>matrix[i][j];
mat1[i][j]=matrix[i][j];
}
}
int mat2[11][11];
for(int i=0;i<11;i++)
fill(mat2[i],mat2[i]+11,0);
for(int q=2;q<=k;q++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int p=0;p<n;p++)
mat2[i][j]+=(mat1[i][p]*matrix[p][j]);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
mat1[i][j]=mat2[i][j];
mat2[i][j]=0;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<mat1[i][j];
if(j!=n-1)cout<<' ';
}
cout<<endl;
}
}
return 0;
}
编辑于 2018-09-05 16:31:24
回复(0)
#include <cstdlib>//用到了三个矩阵惭愧
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{ int n,m,t=0;
while(scanf("%d %d",&n,&m)!=EOF){
int maze[n][n],now[n][n],map[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&maze[i][j]);
now[i][j]=maze[i][j];
map[i][j]=maze[i][j];
}
}
for(int i=0;i<m-1;i++){//执行m-1次乘方
for(int a=0;a<n;a++){
for(int b=0;b<n;b++){
for(int j=0;j<n;j++){
t+=map[a][j]*now[j][b];
}
maze[a][b]=t;
t=0;
}
}
for(int k=0;k<n;k++){
for(int h=0;h<n;h++){
map[k][h]=maze[k][h];
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=n-1)
printf("%d ",maze[i][j]);
else
{printf("%d",maze[i][j]);
printf("\n");
}
}
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{ int n,m,t=0;
while(scanf("%d %d",&n,&m)!=EOF){
int maze[n][n],now[n][n],map[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&maze[i][j]);
now[i][j]=maze[i][j];
map[i][j]=maze[i][j];
}
}
for(int i=0;i<m-1;i++){//执行m-1次乘方
for(int a=0;a<n;a++){
for(int b=0;b<n;b++){
for(int j=0;j<n;j++){
t+=map[a][j]*now[j][b];
}
maze[a][b]=t;
t=0;
}
}
for(int k=0;k<n;k++){
for(int h=0;h<n;h++){
map[k][h]=maze[k][h];
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=n-1)
printf("%d ",maze[i][j]);
else
{printf("%d",maze[i][j]);
printf("\n");
}
}
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
发表于 2018-03-12 21:31:44
回复(1)
#include<stdio.h>
int main(){
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
int num[10][10];
int tmp1[10][10];
int ans[10][10];
for(int i=0;i<n;i++) for(int j=0;j<n;j++){ int tmp; scanf("%d",&tmp); num[i][j]=tmp; ans[i][j]=tmp; tmp1[i][j]=tmp; } while(k>1){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
int tmp=0;
for(int x=0;x<n;x++){
tmp+=tmp1[i][x]*num[x][j];
}
ans[i][j]=tmp;
}
for(int i=0;i<n;i++) for(int j=0;j<n;j++) tmp1[i][j]=ans[i][j];
k--;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){ if(j==n-1) printf("%d",ans[i][j]); else printf("%d ",ans[i][j]);
}
printf("\n");
}
}
}
编辑于 2018-02-28 20:09:22
回复(0)
问题信息
难度：
108条回答
116收藏
13441浏览
通过挑战的用户
查看代码-
2023-03-12 22:00:00
-
2023-03-11 10:11:23
-
2023-03-07 20:06:30 -
2023-02-25 11:05:02
-
2023-02-18 20:11:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
