---
title: Fibonacci Numbers
disqus: Fibonacci Numbers
---

Chủ đề : Số Fibonacci
===

## Mục lục

[TOC]

## Khái niệm

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Số Fibonacci có rất nhiều ứng dụng trong các lĩnh vực khác nhau như toán sơ cấp, chứng khoán...

Cách tính số Fibonacci thông thường
---

Có 2 cách là ***Đệ quy*** và ***Quy hoạch động*** Ý tưởng là dùng công thức truy hồi để tìm số Fibnacci. Ưu điểm của 2 cách này là code ngắn gọn, dễ hiểu còn nhược điểm là độ phức tạp khá lớn. (Đệ quy tốn $O(2 ^ n)$ còn Quy hoạch động tốn $O(n)$).

Cách tính số Fibonacci tối ưu
---

Cũng có 2 cách để tính số Fibonacci với độ phức tạp bé hơn là ***Nhân ma trận*** và ***Khử nhân ma trận bằng chia để trị***.

- Với phương pháp ***Nhân ma trận***, khi đã có công thức truy hồi, chúng ta dựng ma trận hệ số và ma trận cơ sở, từ đó quy về tính ma trận bậc $N$ của ma trận cơ sở trên. Phần khó nhất của phương pháp này là tìm ra công thức truy hồi và chuyển sang 2 loại ma trận.

- Với phương pháp ***Chia để trị***, chúng ta sẽ thay đổi góc nhìn của bài toán, từ việc tính số Fibonacci thứ $N$ thành bài toán sau: Có đoạn thẳng độ dài $N$. Ở mỗi bước bạn được di chuyển 1 hoặc 2 đơn vị. Hỏi có bao nhiêu cách để bạn đi hết đoạn thẳng đó.

Chúng ta chia đoạn thẳng thành 2 phần đoạn thẳng bằng nhau. Có 2 trường hợp:
- Đi hết cả 2 phần 1 cách độc lập, tức là chúng ta đi trọn vẹn hết đoạn này rồi mới chuyển sang đoạn bên kia (Tính số cách mà bước đi khiến 2 phần không giao nhau).
- Từ 1 đoạn chúng ta không đi hết mà ngay lập tức bước sang đoạn bên kia (Tính số cách mà bước đi khiến 2 phần giao nhau).
Từ các case trên chúng ta sẽ chia dần đoạn thẳng độ dài $N$ thành 2 phần bằng nhau và cứ tiếp tục chia đến hết, như vậy số lần chia tối đa là $log2(N)$.

## So sánh 2 phương pháp tối ưu

Ưu điểm của cả 2 cách đều có độ phức tạp khá tốt, xấp xỉ $O(log(n))$. Tuy nhiên mỗi cách lại có ưu và nhược điểm khác nhau :
- Với ***Nhân ma trận*** như đã nói ở trên, phần khó nhất chính là xác định công thức truy hồi và xác định ma trận cơ sở và ma trận hệ số. Một khi đã xác định được những yếu tố trên thì việc code rất đơn giản và ngắn gọn. Tuy nhiên trong quá trình code nhân ma trận, việc sinh ra ma trận gốc không phải lúc nào cũng đơn giản.
- Với ***Khử nhân ma trận***, có 1 nhược điểm chí tử là không phải bài toán Nhân ma trận nào cũng có thể biến đổi được về ***Chia để trị*** (thông thường những bài toán có thể biến đổi được là bài toán đếm). Vì cách tiếp cận của phương pháp này giống với đệ quy (Quy bài toán lớn về bài toán nhỏ) nên rất dễ hiểu và hữu dụng. Tuy nhiên trong các bài toán phức tạp, việc xét case rất loằng ngoằng và dễ code sai nếu không cẩn thận.

Để có cái nhìn trực quan hơn, chúng ta cùng xét 2 ví dụ sau:
- Bài toán tính số Fibonacci thứ $N$ cơ bản:
- Code ***Chia để trị***:

- Code ***Nhân ma trận***


- Rõ ràng, code Chia để trị là ngắn gọn và dễ hiểu hơn rất nhiều so với code Nhân ma trận.

- Bài H ICPC vòng Quốc Gia năm 2022
- Code ***Nhân ma trận***

- Code ***Chia để trị***

    pair <int, int> solve(long long n) {
        if (n <= 1) return {0, 1};
        if (sum.count(n)) return {sum[n], cnt[n]};

        long long mid = (n + 1) / 2;
        pair <int, int> L = solve(mid);
        pair <int, int> R = solve(n - mid);
        int ans = (1ll * L.first * R.second % Mod + 1ll * R.first * L.second % Mod) % Mod;
        int dem = 1ll * L.second * R.second % Mod;
        {
                //khong to
                pair <int, int> LL = solve(mid - 1);
                pair <int, int> RR = solve(n - mid - 1);
                int tmp = (1ll * LL.first * RR.second + 1ll * RR.first * LL.second) % Mod;
                add(tmp, 3ll * LL.second * RR.second % Mod);
                int g = 1ll * LL.second * RR.second % Mod;

                //to
                if (mid >= 2) {
                       LL = solve(mid - 2);
                        add(tmp, (1ll * LL.first * RR.second + 1ll * RR.first * LL.second) % Mod);
                        add(tmp, 6ll * LL.second * RR.second % Mod);
                        add(g, 1ll * LL.second * RR.second % Mod);

                }
                add(tmp, tmp);
                add(g, g);
                add(ans, tmp);
                add(dem, g);

        }

        {
                //khong to
                pair <int, int> LL = solve(mid - 1);
                pair <int, int> RR = solve(n - mid - 1);
                int tmp = (1ll * LL.first * RR.second + 1ll * RR.first * LL.second) % Mod;
                add(tmp, 3ll * LL.second * RR.second % Mod);
                int g = 1ll * LL.second * RR.second % Mod;

                //to
                if (n - mid >= 2) {
                        RR = solve(n - mid - 2);
                        add(tmp, (1ll * LL.first * RR.second + 1ll * RR.first * LL.second) % Mod);
                        add(tmp, 6ll * LL.second * RR.second % Mod);
                        add(g, 1ll * LL.second * RR.second % Mod);
                }

                add(tmp, tmp);
                add(g, g);
                add(ans, tmp);
                add(dem, g);
        }
        sum[n] = ans; cnt[n] = dem;
        return {ans, dem};
} (*Code đã được AC bởi tài khoản 31tranhoangson trên nền tảng VNOI*).

Chúng ta có thể thấy rõ ràng điểm yếu chí tử của phương pháp khử nhân ma trận: Với bài toán cần xét nhiều trường hợp, phương pháp đòi hỏi 1 đầu óc "sáng suốt và minh mẫn" để không đập bàn phím trong lúc code.