分治法矩阵乘法怎么求？
#include<iostream>
#include<ctime>
using namespace std;
typedef int** Matrix;
bool BF_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size);
bool Add_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size);
bool Sub_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size);
bool DAC_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size);
bool Malloc_Matrix(Matrix A[],Matrix B[],Matrix M[],Matrix Temp[],int Size);
bool Initab(Matrix A[],Matrix B[],Matrix& M1,Matrix& M2,int Size);
bool Get_Result(Matrix& Result,Matrix M[],int Size);
bool Delete_Matrix(Matrix A[],Matrix B[],Matrix M[],Matrix Temp[],int Size);
bool Out_Matrix(Matrix& M,int Size);
char Menu();
int main()
{
clock_t start_time,end_time,spend_time;
Matrix A,B,C;
int Size=0;
cout<<请输入矩阵阶数\n;
cin>>Size;//必须输2的幂次方 比如 4 8 16 32
A=new int*[Size];
B=new int*[Size];
C=new int*[Size];
for(int i=0;i<Size;i++)
{ A[i]=new int[Size];
B[i]=new int[Size];
C[i]=new int[Size];
}
srand(time(0));
for(int i=0;i<Size;i++)
for(int j=0;j<Size;j++)
{
A[i][j]=rand()%100;
B[i][j]=rand()%100;
}
switch(Menu())
{
case 'b':
case 'B':{
/*cout<<A=<<endl;
Out_Matrix(A,Size);
cout<<B=<<endl;
Out_Matrix(B,Size);*/
start_time=clock();//time(NULL);
BF_Matrix(A,B,C,Size);
end_time=clock();//time(NULL);
spend_time=end_time-start_time;
//Out_Matrix(C,Size);
break;
}
case 'd':
case 'D':{
/*cout<<A=<<endl;
Out_Matrix(A,Size);
cout<<B=<<endl;
Out_Matrix(B,Size);*/
start_time=clock();//time(NULL);
DAC_Matrix(A,B,C,Size);
end_time=clock();//time(NULL);
spend_time=end_time-start_time;
//Out_Matrix(C,Size);
}
}
cout<<所花时间为：<<spend_time/CLOCKS_PER_SEC<<秒\n;
//Out_Matrix(C,Size);
for(int i=0;i<Size;i++)
{ delete [] A[i];
delete [] B[i];
delete [] C[i];
}
delete [] A;
delete [] B;
delete [] C;
return 0;
}
bool BF_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size)
{
for(int i=0;i<Size;i++)
for(int j=0;j<Size;j++)
{
Result[i][j]=0;
for(int m=0;m<Size;m++)
Result[i][j]+=M1[i][m]*M2[m][j];
}
return true;
}
bool Add_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size)
{
for(int i=0;i<Size;i++)
for(int j=0;j<Size;j++)
Result[i][j]=M1[i][j]+M2[i][j];
return true;
}
bool Sub_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size)
{
for(int i=0;i<Size;i++)
for(int j=0;j<Size;j++)
Result[i][j]=M1[i][j]-M2[i][j];
return true;
}
bool DAC_Matrix(Matrix& M1,Matrix& M2,Matrix& Result,int Size)
{
if(Size==1)
{
Result[0][0]=M1[0][0]*M2[0][0];
return true;
}
Matrix A[4],B[4],M[7],Temp[2];
Malloc_Matrix(A,B,M,Temp,Size/2);
Initab(A,B,M1,M2,Size);
//m1=(a00+a11)*(b00+b11)
Add_Matrix(A[0],A[3],Temp[0],Size/2);
Add_Matrix(B[0],B[3],Temp[1],Size/2);
DAC_Matrix(Temp[0],Temp[1],M[0],Size/2);
//m2=(a10+a11)*b00
Add_Matrix(A[2],A[3],Temp[0],Size/2);
DAC_Matrix(Temp[0],B[0],M[1],Size/2);
//m3=a00*(b01-b11)
Sub_Matrix(B[1],B[3],Temp[1],Size/2);
DAC_Matrix(A[0],Temp[1],M[2],Size/2);
//m4=a11*(b10-b00)
Sub_Matrix(B[2],B[0],Temp[1],Size/2);
DAC_Matrix(A[3],Temp[1],M[3],Size/2);
//m5=(a00+a01)*b11
Add_Matrix(A[0],A[1],Temp[0],Size/2);
DAC_Matrix(Temp[0],B[3],M[4],Size/2);
//m6=(a10-a00)*(b00+b01)
Sub_Matrix(A[2],A[0],Temp[0],Size/2);
Add_Matrix(B[0],B[1],Temp[1],Size/2);
DAC_Matrix(Temp[0],Temp[1],M[5],Size/2);
//m7=(a01-a11)*(b10+b11)
Sub_Matrix(A[1],A[3],Temp[0],Size/2);
Add_Matrix(B[2],B[3],Temp[1],Size/2);
DAC_Matrix(Temp[0],Temp[1],M[6],Size/2);
Get_Result(Result,M,Size);
Delete_Matrix(A,B,M,Temp,Size/2);
return true;
}
bool Malloc_Matrix(Matrix A[],Matrix B[],Matrix M[],Matrix Temp[],int Size)
{
for(int i=0;i<4+7+2;i++)
{
if(i<4){
A[i]=new int*[Size];
B[i]=new int*[Size];
}
else if(i<4+7)
M[i-4]=new int*[Size];
else
Temp[i-4-7]=new int*[Size];
}
for(int i=0;i<4+7+2;i++)
{
if(i<4){
for(int j=0;j<Size;j++)
{
A[i][j]=new int[Size];
B[i][j]=new int[Size];
}
}
else if(i<4+7)
for(int j=0;j<Size;j++)
M[i-4][j]=new int[Size];
else
for(int j=0;j<Size;j++)
Temp[i-4-7][j]=new int[Size];
}
return true;
}
bool Initab(Matrix A[],Matrix B[],Matrix& M1,Matrix& M2,int Size)
{
for(int i=0;i<Size/2;i++)
for(int j=0;j<Size/2;j++)
{
A[0][i][j]=M1[i][j];
A[1][i][j]=M1[i][j+Size/2];
A[2][i][j]=M1[i+Size/2][j];
A[3][i][j]=M1[i+Size/2][j+Size/2];
B[0][i][j]=M2[i][j];
B[1][i][j]=M2[i][j+Size/2];
B[2][i][j]=M2[i+Size/2][j];
B[3][i][j]=M2[i+Size/2][j+Size/2];
}
return true;
}
bool Get_Result(Matrix& Result,Matrix M[],int Size)
{
for(int i=0;i<Size/2;i++)
for(int j=0;j<Size/2;j++)
{
Result[i][j]=M[0][i][j]+M[3][i][j]-M[4][i][j]+M[6][i][j];
Result[i][j+Size/2]=M[2][i][j]+M[4][i][j];
Result[i+Size/2][j]=M[1][i][j]+M[3][i][j];
Result[i+Size/2][j+Size/2]=M[0][i][j]+M[2][i][j]-M[1][i][j]+M[5][i][j];
}
return true;
}
bool Delete_Matrix(Matrix A[],Matrix B[],Matrix M[],Matrix Temp[],int Size)
{
for(int i=0;i<4+7+2;i++)
{
if(i<4){
for(int j=0;j<Size;j++)
{
delete [] A[i][j];
delete [] B[i][j];
}
}
else if(i<4+7)
for(int j=0;j<Size;j++)
delete [] M[i-4][j];
else
for(int j=0;j<Size;j++)
delete [] Temp[i-4-7][j];
}
for(int i=0;i<4+7+2;i++)
{
if(i<4){
delete [] A[i];
delete [] B[i];
}
else if(i<4+7)
delete [] M[i-4];
else
delete [] Temp[i-4-7];
}
return true;
}
bool Out_Matrix(Matrix& M,int Size)
{
for(int i=0;i<Size;i++)
{
for(int j=0;j<Size;j++)
cout<<M[i][j]<<' ';
cout<<endl;
}
return true;
}
char Menu()
{
char choose;
cout<<蛮力法------------B\n;
cout<<分治法------------D\n;
cin>>choose;
return choose;
}
望采纳
