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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · מיקום מספר בתור והעברת איברים לראש

א.

כתבו פעולה `putInPlace` המקבלת תור `q` ומספר `num` וממקמת את המספר `num` במיקומו, כך שכל האיברים הקטנים ממנו, נמצאים לפניו וכל האיברים השווים לו או הגדולים ממנו נמצאים אחריו.

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

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

לדוגמה:

עבור התור `q` הבא: 2, 10, 12, 3, 7, 4, 1 (2 בראש התור)

והמספר `num=9`

התור שיתקבל יכול להיות: 2, 3, 7, 4, 1, 9, 10, 12

והפעולה תחזיר 6 (מיקומו של ה-`num` אחרי הכנסתו).

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

Java:

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

C#:

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

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

לדוגמה:

עבור התור `q` הבאה: 7, 2, 5, 4, 6, 8, 10, 12 (7 בראש התור)

והמספר `k=5` התור `q` יראה כך: 4, 6, 8, 10, 12, 7, 2, 5

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

Java:

public static void moveToFront(Queue<Integer> q, int k)

C#:

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

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

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

סעיף א

תשובה:

מרוקנים את `q` לשני תורי עזר (קטנים מ-`num` / גדולים או שווים), מחזירים לתור את הקטנים, אחריהם את `num` ואחריו את הגדולים; המיקום המוחזר הוא מספר הקטנים ועוד 1.

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

1. מוציאים את כל איברי `q`. כל איבר קטן מ-`num` נכנס לתור `small`, וכל איבר גדול או שווה ל-`num` נכנס לתור `big`.

2. `q` עכשיו ריק. מכניסים אליו בחזרה את כל איברי `small` וסופרים אותם. המשתנה `place` מתחיל ב-1, ולכן אחרי הלולאה הוא שווה למספר הקטנים ועוד 1 - בדיוק המיקום הסידורי של `num`.

3. מכניסים את `num`, ואחריו את כל איברי `big`.

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

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

Java:

public static int putInPlace(Queue<Integer> q, int num)
{
    Queue<Integer> small = new Queue<Integer>();   // האיברים הקטנים מ-num
    Queue<Integer> big = new Queue<Integer>();     // האיברים הגדולים או השווים ל-num
    while (!q.isEmpty())
    {
        int x = q.remove();
        if (x < num)
            small.insert(x);
        else
            big.insert(x);
    }
    int place = 1;                                 // המיקום הסידורי של num
    while (!small.isEmpty())
    {
        q.insert(small.remove());
        place++;
    }
    q.insert(num);
    while (!big.isEmpty())
        q.insert(big.remove());
    return place;
}

C#:

public static int PutInPlace(Queue<int> q, int num)
{
    Queue<int> small = new Queue<int>();   // האיברים הקטנים מ-num
    Queue<int> big = new Queue<int>();     // האיברים הגדולים או השווים ל-num
    while (!q.IsEmpty())
    {
        int x = q.Remove();
        if (x < num)
            small.Insert(x);
        else
            big.Insert(x);
    }
    int place = 1;                                 // המיקום הסידורי של num
    while (!small.IsEmpty())
    {
        q.Insert(small.Remove());
        place++;
    }
    q.Insert(num);
    while (!big.IsEmpty())
        q.Insert(big.Remove());
    return place;
}

בדיקה על הדוגמה: `q = 2, 10, 12, 3, 7, 4, 1`, `num = 9`.

•`small = 2, 3, 7, 4, 1`, `big = 10, 12`.

•התור החדש: `2, 3, 7, 4, 1, 9, 10, 12`, ו-`place = 1 + 5 = 6`.

תשובה: הפעולה שלמעלה; בדוגמה היא מחזירה 6 והתור הוא `2, 3, 7, 4, 1, 9, 10, 12`.

סעיף ב

תשובה:

סופרים את איברי התור `n` (בעזרת תור עזר, והתור משוחזר), ואז מעבירים `n-k` פעמים את האיבר שבראש התור לסוף התור.

הרעיון: להעביר את `k` האחרונים לראש זה אותו דבר כמו להעביר את `n-k` הראשונים לסוף התור (סיבוב של התור). פעולה כזו קלה בתור: `q.insert(q.remove())`.

1. פעולת עזר `size` סופרת את איברי התור: מעבירה את כולם לתור עזר תוך כדי ספירה, ומחזירה אותם ל-`q` באותו סדר.

2. `moveToFront` מחשבת `n = size(q)` ומבצעת `n-k` פעמים: מוציאה את האיבר שבראש התור ומכניסה אותו לסופו.

3. אחרי `n-k` סיבובים, `n-k` האיברים שהיו בתחילת התור נמצאים בסופו (באותו סדר), ו-`k` האחרונים הגיעו לראש התור.

Java:

public static int size(Queue<Integer> q)
{
    Queue<Integer> temp = new Queue<Integer>();
    int count = 0;
    while (!q.isEmpty())
    {
        temp.insert(q.remove());
        count++;
    }
    while (!temp.isEmpty())        // מחזירים את התור למצבו המקורי
        q.insert(temp.remove());
    return count;
}

public static void moveToFront(Queue<Integer> q, int k)
{
    int n = size(q);
    for (int i = 0; i < n - k; i++)    // n-k האיברים הראשונים עוברים לסוף התור
        q.insert(q.remove());
}

C#:

public static int Size(Queue<int> q)
{
    Queue<int> temp = new Queue<int>();
    int count = 0;
    while (!q.IsEmpty())
    {
        temp.Insert(q.Remove());
        count++;
    }
    while (!temp.IsEmpty())        // מחזירים את התור למצבו המקורי
        q.Insert(temp.Remove());
    return count;
}

public static void MoveToFront(Queue<int> q, int k)
{
    int n = Size(q);
    for (int i = 0; i < n - k; i++)    // n-k האיברים הראשונים עוברים לסוף התור
        q.Insert(q.Remove());
}

בדיקה על הדוגמה: `n = 8`, `k = 5`, ולכן מסובבים `8-5 = 3` פעמים: האיברים 7, 2, 5 עוברים לסוף, והתור הוא `4, 6, 8, 10, 12, 7, 2, 5`, כנדרש.

תשובה: הפעולה שלמעלה (ספירת האיברים ואז `n-k` סיבובים של ראש התור לסופו).

סעיף ג

תשובה:

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

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

1. סעיף א' (`putInPlace`): כל איבר יוצא מ-`q` פעם אחת (לתור `small` או `big`) ונכנס חזרה ל-`q` פעם אחת. כל פעולת תור (`insert`, `remove`, `head`, `isEmpty`) היא O(1)O(1), ולכן בסך הכול כ-2n2n פעולות: O(n)O(n).

2. סעיף ב' (`moveToFront`): הפעולה `size` עוברת על התור פעמיים (הוצאה לתור עזר והחזרה) - 2n2n פעולות. אחר כך n−k<nn-k<n סיבובים, כל אחד O(1)O(1). בסך הכול לכל היותר 3n3n פעולות: O(n)O(n).

תשובה: סעיף א' - O(n)O(n), סעיף ב' - O(n)O(n).

שאלה 2 · סידור זוגיים ואי-זוגיים בשרשרת דו-כיוונית

בעזרת המחלקה `BinNode` אפשר לממש שרשרת חוליות דו-כיוונית.

א.

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

סדר האיברים לא חשוב.

לדוגמה:

אם לפני הפעולה השרשרת הייתה: 1, 11, 4, 6, 3

אז אחרי הפעולה היא __יכולה להיות__: 6, 4, 11, 1, 3

שימו לב: אין להשתמש במבנה נתונים נוסף!

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

Java:

public static void order(BinNode<Integer> chain)

C#:

public static void Order(BinNode<int> chain)
(12 נקודות)
ב.

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

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

סעיף א

תשובה:

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

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

1. `posL` מצביע על החוליה הראשונה. `posR` מתקדם עד החוליה האחרונה (כל עוד יש לה חוליה מימין).

2. כל עוד `posL != posR`:

•אם הערך ב-`posL` זוגי - הוא כבר במקום הנכון, ו-`posL` מתקדם ימינה.

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

•אחרת: ב-`posL` אי-זוגי וב-`posR` זוגי - מחליפים את שני הערכים. בסיבוב הבא `posL` יתקדם (כי עכשיו יש בו זוגי).

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

Java:

public static void order(BinNode<Integer> chain)
{
    if (chain == null)
        return;
    BinNode<Integer> posL = chain, posR = chain;
    while (posR.hasRight())            // posR מתקדם לחוליה האחרונה
        posR = posR.getRight();
    while (posL != posR)
    {
        if (posL.getValue() % 2 == 0)          // זוגי במקומו - מתקדמים ימינה
            posL = posL.getRight();
        else if (posR.getValue() % 2 != 0)     // אי-זוגי במקומו - זזים שמאלה
            posR = posR.getLeft();
        else                                   // posL אי-זוגי ו-posR זוגי - מחליפים ערכים
        {
            int x = posL.getValue();
            posL.setValue(posR.getValue());
            posR.setValue(x);
        }
    }
}

C#:

public static void Order(BinNode<int> chain)
{
    if (chain == null)
        return;
    BinNode<int> posL = chain, posR = chain;
    while (posR.HasRight())            // posR מתקדם לחוליה האחרונה
        posR = posR.GetRight();
    while (posL != posR)
    {
        if (posL.GetValue() % 2 == 0)          // זוגי במקומו - מתקדמים ימינה
            posL = posL.GetRight();
        else if (posR.GetValue() % 2 != 0)     // אי-זוגי במקומו - זזים שמאלה
            posR = posR.GetLeft();
        else                                   // posL אי-זוגי ו-posR זוגי - מחליפים ערכים
        {
            int x = posL.GetValue();
            posL.SetValue(posR.GetValue());
            posR.SetValue(x);
        }
    }
}

מעקב על הדוגמה (`1, 11, 4, 6, 3`):

שלב`posL``posR`פעולההשרשרת
113שניהם אי-זוגיים: `posR` שמאלה1, 11, 4, 6, 3
216החלפה6, 11, 4, 1, 3
361זוגי: `posL` ימינה6, 11, 4, 1, 3
4111`posR` שמאלה6, 11, 4, 1, 3
5114החלפה6, 4, 11, 1, 3
6411זוגי: `posL` ימינה, נפגשים6, 4, 11, 1, 3

התוצאה `6, 4, 11, 1, 3` - בדיוק כמו בדוגמה.

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

סעיף ב

תשובה:

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

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

1. ההגעה לחוליה האחרונה עם `posR`: מעבר אחד על השרשרת, n−1n-1 צעדים.

2. בלולאה הראשית, בכל סיבוב אחד המצביעים מתקרב לשני בחוליה אחת, או שמתבצעת החלפה (O(1)O(1)) שאחריה `posL` מתקדם. המרחק בין המצביעים הוא לכל היותר n−1n-1, ולכן יש לכל היותר כ-2n2n סיבובים.

3. בסך הכול כל חוליה נסרקת מספר קבוע של פעמים: O(n)O(n).

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

שאלה 3 · ירושה, הרשאות גישה והמרות טיפוס

נתונות שתי המחלקות `Flower` ו- `Rose`:

Java:

public class Flower
{
  protected int height;
  private int price;
  public Flower (int val) { this.height = val; this.price = 10;}
  public int getHeight() { return this.height; }
  public int getPrice () { return this.price; }
}
public class Rose extends Flower
{
  private String color;
  public Rose(int val, String col)
    {
         super(val);
         this.color=col;
    }
  public boolean validHeight()
    {
        return this.height > 10 && this.height < 30;
    }
}

C#:

public class Flower
{
  protected int height;
  private int price;
  public Flower (int val) { this.height = val; this.price = 10;}
  public int GetHeight() { return this.height; }
  public int GetPrice () { return this.price; }
}
public class Rose : Flower
{
  private string color;
  public Rose(int val, string col): base(val)
    {
         this.color=col;
    }
  public bool ValidHeight()
    {
        return this.height > 10 && this.height < 30;
    }
}
א.

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

1. המחלקה Flower יורשת את הפעולה `validHeight()` מהמחלקה Rose.

2. המחלקה Rose יורשת את כל התכונות ואת כל הפעולות של המחלקה Flower.

3. המחלקה Rose יכולה לגשת ישירות לתכונה `height` של המחלקה Flower.

4. המחלקה Flower יכולה לגשת לתכונה `color` של המחלקה Rose.

5. לעצמים מטיפוס Rose אין תכונה `price`.

(5 נקודות)
ב.

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

Java:

Flower   first = new Rose (20, "RED");
Flower   second = new Flower (93);

C#:

Flower   first = new Rose (20, "RED");
Flower   second = new Flower (93);

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

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

Java:

1. boolean b = first. validHeight();
2. boolean b = second. validHeight();
3. boolean b = ((Rose)first). validHeight();
4. boolean b = ((Rose)second). validHeight();
5. boolean b = first.getPrice() == second.price;

C#:

1. bool b = first. ValidHeight();
2. bool b = second. ValidHeight();
3. bool b = ((Rose)first). ValidHeight();
4. bool b = ((Rose)second). ValidHeight();
5. bool b = first.GetPrice() == second.price;
(5 נקודות)
ג.

כתבו פעולה המקבלת מערך עצמים מטיפוס `Object`. על הפעולה להדפיס כמה עצמים הם מטיפוס Rose, כמה עצמים מטיפוס Flower ואינו מטיפוס Rose וכמה עצמים הם לא מטיפוס Flower.

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

סעיף א

תשובה:

1 - לא נכון; 2 - נכון; 3 - נכון; 4 - לא נכון; 5 - לא נכון.

עקרון: הירושה היא בכיוון אחד בלבד - המחלקה היורשת (`Rose`) מקבלת את מה שיש במחלקת הבסיס (`Flower`), ולא להפך. הרשאת הגישה (`private` / `protected`) קובעת מי יכול לגשת ישירות לתכונה.

1. לא נכון. `Rose` יורשת מ-`Flower` (`extends Flower` / `: Flower`) ולא להפך. הפעולה `validHeight()` מוגדרת רק ב-`Rose`, ו-`Flower` לא מכירה אותה.

2. נכון. זו הגדרת הירושה: עצם מטיפוס `Rose` מכיל את כל התכונות (`height`, `price`) ואת כל הפעולות (`getHeight`, `getPrice`) של `Flower`. התכונה `price` היא `private`, ולכן `Rose` לא ניגשת אליה ישירות - אבל היא קיימת בעצם ונגישה דרך `getPrice()`.

3. נכון. `height` מוגדרת `protected`, ומחלקה יורשת רשאית לגשת ישירות לתכונה `protected` - כך בדיוק עושה `validHeight()` (`this.height > 10`).

4. לא נכון. מחלקת הבסיס אינה מכירה את התכונות שהוגדרו במחלקה היורשת; בנוסף `color` היא `private` של `Rose`.

5. לא נכון. לכל עצם מטיפוס `Rose` יש תכונה `price` (שהתקבלה בירושה, והבנאי של `Flower` נותן לה את הערך 10). היא רק אינה נגישה ישירות מ-`Rose`.

תשובה: 1 - לא נכון; 2 - נכון; 3 - נכון; 4 - לא נכון; 5 - לא נכון.

סעיף ב

תשובה:

1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקינה (`b = true`); 4 - שגיאת ריצה; 5 - שגיאת הידור.

שני כללים:

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

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

כאן `first` הוא הפניה מטיפוס `Flower` לעצם מטיפוס `Rose`, ו-`second` הוא הפניה מטיפוס `Flower` לעצם מטיפוס `Flower`.

1. שגיאת הידור. טיפוס ההפניה `first` הוא `Flower`, ובמחלקה `Flower` אין פעולה `validHeight()` (למרות שהעצם עצמו הוא `Rose`).

2. שגיאת הידור. מאותה סיבה: ל-`Flower` אין פעולה `validHeight()`.

3. תקינה. ההמרה `(Rose)first` עוברת הידור (`Rose` יורשת מ-`Flower`) וגם מצליחה בריצה, כי העצם באמת `Rose`. גובהו 20, ו-10<20<3010<20<30, ולכן `b = true`.

4. שגיאת ריצה. ההידור עובר (המרה מ-`Flower` ל-`Rose` אפשרית עקרונית), אבל בזמן ריצה העצם הוא `Flower` ולא `Rose`, ולכן נזרקת חריגה (`ClassCastException` ב-Java, `InvalidCastException` ב-C#).

5. שגיאת הידור. התכונה `price` מוגדרת `private` במחלקה `Flower`, ולכן אי אפשר לגשת אליה ישירות מהתוכנית הראשית (`second.price`). (הקריאה `first.getPrice()` עצמה תקינה.)

תשובה: 1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקינה; 4 - שגיאת ריצה; 5 - שגיאת הידור.

סעיף ג

תשובה:

שלושה מונים; לכל תא בודקים קודם `instanceof Rose` (`is Rose`), אחרת `instanceof Flower`, אחרת - לא `Flower`; בסוף מדפיסים את שלושת המונים.

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

1. הסדר חשוב: עצם מטיפוס `Rose` הוא גם מטיפוס `Flower` (ירושה), ולכן קודם בודקים אם הוא `Rose`.

2. אם הוא לא `Rose` אבל הוא `Flower` - הוא "`Flower` שאינו `Rose`".

3. אחרת הוא לא מטיפוס `Flower` (כל עצם אחר, וגם תא ריק `null`, שעבורו `instanceof` מחזיר false).

4. בסוף מדפיסים את שלושת המונים. הפעולה עוברת פעם אחת על המערך: O(n)O(n).

Java:

public static void countObjects(Object[] arr)
{
    int countRose = 0, countFlower = 0, countOther = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] instanceof Rose)
            countRose++;
        else if (arr[i] instanceof Flower)
            countFlower++;
        else
            countOther++;
    }
    System.out.println("Rose: " + countRose);
    System.out.println("Flower (not Rose): " + countFlower);
    System.out.println("Not Flower: " + countOther);
}

C#:

public static void CountObjects(Object[] arr)
{
    int countRose = 0, countFlower = 0, countOther = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] is Rose)
            countRose++;
        else if (arr[i] is Flower)
            countFlower++;
        else
            countOther++;
    }
    Console.WriteLine("Rose: " + countRose);
    Console.WriteLine("Flower (not Rose): " + countFlower);
    Console.WriteLine("Not Flower: " + countOther);
}

דוגמה: עבור המערך `{new Rose(20,"RED"), new Flower(5), "abc", new Rose(1,"W")}` יודפס: `Rose: 2`, `Flower (not Rose): 1`, `Not Flower: 1`.

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

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

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

Java:

public interface Dancer{
    void lonelyDance();
    void coupleDance(Dancer d);
}
public interface Singer   {    void sing();  }
public interface Musician {    void play();  }
public class Actor implements Dancer, Singer, Musician
{
    private String name;
    private int age;
    …
}
public class Driver
{
    public static void main(String[] args)
    {
        Actor actor1 = new Actor("Bob", 25);
        Actor actor2 = new Actor("Alice");
        ( *****)
    }
}

C#:

public interface Dancer{
     void LonelyDance();
     void CoupleDance(Dancer d);
}
public interface Singer {      void Sing(); }
public interface Musician {    void Play(); }
public class Actor : Dancer, Singer, Musician
{
     private string name;
     private int age;
     …
}
public class Driver
{
     public static void Main(string[] args)
     {
            Actor actor1 = new Actor("Bob", 25);
            Actor actor2 = new Actor("Alice");
            ( *****)
     }
}
א.

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

(4 נקודות)
ב.

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

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

Java:

(1)   Dancer dancer1 = actor1;
      dancer1. coupleDance (actor2);

(2)   Singer singer2 = new Singer();
      singer2.sing();

(3)   Singer singer3 = new Actor ("Clark",30);
      Dancer dancer3 = (Actor)singer3;

(4)   Singer actor4 = new Actor("Danny");
      actor4.play();

(5)   Dancer actor5 = new Actor("Eddie");
      Singer singer5 = (Singer) actor5 ;
      singer5.sing();

(6)   Musician musician6 = new Actor("Freddie", 45);
      ((Actor) musician6).lonelyDance();
      ((Singer) musician6).sing();

C#:

(1)   Dancer dancer1 = actor1;
      dancer1. CoupleDance (actor2);

(2)   Singer singer2 = new Singer();
      singer2.Sing();

(3)   Singer singer3 = new Actor ("Clark",30);
      Dancer dancer3 = (Actor)singer3;

(4)   Singer actor4 = new Actor("Danny");
      actor4.Play();

(5)   Dancer actor5 = new Actor("Eddie");
      Singer singer5 = (Singer) actor5 ;
      singer5.Sing();

(6)   Musician musician6 = new Actor("Freddie", 45);
      ((Actor) musician6).LonelyDance();
      ((Singer) musician6).Sing();
(6 נקודות)
ג.

(אין קשר לסעיפים א' ו-ב')

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

Java:

public static void main(String[] args)
{
   C c = new A();
   B b1 = (B)(new A());
   B b2 = new D();
   A a = new D();
}

C#:

public static void Main(string[] args)
{
   C c = new A();
   B b1 = (B)(new A());
   B b2 = new D();
   A a = new D();
}

עבור כל אחת מן האפשרויות 1-6, קבעו אם יחס ההורשה בין המחלקות מתאים לקוד של הפעולה `main` הנתונה.

הסבירו את תשובתכם.

1. C יורשת מ- A, B יורשת מ- A, D יורשת מ- A.

2. A יורשת מ- C, B יורשת מ- A, D יורשת מ- A.

3. C יורשת מ- A, B יורשת מ- A, D יורשת מ- B.

4. A יורשת מ- C, C יורשת מ- B, D יורשת מ- A.

5. A יורשת מ- C, B יורשת מ- A, D יורשת מ- B.

6. A יורשת מ- C, B יורשת מ- C, D יורשת מ- C.

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

סעיף א

תשובה:

שני בנאים `Actor(String name, int age)` ו-`Actor(String name)`, ופעולות `public` לכל פעולות הממשקים: `lonelyDance()`, `coupleDance(Dancer d)`, `sing()`, `play()`.

מה חסר:

1. בנאים: בפעולה הראשית נוצרים עצמים בשתי צורות - `new Actor("Bob", 25)` ו-`new Actor("Alice")` - ולכן צריך שני בנאים: אחד המקבל שם וגיל ואחד המקבל שם בלבד.

2. פעולות הממשקים: מחלקה (לא מופשטת) המממשת ממשק חייבת לממש את כל הפעולות שלו, וכ-`public`. `Actor` מממשת שלושה ממשקים, ולכן חסרות ארבע פעולות: `lonelyDance` ו-`coupleDance` מ-`Dancer`, `sing` מ-`Singer`, `play` מ-`Musician`.

Java:

public class Actor implements Dancer, Singer, Musician
{
    private String name;
    private int age;

    public Actor(String name, int age)   // בנאי: new Actor("Bob", 25)
    public Actor(String name)            // בנאי: new Actor("Alice")
    public void lonelyDance()            // מהממשק Dancer
    public void coupleDance(Dancer d)    // מהממשק Dancer
    public void sing()                   // מהממשק Singer
    public void play()                   // מהממשק Musician
}

C#:

public class Actor : Dancer, Singer, Musician
{
    private string name;
    private int age;

    public Actor(string name, int age)   // בנאי: new Actor("Bob", 25)
    public Actor(string name)            // בנאי: new Actor("Alice")
    public void LonelyDance()            // מהממשק Dancer
    public void CoupleDance(Dancer d)    // מהממשק Dancer
    public void Sing()                   // מהממשק Singer
    public void Play()                   // מהממשק Musician
}

תשובה: שני בנאים ו-4 הפעולות של הממשקים, כמפורט למעלה.

סעיף ב

תשובה:

1 - תקין; 2 - שגיאת קומפילציה; 3 - תקין; 4 - שגיאת קומפילציה; 5 - תקין; 6 - תקין.

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

1. תקין. `Actor` מממשת את `Dancer`, ולכן אפשר להציב את `actor1` בהפניה מטיפוס `Dancer`. הפעולה `coupleDance` קיימת ב-`Dancer`, והפרמטר `actor2` הוא `Actor`, כלומר גם `Dancer`.

2. שגיאת קומפילציה. `Singer` הוא ממשק, ואי אפשר ליצור ממנו עצם (`new Singer()`).

3. תקין. עצם `Actor` מוצב בהפניה מטיפוס `Singer`. ההמרה `(Actor)singer3` עוברת הידור, ובריצה העצם הוא באמת `Actor`; ו-`Actor` מממשת את `Dancer`, ולכן ההצבה ל-`dancer3` תקינה.

4. שגיאת קומפילציה. ההפניה `actor4` היא מטיפוס `Singer`, ובממשק `Singer` אין פעולה `play()` (למרות שהעצם עצמו הוא `Actor`).

5. תקין. ההמרה מ-`Dancer` ל-`Singer` מותרת בהידור (המרה לממשק), ובריצה העצם הוא `Actor` שמממש את `Singer`, ולכן ההמרה מצליחה ו-`sing()` מתבצעת.

6. תקין. העצם הוא `Actor`; ההמרה `(Actor) musician6` מצליחה ו-`lonelyDance()` קיימת ב-`Actor`; גם ההמרה `(Singer) musician6` מצליחה, כי `Actor` מממשת את `Singer`.

תשובה: 1 - תקין; 2 - שגיאת קומפילציה; 3 - תקין; 4 - שגיאת קומפילציה; 5 - תקין; 6 - תקין.

סעיף ג

תשובה:

רק יחס ההורשה 4 מתאים לקוד (A יורשת מ-C, C יורשת מ-B, D יורשת מ-A); כל האחרים אינם מתאימים.

מה כל שורה דורשת:

1. `C c = new A();` - עצם `A` מוצב בהפניה מטיפוס `C`, ולכן A חייבת לרשת (ישירות או בעקיפין) מ-C.

2. `B b1 = (B)(new A());` - ההמרה תעבור הידור רק אם יש קשר ירושה בין A ל-B, ותצליח בזמן ריצה רק אם העצם (`new A()`) הוא באמת `B`, כלומר A חייבת לרשת מ-B.

3. `B b2 = new D();` - D חייבת לרשת מ-B.

4. `A a = new D();` - D חייבת לרשת מ-A.

בדיקת האפשרויות:

1. לא מתאים. C יורשת מ-A ולא A מ-C, ולכן `C c = new A()` היא שגיאת הידור. (גם D אינה `B`.)

2. לא מתאים. D יורשת מ-A ולא מ-B, ולכן `B b2 = new D()` היא שגיאת הידור. (בנוסף B יורשת מ-A ולא להפך, ולכן ההמרה `(B)(new A())` תיכשל בזמן ריצה.)

3. לא מתאים. C יורשת מ-A ולא A מ-C, ולכן `C c = new A()` היא שגיאת הידור.

4. מתאים. B היא מחלקת הבסיס, C יורשת ממנה, A יורשת מ-C ו-D יורשת מ-A. לכן A היא גם C וגם B, ו-D היא A, C ו-B. כל ארבע השורות תקינות, וההמרה `(B)(new A())` היא המרה כלפי מעלה שמצליחה תמיד.

5. לא מתאים. B יורשת מ-A ולא A מ-B: הקוד עובר הידור, אבל `(B)(new A())` גורמת לשגיאת זמן ריצה, כי עצם מטיפוס `A` אינו `B`.

6. לא מתאים. A ו-B הן "אחיות" (שתיהן יורשות מ-C) ואין ביניהן קשר ירושה, ולכן `(B)(new A())` היא שגיאת הידור. בנוסף D אינה `B` ואינה `A`.

תשובה: רק אפשרות 4 מתאימה; 1, 2, 3, 5, 6 אינן מתאימות.

שאלה 5 · בניית רשימת תדירויות בשרשרת חוליות

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

רשימת תדירויות (Frequency List) היא רשימה של מספרים שלמים שבה כל מספר מופיע __פעם אחת__ ולאחריו מספר הפעמים שהופיע ברשימה המקורית.

א.

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

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

יש למחוק ערכים שחוזרים על עצמם חוץ מהמופע הראשון.

אין להשתמש במבני נתונים נוספים!!!

לדוגמה:

הרשימה המקורית: 100, 40, 20, 100, 100, 20, 30, 20, 20

•מספר 100 מופיע שלוש פעמים.

•מספר 40 מופיע פעם אחת.

•מספר 20 מופיע ארבע פעמים.

•מספר 30 מופיע פעם אחת.

הרשימה אחרי העדכון (רשימת תדירויות): 100, 3, 40, 1, 20, 4, 30, 1

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

Java:

public static void buildFreqList(Node<Integer> chain)

C#:

public static void BuildFreqList(Node<int> chain)
(7 נקודות)
ב.

כתבו פעולה המקבלת הפניה לחוליה ראשונה של שרשרת חוליות ומחזירה את המספר __המופיע הכי הרבה__ פעמים בשרשרת. בעבור הרשימה הנתונה בסעיף א' הפעולה תחזיר 20.

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

Java:

public static int mostPopularNumber(Node<Integer> chain)

C#:

public static int MostPopularNumber(Node<int> chain)

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

(7 נקודות)
ג.

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

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

סעיף א

תשובה:

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

הרעיון: עוברים על הרשימה עם מצביע `pos`. בכל שלב `pos` מצביע על ערך שמופיע כאן בפעם הראשונה (כל המופעים הקודמים שלו כבר נמחקו).

1. שומרים `num = pos.getValue()` ומאתחלים `count = 1`.

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

•אם בחוליה הבאה יש `num` - מגדילים את `count` ומוחקים אותה (`prev` לא זז, כי החוליה הבאה החדשה עוד לא נבדקה).

•אחרת `prev` מתקדם.

3. יוצרים חוליה חדשה עם הערך `count` ומשרשרים אותה מיד אחרי `pos`. (חוליה חדשה היא חלק מהרשימה עצמה ולא מבנה נתונים נוסף.)

4. מקדמים את `pos` אל החוליה שאחרי חוליית המונה - הערך החדש הבא.

Java:

public static void buildFreqList(Node<Integer> chain)
{
    Node<Integer> pos = chain;
    while (pos != null)
    {
        int num = pos.getValue();
        int count = 1;
        Node<Integer> prev = pos;              // סורקים את המשך הרשימה
        while (prev.hasNext())
        {
            if (prev.getNext().getValue() == num)
            {
                count++;                       // מוחקים את המופע החוזר
                prev.setNext(prev.getNext().getNext());
            }
            else
                prev = prev.getNext();
        }
        Node<Integer> freq = new Node<Integer>(count, pos.getNext());
        pos.setNext(freq);                     // חוליית התדירות אחרי הערך
        pos = freq.getNext();                  // עוברים לערך הבא
    }
}

C#:

public static void BuildFreqList(Node<int> chain)
{
    Node<int> pos = chain;
    while (pos != null)
    {
        int num = pos.GetValue();
        int count = 1;
        Node<int> prev = pos;              // סורקים את המשך הרשימה
        while (prev.HasNext())
        {
            if (prev.GetNext().GetValue() == num)
            {
                count++;                       // מוחקים את המופע החוזר
                prev.SetNext(prev.GetNext().GetNext());
            }
            else
                prev = prev.GetNext();
        }
        Node<int> freq = new Node<int>(count, pos.GetNext());
        pos.SetNext(freq);                     // חוליית התדירות אחרי הערך
        pos = freq.GetNext();                  // עוברים לערך הבא
    }
}

מעקב על הדוגמה:

`num`מופעים שנמחקו`count`הרשימה אחרי השלב
10023100, 3, 40, 20, 20, 30, 20, 20
4001100, 3, 40, 1, 20, 20, 30, 20, 20
2034100, 3, 40, 1, 20, 4, 30
3001100, 3, 40, 1, 20, 4, 30, 1

תשובה: הפעולה שלמעלה; בדוגמה מתקבלת הרשימה `100, 3, 40, 1, 20, 4, 30, 1`.

סעיף ב

תשובה:

מזמנים את `buildFreqList(chain)` ואז עוברים על הזוגות (ערך, מונה) בקפיצות של שתי חוליות ושומרים את הערך שהמונה שלו מקסימלי.

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

1. מזמנים `buildFreqList(chain)`. `chain` עדיין מצביע על החוליה הראשונה, כי הערך הראשון לעולם לא נמחק.

2. מאתחלים את המקסימום מהזוג הראשון: `maxNum` הוא הערך ו-`maxCount` הוא המונה שאחריו.

3. עוברים על שאר הזוגות: `pos` מצביע על ערך, `pos.getNext()` על המונה שלו, והמעבר לזוג הבא הוא `pos.getNext().getNext()`.

4. אם המונה גדול מ-`maxCount` - מעדכנים את `maxCount` ואת `maxNum`. (בתיקו נשאר המספר שהופיע ראשון.)

Java:

public static int mostPopularNumber(Node<Integer> chain)
{
    buildFreqList(chain);
    int maxNum = chain.getValue();
    int maxCount = chain.getNext().getValue();
    Node<Integer> pos = chain.getNext().getNext();   // הזוג השני
    while (pos != null)
    {
        int count = pos.getNext().getValue();
        if (count > maxCount)
        {
            maxCount = count;
            maxNum = pos.getValue();
        }
        pos = pos.getNext().getNext();
    }
    return maxNum;
}

C#:

public static int MostPopularNumber(Node<int> chain)
{
    BuildFreqList(chain);
    int maxNum = chain.GetValue();
    int maxCount = chain.GetNext().GetValue();
    Node<int> pos = chain.GetNext().GetNext();   // הזוג השני
    while (pos != null)
    {
        int count = pos.GetNext().GetValue();
        if (count > maxCount)
        {
            maxCount = count;
            maxNum = pos.GetValue();
        }
        pos = pos.GetNext().GetNext();
    }
    return maxNum;
}

בדיקה על הדוגמה: רשימת התדירויות היא `100, 3, 40, 1, 20, 4, 30, 1`. המונים: 3, 1, 4, 1. המקסימום 4 שייך ל-20, והפעולה מחזירה 20.

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

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

סעיף ג

תשובה:

שתיהן O(n2)O(n^2), כאשר nn מספר האיברים ברשימה המקורית.

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

1. `buildFreqList`: לכל ערך שונה סורקים את כל המשך הרשימה. במקרה הגרוע (כל הערכים שונים) הסריקות הן באורך n−1,n−2,…,1n-1, n-2, \ldots, 1, ובסך הכול

(n−1)+(n−2)+…+1=n(n−1)2(n-1)+(n-2)+\ldots+1=\frac{n(n-1)}{2}

פעולות - סכום של סדרה חשבונית, כלומר O(n2)O(n^2).

2. `mostPopularNumber`: מזמנת את `buildFreqList` (O(n2)O(n^2)) ואחר כך עוברת פעם אחת על רשימת התדירויות, שאורכה לכל היותר 2n2n (O(n)O(n)). בסך הכול O(n2)+O(n)=O(n2)O(n^2)+O(n)=O(n^2).

תשובה: `buildFreqList` - O(n2)O(n^2); `mostPopularNumber` - O(n2)O(n^2).

שאלה 6 · מערכת ניהול מלון: ירושה ורב-צורתיות

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

מערכת ניהול המלון כוללת ארבע מחלקות: `Room`, `FamilyRoom`, `Suite`, `Hotel`.

לחדר רגיל (`Room`) יש את התכונות הבאות:

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

•`beds` – מספר המיטות, מטיפוס שלם, `int`

•`price` – מחיר, מטיפוס ממשי, `double`

לחדר משפחה (`FamilyRoom`) יש את התכונות הבאות:

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

•`beds` – מספר המיטות, מטיפוס שלם, `int`

•`price` – מחיר, מטיפוס ממשי, `double`

•`babyBed` – האם נוספה מיטת תינוק, מטיפוס `boolean` (`true` – כן נוספה מיטה, `false` – לא)

•`balcony` – האם יש מרפסת, מטיפוס `boolean` (`true` – יש, `false` – אין)

לסוויטה (`Suite`) יש את התכונות הבאות:

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

•`beds` – מספר המיטות, מטיפוס שלם, `int`

•`price` – מחיר, מטיפוס ממשי, `double`

•`jacuzzi` – האם יש ג'קוזי, מטיפוס `boolean` (`true` – יש, `false` – אין)

א.

סרטטו תרשים UML המתאר את הקשר בין המחלקות: `Room`, `FamilyRoom`, `Suite` באופן __המתאים ביותר לעקרונות של תכנות מונחה עצמים__.

(2 נקודות)
ב.

לכל אחת מהמחלקות `Room`, `FamilyRoom`, `Suite` כתבו כותרת המחלקה ותכונות שלה.

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

(3 נקודות)
ג.

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

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

•החלפת מצעים למיטה אחת – חמש דקות,

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

•ניקוי מרפסת – חמש דקות

•קיפול והוצאת מיטת תינוק – חמש דקות

•ניקוי ג'קוזי – עשרים דקות

•שאיבת שטיחים – חמש עשרה דקות

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

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

(6 נקודות)
ד.

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

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

(1 נקודות)
ה.

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

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

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

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

Java:

public int totalTime(int[] numArr)

C#:

public int TotalTime(int[] numArr)
(6 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

`Room` היא מחלקת הבסיס; `FamilyRoom` ו-`Suite` יורשות ממנה (חץ ירושה מכל אחת מהן אל `Room`).

הרעיון: לשלושת סוגי החדרים יש את אותן שלוש תכונות משותפות: `num`, `beds`, `price`. לחדר משפחה ולסוויטה יש בנוסף תכונות משלהם. לכן לפי עקרון הירושה (מניעת שכפול קוד):

1. `Room` (חדר רגיל) היא מחלקת הבסיס ובה שלוש התכונות המשותפות.

2. `FamilyRoom` יורשת מ-`Room` ומוסיפה את `babyBed` ו-`balcony`.

3. `Suite` יורשת מ-`Room` ומוסיפה את `jacuzzi`.

בתרשים: שלוש מלבנים (מחלקות); מ-`FamilyRoom` ומ-`Suite` יוצאים קווים שמתאחדים לחץ ירושה (חץ עם ראש משולש) המצביע אל `Room`. אפשר לרשום בכל מלבן את התכונות שלו:

•`Room`: `num : int`, `beds : int`, `price : double`

•`FamilyRoom`: `babyBed : boolean`, `balcony : boolean`

•`Suite`: `jacuzzi : boolean`

תשובה: `FamilyRoom` ו-`Suite` יורשות מ-`Room`.

סעיף ב

תשובה:

`Room` עם `num`, `beds`, `price`; `FamilyRoom extends Room` עם `babyBed`, `balcony`; `Suite extends Room` עם `jacuzzi`. כל התכונות `private`.

לפי התרשים מסעיף א': התכונות המשותפות מוגדרות רק ב-`Room`, וכל מחלקה יורשת מגדירה רק את התכונות הנוספות שלה. התכונות `private` (כימוס), והגישה אליהן דרך פעולות `get/set`.

Java:

public class Room
{
    private int num;          // מספר חדר
    private int beds;         // מספר המיטות
    private double price;     // מחיר
}

public class FamilyRoom extends Room
{
    private boolean babyBed;  // האם נוספה מיטת תינוק
    private boolean balcony;  // האם יש מרפסת
}

public class Suite extends Room
{
    private boolean jacuzzi;  // האם יש ג'קוזי
}

C#:

public class Room
{
    private int num;          // מספר חדר
    private int beds;         // מספר המיטות
    private double price;     // מחיר
}

public class FamilyRoom : Room
{
    private bool babyBed;  // האם נוספה מיטת תינוק
    private bool balcony;  // האם יש מרפסת
}

public class Suite : Room
{
    private bool jacuzzi;  // האם יש ג'קוזי
}

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

סעיף ג

תשובה:

פעולה `cleaningTime()` בכל שלוש המחלקות: ב-`Room`: `5*beds + 10`; ב-`FamilyRoom` (דריסה): זמן `Room` ועוד 5 למרפסת ועוד 5 למיטת תינוק (אם יש); ב-`Suite` (דריסה): זמן `Room` ועוד 10 (ריצפה 20), ועוד 20 לג'קוזי (אם יש), ועוד 15 לשטיחים.

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

1. במחלקה `Room` (חדר רגיל): מצעים לכל מיטה - `5 * beds` דקות, ועוד 10 דקות לשטיפת ריצפה וניקוי אבק.

2. במחלקה `FamilyRoom`: מתחילים מהזמן של חדר רגיל (`super.cleaningTime()`) - מצעים ו-10 דקות ריצפה. מוסיפים 5 דקות אם יש מרפסת (`balcony`), ו-5 דקות אם יש מיטת תינוק (`babyBed`).

3. במחלקה `Suite`: בסוויטה הריצפה והאבק לוקחים 20 דקות במקום 10, ולכן לזמן של חדר רגיל מוסיפים 10. מוסיפים 20 דקות אם יש ג'קוזי, ותמיד 15 דקות לשאיבת שטיחים.

Java:

// במחלקה Room
public int cleaningTime()
{
    return this.beds * 5 + 10;       // מצעים לכל מיטה + שטיפת ריצפה וניקוי אבק
}

// במחלקה FamilyRoom
public int cleaningTime()
{
    int t = super.cleaningTime();    // מצעים + ריצפה, כמו בחדר רגיל
    if (this.balcony)
        t += 5;                      // ניקוי מרפסת
    if (this.babyBed)
        t += 5;                      // קיפול והוצאת מיטת תינוק
    return t;
}

// במחלקה Suite
public int cleaningTime()
{
    int t = super.cleaningTime() + 10; // ריצפה ואבק בסוויטה: 20 דקות במקום 10
    if (this.jacuzzi)
        t += 20;                       // ניקוי ג'קוזי
    t += 15;                           // שאיבת שטיחים
    return t;
}

C#:

// במחלקה Room
public virtual int CleaningTime()
{
    return this.beds * 5 + 10;       // מצעים לכל מיטה + שטיפת ריצפה וניקוי אבק
}

// במחלקה FamilyRoom
public override int CleaningTime()
{
    int t = base.CleaningTime();    // מצעים + ריצפה, כמו בחדר רגיל
    if (this.balcony)
        t += 5;                      // ניקוי מרפסת
    if (this.babyBed)
        t += 5;                      // קיפול והוצאת מיטת תינוק
    return t;
}

// במחלקה Suite
public override int CleaningTime()
{
    int t = base.CleaningTime() + 10; // ריצפה ואבק בסוויטה: 20 דקות במקום 10
    if (this.jacuzzi)
        t += 20;                       // ניקוי ג'קוזי
    t += 15;                           // שאיבת שטיחים
    return t;
}

דוגמאות:

•חדר רגיל עם 2 מיטות: 5⋅2+10=205\cdot2+10=20 דקות.

•חדר משפחה עם 4 מיטות, מרפסת ומיטת תינוק: 5⋅4+10+5+5=405\cdot4+10+5+5=40 דקות.

•סוויטה עם 2 מיטות וג'קוזי: 5⋅2+20+20+15=655\cdot2+20+20+15=65 דקות.

תשובה: הפעולה `cleaningTime()` ב-`Room`, ודריסה שלה ב-`FamilyRoom` וב-`Suite`, כמו בקוד שלמעלה.

סעיף ד

תשובה:

`public class Hotel { private Room[] rooms; }` - מערך מטיפוס `Room` שיכול להכיל גם `FamilyRoom` וגם `Suite`.

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

Java:

public class Hotel
{
    private Room[] rooms;     // מערך חדרי המלון
}

C#:

public class Hotel
{
    private Room[] rooms;     // מערך חדרי המלון
}

תשובה: `private Room[] rooms;` במחלקה `Hotel`.

סעיף ה

תשובה:

לכל מספר חדר ב-`numArr` מחפשים במערך החדרים את החדר עם אותו מספר, מוסיפים את `cleaningTime()` שלו לסכום, ואם הוא `FamilyRoom` עם מיטת תינוק מגדילים מונה; בסוף מדפיסים את המונה ומחזירים את הסכום.

הרעיון:

1. עוברים על מספרי החדרים שבמערך `numArr`.

2. לכל מספר מחפשים במערך `rooms` את החדר שמספרו (`getNum()`) שווה לו.

3. מוסיפים לסכום את `cleaningTime()` של החדר. בזכות הדריסה מסעיף ג' מופעלת אוטומטית הגרסה של סוג החדר (רגיל / משפחה / סוויטה).

4. אם החדר הוא חדר משפחה (`instanceof FamilyRoom`, ב-C#: `is FamilyRoom`), ממירים אותו ל-`FamilyRoom` ובודקים אם יש בו מיטת תינוק (`getBabyBed()`). אם כן - מגדילים את מונה מיטות התינוק.

5. בסוף מדפיסים את מספר מיטות התינוק ומחזירים את הזמן הכולל.

`getNum()` ו-`getBabyBed()` הן פעולות ה-`get` שמותר להניח שקיימות.

Java:

public int totalTime(int[] numArr)
{
    int time = 0;
    int babyBeds = 0;
    for (int i = 0; i < numArr.length; i++)
    {
        for (int j = 0; j < this.rooms.length; j++)
        {
            if (this.rooms[j].getNum() == numArr[i])
            {
                time += this.rooms[j].cleaningTime();   // שיגור דינמי לפי סוג החדר
                if (this.rooms[j] instanceof FamilyRoom &&
                    ((FamilyRoom) this.rooms[j]).getBabyBed())
                    babyBeds++;
            }
        }
    }
    System.out.println("Baby beds: " + babyBeds);
    return time;
}

C#:

public int TotalTime(int[] numArr)
{
    int time = 0;
    int babyBeds = 0;
    for (int i = 0; i < numArr.Length; i++)
    {
        for (int j = 0; j < this.rooms.Length; j++)
        {
            if (this.rooms[j].GetNum() == numArr[i])
            {
                time += this.rooms[j].CleaningTime();   // שיגור דינמי לפי סוג החדר
                if (this.rooms[j] is FamilyRoom &&
                    ((FamilyRoom) this.rooms[j]).GetBabyBed())
                    babyBeds++;
            }
        }
    }
    Console.WriteLine("Baby beds: " + babyBeds);
    return time;
}

דוגמה: אם יתפנו חדר רגיל עם 2 מיטות (20 דקות), חדר משפחה עם 4 מיטות, מרפסת ומיטת תינוק (40 דקות) וסוויטה עם 2 מיטות וג'קוזי (65 דקות), יודפס `Baby beds: 1` והפעולה תחזיר 20+40+65=12520+40+65=125 דקות.

סיבוכיות: לכל אחד מ-mm מספרי החדרים סורקים את nn חדרי המלון: O(m⋅n)O(m\cdot n).

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

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

א.

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

Java:

public static  boolean special(BinNode<Integer> t)
 {
     return special(t, 0);
 }
private static  boolean special(BinNode<Integer> t, int r)
 {
    if (t==null)
          return true;
    if (t.getValue()<r)
          return false;
   return special(t.getLeft(), r+1) && special(t.getRight(), r+1);
}

C#:

public static  bool Special(BinNode<int> t)
 {
     return Special(t, 0);
 }
private static  bool Special(BinNode<int> t, int r)
 {
    if (t==null)
          return true;
    if (t.GetValue()<r)
          return false;
   return Special(t.GetLeft(), r+1) && Special(t.GetRight(), r+1);
}

תנו דוגמה לעץ המכיל לפחות שישה איברים שעבורו תחזיר הפעולה `special(t)` את הערך `true`.

(5 נקודות)
ב.

מהי מטרת הפעולה `special`?

(4 נקודות)
ג.

נתונות שתי פעולות המקבלות הפנייה לשורש של עץ חיפוש בינרי (Binary Search Tree):

Java:

public static int what(BinNode<Integer> bt)
{
    if(bt.getLeft() == null)
        return bt.getValue();
    return what(bt.getLeft());
}

public static int where(BinNode<Integer> bt)
{
    while(bt.getRight()!=null)
    {
        bt = bt.getRight();
    }
    return bt.getValue();
}

C#:

public static int What(BinNode<int> bt)
{
    if(bt.GetLeft() == null)
        return bt.GetValue();
    return What(bt.GetLeft());
}

public static int Where(BinNode<int> bt)
{
    while(bt.GetRight()!=null)
    {
        bt = bt.GetRight();
    }
    return bt.GetValue();
}

מהן מטרות הפעולות `what` ו-`where`?

(4 נקודות)
ד.

האם קיים עץ חיפוש בינרי `bt` הכולל לפחות שלושה צמתים שעבורו מתקיים:

`what(bt) = where(bt)`?

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

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

סעיף א

תשובה:

לדוגמה: שורש 12; בנים 8 (שמאלי) ו-15 (ימני); ל-8 בן ימני 17; ל-15 בן ימני 9; ל-9 בן שמאלי 10. כל ערך גדול או שווה לרמה שלו, ולכן מוחזר `true`.

מה הפעולה בודקת: הפרמטר `r` הוא הרמה של הצומת: השורש נבדק עם `r = 0`, ובכל ירידה לבן `r` גדל ב-1. הפעולה מחזירה `false` אם בצומת כלשהו הערך קטן מהרמה שלו, ו-`true` אם כל הצמתים עברו את הבדיקה (עץ ריק מחזיר `true`).

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

דוגמה (העץ באיור):

צומתמיקוםרמה `r`בדיקה `value < r`
12שורש0`12 < 0` לא
8בן שמאלי של 121`8 < 1` לא
15בן ימני של 121`15 < 1` לא
17בן ימני של 82`17 < 2` לא
9בן ימני של 152`9 < 2` לא
10בן שמאלי של 93`10 < 3` לא

לאף צומת הבדיקה לא מתקיימת, וכל הקריאות על בנים ריקים (`null`) מחזירות `true`; לכן `special(t)` מחזירה `true`.

תשובה: העץ שבאיור (12; 8, 15; 17, 9; 10) - כל ערך גדול או שווה לרמה שלו.

סעיף ב

תשובה:

הפעולה מחזירה `true` אם ערך כל צומת בעץ גדול או שווה לרמה שבה הוא נמצא (השורש ברמה 0), ו-`false` אחרת.

1. הפעולה הציבורית `special(t)` מזמנת את פעולת העזר עם `r = 0` - הרמה של השורש.

2. בפעולת העזר: עץ ריק מקיים את התנאי (`true`). אם ערך הצומת קטן מ-`r` - מוחזר `false`. אחרת ממשיכים לשני תתי-העצים עם `r + 1`, כי הבנים נמצאים רמה אחת מתחת, והתוצאה היא "וגם" של שניהם.

3. לכן מוחזר `true` רק אם בכל הצמתים מתקיים: ערך הצומת ≥\ge הרמה שלו.

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

סעיף ג

תשובה:

`what` מחזירה את הערך הקטן ביותר בעץ (הצומת השמאלי ביותר); `where` מחזירה את הערך הגדול ביותר בעץ (הצומת הימני ביותר).

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

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

2. `where` (בלולאה) מתקדמת שוב ושוב לבן הימני, עד צומת שאין לו בן ימני, ומחזירה את ערכו - הצומת הימני ביותר, כלומר הערך הגדול ביותר בעץ.

תשובה: `what` מחזירה את המספר הקטן ביותר בעץ, ו-`where` מחזירה את המספר הגדול ביותר בעץ.

סעיף ד

תשובה:

כן - כשכל הערכים בעץ שווים, למשל שרשרת של שלושה צמתים עם הערך 1, כל אחד בן ימני של קודמו: `what = where = 1`.

1. לפי סעיף ג', `what(bt)` הוא הערך הקטן ביותר בעץ ו-`where(bt)` הוא הגדול ביותר. הם שווים רק אם כל הערכים בעץ שווים.

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

3. בדיקה: לשורש אין בן שמאלי, ולכן `what(bt)` מחזירה מיד 1. `where(bt)` יורדת ימינה עד הצומת השלישי ומחזירה 1. כלומר `what(bt) = where(bt) = 1`.

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

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

שאלה 8 · מעקב אחר ירושה, דריסה ומונים סטטיים

נתונות שתי המחלקות הבאות:

Java:

public class A {
    public static int countA = 0;
    private String st;
    public A() { this.st = "aaa"; countA++;}
    public A(String st) { this.st = st; countA++;}
    public String toString() { return this.st; }
    public boolean same (Object obj) {
        if ((obj instanceof A) && (((A)obj).st.equals(this.st)))
            return true;
        return false;
    }
}     //end of class A

public class B extends A {
    public static int countB = 0;
    private int num;
    public B() {
        super();
        this.num = 1;
        countB++;
    }
    public B(int num) {
        super();
        this.num = num;
        countB++;
    }
    public B(int num, String st) {
        super(st);
        this.num = Math.abs(num);
        countB++;
    }
    public String toString() {
        String s = this.num +"/";
        for(int i = 0; i< this.num; i++)
            s+=super.toString();
        return s;
    }
    public boolean same (Object obj) {
        if ((obj instanceof B) && (((B)obj).num == this.num))
            return true;
        return false;
    }
} //end of class B

C#:

using System;

public class A {
    public static int countA = 0;
    private string st;
    public A() { this.st = "aaa"; countA++;}
    public A(string st) { this.st = st; countA++;}
    public override string ToString() { return this.st; }
    public virtual bool Same (Object obj) {
         if ((obj is A) && (((A)obj).st.Equals(this.st)))
             return true;
         return false;
    }
}     //end of class A

public class B : A {
    public static int countB = 0;
    private int num;
    public B(): base() {
        this.num = 1;
        countB++;
    }
    public B(int num): base() {
        this.num = num;
        countB++;
    }
    public B(int num, string st): base(st) {
        this.num = Math.Abs(num);
        countB++;
    }
    public override string ToString() {
        string s = this.num +"/";
        for(int i = 0; i< this.num; i++)
            s+= base.ToString();
        return s;
    }
    public override bool Same (Object obj) {
        if ((obj is B) && (((B)obj).num == this.num))
            return true;
        return false;
    }
} //end of class B
א.

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

Java:

A a = new A();
B b = new B();
if (a.same (b))
     System.out.println (a);
else
     System.out.println (b);
if (b.same(a))
     System.out.println (b);
else
     System.out.println (a);

C#:

A a = new A();
B b = new B();
if (a.Same(b))
    Console.WriteLine (a);
else
    Console.WriteLine (b);
if (b.Same(a))
     Console.WriteLine (b);
else
    Console.WriteLine (a);

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

(4 נקודות)
ב.

נתונה המחלקה `Tester` הבאה:

Java:

public class Tester {
    public static void print (Object[] arr)
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i] != null)
            {
                if (arr[i] instanceof B)
                    System.out.println("B: " + arr[i]);
                else if (arr[i] instanceof A)
                       System.out.println("A: " + arr[i]);
                     else
                       System.out.println("Unknown");
            }
            else
             System.out.println("NULL");
        }
    }
    public static void main (String[] args)
    {
        A[] ar1 = new A[7];
        ar1[0] = new B(-4);
        ar1[1] = new A("bbb");
        ar1[2] = new B(3,"ccc");
        ar1[3] = new B();
        ar1[4] = new B(2, "ddd");
        ar1[5] = new A();
        print(ar1);
        System.out.println(A.countA+ " "+ B.countB);
    }
} //end of class Tester

C#:

using System;

public class Tester {
     public static void Print (Object[] arr)
     {
          for (int i = 0; i < arr.Length; i++)
          {
                if (arr[i] != null)
                {
                       if (arr[i] is B)
                             Console.WriteLine("B: " + arr[i]);
                       else if (arr[i] is A)
                                Console.WriteLine("A: " + arr[i]);
                              else
                                Console.WriteLine("Unknown");
                }
                else
                  Console.WriteLine("NULL");
          }
     }
     public static void Main (String[] args)
     {
          A[] ar1 = new A[7];
          ar1[0] = new B(-4);
          ar1[1] = new A("bbb");
          ar1[2] = new B(3,"ccc");
          ar1[3] = new B();
          ar1[4] = new B(2, "ddd");
          ar1[5] = new A();
          Print(ar1);
          Console.WriteLine(A.countA+ " "+ B.countB);
     }
} //end of class Tester

עקבו אחרי ביצוע תוכנית הראשית (`main`) ורשמו מה יהיה פלט התוכנית. יש להציג את התכונות של כל העצמים שנוצרו במהלך ביצוע התוכנית.

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

סעיף א

תשובה:

יודפס `aaa` ובשורה הבאה `aaa`.

1. `a` הוא עצם `A` עם `st = "aaa"`. `b` הוא עצם `B` שנבנה ב-`B()`: הבנאי מזמן את `A()` ולכן `st = "aaa"`, ו-`num = 1`.

2. `a.same(b)`: `a` הוא עצם מטיפוס `A`, ולכן מופעלת הפעולה `same` של `A`. `b` הוא `instanceof A` (כי `B` יורשת מ-`A`), ו-`st` של `b` הוא `"aaa"` - שווה ל-`st` של `a`. התוצאה `true`, ולכן מודפס `a`, כלומר `a.toString()` = `aaa`.

3. `b.same(a)`: `b` הוא עצם מטיפוס `B`, ולכן מופעלת הגרסה הדורסת של `B`. היא בודקת אם `a` הוא `instanceof B` - והוא לא (עצם `A` אינו `B`). התוצאה `false`, ולכן מתבצע ה-`else` ומודפס `a` - שוב `aaa`.

פלט:

aaa
aaa

תשובה: `aaa` ו-`aaa` (בשתי שורות).

סעיף ב

תשובה:

הפלט: `B: -4/`, `A: bbb`, `B: 3/ccccccccc`, `B: 1/aaa`, `B: 2/dddddd`, `A: aaa`, `NULL`, `6 4`.

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

תאהבנאיטיפוס`st``num``countA``countB`
`ar1[0]``B(-4)`B`"aaa"`-411
`ar1[1]``A("bbb")`A`"bbb"`-21
`ar1[2]``B(3,"ccc")`B`"ccc"`332
`ar1[3]``B()`B`"aaa"`143
`ar1[4]``B(2,"ddd")`B`"ddd"`254
`ar1[5]``A()`A`"aaa"`-64
`ar1[6]`--`null`-64

שימו לב: `B(int num)` אינו מפעיל `Math.abs`, ולכן ב-`ar1[0]` נשמר `num = -4`.

הפעולה `print`: לכל תא, אם הוא `null` מודפס `NULL`; אחרת בודקים קודם `instanceof B` (כי עצם `B` הוא גם `A`) ומדפיסים `"B: "` או `"A: "` ואחריהם את `toString()` של העצם (שיגור דינמי לגרסה של הטיפוס האמיתי).

`toString()` של `B` מחזירה את `num`, לוכסן, ואחריו את `st` משוכפל `num` פעמים (`super.toString()` מחזירה את `st`).

תא`toString()`שורת הפלט
0`-4` ו-`"/"`, הלולאה `i < -4` לא מתבצעת`B: -4/`
1`st``A: bbb`
2`"3/"` ו-`"ccc"` שלוש פעמים`B: 3/ccccccccc`
3`"1/"` ו-`"aaa"` פעם אחת`B: 1/aaa`
4`"2/"` ו-`"ddd"` פעמיים`B: 2/dddddd`
5`st``A: aaa`
6`null``NULL`

לבסוף מודפסים המונים הסטטיים: `countA = 6` (כל ששת העצמים), `countB = 4` (ארבעת עצמי `B`).

פלט:

B: -4/
A: bbb
B: 3/ccccccccc
B: 1/aaa
B: 2/dddddd
A: aaa
NULL
6 4

תשובה: הפלט שלמעלה; בסוף `countA = 6`, `countB = 4`.

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

א.

נתונה הפעולה הרקורסיבית `what` המקבלת תור של מספרים `q` ומספר `x`:

Java:

public  static  int  what (Queue<Integer> q , int x)
{
  if ( q.isEmpty() || x != q.head() )
          return 0;
    x = q.remove();
    return   1 + what(q , x);
}

C#:

public static int What (Queue<int> q , int x)
{
  if ( q.IsEmpty() || x != q.Head() )
          return 0;
    x = q.Remove();
    return   1 + What(q , x);
}
(1)

מה יחזיר זימון הפעולה `what(q,5)` עבור התור `q:[5,5,5,3,3,2,8]` (5 בראש התור)?

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

(2)

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

האם הטענה "ערך `x` לא מופיע בתור" נכונה? הסבירו את תשובתכם.

(3)

תנו דוגמה של תור `q` שעבורו זימון הפעולה `what(q, 7)` תחזיר 4. איך ייראה התור אחרי זימון הפעולה?

(4)

מה מבצעת הפעולה ?

(8 נקודות)
ב.

נתונה הפעולה `secret` המקבלת תור של מספרים `q`:

Java:

public  static  int  secret(Queue<Integer> q)
{
  if (q.isEmpty())  return 0;
  int x = q.head();
  int z = x * what(q, x);
  int y = 1 + secret(q);
  q.insert(z);
  return y;
}

C#:

public static int  Secret(Queue<int> q)
{
  if (q.IsEmpty()) return 0;
  int x = q.Head();
  int z = x * What(q, x);
  int y = 1 + Secret(q);
  q.Insert(z);
  return y;
}

עקבו אחר הפעולה `secret(q)` עבור התור `q : [5,5,1,1,4,4,4,5,6]` (5 בראש התור).

אין צורך לפרט את המעקב אחרי הפעולה `what`.

(1)

מהו הערך המוחזר מהפעולה `secret`?

(2)

איך ייראה התור בסיום הפעולה `secret`?

(3)

__אחרי__ זימון הפעולה `secret(q)` התור `q` נראה כך: `q:[6,16,2,3]` (6 בראש התור)

איך נראה התור `q` __לפני__ זימון הפעולה?

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

סעיף א

(1)
תשובה:

הפעולה מחזירה 3, והתור נשאר `[3,3,2,8]`.

הפעולה בודקת אם התור ריק או אם הראש שונה מ-`x`; אם כן מחזירה 0. אחרת מוציאה את הראש וממשיכה ברקורסיה (עם `x` שווה לאיבר שהוצא).

קריאההתור בכניסה`x``q.head()`תנאי העצירהפעולהערך מוחזר
1`[5,5,5,3,3,2,8]`55לאמוציאים 51+2=31+2=3
2`[5,5,3,3,2,8]`55לאמוציאים 51+1=21+1=2
3`[5,3,3,2,8]`55לאמוציאים 51+0=11+0=1
4`[3,3,2,8]`53כן (`5 != 3`)-0

הערכים חוזרים מהקריאה הרביעית כלפי מעלה: 0→1→2→30 \to 1 \to 2 \to 3.

תשובה: `what(q,5)` מחזירה 3, ובסיום התור הוא `[3,3,2,8]`.

(2)
תשובה:

לא נכונה: אפשר להסיק רק ש-`x` אינו בראש התור; הוא יכול להופיע בהמשך התור.

1. התור לא ריק ולא השתנה, כלומר כבר בקריאה הראשונה תנאי העצירה התקיים בגלל `x != q.head()` - הראש שונה מ-`x`, ושום איבר לא הוצא.

2. הפעולה בודקת רק את ראש התור, ולא את שאר האיברים. לכן `x` יכול להופיע במקום אחר בתור.

3. דוגמה נגדית: `q:[3,5]` (3 בראש התור) ו-`x = 5`. הראש 3 שונה מ-5, הפעולה מחזירה 0 והתור לא משתנה - אבל 5 מופיע בתור.

תשובה: הטענה אינה נכונה. אפשר לקבוע רק ש-`x` אינו נמצא בראש התור.

(3)
תשובה:

לדוגמה `q:[7,7,7,7,1,8]` (7 בראש התור); אחרי הזימון: `q:[1,8]`.

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

דוגמה: `q:[7,7,7,7,1,8]` (7 בראש התור).

1. ארבע קריאות רצופות מוציאות את ארבעת ה-7.

2. בקריאה החמישית הראש הוא 1, ו-`7 != 1`, ולכן מוחזר 0.

3. בסך הכול 1+1+1+1+0=41+1+1+1+0=4.

הפעולה מוציאה את ארבעת ה-7, ולכן אחרי הזימון התור הוא `q:[1,8]`.

תשובה: למשל `q:[7,7,7,7,1,8]`; אחרי הזימון `q:[1,8]` (1 בראש התור).

(4)
תשובה:

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

1. כל עוד בראש התור נמצא `x`, הפעולה מוציאה אותו ומוסיפה 1 לתוצאה.

2. כשהתור מתרוקן או שבראשו ערך אחר, היא מפסיקה ומחזירה 0.

3. לכן התוצאה היא אורך הרצף של `x` בתחילת התור, והרצף הזה נמחק מהתור. מופעים של `x` שאינם ברצף ההתחלתי נשארים.

תשובה: הפעולה מחזירה את מספר המופעים הרצופים של `x` בראש התור ומוציאה אותם מהתור.

סעיף ב

(1)
תשובה:

5

מה עושה כל קריאה: `x` הוא הראש, `what(q, x)` מוציאה את הרצף של `x` בראש התור ומחזירה את אורכו, ו-`z` הוא `x` כפול האורך. אחר כך קריאה רקורסיבית על שאר התור, ורק אחרי שהיא חוזרת מכניסים את `z` לסוף התור. הפעולה מחזירה 1+1+ (התוצאה של הקריאה הבאה), כלומר את מספר הרצפים.

קריאההתור בכניסה`x``what(q,x)``z`התור אחרי `what`
1`[5,5,1,1,4,4,4,5,6]`5210`[1,1,4,4,4,5,6]`
2`[1,1,4,4,4,5,6]`122`[4,4,4,5,6]`
3`[4,4,4,5,6]`4312`[5,6]`
4`[5,6]`515`[6]`
5`[6]`616`[]`
6`[]`---מחזירה 0

החזרה מהרקורסיה (מהקריאה העמוקה כלפי מעלה):

קריאה`y`מכניסים `z`התור אחרי ההכנסה
51+0=11+0=16`[6]`
41+1=21+1=25`[6,5]`
31+2=31+2=312`[6,5,12]`
21+3=41+3=42`[6,5,12,2]`
11+4=51+4=510`[6,5,12,2,10]`

תשובה: הפעולה מחזירה 5 (מספר הרצפים בתור).

(2)
תשובה:

`q:[6,5,12,2,10]` (6 בראש התור).

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

•הרצפים בתור המקורי: 5 פעמיים (z=10z=10), 1 פעמיים (z=2z=2), 4 שלוש פעמים (z=12z=12), 5 פעם אחת (z=5z=5), 6 פעם אחת (z=6z=6).

•סדר ההכנסה: 6, 5, 12, 2, 10.

תשובה: `q:[6,5,12,2,10]` (6 בראש התור).

(3)
תשובה:

לדוגמה `q:[3,1,1,4,4,4,4,2,2,2]` (3 בראש התור).

חושבים הפוך: מסעיפים 1-2 ראינו שכל רצף של ערך vv באורך LL הופך לאיבר אחד v⋅Lv\cdot L, והאיברים נכנסים לתור בסדר הפוך לסדר הרצפים.

1. התור בסיום הוא `[6,16,2,3]`, ולכן ברשימה המקורית היו 4 רצפים, ומכפלות הרצפים לפי הסדר המקורי הן: 3, 2, 16, 6.

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

•3=3⋅13 = 3\cdot1: האיבר 3 פעם אחת.

•2=1⋅22 = 1\cdot2: האיבר 1 פעמיים.

•16=4⋅416 = 4\cdot4: האיבר 4 ארבע פעמים.

•6=2⋅36 = 2\cdot3: האיבר 2 שלוש פעמים.

3. בדיקה: עבור `[3,1,1,4,4,4,4,2,2,2]` ערכי `z` לפי הסדר הם 3, 2, 16, 6, והם נכנסים לתור בסדר הפוך: `[6,16,2,3]`. הפעולה מחזירה 4.

התשובה אינה יחידה: למשל גם `[1,1,1,2,4,4,4,4,6]` (מכפלות 3,2,16,63, 2, 16, 6) מתאים.

תשובה: למשל `q:[3,1,1,4,4,4,4,2,2,2]` (3 בראש התור).

שאלה 10 · משחק קלפים: השוואת קלפים ומחלקת חפיסה

המחלקה `Card` מייצגת קלף למשחק ילדים Eka.

במשחק משתתפים קלפים בארבעה צבעים: אדום (R), ירוק (G), כחול (B) וצהוב (Y). על כל קלף רשום מספר בין 1 ל-9. סה"כ משתמשים במשחק 36 קלפים שונים.

Java:

public class Card
{
    private char color;
    private int digit;
    public Card(char c, int d)
    {
        this.color = c;
        this.digit = d;
    }
}

C#:

public class Card
{
    private char color;
    private int digit;
    public Card(char c, int d)
    {
        this.color = c;
        this.digit = d;
    }
}
א.

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

כתבו במחלקה `Card` פעולה `compareTo`. הפעולה תקבל הפניה לעצם `other` מטיפוס `Card`.

•אם הקלף שמפעיל את הפעולה (`this`) "חזק יותר" מהקלף שמתקבל כפרמטר (`other`), הפעולה תחזיר -1.

•אם הקלף שמפעיל את הפעולה (`this`) "חלש יותר" מהקלף שמתקבל כפרמטר (`other`), הפעולה תחזיר 1.

•אם הקלף שמפעיל את הפעולה (`this`) זהה לקלף שמתקבל כפרמטר (`other`), הפעולה תחזיר 0.

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

Java:

public int compareTo(Card other)

C#:

public int CompareTo(Card other)
(3 נקודות)

למשחק Eka כללים הבאים:

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

אם כל הקלפים חולקו ואין מנצח – מכריזים על תיקו.

המחלקה `Deck` מייצגת חפיסת קלפים. במחלקה הוגדרו פעולות הבאות:

כותרת הפעולה (Java)כותרת הפעולה (C#)תיאור
`public Deck()``public Deck()`פעולה בונה המייצרת חפיסה ריקה (ללא קלפים).
`public void addCard(Card c)``public void AddCard(Card c)`פעולה המקבלת קלף `c` ומוסיפה אותו לחפיסה
`public Card drawCard()``public Card DrawCard()`פעולה המוציאה קלף מהחפיסה ומחזירה אותו. אם החפיסה ריקה, הפעולה תחזיר `null`.
`public boolean exist(Card c)``public bool Exist(Card c)`פעולה המקבלת קלף `c` ובודקת אם הוא קיים בחפיסה. אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
`public boolean isFull(char color)``public bool IsFull(char color)`פעולה המקבלת צבע `color` ובודקת אם בחפיסה יש כל הקלפים של אותו צבע. אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
ב.

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

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

Java:

public static void game(Deck d)

C#:

public static void Game(Deck d)
(5 נקודות)
ג.

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

הערה: שימו לב שבמחלקה `Card` אין פעולות get ואי אפשר להוסיף אותן!

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

סעיף א

תשובה:

משווים קודם את המספרים (גדול יותר - מחזירים -1, קטן יותר - 1); אם שווים, משווים את דרגות הצבעים (R=0, G=1, B=2, Y=3) באותו אופן; אם גם הצבע שווה - 0.

הרעיון:

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

2. משווים קודם את המספרים: אם המספר של `this` גדול - הוא חזק יותר ומחזירים -1; אם קטן - מחזירים 1.

3. אם המספרים שווים, משווים את דרגות הצבעים באותו אופן.

4. אם גם הצבעים שווים - הקלפים זהים, ומחזירים 0.

הפעולה כתובה בתוך המחלקה `Card`, ולכן מותר לה לגשת ישירות לתכונות הפרטיות `digit` ו-`color` גם של העצם `other` (הרשאת `private` היא ברמת המחלקה).

Java:

private static int rank(char color)       // דרגת הצבע: אדום הכי חלש, צהוב הכי חזק
{
    if (color == 'R') return 0;
    if (color == 'G') return 1;
    if (color == 'B') return 2;
    return 3;                             // 'Y'
}

public int compareTo(Card other)
{
    if (this.digit > other.digit) return -1;
    if (this.digit < other.digit) return 1;
    if (rank(this.color) > rank(other.color)) return -1;
    if (rank(this.color) < rank(other.color)) return 1;
    return 0;
}

C#:

private static int Rank(char color)       // דרגת הצבע: אדום הכי חלש, צהוב הכי חזק
{
    if (color == 'R') return 0;
    if (color == 'G') return 1;
    if (color == 'B') return 2;
    return 3;                             // 'Y'
}

public int CompareTo(Card other)
{
    if (this.digit > other.digit) return -1;
    if (this.digit < other.digit) return 1;
    if (Rank(this.color) > Rank(other.color)) return -1;
    if (Rank(this.color) < Rank(other.color)) return 1;
    return 0;
}

דוגמאות: `R5` מול `Y5`: המספרים שווים, אדום חלש מצהוב, מוחזר 1. `R6` מול `Y5`: 6 > 5, מוחזר -1. `G2` מול `G2`: מוחזר 0.

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

סעיף ב

תשובה:

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

הרעיון:

1. יוצרים שתי חפיסות ריקות - `player1` (השחקן הראשון) ו-`player2` (השני).

2. בחפיסה 36 קלפים ובכל סבב נשלפים שניים, ולכן יש לכל היותר 18 סבבים.

3. בכל סבב: השחקן הראשון שולף `c1` והשני `c2`. אם `c1.compareTo(c2) == -1` הקלף של הראשון חזק יותר, ואחרת (כל הקלפים שונים, ולכן אין תוצאה 0) של השני. המנצח בסבב מוסיף את שני הקלפים לחפיסה שלו.

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

5. אם הסתיימו 18 הסבבים בלי מנצח - כל הקלפים חולקו, ומדפיסים "תיקו".

Java:

public static boolean hasFullColor(Deck p)
{
    return p.isFull('R') || p.isFull('G') || p.isFull('B') || p.isFull('Y');
}

public static void game(Deck d)
{
    Deck player1 = new Deck();
    Deck player2 = new Deck();
    for (int i = 0; i < 18; i++)          // 36 קלפים = 18 סבבים
    {
        Card c1 = d.drawCard();
        Card c2 = d.drawCard();
        Deck w;
        if (c1.compareTo(c2) == -1)       // הקלף של הראשון חזק יותר
            w = player1;
        else
            w = player2;
        w.addCard(c1);
        w.addCard(c2);
        if (hasFullColor(w))
        {
            if (w == player1)
                System.out.println("הראשון מנצח");
            else
                System.out.println("השני מנצח");
            return;
        }
    }
    System.out.println("תיקו");
}

C#:

public static bool HasFullColor(Deck p)
{
    return p.IsFull('R') || p.IsFull('G') || p.IsFull('B') || p.IsFull('Y');
}

public static void Game(Deck d)
{
    Deck player1 = new Deck();
    Deck player2 = new Deck();
    for (int i = 0; i < 18; i++)          // 36 קלפים = 18 סבבים
    {
        Card c1 = d.DrawCard();
        Card c2 = d.DrawCard();
        Deck w;
        if (c1.CompareTo(c2) == -1)       // הקלף של הראשון חזק יותר
            w = player1;
        else
            w = player2;
        w.AddCard(c1);
        w.AddCard(c2);
        if (HasFullColor(w))
        {
            if (w == player1)
                Console.WriteLine("הראשון מנצח");
            else
                Console.WriteLine("השני מנצח");
            return;
        }
    }
    Console.WriteLine("תיקו");
}

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

סעיף ג

תשובה:

תכונות: מערך `Card[36]` ומונה `count`. `addCard` מוסיפה בתא `count`; `drawCard` מוציאה את הקלף האחרון (או `null`); `exist` משווה עם `compareTo(c) == 0`; `isFull` בודקת `exist` לכל המספרים 1-9 בצבע הנתון.

הרעיון:

1. תכונות: מערך של 36 קלפים (מספר הקלפים במשחק) ומונה `count` של מספר הקלפים בחפיסה כרגע. הקלפים נמצאים בתאים `0` עד `count-1`.

2. `Deck()`: יוצרת מערך בגודל 36 ומאפסת את המונה.

3. `addCard(c)`: מכניסה את `c` לתא `count` ומגדילה את המונה (אם יש מקום).

4. `drawCard()`: אם החפיסה ריקה מחזירה `null`. אחרת מקטינה את המונה ומחזירה את הקלף שבתא `count` - הקלף העליון בחפיסה (האחרון שנוסף). כך ההוצאה היא O(1)O(1).

5. `exist(c)`: אין פעולות `get` ב-`Card`, ולכן לא ניתן להשוות צבע ומספר ישירות. במקום זה משתמשים ב-`compareTo` מסעיף א': היא מחזירה 0 בדיוק כשלשני הקלפים אותו מספר ואותו צבע.

6. `isFull(color)`: בצבע אחד יש 9 קלפים (המספרים 1 עד 9). יוצרים לכל מספר `d` קלף `new Card(color, d)` ובודקים בעזרת `exist` אם הוא בחפיסה. אם אחד חסר - `false`; אם כולם נמצאו - `true`.

Java:

public class Deck
{
    private Card[] cards;     // הקלפים בחפיסה
    private int count;        // מספר הקלפים בחפיסה כרגע

    public Deck()
    {
        this.cards = new Card[36];
        this.count = 0;
    }

    public void addCard(Card c)
    {
        if (this.count < this.cards.length)
        {
            this.cards[this.count] = c;
            this.count++;
        }
    }

    public Card drawCard()
    {
        if (this.count == 0)
            return null;
        this.count--;                       // הקלף העליון הוא האחרון שנוסף
        Card c = this.cards[this.count];
        this.cards[this.count] = null;
        return c;
    }

    public boolean exist(Card c)
    {
        for (int i = 0; i < this.count; i++)
            if (this.cards[i].compareTo(c) == 0)   // אותו מספר ואותו צבע
                return true;
        return false;
    }

    public boolean isFull(char color)
    {
        for (int d = 1; d <= 9; d++)
            if (!this.exist(new Card(color, d)))
                return false;
        return true;
    }
}

C#:

public class Deck
{
    private Card[] cards;     // הקלפים בחפיסה
    private int count;        // מספר הקלפים בחפיסה כרגע

    public Deck()
    {
        this.cards = new Card[36];
        this.count = 0;
    }

    public void AddCard(Card c)
    {
        if (this.count < this.cards.Length)
        {
            this.cards[this.count] = c;
            this.count++;
        }
    }

    public Card DrawCard()
    {
        if (this.count == 0)
            return null;
        this.count--;                       // הקלף העליון הוא האחרון שנוסף
        Card c = this.cards[this.count];
        this.cards[this.count] = null;
        return c;
    }

    public bool Exist(Card c)
    {
        for (int i = 0; i < this.count; i++)
            if (this.cards[i].CompareTo(c) == 0)   // אותו מספר ואותו צבע
                return true;
        return false;
    }

    public bool IsFull(char color)
    {
        for (int d = 1; d <= 9; d++)
            if (!this.Exist(new Card(color, d)))
                return false;
        return true;
    }
}

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

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

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

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