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

בגרם מדרגות נתון יש מספר של 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 כוכבים