我正在尝试优化代码以计算矩阵的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);
    }
}

最佳答案

似乎您的摘录不是您要针对的。我猜你的意思是这样的:

void power(long long A[2][2], long long B[2][2], long long n){
    if (n == 1) {
        multiplySquare(A, B);
    }
    else if(n % 2 == 0) {
        power(A, B, n / 2);
        multiplySquare(A, A);
    }
    else {
        power(A, B, (n - 1) / 2);
        multiplySquare(A, A);
        multiplySquare(A, B);
    }

关于c++ - 计算矩阵的n次幂,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/48859133/

10-11 21:30