מבחן מה"ט אלגוריתמיקה ותכנות (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 · מחרוזת תקינה: בדיקה וספירה
מחרוזת "תקינה" היא מחרוזת העונה על שני תנאים:
•אורך המחרוזת זוגי;
•התו הראשון זהה לתו האחרון ותו זה אינו מופיע במקומות האחרים של המחרוזת.
לדוגמה: המחרוזת "Abbc1A" היא "מחרוזת תקינה".
המחרוזת "Abc1A" אינה "מחרוזת תקינה".
המחרוזת "Abbc1D" אינה "מחרוזת תקינה".
המחרוזת "AbAc1A" אינה "מחרוזת תקינה".
כתבו פונקציה המקבלת מחרוזת ובודקת אם היא "מחרוזת תקינה". אם כן – הפונקציה תחזיר ערך `True`, ואם לא – הפונקציה תחזיר ערך `False`.
כותרת הפונקציה:
def is_valid(s):כתבו קטע קוד הקולט 30 מחרוזות. הקטע יחשב וידפיס את מספר "המחרוזות התקינות" ואת מספר המחרוזות שאינן תקינות. יש להשתמש בפונקציה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 1
סעיף א
בודקים שהאורך זוגי וגדול מ-0, ש-`s[0] == s[-1]`, ושהתו הראשון לא מופיע באף אחד מהמקומות 1 עד `len(s)-2`; אם כל התנאים מתקיימים מחזירים `True`.
מבוקש: פונקציה שמחזירה `True` רק אם מתקיימים שני התנאים של "מחרוזת תקינה".
רעיון הפתרון:
1. בודקים את האורך: אם `len(s) % 2 != 0` המחרוזת אינה תקינה. מחרוזת ריקה (אורך 0) היא אמנם באורך זוגי, אבל אין לה תו ראשון ותו אחרון, ולכן גם עבורה מחזירים `False` (וכך גם נמנעת גישה ל-`s[0]` במחרוזת ריקה).
2. בודקים שהתו האחרון `s[n-1]` שווה לתו הראשון `s[0]`. אם לא – מחזירים `False`.
3. עוברים על "המקומות האחרים" – האינדקסים 1 עד `n-2` – ואם אחד מהם שווה לתו הראשון מחזירים `False` מיד.
4. אם עברנו את כל הבדיקות, המחרוזת תקינה ומחזירים `True`.
def is_valid(s):
n = len(s)
if n == 0 or n % 2 != 0: # אורך 0 או אורך אי-זוגי
return False
first = s[0]
if s[n - 1] != first: # התו האחרון שונה מהראשון
return False
for i in range(1, n - 1): # התווים שבין הראשון לאחרון
if s[i] == first:
return False
return Trueבדיקה על הדוגמאות:
- "Abbc1A": אורך 6 (זוגי), ראשון ואחרון 'A', ובאמצע "bbc1" אין 'A' – מוחזר `True`.
- "Abc1A": אורך 5 (אי-זוגי) – מוחזר `False`.
- "Abbc1D": 'A' שונה מ-'D' – מוחזר `False`.
- "AbAc1A": 'A' מופיע גם באינדקס 2 – מוחזר `False`.
סיבוכיות: מעבר אחד על המחרוזת, .
תשובה: הפונקציה `is_valid` שלמעלה.
סעיף ב
לולאה של 30 קליטות; לכל מחרוזת מזמנים `is_valid` ומגדילים את המונה המתאים (תקינות / לא תקינות); בסוף מדפיסים את שני המונים.
מבוקש: לקלוט 30 מחרוזות ולספור כמה מהן תקינות וכמה אינן תקינות.
רעיון הפתרון:
1. מאתחלים שני מונים ל-0: `valid_count` למחרוזות התקינות ו-`invalid_count` לשאינן תקינות.
2. מספר המחרוזות ידוע מראש (30), ולכן משתמשים בלולאת `for` עם `range(30)`.
3. בכל סיבוב קולטים מחרוזת ומזמנים את `is_valid` מסעיף א: אם הוחזר `True` מגדילים את `valid_count`, אחרת את `invalid_count`.
4. אחרי הלולאה מדפיסים את שני המונים.
valid_count = 0
invalid_count = 0
for i in range(30):
s = input()
if is_valid(s):
valid_count += 1
else:
invalid_count += 1
print("valid strings:", valid_count)
print("invalid strings:", invalid_count)בכל סיבוב בדיוק אחד מהמונים גדל, ולכן בסוף סכומם הוא 30. לדוגמה, אם נקלטו 15 פעמים "Abbc1A" ו-15 פעמים "x", יודפסו 15 ו-15.
תשובה: קטע הקוד שלמעלה.
שאלה 2 · הספרה המקסימלית ומינימום הספרות המקסימליות
כתבו פונקציה המקבלת מספר שלם חיובי ומחזירה את הספרה המקסימלית (הגדולה ביותר) המופיעה בו.
עבור המספר 12734 הפונקציה תחזיר 7.
כותרת הפונקציה:
def max_digit(num):כתבו פונקציה המקבלת רשימה של מספרים שלמים חיוביים. עבור כל איבר ברשימה, הפונקציה תמצא את הספרה הגדולה ביותר ותחזיר את הערך המינימלי (הקטן ביותר) מבין כל הספרות המקסימליות שנמצאו.
עבור הרשימה `arr = [1283, 45, 1971, 613]` הפונקציה תחזיר 5.
כותרת הפונקציה:
def min_of_max_digits(arr):◂ פתרון מלא לשאלה 2
סעיף א
מפרקים את המספר לספרות בעזרת `% 10` ו-`// 10` ושומרים את הספרה הגדולה ביותר; עבור 12734 מוחזר 7.
מבוקש: הספרה הגדולה ביותר במספר.
רעיון הפתרון:
1. `num % 10` היא ספרת האחדות, ו-`num // 10` מוחק אותה. חוזרים על כך עד ש-`num` מגיע ל-0, וכך עוברים על כל הספרות.
2. מחזיקים משתנה `max_d` עם הספרה הגדולה ביותר שנמצאה עד כה. מאתחלים אותו ל-0, שאינו גדול מאף ספרה, וכל ספרה גדולה ממנו מחליפה אותו.
3. בסוף מחזירים את `max_d`.
def max_digit(num):
max_d = 0
while num > 0:
dig = num % 10 # ספרת האחדות
if dig > max_d:
max_d = dig
num = num // 10 # מחיקת ספרת האחדות
return max_dמעקב עבור 12734: הספרות מתקבלות בסדר 4, 3, 7, 2, 1; `max_d` משתנה ל-4, נשאר 4, משתנה ל-7, ונשאר 7 עד הסוף. מוחזר 7.
מספר הסיבובים הוא מספר הספרות של המספר.
תשובה: הפונקציה `max_digit` שלמעלה.
סעיף ב
מחשבים `max_digit` לכל איבר ושומרים את הקטן מבין הערכים; עבור הדוגמה מוחזר 5.
מבוקש: המינימום מבין הספרות המקסימליות של איברי הרשימה.
רעיון הפתרון:
1. מאתחלים את `min_val` לספרה המקסימלית של האיבר הראשון, `max_digit(arr[0])` – כך ההשוואה מתחילה מערך אמיתי מהרשימה.
2. עוברים על שאר האיברים, מחשבים לכל אחד את `max_digit`, ואם התוצאה קטנה מ-`min_val` מעדכנים אותו.
3. מחזירים את `min_val`.
def min_of_max_digits(arr):
min_val = max_digit(arr[0])
for i in range(1, len(arr)):
cur = max_digit(arr[i])
if cur < min_val:
min_val = cur
return min_valבדיקה על הדוגמה:
מוחזר 5.
תשובה: הפונקציה `min_of_max_digits` שלמעלה; עבור הדוגמה היא מחזירה 5.
שאלה 3 · מעקב: השוואת ספרה ראשונה ואורך מספרים
נתונה הפונקציה `what` המקבלת שני מספרים שלמים חיוביים `num1` ו-`num2`:
def what(num1, num2):
if num1 == num2:
return False
while num1 > 9 and num2 > 9:
num1 = num1 // 10
num2 = num2 // 10
return num1 == num2תנו דוגמה למספר שלם וחיובי `num` שעבורו זימון הפונקציה `what(1234, num)` יחזיר ערך `True`.
מה מבצעת הפונקציה `what` באופן כללי?
נתונה הפונקציה `secret` המקבלת שתי רשימות המכילות מספרים שלמים חיוביים ומשתמשת בפונקציה `what`:
def secret(a, b):
for i in range(len(a)):
flag = False
for k in range(len(b)):
if what(a[i], b[k]):
flag = True
if not flag:
return False
return Trueנתונה רשימת מספרים שלמים `a = [46, 127, 415, 104, 491, 371, 49]`
תנו דוגמה לרשימה `b` בעלת מספר האיברים הקטן ביותר שעבורו זימון הפונקציה `secret(a, b)` יחזיר ערך `True`.
האם לכל זוג רשימות של מספרים שלמים חיוביים `a` ו-`b`, תוצאת זימון הפונקציה `secret(a, b)` תהיה זהה לתוצאת זימון הפונקציה `secret(b, a)`? הסבירו את תשובתכם.
מה מבצעת הפונקציה `secret` באופן כללי?
◂ פתרון מלא לשאלה 3
סעיף א
למשל `num = 1000` (כל מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234).
מבוקש: מספר `num` כך ש-`what(1234, num)` יחזיר `True`.
1. אם `num == 1234` מוחזר מיד `False`, ולכן `num` חייב להיות שונה מ-1234.
2. הלולאה מחלקת את שני המספרים ב-10 כל עוד שניהם גדולים מ-9. בסופה מוחזר `num1 == num2`.
3. נבחר `num = 1000` ונעקוב:
4. הלולאה נעצרת עם `num1 = 1` ו-`num2 = 1`, ולכן מוחזר `1 == 1`, כלומר `True`.
תשובה: `num = 1000` (גם 1999, 1500 וכדומה).
מחזירה `True` אם המספרים שונים זה מזה, יש להם אותו מספר ספרות ואותה ספרה שמאלית (ראשונה); אחרת `False`.
1. אם המספרים שווים – מוחזר `False`.
2. הלולאה מוחקת בכל סיבוב את ספרת האחדות משני המספרים, ונעצרת ברגע שאחד מהם הפך לחד-ספרתי.
3. אם למספרים אותו מספר ספרות, שניהם הופכים לחד-ספרתיים באותו סיבוב, וכל אחד מהם הוא הספרה השמאלית שלו. אז מוחזר `True` אם ורק אם הספרות השמאליות שוות.
4. אם למספרים מספר ספרות שונה, כשהקצר מביניהם הופך לחד-ספרתי (לכל היותר 9), הארוך עדיין גדול מ-9, ולכן ההשוואה מחזירה `False`.
תשובה: הפונקציה מחזירה `True` אם `num1` ו-`num2` שונים זה מזה, בעלי אותו מספר ספרות ומתחילים באותה ספרה (הספרה השמאלית); אחרת היא מחזירה `False`.
סעיף ב
`b = [47, 100, 400, 300]` – ארבעה איברים, זה המספר הקטן ביותר האפשרי.
נתון: `a = [46, 127, 415, 104, 491, 371, 49]`. מבוקש: רשימה `b` קצרה ככל האפשר כך ש-`secret(a, b)` יחזיר `True`.
1. `secret` מחזירה `True` רק אם לכל איבר `a[i]` יש ב-`b` לפחות איבר אחד שעבורו `what(a[i], b[k])` הוא `True`, כלומר מספר שונה מ-`a[i]`, באותו מספר ספרות ועם אותה ספרה שמאלית (סעיף א2).
2. נחלק את איברי `a` לקבוצות לפי (מספר ספרות, ספרה שמאלית):
3. כל איבר של `b` יכול לשמש רק קבוצה אחת (יש לו מספר ספרות אחד וספרה שמאלית אחת), ולכן צריך לפחות 4 איברים ב-`b`.
4. בכל קבוצה בוחרים מספר שונה מכל איברי הקבוצה: 47 (שונה מ-46 ומ-49), 100 (שונה מ-127 ומ-104), 400 (שונה מ-415 ומ-491), 300 (שונה מ-371).
5. בדיקה: 46 ו-49 מתאימים ל-47, 127 ו-104 ל-100, 415 ו-491 ל-400, ו-371 ל-300. לכל איבר של `a` הדגל `flag` הופך ל-`True`, ולכן מוחזר `True`.
שימו לב: אסור לבחור למשל 46 עבור הקבוצה הראשונה, כי `what(46, 46)` מחזירה `False`, ואז 46 שב-`a` לא היה מוצא בן זוג.
תשובה: `b = [47, 100, 400, 300]` (ארבעה איברים).
לא. למשל עבור `a = [12]`, `b = [13, 5]`: `secret(a, b)` מחזירה `True` ו-`secret(b, a)` מחזירה `False`.
1. `secret(a, b)` בודקת שלכל איבר של `a` יש "בן זוג" ב-`b`, אבל לא בודקת דבר על איברי `b` שלא שימשו. הבדיקה אינה סימטרית.
2. דוגמה נגדית: `a = [12]`, `b = [13, 5]`.
•`secret(a, b)`: עבור 12 קיים 13 – אותו מספר ספרות, אותה ספרה שמאלית ושונה ממנו, כלומר `what(12, 13)` מחזירה `True`. מוחזר `True`.
•`secret(b, a)`: עבור 13 קיים 12, אבל עבור 5 אין ב-`a` אף מספר חד-ספרתי, ולכן `flag` נשאר `False` ומוחזר `False`.
תשובה: לא, התוצאה תלויה בסדר הפרמטרים; בדוגמה שלמעלה `secret(a, b)` היא `True` ו-`secret(b, a)` היא `False`.
מחזירה `True` אם לכל מספר ב-`a` יש ב-`b` מספר שונה ממנו בעל אותו מספר ספרות ואותה ספרה שמאלית; אחרת `False`.
1. הלולאה החיצונית עוברת על כל איבר `a[i]`.
2. הלולאה הפנימית מחפשת ב-`b` איבר שעבורו `what(a[i], b[k])` היא `True`, ואם נמצא כזה – `flag` הופך ל-`True`.
3. אם עבור איבר כלשהו של `a` לא נמצא איבר כזה, מוחזר `False` מיד. אם כל האיברים עברו – מוחזר `True`.
תשובה: הפונקציה בודקת אם לכל מספר ברשימה `a` קיים ברשימה `b` מספר שונה ממנו, בעל אותו מספר ספרות ומתחיל באותה ספרה; אם כן היא מחזירה `True`, אחרת `False`.
שאלה 4 · מחלקת מחשב נייד ופונקציות על רשימה
מעבדת מחשבים החליטה למחשב את ניהול המחשבים הניידים המגיעים אליה לתיקון. לשם כך הוגדרה המחלקה `Laptop`. למחלקה התכונות הבאות:
•`serialNum` – (מחרוזת) - מספר סידורי של המחשב;
•`ownerName` – (מחרוזת) - שם בעל המחשב;
•`ramSize` – (מספר שלם) - זיכרון ה-RAM של המחשב (ב-GB);
•`isTouchScreen` – (בוליאני) - האם למחשב יש מסך מגע? (כן – `True`, לא – `False`);
•`isRepaired` – (בוליאני) - האם המחשב תוקן ומוכן לאיסוף? (כן – `True`, לא – `False`).
כתבו במחלקה `Laptop` את הפונקציה הבונה (`__init__`) המקבלת כפרמטרים את המספר הסידורי ואת שם הבעלים בלבד. הפונקציה תאתחל את שאר התכונות כך שהמחשב יהיה בעל זיכרון RAM של 8 GB, ללא מסך מגע, ואינו מוכן לאיסוף.
כתבו פונקציה חיצונית המקבלת רשימה של מחשבים ניידים (רשימת אובייקטים מטיפוס `Laptop`) ומחזירה את מספר המחשבים שהם בעלי מסך מגע וגם הזיכרון שלהם הוא לפחות 8 GB.
כתבו פונקציה חיצונית המקבלת רשימה של מחשבים ניידים (רשימת אובייקטים מטיפוס `Laptop`) ומדפיסה את שמות הבעלים של המחשבים עם מסך מגע המוכנים לאיסוף.
אם אין אף מחשב כזה (שמוכן לאיסוף וגם בעל מסך מגע), הפונקציה תדפיס הודעה מתאימה.
◂ פתרון מלא לשאלה 4
סעיף א
`__init__(self, serialNum, ownerName)` שומרת את שני הפרמטרים ומאתחלת `ramSize = 8`, `isTouchScreen = False`, `isRepaired = False`.
מבוקש: פונקציה בונה עם שני פרמטרים שמאתחלת את כל חמש התכונות.
1. המספר הסידורי ושם הבעלים מתקבלים כפרמטרים ונשמרים בתכונות `self.serialNum` ו-`self.ownerName`.
2. שלוש התכונות האחרות מקבלות ערכים קבועים לפי הדרישה: זיכרון של 8 GB – `ramSize = 8`; ללא מסך מגע – `isTouchScreen = False`; אינו מוכן לאיסוף – `isRepaired = False`.
class Laptop:
def __init__(self, serialNum, ownerName):
self.serialNum = serialNum
self.ownerName = ownerName
self.ramSize = 8
self.isTouchScreen = False
self.isRepaired = Falseלדוגמה, `Laptop("SN-17", "Dana")` יוצר מחשב של Dana עם 8 GB, בלי מסך מגע, שעדיין לא תוקן.
תשובה: הפונקציה הבונה שלמעלה.
סעיף ב
עוברים על הרשימה וסופרים את המחשבים שעבורם `isTouchScreen` הוא `True` וגם `ramSize >= 8`; מחזירים את המונה.
מבוקש: מספר המחשבים שמקיימים שני תנאים יחד.
1. הפונקציה חיצונית (לא בתוך המחלקה), ולכן היא ניגשת לתכונות דרך כל אובייקט ברשימה: `lap.isTouchScreen`, `lap.ramSize`.
2. "לפחות 8 GB" פירושו `ramSize >= 8` (כולל 8).
3. שני התנאים צריכים להתקיים יחד, ולכן מחברים אותם ב-`and`. לכל מחשב שמקיים אותם מגדילים מונה, ובסוף מחזירים אותו.
def count_touch_8gb(laptops):
count = 0
for lap in laptops:
if lap.isTouchScreen and lap.ramSize >= 8:
count += 1
return countלדוגמה, עבור שלושה מחשבים: מסך מגע עם 8 GB, מסך מגע עם 4 GB, ומסך מגע עם 16 GB – מוחזר 2.
תשובה: הפונקציה `count_touch_8gb` שלמעלה.
סעיף ג
מדפיסים את `ownerName` של כל מחשב שבו `isTouchScreen` וגם `isRepaired`; דגל `found` מסמן אם הודפס שם, ואם לא – מדפיסים הודעה.
מבוקש: להדפיס את שמות הבעלים של המחשבים שיש להם מסך מגע ושתוקנו, ואם אין כאלה – להדפיס הודעה.
1. עוברים על כל המחשבים. אם `lap.isTouchScreen and lap.isRepaired` – מדפיסים את `lap.ownerName`.
2. כדי לדעת בסוף אם נמצא לפחות מחשב אחד, מחזיקים דגל `found` שמאותחל ל-`False` והופך ל-`True` בכל הדפסה.
3. אחרי הלולאה: אם `found` עדיין `False`, אף מחשב לא עמד בתנאים, ומדפיסים הודעה מתאימה.
def print_ready_touch_owners(laptops):
found = False
for lap in laptops:
if lap.isTouchScreen and lap.isRepaired:
print(lap.ownerName)
found = True
if not found:
print("No repaired touch-screen laptops")לדוגמה, אם רק המחשב של Dana הוא בעל מסך מגע ותוקן, יודפס `Dana`; עבור רשימה שאין בה מחשב כזה תודפס ההודעה.
תשובה: הפונקציה `print_ready_touch_owners` שלמעלה.
שאלה 5 · דרגת אי-זוגיות ורשימה מלאה לפי דרגות
נתונה הגדרה הבאה:
•"דרגת האי-זוגיות" של מספר שלם היא כמות הספרות האי-זוגיות במספר.
"דרגת האי-זוגיות" של המספר 12347 היא 3.
"דרגת האי-זוגיות" של המספר 1860 היא 1.
"דרגת האי-זוגיות" של המספר 246 היא 0.
"דרגת האי-זוגיות" של המספר (-3145) היא 3.
כתבו פונקציה המקבלת מספר שלם ומחזירה את "דרגת האי-זוגיות" שלו.
כותרת הפונקציה:
def odd_degree(num)•"דרגת השיא" של רשימה של מספרים שלמים היא "דרגת האי-זוגיות" הגבוהה ביותר שיש בה.
כתבו פונקציה המקבלת רשימה מספרים שלמים ומחזירה את "דרגת השיא" שלו.
כותרת הפונקציה:
def peek_degree(lst)•רשימה של מספרים שלמים נקרא "רשימה מלאה לפי דרגות האי-זוגיות" אם היא כוללת את כל דרגות האי-זוגיות מ-0 ועד "דרגת השיא" וכל דרגה מופיעה בה בדיוק פעם אחת.
כתבו פונקציה המקבלת רשימה של מספרים שלמים. הפונקציה מחזירה `True` אם הרשימה מלאה לפי דרגות האי-זוגיות, אחרת הפונקציה מחזירה `False`.
כותרת הפונקציה:
def is_full_list(lst)◂ פתרון מלא לשאלה 5
סעיף א
הופכים מספר שלילי לחיובי, מפרקים לספרות וסופרים את הספרות האי-זוגיות.
מבוקש: מספר הספרות האי-זוגיות במספר שלם (שיכול להיות גם שלילי).
רעיון הפתרון:
1. הסימן אינו ספרה, ולכן במספר שלילי עובדים עם הערך המוחלט (`num = -num`). זה גם הכרחי: ב-Python הפעולה `%` על מספר שלילי מחזירה תוצאה לא שלילית (למשל `-3145 % 10` הוא 5), ו-`//` מעגל כלפי מטה, כך שהלולאה לא הייתה מגיעה ל-0.
2. מפרקים את המספר לספרות בעזרת `% 10` ו-`// 10`.
3. ספרה אי-זוגית היא ספרה שהשארית שלה בחלוקה ב-2 היא 1. לכל ספרה כזו מגדילים מונה.
4. עבור המספר 0 הלולאה לא מתבצעת ומוחזר 0 – נכון, כי 0 היא ספרה זוגית.
def odd_degree(num):
if num < 0:
num = -num # הסימן לא משפיע על הספרות
count = 0
while num > 0:
if (num % 10) % 2 == 1: # ספרת האחדות אי-זוגית
count += 1
num = num // 10
return countבדיקה: 12347 – הספרות האי-זוגיות 1, 3, 7, ולכן 3. המספר 1860 – רק 1, ולכן 1. המספר 246 – אין, ולכן 0. המספר -3145 – אחרי הפיכת הסימן 3145, הספרות האי-זוגיות 3, 1, 5, ולכן 3.
תשובה: הפונקציה `odd_degree` שלמעלה.
סעיף ב
מקסימום של `odd_degree` על כל איברי הרשימה.
מבוקש: הערך הגדול ביותר של `odd_degree` בין איברי הרשימה.
1. מאתחלים את `max_deg` לדרגת האי-זוגיות של האיבר הראשון.
2. עוברים על שאר האיברים, מחשבים לכל אחד `odd_degree` בעזרת הפונקציה מסעיף א, ומעדכנים את `max_deg` אם התקבלה דרגה גבוהה יותר.
3. מחזירים את `max_deg`.
def peek_degree(lst):
max_deg = odd_degree(lst[0])
for i in range(1, len(lst)):
deg = odd_degree(lst[i])
if deg > max_deg:
max_deg = deg
return max_degלדוגמה, עבור `[12347, 1860, 246]` הדרגות הן 3, 1, 0, ומוחזר 3.
מניחים שהרשימה אינה ריקה (לרשימה ריקה אין "דרגת שיא").
תשובה: הפונקציה `peek_degree` שלמעלה.
סעיף ג
מחשבים את דרגת השיא `peak`, סופרים ברשימת מונים בגודל `peak+1` כמה מספרים יש מכל דרגה, ומחזירים `True` רק אם כל מונה שווה בדיוק ל-1.
מבוקש: לבדוק שכל דרגה מ-0 עד "דרגת השיא" מופיעה ברשימה בדיוק פעם אחת.
רעיון הפתרון:
1. מחשבים `peak = peek_degree(lst)` (סעיף ב). כל דרגה ברשימה היא בין 0 ל-`peak`.
2. יוצרים רשימת מונים `counts` בגודל `peak + 1`, כך ש-`counts[d]` סופר כמה מספרים ברשימה הם בעלי דרגה `d`.
3. עוברים על כל איברי הרשימה ומגדילים את `counts[odd_degree(x)]`. האינדקס תמיד בטווח, כי אף דרגה אינה גדולה מ-`peak`.
4. עוברים על המונים: מונה 0 פירושו דרגה חסרה, ומונה גדול מ-1 פירושו דרגה שמופיעה יותר מפעם אחת. בשני המקרים מחזירים `False`. אם כל המונים שווים ל-1 – מחזירים `True`.
def is_full_list(lst):
peak = peek_degree(lst)
counts = [0] * (peak + 1) # counts[d] = כמה מספרים בעלי דרגה d
for x in lst:
counts[odd_degree(x)] += 1
for d in range(peak + 1):
if counts[d] != 1: # דרגה חסרה או מופיעה יותר מפעם אחת
return False
return Trueדוגמאות:
•`[246, 1860, 13]`: הדרגות 0, 1, 2, דרגת השיא 2, וכל דרגה מופיעה פעם אחת – מוחזר `True`.
•`[1, 3, 5]`: הדרגות 1, 1, 1, דרגה 0 חסרה ודרגה 1 מופיעה שלוש פעמים – מוחזר `False`.
סיבוכיות: מעבר על הרשימה (פעם ב-`peek_degree` ופעם בספירה) ומעבר על המונים, כלומר , כאשר הוא מספר הספרות של המספר הארוך ביותר.
תשובה: הפונקציה `is_full_list` שלמעלה.
שאלה 6 · מזהי מכשירים בבית חכם: מחרוזות
במערכת "SmartHome" כל מכשיר מקבל מזהה ייחודי מסוג מחרוזת (`str`) המורכב משם החדר, התו נקודתיים (":") ושם מכשיר.
לדוגמה: "KITCHEN:LIGHT", "ROOM_2:TV", "MICROWAVE:KITCHEN".
כתבו פונקציה המקבלת מחרוזת המייצגת מזהה מכשיר. הפונקציה תבדוק אם המזהה תקין. אם כן – הפונקציה תחזיר `True`, ואם לא – הפונקציה תחזיר `False`. מזהה תקין הוא מחרוזת שמתקיימים בה שני תנאים:
•היא מכילה בדיוק פעם אחת את התו נקודתיים (":");
•התו נקודתיים אינו מופיע בתחילת המחרוזת ואינו מופיע בסופה.
כותרת הפונקציה:
def is_valid_device(device_id)כדי לייעל את צריכת החשמל, על המערכת לדעת אם שני מכשירים נמצאים באותו החדר.
כתבו פונקציה המקבלת שתי מחרוזות `dev1` ו-`dev2` המייצגות מזהי מכשירים. הפונקציה תבדוק אם שני המכשירים נמצאים באותו החדר. אם כן – הפונקציה תחזיר `True`, ואם לא – הפונקציה תחזיר `False`.
כותרת הפונקציה:
def are_in_same_room(dev1, dev2)כתבו פונקציה המקבלת רשימה של מחרוזות `all_devices` ומחרוזת נוספת `room_name`.
הפונקציה תחזיר רשימה חדשה המכילה רק את שמות המכשירים הנמצאים בחדר `room_name`.
כותרת הפונקציה:
def get_devices_in_room(all_devices, room_name)לדוגמה: עבור החדר `room_name = "KITCHEN"` ורשימת המכשירים `all_devices` הבאה
all_devices =["KITCHEN:LIGHT" ,"ROOM_2:TV" ,"KITCHEN:MICROWAVE"]הפונקציה תחזיר רשימה חדשה `["LIGHT", "MICROWAVE"]`.
אם לא נמצאו מכשירים בחדר המבוקש, הפונקציה תחזיר רשימה ריקה, כלומר רשימה באורך 0.
◂ פתרון מלא לשאלה 6
סעיף א
סופרים את התווים ':'; אם המספר שונה מ-1 – `False`; אחרת מחזירים `True` רק אם התו הראשון והתו האחרון אינם ':'.
מבוקש: לבדוק את שני התנאים של מזהה תקין.
רעיון הפתרון:
1. עוברים על תווי המחרוזת וסופרים כמה מהם הם ':'. אם המונה שונה מ-1 (אין נקודתיים, או שיש יותר מאחד) – המזהה אינו תקין.
2. אם יש בדיוק נקודתיים אחד, בודקים שהוא לא התו הראשון (`device_id[0]`) ולא התו האחרון (`device_id[-1]`). אחרת שם החדר או שם המכשיר היה ריק.
3. הבדיקה של סעיף 2 מתבצעת רק אחרי שהתברר שיש תו ':' במחרוזת, ולכן המחרוזת אינה ריקה ואין שגיאה בגישה ל-`device_id[0]`.
def is_valid_device(device_id):
count = 0
for ch in device_id:
if ch == ":":
count += 1
if count != 1:
return False
if device_id[0] == ":" or device_id[-1] == ":":
return False
return Trueדוגמאות: "KITCHEN:LIGHT" – `True`; "A:B:C" – שני נקודתיים, `False`; ":TV" – נקודתיים בהתחלה, `False`; "TV:" – נקודתיים בסוף, `False`; "TV" – אין נקודתיים, `False`.
תשובה: הפונקציה `is_valid_device` שלמעלה.
סעיף ב
שם החדר הוא החלק שלפני ':'; משווים את שמות החדרים של שני המזהים.
מבוקש: לבדוק אם לשני מזהים יש אותו שם חדר.
1. במזהה תקין יש בדיוק נקודתיים אחד, ושם החדר הוא כל מה שלפניו. מוצאים את מיקום הנקודתיים בעזרת `index(":")` וחותכים `device_id[:pos]`.
2. כדי לא לכתוב את אותו קוד פעמיים, כותבים פונקציית עזר `get_room` שמחזירה את שם החדר של מזהה.
3. מחזירים את תוצאת ההשוואה בין שני שמות החדרים. משווים את השם המלא ולא רק התחלה, כדי ש-"ROOM_2" ו-"ROOM_22" ייחשבו חדרים שונים.
def get_room(device_id):
pos = device_id.index(":")
return device_id[:pos] # החלק שלפני הנקודתיים
def are_in_same_room(dev1, dev2):
return get_room(dev1) == get_room(dev2)דוגמאות: "KITCHEN:LIGHT" ו-"KITCHEN:MICROWAVE" – שניהם בחדר "KITCHEN", מוחזר `True`; "KITCHEN:LIGHT" ו-"ROOM_2:TV" – מוחזר `False`.
תשובה: הפונקציה `are_in_same_room` שלמעלה.
סעיף ג
לכל מזהה מפצלים לפי ':'; אם שם החדר שווה ל-`room_name`, מוסיפים לרשימה חדשה את שם המכשיר (החלק שאחרי ':'); מחזירים את הרשימה.
מבוקש: רשימה חדשה של שמות המכשירים (בלי שם החדר) שנמצאים בחדר הנתון.
רעיון הפתרון:
1. מתחילים מרשימה ריקה `result`. אם אף מכשיר לא נמצא בחדר, היא תוחזר ריקה כנדרש.
2. לכל מזהה מוצאים את מיקום הנקודתיים `pos`. שם החדר הוא `dev[:pos]` ושם המכשיר הוא `dev[pos + 1:]`.
3. אם שם החדר שווה ל-`room_name`, מוסיפים לרשימה את שם המכשיר בלבד.
4. מחזירים את `result`. זו רשימה חדשה – הרשימה `all_devices` אינה משתנה.
def get_devices_in_room(all_devices, room_name):
result = []
for dev in all_devices:
pos = dev.index(":")
if dev[:pos] == room_name:
result.append(dev[pos + 1:]) # שם המכשיר - אחרי הנקודתיים
return resultמעקב על הדוגמה:
מוחזרת הרשימה `["LIGHT", "MICROWAVE"]`.
תשובה: הפונקציה `get_devices_in_room` שלמעלה.
שאלה 7 · מעקב: מחלקת ספרה מינימלית ומקסימלית
נתונה המחלקה `DigitInfo`:
class DigitInfo:
def __init__(self, num):
if num < 0:
num = num * -1
dig = num % 10
self.dig1 = dig
self.dig2 = dig
num = num // 10
while num > 0:
dig = num % 10
if dig < self.dig1:
self.dig1 = dig
elif dig > self.dig2:
self.dig2 = dig
num = num // 10
def __str__(self):
return str(self.dig1) + "," + str(self.dig2)
def combine(self):
return self.dig1 + self.dig2עקבו אחרי ביצוע קטע הקוד שלפניכם ורשמו מה יהיה הפלט:
info = DigitInfo(48291)
print(info)
print(info.combine())מהו הערך הגדול ביותר ומהו הערך הקטן ביותר שיכולה להחזיר הפונקציה `combine()`?
נתונה הפונקציה `Mystery`:
def mystery(arr):
temp1 = DigitInfo(arr[0])
temp2 = DigitInfo(arr[0])
ind1 = 0
ind2 = 0
for i in range(1, len(arr)):
cur = DigitInfo(arr[i])
if cur.combine() > temp1.combine():
temp2 = temp1
temp1 = cur
ind2 = ind1
ind1 = i
else:
if cur.combine() > temp2.combine():
temp2 = cur
ind2 = i
print(str(arr[ind1]) + " " + str(arr[ind2]))עקבו אחרי ביצוע קטע הקוד שלפניכם ורשמו מה יהיה הפלט:
a = [3458,45, 7341, 6, 13579, 86]
mystery(a)◂ פתרון מלא לשאלה 7
סעיף א
הפלט: `1,9` ובשורה הבאה `10`.
עוקבים אחרי הפונקציה הבונה עבור `num = 48291`.
1. `num` חיובי, ולכן אינו משתנה.
2. ספרת האחדות היא , ולכן `dig1 = 1`, `dig2 = 1`, ואחר כך `num = 4829`.
3. הלולאה עוברת על שאר הספרות מימין לשמאל:
אחרי הסיבוב הרביעי `num = 0` והלולאה נגמרת.
4. `print(info)` מזמן את `__str__`, שמחזירה `"1,9"`.
5. `combine()` מחזירה .
כלומר `dig1` היא הספרה הקטנה ביותר במספר ו-`dig2` הגדולה ביותר.
תשובה: הפלט הוא
1,9
10סעיף ב
הגדול ביותר 18 (למשל עבור 9), הקטן ביותר 0 (עבור 0).
1. כפי שראינו בסעיף א, `dig1` היא הספרה הקטנה ביותר ו-`dig2` הספרה הגדולה ביותר במספר, ו-`combine()` מחזירה את סכומן.
2. ערך מקסימלי: כל ספרה היא לכל היותר 9, ולכן הסכום לכל היותר . הוא מתקבל כשכל הספרות הן 9, למשל עבור `DigitInfo(9)` או `DigitInfo(99)`.
3. ערך מינימלי: כל ספרה היא לפחות 0, ולכן הסכום לפחות . הוא מתקבל עבור `DigitInfo(0)`: אז `dig1 = dig2 = 0` והלולאה אינה מתבצעת.
תשובה: הערך הגדול ביותר הוא 18 והקטן ביותר הוא 0.
סעיף ג
הפלט: `86 6`.
קודם מחשבים לכל איבר את הספרה הקטנה, הגדולה ואת `combine()`:
בהתחלה `temp1` ו-`temp2` הם שניהם `DigitInfo(3458)` (ערך 11), ו-`ind1 = ind2 = 0`.
מעקב אחרי הלולאה (`t1`, `t2` – ערכי `combine()` של `temp1` ו-`temp2`):
בסוף `ind1 = 5` ו-`ind2 = 3`, ולכן מודפס `arr[5]`, רווח, ו-`arr[3]`.
במקרה זה הפונקציה מדפיסה את שני המספרים עם ערכי `combine()` הגבוהים ביותר: הגבוה ביותר (86, ערך 14) והשני אחריו (6, ערך 12).
תשובה: הפלט הוא `86 6`.
שאלה 8 · פסגות במטריצה: בדיקה ורשימת ערכים
•מטריצה (רשימה של רשימות) מורכבת משורות ועמודות
•מסגרת המטריצה מורכבת מתאים הנמצאים בשורה 0, בעמודה 0, בשורה אחרונה ובעמודה אחרונה.
•תא פנימי במטריצה הוא איבר שאינו נמצא במסגרת המטריצה.
•תא פנימי במטריצה נקרא "פסגה" אם הערך המאוחסן בו גדול מכל הערכים שבשמונת שכניו (כלומר, התאים הסמוכים לו).
•התא במיקום (1,1) הוא "פסגה" כיוון שערכו (10) גדול מכל שכניו (המסומנים באפור).
•גם תא במיקום (3,2) הוא "פסגה" (ערכו 21).
•גם תא (1,4) הוא "פסגה".

כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום של תא: `row` (אינדקס שורה) ו-`col` (אינדקס עמודה). הפונקציה תבדוק אם האיבר במיקום זה הוא "פסגה". אם כן – הפונקציה תחזיר `True`, ואם לא – הפונקציה תחזיר `False`.
כותרת הפונקציה:
def is_peak(arr, row, col)כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr`. הפונקציה תחזיר רשימה המכילה את הערכים של כל "הפסגות" הקיימות במטריצה `arr`. אם אין שום "פסגה" במטריצה, הפונקציה תחזיר רשימה ריקה.
כותרת הפונקציה:
def get_peaks_list(arr)מהי סיבוכיות זמן הריצה של כל הפונקציות שכתבתם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
אם התא במסגרת מחזירים `False`; אחרת עוברים על ריבוע 3×3 סביבו ומחזירים `False` אם אחד השכנים גדול או שווה לערך התא; אחרת `True`.
מבוקש: לבדוק אם התא `(row, col)` הוא תא פנימי שערכו גדול ממש מכל שמונת שכניו.
רעיון הפתרון:
1. מספר השורות הוא `len(arr)` ומספר העמודות `len(arr[0])`.
2. לפי ההגדרה רק תא פנימי יכול להיות "פסגה". תא פנימי מקיים `1 <= row <= rows-2` וגם `1 <= col <= cols-2`. אם התא במסגרת (או מחוץ למטריצה) מחזירים `False`. זה גם מבטיח שלכל תא שנבדק יש שמונה שכנים בתוך המטריצה.
3. השכנים הם כל התאים בשורות `row-1` עד `row+1` ובעמודות `col-1` עד `col+1`, חוץ מהתא עצמו. עוברים עליהם בשתי לולאות מקוננות.
4. "גדול מכל הערכים" פירושו גדול ממש, ולכן אם שכן כלשהו גדול או שווה לערך התא – מחזירים `False` מיד.
5. אם אף שכן לא פסל את התא – מחזירים `True`.
def is_peak(arr, row, col):
rows = len(arr)
cols = len(arr[0])
# תא במסגרת אינו יכול להיות "פסגה"
if row <= 0 or row >= rows - 1 or col <= 0 or col >= cols - 1:
return False
for i in range(row - 1, row + 2):
for j in range(col - 1, col + 2):
if (i != row or j != col) and arr[i][j] >= arr[row][col]:
return False
return Trueבדיקה על הדוגמה: עבור `(1,1)` הערך 10 והשכנים 5, 4, 1, 1, 7, 6, 1, 7 – כולם קטנים מ-10, ולכן `True`. עבור `(3,1)` הערך 10 והשכן `(4,1)` שווה ל-10, ולכן `False`.
תשובה: הפונקציה `is_peak` שלמעלה.
סעיף ב
עוברים על כל התאים הפנימיים (שורות ועמודות 1 עד הלפני-אחרונה), ולכל תא שעבורו `is_peak` מחזירה `True` מוסיפים את ערכו לרשימה; עבור הדוגמה מתקבל `[10, 123, 21]`.
מבוקש: רשימת הערכים של כל הפסגות.
רעיון הפתרון:
1. מתחילים מרשימה ריקה `peaks`. אם לא תימצא אף פסגה, היא תוחזר ריקה כנדרש.
2. פסגה יכולה להיות רק בתא פנימי, ולכן עוברים על השורות 1 עד `len(arr)-2` ועל העמודות 1 עד `len(arr[0])-2` (`range(1, len(arr) - 1)` ו-`range(1, len(arr[0]) - 1)`).
3. לכל תא כזה מזמנים את `is_peak` מסעיף א, ואם הוא פסגה מוסיפים את ערכו `arr[i][j]` לרשימה.
4. מחזירים את `peaks`.
def get_peaks_list(arr):
peaks = []
for i in range(1, len(arr) - 1):
for j in range(1, len(arr[0]) - 1):
if is_peak(arr, i, j):
peaks.append(arr[i][j])
return peaksבדיקה על המטריצה שבאיור: התאים הפנימיים הם שורות 1–3 ועמודות 1–4. הפסגות הן `(1,1)` עם 10, `(1,4)` עם 123 ו-`(3,2)` עם 21; בכל שאר התאים הפנימיים יש שכן גדול או שווה (למשל `(2,3)` עם 10 והשכן 123). לכן מוחזר `[10, 123, 21]`.
במטריצה שאין בה תאים פנימיים (פחות משלוש שורות או שלוש עמודות) הלולאות לא מתבצעות ומוחזרת רשימה ריקה.
תשובה: הפונקציה `get_peaks_list` שלמעלה.
סעיף ג
`is_peak`: (לכל היותר 9 בדיקות); `get_peaks_list`: עבור מטריצה בת שורות ו- עמודות.
1. `is_peak`: הלולאות המקוננות עוברות על ריבוע של תאים בלבד, בלי קשר לגודל המטריצה. מספר הפעולות קבוע, ולכן הסיבוכיות .
2. `get_peaks_list`: עבור מטריצה בת שורות ו- עמודות עוברים על תאים פנימיים, ולכל אחד מזמנים את `is_peak` שעולה . סך הכול , כלומר סיבוכיות לינארית במספר התאים במטריצה.
תשובה: `is_peak` – ; `get_peaks_list` – .
שאלה 9 · מחלקות זמן, מסלול אוטובוס ומערכת קווים
חברת "דן" מעוניינת למחשב את שירותי המודיעין שלה עבור קווי האוטובוס בעיר. לצורך כך הוגדרו שלוש מחלקות: `Time`, `BusRoute` ו-`CityTransport`.
המחלקה `Time` מייצגת נקודת זמן לפי מספר שעות ומספר דקות. במחלקה הוגדרה הפעולה הבונה הבאה:
class Time:
def __init__(self, h, m):
self.hour = h
self.minute = mבמחלקה `Time` הוגדרה פונקציה `min_from_midnight` המחזירה את מספר הדקות שעברו מחצות (0:00). אין צורך לממש אותה!
כתבו במחלקה `Time` את הפונקציה `add` המקבלת את המספר השלם החיובי `min_to_add`.
הפונקציה תחזיר אובייקט חדש מסוג `Time` המייצג את נקודת הזמן לאחר הוספת `min_to_add` דקות לזמן הנוכחי. כותרת הפונקציה:
def add(self, min_to_add)לדוגמה, אם האובייקט הנוכחי הוא 8:30 והפונקציה קיבלה 45, יוחזר אובייקט חדש המייצג את נקודת הזמן 9:15.
המחלקה `BusRoute` מייצגת מסלול של קו אוטובוס. תכונות המחלקה:
•`line_no` – מספר קו (למשל: "61") – מטיפוס מחרוזת, `str`;
•`stops` – רשימת השמות של תחנות העצירה במסלול – מטיפוס רשימת מחרוזות, `list` של `str`;
•`durations` – רשימה מספרים שלמים, `list` של `int`.
הערך `k` ברשימה מציין את מספר הדקות הדרושות לאוטובוס כדי להגיע מתחנה `k` לתחנה `k+1`.
אם הרשימה `stops` הוא:
והרשימה `durations` הוא:
האוטובוס נוסע 12 דקות מעמידר לקניון איילון, 15 דקות מקניון איילון לבורסה, 10 דקות מהבורסה למיניסטור לונדון, 8 דקות ממיניסטור לונדון לכרמלית.
כתבו במחלקה `BusRoute` את שתי הפונקציות הבאות:
פונקציה בוליאנית המקבלת שמות של שתי תחנות `st1` ו-`st2` ובודקת האם ניתן להגיע מ-`st1` ל-`st2` באמצעות קו זה (כלומר, ששתיהן קיימות ברשימת תחנות ו-`st2` מופיעה אחרי `st1`).
כותרת הפונקציה:
def is_route_possible(self, st1, st2)פונקציה המקבלת שם של תחנת יעד `stop_name` וזמן יציאה למסלול `start_time`. הפונקציה תחזיר את זמן ההגעה לתחנה זו.
אפשר להניח שהתחנה `stop_name` קיימת במסלול.
כותרת הפונקציה:
def get_arrival_time(self, start_time, stop_name)המחלקה `CityTransport` מייצגת מערכת הקווים העירונית. למחלקה תכונה אחת:
•`routes` – רשימה קווי אוטובוס (רשימה של אובייקטים מסוג `BusRoute`)
כתבו במחלקה `CityTransport` את הפונקציה המקבלת תחנת מוצא ותחנת יעד. הפונקציה תדפיס מספרי הקווים (`line_no`) המאפשרים נסיעה מתחנת מוצא לתחנת יעד.
כותרת הפונקציה:
def print_relevant_lines(self, origin, destination)◂ פתרון מלא לשאלה 9
סעיף א
`total = self.min_from_midnight() + min_to_add` (מודולו ), ומחזירים `Time(total // 60, total % 60)`.
מבוקש: אובייקט `Time` חדש שמייצג את הזמן הנוכחי ועוד `min_to_add` דקות.
רעיון הפתרון:
1. הדרך הנוחה היא לעבור לדקות: `self.min_from_midnight()` נותנת את הזמן הנוכחי בדקות מחצות. מוסיפים לו את `min_to_add` ומקבלים את הזמן החדש בדקות.
2. אם הסכום עובר את חצות (1440 דקות ביממה, ), לוקחים שארית חלוקה ב-1440 כדי להתחיל יממה חדשה.
3. ממירים חזרה לשעות ודקות: שעות = `total // 60`, דקות = `total % 60`.
4. יוצרים ומחזירים אובייקט חדש; האובייקט הנוכחי (`self`) אינו משתנה.
class Time:
def __init__(self, h, m):
self.hour = h
self.minute = m
def add(self, min_to_add):
total = self.min_from_midnight() + min_to_add
total = total % (24 * 60) # מעבר חצות מתחיל יממה חדשה
return Time(total // 60, total % 60)בדיקה על הדוגמה: 8:30 הוא דקות מחצות. , ו-, , כלומר 9:15.
דוגמה למעבר חצות: 23:50 ועוד 20 דקות נותנים , ו-, כלומר 0:10.
תשובה: הפונקציה `add` שלמעלה.
סעיף ב
מחזירה `True` אם שתי התחנות ב-`stops` וגם `stops.index(st1) < stops.index(st2)`; אחרת `False`.
מבוקש: לבדוק ששתי התחנות קיימות במסלול ושהתחנה `st2` באה אחרי `st1`.
1. אם אחת התחנות אינה ברשימה `self.stops` (בדיקה בעזרת `in`) – אי אפשר לנסוע ביניהן בקו הזה, ומחזירים `False`. הבדיקה הזו באה קודם, כי `index` של ערך שאינו ברשימה גורם לשגיאה.
2. אם שתיהן קיימות, מוצאים את המיקום של כל אחת בעזרת `index`. האוטובוס נוסע רק קדימה במסלול, ולכן אפשר להגיע מ-`st1` ל-`st2` רק אם המיקום של `st1` קטן מהמיקום של `st2`.
3. אם `st1` ו-`st2` הן אותה תחנה, `st2` אינה מופיעה אחרי `st1`, וההשוואה `<` מחזירה `False`.
הקוד מופיע בתוך המחלקה המלאה בסוף סעיף 2.
דוגמה על המסלול שבשאלה: `is_route_possible("עמידר", "בורסה")` מחזירה `True` (מיקום 0 לפני מיקום 2), ו-`is_route_possible("בורסה", "עמידר")` מחזירה `False`.
תשובה: הפונקציה `is_route_possible` במחלקה `BusRoute` שבסעיף 2.
מוצאים `k = stops.index(stop_name)`, סוכמים `durations[0]` עד `durations[k-1]`, ומחזירים `start_time.add(total)`.
מבוקש: הזמן שבו האוטובוס, שיצא מתחנת המוצא של המסלול (תחנה 0) בזמן `start_time`, מגיע לתחנה `stop_name`.
1. מוצאים את המיקום `k` של התחנה ברשימה `stops` (התחנה קיימת, לפי הנתון).
2. כדי להגיע מתחנה 0 לתחנה `k` עוברים את הקטעים 0, 1, ..., `k-1`, ולכן זמן הנסיעה הוא `durations[0] + ... + durations[k-1]`. סוכמים אותם בלולאה.
3. את זמן ההגעה מקבלים בעזרת הפונקציה `add` מסעיף א: `start_time.add(total)`, שמחזירה אובייקט `Time` חדש.
4. אם `stop_name` היא תחנת המוצא (`k = 0`), הלולאה לא מתבצעת, ומוחזר זמן היציאה עצמו.
המחלקה עם שתי הפונקציות (הפונקציה הבונה לא נדרשה בשאלה ומופיעה כדי שהמחלקה תהיה שלמה):
class BusRoute:
def __init__(self, line_no, stops, durations):
self.line_no = line_no
self.stops = stops
self.durations = durations
def is_route_possible(self, st1, st2):
if st1 not in self.stops or st2 not in self.stops:
return False
return self.stops.index(st1) < self.stops.index(st2)
def get_arrival_time(self, start_time, stop_name):
k = self.stops.index(stop_name)
total = 0
for i in range(k): # הקטעים מתחנה 0 עד תחנה k
total += self.durations[i]
return start_time.add(total)דוגמה: יציאה ב-8:00 מעמידר, היעד "מיניסטור לונדון" (מיקום 3). זמן הנסיעה דקות, ולכן מוחזר 8:37. ליעד "כרמלית" – דקות, כלומר 8:45.
תשובה: הפונקציה `get_arrival_time` במחלקה שלמעלה.
סעיף ג
עוברים על `self.routes` ומדפיסים את `line_no` של כל קו שעבורו `is_route_possible(origin, destination)` מחזירה `True`.
מבוקש: להדפיס את מספרי כל הקווים שבהם אפשר לנסוע מ-`origin` ל-`destination`.
1. כל קו הוא אובייקט `BusRoute`, ובסעיף ב1 כבר כתבנו בו את `is_route_possible`, שבודקת בדיוק את זה. לכן אין צורך לבדוק את התחנות שוב.
2. עוברים על הרשימה `self.routes`, ולכל קו שעבורו `route.is_route_possible(origin, destination)` מחזירה `True` מדפיסים את `route.line_no`.
3. בנוסף, דגל `found` מאפשר להדפיס הודעה אם אין אף קו מתאים (לא נדרש, אבל מבהיר את הפלט).
class CityTransport:
def __init__(self, routes):
self.routes = routes
def print_relevant_lines(self, origin, destination):
found = False
for route in self.routes:
if route.is_route_possible(origin, destination):
print(route.line_no)
found = True
if not found:
print("No line from", origin, "to", destination)דוגמה: אם במערכת קו "61" עם המסלול שבשאלה וקו "5" עם המסלול בורסה → כרמלית, אז עבור `print_relevant_lines("בורסה", "כרמלית")` יודפסו 61 ו-5; עבור הכיוון ההפוך תודפס ההודעה, כי בשני הקווים כרמלית באה אחרי בורסה.
תשובה: הפונקציה `print_relevant_lines` שלמעלה.
שאלה 10 · מעקב רקורסיה: ספרות יורדות וחלוקת רשימה
נתונה הפונקציה `what` המקבלת מספר שלם חיובי `n` ופונקציית עזר בשם `what_helper`:
def what(n):
if n < 10:
return True
return what_helper(n // 10, n % 10)
def what_helper(n, k):
if n == 0:
return True
if n % 10 <= k:
return False
return what_helper(n // 10, n % 10)מה תהיה תוצאת זימון הפונקציה `what(8652)`? יש להראות מעקב.
תנו דוגמה למספר תלת-ספרתי `n` שעבורו תוצאת זימון הפונקציה `what(n)` תהיה `True`.
מה מבצעת הפונקציה `what(n)` באופן כללי עבור מספר שלם חיובי `n`?
נתונה הפונקציה `secret` המקבלת רשימה של מספרים שלמים ופונקציית עזר `secret_helper`
def secret(a):
secret_helper(a, 0, len(a) - 1)
def secret_helper(a, low, high):
if low < high:
if what(a[low]):
secret_helper(a, low + 1, high)
elif not what(a[high]):
secret_helper(a, low, high - 1)
else:
temp = a[low]
a[low] = a[high]
a[high] = temp
secret_helper(a, low + 1, high - 1)עקבו אחרי זימון הפונקציה `secret(a)` עבור הרשימה הבאה:
a = [17, 863, 19, 542, 123,542]רשמו מה תהיה התוצאה של הזימון. יש להראות מעקב.
תנו דוגמה של רשימה `b` הכוללת חמישה מספרים תלת-ספרתיים, כך שזימון הפונקציה `secret(b)` לא יגרום לשינוי ברשימה.
תנו דוגמה של רשימה `c` הכוללת חמישה מספרים תלת-ספרתיים, כך שזימון הפונקציה `secret(c)` יגרום להפיכת סדר איברים ברשימה.
מה מבצעת הפונקציה `secret` באופן כללי עבור רשימה של מספרים שלמים חיוביים?
◂ פתרון מלא לשאלה 10
סעיף א
`True`.
1. `what(8652)`: המספר אינו קטן מ-10, ולכן מזמנים `what_helper(865, 2)` (`8652 // 10 = 865`, `8652 % 10 = 2`).
2. מעקב אחרי הזימונים הרקורסיביים:
3. הערך `True` מוחזר לאורך כל שרשרת הזימונים אל `what(8652)`.
תשובה: `what(8652)` מחזירה `True`.
למשל `n = 321`.
1. לפי המעקב בסעיף 1, הפונקציה משווה כל ספרה לספרה שמימינה, ומחזירה `True` רק אם כל ספרה גדולה ממש מהספרה שמימינה.
2. נבחר `n = 321`: `what(321)` מזמנת `what_helper(32, 1)`; , ולכן `what_helper(3, 2)`; , ולכן `what_helper(0, 3)`, שמחזירה `True`.
תשובה: `n = 321` (גם 987, 520 וכדומה).
מחזירה `True` אם ספרות `n` יורדות ממש משמאל לימין (כל ספרה גדולה מזו שמימינה); אחרת `False`. מספר חד-ספרתי – `True`.
1. מספר חד-ספרתי מחזיר `True` מיד.
2. אחרת `what_helper` מקבלת את שאר המספר `n` ואת הספרה האחרונה שהוסרה `k`. בכל זימון היא משווה את ספרת האחדות של `n` (הספרה שמשמאל ל-`k`) עם `k`: אם היא קטנה או שווה ל-`k` – מוחזר `False`; אחרת ממשיכים עם הספרה הבאה.
3. כש-`n` מגיע ל-0 כל הזוגות של ספרות סמוכות נבדקו ולא נמצאה הפרה, ומוחזר `True`.
4. לכן `True` מוחזר בדיוק כאשר כל ספרה גדולה ממש מהספרה שמימינה, כלומר הספרות יורדות ממש משמאל לימין. למשל `what(8652)` היא `True`, אבל `what(8852)` היא `False` (שתי ספרות 8 סמוכות) וגם `what(123)` היא `False`.
תשובה: הפונקציה בודקת אם ספרות המספר מסודרות בסדר יורד ממש משמאל לימין; אם כן היא מחזירה `True`, אחרת `False`.
סעיף ב
הרשימה הופכת ל-`[542, 863, 542, 19, 123, 17]`.
1. קודם נחשב את `what` לכל ערך ברשימה (לפי סעיף א3 – האם הספרות יורדות ממש):
2. `secret(a)` מזמנת `secret_helper(a, 0, 5)`. מעקב:
3. הפונקציה אינה מחזירה ערך, אלא משנה את הרשימה עצמה.
תשובה: אחרי הזימון `a = [542, 863, 542, 19, 123, 17]`.
למשל `b = [321, 543, 987, 210, 765]` (כל המספרים עם ספרות יורדות).
1. החלפה מתבצעת רק כאשר `what(a[low])` היא `False` וגם `what(a[high])` היא `True`. אם כל המספרים ברשימה מקיימים `what`, הענף הראשון מתבצע תמיד, `low` רק גדל, ואף החלפה לא קורית.
2. נבחר חמישה מספרים תלת-ספרתיים עם ספרות יורדות ממש: `b = [321, 543, 987, 210, 765]`.
3. מעקב: `(0,4)` – `what(321)` True, `(1,4)` – `what(543)` True, `(2,4)` – `what(987)` True, `(3,4)` – `what(210)` True, `(4,4)` – עצירה. לא הייתה החלפה, והרשימה נשארת כפי שהייתה.
(גם רשימה שבה אף מספר אינו מקיים `what`, למשל `[123, 456, 789, 112, 345]`, לא תשתנה: אז `high` רק קטן.)
תשובה: `b = [321, 543, 987, 210, 765]`.
למשל `c = [123, 456, 789, 654, 321]`, שהופכת ל-`[321, 654, 789, 456, 123]`.
1. כדי שהסדר יתהפך, צריך שבזימון הראשון `(0, 4)` תתבצע החלפה בין `c[0]` ל-`c[4]`, ובזימון `(1, 3)` החלפה בין `c[1]` ל-`c[3]`. האיבר האמצעי `c[2]` נשאר במקומו גם בהיפוך, והרקורסיה נעצרת ב-`(2, 2)`.
2. החלפה מתבצעת רק כאשר `what(c[low])` היא `False` ו-`what(c[high])` היא `True`. לכן נדרש: `c[0]` ו-`c[1]` בלי ספרות יורדות, `c[3]` ו-`c[4]` עם ספרות יורדות, ו-`c[2]` כלשהו.
3. נבחר `c = [123, 456, 789, 654, 321]`:
4. התקבלה `[321, 654, 789, 456, 123]` – בדיוק הרשימה המקורית בסדר הפוך.
תשובה: `c = [123, 456, 789, 654, 321]`.
מסדרת מחדש את הרשימה כך שכל המספרים שספרותיהם יורדות ממש (`what` מחזירה `True`) נמצאים בתחילתה, ואחריהם כל שאר המספרים.
1. `low` מתקדם מההתחלה ו-`high` מהסוף. איבר בהתחלה שמקיים `what` כבר נמצא במקום הנכון, ו-`low` מדלג עליו; איבר בסוף שאינו מקיים `what` כבר במקום הנכון, ו-`high` מדלג עליו.
2. כאשר בצד שמאל יש איבר שאינו מקיים `what` ובצד ימין איבר שמקיים אותו – מחליפים ביניהם, ושני המצביעים מתקדמים.
3. כשהמצביעים נפגשים, כל האיברים שמשמאל מקיימים `what` וכל האיברים שמימין אינם מקיימים אותו.
4. זו חלוקה של הרשימה לשתי קבוצות (כמו בשלב החלוקה של מיון מהיר). הסדר הפנימי בכל קבוצה אינו נשמר בהכרח, כפי שראינו בסעיף 1.
תשובה: הפונקציה מסדרת את הרשימה כך שבתחילתה כל המספרים שספרותיהם יורדות ממש משמאל לימין, ובסופה כל שאר המספרים.