c++ - 有人可以解释一下这个矩阵求幂函数是如何工作的吗?
问题描述
#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
保存先前调用时的值,还是使用一些垃圾值对其进行初始化?
解决方案
调用 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;
推荐阅读
- excel - VBA Script to Create PDF from Excel Goes to Printer and Doesn't Export File
- discord.js - 如何让我的不和谐机器人只在聊天中工作?
- javascript - 如何修复 Angular *ngFor DOM 节点泄漏
- javascript - 反应:我如何摆脱这个最大更新深度超出错误
- python - Python PhantomJS 无法获取所有 html
- ansible - 如何同步和备份文件
- javascript - 从同一源构建分布式和 NPM 包
- javascript - 如何控制脚本的执行顺序?
- c# - 当在 http://localhost 上使用 OAuth 时,Chrome 默认 SameSite 设置上的 .NET Core 中出现关联失败错误
- python - Python中的基本浏览器。从用户那里获取 URL