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

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

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

לכן מוציאים את העבודות מ־q אחת־אחת ומכניסים אותן לתור עזר temp. כשנתקלים לראשונה בעבודה שמספר העמודים שלה גדול מזה של job, מכניסים קודם את job ומסמנים inserted = true. אם התור הסתיים ו־job עדיין לא הוכנסה (בכל העבודות יש פחות עמודים או אותו מספר, או שהתור ריק), מכניסים את job בסוף. לבסוף מעבירים את temp בחזרה ל־q.

פתרון: הקוד המלא – בלשונית Java/C#. הפעולה נמצאת בתוך המחלקה PrintQueue וניגשת ישירות לתכונה q. הגישה לתכונות של PrintJob נעשית בפעולות get.

יעילות: O(n), כאשר n הוא מספר העבודות בתור. כל עבודה עוברת לתור העזר וחוזרת ממנו פעם אחת.

בדיקה: בתור 2, 5, 5, 12, 20, 40 (מספרי העמודים) מכניסים את 6075 עם 5 עמודים. העבודות 2041 (2), 3310 (5) ו־1187 (5) עוברות לתור העזר. העבודה 4402 (12) היא הראשונה עם יותר מ־5 עמודים, ולכן לפניה מוכנסת 6075. מתקבל:
2041/2, 3310/5, 1187/5, 6075/5, 4402/12, 2390/20, 5120/40, בדיוק כמו באיור. נבדקו גם הכנסה לתור ריק, הכנסת עבודה של 100 עמודים (נכנסת לסוף) והכנסת עבודה של עמוד אחד (נכנסת לראש התור).

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

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

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

לפי השאלה שתי העבודות נמצאות בתור, ולכן job1 ו־job2 אינם null.

פתרון: הקוד המלא – בלשונית Java/C#.

יעילות: O(n). מעבר אחד להוצאת שתי העבודות ועוד מעבר אחד בתוך addJob.

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

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

מה נדרש: לממש פעולה במחלקה Truck שמשאירה בשרשרת את k − 1 החבילות הראשונות שמשקלן w, מוחקת את כל שאר החבילות שמשקלן w, ומחזירה כמה חבילות נמחקו.

רעיון: עוברים על השרשרת פעם אחת מתחילתה ומחזיקים שתי הפניות: pos – החוליה הנבדקת, ו־prev – החוליה שלפניה בשרשרת (בהתחלה null). בנוסף סופרים ב־seen כמה חבילות במשקל w כבר פגשנו.

אחרי מחיקה prev לא משתנה, כי החוליה שלפני החוליה הבאה היא עדיין prev. אם יש פחות מ־k חבילות במשקל w, התנאי seen ≥ k לא מתקיים אף פעם, השרשרת לא משתנה ומוחזר 0.

פתרון:

public int removeFrom(int w, int k)
{
    int seen = 0;    // כמה חבילות במשקל w כבר נמצאו
    int count = 0;   // כמה חבילות נמחקו
    Node<Parcel> prev = null;   // החוליה שלפני pos (null – pos היא החוליה הראשונה)
    Node<Parcel> pos = lst;
    while (pos != null)
    {
        boolean match = pos.getValue().getWeight() == w;
        if (match)
            seen++;
        if (match && seen >= k)
        {
            // מחיקת pos: מחברים את החוליה שלפניה לחוליה שאחריה
            if (prev == null)
                lst = pos.getNext();
            else
                prev.setNext(pos.getNext());
            count++;
        }
        else
        {
            prev = pos;   // pos נשארת בשרשרת
        }
        pos = pos.getNext();
    }
    return count;
}

בדיקה: על השרשרת מהדוגמה (P1:12, P2:7, P3:12, P4:5, P5:12, P6:7, P7:12):

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

טעות נפוצה: לעדכן prev = pos גם אחרי מחיקה – אז prev מצביע על חוליה שכבר אינה בשרשרת, ואם שתי חבילות שצריך למחוק צמודות זו לזו, השנייה לא תימחק באמת (prev.setNext משנה חוליה שכבר נמחקה). טעות נוספת: לשכוח את המקרה שבו נמחקת החוליה הראשונה (k = 1) ויש לשנות את lst.

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

רעיון: עוברים על השרשרת עם pos. לכל חוליה pos שמשקלה w מזמנים את הפעולה מסעיף א: removeFrom(w, 2). עם k = 2 הפעולה משאירה את החבילה הראשונה במשקל w ומוחקת את כל האחרות. החבילה הראשונה במשקל w היא בדיוק pos: כל החבילות שלפני pos כבר טופלו, וכל החבילות שאחריהן ששקלו כמוהן כבר נמחקו – ולכן אף חבילה לפני pos אינה במשקל w. לכן pos עצמה לא נמחקת, ואפשר להמשיך ממנה ל־pos.getNext().
הפעולה removeFrom מחזירה כמה חבילות נמחקו, ולכן מוסיפים לסכום k·w. השרשרת לעולם לא מתרוקנת (pos נשארת), כך שההנחה של סעיף א מתקיימת.

פתרון (Java) – הפעולה removeFrom מסעיף א נמצאת באותה מחלקה:

// משתמשת בפעולה removeFrom מסעיף א
public int removeRepeats()
{
    int sum = 0;
    Node<Parcel> pos = lst;
    while (pos != null)
    {
        int w = pos.getValue().getWeight();
        // pos היא החבילה הראשונה במשקל w – מוחקים את כל שאר החבילות במשקל w
        int k = removeFrom(w, 2);
        sum = sum + k * w;
        pos = pos.getNext();
    }
    return sum;
}

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

הפעולה מחזירה 43 והשרשרת P1:12, P2:7, P4:5 – כמו בדוגמה. מקרים נוספים: שרשרת 4, 4, 4 (מוחזר 8, נשארת חבילה אחת) ושרשרת 1, 2, 3 (מוחזר 0, ללא שינוי).

יעילות: הלולאה עוברת על לכל היותר L חוליות, ובכל צעד removeFrom עוברת על כל השרשרת – O(L) ⇒ O(L·L) = O(L²).

מה נדרש: עץ בינרי עם 10 צמתים, לכל היותר 4 רמות, לפחות שני צמתים שיש להם בן יחיד – ובכל מסלול מהשורש לעלה לכל היותר צומת אחד כזה.

רעיון: את הצמתים בעלי הבן היחיד צריך לפזר כך שאף שניים מהם לא יהיו על אותו מסלול – כלומר אף אחד מהם לא יהיה צאצא של אחר. נוח לבנות קודם עץ מלא בן 3 רמות (7 צמתים), ואז להוסיף בן יחיד לכמה מן העלים שלו: כל עלה כזה הופך לצומת בעל בן יחיד, והם נמצאים במסלולים שונים.

הבחנה: בכל עץ בינרי מספר הצמתים הוא 2·(מספר הצמתים בעלי שני בנים) + (מספר הצמתים בעלי בן יחיד) + 1. עם 10 צמתים, מספר הצמתים בעלי בן יחיד חייב להיות אי־זוגי, ולכן "לפחות שניים" פירושו לפחות שלושה.

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

בכתיב מילולי: לשורש 1 – הבנים 2 ו־3. ל־2 – הבנים 4 ו־5. ל־3 – הבנים 6 ו־7. ל־4 – רק בן שמאלי 8. ל־5 – רק בן ימני 9. ל־6 – רק בן שמאלי 10. הצמתים 7, 8, 9, 10 הם עלים.

בדיקה – כל המסלולים מהשורש לעלים:

10 צמתים, 4 רמות, 3 צמתים בעלי בן יחיד, ובכל מסלול לכל היותר אחד ⇒ "עץ 1־דליל". (ובדוגמה: isSparseK(עץ, 1) = true, isSparseK(עץ, 0) = false. בסריקה של כל צורות העצים בנות 4 רמות לכל היותר נמצאו 48 עצים שמקיימים את הדרישות.)
יש עוד תשובות נכונות רבות.

טעות נפוצה: לתת לצומת 8 (שאביו 4 הוא כבר בעל בן יחיד) בן אחד נוסף – אז 8 הופך לבעל בן יחיד ובמסלול יש 2 צמתים כאלה (וגם העץ יעבור את 4 הרמות).

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

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

פתרון:

public static boolean isSparseK(BinNode<Integer> root, int k)
{
    // לצומת יש בן יחיד אם יש לו בן שמאלי בלבד או בן ימני בלבד
    if (root.hasLeft() != root.hasRight())
    {
        if (k == 0)
            return false;
        k = k - 1;   // הצומת "צורך" צומת אחד מתוך K
    }
    if (root.hasLeft() && !isSparseK(root.getLeft(), k))
        return false;
    if (root.hasRight() && !isSparseK(root.getRight(), k))
        return false;
    return true;
}

בדיקה: על העץ מהדוגמה בשאלה: isSparseK(root, 1) = false (במסלול המודגש שני צמתים בעלי בן יחיד), isSparseK(root, 2) = true, isSparseK(root, 3) = true, isSparseK(root, 0) = false. על העץ מסעיף א: K = 1 ⇒ true, K = 0 ⇒ false. עץ שהוא עלה יחיד עם K = 0 ⇒ true.

יעילות: כל צומת נבדק לכל היותר פעם אחת, ובכל צומת מספר קבוע של פעולות ⇒ O(n), כאשר n מספר הצמתים בעץ.

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

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

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

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים:

קרוסקל מוסיף את שלוש הקשתות במשקל 2 (הן לא סוגרות מעגל), ודוחה את a–d (3) שסוגרת את המעגל. העפ"מ: a–b , b–c , c–d במשקל 6, והוא יחיד.
בעץ, המסלול מ־a ל־d הוא a–b–c–d במשקל 6, אבל בגרף יש מסלול קל יותר: הקשת a–d במשקל 3.

בדיקה: העפ"מ יחיד, במשקל 6, בלי a–d, ודייקסטרה מ־a נותן מרחק 3 ל־d.

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

מה נדרש: להראות שבגרף מכוון ללא מעגלים יש לכל היותר n(n−1)/2 קשתות.

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

פתרון: הטענה נכונה. הגרף מכוון וללא מעגלים, ולכן יש לו מיון טופולוגי v₁, v₂, …, vₙ: לכל קשת vᵢ→vⱼ מתקיים i < j.
כל קשת נקבעת על ידי זוג מקומות (i, j) עם i < j, ולכל זוג כזה יש לכל היותר קשת אחת (vᵢ→vⱼ; הקשת ההפוכה אסורה, ואין קשתות כפולות). מספר הזוגות i < j הוא (n−1) + (n−2) + … + 1 = n(n−1)/2. לכן יש לכל היותר n(n−1)/2 קשתות.
(החסם מושג: הגרף שבו יש קשת vᵢ→vⱼ לכל i < j הוא ללא מעגלים ויש בו בדיוק n(n−1)/2 קשתות.)

בדיקה: למשל עם 2 עד 4 קודקודים: מספר הקשתות המרבי בגרף מכוון ללא מעגלים הוא 1, 3, 6 – כלומר n(n−1)/2.

מה נדרש: לבדוק אם "כל הקודקודים ישיגים מ־s" מבטיח "כל קודקוד ישיג מכל קודקוד".

רעיון: DFS מ־s מגלה בדיוק את הקודקודים שיש אליהם מסלול מ־s. הוא לא אומר כלום על מסלולים חזרה אל s.

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים:
s→a , s→b , s→c

DFS מ־s מגלה את a, b ו־c – כל הקודקודים. אבל מ־a לא יוצאת אף קשת, ולכן אין מסלול מ־a ל־s (או לכל קודקוד אחר). הגרף אינו קשיר היטב.

בדיקה: כל הקודקודים ישיגים מ־s, ומ־a לא ישיג אף קודקוד מלבדו.

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

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

רעיון: רכיב עם קודקוד אחד בלבד הוא קודקוד מבודד. אם אין כאלה – כל רכיב "גדול".

פתרון: הטענה נכונה. יהי x קודקוד ברכיב כלשהו. ל־x יש שכן y, והקשת x–y מחברת אותם – לכן y באותו רכיב. כלומר בכל רכיב יש לפחות 2 קודקודים.
אם יש k רכיבים, הם זרים זה לזה ולכן מכילים יחד לפחות 2k קודקודים: 2k ≤ n, ומכאן k ≤ n/2.
(החסם מושג למשל בגרף של n/2 קשתות נפרדות: a–b , c–d.)

מה נדרש: לבדוק אם "מקור יחיד" מבטיח מיון טופולוגי יחיד.

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

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים:
s→a , s→b , a→c , b→c

אין בגרף מעגל, ודרגות הכניסה: s – 0, a – 1, b – 1, c – 2. רק ל־s דרגת כניסה 0.
אחרי s, גם a וגם b אפשר לשים בתור הבא (אין קשת ביניהם). מתקבלים שני מיונים טופולוגיים: s, a, b, c ו־s, b, a, c.

בדיקה: מבין 24 הסידורים של 4 הקודקודים, בדיוק שני סידורים מקיימים את כל הקשתות: sabc ו־sbac.

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

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

רעיון: סריקת DFS מ־s עוברת רק על רכיב הקשירות של s. היעדר קשת אחורה מוכיח שאין מעגל ברכיב הזה בלבד.

פתרון: הטענה לא נכונה. דוגמה נגדית עם 5 קודקודים s, a, b, c, d וקשתות:
s–a , b–c , c–d , d–b

DFS מ־s: s → a, חוזרים. נבדקה רק הקשת s–a (קשת עץ). לא נמצאה קשת אחורה. אבל b–c–d–b הוא מעגל בגרף – ברכיב שה־DFS מ־s לא הגיע אליו.
(אילו היינו מריצים DFS על כל הגרף – מכל קודקוד שעוד לא התגלה – היינו מוצאים קשת אחורה ברכיב b, c, d.)

בדיקה: כל עצי ה־DFS מ־s מכילים את כל הקשתות של הרכיב של s (אין קשת אחורה), ובגרף יש מעגל.

מה נדרש: לקבוע לכל אחד מהעצים (i), (ii), (iii) אם הוא יכול להיות עץ DFS מ־z של אותו גרף G.

רעיון: בסריקת DFS על גרף לא מכוון כל קשת שאינה בעץ מחברת קודקוד עם אב קדמון שלו (קשת אחורה); אין קשתות בין ענפים שונים של העץ. מזה נסיק אילו קשתות בוודאי ב־G, אילו אולי, ואילו בוודאי לא.

פתרון:
קשתות העץ הנתון (ולכן ב־G): s–x , x–y , y–z , s–w.
קשתות נוספות אפשריות (בין קודקוד לאב קדמון שלו): s–y , s–z , x–z.
קשתות שאינן יכולות להיות ב־G: w–x , w–y , w–z (w בענף אחר של s).
בפרט, השכן היחיד של w הוא s.

סריקה שנותנת את (i), בגרף G שבו הקשתות הן העץ הנתון ועוד s–z: מתחילים ב־z ← בוחרים את השכן s ← מ־s עוברים ל־w (השכן היחיד שלו, s, כבר התגלה) ← חוזרים ל־s ועוברים ל־x ← מ־x עוברים ל־y (השכנים של y: x, z – כבר התגלו) ← חוזרים עד z; גם y כבר התגלה. התקבלו בדיוק הקשתות z–s , s–w , s–x , x–y.

בדיקה: בדיוק 8 גרפים על 5 הקודקודים נותנים את העץ הנתון מ־s (העץ ועוד תת־קבוצה של {s–y , s–z , x–z}). עץ (i) מתקבל מ־z בדיוק ב־4 הגרפים שיש בהם s–z, ועצים (ii) ו־(iii) לא מתקבלים באף גרף.

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

רעיון: מוצאים את כל הקודקודים שאפשר להגיע אליהם מ־ 1 ; אם לא הגענו לכולם – הגרף אינו קשיר, וממשיכים מקודקוד שלא הגענו אליו.

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

בדיקה: BFS מכל קודקוד שלא סומן מוצא את שני הרכיבים [1, 2, 3, 4] ו־ [5, 6, 7].

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

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

פתרון: ברכיב הראשון: 1 → קבוצה X , השכנים 2 , 4 → קבוצה Y , ו־ 3 (שכן של 2 ושל 4) → קבוצה X . ברכיב השני: 5 → X , 6 → Y , 7 → X .
X = {1, 3, 5, 7} , Y = {2, 4, 6}. הקשתות: 1–2 , 2–3 , 3–4 , 4–1 , 5–6 , 6–7 – כולן בין X ל־ Y . לכן הגרף דו־צדדי.

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

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

רעיון: בגרף לא מכוון עם n קודקודים ו־ c רכיבי קשירות, אם יש יותר מ־ n − c קשתות – בהכרח יש מעגל. אבל כאן אפשר פשוט להצביע על המעגל.

פתרון: המסלול 1 – 2 – 3 – 4 – 1 חוזר לקודקוד שממנו התחיל ועובר ב־4 קשתות שונות – זה מעגל. (בדיקה בספירה: n = 7 , c = 2 , ויש 6 קשתות > 7 − 2 = 5.)

בדיקה: 6 > 5 ⇒ יש מעגל.

מה נדרש: לבדוק את שני התנאים של עץ – קשיר וללא מעגלים.

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

פתרון: הגרף אינו קשיר (יש 2 רכיבי קשירות), וגם יש בו מעגל 1 – 2 – 3 – 4 – 1 . לכן הגרף אינו עץ. (הרכיב {5, 6, 7} לבדו הוא עץ, אבל הגרף כולו לא.)

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

טעות נפוצה: לענות "כן" רק משום שמספר הקשתות הוא n − 1 = 6 , בלי לבדוק קשירות.

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

רעיון: לכל תחנה רושמים את התחנות שהחצים היוצאים ממנה מגיעים אליהן.

פתרון (שכנים לפי סדר אלפביתי):

בדיקה: בסרטוט 14 חצים, ובטבלה 2 + 2 + 2 + 2 + 1 + 2 + 2 + 1 = 14 איברים. שימו לב ש־ Q → R ו־ T → Q הם שני חצים שונים, וש־ V → P הוא החץ הנכנס היחיד ל־ P .

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

רעיון: ביטול "כל הקווים הנכנסים והיוצאים" של U פירושו למחוק את הרשימה של U (U → T , U → W) וגם את U מכל רשימה שהוא מופיע בה (Q → U). בנוסף נמחקות S → R ו־ R → T .

פתרון:

בדיקה: נמחקו 5 קשתות ונשארו 14 − 5 = 9 , ובטבלה 2 + 1 + 1 + 1 + 1 + 0 + 2 + 1 = 9 .

טעות נפוצה: למחוק את הרשימה של U ולשכוח את הקשת הנכנסת Q → U ברשימה של Q.

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

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

פתרון:

BFS(G, s):
    לכל קודקוד v:  d[v] ← ∞ ;  π[v] ← null
    d[s] ← 0 ;  Q ← תור ריק ;  Q.insert(s)
    כל עוד Q אינו ריק:
        u ← Q.remove()
        לכל v ברשימת הסמיכויות של u:
            אם d[v] = ∞:
                d[v] ← d[u] + 1 ;  π[v] ← u ;  Q.insert(v)

אם בסוף d[y] = ∞ – אי אפשר להגיע ל־ y . אחרת המסלול מתקבל מ־ y , π[y] , π[π[y]] , … עד s (בסדר הפוך). זמן הריצה O(|V| + |E|).

בדיקה: DFS או מיון טופולוגי היו מוצאים מסלול כלשהו, אבל לא בהכרח עם מספר נסיעות מינימלי; דייקסטרה מתאים לגרף ממושקל ומיותר כאן (כל המשקלים 1). לכן BFS הוא הבחירה הנכונה והיעילה.

מה נדרש: להריץ BFS מ־ P על הגרף שלאחר השינויים ולשחזר את המסלול ל־ T .

רעיון: בכל צעד מוציאים תחנה מהתור, ולכל שכן שעוד לא התגלה קובעים d = d[u] + 1 , π = u ומכניסים לתור.

פתרון – מעקב:

הערכים הסופיים:

שחזור המסלול מ־ T : π[T] = W , π[W] = V , π[V] = S , π[S] = P . לכן המסלול הוא P → S → V → W → T , ובו d[T] = 4 נסיעות.

בדיקה: לאחר השינויים יש רק שני מסלולים פשוטים מ־ P ל־ T : P → S → V → W → T (4 נסיעות) ו־ P → Q → R → V → W → T (5 נסיעות), והמסלול שנמצא הוא הקצר. לפני השינויים היה אפשר להגיע ב־3 נסיעות (למשל P → Q → R → T).

מה נדרש: הדרגות של הקודקודים ב־ Bₙ .

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

פתרון: L מחובר לכל אחד מ־ n קודקודי העמוד ובנוסף ל־ R (קשת הגשר) ⇐ דרגה n + 1 ; וכך גם R . כל קודקוד עמוד מחובר רק ל־ L ול־ R ⇐ דרגה 2 .

בדיקה: ב־ B₄ שבאיור: ל־ L שכנים 1, 2, 3, 4, R (דרגה 5), ולקודקוד 3 שכנים L, R . כך גם לכל 2 ≤ n ≤ 8 .

מה נדרש: מספר הקשתות מכל סוג ובסך הכול.

פתרון: לכל אחד מ־ n קודקודי העמוד יש קשת אחת ל־ L ⇐ n קשתות שמאליות, וקשת אחת ל־ R ⇐ n קשתות ימניות. עם קשת הגשר: 2n + 1 קשתות.

בדיקה: לפי משפט סכום הדרגות: 2·(n + 1) + n·2 = 4n + 2 = 2·(2n + 1) ⇐ 2n + 1 קשתות. ב־ B₄ : 4 + 4 + 1 = 9 קשתות.

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

רעיון: גרף הוא דו־צדדי אם ורק אם אין בו מעגל באורך אי־זוגי.

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

בדיקה: צביעה בשני צבעים נכשלת לכל 2 ≤ n ≤ 8 .

מה נדרש: מספר העצים הפורשים המינימליים.

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

פתרון:

(גם בקרוסקל: קודם נבחרות כל n הקשתות במשקל 1 ; אחר כך הקשת הראשונה במשקל 2 מחברת את R , וכל קשת נוספת תיצור מעגל. סדר שונה בין הקשתות במשקל 2 נותן עפ"מ אחר.)

בדיקה: לכל 2 ≤ n ≤ 7 יש בדיוק n עפ"מים במשקל n + 2 .

טעות נפוצה: לענות "עפ"מ אחד" – כל הקשתות הימניות באותו משקל, וכל אחת מהן יכולה להיות הקשת שמחברת את R .

מה נדרש: משקלים שבהם קשת הגשר לבדה אינה מסלול קל ביותר בין L ל־ R .

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

פתרון: אם 2w < g , המסלולים L–i–R (משקל 2w) קלים ממש מקשת הגשר, ולכן כל מסלול קל ביותר עובר בקודקוד עמוד. דוגמה: w = 1 , g = 3 : דרך עמוד 1 + 1 = 2 < 3 .

בדיקה: עם w = 1 , g = 3 התנאי מתקיים, ובאופן כללי התנאי מתקיים בדיוק כאשר 2w < g .

מה נדרש: הערך הגדול ביותר של w כאשר g = 12 .

רעיון: לפי סעיף (1), התנאי הוא שהמסלול דרך קודקוד עמוד (2w) יהיה קל ממש מקשת הגשר (g = 12).

פתרון: צריך 2w < 12 ⇐ w < 6 . אם המשקלים שלמים, הערך הגדול ביותר הוא w = 5 : אז דרך עמוד 5 + 5 = 10 < 12 .
ב־ w = 6 : יש מסלולים קלים במשקל 12 גם דרך עמוד (6 + 6) וגם בקשת הגשר (12). קשת הגשר אינה עוברת בקודקוד עמוד, ולכן לא כל מסלול קל עובר בקודקוד עמוד.
(אם w יכול להיות לא שלם, כל w < 6 מתאים ואין "גדול ביותר"; התשובה המקובלת היא w = 5 למשקלים שלמים, או "w קטן מ־ 6".)

בדיקה: עם g = 12 ו־ w = 1, 2, 3, 4, 5, 5.9, 6, 7 : התנאי מתקיים רק ל־ w = 1, 2, 3, 4, 5, 5.9 .

טעות נפוצה: לענות w = 6 – במצב של שוויון קשת הגשר היא מסלול קל נוסף שאינו עובר בקודקוד עמוד.

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

רעיון: אוטומט סופי זוכר רק כמות חסומה של מידע. בכל השפות מספר ה־c חייב להיות שווה למספר ה־b (m). השאלה היא אם m חסום או לא.

פתרון:

בדיקה: ב־L₃ יש מספר סופי של מילים, הגדול ביותר בהן m = 97 (קטן מ־100); ב־L₂ תמיד m ≤ 49 ו־n לא חסום; ב־L₁ תמיד n ≤ 49 ו־m לא חסום, והרישות bᵐ a (m > 50) נבדלות זו מזו.

טעות נפוצה: לחשוב ש־L₃ אינה רגולרית "כי m אינו חסום במפורש". החסם m < 2n יחד עם n < 50 נותן m < 100.

מה נדרש: לקבוע רגולריות של L₄, L₅, L₆ (L̅ = המשלים של L).

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

פתרון:

בדיקה: L₁ ∩ L₂ ריקה, L₃ ⊆ L₁ , וכל מילה של L₂ אינה ב־L₁.

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

מה נדרש: אוטומט סופי דטרמיניסטי (לא חייב להיות מלא – מעבר שחסר פירושו דחייה) ל־L.

רעיון: המילה מתפרקת באופן יחיד: רצף b (n), רצף c (m), ואחריו w – שאין בה c. כדי לדעת אם n · m זוגי מספיק לזכור את הזוגיות של n ושל m: המכפלה אי־זוגית רק כששניהם אי־זוגיים.

במצבים X ו־Y0 (מכפלה זוגית, w ריקה עד כה – 0 אותיות b) המילה כבר יכולה להסתיים, ולכן הם מקבלים.

פתרון: מצב התחלה: S. מצבים מקבלים: X, Y0, E0, W1.

("–" = אין מעבר, המילה נדחית.)
שימו לב: מ־Y0 ו־Y1 ה־c הבא מחליף את זוגיות m, ולכן Y1 ⇄ Y0 ; מ־X ה־c נשאר ב־X (n זוגי – המכפלה תמיד זוגית).

בדיקה:

(bcc: n·m = 2 זוגי, w ריקה – מתקבלת; bc: n·m = 1 אי־זוגי, w ריקה ואין בה a – נדחית; bcaa: שתי אותיות a – נדחית.)

מה נדרש: מכונת טיורינג שמקבלת ⊢x#y (x, y מעל {0, 1}, באותו אורך) ומשאירה על הסרט $1ᵈ$, כאשר d הוא מספר המקומות שבהם x ו־y שונות.

רעיון:

פתרון:

מעקב – הקלט 10110#11100 (הסרט בכל פעם שהמכונה מתחילה סבב חדש, כלומר נכנסת ל־q3, ובסוף):

בין שני ה־$: 11 ⇒ המרחק 2 ✔ (כמו בדוגמה). ב־0110#0110 התוצאה ⊢XXXX#YYYY$$ – מרחק 0.

בדיקה: לכל הזוגות x, y המכונה עוצרת, על הסרט נשארים בדיוק שני סימני $, וביניהם בדיוק d אחדות. למשל 10110#11100 ⇒ $11$ (148 צעדים), 1#0 ⇒ $1$, 000#111 ⇒ $111$.

טעות נפוצה: לכתוב את ה־1 של המונה בלי $ מפריד בין המילה השנייה למונה – אז אי אפשר להבדיל בין 1 של המילה השנייה ל־1 של המונה. ה־$ הראשון נכתב לפני הסבב הראשון.

מה נדרש: להריץ את המכונה על ⊢1#11 ולכתוב את הסרט בסוף.

קריאת הסרטוט: התווית "x / y, כיוון" על חץ פירושה: קוראים x, כותבים y ומזיזים את הראש לכיוון הנתון. כשרשומות על חץ שתי תוויות – יש שני מעברים. טבלת המעברים של המכונה:

רעיון: בכל "סיבוב" המכונה מסמנת ב־ a את ה־ 1 הבא של המספר השמאלי ומסמנת ב־ b את ה־ 1 הבא של המספר הימני (q0–q4). כשאחד המספרים נגמר היא מוחקת את המספר ה"קצר" ואת #, ומחזירה ל־ 1 את כל הסימנים של המספר ה"ארוך".

פתרון – מעקב (התאים ממוספרים מ־ 0 = ⊢):

התוצאה: המכונה עצרה במצב q10, ועל הסרט: ⊢ Δ Δ 1 1 Δ Δ …

בדיקה: המעקב נבנה צעד אחר צעד לפי טבלת המעברים.

מה נדרש: הסרט הסופי עבור 111#1 (בלי מעקב).

פתרון (לפי הרעיון מסעיף א):

הסרט בסיום: ⊢ 1 1 1 Δ Δ … – שלושה אחדים, max(3, 1) = 3.

בדיקה: עבור 111#1 המכונה עוצרת במצב q10 והסרט הוא ⊢111.

מה נדרש: לתאר את הפונקציה שהמכונה מחשבת עבור קלט 1ˣ#1ʸ, כאשר x, y > 0.

רעיון: בכל סיבוב (q0 → q1 → q2 → q3 → q4 → q0) מסומן 1 אחד של x ב־ a ו־ 1 אחד של y ב־ b – מתאימים זוג. הסיבובים נמשכים עד שאחד המספרים נגמר:

פתרון: המכונה מחשבת את המקסימום max(x, y): בסיום על הסרט יש רצף של max(x, y) אחדים, וכל שאר התאים ריקים (Δ). כש־ x > y הרצף מתחיל בתא 1; כש־ x ≤ y הוא נמצא במקום שבו היה המספר הימני.

בדיקה: לכל הזוגות הקטנים x, y שאינם שניהם 0 מתקבלים max(x, y) אחדים והמכונה עוצרת ב־ q10 (למשל 1#11 → 11, 111#1 → 111).

מה נדרש: לבדוק את שלושת המקרים שבהם לפחות אחד המספרים הוא 0 (מספר אונרי 0 = אין אחדים). התוצאה הנכונה היא max(x, y).

פתרון:

מקרה 1 – x = 0, y > 0: המכונה פועלת נכון.
q0 קורא מיד # ⇒ מוחק אותו וזז שמאלה אל ⊢ (q5 לא מוחק כלום, כי אין a) ⇒ q6 זז ימינה, מדלג על התא הריק ומגיע ל־ 1 ⇒ q7 עובר על האחדים ועוצר ב־ q10. נשארים y אחדים = max(0, y).
דוגמה: קלט ⊢ # 1 1 Δ … ⇒ פלט ⊢ Δ 1 1 Δ …

מקרה 2 – y = 0, x > 0: המכונה פועלת נכון.
q0 מסמן את תא 1 ב־ a, q1 עובר אל #, q2 קורא מיד Δ ⇒ q8 מוחק את #, ו־ q9 הולך שמאלה: משאיר את האחדים, מחזיר את ה־ a ל־ 1 ועוצר ב־ ⊢. נשארים x אחדים = max(x, 0).
דוגמה: קלט ⊢ 1 1 # Δ … ⇒ פלט ⊢ 1 1 Δ …

מקרה 3 – x = 0, y = 0: המכונה פועלת לא נכון.
קלט ⊢ # Δ … : q0 קורא # ⇒ כותב Δ וזז שמאלה; q5 קורא ⊢ ⇒ זז ימינה ל־ q6. עכשיו כל הסרט ריק. q6 זז ימינה על Δ ומחפש b או 1 כדי לעבור ל־ q7 – אבל אין כאלה, ולכן הוא ממשיך ימינה בלי סוף. המכונה לעולם אינה מגיעה למצב העצירה q10 (לולאה אינסופית).
הסיבה: q6 מניח שאחרי התאים הריקים יש לפחות 1 אחד של המספר הימני (או b). כש־ x ≤ y זה נכון רק אם y > 0; כש־ y = 0 אין סימן שיעצור את החיפוש.

בדיקה: x=0,y=2 → ⊢Δ11 (q10); x=2,y=0 → ⊢11 (q10); x=y=0 → המכונה לא עוצרת: היא נשארת ב־ q6 וזזה ימינה בלי סוף.

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

רעיון – תא אחסון, חדר קירור ומכולה הם סוגים של יחידת אחסון ("is-a") ⇒ הם יורשים מ־Unit. לכל יחידת אחסון יש חוזה ("has-a") ⇒ הכלה: ב־Unit יש תכונה lease מטיפוס Lease. התכונות code ו־lease שמופיעות גם בפירוט של Locker, ColdRoom ו־Container הן התכונות שעוברות אליהן בירושה מ־Unit – לכן לא מגדירים אותן שוב, ולא מחברים את Lease ישירות לכל אחת מהן.

פתרון

   Lease ───────────◆ Unit
                       △
          ┌────────────┼─────────────┐
          │            │             │
        Locker      ColdRoom     Container

בדיקה – Locker "היא" Unit ✓, ColdRoom "היא" Unit ✓, Container "היא" Unit ✓; ל־Unit "יש" Lease ✓; חוזה אינו יחידת אחסון, לכן אין ירושה בין Lease ל־Unit.

טעות נפוצה: לסמן הכלה של Lease בכל אחת משלוש המחלקות היורשות – החוזה כבר נמצא ב־Unit ועובר בירושה.

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

רעיון – התכונות פרטיות (private). במחלקות היורשות כותבים רק את התכונה החדשה – code ו־lease כבר נמצאות ב־Unit ועוברות בירושה. ב־Java הירושה נכתבת extends Unit, וב־C# : Unit. התכונה lease היא מטיפוס המחלקה Lease (הכלה).

פתרון

public class Lease {
    private String tenant;
    private int months;
    private int boxes;
}

public class Unit {
    private String code;
    private Lease lease;
}

public class Locker extends Unit {
    private int floor;
}

public class ColdRoom extends Unit {
    private int temp;
}

public class Container extends Unit {
    private boolean roofed;
}

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

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

מה נדרש – לממש את הפעולה הבונה של Unit שמקבלת את נתוני החוזה ואת קוד היחידה.

רעיון – Unit מכילה חוזה, ולכן הפעולה הבונה יוצרת עצם Lease חדש מהנתונים שקיבלה (tenant, months, boxes) בעזרת הפעולה הבונה הנתונה של Lease, ושומרת אותו בתכונה lease. את code שומרים ישירות.

פתרון

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

    public Unit(String tenant, int months, int boxes, String code) {
        this.lease = new Lease(tenant, months, boxes);
        this.code = code;
    }

בדיקה – new Unit("Noa", 3, 10, "U-01") יוצר חוזה של 3 חודשים ו־10 ארגזים, והמחיר שלו 340 (ראו סעיף ג).

טעות נפוצה: לכתוב this.tenant = tenant בתוך Unit – ל־Unit אין תכונות כאלה; הנתונים שייכים לעצם ה־Lease.

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

רעיון – התכונות code ו־lease פרטיות ב־Unit, ולכן ColdRoom לא יכולה לאתחל אותן בעצמה – היא מעבירה את ארבעת הנתונים הראשונים לפעולה הבונה של מחלקת־העל (super(...) ב־Java, : base(...) ב־C#), ואחר כך מאתחלת את התכונה שלה – temp. ב־Java הקריאה ל־super חייבת להיות השורה הראשונה. (בקוד המלא שלפניכם מופיעה גם הפעולה price מסעיף ג2.)

פתרון

public class ColdRoom extends Unit {
    private int temp;

    public ColdRoom(String tenant, int months, int boxes, String code, int temp) {
        super(tenant, months, boxes, code);
        this.temp = temp;
    }

    public double price() {
        return super.price() + 35 * getLease().getMonths();
    }
}

בדיקה – new ColdRoom("Noa", 3, 10, "C-02", 4) תקין בשתי השפות; החוזה שנוצר בתוכו הוא של 3 חודשים ו־10 ארגזים.

מה נדרש – לכתוב ב־Unit פעולה שמחזירה את המחיר לפי התעריף הבסיסי: 100 ש"ח לחודש ועוד 4 ש"ח לארגז.

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

פתרון

(בתוך Unit):

    public double price() {
        return 100 * this.lease.getMonths() + 4 * this.lease.getBoxes();
    }

בדיקה – 3 חודשים ו־10 ארגזים: 100·3 + 4·10 = 300 + 40 = 340. התוצאה: 340 בשתי השפות.

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

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

רעיון – זהו פולימורפיזם: כל מחלקה דורסת את price לפי הכלל שלה, והפעולה המתאימה נבחרת בזמן ריצה לפי סוג העצם שזימן אותה. תא אחסון משלם לפי התעריף הבסיסי – לכן לא כותבים price ב־Locker, והיא יורשת אותה מ־Unit. בחדר קירור ובמכולה משתמשים בחישוב הבסיסי דרך super.price() (ב־C# base.Price()), כדי לא לשכפל את הנוסחה. בחדר הקירור צריך גם את מספר החודשים: התכונה lease פרטית ב־Unit, ולכן מגיעים אליה דרך getLease() (פעולת get שקיימת לפי השאלה), ומשם getMonths(). ב־C# הפעולות היורשות מסומנות override (והפעולה ב־Unit virtual).

פתרון

public class ColdRoom extends Unit {
    private int temp;

    public ColdRoom(String tenant, int months, int boxes, String code, int temp) {
        super(tenant, months, boxes, code);
        this.temp = temp;
    }

    public double price() {
        return super.price() + 35 * getLease().getMonths();
    }
}

public class Container extends Unit {
    private boolean roofed;

    public Container(String tenant, int months, int boxes, String code, boolean roofed) {
        super(tenant, months, boxes, code);
        this.roofed = roofed;
    }

    public double price() {
        return super.price() * 0.8;
    }
}

בדיקה – מערך Unit[] עם Unit, Locker, ColdRoom ו־Container (3 חודשים, 10 ארגזים): 340, 340, 445 (=340+35·3), 272 (=340·0.8). חדר קירור לחודש אחד בלי ארגזים: 100+35 = 135; מכולה ל־6 חודשים ו־25 ארגזים: (600+100)·0.8 = 560. כל התוצאות זהות ב־Java וב־C#.

טעות נפוצה: לכתוב בחדר הקירור this.lease.getMonths() – lease פרטית ב־Unit ואינה נגישה במחלקה היורשת. וגם: ב־C# לשכוח virtual/override, לכתוב price מיותרת ב־Locker, או לבדוק את סוג העצם במקום לדרוס.

מה נדרש – להשלים ב־TT וב־UU פעולות בונות בלבד, כך שהרצת Test תיצור בדיוק את העצמים שבתרשים, ולציין לכל עצם איזו פעולה בונה יצרה אותו.

רעיון – לפי סוגי הפרמטרים: ל־TT יש קריאות בלי פרמטר, עם int ועם TT – שלוש פעולות בונות. ל־UU יש קריאות עם (TT, TT), עם TT, עם int ועם (int, TT) – ארבע פעולות בונות. את הערכים קובעים לפי התרשים:

פתרון

public class TT
{
    private int p;

    public TT()
    {
        this.p = 10;
    }

    public TT(int p)
    {
        this.p = p;
    }

    public TT(TT other)
    {
        this.p = other.p;
    }
}

public class UU extends TT
{
    private TT left;
    private TT right;

    public UU(TT left, TT right)
    {
        super();
        this.left = left;
        this.right = right;
    }

    public UU(TT t)
    {
        super(t);
        this.left = t;
        this.right = null;
    }

    public UU(int p)
    {
        super(p);
        this.left = null;
        this.right = new TT();
    }

    public UU(int p, TT t)
    {
        super(p);
        this.left = t;
        this.right = new TT(t);
    }
}

הפעולה הבונה של כל עצם:

בדיקה – ערכי השדות וההפניות אחרי Test: t1…t3 = 10, 4, 4 ו־t3 אינו t2; u1: p=10, left הוא t1, right הוא t2; u2: p=4, left הוא t3, right=null; u3: p=7, left=null, right עצם חדש עם p=10; u4: p=3, left הוא t2, right עצם חדש עם p=4 – הכול תואם לתרשים.

טעות נפוצה: ב־u4 לכתוב this.right = t – אז right היה מפנה אל t2 עצמו ולא לקופסה חדשה. וגם: ב־u2 לנסות לכתוב super(t.p) – p פרטית ב־TT ואין פעולת get, ולכן משתמשים בפעולה הבונה המעתיקה super(t).

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

רעיון – עוקבים אחרי שרשרת הפעולות הבונות. פעולה בונה של מחלקה יורשת שאינה מזמנת במפורש פעולה בונה של מחלקת הבסיס (super(...) / base(...)) מזמנת אוטומטית את הפעולה הבונה בלי פרמטרים של מחלקת הבסיס. רק אחרי שהיא מסתיימת מתבצע שאר הגוף.

פתרון

בדיקה – מדפיסים לכל עצם את המחלקה שלו ואת val. התקבלו בדיוק הערכים שבטבלה.

טעות נפוצה: לחשוב ש־new Y(2) מתחילה מ־val = 4 (כמו new Y()). הפעולה הבונה Y(int k) לא מזמנת את Y(), אלא את X() של מחלקת הבסיס, ולכן val מתחיל מ־3.

מה נדרש – מה מודפס בכל אחת מעשר השורות.

רעיון – שני שלבים בכל קריאה:

מצב העצמים (מסעיף א): x=X(3), xy=Y(4), xz=Z(12), y=Y(8), yz=Z(14), z=Z(6).

פתרון

הפלט:

24
20
-5
5
-8
11
10
-11
16
22

בדיקה – הפלט ב־Java וב־C# זהה.

הבדל בין הנוסחים: ב־C#, Calc(Y) מוגדרת virtual ב־X ו־override ב־Y וב־Z, ולכן היא נדרסת כמו ב־Java. לעומתה, Calc(X) של Y ו־Calc(Z) של Z הן העמסות חדשות. ב־C# המהדר בוחר קודם מבין הפעולות שהוגדרו (לא כ־override) במחלקה של טיפוס ההפניה, אם אחת מהן מתאימה לארגומנט. בעשר השורות שבשאלה הבחירה הזו זהה לבחירה ב־Java (למשל בשורה 10 נבחרת Calc(Z), ובשורה 6 Calc(Z) ו־Calc(X) לא מתאימות ל־int ולכן נבחרת Calc(int)), ולכן התוצאות זהות.

טעות נפוצה: בשורה 4 לחשוב שהפעולה שתתבצע היא calc(Z) של Z, כי הארגומנט והעצם הם מטיפוס Z. טיפוס ההפניה xz הוא X, ול־X יש רק calc(int) ו־calc(Y). לכן נבחרת calc(Y), ובזמן ריצה מתבצעת הגרסה הדורסת של Z. באופן דומה, בשורה 5 הארגומנט xy מוצהר כ־X, ולכן נבחרת calc(X) ולא calc(Y).