ในปัญหานี้ เราได้รับจำนวนเต็ม N และฟังก์ชันแบบเรียกซ้ำซึ่งกำหนดพจน์ที่ N เป็นฟังก์ชันของเทอมอื่นๆ งานของเราคือสร้างโปรแกรมเพื่อค้นหาเทอมที่ N (ตัวอย่างการยกกำลังเมทริกซ์)
ฟังก์ชันคือ
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
แนวทางการแก้ปัญหา
แนวทางง่ายๆ ในการแก้ปัญหาคือการใช้การเรียกซ้ำหรือการวนซ้ำ เราสามารถหาเทอมที่ 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
