מתכונת 8 במדעי המחשב - מבני נתונים ומסלול 899271

מה נדרש: לעקוב אחר ppp(q, 4) (ב־C#: Ppp) על התור שבאיור ולכתוב מה מוחזר. מראש התור (משמאל) לסופו: 4, 2, 7, 7, 5, 9, 3.

רעיון: הפעולה מכניסה −1 לסוף התור כ"סימן עצירה" (כל המספרים בתור גדולים מ־0). אחר כך היא מסובבת את התור: מוציאה כל איבר x מהראש ומחזירה אותו לסוף, עד שה־−1 מגיע לראש. במהלך הסיבוב max הוא הגדול ביותר מבין האיברים שכבר עברו, ו־c גדל ב־1 בכל פעם ש־x גדול ממש מ־max.

פתרון – טבלת מעקב (k = 4). כל שורה היא סיבוב אחד של הלולאה: התור – כפי שהוא בתחילת הסיבוב (הראש משמאל), max ו־c – הערכים בסוף הסיבוב.

בשורה האחרונה בראש התור −1, ולכן הלולאה מסתיימת. q.remove() מוציא את ה־−1, והתור חוזר להיות 4, 2, 7, 7, 5, 9, 3 – בדיוק כמו בהתחלה.
c = 3, והתנאי c >= k הוא 3 >= 4 ⇒ הפעולה מחזירה false.

בדיקה: על הקוד של השאלה: ppp(q, 4) = false, והתור אחרי הקריאה: [4, 2, 7, 7, 5, 9, 3].

טעות נפוצה: לספור גם את ה־7 השני – הוא אינו גדול ממש מ־max = 7, ולכן c לא גדל.

מה נדרש: להסביר מה ppp עושה.

הסבר: הפעולה עוברת על איברי התור לפי הסדר מהראש לסוף, ו־max שומר את הגדול ביותר מבין האיברים שכבר נבדקו. c סופר את האיברים שגדולים מכל האיברים שלפניהם ("שיאים"): האיבר הראשון תמיד נספר (כי max מתחיל ב־0 וכל המספרים חיוביים), ואיבר נוסף נספר רק אם הוא שובר את השיא הקודם.

תשובה: הפעולה מחזירה true אם בתור q יש לפחות k איברים שכל אחד מהם גדול מכל האיברים שלפניו בתור, ואחרת false. בסיום הפעולה התור q חוזר למצבו המקורי (אותם איברים באותו סדר).

בדיקה: על התור 4, 2, 7, 7, 5, 9, 3: השיאים הם 4, 7, 9 ⇒ k = 1, 2, 3 ⇒ true; k = 4, 5, 6, 7 ⇒ false.

טעות נפוצה: לחשוב שהפעולה סופרת ערכים שונים בתור (בתור שלנו יש 6 ערכים שונים), או איברים שגדולים רק מן האיבר הסמוך שלפניהם – הספירה היא מול כל האיברים הקודמים. למשל בתור 5, 1, 3 יש שיא אחד בלבד (5), אף ש־3 גדול מ־1.

מה נדרש: סיבוכיות זמן הריצה של ppp, עם נימוק.

תשובה: O(n), כאשר n מספר האיברים בתור q.

נימוק: הלולאה while מעבירה בכל סיבוב איבר אחד מראש התור לסופו, ונעצרת כשה־−1 (שהוכנס לסוף) מגיע לראש – כלומר בדיוק n סיבובים. בכל סיבוב מתבצע מספר קבוע של פעולות שכל אחת O(1) (head, remove, insert, השוואה). מחוץ ללולאה – מספר קבוע של פעולות. סך הכול n·O(1) + O(1) = O(n).

מה נדרש: לעקוב אחר find(q, 1) (ב־C#: Find) ולכתוב מה מוחזר. התור: 4, 2, 7, 7, 5, 9, 3.

רעיון: find עולה מ־k = 1 כלפי מעלה: כל עוד ppp(q, k) מחזירה true היא קוראת לעצמה עם k + 1, ובפעם הראשונה ש־ppp(q, k) מחזירה false היא מחזירה k − 1. התור לא משתנה בין הקריאות (ppp מחזירה אותו למצבו המקורי). לפי סעיף א, בתור יש 3 שיאים (4, 7, 9).

פתרון – טבלת מעקב:

הפעולה מחזירה 3.

בדיקה: על הקוד של השאלה: find(q, 1) = 3, והתור בסוף: [4, 2, 7, 7, 5, 9, 3].

מה נדרש: להסביר מה מחזירה find(q, 1).

תשובה: הפעולה מחזירה את מספר האיברים בתור שכל אחד מהם גדול מכל האיברים שלפניו (מספר ה"שיאים" בתור). התור q לא משתנה.

הסבר: נסמן ב־R את מספר השיאים בתור. לפי סעיף א, ppp(q, k) מחזירה true בדיוק כאשר R ≥ k. find מנסה את k = 1, 2, 3, … לפי הסדר, ועוצרת ב־k הראשון שעבורו R < k, כלומר ב־k = R + 1, ואז מחזירה k − 1 = R. הרקורסיה תמיד נעצרת, כי R ≤ n (מספר האיברים), ולכן לכל המאוחר בקריאה עם k = n + 1 מתקבל false.

בדיקה: 1, 2, 3, 4, 5 ⇒ 5 ; 9, 1, 2, 3 ⇒ 1 ; 3, 3, 3 ⇒ 1 ; 2, 1, 5, 4, 8, 8, 6 ⇒ 3.

מה נדרש: סיבוכיות זמן הריצה של find(q, 1), עם נימוק.

תשובה: O(n²) במקרה הגרוע (n – מספר האיברים בתור).

נימוק: כל קריאה ל־find מבצעת קריאה אחת ל־ppp, שעולה O(n) (סעיף א(3)), ועוד מספר קבוע של פעולות. k מתחיל ב־1 וגדל ב־1 בכל קריאה עד R + 1, כאשר R מספר השיאים – כלומר יש R + 1 קריאות. במקרה הגרוע – כשהתור עולה ממש (כל איבר הוא שיא, R = n) – יש n + 1 קריאות, וכל אחת O(n) ⇒ (n + 1)·O(n) = O(n²).
(במקרה הטוב – כשהאיבר שבראש התור הוא הגדול ביותר, R = 1 – יש שתי קריאות בלבד ⇒ O(n).)

מה נדרש: לדמות את המשחק מהמשבצת הראשונה: steps איסופים, או פחות אם השחקן יוצא מהשרשרת.

רעיון: שני מצביעים מתקדמים יחד – pv על הנקודות ו־pj על אורך הקפיצה של אותה משבצת. בכל צעד: מוסיפים לסכום את pv.getValue(), סופרים איסוף, שומרים את אורך הקפיצה jump ומקדמים את שני המצביעים jump חוליות. אם תוך כדי הקפיצה pv נהיה null – השחקן יצא מהשרשרת, והלולאה החיצונית נעצרת בגלל התנאי pv != null. (מכיוון שהשרשרות באורך שווה, pj נהיה null בדיוק כש־pv נהיה null.) הפעולה רק קוראת מהשרשרות.

פתרון:

public static int collect(Node<Integer> vals, Node<Integer> jumps, int steps) {
    int sum = 0;
    int count = 0;                              // כמה ערכים כבר נאספו
    Node<Integer> pv = vals;
    Node<Integer> pj = jumps;                   // הקפיצה באותו מיקום כמו pv
    while (count < steps && pv != null) {
        sum = sum + pv.getValue();
        count++;
        int jump = pj.getValue();
        for (int i = 0; i < jump && pv != null; i++) {   // מתקדמים jump חוליות בשתי השרשרות
            pv = pv.getNext();
            pj = pj.getNext();
        }
    }
    return sum;
}

בדיקה: על השרשרות מהדוגמה עם steps = 10:

התוצאות: steps = 1 ← 4, steps = 3 ← 10, steps = 10 ← 12 – כמו בדוגמאות. השרשרות לא השתנו.

טעות נפוצה: לקרוא את אורך הקפיצה אחרי שמתחילים להזיז את pj, או לקדם רק את pv – אז pj כבר לא מצביע על אותה משבצת, וכל הקפיצות הבאות שגויות. טעות נוספת: לשכוח לבדוק pv != null בתוך הקפיצה ולקבל חריגה כשקופצים אל מעבר לסוף.

מה נדרש: לבדוק אם יש משבצת התחלה שממנה steps איסופים נותנים בדיוק target.

רעיון: הפעולה collect מסעיף א מתחילה מהחוליות שמועברות אליה – ואפשר להעביר לה חוליות מאמצע השרשרות; היא מתייחסת אליהן כאל "המשבצת הראשונה". לכן עוברים עם שני מצביעים במקביל, pv על vals ו־pj על jumps (תמיד באותו מיקום), ולכל מיקום קוראים collect(pv, pj, steps). אם התוצאה שווה ל־target – מחזירים true מיד. אם עברנו על כל המיקומים – false. הקפיצות תמיד קדימה, ולכן החוליות שלפני משבצת ההתחלה לא משפיעות על המשחק ממנה.

פתרון: (משתמשים בפעולה collect / Collect מסעיף א)

public static boolean reach(Node<Integer> vals, Node<Integer> jumps, int steps, int target) {
    Node<Integer> pv = vals;
    Node<Integer> pj = jumps;                   // אותו מיקום בשתי השרשרות
    while (pv != null) {
        if (collect(pv, pj, steps) == target)   // משחק שמתחיל מהמיקום הנוכחי
            return true;
        pv = pv.getNext();
        pj = pj.getNext();
    }
    return false;
}

בדיקה: על השרשרות מהדוגמה עם steps = 2, ערכי collect לכל משבצת התחלה:

לכן target = 11 ← true (התחלה 4), ו־target = 9 ← false (אין 9 בטבלה), כמו בדוגמאות. נבדקו גם steps = 3, target = 13 ← true, steps = 1, target = 2 ← true (המשבצת האחרונה), ושרשרות של חוליה אחת.

טעות נפוצה: לקדם רק את pv ולהעביר ל־collect את jumps מההתחלה – אז אורכי הקפיצה לא שייכים למשבצות הנכונות.

מה נדרש: לבדוק שבכל צומת שאינו עלה, הערך שווה לסכום הערכים של כל הצאצאים שלו.

רעיון (רקורסיה):

פתרון:

public static boolean isSumTree(BinNode<Integer> tree) {
    if (!tree.hasLeft() && !tree.hasRight())    // עלה – אין לו צאצאים, ואין מה לבדוק
        return true;
    int desc = sumTree(tree.getLeft()) + sumTree(tree.getRight());   // סכום כל הצאצאים
    if (tree.getValue() != desc)
        return false;
    if (tree.hasLeft() && !isSumTree(tree.getLeft()))
        return false;
    if (tree.hasRight() && !isSumTree(tree.getRight()))
        return false;
    return true;
}

יעילות (לא נדרש): בכל צומת שאינו עלה מופעלת sumTree על שני תתי־העצים שלו, וזמנה ליניארי בגודלם. בעץ "שרשרת" של n צמתים זה n + (n − 1) + ... + 1 ⇒ O(n²) במקרה הגרוע.

בדיקה:
העץ בדוגמה הראשונה:

כל הבדיקות עברו ⇒ true.
העץ בדוגמה השנייה: בשורש 11 + 14 = 25 – תקין; ממשיכים לבן השמאלי 5: 2 + 4 = 6 ≠ 5 ⇒ false (בלי לבדוק את תת־העץ הימני).

התוצאות שבדוגמאות מתקבלות, וגם: צומת יחיד 9 ← true; העץ 0 עם הבנים 3 ו־ ‎-3 ← true; שרשרת שמאלית של שלושה צמתים עם הערכים 12, 6, 6 (מהשורש למטה) ← true, והשרשרת 6, 6, 6 ← false (סכום הצאצאים של השורש הוא 12).

טעות נפוצה: להשוות את ערך הצומת רק לסכום הבנים שלו (getValue של השמאלי + getValue של הימני) במקום לסכום כל הצאצאים. בדוגמה הראשונה זה ייתן בשורש 10 + 4 = 14 ≠ 28, ולכן false – תשובה שגויה.

מה נדרש: מסלול מ־ vₛ אל vₜ עם מספר קשתות מינימלי, או רשימה ריקה אם אין מסלול.

רעיון: ב־BFS מ־ vₛ כל קודקוד v מתגלה לראשונה דרך מסלול קצר ביותר (במספר קשתות). אם נשמור לכל קודקוד את ההורה π[v] – הקודקוד שממנו התגלה – המסלול vₛ → … → π[v] → v הוא מסלול קצר ביותר. לכן מריצים BFS (אפשר לעצור כש־ vₜ יוצא מהתור), ואז משחזרים את המסלול מ־ vₜ אחורה.

פתרון:

ShortestRoute(G, vₛ, vₜ):
    לכל קודקוד u ב־V:   visited[u] ← false ;  π[u] ← NIL
    visited[vₛ] ← true
    Q ← תור ריק ;  Q.insert(vₛ)
    כל עוד Q אינו ריק וגם visited[vₜ] = false:
        u ← Q.remove()
        לכל שכן v של u:
            אם visited[v] = false:
                visited[v] ← true ;  π[v] ← u
                Q.insert(v)
    אם visited[vₜ] = false:   החזר רשימה ריקה          // אין מסלול
    path ← רשימה ריקה ;  x ← vₜ
    כל עוד x ≠ NIL:
        הוסף את x לתחילת path
        x ← π[x]
    החזר את path

(העצירה ברגע ש־ vₜ מתגלה היא רק חיסכון; גם בלי העצירה התוצאה זהה.)

זמן ריצה: האתחול O(|V|); כל קודקוד נכנס לתור פעם אחת וכל רשימת שכנים נסרקת פעם אחת ⇒ O(|V| + |E|); שחזור המסלול – לכל היותר |V| צעדים. סך הכול O(|V| + |E|).

בדיקה – על הגרף שבדוגמה מ־2 אל 9 (שכנים בסדר עולה; בסוגריים – ההורה). אחרי צעד 2 הקודקוד 9 כבר התגלה, והלולאה נעצרת:

שחזור: 9 ← π[9] = 4 ← π[4] = 2 ⇒ המסלול 2, 4, 9 – כמו בדוגמה. עבור 0 ו־9: ה־BFS מ־0 מגלה רק את {0, 5, 11, 3, 7}, ולכן מוחזרת רשימה ריקה.

טעות נפוצה: להשתמש ב־DFS – הוא מוצא מסלול, אבל לא בהכרח מסלול עם מספר קשתות מינימלי (למשל DFS מ־2 שעובר על השכנים בסדר יורד מוצא 2, 6, 10, 9 – 3 קשתות).

מה נדרש: לחלק את הגרף לרכיבי קשירות, לספור בכל רכיב את הקשתות, ולהחזיר את הרכיב עם הכי הרבה קשתות.

רעיון: BFS מקודקוד s מגלה בדיוק את רכיב הקשירות של s. כל קשת של הגרף נמצאת כולה בתוך רכיב אחד (שני קצותיה באותו רכיב), ובסכום הדרגות של קודקודי הרכיב כל קשת נספרת פעמיים – פעם מכל קצה. לכן מספר הקשתות ברכיב = (סכום הדרגות של קודקודיו) / 2. את הדרגה מקבלים בזמן שעוברים על רשימת השכנים של הקודקוד ב־BFS.

פתרון:

MostEdgesComponent(G):
    לכל קודקוד u ב־V:   visited[u] ← false
    best ← ריק ;  maxEdges ← −1
    לכל קודקוד s מ־ v₀ עד vₙ₋₁:
        אם visited[s] = false:               // s פותח רכיב קשירות חדש
            comp ← רשימה ובה s ;  degSum ← 0
            visited[s] ← true ;  Q ← תור ריק ;  Q.insert(s)
            כל עוד Q אינו ריק:
                u ← Q.remove()
                לכל שכן v של u:
                    degSum ← degSum + 1          // סופרים את הקשת (u, v) מצד u
                    אם visited[v] = false:
                        visited[v] ← true ;  הוסף את v ל־comp ;  Q.insert(v)
            edges ← degSum / 2
            אם edges > maxEdges:
                maxEdges ← edges ;  best ← comp
    החזר את best

זמן ריצה: הלולאה החיצונית n פעמים; בכל הסריקות יחד כל קודקוד נכנס לתור פעם אחת וכל רשימת שכנים נסרקת פעם אחת (visited אינו מאופס) ⇒ O(|V| + |E|).

בדיקה – על הגרף שבדוגמה:

מוחזר הרכיב {2, 4, 6, 9, 10} – כמו בדוגמה. שימו לב שלרכיב {0, 3, 5, 7, 11} יש אותו מספר קודקודים (5), אבל רק 4 קשתות.

טעות נפוצה: לבחור את הרכיב עם הכי הרבה קודקודים, או לסכם דרגות בלי לחלק ב־2 (אז כל קשת נספרת פעמיים – ההשוואה בין הרכיבים עדיין נכונה, אבל המספר המדווח שגוי).

מה נדרש: למצוא את כל הקודקודים x שיש מסלול x ⇝ vⱼ , בלי לעבור על כל המסלולים.

רעיון: יש מסלול מ־ x אל vⱼ בגרף G אם ורק אם יש מסלול מ־ vⱼ אל x בגרף ההפוך Gᵀ (אותו מסלול, בכיוון ההפוך). ברשימות הסמיכויות של G רשומות רק הקשתות היוצאות, ולכן קודם בונים את Gᵀ (רשימות של הקשתות הנכנסות), ואז סריקה לרוחב מ־ vⱼ ב־ Gᵀ מגלה בדיוק את הקודקודים המבוקשים.

פתרון:

Prerequisites(G, vⱼ):
    // שלב 1: בניית הגרף ההפוך – כל קשת u → v הופכת ל־ v → u
    לכל קודקוד u:  radj[u] ← רשימה ריקה
    לכל קודקוד u ב־V:
        לכל v ברשימת הסמיכויות של u:
            הוסף את u ל־radj[v]
    // שלב 2: סריקה לרוחב מ־vⱼ בגרף ההפוך
    לכל קודקוד u:  visited[u] ← false
    visited[vⱼ] ← true ;  Q ← תור ריק ;  Q.insert(vⱼ)
    R ← רשימה ריקה
    כל עוד Q אינו ריק:
        u ← Q.remove()
        לכל w ב־radj[u]:
            אם visited[w] = false:
                visited[w] ← true ;  הוסף את w ל־R ;  Q.insert(w)
    החזר את R

זמן ריצה: בניית הגרף ההפוך – מעבר אחד על כל הרשימות, O(|V| + |E|). ב־BFS כל קודקוד נכנס לתור פעם אחת לכל היותר וכל רשימה נסרקת פעם אחת – O(|V| + |E|). סך הכול O(|V| + |E|).

בדיקה – על הגרף שבדוגמה עם vⱼ = 6 (ב־ radj[6] נמצאים 2 , 3 , 8 – הקודקודים שיש מהם קשת אל 6):

התוצאה {0, 2, 3, 8} – כמו בדוגמה.

טעות נפוצה: להריץ BFS מ־ vⱼ בגרף המקורי – כך מוצאים את המשימות שתלויות ב־ vⱼ (שבאות אחריה) ולא את אלה שקודמות לה. גם הרצת סריקה מכל קודקוד בנפרד ("האם מגיעים ממנו ל־ vⱼ ?") נכונה אבל לא יעילה: O(|V|·(|V| + |E|)).

מה נדרש: מסלול ארוך ביותר (במספר קשתות) בגרף מכוון ללא מעגלים.

רעיון: בגרף כללי זו בעיה קשה, אבל בגרף ללא מעגלים אפשר לעבור על הקודקודים בסדר טופולוגי: כשמגיעים לקודקוד u , כל הקודקודים שיש מהם קשת אל u כבר טופלו, ולכן L[u] – אורך השרשרת הארוכה ביותר שמסתיימת ב־ u – כבר סופי. אז מעדכנים את השכנים: L[v] = max(L[v], L[u] + 1). זה בדיוק אלגוריתם המסלולים בגמ"ל, עם "מקסימום" במקום "מינימום" (או: מסלול קל ביותר כשמשקל כל קשת הוא −1).

פתרון:

LongestChain(G):
    // שלב 1: מיון טופולוגי לפי דרגות כניסה
    לכל קודקוד u:  in[u] ← 0
    לכל קודקוד u, לכל v ברשימת הסמיכויות של u:  in[v] ← in[v] + 1
    Q ← תור ובו כל הקודקודים שדרגת הכניסה שלהם 0 ;  order ← רשימה ריקה
    כל עוד Q אינו ריק:
        u ← Q.remove() ;  הוסף את u לסוף order
        לכל v ברשימת הסמיכויות של u:
            in[v] ← in[v] − 1
            אם in[v] = 0:  Q.insert(v)
    // שלב 2: L[v] = אורך השרשרת הארוכה ביותר שמסתיימת ב־v
    לכל קודקוד v:  L[v] ← 0 ;  P[v] ← null
    לכל קודקוד u לפי הסדר ב־order:
        לכל v ברשימת הסמיכויות של u:
            אם L[u] + 1 > L[v]:
                L[v] ← L[u] + 1 ;  P[v] ← u
    // שלב 3: שחזור השרשרת
    end ← הקודקוד שבו L מקסימלי
    chain ← רשימה ריקה ;  x ← end
    כל עוד x ≠ null:
        הוסף את x לתחילת chain ;  x ← P[x]
    החזר את chain

זמן ריצה: חישוב דרגות הכניסה ומיון טופולוגי O(|V| + |E|); מעבר שני – כל קשת נבדקת פעם אחת O(|V| + |E|); מציאת המקסימום והשחזור O(|V|). סך הכול O(|V| + |E|).

בדיקה – על הגרף שבדוגמה. סדר טופולוגי (דרגות כניסה, תור): 0, 3, 8, 2, 9, 5, 6, 1, 7, 4 . הערכים של L אחרי עיבוד כל קודקוד:

L מקסימלי הוא L[4] = 5 . שחזור: 4 ← 7 ← 1 ← 5 ← 2 ← 0 , כלומר 0 , 2 , 5 , 1 , 7 , 4 – כמו בדוגמה. זו השרשרת הארוכה היחידה בגרף.

טעות נפוצה: לחשב L בסדר מספרי של הקודקודים (0 , 1 , 2 , …) במקום בסדר טופולוגי – אז, למשל, קודקוד 1 מעובד לפני 5 , עוד לפני ש־ L[1] קיבל את ערכו הסופי, והתשובה שגויה.

מה נדרש: דוגמה לגרף לא מכוון עם 6 קודקודים, שיש בו שני קודקודים לא שכנים שהוספת קשת ביניהם נותנת עץ.

רעיון: מתחילים מעץ על 6 קודקודים (5 קשתות) ומוחקים ממנו קשת אחת. החזרת הקשת שנמחקה מחזירה את העץ.

פתרון: (הקשת המקווקוות באדום אינה בגרף – היא הקשת שמוסיפים.)

קשתות הגרף: 1–2 , 2–3 , 4–5 , 4–6 (4 קשתות).
בין 3 ל־4 אין קשת. אם מוסיפים את הקשת 3–4 מתקבלות 5 קשתות: 1–2 , 2–3 , 3–4 , 4–5 , 4–6. הגרף קשיר ואין בו מעגל – זה עץ. לכן זהו "גרף־עץ־שבור".

בדיקה: הגרף מקיים את ההגדרה, ואחרי הוספת 3–4 מתקבל עץ.

מה נדרש: לקבוע אם מספר הקשתות ב"גרף־עץ־שבור" עם n קודקודים ידוע, ואם כן – מהו.

רעיון: בכל עץ עם n קודקודים יש בדיוק n−1 קשתות.

פתרון: כן. לפי ההגדרה יש שני קודקודים u, v שאין ביניהם קשת, וכשמוסיפים את הקשת u–v מתקבל עץ על אותם n קודקודים. לעץ הזה יש n−1 קשתות, והוא מכיל את כל קשתות הגרף ועוד קשת אחת. לכן בגרף יש n−1 − 1 = n−2 קשתות.

בדיקה: בדוגמה מסעיף א: 6 קודקודים ו־4 קשתות. גם בבדיקה הממוחשבת – לכל אחד מ־1,209 הגרפים־עצים־שבורים עם 2 עד 6 קודקודים היו בדיוק n−2 קשתות.

מה נדרש: לקבוע את מספר רכיבי הקשירות של "גרף־עץ־שבור".

רעיון: הגרף הוא עץ שהורדנו ממנו קשת אחת. בעץ כל קשת היא "גשר": אין בין קצותיה מסלול אחר.

פתרון: כן. נסמן ב־T את העץ שמתקבל אחרי הוספת הקשת u–v. הגרף שלנו הוא T בלי הקשת u–v.

לכן בגרף בדיוק 2 רכיבי קשירות (הרכיב של u והרכיב של v). כל אחד מהם הוא עץ.

בדיקה: בדוגמה מסעיף א הרכיבים הם {1, 2, 3} ו־{4, 5, 6}. גם בבדיקה הממוחשבת – לכל הגרפים־עצים־שבורים היו בדיוק 2 רכיבים.

מה נדרש: אלגוריתם יעיל שבודק אם גרף (ברשימת סמיכויות) הוא "גרף־עץ־שבור".

רעיון: נוכיח ש־G הוא גרף־עץ־שבור אם ורק אם יש בו n−2 קשתות ו־2 רכיבי קשירות.

אז מספיק לספור קשתות ורכיבי קשירות.

פתרון – האלגוריתם (הגרף פשוט – בלי קשתות מקבילות ולולאות; כל קשת מופיעה פעמיים ברשימת הסמיכויות – פעם אצל כל אחד מקצותיה):

בדיקה: האלגוריתם מחזיר תמיד אותה תשובה כמו ההגדרה עצמה ("יש זוג קודקודים לא שכנים שהוספת קשת ביניהם נותנת עץ"). על הדוגמה מסעיף א מתקבל "אמת".

טעות נפוצה: לבדוק רק "יש n−2 קשתות". גרף עם n−2 קשתות יכול להיות בעל יותר משני רכיבים – למשל משולש ועוד שני קודקודים מבודדים (5 קודקודים, 3 קשתות, 3 רכיבים) – ואז אין קשת אחת שהוספתה נותנת עץ. חייבים לבדוק גם את מספר הרכיבים.

מה נדרש: סיבוכיות האלגוריתם מסעיף ג(1), עם נימוק.

רעיון: נחשב כל שלב בנפרד, ונשים לב שהעצירה המוקדמת מגבילה את מספר הקשתות שנבדקות.

פתרון:

סך הכול: O(n). (בלי העצירה המוקדמת הסיבוכיות היא O(n + E), שהיא עדיין לינארית בגודל הקלט – רשימת הסמיכויות.)

מה נדרש: לקבוע לכל אחת מהשפות אם היא רגולרית, ולנמק.

רעיון: לאוטומט סופי יש זיכרון חסום. נבדוק כמה מידע צריך לזכור בזמן הקריאה.

פתרון:
L₁ – לא רגולרית. צריך לזכור את ההפרש n_a − n_b, שיכול להיות גדול כרצוננו (למשל אחרי aⁱ ההפרש הוא i). נימוק מדויק: אילו היה אוטומט סופי עם p מצבים, בין המילים a⁰, a¹, …, aᵖ היו שתיים, aⁱ ו־aʲ עם i ≠ j, שמסתיימות באותו מצב. אז האוטומט היה מקבל או דוחה יחד את aⁱbⁱ (בשפה) ואת aʲbⁱ (לא בשפה) – סתירה.

L₂ – רגולרית. מספיק לזכור את ההפרש n_a − n_b מודולו 3 – שלוש אפשרויות. כל a מוסיפה 1 וכל b מחסירה 1 (מודולו 3). המצב Dᵣ אומר שההפרש עד כה נותן שארית r:

L₃ – רגולרית. סופרים את האורך עד 12 בלבד: מצבים C₀…C₁₂, כל אות מקדמת Cᵢ → Cᵢ₊₁, ומ־C₁₂ לולאה על a,b. המצב המקבל: C₁₂.

בדיקה: שני האוטומטים מקבלים בדיוק את המילים של L₂ ושל L₃.

מה נדרש: לקבוע אם L₁ ∩ L₃ – המילים עם מספר שווה של a ושל b שאורכן לפחות 12 – רגולרית.

רעיון: L₃ מוציאה מ־L₁ רק מספר סופי של מילים (הקצרות), וזה לא "מציל" את L₁.

פתרון: לא רגולרית. מתקיים L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃). החלק L₁ ∩ L̅₃ מכיל רק מילים שאורכן קטן מ־12, ולכן הוא סופי ורגולרי. נניח בשלילה ש־L₁ ∩ L₃ רגולרית. אז L₁ היא איחוד של שתי שפות רגולריות ולכן רגולרית – סתירה לסעיף (1).
במילים: גם במילים הארוכות (למשל aⁱbⁱ עם i ≥ 6) האוטומט צריך לזכור את ההפרש n_a − n_b, שאינו חסום.

בדיקה: aⁿbⁿ שייכת ל־L₁ ∩ L₃ לכל n ≥ 6 (השפה אינסופית), וכל זוג תחיליות aⁱ, aʲ (i ≠ j) מובחן על ידי הסיומת bⁱ.

טעות נפוצה: לענות "רגולרית, כי L₃ רגולרית וחיתוך של רגולריות הוא רגולרי". כלל הסגירות דורש ששתי השפות יהיו רגולריות, ו־L₁ אינה רגולרית.

מה נדרש: לקבוע אם L₁ ∩ L̅₃ רגולרית (L̅₃ – המשלים של L₃ ביחס ל־{a,b}*).

רעיון: המשלים של "אורך לפחות 12" הוא "אורך לכל היותר 11" – יש מספר סופי של מילים כאלה.

פתרון: רגולרית. L̅₃ = { w | |w| ≤ 11 }, ויש בה מספר סופי של מילים (2¹² − 1). לכן גם L₁ ∩ L̅₃ ⊆ L̅₃ סופית (אלה המילים באורך זוגי עד 10 עם מספר שווה של a ושל b, כולל המילה הריקה ε), וכל שפה סופית היא רגולרית.

בדיקה: ספירת המילים: יש 351 מילים ב־L₁ ∩ L̅₃ (1 + 2 + 6 + 20 + 70 + 252 לפי האורכים 0, 2, …, 10).

מה נדרש: לקבוע אם השפה של המילים שבהן ההפרש n_a − n_b מתחלק ב־3 אבל אינו 0 – רגולרית.

רעיון: ננסה "לבנות" את L₁ מ־L₂ ומהשפה הנתונה בעזרת פעולות שהשפות הרגולריות סגורות להן. אם זה מצליח – השפה הנתונה לא יכולה להיות רגולרית.

פתרון: לא רגולרית. אם n_a(w) = n_b(w) אז ההפרש הוא 0, שמתחלק ב־3, ולכן L₁ ⊆ L₂. מכאן ש־L₂ מתחלקת לשני חלקים זרים: L₁ (הפרש 0) ו־M = L₂ ∩ L̅₁ (הפרש 3, −3, 6, …). לכן L₁ = L₂ ∩ M̅ (המילים של L₂ שאינן ב־M).
נניח בשלילה ש־M רגולרית. אז גם M̅ רגולרית (משלים), ו־L₂ ∩ M̅ רגולרית (חיתוך של רגולריות). כלומר L₁ רגולרית – סתירה לסעיף (1).
במילים: כדי להבחין בין הפרש 0 להפרש 3 או 6 האוטומט היה צריך לזכור את ההפרש עצמו, ולא רק את השארית שלו.

בדיקה: L₁ ⊆ L₂, והשוויון L₁ = L₂ ∩ M̅ מתקיים. דוגמאות למילים ב־M: aaa, bbb, aaaab.

טעות נפוצה: לענות "רגולרית, כי L₂ רגולרית". L̅₁ אינה רגולרית, ולכן כלל הסגירות לחיתוך לא חל כאן.

מה נדרש: לקבוע לכל מילה אם היא ב־L.

רעיון: בודקים קודם את הצורה (בדיוק # אחד, ומשני צדדיו חלק לא ריק של a/b), ואז את התנאי: u מסתיימת ב־a או |v| מתחלק ב־3.

פתרון:

בדיקה: חמש המילים מול הגדרת L – התוצאות זהות לטבלה.

טעות נפוצה: לקבל את a# כי "u מסתיימת ב־a". התנאי על u או על v נבדק רק אחרי שהצורה תקינה, ו־v חייבת להיות לא ריקה.

מה נדרש: להשלים את התוויות החסרות ולסמן מצבים מקבלים, בלי לשנות שום דבר אחר.

רעיון: נבין מה כל מצב "זוכר":

פתרון: האוטומט המושלם (התוויות שהוספנו באדום, המצבים המקבלים מסומנים בעיגול כפול אדום):

טבלת המעברים המלאה (מעבר שאינו בטבלה – האוטומט נתקע ודוחה; בהדגשה – התוויות שהוספנו):

מעקב לדוגמה:

בדיקה: האוטומט המושלם מקבל בדיוק את המילים של L. בנוסף נבדקו בחיפוש ממצה כל ההשלמות האפשריות של התוויות החסרות (כל קבוצה לא ריקה של סימנים לכל מעבר, וכל בחירה של מצבים מקבלים): ההשלמה שלמעלה היא היחידה שמקבלת את L.

מה נדרש: המילים המשותפות ל־ L₄ ול־ L₅.

פתרון: L₄ = {xy, yyx}, L₅ = {ε, x, xy}. רק xy מופיעה בשתיהן: L₄ ∩ L₅ = {xy}.

מה נדרש: כל השרשורים uv כאשר u, v ∈ L₆ (אפשר גם u = v).

פתרון:

L₆ • L₆ = {yy, yyx, yxy, yxyx}.

טעות נפוצה: לשכוח את השרשור של מילה עם עצמה (yy, yxyx), או לחשוב ש־ yyx ו־ yxy הן אותה מילה.

מה נדרש: שרשור של Σ* עם {ε}.

פתרון: המילה היחידה ב־ L₂ היא ε, ו־ w • ε = w לכל w. לכן כל מילה של Σ* מתקבלת כמו שהיא, ולא מתקבל שום דבר אחר: L₁ • L₂ = Σ*.

מה נדרש: ההיפוך של השפה הריקה.

פתרון: Lᴿ מכילה את ההיפוך של כל מילה של L. ב־ L₃ = Ø אין מילים, ולכן אין מה להפוך: L₃ᴿ = Ø.

טעות נפוצה: לכתוב {ε}. ההיפוך של {ε} הוא {ε}, אבל ההיפוך של Ø הוא Ø.

מה נדרש: כל השרשורים uv כאשר u ∈ L₅ ו־ v ∈ L₆.

פתרון:

כל שש המילים שונות: L₅ • L₆ = {y, yx, xy, xyx, xyy, xyyx}.

מה נדרש: אוטומט מחסנית דטרמיניסטי ל־ L = {aⁿ bᵐ cᵐ aⁿ | n ≥ 0, m ≥ 1}.

רעיון: המבנה "מקונן": ה־ b מתאימים ל־ c שמיד אחריהם, וה־ a הראשונים מתאימים ל־ a שבסוף. מחסנית מתאימה בדיוק לזה – מה שנדחף אחרון נשלף ראשון:

כדי לדעת בלי מעברי ε מתי נגמר כל בלוק, מסמנים את הסימן הראשון של כל בלוק:

התנאי m ≥ 1 חשוב: בזכותו ה־ b מפריד בין שני בלוקי ה־ a, והאוטומט יודע בכל רגע אם הוא בבלוק הראשון או האחרון.

פתרון:

בכל צירוף (מצב, אות, ראש מחסנית) יש לכל היותר מעבר אחד ואין מעברי ε – האוטומט דטרמיניסטי. כל צירוף שאינו בטבלה = דחייה (למשל c בלי b לפניו, b אחרי c, או אות נוספת ב־ q5).

בדיקה – מעקב על aabbccaa (n = 2, m = 2):

הקלט נגמר ב־ q5 ⇒ מתקבלת. מעקב על bbcc (n = 0): q0 → q2 (Z⊥) → q2 (BZ⊥) → q3 (Z⊥) → q5 (⊥) ⇒ מתקבלת. לעומת זאת abcaa נתקעת ב־ q5 (a מיותר), ו־ abcca נתקעת ב־ q4 (c במקום a) – נדחות.
האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}. מתקבלות למשל: bc, bbcc, abca, aabcaa, abbcca.

טעות נפוצה: לסמן את q0 כמקבל – ε אינה בשפה, כי m ≥ 1.

מה נדרש: מעקב מלא על המילה ba.

רעיון: מריצים את המעברים אחד אחד. מעברי המכונה: q₀: a/a,R → q₁ ; b/b,R → q₂ . q₁: a/a,R → q₁ ; b/b,R → q₁ ; Δ/Δ,L → q₃ . q₂: a/a,R → q₂ ; b/b,R → q₂ ; Δ/Δ,L → q₄ . q₃: a/a,L → q₅ ; b/a,L → q₅ . q₄: a/b,L → q₅ ; b/b,L → q₅ . q₅: a/a,L → q₅ ; b/b,L → q₅ ; ⊣/⊣,R → q₆ . q₆ – מצב מקבל.
בטבלה: תא 0 הוא הסמן ⊣ , הראש הקורא מסומן ב־[ ].

פתרון:

שלב 0→1: ב־q₀ קוראים b ⇐ משאירים, זזים ימינה ל־q₂ (המכונה "זוכרת" שהאות הראשונה היא b). שלב 1→2: q₂ ממשיך ימינה. שלב 2→3: ב־Δ חוזרים צעד שמאלה – אל האות האחרונה – ב־q₄. שלב 3→4: q₄ כותב b במקום ה־a האחרון. שלבים 4→6: q₅ חוזר שמאלה עד ⊣ , ואז ימינה ל־q₆. המילה מתקבלת, ועל הסרט bb.

בדיקה: המעקב עובר בדיוק בשלבים האלה.

מה נדרש: מעקב מלא על abb.

פתרון:

הסבר: האות הראשונה היא a ⇐ q₁ (0→1). q₁ עובר ימינה עד Δ (1→3), חוזר אל האות האחרונה ב־q₃ (3→4), וכותב שם a במקום b (4→5). q₅ חוזר שמאלה עד ⊣ (5→7), ו־q₆ (7→8). המילה מתקבלת, ועל הסרט aba.

בדיקה: המעקב עובר באותם 9 שלבים, ובסוף: מתקבלת, תוכן הסרט aba.

מה נדרש: תוכן הסרט בסוף הריצה על babaa.

רעיון: כפי שראינו בסעיפים (1) ו־(2), המכונה זוכרת את האות הראשונה (q₁ – a , q₂ – b), עוברת לסוף המילה וכותבת את האות הזו במקום האות האחרונה.

פתרון: האות הראשונה של babaa היא b , והאחרונה (תא 5) היא a – היא מוחלפת ב־b. הסרט בסוף:

כלומר על הסרט babab, והמכונה עוצרת ב־q₆ (מקבלת).

בדיקה: עבור babaa: מתקבלת, תוכן הסרט babab.

מה נדרש: לספור את המילים באורך 4 שהמכונה משאירה כמו שהן.

רעיון: המכונה משנה רק את האות האחרונה – כותבת בה את האות הראשונה. המילה לא משתנה בדיוק כשהאות האחרונה כבר שווה לראשונה.

פתרון: במילה x₁x₂x₃x₄ יש לבחור את x₁ (2 אפשרויות), את x₂ ו־x₃ (2 אפשרויות לכל אחת), ו־x₄ חייבת להיות שווה ל־x₁ (אפשרות אחת). סך הכול 2 · 2 · 2 = 8 מילים: aaaa , aaba , abaa , abba , baab , babb , bbab , bbbb.

בדיקה: מבין 16 המילים באורך 4 בדיוק 8 נשארות ללא שינוי, אלה שברשימה.

מה נדרש: תיאור קצר של פעולת המכונה.

פתרון: המכונה כותבת במקום האות האחרונה של המילה את האות הראשונה שלה: ב־q₀ היא קוראת את האות הראשונה ו"זוכרת" אותה במצב (q₁ – a , q₂ – b), עוברת ימינה עד סוף המילה, חוזרת צעד אחד אל האות האחרונה (q₃ / q₄) וכותבת שם את האות שזכרה. אחר כך q₅ חוזר שמאלה עד הסמן ⊣ , והמכונה עוצרת ב־q₆ מעל התא הראשון. במילה בת אות אחת האות הראשונה היא גם האחרונה, והמילה לא משתנה. המכונה מקבלת כל מילה לא ריקה; במילה הריקה q₀ קורא Δ , אין מעבר – והמילה נדחית.

בדיקה: ba → bb , abb → aba , babaa → babab , a → a , המילה הריקה – נדחית. פלט המכונה הוא בדיוק הפונקציה הזו לכל מילה.

מה נדרש – לסרטט את הקשרים בין חמש המחלקות: מי יורש ממי ומי מכיל את מי.

רעיון – חתול, כלב וארנב הם חיות מחמד ("is-a") ⇒ הם יורשים מ־Pet. לכל חיית מחמד בפנסיון יש שהייה ("has-a") ⇒ הכלה: ב־Pet יש תכונה stay מטיפוס Stay. התכונות chip ו־stay שמופיעות גם בפירוט של Cat, Dog ו־Rabbit עוברות אליהן בירושה מ־Pet – לכן לא מגדירים אותן שוב, ולא מחברים את Stay ישירות לכל אחת מהן.

פתרון

   Stay ───────────◆ Pet
                     △
          ┌──────────┼──────────┐
          │          │          │
         Cat        Dog       Rabbit

בדיקה – Cat "היא" Pet ✓, Dog "היא" Pet ✓, Rabbit "היא" Pet ✓; ל־Pet "יש" Stay ✓; שהייה אינה חיית מחמד, לכן אין ירושה בין Stay ל־Pet.

טעות נפוצה: לסמן את Stay כמחלקת־על של Pet ("חיה היא שהייה") – הקשר ביניהן הוא הכלה, לא ירושה.

מה נדרש – לכתוב את כותרות חמש המחלקות ואת התכונות שלהן (בלי פעולות).

רעיון – התכונות פרטיות (private). במחלקות היורשות כותבים רק את התכונה החדשה – chip ו־stay כבר נמצאות ב־Pet ועוברות בירושה. ב־Java הירושה נכתבת extends Pet, וב־C# : Pet. התכונה stay היא מטיפוס המחלקה Stay (הכלה); indoor בוליאנית – boolean ב־Java ו־bool ב־C#.

פתרון

public class Stay {
    private String owner;
    private int nights;
    private int meals;
}

public class Pet {
    private String chip;
    private Stay stay;
}

public class Cat extends Pet {
    private boolean indoor;
}

public class Dog extends Pet {
    private int weight;
}

public class Rabbit extends Pet {
    private int age;
}

בדיקה – שני הקבצים עוברים הידור (Java ו־C#).

טעות נפוצה: להגדיר שוב chip ו־stay במחלקות היורשות – כך נוצרות תכונות כפולות שמסתירות את אלה של Pet.

מה נדרש – לממש את הפעולה הבונה של Pet שמקבלת את נתוני השהייה ואת מספר השבב.

רעיון – Pet מכילה שהייה, ולכן הפעולה הבונה יוצרת עצם Stay חדש מהנתונים שקיבלה (owner, nights, meals) בעזרת הפעולה הבונה הנתונה של Stay, ושומרת אותו בתכונה stay. את chip שומרים ישירות.

פתרון

(בתוך המחלקה Pet):

    public Pet(String owner, int nights, int meals, String chip) {
        this.stay = new Stay(owner, nights, meals);
        this.chip = chip;
    }

בדיקה – new Pet("Gal", 4, 8, "P-100") יוצר שהייה של 4 לילות ו־8 ארוחות, והעלות שלה 456 (ראו סעיף ג).

טעות נפוצה: לשמור את owner, nights ו־meals בתכונות של Pet – אין לה תכונות כאלה; הנתונים שייכים לעצם ה־Stay.

מה נדרש – לממש את הפעולה הבונה של Dog.

רעיון – התכונות chip ו־stay פרטיות ב־Pet, ולכן Dog מעבירה את ארבעת הנתונים הראשונים לפעולה הבונה של מחלקת־העל (super(...) ב־Java – בשורה הראשונה, : base(...) ב־C#), ואחר כך מאתחלת את התכונה שלה – weight. (בקוד המלא שלפניכם מופיעה גם הפעולה cost מסעיף ג2.)

פתרון

public class Dog extends Pet {
    private int weight;

    public Dog(String owner, int nights, int meals, String chip, int weight) {
        super(owner, nights, meals, chip);
        this.weight = weight;
    }

    public double cost() {
        if (this.weight > 20)
            return super.cost() + 15 * getStay().getNights();
        return super.cost();
    }
}

בדיקה – new Dog("Gal", 4, 8, "P-102", 30) תקין בשתי השפות; השהייה שנוצרת בתוכו היא של 4 לילות ו־8 ארוחות.

מה נדרש – לכתוב ב־Pet פעולה שמחזירה את העלות הבסיסית: 90 ש"ח ללילה ועוד 12 ש"ח לארוחה מיוחדת.

רעיון – מספר הלילות ומספר הארוחות שמורים בעצם השהייה, והתכונות שלו פרטיות – לכן ניגשים אליהן דרך פעולות ה־get של Stay. ב־C# מגדירים את הפעולה virtual כדי שאפשר יהיה לדרוס אותה במחלקות היורשות.

פתרון

(בתוך Pet):

    public double cost() {
        return 90 * this.stay.getNights() + 12 * this.stay.getMeals();
    }

בדיקה – 4 לילות ו־8 ארוחות: 90·4 + 12·8 = 360 + 96 = 456. התוצאה: 456 בשתי השפות.

טעות נפוצה: לגשת ל־stay.nights ישירות – התכונה פרטית במחלקה Stay, ולכן זו שגיאת הידור.

מה נדרש – להוסיף cost רק במחלקות שבהן העלות שונה מהעלות הבסיסית, בלי לבדוק את סוג העצם.

רעיון – פולימורפיזם: Dog ו־Rabbit דורסות את cost, והפעולה המתאימה נבחרת בזמן ריצה לפי סוג העצם. חתול משלם לפי העלות הבסיסית – לכן לא כותבים cost ב־Cat. בכלב התוספת תלויה בתכונה של הכלב עצמו (weight), ולכן הבדיקה weight > 20 נמצאת בתוך הפעולה הדורסת של Dog – זו לא בדיקת סוג, אלא בדיקת ערך של תכונה. את מספר הלילות מקבלים דרך getStay().getNights() (stay פרטית ב־Pet). בשני המקרים משתמשים בחישוב הבסיסי דרך super.cost() (ב־C# base.Cost()). ב־C# הפעולות מסומנות override.

פתרון

public class Dog extends Pet {
    private int weight;

    public Dog(String owner, int nights, int meals, String chip, int weight) {
        super(owner, nights, meals, chip);
        this.weight = weight;
    }

    public double cost() {
        if (this.weight > 20)
            return super.cost() + 15 * getStay().getNights();
        return super.cost();
    }
}

public class Rabbit extends Pet {
    private int age;

    public Rabbit(String owner, int nights, int meals, String chip, int age) {
        super(owner, nights, meals, chip);
        this.age = age;
    }

    public double cost() {
        return super.cost() * 0.75;
    }
}

בדיקה – מערך Pet[] (4 לילות, 8 ארוחות): Pet 456, Cat 456, Dog של 30 ק"ג 516 (=456+15·4), Dog של 20 ק"ג בדיוק 456 (אין תוספת – "יותר מ־20"), Rabbit 342 (=456·0.75). כלב של 21 ק"ג ל־2 לילות ו־3 ארוחות: 180+36+30 = 246; ארנב ללילה אחד וארוחה אחת: 102·0.75 = 76.5. התוצאות זהות ב־Java וב־C#.

טעות נפוצה: לכתוב weight >= 20 – כלב של 20 ק"ג בדיוק לא משלם תוספת. וגם: לכתוב cost מיותרת ב־Cat, או לבדוק את סוג העצם (instanceof / is) ב־Pet במקום לדרוס.

מה נדרש – לממש את הפעולות הבונות של Box ושל GiftBox ואת toString של GiftBox כך שיתקבל הפלט הנתון.

רעיון – מסיקים מהפלט, שורה אחר שורה. made היא תכונת מחלקה (static) פרטית של Box: יש עותק אחד שלה לכל העצמים, ו־GiftBox לא יכולה לגשת אליה. לכן רק פעולה בונה של Box יכולה לשנות אותה.

פתרון

public class Box {
    private static int made = 0;
    protected int size;

    public Box() {
        this.size = 1;          // לא משנה את made
    }

    public Box(int size) {
        made++;                 // הפעולה הבונה היחידה שמגדילה את made
        this.size = size;
    }

    public String toString() {return "made=" + made + ", size=" + size;}
}

public class GiftBox extends Box {
    private String color;

    public GiftBox(String color) {
        super(color.length());  // הגודל הוא אורך שם הצבע, ו-made גדל
        this.color = color;
    }

    public GiftBox(int size, String color) {
        super();                // לא מגדילה את made
        this.size = size;       // size מוגדרת protected ולכן נגישה במחלקה היורשת
        this.color = color;
    }

    public String toString() {
        return super.toString() + ", color=" + this.color;
    }
}

בדיקה – קטע הקוד מהשאלה (Java ו־C#) מדפיס בדיוק:

made=0, size=1
made=1, size=8
made=2, size=3, color=red
made=2, size=6, color=green
made=3, size=6, color=yellow

טעות נפוצה: לממש את GiftBox(int size, String color) עם super(size). כך made גדל, ובשורה //4 מודפס made=3, size=6, color=green (ובשורה //5 made=4). גם מימוש של Box() כ־this(1) שגוי: הוא מגדיל את made, ובשורה //1 מתקבל made=1.

מה נדרש – לקבוע לכל אחד מששת התרשימים אם הוא מתאים לקוד שרץ באופן תקין.

רעיון – השמה X ref = new Y(); עוברת הידור רק אם Y היא X או תת־מחלקה של X (ישירה או עקיפה). מכל שורה ב־main מקבלים דרישה:

פתרון

בדיקה – בנינו את המחלקות K, L, M, N לפי כל אחד מהתרשימים והידרנו את Tester (ב־Java וב־C#). בתרשימים 1, 3, 5 הייתה שגיאת הידור, ובתרשימים 2, 4, 6 התוכנית רצה תקין.

מה נדרש – לבדוק אילו מהתרשימים שנמצאו אפשריים ב־ב(1) (2, 4, 6) נשארים אפשריים אחרי השורות החדשות.

רעיון – k3 מפנה לעצם מטיפוס M. ההמרה (L)k3 עוברת הידור בכל שלושת התרשימים, כי L היא תת־מחלקה של K (טיפוס ההפניה). אבל בזמן ריצה היא מצליחה רק אם העצם (M) הוא באמת L, כלומר רק אם M יורשת (ישירות או בעקיפין) מ־L. אחרת נזרקת חריגה: ClassCastException ב־Java, InvalidCastException ב־C#.

פתרון – כן, התשובה משתנה: רק תרשים 2 נשאר אפשרי.

בדיקה – עם השורות הנוספות (Java ו־C#): בתרשימים 4 ו־6 מתקבלת שגיאת ריצה (ClassCastException / InvalidCastException), ובתרשים 2 התוכנית רצה תקין.

טעות נפוצה: לחשוב שאם ההמרה עוברת הידור היא תקינה. המהדר בודק רק שההמרה אפשרית לפי טיפוס ההפניה (K ⇐ L). את סוג העצם בפועל בודקים רק בזמן ריצה.

מה נדרש – לכתוב את התכונות ואת כותרות הפעולות של Device שבלעדיהן Lamp לא תעבור הידור.

רעיון – עוברים על Lamp שורה אחר שורה ושואלים מה היא צריכה מ־Device:

פתרון (גופי הפעולות כאן ריקים או מחזירים ערך זמני, רק כדי שהקוד יעבור הידור; בבחינה מספיקות הכותרות)

public class Device {
    protected boolean broken;
    protected static double rate;

    public Device() { }
    public Device(String code, int power) { }
    public String info() { return ""; }
    public boolean isOld(int year) { return false; }
}

אפשר להוסיף ל־Device תכונות פרטיות נוספות (למשל code ו־power, לשמירת הפרמטרים של הפעולה הבונה), אבל הן אינן נדרשות כדי ש־Lamp תהיה תקינה.

בדיקה – Device יחד עם Lamp ללא שינוי תקינות ב־Java וב־C#. בדקנו גם שכל רכיב נחוץ: בלי Device() או בלי Device(String, int), עם private boolean broken, עם rate שאינה static או שהיא private, בלי info() (וב־C# בלי virtual), בלי isOld(int) או כש־isOld(int) מחזירה int – בכל אחד מהמקרים התקבלה שגיאת הידור.

טעות נפוצה: לחשוב ש־this.isOld(2020) היא קריאה רקורסיבית ל־isOld() של Lamp. ל־isOld של Lamp אין פרמטרים, ולכן נדרשת ב־Device פעולה נוספת בשם isOld שמקבלת מספר ומחזירה boolean (העמסה).

מה נדרש – לצייר את ארבעת העצמים ולכתוב את הפלט של הפעולות הבונות.

רעיון

פתרון

תרשים העצמים:

הפלט:

Robot Alfa
Robot Beta
Cleaner
Robot Gama
Cleaner 60
Robot Delta
Cleaner

בדיקה – הפלט ב־Java וב־C# הוא בדיוק הפלט שלמעלה.

טעות נפוצה: לחשוב שאצל Gama האנרגיה היא 100 – הפעולה הבונה של Robot מציבה 100, אבל מיד אחריה הפעולה הבונה של Cleaner מציבה 60.

מה נדרש – לכל פקודה: האם היא עוברת הידור, האם היא רצה בלי שגיאה, ומה היא מדפיסה.

רעיון – שלושה כללים:

פתרון

בדיקה – כל פקודה לבדה בפעולה הראשית תקינה ב־Java וב־C#. הפקודות הלא תקינות נכשלו בהידור בשתי השפות, פרט לפקודה שנכשלה בזמן ריצה (ב־Java: ClassCastException, ב־C#: InvalidCastException). הפלט של הפקודות התקינות זהה בשתי השפות.