דילוג לתוכן המרכזי
GuyAI

בגרות במדעי המחשב מבני נתונים ומסלול 899271 - קיץ 2024

4–5 יח"ל · שאלון 899271 · 14 שאלות · 3:30 שעות · פתרון מלא לכל סעיף

בחינת הבגרות במדעי המחשב, מבני נתונים ומסלול, קיץ 2024, כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה ופתרון מלא: הרעיון, הקוד או המעקב, ובדיקה קצרה. כל קוד מופיע ב-Java וב-C#. נסו לפתור לבד, ואז פתחו את הפתרון.

הוראות הבחינה (כמו בשאלון)

א. משך הבחינה: שלוש שעות וחצי.

ב. מבנה השאלון ומפתח ההערכה: בשאלון זה שני פרקים.
יש לבחור בארבע שאלות סך הכול. לכל שאלה – 25 נקודות; סך הכול – 100 נקודות.
שימו לב: אם תבחרו לענות על שאלות מן הפרק השני, בחרו בשאלות מתוך מסלול אחד בלבד.

ג. חומר עזר מותר בשימוש: כל חומר עזר, חוץ ממחשבון שיש בו אפשרות תכנות.

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

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

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

בהצלחה!

השאלות

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

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

לפותרים בשפת Java: בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner input = new Scanner (System.in);

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

פרק ראשון

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

שאלה 1 · איבר קסם בתור (25 נקודות)

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

א.

כתבו פעולה ששמה isMagic בשפת Java או IsMagic בשפת C#, המקבלת תור – q מטיפוס שלם, ומספר שלם – m הגדול מ־ 0 וקטן או שווה לגודל התור.
הפעולה תחזיר true אם האיבר במקום ה־ m בתור הוא "איבר קסם", אחרת היא תחזיר false.

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

לדוגמה: עבור התור שלפניכם:

עבור m = 1 הפעולה תחזיר false (המספר הראשון בתור אינו "איבר קסם")
עבור m = 2 הפעולה תחזיר true (5 + 6 = 11)
עבור m = 3 הפעולה תחזיר false (11 + 9 ≠ 6)

ב.

כתבו פעולה ששמה nMagic בשפת Java או NMagic בשפת C# המקבלת תור מטיפוס שלם – q , ומספר שלם n הגדול מ־ 0 וקטן או שווה לגודל התור.
הפעולה תחזיר true אם כל האיברים הנמצאים במקומות שהם כפולה של n (המקום ה־ n בתור, המקום ה־ 2n בתור וכן הלאה בדילוגים של n מקומות) הם "איברי קסם". אחרת הפעולה תחזיר false.
אפשר להשתמש בפעולה שכתבתם בסעיף א.

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

דוגמאות: עבור התור שבדוגמה שלעיל:
עבור n = 2 הפעולה תחזיר true מכיוון שכל האיברים הנמצאים במקומות שהם כפולה של 2 (2, 4, 6) הם "איברי קסם".
עבור n = 4 הפעולה תחזיר true מכיוון שהאיבר במקום ה־ 4 הוא "איבר קסם" (אין בתור איברים נוספים במקומות שהם כפולה של 4).
עבור n = 3 הפעולה תחזיר false מכיוון שהאיבר במקום ה־ 3 אינו "איבר קסם".

◂ פתרון מלא לשאלה 1

סעיף א

תשובה

מעבירים את כל איברי התור לתור עזר תוך ספירת המקום; שומרים את האיבר במקום m−1 ואת האיבר במקום m, וכשמגיעים למקום m+1 בודקים before + x == cur (רק אם m > 1). בסוף מחזירים את האיברים לתור. אם m = 1 או m הוא המקום האחרון – false.

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

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

•כשמגיעים למקום m−1 שומרים את הערך ב־before.
•כשמגיעים למקום m שומרים את הערך ב־cur.
•כשמגיעים למקום m+1 (הערך x) בודקים אם before + x == cur.

שני מקרי הקצה מטופלים מעצמם:

•אם m = 1 – אין איבר לפניו. התנאי m > 1 מונע את הבדיקה, והתשובה נשארת false.
•אם m הוא המקום האחרון – לעולם לא מגיעים למקום m+1, והתשובה נשארת false.

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

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

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

בדיקה (התור 5, 11, 6, 9, 3, 6, 3):

mbeforecurאחריובדיקהתוצאה
1–511m = 1false
251165 + 6 = 11true
3116911 + 9 = 20 ≠ 6false
763–אין איבר אחריוfalse

לכל m = 1..7 מתקבלים הערכים false, true, false, true, false, true, false, ואחרי כל קריאה התור נשאר 5, 11, 6, 9, 3, 6, 3.

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

הקוד המלא
// סעיף א: האם האיבר במקום ה-m בתור הוא "איבר קסם". התור נשמר.
public static boolean isMagic(Queue<Integer> q, int m)
{
    Queue<Integer> temp = new Queue<Integer>();
    int pos = 0;            // מקום האיבר הנוכחי בתור
    int before = 0;         // האיבר במקום m-1
    int cur = 0;            // האיבר במקום m
    boolean magic = false;
    while (!q.isEmpty())
    {
        int x = q.remove();
        pos++;
        if (pos == m - 1)
            before = x;
        else if (pos == m)
            cur = x;
        else if (pos == m + 1 && m > 1)
            magic = (before + x == cur);
        temp.insert(x);
    }
    while (!temp.isEmpty())          // החזרת התור למצבו המקורי
        q.insert(temp.remove());
    return magic;
}

סעיף ב

תשובה

סופרים את גודל התור (ומחזירים את האיברים לתור), ואז בודקים isMagic(q, m) לכל m = n, 2n, 3n, … ≤ גודל התור. אם אחד מהם אינו איבר קסם – false, אחרת true.

מה נדרש: לבדוק אם כל האיברים במקומות n, 2n, 3n, … הם "איברי קסם".

רעיון:

1.סופרים את מספר האיברים בתור (size): מעבירים את האיברים לתור עזר תוך כדי ספירה, ואחר כך מחזירים אותם.
2.בלולאה עם קפיצות של n, m = n, 2n, 3n, … כל עוד m ≤ size, מפעילים את isMagic מסעיף א. הפעולה isMagic שומרת על התור, ולכן אפשר להפעיל אותה שוב ושוב על אותו התור.
3.ברגע שנמצא מקום שאינו "איבר קסם" מחזירים false. אם הלולאה הסתיימה, כל המקומות תקינים ומחזירים true.

בגלל ש־n ≤ גודל התור, הלולאה מתבצעת לפחות פעם אחת. אם size הוא כפולה של n, המקום האחרון נבדק, ו־isMagic מחזירה עליו false (האחרון אינו איבר קסם), כמו שנדרש.

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

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

בדיקה (התור 5, 11, 6, 9, 3, 6, 3, גודל 7):

•n = 2: נבדקים המקומות 2, 4, 6: 5+6=11 ✓, 6+3=9 ✓, 3+3=6 ✓ ⇒ true.
•n = 4: נבדק רק המקום 4: 6+3=9 ✓ ⇒ true.
•n = 3: המקום 3: 11+9 ≠ 6 ⇒ false.

מתקבל true, true, false בהתאמה. בבדיקות נוספות: n = 1 ⇒ false (המקום הראשון אינו איבר קסם), n = 7 ⇒ false (המקום האחרון), n = 5 ⇒ false.

הקוד המלא
// סעיף ב: האם כל האיברים במקומות n, 2n, 3n, ... הם "איברי קסם"
public static boolean nMagic(Queue<Integer> q, int n)
{
    // ספירת איברי התור (והחזרתם לתור)
    Queue<Integer> temp = new Queue<Integer>();
    int size = 0;
    while (!q.isEmpty())
    {
        temp.insert(q.remove());
        size++;
    }
    while (!temp.isEmpty())
        q.insert(temp.remove());

    for (int m = n; m <= size; m = m + n)
    {
        if (!isMagic(q, m))
            return false;
    }
    return true;
}

שאלה 2 · תור עדיפויות בחדר מיון (25 נקודות)

נתונה המחלקה Patient – חולה בחדר מיון, ולה שתי תכונות:

•id – מספר הזהות של החולה, מטיפוס שלם
•priority – רמת הדחיפות של הטיפול בחולה. רמת הדחיפות מיוצגת במספר מטיפוס שלם בין 1 ל־ 10. ככל שהמספר גבוה יותר, רמת הדחיפות גבוהה יותר.

הניחו שלתכונות המחלקה יש פעולות get/Get ו־ set/Set.

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

כדי לשמור על סדר הטיפול נבנתה המחלקה PriorQueue – תור עדיפויות, ולה תכונה אחת:

•q – הפניה לתור, מטיפוס Patient

דוגמה לתור q:

הניחו שהחולים שרמת הדחיפות שלהם זהה מוצגים בדוגמה לפי סדר הגעתם לחדר המיון.

א.

ממשו את הפעולה שלפניכם השייכת לממשק המחלקה PriorQueue :

Java – public void priorityInsert (Patient p)
C# – public void PriorityInsert (Patient p)

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

לדוגמה: עבור התור המוצג לעיל והעצם שלפניכם:

התור ייראה כך לאחר ההכנסה:

ב.

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

Java – public void update (int id, int pri)
C# – public void Update (int id, int pri)

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

◂ פתרון מלא לשאלה 2

סעיף א

תשובה

מעבירים את q לתור עזר. לפני החולה הראשון שרמת הדחיפות שלו נמוכה ממש מזו של p מכניסים את p. אם אין חולה כזה, p נכנס בסוף. אחר כך מחזירים את כל האיברים מתור העזר ל־q.

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

רעיון: התור תמיד ממוין לפי כללי חדר המיון. החולה החדש הגיע אחרון, ולכן הוא צריך לעמוד:

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

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

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

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

בדיקה: בתור 7, 7, 6, 4, 4, 4 (הדחיפויות) מכניסים את 11210 עם דחיפות 6. החולים 13893 (7), 28834 (7) ו־72890 (6) עוברים לתור העזר. החולה 12223 (4) הוא הראשון עם דחיפות נמוכה מ־6, ולכן לפניו מוכנס 11210. מתקבל:
13893/7, 28834/7, 72890/6, 11210/6, 12223/4, 13335/4, 33800/4, בדיוק כמו באיור. נבדקו גם הכנסה לתור ריק, הכנסת חולה בדחיפות 1 (נכנס לסוף) והכנסת חולה בדחיפות 10 (נכנס לראש התור).

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

הקוד המלא
public void priorityInsert(Patient p)
{
    Queue<Patient> temp = new Queue<Patient>();
    boolean inserted = false;
    while (!q.isEmpty())
    {
        Patient cur = q.remove();
        // p נכנס לפני החולה הראשון שרמת הדחיפות שלו נמוכה משלו
        if (!inserted && cur.getPriority() < p.getPriority())
        {
            temp.insert(p);
            inserted = true;
        }
        temp.insert(cur);
    }
    if (!inserted)            // אין חולה עם דחיפות נמוכה יותר – p בסוף התור
        temp.insert(p);
    while (!temp.isEmpty())   // העברה חזרה לתור q
        q.insert(temp.remove());
}

סעיף ב

תשובה

מוציאים את החולה עם מספר הזהות id מהתור (שאר החולים נשארים באותו סדר), מעדכנים את רמת הדחיפות שלו: setPriority(pri), ומכניסים אותו מחדש עם priorityInsert מסעיף א.

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

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

1.הוצאה: מעבירים את כל החולים מ־q לתור עזר, חוץ מהחולה שמספר הזהות שלו id. אותו שומרים במשתנה found. אחר כך מחזירים את תור העזר ל־q. עכשיו q מכיל את כל שאר החולים באותו סדר, והוא עדיין ממוין.
2.הכנסה מחדש: מעדכנים found.setPriority(pri) ומפעילים את priorityInsert(found) מסעיף א. הפעולה מכניסה את החולה אחרי כל החולים שרמת הדחיפות שלהם גבוהה מ־pri או שווה לה. זה בדיוק "כאילו הגיע אחריהם", כמו שנדרש.

לפי השאלה החולה נמצא בתור, ולכן found אינו null.

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

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

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

•update(13335, 7) ⇒ 13893/7, 28834/7, 13335/7, 72890/6, 12223/4, 33800/4. החולה הוצב אחרי שני החולים שכבר נמצאים ברמה 7.
•אחר כך update(13893, 4) ⇒ 28834/7, 13335/7, 72890/6, 12223/4, 33800/4, 13893/4. החולה ירד לסוף, אחרי כל החולים ברמה 4.
•update(33800, 4), כלומר עדכון לאותה רמה ⇒ החולה עובר לסוף הקבוצה של רמה 4: …, 13893/4, 33800/4.

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

הקוד המלא
public void update(int id, int pri)
{
    Queue<Patient> temp = new Queue<Patient>();
    Patient found = null;
    while (!q.isEmpty())
    {
        Patient cur = q.remove();
        if (cur.getId() == id)
            found = cur;          // מוציאים את החולה מהתור
        else
            temp.insert(cur);     // שאר החולים נשמרים לפי הסדר
    }
    while (!temp.isEmpty())
        q.insert(temp.remove());
    found.setPriority(pri);
    priorityInsert(found);        // הכנסה מחדש לפי רמת הדחיפות החדשה
}

שאלה 3 · פעולות רקורסיביות על שרשרת חוליות (25 נקודות)

נוסח השאלה:

שימו לב: לשאלה זו שני נוסחים: בשפת Java בעמוד 5 ובשפת C# בעמוד 6.

לפותרים בשפת Java

א.(1)

נתונה הפעולה what :

Java
public static Node<Integer> what (Node<Integer>lst, int x)
{
    if (lst == null)
        return null;
    Node<Integer> temp = what (lst.getNext(),x);
    if (lst.getValue() == x)
        return temp;
    lst.setNext (temp);
    return lst;
}

נתונה שרשרת חוליות – lst מטיפוס שלם:

(1) עקבו אחר הפעולה what (lst, 1) , והציגו את השרשרת שהפעולה מחזירה.

(2)

מה עושה הפעולה what ? הסבירו את תשובתכם.

(3)

מהי סיבוכיות הפעולה what ? נמקו את תשובתכם.

ב.(1)

נתונה הפעולה guess :

Java
public static void guess (Node<Integer>lst)
{
    if (lst != null)  {
        Node<Integer> temp = what (lst.getNext(), lst.getValue());
        lst.setNext (temp);
        guess (lst.getNext());
    }
}

נתונה שרשרת חוליות – lst , מטיפוס שלם:

(1) עקבו אחר הפעולה guess (lst) , והציגו את השרשרת lst בסיום הפעולה.
בסעיף זה אין צורך לעקוב אחר הפעולה what .

(2)

מה עושה הפעולה guess ? הסבירו את תשובתכם.

(3)

מהי סיבוכיות הפעולה guess ? נמקו את תשובתכם.

◂ פתרון מלא לשאלה 3

סעיף א(1)

תשובה

הפעולה מחזירה את השרשרת 3 → 5 → 3 → 9 → 4 → null (שתי החוליות עם הערך 1 הוסרו).

מה נדרש: לעקוב אחר הקריאה what(lst, 1) ולהציג את השרשרת המוחזרת.

רעיון: הפעולה קוראת לעצמה לפני שהיא מטפלת בחוליה הנוכחית. לכן הקריאות יורדות עד סוף השרשרת (lst == null), והטיפול בחוליות מתבצע בדרך חזרה, מהחוליה האחרונה לראשונה. כל קריאה מקבלת ב־temp את השרשרת שכבר "נוקתה" אחריה, ואז:

•אם ערך החוליה שווה ל־x – מחזירה את temp, כלומר מדלגת על החוליה ומוציאה אותה מהשרשרת;
•אחרת – מחברת את החוליה ל־temp (setNext) ומחזירה את החוליה.

פתרון – מעקב (השרשרת 1, 3, 5, 3, 1, 9, 4; x = 1; השורות לפי סדר החזרה מהרקורסיה):

קריאה על חוליהtemp שהתקבל מהקריאה הרקורסיביתערך == 1 ?מוחזר
null––null
4nullלא4
94לא9 → 4
1 (החמישית)9 → 4כן9 → 4
3 (הרביעית)9 → 4לא3 → 9 → 4
53 → 9 → 4לא5 → 3 → 9 → 4
3 (השנייה)5 → 3 → 9 → 4לא3 → 5 → 3 → 9 → 4
1 (הראשונה)3 → 5 → 3 → 9 → 4כן3 → 5 → 3 → 9 → 4

השרשרת המוחזרת: 3 → 5 → 3 → 9 → 4 → null

בדיקה: הקוד מדפיס: 3 -> 5 -> 3 -> 9 -> 4 -> null.

הערה: החוליה הראשונה (1) לא שונתה. המשתנה lst עדיין מפנה אליה, והיא עדיין מצביעה על החוליה 3. לכן צריך להשתמש בערך המוחזר מהפעולה, ולא ב־lst.

סעיף א(2)

תשובה

הפעולה מוחקת מהשרשרת lst את כל החוליות שהערך שלהן שווה ל־x (סדר שאר החוליות נשמר) ומחזירה הפניה לראש השרשרת החדשה (null אם לא נשארו חוליות).

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

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

•תנאי עצירה: שרשרת ריקה – אין מה למחוק, ומחזירים null.
•צעד: temp = what(lst.getNext(), x) מחזיר את המשך השרשרת אחרי שנמחקו ממנו כל ה־x (הנחת האינדוקציה). אם החוליה הנוכחית היא x, מוותרים עליה ומחזירים את temp. אחרת מחברים אותה ל־temp ומחזירים אותה כראש השרשרת.

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

בדיקה: על השרשרת 1, 3, 5, 3, 1, 9, 4:

•what(lst, 3) ⇒ 1 → 5 → 1 → 9 → 4;
•what(lst, 7) ⇒ השרשרת לא השתנתה;
•what על השרשרת 2, 2, 2 עם x = 2 ⇒ null.

סעיף א(3)

תשובה

O(n), כאשר n הוא מספר החוליות בשרשרת: קריאה רקורסיבית אחת לכל חוליה (ועוד אחת ל־null), ובכל קריאה עבודה קבועה.

מה נדרש: סיבוכיות זמן, כאשר n הוא מספר החוליות ב־lst.

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

פתרון: כל קריאה מבצעת קריאה רקורסיבית אחת בלבד, על החוליה הבאה. לכן יש n + 1 קריאות: אחת לכל חוליה ואחת ל־null בסוף. בכל קריאה, מלבד הקריאה הרקורסיבית, יש מספר קבוע של פעולות: השוואה, getValue, setNext ו־return, כלומר O(1).
סה"כ: (n + 1) · O(1) = O(n).

בדיקה: סופרים את הקריאות במעקב. על שרשרות באורך 100, 200, 400, 800, 1600 היו 101, 201, 401, 801, 1601 קריאות, כלומר n + 1, גידול לינארי.

סעיף ב(1)

תשובה

בסיום הפעולה: lst = 1 → 3 → 5 → 9 → 4 → null.

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

רעיון: לפי סעיף א, what(lst.getNext(), lst.getValue()) מוחקת מהמשך השרשרת את כל החוליות שהערך שלהן שווה לערך החוליה הנוכחית. החוליה הנוכחית מחוברת להמשך הנקי, והפעולה ממשיכה רקורסיבית לחוליה הבאה (שכבר שייכת לשרשרת החדשה).

פתרון – מעקב:

קריאה (חוליה נוכחית)מה מוחקים מההמשךlst אחרי הצעד
1כל ה־1 שאחריה (החוליה החמישית)1 → 3 → 5 → 3 → 9 → 4
3כל ה־3 שאחריה (החוליה הרביעית)1 → 3 → 5 → 9 → 4
5אין 5 נוספים1 → 3 → 5 → 9 → 4
9אין 9 נוספים1 → 3 → 5 → 9 → 4
4ההמשך ריק1 → 3 → 5 → 9 → 4
nullהפעולה מסתיימת

בסיום: lst = 1 → 3 → 5 → 9 → 4 → null

בדיקה: הקוד מדפיס 1 -> 3 -> 5 -> 9 -> 4 -> null.
כאן lst עצמו מתאים לתוצאה: החוליה הראשונה אף פעם לא נמחקת, כי what מופעלת רק על ההמשך שלה.

סעיף ב(2)

תשובה

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

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

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

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

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

בדיקה: 1, 3, 5, 3, 1, 9, 4 ⇒ 1, 3, 5, 9, 4. על 4, 4, 2, 4, 2, 7, 2 מתקבל 4, 2, 7.

סעיף ב(3)

תשובה

O(n²), כאשר n הוא מספר החוליות: לכל חוליה מופעלת what על ההמשך שלה, שאורכו עד n−1, n−2, …, 0. הסכום הוא n(n−1)/2.

מה נדרש: סיבוכיות זמן של guess, כאשר n הוא מספר החוליות ב־lst.

רעיון: guess מופעלת פעם אחת על כל חוליה שנשארת בשרשרת. בכל הפעלה יש קריאה ל־what על המשך השרשרת, ולפי סעיף א(3) היא עולה O(אורך ההמשך).

פתרון: המקרה הגרוע הוא שכל הערכים שונים, ואז אף חוליה לא נמחקת. לחוליה הראשונה what עוברת על n−1 חוליות, לשנייה על n−2, וכן הלאה, עד 0 לחוליה האחרונה:
(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2 ⇒ O(n²).
(במקרה הטוב, כשכל הערכים שווים, הקריאה הראשונה ל־what מוחקת את כל ההמשך, והסיבוכיות היא O(n). הסיבוכיות שמבקשים היא של המקרה הגרוע: O(n²).)

בדיקה: סופרים את הקריאות ל־what כש־guess פועלת על שרשרות עם ערכים שונים באורך n = 100, 200, 400, 800, 1600. היו 5050, 20100, 80200, 320400, 1280800 קריאות, כלומר בדיוק n(n+1)/2 (כולל הקריאות על null). כשמכפילים את n, מספר הקריאות גדל פי 4, כמו שמתאים ל־O(n²).

שאלה 4 · תחנות אוטובוס – מערך ושרשרת חוליות (25 נקודות)

נתונה המחלקה BusStation – תחנת אוטובוס, ולה שלוש תכונות:

•num – מספר התחנה, מטיפוס שלם
•arr – מערך מטיפוס שלם בגודל 10 , המכיל את מספרי קווי האוטובוס שעוצרים בתחנה. בתחנה עוצרים עד 10 קווים, והם נשמרים ברצף מתחילת המערך.
•amount – כמות קווי האוטובוס שעוצרים בתחנה בפועל, מטיפוס שלם. בתחנה עוצר קו אוטובוס אחד לפחות.

הניחו שלתכונות המחלקה יש פעולות get/Get ו־ set/Set .

א.

ממשו את הפעולה שלפניכם השייכת לממשק המחלקה BusStation :

Java – public boolean isStopping (int n)
C# – public bool IsStopping (int n)

הפעולה מקבלת מספר קו אוטובוס – n מטיפוס שלם. הפעולה מחזירה true אם קו האוטובוס עוצר בתחנה, ואחרת מחזירה false .

ב.

נתון מערך arr מטיפוס BusStation , ובו כל תחנות האוטובוס בעיר מסוימת. ידוע שכמה מקווי האוטובוס עוצרים בכל אחת מן התחנות בעיר, ושאר הקווים עוצרים רק בחלק מן התחנות.
כתבו פעולה חיצונית ששמה allStations בשפת Java או AllStations בשפת C# , המקבלת את המערך arr .
הפעולה מחזירה שרשרת חוליות מטיפוס שלם שבכל חוליה מופיע אחד ממספרי הקווים שעוצרים בכל התחנות בעיר (כל קו כזה יופיע פעם אחת בלבד בשרשרת).
הערה: אין חשיבות לסדר הקווים בשרשרת.

◂ פתרון מלא לשאלה 4

סעיף א

תשובה

חיפוש סדרתי במערך arr בתאים 0 עד amount−1: אם arr[i] == n מחזירים true. בסוף הלולאה מחזירים false.

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

רעיון: הקווים שמורים ברצף מתחילת המערך, ויש amount קווים. לכן מספיק לחפש בתאים 0 עד amount−1 (חיפוש סדרתי). אסור לחפש בכל 10 התאים: בתאים שאחרי amount יש ערכים שאינם קווים (למשל 0), ואז שאלה כמו isStopping(0) עלולה להחזיר true בטעות.

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

יעילות: O(amount), ולכל היותר 10 בדיקות, כלומר O(1).

בדיקה: תחנה עם הקווים 5, 18, 40, 7 (amount = 4): isStopping(18) ⇒ true, isStopping(7) ⇒ true (התא האחרון בשימוש), isStopping(99) ⇒ false, isStopping(0) ⇒ false (אף שבתאים הריקים יש 0). בתחנה מלאה (10 קווים) isStopping(10) ⇒ true.

הקוד המלא
public boolean isStopping(int n)
{
    for (int i = 0; i < amount; i++)     // הקווים שמורים ברצף בתאים 0 עד amount-1
    {
        if (arr[i] == n)
            return true;
    }
    return false;
}

סעיף ב

תשובה

עוברים על הקווים של התחנה הראשונה arr[0]. לכל קו בודקים בעזרת isStopping אם הוא עוצר בכל שאר התחנות. אם כן – מוסיפים אותו כחוליה חדשה לראש השרשרת. בסוף מחזירים את השרשרת.

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

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

1.עוברים על הקווים של arr[0], בתאים 0 עד getAmount()−1 של המערך שמחזירה getArr().
2.לכל קו line בודקים את שאר התחנות, arr[1] עד arr[arr.length−1], בעזרת isStopping מסעיף א. אם יש תחנה שהקו לא עוצר בה, מפסיקים לבדוק (inAll = false).
3.אם הקו עוצר בכל התחנות, יוצרים חוליה חדשה ומחברים אותה לראש השרשרת: new Node(line, result).

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

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

יעילות: אם יש k תחנות, בודקים לכל היותר 10 קווים, ולכל קו לכל היותר k−1 תחנות × 10 תאים. סה"כ O(k).

בדיקה: ארבע תחנות עם הקווים {5, 18, 40, 7}, {40, 3, 5, 12}, {7, 5, 40, 18, 22}, {40, 5}. המועמדים הם 5, 18, 40, 7. רק 5 ו־40 עוצרים בכל התחנות (18 ו־7 לא עוצרים בתחנה 2). מתקבלת שרשרת עם הערכים 5 ו־40. נבדקו גם מערך עם תחנה אחת (מוחזרים כל הקווים שלה) ושתי תחנות בלי קו משותף (מוחזר null).

טעות נפוצה: לעבור בכל תחנה על כל 10 תאי המערך במקום על amount הראשונים. במקרה כזה ערכי ברירת המחדל (0) נחשבים כקו שעוצר בכל התחנות.

הקוד המלא
public static Node<Integer> allStations(BusStation[] arr)
{
    Node<Integer> result = null;
    int[] lines = arr[0].getArr();             // קו שעוצר בכל התחנות עוצר בפרט בתחנה הראשונה
    for (int i = 0; i < arr[0].getAmount(); i++)
    {
        int line = lines[i];
        boolean inAll = true;
        for (int j = 1; j < arr.length && inAll; j++)
        {
            if (!arr[j].isStopping(line))
                inAll = false;
        }
        if (inAll)
            result = new Node<Integer>(line, result);   // הוספה לראש השרשרת
    }
    return result;
}

שאלה 5 · תת־סדרה נגדית בשרשרת חוליות (25 נקודות)

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

לדוגמה: בסדרת המספרים: 17, 3, 1, −4, 5, 6, 4, −3, 7, 23, −99 יש שתי תת־סדרות נגדיות:

i. 3, 1, −4, 5, 6, 4, −3
ii. −4, 5, 6, 4

נתונה שרשרת חוליות lst מטיפוס שלם, המכילה מספרים חיוביים ושליליים שאינם 0 , וכולם שונים זה מזה (כלומר אין שני מספרים זהים בשרשרת).

א.

כתבו פעולה ששמה width בשפת Java או Width בשפת C# המקבלת את השרשרת lst ומספר שלם num (חיובי או שלילי) המופיע בשרשרת.
הפעולה תחזיר את אורך ה"תת־סדרה נגדית" שהמספר num מתחיל או מסיים (האורך כולל את המספרים בקצוות).
אם המספר הנגדי ל־ num אינו מופיע בשרשרת, הפעולה תחזיר −1 .

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

דוגמאות: עבור השרשרת lst שלפניכם:

עבור num = 9 הפעולה תחזיר 7 (התת־סדרה: −9, −1, 1, 22, 10, −2, 9).
עבור num = −1 הפעולה תחזיר 2 (התת־סדרה: −1, 1).
עבור num = 22 הפעולה תחזיר −1 (משום שהמספר הנגדי לו, −22 , אינו מופיע בשרשרת).

ב.

כתבו פעולה ששמה longest בשפת Java או Longest בשפת C# המקבלת את השרשרת lst . הפעולה תחזיר את אורך ה"תת־סדרה נגדית" הגדולה ביותר. אם אין בשרשרת שום "תת־סדרה נגדית", הפעולה תחזיר −1 .
אפשר להשתמש בפעולה שכתבתם בסעיף א.

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

לדוגמה: עבור השרשרת lst שבדוגמה לעיל הפעולה תחזיר 7 .
הסבר: ה"תת־סדרה נגדית" המתחילה במספר −9 ומסתיימת במספר 9 מכילה שבעה מספרים והיא הגדולה ביותר.

◂ פתרון מלא לשאלה 5

סעיף א

תשובה

עוברים פעם אחת על השרשרת וסופרים מקומות. שומרים את המקום של num (posNum) ואת המקום של −num (posOpp). אם −num לא נמצא – מחזירים −1, אחרת מחזירים |posNum − posOpp| + 1.

מה נדרש: למצוא את אורך הרצף שמתחיל ב־num ונגמר ב־−num, או מתחיל ב־−num ונגמר ב־num.

רעיון: כל המספרים בשרשרת שונים זה מזה, ולכן num מופיע פעם אחת ו־−num מופיע לכל היותר פעם אחת. האורך של הרצף שביניהם, כולל הקצוות, הוא ההפרש בין המקומות שלהם ועוד 1. לא משנה מי מהשניים מופיע קודם, ולכן משתמשים בערך מוחלט: |posNum − posOpp| + 1.

עוברים על השרשרת עם הפניה עזר p (lst עצמו לא זז) וסופרים מקום (pos):

•אם הערך הוא num – שומרים posNum = pos.
•אם הערך הוא −num – שומרים posOpp = pos.

אם בסוף posOpp == 0, המספר הנגדי לא נמצא, ומחזירים −1. (num ≠ 0, ולכן num ו־−num שונים, וה־else if תקין.)

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

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

בדיקה (השרשרת −9, −1, 1, 22, 10, −2, 9, −10, 4):

numמקום numמקום −numתוצאה
9717 − 1 + 1 = 7
−1233 − 2 + 1 = 2
224לא נמצא−1
10584

מתקבלים 7, 2, −1, 4, והשרשרת לא משתנה.

הקוד המלא
public static int width(Node<Integer> lst, int num)
{
    int pos = 0;            // מקום החוליה הנוכחית
    int posNum = 0;         // המקום של num
    int posOpp = 0;         // המקום של -num (0 = לא נמצא)
    Node<Integer> p = lst;
    while (p != null)
    {
        pos++;
        if (p.getValue() == num)
            posNum = pos;
        else if (p.getValue() == -num)
            posOpp = pos;
        p = p.getNext();
    }
    if (posOpp == 0)
        return -1;
    return Math.abs(posNum - posOpp) + 1;
}

סעיף ב

תשובה

max = −1. לכל ערך v בשרשרת מחשבים width(lst, v) ומעדכנים את max אם התוצאה גדולה יותר. מחזירים את max (נשאר −1 אם אין אף תת־סדרה נגדית).

מה נדרש: האורך הגדול ביותר של "תת־סדרה נגדית" בשרשרת, או −1 אם אין אף אחת.

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

פתרון: הקוד המלא – בלשונית Java/C#. width רק קוראת את השרשרת ולא משנה אותה, ולכן אפשר לקרוא לה על אותה lst שוב ושוב בזמן המעבר.

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

בדיקה: בשרשרת שבדוגמה יש שלוש תת־סדרות נגדיות: (−9 … 9) באורך 7, (10 … −10) באורך 4 ו־(−1, 1) באורך 2. ל־22, −2 ו־4 אין מספר נגדי. המקסימום הוא 7. בבדיקות נוספות: שרשרת בלי זוגות נגדיים ⇒ −1, השרשרת 2, −2 ⇒ 2, וסדרת הדוגמה מהפתיח, 17, 3, 1, −4, 5, 6, 4, −3, 7, 23, −99 ⇒ 7 (התת־סדרה 3 … −3).

הקוד המלא
public static int longest(Node<Integer> lst)
{
    int max = -1;
    Node<Integer> p = lst;
    while (p != null)
    {
        int w = width(lst, p.getValue());   // תת-סדרה נגדית שמתחילה או מסתיימת בערך זה
        if (w > max)
            max = w;
        p = p.getNext();
    }
    return max;
}

פרק שני – אלגוריתמים

בפרק זה שאלות בשלושה מסלולים:
אלגוריתמים, עמודים 9–10.
מודלים חישוביים, עמודים 11–13.
תכנות מונחה עצמים בשפת Java, עמודים 14–19; תכנות מונחה עצמים בשפת C#, עמודים 20–25.
בחרו בשאלות מתוך מסלול אחד בלבד.

שאלה 6 · קודקודים ישיגים ורכיב הקשירות הקטן ביותר (25 נקודות)

נתון גרף, לא קשיר ולא מכוון G(V, E) שבו n קודקודים, מ־ v₀ עד vₙ₋₁ .

א.

כתבו אלגוריתם המוצא ומחזיר את כל הקודקודים שיש מסלול בין קודקוד בגרף – vⱼ וביניהם.
הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
דוגמה: עבור הגרף שלפניכם, וקודקוד 3 , האלגוריתם יחזיר את הקודקודים 0 , 6 , 7 , 9 .

הסבר: קיים מסלול בין הקודקוד 3 ובין הקודקודים 0 , 6 , 7 , 9 .

ב.

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

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

◂ פתרון מלא לשאלה 6

סעיף א

תשובה

סריקת BFS (או DFS) מ־ vⱼ : כל קודקוד שמתגלה בסריקה (חוץ מ־ vⱼ עצמו) מוחזר. זמן ריצה O(|V| + |E|). בדוגמה מ־3 מתגלים 7, 0, 9, 6.

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

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

פתרון (הגרף מיוצג ברשימות שכנויות):

Reachable(G, vⱼ):
    לכל קודקוד u ב־V:   visited[u] ← false
    visited[vⱼ] ← true
    Q ← תור ריק ;  Q.insert(vⱼ)
    R ← רשימה ריקה                        // הקודקודים שיוחזרו
    כל עוד Q אינו ריק:
        u ← Q.remove()
        לכל שכן v של u:
            אם visited[v] = false:
                visited[v] ← true
                הוסף את v ל־R
                Q.insert(v)
    החזר את R

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

בדיקה – על הגרף שבדוגמה מקודקוד 3 (שכנים בסדר עולה):

צעדהוצא מהתורשכנים חדשים שסומנוהתור אחרי הצעדR
0–3 (המקור)[3]{}
137[7]{7}
270, 9[0, 9]{7, 0, 9}
306[9, 6]{7, 0, 9, 6}
49– (6, 7 כבר מסומנים)[6]{7, 0, 9, 6}
56–[]{7, 0, 9, 6}

התוצאה: 0, 6, 7, 9 – כמו בדוגמה.

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

סעיף ב

תשובה

עוברים על הקודקודים v₀…vₙ₋₁; מכל קודקוד שעוד לא סומן מריצים BFS שאוסף את רכיב הקשירות שלו; שומרים את הרכיב בעל מספר הקודקודים הקטן ביותר. זמן ריצה O(|V| + |E|). בדוגמה: הרכיבים בגדלים 5, 2, 3 ⇒ מוחזר {1, 5}.

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

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

פתרון:

SmallestComponent(G):
    לכל קודקוד u ב־V:   visited[u] ← false
    minComp ← ריק ;  minSize ← ∞
    לכל קודקוד s מ־ v₀ עד vₙ₋₁:
        אם visited[s] = false:            // s פותח רכיב קשירות חדש
            comp ← רשימה ובה s ;  visited[s] ← true
            Q ← תור ריק ;  Q.insert(s)
            כל עוד Q אינו ריק:
                u ← Q.remove()
                לכל שכן v של u:
                    אם visited[v] = false:
                        visited[v] ← true
                        הוסף את v ל־comp
                        Q.insert(v)
            אם |comp| < minSize:
                minSize ← |comp| ;  minComp ← comp
    החזר את minComp

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

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

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

קודקוד שפותח רכיבהרכיב שנמצאגודלminSize אחרי
0{0, 6, 7, 9, 3}55
1{1, 5}22
2{2, 4, 8}32

שאר הקודקודים (3–9) כבר מסומנים. מוחזר הרכיב {1, 5} – כמו בדוגמה.

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

שאלה 7 · טענות על גרפים – נכון / לא נכון (25 נקודות)

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

א.

כל עץ המתקבל מהרצת DFS על גרף G לא מכוון, יכול להתקבל גם מהרצת BFS על אותו הגרף.

ב.

כל עץ המתקבל מהרצת DFS על גרף G לא מכוון מלא הוא עץ שבו לכל צומת יש רק בן אחד.

ג.

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

ד.

אם בגרף G שאינו מכוון המסלול הקצר ביותר מן הצומת sⱼ אל הצומת sₙ הוא S[sⱼ…sₘ…sₖ…sₙ] ,
בהכרח התת־מסלול מ־ sₘ ועד sₖ הוא המסלול הקצר ביותר מן הצומת sₘ אל הצומת sₖ .

ה.

גרף שיש בו מעגל אינו יכול להיות גרף דו־צדדי.

ו.

לכל גרף G ממושקל, לא מכוון, יש עץ פורש מינימלי יחיד.

◂ פתרון מלא לשאלה 7

סעיף א

תשובה

לא נכונה. דוגמה נגדית: הגרף השלם K₄ – עץ DFS שלו הוא מסלול a–b–c–d, ואילו כל עץ BFS שלו הוא "כוכב" (השורש מחובר ישירות לשלושת האחרים).

מה נדרש: לקבוע אם כל עץ DFS הוא גם עץ BFS אפשרי.

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

פתרון: הטענה לא נכונה. דוגמה נגדית: הגרף השלם על 4 קודקודים a, b, c, d (כל זוג קודקודים מחובר בקשת).

•DFS מ־a: a → b → c → d. עץ ה־DFS הוא המסלול a–b–c–d (עומק 3).
•BFS מכל שורש r: כל שלושת הקודקודים האחרים שכנים של r, ולכן כולם מתגלים כבר בשלב הראשון ונעשים ילדים של r – העץ הוא "כוכב" (כל הקשתות יוצאות מ־r).

מסלול של 4 קודקודים אינו כוכב, ולכן עץ ה־DFS הזה אינו יכול להתקבל מ־BFS בשום בחירה של שורש וסדר שכנים.

בדיקה: עוברים על כל עצי ה־DFS וכל עצי ה־BFS של K₄ (כל שורש וכל סדר שכנים): אף אחד מ־12 עצי ה־DFS אינו עץ BFS.

טעות נפוצה: לתת משולש כדוגמה נגדית – עץ ה־DFS של משולש (מסלול) כן מתקבל ב־BFS מהקודקוד האמצעי.

סעיף ב

תשובה

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

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

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

פתרון: הטענה נכונה.
נניח ש־DFS נמצא בקודקוד u, ועדיין יש בגרף קודקוד w שלא התגלה. בגרף מלא יש קשת u–w, ולכן ל־u יש שכן לא מגולה, וה־DFS ממשיך ממנו לקודקוד חדש (בן של u) ואינו חוזר אחורה. ה־DFS חוזר אחורה בפעם הראשונה רק כשכל n הקודקודים כבר התגלו – ואז אין עוד בנים חדשים לאף צומת.
לכן הקודקודים מתגלים בשרשרת v₁ → v₂ → … → vₙ, ועץ ה־DFS הוא המסלול v₁–v₂–…–vₙ: לכל צומת בן אחד בדיוק, חוץ מ־vₙ (עלה, ללא בנים). זה נכון לכל קודקוד התחלה ולכל סדר של שכנים.

בדיקה: בכל עצי ה־DFS (כל שורש וכל סדר שכנים) של הגרפים המלאים K₂ … K₅ יש לכל צומת לכל היותר בן אחד. (לעומת זאת, בגרף שאינו מלא – למשל כוכב a–b, a–c, a–d – ל־a יש שלושה בנים; לכן חשובה המילה "מלא".)

טעות נפוצה: להתעלם מהמילה מלא ולתת דוגמה נגדית של גרף שאינו מלא.

סעיף ג

תשובה

נכונה. לכל שני קודקודים u, w: יש מסלול u ⇝ v ומסלול v ⇝ w, ושרשורם הוא מסלול u ⇝ w. לכן בין כל שני קודקודים יש מסלולים בשני הכיוונים.

מה נדרש: להוכיח או להפריך שהגרף קשיר היטב (לכל זוג קודקודים u, w יש מסלול מכוון מ־u ל־w).

רעיון: לעבור "דרך v".

פתרון: הטענה נכונה. יהיו u ו־w שני קודקודים כלשהם בגרף.

•לפי הנתון אפשר להגיע מכל קודקוד אל v, ולכן יש מסלול מכוון u ⇝ v.
•לפי הנתון אפשר להגיע מ־v לכל קודקוד, ולכן יש מסלול מכוון v ⇝ w.
•שרשור שני המסלולים נותן הילוך (מסלול, אולי עם חזרות – ואפשר לקצר אותו למסלול פשוט) u ⇝ v ⇝ w.

באותו אופן יש גם מסלול מ־w ל־u. הזוג נבחר באופן כללי, ולכן G קשיר היטב.

בדיקה: למשל, בגרף מכוון על 5 קודקודים שבו קודקוד 0 מגיע לכולם וכולם מגיעים אליו – כל קודקוד מגיע לכל הקודקודים (דרך קודקוד 0).

סעיף ד

תשובה

נכונה. אילו היה מסלול קצר יותר מ־sₘ ל־sₖ, היינו מחליפים בו את הקטע sₘ…sₖ ומקבלים מסלול מ־sⱼ ל־sₙ קצר יותר מ־S – בסתירה לכך ש־S הקצר ביותר.

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

רעיון: הוכחה בדרך השלילה – "גזור והדבק".

פתרון: הטענה נכונה. נסמן את S כשרשור של שלושה קטעים: S = P₁ · P₂ · P₃, כאשר P₁ מ־sⱼ ל־sₘ, P₂ מ־sₘ ל־sₖ, P₃ מ־sₖ ל־sₙ. אורך S הוא |P₁| + |P₂| + |P₃|.
נניח בשלילה שיש מסלול P₂′ מ־sₘ ל־sₖ שאורכו קטן מ־|P₂|. נחליף את P₂ ב־P₂′ ונקבל הילוך מ־sⱼ ל־sₙ באורך |P₁| + |P₂′| + |P₃| < |S|. (אם בהילוך החדש יש קודקוד שחוזר, משמיטים את המעגל שנוצר – בגרף בלי משקלים שליליים זה רק מקצר.) קיבלנו מסלול מ־sⱼ ל־sₙ קצר מ־S – סתירה לכך ש־S הוא המסלול הקצר ביותר. לכן P₂ הוא מסלול קצר ביותר מ־sₘ ל־sₖ.
(הטענה נכונה גם בגרף ללא משקלים – אורך = מספר קשתות – וגם בגרף ממושקל עם משקלים אי־שליליים.)

בדיקה: בכל גרף ממושקל, כל תת־מסלול של מסלול קצר ביותר הוא באורך השווה למרחק הקצר ביותר בין קצותיו.

סעיף ה

תשובה

לא נכונה. דוגמה נגדית: מעגל באורך 4, a–b–c–d–a, הוא גרף דו־צדדי: {a, c} ו־{b, d}.

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

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

פתרון: הטענה לא נכונה. דוגמה נגדית: הגרף a–b, b–c, c–d, d–a (מעגל באורך 4).
נחלק: X = {a, c}, Y = {b, d}. כל אחת מארבע הקשתות מחברת קודקוד מ־X עם קודקוד מ־Y, ולכן הגרף דו־צדדי – למרות שיש בו מעגל.

בדיקה: צביעה בשני צבעים ב־BFS: a, c צבע 0; b, d צבע 1 – אין קשת בין קודקודים באותו צבע.

סעיף ו

תשובה

לא נכונה. דוגמה נגדית: משולש a, b, c שבו משקל כל קשת 1 – כל שתי קשתות הן עץ פורש מינימלי במשקל 2, כלומר יש 3 עצים כאלה.

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

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

פתרון: הטענה לא נכונה. דוגמה נגדית: גרף משולש עם הקשתות a–b, b–c, a–c, וכולן במשקל 1.
עץ פורש על 3 קודקודים כולל 2 קשתות, ולכן משקלו 2 בכל בחירה. העצים {a–b, b–c}, {a–b, a–c}, {b–c, a–c} הם שלושה עצים פורשים מינימליים שונים.

בדיקה: מונים את כל זוגות הקשתות של המשולש: 3 עצים במשקל המינימלי 2.

שאלה 8 · האלגוריתם של דייקסטרה (25 נקודות)

לפניכם הגרף הממושקל G :

א.(1)

כתבו אלגוריתם המוצא בגרף ממושקל (אי־שלילי) כלשהו, שבו n קודקודים מ־ v₀ עד vₙ₋₁ וקודקוד בגרף – vⱼ , את המסלולים הקצרים (הקלים) ביותר מקודקוד vⱼ שבגרף אל שאר הקודקודים שבגרף.

(2)

מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.

ב.(1)

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

(2)

בעבור גרף G הנתון, סרטטו את עץ המסלולים הקצרים (מקודקוד S).

◂ פתרון מלא לשאלה 8

סעיף א(1)

תשובה

האלגוריתם של דייקסטרה מ־vⱼ: אתחול d[vⱼ]=0 ושאר d=∞; בכל איטרציה מעבירים מ־T ל־P את הקודקוד u בעל d מינימלי ומרפים את הקשתות שלו (אם d[u]+w(u,v) < d[v] אז d[v] ← d[u]+w(u,v), π[v] ← u). המסלולים נקראים לאחור לפי π.

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

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

פתרון:

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

בסיום d[v] הוא אורך המסלול הקל ביותר מ־vⱼ ל־v, והמסלול עצמו מתקבל בהליכה לאחור v, π[v], π[π[v]], … עד vⱼ. אם d[v] = ∞ – אין מסלול מ־vⱼ ל־v.

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

סעיף א(2)

תשובה

O(n²) (מימוש במערך). עם ערימת מינימום: O((n + |E|)·log n).

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

פתרון (מימוש פשוט – d במערך):

•אתחול: O(n).
•הלולאה הראשית רצה n פעמים (בכל איטרציה קודקוד אחד עובר מ־T ל־P).
•בכל איטרציה מחפשים את המינימום ב־T במעבר על עד n קודקודים: O(n). סך הכול לחיפושים: n · O(n) = O(n²).
•ההרפיות: רשימת השכנים של כל קודקוד נסרקת פעם אחת (כשהוא נבחר) ⇒ סך הכול O(|E|), ו־|E| ≤ n² .

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

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

סעיף ב(1)

תשובה

d/π: S 0/– , G 2/S , C 9/G , H 10/G , B 12/G , D 16/H , I 18/H , F 22/G. סדר הקביעה: S, G, C, H, B, D, I, F.

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

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

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

איטרציההקודקוד שנבחרP (קבועים)T (זמניים)SBCDFGHI
0 (אתחול)–{ }{S, B, C, D, F, G, H, I}0/–∞/–∞/–∞/–∞/–∞/–∞/–∞/–
1S{S}{B, C, D, F, G, H, I}0/–15/S∞/–∞/–30/S2/S∞/–∞/–
2G{S, G}{B, C, D, F, H, I}0/–12/G9/G∞/–22/G2/S10/G∞/–
3C{S, G, C}{B, D, F, H, I}0/–12/G9/G19/C22/G2/S10/G∞/–
4H{S, G, C, H}{B, D, F, I}0/–12/G9/G16/H22/G2/S10/G18/H
5B{S, G, C, H, B}{D, F, I}0/–12/G9/G16/H22/G2/S10/G18/H
6D{S, G, C, H, B, D}{F, I}0/–12/G9/G16/H22/G2/S10/G18/H
7I{S, G, C, H, B, D, I}{F}0/–12/G9/G16/H22/G2/S10/G18/H
8F{S, G, C, H, B, D, I, F}{ }0/–12/G9/G16/H22/G2/S10/G18/H

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

1.S (0): B ← 15, G ← 2, F ← 30.
2.G (2): B: 2+10 = 12 < 15 ⇒ 12/G ; C: 2+7 = 9 ; F: 2+20 = 22 < 30 ⇒ 22/G ; H: 2+8 = 10.
3.C (9): B: 9+4 = 13 > 12 – ללא שינוי ; D: 9+10 = 19 ; H: 9+13 = 22 > 10 – ללא שינוי.
4.H (10): D: 10+6 = 16 < 19 ⇒ 16/H ; I: 10+8 = 18 ; F: 10+13 = 23 > 22 – ללא שינוי.
5.B (12): כל שכניו (S, C, G) כבר קבועים.
6.D (16): I: 16+15 = 31 > 18 – ללא שינוי.
7.I (18), 8. F (22): אין שכנים זמניים לעדכון.

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

קודקודאורךמסלול
G2S → G
C9S → G → C
H10S → G → H
B12S → G → B
D16S → G → H → D
I18S → G → H → I
F22S → G → F

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

טעות נפוצה: לקבוע את F עם המרחק 30 (הקשת הישירה S–F) – המסלול S → G → F קל יותר (22).

סעיף ב(2)

תשובה

קשתות העץ (π[v] – v): S–G, G–B, G–C, G–F, G–H, H–D, H–I.

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

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

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

ובצורת עץ:

S
└── G   (2)
    ├── C   (9)
    ├── H   (10)
    │   ├── D   (16)
    │   └── I   (18)
    ├── B   (12)
    └── F   (22)

בדיקה: סכום המשקלים על המסלול מהשורש לכל קודקוד בעץ שווה ל־d שלו (למשל S–G–H–I: 2 + 8 + 8 = 18).

פרק שני – מודלים חישוביים

בפרק זה שאלות בשלושה מסלולים:
אלגוריתמים, עמודים 9–10.
מודלים חישוביים, עמודים 11–13.
תכנות מונחה עצמים בשפת Java, עמודים 14–19; תכנות מונחה עצמים בשפת C#, עמודים 20–25.
בחרו בשאלות מתוך מסלול אחד בלבד.

שאלה 9 · טענות על שפות לא רגולריות ואוטומט סופי דטרמיניסטי (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.

א.(1)

לפניכם שתי טענות (1)–(2) בנוגע לשפות L₁ , L₂ שמעל הא"ב {a, b} .
בעבור כל טענה, ציינו אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע,
ואם היא לא נכונה – הביאו דוגמה נגדית. אין קשר בין הטענות.

(1) אם L₁ , L₂ הן שפות לא רגולריות, בהכרח L₁ ∩ L₂ היא שפה לא רגולרית.

(2)

(L₁ • L₂)ⁿ תמיד שווה ל־ L₁ⁿ • L₂ⁿ .

ב.(1)

נתונה השפה L מעל הא"ב {a, b, c} :
L = {w | רצפים ab , bc אינם מופיעים ב־ w , #a(w) + #c(w) = מספר זוגי }
#a(w) מציין את מספר המופעים של a במילה w .
#c(w) מציין את מספר המופעים של c במילה w .

דוגמה למילה בשפה L היא cba , כי סכום המופעים של האות a (1) והאות c (1) הוא מספר זוגי (2) , והרצפים ab ו־ bc אינם מופיעים במילה.

(1) לפניכם חמש מילים. בנוגע לכל אחת מהן ציינו אם המילה שייכת לשפה L או לא. נמקו את תשובתכם.
aaccc , aab , ε , baa , cbbba .

(2)

בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L .

◂ פתרון מלא לשאלה 9

סעיף א(1)

תשובה

לא נכונה. L₁ = {aⁿbⁿ | n ≥ 0}, L₂ = {bⁿaⁿ | n ≥ 0} – שתיהן לא רגולריות, אבל L₁ ∩ L₂ = {ε}, שפה סופית ולכן רגולרית.

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

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

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

•L₁ = {aⁿbⁿ | n ≥ 0} – שפה לא רגולרית (אוטומט סופי אינו יכול "לזכור" כמה a נקראו).
•L₂ = {bⁿaⁿ | n ≥ 0} – לא רגולרית מאותה סיבה.
•מילה לא ריקה ב־L₁ מתחילה ב־a, ומילה לא ריקה ב־L₂ מתחילה ב־b, לכן המילה המשותפת היחידה היא ε: L₁ ∩ L₂ = {ε}.

{ε} היא שפה סופית, ולכן רגולרית (אוטומט עם מצב התחלתי מקבל בלבד).

(דוגמה נוספת: L₂ = המשלימה של L₁. היא לא רגולרית – אחרת גם המשלימה שלה, L₁, הייתה רגולרית – והחיתוך הוא ∅, שפה רגולרית.)

סעיף א(2)

תשובה

לא נכונה. L₁ = {a}, L₂ = {b}, n = 2: (L₁•L₂)² = {abab}, ואילו L₁²•L₂² = {aabb}.

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

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

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

•L₁ • L₂ = {ab}, ולכן (L₁ • L₂)² = {abab}.
•L₁² = {aa}, L₂² = {bb}, ולכן L₁² • L₂² = {aabb}.

abab ≠ aabb, כלומר השפות שונות. (בשביל n = 0 ו־n = 1 השוויון מתקיים, אבל לא "תמיד".)

בדיקה: חישוב השפות: {'abab'} לעומת {'aabb'}.

סעיף ב(1)

תשובה

cbbba ∈ L ; baa ∈ L ; ε ∈ L ; aab ∉ L (מכילה ab) ; aaccc ∉ L (5 מופעים של a ו־c – אי־זוגי).

מה נדרש: לבדוק לכל מילה שני תנאים: (1) אין בה את הרצפים ab ו־bc; (2) #a(w) + #c(w) זוגי.

פתרון:

מילהרצף ab או bc?#a + #cשייכת ל־L?
cbbbaלא (cb, bb, bb, ba)1 + 1 = 2 – זוגיכן
baaלא (ba, aa)2 + 0 = 2 – זוגיכן
εלא (אין אותיות)0 + 0 = 0 – זוגיכן
aabכן – מופיע ab2 + 0 = 2לא (בגלל ab)
aacccלא (aa, ac, cc, cc)2 + 3 = 5 – אי־זוגילא

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

טעות נפוצה: לשכוח ש־ε שייכת לשפה – 0 הוא מספר זוגי ואין בה רצפים אסורים.

סעיף ב(2)

תשובה

6 מצבים (זוגיות של #a+#c × האות האחרונה): q0 (התחלה, זוגי), q1, q2, q3, q4, q5; מקבלים: q0, q2, q4. מעברים: q0: a→q3, b→q4, c→q1 ; q1: a→q2, b→q5, c→q0 ; q2: a→q3, c→q1 ; q3: a→q2, c→q0 ; q4: a→q3, b→q4 ; q5: a→q2, b→q5 (מעבר חסר = דחייה).

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

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

1.הזוגיות של #a(w) + #c(w) – כל a או c מחליף זוגיות, b לא משנה אותה.
2.האות האחרונה – כדי לא לאפשר ab ו־bc: אחרי a אסור b, אחרי b אסור c. אחרי c (או בהתחלה) אין איסור, ולכן "אחרון c" ו"התחלה" מתנהגים אותו דבר.

לכן 3 × 2 = 6 מצבים. מעבר שיוצר רצף אסור אינו מוגדר (במקום מצב בור) – לכן האוטומט אינו מלא.

פתרון – Σ = {a, b, c}, מצב התחלתי q0, מצבים מקבלים {q0, q2, q4}:

מצבמשמעותabc
→ q0 (מקבל)זוגי; התחלה או האות האחרונה cq3q4q1
q1אי־זוגי; האות האחרונה cq2q5q0
q2 (מקבל)זוגי; האות האחרונה aq3–q1
q3אי־זוגי; האות האחרונה aq2–q0
q4 (מקבל)זוגי; האות האחרונה bq3q4–
q5אי־זוגי; האות האחרונה bq2q5–

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

הסבר המעברים: a מעביר תמיד ל"אחרון a" ומחליף זוגיות; c מעביר ל"אחרון c" ומחליף זוגיות (חסר אחרי b); b שומר על הזוגיות ומעביר ל"אחרון b" (חסר אחרי a).

בדיקה:

•cba: q0 –c→ q1 –b→ q5 –a→ q2 ⇒ מקבל ✓.
•cbbba: q0 → q1 → q5 → q5 → q5 → q2 ⇒ מקבל ✓.
•aab: q0 → q3 → q2, ומ־q2 אין מעבר ב־b ⇒ נדחית ✓.
•aaccc: q0 → q3 → q2 → q1 → q0 → q1 ⇒ q1 אינו מקבל ⇒ נדחית ✓.
•ε: נשארים ב־q0 המקבל ✓.

האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}.

שאלה 10 · פעולות על שפות ואוטומט מחסנית דטרמיניסטי (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.

א.(1)

לפניכם שש שפות מעל הא"ב {0 , 1} :
Σ* – מציין את שפת כל המילים מעל הא"ב {0 , 1} .

L₁ = ØL₄ = {0110}
L₂ = Σ*L₅ = {ε , 110, 00, 001}
L₃ = {ε}L₆ = {1, 0110, 110, 01}

כתבו את השפה המתקבלת מכל אחת מחמש הפעולות שלהלן:

(1) L₅ ∩ L₆

(2)

L₂ᴿ

(3)

L₁ • L₆

(4)

L₃ • L₄

(5)

L₄ • L₅

ב.

נתונה השפה L מעל הא"ב {a, b, c} :
L = {(ab)ᵏ cᵐ bᵐ⁺³ᵏ | k , m >= 0}

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

◂ פתרון מלא לשאלה 10

סעיף א(1)

תשובה

L₅ ∩ L₆ = {110}

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

פתרון: L₅ = {ε, 110, 00, 001}, L₆ = {1, 0110, 110, 01}. המילה היחידה שמופיעה בשתיהן היא 110 (ε, 00, 001 אינן ב־L₆).
L₅ ∩ L₆ = {110}.

סעיף א(2)

תשובה

L₂ᴿ = Σ* = L₂

מה נדרש: ההיפוך של L₂ = Σ* – קבוצת ההיפוכים של כל המילים.

פתרון: לכל מילה w מעל {0, 1} גם wᴿ היא מילה מעל {0, 1}, ולהפך: כל מילה u היא ההיפוך של uᴿ ∈ Σ*. לכן קבוצת ההיפוכים היא שוב כל המילים: L₂ᴿ = Σ*.

סעיף א(3)

תשובה

L₁ • L₆ = Ø

מה נדרש: שרשור של השפה הריקה עם L₆.

פתרון: מילה בשרשור L₁ • L₆ היא xy כאשר x ∈ L₁ ו־y ∈ L₆. ב־L₁ = Ø אין אף מילה, ולכן אין אף זוג כזה: L₁ • L₆ = Ø.

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

סעיף א(4)

תשובה

L₃ • L₄ = {0110}

מה נדרש: שרשור של {ε} עם L₄.

פתרון: המילה היחידה ב־L₃ היא ε, ו־ε · 0110 = 0110. לכן L₃ • L₄ = {0110} = L₄ ({ε} היא איבר היחידה של השרשור).

סעיף א(5)

תשובה

L₄ • L₅ = {0110, 0110110, 011000, 0110001}

מה נדרש: שרשור של 0110 עם כל אחת ממילות L₅.

פתרון:

•0110 · ε = 0110
•0110 · 110 = 0110110
•0110 · 00 = 011000
•0110 · 001 = 0110001

L₄ • L₅ = {0110, 0110110, 011000, 0110001}.

סעיף ב

תשובה

דוחפים 3 סימנים לכל ab ו־1 לכל c (הסימן התחתון ביותר מסומן Y), ושולפים סימן אחד לכל b; מגיעים למצב המקבל q5 כששולפים את Y. מצבים מקבלים: q0 (בשביל ε) ו־q5. אין מעברי ε.

מה נדרש: אוטומט מחסנית דטרמיניסטי ל־L = {(ab)ᵏ cᵐ bᵐ⁺³ᵏ | k, m ≥ 0}.

רעיון: מספר ה־b בסוף צריך להיות 3 לכל זוג ab ועוד 1 לכל c. לכן:

•על כל זוג ab דוחפים 3 סימנים למחסנית.
•על כל c דוחפים סימן 1.
•על כל b שולפים סימן אחד.
•המילה מתקבלת אם בסוף הקלט המחסנית ריקה (רק ⊥).

כדי לדעת בלי מעברי ε מתי שלפנו את הסימן האחרון, הסימן הראשון שנדחף (התחתון ביותר מעל ⊥) הוא Y, וכל השאר X. כששולפים את Y עוברים למצב המקבל q5. אחרי ab מוכרח לבוא a, c או b, ואחרי c – רק c או b, ואחרי b – רק b: הסדר נאכף על ידי המצבים.

פתרון:

•מצבים: q0 (התחלתי), q1, q2, q3, q4, q5. מצבים מקבלים: q0, q5 (q0 מקבל את ε, כלומר k = m = 0).
•א"ב הקלט: {a, b, c}. א"ב המחסנית: {X, Y, ⊥}, כאשר ⊥ הוא סימן תחתית המחסנית (נמצא בה בהתחלה).
•סימון מעבר: (מצב, אות קלט, ראש המחסנית) → (מצב חדש, מחרוזת שמחליפה את ראש המחסנית). התו השמאלי במחרוזת הוא ראש המחסנית החדש; ε = שליפה (pop).
מצבקלטראש המחסניתמצב חדשמחליפים את הראש ב־משמעות
q0a⊥q1XXY⊥ה־a של ה־ab הראשון: דוחפים 3 (התחתון Y)
q0c⊥q3Y⊥k = 0, ה־c הראשון: דוחפים 1 (Y)
q1bXq2Xה־b של ab – בלי שינוי במחסנית
q2aXq1XXXXab נוסף: דוחפים עוד 3
q2cXq3XXc ראשון אחרי (ab)ᵏ: דוחפים 1
q2bXq4εm = 0, ה־b הראשון: שולפים
q3cXq3XXc נוסף: דוחפים 1
q3cYq3XYc נוסף (k = 0, m = 1 עד כה): דוחפים 1
q3bXq4εה־b הראשון: שולפים
q3bYq5εה־b הראשון והאחרון (k = 0, m = 1)
q4bXq4εשולפים
q4bYq5εשולפים את הסימן האחרון – המחסנית ריקה

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

בדיקה – מעקב על abcbbbb (k = 1, m = 1, ולכן 1 + 3 = 4 אותיות b):

נקראמצבמחסנית (ראש משמאל)
–q0⊥
aq1XXY⊥
bq2XXY⊥
cq3XXXY⊥
bq4XXY⊥
bq4XY⊥
bq4Y⊥
bq5⊥

הקלט נגמר במצב המקבל q5 ⇒ המילה מתקבלת. לעומת זאת abcbbb נגמרת ב־q4 (לא מקבל) ו־abcbbbbb נתקעת (ב־q5 אין מעברים) – שתיהן נדחות.
האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}. מתקבלות למשל: ε, abbbb, cb, ccbb, abcbbbb, ababbbbbbb.

טעות נפוצה: לשכוח את המילה ε (k = m = 0) – לכן q0 חייב להיות מקבל.

שאלה 11 · מכונת טיורינג – הפרש בין שני מספרים אונריים (25 נקודות)

לפניכם מכונת טיורינג:

המכונה מקבלת בתחילת הסרט שני מספרים אונריים שביניהם הסימן # .

א.

עקבו אחר המכונה עבור הסרט שלהלן:

⊢1#111ΔΔ. . .

כתבו מה יתקבל על הסרט בסיום הפעולה.

ב.

כתבו מה יתקבל על הסרט שלהלן בסיום הפעולה:

⊢11#1ΔΔ. . .

הערה: בסעיף זה אין צורך להראות מעקב.

ג.

מה המכונה מבצעת עבור שני מספרים אונריים הגדולים מאפס?

ד.

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

1.המספר הראשון (משמאל) שווה לאפס והמספר השני גדול מאפס.
2.המספר השני שווה לאפס והמספר הראשון גדול מאפס.
3.שני המספרים שווים לאפס.
◂ פתרון מלא לשאלה 11

סעיף א

תשובה

המכונה עוצרת במצב q7 והסרט: ⊢ Δ $ 1 1 $ Δ Δ … (בין שני סימני $ – 11, כלומר 2 = 3 − 1).

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

קריאת הסרטוט: התווית "x / y , כיוון" על חץ פירושה: קוראים x, כותבים y ומזיזים את הראש לכיוון הנתון. הראש מתחיל במצב q0 על התא הראשון שמימין ל־⊢ (תא 1). q7 הוא מצב העצירה (המקבל). טבלת המעברים של המכונה:

מצבקוראכותבתזוזהמצב חדש
q01Δימיןq1
q0#$ימיןq8
q111ימיןq1
q1##ימיןq2
q211ימיןq2
q2ΔΔשמאלq3
q31Δשמאלq4
q3#$שמאלq5
q411שמאלq4
q4##שמאלq4
q4ΔΔימיןq0
q511שמאלq5
q5Δ1שמאלq6
q6Δ$ימיןq7
q811ימיןq8
q8Δ$ימיןq7

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

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

צעדמצבתא (מיקום הראש)נקראנכתבתזוזהמצב חדשהסרט אחרי הצעד
1q011Δימיןq1⊢ Δ # 1 1 1 Δ
2q12##ימיןq2⊢ Δ # 1 1 1 Δ
3q2311ימיןq2⊢ Δ # 1 1 1 Δ
4q2411ימיןq2⊢ Δ # 1 1 1 Δ
5q2511ימיןq2⊢ Δ # 1 1 1 Δ
6q26ΔΔשמאלq3⊢ Δ # 1 1 1 Δ
7q351Δשמאלq4⊢ Δ # 1 1 Δ Δ
8q4411שמאלq4⊢ Δ # 1 1 Δ Δ
9q4311שמאלq4⊢ Δ # 1 1 Δ Δ
10q42##שמאלq4⊢ Δ # 1 1 Δ Δ
11q41ΔΔימיןq0⊢ Δ # 1 1 Δ Δ
12q02#$ימיןq8⊢ Δ $ 1 1 Δ Δ
13q8311ימיןq8⊢ Δ $ 1 1 Δ Δ
14q8411ימיןq8⊢ Δ $ 1 1 Δ Δ
15q85Δ$ימיןq7⊢ Δ $ 1 1 $ Δ

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

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

סעיף ב

תשובה

⊢ $ 1 $ Δ Δ … (המכונה עוצרת ב־q7).

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

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

•סיבוב 1: q0 מוחק את ה־1 בתא 1, q3 מוחק את ה־1 של המספר הימני (תא 4). הסרט: ⊢ Δ 1 # Δ.
•סיבוב 2: q0 מוחק את ה־1 בתא 2. ב־q2 נקרא Δ (תא 4), ב־q3 נקרא # – המספר הימני נגמר: # ← $.
•q5 הולך שמאלה ופוגש את Δ בתא 2 (ה־1 שנמחק בסיבוב הזה ולא היה לו "בן זוג") וכותב בו 1 בחזרה; q6 כותב $ בתא 1 ועובר ל־q7.

הסרט בסיום: ⊢ $ 1 $ Δ Δ … – בין שני סימני ה־$ יש 1 אחד: 2 − 1 = 1.

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

סעיף ג

תשובה

המכונה מחשבת את ההפרש בערך מוחלט |x − y| של שני המספרים: בסיום על הסרט Δ…Δ $ 1^|x−y| $ (התוצאה באונרי בין שני סימני $).

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

רעיון: בכל סיבוב (q0 → q1 → q2 → q3 → q4 → q0) נמחק 1 אחד משמאל ל־# (מתחילת המספר הראשון) ו־1 אחד מימין ל־# (מסוף המספר השני). הסיבובים נמשכים עד שאחד המספרים נגמר, כלומר min(x, y) סיבובים מלאים.

•x ≤ y: q0 פוגש את # (המספר הראשון נגמר) ⇒ כותב $, q8 עובר על y − x האחדים שנשארו וכותב $ אחריהם.
•x > y: בסיבוב ה־(y+1) q0 מוחק עוד 1, אבל q3 פוגש את # (המספר השני נגמר) ⇒ כותב $, q5 הולך שמאלה על האחדים שנשארו, מחזיר 1 לתא שנמחק עכשיו (כי לא היה לו בן זוג), ו־q6 כותב $ בתא הריק שמשמאלו. בין שני ה־$ נשארים x − y אחדים.

פתרון: המכונה מחשבת את ההפרש בערך מוחלט |x − y| ומשאירה אותו בייצוג אונרי בין שני סימני $:
⊢ Δ…Δ $ 1^|x−y| $ Δ … (משמאל ל־$ הראשון – תאים ריקים).
אם x = y התוצאה $$ (אפס).

בדיקה: לכל הזוגות 1 ≤ x, y ≤ 6 מתקבל $ 1^|x−y| $ במצב q7 (למשל 1#111 → $11$, 11#1 → $1$).

סעיף ד

תשובה
1.נכון: ⊢ # 1 1 Δ → ⊢ $ 1 1 $ Δ. 2. לא נכון: q6 מגיע לתא ⊢ ואין לו מעבר עליו – המכונה נתקעת ולא מגיעה ל־q7 (וגם חסר ה־$ השמאלי). 3. נכון: ⊢ # Δ → ⊢ $ $ Δ.

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

פתרון:

מקרה 1 – x = 0, y > 0: המכונה פועלת נכון.
q0 קורא מיד # ⇒ כותב $ ועובר ל־q8, שעובר על כל האחדים של y וכותב $ בתא הריק שאחריהם ⇒ q7. התוצאה y = |0 − y|.
דוגמה: קלט ⊢ # 1 1 Δ … ⇒ פלט ⊢ $ 1 1 $ Δ … (2 = |0 − 2|).

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

מקרה 3 – x = 0, y = 0: המכונה פועלת נכון.
q0 קורא # ⇒ כותב $ ועובר ל־q8; q8 קורא Δ ⇒ כותב $ ⇒ q7.
דוגמה: קלט ⊢ # Δ … ⇒ פלט ⊢ $ $ Δ … (אין אחדים בין ה־$ – התוצאה 0 = |0 − 0|).

בדיקה: x=0,y=2 → ⊢$11$ (q7); x=2,y=0 → נעצר ב־q6 עם ⊢11$; x=y=0 → ⊢$$ (q7).

פרק שני – תכנות מונחה עצמים

בחרו בשאלות מתוך מסלול אחד בלבד.

שאלה 12 (בנוסח C#: שאלה 15) · השכרת כלי רכב – ירושה, הכלה ופעולת תשלום (25 נקודות)

נוסח השאלה:

בחברה להשכרת כלֵי רכב "סעו לשלום" פותחה מערכת ממוחשבת שבה המחלקות האלה:
Contract – חוזה, Vehicle – כלִי רכב, Car – מכונית, Truck – משאית, Motorcycle – אופנוע.

להלן פירוט תכונות המחלקות:

•למחלקה חוזה (Contract) שלוש תכונות: name – שם לקוח (מחרוזת), days – מספר ימי השכרה (מטיפוס שלם),

kilo – מספר הקילומטרים שנסע הלקוח (מטיפוס שלם).

•למחלקה כלִי רכב (Vehicle) שתי תכונות: מזהה כלי רכב – id (מחרוזת), חוזה – contract (Contract).
•למחלקה מכונית (Car) שלוש תכונות: מזהה כלי רכב – id (מחרוזת), חוזה – contract (Contract),

מספר מקומות ישיבה – seats (מטיפוס שלם).

•למחלקה משאית (Truck) שלוש תכונות: מזהה כלי רכב – id (מחרוזת), חוזה – contract (Contract),

משקל מקסימלי להעמסה – max (מטיפוס שלם).

•למחלקה אופנוע (Motorcycle) שלוש תכונות: מזהה כלי רכב – id (מחרוזת), חוזה – contract (Contract),

אופנוע שטח – offRoad (בוליאני. אם האופנוע הוא אופנוע שטח התכונה היא אמת ואם לא, היא שקר).

א.(1)

סרטטו תרשים הייררכייה המתאר את הקשר בין המחלקות של המערכת הממוחשבת.
יש לסמן ירושה באמצעות החץ

והכלה באמצעות הסימן

.

(2)

כתבו את כותרות המחלקות ואת התכונות שלהן. הניחו שהפעולות get ו־ set קיימות בכל התכונות של המחלקות,
ואין צורך לממש אותן.

ב.(1)

נתונה הפעולה הבונה של המחלקה Contract :

Java
public Contract (String name, int days, int kilo)

אין צורך לממש את הפעולה.

(1) לפניכם כותרת הפעולה הבונה של המחלקה Vehicle . הפעולה מקבלת שם לקוח, מספר ימי השכרה,
מספר קילומטרים שנסע הלקוח ומזהה כלי הרכב.

Java
public Vehicle (String name, int days, int kilo, String id)

ממשו את הפעולה הבונה.

(2)

לפניכם כותרת הפעולה הבונה של המחלקה Car . הפעולה מקבלת שם לקוח, מספר ימי השכרה, מספר קילומטרים
שנסע הלקוח, מזהה כלי הרכב ומספר מקומות ישיבה.

Java
public Car (String name, int days, int kilo, String id, int seats)

ממשו את הפעולה הבונה.

ג.(1)

התעריף הבסיסי שהחברה גובה על השכרת כלִי רכב – Vehicle הוא 60 שקלים ליום השכרה ו־ 2 שקלים לכל קילומטר
של נסיעה.
מחיר ההשכרה של מכונית (Car) הוא לפי התעריף הבסיסי.
מחיר ההשכרה של משאית (Truck) הוא לפי התעריף הבסיסי ונוסף על כך סכום חד־פעמי של 500 שקלים.
מחיר ההשכרה של אופנוע (Motorcycle) הוא מחצית מן התעריף הבסיסי.

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

(1) כתבו את הפעולה payment במחלקה Vehicle (כאמור לעיל, הסכום לתשלום הוא לפי התעריף הבסיסי).

(2)

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

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

◂ פתרון מלא לשאלה 12

סעיף א(1)

תשובה

Car, Truck ו־Motorcycle יורשות מ־Vehicle (חץ ירושה אל Vehicle); Vehicle מכילה עצם מטיפוס Contract (הכלה, המעוין בצד של Vehicle).

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

רעיון – מכונית, משאית ואופנוע הם סוגים של כלי רכב ("is-a") ⇒ הן יורשות מ־Vehicle. לכל כלי רכב יש חוזה ("has-a") ⇒ הכלה: ב־Vehicle יש תכונה contract מטיפוס Contract. התכונות id ו־contract שמופיעות גם בפירוט של Car, Truck ו־Motorcycle הן בדיוק התכונות שעוברות אליהן בירושה מ־Vehicle – לכן לא מגדירים אותן שוב, וגם לא מחברים את Contract ישירות לכל אחת מהן.

פתרון

   Contract ───────────◆ Vehicle
                            △
            ┌───────────────┼───────────────┐
            │               │               │
           Car            Truck         Motorcycle
•חץ ירושה (משולש ריק) יוצא מכל אחת מהמחלקות Car, Truck, Motorcycle ומצביע אל Vehicle.
•קו הכלה בין Vehicle ל־Contract, והמעוין המלא בצד של המחלקה המכילה – Vehicle.

בדיקה – Car "היא" Vehicle ✓, Truck "היא" Vehicle ✓, Motorcycle "היא" Vehicle ✓; ל־Vehicle "יש" Contract ✓; חוזה אינו כלי רכב, לכן אין ירושה בין Contract ל־Vehicle.

טעות נפוצה: לסמן ירושה בין Vehicle ל־Contract, או לסמן הכלה של Contract בכל אחת משלוש המחלקות היורשות (החוזה כבר נמצא ב־Vehicle ועובר בירושה).

סעיף א(2)

תשובה

Contract: name, days, kilo; Vehicle: id, contract; Car extends Vehicle: seats; Truck extends Vehicle: max; Motorcycle extends Vehicle: offRoad.

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

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

פתרון

public class Contract {
    private String name;
    private int days;
    private int kilo;
}

public class Vehicle {
    private String id;
    private Contract contract;
}

public class Car extends Vehicle {
    private int seats;
}

public class Truck extends Vehicle {
    private int max;
}

public class Motorcycle extends Vehicle {
    private boolean offRoad;
}

בדיקה – שני הקבצים עוברים הידור (Java ו־C#), וכל עצם Car/Truck/Motorcycle מכיל גם את id ו־contract שירש מ־Vehicle.

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

הקוד המלא
public class Contract {
    private String name;
    private int days;
    private int kilo;
}

public class Vehicle {
    private String id;
    private Contract contract;
}

public class Car extends Vehicle {
    private int seats;
}

public class Truck extends Vehicle {
    private int max;
}

public class Motorcycle extends Vehicle {
    private boolean offRoad;
}

סעיף ב(1)

תשובה

this.contract = new Contract(name, days, kilo); this.id = id;

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

רעיון – Vehicle מכילה חוזה, ולכן הפעולה הבונה יוצרת עצם Contract חדש מהנתונים שקיבלה (name, days, kilo) בעזרת הפעולה הבונה הנתונה של Contract, ושומרת אותו בתכונה contract. את id שומרים ישירות.

פתרון

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

Java
    public Vehicle(String name, int days, int kilo, String id) {
        this.contract = new Contract(name, days, kilo);
        this.id = id;
    }

C# (בתוך המחלקה Vehicle):

C#
    public Vehicle(string name, int days, int kilo, string id)
    {
        this.contract = new Contract(name, days, kilo);
        this.id = id;
    }

בדיקה – new Vehicle("Dana", 3, 100, "11-111-11") יוצר חוזה עם 3 ימים ו־100 ק"מ, ו־payment שלו מחזיר 380 (ראו סעיף ג).

טעות נפוצה: לכתוב this.name = name וכו' בתוך Vehicle – ל־Vehicle אין תכונות כאלה; הנתונים שייכים לעצם ה־Contract.

הקוד המלא
    public Vehicle(String name, int days, int kilo, String id) {
        this.contract = new Contract(name, days, kilo);
        this.id = id;
    }

סעיף ב(2)

תשובה

Java: super(name, days, kilo, id); this.seats = seats; C#: : base(name, days, kilo, id) { this.seats = seats; }

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

רעיון – התכונות id ו־contract פרטיות ב־Vehicle, ולכן Car לא יכולה לאתחל אותן בעצמה – היא מעבירה את ארבעת הנתונים הראשונים לפעולה הבונה של מחלקת־העל (super(...) ב־Java, : base(...) ב־C#), ואחר כך מאתחלת את התכונה שלה – seats. ב־Java הקריאה ל־super חייבת להיות השורה הראשונה.

פתרון

public class Car extends Vehicle {
    private int seats;

    public Car(String name, int days, int kilo, String id, int seats) {
        super(name, days, kilo, id);
        this.seats = seats;
    }
}

בדיקה – new Car("Dana", 3, 100, "22-222-22", 5) תקין בשתי השפות; התשלום שלו 380 (כמו Vehicle עם אותו חוזה).

הקוד המלא
public class Car extends Vehicle {
    private int seats;

    public Car(String name, int days, int kilo, String id, int seats) {
        super(name, days, kilo, id);
        this.seats = seats;
    }
}

סעיף ג(1)

תשובה

Java: return 60 * this.contract.getDays() + 2 * this.contract.getKilo(); (C#: public virtual double Payment() עם GetDays/GetKilo)

מה נדרש – לכתוב ב־Vehicle פעולה שמחזירה את התשלום לפי התעריף הבסיסי: 60 ש"ח ליום ועוד 2 ש"ח לק"מ.

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

פתרון

(בתוך Vehicle):

    public double payment() {
        return 60 * this.contract.getDays() + 2 * this.contract.getKilo();
    }

בדיקה – 3 ימים ו־100 ק"מ: 60·3 + 2·100 = 180 + 200 = 380. התוצאה: 380 בשתי השפות.

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

הקוד המלא
    public double payment() {
        return 60 * this.contract.getDays() + 2 * this.contract.getKilo();
    }

סעיף ג(2)

תשובה

Car – אין צורך (יורשת את התעריף הבסיסי). Truck: return super.payment() + 500; Motorcycle: return super.payment() / 2; (C#: override ו־base.Payment())

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

רעיון – זהו פולימורפיזם: כל מחלקה דורסת את payment לפי הכלל שלה, והפעולה המתאימה נבחרת בזמן ריצה לפי סוג העצם שזימן אותה. מכונית משלמת לפי התעריף הבסיסי – לכן לא כותבים payment ב־Car, והיא יורשת אותה מ־Vehicle. במשאית ובאופנוע משתמשים בחישוב הבסיסי דרך super.payment() (ב־C# base.Payment()) – כך לא משכפלים את הנוסחה ולא צריך גישה לחוזה הפרטי. ב־C# הפעולות היורשות מסומנות override (והפעולה ב־Vehicle virtual).

פתרון

public class Truck extends Vehicle {
    private int max;

    public Truck(String name, int days, int kilo, String id, int max) {
        super(name, days, kilo, id);
        this.max = max;
    }

    public double payment() {
        return super.payment() + 500;
    }
}

public class Motorcycle extends Vehicle {
    private boolean offRoad;

    public Motorcycle(String name, int days, int kilo, String id, boolean offRoad) {
        super(name, days, kilo, id);
        this.offRoad = offRoad;
    }

    public double payment() {
        return super.payment() / 2;
    }
}

בדיקה – מערך Vehicle[] עם Vehicle, Car, Truck ו־Motorcycle (3 ימים, 100 ק"מ): 380, 380, 880 (=380+500), 190 (=380/2). אופנוע ליום אחד ו־5 ק"מ: (60+10)/2 = 35. כל התוצאות זהות ב־Java וב־C#.

טעות נפוצה: ב־C# לשכוח virtual/override – אז זימון דרך הפניה מטיפוס Vehicle יפעיל את הגרסה של Vehicle. וגם: לכתוב payment מיותרת ב־Car, או לבדוק את סוג העצם (instanceof / is) במקום לדרוס.

הקוד המלא
public class Truck extends Vehicle {
    private int max;

    public Truck(String name, int days, int kilo, String id, int max) {
        super(name, days, kilo, id);
        this.max = max;
    }

    public double payment() {
        return super.payment() + 500;
    }
}

public class Motorcycle extends Vehicle {
    private boolean offRoad;

    public Motorcycle(String name, int days, int kilo, String id, boolean offRoad) {
        super(name, days, kilo, id);
        this.offRoad = offRoad;
    }

    public double payment() {
        return super.payment() / 2;
    }
}

שאלה 13 (בנוסח C#: שאלה 16) · פעולות בונות לפי תרשים עצמים (25 נקודות)

נוסח השאלה:

לפניכם כותרות המחלקות BB , AA והתכונות שלהן.
הפעולות הבונות של המחלקות מסומנות ב־ * (תיתכן יותר מפעולה בונה אחת למחלקה).

Java
public class AA
{
    private int x;
    ***
}
public class BB extends AA
{
    private AA f;
    ***
}

הערה: שימו לב – לשתי המחלקות אין פעולות get ו־ set .

לפניכם המחלקה Test , הכוללת פעולה ראשית:

Java
public class Test{
    public static void main(String[] args) {
        AA a1 = new AA ();
        AA a2  = new AA (8);
        AA a3 = new AA (3);
        AA a4 = new AA (a1);
        AA a5 = new AA (a2);
        BB b1 = new BB ();
        BB b2 = new BB (6, a4);
        BB b3 = new BB (5, a2);
        BB b4 = new BB (a4);
        BB b5 = new BB (a2);
    }
}

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

◂ פתרון מלא לשאלה 13

פתרון

תשובה

AA: AA() { x = 2 }, AA(int x), AA(AA other) { x = other.x }. BB: BB() { super(1); f = null }, BB(int x, AA f) { super(x); this.f = f }, BB(AA f) { super(0); this.f = new AA(f) }.

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

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

•new AA () נותן x = 2, ולכן AA() מציבה 2.
•a4 = new AA (a1) הוא עצם נפרד (קופסה משלו) עם x = 2 – פעולה בונה מעתיקה. היא כתובה בתוך AA, ולכן מותר לה לקרוא את other.x למרות שהתכונה פרטית.
•x פרטית ב־AA, ולכן BB קובעת אותה רק דרך super(...)/base(...). new BB () נותן x = 1 – לכן super(1) (ולא super(), שהיה נותן 2).
•ב־b2 ו־b3 כתוב f = a4 / f = a2: התכונה f מפנה לאותו עצם שהתקבל – מעתיקים את ההפניה בלבד.
•ב־b4 ו־b5 התכונה f מפנה לעצם AA חדש (קופסה נוספת מתחת) עם אותו x כמו a4/a2, ו־x של BB הוא 0. BB לא יכולה לקרוא את x של הפרמטר (פרטית ב־AA, ואין get), ולכן יוצרים את ההעתק בעזרת הפעולה הבונה המעתיקה: new AA(f).

פתרון

public class AA
{
    private int x;

    public AA()
    {
        this.x = 2;
    }

    public AA(int x)
    {
        this.x = x;
    }

    public AA(AA other)
    {
        this.x = other.x;
    }
}

public class BB extends AA
{
    private AA f;

    public BB()
    {
        super(1);
        this.f = null;
    }

    public BB(int x, AA f)
    {
        super(x);
        this.f = f;
    }

    public BB(AA f)
    {
        super(0);
        this.f = new AA(f);
    }
}

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

עצםהקריאההפעולה הבונהמה מתקבל
a1new AA ()AA()x = 2
a2new AA (8)AA(int x)x = 8
a3new AA (3)AA(int x)x = 3
a4new AA (a1)AA(AA other) – פעולה בונה מעתיקהעצם חדש עם x = 2 (כמו a1)
a5new AA (a2)AA(AA other)עצם חדש עם x = 8
b1new BB ()BB()x = 1, f = null
b2new BB (6, a4)BB(int x, AA f)x = 6, f מפנה אל a4 עצמו
b3new BB (5, a2)BB(int x, AA f)x = 5, f מפנה אל a2 עצמו
b4new BB (a4)BB(AA f)x = 0, f מפנה לעצם AA חדש עם x = 2 (העתק של a4)
b5new BB (a2)BB(AA f)x = 0, f מפנה לעצם AA חדש עם x = 8 (העתק של a2)

בדיקה – ערכי השדות של כל עצם אחרי Test: a1…a5 = 2, 8, 3, 2, 8; b1: x=1, f=null; b2: x=6, f הוא a4 עצמו; b3: x=5, f הוא a2 עצמו; b4: x=0, f עצם חדש עם x=2; b5: x=0, f עצם חדש עם x=8; ו־a4 אינו a1 – הכול תואם לתרשים.

טעות נפוצה: ב־b4/b5 לכתוב this.f = f – אז f היה מפנה ל־a4/a2 עצמם (כמו ב־b2), ולא לעצם חדש כפי שבתרשים. ולהפך: ב־b2/b3 ליצור העתק במקום לשמור את ההפניה.

הקוד המלא
public class AA
{
    private int x;

    public AA()
    {
        this.x = 2;
    }

    public AA(int x)
    {
        this.x = x;
    }

    public AA(AA other)
    {
        this.x = other.x;
    }
}

public class BB extends AA
{
    private AA f;

    public BB()
    {
        super(1);
        this.f = null;
    }

    public BB(int x, AA f)
    {
        super(x);
        this.f = f;
    }

    public BB(AA f)
    {
        super(0);
        this.f = new AA(f);
    }
}

שאלה 14 (בנוסח C#: שאלה 17) · מעקב – ירושה, דריסה והעמסה (AA ו־BB) (25 נקודות)

נוסח השאלה:

נתונות המחלקות BB , AA :

Java
public class AA {
    private int x;

    public AA() { this.x = 4; }
    public AA(int x) { this.x = x; }
    public int getX() { return this.x; }
    public void foo() { this.x = 3; }
    public void goo() { this.x = this.x + 3; }
    public void bar() { goo(); }
    public String toString() { return "x = " + this.x; }
}

public class BB extends AA {
    private int y;

    public BB() {
        super();
        this.y = 2;
    }
    public BB (int a) {
        super (a);
        this.y = getX() * 2;
    }
    public BB (int a, int b) {
        super (a);
        this.y = b;
    }
    public int getY() { return this.y; }
    public void foo() { this.y = 5; }
    public void goo() { this.y = getX() - 1; }
    public void bar (int a) {
        this.y = a + getX() + this.y;
    }
    public String toString() {
        return super.toString() + "  y = " + this.y;
    }
}
א.

לפניכם קטע קוד:

Java
AA[] items = new AA[6];
items[0] = new AA();
items[1] = new BB();
items[2] = new AA(2);
items[3] = new BB(2);
items[4] = new BB(1, 22);
items[5] = items[4];
for (int i = 0; i < items.length; i++)
    System.out.println(items[i]);

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

ב.

לפניכם המשך קטע הקוד:

Java
items[0].foo();
items[1].goo();
((AA) items[3]).goo();
items[4].bar();
BB temp = new BB(1);
temp.bar();
System.out.println("Temp: " + temp);
temp.bar(9);
items[2] = temp;
for (int i = 0; i < items.length; i++)
    System.out.println(items[i]);

כתבו מה הקוד מדפיס.

◂ פתרון מלא לשאלה 14

סעיף א

תשובה
x = 4
x = 4  y = 2
x = 2
x = 2  y = 4
x = 1  y = 22
x = 1  y = 22

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

רעיון – לכל new רצה הפעולה הבונה המתאימה לפרמטרים. הפעולות הבונות של BB קוראות קודם לפעולה הבונה של AA (super/base). items[5] = items[4] לא יוצרת עצם – שני התאים מפנים לאותו עצם. ההדפסה מזמנת את toString של העצם בפועל: ב־BB היא מחזירה את המחרוזת של AA ועוד " y = " (בקוד המודפס יש שני רווחים לפני y, ולכן גם בפלט יש שני רווחים בין x ל־y).

פתרון

שורהפעולה בונה שרצהxy
items[0] = new AA()AA()4–
items[1] = new BB()BB() → AA() נותן x=4, ואז y=242
items[2] = new AA(2)AA(int x)2–
items[3] = new BB(2)BB(int a) → AA(2), ואז y = getX()·2 = 424
items[4] = new BB(1, 22)BB(int a, int b) → AA(1), ואז y = 22122
items[5] = items[4]אין עצם חדש – העתקת הפניה(1)(22)

העצמים (5 עצמים בלבד):

items[0] ──► AA  x = 4
items[1] ──► BB  x = 4, y = 2
items[2] ──► AA  x = 2
items[3] ──► BB  x = 2, y = 4
items[4] ──► BB  x = 1, y = 22  ◄── items[5]   (אותו עצם!)

הפלט:

x = 4
x = 4  y = 2
x = 2
x = 2  y = 4
x = 1  y = 22
x = 1  y = 22

בדיקה – הפלט של הקוד הנתון זהה ב־Java וב־C# ותואם לטבלה.

טעות נפוצה: לצייר עצם שישי עבור items[5]; או לחשוב ש־new BB() נותן x = 0 – בפועל super() מפעילה את AA() שמציבה 4.

סעיף ב

תשובה
Temp: x = 1  y = 0
x = 3
x = 4  y = 3
x = 1  y = 10
x = 2  y = 1
x = 1  y = 0
x = 1  y = 0

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

רעיון – הפעולה שרצה נקבעת לפי סוג העצם בזמן ריצה (דריסה): foo ו־goo דרוסות ב־BB. ל־BB אין bar() בלי פרמטרים – יש לה רק bar(int) (העמסה), ולכן bar() על עצם BB מפעילה את AA.bar, וזו קוראת ל־goo() – שגם כאן נבחרת לפי סוג העצם, כלומר BB.goo. ב־C# זה זהה: Foo ו־Goo מוגדרות virtual ונדרסות ב־override, ו־Bar של AA (שאינה virtual) קוראת ל־Goo הווירטואלית. (בשאלון הביטוי getX() – 1 מודפס עם קו מפריד ארוך; זהו סימן המינוס הרגיל, ובקוד שלפניכם הוא נכתב -.)

פתרון

פקודהטיפוס בזמן ריצהאיזו פעולה רצה בפועלשינוי
items[0].foo()AAAA.fooitems[0]: x = 3
items[1].goo()BBBB.goo (דריסה)items[1]: y = getX() − 1 = 4 − 1 = 3
((AA) items[3]).goo()BBההמרה ל־AA לא משנה את סוג העצם ⇒ BB.gooitems[3]: y = 2 − 1 = 1
items[4].bar()BBAA.bar (ל־BB אין bar בלי פרמטרים) ← קוראת ל־goo() ⇒ BB.gooitems[4] (וגם items[5]): y = 1 − 1 = 0
BB temp = new BB(1)BBBB(int a)temp: x = 1, y = 1·2 = 2
temp.bar()BBAA.bar ← BB.gootemp: y = 1 − 1 = 0
הדפסהBB.toString ← super.toString()Temp: x = 1 y = 0
temp.bar(9)BBBB.bar(int a) (העמסה)temp: y = 9 + 1 + 0 = 10
items[2] = tempitems[2] מפנה עכשיו ל־temp

מצב המערך בסוף: items[0] → AA x=3; items[1] → BB x=4, y=3; items[2] → temp (x=1, y=10); items[3] → BB x=2, y=1; items[4] ו־items[5] → אותו BB x=1, y=0.

הפלט:

Temp: x = 1  y = 0
x = 3
x = 4  y = 3
x = 1  y = 10
x = 2  y = 1
x = 1  y = 0
x = 1  y = 0

בדיקה – הפלט של ההמשך (אחרי סעיף א) זהה ב־Java וב־C# ותואם לטבלה. שימו לב ש־x של עצמי BB לא משתנה אף פעם, כי AA.goo ו־AA.foo לא רצות על עצמי BB.

טעות נפוצה: לחשוב ש־((AA) items[3]).goo() מפעילה את AA.goo – ההמרה משנה רק את הטיפוס של ההפניה, לא את העצם. וגם לשכוח ש־items[5] הוא אותו עצם כמו items[4], ולכן גם הוא מודפס עם y = 0.

טבלת התשובות
שאלהסעיףתשובה
1א

מעבירים את כל איברי התור לתור עזר תוך ספירת המקום; שומרים את האיבר במקום m−1 ואת האיבר במקום m, וכשמגיעים למקום m+1 בודקים before + x == cur (רק אם m > 1). בסוף מחזירים את האיברים לתור. אם m = 1 או m הוא המקום האחרון – false.

ב

סופרים את גודל התור (ומחזירים את האיברים לתור), ואז בודקים isMagic(q, m) לכל m = n, 2n, 3n, … ≤ גודל התור. אם אחד מהם אינו איבר קסם – false, אחרת true.

2א

מעבירים את q לתור עזר. לפני החולה הראשון שרמת הדחיפות שלו נמוכה ממש מזו של p מכניסים את p. אם אין חולה כזה, p נכנס בסוף. אחר כך מחזירים את כל האיברים מתור העזר ל־q.

ב

מוציאים את החולה עם מספר הזהות id מהתור (שאר החולים נשארים באותו סדר), מעדכנים את רמת הדחיפות שלו: setPriority(pri), ומכניסים אותו מחדש עם priorityInsert מסעיף א.

3א(1)

הפעולה מחזירה את השרשרת 3 → 5 → 3 → 9 → 4 → null (שתי החוליות עם הערך 1 הוסרו).

א(2)

הפעולה מוחקת מהשרשרת lst את כל החוליות שהערך שלהן שווה ל־x (סדר שאר החוליות נשמר) ומחזירה הפניה לראש השרשרת החדשה (null אם לא נשארו חוליות).

א(3)

O(n), כאשר n הוא מספר החוליות בשרשרת: קריאה רקורסיבית אחת לכל חוליה (ועוד אחת ל־null), ובכל קריאה עבודה קבועה.

ב(1)

בסיום הפעולה: lst = 1 → 3 → 5 → 9 → 4 → null.

ב(2)

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

ב(3)

O(n²), כאשר n הוא מספר החוליות: לכל חוליה מופעלת what על ההמשך שלה, שאורכו עד n−1, n−2, …, 0. הסכום הוא n(n−1)/2.

4א

חיפוש סדרתי במערך arr בתאים 0 עד amount−1: אם arr[i] == n מחזירים true. בסוף הלולאה מחזירים false.

ב

עוברים על הקווים של התחנה הראשונה arr[0]. לכל קו בודקים בעזרת isStopping אם הוא עוצר בכל שאר התחנות. אם כן – מוסיפים אותו כחוליה חדשה לראש השרשרת. בסוף מחזירים את השרשרת.

5א

עוברים פעם אחת על השרשרת וסופרים מקומות. שומרים את המקום של num (posNum) ואת המקום של −num (posOpp). אם −num לא נמצא – מחזירים −1, אחרת מחזירים |posNum − posOpp| + 1.

ב

max = −1. לכל ערך v בשרשרת מחשבים width(lst, v) ומעדכנים את max אם התוצאה גדולה יותר. מחזירים את max (נשאר −1 אם אין אף תת־סדרה נגדית).

6א

סריקת BFS (או DFS) מ־ vⱼ : כל קודקוד שמתגלה בסריקה (חוץ מ־ vⱼ עצמו) מוחזר. זמן ריצה O(|V| + |E|). בדוגמה מ־3 מתגלים 7, 0, 9, 6.

ב

עוברים על הקודקודים v₀…vₙ₋₁; מכל קודקוד שעוד לא סומן מריצים BFS שאוסף את רכיב הקשירות שלו; שומרים את הרכיב בעל מספר הקודקודים הקטן ביותר. זמן ריצה O(|V| + |E|). בדוגמה: הרכיבים בגדלים 5, 2, 3 ⇒ מוחזר {1, 5}.

7א

לא נכונה. דוגמה נגדית: הגרף השלם K₄ – עץ DFS שלו הוא מסלול a–b–c–d, ואילו כל עץ BFS שלו הוא "כוכב" (השורש מחובר ישירות לשלושת האחרים).

ב

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

ג

נכונה. לכל שני קודקודים u, w: יש מסלול u ⇝ v ומסלול v ⇝ w, ושרשורם הוא מסלול u ⇝ w. לכן בין כל שני קודקודים יש מסלולים בשני הכיוונים.

ד

נכונה. אילו היה מסלול קצר יותר מ־sₘ ל־sₖ, היינו מחליפים בו את הקטע sₘ…sₖ ומקבלים מסלול מ־sⱼ ל־sₙ קצר יותר מ־S – בסתירה לכך ש־S הקצר ביותר.

ה

לא נכונה. דוגמה נגדית: מעגל באורך 4, a–b–c–d–a, הוא גרף דו־צדדי: {a, c} ו־{b, d}.

ו

לא נכונה. דוגמה נגדית: משולש a, b, c שבו משקל כל קשת 1 – כל שתי קשתות הן עץ פורש מינימלי במשקל 2, כלומר יש 3 עצים כאלה.

8א(1)

האלגוריתם של דייקסטרה מ־vⱼ: אתחול d[vⱼ]=0 ושאר d=∞; בכל איטרציה מעבירים מ־T ל־P את הקודקוד u בעל d מינימלי ומרפים את הקשתות שלו (אם d[u]+w(u,v) < d[v] אז d[v] ← d[u]+w(u,v), π[v] ← u). המסלולים נקראים לאחור לפי π.

א(2)

O(n²) (מימוש במערך). עם ערימת מינימום: O((n + |E|)·log n).

ב(1)

d/π: S 0/– , G 2/S , C 9/G , H 10/G , B 12/G , D 16/H , I 18/H , F 22/G. סדר הקביעה: S, G, C, H, B, D, I, F.

ב(2)

קשתות העץ (π[v] – v): S–G, G–B, G–C, G–F, G–H, H–D, H–I.

9א(1)

לא נכונה. L₁ = {aⁿbⁿ | n ≥ 0}, L₂ = {bⁿaⁿ | n ≥ 0} – שתיהן לא רגולריות, אבל L₁ ∩ L₂ = {ε}, שפה סופית ולכן רגולרית.

א(2)

לא נכונה. L₁ = {a}, L₂ = {b}, n = 2: (L₁•L₂)² = {abab}, ואילו L₁²•L₂² = {aabb}.

ב(1)

cbbba ∈ L ; baa ∈ L ; ε ∈ L ; aab ∉ L (מכילה ab) ; aaccc ∉ L (5 מופעים של a ו־c – אי־זוגי).

ב(2)

6 מצבים (זוגיות של #a+#c × האות האחרונה): q0 (התחלה, זוגי), q1, q2, q3, q4, q5; מקבלים: q0, q2, q4. מעברים: q0: a→q3, b→q4, c→q1 ; q1: a→q2, b→q5, c→q0 ; q2: a→q3, c→q1 ; q3: a→q2, c→q0 ; q4: a→q3, b→q4 ; q5: a→q2, b→q5 (מעבר חסר = דחייה).

10א(1)

L₅ ∩ L₆ = {110}

א(2)

L₂ᴿ = Σ* = L₂

א(3)

L₁ • L₆ = Ø

א(4)

L₃ • L₄ = {0110}

א(5)

L₄ • L₅ = {0110, 0110110, 011000, 0110001}

ב

דוחפים 3 סימנים לכל ab ו־1 לכל c (הסימן התחתון ביותר מסומן Y), ושולפים סימן אחד לכל b; מגיעים למצב המקבל q5 כששולפים את Y. מצבים מקבלים: q0 (בשביל ε) ו־q5. אין מעברי ε.

11א

המכונה עוצרת במצב q7 והסרט: ⊢ Δ $ 1 1 $ Δ Δ … (בין שני סימני $ – 11, כלומר 2 = 3 − 1).

ב

⊢ $ 1 $ Δ Δ … (המכונה עוצרת ב־q7).

ג

המכונה מחשבת את ההפרש בערך מוחלט |x − y| של שני המספרים: בסיום על הסרט Δ…Δ $ 1^|x−y| $ (התוצאה באונרי בין שני סימני $).

ד
1.נכון: ⊢ # 1 1 Δ → ⊢ $ 1 1 $ Δ. 2. לא נכון: q6 מגיע לתא ⊢ ואין לו מעבר עליו – המכונה נתקעת ולא מגיעה ל־q7 (וגם חסר ה־$ השמאלי). 3. נכון: ⊢ # Δ → ⊢ $ $ Δ.
12א(1)

Car, Truck ו־Motorcycle יורשות מ־Vehicle (חץ ירושה אל Vehicle); Vehicle מכילה עצם מטיפוס Contract (הכלה, המעוין בצד של Vehicle).

א(2)

Contract: name, days, kilo; Vehicle: id, contract; Car extends Vehicle: seats; Truck extends Vehicle: max; Motorcycle extends Vehicle: offRoad.

ב(1)

this.contract = new Contract(name, days, kilo); this.id = id;

ב(2)

Java: super(name, days, kilo, id); this.seats = seats; C#: : base(name, days, kilo, id) { this.seats = seats; }

ג(1)

Java: return 60 * this.contract.getDays() + 2 * this.contract.getKilo(); (C#: public virtual double Payment() עם GetDays/GetKilo)

ג(2)

Car – אין צורך (יורשת את התעריף הבסיסי). Truck: return super.payment() + 500; Motorcycle: return super.payment() / 2; (C#: override ו־base.Payment())

13-

AA: AA() { x = 2 }, AA(int x), AA(AA other) { x = other.x }. BB: BB() { super(1); f = null }, BB(int x, AA f) { super(x); this.f = f }, BB(AA f) { super(0); this.f = new AA(f) }.

14א
x = 4
x = 4  y = 2
x = 2
x = 2  y = 4
x = 1  y = 22
x = 1  y = 22
ב
Temp: x = 1  y = 0
x = 3
x = 4  y = 3
x = 1  y = 10
x = 2  y = 1
x = 1  y = 0
x = 1  y = 0

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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