FizzBuzz

Q: מהי סיבוכיות הזמן של FizzBuzz?

מענה עבור מספר אחד הוא O(1) : מספר קבוע של בדיקות שארית והמרה של מספר שאורכו לכל היותר 10 ספרות. הדפסת הרצף מ־1 עד n היא O(n) .

מתחיליםמתמטיקה וסימולציה

+10

במשחק הספירה FizzBuzz, השחקנים סופרים החל מ־1 ומחליפים מספרים מסוימים במילים. בהינתן מספר תור n, החזר את מה ששחקן אומר בתור הזה: "FizzBuzz" אם n מתחלק גם ב־3 וגם ב־5, "Fizz" אם הוא מתחלק רק ב־3, "Buzz" אם הוא מתחלק רק ב־5, ואחרת את n עצמו כמחרוזת, למשל "7".

פונקציה

fizzBuzz(n: integer) → string

ninteger: מספר התור, מספר שלם חיובי
מחזירהstring: המילה או המספר שנאמרים בתור n, כמחרוזת

אילוצים

1 ≤ n ≤ 10⁹
התשובה היא תמיד מחרוזת, גם כשהיא המספר עצמו.

דוגמאות

קלט: n = 15
פלט: "FizzBuzz"
הסבר: 15 חלקי 3 הם 5 ו-15 חלקי 5 הם 3, בשניהם אין שארית, ולכן התור של 15 הוא "FizzBuzz".

קלט: n = 7
פלט: "7"
הסבר: 7 משאיר שארית 1 בחלוקה ב־3 ושארית 2 בחלוקה ב־5, לכן אף מילה אינה מתאימה ומחזירים את המספר כטקסט, "7".

שאלת המשך

כלל חדש הופך כפולות של 7 ל־"Bazz", והמילים מצטרפות לפי הסדר, כך ש־105 הוא "FizzBuzzBazz". איך מוסיפים אותו בלי להוסיף מקרה לכל שילוב?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל כלל הוא בדיקת שארית אחת. המלכודת היא הסדר: 15 מתחלק ב־3, ולכן פונקציה שבודקת קודם את 3 ומחזירה מיד תענה "Fizz" עבור 15. בדוק קודם את המקרה המשולב, או בנה את התשובה על סמך שתי הבדיקות.

בנו את המילה משתי הבדיקות

האינטואיציה

התחילו במילה ריקה. אם 3 מחלק את n, הוסיפו "Fizz"; אם 5 מחלק את n, הוסיפו "Buzz". שתי הבדיקות תמיד מתבצעות, ולכן כפולה של 15 אוספת את שני החלקים לפי הסדר והופכת ל־"FizzBuzz" בלי מקרה מיוחד. אם המילה עדיין ריקה, אף אחד מהכללים לא חל, ומחזירים את המספר כמחרוזת.

אלגוריתם

הגדר את word כמחרוזת ריקה.
אם n % 3 == 0, הוסף בסוף "Fizz".
אם n % 5 == 0, הוסף בסוף "Buzz".
אם word ריק, החזר את n כמחרוזת.
אחרת, החזר את word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

בדוק 15, אחר כך 3, ואז 5

האינטואיציה

מספר שמתחלק גם ב־3 וגם ב־5 מתחלק בדיוק ב־15, כי ל־3 ול־5 אין גורם משותף. לכן הכלל המשולב הוא בדיקה אחת, n % 15 == 0, והיא מתבצעת ראשונה. אם היא נכשלת, התאמה ל־3 פירושה 3 בלבד, והתאמה ל־5 פירושה 5 בלבד. כל בדיקה מחזירה תוצאה מיד, ואם אף אחת מהן לא מתאימה, מחזירים את המספר כמחרוזת.

אלגוריתם

אם n % 15 == 0, החזר "FizzBuzz".
אם n % 3 == 0, החזר "Fizz".
אם n % 5 == 0, החזר "Buzz".
אחרת החזר את n כמחרוזת, כאשר כל ספרה נכתבת במילים.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

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

בדיקת 3 או 5 לפני 15 והחזרה מיידית: 15, 30 ו־45 מתקבלים כ־"Fizz".
החזרת המספר במקום מחרוזת. בתור 7 מתקבל "7".
המרת מספרים גדולים לכתיב מדעי. ב־R המרה רגילה מדפיסה את 10^9 בתור 1e+09; יש להשתמש ב־format(n, scientific = FALSE).
הדפסת התשובה במקום החזרתה.

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

למה שואלים על FizzBuzz בריאיונות תכנות?

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

האם תוכל לפתור את FizzBuzz בלי אופרטור השארית?

כן. חלקו באמצעות חילוק שלם, הכפילו את המנה בחזרה והשוו אותה ל־n: הם שווים רק כשלא נשארת שארית. כשמדפיסים את כל הרצף, אפשר גם להחזיק שני מונים שמתאפסים ב־3 וב־5.

מהי סיבוכיות הזמן של FizzBuzz?

מענה עבור מספר אחד הוא O(1): מספר קבוע של בדיקות שארית והמרה של מספר שאורכו לכל היותר 10 ספרות. הדפסת הרצף מ־1 עד n היא O(n).

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

בדיקה #1

בדיקה #2

ארגומנט

n = 15

הפלט הצפוי

"FizzBuzz"