Может ли кто-нибудь объяснить мне, как работает эта функция возведения в степень матрицы? - PullRequest
Новая
       39

Может ли кто-нибудь объяснить мне, как работает эта функция возведения в степень матрицы?

0 голосов
/ 03 февраля 2020 
#include <bits/stdc++.h>
using namespace std;
//Program to find the nth fib number using matrix exponentation
void multi_mat(int A[3][3], int B[3][3])
{
    int res_mat[3][3];
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            res_mat[i][j] = 0;
            for (int k = 0; k < 3; k++)
            {
                res_mat[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            A[i][j] = res_mat[i][j];
        }
    }
}
int power(int F[3][3], int n)
{
    int M[3][3] = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
    if (n == 1)
        return F[0][0] + F[0][1];
    power(F, n / 2);
    multi_mat(F, F);
    if (n % 2 != 0)
        multi_mat(F, M);
    return F[0][0] + F[0][1];
}
int findfib(int n)
{
    int F[3][3] = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    return power(F, n - 2);
}
int main()
{
    int n = 0;
    cin >> n;
    cout << "The fib of the " << n << "th number is : " << findfib(n) << '\n';
    return 0;
}

Это код для возведения в степень матрицы. У меня проблемы с пониманием, где хранятся данные при вызове функции multi_mat. Кроме того, когда я вызываю функцию multi_mat, матрица res_mat содержит значения, когда она была ранее вызвана, или инициализирует ее каким-то ненужным значением?

1 Ответ

0 голосов
/ 03 февраля 2020

где данные сохраняются при вызове функции multi_mat

Первоначально они хранятся в res_mat: 

res_mat[i][j] += A[i][k] * B[k][j];

, но через несколько строк, он копируется в A: 

A[i][j] = res_mat[i][j];

Таким образом, в конце выполнения местом, где хранится результат, является первый аргумент A, который вне функции называется F, так как функция была вызвана следующим образом: 

multi_mat(F, F);

содержит ли матрица res_mat значения, когда она была ранее вызвана, или инициализирует ее каким-либо нежелательным значением?

Да в этот момент он имеет «ненужные» значения: 

int res_mat[3][3];

, но позже он инициализируется нулями, когда эта строка выполняется для каждого элемента матрицы: 

res_mat[i][j] = 0;
...