מספרי פיבונאצ'י בשפת פייתון

מספרי פיבונאצ'י הם רצף מסוים שבו הערך הראשון מוצהר מראש כ-0 והערך השני מוצהר מראש כ-1. שאר המספרים מופקים משני אלה על ידי הוספת שני המספרים הקודמים. כל מספרי פיבונאצ'י הם מספרים שלמים חיוביים, המתחילים מ-0. שנים עשר מספרי פיבונאצ'י הראשונים וכיצד הם מתקבלים הם כדלקמן:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

ללא ביטויי הסכום, ניתן לשים את מספרי פיבונאצ'י אלה בטבלה באופן הבא:

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

ניתן להפיק מספרי פיבונאצ'י בזמן O(n) ובזמן O(1). בביטויי מורכבות זמן אלה, n פירושו n פעולות עיקריות, ו-1 פירושו פעולה עיקרית אחת. עם O(n), נוצרים n מספרי פיבונאצ'י, החל מ-0. עם O(1), מספר פיבונאצ'י אחד מופק מאינדקס מתאים. לכן נדרשת רק פעולה עיקרית אחת במקום n פעולות עיקריות.

מטרת מאמר זה היא להסביר כיצד לייצר מספרי פיבונאצ'י, בכל מקרה, באמצעות פייתון.

נוסחה למספר פיבונאצ'י

ההגדרה הרשמית של מספר פיבונאצ'י היא:

שבו F _נ הוא מספר פיבונאצ'י במדד n

הפקת מספרי פיבונאצי בזמן O(n).

אם n הוא 1, אז רק 0 יודפס כמספר פיבונאצ'י. אם n הוא 2, אז 0 ו-1 יודפסו כמספרי פיבונאצ'י, בסדר הזה. אם n הוא 3, אז 0, 1 ו-1 יודפסו כמספרי פיבונאצ'י בסדר הזה. אם n הוא 4, אז 0, 1, 1 ו-2 יודפסו כמספרי פיבונאצ'י בסדר הזה. אם n הוא 5, אז 0, 1, 1, 2 ו-3 יודפסו כמספרי פיבונאצ'י, בסדר הזה. אם n הוא 6, אז 0, 1, 1, 2, 3 ו-5 יודפסו כמספרי פיבונאצ'י, בסדר הזה - וכן הלאה.

פונקציית Python להפקת n מספרי פיבונאצ'י הראשונים היא:

זה מתחיל ביצירת מערך של n אלמנטים, כולם מאותחלים לאפסים. מערך זה יכיל את מספרי פיבונאצ'י. מספר פיבונאצ'י הראשון, 0, כבר שם. מספר פיבונאצ'י השני, 1, מוקצה על ידי ההצהרה הבאה (בפונקציה). ואז יש את for-loop, שמתחיל מאינדקס 2 עד קצת לפני n. יש בו את ההצהרה:

זה מוסיף את שני המספרים הקודמים המיידיים.

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

N = 12
A = fibonacci(N)
עבור i בטווח(N):
הדפס (A[i], end=' ')
הדפס()

הפלט הוא:

הפקת מספר פיבונאצי אחד בזמן קבוע

יש נוסחה מתמטית שמקשרת אינדקס מבוסס אפס למספר פיבונאצ'י המקביל לו. הנוסחה היא:

שימו לב שבצד ימין של המשוואה, לא השורש הריבועי של 5 מועלה בחזקת n; זה הביטוי בסוגריים שמועלה לעוצמה n. יש שני ביטויים כאלה.

אם n הוא 0, Fibn יהיה 0. אם n הוא 1, Fib _נ יהיה 1. אם n הוא 2, Fib _נ יהיה 1. אם n הוא 3, Fib _נ יהיה 2. אם n הוא 4, Fib _נ יהיה 3 - וכן הלאה. הקורא יכול לאמת נוסחה זו באופן מתמטי על ידי החלפת n בערכים שונים והערכה. n הוא אינדקס מבוסס אפס בנוסחה זו.

קוד Python עבור נוסחה זו הוא:

ייבוא ​​מתמטיקה

מודול המתמטיקה יובא. יש לו את פונקציית השורש הריבועי. המפעיל, ** משמש לכוח. הפונקציה fibNo() מיישמת את הנוסחה ישירות. קריאה והדפסה מתאימים עבור הפונקציה fibNo() היא:

N = 11
מימין = fibNo(N)
print (ret)

הפלט הוא:

אפשר להסיר מהתשובה את הספרות העשרוניות המיותרות. עם זאת, זה דיון לתקופה אחרת.

אם נדרשים מספרי פיבונאצ'י שונים עבור n אינדקסים שונים, יש לקרוא לפונקציה fibNo() פעם אחת עבור כל אחד מאינדקס n כדי להחזיר את מספרי פיבונאצ'י התואמים השונים. התוכנית הבאה עושה זאת עבור האינדקסים המבוססים על אפס, 7 עד 9 (כולל):

ייבוא ​​מתמטיקה

הפלט הוא:

שימו לב לאופן שבו ה-for-loop קודד ב-Python. המדד הראשון הוא 7. המדד הבא הוא 8, והאינדקס האחרון הוא 9. 10 בארגומנט הטווח הוא 9 + 1. הערך במיקום 10 צריך להיות המדד האחרון מבוסס אפס פלוס 1. המדד הראשון ארגומנט, 7, הוא המדד המבוסס על אפס התחלה.

סיכום

מספרי פיבונאצ'י הם רצף מסוים של מספרים שלמים (מספרים שלמים חיוביים). זה מתחיל ב-0, ואחריו 1 ללא תנאי. שאר המספרים מפותחים משם על ידי הוספת שני המספרים הקודמים המיידיים.

כדי לקבל את n מספרי פיבונאצ'י הראשונים, קבל את 0 ו-1 כשניים הראשונים, ולאחר מכן עבור השאר, השתמש ב-for-loop עם משפט כמו:

מה שמוסיף את שני המספרים הקודמים המיידיים.

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