在 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
解释
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项作为对先前项的递归调用,并使用初始值可以找到结果。
程序来说明我们的解决方案的工作,
示例
#includeusing 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< 输出结果 5t使用矩阵求幂找到的h项是 121有效的方法
解决该问题的有效方法是使用矩阵求幂的概念。在这种方法中,我们将使用变换矩阵来查找第N项。
为此,我们需要找到变换矩阵。矩阵取决于相关项的数量,这里恰好是2。初始值是T(0)=1,T(1)=1。
变换矩阵的大小为k*k。当与大小为k*1的初始矩阵相乘时,返回下一项。
这里是值,
初始矩阵=
$$\begin{bmatrix}1\\0\end{bmatrix}$$
变换矩阵=
$$\begin{bmatrix}2&3\\1&0\end{bmatrix}$$
Tn的值表示为TM(n-1)*IM
$$\begin{bmatrix}2&3\\1&0\end{bmatrix}^{n-1}*\begin{bmatrix}2\\3\end{bmatrix}$$
程序来说明我们的解决方案的工作,
示例
#includeusing 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< 输出结果 5t使用矩阵求幂找到的h项是 121