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

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

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

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

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

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

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

מבחן ב- Java (עמוד 2)

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

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

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

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

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

שאלות 8-5: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.

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

שאלות 10-9: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.

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

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

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

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

שאלה 1 · מספרים זרים וסידור מחדש של תור

א.

שני מספרים שלמים וחיוביים `num1` ו- `num2` נקראים "זרים זה לזה" אם אין להם אף מחלק משותף פרט ל- 1.

לדוגמה:

המספרים 8 ו- 9 הם זרים, 10 ו- 21 הם זרים.

המספרים 14 ו- 21 הם לא זרים כי יש להם מחלק משותף 7.

המספרים 6 ו- 12 הם לא זרים כי יש להם מחלקים משותפים 2, 3, 6.

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

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

Java:

public static boolean strangers(int num1, int num2)

C#:

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

כתבו פעולה `change` המקבלת תור `q` ומספר `num`. הפעולה משנה את סדר האיברים בתור כך שכל המספרים ה"זרים" ל- `num` יהיו בתחילת התור וכל האיברים אשר "לא זרים" ל- `num`, יהיו אחריהם.

לדוגמא:

עבור התור `q` הבא:

⬅210123741⬅

והמספר `num=9`

התור שיתקבל יכול להיות:

⬅210741312⬅

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

Java:

public static void change(Queue<Integer> q, int num)

C#:

public static void Change(Queue<int> q, int num)
(6 נקודות)
ג.

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

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

סעיף א

תשובה:

עוברים על כל המחלקים האפשריים dd מ-2 עד min⁡(num1,num2)\min(num1,num2); אם dd מחלק את שני המספרים מחזירים `false`, ואם לא נמצא מחלק כזה מחזירים `true`.

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

1. מחשבים את `min`, הקטן מבין שני המספרים.

2. עוברים בלולאה על dd מ-2 עד `min`. אם dd מחלק את שני המספרים (`num1 % d == 0` וגם `num2 % d == 0`) מצאנו מחלק משותף גדול מ-1, והמספרים אינם זרים: מחזירים `false` מיד.

3. אם הלולאה הסתיימה בלי למצוא מחלק כזה, המחלק המשותף היחיד הוא 1, ומחזירים `true`.

בדיקה מול הדוגמאות: עבור 8 ו-9 בודקים d=2,…,8d=2,\dots,8 ואף אחד מהם אינו מחלק את שניהם, לכן `true`. עבור 14 ו-21: d=7d=7 מחלק את שניהם, לכן `false`. עבור 6 ו-12: כבר d=2d=2 מחלק את שניהם, לכן `false`.

Java:

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

C#:

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

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

סעיף ב

תשובה:

מרוקנים את `q` לשני תורי עזר: הזרים ל-`num` (לפי `strangers` מסעיף א') והלא זרים; אחר כך מחזירים ל-`q` קודם את כל תור הזרים ואחריו את תור הלא זרים.

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

(בציור ראש התור הוא האיבר השמאלי: החץ השמאלי מסמן את היציאה מהתור, והחץ הימני את הכניסה לסופו.)

1. יוצרים שני תורים ריקים: `strange` עבור המספרים הזרים ל-`num`, ו-`notStrange` עבור השאר.

2. כל עוד `q` לא ריק: מוציאים את האיבר שבראשו, `x`, ומזמנים `strangers(x, num)`. אם התשובה `true` מכניסים את `x` ל-`strange`, אחרת ל-`notStrange`. בסוף השלב `q` ריק.

3. מעבירים את כל `strange` אל `q`, ואחריו את כל `notStrange`. כך כל הזרים בתחילת התור וכל הלא זרים אחריהם (וגם הסדר היחסי בתוך כל קבוצה נשמר).

מעקב על הדוגמה (num=9num=9): הזרים ל-9 הם 2, 10, 7, 4, 1 (אין להם מחלק 3), והלא זרים הם 12 ו-3 (מתחלקים ב-3). התור שיתקבל: 2, 10, 7, 4, 1, 12, 3. השאלה מציינת שהתור "יכול להיות" 2, 10, 7, 4, 1, 3, 12 – גם הסדר שלנו מקיים את הדרישה, כי הדרישה היא רק שכל הזרים יופיעו לפני כל הלא זרים.

Java:

public static void change(Queue<Integer> q, int num)
{
    Queue<Integer> strange = new Queue<Integer>();     // הזרים ל-num
    Queue<Integer> notStrange = new Queue<Integer>();  // הלא זרים ל-num
    while (!q.isEmpty())
    {
        int x = q.remove();
        if (strangers(x, num))
            strange.insert(x);
        else
            notStrange.insert(x);
    }
    while (!strange.isEmpty())
        q.insert(strange.remove());
    while (!notStrange.isEmpty())
        q.insert(notStrange.remove());
}

C#:

public static void Change(Queue<int> q, int num)
{
    Queue<int> strange = new Queue<int>();     // הזרים ל-num
    Queue<int> notStrange = new Queue<int>();  // הלא זרים ל-num
    while (!q.IsEmpty())
    {
        int x = q.Remove();
        if (Strangers(x, num))
            strange.Insert(x);
        else
            notStrange.Insert(x);
    }
    while (!strange.IsEmpty())
        q.Insert(strange.Remove());
    while (!notStrange.IsEmpty())
        q.Insert(notStrange.Remove());
}

תשובה: הפעולה שלמעלה; עבור הדוגמה מתקבל התור 2, 10, 7, 4, 1, 12, 3.

סעיף ג

תשובה:

סעיף א': O(min⁡(num1,num2))O(\min(num1,num2)). סעיף ב': O(n⋅num)O(n\cdot num), כאשר nn מספר האיברים בתור (אם מתייחסים לבדיקת זרות כפעולה בגודל חסום – O(n)O(n)).

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

סעיף ב': נסמן ב-nn את מספר האיברים בתור.

1. בלולאה הראשונה כל איבר מוצא מ-`q` פעם אחת, ולכל איבר `x` מזמנים את `strangers(x, num)`, שעולה O(min⁡(x,num))≤O(num)O(\min(x,num))\le O(num).

2. בשתי הלולאות האחרונות כל איבר מועבר פעם אחת בחזרה ל-`q`: עוד O(n)O(n).

בסך הכול: O(n⋅num)+O(n)=O(n⋅num)O(n\cdot num)+O(n)=O(n\cdot num). אם רואים בבדיקת הזרות פעולה שזמנה חסום (המספרים בגודל חסום), הפעולה לינארית: O(n)O(n).

תשובה: א' – O(min⁡(num1,num2))O(\min(num1,num2)); ב' – O(n⋅num)O(n\cdot num) (לינארית במספר איברי התור).

שאלה 2 · פיצול שרשרת חוליות לפי זוגיות

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

הפעולה תפצל את השרשרת לשניים לפי הכלל הבא:

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

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

הפעולה תחזיר הפניה לחוליה הראשונה של השרשרת החדשה.

לדוגמה:

א.

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

Java:

public static Node<Integer> split(Node<Integer> chain)

C#:

public static Node<int> Split(Node<int> chain)
(12 נקודות)
ב.

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

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

סעיף א

תשובה:

שומרים את זוגיות הערך הראשון ועוברים על השרשרת עם `prev` ו-`cur`; כל חוליה שזוגיותה שונה מנותקת מהשרשרת המקורית (`prev.setNext(cur.getNext())`) ומחוברת לסוף השרשרת החדשה. מחזירים את ראש השרשרת החדשה (או `null`).

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

1. אם השרשרת ריקה – אין מה לפצל, מחזירים `null`.

2. שומרים במשתנה `firstEven` אם הערך הראשון זוגי. (הבדיקה `x % 2 == 0` נכונה גם למספרים שליליים.)

3. מחזיקים שתי הפניות: `prev` – החוליה האחרונה שנשארה בשרשרת המקורית, ו-`cur` – החוליה שבודקים. בהתחלה `prev = chain` ו-`cur` היא החוליה השנייה.

4. לשרשרת החדשה מחזיקים ראש `newHead` וסוף `newTail`, כדי להוסיף חוליות לסופה ולשמור על הסדר המקורי.

5. אם הזוגיות של `cur` שונה מ-`firstEven`:

•מדלגים עליה בשרשרת המקורית: `prev.setNext(cur.getNext())`;

•מנתקים אותה (`cur.setNext(null)`) ומחברים לסוף השרשרת החדשה;

•ממשיכים ל-`prev.getNext()`; את `prev` לא מקדמים, כי החוליה שאחריו השתנתה.

6. אחרת החוליה נשארת: מקדמים גם את `prev` וגם את `cur`.

7. בסוף מחזירים את `newHead` (אם לא הועברה אף חוליה – `null`).

מעקב על הדוגמה: הערך הראשון 10 זוגי, ולכן מעבירים את האי-זוגיים. עוברים על 20 (נשאר), 5 (עובר), 7 (עובר), 8, 4, 6 (נשארים), 11 (עובר), 7 (עובר). מתקבל: `chain` → 10 → 20 → 8 → 4 → 6, ו-`newChain` → 5 → 7 → 11 → 7, כמו בדוגמה.

Java:

public static Node<Integer> split(Node<Integer> chain)
{
    if (chain == null)
        return null;
    boolean firstEven = chain.getValue() % 2 == 0;  // זוגיות הערך הראשון
    Node<Integer> newHead = null;   // ראש השרשרת החדשה
    Node<Integer> newTail = null;   // סוף השרשרת החדשה
    Node<Integer> prev = chain;     // החוליה הראשונה תמיד נשארת
    Node<Integer> cur = chain.getNext();
    while (cur != null)
    {
        boolean curEven = cur.getValue() % 2 == 0;
        if (curEven != firstEven)
        {
            // מנתקים את cur מהשרשרת המקורית
            prev.setNext(cur.getNext());
            cur.setNext(null);
            // ומחברים אותו לסוף השרשרת החדשה
            if (newHead == null)
                newHead = cur;
            else
                newTail.setNext(cur);
            newTail = cur;
            cur = prev.getNext();
        }
        else
        {
            prev = cur;
            cur = cur.getNext();
        }
    }
    return newHead;
}

C#:

public static Node<int> Split(Node<int> chain)
{
    if (chain == null)
        return null;
    bool firstEven = chain.GetValue() % 2 == 0;  // זוגיות הערך הראשון
    Node<int> newHead = null;   // ראש השרשרת החדשה
    Node<int> newTail = null;   // סוף השרשרת החדשה
    Node<int> prev = chain;     // החוליה הראשונה תמיד נשארת
    Node<int> cur = chain.GetNext();
    while (cur != null)
    {
        bool curEven = cur.GetValue() % 2 == 0;
        if (curEven != firstEven)
        {
            // מנתקים את cur מהשרשרת המקורית
            prev.SetNext(cur.GetNext());
            cur.SetNext(null);
            // ומחברים אותו לסוף השרשרת החדשה
            if (newHead == null)
                newHead = cur;
            else
                newTail.SetNext(cur);
            newTail = cur;
            cur = prev.GetNext();
        }
        else
        {
            prev = cur;
            cur = cur.GetNext();
        }
    }
    return newHead;
}

תשובה: הפעולה `split` שלמעלה; עבור הדוגמה השרשרת המקורית נעשית 10, 20, 8, 4, 6 והשרשרת המוחזרת היא 5, 7, 11, 7.

סעיף ב

תשובה:

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

נסמן ב-nn את מספר החוליות בשרשרת.

1. הלולאה עוברת על כל חוליה פעם אחת בדיוק: בכל סיבוב `cur` מתקדם לחוליה הבאה (גם כשהחוליה מועברת, `cur` עובר ל-`prev.getNext()`, שהיא החוליה הבאה שטרם נבדקה).

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

לכן הסיבוכיות היא n⋅O(1)=O(n)n\cdot O(1)=O(n). הפעולה אינה יוצרת חוליות חדשות, ולכן הזיכרון הנוסף הוא O(1)O(1).

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

שאלה 3 · פעולות בונות, ירושה והמרות טיפוסים

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

Java:

public class First
{
  protected int num;
  ….
}
public class Second extends First
{
    private double x;
    private First f;
  …
}
public class Test
{
public static void main(String[] args)
{
     First[] arr = new First[5];
     arr[0] = new First (13);
     arr[1] = new First ();
     arr[2] = new Second();
     arr[3] = new Second(5, arr[0]);
     arr[4] = new Second(2, 3.7, arr[2]);
}
}

C#:

public class First
{
  protected int num;
  ….
}
public class Second : First
{
    private double x;
    private First f;
  …
}
public class Test
{
public static void Main(string[] args)
{
     First[] arr = new First[5];
     arr[0] = new First (13);
     arr[1] = new First ();
     arr[2] = new Second();
     arr[3] = new Second(5, arr[0]);
     arr[4] = new Second(2, 3.7, arr[2]);
}
}

הרצת הפעולה יצרה את העצמים הבאים:

א.

כתבו במחלקות `First` ו- `Second` את הפעולות הבונות (constructors) הנדרשות לשם הרצת הפעולה הראשית כך שיתקבלו העצמים המתוארים.

(8 נקודות)

נתון עץ הירושה הבא:

ב.

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

Shape s1 = new Shape();
Shape s2 = new Circle();
Shape s3 = new Cylinder();
Circle c = new Cylinder();

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

אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (שגיאת קומפילציה/הידור או שגיאת זמן ריצה).

(1)
Circle c0 = new Shape();
(2)
Circle c1 = s1;
(3)
Circle c2 = (Circle)s2;
(4)
Circle c3 = (Circle)s3;
(5)
Circle c4 = (Circle) s1;
(6)
Triangle t = new Triangle();
Shape s5 = t;
Circle c5 = (Circle)s5;
(7)
Shape s = (Circle)(new Cylinder());
(8)
Circle c = (Shape)(new Cylinder());
(8 נקודות)
◂ פתרון מלא לשאלה 3

סעיף א

תשובה:

ב-`First`: בונה ריקה (`num=10`) ובונה עם `num`. ב-`Second`: בונה ריקה (`num=10, x=1.1, f=null`); בונה `(int num, First other)` – `num`, `x=num+0.5`, `f` עותק חדש של `other`; בונה `(int a, double b, First f)` – `num=(int)(a+b)=5`, `x=num+0.5=5.5`, `f` מפנה לעצם שהתקבל.

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

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

זימוןבונה נדרשתמה צריך להתקבל
`new First(13)``First(int)``num = 13`
`new First()``First()``num = 10`
`new Second()``Second()``num = 10`, `x = 1.1`, `f = null`
`new Second(5, arr[0])``Second(int, First)``num = 5`, `x = 5.5`, `f` מפנה לעצם `First` חדש עם `num = 13`
`new Second(2, 3.7, arr[2])``Second(int, double, First)``num = 5`, `x = 5.5`, `f` מפנה לעצם הקיים `arr[2]`

1. `First()`: מציבה `num = 10`. זה גם ערך ברירת המחדל שמקבל `arr[2]` (עצם `Second` שנבנה בלי פרמטרים), ולכן `Second()` תזמן את `super()`/`base()`.

2. `First(int num)`: מציבה את הפרמטר ב-`num`.

3. `Second()`: מזמנת את הבונה הריקה של `First` (`num = 10`) ומציבה `x = 1.1`, `f = null`.

4. `Second(int num, First other)`: באיור `f` של `arr[3]` מצביע על עצם `First` נפרד עם `num = 13`, ולא על `arr[0]`. לכן יוצרים עותק: `new First(other.getNum())`. את `num` מעבירים ל-`super(num)`, ו-`x` מחשבים כ-`num + 0.5` =5+0.5=5.5=5+0.5=5.5.

5. `Second(int a, double b, First f)`: כאן `f` של `arr[4]` מצביע על העצם הקיים `arr[2]` (החץ באיור חוזר אליו), ולכן מציבים את ההפניה עצמה: `this.f = f`. את `num` מקבלים מ-(int)(2+3.7)=(int)5.7=5(int)(2+3.7)=(int)5.7=5, ואת `x` מאותו כלל של סעיף 4: 5+0.5=5.55+0.5=5.5.

השאלה אינה קובעת איך מחושבים הערכים מהפרמטרים, ולכן כל בונות שנותנות את אותם עצמים מתקבלות; בחרנו כלל אחד (`x = num + 0.5`) לשתי הבונות עם הפרמטרים. הוספנו ל-`First` פעולת `get` לתכונה `num` (במקום שבו כתוב `….`), כדי ש-`Second` תוכל לקרוא את `num` של עצם אחר. (ב-C# אסור לגשת לתכונה `protected` דרך הפניה מטיפוס `First` מתוך `Second`, ולכן ה-`Get` הכרחי שם.)

Java:

public class First
{
    protected int num;

    public First()                  // arr[1]: num = 10
    {
        this.num = 10;
    }
    public First(int num)           // arr[0]: num = 13
    {
        this.num = num;
    }
    public int getNum()
    {
        return this.num;
    }
}

public class Second extends First
{
    private double x;
    private First f;

    public Second()                 // arr[2]: num = 10, x = 1.1, f = null
    {
        super();
        this.x = 1.1;
        this.f = null;
    }
    public Second(int num, First other)   // arr[3]: num = 5, x = 5.5, עותק חדש של other
    {
        super(num);
        this.x = num + 0.5;
        this.f = new First(other.getNum());
    }
    public Second(int a, double b, First f) // arr[4]: num = 5, x = 5.5, f מפנה לעצם הקיים
    {
        super((int)(a + b));
        this.x = this.num + 0.5;
        this.f = f;
    }
}

C#:

public class First
{
    protected int num;

    public First()                  // arr[1]: num = 10
    {
        this.num = 10;
    }
    public First(int num)           // arr[0]: num = 13
    {
        this.num = num;
    }
    public int GetNum()
    {
        return this.num;
    }
}

public class Second : First
{
    private double x;
    private First f;

    public Second() : base()        // arr[2]: num = 10, x = 1.1, f = null
    {
        this.x = 1.1;
        this.f = null;
    }
    public Second(int num, First other) : base(num)   // arr[3]: num = 5, x = 5.5
    {
        this.x = num + 0.5;
        this.f = new First(other.GetNum());           // עותק חדש של other
    }
    public Second(int a, double b, First f) : base((int)(a + b))  // arr[4]
    {
        this.x = this.num + 0.5;
        this.f = f;                                   // הפניה לעצם הקיים
    }
}

תשובה: הבונות שלמעלה: `First()` ו-`First(int)`; `Second()`, `Second(int, First)` (יוצרת עותק חדש של העצם) ו-`Second(int, double, First)` (שומרת הפניה לעצם הקיים).

סעיף ב

(1)
תשובה:

לא תקין – שגיאת קומפילציה (הידור).

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

תשובה: לא תקין – שגיאת קומפילציה: אי אפשר להציב עצם `Shape` במשתנה `Circle`.

(2)
תשובה:

לא תקין – שגיאת קומפילציה (הידור).

הטיפוס המוצהר של `s1` הוא `Shape`. המהדר בודק רק את הטיפוס המוצהר: השמה מ-`Shape` ל-`Circle` היא המרה "כלפי מטה" (downcasting), והיא מחייבת המרה מפורשת `(Circle)`. בלי המרה – שגיאת קומפילציה. (גם עם המרה היינו מקבלים שגיאת זמן ריצה, כי `s1` מפנה לעצם `Shape` – ראו קטע 5.)

תשובה: לא תקין – שגיאת קומפילציה: חסרה המרה מפורשת מ-`Shape` ל-`Circle`.

(3)
תשובה:

תקין.

יש המרה מפורשת מ-`Shape` ל-`Circle`, ולכן המהדר מאשר (`Circle` יורשת מ-`Shape`). בזמן ריצה `s2` מפנה לעצם שנוצר ב-`new Circle()`, כלומר העצם באמת `Circle`, וההמרה מצליחה.

תשובה: תקין; `c2` מפנה לעצם ה-`Circle` של `s2`.

(4)
תשובה:

תקין.

ההמרה המפורשת מ-`Shape` ל-`Circle` עוברת הידור. בזמן ריצה `s3` מפנה לעצם `Cylinder`, ו-`Cylinder` יורשת מ-`Circle` – כלומר `Cylinder` הוא גם `Circle`, וההמרה מצליחה.

תשובה: תקין; `c3` מפנה לעצם ה-`Cylinder`.

(5)
תשובה:

לא תקין – שגיאת זמן ריצה.

בזמן הידור ההמרה מותרת: `s1` מטיפוס `Shape` ו-`Circle` יורשת מ-`Shape`, אז ייתכן שהעצם הוא `Circle`. אבל בזמן ריצה `s1` מפנה לעצם שנוצר ב-`new Shape()`, שאינו `Circle`. ההמרה נכשלת: ב-Java נזרקת `ClassCastException`, וב-C# נזרקת `InvalidCastException`.

תשובה: לא תקין – שגיאת זמן ריצה (המרה לא חוקית).

(6)
תשובה:

לא תקין – שגיאת זמן ריצה (בשורה השלישית).

1. `Triangle t = new Triangle();` – תקין.

2. `Shape s5 = t;` – תקין: המרה כלפי מעלה מ-`Triangle` ל-`Shape` מותרת תמיד.

3. `Circle c5 = (Circle)s5;` – עוברת הידור, כי הטיפוס המוצהר של `s5` הוא `Shape` ו-`Circle` היא תת-מחלקה שלה. אבל בזמן ריצה `s5` מפנה לעצם `Triangle`, ו-`Triangle` אינה `Circle` (הן "אחיות" בעץ הירושה). ההמרה נכשלת: `ClassCastException` ב-Java, `InvalidCastException` ב-C#.

תשובה: לא תקין – שגיאת זמן ריצה בהמרה `(Circle)s5`.

(7)
תשובה:

תקין.

`new Cylinder()` הוא עצם `Cylinder`. ההמרה `(Circle)` היא המרה כלפי מעלה (`Cylinder` יורשת מ-`Circle`) ולכן תקינה, והתוצאה מטיפוס `Circle` מוצבת במשתנה `Shape` – שוב המרה כלפי מעלה, מותרת.

תשובה: תקין; `s` מפנה לעצם `Cylinder`.

(8)
תשובה:

לא תקין – שגיאת קומפילציה (הידור).

ההמרה `(Shape)(new Cylinder())` עצמה תקינה, אבל הטיפוס של הביטוי הוא עכשיו `Shape`. הצבת ביטוי מטיפוס `Shape` במשתנה מטיפוס `Circle` היא המרה כלפי מטה ללא המרה מפורשת – שגיאת קומפילציה, למרות שהעצם עצמו הוא `Cylinder`. (בנוסף, המשתנה `c` כבר הוגדר בקטע הקוד הנתון, `Circle c = new Cylinder();`, והגדרה כפולה של אותו שם היא גם היא שגיאת קומפילציה.)

תשובה: לא תקין – שגיאת קומפילציה: אי אפשר להציב ביטוי מטיפוס `Shape` במשתנה `Circle` בלי המרה.

שאלה 4 · ממשקים, ירושה ופולימורפיזם – מעקב פלט

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

Java:

public interface Int1{ void doIt1(); }
public interface Int2{ void doIt2(); }

class One implements Int1
{
    private int a;
    public One()
    {
     System.out.println("ctor One");
     this.a = 0;
    }
    public  void doIt1()
    {
     System.out.println("One:DoIt1()");
     this.a += 5;
    }
    public String toString()
    {
     return "One: a=" + this.a;
    }
}
class Two extends One
{
    private int b;
    public Two()
    {
          System.out.println("ctor Two");
          this.b = 0;
    }
    public void doIt1()
    {
          System.out.println("Two: doIt1()");
          super.doIt1();
          this.b += 5;
    }
    public  String toString()
    {
          return super.toString() + " Two: b=" + this.b;
     }
 }
class Three extends One implements Int2
{
    private int c;
    public Three()
    {
          System.out.println("ctor1 Three");
          this.c = 0;
    }

public void doIt1()
    {
          System.out.println("Three: doIt1()");
          super.doIt1();
          this.c += 5;
    }

    public void doIt2()
    {
          System.out.println("Three: doIt2()");
          super.doIt1();
          this.c += 10;
    }

    public String toString()
    {
        return super.toString() + " Three: c=" + this.c;
     }
}

C#:

public interface Int1 { void DoIt1(); }
public interface Int2 { void DoIt2(); }

class One : Int1
 {
      private int a;
      public One()
      {
       Console.WriteLine("ctor One");
       this.a = 0;
      }
      public virtual void DoIt1()
      {
       Console.WriteLine("One:DoIt1()");
       this.a += 5;
      }
      public override string ToString()
      {
       return "One: a=" + this.a;
      }
 }
class Two : One
 {
      private int b;
      public Two()
      {
       Console.WriteLine("ctor Two");
       this.b = 0;
      }
      public override void DoIt1()
      {
       Console.WriteLine("Two: doIt1()");
       base.DoIt1();
       this.b += 5;
      }
      public override string ToString()
      {
      return base.ToString() + " Two: b=" + this.b;
      }
}
class Three : One, Int2
{
      private int c;
      public Three()
      {
       Console.WriteLine("ctor1 Three");
       this.c = 0;
      }
      public override void DoIt1()
      {
       Console.WriteLine("Three: doIt1()");
       base.DoIt1();
       this.c += 5;
      }
      public void DoIt2()
      {
       Console.WriteLine("Three: doIt2()");
       base.DoIt1();
       this.c += 10;
      }
      public override string ToString()
      {
       return base.ToString() + " Three: c=" + this.c;
      }
}

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

שימו לב שאין קשר בין סעיפים!

(1)

Java:

Int2 x1 = new Int2();
x1.doIt2();
System.out.println(x1);

C#:

Int2 x1 = new Int2();
x1.DoIt2();
Console.WriteLine(x1);
(2)

Java:

Int1 x2 = new Three();
Int2 y2 = (Int2)x2;
y2.doIt2();
System.out.println(x2);
System.out.println(y2);

C#:

Int1 x2 = new Three();
Int2 y2 = (Int2)x2;
y2.DoIt2();
Console.WriteLine(x2);
Console.WriteLine(y2);
(3)

Java:

Three x3 = new One();
x3.doIt1();
System.out.println(x3);

C#:

Three x3 = new One();
x3.DoIt1();
Console.WriteLine(x3);
(4)

Java:

One x4 = new Two();
Three y4 = (Three)x4;
y4.doIt2();
System.out.println(x4);
System.out.println(y4);

C#:

One x4 = new Two();
Three y4 = (Three)x4;
y4.DoIt2();
Console.WriteLine(x4);
Console.WriteLine(y4);
(5)

Java:

Int2 x5 = new Three();
((One)x5).doIt1();
System.out.println(x5);

C#:

Int2 x5 = new Three();
((One)x5).DoIt1();
Console.WriteLine(x5);
◂ פתרון מלא לשאלה 4

פתרון

(1)
תשובה:

לא תקין – שגיאת קומפילציה: אי אפשר ליצור עצם מממשק.

`Int2` הוא ממשק (interface). ממשק מגדיר רק כותרות של פעולות, בלי מימוש, ולכן אי אפשר ליצור ממנו עצם עם `new`. השורה `Int2 x1 = new Int2();` היא שגיאת קומפילציה (הידור), ושאר הקטע אינו מתבצע. אפשר להגדיר משתנה מטיפוס `Int2`, אבל הוא חייב להפנות לעצם של מחלקה שמממשת את הממשק (למשל `new Three()`).

תשובה: לא תקין – שגיאת קומפילציה: לא ניתן ליצור מופע של ממשק.

(בנוסח C# של השאלון הזימונים נכתבו באות קטנה, `doIt1()`/`doIt2()`, בעוד שבמחלקות הפעולות הן `DoIt1`/`DoIt2`. ב-C# יש הבחנה בין אותיות גדולות לקטנות, כך שזו טעות הקלדה; ברור שהכוונה ל-`DoIt1`/`DoIt2`, והניתוח זהה.)

(2)
תשובה:

תקין. הפלט: `ctor One`, `ctor1 Three`, `Three: doIt2()`, `One:DoIt1()`, `One: a=5 Three: c=10`, `One: a=5 Three: c=10`.

1. `Int1 x2 = new Three();` – `Three` יורשת מ-`One`, ש-`One` מממשת את `Int1`, ולכן `Three` היא `Int1`: ההשמה תקינה. יצירת העצם מפעילה קודם את הבונה של `One` ואחר כך את של `Three`: מודפס `ctor One` ואז `ctor1 Three`. עכשיו a=0a=0, c=0c=0.

2. `Int2 y2 = (Int2)x2;` – המרה מפורשת בין ממשקים מותרת בהידור; בזמן ריצה העצם הוא `Three`, שמממשת את `Int2`, ולכן ההמרה מצליחה. `x2` ו-`y2` מפנים לאותו עצם.

3. `y2.doIt2();` – מתבצעת `doIt2` של `Three`: מודפס `Three: doIt2()`, אחר כך `super.doIt1()` מפעיל את `doIt1` של `One` (ולא את זו של `Three`, כי `super` פונה ישירות למחלקת הבסיס): מודפס `One:DoIt1()` ו-a=0+5=5a=0+5=5. בסוף c=0+10=10c=0+10=10.

4. `System.out.println(x2);` – מופעלת `toString` של העצם בפועל, `Three` (פולימורפיזם): `super.toString()` נותנת `One: a=5`, ומתווסף ` Three: c=10`.

5. `System.out.println(y2);` – אותו עצם, אותו פלט.

ctor One
ctor1 Three
Three: doIt2()
One:DoIt1()
One: a=5 Three: c=10
One: a=5 Three: c=10

תשובה: תקין; הפלט שלמעלה (שש שורות).

(בנוסח C# של השאלון הזימונים נכתבו באות קטנה, `doIt1()`/`doIt2()`, בעוד שבמחלקות הפעולות הן `DoIt1`/`DoIt2`. ב-C# יש הבחנה בין אותיות גדולות לקטנות, כך שזו טעות הקלדה; ברור שהכוונה ל-`DoIt1`/`DoIt2`, והניתוח זהה.)

(3)
תשובה:

לא תקין – שגיאת קומפילציה: אי אפשר להציב עצם `One` במשתנה `Three`.

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

תשובה: לא תקין – שגיאת קומפילציה.

(בנוסח C# של השאלון הזימונים נכתבו באות קטנה, `doIt1()`/`doIt2()`, בעוד שבמחלקות הפעולות הן `DoIt1`/`DoIt2`. ב-C# יש הבחנה בין אותיות גדולות לקטנות, כך שזו טעות הקלדה; ברור שהכוונה ל-`DoIt1`/`DoIt2`, והניתוח זהה.)

(4)
תשובה:

לא תקין – שגיאת זמן ריצה בהמרה `(Three)x4`; לפני השגיאה מודפס `ctor One`, `ctor Two`.

1. `One x4 = new Two();` – תקין (`Two` יורשת מ-`One`). מודפס `ctor One` ואחריו `ctor Two`.

2. `Three y4 = (Three)x4;` – בהידור ההמרה מותרת: `x4` מטיפוס `One`, ו-`Three` יורשת מ-`One`, כך שייתכן שהעצם הוא `Three`. אבל בזמן ריצה העצם הוא `Two`, ו-`Two` ו-`Three` הן מחלקות "אחיות" – `Two` אינה `Three`. ההמרה נכשלת: ב-Java נזרקת `ClassCastException`, וב-C# `InvalidCastException`. התוכנית נעצרת, ושלוש השורות האחרונות אינן מתבצעות.

ctor One
ctor Two

ואחר כך שגיאת זמן ריצה.

תשובה: לא תקין – שגיאת זמן ריצה (המרה לא חוקית מ-`Two` ל-`Three`); לפני השגיאה מודפסות השורות `ctor One` ו-`ctor Two`.

(בנוסח C# של השאלון הזימונים נכתבו באות קטנה, `doIt1()`/`doIt2()`, בעוד שבמחלקות הפעולות הן `DoIt1`/`DoIt2`. ב-C# יש הבחנה בין אותיות גדולות לקטנות, כך שזו טעות הקלדה; ברור שהכוונה ל-`DoIt1`/`DoIt2`, והניתוח זהה.)

(5)
תשובה:

תקין. הפלט: `ctor One`, `ctor1 Three`, `Three: doIt1()`, `One:DoIt1()`, `One: a=5 Three: c=5`.

1. `Int2 x5 = new Three();` – `Three` מממשת את `Int2`, תקין. מודפס `ctor One`, `ctor1 Three`.

2. `((One)x5).doIt1();` – המרה מממשק למחלקה `One` מותרת בהידור, ובזמן ריצה העצם הוא `Three`, שהיא `One`, ולכן ההמרה מצליחה. ההמרה משנה רק את הטיפוס המוצהר; הפעולה שמתבצעת נקבעת לפי העצם בפועל, ולכן מתבצעת `doIt1` של `Three` (דריסה): מודפס `Three: doIt1()`, ואז `super.doIt1()` מדפיס `One:DoIt1()` ומעדכן a=5a=5; בסוף c=0+5=5c=0+5=5.

3. `System.out.println(x5);` – `toString` של `Three`: `One: a=5 Three: c=5`.

ctor One
ctor1 Three
Three: doIt1()
One:DoIt1()
One: a=5 Three: c=5

תשובה: תקין; הפלט שלמעלה (חמש שורות).

(בנוסח C# של השאלון הזימונים נכתבו באות קטנה, `doIt1()`/`doIt2()`, בעוד שבמחלקות הפעולות הן `DoIt1`/`DoIt2`. ב-C# יש הבחנה בין אותיות גדולות לקטנות, כך שזו טעות הקלדה; ברור שהכוונה ל-`DoIt1`/`DoIt2`, והניתוח זהה.)

שאלה 5 · מיקומים ומרחק מינימלי במחסנית

הערה כללית לשאלה:

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

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

א.

כתבו פעולה המקבלת מחסנית של מספרים שלמים `stk` ומספר שלם `num`.

הפעולה תחזיר מיקומו הראשון של `num` בתוך המחסנית. אם `num` לא מופיע במחסנית, הפעולה תחזיר ערך 1-.

לדוגמה:

עבור המחסנית `stk` הבאה והמספר `num=3`

⇅183151331221121037

הפעולה תחזיר 2.

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

Java:

public static int firstPlace(Stack<Integer>stk, int num)

C#:

public static int FirstPlace(Stack<int> stk, int num)
(5 נקודות)
ב.

כתבו פעולה המקבלת מחסנית של מספרים שלמים `stk` ומספר שלם `num`. הפעולה תחזיר את מיקומו האחרון של `num` בתוך המחסנית. אם `num` לא מופיע במחסנית, הפעולה תחזיר ערך 1-.

לדוגמה:

עבור המחסנית `stk` הבאה והמספר `num=3`

⇅183151331221121037

הפעולה תחזיר 10.

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

Java:

public static int lastPlace(Stack<Integer>stk, int num)

C#:

public static int LastPlace(Stack<int> stk, int num)
(5 נקודות)
ג.

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

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

לדוגמה:

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

⇅48-2114111-281
(5 נקודות)
ד.

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

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

סעיף א

תשובה:

מוציאים איברים מראש המחסנית למחסנית עזר וסופרים; בהופעה הראשונה של `num` שומרים את המונה ועוצרים. מחזירים את כל האיברים מהעזר ל-`stk` ומחזירים את המיקום (או 1-). בדוגמה: 2.

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

1. `count` סופר כמה איברים הוצאו, כלומר מה המיקום של האיבר הנוכחי. `place` מאותחל ל-1- ("לא נמצא").

2. כל עוד המחסנית לא ריקה וטרם נמצא `num`: מוציאים איבר `x`, דוחפים ל-`temp`, מגדילים את `count`. אם `x == num` – זו ההופעה הראשונה, שומרים `place = count` (התנאי של הלולאה יעצור אותה).

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

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

מעקב על הדוגמה: מוציאים 18 (`count=1`), אחר כך 3 (`count=2`) – שווה ל-`num`, `place=2`. מחזירים את 3 ו-18 למחסנית. מוחזר 2.

Java:

public static int firstPlace(Stack<Integer> stk, int num)
{
    Stack<Integer> temp = new Stack<Integer>();
    int place = -1;
    int count = 0;
    while (!stk.isEmpty() && place == -1)
    {
        int x = stk.pop();
        temp.push(x);
        count++;
        if (x == num)
            place = count;
    }
    while (!temp.isEmpty())        // החזרת המחסנית למצבה המקורי
        stk.push(temp.pop());
    return place;
}

C#:

public static int FirstPlace(Stack<int> stk, int num)
{
    Stack<int> temp = new Stack<int>();
    int place = -1;
    int count = 0;
    while (!stk.IsEmpty() && place == -1)
    {
        int x = stk.Pop();
        temp.Push(x);
        count++;
        if (x == num)
            place = count;
    }
    while (!temp.IsEmpty())        // החזרת המחסנית למצבה המקורי
        stk.Push(temp.Pop());
    return place;
}

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

סעיף ב

תשובה:

מוציאים את כל המחסנית למחסנית עזר תוך ספירה, ובכל הופעה של `num` מעדכנים `place = count`; כך נשאר המיקום של ההופעה האחרונה. מחזירים את האיברים ל-`stk` ומחזירים `place`. בדוגמה: 10.

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

1. `place = -1`, `count = 0`.

2. כל עוד `stk` לא ריקה: מוציאים `x`, דוחפים ל-`temp`, `count++`; אם `x == num` מציבים `place = count`.

3. מחזירים את כל האיברים מ-`temp` ל-`stk` (המחסנית חוזרת למצבה).

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

מעקב על הדוגמה: 3 מופיע במקומות 2, 5 ו-10. `place` מתעדכן ל-2, אחר כך ל-5 ולבסוף ל-10, ולכן מוחזר 10.

Java:

public static int lastPlace(Stack<Integer> stk, int num)
{
    Stack<Integer> temp = new Stack<Integer>();
    int place = -1;
    int count = 0;
    while (!stk.isEmpty())
    {
        int x = stk.pop();
        temp.push(x);
        count++;
        if (x == num)
            place = count;         // כל הופעה מאוחרת יותר דורסת את הקודמת
    }
    while (!temp.isEmpty())        // החזרת המחסנית למצבה המקורי
        stk.push(temp.pop());
    return place;
}

C#:

public static int LastPlace(Stack<int> stk, int num)
{
    Stack<int> temp = new Stack<int>();
    int place = -1;
    int count = 0;
    while (!stk.IsEmpty())
    {
        int x = stk.Pop();
        temp.Push(x);
        count++;
        if (x == num)
            place = count;         // כל הופעה מאוחרת יותר דורסת את הקודמת
    }
    while (!temp.IsEmpty())        // החזרת המחסנית למצבה המקורי
        stk.Push(temp.Pop());
    return place;
}

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

סעיף ג

תשובה:

מוציאים את האיברים אחד-אחד למחסנית עזר; לכל איבר `x` שהוצא מזמנים `firstPlace(stk, x)` על החלק שנשאר. אם בן הזוג נמצא במקום `place`, המרחק הוא `place - 1`; שומרים את המינימום. בסוף מחזירים את האיברים ל-`stk`. בדוגמה: 1.

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

1. `min` מאותחל לערך הגדול ביותר האפשרי.

2. כל עוד `stk` לא ריקה: מוציאים `x` ודוחפים אותו ל-`temp`.

3. `place = firstPlace(stk, x)`. אם `place != -1` ו-`place - 1 < min` – מעדכנים `min = place - 1`.

4. בסוף מחזירים את כל `temp` ל-`stk` ומחזירים `min`.

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

מעקב על הדוגמה (מיקומים מהראש): 4, 8, -2, 11, 4, 11, 1, -2, 8, 1.

איבר שהוצאמיקום בן הזוג בחלק שנשארמרחק`min`
4433
8763
-2543
11211
41- (כבר הוצא)–1
111-–1
1321
-2, 8, 11-–1

מוחזר 1, כמו בדוגמה.

Java:

public static int minDistance(Stack<Integer> stk)
{
    Stack<Integer> temp = new Stack<Integer>();
    int min = Integer.MAX_VALUE;
    while (!stk.isEmpty())
    {
        int x = stk.pop();
        temp.push(x);
        int place = firstPlace(stk, x);   // מיקום בן הזוג בחלק שנשאר
        if (place != -1 && place - 1 < min)
            min = place - 1;               // מספר האיברים שביניהם
    }
    while (!temp.isEmpty())                // החזרת המחסנית למצבה המקורי
        stk.push(temp.pop());
    return min;
}

C#:

public static int MinDistance(Stack<int> stk)
{
    Stack<int> temp = new Stack<int>();
    int min = int.MaxValue;
    while (!stk.IsEmpty())
    {
        int x = stk.Pop();
        temp.Push(x);
        int place = FirstPlace(stk, x);   // מיקום בן הזוג בחלק שנשאר
        if (place != -1 && place - 1 < min)
            min = place - 1;               // מספר האיברים שביניהם
    }
    while (!temp.IsEmpty())                // החזרת המחסנית למצבה המקורי
        stk.Push(temp.Pop());
    return min;
}

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

סעיף ד

תשובה:

א' – O(n)O(n), ב' – O(n)O(n), ג' – O(n2)O(n^2), כאשר nn מספר האיברים במחסנית.

נסמן ב-nn את מספר האיברים במחסנית. כל פעולת `push`/`pop`/`isEmpty` היא O(1)O(1).

1. סעיף א': במקרה הגרוע (`num` לא קיים או נמצא בתחתית) מוציאים את כל nn האיברים ומחזירים אותם: 2n2n העברות, כלומר O(n)O(n).

2. סעיף ב': תמיד עוברים על כל המחסנית ומחזירים אותה: O(n)O(n).

3. סעיף ג': הלולאה הראשית מבצעת nn סיבובים. בכל סיבוב מזמנים `firstPlace` על החלק שנשאר במחסנית, שגודלו עד nn, ולכן כל זימון עולה עד O(n)O(n). בסך הכול n⋅O(n)=O(n2)n\cdot O(n)=O(n^2) (בדיוק יותר: ∑k=0n−1k=n(n−1)2\sum_{k=0}^{n-1}k=\frac{n(n-1)}{2} העברות במקרה הגרוע), ועוד O(n)O(n) להחזרת המחסנית. לכן O(n2)O(n^2).

תשובה: א' – O(n)O(n); ב' – O(n)O(n); ג' – O(n2)O(n^2).

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

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

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

•יצרן (`producer`).

•מידה (`size`).

•צבע (`color`).

•מחיר בסיסי (`price`).

•האם נעל אורתופדי? (`orth`).

בנעלי נשים עבור כל זוג נשמרים הפרטים הבאים:

•יצרן (`producer`).

•מידה (`size`).

•צבע (`color`).

•מחיר בסיסי (`price`).

•שנת ייצור (`year`).

•גובה עקב (`heel`).

בנעלי גברים עבור כל זוג נשמרים הפרטים הבאים:

•יצרן (`producer`).

•מידה (`size`).

•צבע (`color`).

•מחיר בסיסי (`price`).

•שנת ייצור (`year`).

•אם זו נעל עבודה (`work`).

מחיר הנעליים נקבע לפי מספר קריטריונים:

•מחיר בסיסי עבור נעלי ילדים הוא 100 ₪.

•מחיר בסיסי עבור נעליים למבוגרים הוא 200 ₪.

•עבור מידה מעל 40 המחיר הוא 300 ₪.

•נעל ילדים אורתופדית מוסיפה 25 ₪ למחיר.

•גובה עקב של שלושה ס"מ לפחות מוסיף 30 ₪ למחיר, גובה עקב של חמישה ס"מ לפחות מוסיף 60 ₪ למחיר.

•עבור נעל שנוצרה השנה, 2023, יש תוספת של 50% למחיר.

•נעל עבודה מוזילה את מחיר הנעל ב- 50 ₪.

א.

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

(2 נקודות)
ב.

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

אפשר להניח שבכל מחלקה הוגדרו פעולות `set/get`.

(4 נקודות)
ג.

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

(2 נקודות)
ד.

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

(8 נקודות)
ה.

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

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

סעיף א

תשובה:

מחלקה מופשטת `Shoe` (producer, size, color, price); `KidsShoe` יורשת ממנה (orth); מחלקה מופשטת `AdultShoe` יורשת מ-`Shoe` (year); `WomenShoe` (heel) ו-`MenShoe` (work) יורשות מ-`AdultShoe`.

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

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

2. לנעלי נשים ולנעלי גברים יש בנוסף שנת ייצור, וגם כלל המחיר שלהן משותף (מחיר בסיסי 200 ₪ ותוספת 50% לנעל משנת 2023). לכן נגדיר מחלקת ביניים מופשטת `AdultShoe` – נעל מבוגרים – שיורשת מ-`Shoe`.

3. `KidsShoe` (נעל ילדים) יורשת מ-`Shoe` ומוסיפה את `orth`.

4. `WomenShoe` (נעל נשים) יורשת מ-`AdultShoe` ומוסיפה את `heel`; `MenShoe` (נעל גברים) יורשת מ-`AdultShoe` ומוסיפה את `work`.

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

                    +---------------------------+
                    |   Shoe   (abstract)       |
                    +---------------------------+
                    | # producer : String       |
                    | # size : int              |
                    | # color : String          |
                    | # price : double          |
                    +---------------------------+
                    | + calcPrice() : double    |
                    +---------------------------+
                        ^                   ^
                        |                   |
     +-----------------------+    +------------------------------+
     |   KidsShoe            |    |   AdultShoe   (abstract)     |
     +-----------------------+    +------------------------------+
     | - orth : boolean      |    | # year : int                 |
     +-----------------------+    +------------------------------+
     | + calcPrice() : double|    | + extra() : double (abstract)|
     +-----------------------+    | + calcPrice() : double       |
                                  +------------------------------+
                                       ^                  ^
                                       |                  |
                          +-------------------+   +-------------------+
                          |   WomenShoe       |   |   MenShoe         |
                          +-------------------+   +-------------------+
                          | - heel : double   |   | - work : boolean  |
                          +-------------------+   +-------------------+
                          | + extra() : double|   | + extra() : double|
                          +-------------------+   +-------------------+

תשובה: חמש מחלקות: `Shoe` (מופשטת) ← `KidsShoe`, `AdultShoe` (מופשטת) ← `WomenShoe`, `MenShoe`, כמתואר בתרשים.

סעיף ב

תשובה:

כל מחלקה מגדירה רק את התכונות החדשות שלה; הבונה של כל מחלקה יורשת מזמנת את בונה מחלקת הבסיס. המחיר הבסיסי נקבע בבונה: 100 ב-`KidsShoe`, 200 ב-`AdultShoe`.

הרעיון:

1. התכונות מוגדרות `protected` במחלקות הבסיס, כדי שהמחלקות היורשות יוכלו להשתמש בהן בחישוב המחיר.

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

3. את המחיר הבסיסי לא מקבלים כפרמטר – הוא נקבע לפי הסוג: `KidsShoe` מעבירה 100, ו-`AdultShoe` מעבירה 200 (וכך גם `WomenShoe` ו-`MenShoe`, דרכה).

4. גובה העקב נשמר כ-`double` (ס"מ, יכול להיות לא שלם).

Java:

public abstract class Shoe
{
    protected String producer;   // יצרן
    protected int size;          // מידה
    protected String color;      // צבע
    protected double price;      // מחיר בסיסי

    public Shoe(String producer, int size, String color, double price)
    {
        this.producer = producer;
        this.size = size;
        this.color = color;
        this.price = price;
    }
}

public class KidsShoe extends Shoe
{
    private boolean orth;        // האם אורתופדית

    public KidsShoe(String producer, int size, String color, boolean orth)
    {
        super(producer, size, color, 100);   // מחיר בסיסי לילדים
        this.orth = orth;
    }
}

public abstract class AdultShoe extends Shoe
{
    protected int year;          // שנת ייצור

    public AdultShoe(String producer, int size, String color, int year)
    {
        super(producer, size, color, 200);   // מחיר בסיסי למבוגרים
        this.year = year;
    }
}

public class WomenShoe extends AdultShoe
{
    private double heel;         // גובה עקב בס"מ

    public WomenShoe(String producer, int size, String color, int year, double heel)
    {
        super(producer, size, color, year);
        this.heel = heel;
    }
}

public class MenShoe extends AdultShoe
{
    private boolean work;        // האם נעל עבודה

    public MenShoe(String producer, int size, String color, int year, boolean work)
    {
        super(producer, size, color, year);
        this.work = work;
    }
}

C#:

public abstract class Shoe
{
    protected string producer;   // יצרן
    protected int size;          // מידה
    protected string color;      // צבע
    protected double price;      // מחיר בסיסי

    public Shoe(string producer, int size, string color, double price)
    {
        this.producer = producer;
        this.size = size;
        this.color = color;
        this.price = price;
    }
}

public class KidsShoe : Shoe
{
    private bool orth;           // האם אורתופדית

    public KidsShoe(string producer, int size, string color, bool orth)
        : base(producer, size, color, 100)   // מחיר בסיסי לילדים
    {
        this.orth = orth;
    }
}

public abstract class AdultShoe : Shoe
{
    protected int year;          // שנת ייצור

    public AdultShoe(string producer, int size, string color, int year)
        : base(producer, size, color, 200)   // מחיר בסיסי למבוגרים
    {
        this.year = year;
    }
}

public class WomenShoe : AdultShoe
{
    private double heel;         // גובה עקב בס"מ

    public WomenShoe(string producer, int size, string color, int year, double heel)
        : base(producer, size, color, year)
    {
        this.heel = heel;
    }
}

public class MenShoe : AdultShoe
{
    private bool work;           // האם נעל עבודה

    public MenShoe(string producer, int size, string color, int year, bool work)
        : base(producer, size, color, year)
    {
        this.work = work;
    }
}

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

סעיף ג

תשובה:

`Storage` מכילה מערך `Shoe[] shoes` (מטיפוס מחלקת הבסיס, כך שאפשר לשמור בו כל סוג נעל) ומונה `count`; ב-UML – קשר הכלה מ-`Storage` אל `Shoe`.

הרעיון: במחסן יש מאות זוגות נעליים מכל הסוגים. נשמור אותם במערך אחד מטיפוס מחלקת הבסיס `Shoe`: בזכות הירושה, כל `KidsShoe`, `WomenShoe` או `MenShoe` הוא גם `Shoe` ויכול להיכנס למערך. מונה `count` שומר כמה מקומות במערך תפוסים בפועל.

1. תכונה `shoes` – מערך של `Shoe`, בגודל מרבי שמתקבל בבונה (למשל 1000).

2. תכונה `count` – מספר הזוגות השמורים.

3. פעולה `addShoe` מוסיפה זוג למקום הפנוי הבא.

Java:

/*
 * המחלקה Storage – מחסן החנות.
 * שומרת את כל זוגות הנעליים שהחנות מציעה (ילדים, נשים וגברים)
 * במערך אחד מטיפוס מחלקת הבסיס Shoe – בזכות הירושה כל סוג נעל
 * יכול להישמר בו. count – מספר הזוגות השמורים בפועל במערך.
 */
public class Storage
{
    private Shoe[] shoes;   // כל זוגות הנעליים במחסן
    private int count;      // מספר הזוגות השמורים במערך

    public Storage(int max)
    {
        this.shoes = new Shoe[max];
        this.count = 0;
    }

    // הוספת זוג נעליים למחסן (אם יש מקום)
    public void addShoe(Shoe s)
    {
        if (this.count < this.shoes.length)
        {
            this.shoes[this.count] = s;
            this.count++;
        }
    }
}

C#:

/*
 * המחלקה Storage – מחסן החנות.
 * שומרת את כל זוגות הנעליים שהחנות מציעה (ילדים, נשים וגברים)
 * במערך אחד מטיפוס מחלקת הבסיס Shoe – בזכות הירושה כל סוג נעל
 * יכול להישמר בו. count – מספר הזוגות השמורים בפועל במערך.
 */
public class Storage
{
    private Shoe[] shoes;   // כל זוגות הנעליים במחסן
    private int count;      // מספר הזוגות השמורים במערך

    public Storage(int max)
    {
        this.shoes = new Shoe[max];
        this.count = 0;
    }

    // הוספת זוג נעליים למחסן (אם יש מקום)
    public void AddShoe(Shoe s)
    {
        if (this.count < this.shoes.Length)
        {
            this.shoes[this.count] = s;
            this.count++;
        }
    }
}

תוספת ל-UML: `Storage` מכילה עצמים מסוג `Shoe` (קשר הכלה – מעוין בצד המחלקה המכילה; למחסן אחד יש הרבה נעליים):

     +----------------------------+              +-------------------+
     |   Storage                  |              |   Shoe (abstract) |
     +----------------------------+  1        *  +-------------------+
     | - shoes : Shoe[]           |<>----------->|  ...              |
     | - count : int              |              +-------------------+
     +----------------------------+                 ^            ^
     | + addShoe(Shoe s)          |                 |            |
     | + countOrth() : int        |             KidsShoe     AdultShoe
     +----------------------------+                           ^      ^
                                                              |      |
                                                       WomenShoe   MenShoe

תשובה: המחלקה `Storage` שלמעלה, עם התיעוד, וקשר הכלה `Storage` ◇—→ `Shoe` בתרשים.

סעיף ד

תשובה:

`Shoe.calcPrice()` – מחיר בסיסי או 300 למידה מעל 40; `KidsShoe` דורסת ומוסיפה 25 לאורתופדית; `AdultShoe` דורסת: מוסיפה `extra()` (מופשטת) ומכפילה ב-1.5 לשנת 2023; `WomenShoe.extra()` – 30/60 לפי העקב, `MenShoe.extra()` – 50- לנעל עבודה.

הנחות (הקריטריונים אינם קובעים סדר):

- "עבור מידה מעל 40 המחיר הוא 300 ₪" – זה המחיר הבסיסי במקום 100/200, ועליו מוסיפים את שאר התוספות.

•תוספות העקב אינן מצטברות: עקב של 5 ס"מ לפחות מוסיף 60 ₪, עקב של 3 עד פחות מ-5 ס"מ מוסיף 30 ₪.

•תוספת ה-50% לנעל משנת 2023 מחושבת על המחיר אחרי התוספות וההנחות של הסוג (עקב / נעל עבודה). שנת ייצור קיימת רק לנעלי מבוגרים.

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

1. `Shoe.calcPrice()` – החלק המשותף לכולם: אם המידה מעל 40 מחזירה 300, אחרת את המחיר הבסיסי `price`.

2. `KidsShoe.calcPrice()` – דורסת: לוקחת את `super.calcPrice()` ומוסיפה 25 ₪ אם הנעל אורתופדית.

3. `AdultShoe.calcPrice()` – דורסת: לוקחת את `super.calcPrice()`, מוסיפה `extra()` – תוספת או הנחה שתלויה בסוג – ואם שנת הייצור 2023 מכפילה ב-1.5. `extra()` היא פעולה מופשטת ב-`AdultShoe`, ולכן כל נעל מבוגרים חייבת לממש אותה.

4. `WomenShoe.extra()` – 60 לעקב של 5 ס"מ לפחות, 30 לעקב של 3 ס"מ לפחות, אחרת 0.

5. `MenShoe.extra()` – 50- לנעל עבודה, אחרת 0.

כך אפשר לזמן `shoes[i].calcPrice()` לכל זוג במחסן, והגרסה המתאימה תופעל לפי הסוג בפועל.

Java:

// במחלקה Shoe: מחיר בסיסי, או 300 למידה מעל 40
public double calcPrice()
{
    if (this.size > 40)
        return 300;
    return this.price;
}

// במחלקה KidsShoe: תוספת לנעל אורתופדית
public double calcPrice()
{
    double p = super.calcPrice();
    if (this.orth)
        p = p + 25;
    return p;
}

// במחלקה AdultShoe: תוספת/הנחה לפי הסוג, ואז 50% לנעל משנת 2023
public abstract double extra();

public double calcPrice()
{
    double p = super.calcPrice() + this.extra();
    if (this.year == 2023)
        p = p * 1.5;
    return p;
}

// במחלקה WomenShoe: תוספת לפי גובה העקב
public double extra()
{
    if (this.heel >= 5)
        return 60;
    if (this.heel >= 3)
        return 30;
    return 0;
}

// במחלקה MenShoe: הנחה לנעל עבודה
public double extra()
{
    if (this.work)
        return -50;
    return 0;
}

C#:

// במחלקה Shoe: מחיר בסיסי, או 300 למידה מעל 40
public virtual double CalcPrice()
{
    if (this.size > 40)
        return 300;
    return this.price;
}

// במחלקה KidsShoe: תוספת לנעל אורתופדית
public override double CalcPrice()
{
    double p = base.CalcPrice();
    if (this.orth)
        p = p + 25;
    return p;
}

// במחלקה AdultShoe: תוספת/הנחה לפי הסוג, ואז 50% לנעל משנת 2023
public abstract double Extra();

public override double CalcPrice()
{
    double p = base.CalcPrice() + this.Extra();
    if (this.year == 2023)
        p = p * 1.5;
    return p;
}

// במחלקה WomenShoe: תוספת לפי גובה העקב
public override double Extra()
{
    if (this.heel >= 5)
        return 60;
    if (this.heel >= 3)
        return 30;
    return 0;
}

// במחלקה MenShoe: הנחה לנעל עבודה
public override double Extra()
{
    if (this.work)
        return -50;
    return 0;
}

דוגמאות:

•נעל ילדים מידה 30, אורתופדית: 100+25=125100+25=125 ₪.

•נעל נשים מידה 38, עקב 4 ס"מ, משנת 2023: (200+30)⋅1.5=345(200+30)\cdot 1.5=345 ₪.

•נעל גברים מידה 43, נעל עבודה, משנת 2023: (300−50)⋅1.5=375(300-50)\cdot 1.5=375 ₪.

תשובה: `calcPrice` נכתבה ב-`Shoe` (בסיס), נדרסה ב-`KidsShoe` וב-`AdultShoe`; התוספות של נעלי מבוגרים בפעולה `extra` ב-`WomenShoe` וב-`MenShoe`.

סעיף ה

תשובה:

עוברים על `shoes[0..count-1]`; סופרים כל איבר שהוא `KidsShoe` (בדיקת `instanceof` / `is`) ושה-`isOrth()` שלו `true`.

הרעיון: רק לנעלי ילדים יש תכונה `orth`. עוברים על כל הזוגות במחסן; לכל זוג בודקים קודם שהוא נעל ילדים (`instanceof` ב-Java, `is` ב-C#), ורק אז ממירים אותו ל-`KidsShoe` ובודקים אם הוא אורתופדי. הסדר בתנאי חשוב: אם הזוג אינו `KidsShoe`, החלק השני לא מתבצע (הערכה מקוצרת של `&&`), ולכן אין המרה לא חוקית.

נשתמש בפעולת ה-`get` של `orth` (לפי ההנחה בסעיף ב' היא קיימת; כתבנו אותה במפורש).

Java:

// במחלקה KidsShoe
public boolean isOrth()
{
    return this.orth;
}

// במחלקה Storage
public int countOrth()
{
    int c = 0;
    for (int i = 0; i < this.count; i++)
    {
        if (this.shoes[i] instanceof KidsShoe && ((KidsShoe)this.shoes[i]).isOrth())
            c++;
    }
    return c;
}

C#:

// במחלקה KidsShoe
public bool IsOrth()
{
    return this.orth;
}

// במחלקה Storage
public int CountOrth()
{
    int c = 0;
    for (int i = 0; i < this.count; i++)
    {
        if (this.shoes[i] is KidsShoe && ((KidsShoe)this.shoes[i]).IsOrth())
            c++;
    }
    return c;
}

תשובה: הפעולה `countOrth` שלמעלה; זמן ריצה O(n)O(n) במספר הזוגות במחסן.

שאלה 7 · עץ בינרי מיוחד – תתי-עצים ללא ערך משותף

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

לדוגמה:

העץ הבא הוא "עץ מיוחד":

העץ הבא הוא לא "עץ מיוחד" כי הערך 7 מופיע גם בתת-העץ השמאלי של הצומת 70 וגם בתת-העץ הימני שלו.

א.

האם קיים "עץ מיוחד" שיש בו ערכים זהים? אם כן – ציירו את העץ ואם לא – תסבירו מדוע עץ כזה לא קיים.

(3 נקודות)
ב.

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

(3 נקודות)
ג.

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

(9 נקודות)
ד.

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

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

סעיף א

תשובה:

כן. למשל שורש 5 שבנו השמאלי 5 (ואין בן ימני): בכל צומת אין ערך משותף בין תת-העץ השמאלי לימני, אף שהערך 5 מופיע פעמיים.

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

דוגמה:

      5
     /
    5

בדיקה לפי ההגדרה:

1. בשורש 5: תת-העץ השמאלי מכיל {5}, תת-העץ הימני ריק – אין ערך משותף.

2. בצומת השמאלי 5: שני תתי-העצים ריקים – אין ערך משותף.

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

תשובה: כן, קיים – למשל עץ שבו לשורש 5 יש בן שמאלי 5 בלבד.

סעיף ב

תשובה:

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

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

1. ניקח צומת כלשהו עם ערך vv, ערך כלשהו aa מתת-העץ השמאלי וערך כלשהו bb מתת-העץ הימני.

2. לפי ההגדרה a<va<v ו-b≥vb\ge v, ולכן a<v≤ba<v\le b, כלומר a≠ba\ne b.

3. זה נכון לכל זוג ערכים ולכל צומת, ולכן בשום צומת אין ערך שמופיע גם משמאל וגם מימין.

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

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

סעיף ג

תשובה:

רקורסיה: עץ ריק מיוחד; אחרת בודקים שאף ערך של תת-העץ השמאלי אינו מופיע בתת-העץ הימני (`noCommon`, בעזרת חיפוש `exists`), ושני תתי-העצים מיוחדים בעצמם.

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

1. `exists(t, x)` – האם הערך `x` נמצא בעץ `t`. עץ ריק – לא; אחרת: הערך בשורש, או שהוא קיים באחד מתתי-העצים.

2. `noCommon(t1, t2)` – האם אף ערך של `t1` אינו מופיע ב-`t2`. עוברים רקורסיבית על כל צומת של `t1` ומחפשים את ערכו ב-`t2` בעזרת `exists`. ברגע שנמצא ערך משותף מחזירים `false`.

3. `isSpecial(t)` – הכלל צריך להתקיים בכל צומת:

•עץ ריק הוא מיוחד (אין צמתים שיפרו את הכלל) – תנאי עצירה;

•בשורש: `noCommon(left, right)` חייב להיות `true`;

•ובנוסף כל אחד מתתי-העצים חייב להיות מיוחד בעצמו – זימון רקורסיבי.

בדיקה מול הדוגמאות: בעץ הראשון, בשורש 70 הערכים משמאל {10, 1, 7} ומימין {51, 212, 22, 17} – אין משותף; ב-10: {1} מול {7}; ב-51: ריק מול {212, 22, 17}; ב-212: {22} מול {17}. מוחזר `true`. בעץ השני, בשורש 70 הערך 7 משמאל נמצא גם מימין, ולכן `noCommon` מחזירה `false` ומוחזר `false`.

Java:

// האם הערך x נמצא בעץ t
public static boolean exists(BinNode<Integer> t, int x)
{
    if (t == null)
        return false;
    if (t.getValue() == x)
        return true;
    return exists(t.getLeft(), x) || exists(t.getRight(), x);
}

// האם אף ערך של t1 אינו מופיע ב-t2
public static boolean noCommon(BinNode<Integer> t1, BinNode<Integer> t2)
{
    if (t1 == null)
        return true;
    if (exists(t2, t1.getValue()))
        return false;
    return noCommon(t1.getLeft(), t2) && noCommon(t1.getRight(), t2);
}

public static boolean isSpecial(BinNode<Integer> t)
{
    if (t == null)
        return true;
    if (!noCommon(t.getLeft(), t.getRight()))
        return false;
    return isSpecial(t.getLeft()) && isSpecial(t.getRight());
}

C#:

// האם הערך x נמצא בעץ t
public static bool Exists(BinNode<int> t, int x)
{
    if (t == null)
        return false;
    if (t.GetValue() == x)
        return true;
    return Exists(t.GetLeft(), x) || Exists(t.GetRight(), x);
}

// האם אף ערך של t1 אינו מופיע ב-t2
public static bool NoCommon(BinNode<int> t1, BinNode<int> t2)
{
    if (t1 == null)
        return true;
    if (Exists(t2, t1.GetValue()))
        return false;
    return NoCommon(t1.GetLeft(), t2) && NoCommon(t1.GetRight(), t2);
}

public static bool IsSpecial(BinNode<int> t)
{
    if (t == null)
        return true;
    if (!NoCommon(t.GetLeft(), t.GetRight()))
        return false;
    return IsSpecial(t.GetLeft()) && IsSpecial(t.GetRight());
}

תשובה: הפעולה `isSpecial` שלמעלה (עם פעולות העזר `exists` ו-`noCommon`).

סעיף ד

תשובה:

O(n2)O(n^2), כאשר nn מספר הצמתים בעץ.

נסמן ב-nn את מספר הצמתים בעץ.

1. `exists(t2, x)` עוברת במקרה הגרוע על כל צמתי `t2`: O(∣t2∣)O(|t2|).

2. `noCommon(L, R)` מזמנת את `exists(R, ...)` פעם אחת לכל צומת של `L`, ולכן עולה O(∣L∣⋅∣R∣)O(|L|\cdot|R|) (ועוד O(∣L∣)O(|L|) למעבר על `L`).

3. `isSpecial` מזמנת את `noCommon(L, R)` פעם אחת בכל צומת vv של העץ, כאשר LL ו-RR הם תתי-העצים של vv.

הסכום הכולל הוא ∑v∣Lv∣⋅∣Rv∣\sum_v |L_v|\cdot|R_v|. המכפלה ∣Lv∣⋅∣Rv∣|L_v|\cdot|R_v| סופרת את זוגות הצמתים שאחד מהם בתת-העץ השמאלי של vv והשני בימני – כלומר זוגות ש-vv הוא האב הקדמון המשותף הנמוך ביותר שלהם. כל זוג צמתים נספר כך פעם אחת לכל היותר, ולכן הסכום אינו עולה על מספר הזוגות n(n−1)2\frac{n(n-1)}{2}. בנוסף כל צומת מבוקר מספר קבוע של פעמים ב-`isSpecial` עצמה – O(n)O(n).

לכן הסיבוכיות היא O(n2)O(n^2). החסם מושג, למשל, בעץ שבו לשורש שני תתי-עצים בגודל n2\frac{n}{2} בערך בלי ערכים משותפים: כבר בשורש מתבצעות כ-n2⋅n2=n24\frac{n}{2}\cdot\frac{n}{2}=\frac{n^2}{4} השוואות.

תשובה: O(n2)O(n^2).

שאלה 8 · ירושה, הכלה ותכונות סטטיות – מעקב

נתונות המחלקות `A, B, C` הבאות:

Java:

public class A
{
    private static int countA = 0;
    protected int x;
    public A()
     {
          countA++;
          this.x = 0;
    }
    public A(int x)
     {
          countA++;
          this.x = x;
    }
    public String toString()
     {
          return "A:"+this.x;
     }
    public int doIt(int z)
     {
          return this.x * z;
     }
    public static int getCount(){ return countA;   }
}// end of class A

public class B extends A
{
    protected int y;
    private static int countB = 0;
    public B(int y)
    {
          this.y = y;
          countB++;
    }
    public B(int x, int y)
    {
          super(x);
          countB++;
          this.y = y;
    }
    public String toString()
    {
        return "B:"+super.toString()+":"+this.y;
    }
    public static int getCount(){return countB;}
    public int doIt(int z)
    {
          return super.doIt(z) + this.y;
     }
} //end of class B
public class C extends B
{
    private A myA;
    private static int countC = 0;
    public C(int x, int y)
    {
        super(x, y);
        this.myA = new A(x+y);
        countC++;
    }
    public static int getCount(){return countC;}
    public String toString()
    {
        return "C:"+super.toString()+" ["+this.myA+"]";
    }
}// end of class C

C#:

public class A
{
  private static int countA = 0;
  protected int x;
  public A()
  {
      countA++;
      this.x = 0;
  }
  public A(int x)
  {
      countA++;
      this.x = x;
  }
  public override string ToString()
  {
      return "A:" + this.x;
  }
  public virtual int DoIt(int z)
  {
      return this.x * z;
  }
  public static int GetCount() { return countA; }
}// end of class A


public class B : A
{
  protected int y;
  private static int countB = 0;
  public B(int y)
  {
      this.y = y;
      countB++;
  }
  public B(int x, int y):base(x)
  {
      countB++;
      this.y = y;
  }
  public override string ToString()
  {
      return "B:" + base.ToString() + ":" + this.y;
  }
  public static new   int GetCount() { return countB; }
  public override int DoIt(int z)
  {
      return base.DoIt(z) + this.y;
  }
} //end of class B
public class C : B
{
  private A myA;
  private static int countC = 0;
  public C(int x, int y):base(x,y)
  {
      this.myA = new A(x + y);
      countC++;
  }
  public static new int GetCount() { return countC; }
  public override string ToString()
  {
      return "C:" + base.ToString() + " [" + this.myA + "]";
  }
}// end of class C
א.

ציירו תרשים UML שמייצג את הקשרים בין המחלקות `A, B, C`.

יש לסמן ירושה באמצעות החץ ⟶\longrightarrow והכלה באמצעות הסימן ⧫\rule[0.5ex]{2em}{1.2pt}\blacklozenge

(1 נקודות)
ב.

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

A[] arr = new A[5];
arr[0] = new A(13);
arr[1] = new B(5, 10);
arr[2] = new C(2, 7);
arr[3] = new C(3, 3);
arr[4] = new B(5);

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

(5 נקודות)
ג.

לקוד של סעיף ב' התווסף קוד הבא:

Java:

System.out.println("A objects: " + A.getCount());
System.out.println("B objects: " + B.getCount());
System.out.println("C objects: " + C.getCount());

C#:

Console.WriteLine("A objects: " + A.GetCount());
Console.WriteLine("B objects: " + B.GetCount());
Console.WriteLine("C objects: " + C.GetCount());

רשמו מה יהיה הפלט.

(3 נקודות)
ד.

לקוד של סעיף ב' התווסף קוד הבא:

Java:

for (int k=0; k <arr.length; k++)
  System.out.println(arr[k]);

C#:

for (int k=0; k <arr.length; k++)
   Console.WriteLine(arr[k]);

רשמו מה יהיה הפלט.

(5 נקודות)
ה.

לקוד של סעיף ב' התווסף קוד הבא:

Java:

for (int k=0; k <arr.length; k++)
  if(arr[k] instanceof B)
       System.out.println(arr[k].doIt(k+1));

C#:

for (int k=0; k <arr.length; k++)
   if(arr[k] instanceof B)
      Console.WriteLine(arr[k].doIt(k+1));

רשמו מה יהיה הפלט.

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

סעיף א

תשובה:

`B` יורשת מ-`A` ו-`C` יורשת מ-`B` (חצי ירושה C→B→A); בנוסף `C` מכילה עצם `A` (התכונה `myA`) – קו הכלה עם מעוין מלא בצד של `C`.

הקשרים:

1. `B extends A` – ירושה: חץ מ-`B` אל `A`.

2. `C extends B` – ירושה: חץ מ-`C` אל `B`.

3. ב-`C` יש תכונה `private A myA`, שנוצרת בבונה של `C` (`new A(x+y)`) – כלומר `C` מכילה עצם `A`: קו הכלה בין `C` ל-`A`, והמעוין בצד המחלקה המכילה, `C`.

        +----------------------+
        |          A           |<-------------------+
        +----------------------+                    |
        | - countA : int (st.) |                    |
        | # x : int            |                    |
        +----------------------+                    |
                   ^                                |
                   |  (ירושה)                       |
        +----------------------+                    |
        |          B           |                    |
        +----------------------+                    |  myA (הכלה)
        | # y : int            |                    |
        | - countB : int (st.) |                    |
        +----------------------+                    |
                   ^                                |
                   |  (ירושה)                       |
        +----------------------+                    |
        |          C           |◆-------------------+
        +----------------------+
        | - myA : A            |
        | - countC : int (st.) |
        +----------------------+

(`#` – protected, `-` – private, `(st.)` – תכונה סטטית.)

תשובה: `C` ← `B` ← `A` בירושה, ו-`C` מכילה את `A` (התכונה `myA`).

סעיף ב

תשובה:

נוצרו 7 עצמים: arr[0] – A(x=13); arr[1] – B(x=5, y=10); arr[2] – C(x=2, y=7, myA→A(x=9)); arr[3] – C(x=3, y=3, myA→A(x=6)); arr[4] – B(x=0, y=5). המונים: countA=7, countB=4, countC=2.

הרעיון: בכל יצירת עצם של מחלקה יורשת מתבצעת קודם הבונה של מחלקת הבסיס. בונה של `B` שאינה מזמנת `super(...)` במפורש מזמנת את `A()` הריקה. כל בונה של `A` מגדילה את `countA`, כל בונה של `B` מגדילה את `countB`, ובונה `C` מגדילה את `countC` – וגם יוצרת עצם `A` נוסף (`myA`), שמגדיל שוב את `countA`. המונים סטטיים – משותפים לכל העצמים של המחלקה.

שורהמה מתבצעעצמים שנוצרוcountAcountBcountC
`arr[0] = new A(13)``A(13)`A: x=13100
`arr[1] = new B(5, 10)``super(5)` ואז y=10B: x=5, y=10210
`arr[2] = new C(2, 7)``B(2,7)` → `A(2)`; אחר כך `myA = new A(2+7)`C: x=2, y=7; A: x=9421
`arr[3] = new C(3, 3)``B(3,3)` → `A(3)`; `myA = new A(3+3)`C: x=3, y=3; A: x=6632
`arr[4] = new B(5)``A()` (x=0) ואז y=5B: x=0, y=5742

העצמים:

arr[0] --> [ A | x = 13 ]
arr[1] --> [ B | x = 5,  y = 10 ]
arr[2] --> [ C | x = 2,  y = 7,  myA --> [ A | x = 9 ] ]
arr[3] --> [ C | x = 3,  y = 3,  myA --> [ A | x = 6 ] ]
arr[4] --> [ B | x = 0,  y = 5 ]

התכונות הסטטיות (שייכות למחלקות, לא לעצמים): `countA = 7`, `countB = 4`, `countC = 2`.

תשובה: חמישה עצמים במערך ועוד שני עצמי `A` פנימיים (x=9, x=6), עם הערכים שבציור.

סעיף ג

תשובה:

`A objects: 7`, `B objects: 4`, `C objects: 2`.

כל פעולת `getCount` היא סטטית ומחזירה את המונה של המחלקה שלה (ב-`B` וב-`C` הפעולה מוגדרת מחדש ומסתירה את זו של `A`; ב-C# זה מסומן ב-`new`). לפי המעקב בסעיף ב':

1. `countA = 7`: חמישה עצמים במערך (כל אחד מהם מפעיל בונה של `A`) ועוד שני עצמי `myA` שנוצרו בבונות של `C`. 5+2=75+2=7.

2. `countB = 4`: שני עצמי `B` ושני עצמי `C` (כל `C` הוא גם `B` ומפעיל בונה של `B`).

3. `countC = 2`: שני עצמי `C`.

A objects: 7
B objects: 4
C objects: 2

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

סעיף ד

תשובה:

`A:13`, `B:A:5:10`, `C:B:A:2:7 [A:9]`, `C:B:A:3:3 [A:6]`, `B:A:0:5`.

הדפסת עצם מפעילה את `toString` של הטיפוס בפועל של העצם (פולימורפיזם):

•`A`: `"A:" + x`.

•`B`: `"B:" + super.toString() + ":" + y`, כלומר `B:A:x:y`.

•`C`: `"C:" + super.toString() + " [" + myA + "]"`, כלומר `C:B:A:x:y [A:x']`, כאשר `myA` מודפס גם הוא בעזרת `toString` של `A`.

אינדקס kהעצםהפלט
0A, x=13`A:13`
1B, x=5, y=10`B:A:5:10`
2C, x=2, y=7, myA.x=9`C:B:A:2:7 [A:9]`
3C, x=3, y=3, myA.x=6`C:B:A:3:3 [A:6]`
4B, x=0, y=5`B:A:0:5`
A:13
B:A:5:10
C:B:A:2:7 [A:9]
C:B:A:3:3 [A:6]
B:A:0:5

(בנוסח C# הודפס `arr.length`; ב-C# התכונה היא `arr.Length`. הפלט זהה.)

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

סעיף ה

תשובה:

`20`, `13`, `15`, `5` (עבור k=1, 2, 3, 4).

הרעיון: התנאי `instanceof B` נכון לעצמי `B` וגם לעצמי `C` (כי `C` יורשת מ-`B`), ולא נכון רק ל-`arr[0]`. הפעולה `doIt` נדרסת ב-`B`: `super.doIt(z) + y` =x⋅z+y=x\cdot z+y. `C` אינה דורסת את `doIt`, ולכן גם לעצמי `C` מתבצעת הגרסה של `B`. הפרמטר הוא z=k+1z=k+1.

אינדקס kהעצם`instanceof B`חישוב x⋅z+yx\cdot z+yפלט
0A (x=13)לא––
1B (x=5, y=10)כן5⋅2+10=205\cdot 2+10=2020
2C (x=2, y=7)כן2⋅3+7=132\cdot 3+7=1313
3C (x=3, y=3)כן3⋅4+3=153\cdot 4+3=1515
4B (x=0, y=5)כן0⋅5+5=50\cdot 5+5=55
20
13
15
5

(בנוסח C# הודפסו `instanceof` ו-`doIt`, שאינם תחביר C#; הכוונה ל-`arr[k] is B` ול-`DoIt(k+1)`, והפלט זהה.)

תשובה: 20, 13, 15, 5 (כל מספר בשורה נפרדת).

שאלה 9 · מעקב אחר פעולה רקורסיבית על תור

נתונה הפעולה `sod` המקבלת תור `q` של מספרים שליליים וחיוביים (ללא אפסים). הפעולה משתמשת בפעולה רקורסיבית `what`

Java:

public static void sod(Queue<Integer> q)
{
    q.insert(0);
    what(q);
    q.remove();
}

public static void what(Queue<Integer> q)
{
  if (q.head() != 0)
  {
    int x = q.remove();
    if (x > 0)
        q.insert(x);
    what(q);
    if (x < 0)
        q.insert(x);
  }
}

C#:

public static void Sod(Queue<int> q)
{
    q.Insert(0);
    What(q);
    q.Remove();
}

public static void What(Queue<int> q)
{
  if (q.Head() != 0)
  {
    int x = q.Remove();
    if (x > 0)
        q.Insert(x);
    What(q);
    if (x < 0)
        q.Insert(x);
  }
}
א.

מה יהיה התוכן של התור `q` אחרי זימון הפעולה `sod(q)` עבור התור הבא:

⬅3-1724-9⬅

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

(6 נקודות)
ב.

אחרי זימון הפעולה `sod(q)` עבור התור `q` לא ריק, התור `q` נשאר ללא שינוי.

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

(1)

זה יכול לקרות רק כאשר בתור יש ערך אחד בלבד.

(2)

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

(3)

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

(4)

לא ייתכן שבתור יש גם ערכים חיוביים וגם ערכים שליליים.

(4 נקודות)
ג.

מה מבצעת הפעולה `sod` באופן כללי עבור התור של מספרים שליליים וחיוביים (ללא אפסים).

(2 נקודות)
ד.

כתבו את הפעולה `sod` בלי שימוש ברקורסיה.

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

סעיף א

תשובה:

התור יהיה: 3, 7, 2, 4, 9-, 1- (ראש התור 3).

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

(ראש התור הוא האיבר השמאלי.)

שלב 1 – `q.insert(0)`: התור: 3, 1-, 7, 2, 4, 9-, 0.

שלב 2 – הזימונים של `what` (בדרך "למטה"):

זימוןראש התורxפעולה לפני הזימון הבאהתור אחרי
what 133חיובי – `insert(3)`1-, 7, 2, 4, 9-, 0, 3
what 21-1-שלילי – ממתין7, 2, 4, 9-, 0, 3
what 377`insert(7)`2, 4, 9-, 0, 3, 7
what 422`insert(2)`4, 9-, 0, 3, 7, 2
what 544`insert(4)`9-, 0, 3, 7, 2, 4
what 69-9-שלילי – ממתין0, 3, 7, 2, 4
what 70–עצירה0, 3, 7, 2, 4

שלב 3 – החזרה מהרקורסיה ("למעלה"):

חוזרים אלxפעולה אחרי הזימוןהתור אחרי
what 69-`insert(-9)`0, 3, 7, 2, 4, 9-
what 5, 4, 34, 2, 7אין (חיוביים)ללא שינוי
what 21-`insert(-1)`0, 3, 7, 2, 4, 9-, 1-
what 13איןללא שינוי

שלב 4 – `q.remove()` מוציא את ה-0.

התור הסופי: 3, 7, 2, 4, 9-, 1-.

תשובה: 3, 7, 2, 4, 9-, 1- (ראש התור 3).

סעיף ב

(1)
תשובה:

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

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

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

תשובה: הטענה לא נכונה.

(2)
תשובה:

לא נכונה. דוגמה נגדית: התור 5- (ערך שלילי אחד). אין חיוביים, והשלילי היחיד "מתהפך" לעצמו – התור נשאר 5-. גם התור 3, 1- נשאר ללא שינוי.

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

דוגמה נגדית: התור 5- (ערך שלילי אחד). אין חיוביים, והשלילי היחיד "מתהפך" לעצמו – התור נשאר 5-. גם התור 3, 1- נשאר ללא שינוי.

תשובה: הטענה לא נכונה.

(3)
תשובה:

לא נכונה. דוגמה נגדית: התור 1, 2 – כולו חיובי, ונשאר ללא שינוי.

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

דוגמה נגדית: התור 1, 2 – כולו חיובי, ונשאר ללא שינוי.

תשובה: הטענה לא נכונה.

(4)
תשובה:

לא נכונה. דוגמה נגדית: התור 3, 1- (ראש התור 3). החיובי 3 נשאר בתחילת התור, והשלילי היחיד 1- נשאר אחריו – התור נשאר 3, 1-. (גם 4, 1-, 2-, 1- נשאר ללא שינוי.)

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

דוגמה נגדית: התור 3, 1- (ראש התור 3). החיובי 3 נשאר בתחילת התור, והשלילי היחיד 1- נשאר אחריו – התור נשאר 3, 1-. (גם 4, 1-, 2-, 1- נשאר ללא שינוי.)

תשובה: הטענה לא נכונה.

סעיף ג

תשובה:

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

מהמעקב בסעיף א':

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

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

3. ה-0 שהיה בראש מוצא, ונשארים רק המספרים המקוריים.

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

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

סעיף ד

תשובה:

מוסיפים 0; כל עוד ראש התור אינו 0 – מוציאים איבר: חיובי חוזר לסוף התור, שלילי נדחף למחסנית. מוציאים את ה-0, ומרוקנים את המחסנית לסוף התור (השליליים בסדר הפוך).

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

1. מוסיפים 0 לסוף התור כסימן לסוף הסיבוב.

2. כל עוד ראש התור אינו 0: מוציאים `x`. אם הוא חיובי – מכניסים אותו מיד לסוף התור (אחרי ה-0); אם הוא שלילי – דוחפים אותו למחסנית.

3. כשה-0 בראש – מוציאים אותו. עכשיו בתור רק החיוביים, בסדרם המקורי.

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

מעקב על התור של סעיף א': החיוביים 3, 7, 2, 4 חוזרים לתור; המחסנית מקבלת 1- ואחר כך 9-. אחרי הוצאת ה-0 מרוקנים את המחסנית: קודם 9- ואחר כך 1-. התוצאה 3, 7, 2, 4, 9-, 1- – כמו בגרסה הרקורסיבית.

Java:

public static void sod(Queue<Integer> q)
{
    Stack<Integer> stk = new Stack<Integer>();
    q.insert(0);                   // סימון סוף הסיבוב
    while (q.head() != 0)
    {
        int x = q.remove();
        if (x > 0)
            q.insert(x);           // חיובי – חוזר לסוף התור מיד
        else
            stk.push(x);           // שלילי – נשמר במחסנית
    }
    q.remove();                    // הוצאת ה-0
    while (!stk.isEmpty())         // השליליים בסדר הפוך
        q.insert(stk.pop());
}

C#:

public static void Sod(Queue<int> q)
{
    Stack<int> stk = new Stack<int>();
    q.Insert(0);                   // סימון סוף הסיבוב
    while (q.Head() != 0)
    {
        int x = q.Remove();
        if (x > 0)
            q.Insert(x);           // חיובי – חוזר לסוף התור מיד
        else
            stk.Push(x);           // שלילי – נשמר במחסנית
    }
    q.Remove();                    // הוצאת ה-0
    while (!stk.IsEmpty())         // השליליים בסדר הפוך
        q.Insert(stk.Pop());
}

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

שאלה 10 · ניהול לקוחות ודירות בשרשראות חוליות

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

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

•`code` – מספר ייחודי של הדירה, מטיפוס שלם, `int`.

•`city` – העיר שבה נמצאת הדירה, מטיפוס מחרוזת, `String`.

•`numRooms` – מספר החדרים, מטיפוס שלם, `int`.

•`numPictures` – מספר תמונות הדירה, מטיפוס שלם, `int`.

במחלקה הוגדרו פעולה בונה ופעולות `set/get` לכל התכונות. המחלקה `Client` מייצגת לקוח. למחלקה יש את התכונות הבאות:

•`id` – מספר תעודת הזהות של הלקוח, מטיפוס מחרוזת, `String`.

•`codeList` – רשימה (שרשרת חוליות) של קודי הדירות שהלקוח כבר צפה בהן, מטיפוס `Node<Integer>`.

•`totalSum` – סכום תשלום, מטיפוס שלם, `int`.

במחלקה הוגדרו פעולות `set/get` לכל התכונות והפעולה הבונה הבאה:

Java:

public Client(String id)
{
      this.id = id;
      this.codeList = null;
      this.totalSum = 0;
}

C#:

public Client(string id)
{
    this.id = id;
    this.codeList = null;
    this.totalSum = 0;
}

(בנוסח C#: הטיפוסים `string` ו-`Node<int>`, ופעולות `Set/Get`.)

א.

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

(4 נקודות)

המחלקה `Rentings` מייצגת נתונים של החברה. למחלקה שתי תכונות:

•`aparts` – רשימה (שרשרת חוליות) של דירות מטיפוס `Node<Apartment>`.

•`clients` – רשימה (שרשרת חוליות) של לקוחות מטיפוס `Node<Client>`.

במחלקה הוגדרו פעולה בונה ופעולות `set/get` לכל התכונות.

ב.

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

Java:

public void addClient(String id)

C#:

public void AddClient(string id)
(6 נקודות)
ג.

כדי לייעל חיפוש דירה מתאימה לדרישות הלקוח הוחלט להוסיף למחלקה `Rentings` פעולה המדפיסה רשימת קודים של דירות הנמצאות בעיר מסוימת `city`, שיש להן מספר חדרים מסוים `numRooms` ויש לפחות `numPictures` תמונות.

אם אין במאגר נתוני החברה דירות מתאימות הפעולה תדפיס הודעה "No match".

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

Java:

public void printMatch(String city, int numRooms, int numPictures)

C#:

public void PrintMatch(string city, int numRooms, int numPictures)
(6 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

מחפשים את הקוד ב-`codeList`; אם נמצא – לא עושים כלום. אחרת מוסיפים חוליה חדשה עם הקוד לראש הרשימה ומגדילים את `totalSum` ב-1.

הרעיון: דירה היא "חדשה" ללקוח אם הקוד שלה עוד לא מופיע ברשימה `codeList`.

1. עוברים על שרשרת החוליות `codeList` עם הפניה `p`. אם נמצאה חוליה שערכה שווה ל-`code` – הלקוח כבר צפה בדירה, הצפייה בחינם, ויוצאים מהפעולה בלי שינוי.

2. אם סיימנו את המעבר בלי למצוא – זו דירה חדשה:

•מוסיפים חוליה חדשה עם הקוד. הכי פשוט להוסיף לראש הרשימה: `new Node<Integer>(code, this.codeList)` – החוליה החדשה מצביעה על הרשימה הקיימת (גם אם היא `null`), והיא הופכת לראש החדש. סדר הקודים ברשימה אינו חשוב.

•מחייבים את הלקוח בשקל אחד: `totalSum++`.

Java:

public void addApCode(int code)
{
    Node<Integer> p = this.codeList;
    while (p != null)
    {
        if (p.getValue() == code)
            return;                // הלקוח כבר צפה בדירה – אין חיוב
        p = p.getNext();
    }
    this.codeList = new Node<Integer>(code, this.codeList);  // הוספה לראש הרשימה
    this.totalSum++;               // חיוב בשקל אחד
}

C#:

public void AddApCode(int code)
{
    Node<int> p = this.codeList;
    while (p != null)
    {
        if (p.GetValue() == code)
            return;                // הלקוח כבר צפה בדירה – אין חיוב
        p = p.GetNext();
    }
    this.codeList = new Node<int>(code, this.codeList);  // הוספה לראש הרשימה
    this.totalSum++;               // חיוב בשקל אחד
}

דוגמה: לקוח חדש צופה בדירות 5, 7 ושוב 5: אחרי 5 – הרשימה {5}, סכום 1; אחרי 7 – {7, 5}, סכום 2; אחרי 5 שוב – אין שינוי, הסכום נשאר 2.

תשובה: הפעולה `addApCode` שלמעלה.

סעיף ב

תשובה:

עוברים על `clients` ומשווים את `getId()` של כל לקוח ל-`id` (בעזרת `equals`); אם נמצא – יוצאים. אחרת יוצרים `new Client(id)` ומוסיפים אותו בחוליה חדשה לראש הרשימה.

הרעיון: קודם מוודאים שהלקוח עוד לא רשום, ורק אז יוצרים עצם `Client` חדש ומוסיפים אותו.

1. עוברים על שרשרת `clients`. לכל חוליה לוקחים את הלקוח (`getValue()`) ואת תעודת הזהות שלו (`getId()`).

2. משווים מחרוזות ב-Java בעזרת `equals` (ולא `==`, שמשווה הפניות); ב-C# האופרטור `==` על `string` משווה את התוכן.

3. אם נמצאה התאמה – הלקוח קיים, יוצאים בלי לעשות כלום.

4. אחרת יוצרים לקוח חדש בעזרת הבונה הנתונה `Client(id)` (רשימת צפיות ריקה, סכום 0) ומוסיפים אותו בחוליה חדשה לראש הרשימה.

Java:

public void addClient(String id)
{
    Node<Client> p = this.clients;
    while (p != null)
    {
        if (p.getValue().getId().equals(id))
            return;                // הלקוח כבר קיים
        p = p.getNext();
    }
    this.clients = new Node<Client>(new Client(id), this.clients);
}

C#:

public void AddClient(string id)
{
    Node<Client> p = this.clients;
    while (p != null)
    {
        if (p.GetValue().GetId() == id)
            return;                // הלקוח כבר קיים
        p = p.GetNext();
    }
    this.clients = new Node<Client>(new Client(id), this.clients);
}

תשובה: הפעולה `addClient` שלמעלה.

סעיף ג

תשובה:

עוברים על `aparts`; לכל דירה שעירה שווה ל-`city`, מספר חדריה שווה ל-`numRooms` ומספר תמונותיה לפחות `numPictures` – מדפיסים את הקוד ומסמנים `found = true`. אם בסוף `found` עדיין `false` – מדפיסים "No match".

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

1. `found = false`.

2. לכל דירה ב-`aparts` בודקים את שלושת התנאים יחד:

•העיר שלה שווה ל-`city` (השוואת מחרוזות – `equals` ב-Java);

•מספר החדרים שווה ל-`numRooms`;

•מספר התמונות לפחות `numPictures`, כלומר `>=`.

3. אם שלושתם מתקיימים – מדפיסים את קוד הדירה ומציבים `found = true`.

4. אחרי הלולאה: אם `found` עדיין `false`, לא נמצאה אף דירה מתאימה – מדפיסים `No match`.

Java:

public void printMatch(String city, int numRooms, int numPictures)
{
    boolean found = false;
    Node<Apartment> p = this.aparts;
    while (p != null)
    {
        Apartment ap = p.getValue();
        if (ap.getCity().equals(city) && ap.getNumRooms() == numRooms
                && ap.getNumPictures() >= numPictures)
        {
            System.out.println(ap.getCode());
            found = true;
        }
        p = p.getNext();
    }
    if (!found)
        System.out.println("No match");
}

C#:

public void PrintMatch(string city, int numRooms, int numPictures)
{
    bool found = false;
    Node<Apartment> p = this.aparts;
    while (p != null)
    {
        Apartment ap = p.GetValue();
        if (ap.GetCity() == city && ap.GetNumRooms() == numRooms
                && ap.GetNumPictures() >= numPictures)
        {
            Console.WriteLine(ap.GetCode());
            found = true;
        }
        p = p.GetNext();
    }
    if (!found)
        Console.WriteLine("No match");
}

דוגמה: אם במאגר הדירות 1 (חיפה, 3 חדרים, 5 תמונות), 2 (חיפה, 3 חדרים, 2 תמונות), 3 (חיפה, 3 חדרים, 8 תמונות) ו-4 (אילת, 3 חדרים, 9 תמונות), הזימון עם `"Haifa", 3, 5` מדפיס 1 ו-3; הזימון עם `"Haifa", 4, 1` מדפיס `No match`.

תשובה: הפעולה `printMatch` שלמעלה; זמן ריצה O(n)O(n) במספר הדירות.

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

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

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