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

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

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

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

תיאור הבעיה:

ניתן לך מערך של גבהים `heights` באורך n. כל פריט מערך מציין גובה. עליך למצוא שני גבהים (=פריטי מערך) שביחד עם ציר ה-x יוצרים מיכל, כך שהמיכל יכיל את כמות המים המקסימלית.

לדוגמה, אם נתון מערך גבהים:

[2, 2]

אז הגובה המקסימלי הוא בהכרח:

2

למה? האיור הבא מסביר את אופן החישוב:

The max width is 1*2=2 with distance of 1 and height of 2 for the two heights array items

 

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

 

דוגמה נוספת. נתון מערך גבהים:

[2, 1, 3]

בתוך המערך ישנם 3 שטחים אפשריים:

  • כדי לחשב את השטח התחום בין הגבהים 2 ל-1 יש לקחת בחשבון את המרחק בין הגבהים שהוא 1, ואת הגובה הנמוך מבין השניים שהוא 1, ואז לפי נוסחת השטח שהיא גובה * אורך נחשב שטח של: 1 * 1 = 1

  • לפי אותו היגיון, השטח התחום בין הגבהים 1 ו-3 גם הוא 1.

  • כאשר הגבהים התוחמים הם 2 ו-3, הגובה המינימלי מבין הגבהים התוחמים הוא 2 והמרחק בין הגבהים התוחמים הוא 2, ובהתאם השטח הוא: 2 * 2 = 4

מבין שלוש השטחים שטח של 4 הוא הגבוה ביותר ולכן הצפי הוא שעבור קלט של מערך 2,1,3 הפונקציה תנפק את הפתרון 4.

האיור הבא מסביר את הפתרון:

The max area is between the array items with the heights of 2 and 3 with the distance of 2 among the two items and so the area is 2*2=4

 

פתרון יעיל המבוסס על טכניקת שני המצביעים

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

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

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

הפונקציה `container_with_most_water()` מקבלת רשימה של גבהים (`heights`) כקלט. המטרה של הפונקציה היא לחשב את השטח המקסימלי שניתן ללכוד בין שני קווים בגבהים הנתונים. לשם כך, הפונקציה משתמשת בטכניקת שני המצביעים, כאשר `left_cursor` ו-`right_cursor` מאותחלים לתחילת ולסוף הרשימה. מצביעים אלו מייצגים את הרוחב המרבי האפשרי של המיכל.

def container_with_most_water(heights):
    # Goal: compute the maximum area 
    # that can't be less than zero
    max_area = 0
    
    # For this, we use the two pointers technique
    # Initialize two cursors at the ends, representing the maximum width
    left_cursor = 0
    right_cursor = len(heights) - 1

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

# Keep iterating as long as the 2 cursors haven't met
while left_cursor < right_cursor:
    # Get the heights at the left and right cursor positions
    left_height = heights[left_cursor]
    right_height = heights[right_cursor]
  • בתוך הלולאה, הקוד מקבל את הגבהים של הקווים בעמדות הנוכחיות של `left_cursor` ו-`right_cursor`.

`container_height` מייצג את גובה המיכל, והוא נקבע על ידי הקצר מבין שני הקווים. גובה המיכל תמיד מוגבל על ידי הקו הקצר יותר.

# The container's height is limited by the shorter side
 container_height = min(left_height, right_height)

`local_area` מחושב על ידי הכפלת `container_height` ורוחב המיכל, שהוא ההפרש בין העמדות של `left_cursor` ו-`right_cursor`.

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

# Calculate the local area by multiplying height and width
local_area = container_height * (right_cursor - left_cursor)
        
# Update the maximum area if a larger area is found
if local_area > max_area:
    max_area = local_area

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

# Advance the cursor with the lower height as it may find a higher side
if left_height < right_height:
    left_cursor = left_cursor + 1
else:
    right_cursor = right_cursor - 1

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

עכשיו הכל ביחד:

def container_with_most_water(heights):
    # Goal: compute the maximum area 
    # that can't be less than zero
    max_area = 0
    
    # For this, we use the two pointers technique
    # Initialize two cursors at the ends, representing the maximum width
    left_cursor = 0
    right_cursor = len(heights) - 1
    
    # Keep iterating as long as the 2 cursors haven't met
    while left_cursor < right_cursor:
        # Get the heights at the left and right cursor positions
        left_height = heights[left_cursor]
        right_height = heights[right_cursor]
        
        # The container's height is limited by the shorter side
        container_height = min(left_height, right_height)
        
        # Calculate the local area by multiplying height and width
        local_area = container_height * (right_cursor - left_cursor)
        
        # Update the maximum area if a larger area is found
        max_area = max(max_area, local_area)
        
        # Advance the cursor with the lower height as it may find a higher side
        if left_height < right_height:
            left_cursor = left_cursor + 1
        else:
            right_cursor = right_cursor - 1
        
    return max_area

נבחן את הפתרון:

# Test cases
heights = [2,2]
print(container_with_most_water(heights)) # 2

heights = [2,1]
print(container_with_most_water(heights)) # 1

heights = [2,1,2]
print(container_with_most_water(heights)) # 4

heights = [1,2,1,2]
print(container_with_most_water(heights)) # 4

heights = [2,1,2,1]
print(container_with_most_water(heights)) # 4

heights = [2,1,2,1,1,1]
print(container_with_most_water(heights)) # 5

heights = [1,3,1,3,1,1]
print(container_with_most_water(heights)) # 6

heights = [1,8,6,2,5,8,3]
print(container_with_most_water(heights)) # 32

heights = [1,8,6,2,5,4,8,3,7]
print(container_with_most_water(heights)) # 49

heights = [1,5,4,3]
print(container_with_most_water(heights)) # 6

heights = []
print(container_with_most_water(heights)) # 0

   

ניתוח ביצועים

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

  • סיבוכיות מקום: לפונקציה סיבוכיות מקום O(1), שהיא קבועה מכיוון שהיא משתמשת במשתנים התופסים מקום קבוע בזכרון ללא תלות במידות הקלט.

   

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

שימוש בטכניקת שני המצביעים לפתרון בעיות תכנותיות

חידה תכנותית: twoSum

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

   

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

 

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

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

 

 

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

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

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

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

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

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

 

 

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

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