数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中求第 N 项（矩阵幂运算示例）
在这个问题中，我们给定一个整数 N 和一个递归函数，该函数给出了第 N 项作为其他项的函数。我们的任务是创建一个程序来查找第 N 项（矩阵幂运算示例）。
函数为：
T(n) = 2*( T(n-1) ) + 3*( T(n-2) ) Initial values are T(0) = 1 , T(1) = 1
让我们来看一个例子来理解这个问题：
输入
N = 4
输出
41
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
解释
T(4) = 2* (T(3)) + 3*(T(2)) T(4) = 2* ( 2*(T(2)) + 3*(T(1)) ) + 3*( 2* (T(1)) + 3*(T(0)) ) T(4) = 2*( 2*(2* (T(1)) + 3*(T(0))) + 3*(1) ) + 3*(2*(1) + 3*(1)) T(4) = 2*(2 * (2 *(1) + 3*(1) )) + 3 ) + 3 * (5) T(4) = 2*(2 * (2 + 3) + 3) + 15 T(4) = 2*(2 * (5) + 3) + 15 T(4) = 2*(10 + 3) + 15 T(4) = 2*(13) + 15 = 26 + 15 = 41
解决方案方法
解决这个问题的一个简单方法是使用递归或迭代。我们可以将第 n 项作为对前几项的递归调用，并使用初始值来找到结果。
程序说明了我们解决方案的工作原理：
示例
#include <iostream> using namespace std; long calcNthTerm(long n) { if(n == 0 || n == 1) return 1; return ( ( 2*(calcNthTerm(n-1)) ) + ( 3*(calcNthTerm(n-2)) ) ); } int main() { long n = 5; cout<<n<<"th term of found using matrix exponentiation is "<<calcNthTerm(n); return 0; }
输出
5th term of found using matrix exponentiation is 121
高效方法
解决这个问题的一个高效方法是使用矩阵幂运算的概念。在这种方法中，我们将使用一个变换矩阵来查找第 N 项。
为此，我们需要找到变换矩阵。该矩阵取决于相关项的数量（此处为 2），以及初始值 T(0) = 1, T(1)= 1。
变换矩阵的大小为 k*k。当它与大小为 k*1 的初始矩阵相乘时，会返回下一项。
以下是值：
初始矩阵 =
[10]
变换矩阵 =
[2310]
Tn 的值给出为 TM(n-1)*IM
[2310]n−1∗[11]
程序说明了我们解决方案的工作原理：
示例
#include <iostream> using namespace std; #define MOD 1000000009 long calcNthTerm(long n) { if (n <= 1) return 1; n--; long resultantMat[2][2] = { 1, 0, 0, 1 }; long transMat[2][2] = { 2, 3, 1, 0 }; while (n) { long tempMat[2][2]; if (n & 1) { tempMat[0][0] = (resultantMat[0][0] * transMat[0][0] + resultantMat[0][1] * transMat[1][0]) % MOD; tempMat[0][1] = (resultantMat[0][0] * transMat[0][1] + resultantMat[0][1] * transMat[1][1]) % MOD; tempMat[1][0] = (resultantMat[1][0] * transMat[0][0] + resultantMat[1][1] * transMat[1][0]) % MOD; tempMat[1][1] = (resultantMat[1][0] * transMat[0][1] + resultantMat[1][1] * transMat[1][1]) % MOD; resultantMat[0][0] = tempMat[0][0]; resultantMat[0][1] = tempMat[0][1]; resultantMat[1][0] = tempMat[1][0]; resultantMat[1][1] = tempMat[1][1]; } n = n / 2; tempMat[0][0] = (transMat[0][0] * transMat[0][0] + transMat[0][1] * transMat[1][0]) % MOD; tempMat[0][1] = (transMat[0][0] * transMat[0][1] + transMat[0][1] * transMat[1][1]) % MOD; tempMat[1][0] = (transMat[1][0] * transMat[0][0] + transMat[1][1] * transMat[1][0]) % MOD; tempMat[1][1] = (transMat[1][0] * transMat[0][1] + transMat[1][1] * transMat[1][1]) % MOD; transMat[0][0] = tempMat[0][0]; transMat[0][1] = tempMat[0][1]; transMat[1][0] = tempMat[1][0]; transMat[1][1] = tempMat[1][1]; } return (resultantMat[0][0] * 1 + resultantMat[0][1] * 1) % MOD; } int main() { long n = 5; cout<<n<<"th term of found using matrix exponentiation is "<<calcNthTerm(n); return 0; }
输出
5th term of found using matrix exponentiation is 121
更新于：2021年3月13日
浏览量 155 次
广告