המשמעות של מספרי פיבונאצ'י
מספרי פיבונאצ'י הם רצף מסוים של מספרים שלמים חיוביים, החל מ-0. מספרים שלמים הם מספרים שלמים חיוביים. אז, מספר פיבונאצ'י הוא רצף מסוים של מספרים שלמים או מספרים טבעיים, המתחיל מ-0. ברצף זה, שני המספרים הראשונים הם 0 ו-1, בסדר הזה. שאר המספרים מפותחים משם על ידי הוספת שני המספרים הקודמים. שנים עשר מספרי פיבונאצ'י הראשונים מתקבלים באופן הבא:
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
במילים אחרות, שנים עשר מספרי פיבונאצ'י הראשונים הם:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
כמובן, המספר השלושה עשר יהיה: 144 = 55 + 89. ניתן לדמיין מספרי פיבונאצ'י במערך, כך:
| 0 | 1 | 1 | שתיים | 3 | 5 | 8 | 13 | עשרים ואחת | 3. 4 | 55 | 89 |
למערך יש אינדקסים. בטבלה הבאה, השורה השנייה מציגה את האינדקסים המתאימים מבוססי אפס עבור מספרי פיבונאצ'י במערך:
| 0 | 1 | 1 | שתיים | 3 | 5 | 8 | 13 | עשרים ואחת | 3. 4 | 55 | 89 |
| 0 | 1 | שתיים | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | אחד עשר |
עם אינדקסים מבוססי אפס, אם יש שנים עשר אלמנטים, המדד האחרון הוא 11.
ניתן להפיק מספרי פיבונאצ'י בזמן O(n) או בזמן O(1). בביטויי מורכבות זמן אלה, n פירושו n פעולות עיקריות, ו-1 פירושו פעולה עיקרית אחת. עם O(n), נוצרים n מספרי פיבונאצ'י, החל מ-0. עם O(1), מספר פיבונאצ'י אחד מופק מהאינדקס המקביל. לכן O(1) לוקח רק פעולה עיקרית אחת במקום n פעולות עיקריות.
מטרת מאמר זה היא להסביר כיצד לייצר מספרי פיבונאצ'י, כך או כך, באמצעות JavaScript, שהוא למעשה ECMAScript היום.
סביבת קידוד
סביבת node.js לא תעשה שימוש כפי שהקורא יכול היה לצפות. במקום זאת, הדפדפן ישמש לפירוש הקוד והצגת התוצאות. יש לכתוב את הסקריפט (קוד) בקובץ עורך טקסט, אותו יש לשמור עם הסיומת '.html'. הסקריפט צריך לכלול קוד מינימלי:
DOCTYPE HTML >< html >
< רֹאשׁ >
< כותרת > מספרי פיבונאצ'י עם JavaScript כותרת >
רֹאשׁ >
< גוּף >
< סוג סקריפט = 'טקסט/ecmascript' >
תַסרִיט >
גוּף >
html >
זהו קוד מינימום משוער שדף אינטרנט צריך. כל הקידוד של מאמר זה עובר בין התגים, .
כדי להפעיל את הקוד שנכתב (נוסף), פשוט לחץ פעמיים על הסמל של שם הקובץ, והדפדפן של המחשב יפתח אותו.
הגדרה של מספר פיבונאצ'י
יש הגדרה מתמטית למספר פיבונאצ'י. הוא מוגדר כך:
כאשר Fn הוא מספר פיבונאצ'י המתאים לאינדקס מבוסס אפס, n.
שני המספרים הראשונים: 0 ו-1, מוצהרים מראש, בסדר הזה. השורה האחרונה של פונקציה זו מראה כיצד שאר המספרים מקורם משני המספרים הראשונים בסדר שלהם.
הגדרה זו היא גם אחת הנוסחאות למספר פיבונאצ'י.
הפקת מספרי פיבונאצי בזמן 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 יוצגו כמספרי פיבונאצ'י, בסדר הזה - וכן הלאה.
פונקציית ECMAscript ליצירת n המספרים השלמים הראשונים של פיבונאצ'י (מספרים) היא:
< סוג סקריפט = 'טקסט/ecmascript' >פוּנקצִיָה פיבונאצ'י ( א ) {
נ = א. אורך ;
אם ( נ > 0 )
א [ 0 ] = 0 ;
אם ( נ > 1 )
א [ 1 ] = 1 ;
ל ( אני = שתיים ; אני < נ ; אני ++ ) { //n=0 ו-n=2 נשקלו
currNo = א [ אני - 1 ] + א [ אני - שתיים ] ;
א [ אני ] = currNo ;
}
}
תג הסקריפט הסוגר לא הוצג. הפונקציה מקבלת מערך. שני מספרי פיבונאצ'י הראשונים מוקצים במיקום שלהם. לולאת for חוזרת מהאינדקס מבוסס אפס, 2 עד מתחת ל-n. ההצהרה החשובה ביותר ב-for-loop היא:
currNo = A[i – 1] + A[i – 2];
זה מוסיף את שני המספרים הקודמים המיידיים במערך כדי לקבל את המספר הנוכחי. עד שהפונקציה fibonacci() תסיים להפעיל, כל הרכיבים של המערך הם n מספרי פיבונאצ'י הראשונים. קוד מתאים לקרוא לפונקציה fibonacci() ולהציג את מספרי פיבונאצ'י הוא:
נ = 12 ;arr = חָדָשׁ מַעֲרָך ( נ ) ;
פיבונאצ'י ( arr ) ;
ל ( אני = 0 ; אני < נ ; אני ++ )
מסמך. לִכתוֹב ( arr [ אני ] + '' ) ;
מסמך. לִכתוֹב ( '
' ) ;
תַסרִיט >
קוד זה מציג את תג הסקריפט הסוגר. הקוד מוקלד מתחת לקוד שלמעלה. הפלט המוצג בדף האינטרנט הוא:
0 1 1 2 3 5 8 13 21 34 55 89
כצפוי.
הפקת מספר פיבונאצי אחד בזמן O(1).
O(1) הוא זמן קבוע. זה מתייחס לפעולה עיקרית אחת. נוסחה מתמטית נוספת להפקת מספר פיבונאצ'י היא:
שימו לב שבצד ימין של המשוואה, לא השורש הריבועי של 5 מועלה בחזקת n; זה הביטוי בסוגריים שמועלה לעוצמה n. יש שני ביטויים כאלה.
אם n הוא 0, Fibn יהיה 0. אם n הוא 1, Fibn יהיה 1. אם n הוא 2, Fibn יהיה 1. אם n הוא 3, Fibn יהיה 2. אם n הוא 4, Fibn יהיה 3 – וכן הלאה. הקורא יכול לאמת נוסחה זו באופן מתמטי על ידי החלפת n בערכים שונים והערכה. n הוא אינדקס מבוסס אפס בנוסחה זו. התוצאה היא מספר פיבונאצ'י המתאים.
קוד ה-ECMAScript (JavaScript) עבור נוסחה זו הוא:
< סוג סקריפט = 'טקסט/ecmascript' >פוּנקצִיָה fibNo ( נ ) {
FibN = ( מתמטיקה . פאו ( ( 1 + מתמטיקה . sqrt ( 5 ) ) / שתיים , נ ) - מתמטיקה . פאו ( ( 1 - מתמטיקה . sqrt ( 5 ) ) / שתיים , נ ) ) / מתמטיקה . sqrt ( 5 ) ;
לַחֲזוֹר FibN ;
}
תג הסקריפט הסוגר לא הוצג. שימו לב כיצד נעשה שימוש בפונקציות המוגדרות מראש של כוח (pow) ושורש ריבועי (sqrt). ב-ECMAScript (JavaScript), אין צורך לייבא את מודול המתמטיקה. הפונקציה fibNo() מיישמת את הנוסחה ישירות. קריאה ותצוגה מתאימים עבור הפונקציה fibNo() בדף האינטרנט הם:
נ = אחד עשר ;ימין = fibNo ( נ ) ;
מסמך. לִכתוֹב ( ימין ) ;
תַסרִיט >
הקוד מציג את תג הסקריפט הסוגר. הפלט הוא:
89.000000000000003
אפשר להסיר מהתשובה את הספרות העשרוניות המיותרות. עם זאת, זה דיון לתקופה אחרת.
אם נדרש יותר ממספר פיבונאצ'י אחד, הקוד צריך לקרוא לנוסחה פעם אחת עבור כל אינדקס n המקביל מבוסס אפס.
סיכום
מספרי פיבונאצ'י הם רצף מסוים של מספרים שלמים חיוביים, החל מ-0. מספרים שלמים הם מספרים שלמים חיוביים. אז, מספר פיבונאצ'י הוא רצף מסוים של מספרים שלמים או מספרים טבעיים, המתחיל מ-0. ברצף זה, שני המספרים הראשונים הם 0 ו-1, בסדר הזה. שני המספרים הראשונים האלה פשוט מוגדרים ככאלה. שאר המספרים מפותחים משם על ידי הוספת שני המספרים הקודמים המיידיים.
לאחר הפקת שני מספרי פיבונאצ'י הראשונים, כדי להפיק את שאר מספרי פיבונאצ'י, כדי להסתיים בסה'כ של n מספרים, יש להשתמש בלולאת for עם ההצהרה:
currNo = A[i – 1] + A[i – 2];
זה מוסיף את שני מספרי פיבונאצ'י המיידיים למספר פיבונאצ'י הנוכחי.
כאשר ניתן אינדקס מבוסס אפס, כדי לקבל את מספר פיבונאצ'י המתאים, השתמש בנוסחה:
