Простое возведение матрицы в степень в С++

Поэтому меня попросили определить матрицу как:

typedef vector<double> vec;
typedef vector<vec> matrix;

и на основе этого напишите некоторые функции, такие как скалярное умножение, сложение и т. д. Все, кроме возведения в степень, работает довольно хорошо, и я понятия не имею, что может вызывать проблемы в этой функции. Прежде всего я определил умножение как:

void multip(const matrix& A, const matrix& B, matrix& result){
    int n = A.size();
    for (int i = 0; i<n; i++){
        for (int j = 0; j<n; j++){
            for (int k = 0; k< n; k++){
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

и на основе этого я хотел сделать рекурсивную (это обязательно) функцию возведения в степень следующим образом:

void expo(matrix& M, unsigned n){
    if (n>0){
        n--;
        multip(M, expo(M, n), M);}
    else{return;}
}

Это не работает, возвращая [Error] Invalid use of void expression. Я понял, почему это не сработает, но понятия не имею, как это обойти. Может ли кто-нибудь помочь мне с этой проблемой?


c++ matrix exponentiation
person Jakub Sapko    schedule 24.03.2020    source источник
comment
expo(M, n) ничего не возвращает. Таким образом, вы не можете использовать значение, которое он возвращает, потому что его нет.   -  person user253751    schedule 24.03.2020
comment
На самом деле, вы не можете выполнить это возведение в степень, если n не является целой степенью двойки, если только вы не разрешите хранить накопленную матрицу в дополнение к начальному значению M.   -  person Ruslan    schedule 24.03.2020
comment
1) Вы используете одну и ту же память для всех матриц - все ваши вычисления пойдут наперекосяк. 2) expo ничего не возвращает, и вы пытаетесь отправить его результат, как если бы это была ссылка на матрицу, в multip.   -  person ALX23z    schedule 24.03.2020
comment
Я написал ALX23z и пользователю 253751, что понял причину этого, хотя не могу найти подходящего решения для этого.   -  person Jakub Sapko    schedule 24.03.2020
comment
Что значит не могу найти решение? Другие ребята уже дали вам решение в комментариях. Либо реорганизуйте код своих операторов, чтобы он фактически возвращал результат (например, matrix multip(const matrix& A, const matrix& B)), либо не используйте повторение, вместо этого выполняйте n обычных умножений.   -  person pptaszni    schedule 24.03.2020
comment
Это должно быть рекурсивно, и после замены пустоты на матрицу это не работает, поэтому нет, решение не было дано.   -  person Jakub Sapko    schedule 24.03.2020

Ответы (1)


arrow_upward
1
arrow_downward

Основная проблема в том, что multip меняет свой 3-й аргумент, поэтому он не может быть таким же, как 1-й, как при вызове multip(M, expo(M, n), M); в вашем коде.

Если вы используете возвращаемые функцией значения для возврата значений, как вы и должны, это становится простым.

Исправления и рабочий пример:

#include <iostream>
#include <vector>

using namespace std;

typedef vector<double> vec;
typedef vector<vec> matrix;

matrix multip(const matrix& A, const matrix& B) {
    size_t n = A.size();
    matrix result(n, vec(n));
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            for (size_t k = 0; k < n; ++k) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return result;
}

matrix expo(matrix const& M, unsigned n) {
    if(n < 1)
        throw;
    if(n == 1)
        return M;
    return multip(M, expo(M, n - 1));
}

void print(matrix const& M) {
    size_t n = M.size();
    for(size_t i = 0; i < n; ++i) {
        for(size_t j = 0; j < n; ++j)
            cout << M[i][j] << ' ';
        cout << '\n';
    }
}

int main() {
    matrix m(2, vec(2));
    m[0][0] = 2;
    m[1][1] = 2;
    print(m);
    cout << '\n';

    m = expo(m, 3);
    print(m);
    cout << '\n';
}

Выходы:

2 0 
0 2 

8 0 
0 8
person Maxim Egorushkin    schedule 24.03.2020