Trong bài toán này, chúng ta được cung cấp một số nguyên N và một hàm đệ quy có số hạng thứ N là một hàm của các số hạng khác. Nhiệm vụ của chúng tôi là tạo một chương trình để Tìm số hạng thứ N (Một ví dụ lũy thừa ma trận).
Chức năng là
T(n) = 2*( T(n-1) ) + 3*( T(n-2) ) Initial values are T(0) = 1 , T(1) = 1
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 4
Đầu ra
41
Giải thích
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
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là sử dụng đệ quy hoặc lặp. Chúng ta có thể tìm số hạng thứ n dưới dạng lời gọi đệ quy tới các số hạng trước đó và sử dụng các giá trị ban đầu, kết quả có thể được tìm thấy.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
5th term of found using matrix exponentiation is 121
Cách tiếp cận hiệu quả
Một cách tiếp cận hiệu quả để giải quyết vấn đề là sử dụng khái niệm lũy thừa ma trận. Trong phương pháp này, chúng tôi sẽ sử dụng ma trận biến đổi để tìm số hạng thứ N.
Đối với điều này, chúng ta cần tìm ma trận biến đổi. Ma trận phụ thuộc vào số lượng các số hạng phụ thuộc mà xảy ra ở đây là 2. Và các giá trị ban đầu là T (0) =1, T (1) =1.
Ma trận biến đổi có kích thước k * k. Khi nhân với ma trận ban đầu có kích thước k * 1, sẽ trả về số hạng tiếp theo.
Đây là các giá trị,
ma trận ban đầu =
$$ \ begin {bmatrix} 1 \\ 0 \ end {bmatrix} $$
Chuyển đổi ma trận =
$$ \ begin {bmatrix} 2 &3 \\ 1 &0 \ end {bmatrix} $$
Các giá trị của Tn được đưa ra dưới dạng TM (n-1) * IM
$$ \ begin {bmatrix} 2 &3 \\ 1 &0 \ end {bmatrix} ^ {n-1} * \ begin {bmatrix} 2 \\ 3 \ end {bmatrix} $$
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
5th term of found using matrix exponentiation is 121