מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - קיץ 2023 מועד א'
הנדסת תוכנה · סמל 97103 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), קיץ 2023 מועד א', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: מבחן ב- Python:
חלק א' – 48 נקודות
שאלות 6-1: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 9-7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 22 נקודות
שאלות 12-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
אין לצרף ספרים או חוברות עם פתרונות.
שאלה 1 · הדפסת מספרים המתחלקים בסכום ספרותיהם
מספר שלם חיובי נקרא "מספר מושלם" אם הוא מתחלק בסכום ספרותיו.
מספר 12 הוא מספר מושלם, מספר 24 הוא מספר מושלם, מספר 25 אינו מספר מושלם.
כתבו קטע תוכנית להדפסת כל המספרים המושלמים מ- 1 עד 1,000.
◂ פתרון מלא לשאלה 1
פתרון
לולאה על 1 עד 1000; לכל מספר מחשבים את סכום ספרותיו (`% 10`, `// 10`) ומדפיסים אותו אם הוא מתחלק בסכום. יודפסו 213 מספרים: 1, 2, ..., 10, 12, 18, 20, 21, 24, ...
1. עוברים בלולאה על כל המספרים `num` מ-1 עד 1000.
2. לכל מספר מחשבים את סכום הספרות שלו: הספרה הימנית היא `temp % 10`, ואחרי שמוסיפים אותה לסכום מסירים אותה בעזרת `temp //= 10`. ממשיכים עד ש-`temp` מתאפס. עובדים על עותק `temp` כדי לא לקלקל את `num`.
3. אם `num % digits_sum == 0` המספר מתחלק בסכום ספרותיו, כלומר הוא "מספר מושלם", ומדפיסים אותו.
סכום הספרות של מספר חיובי הוא לפחות 1, ולכן אין חלוקה באפס.
בדיקה מול הדוגמאות: : סכום הספרות ו-, מושלם. : ו-, מושלם. : ו- אינו מתחלק ב-, לא מושלם.
for num in range(1, 1001):
digits_sum = 0
temp = num
while temp > 0:
digits_sum += temp % 10
temp //= 10
if num % digits_sum == 0:
print(num)סיבוכיות: לכל מספר מבצעים מספר פעולות כמספר ספרותיו (לכל היותר 4), כלומר בערך פעולות.
תשובה: הקטע מדפיס את כל המספרים המתחלקים בסכום ספרותיהם בין 1 ל-1000 (213 מספרים: 1, 2, ..., 10, 12, 18, 20, 21, 24, ...).
שאלה 2 · קליטת מחרוזות עד מספר נייד תקין
מחרוזת שמייצגת "מספר נייד תקין" היא מחרוזת העונה לשלושה תנאים:
•שלושת התווים ראשונים הם קידומת (050, 051, 052, 053, 054, 055, 056, 057, 058).
•התו הרביעי הוא מקף (-).
•שבעת התווים הבאים הם ספרות.
המחרוזת 050-1230567 היא מספר נייד תקין.
כתבו קטע תוכנית הקולטת מחרוזות עד שתקלט מחרוזת שהיא מספר נייד תקין. יש להדפיס מספר המחרוזות שנקלטו.
◂ פתרון מלא לשאלה 2
פתרון
פעולת עזר `is_valid_phone(s)` בודקת אורך 11, קידומת מהרשימה, מקף במקום 3 ו-7 ספרות; לולאת `while` קולטת ומונה מחרוזות עד שמתקבלת מחרוזת תקינה, ובסוף מודפס המונה (כולל המחרוזת התקינה).
1. נכתוב פעולת עזר `is_valid_phone(s)` שבודקת את שלושת התנאים:
•אורך המחרוזת הוא בדיוק 11 תווים (3 של קידומת, מקף ו-7 ספרות). בלי הבדיקה הזו, מחרוזת קצרה מדי תגרום לחריגה, וארוכה מדי תתקבל בטעות.
•שלושת התווים הראשונים `s[0:3]` הם אחת מהקידומות ברשימה.
•התו `s[3]` הוא מקף.
•כל אחד מהתווים `s[4:]` הוא ספרה, כלומר נמצא בין `'0'` ל-`'9'`.
כשתנאי אחד נכשל מחזירים `False` מיד; אם כולם עברו מחזירים `True`.
2. בתוכנית הראשית: מונה `count` שמתחיל ב-0. בכל סיבוב קולטים מחרוזת ומגדילים את המונה. אם המחרוזת תקינה, מסמנים `found = True` והלולאה נעצרת.
3. בסוף מדפיסים את `count`. המונה כולל גם את המחרוזת התקינה האחרונה, כי גם היא נקלטה.
def is_valid_phone(s):
prefixes = ["050", "051", "052", "053", "054", "055", "056", "057", "058"]
if len(s) != 11:
return False
if s[0:3] not in prefixes:
return False
if s[3] != '-':
return False
for ch in s[4:]:
if ch < '0' or ch > '9':
return False
return True
count = 0
found = False
while not found:
s = input()
count += 1
if is_valid_phone(s):
found = True
print(count)דוגמה: אם נקלטות המחרוזות `abc`, `059-1230567`, `050-1230567`, יודפס 3 (הקידומת 059 אינה ברשימה).
תשובה: הקוד שלמעלה: לולאה הקולטת מחרוזות ומונה אותן עד שמתקבל מספר נייד תקין, ואז מדפיסה את מספר המחרוזות שנקלטו.
שאלה 3 · רשימה מסודרת: זוגיים לפני אי-זוגיים
רשימה של מספרים שלמים נקראת "רשימה מסודרת" אם כל הערכים הזוגיים (אם יש כאלה) נמצאים בתחילת הרשימה וכל הערכים האי-זוגיים (אם יש כאלה) נמצאים אחריהם, בסוף הרשימה.
הרשימות הבאות הן רשימות "מסודרות":
lst1 = [6, 24, 12, 8, 44, 3, 7]
lst2 = [6, 24, 12, 8, 16, 22]כתבו פעולה המקבלת רשימה של מספרים שלמים `arr`.
הפעולה תחזיר ערך `True`, אם הרשימה "מסודרת" ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_ordered(arr)כתבו פעולה המקבלת שלושה פרמטרים מטיפוס מספר שלם: `size`, `x`, `y`.
הפעולה צריכה ליצור רשימה מסודרת של מספרים שלמים בגודל `size` המלאה במספרים אקראיים בין `x` ל- `y` (כולל).
כותרת הפעולה:
build_ordered(size, x, y)◂ פתרון מלא לשאלה 3
סעיף א
מדלגים על הזוגיים שבתחילת הרשימה; מהמקום הראשון שבו מופיע אי-זוגי, אם מופיע עוד זוגי - `False`, אחרת `True`. סיבוכיות .
הרעיון: ברשימה מסודרת יש "גבול" אחד: לפניו רק זוגיים ואחריו רק אי-זוגיים. לכן:
1. מתקדמים עם אינדקס `i` מתחילת הרשימה כל עוד הערך זוגי. כשנעצרים, `i` מצביע על הערך האי-זוגי הראשון (או על סוף הרשימה).
2. מהמקום הזה ועד הסוף כל הערכים חייבים להיות אי-זוגיים. אם נמצא ערך זוגי - הוא מופיע אחרי אי-זוגי, והרשימה אינה מסודרת: מחזירים `False`.
3. אם הגענו לסוף בלי למצוא זוגי כזה, מחזירים `True`.
רשימה שכולה זוגיים (כמו `lst2`), שכולה אי-זוגיים, או רשימה ריקה - כולן מסודרות, והפעולה מחזירה עבורן `True`.
def is_ordered(arr):
i = 0
# skip the even values at the start of the list
while i < len(arr) and arr[i] % 2 == 0:
i += 1
# from here on, every value must be odd
while i < len(arr):
if arr[i] % 2 == 0:
return False
i += 1
return Trueדוגמאות: עבור `lst1` הלולאה הראשונה עוצרת ב-3 (אינדקס 5), ואחריו רק 7 - מוחזר `True`. עבור `[2, 3, 4]` הלולאה הראשונה עוצרת ב-3, והלולאה השנייה מוצאת את 4 - מוחזר `False`.
סיבוכיות: כל איבר נבדק פעם אחת, .
תשובה: הפעולה `is_ordered` שלמעלה (מעבר אחד על הרשימה, ).
סעיף ב
מגרילים `size` מספרים ב-`random.randint(x, y)`; זוגיים נכנסים לרשימה `evens`, אי-זוגיים לרשימה `odds`; מחזירים `evens + odds`.
הרעיון: אם נגריל את המספרים ונכניס אותם לרשימה אחת לפי סדר ההגרלה, הרשימה כנראה לא תהיה מסודרת. במקום זה נחזיק שתי רשימות:
1. `evens` - כל המספרים הזוגיים שהוגרלו.
2. `odds` - כל המספרים האי-זוגיים שהוגרלו.
3. מגרילים `size` פעמים מספר בעזרת `random.randint(x, y)` (שמחזיר מספר בין `x` ל-`y` כולל), ומוסיפים אותו לרשימה המתאימה לפי `num % 2`.
4. בסוף מחברים: `evens + odds`. כל הזוגיים בתחילה וכל האי-זוגיים אחריהם, כלומר הרשימה מסודרת, ואורכה `size` כי כל מספר שהוגרל נכנס לאחת משתי הרשימות.
(ב-Python גם עבור מספר שלילי `num % 2` מחזיר 0 או 1, כך שהבדיקה נכונה גם אם `x` שלילי.)
import random
def build_ordered(size, x, y):
evens = []
odds = []
for i in range(size):
num = random.randint(x, y)
if num % 2 == 0:
evens.append(num)
else:
odds.append(num)
return evens + oddsתשובה: הפעולה `build_ordered` שלמעלה; הרשימה המוחזרת מסודרת, בגודל `size`, וכל ערכיה בין `x` ל-`y`.
שאלה 4 · מחלקת זמן: הפרש דקות ובדיקת משלוחים
המחלקה `Time` מייצגת נקודת זמן לפי מספר שעות ומספר דקות.
class Time:
def __init__(self, hour, minutes):
self.hour=hour
self.minutes=minutesכתבו במחלקה `Time` פעולה `difference` המקבלת הפניה לאובייקט `other` מטיפוס `Time` ומחזירה את מספר הדקות שעברו בין הזמן המיוצג על-ידי האובייקט שמפעיל את הפעולה (`this`) לזמן המיוצג באמצעות `other`. אפשר להניח ש- `this` לפני `other`.
חברת משלוחים מבטיחה ללקוחותיה שכל משלוח יגיע למען לא מאוחר משלוש שעות (180 דקות) מהרגע שהתקבל בחברה.
כתבו קטע תוכנית לבדיקה. הקטע צריך לקלוט עבור כל אחד מ- 100 משלוחים את זמני קבלתו בחברה ומסירתו לידי הלקוח. עבור כל משלוח ייקלטו ארבעה מספרים שלמים.
עבור משלוח שהתקבל בחברה ב- 10:50 ונמסר ללקוח ב- 12:20 יש לקלוט ארבעה מספרים: 10, 50, 12, 20.
קטע התוכנית יבדוק אם חברת המשלוחים קיימה את ההבטחה וידפיס הודעה מתאימה.
עליכם להיעזר בפעולה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 4
סעיף א
ממירים כל זמן לדקות מתחילת היממה (`hour*60+minutes`) ומחזירים את ההפרש: זמן `other` פחות זמן `self`.
הרעיון: קשה להחסיר זמנים ישירות (למשל 12:20 פחות 10:50 - צריך "לפרוט" שעה). לכן ממירים כל נקודת זמן למספר הדקות שעברו מתחילת היממה:
1. דקות של האובייקט המפעיל (`self`, שהוא `this` בשאלה): `self.hour * 60 + self.minutes`.
2. דקות של `other`: `other.hour * 60 + other.minutes`.
3. מאחר ש-`this` לפני `other`, ההפרש `other_total - this_total` הוא מספר חיובי (או 0), והוא מספר הדקות שעברו.
class Time:
def __init__(self, hour, minutes):
self.hour = hour
self.minutes = minutes
def difference(self, other):
this_total = self.hour * 60 + self.minutes
other_total = other.hour * 60 + other.minutes
return other_total - this_totalבדיקה: עבור 10:50 ו-12:20: , , וההפרש דקות.
תשובה: הפעולה `difference` שלמעלה מחזירה `(other.hour*60+other.minutes) - (self.hour*60+self.minutes)`.
סעיף ב
לולאה של 100 משלוחים: קולטים 4 מספרים, בונים שני עצמי `Time` ומחשבים `received.difference(delivered)`; אם משלוח כלשהו עבר 180 דקות - ההבטחה הופרה. בסוף מודפסת הודעה אחת בהתאם.
1. משתנה בוליאני `kept` מתחיל ב-`True` ("עד עכשיו ההבטחה נשמרה").
2. לכל אחד מ-100 המשלוחים קולטים ארבעה מספרים לפי הסדר שבדוגמה: שעת הקבלה, דקות הקבלה, שעת המסירה, דקות המסירה.
3. בונים שני עצמים: `received` (זמן הקבלה) ו-`delivered` (זמן המסירה). זמן הקבלה הוא לפני זמן המסירה, ולכן אפשר להפעיל את `received.difference(delivered)` מסעיף א ולקבל את משך המשלוח בדקות.
4. אם המשך גדול מ-180, המשלוח איחר, ומעדכנים `kept = False`. (משלוח של בדיוק 180 דקות עדיין עומד בהבטחה - "לא מאוחר משלוש שעות".)
5. אחרי הלולאה מדפיסים הודעה לפי `kept`. ממשיכים לקלוט את כל 100 המשלוחים גם אחרי שנמצא איחור, כי הקלט של כולם מגיע בכל מקרה.
הנחה: הקבלה והמסירה של כל משלוח באותו יום (כמו בדוגמה), כך שזמן המסירה מאוחר מזמן הקבלה.
kept = True
for i in range(100):
h1 = int(input())
m1 = int(input())
h2 = int(input())
m2 = int(input())
received = Time(h1, m1)
delivered = Time(h2, m2)
if received.difference(delivered) > 180:
kept = False
if kept:
print("The company kept its promise")
else:
print("The company did not keep its promise")בדוגמה: , המשלוח עומד בהבטחה.
תשובה: הקטע שלמעלה: 100 פעמים קולט 4 מספרים, מחשב את משך המשלוח ב-`difference`, ומדפיס בסוף אם כל המשלוחים הגיעו תוך 180 דקות לכל היותר.
שאלה 5 · מעקב: איברים זוגיים עולים, אי-זוגיים יורדים
נתונה הפעולה `what` המקבלת רשימה של מספרים שלמים באורך זוגי:
def what(a):
length = len(a)
for i in range(2,length-1,2):
if a[i]<a[i-2]:
return False
i+=1
if a[i]>a[i-2]:
return False
return Trueנתונה רשימה מספרים שלמים `a`:
a = [1, 25, 3, 8, 10, 4, 20, 5]עקבו בעזרת טבלת מעקב אחרי ביצוע הפעולה ורשמו מה תחזיר הפעולה.
תנו דוגמה לרשימה בגודל עשרה ערכים שעבורו הפעולה `what` תחזיר ערך `True`.
מה מבצעת הפעולה `what` באופן כללי?
נתונה רשימה `b` של מספרים שלמים. ידוע שתוצאת הזימון `what(b)` היא `True`.
כתבו פעולה יעילה ככל האפשר, המחזירה את הערך הגדול ביותר ברשימה `b`.
מהי סיבוכיות הפעולה שכתבתם?
◂ פתרון מלא לשאלה 5
סעיף א
הפעולה מחזירה `False` (בבדיקה `a[7]>a[5]`, כלומר `5>4`).
נתון: `a = [1, 25, 3, 8, 10, 4, 20, 5]`, ולכן `length = 8` והלולאה `range(2, 7, 2)` נותנת ל-`i` את הערכים 2, 4, 6.
שימו לב: הפקודה `i+=1` משנה את `i` רק עד סוף הסיבוב הנוכחי; בתחילת הסיבוב הבא `i` מקבל את הערך הבא מ-`range`. כך בכל סיבוב בודקים מקום זוגי `i` ומיד אחריו את המקום האי-זוגי `i+1`.
בשלב 6 התנאי `a[7]>a[5]` מתקיים (5 גדול מ-4), ולכן הפעולה מחזירה `False`.
תשובה: `what(a)` מחזירה `False`.
סעיף ב
למשל `[1, 20, 2, 18, 3, 16, 4, 14, 5, 12]`.
הפעולה מחזירה `True` אם אף אחד מהתנאים לא מתקיים, כלומר:
1. במקומות הזוגיים (0, 2, 4, 6, 8) כל ערך אינו קטן מהערך שלפניו במקום הזוגי הקודם - סדרה עולה (לא יורדת).
2. במקומות האי-זוגיים (1, 3, 5, 7, 9) כל ערך אינו גדול מהערך שלפניו במקום האי-זוגי הקודם - סדרה יורדת (לא עולה).
נבנה: במקומות הזוגיים 1, 2, 3, 4, 5 (עולה), ובמקומות האי-זוגיים 20, 18, 16, 14, 12 (יורדת):
`[1, 20, 2, 18, 3, 16, 4, 14, 5, 12]`
בדיקה: `2>=1`, `18<=20`, `3>=2`, `16<=18`, `4>=3`, `14<=16`, `5>=4`, `12<=14` - אף תנאי של `return False` לא מתקיים, והפעולה מחזירה `True`.
תשובה: `[1, 20, 2, 18, 3, 16, 4, 14, 5, 12]`.
סעיף ג
מחזירה `True` אם האיברים במקומות הזוגיים מסודרים בסדר עולה (לא יורד) והאיברים במקומות האי-זוגיים בסדר יורד (לא עולה); אחרת `False`.
בכל סיבוב, עבור מקום זוגי `i`:
1. התנאי `a[i]<a[i-2]` בודק שהאיבר במקום הזוגי אינו קטן מהאיבר הזוגי הקודם. אם הוא קטן - `False`.
2. אחרי `i+=1` התנאי `a[i]>a[i-2]` בודק שהאיבר במקום האי-זוגי אינו גדול מהאיבר האי-זוגי הקודם. אם הוא גדול - `False`.
כיוון שאורך הרשימה זוגי , הערך האחרון של `i` הוא , ואחרי ההגדלה נבדק גם המקום . לכן כל האיברים נבדקים.
תשובה: הפעולה בודקת אם האיברים שבמקומות הזוגיים מהווים סדרה עולה (לא יורדת) והאיברים שבמקומות האי-זוגיים מהווים סדרה יורדת (לא עולה). אם כן מחזירה `True`, אחרת `False`.
סעיף ד
הגדול ביותר הוא המקסימום בין `b[n-2]` (האחרון במקומות הזוגיים) ל-`b[1]` (הראשון במקומות האי-זוגיים); סיבוכיות .
הרעיון: מסעיף ג, כיוון ש-`what(b)` מחזירה `True`:
1. האיברים במקומות הזוגיים עולים, ולכן הגדול מביניהם הוא האחרון שבהם. האורך זוגי, ולכן המקום הזוגי האחרון הוא : הערך `b[n-2]`.
2. האיברים במקומות האי-זוגיים יורדים, ולכן הגדול מביניהם הוא הראשון שבהם: `b[1]`.
3. כל איבר ברשימה נמצא באחת משתי הקבוצות, ולכן הערך הגדול ביותר ברשימה הוא הגדול מבין `b[n-2]` ו-`b[1]`. אין צורך לעבור על הרשימה.
def max_value(b):
n = len(b)
if b[n - 2] > b[1]:
return b[n - 2]
return b[1]דוגמה: עבור הרשימה מסעיף ב, `b[8]=5` ו-`b[1]=20`, והפעולה מחזירה 20, שהוא אכן המקסימום.
סיבוכיות: מספר קבוע של פעולות (חישוב אורך, שתי גישות לרשימה והשוואה אחת), בלי קשר לגודל הרשימה - .
תשובה: מחזירים את הגדול מבין `b[n-2]` ו-`b[1]`; הסיבוכיות .
שאלה 6 · מעקב וניתוח פעולות על מחרוזות ורשימת מחרוזות
נתונה הפעולה `secret(s)` הבאה המקבלת מחרוזת:
def secret(s):
for i in range(0, len(s), 2):
if s[i]>='A' and s[i]<='Z':
return False
for i in range(1, len(s), 2):
if s[i]<'A' or s[i]>'Z':
return False
return Trueתנו דוגמה למחרוזת באורך של שישה תווים שעבורה הפעולה `secret` תחזיר ערך `True`.
נתונה טענה הבאה: אם זימון הפעולה `secret(str)` מחזיר ערך `True`, במחרוזת `str` אין רצף תווים זהים. האם הטענה נכונה? הסבירו את תשובתכם.
מהי סיבוכיות הפעולה? הסבירו את תשובתכם.
נתונה הפעולה `mystery(a)` המקבלת רשימת מחרוזות. הפעולה משתמשת בפעולה `secret`:
def mystery(a):
for i in range(0,len(a),2):
if secret(a[i]) == secret(a[i+1]):
return False
return Trueתנו דוגמה לרשימה `arr` בגודל שישה מחרוזות שעבורו הפעולה `mystery` תחזיר ערך `True`.
נתונה הטענה הבאה: אם זימון הפעולה `mystery(arr)` מחזיר ערך `True`, הרשימה `arr` לא כוללת זוג מחרוזות זהות אשר נמצאות במקומות סמוכים ברשימה. האם הטענה נכונה? הסבירו את תשובתכם.
מהי הסיבוכיות של הפעולה `mystery`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `"aBcDeF"`.
הלולאה הראשונה עוברת על המקומות הזוגיים (0, 2, 4) ומחזירה `False` אם יש שם אות גדולה (`'A'` עד `'Z'`). הלולאה השנייה עוברת על המקומות האי-זוגיים (1, 3, 5) ומחזירה `False` אם יש שם תו שאינו אות גדולה.
לכן צריך: במקומות הזוגיים תווים שאינם אותיות גדולות, ובמקומות האי-זוגיים אותיות גדולות.
`"aBcDeF"`: במקומות 0, 2, 4 התווים `a`, `c`, `e` (אותיות קטנות), ובמקומות 1, 3, 5 התווים `B`, `D`, `F` (אותיות גדולות). אף תנאי לא מתקיים והפעולה מחזירה `True`.
תשובה: `"aBcDeF"`.
הטענה נכונה: כל שני תווים סמוכים הם אחד במקום זוגי (לא אות גדולה) ואחד במקום אי-זוגי (אות גדולה), ולכן הם שונים.
1. כל שני תווים סמוכים במחרוזת נמצאים במקומות `j` ו-`j+1`, ולכן אחד מהם במקום זוגי והשני במקום אי-זוגי.
2. אם `secret(str)` החזירה `True`, אז התו שבמקום הזוגי אינו אות גדולה, והתו שבמקום האי-זוגי הוא אות גדולה (`'A'` עד `'Z'`).
3. תו שהוא אות גדולה ותו שאינו אות גדולה אינם יכולים להיות אותו תו. לכן כל שני תווים סמוכים שונים זה מזה, ואין במחרוזת שני תווים זהים ברצף.
תשובה: הטענה נכונה.
, כאשר אורך המחרוזת.
נסמן ב- את אורך המחרוזת.
1. הלולאה הראשונה עוברת על כ- המקומות הזוגיים, והלולאה השנייה על כ- המקומות האי-זוגיים.
2. בכל סיבוב מתבצעות השוואות בודדות - מספר קבוע של פעולות.
3. במקרה הגרוע (כשהפעולה מחזירה `True`) עוברים על כל התווים פעם אחת: בדיקות.
תשובה: הסיבוכיות לינארית, .
סעיף ב
למשל `["aB", "ab", "cD", "cd", "eF", "ef"]`.
הפעולה עוברת על זוגות: (מקום 0, מקום 1), (מקום 2, מקום 3), (מקום 4, מקום 5), ומחזירה `False` אם בזוג כלשהו לשתי המחרוזות אותה תוצאה של `secret`. לכן בכל זוג צריכה להיות מחרוזת אחת שעבורה `secret` מחזירה `True` ומחרוזת אחת שעבורה היא מחזירה `False`.
1. `secret("aB")` מחזירה `True` (במקום 0 אות קטנה, במקום 1 אות גדולה), ו-`secret("ab")` מחזירה `False` (במקום 1 אות קטנה).
2. כך גם `"cD"` (`True`) מול `"cd"` (`False`), ו-`"eF"` (`True`) מול `"ef"` (`False`).
בכל זוג התוצאות שונות, והפעולה מחזירה `True`.
תשובה: `["aB", "ab", "cD", "cd", "eF", "ef"]`.
הטענה אינה נכונה. דוגמה נגדית: `["aB", "ab", "ab", "aB"]` - הפעולה מחזירה `True`, אבל במקומות 1 ו-2 יש שתי מחרוזות `"ab"` זהות.
1. הפעולה משווה רק בין המקומות `i` ו-`i+1` כאשר `i` זוגי: (0,1), (2,3), (4,5) וכו'. בתוך זוג כזה, שתי מחרוזות זהות נותנות אותה תוצאה של `secret`, ואז הפעולה מחזירה `False`. כלומר בתוך זוג כזה הטענה מתקיימת.
2. אבל מקומות סמוכים כמו (1,2), (3,4) לא נבדקים כלל. לכן שתי מחרוזות זהות יכולות לשבת במקומות כאלה.
3. דוגמה נגדית: `arr = ["aB", "ab", "ab", "aB"]`.
•זוג (0,1): `secret("aB")=True`, `secret("ab")=False` - שונות.
•זוג (2,3): `secret("ab")=False`, `secret("aB")=True` - שונות.
הפעולה מחזירה `True`, אבל `arr[1]` ו-`arr[2]` הן שתיהן `"ab"` - מחרוזות זהות במקומות סמוכים.
תשובה: הטענה אינה נכונה (דוגמה נגדית: `["aB", "ab", "ab", "aB"]`).
, כאשר מספר המחרוזות ברשימה ו- אורך המחרוזת הארוכה ביותר (כלומר לינארית בסך כל התווים).
נסמן ב- את מספר המחרוזות ברשימה וב- את אורך המחרוזת הארוכה ביותר.
1. הלולאה של `mystery` מבצעת סיבובים.
2. בכל סיבוב מופעלת `secret` פעמיים, וכל הפעלה עולה לפי סעיף א(3).
3. סך הכול: . במילים אחרות, במקרה הגרוע עוברים פעם אחת על כל התווים של כל המחרוזות.
תשובה: .
שאלה 7 · מחלקת קפסולות קפה: פעולות על רשימת עצמים
נתונה המחלקה Coffee, המייצגת קפסולות למכונת קפה. תכונות המחלקה הן:
•שם היצרן – `name`, מטיפוס מחרוזת – `string`.
•סוג קפה – `kind`, מטיפוס מחרוזת – `string`.
•רמת החוזק – `strength`, מטיפוס מספר שלם – `int` (בין 1 ל-12).
•מחיר – `price`, מטיפוס מספר ממשי – `float`.
במחלקה הוגדרה פעולה בונה (`constructor`) המקבלת פרמטר לכל תכונה ויוצרת עצם סוג Coffee, המכיל את הערכים האלו בתכונות.
class Coffee:
def __init__(self, name, kind, strength, price):
self.name = name
self.kind = kind
self.strength = strength
self.price = priceכתבו פעולה המקבלת רשימה של עצמים מסוג `Coffee`. הפעולה תבדוק שכל הקפסולות הן מאותו יצרן. אם כן – הפעולה תחזיר ערך `True`, ולא – תחזיר `False`.
כותרת הפעולה:
same_products(crr)כתבו פעולה המקבלת רשימה של עצמים מסוג `Coffee` ומספר שלם חיובי `num`.
הפעולה תחזיר רשימה חדשה הכוללת את סוגי קפה שרמת החוזק שלהם קטנה מ- `num`.
אם אין רשימה אף קפסולה שרמת החוזק שלה קטנה מ- `num`, הפעולה תחזיר רשימה ריקה.
כותרת הפעולה:
weak_sorts(crr, num)כתבו פעולה המקבלת רשימה של עצמים מסוג `Coffee`. הפעולה תדפיס את פרטי הקפסולות היקרות ביותר.
כותרת הפעולה:
most_expensive(crr)◂ פתרון מלא לשאלה 7
סעיף א
משווים את `name` של כל קפסולה ל-`name` של הקפסולה הראשונה; בהבדל הראשון - `False`, ובסוף - `True`.
הרעיון: כל הקפסולות מאותו יצרן אם ורק אם לכל אחת אותו שם יצרן כמו לקפסולה הראשונה.
1. עוברים על כל קפסולה `c` ברשימה.
2. אם `c.name` שונה מ-`crr[0].name`, יש לפחות שני יצרנים שונים - מחזירים `False` מיד.
3. אם הלולאה הסתיימה, כל השמות שווים - מחזירים `True`.
(ברשימה ריקה הלולאה לא מתבצעת כלל ומוחזר `True`, ולכן אין גישה ל-`crr[0]` כשהרשימה ריקה.)
def same_products(crr):
for c in crr:
if c.name != crr[0].name:
return False
return Trueסיבוכיות: מעבר אחד על הרשימה, .
תשובה: הפעולה `same_products` שלמעלה.
סעיף ב
רשימה חדשה; לכל קפסולה עם `strength < num` מוסיפים את `kind` שלה (אם עוד לא נמצא ברשימה). אם אין כאלה - מוחזרת רשימה ריקה.
הרעיון: הפעולה מחזירה את סוגי הקפה (מחרוזות `kind`), לא את העצמים עצמם.
1. יוצרים רשימה ריקה `result`.
2. עוברים על כל קפסולה `c`. אם `c.strength < num`, מוסיפים את `c.kind` לרשימה.
3. כדי שכל סוג יופיע פעם אחת בלבד (ייתכנו כמה קפסולות מאותו סוג), מוסיפים רק אם `c.kind not in result`.
4. אם אף קפסולה לא עומדת בתנאי, `result` נשארת ריקה - בדיוק כפי שנדרש.
def weak_sorts(crr, num):
result = []
for c in crr:
if c.strength < num and c.kind not in result:
result.append(c.kind)
return resultדוגמה: עבור הקפסולות (Ristretto, חוזק 10), (Lungo, חוזק 4), (Lungo, חוזק 5), (Decaf, חוזק 2) ו-`num = 6` מוחזרת הרשימה `['Lungo', 'Decaf']`.
תשובה: הפעולה `weak_sorts` שלמעלה.
סעיף ג
מעבר ראשון מוצא את המחיר המרבי; מעבר שני מדפיס את פרטי כל הקפסולות שמחירן שווה למחיר המרבי.
הרעיון: ייתכן שכמה קפסולות חולקות את המחיר הגבוה ביותר, ולכן אי אפשר להסתפק בקפסולה אחת. עושים שני מעברים:
1. מעבר ראשון: מוצאים את המחיר המרבי `max_price` - מתחילים מהמחיר של הקפסולה הראשונה ומעדכנים בכל פעם שמוצאים מחיר גבוה יותר.
2. מעבר שני: מדפיסים את כל הפרטים (`name`, `kind`, `strength`, `price`) של כל קפסולה שמחירה שווה ל-`max_price`.
3. אם הרשימה ריקה, אין מה להדפיס ויוצאים מהפעולה.
def most_expensive(crr):
if len(crr) == 0:
return
max_price = crr[0].price
for c in crr:
if c.price > max_price:
max_price = c.price
for c in crr:
if c.price == max_price:
print(c.name, c.kind, c.strength, c.price)סיבוכיות: שני מעברים על הרשימה, .
תשובה: הפעולה `most_expensive` שלמעלה.
שאלה 8 · רשימות הפוכות ובדיקת תת-רשימה רציפה
כתבו פעולה המקבלת שתי רשימות של מספרים שלמים ובודקת אם הן הפוכות. אם כן – הפעולה תחזיר ערך `True`, ולא – תחזיר ערך `False`.
לדוגמה: הרשימות `a` ו- `b` הן רשימות הפוכות:
a = [1, 25, 3, 8, 10, 4, 20, 5]
b= [5, 20, 4, 10, 8, 3, 25, 1]מהי סיבוכיות הפעולה שכתבתם? הסבירו את תשובתכם.
נתונה הפעולה `what` המקבלת שתי רשימות של מספרים שלמים:
def what(a, b):
n = len(a)
m = len(b)
for i in range(n-m+1):
f = True
for k in range(m-1,-1, -1):
if a[i+k]!=b[k]:
f = False
if f:
return True
return Falseעקבו אחר ביצוע הפעולה `what(a,b)` עבור הפרמטרים הבאים:
a = [8,6,7,10,13,2]
b = [2,7,6]תנו דוגמה לרשימה `b` בגודל של ארבעה מספרים שעבורה זימון הפעולה `what(a,b)` יחזיר `True`.
מה מבצעת הפעולה `what` באופן כללי?
מהי הסיבוכיות של הפעולה `what`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
אם האורכים שונים - `False`; אחרת משווים `a[i]` ל-`b[n-1-i]` לכל `i`, ובהבדל הראשון - `False`; בסוף - `True`.
הרעיון: שתי רשימות הפוכות אם הראשונה בסדר רגיל שווה לשנייה בסדר הפוך: האיבר הראשון של `a` שווה לאחרון של `b`, השני לאחד-לפני-האחרון, וכן הלאה.
1. אם האורכים שונים, הרשימות אינן יכולות להיות הפוכות - מחזירים `False`.
2. לכל מקום `i` מ-0 עד משווים את `a[i]` ל-`b[n-1-i]` (המקום המקביל מהסוף). בהבדל הראשון מחזירים `False`.
3. אם כל ההשוואות הצליחו, מחזירים `True`.
def is_reversed(a, b):
n = len(a)
if n != len(b):
return False
for i in range(n):
if a[i] != b[n - 1 - i]:
return False
return Trueבדוגמה: `a[0]=1` מול `b[7]=1`, `a[1]=25` מול `b[6]=25`, ..., `a[7]=5` מול `b[0]=5` - הכול שווה, והפעולה מחזירה `True`.
תשובה: הפעולה `is_reversed` שלמעלה.
סעיף ב
, כאשר אורך הרשימות.
הלולאה מבצעת לכל היותר סיבובים (אחד לכל מקום ברשימה), ובכל סיבוב השוואה אחת - מספר קבוע של פעולות. בדיקת האורכים לוקחת זמן קבוע.
תשובה: הסיבוכיות לינארית, .
סעיף ג
הפעולה מחזירה `False` (לא נמצא אף `i` שבו כל שלושת האיברים שווים).
נתון: `n = 6`, `m = 3`, ולכן `i` עובר על `range(4)`: 0, 1, 2, 3. לכל `i` הלולאה הפנימית עוברת על `k` = 2, 1, 0 (מהסוף להתחלה), ו-`f` מתחיל ב-`True` בכל `i` חדש.
שימו לב: אין יציאה מהלולאה הפנימית כשנמצא הבדל - כל שלוש ההשוואות מתבצעות תמיד, ו-`f` שהפך ל-`False` נשאר כך עד סוף ה-`i` הנוכחי.
1. עבור `i=0`: מושווה `[8,6,7]` עם `[2,7,6]` - `f=False`.
2. עבור `i=1`: מושווה `[6,7,10]` עם `[2,7,6]` - רק `7` שווה, `f=False`.
3. עבור `i=2`: מושווה `[7,10,13]` עם `[2,7,6]` - `f=False`.
4. עבור `i=3`: מושווה `[10,13,2]` עם `[2,7,6]` - `f=False`.
בשום שלב `f` לא נשאר `True`, הלולאה החיצונית מסתיימת, ומוחזר `False`.
תשובה: `what(a,b)` מחזירה `False`.
סעיף ד
למשל `b = [6, 7, 10, 13]`.
הפעולה מחזירה `True` אם קיים `i` שעבורו `a[i+k] == b[k]` לכל `k`, כלומר אם `b` מופיעה ב-`a` כקטע רציף, באותו סדר. ב-`a = [8,6,7,10,13,2]` יש שלושה קטעים רציפים באורך 4: `[8,6,7,10]`, `[6,7,10,13]`, `[7,10,13,2]`. כל אחד מהם מתאים.
נבחר `b = [6, 7, 10, 13]`: עבור `i=1` מתקיים `a[1]=6`, `a[2]=7`, `a[3]=10`, `a[4]=13` - כל ההשוואות שוות, `f` נשאר `True`, והפעולה מחזירה `True`.
תשובה: `b = [6, 7, 10, 13]`.
סעיף ה
מחזירה `True` אם הרשימה `b` מופיעה בתוך `a` כקטע רציף (תת-רשימה רציפה, באותו סדר), אחרת `False`.
1. הלולאה החיצונית עוברת על כל מקום התחלה אפשרי `i` ב-`a` שממנו נשארים לפחות `m` איברים (מ-0 עד ).
2. הלולאה הפנימית משווה את הקטע `a[i], a[i+1], ..., a[i+m-1]` איבר-איבר עם `b[0], ..., b[m-1]`. אם יש הבדל כלשהו, `f` הופך ל-`False`.
3. אם בקטע כלשהו כל האיברים שווים, `f` נשאר `True` ומוחזר `True`. אם אין קטע כזה, מוחזר `False`.
תשובה: הפעולה בודקת אם הרשימה `b` מופיעה כקטע רציף (באותו סדר) בתוך הרשימה `a`.
סעיף ו
, כלומר במקרה הגרוע.
נסמן = אורך `a`, = אורך `b`.
1. הלולאה החיצונית מבצעת עד סיבובים.
2. בכל סיבוב הלולאה הפנימית מבצעת תמיד השוואות (אין בה יציאה מוקדמת).
3. סך הכול במקרה הגרוע (כש-`b` לא נמצאת): השוואות, כלומר . למשל כאשר זה בסדר גודל של .
תשובה: .
שאלה 9 · מחלקה המונה ספרות של מספר
נתונה מחלקה `Digits` המתארת ספרות של מספר שלם וחיובי.
למחלקה `Digits` תכונה אחת בלבד `arr_digits` – רשימה בת עשרה ערכים מטיפוס מספר שלם, המייצגת את מספר הפעמים שבו כל ספרה בין 0-9 מופיעה במספר.
לדוגמה: עבור התכונה `arr_digits` הבאה: `[0, 0, 1, 0, 2, 0, 0, 0, 3, 0]`
המידע המתקבל עבור מספר מסוים הוא:
•הספרה 2 מופיעה במספר פעם אחת.
•הספרה 4 מופיעה במספר שתי פעמים.
•הספרה 8 מופיעה במספר שלוש פעמים.
כתבו במחלקה `Digits` פעולה בונה (`constructor`) המקבלת כפרמטר מספר שלם חיובי כלשהו ומאתחלת את התכונה `arr_digits` בהתאם (כלומר הרשימה תכיל את מספר הפעמים שכל ספרה מופיעה בו).
כתבו במחלקה `Digits` פעולה `equals` המקבלת הפניה לעצם אחר מטיפוס `Digits`.
הפעולה תחזיר ערך `True` אם שני העצמים זהים, ולא – הפעולה תחזיר ערך `False`.
נתון קטע הבא:
num1 = int(input("first number:"))
num2 = int(input("second number:"))
dg1=Digits(num1)
dg2=Digits(num2)
if dg1.equals(dg2):
print("the numbers are equal")
else:
print("the number are not equal")האם הפעולה מדפיסה תוצאה נכונה עבור כל זוג מספרים שלמים וחיובים `num1` ו-`num2`?
הסבירו את תשובתכם.
כתבו במחלקה `Digits` פעולה `compare_to` המקבלת כפרמטר הפניה לעצם `other` מטיפוס `Digits`.
•הפעולה תחזיר 1 אם מספר המיוצג על ידי העצם המפעיל את הפעולה (`this`) גדול ממספר המיוצג על ידי העצם שהתקבל כפרמטר (`other`).
•הפעולה תחזיר 2 אם המספר המיוצג על ידי העצם המפעיל את הפעולה (`this`) קטן מהמספר המיוצג על ידי העצם שהתקבל כפרמטר (`other`).
•אם אין אפשרות לתשובה חד משמעית, הפעולה תחזיר 0.
◂ פתרון מלא לשאלה 9
סעיף א
יוצרים רשימה של 10 אפסים; כל עוד `num > 0` מגדילים ב-1 את `arr_digits[num % 10]` ומבצעים `num //= 10`.
1. יוצרים רשימה של עשרה אפסים: `[0] * 10`. המקום `d` ברשימה יחזיק את מספר ההופעות של הספרה `d`.
2. מפרקים את המספר לספרות: `num % 10` היא הספרה הימנית. מגדילים ב-1 את המונה שלה: `arr_digits[num % 10] += 1`.
3. מסירים את הספרה הימנית: `num //= 10`, וחוזרים עד ש-`num` מתאפס.
המספר חיובי, ולכן הלולאה מתבצעת לפחות פעם אחת.
class Digits:
def __init__(self, num):
self.arr_digits = [0] * 10
while num > 0:
self.arr_digits[num % 10] += 1
num //= 10דוגמה: עבור `num = 2448` מתקבל `arr_digits = [0, 0, 1, 0, 2, 0, 0, 0, 1, 0]`.
תשובה: הפעולה הבונה שלמעלה.
סעיף ב
משווים את `arr_digits` של שני העצמים מקום-מקום (0 עד 9); בהבדל הראשון - `False`, אחרת `True`.
הרעיון: לעצם יש תכונה אחת בלבד, ולכן שני עצמים זהים אם ורק אם הרשימות `arr_digits` שלהם שוות בכל עשרת המקומות.
1. עוברים על `i` מ-0 עד 9.
2. אם `self.arr_digits[i] != other.arr_digits[i]` - יש ספרה שמספר ההופעות שלה שונה, ומחזירים `False`.
3. אם כל המקומות שווים, מחזירים `True`.
class Digits:
...
def equals(self, other):
for i in range(10):
if self.arr_digits[i] != other.arr_digits[i]:
return False
return Trueתשובה: הפעולה `equals` שלמעלה.
סעיף ג
לא. העצם שומר רק כמה פעמים מופיעה כל ספרה, לא את סדר הספרות; למשל עבור 12 ו-21 יודפס "the numbers are equal" למרות שהמספרים שונים.
1. `equals` משווה רק את מספר ההופעות של כל ספרה. המידע על סדר הספרות אובד בפעולה הבונה.
2. כאשר המספרים שווים באמת, לשניהם אותן ספרות, ומודפס בצדק "the numbers are equal". כאשר לשני המספרים אוסף ספרות שונה, מודפס בצדק "not equal".
3. אבל שני מספרים שונים שהם סידור אחר של אותן ספרות נותנים רשימות `arr_digits` זהות. דוגמה נגדית: `num1 = 12`, `num2 = 21`. לשניהם הספרה 1 פעם אחת והספרה 2 פעם אחת, ולכן `equals` מחזירה `True` ומודפס "the numbers are equal", אף ש-.
תשובה: לא. התוצאה שגויה עבור מספרים שונים בעלי אותן ספרות בסדר אחר (למשל 12 ו-21).
סעיף ד
משווים קודם את מספר הספרות (סכום `arr_digits`): יותר ספרות - גדול יותר. באותו מספר ספרות: אם הסידור הקטן ביותר של `this` גדול מהסידור הגדול ביותר של `other` - 1; אם הסידור הגדול ביותר של `this` קטן מהסידור הקטן ביותר של `other` - 2; אחרת 0.
הרעיון: העצם יודע אילו ספרות יש במספר אבל לא באיזה סדר. לכן המספר "האמיתי" יכול להיות כל סידור של הספרות (בלי 0 מוביל, כי המספר חיובי). נקבע תשובה רק אם היא נכונה לכל הסידורים האפשריים:
1. מספר הספרות הוא סכום הערכים ב-`arr_digits`. למספר חיובי בלי אפסים מובילים, מספר עם יותר ספרות תמיד גדול יותר. לכן אם ל-`this` יש יותר ספרות - מחזירים 1, ואם פחות - מחזירים 2.
2. אותו מספר ספרות: נחשב לכל עצם את הטווח של הערכים האפשריים:
•הסידור הגדול ביותר (`max_number`): הספרות מהגדולה לקטנה, למשל עבור הספרות 1, 9 - המספר 91.
•הסידור הקטן ביותר (`min_number`): הספרה הקטנה ביותר שאינה 0 בהתחלה, ואחריה כל השאר מהקטנה לגדולה, למשל עבור 0, 3 - המספר 30 (ולא 03).
3. אם גם הסידור הקטן ביותר של `this` גדול מהסידור הגדול ביותר של `other`, אז `this` גדול בוודאות - מחזירים 1. באופן סימטרי, אם הסידור הגדול ביותר של `this` קטן מהסידור הקטן ביותר של `other` - מחזירים 2.
4. אחרת שני הטווחים חופפים, ואפשר לבחור סידורים שבהם `this` גדול וסידורים שבהם הוא קטן (או שווה) - מחזירים 0. בפרט, אם לשני העצמים אותן ספרות בדיוק, תמיד מוחזר 0.
class Digits:
...
def count_digits(self):
total = 0
for i in range(10):
total += self.arr_digits[i]
return total
def max_number(self):
# digits from the largest to the smallest
result = 0
for d in range(9, -1, -1):
for k in range(self.arr_digits[d]):
result = result * 10 + d
return result
def min_number(self):
# the smallest non-zero digit first, then all digits from the smallest
counts = self.arr_digits[:]
first = 1
while counts[first] == 0:
first += 1
counts[first] -= 1
result = first
for d in range(10):
for k in range(counts[d]):
result = result * 10 + d
return result
def compare_to(self, other):
len1 = self.count_digits()
len2 = other.count_digits()
if len1 > len2:
return 1
if len1 < len2:
return 2
if self.min_number() > other.max_number():
return 1
if self.max_number() < other.min_number():
return 2
return 0דוגמאות:
•`Digits(100)` מול `Digits(99)`: 3 ספרות מול 2 - מוחזר 1.
•`Digits(30)` מול `Digits(12)`: הסידור הקטן ביותר של `{3,0}` הוא 30, הגדול ביותר של `{1,2}` הוא 21, ו- - מוחזר 1.
•`Digits(19)` מול `Digits(23)`: ייתכן אבל גם - מוחזר 0.
•`Digits(12)` מול `Digits(21)`: אותן ספרות - מוחזר 0.
תשובה: הפעולה `compare_to` שלמעלה: לפי מספר הספרות, ובמספר ספרות שווה לפי השוואת הסידור הקטן ביותר והגדול ביותר; 0 כשהתשובה תלויה בסדר הספרות.
שאלה 10 · מחלקות בניין, דירה וחדר: חישוב חיוב חודשי
החברה "`CleanMe`" נותנת שרותי אחזקה וניקיון דירות ללקוחות פרטיים בבניינים רבי קומות".
לצורך מחשוב הוגדרו שלוש מחלקות: `Building`, `App`, `Room`.
המחלקה `Room` מייצגת חדר. לכל חדר שומרים את הפרטים הבאים:
•`kind` – סוג חדר (חדר שינה, חדר עבודה, שירותים, אמבטיה, מטבח וכו').
•`area` – שטח במטרים מרובעים.
•`freq` – תדירות הניקיון בחודש (0- לא צריך לנקות, 1- יש לנקות פעם אחת בחודש, 2- פעמיים בחודש, 3- שלוש פעמים וכד').
המחלקה `App` מייצגת דירה. לכל דירה שומרים את הפרטים הבאים:
•`app_num` – מס' דירה.
•`owner` – שם בעל הדירה.
•`rooms` – רשימת חדרים (עצמים מסוג `Room`) השייכים לדירה.
•`rate` – מחיר הניקיון של מטר מרובע אחד בדירה זו.
שימו לב: מחיר זה משתנה מדירה לדירה ותלוי בהסכם בין בעל הדירה והחברה.
המחלקה `Building` מייצגת בניין. פרטי הבניין הם:
•`address` – כתובת בניין (רחוב ומספר).
•`apartments` – רשימת דירות (הפניות לעצמים מסוג `App`) שחברה נותנת להן שרותי ניקיון.
כתבו לכל אחת מהמחלקות `Building`, `App`, `Room` פעולות בונות (`constructor`)
המחיר החודשי של ניקיון הדירה מחושב בהתאם לשטח הכולל של החדרים שיש לנקות, תדירות הניקיון ומחיר הניקיון של מטר מרובע בדירה זו.
כתבו במחלקה `App` פעולה המחזירה מחיר חודשי של ניקיון הדירה.
כותרת הפעולה:
month_cost(self)כתבו פעולה המקבלת רשימת בניינים (עצמים מסוג `Building`) שהחברה נותנת שירות בהם `builds` ורשימת שמות של לקוחות החברה `clients`. הפעולה תדפיס עבור כל לקוח חשבונית הכוללת את שם לקוח, את פרטי כל הדירות השייכות ללקוח, את התשלום החודשי לכל דירה ואת התשלום הכולל שאותו לקוח צריך לשלם.
כותרת הפעולה:
month_report(builds, clients)◂ פתרון מלא לשאלה 10
סעיף א
לכל מחלקה `__init__` שמקבלת פרמטר לכל תכונה ושומרת אותו ב-`self`: `Room(kind, area, freq)`, `App(app_num, owner, rooms, rate)`, `Building(address, apartments)`.
הרעיון: פעולה בונה מקבלת ערך לכל תכונה ושומרת אותו בעצם החדש. התכונות `rooms` ו-`apartments` הן רשימות של הפניות לעצמים מהמחלקות האחרות (דירה מכילה חדרים, בניין מכיל דירות), ולכן הפעולה הבונה מקבלת את הרשימה המוכנה ושומרת אותה.
class Room:
def __init__(self, kind, area, freq):
self.kind = kind
self.area = area
self.freq = freq
class App:
def __init__(self, app_num, owner, rooms, rate):
self.app_num = app_num
self.owner = owner
self.rooms = rooms
self.rate = rate
class Building:
def __init__(self, address, apartments):
self.address = address
self.apartments = apartmentsתשובה: שלוש הפעולות הבונות שלמעלה.
סעיף ב
על כל חדרי הדירה.
הרעיון: כל חדר מנוקה `freq` פעמים בחודש, ובכל ניקיון מנקים `area` מטרים מרובעים. לכן החדר תורם בחודש `area * freq` מטרים מרובעים לניקיון. חדר עם `freq = 0` תורם 0, כנדרש.
1. סוכמים על כל החדרים ברשימה `rooms` את `room.area * room.freq` - סך המטרים המרובעים שמנקים בחודש.
2. כופלים במחיר למטר מרובע `rate` של הדירה.
class App:
...
def month_cost(self):
total_area = 0
for room in self.rooms:
total_area += room.area * room.freq
return total_area * self.rateדוגמה: דירה עם חדר שינה של (פעמיים בחודש) ומטבח של (4 פעמים בחודש) ומחיר 5 למטר: .
תשובה: הפעולה `month_cost` שלמעלה מחזירה `rate * Σ(area * freq)`.
סעיף ג
לכל שם ב-`clients`: מדפיסים את השם, עוברים על כל הבניינים ועל כל הדירות בהם; לכל דירה ש-`owner` שלה שווה לשם מדפיסים כתובת, מספר דירה ו-`month_cost()`, וצוברים; בסוף מדפיסים את הסכום הכולל.
הרעיון: ללקוח יכולות להיות כמה דירות, גם בבניינים שונים. לכן לכל לקוח עוברים על כל הדירות של כל הבניינים:
1. לולאה על כל שם `name` ברשימה `clients`. מדפיסים את שם הלקוח ומאפסים סכום `total`.
2. לולאה על כל בניין `b` ב-`builds`, ובתוכה לולאה על כל דירה `app` ב-`b.apartments`.
3. אם `app.owner == name`, הדירה שייכת ללקוח: מחשבים את התשלום החודשי בעזרת `app.month_cost()` מסעיף ב, מדפיסים את פרטי הדירה (כתובת הבניין, מספר הדירה, התשלום החודשי) ומוסיפים את התשלום ל-`total`.
4. אחרי שעברנו על כל הבניינים, מדפיסים את התשלום הכולל של הלקוח.
def month_report(builds, clients):
for name in clients:
print("Client:", name)
total = 0
for b in builds:
for app in b.apartments:
if app.owner == name:
cost = app.month_cost()
print(" Address:", b.address, "Apartment:", app.app_num,
"Monthly payment:", cost)
total += cost
print("Total payment:", total)סיבוכיות: לכל לקוח עוברים על כל הדירות בכל הבניינים, כלומר (מספר הלקוחות כפול מספר הדירות), ובכל דירה מחשבים את המחיר לפי מספר החדרים שלה.
תשובה: הפעולה `month_report` שלמעלה.
שאלה 11 · מילון מחירים: חישוב סכום קנייה ומוצרים חסרים
בחנות קיים מבנה נתונים מסוג מילון המייצג רשימת מוצרים ומחירים בהתאם ליחידת מוצר.
prices = {'apple':10.0, 'banana': 6.5, 'milk':6.90, ….}דני מגיע לחנות עם רשימת קניות שאימא שלו הכינה:
shopping_list=[('apple',3),('milk',2),('coca-cola', 3)…]כתבו פעולה המקבלת מילון מוצרים `prices` ורשימת קניות `shopping_list`.
הפעולה תחשב ותחזיר סכום כולל שדני חייב לשלם.
מירי, אחותו הקטנה של דני, מתכוננת למסיבת היום הולדת שלה, וביקשה מדני לבדוק האם כל מה שהיא רוצה אפשר לקנות בחנות. לשם כך היא הכינה רשימת מוצרים שלה:
sister_list = ['milky', 'shoko', 'fries'…]כתבו פעולה המקבלת מילון מוצרים `prices` ורשימה `sister_list`. הפעולה תיצור ותחזיר רשימה מוצרים מתוך רשימה של מירי שחסרים בחנות.
◂ פתרון מלא לשאלה 11
סעיף א
סכום על כל זוג `(product, amount)` ברשימה: `prices[product] * amount`, רק עבור מוצרים שנמצאים במילון.
הרעיון: כל איבר ברשימת הקניות הוא זוג (tuple): שם מוצר וכמות. המחיר ליחידה נמצא במילון לפי שם המוצר.
1. מאתחלים `total = 0`.
2. לכל זוג ברשימה: `product = item[0]`, `amount = item[1]`.
3. אם המוצר נמצא במילון (`product in prices`), מוסיפים לסכום `prices[product] * amount`.
4. מוצר שאינו במילון אינו נמכר בחנות ולכן דני לא משלם עליו (בלי הבדיקה, גישה `prices[product]` למפתח שלא קיים הייתה גורמת לשגיאה `KeyError`).
5. מחזירים את `total`.
def total_price(prices, shopping_list):
total = 0
for item in shopping_list:
product = item[0]
amount = item[1]
if product in prices:
total += prices[product] * amount
return totalדוגמה: עם המחירים שבמילון ורשימת הקניות שבשאלה (בהנחה ש-`'coca-cola'` אינו במילון): .
תשובה: הפעולה `total_price` שלמעלה.
סעיף ב
רשימה חדשה של כל המוצרים מ-`sister_list` שאינם מפתחות במילון `prices` (`product not in prices`).
הרעיון: מוצר "חסר בחנות" אם אינו מופיע כמפתח במילון המחירים.
1. יוצרים רשימה ריקה `missing`.
2. עוברים על כל מוצר ברשימה של מירי. אם `product not in prices`, מוסיפים אותו ל-`missing`.
3. מחזירים את `missing`. אם כל המוצרים נמכרים בחנות - מוחזרת רשימה ריקה.
בדיקת `in` במילון מתבצעת בזמן קבוע בממוצע, ולכן הפעולה כולה לינארית באורך הרשימה של מירי.
def missing_products(prices, sister_list):
missing = []
for product in sister_list:
if product not in prices:
missing.append(product)
return missingדוגמה: עבור המילון `{'apple':10.0, 'banana':6.5, 'milk':6.90}` והרשימה `['milky', 'shoko', 'fries', 'apple']` מוחזרת הרשימה `['milky', 'shoko', 'fries']`.
תשובה: הפעולה `missing_products` שלמעלה.
שאלה 12 · רקורסיה: חזקת עשר וחיפוש ספרות רצופות
נתונות הפעולות הרקורסיביות הבאות: `what1, what2, what3`:
def what1(num):
if num == 0:
return 1
else:
return 10* what1(num//10)
def what2(num1, num2):
d = secret(num2)
return what3(num1, num2, d)
def what3(num1, num2, d):
if num1 < num2 :
return False
if num1 % d == num2:
return True
return what3(num1//10, num2, d)עקבו אחרי זימון `what1(123)` רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `what1(num)` עבור מספר שלם חיובי `num`?
עקבו אחרי זימון `what2(124567,234)` ורשמו את תוצאות הזימון.
תנו דוגמה למספר תלת-סיפרתי `num` שעבורו זימון `what2(456789, num)` יחזיר ערך `True`.
מה מבצעת הפעולה `what2(num1,num2)` עבור שני מספרים שלמים וחיוביים `num1` ו- `num2`?
◂ פתרון מלא לשאלה 12
סעיף א
`what1(123)` מחזירה 1000.
בכל קריאה, אם `num` אינו 0, הפעולה מסירה את הספרה הימנית (`num//10`) ומכפילה ב-10 את תוצאת הקריאה הרקורסיבית. תנאי העצירה: `num == 0` מחזיר 1.
הקריאות יורדות מלמעלה למטה, והערכים חוזרים מלמטה למעלה:
תשובה: `what1(123)` מחזירה 1000.
סעיף ב
מחזירה , כאשר מספר הספרות של `num` (למשל עבור 123 - 1000).
1. כל קריאה רקורסיבית מסירה ספרה אחת מ-`num` ומכפילה את התוצאה ב-10.
2. אם ל-`num` יש ספרות, אחרי קריאות `num` מגיע ל-0 ומוחזר 1.
3. לכן התוצאה היא - המספר 1 ואחריו אפסים, כלומר החזקה הקטנה ביותר של 10 שגדולה מ-`num`.
תשובה: הפעולה מחזירה , כאשר הוא מספר הספרות של `num`.
סעיף ג
`d = 1000`; הקריאות `what3` בודקות 567, 456, 245 ואף אחד מהם אינו 234; כשמגיעים ל-`num1 = 124 < 234` מוחזר `False`. התוצאה: `False`.
הפעולה `secret` לא הוגדרה בשאלה, ונאמר שאין צורך לעקוב אחריה. מההקשר (פעולות `what1` ו-`what3`) הכוונה היא לפעולה `what1`: `d = secret(234)` הוא , כי ל-234 שלוש ספרות. כך `num1 % d` נותן בדיוק את שלוש הספרות האחרונות של `num1`, שאותן משווים ל-`num2`.
1. `what2(124567, 234)`: מחשבים `d = 1000` וקוראים ל-`what3(124567, 234, 1000)`.
2. בכל קריאה של `what3`: אם `num1 < num2` - מחזירים `False`; אם שלוש הספרות האחרונות של `num1` (`num1 % 1000`) שוות ל-234 - מחזירים `True`; אחרת מסירים את הספרה הימנית של `num1` וממשיכים.
בקריאה הרביעית `num1 = 124` כבר קטן מ-`num2 = 234` (נשארו שלוש ספרות שאינן 234), ולכן מוחזר `False` בלי לבדוק את השארית. הערך `False` חוזר כמו שהוא דרך כל הקריאות עד `what2`.
תשובה: `what2(124567,234)` מחזירה `False`.
סעיף ד
למשל `num = 567` (מתאימים גם 456, 678, 789).
הפעולה מחזירה `True` כאשר שלוש הספרות האחרונות של `num1`, אחרי הסרת מספר כלשהו של ספרות מימין, שוות ל-`num`. כלומר `num` צריך להיות שלוש ספרות רצופות מתוך 456789: 789, 678, 567 או 456.
בדיקה עבור `num = 567` (`d = 1000`):
1. `what3(456789, 567, 1000)`: , ממשיכים עם 45678.
2. `what3(45678, 567, 1000)`: , ממשיכים עם 4567.
3. `what3(4567, 567, 1000)`: - שווה, מוחזר `True`.
תשובה: `num = 567` (או 456, 678, 789).
סעיף ה
מחזירה `True` אם הספרות של `num2` מופיעות ברצף (באותו סדר) בתוך `num1`, כלומר `num2` הוא "תת-מספר" רציף של `num1`; אחרת `False`.
1. `d` הוא , כאשר מספר הספרות של `num2` (סעיף ב). לכן `num1 % d` הן הספרות האחרונות של `num1`.
2. `what3` משווה את הספרות האחרונות ל-`num2`, ואם אינן שוות מסירה את הספרה הימנית של `num1` ובודקת שוב. כך נבדקים כל קטעי הספרות הרצופות של `num1`, מהימני ועד השמאלי.
3. העצירה ב-`num1 < num2` מתרחשת כשנשארו ב-`num1` פחות ספרות מ-`num2` (או ערך קטן מדי), ואז כבר אין קטע מתאים, ומוחזר `False`.
תשובה: הפעולה בודקת אם `num2` מופיע כרצף ספרות (באותו סדר) בתוך `num1` - אם כן מחזירה `True`, אחרת `False`.