תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

חידה תכנותית: כמה דרכים שונות לטפס מדרגות

מחבר:
בתאריך:

בגרם מדרגות נתון יש מספר של N מדרגות. מהו מספר הדרכים לטיפוס לראש גרם המדרגות?

 

פתרון

בשביל הפתרון נחשוב על כמה דוגמאות קונקרטיות:

  • קיימת רק דרך 1 לטפס מדרגה 1.

  • כדי לטפס 2 מדרגות אז אפשר לטפס כל מדרגה בנפרד או לטפס את 2 המדרגות בבת אחת, ומכאן 2 דרכים.

  • כדי לטפס 3 מדרגות אפשר לטפס מדרגה-מדרגה, או 2 מדרגות ואז 1, או מדרגה 1 ואז 2. סה"כ 3 דרכים.

  • כדי לטפס 4 מדרגות אפשר:

    1. לטפס מדרגה-מדרגה [1, 1, 1, 1]
    2. 2 מדרגות בבת אחת ואז מדרגה-מדרגה [2, 1, 1]
    3. מדרגה-מדרגה ואז 2 מדרגות [1, 1, 2]
    4. מדרגה 1 - 2 מדרגות - מדרגה 1 [1, 2, 1]
    5. 2 מדרגות - 2 מדרגות [2, 2]

סה"כ 5 דרכים.

נתעכב על הדוגמה של 4 מדרגות כי חישוב מספר הדרכים הוא סכום מספר הדרכים לטפס 2 מדרגות (2 דרכים) בתוספת מספר הדרכים לטפס 3 מדרגות (3 דרכים). `2 + 3 = 5`. יש 5 דרכים לטפס 4 מדרגות.

מזה נסיק כלל שכדי לטפס N מדרגות צריך לחבר את מספר הדרכים לטיפוס `N-1` ו `N-2` מדרגות. אפשר לנסח את הכלל כך:

combinations(N) = combinations(N-1) + combinations(N-2)

הכלל מבוסס על הרעיון שאפשר להגיע לשלב ה-N על ידי ביצוע צעד אחד מהשלב (`N-1`) או שני צעדים מהשלב (`N-2`).

ננסח את הרעיון בקוד:

# Number of ways to climb 1 stair
prev1 = 1
# Number of ways to climb 2 stairs
prev2 = 2
# Number of ways to climb 3 stairs
current = prev1 + prev2

אנחנו יכולים להרחיב את הרעיון לכל מספר N של מדרגות בעזרת רקורסיה או לולאה. את הלולאה נתחיל להריץ מ-3 (כי חישבנו כבר עבור מדרגה אחת ושתי מדרגות):

for range(3, n+1):
    current = prev1 + prev2

צריך לעדכן את `prev1` ו-`prev2`:

for range(3, n+1):
    current = prev1 + prev2
    prev1 = prev2
    prev2 = current

נעשה מזה פונקציה:

def climb_stairs(n):
    # Handle edge cases
    if n < 0:
        raise Exception("Number of stairs cannot be less than 0")
    if n <= 2:
        return n

    # Initialize variables to keep track of the previous two solutions
    prev1 = 1  # Represents 1 stair
    prev2 = 2  # Represents 2 stairs

    # Initialize a variable to store the current solution
    current = 0

    # Start the loop from 3, as we've already handled the cases for 1 and 2 stairs
    for _ in range(3, n + 1):
        # Calculate the current solution based on the previous two solutions
        current = prev1 + prev2

        # Update the previous solutions for the next iteration
        prev1 = prev2 
        prev2 = current

    return current

נבחן את הפונקציה:

# Test cases
print(climb_stairs(2)) # 2
print(climb_stairs(3)) # 3
print(climb_stairs(4)) # 5
print(climb_stairs(5)) # 8
print(climb_stairs(6)) # 13

הפתרון יעיל ביותר עם סיבוכיות זמן O(N) כש-N תלוי במספר המדרגות וסיבוכיות מקום קבועה כי כל המשתנים המשמשים בפונקציה דורשים מקום אחסון קבוע.

במדריך תכנות דינמי תוכלו לקרוא על הרעיון התכנותי המאוד חשוב עליו ביססתי את הפתרון ואיך כל זה קשור לסדרה חשבונית ע"ש אחד פיבונאצ'י.

 

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

חידה תכנותית: תת מערך בעל סכום מירבי

 

לכל המדריכים בסדרה ללימוד פייתון

 

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים

 

 

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

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

שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

דג למים הוא כמו ציפור ל...?