לדף הראשי

בעיה ג'

הוראות המופיעות בגוף של מבנה 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, 17, 55, -2, 0, 55, 9]

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

[-1, 9, 17, -2, 0, 55, 55]

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

לפתרון בקוד ראו כאן. 

פתרון מפורט

נתחיל בפירוק הבעיה. נקודת המוצא היא לפתור תת-בעיה זו: 

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

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

 

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

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

המקיימים תנאי מסיים, ואותם בלבד. 

 

 

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

nums = [-1, 17, 55, -2, 0, 55, 9]

positiveNums = [] 

for num in nums: 

    if num > 0: 

        positiveNums.append(num)

print(positiveNums)

>>>

[17, 55, 55, 9]

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

positiveNums = [num for num in nums if num > 0]

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

positiveNums.sort()

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

sortedLst = sorted(positiveNums)

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

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

nums = [-1, 17, 55, -2, 0, 55, 9]

positiveNums = [] 

for num in nums: 

    if num > 0: 

        positiveNums.append(num)

positiveNums.sort() 

print(positiveNums)

>>>

[9, 17, 55, 55]

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

המספר 9 ברשימה המספרים החיוביים ממוינת צריך להחליף את המספר שיש באינדקס 1 ברשימה הנתונה; המספר 17 ברשימת המספרים החיוביים הממוינת צריך להחליף את המספר באינדקס 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, 17, 55, -2, 0, 55, 9]))

>>>

[-1, 9, 17, -2, 0, 55, 55]

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

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

nums = [-1, 17, 55, -2, 0, 55, 9]

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 – 

[9, 17, 55, 55]

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

[1, 2, 5, 6]

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

nums[1] = 9

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

nums[2] = 17

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

for ind in inds:   

    nums[ind] = positiveNums[?]

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

[-1, 17, 55, -2, 0, 55, 9]

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

[9, 17, 55, 55]

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

[1, 2, 5, 6]

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

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

for i, ind in enumerate(inds): 

    nums[ind] = positiveNums[i]

הלולאה סורקת את המבנה שיוצרת enumerate, מבנה שיש בו זוגות לפי הרשימה inds: האיבר הראשון בזוג הוא ערך מתוך הרשימה inds, והוא מושם במשתנה i; האיבר השני בזוג הוא האינדקס שבו נמצא הערך הזה, והוא מושם במשתנה ind. עבור הרשימה inds הזאת – 

[1, 2, 5, 6]

יווצרו הזוגות הללו – 

i = 1, ind = 0

i = 2, ind = 1 

i = 5, ind = 2

i = 6, ind = 3

1, 2, 5 ו-6 הם האינדקסים שאליהם יש להכניס את המספרים מתוך הרשימה positiveNums. המספרים 0, 1, 2, 3 הם האינדקסים שבהם נמצאים המספרים הללו ברשימה positiveNums.

על בסיס הקוד הזה נכתוב אפוא את הקוד המלא של הפונקציה 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, ind in enumerate(inds): 

        nums[ind] = positiveNums[i]

    return nums

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