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

מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2026 מועד ב'

הנדסת תוכנה · סמל 97105 · 9 שאלות · פתרון מלא לכל סעיף

מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2026 מועד ב', כל 9 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.

הנחיות הבחינה

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

מבנה השאלון: בשאלון זה שני מבחנים, עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:

מבחן ב- C# (עמוד 2)

מבחן ב- JAVA (עמוד 14)

בכל מבחן עשר שאלות.

חלק א' – 32 נקודות

שאלות 3–1: יש לענות על שתי שאלות בלבד. ערך כל שאלה 16 נקודות.

חלק ב' – 32 נקודות

שאלות 6–4: יש לענות על שתי שאלות בלבד. ערך כל שאלה 16 נקודות.

חלק ג' – 36 נקודות

שאלות 9–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.

בסך הכול: 100 נקודות.

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

2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.

אין לצרף ספרים או חוברות עם פתרונות.

שאלה 1 · מספרים מצטלבים ומחסניות

א.

שני מספרים שלמים וחיוביים num1 ו-num2 נקראים "מצטלבים" (crossed) אם יש להם בדיוק מחלק משותף אחד (פרט ל-1).

לדוגמה:

המספרים 14 ו-21 הם מצטלבים כי יש להם מחלק משותף אחד בלבד (7).

המספרים 3 ו-27 הם מצטלבים כי יש להם מחלק משותף אחד בלבד (3).

המספרים 8 ו-9 אינם מצטלבים כי אין להם שום מחלק משותף.

המספרים 12 ו-36 אינם מצטלבים כי יש להם יותר ממחלק משותף אחד (2, 3, 6, 12).

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

כותרת הפעולה:

Java:

public static boolean crossed(int num1, int num2)

C#:

public static bool Crossed(int num1, int num2)
(6 נקודות)
ב.

כתבו פעולה crossedStacks המקבלת שתי מחסניות של מספרים שלמים חיוביים st1 ו-st2. הפעולה תבדוק שלכל איבר במחסנית st1 יש איבר מצטלב במחסנית st2. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

(8 נקודות)
ג.

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

(2 נקודות)
◂ פתרון מלא לשאלה 1

סעיף א

תשובה:

הפעולה crossed שלהלן: סופרת את המחלקים המשותפים d בין 2 לבין המספר הקטן, ומחזירה true אם ורק אם נמצא בדיוק מחלק משותף אחד.

הרעיון: נבדוק את כל המחלקים האפשריים פרט ל-1. מחלק משותף של שני המספרים אינו יכול להיות גדול מהקטן מביניהם, ולכן מספיק לעבור על d מ-2 עד min⁡(num1,num2)\min(num1, num2). נספור כמה ערכים של d מחלקים את שני המספרים (שארית 0 בשתי החלוקות). המספרים "מצטלבים" אם ורק אם המונה שווה בדיוק ל-1.

1. `count = 0`, `min` - הקטן מבין שני המספרים.

2. לכל d מ-2 עד `min`: אם `num1 % d == 0` וגם `num2 % d == 0` - מגדילים את `count`.

3. מחזירים `count == 1`.

Java:

public static boolean crossed(int num1, int num2)
{
    int count = 0;                           // מספר המחלקים המשותפים (פרט ל-1)
    int min = Math.min(num1, num2);          // מחלק משותף אינו גדול מהקטן מביניהם
    for (int d = 2; d <= min; d++)
    {
        if (num1 % d == 0 && num2 % d == 0)  // d מחלק את שני המספרים
            count++;
    }
    return count == 1;
}

C#:

public static bool Crossed(int num1, int num2)
{
    int count = 0;                           // מספר המחלקים המשותפים (פרט ל-1)
    int min = Math.Min(num1, num2);          // מחלק משותף אינו גדול מהקטן מביניהם
    for (int d = 2; d <= min; d++)
    {
        if (num1 % d == 0 && num2 % d == 0)  // d מחלק את שני המספרים
            count++;
    }
    return count == 1;
}

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

- 14 ו-21: בין 2 ל-14 רק 7 מחלק את שניהם, `count = 1` ← true.

- 3 ו-27: d רץ מ-2 עד 3, רק 3 מחלק את שניהם ← true.

- 8 ו-9: אף d בין 2 ל-8 אינו מחלק את שניהם, `count = 0` ← false.

- 12 ו-36: המחלקים המשותפים 2, 3, 4, 6, 12, `count = 5` ← false.

(הערה: בדוגמה בשאלון מופיעים המחלקים 2, 3, 6, 12 - גם 4 הוא מחלק משותף של 12 ו-36, אבל המסקנה זהה.)

תשובה: הפעולה crossed שלמעלה.

סעיף ב

תשובה:

הפעולה crossedStacks שלהלן: לכל איבר x של st1 בודקת בעזרת פעולת העזר hasCrossed אם יש ב-st2 איבר y כך ש-crossed(x, y); מחזירה true רק אם לכל x נמצא איבר כזה. שתי המחסניות משוחזרות.

הרעיון: נשלוף את איברי st1 אחד אחד. לכל איבר x נחפש ב-st2 איבר y שמצטלב איתו, בעזרת הפעולה `crossed` מסעיף א'. אם לאיבר כלשהו של st1 לא נמצא איבר מצטלב - התשובה false.

החיפוש ב-st2 נעשה בפעולת עזר `hasCrossed`: היא שולפת את איברי st2 למחסנית עזר, בודקת כל איבר, ומחזירה אותם ל-st2 - כך st2 חוזרת למצבה המקורי לפני הבדיקה של האיבר הבא של st1. גם איברי st1 נשמרים במחסנית עזר ומוחזרים בסוף, כדי שהפעולה לא תהרוס את המחסניות שקיבלה. (אחרי שנמצא איבר בלי בן-זוג מצטלב, לא מחפשים יותר, אבל ממשיכים לשלוף כדי לשחזר את st1 בסדר הנכון.)

1. `ok = true`.

2. כל עוד st1 אינה ריקה: שולפים x ודוחפים ל-`temp1`; אם `ok` ועדיין אין ל-x איבר מצטלב ב-st2 (`hasCrossed(st2, x)` מחזירה false) - `ok = false`.

3. מחזירים את האיברים מ-`temp1` ל-st1.

4. מחזירים `ok`.

Java:

public static boolean crossedStacks(Stack<Integer> st1, Stack<Integer> st2)
{
    boolean ok = true;                        // לכל איבר שנבדק נמצא איבר מצטלב
    Stack<Integer> temp1 = new Stack<Integer>();
    while (!st1.isEmpty())
    {
        int x = st1.pop();
        temp1.push(x);
        if (ok && !hasCrossed(st2, x))        // ל-x אין איבר מצטלב ב-st2
            ok = false;
    }
    while (!temp1.isEmpty())                  // שחזור st1
        st1.push(temp1.pop());
    return ok;
}

// פעולת עזר: האם יש במחסנית st איבר מצטלב עם x (המחסנית נשמרת)
public static boolean hasCrossed(Stack<Integer> st, int x)
{
    boolean found = false;
    Stack<Integer> temp = new Stack<Integer>();
    while (!st.isEmpty())
    {
        int y = st.pop();
        temp.push(y);
        if (crossed(x, y))
            found = true;
    }
    while (!temp.isEmpty())                   // שחזור st
        st.push(temp.pop());
    return found;
}

C#:

public static bool CrossedStacks(Stack<int> st1, Stack<int> st2)
{
    bool ok = true;                        // לכל איבר שנבדק נמצא איבר מצטלב
    Stack<int> temp1 = new Stack<int>();
    while (!st1.IsEmpty())
    {
        int x = st1.Pop();
        temp1.Push(x);
        if (ok && !HasCrossed(st2, x))        // ל-x אין איבר מצטלב ב-st2
            ok = false;
    }
    while (!temp1.IsEmpty())                  // שחזור st1
        st1.Push(temp1.Pop());
    return ok;
}

// פעולת עזר: האם יש במחסנית st איבר מצטלב עם x (המחסנית נשמרת)
public static bool HasCrossed(Stack<int> st, int x)
{
    bool found = false;
    Stack<int> temp = new Stack<int>();
    while (!st.IsEmpty())
    {
        int y = st.Pop();
        temp.Push(y);
        if (Crossed(x, y))
            found = true;
    }
    while (!temp.IsEmpty())                   // שחזור st
        st.Push(temp.Pop());
    return found;
}

דוגמה: st1 = 14, 3, 10 (14 בראש), st2 = 21, 27, 15. ל-14 מצטלב 21 (מחלק משותף 7), ל-3 מצטלב 27 (3), ול-10 מצטלב 15 (5) ← true. אם במקום 15 יהיה ב-st2 המספר 9, ל-10 אין איבר מצטלב (10 זר ל-21, ל-27 ול-9) ← false. בשני המקרים המחסניות חוזרות למצבן המקורי.

תשובה: הפעולה crossedStacks (עם פעולת העזר hasCrossed) שלמעלה.

סעיף ג

תשובה:

סעיף א': O(min⁡(num1,num2))O(\min(num1,num2)); סעיף ב': O(n⋅m⋅k)O(n\cdot m\cdot k), כאשר n ו-m מספרי האיברים ב-st1 וב-st2 ו-k הערך הגדול ביותר במחסניות.

סעיף א': הלולאה רצה על d מ-2 עד min⁡(num1,num2)\min(num1,num2), ובכל סיבוב מתבצעות שתי פעולות שארית והשוואה - עבודה קבועה. לכן הסיבוכיות O(min⁡(num1,num2))O(\min(num1,num2)).

סעיף ב': נסמן ב-n את מספר האיברים ב-st1, ב-m את מספר האיברים ב-st2, וב-k את הערך הגדול ביותר במחסניות.

1. לכל אחד מ-n האיברים של st1 מזמנים את `hasCrossed`.

2. `hasCrossed` עוברת על m האיברים של st2 (שליפה ושחזור - O(m)O(m)), ולכל זוג מזמנת את `crossed`, שעולה O(k)O(k) לכל היותר. לכן זימון אחד של `hasCrossed` עולה O(m⋅k)O(m\cdot k).

3. שליפת איברי st1 ושחזורם - O(n)O(n).

4. בסך הכול: O(n⋅m⋅k)O(n\cdot m\cdot k). אם מתייחסים לבדיקת "מצטלבים" כפעולה בזמן קבוע (מספרים חסומים), הסיבוכיות היא O(n⋅m)O(n\cdot m).

תשובה: א' - O(min⁡(num1,num2))O(\min(num1,num2)); ב' - O(n⋅m⋅k)O(n\cdot m\cdot k) (או O(n⋅m)O(n\cdot m) אם בדיקת זוג נחשבת לפעולה קבועה).

שאלה 2 · הכלת ערכי תור בתור אחר

א.

כתבו פעולה המקבלת שני תורים של מספרים שלמים q1 ו-q2. הפעולה תבדוק אם כל הערכים של התור q1 נמצאים בתוך התור q2. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

לדוגמה: עבור התורים q1 ו-q2 הבאים הפעולה תחזיר ערך true (ראו איור לשאלה).

(7 נקודות)
ב.

כתבו פעולה המקבלת שני תורים של מספרים שלמים q1 ו-q2. הפעולה תבדוק אם כל הערכים של התור q1 נמצאים בתור q2 באותו הסדר. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

לדוגמה: עבור התורים q1 ו-q2 הבאים הפעולה תחזיר ערך true (ראו איור לשאלה).

(7 נקודות)
ג.

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

(2 נקודות)
◂ פתרון מלא לשאלה 2

סעיף א

תשובה:

הפעולה allInQueue שלהלן: לכל ערך x של q1 בודקת בעזרת פעולת העזר isIn אם x נמצא ב-q2; מחזירה true רק אם כל הערכים נמצאו. שני התורים משוחזרים.

בשאלון לא ניתנה כותרת, ולכן נקרא לפעולה `allInQueue` (ב-C#: `AllInQueue`). (בתורים שבאיור ראש התור משמאל.)

הרעיון: נעבור על הערכים של q1 אחד אחד, ולכל ערך x נחפש אותו ב-q2. בתור אפשר לראות רק את האיבר שבראשו, ולכן כדי לחפש ב-q2 נוציא ממנו את כל האיברים לתור עזר תוך כדי השוואה ל-x, ואחר כך נחזיר אותם ל-q2 (כך הסדר נשמר). את החיפוש נכתוב בפעולת עזר `isIn`. גם איברי q1 עוברים לתור עזר ומוחזרים בסוף, כדי שהתורים לא ייהרסו.

1. `ok = true`.

2. כל עוד q1 אינו ריק: מוציאים x ומכניסים ל-`temp`; אם `ok` ו-x לא נמצא ב-q2 - `ok = false`.

3. מחזירים את האיברים מ-`temp` ל-q1 (באותו הסדר).

4. מחזירים `ok`.

Java:

public static boolean allInQueue(Queue<Integer> q1, Queue<Integer> q2)
{
    boolean ok = true;
    Queue<Integer> temp = new Queue<Integer>();
    while (!q1.isEmpty())
    {
        int x = q1.remove();
        temp.insert(x);
        if (ok && !isIn(q2, x))       // x לא נמצא בתור q2
            ok = false;
    }
    while (!temp.isEmpty())           // שחזור q1
        q1.insert(temp.remove());
    return ok;
}

// פעולת עזר: האם x נמצא בתור q (התור נשמר)
public static boolean isIn(Queue<Integer> q, int x)
{
    boolean found = false;
    Queue<Integer> temp = new Queue<Integer>();
    while (!q.isEmpty())
    {
        int y = q.remove();
        temp.insert(y);
        if (y == x)
            found = true;
    }
    while (!temp.isEmpty())           // שחזור q
        q.insert(temp.remove());
    return found;
}

C#:

public static bool AllInQueue(Queue<int> q1, Queue<int> q2)
{
    bool ok = true;
    Queue<int> temp = new Queue<int>();
    while (!q1.IsEmpty())
    {
        int x = q1.Remove();
        temp.Insert(x);
        if (ok && !IsIn(q2, x))       // x לא נמצא בתור q2
            ok = false;
    }
    while (!temp.IsEmpty())           // שחזור q1
        q1.Insert(temp.Remove());
    return ok;
}

// פעולת עזר: האם x נמצא בתור q (התור נשמר)
public static bool IsIn(Queue<int> q, int x)
{
    bool found = false;
    Queue<int> temp = new Queue<int>();
    while (!q.IsEmpty())
    {
        int y = q.Remove();
        temp.Insert(y);
        if (y == x)
            found = true;
    }
    while (!temp.IsEmpty())           // שחזור q
        q.Insert(temp.Remove());
    return found;
}

בדיקה על הדוגמה: q1 = 2, 10, 12, 3 ו-q2 = 8, 10, 11, 2, 3, 16, 12, 4 (משמאל - ראש התור). כל אחד מהערכים 2, 10, 12, 3 נמצא ב-q2 (האיברים המודגשים באיור), ולכן מוחזר true. עבור q1 = 2, 5 מוחזר false, כי 5 אינו ב-q2.

תשובה: הפעולה allInQueue (עם פעולת העזר isIn) שלמעלה.

סעיף ב

תשובה:

הפעולה inSameOrder שלהלן: עוברת פעם אחת על q2 ומוציאה מהעתק של q1 את האיבר שבראשו בכל פעם שהוא מופיע ב-q2; מחזירה true אם ההעתק התרוקן. שני התורים משוחזרים.

נקרא לפעולה `inSameOrder` (ב-C#: `InSameOrder`).

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

•נכין העתק `copy` של q1 (ונשחזר את q1).

•לכל איבר y של q2: אם `copy` אינו ריק ו-y שווה לאיבר שבראש `copy` - מצאנו את הערך הבא של q1 במקום מאוחר יותר ב-q2, ומוציאים אותו מ-`copy`.

•בסוף המעבר: אם `copy` ריק - כל הערכים של q1 נמצאו לפי הסדר.

למה זה נכון? מתאימים כל ערך של q1 למופע הראשון שלו ב-q2 אחרי המקום שבו נמצא הערך הקודם. אם יש התאמה כלשהי לפי הסדר, גם הבחירה ה"מוקדמת ביותר" הזאת מצליחה, כי היא משאירה את מירב האיברים של q2 לערכים הבאים.

1. מעתיקים את q1 ל-`copy` (ומחזירים את q1 מ-`temp`).

2. מוציאים את איברי q2 אחד אחד ל-`temp`; אם `copy` אינו ריק וראשו שווה לאיבר - `copy.remove()`.

3. מחזירים את q2 מ-`temp`.

4. מחזירים `copy.isEmpty()`.

Java:

public static boolean inSameOrder(Queue<Integer> q1, Queue<Integer> q2)
{
    // copy - העתק של q1: ממנו נוציא כל איבר שנמצא ב-q2 בתורו
    Queue<Integer> copy = new Queue<Integer>();
    Queue<Integer> temp = new Queue<Integer>();
    while (!q1.isEmpty())
    {
        int x = q1.remove();
        copy.insert(x);
        temp.insert(x);
    }
    while (!temp.isEmpty())           // שחזור q1
        q1.insert(temp.remove());

    while (!q2.isEmpty())             // מעבר אחד על q2
    {
        int y = q2.remove();
        temp.insert(y);
        if (!copy.isEmpty() && copy.head() == y)  // נמצא האיבר הבא של q1
            copy.remove();
    }
    while (!temp.isEmpty())           // שחזור q2
        q2.insert(temp.remove());

    return copy.isEmpty();            // כל איברי q1 נמצאו לפי הסדר
}

C#:

public static bool InSameOrder(Queue<int> q1, Queue<int> q2)
{
    // copy - העתק של q1: ממנו נוציא כל איבר שנמצא ב-q2 בתורו
    Queue<int> copy = new Queue<int>();
    Queue<int> temp = new Queue<int>();
    while (!q1.IsEmpty())
    {
        int x = q1.Remove();
        copy.Insert(x);
        temp.Insert(x);
    }
    while (!temp.IsEmpty())           // שחזור q1
        q1.Insert(temp.Remove());

    while (!q2.IsEmpty())             // מעבר אחד על q2
    {
        int y = q2.Remove();
        temp.Insert(y);
        if (!copy.IsEmpty() && copy.Head() == y)  // נמצא האיבר הבא של q1
            copy.Remove();
    }
    while (!temp.IsEmpty())           // שחזור q2
        q2.Insert(temp.Remove());

    return copy.IsEmpty();            // כל איברי q1 נמצאו לפי הסדר
}

בדיקה על הדוגמה: q1 = 7, 10, 5 ו-q2 = 5, 10, 7, 2, 10, 16, 3, 5.

איבר ב-q2ראש copyפעולהcopy אחרי
57-7, 10, 5
107-7, 10, 5
77הוצאה10, 5
210-10, 5
1010הוצאה5
165-5
35-5
55הוצאהריק

ההעתק התרוקן ← true (אלה האיברים המודגשים באיור). לעומת זאת עבור q1 = 7, 10 ו-q2 = 10, 7 מוחזר false: הערך 10 מופיע ב-q2 רק לפני 7.

תשובה: הפעולה inSameOrder שלמעלה.

סעיף ג

תשובה:

סעיף א': O(n⋅m)O(n\cdot m); סעיף ב': O(n+m)O(n+m), כאשר n ו-m מספרי האיברים ב-q1 וב-q2.

נסמן ב-n את מספר האיברים ב-q1 וב-m את מספר האיברים ב-q2. כל פעולות התור (`insert`, `remove`, `head`, `isEmpty`) הן O(1)O(1).

סעיף א':

1. לכל אחד מ-n האיברים של q1 מזמנים את `isIn`.

2. `isIn` מוציאה את m האיברים של q2 ומחזירה אותם - O(m)O(m).

3. שחזור q1 - O(n)O(n). בסך הכול O(n⋅m)O(n\cdot m).

סעיף ב':

1. העתקת q1 ושחזורו - O(n)O(n).

2. מעבר אחד על q2 ושחזורו, ובכל איבר עבודה קבועה - O(m)O(m).

3. בסך הכול O(n+m)O(n+m).

תשובה: א' - O(n⋅m)O(n\cdot m); ב' - O(n+m)O(n+m).

שאלה 3 · ירושה ומערך פריטים מסוגים שונים

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

•המחלקה Hardware עבור רכיבי חומרה פיזיים;

•המחלקה Server עבור שרתי מחשוב;

•המחלקה Switch עבור מתגי תקשורת;

•המחלקה SoftwareLicense עבור רישיונות תוכנה (כגון Windows או Oracle).

Java:

public class Hardware {
    private String serialNumber; // מספר סידורי
    private double price;        // מחיר יחידה
    public double getPrice() { return this.price; }
}
public class Server extends Hardware {
    private int ramGB;      // זיכרון בג'יגה בייט
    private int cpuCores;  // מספר ליבות מעבד
}
public class Switch extends Hardware {
    private int portsCount; // מספר פורטים
    private boolean managed; // האם מנוהל
    public int getPortsCount() { return this.portsCount; }
    public boolean isManaged(){return this.managed;}
}
public class SoftwareLicense {
    private String softwareName; // שם התוכנה
    private int months; // משך הרישיון בחודשים
    private double monthlyRate;   // עלות חודשית
    public double getPrice(){
       return (this.months * this.monthlyRate);
    }
}

C#:

public class Hardware {
    private string serialNumber; // מספר סידורי
    private double price;        // מחיר יחידה
    public double GetPrice() { return this.price; }
}
public class Server : Hardware {
    private int ramGB;      // זיכרון בג'יגה בייט
    private int cpuCores;  // מספר ליבות מעבד
}
public class Switch : Hardware {
    private int portsCount; // מספר פורטים
    private bool managed; // האם מנוהל
    public int GetPortsCount() { return this.portsCount; }
    public bool IsManaged(){return this.managed;}
}
public class SoftwareLicense {
    private string softwareName; // שם התוכנה
    private int months; // משך הרישיון בחודשים
    private double monthlyRate;   // עלות חודשית
    public double GetPrice(){
       return (this.months * this.monthlyRate);
    }
}
א.

בתחילת דרכה, המחלקה ProjectOrder ניהלה רק רכיבי חומרה המסופקים ללקוח.

למחלקה התכונות האלה:

•`String clientName` – שם הלקוח; (C#: `string clientName`)

•`Hardware[] items` – מערך של פריטי חומרה בלבד.

כתבו במחלקה ProjectOrder את הפעולה countLargeSwitches. הפעולה תחזיר כמות מתגי תקשורת הניתנים לניהול שיש להם יותר מ-16 פורטים.

(6 נקודות)
ב.

החברה החליטה לאפשר ללקוחות להוסיף להזמנה גם רישיונות תוכנה (SoftwareLicense).

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

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

(1)

אילו שינויים יש לבצע בהגדרת התכונות של המחלקה ProjectOrder כדי לתמוך בדרישה החדשה?

(2)

כתבו פעולה פנימית `public double calculateTotal()` (C#: `public double CalculateTotal()`).

הפעולה תחזיר את העלות הכוללת של כל הפריטים במערך החדש.

(10 נקודות)
◂ פתרון מלא לשאלה 3

סעיף א

תשובה:

הפעולה countLargeSwitches שלהלן: עוברת על המערך, ולכל פריט שהוא Switch (בדיקה ב-instanceof / is והמרה) סופרת אותו אם isManaged() מחזירה true ו-getPortsCount() > 16.

הרעיון: המערך `items` מטיפוס `Hardware[]`, ובפועל יש בו עצמים מסוג Hardware, Server ו-Switch. רק לעצם מסוג Switch יש הפעולות `isManaged()` ו-`getPortsCount()`, ולכן:

1. עוברים על כל תאי המערך.

2. בודקים אם העצם הוא מסוג Switch (`instanceof` ב-Java, `is` ב-C#). בדיקה זו מחזירה false גם עבור תא ריק (null), כך שאין חשש לשגיאה.

3. ממירים (casting) את ההפניה לטיפוס Switch, כדי שהמהדר יאפשר לזמן את הפעולות של Switch.

4. אם המתג מנוהל וגם מספר הפורטים גדול מ-16 - מגדילים את המונה.

5. מחזירים את המונה.

Java:

public int countLargeSwitches()
{
    int count = 0;
    for (int i = 0; i < this.items.length; i++)
    {
        if (this.items[i] instanceof Switch)          // רק מתגי תקשורת
        {
            Switch s = (Switch) this.items[i];        // המרה כדי לגשת לפעולות של Switch
            if (s.isManaged() && s.getPortsCount() > 16)
                count++;
        }
    }
    return count;
}

C#:

public int CountLargeSwitches()
{
    int count = 0;
    for (int i = 0; i < this.items.Length; i++)
    {
        if (this.items[i] is Switch)          // רק מתגי תקשורת
        {
            Switch s = (Switch) this.items[i];        // המרה כדי לגשת לפעולות של Switch
            if (s.IsManaged() && s.GetPortsCount() > 16)
                count++;
        }
    }
    return count;
}

דוגמה: במערך עם מתג מנוהל עם 24 פורטים, מתג מנוהל עם 16 פורטים, מתג לא מנוהל עם 48 פורטים ושרת - מוחזר 1 (רק הראשון; 16 אינו "יותר מ-16").

תשובה: הפעולה countLargeSwitches שלמעלה.

סעיף ב

(1)
תשובה:

מגדירים את המערך מטיפוס Object (ב-C#: object): `Object[] items` במקום `Hardware[] items`; התכונה clientName לא משתנה.

הנימוק:

1. המערך צריך להחזיק גם עצמים מסוג Hardware (ותת-המחלקות Server ו-Switch) וגם עצמים מסוג SoftwareLicense.

2. SoftwareLicense אינה יורשת מ-Hardware, ולכן אי אפשר להכניס רישיון למערך מטיפוס `Hardware[]`.

3. אסור להוסיף מחלקה (למשל מחלקת-על משותפת "Product" או ממשק) ואסור לשנות את יחסי הירושה. הטיפוס היחיד שכל המחלקות יורשות ממנו הוא Object - מחלקת-העל של כל המחלקות ב-Java (ב-C#: object).

4. לכן משנים את טיפוס המערך ל-`Object[]`; כל עצם, מכל אחת מהמחלקות, יכול להישמר בתא שלו.

Java:

private String clientName;
private Object[] items;      // במקום Hardware[] - מערך שמחזיק גם חומרה וגם רישיונות

C#:

private string clientName;
private object[] items;      // במקום Hardware[] - מערך שמחזיק גם חומרה וגם רישיונות

המחיר של השינוי: כאשר שולפים פריט מהמערך, הטיפוס הסטטי שלו הוא Object, ולכן כדי לזמן את `getPrice()` צריך לבדוק את הטיפוס בפועל ולבצע המרה (ראו סעיף 2).

תשובה: `private Object[] items;` (ב-C#: `private object[] items;`).

(2)
תשובה:

הפעולה calculateTotal שלהלן: לכל פריט בודקת אם הוא Hardware או SoftwareLicense, ממירה אליו ומוסיפה לסכום את getPrice() שלו.

הרעיון: לשתי המשפחות יש פעולה `getPrice()`, אבל הן לא מוגדרות במחלקה משותפת (ב-Object אין `getPrice()`), ולכן אי אפשר לזמן אותה ישירות דרך הפניה מטיפוס Object. לכל פריט:

1. אם הוא `instanceof Hardware` - זה רכיב חומרה (גם Server ו-Switch עונים לבדיקה זו, כי הם יורשים מ-Hardware ויורשים ממנה את `getPrice()`, המחזירה את מחיר היחידה). ממירים ל-Hardware ומוסיפים את המחיר.

2. אחרת, אם הוא `instanceof SoftwareLicense` - ממירים ל-SoftwareLicense ומוסיפים את `getPrice()` שלו, המחזירה months × monthlyRate.

3. מחזירים את הסכום.

Java:

public double calculateTotal()
{
    double total = 0;
    for (int i = 0; i < this.items.length; i++)
    {
        if (this.items[i] instanceof Hardware)              // Hardware, Server או Switch
            total += ((Hardware) this.items[i]).getPrice();
        else if (this.items[i] instanceof SoftwareLicense)  // רישיון תוכנה
            total += ((SoftwareLicense) this.items[i]).getPrice();
    }
    return total;
}

C#:

public double CalculateTotal()
{
    double total = 0;
    for (int i = 0; i < this.items.Length; i++)
    {
        if (this.items[i] is Hardware)              // Hardware, Server או Switch
            total += ((Hardware) this.items[i]).GetPrice();
        else if (this.items[i] is SoftwareLicense)  // רישיון תוכנה
            total += ((SoftwareLicense) this.items[i]).GetPrice();
    }
    return total;
}

דוגמה: מתג במחיר 100, שרת במחיר 500.5, רכיב חומרה במחיר 10 ורישיון ל-12 חודשים בעלות 20.25 לחודש: 100+500.5+10+12⋅20.25=853.5100+500.5+10+12\cdot 20.25=853.5.

תשובה: הפעולה calculateTotal שלמעלה.

שאלה 4 · ממשקים, המרות טיפוסים ושגיאות

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

Java:

interface IConnectable {void connect(String network);}
interface IRemoteControllable { void performAction(); }

public class EDevice {
    private String model;

    public EDevice(String model) { this.model = model; }

    public void printInfo() {
        System.out.println("Device: " + model);
    }
}

public class SmartLamp extends EDevice
                    implements IRemoteControllable {
    public SmartLamp(String model) { super(model); }
    public void performAction() {
            System.out.println("Lamp: Lighting up");
    }
}

public class SmartTV extends EDevice
            implements IConnectable, IRemoteControllable {
    public SmartTV(String model) { super(model); }
    public void connect(String net) {
            System.out.println("TV connected to " + net);
    }
    public void performAction() {
            System.out.println("TV: Playing movie");
    }
}

public class RobotVacuum extends EDevice
                implements IConnectable {
    public RobotVacuum(String model) { super(model); }
    public void connect(String net) {
            System.out.println("Vacuum ready on " + net);
    }
}

C#:

interface IConnectable {void Connect(string network);}
interface IRemoteControllable { void PerformAction(); }

public class EDevice {
    private string model;

    public EDevice(string model) { this.model = model; }

    public void PrintInfo() {
        Console.WriteLine("Device: " + model);
    }
}

public class SmartLamp : EDevice, IRemoteControllable {
    public SmartLamp(string model) : base(model) {
    }
     public void PerformAction() {
          Console.WriteLine("Lamp: Lighting up");
    }
}

public class SmartTV : EDevice, IConnectable,
                      IRemoteControllable {
     public SmartTV(string model) : base(model) {
     }
     public void Connect(string net) {
          Console.WriteLine("TV connected to " + net);
     }
     public void PerformAction() {
          Console.WriteLine("TV: Playing movie");
     }
}

public class RobotVacuum : EDevice, IConnectable {
     public RobotVacuum(string model) : base(model) {
     }
     public void Connect(string net) {
          Console.WriteLine("Vacuum ready on " + net);
     }
}
א.

נתון קטע קוד:

Java:

EDevice tv = new SmartTV("Sony-4K");
EDevice lamp = new SmartLamp("Lux");
IConnectable vacuum = new RobotVacuum("iRobot");
// **** //

C#:

EDevice tv = new SmartTV("Sony-4K");
EDevice lamp = new SmartLamp("Lux");
IConnectable vacuum = new RobotVacuum("iRobot");
// **** //

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

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

Java:

// 1
tv.printInfo();
tv.connect("Home_Net");

// 2
IRemoteControllable r1 = new SmartLamp("LED");
r1.printInfo();

// 3
if (vacuum instanceof EDevice) {
    ((EDevice)vacuum).printInfo();
}

// 4
SmartTV tv2 = (SmartTV)(new EDevice("Generic"));
tv2.printInfo();

// 5
IConnectable c1 = (IConnectable)lamp;
c1.connect("Guest_WiFi");

// 6
IRemoteControllable r2 = vacuum;
r2.performAction();

C#:

// 1
tv.PrintInfo();
tv.Connect("Home_Net");

// 2
IRemoteControllable r1 = new SmartLamp("LED");
r1.PrintInfo();

// 3
if (vacuum is EDevice) {
    ((EDevice)vacuum).PrintInfo();
}

// 4
SmartTV tv2 = (SmartTV)(new EDevice("Generic"));
tv2.PrintInfo();

// 5
IConnectable c1 = (IConnectable)lamp;
c1.Connect("Guest_WiFi");

// 6
IRemoteControllable r2 = vacuum;
r2.PerformAction();
(12 נקודות)
ב.

כתבו פעולה המקבלת מערך של מכשירי חשמל (מערך עצמים מסוג EDevice) ושם רשת. הפעולה צריכה:

1. להדפיס את המידע של כל מכשיר;

2. אם מכשיר ניתן לחיבור – לחבר אותו לרשת;

3. אם מכשיר ניתן לשליטה מרחוק – להפעיל אותו.

כותרת הפעולה:

Java:

public static void setupHome(EDevice[] devices, String network)

C#:

public static void SetupHome(EDevice[] devices, string network)
(4 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקין, הפלט: Device: iRobot; 4 - שגיאה בזמן ריצה (ClassCastException / InvalidCastException); 5 - שגיאה בזמן ריצה (ClassCastException / InvalidCastException); 6 - שגיאת הידור.

כללים:

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

•המרה מפורשת (casting) כלפי מטה, או ממחלקה שאינה final/sealed לממשק, עוברת הידור; בזמן ריצה בודקים את הטיפוס האמיתי של העצם, ואם הוא לא מתאים - נזרקת חריגה (ב-Java `ClassCastException`, ב-C# `InvalidCastException`).

•בזמן ריצה מופעלת הפעולה של הטיפוס האמיתי של העצם.

המשתנים: `tv` מוצהר EDevice ומפנה ל-SmartTV; `lamp` מוצהר EDevice ומפנה ל-SmartLamp; `vacuum` מוצהר IConnectable ומפנה ל-RobotVacuum.

קטע 1 - שגיאת הידור. `tv.printInfo()` תקין (מוגדרת ב-EDevice), אבל `tv.connect("Home_Net")` - הטיפוס המוצהר של tv הוא EDevice, ובמחלקה EDevice אין פעולה connect. זה שהעצם בפועל הוא SmartTV לא עוזר, כי המהדר בודק את הטיפוס המוצהר. (תיקון: `((SmartTV)tv).connect(...)` או `((IConnectable)tv).connect(...)`.)

קטע 2 - שגיאת הידור. ההשמה `IRemoteControllable r1 = new SmartLamp("LED")` תקינה, כי SmartLamp מממשת את IRemoteControllable. אבל `r1.printInfo()` - בממשק IRemoteControllable מוגדרת רק performAction, ולכן דרך r1 אי אפשר לזמן את printInfo.

קטע 3 - תקין. vacuum מפנה לעצם RobotVacuum, שהוא EDevice (יורש ממנה), ולכן התנאי `vacuum instanceof EDevice` (ב-C#: `vacuum is EDevice`) מתקיים. ההמרה ל-EDevice מצליחה, ו-printInfo מדפיסה את הדגם:

Device: iRobot

קטע 4 - שגיאה בזמן ריצה. ההמרה `(SmartTV)` מ-EDevice היא המרה כלפי מטה במורד הירושה, ולכן עוברת הידור. אבל העצם שנוצר הוא EDevice "רגיל" ולא SmartTV, ולכן בזמן ריצה ההמרה נכשלת ונזרקת `ClassCastException` (ב-C#: `InvalidCastException`); השורה `tv2.printInfo()` לא מתבצעת.

קטע 5 - שגיאה בזמן ריצה. המרה מפורשת של משתנה מטיפוס EDevice (מחלקה שאינה final/sealed) לממשק IConnectable עוברת הידור, כי ייתכן שתת-מחלקה של EDevice מממשת את הממשק. בזמן ריצה lamp מפנה ל-SmartLamp, שאינה מממשת את IConnectable, ולכן נזרקת `ClassCastException` (ב-C#: `InvalidCastException`), ו-connect לא מתבצעת.

קטע 6 - שגיאת הידור. vacuum מוצהר IConnectable, ואין קשר בין IConnectable לבין IRemoteControllable; השמה בלי המרה מפורשת אסורה. (וגם בפועל RobotVacuum אינה מממשת את IRemoteControllable, ולכן גם עם המרה הייתה נזרקת חריגה בזמן ריצה.)

קטעתקין?הסבר / פלט
1שגיאת הידורב-EDevice אין connect
2שגיאת הידורב-IRemoteControllable אין printInfo
3תקיןDevice: iRobot
4שגיאה בזמן ריצההעצם אינו SmartTV
5שגיאה בזמן ריצהSmartLamp אינה מממשת IConnectable
6שגיאת הידורIConnectable אינו IRemoteControllable

תשובה: 1, 2, 6 - שגיאת הידור; 4, 5 - שגיאה בזמן ריצה; 3 - תקין ומדפיס Device: iRobot.

סעיף ב

תשובה:

הפעולה setupHome שלהלן: לכל מכשיר מזמנת printInfo; אם הוא instanceof IConnectable - ממירה ומזמנת connect(network); אם הוא instanceof IRemoteControllable - ממירה ומזמנת performAction().

הרעיון: את printInfo אפשר לזמן ישירות, כי היא מוגדרת ב-EDevice. את connect ואת performAction אי אפשר לזמן דרך הפניה מטיפוס EDevice, ולכן לכל מכשיר בודקים אם הוא מממש את הממשק המתאים (`instanceof` / `is`), ואם כן - ממירים להפניה מטיפוס הממשק ומזמנים את הפעולה. שתי הבדיקות נפרדות (לא else), כי מכשיר יכול לממש את שני הממשקים (כמו SmartTV).

Java:

public static void setupHome(EDevice[] devices, String network)
{
    for (int i = 0; i < devices.length; i++)
    {
        EDevice d = devices[i];
        d.printInfo();                                    // 1. כל מכשיר
        if (d instanceof IConnectable)                    // 2. ניתן לחיבור
            ((IConnectable) d).connect(network);
        if (d instanceof IRemoteControllable)             // 3. ניתן לשליטה מרחוק
            ((IRemoteControllable) d).performAction();
    }
}

C#:

public static void SetupHome(EDevice[] devices, string network)
{
    for (int i = 0; i < devices.Length; i++)
    {
        EDevice d = devices[i];
        d.PrintInfo();                                    // 1. כל מכשיר
        if (d is IConnectable)                    // 2. ניתן לחיבור
            ((IConnectable) d).Connect(network);
        if (d is IRemoteControllable)             // 3. ניתן לשליטה מרחוק
            ((IRemoteControllable) d).PerformAction();
    }
}

דוגמה: עבור המערך {SmartTV("Sony-4K"), SmartLamp("Lux"), RobotVacuum("iRobot")} והרשת "Home_Net" יודפס:

Device: Sony-4K
TV connected to Home_Net
TV: Playing movie
Device: Lux
Lamp: Lighting up
Device: iRobot
Vacuum ready on Home_Net

תשובה: הפעולה setupHome שלמעלה.

שאלה 5 · ניתוח פעולות על מחסנית ותור

א.

נתונה הפעולה secret (C#: Secret):

Java:

public static boolean secret(Stack<Integer> s) {
    if (s.isEmpty()) return true;
    boolean res = true;
    while (!s.isEmpty()) {
        int x = s.pop();
        if (!s.isEmpty()) {
            if (x * s.top() >= 0) {
                res = false;
            }
        }
    }
    return res;
}

C#:

public static bool Secret(Stack<int> s) {
    if (s.IsEmpty()) return true;
    bool res = true;
    while (!s.IsEmpty()) {
        int x = s.Pop();
        if (!s.IsEmpty()) {
            if (x * s.Top() >= 0) {
                res = false;
            }
        }
    }
    return res;
}
(1)

תנו דוגמה למחסנית s הכוללת לפחות שישה ערכים שלמים (גם חיוביים וגם שליליים), שעבורה זימון הפעולה secret(s) יחזיר ערך true. אם אין מחסנית כזאת – הסבירו את הסיבה לכך.

(2)

מה מבצעת הפעולה secret באופן כללי עבור מחסנית של מספרים שלמים?

(6 נקודות)
ב.

נתונה הפעולה mystery (C#: Mystery):

Java:

public static boolean mystery(Queue<Integer> q) {
    if (q.isEmpty()) return true;
    boolean res = true;
    while (!q.isEmpty()) {
        int first = q.remove();
        if (!q.isEmpty()) {
            int second = q.remove();
            if (first * second <= 0) {
                res = false;
            }
        }
    }
    return res;
}

C#:

public static bool Mystery(Queue<int> q) {
    if (q.IsEmpty()) return true;
    bool res = true;
    while (!q.IsEmpty()) {
        int first = q.Remove();
        if (!q.IsEmpty()) {
            int second = q.Remove();
            if (first * second <= 0) {
                res = false;
            }
        }
    }
    return res;
}
(1)

תנו דוגמה לתור q הכולל לפחות שישה ערכים שלמים (גם חיוביים וגם שליליים), שעבורו זימון הפעולה mystery(q) יחזיר ערך true. אם אין תור כזה – הסבירו את הסיבה לכך.

(2)

מה מבצעת הפעולה mystery באופן כללי עבור תור של מספרים שלמים?

(6 נקודות)
ג.

כתבו פעולה בשם check (C#: Check) המקבלת מחסנית של מספרים שלמים חיוביים ומספר שלם חיובי k. הפעולה תבדוק אם כל איברי המחסנית הם כפולות של k (מתחלקים ב-k ללא שארית). אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

בסיום הפעולה, על המחסנית לחזור למצב המקורי.

(4 נקודות)
◂ פתרון מלא לשאלה 5

סעיף א

(1)
תשובה:

למשל המחסנית 3, -1, 4, -2, 5, -6 (3 בראש) - הסימנים מתחלפים, ולכן מוחזר true.

מה נבדק: בכל סיבוב שולפים איבר x ומשווים אותו לאיבר שנמצא עכשיו בראש המחסנית - כלומר לאיבר שהיה מתחתיו. אם המכפלה x⋅top≥0x\cdot top \ge 0, `res` הופך ל-false. לכן כדי לקבל true, כל מכפלה של שני איברים סמוכים צריכה להיות שלילית: סימנים מתחלפים, בלי אפסים.

דוגמה: המחסנית (מהראש לתחתית) 3, -1, 4, -2, 5, -6.

x שנשלףראש המחסניתמכפלהres
3-1-3true
-14-4true
4-2-8true
-25-10true
5-6-30true
-6(ריקה)-true

כל המכפלות שליליות, ולכן מוחזר true.

תשובה: כן, למשל 3, -1, 4, -2, 5, -6 (3 בראש המחסנית).

(2)
תשובה:

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

1. מחסנית ריקה - מוחזר true מיד.

2. אחרת שולפים את כל האיברים. לכל איבר (פרט לאחרון) בודקים את המכפלה שלו באיבר שמתחתיו. מכפלה ≥0\ge 0 פירושה ששני האיברים באותו סימן, או שאחד מהם 0 - ואז `res = false`.

3. לכן מוחזר true אם ורק אם לכל שני איברים סמוכים יש סימנים מנוגדים (אחד חיובי ואחד שלילי) - הסימנים לאורך המחסנית מתחלפים, ואין בה אפסים (פרט אולי למחסנית בת איבר אחד, שמחזירה תמיד true).

4. תופעת לוואי: הפעולה מרוקנת את המחסנית (האיברים לא מוחזרים).

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

סעיף ב

(1)
תשובה:

למשל התור 2, 5, -3, -1, 4, 7 (2 בראש) - בכל זוג (2,5), (-3,-1), (4,7) שני האיברים באותו סימן, ולכן מוחזר true.

מה נבדק: בכל סיבוב מוציאים שני איברים, `first` ו-`second`. אם המכפלה שלהם ≤0\le 0 (סימנים שונים, או 0) - `res = false`. כלומר האיברים נבדקים בזוגות נפרדים: הראשון עם השני, השלישי עם הרביעי וכן הלאה, ואין השוואה בין זוג לזוג. לכן אפשר לשים זוג חיובי וזוג שלילי.

דוגמה: התור (מהראש לסוף) 2, 5, -3, -1, 4, 7.

firstsecondמכפלהres
2510true
-3-13true
4728true

כל המכפלות חיוביות ← true.

תשובה: כן, למשל 2, 5, -3, -1, 4, 7 (2 בראש התור).

(2)
תשובה:

מחלקת את התור לזוגות עוקבים (1-2, 3-4, ...) ומחזירה true אם בכל זוג שני האיברים שונים מ-0 ובאותו סימן; איבר אחרון בלי בן-זוג (אורך אי-זוגי) אינו נבדק. התור מתרוקן.

1. תור ריק - מוחזר true.

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

3. אם מספר האיברים אי-זוגי, האיבר האחרון מוצא לבד ולא נבדק כלל.

4. תופעת לוואי: התור מתרוקן.

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

סעיף ג

תשובה:

הפעולה check שלהלן: שולפת כל איבר למחסנית עזר ובודקת x % k == 0; בסוף מחזירה את האיברים למחסנית ומחזירה true אם כולם התחלקו ב-k.

הרעיון: שולפים את כל האיברים ובודקים לכל אחד אם x%k=0x \% k = 0. כדי שהמחסנית תחזור למצבה המקורי, כל איבר שנשלף נדחף למחסנית עזר, ובסוף מחזירים אותם (שני היפוכים - הסדר המקורי). לא עוצרים באמצע הלולאה כשמוצאים איבר שאינו כפולה, כדי שהשחזור יהיה מלא.

1. `ok = true`.

2. כל עוד המחסנית אינה ריקה: שולפים x, דוחפים ל-`temp`; אם `x % k != 0` - `ok = false`.

3. מחזירים את האיברים מ-`temp` למחסנית.

4. מחזירים `ok`.

Java:

public static boolean check(Stack<Integer> st, int k)
{
    boolean ok = true;
    Stack<Integer> temp = new Stack<Integer>();
    while (!st.isEmpty())
    {
        int x = st.pop();
        temp.push(x);
        if (x % k != 0)          // x אינו כפולה של k
            ok = false;
    }
    while (!temp.isEmpty())      // החזרת המחסנית למצבה המקורי
        st.push(temp.pop());
    return ok;
}

C#:

public static bool Check(Stack<int> st, int k)
{
    bool ok = true;
    Stack<int> temp = new Stack<int>();
    while (!st.IsEmpty())
    {
        int x = st.Pop();
        temp.Push(x);
        if (x % k != 0)          // x אינו כפולה של k
            ok = false;
    }
    while (!temp.IsEmpty())      // החזרת המחסנית למצבה המקורי
        st.Push(temp.Pop());
    return ok;
}

דוגמה: המחסנית 6, 9, 12 ו-k = 3 ← true; המחסנית 6, 9, 13 ו-k = 3 ← false (13 אינו מתחלק ב-3). בשני המקרים המחסנית חוזרת למצבה.

תשובה: הפעולה check שלמעלה.

שאלה 6 · מעבורת: תור משאיות ובדיקת תקינות

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

המחלקה Truck מייצגת משאית:

Java:

class Truck {
    private String plateNumber;  // מספר רישוי
    private int weight;            // משקל המשאית (בטונות)
    private int cargoValue;        // ערך המטען של המשאית (בשקלים)
}

C#:

class Truck {
    private string plateNumber;  // מספר רישוי
    private int weight;            // משקל המשאית (בטונות)
    private int cargoValue;        // ערך המטען של המשאית (בשקלים)
}

אפשר להניח שבמחלקה הוגדרו בנאי ופעולות get (C#: Get) לכל התכונות.

א.

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

•תור של משאיות (`Queue<Truck> trucks`);

•משקל מקסימלי שהמעבורת יכולה לשאת (maxCapacity).

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

(3 נקודות)
ב.

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

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

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

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

כותרת הפעולה

Java:

public boolean isValid()

C#:

public bool IsValid()
(8 נקודות)
ג.

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

•אם ההוספה בוצעה - הפעולה מוסיפה את המשאית ומחזירה true.

•אם הוספת המשאית תהפוך את המעבורת ל"לא תקינה" - אין להוסיף את המשאית והפעולה תחזיר false.

כותרת הפעולה

Java:

public boolean addTruck(Truck t)

C#:

public bool AddTruck(Truck t)
(5 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

המחלקה Ferry עם התכונות trucks (Queue<Truck>) ו-maxCapacity (int), ובנאי שמקבל את המשקל המרבי ויוצר תור ריק.

הרעיון: התכונות פרטיות (private), כדי לשמור על הכימוס. הבנאי מקבל את המשקל המרבי ושומר אותו, ויוצר תור משאיות חדש וריק - כך המעבורת מתחילה ללא משאיות. (המשקל נמדד בטונות, כמו weight של משאית, ולכן maxCapacity מטיפוס int.)

Java:

public class Ferry
{
    private Queue<Truck> trucks;     // תור המשאיות שעל המעבורת
    private int maxCapacity;         // המשקל המקסימלי שהמעבורת יכולה לשאת

    public Ferry(int maxCapacity)
    {
        this.maxCapacity = maxCapacity;
        this.trucks = new Queue<Truck>();   // מעבורת ריקה
    }
}

C#:

public class Ferry
{
    private Queue<Truck> trucks;     // תור המשאיות שעל המעבורת
    private int maxCapacity;         // המשקל המקסימלי שהמעבורת יכולה לשאת

    public Ferry(int maxCapacity)
    {
        this.maxCapacity = maxCapacity;
        this.trucks = new Queue<Truck>();   // מעבורת ריקה
    }
}

תשובה: המחלקה Ferry שלמעלה.

סעיף ב

תשובה:

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

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

•משקל: סוכמים את משקלי כל המשאיות ב-`total`.

•סדר: זוכרים את המשאית הקודמת `prev`. אם ערך המטען של הקודמת גדול מערך המטען של הנוכחית - הסדר הלא-יורד הופר.

כדי לעבור על התור צריך להוציא ממנו את המשאיות; לכן כל משאית מוכנסת לתור עזר `temp`, ובסוף מחזירים את כולן ל-`trucks`. מכיוון שתור שומר על סדר (FIFO), הסדר המקורי חוזר. לא יוצאים מהלולאה באמצע, כדי שהשחזור יהיה מלא.

1. `total = 0`, `sorted = true`, `prev = null`.

2. כל עוד `trucks` אינו ריק: מוציאים משאית t, מכניסים ל-`temp`, מוסיפים את משקלה ל-`total`; אם `prev` קיימת וערך המטען שלה גדול מזה של t - `sorted = false`; `prev = t`.

3. מחזירים את המשאיות מ-`temp` ל-`trucks`.

4. מחזירים `total <= maxCapacity && sorted`.

Java:

public boolean isValid()
{
    int total = 0;                    // סכום משקלי המשאיות
    boolean sorted = true;            // ערכי המטען בסדר לא יורד
    Truck prev = null;                // המשאית הקודמת בתור
    Queue<Truck> temp = new Queue<Truck>();
    while (!this.trucks.isEmpty())
    {
        Truck t = this.trucks.remove();
        temp.insert(t);
        total += t.getWeight();
        if (prev != null && prev.getCargoValue() > t.getCargoValue())
            sorted = false;           // משאית זולה יותר מזו שלפניה
        prev = t;
    }
    while (!temp.isEmpty())           // החזרת התור למצבו
        this.trucks.insert(temp.remove());
    return total <= this.maxCapacity && sorted;
}

C#:

public bool IsValid()
{
    int total = 0;                    // סכום משקלי המשאיות
    bool sorted = true;            // ערכי המטען בסדר לא יורד
    Truck prev = null;                // המשאית הקודמת בתור
    Queue<Truck> temp = new Queue<Truck>();
    while (!this.trucks.IsEmpty())
    {
        Truck t = this.trucks.Remove();
        temp.Insert(t);
        total += t.GetWeight();
        if (prev != null && prev.GetCargoValue() > t.GetCargoValue())
            sorted = false;           // משאית זולה יותר מזו שלפניה
        prev = t;
    }
    while (!temp.IsEmpty())           // החזרת התור למצבו
        this.trucks.Insert(temp.Remove());
    return total <= this.maxCapacity && sorted;
}

דוגמה: maxCapacity = 100 ובתור (מהראש) משאיות במשקלים 30, 30, 40 עם ערכי מטען 1000, 1000, 5000: סך המשקל 30+30+40=100≤10030+30+40=100\le 100, והערכים 1000 ≤ 1000 ≤ 5000 ← true. אם הערך של המשאית השנייה היה 500 - הסדר מופר (1000 > 500) ← false.

תשובה: הפעולה isValid שלמעלה.

סעיף ג

תשובה:

הפעולה addTruck שלהלן: מחשבת את המשקל הנוכחי ואת המשאית האחרונה בתור (עם שחזור התור), ומוסיפה את t רק אם המעבורת תקנית, המשקל אחרי ההוספה ≤ maxCapacity, וערך המטען של t אינו קטן מזה של המשאית האחרונה; אחרת מחזירה false.

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

1. המעבורת תקנית עכשיו (`isValid()` מסעיף ב');

2. המשקל הנוכחי ועוד משקל t אינו עולה על maxCapacity;

3. ערך המטען של המשאית האחרונה הנוכחית (אם יש) נמוך מערך המטען של t או שווה לו - זה הזוג הסמוך היחיד שנוסף.

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

Java:

public boolean addTruck(Truck t)
{
    int total = 0;                    // משקל המשאיות שכבר על המעבורת
    Truck last = null;                // המשאית האחרונה בתור
    Queue<Truck> temp = new Queue<Truck>();
    while (!this.trucks.isEmpty())
    {
        Truck x = this.trucks.remove();
        temp.insert(x);
        total += x.getWeight();
        last = x;
    }
    while (!temp.isEmpty())           // החזרת התור למצבו
        this.trucks.insert(temp.remove());

    if (!isValid())                                   // המעבורת כבר אינה תקנית
        return false;
    if (total + t.getWeight() > this.maxCapacity)     // חריגה ממגבלת המשקל
        return false;
    if (last != null && last.getCargoValue() > t.getCargoValue())  // הפרת סדר ערך המטען
        return false;
    this.trucks.insert(t);                            // ההוספה שומרת על תקינות
    return true;
}

C#:

public bool AddTruck(Truck t)
{
    int total = 0;                    // משקל המשאיות שכבר על המעבורת
    Truck last = null;                // המשאית האחרונה בתור
    Queue<Truck> temp = new Queue<Truck>();
    while (!this.trucks.IsEmpty())
    {
        Truck x = this.trucks.Remove();
        temp.Insert(x);
        total += x.GetWeight();
        last = x;
    }
    while (!temp.IsEmpty())           // החזרת התור למצבו
        this.trucks.Insert(temp.Remove());

    if (!IsValid())                                   // המעבורת כבר אינה תקנית
        return false;
    if (total + t.GetWeight() > this.maxCapacity)     // חריגה ממגבלת המשקל
        return false;
    if (last != null && last.GetCargoValue() > t.GetCargoValue())  // הפרת סדר ערך המטען
        return false;
    this.trucks.Insert(t);                            // ההוספה שומרת על תקינות
    return true;
}

דוגמה: maxCapacity = 100, בתור משאיות A (30 טון, 1000 ₪) ו-C (30 טון, 1000 ₪). הוספת D (50 טון, 5000 ₪): 60+50=110>10060+50=110>100 ← false, D לא נוספת. הוספת E (40 טון, 5000 ₪): 60+40=100≤10060+40=100\le 100, 1000≤50001000\le 5000 ← true, E נוספת לסוף התור. הוספת משאית עם ערך מטען 500 לתור שמסתיים ב-A הייתה נדחית בגלל הסדר.

תשובה: הפעולה addTruck שלמעלה.

שאלה 7 · מעקב אחר רקורסיה על עץ בינרי

נתונות הפעולות הבאות:

Java:

public static int what(BinNode<Character> bt) {
    if (bt == null) return 0;
    return 1 + Math.max(what(bt.getLeft()),
                        what(bt.getRight()));
}

public static void printTree(BinNode<Character> bt) {
    if (bt == null) return;

    printTree(bt.getLeft());

    int leftH = what(bt.getLeft());
    int rightH = what(bt.getRight());
    int count = leftH + rightH + 1;

    for (int i = 0; i < count; i++) {
        System.out.print(bt.getValue());
    }

    printTree (bt.getRight());
}

C#:

public static int What(BinNode<char> bt) {
    if (bt == null) return 0;
    return 1 + Math.Max(What(bt.GetLeft()),
                        What(bt.GetRight()));
}

public static void PrintTree(BinNode<char> bt) {
    if (bt == null) return;

    PrintTree(bt.GetLeft());

    int leftH = What(bt.GetLeft());
    int rightH = What(bt.GetRight());
    int count = leftH + rightH + 1;

    for (int i = 0; i < count; i++) {
        Console.Write(bt.GetValue());
    }

    PrintTree (bt.GetRight());
}

נתון עץ בינרי bt:

א.

מה תהיה תוצאת הזימון what(bt)?

(3 נקודות)
ב.

עבור הצומת B, כמה פעמים תודפס האות 'B'?

(3 נקודות)
ג.

מה תהיה תוצאת הזימון printTree(bt)? יש להראות מעקב אחרי זימון הפעולה.

(8 נקודות)
ד.

ציירו עץ בינרי שעבורו פלט של הפעולה printTree יהיה EDDCCCBBBBAAAAA.

(4 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

תשובה:

4

מה מחשבת what: עבור עץ ריק מוחזר 0; אחרת 1 ועוד המקסימום מבין התוצאות של שני תתי-העצים. זהו מספר הצמתים במסלול הארוך ביותר מהשורש לעלה ("הגובה" כשסופרים צמתים).

נחשב מלמטה למעלה (בעץ: A שורש; B בן שמאלי של A עם הבנים D ו-E; C בן ימני של A, ול-C בן ימני F; G בן שמאלי של F):

צומתwhat(שמאל)what(ימין)what(צומת)
D001+0=11+0=1
E001+0=11+0=1
B111+1=21+1=2
G001+0=11+0=1
F101+1=21+1=2
C021+2=31+2=3
A231+3=41+3=4

המסלול הארוך ביותר: A → C → F → G, ארבעה צמתים.

תשובה: what(bt) = 4.

סעיף ב

תשובה:

3 פעמים.

בצומת B הפעולה printTree מחשבת:

1. `leftH = what(D) = 1` (D עלה).

2. `rightH = what(E) = 1` (E עלה).

3. `count = leftH + rightH + 1 = 1+1+1 = 3`.

הלולאה מדפיסה את ערך הצומת count פעמים, ולכן B מודפסת 3 פעמים: BBB. (printTree מזמנת את עצמה על כל צומת פעם אחת בדיוק, ולכן אין הדפסות נוספות של B.)

תשובה: 3 פעמים.

סעיף ג

תשובה:

DBBBEAAAAAACCCGFF

מבנה הפעולה: printTree עוברת על העץ בסדר תוכי (in-order): קודם כל תת-העץ השמאלי, אחר כך הצומת עצמו, ואחר כך תת-העץ הימני. בכל צומת היא מדפיסה את האות `count = what(שמאל) + what(ימין) + 1` פעמים.

סדר הזימונים:

1. printTree(A) → קודם printTree(B) → קודם printTree(D).

2. printTree(D): השמאלי ריק; count = 0+0+1 = 1 → מודפס D; הימני ריק. חוזרים ל-B.

3. ב-B: count = 1+1+1 = 3 → BBB; אחר כך printTree(E): count = 1 → E. חוזרים ל-A.

4. ב-A: leftH = what(B) = 2, rightH = what(C) = 3, count = 6 → AAAAAA; אחר כך printTree(C).

5. printTree(C): השמאלי ריק; count = 0+2+1 = 3 → CCC; אחר כך printTree(F).

6. printTree(F): קודם printTree(G): count = 1 → G; ב-F: count = 1+0+1 = 2 → FF; הימני ריק.

סדרצומתleftHrightHcountמודפס
1D001D
2B113BBB
3E001E
4A236AAAAAA
5C023CCC
6G001G
7F102FF

הכול מודפס באותה שורה (print, בלי ירידת שורה):

DBBBEAAAAAACCCGFF

(בגרסת C# הפעולה נקראת What, והכתיב what בגוף PrintTree הוא שגיאת הקלדה; התוצאה זהה.)

תשובה: DBBBEAAAAAACCCGFF

סעיף ד

תשובה:

שרשרת של בנים שמאליים: A שורש, B בן שמאלי של A, C בן שמאלי של B, D בן שמאלי של C, E בן שמאלי של D (לאף צומת אין בן ימני).

ניתוח הפלט: E פעם אחת, D פעמיים, C שלוש פעמים, B ארבע פעמים, A חמש פעמים.

1. printTree מדפיסה בסדר תוכי, ולכן הסדר התוכי של העץ צריך להיות E, D, C, B, A.

2. בכל צומת count=what(left)+what(right)+1count = what(left)+what(right)+1, ולכן צריך: E - סכום גבהים 0 (עלה); D - סכום 1; C - סכום 2; B - סכום 3; A - סכום 4.

3. ניקח שרשרת שבה כל צומת הוא הבן השמאלי של הצומת שאחריו: E בן שמאלי של D, D של C, C של B, B של A. אז הסדר התוכי הוא E, D, C, B, A (תמיד קודם השמאלי ואז הצומת), ולכל צומת אין בן ימני, ולכן count = (גובה תת-העץ השמאלי) + 1:

צומתwhat(שמאל)what(ימין)count
E001
D102
C203
B304
A405

העץ (כל קו הוא קשר לבן שמאלי):

        A
       /
      B
     /
    C
   /
  D
 /
E

הפלט: E, DD, CCC, BBBB, AAAAA = EDDCCCBBBBAAAAA, כנדרש. (שרשרת של בנים ימניים לא מתאימה: בה הסדר התוכי היה A, B, C, D, E.)

תשובה: A בשורש, ומתחתיו שרשרת בנים שמאליים B, C, D, E.

שאלה 8 · חדרי לימוד: ירושה, UML ופולימורפיזם

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

לכל חדר קיימת מערכת שיעורים משלו: מערך דו-ממדי (arr) הכולל עבור כל יום וכל שיעור את מספר הקבוצה הלומדת בו (המספר 0 מציין שהחדר פנוי). גודל המערך 10X5.

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

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

עבור חדר לימוד רגיל (ClassRoom):

•מספר החדר (roomNum)

•מספר מקומות הישיבה בחדר (seats)

•מערך של מערכת שיעורים (arr)

עבור מעבדת מחשבים (CompRoom):

•מספר החדר (roomNum)

•מספר מקומות הישיבה בחדר (seats)

•מערך של מערכת שיעורים (arr)

•מספר מחשבים (comps)

עבור חדר מולטימדיה (MediaRoom):

•מספר החדר (roomNum)

•מספר מקומות הישיבה בחדר (seats)

•מערך של מערכת שיעורים (arr)

•מספר מחשבים (comps)

•מערך שמות של סוגי ציוד המצויים בחדר (equips)

א.

שרטטו תרשים UML המתאר את הקשר בין המחלקות MediaRoom, CompRoom ו-ClassRoom באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.

לכל אחת מהמחלקות ClassRoom, CompRoom, MediaRoom כתבו:

•כותרת המחלקה;

•תכונות;

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

הערה: הניחו שהפעולות get ו-set מוגדרות עבור כל תכונה בכל אחת מהמחלקות. גם פעולות toString() הוגדרו בכל אחת מהמחלקות.

(4 נקודות)
ב.

•כתבו פעולה המקבלת מחרוזת המייצגת סוג ציוד ובודקת אם הציוד קיים בחדר. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false. כותרת הפעולה:

Java:

boolean isEquipmentExist(String eq)

C#:

bool IsEquipmentExist(string eq)

•כתבו פעולה המקבלת מספר המייצג יום בשבוע (מ-1 עבור יום ראשון ועד 5 עבור יום חמישי) ומספר שיעור לימוד (בין 1 ל-10). הפעולה תבדוק אם החדר פנוי בשיעור זה. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

ניתן להניח כי הפרמטרים של הפעולה תקינים. כותרת הפעולה:

Java:

boolean isFree(int day, int lesson)

C#:

bool IsFree(int day, int lesson)

עבור כל פעולה יש לציין באיזו מחלקה צריך לממש את הפעולה.

(6 נקודות)
ג.

הוגדרה המחלקה College לניהול חדרי לימוד במכללה. למחלקה תכונה אחת.

public class College {
       private ____________________  rooms;
}

•השלימו את החסר בהגדרת התכונה.

•כתבו במחלקה College פעולה המקבלת יום day ומספר שיעור lesson ומדפיסה את הפרטים של כל מעבדות מחשב הפנויות באותו היום ובאותו השיעור. כותרת הפעולה:

Java:

void printFreeCompRooms(int day, int lesson)

C#:

void PrintFreeCompRooms(int day, int lesson)

אפשר להניח שהפרמטרים תקינים.

•כתבו במחלקה College פעולה בשם collectEquipmentExist (C#: CollectEquipmentExist) המקבלת מחרוזת המייצגת סוג ציוד ומחזירה את אוסף חדרי מולטימדיה שבהם קיים סוג הציוד הזה.

הערה:

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

(8 נקודות)
◂ פתרון מלא לשאלה 8

סעיף א

תשובה:

שרשרת ירושה: CompRoom יורשת מ-ClassRoom ומוסיפה comps; MediaRoom יורשת מ-CompRoom ומוסיפה equips. כל בנאי מקבל את כל התכונות ומעביר לבנאי של מחלקת-העל את התכונות שלה.

הרעיון: משווים את רשימות המידע:

1. למעבדת מחשבים יש כל התכונות של חדר רגיל (roomNum, seats, arr) ועוד comps - מעבדת מחשבים היא חדר לימוד עם תוספת. לכן CompRoom יורשת מ-ClassRoom ומוסיפה רק את comps.

2. לחדר מולטימדיה יש כל התכונות של מעבדת מחשבים ועוד equips - לכן MediaRoom יורשת מ-CompRoom ומוסיפה רק את equips.

3. כך כל תכונה מוגדרת פעם אחת בלבד (אין שכפול קוד), ופעולות משותפות - כמו בדיקת חדר פנוי - נכתבות פעם אחת במחלקת-העל ועוברות בירושה. בנוסף, מערך מטיפוס ClassRoom יוכל להחזיק את שלושת סוגי החדרים (פולימורפיזם).

4. התכונות פרטיות (-), והבנאים ציבוריים (+). כל בנאי מקבל את כל הנתונים של העצם, מעביר לבנאי של מחלקת-העל (super / base) את התכונות שלה, ומאתחל בעצמו רק את התכונה החדשה.

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

+----------------------------------------------------+
|                     ClassRoom                      |
+----------------------------------------------------+
| - roomNum : int                                    |
| - seats : int                                      |
| - arr : int[][]                                    |
+----------------------------------------------------+
| + ClassRoom(roomNum, seats, arr)                   |
+----------------------------------------------------+
                          ^
                          |  (ירושה)
+----------------------------------------------------+
|                      CompRoom                      |
+----------------------------------------------------+
| - comps : int                                      |
+----------------------------------------------------+
| + CompRoom(roomNum, seats, arr, comps)             |
+----------------------------------------------------+
                          ^
                          |  (ירושה)
+----------------------------------------------------+
|                     MediaRoom                      |
+----------------------------------------------------+
| - equips : String[]                                |
+----------------------------------------------------+
| + MediaRoom(roomNum, seats, arr, comps, equips)    |
+----------------------------------------------------+

(ב-C#: `arr : int[,]`, `equips : string[]`.)

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

Java:

public class ClassRoom
{
    private int roomNum;     // מספר החדר
    private int seats;       // מספר מקומות הישיבה
    private int[][] arr;     // מערכת השיעורים: 10 שורות (שיעורים) על 5 עמודות (ימים)

    public ClassRoom(int roomNum, int seats, int[][] arr)
    {
        this.roomNum = roomNum;
        this.seats = seats;
        this.arr = arr;
    }
}

public class CompRoom extends ClassRoom
{
    private int comps;       // מספר המחשבים

    public CompRoom(int roomNum, int seats, int[][] arr, int comps)
    {
        super(roomNum, seats, arr);
        this.comps = comps;
    }
}

public class MediaRoom extends CompRoom
{
    private String[] equips; // שמות סוגי הציוד שבחדר

    public MediaRoom(int roomNum, int seats, int[][] arr, int comps, String[] equips)
    {
        super(roomNum, seats, arr, comps);
        this.equips = equips;
    }
}

C#:

public class ClassRoom
{
    private int roomNum;     // מספר החדר
    private int seats;       // מספר מקומות הישיבה
    private int[,] arr;     // מערכת השיעורים: 10 שורות (שיעורים) על 5 עמודות (ימים)

    public ClassRoom(int roomNum, int seats, int[,] arr)
    {
        this.roomNum = roomNum;
        this.seats = seats;
        this.arr = arr;
    }
}

public class CompRoom : ClassRoom
{
    private int comps;       // מספר המחשבים

    public CompRoom(int roomNum, int seats, int[,] arr, int comps)
        : base(roomNum, seats, arr)
    {
        this.comps = comps;
    }
}

public class MediaRoom : CompRoom
{
    private string[] equips; // שמות סוגי הציוד שבחדר

    public MediaRoom(int roomNum, int seats, int[,] arr, int comps, string[] equips)
        : base(roomNum, seats, arr, comps)
    {
        this.equips = equips;
    }
}

תשובה: ClassRoom ← CompRoom ← MediaRoom (שרשרת ירושה), כמפורט בתרשים ובקוד.

סעיף ב

תשובה:

isEquipmentExist - במחלקה MediaRoom (מחפשת את eq במערך equips); isFree - במחלקה ClassRoom (בודקת ש-arr[lesson-1][day-1] == 0), ועוברת בירושה ל-CompRoom ול-MediaRoom.

הפעולה isEquipmentExist - במחלקה MediaRoom. רק לחדר מולטימדיה יש מערך ציוד (equips), ולכן הפעולה שייכת לשם. עוברים על המערך ומשווים כל שם ל-eq (ב-Java משווים מחרוזות עם `equals`, לא עם `==`, כדי להשוות תוכן ולא הפניות; ב-C# האופרטור `==` משווה תוכן של מחרוזות). ברגע שנמצא - מחזירים true; אם הסתיים המערך - false.

Java:

// במחלקה MediaRoom
public boolean isEquipmentExist(String eq)
{
    for (int i = 0; i < this.equips.length; i++)
    {
        if (this.equips[i].equals(eq))
            return true;
    }
    return false;
}

C#:

// במחלקה MediaRoom
public bool IsEquipmentExist(string eq)
{
    for (int i = 0; i < this.equips.Length; i++)
    {
        if (this.equips[i] == eq)
            return true;
    }
    return false;
}

הפעולה isFree - במחלקה ClassRoom. מערכת השיעורים arr קיימת בכל סוגי החדרים, ולכן הפעולה נכתבת פעם אחת במחלקת-העל ועוברת בירושה ל-CompRoom ול-MediaRoom.

גודל המערך 10X5: 10 שורות - שיעור 1 עד 10, ו-5 עמודות - יום 1 עד 5. האינדקסים במערך מתחילים ב-0, ולכן השיעור lesson והיום day נמצאים בתא `arr[lesson-1][day-1]`. החדר פנוי אם בתא כתוב 0 (אין קבוצה).

Java:

// במחלקה ClassRoom
public boolean isFree(int day, int lesson)
{
    return this.arr[lesson - 1][day - 1] == 0;   // 0 - אין קבוצה בחדר
}

C#:

// במחלקה ClassRoom
public bool IsFree(int day, int lesson)
{
    return this.arr[lesson - 1, day - 1] == 0;   // 0 - אין קבוצה בחדר
}

תשובה: isEquipmentExist נכתבת ב-MediaRoom; isFree נכתבת ב-ClassRoom (ומשמשת את כל סוגי החדרים).

סעיף ג

תשובה:

התכונה: `ClassRoom[] rooms`. printFreeCompRooms מדפיסה (toString) כל חדר שהוא CompRoom ואינו MediaRoom ושעבורו isFree(day, lesson); collectEquipmentExist מחזירה Queue<MediaRoom> של חדרי המולטימדיה שבהם isEquipmentExist(eq).

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

Java:

public class College
{
    private ClassRoom[] rooms;
}

C#:

public class College
{
    private ClassRoom[] rooms;
}

2. printFreeCompRooms. עוברים על כל החדרים. מעבדת מחשבים היא עצם מסוג CompRoom - אבל גם MediaRoom עונה על `instanceof CompRoom` (כי היא יורשת ממנה), ולכן מסננים גם את חדרי המולטימדיה: `r instanceof CompRoom && !(r instanceof MediaRoom)`. אם החדר הוא מעבדת מחשבים והוא פנוי (`isFree` שנכתבה ב-ClassRoom, ולכן אפשר לזמן אותה דרך הפניה מטיפוס ClassRoom בלי המרה) - מדפיסים את פרטיו. ההדפסה של העצם מזמנת את toString שלו (שהוגדרה בכל מחלקה - פולימורפיזם).

Java:

public void printFreeCompRooms(int day, int lesson)
{
    for (int i = 0; i < this.rooms.length; i++)
    {
        ClassRoom r = this.rooms[i];
        // מעבדת מחשבים: CompRoom שאינו חדר מולטימדיה
        if (r instanceof CompRoom && !(r instanceof MediaRoom) && r.isFree(day, lesson))
            System.out.println(r);       // toString של CompRoom
    }
}

C#:

public void PrintFreeCompRooms(int day, int lesson)
{
    for (int i = 0; i < this.rooms.Length; i++)
    {
        ClassRoom r = this.rooms[i];
        // מעבדת מחשבים: CompRoom שאינו חדר מולטימדיה
        if (r is CompRoom && !(r is MediaRoom) && r.IsFree(day, lesson))
            Console.WriteLine(r);       // ToString של CompRoom
    }
}

3. collectEquipmentExist. נחזיר את האוסף כתור של חדרי מולטימדיה - תור גדל לפי הצורך, ולכן אין בעיה של מקומות ריקים. לכל חדר: אם הוא MediaRoom, ממירים אליו (רק ב-MediaRoom יש `isEquipmentExist`) ובודקים אם הציוד קיים; אם כן - מכניסים אותו לתור. בסוף מחזירים את התור.

Java:

public Queue<MediaRoom> collectEquipmentExist(String eq)
{
    Queue<MediaRoom> result = new Queue<MediaRoom>();
    for (int i = 0; i < this.rooms.length; i++)
    {
        if (this.rooms[i] instanceof MediaRoom)
        {
            MediaRoom m = (MediaRoom) this.rooms[i];
            if (m.isEquipmentExist(eq))
                result.insert(m);
        }
    }
    return result;
}

C#:

public Queue<MediaRoom> CollectEquipmentExist(string eq)
{
    Queue<MediaRoom> result = new Queue<MediaRoom>();
    for (int i = 0; i < this.rooms.Length; i++)
    {
        if (this.rooms[i] is MediaRoom)
        {
            MediaRoom m = (MediaRoom) this.rooms[i];
            if (m.IsEquipmentExist(eq))
                result.Insert(m);
        }
    }
    return result;
}

דוגמה: במכללה חדר רגיל 1, מעבדות מחשבים 2, 3, 6 וחדרי מולטימדיה 4 (מקרן ורמקולים) ו-5 (מצלמה). אם בחדר 3 לומדת קבוצה ביום 2 בשיעור 3, אז `printFreeCompRooms(2, 3)` מדפיסה את חדרים 2 ו-6 בלבד, ו-`collectEquipmentExist("projector")` מחזירה תור שבו רק חדר 4.

תשובה: `private ClassRoom[] rooms;` והפעולות printFreeCompRooms ו-collectEquipmentExist שלמעלה.

שאלה 9 · בדיקת שרשרת חוליות XYX

נתונה הגדרה הבאה:

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

לדוגמה, השרשרת שלפניכם היא "שרשרת XYX":

א.

כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם שרשרת היא "שרשרת XYX". אם כן – הפעולה תחזיר ערך true, ואם לא – ערך false.

כותרת הפעולה:

Java:

public static boolean isXYX(Node<Integer> chain)

C#:

public static bool IsXYX(Node<int> chain)
(16 נקודות)
ב.

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

(2 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

הפעולה isXYX שלהלן: סופרת את אורך השרשרת n; אם n אינו מתחלק ב-3 (או השרשרת ריקה) מחזירה false; אחרת (k = n/3) משווה את החלק הראשון לשלישי איבר-איבר, דוחפת את החלק הראשון למחסנית ומשווה את החלק האמצעי לאיברים הנשלפים מהמחסנית (סדר הפוך).

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

1. אורך: סופרים את מספר החוליות n. אם n אינו מתחלק ב-3 - אי אפשר לחלק את השרשרת לשלושה חלקים כאלה, ומחזירים false. גם עבור שרשרת ריקה מחזירים false (אין בה חלקים). אורך כל חלק: k=n/3k=n/3.

2. מצביעים: p1 - לתחילת החלק הראשון (chain), p2 - לתחילת החלק האמצעי (k צעדים מההתחלה), p3 - לתחילת החלק האחרון (עוד k צעדים).

3. X ראשון = X אחרון: מתקדמים k צעדים עם p1 ו-p3 יחד ומשווים את הערכים; בכל שוני - false. באותו מעבר דוחפים את ערכי החלק הראשון למחסנית.

4. Y = X הפוך: המחסנית מחזירה את ערכי החלק הראשון מהאחרון לראשון. מתקדמים k צעדים עם p2 ומשווים כל ערך לערך שנשלף מהמחסנית; בכל שוני - false.

5. אם כל ההשוואות הצליחו - true.

(ב-Java משווים ערכי Integer עם `equals`, כדי להשוות ערכים ולא הפניות.)

Java:

public static boolean isXYX(Node<Integer> chain)
{
    // 1. אורך השרשרת
    int n = 0;
    for (Node<Integer> p = chain; p != null; p = p.getNext())
        n++;
    if (n == 0 || n % 3 != 0)          // אי אפשר לחלק לשלושה חלקים שווים
        return false;
    int k = n / 3;                     // אורך כל חלק

    // 2. הצבת p1 בתחילת X, p2 בתחילת Y, p3 בתחילת X השני
    Node<Integer> p1 = chain;
    Node<Integer> p2 = chain;
    for (int i = 0; i < k; i++)
        p2 = p2.getNext();
    Node<Integer> p3 = p2;
    for (int i = 0; i < k; i++)
        p3 = p3.getNext();

    // 3. החלק הראשון זהה לשלישי; ערכיו נדחפים למחסנית
    Stack<Integer> st = new Stack<Integer>();
    for (int i = 0; i < k; i++)
    {
        if (!p1.getValue().equals(p3.getValue()))
            return false;
        st.push(p1.getValue());
        p1 = p1.getNext();
        p3 = p3.getNext();
    }

    // 4. החלק האמצעי שווה ל-X בסדר הפוך: משווים למחסנית
    for (int i = 0; i < k; i++)
    {
        if (!p2.getValue().equals(st.pop()))
            return false;
        p2 = p2.getNext();
    }
    return true;
}

C#:

public static bool IsXYX(Node<int> chain)
{
    // 1. אורך השרשרת
    int n = 0;
    for (Node<int> p = chain; p != null; p = p.GetNext())
        n++;
    if (n == 0 || n % 3 != 0)          // אי אפשר לחלק לשלושה חלקים שווים
        return false;
    int k = n / 3;                     // אורך כל חלק

    // 2. הצבת p1 בתחילת X, p2 בתחילת Y, p3 בתחילת X השני
    Node<int> p1 = chain;
    Node<int> p2 = chain;
    for (int i = 0; i < k; i++)
        p2 = p2.GetNext();
    Node<int> p3 = p2;
    for (int i = 0; i < k; i++)
        p3 = p3.GetNext();

    // 3. החלק הראשון זהה לשלישי; ערכיו נדחפים למחסנית
    Stack<int> st = new Stack<int>();
    for (int i = 0; i < k; i++)
    {
        if (p1.GetValue() != p3.GetValue())
            return false;
        st.Push(p1.GetValue());
        p1 = p1.GetNext();
        p3 = p3.GetNext();
    }

    // 4. החלק האמצעי שווה ל-X בסדר הפוך: משווים למחסנית
    for (int i = 0; i < k; i++)
    {
        if (p2.GetValue() != st.Pop())
            return false;
        p2 = p2.GetNext();
    }
    return true;
}

בדיקה על הדוגמה: השרשרת 10, 20, 15, 15, 20, 10, 10, 20, 15: n = 9, k = 3.

צעדחלק ראשון (p1)חלק אחרון (p3)שווים?
01010כן
12020כן
21515כן

במחסנית (מהראש): 15, 20, 10.

צעדחלק אמצעי (p2)נשלף מהמחסניתשווים?
01515כן
12020כן
21010כן

← true. דוגמאות נוספות: 1, 2, 2, 1, 1, 2 ← true; 1, 2, 1, 2, 1, 2 ← false (האמצעי אינו הפוך); שרשרת באורך 2 ← false.

תשובה: הפעולה isXYX שלמעלה.

סעיף ב

תשובה:

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

נסמן ב-n את מספר החוליות, k=n/3k=n/3.

1. ספירת האורך - מעבר אחד על השרשרת: n צעדים.

2. הצבת p2 ו-p3: 2k2k צעדים.

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

4. השוואת החלק האמצעי לערכים מהמחסנית: k סיבובים, כל אחד O(1)O(1).

5. בסך הכול n+4k=n+4n3n+4k=n+\frac{4n}{3} פעולות קבועות לכל היותר - סיבוכיות לינארית. (זיכרון נוסף: מחסנית של kk ערכים, O(n)O(n).)

תשובה: O(n)O(n).

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

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

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