מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - אביב 2026 מועד א'
הנדסת תוכנה · סמל 97103 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), אביב 2026 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: בשאלון זה שני מבחנים. עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:
מבחן ב-Python (עמוד 2)
בכל מבחן 10 שאלות.
חלק א' – 36 נקודות
שאלות 1–4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 5–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 34 נקודות
שאלות 8–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 17 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
אין לצרף ספרים או חוברות עם פתרונות.
מילון עזר.
שאלה 1 · מחרוזת תקינה: אותיות גדולות וקטנות, קליטה עד תנאי
"מחרוזת תקינה" היא מחרוזת הכוללת רק אותיות (גדולות וקטנות) ומספר האותיות הגדולות שבה גדול ממספר האותיות הקטנות.
כתבו פונקציה המקבלת מחרוזת ובודקת אם היא "תקינה". אם כן – הפונקציה תחזיר ערך `True`, ואם לא – הפונקציה תחזיר ערך `False`.
כתבו קטע תוכנית הקולט מחרוזות. הקלט מסתיים כאשר תיקלט מחרוזת "תקינה". הקטע יחשב וידפיס את מספר המחרוזות אשר מתחילות או מסתיימות באות 'A'.
◂ פתרון מלא לשאלה 1
סעיף א
עוברים על התווים: אות גדולה ('A'–'Z') מגדילה מונה אחד, אות קטנה ('a'–'z') מונה שני, וכל תו אחר מחזיר מיד `False`; בסוף מחזירים `upper > lower`.
1. מחרוזת תקינה צריכה לקיים שני תנאים: כל התווים הם אותיות, ויש יותר אותיות גדולות מקטנות.
2. עוברים על המחרוזת תו אחרי תו. תו בין 'A' ל-'Z' הוא אות גדולה – מגדילים את `upper`. תו בין 'a' ל-'z' הוא אות קטנה – מגדילים את `lower`.
3. תו שאינו אות (ספרה, רווח, סימן) פוסל את המחרוזת מיד, ולכן מחזירים `False` בלי להמשיך לסרוק.
4. אחרי הלולאה כל התווים הם אותיות, ונשאר להשוות: מחזירים `True` רק אם `upper > lower`.
5. מחרוזת ריקה: אין בה אותיות גדולות, ו- אינו מתקיים, ולכן היא לא תקינה (הבדיקה בתחילת הפונקציה רק מבהירה זאת).
לדוגמה: "ABc" – שתי גדולות ואחת קטנה, ולכן `True`; "Ab" – אחת מול אחת, ולכן `False`; "AB1" – יש ספרה, ולכן `False`.
def is_valid(s):
if len(s) == 0:
return False
upper = 0
lower = 0
for ch in s:
if 'A' <= ch <= 'Z': # אות גדולה
upper += 1
elif 'a' <= ch <= 'z': # אות קטנה
lower += 1
else: # תו שאינו אות
return False
return upper > lowerסיבוכיות: מעבר אחד על המחרוזת, עבור מחרוזת באורך .
תשובה: הפונקציה `is_valid` מחזירה `True` אם כל התווים הם אותיות ויש יותר אותיות גדולות מקטנות, ואחרת `False`.
סעיף ב
לולאה שקולטת מחרוזת, מגדילה מונה אם `s[0] == 'A'` או `s[-1] == 'A'`, ונעצרת כש-`is_valid(s)` מחזירה `True`; אחרי הלולאה מדפיסים את המונה.
1. לא ידוע מראש כמה מחרוזות ייקלטו, ולכן משתמשים בלולאת `while`. תנאי העצירה – המחרוזת שנקלטה "תקינה" – נבדק בעזרת הפונקציה `is_valid` מסעיף א.
2. גם המחרוזת התקינה שמסיימת את הקלט היא מחרוזת שנקלטה, ולכן בודקים גם אותה לפני שיוצאים מהלולאה. (מי שמפרש שהמחרוזת המסיימת לא נספרת, פשוט מעביר את בדיקת העצירה לפני הספירה.)
3. מחרוזת "מתחילה או מסתיימת ב-'A'" אם התו הראשון `s[0]` הוא 'A' או התו האחרון `s[-1]` הוא 'A'. מחרוזת שגם מתחילה וגם מסתיימת ב-'A' נספרת פעם אחת בלבד, כי זה תנאי אחד עם `or`.
4. לפני הגישה ל-`s[0]` מוודאים שהמחרוזת אינה ריקה, כדי לא לחרוג מגבולות המחרוזת.
5. המונה מודפס פעם אחת, אחרי שהקלט הסתיים.
לדוגמה, עבור הקלט "Abc", "xyzA", "hello", "bA", "ABx": נספרות "Abc" (מתחילה ב-A), "xyzA" (מסתיימת ב-A), "bA" ו-"ABx"; "ABx" גם תקינה (שתי גדולות ואחת קטנה) ולכן הקלט נעצר. יודפס 4.
count = 0
s = input()
while True:
if len(s) > 0 and (s[0] == 'A' or s[-1] == 'A'):
count += 1
if is_valid(s): # מחרוזת תקינה מסיימת את הקלט
break
s = input()
print(count)תשובה: הקטע קולט מחרוזות עד מחרוזת תקינה (לפי `is_valid`), סופר את המחרוזות שהתו הראשון או האחרון שלהן הוא 'A', ומדפיס את המונה.
שאלה 2 · מספר מתחלף: זוגיות ספרות שכנות
"מספר מתחלף" הוא מספר שלם חיובי שבו כל זוג ספרות שכנות (צמודות) הוא בעל זוגיות שונה. כלומר אם ספרה אחת זוגית, הספרה הסמוכה לה תהיה אי-זוגית, ולהפך. מספר חד ספרתי הוא "מספר מתחלף".
לדוגמה:
•המספר 18345 הוא מספר מתחלף.
•המספר 2347 הוא מספר מתחלף.
•המספר 4 הוא מספר מתחלף.
•המספר 23441 אינו מספר מתחלף.
•המספר אינו מספר מתחלף.
כתבו פונקציה המקבלת מספר שלם ובודקת אם הוא מספר מתחלף. אם כן – הפונקציה תחזיר ערך `True`, ואם לא – הפונקציה תחזיר ערך `False`.
כתבו פונקציה המקבלת רשימה של מספרים שלמים ומחזירה סכום של כל המספרים המתחלפים הנמצאים ברשימה.
◂ פתרון מלא לשאלה 2
סעיף א
מספר שאינו חיובי – `False`; אחרת מפרקים את המספר לספרות מימין לשמאל ומשווים את הזוגיות של כל ספרה לזו של הספרה שלפניה; זוגיות זהה – `False`, אחרת בסוף `True`.
1. לפי ההגדרה, מספר מתחלף חייב להיות שלם חיובי. לכן מספר שלילי (כמו ) או אפס מחזיר מיד `False`.
2. מפרקים את המספר לספרות מימין לשמאל: `num % 10` היא ספרת האחדות, ו-`num // 10` מוחק אותה. הסדר שבו עוברים על הספרות לא משנה, כי בודקים רק זוגות שכנים.
3. שומרים את הספרה הקודמת ב-`prev`. לכל ספרה חדשה `digit` בודקים: אם `digit % 2 == prev % 2`, לשתי הספרות השכנות יש אותה זוגיות – המספר אינו מתחלף, ומחזירים `False`.
4. אם עברנו על כל הספרות בלי למצוא זוג כזה – מחזירים `True`. מספר חד ספרתי לא נכנס ללולאה כלל, ולכן מוחזר `True`, כנדרש.
1. 18345: הזוגות מימין לשמאל הם (5,4), (4,3), (3,8), (8,1) – בכל זוג ספרה זוגית ואי-זוגית, ולכן `True`.
2. 23441: הזוג (4,4) – שתי ספרות זוגיות, ולכן `False`.
3. : המספר שלילי, ולכן `False`.
def is_alternating(num):
if num <= 0: # רק מספר שלם חיובי יכול להיות מתחלף
return False
prev = num % 10 # ספרת האחדות
num //= 10
while num > 0:
digit = num % 10
if digit % 2 == prev % 2: # שתי ספרות שכנות עם אותה זוגיות
return False
prev = digit
num //= 10
return Trueסיבוכיות: , כאשר הוא מספר הספרות.
תשובה: הפונקציה `is_alternating` מחזירה `True` אם המספר חיובי ואין בו שתי ספרות שכנות עם אותה זוגיות, ואחרת `False`.
סעיף ב
עוברים על הרשימה ומוסיפים לסכום כל מספר ש-`is_alternating` מחזירה עבורו `True`; מחזירים את הסכום.
1. משתמשים בפונקציה `is_alternating` מסעיף א, כך שאין צורך לכתוב שוב את בדיקת הספרות.
2. סוכם `total` מתחיל ב-0 (האיבר הניטרלי בחיבור). עוברים על כל מספר ברשימה, ואם הוא מתחלף – מוסיפים אותו לסכום.
3. אם אין ברשימה אף מספר מתחלף (או שהרשימה ריקה) מוחזר 0.
לדוגמה, עבור הרשימה `[18345, 2347, 4, 23441, -1234]` המספרים המתחלפים הם 18345, 2347 ו-4, והסכום הוא .
def sum_alternating(lst):
total = 0
for x in lst:
if is_alternating(x):
total += x
return totalתשובה: הפונקציה `sum_alternating` מחזירה את סכום כל המספרים ברשימה שהפונקציה `is_alternating` מזהה כמתחלפים (0 אם אין כאלה).
שאלה 3 · מעקב וניתוח: חיפוש זוג שסכומו נתון
הגדרה: רשימה נקראת "רשימה ממוינת בסדר יורד" אם כל איבר (פרט לאיבר הראשון) קטן מהאיבר הקודם לו או שווה לו.
נתונה הפונקציה `secret` המקבלת רשימת מספרים שלמים ממוינת בסדר יורד ומספר שלם נוסף:
def secret(arr, num):
i = 0
j = len(arr) - 1
while i < j:
s = arr[i] + arr[j]
if s > num:
i += 1
else:
if s < num:
j -= 1
else:
return True
return Falseנתונה הרשימה `arr=[20, 16, 9, 4, 2]`
עקבו בעזרת טבלת מעקב אחר הזימון `secret(arr, 12)`, ורשמו מה תחזיר הפונקציה.
תנו דוגמה לפרמטר `num` כך שזימון `secret (arr, num)` יחזיר תוצאה שונה מהתוצאה שהתקבלה בסעיף א.1.
שימו לב: אין לשנות את הרשימה `arr`!
מה מבצעת הפונקציה `secret` באופן כללי?
האם ההנחה שרשימה `arr` ממוינת בסדר יורד היא הכרחית לביצוע תקין של הפונקציה `secret`?
אם לא – תסבירו למה דרישה זו מיותרת, ואם כן – כתבו פונקציה חדשה המבצעת את אותה המשימה עבור כל רשימה של מספרים שלמים (גם ממוינת וגם לא ממוינת).
◂ פתרון מלא לשאלה 3
סעיף א
הפונקציה מחזירה `False`.
מה עוקבים: בכל סיבוב מחשבים את סכום שני האיברים שבמקומות `i` (מתחילת הרשימה) ו-`j` (מסופה), משווים אותו ל-`num = 12`, ומזיזים את אחד המצביעים.
הלולאה מסתיימת כש-`i` ו-`j` נפגשים (שניהם 3) בלי שנמצא סכום השווה ל-12, ולכן מוחזר `False`.
(ואכן, אין ברשימה שני איברים שסכומם 12: הסכומים האפשריים הם 6, 11, 13, 18, 20, 22, 24, 25, 29, 36.)
תשובה: `secret(arr, 12)` מחזירה `False`.
למשל `num = 13` (כי ); הפונקציה מחזירה `True`.
מה צריך: בסעיף א.1 התקבל `False`, ולכן צריך `num` שעבורו יוחזר `True`, כלומר `num` ששווה לסכום של שני איברים של `arr` (במקומות שונים).
נבחר `num = 13`, כי . מעקב:
כל אחד מהסכומים 6, 11, 13, 18, 20, 22, 24, 25, 29, 36 היה מתאים גם הוא.
תשובה: `num = 13` – הזימון `secret(arr, 13)` מחזיר `True`.
סעיף ב
מחזירה `True` אם יש ברשימה שני איברים (במקומות שונים) שסכומם שווה ל-`num`, ואחרת `False`.
1. `i` מצביע על האיבר הגדול שעדיין לא נפסל (בתחילת הרשימה), ו-`j` על האיבר הקטן (בסופה).
2. אם הסכום גדול מ-`num`, צריך סכום קטן יותר. `arr[i]` גדול מדי: גם עם האיבר הקטן ביותר שנשאר הוא נותן סכום גדול מדי, ולכן הוא לא יכול להשתתף בזוג מתאים – מזיזים את `i` קדימה לאיבר קטן יותר.
3. אם הסכום קטן מ-`num`, באותו אופן `arr[j]` קטן מדי גם עם האיבר הגדול ביותר שנשאר – מזיזים את `j` אחורה לאיבר גדול יותר.
4. אם הסכום שווה ל-`num` – נמצא זוג, ומוחזר `True`. אם המצביעים נפגשו – אין זוג כזה, ומוחזר `False`.
בכל סיבוב אחד המצביעים זז, ולכן יש לכל היותר סיבובים – סיבוכיות .
תשובה: הפונקציה בודקת אם קיימים ברשימה שני איברים במקומות שונים שסכומם שווה ל-`num` (מחזירה `True` אם כן, `False` אם לא).
סעיף ג
כן, ההנחה הכרחית (למשל `secret([2, 4, 9], 13)` מחזירה `False` אף ש-). הפונקציה החדשה ממיינת עותק של הרשימה בסדר יורד ומריצה עליו את אותו אלגוריתם.
ההנחה הכרחית. כל ההיגיון של הזזת המצביעים (סעיף ב) מבוסס על כך ש-`arr[i]` הוא הגדול ו-`arr[j]` הוא הקטן מבין האיברים שנשארו. ברשימה לא ממוינת, הזזת מצביע עלולה לפסול איבר שדווקא שייך לזוג המתאים.
דוגמה נגדית: `arr = [2, 4, 9]`, `num = 13` (יש זוג: ).
הפונקציה מחזירה `False`, למרות שיש זוג שסכומו 13.
1. יוצרים עותק ממוין של הרשימה בסדר יורד בעזרת `sorted(arr, reverse=True)`. `sorted` מחזירה רשימה חדשה, ולכן הרשימה המקורית לא משתנה.
2. מריצים על העותק בדיוק את אותו אלגוריתם של שני מצביעים, שעכשיו פועל נכון כי ההנחה מתקיימת.
סיבוכיות: המיון והסריקה , ובסך הכול . (אפשר גם לבדוק את כל הזוגות בשתי לולאות מקוננות, ב-.)
def secret_any(arr, num):
sorted_arr = sorted(arr, reverse=True) # עותק ממוין בסדר יורד
i = 0
j = len(sorted_arr) - 1
while i < j:
s = sorted_arr[i] + sorted_arr[j]
if s > num:
i += 1
elif s < num:
j -= 1
else:
return True
return Falseעבור הדוגמה הנגדית: העותק הוא `[9, 4, 2]`; ולכן `j` זז, ואז – מוחזר `True`, כנדרש.
תשובה: כן, ההנחה הכרחית; הפונקציה `secret_any` ממיינת עותק של הרשימה בסדר יורד ומריצה עליו את אותו אלגוריתם, ולכן פועלת נכון לכל רשימה.
שאלה 4 · מחלקת משאית: בנאי ופונקציות על רשימת עצמים
חברת משאיות המתמחה בהובלת מזון החליטה למחשב את ניהול המשאיות שלה. לשם כך הוגדרה המחלקה `Truck`. למחלקה התכונות הבאות:
•מספר הרישוי – `truck_id` - מחרוזת (`str`)
•שם הנהג `driver_name` – מחרוזת (`str`)
•המשקל המרבי (מקסימלי) לאחסון – `max_weight` - מספר שלם (`int`)
•האם המשאית מיועדת לקירור? `is_refrigeration` – בוליאני (`bool`)
•האם המשאית פנויה להובלה? – `is_free` – בוליאני (`bool`)
כתבו במחלקה `Truck` את הפונקציה הבונה (`__init__`) המקבלת את מספר הרישוי ואת שם הנהג. הפונקציה מאתחלת את המשאית הפנויה להובלה, עם משקל מרבי של 4,000 קילוגרם ושאינה מיועדת לקירור.
כתבו פונקציה חיצונית המקבלת רשימה של משאיות (רשימת הפניות לאובייקטים מטיפוס `Truck`) ומדפיסה את לוחיות הרישוי של המשאיות המיועדות לקירור שמשקלן לפחות 10,000 קילוגרם.
כתבו פונקציה המקבלת רשימה של משאיות (רשימת הפניות לאובייקטים מטיפוס `Truck`) ומחזירה את שם הנהג של משאית שהיא פנויה להובלה, מיועדת לקירור ומשקל האחסון שלה הוא הגדול ביותר.
אם אין אף משאית פנויה שמיועדת לקירור, הפונקציה תחזיר מחרוזת "NONAME".
◂ פתרון מלא לשאלה 4
סעיף א
`__init__(self, truck_id, driver_name)` שומרת את שני הפרמטרים, וקובעת `max_weight = 4000`, `is_refrigeration = False`, `is_free = True`.
1. הבנאי מקבל רק שני פרמטרים (מלבד `self`): מספר הרישוי ושם הנהג, ושומר אותם בתכונות המתאימות.
2. שלוש התכונות האחרות מקבלות ערכים קבועים לפי הדרישה: משקל מרבי 4000 ק"ג, לא מיועדת לקירור (`False`), ופנויה להובלה (`True`).
class Truck:
def __init__(self, truck_id, driver_name):
self.truck_id = truck_id
self.driver_name = driver_name
self.max_weight = 4000 # משקל מרבי 4,000 ק"ג
self.is_refrigeration = False # לא מיועדת לקירור
self.is_free = True # פנויה להובלהתשובה: הבנאי שלמעלה – שומר את מספר הרישוי ואת שם הנהג, ומאתחל `max_weight=4000`, `is_refrigeration=False`, `is_free=True`.
סעיף ב
לולאה על הרשימה; אם `t.is_refrigeration` וגם `t.max_weight >= 10000` – מדפיסים `t.truck_id`.
1. הפונקציה חיצונית (לא בתוך המחלקה), ולכן היא ניגשת לתכונות דרך כל עצם: `t.is_refrigeration`, `t.max_weight`, `t.truck_id`.
2. לכל משאית בודקים שני תנאים יחד (`and`): היא מיועדת לקירור, ומשקלה המרבי לפחות 10,000 ק"ג – כלומר `>= 10000` (גם 10,000 בדיוק נכלל).
3. אם שני התנאים מתקיימים – מדפיסים את מספר הרישוי. הסעיף לא דורש שהמשאית תהיה פנויה, ולכן לא בודקים את `is_free`.
def print_heavy_refrigerated(trucks):
for t in trucks:
if t.is_refrigeration and t.max_weight >= 10000:
print(t.truck_id)תשובה: הפונקציה `print_heavy_refrigerated` מדפיסה את `truck_id` של כל משאית שמיועדת לקירור ושה-`max_weight` שלה לפחות 10000.
סעיף ג
חיפוש מקסימום לפי `max_weight` רק בין המשאיות עם `is_free` ו-`is_refrigeration`; מחזירים את `driver_name` של המשאית שנמצאה, או "NONAME" אם לא נמצאה אף אחת.
1. זה חיפוש מקסימום, אבל רק בין המשאיות שעומדות בשני התנאים: פנויה (`is_free`) ומיועדת לקירור (`is_refrigeration`).
2. לא מאתחלים את המקסימום במשאית הראשונה ברשימה, כי ייתכן שהיא לא עומדת בתנאים. במקום זאת המשתנה `best` מתחיל ב-`None`, שפירושו "עדיין לא נמצאה משאית מתאימה".
3. כל משאית מתאימה מחליפה את `best` אם זו המתאימה הראשונה (`best is None`) או אם המשקל שלה גדול מזה של `best`.
4. אחרי הלולאה: אם `best` נשאר `None` – אין משאית פנויה לקירור, ומחזירים "NONAME". אחרת מחזירים את שם הנהג של `best`. (אם לכמה משאיות אותו משקל מרבי, מוחזרת הראשונה מביניהן.)
def best_refrigerated_driver(trucks):
best = None
for t in trucks:
if t.is_free and t.is_refrigeration:
if best is None or t.max_weight > best.max_weight:
best = t
if best is None:
return "NONAME"
return best.driver_nameסיבוכיות: מעבר אחד על הרשימה, .
תשובה: הפונקציה `best_refrigerated_driver` מחזירה את שם הנהג של המשאית הפנויה לקירור עם `max_weight` הגדול ביותר, או "NONAME" אם אין כזו.
שאלה 5 · סכום מחלקים: מספר משוכלל, חסר ועתיר
כתבו פונקציה המקבלת מספר שלם וחיובי `num` ומחזירה את סכום כל מחלקיו החיוביים פרט לו עצמו.
כותרת הפונקציה:
def sum_of_proper_divisors(num)לדוגמה:
•עבור המספר 10 הפונקציה תחזיר
•עבור המספר 6 הפונקציה תחזיר
•עבור המספר 12 הפונקציה תחזיר
כתבו פונקציה המקבלת מספר שלם חיובי `num`, ומחזירה את אחד מהערכים הבאים המציינים "סוג המספר":
•`'P'` – אם `num` שווה לסכום מחלקיו (מספר משוכלל – Perfect).
•`'D'` – אם `num` גדול מסכום מחלקיו (מספר חסר – Deficient).
•`'A'` – אם `num` קטן מסכום מחלקיו (מספר עתיר – Abundant).
כותרת הפונקציה:
def check_number_type(num)כתבו פונקציה המקבלת מספר שלם חיובי `limit` ותו `num_type` ומחזירה רשימה הכוללת את כל המספרים השלמים החיוביים הקטנים מ-`limit` בהתאם לסוג המבוקש `num_type`.
לדוגמה:
עבור המספר `num = 60` וסוג המספר `num_type='A'` הפונקציה תחזיר את הרשימה:
`[12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56]`
כותרת הפונקציה:
def all_numbers_by_type(limit, num_type)◂ פתרון מלא לשאלה 5
סעיף א
סוכמים את כל `d` בתחום 1 עד `num // 2` שמקיימים `num % d == 0`; עבור 10, 6, 12 מתקבלים 8, 6, 16.
1. מחלק של `num` הוא מספר `d` שעבורו `num % d == 0`.
2. מחלק של `num` ששונה מ-`num` עצמו הוא לכל היותר `num // 2` (המחלק הבא אחרי חצי המספר הוא המספר עצמו). לכן מספיק לבדוק את `d` מ-1 עד `num // 2`, ו-`num` עצמו לא נכלל אוטומטית.
3. כל מחלק שנמצא מתווסף לסכום `total`, שמתחיל ב-0.
4. עבור `num = 1` הלולאה לא רצה כלל (`1 // 2 = 0`), ומוחזר 0 – נכון, כי ל-1 אין מחלקים פרט לו עצמו.
בדיקה על הדוגמאות:
1. עבור 10: נבדקים 1 עד 5, והמחלקים הם 1, 2, 5 – הסכום .
2. עבור 12: נבדקים 1 עד 6, והמחלקים הם 1, 2, 3, 4, 6 – הסכום .
def sum_of_proper_divisors(num):
total = 0
for d in range(1, num // 2 + 1):
if num % d == 0:
total += d
return totalסיבוכיות: .
תשובה: הפונקציה סוכמת את כל המחלקים של `num` בין 1 ל-`num // 2`; למשל עבור 10 מוחזר 8, עבור 6 מוחזר 6 ועבור 12 מוחזר 16.
סעיף ב
`s = sum_of_proper_divisors(num)`; מחזירים `'P'` אם `num == s`, `'D'` אם `num > s`, ואחרת `'A'`.
1. מחשבים פעם אחת את סכום המחלקים `s` בעזרת הפונקציה מסעיף א (כפי שנדרש), ושומרים אותו במשתנה כדי לא לחשב אותו שוב בכל השוואה.
2. משווים את `num` ל-`s`: שוויון – משוכלל (`'P'`); `num` גדול יותר – חסר (`'D'`); אחרת `num` קטן יותר – עתיר (`'A'`).
לדוגמה: עבור 6 הסכום 6 – `'P'`; עבור 10 הסכום 8 והוא קטן מ-10 – `'D'`; עבור 12 הסכום 16 והוא גדול מ-12 – `'A'`.
def check_number_type(num):
s = sum_of_proper_divisors(num)
if num == s:
return 'P'
if num > s:
return 'D'
return 'A'תשובה: הפונקציה `check_number_type` מחזירה `'P'`, `'D'` או `'A'` לפי השוואת `num` לסכום מחלקיו שמחושב ב-`sum_of_proper_divisors`.
סעיף ג
עוברים על `num` מ-1 עד `limit - 1` ומוסיפים לרשימה כל מספר ש-`check_number_type(num) == num_type`; עבור 60 ו-`'A'` מתקבלת הרשימה `[12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56]`.
1. המספרים השלמים החיוביים הקטנים מ-`limit` הם 1, 2, ..., `limit - 1`, כלומר `range(1, limit)` (הגבול העליון לא נכלל).
2. לכל מספר בודקים את סוגו בעזרת `check_number_type` מסעיף ב, ואם הוא שווה לסוג המבוקש `num_type` – מוסיפים אותו לרשימה.
3. מוחזרת הרשימה, שבה המספרים מסודרים בסדר עולה (כי עברנו עליהם בסדר עולה). אם אין אף מספר מתאים – מוחזרת רשימה ריקה.
בדיקה על הדוגמה (בשאלה כתוב `num = 60`, והכוונה לפרמטר `limit = 60`; סוג `'A'`): למשל 12 עתיר כי , ו-18 עתיר כי ; לעומת זאת 14 חסר כי . המספרים העתירים הקטנים מ-60 הם בדיוק 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, כמו בדוגמה.
def all_numbers_by_type(limit, num_type):
result = []
for num in range(1, limit):
if check_number_type(num) == num_type:
result.append(num)
return resultסיבוכיות: לכל אחד מ-`limit` המספרים מחשבים סכום מחלקים ב-, ובסך הכול .
תשובה: הפונקציה `all_numbers_by_type` מחזירה את רשימת המספרים מ-1 עד `limit - 1` שסוגם (לפי `check_number_type`) הוא `num_type`; עבור 60 ו-`'A'` מתקבל `[12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56]`.
שאלה 6 · גלגול K של מחרוזת: סיבובים שמאלה
"סיבוב שמאלה של מחרוזת" היא פעולה שבה התו הראשון של המחרוזת נמחק ומועבר לסופה.
לדוגמה: אם `s = "ABCD"` אזי תוצאת הפונקציה היא: "BCDA".
מחרוזת `s2` היא "גלגול K" של מחרוזת `s1` אם אפשר לקבל את מחרוזת `s2` באמצעות K סיבובים שמאלה של מחרוזת `s1`.
לדוגמה: אם `s1 = "ABCDE"` אזי `s2= "CDEAB"` היא גלגול 2 של מחרוזת `s1`.
כתבו פונקציה המקבלת שתי מחרוזות `s1` ו-`s2` ומספר שלם חיובי `k`. הפונקציה תבדוק אם מחרוזת `s2` היא "גלגול K" של מחרוזת `s1`. אם כן – הפונקציה תחזיר `True`, ולא – הפונקציה תחזיר `False`.
כותרת הפונקציה:
def is_k_rolling(s1, s2, k)כתבו פונקציה המקבלת שתי מחרוזות `s1` ו-`s2`. הפונקציה תחזיר מספר שלם `k` שעבורו מחרוזת `s2` היא "גלגול K" של מחרוזת `s1`. אם אין שום מספר `k`, הפונקציה תחזיר `-1`.
כותרת הפונקציה:
def find_rolling_k(s1, s2)כתבו פונקציה המקבלת רשימת מחרוזות `arr` ומחרוזת נוספת `s`. על הפונקציה לבדוק אם כל המחרוזות שנמצאות ב-`arr` הן "גלגול K" כלשהו של המחרוזת `s`. אם כן – הפונקציה תחזיר `True`, ולא – הפונקציה תחזיר `False`.
כותרת הפונקציה:
def are_all_rotations(arr, s)◂ פתרון מלא לשאלה 6
סעיף א
אם האורכים שונים – `False`; אחרת `k = k % len(s1)` ומחזירים `s1[k:] + s1[:k] == s2`.
1. סיבוב שמאלה לא משנה את אורך המחרוזת, ולכן אם `len(s1) != len(s2)` – בוודאי `s2` אינה גלגול של `s1`.
2. אחרי סיבובים שמאלה, התווים הראשונים עוברים (באותו סדר) לסוף המחרוזת. כלומר התוצאה היא `s1[k:] + s1[:k]`. לדוגמה, ל-"ABCDE" ו-: `"CDE" + "AB" = "CDEAB"`.
3. אחרי סיבובים ( – אורך המחרוזת) מקבלים שוב את המחרוזת המקורית, ולכן סיבובים שקולים ל- סיבובים. כך הפונקציה נכונה גם עבור (למשל ל-"ABCDE" שקול ל-).
4. מחרוזת ריקה (שתיהן ריקות): סיבוב לא משנה אותה, ומחזירים `True` לפני החלוקה ב- (כדי לא לחלק באפס).
def is_k_rolling(s1, s2, k):
if len(s1) != len(s2):
return False
if len(s1) == 0:
return True
k = k % len(s1) # n סיבובים מחזירים את המחרוזת המקורית
return s1[k:] + s1[:k] == s2תשובה: הפונקציה `is_k_rolling` מחזירה `True` אם האורכים שווים ו-`s1[k:] + s1[:k] == s2` (אחרי `k = k % len(s1)`), ואחרת `False`.
סעיף ב
מנסים `k` מ-1 עד `len(s1)` בעזרת `is_k_rolling`; מחזירים את ה-`k` הראשון שמתאים, ואם אין – `-1`.
1. לפי סעיף א, גלגול וגלגול זהים ( – אורך המחרוזת). לכן מספיק לנסות את הערכים : אם אף אחד מהם לא מתאים, אין שום מתאים.
2. לכל קוראים ל-`is_k_rolling(s1, s2, k)`. ה- הראשון שעבורו מוחזר `True` הוא התשובה (הקטן ביותר).
3. אם הלולאה הסתיימה בלי התאמה – מחזירים `-1`. בפרט, אם האורכים שונים, `is_k_rolling` מחזירה תמיד `False`, ומוחזר `-1`.
4. אם `s1` ו-`s2` זהות, יוחזר המספר החיובי הקטן ביותר שמחזיר את המחרוזת לעצמה (למשל 3 עבור "ABC", ו-1 עבור "AAA"). (מניחים שהמחרוזות אינן ריקות.)
לדוגמה, עבור "ABCDE" ו-"CDEAB": נותן "BCDEA" – לא; נותן "CDEAB" – כן, ומוחזר 2.
def find_rolling_k(s1, s2):
for k in range(1, len(s1) + 1):
if is_k_rolling(s1, s2, k):
return k
return -1סיבוכיות: ניסיונות, ובכל אחד בניית מחרוזת והשוואה ב- – בסך הכול .
תשובה: הפונקציה `find_rolling_k` מחזירה את ה-`k` הקטן ביותר בין 1 ל-`len(s1)` שעבורו `s2` היא גלגול `k` של `s1`, או `-1` אם אין כזה (למשל עבור "ABCDE" ו-"CDEAB" מוחזר 2).
סעיף ג
לכל מחרוזת `word` ב-`arr`: אם `find_rolling_k(s, word) == -1` מחזירים `False`; אם כולן עברו – `True`.
1. מחרוזת `word` היא גלגול כלשהו של `s` אם ורק אם `find_rolling_k(s, word)` מסעיף ב אינה מחזירה `-1`. שימו לב לסדר הפרמטרים: `s` היא המחרוזת המקורית ו-`word` היא הגלגול שלה.
2. "כל המחרוזות" – מספיקה מחרוזת אחת שאינה גלגול כדי להחזיר `False`, ולכן מחזירים `False` מיד כשנמצאת כזו.
3. אם הלולאה הסתיימה – כל המחרוזות הן גלגולים של `s`, ומחזירים `True`. (עבור רשימה ריקה מוחזר `True`, כי אין בה מחרוזת שאינה גלגול.)
לדוגמה, עבור `s = "ABCD"`: הרשימה `["BCDA", "CDAB", "ABCD"]` מחזירה `True` (גלגולים 1, 2, 4), ואילו `["BCDA", "ACBD"]` מחזירה `False`, כי "ACBD" אינה גלגול של "ABCD".
def are_all_rotations(arr, s):
for word in arr:
if find_rolling_k(s, word) == -1:
return False
return Trueתשובה: הפונקציה `are_all_rotations` מחזירה `False` ברגע שנמצאת ב-`arr` מחרוזת ש-`find_rolling_k(s, word)` מחזירה עבורה `-1`, ואחרת `True`.
שאלה 7 · מעקב: מיון מנייה לפי ספרה
נתונה הפונקציה `what` המקבלת רשימה של מספרים שלמים חיוביים `arr` ופרמטר נוסף `exp`. הפרמטר `exp` יכול לקבל ערכים שהם חזקות של 10 (כגון 1, 10, 100, 1000 ...).
def what(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
digit = (arr[i] // exp) % 10
count[digit] += 1
# **** סיום שלב 1 ****
for i in range(1, 10):
count[i] += count[i - 1]
# **** סיום שלב 2 ****
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % 10
output[count[digit] - 1] = arr[i]
count[digit] -= 1
# **** סיום שלב 3 ****
return outputנתונה הרשימה `arr = [23, 15, 9, 71, 25]`
עקבו אחרי זימון הפונקציה `out1 = what(arr, 1)` ורשמו מה יהיה תוכן הרשימה `out1` אחרי זימון הפונקציה.
נתונה הרשימה `arr = [23, 15, 9, 71, 25]`
עקבו אחרי זימון הפונקציה `out2 = what(arr, 10)` ורשמו מה יהיה תוכן הרשימה `out2` אחרי זימון הפונקציה.
מה מבצעת הפונקציה `what` באופן כללי?
◂ פתרון מלא לשאלה 7
סעיף א
`out1 = [71, 23, 15, 25, 9]`. `count` אחרי שלב 1: `[0, 1, 0, 1, 0, 2, 0, 0, 0, 1]`; אחרי שלב 2: `[0, 1, 1, 2, 2, 4, 4, 4, 4, 5]`; אחרי שלב 3: `[0, 0, 1, 1, 2, 2, 4, 4, 4, 4]`.
נתון: `arr = [23, 15, 9, 71, 25]`, `exp = 1`, ולכן `digit = arr[i] % 10` – ספרת האחדות. .
מבוקש: תוכן `count` אחרי כל שלב, ותוכן `out1`.
ספרות האחדות הן: 23 → 3, 15 → 5, 9 → 9, 71 → 1, 25 → 5. כל ספרה מגדילה את התא המתאים ב-`count`:
שלב 2 – סכומים מצטברים: כל תא מקבל את סכום התאים עד אליו כולל. עכשיו `count[d]` הוא מספר האיברים שספרתם קטנה מ- או שווה לו, כלומר המקום (בספירה מ-1) שבו יוצב האיבר האחרון עם הספרה :
שלב 3 – הצבה ב-`output` מהסוף להתחלה: לכל איבר מציבים אותו במקום `count[digit] - 1` ומקטינים את `count[digit]` ב-1:
שימו לב ש-15 ו-25 (שתיהן עם ספרה 5) נשארו באותו סדר יחסי כמו ב-`arr`, כי עברנו מהסוף והצבנו את 25 במקום המאוחר יותר.
תשובה: `out1 = [71, 23, 15, 25, 9]` – הרשימה ממוינת לפי ספרת האחדות (1, 3, 5, 5, 9).
סעיף ב
`out2 = [9, 15, 23, 25, 71]`.
נתון: אותה רשימה `arr = [23, 15, 9, 71, 25]` (הפונקציה לא משנה את `arr`, היא כותבת לרשימה חדשה `output`), והפעם `exp = 10`, ולכן `digit = (arr[i] // 10) % 10` – ספרת העשרות.
מבוקש: תוכן `out2`.
שלב 1: ספרות העשרות: 23 → 2, 15 → 1, 9 → 0 (כי ), 71 → 7, 25 → 2.
23 ו-25 (שתיהן עם ספרת עשרות 2) נשארו בסדר שבו הופיעו ב-`arr`.
תשובה: `out2 = [9, 15, 23, 25, 71]` – הרשימה ממוינת לפי ספרת העשרות (0, 1, 2, 2, 7).
סעיף ג
מחזירה רשימה חדשה עם איברי `arr` ממוינים בסדר עולה לפי הספרה במקום `exp` (אחדות, עשרות, ...), מיון יציב (מיון מנייה – שלב אחד של מיון בסיס).
1. `(arr[i] // exp) % 10` היא הספרה של `arr[i]` במקום שמייצג `exp`: אחדות עבור 1, עשרות עבור 10, מאות עבור 100 וכן הלאה.
2. שלב 1 סופר כמה איברים יש עם כל ספרה, ושלב 2 הופך את המונים לסכומים מצטברים – כך `count[d]` מציין את הסוף של "האזור" ב-`output` שבו יוצבו האיברים עם הספרה .
3. שלב 3 מציב כל איבר באזור שלו. המעבר הוא מסוף `arr` להתחלה, ולכן איברים עם אותה ספרה שומרים על הסדר היחסי שהיה להם ב-`arr` – המיון יציב.
4. הרשימה `arr` לא משתנה; מוחזרת רשימה חדשה.
זהו מיון מנייה (Counting Sort) לפי ספרה אחת – השלב הבסיסי של מיון בסיס (Radix Sort). הפעלה של `what` עם `exp = 1, 10, 100, ...` ברצף (כל פעם על התוצאה הקודמת) ממיינת את הרשימה כולה. סיבוכיות כל זימון: .
תשובה: הפונקציה מחזירה רשימה חדשה שבה איברי `arr` ממוינים בסדר עולה לפי הספרה במקום `exp`, במיון יציב (מיון מנייה, שלב של מיון בסיס).
שאלה 8 · פרחים במטריצה: לב הפרח ועלי כותרת
נגדיר "פרח" בתוך מטריצה (רשימה של רשימות) כך:
•ה"פרח" מורכב מחמישה איברים בתת-מטריצה בגודל 3X3. האיבר המרכזי בתת-המטריצה הוא "לב הפרח". ארבעת האיברים הצמודים לו בפינותיו (אלכסוניים) הם "עלי הכותרת" של ה"פרח".
•הערך של "לב הפרח" שווה לסכום "עלי הכותרת" של הפרח.
•בכל פרח צריכים להיות בדיוק ארבעה "עלי כותרת".
לדוגמה: במערך הזה יש שני פרחים: אחד עם לב הפרח 6, ושני עם לב הפרח 15.

כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום איבר במטריצה: `row` (שורה) ו-`col` (עמודה). הפונקציה תבדוק אם איבר זה הוא "לב הפרח".
אם כן – הפונקציה תחזיר `True`, ולא – הפונקציה תחזיר `False`.
כותרת הפונקציה:
def is_flower(arr, row, col)כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr` ומחזירה רשימה חדשה הכוללת ערכים של כל "לב הפרח" הקיים במטריצה `arr`. אם אין אף "פרח", הפונקציה תחזיר רשימה ריקה.
כותרת הפונקציה:
def flower_hearts(arr)מהי סיבוכיות זמן הריצה של כל אחת הפונקציות שכתבתם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
אם האיבר בשורה או בעמודה שבשולי המטריצה – `False` (אין לו ארבעה עלי כותרת); אחרת מחזירים אם `arr[row][col]` שווה לסכום ארבעת האיברים האלכסוניים `arr[row±1][col±1]`.
1. עלי הכותרת של האיבר במקום (`row`, `col`) הם ארבעת השכנים האלכסוניים: (`row-1`, `col-1`), (`row-1`, `col+1`), (`row+1`, `col-1`), (`row+1`, `col+1`).
2. בכל פרח צריכים להיות בדיוק ארבעה עלי כותרת, ולכן לאיבר בשורה הראשונה או האחרונה, או בעמודה הראשונה או האחרונה, חסרים עלים – הוא לא יכול להיות לב פרח. בודקים זאת קודם, וכך גם לא חורגים מגבולות המטריצה:
•`row` צריך להיות בין 1 ל-`len(arr) - 2`;
•`col` צריך להיות בין 1 ל-`len(arr[row]) - 2`.
3. אם המיקום פנימי – מחשבים את סכום ארבעת העלים ומשווים לערך האיבר.
בדוגמה שבאיור לשאלה: לב הפרח 6 נמצא בשורה 1 ועמודה 1, ועלי הכותרת שלו הם . לב הפרח 15 נמצא בשורה 3 ועמודה 3, ועלי הכותרת שלו הם .
def is_flower(arr, row, col):
if row < 1 or row >= len(arr) - 1: # שורה ראשונה/אחרונה
return False
if col < 1 or col >= len(arr[row]) - 1: # עמודה ראשונה/אחרונה
return False
petals = (arr[row - 1][col - 1] + arr[row - 1][col + 1] +
arr[row + 1][col - 1] + arr[row + 1][col + 1])
return arr[row][col] == petalsתשובה: הפונקציה `is_flower` מחזירה `True` אם האיבר אינו בשולי המטריצה וערכו שווה לסכום ארבעת שכניו האלכסוניים, ואחרת `False`.
סעיף ב
שתי לולאות מקוננות על כל המיקומים הפנימיים (`row` מ-1 עד `len(arr) - 2`, `col` מ-1 עד `len(arr[row]) - 2`); כל איבר ש-`is_flower` מחזירה עבורו `True` נוסף לרשימה; בדוגמה מוחזר `[6, 15]`.
1. לב פרח יכול להיות רק איבר פנימי (לא בשורה או בעמודה שבשוליים), ולכן הלולאות עוברות רק על השורות 1 עד `len(arr) - 2` ועל העמודות 1 עד `len(arr[row]) - 2`. כך לא מבזבזים בדיקות על השוליים.
2. לכל מיקום פנימי משתמשים בפונקציה `is_flower` מסעיף א. אם היא מחזירה `True`, מוסיפים את ערך האיבר `arr[row][col]` לרשימת התוצאה.
3. הרשימה מתחילה ריקה, ולכן אם אין אף פרח (או שהמטריצה קטנה מ-3X3 ואין בה מיקומים פנימיים) מוחזרת רשימה ריקה, כנדרש.
4. המעבר הוא שורה אחרי שורה, ולכן הלבבות מופיעים ברשימה לפי סדר הופעתם במטריצה.
בדוגמה שבאיור לשאלה (התאים הריקים מכילים ערכים שאינם יוצרים פרחים נוספים) מוחזר `[6, 15]`.
def flower_hearts(arr):
hearts = []
for row in range(1, len(arr) - 1):
for col in range(1, len(arr[row]) - 1):
if is_flower(arr, row, col):
hearts.append(arr[row][col])
return heartsתשובה: הפונקציה `flower_hearts` עוברת על כל המיקומים הפנימיים, ומחזירה רשימה של ערכי האיברים ש-`is_flower` מזהה כלב פרח (רשימה ריקה אם אין).
סעיף ג
`is_flower`: ; `flower_hearts`: עבור מטריצה בת שורות ו- עמודות.
נסמן ב- את מספר השורות וב- את מספר העמודות של המטריצה.
1. `is_flower`: הפונקציה מבצעת מספר קבוע של פעולות – שתי בדיקות גבולות, חיבור של ארבעה איברים והשוואה אחת – בלי לולאות. מספר הפעולות לא תלוי בגודל המטריצה, ולכן הסיבוכיות היא .
2. `flower_hearts`: שתי לולאות מקוננות עוברות על מיקומים פנימיים, ובכל מיקום יש קריאה אחת ל-`is_flower` () ולכל היותר הוספה אחת לרשימה (). לכן הסיבוכיות היא , כלומר לינארית במספר האיברים של המטריצה.
תשובה: `is_flower` – ; `flower_hearts` – .
שאלה 9 · חניון חברות: מחלקות, מכסות ומקומות חניה
חניון תת-קרקעי משרת כמה חברות היי-טק. לכל חברה מוקצית מכסה מקסימלית של מקומות חניה (מספר הרכבים של החברה אשר יכולים לחנות בו-זמנית), ויש לנהל את הרכבים בהתאם לחברה שאליה הם משויכים ולמכסות המוקצות לה. לשם כך הוגדרו המחלקות הבאות:
המחלקה "רכב חברה" (`CompanyCar`) ולה התכונות:
•מספר הרישוי (`license_plate`) – מחרוזת, `str`
•היצרן (`manufacturer`) – מחרוזת, `str`
•שם החברה שהרכב משויך אליה (`company`) – מחרוזת, `str`
המחלקה "מגבלת חברה" (`CompanyLimit`) ולה התכונות:
•שם החברה (`company_name`) – מחרוזת, `str`
•המגבלה המקסימלית (`company_limit`) – מספר שלם, `int`
בכל מחלקה הוגדרה פונקציה בונה (`__init__`) המקבלת ערכים לכל התכונות.
הגדירו מחלקה בשם "חניון חברות" (`Parking`) הכוללת את התכונות הבאות:
•רשימה של רכבים (`cars`) – רשימה של עצמים מסוג "רכב חברה". הרשימה תכיל את הרכבים הנמצאים כרגע בחניון.
•רשימה של מקומות חניה (`parking_spots`) – רשימה של מחרוזות באותו הגודל, המציין את מקום החניה של הרכב המתאים (לדוגמה: "Q21", "A4", "P10").
•מגבלות חניה (`limits`) – רשימה של עצמים מסוג `CompanyLimit`, המכילה את המכסות לכל חברה.
כתבו במחלקה `Parking` פונקציה בונה (`__init__`), המקבלת רשימת `limits` מוכנה (עם החברות והמגבלות שלהן), ומייצרת חניון ללא רכבים: רשימות ה-`cars` וה-`parking_spot` יהיו ריקות בתחילה. קיבולת החניון הכוללת היא 150 מקומות.
כתבו במחלקה "חניון חברות" פונקציה המקבלת מקום בחניה (`spot`). הפונקציה תבדוק אם מקום זה פנוי. אם כן – הפונקציה תחזיר ערך `True`, ואם לא – הפונקציה תחזיר ערך `False`. כותרת הפונקציה:
def check_spot(self, spot)כתבו במחלקה "חניון חברות" פונקציה המקבלת את פרטי הרכב ואת מקום החניה (`spot`) ומנסה לחנות אותו:
•אם החניה `spot` תפוסה על ידי רכב אחר, הפונקציה תדפיס הודעה מתאימה ותחזיר `False`.
•אם החברה כבר ניצלה את המכסה שלה, הפונקציה תדפיס הודעה מתאימה ותחזיר `False`.
•אם המכסה לא נוצלה במלואה, הפונקציה תייצר רכב חדש (עצם מסוג `CompanyCar`) עם הפרטים שקיבלה, תוסיף את הרכב ותחזיר `True`. כותרת הפונקציה:
def park_car(self, license, manufacturer, company, spot)אפשר להניח שיש מקומות פנויים בחניון, והרכב (עם מספר הרישוי הנתון) אינו נמצא בחניון.
◂ פתרון מלא לשאלה 9
סעיף א
מחלקה `Parking` עם שלוש תכונות: `cars` (רשימת עצמי `CompanyCar`), `parking_spots` (רשימת מחרוזות מקבילה – `parking_spots[i]` הוא המקום של `cars[i]`) ו-`limits` (רשימת עצמי `CompanyLimit`).
1. המחלקה `Parking` מחזיקה שלוש רשימות. `cars` ו-`parking_spots` הן רשימות מקבילות: באותו אינדקס `i` נמצאים רכב (`cars[i]`) ומקום החניה שלו (`parking_spots[i]`). לכן הן תמיד באותו גודל – כל הוספה של רכב מוסיפה גם את מקומו.
2. `limits` היא רשימה של עצמי `CompanyLimit` – לכל חברה שמה והמכסה שלה.
3. בנוסף נשמור את קיבולת החניון (150 מקומות), שנדרשת בסעיף א.2.
לשלמות, אלה המחלקות הנתונות (בנאי שמקבל ערכים לכל התכונות), ואחריהן השלד של `Parking` (הבנאי שלה נכתב בסעיף א.2):
class CompanyCar:
def __init__(self, license_plate, manufacturer, company):
self.license_plate = license_plate
self.manufacturer = manufacturer
self.company = company
class CompanyLimit:
def __init__(self, company_name, company_limit):
self.company_name = company_name
self.company_limit = company_limit
class Parking:
# התכונות:
# cars - רשימת עצמים מסוג CompanyCar (הרכבים שבחניון)
# parking_spots - רשימת מחרוזות; parking_spots[i] הוא מקום החניה של cars[i]
# limits - רשימת עצמים מסוג CompanyLimit (המכסה של כל חברה)
# capacity - קיבולת החניון (150)
...תשובה: המחלקה `Parking` כוללת את `cars`, את `parking_spots` (רשימה מקבילה ל-`cars`) ואת `limits`, ובנוסף את הקיבולת `capacity`.
`__init__(self, limits)`: `self.cars = []`, `self.parking_spots = []`, `self.limits = limits`, `self.capacity = 150`.
1. הבנאי מקבל רק את רשימת המגבלות ושומר אותה בתכונה `limits`.
2. החניון נוצר ריק: שתי הרשימות המקבילות `cars` ו-`parking_spots` מאותחלות כרשימות ריקות חדשות.
3. הקיבולת הכוללת נשמרת בתכונה `capacity` עם הערך 150.
class Parking:
def __init__(self, limits):
self.cars = [] # אין רכבים בהתחלה
self.parking_spots = [] # ואין מקומות תפוסים
self.limits = limits # רשימת CompanyLimit מוכנה
self.capacity = 150 # קיבולת החניון הכוללתתשובה: הבנאי שלמעלה – `cars` ו-`parking_spots` ריקות, `limits` מקבלת את הרשימה שהועברה, ו-`capacity = 150`.
סעיף ב
`return spot not in self.parking_spots` – המקום פנוי אם הוא לא מופיע ברשימת המקומות התפוסים.
1. כל רכב שבחניון רשום יחד עם מקומו ברשימה `parking_spots`. לכן מקום תפוס אם ורק אם הוא מופיע ברשימה הזו.
2. מחפשים את `spot` ברשימה. אם הוא נמצא – המקום תפוס ומחזירים `False`; אם לא – המקום פנוי ומחזירים `True`.
def check_spot(self, spot):
for s in self.parking_spots:
if s == spot: # המקום כבר תפוס
return False
return True(אותו דבר בקיצור: `return spot not in self.parking_spots`.)
סיבוכיות: , כאשר הוא מספר הרכבים בחניון.
תשובה: הפונקציה `check_spot` מחזירה `True` אם `spot` אינו מופיע ב-`parking_spots`, ואחרת `False`.
סעיף ג
בודקים `check_spot(spot)` (תפוס – הודעה ו-`False`); מוצאים ב-`limits` את המכסה של `company` וסופרים ב-`cars` את רכבי החברה (מכסה נוצלה – הודעה ו-`False`); אחרת יוצרים `CompanyCar`, מוסיפים אותו ל-`cars` ואת `spot` ל-`parking_spots`, ומחזירים `True`.
1. בדיקת המקום: משתמשים ב-`check_spot` מסעיף ב. אם המקום תפוס – מדפיסים הודעה ומחזירים `False`.
2. מציאת המכסה של החברה: עוברים על `self.limits` ומחפשים את העצם שבו `company_name` שווה ל-`company`. את `company_limit` שלו שומרים במשתנה `limit`. אם החברה לא מופיעה ברשימת המגבלות, לא הוקצתה לה מכסה – `limit` נשאר 0, והרכב לא יוכנס.
3. כמה מקומות החברה כבר מנצלת: סופרים ב-`self.cars` את הרכבים שה-`company` שלהם הוא החברה הזו.
4. אם מספר הרכבים של החברה כבר הגיע למכסה (`used >= limit`) – המכסה נוצלה: מדפיסים הודעה ומחזירים `False`.
5. אחרת יוצרים עצם חדש `CompanyCar` עם הפרטים שהתקבלו, ומוסיפים גם אותו ל-`cars` וגם את `spot` ל-`parking_spots`, כדי ששתי הרשימות המקבילות יישארו מתואמות. מחזירים `True`.
(לפי ההנחה בשאלה יש מקומות פנויים בחניון, ולכן אין צורך לבדוק את הקיבולת 150, והרכב לא נמצא כבר בחניון.)
def park_car(self, license, manufacturer, company, spot):
# 1. האם המקום פנוי?
if not self.check_spot(spot):
print("Spot", spot, "is taken")
return False
# 2. המכסה של החברה
limit = 0
for lim in self.limits:
if lim.company_name == company:
limit = lim.company_limit
# 3. כמה רכבים של החברה כבר חונים
used = 0
for car in self.cars:
if car.company == company:
used += 1
# 4. האם המכסה נוצלה?
if used >= limit:
print("Company", company, "has used its quota")
return False
# 5. חונים את הרכב
self.cars.append(CompanyCar(license, manufacturer, company))
self.parking_spots.append(spot)
return Trueדוגמה: חניון עם המגבלות `CompanyLimit("Intel", 2)` ו-`CompanyLimit("Wix", 1)`.
1. `park_car("111", "Mazda", "Intel", "A4")` – המקום פנוי, ל-Intel 0 רכבים מתוך 2 – מוחזר `True`.
2. `park_car("222", "Kia", "Wix", "A4")` – המקום A4 תפוס – הודעה ו-`False`.
3. `park_car("222", "Kia", "Wix", "P10")` – ל-Wix 0 מתוך 1 – מוחזר `True`.
4. `park_car("333", "Kia", "Wix", "Q21")` – ל-Wix כבר רכב אחד מתוך 1 – הודעה ו-`False`.
תשובה: הפונקציה `park_car` בודקת שהמקום פנוי ושהחברה לא ניצלה את מכסתה (לפי `limits` ומספר רכביה ב-`cars`); אם אחד התנאים נכשל – מדפיסה הודעה ומחזירה `False`, ואחרת מוסיפה `CompanyCar` חדש ל-`cars` ואת `spot` ל-`parking_spots` ומחזירה `True`.
שאלה 10 · רקורסיה: חזקה, ריבוע שלם והדפסת ספרות
נתונה הפונקציה `what` המקבלת שני מספרים שלמים חיוביים `a` ו-`b` (גדולים מאפס). (`n=1` הינו ערך ברירת מחדל של `n`, במידה ולא מסופק ערך ל-`n` בעת קריאה לפונקציה).
def what(a, b, n=1):
if a == 1:
return b == 1
if n == b:
return True
if n > b:
return False
return what(a, b, n * a)מה תהיה תוצאת זימון הפונקציה `what(2, 15)`? יש להראות מעקב.
תנו דוגמה למספר דו-ספרתי `b` שעבורו תוצאת זימון הפונקציה `what(3, b)` תהיה `True`.
מה מבצעת הפונקציה `what(a, b)` באופן כללי עבור שני מספרים שלמים חיוביים?
נתונה הפונקציה `why` המקבלת מספר שלם `n`. `x=None`, ערך ברירת המחדל של `x`.
def why(n, x = None):
if x is None:
x = n
if n > x * x:
return False
if n < x * x:
return why(n, x - 1)
return Trueמה תהיה תוצאת זימון הפונקציה `why(10)`? יש להראות מעקב.
תנו דוגמה למספר דו-ספרתי `n` שעבורו תוצאת זימון הפונקציה `why(n)` תהיה `True`.
מה מבצעת הפונקציה `why` באופן כללי עבור מספר שלם `n`? יש להתייחס למקרים שונים של n.
נתונה הפונקציה `display` המקבלת מספר שלם:
def display(n):
if n > 0:
display(n // 10)
print(n % 10, end="")
display(n // 10)מה יהיה פלט עבור זימון הפונקציה `display(12)`? יש להראות מעקב.
מה יהיה פלט עבור זימון הפונקציה `display(123)`?
מה יהיה פלט עבור זימון הפונקציה `display (1234)`?
◂ פתרון מלא לשאלה 10
סעיף א
`False`.
מה עוקבים: בכל קריאה `n` מוכפל ב-`a = 2`, עד ש-`n` שווה ל-`b = 15` (מוחזר `True`) או עובר אותו (מוחזר `False`).
הערך `False` חוזר דרך כל הקריאות עד הקריאה המקורית. (15 אינו חזקה של 2: הוא בין ל-.)
תשובה: `what(2, 15)` מחזירה `False`.
`b = 27` (או `b = 81`).
מה צריך: עם `a = 3` הערכים של `n` הם (חזקות של 3). מוחזר `True` אם `b` שווה לאחד מהם. החזקות הדו-ספרתיות של 3 הן ו-.
מעקב עבור `b = 27`:
תשובה: `b = 27` (גם `b = 81` מתאים).
מחזירה `True` אם `b` הוא חזקה שלמה אי-שלילית של `a` (, ), ואחרת `False`.
1. `n` מתחיל ב-1 ובכל קריאה מוכפל ב-`a`, ולכן הוא עובר על הערכים .
2. אם `n` הגיע בדיוק ל-`b` – מוחזר `True`, כלומר עבור כלשהו. אם `n` עבר את `b` – אף חזקה של `a` לא שווה ל-`b` (החזקות רק גדלות), ומוחזר `False`.
3. המקרה `a == 1` מטופל בנפרד, כי שם `n` היה נשאר 1 לנצח (רקורסיה אינסופית): החזקה היחידה של 1 היא 1, ולכן מוחזר `True` רק אם `b == 1`.
4. כיוון ש-, עבור `b = 1` מוחזר `True` לכל `a`.
תשובה: `what(a, b)` בודקת אם `b` הוא חזקה של `a`, כלומר אם קיים שלם כך ש- (מחזירה `True` אם כן, `False` אם לא).
סעיף ב
`False`.
מה עוקבים: בקריאה הראשונה `x` מקבל את הערך `n = 10`. בכל קריאה משווים את `n` ל-: אם מקטינים את `x` ב-1, אם מחזירים `False`, ואם הם שווים – `True`.
`x` "דילג" מ-4 () ל-3 () בלי לפגוש , ולכן מוחזר `False`.
תשובה: `why(10)` מחזירה `False`.
`n = 16` (או כל ריבוע דו-ספרתי: 25, 36, 49, 64, 81).
מה צריך: מוחזר `True` רק כשמגיעים ל-`x` שעבורו , כלומר כש-`n` הוא ריבוע של מספר שלם. הריבועים הדו-ספרתיים הם 16, 25, 36, 49, 64, 81.
מעקב קצר עבור `n = 16`: : ; : ; ... ; : ; : – מוחזר `True`.
תשובה: `n = 16` (וגם 25, 36, 49, 64 או 81).
עבור מחזירה `True` אם `n` ריבוע שלם (0, 1, 4, 9, ...) ו-`False` אחרת; עבור הרקורסיה אינה נעצרת (`RecursionError`).
ההסבר: הפונקציה מתחילה ב- ומקטינה את `x` כל עוד . היא נעצרת ב-`x` הגדול ביותר שעבורו , ושם מחזירה `True` אם ו-`False` אם .
1. : מקיים , ו-`x` יורד בהדרגה. מכיוון ש-, הירידה נעצרת לכל היותר ב-. מוחזר `True` אם ורק אם `n` הוא ריבוע של מספר שלם (1, 4, 9, 16, ...), ואחרת `False`. לדוגמה `why(1)` מחזירה `True` מיד (), ו-`why(2)` מחזירה `False` (, ואז ).
2. : ו-, כלומר אף אחד מהתנאים , לא מתקיים, ומוחזר `True` (0 הוא ריבוע של 0).
3. : שלילי, ו- חיובי, ולכן תמיד . `x` יורד ל-, ו- רק גדל, כך שהתנאי לעולם לא משתנה. הרקורסיה אינה מגיעה לתנאי עצירה – רקורסיה אינסופית, שמסתיימת בשגיאה (`RecursionError`, חריגה מעומק הרקורסיה).
תשובה: עבור הפונקציה בודקת אם `n` הוא ריבוע של מספר שלם (מחזירה `True` אם כן, `False` אם לא); עבור היא נכנסת לרקורסיה אינסופית ומסתיימת בשגיאה.
סעיף ג
`121`
מה עוקבים: כל קריאה עם מבצעת שלושה דברים לפי הסדר: קריאה ל-`display(n // 10)`, הדפסת ספרת האחדות `n % 10`, ושוב קריאה ל-`display(n // 10)`. קריאה עם לא עושה דבר.
תשובה: הפלט הוא `121`.
`1213121`
רעיון: `display(123)` מדפיסה את הפלט של `display(12)`, אחריו את הספרה , ושוב את הפלט של `display(12)`.
מסעיף ג.1 הפלט של `display(12)` הוא `121`, ולכן:
`121` + `3` + `121` = `1213121`
תשובה: הפלט הוא `1213121`.
`121312141213121`
רעיון: באותו אופן, `display(1234)` מדפיסה את הפלט של `display(123)`, אחריו את הספרה , ושוב את הפלט של `display(123)`.
מסעיף ג.2 הפלט של `display(123)` הוא `1213121`, ולכן:
`1213121` + `4` + `1213121` = `121312141213121`
(באופן כללי, עבור מספר בן ספרות מודפסות ספרות; כאן .)
תשובה: הפלט הוא `121312141213121`.