# Dãy số fibonacci và ứng dụng
**[Table of Contents]**

[toc]

## Giới thiệu
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, 1 hoặc 1, 1. Và từ phần tử thứ 3 trở đi, các phần tử sau luôn bằng tổng hai phần tử liền trước.

Công thức truy hồi của dãy số fibonacci:


* ***Lưu ý:** Tuỳ theo định nghĩa từ bài tập hoặc nhu cầu sử dụng, dãy số fibonacci có thể bắt đầu với số khác nhau. Ở đây ta định nghĩa dãy bắt đầu bằng 1, 1.*

## Hướng dẫn cài đặt

- Sau đây là các cách cài đặt chương trình tìm số fibonacci thứ N:

**Dùng vòng lặp for**

const int N = 50;
int f[N];

int nthFibo(int n)
{
    //trường hợp cơ sở
    f[1] = f[2] = 1;

    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];

    return f[n];
}
    

* Ta dễ dàng nhận thấy vòng `for` với độ phức tạp: O(n)

**Dùng đệ qui**

int nthFibo(int n)
{
    //trường hợp cơ sở
    if (n == 1 || n == 2) return 1;
    
    return nthFibo(n - 1) + nthFibo(n - 2);
}


Trong `nthFibo(n)` sẽ có hai hàm con được gọi: `nthFibo(n - 1)` và `nthFibo(n - 2)`. Khi đó cứ mỗi `n` sẽ có 2 lần gọi hàm cho đến khi `n` giảm về 1 hoặc 2.
* Vậy độ phức tạp: O(2^n^).

**Dùng đệ qui có nhớ**

const int N = 50;
int f[N];

int nthFibo(int n)
{
    // nếu số fibonacci thứ n đã được tính thì ta không cần tính lại
    if (f[n] > 0) return f[n];
    
    if (n == 1 || n == 2) return 1;
    
    // Lưu f[n] = nthFibo(n - 1) + nthFibo(n - 2), sau đó trả về f[n]
    return f[n] = nthFibo(n - 1) + nthFibo(n - 2);
}

* Độ phức tạp: O(n)

*Vì mỗi số fibonacci chỉ được tính đúng 1 lần*

## Bài toán số con thỏ

**Bài toán:**
Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi n tháng bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh?

- **Theo đề bài ta có:**
Tháng thứ nhất: **có 1** đôi thỏ *(đôi thỏ 1 chưa đủ tháng)*.
Tháng thứ hai: **có 1** đôi thỏ *(đôi thỏ 1 chưa đủ tháng)*.
Tháng thứ ba: **có 2** đôi thỏ *(đôi thỏ 1 sinh đôi thỏ 2)*.
Tháng thứ tư: **có 3** đôi thỏ *(đôi thỏ 1 sinh đôi thỏ 3; đôi thỏ 2 chưa đủ tháng)*.
Tháng thứ năm: **có 5** đôi thỏ *(đôi thỏ 1, 2 sinh đôi thỏ 4, 5; đôi thỏ 3 chưa đủ tháng)*.

Gọi số lượng đôi thỏ tại tháng thứ n là `numRabbits(n)`.

Nhận thấy rằng, tại tháng thứ n chỉ có thêm các đôi thỏ do các đôi thỏ ở tháng thứ n - 2 sinh. Khi đó `numRabbits(n)` = `numRabbits(n - 1) + numRabbits(n - 2)`
(số lượng hiện tại + số lượng mới được sinh).

Vậy số lượng đôi thỏ sau `n` tháng là số fibonacci thứ `n` với dãy fibo được bắt đầu từ 1:

const int N = 50;
int f[N];

int numRabbits(int n)
{
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];

    return f[n];
}

## Nâng cao

Áp dụng nhân ma trận để giảm độ phức tạp khi tìm số fibonacci thứ `n`
Tham khảo tại: [VNOI Wiki - Nhân ma trận](https://vnoi.info/wiki/algo/trick/matrix-multiplication.md)

## Một số bài tập ứng dụng

* **VNOJ**
[Lát gạch](https://oj.vnoi.info/problem/latgach)
[Lát gạch 4](https://oj.vnoi.info/problem/latgach4)
* **Ntucoder**:
[FIBO4](http://ntucoder.net/Problem/Details/1165)