בעיה ט'

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

age = input(‘Insert age; -1 to stop: ‘)

while age != ‘-1’:

    print(age)

    age = input(‘Insert age; -1 to stop: ‘)

 

eruptions היא רשימה של רשימות. היא מכילה מידע על התפרצויות הרי געש. בכל רשימה פנימית יש שלושה ערכים, בסדר זה מהראשון לאחרון: מחרוזת המכילה תאריך, שם (מחרוזת) של הר הגעש שהתפרץ, ודרגת ההתפרצות (מספר בין 0 כולל ל-9 כולל). הנה דוגמה לרשימה eruptions –

eruptions = [ [“13.1.1975”, “M1”, 7], [“8.11.1989”, “M3”, 3], [“4.5.1989”, “M1”, 2], [“17.4.2000”, “M2”, 5], [“13.6.2014”, “M3”, 6] ]

הנתונים ברשימה הם להדגמה בלבד. בנוסף הרשימה אינה ממוינת. 

כתבו את הפונקציה mostActive –

def mostActive(eruptions, measure):

לפונקציה שני פרמטרים אלה: 

• eruptions – רשימה במבנה שתואר למעלה

• measure – מספר המציין דרגת התפרצות של הר געש

הפונקציה מוצאת את שם ההר שהיו לו הכי הרבה התפרצויות שהדרגה שלהן הייתה גדולה יותר מ-measure. אפשר להניח שיש רק הר אחד כזה. 

לדוגמה עבור רשימת הדוגמה, הזימון הזה – 

mostActive(eruptions, 2)

יחזיר את המחרוזת “M3” .

פתרון

בעיה זו מביאה אותנו, לראשונה בדיוננו עד כה, לעסוק בטיפול באוסף של אוספים. כזה הוא האוסף eruptions המוצג בבעיה; ספציפית הוא רשימה של רשימות. הפתרון שנציע לבעיה כרוך ביצירת מילון שכיחויות, ומבחינה זו הוא דומה מאוד לפתרון לסעיף ב’ של בעיה ח’. בכל זאת יש הבדלים חשובים בין שני הפתרונות. הניסוח של בעיה ח’ הוא “טכני” (נתונה רשימה ויש לעשות כך וכך), ואילו הניסוח של הבעיה הזאת הוא “סיפורי”. לכן נדרש כאן מאמץ רב יותר בתכנון האלגוריתם שהפתרון ייוסד עליו. בייחוד כאן לא נאמר במפורש שיש ליצור מילון, ובקריאה ראשונה אפשר שלא יעלה על דעתנו להשתמש במילון, וממילא לא במילון שכיחויות. הניסוח של המבוקש בבעיה הנוכחית הוא זה: “הפונקציה מוצאת את שם ההר שהיו לו הכי הרבה התפרצויות שהדרגה שלהן הייתה גדולה יותר מ-measure.” כדי למצוא את שם ההר הזה אין הכרח ליצור מילון שכיחויות. אפשר למשל להסמיך את המימוש על אלגוריתם זה –

(1) נסרוק את הרשימה eruptions ונכין רשימה של שמות ההרים שאין בה כפילויות (כלומר כל שם הר מופיע בה פעם אחת). שם הרשימה: names. מימוש בקוד –

names = set() 

for eruption in eruptions:

     names.add(eruption[1])

names = list(names)

קוד זה יכול להפיק למשל את הרשימה הזאת –

[“M1”, “M2”, “M3”]

אפשר שסדר שמות ההרים ברשימה לא יהיה לפי סדר סריקת הרשימות הפנימות (מדוע?) 

הואיל ושלוש השורות הראשונות בקוד ערוכות בתבנית של יצירת אוסף חדש לפי סריקת אוסף קיים בלולאת for (ראו לעיל בעיה א’), נוכל לקצרו באמצעות ביטוי Set Comprehension כך –

names = list({eruption[1] for eruption in eruptions})

(2) נכין רשימה שאורכה כמספר השמות ברשימת שמות ההרים ומכילה אפסים, שם הרשימה: counts. מימוש בקוד –

counts = [0] * len(names)

עבור רשימת הדוגמה, הקוד ייצור את הרשימה הזאת –

[0, 0, 0]

עד לסוף ביצוע הפונקציה הרשימה counts תכיל עבור כל הר את מספר ההתפרצויות שלו שעצמתן גדול מ-measure. יש התאמה בין הערכים הנמצאים באינדקסים שווים ברשימה counts וברשימה names: כך למשל לפי הדוגמה לרשימה names שהוצגה בתיאור צעד 1, מספר ההתפרצויות שעצמתן גדול מ-measure של ההר ששמו “M2” נמצאת באינדקס 1 ברשימה counts. 

(3) לאחר מכן נסרוק שוב את הרשימה eruptions, רשימה פנימית אחר רשימה פנימית, ועבור כל רשימה פנימית, אם דרגת ההתפרצות המופיעה בה גדולה מ-measure, נגדיל ב-1 את אחד המספרים ברשימה counts: המספר המונה את מספר ההתפרצויות של ההר ששמו מופיע ברשימה הפנימית הנסרקת הנוכחית; כאמור בצעד 2, נוכל להגיע אל המספר הזה באמצעות האינדקס של המקום ברשימה names שבו מופיע שם ההר המופיע ברשימה הפנימית הנסרקת הנוכחית. מימוש בקוד –

for eruption in eruptions:

    if eruption[2] > measure: 

        counts[names.index(eruption[1])] += 1

עד לסוף הסריקה בצעד זה הרשימה counts תכיל עבור כל שם הר את מספר ההתפרצויות שלו הגדולות מ-measure.  

(4) לבסוף נמצא את האינדקס של המספר המקסימלי שיש ברשימה counts בסוף צעד 3 (לפי השאלה המספר המקסימלי צריך להופיע ברשימה זו פעם אחת בלבד), ונחזיר את שם ההר המופיע באינדקס זה ברשימה names. מימוש בקוד –

maxName = names[counts.index(max(counts))]

return maxName

הנה המימוש במלואו, הפעם כחלק מהפונקציה במלואה –

def mostActive(eruptions, measure): 

    # 1 

    names = list({eruption[1] for eruption in eruptions})    

    # 2 

    counts = [0] * len(names)        

    # 3 

    for eruption in eruptions:

        if eruption[2] > measure: 

            counts[names.index(eruption[1])] += 1

    # 4 

    maxName = names[counts.index(max(counts))]

    return maxName

 

eruptions = [ [“13.1.1975″,”M1”,7], 

              [“8.11.1989″,”M3”,3], 

              [“4.5.1989″,”M1”,2], 

              [“17.4.2000″,”M2”,5], 

              [“13.6.2014″,”M3”,6] ]

print(mostActive(eruptions, 2))

>>>

‘M3’

הרשימה המוכנת בצעד 2 מכונה לעתים “רשימת מונים”. הייעוד שלה הוא למנות את מספר ההיקרויות של קבוצה מוגבלת, על פי רוב קטנה, של מקרים. היא מסייעת בטיפול במצב נפוץ בתכנות, כלומר חישוב שכיחויות. מהלך העניינים הכללי של שימוש בה הוא זה: יצירת אוסף, למשל רשימה, והגדרת אורכה בתור מספר המקרים הקיימים, אתחול כל “התאים” בה ל-0, ואחר כך סריקה של אוסף שבו כל מקרה מופיע מספר כלשהו של פעמים והגדלה ב-1 של המספר המופיע ברשימה ותואם למקרה הנסרק הנוכחי.

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

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

eruptions = [ [“13.1.1975″,”M1”,7], 

              [“8.11.1989″,”M3”,3], 

              [“4.5.1989″,”M1”,2], 

              [“17.4.2000″,”M2”,5], 

              [“13.6.2014″,”M3”,6] ]

measure = 2 

mountains = {} 

for eruption in eruptions:

    thisMountain, thisMeasure = eruption[1:]

    if thisMeasure > measure: 

        if thisMountain not in mountains: 

            mountains[thisMountain] = 1

        else:

            mountains[thisMountain] += 1   

print(mountains)

>>>

{‘M1’: 1, ‘M3’: 2, ‘M2’: 1}

לאחר הגדרת מילון ריק, הלולאה סורקת רשימה פנימית אחר רשימה פנימית ברשימה eruptions. בגוף הלולאה אנחנו מתחילים בקבלת שם ההר ודרגת ההתפרצות המופיעים ברשימה הפנימית הנסרקת הנוכחית (שלב זה אינו הכרחי ונעשה כאן לצורך בהירות הקוד; אפשר להסתפק בהפעלת האופרטור [ ] על הרשימה הפנימית והעברת האינדקסים 1 ו-2 לאופרטור). אם מצאנו שדרגת ההתפרצות גדולה מ-measure, הבחנו בין שני מקרים אלה: אם שם ההר עדיין אינו מפתח במילון, מיפינו אותו לשכיחות 1, ואם הוא כבר מפתח במילון הגדלנו ב-1 את השכיחות שהוא ממופה אליה. עד לסוף הלולאה יהיה בידינו המילון ובו השכיחויות המבוקשות. 

כשיש בידינו שכיחות ההתפרצויות הגדולות מ-measure של כל הר והר, כל שנותר הוא למצוא את שם ההר ששכיחות התפרצויותיו היא הגדולה ביותר (לפי ההנחה בבעיה יש הר אחד כזה). הבעיה הכללית שיש לפתור בצעד זה היא זו: 

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

יש למצוא את המפתח הממופה למספר זה. 

 

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

def mostActive(erruptions, measure): 

    mountains = {} 

    for erruption in erruptions: 

        if erruption[2] > measure: 

            if erruption[1] not in mountains: 

                mountains[erruption[1]] = 1

            else:

                mountains[erruption[1]] += 1   

    maxFreq = max(mountains.values())

    for name, freq in mountains.items():

        if freq == maxFreq: 

            return name     

 

eruptions = [ [“13.1.1975”, “M1”, 7], [“8.11.1989”, “M3”, 3], [“4.5.1989”, “M1”, 2], [“17.4.2000”, “M2”, 5], [“13.6.2014”, “M3”, 6] ]

mostActive(eruptions, 2)

>>>

‘M3’

לפני סריקת הזוגות במילון השכיחויות מצאנו את השכיחות המקסימלית באמצעות הפעלת הפונקציה max על אוסף הערכים (values) שבמילון. השתמשנו בשכיחות זו בשעת הבדיקה של כל זוג וזוג במילון. ברגע שמצאנו אותה החזרנו את המפתח, כלומר את שם ההר, בזוג. 

שימו לב שהוראת ה-return נמצאת בתוך הלולאה, ומחוץ ללולאה אין הוראת return. הסיבה היא שכאן ידוע בוודאות שתנאי הלולאה יתקיים לפחות פעם אחת, או, בניסוח אחר: שלא יקרה מצב שלא נמצא הר ששכיחותו היא הגדולה ביותר. תנו גם דעתכם כי יכולנו לקטוע את הלולאה באמצעות הוראת return כיוון שהלולאה נמצאת בתוך פונקציה; אם לא זה היה המצב היה עלינו לשכתב מעט את הקוד (ראו בעיה א’). 

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

def mostActive(erruptions, measure): 

    mountains = {} 

    for erruption in erruptions: 

        if erruption[2] > measure: 

            if erruption[1] not in mountains: 

                mountains[erruption[1]] = 1

            else:

                mountains[erruption[1]] += 1       

    revMountains = [] 

    for name, freq in mountains.items() :

        revMountains.append([freq, name])

    return sorted(revMountains, reverse = True)[0][1]

 

 

eruptions = [ [“13.1.1975”, “M1”, 7], [“8.11.1989”, “M3”, 3], [“4.5.1989”, “M1”, 2], [“17.4.2000”, “M2”, 5], [“13.6.2014”, “M3”, 6] ]

mostActive(eruptions, 2)

הלולאה המופיעה לפני הוראת ה-return יוצרת רשימה של זוגות שכיחות-שם הר, וכל זוג נמצא ברשימה פנימית (אפשר לשמור גם ברשומה פנימית). אפשר לכתבה באמצעות ביטוי List Comprehension כך (ראו בעיה א’) – 

revMountains = [[freq, name] for name, freq in mountains.items()]

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

[[2, ‘M3’], [1, ‘M2’], [1, ‘M1’]]

לאחר יצירת הרשימה הממוינת כל שנותר הוא לקחת, מהרשימה הפנימית שבאינדקס 0 – בה מופיע המספר המקסימלי באוסף הערכים של המילון – את הערך המופיע בה באינדקס 1, כלומר את שם ההר ששכיחותו הגדולה ביותר. הצעד הזה מתבטא בקוד בהפעלה כפולה של האופרטור [ ] – הפעלה ראשונה כדי לקבל את הרשימה הפנימית באינדקס 0, והפעלה שניה כדי לקבל את הערך באינדקס 1 ברשימה פנימית זו, כלומר שם ההר. אם היינו ממיינים את הרשימה revMountains בסדר עולה (למעשה: לא יורד) היה עלינו לגשת לרשימה הפנימית האחרונה ברשימה הממוינת (בהפעלה הראשונה של האופרטור [ ] היינו מניחים 1- בין הסוגריים המרובעים). 

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