בעיה י"ד

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

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

while age != ‘-1’:

    print(age)

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

 

(א) נתון מילון הבנוי כך: כל מפתח בו הוא מספר שלם לא שלילי. נקרא לו n . כל ערך הוא רשימה שיש בה רשימה אחת או יותר. בכל רשימה פנימית יש זוג ערכים, בסדר זה: מילה שהאות a או האות A מופיעות בה n פעמים, ו-True אם המילה היא שם של מקום או False אם היא אינה שם של מקום. מילה (מחרוזת) לא יכולה להופיע יותר מפעם אחת במילון. דוגמה למילון – כאן מוצב במשתנה aS –

aS = {1 : [[“cat”,False],[“Siam”,True],[“dating”,False]],

      2 : [[“Aachen”,True], [“Barbados”,True]],

      3 : [[“malaria”,False]]}

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

def deleteWord(myDict, word):

לפונקציה שני פרמטרים: myDict, מילון במבנה של המילון aS, ומילה (מחרוזת) word המופיעה במילון myDict. הפונקציה מוחקת מהמילון myDict את הרשימה הפנימית שהמילה word מופיעה בה (יש רק רשימה אחת כזו). אם לאחר המחיקה נוצר במילון זוג שהערך בו הוא רשימה ריקה, הזוג הזה נמחק מהמילון. הפונקציה מחזירה את המילון myDict לאחר מחיקת המילה word ממנו. 

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

deleteWord(aS, “cat”))

ימחק את הרשימה הפנימית שהמילה ‘cat’ מופיעה בה, ויחזיר את המילון הזה –

{1: [[‘Siam’, True], [‘dating’, False]], 

 2: [[‘Aachen’, True], [‘Barbados’, True]], 

 3: [[‘malaria’, False]]}

והזימון הזה –

deleteWord(aS, “malaria”)

ימחק את הרשימה הפנימית שהמילה ‘malaria’ מופיעה בה, וכיוון שזו הרשימה הפנימית היחידה ברשימה שאליה ממופה המפתח 3, הזוג כולו יימחק מהמילון, ויוחזר המילון הזה –

{1: [[‘cat’, False], [‘Siam’, True], [‘dating’, False]], 

  2: [[‘Aachen’, True], [‘Barbados’, True]]}

(ב) נתון מילון הבנוי כך: כל מפתח הוא מספר שלם לא שלילי. נקרא לו n. כל ערך הוא רשימה שיש בה מילה אחת או יותר. בכל מילה האות a או האות A מופיעות n פעמים. המילים ברשימה ממוינות לפי אורכן, מהקצרה ביותר לארוכה ביותר. דוגמה למילון – כאן מוצב במשתנה aS –

aS = {1 : [“cat”, “Siam”, “Mali”, “dating”], 

      2 : [“Aachen”, “Barbados”], 

      3 : [“malaria”]}

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

def insertWord(myDict, word):

לפונקציה שני פרמטרים: myDict, מילון במבנה של המילון aS, ומילה (מחרוזת) word. הפונקציה מוסיפה את המילה word למילון myDict באופן זה: 

• אם יש במילון myDict מפתח שהוא מספר הפעמים שהאות a או האות A מופיעות במילה word, הפונקציה תכניס את המילה word לרשימה שהיא הערך של המפתח הזה. המילה תוכנס לרשימה לפי ארכה, וההכנסה תשמור על סדר המיון מהמילה הקצרה ביותר למילה הארוכה ביותר. הנה שתי דוגמות, ובשתיהן הארגומנט aS הוא מילון הדוגמה –

>>> print(insertWord(aS, ‘Guam’))

{1: [‘cat’, ‘Guam’, ‘Siam’, ‘Mali’, ‘dating’], 

 2: [‘Aachen’, ‘Barbados’], 

3: [‘malaria’]}

כיוון שבמילה ‘Guam’ האות ‘a’ מופיעה פעם אחת (ואין מופיעה בה האות ‘A’) מילה זו מוכנסת לרשימה שאליה ממופה המפתח 1. וכיוון שאורך המילה הוא 4 היא ממוקמת בתוך רצף המילים שאורכן 4. אפשר להכניס אותה בין המילה ‘cat’ שאורכה 3 לבין המילה הראשונה שאורכה 4, ‘Siam’, כמו כאן, גם הכנסה למקום אחר השומר על המיון לפי האורך. 

דוגמה נוספת – הכנסת המילה ‘ma’ –

>>> print(insertWord(aS, ‘ma’))

{1: [‘ma’, ‘cat’, ‘Siam’, ‘Mali’, ‘dating’], 

 2: [‘Aachen’, ‘Barbados’], 3: [‘malaria’]}

כיוון שבמילה ‘ma’ האות ‘a’ מופיעה פעם אחת (ואין מופיע בה האות ‘A’) גם מילה זו מוכנסת לרשימה שאליה ממופה המפתח 1. וכיוון שאורך המילה הוא 2 והמילה הקצרה ביותר ברשימה אורכה 3 (‘cat’), המילה ‘ma’ ממוקמת בתחילת הרשימה. 

• אם אין במילון myDict מפתח שהוא מספר הפעמים שהאות ‘a’ או האות ‘A’ מופיעות במילה word, הפונקציה תיצור זוג חדש במילון myDict: המפתח יהיה מספר הפעמים הזה והערך יהיה רשימה המכילה את word בלבד. הנה דוגמה ובה הארגומנט aS הוא מילון הדוגמה –

>>> print(insertWord(aS, ‘Casablanca’))

{1: [‘cat’, ‘Siam’, ‘Mali’,’dating’], 

 2: [‘Aachen’, ‘Barbados’], 

 3: [‘malaria’], 

 4: [‘Casablanca’]}

במילון המועבר לפונקציה אין מפתח שאורכו כמספר הפעמים שהאות ‘a’ מופיעה במילה ‘Casablanca’, כלומר 4. לכן מיתוסף  למילון זוג חדש שהמפתח בו הוא המספר 4 והערך הוא רשימה המכילה את המילה ‘Casablanca’.

הפונקציה מחזירה את המילון myDict המעודכן.

פתרון

(א) בבסיס השאלה נמצאת בעיה זו: 

איתור ערך הנמצא באוסף הנמצא באוסף שיש בו אוספים פנימיים נוספים. 

ספציפית עלינו למצוא מילה, שהיא עצמה ערך אחד (מתוך שניים) ברשימה פנימית, הנמצאת בתוך רשימה שיש בה רשימות פנימיות נוספות. רשימת הרשימות הזאת היא עצמה ערך של מפתח במילון. מובן שאיתור המילה, ולאחר מכן גם מחיקת הרשימה הפנימית שהיא נמצאת בה, ואולי מחיקת הזוג מפתח-ערך במילון שהרשימה הפנימית הזאת נכללת בו – כל אלה יעשו אגב התמקדות בזוג המסוים הזה.. למשל אם עלינו למחוק את המילה ‘cat’ מהמילון הזה – 

aS = {1 : [[“cat”,False],[“Siam”,True],[“dating”,False]],

      2 : [[“Aachen”,True], [“Barbados”,True]],

      3 : [[“malaria”,False]]}

אז כל הפעולות שנבצע יתמקדו בזוג המסוים שהמילה ‘cat’ נמצאת בערך (ברשימה) שבו. נגדיר אפוא משתנה המחזיק את המפתח של הזוג הזה, כך –

key = word.lower().count(‘a’)

המפתח בזוג הוא מספר ההופעות של האות a או האות A במילה word. כדי למנות את ההופעות של שתי האותיות הללו הפכנו כל אות “גדולה” (upper case) לאות “קטנה” (lower case) באמצעות הפונקציה lower.

עתה, באמצעות key, המפתח בזוג שעלינו להתמקד בו, נוכל לגשת לערך (הרשימה) בזוג, כך –

myDict[key]

הצעד הבא הוא לאתר, בתוך הרשימה שהמפתח key ממופה אליה, את הרשימה הפנימית שבה נמצאת word. נעדיף להשתמש כאן בלולאת while כיוון שנרצה להמשיך בחיפוש רק כל עוד טרם מצאנו את המילה. בנוסף, במבט קדימה נשים לנו למטרה להחזיק בידינו בסוף הלולאה את  האינדקס של הרשימה הפנימית המכילה את word, כדי שנוכל למחוק את הרשימה הזאת מהמילון באמצעות האופרטור del. הנה הצעה למימוש הלולאה –

i = 0 

while myDict[key][i][0] != word: 

    i = i + 1

המשתנה i מחזיק אינדקס של רשימה פנימית ברשימה שאליה ממופה key. לפני הלולאה הוא מאותחל ל-0 כדי “להצביע” על הרשימה הפנימית הראשונה, ובכל סיבוב של הלולאה ערכו גדל ב-1 כדי “לעבור” לרשימה הפנימית הבאה. בתחילת כל סיבוב אנו בודקים אם המילה הנמצאת באינדקס 0 ברשימה הפנימית שבאינדקס i אינה word, כלומר אם טרם הגענו לרשימה הפנימית המכילה את word (וכאמור בוודאות יש כזו). בדיקת התנאי הזה מתבצעת באמצעות שלוש הפעלות רצופות של האופרטור [ ] – 

• הפעלה ראשונה על מילון – myDict[key] – כאן מתקבלת הרשימה שהמפתח key ממופה אליה, וכפי שהוסבר לעיל זו הרשימה שיש בה רשימה פנימית המכילה את word.

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

• הפעלה שלישית על הרשימה הפנימית הזאת – כדי לקבל את המילה הנמצאת בה (באינדקס 0). 

כשהמילה ברשימה הפנימית הנוכחית זהה למילה word תנאי הלולאה מחזיר False, כיוון שכבר לא מתקיים המצב שהמילה ברשימה הפנימית שונה מ-word. או אז הלולאה נפסקת, והמשתנה i מכיל את האינדקס של הרשימה הפנימית שהמילה word מופיעה בה. 

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

aS = {1 : [[“cat”,False],[“Siam”,True],[“dating”,False]],

      2 : [[“Aachen”,True], [“Barbados”,True]],

      3 : [[“malaria”,False]]}

וגם נניח שאנו מחפשים את המילה ‘Siam’. טבלת המעקב הזאת מתארת את פעולת לולאת החיפוש שהוצגה למעלה (להסבר המבנה של טבלת מעקב ראו למעלה, בעיה ג’) –

כפי שאפשר לראות, הלולאה נעצרת בסריקה של הרשימה הפנימית השניה ברשימה שאליה ממופה המפתח 1; ברשימה פנימית זו מופיעה המילה שחיפשנו, ‘Siam’. בסוף הלולאה המשתנה i מכיל את האינדקס של רשימה פנימית זו. לאחר שאינדקס זה בידינו, עלינו למחוק את הרשימה הפנימית. כאמור לשם כך נשתמש באופרטור del –

del myDict[key][i]

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

def deleteWord(myDict, word):  

    key = word.lower().count(‘a’)

    i = 0 

    while myDict[key][i][0] != word: 

        i = i + 1    

    del myDict[key][i]

    if not myDict[key]: 

        del myDict[key]

    return myDict

מבנה ה-if בסוף הפונקציה בודק אם לאחר המחיקה התרוקנה הרשימה שאליה ממופה key, ואם זה המצב מוחק מהמילון את המפתח הזה ואת הרשימה שהוא ממופה אליה. 

 

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

key = word.lower().count(‘a’)

בכל זאת יש שני הבדלים חשובים בין השאלה בסעיף זה לשאלה בסעיף הקודם. ראשית הפעם אין ידוע שהמילה word נמצאת במילון, או, ליתר דיוק, אין ידוע שיש במילון זוג שהמפתח בו הוא key. לכן עלינו לטפל הן במצב שהמפתח key נמצא במילון הן במצב שהמפתח אינו נמצא במילון. המצב שהמפתח אינו נמצא במילון מודגם בגוף השאלה בדוגמה המכניסה למילון את המילה ‘Casablanca’. הטיפול במצב זה הוא פשוט למדי. הנה הקוד –

if key not in myDict: 

    myDict[key] = [word] 

במצב האחר, כלומר כש-key הוא מפתח במילון, עלינו לפתור בעיה דומה לזו שפתרנו בדיון בסעיף הקודם, הווה אומר למצוא את האינדקס של ערך ברשימה שאליה ממופה המפתח key. הפעם נרצה למצוא את האינדקס כדי שנוכל להכניס את המילה למקומה המתאים ברשימה, לפי אורך המילה, באופן שיישמר ארגון המילים ברשימה מהמילים הקצרות ביותר למילים הארוכות ביותר. למשל נניח שנרצה להכניס את המילה ‘Guam’ לרשימה הזאת –

[‘cat’, ‘Siam’, ‘Mali’, ‘dating’]

ברשימה זו יש כמה מקומות שאליהם נוכל להכניס את המילה ‘Guam’ – 

• בין המילה ‘cat’ למילה ‘Siam’

• בין המילה ‘Siam’ לבין המילה ‘Mali’

• או בין המילה ‘Mali’ למילה ‘dating’

נבחר להוסיף את ‘Guam’ בין המילה ‘cat’ למילה ‘Siam’ או, בניסוח כללי, בין המילה האחרונה בקבוצת המילים שאורכן קטן מאורך המילה word, למילה הראשונה בקבוצת המילים שאורכן שווה לאורך המילה word או גדול ממנו. הנה הצעה לקוד המוצא את האינדקס של מקום ההכנסה המתאים –

i = 0         

while len(word) > len(myDict[key][i]):            

        i = i + 1

ודאי תוכלו להבחין כי המבנה של לולאה זו דומה מאוד למבנה של הלולאה שכתבנו בסעיף א’. גם כאן המשתנה i מחזיק בכל סיבוב וסיבוב אינדקס לערך הנמצא ברשימה שאליה ממופה המפתח key, כלומר אינדקס לרשימה שאליה יש להכניס את המילה word. ההבדל בין הלולאה כאן לזו שכתבנו בסעיף הקודם נעוץ בתנאי הלולאה: לפי התנאי כאן, הלולאה תמשיך להסתובב כל עוד האורך של המילה הנמצאת באינדקס הנוכחי ברשימה הוא קטן מהאורך של המילה word. כשהלולאה תעצר המשתנה i יכיל את האינדקס של המילה הבאה לאחר המילה האחרונה ברשימה שאורכה קטן מאורך המילה word, ומילה זו אינה אלא המילה הראשונה בקבוצת המילים שאורכן שווה לאורך המילה word או גדול ממנו. טבלת המעקב הזאת עוקבת אחר ביצוע הלולאה עבור הדוגמה שניתנה למעלה (הכנסת המילה ‘Guam’) –

ברגע שמצאנו מילה ברשימה שאורכה שווה לרשימה שיש להכניס לרשימה, כאן: המילה ‘Siam’ שאורכה 4, הלולאה נעצרה והמשתנה i מכיל את האינדקס שאליו נכניס את המילה. לצורך ההכנסה נשתמש בפונקציה insert, כך – 

myDict[key].insert(i, word)

שימו לב: אם לכל המילים ברשימה שאליה יש להכניס את word יש אורך הגדול מאורכה של word, יש להכניס את המילה לראש הרשימה, כלומר להכניסה בתור המילה באינדקס 0. המימוש למעלה יפעל במקרה זה כנדרש: מיד בבדיקה הראשונה של תנאי הלולאה יתברר כי הוא אינו מתקיים (כי אורך המילה הראשונה גדול מאורך המילה שיש להכניס), ווהמשתנה i יכיל 0, האינדקס שאליו נכניס את המילה. 

מה בנוגע למצב “ההפוך”, כלומר למצב שבו לכל המילים ברשימה שאליה מוכנסת word יש אורך הקטן מאורכה של word? במצב זה תוצאת החישוב של הביטוי הנבדק בתנאי הלולאה תמיד תהיה True. כך יהיה גם כאשר נסיים לסרוק את כל המילים ברשימה, ובנקודה זו המשתנה i, כיוון שבסיבוב האחרון של הלולאה שוב יקודם ב-1, יכיל מספר שכבר אינו נמצא במערכת האינדקסים של הרשימה (לשם דיוק: הוא יהיה גדול ב-1 מהאינדקס האחרון במערכת זו). לכן הרצת הקוד כפי שהוא כתוב כרגע תוציא הודעת שגיאה זו –

    while len(word) > len(myDict[key][i]):

IndexError: list index out of range

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

def insertWord(myDict, word):  

    key = word.count(‘a’)

    if key not in myDict: 

        myDict[key] = [word]

    else: 

        i = 0         

        while i < len(myDict[key]) and len(word) > len(myDict[key][i]):          

            i = i + 1

        myDict[key].insert(i, word)

    return myDict

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