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

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

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

עוברים על התווים: אות גדולה ('A'–'Z') מגדילה מונה אחד, אות קטנה ('a'–'z') מונה שני, וכל תו אחר מחזיר מיד `False`; בסוף מחזירים `upper > lower`.

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

1. מחרוזת תקינה צריכה לקיים שני תנאים: כל התווים הם אותיות, ויש יותר אותיות גדולות מקטנות.

2. עוברים על המחרוזת תו אחרי תו. תו בין 'A' ל-'Z' הוא אות גדולה – מגדילים את `upper`. תו בין 'a' ל-'z' הוא אות קטנה – מגדילים את `lower`.

3. תו שאינו אות (ספרה, רווח, סימן) פוסל את המחרוזת מיד, ולכן מחזירים `False` בלי להמשיך לסרוק.

4. אחרי הלולאה כל התווים הם אותיות, ונשאר להשוות: מחזירים `True` רק אם `upper > lower`.

5. מחרוזת ריקה: אין בה אותיות גדולות, ו-0>00>0 אינו מתקיים, ולכן היא לא תקינה (הבדיקה בתחילת הפונקציה רק מבהירה זאת).

לדוגמה: "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

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

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

•המספר −1234-1234 אינו מספר מתחלף.

א.

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

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

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

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

1. לפי ההגדרה, מספר מתחלף חייב להיות שלם חיובי. לכן מספר שלילי (כמו −1234-1234) או אפס מחזיר מיד `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. −1234-1234: המספר שלילי, ולכן `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

סיבוכיות: O(d)O(d), כאשר dd הוא מספר הספרות.

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

סעיף ב

תשובה:

עוברים על הרשימה ומוסיפים לסכום כל מספר ש-`is_alternating` מחזירה עבורו `True`; מחזירים את הסכום.

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

1. משתמשים בפונקציה `is_alternating` מסעיף א, כך שאין צורך לכתוב שוב את בדיקת הספרות.

2. סוכם `total` מתחיל ב-0 (האיבר הניטרלי בחיבור). עוברים על כל מספר ברשימה, ואם הוא מתחלף – מוסיפים אותו לסכום.

3. אם אין ברשימה אף מספר מתחלף (או שהרשימה ריקה) מוחזר 0.

לדוגמה, עבור הרשימה `[18345, 2347, 4, 23441, -1234]` המספרים המתחלפים הם 18345, 2347 ו-4, והסכום הוא 18345+2347+4=2069618345+2347+4=20696.

הקוד:

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]`

(1)

עקבו בעזרת טבלת מעקב אחר הזימון `secret(arr, 12)`, ורשמו מה תחזיר הפונקציה.

(2)

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

שימו לב: אין לשנות את הרשימה `arr`!

(5 נקודות)
ב.

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

(2 נקודות)
ג.

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

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

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

סעיף א

(1)
תשובה:

הפונקציה מחזירה `False`.

מה עוקבים: בכל סיבוב מחשבים את סכום שני האיברים שבמקומות `i` (מתחילת הרשימה) ו-`j` (מסופה), משווים אותו ל-`num = 12`, ומזיזים את אחד המצביעים.

טבלת מעקב:

סיבובijarr[i]arr[j]sהשוואה ל-12פעולה
1042022222>1222>12`i += 1`
2141621818>1218>12`i += 1`
324921111<1211<12`j -= 1`
423941313>1213>12`i += 1`
סוף33התנאי `i < j` שקרי

הלולאה מסתיימת כש-`i` ו-`j` נפגשים (שניהם 3) בלי שנמצא סכום השווה ל-12, ולכן מוחזר `False`.

(ואכן, אין ברשימה שני איברים שסכומם 12: הסכומים האפשריים הם 6, 11, 13, 18, 20, 22, 24, 25, 29, 36.)

תשובה: `secret(arr, 12)` מחזירה `False`.

(2)
תשובה:

למשל `num = 13` (כי 9+4=139+4=13); הפונקציה מחזירה `True`.

מה צריך: בסעיף א.1 התקבל `False`, ולכן צריך `num` שעבורו יוחזר `True`, כלומר `num` ששווה לסכום של שני איברים של `arr` (במקומות שונים).

נבחר `num = 13`, כי 9+4=139+4=13. מעקב:

סיבובijarr[i]arr[j]sהשוואה ל-13פעולה
1042022222>1322>13`i += 1`
2141621818>1318>13`i += 1`
324921111<1311<13`j -= 1`
423941313=1313=13`return True`

כל אחד מהסכומים 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`.

בכל סיבוב אחד המצביעים זז, ולכן יש לכל היותר n−1n-1 סיבובים – סיבוכיות O(n)O(n).

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

סעיף ג

תשובה:

כן, ההנחה הכרחית (למשל `secret([2, 4, 9], 13)` מחזירה `False` אף ש-4+9=134+9=13). הפונקציה החדשה ממיינת עותק של הרשימה בסדר יורד ומריצה עליו את אותו אלגוריתם.

ההנחה הכרחית. כל ההיגיון של הזזת המצביעים (סעיף ב) מבוסס על כך ש-`arr[i]` הוא הגדול ו-`arr[j]` הוא הקטן מבין האיברים שנשארו. ברשימה לא ממוינת, הזזת מצביע עלולה לפסול איבר שדווקא שייך לזוג המתאים.

דוגמה נגדית: `arr = [2, 4, 9]`, `num = 13` (יש זוג: 4+9=134+9=13).

סיבובijarr[i]arr[j]sפעולה
102291111<1311<13, `j -= 1` – האיבר 9 נפסל
2012466<136<13, `j -= 1`
סוף00מוחזר `False`

הפונקציה מחזירה `False`, למרות שיש זוג שסכומו 13.

הפונקציה החדשה – רעיון:

1. יוצרים עותק ממוין של הרשימה בסדר יורד בעזרת `sorted(arr, reverse=True)`. `sorted` מחזירה רשימה חדשה, ולכן הרשימה המקורית לא משתנה.

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

סיבוכיות: המיון O(nlog⁡n)O(n\log n) והסריקה O(n)O(n), ובסך הכול O(nlog⁡n)O(n\log n). (אפשר גם לבדוק את כל הזוגות בשתי לולאות מקוננות, ב-O(n2)O(n^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]`; 9+2=11<139+2=11<13 ולכן `j` זז, ואז 9+4=139+4=13 – מוחזר `True`, כנדרש.

תשובה: כן, ההנחה הכרחית; הפונקציה `secret_any` ממיינת עותק של הרשימה בסדר יורד ומריצה עליו את אותו אלגוריתם, ולכן פועלת נכון לכל רשימה.

שאלה 4 · מחלקת משאית: בנאי ופונקציות על רשימת עצמים

חברת משאיות המתמחה בהובלת מזון החליטה למחשב את ניהול המשאיות שלה. לשם כך הוגדרה המחלקה `Truck`. למחלקה התכונות הבאות:

•מספר הרישוי – `truck_id` - מחרוזת (`str`)

•שם הנהג `driver_name` – מחרוזת (`str`)

•המשקל המרבי (מקסימלי) לאחסון – `max_weight` - מספר שלם (`int`)

•האם המשאית מיועדת לקירור? `is_refrigeration` – בוליאני (`bool`)

•האם המשאית פנויה להובלה? – `is_free` – בוליאני (`bool`)

א.

כתבו במחלקה `Truck` את הפונקציה הבונה (`__init__`) המקבלת את מספר הרישוי ואת שם הנהג. הפונקציה מאתחלת את המשאית הפנויה להובלה, עם משקל מרבי של 4,000 קילוגרם ושאינה מיועדת לקירור.

(3 נקודות)
ב.

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

(4 נקודות)
ג.

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

אם אין אף משאית פנויה שמיועדת לקירור, הפונקציה תחזיר מחרוזת "NONAME".

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

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

תשובה: הפונקציה `best_refrigerated_driver` מחזירה את שם הנהג של המשאית הפנויה לקירור עם `max_weight` הגדול ביותר, או "NONAME" אם אין כזו.

שאלה 5 · סכום מחלקים: מספר משוכלל, חסר ועתיר

א.

כתבו פונקציה המקבלת מספר שלם וחיובי `num` ומחזירה את סכום כל מחלקיו החיוביים פרט לו עצמו.

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

def sum_of_proper_divisors(num)

לדוגמה:

•עבור המספר 10 הפונקציה תחזיר 8=1+2+58 = 1+2+5

•עבור המספר 6 הפונקציה תחזיר 6=1+2+36 = 1+2+3

•עבור המספר 12 הפונקציה תחזיר 16=1+2+3+4+616 = 1+2+3+4+6

(6 נקודות)
ב.

כתבו פונקציה המקבלת מספר שלם חיובי `num`, ומחזירה את אחד מהערכים הבאים המציינים "סוג המספר":

•`'P'` – אם `num` שווה לסכום מחלקיו (מספר משוכלל – Perfect).

•`'D'` – אם `num` גדול מסכום מחלקיו (מספר חסר – Deficient).

•`'A'` – אם `num` קטן מסכום מחלקיו (מספר עתיר – Abundant).

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

def check_number_type(num)

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

(3 נקודות)
ג.

כתבו פונקציה המקבלת מספר שלם חיובי `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)
(6 נקודות)
◂ פתרון מלא לשאלה 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 – הסכום 1+2+5=81+2+5=8.

2. עבור 12: נבדקים 1 עד 6, והמחלקים הם 1, 2, 3, 4, 6 – הסכום 1+2+3+4+6=161+2+3+4+6=16.

הקוד:

def sum_of_proper_divisors(num):
    total = 0
    for d in range(1, num // 2 + 1):
        if num % d == 0:
            total += d
    return total

סיבוכיות: O(num)O(num).

תשובה: הפונקציה סוכמת את כל המחלקים של `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 עתיר כי 1+2+3+4+6=16>121+2+3+4+6=16>12, ו-18 עתיר כי 1+2+3+6+9=21>181+2+3+6+9=21>18; לעומת זאת 14 חסר כי 1+2+7=10<141+2+7=10<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` המספרים מחשבים סכום מחלקים ב-O(num)O(num), ובסך הכול O(limit2)O(limit^2).

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

כתבו פונקציה המקבלת שתי מחרוזות `s1` ו-`s2`. הפונקציה תחזיר מספר שלם `k` שעבורו מחרוזת `s2` היא "גלגול K" של מחרוזת `s1`. אם אין שום מספר `k`, הפונקציה תחזיר `-1`.

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

def find_rolling_k(s1, s2)
(5 נקודות)
ג.

כתבו פונקציה המקבלת רשימת מחרוזות `arr` ומחרוזת נוספת `s`. על הפונקציה לבדוק אם כל המחרוזות שנמצאות ב-`arr` הן "גלגול K" כלשהו של המחרוזת `s`. אם כן – הפונקציה תחזיר `True`, ולא – הפונקציה תחזיר `False`.

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

def are_all_rotations(arr, s)
(5 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

אם האורכים שונים – `False`; אחרת `k = k % len(s1)` ומחזירים `s1[k:] + s1[:k] == s2`.

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

1. סיבוב שמאלה לא משנה את אורך המחרוזת, ולכן אם `len(s1) != len(s2)` – בוודאי `s2` אינה גלגול של `s1`.

2. אחרי kk סיבובים שמאלה, kk התווים הראשונים עוברים (באותו סדר) לסוף המחרוזת. כלומר התוצאה היא `s1[k:] + s1[:k]`. לדוגמה, ל-"ABCDE" ו-k=2k=2: `"CDE" + "AB" = "CDEAB"`.

3. אחרי nn סיבובים (nn – אורך המחרוזת) מקבלים שוב את המחרוזת המקורית, ולכן kk סיבובים שקולים ל-k mod nk \bmod n סיבובים. כך הפונקציה נכונה גם עבור k≥nk \ge n (למשל k=7k=7 ל-"ABCDE" שקול ל-k=2k=2).

4. מחרוזת ריקה (שתיהן ריקות): סיבוב לא משנה אותה, ומחזירים `True` לפני החלוקה ב-nn (כדי לא לחלק באפס).

הקוד:

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. לפי סעיף א, גלגול kk וגלגול k+nk+n זהים (nn – אורך המחרוזת). לכן מספיק לנסות את הערכים k=1,2,…,nk=1, 2, \dots, n: אם אף אחד מהם לא מתאים, אין שום kk מתאים.

2. לכל kk קוראים ל-`is_k_rolling(s1, s2, k)`. ה-kk הראשון שעבורו מוחזר `True` הוא התשובה (הקטן ביותר).

3. אם הלולאה הסתיימה בלי התאמה – מחזירים `-1`. בפרט, אם האורכים שונים, `is_k_rolling` מחזירה תמיד `False`, ומוחזר `-1`.

4. אם `s1` ו-`s2` זהות, יוחזר המספר החיובי הקטן ביותר שמחזיר את המחרוזת לעצמה (למשל 3 עבור "ABC", ו-1 עבור "AAA"). (מניחים שהמחרוזות אינן ריקות.)

לדוגמה, עבור "ABCDE" ו-"CDEAB": k=1k=1 נותן "BCDEA" – לא; k=2k=2 נותן "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

סיבוכיות: nn ניסיונות, ובכל אחד בניית מחרוזת והשוואה ב-O(n)O(n) – בסך הכול O(n2)O(n^2).

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

יש להראות את תוכן הרשימה `count` אחרי סיום של כל אחד מהשלבים 1–3.

(6 נקודות)
ב.

נתונה הרשימה `arr = [23, 15, 9, 71, 25]`

עקבו אחרי זימון הפונקציה `out2 = what(arr, 10)` ורשמו מה יהיה תוכן הרשימה `out2` אחרי זימון הפונקציה.

(6 נקודות)
ג.

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

(3 נקודות)
◂ פתרון מלא לשאלה 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` – ספרת האחדות. n=5n=5.

מבוקש: תוכן `count` אחרי כל שלב, ותוכן `out1`.

שלב 1 – ספירת ספרות האחדות:

ספרות האחדות הן: 23 → 3, 15 → 5, 9 → 9, 71 → 1, 25 → 5. כל ספרה מגדילה את התא המתאים ב-`count`:

אינדקס0123456789
count אחרי שלב 10101020001

שלב 2 – סכומים מצטברים: כל תא מקבל את סכום התאים עד אליו כולל. עכשיו `count[d]` הוא מספר האיברים שספרתם קטנה מ-dd או שווה לו, כלומר המקום (בספירה מ-1) שבו יוצב האיבר האחרון עם הספרה dd:

אינדקס0123456789
count אחרי שלב 20112244445

שלב 3 – הצבה ב-`output` מהסוף להתחלה: לכל איבר מציבים אותו במקום `count[digit] - 1` ומקטינים את `count[digit]` ב-1:

iarr[i]digitcount[digit] לפנימקום ב-outputoutput אחרי ההצבהcount[digit] אחרי
425543[0, 0, 0, 25, 0]3
371110[71, 0, 0, 25, 0]0
29954[71, 0, 0, 25, 9]4
115532[71, 0, 15, 25, 9]2
023321[71, 23, 15, 25, 9]1
אינדקס0123456789
count אחרי שלב 30011224444

שימו לב ש-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 (כי 9//10=09 // 10 = 0), 71 → 7, 25 → 2.

אינדקס0123456789
count אחרי שלב 11120000100
count אחרי שלב 21244444555

שלב 3:

iarr[i]digitcount[digit] לפנימקום ב-outputoutput אחרי ההצבהcount[digit] אחרי
425243[0, 0, 0, 25, 0]3
371754[0, 0, 0, 25, 71]4
29010[9, 0, 0, 25, 71]0
115121[9, 15, 0, 25, 71]1
023232[9, 15, 23, 25, 71]2
אינדקס0123456789
count אחרי שלב 30124444455

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` שבו יוצבו האיברים עם הספרה dd.

3. שלב 3 מציב כל איבר באזור שלו. המעבר הוא מסוף `arr` להתחלה, ולכן איברים עם אותה ספרה שומרים על הסדר היחסי שהיה להם ב-`arr` – המיון יציב.

4. הרשימה `arr` לא משתנה; מוחזרת רשימה חדשה.

זהו מיון מנייה (Counting Sort) לפי ספרה אחת – השלב הבסיסי של מיון בסיס (Radix Sort). הפעלה של `what` עם `exp = 1, 10, 100, ...` ברצף (כל פעם על התוצאה הקודמת) ממיינת את הרשימה כולה. סיבוכיות כל זימון: O(n+10)=O(n)O(n+10)=O(n).

תשובה: הפונקציה מחזירה רשימה חדשה שבה איברי `arr` ממוינים בסדר עולה לפי הספרה במקום `exp`, במיון יציב (מיון מנייה, שלב של מיון בסיס).

שאלה 8 · פרחים במטריצה: לב הפרח ועלי כותרת

נגדיר "פרח" בתוך מטריצה (רשימה של רשימות) כך:

•ה"פרח" מורכב מחמישה איברים בתת-מטריצה בגודל 3X3. האיבר המרכזי בתת-המטריצה הוא "לב הפרח". ארבעת האיברים הצמודים לו בפינותיו (אלכסוניים) הם "עלי הכותרת" של ה"פרח".

•הערך של "לב הפרח" שווה לסכום "עלי הכותרת" של הפרח.

•בכל פרח צריכים להיות בדיוק ארבעה "עלי כותרת".

לדוגמה: במערך הזה יש שני פרחים: אחד עם לב הפרח 6, ושני עם לב הפרח 15.

א.

כתבו פונקציה המקבלת מטריצה של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום איבר במטריצה: `row` (שורה) ו-`col` (עמודה). הפונקציה תבדוק אם איבר זה הוא "לב הפרח".

אם כן – הפונקציה תחזיר `True`, ולא – הפונקציה תחזיר `False`.

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

def is_flower(arr, row, col)
(4 נקודות)
ב.

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

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

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

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

(3 נקודות)
◂ פתרון מלא לשאלה 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, ועלי הכותרת שלו הם 3+1+0+2=63+1+0+2=6. לב הפרח 15 נמצא בשורה 3 ועמודה 3, ועלי הכותרת שלו הם 2+8+7+(−2)=152+8+7+(-2)=15.

הקוד:

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`: O(1)O(1); `flower_hearts`: O(n⋅m)O(n\cdot m) עבור מטריצה בת nn שורות ו-mm עמודות.

נסמן ב-nn את מספר השורות וב-mm את מספר העמודות של המטריצה.

1. `is_flower`: הפונקציה מבצעת מספר קבוע של פעולות – שתי בדיקות גבולות, חיבור של ארבעה איברים והשוואה אחת – בלי לולאות. מספר הפעולות לא תלוי בגודל המטריצה, ולכן הסיבוכיות היא O(1)O(1).

2. `flower_hearts`: שתי לולאות מקוננות עוברות על (n−2)⋅(m−2)(n-2)\cdot(m-2) מיקומים פנימיים, ובכל מיקום יש קריאה אחת ל-`is_flower` (O(1)O(1)) ולכל היותר הוספה אחת לרשימה (O(1)O(1)). לכן הסיבוכיות היא O((n−2)(m−2))=O(n⋅m)O((n-2)(m-2))=O(n\cdot m), כלומר לינארית במספר האיברים של המטריצה.

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

שאלה 9 · חניון חברות: מחלקות, מכסות ומקומות חניה

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

המחלקה "רכב חברה" (`CompanyCar`) ולה התכונות:

•מספר הרישוי (`license_plate`) – מחרוזת, `str`

•היצרן (`manufacturer`) – מחרוזת, `str`

•שם החברה שהרכב משויך אליה (`company`) – מחרוזת, `str`

המחלקה "מגבלת חברה" (`CompanyLimit`) ולה התכונות:

•שם החברה (`company_name`) – מחרוזת, `str`

•המגבלה המקסימלית (`company_limit`) – מספר שלם, `int`

בכל מחלקה הוגדרה פונקציה בונה (`__init__`) המקבלת ערכים לכל התכונות.

א.
(1)

הגדירו מחלקה בשם "חניון חברות" (`Parking`) הכוללת את התכונות הבאות:

•רשימה של רכבים (`cars`) – רשימה של עצמים מסוג "רכב חברה". הרשימה תכיל את הרכבים הנמצאים כרגע בחניון.

•רשימה של מקומות חניה (`parking_spots`) – רשימה של מחרוזות באותו הגודל, המציין את מקום החניה של הרכב המתאים (לדוגמה: "Q21", "A4", "P10").

•מגבלות חניה (`limits`) – רשימה של עצמים מסוג `CompanyLimit`, המכילה את המכסות לכל חברה.

(2)

כתבו במחלקה `Parking` פונקציה בונה (`__init__`), המקבלת רשימת `limits` מוכנה (עם החברות והמגבלות שלהן), ומייצרת חניון ללא רכבים: רשימות ה-`cars` וה-`parking_spot` יהיו ריקות בתחילה. קיבולת החניון הכוללת היא 150 מקומות.

(4 נקודות)
ב.

כתבו במחלקה "חניון חברות" פונקציה המקבלת מקום בחניה (`spot`). הפונקציה תבדוק אם מקום זה פנוי. אם כן – הפונקציה תחזיר ערך `True`, ואם לא – הפונקציה תחזיר ערך `False`. כותרת הפונקציה:

def check_spot(self, spot)
(5 נקודות)
ג.

כתבו במחלקה "חניון חברות" פונקציה המקבלת את פרטי הרכב ואת מקום החניה (`spot`) ומנסה לחנות אותו:

•אם החניה `spot` תפוסה על ידי רכב אחר, הפונקציה תדפיס הודעה מתאימה ותחזיר `False`.

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

•אם המכסה לא נוצלה במלואה, הפונקציה תייצר רכב חדש (עצם מסוג `CompanyCar`) עם הפרטים שקיבלה, תוסיף את הרכב ותחזיר `True`. כותרת הפונקציה:

def park_car(self, license, manufacturer, company, spot)

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

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

סעיף א

(1)
תשובה:

מחלקה `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`.

(2)
תשובה:

`__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`.

הקוד (בתוך המחלקה `Parking`):

    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`.)

סיבוכיות: O(k)O(k), כאשר kk הוא מספר הרכבים בחניון.

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

הקוד (בתוך המחלקה `Parking`):

    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)
(1)

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

(2)

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

(3)

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

(6 נקודות)
ב.

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

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

(2)

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

(3)

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

(6 נקודות)
ג.

נתונה הפונקציה `display` המקבלת מספר שלם:

def display(n):
    if n > 0:
        display(n // 10)
        print(n % 10, end="")
        display(n // 10)
(1)

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

(2)

מה יהיה פלט עבור זימון הפונקציה `display(123)`?

(3)

מה יהיה פלט עבור זימון הפונקציה `display (1234)`?

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

סעיף א

(1)
תשובה:

`False`.

מה עוקבים: בכל קריאה `n` מוכפל ב-`a = 2`, עד ש-`n` שווה ל-`b = 15` (מוחזר `True`) או עובר אותו (מוחזר `False`).

קריאהabn`a == 1`?`n == b`?`n > b`?מה קורה
12151לאלאלא`what(2, 15, 2)`
22152לאלאלא`what(2, 15, 4)`
32154לאלאלא`what(2, 15, 8)`
42158לאלאלא`what(2, 15, 16)`
521516לאלאכן`return False`

הערך `False` חוזר דרך כל הקריאות עד הקריאה המקורית. (15 אינו חזקה של 2: הוא בין 23=82^3=8 ל-24=162^4=16.)

תשובה: `what(2, 15)` מחזירה `False`.

(2)
תשובה:

`b = 27` (או `b = 81`).

מה צריך: עם `a = 3` הערכים של `n` הם 1,3,9,27,81,243,…1, 3, 9, 27, 81, 243, \dots (חזקות של 3). מוחזר `True` אם `b` שווה לאחד מהם. החזקות הדו-ספרתיות של 3 הן 33=273^3=27 ו-34=813^4=81.

מעקב עבור `b = 27`:

קריאהn`n == 27`?`n > 27`?מה קורה
11לאלא`what(3, 27, 3)`
23לאלא`what(3, 27, 9)`
39לאלא`what(3, 27, 27)`
427כן`return True`

תשובה: `b = 27` (גם `b = 81` מתאים).

(3)
תשובה:

מחזירה `True` אם `b` הוא חזקה שלמה אי-שלילית של `a` (b=akb=a^k, k≥0k\ge0), ואחרת `False`.

ההסבר:

1. `n` מתחיל ב-1 ובכל קריאה מוכפל ב-`a`, ולכן הוא עובר על הערכים a0=1,a1,a2,…a^0=1, a^1, a^2, \dots.

2. אם `n` הגיע בדיוק ל-`b` – מוחזר `True`, כלומר b=akb=a^k עבור kk כלשהו. אם `n` עבר את `b` – אף חזקה של `a` לא שווה ל-`b` (החזקות רק גדלות), ומוחזר `False`.

3. המקרה `a == 1` מטופל בנפרד, כי שם `n` היה נשאר 1 לנצח (רקורסיה אינסופית): החזקה היחידה של 1 היא 1, ולכן מוחזר `True` רק אם `b == 1`.

4. כיוון ש-a0=1a^0=1, עבור `b = 1` מוחזר `True` לכל `a`.

תשובה: `what(a, b)` בודקת אם `b` הוא חזקה של `a`, כלומר אם קיים k≥0k\ge0 שלם כך ש-b=akb=a^k (מחזירה `True` אם כן, `False` אם לא).

סעיף ב

(1)
תשובה:

`False`.

מה עוקבים: בקריאה הראשונה `x` מקבל את הערך `n = 10`. בכל קריאה משווים את `n` ל-x2x^2: אם n<x2n<x^2 מקטינים את `x` ב-1, אם n>x2n>x^2 מחזירים `False`, ואם הם שווים – `True`.

קריאהnxx⋅xx\cdot xהשוואהמה קורה
1101010010<10010<100`why(10, 9)`
21098110<8110<81`why(10, 8)`
31086410<6410<64`why(10, 7)`
41074910<4910<49`why(10, 6)`
51063610<3610<36`why(10, 5)`
61052510<2510<25`why(10, 4)`
71041610<1610<16`why(10, 3)`
8103910>910>9`return False`

`x` "דילג" מ-4 (16>1016>10) ל-3 (9<109<10) בלי לפגוש x2=10x^2=10, ולכן מוחזר `False`.

תשובה: `why(10)` מחזירה `False`.

(2)
תשובה:

`n = 16` (או כל ריבוע דו-ספרתי: 25, 36, 49, 64, 81).

מה צריך: מוחזר `True` רק כשמגיעים ל-`x` שעבורו x⋅x=nx\cdot x=n, כלומר כש-`n` הוא ריבוע של מספר שלם. הריבועים הדו-ספרתיים הם 16, 25, 36, 49, 64, 81.

מעקב קצר עבור `n = 16`: x=16x=16: 16<25616<256; x=15x=15: 16<22516<225; ... ; x=5x=5: 16<2516<25; x=4x=4: 16=1616=16 – מוחזר `True`.

תשובה: `n = 16` (וגם 25, 36, 49, 64 או 81).

(3)
תשובה:

עבור n≥0n\ge0 מחזירה `True` אם `n` ריבוע שלם (0, 1, 4, 9, ...) ו-`False` אחרת; עבור n<0n<0 הרקורסיה אינה נעצרת (`RecursionError`).

ההסבר: הפונקציה מתחילה ב-x=nx=n ומקטינה את `x` כל עוד x2>nx^2>n. היא נעצרת ב-`x` הגדול ביותר שעבורו x2≤nx^2\le n, ושם מחזירה `True` אם x2=nx^2=n ו-`False` אם x2<nx^2<n.

המקרים השונים של n:

1. n>0n>0: x=nx=n מקיים x2=n2≥nx^2=n^2\ge n, ו-`x` יורד בהדרגה. מכיוון ש-12=1≤n1^2=1\le n, הירידה נעצרת לכל היותר ב-x=1x=1. מוחזר `True` אם ורק אם `n` הוא ריבוע של מספר שלם (1, 4, 9, 16, ...), ואחרת `False`. לדוגמה `why(1)` מחזירה `True` מיד (1=1⋅11=1\cdot1), ו-`why(2)` מחזירה `False` (2<42<4, ואז 2>12>1).

2. n=0n=0: x=0x=0 ו-0⋅0=00\cdot0=0, כלומר אף אחד מהתנאים n>x2n>x^2, n<x2n<x^2 לא מתקיים, ומוחזר `True` (0 הוא ריבוע של 0).

3. n<0n<0: x=nx=n שלילי, ו-x2x^2 חיובי, ולכן תמיד n<x2n<x^2. `x` יורד ל-n−1,n−2,…n-1, n-2, \dots, ו-x2x^2 רק גדל, כך שהתנאי לעולם לא משתנה. הרקורסיה אינה מגיעה לתנאי עצירה – רקורסיה אינסופית, שמסתיימת בשגיאה (`RecursionError`, חריגה מעומק הרקורסיה).

תשובה: עבור n≥0n\ge0 הפונקציה בודקת אם `n` הוא ריבוע של מספר שלם (מחזירה `True` אם כן, `False` אם לא); עבור n<0n<0 היא נכנסת לרקורסיה אינסופית ומסתיימת בשגיאה.

סעיף ג

(1)
תשובה:

`121`

מה עוקבים: כל קריאה עם n>0n>0 מבצעת שלושה דברים לפי הסדר: קריאה ל-`display(n // 10)`, הדפסת ספרת האחדות `n % 10`, ושוב קריאה ל-`display(n // 10)`. קריאה עם n=0n=0 לא עושה דבר.

עץ הקריאות של `display(12)`:

שלבקריאהפעולהפלט מצטבר
1`display(12)`קוראת ל-`display(1)`
2`display(1)`קוראת ל-`display(0)` – לא עושה דבר
3`display(1)`מדפיסה 1%10=11 \% 10 = 11
4`display(1)`קוראת ל-`display(0)` – לא עושה דבר; חוזרת1
5`display(12)`מדפיסה 12%10=212 \% 10 = 212
6`display(12)`קוראת ל-`display(1)` – מדפיסה 1 (כמו בשלבים 2–4)121

תשובה: הפלט הוא `121`.

(2)
תשובה:

`1213121`

רעיון: `display(123)` מדפיסה את הפלט של `display(12)`, אחריו את הספרה 123%10=3123 \% 10 = 3, ושוב את הפלט של `display(12)`.

מסעיף ג.1 הפלט של `display(12)` הוא `121`, ולכן:

`121` + `3` + `121` = `1213121`

תשובה: הפלט הוא `1213121`.

(3)
תשובה:

`121312141213121`

רעיון: באותו אופן, `display(1234)` מדפיסה את הפלט של `display(123)`, אחריו את הספרה 1234%10=41234 \% 10 = 4, ושוב את הפלט של `display(123)`.

מסעיף ג.2 הפלט של `display(123)` הוא `1213121`, ולכן:

`1213121` + `4` + `1213121` = `121312141213121`

(באופן כללי, עבור מספר בן dd ספרות מודפסות 2d−12^d-1 ספרות; כאן 24−1=152^4-1=15.)

תשובה: הפלט הוא `121312141213121`.

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

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

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