我正在尝试优化我的代码以计算矩阵的 n 次方。
之前我只会调用 multiplySquare
n
次,但那太慢了。问题是,它构建得很好,但是当我运行它时,我遇到了退出值 1
的失败。我相信我的算法是正确的,那么是什么原因造成的呢?
[编辑] 添加了递归终止条件,但我仍然遇到同样的错误。
[再次编辑] 我再次重写了递归部分,现在它似乎可以工作,但仅适用于 n
的某些输入。我将不得不更多地使用它。任何帮助,将不胜感激。
void multiplySquare(long long A[2][2], long long B[2][2]){
long long result[2][2];
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
result[i][j] = 0;
for (int k = 0; k < 2; k++){
result[i][j] += A[i][k] * B[k][j];
}
}
}
for (int i=0; i<2; i++){
for (int j=0; j<2; j++){
A[i][j] = result[i][j];
}
}
}
void power(long long A[2][2], long long B[2][2], long long n){
if(n/2 != 0){
power(A, B, n/2);
}
if(n%2 != 0){
multiplySquare(A, B);
}
}
最佳答案
有效计算数字 x
的 N
次方的算法是:
如果N
为零,返回1
。
如果N
为1,返回x
。
计算 (N/2)
次方。 y = x^(N/2)
如果 N
是偶数,返回 y*y
如果 N
是奇数,返回 x*y*y
如果您将该逻辑转化为您的案例,您将需要以下内容:
// Assuming that the result is returned in B.
void power(long long A[2][2], long long B[2][2], long long n)
{
if ( n == 0 )
{
makeIdentity(B);
return;
}
if ( n == 1 )
{
assign(A, B); // Make B same as A.
return;
}
power(A, B, n/2);
multiplySquare(B, B);
if(n % 2 != 0)
{
multiplySquare(B, A);
}
}
关于c++ - 计算矩阵的 n 次方,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48859133/