C++ में Nवां पद ढूंढना (मैट्रिक्स घातांकन उदाहरण)

इस समस्या में, हमें एक पूर्णांक N और एक पुनरावर्ती फ़ंक्शन दिया जाता है जो Nवें पद को अन्य पदों के फ़ंक्शन के रूप में देता है। हमारा कार्य Nवां पद ढूंढने के लिए एक प्रोग्राम बनाना है (मैट्रिक्स घातांकन उदाहरण)।

फ़ंक्शन है

T(n) = 2*( T(n-1) ) + 3*( T(n-2) ) प्रारंभिक मान हैं 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