Question

用C++实现矩阵链相乘

Answer 1

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=52;
const int mod=1111;
struct Matrix
{
int mat[N][N];
int n,m;
Matrix()//初始化
{
n=m=N;
memset(mat,0,sizeof(mat));
}
inline void init(int row,int column)//初始矩阵大小
{
n=row,m=column;
}
void init_e()//单位矩阵
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
mat[i][j]=(i==j);
}
}
}
void print()
{//测试检查用
puts("--------------");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout<<(int)mat[i][j];
}
cout<<endl;
}
}

};

Matrix operator *(Matrix a,Matrix b) //乘法。。。。。
{
Matrix ret;
ret.init(a.n,b.m);
for(int i=0;i<a.n;i++)
{
for(int k=0;k<a.m;k++) if(a.mat[i][k])
{
for(int j=0;j<b.m;j++) if(b.mat[k][j])
{
ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
if(ret.mat[i][j]>=mod)
{
ret.mat[i][j]%=mod;
}
}
}
}
return ret;
}
Matrix operator +(Matrix a,Matrix b) //加法。。。。。
{
Matrix ret;
ret.init(a.n,a.m);
for(int i=0;i<a.n;i++)
{
for(int j=0;j<a.m;j++)
{
ret.mat[i][j]=a.mat[i][j]+b.mat[i][j];
if(ret.mat[i][j]>=mod)
{
ret.mat[i][j]%=mod;
}
}
}
return ret;
}
Matrix operator ^(Matrix a,int b)//求幂
{
Matrix ret=a,tmp=a;
ret.init_e();
for(;b;b>>=1)
{
if(b&1)
{
ret=ret*tmp;
}
tmp=tmp*tmp;
}
return ret;
}
Matrix sum1(Matrix a,int b) //递归幂求和 s=a+a^2+a^3.....
{
Matrix ret=a;
ret.init_e();
if(b=1) return a;
else if(b&1)
{
return (a^b)+sum1(a,b-1);
}
else
{
return sum1(a,b>>1)*(a^(b>>1))+ret;
}
}
Matrix sum2(Matrix a,int b) //非递归幂求和
{
int k=0,ss[32];
Matrix ret,tp1,tp2;
tp1=tp2=ret=a;
while(b)
{
ss[k++]=b&1;
b>>=1;
}
for(int i=k-2;i>=0;i--)
{
tp1=tp1*(tp2+ret);
tp2=tp2*tp2;
if(ss[i])
{
tp2=tp2*a;
tp1=tp1+tp2;
}
}
return tp1;
}
int main()
{
Matrix a, b;
a.init(2, 2);
b.init(2, 2);
a.mat[0][0] = a.mat[0][1] = a.mat[1][0] = 1;

b = a + a;
b.print();
b = a ^ 2;
b.print();
b = a * a;
b.print();

return 0;
}