Factorial
העצרת של מספר שלם n, שנכתבת n!, היא המכפלה של כל המספרים השלמים מ־1 ועד n. לדוגמה, 4! = 1 × 2 × 3 × 4 = 24. לפי ההגדרה 0! = 1. הפונקציה שלך מקבלת את n ומחזירה את n!.
פונקציה
- ninteger
- המספר השלם שעצרת שלו מחשבים
- מחזירהinteger
- המכפלה של כל המספרים השלמים מ-1 עד n, שהיא 1 כאשר n הוא 0
אילוצים
0 ≤ n ≤ 12- התשובה נכנסת למספר שלם חתום בן 32 סיביות: הגדול ביותר הוא
12! = 479001600.
דוגמאות
- קלט
- n = 5
- פלט
- 120
- הסבר
- כפלו את
1 × 2 × 3 × 4 × 5. המכפלה המצטברת היא 1, 2, 6, 24 ומסתיימת ב-120.
- קלט
- n = 0
- פלט
- 1
- הסבר
- אין מה להכפיל, ומכפלה שאין בה גורמים היא
1. לכן0! = 1.
+11 בדיקות נסתרות בשליחה
שאלת המשך
100! מכיל 158 ספרות. האם תוכל לספור בכמה אפסים הוא מסתיים בלי לחשב אותו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כתבו את
4!ואת5!כמכפלות. מה הקשר בין5!ל־4!?5! = 5 × 4!. באופן כללי,n! = n × (n-1)!, והשרשרת נעצרת ב־0! = 1.שמור מכפלה מצטברת שמתחילה ב־
1וכפול אותה בכל מספר מ־2עדn. התחלה ב־1 נותנת גם את התשובה הנכונה עבור0ו־1.
פתרון
לעצרת יש שני תיאורים שקולים, וכל אחד מהם הופך לקוד. כמכפלה, n! = 1 × 2 × ... × n, שהיא לולאה. כהגדרה רקורסיבית, 0! = 1 וגם n! = n × (n-1)!, שהיא פונקציה שקוראת לעצמה. בשתי הדרכים מבצעים בערך n כפלות. כדאי לסיים עם הלולאה, כי היא אינה זקוקה למחסנית קריאות.
רקורסיה מתוך ההגדרה
האינטואיציה
העצרת מוגדרת באמצעות עצרת קטנה יותר: n! = n × (n-1)!. אם כבר ידוע לך ש־4! = 24, אז 5! = 5 × 24 = 120. פונקציה רקורסיבית כותבת את המשפט הזה כקוד. כדי לחשב את factorial(n), היא מבקשת את factorial(n-1) ומכפילה את התוצאה ב־n.
לקריאות צריך להיות מקום לעצור בו, מקרה הבסיס: factorial(0) מחזירה 1 בלי לקרוא לשום דבר. בכל קריאה n קטן באחד, כך שמ־5 הקריאות יורדות בסדר הבא: 5, 4, 3, 2, 1, 0. לאחר מכן התוצאות חוזרות במעלה השרשרת: 1, 1, 2, 6, 24, 120.
יש n + 1 קריאות ו־n פעולות כפל, ולכן זמן הריצה הוא O(n). כל קריאה ממתינה במחסנית עד שהקריאה שמתחתיה מסתיימת, ולכן המחסנית מחזיקה n + 1 מסגרות, כלומר נדרש מקום של O(n). כאשר n ≤ 12, זה זניח, אבל אותה תבנית עם קלט גדול גורמת לגלישת מחסנית.
אלגוריתם
- אם
nהוא0, החזירו1. זהו מקרה הבסיס. - אחרת, קראו לפונקציה עם
n-1. - הכפילו את התוצאה ב-
nוהחזירו אותה.
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)כפל בלולאה
האינטואיציה
פותחים את הרקורסיה ומקבלים מכפלה מצטברת. מתחילים ב-result = 1 ומכפילים ב-2, אחר כך ב-3, וכך הלאה עד n. עבור n = 5 התוצאה מתקדמת כך: 1, 2, 6, 24, 120.
התחלה ב-1 מכסה גם את הקלטים הקטנים ביותר. עבור n = 0 ועבור n = 1, הלולאה מ-2 עד n רצה אפס פעמים, והפונקציה מחזירה את ערך ההתחלה 1, שהיא התשובה הנכונה בשני המקרים.
הלולאה מבצעת n-1 פעולות כפל, בזמן O(n), ושומרת מספר אחד, במרחב O(1). אין מחסנית קריאות שעלולה לגלוש, ולכן מראיינים מצפים לגרסה הזו לאחר שהצגת את הגרסה הרקורסיבית.
אלגוריתם
- הגדר את
result = 1. - עבור עם
kמ־2עדn, כולל שניהם. - כפול את
resultב־kבכל שלב. - החזר את
result.
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
מלכודות ומקרי קצה
קוד לחישוב עצרת קצר, ולכן הבאגים נמצאים בקצוות.
- מתחילים את המכפלה ב-
0. כל כפל משאיר אותה על 0. הערך ההתחלתי של מכפלה הוא1. - עוצרים את הרקורסיה רק ב-
n == 1. אם קוראים לפונקציה עם0, היא לעולם לא מגיעה למקרה הבסיס: היא ממשיכה ל--1, ל--2 וכן הלאה, עד לגלישת מחסנית. יש לקבוע אתn == 0כמקרה הבסיס. - משתמשים בלולאה עם
k < nבמקום עםk ≤ n. כך הגורם האחרון נשמט והתוצאה היא(n-1)!, ולכן עבור5מתקבלת התוצאה 24 במקום 120. - מתעלמים מגלישה.
13! = 6227020800לא נכנס למספר שלם מסומן בן 32 סיביות. ב-Java וב-C# המכפלה גולשת בשקט למספר שגוי, ב-C גלישה של מספר שלם מסומן היא התנהגות לא מוגדרת, ובבנייה לניפוי שגיאות של Rust מתרחשת בהלה. מספר שלם בן 64 סיביות יכול להכיל עד20!; מעבר לכך דרושים מספרים שלמים גדולים. - ב-Swift, כתיבה של
for k in 2...n. טווח סגור שהסוף שלו קטן מההתחלה גורם לקריסה בזמן ריצה כאשרnהוא 0 או 1.
שאלות נפוצות4
מהי סיבוכיות הזמן של חישוב עצרת?
גם הלולאה וגם הרקורסיה מבצעות כפל אחד עבור כל מספר עד n, ולכן זמן הריצה הוא O(n). הלולאה דורשת מרחב נוסף של O(1). הרקורסיה שומרת מסגרת מחסנית אחת לכל קריאה עד להחזרת מקרה הבסיס, ולכן היא משתמשת במרחב של O(n).
למה 0! שווה ל-1?
0! הוא מכפלה של אפס מספרים, ומכפלה ללא גורמים היא 1, בדומה לכך שסכום ללא איברים הוא 0. כך נשמרת גם נכונותו של הכלל n! = n × (n-1)! כאשר n = 1: 1! = 1 × 0! = 1. גם הספירה תואמת: יש בדיוק דרך אחת לסדר אפס פריטים.
מה עדיף לחישוב עצרת, רקורסיה או לולאה?
הם מבצעים את אותן פעולות כפל ומחזירים את אותה תשובה. הגרסה הרקורסיבית נקראת כמו ההגדרה המתמטית, ולכן היא תרגיל ראשון קלאסי ברקורסיה. הלולאה משתמשת בזיכרון קבוע ואינה יכולה לחרוג מגודל מחסנית הקריאות, ולכן היא הבחירה הטובה יותר בקוד אמיתי.
מהי העצרת הגדולה ביותר שנכנסת למספר שלם?
12! = 479001600 היא העצרת הגדולה ביותר שנכנסת למספר שלם מסומן של 32 סיביות. 20! = 2432902008176640000 היא הגדולה ביותר עבור מספר שלם מסומן של 64 סיביות. מעבר לכך, צריך מספרים בגודל בלתי מוגבל, כמו int של Python, BigInteger של Java או BigInt של JavaScript.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def factorial(n):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
n = 5
צפוי
120