在 C++ 中查找第 N 项（矩阵求幂示例）

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们得到一个整数 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 项作为对先前项的递归调用，并使用初始值可以找到结果。

程序来说明我们的解决方案的工作，

示例

#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<<"t使用矩阵求幂找到的 h 项是 "<<calcNthTerm(n);
   return 0;
}
输出结果
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}$$

程序来说明我们的解决方案的工作，

示例

#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<<"t使用矩阵求幂找到的 h 项是 "<<calcNthTerm(n);
   return 0;
}
输出结果
5t使用矩阵求幂找到的 h 项是 121

以上是 在 C++ 中查找第 N 项（矩阵求幂示例） 的全部内容， 来源链接： utcz.com/z/311376.html

回到顶部