इस समस्या में, हमें एक पूर्णांक N और एक पुनरावर्ती फलन दिया जाता है जो अन्य पदों के फलन के रूप में Nth पद देता है। हमारा काम Nth टर्म (एक मैट्रिक्स एक्सपोनेंटिएशन उदाहरण) खोजने के लिए एक प्रोग्राम बनाना है।
समारोह है
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
समाधान दृष्टिकोण
समस्या को हल करने के लिए एक आसान तरीका रिकर्सन या पुनरावृत्ति का उपयोग कर रहा है। हम पिछले पदों के लिए पुनरावर्ती कॉल के रूप में nth शब्द पा सकते हैं और प्रारंभिक मानों का उपयोग करके परिणाम प्राप्त किया जा सकता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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
कुशल तरीका
समस्या को हल करने के लिए एक कुशल दृष्टिकोण मैट्रिक्स एक्सपोनेंटिएशन की अवधारणा का उपयोग कर रहा है। इस पद्धति में, हम Nth टर्म को खोजने के लिए एक ट्रांसफॉर्म मैट्रिक्स का उपयोग करेंगे।
इसके लिए हमें ट्रांसफॉर्म मैट्रिक्स खोजने की जरूरत है। मैट्रिक्स आश्रित पदों की संख्या पर निर्भर है जो यहां 2 होता है। और प्रारंभिक मान जो T(0) =1, T(1)=1. हैं।
रूपांतरण मैट्रिक्स k*k आकार का होता है। जिसे k*1 आकार के प्रारंभिक मैट्रिक्स से गुणा करने पर अगला पद लौटाता है।
ये रहे मान,
प्रारंभिक मैट्रिक्स =
$$\शुरू{bmatrix}1 \\0 \end{bmatrix}$$
रूपांतरण मैट्रिक्स =
$$\शुरू{bmatrix}2&3 \\1&0 \end{bmatrix}$$
Tn का मान TM (n-1) . के रूप में दिया जाता है *आईएम
$$\शुरू{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