矩阵乘法在程序中的使用----如有错误欢迎指出

矩阵的乘法在程序中作用有很多的体现。

前两天接触的那个题，可以使用矩阵连乘，然后，二分计算快速解答。由于是第一次接触，花了好一会才明白点所以然，这里小小的总结一下。

首先，使用矩阵连乘的好处：可以实现快速计算。

其次，如何把问题转化成矩阵连乘的形式。

这里举例说明。

拿fibonacci举例。

fibonacci公式：F[n]=F[n-1]+F[n-2]；

可以先观察下这个式子：

1 1

【F[n-1]，F[n-2] 】* 【 】 (囧~~~不会在这里插入数学公式，只好省略矩阵的大括号)

1 0

=【F[n-1]+F[n-2]，F[n-1]】

这时还没有发现什么的话，再乘一次

1 1

【F[n-1]+F[n-2]，F[n-1] *【 】

1 0

=【2F[n-1]+F[n-2]，F[n-1]+F[n-2]】

也就是说，

1 1

F[1]=【0,1】* 【 】 的前一个项

1 0

即

1 1

F[n]=【0,1】 * 【 】 的n次幂的第一项

1 0

到此就把题目转化成了求矩阵乘法。其中，

1 1

【 】 是该矩阵乘法的初始矩阵。【0,1】的名字不知道叫什么，假定是结果矩阵

1 0

再者，初始矩阵的求法

这里举例说明，假设F[n]=3F[n-1]-F[n-2]（牵扯m个F[n]初始矩阵就是m*m的矩阵，结果矩阵就是1*m的矩阵）

此时，m=2,由于肯定会知道F[0]，F[1]，F[2]这些初始值。即结果矩阵就是【F[n-1]，F[n-2]】

利用矩阵的求法，可以计算出初始矩阵。

a b

【F[n-1],F[n-2]】*【 】观察可知，a=3,c=-1(第一行乘第一列得F[n])；b=1,d=0(第一行乘以第二列得F[n-1])。

c d

最后，如何实现快速计算。

利用二分法，计算矩阵的n次幂，由于m^2=(m*m)，m^4=m^2*m^2,m^8=m^4*m^4,计算m^8只需要乘3次，可以节省很多时间。这里不再贴代码。

在这里附上我的Matrix模板

#include<iostream>
template<class T> 
class Matrix
{
public:
	Matrix();//构造函数
	Matrix(const Matrix<T> &m);//拷贝构造函数
	Matrix(int r,int c);//初始化一个矩阵，利用行和列
	~Matrix(){delete m_elem;}
	void display();
	void trans();//转置
	Matrix operator =(const Matrix<T> & m);
	T & operator[](int pos);
	Matrix operator +(const Matrix<T> & m);
	Matrix operator -(const Matrix<T> & m);
	Matrix operator *(const Matrix<T> & m);
	bool operator ==(const Matrix<T> & m);	
private:
	T * m_elem;//指向元素的指针(类)
	int row,column;
};
template<class T>
Matrix<T>::Matrix(int r,int c):row(r),column(c)
{
	if (row==0||column==0)
	{
		m_elem=NULL;
	}
	else
	{
		m_elem= new T[row*column];
		if (!m_elem)
		{
			cout<<"无法分配内存";
		}
		cout<<"创建一个"<<row<<"行"<<column<<"列的矩阵"<<endl;
		for (int i=0;i<row;i++)
		{
			for (int j=0;j<column;j++)
			{
				cin>>m_elem[i*column+j];
			}
		}
	}
}
template <class T>
Matrix<T>::Matrix()
{
	cout<<"\n请输入行数 列数:";
	cin>>row>>column;
	
	m_elem = new T[row * column];
	if (!m_elem)
	{
		cout<<"无法分配内存";
	}
	cout<<"创建一个"<<row<<"行"<<column<<"列的矩阵"<<endl;
	for (int i=0;i<row;i++)
	{
		for (int j=0;j<column;j++)
		{
			cin>>m_elem[i*column+j];
		}
	}
}
template <class T>
Matrix<T>::Matrix(const Matrix<T> &m)
{
	this->m_elem = new T[m.row * m.column];
	
	if (!m_elem)
	{
		cout<<"无法分配内存";
	}
	
	row = m.row;
	column = m.column;
	memcpy(m_elem,m.m_elem,sizeof(T) * row * column);	
}
template<class T>
T & Matrix<T>::operator[](int pos)
{
	return m_elem[pos];
}
template<class T>
Matrix<T> Matrix<T>::operator +(const Matrix<T> & m)
{
	Matrix<T> mresult(*this);
	if (row!=Matrix::row||this->column!=Matrix::column)
	{
		cout<<"不同的矩阵不能相加";
	}
	else
	{
		for (int i=0;i<row*column;i++)
		{
			mresult.m_elem[i]+=m.m_elem[i];
		}
	}
	return mresult;
}
template<class T>
Matrix<T> Matrix<T>::operator -(const Matrix<T> & m)
{
	{
		if (this.row!=Matrix::row||this->column!=Matrix::column)
		{
			cout<<"不同的矩阵不能相减";
		}
		else
		{
			Matrix<T> mresult(*this);
			for (int i=0;i<row*column;i++)
			{
				mresult.m_elem[i]-=m.m_elem[i];
			}
			return mresult;
		}
	}
}
template<class T>
Matrix<T> Matrix<T>::operator *(const Matrix<T> & m)
{
	Matrix<T> mresult(0,0);
	mresult.m_elem=new T[row*m.column];
	mresult.row=row;
	mresult.column=m.column;
	if (column!=m.row)
	{
		cout<<"不符合计算要求";
	}
	else
	{
		for (int i=0;i<row*m.column;i++)
		{
			int sum=0;
			for (int j=0;j<=m.column;j++)
			{
				sum+=m_elem[i/m.column*column+j]*m.m_elem[m.column*j+(i%m.column)];
			}
			mresult.m_elem[i]=sum;
		}
	}
	return mresult;
}
template<class T>
void Matrix<T>::trans()
{
	Matrix<T> mresult(*this);
	int num=row*column-1;
	for (int i=0;i<=num;i++)
	{
		mresult.m_elem[i]=m_elem[(column*i)%num];
	}
	//return mresult;
}
template <class T>
Matrix<T> Matrix<T>::operator = (const   Matrix<T> &m)
{
	this->m_elem = new T[m.row * m.column];
	
	if (!m_elem)
	{
		cout<<"无法分配内存";
	}
	
	row = m.row;
	column = m.column;
	memcpy(m_elem,m.m_elem,sizeof(T) * row * column);
	
	return *this;
}

template<class T>
bool Matrix<T>::operator ==(const Matrix<T> & m)
{
	if (row!=m.row||column!=m.column)
	{
		return false;
	}
	else
		for (int i=0;i<row*column;i++)
		{
			if(m_elem[i]!=m.m_elem[i])
			{
				return false;
			}
		}
		return true;
}
template <class T>
void Matrix<T>::display()
{
	for (int i=0;i<row*column;i++)
	{
		cout<<m_elem[i]<<" ";
		if (i&&i%column)
		{
			cout<<endl;
		}
	}
}