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番目の用語は、前の用語への再帰呼び出しとして見つけることができ、初期値を使用して結果を見つけることができます。

ソリューションの動作を説明するプログラム

例

#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の初期行列を掛けると、次の項が返されます。

値は次のとおりです

初期行列=

$$ \ 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<<"th term of found using matrix exponentiation is "<<calcNthTerm(n);
   return 0;
}

出力

5th term of found using matrix exponentiation is 121