מבחן מה"ט אלגוריתמיקה ותכנות (Python) 97103 - קיץ 2026 מועד א'
הנדסת תוכנה · סמל 97103 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Python), קיץ 2026 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: מבחן ב-Python (עמוד 2)
בכל מבחן 10 שאלות.
חלק א' – 36 נקודות
שאלות 1–4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה – 12 נקודות.
חלק ב' – 30 נקודות
שאלות 5–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
חלק ג' – 34 נקודות
שאלות 8–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 17 נקודות.
בסך הכול: 100 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחרוזת ייחודית: בדיקת תווים כפולים
מחרוזת נקראת "מחרוזת ייחודית" אם כל תו המופיע בה מופיע פעם אחת בלבד (כלומר, אין בה תווים כפולים).
•המחרוזת "abc12!" היא מחרוזת ייחודית;
•המחרוזת "aA12" היא מחרוזת ייחודית (האות 'a' שונה מ-'A');
•המחרוזת "apple1" אינה ייחודית (התו 'p' מופיע פעמיים);
•המחרוזת "121" אינה ייחודית (התו '1' מופיע פעמיים).
כתבו פונקציה המקבלת מחרוזת ובודקת אם היא "ייחודית". אם כן – הפונקציה תחזיר ערך True, ואם לא – הפונקציה תחזיר ערך False.
כתבו קטע קוד הקולט סדרת מחרוזות עד אשר נקלטת מחרוזת המתחילה באות 'R'. בסיום יש להדפיס כמה מחרוזות מתוך המחרוזות שנקלטו (לא כולל מחרוזת הסיום) היו "מחרוזות ייחודיות".
◂ פתרון מלא לשאלה 1
סעיף א
משווים כל זוג תווים במקומות ; אם נמצא זוג שווה מחזירים False, ואם לא נמצא – True.
הרעיון: מחרוזת אינה ייחודית אם יש בה שני מקומות שונים שבהם אותו תו. לכן נשווה כל תו לכל התווים שאחריו:
1. לולאה חיצונית עוברת על המקום i מ-0 עד הסוף.
2. לולאה פנימית עוברת על המקום j מ-`i + 1` עד הסוף (כך לא משווים תו לעצמו, וכל זוג נבדק פעם אחת).
3. ברגע שנמצא `s[i] == s[j]` – יש תו כפול, ומחזירים False מיד (אין טעם להמשיך).
4. אם הלולאות הסתיימו בלי למצוא זוג שווה – כל התווים שונים, ומחזירים True.
ההשוואה `==` בין תווים מבחינה בין אות קטנה לגדולה, ולכן "aA12" ייחודית, כנדרש.
def is_unique(s):
for i in range(len(s)):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
return False
return True•עבור "apple1": כאשר ו- מתקיים `s[1] == s[2] == 'p'`, ומוחזר False.
•עבור "abc12!": אף זוג אינו שווה, ומוחזר True.
סיבוכיות: עבור מחרוזת באורך n נבדקים לכל היותר זוגות, כלומר .
תשובה: הפונקציה `is_unique` שלמעלה.
סעיף ב
לולאת while עם קליטה לפני הלולאה ובסופה; לכל מחרוזת שאינה מחרוזת הסיום מזמנים את `is_unique` ומגדילים מונה; בסוף מדפיסים את המונה.
הרעיון: זו לולאת זקיף – מספר המחרוזות לא ידוע מראש, והקלט נעצר במחרוזת שמתחילה ב-'R'.
1. קולטים מחרוזת ראשונה לפני הלולאה.
2. תנאי הלולאה: המחרוזת אינה מתחילה ב-'R'. כדי לא לגשת ל-`s[0]` במחרוזת ריקה, בודקים קודם שהאורך גדול מ-0 (מחרוזת ריקה אינה מתחילה ב-'R', ולכן היא מחרוזת רגילה ונבדקת).
3. בגוף הלולאה בודקים את המחרוזת בעזרת הפונקציה מסעיף א, ואם היא ייחודית מגדילים את המונה `count` ב-1. בסוף הגוף קולטים את המחרוזת הבאה.
4. מחרוזת הסיום מסיימת את הלולאה לפני שהיא נבדקת, ולכן היא לא נספרת – כנדרש.
5. אחרי הלולאה מדפיסים את המונה.
count = 0
s = input()
while not (len(s) > 0 and s[0] == 'R'):
if is_unique(s):
count += 1
s = input()
print(count)דוגמה: עבור הקלט "abc", "aab", "xyz", "Rest" – המחרוזות "abc" ו-"xyz" ייחודיות, "aab" לא, ו-"Rest" היא מחרוזת הסיום. יודפס 2.
תשובה: קטע הקוד שלמעלה.
שאלה 2 · ספרה מובילה ושלשות סמוכות ברשימה
"ספרה מובילה" של מספר שלם חיובי היא הספרה השמאלית ביותר שלו.
לדוגמה: הספרה המובילה של 452 היא 4, הספרה המובילה של 19 היא 1, הספרה המובילה של 9 היא 9.
כתבו פונקציה המקבלת מספר שלם חיובי ומחזירה את הספרה המובילה שלו.
רצף של שלושה מספרים סמוכים ברשימה ייקרא "שלשת ראש זהה" אם בכל שלושת המספרים ברצף הספרה המובילה זהה.
ברשימה a = [58, 612, 61, 6929, 13, 12, 21, 22, 239]
יש שתי "שלשות ראש זהה".
כתבו פונקציה המקבלת רשימה של מספרים שלמים חיוביים ומחזירה את כמות "שלשות ראש זהה".
◂ פתרון מלא לשאלה 2
סעיף א
כל עוד המספר גדול או שווה ל-10 מחלקים אותו ב-10 בחלוקת שלמים (`//`); מה שנשאר הוא הספרה המובילה.
הרעיון: חלוקת שלמים ב-10 (`num // 10`) מוחקת את ספרת האחדות, כלומר את הספרה הימנית. אם נמחק ספרות מימין עד שנשארת ספרה אחת, היא הספרה השמאלית ביותר.
1. כל עוד (יש יותר מספרה אחת) – מבצעים `num = num // 10`.
2. כשהלולאה נעצרת, , כלומר נשארה ספרה אחת – מחזירים אותה.
3. אם המספר חד-ספרתי מלכתחילה, הלולאה לא מתבצעת והוא מוחזר כמו שהוא (הספרה המובילה של 9 היא 9).
def leading_digit(num):
while num >= 10:
num = num // 10
return numמעקב עבור 452: , ו- ולכן מוחזר 4.
תשובה: הפונקציה `leading_digit` שלמעלה.
סעיף ב
עוברים על כל מקום התחלה i מ-0 עד `len(lst) - 3`, ומונים את המקומות שבהם `leading_digit` של `lst[i]`, `lst[i+1]`, `lst[i+2]` שווה.
הרעיון: כל שלשה של מספרים סמוכים נקבעת לפי המקום של האיבר הראשון שלה, i. האיבר האחרון בשלשה הוא `lst[i + 2]`, ולכן i רץ מ-0 עד `len(lst) - 3`, כלומר `range(len(lst) - 2)`. (אם ברשימה פחות משלושה איברים, הטווח ריק והתשובה 0.)
1. לכל i מחשבים את הספרה המובילה d של `lst[i]` בעזרת הפונקציה מסעיף א.
2. אם גם ל-`lst[i + 1]` וגם ל-`lst[i + 2]` הספרה המובילה היא d – מצאנו שלשה, ומגדילים את המונה.
3. שלשות יכולות לחפוף (למשל ארבעה מספרים רצופים עם אותה ספרה מובילה נותנים שתי שלשות), ולכן מתקדמים תמיד במקום אחד.
def count_same_head_triples(lst):
count = 0
for i in range(len(lst) - 2):
d = leading_digit(lst[i])
if leading_digit(lst[i + 1]) == d and leading_digit(lst[i + 2]) == d:
count += 1
return countבדיקה על הדוגמה: הספרות המובילות של a הן 5, 6, 6, 6, 1, 1, 2, 2, 2. השלשות הזהות מתחילות במקום 1 (612, 61, 6929) ובמקום 6 (21, 22, 239); בשאר המקומות יש לפחות ספרה אחת שונה. הפונקציה מחזירה 2, כמו בשאלה.
תשובה: הפונקציה `count_same_head_triples` שלמעלה.
שאלה 3 · מעקב: סימנים מתחלפים באיברים סמוכים
נתונה פונקציה הבאה:
def secret(arr):
right = len(arr) - 1
left = right - 1
count = 0
while left >= 0:
if arr[left] * arr[right] < 0:
count += 1
right -= 1
left -= 1
if count == len(arr) - 1:
return True
return Falseנתונה הרשימה `arr=[1, -5, 2, -8, 4, 10, -3]`
עקבו בעזרת טבלת מעקב אחר הזימון `secret(arr)`, ורשמו מה תחזיר הפונקציה.
האם אפשר לשנות את סדר האיברים ברשימה arr כך שזימון `secret(arr)` יחזיר תוצאה שונה מהתוצאה שהתקבלה בסעיף א1? הסבירו את תשובתכם.
מה מבצעת הפונקציה secret באופן כללי?
נתונה טענה הבאה: אם הפונקציה secret החזירה True עבור רשימה מסוימת, הרי שבהכרח אין ברשימה זו את המספר 0.
קבעו אם הטענה הבאה נכונה או לא נכונה, ונמקו את קביעתכם.
◂ פתרון מלא לשאלה 3
סעיף א
count = 5, ו-`len(arr) - 1 = 6`, ולכן הפונקציה מחזירה False.
אורך הרשימה 7, ולכן בהתחלה `right = 6`, `left = 5`, `count = 0`. בכל סיבוב בודקים את המכפלה של שני איברים סמוכים; מכפלה שלילית פירושה שלשני האיברים סימנים מנוגדים, ואז count גדל ב-1. אחר כך שני האינדקסים זזים מקום אחד שמאלה.
אחרי הסיבוב האחרון `left = -1`, והלולאה נעצרת.
בדיקת הסיום: `count == len(arr) - 1`, כלומר ? לא. לכן מוחזר False (הזוג 4, 10 הוא זוג סמוך עם אותו סימן).
תשובה: הפונקציה מחזירה False.
כן. למשל `[1, -5, 2, -8, 4, -3, 10]` – הסימנים מתחלפים בכל זוג סמוך, ו-secret מחזירה True.
הפונקציה מחזירה True רק אם כל שישת הזוגות הסמוכים הם בעלי סימנים מנוגדים, כלומר הסימנים ברשימה מתחלפים: חיובי, שלילי, חיובי, ...
ברשימה יש 4 מספרים חיוביים (1, 2, 4, 10) ו-3 שליליים (-5, -8, -3), ואין 0. ברשימה באורך 7 עם סימנים מתחלפים שמתחילה בחיובי יש בדיוק 4 מקומות חיוביים (0, 2, 4, 6) ו-3 שליליים (1, 3, 5) – בדיוק מה שיש לנו. לכן אפשר לסדר מחדש, למשל:
`arr = [1, -5, 2, -8, 4, -3, 10]`
(החלפנו בין 10 ל-3-). עכשיו כל ששת הזוגות הסמוכים נותנים מכפלה שלילית, , ומוחזר True.
תשובה: כן – למשל `[1, -5, 2, -8, 4, -3, 10]`, שעבורה מוחזר True.
סעיף ב
מחזירה True אם הסימנים ברשימה מתחלפים – לכל שני איברים סמוכים סימנים מנוגדים (בלי אפסים); אחרת False.
הלולאה עוברת על כל הזוגות הסמוכים `(arr[left], arr[left + 1])`, מהסוף להתחלה, וסופרת ב-count כמה מהם בעלי מכפלה שלילית, כלומר אחד חיובי ואחד שלילי (מכפלה עם 0 שווה 0, ואינה נספרת).
ברשימה באורך n יש זוגות סמוכים. התנאי `count == len(arr) - 1` מתקיים רק אם כל הזוגות נספרו.
תשובה: הפונקציה בודקת אם הסימנים ברשימה מתחלפים (חיובי-שלילי לסירוגין): מחזירה True אם לכל שני איברים סמוכים יש סימנים מנוגדים, ו-False אחרת. (מקרי קצה: רשימה עם איבר אחד מחזירה True, כי אין זוגות ו-; רשימה ריקה מחזירה False, כי .)
סעיף ג
ברשימה עם 2 איברים לפחות הטענה נכונה (כל זוג שמכיל 0 נותן מכפלה 0, שאינה נספרת). אבל באופן כללי היא אינה נכונה: עבור `[0]` מוחזר True.
1. רשימה עם 2 איברים לפחות: נניח שבמקום k יש 0. למקום k יש לפחות שכן אחד, ולכן הוא שייך לפחות לזוג סמוך אחד. המכפלה בזוג הזה היא 0, והתנאי `0 < 0` אינו מתקיים – הזוג לא נספר. לכן , והפונקציה מחזירה False. כלומר, אם הוחזר True – אין 0 ברשימה.
2. רשימה עם איבר אחד: עבור `arr = [0]` מתקבל `right = 0`, `left = -1`, הלולאה לא מתבצעת כלל, ו-. הפונקציה מחזירה True, ובכל זאת ברשימה יש 0.
לכן הטענה, כפי שנוסחה ("עבור רשימה מסוימת"), אינה נכונה – `[0]` היא דוגמה נגדית. היא נכונה רק לרשימות שבהן לפחות שני איברים.
תשובה: הטענה אינה נכונה באופן כללי: `secret([0])` מחזירה True. עבור רשימה עם 2 איברים לפחות הטענה נכונה, כי 0 נותן מכפלה 0 עם שכנו, והזוג לא נספר.
שאלה 4 · מחלקת טיסה: סכום נוסעים וטיסות מתאימות
נתונה המחלקה Flight המייצגת טיסה. למחלקה כמה תכונות:
•מספר הטיסה – flight_Num – מספר שלם (int)
•יעד הטיסה – destination - מחרוזת (str)
•מספר הנוסעים הרשומים לטיסה – passengers – מספר שלם (int)
•קיבולת המטוס (מספר המקומות הכולל במטוס) – capacity – מספר שלם (int)
כתבו פונקציה חיצונית המקבלת רשימה של טיסות flights (רשימה של עצמים מסוג Flight) ושם של יעד dest. הפונקציה תחזיר את מספר הנוסעים הכולל הרשומים לכל הטיסות ש-dest הוא היעד שלהן.
קבוצת תיירים המונה num אנשים מעוניינת לטוס ליעד dest. טיסה נחשבת "מתאימה" לקבוצה אם היעד שלה הוא היעד המבוקש, ויש בה מספיק מקומות פנויים לכל חברי הקבוצה.
כתבו פונקציה חיצונית המקבלת רשימה של טיסות, שם יעד ומספר תיירים. הפונקציה תדפיס את מספרי הטיסות המתאימות לקבוצה.
◂ פתרון מלא לשאלה 4
סעיף א
צובר: עוברים על הטיסות, ולכל טיסה עם `f.destination == dest` מוסיפים את `f.passengers`; מחזירים את הצובר.
הרעיון: זה צובר עם תנאי. לשם הבהירות נכתוב גם את המחלקה Flight עם פעולה בונה (התכונות נגישות ישירות, כמו בשאלה).
1. מאפסים צובר `total = 0`.
2. עוברים על כל טיסה f ברשימה. אם היעד שלה הוא dest (`f.destination == dest`), מוסיפים לצובר את מספר הנוסעים הרשומים אליה, `f.passengers`.
3. בסוף הלולאה מחזירים את הצובר. אם אין אף טיסה ליעד – מוחזר 0.
class Flight:
def __init__(self, flight_Num, destination, passengers, capacity):
self.flight_Num = flight_Num
self.destination = destination
self.passengers = passengers
self.capacity = capacity
def total_passengers(flights, dest):
total = 0
for f in flights:
if f.destination == dest:
total += f.passengers
return totalדוגמה: עבור הטיסות 101 (Rome, 150 נוסעים, 180 מקומות), 102 (Paris, 100, 120), 103 (Rome, 175, 180), 104 (Rome, 90, 200), הזימון `total_passengers(flights, "Rome")` מחזיר .
תשובה: הפונקציה `total_passengers` שלמעלה.
סעיף ב
לכל טיסה מחשבים מקומות פנויים `capacity - passengers`; אם היעד הוא dest והמקומות הפנויים – מדפיסים את `flight_Num`.
הרעיון: מספר המקומות הפנויים בטיסה הוא הקיבולת פחות מספר הנוסעים הרשומים: `free_seats = f.capacity - f.passengers`. טיסה מתאימה אם מתקיימים שני התנאים יחד (`and`):
1. `f.destination == dest` – היעד הוא היעד המבוקש;
2. `free_seats >= num` – יש מקום לכל num חברי הקבוצה ("מספיק" כולל מצב שבו נשארים בדיוק num מקומות).
לכל טיסה מתאימה מדפיסים את מספר הטיסה `f.flight_Num`.
def print_suitable_flights(flights, dest, num):
for f in flights:
free_seats = f.capacity - f.passengers
if f.destination == dest and free_seats >= num:
print(f.flight_Num)דוגמה: עם הטיסות מהדוגמה של סעיף א, הזימון `print_suitable_flights(flights, "Rome", 30)` בודק: בטיסה 101 יש מקומות פנויים (מתאימה), בטיסה 103 יש (לא), בטיסה 104 יש (מתאימה); טיסה 102 היא לפריז. יודפסו 101 ו-104.
תשובה: הפונקציה `print_suitable_flights` שלמעלה.
שאלה 5 · איברים פורצים ברשימה
נגדיר מספר ברשימה כ"איבר פורץ" אם הוא גדול ממש מכל האיברים המופיעים לפניו (משמאלו) ברשימה.
הערה: האיבר הראשון ברשימה (באינדקס 0) נחשב תמיד ל"איבר פורץ".
לדוגמה: עבור הרשימה `arr = [7, 2, 9, 9, 15, 3]` האיברים הפורצים הם 7, 9, 15
כי 7 הוא הראשון, 9 גדול מ-7 ומ-2, 15 גדול מכל קודמיו.
כתבו פונקציה בשם is_breakthrough המקבלת רשימה של מספרים שלמים arr ואינדקס k. הפונקציה תחזיר True אם האיבר במיקום k הוא "איבר פורץ", ואם לא – הפונקציה תחזיר False.
כתבו פונקציה בשם all_breakthroughs המקבלת רשימה של מספרים שלמים ומחזירה רשימה חדשה המכילה את כל האיברים הפורצים מתוך הרשימה המקורית, לפי סדר הופעתם.
נתונה רשימה arr בגודל n.
מהו האורך המינימלי האפשרי של הרשימה המוחזרת מסעיף ב'? תנו דוגמה לרשימת קלט בגודל n=4 שתקיים זאת.
מהו האורך המקסימלי האפשרי של הרשימה המוחזרת מסעיף ב'? תנו דוגמה לרשימת קלט בגודל n=4 שתקיים זאת.
◂ פתרון מלא לשאלה 5
סעיף א
עוברים על המקומות ; אם `arr[j] >= arr[k]` מחזירים False; אם הלולאה הסתיימה – True.
הרעיון: `arr[k]` פורץ אם הוא גדול ממש מכל האיברים שלפניו. מספיק למצוא איבר אחד לפניו שגדול ממנו או שווה לו כדי לקבוע שהוא לא פורץ.
1. עוברים על המקומות j מ-0 עד `k - 1` (`range(k)`).
2. אם `arr[j] >= arr[k]` – מחזירים False מיד. (השוויון חשוב: ב-[7, 2, 9, 9, ...] ה-9 השני אינו פורץ, כי אינו גדול ממש מה-9 שלפניו.)
3. אם הלולאה הסתיימה – כל האיברים שלפניו קטנים ממנו, ומחזירים True.
עבור הטווח `range(0)` ריק, ולכן מוחזר True – בהתאם להערה שהאיבר הראשון תמיד פורץ.
def is_breakthrough(arr, k):
for j in range(k):
if arr[j] >= arr[k]:
return False
return Trueתשובה: הפונקציה `is_breakthrough` שלמעלה.
סעיף ב
יוצרים רשימה ריקה; לכל k מ-0 עד הסוף, אם `is_breakthrough(arr, k)` – מוסיפים את `arr[k]` לסוף; מחזירים את הרשימה.
הרעיון: עוברים על כל המקומות k ברשימה לפי הסדר, ולכל אחד שואלים את הפונקציה מסעיף א אם הוא פורץ. איבר פורץ מוסיפים לסוף רשימה חדשה `result` בעזרת `append`, וכך נשמר סדר ההופעה. הרשימה המקורית לא משתנה.
def all_breakthroughs(arr):
result = []
for k in range(len(arr)):
if is_breakthrough(arr, k):
result.append(arr[k])
return resultבדיקה על הדוגמה `[7, 2, 9, 9, 15, 3]`:
מוחזר `[7, 9, 15]`, כמו בשאלה.
סיבוכיות: לכל k נבדקים k איברים, סך הכול , כלומר .
תשובה: הפונקציה `all_breakthroughs` שלמעלה.
סעיף ג
1 (עבור ). דוגמה: `[9, 3, 5, 1]` → `[9]`.
האיבר הראשון תמיד פורץ, ולכן ברשימה לא ריקה יוחזר לפחות איבר אחד. אורך 1 מתקבל כאשר האיבר הראשון הוא הגדול ביותר (או שווה למקסימום), כי אז אף איבר אחריו אינו גדול ממנו ממש.
דוגמה עם : `arr = [9, 3, 5, 1]` – כל האיברים אחרי 9 קטנים ממנו, ומוחזר `[9]`. (גם `[4, 4, 4, 4]` מתאימה.)
(עבור רשימה ריקה, , מוחזרת רשימה ריקה.)
תשובה: האורך המינימלי הוא 1; למשל `[9, 3, 5, 1]`.
n. דוגמה: `[1, 2, 3, 4]` → `[1, 2, 3, 4]`.
הרשימה המוחזרת מכילה רק איברים מהרשימה המקורית, ולכן אורכה לכל היותר n. אורך n מתקבל כאשר כל איבר פורץ, כלומר כל איבר גדול ממש מכל קודמיו – רשימה עולה ממש.
דוגמה עם : `arr = [1, 2, 3, 4]` – מוחזר `[1, 2, 3, 4]`, באורך 4.
תשובה: האורך המקסימלי הוא n; למשל `[1, 2, 3, 4]`.
שאלה 6 · תרומות ופרויקטי צדקה: בנאי, סכום ומקסימום
לפניכם הגדרות של שתי מחלקות המייצגות מערכת לניהול פרויקטים של תרומות:
המחלקה Donation מייצגת תרומה בודדת ולה התכונות האלה:
•שם התורם – donor_name - מחרוזת (str)
•סכום התרומה – amount – מספר עשרוני (float)
•סוג התרומה – donation_type - תו/מחרוזת ('F' עבור מזון, 'C' עבור ביגוד, 'M' עבור כסף).
המחלקה CharityProject מייצגת פרויקט צדקה. למחלקה התכונות האלה:
•מספר זיהוי של הפרויקט – project_id - מספר שלם (int)
•שם היישוב שבו נערך הפרויקט – location - מחרוזת (str)
•רשימת תרומות donations. הרשימה מלאה באובייקטים מסוג Donation.
כתבו בנאי (`__init__`) למחלקה Donation המקבל ערכים עבור כל תכונותיה. הבנאי יבדוק את תקינות הפרמטרים:
•סכום התרומה (amount) חייב להיות חיובי ממש. אם לא, ייקבע ערך ברירת מחדל של 10.
•סוג התרומה (donation_type) חייב להיות אחד מהתווים 'F', 'C' או 'M'. אם לא, ייקבע ערך ברירת מחדל של 'M'.
כתבו במחלקה CharityProject פונקציה בשם get_type_total המקבלת תו המייצג סוג תרומה. הפונקציה תחזיר את הסכום הכולל של כל התרומות מסוג זה הקיימות ברשימה התרומות של הפרויקט.
כתבו פונקציה חיצונית המקבלת רשימה של פרויקטים (אובייקטים מסוג CharityProject) ותו המייצג סוג תרומה. הפונקציה תדפיס את שם היישוב (location) של הפרויקט שבו נאסף סכום הכסף הגבוה ביותר עבור סוג התרומה שהתקבל.
הנחה: כל יישוב מופיע ברשימת הפרויקטים פעם אחת לכל היותר.
◂ פתרון מלא לשאלה 6
סעיף א
`__init__(self, donor_name, amount, donation_type)`: amount נשמר אם , אחרת 10; donation_type נשמר אם הוא אחד מ-'F', 'C', 'M', אחרת 'M'.
הרעיון: הבנאי מקבל, מלבד self, שלושה פרמטרים – אחד לכל תכונה – ושומר אותם בתכונות העצם:
1. שם התורם נשמר כמו שהוא (אין עליו דרישת תקינות).
2. סכום: אם (חיובי ממש, כלומר 0 אינו תקין) שומרים אותו; אחרת שומרים את ערך ברירת המחדל 10.
3. סוג: בודקים אם הוא אחד משלושת התווים המותרים בעזרת `in` על אוסף של שלושתם (שקול ל-`t == 'F' or t == 'C' or t == 'M'`). אם כן – שומרים אותו; אחרת – 'M'.
class Donation:
def __init__(self, donor_name, amount, donation_type):
self.donor_name = donor_name
if amount > 0:
self.amount = amount
else:
self.amount = 10
if donation_type in ('F', 'C', 'M'):
self.donation_type = donation_type
else:
self.donation_type = 'M'דוגמה: `Donation("Dana", -5, 'X')` יוצר תרומה עם `amount = 10` ו-`donation_type = 'M'`.
תשובה: הבנאי שלמעלה.
סעיף ב
צובר על `self.donations`: לכל תרומה d עם `d.donation_type == d_type` מוסיפים את `d.amount`; מחזירים את הצובר (0 אם אין תרומות מהסוג).
הרעיון: זו פעולה פנימית של CharityProject, ולכן היא ניגשת לרשימת התרומות של הפרויקט דרך `self.donations`. מאפסים צובר, עוברים על כל התרומות, ולכל תרומה מהסוג המבוקש מוסיפים את הסכום שלה. בסוף מחזירים את הצובר. נכתוב את המחלקה עם בנאי פשוט (רשימת תרומות ריקה בהתחלה) ואת הפעולה:
class CharityProject:
def __init__(self, project_id, location):
self.project_id = project_id
self.location = location
self.donations = []
def get_type_total(self, d_type):
total = 0
for d in self.donations:
if d.donation_type == d_type:
total += d.amount
return totalדוגמה: אם בפרויקט תרומות של 100 מסוג 'M', של 10 מסוג 'M' ושל 50.5 מסוג 'F', אז `get_type_total('M')` מחזירה ו-`get_type_total('F')` מחזירה 50.5.
תשובה: הפעולה `get_type_total` שלמעלה.
סעיף ג
חיפוש מקסימום: לכל פרויקט מחשבים `p.get_type_total(d_type)`, שומרים את הפרויקט עם הסכום הגדול ביותר, ומדפיסים את ה-location שלו.
הרעיון: חיפוש מקסימום רגיל, כשהערך שמשווים הוא הסכום שמחזירה הפעולה מסעיף ב.
1. אם הרשימה ריקה – אין מה להדפיס, ויוצאים.
2. מניחים שהפרויקט הראשון הוא הטוב ביותר: `best = projects[0]`, ושומרים את הסכום שלו ב-`best_total` (כך מחשבים את הסכום של כל פרויקט פעם אחת בלבד).
3. עוברים על כל הפרויקטים; לכל פרויקט p מחשבים `total = p.get_type_total(d_type)`. אם הוא גדול מ-`best_total` – מעדכנים את best ואת `best_total`.
4. בסוף מדפיסים `best.location`.
בזכות ההנחה שכל יישוב מופיע פעם אחת, אין צורך לצבור סכומים של כמה פרויקטים באותו יישוב – כל פרויקט הוא יישוב אחר. אם לכמה פרויקטים אותו סכום מקסימלי, מודפס הראשון שבהם.
def print_best_location(projects, d_type):
if len(projects) == 0:
return
best = projects[0]
best_total = best.get_type_total(d_type)
for p in projects:
total = p.get_type_total(d_type)
if total > best_total:
best_total = total
best = p
print(best.location)דוגמה: לפרויקט בחיפה (Haifa) תרומות כסף של 110 ותרומות מזון של 50.5, ולפרויקט באילת (Eilat) תרומת כסף של 200. עבור 'M' יודפס Eilat, ועבור 'F' יודפס Haifa.
תשובה: הפונקציה `print_best_location` שלמעלה.
שאלה 7 · חפיפה בין סוף מחרוזת לתחילת אחרת
לפניכם שתי פונקציות secret ו-sod:
def secret(s, t):
v = 0
n = len(s)
m = len(t)
length = n if n < m else m
for i in range(1, length + 1):
p1 = s[n - i:]
p2 = t[0:i]
if p1 == p2:
v = i
return v
def sod(arr):
for j in range(len(arr) - 1):
# (*) פקודת התנאי
if secret(arr[j], arr[j + 1]) == 0:
return False
return Trueעקבו בעזרת טבלת המעקב אחרי זימון הפונקציה `secret("Windstorm", "stormy")`.
בטבלת המעקב יש להציג את ערכי המשתנים p1,p2,i,v בכל סיבוב (איטרציה) של הלולאה.
תנו דוגמה לזוג מחרוזות שונות שעבורן הפונקציה תחזיר ערך 3.
מה מבצעת הפונקציה secret באופן כללי עבור שתי מחרוזות s1, s2?
נתונה רשימה:
`arr = ["Basketball", "ballroom", "Roommate", "material"]`
עקבו אחרי זימון הפונקציה `sod(arr)` ורשמו מה תהיה תוצאת הזימון.
פקודת התנאי (*) השתנה לפקודה הבאה:
if secret(arr[j], arr[j + 1]) !=3:תנו דוגמה לרשימה arr בגודל שישה תאים שעבורו זימון הפונקציה `sod(arr)` יחזיר ערך True.
◂ פתרון מלא לשאלה 7
סעיף א
הפונקציה מחזירה 5 (החפיפה "storm").
בהתחלה `v = 0`, `n = len("Windstorm") = 9`, `m = len("stormy") = 6`, ולכן `length = 6` (הקטן מבין השניים). הלולאה רצה על . בכל סיבוב p1 הוא i התווים האחרונים של s (`s[n - i:]`), ו-p2 הוא i התווים הראשונים של t (`t[0:i]`). אם הם שווים – `v = i`.
תשובה: הפונקציה מחזירה 5.
למשל `secret("sunset", "settle")` מחזירה 3.
צריך שסוף s ותחילת t יחפפו ב-3 תווים בדיוק, וגם שלא תהיה חפיפה ארוכה יותר (כי v מקבל את ה-i הגדול ביותר שמתאים).
ניקח `s = "sunset"`, `t = "settle"`: הסוף של s הוא "set", וגם t מתחילה ב-"set".
בדיקה: עבור : "t" מול "s"; : "et" מול "se"; : "set" מול "set" – שווה, ; : "nset" מול "sett"; : "unset" מול "settl"; : "sunset" מול "settle" – כולם שונים. מוחזר 3.
תשובה: למשל "sunset" ו-"settle".
מחזירה את האורך של הסיומת הארוכה ביותר של s1 שהיא גם רישא (התחלה) של s2 – אורך החפיפה; 0 אם אין חפיפה.
לכל אורך i, מ-1 עד אורך המחרוזת הקצרה, הפונקציה משווה את i התווים האחרונים של s1 ל-i התווים הראשונים של s2. כל פעם שיש התאמה, v מקבל את i. מאחר ש-i עולה, בסוף v הוא ה-i הגדול ביותר שבו הייתה התאמה, ואם לא הייתה אף התאמה – v נשאר 0. ההשוואה רגישה לאותיות גדולות וקטנות.
תשובה: secret מחזירה את אורך החפיפה המקסימלית בין סוף s1 לתחילת s2: האורך של הסיומת הארוכה ביותר של s1 ששווה לרישא של s2 (ו-0 אם אין כזו).
סעיף ב
False – `secret("ballroom", "Roommate")` מחזירה 0, כי "room" שונה מ-"Room" (R גדולה).
הפונקציה sod עוברת על כל זוג מחרוזות סמוכות, ומחזירה False ברגע שיש זוג שאין ביניהם חפיפה כלל (secret מחזירה 0). אם לכל הזוגות יש חפיפה – מוחזר True. ברשימה 4 מחרוזות, ולכן j רץ על 0, 1, 2.
בזוג השני: הסיומות של "ballroom" הן "m", "om", "oom", "room", ... והרישות של "Roommate" הן "R", "Ro", "Roo", "Room", ... . הסיומת "room" מתחילה ב-r קטנה, והרישא "Room" ב-R גדולה, ולכן אף אורך אינו מתאים, ו-secret מחזירה 0. הזוג השלישי ("Roommate", "material", חפיפה "mate") כבר לא נבדק.
תשובה: `sod(arr)` מחזירה False.
למשל `["catdog", "dogpig", "pigcow", "cowbee", "beeant", "antfox"]` – לכל זוג סמוך חפיפה של 3 בדיוק.
עכשיו sod מחזירה False אם יש זוג סמוך שהחפיפה שלו שונה מ-3. כדי לקבל True, לכל אחד מחמשת הזוגות הסמוכים החפיפה המקסימלית צריכה להיות בדיוק 3: שלושת התווים האחרונים של כל מחרוזת הם שלושת הראשונים של הבאה, ואין חפיפה ארוכה יותר.
נבנה שרשרת של מחרוזות בנות 6 אותיות, שכל אחת מורכבת משתי מילים בנות 3 אותיות, והמילה השנייה של כל מחרוזת היא הראשונה של הבאה:
arr = ["catdog", "dogpig", "pigcow", "cowbee", "beeant", "antfox"]בדיקה לזוג הראשון: עבור "dog" = "dog"; עבור משווים "tdog"/"dogp", "atdog"/"dogpi", "catdog"/"dogpig" – שונים; עבור ("g"/"d", "og"/"do") – שונים. החפיפה היא 3. כך גם בשאר הזוגות, ולכן התנאי `!= 3` לא מתקיים אף פעם, והפונקציה מחזירה True.
תשובה: למשל `["catdog", "dogpig", "pigcow", "cowbee", "beeant", "antfox"]`.
שאלה 8 · מטריצה מיוחדת: מסגרת קטנה מהפנים
•מסגרת רשימה הדו-ממדית (מטריצה) מורכבת מהתאים הנמצאים בשורה 0, עמודה 0, שורה אחרונה ועמודה אחרונה.
•תא פנימי במטריצה הוא איבר שאינו נמצא במסגרת.
•מטריצה נקראת "מטריצה מיוחדת" אם כל האיברים הנמצאים במסגרת קטנים ממש מכל האיברים הנמצאים בתאים פנימיים.
הנחה: גודל המטריצה הוא לפחות 3X3
לדוגמה, המטריצה הבאה היא מטריצה מיוחדת:

כתבו פונקציה בשם `is_special(arr)` המקבלת מטריצה (רשימה דו-ממדית) של מספרים שלמים. הפונקציה תבדוק אם המטריצה היא מטריצה מיוחדת. אם כן – הפונקציה תחזיר True, ואם לא – הפונקציה תחזיר False.
מהי סיבוכיות זמן הריצה של כל הפונקציה שכתבתם בסעיף א'? הסבירו את תשובתכם.
כתבו פונקציה בשם `make_special(arr, low, high)` המקבלת מטריצה (רשימה דו-ממדית) של מספרים שלמים arr ושני מספרים שלמים low ו-high. הפונקציה תמלא את המטריצה במספרים אקראיים בטווח בין low ל-high (כולל), כך שתתקבל מטריצה "מיוחדת".
הנחה: הטווח בין low ל-high גדול מספיק (לפחות 2 ערכים שונים).
הנחיה: בצעו את המילוי בדרך שאינה מסתמכת על מזל בלבד, אלא מבטיחה את התנאי מראש.
◂ פתרון מלא לשאלה 8
סעיף א
במעבר אחד מחשבים את המקסימום של תאי המסגרת ואת המינימום של התאים הפנימיים; מחזירים `max_frame < min_inner`.
הרעיון: "כל איבר במסגרת קטן ממש מכל איבר פנימי" שקול לתנאי אחד: הגדול ביותר במסגרת קטן ממש מהקטן ביותר בפנים. (אם המקסימום של המסגרת קטן מהמינימום של הפנים, אז כל איבר במסגרת, שהוא לכל היותר המקסימום, קטן מכל איבר פנימי, שהוא לפחות המינימום; ולהפך – אם התנאי נכון לכל הזוגות, הוא נכון בפרט לזוג מקסימום-מינימום.) כך אין צורך להשוות כל זוג.
1. נסמן `rows` = מספר השורות ו-`cols` = מספר העמודות.
2. תא `(i, j)` שייך למסגרת אם או או או ; אחרת הוא פנימי.
3. ערכים התחלתיים: `max_frame = arr[0][0]` (תא במסגרת), `min_inner = arr[1][1]` (תא פנימי – קיים, כי המטריצה לפחות 3X3).
4. במעבר אחד על כל התאים מעדכנים את `max_frame` עבור תאי מסגרת ואת `min_inner` עבור תאים פנימיים.
5. מחזירים את תוצאת ההשוואה `max_frame < min_inner` (קטן ממש).
def is_special(arr):
rows = len(arr)
cols = len(arr[0])
max_frame = arr[0][0]
min_inner = arr[1][1]
for i in range(rows):
for j in range(cols):
if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
if arr[i][j] > max_frame:
max_frame = arr[i][j]
else:
if arr[i][j] < min_inner:
min_inner = arr[i][j]
return max_frame < min_innerבדיקה על הדוגמה: איברי המסגרת: 1, 5, 3, 6, 4, -6, 1, 1, 3, 4, 5, 2, -7, 0 – המקסימום 6. האיברים הפנימיים: 10, 8, 9, 15, 12, 21 – המינימום 8. , ולכן מוחזר True.
תשובה: הפונקציה `is_special` שלמעלה.
סעיף ב
עבור מטריצה בגודל (עבור מטריצה ריבועית ).
נסמן ב-n את מספר השורות וב-m את מספר העמודות.
1. הלולאות המקוננות עוברות על כל תא במטריצה פעם אחת בדיוק: סיבובים.
2. בכל סיבוב מתבצעות כמה השוואות והשמה אחת לכל היותר – עבודה קבועה, .
3. הצעדים שמחוץ ללולאות (חישוב אורכים, ערכים התחלתיים, ההשוואה בסוף) הם .
סך הכול , כלומר זמן ליניארי במספר התאים. אי אפשר לעשות זאת מהר יותר באופן כללי, כי כל תא עשוי להיות זה שמפר את התנאי, ולכן צריך לבדוק את כולם.
תשובה: – כל תא נבדק פעם אחת בעבודה קבועה (למטריצה ריבועית : ).
סעיף ג
מחלקים את הטווח בנקודה `mid = (low + high) // 2`: תאי המסגרת מקבלים `random.randint(low, mid)` והתאים הפנימיים `random.randint(mid + 1, high)`.
הרעיון: מפצלים את הטווח לשני תת-טווחים שאינם חופפים: חלק "נמוך" לתאי המסגרת וחלק "גבוה" לתאים הפנימיים. כל מספר בחלק הנמוך קטן ממש מכל מספר בחלק הגבוה, ולכן המטריצה תהיה מיוחדת בוודאות, בלי קשר לתוצאות ההגרלה.
1. נקודת חלוקה: `mid = (low + high) // 2`. מאחר שבטווח לפחות 2 ערכים, , ולכן . כך שני התת-טווחים ו- אינם ריקים, וכולם בתוך .
2. עוברים על כל התאים. תא במסגרת (שורה 0 או אחרונה, עמודה 0 או אחרונה) מקבל `random.randint(low, mid)`.
3. תא פנימי מקבל `random.randint(mid + 1, high)`.
4. אז כל איבר במסגרת כל איבר פנימי – התנאי מתקיים.
המטריצה מתמלאת במקום (הפונקציה משנה את arr שהתקבלה, ולכן אין צורך להחזיר ערך). גודל המטריצה נלקח מ-arr עצמה.
import random
def make_special(arr, low, high):
mid = (low + high) // 2
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
arr[i][j] = random.randint(low, mid)
else:
arr[i][j] = random.randint(mid + 1, high)דוגמה: עבור , (הטווח הקטן ביותר המותר): , המסגרת כולה 1 והפנים כולו 2 – מטריצה מיוחדת. עבור , : , המסגרת מקבלת ערכים 0 עד 50 והפנים 51 עד 100.
תשובה: הפונקציה `make_special` שלמעלה.
שאלה 9 · מרכז למידה: רישום לקורסים וקורסי מצטיינים
מרכז למידה מעוניין לנהל את הרישום לקורסים שלו. לשם כך הוגדרו שלוש מחלקות:
המחלקה Student מייצגת תלמיד. למחלקה שתי תכונות:
•שם מלא - full_name – מחרוזת (str)
•ציון ממוצע - grade – מספר עשרוני (float)
המחלקה Course מייצגת קורס בודד. למחלקה התכונות האלה:
•שם קורס - course_name – מחרוזת (str)
•ציון סף לקבלה לקורס - min_entry_grade – מספר עשרוני (float)
•מספר מקסימלי של מקומות בקורס - max_students – מספר שלם (int)
•תלמידים שנרשמו - registered – רשימה של אובייקטים מסוג Student
המחלקה LearningCenter מייצגת את המרכז כולו. למחלקה שתי תכונות:
•שם מרכז – center_name – מחרוזת (str)
•רשימת קורסים - courses – רשימה של אובייקטים מסוג Course.
כתבו במחלקה Course פעולה בונה (`__init__`) המקבלת שם קורס, ציון סף לקבלה ומספר מקסימלי של מקומות. הפעולה מאתחלת קורס ללא רשומים.
כתבו במחלקה Course פונקציה בשם add_student. הפונקציה תוסיף את התלמיד לקורס אם יש מקום פנוי בקורס והציון הממוצע של התלמיד גדול או שווה לציון הסף של הקורס. אם ההוספה הצליחה – הפונקציה תחזיר True, ואם לא – הפונקציה תחזיר ערך False. כותרת הפונקציה:
def add_student(name, grade):קורס נקרא "קורס מצטיינים" אם לפחות חצי מהרשומים בקורס הם בעלי ציון ממוצע הגבוה מ-90.
כתבו במחלקה Course פונקציה בשם is_honors_course. אם קורס הוא "קורס מצטיינים" – הפונקציה תחזיר True, ואם לא – הפונקציה תחזיר ערך False. אם אין תלמידים רשומים כלל, הפונקציה תחזיר False.
כתבו במחלקה LearningCenter פונקציה בשם print_full_courses. הפונקציה תדפיס את שמות הקורסים שאין בהם מקומות פנויים.
כתבו עבור המחלקה LearningCenter פונקציה בשם get_excellent_courses.
הפונקציה תיצור ותחזיר רשימה חדשה המכילה את שמות הקורסים המוגדרים כ"קורסי מצטיינים". אם אין אף קורס מתאים, הפונקציה תחזיר רשימה ריקה.
◂ פתרון מלא לשאלה 9
סעיף א
`__init__(self, course_name, min_entry_grade, max_students)` שומרת את שלושת הערכים ומאתחלת `self.registered = []`.
הרעיון: הפעולה הבונה מקבלת שלושה ערכים ושומרת אותם בתכונות המתאימות. התכונה הרביעית, רשימת הרשומים, אינה מתקבלת כפרמטר: קורס חדש הוא "ללא רשומים", ולכן מאתחלים אותה לרשימה ריקה. נכתוב גם את המחלקה Student, שבה נשתמש בסעיף הבא.
class Student:
def __init__(self, full_name, grade):
self.full_name = full_name
self.grade = grade
class Course:
def __init__(self, course_name, min_entry_grade, max_students):
self.course_name = course_name
self.min_entry_grade = min_entry_grade
self.max_students = max_students
self.registered = []תשובה: הפעולה הבונה שלמעלה.
אם `len(self.registered) < self.max_students` וגם `grade >= self.min_entry_grade` – מוסיפים `Student(name, grade)` ל-registered ומחזירים True; אחרת False.
הרעיון: הפונקציה מקבלת את נתוני התלמיד (שם וציון), ולכן יוצרת ממנו עצם Student חדש לפני ההוספה. כיוון שזו פעולה של המחלקה Course, הפרמטר הראשון שלה הוא self (בכותרת שבשאלה הוא לא נכתב, ובקוד נוסיף אותו).
1. יש מקום פנוי אם מספר הרשומים קטן ממש מהמספר המקסימלי: `len(self.registered) < self.max_students`.
2. הציון מספיק אם `grade >= self.min_entry_grade` ("גדול או שווה").
3. אם שני התנאים מתקיימים (`and`) – יוצרים `Student(name, grade)`, מוסיפים לסוף `self.registered` ומחזירים True.
4. אחרת לא מוסיפים דבר ומחזירים False.
class Course:
def add_student(self, name, grade):
if len(self.registered) < self.max_students and grade >= self.min_entry_grade:
self.registered.append(Student(name, grade))
return True
return Falseדוגמה: בקורס עם ציון סף 80 ו-3 מקומות: הוספת תלמיד עם 95 – True; עם 70 – False (מתחת לסף); עם 85 – True; עם 92 – True (עכשיו 3 רשומים); עם 99 – False (אין מקום).
תשובה: הפעולה `add_student` שלמעלה.
אם אין רשומים – False; אחרת סופרים את הרשומים עם ומחזירים `count * 2 >= len(self.registered)`.
1. מקרה מיוחד: אם רשימת הרשומים ריקה – מחזירים False מיד, כנדרש.
2. סופרים במונה count את הרשומים שהציון הממוצע שלהם גבוה מ-90 (`s.grade > 90`, כלומר 90 עצמו לא נחשב).
3. "לפחות חצי" פירושו . כדי להימנע מחלוקה (ומבעיה עם מספר רשומים אי-זוגי) משווים בצורה השקולה .
class Course:
def is_honors_course(self):
if len(self.registered) == 0:
return False
count = 0
for s in self.registered:
if s.grade > 90:
count += 1
return count * 2 >= len(self.registered)דוגמה: בקורס מסעיף 2 רשומים 95, 85, 92: שניים מעל 90, ו- – קורס מצטיינים, מוחזר True.
תשובה: הפעולה `is_honors_course` שלמעלה.
סעיף ב
עוברים על `self.courses` ומדפיסים `c.course_name` לכל קורס שבו `len(c.registered) >= c.max_students`.
הרעיון: קורס מלא כאשר מספר הרשומים הגיע למספר המקומות המקסימלי. הפעולה `add_student` לא מאפשרת לעבור את המקסימום, ולכן בפועל זה שוויון; הבדיקה `>=` בטוחה גם אם הרשימה מולאה בדרך אחרת. נכתוב את המחלקה עם בנאי (רשימת קורסים ריקה בהתחלה) ואת הפעולה:
class LearningCenter:
def __init__(self, center_name):
self.center_name = center_name
self.courses = []
def print_full_courses(self):
for c in self.courses:
if len(c.registered) >= c.max_students:
print(c.course_name)תשובה: הפעולה `print_full_courses` שלמעלה.
יוצרים רשימה ריקה, ולכל קורס c שעבורו `c.is_honors_course()` מחזירה True מוסיפים את `c.course_name`; מחזירים את הרשימה.
הרעיון: משתמשים בפעולה `is_honors_course` מסעיף א3 – כל קורס "יודע" לענות אם הוא קורס מצטיינים.
1. יוצרים רשימה חדשה וריקה `result`.
2. עוברים על כל הקורסים במרכז; לכל קורס מצטיינים מוסיפים את שמו (לא את העצם עצמו) לסוף הרשימה.
3. מחזירים את הרשימה. אם לא נמצא אף קורס – היא נשארת ריקה, כנדרש.
class LearningCenter:
def get_excellent_courses(self):
result = []
for c in self.courses:
if c.is_honors_course():
result.append(c.course_name)
return resultדוגמה: אם במרכז הקורס "Algo" מסעיף א (מלא, 2 מתוך 3 מעל 90) והקורס "Data" עם תלמיד אחד בציון 61, אז `print_full_courses` מדפיסה Algo ו-`get_excellent_courses` מחזירה `['Algo']`.
תשובה: הפעולה `get_excellent_courses` שלמעלה.
שאלה 10 · רקורסיה: מספר מיוחד לפי ספרות לסירוגין
נתונות שתי פונקציות המשתפות פעולה ביניהן כדי לבדוק האם מספר שלם חיובי הוא מספר "מיוחד": הפונקציה is_special והפונקציה check_special
def check_special (num, diff):
if num == 0:
return diff == 0
last = num % 10
return check_special (num // 10, last - diff)
def is_special(num):
if num < 10:
return False
return check_special (num, 0)מה תהיה תוצאת זימון הפונקציה `is_special(12551)`? יש להראות מעקב.
מה תהיה תוצאת זימון הפונקציה `is_special(4254)`?
מה מבצעת הפונקציה `is_special(num)` באופן כללי עבור מספר שלם num?
נתונה הפונקציה רקורסיבית secret המקבלת רשימה של מספרים שלמים ואינדקס תחילת ריצה i. הפונקציה משתמשת בפונקציה is_special.
def secret(arr, i=0):
if i == len(arr):
return -1
res = secret(arr, i + 1)
if is_special(arr[i]) and arr[i] > res:
return arr[i]
return resנתונה רשימה arr:
`arr = [1234, 55, 1012, 363, 44, 827, 198]`
מה תהיה תוצאת זימון הפונקציה `secret(arr)`? יש להראות מעקב זימון הפונקציה.
אין צורך במעקב אחרי הפונקציה is_special.
מה מבצעת הפונקציה secret באופן כללי?
כתבו הפונקציה רקורסיבית המקבלת רשימה של מספרים שלמים. הפונקציה תבדוק שכל המספרים ברשימה הם "מיוחדים" (כלומר הפונקציה is_special תחזיר ערך True עבורם).
אם כן – הפונקציה תחזיר ערך True, ואם לא – הפונקציה תחזיר ערך False.
הערה: ניתן לכתוב שתי פונקציות המשתפות פעולה להשגת אותה המטרה.
◂ פתרון מלא לשאלה 10
סעיף א
True.
, ולכן is_special מזמנת `check_special(12551, 0)`. בכל זימון: `last` היא ספרת האחדות של num, והזימון הבא מקבל את num בלי ספרת האחדות ואת `last - diff`. כשמגיעים ל- מחזירים את תוצאת הבדיקה `diff == 0`.
הערך True חוזר ללא שינוי דרך כל הזימונים עד is_special.
תשובה: `is_special(12551)` מחזירה True.
False.
, ולכן מזמנים `check_special(4254, 0)`:
1. `last = 4`, הזימון הבא `check_special(425, 4 - 0 = 4)`.
2. `last = 5`, הזימון הבא `check_special(42, 5 - 4 = 1)`.
3. `last = 2`, הזימון הבא `check_special(4, 2 - 1 = 1)`.
4. `last = 4`, הזימון הבא `check_special(0, 4 - 1 = 3)`.
5. : מוחזר `3 == 0`, כלומר False.
תשובה: `is_special(4254)` מחזירה False.
עבור (חד-ספרתי, 0 או שלילי) – False. עבור – True אם הסכום לסירוגין של הספרות הוא 0, כלומר סכום הספרות במקומות האי-זוגיים (אחדות, מאות, ...) שווה לסכום הספרות במקומות הזוגיים (עשרות, אלפים, ...).
נסמן את ספרות num מימין לשמאל: (אחדות), (עשרות), , ... , .
1. מה check_special מחשבת: ה-diff מתעדכן לפי `diff = last - diff`:
, אחר כך , אחר כך , וכן הלאה. כשהספרות נגמרות () מתקבל
,
כלומר הסכום לסירוגין של הספרות (עד סימן). הפונקציה מחזירה True בדיוק כאשר הסכום הזה הוא 0, כלומר
בבדיקה בסעיף 1: – מיוחד; בסעיף 2: – לא מיוחד.
2. המקרים של num:
• – כולל מספר חד-ספרתי, 0 ומספר שלילי: is_special מחזירה False בלי לזמן את check_special.
•: מוחזר True אם ורק אם סכום הספרות במקומות האי-זוגיים (אחדות, מאות, רבבות, ...) שווה לסכום הספרות במקומות הזוגיים (עשרות, אלפים, ...).
•כל מספר מיוחד מתחלק ב-11 (ההפרש בין שני הסכומים הוא 0), אבל לא כל מספר שמתחלק ב-11 הוא מיוחד: למשל , אבל , ולכן `is_special(209)` מחזירה False.
תשובה: is_special מחזירה False לכל ; עבור היא מחזירה True אם ורק אם סכום הספרות שבמקומות האי-זוגיים (אחדות, מאות, ...) שווה לסכום הספרות שבמקומות הזוגיים (עשרות, אלפים, ...).
סעיף ב
1012.
הפונקציה קודם מזמנת את עצמה עבור `i + 1`, ורק אחרי שהזימון חוזר בודקת את `arr[i]`. לכן הזימונים יורדים מ- עד (תנאי העצירה, מוחזר -1), והבדיקות מתבצעות בדרך חזרה, מ- עד .
לפי סעיף א3, מספר מיוחד הוא מספר דו-ספרתי לפחות שהסכום לסירוגין של ספרותיו 0: 55, 1012 (), 363 (), 44, 198 () מיוחדים; 1234 () ו-827 () אינם מיוחדים.
תשובה: `secret(arr)` מחזירה 1012.
מחזירה את המספר המיוחד הגדול ביותר ברשימה (מהמקום i ועד הסוף); אם אין מספר מיוחד – מחזירה -1.
הערך res שחוזר מהזימון עם `i + 1` הוא התשובה לחלק הרשימה שמתחיל במקום `i + 1`. האיבר `arr[i]` מחליף אותו רק אם הוא מיוחד וגם גדול ממנו. זה חיפוש מקסימום רקורסיבי על המספרים המיוחדים בלבד, כשהערך -1 משמש "אין עדיין מספר מיוחד" (כל מספר מיוחד הוא לפחות 11, ולכן גדול מ-1-).
תשובה: secret מחזירה את המספר ה"מיוחד" הגדול ביותר ברשימה arr (מהאינדקס i עד הסוף; בזימון `secret(arr)` – בכל הרשימה), ואם אין ברשימה אף מספר מיוחד היא מחזירה -1.
סעיף ג
`all_special(arr, i=0)`: אם `i == len(arr)` – True; אם `arr[i]` אינו מיוחד – False; אחרת מחזירים `all_special(arr, i + 1)`.
הרעיון: כמו ב-secret, נשתמש באינדקס i עם ערך ברירת מחדל 0, שמסמן מאיפה בודקים.
1. תנאי עצירה: אם `i == len(arr)` – עברנו את כל הרשימה בלי למצוא מספר שאינו מיוחד, ומחזירים True. (גם רשימה ריקה מקיימת "כל המספרים מיוחדים".)
2. בדיקת האיבר הנוכחי: אם `is_special(arr[i])` מחזירה False – יש מספר שאינו מיוחד, ומחזירים False מיד, בלי להמשיך.
3. צעד הרקורסיה: אחרת האיבר הנוכחי תקין, והתשובה היא התשובה לשאר הרשימה: `all_special(arr, i + 1)`.
def all_special(arr, i=0):
if i == len(arr):
return True
if not is_special(arr[i]):
return False
return all_special(arr, i + 1)דוגמאות: `all_special([55, 1012, 363])` מחזירה True. עבור הרשימה מסעיף ב, `all_special(arr)` מחזירה False כבר באיבר הראשון, 1234.
תשובה: הפונקציה `all_special` שלמעלה.