מבחן מה"ט אלגוריתמיקה ותכנות (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 · מספרים אקראיים: מינימום וסכום ספרות
כתבו קטע תוכנית המייצר 50 מספרים שלמים אקראיים חיוביים תלת ספרתיים.
על התוכנית להדפיס את המספר הקטן ביותר שנוצר ואת סכום ספרותיו.
◂ פתרון מלא לשאלה 1
פתרון
לולאה של 50 הגרלות `random.randint(100, 999)` ששומרת את הקטן ביותר, ואחריה לולאת `% 10` / `// 10` שסוכמת את ספרותיו; מדפיסים את המספר ואת הסכום.
מבוקש: לייצר 50 מספרים אקראיים תלת ספרתיים, למצוא את הקטן מהם ולהדפיס אותו ואת סכום ספרותיו.
רעיון הפתרון:
1. מספר שלם חיובי תלת ספרתי הוא מספר בין 100 ל-999 (כולל), ולכן כל מספר נוצר בעזרת `random.randint(100, 999)`.
2. מציאת הקטן ביותר: מחזיקים משתנה `min_num` עם הערך הקטן ביותר שנמצא עד כה. מאתחלים אותו ל-1000, שגדול מכל מספר תלת ספרתי, כך שכבר המספר הראשון שנוצר יחליף אותו. כל מספר חדש שקטן מ-`min_num` מחליף אותו. אין צורך לשמור את כל 50 המספרים ברשימה.
3. סכום הספרות: אחרי הלולאה מפרקים את `min_num` לספרות. בכל סיבוב `temp % 10` היא ספרת האחדות, מוסיפים אותה לסכום, ו-`temp // 10` מוחק אותה. כשהמספר מגיע ל-0 עברנו על כל הספרות.
4. מדפיסים את המספר הקטן ואת סכום ספרותיו.
import random
min_num = 1000 # גדול מכל מספר תלת ספרתי
for i in range(50):
num = random.randint(100, 999) # מספר תלת ספרתי חיובי
if num < min_num:
min_num = num
total = 0
temp = min_num
while temp > 0:
total = total + temp % 10 # הספרה הימנית
temp = temp // 10 # הסרת הספרה הימנית
print("smallest:", min_num)
print("sum of digits:", total)לדוגמה, אם הקטן ביותר שנוצר הוא 102, יודפסו 102 ו-3 ().
הלולאה הראשית מבצעת 50 סיבובים קבועים, ולולאת הספרות 3 סיבובים בלבד.
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · קליטת מחרוזות עד תנאי עצירה, ספירת תווים
כתבו קטע תוכנית הקולטת מחרוזות עד שתיקלט מחרוזת שהתו האחרון שלה זהה לתו הראשון שלה.
עבור כל מחרוזת יש להדפיס כמה פעמים מופיעה בה האות 'A'.
נוסף על כך יש לחשב ולהדפיס מספר מחרוזות באורך זוגי.
◂ פתרון מלא לשאלה 2
פתרון
לולאה שקולטת מחרוזת, סופרת ומדפיסה את מספר ה-'A' בה, מגדילה מונה אם אורכה זוגי, ועוצרת אחרי מחרוזת שבה `s[0] == s[-1]`; בסוף מדפיסים את המונה.
מבוקש: לקלוט מחרוזות עד מחרוזת שהתו הראשון והאחרון שלה זהים; לכל מחרוזת להדפיס את מספר המופעים של 'A', ובסוף להדפיס כמה מחרוזות היו באורך זוגי.
רעיון הפתרון:
1. לא ידוע מראש כמה מחרוזות ייקלטו, ולכן משתמשים בלולאת `while` עם דגל `stop`.
2. לכל מחרוזת: עוברים על התווים ומונים את התווים השווים ל-'A' (האות הגדולה בלבד), ומדפיסים את המונה.
3. אם `len(s) % 2 == 0` המחרוזת באורך זוגי, ומגדילים את המונה `even_count`.
4. תנאי העצירה: `s[0] == s[-1]` (התו הראשון שווה לתו האחרון). בודקים קודם ש-`len(s) > 0`, כדי שמחרוזת ריקה לא תגרום לשגיאה. המחרוזת שעוצרת את הקלט היא גם מחרוזת שנקלטה, ולכן גם היא נספרת ומודפס עבורה מספר ה-'A'.
5. אחרי הלולאה מדפיסים את `even_count`.
even_count = 0
stop = False
while not stop:
s = input()
count_a = 0
for ch in s:
if ch == 'A':
count_a = count_a + 1
print(count_a)
if len(s) % 2 == 0:
even_count = even_count + 1
if len(s) > 0 and s[0] == s[-1]:
stop = True
print("even length strings:", even_count)דוגמת הרצה: עבור הקלט `ABA1`, `xAAy`, `hello`, `AbcA` יודפסו 2, 2, 0, 2 (מספר ה-'A' בכל מחרוזת), הקלט נעצר אחרי `AbcA` (מתחילה ומסתיימת ב-'A'), ובסוף יודפס 3: שלוש מחרוזות באורך 4 ומחרוזת אחת באורך 5.
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · רשימה מאוזנת: בדיקה ומילוי אקראי
רשימה של מספרים שלמים נקראת "רשימה מאוזנת" אם סכום של כל הערכים הנמצאים במקומות הזוגיים שווה לסכום של כל הערכים הנמצאים במקומות האי-זוגיים.
הרשימה `arr=[12, 3, 7, 15, 5, 12, 6]` היא רשימה "מאוזנת":
כתבו פעולה המקבלת רשימה של מספרים שלמים `arr`. הפעולה תחזיר ערך `true`, אם הרשימה "מאוזנת", ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
is_balanced(arr)כתבו פעולה המקבלת מספר שלם וחיובי `size>2` ושני פרמטרים נוספים `x` ו- `y`, מטיפוס מספר שלם.
הפעולה תיצור רשימה בגודל `size` ותמלא אותה במספרים אקראיים בין `x` ל- `y` (כולל) כך שהרשימה תהיה מאוזנת. הפעולה תחזיר את הרשימה.
כותרת הפעולה:
fill_return(int size, int x, int y)◂ פתרון מלא לשאלה 3
סעיף א
סוכמים בנפרד את הערכים במקומות הזוגיים והאי-זוגיים ומחזירים `sum_even == sum_odd`.
מבוקש: לבדוק אם סכום הערכים באינדקסים הזוגיים שווה לסכום הערכים באינדקסים האי-זוגיים.
רעיון הפתרון:
1. עוברים על כל האינדקסים `i` של הרשימה.
2. אם `i % 2 == 0` מוסיפים את `arr[i]` ל-`sum_even`, אחרת ל-`sum_odd`.
3. מחזירים את תוצאת ההשוואה `sum_even == sum_odd` (ב-Python הערכים הבוליאניים הם `True` ו-`False`).
def is_balanced(arr):
sum_even = 0
sum_odd = 0
for i in range(len(arr)):
if i % 2 == 0:
sum_even = sum_even + arr[i]
else:
sum_odd = sum_odd + arr[i]
return sum_even == sum_oddבדיקה על הדוגמה: מקומות זוגיים , מקומות אי-זוגיים , הסכומים שווים ולכן מוחזר `True`.
סיבוכיות: מעבר אחד על הרשימה, .
תשובה: הפעולה `is_balanced` שלמעלה.
סעיף ב
ממלאים באקראי את כל התאים חוץ מהאחרון, מחשבים את הערך שמאזן את הרשימה בתא האחרון; אם הוא בטווח `[x, y]` מציבים ומחזירים, אחרת מגרילים מחדש.
מבוקש: רשימה בגודל `size` עם ערכים אקראיים בטווח שהיא מאוזנת.
רעיון הפתרון:
1. ממלאים באקראי את התאים 0 עד `size-2` ובאותה לולאה סוכמים את המקומות הזוגיים (`sum_even`) ואת האי-זוגיים (`sum_odd`).
2. את התא האחרון (אינדקס `size-1`) לא מגרילים אלא מחשבים, כך שהרשימה תהיה מאוזנת:
•אם `size-1` זוגי, התא האחרון שייך לסכום הזוגי, וצריך , כלומר .
•אם `size-1` אי-זוגי, צריך , כלומר .
3. הערך המשלים חייב להיות בטווח `x` עד `y`. אם הוא בטווח, מציבים אותו ומחזירים את הרשימה; אם לא, חוזרים על ההגרלה מההתחלה (לולאת `while True`).
import random
def fill_return(size, x, y):
arr = [0] * size
while True:
sum_even = 0
sum_odd = 0
for i in range(size - 1): # כל התאים חוץ מהאחרון
arr[i] = random.randint(x, y)
if i % 2 == 0:
sum_even = sum_even + arr[i]
else:
sum_odd = sum_odd + arr[i]
if (size - 1) % 2 == 0: # התא האחרון במקום זוגי
last = sum_odd - sum_even
else: # התא האחרון במקום אי-זוגי
last = sum_even - sum_odd
if x <= last <= y: # הערך המשלים בטווח
arr[size - 1] = last
return arrהערה: כש-`size` זוגי תמיד קיימת רשימה מאוזנת (למשל זוגות של ערכים שווים), ולכן הלולאה מסתיימת. כש-`size` אי-זוגי ייתכן שאין פתרון בכלל: למשל `size=3`, `x=5`, `y=6` דורש , אבל . במקרה כזה אף פעולה לא יכולה למלא את הדרישה, ולכן מניחים שהנתונים מאפשרים רשימה מאוזנת.
ניתן גם לוודא את התוצאה בעזרת `is_balanced` מסעיף א: הרשימה המוחזרת תמיד מקיימת אותה.
תשובה: הפעולה `fill_return` שלמעלה.
שאלה 4 · מכירות נעליים לפי מחלקות: מונים ברשימה
במפעל נעליים יש ארבע מחלקות ייצור:
•מחלקה 1 – נעלי נשים
•מחלקה 2 – נעלי גברים
•מחלקה 3 – נעלי ילדים
•מחלקה 4 – נעלי ספורט
לכל סוג נעליים קיים בקטלוג מספר המורכב משלוש ספרות. ספרת המאות מציינת את קוד המחלקה (1-4), שתי הספרות האחרות מציינות את קוד המוצר.
לדוגמה: המספר 321 בקטלוג מציין נעל ילדים אשר קוד המוצר שלה הוא 21.
כתבו תוכנית הקולטת רשימה של מספרים קטלוגיים של נעלים אשר נמכרו בחודש האחרון. עבור כל מספר קטלוג ייקלט גם מספר זוגות הנעליים של אותו הקוד. הקלט מסתיים כאשר ייקלט 0 בתור מספר הקטלוג.
על התוכנית להדפיס את מספר זוגות הנעלים שמכרה כל מחלקה במשך החודש ואת מספר זוגות הנעלים שמכר המפעל.
◂ פתרון מלא לשאלה 4
פתרון
רשימת מונים `sales` לפי מחלקה; לכל מספר קטלוג (עד 0) קולטים את מספר הזוגות ומוסיפים ל-`sales[catalog // 100]`; בסוף מדפיסים את ארבעת המונים ואת סכומם.
מבוקש: לסכם את מספר זוגות הנעליים שנמכרו בכל אחת מארבע המחלקות ובמפעל כולו.
רעיון הפתרון:
1. קוד המחלקה הוא ספרת המאות של מספר הקטלוג, כלומר `catalog // 100` (למשל ).
2. מחזיקים רשימת מונים `sales` בגודל 5, ומשתמשים בתאים 1 עד 4 כך שהאינדקס הוא קוד המחלקה עצמו (תא 0 לא בשימוש). כך אין צורך בשרשרת של `if`.
3. לולאת זקיף: קולטים מספר קטלוג לפני הלולאה; כל עוד הוא שונה מ-0 קולטים את מספר הזוגות, מוסיפים אותו למונה של המחלקה, וקולטים את מספר הקטלוג הבא. כשנקלט 0 הלולאה נגמרת, ולא נקלט עבורו מספר זוגות.
4. בסוף מדפיסים את המונה של כל מחלקה, ותוך כדי סוכמים אותם לסך המכירות של המפעל.
sales = [0] * 5 # sales[1] .. sales[4] - זוגות לכל מחלקה
catalog = int(input())
while catalog != 0:
pairs = int(input())
dept = catalog // 100 # ספרת המאות = קוד המחלקה
sales[dept] = sales[dept] + pairs
catalog = int(input())
total = 0
for dept in range(1, 5):
print("department", dept, ":", sales[dept])
total = total + sales[dept]
print("factory total:", total)דוגמת הרצה: הקלט 321, 5, 110, 2, 421, 3, 305, 1, 0 (מספר קטלוג ואחריו מספר זוגות) נותן: מחלקה 1: 2, מחלקה 2: 0, מחלקה 3: , מחלקה 4: 3, וסך הכול במפעל זוגות.
תשובה: התוכנית שלמעלה.
שאלה 5 · מעקב: ממוצע ספרות ומציאת האיבר המרבי
נתונה הפעולה `one` המקבלת כפרמטר מספר שלם וחיובי `num`.
def one(num):
x = 0
y = 0
while num > 0:
x = x + num % 10
y = y + 1
num = num // 10
return x/yמה תחזיר הפעולה עבור `num=12345`? עקבו באמצעות טבלת מעקב אחר זימון הפעולה `one(12345)`.
מה מבצעת הפעולה עבור מספר `num` שלם וחיובי כלשהו?
נתונה הפעולה `two` המקבלת רשימה של מספרים שלמים חיוביים:
def two (arr):
res = 0
for i in range(1,len(arr)):
if one(arr[i]) > one (arr[res]):
res = i
print (arr[res])נתונה רשימה של מספרים שלמים וחיוביים `arr` הבאה:
arr = [24, 34783,1245, 68, 468, 95]עקבו באמצעות טבלת מעקב אחר ביצוע זימון הפעולה `two (arr)` ורשמו מה יהיה הפלט.
הסבירו מה תבצע הפעולה `two(arr)` עבור רשימה כלשהי של מספרים שלמים וחיוביים.
◂ פתרון מלא לשאלה 5
סעיף א
3.0
עוקבים אחרי הלולאה: בכל סיבוב `num % 10` היא ספרת האחדות, שמתווספת ל-`x`; `y` סופר את הסיבובים; `num // 10` מוחק את ספרת האחדות.
כש-`num` מגיע ל-0 הלולאה נעצרת, והפעולה מחזירה (האופרטור `/` ב-Python מחזיר מספר ממשי).
תשובה: `one(12345)` מחזירה 3.0.
מחזירה את ממוצע הספרות של `num`.
בסוף הלולאה `x` הוא סכום הספרות של `num` (כל סיבוב מוסיף ספרה אחת), ו-`y` הוא מספר הספרות (סיבוב אחד לכל ספרה). המנה היא סכום הספרות חלקי מספרן.
תשובה: הפעולה מחזירה את ממוצע הספרות של `num`.
סעיף ב
הפלט: 68
לפי סעיף א, `one` מחזירה את ממוצע הספרות. נחשב אותו לכל איבר:
- 24:
- 34783:
- 1245:
- 68:
- 468:
- 95:
`res` מתחיל ב-0 (האיבר 24). בכל סיבוב משווים את ממוצע האיבר `arr[i]` לממוצע האיבר `arr[res]`, ומעדכנים את `res` רק אם הממוצע החדש גדול ממש:
בסוף הלולאה `res = 3`, ומודפס `arr[3]`.
תשובה: הפלט הוא 68.
מדפיסה את האיבר שממוצע ספרותיו הגדול ביותר; בשוויון - את הראשון מביניהם (השמאלי).
`res` שומר את האינדקס של האיבר בעל ממוצע הספרות הגדול ביותר שנמצא עד כה, וזה אלגוריתם רגיל של חיפוש מקסימום, כשהמפתח הוא `one` (ממוצע הספרות). מכיוון שההשוואה היא `>` ולא `>=`, איבר עם ממוצע שווה למקסימום הנוכחי לא מחליף אותו (כמו 95 בדוגמה, שממוצע ספרותיו 7.0 כמו של 68).
תשובה: הפעולה מדפיסה את האיבר ברשימה שממוצע ספרותיו הגדול ביותר; אם יש כמה כאלה - את הראשון מביניהם.
שאלה 6 · מעקב אחר פעולה על שתי מחרוזות
נתונה הפעולה `mystery` המקבלת שתי מחרוזות:
def mystery(s1, s2):
out1 = "";
out2 = "";
for i in range(len(s1)):
ch = s1[i]
pos = s2.find(ch)
if pos == -1:
if out1.find(ch) == -1:
out1 = out1 + ch
else:
if out2.find(ch) == -1:
out2 = out2 + ch
return out1 + out2נתונות שתי מחרוזות `s1="COMPUTERS"` ו- `s2="CANNOTTHINK"`
עקבו בעזרת טבלת מעקב אחרי זימון הפעלה `mystery(s1, s2)` ורשמו מה תחזיר הפעולה.
מה מבצעת הפעולה `mystery` באופן כללי?
האם קיימות שתי מחרוזות שונות `s1` ו-`s2` שעבורם זימונים `mystery(s1, s2)` ו- `mystery(s2, s1)` יחזירו אותה תוצאה? אם כן, הביאו דוגמה של זוג מחרוזות כאלה, ולא, הסבירו למה הדבר אינו אפשרי.
◂ פתרון מלא לשאלה 6
סעיף א
"MPUERSCOT"
עוברים על התווים של `s1` לפי הסדר. `pos` הוא המיקום של התו ב-`s2` (או 1- אם הוא לא מופיע בה). תו שלא נמצא ב-`s2` מצורף ל-`out1`, ותו שנמצא ב-`s2` מצורף ל-`out2`, בשני המקרים רק אם עוד לא הופיע שם.
התווים של `s2="CANNOTTHINK"` הם C, A, N, O, T, H, I, K.
הפעולה מחזירה את `out1 + out2`.
תשובה: `mystery(s1, s2)` מחזירה "MPUERSCOT".
סעיף ב
מחזירה את התווים של `s1` שאינם ב-`s2`, ואחריהם את התווים של `s1` שנמצאים גם ב-`s2`; כל תו פעם אחת, לפי סדר הופעתו הראשונה ב-`s1`.
`out1` אוסף את התווים של `s1` שלא מופיעים ב-`s2` (`pos == -1`), ו-`out2` את התווים של `s1` שכן מופיעים ב-`s2`. הבדיקה `out1.find(ch) == -1` (וכן ב-`out2`) מונעת כפילויות, ולכן כל תו נכנס פעם אחת, במקום של הופעתו הראשונה ב-`s1`. בסוף מוחזר השרשור: קודם הקבוצה הראשונה, אחריה השנייה.
תשובה: הפעולה מחזירה מחרוזת שבה מופיעים קודם כל התווים של `s1` שאינם נמצאים ב-`s2`, ואחריהם התווים של `s1` שנמצאים גם ב-`s2`; כל תו מופיע פעם אחת בלבד, לפי סדר הופעתו הראשונה ב-`s1`.
סעיף ג
כן. למשל `s1="ABA"`, `s2="AB"`: שני הזימונים מחזירים "AB".
לפי סעיף ב, אם כל תו של כל אחת מהמחרוזות מופיע גם בשנייה, אז `out1` ריק בשני הזימונים, והתוצאה היא רק התווים השונים לפי סדר הופעתם הראשונה. מספיק לבחור שתי מחרוזות שונות עם אותם תווים ובאותו סדר הופעה ראשונה.
דוגמה: `s1="ABA"`, `s2="AB"` (המחרוזות שונות).
1. `mystery("ABA", "AB")`: התווים A, B, A כולם נמצאים ב-"AB", לכן `out1=""` ו-`out2="AB"` (ה-A השני לא מתווסף שוב). מוחזר "AB".
2. `mystery("AB", "ABA")`: התווים A, B נמצאים ב-"ABA", לכן `out1=""` ו-`out2="AB"`. מוחזר "AB".
תשובה: כן. לדוגמה `s1="ABA"` ו-`s2="AB"`: שני הזימונים מחזירים "AB".
שאלה 7 · מחלקת צעצוע: יצירת עצם ומעקב תנאים
נתונה המחלקה צעצוע `Toy` שיש לה ארבע תכונות:
•קוד צעצוע – `code`, מטיפוס שלם, `int`
•גיל מינימלי – `age`, מטיפוס שלם, `int`
•מחיר – `price`, מטיפוס ממשי, `double`
•האם אפשר להזמין באינטרנט? – `is_possible`, מטיפוס בוליאני, `bool` (`True` – אם אפשר להזמין, `False` – אם אי אפשר להזמין)
במחלקה הוגדרה פעולה הבונה (בנאי, `constructor`)
def __init__(self, code, age, price,is_possible):
self.code = code
self.age = age
self.price = price
self.is_possible = is_possibleכתבו פעולה המקבלת את קוד הצעצוע ואת מחירו. הפעולה תיצור ותחזיר עצם חדש עם גיל מינימלי עשר שאי אפשר להזמין אותו באינטרנט.
כותרת הפעולה:
special_toy(code, price)לפניכם קטע קוד בפעולה הראשית `main()`. עקבו בעזרת טבלת המעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט:
t1 = Toy(1122, 10,120, True)
t2 = special_toy(2233, 55)
# (*) כאן יש להוסיף פקודה/פקודות בסעיף ג'
if t1.age > 6 and not t1.is_possible:
print("1")
else:
print("2")
if t2.price < 100:
print("3")
else:
if not t2.is_possible:
print("4")השלימו בקוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה "1" בלבד.
◂ פתרון מלא לשאלה 7
סעיף א
`return Toy(code, 10, price, False)`
מבוקש: פעולה חיצונית (לא של המחלקה, כי בכותרת אין `self`) שיוצרת צעצוע עם הקוד והמחיר שהתקבלו, גיל מינימלי 10, ואי אפשר להזמין אותו באינטרנט.
מזמנים את הבנאי עם הערכים האלה: `age=10` ו-`is_possible=False`, ומחזירים את העצם החדש.
def special_toy(code, price):
return Toy(code, 10, price, False)תשובה: הפעולה `special_toy` שלמעלה.
סעיף ב
הפלט: 2 ואחריו 3 (בשתי שורות).
1. העצמים שנוצרים:
את `t2` יוצרת `special_toy` מסעיף א, ולכן הגיל שלו 10 ואי אפשר להזמין אותו באינטרנט.
2. מעקב אחרי התנאים:
תשובה: הפלט הוא 2 ואחריו 3, כל אחד בשורה נפרדת.
סעיף ג
`t1.is_possible = False`, `t2.price = 100`, `t2.is_possible = True`
מבוקש: שהתנאי הראשון יתקיים, ושבחלק השני לא יודפס דבר.
1. כדי שיודפס "1": צריך `t1.age > 6` (כבר מתקיים, 10) וגם `not t1.is_possible`, כלומר `t1.is_possible` צריך להיות `False`.
2. כדי שלא יודפס "3": צריך `t2.price < 100` להיות שקר, כלומר מחיר של 100 לפחות.
3. אז מגיעים ל-`else`, וכדי שלא יודפס "4" צריך `not t2.is_possible` להיות שקר, כלומר `t2.is_possible` צריך להיות `True`.
מוסיפים במקום (*):
t1.is_possible = False
t2.price = 100
t2.is_possible = Trueבדיקה: `10 > 6 and not False` אמת, יודפס "1"; `100 < 100` שקר, נכנסים ל-`else`; `not True` שקר, לא מודפס דבר.
תשובה: הפקודות `t1.is_possible = False`, `t2.price = 100`, `t2.is_possible = True`.
שאלה 8 · מספרים זרים: ספרות משותפות וסיבוכיות
כתבו פעולה המקבלת מספר שלם וחיובי `num` וספרה `digit`. הפעולה תבדוק אם הספרה נמצאת בתוך מספר. אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
exist(num, digit)שני מספרים שלמים וחיוביים נקראים "זרים" אם אין להם אף ספרה משותפת אחת.
כתבו פעולה המקבלת שני מספרים שלמים וחיוביים. הפעולה תבדוק אם הם "זרים". אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_strangers(num1, num2)רשימה של מספרים שלמים וחיוביים נקראת "רשימת זרים" אם כל איברי הרשימה "זרים" זה לזה.
כתבו פעולה המקבלת רשימה של מספרים שלמים וחיוביים ובודקת אם היא "רשימת זרים". אם כן הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_it_strangers(arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו- ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
עוברים על ספרות `num` (`% 10`, `// 10`); אם ספרה שווה ל-`digit` מחזירים `True`, ובסוף `False`.
רעיון: מפרקים את `num` לספרות מימין לשמאל. `num % 10` היא ספרת האחדות; אם היא שווה ל-`digit` הספרה נמצאה ומחזירים `True` מיד. אחרת מוחקים אותה (`num // 10`) וממשיכים. אם המספר התאפס ולא מצאנו - מחזירים `False`.
def exist(num, digit):
while num > 0:
if num % 10 == digit:
return True
num = num // 10
return Falseלדוגמה `exist(1234, 3)` מחזירה `True` ו-`exist(1234, 5)` מחזירה `False`.
תשובה: הפעולה `exist` שלמעלה.
סעיף ב
לכל ספרה של `num1` בודקים `exist(num2, digit)`; אם נמצאה ספרה משותפת מחזירים `False`, אחרת `True`.
רעיון: המספרים זרים אם אף ספרה של `num1` לא נמצאת ב-`num2`. עוברים על הספרות של `num1`, ולכל אחת משתמשים בפעולה `exist` מסעיף א. ברגע שנמצאת ספרה משותפת מחזירים `False`; אם עברנו על כל הספרות - מחזירים `True`.
def is_strangers(num1, num2):
while num1 > 0:
if exist(num2, num1 % 10): # ספרה של num1 נמצאת גם ב-num2
return False
num1 = num1 // 10
return Trueלדוגמה `is_strangers(123, 456)` מחזירה `True`, ו-`is_strangers(123, 451)` מחזירה `False` (הספרה 1 משותפת).
תשובה: הפעולה `is_strangers` שלמעלה.
סעיף ג
לולאה כפולה על כל הזוגות `i < j`; אם זוג כלשהו אינו "זרים" (`is_strangers`) מחזירים `False`, אחרת `True`.
רעיון: הרשימה היא "רשימת זרים" אם כל זוג איברים בה זרים. עוברים על כל הזוגות בעזרת לולאה כפולה, כש-`j` מתחיל מ-`i + 1` כדי לבדוק כל זוג פעם אחת ולא להשוות איבר לעצמו. בכל זוג משתמשים ב-`is_strangers` מסעיף ב; זוג אחד שאינו זר מספיק כדי להחזיר `False`.
def is_it_strangers(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if not is_strangers(arr[i], arr[j]):
return False
return Trueלדוגמה `[12, 34, 56]` היא רשימת זרים (מוחזר `True`), ו-`[12, 34, 51]` אינה (ל-12 ול-51 יש ספרה משותפת 1).
תשובה: הפעולה `is_it_strangers` שלמעלה.
סעיף ד
`exist`: ; `is_strangers`: , כאשר הוא מספר הספרות.
נסמן ב- את מספר הספרות של מספר; .
1. `exist(num, digit)`: הלולאה מבצעת סיבוב אחד לכל ספרה של `num` (בכל סיבוב המספר מתחלק ב-10), ובכל סיבוב מספר קבוע של פעולות. במקרה הגרוע (הספרה לא נמצאת) מבצעים סיבובים, ולכן הסיבוכיות .
2. `is_strangers(num1, num2)`: הלולאה החיצונית עוברת על הספרות של `num1`, ובכל סיבוב מזמנת את `exist(num2, ...)` שעולה . במקרה הגרוע (המספרים זרים) מבצעים את כל הסיבובים, ולכן הסיבוכיות .
תשובה: `exist` - , לינארית במספר הספרות; `is_strangers` - , מכפלת מספרי הספרות.
שאלה 9 · מחלקת נתוני איכות אוויר: דירוג וסינון
מדד איכות האוויר (Air Quality Index - AIQ) משמש להערכה רמת הזיהום של האוויר באזורים שונים של הארץ. מדד AIQ הוא מספר שלם שנע מ- 0 ל-500. המשרד לאיכות הסביבה מפרסם כל יום "מפת זיהום ארצית" הכוללת נתונים של רמת הזיהום ביישובים שונים. לשם כך פיתחו מתכנתי המשרד מחלקה AIQData. למחלקה ארבע תכונות:
•תאריך – `date`, מטיפוס מחרוזת, `str`
•שם היישוב – `city`, מטיפוס מחרוזת, `str`
•מספר תושבים – `popul`, מטיפוס מספר שלם, `int`
•מדד איכות האוויר – `aiq` – מטיפוס שלם, `int`
כדי להעלות את מודעות האוכלוסייה הרחבה להשלכות הבריאותיות של זיהום האוויר, הוחלט במקום לפרסם מדד מספרי מדויק, לפרסם "דירוג" לפי הכלל הבא:
כתבו פעולה פנימית במחלקה AIQData המחזירה דירוג לפי מדד איכות האוויר. כותרת הפעולה:
raiting(self)כתבו פעולה המקבלת רשימת נתונים של איכות האוויר `arr` (רשימת הפניות לעצמים מטיפוס `AIQData`) ותאריך מסוים `check_date`. על הפעולה להדפיס שמות של כל היישובים שאיכות האוויר בתאריך זה הייתה "לא בריאה" או "מסוכנת". חובה להשתמש בפעולה שכתבתם בסעיף א'.
כותרת הפעולה:
print_dangerous(arr, check_date)כתבו פעולה המקבלת רשימת נתונים של איכות האוויר `arr` (רשימה הפניות לעצמים מטיפוס `AIQData`) ורשימה שמות יישובים `cities`. הפעולה תחשב ותדפיס עבור כל יישוב כמה פעמים איכות האוויר הייתה "טובה" וכמה פעמים היא הייתה "מסוכנת".
כותרת הפעולה:
print_cities(arr, cities)◂ פתרון מלא לשאלה 9
סעיף א
שרשרת תנאים על `self.aiq`: עד 49 → 1, עד 99 → 2, עד 149 → 3, עד 199 → 4, אחרת → 5.
רעיון: בודקים את `self.aiq` מול הגבולות העליונים של הטווחים, מהקטן לגדול. ברגע שהערך קטן או שווה לגבול העליון של טווח, הוא שייך לטווח הזה (כי כבר ידוע שהוא גדול מהגבול של הטווח הקודם), ומחזירים את הדירוג. אם עבר את כל הבדיקות, הוא בטווח 200-500 ודירוגו 5.
את הבנאי לא נדרש לכתוב; הוא מובא כדי שהמחלקה תהיה שלמה.
class AIQData:
def __init__(self, date, city, popul, aiq):
self.date = date
self.city = city
self.popul = popul
self.aiq = aiq
def raiting(self):
if self.aiq <= 49:
return 1
if self.aiq <= 99:
return 2
if self.aiq <= 149:
return 3
if self.aiq <= 199:
return 4
return 5לדוגמה עבור `aiq = 160` הבדיקות הראשונות נכשלות ו-`160 <= 199` מתקיים, ומוחזר 4.
תשובה: הפעולה `raiting` שלמעלה.
סעיף ב
עוברים על `arr` ומדפיסים את `city` של כל עצם שבו `date == check_date` ו-`raiting() >= 4`.
רעיון: "לא בריא" הוא דירוג 4 ו"מסוכן" הוא דירוג 5, כלומר מחפשים דירוג 4 ומעלה. עוברים על כל העצמים ברשימה; לכל עצם בודקים שהתאריך שלו הוא התאריך המבוקש, ושהדירוג שמחזירה `raiting()` מסעיף א הוא לפחות 4. אם שני התנאים מתקיימים - מדפיסים את שם היישוב.
def print_dangerous(arr, check_date):
for data in arr:
if data.date == check_date and data.raiting() >= 4:
print(data.city)תשובה: הפעולה `print_dangerous` שלמעלה.
סעיף ג
לכל יישוב ב-`cities` סופרים ב-`arr` את העצמים של היישוב עם דירוג 1 (טובה) ועם דירוג 5 (מסוכנת), ומדפיסים את שני המונים.
רעיון: לולאה חיצונית על היישובים. לכל יישוב מאפסים שני מונים, `good` ו-`dangerous`, ועוברים על כל נתוני `arr`. עצם ששייך ליישוב (`data.city == city`) נבדק לפי הדירוג: דירוג 1 ("טוב") מגדיל את `good`, ודירוג 5 ("מסוכן") מגדיל את `dangerous`. אחרי המעבר על הרשימה מדפיסים את שם היישוב ואת שני המונים.
def print_cities(arr, cities):
for city in cities:
good = 0
dangerous = 0
for data in arr:
if data.city == city:
if data.raiting() == 1:
good = good + 1
elif data.raiting() == 5:
dangerous = dangerous + 1
print(city, "good:", good, "dangerous:", dangerous)אם יש יישובים ו- נתונים, הפעולה מבצעת בדיקות, כלומר .
תשובה: הפעולה `print_cities` שלמעלה.
שאלה 10 · סידור רשימה: שליליים לפני אי-שליליים
נתונה הפעולה `why` המקבלת רשימה של מספרים שלמים:
def why(arr):
temp = []
for i in range(len(arr)):
if arr[i] < 0:
temp.append(arr[i])
for i in range(len(arr)):
if arr[i] >= 0:
temp.append(arr[i])
for i in range(len(arr)):
arr[i] = temp[i]נתונה הרשימה `arr = [12, 0, -344, -46, 670, 0]`
מה יהיה תוכן הרשימה אחרי זימון הפעולה `why(arr)`?
מה מבצעת הפעולה `why` באופן כללי?
נתונה הפעולה `what` המקבלת רשימה מספרים שלמים:
def what(arr):
start = 0
end = -1
while start - end < len(arr):
if arr[start] < 0:
start = start + 1
elif arr[end] >= 0:
end = end -1
else:
temp = arr[end]
arr[end] = arr[start]
arr[start] = tempנתונה רשימה `arr = [123, -45, -678, 12, -345, 67]`
מה יהיה תוכן ההרשימה אחרי זימון הפעולה `what(arr)`?
תנו דוגמה לרשימה `brr` בגודל של חמישה תאים, כך שהתוכן של הרשימה לא ישתנה אחרי ביצוע הפעולה `what(brr)`
מה מבצעת הפעולה `what` באופן כללי?
האם קיימת רשימה `crr` בגודל של שישה תאים, שעבורה שני זימונים `why(crr)` ו- `what(crr)` יביאו לאותן תוצאות? אם כן – תנו דוגמה של הרשימה `crr`, ולא – הסבר למה.
מה הן סיבוכיות זמן הריצה של הפעולות `what` ו- `why`?
◂ פתרון מלא לשאלה 10
סעיף א
`[-344, -46, 12, 0, 670, 0]`
עוקבים אחרי בניית `temp`:
תשובה: אחרי הזימון `arr = [-344, -46, 12, 0, 670, 0]`.
מסדרת את הרשימה כך שכל השליליים בהתחלה ואחריהם כל האי-שליליים, וכל קבוצה שומרת על הסדר המקורי שלה.
הלולאה הראשונה מעתיקה ל-`temp` את כל הערכים השליליים לפי הסדר שלהם, השנייה מוסיפה אחריהם את כל הערכים האי-שליליים (אפס וחיוביים) לפי הסדר, והשלישית מעתיקה את `temp` חזרה ל-`arr`. כך `arr` עצמה משתנה (היא מועברת כהפניה).
תשובה: הפעולה מסדרת מחדש את הרשימה כך שבתחילתה כל המספרים השליליים ואחריהם כל המספרים האי-שליליים; בתוך כל קבוצה נשמר הסדר המקורי. היא משתמשת ברשימת עזר.
סעיף ב
`[-345, -45, -678, 12, 123, 67]`
`start` מתקדם מתחילת הרשימה ו-`end` מהסוף (אינדקס שלילי: 1- הוא התא האחרון, 2- הלפני אחרון וכו'). התא `end` הוא התא שאינדקסו מההתחלה . התנאי `start - end < len(arr)` אומר שהמצביעים עוד לא חצו זה את זה. כאן `len(arr) = 6`.
עכשיו `start - end = 3 - (-3) = 6`, והתנאי `6 < 6` שקר, לכן הלולאה נעצרת.
תשובה: אחרי הזימון `arr = [-345, -45, -678, 12, 123, 67]`.
למשל `brr = [-1, -2, 3, 4, 5]` (כל השליליים כבר לפני כל האי-שליליים).
החלפה מתבצעת רק כאשר `arr[start]` אי-שלילי וגם `arr[end]` שלילי, כלומר כשיש מספר אי-שלילי שנמצא לפני מספר שלילי. אם כל השליליים כבר נמצאים לפני כל האי-שליליים, אין אף החלפה והרשימה לא משתנה.
מעקב עבור `brr = [-1, -2, 3, 4, 5]`: `start` מתקדם על -1 ו--2 עד `start = 2`; אחר כך `end` יורד מ-1- (5) ל-2- (4) ול-3- (3), ואז והלולאה נעצרת, בלי החלפות.
תשובה: לדוגמה `brr = [-1, -2, 3, 4, 5]` (וגם כל רשימה של חמישה תאים שבה כל השליליים לפני כל האי-שליליים, למשל `[1, 2, 3, 4, 5]`).
מסדרת את הרשימה במקום כך שכל השליליים בהתחלה וכל האי-שליליים בסוף, בעזרת החלפות משני הקצוות; הסדר בתוך הקבוצות לא בהכרח נשמר.
`start` מדלג על ערכים שליליים שכבר בצד שמאל, `end` מדלג על ערכים אי-שליליים שכבר בצד ימין. כאשר `start` עומד על ערך אי-שלילי ו-`end` על ערך שלילי, שניהם "במקום הלא נכון" ומחליפים ביניהם. הלולאה נעצרת כשהמצביעים נפגשים.
תשובה: הפעולה מחלקת את הרשימה (בתוך הרשימה עצמה, בלי רשימת עזר) כך שכל המספרים השליליים יהיו בתחילתה וכל האי-שליליים בסופה. בניגוד ל-`why`, הסדר המקורי בתוך כל קבוצה לא בהכרח נשמר (בסעיף 1, -345 עבר לפני -45).
סעיף ג
כן. למשל `crr = [-1, -2, -3, 4, 5, 6]`: שתי הפעולות משאירות אותה ללא שינוי.
שתי הפעולות מעבירות את השליליים להתחלה; ההבדל ביניהן הוא רק בסדר בתוך הקבוצות. ברשימה שבה כל השליליים כבר לפני כל האי-שליליים:
1. `why` מעתיקה את השליליים לפי הסדר ואחריהם את האי-שליליים לפי הסדר, ומקבלת בדיוק את אותה רשימה.
2. `what` לא מבצעת אף החלפה (כמו בסעיף ב2), ולכן גם היא לא משנה את הרשימה.
תשובה: כן. לדוגמה `crr = [-1, -2, -3, 4, 5, 6]`; אחרי כל אחד מהזימונים הרשימה נשארת `[-1, -2, -3, 4, 5, 6]`.
סעיף ד
שתיהן .
נסמן = אורך הרשימה.
1. `why`: שלוש לולאות נפרדות, כל אחת סיבובים עם פעולה קבועה (הוספה בסוף רשימה היא פעולה קבועה), סך הכול , כלומר (וגם זיכרון נוסף לרשימה `temp`).
2. `what`: בכל סיבוב או ש-`start` גדל, או ש-`end` קטן, או שמתבצעת החלפה. אחרי החלפה `arr[start]` שלילי, ולכן בסיבוב הבא `start` בהכרח גדל. המרחק בין המצביעים קטן ב-1 לפחות כל שני סיבובים, ולכן יש לכל היותר כ- סיבובים, כלומר .
תשובה: סיבוכיות זמן הריצה של `what` ושל `why` היא , לינארית באורך הרשימה.
שאלה 11 · פלינדרום של אותיות גדולות במחרוזת
נתונה מחרוזת `s="aMrAdDYrM"`. עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `why(s)` ורשמו מהי תוצאת הזימון.
def why(s):
while len(s) > 1:
if s[0] < 'A' or s[0] > 'Z':
s = s[1:]
elif s[-1] < 'A' or s[-1] > 'Z':
s = s[:-1]
elif s[0] != s[-1]:
return False
else:
s = s[1:-1]
print(s)
return Trueנתונה הפעולה `what` הבאה:
def what(s):
while len(s) > 1:
if s[0] != s[-1]:
return False
s = s[1:-1]
return Trueתנו דוגמה למחרוזת `s` באורך שישה תווים כך שזימון `what(s)` יחזיר ערך `true`.
נתונה הפעולה `where` הבאה. הפעולה משתמשת בפעולה `what`:
def where(s):
str = ""
for i in range(len(s)):
if s[i] >= 'A' and s[i] <= 'Z':
str = str + s[i]
return what(str)האם הפעולה `where` שקולה (מבצעת בדיוק אותו הדבר) לפעולה `why`? אם כן, הסבירו מה מבצעות שתי הפעולות באופן כללי, ולא – תנו דוגמה של מחרוזת `s` שעבורה תוצאות הזימונים `why(s)` ו- `where(s)` יהיו שונות.
◂ פתרון מלא לשאלה 11
סעיף א
מודפסות השורות MrAdDYrM, rAdDYr, AdDYr, AdDY, והפעולה מחזירה `False`.
בכל סיבוב הפעולה בודקת את התו הראשון והאחרון: תו שאינו אות גדולה (קטן מ-'A' או גדול מ-'Z') נמחק מהקצה שלו; אם שני הקצוות אותיות גדולות ושונות - מוחזר `False`; אם הן שוות - שתיהן נמחקות. אחרי כל שינוי מודפסת המחרוזת.
פלט:
MrAdDYrM
rAdDYr
AdDYr
AdDYתשובה: מודפסות ארבע השורות שלמעלה, ו-`why("aMrAdDYrM")` מחזירה `False`.
סעיף ב
למשל `s = "ABCCBA"` (פלינדרום).
`what` משווה את התו הראשון לאחרון; אם הם שונים מחזירה `False`, ואחרת מוחקת את שניהם וממשיכה פנימה. היא מחזירה `True` רק אם כל זוגות התווים הסימטריים שווים, כלומר אם המחרוזת היא פלינדרום (נקראת אותו דבר משני הכיוונים).
מעקב עבור `"ABCCBA"`: A=A, נשאר `"BCCB"`; B=B, נשאר `"CC"`; C=C, נשאר `""`; האורך 0, ומוחזר `True`.
תשובה: לדוגמה `s = "ABCCBA"`.
סעיף ג
כן (מבחינת הערך המוחזר): שתיהן מחזירות `True` אם ורק אם רצף האותיות הגדולות ב-`s` הוא פלינדרום. ההבדל היחיד: `why` גם מדפיסה את המחרוזת בכל סיבוב.
1. `where` בונה את המחרוזת `str` של כל האותיות הגדולות ('A' עד 'Z') של `s` לפי הסדר, ובודקת בעזרת `what` (סעיף ב) אם היא פלינדרום.
2. `why` מוחקת מהקצוות כל תו שאינו אות גדולה, ולכן בכל פעם שהיא מגיעה להשוואה `s[0] != s[-1]` שני הקצוות הם האות הגדולה הראשונה והאות הגדולה האחרונה שנשארו. היא משווה אותן, ואם הן שוות מוחקת את שתיהן וממשיכה פנימה. זו בדיוק אותה השוואה ש-`what` עושה על רצף האותיות הגדולות: ראשונה מול אחרונה, אחר כך שנייה מול לפני אחרונה, וכן הלאה.
3. כששתי הפעולות מסיימות בלי למצוא זוג שונה (נשארו 0 או 1 תווים) הן מחזירות `True`, וברגע שנמצא זוג אותיות שונות שתיהן מחזירות `False`.
בדיקה על המחרוזת מסעיף א: האותיות הגדולות של "aMrAdDYrM" הן "MADYM"; `what` משווה M=M ואז A מול Y, ומחזירה `False`, כמו `why`.
הערה: `why` מדפיסה את המחרוזת בכל סיבוב, ו-`where` לא מדפיסה דבר; הערך שמוחזר זהה לכל מחרוזת.
תשובה: כן, מבחינת התוצאה המוחזרת הפעולות שקולות: שתיהן בודקות אם רצף האותיות הגדולות במחרוזת (בהתעלמות מכל שאר התווים) הוא פלינדרום, ומחזירות `True` אם כן ו-`False` אם לא. ההבדל היחיד הוא ההדפסות ש-`why` מבצעת בדרך.
שאלה 12 · רשימת רשימות סופר מאוזנת וסיבוכיותה
נתונות הגדרות הבאות:
•מספר שלם וחיובי נקרא "מספר מאוזן" אם סכום הספרות הזוגיות שלו שווה לסכום הספרות האי-זוגיות.
המספרים 121, 134, 41111, 2334 הם "מספרים מאוזנים".
המספרים 43, 186, -121, 35 אינם "מספרים מאוזנים".
•רשימה של מספרים שלמים (חיוביים, שליליים ואפסים) נקראת "מאוזנת בקצוות" אם הערך הגדול ביותר ברשימה הוא "מספר מאוזן" וגם הערך הקטן ביותר ברשימה הוא "מספר מאוזן".
•רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה) נקראת "סופר מאוזנת" אם כל איבר שלה הוא רשימה "מאוזנת בקצוות".
כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים (רשימה שכל איבר שבה הוא רשימה של מספרים שלמים) ובודקת אם היא "סופר מאוזנת".
אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 12
סעיף א
שלוש פעולות: `is_balanced_number` (סכום ספרות זוגיות = סכום אי-זוגיות, רק למספר חיובי), `is_edges_balanced` (מקסימום ומינימום מאוזנים), `is_super_balanced` (כל רשימה פנימית מאוזנת בקצוות).
מפרקים את הבעיה לשלוש פעולות, לפי שלוש ההגדרות:
1. `is_balanced_number(num)`: לפי ההגדרה רק מספר שלם וחיובי יכול להיות מאוזן (ולכן -121 אינו מאוזן), אז עבור `num <= 0` מחזירים `False`. אחרת מפרקים את המספר לספרות (`% 10`, `// 10`), ספרה זוגית מוסיפים ל-`sum_even` וספרה אי-זוגית ל-`sum_odd`, ובסוף משווים. לדוגמה ב-2334: ו-, מאוזן; ב-43: , לא מאוזן.
2. `is_edges_balanced(lst)`: מוצאים במעבר אחד את הערך הגדול ביותר ואת הקטן ביותר ברשימה (מאתחלים את שניהם לאיבר הראשון), ומחזירים אמת רק אם שניהם מספרים מאוזנים. (מניחים שכל רשימה פנימית אינה ריקה, אחרת אין לה ערך גדול או קטן ביותר.)
3. `is_super_balanced(lists)`: עוברים על הרשימות הפנימיות; ברגע שאחת מהן אינה מאוזנת בקצוות מחזירים `False`. אם כולן עברו - מחזירים `True`.
def is_balanced_number(num):
if num <= 0: # רק מספר שלם וחיובי יכול להיות מאוזן
return False
sum_even = 0
sum_odd = 0
while num > 0:
digit = num % 10
if digit % 2 == 0:
sum_even = sum_even + digit
else:
sum_odd = sum_odd + digit
num = num // 10
return sum_even == sum_odd
def is_edges_balanced(lst):
max_val = lst[0]
min_val = lst[0]
for val in lst:
if val > max_val:
max_val = val
if val < min_val:
min_val = val
return is_balanced_number(max_val) and is_balanced_number(min_val)
def is_super_balanced(lists):
for lst in lists:
if not is_edges_balanced(lst):
return False
return Trueדוגמה: עבור `[[121, 134, 2334, 500], [41111, 1000, 121]]` - ברשימה הראשונה המקסימום 2334 והמינימום 121, שניהם מאוזנים; בשנייה המקסימום 41111 והמינימום 121, שניהם מאוזנים, ולכן מוחזר `True`. אם נוסיף רשימה `[121, -5]`, המינימום -5 שלילי ואינו מאוזן, ויוחזר `False`.
תשובה: הפעולה `is_super_balanced` (עם פעולות העזר) שלמעלה.
סעיף ב
, כאשר הוא מספר כל האיברים בכל הרשימות (למשל עבור רשימות באורך ).
נסמן = מספר הרשימות הפנימיות ו- = האורך המרבי של רשימה פנימית.
1. `is_balanced_number` עוברת על ספרות המספר: כאשר הוא מספר הספרות, ועבור מספרים שלמים בגודל רגיל זה מספר קטן וחסום, כלומר פעולה קבועה.
2. `is_edges_balanced` עוברת פעם אחת על הרשימה כדי למצוא מקסימום ומינימום (), ואחר כך מזמנת פעמיים את `is_balanced_number` (). סך הכול .
3. `is_super_balanced` מזמנת את `is_edges_balanced` לכל אחת מ- הרשימות. במקרה הגרוע (כל הרשימות מאוזנות בקצוות, ואין יציאה מוקדמת) זה .
תשובה: הסיבוכיות היא , כלומר לינארית במספר הכולל של האיברים בכל הרשימות: כל איבר נבדק פעם אחת בחיפוש המקסימום והמינימום, ולכל רשימה יש עוד בדיקת ספרות קצרה של שני מספרים.
שאלה 13 · מחלקות נוסע וטיול: בדיקת תנאי הצטרפות
חברת "טיולי עם" מארגנת טיולים ליעדים שונים בעולם. למערכת הממוחשבת של החברה יש שלוש מחלקות: `Date, Traveler, Travel`.
המחלקה `Date` מציינת תאריך. למחלקה יש שלוש תכונות:
`day` – יום, `month` - חודש, `year` – שנה.
במחלקה הוגדרה הפעולה המקבלת כפרמטר תאריך מסוים ובודקת אם התאריך הנוכחי (התאריך שמיוצג באמצעות האובייקט שמפעיל את הפעולה, `self`), לפני מהתאריך `other` שהתקבל כפרמטר.
כותרת הפעולה:
before(self,other)המחלקה `Traveler` מייצגת נוסע. למחלקה יש את התכונות הבאות:
•שם נוסע – `name` - מטיפוס מחרוזת, `str`
•תאריך התפוגה של הדרכון – `expire_date` – מטיפוס תאריך, `Date`
•יעד הנסיעה הרצוי – `destination` – מטיפוס מחרוזת, `str`
•סכום המקדמה ששילם – `payment` – מטיפוס מספר שלם, `int`
כתבו פעולה הבודקת אם הנוסע יכול להצטרף לטיול שמחירו `price`, תאריך היציאה `start` ויעד הטיול `dest`. הנוסע יכול להצטרף לטיול אם הדרכון שלו בתוקף, יעד הטיול הוא היעד הרצוי ונוסע שילם לפחות חצי ממחיר הטיול.
כותרת הפעולה:
can_go(self, start, price, dest)המחלקה `Travel` מייצגת טיול. למחלקה ארבע תכונות:
•יעד הטיול – `destination`, מטיפוס מחרוזת, `str`
•רשימה נרשמים לטיול – `travelers`, רשימה הפניות לעצמים מטיפוס `Traveler`
•מחיר הטיול – `price`, מטיפוס מספר שלם, `int`
•תאריך היציאה לטיול – `start_date`, מטיפוס תאריך, `Date`
כתבו פעולה המדפיסה את שמות הנרשמים שהדרכון שלהם אינו בתוקף בתאריך היציאה.
כותרת הפעולה:
not_valid_names(self)הטיול מובטח רק אם בין הנרשמים יש לפחות `min_num` נוסעים שיכולים לצאת לטיול.
כתבו פעולה הבודקת אם הטיול מובטח. אם כן – הפעולה תחזיר ערך `True`, ולא, הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_guaranted(self, min_num)◂ פתרון מלא לשאלה 13
סעיף א
מחזירה `not self.expire_date.before(start) and self.destination == dest and self.payment * 2 >= price`.
זו פעולה של המחלקה `Traveler` (מופעלת על נוסע). שלושה תנאים צריכים להתקיים יחד:
1. הדרכון בתוקף ביום היציאה: תאריך התפוגה אינו לפני תאריך היציאה, כלומר `not self.expire_date.before(start)`. כאן משתמשים בפעולה `before` הנתונה של `Date`.
2. יעד הטיול הוא היעד הרצוי: `self.destination == dest`.
3. הנוסע שילם לפחות חצי מהמחיר: , ובלי חילוק: `self.payment * 2 >= price`.
class Traveler:
# ... התכונות והבנאי של המחלקה
def can_go(self, start, price, dest):
valid = not self.expire_date.before(start) # הדרכון לא פג לפני היציאה
return valid and self.destination == dest and self.payment * 2 >= priceהערה: דרכון שתוקפו פג בדיוק ביום היציאה נחשב כאן בתוקף (תאריך התפוגה אינו *לפני* היציאה).
תשובה: הפעולה `can_go` שלמעלה.
סעיף ב
עוברים על `self.travelers` ומדפיסים את `name` של כל נוסע שבו `expire_date.before(self.start_date)`.
זו פעולה של המחלקה `Travel`. עוברים על רשימת הנרשמים `self.travelers`. הדרכון של נוסע אינו בתוקף ביום היציאה אם תאריך התפוגה שלו לפני תאריך היציאה של הטיול, כלומר `t.expire_date.before(self.start_date)`; במקרה כזה מדפיסים את שמו. (זו בדיוק השלילה של תנאי התוקף מסעיף א.)
class Travel:
# ... התכונות והבנאי של המחלקה
def not_valid_names(self):
for t in self.travelers:
if t.expire_date.before(self.start_date):
print(t.name)תשובה: הפעולה `not_valid_names` שלמעלה.
סעיף ג
סופרים את הנרשמים שעבורם `can_go(self.start_date, self.price, self.destination)` אמת, ומחזירים `count >= min_num`.
זו פעולה של המחלקה `Travel`. נוסע "יכול לצאת לטיול" אם הפעולה `can_go` מסעיף א מחזירה עבורו `True` עם הנתונים של הטיול הזה: תאריך היציאה `self.start_date`, המחיר `self.price` והיעד `self.destination`.
1. עוברים על כל הנרשמים וסופרים במונה `count` את אלה שיכולים לצאת.
2. מחזירים את תוצאת ההשוואה `count >= min_num`.
class Travel:
# ... התכונות, הבנאי ו-not_valid_names
def is_guaranted(self, min_num):
count = 0
for t in self.travelers:
if t.can_go(self.start_date, self.price, self.destination):
count = count + 1
return count >= min_numתשובה: הפעולה `is_guaranted` שלמעלה.
שאלה 14 · רקורסיה: זוגות עם סכום והפרש נתונים
נתונה הפעולה הרקורסיביות `what` המקבלת רשימה מספרים שלמים הממוינת בסדר עולה ומספר שלם וחיובי `num`:
def what(arr, num, found = False):
if len(arr)<2 :
return found
if arr[0] + arr[-1] < num :
return what(arr[1:], num, found)
if arr[0] + arr[-1] > num:
return what(arr[: -1], num, found)
print(arr[0], arr[-1])
return what(arr[1:-1], num, True)נתונה הרשימה הבאה של מספרים שלמים:
arr =[2,4,7,13,18,21,30]עקבו אחרי זימון `what(a, 20)` רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `what` באופן כללי?
נתונה הפעולה הרקורסיביות `why` המקבלת רשימה מספרים שלמים הממוינת בסדר עולה ומספר שלם וחיובי `num`:
def why(arr, num, count = 0, left = 0, right = 1):
if left == len(arr)-1 or right == len(arr):
return count
if arr[right] - arr[left] < num :
return why(arr, num, count, left, right+1)
if arr[right] - arr[left] > num:
return why(arr, num, count, left+1, right)
print(arr[left], arr[right])
return why(arr, num, count+1, left+1, right+1)נתונה הרשימה הבאה של מספרים שלמים:
arr=[2,4,7,13,18,21,30]האם קיים מספר `num` שעבורו זימון `why(a, num)` יחזיר 2? אם כן, תנו דוגמה למספר כזה וציינו מה יהיה הפלט, ולא – הסבירו למה הדבר אינו אפשרי.
מה מבצעת הפעולה `why` באופן כללי?
◂ פתרון מלא לשאלה 14
סעיף א
מודפס `2 18` ואחריו `7 13`, והזימון מחזיר `True`.
הרשימה `a` בזימון היא הרשימה `arr` הנתונה. בכל זימון משווים את סכום הקצוות `arr[0] + arr[-1]` ל-20: אם הסכום קטן, מוותרים על האיבר הקטן (הראשון); אם הוא גדול, מוותרים על הגדול (האחרון); אם הוא שווה, מדפיסים את הזוג וממשיכים פנימה עם `found = True`.
הערך `True` מוחזר לאורך כל שרשרת הזימונים עד הזימון הראשון.
פלט:
2 18
7 13תשובה: מודפסים הזוגות `2 18` ו-`7 13`, והזימון `what(a, 20)` מחזיר `True`.
סעיף ב
מדפיסה את כל זוגות האיברים (במקומות שונים) שסכומם `num`, ומחזירה `True` אם נמצא לפחות זוג אחד, אחרת `False`.
הרשימה ממוינת, ולכן אם סכום הקצוות קטן מ-`num` האיבר הראשון קטן מדי לכל זוג אפשרי (גם עם הגדול ביותר), ומוותרים עליו; אם הסכום גדול מ-`num` האיבר האחרון גדול מדי לכל זוג, ומוותרים עליו. כשהסכום שווה, מדפיסים את הזוג ומסירים את שני האיברים. זו שיטת "שני המצביעים" מהקצוות פנימה. הפרמטר `found` הופך ל-`True` אחרי הזוג הראשון שנמצא ונשמר עד הסוף.
תשובה: הפעולה מדפיסה את כל זוגות האיברים ברשימה שסכומם שווה ל-`num` (מהזוג החיצוני פנימה), ומחזירה `True` אם נמצא לפחות זוג אחד כזה, ו-`False` אחרת.
סעיף ג
כן. למשל `num = 5`: מודפס `2 7` ו-`13 18`, והזימון מחזיר 2.
`why` מחפשת זוגות שההפרש ביניהם `arr[right] - arr[left]` שווה ל-`num`: אם ההפרש קטן מדי מגדילים את `right`, אם הוא גדול מדי מגדילים את `left`, ואם הוא שווה מדפיסים את הזוג, מגדילים את `count` ומקדמים את שניהם. לכן צריך `num` שהוא הפרש של בדיוק שני זוגות ברשימה.
ההפרש 5 מתקבל פעמיים: ו-. נבדוק במעקב עבור `num = 5`:
פלט:
2 7
13 18(גם `num` = 3, 9, 11, 14 או 17 מתאימים, כי כל אחד מהם הוא הפרש של בדיוק שני זוגות.)
תשובה: כן. לדוגמה `num = 5`: יודפסו `2 7` ו-`13 18`, והזימון `why(a, 5)` יחזיר 2.
סעיף ד
מדפיסה את כל זוגות האיברים שההפרש ביניהם שווה ל-`num` ומחזירה את מספר הזוגות האלה.
`left` ו-`right` הם שני מצביעים שמתקדמים שניהם ימינה על הרשימה הממוינת: הפרש קטן מ-`num` מגדיל את `right` (כדי להגדיל את ההפרש), הפרש גדול מ-`num` מגדיל את `left` (כדי להקטין אותו), והפרש שווה הוא זוג מתאים - מדפיסים אותו ומוסיפים 1 ל-`count`. כשאחד המצביעים מגיע לסוף הרשימה מוחזר `count`.
תשובה: הפעולה מדפיסה את כל זוגות האיברים ברשימה הממוינת (עם ערכים שונים זה מזה) שההפרש ביניהם שווה ל-`num`, ומחזירה את מספר הזוגות האלה.