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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · תור צומח בקיצוניות

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

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

כי:

- 5 > 2

- 10 > 2 +5

- 20 > 10 +2+5

א.

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

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

Java:

public static boolean isGreater(Queue<Integer> q, int num)

C#:

public static bool IsGreater(Queue<int> q, int num)
(6 נקודות)
ב.

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

לדוגמה, עבור התור q: 2, 1, 5, 6, 10, 16, 12, 20

הפעולה תחזיר תור חדש: 2, 5, 10, 20

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

Java:

public static Queue<Integer> buildExtreme(Queue<Integer> q)

C#:

public static Queue<int> BuildExtreme(Queue<int> q)

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

(8 נקודות)
ג.

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

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

סעיף א

תשובה:

הפעולה isGreater שלהלן: סוכמת את איברי q בעזרת תור עזר (ומשחזרת את q), ומחזירה num > sum.

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

1. `sum = 0`.

2. כל עוד q אינו ריק: מוציאים איבר `x`, מוסיפים אותו ל-`sum` ומכניסים אותו ל-`temp`.

3. כל עוד `temp` אינו ריק: מעבירים את האיבר שבראשו חזרה ל-q.

4. מחזירים את תוצאת ההשוואה `num > sum`.

Java:

public static boolean isGreater(Queue<Integer> q, int num) {
    Queue<Integer> temp = new Queue<Integer>();
    int sum = 0;
    while (!q.isEmpty()) {          // מוציאים את כל האיברים, סוכמים ושומרים בתור עזר
        int x = q.remove();
        sum += x;
        temp.insert(x);
    }
    while (!temp.isEmpty()) {       // מחזירים את האיברים ל-q באותו סדר
        q.insert(temp.remove());
    }
    return num > sum;
}

C#:

public static bool IsGreater(Queue<int> q, int num) {
    Queue<int> temp = new Queue<int>();
    int sum = 0;
    while (!q.IsEmpty()) {          // מוציאים את כל האיברים, סוכמים ושומרים בתור עזר
        int x = q.Remove();
        sum += x;
        temp.Insert(x);
    }
    while (!temp.IsEmpty()) {       // מחזירים את האיברים ל-q באותו סדר
        q.Insert(temp.Remove());
    }
    return num > sum;
}

דוגמה: עבור התור 2, 5, 10, 20 הסכום הוא 2+5+10+20=372+5+10+20=37. לכן `isGreater(q, 38)` מחזירה true, ו-`isGreater(q, 37)` מחזירה false (37 אינו גדול מ-37). עבור תור ריק הסכום הוא 0, ולכן כל num חיובי גדול ממנו.

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

סעיף ב

תשובה:

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

הרעיון: נבנה את התור החדש `result` איבר אחר איבר, לפי סדר האיברים ב-q. איבר x מצטרף לסוף `result` רק אם הוא גדול מסכום כל האיברים שכבר נמצאים ב-`result` - כלומר מסכום כל האיברים שיקדמו לו בתור החדש. זו בדיוק הבדיקה של סעיף א': `isGreater(result, x)`. כך כל איבר שנכנס מקיים את התנאי, ו-`result` הוא "תור צומח בקיצוניות". (האיבר הראשון תמיד נכנס: הסכום של תור ריק הוא 0, והמספרים חיוביים.)

כדי לשמור על q, כל איבר שהוצא ממנו נכנס לתור עזר `temp`, ובסוף מחזירים את האיברים ל-q. (הפעולה isGreater עצמה משחזרת את `result`, ולכן אפשר לקרוא לה שוב ושוב.)

1. יוצרים תור ריק `result` ותור עזר `temp`.

2. כל עוד q אינו ריק: מוציאים איבר `x` ומכניסים אותו ל-`temp`; אם `isGreater(result, x)` - מכניסים את `x` ל-`result`.

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

4. מחזירים את `result`.

Java:

public static Queue<Integer> buildExtreme(Queue<Integer> q) {
    Queue<Integer> result = new Queue<Integer>();
    Queue<Integer> temp = new Queue<Integer>();
    while (!q.isEmpty()) {
        int x = q.remove();
        temp.insert(x);
        if (isGreater(result, x)) {  // x גדול מסכום כל האיברים שכבר בתור החדש
            result.insert(x);
        }
    }
    while (!temp.isEmpty()) {        // שחזור התור q
        q.insert(temp.remove());
    }
    return result;
}

C#:

public static Queue<int> BuildExtreme(Queue<int> q) {
    Queue<int> result = new Queue<int>();
    Queue<int> temp = new Queue<int>();
    while (!q.IsEmpty()) {
        int x = q.Remove();
        temp.Insert(x);
        if (IsGreater(result, x)) {  // x גדול מסכום כל האיברים שכבר בתור החדש
            result.Insert(x);
        }
    }
    while (!temp.IsEmpty()) {        // שחזור התור q
        q.Insert(temp.Remove());
    }
    return result;
}

מעקב על הדוגמה (q: 2, 1, 5, 6, 10, 16, 12, 20):

איבר xסכום result לפניx גדול מהסכום?result אחרי
20כן2
12לא2
52כן2, 5
67לא2, 5
107כן2, 5, 10
1617לא2, 5, 10
1217לא2, 5, 10
2017כן2, 5, 10, 20

התור המוחזר הוא 2, 5, 10, 20, כמו בדוגמה, ו-q נשאר 2, 1, 5, 6, 10, 16, 12, 20.

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

סעיף ג

תשובה:

סעיף א': O(n)O(n); סעיף ב': O(n2)O(n^2) במקרה הגרוע (n - מספר האיברים ב-q).

נסמן ב-nn את מספר האיברים בתור q. כל פעולות התור (`insert`, `remove`, `isEmpty`) הן O(1)O(1).

1. isGreater (סעיף א'): כל איבר יוצא מ-q ונכנס ל-`temp` פעם אחת, ואחר כך חוזר ל-q פעם אחת. כ-2n2n פעולות קבועות, ולכן O(n)O(n).

2. buildExtreme (סעיף ב'): הלולאה עוברת על nn האיברים של q, ולכל איבר קוראת ל-`isGreater(result, x)`, שעולה O(k)O(k) כאשר kk מספר האיברים שכבר ב-`result`. במקרה הגרוע כל איברי q נכנסים ל-`result` (למשל q = 1, 2, 4, 8, ...), ואז kk גדל עד nn, וסך העבודה הוא 0+1+2+⋯+(n−1)=n(n−1)20+1+2+\dots+(n-1)=\frac{n(n-1)}{2}, כלומר O(n2)O(n^2). השחזור של q מוסיף רק O(n)O(n).

תשובה: סעיף א' - O(n)O(n); סעיף ב' - O(n2)O(n^2) (במקרה הגרוע).

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

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

לדוגמה:

•ה"עוצמה" של החוליה p1 היא 1;

•ה"עוצמה" של החוליה p2 היא 5;

•ה"עוצמה" של החוליה p3 היא 0.

א.

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

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

Java:

public static int getMagnitude(Node<Integer> p)

C#:

public static int GetMagnitude (Node<int> p)
(7 נקודות)
ב.

נתונה שרשרת חוליות באורך n. מהו הערך המקסימלי האפשרי ל"עוצמה" של חוליה כלשהי בשרשרת זו? הסבירו את תשובתכם.

(2 נקודות)
ג.

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

Java:

public static void printByMagnitude(Node<Integer> chain)

C#:

public static void PrintByMagnitude(Node<int> chain)
(7 נקודות)
◂ פתרון מלא לשאלה 2

סעיף א

תשובה:

הפעולה getMagnitude שלהלן: מתקדמת מהחוליה שאחרי p כל עוד הערך קטן מערך p וסופרת את החוליות.

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

1. `count = 0`, `cur = p.getNext()`.

2. כל עוד `cur != null` וגם `cur.getValue() < p.getValue()`: מגדילים את `count` ומתקדמים.

3. מחזירים את `count`.

Java:

public static int getMagnitude(Node<Integer> p) {
    int count = 0;
    Node<Integer> cur = p.getNext();
    while (cur != null && cur.getValue() < p.getValue()) {
        count++;
        cur = cur.getNext();
    }
    return count;
}

C#:

public static int GetMagnitude(Node<int> p) {
    int count = 0;
    Node<int> cur = p.GetNext();
    while (cur != null && cur.GetValue() < p.GetValue()) {
        count++;
        cur = cur.GetNext();
    }
    return count;
}

בדיקה על הדוגמה (11 → 2 → 30 → 4 → 11 → 2 → 15 → 4):

•p1 (ערך 11): אחריו 2 (קטן, נספר), ואחר כך 30 (לא קטן) - עוצרים. עוצמה 1.

•p2 (ערך 30): אחריו 4, 11, 2, 15, 4 - כולם קטנים מ-30, והשרשרת נגמרת. עוצמה 5.

•p3 (ערך 2): אחריו 15, שאינו קטן מ-2. עוצמה 0.

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

סעיף ב

תשובה:

n-1

1. העוצמה של חוליה סופרת רק חוליות שנמצאות אחריה בשרשרת.

2. החוליה שאחריה יש הכי הרבה חוליות היא החוליה הראשונה: יש אחריה n−1n-1 חוליות.

3. לכן העוצמה אינה יכולה לעלות על n−1n-1, והערך הזה מתקבל כאשר ערך החוליה הראשונה גדול מערכי כל שאר החוליות (למשל 9 → 5 → 3 → 7: העוצמה של 9 היא 3 = 4-1).

תשובה: n−1n-1.

סעיף ג

תשובה:

הפעולה printByMagnitude שלהלן: מוצאת את העוצמה המקסימלית, ואז לכל עוצמה k מ-0 עד המקסימום עוברת על השרשרת ומדפיסה את ערכי החוליות שעוצמתן k. לדוגמה: 2 4 2 4 11 11 15 30.

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

1. מעבר ראשון: מחשבים את העוצמה של כל חוליה ושומרים את המקסימום ב-`max`.

2. לכל `k` מ-0 עד `max`: עוברים על השרשרת ומדפיסים את ערך כל חוליה ש-`getMagnitude(p) == k`.

Java:

public static void printByMagnitude(Node<Integer> chain) {
    int max = -1;                       // העוצמה הגדולה ביותר בשרשרת
    for (Node<Integer> p = chain; p != null; p = p.getNext()) {
        int m = getMagnitude(p);
        if (m > max) max = m;
    }
    for (int k = 0; k <= max; k++) {    // מעבר לכל עוצמה, מהקטנה לגדולה
        for (Node<Integer> p = chain; p != null; p = p.getNext()) {
            if (getMagnitude(p) == k) {
                System.out.print(p.getValue() + " ");
            }
        }
    }
    System.out.println();
}

C#:

public static void PrintByMagnitude(Node<int> chain) {
    int max = -1;                       // העוצמה הגדולה ביותר בשרשרת
    for (Node<int> p = chain; p != null; p = p.GetNext()) {
        int m = GetMagnitude(p);
        if (m > max) max = m;
    }
    for (int k = 0; k <= max; k++) {    // מעבר לכל עוצמה, מהקטנה לגדולה
        for (Node<int> p = chain; p != null; p = p.GetNext()) {
            if (GetMagnitude(p) == k) {
                Console.Write(p.GetValue() + " ");
            }
        }
    }
    Console.WriteLine();
}

בדיקה על הדוגמה: העוצמות של החוליות 11, 2, 30, 4, 11, 2, 15, 4 הן 1, 0, 5, 0, 1, 0, 1, 0, והמקסימום הוא 5.

עוצמה kערכים מודפסים
02 4 2 4
111 11 15
2, 3, 4(אין)
530

הפלט: `2 4 2 4 11 11 15 30`.

(סיבוכיות: חישוב עוצמה הוא O(n)O(n), כל מעבר על השרשרת הוא O(n2)O(n^2), ויש עד nn מעברים - O(n3)O(n^3) במקרה הגרוע.)

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

שאלה 3 · היררכיית מחלקות וממשקים, המרות טיפוסים

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

•הממשק IFlier כולל את כותרת הפעולה

`public void fly()` (ב-C#: `public void Fly()`).

•הממשק IGPS כולל את כותרת הפעולה

`public void navigate(double x, double y)` (ב-C#: `public void Navigate(double x, double y)`).

•המחלקה Device היא מחלקת בסיס (על), ולה תכונה

`protected String serialNum` (ב-C#: `protected string serialNum`).

•המחלקה Drone יורשת מ-Device ומממשת את הממשקים IFlier ו-IGPS.

המחלקה גם כוללת פעולה ייחודית

`public void takePhoto()` (ב-C#: `public void TakePhoto()`).

•המחלקה SmartPhone יורשת מ-Device ומממשת את הממשק IGPS.

המחלקה גם כוללת פעולה ייחודית

`public void call()` (ב-C#: `public void Call()`).

•המחלקה PaperPlane מממשת רק את הממשק IFlier.

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

א.

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

הנחיות לציור:

•השתמשו בציון ברור עבור מחלקות וממשקים (ציינו מי הוא interface ומי class).

•השתמשו בחץ רציף לסימון ירושה (———>).

•השתמשו בחץ מקווקו לסימון מימוש ממשק (— — >).

(3 נקודות)
ב.

עבור המחלקות Device, Drone, SmartPhone ו-PaperPlane, כתבו את כותרת המחלקה ואת כותרות הפעולות (__אין צורך לממש את הפעולות__).

(4 נקודות)
ג.

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

Java:

6. Device d = new Drone();

7. IFlier f = new IFlier();

8. IGPS g = new SmartPhone();

9. IFlier f2 = new Drone();
   ((Drone)f2).fly();

10.     Device d2 = new Device();
   ((Drone)d2).fly();

C#:

1. Device d = new Drone();

2. IFlier f = new IFlier();

3. IGPS g = new SmartPhone();

4. IFlier f2 = new Drone();
   ((Drone)f2).Fly();

5. Device d2 = new Device();
   ((Drone)d2).Fly();
(5 נקודות)
ד.

כתבו פעולה חיצונית המקבלת כפרמטר מערך items של עצמים מטיפוס Object. הפעולה תעבור על המערך ותדפיס "Fly" עבור כל עצם שמממש את הממשק IFlier, ותדפיס "Navigate" עבור כל עצם שמממש את הממשק IGPS.

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

סעיף א

תשובה:

שני ממשקים (IFlier, IGPS) ומחלקת על Device; Drone ו-SmartPhone יורשות מ-Device (חץ רציף); Drone מממשת את IFlier ואת IGPS, SmartPhone מממשת את IGPS ו-PaperPlane מממשת את IFlier (חצים מקווקווים).

מה משרטטים: שישה מלבנים, בכל אחד שם ומעליו הסוג: `<<interface>>` או `class`. החצים יוצאים מהמחלקה היורשת/המממשת ומצביעים אל מחלקת העל/הממשק.

1. שורה עליונה: שלושה מלבנים - `<<interface>> IFlier`, `<<interface>> IGPS`, `class Device`.

2. שורה תחתונה: שלושה מלבנים - `class Drone`, `class SmartPhone`, `class PaperPlane`.

3. חצים רציפים (ירושה): Drone ———> Device ו-SmartPhone ———> Device.

4. חצים מקווקווים (מימוש ממשק): Drone — — > IFlier, Drone — — > IGPS, SmartPhone — — > IGPS, PaperPlane — — > IFlier.

5. ל-PaperPlane אין חץ רציף: היא אינה יורשת מ-Device (במפורש), רק מממשת ממשק.

סיכום הקשרים:

רכיבסוגיורש מ- (חץ רציף)מממש (חץ מקווקו)
IFlierinterface––
IGPSinterface––
Deviceclass––
DroneclassDeviceIFlier, IGPS
SmartPhoneclassDeviceIGPS
PaperPlaneclass–IFlier

תשובה: העץ המתואר בטבלה ובשלבים 1-4.

סעיף ב

תשובה:

Device - מחלקת על עם serialNum ובנאי; Drone יורשת מ-Device ומממשת IFlier, IGPS (fly, navigate, takePhoto); SmartPhone יורשת מ-Device ומממשת IGPS (navigate, call); PaperPlane מממשת IFlier (fly). הכותרות המלאות בפתרון.

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

•ב-Drone יש `fly` (מ-IFlier), `navigate` (מ-IGPS) והפעולה הייחודית `takePhoto`;

•ב-SmartPhone יש `navigate` (מ-IGPS) והפעולה הייחודית `call`;

•ב-PaperPlane יש `fly` (מ-IFlier).

לכל מחלקה יש גם פעולה בונה ללא פרמטרים (לפי ההערה). ב-Java הירושה נכתבת ב-`extends` והמימוש ב-`implements`; ב-C# שניהם אחרי נקודתיים, מחלקת העל ראשונה. לשלמות מופיעות גם הגדרות הממשקים. (`{ ... }` מסמן גוף שאין צורך לממש.)

Java:

public interface IFlier {
    public void fly();
}

public interface IGPS {
    public void navigate(double x, double y);
}

public class Device {
    protected String serialNum;
    public Device() { ... }
}

public class Drone extends Device implements IFlier, IGPS {
    public Drone() { ... }
    public void fly() { ... }
    public void navigate(double x, double y) { ... }
    public void takePhoto() { ... }
}

public class SmartPhone extends Device implements IGPS {
    public SmartPhone() { ... }
    public void navigate(double x, double y) { ... }
    public void call() { ... }
}

public class PaperPlane implements IFlier {
    public PaperPlane() { ... }
    public void fly() { ... }
}

C#:

public interface IFlier {
    void Fly();
}

public interface IGPS {
    void Navigate(double x, double y);
}

public class Device {
    protected string serialNum;
    public Device() { ... }
}

public class Drone : Device, IFlier, IGPS {
    public Drone() { ... }
    public void Fly() { ... }
    public void Navigate(double x, double y) { ... }
    public void TakePhoto() { ... }
}

public class SmartPhone : Device, IGPS {
    public SmartPhone() { ... }
    public void Navigate(double x, double y) { ... }
    public void Call() { ... }
}

public class PaperPlane : IFlier {
    public PaperPlane() { ... }
    public void Fly() { ... }
}

תשובה: הכותרות שלמעלה.

סעיף ג

תשובה:

1 (6) תקינה; 2 (7) שגיאת הידור - אי אפשר ליצור עצם מממשק; 3 (8) תקינה; 4 (9) תקינה; 5 (10) שגיאת זמן ריצה - המרה של עצם Device ל-Drone.

(המספור ב-Java הוא 6-10, ב-C# 1-5; ההוראות זהות.) לכל הוראה בודקים שני שלבים: בזמן הידור - האם הטיפוס שמימין מתאים לטיפוס המשתנה, והאם ההמרה (casting) אפשרית בין הטיפוסים; בזמן ריצה - האם העצם שנוצר בפועל הוא באמת מהטיפוס שאליו ממירים.

1. הוראה 1 (6): `Device d = new Drone();` - תקינה. Drone יורשת מ-Device, ולכן הפניה מטיפוס Device יכולה להצביע על עצם Drone (המרה כלפי מעלה).

2. הוראה 2 (7): `IFlier f = new IFlier();` - אינה תקינה, שגיאת הידור. IFlier הוא ממשק; אי אפשר ליצור עצם מממשק (אין לו פעולה בונה ואין מימוש לפעולות).

3. הוראה 3 (8): `IGPS g = new SmartPhone();` - תקינה. SmartPhone מממשת את IGPS, ולכן הפניה מטיפוס הממשק יכולה להצביע עליה.

4. הוראה 4 (9): `IFlier f2 = new Drone();` ואחריה `((Drone)f2).fly();` - תקינה. השורה הראשונה תקינה כי Drone מממשת את IFlier. בשורה השנייה ההמרה ל-Drone עוברת הידור, ובזמן ריצה העצם הוא באמת Drone, ולכן ההמרה מצליחה והפעולה fly של Drone מופעלת.

5. הוראה 5 (10): `Device d2 = new Device();` ואחריה `((Drone)d2).fly();` - אינה תקינה, שגיאת זמן ריצה. השורה הראשונה תקינה (Device אינה מופשטת ויש לה בנאי ללא פרמטרים). ההמרה `(Drone)d2` עוברת הידור, כי Drone היא תת-מחלקה של Device והפניה מטיפוס Device יכולה בעיקרון להצביע על Drone. אבל בזמן ריצה העצם הוא Device ולא Drone, ולכן ההמרה נכשלת: ב-Java נזרקת `ClassCastException`, וב-C# - `InvalidCastException`.

תשובה: הוראות 1, 3, 4 (ב-Java 6, 8, 9) תקינות; הוראה 2 (7) - שגיאת הידור; הוראה 5 (10) - שגיאת זמן ריצה.

סעיף ד

תשובה:

הפעולה printActions שלהלן: לכל איבר בודקת instanceof IFlier (ב-C#: is IFlier) ומדפיסה "Fly", ובנפרד בודקת instanceof IGPS (is IGPS) ומדפיסה "Navigate".

הרעיון: המערך הוא מטיפוס Object, ולכן כל עצם יכול להופיע בו. לכל איבר נבדוק בזמן ריצה אם העצם מממש את הממשק בעזרת `instanceof` (ב-C#: `is`). שתי הבדיקות נפרדות (לא `else`), כי עצם יכול לממש את שני הממשקים - Drone, למשל - ואז יודפסו עבורו גם "Fly" וגם "Navigate". עבור איבר `null` שתי הבדיקות מחזירות false, ולכן לא יודפס עבורו דבר. שם הפעולה לא נקבע בשאלה; נקרא לה printActions.

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

2. אם האיבר מממש את IFlier - מדפיסים "Fly".

3. אם האיבר מממש את IGPS - מדפיסים "Navigate".

Java:

public static void printActions(Object[] items) {
    for (int i = 0; i < items.length; i++) {
        if (items[i] instanceof IFlier) {
            System.out.println("Fly");
        }
        if (items[i] instanceof IGPS) {
            System.out.println("Navigate");
        }
    }
}

C#:

public static void PrintActions(object[] items) {
    for (int i = 0; i < items.Length; i++) {
        if (items[i] is IFlier) {
            Console.WriteLine("Fly");
        }
        if (items[i] is IGPS) {
            Console.WriteLine("Navigate");
        }
    }
}

דוגמה: עבור המערך {Drone, SmartPhone, PaperPlane, Device} יודפס: Fly, Navigate (עבור Drone), Navigate (SmartPhone), Fly (PaperPlane), ועבור Device - כלום.

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

שאלה 4 · העברת חוליות זוגיות לתחילת השרשרת

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

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

א.

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

Java:

public static Node<Integer> lastEvenNode(Node<Integer> ch)

C#:

public static Node<int> LastEvenNode(Node<int> ch)
(4 נקודות)
ב.

כתבו פעולה חיצונית המקבלת הפניה לחוליה הראשונה בשרשרת ch. הפעולה תאתר את החוליה הזוגית האחרונה בשרשרת ותעביר אותה (__על ידי שינוי מצביעים בלבד!__) כך שתהיה החוליה הראשונה בשרשרת. הפעולה תחזיר הפניה לחוליה הראשונה החדשה. כותרת הפעולה:

Java:

public static Node<Integer> lastEvenToFront(Node<Integer> ch)

C#:

public static Node<int> LastEvenToFront(Node<int> ch)

יש להשתמש בפעולה lastEvenNode מסעיף א'.

(6 נקודות)
ג.

נתונה הפעולה `countEven(Node<Integer> ch)` (ב-C#: `CountEven(Node<int> ch)`) המחזירה את מספר הערכים הזוגיים בשרשרת (__אין צורך לממש את הפעולה__).

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

Java:

public static Node<Integer> allEventsToFront(Node<Integer> ch)

C#:

public static Node<int> AllEventsToFront(Node<int> ch)

יש להשתמש בפעולה countEven ובפעולה lastEvenToFront.

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

סעיף א

תשובה:

הפעולה lastEvenNode שלהלן: עוברת על כל השרשרת ושומרת ב-last את החוליה הזוגית האחרונה שנמצאה (בהתחלה null).

הרעיון: אי אפשר לדעת שחוליה זוגית היא האחרונה עד שמגיעים לסוף השרשרת. לכן עוברים על כל השרשרת, ובכל פעם שנמצאת חוליה זוגית מעדכנים את `last` להצביע עליה. בסוף המעבר `last` מצביע על החוליה הזוגית האחרונה, ואם לא נמצאה אף חוליה זוגית - הוא נשאר null.

1. `last = null`, `p = ch`.

2. כל עוד `p != null`: אם ערך `p` זוגי (`% 2 == 0`) - `last = p`; מתקדמים.

3. מחזירים את `last`.

Java:

public static Node<Integer> lastEvenNode(Node<Integer> ch) {
    Node<Integer> last = null;
    Node<Integer> p = ch;
    while (p != null) {
        if (p.getValue() % 2 == 0) {
            last = p;               // החוליה הזוגית האחרונה שראינו עד כה
        }
        p = p.getNext();
    }
    return last;
}

C#:

public static Node<int> LastEvenNode(Node<int> ch) {
    Node<int> last = null;
    Node<int> p = ch;
    while (p != null) {
        if (p.GetValue() % 2 == 0) {
            last = p;               // החוליה הזוגית האחרונה שראינו עד כה
        }
        p = p.GetNext();
    }
    return last;
}

דוגמה: בשרשרת 3 → 8 → 5 → 6 → 7 → 1 → 4 → 9 מוחזרת ההפניה לחוליה שערכה 4; בשרשרת 1 → 3 → 5 מוחזר null.

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

סעיף ב

תשובה:

הפעולה lastEvenToFront שלהלן: מוצאת את last בעזרת lastEvenNode; אם אין כזו או שהיא כבר ראשונה - מחזירה ch; אחרת מוצאת את החוליה שלפניה, מנתקת את last ומחברת אותה לפני ch, ומחזירה את last.

הרעיון: כדי להעביר חוליה למקום אחר בשרשרת בלי ליצור חוליה חדשה, צריך (1) לנתק אותה ממקומה - לחבר את החוליה שלפניה ישירות לחוליה שאחריה, ו-(2) לחבר אותה לפני הראש הנוכחי. בשרשרת חד-כיוונית אין קישור אחורה, ולכן את החוליה שלפני `last` מוצאים במעבר מתחילת השרשרת.

מקרים מיוחדים: אם אין חוליה זוגית (`last == null`) או שהחוליה הזוגית האחרונה כבר ראשונה (`last == ch`), השרשרת לא משתנה ומחזירים את `ch`.

1. `last = lastEvenNode(ch)`; בודקים את המקרים המיוחדים.

2. מתקדמים עם `prev` מ-`ch` עד ש-`prev.getNext() == last`.

3. `prev.setNext(last.getNext())` - `last` מנותקת, והשרשרת "מדלגת" עליה.

4. `last.setNext(ch)` - `last` מצביעה על הראש הישן.

5. מחזירים את `last` - הראש החדש.

Java:

public static Node<Integer> lastEvenToFront(Node<Integer> ch) {
    Node<Integer> last = lastEvenNode(ch);
    if (last == null || last == ch) {   // אין חוליה זוגית, או שהיא כבר ראשונה
        return ch;
    }
    Node<Integer> prev = ch;            // מחפשים את החוליה שלפני last
    while (prev.getNext() != last) {
        prev = prev.getNext();
    }
    prev.setNext(last.getNext());       // מנתקים את last ממקומה
    last.setNext(ch);                   // ומחברים אותה לפני הראש הישן
    return last;
}

C#:

public static Node<int> LastEvenToFront(Node<int> ch) {
    Node<int> last = LastEvenNode(ch);
    if (last == null || last == ch) {   // אין חוליה זוגית, או שהיא כבר ראשונה
        return ch;
    }
    Node<int> prev = ch;            // מחפשים את החוליה שלפני last
    while (prev.GetNext() != last) {
        prev = prev.GetNext();
    }
    prev.SetNext(last.GetNext());       // מנתקים את last ממקומה
    last.SetNext(ch);                   // ומחברים אותה לפני הראש הישן
    return last;
}

דוגמה: עבור 3 → 8 → 5 → 6 → 7 → 1 → 4 → 9, החוליה הזוגית האחרונה היא 4 והחוליה שלפניה היא 1. אחרי `1.setNext(9)` ו-`4.setNext(3)` מתקבלת השרשרת 4 → 3 → 8 → 5 → 6 → 7 → 1 → 9.

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

סעיף ג

תשובה:

הפעולה allEventsToFront שלהלן: מחשבת k = countEven(ch) וקוראת k פעמים ל-lastEvenToFront, כל פעם עם הראש החדש. כל הזוגיים עוברים לתחילת השרשרת (אפילו בסדרם המקורי).

הרעיון: נסמן את החוליות הזוגיות לפי סדרן בשרשרת e1,e2,…,eke_1, e_2, \dots, e_k (כאשר kk = `countEven(ch)`).

•הקריאה הראשונה ל-`lastEvenToFront` מעבירה את eke_k לראש השרשרת.

•בקריאה השנייה, eke_k כבר בראש, ולכן החוליה הזוגית האחרונה בשרשרת היא ek−1e_{k-1} - והיא עוברת לראש, לפני eke_k.

•כך הלאה: אחרי jj קריאות, בתחילת השרשרת נמצאות ek−j+1,…,eke_{k-j+1}, \dots, e_k, ובהמשך נמצאות שאר החוליות, ובהן e1,…,ek−je_1, \dots, e_{k-j}.

אחרי kk קריאות כל kk החוליות הזוגיות נמצאות בתחילת השרשרת, בסדר e1,e2,…,eke_1, e_2, \dots, e_k, ואחריהן האי-זוגיות בסדרן המקורי. מספר הקריאות חייב להיות בדיוק kk, ולכן משתמשים ב-`countEven`. אין מבנה נתונים נוסף ואין חוליות חדשות - רק שינויי מצביעים בתוך `lastEvenToFront`.

1. `k = countEven(ch)`.

2. חוזרים kk פעמים: `ch = lastEvenToFront(ch)` (חשוב לעדכן את `ch`, כי הראש משתנה).

3. מחזירים את `ch`.

Java:

public static Node<Integer> allEventsToFront(Node<Integer> ch) {
    int k = countEven(ch);
    for (int i = 0; i < k; i++) {
        ch = lastEvenToFront(ch);
    }
    return ch;
}

C#:

public static Node<int> AllEventsToFront(Node<int> ch) {
    int k = CountEven(ch);
    for (int i = 0; i < k; i++) {
        ch = LastEvenToFront(ch);
    }
    return ch;
}

מעקב על 3 → 8 → 5 → 6 → 7 → 1 → 4 → 9 (k = 3):

קריאההחוליה שעוברתהשרשרת אחרי הקריאה
144 → 3 → 8 → 5 → 6 → 7 → 1 → 9
266 → 4 → 3 → 8 → 5 → 7 → 1 → 9
388 → 6 → 4 → 3 → 5 → 7 → 1 → 9

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

שאלה 5 · תכנון מחלקות למרכז לוגיסטי

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

להלן הגדרות התפקידים במרכז:

תפקידתיאור תפקיד
סדרן (Dispatcher)עובד האחראי על שיבוץ משלוחים לאזורי הפצה. נוסף לתכונות העובד הכלליות, לסדרן יש תכונה מספר עמדה (stationNum) מטיפוס שלם.
נהג (Driver)עובד בעל תכונה סוג רישיון (licenseType) מטיפוס מחרוזת. לדוגמה: "C1" , "E" , "C".
נהג משאית (TruckDriver)נוסף לתכונות הנהג, יש לו תכונה משקל מקסימלי מורשה (maxWeight) מטיפוס ממשי, המציינת את המשקל המקסימלי שהוא רשאי לשנע.
מנהל משמרת (Manager)מנהל המשמרת הוא עובד לכל דבר. הוא האחראי על צוות עובדים. למנהל יש מערך בשם team המכיל עד 20 העובדים הכפופים לו (מכל הסוגים) ותכונה current המייצגת את מספרם בפועל.
א.

שרטטו תרשים UML המתאר את הקשרים בין כל המחלקות. על התרשים לשקף את __עקרונות התכנות מונחה העצמים__ – הגדירו מחלקת על בשם Employee ובצעו הורשה והכלה בהתאם לתיאור.

השתמשו בחץ רציף ◄——— לירושה וחץ עם מעוין ◆——— להכלה.

(4 נקודות)
ב.

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

1. כותרת מחלקה;

2. תכונות – הקפידו על הרשאות גישה (private/protected/public) לפי עקרונות של תמ"ע ועל שימוש ב-static היכן שנדרש;

3. פעולה בונה (Constructor) המקבלת את הפרמטרים הרלוונטיים לאתחול העצם.

שימו לב: מספר העובד נוצר אוטומטית!

(6 נקודות)

אפשר להניח שקיימות פעולות get/set בכל אחד מהמחלקות – אין צורך לממש אותן. (ב-C#: Get/Set)

ג.

המחלקה LogisticsCenter כוללת מערך של כל עובדי המרכז בשם allEmployees ומונה total המציין מספר העובדים בפועל.

הוסיפו למחלקה את הפעולות האלה:

1. פעולה בשם heavyDutyCheck (ב-C#: HeavyDutyCheck). הפעולה תקבל כפרמטר משקל weight. הפעולה תחזיר את מספר הנהגים במערך שהם נהגי משאית המורשים להוביל משקל השווה ל-weight או גבוה ממנו.

2. פעולה בשם printAllDrivers (ב-C#: PrintAllDrivers). הפעולה תדפיס את השם ואת סוג הרישיון של כל נהג שהוא לא נהג משאית.

3. פעולה בשם printDriversByManager (ב-C#: PrintDriversByManager). הפעולה תדפיס עבור כל מנהל משמרת את שמו ואת שמם של כל נהגי המשאיות בצוות שלו.

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

סעיף א

תשובה:

Employee מחלקת על; Dispatcher, Driver ו-Manager יורשות מ-Employee; TruckDriver יורשת מ-Driver; Manager מכילה מערך של Employee (הכלה, מעוין בצד Manager).

ניתוח התיאור:

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

2. סדרן, נהג ומנהל משמרת הם עובדים ("הוא עובד") - ירושה מ-Employee.

3. נהג משאית הוא נהג עם תכונה נוספת ("נוסף לתכונות הנהג") - ירושה מ-Driver (ודרכה גם מ-Employee).

4. למנהל יש מערך team של עובדים ("מכל הסוגים") - הכלה בין Manager ל-Employee: המעוין צמוד ל-Manager (המכיל), והקו מגיע ל-Employee (המוכל), עם הריבוי 0..20.

מה משרטטים: בכל מלבן - שם המחלקה ותכונותיה, ובין המלבנים החצים:

מחלקהתכונותקשר
Employeecounter (static), name, empNumמחלקת על
DispatcherstationNumירושה ◄——— Employee
DriverlicenseTypeירושה ◄——— Employee
TruckDrivermaxWeightירושה ◄——— Driver
Managerteam (מערך Employee בגודל 20), currentירושה ◄——— Employee, וגם הכלה Manager ◆——— Employee

(החץ הרציף של הירושה יוצא מהמחלקה היורשת ומצביע אל מחלקת העל.)

תשובה: התרשים המתואר בטבלה.

סעיף ב

תשובה:

הקוד שלהלן: Employee עם מונה static פרטי counter שמקודם בבנאי ונותן empNum; תכונות private; כל תת-מחלקה מעבירה את name (ושאר הנתונים) לבנאי של מחלקת העל; Manager יוצר מערך team בגודל 20 ו-current = 0.

עקרונות:

1. הכמסה: כל התכונות `private`; הגישה אליהן בעזרת פעולות get/set (אפשר להניח שהן קיימות).

2. מספר עובד אוטומטי: תכונה `static` אחת `counter`, המשותפת לכל העצמים מכל המחלקות. הבנאי של Employee מגדיל אותה ב-1 ומעתיק את ערכה ל-`empNum`. כך העובד הראשון מקבל 1, השני 2, וכן הלאה, ואי אפשר לתת מספר כפול - והבנאי אינו מקבל את מספר העובד כפרמטר.

3. ירושה: כל בנאי של תת-מחלקה קורא קודם לבנאי של מחלקת העל (`super(...)` ב-Java, `: base(...)` ב-C#), כך שגם לכל סדרן, נהג ומנהל נקבע מספר עובד.

4. Employee מופשטת (abstract): כל עובד במרכז הוא אחד מהתפקידים, ולכן לא יוצרים עצם "עובד" כללי. (גם הגדרה רגילה, לא מופשטת, מתקבלת.)

5. Manager: הבנאי יוצר מערך ריק של 20 עובדים ו-`current = 0`; העובדים מתווספים אחר כך.

Java:

public abstract class Employee {
    private static int counter = 0;   // מונה משותף לכל העובדים
    private String name;
    private int empNum;

    public Employee(String name) {
        counter++;
        this.empNum = counter;        // מספר עובד ייחודי, ניתן אוטומטית
        this.name = name;
    }
}

public class Dispatcher extends Employee {
    private int stationNum;

    public Dispatcher(String name, int stationNum) {
        super(name);
        this.stationNum = stationNum;
    }
}

public class Driver extends Employee {
    private String licenseType;

    public Driver(String name, String licenseType) {
        super(name);
        this.licenseType = licenseType;
    }
}

public class TruckDriver extends Driver {
    private double maxWeight;

    public TruckDriver(String name, String licenseType, double maxWeight) {
        super(name, licenseType);
        this.maxWeight = maxWeight;
    }
}

public class Manager extends Employee {
    private Employee[] team;
    private int current;

    public Manager(String name) {
        super(name);
        this.team = new Employee[20];
        this.current = 0;
    }
}

C#:

public abstract class Employee {
    private static int counter = 0;   // מונה משותף לכל העובדים
    private string name;
    private int empNum;

    public Employee(string name) {
        counter++;
        this.empNum = counter;        // מספר עובד ייחודי, ניתן אוטומטית
        this.name = name;
    }
}

public class Dispatcher : Employee {
    private int stationNum;

    public Dispatcher(string name, int stationNum) : base(name) {
        this.stationNum = stationNum;
    }
}

public class Driver : Employee {
    private string licenseType;

    public Driver(string name, string licenseType) : base(name) {
        this.licenseType = licenseType;
    }
}

public class TruckDriver : Driver {
    private double maxWeight;

    public TruckDriver(string name, string licenseType, double maxWeight)
        : base(name, licenseType) {
        this.maxWeight = maxWeight;
    }
}

public class Manager : Employee {
    private Employee[] team;
    private int current;

    public Manager(string name) : base(name) {
        this.team = new Employee[20];
        this.current = 0;
    }
}

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

סעיף ג

תשובה:

שלוש הפעולות שלהלן: מעבר על allEmployees עד total ובדיקת טיפוס העצם בזמן ריצה (instanceof / is) - TruckDriver עם maxWeight ≥ weight; Driver שאינו TruckDriver; Manager - ולכל מנהל מעבר על team עד current והדפסת נהגי המשאית.

הרעיון: המערך allEmployees מטיפוס Employee מכיל עצמים מכל התפקידים (פולימורפיזם). לכן בכל פעולה עוברים על התאים 0 עד total-1, בודקים את הטיפוס האמיתי של העצם בעזרת `instanceof` (ב-C#: `is`), ורק אחרי הבדיקה ממירים (casting) לטיפוס המתאים כדי להשתמש בפעולות שלו.

1. heavyDutyCheck: סופרים עצמים שהם TruckDriver וש-`getMaxWeight() >= weight`.

2. printAllDrivers: עצם שהוא Driver וגם אינו TruckDriver. הבדיקה השנייה חשובה: נהג משאית יורש מ-Driver, ולכן גם עליו `instanceof Driver` מחזיר true.

3. printDriversByManager: לכל עצם שהוא Manager מדפיסים את שמו, ואז עוברים על המערך `team` שלו בתאים 0 עד `current`-1 ומדפיסים את שמות העובדים שהם TruckDriver. השם (`getName`) מוגדר ב-Employee, ולכן אין צורך בהמרה כדי להדפיס אותו.

Java:

public class LogisticsCenter {
    private Employee[] allEmployees;
    private int total;

    // 1. מספר נהגי המשאית שמורשים להוביל משקל weight או יותר
    public int heavyDutyCheck(double weight) {
        int count = 0;
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] instanceof TruckDriver) {
                TruckDriver t = (TruckDriver) allEmployees[i];
                if (t.getMaxWeight() >= weight) count++;
            }
        }
        return count;
    }

    // 2. שם וסוג רישיון של כל נהג שאינו נהג משאית
    public void printAllDrivers() {
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] instanceof Driver && !(allEmployees[i] instanceof TruckDriver)) {
                Driver d = (Driver) allEmployees[i];
                System.out.println(d.getName() + " " + d.getLicenseType());
            }
        }
    }

    // 3. לכל מנהל משמרת: שמו ושמות נהגי המשאית בצוות שלו
    public void printDriversByManager() {
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] instanceof Manager) {
                Manager m = (Manager) allEmployees[i];
                System.out.println("Manager: " + m.getName());
                Employee[] team = m.getTeam();
                for (int j = 0; j < m.getCurrent(); j++) {
                    if (team[j] instanceof TruckDriver) {
                        System.out.println("  " + team[j].getName());
                    }
                }
            }
        }
    }
}

C#:

public class LogisticsCenter {
    private Employee[] allEmployees;
    private int total;

    // 1. מספר נהגי המשאית שמורשים להוביל משקל weight או יותר
    public int HeavyDutyCheck(double weight) {
        int count = 0;
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] is TruckDriver) {
                TruckDriver t = (TruckDriver) allEmployees[i];
                if (t.GetMaxWeight() >= weight) count++;
            }
        }
        return count;
    }

    // 2. שם וסוג רישיון של כל נהג שאינו נהג משאית
    public void PrintAllDrivers() {
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] is Driver && !(allEmployees[i] is TruckDriver)) {
                Driver d = (Driver) allEmployees[i];
                Console.WriteLine(d.GetName() + " " + d.GetLicenseType());
            }
        }
    }

    // 3. לכל מנהל משמרת: שמו ושמות נהגי המשאית בצוות שלו
    public void PrintDriversByManager() {
        for (int i = 0; i < total; i++) {
            if (allEmployees[i] is Manager) {
                Manager m = (Manager) allEmployees[i];
                Console.WriteLine("Manager: " + m.GetName());
                Employee[] team = m.GetTeam();
                for (int j = 0; j < m.GetCurrent(); j++) {
                    if (team[j] is TruckDriver) {
                        Console.WriteLine("  " + team[j].GetName());
                    }
                }
            }
        }
    }
}

דוגמה: אם במרכז נהגי משאית Avi (maxWeight = 12) ו-Dana (30), נהג Moshe (רישיון C1), סדרנית ומנהל Yossi שבצוותו Avi, Moshe ו-Dana - אז `heavyDutyCheck(20)` מחזירה 1, `printAllDrivers` מדפיסה "Moshe C1", ו-`printDriversByManager` מדפיסה את Yossi ואחריו Avi ו-Dana.

תשובה: המחלקה LogisticsCenter עם שלוש הפעולות שלמעלה.

שאלה 6 · סינון רכיבים ומתח עבודה משותף

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

נתונה המחלקה Component:

Java:

public class Component {
  private double low;        // מתח מינימלי
  private double high;       // מתח מקסימלי
  private boolean isActive; // מצב: true - פעיל, false – כבוי
  public Component(double low, double high) {
       this.low = low; this.high = high; this.isActive = true;
  }
  public double getLow() { return this.low; }
  public double getHigh() { return this.high; }
  public boolean getIsActive() { return this.isActive; }
  public void setIsActive(boolean status) {
     this.isActive = status;
  }
}

C#:

public class Component {
  private double low;        // מתח מינימלי
  private double high;       // מתח מקסימלי
  private bool isActive; // מצב: true - פעיל, false – כבוי
  public Component(double low, double high) {
       this.low = low; this.high = high; this.isActive = true;
  }
  public double GetLow() { return this.low; }
  public double GetHigh() { return this.high; }
  public bool GetIsActive() { return this.isActive; }
  public void SetIsActive(bool status) {
     this.isActive = status;
  }
}
א.

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

Java:

public static boolean filterAndCheck (Node<Component> chain,
                                       double voltage)

C#:

public static bool FilterAndCheck (Node<Component> chain,
                                   double voltage)
(8 נקודות)
ב.

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

Java:

public static boolean hasCommonVoltage(Node<Component> chain)

C#:

public static bool HasCommonVoltage(Node<Component> chain)

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

רמז: כדי שמתח כזה יהיה קיים, הערך המינימלי (low) הגבוה ביותר מבין כל הרכיבים __צריך להיות קטן__ מהערך המקסימלי (high) הנמוך ביותר מבין כל הרכיבים.

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

סעיף א

תשובה:

הפעולה filterAndCheck שלהלן: לכל רכיב, אם voltage < low או voltage > high - setIsActive(false); אחר כך, אם הרכיב פעיל - found = true. מחזירה found.

הרעיון: המתח voltage נמצא בטווח התקין של רכיב אם low≤voltage≤highlow \le voltage \le high. לכן הוא מחוץ לטווח אם `voltage < low` או `voltage > high` - ואז מכבים את הרכיב. אחרי הטיפול ברכיב בודקים אם הוא עדיין פעיל; מספיק רכיב אחד כזה כדי להחזיר true.

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

1. `found = false`.

2. לכל רכיב `c` בשרשרת: אם `voltage < c.getLow() || voltage > c.getHigh()` - `c.setIsActive(false)`.

3. אם `c.getIsActive()` - `found = true`.

4. בסוף השרשרת מחזירים את `found`.

Java:

public static boolean filterAndCheck(Node<Component> chain, double voltage) {
    boolean found = false;
    Node<Component> p = chain;
    while (p != null) {
        Component c = p.getValue();
        if (voltage < c.getLow() || voltage > c.getHigh()) {
            c.setIsActive(false);       // המתח מחוץ לטווח - מכבים את הרכיב
        }
        if (c.getIsActive()) {
            found = true;               // רכיב זה נשאר פעיל
        }
        p = p.getNext();
    }
    return found;
}

C#:

public static bool FilterAndCheck(Node<Component> chain, double voltage) {
    bool found = false;
    Node<Component> p = chain;
    while (p != null) {
        Component c = p.GetValue();
        if (voltage < c.GetLow() || voltage > c.GetHigh()) {
            c.SetIsActive(false);       // המתח מחוץ לטווח - מכבים את הרכיב
        }
        if (c.GetIsActive()) {
            found = true;               // רכיב זה נשאר פעיל
        }
        p = p.GetNext();
    }
    return found;
}

דוגמה: שרשרת של שלושה רכיבים פעילים עם הטווחים [3, 5], [4, 12], [1, 3.3] ו-voltage = 4.5: הרכיב השלישי נכבה (4.5 > 3.3), שני הראשונים נשארים פעילים, והפעולה מחזירה true. אם אחר כך voltage = 20 - כל הרכיבים נכבים והפעולה מחזירה false.

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

סעיף ב

תשובה:

הפעולה hasCommonVoltage שלהלן: מחשבת על הרכיבים הפעילים בלבד maxLow (המקסימום של low) ו-minHigh (המינימום של high), ומחזירה maxLow <= minHigh.

הרעיון: מתח VV מתאים לכל הרכיבים הפעילים אם לכל רכיב פעיל lowi≤V≤highilow_i \le V \le high_i. כלומר VV צריך להיות גדול או שווה לכל ה-low וקטן או שווה לכל ה-high:

max⁡i(lowi)≤V≤min⁡i(highi)\max_i(low_i) \le V \le \min_i(high_i)

מתח כזה קיים בדיוק כאשר max⁡(low)≤min⁡(high)\max(low) \le \min(high) - חיתוך כל הטווחים אינו ריק (למשל V=max⁡(low)V=\max(low)). אם שני הערכים שווים, יש מתח יחיד שמתאים לכולם, ולכן ההשוואה כוללת שוויון (בהתאם לטווח התקין בסעיף א', שכולל את הקצוות). ברמז כתוב "קטן"; ההבדל בין `<` ל-`<=` הוא רק במקרה הגבולי שבו maxLow שווה ל-minHigh, ושתי התשובות מתקבלות.

1. `maxLow` מאותחל למינוס אינסוף ו-`minHigh` לפלוס אינסוף.

2. עוברים על השרשרת; לכל רכיב פעיל: מעדכנים `maxLow` אם `low` שלו גדול יותר, ו-`minHigh` אם `high` שלו קטן יותר. רכיבים כבויים אינם משתתפים בבדיקה.

3. מחזירים `maxLow <= minHigh`.

(אם אין אף רכיב פעיל, נשארים הערכים ההתחלתיים והפעולה מחזירה true: אין רכיב פעיל שאינו מתאים.)

Java:

public static boolean hasCommonVoltage(Node<Component> chain) {
    double maxLow = Double.NEGATIVE_INFINITY;   // הגבול התחתון הגבוה ביותר
    double minHigh = Double.POSITIVE_INFINITY;  // הגבול העליון הנמוך ביותר
    Node<Component> p = chain;
    while (p != null) {
        Component c = p.getValue();
        if (c.getIsActive()) {
            if (c.getLow() > maxLow) maxLow = c.getLow();
            if (c.getHigh() < minHigh) minHigh = c.getHigh();
        }
        p = p.getNext();
    }
    return maxLow <= minHigh;
}

C#:

public static bool HasCommonVoltage(Node<Component> chain) {
    double maxLow = double.NegativeInfinity;   // הגבול התחתון הגבוה ביותר
    double minHigh = double.PositiveInfinity;  // הגבול העליון הנמוך ביותר
    Node<Component> p = chain;
    while (p != null) {
        Component c = p.GetValue();
        if (c.GetIsActive()) {
            if (c.GetLow() > maxLow) maxLow = c.GetLow();
            if (c.GetHigh() < minHigh) minHigh = c.GetHigh();
        }
        p = p.GetNext();
    }
    return maxLow <= minHigh;
}

דוגמה: לרכיבים הפעילים [3, 5], [4, 12], [1, 3.3]: maxLow = 4, minHigh = 3.3, ו-4 > 3.3 - מוחזר false (אין מתח שמתאים גם לרכיב [1, 3.3] וגם לרכיב [4, 12]). אחרי filterAndCheck עם 4.5 נשארים פעילים רק [3, 5] ו-[4, 12]: maxLow = 4, minHigh = 5 - מוחזר true (כל מתח בין 4 ל-5 מתאים).

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

שאלה 7 · ערך זהב בתור של מחסניות

א.

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

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

Java:

public static boolean isLeastTwice(Stack<Integer> st, int val)

C#:

public static bool IsLeastTwice(Stack<int> st, int val)
(6 נקודות)
ב.

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

כתבו פעולה המקבלת תור מחסניות של מספרים שלמים que ומחזירה "ערך זהב". אם אין מספר כזה, הפעולה תחזיר ערך (-1).

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

Java:

public static int goldValue(Queue<Stack<Integer>> que)

C#:

public static int GoldValue(Queue<Stack<int>> que)

לדוגמה, עבור תור שלפניכם הפעולה תחזיר ערך 8.

(10 נקודות)
ג.

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

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

סעיף א

תשובה:

הפעולה isLeastTwice שלהלן: סופרת את המופעים של val בעזרת מחסנית עזר, משחזרת את st ומחזירה count >= 2.

הרעיון: שולפים את כל איברי המחסנית וסופרים כמה מהם שווים ל-val. כל איבר שנשלף נדחף למחסנית עזר `temp`, ובסוף מחזירים את כל האיברים מ-`temp` ל-st - היפוך כפול מחזיר את הסדר המקורי. שמירה על המחסנית חיונית, כי בסעיף ב' נבדוק אותה מחסנית שוב ושוב עם ערכים שונים.

1. `count = 0`.

2. כל עוד st אינה ריקה: שולפים `x`; אם `x == val` מגדילים את `count`; דוחפים את `x` ל-`temp`.

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

4. מחזירים `count >= 2`.

Java:

public static boolean isLeastTwice(Stack<Integer> st, int val) {
    Stack<Integer> temp = new Stack<Integer>();
    int count = 0;
    while (!st.isEmpty()) {
        int x = st.pop();
        if (x == val) count++;
        temp.push(x);
    }
    while (!temp.isEmpty()) {       // שחזור המחסנית
        st.push(temp.pop());
    }
    return count >= 2;
}

C#:

public static bool IsLeastTwice(Stack<int> st, int val) {
    Stack<int> temp = new Stack<int>();
    int count = 0;
    while (!st.IsEmpty()) {
        int x = st.Pop();
        if (x == val) count++;
        temp.Push(x);
    }
    while (!temp.IsEmpty()) {       // שחזור המחסנית
        st.Push(temp.Pop());
    }
    return count >= 2;
}

דוגמה: במחסנית 4, 8, 6, 3, 8, 6 (4 בראש): `isLeastTwice(st, 8)` ו-`isLeastTwice(st, 6)` מחזירות true, ו-`isLeastTwice(st, 4)` מחזירה false (4 מופיע פעם אחת).

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

סעיף ב

תשובה:

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

הרעיון: "ערך זהב" מופיע לפחות פעמיים בכל מחסנית - בפרט במחסנית הראשונה בתור. לכן מספיק לבדוק כמועמדים רק את הערכים של המחסנית הראשונה. לכל מועמד `v` נעבור על כל המחסניות בתור ונבדוק בעזרת `isLeastTwice(s, v)` מסעיף א'. המועמד הראשון שעובר את הבדיקה בכל המחסניות הוא ערך זהב, ומחזירים אותו. אם אף מועמד לא עבר - מחזירים -1.

פרטים חשובים:

•את ערכי המחסנית הראשונה מעתיקים קודם למחסנית מועמדים `cand` (ומשחזרים את המחסנית הראשונה), כי בזמן הבדיקה `isLeastTwice` צריכה לראות את המחסנית הראשונה שלמה.

•המעבר על התור נעשה בהוצאת המחסניות לתור עזר `tq` והחזרתן - כך התור חוזר לסדרו המקורי לפני כל `return`. גם אחרי שמחסנית אחת נכשלה, ממשיכים להעביר את שאר המחסניות כדי לשחזר את התור.

•`isLeastTwice` משחזרת כל מחסנית, ולכן כל המחסניות נשארות שלמות.

1. אם התור ריק - מחזירים -1.

2. מעתיקים את ערכי המחסנית שבראש התור (`que.head()`) ל-`cand`, בלי לשנות אותה.

3. לכל `v` מ-`cand`: מעבירים את כל המחסניות מ-`que` ל-`tq` ובודקים לכל אחת `isLeastTwice(s, v)`; מחזירים את המחסניות ל-`que`; אם `v` עבר בכולן - מחזירים `v`.

4. אם אף מועמד לא עבר - מחזירים -1.

Java:

public static int goldValue(Queue<Stack<Integer>> que) {
    if (que.isEmpty()) return -1;
    // מעתיקים את ערכי המחסנית הראשונה - הם המועמדים
    Stack<Integer> first = que.head();
    Stack<Integer> temp = new Stack<Integer>();
    Stack<Integer> cand = new Stack<Integer>();
    while (!first.isEmpty()) temp.push(first.pop());
    while (!temp.isEmpty()) {
        int x = temp.pop();
        first.push(x);
        cand.push(x);
    }
    while (!cand.isEmpty()) {
        int v = cand.pop();
        boolean inAll = true;
        Queue<Stack<Integer>> tq = new Queue<Stack<Integer>>();
        while (!que.isEmpty()) {            // בודקים את v בכל המחסניות
            Stack<Integer> s = que.remove();
            if (inAll && !isLeastTwice(s, v)) inAll = false;
            tq.insert(s);
        }
        while (!tq.isEmpty()) que.insert(tq.remove());   // שחזור התור
        if (inAll) return v;
    }
    return -1;
}

C#:

public static int GoldValue(Queue<Stack<int>> que) {
    if (que.IsEmpty()) return -1;
    // מעתיקים את ערכי המחסנית הראשונה - הם המועמדים
    Stack<int> first = que.Head();
    Stack<int> temp = new Stack<int>();
    Stack<int> cand = new Stack<int>();
    while (!first.IsEmpty()) temp.Push(first.Pop());
    while (!temp.IsEmpty()) {
        int x = temp.Pop();
        first.Push(x);
        cand.Push(x);
    }
    while (!cand.IsEmpty()) {
        int v = cand.Pop();
        bool inAll = true;
        Queue<Stack<int>> tq = new Queue<Stack<int>>();
        while (!que.IsEmpty()) {            // בודקים את v בכל המחסניות
            Stack<int> s = que.Remove();
            if (inAll && !IsLeastTwice(s, v)) inAll = false;
            tq.Insert(s);
        }
        while (!tq.IsEmpty()) que.Insert(tq.Remove());   // שחזור התור
        if (inAll) return v;
    }
    return -1;
}

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

מועמדמחסנית 1מחסנית 2מחסנית 3מחסנית 4מחסנית 5מחסנית 6ערך זהב?
41 מופע ✗לא
8222422כן

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

תשובה: הפעולה goldValue שלמעלה; בדוגמה מוחזר 8.

סעיף ג

תשובה:

סעיף א': O(n)O(n) (n - גודל המחסנית); סעיף ב': O(m⋅N)O(m \cdot N), כאשר m גודל המחסנית הראשונה ו-N מספר האיברים בכל המחסניות יחד (במקרה הגרוע O(N2)O(N^2)).

פעולות המחסנית והתור הן O(1)O(1).

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

2. goldValue: נסמן ב-mm את מספר האיברים במחסנית הראשונה, ב-kk את מספר המחסניות וב-NN את מספר האיברים בכל המחסניות יחד.

•העתקת המחסנית הראשונה: O(m)O(m).

•לכל אחד מ-mm המועמדים: קריאה ל-`isLeastTwice` על כל מחסנית, שעולה בסך הכול O(N)O(N), ועוד O(k)O(k) להעברת המחסניות בתור וחזרה. מכיוון ש-k≤Nk \le N (כל מחסנית מכילה לפחות איבר אחד), זה O(N)O(N) לכל מועמד.

•בסך הכול: O(m⋅N)O(m \cdot N). מכיוון ש-m≤Nm \le N, במקרה הגרוע זה O(N2)O(N^2).

תשובה: סעיף א' - O(n)O(n); סעיף ב' - O(m⋅N)O(m \cdot N), כלומר לכל היותר O(N2)O(N^2).

שאלה 8 · עץ משלים: הגדרה, בדיקה ועץ חיפוש

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

•עבור כל צומת שיש לו שני בנים, ערך הצומת שווה לסכום הערכים של שני בניו;

•עבור כל צומת שיש לו בן יחיד, ערך הצומת שווה לערכו של הבן היחיד;

•הערכים בכל עלי העץ (צמתים ללא בנים) חייבים להיות מספרים חיוביים (גדולים מ-0).

א.

ציירו "עץ משלים" הכולל לפחות שישה צמתים, שבו לפחות לאחד הצמתים יש בן יחיד.

(3 נקודות)
ב.

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

Java:

public static boolean isComplementary(BinNode<Integer> bt)

C#:

public static bool IsComplementary(BinNode<int> bt)
(12 נקודות)
ג.

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

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

סעיף א

תשובה:

שורש 12; בנו השמאלי 7 עם הבנים 3 ו-4; בנו הימני 5 עם בן יחיד (שמאלי) 5.

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

1. עלים: 3, 4, 5 (כולם חיוביים).

2. צומת עם שני הבנים 3 ו-4: ערכו 3+4=73+4=7.

3. צומת עם בן יחיד שערכו 5: ערכו 5.

4. השורש, עם הבנים 7 (שמאלי) ו-5 (ימני): ערכו 7+5=127+5=12.

העץ שמשרטטים (6 צמתים):

•שורש 12

•בן שמאלי 7

•בן שמאלי 3 (עלה)

•בן ימני 4 (עלה)

•בן ימני 5 (בן יחיד שמאלי)

•בן שמאלי 5 (עלה)

בדיקה: 12=7+512=7+5, 7=3+47=3+4, הצומת 5 שווה לבנו היחיד 5, והעלים 3, 4, 5 חיוביים. לצומת 5 העליון יש בן יחיד, כנדרש.

תשובה: העץ שלמעלה.

סעיף ב

תשובה:

הפעולה הרקורסיבית isComplementary שלהלן: עלה - ערך חיובי; שני בנים - ערך = סכום הבנים ושני תתי-העצים משלימים; בן יחיד - ערך = ערך הבן ותת-העץ שלו משלים.

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

1. עץ ריק (`bt == null`): אין צומת שמפר את הכללים - מחזירים true (זה גם מקרה הבסיס).

2. עלה (אין בנים): מחזירים `bt.getValue() > 0`.

3. שני בנים: אם ערך הצומת שונה מסכום ערכי שני הבנים - false; אחרת בודקים ברקורסיה את שני תתי-העצים.

4. בן יחיד: מוצאים את הבן (שמאלי או ימני). אם ערך הצומת שונה מערכו - false; אחרת בודקים ברקורסיה את תת-העץ שלו.

(ב-Java ערכי הצמתים הם מטיפוס Integer; כדי להשוות ערכים ולא הפניות, משווים אחרי העברה למשתני int.)

Java:

public static boolean isComplementary(BinNode<Integer> bt) {
    if (bt == null) return true;
    if (!bt.hasLeft() && !bt.hasRight()) {          // עלה
        return bt.getValue() > 0;
    }
    if (bt.hasLeft() && bt.hasRight()) {            // שני בנים
        if (bt.getValue() != bt.getLeft().getValue() + bt.getRight().getValue())
            return false;
        return isComplementary(bt.getLeft()) && isComplementary(bt.getRight());
    }
    BinNode<Integer> child;                         // בן יחיד
    if (bt.hasLeft()) child = bt.getLeft();
    else child = bt.getRight();
    int v = bt.getValue();
    int c = child.getValue();
    if (v != c) return false;
    return isComplementary(child);
}

C#:

public static bool IsComplementary(BinNode<int> bt) {
    if (bt == null) return true;
    if (!bt.HasLeft() && !bt.HasRight()) {          // עלה
        return bt.GetValue() > 0;
    }
    if (bt.HasLeft() && bt.HasRight()) {            // שני בנים
        if (bt.GetValue() != bt.GetLeft().GetValue() + bt.GetRight().GetValue())
            return false;
        return IsComplementary(bt.GetLeft()) && IsComplementary(bt.GetRight());
    }
    BinNode<int> child;                         // בן יחיד
    if (bt.HasLeft()) child = bt.GetLeft();
    else child = bt.GetRight();
    int v = bt.GetValue();
    int c = child.GetValue();
    if (v != c) return false;
    return IsComplementary(child);
}

בדיקה: על העץ מסעיף א' הפעולה מחזירה true. אם נשנה את העלה 4 ל-5, הצומת 7 כבר אינו שווה ל-3+5=83+5=8 - מוחזר false. עלה שערכו 0 - false.

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

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

סעיף ג

תשובה:

לא קיים: צומת עם שני בנים מחייב R < L + R = v < R (סתירה), וצומת עם בן יחיד מחייב ערך שווה לבנו - אסור ב-BST; לכן רק עץ של צומת אחד יכול להיות גם BST וגם עץ משלים.

טענה: עץ כזה לא קיים. נבדוק כל סוג של צומת פנימי:

1. כל הערכים בעץ משלים חיוביים. העלים חיוביים לפי ההגדרה, וכל צומת פנימי שווה לסכום של ערכים חיוביים או לערך חיובי של בנו - ולכן גם הוא חיובי (מלמטה למעלה).

2. צומת עם שני בנים - ערכו vv, הבן השמאלי LL והבן הימני RR. בעץ משלים v=L+Rv=L+R, ומכיוון ש-L>0L>0 מתקבל v>Rv>R. אבל ב-BST הבן הימני גדול מהצומת: R>vR>v. סתירה - בעץ כזה אין צומת עם שני בנים.

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

4. לכן בעץ שהוא גם BST וגם עץ משלים אין צמתים פנימיים בכלל - הוא כולל צומת אחד בלבד (עלה חיובי). עץ עם ארבעה צמתים או יותר חייב לכלול צומת פנימי, ולכן אינו יכול לקיים את שתי ההגדרות.

(הערה: אם מגדירים BST שמאפשר ערכים שווים בתת-העץ הימני, השרשרת 5 → 5 → 5 → 5 של בנים ימניים יחידים הייתה מקיימת את שני התנאים. בהגדרה הרגילה של עץ חיפוש בינרי - ערכים שונים, שמאל קטן וימין גדול - עץ כזה לא קיים.)

תשובה: לא קיים עץ כזה.

שאלה 9 · מעקב אחר היררכיית מכשירים ניידים

לפניכם ארבע מחלקות המייצגות היררכיה של מכשירים ניידים והמחלקה Test

Java:

class MobileDevice {
    protected int id;
    protected boolean isOn = true;
    protected static int count = 0;

    public MobileDevice () {
        count++;
        this.id = count;
        System.out.print("D" + id + " ");
    }

    public boolean getIsOn(){ return this.isOn; }
    public void togglePower(){ this.isOn = !this.isOn; }

    public String getStatus() {
        if(isOn)return "ID"+id+" [ON]";
        return "ID" + id + " [OFF]";
    }
}// end of MobileDevice

class Phone extends MobileDevice {
    protected boolean isSilent = true;

    public Phone() {  System.out.print("P "); }

    public void setStatus(boolean isOn, boolean isSilent) {
        this.isOn = isOn;
        this.isSilent = isSilent;
    }
    public String getStatus() {
        if(isSilent)return super.getStatus()+" SILENT";
        return super.getStatus() + " RING";
    }
}// end of Phone

class SmartPhone extends Phone {
    public SmartPhone() { System.out.print("S ");}

    public String getStatus() {
        return super.getStatus()+" WiFi" ;
    }
}// end of SmartPhone

class Laptop extends MobileDevice {
    public Laptop() { System.out.print("L ");}
}// end of Laptop

public class Test {
    public static void main(String[] args) {
        MobileDevice[] net = new MobileDevice[5];

        System.out.println("--- Step 1: Creation ---");
        net[0] = new SmartPhone();
        System.out.println();
        net[1] = new Laptop();
        System.out.println();
        net[2] = net[0];
        net[3] = new Phone();
        System.out.println();
        net[4] = new MobileDevice();
        System.out.println();

        System.out.println("--- Step 2: Action ---");
        for (int i = 0; i < net.length; i++) {
            if (net[i] instanceof Phone) {
                ((Phone)net[i]).setStatus(true, false);
            } else {
                net[i].togglePower();
            }
        }

        System.out.println("--- Step 3: Final Status ---");
        for (int i = 0; i < net.length; i++)  {
            if (net[i] != null) {
                System.out.println(net[i].getStatus());
            }
        }
    }
}

C#:

class MobileDevice {
    protected int id;
    protected bool isOn = true;
    protected static int count = 0;

    public MobileDevice () {
        count++;
        this.id = count;
        Console.Write("D" + id + " ");
    }

    public bool GetIsOn(){ return this.isOn; }
    public void TogglePower(){ this.isOn = !this.isOn; }

    public virtual string GetStatus() {
        if(isOn)return "ID"+id+" [ON]";
        return "ID" + id + " [OFF]";
    }
}// end of MobileDevice

class Phone : MobileDevice {
    protected bool isSilent = true;

    public Phone() {  Console.Write("P "); }

    public void SetStatus(bool isOn, bool isSilent) {
        this.isOn = isOn;
        this.isSilent = isSilent;
    }
    public override string GetStatus() {
        if(isSilent)return base.GetStatus()+" SILENT";
        return base.GetStatus() + " RING";
    }
}// end of Phone

class SmartPhone : Phone {
    public SmartPhone() { Console.Write("S ");}

    public override string GetStatus() {
        return base.GetStatus()+" WiFi" ;
    }
}// end of SmartPhone

class Laptop : MobileDevice {
    public Laptop() { Console.Write("L ");}
}// end of Laptop

public class Test {
    public static void Main(string[] args) {
        MobileDevice[] net = new MobileDevice[5];

        Console.WriteLine("--- Step 1: Creation ---");
        net[0] = new SmartPhone();
        Console.WriteLine();
        net[1] = new Laptop();
        Console.WriteLine();
        net[2] = net[0];
        net[3] = new Phone();
        Console.WriteLine();
        net[4] = new MobileDevice();
        Console.WriteLine();

        Console.WriteLine("--- Step 2: Action ---");
        for (int i = 0; i < net.Length; i++) {
            if (net[i] is Phone) {
                ((Phone)net[i]).SetStatus(true, false);
            } else {
                net[i].TogglePower();
            }
        }

        Console.WriteLine("--- Step 3: Final Status ---");
        for (int i = 0; i < net.Length; i++)  {
            if (net[i] != null) {
                Console.WriteLine(net[i].GetStatus());
            }
        }
    }
}
א.

עקבו אחרי ביצוע קוד ב-main (ב-C#: Main) ורשמו מה יהיה הפלט.

(10 נקודות)
ב.

מנהלי הפרויקט החליטו להוסיף מעקב אחר רמת הסוללה של המכשירים. רמת הסוללה מיוצגת במספר שלם (int) בין 0 ל-100.

רוצים להוסיף תכונה בשם batteryLevel ופעולות getBatteryLevel ו-setBatteryLevel (ב-C#: GetBatteryLevel ו-SetBatteryLevel).

(1)

באיזו מחלקה / מחלקות הכי נכון להגדיר את התכונה ואת הפעולות? נמקו את בחירתכם.

(2)

כתבו פעולה חיצונית (סטטית) בשם checkCritical (ב-C#: CheckCritical). הפעולה תקבל מערך של מכשירים ניידים ותדפיס את ה-ID של כל המחשבים הניידים (Laptop) במערך שהם במצב מופעל ([ON]) ושרמת הסוללה שלהם נמוכה מ-10 (כלומר במצב קריטי).

הערה: הניחו כי הפעולה `getBatteryLevel()` (ב-C#: `GetBatteryLevel()`) כבר קיימת כראוי במחלקות הרלוונטיות.

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

סעיף א

תשובה:

--- Step 1: Creation --- / D1 P S / D2 L / D3 P / D4 / --- Step 2: Action --- / --- Step 3: Final Status --- / ID1 [ON] RING WiFi / ID2 [OFF] / ID1 [ON] RING WiFi / ID3 [ON] RING / ID4 [OFF]

כללים שמשמשים במעקב:

•יצירת עצם של תת-מחלקה מפעילה קודם את הבנאי של מחלקת העל (ושל מחלקת העל שלה), ורק אחר כך את הבנאי של המחלקה עצמה. לכן SmartPhone מדפיס קודם את ההדפסה של MobileDevice, אחריה של Phone, ובסוף של SmartPhone.

•`count` הוא `static` - מונה אחד משותף לכל המכשירים, ולכן המכשירים מקבלים את המספרים 1, 2, 3, 4 לפי סדר היצירה.

•`net[2] = net[0]` אינה יוצרת עצם חדש: שני התאים מצביעים על אותו SmartPhone.

•`getStatus` נקראת לפי הטיפוס האמיתי של העצם (פולימורפיזם), ו-`super.getStatus()` (ב-C#: `base.GetStatus()`) מוסיפה את התוצאה של מחלקת העל.

שלב 1 - יצירה:

הוראהcount אחריidהדפסה
net[0] = new SmartPhone()11`D1 P S ` ואז ירידת שורה
net[1] = new Laptop()22`D2 L ` ואז ירידת שורה
net[2] = net[0]2-(אין הדפסה; אותו עצם כמו net[0])
net[3] = new Phone()33`D3 P ` ואז ירידת שורה
net[4] = new MobileDevice()44`D4 ` ואז ירידת שורה

שלב 2 - פעולה (בהתחלה לכל המכשירים isOn = true, ולטלפונים isSilent = true):

תא iהעצםPhone?פעולהמצב אחרי
0SmartPhone (id 1)כןsetStatus(true, false)isOn = true, isSilent = false
1Laptop (id 2)לאtogglePowerisOn = false
2SmartPhone (id 1) - אותו עצםכןsetStatus(true, false)ללא שינוי: isOn = true, isSilent = false
3Phone (id 3)כןsetStatus(true, false)isOn = true, isSilent = false
4MobileDevice (id 4)לאtogglePowerisOn = false

(SmartPhone הוא Phone, ולכן הבדיקה `instanceof Phone` / `is Phone` מחזירה עבורו true.) בשלב זה אין הדפסה מלבד הכותרת.

שלב 3 - מצב סופי:

תא iחישוב getStatusתוצאה
0SmartPhone: Phone.getStatus + " WiFi"; Phone: לא שקט, ולכן MobileDevice.getStatus + " RING"; MobileDevice: דולקID1 [ON] RING WiFi
1Laptop לא דורסת את getStatus - הגרסה של MobileDevice; כבויID2 [OFF]
2אותו עצם כמו i = 0ID1 [ON] RING WiFi
3Phone: לא שקט, דולקID3 [ON] RING
4MobileDevice כבויID4 [OFF]

הפלט (בשורות של שלב 1 יש רווח בסוף השורה):

--- Step 1: Creation ---
D1 P S 
D2 L 
D3 P 
D4 
--- Step 2: Action ---
--- Step 3: Final Status ---
ID1 [ON] RING WiFi
ID2 [OFF]
ID1 [ON] RING WiFi
ID3 [ON] RING
ID4 [OFF]

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

סעיף ב

(1)
תשובה:

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

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

2. MobileDevice היא מחלקת העל של כל ההיררכיה. תכונה ופעולות שמוגדרות בה עוברות בירושה ל-Phone, SmartPhone ו-Laptop.

3. כך הקוד נכתב פעם אחת (בלי שכפול בכל מחלקה), וכל הפניה מטיפוס MobileDevice - כמו איברי המערך net - יכולה לקרוא ל-`getBatteryLevel()` בלי המרה.

4. התכונה תהיה `protected` (כמו שאר התכונות במחלקה) או `private`, והפעולות `public`. הפעולה `setBatteryLevel` תקבל רק ערך בין 0 ל-100, כדי לשמור על תקינות הנתון.

הגדרה אפשרית (התוספות בלבד; גם פעולה getId, כי id מוגדר protected ופעולה חיצונית צריכה אותו בסעיף 2):

Java:

class MobileDevice {
    protected int id;
    protected boolean isOn = true;
    protected static int count = 0;
    protected int batteryLevel = 100;          // תכונה חדשה: רמת הסוללה (0-100)
    // ... הבנאי והפעולות הקיימות ללא שינוי ...

    public int getId() { return this.id; }     // לשימוש פעולות חיצוניות

    public int getBatteryLevel() { return this.batteryLevel; }

    public void setBatteryLevel(int level) {
        if (level >= 0 && level <= 100) {       // רק ערך חוקי בין 0 ל-100
            this.batteryLevel = level;
        }
    }
}

C#:

class MobileDevice {
    protected int id;
    protected bool isOn = true;
    protected static int count = 0;
    protected int batteryLevel = 100;          // תכונה חדשה: רמת הסוללה (0-100)
    // ... הבנאי והפעולות הקיימות ללא שינוי ...

    public int GetId() { return this.id; }     // לשימוש פעולות חיצוניות

    public int GetBatteryLevel() { return this.batteryLevel; }

    public void SetBatteryLevel(int level) {
        if (level >= 0 && level <= 100) {       // רק ערך חוקי בין 0 ל-100
            this.batteryLevel = level;
        }
    }
}

תשובה: במחלקה MobileDevice.

(2)
תשובה:

הפעולה checkCritical שלהלן: לכל איבר d - אם d instanceof Laptop (ב-C#: is Laptop), d.getIsOn() ו-d.getBatteryLevel() < 10 - מדפיסה "ID" + d.getId().

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

1. הוא מחשב נייד - `instanceof Laptop` (ב-C#: `is Laptop`). הבדיקה מחזירה false גם עבור תא ריק (null), ולכן אין סכנה לקריאה על null.

2. הוא מופעל - `getIsOn()` מחזירה true.

3. רמת הסוללה שלו קריטית - `getBatteryLevel() < 10`.

הפעולות `getIsOn` ו-`getBatteryLevel` מוגדרות ב-MobileDevice (לפי סעיף 1), ולכן אפשר לקרוא להן דרך הפניה מטיפוס MobileDevice, בלי המרה ל-Laptop. את ה-ID מקבלים בפעולה `getId()` שהוספנו (התכונה id היא protected), ומדפיסים אותו באותה צורה כמו ב-getStatus: "ID" ואחריו המספר. (ב-C# נשתמש בשם GetBatteryLevel, כמו בהגדרת הפעולה בסעיף.)

Java:

public static void checkCritical(MobileDevice[] devices) {
    for (int i = 0; i < devices.length; i++) {
        MobileDevice d = devices[i];
        if (d instanceof Laptop && d.getIsOn() && d.getBatteryLevel() < 10) {
            System.out.println("ID" + d.getId());
        }
    }
}

C#:

public static void CheckCritical(MobileDevice[] devices) {
    for (int i = 0; i < devices.Length; i++) {
        MobileDevice d = devices[i];
        if (d is Laptop && d.GetIsOn() && d.GetBatteryLevel() < 10) {
            Console.WriteLine("ID" + d.GetId());
        }
    }
}

דוגמה: במערך של חמישה מחשבים ניידים עם id 1-5, שבו לראשון סוללה 5, לשני 9 אבל הוא כבוי, לשלישי 10, לרביעי 60 ולחמישי 0 (כולם מופעלים מלבד השני) - יודפסו ID1 ו-ID5 (השני כבוי, ו-10 ו-60 אינם נמוכים מ-10).

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

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

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

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