מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - קיץ 2024 מועד ב'
הנדסת תוכנה · סמל 97103 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), קיץ 2024 מועד ב', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: בשאלון זה שני מבחנים. עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:
מבחן ב- Python (עמוד 2)
בכל מבחן 14 שאלות.
חלק א' – 48 נקודות
שאלות 1-7: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 8-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 22 נקודות
שאלות 12-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
אין לצרף ספרים או חוברות עם פתרונות.
שאלה 1 · קליטה עד 0: מניית שליליים וממוצע חיוביים
כתבו קטע תוכנית שקולט מספרים שלמים. הקלט יסתיים כאשר ייקלט המספר 0.
על התוכנית לחשב ולהדפיס:
•את כמות המספרים השליליים שנקלטו
•את ממוצע מספרים חיוביים שנקלטו.
הערה: אם לא נקלט אף מספר חיובי יש להדפיס הודעה מתאימה.
◂ פתרון מלא לשאלה 1
פתרון
לולאת while עד קליטת 0, עם מונה לשליליים, מונה וצובר לחיוביים; בסוף מדפיסים את מונה השליליים ואת הממוצע , או הודעה אם .
הרעיון: מספר הנתונים לא ידוע מראש – הקלט נגמר כשנקלט 0 – ולכן משתמשים בלולאת `while` עם "זקיף": קולטים מספר ראשון לפני הלולאה, ובסוף כל סיבוב קולטים את המספר הבא. ה-0 עצמו לא נספר.
1. לשליליים צריך רק כמות – מונה `count_neg`.
2. לממוצע החיוביים צריך שני משתנים: צובר `sum_pos` (סכום החיוביים) ומונה `count_pos` (כמה חיוביים היו). הממוצע הוא .
3. בתוך הלולאה המספר אינו 0, ולכן הוא שלילי או חיובי – מספיק `if`/`else`.
4. אחרי הלולאה: אם `count_pos` הוא 0, חלוקה בו אסורה – לכן מדפיסים הודעה מתאימה במקום הממוצע.
count_neg = 0 # מונה המספרים השליליים
sum_pos = 0 # צובר המספרים החיוביים
count_pos = 0 # מונה המספרים החיוביים
num = int(input())
while num != 0:
if num < 0:
count_neg = count_neg + 1
else:
sum_pos = sum_pos + num
count_pos = count_pos + 1
num = int(input())
print("Negative numbers:", count_neg)
if count_pos > 0:
print("Average of positive numbers:", sum_pos / count_pos)
else:
print("No positive numbers were entered")דוגמה: עבור הקלט 5, 3-, 10, 1-, 0 יודפס: מספר השליליים 2, והממוצע . עבור הקלט 5-, 3-, 0 יודפס 2 ואחריו ההודעה שלא נקלטו מספרים חיוביים.
תשובה: קטע התוכנית שלמעלה – מונה לשליליים, מונה וצובר לחיוביים, וטיפול במקרה שאין חיוביים.
שאלה 2 · קליטת 20 מחרוזות: אורך זוגי ואות A
כתבו קטע תוכנית הקולט 20 מחרוזות.
עבור כל מחרוזת באורך זוגי יש להדפיס את התו הראשון ואת התו האחרון שלה.
כמו כן, יש למנות ולהדפיס את כמות המחרוזות אשר מתחילות או מסתיימות באות 'A'.
◂ פתרון מלא לשאלה 2
פתרון
לולאה של 20 סיבובים: אם `len(s) % 2 == 0` מדפיסים `s[0]` ו-`s[-1]`; אם `s[0] == 'A' or s[-1] == 'A'` מגדילים מונה; בסוף מדפיסים את המונה.
הרעיון: מספר המחרוזות ידוע (20), ולכן לולאת `for`. כל מחרוזת עוברת שתי בדיקות בלתי תלויות, ולכן שני `if` נפרדים (מחרוזת יכולה גם להיות באורך זוגי וגם להתחיל ב-'A'):
1. אורך זוגי: `len(s) % 2 == 0` – מדפיסים את התו הראשון `s[0]` ואת התו האחרון `s[-1]`.
2. מתחילה או מסתיימת ב-'A': `s[0] == 'A' or s[-1] == 'A'` – מגדילים את המונה `count_a` ב-1. משתמשים ב-`or`, כי מספיק שאחד מהתנאים יתקיים (מחרוזת כמו "ABBA" נספרת פעם אחת בלבד).
מחרוזת ריקה היא באורך 0 (זוגי) אבל אין בה תווים, ולכן בשתי הבדיקות מוסיפים את התנאי `len(s) > 0`, כדי לא לגשת ל-`s[0]` שאינו קיים.
בסוף הלולאה מדפיסים את המונה.
count_a = 0
for i in range(20):
s = input()
if len(s) > 0 and len(s) % 2 == 0:
print(s[0], s[-1])
if len(s) > 0 and (s[0] == 'A' or s[-1] == 'A'):
count_a = count_a + 1
print("Strings that start or end with 'A':", count_a)דוגמה: עבור "AB" יודפס `A B` והמונה יגדל; עבור "ABC" (אורך אי-זוגי) לא יודפסו תווים, אבל המונה יגדל; עבור "XYZW" יודפס `X W` והמונה לא ישתנה.
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · מספרים אקראיים: מניית מספרי שבע-בול
מספר "שבע-בול" הוא מספר שמתחלק ב- 7 ללא שארית שלפחות אחת מהספרות שלו היא 7.
כתבו קטע תוכנית המייצרת 365 מספרים אקראיים תלת-ספרתיים שלמים חיוביים.
על התוכנית לחשב ולהדפיס כמה מהמספרים שנוצרו הם מספרים "שבע-בול".
◂ פתרון מלא לשאלה 3
פתרון
365 הגרלות של `random.randint(100, 999)`; מונים מספר אם `num % 7 == 0` ואחת משלוש ספרותיו (מאות, עשרות, אחדות) שווה ל-7.
1. מספר תלת-ספרתי חיובי הוא מספר בין 100 ל-999, ולכן מגרילים `random.randint(100, 999)` (שני הגבולות כלולים).
2. לכל מספר מפרקים את שלוש הספרות:
•ספרת המאות: `num // 100`
•ספרת העשרות: `num // 10 % 10`
•ספרת האחדות: `num % 10`
3. המספר הוא "שבע-בול" אם שני התנאים מתקיימים יחד: הוא מתחלק ב-7 (`num % 7 == 0`) וגם לפחות אחת מהספרות היא 7 (שלוש השוואות מחוברות ב-`or`).
4. מונה `count` גדל בכל פעם שנמצא מספר כזה, ובסוף הלולאה מדפיסים אותו.
import random
count = 0
for i in range(365):
num = random.randint(100, 999)
hundreds = num // 100
tens = num // 10 % 10
units = num % 10
if num % 7 == 0 and (hundreds == 7 or tens == 7 or units == 7):
count = count + 1
print("Number of 'seven-boom' numbers:", count)דוגמה: ויש בו הספרה 7 – "שבע-בול". מתחלק ב-7 אבל אין בו 7 – לא. מכיל 7 אבל – לא.
תשובה: קטע התוכנית שלמעלה.
שאלה 4 · רשימה משולשת: חלוקה לשלישים וסכומים
רשימה של מספרים שלמים נקראת "משולשת" אם היא עונה על שלושה תנאים:
•מספר איברי הרשימה מתחלק בשלוש ללא שארית
•סכום ערכי האיברים הנמצאים בכל שליש מתחלק גם הוא בשלוש ללא שארית
•ברשימה יש בדיוק שלושה איברים בעלי ערך 3.
הרשימה הבאה היא "רשימה משולשת":
כתבו פעולה המקבלת רשימה של מספרים שלמים `arr`. הפעולה תחזיר ערך `True`, אם הרשימה היא "רשימה משולשת", ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
`is_tripple(arr)`
◂ פתרון מלא לשאלה 4
פתרון
בודקים `len(arr) % 3 == 0`, אחר כך שסכום כל אחד משלושת השלישים (באורך `len(arr)//3`) מתחלק ב-3, ולבסוף שמספר האיברים ששווים 3 הוא בדיוק 3.
הרעיון: בודקים את שלושת התנאים לפי הסדר, ומחזירים `False` ברגע שתנאי אחד נכשל.
1. תנאי 1: אם `len(arr) % 3 != 0` – הרשימה לא משולשת. (התנאי הזה חייב להיבדק ראשון, כי רק אחריו אפשר לחלק את הרשימה לשלושה שלישים שווים.)
2. תנאי 2: אורך כל שליש הוא `third = n // 3`. השליש ה-t (עבור ) הוא התאים מ-`t*third` עד `(t+1)*third - 1`. מחשבים את סכומו, ואם הסכום אינו מתחלק ב-3 – מחזירים `False`. (ב-Python גם סכום שלילי כמו נותן `-6 % 3 == 0`, כך שהבדיקה נכונה גם לשליליים.)
3. תנאי 3: סופרים כמה איברים שווים ל-3; הרשימה משולשת רק אם המונה שווה בדיוק ל-3 (לא פחות ולא יותר).
def is_tripple(arr):
n = len(arr)
if n % 3 != 0: # תנאי 1
return False
third = n // 3
for t in range(3): # תנאי 2: שלושת השלישים
s = 0
for i in range(t * third, (t + 1) * third):
s = s + arr[i]
if s % 3 != 0:
return False
count3 = 0 # תנאי 3: בדיוק שלושה איברים שערכם 3
for x in arr:
if x == 3:
count3 = count3 + 1
return count3 == 3בדיקה על הדוגמה: 12 איברים, , כל שליש באורך 4:
•שליש ראשון: , מתחלק ב-3.
•שליש שני: , מתחלק ב-3.
•שליש שלישי: , מתחלק ב-3.
•הערך 3 מופיע בתאים 1, 5, 6 – בדיוק שלוש פעמים.
לכן הפעולה מחזירה `True`.
סיבוכיות: מעבר אחד על השלישים ומעבר אחד לספירת ה-3 – .
תשובה: הפעולה `is_tripple` שלמעלה.
שאלה 5 · איבר נפילה ברשימה ומניית נפילות
איבר ברשימה נקרא "נפילה" אם ערכו קטן מערכים של שני שכניו.
כתבו פעולה המקבלת רשימה של מספרים שלמים ומספר שלם המציין אינדקס (מיקום) ברשימה. הפעולה תבדוק אם איבר שנמצא במקום הנתון הוא "נפילה". אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
`is_fall(arr, index)`
כתבו פעולה המקבלת רשימה של מספרים שלמים ומחזירה את מספר הנפילות שיש בו.
חובה להשתמש בפעולה שכתבתם בסעיף א'.
מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 5
סעיף א
אם `index` הוא הראשון או האחרון (או מחוץ לרשימה) – `False`; אחרת מחזירים `arr[index] < arr[index-1] and arr[index] < arr[index+1]`.
1. לאיבר הראשון (`index == 0`) ולאחרון (`index == len(arr)-1`) אין שני שכנים, ולפי ההגדרה הם לא יכולים להיות נפילה – מחזירים `False`. את אותה בדיקה (`index <= 0` או `index >= len(arr)-1`) מנצלים גם כדי לא לחרוג מגבולות הרשימה.
2. אחרת יש לאיבר שני שכנים: `arr[index-1]` משמאל ו-`arr[index+1]` מימין. האיבר הוא נפילה אם הוא קטן ממש משניהם – שני תנאים מחוברים ב-`and`.
def is_fall(arr, index):
if index <= 0 or index >= len(arr) - 1:
return False # ראשון, אחרון או אינדקס מחוץ לרשימה
return arr[index] < arr[index - 1] and arr[index] < arr[index + 1]דוגמה: ברשימה `[5, 2, 7, 3, 3, 1, 4]` האיבר במקום 1 (ערך 2) קטן מ-5 ומ-7 – נפילה. האיבר במקום 3 (ערך 3) אינו קטן מהשכן 3 – לא נפילה.
תשובה: הפעולה `is_fall` שלמעלה.
סעיף ב
עוברים על כל האינדקסים ומגדילים מונה בכל פעם ש-`is_fall(arr, i)` מחזירה `True`; מחזירים את המונה.
הרעיון: עוברים בלולאה על כל המקומות ברשימה, ולכל מקום שואלים את `is_fall` מסעיף א' אם הוא נפילה; אם כן – מגדילים מונה. אין צורך לטפל בנפרד באיבר הראשון ובאחרון: `is_fall` כבר מחזירה עבורם `False`. (לפעולה לא ניתנה כותרת בשאלה, ולכן בחרנו את השם `count_falls`.)
def count_falls(arr):
count = 0
for i in range(len(arr)):
if is_fall(arr, i):
count = count + 1
return countדוגמה: עבור `[5, 2, 7, 3, 3, 1, 4]` הנפילות הן במקומות 1 (ערך 2) ו-5 (ערך 1, קטן מ-3 ומ-4), ולכן הפעולה מחזירה 2.
תשובה: הפעולה `count_falls` שלמעלה.
סעיף ג
`is_fall`: ; `count_falls`: , כאשר n אורך הרשימה.
נסמן ב-n את אורך הרשימה.
1. `is_fall` (סעיף א): מספר קבוע של השוואות (גבולות ושני שכנים), בלי לולאה, ולא תלוי ב-n – .
2. `count_falls` (סעיף ב): לולאה אחת של n סיבובים, ובכל סיבוב זימון של `is_fall` שעולה . סך הכול .
תשובה: סעיף א – ; סעיף ב – .
שאלה 6 · מעקב: חלוקת רשימה לפי ספרת האחדות
נתונה הפעולה `Mystery`. הפעולה מקבלת רשימה של מספרים שלמים חיוביים `arr` וסיפרה `k`
(k – מספר שלם בין 0 ל-9).
def mystery(arr, k):
left = 0
right = -1
while left - right < len(arr):
if arr[left]%10 < k:
left = left + 1
elif arr[right]%10 > k:
right = right - 1
else :
arr[left],arr[right] = arr[right], arr[left]
right = right - 1נתונה רשימת מספרים שלמים `arr = [128, 14, 313, 420, 17, 101]`
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `mystery(arr, 4)` ורשמו מה יהיה התוכן של הרשימה `arr` אחרי ביצוע הפעולה.
נתונה רשימת מספרים שלמים `arr = [128, 14, 313, 420, 17, 101]`
תנו דוגמה של מספר `k` כך שתוכן הרשימה הנתונה `arr` לא ישתנה אחרי זימון הפעולה
`mystery(arr, k)`
האם קיימת ספרה `k` שעבורה כל רשימה של מספרים שלמים וחיוביים `arr` לא תשתנה אחרי זימון הפעולה `mystery(arr, k)`? הסבירו את תשובתכם.
מה מבצעת הפעולה `mystery(a, k)` באופן כללי?
◂ פתרון מלא לשאלה 6
סעיף א
`arr = [101, 420, 313, 14, 17, 128]`
איך קוראים את הקוד: `left` מתקדם מתחילת הרשימה, ו-`right` הוא אינדקס שלילי שמתקדם מהסוף: `arr[-1]` הוא התא האחרון (תא 5), `arr[-2]` הוא תא 4 וכן הלאה – התא האמיתי הוא . התנאי `left - right < len(arr)` שקול ל-, כלומר הלולאה רצה כל עוד `left` נמצא משמאל לתא ש-`right` מצביע עליו.
בכל סיבוב: אם ספרת האחדות של `arr[left]` קטנה מ-4 – `left` מתקדם; אחרת, אם ספרת האחדות של `arr[right]` גדולה מ-4 – `right` זז שמאלה; אחרת מחליפים בין שני התאים ו-`right` זז שמאלה.
ספרות האחדות של האיברים: 128→8, 14→4, 313→3, 420→0, 17→7, 101→1.
תשובה: אחרי הזימון `arr = [101, 420, 313, 14, 17, 128]`.
סעיף ב
.
הרעיון: הרשימה משתנה רק בענף ה-`else` (החלפה). אם ספרת האחדות של כל האיברים קטנה מ-k, התנאי הראשון מתקיים תמיד: `left` רק מתקדם, אין אף החלפה, והלולאה נגמרת כש-`left` מגיע לתא האחרון.
ספרות האחדות ברשימה הן 8, 4, 3, 0, 7, 1 – הגדולה ביותר היא 8. לכן עבור כולן קטנות מ-k:
`left` עובר 0→1→2→3→4→5, וכשמגיע ל-5 מתקיים , לא קטן מ-6, והלולאה נעצרת בלי שינוי.
(עבור כל k אחר בין 0 ל-8 יש איבר שספרת האחדות שלו אינה קטנה מ-k, ומתבצעת החלפה ששינתה את הרשימה.)
תשובה: .
סעיף ג
לא. לכל k יש רשימה שמשתנה: עבור – `[5, 10]` הופכת ל-`[10, 5]`; עבור – `[k, 10]` הופכת ל-`[10, k]`.
הרעיון: כדי להראות שאין k כזה מספיק למצוא, לכל k, רשימה אחת שמשתנה.
1. : אף ספרה אינה קטנה מ-0, ולכן התנאי הראשון לא מתקיים לעולם. ניקח `arr = [5, 10]`: `arr[0]%10 = 5` אינו קטן מ-0; `arr[-1]%10 = 0` אינו גדול מ-0; לכן מתבצעת החלפה והרשימה הופכת ל-`[10, 5]`.
2. : ניקח `arr = [k, 10]` (שני מספרים חיוביים). `arr[0]%10 = k` אינו קטן מ-k; `arr[-1]%10 = 0` אינו גדול מ-k; לכן מתבצעת החלפה והרשימה הופכת ל-`[10, k]`.
בשני המקרים האיבר הראשון אינו "קטן מ-k" והאיבר האחרון אינו "גדול מ-k", ולכן כבר בסיבוב הראשון מתבצעת החלפה בין שני ערכים שונים – והרשימה משתנה.
תשובה: לא קיימת ספרה כזו.
סעיף ד
מסדרת את הרשימה במקום: כל המספרים שספרת האחדות שלהם קטנה מ-k עוברים לתחילת הרשימה, וכל המספרים שספרת האחדות שלהם גדולה או שווה ל-k – לסופה (הסדר בתוך כל קבוצה עלול להשתנות).
ניתוח: זו חלוקה (partition) של הרשימה לפי ספרת האחדות, בשני מצביעים:
1. `left` מתקדם מההתחלה כל עוד הוא פוגש מספרים שספרת האחדות שלהם קטנה מ-k – הם כבר במקומם (בחלק השמאלי).
2. `right` מתקדם מהסוף כל עוד הוא פוגש מספרים שספרת האחדות שלהם גדולה מ-k – הם כבר במקומם (בחלק הימני).
3. כשאף אחד מהם לא יכול להתקדם, `arr[left]` שייך לצד ימין (ספרה ) ו-`arr[right]` אינו גדול מ-k. מחליפים ביניהם; האיבר שעבר ל-`right` (ספרה ) נשאר בצד ימין, ו-`right` זז. האיבר שעבר ל-`left` ייבדק בסיבוב הבא: אם ספרתו קטנה מ-k – `left` יתקדם, ואם היא שווה ל-k – הוא יוחלף שוב ימינה.
4. הלולאה נגמרת כששני המצביעים נפגשים.
בסוף: כל המספרים שספרת האחדות שלהם קטנה מ-k נמצאים בתחילת הרשימה, ואחריהם כל המספרים שספרת האחדות שלהם גדולה או שווה ל-k. בסעיף א' (k=4): 101, 420, 313 (ספרות 1, 0, 3) ואחריהם 14, 17, 128 (ספרות 4, 7, 8).
תשובה: הפעולה מסדרת מחדש את הרשימה (במקום, בלי רשימה נוספת) כך שבתחילתה כל המספרים שספרת האחדות שלהם קטנה מ-k ובסופה כל המספרים שספרת האחדות שלהם גדולה או שווה ל-k.
שאלה 7 · מחלקת משחקים: החלפה וצירופי מתנות
החנות "Game4U" מוכרת משחקי שולחן לילדים. לשם ניהול ממוחשב של המכירות הוגדרה המחלקה `Game` ולה ארבע תכונות:
שם המשחק – `name`, מטיפוס מחרוזת, `string`
גיל מינימלי – `minAge`, מטיפוס מספר שלם, `int`
מספר שחקנים – `numPlayers`, מטיפוס מספר שלם, `int`
מחיר – `price`, מטיפוס מספר ממשי, `float`
לקוח יכול להחליף את המשחק שקנה למשחק אחר בתנאי שהגיל מינימלי של שני משחקים זהה והמחיר של משחק האחר לא גבוה מהמחיר שקנה הלקוח.
כתבו פעולה המקבלת הפניה למשחק בשם `other` (הפניה לעצם מטיפוס `Game`).
הפעולה תבדוק אם אפשר להחליף משחק `self` למשחק `other`. אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`. כותרת הפעולה:
`can_replace(self, other)`
כתבו פעולה המקבלת רשימת משחקים `arr` ומשחק `my_game` שהלקוח מעוניין להחליף.
הפעולה תמנה ותחזיר את מספר המשחקים אשר מתאימים להחלפה.
כותרת הפעולה:
`replace(arr, my_game)`
סבא וסבתא של התאומים אורי ודורון רוצים לקנות להם מתנות ליום ההולדת החמישי שלהם.
ליאור, האחות הגדולה של התאומים, ביקשה שבכל משחק יוכלו לשחק לפחות שלושה שחקנים.
כתבו פעולה המקבלת רשימת משחקים ומדפיסה את כל הצירופים האפשריים של שני משחקים שונים שעולים יחד פחות מ- 200 ₪.
כותרת הפעולה:
`gift_for_twins(arr)`
מהי סיבוכיות הפעולות שכתבתם בסעיפים ב' ו- ג' . הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
`return self.minAge == other.minAge and other.price <= self.price`
הרעיון: `self` הוא המשחק שהלקוח קנה ו-`other` הוא המשחק שהוא רוצה לקבל במקומו. שני תנאים חייבים להתקיים יחד (`and`):
1. אותו גיל מינימלי: `self.minAge == other.minAge`.
2. המחיר של `other` לא גבוה מהמחיר של `self`: `other.price <= self.price` (מחיר שווה מותר).
class Game:
def __init__(self, name, minAge, numPlayers, price):
self.name = name
self.minAge = minAge
self.numPlayers = numPlayers
self.price = price
# סעיף א
def can_replace(self, other):
return self.minAge == other.minAge and other.price <= self.price(הפעולה הבונה `__init__` נכתבה רק כדי שהמחלקה תהיה שלמה; הפעולה המבוקשת היא `can_replace`.)
דוגמה: משחק לגיל 5 במחיר 150.5 אפשר להחליף במשחק לגיל 5 במחיר 60 (`True`), אבל לא להפך (`False`), ולא במשחק לגיל 8.
תשובה: הפעולה `can_replace` שלמעלה.
סעיף ב
מונים את המשחקים `game` ברשימה (פרט ל-`my_game` עצמו) שעבורם `my_game.can_replace(game)` מחזירה `True`.
הרעיון: עוברים על כל המשחקים ברשימה, ולכל משחק `game` שואלים את הפעולה מסעיף א' אם אפשר להחליף את `my_game` אליו: `my_game.can_replace(game)`. אם כן – מגדילים מונה. המשחק `my_game` עצמו (אם הוא נמצא ברשימה) מקיים את התנאים מול עצמו, אבל "החלפה" שלו בעצמו אינה החלפה – לכן מדלגים עליו בבדיקה `game is not my_game`.
def replace(arr, my_game):
count = 0
for game in arr:
if game is not my_game and my_game.can_replace(game):
count = count + 1
return countדוגמה: אם `my_game` הוא משחק לגיל 5 במחיר 150.5, וברשימה יש משחקים לגיל 5 במחירים 60 ו-90 ומשחקים לגיל 8 – הפעולה תחזיר 2.
תשובה: הפעולה `replace` שלמעלה.
סעיף ג
לולאה מקוננת על כל הזוגות ; מדפיסים את שמות שני המשחקים אם לשניהם `minAge <= 5` ו-`numPlayers >= 3`, וגם `price` של שניהם יחד קטן מ-200.
הרעיון: מתרגמים את הסיפור לתנאים. כל אחד משני המשחקים בצירוף צריך:
1. להתאים לילדים בני 5: הגיל המינימלי שלו לכל היותר 5 (`minAge <= 5`).
2. לאפשר לפחות שלושה שחקנים (`numPlayers >= 3`).
ובנוסף, שני המשחקים יחד עולים פחות מ-200 ₪: `g1.price + g2.price < 200`.
כדי לעבור על כל הצירופים של שני משחקים שונים, כל צירוף פעם אחת, משתמשים בלולאה מקוננת שבה `j` מתחיל מ-`i + 1`: כך לא משווים משחק לעצמו, ולא מדפיסים גם (א, ב) וגם (ב, א).
def gift_for_twins(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
g1 = arr[i]
g2 = arr[j]
if (g1.minAge <= 5 and g2.minAge <= 5 and
g1.numPlayers >= 3 and g2.numPlayers >= 3 and
g1.price + g2.price < 200):
print(g1.name, "+", g2.name)דוגמה: עבור המשחקים Uno (גיל 5, 4 שחקנים, 60), Chess (גיל 8, 2 שחקנים, 120), Catan (גיל 5, 3 שחקנים, 150.5), Rummy (גיל 5, 4 שחקנים, 90), Taki (גיל 3, 6 שחקנים, 40), Monopoly (גיל 8, 6 שחקנים, 100) – Chess ו-Monopoly נפסלים בגלל הגיל, ומבין השאר מודפסים: Uno + Rummy (150), Uno + Taki (100), Catan + Taki (190.5), Rummy + Taki (130). הצירופים Uno + Catan (210.5) ו-Catan + Rummy (240.5) יקרים מדי.
תשובה: הפעולה `gift_for_twins` שלמעלה.
סעיף ד
`replace`: ; `gift_for_twins`: , כאשר n מספר המשחקים ברשימה.
נסמן ב-n את מספר המשחקים ברשימה.
1. `replace` (סעיף ב): לולאה אחת על n המשחקים, ובכל סיבוב `can_replace` מבצעת שתי השוואות – . סך הכול .
2. `gift_for_twins` (סעיף ג): לולאה מקוננת. עבור כל i הלולאה הפנימית רצה פעמים, ולכן מספר הזוגות הנבדקים הוא
ובכל זוג עבודה קבועה. לכן הסיבוכיות .
תשובה: סעיף ב – ; סעיף ג – .
שאלה 8 · סט שלם של ספרות בתת-רשימה
כתבו פעולה המקבלת מספר שלם וחיובי `num` וספרה `dig`. הפעולה תבדוק אם `dig` היא אחת מהספרות של `num`. אם כן, הפעולה תחזיר `True`, ולא – הפעולה תחזיר `False`.
כותרת הפעולה:
`exists(num, dig)`
אוסף של מספרים שלמים חיוביים נקרא "סט שלם של ספרות" אם כל הספרות בין 0 ל- 9 מופיעות בו לפחות פעם אחת.
הרשימה `arr1` היא "סט שלם של ספרות"
גם שתי תת-רשימות
הן "סט שלם של ספרות" כל אחת
הרשימה הבאה היא לא " סט שלם של ספרות " כי סיפרה 7 לא מופיעה באף אחד מאיברי הרשימה.
כתבו פעולה המקבלת רשימה של מספרים שלמים חיוביים ושני מספרים נוספים המציינים אינדקס (מיקום ברשימה). הפעולה תבדוק אם תת-רשימה (רצף תאים בין שני האינדקסים) הוא "סט שלם של ספרות". אם כן – הפעולה תחזיר ערך `True`, ולא – תחזיר ערך `False`.
כותרת הפעולה:
`is_full_set(arr, left, right)`
כתבו פעולה המקבלת רשימה של מספרים שלמים וחיוביים. הפעולה תחזיר אורך (מספר תאים) של תת-הרשימה הקטנה ביותר, שהיא "סט שלם של ספרות" (כהגדרתו בסעיף ב'). אם אין אף תת רשימה שהיא "סט שלם של ספרות", הפעולה תחזיר ערך (1-).
עבור הרשימה `arr1` (מהדוגמה בסעיף ב') הפעולה תחזיר 5, עבור הרשימה `arr2` (מהדוגמה בסעיף ב') הפעולה תחזיר (1-).
כותרת הפעולה:
`min_full_set(arr)`
◂ פתרון מלא לשאלה 8
סעיף א
מפרקים את `num` לספרות בעזרת `% 10` ו-`// 10`; אם אחת מהן שווה ל-`dig` מחזירים `True`, ואם נגמרו הספרות – `False`.
הרעיון: הדרך הרגילה לעבור על ספרות של מספר:
1. `num % 10` היא ספרת האחדות הנוכחית – משווים אותה ל-`dig`, ואם שוות מחזירים `True` מיד.
2. `num // 10` "מוחק" את ספרת האחדות, וממשיכים לספרה הבאה.
3. כש-`num` מגיע ל-0 עברנו על כל הספרות בלי למצוא את `dig` – מחזירים `False`.
כיוון ש-`num` חיובי, הלולאה עוברת על כל ספרותיו, כולל אפסים באמצע או בסוף (למשל ב-205 נבדקות 5, 0, 2).
def exists(num, dig):
while num > 0:
if num % 10 == dig:
return True
num = num // 10
return Falseדוגמה: `exists(205, 0)` מחזירה `True`; `exists(205, 7)` מחזירה `False`.
תשובה: הפעולה `exists` שלמעלה.
סעיף ב
לכל ספרה `dig` מ-0 עד 9 מחפשים תא `i` בין `left` ל-`right` (כולל) שבו `exists(arr[i], dig)`; אם יש ספרה שלא נמצאה – `False`, אחרת `True`.
הרעיון: "סט שלם" פירושו שכל אחת מעשר הספרות 0–9 מופיעה באחד המספרים לפחות. לכן הולכים לפי הספרות:
1. לולאה חיצונית על `dig` מ-0 עד 9.
2. לכל ספרה מחפשים בתת-הרשימה – התאים מ-`left` עד `right`, כולל שני הקצוות (כמו בדוגמה, שבה התת-רשימה 1–5 כוללת את התאים 1 ו-5) – מספר שהספרה מופיעה בו, בעזרת `exists` מסעיף א'. החיפוש נעצר ברגע שנמצא מספר כזה (`found`).
3. אם עבור ספרה כלשהי לא נמצא אף מספר – התת-רשימה אינה סט שלם, ומחזירים `False` מיד.
4. אם כל עשר הספרות נמצאו – מחזירים `True`.
def is_full_set(arr, left, right):
for dig in range(10):
found = False
i = left
while i <= right and not found:
if exists(arr[i], dig):
found = True
i = i + 1
if not found:
return False
return Trueבדיקה על הדוגמה: בתת-הרשימה 1–5 של `arr1` (32, 817, 14, 205, 961) מופיעות הספרות 3, 2 / 8, 1, 7 / 4 / 0, 5 / 9, 6 – כל עשר הספרות, ולכן `is_full_set(arr1, 1, 5)` מחזירה `True`. לעומת זאת `is_full_set(arr1, 2, 5)` מחזירה `False` (חסרות 3 ו-2), ו-`is_full_set(arr2, 0, 9)` מחזירה `False` (חסרה 7).
תשובה: הפעולה `is_full_set` שלמעלה.
סעיף ג
בודקים אורכים מ-1 עד `len(arr)`; לכל אורך עוברים על כל נקודות ההתחלה ובודקים עם `is_full_set`. האורך הראשון שנמצא עבורו סט שלם מוחזר; אם אין – מחזירים 1-.
הרעיון: מחפשים את האורך הקטן ביותר, ולכן בודקים את האורכים בסדר עולה: 1, 2, 3, ... . האורך הראשון שעבורו קיימת תת-רשימה שהיא סט שלם הוא בהכרח הקטן ביותר, ואפשר להחזיר אותו מיד.
1. לכל אורך `length` מ-1 עד n (אורך הרשימה), עוברים על כל נקודות ההתחלה האפשריות `left` מ-0 עד `n - length`. תת-הרשימה היא התאים מ-`left` עד `left + length - 1`.
2. לכל תת-רשימה כזו שואלים את `is_full_set` מסעיף ב'. אם התשובה `True` – מחזירים את `length`.
3. אם עברנו על כל האורכים (כולל הרשימה כולה) ולא נמצא סט שלם – מחזירים 1-.
def min_full_set(arr):
n = len(arr)
for length in range(1, n + 1):
for left in range(n - length + 1):
if is_full_set(arr, left, left + length - 1):
return length
return -1•`arr1`: אף תת-רשימה באורך 1–4 אינה מכילה את כל עשר הספרות, ובאורך 5 התת-רשימה שמתחילה בתא 1 (32, 817, 14, 205, 961) היא סט שלם – הפעולה מחזירה 5.
•`arr2`: הספרה 7 לא מופיעה באף איבר, ולכן אף תת-רשימה (גם לא הרשימה כולה) אינה סט שלם – הפעולה מחזירה 1-.
תשובה: הפעולה `min_full_set` שלמעלה.
שאלה 9 · מחלקות חולצה ומחסן: סינון ומבצע
החנות "חלץ לך חולצה" מוכרת חולצות של מותגים שונים באמצעות האינטרנט. לשם כך הוגדרו המחלקות `Shirt` ו- `Storage`.
המחלקה `Shirt` מייצגת חולצה. למחלקה ארבע התכונות הבאות:
•קוד מתנה – `code` – מטיפוס מספר שלם, `int`
•שם מותג – `brand` – מטיפוס מחרוזת, `string`
•מחיר – `price` – מטיפוס ממשי, `float`
•סוג חולצה (למי מיועדת החולצה) – `type` – מטיפוס תו, `char`.
התכונה יכולה לקבל אחת משלוש האפשרויות הבאות:
'F' – חולצות לנשים, 'M' – לגברים, 'K' – לילדים.
כתבו פעולה `set_type(self, type)`. הפעולה מעדכנת את התכונה `type` בהתאם לפרמטר.
אם הפרמטר שהפעולה מקבלת אינו תקין, העדכון לא מתבצע.
המחלקה `Storage` מייצגת את המחסן של החנות. למחלקה שתי התכונות הבאות:
•רשימת חולצות – `shirts` – רשימה של עצמים מטיפוס `Shirt`
•רשימת מותגים שהחנות מוכרת – `brands` – רשימה של מחרוזות
כתבו במחלקה `Storage` פעולה המקבלת שם מותג וסוג חולצה. הפעולה תחזיר רשימת חולצות של אותו מותג וסוג.
כותרת הפעולה:
`shirts_by_brand(self, brand, type)`
אם בחנות אין חולצות מתאימות, הפעולה תחזיר רשימה ריקה.
החנות רוצה להכריז על מבצע המיועד למשפחות: כל מי שמזמין שתי חולצות של אותו מותג (אחת לנשים ואחרת לגברים), יכול לקבל חולצה לילד (של אותו המותג) במתנה.
כתבו במחלקה `Storage` פעולה המדפיסה שמות של כל המותגים אשר יוכלו להשתתף במבצע.
כותרת הפעולה:
`print_names(self)`
מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיפים ב' ו- ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
`if type == 'F' or type == 'M' or type == 'K': self.type = type`
הרעיון: ערך תקין הוא אחד משלושת התווים 'F', 'M', 'K'. בודקים את הפרמטר מול שלושתם (`or`); רק אם הוא אחד מהם מעדכנים את התכונה, ואחרת לא עושים דבר (התכונה שומרת על ערכה הקודם).
class Shirt:
def __init__(self, code, brand, price, type):
self.code = code
self.brand = brand
self.price = price
self.type = type
# סעיף א
def set_type(self, type):
if type == 'F' or type == 'M' or type == 'K':
self.type = typeדוגמה: אם לחולצה `type = 'F'`, הזימון `set_type('X')` לא משנה אותה, והזימון `set_type('K')` משנה אותה ל-'K'.
תשובה: הפעולה `set_type` שלמעלה.
סעיף ב
יוצרים רשימה ריקה `res`, עוברים על `self.shirts` ומוסיפים כל חולצה שבה `shirt.brand == brand and shirt.type == type`; מחזירים את `res`.
הרעיון: סינון של רשימת החולצות:
1. מתחילים מרשימה ריקה `res` – כך, אם לא תימצא אף חולצה מתאימה, תוחזר רשימה ריקה כנדרש.
2. עוברים על כל החולצות במחסן (`self.shirts`), ולכל חולצה בודקים ששני התנאים מתקיימים: המותג שלה הוא `brand` וגם הסוג שלה הוא `type`.
3. חולצה מתאימה מוסיפים ל-`res` (את העצם עצמו), ובסוף מחזירים את `res`.
class Storage:
def __init__(self, shirts, brands):
self.shirts = shirts
self.brands = brands
def shirts_by_brand(self, brand, type):
res = []
for shirt in self.shirts:
if shirt.brand == brand and shirt.type == type:
res.append(shirt)
return resדוגמה: אם במחסן יש חולצות Nike מסוגים 'F', 'M', 'K' ושתי חולצות Zara, הזימון `shirts_by_brand("Nike", 'M')` מחזיר רשימה עם חולצת ה-Nike לגברים, והזימון `shirts_by_brand("Adidas", 'F')` מחזיר `[]`.
תשובה: הפעולה `shirts_by_brand` שלמעלה.
סעיף ג
לכל מותג ב-`self.brands` מדפיסים את שמו אם `shirts_by_brand` מחזירה רשימה לא ריקה עבור כל אחד מהסוגים 'F', 'M' ו-'K'.
הרעיון: מותג יכול להשתתף במבצע רק אם יש במחסן חולצות שלו משלושת הסוגים: לנשים ('F') ולגברים ('M') – שאותן המשפחה מזמינה – ולילדים ('K') – שאותה החנות נותנת במתנה.
1. עוברים על כל המותגים ברשימה `self.brands`.
2. לכל מותג מזמנים את `shirts_by_brand` מסעיף ב' שלוש פעמים, פעם לכל סוג, ובודקים שאף אחת מהרשימות אינה ריקה (שלושה תנאים מחוברים ב-`and`).
3. אם שלושת התנאים מתקיימים – מדפיסים את שם המותג.
class Storage:
# ... (שאר התכונות והפעולות של המחלקה)
def print_names(self):
for brand in self.brands:
if (len(self.shirts_by_brand(brand, 'F')) > 0 and
len(self.shirts_by_brand(brand, 'M')) > 0 and
len(self.shirts_by_brand(brand, 'K')) > 0):
print(brand)דוגמה: אם ל-Nike יש חולצות מכל שלושת הסוגים, ל-Zara רק לנשים ולגברים, ול-Gap מכל שלושת הסוגים – יודפסו Nike ו-Gap.
תשובה: הפעולה `print_names` שלמעלה.
סעיף ד
`shirts_by_brand`: ; `print_names`: , כאשר n מספר החולצות ו-m מספר המותגים.
נסמן ב-n את מספר החולצות במחסן (אורך `shirts`) וב-m את מספר המותגים (אורך `brands`).
1. `shirts_by_brand` (סעיף ב): מעבר אחד על n החולצות, ובכל חולצה שתי השוואות והוספה לרשימה – . סך הכול .
2. `print_names` (סעיף ג): לולאה על m המותגים, ולכל מותג לכל היותר שלושה זימונים של `shirts_by_brand`, כל אחד : .
תשובה: סעיף ב – ; סעיף ג – .
שאלה 10 · מעקב ושיפור יעילות: השוואת שתי רשימות
נתונה הפעולה `what` המקבלת שתי רשימות של מספרים שלמים:
def what(arr1, arr2):
for x in range(len(arr1)):
for k in range(len(arr2)):
if arr1[x] >= arr2[k]:
return True # (*)
return False # (**)עקבו בעזרת טבלת מעקב אחר ביצוע הפעולה `what` עבור הפרמטרים הבאים:
`arr1 = [4,6,2,7]`
`arr2 = [8,7,9]`
מה מבצעת הפעולה `what` באופן כללי?
מהי סיבוכיות הפעולה `what`? הסבירו את תשובתכם.
כתבו פעולה חדשה, יעילה יותר, אשר מבצעת אותה מטלה כמו הפעולה `what`.
מהי סיבוכיות הפעולה החדשה? הסבירו את תשובתכם.
בפעולה `what` נעשו שני שינוים:
•הפקודה `(*)` הוחלפה ל- `return False`
•הפקודה `()` הוחלפה ל- `return True`
מה מבצעת הפעולה `what` באופן כללי אחרי השינוי?
◂ פתרון מלא לשאלה 10
סעיף א
הפעולה מחזירה `True` (בזוג `x = 3, k = 1`: ).
הלולאה החיצונית עוברת על התאים של `arr1`, והפנימית משווה כל אחד מהם לכל איברי `arr2`. ברגע שנמצא זוג שבו האיבר מ-`arr1` גדול או שווה לאיבר מ-`arr2` – הפעולה מחזירה `True` ונעצרת.
תשובה: הפעולה מחזירה `True`.
סעיף ב
מחזירה `True` אם יש איבר ב-`arr1` שגדול או שווה לאיבר כלשהו ב-`arr2` (כלומר המקסימום של `arr1` גדול או שווה למינימום של `arr2`), ואחרת `False`.
הפעולה בודקת את כל הזוגות (איבר מ-`arr1`, איבר מ-`arr2`), ומחזירה `True` ברגע שנמצא זוג שבו האיבר מ-`arr1` גדול או שווה לאיבר מ-`arr2`. אם אין זוג כזה – מחזירה `False`.
ניסוח שקול: זוג כזה קיים בדיוק כשהאיבר הגדול ביותר ב-`arr1` גדול או שווה לאיבר הקטן ביותר ב-`arr2`. (אם אחת הרשימות ריקה – מוחזר `False`.)
תשובה: הפעולה מחזירה `True` אם קיים איבר ב-`arr1` שגדול או שווה לאיבר כלשהו ב-`arr2` (), ואחרת `False`.
סעיף ג
, כאשר n ו-m אורכי `arr1` ו-`arr2`.
נסמן ב-n את אורך `arr1` וב-m את אורך `arr2`. במקרה הגרוע (כשאין זוג מתאים והפעולה מחזירה `False`) הלולאה החיצונית רצה n פעמים, ובכל אחת הפנימית רצה m פעמים עם השוואה אחת – השוואות.
תשובה: .
סעיף ד
מוצאים את המקסימום של `arr1` ואת המינימום של `arr2` (כל אחד במעבר אחד) ומחזירים `max1 >= min2` (ו-`False` אם אחת הרשימות ריקה).
הרעיון: לפי סעיף ב', אין צורך לבדוק את כל הזוגות: אם יש זוג שבו , אז בוודאי ; ולהפך, אם אז הזוג (המקסימום, המינימום) עצמו מתאים. לכן:
1. אם אחת הרשימות ריקה – אין אף זוג, ו-`what` המקורית מחזירה `False`; גם החדשה מחזירה `False`.
2. מוצאים את האיבר הגדול ביותר ב-`arr1` במעבר אחד.
3. מוצאים את האיבר הקטן ביותר ב-`arr2` במעבר אחד.
4. מחזירים את תוצאת ההשוואה `max1 >= min2`.
def what2(arr1, arr2):
if len(arr1) == 0 or len(arr2) == 0:
return False
max1 = arr1[0]
for x in arr1:
if x > max1:
max1 = x
min2 = arr2[0]
for y in arr2:
if y < min2:
min2 = y
return max1 >= min2בדיקה על הנתונים מסעיף א': , , ו- – מוחזר `True`, כמו ב-`what`.
תשובה: הפעולה `what2` שלמעלה.
סעיף ה
.
הפעולה החדשה עוברת פעם אחת על `arr1` (n איברים) ופעם אחת על `arr2` (m איברים), בלולאות נפרדות ולא מקוננות, ובכל צעד עבודה קבועה: .
תשובה: .
סעיף ו
מחזירה `True` אם כל איבר ב-`arr1` קטן מכל איבר ב-`arr2` (כלומר ), ואחרת `False`.
אחרי השינוי, ברגע שנמצא זוג שבו הפעולה מחזירה `False`; רק אם אין אף זוג כזה – כלומר לכל x ולכל k מתקיים – הפעולה מגיעה לסוף ומחזירה `True`. זו בדיוק השלילה של הפעולה המקורית.
לדוגמה, עבור הנתונים מסעיף א' תוחזר עכשיו `False` (בגלל ), ועבור `arr1 = [1, 2]`, `arr2 = [3, 4]` תוחזר `True`.
תשובה: הפעולה מחזירה `True` אם כל האיברים ב-`arr1` קטנים מכל האיברים ב-`arr2` (המקסימום של `arr1` קטן מהמינימום של `arr2`), ואחרת `False`.
שאלה 11 · מעקב: מחיקת מופעים של תו ממחרוזת
נתונות הפעולות הבאות:
הפעולה `one` מקבלת מחרוזת `s`, תו `ch` ומספר שלם `k`:
def one(s, ch, k):
res = ""
while k>0 and len(s)>0:
if(s[0] == ch):
k = k-1
else:
res = res + s[0]
s=s[1:]
return res + sהפעולה `two` מקבלת רשימת מחרוזות `arr` ותו `ch`:
def two(arr, ch):
for x in range(1, len(arr),2):
print(arr[x],arr[x-1], one(arr[x-1],ch, x))
if arr[x] !=one(arr[x-1],ch, x):
return False
return Trueמה תהיה תוצאת הזימון `one(s1, 'A', 2)` עבור מחרוזת `s1="AABBAAD"`? יש להראות מעקב!
מה תהיה תוצאת הזימון `one(s1, 'F', 3)` עבור מחרוזת `s1="AABBAAD"`?
נתונה מחרוזת `s2="AABCCDDC"`. תנו דוגמה לפרמטרים `k` ו-`ch` כך שתוצאת הזימון `one(s2, ch, k)` תהיה מחרוזת `s3="AABDDC"`.
מה מבצעת הפעולה `one`?
תנו דוגמה לרשימה `arr` של שמונה מחרוזות שונות זו מזו, שעבורה זימון הפעולה `two(arr,'Z')` יחזיר `True`.
◂ פתרון מלא לשאלה 11
סעיף א
`"BBAAD"`
בכל סיבוב בודקים את התו הראשון של `s`: אם הוא שווה ל-`ch` – מקטינים את k (התו "נמחק", לא נכנס ל-`res`); אחרת מוסיפים אותו ל-`res`. בשני המקרים מורידים אותו מ-`s` (`s=s[1:]`). הלולאה נעצרת כש-k מגיע ל-0 או ש-`s` מתרוקנת, ואז מוחזר `res + s`.
מוחזר = "" + "BBAAD".
תשובה: `"BBAAD"`.
סעיף ב
`"AABBAAD"` (המחרוזת לא משתנה).
התו 'F' אינו מופיע במחרוזת, ולכן k נשאר 3 לאורך כל הלולאה, וכל התווים עוברים אחד-אחד ל-`res`. הלולאה נעצרת כש-`s` מתרוקנת:
מוחזר = "AABBAAD" + "".
תשובה: `"AABBAAD"`.
סעיף ג
`ch = 'C'`, `k = 2`.
משווים את המחרוזות: "AABCCDDC" לעומת "AABDDC" – חסרים שני תווי 'C' שבמקומות 3 ו-4, וה-'C' האחרון נשאר. לפי סעיף ד', `one` מוחקת את k המופעים הראשונים של `ch`, ולכן צריך `ch = 'C'` ו-:
- 'A', 'A', 'B' עוברים ל-`res` → "AAB".
- 'C' נמחק (k=1), 'C' נמחק (k=0) – הלולאה נעצרת, ו-`s` = "DDC".
•מוחזר "AAB" + "DDC" = "AABDDC".
(עם היה נמחק רק 'C' אחד, ועם היו נמחקים כל שלושת ה-'C'.)
תשובה: `ch = 'C'`, `k = 2`.
סעיף ד
מחזירה את המחרוזת `s` בלי k המופעים הראשונים של התו `ch` (אם יש פחות מ-k מופעים – בלי כולם); שאר התווים בסדרם המקורי.
הפעולה עוברת על המחרוזת משמאל לימין. כל מופע של `ch` מדולג (ו-k קטן ב-1), וכל תו אחר מועתק ל-`res`. כש-k מגיע ל-0, הלולאה נעצרת ושארית המחרוזת מצורפת כמו שהיא – כלומר מופעים נוספים של `ch` כבר לא נמחקים. אם המחרוזת נגמרת לפני ש-k מגיע ל-0, נמחקו כל המופעים של `ch`.
תשובה: הפעולה מחזירה מחרוזת חדשה שהיא `s` אחרי מחיקת k המופעים הראשונים של התו `ch` (או כל המופעים, אם יש פחות מ-k).
סעיף ה
למשל `arr = ["ZA", "A", "ZZZB", "B", "ZC", "C", "DZ", "D"]`.
ניתוח של `two`: הלולאה עוברת על האינדקסים האי-זוגיים . לכל x היא משווה את `arr[x]` לתוצאה של `one(arr[x-1], 'Z', x)` – כלומר ל-`arr[x-1]` אחרי מחיקת x המופעים הראשונים של 'Z'. אם יש אי-התאמה – מוחזר `False`; אם כל ארבעת הזוגות מתאימים – `True`.
לכן צריך שכל מחרוזת במקום אי-זוגי תהיה המחרוזת שלפניה בלי (עד) x ה-'Z' הראשונים שלה. כדי שכל המחרוזות יהיו שונות, המחרוזת במקום הזוגי חייבת להכיל 'Z' (אחרת `one` מחזירה אותה בלי שינוי, ואז `arr[x]` יהיה זהה ל-`arr[x-1]`). נבחר מחרוזות שבהן מספר ה-'Z' אינו גדול מ-x, כך שכולם נמחקים:
כל ארבע ההשוואות מתאימות, ולכן `two(arr, 'Z')` מחזירה `True`. כל שמונה המחרוזות שונות זו מזו. (במהלך הריצה מודפסות השורות `A ZA A`, `B ZZZB B`, `C ZC C`, `D DZ D`.)
תשובה: `arr = ["ZA", "A", "ZZZB", "B", "ZC", "C", "DZ", "D"]`.
שאלה 12 · זוג מתאים: ערכי קיצון בעמודות
רשימת מספרים `arr` ו- `mat` המוגדרת כרשימת רשימות של מספרים (רשימה שכל איבר בה הוא רשימה) הללו מוגדרים "זוג מתאים" אם מתקיימים התנאים הבאים:
•אורך של כל איבר ברשימה `mat` שווה לאורך הרשימה `arr`.
•כל איבר `arr[k]` הוא ערך קיצון (הכי גדול או הכי קטן) בין הערכים הנמצאים במקום k בכל אחת מהרשימות של `mat`.
שתי רשימות `arr` ו-`mat` הבאות הן "זוג מתאים"
כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים `mat`, מספר שלם k וערך שלם `value`. הפעולה תבדוק אם ערך `value` הוא ערך "קיצון" (הכי גדול או הכי קטן) בין הערכים הנמצאים במקום k בכל אחת מהרשימות של `mat`.
אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
`is_extreme (mat, k, value)`
כתבו פעולה המקבלת רשימת רשימות `mat` ורשימה של מספרים שלמים `arr`. הפעולה תבדוק אם הרשימות הן "זוג מתאים". אם כן – הפעולה תחזיר `True`,
ולא – הפעולה תחזיר `False`.
כותרת הפעולה:
`is_pair (mat, arr)`
מהי הסיבוכיות של הפעולה `is_pair`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 12
סעיף א
מחשבים את המקסימום והמינימום של `row[k]` על כל השורות `row` ב-`mat`, ומחזירים `value == max_val or value == min_val`.
הרעיון: "הערכים הנמצאים במקום k בכל אחת מהרשימות" הם העמודה k: `mat[0][k], mat[1][k], ...`. ערך הוא ערך קיצון אם הוא שווה לגדול ביותר או לקטן ביותר מביניהם.
1. מאתחלים את `max_val` ואת `min_val` לערך בשורה הראשונה, `mat[0][k]` (מניחים ש-`mat` אינה ריקה).
2. עוברים על כל השורות ומעדכנים את המקסימום והמינימום של `row[k]`.
3. מחזירים `True` אם `value` שווה לאחד מהם (`or`).
def is_extreme(mat, k, value):
max_val = mat[0][k]
min_val = mat[0][k]
for row in mat:
if row[k] > max_val:
max_val = row[k]
if row[k] < min_val:
min_val = row[k]
return value == max_val or value == min_valבדיקה על הדוגמה: בעמודה 0 הערכים הם 31, 4, 11, 19, 12, 7 – המקסימום 31 והמינימום 4. לכן `is_extreme(mat, 0, 4)` ו-`is_extreme(mat, 0, 31)` מחזירות `True`, ו-`is_extreme(mat, 0, 11)` מחזירה `False`.
תשובה: הפעולה `is_extreme` שלמעלה.
סעיף ב
בודקים שכל שורה ב-`mat` באורך `len(arr)`, ואחר כך שלכל k מתקיים `is_extreme(mat, k, arr[k])`; אם אחת הבדיקות נכשלת – `False`, אחרת `True`.
הרעיון: בודקים את שני התנאים של ההגדרה לפי הסדר:
1. תנאי 1: עוברים על כל השורות של `mat`; אם יש שורה שאורכה שונה מ-`len(arr)` – מחזירים `False`. (חשוב לבדוק את התנאי הזה קודם, כי רק אז בטוח לגשת ל-`row[k]` לכל k.) אם `mat` ריקה אין עמודות להשוות אליהן, ומחזירים `False`.
2. תנאי 2: לכל מקום k ב-`arr` משתמשים בפעולה מסעיף א': אם `arr[k]` אינו ערך קיצון בעמודה k – מחזירים `False`.
3. אם שני התנאים התקיימו – מחזירים `True`.
def is_pair(mat, arr):
if len(mat) == 0:
return False
for row in mat: # תנאי 1: אורך כל שורה
if len(row) != len(arr):
return False
for k in range(len(arr)): # תנאי 2: כל arr[k] ערך קיצון בעמודה k
if not is_extreme(mat, k, arr[k]):
return False
return Trueבדיקה על הדוגמה: כל השורות באורך 4. עמודה 0: מינימום 4 = `arr[0]`; עמודה 1 (8, 12, 6, 1, 2, 1): מקסימום 12 = `arr[1]`; עמודה 2 (10, 10, 4, 4, 15, 7): מקסימום 15 = `arr[2]`; עמודה 3 (12, 27, 14, 100, 15, 7): מינימום 7 = `arr[3]`. לכן מוחזר `True`.
תשובה: הפעולה `is_pair` שלמעלה.
סעיף ג
, כאשר r מספר הרשימות ב-`mat` ו-c אורך `arr`.
נסמן ב-r את מספר הרשימות (השורות) ב-`mat` וב-c את אורך `arr`.
1. בדיקת האורכים: מעבר אחד על r השורות – .
2. לולאה על c המקומות, ובכל אחד זימון של `is_extreme` שעוברת על r השורות – .
סך הכול – כלומר לינארי במספר האיברים ב-`mat`.
תשובה: .
שאלה 13 · מחלקות נכס ועירייה: ארנונה והנחות
בעיריית דימונה קיימת מערכת ממוחשבת לגביית מיסוי עירוני (ארנונה). במערכת הוגדרה המחלקה `Property` (נכס) ולה התכונות הבאות:
•מספר הנכס – `num`, מטיפוס מחרוזת, `string`
•מספר תעודת הזהות של המשלם – `id`, מטיפוס מחרוזת, `string`
•כתובת הנכס – `address`, מטיפוס מחרוזת, `string`
•שטח הנכס – `area`, מטיפוס מספר ממשי, `float`
•זכאות להנחה – `discount`, מספר שלם בין 0 ל- 3, כאשר:
0 – מציין שאין הנחה, תשלום מלא,
1 – תשלום מופחת, הנחה של 10%,
2 – הנחה של 50%,
3 – פטור מלא מתשלומי ארנונה
במחלקה הוגדרה פעולה פנימית `account(self)` המחזירה סכום חשבון מלא של ארנונה.
כתבו פעולה פנימית לחישוב סכום לתשלום בהתאם לזכאות להנחה של הנכס.
כותרת הפעולה:
`real_account(self)`
המחלקה `CityData` מאחסנת נתונים של כל הנכסים בעיר.
למחלקה תכונה אחת – רשימה `arr`, רשימה של עצמים מסוג `Property`.
כתבו במחלקה `CityData` פעולה לחישוב סכום כולל של כל ההנחות בתשלומי הארנונה.
כותרת הפעולה:
`total_discount(self)`
תושבי העיר רשאים להגיש בקשה לעדכון רמת הזכאות להנחה. מדי פעם, העירייה אוספת את כל הבקשות לעדכון ומטפלת בהן. לפי החוק העירוני, תושב העיר יכול לקבל הנחה אם מתקיימים התנאים הבאים:
•יש בבעלותו רק נכס אחד
•רמת הזכאות של נכס נמוכה מרמת הזכאות המבוקשת
כתבו פעולה במחלקה `CityData` המקבלת רשימה של תעודות זהות `ids` השייכות למגישי בקשה לעדכון (הנחה), ורמת הזכאות המבוקשת `level`. הפעולה תבדוק אם יש מקום לעדכון. אם כן – הפעולה תבצע את העדכון, ולא – הפעולה תדפיס אחת משלוש ההודעות הבאות:
- "תעודת הזהות אינה ברשימת משלמי ארנונה"
- "יש יותר מנכס אחד בבעלותו"
- "רמת הזכאות המבוקשת נמוכה מנוכחית"
כותרת הפעולה:
`print_decision(self, ids, level)`
◂ פתרון מלא לשאלה 13
סעיף א
`full = self.account()`; לפי `discount`: 0 → `full`, 1 → `full * 0.9`, 2 → `full * 0.5`, 3 → 0.
הרעיון: הסכום המלא כבר מחושב בפעולה הקיימת `account`, ולכן מזמנים אותה ומפעילים עליה את ההנחה לפי רמת הזכאות:
1. רמה 0 – אין הנחה: משלמים 100% מהסכום.
2. רמה 1 – הנחה של 10%: משלמים 90%, כלומר `full * 0.9`.
3. רמה 2 – הנחה של 50%: משלמים 50%, כלומר `full * 0.5`.
4. רמה 3 – פטור מלא: משלמים 0.
class Property:
# ... (שאר התכונות והפעולות של המחלקה)
def real_account(self):
full = self.account()
if self.discount == 1:
return full * 0.9
if self.discount == 2:
return full * 0.5
if self.discount == 3:
return 0
return fullדוגמה: אם `account()` מחזירה 4000, אז לפי הרמות 0, 1, 2, 3 יוחזרו 4000, , ו-0.
תשובה: הפעולה `real_account` שלמעלה.
סעיף ב
סוכמים על כל הנכסים את ההפרש `p.account() - p.real_account()` ומחזירים את הסכום.
הרעיון: ההנחה שנכס מקבל היא ההפרש בין הסכום המלא לסכום שמשלמים בפועל: `p.account() - p.real_account()` (בנכס בלי הנחה ההפרש הוא 0). עוברים על כל הנכסים ברשימה `self.arr` וצוברים את ההפרשים.
class CityData:
def __init__(self, arr):
self.arr = arr
def total_discount(self):
total = 0
for p in self.arr:
total = total + (p.account() - p.real_account())
return totalדוגמה: שני נכסים עם חשבון מלא של 4000 כל אחד, אחד ברמה 1 ואחד ברמה 2: ההנחות הן ו-, ובסך הכול 2400.
תשובה: הפעולה `total_discount` שלמעלה.
סעיף ג
לכל `id` ב-`ids` סופרים את הנכסים שלו: 0 – הודעה ראשונה; יותר מ-1 – הודעה שנייה; נכס יחיד עם `discount >= level` – הודעה שלישית; אחרת `discount = level`.
הרעיון: מטפלים בכל בקשה (כל תעודת זהות ברשימה `ids`) בנפרד:
1. עוברים על כל הנכסים בעיר וסופרים כמה נכסים רשומים על תעודת הזהות הזו (`count`), ושומרים הפניה לנכס שנמצא (`prop`).
2. אם `count == 0` – התושב לא משלם ארנונה בכלל: מדפיסים את ההודעה הראשונה.
3. אם `count > 1` – יש לו יותר מנכס אחד, התנאי הראשון לא מתקיים: מדפיסים את ההודעה השנייה.
4. אחרת יש נכס אחד בדיוק, `prop`. אם רמת הזכאות הנוכחית שלו אינה נמוכה מהמבוקשת (`prop.discount >= level`) – התנאי השני לא מתקיים: מדפיסים את ההודעה השלישית. (גם כשהרמות שוות אין מה לעדכן, והודעה זו היא המתאימה מבין השלוש.)
5. אחרת שני התנאים מתקיימים – מעדכנים: `prop.discount = level`.
class CityData:
# ... (שאר התכונות והפעולות של המחלקה)
def print_decision(self, ids, level):
for id in ids:
count = 0
prop = None
for p in self.arr:
if p.id == id:
count = count + 1
prop = p
if count == 0:
print("תעודת הזהות אינה ברשימת משלמי ארנונה")
elif count > 1:
print("יש יותר מנכס אחד בבעלותו")
elif prop.discount >= level:
print("רמת הזכאות המבוקשת נמוכה מנוכחית")
else:
prop.discount = levelדוגמה: אם התושב 111 בעל נכס יחיד ברמה 0, התושב 333 בעל שני נכסים והתושב 444 בעל נכס יחיד ברמה 3, אז עבור `ids = ["111", "999", "333", "444"]` ו-`level = 2`: הנכס של 111 מתעדכן לרמה 2; עבור 999 מודפס "תעודת הזהות אינה ברשימת משלמי ארנונה"; עבור 333 – "יש יותר מנכס אחד בבעלותו"; עבור 444 – "רמת הזכאות המבוקשת נמוכה מנוכחית".
תשובה: הפעולה `print_decision` שלמעלה.
שאלה 14 · רקורסיה: מספר מחלקים ובחירה בין קצוות
נתונה הפעולה `secret` הבאה המקבלת מספר שלם גדול מ- 0:
def secret(n):
return real_secret(n, 1)
def real_secret(n, k):
if k == n:
return 1
if n % k == 0:
return 1 + real_secret(n, k+1)
return real_secret(n, k+1)עקבו אחרי הזימונים הבאים של הפעולה `secret` ורשמו מה תהיה התוצאה של כל זימון:
`secret(12)`
`secret(7)`
`secret(15)`
מה מבצעת הפעולה `secret(n)` עבור מספר שלם גדול מ- 0?
נתונה הפעולה `sod` המקבלת רשימה של מספרים שלמים גדולים מ- 0:
def sod(arr):
return real_sod(arr, 0, len(arr)-1)
def real_sod(arr, i, j):
if(i == j):
return arr[i]
if secret(arr[i]) < secret(arr[j]):
j = j - 1
else:
i = i + 1
return real_sod(arr, i, j)עקבו אחרי זימון הפעולה `sod(arr)` עבור הרשימה הבאה:
`arr = [4,6,12,17,24,15,10]`
ורשמו מה תהיה התוצאה של הזימון. יש להראות מעקב!
מה מבצעת הפעולה `sod` עבור רשימה של מספרים שלמים גדולים מ- 0?
◂ פתרון מלא לשאלה 14
סעיף א
6
`secret(12)` מזמנת את `real_secret(12, 1)`. בכל זימון k גדל ב-1: אם k מחלק את 12 מוסיפים 1, אחרת לא מוסיפים; כש-k מגיע ל-12 מוחזר 1.
סכום התרומות: .
תשובה: 6.
2
`real_secret(7, 1)`: עבור – , תרומה 1; עבור השארית היא 1, 1, 3, 2, 1 (שונה מ-0), אין תרומה; עבור – `k == n`, מוחזר 1.
סך הכול .
תשובה: 2.
4
`real_secret(15, 1)`: מבין רק 1, 3, 5 מחלקים את 15 (תרומה 1 כל אחד); עבור מוחזר 1.
סך הכול .
תשובה: 4.
סעיף ב
מחזירה את מספר המחלקים של n (כולל 1 ו-n).
הפעולה עוברת ברקורסיה על ומוסיפה 1 על כל k שמחלק את n ללא שארית. בתנאי העצירה היא מחזירה 1 – וזה בדיוק המחלק n עצמו (כל מספר מתחלק בעצמו). לכן התוצאה היא מספר כל המחלקים של n. (עבור : מיד `k == n` ומוחזר 1 – ל-1 מחלק אחד.)
לדוגמה: ל-12 יש 6 מחלקים (1, 2, 3, 4, 6, 12), ול-7, שהוא ראשוני, יש 2.
תשובה: הפעולה מחזירה את מספר המחלקים של n.
סעיף ג
17
קודם מחשבים לפי סעיף ב' את מספר המחלקים של כל איבר:
- 4: 1, 2, 4 → 3
- 6: 1, 2, 3, 6 → 4
- 12: 6 (סעיף א)
- 17 (ראשוני): 1, 17 → 2
- 24: 1, 2, 3, 4, 6, 8, 12, 24 → 8
- 15: 4 (סעיף א)
- 10: 1, 2, 5, 10 → 4
`sod(arr)` מזמנת את `real_sod(arr, 0, 6)`. בכל זימון: אם למספר שב-i יש פחות מחלקים מאשר למספר שב-j – מזיזים את j שמאלה (המספר שב-j "נפסל"); אחרת מזיזים את i ימינה. כש- מוחזר `arr[i]`.
תשובה: 17.
סעיף ד
מחזירה את האיבר ברשימה שיש לו הכי מעט מחלקים (אם יש כמה כאלה – הימני ביותר מביניהם).
הפעולה מחזיקה שני קצוות, i ו-j, ובכל צעד משווה את מספר המחלקים של שני האיברים שבקצוות ו"פוסלת" אחד מהם:
1. אם לאיבר שב-i יש פחות מחלקים – פוסלים את האיבר שב-j (`j = j - 1`).
2. אחרת (לאיבר שב-j מספר מחלקים קטן או שווה) – פוסלים את האיבר שב-i (`i = i + 1`).
בכל צעד נפסל האיבר שיש לו מספר מחלקים גדול או שווה לזה של האיבר שמולו, ולכן איבר שיש לו מספר מחלקים מינימלי לעולם לא נפסל כשמולו איבר עם יותר מחלקים. הפעולה נגמרת כשנשאר איבר אחד (), והוא האיבר עם מספר המחלקים הקטן ביותר. במקרה של שוויון נפסל האיבר שב-i (השמאלי), ולכן מבין כמה איברים עם אותו מספר מחלקים מינימלי נשאר הימני ביותר.
בסעיף ג': ל-17 יש 2 מחלקים – הכי מעט ברשימה – והוא מוחזר.
תשובה: הפעולה מחזירה את האיבר ברשימה שיש לו מספר המחלקים הקטן ביותר (בשוויון – הימני מביניהם); לדוגמה, אם יש ברשימה מספר ראשוני ואין בה 1 – יוחזר מספר ראשוני.