מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - אביב 2024 מועד א'
הנדסת תוכנה · סמל 97103 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), אביב 2024 מועד א', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: מבחן ב-Python
חלק א' – 48 נקודות
שאלות 1-7: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 8-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 22 נקודות
שאלות 12-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
אין לצרף ספרים או חוברות עם פתרונות.
שאלה 1 · קליטת מספרים, מכפלת ספרות ומניית אי-זוגיים
כתבו קטע תוכנית שיקלוט 30 מספרים חיוביים ושלמים
•עבור כל מספר תלת ספרתי שנקלט יש להדפיס את מכפלת ספרותיו.
לדוגמה: עבור מספר 123 יש להדפיס 6 (1\*2\*3).
•על הקוד לחשב ולהדפיס כמה מספרים אי זוגיים נקלטו.
◂ פתרון מלא לשאלה 1
פתרון
לולאה של 30 קליטות; למספר בתחום 100–999 מחשבים את מכפלת הספרות בעזרת `% 10` ו-`// 10` ומדפיסים; מונה סופר מספרים שהשארית שלהם בחלוקה ב-2 היא 1, ומודפס בסוף.
1. מריצים לולאה בדיוק 30 פעמים, ובכל סיבוב קולטים מספר אחד.
2. מספר חיובי הוא תלת ספרתי אם הוא בין 100 ל-999 (כולל).
3. כדי לחשב את מכפלת הספרות מפרקים את המספר: `temp % 10` נותן את ספרת האחדות, ו-`temp // 10` מוחק אותה. מכפילים את הספרה במשתנה `product` שמתחיל ב-1 (האיבר הניטרלי בכפל), עד שהמספר מתאפס. עובדים על עותק (`temp`) כדי לא להרוס את המספר המקורי.
4. מספר הוא אי-זוגי אם השארית שלו בחלוקה ב-2 היא 1. מונה `odd_count` גדל ב-1 בכל פעם כזו, וההדפסה שלו נעשית רק אחרי הלולאה, כשכל 30 המספרים כבר נקלטו.
לדוגמה, עבור 123: , אחר כך , אחר כך , ומודפס 6.
odd_count = 0
for i in range(30):
num = int(input())
if 100 <= num <= 999: # מספר תלת ספרתי
product = 1
temp = num
while temp > 0:
product *= temp % 10 # מכפילים בספרת האחדות
temp //= 10 # מוחקים את ספרת האחדות
print(product)
if num % 2 == 1: # מספר אי-זוגי
odd_count += 1
print("odd numbers:", odd_count)סיבוכיות: כל מספר מטופל במספר קבוע של פעולות (לכל היותר 3 ספרות), ולכן זמן הריצה הוא עבור מספרים.
תשובה: הקוד שלמעלה – לכל מספר תלת ספרתי מודפסת מכפלת ספרותיו, ובסוף מודפס מספר המספרים האי-זוגיים שנקלטו.
שאלה 2 · קליטת מחרוזות עד תנאי עצירה ומניות
כתבו קטע תוכנית הקולט מחרוזות עד שתיקלט מחרוזת שאורכה קטן משישה תווים.
עבור כל מחרוזת באורך אי זוגי יודפס התו האמצעי במחרוזת.
נוסף על כך יש לחשב ולהדפיס:
•כמה מחרוזות מתחילות באות גדולה ('A' עד 'Z').
•כמה מחרוזות לא מסתיימות בספרה ('0'..'9').
◂ פתרון מלא לשאלה 2
פתרון
לולאת `while len(s) >= 6`; במחרוזת באורך אי-זוגי מודפס `s[len(s)//2]`; מונה לתו ראשון בין 'A' ל-'Z' ומונה לתו אחרון שאינו בין '0' ל-'9'; שני המונים מודפסים אחרי הלולאה.
1. זו לולאת זקיף: קולטים מחרוזת ראשונה לפני הלולאה, והלולאה רצה כל עוד אורך המחרוזת הוא 6 תווים או יותר. בסוף כל סיבוב קולטים את המחרוזת הבאה. המחרוזת הקצרה (שאורכה קטן מ-6) רק מסיימת את הקלט ולא נספרת.
2. במחרוזת באורך אי-זוגי התו האמצעי נמצא באינדקס , שהוא בדיוק `len(s) // 2`. לדוגמה, ב-"abcdefg" () האינדקס הוא 3, התו 'd'.
3. מחרוזת מתחילה באות גדולה אם התו הראשון `s[0]` נמצא בין 'A' ל-'Z'.
4. מחרוזת לא מסתיימת בספרה אם התו האחרון `s[-1]` אינו בין '0' ל-'9'.
5. אורך כל מחרוזת שנבדקת הוא לפחות 6, ולכן `s[0]` ו-`s[-1]` תמיד קיימים.
6. את שני המונים מדפיסים אחרי הלולאה.
upper_count = 0 # מחרוזות שמתחילות באות גדולה
not_digit_end = 0 # מחרוזות שלא מסתיימות בספרה
s = input()
while len(s) >= 6:
if len(s) % 2 == 1:
print(s[len(s) // 2]) # התו האמצעי
if 'A' <= s[0] <= 'Z':
upper_count += 1
if not ('0' <= s[-1] <= '9'):
not_digit_end += 1
s = input()
print("start with capital:", upper_count)
print("not ending with digit:", not_digit_end)דוגמה: עבור הקלט Hello12, abcdef, XYZabc9, qwertyu, abc יודפסו התווים l, a, r (המחרוזות באורך 7), אחר כך 2 מחרוזות שמתחילות באות גדולה (Hello12, XYZabc9) ו-2 מחרוזות שלא מסתיימות בספרה (abcdef, qwertyu).
תשובה: הקוד שלמעלה – מדפיס את התו האמצעי של כל מחרוזת באורך אי-זוגי, ובסוף את מספר המחרוזות שמתחילות באות גדולה ואת מספר המחרוזות שלא מסתיימות בספרה.
שאלה 3 · רשימה מאורגנת: בדיקה ומילוי אקראי
רשימה של מספרים שלמים נקראת "רשימה מאורגנת" אם כל הערכים הנמצאים במקומות הזוגיים גדולים מכל הערכים הנמצאים במקומות האי-זוגיים.
הרשימה `arr = [12,3,7,5,15,2,6]` היא רשימה "מאורגנת":
כתבו פעולה המקבלת רשימה של מספרים שלמים `arr`. הפעולה תחזיר ערך `true`, אם הרשימה "מאורגנת", ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
is_arranged(arr)כתבו פעולה המקבלת רשימה של מספרים שלמים `arr` ושני פרמטרים נוספים `a` ו-`b`, מטיפוס מספר שלם. הפעולה תמלא רשימה `arr` במספרים אקראיים בין `a` ל-`b` (כולל) עד שהרשימה תהיה "מאורגנת".
כותרת הפעולה:
fill(arr, a, b)◂ פתרון מלא לשאלה 3
סעיף א
מחשבים את המינימום במקומות הזוגיים ואת המקסימום במקומות האי-זוגיים, ומחזירים `min_even > max_odd`.
"כל ערך במקום זוגי גדול מכל ערך במקום אי-זוגי" שקול לתנאי אחד: הקטן ביותר מבין הערכים במקומות הזוגיים גדול מהגדול ביותר מבין הערכים במקומות האי-זוגיים. כך לא צריך להשוות כל זוג, ומספיק מעבר אחד על הרשימה.
1. מוצאים את `min_even` – המינימום באינדקסים (לולאה בקפיצות של 2 מ-0).
2. מוצאים את `max_odd` – המקסימום באינדקסים (לולאה בקפיצות של 2 מ-1).
3. מחזירים `True` אם , אחרת `False`.
בדוגמה: המקומות הזוגיים מכילים והמינימום הוא 6; המקומות האי-זוגיים מכילים והמקסימום הוא 5. מתקיים , ולכן הרשימה מאורגנת.
לפי הנתון ברשימה יש לפחות שני ערכים, ולכן `arr[0]` ו-`arr[1]` קיימים.
def is_arranged(arr):
min_even = arr[0]
for i in range(0, len(arr), 2): # מקומות זוגיים
if arr[i] < min_even:
min_even = arr[i]
max_odd = arr[1]
for i in range(1, len(arr), 2): # מקומות אי-זוגיים
if arr[i] > max_odd:
max_odd = arr[i]
return min_even > max_oddסיבוכיות: , מעבר אחד על כל איבר.
תשובה: הפעולה `is_arranged` שלמעלה – מחזירה `True` אם ורק אם המינימום במקומות הזוגיים גדול מהמקסימום במקומות האי-זוגיים.
סעיף ב
לולאה: ממלאים את כל `arr` ב-`random.randint(a, b)` ובודקים עם `is_arranged` מסעיף א; חוזרים עד שהבדיקה מחזירה `True`.
1. בכל ניסיון ממלאים מחדש את כל המקומות ברשימה במספרים אקראיים בתחום בעזרת `random.randint(a, b)`. הרשימה משתנה במקום (by reference), ולכן אין צורך להחזיר אותה.
2. אחרי כל מילוי בודקים בעזרת `is_arranged` מסעיף א אם הרשימה מאורגנת. אם לא – מנסים שוב.
3. הלולאה תסתיים: מכיוון ש-, תמיד קיים מילוי מאורגן (למשל בכל המקומות הזוגיים ו- בכל המקומות האי-זוגיים), ולכן לכל ניסיון יש הסתברות חיובית להצליח.
import random
def fill(arr, a, b):
done = False
while not done:
for i in range(len(arr)):
arr[i] = random.randint(a, b)
done = is_arranged(arr)תשובה: הפעולה `fill` שלמעלה – ממלאת שוב ושוב את הרשימה במספרים אקראיים בין `a` ל-`b` עד ש-`is_arranged(arr)` מחזירה `True`.
שאלה 4 · מחלקת תינוק: עדכון מדידות, ממוצע ו-BMI
המחלקה `Baby` (תינוק) משמשת למעקב התפתחותי של התינוקות המגיעים למרפאה במהלך השנה הראשונה לחייהם.
כל תינוק מוזמן לביקורת אחת לחודש. בכל ביקורת שוקלים ומודדים את גובה התינוק ושומרים את התוצאות.
שימו לב: במקרה שתינוק לא הגיע לביקורת בחודש מסוים ערך המדידות יהיה 0 בחודש זה.
אפשר להניח שבחודש שבו הגיע לביקורת תהיה גם מדידת משקל וגם מדידת גובה.
תכונות המחלקה:
שם התינוק – `name`, מטיפוס מחרוזת, `str`
רשימת מדידות גובה – `height` – רשימה באורך 12 של מספרים ממשיים, `float`
רשימת מדידות משקל – `weight` – רשימה באורך 12 של מספרים ממשיים, `float`
הערה: אורך הרשימות `height` ו-`weight` הוא 12. ערך במקום אפס שומר מדידות שנעשו בחודש הראשון אחרי לידה, במקום מספר אחד – מדידות שנעשו בחודש השני אחרי לידה וכך הלאה.
לדוגמה:
שתי רשימות מתארות את התפתחות הילד ב-12 חודשים הראשונים:
משקל בקילוגרמים (`weight`):
גובה במטרים (`height`):
המדידה הראשונה הייתה בחודש 1, המדידה האחרונה הייתה בחודש 12
שימו לב: בחודשים 2, 6, 8, 9, 11 לא היו מדידות
כתבו פעולה המקבלת מספר חודש `month`, גובה `h` ומשקל `w` ומעדכנת את רשימות המדידות בהתאם. כותרת הפעולה:
set_data(int month, double h, double w)כתבו פעולה המחזירה את ממוצע המשקל על פי כל המדידות שהתקיימו. כותרת הפעולה:
avg_weight()המדד מסת גוף (BMI - BodyMassIndex) משקלל את המשקל עם הגובה. המדד הזה חשוב להערכה אם התפתחות הילד תקינה. חישוב ה-BMI מתבצע לפי הנוסחה הבאה: משקל חלקי גובה בריבוע:
כתבו פעולה המחזירה מדד ה-BMI של התינוק על פי המדידה האחרונה שלו. כותרת הפעולה:
get_last_Bmi()◂ פתרון מלא לשאלה 4
סעיף א
`self.height[month - 1] = h` ו-`self.weight[month - 1] = w` (חודש 1 נשמר במקום 0).
לפי ההערה, חודש 1 נשמר במקום 0, חודש 2 במקום 1, וכן הלאה. לכן המדידה של חודש `month` נשמרת באינדקס `month - 1` בשתי הרשימות. ב-Python הפעולה היא פעולה של המחלקה, ולכן הפרמטר הראשון שלה הוא `self` (הטיפוסים `int`/`double` בכותרת אינם נכתבים ב-Python).
לשלמות מוצג גם בנאי פשוט שמאתחל את שתי הרשימות באפסים (חודש בלי ביקורת = 0):
class Baby:
def __init__(self, name):
self.name = name
self.height = [0.0] * 12 # מקום i = חודש i+1
self.weight = [0.0] * 12 def set_data(self, month, h, w):
self.height[month - 1] = h
self.weight[month - 1] = wלדוגמה, `set_data(12, 0.792, 14.705)` כותבת 0.792 ל-`height[11]` ו-14.705 ל-`weight[11]`.
תשובה: הפעולה מעדכנת את `height[month-1]` ל-`h` ואת `weight[month-1]` ל-`w`.
סעיף ב
סכום המשקלים השונים מ-0 חלקי מספרם; בדוגמה .
חודש שבו לא הייתה ביקורת שמור כ-0, ואסור לכלול אותו בממוצע. לכן סוכמים רק משקלים שונים מ-0 וסופרים כמה כאלה היו, ומחלקים את הסכום במונה. אם לא הייתה אף מדידה, מחזירים 0 כדי לא לחלק באפס.
def avg_weight(self):
total = 0
count = 0
for w in self.weight:
if w != 0: # רק חודשים שבהם הייתה ביקורת
total += w
count += 1
if count == 0:
return 0
return total / countבדיקה על הדוגמה: יש 7 מדידות (חודשים 1, 3, 4, 5, 7, 10, 12):
תשובה: הפעולה מחזירה את ממוצע המשקלים השונים מאפס; בדוגמה .
סעיף ג
סורקים מהסוף (מקום 11) אחורה עד למדידה הראשונה השונה מ-0 ומחזירים ; בדוגמה .
המדידה האחרונה היא המקום האחרון ברשימה שבו הערך שונה מ-0 (לא בהכרח מקום 11, כי ייתכן שהתינוק לא הגיע בחודש 12). לכן סורקים את הרשימה מהסוף להתחלה, ובמקום הראשון שבו יש מדידה מחשבים את המדד לפי ומחזירים אותו. לפי הנתון, בחודש שבו הייתה ביקורת נמדדו גם משקל וגם גובה, ולכן הגובה באותו מקום שונה מ-0 ואין חלוקה באפס. אם אין אף מדידה – מחזירים 0.
def get_last_Bmi(self):
for i in range(11, -1, -1): # מהחודש האחרון אחורה
if self.weight[i] != 0:
return self.weight[i] / (self.height[i] ** 2)
return 0בדיקה על הדוגמה: המדידה האחרונה היא בחודש 12 (מקום 11): , .
תשובה: הפעולה מחזירה של המדידה האחרונה; בדוגמה .
שאלה 5 · מעקב: העברת פרמטרים, ערכים מול רשימה
נתונות שתי הפעולות `what` ו-`where`:
def what(a, b):
print(a, b)
a = a + b
b = a - b
a = a - b
print(a, b)
def where(arr):
print(arr[0], arr[1])
arr[0] = arr[0] + arr[1]
arr[1] = arr[0] - arr[1]
arr[0] = arr[0] - arr[1]
print(arr[0], arr[1])עקבו בעזרת טבלת מעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט:
x=3
y=7
z=[3,7]
what(x, y)
where(z)
print("x,y:",x, y)
print("z:", z[0], z[1])הפעולה `where` השתנתה לפעולה הבאה:
def where(arr):
print(arr[0], arr[1])
what(arr[0], arr[1])
print(arr[0], arr[1])מה יהיה הפלט של קטע קוד מסעיף א' אחרי השינוי?
◂ פתרון מלא לשאלה 5
סעיף א
הפלט: `3 7`, `7 3`, `3 7`, `7 3`, `x,y: 3 7`, `z: 7 3` (כל אחד בשורה נפרדת).
רעיון: שתי הפעולות מחליפות בין שני ערכים בלי משתנה עזר: , אחר כך (שווה ל- המקורי), ואחר כך (שווה ל- המקורי). ההבדל ביניהן הוא מה משתנה מחוץ לפעולה:
•`what` מקבלת מספרים שלמים. ההשמות `a = ...`, `b = ...` משנות רק את המשתנים המקומיים של הפעולה, ולכן `x` ו-`y` של התוכנית לא משתנים.
•`where` מקבלת הפניה לרשימה `z` ומשנה את האיברים שלה (`arr[0] = ...`), ולכן השינוי נראה גם אחרי היציאה מהפעולה.
3 7
7 3
3 7
7 3
x,y: 3 7
z: 7 3תשובה: ההחלפה ב-`what` מקומית בלבד (`x,y: 3 7`), וההחלפה ב-`where` משנה את הרשימה עצמה (`z: 7 3`).
סעיף ב
הפלט: `3 7`, `7 3`, `3 7`, `3 7`, `7 3`, `3 7`, `x,y: 3 7`, `z: 3 7` (כל אחד בשורה נפרדת).
רעיון: עכשיו `where` לא משנה את איברי הרשימה בעצמה, אלא מעבירה ל-`what` את הערכים `arr[0]` ו-`arr[1]` (מספרים שלמים). `what` מחליפה רק את המשתנים המקומיים `a`, `b` שלה, ולכן הרשימה `z` נשארת `[3, 7]`.
3 7
7 3
3 7
3 7
7 3
3 7
x,y: 3 7
z: 3 7תשובה: הפעם גם `x`, `y` וגם `z` לא משתנים; השורות האחרונות הן `x,y: 3 7` ו-`z: 3 7`.
שאלה 6 · ניתוח פעולות על מחרוזות: הכלה וזוגות
נתונה הפעולה `secret()` הבאה המקבלת שתי מחרוזות:
def secret(s1, s2):
if s1 == s2:
return False
while len(s1) >0 and len(s2)>0 :
pos = s2.find(s1[0])
if pos == -1:
return False
s1 = s1[1:]
s2 = s2[0:pos]+s2[pos+1:]
return len(s1) == 0תנו דוגמה למחרוזת `s2` באורך של שישה תווים שעבורה הפעולה `secret("HELLO!", s2)` תחזיר ערך `True`.
נתונה הטענה הבאה:
אם זימון הפעולה `secret(s1, s2)` מחזיר ערך `True`, גם זימון הפעולה `secret(s2, s1)` יחזיר ערך `True`.
האם הטענה נכונה? הסבירו את תשובתכם.
מה מבצעת הפעולה `secret` באופן כללי?
נתונה הפעולה `mystery` המקבלת רשימה מחרוזות. הפעולה משתמשת בפעולה `secret`:
def mystery(arr):
for i in range(0, len(arr)-1, 2):
if not secret(arr[i], arr[i+1]):
return False
return Trueתנו דוגמה לרשימה `arr` של שש מחרוזות שעבורה הפעולה `mystery` תחזיר ערך `true`.
נתונה הטענה הבאה:
אם זימון הפעולה `mystery(arr)` מחזיר ערך `True`, הרשימה `arr` לא כוללת זוג מחרוזות זהות אשר נמצאות במקומות עוקבים. האם הטענה נכונה? הסבירו את תשובתכם.
מהי הסיבוכיות של הפעולה `mystery`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `s2 = "!HELLO"` (כל סידור אחר של התווים H, E, L, L, O, ! ששונה מ-"HELLO!").
הבנת הפעולה: בכל סיבוב הפעולה לוקחת את התו הראשון של `s1`, מחפשת אותו ב-`s2`; אם הוא לא נמצא – מחזירה `False`, ואם נמצא – מוחקת אותו מ-`s1` ומוחקת מופע אחד שלו מ-`s2`. בסוף מוחזר `True` רק אם כל התווים של `s1` "נמחקו", כלומר כל תו של `s1` נמצא ב-`s2` (כולל מספר החזרות). בנוסף, אם המחרוזות זהות מוחזר `False` כבר בהתחלה.
ל-"HELLO!" יש 6 תווים: H, E, L, L, O, !. כדי שכולם יימצאו ב-`s2` שאורכה 6, `s2` חייבת להכיל בדיוק את אותם תווים, כלומר להיות סידור מחדש שלהם – אבל לא בדיוק "HELLO!" (אחרת מוחזר `False` בשורה הראשונה).
`s1` התרוקנה, ולכן מוחזר `True`.
תשובה: `s2 = "!HELLO"`.
לא נכונה. דוגמה נגדית: `secret("AB", "ABC")` מחזיר `True`, אבל `secret("ABC", "AB")` מחזיר `False`.
ההסבר: `secret(s1, s2)` מחזירה `True` כשכל התווים של `s1` (עם החזרות) נמצאים ב-`s2` – אבל `s2` יכולה להכיל תווים נוספים. בכיוון ההפוך התווים הנוספים האלה לא יימצאו ב-`s1`, והפעולה תחזיר `False`.
דוגמה נגדית: `s1 = "AB"`, `s2 = "ABC"`.
1. `secret("AB", "ABC")`: 'A' נמצא (pos=0), נשאר `s1="B"`, `s2="BC"`; 'B' נמצא (pos=0), נשאר `s1=""` – מוחזר `True`.
2. `secret("ABC", "AB")`: 'A' ו-'B' נמחקים, נשאר `s1="C"`, `s2=""`; הלולאה נעצרת כי `s2` ריקה, ו-`len(s1)` הוא 1 – מוחזר `False`.
הטענה נכונה רק במקרה המיוחד שבו שתי המחרוזות באותו אורך (אז הן סידורים שונים של אותם תווים), אבל לא באופן כללי.
תשובה: הטענה אינה נכונה (דוגמה נגדית: "AB" ו-"ABC").
מחזירה `True` אם כל תווי `s1` (כולל מספר החזרות של כל תו) מופיעים ב-`s2` והמחרוזות אינן זהות; אחרת `False`.
1. אם המחרוזות זהות – מוחזר `False`.
2. אחרת, כל תו של `s1` "מתאים" למופע אחד שלו ב-`s2`, והמופע הזה נמחק מ-`s2` כדי שלא ישמש פעמיים. לכן תו שמופיע ב-`s1` פעמיים חייב להופיע ב-`s2` לפחות פעמיים.
3. אם תו כלשהו של `s1` לא נמצא – מוחזר `False`. אם כל התווים של `s1` נמצאו – `s1` מתרוקנת ומוחזר `True`.
כלומר הפעולה בודקת אם אפשר לבנות את `s1` מתווי `s2` (סדר התווים לא חשוב), בתנאי ש-`s1` שונה מ-`s2`. בפרט, אם יש לשתיהן אותו אורך, היא בודקת אם `s1` היא אנגרמה (סידור מחדש) של `s2` ששונה ממנה.
תשובה: `secret` מחזירה `True` אם ורק אם `s1 != s2` וכל תווי `s1`, עם החזרות, מוכלים בתווי `s2`.
סעיף ב
למשל `["AB", "BA", "CAT", "ACT", "X", "XY"]`.
ההסבר: הלולאה עוברת על (עבור 6 מחרוזות `range(0, 5, 2)`), כלומר בודקת את הזוגות (0,1), (2,3), (4,5). כדי שיוחזר `True`, בכל זוג `secret(arr[i], arr[i+1])` צריכה להחזיר `True`: המחרוזות בזוג שונות, וכל תווי הראשונה מוכלים בשנייה.
הדוגמה `["AB", "BA", "CAT", "ACT", "X", "XY"]`:
1. `secret("AB", "BA")` – אותם תווים, מחרוזות שונות: `True`.
2. `secret("CAT", "ACT")` – אותם תווים, מחרוזות שונות: `True`.
3. `secret("X", "XY")` – 'X' מוכל ב-"XY": `True`.
שלושת הזוגות עוברים, ולכן `mystery` מחזירה `True`.
תשובה: `arr = ["AB", "BA", "CAT", "ACT", "X", "XY"]`.
לא נכונה. למשל `["AB", "BA", "BA", "AB"]`: `mystery` מחזירה `True`, אבל במקומות 1 ו-2 יש שתי מחרוזות זהות.
ההסבר: `mystery` לא בודקת כל שני מקומות עוקבים, אלא רק את הזוגות (0,1), (2,3), (4,5), ... – הלולאה מתקדמת בקפיצות של 2. בתוך זוג כזה אכן אי אפשר שיהיו מחרוזות זהות (`secret` מחזירה `False` למחרוזות זהות). אבל זוגות עוקבים "בין זוגות", כמו מקומות 1 ו-2, לא נבדקים כלל.
דוגמה נגדית: `arr = ["AB", "BA", "BA", "AB"]`
1. : `secret("AB", "BA")` – `True`.
2. : `secret("BA", "AB")` – `True`.
3. מוחזר `True`, אף על פי ש-`arr[1]` ו-`arr[2]` הן שתיהן "BA" – מחרוזות זהות במקומות עוקבים.
תשובה: הטענה אינה נכונה – רק המקומות עבור זוגי נבדקים.
, כאשר מספר המחרוזות ו- האורך המרבי של מחרוזת; אם אורך המחרוזות חסום בקבוע – .
ההסבר: נסמן ב- את מספר המחרוזות ברשימה וב- את האורך המרבי של מחרוזת.
1. `mystery` מבצעת לכל היותר קריאות ל-`secret` (פעם אחת לכל זוג), כלומר קריאות.
2. בכל קריאה ל-`secret` הלולאה רצה לכל היותר סיבובים (בכל סיבוב נמחק תו מ-`s1`). בכל סיבוב יש חיפוש `find` ב-`s2` וגם יצירת מחרוזות חדשות בחיתוך (`s1[1:]` ו-`s2[0:pos]+s2[pos+1:]`) – כל אחת מהפעולות האלה עולה . לכן קריאה אחת ל-`secret` עולה .
3. בסך הכול: .
אם מתייחסים לאורך המחרוזות כקבוע (מחרוזות קצרות), הסיבוכיות היא – לינארית במספר המחרוזות.
תשובה: ; עבור מחרוזות באורך חסום – .
שאלה 7 · מחלקת ספר: פעולה, מעקב והשלמת קוד
נתונה המחלקה `Book` שיש לה שלוש תכונות:
•קוד ספר – `code`, מטיפוס שלם, `int`
•שנת הוצאה – `year`, מטיפוס שלם, `int`
•האם כתוב בעברית – `isHebrew`, מטיפוס בוליאני, `bool`
במחלקה הוגדרה פעולה הבונה (בנאי, `constructor`)
def __init__(self, code, year, is_hebrew):
self.code = code
self.year = year
self.is_hebrew = is_hebrewכתבו פעולה המקבלת מספר שלם וחיובי `year1` המציין שנה ובודקת אם עברו יותר מעשר שנים משנת ההוצאה עד לשנה `year1` (כולל). אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
old_book(self, year1)עקבו בעזרת טבלת המעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט.
b1 = Book(1122, 1998, False)
b2 = Book(2233, 2010, True)
# (*) כאן יש להוסיף פקודה/פקודות בסעיף ג'
if b1.old_book(2014) and not b1.is_hebrew:
print("###")
else:
print("***")
if b2.old_book(2015):
print("!!!")
else:
if b2.is_hebrew:
print("???")נא השלימו קוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה `*` בלבד.
◂ פתרון מלא לשאלה 7
סעיף א
`return year1 - self.year >= 10` (מספר השנים משנת ההוצאה עד `year1` כולל, , גדול מ-10).
סופרים את השנים משנת ההוצאה `self.year` עד השנה `year1` כולל שתיהן: מספרן הוא . הספר "ישן" אם מספר זה גדול מ-10:
לדוגמה, ספר משנת 2000: עבור נספרות השנים 2000 עד 2010, כלומר – מוחזר `True`; עבור נספרות שנים בלבד – מוחזר `False`.
def old_book(self, year1):
return year1 - self.year >= 10תשובה: הפעולה מחזירה `True` אם , כלומר אם , ואחרת `False`.
סעיף ב
הפלט: `###` ואחריו `???`.
1. הספר `b1` יצא ב-1998, ועד 2014 עברו 16 שנים – הוא ישן. הוא לא בעברית, ולכן התנאי כולו מתקיים ומודפס `###`.
2. הספר `b2` יצא ב-2010, ועד 2015 עברו 5 שנים – הוא לא ישן, ולכן עוברים ל-`else`. הוא בעברית, ולכן מודפס `???`.
(התוצאה אינה תלויה בפרשנות של "כולל" בסעיף א: 16 שנים בבירור יותר מעשר, ו-5 או 6 שנים בבירור לא.)
###
???תשובה: `###` ואחריו `???`.
סעיף ג
למשל: `b1.is_hebrew = True` ו-`b2.is_hebrew = False`.
1. כדי שיודפס `*`, התנאי הראשון צריך להיות שקרי. הדרך הפשוטה: להפוך את `b1` לספר בעברית, ואז `not b1.is_hebrew` שקרי וכל ה-`and` שקרי.
2. כדי שלא יודפס דבר בחלק השני, צריך גם ש-`b2.old_book(2015)` יהיה שקרי (כך הוא כבר: 5 שנים בלבד), וגם ש-`b2.is_hebrew` יהיה שקרי, כדי שלא יודפס `???`. לכן הופכים את `b2` לספר שאינו בעברית.
b1.is_hebrew = True
b2.is_hebrew = False•`b1.old_book(2014)` הוא `True`, אבל `not b1.is_hebrew` הוא `False`, ולכן מודפס `*`.
•`b2.old_book(2015)` הוא `False`; ב-`else` הערך `b2.is_hebrew` הוא `False`, ולכן לא מודפס דבר.
הפלט הוא `*` בלבד.
תשובה: `b1.is_hebrew = True` ו-`b2.is_hebrew = False`.
שאלה 8 · מספרים אחים: מספר ספרות וסכום ספרות
שני מספרים שלמים וחיוביים נקראים "אחים" אם יש להם מספר ספרות זהה וסכום הספרות גם הוא זהה.
כתבו פעולה המקבלת שני מספרים שלמים וחיוביים. הפעולה תבדוק אם הם "אחים".
אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_it_brothers(num1, num2)רשימה של מספרים שלמים וחיוביים נקראת "רשימת אחים" אם כל איברי הרשימה "אחים" זה לזה.
כתבו פעולה המקבלת רשימה מספרים שלמים וחיוביים ובודקת אם היא "רשימת אחים".
אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_it_brothers(arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים א'-ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
מחשבים לכל מספר את מספר הספרות ואת סכום הספרות (בעזרת `% 10` ו-`// 10`) ומחזירים `True` אם שני הנתונים שווים.
1. פעולת עזר `count_digits` סופרת ספרות: כל עוד המספר חיובי, מוחקים ממנו ספרה (`num //= 10`) ומגדילים מונה.
2. פעולת עזר `sum_digits` סוכמת ספרות: מוסיפים לסכום את ספרת האחדות (`num % 10`) ומוחקים אותה.
3. המספרים "אחים" אם מספר הספרות שלהם שווה וגם סכום הספרות שלהם שווה.
לדוגמה: 123 ו-321 – לשניהם 3 ספרות וסכום ספרות 6, ולכן הם אחים. 123 ו-60 – סכום ספרות 6 לשניהם, אבל מספר הספרות שונה (3 מול 2), ולכן הם לא אחים.
def count_digits(num): # מספר הספרות
count = 0
while num > 0:
count += 1
num //= 10
return count
def sum_digits(num): # סכום הספרות
total = 0
while num > 0:
total += num % 10
num //= 10
return totaldef is_it_brothers(num1, num2):
return (count_digits(num1) == count_digits(num2) and
sum_digits(num1) == sum_digits(num2))תשובה: הפעולה מחזירה `True` אם ורק אם למספרים אותו מספר ספרות ואותו סכום ספרות.
סעיף ב
משווים כל איבר לאיבר הראשון: אם לכולם אותו מספר ספרות ואותו סכום ספרות כמו `arr[0]` מוחזר `True`, אחרת `False`.
היחס "אחים" הוא השוואה של שני מאפיינים (מספר ספרות וסכום ספרות). אם כל איבר "אח" של האיבר הראשון, אז לכל האיברים אותם שני מאפיינים, ולכן כל שניים מהם אחים זה לזה. לכן לא צריך לבדוק את כל הזוגות – מספיק להשוות כל איבר ל-`arr[0]`.
1. מחשבים פעם אחת את מספר הספרות וסכום הספרות של `arr[0]`.
2. עוברים על כל האיברים; אם לאחד מהם מאפיין שונה – מחזירים `False` מיד.
3. אם הלולאה הסתיימה – מחזירים `True`. רשימה ריקה או רשימה עם איבר אחד היא "רשימת אחים" (אין זוג שמפר את התנאי).
ב-Python אין העמסה של פעולות: אם שתי פעולות באותו קובץ נקראות `is_it_brothers`, ההגדרה השנייה מחליפה את הראשונה. לכן הפעולה כאן לא קוראת לפעולה מסעיף א, אלא משתמשת ישירות בפעולות העזר `count_digits` ו-`sum_digits` מסעיף א.
def is_it_brothers(arr):
if len(arr) == 0:
return True
digits = count_digits(arr[0])
total = sum_digits(arr[0])
for num in arr:
if count_digits(num) != digits or sum_digits(num) != total:
return False
return Trueלדוגמה: `[123, 321, 222, 600, 141]` – לכולם 3 ספרות וסכום ספרות 6, מוחזר `True`. `[123, 321, 33]` – ל-33 יש 2 ספרות, מוחזר `False`.
תשובה: הפעולה מחזירה `True` אם לכל איברי הרשימה אותו מספר ספרות ואותו סכום ספרות כמו לאיבר הראשון.
סעיף ג
סעיף א: , כאשר מספר הספרות (כלומר ). סעיף ב: , ובמספרים בגודל חסום – .
נסמן ב- את מספר הספרות המרבי של מספר (עבור מספר מתקיים ), וב- את מספר האיברים ברשימה.
1. סעיף א: `count_digits` ו-`sum_digits` מבצעות סיבוב אחד לכל ספרה, כלומר כל אחת. `is_it_brothers(num1, num2)` קוראת לכל אחת מהן פעמיים, ולכן הסיבוכיות היא .
2. סעיף ב: הלולאה עוברת פעם אחת על האיברים, ולכל איבר מחשבים מספר ספרות וסכום ספרות ב-. לכן הסיבוכיות היא . מכיוון שמשווים רק לאיבר הראשון (ולא כל זוג לכל זוג, שהיה עולה ), הפעולה לינארית במספר האיברים. כשגודל המספרים חסום (מספר ספרות קבוע), הסיבוכיות היא .
תשובה: סעיף א – (קבוע עבור מספרים בגודל חסום); סעיף ב – , כלומר .
שאלה 9 · מחלקות תאריך ועובד: השוואה וחיפוש
המחלקה `Date` מייצגת תאריך. תכונות המחלקה:
•`day` – מייצגת את היום (שלמים בין 1 ל-31)
•`month` – מייצגת את החודש (שלמים בין 1 ל-12)
•`year` – מייצגת את השנה (שלמים חיוביים בני ארבע ספרות)
class Date:
def __init__(self, day, month, year):
self.day = day
self.month = month
self.year = yearכתבו פעולה המקבלת כפרמטר תאריך מסוים ובודקת אם התאריך הנוכחי (התאריך שמיוצג באמצעות האובייקט שמפעיל את הפעולה, `this`), מאוחר מהתאריך `other` שהתקבל כפרמטר. אם כן - הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
after(self, other)המחלקה `Worker` מייצגת עובד בחברה. למחלקה שתי תכונות:
•`name` – שם העובד, מטיפוס מחרוזת, `str`
•`birthday` – יום הולדת, מטיפוס `Date`
כתבו פעולה בונה
__init__(self, name, day, month, year)בחברת "חג לעובדים" נהוג לשלוח ברכה ומתנה לכל עובד לכבוד יום ההולדת שלו. לשם כך, מזכירת החברה מדפיסה בתחילת כל חודש את שמות העובדים שיום ההולדת שלהם חל באותו החודש.
כתבו פעולה המקבלת רשימת עובדי החברה `arr` ומספר שלם `month` המציין מספר חודש ומדפיסה את שמות העובדים שאמורים לקבל מתנה.
כותרת הפעולה:
print_by_month(arr, month)כתבו פעולה המקבלת רשימת עובדי החברה ומחזירה שם העובד הצעיר ביותר.
כותרת הפעולה:
youngest(arr)◂ פתרון מלא לשאלה 9
סעיף א
משווים קודם את השנה, אם שוות – את החודש, ואם גם הם שווים – את היום; מוחזר `True` רק אם `self` גדול ב"רכיב הראשון שבו יש הבדל".
השוואת תאריכים היא השוואה "מילונית": השנה חשובה יותר מהחודש, והחודש חשוב יותר מהיום.
1. אם השנים שונות – התאריך מאוחר יותר אם השנה שלו גדולה יותר (החודש והיום כבר לא משנים).
2. אם השנים שוות והחודשים שונים – מכריע החודש.
3. אם גם החודשים שווים – מכריע היום. אם גם הימים שווים, התאריכים זהים, והתאריך הנוכחי אינו מאוחר יותר, ולכן מוחזר `False` (כי `>` ולא `>=`).
לדוגמה: 5/3/2000 מאוחר מ-28/12/1999 (השנה מכריעה), ו-1/4/2000 מאוחר מ-30/3/2000 (החודש מכריע).
def after(self, other):
if self.year != other.year:
return self.year > other.year
if self.month != other.month:
return self.month > other.month
return self.day > other.dayתשובה: הפעולה `after` שלמעלה – משווה שנה, אחר כך חודש, אחר כך יום, ומחזירה `True` אם התאריך הנוכחי מאוחר מ-`other`.
סעיף ב
`self.name = name` ו-`self.birthday = Date(day, month, year)`.
הבנאי מקבל את היום, החודש והשנה כמספרים נפרדים, אבל התכונה `birthday` היא מטיפוס `Date`. לכן יוצרים בתוך הבנאי עצם חדש מסוג `Date` משלושת המספרים ושומרים אותו בתכונה.
class Worker:
def __init__(self, name, day, month, year):
self.name = name
self.birthday = Date(day, month, year)תשובה: הבנאי שומר את השם ויוצר `Date(day, month, year)` לתכונה `birthday`.
סעיף ג
עוברים על כל העובדים ומדפיסים את `w.name` של כל עובד שמתקיים אצלו `w.birthday.month == month`.
עובר על כל עובד ברשימה. החודש של יום ההולדת שלו נמצא בתכונה `month` של העצם `birthday` שלו, כלומר `w.birthday.month`. אם הוא שווה לחודש שהתקבל – מדפיסים את שם העובד. זו פעולה חיצונית למחלקות (אין לה `self`).
def print_by_month(arr, month):
for w in arr:
if w.birthday.month == month:
print(w.name)לדוגמה, עבור העובדים Dan (5/3/1990), Rina (17/8/1995), Avi (30/3/1995) והחודש 3 יודפסו Dan ו-Avi.
סיבוכיות: עבור עובדים.
תשובה: הפעולה מדפיסה את שמות כל העובדים שחודש יום ההולדת שלהם שווה ל-`month`.
סעיף ד
מחפשים מקסימום לפי תאריך הלידה: העובד הצעיר ביותר הוא זה שתאריך הלידה שלו המאוחר ביותר (בעזרת `after` מסעיף א), ומחזירים את שמו.
העובד הצעיר ביותר הוא זה שנולד אחרון, כלומר שתאריך הלידה שלו מאוחר מתאריכי הלידה של כל האחרים. זה חיפוש מקסימום רגיל, כשההשוואה נעשית בפעולה `after` מסעיף א:
1. מניחים שהעובד הראשון הוא הצעיר ביותר.
2. עוברים על כל העובדים; אם תאריך הלידה של עובד מאוחר מתאריך הלידה של הצעיר הנוכחי – הוא הופך לצעיר הנוכחי.
3. בסוף מחזירים את השם של הצעיר ביותר (לא את העצם).
def youngest(arr):
young = arr[0]
for w in arr:
if w.birthday.after(young.birthday):
young = w
return young.nameלדוגמה, עבור Dan (5/3/1990), Rina (17/8/1995), Avi (30/3/1995), Noa (2/8/1995) מוחזר "Rina": היא נולדה ב-1995 כמו Avi ו-Noa, באוגוסט כמו Noa, וב-17 לחודש – אחרי ה-2.
סיבוכיות: .
תשובה: הפעולה מחזירה את שם העובד שתאריך הלידה שלו מאוחר מכולם.
שאלה 10 · חיפוש מאינדקס ובדיקת תת-סדרה
נתונה הפעולות `why` הבאה:
def why(a, x, k):
for i in range(k, len(a)):
if a[i] == x:
return i
return -1תנו דוגמה של רשימת מספרים שלמים `arr` שעבורו זימון הפעולה `why(arr, 5, 3)` יחזיר ערך 5 וזימון הפעולה `why(arr, 3, 5)` יחזיר ערך (-1).
מה מבצעת הפעולה `why` באופן כללי?
נתונה הפעולה `where` הבאה:
def where(a, b):
k = -1
for i in range(0, len(b)):
k = why(a, b[i], k+1)
if k == -1:
return False
return Trueנתונות שתי הרשימות הבאות:
a = [2,4,9,0,2,3]
b = [2,4,0,9,3]מהי תוצאת הזימון `where(a, b)`?
נתונה הפעולה `what` הבאה
def what(a, b):
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1
else:
i += 1
return j == len(b)האם הפעולה `what` שקולה (מבצעת בדיוק אותו הדבר) לפעולה `where`? אם כן – הסבירו מה מבצעות שתי הפעולות באופן כללי, ולא – תנו דוגמה של שתי הרשימות `a` ו-`b` שעבורן תוצאות הזימונים `what(a, b)` ו-`where(a, b)` יהיו שונות.
◂ פתרון מלא לשאלה 10
סעיף א
למשל `arr = [1, 2, 3, 4, 6, 5]`.
הבנת הפעולה: `why(a, x, k)` מחפשת את הערך `x` ברשימה, החל מהאינדקס `k` והלאה, ומחזירה את האינדקס של המופע הראשון שלו; אם אין מופע כזה – מוחזר .
1. `why(arr, 5, 3)` מחזירה 5: החיפוש מתחיל באינדקס 3, ולכן `arr[3]` ו-`arr[4]` אינם 5, ו-`arr[5]` הוא 5.
2. `why(arr, 3, 5)` מחזירה : אין 3 באינדקסים 5 והלאה. (מותר שיהיה 3 לפני אינדקס 5.)
הדוגמה `arr = [1, 2, 3, 4, 6, 5]`:
•`why(arr, 5, 3)`: בודקים `arr[3]=4`, `arr[4]=6`, `arr[5]=5` – מוחזר 5.
•`why(arr, 3, 5)`: בודקים רק את `arr[5]=5`, שאינו 3 – מוחזר (ה-3 שבאינדקס 2 לא נבדק).
תשובה: `arr = [1, 2, 3, 4, 6, 5]`.
מחזירה את האינדקס הראשון שבו `a[i] == x`, ואם אין כזה – .
ההסבר: הלולאה עוברת על האינדקסים מ-`k` עד סוף הרשימה לפי הסדר. ברגע שנמצא איבר ששווה ל-`x`, מוחזר האינדקס שלו (ולכן זה המופע הראשון מ-`k` והלאה). אם הלולאה הסתיימה בלי למצוא, מוחזר . אם `len(a)` הלולאה לא רצה כלל ומוחזר .
תשובה: `why` מחפשת את `x` ברשימה `a` החל מהמקום `k`, ומחזירה את מקום המופע הראשון שלו (או אם הוא לא מופיע מ-`k` והלאה).
סעיף ב
`False` (האיבר 9 של `b` לא נמצא ב-`a` אחרי המקום 3).
רעיון: `where` מחפשת את איברי `b` ב-`a` לפי הסדר: כל איבר מחפשים רק אחרי המקום שבו נמצא האיבר הקודם (`k+1`). אם איבר לא נמצא – מוחזר `False`.
טבלת מעקב (`a = [2,4,9,0,2,3]`, `b = [2,4,0,9,3]`):
בשלב מחפשים את 9 באינדקסים 4 ו-5 של `a` (הערכים 2 ו-3), ואין שם 9. ה-9 שב-`a` נמצא במקום 2, לפני ה-0 שנמצא במקום 3 – כלומר הסדר ב-`a` שונה מהסדר ב-`b`.
תשובה: `where(a, b)` מחזירה `False`.
סעיף ג
כן, הן שקולות: שתיהן מחזירות `True` אם ורק אם `b` היא תת-סדרה של `a` (כל איברי `b` מופיעים ב-`a` באותו סדר, לא בהכרח ברצף).
מה מבצעת `where`: היא מוצאת את `b[0]` ב-`a`, אחר כך את `b[1]` אחרי המקום שנמצא, וכן הלאה. היא מחזירה `True` אם כל איברי `b` נמצאו ב-`a` באותו סדר, כלומר אם `b` היא תת-סדרה של `a` (האיברים לא חייבים להיות צמודים).
מה מבצעת `what`: `i` רץ על `a` ו-`j` מצביע על האיבר הבא של `b` שעדיין לא נמצא. בכל צעד `i` מתקדם; אם `a[i]` שווה ל-`b[j]`, נמצא האיבר `b[j]` ו-`j` מתקדם לאיבר הבא של `b`. בסוף מוחזר `True` אם `j` הגיע לסוף `b`, כלומר כל איברי `b` נמצאו לפי הסדר.
למה הן שקולות: שתיהן משתמשות באותה שיטה "חמדנית": כל איבר של `b` מותאם למופע הראשון שלו ב-`a` אחרי המקום של האיבר הקודם. ב-`where` זה נעשה בקריאה `why(a, b[i], k+1)`, וב-`what` זה נעשה בהתקדמות של `i` עד שנמצא `a[i] == b[j]`. בחירה במופע המוקדם ביותר משאירה את מירב המקום לאיברים הבאים, ולכן שתי הפעולות מחזירות `True` בדיוק כש-`b` היא תת-סדרה של `a`. גם המקרים הקיצוניים זהים: אם `b` ריקה שתיהן מחזירות `True`, ואם `b` לא ריקה ו-`a` ריקה שתיהן מחזירות `False`.
לדוגמה, עבור הרשימות מסעיף ב: `what` מוצאת את 2 (מקום 0), 4 (מקום 1), 0 (מקום 3), ואז מחפשת 9 במקומות 4–5, לא מוצאת, `i` מגיע לסוף ו- – מוחזר `False`, כמו ב-`where`.
תשובה: כן, `what` שקולה ל-`where`; שתיהן בודקות אם `b` היא תת-סדרה של `a` (איברי `b` מופיעים ב-`a` באותו סדר).
שאלה 11 · לוח שנה 2024: מספר ימים ויום בשבוע
נתונה המחלקה `Calendar2024` המתארת לוח שנה 2024.
למחלקה תכונה אחת `days` שהיא רשימת מספרים שלמים בגודל 12 אשר כל אחד מציין מספר הימים בחודש המתאים למיקומו ברשימה.
•איבר במקום 0 (הראשון ברשימה) יהיה 31 כי בחודש ינואר (החודש הראשון בשנה) יש 31 ימים.
•איבר במקום 1 (השני ברשימה) יהיה רשום 29 כי בחודש פברואר (החודש השני בשנה) יש 29 ימים.
•איבר במקום 2 (השלישי ברשימה ) יהיה רשום 31 כי בחודש מארס יש 31 ימים וכו'.
כתבו במחלקה `Calendar2024` פעולה המקבלת כפרמטרים שני מספרים שלמים. הראשון מציין יום בחודש, השני מציין את מספר החודש (יחד מספרים אלו מציינים תאריך).
הפעולה תחשב ותחזיר את מספר הימים שעברו מתחילת השנה (1 בינואר) ועד התאריך שהתקבל.
לדוגמה:
עבור התאריך: 22,1 (22/1) יוחזר המספר: 21
עבור התאריך: 22,3 (22/3) יוחזר המספר: 81 (31+29+21)
עבור התאריך: 1,5 (1/5) יוחזר המספר: 121 (31+29+31+30)
כותרת הפעולה:
num_of_days(self, day, month)יום 1/1 (היום הראשון של השנה) חל בשנה 2024 על יום ב' (יום שני, יום מספר 2 בשבוע).
כתבו פעולה המקבלת כפרמטרים שני מספרים שלמים. הראשון מציין יום בחודש, השני מציין את מספר החודש (יחד מספרים אלו מציינים תאריך). הפעולה תחשב ותחזיר את מספר היום בשבוע שבו הוא חל.
לדוגמה:
עבור יום 1/1 יש להחזיר 2
עבור יום 8/1 יש להחזיר 2
עבור יום 1/2 יש להחזיר 5
עבור יום 22/3 יש להחזיר 6
כותרת הפעולה:
weekday(self, day, month)הערה: אפשר להשתמש בפעולה של סעיף א' גם אם לא כתבתם אותה
כתבו במחלקה `Calendar2024` פעולה המדפיסה יום בשבוע עבור כל יום ראשון וכל יום אחרון של 12 חודשי השנה 2024.
כותרת הפעולה:
print_first_last(self)הערה: אפשר להשתמש בפעולות של סעיפים א' ו-ב' גם אם לא כתבתם אותן
◂ פתרון מלא לשאלה 11
סעיף א
סכום הימים בחודשים ועוד ; למשל 22/3 נותן .
מהדוגמאות רואים שסופרים את הימים שעברו מ-1 בינואר, כלומר ההפרש בין התאריכים: עבור 1/1 מוחזר 0, ועבור 22/1 מוחזר .
1. כל החודשים שלפני החודש `month` עברו במלואם: אלה האיברים במקומות ברשימה `days`, ולכן סוכמים `days[i]` עבור `i` ב-`range(month - 1)`.
2. בחודש `month` עצמו עברו ימים.
3. התוצאה: הסכום ועוד .
- 22/1: אין חודשים קודמים, .
- 22/3: .
- 1/5: .
class Calendar2024:
def __init__(self):
self.days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] def num_of_days(self, day, month):
total = 0
for i in range(month - 1): # החודשים שעברו במלואם
total += self.days[i]
return total + day - 1תשובה: `num_of_days` מחזירה את סכום הימים בחודשים שלפני `month` ועוד (בדוגמאות: 21, 81, 121).
סעיף ב
`return (self.num_of_days(day, month) + 1) % 7 + 1` (יום ראשון = 1, ..., שבת = 7).
ימי השבוע חוזרים כל 7 ימים. מספרי הימים הם 1 (ראשון) עד 7 (שבת), ו-1/1/2024 הוא יום 2.
1. נסמן = `num_of_days(day, month)` – מספר הימים שעברו מ-1/1. אחרי ימים מתקדמים צעדים במחזור של 7.
2. נעבור לספירה מ-0: יום 2 הוא "1" (ראשון = 0, שני = 1, ...). אחרי ימים הערך הוא .
3. נחזור לספירה מ-1 על ידי הוספת 1: .
- 1/1: , .
- 8/1: , .
- 1/2: , .
- 22/3: , .
כל התוצאות מתאימות לדוגמאות.
def weekday(self, day, month):
return (self.num_of_days(day, month) + 1) % 7 + 1תשובה: `weekday` מחזירה , כאשר הוא מספר הימים מסעיף א (בדוגמאות: 2, 2, 5, 6).
סעיף ג
לולאה על החודשים 1–12: מדפיסים את `weekday(1, m)` ואת `weekday(self.days[m-1], m)`.
לכל חודש מ-1 עד 12:
1. היום הראשון בחודש הוא 1, והיום בשבוע שלו הוא `weekday(1, m)`.
2. היום האחרון בחודש הוא מספר הימים בחודש, `self.days[m - 1]` (חודש שמור במקום ), והיום בשבוע שלו הוא `weekday(self.days[m - 1], m)`.
3. מדפיסים בשורה אחת את מספר החודש ואת שני הימים בשבוע.
def print_first_last(self):
for m in range(1, 13):
first = self.weekday(1, m)
last = self.weekday(self.days[m - 1], m)
print(m, first, last)הפלט שמתקבל (חודש, יום בשבוע של היום הראשון, יום בשבוע של היום האחרון):
לדוגמה, 31/1: , (יום רביעי); 1/2: , יום 5 (חמישי), כלומר היום שאחרי – כצפוי.
תשובה: `print_first_last` מדפיסה לכל חודש את `weekday(1, m)` ואת `weekday(days[m-1], m)` (למשל ינואר: 2 ו-4).
שאלה 12 · מערכת בנק: חשבונות, סניפים והעברת לקוח
מערכת מחשוב של בנק "SimpleBank" כוללת שתי מחלקות הבאות: `Account` ו-`Branch`.
למחלקה `Account` (חשבון) ארבע תכונות:
•מספר חשבון – `num`, מטיפוס מספר שלם, `int`
•מספר תעודת הזהות של הלקוח – `id_num`, מטיפוס מחרוזת, `str`
•היתרה בחשבון – `balance`, מטיפוס מספר ממשי, `float`
•מצב החשבון – `is_active`, מטיפוס `bool` (`True` – חשבון פעיל, ו-`False` – חשבון לא פעיל)
בעת פתיחת חשבון, הלקוח מקבל מתנה 100 ₪ ליתרת חשבון.
למחלקה `Branch` (סניף) תכונות הבאות:
•מספר סניף – `branch_num`, מטיפוס שלם, `int`
•רשימת חשבונות – `accounts` – רשימה הפניות לעצמים מסוג `Account`
•מספר החשבונות המקסימלי שאותם הסניף רשאי לפתוח – `max_accounts`, מטיפוס מספר שלם, `int`
בעת פתיחת סניף חדש יש ליצור רשימה ריקה ללא חשבונות בפועל.
כתבו במחלקות `Account` ו-`Branch` פעולות בונות (`constructors`).
במחלקה `Account`:
__init__(self, num, id_num)במחלקה `Branch`:
__init__(self, branch_num, max_accounts)במחלקה `Branch` קיימת פעולה פנימית ליצירת מספר חשבון, המבטיחה שמספר חשבון יהיה ייחודי בסניף. אפשר להשתמש בפעולה זו ולא צריך לממש אותה.
כותרת הפעולה:
generate_num(self)כדי למשוך לקוחות חדשים החליטה הנהלת הבנק על המבצע הבא: כל לקוח חדש (זה שאין לו חשבון בסניף) מקבל מתנה של 500 ₪ בעת פתיחת חשבון (אם ללקוח יש כבר חשבון הוא מקבל מתנה "רגילה" של 100 ₪).
כתבו במחלקה `Branch` פעולה להוספת חשבון חדש:
add_account(self, id_num)כאשר לקוח רוצה לעבור לסניף הנוכחי (`this`) מסניף אחר `other`, כל החשבונות שלו בסניף הקודם נסגרים (הופכים להיות "לא פעילים") ובסניף חדש (`this`) נפתח חשבון חדש עם יתרה השווה לסכום היתרות שהיו לו בסניף הקודם. אין צורך במחיקה חשבונות שנסגרו
כתבו פעולה המבצעת מעבר לקוח מסניף לסניף. כותרת הפעולה:
move_client(id_num, other)שימו לב: לקוח העובר מסניף לסניף הוא לא לקוח חדש ולא מגיעה לו מתנה (גם לא מתנה רגילה).
אפשר להניח שבסניף יש מקום לחשבון חדש.
◂ פתרון מלא לשאלה 12
סעיף א
`Account`: מספר ות"ז מהפרמטרים, `balance = 100`, `is_active = True`. `Branch`: מספר הסניף והמקסימום מהפרמטרים, `accounts = []`.
1. בבנאי של `Account` מקבלים את מספר החשבון ואת מספר תעודת הזהות. היתרה ההתחלתית היא 100 ₪ – המתנה שכל לקוח מקבל בפתיחת חשבון – וחשבון חדש הוא פעיל.
2. בבנאי של `Branch` מקבלים את מספר הסניף ואת המספר המרבי של חשבונות, ורשימת החשבונות מתחילה ריקה (סניף חדש עדיין בלי חשבונות).
class Account:
def __init__(self, num, id_num):
self.num = num
self.id_num = id_num
self.balance = 100.0 # מתנה בפתיחת חשבון
self.is_active = Trueclass Branch:
def __init__(self, branch_num, max_accounts):
self.branch_num = branch_num
self.max_accounts = max_accounts
self.accounts = [] # סניף חדש – בלי חשבונותתשובה: שני הבנאים שלמעלה – חשבון חדש נפתח עם יתרה 100 ומצב פעיל, וסניף חדש נפתח עם רשימת חשבונות ריקה.
סעיף ב
אם הסניף מלא (`len(accounts) >= max_accounts`) מוחזר `False`; אחרת יוצרים `Account(self.generate_num(), id_num)`, ואם אין בסניף חשבון עם אותה ת"ז קובעים יתרה 500; מוסיפים לרשימה ומחזירים `True`.
1. בדיקת מקום: אם מספר החשבונות בסניף כבר הגיע ל-`max_accounts`, אי אפשר לפתוח חשבון נוסף, ומחזירים `False`.
2. האם הלקוח חדש: עוברים על רשימת החשבונות של הסניף ובודקים אם יש בה חשבון עם אותו מספר תעודת זהות. אם אין – הלקוח חדש.
3. יצירת החשבון: מספר החשבון נוצר בפעולה הקיימת `generate_num()`. הבנאי כבר נותן יתרה של 100 ₪ (המתנה הרגילה); ללקוח חדש משנים את היתרה ל-500 ₪.
4. מוסיפים את החשבון לרשימה ומחזירים `True`.
def add_account(self, id_num):
if len(self.accounts) >= self.max_accounts:
return False # אין מקום בסניף
is_new = True
for acc in self.accounts:
if acc.id_num == id_num:
is_new = False # ללקוח כבר יש חשבון
new_acc = Account(self.generate_num(), id_num)
if is_new:
new_acc.balance = 500.0 # מתנה ללקוח חדש
self.accounts.append(new_acc)
return Trueלדוגמה, בסניף עם `max_accounts = 3`: פתיחה ראשונה ללקוח "111" – יתרה 500; פתיחה שנייה ל-"111" – יתרה 100; פתיחה ל-"222" – יתרה 500; פתיחה רביעית – מוחזר `False`.
תשובה: הפעולה `add_account` שלמעלה – מחזירה `False` כשהסניף מלא, ואחרת פותחת חשבון (500 ₪ ללקוח חדש, 100 ₪ ללקוח קיים) ומחזירה `True`.
סעיף ג
עוברים על חשבונות `other`: לכל חשבון פעיל של הלקוח מוסיפים את היתרה לסכום וקובעים `is_active = False`; אחר כך פותחים ב-`self` חשבון חדש (`generate_num`) שיתרתו בדיוק הסכום (בלי מתנה) ומוסיפים לרשימה.
הפעולה שייכת למחלקה `Branch` ומופעלת על הסניף החדש (`self`), כלומר ב-Python הכותרת היא `move_client(self, id_num, other)`.
1. סגירת החשבונות בסניף הקודם: עוברים על `other.accounts`. לכל חשבון פעיל של הלקוח (אותו `id_num`) מוסיפים את היתרה שלו לסכום `total` והופכים אותו ללא פעיל. לא מוחקים את החשבון מהרשימה.
2. אם ללקוח לא היה אף חשבון פעיל ב-`other`, אין מה להעביר, ומחזירים `False`.
3. פתיחת חשבון בסניף החדש: יוצרים חשבון עם מספר מ-`generate_num()`. הבנאי נותן 100 ₪, אבל ללקוח שעובר סניף לא מגיעה מתנה, ולכן דורסים את היתרה בסכום היתרות `total`. לא בודקים מקום, כי לפי הנתון יש מקום בסניף.
4. מוסיפים את החשבון לרשימה של `self` ומחזירים `True` (סימון שהמעבר בוצע).
def move_client(self, id_num, other):
total = 0
found = False
for acc in other.accounts:
if acc.id_num == id_num and acc.is_active:
total += acc.balance
acc.is_active = False # סגירת החשבון בסניף הקודם
found = True
if not found:
return False
new_acc = Account(self.generate_num(), id_num)
new_acc.balance = total # בלי מתנה
self.accounts.append(new_acc)
return Trueלדוגמה: ללקוח "111" יש ב-`other` שני חשבונות פעילים עם יתרות 700 ו-100. אחרי `b2.move_client("111", b1)` שני החשבונות ב-`b1` לא פעילים, וב-`b2` נפתח חשבון אחד עם יתרה ₪.
תשובה: הפעולה `move_client` שלמעלה – סוגרת את כל החשבונות הפעילים של הלקוח ב-`other`, סוכמת את יתרותיהם ופותחת ב-`self` חשבון אחד עם הסכום, בלי מתנה.
שאלה 13 · מספר מיוחד, רשימה מיוחדת ורשימת רשימות
נתונות הגדרות הבאות:
•מספר שלם וחיובי נקרא "מספר מיוחד" אם ספרות המספר (משמאל לימין) מהוות סידרה עולה.
לדוגמה:
המספרים 12, 138, 2689, 4 הם "מספרים מיוחדים".
המספרים 43, 176, -123, 33 אינם "מספרים מיוחדים".
•רשימה של מספרים שלמים (חיוביים, שליליים ואפסים) נקראת "מיוחדת" אם יש בה לפחות "מספר מיוחד" אחד וערכי הרשימה ממוינים בסדר עולה.
•רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה) נקראת "סופר מיוחדת" אם כל איבר שלה הוא "רשימה מיוחדת".
כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה של מספרים שלמים) ובודקת אם היא "סופר מיוחדת".
אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 13
סעיף א
שלוש פעולות: `is_special_num` (מספר חיובי שספרותיו עולות ממש), `is_special_list` (ממוינת בסדר עולה ויש בה מספר מיוחד), `is_super_special` (כל הרשימות הפנימיות מיוחדות).
רעיון הפתרון: מפרקים את הבעיה לשלוש פעולות, אחת לכל הגדרה.
•מספר שאינו חיובי (אפס או שלילי, כמו ) אינו מיוחד.
•הספרות צריכות לעלות משמאל לימין ממש (33 אינו מיוחד, ולכן ספרות שוות אסורות). קל יותר לעבור על הספרות מימין לשמאל (בעזרת `% 10` ו-`// 10`): אז כל ספרה צריכה להיות קטנה ממש מהספרה שמימינה.
•מספר חד-ספרתי (כמו 4) מיוחד – אין בו זוג ספרות שמפר את התנאי.
•בודקים שהרשימה ממוינת בסדר עולה: לכל צריך להתקיים `lst[i-1] <= lst[i]`. אם לא – מחזירים `False` מיד.
•באותו מעבר בודקים אם יש לפחות מספר מיוחד אחד (דגל `has_special`).
•מחזירים את הדגל: רשימה ממוינת בלי אף מספר מיוחד (וגם רשימה ריקה) אינה מיוחדת.
3. רשימה סופר מיוחדת – `is_super_special(lists)`: עוברים על כל הרשימות הפנימיות; אם אחת מהן אינה מיוחדת – `False`, אחרת `True`.
def is_special_num(num):
if num <= 0:
return False
last = num % 10 # הספרה הימנית
num //= 10
while num > 0:
digit = num % 10 # הספרה שמשמאל ל-last
if digit >= last: # הספרות לא עולות ממש
return False
last = digit
num //= 10
return True
def is_special_list(lst):
has_special = False
for i in range(len(lst)):
if i > 0 and lst[i - 1] > lst[i]:
return False # לא ממוינת בסדר עולה
if is_special_num(lst[i]):
has_special = True
return has_special
def is_super_special(lists):
for lst in lists:
if not is_special_list(lst):
return False
return Trueבדיקה על הדוגמאות: 12, 138, 2689, 4 מחזירים `True`; 43, 176, , 33 מחזירים `False`. למשל, ב-176 הספרה 7 אינה קטנה מהספרה 6 שמימינה, ולכן מוחזר `False`; ב-33 שתי הספרות שוות, ולכן גם הוא אינו מיוחד.
דוגמה לרשימת רשימות: `[[-5, 0, 12, 40], [1], [3, 3, 7]]` היא סופר מיוחדת (כל רשימה ממוינת, ובכל אחת יש מספר מיוחד: 12, 1, 3). לעומת זאת `[[-5, 0, 12, 40], [10, 20]]` אינה סופר מיוחדת, כי ב-`[10, 20]` אין מספר מיוחד.
תשובה: הפעולה `is_super_special` שלמעלה (עם פעולות העזר) – מחזירה `True` אם ורק אם כל רשימה פנימית ממוינת בסדר עולה ומכילה לפחות מספר חיובי אחד שספרותיו עולות ממש.
סעיף ב
, כאשר מספר המספרים הכולל בכל הרשימות ו- מספר הספרות המרבי; עבור מספרים בגודל חסום – .
נסמן ב- את מספר המספרים הכולל בכל הרשימות הפנימיות (אם יש רשימות, כל אחת באורך עד , אז ), וב- את מספר הספרות המרבי של מספר.
1. `is_special_num` עוברת פעם אחת על הספרות: .
2. `is_special_list` עוברת פעם אחת על רשימה באורך , ולכל איבר מבצעת השוואה אחת () וקריאה ל-`is_special_num` (): .
3. `is_super_special` קוראת ל-`is_special_list` פעם אחת לכל רשימה, ולכן כל מספר בכל הרשימות נבדק לכל היותר פעם אחת: .
כשגודל המספרים חסום, קבוע, והסיבוכיות היא – לינארית במספר האיברים הכולל (כל איבר נבדק פעם אחת).
תשובה: , כלומר – לינארית במספר הכולל של המספרים בכל הרשימות.
שאלה 14 · רקורסיה: אינדקס המינימום ומיון בסדר יורד
נתונה הפעולה הרקורסיביות `secret`:
def secret(a):
if(len(a) == 1):
return 0
k = secret(a[:-1])
if a[-1] < a[k]:
return (len(a) - 1);
return kנתונה הרשימה הבאה של מספרים שלמים:
a = [3,5,1,2,10,9]עקבו אחרי זימון `secret(a)` רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `secret(a)` באופן כללי?
נתונה הפעולה הרקורסיביות `mystery`:
def mystery(a):
if len(a) == 1:
return a
k = secret(a)
temp = a[k]
a[k] = a[-1]
return (mystery(a[:-1])+[temp])נתונה הרשימה הבאה של מספרים שלמים:
a = {3,5,1,2,10,9}עקבו אחרי זימון `mystery(a)` ורשמו את תוצאות הזימון.
מה מבצעת הפעולה `mystery(a)` באופן כללי?
◂ פתרון מלא לשאלה 14
סעיף א
`secret(a)` מחזירה 2 (המקום של הערך 1, הקטן ביותר).
רעיון: `secret` קוראת לעצמה על הרשימה בלי האיבר האחרון (`a[:-1]`), עד שנשארת רשימה באורך 1 (ואז מוחזר 0). בחזרה מהרקורסיה, בכל שלב משווים את האיבר האחרון `a[-1]` לאיבר `a[k]` שהקריאה הפנימית החזירה: אם האחרון קטן ממנו, מוחזר המקום של האחרון (`len(a) - 1`), אחרת מוחזר `k`.
מעקב – הקריאות יורדות מלמעלה למטה, והערכים חוזרים מלמטה למעלה:
תשובה: `secret(a)` מחזירה 2.
סעיף ב
מחזירה את המקום (האינדקס) של האיבר הקטן ביותר ברשימה; אם הוא מופיע כמה פעמים – את המקום של המופע הראשון.
1. ברשימה באורך 1 האיבר היחיד הוא הקטן ביותר, ומוחזר המקום 0.
2. נניח ש-`secret(a[:-1])` מחזירה את המקום `k` של המינימום בכל הרשימה פרט לאיבר האחרון. המינימום של כל הרשימה הוא או `a[k]` או האיבר האחרון. אם האחרון קטן ממש מ-`a[k]` – הוא המינימום, ומוחזר המקום שלו `len(a) - 1`; אחרת המינימום נשאר `a[k]`.
3. בגלל ההשוואה `<` (ולא `<=`), במקרה של שוויון נשאר המקום הקודם – כלומר מוחזר המופע הראשון של המינימום.
תשובה: `secret(a)` מחזירה את האינדקס של הערך המינימלי ברשימה (המופע הראשון שלו).
סעיף ג
`mystery(a)` מחזירה `[10, 9, 5, 3, 2, 1]`.
הערה: בשאלון הרשימה כתובה בסוגריים מסולסלים, אבל לפי הנוסח מדובר ברשימה של מספרים שלמים, ולכן מתייחסים אליה כאל `a = [3,5,1,2,10,9]`.
רעיון: בכל קריאה `secret(a)` נותנת את מקום המינימום `k`. שומרים את המינימום ב-`temp`, מעתיקים את האיבר האחרון למקום `k` (כך המינימום "יוצא" מהרשימה ואף ערך אחר לא הולך לאיבוד), ואז קוראים ברקורסיה על הרשימה בלי האיבר האחרון ומוסיפים את `temp` בסוף התוצאה.
מעקב (הקריאות יורדות מלמעלה למטה):
החזרה מהרקורסיה (מלמטה למעלה), בכל שלב מוסיפים את `temp` בסוף:
(בקריאה הראשונה הרשימה המקורית עצמה משתנה ל-`[3,5,9,2,10,9]`, כי `a[k] = a[-1]` מתבצע עליה; הקריאות הבאות פועלות על העתקים שנוצרו ב-`a[:-1]`.)
תשובה: `mystery(a)` מחזירה `[10, 9, 5, 3, 2, 1]`.
סעיף ד
מחזירה רשימה חדשה עם אותם ערכים ממוינים בסדר יורד (מהגדול לקטן).
1. בכל קריאה מוציאים מהרשימה את הערך הקטן ביותר (`temp`, בעזרת `secret`), ובמקומו שמים את האיבר האחרון. כך הרשימה `a[:-1]` מכילה בדיוק את כל שאר הערכים.
2. התוצאה של הקריאה היא: התוצאה הרקורסיבית על שאר הערכים, ואחריה הערך הקטן ביותר בסוף.
3. לכן הערך הקטן ביותר נמצא במקום האחרון, השני בקטנותו לפניו, וכן הלאה – הרשימה המוחזרת ממוינת בסדר יורד. זהו מיון בחירה (selection sort) רקורסיבי.
4. תופעת לוואי: הרשימה המקורית שהועברה משתנה (בה האיבר הקטן ביותר מוחלף באיבר האחרון).
תשובה: `mystery(a)` מחזירה את ערכי הרשימה ממוינים בסדר יורד (מיון בחירה רקורסיבי).