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

מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - קיץ 2024 מועד ב'

הנדסת תוכנה · סמל 97103 · 14 שאלות · פתרון מלא לכל סעיף

מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), קיץ 2024 מועד ב', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.

הנחיות הבחינה

משך הבחינה: ארבע שעות וחצי.

מבנה השאלון: בשאלון זה שני מבחנים. עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:

מבחן ב- Python (עמוד 2)

בכל מבחן 14 שאלות.

חלק א' – 48 נקודות

שאלות 1-7: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.

חלק ב' – 30 נקודות

שאלות 8-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.

חלק ג' – 22 נקודות

שאלות 12-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.

בסך הכול: 100 נקודות.

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

2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.

אין לצרף ספרים או חוברות עם פתרונות.

שאלה 1 · קליטה עד 0: מניית שליליים וממוצע חיוביים

כתבו קטע תוכנית שקולט מספרים שלמים. הקלט יסתיים כאשר ייקלט המספר 0.

על התוכנית לחשב ולהדפיס:

•את כמות המספרים השליליים שנקלטו

•את ממוצע מספרים חיוביים שנקלטו.

הערה: אם לא נקלט אף מספר חיובי יש להדפיס הודעה מתאימה.

◂ פתרון מלא לשאלה 1

פתרון

תשובה:

לולאת while עד קליטת 0, עם מונה לשליליים, מונה וצובר לחיוביים; בסוף מדפיסים את מונה השליליים ואת הממוצע sum_poscount_pos\frac{sum\_pos}{count\_pos}, או הודעה אם count_pos=0count\_pos=0.

הרעיון: מספר הנתונים לא ידוע מראש – הקלט נגמר כשנקלט 0 – ולכן משתמשים בלולאת `while` עם "זקיף": קולטים מספר ראשון לפני הלולאה, ובסוף כל סיבוב קולטים את המספר הבא. ה-0 עצמו לא נספר.

1. לשליליים צריך רק כמות – מונה `count_neg`.

2. לממוצע החיוביים צריך שני משתנים: צובר `sum_pos` (סכום החיוביים) ומונה `count_pos` (כמה חיוביים היו). הממוצע הוא sum_poscount_pos\frac{sum\_pos}{count\_pos}.

3. בתוך הלולאה המספר אינו 0, ולכן הוא שלילי או חיובי – מספיק `if`/`else`.

4. אחרי הלולאה: אם `count_pos` הוא 0, חלוקה בו אסורה – לכן מדפיסים הודעה מתאימה במקום הממוצע.

count_neg = 0       # מונה המספרים השליליים
sum_pos = 0         # צובר המספרים החיוביים
count_pos = 0       # מונה המספרים החיוביים
num = int(input())
while num != 0:
    if num < 0:
        count_neg = count_neg + 1
    else:
        sum_pos = sum_pos + num
        count_pos = count_pos + 1
    num = int(input())
print("Negative numbers:", count_neg)
if count_pos > 0:
    print("Average of positive numbers:", sum_pos / count_pos)
else:
    print("No positive numbers were entered")

דוגמה: עבור הקלט 5, 3-, 10, 1-, 0 יודפס: מספר השליליים 2, והממוצע 5+102=7.5\frac{5+10}{2}=7.5. עבור הקלט 5-, 3-, 0 יודפס 2 ואחריו ההודעה שלא נקלטו מספרים חיוביים.

תשובה: קטע התוכנית שלמעלה – מונה לשליליים, מונה וצובר לחיוביים, וטיפול במקרה שאין חיוביים.

שאלה 2 · קליטת 20 מחרוזות: אורך זוגי ואות A

כתבו קטע תוכנית הקולט 20 מחרוזות.

עבור כל מחרוזת באורך זוגי יש להדפיס את התו הראשון ואת התו האחרון שלה.

כמו כן, יש למנות ולהדפיס את כמות המחרוזות אשר מתחילות או מסתיימות באות 'A'.

◂ פתרון מלא לשאלה 2

פתרון

תשובה:

לולאה של 20 סיבובים: אם `len(s) % 2 == 0` מדפיסים `s[0]` ו-`s[-1]`; אם `s[0] == 'A' or s[-1] == 'A'` מגדילים מונה; בסוף מדפיסים את המונה.

הרעיון: מספר המחרוזות ידוע (20), ולכן לולאת `for`. כל מחרוזת עוברת שתי בדיקות בלתי תלויות, ולכן שני `if` נפרדים (מחרוזת יכולה גם להיות באורך זוגי וגם להתחיל ב-'A'):

1. אורך זוגי: `len(s) % 2 == 0` – מדפיסים את התו הראשון `s[0]` ואת התו האחרון `s[-1]`.

2. מתחילה או מסתיימת ב-'A': `s[0] == 'A' or s[-1] == 'A'` – מגדילים את המונה `count_a` ב-1. משתמשים ב-`or`, כי מספיק שאחד מהתנאים יתקיים (מחרוזת כמו "ABBA" נספרת פעם אחת בלבד).

מחרוזת ריקה היא באורך 0 (זוגי) אבל אין בה תווים, ולכן בשתי הבדיקות מוסיפים את התנאי `len(s) > 0`, כדי לא לגשת ל-`s[0]` שאינו קיים.

בסוף הלולאה מדפיסים את המונה.

count_a = 0
for i in range(20):
    s = input()
    if len(s) > 0 and len(s) % 2 == 0:
        print(s[0], s[-1])
    if len(s) > 0 and (s[0] == 'A' or s[-1] == 'A'):
        count_a = count_a + 1
print("Strings that start or end with 'A':", count_a)

דוגמה: עבור "AB" יודפס `A B` והמונה יגדל; עבור "ABC" (אורך אי-זוגי) לא יודפסו תווים, אבל המונה יגדל; עבור "XYZW" יודפס `X W` והמונה לא ישתנה.

תשובה: קטע התוכנית שלמעלה.

שאלה 3 · מספרים אקראיים: מניית מספרי שבע-בול

מספר "שבע-בול" הוא מספר שמתחלק ב- 7 ללא שארית שלפחות אחת מהספרות שלו היא 7.

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

על התוכנית לחשב ולהדפיס כמה מהמספרים שנוצרו הם מספרים "שבע-בול".

◂ פתרון מלא לשאלה 3

פתרון

תשובה:

365 הגרלות של `random.randint(100, 999)`; מונים מספר אם `num % 7 == 0` ואחת משלוש ספרותיו (מאות, עשרות, אחדות) שווה ל-7.

הרעיון:

1. מספר תלת-ספרתי חיובי הוא מספר בין 100 ל-999, ולכן מגרילים `random.randint(100, 999)` (שני הגבולות כלולים).

2. לכל מספר מפרקים את שלוש הספרות:

•ספרת המאות: `num // 100`

•ספרת העשרות: `num // 10 % 10`

•ספרת האחדות: `num % 10`

3. המספר הוא "שבע-בול" אם שני התנאים מתקיימים יחד: הוא מתחלק ב-7 (`num % 7 == 0`) וגם לפחות אחת מהספרות היא 7 (שלוש השוואות מחוברות ב-`or`).

4. מונה `count` גדל בכל פעם שנמצא מספר כזה, ובסוף הלולאה מדפיסים אותו.

import random

count = 0
for i in range(365):
    num = random.randint(100, 999)
    hundreds = num // 100
    tens = num // 10 % 10
    units = num % 10
    if num % 7 == 0 and (hundreds == 7 or tens == 7 or units == 7):
        count = count + 1
print("Number of 'seven-boom' numbers:", count)

דוגמה: 147=7⋅21147=7\cdot 21 ויש בו הספרה 7 – "שבע-בול". 140=7⋅20140=7\cdot 20 מתחלק ב-7 אבל אין בו 7 – לא. 170170 מכיל 7 אבל 170=7⋅24+2170=7\cdot 24+2 – לא.

תשובה: קטע התוכנית שלמעלה.

שאלה 4 · רשימה משולשת: חלוקה לשלישים וסכומים

רשימה של מספרים שלמים נקראת "משולשת" אם היא עונה על שלושה תנאים:

•מספר איברי הרשימה מתחלק בשלוש ללא שארית

•סכום ערכי האיברים הנמצאים בכל שליש מתחלק גם הוא בשלוש ללא שארית

•ברשימה יש בדיוק שלושה איברים בעלי ערך 3.

לדוגמה:

הרשימה הבאה היא "רשימה משולשת":

01234567891011
738-60339-10112

כתבו פעולה המקבלת רשימה של מספרים שלמים `arr`. הפעולה תחזיר ערך `True`, אם הרשימה היא "רשימה משולשת", ולא, הפעולה תחזיר ערך `False`.

כותרת הפעולה:

`is_tripple(arr)`

◂ פתרון מלא לשאלה 4

פתרון

תשובה:

בודקים `len(arr) % 3 == 0`, אחר כך שסכום כל אחד משלושת השלישים (באורך `len(arr)//3`) מתחלק ב-3, ולבסוף שמספר האיברים ששווים 3 הוא בדיוק 3.

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

1. תנאי 1: אם `len(arr) % 3 != 0` – הרשימה לא משולשת. (התנאי הזה חייב להיבדק ראשון, כי רק אחריו אפשר לחלק את הרשימה לשלושה שלישים שווים.)

2. תנאי 2: אורך כל שליש הוא `third = n // 3`. השליש ה-t (עבור t=0,1,2t=0,1,2) הוא התאים מ-`t*third` עד `(t+1)*third - 1`. מחשבים את סכומו, ואם הסכום אינו מתחלק ב-3 – מחזירים `False`. (ב-Python גם סכום שלילי כמו −6-6 נותן `-6 % 3 == 0`, כך שהבדיקה נכונה גם לשליליים.)

3. תנאי 3: סופרים כמה איברים שווים ל-3; הרשימה משולשת רק אם המונה שווה בדיוק ל-3 (לא פחות ולא יותר).

def is_tripple(arr):
    n = len(arr)
    if n % 3 != 0:                      # תנאי 1
        return False
    third = n // 3
    for t in range(3):                  # תנאי 2: שלושת השלישים
        s = 0
        for i in range(t * third, (t + 1) * third):
            s = s + arr[i]
        if s % 3 != 0:
            return False
    count3 = 0                          # תנאי 3: בדיוק שלושה איברים שערכם 3
    for x in arr:
        if x == 3:
            count3 = count3 + 1
    return count3 == 3

בדיקה על הדוגמה: 12 איברים, 12 mod 3=012 \bmod 3 = 0, כל שליש באורך 4:

•שליש ראשון: 7+3+8+(−6)=127+3+8+(-6)=12, מתחלק ב-3.

•שליש שני: 0+3+3+9=150+3+3+9=15, מתחלק ב-3.

•שליש שלישי: (−1)+0+11+2=12(-1)+0+11+2=12, מתחלק ב-3.

•הערך 3 מופיע בתאים 1, 5, 6 – בדיוק שלוש פעמים.

לכן הפעולה מחזירה `True`.

סיבוכיות: מעבר אחד על השלישים ומעבר אחד לספירת ה-3 – O(n)O(n).

תשובה: הפעולה `is_tripple` שלמעלה.

שאלה 5 · איבר נפילה ברשימה ומניית נפילות

איבר ברשימה נקרא "נפילה" אם ערכו קטן מערכים של שני שכניו.

ערך ראשון או ערך אחרון לא יכולים להיות נפילה.

א.

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

כותרת הפעולה:

`is_fall(arr, index)`

(5 נקודות)
ב.

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

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

(5 נקודות)
ג.

מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'. הסבירו את תשובתכם.

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

סעיף א

תשובה:

אם `index` הוא הראשון או האחרון (או מחוץ לרשימה) – `False`; אחרת מחזירים `arr[index] < arr[index-1] and arr[index] < arr[index+1]`.

הרעיון:

1. לאיבר הראשון (`index == 0`) ולאחרון (`index == len(arr)-1`) אין שני שכנים, ולפי ההגדרה הם לא יכולים להיות נפילה – מחזירים `False`. את אותה בדיקה (`index <= 0` או `index >= len(arr)-1`) מנצלים גם כדי לא לחרוג מגבולות הרשימה.

2. אחרת יש לאיבר שני שכנים: `arr[index-1]` משמאל ו-`arr[index+1]` מימין. האיבר הוא נפילה אם הוא קטן ממש משניהם – שני תנאים מחוברים ב-`and`.

def is_fall(arr, index):
    if index <= 0 or index >= len(arr) - 1:
        return False                    # ראשון, אחרון או אינדקס מחוץ לרשימה
    return arr[index] < arr[index - 1] and arr[index] < arr[index + 1]

דוגמה: ברשימה `[5, 2, 7, 3, 3, 1, 4]` האיבר במקום 1 (ערך 2) קטן מ-5 ומ-7 – נפילה. האיבר במקום 3 (ערך 3) אינו קטן מהשכן 3 – לא נפילה.

תשובה: הפעולה `is_fall` שלמעלה.

סעיף ב

תשובה:

עוברים על כל האינדקסים ומגדילים מונה בכל פעם ש-`is_fall(arr, i)` מחזירה `True`; מחזירים את המונה.

הרעיון: עוברים בלולאה על כל המקומות ברשימה, ולכל מקום שואלים את `is_fall` מסעיף א' אם הוא נפילה; אם כן – מגדילים מונה. אין צורך לטפל בנפרד באיבר הראשון ובאחרון: `is_fall` כבר מחזירה עבורם `False`. (לפעולה לא ניתנה כותרת בשאלה, ולכן בחרנו את השם `count_falls`.)

def count_falls(arr):
    count = 0
    for i in range(len(arr)):
        if is_fall(arr, i):
            count = count + 1
    return count

דוגמה: עבור `[5, 2, 7, 3, 3, 1, 4]` הנפילות הן במקומות 1 (ערך 2) ו-5 (ערך 1, קטן מ-3 ומ-4), ולכן הפעולה מחזירה 2.

תשובה: הפעולה `count_falls` שלמעלה.

סעיף ג

תשובה:

`is_fall`: O(1)O(1); `count_falls`: O(n)O(n), כאשר n אורך הרשימה.

נסמן ב-n את אורך הרשימה.

1. `is_fall` (סעיף א): מספר קבוע של השוואות (גבולות ושני שכנים), בלי לולאה, ולא תלוי ב-n – O(1)O(1).

2. `count_falls` (סעיף ב): לולאה אחת של n סיבובים, ובכל סיבוב זימון של `is_fall` שעולה O(1)O(1). סך הכול n⋅O(1)=O(n)n\cdot O(1)=O(n).

תשובה: סעיף א – O(1)O(1); סעיף ב – O(n)O(n).

שאלה 6 · מעקב: חלוקת רשימה לפי ספרת האחדות

נתונה הפעולה `Mystery`. הפעולה מקבלת רשימה של מספרים שלמים חיוביים `arr` וסיפרה `k`

(k – מספר שלם בין 0 ל-9).

def mystery(arr, k):
    left = 0
    right = -1
    while left  - right < len(arr):
        if arr[left]%10 < k:
            left = left + 1
        elif arr[right]%10 > k:
            right = right - 1
        else :
            arr[left],arr[right] = arr[right], arr[left]
            right = right - 1
א.

נתונה רשימת מספרים שלמים `arr = [128, 14, 313, 420, 17, 101]`

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

(5 נקודות)
ב.

נתונה רשימת מספרים שלמים `arr = [128, 14, 313, 420, 17, 101]`

תנו דוגמה של מספר `k` כך שתוכן הרשימה הנתונה `arr` לא ישתנה אחרי זימון הפעולה

`mystery(arr, k)`

(2 נקודות)
ג.

האם קיימת ספרה `k` שעבורה כל רשימה של מספרים שלמים וחיוביים `arr` לא תשתנה אחרי זימון הפעולה `mystery(arr, k)`? הסבירו את תשובתכם.

(2 נקודות)
ד.

מה מבצעת הפעולה `mystery(a, k)` באופן כללי?

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

סעיף א

תשובה:

`arr = [101, 420, 313, 14, 17, 128]`

איך קוראים את הקוד: `left` מתקדם מתחילת הרשימה, ו-`right` הוא אינדקס שלילי שמתקדם מהסוף: `arr[-1]` הוא התא האחרון (תא 5), `arr[-2]` הוא תא 4 וכן הלאה – התא האמיתי הוא 6+right6+right. התנאי `left - right < len(arr)` שקול ל-left<6+rightleft < 6+right, כלומר הלולאה רצה כל עוד `left` נמצא משמאל לתא ש-`right` מצביע עליו.

בכל סיבוב: אם ספרת האחדות של `arr[left]` קטנה מ-4 – `left` מתקדם; אחרת, אם ספרת האחדות של `arr[right]` גדולה מ-4 – `right` זז שמאלה; אחרת מחליפים בין שני התאים ו-`right` זז שמאלה.

ספרות האחדות של האיברים: 128→8, 14→4, 313→3, 420→0, 17→7, 101→1.

צעדleftright (תא אמיתי)`arr[left]%10``arr[right]%10`פעולהarr אחרי הצעד
10-1 (5)8 (לא < 4)1 (לא > 4)החלפה, right = -2[101, 14, 313, 420, 17, 128]
20-2 (4)1 < 4–left = 1[101, 14, 313, 420, 17, 128]
31-2 (4)4 (לא < 4)7 > 4right = -3[101, 14, 313, 420, 17, 128]
41-3 (3)4 (לא < 4)0 (לא > 4)החלפה, right = -4[101, 420, 313, 14, 17, 128]
51-4 (2)0 < 4–left = 2[101, 420, 313, 14, 17, 128]
סוף2-4 (2)2−(−4)=62-(-4)=6, לא קטן מ-6 – הלולאה נעצרת[101, 420, 313, 14, 17, 128]

תשובה: אחרי הזימון `arr = [101, 420, 313, 14, 17, 128]`.

סעיף ב

תשובה:

k=9k=9.

הרעיון: הרשימה משתנה רק בענף ה-`else` (החלפה). אם ספרת האחדות של כל האיברים קטנה מ-k, התנאי הראשון מתקיים תמיד: `left` רק מתקדם, אין אף החלפה, והלולאה נגמרת כש-`left` מגיע לתא האחרון.

ספרות האחדות ברשימה הן 8, 4, 3, 0, 7, 1 – הגדולה ביותר היא 8. לכן עבור k=9k=9 כולן קטנות מ-k:

`left` עובר 0→1→2→3→4→5, וכשמגיע ל-5 מתקיים 5−(−1)=65-(-1)=6, לא קטן מ-6, והלולאה נעצרת בלי שינוי.

(עבור כל k אחר בין 0 ל-8 יש איבר שספרת האחדות שלו אינה קטנה מ-k, ומתבצעת החלפה ששינתה את הרשימה.)

תשובה: k=9k=9.

סעיף ג

תשובה:

לא. לכל k יש רשימה שמשתנה: עבור k=0k=0 – `[5, 10]` הופכת ל-`[10, 5]`; עבור 1≤k≤91\le k\le 9 – `[k, 10]` הופכת ל-`[10, k]`.

הרעיון: כדי להראות שאין k כזה מספיק למצוא, לכל k, רשימה אחת שמשתנה.

1. k=0k=0: אף ספרה אינה קטנה מ-0, ולכן התנאי הראשון לא מתקיים לעולם. ניקח `arr = [5, 10]`: `arr[0]%10 = 5` אינו קטן מ-0; `arr[-1]%10 = 0` אינו גדול מ-0; לכן מתבצעת החלפה והרשימה הופכת ל-`[10, 5]`.

2. 1≤k≤91 \le k \le 9: ניקח `arr = [k, 10]` (שני מספרים חיוביים). `arr[0]%10 = k` אינו קטן מ-k; `arr[-1]%10 = 0` אינו גדול מ-k; לכן מתבצעת החלפה והרשימה הופכת ל-`[10, k]`.

בשני המקרים האיבר הראשון אינו "קטן מ-k" והאיבר האחרון אינו "גדול מ-k", ולכן כבר בסיבוב הראשון מתבצעת החלפה בין שני ערכים שונים – והרשימה משתנה.

תשובה: לא קיימת ספרה כזו.

סעיף ד

תשובה:

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

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

1. `left` מתקדם מההתחלה כל עוד הוא פוגש מספרים שספרת האחדות שלהם קטנה מ-k – הם כבר במקומם (בחלק השמאלי).

2. `right` מתקדם מהסוף כל עוד הוא פוגש מספרים שספרת האחדות שלהם גדולה מ-k – הם כבר במקומם (בחלק הימני).

3. כשאף אחד מהם לא יכול להתקדם, `arr[left]` שייך לצד ימין (ספרה ≥k\ge k) ו-`arr[right]` אינו גדול מ-k. מחליפים ביניהם; האיבר שעבר ל-`right` (ספרה ≥k\ge k) נשאר בצד ימין, ו-`right` זז. האיבר שעבר ל-`left` ייבדק בסיבוב הבא: אם ספרתו קטנה מ-k – `left` יתקדם, ואם היא שווה ל-k – הוא יוחלף שוב ימינה.

4. הלולאה נגמרת כששני המצביעים נפגשים.

בסוף: כל המספרים שספרת האחדות שלהם קטנה מ-k נמצאים בתחילת הרשימה, ואחריהם כל המספרים שספרת האחדות שלהם גדולה או שווה ל-k. בסעיף א' (k=4): 101, 420, 313 (ספרות 1, 0, 3) ואחריהם 14, 17, 128 (ספרות 4, 7, 8).

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

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

החנות "Game4U" מוכרת משחקי שולחן לילדים. לשם ניהול ממוחשב של המכירות הוגדרה המחלקה `Game` ולה ארבע תכונות:

שם המשחק – `name`, מטיפוס מחרוזת, `string`

גיל מינימלי – `minAge`, מטיפוס מספר שלם, `int`

מספר שחקנים – `numPlayers`, מטיפוס מספר שלם, `int`

מחיר – `price`, מטיפוס מספר ממשי, `float`

א.

לקוח יכול להחליף את המשחק שקנה למשחק אחר בתנאי שהגיל מינימלי של שני משחקים זהה והמחיר של משחק האחר לא גבוה מהמחיר שקנה הלקוח.

כתבו פעולה המקבלת הפניה למשחק בשם `other` (הפניה לעצם מטיפוס `Game`).

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

`can_replace(self, other)`

(3 נקודות)
ב.

כתבו פעולה המקבלת רשימת משחקים `arr` ומשחק `my_game` שהלקוח מעוניין להחליף.

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

כותרת הפעולה:

`replace(arr, my_game)`

(3 נקודות)
ג.

סבא וסבתא של התאומים אורי ודורון רוצים לקנות להם מתנות ליום ההולדת החמישי שלהם.

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

כתבו פעולה המקבלת רשימת משחקים ומדפיסה את כל הצירופים האפשריים של שני משחקים שונים שעולים יחד פחות מ- 200 ₪.

כותרת הפעולה:

`gift_for_twins(arr)`

(4 נקודות)
ד.

מהי סיבוכיות הפעולות שכתבתם בסעיפים ב' ו- ג' . הסבירו את תשובתכם.

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

סעיף א

תשובה:

`return self.minAge == other.minAge and other.price <= self.price`

הרעיון: `self` הוא המשחק שהלקוח קנה ו-`other` הוא המשחק שהוא רוצה לקבל במקומו. שני תנאים חייבים להתקיים יחד (`and`):

1. אותו גיל מינימלי: `self.minAge == other.minAge`.

2. המחיר של `other` לא גבוה מהמחיר של `self`: `other.price <= self.price` (מחיר שווה מותר).

class Game:
    def __init__(self, name, minAge, numPlayers, price):
        self.name = name
        self.minAge = minAge
        self.numPlayers = numPlayers
        self.price = price

    # סעיף א
    def can_replace(self, other):
        return self.minAge == other.minAge and other.price <= self.price

(הפעולה הבונה `__init__` נכתבה רק כדי שהמחלקה תהיה שלמה; הפעולה המבוקשת היא `can_replace`.)

דוגמה: משחק לגיל 5 במחיר 150.5 אפשר להחליף במשחק לגיל 5 במחיר 60 (`True`), אבל לא להפך (`False`), ולא במשחק לגיל 8.

תשובה: הפעולה `can_replace` שלמעלה.

סעיף ב

תשובה:

מונים את המשחקים `game` ברשימה (פרט ל-`my_game` עצמו) שעבורם `my_game.can_replace(game)` מחזירה `True`.

הרעיון: עוברים על כל המשחקים ברשימה, ולכל משחק `game` שואלים את הפעולה מסעיף א' אם אפשר להחליף את `my_game` אליו: `my_game.can_replace(game)`. אם כן – מגדילים מונה. המשחק `my_game` עצמו (אם הוא נמצא ברשימה) מקיים את התנאים מול עצמו, אבל "החלפה" שלו בעצמו אינה החלפה – לכן מדלגים עליו בבדיקה `game is not my_game`.

def replace(arr, my_game):
    count = 0
    for game in arr:
        if game is not my_game and my_game.can_replace(game):
            count = count + 1
    return count

דוגמה: אם `my_game` הוא משחק לגיל 5 במחיר 150.5, וברשימה יש משחקים לגיל 5 במחירים 60 ו-90 ומשחקים לגיל 8 – הפעולה תחזיר 2.

תשובה: הפעולה `replace` שלמעלה.

סעיף ג

תשובה:

לולאה מקוננת על כל הזוגות i<ji<j; מדפיסים את שמות שני המשחקים אם לשניהם `minAge <= 5` ו-`numPlayers >= 3`, וגם `price` של שניהם יחד קטן מ-200.

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

1. להתאים לילדים בני 5: הגיל המינימלי שלו לכל היותר 5 (`minAge <= 5`).

2. לאפשר לפחות שלושה שחקנים (`numPlayers >= 3`).

ובנוסף, שני המשחקים יחד עולים פחות מ-200 ₪: `g1.price + g2.price < 200`.

כדי לעבור על כל הצירופים של שני משחקים שונים, כל צירוף פעם אחת, משתמשים בלולאה מקוננת שבה `j` מתחיל מ-`i + 1`: כך לא משווים משחק לעצמו, ולא מדפיסים גם (א, ב) וגם (ב, א).

def gift_for_twins(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            g1 = arr[i]
            g2 = arr[j]
            if (g1.minAge <= 5 and g2.minAge <= 5 and
                    g1.numPlayers >= 3 and g2.numPlayers >= 3 and
                    g1.price + g2.price < 200):
                print(g1.name, "+", g2.name)

דוגמה: עבור המשחקים Uno (גיל 5, 4 שחקנים, 60), Chess (גיל 8, 2 שחקנים, 120), Catan (גיל 5, 3 שחקנים, 150.5), Rummy (גיל 5, 4 שחקנים, 90), Taki (גיל 3, 6 שחקנים, 40), Monopoly (גיל 8, 6 שחקנים, 100) – Chess ו-Monopoly נפסלים בגלל הגיל, ומבין השאר מודפסים: Uno + Rummy (150), Uno + Taki (100), Catan + Taki (190.5), Rummy + Taki (130). הצירופים Uno + Catan (210.5) ו-Catan + Rummy (240.5) יקרים מדי.

תשובה: הפעולה `gift_for_twins` שלמעלה.

סעיף ד

תשובה:

`replace`: O(n)O(n); `gift_for_twins`: O(n2)O(n^2), כאשר n מספר המשחקים ברשימה.

נסמן ב-n את מספר המשחקים ברשימה.

1. `replace` (סעיף ב): לולאה אחת על n המשחקים, ובכל סיבוב `can_replace` מבצעת שתי השוואות – O(1)O(1). סך הכול O(n)O(n).

2. `gift_for_twins` (סעיף ג): לולאה מקוננת. עבור כל i הלולאה הפנימית רצה n−1−in-1-i פעמים, ולכן מספר הזוגות הנבדקים הוא

(n−1)+(n−2)+⋯+1+0=n(n−1)2(n-1)+(n-2)+\dots+1+0=\frac{n(n-1)}{2}

ובכל זוג עבודה קבועה. לכן הסיבוכיות O(n2)O(n^2).

תשובה: סעיף ב – O(n)O(n); סעיף ג – O(n2)O(n^2).

שאלה 8 · סט שלם של ספרות בתת-רשימה

א.

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

כותרת הפעולה:

`exists(num, dig)`

(3 נקודות)
ב.

אוסף של מספרים שלמים חיוביים נקרא "סט שלם של ספרות" אם כל הספרות בין 0 ל- 9 מופיעות בו לפחות פעם אחת.

לדוגמה:

הרשימה `arr1` היא "סט שלם של ספרות"

arr1012345678
7132817142059611861317

גם שתי תת-רשימות

12345
3281714205961
345678
142059611861317

הן "סט שלם של ספרות" כל אחת

הרשימה הבאה היא לא " סט שלם של ספרות " כי סיפרה 7 לא מופיעה באף אחד מאיברי הרשימה.

arr20123456789
31328142059611061319234

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

כותרת הפעולה:

`is_full_set(arr, left, right)`

(6 נקודות)
ג.

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

לדוגמה:

עבור הרשימה `arr1` (מהדוגמה בסעיף ב') הפעולה תחזיר 5, עבור הרשימה `arr2` (מהדוגמה בסעיף ב') הפעולה תחזיר (1-).

כותרת הפעולה:

`min_full_set(arr)`

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

סעיף א

תשובה:

מפרקים את `num` לספרות בעזרת `% 10` ו-`// 10`; אם אחת מהן שווה ל-`dig` מחזירים `True`, ואם נגמרו הספרות – `False`.

הרעיון: הדרך הרגילה לעבור על ספרות של מספר:

1. `num % 10` היא ספרת האחדות הנוכחית – משווים אותה ל-`dig`, ואם שוות מחזירים `True` מיד.

2. `num // 10` "מוחק" את ספרת האחדות, וממשיכים לספרה הבאה.

3. כש-`num` מגיע ל-0 עברנו על כל הספרות בלי למצוא את `dig` – מחזירים `False`.

כיוון ש-`num` חיובי, הלולאה עוברת על כל ספרותיו, כולל אפסים באמצע או בסוף (למשל ב-205 נבדקות 5, 0, 2).

def exists(num, dig):
    while num > 0:
        if num % 10 == dig:
            return True
        num = num // 10
    return False

דוגמה: `exists(205, 0)` מחזירה `True`; `exists(205, 7)` מחזירה `False`.

תשובה: הפעולה `exists` שלמעלה.

סעיף ב

תשובה:

לכל ספרה `dig` מ-0 עד 9 מחפשים תא `i` בין `left` ל-`right` (כולל) שבו `exists(arr[i], dig)`; אם יש ספרה שלא נמצאה – `False`, אחרת `True`.

הרעיון: "סט שלם" פירושו שכל אחת מעשר הספרות 0–9 מופיעה באחד המספרים לפחות. לכן הולכים לפי הספרות:

1. לולאה חיצונית על `dig` מ-0 עד 9.

2. לכל ספרה מחפשים בתת-הרשימה – התאים מ-`left` עד `right`, כולל שני הקצוות (כמו בדוגמה, שבה התת-רשימה 1–5 כוללת את התאים 1 ו-5) – מספר שהספרה מופיעה בו, בעזרת `exists` מסעיף א'. החיפוש נעצר ברגע שנמצא מספר כזה (`found`).

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

4. אם כל עשר הספרות נמצאו – מחזירים `True`.

def is_full_set(arr, left, right):
    for dig in range(10):
        found = False
        i = left
        while i <= right and not found:
            if exists(arr[i], dig):
                found = True
            i = i + 1
        if not found:
            return False
    return True

בדיקה על הדוגמה: בתת-הרשימה 1–5 של `arr1` (32, 817, 14, 205, 961) מופיעות הספרות 3, 2 / 8, 1, 7 / 4 / 0, 5 / 9, 6 – כל עשר הספרות, ולכן `is_full_set(arr1, 1, 5)` מחזירה `True`. לעומת זאת `is_full_set(arr1, 2, 5)` מחזירה `False` (חסרות 3 ו-2), ו-`is_full_set(arr2, 0, 9)` מחזירה `False` (חסרה 7).

תשובה: הפעולה `is_full_set` שלמעלה.

סעיף ג

תשובה:

בודקים אורכים מ-1 עד `len(arr)`; לכל אורך עוברים על כל נקודות ההתחלה ובודקים עם `is_full_set`. האורך הראשון שנמצא עבורו סט שלם מוחזר; אם אין – מחזירים 1-.

הרעיון: מחפשים את האורך הקטן ביותר, ולכן בודקים את האורכים בסדר עולה: 1, 2, 3, ... . האורך הראשון שעבורו קיימת תת-רשימה שהיא סט שלם הוא בהכרח הקטן ביותר, ואפשר להחזיר אותו מיד.

1. לכל אורך `length` מ-1 עד n (אורך הרשימה), עוברים על כל נקודות ההתחלה האפשריות `left` מ-0 עד `n - length`. תת-הרשימה היא התאים מ-`left` עד `left + length - 1`.

2. לכל תת-רשימה כזו שואלים את `is_full_set` מסעיף ב'. אם התשובה `True` – מחזירים את `length`.

3. אם עברנו על כל האורכים (כולל הרשימה כולה) ולא נמצא סט שלם – מחזירים 1-.

def min_full_set(arr):
    n = len(arr)
    for length in range(1, n + 1):
        for left in range(n - length + 1):
            if is_full_set(arr, left, left + length - 1):
                return length
    return -1

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

•`arr1`: אף תת-רשימה באורך 1–4 אינה מכילה את כל עשר הספרות, ובאורך 5 התת-רשימה שמתחילה בתא 1 (32, 817, 14, 205, 961) היא סט שלם – הפעולה מחזירה 5.

•`arr2`: הספרה 7 לא מופיעה באף איבר, ולכן אף תת-רשימה (גם לא הרשימה כולה) אינה סט שלם – הפעולה מחזירה 1-.

תשובה: הפעולה `min_full_set` שלמעלה.

שאלה 9 · מחלקות חולצה ומחסן: סינון ומבצע

החנות "חלץ לך חולצה" מוכרת חולצות של מותגים שונים באמצעות האינטרנט. לשם כך הוגדרו המחלקות `Shirt` ו- `Storage`.

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

•קוד מתנה – `code` – מטיפוס מספר שלם, `int`

•שם מותג – `brand` – מטיפוס מחרוזת, `string`

•מחיר – `price` – מטיפוס ממשי, `float`

•סוג חולצה (למי מיועדת החולצה) – `type` – מטיפוס תו, `char`.

התכונה יכולה לקבל אחת משלוש האפשרויות הבאות:

'F' – חולצות לנשים, 'M' – לגברים, 'K' – לילדים.

א.

כתבו פעולה `set_type(self, type)`. הפעולה מעדכנת את התכונה `type` בהתאם לפרמטר.

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

(2 נקודות)
ב.

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

•רשימת חולצות – `shirts` – רשימה של עצמים מטיפוס `Shirt`

•רשימת מותגים שהחנות מוכרת – `brands` – רשימה של מחרוזות

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

כותרת הפעולה:

`shirts_by_brand(self, brand, type)`

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

(6 נקודות)
ג.

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

כתבו במחלקה `Storage` פעולה המדפיסה שמות של כל המותגים אשר יוכלו להשתתף במבצע.

כותרת הפעולה:

`print_names(self)`

(5 נקודות)
ד.

מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיפים ב' ו- ג'? הסבירו את תשובתכם.

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

סעיף א

תשובה:

`if type == 'F' or type == 'M' or type == 'K': self.type = type`

הרעיון: ערך תקין הוא אחד משלושת התווים 'F', 'M', 'K'. בודקים את הפרמטר מול שלושתם (`or`); רק אם הוא אחד מהם מעדכנים את התכונה, ואחרת לא עושים דבר (התכונה שומרת על ערכה הקודם).

class Shirt:
    def __init__(self, code, brand, price, type):
        self.code = code
        self.brand = brand
        self.price = price
        self.type = type

    # סעיף א
    def set_type(self, type):
        if type == 'F' or type == 'M' or type == 'K':
            self.type = type

דוגמה: אם לחולצה `type = 'F'`, הזימון `set_type('X')` לא משנה אותה, והזימון `set_type('K')` משנה אותה ל-'K'.

תשובה: הפעולה `set_type` שלמעלה.

סעיף ב

תשובה:

יוצרים רשימה ריקה `res`, עוברים על `self.shirts` ומוסיפים כל חולצה שבה `shirt.brand == brand and shirt.type == type`; מחזירים את `res`.

הרעיון: סינון של רשימת החולצות:

1. מתחילים מרשימה ריקה `res` – כך, אם לא תימצא אף חולצה מתאימה, תוחזר רשימה ריקה כנדרש.

2. עוברים על כל החולצות במחסן (`self.shirts`), ולכל חולצה בודקים ששני התנאים מתקיימים: המותג שלה הוא `brand` וגם הסוג שלה הוא `type`.

3. חולצה מתאימה מוסיפים ל-`res` (את העצם עצמו), ובסוף מחזירים את `res`.

class Storage:
    def __init__(self, shirts, brands):
        self.shirts = shirts
        self.brands = brands

    def shirts_by_brand(self, brand, type):
        res = []
        for shirt in self.shirts:
            if shirt.brand == brand and shirt.type == type:
                res.append(shirt)
        return res

דוגמה: אם במחסן יש חולצות Nike מסוגים 'F', 'M', 'K' ושתי חולצות Zara, הזימון `shirts_by_brand("Nike", 'M')` מחזיר רשימה עם חולצת ה-Nike לגברים, והזימון `shirts_by_brand("Adidas", 'F')` מחזיר `[]`.

תשובה: הפעולה `shirts_by_brand` שלמעלה.

סעיף ג

תשובה:

לכל מותג ב-`self.brands` מדפיסים את שמו אם `shirts_by_brand` מחזירה רשימה לא ריקה עבור כל אחד מהסוגים 'F', 'M' ו-'K'.

הרעיון: מותג יכול להשתתף במבצע רק אם יש במחסן חולצות שלו משלושת הסוגים: לנשים ('F') ולגברים ('M') – שאותן המשפחה מזמינה – ולילדים ('K') – שאותה החנות נותנת במתנה.

1. עוברים על כל המותגים ברשימה `self.brands`.

2. לכל מותג מזמנים את `shirts_by_brand` מסעיף ב' שלוש פעמים, פעם לכל סוג, ובודקים שאף אחת מהרשימות אינה ריקה (שלושה תנאים מחוברים ב-`and`).

3. אם שלושת התנאים מתקיימים – מדפיסים את שם המותג.

class Storage:
    # ... (שאר התכונות והפעולות של המחלקה)

    def print_names(self):
        for brand in self.brands:
            if (len(self.shirts_by_brand(brand, 'F')) > 0 and
                    len(self.shirts_by_brand(brand, 'M')) > 0 and
                    len(self.shirts_by_brand(brand, 'K')) > 0):
                print(brand)

דוגמה: אם ל-Nike יש חולצות מכל שלושת הסוגים, ל-Zara רק לנשים ולגברים, ול-Gap מכל שלושת הסוגים – יודפסו Nike ו-Gap.

תשובה: הפעולה `print_names` שלמעלה.

סעיף ד

תשובה:

`shirts_by_brand`: O(n)O(n); `print_names`: O(m⋅n)O(m\cdot n), כאשר n מספר החולצות ו-m מספר המותגים.

נסמן ב-n את מספר החולצות במחסן (אורך `shirts`) וב-m את מספר המותגים (אורך `brands`).

1. `shirts_by_brand` (סעיף ב): מעבר אחד על n החולצות, ובכל חולצה שתי השוואות והוספה לרשימה – O(1)O(1). סך הכול O(n)O(n).

2. `print_names` (סעיף ג): לולאה על m המותגים, ולכל מותג לכל היותר שלושה זימונים של `shirts_by_brand`, כל אחד O(n)O(n): m⋅3⋅O(n)=O(m⋅n)m\cdot 3\cdot O(n)=O(m\cdot n).

תשובה: סעיף ב – O(n)O(n); סעיף ג – O(m⋅n)O(m\cdot n).

שאלה 10 · מעקב ושיפור יעילות: השוואת שתי רשימות

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

def what(arr1, arr2):
    for x in range(len(arr1)):
        for k in range(len(arr2)):
            if arr1[x] >= arr2[k]:
                return True # (*)
    return False # (**)
א.

עקבו בעזרת טבלת מעקב אחר ביצוע הפעולה `what` עבור הפרמטרים הבאים:

`arr1 = [4,6,2,7]`

`arr2 = [8,7,9]`

(4 נקודות)
ב.

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

(2 נקודות)
ג.

מהי סיבוכיות הפעולה `what`? הסבירו את תשובתכם.

(1 נקודות)
ד.

כתבו פעולה חדשה, יעילה יותר, אשר מבצעת אותה מטלה כמו הפעולה `what`.

(4 נקודות)
ה.

מהי סיבוכיות הפעולה החדשה? הסבירו את תשובתכם.

(1 נקודות)
ו.

בפעולה `what` נעשו שני שינוים:

•הפקודה `(*)` הוחלפה ל- `return False`

•הפקודה `()` הוחלפה ל- `return True`

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

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

סעיף א

תשובה:

הפעולה מחזירה `True` (בזוג `x = 3, k = 1`: 7≥77 \ge 7).

הלולאה החיצונית עוברת על התאים של `arr1`, והפנימית משווה כל אחד מהם לכל איברי `arr2`. ברגע שנמצא זוג שבו האיבר מ-`arr1` גדול או שווה לאיבר מ-`arr2` – הפעולה מחזירה `True` ונעצרת.

אינדקס x`arr1[x]`k`arr2[k]``arr1[x] >= arr2[k]`פעולה
0408לאממשיכים
0417לאממשיכים
0429לאממשיכים
1608לאממשיכים
1617לאממשיכים
1629לאממשיכים
2208לאממשיכים
2217לאממשיכים
2229לאממשיכים
3708לאממשיכים
3717כן`return True`

תשובה: הפעולה מחזירה `True`.

סעיף ב

תשובה:

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

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

ניסוח שקול: זוג כזה קיים בדיוק כשהאיבר הגדול ביותר ב-`arr1` גדול או שווה לאיבר הקטן ביותר ב-`arr2`. (אם אחת הרשימות ריקה – מוחזר `False`.)

תשובה: הפעולה מחזירה `True` אם קיים איבר ב-`arr1` שגדול או שווה לאיבר כלשהו ב-`arr2` (max⁡(arr1)≥min⁡(arr2)\max(arr1) \ge \min(arr2)), ואחרת `False`.

סעיף ג

תשובה:

O(n⋅m)O(n\cdot m), כאשר n ו-m אורכי `arr1` ו-`arr2`.

נסמן ב-n את אורך `arr1` וב-m את אורך `arr2`. במקרה הגרוע (כשאין זוג מתאים והפעולה מחזירה `False`) הלולאה החיצונית רצה n פעמים, ובכל אחת הפנימית רצה m פעמים עם השוואה אחת – n⋅mn\cdot m השוואות.

תשובה: O(n⋅m)O(n\cdot m).

סעיף ד

תשובה:

מוצאים את המקסימום של `arr1` ואת המינימום של `arr2` (כל אחד במעבר אחד) ומחזירים `max1 >= min2` (ו-`False` אם אחת הרשימות ריקה).

הרעיון: לפי סעיף ב', אין צורך לבדוק את כל הזוגות: אם יש זוג שבו arr1[x]≥arr2[k]arr1[x] \ge arr2[k], אז בוודאי max⁡(arr1)≥arr1[x]≥arr2[k]≥min⁡(arr2)\max(arr1) \ge arr1[x] \ge arr2[k] \ge \min(arr2); ולהפך, אם max⁡(arr1)≥min⁡(arr2)\max(arr1) \ge \min(arr2) אז הזוג (המקסימום, המינימום) עצמו מתאים. לכן:

1. אם אחת הרשימות ריקה – אין אף זוג, ו-`what` המקורית מחזירה `False`; גם החדשה מחזירה `False`.

2. מוצאים את האיבר הגדול ביותר ב-`arr1` במעבר אחד.

3. מוצאים את האיבר הקטן ביותר ב-`arr2` במעבר אחד.

4. מחזירים את תוצאת ההשוואה `max1 >= min2`.

def what2(arr1, arr2):
    if len(arr1) == 0 or len(arr2) == 0:
        return False
    max1 = arr1[0]
    for x in arr1:
        if x > max1:
            max1 = x
    min2 = arr2[0]
    for y in arr2:
        if y < min2:
            min2 = y
    return max1 >= min2

בדיקה על הנתונים מסעיף א': max⁡(arr1)=7\max(arr1)=7, min⁡(arr2)=7\min(arr2)=7, ו-7≥77 \ge 7 – מוחזר `True`, כמו ב-`what`.

תשובה: הפעולה `what2` שלמעלה.

סעיף ה

תשובה:

O(n+m)O(n+m).

הפעולה החדשה עוברת פעם אחת על `arr1` (n איברים) ופעם אחת על `arr2` (m איברים), בלולאות נפרדות ולא מקוננות, ובכל צעד עבודה קבועה: O(n)+O(m)=O(n+m)O(n)+O(m)=O(n+m).

תשובה: O(n+m)O(n+m).

סעיף ו

תשובה:

מחזירה `True` אם כל איבר ב-`arr1` קטן מכל איבר ב-`arr2` (כלומר max⁡(arr1)<min⁡(arr2)\max(arr1) < \min(arr2)), ואחרת `False`.

אחרי השינוי, ברגע שנמצא זוג שבו arr1[x]≥arr2[k]arr1[x] \ge arr2[k] הפעולה מחזירה `False`; רק אם אין אף זוג כזה – כלומר לכל x ולכל k מתקיים arr1[x]<arr2[k]arr1[x] < arr2[k] – הפעולה מגיעה לסוף ומחזירה `True`. זו בדיוק השלילה של הפעולה המקורית.

לדוגמה, עבור הנתונים מסעיף א' תוחזר עכשיו `False` (בגלל 7≥77 \ge 7), ועבור `arr1 = [1, 2]`, `arr2 = [3, 4]` תוחזר `True`.

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

שאלה 11 · מעקב: מחיקת מופעים של תו ממחרוזת

נתונות הפעולות הבאות:

הפעולה `one` מקבלת מחרוזת `s`, תו `ch` ומספר שלם `k`:

def one(s, ch, k):
    res = ""
    while k>0 and len(s)>0:
        if(s[0] == ch):
            k = k-1
        else:
            res = res + s[0]
        s=s[1:]
    return res + s

הפעולה `two` מקבלת רשימת מחרוזות `arr` ותו `ch`:

def two(arr, ch):
    for x in range(1, len(arr),2):
        print(arr[x],arr[x-1], one(arr[x-1],ch, x))
        if arr[x] !=one(arr[x-1],ch, x):
            return False
    return True
א.

מה תהיה תוצאת הזימון `one(s1, 'A', 2)` עבור מחרוזת `s1="AABBAAD"`? יש להראות מעקב!

(4 נקודות)
ב.

מה תהיה תוצאת הזימון `one(s1, 'F', 3)` עבור מחרוזת `s1="AABBAAD"`?

(2 נקודות)
ג.

נתונה מחרוזת `s2="AABCCDDC"`. תנו דוגמה לפרמטרים `k` ו-`ch` כך שתוצאת הזימון `one(s2, ch, k)` תהיה מחרוזת `s3="AABDDC"`.

(3 נקודות)
ד.

מה מבצעת הפעולה `one`?

(2 נקודות)
ה.

תנו דוגמה לרשימה `arr` של שמונה מחרוזות שונות זו מזו, שעבורה זימון הפעולה `two(arr,'Z')` יחזיר `True`.

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

סעיף א

תשובה:

`"BBAAD"`

בכל סיבוב בודקים את התו הראשון של `s`: אם הוא שווה ל-`ch` – מקטינים את k (התו "נמחק", לא נכנס ל-`res`); אחרת מוסיפים אותו ל-`res`. בשני המקרים מורידים אותו מ-`s` (`s=s[1:]`). הלולאה נעצרת כש-k מגיע ל-0 או ש-`s` מתרוקנת, ואז מוחזר `res + s`.

סיבוב`s[0]`שווה ל-'A'?k אחריres אחריs אחרי
התחלה2"""AABBAAD"
1'A'כן1"""ABBAAD"
2'A'כן0"""BBAAD"
סוףk=0k=0 – הלולאה נעצרת

מוחזר res+sres + s = "" + "BBAAD".

תשובה: `"BBAAD"`.

סעיף ב

תשובה:

`"AABBAAD"` (המחרוזת לא משתנה).

התו 'F' אינו מופיע במחרוזת, ולכן k נשאר 3 לאורך כל הלולאה, וכל התווים עוברים אחד-אחד ל-`res`. הלולאה נעצרת כש-`s` מתרוקנת:

סיבוב`s[0]`שווה ל-'F'?kres אחריs אחרי
1'A'לא3"A""ABBAAD"
2'A'לא3"AA""BBAAD"
3'B'לא3"AAB""BAAD"
4'B'לא3"AABB""AAD"
5'A'לא3"AABBA""AD"
6'A'לא3"AABBAA""D"
7'D'לא3"AABBAAD"""

מוחזר res+sres + s = "AABBAAD" + "".

תשובה: `"AABBAAD"`.

סעיף ג

תשובה:

`ch = 'C'`, `k = 2`.

משווים את המחרוזות: "AABCCDDC" לעומת "AABDDC" – חסרים שני תווי 'C' שבמקומות 3 ו-4, וה-'C' האחרון נשאר. לפי סעיף ד', `one` מוחקת את k המופעים הראשונים של `ch`, ולכן צריך `ch = 'C'` ו-k=2k=2:

- 'A', 'A', 'B' עוברים ל-`res` → "AAB".

- 'C' נמחק (k=1), 'C' נמחק (k=0) – הלולאה נעצרת, ו-`s` = "DDC".

•מוחזר "AAB" + "DDC" = "AABDDC".

(עם k=1k=1 היה נמחק רק 'C' אחד, ועם k≥3k\ge 3 היו נמחקים כל שלושת ה-'C'.)

תשובה: `ch = 'C'`, `k = 2`.

סעיף ד

תשובה:

מחזירה את המחרוזת `s` בלי k המופעים הראשונים של התו `ch` (אם יש פחות מ-k מופעים – בלי כולם); שאר התווים בסדרם המקורי.

הפעולה עוברת על המחרוזת משמאל לימין. כל מופע של `ch` מדולג (ו-k קטן ב-1), וכל תו אחר מועתק ל-`res`. כש-k מגיע ל-0, הלולאה נעצרת ושארית המחרוזת מצורפת כמו שהיא – כלומר מופעים נוספים של `ch` כבר לא נמחקים. אם המחרוזת נגמרת לפני ש-k מגיע ל-0, נמחקו כל המופעים של `ch`.

תשובה: הפעולה מחזירה מחרוזת חדשה שהיא `s` אחרי מחיקת k המופעים הראשונים של התו `ch` (או כל המופעים, אם יש פחות מ-k).

סעיף ה

תשובה:

למשל `arr = ["ZA", "A", "ZZZB", "B", "ZC", "C", "DZ", "D"]`.

ניתוח של `two`: הלולאה עוברת על האינדקסים האי-זוגיים x=1,3,5,7x=1,3,5,7. לכל x היא משווה את `arr[x]` לתוצאה של `one(arr[x-1], 'Z', x)` – כלומר ל-`arr[x-1]` אחרי מחיקת x המופעים הראשונים של 'Z'. אם יש אי-התאמה – מוחזר `False`; אם כל ארבעת הזוגות מתאימים – `True`.

לכן צריך שכל מחרוזת במקום אי-זוגי תהיה המחרוזת שלפניה בלי (עד) x ה-'Z' הראשונים שלה. כדי שכל המחרוזות יהיו שונות, המחרוזת במקום הזוגי חייבת להכיל 'Z' (אחרת `one` מחזירה אותה בלי שינוי, ואז `arr[x]` יהיה זהה ל-`arr[x-1]`). נבחר מחרוזות שבהן מספר ה-'Z' אינו גדול מ-x, כך שכולם נמחקים:

אינדקס x`arr[x-1]``one(arr[x-1], 'Z', x)``arr[x]`שווים?
1"ZA""A""A"כן
3"ZZZB""B""B"כן
5"ZC""C""C"כן
7"DZ""D""D"כן

כל ארבע ההשוואות מתאימות, ולכן `two(arr, 'Z')` מחזירה `True`. כל שמונה המחרוזות שונות זו מזו. (במהלך הריצה מודפסות השורות `A ZA A`, `B ZZZB B`, `C ZC C`, `D DZ D`.)

תשובה: `arr = ["ZA", "A", "ZZZB", "B", "ZC", "C", "DZ", "D"]`.

שאלה 12 · זוג מתאים: ערכי קיצון בעמודות

רשימת מספרים `arr` ו- `mat` המוגדרת כרשימת רשימות של מספרים (רשימה שכל איבר בה הוא רשימה) הללו מוגדרים "זוג מתאים" אם מתקיימים התנאים הבאים:

•אורך של כל איבר ברשימה `mat` שווה לאורך הרשימה `arr`.

•כל איבר `arr[k]` הוא ערך קיצון (הכי גדול או הכי קטן) בין הערכים הנמצאים במקום k בכל אחת מהרשימות של `mat`.

לדוגמה:

שתי רשימות `arr` ו-`mat` הבאות הן "זוג מתאים"

k:0123
arr:412157
k:0123
mat:3181012
4121027
116414
1914100
1221515
7177
א.

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

אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.

כותרת הפעולה:

`is_extreme (mat, k, value)`

(4 נקודות)
ב.

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

ולא – הפעולה תחזיר `False`.

כותרת הפעולה:

`is_pair (mat, arr)`

(5 נקודות)
ג.

מהי הסיבוכיות של הפעולה `is_pair`? הסבירו את תשובתכם.

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

סעיף א

תשובה:

מחשבים את המקסימום והמינימום של `row[k]` על כל השורות `row` ב-`mat`, ומחזירים `value == max_val or value == min_val`.

הרעיון: "הערכים הנמצאים במקום k בכל אחת מהרשימות" הם העמודה k: `mat[0][k], mat[1][k], ...`. ערך הוא ערך קיצון אם הוא שווה לגדול ביותר או לקטן ביותר מביניהם.

1. מאתחלים את `max_val` ואת `min_val` לערך בשורה הראשונה, `mat[0][k]` (מניחים ש-`mat` אינה ריקה).

2. עוברים על כל השורות ומעדכנים את המקסימום והמינימום של `row[k]`.

3. מחזירים `True` אם `value` שווה לאחד מהם (`or`).

def is_extreme(mat, k, value):
    max_val = mat[0][k]
    min_val = mat[0][k]
    for row in mat:
        if row[k] > max_val:
            max_val = row[k]
        if row[k] < min_val:
            min_val = row[k]
    return value == max_val or value == min_val

בדיקה על הדוגמה: בעמודה 0 הערכים הם 31, 4, 11, 19, 12, 7 – המקסימום 31 והמינימום 4. לכן `is_extreme(mat, 0, 4)` ו-`is_extreme(mat, 0, 31)` מחזירות `True`, ו-`is_extreme(mat, 0, 11)` מחזירה `False`.

תשובה: הפעולה `is_extreme` שלמעלה.

סעיף ב

תשובה:

בודקים שכל שורה ב-`mat` באורך `len(arr)`, ואחר כך שלכל k מתקיים `is_extreme(mat, k, arr[k])`; אם אחת הבדיקות נכשלת – `False`, אחרת `True`.

הרעיון: בודקים את שני התנאים של ההגדרה לפי הסדר:

1. תנאי 1: עוברים על כל השורות של `mat`; אם יש שורה שאורכה שונה מ-`len(arr)` – מחזירים `False`. (חשוב לבדוק את התנאי הזה קודם, כי רק אז בטוח לגשת ל-`row[k]` לכל k.) אם `mat` ריקה אין עמודות להשוות אליהן, ומחזירים `False`.

2. תנאי 2: לכל מקום k ב-`arr` משתמשים בפעולה מסעיף א': אם `arr[k]` אינו ערך קיצון בעמודה k – מחזירים `False`.

3. אם שני התנאים התקיימו – מחזירים `True`.

def is_pair(mat, arr):
    if len(mat) == 0:
        return False
    for row in mat:                     # תנאי 1: אורך כל שורה
        if len(row) != len(arr):
            return False
    for k in range(len(arr)):           # תנאי 2: כל arr[k] ערך קיצון בעמודה k
        if not is_extreme(mat, k, arr[k]):
            return False
    return True

בדיקה על הדוגמה: כל השורות באורך 4. עמודה 0: מינימום 4 = `arr[0]`; עמודה 1 (8, 12, 6, 1, 2, 1): מקסימום 12 = `arr[1]`; עמודה 2 (10, 10, 4, 4, 15, 7): מקסימום 15 = `arr[2]`; עמודה 3 (12, 27, 14, 100, 15, 7): מינימום 7 = `arr[3]`. לכן מוחזר `True`.

תשובה: הפעולה `is_pair` שלמעלה.

סעיף ג

תשובה:

O(r⋅c)O(r\cdot c), כאשר r מספר הרשימות ב-`mat` ו-c אורך `arr`.

נסמן ב-r את מספר הרשימות (השורות) ב-`mat` וב-c את אורך `arr`.

1. בדיקת האורכים: מעבר אחד על r השורות – O(r)O(r).

2. לולאה על c המקומות, ובכל אחד זימון של `is_extreme` שעוברת על r השורות – c⋅O(r)=O(r⋅c)c\cdot O(r)=O(r\cdot c).

סך הכול O(r)+O(r⋅c)=O(r⋅c)O(r)+O(r\cdot c)=O(r\cdot c) – כלומר לינארי במספר האיברים ב-`mat`.

תשובה: O(r⋅c)O(r\cdot c).

שאלה 13 · מחלקות נכס ועירייה: ארנונה והנחות

בעיריית דימונה קיימת מערכת ממוחשבת לגביית מיסוי עירוני (ארנונה). במערכת הוגדרה המחלקה `Property` (נכס) ולה התכונות הבאות:

•מספר הנכס – `num`, מטיפוס מחרוזת, `string`

•מספר תעודת הזהות של המשלם – `id`, מטיפוס מחרוזת, `string`

•כתובת הנכס – `address`, מטיפוס מחרוזת, `string`

•שטח הנכס – `area`, מטיפוס מספר ממשי, `float`

•זכאות להנחה – `discount`, מספר שלם בין 0 ל- 3, כאשר:

0 – מציין שאין הנחה, תשלום מלא,

1 – תשלום מופחת, הנחה של 10%,

2 – הנחה של 50%,

3 – פטור מלא מתשלומי ארנונה

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

א.

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

כותרת הפעולה:

`real_account(self)`

(3 נקודות)
ב.

המחלקה `CityData` מאחסנת נתונים של כל הנכסים בעיר.

למחלקה תכונה אחת – רשימה `arr`, רשימה של עצמים מסוג `Property`.

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

כותרת הפעולה:

`total_discount(self)`

(3 נקודות)
ג.

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

•יש בבעלותו רק נכס אחד

•רמת הזכאות של נכס נמוכה מרמת הזכאות המבוקשת

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

- "תעודת הזהות אינה ברשימת משלמי ארנונה"

- "יש יותר מנכס אחד בבעלותו"

- "רמת הזכאות המבוקשת נמוכה מנוכחית"

כותרת הפעולה:

`print_decision(self, ids, level)`

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

סעיף א

תשובה:

`full = self.account()`; לפי `discount`: 0 → `full`, 1 → `full * 0.9`, 2 → `full * 0.5`, 3 → 0.

הרעיון: הסכום המלא כבר מחושב בפעולה הקיימת `account`, ולכן מזמנים אותה ומפעילים עליה את ההנחה לפי רמת הזכאות:

1. רמה 0 – אין הנחה: משלמים 100% מהסכום.

2. רמה 1 – הנחה של 10%: משלמים 90%, כלומר `full * 0.9`.

3. רמה 2 – הנחה של 50%: משלמים 50%, כלומר `full * 0.5`.

4. רמה 3 – פטור מלא: משלמים 0.

class Property:
    # ... (שאר התכונות והפעולות של המחלקה)

    def real_account(self):
        full = self.account()
        if self.discount == 1:
            return full * 0.9
        if self.discount == 2:
            return full * 0.5
        if self.discount == 3:
            return 0
        return full

דוגמה: אם `account()` מחזירה 4000, אז לפי הרמות 0, 1, 2, 3 יוחזרו 4000, 4000⋅0.9=36004000\cdot 0.9=3600, 4000⋅0.5=20004000\cdot 0.5=2000 ו-0.

תשובה: הפעולה `real_account` שלמעלה.

סעיף ב

תשובה:

סוכמים על כל הנכסים את ההפרש `p.account() - p.real_account()` ומחזירים את הסכום.

הרעיון: ההנחה שנכס מקבל היא ההפרש בין הסכום המלא לסכום שמשלמים בפועל: `p.account() - p.real_account()` (בנכס בלי הנחה ההפרש הוא 0). עוברים על כל הנכסים ברשימה `self.arr` וצוברים את ההפרשים.

class CityData:
    def __init__(self, arr):
        self.arr = arr

    def total_discount(self):
        total = 0
        for p in self.arr:
            total = total + (p.account() - p.real_account())
        return total

דוגמה: שני נכסים עם חשבון מלא של 4000 כל אחד, אחד ברמה 1 ואחד ברמה 2: ההנחות הן 4000−3600=4004000-3600=400 ו-4000−2000=20004000-2000=2000, ובסך הכול 2400.

תשובה: הפעולה `total_discount` שלמעלה.

סעיף ג

תשובה:

לכל `id` ב-`ids` סופרים את הנכסים שלו: 0 – הודעה ראשונה; יותר מ-1 – הודעה שנייה; נכס יחיד עם `discount >= level` – הודעה שלישית; אחרת `discount = level`.

הרעיון: מטפלים בכל בקשה (כל תעודת זהות ברשימה `ids`) בנפרד:

1. עוברים על כל הנכסים בעיר וסופרים כמה נכסים רשומים על תעודת הזהות הזו (`count`), ושומרים הפניה לנכס שנמצא (`prop`).

2. אם `count == 0` – התושב לא משלם ארנונה בכלל: מדפיסים את ההודעה הראשונה.

3. אם `count > 1` – יש לו יותר מנכס אחד, התנאי הראשון לא מתקיים: מדפיסים את ההודעה השנייה.

4. אחרת יש נכס אחד בדיוק, `prop`. אם רמת הזכאות הנוכחית שלו אינה נמוכה מהמבוקשת (`prop.discount >= level`) – התנאי השני לא מתקיים: מדפיסים את ההודעה השלישית. (גם כשהרמות שוות אין מה לעדכן, והודעה זו היא המתאימה מבין השלוש.)

5. אחרת שני התנאים מתקיימים – מעדכנים: `prop.discount = level`.

class CityData:
    # ... (שאר התכונות והפעולות של המחלקה)

    def print_decision(self, ids, level):
        for id in ids:
            count = 0
            prop = None
            for p in self.arr:
                if p.id == id:
                    count = count + 1
                    prop = p
            if count == 0:
                print("תעודת הזהות אינה ברשימת משלמי ארנונה")
            elif count > 1:
                print("יש יותר מנכס אחד בבעלותו")
            elif prop.discount >= level:
                print("רמת הזכאות המבוקשת נמוכה מנוכחית")
            else:
                prop.discount = level

דוגמה: אם התושב 111 בעל נכס יחיד ברמה 0, התושב 333 בעל שני נכסים והתושב 444 בעל נכס יחיד ברמה 3, אז עבור `ids = ["111", "999", "333", "444"]` ו-`level = 2`: הנכס של 111 מתעדכן לרמה 2; עבור 999 מודפס "תעודת הזהות אינה ברשימת משלמי ארנונה"; עבור 333 – "יש יותר מנכס אחד בבעלותו"; עבור 444 – "רמת הזכאות המבוקשת נמוכה מנוכחית".

תשובה: הפעולה `print_decision` שלמעלה.

שאלה 14 · רקורסיה: מספר מחלקים ובחירה בין קצוות

נתונה הפעולה `secret` הבאה המקבלת מספר שלם גדול מ- 0:

def secret(n):
    return real_secret(n, 1)

def real_secret(n, k):
    if k == n:
        return 1
    if n % k == 0:
        return 1 + real_secret(n, k+1)
    return real_secret(n, k+1)
א.

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

(1)

`secret(12)`

(2)

`secret(7)`

(3)

`secret(15)`

(3 נקודות)
ב.

מה מבצעת הפעולה `secret(n)` עבור מספר שלם גדול מ- 0?

(2 נקודות)

נתונה הפעולה `sod` המקבלת רשימה של מספרים שלמים גדולים מ- 0:

def sod(arr):
    return real_sod(arr, 0, len(arr)-1)

def real_sod(arr, i, j):
    if(i == j):
        return arr[i]
    if secret(arr[i]) < secret(arr[j]):
        j = j - 1
    else:
        i = i + 1
    return real_sod(arr, i, j)
ג.

עקבו אחרי זימון הפעולה `sod(arr)` עבור הרשימה הבאה:

`arr = [4,6,12,17,24,15,10]`

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

(4 נקודות)
ד.

מה מבצעת הפעולה `sod` עבור רשימה של מספרים שלמים גדולים מ- 0?

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

סעיף א

(1)
תשובה:

6

`secret(12)` מזמנת את `real_secret(12, 1)`. בכל זימון k גדל ב-1: אם k מחלק את 12 מוסיפים 1, אחרת לא מוסיפים; כש-k מגיע ל-12 מוחזר 1.

k`12 % k`תרומה
101
201
301
401
520
601
750
840
930
1020
1110
12`k == n`1

סכום התרומות: 1+1+1+1+0+1+0+0+0+0+0+1=61+1+1+1+0+1+0+0+0+0+0+1=6.

תשובה: 6.

(2)
תשובה:

2

`real_secret(7, 1)`: עבור k=1k=1 – 7%1=07 \% 1 = 0, תרומה 1; עבור k=2,…,6k=2,\dots,6 השארית 7%k7 \% k היא 1, 1, 3, 2, 1 (שונה מ-0), אין תרומה; עבור k=7k=7 – `k == n`, מוחזר 1.

סך הכול 1+1=21+1=2.

תשובה: 2.

(3)
תשובה:

4

`real_secret(15, 1)`: מבין k=1,…,14k=1,\dots,14 רק 1, 3, 5 מחלקים את 15 (תרומה 1 כל אחד); עבור k=15k=15 מוחזר 1.

סך הכול 3+1=43+1=4.

nk שעבורם `n % k == 0` (מ-1 עד n-1)תרומה של `k == n`התוצאה
121, 2, 3, 4, 615+1=65+1=6
7111+1=21+1=2
151, 3, 513+1=43+1=4

תשובה: 4.

סעיף ב

תשובה:

מחזירה את מספר המחלקים של n (כולל 1 ו-n).

הפעולה עוברת ברקורסיה על k=1,2,…,n−1k=1,2,\dots,n-1 ומוסיפה 1 על כל k שמחלק את n ללא שארית. בתנאי העצירה k=nk=n היא מחזירה 1 – וזה בדיוק המחלק n עצמו (כל מספר מתחלק בעצמו). לכן התוצאה היא מספר כל המחלקים של n. (עבור n=1n=1: מיד `k == n` ומוחזר 1 – ל-1 מחלק אחד.)

לדוגמה: ל-12 יש 6 מחלקים (1, 2, 3, 4, 6, 12), ול-7, שהוא ראשוני, יש 2.

תשובה: הפעולה מחזירה את מספר המחלקים של n.

סעיף ג

תשובה:

17

קודם מחשבים לפי סעיף ב' את מספר המחלקים של כל איבר:

- 4: 1, 2, 4 → 3

- 6: 1, 2, 3, 6 → 4

- 12: 6 (סעיף א)

- 17 (ראשוני): 1, 17 → 2

- 24: 1, 2, 3, 4, 6, 8, 12, 24 → 8

- 15: 4 (סעיף א)

- 10: 1, 2, 5, 10 → 4

`sod(arr)` מזמנת את `real_sod(arr, 0, 6)`. בכל זימון: אם למספר שב-i יש פחות מחלקים מאשר למספר שב-j – מזיזים את j שמאלה (המספר שב-j "נפסל"); אחרת מזיזים את i ימינה. כש-i=ji=j מוחזר `arr[i]`.

מצביע ij`arr[i]``arr[j]``secret(arr[i])``secret(arr[j])`פעולה
06410343<43<4: j = 5
05415343<43<4: j = 4
04424383<83<8: j = 3
0341732לא 3<23<2: i = 1
1361742לא 4<24<2: i = 2
23121762לא 6<26<2: i = 3
33i == j: מוחזר `arr[3]` = 17

תשובה: 17.

סעיף ד

תשובה:

מחזירה את האיבר ברשימה שיש לו הכי מעט מחלקים (אם יש כמה כאלה – הימני ביותר מביניהם).

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

1. אם לאיבר שב-i יש פחות מחלקים – פוסלים את האיבר שב-j (`j = j - 1`).

2. אחרת (לאיבר שב-j מספר מחלקים קטן או שווה) – פוסלים את האיבר שב-i (`i = i + 1`).

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

בסעיף ג': ל-17 יש 2 מחלקים – הכי מעט ברשימה – והוא מוחזר.

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

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

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

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