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

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

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

המקרה m = 1 מטופל מעצמו: אין איברים לפניו, ולכן sum = 0. כל הערכים בתור חיוביים, ולכן x == 0 אינו מתקיים והתשובה false, כמו שנדרש בהערה.

בסוף מעבירים את כל האיברים מ־temp בחזרה ל־q, וכך התור חוזר למצבו המקורי ובאותו סדר.

פתרון: הקוד המלא – בלשונית Java/C#. בפעולה משתמשים רק בפעולות התור (insert, remove, isEmpty) ובמשתנים פשוטים, בלי מערך ובלי רשימה.

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

בדיקה (התור 3, 3, 6, 5, 17, 2, 36):

מתקבלים בדיוק הערכים שבטבלה, ואחרי כל קריאה התור נשאר 3, 3, 6, 5, 17, 2, 36.

טעות נפוצה: להוסיף ל־sum גם את האיבר שבמקום m לפני ההשוואה. אז משווים את x לסכום שכולל אותו, והתשובה תמיד false.

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

רעיון:

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

יעילות: יש עד n קריאות ל־isDecisive, וכל קריאה עולה O(n). לכן הפעולה היא O(n²), כאשר n הוא מספר האיברים בתור. (אפשר גם לספור במעבר אחד על התור, עם סכום מצטבר, ב־O(n), אבל השאלה מאפשרת להשתמש בסעיף א.)

בדיקה (התור 3, 3, 6, 5, 17, 2, 36): המקומות המכריעים הם 2, 3, 5, 7, כלומר 4 סיבובים.

מתקבל true, true, false, ובתור 2, 5, 1 עם k = 1 מתקבל false (אין בו סיבוב מכריע).

מה נדרש: לספור כמה מזמני הריצה של הרץ קטנים מ־limit.

רעיון: הזמנים שמורים ברצף מתחילת המערך, ויש amount זמנים. לכן עוברים רק על התאים 0 עד amount−1 וסופרים את התאים שבהם times[i] < limit. אסור לעבור על כל 30 התאים: בתאים שאחרי amount יש 0, ו־0 קטן מכל limit חיובי, כך שהתאים הריקים ייספרו בטעות כ"ריצות".

פתרון: הקוד המלא – בלשונית Java/C#. זו פעולה פנימית של המחלקה, ולכן היא ניגשת ישירות לתכונות times ו־amount.

יעילות: מעבר אחד על amount תאים – O(amount), ולכל היותר 30 בדיקות.

בדיקה: לרצה Dana עם הזמנים 52, 49, 47, 55, 48: countBelow(50) ⇒ 3 (49, 47, 48), countBelow(47) ⇒ 0 (47 אינו קטן ממש מ־47). לרץ Noam עם 61, 57: countBelow(50) ⇒ 0. לרץ עם 30 ריצות (מערך מלא) נספרו כל 30 התאים.

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

רעיון: אי אפשר לדעת מי "הכי טוב" לפני שרואים את כל הרצים, ולכן עובדים בשני מעברים:

פתרון: הקוד המלא – בלשונית Java/C#. זו פעולה חיצונית (static) שמשתמשת רק בפעולות הממשק countBelow ו־getName.

יעילות: אם במועדון k רצים, כל מעבר קורא k פעמים ל־countBelow שעולה לכל היותר 30 צעדים. סה"כ O(k).

בדיקה (הרצים שבדוגמה):

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

מה נדרש: מעקב אחרי zig על העץ: 8 ← בן שמאלי 3 (ל־3 רק בן שמאלי 1) ובן ימני 6 (ל־6 שני בנים: 4 משמאל ו־2 מימין).

רעיון: zig מחזירה 1 לעלה. בצומת פנימי היא מתחילה מ־sum = 0, מוסיפה את zig של הבן השמאלי (אם יש) ומחסירה את zig של הבן הימני (אם יש). הקריאות יורדות עד העלים, והערכים חוזרים למעלה.

פתרון (מעקב):

חזרה מהרקורסיה: zig(1) = 1 ← zig(3) = 1; zig(4) = 1, zig(2) = 1 ← zig(6) = 1 − 1 = 0; zig(8) = 1 − 0 = 1.

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

בדיקה: הקוד הנתון מדפיס על העץ 1, וערכי הביניים זהים לטבלה.

טעות נפוצה: לשכוח שאת הבן הימני מחסירים – אז מתקבל zig(6) = 2 ו־zig(8) = 3.

מה נדרש: מעקב אחרי zig על העץ: 5 ← בן שמאלי 2 ובן ימני 9; ל־2 רק בן ימני 7; ל־7 שני בנים 3 ו־1; ל־9 בן שמאלי 8 ובן ימני 4; ל־4 רק בן ימני 0.

פתרון (מעקב):

חזרה מהרקורסיה: zig(7) = 1 − 1 = 0 ← zig(2) = −0 = 0; zig(0) = 1 ← zig(4) = −1 ← zig(9) = 1 − (−1) = 2; zig(5) = 0 − 2 = −2.

הפעולה מחזירה −2.

בדיקה: הקוד הנתון מדפיס על העץ −2, וערכי הביניים: zig(3)=1, zig(1)=1, zig(7)=0, zig(2)=0, zig(8)=1, zig(0)=1, zig(4)=−1, zig(9)=2, zig(5)=−2.

מה נדרש: הערך המקסימלי של zig בעץ בן 6 צמתים, ועץ שמשיג אותו.

רעיון: מהמעקב רואים שרק העלים "מייצרים" ערכים (1), וכל מעבר לבן ימני הופך את הסימן (ראו סעיף 5): עלה שבמסלול אליו מהשורש מספר זוגי של מעברים ימינה תורם +1, ועלה עם מספר אי־זוגי של מעברים ימינה תורם −1. לכן zig ≤ מספר העלים. בעץ בינרי בן 6 צמתים יש לכל היותר 3 עלים (מספר העלים גדול ב־1 ממספר הצמתים שיש להם שני בנים, ו־6 צמתים מאפשרים לכל היותר 2 כאלה). צריך אפוא עץ עם 3 עלים שבכולם מספר זוגי של מעברים ימינה.

פתרון: המספר הגבוה ביותר הוא 3. העץ (הערכים בצמתים לא משנים):

    a
   / \
  b   R
     / \
    X   d
     \
      e

העלים: b (0 מעברים ימינה) ← +1; d (ימינה, ימינה – 2) ← +1; e (ימינה, שמאלה, ימינה – 2) ← +1.

חישוב: zig(e) = 1 ← zig(X) = −1; zig(d) = 1 ← zig(R) = −1 − 1 = −2; zig(b) = 1 ← zig(a) = 1 − (−2) = 3.

בדיקה: בין כל צורות העצים בני 6 צמתים הערך הגבוה ביותר של zig הוא 3, והוא מתקבל רק בעץ הזה.

מה נדרש: הערך המינימלי של zig בעץ בן 6 צמתים, ועץ שמשיג אותו.

רעיון: כמו בסעיף הקודם: zig ≥ −(מספר העלים) ≥ −3. צריך 3 עלים שבכולם מספר אי־זוגי של מעברים ימינה.

פתרון: המספר הנמוך ביותר הוא −3. העץ:

        a
       / \
      A   c
     / \
    Y   d
     \
      e

העלים: c (ימינה – 1) ← −1; d (שמאלה, ימינה – 1) ← −1; e (שמאלה, שמאלה, ימינה – 1) ← −1.

חישוב: zig(e) = 1 ← zig(Y) = −1; zig(d) = 1 ← zig(A) = −1 − 1 = −2; zig(c) = 1 ← zig(a) = −2 − 1 = −3.

בדיקה: בין כל העצים בני 6 צמתים הערך הנמוך ביותר הוא −3, והוא מתקבל רק בעץ הזה.

מה נדרש: לתאר במשפט מה zig מחזירה.

רעיון: כל עלה מחזיר 1. ערך זה עולה למעלה דרך כל הצמתים שבמסלול מהעלה לשורש: כשעולים מבן שמאלי הערך מתווסף כמו שהוא, וכשעולים מבן ימני הוא מוחסר – כלומר הסימן שלו מתהפך. צמתים פנימיים לא מוסיפים ערך משלהם. לכן כל עלה תורם לתוצאה +1 או −1, לפי הזוגיות של מספר המעברים ימינה במסלול מהשורש אליו.

פתרון: zig מחזירה את מספר העלים שבמסלול אליהם מהשורש יש מספר זוגי של מעברים לבן ימני, פחות מספר העלים שבמסלול אליהם יש מספר אי־זוגי של מעברים לבן ימני.

בדיקה: בעץ של סעיף (1): העלים 1 (0 מעברים ימינה), 4 (1), 2 (2) ← 2 − 1 = 1 ✓. בעץ של סעיף (2): 3 (1 – דרך 2←7), 1 (2), 8 (1), 0 (3) ← זוגי: 1 בלבד, אי־זוגי: 3, 8, 0 ← 1 − 3 = −2 ✓. zig שווה תמיד להפרש הזה.

טעות נפוצה: לכתוב ש־zig "סופרת עלים" – העלים נספרים עם סימן, והתוצאה יכולה להיות 0 או שלילית. שימו לב גם שעל עץ ריק (null) הפעולה נכשלת, ולכן השאלה מדברת על עץ שאינו ריק.

מה נדרש: מעקב אחרי zag על העץ: 4 ← בן שמאלי 1 (ל־1 רק בן שמאלי 6) ובן ימני 8; ל־8 בן שמאלי 5 (בנים 9 ו־7) ובן ימני 0 (ל־0 רק בן ימני 3).

רעיון: zag מחזירה false לעץ ריק. בצומת לא ריק: אם zig של תת־העץ שלו שלילית – true מיד. אחרת ממשיכים לבן השמאלי, ורק אם הוא החזיר false – לבן הימני (|| מקוצר). כלומר zag מחפשת צומת כלשהו שבו zig < 0.

ערכי zig (לפי הכלל מסעיף 5 או בחישוב): zig(6) = 1, zig(1) = 1, zig(9) = 1, zig(7) = 1, zig(5) = 0, zig(3) = 1, zig(0) = −1, zig(8) = 0 − (−1) = 1, zig(4) = 1 − 1 = 0.

פתרון (מעקב):

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

בדיקה: הקוד הנתון מחזיר על העץ true, וסדר הקריאות זהה לטבלה.

מה נדרש: בסעיף ב(1) התקבל true, ולכן צריך עץ עם יותר מ־3 צמתים שבעבורו zag מחזירה false.

רעיון: zag מחזירה true בדיוק כשיש צומת שבו zig של תת־העץ שלו שלילית. לכן צריך עץ שבו zig ≥ 0 בכל צומת. למשל: בעץ מלא כל צומת פנימי מחשב 1 − 1 = 0, ובעלים zig = 1. (גם "שרשרת שמאלית" של 4 צמתים מתאימה: zig = 1 בכל צומת.)

פתרון: עץ מלא בן 7 צמתים:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

zig של העלים 1, 3, 5, 7 הוא 1; zig(2) = 1 − 1 = 0; zig(6) = 0; zig(4) = 0 − 0 = 0. אין צומת עם zig שלילית, ולכן zag(1), zag(3)… כולן false, ו־zag מחזירה false – ההפך מסעיף ב(1).

בדיקה: zag מחזירה על העץ הזה (ועל השרשרת השמאלית בת 4 צמתים) false. בנוסף נבדק על כל צורות העצים עד 8 צמתים ש־zag מחזירה true בדיוק כשיש צומת עם zig < 0.

טעות נפוצה: לבחור עץ שבו לשורש בן ימני עלה ובן שמאלי עם שני בנים – אז zig(שורש) = 0 − 1 = −1 ו־zag מחזירה true.

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

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

פתרון: הטענה נכונה. נניח בשלילה שאין בגרף מעגל. אז כל רכיב קשירות שלו הוא גרף קשיר ללא מעגלים – כלומר עץ. אם יש בגרף k רכיבים, ולרכיב ה־i יש nᵢ קודקודים, אז יש בו nᵢ−1 קשתות. סך הקשתות:
(n₁−1) + (n₂−1) + … + (n_k−1) = n − k ≤ n − 1

(כי k ≥ 1). אבל בגרף יש n קשתות – סתירה. לכן בגרף יש מעגל.

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

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

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

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

הגרף קשיר וכל המשקלים שונים. קרוסקל: מוסיף a–b (1), מוסיף b–c (2), דוחה את a–c (3) כי היא סוגרת את המעגל a–b–c, מוסיף c–d (4). העפ"מ: a–b , b–c , c–d במשקל 7. כשכל המשקלים שונים העפ"מ יחיד – והקשת השלישית הקלה, a–c, אינה בו.

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

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

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

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

פתרון: הטענה נכונה. נניח שנמחקה הקשת u–v, ויהי x קודקוד כלשהו. בגרף המקורי (הקשיר) יש מסלול פשוט מ־x ל־u.

כלומר כל קודקוד נמצא ברכיב של u או ברכיב של v – יש לכל היותר 2 רכיבי קשירות. (יהיו בדיוק 2 אם u–v היא "גשר", ו־1 אם היא על מעגל.)

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

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

פתרון: הטענה נכונה. נניח ש־u ישיג מ־s (המקרה ש־v ישיג סימטרי). ניקח מסלול קצר ביותר מ־s ל־u (באורך d(u)) ונוסיף לו את הקשת u–v: קיבלנו מסלול מ־s ל־v באורך d(u)+1. לכן v ישיג ו־d(v) ≤ d(u) + 1.
הגרף לא מכוון, ולכן אפשר לעבור בקשת גם מ־v ל־u. באותו אופן: d(u) ≤ d(v) + 1.
משני אי־השוויונות: −1 ≤ d(u) − d(v) ≤ 1 , כלומר |d(u) − d(v)| ≤ 1.

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

רעיון: בגרף מכוון הקשת u→v נותנת קיצור רק בכיוון אחד: d(v) ≤ d(u)+1. בכיוון ההפוך אין שום הגבלה – קשת יכולה "לחזור אחורה" לקודקוד קרוב מאוד ל־s.

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

BFS מ־s: d(s) = 0 , d(a) = 1 , d(b) = 2 , d(c) = 3. שני הקצוות של הקשת c→s ישיגים, אבל |d(c) − d(s)| = |3 − 0| = 3 > 1.

בדיקה: BFS על הגרף נותן בדיוק את המרחקים 0, 1, 2, 3.

טעות נפוצה: להעתיק את הנימוק של הגרף הלא מכוון. בגרף מכוון נכון רק החלק d(v) ≤ d(u) + 1.

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

רעיון: ב־DFS יש בחירה – באיזה שכן לא מגולה להמשיך. אם בוחרים שכן שממנו "נתקעים" מוקדם, חוזרים אחורה ויוצא פיצול.

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

סריקה 1 (מ־s בוחרים קודם את b): s → b → a → c. קשתות העץ: s–b , b–a , a–c – זו שרשרת.

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

בדיקה: בין עצי ה־DFS מ־s בגרף מתקבלים גם השרשרת s–b–a–c וגם העץ שבו ל־a שני בנים.

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

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

פתרון:
קשתות העץ הנתון (ולכן בוודאי ב־G): s–e , e–f , f–g , e–h.
קשתות נוספות אפשריות – רק בין קודקוד לאב קדמון שלו: s–f , s–g , e–g , s–h (אולי קיימות ואולי לא).
קשתות שאינן יכולות להיות ב־G: h–f ו־h–g (h נמצא בענף אחר של e מאשר f ו־g).

סריקה שנותנת את (i), בגרף G שבו הקשתות הן העץ הנתון ועוד s–g: מתחילים ב־f ← בוחרים את השכן e ← מ־e בוחרים את s ← מ־s עוברים ל־g (השכנים של g: f, s – כבר התגלו) ← חוזרים ל־s (אין לו עוד שכנים לא מגולים) ← חוזרים ל־e ועוברים ל־h ← חוזרים עד f; גם g כבר התגלה. התקבלו בדיוק קשתות העץ f–e , e–s , s–g , e–h.
(אילו הייתה ב־G גם הקשת s–h, ה־DFS היה מגלה את h מתוך s, ו־h היה בן של s. לכן (i) מתקבל רק כשאין s–h – אבל מספיק שקיים גרף G מתאים, ולכן התשובה "ייתכן".)

בדיקה: בדיוק 16 גרפים על 5 הקודקודים נותנים את העץ הנתון מ־s (העץ ועוד תת־קבוצה של {s–f , s–g , e–g , s–h}). בכל אחד מהם נמצאו כל עצי ה־DFS מ־f: עץ (i) מתקבל ב־4 גרפים (אלה שיש בהם s–g ואין בהם s–h), ועצים (ii) ו־(iii) אף פעם לא.

מה נדרש: להראות ש־BFS מגיע לכל מקום ש־DFS מגיע אליו (מאותו קודקוד).

רעיון: שתי הסריקות מבקרות בדיוק בקבוצת הקודקודים הישיגים מ־ s ; הן נבדלות רק בסדר הביקור.

פתרון: הטענה נכונה.

מ־1 ו־2: ה־BFS מ־ s מבקר בכל הקודקודים.

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

רעיון: קשירות תלויה באיך הקשתות מפוזרות, לא רק בכמה קשתות יש. אפשר "לבזבז" קשתות על מעגל בתוך חלק אחד של הגרף.

פתרון: הטענה לא נכונה. דוגמה נגדית: n = 6 , קודקודים a, b, c, d, e, f וקשתות a–b, b–c, c–a, d–e, e–f, f–d (שני משולשים). יש 6 קודקודים ו־6 קשתות, אבל אין אף קשת בין {a, b, c} ובין {d, e, f} , ולכן אין מסלול מ־ a אל d – הגרף אינו קשיר.
(הכיוון ההפוך כן נכון: גרף קשיר על n קודקודים חייב לפחות n − 1 קשתות; אבל מספר קשתות גדול אינו מבטיח קשירות.)

בדיקה: DFS מ־ a מגיע רק ל־ {a, b, c}.

טעות נפוצה: להסיק מ"עץ על n קודקודים יש n − 1 קשתות" שכל גרף עם n − 1 קשתות או יותר הוא קשיר.

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

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

פתרון: הטענה לא נכונה. דוגמה נגדית: קשתות מכוונות s → a (1), a → b (1), b → t (1), s → t (5).

("מספר קשתות מינימלי" הוא מה ש־BFS מוצא; "משקל מינימלי" – מה שדייקסטרה מוצא. הם שווים רק כשכל המשקלים שווים.)

בדיקה: המסלולים מ־ s אל t עם משקליהם: הקל ביותר (3) עם 3 קשתות, והקצר ביותר במספר קשתות (1) במשקל 5.

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

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

פתרון: הטענה נכונה. תהי e = (u, v) הקשת היחידה בעלת המשקל הקטן ביותר, ונניח בשלילה שיש עץ פורש מינימלי T שאינו מכיל את e .

קיבלנו עץ פורש קל מ־ T – סתירה לכך ש־ T מינימלי. לכן e שייכת לכל עץ פורש מינימלי.
(גם האלגוריתם של קרוסקל בוחר את הקשת הזאת ראשונה. אם יש כמה קשתות קלות ביותר במשקל שווה, הטענה כבר לא נכונה – למשל במשולש שכל משקליו 1.)

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

רעיון: דייקסטרה "קובע" את הקודקוד בעל ה־ d הקטן ביותר ולא משנה אותו יותר. זה נכון רק כי בלי משקלים שליליים מסלול לא יכול להתקצר כשממשיכים בו. קשת שלילית שוברת את ההנחה.

פתרון: הטענה לא נכונה. דוגמה נגדית: קשתות מכוונות s → a (2), s → b (3), b → a (−2). אין מעגלים בכלל, ולכן אין מעגל שלילי.

אבל המסלול s → b → a שוקל 3 + (−2) = 1 < 2 . דייקסטרה טעה ב־ d[a] .
בלמן־פורד (הרפיה של כל הקשתות n − 1 פעמים) מוצא את המרחק הנכון d[a] = 1 .

בדיקה: דייקסטרה מחזיר d[a] = 2 , ובלמן־פורד מחזיר d[a] = 1 .

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

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

פתרון: הטענה נכונה. מיון טופולוגי הוא סידור של הקודקודים שבו לכל קשת u → v , u מופיע לפני v .

לכן אותו סידור הוא מיון טופולוגי גם של הגרף החדש (ובפרט הגרף החדש חסר מעגלים).
(לעומת זאת, הוספת הקשת ההפוכה y → x יכולה ליצור מעגל: למשל בגרף a → b → c עם המיון a, b, c, הקשת c → a סוגרת מעגל.)

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

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

פתרון: קודקוד i של המעגל החיצוני נוגע בשתי קשתות חיצוניות (אל הקודקוד שלפניו ואל הקודקוד שאחריו במעגל) ובחישור אחד (אל i') ⇐ דרגה 3 . באותו אופן קודקוד i' של המעגל הפנימי נוגע בשתי קשתות פנימיות ובחישור אחד (אל i) ⇐ דרגה 3 . כלומר כל הקודקודים בגרף בדרגה 3 .

בדיקה: ב־ P₆ שבאיור: לקודקוד 1 שכנים 6, 2, 1' , ולקודקוד 1' שכנים 6', 2', 1 . כך גם לכל 3 ≤ n ≤ 8 .

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

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

בדיקה: לפי משפט סכום הדרגות: 2n קודקודים · 3 = 6n = 2·(מספר הקשתות) ⇐ 3n קשתות = n + n + n . ב־ P₆ : 6 + 6 + 6 = 18 קשתות.

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

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

פתרון:

בדיקה: צביעה בשני צבעים מצליחה ל־ n = 4, 6, 8 ונכשלת ל־ n = 3, 5, 7 .

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

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

פתרון:

למשל ב־ P₆ יש 6³ = 216 עפ"מים.

בדיקה: מספר העפ"מים: n = 3 – 27 , n = 4 – 64 , n = 5 – 125 , n = 6 – 216 , כולם במשקל 2n .

טעות נפוצה: לענות "n עפ"מים" (רק בחירת החישור) – ולשכוח שגם בכל אחד משני המעגלים אפשר להשמיט כל אחת מ־ n הקשתות.

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

רעיון: נסמן ב־ k את מספר הקשתות בקשת הקצרה של המעגל החיצוני בין שני הקודקודים (1 ≤ k ≤ n/2). מסלול שנשאר על המעגל החיצוני שוקל לפחות k·a . המסלול "למטה–לאורך המעגל הפנימי–למעלה" (חישור, k קשתות פנימיות, חישור) שוקל 2s + k·b .

פתרון: אם 2s + b < a , אז לכל k ≥ 1 : 2s + k·b ≤ k·(2s + b) < k·a . כלומר המסלול דרך המעגל הפנימי קל ממש מכל מסלול שנשאר על המעגל החיצוני, ולכן כל מסלול קל ביותר עובר בקודקוד פנימי.
דוגמה: a = 5 , b = 1 , s = 1 : בין שני קודקודים שכנים – הקשת החיצונית 5 , ודרך המעגל הפנימי 1 + 1 + 1 = 3 ; בין קודקודים במרחק k – על המעגל החיצוני 5k , ודרך המעגל הפנימי 2 + k .

בדיקה: בעבור 3 ≤ n ≤ 8, עם a = 5 , b = 1 , s = 1 , אף מסלול קל ביותר בין שני קודקודים חיצוניים אינו נשאר על המעגל החיצוני. הוא גם אישר על טבלת ערכים שלמים שהתנאי מתקיים בדיוק כאשר 2s + b < a .

מה נדרש: הערך הגדול ביותר של s כאשר a = 10 ו־ b = 2 .

רעיון: המקרה הקשה הוא שני קודקודים שכנים במעגל החיצוני: הקשת הישירה שוקלת a = 10 , וכל מסלול שעובר בקודקוד פנימי צריך לרדת בחישור, לעבור לפחות קשת פנימית אחת (כי i' ≠ (i+1)') ולעלות בחישור – לפחות 2s + b .

פתרון: צריך 2s + 2 < 10 ⇐ s < 4 . אם המשקלים שלמים, הערך הגדול ביותר הוא s = 3 : אז בין שכנים 3 + 2 + 3 = 8 < 10 , ולפי סעיף (1) התנאי מתקיים לכל זוג.
ב־ s = 4 : בין שני שכנים יש שני מסלולים קלים במשקל 10 – הקשת הישירה (10) והמסלול 4 + 2 + 4 . הקשת הישירה אינה עוברת בקודקוד פנימי, ולכן לא כל מסלול קל עובר במעגל הפנימי.
(אם s יכול להיות לא שלם, כל s < 4 מתאים ואין "גדול ביותר"; התשובה המקובלת היא s = 3 למשקלים שלמים, או "s קטן מ־ 4".)

בדיקה: עם a = 10 , b = 2 ו־ s = 1, 2, 3, 3.9, 4, 5 : התנאי מתקיים רק ל־ s = 1, 2, 3, 3.9 .

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

מה נדרש: המילה הקצרה ביותר ב־L₁.

רעיון:
אורך המילה הוא n + 2k + (n + k + 2) = 2n + 3k + 2, והוא הקטן ביותר כש־n = k = 1.

פתרון:
n = 1, k = 1: b¹ c² a⁴ = bccaaaa (אורך 7; 4 = 1 + 1 + 2). כל בחירה אחרת נותנת אורך 9 לפחות.

בדיקה: המילים של L₁ עד אורך 10 הן bccaaaa, bbccaaaaa, bccccaaaaa – הקצרה ביותר bccaaaa.

טעות נפוצה: לכתוב bcaaaa – מספר ה־c הוא 2k, כלומר זוגי ולפחות 2.

מה נדרש: אוטומט מחסנית דטרמיניסטי ל־L₁ = {bⁿ c²ᵏ aⁿ⁺ᵏ⁺² | n, k ≥ 1}.

רעיון:

פתרון:

בכל צירוף (מצב, אות, ראש מחסנית) יש לכל היותר מעבר אחד ואין מעברי ε – האוטומט דטרמיניסטי. כל צירוף שאינו בטבלה = דחייה (למשל a אחרי מספר אי־זוגי של c – במצב q2; b אחרי c; a שלישי אחרי ריקון המחסנית – ב־q7 אין מעברים).

מעקב על bbccaaaaa (n = 2, k = 1, ולכן 2 + 1 + 2 = 5 אותיות a):

הקלט נגמר במצב q7 ⇒ מתקבלת. לעומת זאת bbccaaaa נגמרת ב־q6 (לא מקבל) ונדחית.

בדיקה: האוטומט מקבל בדיוק את המילים של L₁ – גם מילים של L₁ וגם מילים שמתקבלות מהן בשינוי, הוספה או מחיקה של אות אחת מטופלות נכון.

טעות נפוצה: לשכוח את ה־"+2": לקבל כבר כשהמחסנית מתרוקנת. אחרי ש־X נשלף חייבים לקרוא בדיוק עוד שני a.

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

רעיון:
כל מילה של L₁ מתחילה ב־b ומסתיימת ב־a, ואין בה b אחרי a. לכן במילה של L₂ החלק השני מתחיל ב־b הראשון שבא אחרי a. החלוקה נקבעת באופן יחיד, ובודקים כל חלק בנפרד.

פתרון:
(1) bccaaaabccaaaa: החלוקה: bccaaaa | bccaaaa. בכל חלק n = 1, k = 1 (2 c) ⇒ צריך 1 + 1 + 2 = 4 a, ויש 4. ⇒ שייכת ל־L₂.

(2) bccaaabccaaaaa: החלוקה היחידה האפשרית: bccaaa | bccaaaaa. בחלק הראשון n = 1, k = 1 ⇒ צריך 4 a, אבל יש רק 3. ⇒ לא שייכת ל־L₂ (גם החלק השני אינו ב־L₁: 5 a במקום 4).

(3) bbccaaaaabccccaaaaa: החלוקה: bbccaaaaa | bccccaaaaa. חלק ראשון: n = 2, k = 1 ⇒ 2 + 1 + 2 = 5 a ✔. חלק שני: n = 1, k = 2 (4 c) ⇒ 1 + 2 + 2 = 5 a ✔. ⇒ שייכת ל־L₂.

בדיקה: בכל נקודות החלוקה לכל מילה: (1) – חלוקה אחת, (2) – אין אף חלוקה, (3) – חלוקה אחת, כמו בפתרון.

טעות נפוצה: לספור את כל ה־a במילה יחד (למשל ב־(2) יש 3 + 5 = 8 = 4 + 4) ולהסיק שהיא שייכת. כל חלק צריך להתאים בנפרד.

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

רעיון: ב־(L₁ ∪ L₂)* אפשר לערבב בין חלקים מ־L₁ לחלקים מ־L₂ באותה מילה. ב־L₁* ∪ L₂* כל מילה בנויה רק מחלקים של שפה אחת.

פתרון: לא נכונה. דוגמה נגדית: L₁ = {a} , L₂ = {b}.

השפות שונות – הטענה לא מתקיימת. (הכיוון ⊇ תמיד נכון: L₁* ∪ L₂* ⊆ (L₁ ∪ L₂)*.)

בדיקה: בדוגמה האגפים שונים; באופן כללי אגף ימין תמיד מוכל באגף שמאל, אבל לא תמיד שווה לו.

מה נדרש: לקבוע אם היפוך הסגור שווה לסגור של ההיפוך.

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

פתרון: נכונה.

שתי ההכלות מתקיימות, ולכן השפות שוות.

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

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

רעיון: אותה מילה יכולה להתקבל בשרשור בשתי דרכים שונות: פעם כמילה מ־L₁ ועוד חלק מ־L₃, ופעם כמילה מ־L₂ ועוד חלק אחר מ־L₃. אז באגף ימין היא "נמחקת", ובאגף שמאל היא נשארת.

פתרון: לא נכונה. דוגמה נגדית: L₁ = {a} , L₂ = {ε} , L₃ = {b, ab}.

{ab, aab} ≠ {aab} – הטענה לא מתקיימת.

בדיקה: שני האגפים לדוגמה הזאת: {ab, aab} מול {aab}.

מה נדרש: אוטומט מחסנית דטרמיניסטי (אמ"ד) שמקבל בדיוק את המילים aⁱbʲaᵏ עם i, k ≥ 1 ו־j = i + k.

רעיון: נחלק את בלוק ה־b לשני חלקים: i ה־b הראשונים "מבטלים" את ה־a של הבלוק הראשון, ו־k ה־b הנותרים צריכים להתאים ל־a של הבלוק השני.

פתרון:

(q₁ – בבלוק ה־a הראשון; q₂ – בבלוק ה־b, שלב 1; q₃ – שלב 1 הסתיים בדיוק; q₄ – בבלוק ה־b, שלב 2; q₅ – בבלוק ה־a השני.)

מעקב על aabbbbbaaa (i = 2, j = 5, k = 3, ו־5 = 2 + 3 ⇒ בשפה):

סוף הקלט במצב f ⇒ מתקבלת.

דוגמאות דחייה: aba (j = 1 = i: אחרי שליפת X, במצב q₃ נקרא a – אין מעבר); aabba (j = 2 = i: אותו דבר); abbaa (k = 2 אבל רק b אחד עודף: ה־a הראשון שולף את Y ⇒ f, ה־a השני – אין מעבר מ־f); abbab (b אחרי f – אין מעבר).

בדיקה: האוטומט מקבל בדיוק את המילים של L. בין השאר: abba, aabbba, abbbaa, aabbbbaa, aaabbbba מתקבלות; ε, a, aba, abb, abbaa, aabba, abbba, bba נדחות.

טעות נפוצה: להמשיך לשלוף בשלב 2 במקום לדחוף. אחרי ש־X נשלף אין במחסנית מה "לזכור" – צריך לספור מחדש את ה־b העודפים בדחיפה, כדי להשוות אותם ל־a של הבלוק השני.

מה נדרש: מכונת טיורינג שמקבלת ⊢x#y (x, y מעל {a, b}, באותו אורך) ומשאירה על הסרט $x₀y₀x₁y₁…$.

רעיון:

למה החיפושים לא מתבלבלים עם האותיות שהועתקו לסוף? בחיפוש ב־x עוצרים באות הראשונה שאינה X – היא לפני ה־#. בחיפוש ב־y מתחילים מה־# – האות הראשונה שאינה Y היא לפני ה־$.

פתרון:

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

בין שני ה־$: ababba ✔ (כמו בדוגמה).

בדיקה: לכל הזוגות x, y מעל {a, b} המכונה עוצרת, על הסרט נשארים בדיוק שני סימני $, וביניהם בדיוק השזירה. למשל aab#bba ⇒ $ababba$ (146 צעדים), abba#bbab ⇒ $abbbbaab$, a#b ⇒ $ab$.

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

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

רעיון

פתרון – :

public class Fragile extends Parcel {
    private boolean isInsured;     // האם החבילה מבוטחת?
    public void warn() {
        System.out.println("Careful! " + getSender());
    }
}
public class Glass extends Fragile {
    private int layers;            // מספר שכבות הריפוד
}
public class Electronic extends Fragile {
    private boolean hasBattery;    // האם יש במכשיר סוללה?
}
public class Letter extends Parcel {
    private boolean isRegistered;  // האם זה דואר רשום?
}

תרשים ההייררכייה (החץ עם המשולש הריק מצביע מהמחלקה היורשת אל מחלקת הבסיס):

בדיקה – המחלקות המלאות (אותן כותרות ותכונות, יחד עם הפעולות הבונות מסעיף ב) תקינות ב־Java וב־C#.

טעות נפוצה: להשאיר ב־warn() את sender – אחרי שהתכונה נמחקה מ־Fragile זו שגיאת הידור (התכונה פרטית ב־Parcel). טעות נוספת: להוריש את Glass ואת Electronic ישירות מ־Parcel ולהשאיר בהן את isInsured ואת warn() – זו כפילות קוד.

מה נדרש – פעולות בונות שמתאימות לקריאות ב־main / Main ומאתחלות את כל התכונות.

רעיון

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

בדיקה – המחלקות עם הפעולות הבונות ו־Tester הנתונה תקינות ב־Java וב־C#, והפעולה הראשית מתבצעת ללא שגיאות.

טעות נפוצה: לכתוב ב־Glass super(sender, weight) – ל־Fragile אין פעולה בונה עם שני פרמטרים, וגם isInsured לא תאותחל.

מה נדרש – לדרוס את toString (ב־C#: ToString) רק במחלקות שבהן הפלט שונה מזה שהמחלקה כבר יורשת.

רעיון – println(parcels[i]) מפעיל את toString של הטיפוס בפועל של העצם (פולימורפיזם). נבדוק כל שורה בפלט:

ב־C# כל ToString מוגדרת עם override (גם ב־Glass, שדורסת את הגרסה של Fragile).

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

בדיקה – Tester עם הלולאה הנתונה (Java ו־C#) מדפיסה בדיוק:

Glass from Dana! 4 layers
Registered letter. From Omer, 1 kg.
From Noa, 6 kg. Fragile!
From Yossi, 2 kg. Fragile!
Letter. From Lior, 1 kg.

טעות נפוצה: לכתוב ב־Glass super.toString() + ... – זה היה מדפיס גם From Dana, 3 kg. Fragile!. או לשכוח ש־Electronic כבר יורשת את toString של Fragile (ולא של Parcel), ולכן אין צורך לדרוס בה.

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

רעיון – הפעולה לא תקינה (שגיאת הידור). הטיפוס המוצהר של arr[i] הוא Parcel, והמהדר בודק קריאה לפי הטיפוס המוצהר; ב־Parcel אין פעולה warn() (ב־C#: Warn()), ולכן הקריאה לא עוברת הידור, גם אם בזמן ריצה העצם הוא חבילה שבירה.
התיקון: לבדוק אם העצם הוא חבילה שבירה (instanceof Fragile ב־Java, is Fragile ב־C#) ורק אז להמיר (casting) ל־Fragile ולקרוא ל־warn(). Glass ו־Electronic יורשות מ־Fragile, ולכן גם הן עוברות את הבדיקה.

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

בדיקה – עבור parcels: Glass (תא 0), Fragile (תא 2) ו־Electronic (תא 3) מדפיסים, שני המכתבים לא. הפלט (Java ו־C#):

Careful! Dana
Careful! Noa
Careful! Yossi

הפעולה המקורית אכן לא עוברת הידור (Java: cannot find symbol; C#: שגיאה CS1061 – ל־Parcel אין הגדרה ל־Warn). במערך עם Letter, תא null, Electronic ו־Parcel מודפסת שורה אחת (Careful! Tom), בלי שגיאה.

מה נדרש – להוסיף את Time לתרשים ולכתוב את כותרת המחלקה Activity עם התכונות שלה.

רעיון

פתרון

תרשים המחלקות המלא:

כותרת המחלקה ותכונותיה – :

public class Activity {
    private int day;        // היום בשבוע (1–7)
    private Time start;     // שעת ההתחלה
}

בדיקה – המחלקה (יחד עם Time) תקינה ב־Java וב־C#.

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

מה נדרש – להחזיר מערך Lesson שגודלו בדיוק מספר השיעורים ביום day שמתחילים לפני t.

רעיון

פתרון – :

public class Center {
    private Activity[] arr;
    private int count;

    public Center() {
        this.arr = new Activity[500];
        this.count = 0;
    }
    public void add(Activity a) {
        this.arr[this.count] = a;
        this.count++;
    }

    public Lesson[] lessonsBefore(int day, Time t) {
        int num = 0;
        for (int i = 0; i < this.count; i++) {
            if (this.arr[i] instanceof Lesson && this.arr[i].getDay() == day
                    && this.arr[i].getStart().before(t)) {
                num++;
            }
        }
        Lesson[] result = new Lesson[num];
        int k = 0;
        for (int i = 0; i < this.count; i++) {
            if (this.arr[i] instanceof Lesson && this.arr[i].getDay() == day
                    && this.arr[i].getStart().before(t)) {
                result[k] = (Lesson) this.arr[i];
                k++;
            }
        }
        return result;
    }
}

(הפעולה הבונה ו־add נכתבו לצורך הבדיקה בלבד.)

בדיקה – מרכז עם שיעורים ביום 2 בשעות 8:30, 10:00, 9:59, 10:15, שיעור ביום 3, השכרה וטורניר ביום 2: lessonsBefore(2, 10:00) החזירה 2 שיעורים (המאמנים Gal ו־Dana; השיעור של 10:00 אינו "לפני" 10:00). ביום שאין בו שיעורים הוחזר מערך בגודל 0. גם במרכז מלא (500 פעילויות) התקבל המספר הנכון (Java ו־C#).

טעות נפוצה: לרוץ עד arr.length במקום עד count – התאים שאחרי count הם null; או ליצור מערך בגודל count ולהשאיר בו תאים ריקים.

מה נדרש – פעולה usesCourt שמחזירה תשובה לפי סוג הפעילות, בלי instanceof (ב־C#: בלי is/as).

רעיון – דריסה:

פתרון – :

public class Activity {
    private int day;        // היום בשבוע (1–7)
    private Time start;     // שעת ההתחלה

    public Activity(int day, Time start) {
        this.day = day;
        this.start = start;
    }
    public int getDay() { return day; }
    public Time getStart() { return start; }

    public boolean usesCourt(int court) {
        return false;
    }
}

public class Rental extends Activity {
    private String renter;
    private int court;

    public Rental(int day, Time start, String renter, int court) {
        super(day, start);
        this.renter = renter;
        this.court = court;
    }
    public String getRenter() { return renter; }
    public int getCourt() { return court; }

    public boolean usesCourt(int court) {
        return this.court == court;
    }
}

public class Tournament extends Activity {
    private int teams;
    private int[] courts;

    public Tournament(int day, Time start, int teams, int[] courts) {
        super(day, start);
        this.teams = teams;
        this.courts = courts;
    }
    public int getTeams() { return teams; }
    public int[] getCourts() { return courts; }

    public boolean usesCourt(int court) {
        for (int i = 0; i < this.courts.length; i++) {
            if (this.courts[i] == court) {
                return true;
            }
        }
        return false;
    }
}

הפעולות שנוספו: usesCourt במחלקה Activity (מחזירה false), דריסה במחלקה Rental ודריסה במחלקה Tournament.

בדיקה – שיעור, מגרש 3 → false; השכרה של מגרש 3, מגרש 3 → true; השכרה של מגרש 5, מגרש 3 → false; טורניר במגרשים {1, 2, 4}: מגרש 4 → true, מגרש 3 → false (Java ו־C#).

טעות נפוצה: בטורניר לכתוב if (courts[i] == court) return true; else return false; בתוך הלולאה – כך נבדק רק המגרש הראשון.

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

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

פתרון

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

טעות נפוצה: לחשב את f(2) בבנייה של R עם הערך החדש של n (למשל ב־new R(4): n = 15 ואז 15 + (2 − 15) = 2). f(2) מחושבת לפני שההשמה מתבצעת, כש־n עדיין 5.

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

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

מצב העצמים (מסעיף א): p=P(5), pq=Q(10), pr=R(12), q=Q(3), qr=R(4), r=R(6).

פתרון

הפלט:

8
50
40
1
-2
48
-6
-8
-4
30

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

הבדל בין הנוסחים: ב־C#, F(P) מוגדרת virtual ב־P ו־override ב־Q, ו־F(Q) מוגדרת virtual ב־Q ו־override ב־R. כך שתי הפעולות נדרסות כמו ב־Java, והתוצאות זהות.

טעות נפוצה: בשורה 3 לבחור את f(Q), כי הארגומנט qr מטיפוס Q והעצם pq הוא Q. טיפוס ההפניה pq הוא P, ול־P אין f(Q). לכן נבחרת f(P), ובזמן ריצה מתבצעת הגרסה של Q (מכפלה).