matrix.cpp

矩阵相乘

/****************************************/
/*程序:		矩阵相乘	*/
/*作者:		Eric Roy	*/
/*日期:		2007-4-16	*/
/*调试:		VC6			*/
/****************************************/
/**********简单起见,仅研究方阵***********/

#include <iostream>
using namespace std;
#define NH 4		//矩阵大小
int a[NH][NH]={	{1,1,4,1},
				{1,1,1,1},
				{1,1,1,1},
				{1,1,1,1}};
int b[NH][NH]={	{2,2,2,2},
				{3,3,3,3},
				{0,1,0,1},
				{2,3,3,4}};
int c[NH][NH]={	{0,0,0,0},
				{0,0,0,0},
				{0,0,0,0},
				{0,0,0,0}};


void Matrix_Multiply(int n, int A[NH][NH], int B[NH][NH], int C[NH][NH])	//矩阵乘法
{
	int i=0,j=0,p=0;
	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(p=0;p<n;p++)
			{
				C[i][j] += A[i][p] * B[p][j];
			}
		}
	}
}

void Matrix_Plus(int n, int A[NH][NH], int B[NH][NH], int C[NH][NH])		//矩阵加法
{
	int i=0,j=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			C[i][j]=A[i][j] + B[i][j];
		}
	}
}

void Matrix_Minus(int n, int A[NH][NH], int B[NH][NH], int C[NH][NH])		//矩阵减法
{
	int i=0,j=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			C[i][j]=A[i][j] - B[i][j];
		}
	}
}

void Strassen(int n, int A[NH][NH], int B[NH][NH], int C[NH][NH])
{
	if(n==2) Matrix_Multiply(n,A,B,C);
	else
	{
		int l=n/2;
		int i=0,j=0;
		int A11[NH][NH],A12[NH][NH],A21[NH][NH],A22[NH][NH];
		int B11[NH][NH],B12[NH][NH],B21[NH][NH],B22[NH][NH];
		for(i=0;i<l;i++)		//两个相乘矩阵分为四段
		{
			for(j=0;j<l;j++)
			{
				A11[i][j]=A[i][j];
				A12[i][j]=A[i][j+l];
				A21[i][j]=A[i+l][j];
				A22[i][j]=A[i+l][j+l];
				B11[i][j]=B[i][j];
				B12[i][j]=B[i][j+l];
				B21[i][j]=B[i+l][j];
				B22[i][j]=B[i+l][j+l];
			}
		}

/*****************测试部分*******************/
/*
		cout<<"A11: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<A11[i][j];
			}
			cout<<endl;
		}

		cout<<"B12: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<B12[i][j];
			}
			cout<<endl;
		}

		cout<<"B22: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<B22[i][j];
			}
			cout<<endl;
		}
*/
/********************************************/

		int M1[NH][NH],M2[NH][NH],M3[NH][NH],M4[NH][NH],M5[NH][NH],M6[NH][NH],M7[NH][NH];
		int T1[NH][NH],T2[NH][NH],T3[NH][NH],T4[NH][NH],T5[NH][NH],T6[NH][NH],T7[NH][NH],T8[NH][NH],T9[NH][NH],T10[NH][NH];
		//矩阵加减法结果矩阵

		Matrix_Minus(l,B12,B22,T1);	//B12-B22

/*****************测试部分*******************/
/*
		cout<<"T1: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<T1[i][j];
			}
			cout<<endl;
		}
*/
/********************************************/

		Matrix_Plus(l,A11,A12,T2);	//A11+A12
		Matrix_Plus(l,A21,A22,T3);	//A21+A22
		Matrix_Minus(l,B21,B11,T4);	//B21-B11
		Matrix_Plus(l,A11,A22,T5);	//A11+A22
		Matrix_Plus(l,B11,B22,T6);	//B11+B22
		Matrix_Minus(l,A12,A22,T7);	//A12-A22
		Matrix_Plus(l,B21,B22,T8);	//B21+B22
		Matrix_Minus(l,A11,A21,T9);	//A11-A21
		Matrix_Plus(l,B11,B12,T10);	//B11+B12

		Strassen(l,A11,T1,M1);
		Strassen(l,T2,B22,M2);
		Strassen(l,T3,B11,M3);
		Strassen(l,A22,T4,M4);
		Strassen(l,T5,T6,M5);
		Strassen(l,T7,T8,M6);
		Strassen(l,T9,T10,M7);

		int C11[NH][NH],C12[NH][NH],C21[NH][NH],C22[NH][NH];
		Matrix_Plus(l,M5,M4,C11);		//C11=M5+M4
		Matrix_Minus(l,C11,M2,C11);	//(M5+M4)-M2
		Matrix_Plus(l,C11,M6,C11);	//(M5+M4-M2)+M6

		Matrix_Plus(l,M1,M2,C12);		//C12=M1+M2

		Matrix_Plus(l,M3,M4,C21);		//C21=M3+m4

		Matrix_Plus(l,M5,M1,C22);		//C22=M5+M1
		Matrix_Minus(l,C22,M3,C22);	//(M5+M1)-M3
		Matrix_Minus(l,C22,M7,C22);	//(M5+M1-M3)-M7

		for(i=0;i<l;i++)	//四个结果矩阵合成一个矩阵
		{
			for(j=0;j<l;j++)
			{
				C[i][j]=C11[i][j];
				C[i][j+l]=C12[i][j];
				C[i+l][j]=C21[i][j];
				C[i+l][j+l]=C22[i][j];
			}
		}

/*****************测试部分*******************/
/*
		cout<<"T1: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<T1[i][j];
			}
			cout<<endl;
		}

		delete [] T1;

		cout<<"T1: "<<endl;
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				cout<<"\t"<<T1[i][j];
			}
			cout<<endl;
		}
*/
/********************************************/
	}
}

void main(int)
{
//	const int n=NH;
	int i=0,j=0;

	cout<<endl<<"矩阵A为: "<<endl;
	for(i=0;i<NH;i++)
	{
		for(j=0;j<NH;j++)
		{
			cout<<"\t"<<a[i][j];
		}
		cout<<endl;
	}

	cout<<endl<<"矩阵B为: "<<endl;
	for(i=0;i<NH;i++)
	{
		for(j=0;j<NH;j++)
		{
			cout<<"\t"<<b[i][j];
		}
		cout<<endl;
	}

	Strassen(NH, a, b, c);


	cout<<endl<<"结果矩阵C为: "<<endl;
	for(i=0;i<NH;i++)
	{
		for(j=0;j<NH;j++)
		{
			cout<<"\t"<<c[i][j];
		}
		cout<<endl;
	}
/*	
	int d[NH][NH]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
	Matrix_Multiply(NH, a, b, d); 
	cout<<endl<<"结果矩阵D为: "<<endl;
	for(i=0;i<NH;i++)
	{
		for(j=0;j<NH;j++)
		{
			cout<<"\t"<<d[i][j];
		}
		cout<<endl;
	}
*/
	system("pause");
}