Leap Year
נתונה לך שנה year בלוח השנה הגרגוריאני. החזר true אם זו שנה מעוברת, כלומר שנה שיש בה 29 בפברואר, ו-false אחרת.
שנה היא שנה מעוברת אם היא מתחלקת ב-4, למעט שנים שמתחלקות ב-100, שאינן שנים מעוברות אלא אם הן מתחלקות גם ב-400.
פונקציה
- yearinteger
- השנה לבדיקה
- מחזירהboolean
- True כאשר בשנה יש 29 בפברואר, False אחרת
אילוצים
1 ≤ year ≤ 106
דוגמאות
- קלט
- year = 2024
- פלט
- true
- הסבר
2024מתחלק ב־4ואינו שנה שמסתיימת במאה, לכן זו שנה מעוברת.
- קלט
- year = 1900
- פלט
- false
- הסבר
1900מתחלק ב-4, אבל הוא מתחלק גם ב-100ולא ב-400, לכן חל חריג המאה והוא אינו שנה מעוברת.
- קלט
- year = 2000
- פלט
- true
- הסבר
2000מתחלק ב־100, מה שהיה פוסל אותו, אבל הוא גם מתחלק ב־400, מה שמחזיר אותו לרשימה. זו שנה מעוברת.
+16 בדיקות נסתרות בשליחה
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
שארית של
0לאחר חלוקה ב־4היא הכלל הראשון. אילו שנים מפרות אותו?שנים שמתחלקות במאה מפרות את הכלל, וכפולות של
400מפרות בתורן את כלל המאה. כל כפולה של400היא גם כפולה של100ושל4, ולכן סדר הבדיקות שלך קובע את התשובה.בדקו תחילה אם המספר מתחלק ב־
400, אחר כך ב־100, ואז ב־4, ותנו לכלל הראשון שמתקיים לקבוע. או שלבו אותם: מתחלק ב־4 ולא ב־100, או מתחלק ב־400.
פתרון
כל כלל דורש רק שארית אחת, ולכן העבודה מסתכמת בשלוש בדיקות התחלקות. המלכודת היא הסדר: הכללים סותרים זה את זה בשנים כמו 2000, שהן גם שנת מאה וגם כפולה של 400. בדוק קודם את הכלל הספציפי ביותר, או כתוב את הכלל כביטוי אחד שסוגריו משאירים את החריגים במקומם.
בדקו את הכללים מהספציפי ביותר לפחות ספציפי
האינטואיציה
שלושת הכללים יוצרים שרשרת של חריגים. שנה שמתחלקת ב־4 היא שנה מעוברת, שנה שמתחלקת ב־100 מבטלת זאת, ושנה שמתחלקת ב־400 מבטלת את הביטול. שנה שמתאימה לכלל מאוחר יותר מתאימה תמיד גם לכללים המוקדמים יותר: כל כפולה של 400 היא כפולה של 100, וכל כפולה של 100 היא כפולה של 4.
לכן הכלל הספציפי ביותר שמתאים הוא שקובע את התשובה. בדקו תחילה את 400, אחר כך את 100, ואז את 4, והחזירו תשובה ברגע שאחד מהם מתאים. עבור 2000 הבדיקה הראשונה כבר אומרת כן. עבור 1900 הבדיקה הראשונה נכשלת, והשנייה אומרת לא. עבור 2024 שתי הבדיקות הראשונות נכשלות, והשלישית אומרת כן.
אם אף אחד משלושת הכללים אינו מתאים, השנה אינה מתחלקת ב־4 כלל, ולכן היא שנה רגילה.
אלגוריתם
- אם
year % 400 == 0, החזרtrue. - אם
year % 100 == 0, החזרfalse. - אם
year % 4 == 0, החזרtrue. - אחרת החזר
false.
def isLeapYear(year):
if year % 400 == 0:
return True
if year % 100 == 0:
return False
if year % 4 == 0:
return True
return Falseביטוי בוליאני אחד
האינטואיציה
קראו את הכלל כשתי דרכים להיות שנה מעוברת. או שהשנה מתחלקת ב־4 ואינה שנת מאה, או שהיא מתחלקת ב־400. המשפט הזה מתורגם מילה במילה ל־(year % 4 == 0 and year % 100 != 0) or year % 400 == 0.
בדקו זאת בשלוש הדוגמאות. 2024 עומדת בתנאי הראשון. 1900 נכשלת בתנאי הראשון משום שהיא שנת מאה, ונכשלת בשני משום ש־1900 % 400 הוא 300. 2000 נכשלת בתנאי הראשון מאותה סיבה כמו 1900, ועומדת בתנאי השני.
אפשר גם לקבץ את התנאי בדרך אחרת: מתחלקת ב־4, וגם או שאינה שנת מאה או שהיא כפולה של 400. שתי הצורות נותנות אותה תוצאה לכל שנה. הביטוי מבצע לכל היותר את אותן שלוש בדיקות כמו שרשרת ה־if.
אלגוריתם
- חשבו את
year % 4 == 0 and year % 100 != 0: מתחלק ב־4 ואינו שנה של מאה. - חשבו את
year % 400 == 0. - החזירו
trueאם אחד מהתנאים מתקיים.
def isLeapYear(year):
# Every 4th year, except centuries, except every 400th year.
return (year % 4 == 0 and year % 100 != 0) or year % 400 == 0
מלכודות ומקרי קצה
כל טעות כאן נובעת מהתייחסות לכלל כאל בדיקה אחת במקום כאל שרשרת של חריגים.
- בדיקה של
year % 4 == 0בלבד. היא נותנת את התשובה הנכונה לכל שנה מ־1901עד2099, ולכן הבאג מסתתר, ואת התשובה השגויה עבור1900ו־2100. - בדיקת
100לפני400בשרשרת if. בדיקת המאה מחזירהfalseעבור2000עוד לפני שבדיקת400בכלל רצה. - השמטת החלק של החלוקה ב־4 ללא שארית.
year % 100 != 0 or year % 400 == 0מחשיב את2023לשנה מעוברת, כי2023אינה שנה שלמה במאה. - שימוש ב־
year / 4במקום בשארית. החלוקה אומרת לך כמה פעמים4נכנס; השארית אומרת לך אם הוא נכנס בדיוק.
שאלות נפוצות4
מהו הכלל לקביעת שנה מעוברת?
שנה בלוח הגרגוריאני היא שנה מעוברת כאשר היא מתחלקת ב־4, אלא אם היא מתחלקת ב־100. שנה שמתחלקת ב־400 היא בכל זאת שנה מעוברת. לכן 2024 ו־2000 הן שנים מעוברות, ואילו 1900 ו־2100 אינן.
למה 1900 אינה שנה מעוברת, אבל 2000 כן?
שתיהן שנים של מאה, מתחלקות ב־100, מה שבדרך כלל פוסל שנה. 2000 מתחלקת גם ב־400, והכלל הזה גובר על כלל המאה. בחלוקה של 1900 ב־400 נשארת שארית 300, ולכן היא נשארת שנה רגילה.
למה קיימים כללי המאה?
שנה שמשית נמשכת כ־365.2422 ימים. הוספת יום כל 4 שנים נותנת ממוצע של 365.25, כלומר כ־3 ימים יותר מדי בכל 400 שנים. דילוג על היום הנוסף ב־3 מכל 4 שנים של מאה מסיר את אותם 3 ימים. הממוצע הופך ל־365.2425 ימים, די קרוב כדי לשמור על התאמה בין לוח השנה לעונות במשך אלפי שנים.
מהי סיבוכיות הזמן של בדיקה אם שנה היא שנה מעוברת?
סיבוכיות הזמן והמרחב היא O(1). הבדיקה כוללת לכל היותר שלוש פעולות שארית וכמה השוואות, בלי קשר לגודל השנה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def isLeapYear(year):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
year = 2024
צפוי
true