דילוג לתוכן המרכזי

מבחן מה"ט אלגוריתמיקה ותכנות (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):
(6 נקודות)
ב.

כתבו קטע קוד הקולט 30 מחרוזות. הקטע יחשב וידפיס את מספר "המחרוזות התקינות" ואת מספר המחרוזות שאינן תקינות. יש להשתמש בפונקציה שכתבתם בסעיף א'.

(6 נקודות)
◂ פתרון מלא לשאלה 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`.

סיבוכיות: מעבר אחד על המחרוזת, O(n)O(n).

תשובה: הפונקציה `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):
(6 נקודות)
ב.

כתבו פונקציה המקבלת רשימה של מספרים שלמים חיוביים. עבור כל איבר ברשימה, הפונקציה תמצא את הספרה הגדולה ביותר ותחזיר את הערך המינימלי (הקטן ביותר) מבין כל הספרות המקסימליות שנמצאו.

לדוגמה:

עבור הרשימה `arr = [1283, 45, 1971, 613]` הפונקציה תחזיר 5.

כותרת הפונקציה:

def min_of_max_digits(arr):

עליכם להשתמש בפונקציה `max_digit` שכתבתם בסעיף א'.

(6 נקודות)
◂ פתרון מלא לשאלה 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

בדיקה על הדוגמה:

איבר1283451971613
`max_digit`8596
`min_val`8555

מוחזר 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
(1)

תנו דוגמה למספר שלם וחיובי `num` שעבורו זימון הפונקציה `what(1234, num)` יחזיר ערך `True`.

(2)

מה מבצעת הפונקציה `what` באופן כללי?

(4 נקודות)
ב.

נתונה הפונקציה `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
(1)

נתונה רשימת מספרים שלמים `a = [46, 127, 415, 104, 491, 371, 49]`

תנו דוגמה לרשימה `b` בעלת מספר האיברים הקטן ביותר שעבורו זימון הפונקציה `secret(a, b)` יחזיר ערך `True`.

(2)

האם לכל זוג רשימות של מספרים שלמים חיוביים `a` ו-`b`, תוצאת זימון הפונקציה `secret(a, b)` תהיה זהה לתוצאת זימון הפונקציה `secret(b, a)`? הסבירו את תשובתכם.

(3)

מה מבצעת הפונקציה `secret` באופן כללי?

(8 נקודות)
◂ פתרון מלא לשאלה 3

סעיף א

(1)
תשובה:

למשל `num = 1000` (כל מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234).

מבוקש: מספר `num` כך ש-`what(1234, num)` יחזיר `True`.

1. אם `num == 1234` מוחזר מיד `False`, ולכן `num` חייב להיות שונה מ-1234.

2. הלולאה מחלקת את שני המספרים ב-10 כל עוד שניהם גדולים מ-9. בסופה מוחזר `num1 == num2`.

3. נבחר `num = 1000` ונעקוב:

סיבוב`num1``num2``num1 > 9 and num2 > 9`
התחלה12341000True
1123100True
21210True
311False

4. הלולאה נעצרת עם `num1 = 1` ו-`num2 = 1`, ולכן מוחזר `1 == 1`, כלומר `True`.

תשובה: `num = 1000` (גם 1999, 1500 וכדומה).

(2)
תשובה:

מחזירה `True` אם המספרים שונים זה מזה, יש להם אותו מספר ספרות ואותה ספרה שמאלית (ראשונה); אחרת `False`.

1. אם המספרים שווים – מוחזר `False`.

2. הלולאה מוחקת בכל סיבוב את ספרת האחדות משני המספרים, ונעצרת ברגע שאחד מהם הפך לחד-ספרתי.

3. אם למספרים אותו מספר ספרות, שניהם הופכים לחד-ספרתיים באותו סיבוב, וכל אחד מהם הוא הספרה השמאלית שלו. אז מוחזר `True` אם ורק אם הספרות השמאליות שוות.

4. אם למספרים מספר ספרות שונה, כשהקצר מביניהם הופך לחד-ספרתי (לכל היותר 9), הארוך עדיין גדול מ-9, ולכן ההשוואה מחזירה `False`.

תשובה: הפונקציה מחזירה `True` אם `num1` ו-`num2` שונים זה מזה, בעלי אותו מספר ספרות ומתחילים באותה ספרה (הספרה השמאלית); אחרת היא מחזירה `False`.

סעיף ב

(1)
תשובה:

`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` לקבוצות לפי (מספר ספרות, ספרה שמאלית):

קבוצהאיברים מ-`a`
דו-ספרתי שמתחיל ב-446, 49
תלת-ספרתי שמתחיל ב-1127, 104
תלת-ספרתי שמתחיל ב-4415, 491
תלת-ספרתי שמתחיל ב-3371

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]` (ארבעה איברים).

(2)
תשובה:

לא. למשל עבור `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`.

(3)
תשובה:

מחזירה `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, ללא מסך מגע, ואינו מוכן לאיסוף.

(3 נקודות)
ב.

כתבו פונקציה חיצונית המקבלת רשימה של מחשבים ניידים (רשימת אובייקטים מטיפוס `Laptop`) ומחזירה את מספר המחשבים שהם בעלי מסך מגע וגם הזיכרון שלהם הוא לפחות 8 GB.

(4 נקודות)
ג.

כתבו פונקציה חיצונית המקבלת רשימה של מחשבים ניידים (רשימת אובייקטים מטיפוס `Laptop`) ומדפיסה את שמות הבעלים של המחשבים עם מסך מגע המוכנים לאיסוף.

אם אין אף מחשב כזה (שמוכן לאיסוף וגם בעל מסך מגע), הפונקציה תדפיס הודעה מתאימה.

(5 נקודות)
◂ פתרון מלא לשאלה 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)
(4 נקודות)
ב.

•"דרגת השיא" של רשימה של מספרים שלמים היא "דרגת האי-זוגיות" הגבוהה ביותר שיש בה.

כתבו פונקציה המקבלת רשימה מספרים שלמים ומחזירה את "דרגת השיא" שלו.

כותרת הפונקציה:

def peek_degree(lst)
(4 נקודות)
ג.

•רשימה של מספרים שלמים נקרא "רשימה מלאה לפי דרגות האי-זוגיות" אם היא כוללת את כל דרגות האי-זוגיות מ-0 ועד "דרגת השיא" וכל דרגה מופיעה בה בדיוק פעם אחת.

כתבו פונקציה המקבלת רשימה של מספרים שלמים. הפונקציה מחזירה `True` אם הרשימה מלאה לפי דרגות האי-זוגיות, אחרת הפונקציה מחזירה `False`.

כותרת הפונקציה:

def is_full_list(lst)
(7 נקודות)
◂ פתרון מלא לשאלה 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` ופעם בספירה) ומעבר על המונים, כלומר O(n⋅d)O(n\cdot d), כאשר dd הוא מספר הספרות של המספר הארוך ביותר.

תשובה: הפונקציה `is_full_list` שלמעלה.

שאלה 6 · מזהי מכשירים בבית חכם: מחרוזות

במערכת "SmartHome" כל מכשיר מקבל מזהה ייחודי מסוג מחרוזת (`str`) המורכב משם החדר, התו נקודתיים (":") ושם מכשיר.

לדוגמה: "KITCHEN:LIGHT", "ROOM_2:TV", "MICROWAVE:KITCHEN".

א.

כתבו פונקציה המקבלת מחרוזת המייצגת מזהה מכשיר. הפונקציה תבדוק אם המזהה תקין. אם כן – הפונקציה תחזיר `True`, ואם לא – הפונקציה תחזיר `False`. מזהה תקין הוא מחרוזת שמתקיימים בה שני תנאים:

•היא מכילה בדיוק פעם אחת את התו נקודתיים (":");

•התו נקודתיים אינו מופיע בתחילת המחרוזת ואינו מופיע בסופה.

כותרת הפונקציה:

def is_valid_device(device_id)
(5 נקודות)
ב.

כדי לייעל את צריכת החשמל, על המערכת לדעת אם שני מכשירים נמצאים באותו החדר.

כתבו פונקציה המקבלת שתי מחרוזות `dev1` ו-`dev2` המייצגות מזהי מכשירים. הפונקציה תבדוק אם שני המכשירים נמצאים באותו החדר. אם כן – הפונקציה תחזיר `True`, ואם לא – הפונקציה תחזיר `False`.

כותרת הפונקציה:

def are_in_same_room(dev1, dev2)

אפשר להניח שהמזהים תקינים.

(5 נקודות)
ג.

כתבו פונקציה המקבלת רשימה של מחרוזות `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.

(5 נקודות)
◂ פתרון מלא לשאלה 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

מעקב על הדוגמה:

מזההשם החדרשווה ל-"KITCHEN"?`result`
"KITCHEN:LIGHT""KITCHEN"כן`["LIGHT"]`
"ROOM_2:TV""ROOM_2"לא`["LIGHT"]`
"KITCHEN:MICROWAVE""KITCHEN"כן`["LIGHT", "MICROWAVE"]`

מוחזרת הרשימה `["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())
(5 נקודות)
ב.

מהו הערך הגדול ביותר ומהו הערך הקטן ביותר שיכולה להחזיר הפונקציה `combine()`?

(2 נקודות)

נתונה הפונקציה `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)
(8 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

תשובה:

הפלט: `1,9` ובשורה הבאה `10`.

עוקבים אחרי הפונקציה הבונה עבור `num = 48291`.

1. `num` חיובי, ולכן אינו משתנה.

2. ספרת האחדות היא 48291 mod 10=148291 \bmod 10 = 1, ולכן `dig1 = 1`, `dig2 = 1`, ואחר כך `num = 4829`.

3. הלולאה עוברת על שאר הספרות מימין לשמאל:

סיבוב`num``dig``dig < dig1`?`dig > dig2`?`dig1``dig2`
148299לאכן19
24822לאלא19
3488לאלא19
444לאלא19

אחרי הסיבוב הרביעי `num = 0` והלולאה נגמרת.

4. `print(info)` מזמן את `__str__`, שמחזירה `"1,9"`.

5. `combine()` מחזירה 1+9=101+9=10.

כלומר `dig1` היא הספרה הקטנה ביותר במספר ו-`dig2` הגדולה ביותר.

תשובה: הפלט הוא

1,9
10

סעיף ב

תשובה:

הגדול ביותר 18 (למשל עבור 9), הקטן ביותר 0 (עבור 0).

1. כפי שראינו בסעיף א, `dig1` היא הספרה הקטנה ביותר ו-`dig2` הספרה הגדולה ביותר במספר, ו-`combine()` מחזירה את סכומן.

2. ערך מקסימלי: כל ספרה היא לכל היותר 9, ולכן הסכום לכל היותר 9+9=189+9=18. הוא מתקבל כשכל הספרות הן 9, למשל עבור `DigitInfo(9)` או `DigitInfo(99)`.

3. ערך מינימלי: כל ספרה היא לפחות 0, ולכן הסכום לפחות 0+0=00+0=0. הוא מתקבל עבור `DigitInfo(0)`: אז `dig1 = dig2 = 0` והלולאה אינה מתבצעת.

תשובה: הערך הגדול ביותר הוא 18 והקטן ביותר הוא 0.

סעיף ג

תשובה:

הפלט: `86 6`.

קודם מחשבים לכל איבר את הספרה הקטנה, הגדולה ואת `combine()`:

אינדקסמספר`dig1``dig2``combine()`
034583811
145459
27341178
366612
4135791910
5866814

בהתחלה `temp1` ו-`temp2` הם שניהם `DigitInfo(3458)` (ערך 11), ו-`ind1 = ind2 = 0`.

מעקב אחרי הלולאה (`t1`, `t2` – ערכי `combine()` של `temp1` ו-`temp2`):

סיבוב `i``cur.combine()`גדול מ-`t1`?גדול מ-`t2`?`t1``t2``ind1``ind2`
19לא (9≤119 \le 11)לא111100
28לאלא111100
312כן (12 > 11)–121130
410לאלא (10≤1110 \le 11)121130
514כן (14 > 12)–141253

בסוף `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)
(5 נקודות)
ב.

כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr`. הפונקציה תחזיר רשימה המכילה את הערכים של כל "הפסגות" הקיימות במטריצה `arr`. אם אין שום "פסגה" במטריצה, הפונקציה תחזיר רשימה ריקה.

כותרת הפונקציה:

def get_peaks_list(arr)
(10 נקודות)
ג.

מהי סיבוכיות זמן הריצה של כל הפונקציות שכתבתם? הסבירו את תשובתכם.

(2 נקודות)
◂ פתרון מלא לשאלה 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`: O(1)O(1) (לכל היותר 9 בדיקות); `get_peaks_list`: O(n⋅m)O(n\cdot m) עבור מטריצה בת nn שורות ו-mm עמודות.

1. `is_peak`: הלולאות המקוננות עוברות על ריבוע של 3×3=93\times3=9 תאים בלבד, בלי קשר לגודל המטריצה. מספר הפעולות קבוע, ולכן הסיבוכיות O(1)O(1).

2. `get_peaks_list`: עבור מטריצה בת nn שורות ו-mm עמודות עוברים על (n−2)(m−2)(n-2)(m-2) תאים פנימיים, ולכל אחד מזמנים את `is_peak` שעולה O(1)O(1). סך הכול O((n−2)(m−2))=O(n⋅m)O((n-2)(m-2))=O(n\cdot m), כלומר סיבוכיות לינארית במספר התאים במטריצה.

תשובה: `is_peak` – O(1)O(1); `get_peaks_list` – O(n⋅m)O(n\cdot m).

שאלה 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.

(4 נקודות)
ב.

המחלקה `BusRoute` מייצגת מסלול של קו אוטובוס. תכונות המחלקה:

•`line_no` – מספר קו (למשל: "61") – מטיפוס מחרוזת, `str`;

•`stops` – רשימת השמות של תחנות העצירה במסלול – מטיפוס רשימת מחרוזות, `list` של `str`;

•`durations` – רשימה מספרים שלמים, `list` של `int`.

הערך `k` ברשימה מציין את מספר הדקות הדרושות לאוטובוס כדי להגיע מתחנה `k` לתחנה `k+1`.

לדוגמה:

אם הרשימה `stops` הוא:

`k` (אינדקס)01234
`stops[k]`עמידרקניון איילוןבורסהמיניסטור לונדוןכרמלית

והרשימה `durations` הוא:

`k`0123
`durations[k]`1215108

האוטובוס נוסע 12 דקות מעמידר לקניון איילון, 15 דקות מקניון איילון לבורסה, 10 דקות מהבורסה למיניסטור לונדון, 8 דקות ממיניסטור לונדון לכרמלית.

כתבו במחלקה `BusRoute` את שתי הפונקציות הבאות:

(1)

פונקציה בוליאנית המקבלת שמות של שתי תחנות `st1` ו-`st2` ובודקת האם ניתן להגיע מ-`st1` ל-`st2` באמצעות קו זה (כלומר, ששתיהן קיימות ברשימת תחנות ו-`st2` מופיעה אחרי `st1`).

כותרת הפונקציה:

def is_route_possible(self, st1, st2)
(2)

פונקציה המקבלת שם של תחנת יעד `stop_name` וזמן יציאה למסלול `start_time`. הפונקציה תחזיר את זמן ההגעה לתחנה זו.

אפשר להניח שהתחנה `stop_name` קיימת במסלול.

כותרת הפונקציה:

def get_arrival_time(self, start_time, stop_name)
(8 נקודות)
ג.

המחלקה `CityTransport` מייצגת מערכת הקווים העירונית. למחלקה תכונה אחת:

•`routes` – רשימה קווי אוטובוס (רשימה של אובייקטים מסוג `BusRoute`)

כתבו במחלקה `CityTransport` את הפונקציה המקבלת תחנת מוצא ותחנת יעד. הפונקציה תדפיס מספרי הקווים (`line_no`) המאפשרים נסיעה מתחנת מוצא לתחנת יעד.

כותרת הפונקציה:

def print_relevant_lines(self, origin, destination)
(5 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

`total = self.min_from_midnight() + min_to_add` (מודולו 24⋅6024\cdot60), ומחזירים `Time(total // 60, total % 60)`.

מבוקש: אובייקט `Time` חדש שמייצג את הזמן הנוכחי ועוד `min_to_add` דקות.

רעיון הפתרון:

1. הדרך הנוחה היא לעבור לדקות: `self.min_from_midnight()` נותנת את הזמן הנוכחי בדקות מחצות. מוסיפים לו את `min_to_add` ומקבלים את הזמן החדש בדקות.

2. אם הסכום עובר את חצות (1440 דקות ביממה, 24⋅60=144024\cdot60=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 הוא 8⋅60+30=5108\cdot60+30=510 דקות מחצות. 510+45=555510+45=555, ו-555//60=9555 // 60 = 9, 555 mod 60=15555 \bmod 60 = 15, כלומר 9:15.

דוגמה למעבר חצות: 23:50 ועוד 20 דקות נותנים 1430+20=14501430+20=1450, ו-1450 mod 1440=101450 \bmod 1440 = 10, כלומר 0:10.

תשובה: הפונקציה `add` שלמעלה.

סעיף ב

(1)
תשובה:

מחזירה `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.

(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). זמן הנסיעה 12+15+10=3712+15+10=37 דקות, ולכן מוחזר 8:37. ליעד "כרמלית" – 37+8=4537+8=45 דקות, כלומר 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)
א.
(1)

מה תהיה תוצאת זימון הפונקציה `what(8652)`? יש להראות מעקב.

(2)

תנו דוגמה למספר תלת-ספרתי `n` שעבורו תוצאת זימון הפונקציה `what(n)` תהיה `True`.

(3)

מה מבצעת הפונקציה `what(n)` באופן כללי עבור מספר שלם חיובי `n`?

(6 נקודות)

נתונה הפונקציה `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)
ב.
(1)

עקבו אחרי זימון הפונקציה `secret(a)` עבור הרשימה הבאה:

a = [17, 863, 19, 542, 123,542]

רשמו מה תהיה התוצאה של הזימון. יש להראות מעקב.

(2)

תנו דוגמה של רשימה `b` הכוללת חמישה מספרים תלת-ספרתיים, כך שזימון הפונקציה `secret(b)` לא יגרום לשינוי ברשימה.

(3)

תנו דוגמה של רשימה `c` הכוללת חמישה מספרים תלת-ספרתיים, כך שזימון הפונקציה `secret(c)` יגרום להפיכת סדר איברים ברשימה.

(4)

מה מבצעת הפונקציה `secret` באופן כללי עבור רשימה של מספרים שלמים חיוביים?

(11 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

(1)
תשובה:

`True`.

1. `what(8652)`: המספר אינו קטן מ-10, ולכן מזמנים `what_helper(865, 2)` (`8652 // 10 = 865`, `8652 % 10 = 2`).

2. מעקב אחרי הזימונים הרקורסיביים:

זימון`n == 0`?`n % 10``n % 10 <= k`?הזימון הבא
`what_helper(865, 2)`לא5לא (5 > 2)`what_helper(86, 5)`
`what_helper(86, 5)`לא6לא (6 > 5)`what_helper(8, 6)`
`what_helper(8, 6)`לא8לא (8 > 6)`what_helper(0, 8)`
`what_helper(0, 8)`כן––מחזיר `True`

3. הערך `True` מוחזר לאורך כל שרשרת הזימונים אל `what(8652)`.

תשובה: `what(8652)` מחזירה `True`.

(2)
תשובה:

למשל `n = 321`.

1. לפי המעקב בסעיף 1, הפונקציה משווה כל ספרה לספרה שמימינה, ומחזירה `True` רק אם כל ספרה גדולה ממש מהספרה שמימינה.

2. נבחר `n = 321`: `what(321)` מזמנת `what_helper(32, 1)`; 2>12 > 1, ולכן `what_helper(3, 2)`; 3>23 > 2, ולכן `what_helper(0, 3)`, שמחזירה `True`.

תשובה: `n = 321` (גם 987, 520 וכדומה).

(3)
תשובה:

מחזירה `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`.

סעיף ב

(1)
תשובה:

הרשימה הופכת ל-`[542, 863, 542, 19, 123, 17]`.

1. קודם נחשב את `what` לכל ערך ברשימה (לפי סעיף א3 – האם הספרות יורדות ממש):

מספר1786319542123542
`what`FalseTrueFalseTrueFalseTrue

2. `secret(a)` מזמנת `secret_helper(a, 0, 5)`. מעקב:

זימון`a[low]``what(a[low])``a[high]``what(a[high])`פעולההרשימה אחרי הפעולה
`(0, 5)`17False542Trueהחלפה, זימון `(1, 4)``[542, 863, 19, 542, 123, 17]`
`(1, 4)`863True––זימון `(2, 4)`ללא שינוי
`(2, 4)`19False123Falseזימון `(2, 3)`ללא שינוי
`(2, 3)`19False542Trueהחלפה, זימון `(3, 2)``[542, 863, 542, 19, 123, 17]`
`(3, 2)`––––`low < high` לא מתקיים, עצירה–

3. הפונקציה אינה מחזירה ערך, אלא משנה את הרשימה עצמה.

תשובה: אחרי הזימון `a = [542, 863, 542, 19, 123, 17]`.

(2)
תשובה:

למשל `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]`.

(3)
תשובה:

למשל `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]`:

זימון`c[low]``what``c[high]``what`פעולההרשימה
`(0, 4)`123False321Trueהחלפה`[321, 456, 789, 654, 123]`
`(1, 3)`456False654Trueהחלפה`[321, 654, 789, 456, 123]`
`(2, 2)`––––עצירה–

4. התקבלה `[321, 654, 789, 456, 123]` – בדיוק הרשימה המקורית בסדר הפוך.

תשובה: `c = [123, 456, 789, 654, 321]`.

(4)
תשובה:

מסדרת מחדש את הרשימה כך שכל המספרים שספרותיהם יורדות ממש (`what` מחזירה `True`) נמצאים בתחילתה, ואחריהם כל שאר המספרים.

1. `low` מתקדם מההתחלה ו-`high` מהסוף. איבר בהתחלה שמקיים `what` כבר נמצא במקום הנכון, ו-`low` מדלג עליו; איבר בסוף שאינו מקיים `what` כבר במקום הנכון, ו-`high` מדלג עליו.

2. כאשר בצד שמאל יש איבר שאינו מקיים `what` ובצד ימין איבר שמקיים אותו – מחליפים ביניהם, ושני המצביעים מתקדמים.

3. כשהמצביעים נפגשים, כל האיברים שמשמאל מקיימים `what` וכל האיברים שמימין אינם מקיימים אותו.

4. זו חלוקה של הרשימה לשתי קבוצות (כמו בשלב החלוקה של מיון מהיר). הסדר הפנימי בכל קבוצה אינו נשמר בהכרח, כפי שראינו בסעיף 1.

תשובה: הפונקציה מסדרת את הרשימה כך שבתחילתה כל המספרים שספרותיהם יורדות ממש משמאל לימין, ובסופה כל שאר המספרים.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.