ম্যাট্রিক্স এক্সপোনেনশিয়েশন দিয়ে Nতম টার্ম খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা 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×5 + 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 found using matrix exponentiation is " << calcNthTerm(n);
    return 0;
}

আউটপুট

5th term found using matrix exponentiation is 121

দক্ষ পদ্ধতি (ম্যাট্রিক্স এক্সপোনেনশিয়েশন)

এই সমস্যা সমাধানের একটি দক্ষ পদ্ধতি হল ম্যাট্রিক্স এক্সপোনেনশিয়েশন কনসেপ্ট ব্যবহার করা। এই পদ্ধতিতে, আমরা একটি ট্রান্সফর্ম ম্যাট্রিক্স ব্যবহার করে Nতম টার্ম বের করব।

এ জন্য আমাদের ট্রান্সফর্ম ম্যাট্রিক্স বের করতে হবে। ম্যাট্রিক্সটি নির্ভরশীল টার্মের সংখ্যায় (এখানে ২) এবং প্রাথমিক মানগুলিতে (T(0)=1, T(1)=1)।

ট্রান্সফর্ম ম্যাট্রিক্স আকার k×k। যা যখন প্রাথমিক ম্যাট্রিক্স k×1 এর সাথে গুণ করা হয়, পরবর্তী টার্ম দিয়ে।

এখানে মানগুলো:

Initial Matrix = [[1], [0]]

Transform Matrix = [[2, 3], [1, 0]]

Tn এর মান = TM^(n-1) × IM

প্রোগ্রাম উদাহরণ (ম্যাট্রিক্স এক্সপোনেনশিয়েশন)

#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 found using matrix exponentiation is " << calcNthTerm(n);
    return 0;
}

আউটপুট

5th term found using matrix exponentiation is 121