מתכונת 7 במדעי המחשב - מבני נתונים ומסלול 899271
4–5 יח"ל · שאלון 899271 · 12 שאלות · 3 שעות · פתרון מלא לכל סעיף
מבחן מתכונת במדעי המחשב, מבני נתונים ומסלול, במבנה של בחינת הבגרות. כל שאלה בו בנויה כמו שאלה מבגרות אחרת. לכל סעיף יש תשובה ופתרון מלא, וכל קוד מופיע ב-Java וב-C#. פתרו בזמן של הבחינה, ורק אחר כך פתחו את הפתרונות.
הוראות הבחינה
א. משך הבחינה: שלוש שעות.
ב. מבנה השאלון ומפתח ההערכה: בשאלון זה שני פרקים.
פרק ראשון – 25×2 – 50 נקודות
פרק שני – 25×2 – 50 נקודות
סך הכול – 100 נקודות
ג. חומר עזר מותר בשימוש: כל חומר עזר, חוץ ממחשבון שיש בו אפשרות תכנות.
ד. הוראות מיוחדות:
(1) רשמו על הכריכה החיצונית של המחברת את שם המסלול שלמדתם.
המסלול הוא אחד משלושת המסלולים האלה: אלגוריתמים, מודלים חישוביים, תכנות מונחה עצמים.
(2) את כל התוכניות שיש לכתוב בשפת מחשב בפרקים הראשון והשני כתבו בשפה אחת בלבד – Java או C#.
הערה: לא יורדו נקודות אם תכתבו בתוכניות אות גדולה במקום אות קטנה או להפך.
יש לכתוב במחברת הבחינה בלבד. יש לרשום "טיוטה" בראש כל עמוד המשמש טיוטה.
כתיבת טיוטה בדפים שאינם במחברת הבחינה עלולה לגרום לפסילת הבחינה.
השאלות בשאלון זה מנוסחות בלשון רבים, אף על פי כן על כל תלמידה וכל תלמיד להשיב עליהן באופן אישי.
בהצלחה!
השאלות
בשאלון זה שני פרקים. יש לענות על שאלות משני הפרקים, לפי ההוראות בכל פרק.
הערה: בכל שאלה שנדרשת בה קליטה, אין צורך לבדוק את תקינות הקלט.
לפותרים בשפת Java: בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner input = new Scanner (System.in);
שימו לב: בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
פרק ראשון
ענו על שתיים מן השאלות 1–3 (לכל שאלה – 25 נקודות).
שאלה 1 · עדכוני מחירים בחנות – תור (25 נקודות)
נתונה המחלקה Update – עדכון מחיר של מוצר, ולה שתי תכונות:
הניחו שיש פעולות get/Get ו־ set/Set לתכונות המחלקה, ופעולה בונה המקבלת ערכים בעבור תכונות המחלקה.
במכולת השכונתית "פינת הכרם" נשמרים כל עדכוני המחירים של יום אחד בתור – qUpd מטיפוס Update, לפי סדר הזמן שבו נעשו: העדכון המוקדם ביותר נמצא בראש התור.
הערות:
למשל, אם בתור יש (משמאל – ראש התור): (215,40), (308,12), (215,36), (122,9), (215,44) – המחיר התקף של מוצר 215 בסוף היום הוא 44.
ממשו את הפעולה שלפניכם:
Java – public static Queue<Update> latestPrices (Queue<Update> qUpd)
C# – public static Queue<Update> LatestPrices (Queue<Update> qUpd)
הפעולה מקבלת תור עדכונים – qUpd, ומחזירה תור חדש של עצמים מטיפוס Update, ובו כל מוצר מופיע פעם אחת בלבד – עם המחיר התקף שלו בסוף היום.
בעבור התור שבדוגמה, הפעולה תחזיר תור ובו: (215,44), (308,12), (122,9).
הערות:
מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם.
בנוסף לתור העדכונים של היום, נתון תור yesterday מטיפוס Update – מחירון סוף היום הקודם: כל מוצר של המכולת מופיע בו פעם אחת בדיוק, עם המחיר שלו אתמול. כל מוצר שמופיע בתור העדכונים של היום מופיע גם ב־yesterday.
ממשו את הפעולה שלפניכם:
Java – public static Queue<Integer> priceRise (Queue<Update> qUpd, Queue<Update> yesterday)
C# – public static Queue<int> PriceRise (Queue<Update> qUpd, Queue<Update> yesterday)
הפעולה מחזירה תור מטיפוס שלם ובו הקודים של כל המוצרים שהמחיר התקף שלהם בסוף היום גבוה מן המחיר שלהם ב־yesterday. כל מוצר יופיע פעם אחת לכל היותר (ללא חשיבות לסדר).
דוגמה: yesterday = (101,30), (102,12), (103,45), (104,8) ו־ qUpd = (102,15), (101,28), (102,11), (103,50), (101,33). המחירים התקפים בסוף היום: 102 ← 11, 101 ← 33, 103 ← 50. הפעולה תחזיר תור ובו 101 ו־103 (מוצר 102 הוזל מ־12 ל־11, ומוצר 104 לא עודכן היום).
אפשר להשתמש בפעולה שכתבתם בסעיף א.
הערות:
מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם. סמנו ב־ n את מספר העדכונים ב־ qUpd וב־ m את מספר המוצרים ב־ yesterday.
◂ פתרון מלא לשאלה 1
סעיף א(1)
בכל סבב מוציאים את העדכון הראשון; עוברים לפי הסדר על שאר העדכונים: של אותו מוצר – last = המחיר שלו (דורס), של מוצר אחר – לתור עזר שמחליף את qUpd; מכניסים new Update(product, last).
מה נדרש: תור חדש שבו כל מוצר מופיע פעם אחת, עם המחיר מהעדכון האחרון שלו.
רעיון: כל עוד התור אינו ריק:
first – מוצר שעוד לא טופל. last = המחיר שלו.temp.q = temp (שבו נשארו רק מוצרים שלא טופלו, באותו סדר זמן).new Update(first.getProduct(), last).הסדר בתור העזר נשמר (FIFO), ולכן גם בסבבים הבאים העדכון האחרון של כל מוצר הוא האחרון שנפגוש.
פתרון:
public static Queue<Update> latestPrices(Queue<Update> q) {
Queue<Update> result = new Queue<Update>();
while (!q.isEmpty()) {
Update first = q.remove(); // עדכון של מוצר שעוד לא טופל
int last = first.getPrice();
Queue<Update> temp = new Queue<Update>();
while (!q.isEmpty()) { // מעבר על שאר העדכונים לפי הסדר
Update u = q.remove();
if (u.getProduct() == first.getProduct())
last = u.getPrice(); // עדכון מאוחר יותר – מחליף את המחיר
else
temp.insert(u); // מוצר אחר – לסבב הבא
}
q = temp;
result.insert(new Update(first.getProduct(), last));
}
return result;
}בדיקה: על התור מהדוגמה (215,40), (308,12), (215,36), (122,9), (215,44):
| סבב | first | last (לפי הסדר) | temp בסוף הסבב | נוסף לתוצאה |
|---|---|---|---|---|
| 1 | (215,40) | 40 → 36 → 44 | (308,12), (122,9) | (215,44) |
| 2 | (308,12) | 12 | (122,9) | (308,12) |
| 3 | (122,9) | 9 | ריק | (122,9) |
הפלט בפועל: [(215,44), (308,12), (122,9)]. נבדקו גם תור ריק, עדכון יחיד וכל העדכונים לאותו מוצר ((7,5), (7,9), (7,3) ← (7,3)).
טעות נפוצה: לשמור את המחיר הגבוה ביותר או את המחיר של העדכון הראשון – המחיר התקף הוא של העדכון האחרון, גם אם הוא נמוך יותר.
public static Queue<Update> latestPrices(Queue<Update> q) {
Queue<Update> result = new Queue<Update>();
while (!q.isEmpty()) {
Update first = q.remove(); // עדכון של מוצר שעוד לא טופל
int last = first.getPrice();
Queue<Update> temp = new Queue<Update>();
while (!q.isEmpty()) { // מעבר על שאר העדכונים לפי הסדר
Update u = q.remove();
if (u.getProduct() == first.getProduct())
last = u.getPrice(); // עדכון מאוחר יותר – מחליף את המחיר
else
temp.insert(u); // מוצר אחר – לסבב הבא
}
q = temp;
result.insert(new Update(first.getProduct(), last));
}
return result;
}סעיף א(2)
O(n²) – לכל מוצר עוברים על כל העדכונים שנותרו: (n−1)+(n−2)+…+1 במקרה הגרוע.
מה נדרש: סיבוכיות זמן הריצה של latestPrices כתלות ב־n – מספר העדכונים בתור.
פתרון:
(באופן כללי, עם k מוצרים שונים: k סבבים של לכל היותר n צעדים – O(k·n), ובמקרה הגרוע k = n.)
בדיקה: בדוגמה (n = 5, שלושה מוצרים) הלולאה הפנימית עברה על 4, 1 ו־0 עדכונים.
סעיף ב(1)
latest = latestPrices(qUpd); לכל עדכון ב־latest מחפשים את מחיר המוצר ב־yesterday בעזרת פעולת עזר שמעבירה את yesterday דרך תור עזר ומחזירה אותו למצבו; אם המחיר התקף גבוה יותר – מכניסים את הקוד לתוצאה.
מה נדרש: קודי המוצרים שהמחיר התקף שלהם היום גבוה מהמחיר של אתמול, בלי לשנות את yesterday.
רעיון:
findPrice עוברת על כל yesterday: מוציאה כל איבר, בודקת אותו ומכניסה לתור עזר, ובסוף מחזירה את כל האיברים מתור העזר ל־yesterday – כך התור חוזר בדיוק למצבו (באותו סדר) ואפשר לחפש בו שוב.פתרון: (משתמשים בפעולה latestPrices / LatestPrices מסעיף א)
// פעולת עזר: מחזירה את המחיר של product בתור prices; התור חוזר למצבו המקורי
public static int findPrice(Queue<Update> prices, int product) {
Queue<Update> temp = new Queue<Update>();
int price = -1;
while (!prices.isEmpty()) {
Update u = prices.remove();
if (u.getProduct() == product)
price = u.getPrice();
temp.insert(u);
}
while (!temp.isEmpty()) // החזרת התור למצבו
prices.insert(temp.remove());
return price;
}
public static Queue<Integer> priceRise(Queue<Update> today, Queue<Update> yesterday) {
Queue<Update> latest = latestPrices(today); // כל מוצר פעם אחת עם המחיר האחרון
Queue<Integer> result = new Queue<Integer>();
while (!latest.isEmpty()) {
Update u = latest.remove();
if (u.getPrice() > findPrice(yesterday, u.getProduct()))
result.insert(u.getProduct());
}
return result;
}בדיקה: בדוגמה latest = (102,11), (101,33), (103,50).
| מוצר | מחיר תקף היום | מחיר אתמול | נכנס? |
|---|---|---|---|
| 102 | 11 | 12 | לא |
| 101 | 33 | 30 | כן |
| 103 | 50 | 45 | כן |
הפלט בפועל: [101, 103], ו־yesterday אחרי הקריאה: [(101,30), (102,12), (103,45), (104,8)] – ללא שינוי. נבדקו גם: מחיר תקף שווה למחיר של אתמול (לא נכנס), תור עדכונים ריק ← תור ריק.
טעות נפוצה: לחפש ב־yesterday ב־remove בלי להחזיר את האיברים – אחרי החיפוש הראשון התור ריק (או חסר), החיפושים הבאים נכשלים, והדרישה שהתור יישאר כפי שהיה לא מתקיימת.
// פעולת עזר: מחזירה את המחיר של product בתור prices; התור חוזר למצבו המקורי
public static int findPrice(Queue<Update> prices, int product) {
Queue<Update> temp = new Queue<Update>();
int price = -1;
while (!prices.isEmpty()) {
Update u = prices.remove();
if (u.getProduct() == product)
price = u.getPrice();
temp.insert(u);
}
while (!temp.isEmpty()) // החזרת התור למצבו
prices.insert(temp.remove());
return price;
}
public static Queue<Integer> priceRise(Queue<Update> today, Queue<Update> yesterday) {
Queue<Update> latest = latestPrices(today); // כל מוצר פעם אחת עם המחיר האחרון
Queue<Integer> result = new Queue<Integer>();
while (!latest.isEmpty()) {
Update u = latest.remove();
if (u.getPrice() > findPrice(yesterday, u.getProduct()))
result.insert(u.getProduct());
}
return result;
}סעיף ב(2)
O(n² + n·m): latestPrices – O(n²); לכל אחד מ־k ≤ n המוצרים חיפוש ב־yesterday ב־O(m) ⇒ O(n·m).
מה נדרש: סיבוכיות priceRise כתלות ב־n (עדכונים היום) וב־m (מוצרים במחירון של אתמול).
פתרון:
סך הכול O(n² + n·m). (אם ידוע ש־m ≤ n, זה O(n²); אם המחירון גדול בהרבה מהעדכונים, החלק O(n·m) הוא הדומיננטי.)
בדיקה: בדוגמה n = 5, m = 4: latestPrices עברה בלולאה הפנימית על 4 + 2 + 0 = 6 עדכונים, ו־3 קריאות ל־findPrice עברו כל אחת על 4 איברים (ועוד 4 החזרות).
שאלה 2 · מחרוזת דחוסה בשתי שרשרות חוליות (25 נקודות)
כדי לחסוך בזיכרון, מחרוזת שיש בה תווים חוזרים ברצף נשמרת בשתי שרשרות של חוליות:
chars – הפניה לשרשרת חוליות מטיפוס תו (char).
counts – הפניה לשרשרת חוליות של מספרים שלמים חיוביים.
הערה: כמות החוליות בשתי השרשרות שווה.
המספר במיקום 1 בשרשרת counts מתאר כמה פעמים ברצף מופיע התו שבמיקום 1 בשרשרת chars, המספר במיקום 2 מתאר כמה פעמים ברצף מופיע התו שבמיקום 2, וכן הלאה עד סוף שתי השרשרות. המחרוזת המיוצגת מתקבלת מחיבור כל הרצפים לפי הסדר.
דוגמה: שתי השרשרות שלפניכם מייצגות את המחרוזת "kkkmkktt" (שלוש פעמים k, פעם אחת m, פעמיים k ופעמיים t). אורך המחרוזת הוא 8.
ממשו את הפעולה שלפניכם:
Java – public static char charAt (Node<Character> chars, Node<Integer> counts, int pos)
C# – public static char CharAt (Node<char> chars, Node<int> counts, int pos)
הפעולה תחזיר את התו שנמצא במקום pos במחרוזת המיוצגת על ידי שתי השרשרות. המקומות במחרוזת ממוספרים החל מ־1.
הניחו ש־ pos גדול מ־ 0 . אין לשנות את השרשרות שהתקבלו. אין לבנות את המחרוזת המיוצגת.
הערה: אם pos גדול מאורך המחרוזת המיוצגת, הפעולה תחזיר את התו '#'.
דוגמה: בעבור שתי השרשרות בדוגמה שלעיל ו־ pos = 4 , הפעולה תחזיר 'm' .
דוגמה נוספת: בעבור אותן שתי שרשרות ו־ pos = 7 , הפעולה תחזיר 't' .
דוגמה נוספת: בעבור אותן שתי שרשרות ו־ pos = 20 , הפעולה תחזיר '#' , כי אורך המחרוזת הוא 8 בלבד.
ממשו את הפעולה שלפניכם:
Java – public static boolean isPalindrome (Node<Character> chars, Node<Integer> counts)
C# – public static bool IsPalindrome (Node<char> chars, Node<int> counts)
הפעולה תחזיר true אם המחרוזת המיוצגת על ידי שתי השרשרות היא פלינדרום (נקראת באותו אופן משמאל לימין ומימין לשמאל), אחרת הפעולה תחזיר false .
אפשר להשתמש בפעולה שכתבתם בסעיף א. אין לשנות את השרשרות שהתקבלו. אין לבנות את המחרוזת המיוצגת. הניחו שהשרשרות אינן ריקות.
שימו לב: השרשרות עצמן אינן חייבות להיות סימטריות.
דוגמה: בעבור chars = s, a, s ו־ counts = 2, 1, 2 (המחרוזת "ssass") הפעולה תחזיר true .
דוגמה נוספת: בעבור chars = b, c, b, b ו־ counts = 2, 1, 1, 1 (המחרוזת "bbcbb") הפעולה תחזיר true .
דוגמה נוספת: בעבור שתי השרשרות בדוגמה שלעיל (המחרוזת "kkkmkktt") הפעולה תחזיר false .
◂ פתרון מלא לשאלה 2
סעיף א
מקדמים pc ו־pn במקביל; אם pos ≤ pn.getValue() מחזירים pc.getValue(), אחרת pos −= pn.getValue() ומתקדמים; אם השרשרת נגמרה – '#'.
מה נדרש: למצוא את התו במקום pos במחרוזת המיוצגת, בלי לבנות אותה ובלי לשנות את השרשרות.
רעיון: עוברים על שתי השרשרות במקביל – pc על התו ו־pn על מספר החזרות שלו. כל זוג מכסה קבוצה של pn.getValue() מקומות רצופים במחרוזת. אם pos ≤ גודל הקבוצה הנוכחית – התו המבוקש הוא התו של הקבוצה. אחרת, מדלגים על כל הקבוצה: מקטינים את pos בגודל שלה ועוברים לזוג הבא. אם נגמרו החוליות – pos גדול מאורך המחרוזת, ומחזירים '#'. (pos הוא פרמטר מקומי, ולכן מותר לשנות אותו; השרשרות רק נקראות.)
פתרון:
public static char charAt(Node<Character> chars, Node<Integer> counts, int pos) {
Node<Character> pc = chars;
Node<Integer> pn = counts; // הכמות באותו מיקום כמו pc
while (pc != null) {
if (pos <= pn.getValue()) // המקום המבוקש נמצא בקבוצה הזאת
return pc.getValue();
pos = pos - pn.getValue(); // מדלגים על כל הקבוצה
pc = pc.getNext();
pn = pn.getNext();
}
return '#'; // pos גדול מאורך המחרוזת
}בדיקה: על השרשרות מהדוגמה עם pos = 7:
| זוג | תו | כמות | pos לפני | pos ≤ כמות? |
|---|---|---|---|---|
| 1 | k | 3 | 7 | לא ← pos = 4 |
| 2 | m | 1 | 4 | לא ← pos = 3 |
| 3 | k | 2 | 3 | לא ← pos = 1 |
| 4 | t | 2 | 1 | כן ← מחזירים 't' |
התוצאות: pos = 1…9 ← k k k m k k t t # (כלומר "kkkmkktt" ואחריו '#'), pos = 4 ← 'm', pos = 7 ← 't', pos = 20 ← '#'. השרשרות לא השתנו.
טעות נפוצה: להשוות pos < pn.getValue() במקום <= – אז התו האחרון של כל קבוצה "מחליק" לקבוצה הבאה (למשל pos = 3 יחזיר 'm' במקום 'k').
public static char charAt(Node<Character> chars, Node<Integer> counts, int pos) {
Node<Character> pc = chars;
Node<Integer> pn = counts; // הכמות באותו מיקום כמו pc
while (pc != null) {
if (pos <= pn.getValue()) // המקום המבוקש נמצא בקבוצה הזאת
return pc.getValue();
pos = pos - pn.getValue(); // מדלגים על כל הקבוצה
pc = pc.getNext();
pn = pn.getNext();
}
return '#'; // pos גדול מאורך המחרוזת
}סעיף ב
מחשבים total = סכום counts; לכל i מ־1 עד total/2 משווים charAt(i) ל־charAt(total+1−i); אם יש אי־התאמה – false, אחרת true.
מה נדרש: לבדוק אם המחרוזת המיוצגת היא פלינדרום – בלי לבנות אותה.
רעיון: מחרוזת באורך total היא פלינדרום אם לכל i מ־1 עד total/2 התו במקום i שווה לתו במקום total + 1 − i (המקום ה־i מהסוף). את total מקבלים מסכום כל המספרים ב־counts (מעבר אחד על השרשרת), ואת התווים במקומות האלה נותנת charAt מסעיף א. אי אפשר להסתפק בבדיקה שהשרשרות סימטריות: "bbcbb" מיוצגת על ידי b, c, b, b עם 2, 1, 1, 1 – השרשרות אינן סימטריות, והמחרוזת היא פלינדרום.
פתרון: (משתמשים בפעולה charAt / CharAt מסעיף א)
public static boolean isPalindrome(Node<Character> chars, Node<Integer> counts) {
int total = 0; // אורך המחרוזת המיוצגת
Node<Integer> p = counts;
while (p != null) {
total = total + p.getValue();
p = p.getNext();
}
for (int i = 1; i <= total / 2; i++) // התו ה־i מול התו ה־i מהסוף
if (charAt(chars, counts, i) != charAt(chars, counts, total + 1 - i))
return false;
return true;
}בדיקה: בדוגמה "bbcbb": total = 5, בודקים i = 1, 2: charAt(1) = 'b' = charAt(5) = 'b', charAt(2) = 'b' = charAt(4) = 'b' ← true. ב־"kkkmkktt": total = 8, כבר ב־i = 1: charAt(1) = 'k' ≠ charAt(8) = 't' ← false.
התוצאות: "ssass" ← true, "bbcbb" ← true, "rraarr" (r, a, r עם 2, 2, 2) ← true, "kkkmkktt" ← false, "ab" ← false, "aabbba" (a, b, a עם 2, 3, 1) ← false, ותו יחיד x×5 ← true.
טעות נפוצה: להשוות את השרשרות זו מול זו (החוליה הראשונה מול האחרונה) – כפי שראינו, ייצוג לא סימטרי יכול לתאר פלינדרום. טעות נוספת: להשוות את התו במקום i לתו במקום total − i (בלי ה־1+) – זו השוואה לתו הלא נכון, ולמשל "ssass" תיחשב בטעות כלא פלינדרום.
public static boolean isPalindrome(Node<Character> chars, Node<Integer> counts) {
int total = 0; // אורך המחרוזת המיוצגת
Node<Integer> p = counts;
while (p != null) {
total = total + p.getValue();
p = p.getNext();
}
for (int i = 1; i <= total / 2; i++) // התו ה־i מול התו ה־i מהסוף
if (charAt(chars, counts, i) != charAt(chars, counts, total + 1 - i))
return false;
return true;
}שאלה 3 · מסלולים מהשורש לעלה עם סכום נתון (25 נקודות)
בשאלה זו אפשר להשתמש בפעולה החיצונית isLeaf / IsLeaf שלהלן בלי לממש אותה.
| כותרת הפעולה | תיאור הפעולה | דוגמאות |
|---|---|---|
בשפת Java:<br>public static boolean isLeaf (BinNode<Integer> node)<br>בשפת C#:<br>public static bool IsLeaf (BinNode<int> node) | הפעולה מקבלת הפניה לצומת – node שאינו null. הפעולה מחזירה true אם node הוא עלה (אין לו בן שמאלי ואין לו בן ימני), אחרת היא מחזירה false. | – בעבור צומת שאין לו בנים, הפעולה תחזיר true.<br>– בעבור צומת שיש לו בן ימני בלבד, הפעולה תחזיר false. |
ממשו את הפעולה החיצונית שלהלן:
Java – public static int countPaths (BinNode<Integer> tree, int sum)
C# – public static int CountPaths (BinNode<int> tree, int sum)
הפעולה מקבלת הפניה לעץ בינארי של מספרים שלמים – tree שאינו null, ומספר שלם – sum.
הפעולה תחזיר את מספר המסלולים בעץ שמתחילים בשורש העץ, מסתיימים בעלה, וסכום הערכים בצמתים שלהם שווה ל־ sum.
הערה: בעץ יכולים להופיע גם המספר 0 ומספרים שליליים.
דוגמה:
בעבור העץ הנתון ו־ sum = 12 הפעולה תחזיר 3.
הסבר: בעץ יש שלושה מסלולים מהשורש לעלה שסכומם 12: המסלול 5, 3, 4; המסלול 5, 3, -1, 5; והמסלול 5, 4, 3, 0.
דוגמה:
בעבור אותו העץ ו־ sum = 9 הפעולה תחזיר 0.
הסבר: סכום הערכים במסלול 5, 4 הוא 9, אבל המסלול אינו מסתיים בעלה (לצומת 4 יש בן). סכומי המסלולים מהשורש לעלים הם 12, 12, 12 ו־ 18.
דוגמה:
בעבור העץ הנתון ו־ sum = 1 הפעולה תחזיר 1.
הסבר: המסלול היחיד מהשורש לעלה שסכומו 1 הוא 2, -2, 1.
ממשו את הפעולה countPaths / CountPaths המתוארת לעיל.
◂ פתרון מלא לשאלה 3
פתרון
רקורסיה שמורידה מ־ sum את ערך הצומת: בעלה מחזירים 1 אם נשאר 0 (אחרת 0); בצומת אחר מחזירים את סכום הקריאות לבנים הקיימים עם rest = sum − ערך הצומת. בדוגמה (sum = 12) מתקבל 3, ובעבור sum = 9 מתקבל 0.
מה נדרש: לספור את המסלולים שמתחילים בשורש העץ ומסתיימים בעלה, שסכום הערכים בהם שווה ל־ sum.
רעיון (רקורסיה): כשיורדים מצומת לבנו, "מורידים" מהסכום המבוקש את ערך הצומת. כלומר, אם בצומת tree נשאר להשלים את הסכום sum, אז מתחת לצומת נשאר להשלים rest = sum − ערך הצומת.
שימו לב: אסור לעצור כשהסכום מתאפס באמצע המסלול, וגם אסור "לגזום" כשהסכום החלקי גדול מ־ sum – יש בעץ גם אפסים ומספרים שליליים, והמסלול נספר רק כשהוא מגיע לעלה.
פתרון:
public static int countPaths(BinNode<Integer> tree, int sum) {
int rest = sum - tree.getValue(); // הסכום שנותר להשלים מתחת לצומת זה
if (isLeaf(tree)) { // המסלול הסתיים בעלה
if (rest == 0)
return 1;
return 0;
}
int count = 0;
if (tree.hasLeft())
count += countPaths(tree.getLeft(), rest);
if (tree.hasRight())
count += countPaths(tree.getRight(), rest);
return count;
}יעילות: כל צומת מבוקר פעם אחת, ובכל ביקור מתבצעות פעולות בזמן קבוע ⇒ O(n), כאשר n הוא מספר הצמתים בעץ.
בדיקה (העץ בדוגמה הראשונה, sum = 12):
| צומת | הסכום שהתקבל (sum) | rest | עלה? | מוחזר |
|---|---|---|---|---|
| 5 (שורש) | 12 | 7 | לא | 2 + 1 = 3 |
| 3 | 7 | 4 | לא | 1 + 1 = 2 |
| 4 | 4 | 0 | כן | 1 |
| -1 | 4 | 5 | לא | 1 |
| 5 (בן של -1) | 5 | 0 | כן | 1 |
| 4 (בן של השורש) | 7 | 3 | לא | 1 |
| 3 | 3 | 0 | לא – ממשיכים | 1 + 0 = 1 |
| 0 | 0 | 0 | כן | 1 |
| 6 | 0 | -6 | כן | 0 |
הפעולה מחזירה 3. מקרים נוספים: אותו העץ עם sum = 9 ← 0 (המסלול 5, 4 אינו מסתיים בעלה), עם sum = 18 ← 1; העץ השני עם sum = 1 ← 1 ועם sum = 5 ← 1; עץ של צומת יחיד 7 עם sum = 7 ← 1.
טעות נפוצה: לבדוק "rest == 0" בכל צומת ולא רק בעלה. אז בעבור sum = 9 נספר בטעות המסלול 5, 4, שאינו מסתיים בעלה.
public static int countPaths(BinNode<Integer> tree, int sum) {
int rest = sum - tree.getValue(); // הסכום שנותר להשלים מתחת לצומת זה
if (isLeaf(tree)) { // המסלול הסתיים בעלה
if (rest == 0)
return 1;
return 0;
}
int count = 0;
if (tree.hasLeft())
count += countPaths(tree.getLeft(), rest);
if (tree.hasRight())
count += countPaths(tree.getRight(), rest);
return count;
}פרק שני (50 נקודות) – אלגוריתמים
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 4 · טענות על אלגוריתמי גרפים וגרף "קרוב" (25 נקודות)
לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם שבע טענות (1)–(7). בחרו בחמש מהן, וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא לא נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) נתון גרף G קשיר שאינו מכוון, ומריצים עליו BFS מקודקוד s . אם d(v) הוא המרחק של הקודקוד v מ־ s שמחשב האלגוריתם, אז לכל קשת (u , v) בגרף מתקיים: |d(u) − d(v)| ≤ 1 .
(2) בגרף מכוון ממושקל שיש בו קשתות במשקל שלילי, אבל אין בו מעגל שלילי, האלגוריתם של דייקסטרה מחשב תמיד נכון את המרחקים הקצרים (הקלים) מקודקוד המקור לכל הקודקודים.
(3) נתון גרף ממושקל קשיר לא מכוון. אם מוסיפים מספר קבוע c > 0 למשקל של כל קשת בגרף, כל עץ פורש מינימלי של הגרף המקורי הוא גם עץ פורש מינימלי של הגרף החדש.
(4) נתון גרף ממושקל שבו המשקל של כל קשת חיובי. אם מוסיפים מספר קבוע c > 0 למשקל של כל קשת בגרף, כל מסלול קצר (קל) מקודקוד s לקודקוד t בגרף המקורי הוא גם מסלול קצר (קל) מ־ s ל־ t בגרף החדש.
(5) בכל גרף מכוון חסר מעגלים יש לפחות קודקוד אחד שדרגת הכניסה שלו היא 0 .
(6) נתון גרף קשיר לא מכוון. הגובה של כל עץ DFS שמתקבל מסריקה מקודקוד s גדול מן הגובה של עץ ה־ BFS מ־ s או שווה לו. (גובה של עץ הוא מספר הקשתות במסלול הארוך ביותר מן השורש לעלה.)
(7) אם בגרף מכוון ממושקל יש קשת שמשקלה שלילי, האלגוריתם של בלמן־פורד יודיע שיש בגרף מעגל שלילי.
עץ BFS מקודקוד s הוא העץ שמתקבל מן הקשתות שדרכן התגלה כל קודקוד בסריקת BFS מ־ s . הרמה של קודקוד בעץ היא מספר הקשתות בעץ מן השורש s עד הקודקוד (השורש נמצא ברמה 0).
דוגמה לעץ BFS שבו כל הקודקודים נמצאים ברמה 2 לכל היותר:
גרף קשיר לא מכוון מכונה "קרוב" אם בכל סריקת BFS מכל קודקוד בגרף מתקבל עץ BFS שבו כל הקודקודים נמצאים ברמה 2 לכל היותר.
לפניכם שבעה גרפים H₁–H₇ . בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף "קרוב" או לא. אם כתבתם שלא – הציגו סריקת BFS (קודקוד התחלה והרמה של כל קודקוד) שבעבורה מתקבל עץ שיש בו קודקוד ברמה 3 או יותר.
◂ פתרון מלא לשאלה 4
סעיף א
(1) נכונה; (2) לא נכונה; (3) נכונה; (4) לא נכונה; (5) נכונה; (6) נכונה; (7) לא נכונה. (מספיק לענות על חמש מהן.)
מה נדרש: לבחור 5 מתוך 7 טענות, לקבוע אם כל אחת נכונה, ולנמק (טענה נכונה) או להביא דוגמה נגדית עם 4 קודקודים לפחות (טענה לא נכונה).
רעיון: כאן מוצגות כל שבע הטענות. כדי להפריך טענה מספיקה דוגמה אחת; כדי להוכיח טענה צריך נימוק כללי (לא דוגמה).
פתרון:
(1) נכונה. BFS מחשב את המרחק הקצר ביותר (במספר קשתות) מ־ s לכל קודקוד. אם יש קשת (u , v), אז המסלול הקצר מ־ s ל־ u ואחריו הקשת u–v הוא מסלול ל־ v באורך d(u) + 1 , ולכן d(v) ≤ d(u) + 1 . באותו אופן d(u) ≤ d(v) + 1 . משני אי־השוויונים: |d(u) − d(v)| ≤ 1 .
(2) לא נכונה. דוגמה נגדית – גרף מכוון עם הקודקודים s, a, b, t והקשתות:
| קשת | s→a | s→b | b→a | a→t |
|---|---|---|---|---|
| משקל | 1 | 3 | 3− | 1 |
בגרף אין מעגל כלל (ולכן אין מעגל שלילי). דייקסטרה מ־ s: מוציא את s (0) ומעדכן a = 1 , b = 3 ; מוציא את a (1) – ערכו נקבע סופית – ומעדכן t = 2 ; מוציא את t (2) ; מוציא את b (3) – הקשת b→a הייתה נותנת ל־ a את הערך 0 , אבל a כבר הוצא ולא יעודכן שוב, ובוודאי שהשינוי לא יגיע ל־ t . התוצאה: d(t) = 2 . אבל המסלול s→b→a→t שוקל 3 + (3−) + 1 = 1 . כלומר דייקסטרה טעה.
(3) נכונה. בגרף עם n קודקודים יש לכל עץ פורש בדיוק n − 1 קשתות. לכן אחרי ההוספה המשקל של כל עץ פורש גדל באותו סכום בדיוק, (n − 1)·c . הסדר בין המשקלים של העצים הפורשים לא משתנה, ולכן עץ שהיה קל ביותר נשאר קל ביותר.
(4) לא נכונה. דוגמה נגדית – גרף לא מכוון עם הקודקודים s, a, b, t והקשתות s–a (1), a–b (1), b–t (1), s–t (4). המסלול הקל מ־ s ל־ t הוא s–a–b–t במשקל 3 (הקשת הישירה שוקלת 4). נוסיף c = 2 לכל קשת: s–a–b–t שוקל 3 + 3 + 3 = 9 , והקשת s–t שוקלת 6 . עכשיו המסלול הקל הוא s–t , והמסלול s–a–b–t כבר אינו קל ביותר. (הסיבה: במסלול עם k קשתות המשקל גדל ב־ k·c , ולכן מסלול עם יותר קשתות "נענש" יותר.)
(5) נכונה. נניח בשלילה שלכל קודקוד דרגת כניסה גדולה מ־ 0 . נתחיל בקודקוד כלשהו v₀ ונלך "אחורה": ל־ v₀ נכנסת קשת מקודקוד v₁ , ל־ v₁ נכנסת קשת מ־ v₂ , וכן הלאה. יש בגרף מספר סופי של קודקודים, ולכן אחרי n צעדים לכל היותר נגיע לקודקוד שכבר ביקרנו בו. הקשתות בין ההופעה הראשונה לשנייה שלו יוצרות מעגל מכוון – בסתירה לכך שהגרף חסר מעגלים.
(6) נכונה. בעץ BFS מ־ s העומק של כל קודקוד x שווה ל־ d(x) , המרחק הקצר ביותר (במספר קשתות) מ־ s , ולכן גובה עץ ה־ BFS הוא max d(x) . בעץ DFS מ־ s המסלול בעץ מ־ s ל־ x הוא מסלול בגרף, ולכן אורכו לפחות d(x) . כלומר בעץ ה־ DFS כל קודקוד נמצא בעומק ≥ d(x) , ובפרט הקודקוד שבו d(x) מקסימלי. לכן גובה עץ ה־ DFS ≥ גובה עץ ה־ BFS .
(7) לא נכונה. דוגמה נגדית – גרף מכוון עם הקשתות s→a (2), a→b (1−), b→t (1), s→b (3). בגרף יש קשת שלילית, אבל אין בו מעגל כלל. בלמן־פורד מסיים את n − 1 = 3 הסבבים עם d(s) = 0 , d(a) = 2 , d(b) = 1 , d(t) = 2 , ובסבב הבדיקה הנוסף אף קשת אינה משפרת ערך – לכן האלגוריתם מודיע שאין מעגל שלילי.
בדיקה: בדוגמה של (2) דייקסטרה נותן d(t) = 2 ובלמן־פורד נותן 1; בדוגמה של (4): לפני – s–a–b–t במשקל 3, אחרי – s–t במשקל 6.
טעות נפוצה: לחשוב שטענה (4) נכונה "כמו" טענה (3). בעצים פורשים מספר הקשתות קבוע, ובמסלולים – לא.
סעיף ב
H₁, H₃, H₅, H₇ הם גרפים "קרובים". H₂, H₄, H₆ אינם (למשל BFS מ־ A: ב־ H₂ D ברמה 3 , ב־ H₄ D ברמה 3 , ב־ H₆ E ו־ F ברמה 3).
מה נדרש: לקבוע לארבעה גרפים אם כל סריקת BFS מכל קודקוד נותנת עץ שבו כל הקודקודים ברמה 0, 1 או 2 ; ואם לא – להציג סריקה שבה יש קודקוד ברמה 3 .
רעיון: ב־ BFS הרמה של כל קודקוד בעץ שווה למרחק הקצר ביותר שלו (במספר קשתות) מן השורש – גם אם סדר בחירת השכנים משתנה (העץ עצמו יכול להשתנות, אבל הרמות לא). לכן גרף הוא "קרוב" אם ורק אם בין כל שני קודקודים יש מסלול של 2 קשתות לכל היותר. כדי להראות שגרף אינו "קרוב" מספיק למצוא שני קודקודים שהמרחק ביניהם 3 ולהריץ BFS מאחד מהם.
פתרון: (הקשתות כפי שבאיור)
| גרף | קשתות | "קרוב"? | נימוק / סריקה נגדית |
|---|---|---|---|
| H₁ | A–B, B–C, C–D, D–E, E–A (מעגל של 5) | כן | מכל קודקוד: שני שכניו ברמה 1 , ושני הקודקודים הנותרים שכנים שלהם – ברמה 2 |
| H₂ | A–B, B–C, C–D, D–E, E–F, F–A (מעגל של 6) | לא | BFS מ־ A: רמה 1 – B, F ; רמה 2 – C, E ; רמה 3 – D |
| H₃ | A–B, A–C, A–D, A–E, A–F (כוכב) | כן | מ־ A כל השאר ברמה 1 ; מכל קודקוד אחר: A ברמה 1 וכל השאר ברמה 2 |
| H₄ | A–B, B–C, C–D (מסלול) | לא | BFS מ־ A: רמה 1 – B ; רמה 2 – C ; רמה 3 – D |
| H₅ | E–A, E–B, A–B, B–C, C–D, D–A ("בית") | כן | הזוגות שאינם שכנים: E–C (דרך B), E–D (דרך A), A–C (דרך B), B–D (דרך A) – כולם במרחק 2 |
| H₆ | A–B, A–C, B–C, C–D, D–E, D–F, E–F (שני משולשים) | לא | BFS מ־ A: רמה 1 – B, C ; רמה 2 – D ; רמה 3 – E, F |
| H₇ | A–C, A–D, A–E, B–C, B–D, B–E | כן | A ו־ B שכנים של כל אחד מ־ C, D, E ; לכן שני קודקודים מ־{A, B} או שניים מ־{C, D, E} נמצאים במרחק 2 , וקודקודים משתי הקבוצות – שכנים |
בדיקה: BFS מכל קודקוד בכל אחד משבעת הגרפים: הגובה המרבי של עץ BFS הוא 2 ב־ H₁, H₃, H₅, H₇ , ו־ 3 ב־ H₂, H₄, H₆ (עם הרמות שבטבלה).
טעות נפוצה: לבדוק רק סריקה אחת. ב־ H₄ ו־ H₆ סריקה מקודקוד "אמצעי" (B ב־ H₄ , C ב־ H₆) נותנת עץ בגובה 2 – אבל ההגדרה דורשת זאת מכל קודקוד.
שאלה 5 · דייקסטרה וגבהים של עצי DFS (25 נקודות)
בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם גרף מכוון ממושקל G₁ :
(1) איזה אלגוריתם מחזיר את המסלולים הקצרים (הקלים) מקודקוד מקור לכל קודקודי הגרף, בגרף ממושקל כלשהו שכל משקליו אי־שליליים? מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.
נוסף על כך, הריצו את האלגוריתם שכתבתם, בעבור הגרף הנתון G₁ , מקודקוד S לקודקוד T . בצעו מעקב שלב אחר שלב: בכל שלב רשמו איזה קודקוד נבחר, ואת ערכי d (המרחק הידוע) ו־π (הקודקוד הקודם) של הקודקודים. רשמו את המסלול שהתקבל ואת אורכו (סכום משקליו).
עבור גרף G ממושקל כלשהו שכל משקליו מספרים שלמים חיוביים, הרצנו את האלגוריתם המוצא את המסלול הקצר (הקל) בין שני קודקודים s ו־t, וקיבלנו מסלול P .
– האם P יישאר בהכרח מסלול קצר ביותר בין s ל־t אם משקל של קשת אחת בגרף, שאינה נמצאת על המסלול P , יגדל ב־ x (0 < x) ? נמקו את תשובתכם.
– האם P יישאר בהכרח מסלול קצר ביותר בין s ל־t אם משקל כל אחת מן הקשתות בגרף יועלה בריבוע (כל משקל w יוחלף ב־ w²) ? נמקו את תשובתכם.
לפניכם גרף מכוון G :
(1) הציגו שתי סריקות DFS מקודקוד התחלה a כך שיתקבלו שני עצים שהגבהים שלהם שונים זה מזה.
הוסיפו מספר מינימלי של קשתות כך שבארבע סריקות DFS מקודקוד a , יתקבלו ארבעה עצים שהגבהים שלהם שונים זה מזה. סרטטו את הגרף לאחר ההוספה, והציגו את ארבע הסריקות.
◂ פתרון מלא לשאלה 5
סעיף א(1)
אלגוריתם דייקסטרה, O(V²) (במימוש עם ערימה: O((V+E)·log V)). סדר השליפה: S, K, L, N, M, T. המסלול: S→K→M→T, אורכו 16.
מה נדרש: לבחור אלגוריתם למסלולים קלים ביותר ממקור אחד כשהמשקלים אי־שליליים, לתת את הסיבוכיות שלו, ולהריץ אותו על G₁ מ־S ל־T.
רעיון: אלגוריתם דייקסטרה מתאים לכל גרף (מכוון או לא, עם מעגלים או בלי) שמשקליו אי־שליליים. בכל שלב שולפים את הקודקוד שטרם טופל עם d[] הקטן ביותר – ערכו כבר סופי, כי אין משקלים שליליים שיכולים להקטין אותו אחר כך – ומקלים את הקשתות היוצאות ממנו: אם d[u] + w(u,v) < d[v] אז d[v] ← d[u] + w(u,v) ו־π[v] ← u.
(BFS אינו מתאים – הוא סופר קשתות ולא משקלים; בלמן־פורד נכון אבל איטי יותר – O(V·E).)
סיבוכיות: יש V שליפות. במימוש עם מערך, כל שליפה היא חיפוש מינימום בין V קודקודים – O(V), ובסך הכול O(V²). כל קשת מוקלת פעם אחת (כשהקודקוד שממנו היא יוצאת נשלף) – O(E) ≤ O(V²). סך הכול O(V²). (במימוש עם ערימת מינימום: כל שליפה ועדכון O(log V), ובסך הכול O((V+E)·log V).)
פתרון – מעקב על G₁: בכל תא: d (π). קודקוד שנשלף מודגש, וערכו סופי.
| שלב | נשלף | S | K | L | M | N | T |
|---|---|---|---|---|---|---|---|
| אתחול | – | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | S (0) | 0 | 2 (S) | 7 (S) | ∞ | ∞ | ∞ |
| 2 | K (2) | 2 | 6 (K) | 13 (K) | ∞ | ∞ | |
| 3 | L (6) | 6 | 13 (K) | 12 (L) | ∞ | ||
| 4 | N (12) | 13 (K) | 12 | 17 (N) | |||
| 5 | M (13) | 13 | 16 (M) | ||||
| 6 | T (16) | 16 |
הסברים לשלבים:
שחזור המסלול לפי π מהסוף: T ← M ← K ← S.
המסלול: S → K → M → T, אורכו 2 + 11 + 3 = 16.
בדיקה: מעקב מלא אחרי דייקסטרה נותן בדיוק את הטבלה הזאת. בנוסף נמנו כל המסלולים הפשוטים מ־S ל־T: SKMT = 16, SKLNMT = 17, SKLNT = 17, SKLMT = 18, SLNMT = 18, SLNT = 18, SLMT = 19 – ואכן 16 הוא המינימום, והוא יחיד.
טעות נפוצה: לעצור כשמגיעים לראשונה ל־T (בשלב 4, d[T] = 17). ערך של קודקוד סופי רק כשהוא נשלף.
סעיף א(2)
הגדלת קשת אחת שאינה על P: כן – משקל P לא משתנה, ומשקל כל מסלול אחר לא קטן. העלאה בריבוע: לא בהכרח. למשל ב־G₁: S→K→M→T שוקל 4+121+9 = 134, אבל S→K→L→N→M→T שוקל 4+16+36+4+9 = 69.
מה נדרש: לבדוק אם המסלול הקצר P נשאר קצר אחרי (א) הגדלת משקל של קשת אחת שאינה על P, (ב) העלאת כל המשקלים בריבוע.
רעיון: נבדוק איך משתנה משקל של מסלול שלם בכל אחד מהשינויים.
פתרון:
הגדלת קשת e שאינה על P – כן, P נשאר קצר ביותר. הקשת e אינה על P, ולכן משקל P לא השתנה. כל מסלול אחר Q מ־s ל־t: אם Q אינו עובר ב־e – משקלו לא השתנה; אם הוא עובר ב־e – משקלו גדל. בכל מקרה, אחרי השינוי w(Q) ≥ w(Q הישן) ≥ w(P). לכן P עדיין מסלול קצר ביותר.
העלאה בריבוע – לא בהכרח. הריבוע "מעניש" קשתות כבדות הרבה יותר מקשתות קלות: קשת במשקל 11 הופכת ל־121, ואילו קשתות במשקלים 4, 6, 2 הופכות ל־16, 36, 4. לכן מסלול קצר שיש בו קשת כבדה אחת עלול להפסיד למסלול עם הרבה קשתות קלות.
דוגמה נגדית – הגרף G₁ מסעיף (1):
לפני השינוי S→K→M→T היה הקצר ביותר (16 < 17), ואחרי השינוי S→K→L→N→M→T קל יותר.
בדיקה: הגדלה של קשת של G₁ שאינה על המסלול (בכל ערך x) משאירה את S→K→M→T באורך 16 כמסלול הקצר ביותר. אחרי העלאת המשקלים בריבוע דייקסטרה החזיר S→K→L→N→M→T באורך 69.
סעיף ב(1)
סריקה 1: a→b→c→d, ואחר כך a→e – עץ בגובה 3. סריקה 2: a→c→d, ואחר כך a→b, a→e – עץ בגובה 2.
מה נדרש: שתי סריקות DFS מ־a שנותנות עצים בגבהים שונים.
רעיון: הקשתות בגרף: a→b , a→c , a→e , b→c , c→d. הגובה תלוי בשאלה אם c מתגלה דרך b (ואז d בעומק 3) או ישירות מ־a (ואז d בעומק 2).
פתרון:
סריקה 1 (סדר השכנים של a: b, c, e):
a → b → c → d (ל־d אין קשתות יוצאות, חוזרים עד a) → הקשת a→c מובילה לקודקוד שכבר התגלה → e.
קשתות העץ: a–b , b–c , c–d , a–e. גובה העץ: 3 (המסלול a–b–c–d).
סריקה 2 (סדר השכנים של a: c, b, e):
a → c → d (חוזרים ל־c ול־a) → b (הקשת b→c מובילה לקודקוד שכבר התגלה, חוזרים) → e.
קשתות העץ: a–c , c–d , a–b , a–e. גובה העץ: 2 (המסלול a–c–d).
בדיקה: בכל עצי ה־DFS האפשריים מ־a מתקבלים בדיוק שני גבהים – 2 ו־3, ושני העצים שלמעלה נמצאים ביניהם.
סעיף ב(2)
צריך להוסיף 2 קשתות, למשל a→d ו־d→e. גבהים: 1 (a→e, a→d, a→c, a→b), 2 (a→d→e, a→c, a→b), 3 (a→e, a→b→c→d), 4 (a→b→c→d→e).
מה נדרש: להוסיף כמה שפחות קשתות כך שיהיו ארבע סריקות DFS מ־a עם ארבעה גבהים שונים.
רעיון: בגרף יש 5 קודקודים, ולכן גובה עץ DFS שמכיל את כולם הוא 1, 2, 3 או 4. ארבעה גבהים שונים פירושם: כל הגבהים 1, 2, 3, 4. נבדוק מה כל אחד מהם דורש.
לכן צריך לפחות 2 קשתות. נראה ש־2 מספיקות.
פתרון: מוסיפים את הקשתות a→d ו־d→e (מקווקוות באדום):
ארבע סריקות מ־a:
| סריקה | סדר השכנים של a | מהלך | קשתות העץ | גובה |
|---|---|---|---|---|
| 1 | e, d, c, b | a→e; a→d (d→e כבר התגלה); a→c (c→d כבר התגלה); a→b (b→c כבר התגלה) | a–e , a–d , a–c , a–b | 1 |
| 2 | d, c, b, e | a→d→e; חוזרים; a→c (c→d כבר התגלה); a→b (b→c כבר התגלה); e כבר התגלה | a–d , d–e , a–c , a–b | 2 |
| 3 | e, b, … | a→e; a→b→c→d (d→e כבר התגלה); חוזרים עד a, כל השכנים כבר התגלו | a–e , a–b , b–c , c–d | 3 |
| 4 | b, … | a→b→c→d→e; חוזרים עד a, כל השכנים כבר התגלו | a–b , b–c , c–d , d–e | 4 |
מספר הקשתות שהוספנו: 2 – וזה המינימום. (גם הזוג a→d ו־e→b מתאים: בגובה 4 – a→e→b→c→d.)
בדיקה: בגרף המקורי מתקבלים רק הגבהים 2, 3; אף הוספה של קשת אחת לא נותנת 4 גבהים, ומבין ההוספות של שתי קשתות מתאימים בדיוק הזוגות {a→d , d→e} ו־{a→d , e→b}. ארבעת העצים שבטבלה נמצאו בין עצי ה־DFS של הגרף החדש.
שאלה 6 · מבוך עם דמי מעבר ואוצרות – המסלול הזול ביותר (25 נקודות)
במשחק מחשב יש מבוך של חדרים. בין חלק מן החדרים יש דלתות חד־כיווניות: אפשר לעבור בדלת רק בכיוון החץ.
לכל חדר יש ערך (מספר שלם):
המחיר של מסלול הוא סכום הערכים של החדרים שהשחקן נכנס אליהם במסלול. המחיר אינו כולל את ערך החדר שבו השחקן מתחיל את מסלולו, אך הוא כולל את ערך החדר שבו השחקן מסיים את מסלולו. המסלול הזול ביותר בין שני חדרים הוא המסלול שהמחיר שלו הקטן ביותר.
ידוע שבמבוך אין מסלול מעגלי (מסלול שחוזר אל החדר שממנו יצא) שהמחיר שלו שלילי.
לפניכם המבוך MAZE . כל עיגול מייצג חדר, והמספר שבמלבן ליד כל חדר הוא הערך שלו:
דוגמה: המחיר של המסלול A → B → C → E הוא 4 + (−3) + 1 = 2 .
במבוך MAZE , מהו המסלול הזול ביותר מחדר A לחדר H ? כתבו את שמות החדרים במסלול זה לפי הסדר, ואת המחיר שלו (אין צורך לבצע מעקב).
כתבו אלגוריתם המוצא בכל מבוך (שמקיים את התנאים שלעיל) את המסלול הזול ביותר מחדר K₁ לחדר K₂ .
הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
סרטטו את הגרף המייצג את המבוך MAZE הנתון לעיל, באופן שיתאים לאלגוריתם שכתבתם.
◂ פתרון מלא לשאלה 6
סעיף א
A → D → F → C → H , המחיר 5 + (−2) + (−3) + 2 = 2 .
מה נדרש: למצוא מסלול מ־ A ל־ H שסכום ערכי החדרים בו (בלי A , כולל H) מינימלי.
רעיון: כדאי לעבור דרך חדרי האוצר C (−3) ו־ F (−2), גם אם הדרך אליהם "יקרה" בתחילתה.
פתרון: המסלולים הפשוטים מ־ A ל־ H והמחיר שלהם:
| מסלול | חישוב | מחיר |
|---|---|---|
| A → D → F → C → H | 5 + (−2) + (−3) + 2 | 2 |
| A → B → C → H | 4 + (−3) + 2 | 3 |
| A → D → F → C → E → G → H | 5 − 2 − 3 + 1 + 3 + 2 | 6 |
| A → B → C → E → G → H | 4 − 3 + 1 + 3 + 2 | 7 |
| A → D → E → G → H | 5 + 1 + 3 + 2 | 11 |
המסלול הזול ביותר: A → D → F → C → H , במחיר 2 . (מסלול שחוזר לחדר אינו יכול להיות זול יותר, כי במבוך אין מסלול מעגלי במחיר שלילי.)
בדיקה: מניית כל המסלולים הפשוטים (הטבלה למעלה) ובלמן־פורד נותנים שניהם 2 , והמסלול הזה יחיד.
טעות נפוצה: לבחור את A → B → C → H כי הוא "נראה" קצר או כי הקשת הראשונה בו זולה יותר (4 < 5).
סעיף ב(1)
בונים גרף מכוון: קודקוד לכל חדר, ולכל דלת u → v קשת u → v שמשקלה ערך החדר v . מריצים בלמן־פורד מ־ K₁ (יש משקלים שליליים ואין מעגל שלילי), ומשחזרים את המסלול לפי π מ־ K₂ ; המחיר הוא d[K₂]. זמן ריצה O(|V|·|E|).
מה נדרש: אלגוריתם כללי למסלול הזול ביותר במבוך, בלי לעבור על כל המסלולים.
רעיון: המחיר "יושב" על החדרים, ואילו אלגוריתמי מסלולים קצרים עובדים עם משקלים על קשתות. כל כניסה לחדר v נעשית דרך דלת שמגיעה אל v , ולכן נותנים לכל קשת u → v את המשקל value(v) . כך משקל מסלול בגרף = סכום ערכי החדרים שנכנסים אליהם = בדיוק המחיר שהוגדר (ערך חדר המוצא לא נספר, ערך חדר היעד נספר).
יש משקלים שליליים (אוצרות), ולכן דייקסטרה אינו מתאים. מכיוון שאין מעגל במחיר שלילי, בלמן־פורד מוצא את המסלולים הזולים ביותר מ־ K₁ .
פתרון:
CheapestRoute(MAZE, K₁, K₂):
// שלב 1: בניית גרף מכוון ממושקל
לכל חדר – קודקוד
לכל דלת מחדר u לחדר v – קשת u → v שמשקלה value(v) // ערך החדר שנכנסים אליו
// שלב 2: בלמן־פורד מ־K₁
לכל קודקוד v: d[v] ← ∞ ; π[v] ← null
d[K₁] ← 0
חזור |V| − 1 פעמים:
לכל קשת u → v שמשקלה w:
אם d[u] + w < d[v]:
d[v] ← d[u] + w ; π[v] ← u
אם d[K₂] = ∞: החזר "אין מסלול"
// שלב 3: שחזור המסלול
route ← רשימה ריקה ; x ← K₂
כל עוד x ≠ null:
הוסף את x לתחילת route ; x ← π[x]
החזר את route ואת המחיר d[K₂]זמן ריצה: בניית הגרף O(|V| + |E|). בלמן־פורד: |V| − 1 סבבים, ובכל סבב עוברים על כל |E| הקשתות ⇒ O(|V|·|E|). השחזור O(|V|).
בדיקה: על המבוך MAZE עם K₁ = A , K₂ = H – טבלת הערכים d בסוף כל סבב (מעבר על הקשתות בסדר A→B , A→D , B→C , C→E , C→H , D→E , D→F , E→A , E→G , F→C , G→H , H→B ; בסוגריים – π):
| סבב | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| אתחול | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | 0 | 4 (A) | 0 (F) | 5 (A) | 2 (C) | 3 (D) | 5 (E) | 3 (C) |
| 2 | 0 | 4 (A) | 0 (F) | 5 (A) | 1 (C) | 3 (D) | 4 (E) | 2 (C) |
| 3 | 0 | 4 (A) | 0 (F) | 5 (A) | 1 (C) | 3 (D) | 4 (E) | 2 (C) |
בסבב 3 לא היה שינוי, ולכן אפשר לעצור. d[H] = 2 , ושחזור: H ← C ← F ← D ← A , כלומר A → D → F → C → H – כמו בסעיף א.
טעות נפוצה: להפעיל דייקסטרה. כאן דייקסטרה "סוגר" את C עם d = 1 (דרך B) ואת H עם d = 3 , לפני שהוא מגלה את המסלול הזול יותר דרך F (שבו d[C] = 0), ומחזיר מחיר 3 – תשובה שגויה.
סעיף ב(2)
גרף מכוון ממושקל עם הקודקודים A–H ו־12 קשתות (אחת לכל דלת); משקל הקשת u → v הוא ערך החדר v : A→B 4 , A→D 5 , B→C −3 , C→E 1 , C→H 2 , D→E 1 , D→F −2 , E→A 2 , E→G 3 , F→C −3 , G→H 2 , H→B 4 .
מה נדרש: לסרטט את הגרף שהאלגוריתם מסעיף (1) מקבל כקלט.
רעיון: אותם קודקודים ואותם חצים כמו במבוך; על כל קשת רושמים את ערך החדר שאליו היא נכנסת. לכן כל הקשתות הנכנסות לאותו חדר מקבלות אותו משקל (למשל B → C ו־ F → C שתיהן −3).
פתרון:
ובטבלה:
| קשת | A→B | A→D | B→C | C→E | C→H | D→E | D→F | E→A | E→G | F→C | G→H | H→B |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| משקל | 4 | 5 | -3 | 1 | 2 | 1 | -2 | 2 | 3 | -3 | 2 | 4 |
בדיקה: משקל המסלול A → B → C → E בגרף הוא 4 + (−3) + 1 = 2 – בדיוק המחיר שבדוגמה. אין בגרף מעגל במשקל שלילי (למשל המעגל B → C → H → B במשקל 3).
פרק שני (50 נקודות) – מודלים חישוביים
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 7 · טענות על שפות ואוטומט סופי דטרמיניסטי – רצף אסור ומניית אות (25 נקודות)
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.
לפניכם שתי טענות (1)–(2) בנוגע לשפות שמעל הא"ב {a, b} .
בעבור כל טענה, ציינו אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע,
ואם היא לא נכונה – הביאו דוגמה נגדית. אין קשר בין הטענות.
(1) אם L₂ היא שפה רגולרית ו־ L₁ ⊆ L₂ , בהכרח L₁ היא שפה רגולרית.
לכל שתי שפות L₁ , L₂ מתקיים: (L₁ ∩ L₂)ᴿ = L₁ᴿ ∩ L₂ᴿ .
Lᴿ מציין את השפה שמילותיה הן היפוכי המילים של L .
נתונה השפה L מעל הא"ב {a, b, c} :
L = {w | הרצף aa אינו מופיע ב־ w , #c(w) מתחלק ב־ 3 ללא שארית }
#c(w) מציין את מספר המופעים של c במילה w .
דוגמה למילה בשפה L היא abcbcac , כי מספר המופעים של האות c הוא 3 , והרצף aa אינו מופיע במילה.
(1) לפניכם חמש מילים. בנוגע לכל אחת מהן ציינו אם המילה שייכת לשפה L או לא. נמקו את תשובתכם.
ccc , baac , ε , acacbc , cbc .
בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L .
◂ פתרון מלא לשאלה 7
סעיף א(1)
לא נכונה. L₂ = Σ* רגולרית, ו־ L₁ = {aⁿbⁿ | n ≥ 0} ⊆ Σ*, אבל L₁ אינה רגולרית.
מה נדרש: לבדוק אם תת־שפה של שפה רגולרית היא בהכרח רגולרית.
רעיון: Σ* היא שפה רגולרית שמכילה כל שפה מעל הא"ב – גם שפות לא רגולריות.
פתרון: הטענה לא נכונה. דוגמה נגדית:
לכן תת־שפה של שפה רגולרית יכולה להיות לא רגולרית.
טעות נפוצה: לחשוב ש"שפה קטנה יותר היא פשוטה יותר". הרגולריות אינה תלויה בגודל השפה (Σ* אינסופית ורגולרית, ו־ L₁ קטנה ממנה ואינה רגולרית).
סעיף א(2)
נכונה. w ∈ (L₁ ∩ L₂)ᴿ ⇔ wᴿ ∈ L₁ ∩ L₂ ⇔ (wᴿ ∈ L₁ וגם wᴿ ∈ L₂) ⇔ (w ∈ L₁ᴿ וגם w ∈ L₂ᴿ) ⇔ w ∈ L₁ᴿ ∩ L₂ᴿ.
מה נדרש: להוכיח או להפריך שהיפוך של חיתוך שווה לחיתוך ההיפוכים.
רעיון: היפוך הוא "התאמה אחד לאחד" בין מילים: w ∈ Lᴿ אם ורק אם wᴿ ∈ L (כי (wᴿ)ᴿ = w). לכן אפשר לבדוק שייכות של מילה כלשהי לשני האגפים.
פתרון: הטענה נכונה. לכל מילה w:
לשני האגפים בדיוק אותן מילים, ולכן הם שווים.
בדיקה: דוגמה: L₁ = {ab, ba, aab}, L₂ = {ab, aab, b}. L₁ ∩ L₂ = {ab, aab}, ולכן (L₁ ∩ L₂)ᴿ = {ba, baa}. מצד שני L₁ᴿ = {ba, ab, baa}, L₂ᴿ = {ba, baa, b}, והחיתוך = {ba, baa} – שווה.
סעיף ב(1)
ccc ∈ L ; ε ∈ L ; acacbc ∈ L ; baac ∉ L (מכילה aa) ; cbc ∉ L (2 מופעים של c – לא מתחלק ב־ 3).
מה נדרש: לבדוק לכל מילה: (1) אין בה את הרצף aa; (2) #c(w) מתחלק ב־ 3.
פתרון:
| מילה | מופיע aa? | #c | מתחלק ב־ 3? | שייכת ל־ L? |
|---|---|---|---|---|
| ccc | לא | 3 | כן | כן |
| baac | כן | 1 | לא | לא |
| ε | לא | 0 | כן (0 = 3·0) | כן |
| acacbc | לא (ac, ca, ac, cb, bc) | 3 | כן | כן |
| cbc | לא | 2 | לא | לא |
בדיקה: הגדרת השפה והאוטומט מסעיף ב(2) נותנים בדיוק את התשובות האלה.
טעות נפוצה: לדחות את ε – אבל 0 מתחלק ב־ 3 ואין בה aa, ולכן ε ∈ L.
סעיף ב(2)
6 מצבים (האם האות האחרונה a × שארית #c בחלוקה ל־ 3): q0 (התחלה, מקבל), q1, q2, q3 (מקבל), q4, q5. מעברים: q0: a→q3, b→q0, c→q1 ; q1: a→q4, b→q1, c→q2 ; q2: a→q5, b→q2, c→q0 ; q3: b→q0, c→q1 ; q4: b→q1, c→q2 ; q5: b→q2, c→q0 (אין מעבר ב־ a מ־ q3, q4, q5).
מה נדרש: אוטומט סופי דטרמיניסטי עבור L, שמותר שיחסרו בו מעברים.
רעיון: האוטומט זוכר:
לכן 2 × 3 = 6 מצבים. מקבלים: המצבים שבהם השארית 0.
פתרון – Σ = {a, b, c}, מצב התחלתי q0, מצבים מקבלים {q0, q3}:
| מצב | משמעות | a | b | c |
|---|---|---|---|---|
| → q0 (מקבל) | שארית 0; האות האחרונה אינה a (או התחלה) | q3 | q0 | q1 |
| q1 | שארית 1; האות האחרונה אינה a | q4 | q1 | q2 |
| q2 | שארית 2; האות האחרונה אינה a | q5 | q2 | q0 |
| q3 (מקבל) | שארית 0; האות האחרונה a | – | q0 | q1 |
| q4 | שארית 1; האות האחרונה a | – | q1 | q2 |
| q5 | שארית 2; האות האחרונה a | – | q2 | q0 |
("–" = אין מעבר, המילה נדחית.)
בדיקה:
האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}.
טעות נפוצה: לבנות רק 3 מצבים לשארית ולשכוח לזכור את האות האחרונה – אז אי אפשר לזהות את הרצף aa.
שאלה 8 · פעולות על שפות ואוטומט מחסנית דטרמיניסטי – זוגות של a (25 נקודות)
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.
לפניכם שש שפות מעל הא"ב {a , b} :
Σ* – מציין את שפת כל המילים מעל הא"ב {a , b} .
Lᴿ – מציין את השפה שמילותיה הן היפוכי המילים של L .
| L₁ = {ε} | L₄ = {ab , b} |
| L₂ = Ø | L₅ = {ε , a , bb} |
| L₃ = Σ* | L₆ = {ba , ab , aab} |
כתבו את השפה המתקבלת מכל אחת מחמש הפעולות שלהלן:
(1) L₄ ∪ L₆
L₆ᴿ
L₃ ∩ L₆
L₂ ∪ L₁
L₅ • L₄
נתונה השפה L מעל הא"ב {a, b, c} :
L = {a²ⁿ bᵐ cⁿ⁺ᵐ | n , m >= 0}
בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L .
◂ פתרון מלא לשאלה 8
סעיף א(1)
L₄ ∪ L₆ = {b, ab, ba, aab}
מה נדרש: כל המילים שנמצאות לפחות באחת מהשפות L₄, L₆.
פתרון: L₄ = {ab, b}, L₆ = {ba, ab, aab}. המילה ab מופיעה בשתיהן, ובאיחוד היא נכתבת פעם אחת:
L₄ ∪ L₆ = {b, ab, ba, aab} (4 מילים).
סעיף א(2)
L₆ᴿ = {ab, ba, baa}
מה נדרש: להפוך כל מילה של L₆.
פתרון: baᴿ = ab, abᴿ = ba, aabᴿ = baa. לכן L₆ᴿ = {ab, ba, baa}.
טעות נפוצה: להפוך את סדר המילים בקבוצה במקום את סדר האותיות בכל מילה.
סעיף א(3)
L₃ ∩ L₆ = L₆ = {ba, ab, aab}
מה נדרש: המילים המשותפות ל־ Σ* ול־ L₆.
פתרון: כל מילה של L₆ היא מילה מעל {a, b}, ולכן שייכת ל־ L₃ = Σ*. החיתוך הוא L₆ כולה: L₃ ∩ L₆ = {ba, ab, aab}.
סעיף א(4)
L₂ ∪ L₁ = {ε}
מה נדרש: איחוד של השפה הריקה עם השפה {ε}.
פתרון: ב־ L₂ = Ø אין אף מילה, ולכן האיחוד מכיל רק את המילים של L₁: L₂ ∪ L₁ = {ε}.
טעות נפוצה: לחשוב ש־ {ε} היא "ריקה" ולכתוב Ø. ב־ {ε} יש מילה אחת – המילה הריקה.
סעיף א(5)
L₅ • L₄ = {b, ab, aab, bbb, bbab}
מה נדרש: כל השרשורים xy כאשר x ∈ L₅ ו־ y ∈ L₄.
פתרון:
| x ∈ L₅ | y = ab | y = b |
|---|---|---|
| ε | ab | b |
| a | aab | ab |
| bb | bbab | bbb |
המילה ab מתקבלת פעמיים (ε•ab ו־ a•b) ונכתבת פעם אחת: L₅ • L₄ = {b, ab, aab, bbb, bbab} (5 מילים).
סעיף ב
דוחפים סימן אחד לכל זוג aa (על ה־ a הראשון של הזוג; q1 = באמצע זוג) וסימן אחד לכל b; שולפים סימן לכל c. הסימן התחתון ביותר הוא Y, וכששולפים אותו עוברים למצב המקבל q5. מצבים מקבלים: q0 (בשביל ε) ו־ q5. אין מעברי ε.
מה נדרש: אוטומט מחסנית דטרמיניסטי ל־ L = {a²ⁿ bᵐ cⁿ⁺ᵐ | n, m ≥ 0}.
רעיון: מספר ה־ c צריך להיות מספר הזוגות של a ועוד מספר ה־ b. לכן:
כדי לדעת בלי מעברי ε מתי שלפנו את הסימן האחרון, הסימן הראשון שנדחף (התחתון ביותר מעל ⊥) הוא Y, וכל השאר X. כששולפים את Y עוברים למצב המקבל q5, שאין ממנו מעברים.
פתרון:
| מצב | קלט | ראש המחסנית | מצב חדש | מחליפים את הראש ב־ | משמעות |
|---|---|---|---|---|---|
| q0 | a | ⊥ | q1 | Y⊥ | ה־ a הראשון של הזוג הראשון: דוחפים Y (הסימן התחתון) |
| q1 | a | Y | q2 | Y | ה־ a השני של הזוג – בלי שינוי במחסנית |
| q1 | a | X | q2 | X | ה־ a השני של הזוג – בלי שינוי במחסנית |
| q2 | a | Y | q1 | XY | ה־ a הראשון של זוג נוסף: דוחפים X |
| q2 | a | X | q1 | XX | ה־ a הראשון של זוג נוסף: דוחפים X |
| q0 | b | ⊥ | q3 | Y⊥ | n = 0, ה־ b הראשון: דוחפים Y |
| q2 | b | Y | q3 | XY | b אחרי a²ⁿ: דוחפים X |
| q2 | b | X | q3 | XX | b אחרי a²ⁿ: דוחפים X |
| q3 | b | Y | q3 | XY | b נוסף: דוחפים X |
| q3 | b | X | q3 | XX | b נוסף: דוחפים X |
| q2 | c | X | q4 | ε | m = 0, ה־ c הראשון: שולפים |
| q2 | c | Y | q5 | ε | m = 0, n = 1: ה־ c היחיד – המחסנית מתרוקנת |
| q3 | c | X | q4 | ε | ה־ c הראשון: שולפים |
| q3 | c | Y | q5 | ε | ה־ c הראשון והאחרון: המחסנית מתרוקנת |
| q4 | c | X | q4 | ε | שולפים |
| q4 | c | Y | q5 | ε | שולפים את הסימן האחרון – המחסנית ריקה |
בכל צירוף (מצב, אות, ראש מחסנית) יש לכל היותר מעבר אחד ואין מעברי ε – האוטומט דטרמיניסטי. כל צירוף שאינו בטבלה = דחייה (למשל c ב־ q1, כלומר מספר אי־זוגי של a; a אחרי b; או כל אות אחרי שהגענו ל־ q5).
בדיקה – מעקב על aabbccc (n = 1, m = 2, ולכן 1 + 2 = 3 אותיות c):
| נקרא | מצב | מחסנית (ראש משמאל) |
|---|---|---|
| – | q0 | ⊥ |
| a | q1 | Y⊥ |
| a | q2 | Y⊥ |
| b | q3 | XY⊥ |
| b | q3 | XXY⊥ |
| c | q4 | XY⊥ |
| c | q4 | Y⊥ |
| c | q5 | ⊥ |
הקלט נגמר במצב המקבל q5 ⇒ המילה מתקבלת. לעומת זאת aaac נתקעת ב־ q1 (שלושה a – אי־זוגי), ו־ aabccc נתקעת ב־ q5 (c מיותר) – שתיהן נדחות.
האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}. מתקבלות למשל: ε, aac, bc, aaaacc, aabcc, aabbccc.
טעות נפוצה: לדחוף סימן על כל a – אז נדרשים 2n אותיות c במקום n.
שאלה 9 · מכונת טיורינג – המרה מבינארי לאונרי (25 נקודות)
כתבו מכונת טיורינג המקבלת בתחילת הסרט מספר בינארי הגדול מאפס (בלי אפסים מובילים, כלומר הספרה השמאלית היא 1), ומחזירה את אותו המספר בייצוג אונרי.
הנחיות:
– אין צורך לשמור על הקלט (אפשר לשנות את הקלט לסימנים שונים).
– המספר המוחזר יופיע במקום כלשהו בסרט בין שני סימני $ .
– אין צורך לבדוק את תקינות הקלט.
דוגמה ראשונה (המספר 6)
הסרט לפני ההרצה:
הסרט לאחר ההרצה:
דוגמה שנייה (המספר 11)
הסרט לפני ההרצה:
הסרט לאחר ההרצה:
כתבו מכונת טיורינג המקבלת בתחילת הסרט מספר בינארי הגדול מאפס, ומחזירה את אותו המספר בייצוג אונרי, כמפורט לעיל.
◂ פתרון מלא לשאלה 9
פתרון
כותבים $ מיד אחרי המספר הבינארי. בכל סבב מפחיתים 1 מהמספר הבינארי (מימין: 0 ← 1 עד שפוגשים 1, ו־1 ← 0) ומוסיפים 1 בסוף הסרט. כשההפחתה מגיעה ל־⊢ (המספר היה 0) – כותבים $ בתא הריק הראשון ⇒ $1ⁿ$.
מה נדרש: מכונת טיורינג שמקבלת אחרי ⊢ מספר בינארי n ≥ 1, ומשאירה על הסרט $1ⁿ$.
רעיון: "סופרים לאחור": כל עוד המספר הבינארי אינו 0 – מפחיתים ממנו 1 ומוסיפים 1 אחד לתוצאה האונרית. אחרי n סבבים המספר הבינארי הוא 0, ובתוצאה יש בדיוק n אחדות.
פתרון:
| מצב | קורא | כותב | תזוזה | מצב חדש | הסבר |
|---|---|---|---|---|---|
| q₀ | ⊢ | ⊢ | R | g | התחלה |
| g | 0 | 0 | R | g | ימינה עד סוף המספר |
| g | 1 | 1 | R | g | |
| g | △ | $ | L | d | $ אחרי המספר; חזרה לספרה הימנית |
| d | 0 | 1 | L | d | הפחתה: 0 ← 1 ו"לווים" שמאלה |
| d | 1 | 0 | R | a | הפחתה: 1 ← 0 – ההפחתה הסתיימה |
| d | ⊢ | ⊢ | R | z | המספר היה 0 – סיום |
| a | 0 | 0 | R | a | ימינה עד ה־$ |
| a | 1 | 1 | R | a | |
| a | $ | $ | R | a₂ | |
| a₂ | 1 | 1 | R | a₂ | ימינה עד סוף האחדות |
| a₂ | △ | 1 | L | b | מוסיפים 1 בסוף |
| b | 1 | 1 | L | b | חזרה שמאלה |
| b | $ | $ | L | d | הפחתה נוספת |
| z | 1 | 1 | R | z | ימינה (כל הספרות הפכו ל־1) |
| z | $ | $ | R | z₂ | |
| z₂ | 1 | 1 | R | z₂ | |
| z₂ | △ | $ | R | h | $ סוגר – עצירה |
מעקב – 110 (המספר 6) (הסרט בכל פעם שהמכונה מתחילה הפחתה, ובסוף):
| שלב | הסרט | המספר הבינארי | אחדות בתוצאה |
|---|---|---|---|
| $ אחרי המספר | ⊢110$ | 6 | 0 |
| אחרי סבב 1 | ⊢101$1 | 5 | 1 |
| אחרי סבב 2 | ⊢100$11 | 4 | 2 |
| אחרי סבב 3 | ⊢011$111 | 3 | 3 |
| אחרי סבב 4 | ⊢010$1111 | 2 | 4 |
| אחרי סבב 5 | ⊢001$11111 | 1 | 5 |
| אחרי סבב 6 | ⊢000$111111 | 0 | 6 |
| הפחתה נכשלת (מגיעים ל־⊢) ⇒ z | ⊢111$111111 | – | 6 |
| z₂ כותב $ – עצירה | ⊢111$111111$ | – | 6 |
בין שני ה־$: שש אחדות ✔ (כמו בדוגמה).
בדיקה: לכל n (קלט בינארי) נשארים על הסרט בדיוק שני סימני $ וביניהם n אחדות. למשל 1 ⇒ ⊢1$1$ (13 צעדים), 1011 ⇒ ⊢1111$11111111111$ (198 צעדים), 1000000 ⇒ 64 אחדות בין ה־$.
טעות נפוצה: בהפחתה, להפוך רק את הספרה הימנית (1 ← 0) בלי לטפל ב"לווה": כש־n זוגי הספרה הימנית היא 0, וצריך להפוך את כל האפסים שמימין ל־1 הקרוב ל־1, ואת ה־1 הזה ל־0.
תכנות מונחה עצמים
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 10 · משתלה – הכללה למחלקת־על חדשה ודריסה (25 נקודות)
משתלת "ירוק עד" מעוניינת למכור את מוצריה גם באופן מקוון (אונליין). בשלב הראשון החליטה המשתלה למכור באופן מקוון רק עצים ופרחים.
לשם כך נבנו המחלקות האלה:
– המחלקה Plant , המייצגת צמח
– המחלקה Tree , המייצגת עץ
– המחלקה Flower , המייצגת פרח
public class Plant {
private String code; // קוד המוצר
private String name; // שם הצמח
private String supplier; // שם הספק
private double price; // מחיר
private int height; // גובה בסנטימטרים
}
public class Tree extends Plant {
private int age; // גיל העץ בשנים
}
public class Flower extends Plant {
private String color; // צבע הפרח
private boolean perennial; // האם הפרח רב־שנתי
}הניחו שיש פעולות get ו־ set בעבור התכונות בכל המחלקות.
המחלקה Delivery מייצגת משלוח ללקוח. למחלקה שלוש תכונות:
(1) כתבו את כותרת המחלקה Delivery ואת התכונות שלה.
סרטטו תרשים הייררכייה המתאר את הקשר בין המחלקות: Plant , Tree , Flower , Delivery .
יש לסמן ירושה באמצעות החץ ◁——— והכלה באמצעות הסימן ◆——— .
בשלב השני החליטה המשתלה למכור באופן מקוון גם כלי גינון.
לפניכם המחלקה Tool המייצגת כלי גינון:
public class Tool {
private String code; // קוד המוצר
private String material; // החומר שממנו עשוי הכלי
private String supplier; // שם הספק
private double price; // מחיר
private int warranty; // תקופת האחריות בחודשים
}הניחו שיש פעולות get ו־ set בעבור תכונות המחלקה.
כדי שהמערך במחלקה Delivery יוכל להכיל גם כלי גינון, נעשו הפעולות האלה:
– הוגדרה המחלקה Item – מוצר.
– המערך plants במחלקה Delivery הוחלף במערך items מטיפוס Item .
– נכתבו במחלקות המתאימות (כולל במחלקה Tool) יחסי הורשה חדשים בינן ובין המחלקה Item .
– חלק מן התכונות שהופיעו עד עכשיו בכמה מן המחלקות האחרות (כולל המחלקה Tool) הועברו למחלקה Item , בהתאם לעקרונות תכנות מונחה עצמים (מעבר לתכונות אלו אין תכונות נוספות במחלקה Item).
(1) סרטטו תרשים הייררכייה מעודכן המתאר את הקשר בין המחלקות: Plant , Tree , Flower , Tool , Item , Delivery .
יש לסמן ירושה באמצעות החץ ◁——— והכלה באמצעות הסימן ◆——— .
כִּתבו את כותרת המחלקה Item ותכונותיה.
כִּתבו מחדש את המחלקות שחל בהן שינוי בעקבות ההוספה של המחלקה Item .
שימו לב: יש להתייחס גם ליחסי הורשה חדשים וגם לשינוי שחל בתכונות המחלקה.
בשלב האחרון החליטה המשתלה על מבצע סוף עונה: ברכישה מקוונת כל המוצרים יימכרו בהנחה של 5% , ובעבור צמחים (עצים ופרחים) תינתן הנחה נוספת של 20% מן המחיר שאחרי ההנחה הראשונה.
נתונה הפעולה הפנימית במחלקה Item :
public double getSalePrice()זימון הפעולה מחזיר את מחיר המוצר (עץ/פרח/כלי גינון) לאחר ההנחה – בהתאם לכל מוצר.
ממשו את הפעולה במחלקה Item , והוסיפו פעולה/ות במחלקה/ות המתאימה/ות כדי לבצע את הנדרש. ציינו בעבור כל פעולה שהוספתם באיזו מחלקה היא נוספה.
אין להשתמש בפעולה instanceof ובפעולות המחלקה Object ואין לשנות את תכונות המחלקות.
◂ פתרון מלא לשאלה 10
סעיף א(1)
public class Delivery { private String address; private Plant[] plants; private int count; }
מה נדרש – כותרת המחלקה Delivery ושלוש התכונות שלה.
רעיון – המערך צריך להכיל גם עצים וגם פרחים, ולכן טיפוס האיברים שלו הוא מחלקת־העל המשותפת Plant.
פתרון – :
public class Delivery {
private String address; // כתובת המשלוח
private Plant[] plants; // הצמחים במשלוח – עצים ופרחים
private int count; // מספר הצמחים הנוכחי במשלוח
}בדיקה – המחלקה תקינה יחד עם המחלקות הנתונות, ב־Java וב־C#.
public class Delivery {
private String address; // כתובת המשלוח
private Plant[] plants; // הצמחים במשלוח – עצים ופרחים
private int count; // מספר הצמחים הנוכחי במשלוח
}סעיף א(2)
Tree ◁— Plant, Flower ◁— Plant (ירושה); Delivery ◆— Plant (הכלה).
מה נדרש – תרשים הייררכייה של Plant , Tree , Flower , Delivery.
רעיון
פתרון
בדיקה – התרשים מתאים לקוד: Tree extends Plant, Flower extends Plant, ובמחלקה Delivery התכונה Plant[] plants.
סעיף ב(1)
Plant ו־Tool יורשות מ־Item; Tree ו־Flower יורשות מ־Plant; Delivery ◆— Item.
מה נדרש – תרשים מעודכן אחרי הוספת Item ו־Tool.
רעיון
פתרון
בדיקה – הקוד המעודכן (סעיף ב(3)) תקין, ומערך מטיפוס Item יכול לקבל עצמי Tree , Flower ו־Tool.
סעיף ב(2)
public class Item { private String code; private String supplier; private double price; }
מה נדרש – כותרת Item ותכונותיה.
רעיון – התכונות שמופיעות גם ב־Plant וגם ב־Tool הן code , supplier ו־price – הן עוברות ל־Item. name ו־height שייכות רק לצמח; material ו־warranty רק לכלי.
פתרון – :
public class Item {
private String code; // קוד המוצר
private String supplier; // שם הספק
private double price; // מחיר
}בדיקה – המחלקה תקינה ב־Java וב־C# יחד עם שאר המחלקות המעודכנות.
טעות נפוצה: לשכוח את supplier – גם היא משותפת לשתי המחלקות.
public class Item {
private String code; // קוד המוצר
private String supplier; // שם הספק
private double price; // מחיר
}סעיף ב(3)
Plant extends Item {name, height}; Tool extends Item {material, warranty}; Delivery: Item[] items. Tree ו־Flower ללא שינוי.
מה נדרש – לכתוב מחדש את המחלקות שהשתנו.
רעיון
פתרון – :
public class Plant extends Item {
private String name; // שם הצמח
private int height; // גובה בסנטימטרים
}
public class Tool extends Item {
private String material; // החומר שממנו עשוי הכלי
private int warranty; // תקופת האחריות בחודשים
}
public class Delivery {
private String address; // כתובת המשלוח
private Item[] items; // המוצרים במשלוח
private int count; // מספר המוצרים הנוכחי במשלוח
}בדיקה – כל המחלקות (כולל Tree ו־Flower ללא שינוי) תקינות, והשמה של new Tree(), new Flower() ו־new Tool() למערך מטיפוס Item תקינה (Java ו־C#).
public class Plant extends Item {
private String name; // שם הצמח
private int height; // גובה בסנטימטרים
}
public class Tool extends Item {
private String material; // החומר שממנו עשוי הכלי
private int warranty; // תקופת האחריות בחודשים
}
public class Delivery {
private String address; // כתובת המשלוח
private Item[] items; // המוצרים במשלוח
private int count; // מספר המוצרים הנוכחי במשלוח
}סעיף ג
Item: getSalePrice() { return price * 0.95; } Plant (דריסה): return super.getSalePrice() * 0.8; (ב־C#: virtual/override ו־base.GetSalePrice()).
מה נדרש – getSalePrice ב־Item ודריסה במקום המתאים, בלי instanceof (ב־C#: בלי is/as).
רעיון
price * 0.95.super.getSalePrice() * 0.8 – 20% הנחה מן המחיר שאחרי ההנחה הראשונה. Tree ו־Flower יורשות את הגרסה של Plant.virtual ב־Item ו־override ב־Plant, וזימון base.GetSalePrice().פתרון – :
public class Item {
private String code; // קוד המוצר
private String supplier; // שם הספק
private double price; // מחיר
public Item(String code, String supplier, double price) {
this.code = code;
this.supplier = supplier;
this.price = price;
}
public String getCode() { return code; }
public String getSupplier() { return supplier; }
public double getPrice() { return price; }
public double getSalePrice() {
return this.price * 0.95;
}
}
public class Plant extends Item {
private String name; // שם הצמח
private int height; // גובה בסנטימטרים
public Plant(String code, String supplier, double price, String name, int height) {
super(code, supplier, price);
this.name = name;
this.height = height;
}
public double getSalePrice() {
return super.getSalePrice() * 0.8;
}
}הפעולות שנוספו: getSalePrice במחלקה Item, ודריסה של getSalePrice במחלקה Plant.
בדיקה – עץ במחיר 200 → 200·0.95·0.8 = 152; פרח במחיר 40 → 30.4 (בהדפסה מתקבל 30.400000000000002 בגלל ייצוג מקורב של מספרים ממשיים); כלי במחיר 120 → 114 (Java ו־C#).
טעות נפוצה: לחשב לצמח הנחה של 25% (5% + 20%) – ההנחה הנוספת היא מן המחיר שאחרי ההנחה הראשונה, כלומר 0.95·0.8 = 0.76 (הנחה כוללת של 24%).
public class Item {
private String code; // קוד המוצר
private String supplier; // שם הספק
private double price; // מחיר
public Item(String code, String supplier, double price) {
this.code = code;
this.supplier = supplier;
this.price = price;
}
public String getCode() { return code; }
public String getSupplier() { return supplier; }
public double getPrice() { return price; }
public double getSalePrice() {
return this.price * 0.95;
}
}
public class Plant extends Item {
private String name; // שם הצמח
private int height; // גובה בסנטימטרים
public Plant(String code, String supplier, double price, String name, int height) {
super(code, supplier, price);
this.name = name;
this.height = height;
}
public double getSalePrice() {
return super.getSalePrice() * 0.8;
}
}שאלה 11 · פעולות בונות לפי תרשים עצמים – העתקה הפוכה ושיתוף עצם (25 נקודות)
לפניכם כותרות המחלקות NN , MM והתכונות שלהן.
הפעולות הבונות של המחלקות מסומנות ב־ * (תיתכן יותר מפעולה בונה אחת למחלקה).
public class MM
{
private int k;
private int m;
***
}
public class NN extends MM
{
private MM g;
***
}הערה: שימו לב – לשתי המחלקות אין פעולות get ו־ set .
לפניכם המחלקה Test , הכוללת פעולה ראשית:
public class Test {
public static void main(String[] args) {
MM m1 = new MM (4, 7);
MM m2 = new MM (5);
MM m3 = new MM (9);
MM m4 = new MM (m1);
NN n1 = new NN (m3);
NN n2 = new NN (3, 1);
NN n3 = new NN (2, 6);
NN n4 = new NN (n3);
}
}לפניכם תרשים של עצמים שנוצרו בעקבות הרצת קטע הקוד.
כתבו במחלקות MM ו־ NN את הפעולות הבונות הנדרשות כדי לקבל את העצמים שבתרשים.
ציינו בעבור כל אחד מן העצמים שנוצרו את הפעולה הבונה המתאימה לו.
הערה: אין להוסיף פעולות שאינן בונות במחלקות MM ו־ NN . פתרון המוסיף פעולות שאינן בונות לא יזוכה בנקודות.
◂ פתרון מלא לשאלה 11
פתרון
MM: MM(int k, int m), MM(int v) { k = m = v }, MM(MM other) { k = other.m; m = other.k }. NN: NN(MM g) { super(0); this.g = g }, NN(int k, int m) { super(k, m); g = new MM(k + m) }, NN(NN other) { super(other); this.g = other.g }.
מה נדרש – להשלים ב־MM וב־NN פעולות בונות בלבד, כך שהרצת Test תיצור בדיוק את העצמים שבתרשים, ולציין לכל עצם איזו פעולה בונה יצרה אותו.
רעיון – עוברים על הקריאות לפי סוג הפרמטרים ומשווים לתרשים:
new MM (5) נותן k = 5 ו־m = 5 (וגם new MM (9) נותן 9 ו־9) – הפרמטר היחיד מוצב בשתי התכונות.m4 = new MM (m1) הוא עצם חדש שבו k = 7 ו־m = 4, כלומר הערכים של m1 בסדר הפוך – פעולה בונה מעתיקה שמחליפה בין התכונות. היא כתובה בתוך MM, ולכן מותר לה לקרוא את other.k ו־other.m הפרטיות.new NN (m3)), עם (int, int) ועם NN (new NN (n3)). n3 הוא עצם NN, ולכן הקריאה new NN (n3) תפעיל פעולה בונה שהפרמטר שלה מטיפוס NN, אם קיימת כזו (היא המתאימה ביותר); בלעדיה הייתה רצה NN(MM g) ונותנת k = 0, m = 0, g = n3 – וזה לא מה שבתרשים. לכן צריך שלוש פעולות בונות ב־NN.super(...)/base(...).super(0) ושמירת ההפניה.super(other); ו־g של n4 מפנה לאותו עצם שאליו מפנה g של n3 (בתרשים שני החצים מגיעים לאותה קופסה) – this.g = other.g. הגישה ל־other.g מותרת כי היא כתובה בתוך NN.פתרון
public class MM
{
private int k;
private int m;
public MM(int k, int m)
{
this.k = k;
this.m = m;
}
public MM(int v)
{
this.k = v;
this.m = v;
}
public MM(MM other)
{
this.k = other.m;
this.m = other.k;
}
}
public class NN extends MM
{
private MM g;
public NN(MM g)
{
super(0);
this.g = g;
}
public NN(int k, int m)
{
super(k, m);
this.g = new MM(k + m);
}
public NN(NN other)
{
super(other);
this.g = other.g;
}
}הפעולה הבונה של כל עצם:
| עצם | הקריאה | הפעולה הבונה | מה מתקבל |
|---|---|---|---|
| m1 | new MM (4, 7) | MM(int k, int m) | k = 4, m = 7 |
| m2 | new MM (5) | MM(int v) | k = 5, m = 5 |
| m3 | new MM (9) | MM(int v) | k = 9, m = 9 |
| m4 | new MM (m1) | MM(MM other) – פעולה בונה מעתיקה | עצם חדש: k = 7, m = 4 |
| n1 | new NN (m3) | NN(MM g) | k = 0, m = 0, g מפנה אל m3 עצמו |
| n2 | new NN (3, 1) | NN(int k, int m) | k = 3, m = 1, g מפנה לעצם MM חדש (4, 4) |
| n3 | new NN (2, 6) | NN(int k, int m) | k = 2, m = 6, g מפנה לעצם MM חדש (8, 8) |
| n4 | new NN (n3) | NN(NN other) (ובתוכה MM(MM other) דרך super/base) | k = 6, m = 2, g מפנה לאותו עצם כמו g של n3 |
בדיקה – ערכי השדות אחרי Test: m1…m4 = (4,7), (5,5), (9,9), (7,4); n1 = (0,0) ו־g הוא m3 עצמו; n2 = (3,1) עם g חדש (4,4); n3 = (2,6) עם g חדש (8,8); n4 = (6,2), ו־g של n4 הוא אותו עצם כמו g של n3; m4 אינו m1 – הכול תואם לתרשים.
טעות נפוצה: ב־n4 לכתוב this.g = new MM(other.g) – זה יוצר קופסה שלישית, ובתרשים g של n3 ו־g של n4 מפנים לאותה קופסה. וגם: לנסות לכתוב ב־NN super(other.m, other.k) – התכונות פרטיות ב־MM ואין פעולות get.
public class MM
{
private int k;
private int m;
public MM(int k, int m)
{
this.k = k;
this.m = m;
}
public MM(int v)
{
this.k = v;
this.m = v;
}
public MM(MM other)
{
this.k = other.m;
this.m = other.k;
}
}
public class NN extends MM
{
private MM g;
public NN(MM g)
{
super(0);
this.g = g;
}
public NN(int k, int m)
{
super(k, m);
this.g = new MM(k + m);
}
public NN(NN other)
{
super(other);
this.g = other.g;
}
}שאלה 12 · P, Q, R, S – העמסה, דריסה ופולימורפיזם (25 נקודות)
לשאלה זו שני נוסחים: בשפת Java ובשפת C# .
לפותרים בשפת Java
נתונות המחלקות P , Q , R , S :
public class P {
private int k;
public P (int k) { this.k = k; }
public int getK() { return k; }
public int show (int x) {
System.out.println ("P-int");
return k + x;
}
}
---------------------------------------------
public class Q extends P {
public Q (int k) { super (k * 3); }
public int show (P other) {
System.out.println ("Q-P");
return getK() - other.getK();
}
public int show (int x) {
System.out.println ("Q-int");
return super.show (x + 1);
}
}
---------------------------------------------
public class R extends Q {
public R (int k) { super (k - 1); }
public int show (Q other) {
System.out.println ("R-Q");
return other.getK();
}
}
---------------------------------------------
public class S extends P {
public S (int k) { super (k + 4); }
public int show (P other) {
System.out.println ("S-P");
return other.show (getK());
}
}סרטטו את תרשים ההייררכייה של המחלקות P , Q , R , S . יש לסמן ירושה באמצעות החץ ◁——— .
נתונה המחלקה Tester :
public class Tester {
public static void main (String[] args) {
P p = new P (2);
Q q = new Q (1);
R r = new R (4);
S s = new S (3);
P pq = new Q (2);
Q qr = new R (5);
//***
}
}סרטטו את העצמים שנוצרו בפעולה main .
במקום המסומן ב־ * נוסף קטע הקוד התקין שלפניכם:
System.out.println (pq.show(1)); //(1)
System.out.println (qr.show(r)); //(2)
System.out.println (r.show(qr)); //(3)
System.out.println (((Q)pq).show(s)); //(4)
System.out.println (s.show(pq)); //(5)כתבו את הפלט של הפעולה (כתבו את מספר השורה המשויך לכל פלט).
◂ פתרון מלא לשאלה 12
סעיף א
Q ו־S יורשות מ־P; R יורשת מ־Q.
מה נדרש – תרשים ירושה של P, Q, R, S.
רעיון – לפי הכותרות: Q extends P (ב־C#: Q : P), R extends Q, S extends P. כלומר Q ו־S הן "אחיות" שיורשות מ־P, ו־R יורשת מ־Q (ובעקיפין גם מ־P). אין קשר ירושה בין S לבין Q או R.
פתרון
בדיקה – התרשים מתאים לכותרות המחלקות; הקוד תקין ב־Java וב־C# עם ההייררכייה הזאת.
סעיף ב(1)
p→P(k=2), q→Q(k=3), r→R(k=9), s→S(k=7), pq (מוצהר P)→Q(k=6), qr (מוצהר Q)→R(k=12)
מה נדרש – לסרטט את ששת העצמים: לכל משתנה – הטיפוס המוצהר שלו, חץ אל העצם, הטיפוס בפועל של העצם וערך התכונה k.
רעיון – לכל העצמים יש תכונה אחת, k, שמוגדרת ב־P. נחשב אותה לפי שרשור הפעולות הבונות:
P(k) – מציבה k.Q(k) – קוראת ל־P(k * 3).R(k) – קוראת ל־Q(k - 1), כלומר (k − 1)·3.S(k) – קוראת ל־P(k + 4).| משתנה | טיפוס מוצהר | טיפוס העצם בפועל | חישוב | k |
|---|---|---|---|---|
| p | P | P | 2 | 2 |
| q | Q | Q | 1·3 | 3 |
| r | R | R | (4 − 1)·3 | 9 |
| s | S | S | 3 + 4 | 7 |
| pq | P | Q | 2·3 | 6 |
| qr | Q | R | (5 − 1)·3 | 12 |
פתרון – התרשים (משמאל המשתנה עם הטיפוס המוצהר, מימין העצם עם הטיפוס שלו בפועל):
בדיקה – הדפסה של getK() לכל עצם נותנת את הערכים 2, 3, 9, 7, 6, 12, ב־Java וב־C#.
טעות נפוצה: ב־R לחשב (4·3) − 1 = 11 – הפעולה הבונה של R מחסירה 1 לפני שהיא מעבירה ל־Q, ו־Q היא שמכפילה ב־3.
סעיף ב(2)
(1) Q-int P-int 8 (2) Q-P 3 (3) R-Q 12 (4) Q-P -1 (5) S-P Q-int P-int 14 (הפלט זהה ב־Java וב־C#)
מה נדרש – הפלט של חמש השורות, עם מספר השורה.
רעיון – שני שלבים בכל קריאה:
הפעולות: ב־P – show(int); ב־Q – show(P) חדשה ו־show(int) שדורסת את של P; ב־R – show(Q) חדשה; ב־S – show(P) חדשה (S אינה קשורה ל־Q). ערכי k (מסעיף ב1): p=2, q=3, r=9, s=7, pq=6, qr=12.
| שורה | בחירת הפעולה | ביצוע | פלט |
|---|---|---|---|
(1) pq.show(1) | pq מוצהר P ← show(int); בפועל Q ← הגרסה הדורסת של Q | Q-int, ואז super.show(2): P-int, 6 + 2 = 8 | Q-int, P-int, 8 |
(2) qr.show(r) | qr מוצהר Q: מתאימה רק show(P) (r הוא P). ל־R יש show(Q), אבל היא לא דורסת את show(P) – חתימה אחרת | getK() - other.getK() = 12 − 9 | Q-P, 3 |
(3) r.show(qr) | r מוצהר R: מתאימות show(Q) ו־show(P); נבחרת הספציפית ביותר – show(Q) | מחזירה את k של qr = 12 | R-Q, 12 |
(4) ((Q)pq).show(s) | ההמרה תקינה (העצם הוא Q). s אינו Q אבל הוא P ← show(P) של Q | 6 − 7 | Q-P, -1 |
(5) s.show(pq) | show(P) של S | S-P, ואז pq.show(7): pq בפועל Q ← Q-int, super.show(8) ← P-int, 6 + 8 = 14 | S-P, Q-int, P-int, 14 |
פתרון – הפלט:
(1) Q-int
P-int
8
(2) Q-P
3
(3) R-Q
12
(4) Q-P
-1
(5) S-P
Q-int
P-int
14ב־C# הפלט זהה (המחרוזות המודפסות זהות, והערכים המוחזרים הם מספרים). ב־C# הדריסה בשורות (1) ו־(5) מתרחשת כי Show(int) מוגדרת ב־P כ־virtual וב־Q כ־override; ב־Java כל פעולה ניתנת לדריסה בלי מילת מפתח.
בדיקה – הקוד כפי שהוא (Java ו־C#) מדפיס בדיוק את הפלט שלמעלה.
טעות נפוצה: בשורה (2) לחשוב שבגלל שהעצם הוא R תופעל show(Q) של R – המהדר בוחר לפי הטיפוס המוצהר Q, ושם יש רק show(P); ו־R לא דורסת אותה. בשורה (5) – לשכוח ש־other.show(getK()) היא קריאה פולימורפית שמגיעה ל־Q ומשם ל־P.
טבלת התשובות
| שאלה | סעיף | תשובה |
|---|---|---|
| 1 | א(1) | בכל סבב מוציאים את העדכון הראשון; עוברים לפי הסדר על שאר העדכונים: של אותו מוצר – last = המחיר שלו (דורס), של מוצר אחר – לתור עזר שמחליף את qUpd; מכניסים new Update(product, last). |
| א(2) | O(n²) – לכל מוצר עוברים על כל העדכונים שנותרו: (n−1)+(n−2)+…+1 במקרה הגרוע. | |
| ב(1) | latest = latestPrices(qUpd); לכל עדכון ב־latest מחפשים את מחיר המוצר ב־yesterday בעזרת פעולת עזר שמעבירה את yesterday דרך תור עזר ומחזירה אותו למצבו; אם המחיר התקף גבוה יותר – מכניסים את הקוד לתוצאה. | |
| ב(2) | O(n² + n·m): latestPrices – O(n²); לכל אחד מ־k ≤ n המוצרים חיפוש ב־yesterday ב־O(m) ⇒ O(n·m). | |
| 2 | א | מקדמים pc ו־pn במקביל; אם pos ≤ pn.getValue() מחזירים pc.getValue(), אחרת pos −= pn.getValue() ומתקדמים; אם השרשרת נגמרה – '#'. |
| ב | מחשבים total = סכום counts; לכל i מ־1 עד total/2 משווים charAt(i) ל־charAt(total+1−i); אם יש אי־התאמה – false, אחרת true. | |
| 3 | - | רקורסיה שמורידה מ־ sum את ערך הצומת: בעלה מחזירים 1 אם נשאר 0 (אחרת 0); בצומת אחר מחזירים את סכום הקריאות לבנים הקיימים עם rest = sum − ערך הצומת. בדוגמה (sum = 12) מתקבל 3, ובעבור sum = 9 מתקבל 0. |
| 4 | א | (1) נכונה; (2) לא נכונה; (3) נכונה; (4) לא נכונה; (5) נכונה; (6) נכונה; (7) לא נכונה. (מספיק לענות על חמש מהן.) |
| ב | H₁, H₃, H₅, H₇ הם גרפים "קרובים". H₂, H₄, H₆ אינם (למשל BFS מ־ A: ב־ H₂ D ברמה 3 , ב־ H₄ D ברמה 3 , ב־ H₆ E ו־ F ברמה 3). | |
| 5 | א(1) | אלגוריתם דייקסטרה, O(V²) (במימוש עם ערימה: O((V+E)·log V)). סדר השליפה: S, K, L, N, M, T. המסלול: S→K→M→T, אורכו 16. |
| א(2) | הגדלת קשת אחת שאינה על P: כן – משקל P לא משתנה, ומשקל כל מסלול אחר לא קטן. העלאה בריבוע: לא בהכרח. למשל ב־G₁: S→K→M→T שוקל 4+121+9 = 134, אבל S→K→L→N→M→T שוקל 4+16+36+4+9 = 69. | |
| ב(1) | סריקה 1: a→b→c→d, ואחר כך a→e – עץ בגובה 3. סריקה 2: a→c→d, ואחר כך a→b, a→e – עץ בגובה 2. | |
| ב(2) | צריך להוסיף 2 קשתות, למשל a→d ו־d→e. גבהים: 1 (a→e, a→d, a→c, a→b), 2 (a→d→e, a→c, a→b), 3 (a→e, a→b→c→d), 4 (a→b→c→d→e). | |
| 6 | א | A → D → F → C → H , המחיר 5 + (−2) + (−3) + 2 = 2 . |
| ב(1) | בונים גרף מכוון: קודקוד לכל חדר, ולכל דלת u → v קשת u → v שמשקלה ערך החדר v . מריצים בלמן־פורד מ־ K₁ (יש משקלים שליליים ואין מעגל שלילי), ומשחזרים את המסלול לפי π מ־ K₂ ; המחיר הוא d[K₂]. זמן ריצה O(|V|·|E|). | |
| ב(2) | גרף מכוון ממושקל עם הקודקודים A–H ו־12 קשתות (אחת לכל דלת); משקל הקשת u → v הוא ערך החדר v : A→B 4 , A→D 5 , B→C −3 , C→E 1 , C→H 2 , D→E 1 , D→F −2 , E→A 2 , E→G 3 , F→C −3 , G→H 2 , H→B 4 . | |
| 7 | א(1) | לא נכונה. L₂ = Σ* רגולרית, ו־ L₁ = {aⁿbⁿ | n ≥ 0} ⊆ Σ*, אבל L₁ אינה רגולרית. |
| א(2) | נכונה. w ∈ (L₁ ∩ L₂)ᴿ ⇔ wᴿ ∈ L₁ ∩ L₂ ⇔ (wᴿ ∈ L₁ וגם wᴿ ∈ L₂) ⇔ (w ∈ L₁ᴿ וגם w ∈ L₂ᴿ) ⇔ w ∈ L₁ᴿ ∩ L₂ᴿ. | |
| ב(1) | ccc ∈ L ; ε ∈ L ; acacbc ∈ L ; baac ∉ L (מכילה aa) ; cbc ∉ L (2 מופעים של c – לא מתחלק ב־ 3). | |
| ב(2) | 6 מצבים (האם האות האחרונה a × שארית #c בחלוקה ל־ 3): q0 (התחלה, מקבל), q1, q2, q3 (מקבל), q4, q5. מעברים: q0: a→q3, b→q0, c→q1 ; q1: a→q4, b→q1, c→q2 ; q2: a→q5, b→q2, c→q0 ; q3: b→q0, c→q1 ; q4: b→q1, c→q2 ; q5: b→q2, c→q0 (אין מעבר ב־ a מ־ q3, q4, q5). | |
| 8 | א(1) | L₄ ∪ L₆ = {b, ab, ba, aab} |
| א(2) | L₆ᴿ = {ab, ba, baa} | |
| א(3) | L₃ ∩ L₆ = L₆ = {ba, ab, aab} | |
| א(4) | L₂ ∪ L₁ = {ε} | |
| א(5) | L₅ • L₄ = {b, ab, aab, bbb, bbab} | |
| ב | דוחפים סימן אחד לכל זוג aa (על ה־ a הראשון של הזוג; q1 = באמצע זוג) וסימן אחד לכל b; שולפים סימן לכל c. הסימן התחתון ביותר הוא Y, וכששולפים אותו עוברים למצב המקבל q5. מצבים מקבלים: q0 (בשביל ε) ו־ q5. אין מעברי ε. | |
| 9 | - | כותבים $ מיד אחרי המספר הבינארי. בכל סבב מפחיתים 1 מהמספר הבינארי (מימין: 0 ← 1 עד שפוגשים 1, ו־1 ← 0) ומוסיפים 1 בסוף הסרט. כשההפחתה מגיעה ל־⊢ (המספר היה 0) – כותבים $ בתא הריק הראשון ⇒ $1ⁿ$. |
| 10 | א(1) | public class Delivery { private String address; private Plant[] plants; private int count; } |
| א(2) | Tree ◁— Plant, Flower ◁— Plant (ירושה); Delivery ◆— Plant (הכלה). | |
| ב(1) | Plant ו־Tool יורשות מ־Item; Tree ו־Flower יורשות מ־Plant; Delivery ◆— Item. | |
| ב(2) | public class Item { private String code; private String supplier; private double price; } | |
| ב(3) | Plant extends Item {name, height}; Tool extends Item {material, warranty}; Delivery: Item[] items. Tree ו־Flower ללא שינוי. | |
| ג | Item: getSalePrice() { return price * 0.95; } Plant (דריסה): return super.getSalePrice() * 0.8; (ב־C#: virtual/override ו־base.GetSalePrice()). | |
| 11 | - | MM: MM(int k, int m), MM(int v) { k = m = v }, MM(MM other) { k = other.m; m = other.k }. NN: NN(MM g) { super(0); this.g = g }, NN(int k, int m) { super(k, m); g = new MM(k + m) }, NN(NN other) { super(other); this.g = other.g }. |
| 12 | א | Q ו־S יורשות מ־P; R יורשת מ־Q. |
| ב(1) | p→P(k=2), q→Q(k=3), r→R(k=9), s→S(k=7), pq (מוצהר P)→Q(k=6), qr (מוצהר Q)→R(k=12) | |
| ב(2) | (1) Q-int P-int 8 (2) Q-P 3 (3) R-Q 12 (4) Q-P -1 (5) S-P Q-int P-int 14 (הפלט זהה ב־Java וב־C#) |