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

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

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

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

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

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

מבנה השאלון: מבחן ב-Python

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

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

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

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

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

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

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

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

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

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

שאלה 1 · קליטת מספרים, מכפלת ספרות ומניית אי-זוגיים

כתבו קטע תוכנית שיקלוט 30 מספרים חיוביים ושלמים

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

לדוגמה: עבור מספר 123 יש להדפיס 6 (1\*2\*3).

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

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

פתרון

תשובה:

לולאה של 30 קליטות; למספר בתחום 100–999 מחשבים את מכפלת הספרות בעזרת `% 10` ו-`// 10` ומדפיסים; מונה סופר מספרים שהשארית שלהם בחלוקה ב-2 היא 1, ומודפס בסוף.

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

1. מריצים לולאה בדיוק 30 פעמים, ובכל סיבוב קולטים מספר אחד.

2. מספר חיובי הוא תלת ספרתי אם הוא בין 100 ל-999 (כולל).

3. כדי לחשב את מכפלת הספרות מפרקים את המספר: `temp % 10` נותן את ספרת האחדות, ו-`temp // 10` מוחק אותה. מכפילים את הספרה במשתנה `product` שמתחיל ב-1 (האיבר הניטרלי בכפל), עד שהמספר מתאפס. עובדים על עותק (`temp`) כדי לא להרוס את המספר המקורי.

4. מספר הוא אי-זוגי אם השארית שלו בחלוקה ב-2 היא 1. מונה `odd_count` גדל ב-1 בכל פעם כזו, וההדפסה שלו נעשית רק אחרי הלולאה, כשכל 30 המספרים כבר נקלטו.

לדוגמה, עבור 123: product=1⋅3=3product=1\cdot3=3, אחר כך 3⋅2=63\cdot2=6, אחר כך 6⋅1=66\cdot1=6, ומודפס 6.

הקוד:

odd_count = 0
for i in range(30):
    num = int(input())
    if 100 <= num <= 999:          # מספר תלת ספרתי
        product = 1
        temp = num
        while temp > 0:
            product *= temp % 10   # מכפילים בספרת האחדות
            temp //= 10            # מוחקים את ספרת האחדות
        print(product)
    if num % 2 == 1:               # מספר אי-זוגי
        odd_count += 1
print("odd numbers:", odd_count)

סיבוכיות: כל מספר מטופל במספר קבוע של פעולות (לכל היותר 3 ספרות), ולכן זמן הריצה הוא O(n)O(n) עבור n=30n=30 מספרים.

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

שאלה 2 · קליטת מחרוזות עד תנאי עצירה ומניות

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

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

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

•כמה מחרוזות מתחילות באות גדולה ('A' עד 'Z').

•כמה מחרוזות לא מסתיימות בספרה ('0'..'9').

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

פתרון

תשובה:

לולאת `while len(s) >= 6`; במחרוזת באורך אי-זוגי מודפס `s[len(s)//2]`; מונה לתו ראשון בין 'A' ל-'Z' ומונה לתו אחרון שאינו בין '0' ל-'9'; שני המונים מודפסים אחרי הלולאה.

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

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

2. במחרוזת באורך אי-זוגי nn התו האמצעי נמצא באינדקס n−12\frac{n-1}{2}, שהוא בדיוק `len(s) // 2`. לדוגמה, ב-"abcdefg" (n=7n=7) האינדקס הוא 3, התו 'd'.

3. מחרוזת מתחילה באות גדולה אם התו הראשון `s[0]` נמצא בין 'A' ל-'Z'.

4. מחרוזת לא מסתיימת בספרה אם התו האחרון `s[-1]` אינו בין '0' ל-'9'.

5. אורך כל מחרוזת שנבדקת הוא לפחות 6, ולכן `s[0]` ו-`s[-1]` תמיד קיימים.

6. את שני המונים מדפיסים אחרי הלולאה.

הקוד:

upper_count = 0       # מחרוזות שמתחילות באות גדולה
not_digit_end = 0     # מחרוזות שלא מסתיימות בספרה
s = input()
while len(s) >= 6:
    if len(s) % 2 == 1:
        print(s[len(s) // 2])          # התו האמצעי
    if 'A' <= s[0] <= 'Z':
        upper_count += 1
    if not ('0' <= s[-1] <= '9'):
        not_digit_end += 1
    s = input()
print("start with capital:", upper_count)
print("not ending with digit:", not_digit_end)

דוגמה: עבור הקלט Hello12, abcdef, XYZabc9, qwertyu, abc יודפסו התווים l, a, r (המחרוזות באורך 7), אחר כך 2 מחרוזות שמתחילות באות גדולה (Hello12, XYZabc9) ו-2 מחרוזות שלא מסתיימות בספרה (abcdef, qwertyu).

תשובה: הקוד שלמעלה – מדפיס את התו האמצעי של כל מחרוזת באורך אי-זוגי, ובסוף את מספר המחרוזות שמתחילות באות גדולה ואת מספר המחרוזות שלא מסתיימות בספרה.

שאלה 3 · רשימה מאורגנת: בדיקה ומילוי אקראי

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

לדוגמה:

הרשימה `arr = [12,3,7,5,15,2,6]` היא רשימה "מאורגנת":

0123456
123751526
א.

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

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

is_arranged(arr)
(6 נקודות)
ב.

כתבו פעולה המקבלת רשימה של מספרים שלמים `arr` ושני פרמטרים נוספים `a` ו-`b`, מטיפוס מספר שלם. הפעולה תמלא רשימה `arr` במספרים אקראיים בין `a` ל-`b` (כולל) עד שהרשימה תהיה "מאורגנת".

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

fill(arr, a, b)

אפשר להניח שברשימה יש לפחות שני ערכים וגם a<b.

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

סעיף א

תשובה:

מחשבים את המינימום במקומות הזוגיים ואת המקסימום במקומות האי-זוגיים, ומחזירים `min_even > max_odd`.

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

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

1. מוצאים את `min_even` – המינימום באינדקסים 0,2,4,…0,2,4,\dots (לולאה בקפיצות של 2 מ-0).

2. מוצאים את `max_odd` – המקסימום באינדקסים 1,3,5,…1,3,5,\dots (לולאה בקפיצות של 2 מ-1).

3. מחזירים `True` אם min_even>max_oddmin\_even>max\_odd, אחרת `False`.

בדוגמה: המקומות הזוגיים מכילים 12,7,15,612,7,15,6 והמינימום הוא 6; המקומות האי-זוגיים מכילים 3,5,23,5,2 והמקסימום הוא 5. מתקיים 6>56>5, ולכן הרשימה מאורגנת.

לפי הנתון ברשימה יש לפחות שני ערכים, ולכן `arr[0]` ו-`arr[1]` קיימים.

הקוד:

def is_arranged(arr):
    min_even = arr[0]
    for i in range(0, len(arr), 2):     # מקומות זוגיים
        if arr[i] < min_even:
            min_even = arr[i]
    max_odd = arr[1]
    for i in range(1, len(arr), 2):     # מקומות אי-זוגיים
        if arr[i] > max_odd:
            max_odd = arr[i]
    return min_even > max_odd

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

תשובה: הפעולה `is_arranged` שלמעלה – מחזירה `True` אם ורק אם המינימום במקומות הזוגיים גדול מהמקסימום במקומות האי-זוגיים.

סעיף ב

תשובה:

לולאה: ממלאים את כל `arr` ב-`random.randint(a, b)` ובודקים עם `is_arranged` מסעיף א; חוזרים עד שהבדיקה מחזירה `True`.

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

1. בכל ניסיון ממלאים מחדש את כל המקומות ברשימה במספרים אקראיים בתחום [a,b][a,b] בעזרת `random.randint(a, b)`. הרשימה משתנה במקום (by reference), ולכן אין צורך להחזיר אותה.

2. אחרי כל מילוי בודקים בעזרת `is_arranged` מסעיף א אם הרשימה מאורגנת. אם לא – מנסים שוב.

3. הלולאה תסתיים: מכיוון ש-a<ba<b, תמיד קיים מילוי מאורגן (למשל bb בכל המקומות הזוגיים ו-aa בכל המקומות האי-זוגיים), ולכן לכל ניסיון יש הסתברות חיובית להצליח.

הקוד:

import random

def fill(arr, a, b):
    done = False
    while not done:
        for i in range(len(arr)):
            arr[i] = random.randint(a, b)
        done = is_arranged(arr)

תשובה: הפעולה `fill` שלמעלה – ממלאת שוב ושוב את הרשימה במספרים אקראיים בין `a` ל-`b` עד ש-`is_arranged(arr)` מחזירה `True`.

שאלה 4 · מחלקת תינוק: עדכון מדידות, ממוצע ו-BMI

המחלקה `Baby` (תינוק) משמשת למעקב התפתחותי של התינוקות המגיעים למרפאה במהלך השנה הראשונה לחייהם.

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

שימו לב: במקרה שתינוק לא הגיע לביקורת בחודש מסוים ערך המדידות יהיה 0 בחודש זה.

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

תכונות המחלקה:

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

רשימת מדידות גובה – `height` – רשימה באורך 12 של מספרים ממשיים, `float`

רשימת מדידות משקל – `weight` – רשימה באורך 12 של מספרים ממשיים, `float`

הערה: אורך הרשימות `height` ו-`weight` הוא 12. ערך במקום אפס שומר מדידות שנעשו בחודש הראשון אחרי לידה, במקום מספר אחד – מדידות שנעשו בחודש השני אחרי לידה וכך הלאה.

לדוגמה:

שתי רשימות מתארות את התפתחות הילד ב-12 חודשים הראשונים:

משקל בקילוגרמים (`weight`):

01234567891011
3.36605.7356.9959.390011.2200013.495014.705

גובה במטרים (`height`):

01234567891011
0.54500.5700.6000.66000.735000.77700.792

המדידה הראשונה הייתה בחודש 1, המדידה האחרונה הייתה בחודש 12

שימו לב: בחודשים 2, 6, 8, 9, 11 לא היו מדידות

א.

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

set_data(int month, double h, double w)
(4 נקודות)
ב.

כתבו פעולה המחזירה את ממוצע המשקל על פי כל המדידות שהתקיימו. כותרת הפעולה:

avg_weight()
(4 נקודות)
ג.

המדד מסת גוף (BMI - BodyMassIndex) משקלל את המשקל עם הגובה. המדד הזה חשוב להערכה אם התפתחות הילד תקינה. חישוב ה-BMI מתבצע לפי הנוסחה הבאה: משקל חלקי גובה בריבוע:

BMI=wh2BMI=\frac{w}{h^2}

כתבו פעולה המחזירה מדד ה-BMI של התינוק על פי המדידה האחרונה שלו. כותרת הפעולה:

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

סעיף א

תשובה:

`self.height[month - 1] = h` ו-`self.weight[month - 1] = w` (חודש 1 נשמר במקום 0).

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

לפי ההערה, חודש 1 נשמר במקום 0, חודש 2 במקום 1, וכן הלאה. לכן המדידה של חודש `month` נשמרת באינדקס `month - 1` בשתי הרשימות. ב-Python הפעולה היא פעולה של המחלקה, ולכן הפרמטר הראשון שלה הוא `self` (הטיפוסים `int`/`double` בכותרת אינם נכתבים ב-Python).

לשלמות מוצג גם בנאי פשוט שמאתחל את שתי הרשימות באפסים (חודש בלי ביקורת = 0):

class Baby:
    def __init__(self, name):
        self.name = name
        self.height = [0.0] * 12      # מקום i = חודש i+1
        self.weight = [0.0] * 12

הפעולה:

    def set_data(self, month, h, w):
        self.height[month - 1] = h
        self.weight[month - 1] = w

לדוגמה, `set_data(12, 0.792, 14.705)` כותבת 0.792 ל-`height[11]` ו-14.705 ל-`weight[11]`.

תשובה: הפעולה מעדכנת את `height[month-1]` ל-`h` ואת `weight[month-1]` ל-`w`.

סעיף ב

תשובה:

סכום המשקלים השונים מ-0 חלקי מספרם; בדוגמה 64.9067≈9.272 kg\frac{64.906}{7}\approx9.272\,\text{kg}.

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

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

הקוד:

    def avg_weight(self):
        total = 0
        count = 0
        for w in self.weight:
            if w != 0:          # רק חודשים שבהם הייתה ביקורת
                total += w
                count += 1
        if count == 0:
            return 0
        return total / count

בדיקה על הדוגמה: יש 7 מדידות (חודשים 1, 3, 4, 5, 7, 10, 12):

total=3.366+5.735+6.995+9.390+11.220+13.495+14.705=64.906total=3.366+5.735+6.995+9.390+11.220+13.495+14.705=64.906

avg=64.9067≈9.272 kgavg=\frac{64.906}{7}\approx9.272\,\text{kg}

תשובה: הפעולה מחזירה את ממוצע המשקלים השונים מאפס; בדוגמה 9.272 kg9.272\,\text{kg}.

סעיף ג

תשובה:

סורקים מהסוף (מקום 11) אחורה עד למדידה הראשונה השונה מ-0 ומחזירים wh2\frac{w}{h^2}; בדוגמה 14.7050.7922≈23.44\frac{14.705}{0.792^2}\approx23.44.

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

המדידה האחרונה היא המקום האחרון ברשימה שבו הערך שונה מ-0 (לא בהכרח מקום 11, כי ייתכן שהתינוק לא הגיע בחודש 12). לכן סורקים את הרשימה מהסוף להתחלה, ובמקום הראשון שבו יש מדידה מחשבים את המדד לפי BMI=wh2BMI=\frac{w}{h^2} ומחזירים אותו. לפי הנתון, בחודש שבו הייתה ביקורת נמדדו גם משקל וגם גובה, ולכן הגובה באותו מקום שונה מ-0 ואין חלוקה באפס. אם אין אף מדידה – מחזירים 0.

הקוד:

    def get_last_Bmi(self):
        for i in range(11, -1, -1):          # מהחודש האחרון אחורה
            if self.weight[i] != 0:
                return self.weight[i] / (self.height[i] ** 2)
        return 0

בדיקה על הדוגמה: המדידה האחרונה היא בחודש 12 (מקום 11): w=14.705w=14.705, h=0.792h=0.792.

BMI=14.7050.7922=14.7050.627264≈23.44BMI=\frac{14.705}{0.792^2}=\frac{14.705}{0.627264}\approx23.44

תשובה: הפעולה מחזירה wh2\frac{w}{h^2} של המדידה האחרונה; בדוגמה BMI≈23.44BMI\approx23.44.

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

נתונות שתי הפעולות `what` ו-`where`:

def what(a, b):
    print(a, b)
    a = a + b
    b = a - b
    a = a - b
    print(a, b)

def where(arr):
    print(arr[0], arr[1])
    arr[0] = arr[0] + arr[1]
    arr[1] = arr[0] - arr[1]
    arr[0] = arr[0] - arr[1]
    print(arr[0], arr[1])
א.

עקבו בעזרת טבלת מעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט:

x=3
y=7
z=[3,7]
what(x, y)
where(z)
print("x,y:",x, y)
print("z:", z[0], z[1])
(6 נקודות)
ב.

הפעולה `where` השתנתה לפעולה הבאה:

def where(arr):
    print(arr[0], arr[1])
    what(arr[0], arr[1])
    print(arr[0], arr[1])

מה יהיה הפלט של קטע קוד מסעיף א' אחרי השינוי?

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

סעיף א

תשובה:

הפלט: `3 7`, `7 3`, `3 7`, `7 3`, `x,y: 3 7`, `z: 7 3` (כל אחד בשורה נפרדת).

רעיון: שתי הפעולות מחליפות בין שני ערכים בלי משתנה עזר: a=a+ba=a+b, אחר כך b=a−bb=a-b (שווה ל-aa המקורי), ואחר כך a=a−ba=a-b (שווה ל-bb המקורי). ההבדל ביניהן הוא מה משתנה מחוץ לפעולה:

•`what` מקבלת מספרים שלמים. ההשמות `a = ...`, `b = ...` משנות רק את המשתנים המקומיים של הפעולה, ולכן `x` ו-`y` של התוכנית לא משתנים.

•`where` מקבלת הפניה לרשימה `z` ומשנה את האיברים שלה (`arr[0] = ...`), ולכן השינוי נראה גם אחרי היציאה מהפעולה.

טבלת מעקב:

שלבxyzabפלט
התחלה37[3, 7]
כניסה ל-`what(3, 7)`37[3, 7]37`3 7`
`a = a + b`37[3, 7]107
`b = a - b`37[3, 7]103
`a = a - b`37[3, 7]73`7 3`
כניסה ל-`where(z)`37[3, 7]`3 7`
`arr[0] = arr[0] + arr[1]`37[10, 7]
`arr[1] = arr[0] - arr[1]`37[10, 3]
`arr[0] = arr[0] - arr[1]`37[7, 3]`7 3`
הדפסות בתוכנית37[7, 3]`x,y: 3 7` ואז `z: 7 3`

הפלט:

3 7
7 3
3 7
7 3
x,y: 3 7
z: 7 3

תשובה: ההחלפה ב-`what` מקומית בלבד (`x,y: 3 7`), וההחלפה ב-`where` משנה את הרשימה עצמה (`z: 7 3`).

סעיף ב

תשובה:

הפלט: `3 7`, `7 3`, `3 7`, `3 7`, `7 3`, `3 7`, `x,y: 3 7`, `z: 3 7` (כל אחד בשורה נפרדת).

רעיון: עכשיו `where` לא משנה את איברי הרשימה בעצמה, אלא מעבירה ל-`what` את הערכים `arr[0]` ו-`arr[1]` (מספרים שלמים). `what` מחליפה רק את המשתנים המקומיים `a`, `b` שלה, ולכן הרשימה `z` נשארת `[3, 7]`.

טבלת מעקב:

שלבxyzabפלט
`what(x, y)` – כניסה37[3, 7]37`3 7`
`what(x, y)` – אחרי ההחלפה37[3, 7]73`7 3`
`where(z)` – הדפסה ראשונה37[3, 7]`3 7`
`what(3, 7)` מתוך `where` – כניסה37[3, 7]37`3 7`
`what(3, 7)` מתוך `where` – אחרי ההחלפה37[3, 7]73`7 3`
`where(z)` – הדפסה אחרונה37[3, 7]`3 7`
הדפסות בתוכנית37[3, 7]`x,y: 3 7` ואז `z: 3 7`

הפלט:

3 7
7 3
3 7
3 7
7 3
3 7
x,y: 3 7
z: 3 7

תשובה: הפעם גם `x`, `y` וגם `z` לא משתנים; השורות האחרונות הן `x,y: 3 7` ו-`z: 3 7`.

שאלה 6 · ניתוח פעולות על מחרוזות: הכלה וזוגות

א.

נתונה הפעולה `secret()` הבאה המקבלת שתי מחרוזות:

def secret(s1, s2):
    if s1 == s2:
        return False
    while len(s1) >0 and len(s2)>0 :
        pos = s2.find(s1[0])
        if pos == -1:
            return False
        s1 = s1[1:]
        s2 = s2[0:pos]+s2[pos+1:]
    return len(s1) == 0
(1)

תנו דוגמה למחרוזת `s2` באורך של שישה תווים שעבורה הפעולה `secret("HELLO!", s2)` תחזיר ערך `True`.

(2)

נתונה הטענה הבאה:

אם זימון הפעולה `secret(s1, s2)` מחזיר ערך `True`, גם זימון הפעולה `secret(s2, s1)` יחזיר ערך `True`.

האם הטענה נכונה? הסבירו את תשובתכם.

(3)

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

(6 נקודות)
ב.

נתונה הפעולה `mystery` המקבלת רשימה מחרוזות. הפעולה משתמשת בפעולה `secret`:

def mystery(arr):
    for i in range(0, len(arr)-1, 2):
        if not secret(arr[i], arr[i+1]):
           return False
    return True
(1)

תנו דוגמה לרשימה `arr` של שש מחרוזות שעבורה הפעולה `mystery` תחזיר ערך `true`.

(2)

נתונה הטענה הבאה:

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

(3)

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

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

סעיף א

(1)
תשובה:

למשל `s2 = "!HELLO"` (כל סידור אחר של התווים H, E, L, L, O, ! ששונה מ-"HELLO!").

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

ל-"HELLO!" יש 6 תווים: H, E, L, L, O, !. כדי שכולם יימצאו ב-`s2` שאורכה 6, `s2` חייבת להכיל בדיוק את אותם תווים, כלומר להיות סידור מחדש שלהם – אבל לא בדיוק "HELLO!" (אחרת מוחזר `False` בשורה הראשונה).

מעקב עבור `s2 = "!HELLO"`:

סיבובs1s2pos
1HELLO!!HELLO1
2ELLO!!ELLO1
3LLO!!LLO1
4LO!!LO1
5O!!O1
6!!0
סוף(ריקה)(ריקה)

`s1` התרוקנה, ולכן מוחזר `True`.

תשובה: `s2 = "!HELLO"`.

(2)
תשובה:

לא נכונה. דוגמה נגדית: `secret("AB", "ABC")` מחזיר `True`, אבל `secret("ABC", "AB")` מחזיר `False`.

ההסבר: `secret(s1, s2)` מחזירה `True` כשכל התווים של `s1` (עם החזרות) נמצאים ב-`s2` – אבל `s2` יכולה להכיל תווים נוספים. בכיוון ההפוך התווים הנוספים האלה לא יימצאו ב-`s1`, והפעולה תחזיר `False`.

דוגמה נגדית: `s1 = "AB"`, `s2 = "ABC"`.

1. `secret("AB", "ABC")`: 'A' נמצא (pos=0), נשאר `s1="B"`, `s2="BC"`; 'B' נמצא (pos=0), נשאר `s1=""` – מוחזר `True`.

2. `secret("ABC", "AB")`: 'A' ו-'B' נמחקים, נשאר `s1="C"`, `s2=""`; הלולאה נעצרת כי `s2` ריקה, ו-`len(s1)` הוא 1 – מוחזר `False`.

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

תשובה: הטענה אינה נכונה (דוגמה נגדית: "AB" ו-"ABC").

(3)
תשובה:

מחזירה `True` אם כל תווי `s1` (כולל מספר החזרות של כל תו) מופיעים ב-`s2` והמחרוזות אינן זהות; אחרת `False`.

ההסבר:

1. אם המחרוזות זהות – מוחזר `False`.

2. אחרת, כל תו של `s1` "מתאים" למופע אחד שלו ב-`s2`, והמופע הזה נמחק מ-`s2` כדי שלא ישמש פעמיים. לכן תו שמופיע ב-`s1` פעמיים חייב להופיע ב-`s2` לפחות פעמיים.

3. אם תו כלשהו של `s1` לא נמצא – מוחזר `False`. אם כל התווים של `s1` נמצאו – `s1` מתרוקנת ומוחזר `True`.

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

תשובה: `secret` מחזירה `True` אם ורק אם `s1 != s2` וכל תווי `s1`, עם החזרות, מוכלים בתווי `s2`.

סעיף ב

(1)
תשובה:

למשל `["AB", "BA", "CAT", "ACT", "X", "XY"]`.

ההסבר: הלולאה עוברת על i=0,2,4i=0,2,4 (עבור 6 מחרוזות `range(0, 5, 2)`), כלומר בודקת את הזוגות (0,1), (2,3), (4,5). כדי שיוחזר `True`, בכל זוג `secret(arr[i], arr[i+1])` צריכה להחזיר `True`: המחרוזות בזוג שונות, וכל תווי הראשונה מוכלים בשנייה.

הדוגמה `["AB", "BA", "CAT", "ACT", "X", "XY"]`:

1. `secret("AB", "BA")` – אותם תווים, מחרוזות שונות: `True`.

2. `secret("CAT", "ACT")` – אותם תווים, מחרוזות שונות: `True`.

3. `secret("X", "XY")` – 'X' מוכל ב-"XY": `True`.

שלושת הזוגות עוברים, ולכן `mystery` מחזירה `True`.

תשובה: `arr = ["AB", "BA", "CAT", "ACT", "X", "XY"]`.

(2)
תשובה:

לא נכונה. למשל `["AB", "BA", "BA", "AB"]`: `mystery` מחזירה `True`, אבל במקומות 1 ו-2 יש שתי מחרוזות זהות.

ההסבר: `mystery` לא בודקת כל שני מקומות עוקבים, אלא רק את הזוגות (0,1), (2,3), (4,5), ... – הלולאה מתקדמת בקפיצות של 2. בתוך זוג כזה אכן אי אפשר שיהיו מחרוזות זהות (`secret` מחזירה `False` למחרוזות זהות). אבל זוגות עוקבים "בין זוגות", כמו מקומות 1 ו-2, לא נבדקים כלל.

דוגמה נגדית: `arr = ["AB", "BA", "BA", "AB"]`

1. i=0i=0: `secret("AB", "BA")` – `True`.

2. i=2i=2: `secret("BA", "AB")` – `True`.

3. מוחזר `True`, אף על פי ש-`arr[1]` ו-`arr[2]` הן שתיהן "BA" – מחרוזות זהות במקומות עוקבים.

תשובה: הטענה אינה נכונה – רק המקומות (i,i+1)(i,i+1) עבור ii זוגי נבדקים.

(3)
תשובה:

O(n⋅m2)O(n\cdot m^2), כאשר nn מספר המחרוזות ו-mm האורך המרבי של מחרוזת; אם אורך המחרוזות חסום בקבוע – O(n)O(n).

ההסבר: נסמן ב-nn את מספר המחרוזות ברשימה וב-mm את האורך המרבי של מחרוזת.

1. `mystery` מבצעת לכל היותר n2\frac{n}{2} קריאות ל-`secret` (פעם אחת לכל זוג), כלומר O(n)O(n) קריאות.

2. בכל קריאה ל-`secret` הלולאה רצה לכל היותר mm סיבובים (בכל סיבוב נמחק תו מ-`s1`). בכל סיבוב יש חיפוש `find` ב-`s2` וגם יצירת מחרוזות חדשות בחיתוך (`s1[1:]` ו-`s2[0:pos]+s2[pos+1:]`) – כל אחת מהפעולות האלה עולה O(m)O(m). לכן קריאה אחת ל-`secret` עולה O(m⋅m)=O(m2)O(m\cdot m)=O(m^2).

3. בסך הכול: O(n)⋅O(m2)=O(n⋅m2)O(n)\cdot O(m^2)=O(n\cdot m^2).

אם מתייחסים לאורך המחרוזות כקבוע (מחרוזות קצרות), הסיבוכיות היא O(n)O(n) – לינארית במספר המחרוזות.

תשובה: O(n⋅m2)O(n\cdot m^2); עבור מחרוזות באורך חסום – O(n)O(n).

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

נתונה המחלקה `Book` שיש לה שלוש תכונות:

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

•שנת הוצאה – `year`, מטיפוס שלם, `int`

•האם כתוב בעברית – `isHebrew`, מטיפוס בוליאני, `bool`

במחלקה הוגדרה פעולה הבונה (בנאי, `constructor`)

def __init__(self, code, year, is_hebrew):
    self.code = code
    self.year = year
    self.is_hebrew = is_hebrew
א.

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

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

old_book(self, year1)
(4 נקודות)
ב.

עקבו בעזרת טבלת המעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט.

b1 = Book(1122, 1998, False)
b2 = Book(2233, 2010, True)
#  (*) כאן יש להוסיף פקודה/פקודות בסעיף ג'
if b1.old_book(2014) and not b1.is_hebrew:
    print("###")
else:
    print("***")
if b2.old_book(2015):
    print("!!!")
else:
    if b2.is_hebrew:
        print("???")
(4 נקודות)
ג.

נא השלימו קוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה `*` בלבד.

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

סעיף א

תשובה:

`return year1 - self.year >= 10` (מספר השנים משנת ההוצאה עד `year1` כולל, year1−year+1year1-year+1, גדול מ-10).

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

סופרים את השנים משנת ההוצאה `self.year` עד השנה `year1` כולל שתיהן: מספרן הוא year1−year+1year1-year+1. הספר "ישן" אם מספר זה גדול מ-10:

year1−year+1>10  ⟺  year1−year≥10year1-year+1>10\iff year1-year\ge10

לדוגמה, ספר משנת 2000: עבור year1=2010year1=2010 נספרות השנים 2000 עד 2010, כלומר 2010−2000+1=11>102010-2000+1=11>10 – מוחזר `True`; עבור year1=2009year1=2009 נספרות 1010 שנים בלבד – מוחזר `False`.

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

    def old_book(self, year1):
        return year1 - self.year >= 10

תשובה: הפעולה מחזירה `True` אם year1−year+1>10year1-year+1>10, כלומר אם year1−year≥10year1-year\ge10, ואחרת `False`.

סעיף ב

תשובה:

הפלט: `###` ואחריו `???`.

טבלת מעקב:

שורהביטויערךפלט
יצירת `b1`year=1998, is_hebrew=False
יצירת `b2`year=2010, is_hebrew=True
תנאי ראשון`b1.old_book(2014)`: 2014−1998=16≥102014-1998=16\ge10True
`not b1.is_hebrew`True
`True and True`True`###`
תנאי שני`b2.old_book(2015)`: 2015−2010=5<102015-2010=5<10False
`else``b2.is_hebrew`True`???`

1. הספר `b1` יצא ב-1998, ועד 2014 עברו 16 שנים – הוא ישן. הוא לא בעברית, ולכן התנאי כולו מתקיים ומודפס `###`.

2. הספר `b2` יצא ב-2010, ועד 2015 עברו 5 שנים – הוא לא ישן, ולכן עוברים ל-`else`. הוא בעברית, ולכן מודפס `???`.

(התוצאה אינה תלויה בפרשנות של "כולל" בסעיף א: 16 שנים בבירור יותר מעשר, ו-5 או 6 שנים בבירור לא.)

הפלט:

###
???

תשובה: `###` ואחריו `???`.

סעיף ג

תשובה:

למשל: `b1.is_hebrew = True` ו-`b2.is_hebrew = False`.

מה צריך לקרות:

1. כדי שיודפס `*`, התנאי הראשון צריך להיות שקרי. הדרך הפשוטה: להפוך את `b1` לספר בעברית, ואז `not b1.is_hebrew` שקרי וכל ה-`and` שקרי.

2. כדי שלא יודפס דבר בחלק השני, צריך גם ש-`b2.old_book(2015)` יהיה שקרי (כך הוא כבר: 5 שנים בלבד), וגם ש-`b2.is_hebrew` יהיה שקרי, כדי שלא יודפס `???`. לכן הופכים את `b2` לספר שאינו בעברית.

הפקודות שמוסיפים במקום (*):

b1.is_hebrew = True
b2.is_hebrew = False

מעקב אחרי ההוספה:

•`b1.old_book(2014)` הוא `True`, אבל `not b1.is_hebrew` הוא `False`, ולכן מודפס `*`.

•`b2.old_book(2015)` הוא `False`; ב-`else` הערך `b2.is_hebrew` הוא `False`, ולכן לא מודפס דבר.

הפלט הוא `*` בלבד.

תשובה: `b1.is_hebrew = True` ו-`b2.is_hebrew = False`.

שאלה 8 · מספרים אחים: מספר ספרות וסכום ספרות

א.

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

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

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

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

is_it_brothers(num1, num2)
(5 נקודות)
ב.

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

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

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

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

is_it_brothers(arr)
(6 נקודות)
ג.

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

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

סעיף א

תשובה:

מחשבים לכל מספר את מספר הספרות ואת סכום הספרות (בעזרת `% 10` ו-`// 10`) ומחזירים `True` אם שני הנתונים שווים.

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

1. פעולת עזר `count_digits` סופרת ספרות: כל עוד המספר חיובי, מוחקים ממנו ספרה (`num //= 10`) ומגדילים מונה.

2. פעולת עזר `sum_digits` סוכמת ספרות: מוסיפים לסכום את ספרת האחדות (`num % 10`) ומוחקים אותה.

3. המספרים "אחים" אם מספר הספרות שלהם שווה וגם סכום הספרות שלהם שווה.

לדוגמה: 123 ו-321 – לשניהם 3 ספרות וסכום ספרות 6, ולכן הם אחים. 123 ו-60 – סכום ספרות 6 לשניהם, אבל מספר הספרות שונה (3 מול 2), ולכן הם לא אחים.

הקוד:

def count_digits(num):          # מספר הספרות
    count = 0
    while num > 0:
        count += 1
        num //= 10
    return count

def sum_digits(num):            # סכום הספרות
    total = 0
    while num > 0:
        total += num % 10
        num //= 10
    return total
def is_it_brothers(num1, num2):
    return (count_digits(num1) == count_digits(num2) and
            sum_digits(num1) == sum_digits(num2))

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

סעיף ב

תשובה:

משווים כל איבר לאיבר הראשון: אם לכולם אותו מספר ספרות ואותו סכום ספרות כמו `arr[0]` מוחזר `True`, אחרת `False`.

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

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

1. מחשבים פעם אחת את מספר הספרות וסכום הספרות של `arr[0]`.

2. עוברים על כל האיברים; אם לאחד מהם מאפיין שונה – מחזירים `False` מיד.

3. אם הלולאה הסתיימה – מחזירים `True`. רשימה ריקה או רשימה עם איבר אחד היא "רשימת אחים" (אין זוג שמפר את התנאי).

ב-Python אין העמסה של פעולות: אם שתי פעולות באותו קובץ נקראות `is_it_brothers`, ההגדרה השנייה מחליפה את הראשונה. לכן הפעולה כאן לא קוראת לפעולה מסעיף א, אלא משתמשת ישירות בפעולות העזר `count_digits` ו-`sum_digits` מסעיף א.

הקוד:

def is_it_brothers(arr):
    if len(arr) == 0:
        return True
    digits = count_digits(arr[0])
    total = sum_digits(arr[0])
    for num in arr:
        if count_digits(num) != digits or sum_digits(num) != total:
            return False
    return True

לדוגמה: `[123, 321, 222, 600, 141]` – לכולם 3 ספרות וסכום ספרות 6, מוחזר `True`. `[123, 321, 33]` – ל-33 יש 2 ספרות, מוחזר `False`.

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

סעיף ג

תשובה:

סעיף א: O(d)O(d), כאשר dd מספר הספרות (כלומר O(log⁡num)O(\log num)). סעיף ב: O(n⋅d)O(n\cdot d), ובמספרים בגודל חסום – O(n)O(n).

נסמן ב-dd את מספר הספרות המרבי של מספר (עבור מספר numnum מתקיים d≈log⁡10numd\approx\log_{10}num), וב-nn את מספר האיברים ברשימה.

1. סעיף א: `count_digits` ו-`sum_digits` מבצעות סיבוב אחד לכל ספרה, כלומר O(d)O(d) כל אחת. `is_it_brothers(num1, num2)` קוראת לכל אחת מהן פעמיים, ולכן הסיבוכיות היא 4⋅O(d)=O(d)=O(log⁡num)4\cdot O(d)=O(d)=O(\log num).

2. סעיף ב: הלולאה עוברת פעם אחת על nn האיברים, ולכל איבר מחשבים מספר ספרות וסכום ספרות ב-O(d)O(d). לכן הסיבוכיות היא O(n⋅d)O(n\cdot d). מכיוון שמשווים רק לאיבר הראשון (ולא כל זוג לכל זוג, שהיה עולה O(n2⋅d)O(n^2\cdot d)), הפעולה לינארית במספר האיברים. כשגודל המספרים חסום (מספר ספרות קבוע), הסיבוכיות היא O(n)O(n).

תשובה: סעיף א – O(d)O(d) (קבוע עבור מספרים בגודל חסום); סעיף ב – O(n⋅d)O(n\cdot d), כלומר O(n)O(n).

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

א.

המחלקה `Date` מייצגת תאריך. תכונות המחלקה:

•`day` – מייצגת את היום (שלמים בין 1 ל-31)

•`month` – מייצגת את החודש (שלמים בין 1 ל-12)

•`year` – מייצגת את השנה (שלמים חיוביים בני ארבע ספרות)

class Date:
    def __init__(self, day, month, year):
        self.day = day
        self.month = month
        self.year = year

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

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

after(self, other)
(3 נקודות)
ב.

המחלקה `Worker` מייצגת עובד בחברה. למחלקה שתי תכונות:

•`name` – שם העובד, מטיפוס מחרוזת, `str`

•`birthday` – יום הולדת, מטיפוס `Date`

כתבו פעולה בונה

__init__(self, name, day, month, year)
(2 נקודות)
ג.

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

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

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

print_by_month(arr, month)
(5 נקודות)
ד.

כתבו פעולה המקבלת רשימת עובדי החברה ומחזירה שם העובד הצעיר ביותר.

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

youngest(arr)

אפשר להניח שקיים רק עובד אחד שהוא צעיר ביותר

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

סעיף א

תשובה:

משווים קודם את השנה, אם שוות – את החודש, ואם גם הם שווים – את היום; מוחזר `True` רק אם `self` גדול ב"רכיב הראשון שבו יש הבדל".

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

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

1. אם השנים שונות – התאריך מאוחר יותר אם השנה שלו גדולה יותר (החודש והיום כבר לא משנים).

2. אם השנים שוות והחודשים שונים – מכריע החודש.

3. אם גם החודשים שווים – מכריע היום. אם גם הימים שווים, התאריכים זהים, והתאריך הנוכחי אינו מאוחר יותר, ולכן מוחזר `False` (כי `>` ולא `>=`).

לדוגמה: 5/3/2000 מאוחר מ-28/12/1999 (השנה מכריעה), ו-1/4/2000 מאוחר מ-30/3/2000 (החודש מכריע).

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

    def after(self, other):
        if self.year != other.year:
            return self.year > other.year
        if self.month != other.month:
            return self.month > other.month
        return self.day > other.day

תשובה: הפעולה `after` שלמעלה – משווה שנה, אחר כך חודש, אחר כך יום, ומחזירה `True` אם התאריך הנוכחי מאוחר מ-`other`.

סעיף ב

תשובה:

`self.name = name` ו-`self.birthday = Date(day, month, year)`.

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

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

הקוד:

class Worker:
    def __init__(self, name, day, month, year):
        self.name = name
        self.birthday = Date(day, month, year)

תשובה: הבנאי שומר את השם ויוצר `Date(day, month, year)` לתכונה `birthday`.

סעיף ג

תשובה:

עוברים על כל העובדים ומדפיסים את `w.name` של כל עובד שמתקיים אצלו `w.birthday.month == month`.

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

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

הקוד:

def print_by_month(arr, month):
    for w in arr:
        if w.birthday.month == month:
            print(w.name)

לדוגמה, עבור העובדים Dan (5/3/1990), Rina (17/8/1995), Avi (30/3/1995) והחודש 3 יודפסו Dan ו-Avi.

סיבוכיות: O(n)O(n) עבור nn עובדים.

תשובה: הפעולה מדפיסה את שמות כל העובדים שחודש יום ההולדת שלהם שווה ל-`month`.

סעיף ד

תשובה:

מחפשים מקסימום לפי תאריך הלידה: העובד הצעיר ביותר הוא זה שתאריך הלידה שלו המאוחר ביותר (בעזרת `after` מסעיף א), ומחזירים את שמו.

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

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

1. מניחים שהעובד הראשון הוא הצעיר ביותר.

2. עוברים על כל העובדים; אם תאריך הלידה של עובד מאוחר מתאריך הלידה של הצעיר הנוכחי – הוא הופך לצעיר הנוכחי.

3. בסוף מחזירים את השם של הצעיר ביותר (לא את העצם).

הקוד:

def youngest(arr):
    young = arr[0]
    for w in arr:
        if w.birthday.after(young.birthday):
            young = w
    return young.name

לדוגמה, עבור Dan (5/3/1990), Rina (17/8/1995), Avi (30/3/1995), Noa (2/8/1995) מוחזר "Rina": היא נולדה ב-1995 כמו Avi ו-Noa, באוגוסט כמו Noa, וב-17 לחודש – אחרי ה-2.

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

תשובה: הפעולה מחזירה את שם העובד שתאריך הלידה שלו מאוחר מכולם.

שאלה 10 · חיפוש מאינדקס ובדיקת תת-סדרה

א.

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

def why(a, x, k):
    for i in range(k, len(a)):
        if a[i] == x:
            return i
    return -1
(1)

תנו דוגמה של רשימת מספרים שלמים `arr` שעבורו זימון הפעולה `why(arr, 5, 3)` יחזיר ערך 5 וזימון הפעולה `why(arr, 3, 5)` יחזיר ערך (-1).

(2)

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

(5 נקודות)
ב.

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

def where(a, b):
    k = -1
    for i in range(0, len(b)):
        k = why(a, b[i], k+1)
        if k == -1:
            return False
    return True

נתונות שתי הרשימות הבאות:

a = [2,4,9,0,2,3]
b = [2,4,0,9,3]

מהי תוצאת הזימון `where(a, b)`?

יש להראות מעקב אחרי ביצוע הפעולה. אין צורך במעקב אחרי הפעולה why.

(5 נקודות)
ג.

נתונה הפעולה `what` הבאה

def what(a, b):
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            i += 1
            j += 1
        else:
            i += 1
    return j == len(b)

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

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

סעיף א

(1)
תשובה:

למשל `arr = [1, 2, 3, 4, 6, 5]`.

הבנת הפעולה: `why(a, x, k)` מחפשת את הערך `x` ברשימה, החל מהאינדקס `k` והלאה, ומחזירה את האינדקס של המופע הראשון שלו; אם אין מופע כזה – מוחזר −1-1.

מה נדרש:

1. `why(arr, 5, 3)` מחזירה 5: החיפוש מתחיל באינדקס 3, ולכן `arr[3]` ו-`arr[4]` אינם 5, ו-`arr[5]` הוא 5.

2. `why(arr, 3, 5)` מחזירה −1-1: אין 3 באינדקסים 5 והלאה. (מותר שיהיה 3 לפני אינדקס 5.)

הדוגמה `arr = [1, 2, 3, 4, 6, 5]`:

•`why(arr, 5, 3)`: בודקים `arr[3]=4`, `arr[4]=6`, `arr[5]=5` – מוחזר 5.

•`why(arr, 3, 5)`: בודקים רק את `arr[5]=5`, שאינו 3 – מוחזר −1-1 (ה-3 שבאינדקס 2 לא נבדק).

תשובה: `arr = [1, 2, 3, 4, 6, 5]`.

(2)
תשובה:

מחזירה את האינדקס הראשון i≥ki\ge k שבו `a[i] == x`, ואם אין כזה – −1-1.

ההסבר: הלולאה עוברת על האינדקסים מ-`k` עד סוף הרשימה לפי הסדר. ברגע שנמצא איבר ששווה ל-`x`, מוחזר האינדקס שלו (ולכן זה המופע הראשון מ-`k` והלאה). אם הלולאה הסתיימה בלי למצוא, מוחזר −1-1. אם k≥k\ge `len(a)` הלולאה לא רצה כלל ומוחזר −1-1.

תשובה: `why` מחפשת את `x` ברשימה `a` החל מהמקום `k`, ומחזירה את מקום המופע הראשון שלו (או −1-1 אם הוא לא מופיע מ-`k` והלאה).

סעיף ב

תשובה:

`False` (האיבר 9 של `b` לא נמצא ב-`a` אחרי המקום 3).

רעיון: `where` מחפשת את איברי `b` ב-`a` לפי הסדר: כל איבר מחפשים רק אחרי המקום שבו נמצא האיבר הקודם (`k+1`). אם איבר לא נמצא – מוחזר `False`.

טבלת מעקב (`a = [2,4,9,0,2,3]`, `b = [2,4,0,9,3]`):

ib[i]חיפוש מהמקום k+1k (תוצאת why)k == -1?
התחלה-1
0200לא
1411לא
2023לא
394-1כן – מוחזר False

בשלב i=3i=3 מחפשים את 9 באינדקסים 4 ו-5 של `a` (הערכים 2 ו-3), ואין שם 9. ה-9 שב-`a` נמצא במקום 2, לפני ה-0 שנמצא במקום 3 – כלומר הסדר ב-`a` שונה מהסדר ב-`b`.

תשובה: `where(a, b)` מחזירה `False`.

סעיף ג

תשובה:

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

מה מבצעת `where`: היא מוצאת את `b[0]` ב-`a`, אחר כך את `b[1]` אחרי המקום שנמצא, וכן הלאה. היא מחזירה `True` אם כל איברי `b` נמצאו ב-`a` באותו סדר, כלומר אם `b` היא תת-סדרה של `a` (האיברים לא חייבים להיות צמודים).

מה מבצעת `what`: `i` רץ על `a` ו-`j` מצביע על האיבר הבא של `b` שעדיין לא נמצא. בכל צעד `i` מתקדם; אם `a[i]` שווה ל-`b[j]`, נמצא האיבר `b[j]` ו-`j` מתקדם לאיבר הבא של `b`. בסוף מוחזר `True` אם `j` הגיע לסוף `b`, כלומר כל איברי `b` נמצאו לפי הסדר.

למה הן שקולות: שתיהן משתמשות באותה שיטה "חמדנית": כל איבר של `b` מותאם למופע הראשון שלו ב-`a` אחרי המקום של האיבר הקודם. ב-`where` זה נעשה בקריאה `why(a, b[i], k+1)`, וב-`what` זה נעשה בהתקדמות של `i` עד שנמצא `a[i] == b[j]`. בחירה במופע המוקדם ביותר משאירה את מירב המקום לאיברים הבאים, ולכן שתי הפעולות מחזירות `True` בדיוק כש-`b` היא תת-סדרה של `a`. גם המקרים הקיצוניים זהים: אם `b` ריקה שתיהן מחזירות `True`, ואם `b` לא ריקה ו-`a` ריקה שתיהן מחזירות `False`.

לדוגמה, עבור הרשימות מסעיף ב: `what` מוצאת את 2 (מקום 0), 4 (מקום 1), 0 (מקום 3), ואז מחפשת 9 במקומות 4–5, לא מוצאת, `i` מגיע לסוף ו-j=3≠5j=3\ne5 – מוחזר `False`, כמו ב-`where`.

תשובה: כן, `what` שקולה ל-`where`; שתיהן בודקות אם `b` היא תת-סדרה של `a` (איברי `b` מופיעים ב-`a` באותו סדר).

שאלה 11 · לוח שנה 2024: מספר ימים ויום בשבוע

נתונה המחלקה `Calendar2024` המתארת לוח שנה 2024.

למחלקה תכונה אחת `days` שהיא רשימת מספרים שלמים בגודל 12 אשר כל אחד מציין מספר הימים בחודש המתאים למיקומו ברשימה.

•איבר במקום 0 (הראשון ברשימה) יהיה 31 כי בחודש ינואר (החודש הראשון בשנה) יש 31 ימים.

•איבר במקום 1 (השני ברשימה) יהיה רשום 29 כי בחודש פברואר (החודש השני בשנה) יש 29 ימים.

•איבר במקום 2 (השלישי ברשימה ) יהיה רשום 31 כי בחודש מארס יש 31 ימים וכו'.

מספר האיבר ברשימה01234567891011
מספר הימים בחודש312931303130313130313031
א.

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

הפעולה תחשב ותחזיר את מספר הימים שעברו מתחילת השנה (1 בינואר) ועד התאריך שהתקבל.

לדוגמה:

עבור התאריך: 22,1 (22/1) יוחזר המספר: 21

עבור התאריך: 22,3 (22/3) יוחזר המספר: 81 (31+29+21)

עבור התאריך: 1,5 (1/5) יוחזר המספר: 121 (31+29+31+30)

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

num_of_days(self, day, month)
(5 נקודות)
ב.

יום 1/1 (היום הראשון של השנה) חל בשנה 2024 על יום ב' (יום שני, יום מספר 2 בשבוע).

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

לדוגמה:

עבור יום 1/1 יש להחזיר 2

עבור יום 8/1 יש להחזיר 2

עבור יום 1/2 יש להחזיר 5

עבור יום 22/3 יש להחזיר 6

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

weekday(self, day, month)

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

(5 נקודות)
ג.

כתבו במחלקה `Calendar2024` פעולה המדפיסה יום בשבוע עבור כל יום ראשון וכל יום אחרון של 12 חודשי השנה 2024.

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

print_first_last(self)

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

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

סעיף א

תשובה:

סכום הימים בחודשים 1,…,month−11,\dots,month-1 ועוד day−1day-1; למשל 22/3 נותן 31+29+21=8131+29+21=81.

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

מהדוגמאות רואים שסופרים את הימים שעברו מ-1 בינואר, כלומר ההפרש בין התאריכים: עבור 1/1 מוחזר 0, ועבור 22/1 מוחזר 22−1=2122-1=21.

1. כל החודשים שלפני החודש `month` עברו במלואם: אלה האיברים במקומות 0,…,month−20,\dots,month-2 ברשימה `days`, ולכן סוכמים `days[i]` עבור `i` ב-`range(month - 1)`.

2. בחודש `month` עצמו עברו day−1day-1 ימים.

3. התוצאה: הסכום ועוד day−1day-1.

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

- 22/1: אין חודשים קודמים, 0+22−1=210+22-1=21.

- 22/3: 31+29+(22−1)=8131+29+(22-1)=81.

- 1/5: 31+29+31+30+(1−1)=12131+29+31+30+(1-1)=121.

הקוד:

class Calendar2024:
    def __init__(self):
        self.days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    def num_of_days(self, day, month):
        total = 0
        for i in range(month - 1):        # החודשים שעברו במלואם
            total += self.days[i]
        return total + day - 1

תשובה: `num_of_days` מחזירה את סכום הימים בחודשים שלפני `month` ועוד day−1day-1 (בדוגמאות: 21, 81, 121).

סעיף ב

תשובה:

`return (self.num_of_days(day, month) + 1) % 7 + 1` (יום ראשון = 1, ..., שבת = 7).

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

ימי השבוע חוזרים כל 7 ימים. מספרי הימים הם 1 (ראשון) עד 7 (שבת), ו-1/1/2024 הוא יום 2.

1. נסמן nn = `num_of_days(day, month)` – מספר הימים שעברו מ-1/1. אחרי nn ימים מתקדמים nn צעדים במחזור של 7.

2. נעבור לספירה מ-0: יום 2 הוא "1" (ראשון = 0, שני = 1, ...). אחרי nn ימים הערך הוא (n+1) mod 7(n+1)\bmod 7.

3. נחזור לספירה מ-1 על ידי הוספת 1: weekday=(n+1) mod 7+1weekday=(n+1)\bmod7+1.

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

- 1/1: n=0n=0, (0+1) mod 7+1=2(0+1)\bmod7+1=2.

- 8/1: n=7n=7, 8 mod 7+1=1+1=28\bmod7+1=1+1=2.

- 1/2: n=31n=31, 32 mod 7+1=4+1=532\bmod7+1=4+1=5.

- 22/3: n=81n=81, 82 mod 7+1=5+1=682\bmod7+1=5+1=6.

כל התוצאות מתאימות לדוגמאות.

הקוד:

    def weekday(self, day, month):
        return (self.num_of_days(day, month) + 1) % 7 + 1

תשובה: `weekday` מחזירה (n+1) mod 7+1(n+1)\bmod7+1, כאשר nn הוא מספר הימים מסעיף א (בדוגמאות: 2, 2, 5, 6).

סעיף ג

תשובה:

לולאה על החודשים 1–12: מדפיסים את `weekday(1, m)` ואת `weekday(self.days[m-1], m)`.

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

לכל חודש mm מ-1 עד 12:

1. היום הראשון בחודש הוא 1, והיום בשבוע שלו הוא `weekday(1, m)`.

2. היום האחרון בחודש הוא מספר הימים בחודש, `self.days[m - 1]` (חודש mm שמור במקום m−1m-1), והיום בשבוע שלו הוא `weekday(self.days[m - 1], m)`.

3. מדפיסים בשורה אחת את מספר החודש ואת שני הימים בשבוע.

הקוד:

    def print_first_last(self):
        for m in range(1, 13):
            first = self.weekday(1, m)
            last = self.weekday(self.days[m - 1], m)
            print(m, first, last)

הפלט שמתקבל (חודש, יום בשבוע של היום הראשון, יום בשבוע של היום האחרון):

חודשיום ראשון בחודשיום אחרון בחודש
124
255
361
423
546
671
724
857
912
1035
1167
1213

לדוגמה, 31/1: n=30n=30, (30+1) mod 7+1=3+1=4(30+1)\bmod7+1=3+1=4 (יום רביעי); 1/2: n=31n=31, יום 5 (חמישי), כלומר היום שאחרי – כצפוי.

תשובה: `print_first_last` מדפיסה לכל חודש את `weekday(1, m)` ואת `weekday(days[m-1], m)` (למשל ינואר: 2 ו-4).

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

מערכת מחשוב של בנק "SimpleBank" כוללת שתי מחלקות הבאות: `Account` ו-`Branch`.

למחלקה `Account` (חשבון) ארבע תכונות:

•מספר חשבון – `num`, מטיפוס מספר שלם, `int`

•מספר תעודת הזהות של הלקוח – `id_num`, מטיפוס מחרוזת, `str`

•היתרה בחשבון – `balance`, מטיפוס מספר ממשי, `float`

•מצב החשבון – `is_active`, מטיפוס `bool` (`True` – חשבון פעיל, ו-`False` – חשבון לא פעיל)

בעת פתיחת חשבון, הלקוח מקבל מתנה 100 ₪ ליתרת חשבון.

למחלקה `Branch` (סניף) תכונות הבאות:

•מספר סניף – `branch_num`, מטיפוס שלם, `int`

•רשימת חשבונות – `accounts` – רשימה הפניות לעצמים מסוג `Account`

•מספר החשבונות המקסימלי שאותם הסניף רשאי לפתוח – `max_accounts`, מטיפוס מספר שלם, `int`

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

א.

כתבו במחלקות `Account` ו-`Branch` פעולות בונות (`constructors`).

במחלקה `Account`:

__init__(self, num, id_num)

במחלקה `Branch`:

__init__(self, branch_num, max_accounts)

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

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

generate_num(self)
(2 נקודות)
ב.

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

כתבו במחלקה `Branch` פעולה להוספת חשבון חדש:

add_account(self, id_num)

הפעולה תחזיר ערך True אם הוספה הצליחה, ולא הפעולה תחזיר ערך False

(4 נקודות)
ג.

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

כתבו פעולה המבצעת מעבר לקוח מסניף לסניף. כותרת הפעולה:

move_client(id_num, other)

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

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

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

סעיף א

תשובה:

`Account`: מספר ות"ז מהפרמטרים, `balance = 100`, `is_active = True`. `Branch`: מספר הסניף והמקסימום מהפרמטרים, `accounts = []`.

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

1. בבנאי של `Account` מקבלים את מספר החשבון ואת מספר תעודת הזהות. היתרה ההתחלתית היא 100 ₪ – המתנה שכל לקוח מקבל בפתיחת חשבון – וחשבון חדש הוא פעיל.

2. בבנאי של `Branch` מקבלים את מספר הסניף ואת המספר המרבי של חשבונות, ורשימת החשבונות מתחילה ריקה (סניף חדש עדיין בלי חשבונות).

הקוד:

class Account:
    def __init__(self, num, id_num):
        self.num = num
        self.id_num = id_num
        self.balance = 100.0        # מתנה בפתיחת חשבון
        self.is_active = True
class Branch:
    def __init__(self, branch_num, max_accounts):
        self.branch_num = branch_num
        self.max_accounts = max_accounts
        self.accounts = []          # סניף חדש – בלי חשבונות

תשובה: שני הבנאים שלמעלה – חשבון חדש נפתח עם יתרה 100 ומצב פעיל, וסניף חדש נפתח עם רשימת חשבונות ריקה.

סעיף ב

תשובה:

אם הסניף מלא (`len(accounts) >= max_accounts`) מוחזר `False`; אחרת יוצרים `Account(self.generate_num(), id_num)`, ואם אין בסניף חשבון עם אותה ת"ז קובעים יתרה 500; מוסיפים לרשימה ומחזירים `True`.

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

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

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

3. יצירת החשבון: מספר החשבון נוצר בפעולה הקיימת `generate_num()`. הבנאי כבר נותן יתרה של 100 ₪ (המתנה הרגילה); ללקוח חדש משנים את היתרה ל-500 ₪.

4. מוסיפים את החשבון לרשימה ומחזירים `True`.

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

    def add_account(self, id_num):
        if len(self.accounts) >= self.max_accounts:
            return False                      # אין מקום בסניף
        is_new = True
        for acc in self.accounts:
            if acc.id_num == id_num:
                is_new = False                # ללקוח כבר יש חשבון
        new_acc = Account(self.generate_num(), id_num)
        if is_new:
            new_acc.balance = 500.0           # מתנה ללקוח חדש
        self.accounts.append(new_acc)
        return True

לדוגמה, בסניף עם `max_accounts = 3`: פתיחה ראשונה ללקוח "111" – יתרה 500; פתיחה שנייה ל-"111" – יתרה 100; פתיחה ל-"222" – יתרה 500; פתיחה רביעית – מוחזר `False`.

תשובה: הפעולה `add_account` שלמעלה – מחזירה `False` כשהסניף מלא, ואחרת פותחת חשבון (500 ₪ ללקוח חדש, 100 ₪ ללקוח קיים) ומחזירה `True`.

סעיף ג

תשובה:

עוברים על חשבונות `other`: לכל חשבון פעיל של הלקוח מוסיפים את היתרה לסכום וקובעים `is_active = False`; אחר כך פותחים ב-`self` חשבון חדש (`generate_num`) שיתרתו בדיוק הסכום (בלי מתנה) ומוסיפים לרשימה.

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

הפעולה שייכת למחלקה `Branch` ומופעלת על הסניף החדש (`self`), כלומר ב-Python הכותרת היא `move_client(self, id_num, other)`.

1. סגירת החשבונות בסניף הקודם: עוברים על `other.accounts`. לכל חשבון פעיל של הלקוח (אותו `id_num`) מוסיפים את היתרה שלו לסכום `total` והופכים אותו ללא פעיל. לא מוחקים את החשבון מהרשימה.

2. אם ללקוח לא היה אף חשבון פעיל ב-`other`, אין מה להעביר, ומחזירים `False`.

3. פתיחת חשבון בסניף החדש: יוצרים חשבון עם מספר מ-`generate_num()`. הבנאי נותן 100 ₪, אבל ללקוח שעובר סניף לא מגיעה מתנה, ולכן דורסים את היתרה בסכום היתרות `total`. לא בודקים מקום, כי לפי הנתון יש מקום בסניף.

4. מוסיפים את החשבון לרשימה של `self` ומחזירים `True` (סימון שהמעבר בוצע).

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

    def move_client(self, id_num, other):
        total = 0
        found = False
        for acc in other.accounts:
            if acc.id_num == id_num and acc.is_active:
                total += acc.balance
                acc.is_active = False         # סגירת החשבון בסניף הקודם
                found = True
        if not found:
            return False
        new_acc = Account(self.generate_num(), id_num)
        new_acc.balance = total               # בלי מתנה
        self.accounts.append(new_acc)
        return True

לדוגמה: ללקוח "111" יש ב-`other` שני חשבונות פעילים עם יתרות 700 ו-100. אחרי `b2.move_client("111", b1)` שני החשבונות ב-`b1` לא פעילים, וב-`b2` נפתח חשבון אחד עם יתרה 700+100=800700+100=800 ₪.

תשובה: הפעולה `move_client` שלמעלה – סוגרת את כל החשבונות הפעילים של הלקוח ב-`other`, סוכמת את יתרותיהם ופותחת ב-`self` חשבון אחד עם הסכום, בלי מתנה.

שאלה 13 · מספר מיוחד, רשימה מיוחדת ורשימת רשימות

נתונות הגדרות הבאות:

•מספר שלם וחיובי נקרא "מספר מיוחד" אם ספרות המספר (משמאל לימין) מהוות סידרה עולה.

לדוגמה:

המספרים 12, 138, 2689, 4 הם "מספרים מיוחדים".

המספרים 43, 176, -123, 33 אינם "מספרים מיוחדים".

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

•רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה) נקראת "סופר מיוחדת" אם כל איבר שלה הוא "רשימה מיוחדת".

א.

כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה של מספרים שלמים) ובודקת אם היא "סופר מיוחדת".

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

(8 נקודות)
ב.

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

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

סעיף א

תשובה:

שלוש פעולות: `is_special_num` (מספר חיובי שספרותיו עולות ממש), `is_special_list` (ממוינת בסדר עולה ויש בה מספר מיוחד), `is_super_special` (כל הרשימות הפנימיות מיוחדות).

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

1. מספר מיוחד – `is_special_num(num)`:

•מספר שאינו חיובי (אפס או שלילי, כמו −123-123) אינו מיוחד.

•הספרות צריכות לעלות משמאל לימין ממש (33 אינו מיוחד, ולכן ספרות שוות אסורות). קל יותר לעבור על הספרות מימין לשמאל (בעזרת `% 10` ו-`// 10`): אז כל ספרה צריכה להיות קטנה ממש מהספרה שמימינה.

•מספר חד-ספרתי (כמו 4) מיוחד – אין בו זוג ספרות שמפר את התנאי.

2. רשימה מיוחדת – `is_special_list(lst)`:

•בודקים שהרשימה ממוינת בסדר עולה: לכל i>0i>0 צריך להתקיים `lst[i-1] <= lst[i]`. אם לא – מחזירים `False` מיד.

•באותו מעבר בודקים אם יש לפחות מספר מיוחד אחד (דגל `has_special`).

•מחזירים את הדגל: רשימה ממוינת בלי אף מספר מיוחד (וגם רשימה ריקה) אינה מיוחדת.

3. רשימה סופר מיוחדת – `is_super_special(lists)`: עוברים על כל הרשימות הפנימיות; אם אחת מהן אינה מיוחדת – `False`, אחרת `True`.

הקוד:

def is_special_num(num):
    if num <= 0:
        return False
    last = num % 10              # הספרה הימנית
    num //= 10
    while num > 0:
        digit = num % 10         # הספרה שמשמאל ל-last
        if digit >= last:        # הספרות לא עולות ממש
            return False
        last = digit
        num //= 10
    return True

def is_special_list(lst):
    has_special = False
    for i in range(len(lst)):
        if i > 0 and lst[i - 1] > lst[i]:
            return False         # לא ממוינת בסדר עולה
        if is_special_num(lst[i]):
            has_special = True
    return has_special

def is_super_special(lists):
    for lst in lists:
        if not is_special_list(lst):
            return False
    return True

בדיקה על הדוגמאות: 12, 138, 2689, 4 מחזירים `True`; 43, 176, −123-123, 33 מחזירים `False`. למשל, ב-176 הספרה 7 אינה קטנה מהספרה 6 שמימינה, ולכן מוחזר `False`; ב-33 שתי הספרות שוות, ולכן גם הוא אינו מיוחד.

דוגמה לרשימת רשימות: `[[-5, 0, 12, 40], [1], [3, 3, 7]]` היא סופר מיוחדת (כל רשימה ממוינת, ובכל אחת יש מספר מיוחד: 12, 1, 3). לעומת זאת `[[-5, 0, 12, 40], [10, 20]]` אינה סופר מיוחדת, כי ב-`[10, 20]` אין מספר מיוחד.

תשובה: הפעולה `is_super_special` שלמעלה (עם פעולות העזר) – מחזירה `True` אם ורק אם כל רשימה פנימית ממוינת בסדר עולה ומכילה לפחות מספר חיובי אחד שספרותיו עולות ממש.

סעיף ב

תשובה:

O(N⋅d)O(N\cdot d), כאשר NN מספר המספרים הכולל בכל הרשימות ו-dd מספר הספרות המרבי; עבור מספרים בגודל חסום – O(N)O(N).

נסמן ב-NN את מספר המספרים הכולל בכל הרשימות הפנימיות (אם יש kk רשימות, כל אחת באורך עד mm, אז N≤k⋅mN\le k\cdot m), וב-dd את מספר הספרות המרבי של מספר.

1. `is_special_num` עוברת פעם אחת על הספרות: O(d)O(d).

2. `is_special_list` עוברת פעם אחת על רשימה באורך mm, ולכל איבר מבצעת השוואה אחת (O(1)O(1)) וקריאה ל-`is_special_num` (O(d)O(d)): O(m⋅d)O(m\cdot d).

3. `is_super_special` קוראת ל-`is_special_list` פעם אחת לכל רשימה, ולכן כל מספר בכל הרשימות נבדק לכל היותר פעם אחת: O(k⋅m⋅d)=O(N⋅d)O(k\cdot m\cdot d)=O(N\cdot d).

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

תשובה: O(N⋅d)O(N\cdot d), כלומר O(N)O(N) – לינארית במספר הכולל של המספרים בכל הרשימות.

שאלה 14 · רקורסיה: אינדקס המינימום ומיון בסדר יורד

נתונה הפעולה הרקורסיביות `secret`:

def secret(a):
    if(len(a) == 1):
        return 0
    k = secret(a[:-1])
    if a[-1] < a[k]:
        return (len(a) - 1);
    return k
א.

נתונה הרשימה הבאה של מספרים שלמים:

a = [3,5,1,2,10,9]

עקבו אחרי זימון `secret(a)` רשמו את תוצאת הזימון. יש להראות מעקב!

(3 נקודות)
ב.

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

(2 נקודות)

נתונה הפעולה הרקורסיביות `mystery`:

def mystery(a):
    if len(a) == 1:
        return a
    k = secret(a)
    temp = a[k]
    a[k] = a[-1]

    return (mystery(a[:-1])+[temp])
ג.

נתונה הרשימה הבאה של מספרים שלמים:

a = {3,5,1,2,10,9}

עקבו אחרי זימון `mystery(a)` ורשמו את תוצאות הזימון.

יש להראות מעקב אחרי הפעולה mystery, אין צורך במעקב אחרי הפעולה secret

(4 נקודות)
ד.

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

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

סעיף א

תשובה:

`secret(a)` מחזירה 2 (המקום של הערך 1, הקטן ביותר).

רעיון: `secret` קוראת לעצמה על הרשימה בלי האיבר האחרון (`a[:-1]`), עד שנשארת רשימה באורך 1 (ואז מוחזר 0). בחזרה מהרקורסיה, בכל שלב משווים את האיבר האחרון `a[-1]` לאיבר `a[k]` שהקריאה הפנימית החזירה: אם האחרון קטן ממנו, מוחזר המקום של האחרון (`len(a) - 1`), אחרת מוחזר `k`.

מעקב – הקריאות יורדות מלמעלה למטה, והערכים חוזרים מלמטה למעלה:

קריאההרשימהk (מהקריאה הפנימית)a[-1]a[k]a[-1] < a[k]?ערך מוחזר
6[3]–––– (תנאי עצירה)0
5[3,5]053לא0
4[3,5,1]013כן2
3[3,5,1,2]221לא2
2[3,5,1,2,10]2101לא2
1[3,5,1,2,10,9]291לא2

תשובה: `secret(a)` מחזירה 2.

סעיף ב

תשובה:

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

ההסבר (באינדוקציה על אורך הרשימה):

1. ברשימה באורך 1 האיבר היחיד הוא הקטן ביותר, ומוחזר המקום 0.

2. נניח ש-`secret(a[:-1])` מחזירה את המקום `k` של המינימום בכל הרשימה פרט לאיבר האחרון. המינימום של כל הרשימה הוא או `a[k]` או האיבר האחרון. אם האחרון קטן ממש מ-`a[k]` – הוא המינימום, ומוחזר המקום שלו `len(a) - 1`; אחרת המינימום נשאר `a[k]`.

3. בגלל ההשוואה `<` (ולא `<=`), במקרה של שוויון נשאר המקום הקודם – כלומר מוחזר המופע הראשון של המינימום.

תשובה: `secret(a)` מחזירה את האינדקס של הערך המינימלי ברשימה (המופע הראשון שלו).

סעיף ג

תשובה:

`mystery(a)` מחזירה `[10, 9, 5, 3, 2, 1]`.

הערה: בשאלון הרשימה כתובה בסוגריים מסולסלים, אבל לפי הנוסח מדובר ברשימה של מספרים שלמים, ולכן מתייחסים אליה כאל `a = [3,5,1,2,10,9]`.

רעיון: בכל קריאה `secret(a)` נותנת את מקום המינימום `k`. שומרים את המינימום ב-`temp`, מעתיקים את האיבר האחרון למקום `k` (כך המינימום "יוצא" מהרשימה ואף ערך אחר לא הולך לאיבוד), ואז קוראים ברקורסיה על הרשימה בלי האיבר האחרון ומוסיפים את `temp` בסוף התוצאה.

מעקב (הקריאות יורדות מלמעלה למטה):

קריאהa בכניסהktempa אחרי `a[k] = a[-1]`קריאה רקורסיבית על
1[3,5,1,2,10,9]21[3,5,9,2,10,9][3,5,9,2,10]
2[3,5,9,2,10]32[3,5,9,10,10][3,5,9,10]
3[3,5,9,10]03[10,5,9,10][10,5,9]
4[10,5,9]15[10,9,9][10,9]
5[10,9]19[10,9][10]
6[10]–––תנאי עצירה: מוחזר [10]

החזרה מהרקורסיה (מלמטה למעלה), בכל שלב מוסיפים את `temp` בסוף:

קריאהערך מוחזר
6[10]
5[10] + [9] = [10, 9]
4[10, 9] + [5] = [10, 9, 5]
3[10, 9, 5] + [3] = [10, 9, 5, 3]
2[10, 9, 5, 3] + [2] = [10, 9, 5, 3, 2]
1[10, 9, 5, 3, 2] + [1] = [10, 9, 5, 3, 2, 1]

(בקריאה הראשונה הרשימה המקורית עצמה משתנה ל-`[3,5,9,2,10,9]`, כי `a[k] = a[-1]` מתבצע עליה; הקריאות הבאות פועלות על העתקים שנוצרו ב-`a[:-1]`.)

תשובה: `mystery(a)` מחזירה `[10, 9, 5, 3, 2, 1]`.

סעיף ד

תשובה:

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

ההסבר:

1. בכל קריאה מוציאים מהרשימה את הערך הקטן ביותר (`temp`, בעזרת `secret`), ובמקומו שמים את האיבר האחרון. כך הרשימה `a[:-1]` מכילה בדיוק את כל שאר הערכים.

2. התוצאה של הקריאה היא: התוצאה הרקורסיבית על שאר הערכים, ואחריה הערך הקטן ביותר בסוף.

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

4. תופעת לוואי: הרשימה המקורית שהועברה משתנה (בה האיבר הקטן ביותר מוחלף באיבר האחרון).

תשובה: `mystery(a)` מחזירה את ערכי הרשימה ממוינים בסדר יורד (מיון בחירה רקורסיבי).

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

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

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