Fibonacci Number

Q: מהי סיבוכיות הזמן של פונקציית פיבונאצ'י הרקורסיבית?

הרקורסיה הנאיבית מבצעת 2 × F(n+1) - 1 קריאות, מספר שגדל כמו 1.618^n ובדרך כלל נכתב O(2^n) . עבור n = 45 מדובר בכ־ 3.7 × 10^9 קריאות. שמירת כל תוצאה פעם אחת, בטבלה או בשני משתנים, מצמצמת את מספר הקריאות ל־ O(n) .

Q: איך פותרים את בעיית פיבונאצ'י באמצעות תכנות דינמי?

התחילו מנוסחת הנסיגה F(n) = F(n-1) + F(n-2) וחשבו את הערכים בסדר עולה של n , תוך שמירת כל אחד מהם. אפשר למלא טבלה מלמטה למעלה, או להשאיר את הפונקציה הרקורסיבית ולשמור במטמון את התוצאות שלה — פעולה שנקראת ממוּאיזציה. כך או כך, כל ערך מחושב פעם אחת, ולכן העבודה הכוללת היא O(n) .

Q: האם אפשר לחשב את פיבונאצ׳י בזיכרון O(1)?

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

Q: האם יש דרך מהירה יותר מ־O(n)?

כן. המטריצה [[1, 1], [1, 0]] בחזקת n מכילה את F(n) בפינה הימנית העליונה שלה, והעלאה בריבוע חוזרת מחשבת את החזקה הזו באמצעות O(log n) כפל מטריצות. קיימת גם נוסחה סגורה עם חזקות של יחס הזהב, אבל היא פועלת בחישובי נקודה צפה ומאבדת דיוק ככל ש־ n גדל, ולכן מעדיפים את השיטות השלמות.

מתחיליםתכנון דינמי רקורסיה

+10

מספרי פיבונאצ'י מתחילים ב־F(0) = 0 וב־F(1) = 1, וכל מספר מאוחר יותר הוא סכום שני המספרים שלפניו: F(n) = F(n-1) + F(n-2). הסדרה מתחילה ב־0, 1, 1, 2, 3, 5, 8, 13. הפונקציה שלך מקבלת את n ומחזירה את F(n).

פונקציה

fib(n: integer) → integer

ninteger: המיקום בסדרת פיבונאצ'י, בספירה החל מ־0
מחזירהinteger: מספר פיבונאצ'י F(n)

אילוצים

0 ≤ n ≤ 45
התשובה נכנסת למספר שלם signed 32-bit: F(45) = 1134903170.

דוגמאות

קלט: n = 4
פלט: 3
הסבר: ספור כלפי מעלה מההתחלה: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, ו-F(4) = 2 + 1 = 3.

קלט: n = 10
פלט: 55
הסבר: הרצף מאינדקס 0 הוא 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. המספר באינדקס 10 הוא 34 + 21 = 55.

+13 בדיקות נסתרות בשליחה

שאלת המשך

האם אפשר לחשב את F(n) בזמן O(log n)?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

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

רקורסיה ישירות מההגדרה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

תרגמו את ההגדרה מילה במילה. fib(0) הוא 0, fib(1) הוא 1, וכל ערך גדול יותר מחזיר את fib(n-1) + fib(n-2). כל שרשרת של קריאות מסתיימת באחד משני מקרי הבסיס, ולכן התשובה נכונה.

עכשיו ספרו את הקריאות. fib(5) קוראת ל־fib(4) ול־fib(3), אבל fib(4) קוראת שוב ל־fib(3). בסופו של דבר fib(3) רצה פעמיים, fib(2) שלוש פעמים ו־fib(1) חמש פעמים, ו־fib(5) מבצעת 15 קריאות בסך הכול. אותם ערכים מחושבים מחדש שוב ושוב.

מספר הקריאות עוקב אחר מספרי פיבונאצ'י עצמם: חישוב F(n) מבצע 2 × F(n+1) - 1 קריאות. עבור n = 45 מדובר בכ־3.7 × 10^9 קריאות, הרבה יותר מדי למגבלת זמן. החסם נכתב בדרך כלל O(2^n); קצב הגידול המדויק הוא בערך 1.618^n. עומק הרקורסיה הוא רק n רמות, ולכן המחסנית זקוקה ל־O(n) מקום.

אלגוריתם

אם n הוא 0 או 1, החזר את n.
אחרת, קרא לפונקציה עם n-1 ועם n-2.
החזר את סכום שתי התוצאות.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

מלא טבלה מלמטה למעלה

האינטואיציה

החישוב הרקורסיבי איטי רק כי הוא שוכח. אם תכתוב כל מספר פיבונאצ'י בפעם הראשונה שאתה מחשב אותו, כל אחד מהם ידרוש חיבור יחיד. צור טבלה f עם משבצות לאינדקסים מ־0 עד n, קבע f[0] = 0 ו־f[1] = 1, ומלא את השאר משמאל לימין באמצעות f[i] = f[i-1] + f[i-2].

הסדר משמאל לימין הוא מה שגורם לזה לעבוד: כשמגיעים אל f[i], שני המספרים הדרושים לו כבר נמצאים בטבלה. עבור n = 10, הטבלה מתמלאת כך: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, והתשובה נמצאת במשבצת האחרונה.

זוהי תכנות דינמי בצורתו הבסיסית ביותר: נוסחת נסיגה יחד עם טבלה של תשובות למקרים קטנים יותר. יש n-1 פעולות חיבור, זמן הריצה הוא O(n), והטבלה מכילה n + 1 מספרים, ולכן צריכת המקום היא O(n). כעת, n = 45 דורש 44 פעולות חיבור במקום מיליארדי קריאות.

אלגוריתם

אם n הוא 0 או 1, החזר את n.
צור טבלה של n + 1 מספרים, שבה f[0] = 0 ו-f[1] = 1.
עבור i מ-2 עד n, קבע f[i] = f[i-1] + f[i-2].
החזר את f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

השאר רק את שני המספרים האחרונים

האינטואיציה

בדוק מה לולאת הטבלה קוראת. כדי למלא את f[i] היא זקוקה ל-f[i-1] ול-f[i-2], ולא לשום ערך מוקדם יותר, לכן כל תא קודם הוא מטען מיותר. השתמש בשני משתנים במקום בטבלה: prev מכיל את המספר שנמצא שני צעדים לאחור, ו-curr את המספר שנמצא צעד אחד לאחור.

התחל עם prev = 0 ו-curr = 1, שהם F(0) ו-F(1). בכל צעד חשב next = prev + curr, ואז קדם את הזוג: prev מקבל את הערך הקודם של curr, ו-curr מקבל את next. עבור n = 4 הזוג עובר מ-(0, 1) אל (1, 1), (1, 2) ו-(2, 3), ו-curr = 3 היא התשובה.

העבודה זהה: n-1 פעולות חיבור, זמן O(n), עם שלושה מספרים שלמים בזיכרון, מרחב O(1). סדר העדכונים חשוב: אם תדרוס את prev לפני שתוסיף אותו, הסכום ישתמש בערך שגוי.

אלגוריתם

אם n הוא 0 או 1, החזר את n.
הגדר prev = 0 ואת curr = 1.
חזור על הפעולה n-1 פעמים: חשב את next = prev + curr, ואז הגדר את prev = curr ואת curr = next.
החזר את curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

מלכודות ומקרי קצה

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

הגשת פתרון רקורסיבי נאיבי. הוא עובר בדיקות קטנות ואז דורש מיליארדי קריאות עבור n = 45. שמרו את התוצאות בטבלה או בשני משתנים.
התחלה שגויה. כאן F(0) = 0 ו-F(1) = 1, ולכן F(2) = 1 ו-F(10) = 55. התחלת הסדרה ב-1, 1 מזיזה כל תשובה באינדקס אחד.
בניית הטבלה בלי בדיקה עבור ערכי n קטנים. עבור n = 0, בטבלה שגודלה n + 1 = 1 אין מקום עבור f[1], וכתיבה אליו חורגת מגבולות הטבלה. החזירו מיד את n כאשר n < 2.
עדכון הזוג בסדר שגוי. prev = curr ואחריו curr = prev + curr מחבר את prev החדש ומכפיל את curr. חשבו תחילה את הסכום לתוך next, או השתמשו בהשמה בו-זמנית, אם השפה תומכת בה.
ביצוע צעד אחד יותר מדי. לולאה שמחשבת גם את F(n+1) מגיעה לגבול אל F(46) = 1836311903, שעדיין נכנס ל-32 ביט רק במקרה. F(47) כבר לא.

שאלות נפוצות4

מהי סיבוכיות הזמן של פונקציית פיבונאצ'י הרקורסיבית?

הרקורסיה הנאיבית מבצעת 2 × F(n+1) - 1 קריאות, מספר שגדל כמו 1.618^n ובדרך כלל נכתב O(2^n). עבור n = 45 מדובר בכ־3.7 × 10^9 קריאות. שמירת כל תוצאה פעם אחת, בטבלה או בשני משתנים, מצמצמת את מספר הקריאות ל־O(n).

איך פותרים את בעיית פיבונאצ'י באמצעות תכנות דינמי?

התחילו מנוסחת הנסיגה F(n) = F(n-1) + F(n-2) וחשבו את הערכים בסדר עולה של n, תוך שמירת כל אחד מהם. אפשר למלא טבלה מלמטה למעלה, או להשאיר את הפונקציה הרקורסיבית ולשמור במטמון את התוצאות שלה — פעולה שנקראת ממוּאיזציה. כך או כך, כל ערך מחושב פעם אחת, ולכן העבודה הכוללת היא O(n).

האם אפשר לחשב את פיבונאצ׳י בזיכרון O(1)?

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

האם יש דרך מהירה יותר מ־O(n)?

כן. המטריצה [[1, 1], [1, 0]] בחזקת n מכילה את F(n) בפינה הימנית העליונה שלה, והעלאה בריבוע חוזרת מחשבת את החזקה הזו באמצעות O(log n) כפל מטריצות. קיימת גם נוסחה סגורה עם חזקות של יחס הזהב, אבל היא פועלת בחישובי נקודה צפה ומאבדת דיוק ככל ש־n גדל, ולכן מעדיפים את השיטות השלמות.

Python

def fib(n):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

קלט

n = 4

צפוי

Fibonacci Number

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

רקורסיה ישירות מההגדרה

מלא טבלה מלמטה למעלה

השאר רק את שני המספרים האחרונים

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות