Liczby Fibonacciego

Lekcja 4 z 20 w kursie Zagadki matematyczne w Coddy.

Każdy kolejny wyraz ciągu Fibonacciego powstaje przez dodanie dwóch poprzednich wyrazów.

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

Zaczynając od 1 i 2, pierwsze 10 wyrazów mniejszych niż 100 to:

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

Ciąg Fibonacciego pojawia się w książce Liber Abaci (Księga rachunków, 1202) Fibonacciego, gdzie jest wykorzystywany do obliczania wzrostu populacji królików. Fibonacci rozważa wzrost wyidealizowanej (biologicznie nierealistycznej) populacji królików, zakładając, że: nowo narodzona para królików zdolnych do rozmnażania zostaje umieszczona na polu; każda para królików zdolnych do rozmnażania łączy się w parę w wieku jednego miesiąca, a pod koniec drugiego miesiąca zawsze wydaje na świat kolejną parę królików; króliki nigdy nie umierają, lecz rozmnażają się bez końca. Fibonacci zadał zagadkę: ile par będzie po roku?

Pod koniec n-tego miesiąca liczba par królików jest równa liczbie dojrzałych par (czyli liczbie par w miesiącu n – 2) plus liczbie par żyjących w poprzednim miesiącu (miesiącu n – 1). Liczba par w n-tym miesiącu jest n-tą liczbą Fibonacciego. [Wikipedia, wolna encyklopedia]

Wyzwanie

Łatwy

Napisz kod Pythona calcFibonacciNums, który przyjmuje liczbę naturalną <i>N</i> i zwraca liczbę wyrazów ciągu Fibonacciego, zaczynającego się od 1 i 2, których wartości nie przekraczają <i>N</i>.

Spróbuj swoich sił

#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;
}