מספרי פיבונאצ'י

שיעור 4 מתוך 20 בקורס חידות מתמטיות של Coddy.

כל איבר חדש בסדרת פיבונאצ'י נוצר על ידי חיבור שני האיברים הקודמים.

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

בהתחלה ב-1 וב-2, 10 האיברים הראשונים שמתחת ל-100 יהיו:

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

סדרת פיבונאצ'י מופיעה בספר Liber Abaci (ספר החישוב, 1202) מאת פיבונאצ'י, ושימשה בו לחישוב הגידול באוכלוסיית הארנבים. פיבונאצ'י בחן גידול של אוכלוסיית ארנבים אידיאלית (שאינה מציאותית מבחינה ביולוגית), בהנחה שזוג ארנבים מתרבה שזה עתה נולד מוכנס לשדה; כל זוג ארנבים מתרבה מזדווג בגיל חודש, ובתום החודש השני שלו תמיד מוליד זוג ארנבים נוסף; והארנבים לעולם אינם מתים, אלא ממשיכים להתרבות לנצח. פיבונאצ'י הציג את החידה: כמה זוגות יהיו כעבור שנה?

בתום החודש ה-n, מספר זוגות הארנבים שווה למספר הזוגות הבוגרים (כלומר, מספר הזוגות בחודש n – 2) ועוד מספר הזוגות שהיו בחיים בחודש שעבר (חודש n – 1). המספר בחודש ה-n הוא מספר פיבונאצ'י ה-n. [ויקיפדיה, האנציקלופדיה החופשית]

אתגר

קל

כתבו קוד Python בשם calcFibonacciNums שמקבל מספר טבעי, <i>N</i>, ומחזיר את מספר האיברים בסדרת פיבונאצ'י, שמתחילה ב־1 וב־2, שערכיהם אינם עולים על <i>N</i>.

נסו בעצמכם

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