এই সমস্যায়, আমাদেরকে একটি পূর্ণসংখ্যা 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 আকারের প্রারম্ভিক ম্যাট্রিক্সের সাথে গুণ করা হলে, পরবর্তী পদটি প্রদান করে।
এখানে মান আছে,
প্রাথমিক ম্যাট্রিক্স =
$$\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
