Chương trình C++ tìm số Fibonacci dùng lũy thừa ma trận

Các số Fibonacci, thường ký hiệu là F_n, tạo thành một dãy, gọi là dãy Fibonacci, tức là mỗi số là tổng của hai số trước đó, bắt đầu từ 0 và 1. Đó là:

F0 = 0 và F1 = 1 
Và Fn = Fn-1 + Fn-2 cho n > 1.

Thuật toán

Bắt đầu
    Lấy hai mảng 2 chiều
    Tạo hàm và thực hiện nhân ma trận
    Tạo hàm khác để tìm lũy thừa của ma trận
    Tạo hàm để tìm số Fibonacci
    Multiply(arr1[2][2], arr2[2][2])
    Lấy 4 biến a, b, c, d
    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], nhận số nguyên n)
    Nếu (n == 0 hoặc n == 1) trả về;
    arr1[2][2] = {{1,1}, {1,0}}
    power(arr1, n / 2)
    multiply(arr1, arr1)
    Nếu (n mod 2 khác 0)
        multiply(arr1, arr2)
    fibonacci_matrix(n)
    arr1[2][2] = {{1,1}, {1,0}}
    Nếu n == 0 trả về 0
    power(arr1, n - 1)
    Trả về arr1[0][0]
Kết thúc

Mã ví dụ

#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 << "Nhập số nguyên n để tìm số Fibonacci thứ n (nhập 0 để thoát): "; 
        cin >> n; 
        if (n == 0) break; 
        cout << fibonacci_matrix(n) << endl; 
    } 
    return 0; 
}

Kết quả

Nhập số nguyên n để tìm số Fibonacci thứ n (nhập 0 để thoát): 2 
1 
Nhập số nguyên n để tìm số Fibonacci thứ n (nhập 0 để thoát): 6 
8 
Nhập số nguyên n để tìm số Fibonacci thứ n (nhập 0 để thoát): 7 
13 
Nhập số nguyên n để tìm số Fibonacci thứ n (nhập 0 để thoát): 0