我想编写一个能够将2x2矩阵上升到k次方的程序。我知道如何使它平方，但一旦我想达到更高的权力，我努力保存我的结果，并在下一个方程中使用它。a b c d是矩阵中的数字，n是我想在一次内完成的矩阵的数量，k是我想对矩阵取的幂m是我想对这些数字取的模。我知道有一种方法可以使它相当简单，但我想不出一个好方法来在下一个方程中使用我之前做的方程的结果。
#include <iostream>
using namespace std;
int mnoz(int a, int b, int c,int d,int m){
int a2 = (a*a + c*b) % m;
int b2 = (a*b + b*d) % m;
int c2 = (c*a + d*c) % m;
int d2 = (c*b + d*d) % m;
return a2, b2, c2, d2;
}
int main()
{
int a, b, c, d, k, m, n;
int e, f, g, h;
int e2, f2, g2, h2;
cin >> n;
// a^k = (a^2)^k/2
for (int i = 0; i<n; i++){
cin >> a >> b >> c >> d >> k >> m;
if (k == 1){
cout << a << " " << b << " " << c << " " << d << endl;
}
else if (k == 2){
e = (a*a + c*b) % m;
f = (a*b + b*d) % m;
g = (c*a + d*c) % m;
h = (c*b + d*d) % m;
cout << e << " " << f << " " << g << " " << h << endl;
}
else{
if (k % 2 == 0){
e = (a*a + c*b) % m;
f = (a*b + b*d) % m;
g = (c*a + d*c) % m;
h = (c*b + d*d) % m;
int z = (k/2)-1;
for (int j = 0; j < z; j++){
int e2 = e;
int f2 = f;
int g2 = g;
int h2 = h;
mnoz(e2, f2, g2, h2, m);
}
cout << e << " " << f << " " << g << " " << h << endl;
}
}
}
system("pause");
return 0;
}
为了尽量减少乘法次数，可以使用递归方法。
以实数为例，假设你想计算a^n。
- 检查n是偶数还是奇数
- 如果是，则计算
b = a^(n/2)。最后的结果是b*b。 - 奇数则计算
b = a^((n-1)/2。最后的结果是b*b*a。
既然你说的是矩阵而不是数字，你需要能够将任意两个矩阵相乘。您可以为矩阵创建一个类/结构，并添加一个operator*()函数。
下面是一些示例代码。
#include <iostream>
struct Matrix
{
Matrix(double pa, double pb, double pc, double pd) : a(pa), b(pb), c(pc), d(pd) {}
Matrix operator*(Matrix const& rhs) const
{
double an = this->a*rhs.a + this->b*rhs.c;
double bn = this->a*rhs.b + this->b*rhs.d;
double cn = this->c*rhs.a + this->d*rhs.c;
double dn = this->c*rhs.b + this->d*rhs.d;
return Matrix(an, bn, cn, dn);
}
Matrix square() const
{
return (*this)*(*this);
}
double a;
double b;
double c;
double d;
};
Matrix matrixPower(Matrix const& m, int k)
{
if ( k == 1 )
{
return m;
}
Matrix out = matrixPower(m, k/2).square();
if ( k%2 == 1 )
{
return out*m;
}
else
{
return out;
}
}
std::ostream& operator<<(std::ostream& out, Matrix const& m)
{
out << "[ " << m.a << " " << m.b << " ]n";
out << "[ " << m.c << " " << m.d << " ]n";
}
int main()
{
Matrix m(0.4, 0.7, 0.7, 0.4);
std::cout << matrixPower(m, 5) << std::endl;
std::cout << matrixPower(m, 10) << std::endl;
std::cout << matrixPower(m, 15) << std::endl;
};