โปรแกรม C++ หาลำดับฟีโบนัชชีด้วย Matrix Exponentiation

เลขฟีโบนัชชี (Fibonacci numbers) ซึ่งมักแทนด้วย Fn เป็นลำดับที่แต่ละตัวเป็นผลรวมของสองตัวก่อนหน้า เริ่มจาก 0 และ 1 นั่นคือ

F₀ = 0 และ F₁ = 1
และ Fn = Fₙ₋₁ + Fₙ₋₂ สำหรับ n > 1

อัลกอริทึม

Begin
    สร้างอาร์เรย์ 2 มิติสองตัว
    สร้างฟังก์ชันคูณเมทริกซ์
    สร้างฟังก์ชันหายกกำลังของเมทริกซ์
    สร้างฟังก์ชันหาเลขฟีโบนัชชี
    
    Multiply(arr1[2][2], arr2[2][2])
    กำหนดตัวแปร a, b, c, d 4 ตัว
    a = arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0]
    b = arr1[0][0] * arr2[0][1] + arr1[0][1] * arr2[1][1]
    c = arr1[1][0] * arr2[0][0] + arr1[1][1] * arr2[1][0]
    d = arr1[1][0] * arr2[0][1] + arr1[1][1] * arr2[1][1]
    arr1[0][0] = a
    arr1[0][1] = b
    arr1[1][0] = c
    arr1[1][1] = d
    
    Power(arr1[2][2], รับ n เป็น integer)
    ถ้า (n == 0 หรือ n == 1) return;
    arr1[2][2] = {{1,1}, {1,0}}
    power(arr1, n / 2)
    multiply(arr1, arr1)
    ถ้า (n mod 2 != 0)
        multiply(arr1, arr2)
    
    fibonacci_matrix(n)
    arr1[2][2] = {{1,1}, {1,0}}
    ถ้า n == 0 return 0
    power(arr1, n - 1)
    return arr1[0][0]
End

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void multiply(int F[2][2], int M[2][2]) {
    int a = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int b = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int c = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int d = F[1][0] * M[0][1] + F[1][1] * M[1][1];
    F[0][0] = a;
    F[0][1] = b;
    F[1][0] = c;
    F[1][1] = d;
}

void power(int F[2][2], int n) {
    if (n == 0 || n == 1)
        return;
    int M[2][2] = {{1,1},{1,0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}

int fibonacci_matrix(int n) {
    int F[2][2] = {{1,1},{1,0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}

int main() {
    int n;
    while (1) {
        cout<<"Enter the integer n to find nth fibonacci no. (enter 0 to exit):";
        cin>>n;
        if (n == 0) break;
        cout<<fibonacci_matrix(n)<<endl;
    }
    return 0;
}

ผลลัพธ์

Enter the integer n to find nth fibonacci no. (enter 0 to exit): 2
1
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 6
8
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 7
13
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 0