이 문제에서는 정수 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