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

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

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

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

בשורה האחרונה בראש התור 0, ולכן הלולאה מסתיימת. q.remove() מוציא את ה־0, והתור חוזר להיות 3, 5, 2, 4, 6.
a = 10 ו־b = 10 ⇒ a == b ⇒ הפעולה מחזירה true.

בדיקה: על הקוד של השאלה: kkk(q, 3) = true, והתור אחרי הקריאה: [3, 5, 2, 4, 6].

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

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

הסבר: a סוכם את האיברים במקומות 1 עד k, ו־b את האיברים במקומות k + 1 עד n. אם k = 0 או k ≥ n, אחד החלקים ריק (סכומו 0) והשני חיובי, ולכן מוחזר false.

בדיקה: על התור 3, 5, 2, 4, 6: k = 0, 1, 2 ⇒ false ; k = 3 ⇒ true (10 = 10) ; k = 4, 5 ⇒ false.

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

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

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

מה נדרש: לעקוב אחר mystery(q, 5) (ב־C#: Mystery) ולכתוב מה מוחזר. התור: 3, 5, 2, 4, 6 (סכום כולל 20).

רעיון: mystery יורדת מ־n כלפי מטה: אם n == 0 היא מחזירה 0; אם kkk(q, n) מחזירה true היא מחזירה n; אחרת היא קוראת לעצמה עם n − 1. התור לא משתנה בין הקריאות.

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

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

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

מה נדרש: להסביר מה mystery(q, n) מחזירה כאשר n הוא גודל התור.

תשובה: הפעולה מחזירה את המספר k כך שסכום k האיברים הראשונים בתור שווה לסכום שאר האיברים – כלומר את המקום שבו אפשר "לחתוך" את התור לשני חלקים (ראש וסוף) שסכומיהם שווים. אם אין חלוקה כזו – הפעולה מחזירה 0. התור q לא משתנה.

הסבר: mystery בודקת את k = n, n − 1, …, 1 לפי הסדר בעזרת kkk (סעיף א), ומחזירה את ה־k הראשון שעבורו kkk מחזירה true. אם לא נמצא כזה, היא מגיעה ל־n = 0 ומחזירה 0. כיוון שכל המספרים חיוביים, סכום k האיברים הראשונים גדל ממש כש־k גדל, ולכן יש לכל היותר מקום אחד כזה.

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

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

תשובה: O(n²) במקרה הגרוע.

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

מה נדרש: למחוק את n השירים האחרונים שאורכם גדול מ־t (או את כולם, אם יש פחות מ־n כאלה) ולהחזיר כמה שירים נמחקו.

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

כיוון ש־n קטן מכמות השירים, תמיד נשאר לפחות שיר אחד והשרשרת לא מתרוקנת.

פתרון:

public int removeLastLong(int n, int t)
{
    // מעבר ראשון: כמה שירים ארוכים מ-t יש בשרשרת
    int total = 0;
    Node<Song> pos = lst;
    while (pos != null)
    {
        if (pos.getValue().getLength() > t)
            total++;
        pos = pos.getNext();
    }
    // כמה מן השירים הארוכים (הראשונים שבהם) יישארו בשרשרת
    int keep = total - n;
    if (keep < 0)
        keep = 0;
    // מעבר שני: מדלגים על keep השירים הארוכים הראשונים ומוחקים את השאר
    int count = 0;
    Node<Song> prev = null;   // החוליה שלפני pos
    pos = lst;
    while (pos != null)
    {
        boolean isLong = pos.getValue().getLength() > t;
        if (isLong && keep == 0)
        {
            if (prev == null)
                lst = pos.getNext();
            else
                prev.setNext(pos.getNext());
            count++;
        }
        else
        {
            if (isLong)
                keep--;
            prev = pos;
        }
        pos = pos.getNext();
    }
    return count;
}

בדיקה: על השרשרת מהדוגמה (Rain:210, Echo:185, Blue:240, Moon:150, Fire:210, Wind:195, Sky:170):

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

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

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

רעיון:

הלולאה מסתיימת, כי בכל סיבוב נמחק שיר. השרשרת לא מתרוקנת: כל עוד sum > maxTotal ≥ אורך כל שיר, יש בשרשרת לפחות שני שירים, ולכן n = 1 קטן מכמות השירים, כפי שדורשת ההנחה של סעיף א (t = max − 1 אינו שלילי, כי max ≥ 1).

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

// משתמשת בפעולה removeLastLong מסעיף א
public int shorten(int maxTotal)
{
    // סכום אורכי כל השירים
    int sum = 0;
    Node<Song> pos = lst;
    while (pos != null)
    {
        sum = sum + pos.getValue().getLength();
        pos = pos.getNext();
    }
    int count = 0;
    while (sum > maxTotal)
    {
        // מציאת אורך השיר הארוך ביותר
        int max = lst.getValue().getLength();
        pos = lst.getNext();
        while (pos != null)
        {
            if (pos.getValue().getLength() > max)
                max = pos.getValue().getLength();
            pos = pos.getNext();
        }
        // השירים שאורכם גדול מ-(max-1) הם בדיוק השירים שאורכם max;
        // מוחקים את האחרון מביניהם
        removeLastLong(1, max - 1);
        sum = sum - max;
        count++;
    }
    return count;
}

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

910 ≤ 1000 ⇒ הלולאה נעצרת, מוחזר 2, והשרשרת Rain, Echo, Moon, Wind, Sky – כמו בדוגמה. מקרים נוספים: maxTotal = 1360 (מוחזר 0, ללא שינוי), maxTotal = 700 (מוחזר 3: Blue, Fire, Rain), maxTotal = 240 (מוחזר 6, נשאר Moon).

יעילות: המעבר הראשון O(L). בכל סיבוב של הלולאה – מעבר למציאת max ועוד removeLastLong, שהיא O(L) (סעיף א) ⇒ O(L) לסיבוב. יש לכל היותר L − 1 סיבובים ⇒ O(L²).

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

מה נדרש: למצוא את הרמה של num ואת הרמה של −num, ולהחזיר את ההפרש ביניהן בערך מוחלט (או −1 אם −num לא בעץ).

רעיון: כותבים פעולת עזר רקורסיבית level(t, x) שמחזירה את הרמה של x בעץ t:

num ≠ 0, ולכן num ו־−num הם שני מספרים שונים. levelGap מחשבת את level(t, −num); אם התוצאה −1 מחזירים −1, אחרת מחזירים |level(t, num) − level(t, −num)|. (num מופיע בעץ, ולכן level(t, num) אינו −1.)

פתרון: הקוד המלא – בלשונית Java/C#. הפעולות רק קוראות את העץ (getValue, getLeft, getRight) ולא משנות אותו, ולכן העץ נשמר.

יעילות: level עוברת על כל צומת לכל היותר פעם אחת – O(n). levelGap קוראת לה פעמיים – O(n).

בדיקה (העץ שבשאלה. רמה 0: 5; רמה 1: −8, 3; רמה 2: 1, −5, 12, 8; רמה 3: −12, −1, −6; רמה 4: −3):

מתקבלים 2, 1, 3, 1, −1, והעץ לא משתנה.

טעות נפוצה: להחזיר מ־level את lev + 1 גם כאשר lev == −1 – ואז מספר שלא נמצא מקבל רמה 0 (−1 + 1), כאילו הוא בשורש.

מה נדרש: פער הרמות הגדול ביותר מבין כל הזוגות הנגדיים בעץ, או −1 אם אין זוג כזה.

רעיון: כל זוג נגדי כולל מספר כלשהו שבעץ. לכן עוברים על כל הצמתים, ולכל ערך v מחשבים levelGap(t, v) מסעיף א, ושומרים את המקסימום.
את המעבר על כל הצמתים עושים ברקורסיה (סריקה תחילית). חשוב: את levelGap צריך להפעיל על העץ כולו ולא על תת־העץ הנוכחי – המספר הנגדי יכול להיות בכל מקום בעץ, והרמות נמדדות מהשורש של t. לכן פעולת העזר maxGapFrom מקבלת שתי הפניות: root – שורש העץ כולו (לא משתנה), ו־node – הצומת הנוכחי בסריקה.

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

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

יעילות: לכל אחד מ־n הצמתים יש קריאה ל־levelGap שעולה O(n), ולכן הפעולה היא O(n²).

בדיקה: בעץ שבשאלה הפערים הם 2, 1, 1, 1 ו־3, ולשאר המספרים (−6) −1. התקבל 3. מקרים נוספים: עץ עם צומת אחד ⇒ −1; עץ ששורשו 1 ובניו 2 ו־−2 ⇒ 0; עץ ששורשו 7 ובנו השמאלי −7 ⇒ 1; העץ שבשאלה בלי הצומת −3 ⇒ 2.

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

מה נדרש: למצוא דרך מ־ A ל־ H שסכום זמני הגלישה ועוד זמני העצירה בתחנות הביניים בה מינימלי.

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

פתרון: הדרכים המהירות ביותר מ־ A ל־ H (זמן = גלישה + עצירות בתחנות הביניים):

הדרך המהירה ביותר: A → C → E → F → H , 23 דקות.

בדיקה: יש 11 דרכים מ־ A ל־ H ; המינימום 23 מתקבל רק בדרך זו.

טעות נפוצה: לכלול בזמן את העצירה ב־ A (3) או ב־ H (2), או להתעלם מזמני העצירה ולחפש רק את סכום זמני הגלישה הקטן (אז נבחרת דרך כמו A → B → D → G → H , עם 12 דקות גלישה בלבד, שזמנה האמיתי 25).

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

רעיון:

פתרון:

FastestWay(SKI, K₁, K₂):
    // שלב 1: בניית גרף מכוון ממושקל
    לכל תחנה – קודקוד
    לכל מסלול גלישה מ־u אל v – קשת u → v שמשקלה slope(u, v) + stop(v)
    // שלב 2: מיון טופולוגי (הגרף ללא מעגלים)
    order ← מיון טופולוגי של הקודקודים
    // שלב 3: מסלולים קלים בגמ"ל
    לכל קודקוד v:  d[v] ← ∞ ;  π[v] ← null
    d[K₁] ← 0
    לכל קודקוד u לפי הסדר ב־order:
        אם d[u] ≠ ∞:
            לכל קשת u → v שמשקלה w:
                אם d[u] + w < d[v]:
                    d[v] ← d[u] + w ;  π[v] ← u
    אם d[K₂] = ∞:  החזר "אין דרך"
    // שלב 4: שחזור הדרך והזמן
    way ← רשימה ריקה ;  x ← K₂
    כל עוד x ≠ null:
        הוסף את x לתחילת way ;  x ← π[x]
    החזר את way ואת הזמן d[K₂] − stop(K₂)

המיון הטופולוגי – לפי דרגות כניסה (כל פעם מוציאים קודקוד שדרגת הכניסה שלו 0) או לפי DFS (סדר יורד של זמני סיום). כשמעבדים את u לפי הסדר, כל הקשתות שנכנסות ל־ u כבר טופלו, ולכן d[u] כבר סופי.

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

בדיקה: על האתר SKI עם K₁ = A , K₂ = H . סדר טופולוגי: A , B , C , D , E , F , G , H . משקלי הקשתות (גלישה + עצירה ביעד) בסוגריים; בעמודות – d בסוף כל צעד ובסוגריים π:

d[H] = 25 , ולכן הזמן הוא 25 − stop(H) = 25 − 2 = 23 . שחזור: H ← F ← E ← C ← A , כלומר A → C → E → F → H – כמו בסעיף א.

טעות נפוצה: לשכוח להחסיר את stop(K₂) בסוף, או לשים את זמן העצירה על הקשת היוצאת מהתחנה בלי לטפל בתחנת המוצא (אז העצירה ב־ K₁ נספרת בטעות).

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

רעיון: אותם קודקודים ואותם חצים; על כל קשת u → v רושמים slope(u, v) + stop(v). זמני העצירה כבר אינם רשומים ליד התחנות – הם "נכנסו" למשקלי הקשתות.

פתרון:

בדיקה: משקל הדרך A → B → D → G → H בגרף הוא 7 + 8 + 7 + 5 = 27 = 25 + stop(H) , כלומר הזמן מהדוגמה ועוד 2 . לכל 11 הדרכים מ־ A ל־ H : משקל בגרף − 2 = הזמן האמיתי.

מה נדרש: להשלים לכל צומת את רשימת שכניו, מן הקטן אל הגדול.

רעיון: עוברים על רשימת הקשתות E . כל קשת (X – Y) מוסיפה את Y לשכני X ואת X לשכני Y .

פתרון:

בדיקה: סכום הדרגות 2 + 3 + 3 + 2 + 4 + 3 + 3 = 20 = 2·10 , פעמיים מספר הקשתות, כנדרש.

מה נדרש: להריץ את TwoColors צעד אחר צעד ולרשום אחרי כל איטרציה את התור, את U ואת שני המערכים.

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

פתרון:

בשורה האחרונה U = 5 , ובזמן הבדיקה של השכן 6 נמצא ש־ color[6] = color[5] = 0 , ולכן האלגוריתם עוצר (בתור נשארו 6 ו־ 7).

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

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

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

רעיון: הרשימה מתחילה ב־ M = 6 , ואחריו U = 5 , ומשם עולים במערך parent עד צומת שאין לו הורה.

פתרון: 6 , 5 ⇐ parent[5] = 2 ⇐ parent[2] = 1 ⇐ parent[1] ריק (עצירה).
הרשימה: 6 , 5 , 2 , 1 .

הערה: מכאן אפשר לראות שהגרף אינו דו־צדדי. נמשיך מן הצומת 6 במערך parent : parent[6] = 3 , parent[3] = 1 . יחד עם הקשת 5–6 מתקבל המעגל 1–2–5–6–3–1 , שיש בו 5 קשתות – מעגל באורך אי־זוגי.

בדיקה: התוצאה: [6, 5, 2, 1].

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

רעיון – האלגוריתם של דייקסטרה: d[v] – אורך המסלול הקל ביותר שנמצא עד כה מ־ vⱼ אל v ; π[v] – הקודקוד שלפני v במסלול; P – הקודקודים הקבועים, T – הזמניים. בכל איטרציה מעבירים ל־P את הקודקוד מ־T בעל d הקטן ביותר (בלי משקלים שליליים אי אפשר להגיע אליו בדרך קלה יותר), ומרפים את הקשתות היוצאות ממנו. את מספר הקשתות e[v] מעדכנים יחד עם π: אם המסלול הטוב ביותר אל v עובר עכשיו דרך u , אז יש בו קשת אחת יותר מבמסלול אל u .

פתרון:

DijkstraEdges(G, w, vⱼ):
    לכל קודקוד v ב־V:   d[v] ← ∞ ;  π[v] ← NIL ;  e[v] ← 0
    d[vⱼ] ← 0
    P ← ∅ ;  T ← V
    כל עוד T ≠ ∅:
        u ← הקודקוד ב־T שעבורו d[u] מינימלי
        T ← T − {u} ;  P ← P ∪ {u}
        לכל קשת יוצאת (u, v) כך ש־ v ∈ T:
            אם d[u] + w(u, v) < d[v]:
                d[v] ← d[u] + w(u, v)
                π[v] ← u
                e[v] ← e[u] + 1
    החזר את d , π ו־ e

בסיום d[v] הוא משקל המסלול הקל ביותר, המסלול עצמו מתקבל בהליכה לאחור v, π[v], π[π[v]], … עד vⱼ , ו־ e[v] הוא מספר הקשתות בו. אם d[v] = ∞ – אין מסלול מ־ vⱼ אל v .
(בגרף מכוון עוברים רק על הקשתות היוצאות מ־ u ; קשת הנכנסת ל־ u אינה מאפשרת לצאת ממנו.)

בדיקה: המעקב על G מ־A מופיע בסעיף ב(1). בסוף האלגוריתם: e[B] = 1, e[D] = 1, e[C] = 2, e[G] = 2, e[F] = 3, e[E] = 4, e[H] = 5 – בדיוק מספר הקשתות במסלולים שבטבלה שם. שימו לב: אל H המסלול הקל ביותר (18) עובר ב־5 קשתות, אף שיש מסלול A → B → E → H עם 3 קשתות בלבד (משקלו 20).

מה נדרש: זמן הריצה של האלגוריתם מסעיף א(1) כפונקציה של n (ומספר הקשתות |E|).

פתרון (מימוש פשוט – d ו־π במערכים, הגרף ברשימות שכנויות):

לכן זמן הריצה הוא O(n²).

(הערה: אם שומרים את T בערימת מינימום, זמן הריצה O((n + |E|)·log n) – טוב יותר בגרף דליל.)

מה נדרש: להריץ את דייקסטרה מ־A על G ולהראות בכל איטרציה את P, T ואת d/π של כל קודקוד.

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

פתרון – טבלת המעקב (בכל תא: d/π; מודגש – הקודקוד שנקבע באיטרציה):

פירוט ההרפיות:

המסלולים הקלים ביותר מ־A:

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

טעות נפוצה: להתייחס לגרף כלא מכוון – למשל להשתמש בקשת E → B כאילו אפשר לעבור בה מ־B אל E במשקל 2. מ־B אל E יש רק את הקשת B → E במשקל 13.

מה נדרש: לשרטט את העץ שנוצר מקשתות ההורה π.

רעיון: לכל קודקוד v ≠ A מוסיפים את הקשת π[v] → v . מתקבלות n − 1 = 7 קשתות היוצרות עץ ששורשו A , ומכל קודקוד יש בו מסלול מכוון יחיד מ־A.

פתרון: לפי השורה האחרונה בטבלה מסעיף ב(1): π[B] = A, π[D] = A, π[C] = D, π[G] = D, π[F] = C, π[E] = F, π[H] = E.

ובצורת עץ:

A
├── B   (4)
└── D   (9)
    ├── C   (11)
    │   └── F   (14)
    │       └── E   (15)
    │           └── H   (18)
    └── G   (16)

בדיקה: סכום המשקלים על המסלול מהשורש לכל קודקוד בעץ שווה ל־ d שלו (למשל A → D → C → F → E → H: 9 + 2 + 3 + 1 + 3 = 18).

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

רעיון: בכל שפה צריך להשוות את n (מספר ה־a לפני ה־b) ל־m (מספר ה־a אחריו). השאלה היא אם ההשוואה דורשת לזכור מספר לא חסום.

פתרון:

בדיקה: ב־L₃ כל המילים עם n, m < 100; ב־L₁ אין מילה עם m ≥ 30; ב־L₂ הרישות aⁿ b (n > 30) נבדלות זו מזו.

טעות נפוצה: לחשוב ש־L₁ אינה רגולרית "כי n אינו חסום". n לא חסום, אבל כדי להשוות אותו ל־m < 30 מספיק לדעת אם n קטן מ־30 ואם כן – מה ערכו.

מה נדרש: לקבוע רגולריות של L₄, L₅, L₆ (R(L) = השפה ההפוכה: כל מילה נכתבת מהסוף להתחלה).

פתרון:

בדיקה: L₄ = {n ≥ m , m ≠ 30} , L₄ ∩ {m > 30} = L₂ , L₅ = {n = m > 30} , ו־L₂ ∩ L₃ ריקה.

טעות נפוצה: לומר ש־L₄ רגולרית "כי L₁ רגולרית" – איחוד של שפה רגולרית עם שפה לא רגולרית יכול לצאת לא רגולרי; צריך לבדוק את השפה שמתקבלת.

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

רעיון: המילה מתפרקת באופן יחיד: רצף a (n), רצף b (m), רצף c (k), ואחריו w – שאין בה c. צריך לזכור רק את r = (n + 2m) mod 3 (שלוש אפשרויות) ואת השלב: כל a מוסיף 1 לסכום, וכל b מוסיף 2. k לא משפיע – רק צריך להיות חיובי.

מצבים מקבלים: C1 ו־C2 (w ריקה מותרת בשארית 1 ו־2), Y, L1, L2. C0 אינו מקבל – בשארית 0 המילה w חייבת להתחיל ב־a ולכן אינה ריקה.

פתרון: מצב התחלה: S. מצבים מקבלים: C1, C2, Y, L1, L2.

("–" = אין מעבר, המילה נדחית.)

בדיקה:

(abc: n + 2m = 3 , שארית 0, w ריקה – נדחית; abbc: 1 + 4 = 5 , שארית 2 – מתקבלת; aabbcab: 2 + 4 = 6 , שארית 0, w = ab מתחילה ב־a – מתקבלת.)

מה נדרש: לבדוק חמש מילים מול הגדרת L.

רעיון: כל המילים הן מהצורה aⁿ bᵐ cᵏ. מחשבים n, m, k, בודקים את זוגיות n ומפעילים את התנאי המתאים.

פתרון:

בדיקה: לפי הגדרת השפה: abcc ✓, aabb ✗, aaaccc ✓, aabbbbcc ✓, aaabcc ✗ – וכך גם האוטומט מסעיף ג.

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

פתרון:

בדיקה: בין המילים עד אורך 8: המילה הקצרה ביותר עם n זוגי – aabbbc בלבד; עם n אי־זוגי – ac בלבד.

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

רעיון: המעברים בין q₀ ל־q₁ נתונים: ה־a הראשון דוחף S , וכל a נוסף דוחף A. אחרי n אותיות a המחסנית היא S A…A (ראש המחסנית מימין) – בדיוק n סימנים – והאוטומט ב־q₀ אם n זוגי וב־q₁ אם n אי־זוגי. (כש־n = 1 ראש המחסנית הוא S ; כש־n ≥ 2 הוא A.)

ענף n זוגי (q₀ → q₂ … q₇ , q₆): צריך m = n + k , כלומר n אותיות b ראשונות "מתאימות" ל־a , ושאר ה־b (יש k כאלה, k ≥ 1) מתאימות ל־c.

ענף n אי־זוגי (q₁ → q₈ , q₉ , q₁₀): צריך k = n + m , כלומר כל c "מוחק" a או b אחד.

פתרון: (ראש המחסנית / פעולה)

מצבים מקבלים: q₆ , q₁₀ .

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

בדיקה:

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

טעות נפוצה: לסמן את q₃ כמקבל (אז aabb , שבה k = 0 , הייתה מתקבלת), או לרשום במעבר 11 רק A – ואז abbccc ודומותיה (n = 1) נדחות.

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

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

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

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

התוצאה: המכונה עצרה במצב q9, ועל הסרט: ⊢ Δ Δ > X Δ Δ …

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

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

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

הסרט בסיום: ⊢ Δ Δ = X X Δ … – שני המספרים שווים.

בדיקה: עבור 11#11 המכונה עוצרת במצב q9 והסרט הוא ⊢ΔΔ=XX.

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

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

פתרון: המכונה משווה בין x ל־ y וכותבת במקום הסימן # את תוצאת ההשוואה: > אם x > y, < אם x < y, = אם x = y. בנוסף, אחדים של המספר השמאלי נמחקו (min(x, y) אחדים, ועוד אחד כש־ x > y), ו־ min(x, y) אחדים של המספר הימני הפכו ל־ X.

בדיקה: לכל הזוגות הקטנים של x, y נכתב בתא של # הסימן הנכון והמכונה עוצרת ב־ q9 (למשל 11#1 → >, 11#11 → =, 1#11 → <).

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

פתרון:

מקרה 1 – x = 0, y > 0: המכונה פועלת נכון.
q0 קורא מיד # ⇒ q5 עובר ימינה וקורא 1 (אין X, כי לא היו סיבובים) ⇒ q7 זז שמאלה אל # וכותב בו <. 0 < y ✓.
דוגמה: קלט ⊢ # 1 1 Δ … ⇒ פלט ⊢ < 1 1 Δ …

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

מקרה 3 – x = 0, y = 0: המכונה פועלת נכון.
q0 קורא # ⇒ q5 קורא Δ ⇒ q8 זז שמאלה אל # וכותב בו =.
דוגמה: קלט ⊢ # Δ … ⇒ פלט ⊢ = Δ …

בכל שלושת המקרים המכונה מגיעה למצב העצירה q9 עם תוצאת ההשוואה הנכונה: הסימן נקבע רק לפי הבדיקה שמגלה שמספר נגמר (q0 קורא #, או q2 / q5 קוראים Δ), ובכל המקרים הראש חוזר משם אל התא של # בלי לצאת מגבולות הסרט.

בדיקה: x=0,y=2 → ⊢<11 (q9); x=2,y=0 → ⊢Δ1> (q9); x=y=0 → ⊢= (q9).

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

רעיון

פתרון

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

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

public class Shipment {
    private String code;        // קוד המשלוח
    private double weight;      // משקל המשלוח בק"ג
    private Address address;    // כתובת היעד
}

בדיקה – המחלקה (יחד עם Address) תקינה ב־Java וב־C#; בגרסה המלאה (סעיפים ב–ג) נוספות לה פעולה בונה ופעולות get.

טעות נפוצה: לכתוב ב־Shipment גם את fragile או registered – תכונות אלה שייכות רק לסוג משלוח אחד; או לשכוח שהכתובת היא עצם מטיפוס Address (ולא מחרוזת).

מה נדרש – לעבור על כל המשלוחים במחסן ולהחזיר מערך Letter בגודל 60 עם המכתבים הרשומים לעיר שבכתובת adr.

רעיון

פתרון – :

public class Depot {
    private Shipment[] arr;

    public Depot(Shipment[] arr) {
        this.arr = arr;
    }

    public Letter[] registeredLetters(Address adr) {
        Letter[] result = new Letter[60];
        int k = 0;
        for (int i = 0; i < this.arr.length; i++) {
            if (this.arr[i] instanceof Letter) {
                Letter let = (Letter) this.arr[i];
                if (let.getRegistered() && let.getAddress().sameCity(adr)) {
                    result[k] = let;
                    k++;
                }
            }
        }
        return result;
    }
}

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

בדיקה – מחסן עם 3,000 משלוחים (מכתבים רשומים ולא רשומים, חבילות ומשטחים, בשלוש ערים), ובו בדיוק 60 מכתבים רשומים לחיפה: הפעולה החזירה 60 מכתבים, כולם רשומים, כולם לחיפה ואף אחד מהם אינו null (Java ו־C#).

טעות נפוצה: לזמן arr[i].getRegistered() בלי בדיקת טיפוס והמרה – זו שגיאת הידור, כי ל־Shipment אין פעולה כזאת; או להמיר (Letter) arr[i] לפני הבדיקה – אם העצם הוא חבילה, תתקבל שגיאת ריצה.

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

רעיון – פולימורפיזם (דריסה):

פתרון – Java (הפעולה ב־Shipment, ב־Parcel וב־Pallet):

public class Shipment {
    private String code;        // קוד המשלוח
    private double weight;      // משקל המשלוח בק"ג
    private Address address;    // כתובת היעד

    public Shipment(String code, double weight, Address address) {
        this.code = code;
        this.weight = weight;
        this.address = address;
    }
    public String getCode() { return code; }
    public double getWeight() { return weight; }
    public Address getAddress() { return address; }

    public boolean needsCare() {
        return false;
    }
}

public class Parcel extends Shipment {
    private boolean fragile;

    public Parcel(String code, double weight, Address address, boolean fragile) {
        super(code, weight, address);
        this.fragile = fragile;
    }
    public boolean getFragile() { return fragile; }

    public boolean needsCare() {
        return this.fragile;
    }
}

public class Pallet extends Shipment {
    private double[] boxWeights;

    public Pallet(String code, double weight, Address address, double[] boxWeights) {
        super(code, weight, address);
        this.boxWeights = boxWeights;
    }
    public double[] getBoxWeights() { return boxWeights; }

    public boolean needsCare() {
        for (int i = 0; i < this.boxWeights.length; i++) {
            if (this.boxWeights[i] > 30) {
                return true;
            }
        }
        return false;
    }
}

הפעולות שנוספו: needsCare במחלקה Shipment (מחזירה false), דריסה של needsCare במחלקה Parcel ודריסה של needsCare במחלקה Pallet. במחלקה Letter לא נוספה פעולה.

בדיקה – חבילה שבירה → true; חבילה לא שבירה → false; מכתב → false; משטח עם ארגזים {12.5, 30} → false (30 אינו גדול מ־30); משטח עם {12.5, 30.5, 4} → true.

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

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

רעיון

השורה 20 of 3 (בלי טקסט) היא עצם Card. היא לא יכולה להיות new Card(20): אז made היה גדל רק פעמיים (בשורות 1 ו־5), השורה (5) הייתה Hi: 20 וכל השורות היו מסתיימות ב־of 2. גם Wow: ... חייבת להיות Wish – new Gift("Wow") לא מדפיסה כוכביות.

פתרון – השורות החסרות (זהות ב־Java וב־C#):

arr[0] = new Gift();         // (1)
arr[1] = new Wish(3);        // (2)
arr[2] = new Card();         // (3)
arr[3] = new Gift("Bye");    // (4)
arr[4] = new Gift();         // (5)
arr[5] = new Wish(5);        // (6)

התוכנית המלאה בלשונית Java/C#.

בדיקה – הפלט ב־Java וב־C# הוא בדיוק הפלט הנדרש:

Hi: 10 of 3
Wow: 7 of 3 3*
20 of 3
Bye: 7 of 3
Hi: 30 of 3
Wow: 7 of 3 5*

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

טעות נפוצה: לחשוב שבשורה (1) יודפס Hi: 10 of 1 – made סטטית, וההדפסה מתבצעת רק אחרי שכל העצמים נוצרו. טעות נוספת: לחשוב ש־Wish מגדילה את made – היא עוברת דרך Gift(String) ← Card(int).

מה נדרש – לקבוע אם Wish שיורשת ישירות מ־Card גורמת לשגיאה, ולהסביר.

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

פתרון – כן, השינוי גורם לשגיאת הידור בפעולה הבונה של Wish: הקריאה super("Wow") מחפשת פעולה בונה של Card עם פרמטר מסוג מחרוזת, ואין כזו (הפעולה Gift(String t) כבר אינה מחלקת הבסיס של Wish). התוכנית לא תעבור הידור ולכן לא תרוץ ולא יודפס דבר.

בדיקה – הידור של הגרסה ששונתה נכשל בשתי השפות:

טעות נפוצה: לחשוב שהבעיה היא ב־super.toString() או ב־Card[] arr, או לענות שאין שגיאה ולחשב פלט – הפעולה הבונה של Wish היא הבעיה.

מה נדרש – כותרת המחלקה Order ושלוש התכונות שלה.

רעיון – המערך צריך להכיל גם עצמי Guitar וגם עצמי Piano, ולכן טיפוס האיברים שלו הוא מחלקת־העל המשותפת – Instrument (הפניה מטיפוס מחלקת־על יכולה להפנות לעצם של מחלקה יורשת).

פתרון – :

public class Order {
    private String customer;      // שם הלקוח
    private Instrument[] items;   // הכלים בהזמנה – גיטרות ופסנתרים
    private int num;              // מספר הכלים הנוכחי בהזמנה
}

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

טעות נפוצה: להגדיר שני מערכים נפרדים (Guitar[] ו־Piano[]) – השאלה מבקשת מערך אחד המכיל את שני הסוגים.

מה נדרש – תרשים הייררכייה של Instrument , Guitar , Piano , Order.

רעיון

פתרון

בדיקה – התרשים מתאים לקוד: Guitar extends Instrument, Piano extends Instrument, ובמחלקה Order התכונה Instrument[] items.

מה נדרש – תרשים מעודכן אחרי הוספת Item ו־SheetMusic.

רעיון

פתרון

בדיקה – הקוד המעודכן (סעיף ב(3)) תקין, ומערך מטיפוס Item יכול לקבל עצמי Guitar , Piano ו־SheetMusic.

טעות נפוצה: לחבר את Guitar ו־Piano ישירות ל־Item ולמחוק את Instrument – אז התכונות brand ו־year היו צריכות להופיע פעמיים.

מה נדרש – כותרת Item ותכונותיה.

רעיון – מעבירים ל־Item רק את התכונות שמשותפות לכל הפריטים: code ו־price מופיעות גם ב־Instrument וגם ב־SheetMusic. brand ו־year שייכות רק לכלי נגינה, ו־title ו־composer רק לחוברת תווים.

פתרון – :

public class Item {
    private int code;          // קוד המוצר
    private double price;      // מחיר
}

בדיקה – המחלקה תקינה ב־Java וב־C# יחד עם שאר המחלקות המעודכנות.

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

רעיון

פתרון – :

public class Instrument extends Item {
    private String brand;      // שם היצרן
    private int year;          // שנת הייצור
}

public class SheetMusic extends Item {
    private String title;      // שם היצירה
    private String composer;   // שם המלחין
}

public class Order {
    private String customer;   // שם הלקוח
    private Item[] items;      // הפריטים בהזמנה
    private int num;           // מספר הפריטים הנוכחי בהזמנה
}

בדיקה – כל המחלקות (כולל Guitar ו־Piano ללא שינוי) תקינות, והשמה של new Guitar(), new Piano() ו־new SheetMusic() למערך מטיפוס Item תקינה (Java ו־C#).

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

מה נדרש – getFinalPrice ב־Item ודריסה במקום המתאים, בלי instanceof (ב־C#: בלי is/as).

רעיון

פתרון – :

public class Item {
    private int code;          // קוד המוצר
    private double price;      // מחיר

    public Item(int code, double price) {
        this.code = code;
        this.price = price;
    }
    public int getCode() { return code; }
    public double getPrice() { return price; }

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

public class Piano extends Instrument {
    private boolean electric;  // האם הפסנתר חשמלי

    public Piano(int code, double price, String brand, int year, boolean electric) {
        super(code, price, brand, year);
        this.electric = electric;
    }

    public double getFinalPrice() {
        return super.getFinalPrice() + 150;
    }
}

הפעולות שנוספו: getFinalPrice במחלקה Item, ודריסה של getFinalPrice במחלקה Piano.

בדיקה – גיטרה במחיר 1000 → 800; פסנתר במחיר 5000 → 4150; פסנתר חשמלי במחיר 2500 → 2150; תווים במחיר 60 → 48 (Java ו־C#).

טעות נפוצה: לכתוב ב־Piano price * 0.8 + 150 – price פרטית ב־Item ולכן זו שגיאת הידור; וגם אם הייתה נגישה, שכפול החישוב סותר את עקרון השימוש החוזר. הדרך הנכונה: super.getFinalPrice() + 150.