בעיה ג'

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

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

while age != ‘-1’:

    print(age)

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

 

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

def sortPositives(nums):

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

[-1, 5, 3, -2, 0, 3, 1]

המספרים החיוביים ברשימה הם 5, 3, 3 ו-1, בסדר זה; הם אינם ממוינים בסדר עולה. כמו כן הם ממוקמים באינדקסים 1, 2, 5, ו-6 של הרשימה. במקרה זה תחזיר הפונקציה sortPositives את הרשימה הזאת –

[-1, 1, 3, -2, 0, 3, 5]

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

פתרון

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

נתונה רשימה של מספרים שלמים.

יש ליצור רשימה ממוינת של כל המספרים החיוביים ברשימה, ושלהם בלבד.

 

בניסוח כללי הבעיה היא זו –

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

ואותם בלבד. 

 

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

nums = [-1, 5, 3, -2, 0, 3, 1]

positiveNums = [] 

for num in nums: 

    if num > 0: 

        positiveNums.append(num)

print(positiveNums)

>>>

[5, 3, 3, 1]

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

positiveNums.sort()

הפונקציה sort ממיינת את הרשימה במקום (in place), כלומר היא משנה את הרשימה positiveNums גופה. במקרה זה אין לנו צורך לשמור את הרשימה המקורית, כלומר זו לפני המיון. אם יש צורך בכך נשתמש בפונקציה sorted כך –

sortedLst = sorted(positiveNums)

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

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

nums = [-1, 5, 3, -2, 0, 3, 1]

positiveNums = [] 

for num in nums: 

    if num > 0: 

        positiveNums.append(num)

positiveNums.sort() 

>>>

[1, 3, 3, 5]

כיצד ממשיכים מכאן? ברור שעלינו לשבץ את המספרים ברשימה הממוינת positiveNums במקום המספרים החיוביים שברשימה המקורית nums. הנקודה החשובה כאן היא שההחלפה היא “עיוורת” למספרים המוחלפים: היא רואה אך ורק את האינדקסים שבהם יש למקם את המספרים מהרשימה הממוינת, כפי שממחיש האיור הזה – 

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

def sortPositives(nums):

    positiveNums = [] 

    for num in nums: 

        if num > 0: 

            positiveNums.append(num)

    positiveNums.sort()

    j = 0 

    for i in range(len(nums)): 

        if nums[i] > 0: 

            nums[i] = positiveNums[j]

            j += 1 

    return nums

    

print(sortPositives([-1, 5, 3, -2, 0, 3, 1]))

>>>

[-1, 1, 3, -2, 0, 3, 5]

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

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

nums = [-1, 5, 3, -2, 0, 3, 1]

inds = []     

positiveNums = [] 

for i in range(len(nums)):         

    if nums[i] > 0: 

        positiveNums.append(nums[i])

        inds.append(i)

positiveNums.sort() 

print(inds)

>>>

[1, 2, 5, 6]

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

positiveNums.append(num)

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

positiveNums.append(nums[i])

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

[1, 3, 3, 5]

וזו רשימת האינדקסים inds –

[1, 2, 5, 6]

נסרוק אינדקס-אינדקס ברשימה inds, ונשתמש בכל אינדקס ובאופרטור [ ] כדי לבצע את הההחלפה. למשל עבור הערך הראשון ברשימה inds נבצע –

nums[1] = 1

ועבור הערך השני ברשימה inds נבצע –

nums[2] = 3

ואולם אם נממש את הגישה הזאת בקוד תצוץ בעיה –

for ind in inds:   

    nums[ind] = positiveNums[?]

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

[-1, 5, 3, -2, 0, 3, 1]

וזו רשימת המספרים החיוביים הממוינת –

[1, 3, 3, 5]

וזו רשימת האינדקסים הנסרקים –

[1, 2, 5, 6]

הלולאה כפי שכתבנו אותה אינה מאפשרת לנו לדעת שהמספר שיש כרגע באינדקס 1 ברשימה nums, כלומר 5, צריך להיות מוחלף במספר שיש באינדקס 0 ברשימה positiveNums, כלומר ב-1. 

פתרון הקושי מבוסס על אבחנה זו: אורך הרשימה positiveNums  בהכרח שווה לאורך הרשימה inds (הרי ברשימת האינדקסים מותאם לכל מספר חיובי בדיוק אינדקס אחד). מכאן נובע שלשתי הרשימות יש מערכת אינדקסים שווה; בדוגמה למעלה, שבה אורכן של שתי הרשימות הוא 4, סדרת האינדקסים היא 0, 1, 2 ו-3. כיצד תובנה זו מסייעת לנו? כדי להבין את הדבר נעיין בטבלת העוקבת אחר הרצת הלולאה שיש בקוד זה –

nums = [-1, 5, 3, -2, 0, 3, 1]

positiveNums = [1, 3, 3, 5]

inds = [1, 2, 5, 6]

for i in range(len(positiveNums)):             

    nums[inds[i]] = positiveNums[i]

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

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

nums[inds[i]]

ביטוי זה ניגש, בסופו של חשבון, למספר המופיע ברשימה nums באינדקס המופיע ברשימה inds. הגישה לאינדקס הזה שברשימה inds היא לא ישירה כפי שהיה בגרסתו הקודמת של הקוד, כיוון שכבר איננו סורקים את הרשימה inds עצמה (for ind in inds). בגרסת הקוד שהטבלה עוקבת אחריו אנו מגיעים לאינדקס המבוקש ברשימה inds באמצעות משתנה הלולאה i והאופרטור [ ], ועל יסוד העובדה שסדרת האינדקסים הנסרקת בלולאה, כלומר סדרת האינדקסים של הרשימה  positiveNums, זהה לגמרי לסדרת האינדקסים של רשימת האינדקסים inds. עתה עיינו בצד הימני של הוראת ההשמה –

nums[inds[i]] = positiveNums[i]

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

נעיר כי כיוון שסדרת האינדקסים של הרשימה positiveNums זהה לרשימת האינדקסים של הרשימה inds לולאת ה-for בקוד יכולה לסרוק את האינדקסים ברשימה inds, ולכתוב את הלולאה כך – 

for i in range(len(inds)):             

    nums[inds[i]] = positiveNums[i]

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

def sortPositives(nums): 

    positiveNums = [] 

    inds = []     

    for i in range(len(nums)):         

        if nums[i] > 0: 

            inds.append(i)

            positiveNums.append(nums[i])

    positiveNums.sort() 

    for i in range(len(positiveNums)):             

        nums[inds[i]] = positiveNums[i]

    return nums

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