Tìm số hạng thứ N (ví dụ lũy thừa ma trận) trong C++

Giới thiệu

Cho số nguyên N và hàm đệ quy: T(n) = 2×T(n-1) + 3×T(n-2) với T(0)=1, T(1)=1. Tìm T(N) bằng lũy thừa ma trận.

Ví dụ minh họa

Đầu vào

N = 4

Đầu ra

41

Giải thích

T(2) = 2×1 + 3×1 = 5
T(3) = 2×5 + 3×1 = 13
T(4) = 2×13 + 3×5 = 41

Phương pháp 1: Đệ quy/Đệ quy - O(2^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 using recursion is " << calcNthTerm(n);
    return 0;
}

Phương pháp 2: Lũy thừa ma trận - O(log N)

Ma trận chuyển đổi 2×2:

TM = [[2, 3],
      [1, 0]]

Chương trình minh họa

#include <iostream>
using namespace std;
#define MOD 1000000009

long calcNthTerm(long n) {
    if (n <= 1) return 1;
    n--;
    long res[2][2] = {{1,0},{0,1}}; // Ma trận đơn vị
    long tm[2][2] = {{2,3},{1,0}};  // Ma trận chuyển đổi
    
    while (n) {
        if (n & 1) {
            long temp[2][2];
            temp[0][0] = (res[0][0]*tm[0][0] + res[0][1]*tm[1][0]) % MOD;
            temp[0][1] = (res[0][0]*tm[0][1] + res[0][1]*tm[1][1]) % MOD;
            temp[1][0] = (res[1][0]*tm[0][0] + res[1][1]*tm[1][0]) % MOD;
            temp[1][1] = (res[1][0]*tm[0][1] + res[1][1]*tm[1][1]) % MOD;
            memcpy(res, temp, sizeof(res));
        }
        n >>= 1;
        long temp[2][2];
        temp[0][0] = (tm[0][0]*tm[0][0] + tm[0][1]*tm[1][0]) % MOD;
        temp[0][1] = (tm[0][0]*tm[0][1] + tm[0][1]*tm[1][1]) % MOD;
        temp[1][0] = (tm[1][0]*tm[0][0] + tm[1][1]*tm[1][0]) % MOD;
        temp[1][1] = (tm[1][0]*tm[0][1] + tm[1][1]*tm[1][1]) % MOD;
        memcpy(tm, temp, sizeof(tm));
    }
    return (res[0][0]*1 + res[0][1]*1) % MOD;
}

int main() {
    long n = 5;
    cout << n << "th term using matrix exponentiation is " << calcNthTerm(n);
    return 0;
}

Đầu ra

5th term using matrix exponentiation is 121