בעיה א'

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

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

while age != ‘-1’:

    print(age)

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

 

(א) כתבו את הפונקציה numsFreq –

def numsFreq(nums):

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

[33, 13, 913, 33, 33, 13]

הפונקציה תחזיר את המילון הזה –

{33:3, 13:2, 913:1}

בהדפסת המילון הזוגות לא יופיעו בהכרח בסדר הזה. 

(ב) כתבו את הפונקציה digitsFreq –

def digitsFreq(nums):

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

[33, 13, 913]

הפונקציה תחזיר את המילון הזה –

{3:3, 1:2, 9:1}

בהדפסת המילון הזוגות בו לא יופיעו בהכרח בסדר הזה.

פתרון

(א) בעיה זו מבקשת מאתנו ליצור מילון. כבר עשינו זאת בפתרון לבעיה הקודמת (בעיה ז). ואולם בפתרון ההוא יצרנו את כל המילון כולו, כלומר את כל הזוגות הנמצאים בו, בהוראה אחת (אמנם בהמשך שינינו את הערכים שאליהם ממופים המפתחות במילון). לעומת זאת כאן נבנה את המילון בהדרגה, זוג אחר זוג. המילון שנבנה הוא מילון מסוג נפוץ למדי: מילון שכיחויות (frequencies dictionary). במילון מסוג זה כל מקרה ומקרה (כאן: ספרות במספרים) ממופה לשכיחויות של המקרה הזה. תכניות רבות נדרשות ליצור מילון כזה, כיוון שהצורך למצוא שכיחויות היא עניין רווח בתכנות. בסעיף זה של השאלה, בניית המילון היא פשוטה למדי, הואיל וקבלת הערכים הנדרשים לצורך הוספת הזוגות למילון היא קלה: המפתחות נתונים ברשימה nums, והערך שכל מספר (מפתח) ימופה אליו המילון מתקבל בהוראה אחת: זימון הפונקציה count. הנה לפניכם מימוש הפונקציה numsFreq –

def numsFreq(nums): 

    d = {} 

    for num in nums: 

        d[num] = nums.count(num)

    return d

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

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

[33, 13, 913, 33, 33, 13]

המספר 33 ייסרק שלוש פעמים. בסריקה הראשונה יוכנס למילון הזוג 33:1. בסריקה השניה יעודכן הערך במילון שאליו ממופה המפתח 33: במקום 1 יוכנס 1, וכך יקרה גם בסריקה השלישית. דוגמה נוספת: הרשימה nums מכילה מיליארד מספרים, וכולם הם 33. במקרה זה יתבצעו מיליארד פחות אחת עדכונים מיותרים של המילון. כדי להימנע מעדכונים מיותרים כאלה נסרוק לא את nums כי אם קבוצה (set) של המספרים השונים זה מזה ברשימה –

def numsFreq(nums): 

    d = {} 

    for num in set(nums): 

        d[num] = nums.count(num)

    return d

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

def numsFreq(nums):     

    return {num : nums.count(num) for num in set(nums)}

 

print(numsFreq([33, 13, 913, 33, 33, 13]))

>>>

{33: 3, 913: 1, 13: 2}

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

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

for num in nums: 

    digits = set(str(num))

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

def digitsFreq(nums):    

    d = {} 

    for num in nums: 

        digits = set(str(num))

        for digit in digits:             

            intDigit = int(digit)

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

איך נתקדם מכאן? ספציפית: כיצד נבצע את ההכנסה למילון או את העדכון שלו כשיש בידינו כל ספרה וספרה בכל מספר ומספר? ננסה להבין זאת באמצעות הדגמת הסריקה עד כה עבור הרשימה nums זו –

[33, 13, 913]

בסיבוב הראשון של הלולאה החיצונית num == 33, וללולאה הפנימית יש סיבוב אחד בלבד – עבור הספרה 3. בשלב זה המילון ריק, ויש להוסיף אליו את הזוג הזה –

{3:1}

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

בסיבוב השני של הלולאה החיצונית num = 13, וללולאה הפנימית יש שני סיבובים: האחד עבור הספרה 1 והשני עבור הספרה 3 (לא בהכרח בסדר זה; מדוע?). נניח שראשית מיתוסף הזוג שבו המפתח הוא הספרה 1 והערך 1 (יש בינתיים מספר אחד המכיל את הספרה 1, והוא המספר הנסרק כרגע, 13)  –

{3:1, 1:1}

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

{3:2, 1:1}

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

• מצב א’: הספרה אינה נמצאת במילון – אז מתבצעת הוספת זוג חדש למילון: בזוג זה המפתח הוא הספרה והערך הוא 1.  

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

לאור תובנה זו נשלים את כתיבת הפונקציה. הנה גרסתה הסופית –

def digitsFreq(nums):    

    d = {} 

    for num in nums: 

        digits = set(str(num))

        for digit in digits:             

            intDigit = int(digit)

            if intDigit not in d: 

                d[intDigit] = 1 

            else: 

                d[intDigit] += 1

    return d 

        

print(digitsFreq([33, 13, 913]))

>>>

{3: 3, 1: 2, 9: 1}

 

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

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

def digitsFreq(nums):    

    digits = set() 

    for num in nums: 

        digits = digits | set(str(num))

    for digit in digits:

        d[digit] = ?

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

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

 

הפתרון לבעיה מתחיל ביצירת קבוצה ריקה, digits, וממשיך בסריקת כל האוספים הנתונים – כאן: קבוצות של ספרות במספרים (למעשה: קבוצות של מחרוזות המכילות את הספרות במספרים) – והוספת הספרות בכל קבוצה נסרקת לקבוצה digits ההולכת ונבנית. כיוון שבקבוצה אין כפילויות, הקבוצה digits תכיל בסוף הלולאה ספרות שונות זו מזו (מכל המספרים). שימו לב שהפעולה המתבצעת כאן היא איחוד או צירוף (באמצעות האופרטור | ), ומכאן שבקבוצה digits בצורתה הסופית יש ספרות שאינן מופיעות בכל המספרים שברשימה nums (כך בהינתן רשימת הדוגמה הקבוצה digits תכיל את המחרוזת-ספרה ‘1’ והספרה 1 אינה נמצאת במספר 33) . בשאלה 15 נראה כיצד לבנות קבוצה המכילה את כל הערכים המופיעים בכל אחד ואחד מכמה אוספים נתונים. 

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