Các số Fibonacci

Bài học 4 trên 20 trong khóa học Câu đố toán học của Coddy.

Mỗi số hạng mới trong dãy Fibonacci được tạo bằng cách cộng hai số hạng trước đó.

a[n+2]=a[n]+a[n+1]

Bắt đầu với 1 và 2, 10 số hạng đầu tiên nhỏ hơn 100 là:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Dãy Fibonacci xuất hiện trong sách Liber Abaci (Sách tính toán, 1202) của Fibonacci, trong đó dãy này được dùng để tính sự tăng trưởng của quần thể thỏ. Fibonacci xét sự tăng trưởng của một quần thể thỏ lý tưởng hóa (không thực tế về mặt sinh học), với giả định rằng: một cặp thỏ mới sinh có thể sinh sản được thả vào một cánh đồng; mỗi cặp thỏ sinh sản giao phối khi được một tháng tuổi và vào cuối tháng thứ hai, chúng luôn sinh thêm một cặp thỏ; thỏ không bao giờ chết mà tiếp tục sinh sản mãi mãi. Fibonacci đặt câu đố: sau một năm sẽ có bao nhiêu cặp thỏ?

Vào cuối tháng thứ n, số cặp thỏ bằng số cặp đã trưởng thành (tức là số cặp trong tháng n – 2) cộng với số cặp còn sống vào tháng trước (tháng n – 1). Số cặp trong tháng thứ n là số Fibonacci thứ n. [Wikipedia, bách khoa toàn thư miễn phí]

Thử thách

Dễ

Viết code Python calcFibonacciNums nhận một số tự nhiên, <i>N</i>, rồi trả về số hạng của dãy Fibonacci bắt đầu bằng 1 và 2 có giá trị không vượt quá <i>N</i>.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = calcFibonacciNums(n);
    printf("%d\n", r);
    return 0;
}