מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - קיץ 2023 מועד ב'
הנדסת תוכנה · סמל 97103 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), קיץ 2023 מועד ב', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: מבחן ב-Python
חלק א' – 48 נקודות
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 7-9: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 22 נקודות
שאלות 10-12: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
אין לצרף ספרים או חוברות עם פתרונות.
שאלה 1 · קליטת מספרים עד תלת ספרתי, מקסימום ומינימום
כתבו קטע קוד שקולט מספרים שלמים עד שייקלט מספר תלת ספרתי. יש להדפיס את מספר הגדול ביותר שנקלט ואת מספר הקטן שנקלט.
◂ פתרון מלא לשאלה 1
פתרון
לולאת while שקולטת מספרים עד שנקלט מספר תלת ספרתי (), ומעדכנת תוך כדי את המקסימום ואת המינימום; בסוף מדפיסים את שניהם.
מבוקש: לקלוט מספרים שלמים, אחד אחרי השני, ולעצור כשנקלט מספר תלת ספרתי. בסוף מדפיסים את הגדול ביותר ואת הקטן ביותר מבין כל המספרים שנקלטו.
הנחות (לפי הוראה 9 בדף השער):
•המספר התלת ספרתי שעוצר את הקליטה גם הוא "מספר שנקלט", ולכן הוא משתתף בחישוב הגדול והקטן.
•מספר שלילי כמו הוא גם תלת ספרתי (יש לו שלוש ספרות), לכן הבדיקה היא על הערך המוחלט: .
רעיון:
1. קולטים את המספר הראשון לפני הלולאה, ומאתחלים בו גם את `max_num` וגם את `min_num`. כך אין צורך לנחש ערך התחלתי "גדול מאוד" או "קטן מאוד".
2. כל עוד המספר האחרון שנקלט אינו תלת ספרתי, קולטים מספר חדש ומשווים אותו לגדול ולקטן הנוכחיים: אם הוא גדול מהמקסימום מעדכנים את המקסימום, ואם הוא קטן מהמינימום מעדכנים את המינימום.
3. כשנקלט מספר תלת ספרתי, תנאי הלולאה נכשל (המספר כבר עודכן במקסימום/מינימום בתוך הלולאה, או שהיה המספר הראשון), והלולאה מסתיימת. מדפיסים את שתי התוצאות.
אם המספר הראשון כבר תלת ספרתי, הלולאה לא מתבצעת כלל, והוא גם הגדול וגם הקטן.
num = int(input())
max_num = num
min_num = num
while not (100 <= abs(num) <= 999):
num = int(input())
if num > max_num:
max_num = num
if num < min_num:
min_num = num
print("max:", max_num)
print("min:", min_num)דוגמה: עבור הקלט הקליטה נעצרת ב-, יודפס `max: 350` ו-`min: -20`.
תשובה: קטע הקוד שלמעלה: קליטה ראשונה לפני הלולאה, לולאת while עד מספר תלת ספרתי, עדכון מקסימום ומינימום בכל קליטה, והדפסה בסוף.
שאלה 2 · בדיקת מחרוזת תקינה וספירת מחרוזות תקינות
מחרוזת "תקינה" היא מחרוזת העונה לשני תנאים הבאים:
•אורך המחרוזת אי-זוגי.
•תו ראשון זהה לתו אמצעי וזהה לתו האחרון.
לדוגמה: המחרוזת "AbbAc1A" היא "מחרוזת תקינה".
כתבו פעולה המקבלת מחרוזת ובודקת אם היא "מחרוזת תקינה".
אם כן – הפעולה תחזיר ערך `True` , ולא – הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_valid(s)כתבו קטע קוד הקולט 23 מחרוזות. הקטע יחשב וידפיס מספר "מחרוזות תקינות" ומספר מחרוזות לא תקינות. יש להשתמש בפעולה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 2
סעיף א
הפעולה מחזירה `False` אם האורך זוגי, אחרת בודקת `s[0] == s[n//2] == s[n-1]`.
מבוקש: פעולה שבודקת שני תנאים ומחזירה ערך בוליאני.
1. מחשבים את האורך `n = len(s)`. אם `n` זוגי, המחרוזת לא תקינה ומחזירים מיד `False`. (גם מחרוזת ריקה, שאורכה , נופלת כאן, וזה נכון כי אין לה תו ראשון.)
2. כשהאורך אי-זוגי יש תו אמצעי אחד בדיוק, באינדקס `n // 2`. למשל באורך האינדקסים הם עד , והאמצעי הוא .
3. התו האחרון נמצא באינדקס `n - 1`.
4. מחזירים את תוצאת ההשוואה: התו הראשון שווה לאמצעי, והאמצעי שווה לאחרון (ולכן גם הראשון שווה לאחרון).
def is_valid(s):
n = len(s)
if n % 2 == 0:
return False
mid = n // 2
return s[0] == s[mid] and s[mid] == s[n - 1]בדיקה עם הדוגמה: "AbbAc1A" באורך (אי-זוגי), האמצעי באינדקס הוא 'A', הראשון 'A' והאחרון 'A', לכן מוחזר `True`.
סיבוכיות: - מספר קבוע של פעולות.
תשובה: הפעולה `is_valid` שלמעלה.
סעיף ב
לולאה של 23 קליטות; על כל מחרוזת מזמנים `is_valid` ומגדילים את המונה המתאים; בסוף מדפיסים את שני המונים.
מבוקש: שני מונים - של מחרוזות תקינות ושל לא תקינות.
1. מאתחלים שני מונים ב-: `valid` ו-`not_valid`.
2. לולאת `for` שמתבצעת בדיוק פעמים. בכל סיבוב קולטים מחרוזת אחת.
3. מזמנים את `is_valid` מסעיף א: אם החזירה `True` מגדילים את `valid`, אחרת את `not_valid`.
4. אחרי הלולאה מדפיסים את שני המונים. (אפשר גם להסתפק במונה אחד ולהדפיס כמספר הלא תקינות.)
valid = 0
not_valid = 0
for i in range(23):
s = input()
if is_valid(s):
valid += 1
else:
not_valid += 1
print("valid:", valid)
print("not valid:", not_valid)תשובה: קטע הקוד שלמעלה, שמשתמש ב-`is_valid` וסופר את שני הסוגים.
שאלה 3 · בדיקת רשימה מאוזנת והדפסתה לפי התוצאה
רשימה של מספרים שלמים נקראת "רשימה מאוזנת" אם היא עונה על תנאים הבאים:
•כמות האיברים החיוביים שווה לכמות האיברים השליליים.
•הרשימה לא כולל אפסים.
כתבו פעולה המקבלת רשימה של מספרים שלמים. אם הרשימה מאוזנת יש להדפיס אותה מתחילתה ועד סופה בשורה אחת, ולא – יש להדפיס אותה בסדר הפוך (מסוף הרשימה להתחלה).
◂ פתרון מלא לשאלה 3
פתרון
מעבר אחד שסופר חיוביים ושליליים ומזהה אפס; אם המונים שווים ואין אפס - הדפסה מההתחלה לסוף, אחרת מהסוף להתחלה, בשורה אחת.
מבוקש: לבדוק אם הרשימה מאוזנת, ולפי התשובה להדפיס אותה בסדר רגיל או הפוך. השאלה לא נותנת שם לפעולה, נקרא לה `print_balanced(arr)`.
1. עוברים פעם אחת על כל האיברים: איבר חיובי מגדיל את `pos`, איבר שלילי מגדיל את `neg`, ואיבר שהוא אפס מסמן `has_zero = True`.
2. הרשימה מאוזנת בדיוק כאשר `pos == neg` וגם לא נמצא אפס.
3. אם היא מאוזנת - מדפיסים את האיברים לפי האינדקסים ; אחרת לפי (בעזרת `range(len(arr) - 1, -1, -1)`). בשני המקרים ההדפסה בשורה אחת עם `end=" "`, ובסוף `print()` לירידת שורה.
def print_balanced(arr):
pos = 0
neg = 0
has_zero = False
for x in arr:
if x > 0:
pos += 1
elif x < 0:
neg += 1
else:
has_zero = True
if pos == neg and not has_zero:
for i in range(len(arr)):
print(arr[i], end=" ")
else:
for i in range(len(arr) - 1, -1, -1):
print(arr[i], end=" ")
print()דוגמאות: עבור יש חיוביים ו- שליליים ואין אפס, לכן יודפס `3 -1 2 -8`. עבור יש אפס, לכן יודפס בסדר הפוך `-8 0 -1 3`.
סיבוכיות: - מעבר אחד לבדיקה ומעבר אחד להדפסה.
תשובה: הפעולה `print_balanced` שלמעלה.
שאלה 4 · מחלקת משלוח פרחים: בנאי ופיצוי על הפסד
חברת "פרחי הארץ" מגדלת פרחים ושולחת אותם למכירה לחוץ לארץ.
נתונה מחלקה `FlowerPackage` המייצגת משלוח פרחים המיועד לשליחה לחו"ל. למחלקה יש את התכונות הבאות:
•`type` – סוג הפרח, מטיפוס מחרוזת.
•`num` – מספר פרחים במשלוח, מטיפוס מספר שלם.
•`time` – מספר שעות שניתן להחזיק את הפרחים ללא מים, מטיפוס מספר שלם.
•`price` – מחיר פרח בודד, מטיפוס מספר ממשי.
במחלקה הוגדרה פעולה בונה (בנאי) המקבל פרמטרים לכל התכונות.
כתבו פעולה בונה המקבלת סוג פרח ומחיר. הפעולה מייצרת משלוח סטנדרטי של 2,000 פרחים.
זמן סטנדרטי שאפשר להחזיק את הפרחים ללא מים – 12 שעות.
עקב בעיות לוגיסטיות, חברת התעופה מציעה מסלול טיסה ארוך יותר. חלק ממשלוחים לא ישרדו טיסה ארוכה ואז אי אפשר יהיה למכור את הפרחים.
"פרחי הארץ" תדרוש מחברת התעופה פיצוי על ההפסד הכספי.
כתבו פעולה חיצונית המקבלת רשימה הפניות לעצמים מסוג `FlowerPackage` בשם `arr` ואורך הטיסה `flyTime`. הפעולה תדפיס פרטי המשלוחים שלא יהיו תקינים.
פעולה גם תחשב ותדפיס סכום ש"פרחי הארץ" הפסידה.
כותרת הפעולה:
compensation(arr, flyTime)הנחה: כל איבר ברשימה מכיל הפניה לעצם מסוג `FlowerPackage` ואין איברים שערכם שווה ל- `null`.
◂ פתרון מלא לשאלה 4
סעיף א
בנאי חלופי `standard(cls, type, price)` (classmethod) שמחזיר `cls(type, 2000, 12, price)`.
מבוקש: דרך נוספת ליצור עצם `FlowerPackage`, שמקבלת רק סוג ומחיר וממלאת ערכים קבועים: פרחים ו- שעות.
ב-Python אין העמסה של בנאים: במחלקה יש `__init__` אחד בלבד, והוא כבר קיים ומקבל את ארבע התכונות. לכן את הבנאי השני כותבים כ"בנאי חלופי" - פעולת מחלקה (`@classmethod`) שמזמנת את הבנאי הקיים עם הערכים הסטנדרטיים ומחזירה את העצם החדש.
1. הפעולה מקבלת את `cls` (המחלקה עצמה), את `type` ואת `price`.
2. היא מזמנת `cls(type, 2000, 12, price)`: הבנאי הקיים מאתחל את כל ארבע התכונות.
3. העצם שנוצר מוחזר למזמן.
בקוד מופיעה גם הפעולה `__str__`, שמחזירה את פרטי המשלוח כמחרוזת; נשתמש בה בסעיף ב להדפסה.
class FlowerPackage:
def __init__(self, type, num, time, price):
self.type = type
self.num = num
self.time = time
self.price = price
@classmethod
def standard(cls, type, price):
return cls(type, 2000, 12, price)
def __str__(self):
return ("type: " + self.type + ", num: " + str(self.num) +
", time: " + str(self.time) + ", price: " + str(self.price))שימוש: `p = FlowerPackage.standard("rose", 1.5)` יוצר משלוח של ורדים, שעות ללא מים, לפרח.
(אפשרות שקולה: בנאי אחד עם ערכי ברירת מחדל, למשל `def __init__(self, type, price, num=2000, time=12)`, אבל אז משתנה סדר הפרמטרים של הבנאי הקיים, ולכן הבנאי החלופי עדיף.)
תשובה: הפעולה `standard(cls, type, price)` שמחזירה `cls(type, 2000, 12, price)`.
סעיף ב
משלוח לא תקין אם `flyTime > time`; מדפיסים אותו ומוסיפים להפסד `num * price`; בסוף מדפיסים את סכום ההפסד.
נתון: רשימת משלוחים ואורך הטיסה בשעות.
מבוקש: להדפיס את המשלוחים שהפרחים בהם לא ישרדו, ואת סך ההפסד.
1. משלוח "לא תקין" כשהטיסה ארוכה ממספר השעות שהפרחים מחזיקים ללא מים, כלומר `flyTime > p.time`. (אם הטיסה שווה בדיוק ל-`time` הפרחים עוד מחזיקים, ולכן המשלוח תקין.)
2. ההפסד ממשלוח לא תקין הוא מחיר כל הפרחים בו: `p.num * p.price`.
3. מאתחלים `loss = 0`, עוברים על כל המשלוחים; לכל משלוח לא תקין מדפיסים את פרטיו (בעזרת `__str__` מסעיף א) ומוסיפים את ההפסד שלו.
4. אחרי הלולאה מדפיסים את `loss`.
def compensation(arr, flyTime):
loss = 0
for p in arr:
if flyTime > p.time:
print(p)
loss += p.num * p.price
print("loss:", loss)דוגמה: עבור `flyTime = 15` ומשלוחים: ורדים ( פרחים, שעות, ), צבעונים (, , ), חבצלות (, , ) - לא תקינים הוורדים והחבצלות, וההפסד .
סיבוכיות: , מעבר אחד על הרשימה.
תשובה: הפעולה `compensation` שלמעלה.
שאלה 5 · מעקב אחר ספירת ספרות ובחירת איבר מינימלי
נתונה הפעולה `secret` המקבלת כפרמטר מספר שלם וחיובי `num`.
def secret(num):
res1 = 0
res2 = 0
while num > 0:
res1 +=1
if num %2 == 0:
res2 +=1
num //= 10
return res1 - res2;עקבו בעזרת טבלת המעקב אחרי ביצוע הפעולה עבור `num = 37245` ורשמו מה תחזיר הפעולה.
תנו דוגמה למספר שלם וחיובי `num > 1000`, שעבורו הפעולה תחזיר 0.
מה מבצעת הפעולה `secret` עבור מספר `num` שלם וחיובי כלשהו?
נתונה הפעולה `sod()` הבאה המקבלת רשימה של מספרים שלמים חיוביים:
def sod(arr):
res = 0;
for i in range(len(arr)):
if secret(arr[i]) <= secret(arr[res]):
res = i;
return arr[res];עקבו באמצעות טבלת מעקב אחר ביצוע הפעולה `sod()` עבור הרשימה:
arr = [7245, 64, 14783, 32, 824, 199]ורשמו מה יהיה תוכן של הרשימה אחרי ביצוע הפעולה. אין צורך במעקב אחרי הפעולה `secret`.
מה מבצעת הפעולה `sod` באופן כללי עבור רשימה כלשהי של מספרים שלמים וחיוביים?
◂ פתרון מלא לשאלה 5
סעיף א
הפעולה תחזיר .
עוקבים אחרי הלולאה: בכל סיבוב `res1` גדל ב- (סופר ספרה), `res2` גדל אם `num` זוגי (כלומר אם ספרת האחדות שלו זוגית), ואחר כך מורידים את ספרת האחדות ב-`num //= 10`.
כעת `num = 0`, התנאי `num > 0` נכשל והלולאה מסתיימת.
הערך המוחזר: `res1 - res2` .
תשובה: הפעולה תחזיר .
למשל (כל הספרות זוגיות).
הפעולה מחזירה (מספר הספרות) פחות (מספר הספרות הזוגיות). התוצאה כאשר כל הספרות זוגיות.
דוגמה: . כל ארבע הספרות זוגיות, ולכן `res1` , `res2` , ומוחזר .
(גם , וכדומה מתאימים.)
תשובה: .
מחזירה את מספר הספרות האי-זוגיות של `num`.
•בכל סיבוב של הלולאה מטפלים בספרה אחת (ספרת האחדות), ומסירים אותה ב-`num //= 10`. לכן `res1` סופר את כל הספרות של `num`.
•הבדיקה `num %2 == 0` בודקת את הזוגיות של `num`, וזוגיות של מספר נקבעת לפי ספרת האחדות שלו. לכן `res2` סופר את הספרות הזוגיות.
•ההפרש `res1 - res2` הוא מספר הספרות שאינן זוגיות.
תשובה: הפעולה מחזירה את מספר הספרות האי-זוגיות במספר `num`.
סעיף ב
הרשימה לא משתנה: ; הפעולה מחזירה .
לפי סעיף א, `secret(x)` הוא מספר הספרות האי-זוגיות של `x`:
`secret(7245)` (7, 5), `secret(64)` , `secret(14783)` (1, 7, 3), `secret(32)` (3), `secret(824)` , `secret(199)` .
`res` הוא אינדקס; בכל סיבוב משווים את האיבר הנוכחי לאיבר שבאינדקס `res`, ומעדכנים אם הערך של `secret` קטן או שווה.
בסוף `res = 4`, והפעולה מחזירה `arr[4]` .
הפעולה רק קוראת את איברי הרשימה ואינה משנה אותם, לכן תוכן הרשימה אחרי הביצוע זהה לתוכן המקורי.
תשובה: תוכן הרשימה לא משתנה: `[7245, 64, 14783, 32, 824, 199]`. הפעולה מחזירה .
מחזירה את האיבר שיש בו הכי מעט ספרות אי-זוגיות; אם יש כמה כאלה - את האחרון מביניהם.
•`res` שומר את האינדקס של "המועמד הטוב ביותר" עד כה, כלומר האיבר עם הכי מעט ספרות אי-זוגיות (הערך של `secret`).
•איבר חדש מחליף את המועמד אם יש לו מספר קטן יותר או שווה של ספרות אי-זוגיות. בגלל ה"שווה", כשיש תיקו האיבר המאוחר יותר מחליף את הקודם (בדוגמה: החליף את , לשניהם ).
•הרשימה עצמה אינה משתנה.
תשובה: הפעולה מחזירה את האיבר ברשימה שמספר הספרות האי-זוגיות בו הוא הקטן ביותר; אם יש כמה איברים כאלה - את האחרון מביניהם ברשימה.
שאלה 6 · ניתוח פעולות על מחרוזות ורשימת מחרוזות
נתונה הפעולה `Secret ()` הבאה המקבלת מחרוזת:
def secret(str):
i = 0;
while i < len(str)//2:
if str[i] < 'a' or str[i]> 'z':
return False
i+=1
if len(str)%2!=0:
i+=1
while i < len(str):
if str[i] < 'A' or str[i] > 'Z':
return False;
i+=1
return Trueתנו דוגמה למחרוזת באורך של שישה תווים שעבורה הפעולה `secret` תחזיר ערך `True`.
נתונה טענה הבאה: אם זימון הפעולה `secret(str)` מחזיר ערך `True`, במחרוזת `str` יש רק אותיות (גדולות או קטנות). האם הטענה נכונה? הסבירו את תשובתכם.
נתונה הפעולה `mystery` המקבלת רשימת מחרוזות. הפעולה משתמשת בפעולה `secret`:
def mystery(arr):
i = 0
j = len(arr)
while i < j:
if secret(arr[i]) != secret(arr[j]):
return False;
i+=1
j-=1
return True;תנו דוגמה רשימה `arr` בגודל שישה איברים שעבורה הפעולה `mystery` תחזיר ערך `True`.
נתונה הטענה הבאה: אם זימון הפעולה `mystery (arr)` מחזיר ערך `True`, הרשימה `arr` לא כוללת זוג מחרוזות זהות אשר נמצאות בתאים סמוכים. האם הטענה נכונה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
למשל "abcDEF".
קודם נבין מה הפעולה בודקת:
•הלולאה הראשונה עוברת על האינדקסים עד `len(str)//2 - 1`, כלומר על החצי הראשון, ודורשת שכל תו יהיה אות קטנה ('a' עד 'z').
•אם האורך אי-זוגי, מדלגים על התו האמצעי (`i+=1`) בלי לבדוק אותו.
•הלולאה השנייה עוברת על שאר התווים עד הסוף ודורשת שכל אחד יהיה אות גדולה ('A' עד 'Z').
באורך : `len(str)//2` , לכן שלושת התווים הראשונים (אינדקסים ) צריכים להיות אותיות קטנות, ושלושת האחרונים (אינדקסים ) אותיות גדולות.
דוגמה: "abcDEF" - הלולאה הראשונה עוברת על 'a', 'b', 'c' (קטנות), האורך זוגי ולכן אין דילוג, והלולאה השנייה עוברת על 'D', 'E', 'F' (גדולות). מוחזר `True`.
תשובה: "abcDEF".
לא נכונה. באורך אי-זוגי התו האמצעי לא נבדק, למשל `secret("a1B")` מחזירה `True`.
כדי להפריך טענה מספיקה דוגמה נגדית אחת.
כשאורך המחרוזת אי-זוגי, הפעולה מבצעת `i+=1` ומדלגת על התו האמצעי בלי לבדוק אותו. לכן התו האמצעי יכול להיות כל תו - גם ספרה או סימן.
דוגמה נגדית: "a1B" (אורך ):
1. `len(str)//2` : הלולאה הראשונה בודקת רק את 'a' - אות קטנה, תקין. אחרי הלולאה `i = 1`.
2. האורך אי-זוגי, לכן `i` גדל ל- - דילגנו על '1'.
3. הלולאה השנייה בודקת רק את 'B' - אות גדולה, תקין.
4. מוחזר `True`, אבל במחרוזת יש את התו '1' שאינו אות.
(גם המחרוזת הריקה מחזירה `True`, כי אף לולאה לא מתבצעת.)
תשובה: הטענה לא נכונה. התו האמצעי במחרוזת באורך אי-זוגי אינו נבדק, למשל `secret("a1B")` מחזירה `True` אף שיש בה ספרה.
סעיף ב
בכתיבה כפי שהודפסה (`j = len(arr)`) כל רשימה לא ריקה גורמת לשגיאת חריגה מגבולות; עם התיקון `j = len(arr) - 1`, למשל `["abCD", "x", "abc", "Ab", "q", "efGH"]`.
הערה על הקוד: בקוד כפי שהודפס `j = len(arr)`. ברשימה באורך האינדקסים הם עד , ולכן כבר בסיבוב הראשון `arr[j]` הוא `arr[6]`, שאינו קיים, והפעולה נעצרת בשגיאה `IndexError`. כך קורה לכל רשימה שאינה ריקה, ולכן כפי שהודפסה אין רשימה בגודל שישה שעבורה תוחזר `True`.
ברור שהכוונה היא להשוות בין איברים סימטריים, מהקצוות פנימה, ולכן (לפי הוראה 9 בדף השער) נתקן את השורה ל-`j = len(arr) - 1`:
def mystery(arr):
i = 0
j = len(arr) - 1
while i < j:
if secret(arr[i]) != secret(arr[j]):
return False
i += 1
j -= 1
return Trueמה הפעולה בודקת: `i` מתחיל בתחילת הרשימה ו-`j` בסופה, והם מתקרבים זה לזה. בכל שלב משווים את התוצאה של `secret` על האיבר ה-`i` ועל האיבר ה-`j`. אם בזוג סימטרי אחד התוצאות שונות - מוחזר `False`. כלומר מוחזר `True` כאשר סדרת הערכים `secret(arr[0]), ..., secret(arr[n-1])` היא פלינדרום.
דוגמה: `arr = ["abCD", "x", "abc", "Ab", "q", "efGH"]`. ערכי `secret`:
- "abCD" - True (חצי ראשון קטנות, חצי שני גדולות); "efGH" - True.
- "x" - True (אורך : אין תווים בחצי הראשון, התו האמצעי מדולג, ואין תווים בחצי השני); "q" - True.
- "abc" - False (התו 'c' בחצי השני אינו אות גדולה); "Ab" - False (התו 'A' בחצי הראשון אינו אות קטנה).
אחרי הסיבוב השלישי `i = 3`, `j = 2`, הלולאה מסתיימת ומוחזר `True`.
(דוגמה פשוטה עוד יותר: שש מחרוזות זהות.)
תשובה: כפי שהודפס הקוד נכשל (`arr[len(arr)]`) לכל רשימה לא ריקה. אחרי התיקון `j = len(arr) - 1`, דוגמה: `["abCD", "x", "abc", "Ab", "q", "efGH"]`.
לא נכונה. למשל רשימה של שש מחרוזות "aB" זהות - `mystery` מחזירה `True`.
(בהמשך לתיקון `j = len(arr) - 1` מסעיף 1.)
`mystery` בודקת רק שהזוגות הסימטריים (הראשון והאחרון, השני ולפני האחרון וכן הלאה) מקבלים מ-`secret` את אותו ערך. היא בכלל לא משווה בין איברים סמוכים, ומחרוזות זהות תמיד מקבלות מ-`secret` אותו ערך - כך שהן לא יכולות לגרום ל-`False`.
דוגמה נגדית: `arr = ["aB", "aB", "aB", "aB", "aB", "aB"]`. כל האיברים זהים, ולכן בכל זוג סימטרי ערכי `secret` שווים (שניהם `True`), והפעולה מחזירה `True`. אבל ברשימה יש מחרוזות זהות בתאים סמוכים (למשל בתאים ו-).
תשובה: הטענה לא נכונה; למשל עבור שש מחרוזות "aB" הפעולה מחזירה `True` אף שיש מחרוזות זהות בתאים סמוכים.
שאלה 7 · מעקב אחר שני מצביעים בספירת זוגות
נתונה פעולה `what` הבאה. הפעולה מקבלת רשימה של מספרים שלמים `arr` ומספר שלם `num`.
הרשימה ממוינת בסדר עולה.
def what(arr, num):
c = 0
left = 0
right = len(arr)-1
while left < right :
if arr[left] + arr[right] >= num:
right-=1
else:
c+=(right - left)
left+=1
return cנתונה הרשימה הבאה:
arr = [1,3, 6, 11, 18, 21, 27, 35]עקבו בעזרת טבלת המעקב אחרי ביצוע זימון הפעולה `what(arr, 7)`. מה תהייה תוצאת הזימון?
עקבו בעזרת טבלת המעקב אחרי ביצוע זימון הפעולה `what(arr, 26)`. מה תהייה תוצאת הזימון?
מה מבצעת הפעולה `what(arr, num)` באופן כללי עבור רשימה של מספרים שלמים ממוינת בסדר עולה `arr` ומספר שלם `num`.
מהי הסיבוכיות של הפעולה `what`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
בכל סיבוב מחשבים `arr[left] + arr[right]`: אם הסכום גדול או שווה ל- מקטינים את `right`; אחרת מוסיפים ל-`c` את `right - left` ומגדילים את `left`.
עכשיו `left = 1`, `right = 1`, התנאי `left < right` נכשל, ומוחזר `c = 1`.
(אכן, הזוג היחיד שסכומו קטן מ- הוא .)
תשובה: תוצאת הזימון היא .
סעיף ב
אותו תהליך, עם `num = 26`:
עכשיו `left = 3`, `right = 3`, הלולאה מסתיימת ומוחזר `c = 11`.
בדיקה: הזוגות שסכומם קטן מ- הם עם (5 זוגות), עם (4 זוגות), עם (2 זוגות), סך הכול .
תשובה: תוצאת הזימון היא .
סעיף ג
מחזירה את מספר הזוגות של איברים במקומות שונים () שסכומם קטן מ-`num`.
הפעולה סופרת זוגות של אינדקסים שעבורם `arr[i] + arr[j] < num`.
למה זה עובד (הרשימה ממוינת):
1. אם `arr[left] + arr[right] < num`, אז לכל בין `left+1` ל-`right` מתקיים `arr[left] + arr[k] <= arr[left] + arr[right] < num`. לכן כל `right - left` הזוגות שבהם `left` הוא האיבר הקטן מתאימים, סופרים את כולם בבת אחת, וממשיכים ל-`left` הבא.
2. אם `arr[left] + arr[right] >= num`, אז גם עם כל איבר אחר שנשאר בטווח (כולם גדולים או שווים ל-`arr[left]`) הסכום עם `arr[right]` יהיה לפחות `num`. לכן `arr[right]` לא משתתף באף זוג מתאים, ומוציאים אותו (`right-=1`).
תשובה: הפעולה מחזירה את מספר הזוגות של איברים מהרשימה (במקומות שונים) שסכומם קטן מ-`num`.
סעיף ד
בכל סיבוב של הלולאה מתבצעת בדיוק אחת משתי הפעולות: `left` גדל ב- או `right` קטן ב-. לכן המרחק `right - left` קטן ב- בכל סיבוב. בהתחלה הוא והלולאה נעצרת כשהוא , לכן יש בדיוק סיבובים, וכל סיבוב בזמן קבוע.
תשובה: , כאשר אורך הרשימה.
שאלה 8 · מחלקת לקוח מים: עדכון קריאה ותשלום
לפי התקנון של רשות המים, חיוב עבור צריכת מים ביתית מתבצע לפי השיטה הבאה:
•צריכת המים נקבעת על פי קריאת מד המים. ההפרש בין הקריאה הנוכחית לקריאה הקודמת קובע את כמות הצריכה.
•תעריפי המים אחידים בכל הארץ וקובעת אותם הרשות הממשלתית למים וביוב. סכום החיוב הוא מכפלה של כמויות המים שנצרכו בתקופת החשבון בתעריפי המים.
•צריכה ביתית כוללת שני תעריפים:
•תעריף מוזל המתייחס לכמות של שבעה מ"ק לכל נפש המתגוררת ביחידת הדיור.
•ותעריף גבוה המתייחס ליתרת כמות המים שנצרכה ביחידת הדיור בתקופת החשבון.
אם הצריכה הביתית הייתה 35 מ"ק מים ובדירה מתגוררות ארבע נפשות יש לשלם עבור מ"ק לפי התעריף המוזל ועבור מ"ק לפי התעריף הגבוה.
חברת "מי הארץ" החליטה למחשב את תהליך גביית התשלום. לצורך כך הגדירו את המחלקה לקוח (`Client`) המייצגת יחידת דיור.
למחלקה יש התכונות הבאות:
•`address` – כתובת, מטיפוס מחרוזת.
•`persons` – מספר נפשות, מטיפוס מספר שלם.
•`current` – קריאת מד המים נוכחית, מטיפוס מספר שלם.
•`prev` – קריאת מד המים קודמת, מטיפוס מספר שלם.
במחלקה הוגדרה פעולה בונה (בנאי) המקבל פרמטרים לכל התכונות.
כתבו במחלקה `Client` פעולה לעדכון קריאת מד המים נוכחית. הפעולה מקבלת מספר שלם `new_current` ומעדכנת תכונות `current` ו- `prev` בהתאם.
כותרת הפעולה:
update_current(new_current)כתבו במחלקה `Client` את הפעולה לחישוב תשלום. הפעולה מקבלת שני תעריפים `rate1` (תעריף מוזל) ו-`rate2` (תעריף גבוה). הפעולה תחזיר סכום לתשלום לפי תקנון של רשות המים.
כותרת הפעולה:
payment(rate1, rate2)הנהלת חברת "מי הארץ" החליטה להציע ללקוחות שלה בדיקת מד המים בחינם. בשלב ראשון הוחלט לבדוק את מד המים אצל לקוחות שהתשלום שלהם גבוה ביחס למשפחות עם אותו מספר נפשות.
כתבו פעולה חיצונית המקבלת רשימת לקוחות (הפניות לעצמים מטיפוס `Client`), מספר שלם חיובי `num` המציין את מספר הנפשות ביחידת הדיור ושני תעריפים `rate1` (מוזל) ו- `rate2` (גבוה). הפעולה תדפיס כתובת של כל הלקוחות שיש להם `num` נפשות ביחידת דיור והתשלום שלהם גבוה מהממוצע התשלומים של לקוחות עם אותו מספר נפשות.
כותרת הפעולה:
proposal(arr, num, rate1, rate2)◂ פתרון מלא לשאלה 8
סעיף א
`self.prev = self.current` ואחר כך `self.current = new_current`.
מבוקש: לקבל קריאה חדשה של המונה. הקריאה שהייתה עד עכשיו "נוכחית" הופכת לקריאה הקודמת, והקריאה החדשה הופכת לנוכחית.
1. קודם מעבירים את `current` אל `prev`. הסדר חשוב: אם נעדכן קודם את `current`, הערך הישן שלו יאבד.
2. אחר כך שמים ב-`current` את `new_current`.
הקוד כולל גם את הבנאי הנתון ואת הפעולה של סעיף ב:
class Client:
def __init__(self, address, persons, current, prev):
self.address = address
self.persons = persons
self.current = current
self.prev = prev
def update_current(self, new_current):
self.prev = self.current
self.current = new_current
def payment(self, rate1, rate2):
usage = self.current - self.prev
low_limit = 7 * self.persons
if usage <= low_limit:
return usage * rate1
return low_limit * rate1 + (usage - low_limit) * rate2תשובה: הפעולה `update_current` שלמעלה: `self.prev = self.current`, ואז `self.current = new_current`.
סעיף ב
צריכה ; עד מ"ק בתעריף `rate1`, והיתרה בתעריף `rate2`.
נתון: קריאה נוכחית, קריאה קודמת, מספר נפשות ושני תעריפים.
מבוקש: הסכום לתשלום.
1. הצריכה בתקופה: `usage = current - prev`.
2. הכמות בתעריף המוזל: `low_limit = 7 * persons` מ"ק.
3. אם הצריכה לא עולה על `low_limit`, כל הצריכה בתעריף המוזל: `usage * rate1`.
4. אחרת: `low_limit` מ"ק בתעריף המוזל, והיתרה `usage - low_limit` בתעריף הגבוה:
`low_limit * rate1 + (usage - low_limit) * rate2`.
הפעולה נמצאת בקוד שבסעיף א (הפעולה `payment`).
דוגמה (לפי הדוגמה בשאלה): נפשות, צריכה מ"ק, ונניח `rate1 = 2`, `rate2 = 5`: הסכום . אם הצריכה מ"ק בלבד, כל הכמות מוזלת: .
תשובה: הפעולה `payment` שמחזירה `usage * rate1` אם `usage <= 7 * persons`, ואחרת `7 * persons * rate1 + (usage - 7 * persons) * rate2`.
סעיף ג
מעבר ראשון: ממוצע `payment` של הלקוחות עם `num` נפשות; מעבר שני: הדפסת הכתובת של כל לקוח כזה שהתשלום שלו גבוה מהממוצע.
מבוקש: למצוא, מבין הלקוחות עם `num` נפשות, את אלה שמשלמים יותר מהממוצע של קבוצתם.
1. מעבר ראשון על הרשימה: לכל לקוח עם `persons == num` מחשבים `payment(rate1, rate2)` (מסעיף ב), צוברים לסכום `total` וסופרים ב-`count`.
2. אם `count == 0` אין לקוחות כאלה, אין ממוצע ואין מה להדפיס - יוצאים מהפעולה (כך גם נמנעים מחילוק באפס).
3. הממוצע: `avg = total / count`.
4. מעבר שני: לכל לקוח עם `num` נפשות שהתשלום שלו גדול מ-`avg` מדפיסים את הכתובת.
אי אפשר להסתפק במעבר אחד, כי את הממוצע יודעים רק אחרי שעוברים על כל הקבוצה.
def proposal(arr, num, rate1, rate2):
total = 0
count = 0
for c in arr:
if c.persons == num:
total += c.payment(rate1, rate2)
count += 1
if count == 0:
return
avg = total / count
for c in arr:
if c.persons == num and c.payment(rate1, rate2) > avg:
print(c.address)דוגמה: `rate1 = 2`, `rate2 = 5`, `num = 4`, וארבעה לקוחות בני נפשות שהתשלומים שלהם . הממוצע , ולכן תודפס רק הכתובת של הלקוח שמשלם .
סיבוכיות: , שני מעברים על הרשימה.
תשובה: הפעולה `proposal` שלמעלה.
שאלה 9 · משקל נקי של מספר ורשימות ממוינות לפיו
נתונות ההגדרות הבאות:
•"משקל נקי" של מספר שלם חיובי הוא סכום הספרות של המספר בלי הספרה השמאלית ביותר ובלי הספרה הימנית ביותר.
ה"משקל הנקי" של 123 הוא 2.
ה"משקל הנקי" של -12345 הוא .
ה"משקל הנקי" של 18 הוא 0.
ה"משקל הנקי" של 9 הוא 0.
•רשימה של מספרים שלמים נקראת "רשימה ממוינת לפי משקלים" אם ה"משקלים" של כל איברי הרשימה ממוינים בסדר עולה ממש (ללא חזרות של משקל).
לדוגמה: הרשימה הבאה "ממוינת לפי משקלים"
[35, 923, 781, 12349,1892]כתבו פעולה אשר מקבלת מספר שלם חיובי ומחזירה את ה"משקל הנקי" שלו.
כתבו פעולה אשר מקבלת רשימה של מספרים שלמים ומחזירה ערך `True` אם הרשימה היא "רשימה ממוינת לפי משקלים", ולא הפעולה תחזיר ערך `False`.
כתבו פעולה אשר מקבלת שתי רשימות של מספרים שלמים וחיוביים. כל אחת מהרשימות היא "רשימה ממוינת לפי משקלים". הפעולה תדפיס את כל האיברים עם "משקל הנקי" ייחודי (כלומר את כל האיברים מהרשימה הראשונה ש"המשקל הנקי" שלהם לא מופיע ברשימה השני ואת ככל האיברים מהרשימה השנייה ש"המשקל הנקי" שלהם לא מופיע ברשימה הראשונה).
לדוגמה: עבור שתי הרשימות
הפעולה תדפיס:
923, 358, 12349, 5821, 1742, 36621מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים ב' ו- ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
מורידים את ספרת האחדות, ואז סוכמים ספרות כל עוד נשארו לפחות שתי ספרות (כך הספרה השמאלית לא נכנסת).
מבוקש: סכום כל הספרות חוץ מהראשונה והאחרונה. נקרא לפעולה `clean_weight(num)`.
1. בדוגמה בשאלה מופיע גם מספר שלילי (), לכן מתחילים מ-`num = abs(num)`; זה לא משנה מספרים חיוביים.
2. מורידים את הספרה הימנית: `num //= 10`.
3. כל עוד `num >= 10` (נשארו לפחות שתי ספרות), ספרת האחדות הנוכחית אינה הספרה השמאלית ביותר, ולכן מוסיפים אותה לסכום ומורידים אותה.
4. כשנשארת ספרה אחת (`num < 10`) - זו הספרה השמאלית, והיא לא נספרת. מחזירים את הסכום.
מספר חד-ספרתי או דו-ספרתי מחזיר , כי אחרי שלב 2 נשארת לכל היותר ספרה אחת.
def clean_weight(num):
num = abs(num)
num //= 10
s = 0
while num >= 10:
s += num % 10
num //= 10
return sבדיקה: , מוסיפים , נשאר : מוחזר . , מוסיפים , נשאר : מוחזר . : מוחזר . : מוחזר .
תשובה: הפעולה `clean_weight` שלמעלה.
סעיף ב
עוברים על זוגות סמוכים; אם `clean_weight(arr[i]) >= clean_weight(arr[i+1])` מחזירים `False`, ובסוף `True`.
סדר עולה ממש מתקיים בדיוק כאשר כל איבר קטן ממש מהאיבר שאחריו, לכן מספיק לבדוק זוגות סמוכים.
1. עוברים על האינדקסים .
2. אם המשקל של `arr[i]` גדול או שווה למשקל של `arr[i+1]`, הסדר אינו עולה ממש (גם משקל שחוזר פוסל), ומחזירים מיד `False`.
3. אם לא נמצא זוג כזה, מחזירים `True`. (רשימה ריקה או בת איבר אחד נחשבת ממוינת.)
def is_weight_sorted(arr):
for i in range(len(arr) - 1):
if clean_weight(arr[i]) >= clean_weight(arr[i + 1]):
return False
return Trueבדיקה עם הדוגמה : המשקלים עולים ממש, לכן `True`.
תשובה: הפעולה `is_weight_sorted` שלמעלה.
סעיף ג
מיזוג בשני מצביעים לפי המשקל: משקל קטן יותר - מדפיסים ומתקדמים; משקלים שווים - מדלגים על שניהם; בסוף מדפיסים את השאריות.
נתון: שתי רשימות, בכל אחת המשקלים עולים ממש (ולכן כל משקל מופיע ברשימה לכל היותר פעם אחת).
מבוקש: להדפיס את האיברים שהמשקל שלהם מופיע רק באחת הרשימות. בדוגמה ההדפסה מסודרת לפי המשקל, כמו מיזוג של שתי רשימות ממוינות.
רעיון - מיזוג עם שני מצביעים, `i` ברשימה הראשונה ו-`j` בשנייה:
1. משווים את המשקל `w1` של `arr1[i]` למשקל `w2` של `arr2[j]`.
2. אם `w1 < w2`: המשקל `w1` לא יכול להופיע בהמשך הרשימה השנייה (שם המשקלים רק גדלים), ולכן `arr1[i]` ייחודי - מוסיפים אותו לפלט ומקדמים את `i`.
3. אם `w2 < w1`: באותו אופן `arr2[j]` ייחודי - מוסיפים ומקדמים את `j`.
4. אם המשקלים שווים: שני האיברים אינם ייחודיים - מקדמים את שני המצביעים בלי להדפיס.
5. כשאחת הרשימות נגמרת, כל האיברים שנשארו ברשימה השנייה ייחודיים (המשקלים שלהם גדולים מכל המשקלים של הרשימה שנגמרה) - מוסיפים את כולם.
6. מדפיסים את האיברים שנאספו, מופרדים בפסיק, כמו בדוגמה.
def print_unique(arr1, arr2):
i = 0
j = 0
res = []
while i < len(arr1) and j < len(arr2):
w1 = clean_weight(arr1[i])
w2 = clean_weight(arr2[j])
if w1 < w2:
res.append(arr1[i])
i += 1
elif w2 < w1:
res.append(arr2[j])
j += 1
else:
i += 1
j += 1
while i < len(arr1):
res.append(arr1[i])
i += 1
while j < len(arr2):
res.append(arr2[j])
j += 1
print(", ".join(str(x) for x in res))מעקב קצר על הדוגמה (משקלים בסוגריים): ו- שווים - דילוג; - מדפיסים ; - מדפיסים ; ו- שווים - דילוג; - מדפיסים ; גדול מ-, , - מדפיסים שלושתם; ו- שווים - דילוג. הפלט: `923, 358, 12349, 5821, 1742, 36621`, כמו בדוגמה.
תשובה: הפעולה `print_unique` שלמעלה.
סעיף ד
סעיף ב: ; סעיף ג: (כשמספר הספרות של כל מספר חסום).
חישוב "משקל נקי" עובר על הספרות של המספר, כלומר , כאשר מספר הספרות. עבור מספרים שלמים רגילים חסום (ולכן זמן קבוע).
•סעיף ב: לולאה אחת על זוגות סמוכים, ובכל סיבוב שני חישובי משקל. סך הכול , כלומר .
•סעיף ג: בכל סיבוב של המיזוג לפחות אחד המצביעים מתקדם, ושני המצביעים רק מתקדמים, לכן יש לכל היותר סיבובים ( אורכי הרשימות). כל סיבוב . סך הכול , כלומר . לא צריך לולאה מקוננת, כי שתי הרשימות ממוינות לפי משקל.
תשובה: סעיף ב - ; סעיף ג - .
שאלה 10 · רשימה ממוינת לפי שארית: בדיקה ומיון
נתונה הגדרה הבאה:
רשימה של מספרים שלמים חיוביים נקראת "רשימה ממוינת לפי שארית של k" אם היא עונה על כלל הבא:
•בתחילת הרשימה מופיעים מספרים שמתחלקים ב- k ללא שארית (עם שארית 0).
•אחריהם מופיעים מספרים שמתחלקים ב- k עם שארית 1.
•אחריהם מופיעים מספרים שמתחלקים ב- k עם שארית 2.
•אחריהם מופיעים מספרים שמתחלקים ב- k עם שארית 3.
•וכך הלאה.
לדוגמה:
הרשימה הבאה "ממוינת לפי שארית של 4":
[4, 8, 1, 13, 9, 2, 7, 15]הרשימה הבאה "ממוינת לפי שארית של 5":
[15, 1,2, 7, 13, 8, 4, 9]כתבו פעולה המקבלת רשימה של מספרים שלמים חיוביים `arr` ומספר שלם חיובי `k` ובודקת אם היא "רשימה ממוינת לפי שארית של k". אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`.
כתבו פעולה המקבל רשימה של מספרים שלמים חיוביים `arr` ומספר שלם וחיובי `k`. הפעולה תחזיר רשימה חדשה "הממוינת לפי k" הכולל את כל הערכים של הרשימה `arr`.
מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 10
סעיף א
מחזירים `False` אם קיים עם `arr[i] % k > arr[i+1] % k`, אחרת `True`.
לפי ההגדרה, השאריות בחלוקה ב-`k` לאורך הרשימה צריכות להיות בסדר עולה (לא ממש - כמה מספרים יכולים להיות עם אותה שארית). שארית שחסרה (למשל אין מספרים עם שארית 2) לא פוסלת.
1. עוברים על כל זוג סמוך `arr[i]`, `arr[i+1]`.
2. אם השארית של `arr[i]` גדולה מהשארית של `arr[i+1]`, מצאנו מספר עם שארית קטנה שמופיע אחרי מספר עם שארית גדולה - מחזירים `False`.
3. אם לא נמצא זוג כזה - מחזירים `True`.
def is_sorted_by_rem(arr, k):
for i in range(len(arr) - 1):
if arr[i] % k > arr[i + 1] % k:
return False
return Trueבדיקה: עבור ו- השאריות - לא יורדות, לכן `True`. עבור ו- השאריות - `True`.
תשובה: הפעולה `is_sorted_by_rem` שלמעלה.
סעיף ב
מחלקים את האיברים ל-`k` רשימות עזר לפי `x % k`, ומשרשרים אותן לפי השארית .
הרעיון: "מיון בדליים". השארית בחלוקה ב-`k` היא אחד מ-`k` ערכים: .
1. יוצרים `k` רשימות ריקות (`buckets`), אחת לכל שארית.
2. עוברים על `arr` ושמים כל איבר `x` בדלי שמספרו `x % k`.
3. בונים רשימה חדשה `res`: מוסיפים את כל איברי דלי , אחריהם את איברי דלי , וכך הלאה עד דלי .
4. מחזירים את `res`. הרשימה המקורית לא משתנה.
def sort_by_rem(arr, k):
buckets = []
for r in range(k):
buckets.append([])
for x in arr:
buckets[x % k].append(x)
res = []
for r in range(k):
for x in buckets[r]:
res.append(x)
return resדוגמה: עבור ו- הדליים הם: שארית : ; שארית : ; שארית : ; שארית : . מוחזר .
תשובה: הפעולה `sort_by_rem` שלמעלה.
סעיף ג
סעיף א: ; סעיף ב: .
•סעיף א: לולאה אחת על זוגות סמוכים, וכל בדיקה בזמן קבוע: .
•סעיף ב: יצירת `k` דליים - ; פיזור האיברים לדליים - ; איסוף מכל הדליים - (עוברים על כל הדליים ועל כל האיברים). סך הכול . אין צורך במיון השוואות שעולה .
תשובה: סעיף א - ; סעיף ב - .
שאלה 11 · תמורות של מספרים ורשימות סופר תמורה
נתונות ההגדרות הבאות:
•זוג מספרים שלמים חיוביים שונים זה מזה נקרא "תמורה" (פרמוטציה) אם הם מורכבים מאותן הספרות אבל סדר המופעים של הספרות שונה.
זוג מספרים 123 ו- 312 הוא "תמורה".
זוג מספרים 1234 ו- 3214 הוא "תמורה".
זוג מספרים 1223 ו- 1323 לא "תמורה".
זוג מספרים 123 ו- 123 לא "תמורה".
•רשימה של מספרים שלמים חיוביים נקראת "רשימת תמורות" אם יש בה לפחות זוג אחד שהוא "תמורה".
•רשימת רשימות של מספרים שלמים חיוביים (רשימה שכל איבר שבה הוא רשימה) נקראת "סופר תמורה" אם כל איבר שלה היא "רשימת תמורות".
כתבו פעולה המקבלת זוג מספרים שלמים חיוביים ובודקת אם הוא "תמורה".
אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_perm(num1, num2)כתבו פעולה המקבלת רשימת רשימות של מספרים שלמים חיוביים (רשימה שכל איבר שבה הוא רשימה של מספרים) ובודקת אם היא "סופר תמורה".
אם כן – הפעולה תחזיר ערך `True`, ולא – הפעולה תחזיר ערך `False`.
כותרת הפעולה:
is_super_perm(arr)מהי הסיבוכיות של הפעולות `is_perm` ו- `is_super_perm` ? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
אם המספרים שווים - `False`; אחרת משווים מוני ספרות (מערך של 10): `True` אם כל המונים מתאפסים.
מבוקש: לבדוק ששני המספרים שונים ושהם בנויים מאותן ספרות, כל ספרה באותו מספר מופעים.
1. אם `num1 == num2` - לפי ההגדרה זו לא "תמורה" (כמו 123 ו-123), מחזירים `False`.
2. יוצרים מערך מונים `count` בגודל (מונה לכל ספרה עד ).
3. עוברים על ספרות `num1` (בעזרת `% 10` ו-`// 10`) ומגדילים את המונה של כל ספרה.
4. עוברים על ספרות `num2` ומקטינים את המונה של כל ספרה.
5. אם כל המונים חזרו ל-, לשני המספרים בדיוק אותן ספרות עם אותן כמויות - מחזירים `True`; אחרת `False`.
מכיוון שהמספרים שונים אבל בעלי אותן ספרות, סדר הספרות בהכרח שונה - כפי שההגדרה דורשת.
def is_perm(num1, num2):
if num1 == num2:
return False
count = [0] * 10
while num1 > 0:
count[num1 % 10] += 1
num1 //= 10
while num2 > 0:
count[num2 % 10] -= 1
num2 //= 10
for c in count:
if c != 0:
return False
return Trueבדיקה: 123 ו-312 - המונים של 1, 2, 3 עולים ל-1 ויורדים ל-0: `True`. 1223 ו-1323 - המונה של 2 נשאר והמונה של 3 נשאר : `False`. 123 ו-123 - שווים: `False`.
תשובה: הפעולה `is_perm` שלמעלה.
סעיף ב
פעולת עזר `is_perm_list` בודקת כל הזוגות ברשימה בעזרת `is_perm`; `is_super_perm` מחזירה `False` אם רשימה פנימית כלשהי אינה רשימת תמורות.
מפרקים את הבעיה לשתי פעולות:
1. פעולת עזר `is_perm_list(lst)` - בודקת אם רשימה אחת היא "רשימת תמורות": עוברים על כל הזוגות בשתי לולאות מקוננות; אם `is_perm(lst[i], lst[j])` מחזירה `True` מצאנו זוג, ומחזירים `True`. אם נגמרו הזוגות בלי למצוא - `False`.
2. `is_super_perm(arr)` - עוברת על כל רשימה פנימית; אם אחת מהן אינה "רשימת תמורות", מחזירים מיד `False`. אם כולן עברו את הבדיקה - `True`.
def is_perm_list(lst):
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if is_perm(lst[i], lst[j]):
return True
return False
def is_super_perm(arr):
for lst in arr:
if not is_perm_list(lst):
return False
return Trueדוגמה: עבור `[[5, 123, 7, 312], [21, 12], [4, 1234, 99, 4321]]` בכל רשימה פנימית יש זוג שהוא תמורה (; ; ), לכן מוחזר `True`. עבור `[[5, 123, 7, 312], [21, 13]]` הרשימה השנייה אינה רשימת תמורות, לכן `False`.
תשובה: הפעולות `is_perm_list` ו-`is_super_perm` שלמעלה.
סעיף ג
`is_perm`: (מספר הספרות); `is_super_perm`: - ריבועי באורך הרשימות הפנימיות.
נסמן ב- את מספר הספרות של המספרים, ב- את מספר הרשימות הפנימיות וב- את האורך המרבי של רשימה פנימית.
•`is_perm`: שתי לולאות על הספרות של שני המספרים () ולולאה על מונים (). סך הכול ; עבור מספרים שלמים רגילים זה זמן קבוע.
•`is_super_perm`: לכל רשימה פנימית באורך , `is_perm_list` בודקת במקרה הגרוע את כל הזוגות, וכל בדיקה , כלומר . על רשימות: , ועבור חסום .
תשובה: `is_perm` - (קבוע עבור מספרים רגילים); `is_super_perm` - .
שאלה 12 · מעקב אחר רקורסיה: רצף ספרות זהות
נתונות הפעולות הבאות:
def what(num):
return do_what(num,1);
def do_what(num, c):
if num < 10:
return c
if num%10 == (num //10) % 10:
a = do_what(num//10, c+1)
else:
a = do_what(num//10, 1)
return max(a, c)
def secret(arr):
return do_secret(arr, 0, len(arr)-1)
def do_secret(arr, left, right):
if left == right:
return arr[left]
if what (arr[left]) < what(arr[right]):
return do_secret(arr, left +1, right)
return do_secret(arr, left, right -1)עקבו אחרי זימון `what (5777922)` רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `what (num)` עבור מספר שלם חיובי `num`?
עקבו אחרי זימון `secret (arr)` עבור הרשימה
arr = [777922,111,623,221333,10000,22133,211,1001,99790]ורשמו את תוצאות הזימון.
האם קיימת רשימה של מספרים שלמים חיוביים `arr` בגודל חמישה איברים לפחות, שעבורה זימון הפעולה `secret (arr)` יחזיר 123? הסבירו את תשובתכם.
מה מבצעת הפעולה `secret (arr)` עבור רשימה מספרים שלמים וחיוביים `arr`?
◂ פתרון מלא לשאלה 12
סעיף א
`what(5777922)` מזמנת `do_what(5777922, 1)`. בכל קריאה משווים את ספרת האחדות (`num%10`) לספרת העשרות (`(num//10)%10`): אם הן שוות, הרצף הנוכחי מתארך וממשיכים עם `c+1`; אחרת מתחיל רצף חדש עם `1`. הערך המוחזר הוא המקסימום בין התוצאה מהקריאה הפנימית ל-`c`.
שלב הקריאות (מלמעלה למטה):
שלב החזרה (מלמטה למעלה), `max(a, c)`:
תשובה: `what(5777922)` מחזירה .
סעיף ב
מחזירה את אורך הרצף הארוך ביותר של ספרות זהות סמוכות ב-`num`.
•הפרמטר `c` הוא אורך הרצף הנוכחי של ספרות זהות שמסתיים בספרת האחדות של `num` (מתחיל ב-).
•כשספרת האחדות שווה לספרת העשרות, הרצף ממשיך, ולכן עוברים לקריאה הבאה עם `c+1`. כשהן שונות, מתחיל רצף חדש באורך .
•כל קריאה מחזירה את המקסימום בין אורך הרצף הנוכחי `c` לבין מה שהתקבל מהקריאות הבאות, לכן בסוף מתקבל אורך הרצף הארוך ביותר.
בסעיף א: ב-5777922 הרצפים הם 5, 777, 9, 22, והארוך ביותר הוא 777, באורך .
תשובה: הפעולה מחזירה את אורך הרצף הארוך ביותר של ספרות זהות רצופות במספר `num`.
סעיף ג
לפי סעיף ב, `what` של כל איבר הוא אורך הרצף הארוך ביותר של ספרות זהות:
`secret(arr)` מזמנת `do_secret(arr, 0, 8)`. בכל קריאה: אם `what(arr[left]) < what(arr[right])` מקדמים את `left`, אחרת מקטינים את `right`. עוצרים כש-`left == right`.
תשובה: `secret(arr)` מחזירה .
סעיף ד
כן, למשל `[123, 45, 6, 789, 10]`.
ב-123 אין ספרות זהות סמוכות, לכן `what(123) = 1` - הערך הקטן ביותר האפשרי. לפי סעיף ה, `secret` מחזירה את האיבר הראשון (השמאלי ביותר) מבין האיברים עם `what` מרבי. לכן צריך שלכל האיברים `what` יהיה , ו-123 יהיה הראשון ברשימה.
דוגמה: `arr = [123, 45, 6, 789, 10]`. לכל האיברים `what = 1`. בכל קריאה התנאי `1 < 1` לא מתקיים, ולכן תמיד `right` קטן ו-`left` נשאר : , ומוחזר `arr[0]` .
תשובה: כן. למשל `[123, 45, 6, 789, 10]`: לכל האיברים אין ספרות זהות סמוכות, ו-123 הוא הראשון, ולכן הוא מוחזר.
סעיף ה
מחזירה את האיבר שבו רצף הספרות הזהות הארוך ביותר; אם יש כמה כאלה - את הראשון מביניהם (השמאלי ביותר).
`do_secret` מצמצמת את הטווח `[left, right]` מהקצוות: בכל שלב היא מוציאה את האיבר שבקצה שיש לו `what` קטן יותר, עד שנשאר איבר אחד.
נסמן ב- את הערך המרבי של `what` ברשימה, וב- את האינדקס הראשון שבו `what` שווה ל-. האיבר ב- אף פעם לא מוצא:
•הוא לא מוצא כקצה שמאלי, כי לשם כך צריך `what(arr[p]) < what(arr[right])`, כלומר ערך גדול מ- - בלתי אפשרי.
•הוא לא מוצא כקצה ימני, כי לשם כך צריך `what(arr[left]) >= what(arr[p]) = M` עם `left < p`, אבל לפני אין איבר עם הערך .
כיוון שבכל קריאה הטווח קטן באחד, בסוף נשאר רק . (בסעיף ג: , ו-10000 מוחזר.)
תשובה: הפעולה מחזירה את האיבר ברשימה שבו רצף הספרות הזהות הסמוכות הוא הארוך ביותר; אם יש כמה כאלה - את הראשון מביניהם ברשימה.