מבחן מה"ט אלגוריתמיקה ותכנות (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 · קליטת זוגות מספרים: מנייה וסכום
כתבו קטע תוכנית הקולט 20 זוגות של מספרים שלמים וחיוביים.
על התוכנית לחשב ולהדפיס:
•את כמות המספרים הדו-ספרתיים שנקלטו.
•את סכום כל המספרים הזוגיים שנקלטו.
◂ פתרון מלא לשאלה 1
פתרון
לולאה של 20 סיבובים, בכל סיבוב קולטים שני מספרים; מונה למספרים שבין 10 ל-99 וצובר לסכום המספרים הזוגיים.
הרעיון: 20 זוגות הם 40 מספרים. נריץ לולאה של 20 סיבובים, ובכל סיבוב נקלוט זוג אחד (שני מספרים). כל מספר שנקלט נבדוק בשתי בדיקות נפרדות:
1. מספר שלם וחיובי הוא דו-ספרתי אם ; במקרה כזה מגדילים מונה `count_two_digit` ב-1.
2. מספר זוגי אם השארית שלו בחלוקה ב-2 היא 0 (`num % 2 == 0`); במקרה כזה מוסיפים אותו לצובר `sum_even` (מוסיפים את הערך עצמו, כי מבקשים סכום ולא כמות).
שתי הבדיקות בלתי תלויות (מספר כמו 24 גם דו-ספרתי וגם זוגי), ולכן אלה שני `if` נפרדים ולא `elif`.
כדי לא לכתוב את הבדיקות פעמיים, עוברים בלולאה פנימית קצרה על שני המספרים של הזוג. בסוף מדפיסים את המונה ואת הצובר.
count_two_digit = 0
sum_even = 0
for i in range(20):
a = int(input())
b = int(input())
for num in (a, b):
if 10 <= num <= 99:
count_two_digit = count_two_digit + 1
if num % 2 == 0:
sum_even = sum_even + num
print("two-digit numbers:", count_two_digit)
print("sum of even numbers:", sum_even)דוגמה: אם נקלטו (בין השאר) הזוגות 12, 7 ו-150, 33: המספרים 12 ו-33 דו-ספרתיים, והמספרים 12 ו-150 זוגיים (תרומה של לסכום).
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · קליטת מחרוזות עד זקיף: חיפוש תו
כתבו קטע תוכנית הקולטת מחרוזות עד שתיקלט מחרוזת באורך אי-זוגי.
עבור כל מחרוזת יש לבדוק אם מופיעה בה האות 'Z' ולהדפיס הודעה מתאימה.
כמו כן, יש למנות ולהדפיס את כמות המחרוזות אשר מתחילות ומסתיימות בתווים זהים.
◂ פתרון מלא לשאלה 2
פתרון
לולאת while שרצה כל עוד אורך המחרוזת זוגי; בכל מחרוזת בודקים `'Z' in s` ומשווים בין `s[0]` ל-`s[-1]`; בסוף מדפיסים את המונה.
הרעיון: מספר המחרוזות לא ידוע מראש, ולכן משתמשים בלולאת `while` עם "זקיף": קולטים מחרוזת לפני הלולאה, והלולאה רצה כל עוד אורך המחרוזת זוגי (`len(s) % 2 == 0`). המחרוזת באורך האי-זוגי רק מסיימת את הקלט, ולכן אינה מעובדת.
בכל סיבוב:
1. בודקים אם התו `'Z'` מופיע במחרוזת בעזרת האופרטור `in`, ומדפיסים הודעה מתאימה (מופיע / לא מופיע).
2. בודקים אם התו הראשון `s[0]` שווה לתו האחרון `s[-1]`; אם כן מגדילים את המונה `count_same`. מחרוזת ריקה היא באורך 0, כלומר זוגי, ולכן היא נכנסת ללולאה; כדי שלא תהיה גישה לתו שלא קיים, בודקים קודם ש-`len(s) > 0`.
3. קולטים את המחרוזת הבאה בסוף הסיבוב, וכך תנאי הלולאה נבדק עליה.
אחרי הלולאה מדפיסים את המונה.
count_same = 0
s = input()
while len(s) % 2 == 0:
if 'Z' in s:
print("The letter Z appears in", s)
else:
print("The letter Z does not appear in", s)
if len(s) > 0 and s[0] == s[-1]:
count_same = count_same + 1
s = input()
print("strings that start and end with the same character:", count_same)דוגמה: עבור הקלט `abca`, `ZZ`, `xyZx`, `abc`: יודפס ש-Z לא מופיעה ב-abca, מופיעה ב-ZZ ומופיעה ב-xyZx; המחרוזת abc באורך 3 עוצרת את הקלט, והמונה הוא 3 (בשלוש המחרוזות התו הראשון שווה לאחרון).
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · מספרים אקראיים: השכיח ומספרים שלא נוצרו
כתבו קטע תוכנית המייצרת 40 מספרים אקראיים דו-ספרתיים חיוביים. על התוכנית לחשב ולהדפיס:
•מהו המספר שנוצר הכי הרבה פעמים (אם יש כמה מספרים שנוצרו הכי הרבה פעמים, מספיק להדפיס אחד מהם).
•אילו מספרים לא נוצרו.
◂ פתרון מלא לשאלה 3
פתרון
רשימת מונים בגודל 90 (התא `num-10` סופר את המספר num); המספר השכיח הוא האינדקס של המונה המקסימלי ועוד 10, והמספרים שלא נוצרו הם האינדקסים שבהם המונה 0, ועוד 10.
הרעיון: רשימת מונים. המספרים הדו-ספרתיים החיוביים הם 10 עד 99, כלומר ערכים אפשריים. ניצור רשימה `counts` של 90 מונים, שכולם 0 בהתחלה. המונה `counts[num - 10]` סופר כמה פעמים נוצר המספר num (המספר 10 בתא 0, המספר 99 בתא 89).
1. יצירת המספרים: 40 פעמים מגרילים `num = random.randint(10, 99)` (שני הקצוות כלולים) ומגדילים את המונה המתאים ב-1.
2. המספר השכיח: מחפשים את התא עם המונה הגדול ביותר (חיפוש מקסימום רגיל). בגלל ההשוואה `>` נשמר התא הראשון שבו מתקבל המקסימום, כלומר אם יש כמה מספרים שכיחים, מודפס הקטן שבהם, וזה מספיק לפי השאלה. המספר עצמו הוא האינדקס ועוד 10.
3. המספרים שלא נוצרו: עוברים על כל 90 התאים ומדפיסים `i + 10` לכל תא שבו המונה 0.
import random
counts = [0] * 90 # counts[i] = how many times the number i+10 was generated
for i in range(40):
num = random.randint(10, 99)
counts[num - 10] = counts[num - 10] + 1
max_index = 0
for i in range(1, 90):
if counts[i] > counts[max_index]:
max_index = i
print("most frequent number:", max_index + 10, "appeared", counts[max_index], "times")
print("numbers that were not generated:")
for i in range(90):
if counts[i] == 0:
print(i + 10, end=" ")
print()שימו לב: אסור להגריל `random.randint(10, 100)`, כי 100 הוא מספר תלת-ספרתי והתא `counts[90]` לא קיים.
סיבוכיות: , כלומר מספר קבוע של פעולות.
תשובה: קטע התוכנית שלמעלה.
שאלה 4 · מחלקת מנות: החלפה וצירופי זוגות
המסעדה "Chef4U" מציעה משלוח מנות שף קטנות במחיר מוזל עד לבית הלקוח.
המחלקה Food מייצגת מנה. למחלקה 4 תכונות:
•שם המנה – name, מטיפוס מחרוזת, string.
•מחיר המנה – price, מטיפוס מספר ממשי, float.
•מנה חלבית? – isMilk, מטיפוס בוליאני, boolean (true – מנה חלבית, false – לא).
•דירוג המנה – raiting, מטיפוס מספר שלם, int. דירוג המנה הוא מספר שלם מ- 1 (הכי נמוך) עד 10 (הכי גבוה).
לפעמים המסעדה נאלצת להחליף את המנה הנוכחית (self) למנה אחרת other. אפשר להחליף בין המנות אם שתיהן מאותו סוג (חלבי או לא), יש להן אותו דירוג ומחיר של המנה other לא גבוה ממחיר של המנה self.
כתבו פעולה המקבלת מנה אחרת (הפנייה לעצם מטיפוס Food). הפעולה תבדוק אם ניתן להחליף מנה self למנה other. אם כן – הפעולה תחזיר ערך True, ולא – הפעולה תחזיר ערך False. כותרת הפעולה:
can_change(self, other)כתבו פעולה המקבלת רשימת מנות arr ומנה new_food. הפעולה תדפיס את שמות כל המנות שאפשר להחליף אותן למנה new_food. כותרת הפעולה:
changes(arr, new_food)המסעדה הכריזה על המבצע: שתי מנות שונות בפחות מ- 100 ₪.
כתבו פעולה המקבלת רשימת מנות ומדפיסה את כל הצירופים האפשריים של שתי מנות שונות שעולות יחד פחות מ- 100 ₪. כותרת הפעולה:
offers(arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים ב' ו-ג'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 4
סעיף א
`return self.isMilk == other.isMilk and self.raiting == other.raiting and other.price <= self.price`
הרעיון: הפעולה היא פעולה פנימית של המחלקה Food. אפשר להחליף רק אם שלושה תנאים מתקיימים יחד, ולכן מחברים אותם ב-`and` ומחזירים את התוצאה הבוליאנית ישירות:
1. אותו סוג: `self.isMilk == other.isMilk`.
2. אותו דירוג: `self.raiting == other.raiting`.
3. המחיר של other לא גבוה מהמחיר של self: `other.price <= self.price` ("לא גבוה" כולל מחיר שווה).
נכתוב את המחלקה עם פעולה בונה, ואת הפעולה בתוכה:
class Food:
def __init__(self, name, price, isMilk, raiting):
self.name = name
self.price = price
self.isMilk = isMilk
self.raiting = raiting
def can_change(self, other):
return (self.isMilk == other.isMilk and
self.raiting == other.raiting and
other.price <= self.price)תשובה: הפעולה מחזירה True בדיוק כששלושת התנאים מתקיימים.
סעיף ב
עוברים על המנות ב-arr ומדפיסים את `food.name` לכל מנה שעבורה `food.can_change(new_food)` מחזירה True.
הרעיון: כל מנה food ברשימה היא המנה ה"נוכחית" (self) שאולי נחליף, ו-new_food היא המנה ה"אחרת" (other). לכן לכל מנה מזמנים את הפעולה מסעיף א, `food.can_change(new_food)`, ואם התשובה True מדפיסים את שם המנה.
def changes(arr, new_food):
for food in arr:
if food.can_change(new_food):
print(food.name)דוגמה: אם arr מכילה את המנות pasta (50, חלבית, דירוג 8), pizza (40, חלבית, 8), steak (90, לא חלבית, 8), ו-new_food היא lasagna (45, חלבית, 8), יודפס רק pasta: ל-pizza המחיר 40 נמוך מ-45, ו-steak אינה חלבית.
תשובה: הפעולה שלמעלה.
סעיף ג
שתי לולאות מקוננות על i ועל `j > i`; מדפיסים את שמות arr[i] ו-arr[j] כאשר `arr[i].price + arr[j].price < 100`.
הרעיון: צירוף של שתי מנות שונות הוא זוג מקומות ברשימה. לולאה חיצונית עוברת על i, ולולאה פנימית מתחילה מ-`i + 1`. כך:
•מנה לא מצורפת לעצמה ();
•כל צירוף מודפס פעם אחת בלבד (הזוג (pizza, pasta) לא יודפס שוב אחרי (pasta, pizza)).
לכל זוג בודקים אם סכום המחירים קטן מ-100, ואם כן מדפיסים את שני השמות.
def offers(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i].price + arr[j].price < 100:
print(arr[i].name, "+", arr[j].name)דוגמה: עבור המחירים pasta 50, pizza 40, steak 90, salad 45 יודפסו: pasta + pizza (90), pasta + salad (95), pizza + salad (85). כל צירוף עם steak עולה יותר מ-100.
תשובה: הפעולה שלמעלה.
סעיף ד
`changes`: ; `offers`: , כאשר n הוא מספר המנות ברשימה.
נסמן ב-n את מספר המנות ברשימה arr.
1. `changes` (סעיף ב): לולאה אחת שעוברת על n המנות, ובכל סיבוב מזמנים את `can_change`, שמבצעת שלוש השוואות בלבד, כלומר . סך הכול .
2. `offers` (סעיף ג): לולאה מקוננת. עבור i הלולאה הפנימית רצה פעמים, ולכן מספר הזוגות הנבדקים הוא
ובכל בדיקה עבודה קבועה. לכן הסיבוכיות היא .
תשובה: סעיף ב – ; סעיף ג – .
שאלה 5 · רשימה מושלמת K וסופר מושלמת
רשימה של מספרים שלמים חיוביים נקראת רשימה "מושלמת K" אם היא עונה על התנאי הבא:
הסכום של כל K האיברים ההתחלתיים ברשימה (האיברים אשר נמצאים במקומות 0, 1, 2,..., K-1) מתחלק ב-K ללא שארית.
הרשימה הבאה היא רשימה "מושלמת 5":
כי סכום של חמשת האיברים הראשונים 15=7+1+4+1+2 מתחלק ב- 5.
כתבו פעולה המקבלת רשימה של מספרים שלמים חיוביים arr ומספר שלם חיובי K. הפעולה תחזיר ערך True, אם הרשימה "מושלמת K", ולא, הפעולה תחזיר ערך False.
כותרת הפעולה:
is_perfectK(arr, k)רשימה של מספרים שלמים חיוביים נקראת רשימה "סופר מושלמת " אם היא רשימה מושלמת K עבור כל ערך של K מ- 1 עד לאורך הרשימה.
הרשימה הנתונה
הוא לא רשימה "סופר מושלמת" כי היא לא רשימה "מושלמת 4".
כתבו פעולה המקבלת רשימה של מספרים שלמים חיוביים arr. הפעולה תחזיר ערך True, אם הרשימה " סופר מושלמת ", ולא, הפעולה תחזיר ערך False.
כותרת הפעולה:
is_super_perfect(arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 5
סעיף א
מסכמים את k האיברים הראשונים ומחזירים `total % k == 0` (ו-False אם k גדול מאורך הרשימה).
הרעיון: מחשבים בלולאה את סכום האיברים במקומות ובודקים אם השארית של הסכום בחלוקה ב-k היא 0.
אם k גדול מאורך הרשימה, אין ברשימה k איברים התחלתיים, ולכן נחזיר False (בלי הבדיקה הזאת הייתה גישה לתא שלא קיים).
def is_perfectK(arr, k):
if k > len(arr):
return False
total = 0
for i in range(k):
total = total + arr[i]
return total % k == 0בדיקה על הדוגמה: עבור הסכום הוא , ו-, לכן מוחזר True. עבור הסכום הוא ו-, לכן מוחזר False.
תשובה: הפעולה שלמעלה.
סעיף ב
סכום מצטבר: לכל k מ-1 עד len(arr) מוסיפים את arr[k-1] ובודקים שהסכום מתחלק ב-k; אם לא – False, ואם כל הבדיקות עברו – True.
הרעיון: צריך לבדוק את התנאי מסעיף א לכל (n אורך הרשימה). אפשר לזמן את `is_perfectK(arr, k)` לכל k, אבל אז הסכום מחושב כל פעם מההתחלה. יעיל יותר לשמור סכום מצטבר: הסכום של k האיברים הראשונים שווה לסכום של האיברים הראשונים ועוד `arr[k-1]`. כך כל k מוסיף פעולה אחת בלבד.
ברגע שנמצא k שעבורו הסכום לא מתחלק ב-k, הרשימה אינה סופר מושלמת ומחזירים False מיד. אם הלולאה הסתיימה – מחזירים True.
def is_super_perfect(arr):
total = 0
for k in range(1, len(arr) + 1):
total = total + arr[k - 1] # sum of the first k elements
if total % k != 0:
return False
return Trueבדיקה על הדוגמה: הסכומים המצטברים הם 7, 8, 12, 13, ... עבור הם מתחלקים (, , ), אבל עבור : , ולכן מוחזר False, כמו בשאלה.
דוגמה לרשימה סופר מושלמת: – הסכומים המצטברים מתחלקים ב- בהתאמה.
תשובה: הפעולה שלמעלה.
סעיף ג
סעיף א: , כלומר לכל היותר ; סעיף ב: .
נסמן ב-n את אורך הרשימה.
1. `is_perfectK`: הלולאה רצה k פעמים ובכל סיבוב חיבור אחד, ולכן . מכיוון ש- (אחרת מוחזר False מיד), זה לכל היותר .
2. `is_super_perfect`: לולאה אחת של לכל היותר n סיבובים, ובכל סיבוב חיבור אחד ובדיקת שארית אחת – . לכן .
(אילו היינו מזמנים את `is_perfectK` לכל k, הסיבוכיות הייתה , כלומר ; הסכום המצטבר חוסך את זה.)
תשובה: סעיף א – ; סעיף ב – .
שאלה 6 · מעקב: מניית מופעי ספרה במספרים
נתונה הפעולה one המקבלת כפרמטר מספר שלם וחיובי num וספרה dig.
def one(num, dig):
res = 0
while num > 0:
if num % 10 == dig:
res = res + 1
num = num // 10
return resתנו דוגמה של מספר num > 1000 כך שתוצאת הזימון `one(num, 7)` תהיה 3.
מה מבצעת הפעולה one באופן כללי?
נתונה הפעולה two המקבלת רשימה arr של מספרים שלמים חיוביים וספרה dig:
def two(arr, dig):
res = 0
for i in range(len(arr)):
res = res + one (arr[i], dig)
return resנתונה רשימה של מספרים שלמים וחיוביים arr הבאה:
arr = [24, 34783, 1245, 68, 468, 9445]עקבו באמצעות טבלת מעקב אחר ביצוע זימון הפעולה `two(arr, 4)` ורשמו מה יהיה הפלט.
הסבירו מה מבצעת הפעולה two באופן כללי.
נתונה הפעולה three המקבלת רשימה של מספרים שלמים חיוביים arr:
def three(arr):
res = 0
for i in range(1,10):
if two(arr, i) > two(arr, res):
res = i
return resתנו דוגמה של רשימה arr בגודל שישה תאים שעבורו תוצאת זימון הפעולה `three(arr)` תהיה 6.
הסבירו מה מבצעת הפעולה three באופן כללי.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `num = 7577` (כל מספר גדול מ-1000 שבו הספרה 7 מופיעה בדיוק 3 פעמים).
הפעולה עוברת על ספרות num מהאחרונה לראשונה (`num % 10` היא ספרת האחדות, ו-`num // 10` מוחק אותה) ומוסיפה 1 ל-res בכל פעם שהספרה שווה ל-dig. לכן צריך מספר גדול מ-1000 שבו הספרה 7 מופיעה בדיוק שלוש פעמים, למשל 7577.
תשובה: `num = 7577` (למשל), ו-`one(7577, 7)` מחזירה 3.
מחזירה את מספר הפעמים שהספרה dig מופיעה במספר num.
בכל סיבוב הפעולה בודקת את ספרת האחדות של num (`num % 10`), סופרת אותה אם היא שווה ל-dig, ומוחקת אותה (`num // 10`). הלולאה נמשכת עד שלא נשארו ספרות (num הופך ל-0). כך כל ספרה של num נבדקת פעם אחת בדיוק.
תשובה: הפעולה מחזירה כמה פעמים הספרה dig מופיעה במספר num.
סעיף ב
הפעולה מחזירה 6.
הפעולה עוברת על כל איברי הרשימה ומוסיפה ל-res את מספר המופעים של הספרה 4 בכל איבר (לפי סעיף א). `len(arr) = 6`, ובהתחלה `res = 0`.
תשובה: הזימון `two(arr, 4)` מחזיר 6.
מחזירה את מספר המופעים הכולל של הספרה dig בכל המספרים שברשימה.
הפעולה מזמנת את one לכל איבר ברשימה וצוברת את התוצאות. לכן היא סופרת את כל המופעים של dig בכל המספרים יחד.
תשובה: הפעולה מחזירה כמה פעמים בסך הכול מופיעה הספרה dig בכל המספרים שברשימה arr.
סעיף ג
למשל `arr = [6, 16, 26, 36, 46, 56]`.
לפי סעיף 2 (בהמשך), three מחזירה את הספרה שמופיעה הכי הרבה פעמים בכל הרשימה. לכן צריך רשימה של 6 מספרים שבה הספרה 6 מופיעה יותר מכל ספרה אחרת (כולל 0), למשל:
`arr = [6, 16, 26, 36, 46, 56]`
מספר המופעים של כל ספרה (`two(arr, d)`):
מעקב: בהתחלה `res = 0` (0 מופעים). עבור : , לכן `res = 1`. עבור : לא מתקיים, res נשאר 1. עבור : , לכן `res = 6`. עבור : לא מתקיים.
תשובה: `arr = [6, 16, 26, 36, 46, 56]`, ו-`three(arr)` מחזירה 6.
מחזירה את הספרה (0 עד 9) שמופיעה הכי הרבה פעמים בכל מספרי הרשימה; בשוויון – הקטנה מביניהן.
הפעולה היא חיפוש מקסימום: res מתחיל בספרה 0, ועבור כל ספרה i מ-1 עד 9 משווים את מספר המופעים שלה ברשימה (`two(arr, i)`) למספר המופעים של הספרה הטובה ביותר עד כה (`two(arr, res)`). אם הוא גדול ממש – i הופכת לטובה ביותר.
בגלל ההשוואה `>` (גדול ממש), כשכמה ספרות מופיעות אותו מספר מקסימלי של פעמים, נשארת הקטנה מביניהן.
תשובה: הפעולה מחזירה את הספרה שמופיעה הכי הרבה פעמים בכל המספרים שברשימה (ואם יש כמה כאלה – את הקטנה מביניהן).
שאלה 7 · מעקב: סיווג תווים במחרוזת
נתונה הפעולה secret הבאה המקבלת מחרוזת:
def secret(str):
c = 0
print("%", end = "")
for i in range(len(str)):
if str[i] >= 'A' and str[i] <='Z':
print(i,'#', end = "")
elif str[i] >= 'a' and str[i] <='z':
print(i,'?', end = "")
else:
c = c + 1
print("%", end = "")
return cתנו דוגמה למחרוזת באורך של 6 תווים לכל הפחות שעבורה הפעולה secret תדפיס את המחרוזת הבאה: `%3 ?5 #%`. איזה ערך תחזיר הפעולה?
תנו דוגמה למחרוזת באורך של 6 תווים לכל הפחות שעבורה הפעולה secret תדפיס את המחרוזת הבאה: `%%` . איזה ערך תחזיר הפעולה?
תנו דוגמה למחרוזת באורך של 6 תווים לכל הפחות שעבורה הפעולה secret תחזיר 2.
מה תדפיס הפעולה?
מה מבצעת הפעולה?
◂ פתרון מלא לשאלה 7
סעיף א
למשל `"12!a3B"`; הפעולה תחזיר 4.
איך הפעולה מדפיסה: בהתחלה ובסוף מודפס `%`. לכל אות גדולה באנגלית במקום i מודפס `i #`, ולכל אות קטנה `i ?` (הפקודה `print(i,'#', end = "")` מפרידה ברווח בין i לסימן, ולא יורדת שורה). כל תו אחר לא מודפס, אלא נספר ב-c, והפעולה מחזירה את c.
לכן הפלט `%3 ?5 #%` אומר: במקום 3 אות קטנה, במקום 5 אות גדולה, ובכל שאר המקומות תווים שאינם אותיות באנגלית. מחרוזת של 6 תווים בדיוק: `"12!a3B"`.
תשובה: למשל `"12!a3B"`; הפלט `%3 ?5 #%` והערך המוחזר 4.
סעיף ב
למשל `"123456"`; הפעולה תחזיר 6 (אורך המחרוזת).
הפלט `%%` אומר שבין שני סימני ה-% לא הודפס דבר, כלומר אין במחרוזת אף אות באנגלית (גדולה או קטנה). כל התווים נספרים ב-c, ולכן הערך המוחזר שווה לאורך המחרוזת.
דוגמה: `"123456"` – שישה תווים שאינם אותיות, ולכן מוחזר 6.
תשובה: למשל `"123456"`; הפלט `%%` והערך המוחזר 6.
סעיף ג
למשל `"5Sima2"`; יודפס `%1 #2 ?3 ?4 ?%`.
הערך המוחזר הוא מספר התווים שאינם אותיות באנגלית, ולכן צריך מחרוזת שבה בדיוק 2 תווים כאלה, וכל השאר אותיות. דוגמה: `"5Sima2"`.
תשובה: למשל `"5Sima2"`; הפלט `%1 #2 ?3 ?4 ?%` והערך המוחזר 2.
סעיף ד
מדפיסה בין שני סימני % את מקומות האותיות באנגלית (עם # לאות גדולה ו-? לאות קטנה) ומחזירה את מספר התווים שאינם אותיות באנגלית.
הפעולה עוברת על כל תווי המחרוזת:
•לכל אות גדולה באנגלית מדפיסה את המקום שלה ואחריו `#`;
•לכל אות קטנה באנגלית מדפיסה את המקום שלה ואחריו `?`;
•את כל שאר התווים (ספרות, סימנים, רווחים) היא סופרת.
הפלט כולו עטוף בסימני `%` בהתחלה ובסוף.
תשובה: הפעולה מדפיסה, בין שני סימני %, את מיקומי האותיות האנגליות במחרוזת (# לגדולה, ? לקטנה), ומחזירה את מספר התווים במחרוזת שאינם אותיות באנגלית.
שאלה 8 · פלינדרום ופלינדרום של ערכים זוגיים
נתונה הגדרה הבאה:
"פָּלִינְדְרוֹם" הוא רצף ערכים שקריאתו מימין לשמאל ומשמאל לימין היא זהה.
דוגמאות לרשימות שהן פלינדרומים:
[1] , [10,10,10,10], [5,2,2,5] , [1,3,10,3,1]
כתבו פעולה המקבלת רשימה של מספרים שלמים ובודקת אם היא "פלינדרום"
כותרת הפעולה:
def is_palindrom(arr)נתונה הגדרה נוספת:
"פלינדרום של ערכים זוגיים" הוא רצף מספרים שלמים שקריאתו רק ערכים זוגיים שיש בו מימין לשמאל ומשמאל לימין היא זהה.
דוגמאות לפלינדרומים של ערכים זוגיים ( הערכים המודגשים):
[1,3,2], [10,3,4,5,7,4,10], [3,5,7,1], [5,2,2,5], [1,3,10,3,1,10]
כתבו פעולה המקבלת רשימה של מספרים שלמים ובודקת אם היא "פלינדרום של ערכים זוגיים".
כותרת הפעולה:
def is_even_palindrom(arr)מהן סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
משווים את `arr[i]` ל-`arr[n-1-i]` עבור i מ-0 עד `n//2 - 1`; אם יש אי-שוויון מחזירים False, אחרת True.
הרעיון: רשימה היא פלינדרום אם האיבר הראשון שווה לאחרון, השני לזה שלפני האחרון, וכן הלאה. לכן משווים זוגות מהקצוות פנימה: `arr[i]` מול `arr[n-1-i]`. מספיק לעבור עד האמצע (`n // 2` זוגות): אחרי האמצע הזוגות חוזרים על עצמם, ובאורך אי-זוגי האיבר האמצעי שווה לעצמו.
אם נמצא זוג שונה – מחזירים False מיד; אם כל הזוגות שווים – True.
def is_palindrom(arr):
n = len(arr)
for i in range(n // 2):
if arr[i] != arr[n - 1 - i]:
return False
return Trueבדיקה: עבור `[1,3,10,3,1]`: , משווים () ו- (), ומוחזר True. עבור `[1,2]`: , ומוחזר False.
תשובה: הפעולה שלמעלה.
סעיף ב
בונים רשימה evens של הערכים הזוגיים לפי הסדר ומחזירים `is_palindrom(evens)`.
הרעיון: לפי ההגדרה מתעלמים מהערכים האי-זוגיים ובודקים אם רצף הערכים הזוגיים (לפי סדר הופעתם) הוא פלינדרום. לכן:
1. עוברים על הרשימה ומעתיקים לרשימה חדשה evens את הערכים הזוגיים (`x % 2 == 0`; גם מספר שלילי זוגי ו-0 נחשבים).
2. מזמנים את הפעולה מסעיף א על evens.
def is_even_palindrom(arr):
evens = []
for x in arr:
if x % 2 == 0:
evens.append(x)
return is_palindrom(evens)•`[10,3,4,5,7,4,10]` → evens = `[10,4,4,10]`, פלינדרום → True.
•`[3,5,7,1]` → evens ריקה; רשימה ריקה היא פלינדרום (אין זוג שונה) → True, בהתאם לדוגמה.
•`[1,3,10,3,1,10]` → evens = `[10,10]` → True.
•לעומת זאת `[2,3,4]` → evens = `[2,4]` → False.
תשובה: הפעולה שלמעלה.
סעיף ג
שתיהן , כאשר n אורך הרשימה.
נסמן ב-n את אורך הרשימה.
1. `is_palindrom`: הלולאה רצה לכל היותר פעמים, ובכל סיבוב השוואה אחת. .
2. `is_even_palindrom`: בניית evens היא מעבר אחד על n האיברים – . אם ב-evens יש m איברים (), הזימון של `is_palindrom` עולה . סך הכול .
תשובה: סעיף א – ; סעיף ב – .
שאלה 9 · מחלקת יעדי טיסה: הכנסות ומחירים
החברה "סע לך" מוכרת כרטיסי טיסה ליעדים שונים ברחבי העולם.
לצורך אחסון נתוני כרטיסים שנמכרו הוגדרה מחלקה בשם Destination ולה 3 תכונות:
•שם היעד – name – מסוג מחרוזת, string.
•מחיר כרטיס – price – מסוג מספר ממשי, float.
•מספר כרטיסים שנמכרו – num – מסוג מספר שלם, int.
במחלקה הוגדרה פעולה הבונה (בנאי, constructor).
def __init__(self,name = None, price = None, num = None):
if name is None:
self.name = "New York"
self.price = 100.0
self.num = 10
else:
self.name = name
self.price = price
self.num = numכתבו פעולה המחשבת ומחזירה את ההכנסה הכוללת ממכירת כרטיסים ליעד (מחיר כולל של כל הכרטיסים שנמכרו ליעד). כותרת הפעולה:
def total(self)לפניכם קטע קוד המשתמש במחלקה Destination:
d1 = Destination()
print(d1.name, d1.total())
d1.name = "London"
d1.num = 200
d1.price = 300.0
print(d1.name, d1.total())
d1.num = 50
d2 = Destination(d1.name, 100.0, d1.num)
print(d2.name, d2.total())עקבו אחרי הביצוע של קטע הקוד ורשמו מה יהיה הפלט.
כתבו פעולה המקבלת רשימת יעדים dest ומחזירה שם יעד שההכנסה הכוללת ממכירת הכרטיסים אליו היא הכי נמוכה.
כותרת הפעולה:
get_not_popular(dest)כתבו פעולה המקבלת רשימה dest ומחיר max_price . הפעולה תחזיר את רשימת שמות היעדים אשר מחיר כרטיס טיסה אליהם הינו נמוך מ- max_price.
אם אין אף יעד כזה, הפעולה תחזיר רשימה ריקה.
כותרת הפעולה:
cheap_dests(dest, max_price)◂ פתרון מלא לשאלה 9
סעיף א
`return self.price * self.num`
ההכנסה הכוללת היא מחיר כרטיס כפול מספר הכרטיסים שנמכרו. זו פעולה פנימית של המחלקה Destination, ולכן היא ניגשת לתכונות דרך self:
def total(self):
return self.price * self.numלדוגמה, ליעד שבו מחיר כרטיס 300.0 ונמכרו 200 כרטיסים: .
תשובה: `total` מחזירה `self.price * self.num`.
סעיף ב
New York 1000.0 / London 60000.0 / London 5000.0 (שלוש שורות).
עוקבים אחרי ערכי התכונות של d1 ו-d2 אחרי כל שורה (`total` מחזירה price כפול num, ו-`print` עם שני ערכים מפריד ביניהם ברווח):
הסבר:
1. `Destination()` בלי פרמטרים: name הוא None, ולכן נבחרים ערכי ברירת המחדל: New York, 100.0, 10. ההכנסה: .
2. אחרי השינויים: .
3. d2 הוא עצם חדש עם השם London, מחיר 100.0 ו-50 כרטיסים: . (התוצאה ממשית, כי price מטיפוס float.)
תשובה: הפלט הוא
New York 1000.0
London 60000.0
London 5000.0סעיף ג
חיפוש מינימום לפי `d.total()`, ומחזירים את `name` של היעד שנמצא.
הרעיון: חיפוש מינימום. מניחים שהרשימה אינה ריקה. מתחילים מהיעד הראשון כ"מינימום עד כה", עוברים על כל היעדים, ואם ההכנסה (`total()`, מסעיף א) של יעד קטנה מזו של המינימום עד כה – הוא הופך למינימום. בסוף מחזירים את השם של היעד שנמצא (ולא את העצם או את ההכנסה).
def get_not_popular(dest):
min_dest = dest[0]
for d in dest:
if d.total() < min_dest.total():
min_dest = d
return min_dest.nameדוגמה: עבור היעדים Paris (500.0, 10 כרטיסים, הכנסה 5000.0), Rome (300.0, 5, הכנסה 1500.0), Eilat (200.0, 40, הכנסה 8000.0) יוחזר "Rome".
תשובה: הפעולה שלמעלה.
סעיף ד
מתחילים מרשימה ריקה ומוסיפים `d.name` לכל יעד שבו `d.price < max_price`; מחזירים את הרשימה.
הרעיון: מתחילים מרשימה ריקה result, עוברים על כל היעדים, ולכל יעד שמחיר הכרטיס שלו קטן ממש מ-max_price ("נמוך מ-") מוסיפים את שמו. אם אין אף יעד כזה, לא נוסף דבר והרשימה הריקה מוחזרת, כנדרש.
def cheap_dests(dest, max_price):
result = []
for d in dest:
if d.price < max_price:
result.append(d.name)
return resultדוגמה: עבור היעדים מסעיף ג ו-`max_price = 400`, מוחזר `['Rome', 'Eilat']`; עבור `max_price = 100` מוחזרת רשימה ריקה.
תשובה: הפעולה שלמעלה.
שאלה 10 · היפוך קטע ברשימה וסיבוב מעגלי
נתונה הפעולה why המקבלת רשימה של מספרים שלמים arr ומספר שלם חיובי s. הפעולה משתמשת בפעולת עזר what.
def why(arr, s):
s = s % len(arr)
what(arr, 0, len(arr) - 1)
what(arr, 0, s - 1)
what(arr, s, len(arr) - 1)
def what(arr, start, end):
while (start < end):
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start = start + 1
end = end - 1נתונה רשימה arr הבאה:
מה יהיה תוכן הרשימה אחרי זימון הפעולה `what(arr, 2, 6)` ? יש להראות מעקב אחרי ביצוע הפעולה.
מה מבצעת הפעולה what באופן כללי? בתשובה יש להתייחס לכל הפרמטרים של הפעולה.
מה יהיה תוכן הרשימה אחרי זימון הפעולה `why(arr, 4)` ?
יש להראות מעקב אחרי ביצוע הפעולה why, אין צורך במעקב אחרי ביצוע הפעולה what.
האם קיימים ערכים של פרמטר s שעבורם הרשימה arr לא השתנה אחרי ביצוע זימון הפעולה `why(arr, s)`? הסבירו את תשובתכם.
מה מבצעת הפעולה why באופן כללי? בתשובה יש להתייחס לכל הפרמטרים של הפעולה.
◂ פתרון מלא לשאלה 10
סעיף א
`[5, 7, 40, 26, 21, 15, 12, 51, 71, 84]`
הלולאה מחליפה בין `arr[start]` ל-`arr[end]`, ואחר כך מקרבת את start ו-end זה לזה, כל עוד .
התא 4 (הערך 21) הוא אמצע הקטע ונשאר במקומו.
תשובה: `[5, 7, 40, 26, 21, 15, 12, 51, 71, 84]`
סעיף ב
הופכת את סדר האיברים ברשימה arr בקטע שבין המקום start למקום end (כולל), ושאר הרשימה לא משתנה.
בכל סיבוב מוחלפים שני האיברים שבקצוות הקטע, והקצוות מתקדמים פנימה, עד שהם נפגשים. כך האיבר שבמקום start עובר למקום end, זה שבמקום start+1 עובר ל-end-1, וכן הלאה – סדר הקטע מתהפך. איברים מחוץ לקטע לא נוגעים בהם. אם לא קורה דבר. השינוי נעשה ברשימה עצמה (הפעולה לא מחזירה ערך).
תשובה: what הופכת (במקום) את סדר האיברים של arr מהמקום start עד המקום end, כולל שני הקצוות.
סעיף ג
`[12, 51, 71, 84, 5, 7, 40, 26, 21, 15]` (ממשיכים מהרשימה שאחרי סעיף א). על הרשימה המקורית מהטבלה: `[40, 51, 71, 84, 5, 7, 12, 15, 21, 26]`.
הפעולה what משנה את הרשימה עצמה, ולכן אחרי הזימון בסעיף א תוכן arr הוא `[5, 7, 40, 26, 21, 15, 12, 51, 71, 84]`. נמשיך מהרשימה הזאת. `len(arr) = 10`.
התוצאה היא הרשימה שלפני הזימון, מסובבת 4 מקומות ימינה: ארבעת האחרונים (12, 51, 71, 84) עברו להתחלה.
אם מבצעים את הזימון דווקא על הרשימה המקורית מהטבלה `[5, 7, 12, 15, 21, 26, 40, 51, 71, 84]`, מתקבל באותו אופן `[40, 51, 71, 84, 5, 7, 12, 15, 21, 26]`.
תשובה: `[12, 51, 71, 84, 5, 7, 40, 26, 21, 15]`
סעיף ד
כן: כל s שהוא כפולה של אורך הרשימה (10, 20, 30, ...).
כן. אם s מתחלק באורך הרשימה n (כאן , כלומר ), אז אחרי השורה הראשונה , והזימונים הם:
1. `what(arr, 0, n-1)` – הרשימה מתהפכת;
2. `what(arr, 0, -1)` – כאן , ולכן הלולאה לא מתבצעת ואין שינוי;
3. `what(arr, 0, n-1)` – הרשימה מתהפכת שוב וחוזרת למצבה המקורי.
במובן של סעיף ה: סיבוב ב-n מקומות (או בכפולה של n) מחזיר כל איבר למקומו.
לכל s אחר (שאינו כפולה של 10) הרשימה בשאלה כן משתנה, כי כל איבריה שונים זה מזה.
תשובה: כן – כל s שהוא כפולה של אורך הרשימה (למשל 10, 20, 30); אז והרשימה מתהפכת פעמיים וחוזרת למצבה.
סעיף ה
מסובבת את הרשימה arr באופן מעגלי s מקומות ימינה (בפועל `s % len(arr)` מקומות).
נסמן = אורך הרשימה ו-. היפוך כל הרשימה מעביר את האיברים האחרונים להתחלה (בסדר הפוך) ואת השאר לסוף (גם בסדר הפוך). שני ההיפוכים הבאים מחזירים כל אחד משני החלקים לסדר המקורי שלו. התוצאה: האיברים האחרונים עוברים להתחלה, והשאר זזים מקומות ימינה – סיבוב מעגלי.
החלוקה s % len(arr) מאפשרת s גדול מהאורך: סיבוב ב-n מקומות לא משנה דבר.
תשובה: why מבצעת סיבוב מעגלי (רוטציה) של הרשימה arr ב-s מקומות ימינה: האיבר שבמקום i עובר למקום . כאשר s כפולה של אורך הרשימה – הרשימה לא משתנה.
שאלה 11 · מחלקת Number: מספר ספרות וסכום ספרות
נתונה מחלקה Number הבאה:
class Number:
def __init__(self, num):
self.num1 = 0
self.num2 = 0
if num < 0:
num = num *(-1)
while num > 0:
self.num1 = self.num1 + 1;
self.num2 = self.num2 + num % 10
num = num // 10
def equals(self, other):
return self.num1 == other.num1 and self.num2 == other.num2
def is_same(self, other):
return self.num1 * other.num2 == self.num2 * other.num1נתונה פעולה mystery הבאה:
def mystery(x, y):
a = Number(x)
b = Number(y)
if x == y:
return 1
if a.equals(b):
return 2
if a.is_same(b):
return 3
return 4תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 2.
תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 3.
תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 4.
האם קיים מספר שלם תלת-ספרתי חיובי x שעבורו הפעולה mystery אף פעם לא תחזיר 2? הסבירו את תשובתכם.
האם קיים מספר שלם תלת-ספרתי חיובי x שעבורו הפעולה mystery אף פעם לא תחזיר 3? הסבירו את תשובתכם.
נתונה פעולה secret הבאה:
def secret(arr):
temp1 = Number(arr[0])
temp2 = Number(arr[0])
pos1 = 0
pos2 = 0
for i in range(1, len(arr)):
cur = Number(arr[i])
if cur.num1 > temp1.num1:
pos1 = i
temp1 = cur
if cur.num2 > temp2.num2:
pos2 = i
temp2 = cur
return pos1 == pos2נתונה הרשימה arr הבאה:
עקבו אחרי ביצוע זימון הפעולה `secret(arr)` ורשמו תוצאת הזימון.
מה מבצעת הפעולה secret באופן כללי עבור רשימה של מספרים שלמים?
◂ פתרון מלא לשאלה 11
סעיף א
למשל `mystery(342, 234)`.
קודם מבינים את המחלקה: הפעולה הבונה של Number מחליפה מספר שלילי בערכו המוחלט, ואז עוברת על ספרותיו: num1 = מספר הספרות, num2 = סכום הספרות.
•`equals` מחזירה True אם לשני המספרים אותו מספר ספרות ואותו סכום ספרות.
•`is_same` בודקת , כלומר שהיחס "סכום ספרות חלקי מספר ספרות" (ממוצע הספרות) שווה בשני המספרים.
כדי לקבל 2 צריך (אחרת מוחזר 1) עם אותו מספר ספרות ואותו סכום ספרות. למשל 342 ו-234: לשניהם 3 ספרות וסכום .
תשובה: `x = 342`, `y = 234`.
למשל `mystery(60, 405)`.
צריך , ש-equals תחזיר False, ו-is_same תחזיר True: אותו ממוצע ספרות אבל לא אותו (מספר ספרות, סכום ספרות).
•`Number(60)`: num1 = 2, num2 = .
•`Number(405)`: num1 = 3, num2 = .\nequals: → False. is_same: ו- → True.
תשובה: `x = 60`, `y = 405`.
למשל `mystery(12, 5)`.
צריך שאף תנאי לא יתקיים: , ממוצע ספרות שונה.
•`Number(12)`: num1 = 2, num2 = 3.
•`Number(5)`: num1 = 1, num2 = 5.\nequals: False. is_same: לעומת → False. לכן מוחזר 4.
תשובה: `x = 12`, `y = 5`.
אם y חיובי – כן: x = 100 (וגם x = 999). אם מותר y שלילי – לא, כי `mystery(x, -x)` מחזירה 2 לכל x.
כדי שיוחזר 2 צריך y שונה מ-x עם 3 ספרות ואותו סכום ספרות S כמו x.
•ל-x = 100 סכום הספרות הוא 1, והמספר התלת-ספרתי היחיד שסכום ספרותיו 1 הוא 100 עצמו (הספרה הראשונה חייבת להיות לפחות 1, ולכן היא 1 ושאר הספרות 0). לכן אין y חיובי מתאים, ו-mystery לא תחזיר 2 לאף y.
•באותו אופן x = 999: סכום הספרות 27 אפשרי בשלוש ספרות רק כ-999.
•לכל x תלת-ספרתי אחר אפשר להזיז יחידה בין ספרות (למשל 342 → 432 או 243) ולקבל y אחר עם אותו סכום.
לכן התשובה היא כן: x = 100 (וגם x = 999).
הערה: הפעולה הבונה של Number מטפלת גם במספרים שליליים (לוקחת ערך מוחלט). אם מותר להעביר y שלילי, אז עבור מתקיים ול-Number(-x) אותו מספר ספרות ואותו סכום ספרות, ולכן `mystery(x, -x)` מחזירה 2 לכל x – ואז אין x כזה.
תשובה: כן – x = 100 (וגם x = 999), כש-y מספר חיובי; אם y יכול להיות שלילי, אין x כזה.
לא. לכל x תלת-ספרתי, `mystery(x, 1001*x)` מחזירה 3 (למשל x = 100, y = 100100).
נראה שלכל x תלת-ספרתי יש y שעבורו מוחזר 3.
יהי S סכום הספרות של x (ל-x יש 3 ספרות). ניקח את y = x "כתוב פעמיים" ברצף, כלומר (למשל 342 → 342342). אז:
1. , ולכן לא מוחזר 1.
2. ל-y יש 6 ספרות, ול-x יש 3, ולכן equals מחזירה False ולא מוחזר 2.
3. סכום הספרות של y הוא 2S. בדיקת is_same:
, וגם → True.
לכן `mystery(x, 1001*x)` מחזירה 3 לכל x תלת-ספרתי. למשל `mystery(100, 100100)`: ו-, ומוחזר 3.
תשובה: לא קיים x כזה – לכל x תלת-ספרתי, עבור (ממוצע ספרות זהה ומספר ספרות שונה) הפעולה מחזירה 3.
סעיף ב
הזימון מחזיר False (pos1 = 5, pos2 = 2).
לכל איבר נחשב num1 (מספר הספרות) ו-num2 (סכום הספרות של הערך המוחלט). temp1 שומר את העצם עם הכי הרבה ספרות עד כה, ו-temp2 את העצם עם סכום הספרות הגדול ביותר עד כה (רק כשהערך גדול ממש מתבצע עדכון).
התחלה: `arr[0] = 3458`: num1 = 4, num2 = ; temp1 = temp2 = (4, 20), pos1 = pos2 = 0.
הסבר לשורות המעניינות:
•: ל-7681 יש 4 ספרות, לא יותר מ-4, ולכן temp1 לא משתנה; סכום הספרות , ולכן pos2 = 2.
•: ל-13571 יש 5 ספרות, , ולכן pos1 = 5; סכום ספרותיו .
בסוף .
תשובה: `secret(arr)` מחזירה False.
סעיף ג
בודקת אם המספר עם הכי הרבה ספרות ברשימה הוא גם המספר עם סכום הספרות הגדול ביותר (המופע הראשון של כל מקסימום, לפי ערך מוחלט).
pos1 הוא המקום של המספר הראשון ברשימה שיש לו מספר ספרות מקסימלי, ו-pos2 הוא המקום של המספר הראשון שסכום ספרותיו (של הערך המוחלט) מקסימלי. העדכון נעשה רק בגדול ממש, ולכן בשוויון נשאר המופע הראשון. הפעולה מחזירה True אם שני המקומות זהים.
תשובה: הפעולה מחזירה True אם המספר הראשון ברשימה בעל מספר הספרות הגדול ביותר הוא גם המספר הראשון בעל סכום הספרות הגדול ביותר (בהתעלם מהסימן), ו-False אחרת.
שאלה 12 · מספרים, רשימות ורשימת רשימות סופר זוגיות
נתונות הגדרות הבאות:
•מספר שלם וחיובי נקרא "מספר סופר זוגי" כל הספרות שלו זוגיות וגם כמות הספרות היא זוגית.
לדוגמה:
המספרים 22, 2684, 8204, 20 הם "מספרים סופר זוגיים".
המספרים 43, 1233, -22 , 442 הם לא "מספרים סופר זוגיים"
•רשימה של מספרים שלמים (חיוביים, שליליים ואפסים) נקראת "סופר זוגית" אם אורך הרשימה הוא זוגי, ויותר מחצי איברי הרשימה הם "מספרים סופר זוגיים".
•רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה) נקראת "סופר זוגית" אם מספר הרשימות שבה זוגי וכל הרשימות שלה הן מרשימות "סופר זוגיים".
כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה של מספרים שלמים) ובודקת אם היא " סופר זוגית".
אם כן – הפעולה תחזיר ערך True, ולא – הפעולה תחזיר ערך False.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
רמז: מומלץ לכתוב פעולות עזר!
◂ פתרון מלא לשאלה 12
סעיף א
שלוש פעולות: `is_super_even_number` (חיובי, כל הספרות זוגיות, מספר ספרות זוגי), `is_super_even_list` (אורך זוגי ויותר מחצי האיברים סופר זוגיים), `is_super_even_lists` (מספר רשימות זוגי וכל רשימה סופר זוגית).
הרעיון: שלוש ההגדרות בנויות זו על זו, ולכן נכתוב פעולת עזר לכל רמה.
1. `is_super_even_number(num)` – מחזירה True אם num "מספר סופר זוגי".
•מספר שאינו חיובי (0 או שלילי, כמו -22) אינו סופר זוגי לפי ההגדרה.
•עוברים על הספרות בעזרת `% 10` ו-`// 10`: אם יש ספרה אי-זוגית מחזירים False מיד, ובמקביל סופרים את הספרות.
•בסוף מחזירים True רק אם מספר הספרות זוגי.
2. `is_super_even_list(arr)` – מחזירה True אם הרשימה "סופר זוגית".
•אם האורך אי-זוגי – False.
•סופרים כמה איברים הם מספרים סופר זוגיים (בעזרת פעולה 1), ומחזירים True אם הכמות גדולה ממש מחצי האורך (`count > len(arr) / 2`).
3. `is_super_even_lists(lst)` – הפעולה המבוקשת.
•אם מספר הרשימות אי-זוגי – False.
•אם אחת הרשימות אינה סופר זוגית (פעולה 2) – False מיד.
•אחרת – True.
def is_super_even_number(num):
if num <= 0:
return False
count = 0
while num > 0:
if (num % 10) % 2 != 0:
return False
count = count + 1
num = num // 10
return count % 2 == 0
def is_super_even_list(arr):
if len(arr) % 2 != 0:
return False
count = 0
for x in arr:
if is_super_even_number(x):
count = count + 1
return count > len(arr) / 2
def is_super_even_lists(lst):
if len(lst) % 2 != 0:
return False
for arr in lst:
if not is_super_even_list(arr):
return False
return True- 2684: הספרות 4, 8, 6, 2 זוגיות ויש 4 ספרות → True. 442: כל הספרות זוגיות אבל יש 3 ספרות → False. 20: הספרות 0 ו-2 זוגיות ויש 2 → True.
•`[[22, 3, 20, 46], [88, 64]]`: ברשימה הראשונה 3 מתוך 4 סופר זוגיים (), בשנייה 2 מתוך 2 (), ויש 2 רשימות → True.
•`[[22, 3, 20, 46], [88, 5]]`: ברשימה השנייה רק 1 מתוך 2, ו-1 אינו גדול מ-1 → False.
תשובה: הפעולה `is_super_even_lists` שלמעלה (עם שתי פעולות העזר).
סעיף ב
, ובמספרים בגודל חסום – ליניארית במספר האיברים הכולל.
נסמן: m – מספר הרשימות, n – האורך המקסימלי של רשימה, d – מספר הספרות המקסימלי של מספר.
1. `is_super_even_number`: לולאה על הספרות – .
2. `is_super_even_list`: מזמנת את פעולה 1 לכל אחד מ-n האיברים – .
3. `is_super_even_lists`: מזמנת את פעולה 2 לכל אחת מ-m הרשימות – .
מכיוון שמספר הספרות של מספר שלם (בגודל חסום) הוא קבוע קטן, נהוג לכתוב : כל איבר בכל הרשימות נבדק פעם אחת, כלומר הסיבוכיות ליניארית במספר האיברים הכולל. (במקרה הטוב, כשמספר הרשימות אי-זוגי, מוחזר False מיד – .)
תשובה: , ובמספרים בגודל חסום .
שאלה 13 · רשת מכללות: מחלקות, חיפוש ופתיחת מגמה
ברשת מכללות "דרך למקצוע" קיימות 80 מכללות. ברשת הוחלט למחשב את מאגר המידע כדי לעזור לרוצים ללמוד לבחור את המכללה המתאימה ביותר לצרכים שלהם.
לכל מכללה שמורים הפרטים הבאים:
•שם מכללה.
•יישוב שבו נמצא קמפוס לימודי של המכללה.
•רשימת המגמות הנלמדות במכללה. בכל מכללה יש לכל היותר 10 מגמות שונות.
כל מגמה מזוהה ע"י מספר המקצוע (code) ושם המגמה (major_name).
כתבו את כותרת המחלקה ואת התכונות עבור כל אחת מהמחלקות
•מגמה Major
•מכללה College
•רשת מכללות Network
כתבו פעולה פנימית במחלקה Network המקבלת שם יישוב ומדפיסה את שמותיהן של כל המכללות אשר נמצאות ביישוב זה. אם ביישוב אין אף מכללה של הרשת,
יש להדפיס הודעה מתאימה.
הנהלת הרשת בודקת אפשרות לפתוח מגמה חדשה. כתבו פעולה פנימית במחלקה Network המקבלת קוד של המגמה ומחזירה רשימת שמות של המכללות שבהן אפשר לפתוח את המגמה.
אם אין אף מכללה שבה אפשר לפתוח את המגמה יש להחזיר רשימה ריקה.
שימו לב שאי אפשר לפתוח מגמה אם היא כבר קיימת במכללה או שבמכללה יש כבר 10 מגמות שונות.
הערה: אם כתבתם פעולות עזר – עליכם לציין באיזו מחלקה הן נמצאות וגם להגדיר את טענות הכניסה והיציאה לכל פעולה (הפרמטרים של הפעולה והמטרה שלה).
◂ פתרון מלא לשאלה 13
סעיף א
Major: code, major_name. College: name, city, majors (רשימת Major, עד 10). Network: colleges (רשימת College, 80 מכללות).
הרעיון: כל רמה מכילה רשימה של עצמים מהרמה שמתחתיה: הרשת מכילה רשימת מכללות, ומכללה מכילה רשימת מגמות.
1. Major – מגמה: מספר המקצוע `code` (שלם) ושם המגמה `major_name` (מחרוזת).
2. College – מכללה: שם `name`, היישוב של הקמפוס `city`, ורשימת המגמות `majors` – רשימה של עצמים מטיפוס Major, לכל היותר 10.
3. Network – רשת: רשימת המכללות `colleges` – רשימה של עצמים מטיפוס College (80 מכללות).
class Major:
def __init__(self, code, major_name):
self.code = code # int
self.major_name = major_name # str
class College:
def __init__(self, name, city):
self.name = name # str
self.city = city # str
self.majors = [] # list of Major, at most 10
class Network:
def __init__(self):
self.colleges = [] # list of College, 80 collegesתשובה: המחלקות והתכונות שלמעלה.
סעיף ב
עוברים על `self.colleges`, מדפיסים `c.name` כאשר `c.city == city`, ומשתמשים בדגל found כדי להדפיס הודעה אם לא נמצאה אף מכללה.
הרעיון: עוברים על כל המכללות ברשת. לכל מכללה שהיישוב שלה שווה ליישוב שהתקבל – מדפיסים את שמה ומסמנים בדגל found שנמצאה לפחות מכללה אחת. אחרי הלולאה, אם הדגל נשאר False – מדפיסים הודעה שאין מכללה של הרשת ביישוב.
טענת כניסה: city – שם יישוב (מחרוזת). טענת יציאה: הדפסת שמות המכללות ביישוב, או הודעה מתאימה.
class Network:
...
def print_colleges_in_city(self, city):
found = False
for c in self.colleges:
if c.city == city:
print(c.name)
found = True
if not found:
print("There is no college of the network in", city)דוגמה: אם ברשת המכללות Ort (Haifa), Amal (Haifa), Shenkar (Ramat Gan), הזימון עם "Haifa" מדפיס Ort ו-Amal, והזימון עם "Eilat" מדפיס את ההודעה.
תשובה: הפעולה שלמעלה.
סעיף ג
פעולת עזר `has_major(code)` במחלקה College; ב-Network מחזירים את שמות המכללות שבהן `len(c.majors) < 10` וגם `not c.has_major(code)`.
הרעיון: אפשר לפתוח את המגמה במכללה אם שני תנאים מתקיימים: יש בה פחות מ-10 מגמות, והמגמה עם הקוד הזה עוד לא קיימת בה.
1. פעולת עזר במחלקה College – `has_major(self, code)`:
טענת כניסה: code – קוד מגמה (מספר שלם). טענת יציאה: מחזירה True אם במכללה יש מגמה עם הקוד code, אחרת False.
עוברת על רשימת המגמות של המכללה ומשווה את הקוד של כל מגמה ל-code.
2. הפעולה ב-Network – `can_open_major(self, code)`:
טענת כניסה: code – קוד המגמה החדשה. טענת יציאה: רשימת שמות המכללות שבהן אפשר לפתוח את המגמה (רשימה ריקה אם אין).
מתחילים מרשימה ריקה, עוברים על המכללות, ומוסיפים את שם המכללה אם `len(c.majors) < 10` וגם `not c.has_major(code)`.
class College:
...
def has_major(self, code):
for m in self.majors:
if m.code == code:
return True
return False
class Network:
...
def can_open_major(self, code):
result = []
for c in self.colleges:
if len(c.majors) < 10 and not c.has_major(code):
result.append(c.name)
return resultדוגמה: אם ל-Ort יש 10 מגמות, ל-Amal יש רק את המגמה עם הקוד 5, ול-Shenkar אין מגמות, אז עבור הקוד 5 מוחזר `['Shenkar']` (ב-Ort אין מקום וב-Amal המגמה קיימת), ועבור הקוד 77 מוחזר `['Amal', 'Shenkar']`.
תשובה: הפעולה `can_open_major` ופעולת העזר `has_major` שלמעלה.
שאלה 14 · רקורסיה: הפרשים בין איברים סמוכים
נתונה הפעולה what המקבלת רשימה של מספרים שלמים, ושני מספרים נוספים:
def what(arr, begin, end):
if begin < end:
what(arr, begin + 1, end)
arr[begin] = arr[begin] - arr[begin + 1]עקבו אחר זימון `what(brr, 0, len(brr) -1)` עבור הרשימה:
וציינו מה יהיה תוכן הרשימה בסיום ביצוע פעולה.
מהי מטרת הפעולה what? בתשובה יש להתייחס לרשימה שהפעולה מקבלת כפרמטר.
נתונה פעולה אחרת where המקבלת רשימה של מספרים שלמים, ושני מספרים נוספים.
def where(arr, begin, end):
if begin < end:
arr[begin] = arr[begin] - arr[begin + 1]
where(arr, begin + 1, end)אחרי זימון `where(crr, 0, len(crr)-1)` תוכן של רשימה crr הוא:
מה היה התוכן של crr לפני ביצוע הזימון?
מהי מטרת הפעולה where? בתשובה יש להתייחס לרשימה שהפעולה מקבלת כפרמטר.
◂ פתרון מלא לשאלה 14
סעיף א
`[-1, 16, -11, 14, 2, 8]`
`len(brr) = 6`, ולכן הזימון הוא `what(brr, 0, 5)`. בכל זימון שבו מתבצעת קודם הקריאה הרקורסיבית ורק אחריה ההשמה. לכן הקריאות יורדות עד `what(brr, 5, 5)` (שבה לא מתקיים והיא חוזרת מיד), וההשמות מתבצעות בדרך חזרה – מהסוף להתחלה. בכל השמה `arr[begin + 1]` הוא כבר הערך החדש של התא הבא.
ירידה: what(0,5) → what(1,5) → what(2,5) → what(3,5) → what(4,5) → what(5,5) (עצירה).
תשובה: `[-1, 16, -11, 14, 2, 8]`
מחליפה כל איבר בקטע begin..end-1 בהפרש בינו לבין האיבר שאחריו אחרי שזה כבר עודכן, מהסוף להתחלה; התא end לא משתנה. התוצאה: `arr[i]` שווה לסכום המתחלף של המקור מ-i עד end.
הפעולה עוברת (בדרך החזרה מהרקורסיה) על התאים מ- עד begin, מהסוף להתחלה, ומחליפה כל תא בהפרש בין ערכו לבין הערך המעודכן של התא שאחריו. התא end וכל התאים מחוץ לקטע לא משתנים.
בגלל שההפרש מחושב מול ערך שכבר עודכן, כל תא מקבל בסוף סכום מתחלף של האיברים המקוריים מהמקום שלו עד end:
למשל בסעיף 1: .
תשובה: what משנה את הרשימה במקום: כל איבר מהמקום begin עד end-1 מוחלף בהפרש בינו לבין האיבר שאחריו לאחר שזה כבר עודכן (החישוב מתבצע מהסוף להתחלה), כך שכל איבר הופך לסכום המתחלף של האיברים המקוריים ממנו ועד end; האיבר במקום end נשאר.
סעיף ב
`[6, 5, 7, 8, 10, 3]`
הבנת where: כאן ההשמה מתבצעת לפני הקריאה הרקורסיבית, ולכן התאים מעודכנים מההתחלה לסוף, ובכל השמה `arr[begin + 1]` הוא עדיין הערך המקורי של התא הבא (הוא יעודכן רק בקריאה הבאה). לכן עבור הרשימה המקורית :
עבור , והתא האחרון לא משתנה: .
שחזור מהסוף להתחלה: .
בדיקה: הפעלת where על `[6, 5, 7, 8, 10, 3]`: , , , , , והתא האחרון 3 – מתקבל `[1, -2, -1, -2, 7, 3]` כנדרש.
תשובה: לפני הזימון: `[6, 5, 7, 8, 10, 3]`
מחליפה כל איבר מ-begin עד end-1 בהפרש בינו לבין האיבר המקורי שאחריו (מההתחלה לסוף); התא end לא משתנה.
הפעולה עוברת על הרשימה מהמקום begin לכיוון end. בכל שלב היא מחליפה את `arr[begin]` בהפרש בינו לבין האיבר הבא, ורק אחר כך ממשיכה לאיבר הבא. מכיוון שהאיבר הבא עוד לא שונה, ההפרש הוא בין שני ערכים מקוריים סמוכים. האיבר במקום end (האחרון בקטע) לא משתנה.
ההבדל מ-what: שם ההשמה באה אחרי הקריאה הרקורסיבית, ולכן העדכון נעשה מהסוף להתחלה ומול ערכים שכבר עודכנו.
תשובה: where משנה את הרשימה במקום: כל איבר מהמקום begin עד end-1 מוחלף בהפרש בינו לבין האיבר המקורי שאחריו (), והאיבר במקום end נשאר כפי שהוא.