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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · פיצול תור ציונים לתור ציונים ותור ספירה

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

לדוגמה:

תור ציונים marks:

תלמיד ראשון השלים שלוש בחינות וקיבל את הציונים הבאים: 80, 90, 100.

תלמיד שני השלים שתי בחינות וקיבל את הציונים הבאים: 75, 96.

תלמיד שלישי השלים ארבע בחינות וקיבל את הציונים 100, 100, 97, 96.

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

תלמיד חמישי השלים שתי בחינות וקיבל את הציונים הבאים: 88, 94

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

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

תור ציונים marks (אחרי העדכון):

תור בחינות tests:

א.

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

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

Java:

public static Queue<Integer> arrangeData(Queue<Integer> marks)

C#:

public static Queue<int> ArrangeData(Queue<int> marks)
(12 נקודות)
ב.

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

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

סעיף א

תשובה:

מרוקנים את marks איבר-איבר: ציון נשמר בתור עזר ומגדיל מונה; −1-1 מכניס את המונה ל-tests ומאפס אותו. בסוף מחזירים את הציונים מתור העזר ל-marks ומחזירים את tests.

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

•מונה count סופר כמה ציונים יש לתלמיד הנוכחי.

•כל ציון (ערך שונה מ-−1-1) נשמר בתור עזר temp, והמונה גדל ב-1.

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

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

1. יוצרים את tests ואת temp ריקים, ו-count = 0.

2. כל עוד marks לא ריק – מוציאים איבר x:

•אם x == -1 – מכניסים את count ל-tests ומאפסים את count.

•אחרת – מכניסים את x ל-temp ומגדילים את count.

3. אם בסוף נשאר count > 0 (התור לא הסתיים ב-−1-1), מכניסים אותו ל-tests – כך הפעולה עמידה גם לקלט כזה.

4. מעבירים את כל temp חזרה ל-marks ומחזירים את tests.

Java:

public static Queue<Integer> arrangeData(Queue<Integer> marks)
{
    Queue<Integer> tests = new Queue<Integer>(); // התור שיוחזר
    Queue<Integer> temp = new Queue<Integer>();  // הציונים בלי ערכי ההפרדה
    int count = 0;                               // מונה הבחינות של התלמיד הנוכחי

    while (!marks.isEmpty())
    {
        int x = marks.remove();
        if (x == -1)                 // הסתיימו הציונים של תלמיד
        {
            tests.insert(count);
            count = 0;
        }
        else                         // ציון רגיל
        {
            temp.insert(x);
            count++;
        }
    }
    if (count > 0)                   // ליתר ביטחון: אם אחרי התלמיד האחרון אין -1
        tests.insert(count);

    while (!temp.isEmpty())          // מחזירים את הציונים לתור marks
        marks.insert(temp.remove());

    return tests;
}

C#:

public static Queue<int> ArrangeData(Queue<int> marks)
{
    Queue<int> tests = new Queue<int>(); // התור שיוחזר
    Queue<int> temp = new Queue<int>();  // הציונים בלי ערכי ההפרדה
    int count = 0;                               // מונה הבחינות של התלמיד הנוכחי

    while (!marks.IsEmpty())
    {
        int x = marks.Remove();
        if (x == -1)                 // הסתיימו הציונים של תלמיד
        {
            tests.Insert(count);
            count = 0;
        }
        else                         // ציון רגיל
        {
            temp.Insert(x);
            count++;
        }
    }
    if (count > 0)                   // ליתר ביטחון: אם אחרי התלמיד האחרון אין -1
        tests.Insert(count);

    while (!temp.IsEmpty())          // מחזירים את הציונים לתור marks
        marks.Insert(temp.Remove());

    return tests;
}

בדיקה על הדוגמה: 80, 90, 100 נכנסים ל-temp (count = 3), ה-−1-1 מכניס 3 ל-tests. אחר כך 75, 96 → 2; אחר כך 100, 100, 97, 96 → 4; שני −1-1 צמודים → 0; ולבסוף 88, 94 → 2. מתקבל tests = 3, 2, 4, 0, 2 ו-marks = 80, 90, 100, 75, 96, 100, 100, 97, 96, 88, 94 – בדיוק כמו באיורים.

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

סעיף ב

תשובה:

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

נסמן ב-n את מספר האיברים בתור marks לפני הזימון (ציונים וערכי −1-1).

1. הלולאה הראשונה מוציאה כל איבר פעם אחת בדיוק, ועושה עליו מספר קבוע של פעולות (השוואה, insert, הגדלת מונה) – O(n)O(n).

2. הלולאה השנייה מעבירה את הציונים מ-temp חזרה ל-marks; יש בו לכל היותר n איברים – O(n)O(n).

3. שאר הפעולות (יצירת התורים, אתחול) הן O(1)O(1).

סך הכול O(n)+O(n)+O(1)=O(n)O(n)+O(n)+O(1)=O(n) – סיבוכיות לינארית.

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

שאלה 2 · איזון שרשרת חוליות: אורך זוגי וסכום אפס

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

א.

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

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

Java:

public static void balance(Node<Integer> chain)

C#:

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

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

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

סעיף א

תשובה:

סורקים פעם אחת ומחשבים אורך len, סכום sum וחוליה אחרונה. אם len זוגי ו-sum = 0 – לא עושים דבר; אם len אי-זוגי – מוסיפים חוליה -sum; אם len זוגי ו-sum ≠ 0 – מוסיפים שתי חוליות: -sum ו-0.

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

אחרי המעבר יש שלושה מקרים:

1. len זוגי ו-sum = 0 – השרשרת כבר "מאוזנת", לא עושים דבר.

2. len אי-זוגי – מוסיפים חוליה אחת עם הערך -sum. האורך נעשה זוגי (len+1len+1) והסכום נעשה sum+(−sum)=0sum+(-sum)=0. (זה נכון גם כש-sum = 0: מוסיפים חוליה עם 0.)

3. len זוגי ו-sum ≠ 0 – הוספת חוליה אחת הייתה הופכת את האורך לאי-זוגי, ולכן מוסיפים שתי חוליות: -sum ואחריה 0. האורך len+2len+2 זוגי והסכום sum−sum+0=0sum-sum+0=0.

ההנחה: chain מפנה לחוליה הראשונה, כלומר השרשרת אינה ריקה.

Java:

public static void balance(Node<Integer> chain)
{
    int len = 1;                    // מספר החוליות
    int sum = chain.getValue();     // סכום הערכים
    Node<Integer> last = chain;     // בסוף הלולאה: החוליה האחרונה

    while (last.hasNext())
    {
        last = last.getNext();
        len++;
        sum += last.getValue();
    }

    if (len % 2 == 0 && sum == 0)   // השרשרת כבר "מאוזנת"
        return;

    if (len % 2 == 1)               // אורך אי-זוגי: מוסיפים חוליה אחת
    {
        last.setNext(new Node<Integer>(-sum));
    }
    else                            // אורך זוגי וסכום שונה מ-0: מוסיפים שתי חוליות
    {
        last.setNext(new Node<Integer>(-sum));
        last.getNext().setNext(new Node<Integer>(0));
    }
}

C#:

public static void Balance(Node<int> chain)
{
    int len = 1;                    // מספר החוליות
    int sum = chain.GetValue();     // סכום הערכים
    Node<int> last = chain;     // בסוף הלולאה: החוליה האחרונה

    while (last.HasNext())
    {
        last = last.GetNext();
        len++;
        sum += last.GetValue();
    }

    if (len % 2 == 0 && sum == 0)   // השרשרת כבר "מאוזנת"
        return;

    if (len % 2 == 1)               // אורך אי-זוגי: מוסיפים חוליה אחת
    {
        last.SetNext(new Node<int>(-sum));
    }
    else                            // אורך זוגי וסכום שונה מ-0: מוסיפים שתי חוליות
    {
        last.SetNext(new Node<int>(-sum));
        last.GetNext().SetNext(new Node<int>(0));
    }
}

דוגמאות:

- 4, 1, −2-2 (אורך 3, סכום 3) → מוסיפים −3-3: מתקבל 4, 1, −2-2, −3-3 – אורך 4, סכום 0.

- 2, 3 (אורך 2, סכום 5) → מוסיפים −5-5 ו-0: מתקבל 2, 3, −5-5, 0 – אורך 4, סכום 0.

- 3, −3-3 – כבר מאוזנת, לא משתנה.

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

סעיף ב

תשובה:

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

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

1. הלולאה עוברת על כל חוליה פעם אחת ומבצעת בכל חוליה מספר קבוע של פעולות – O(n)O(n).

2. הבדיקות שאחרי הלולאה והוספת חוליה אחת או שתיים (יש לנו כבר הפניה לחוליה האחרונה) – O(1)O(1).

סך הכול O(n)O(n).

תשובה: O(n)O(n) – לינארית באורך השרשרת.

שאלה 3 · העמסה, דריסה ו-equals בירושה

א.

נתונה המחלקה Square המתארת ריבוע:

Java:

public class Square {
  protected double width;
  protected String color;
  public Square(double val){ width = val; color = "black";}
  public void paint(double scale, String color){..}
  public double perimeter(double scale){ … }
}

C#:

public class Square {
  protected double width;
  protected string color;
  public Square(double val){ width = val; color = "black";}
  public void Paint(double scale, string color){..}
  public virtual double Perimeter(double scale){ … }
}

אילו מהחתימות הבאות היא העמסה (overloading) חוקית של הפעולה paint?

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

Java:

1. public int paint (double y, String x)
2. public void paint (int x)
3. public double paint (double a, char b)
4. private void paint(double x, String y)
5. private double paint (String y, double x)

C#:

1. public int Paint (double y, string x)
2. public void Paint (int x)
3. public double Paint (double a, char b)
4. private void Paint(double x, string y)
5. private double Paint (string y, double x)
(5 נקודות)
ב.

נתונה המחלקה Rectangle (מלבן) יורשת מ- Square

Java:

public class Rectangle extends Square {
   private double length;
   public Rectangle(double val1, double val2){
         super(val1);
         length = val2;
     }
   public boolean equals(Rectangle other){
       return width == other.width && length == other.length;
     }
   }

C#:

public class Rectangle : Square {
   private double length;
   public Rectangle(double val1, double val2):base(val1)
     {
         length = val2;
     }
   public bool Equals(Rectangle other){
       return width == other.width && length == other.length;
     }
   }

עבור כל אחת מבין הפעולות הבאות קבעו אם אפשר להוסיף אותה למחלקה Rectangle?

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

Java:

1. private double perimeter (double x){…}
2. public double perimeter (double y) {…}
3. public void perimeter (){…}
4. public int perimeter (int y) {…}
5. public void perimeter (double x) {…}

C#:

1. private override double Perimeter (double x){…}
2. public override double Perimeter (double y) {…}
3. public override void Perimeter (){…}
4. public override int Perimeter (int y) {…}
5. public override void Perimeter (double x) {…}
(5 נקודות)
ג.

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

Java:

Square sqr1 = new Square(1);
Square sqr2 =new Square(1);
Square sqrRec = new Rectangle(1,2);
Rectangle rec = new Rectangle(1,2);
System.out.println(sqr1.equals(sqr2));
System.out.println(sqrRec.equals(rec));
System.out.println(sqrRec.equals((Square)rec));
System.out.println(((Rectangle)sqrRec).equals(rec));
System.out.println(rec.equals(sqrRec));

C#:

Square sqr1 = new Square(1);
Square sqr2 =new Square(1);
Square sqrRec = new Rectangle(1,2);
Rectangle rec = new Rectangle(1,2);
Console.WriteLine(sqr1.Equals(sqr2));
Console.WriteLine(sqrRec.Equals(rec));
Console.WriteLine(sqrRec.Equals((Square)rec));
Console.WriteLine(((Rectangle)sqrRec).Equals(rec));
Console.WriteLine(rec.Equals(sqrRec));

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

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

סעיף א

תשובה:

העמסות חוקיות: 2, 3, 5. לא חוקיות: 1, 4 (אותה רשימת פרמטרים (double, String) כמו paint הקיימת; שינוי טיפוס ההחזרה או ההרשאה בלבד אינו העמסה).

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

החתימה הקיימת: paint(double, String) (ב-C#: Paint(double, string)).

חתימהרשימת טיפוסי הפרמטריםהעמסה חוקית?הסבר
1(double, String)לאאותם טיפוסים באותו סדר; שונה רק טיפוס ההחזרה (int) ושמות הפרמטרים – שגיאת הידור
2(int)כןמספר פרמטרים שונה
3(double, char)כןהפרמטר השני מטיפוס אחר
4(double, String)לאאותה רשימת פרמטרים; שונה רק ההרשאה (private) – שגיאת הידור
5(String, double)כןאותם טיפוסים אבל בסדר אחר – רשימה שונה

התשובה זהה ב-Java וב-C#.

תשובה: חתימות 2, 3, 5 הן העמסות חוקיות; 1 ו-4 אינן חוקיות.

סעיף ב

תשובה:

Java: אפשר להוסיף את 2, 3, 4; אי אפשר את 1 (דריסה שמצמצמת הרשאה) ואת 5 (אותה חתימה עם טיפוס החזרה אחר). C#: אפשר להוסיף רק את 2.

הכללים: Rectangle יורשת מ-Square את perimeter(double) שמחזירה double ומוגדרת public.

•פעולה במחלקה היורשת עם אותה חתימה (אותו שם ואותה רשימת פרמטרים) היא דריסה (override). בדריסה טיפוס ההחזרה חייב להיות זהה (או תואם) ואסור לצמצם את ההרשאה (אסור להפוך פעולה public ל-private).

•פעולה עם אותו שם ורשימת פרמטרים אחרת היא העמסה – מותרת תמיד, עם כל טיפוס החזרה.

•ב-C# יש גם המילה override: מותר לכתוב אותה רק אם במחלקת הבסיס יש פעולה virtual עם אותה חתימה בדיוק (שם, פרמטרים וטיפוס החזרה), ועם אותה הרשאה. פעולה virtual/override לא יכולה להיות private.

Java:

פעולהאפשר להוסיף?הסבר
1לאאותה חתימה perimeter(double) – זו דריסה, אבל ההרשאה צומצמה מ-public ל-private – שגיאת הידור
2כןדריסה תקינה: אותה חתימה, אותו טיפוס החזרה, public
3כןאין פרמטרים – העמסה (פעולה חדשה)
4כןפרמטר int במקום double – העמסה
5לאאותה חתימה perimeter(double) אבל טיפוס החזרה void במקום double – לא דריסה חוקית – שגיאת הידור

C# (בכל החתימות כתוב override):

פעולהאפשר להוסיף?הסבר
1לאפעולת override לא יכולה להיות private, וההרשאה חייבת להיות זהה ל-public של הבסיס
2כןPerimeter(double) ב-Square מוגדרת virtual ומחזירה double – דריסה תקינה
3לאאין במחלקת הבסיס Perimeter() בלי פרמטרים – אין מה לדרוס
4לאאין במחלקת הבסיס Perimeter(int) – אין מה לדרוס
5לאטיפוס ההחזרה void שונה מ-double של הפעולה הנדרסת

תשובה: ב-Java אפשר להוסיף את הפעולות 2, 3, 4 (ואי אפשר את 1, 5); ב-C# אפשר להוסיף רק את פעולה 2.

סעיף ג

תשובה:

Java: false, false, false, true, false (כל אחד בשורה). C#: False, False, False, True, False.

נקודת המפתח: ב-Square אין equals משלה, ולכן יש לה את equals(Object) של Object, שבודקת זהות הפניות (האם זה אותו עצם). ב-Rectangle הפעולה equals(Rectangle other) מקבלת פרמטר מטיפוס Rectangle, ולכן היא העמסה ולא דריסה של equals(Object). איזו גרסה תופעל נקבע בזמן הידור לפי הטיפוס המוצהר של המשתנה שעליו מפעילים ושל הארגומנט:

•אם הטיפוס המוצהר של המשתנה הוא Square – המהדר מכיר רק את equals(Object), והיא לא נדרסה ב-Rectangle, לכן תמיד משווים הפניות.

•אם הטיפוס המוצהר הוא Rectangle וגם הארגומנט מוצהר Rectangle – נבחרת equals(Rectangle), המדויקת יותר, שמשווה את width ו-length.

(ב-C# המצב זהה: ל-Square יש רק Equals(object) של object, ו-Equals(Rectangle) היא העמסה.)

שורהפעולה שנבחרתמה נבדקפלט
sqr1.equals(sqr2)equals(Object)שני עצמים שוניםfalse
sqrRec.equals(rec)equals(Object) – sqrRec מוצהר SquaresqrRec ו-rec הם עצמים שוניםfalse
sqrRec.equals((Square)rec)equals(Object)אותו מצב – ההמרה לא משנה את העצםfalse
((Rectangle)sqrRec).equals(rec)equals(Rectangle) – גם המשתנה וגם הארגומנט מוצהרים Rectanglewidth: 1 == 1, length: 2 == 2true
rec.equals(sqrRec)equals(Object) – הארגומנט מוצהר Square ולא מתאים לפרמטר Rectangleעצמים שוניםfalse

פלט ב-Java:

false
false
false
true
false

פלט ב-C# (ערך bool מודפס באות גדולה):

False
False
False
True
False

תשובה: false, false, false, true, false (ב-C#: False, False, False, True, False).

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

א.

נתונה הפעולה main במחלקה Driver:

Java:

public static void main(String[] args)
  {
      Three x1 = new One();
      Two x2 = (Two)(new One());
      Two x3 = new Four();
      One x4 = new Four();
  }

C#:

public static void Main(string[] args)
  {
      Three x1 = new One();
      Two x2 = (Two)(new One());
      Two x3 = new Four();
      One x4 = new Four();
  }

נתונות חמש האפשרויות לעץ הירושה הכולל את המחלקות One, Two, Three, Four.

1. Three יורשת מ-One, Two יורשת מ-One, Four יורשת מ-One

2. Three יורשת מ-One, Two יורשת מ-One, Four יורשת מ-Two

3. One יורשת מ-Three, Four יורשת מ-Two, Three יורשת מ-Two

4. One יורשת מ-Three, Three יורשת מ-Two, Four יורשת מ-One

5. One יורשת מ-Three, Two יורשת מ-One, Four יורשת מ-One

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

(10 נקודות)
ב.

(אין קשר לסעיף א')

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

•המחלקה Point מתארת נקודה על ציר ה-X.

Java:

public class Point
  {
      private int x;
      public Point (int x)
      {
              this.x = x;
       }
      public String toString()
      {
              return " x= " + this.x;
       }
   }

C#:

public class Point
  {
      protected int x;
      public Point (int x)
      {
              this.x = x;
       }
      public override string ToString()
      {
              return " x= " + this.x;
       }
   }

•המחלקה Circle מתארת מעגל עם מרכז על ציר ה-X

Java:

public class Circle extends Point
  {
        private int radius;
        public Circle( int x, int radius)
        {
              …..
        }
        public String toString()
        {
              …..
        }
}

C#:

public class Circle : Point
  {
        private int radius;
        public Circle( int x, int radius): base(…..)
        {
              …..
        }
        public override string ToString()
        {
              …..
        }
}

•המחלקה Cylinder מייצגת גליל

Java:

public class Cylinder extends Circle
  {
        private int height;
        …….
  }

C#:

public class Cylinder : Circle
  {
        private int height;
        …….
  }

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

Java:

public static void main(String[] args)
   {
       Circle b = new Circle (1, 2);
       System.out.println(b);
       Cylinder c = new Cylinder (10, 20, 30);
       System.out.println(c);
   }

C#:

public static void Main(string[] args)
   {
       Circle b = new Circle (1, 2);
       Console.WriteLine(b);
       Cylinder c = new Cylinder (10, 20, 30);
       Console.WriteLine(c);
   }

השלימו את הפעולות החסרות במחלקות Cylinder ו- Circle כך שפלט של הפעולה main יהיה

x = 1, radius = 2
x = 10, radius = 20, height = 30
(6 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

1 – שגיאת הידור; 2 – שגיאת הידור; 3 – שגיאת הידור; 4 – תקינה; 5 – שגיאת הידור.

הכללים שבודקים בכל שורה:

•`A v = new B();` עובר הידור רק אם B היא A או יורשת ממנה (ישירות או דרך מחלקות ביניים) – הצבה "כלפי מעלה". אחרת – שגיאת הידור.

•`(A)(new B())` – המרה מפורשת עוברת הידור רק אם A ו-B באותו קו ירושה (אחת יורשת מהשנייה). בזמן ריצה היא מצליחה רק אם העצם (B) הוא באמת A, כלומר B היא A או יורשת ממנה. אם A יורשת מ-B (המרה "כלפי מטה" של עצם שאינו A) – שגיאת זמן ריצה (ClassCastException ב-Java, InvalidCastException ב-C#). אם אין ביניהן קשר – שגיאת הידור.

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

לכל אפשרות צריך: One יורשת מ-Three (שורה x1), Four יורשת מ-Two (x3), Four יורשת מ-One (x4), ו-One היא Two (x2, כדי שלא תהיה שגיאה בזמן ריצה).

עצי הירושה (המחלקה העליונה – מחלקת הבסיס):

אפשרות 1:
        One
      /  |  \
   Two Three Four

אפשרות 2:
        One
       /   \
    Two    Three
     |
    Four

אפשרות 3:
        Two
       /   \
    Three   Four
     |
    One

אפשרות 4:
    Two
     |
    Three
     |
    One
     |
    Four

אפשרות 5:
    Three
     |
    One
   /   \
 Two   Four
אפשרותx1x2x3x4תוצאה
1One אינה Three – שגיאת הידורTwo יורשת מ-One: עובר הידור, נכשל בזמן ריצהFour ו-Two "אחיות" – שגיאת הידורתקיןשגיאת הידור
2One אינה Three – שגיאת הידורעובר הידור, נכשל בזמן ריצהFour יורשת מ-Two – תקיןFour יורשת מ-Two שיורשת מ-One – תקיןשגיאת הידור
3One יורשת מ-Three – תקיןOne יורשת מ-Three שיורשת מ-Two – תקיןFour יורשת מ-Two – תקיןFour אינה One (היא יורשת רק מ-Two) – שגיאת הידורשגיאת הידור
4One יורשת מ-Three – תקיןOne יורשת מ-Three שיורשת מ-Two – תקיןFour יורשת (דרך One ו-Three) מ-Two – תקיןFour יורשת מ-One – תקיןתקינה
5One יורשת מ-Three – תקיןTwo יורשת מ-One: עובר הידור, אבל העצם הוא One ולא Two – שגיאת זמן ריצהFour ו-Two שתיהן יורשות מ-One ("אחיות") – שגיאת הידורFour יורשת מ-One – תקיןשגיאת הידור

הסבר קצר לכל אפשרות:

1. השורה x1 מנסה לשים עצם One במשתנה Three, אבל One היא מחלקת הבסיס של Three ולא להפך – שגיאת הידור (וגם x3 שגויה).

2. אותה שגיאה בשורה x1 – שגיאת הידור.

3. השורות x1–x3 תקינות, אבל ב-x4 העצם Four יורש רק מ-Two ואין לו קשר ל-One – שגיאת הידור.

4. כל ההצבות הן "כלפי מעלה" לאורך השרשרת: Four יורשת מ-One, One מ-Three ו-Three מ-Two; וגם ההמרה (Two) של עצם One מצליחה כי One היא Two – התוכנית תקינה.

5. בשורה x3 המחלקות Four ו-Two שתיהן יורשות מ-One ואין ביניהן קשר ירושה – שגיאת הידור. (גם אילו תוקנה שורה זו, השורה x2 הייתה נכשלת בזמן ריצה, כי עצם One אינו Two.)

ב-C# התוצאות זהות.

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

סעיף ב

תשובה:

Circle: בנאי super(x) / base(x) ואתחול radius; toString מחזירה את תיאור הנקודה ועוד ", radius = " + radius. Cylinder: בנאי (x, radius, height) שקורא ל-super(x, radius) / base(x, radius) ומאתחל height; toString מחזירה super.toString() + ", height = " + height.

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

1. בנאי Circle – מקבל x ו-radius. את x אי אפשר להציב ישירות ב-Java (הוא private ב-Point), ולכן קוראים לבנאי של Point: super(x) (ב-C#: base(x)). אחר כך מאתחלים את radius.

2. toString של Circle – מוסיפה את הרדיוס לתיאור של הנקודה.

3. בנאי Cylinder – ב-main נקרא new Cylinder(10, 20, 30), ולכן צריך בנאי עם שלושה פרמטרים: super(x, radius) מאתחל את החלק של Circle (ודרכו את Point), ואחר כך height.

4. toString של Cylinder – מחזירה את התיאור של Circle (super.toString()) ומוסיפה ", height = " והגובה. כך בלי לשכפל קוד מתקבלת השורה השנייה.

Java:

public class Circle extends Point
{
    private int radius;

    public Circle(int x, int radius)
    {
        super(x);                    // את x מאתחלת Point
        this.radius = radius;
    }

    public String toString()
    {
        return super.toString() + ", radius = " + this.radius;
    }
}

public class Cylinder extends Circle
{
    private int height;

    public Cylinder(int x, int radius, int height)
    {
        super(x, radius);            // את x ו-radius מאתחלת Circle
        this.height = height;
    }

    public String toString()
    {
        return super.toString() + ", height = " + this.height;
    }
}

C#:

public class Circle : Point
{
    private int radius;

    public Circle(int x, int radius): base(x)   // את x מאתחלת Point
    {
        this.radius = radius;
    }

    public override string ToString()
    {
        return "x = " + x + ", radius = " + this.radius;   // x מוגדר protected ב-Point
    }
}

public class Cylinder : Circle
{
    private int height;

    public Cylinder(int x, int radius, int height): base(x, radius)
    {
        this.height = height;
    }

    public override string ToString()
    {
        return base.ToString() + ", height = " + this.height;
    }
}

הערה על Java: ב-Point של Java השדה x הוא private ואין לו פעולת get, ולכן Circle יכולה לקבל את x רק דרך super.toString(), שמחזירה בדיוק " x= " + x כפי שהיא כתובה בשאלה. לכן ב-Java השורות יודפסו כ-` x= 1, radius = 2` ו-` x= 10, radius = 20, height = 30` – אותו תוכן, וההבדל בריווח נובע מה-toString הנתונה של Point. אם רוצים את הריווח המדויק, אפשר לכתוב ב-Circle:

`return super.toString().trim().replace("x=", "x =") + ", radius = " + this.radius;`

ב-C# השדה x מוגדר protected, ולכן Circle ניגשת אליו ישירות והפלט זהה בדיוק לנדרש.

מעקב (C#): new Circle(1, 2) – base(1) מציב x = 1, ואז radius = 2; ToString מחזירה "x = 1, radius = 2". new Cylinder(10, 20, 30) – base(10, 20) בונה את חלק ה-Circle, ואז height = 30; ToString של Cylinder קוראת ל-ToString של Circle ומוסיפה ", height = 30".

תשובה: הבנאים ופעולות toString של Circle ו-Cylinder שלמעלה.

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

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

לדוגמה:

שרשרת החוליות הבאה מייצגת רשימה "סופר עולה":

א.

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

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

Java:

public static boolean isSuper(Node<Integer> n)

C#:

public static bool IsSuper(Node<int> n)
(7 נקודות)
ב.

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

אפשר להניח שמספר num גדול מאיבר הראשון בשרשרת.

לדוגמה: אפשר להוסיף לרשימה כל אחד מהמספרים 60, 90, 1200 שבאיור. לעומת זאת, כל אחד מהמספרים 15, 40, 700, אי אפשר להוסיף לשרשרת שבאיור והיא עדיין תישאר "סופר עולה".

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

Java:

public static boolean addToSuper(Node<Integer> n, int num)

C#:

public static bool AddToSuper(Node<int> n, int num)
(7 נקודות)
ג.

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

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

סעיף א

תשובה:

עוברים על השרשרת עם צובר sum של האיברים הקודמים; אם איבר כלשהו קטן או שווה ל-sum מחזירים false, אחרת מוסיפים אותו ל-sum; בסוף מחזירים true.

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

1. sum = 0 (לפני האיבר הראשון אין איברים).

2. לכל חוליה: אם הערך קטן או שווה ל-sum – האיבר אינו גדול מסכום קודמיו, ומחזירים false. (עבור האיבר הראשון זו בדיקה שהוא חיובי, כנדרש.)

3. אחרת מוסיפים את הערך ל-sum ועוברים לחוליה הבאה.

4. אם עברנו על כל השרשרת בלי לעצור – מחזירים true.

Java:

public static boolean isSuper(Node<Integer> n)
{
    int sum = 0;                     // סכום האיברים שלפני החוליה הנוכחית
    while (n != null)
    {
        if (n.getValue() <= sum)     // האיבר אינו גדול מסכום קודמיו
            return false;
        sum += n.getValue();
        n = n.getNext();
    }
    return true;
}

C#:

public static bool IsSuper(Node<int> n)
{
    int sum = 0;                     // סכום האיברים שלפני החוליה הנוכחית
    while (n != null)
    {
        if (n.GetValue() <= sum)     // האיבר אינו גדול מסכום קודמיו
            return false;
        sum += n.GetValue();
        n = n.GetNext();
    }
    return true;
}

בדיקה על הדוגמה: 1 > 0, 3 > 1, 6 > 4, 13 > 10, 27 > 23, 300 > 50, 600 > 350 – כל הבדיקות עוברות ומוחזר true. לעומת זאת עבור 1, 3, 4 מתקבל 4 ≤ 4 ומוחזר false.

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

סעיף ב

תשובה:

מוצאים את החוליה prev האחרונה שערכה קטן מ-num (תוך צבירת הסכום sum עד prev). אם num ≤ sum – false. אחרת בודקים שכל איבר שאחרי prev גדול מסכום קודמיו כולל num; אם כן – מכניסים חוליה חדשה אחרי prev ומחזירים true, אחרת false בלי שינוי.

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

בהכנסה במקום הזה צריך לבדוק שני תנאים:

•num עצמו גדול מסכום כל האיברים שלפניו.

•כל איבר שאחרי num עדיין גדול מסכום קודמיו – הסכום של כל אחד מהם גדל עכשיו ב-num.

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

1. מתקדמים עם prev מהחוליה הראשונה כל עוד הערך בחוליה הבאה קטן מ-num, וצוברים ב-sum את סכום הערכים עד prev כולל.

2. אם num ≤ sum – מחזירים false.

3. מציבים s = sum + num ועוברים על החוליות שאחרי prev: אם ערך כלשהו ≤ s – מחזירים false; אחרת מוסיפים אותו ל-s. (אם num שווה לאיבר קיים, האיבר הזה ייכשל כאן, כי הוא לא גדול מ-s.)

4. אם כל הבדיקות עברו – יוצרים חוליה חדשה עם num, שה-next שלה הוא החוליה שאחרי prev, ומחברים אותה אחרי prev. מחזירים true.

Java:

public static boolean addToSuper(Node<Integer> n, int num)
{
    // שלב 1: מחפשים את החוליה prev שאחריה num צריך להיכנס
    Node<Integer> prev = n;
    int sum = n.getValue();          // סכום האיברים עד prev כולל
    while (prev.hasNext() && prev.getNext().getValue() < num)
    {
        prev = prev.getNext();
        sum += prev.getValue();
    }

    // שלב 2: num חייב להיות גדול מסכום כל האיברים שלפניו
    if (num <= sum)
        return false;

    // שלב 3: כל איבר שאחרי num חייב להישאר גדול מסכום קודמיו (כולל num)
    int s = sum + num;
    Node<Integer> p = prev.getNext();
    while (p != null)
    {
        if (p.getValue() <= s)
            return false;
        s += p.getValue();
        p = p.getNext();
    }

    // שלב 4: ההכנסה חוקית - מכניסים את num אחרי prev
    prev.setNext(new Node<Integer>(num, prev.getNext()));
    return true;
}

C#:

public static bool AddToSuper(Node<int> n, int num)
{
    // שלב 1: מחפשים את החוליה prev שאחריה num צריך להיכנס
    Node<int> prev = n;
    int sum = n.GetValue();          // סכום האיברים עד prev כולל
    while (prev.HasNext() && prev.GetNext().GetValue() < num)
    {
        prev = prev.GetNext();
        sum += prev.GetValue();
    }

    // שלב 2: num חייב להיות גדול מסכום כל האיברים שלפניו
    if (num <= sum)
        return false;

    // שלב 3: כל איבר שאחרי num חייב להישאר גדול מסכום קודמיו (כולל num)
    int s = sum + num;
    Node<int> p = prev.GetNext();
    while (p != null)
    {
        if (p.GetValue() <= s)
            return false;
        s += p.GetValue();
        p = p.GetNext();
    }

    // שלב 4: ההכנסה חוקית - מכניסים את num אחרי prev
    prev.SetNext(new Node<int>(num, prev.GetNext()));
    return true;
}

בדיקה על הדוגמאות (השרשרת 1, 3, 6, 13, 27, 300, 600):

המספר numprev (האיבר האחרון הקטן מ-num)sum עד prevnum > sum?בדיקת האיברים שאחריתוצאה
602750כן300 > 110, 600 > 410true
902750כן300 > 140, 600 > 440true
1200600950כןאין איברים אחריtrue
151323לא (15 ≤ 23)–false
402750לא (40 ≤ 50)–false
700600950לא (700 ≤ 950)–false

התוצאות מתאימות לדוגמאות שבשאלה. למשל אחרי הוספת 60 השרשרת היא 1, 3, 6, 13, 27, 60, 300, 600.

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

סעיף ג

תשובה:

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

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

1. isSuper: לולאה אחת שעוברת על כל חוליה לכל היותר פעם אחת, עם מספר קבוע של פעולות בכל חוליה – O(n)O(n) (במקרה הגרוע, כשהרשימה אכן "סופר עולה", עוברים על כולה).

2. addToSuper: הלולאה הראשונה עוברת על החוליות עד prev, והלולאה השנייה ממשיכה מהחוליה שאחרי prev עד הסוף – יחד כל חוליה נבדקת פעם אחת לכל היותר, כלומר O(n)O(n). ההכנסה עצמה (יצירת חוליה ושינוי הפניה אחת) היא O(1)O(1).

תשובה: הסיבוכיות של שתי הפעולות היא O(n)O(n).

שאלה 6 · היררכיית עובדים במכללה: UML, בנאים וניהול צוות

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

למתרגל (Tutor) יש את התכונות:

•num – מספר עובד, מטיפוס שלם, int.

•name – שם, מטיפוס מחרוזת, String.

•courseNum – מספר קורס, מטיפוס שלם, int.

למרצה (Lecturer) יש את התכונות:

•num – מספר עובד, מטיפוס שלם, int.

•name – שם, מטיפוס מחרוזת, String.

•specialization – התמחות (מתמטיקה, מדעי המחשב, אנגלית וכו'), מטיפוס מחרוזת, String.

לראש מחלקה (Head) – ראש מחלקה הוא מרצה שאחראי על צוות שמונה עד עשרים מרצים ומתרגלים, יש את התכונות הבאות:

•arr – מערך של אנשי הצוות הכפופים לראש הצוות.

•current – מספר אנשי הצוות בפועל, מטיפוס שלם, int.

א.

סרטטו תרשים UML המתאר את הקשר בין המחלקות Employee, Tutor, Lecturer, Head באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.

(4 נקודות)
ב.

לכל אחת מהמחלקות Employee, Tutor, Lecturer, Head כתבו:

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

•תכונות.

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

הערה:

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

(6 נקודות)
ג.

המחלקה TeachingStaff מיועדת לנהל את כל העובדים במכללה. תכונות המחלקה:

•arr – מערך של כל אנשי הצוות. במכללה יכולים לעבוד לא יותר מ- 200 אנשי צוות.

•current – מספר אנשי הצוות בפועל, מטיפוס שלם, int.

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

1. פעולה בשם numHeads המחזירה את מספר הצוותים.

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

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

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

סעיף א

תשובה:

Employee מחלקה מופשטת (num, name, מונה סטטי); Tutor ו-Lecturer יורשות מ-Employee; Head יורשת מ-Lecturer ומכילה מערך של Employee (8 עד 20 אנשי צוות) ואת current.

שיקולים:

1. התכונות num ו-name משותפות למתרגל ולמרצה, ולכן מעבירים אותן למחלקת בסיס Employee – כך לא משכפלים קוד. כל עובד במכללה הוא מתרגל או מרצה, ולכן Employee מופשטת (abstract): לא יוצרים ממנה עצמים ישירות.

2. כדי שמספר העובד יינתן אוטומטית, ב-Employee יש תכונה סטטית counter – משותפת לכל העצמים – שהבנאי מגדיל ומעתיק ל-num.

3. Tutor יורשת מ-Employee ומוסיפה courseNum. Lecturer יורשת מ-Employee ומוסיפה specialization.

4. "ראש מחלקה הוא מרצה" – יחס "הוא" (is-a), ולכן Head יורשת מ-Lecturer (ויש לו גם התמחות).

5. לראש המחלקה יש צוות – יחס "יש לו" (has-a): Head מכילה מערך arr מטיפוס Employee[] (המערך יכול להחזיק גם מרצים וגם מתרגלים) בגודל 20, ו-current. בתרשים זה קשר הכלה (אגרגציה) מ-Head אל Employee עם ריבוי 8..20.

סימונים: `-` פרטי (private), `#` מוגן (protected), `+` ציבורי (public); החץ עם ראש משולש (^) – ירושה; `<>` – הכלה.

              +-----------------------------+
              |     Employee  {abstract}    |
              |-----------------------------|
              | - counter : int  {static}   |
              | # num : int                 |
              | # name : String             |
              |-----------------------------|
              | + Employee(name)            |
              +-----------------------------+
                  ^                     ^
                  |  (ירושה)            |  (ירושה)
   +---------------------------+   +-------------------------------+
   |          Tutor            |   |          Lecturer             |
   |---------------------------|   |-------------------------------|
   | - courseNum : int         |   | - specialization : String     |
   |---------------------------|   |-------------------------------|
   | + Tutor(name, courseNum)  |   | + Lecturer(name, spec.)       |
   +---------------------------+   +-------------------------------+
                                                  ^
                                                  |  (ירושה)
                                   +-------------------------------+
                                   |            Head               |
                                   |-------------------------------|
                                   | - arr : Employee[]            |<>------> Employee
                                   | - current : int               |  8..20
                                   |-------------------------------|
                                   | + Head(name, spec.)           |
                                   +-------------------------------+

תשובה: Employee (מופשטת) ← Tutor, Lecturer; Lecturer ← Head; Head מכילה מערך של Employee (8 עד 20).

סעיף ב

תשובה:

Employee: מונה סטטי counter, num, name; הבנאי מקבל name, מגדיל את counter ומציב num = counter. Tutor(name, courseNum), Lecturer(name, specialization) קוראות לבנאי של Employee; Head(name, specialization) קוראת לבנאי של Lecturer ויוצרת מערך Employee[20] עם current = 0.

הרעיון:

1. מספר עובד אוטומטי: ב-Employee מגדירים `private static int counter = 0`. תכונה סטטית שייכת למחלקה ולא לעצם, ולכן כל העצמים חולקים אותה. בכל יצירת עובד (מכל סוג – כי כל בנאי של מחלקה יורשת קורא בסוף לבנאי של Employee) הבנאי מגדיל את counter ומציב אותו ב-num: העובד הראשון יקבל 1, השני 2 וכן הלאה. num לא מועבר כפרמטר.

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

3. Head: הבנאי מקבל את מה שדרוש למרצה (שם והתמחות), יוצר מערך ריק בגודל 20 (המקסימום בצוות) ומאפס את current; אנשי הצוות יתווספו אחר כך.

4. התכונות num ו-name מוגדרות protected כדי שמחלקות יורשות יוכלו לגשת אליהן; שאר התכונות private.

Java:

public abstract class Employee
{
    private static int counter = 0;  // כמה עובדים נוצרו עד עכשיו
    protected int num;               // מספר עובד - נקבע אוטומטית
    protected String name;

    public Employee(String name)
    {
        counter++;
        this.num = counter;
        this.name = name;
    }
}

public class Tutor extends Employee
{
    private int courseNum;

    public Tutor(String name, int courseNum)
    {
        super(name);
        this.courseNum = courseNum;
    }
}

public class Lecturer extends Employee
{
    private String specialization;

    public Lecturer(String name, String specialization)
    {
        super(name);
        this.specialization = specialization;
    }
}

public class Head extends Lecturer
{
    private Employee[] arr;          // אנשי הצוות הכפופים לראש המחלקה
    private int current;             // מספר אנשי הצוות בפועל

    public Head(String name, String specialization)
    {
        super(name, specialization);
        this.arr = new Employee[20]; // לכל היותר עשרים אנשי צוות
        this.current = 0;
    }
}

C#:

public abstract class Employee
{
    private static int counter = 0;  // כמה עובדים נוצרו עד עכשיו
    protected int num;               // מספר עובד - נקבע אוטומטית
    protected string name;

    public Employee(string name)
    {
        counter++;
        this.num = counter;
        this.name = name;
    }
}

public class Tutor : Employee
{
    private int courseNum;

    public Tutor(string name, int courseNum) : base(name)
    {
        this.courseNum = courseNum;
    }
}

public class Lecturer : Employee
{
    private string specialization;

    public Lecturer(string name, string specialization) : base(name)
    {
        this.specialization = specialization;
    }
}

public class Head : Lecturer
{
    private Employee[] arr;          // אנשי הצוות הכפופים לראש המחלקה
    private int current;             // מספר אנשי הצוות בפועל

    public Head(string name, string specialization) : base(name, specialization)
    {
        this.arr = new Employee[20]; // לכל היותר עשרים אנשי צוות
        this.current = 0;
    }
}

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

סעיף ג

תשובה:

TeachingStaff: Employee[] arr בגודל 200 ו-current. numHeads סופרת את האיברים ב-arr[0..current-1] שהם Head. getNewTutor עוברת על המערך, בוחרת מבין העצמים שהם Tutor עם courseNum המבוקש את בעל מספר העובד הגדול ביותר, ומחזירה אותו או null.

הרעיון:

1. תכונות: מערך arr מטיפוס Employee[] בגודל 200 – טיפוס הבסיס מאפשר לשמור בו מתרגלים, מרצים וראשי מחלקות. current מציין כמה תאים בשימוש (התאים 0 עד current-1).

2. numHeads: לכל צוות יש ראש מחלקה אחד, ולכן מספר הצוותים הוא מספר העצמים מטיפוס Head במערך. עוברים על התאים התפוסים ובודקים כל עצם עם instanceof (ב-C#: is) – מונים את אלה שהם Head.

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

•result = null (עוד לא נמצא מתרגל מתאים).

•לכל עצם שהוא Tutor ממירים אותו ל-Tutor (המרה כלפי מטה, כדי לגשת ל-getCourseNum), ואם הקורס שלו הוא המבוקש ו-result עדיין null או שמספר העובד שלו גדול משל result – מעדכנים את result.

•בסוף מחזירים את result; אם אף מתרגל לא לימד בקורס, הוא נשאר null, כנדרש.

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

Java:

public class TeachingStaff
{
    private Employee[] arr;          // כל אנשי הצוות במכללה
    private int current;             // מספר אנשי הצוות בפועל

    public TeachingStaff()
    {
        this.arr = new Employee[200];
        this.current = 0;
    }

    // 1. מספר הצוותים = מספר ראשי המחלקות
    public int numHeads()
    {
        int count = 0;
        for (int i = 0; i < current; i++)
            if (arr[i] instanceof Head)
                count++;
        return count;
    }

    // 2. המתרגל בקורס courseNum עם מספר העובד הגדול ביותר
    public Tutor getNewTutor(int courseNum)
    {
        Tutor result = null;
        for (int i = 0; i < current; i++)
        {
            if (arr[i] instanceof Tutor)
            {
                Tutor t = (Tutor) arr[i];
                if (t.getCourseNum() == courseNum &&
                    (result == null || t.getNum() > result.getNum()))
                    result = t;
            }
        }
        return result;
    }
}

C#:

public class TeachingStaff
{
    private Employee[] arr;          // כל אנשי הצוות במכללה
    private int current;             // מספר אנשי הצוות בפועל

    public TeachingStaff()
    {
        this.arr = new Employee[200];
        this.current = 0;
    }

    // 1. מספר הצוותים = מספר ראשי המחלקות
    public int NumHeads()
    {
        int count = 0;
        for (int i = 0; i < current; i++)
            if (arr[i] is Head)
                count++;
        return count;
    }

    // 2. המתרגל בקורס courseNum עם מספר העובד הגדול ביותר
    public Tutor GetNewTutor(int courseNum)
    {
        Tutor result = null;
        for (int i = 0; i < current; i++)
        {
            if (arr[i] is Tutor)
            {
                Tutor t = (Tutor) arr[i];
                if (t.GetCourseNum() == courseNum &&
                    (result == null || t.GetNum() > result.GetNum()))
                    result = t;
            }
        }
        return result;
    }
}

סיבוכיות: כל פעולה עוברת פעם אחת על current התאים – O(n)O(n).

תשובה: המחלקה TeachingStaff שלמעלה עם הפעולות numHeads ו-getNewTutor.

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

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

Java:

public static void what(Stack<Integer> s)
{
   if (!s.isEmpty())
    {
      System.out.print(s.pop()+" ");
      what(s);
    }
}
public static void doWhat(BinNode<Integer> t, int data)
 {
      Stack<Integer>s = new Stack<Integer>();
      doWhat(t, s, data);
  }
private static void doWhat(BinNode<Integer> t, Stack<Integer> s,
                            int val)
{
    if (t!=null)
     {
       int x = t.getValue();
       s.push(x);
       if(x == val)
       {
         what(s);
       }
       else
       {
         doWhat(t.getLeft(), s, val);
               if (!s.isEmpty())
                 doWhat(t.getRight(), s, val);
               if (!s.isEmpty())
                 s.pop();
          }
      }
 }

C#:

public static void What(Stack<int> s)
{
   if (!s.IsEmpty())
    {
      Console.Write(s.Pop()+" ");
      What(s);
    }
}
public static void DoWhat(BinNode<int> t, int data)
 {
      Stack<int>s = new Stack<int>();
      DoWhat(t, s, data);
  }
private static void DoWhat(BinNode<int> t, Stack<int> s,
                            int val)
{
    if (t!=null)
     {
       int x = t.GetValue();
       s.Push(x);
       if(x == val)
       {
         What(s);
       }
       else
       {
         DoWhat(t.GetLeft(), s, val);
              if (!s.IsEmpty())
                DoWhat(t.GetRight(), s, val);
              if (!s.IsEmpty())
                s.Pop();
          }
      }
 }
א.

מה מבצעת הפעולה what(Stack<Integer> s) עבור מחסנית של מספרים שלמים s?

(2 נקודות)
ב.

עקבו אחרי זימון הפעולה doWhat(bt,3) עבור עץ bt שבאיור וכתבו מה יהיה הפלט של הזימון.

(6 נקודות)
ג.

עקבו אחרי זימון הפעולה doWhat(bt,5) עבור עץ bt שבאיור וכתבו מה יהיה הפלט של הזימון.

(6 נקודות)
ד.

מה יהיה פלט של זימון הפעולה doWhat(bt,10) עבור עץ bt שבאיור?

(2 נקודות)
ה.

מה מבצעת הפעולה doWhat(t, val) עבור עץ בינרי t ומספר שלם val באופן כללי?

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

סעיף א

תשובה:

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

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

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

תשובה: what מדפיסה את כל איברי s מהראש עד התחתית ומרוקנת את המחסנית.

סעיף ב

תשובה:

3 2 1

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

המחסנית רשומה כשהראש משמאל.

שלבצומת tמה קורההמחסנית אחרי השלבפלט
11push 1; 1 ≠ 3 – קריאה לבן השמאלי (2)1
22push 2; 2 ≠ 3 – קריאה לבן השמאלי (3)2, 1
33push 3; 3 == 3 – קריאה ל-what3, 2, 1
4–what מוציאה ומדפיסה 3, 2, 1ריקה3 2 1
52חוזרים לצומת 2: המחסנית ריקה – לא יורדים ימינה ולא מוציאיםריקה
61חוזרים לצומת 1: המחסנית ריקה – לא יורדים ימינה ולא מוציאיםריקה

תשובה: יודפס `3 2 1`.

סעיף ג

תשובה:

5 4 2 1

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

שלבצומת tמה קורההמחסנית אחרי השלבפלט
11push 1; 1 ≠ 5 – קריאה לבן השמאלי (2)1
22push 2; 2 ≠ 5 – קריאה לבן השמאלי (3)2, 1
33push 3; 3 ≠ 5 – שמאל: null; המחסנית לא ריקה – ימין: null; המחסנית לא ריקה – pop2, 1
42המחסנית לא ריקה – קריאה לבן הימני (4)2, 1
54push 4; 4 ≠ 5 – קריאה לבן השמאלי (5)4, 2, 1
65push 5; 5 == 5 – קריאה ל-what5, 4, 2, 1
7–what מוציאה ומדפיסה 5, 4, 2, 1ריקה5 4 2 1
84, 2, 1בחזרה בכל צומת המחסנית ריקה – לא יורדים ימינה ולא מוציאיםריקה

הצומת 3 נכנס למחסנית ויצא ממנה (הוא לא על המסלול ל-5), ולכן לא מודפס.

תשובה: יודפס `5 4 2 1`.

סעיף ד

תשובה:

לא יודפס דבר.

הערך 10 לא נמצא בעץ, ולכן התנאי x == val לא מתקיים אף פעם ו-what לא נקראת. הסריקה עוברת על כל הצמתים בסדר תחילי (1, 2, 3, 4, 5, 6, 7): כל צומת נדחף כשנכנסים אליו ומוצא כשמסיימים את שני תת-העצים שלו. המחסנית אף פעם לא מתרוקנת באמצע (תמיד נשארים בה לפחות אבות הצומת הנוכחי), ובסוף, אחרי ה-pop של 1, היא ריקה.

תשובה: אין פלט (לא יודפס כלום).

סעיף ה

תשובה:

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

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

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

שאלה 8 · מעקב אחרי ירושה, דריסה, super והמרות

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

Java:

public class A
{
    public A()
    {
        System.out.println("A");
    }

     public void one()
     {
         System.out.println("one of A");
     }

     public void two()
     {
         System.out.println("two of A");
         this.one();
     }

    public void four()
    {
        System.out.println ("four of A");
        this.two();
    }
} //end of class A

public class B extends A
{
    public B()
    {
        System.out.println("B");
    }

     public void one()
     {
         System.out.println("one of B");
     }

     public void two()
     {
         System.out.println("two of B");
     }

    public void three()
    {
        System.out.println("three of B");
        super.two();
    }
} //end of class B

public class C extends B
{
    public void four()
    {
        System.out.println ("four of C");
    }
} //end of class C

C#:

public class A
{
    public A()
    {
        Console.WriteLine("A");
    }

     public virtual void One()
     {
         Console.WriteLine("One of A");
     }

     public virtual void Two()
     {
         Console.WriteLine("Two of A");
         this.One();
     }

    public virtual void Four()
    {
        Console.WriteLine ("Four of A");
        this.Two();
    }
} //end of class A

public class B : A
{
    public B()
    {
        Console.WriteLine("B");
    }

     public override void One()
     {
         Console.WriteLine("One of B");
     }

     public override void Two()
     {
         Console.WriteLine("Two of B");
     }

    public void Three()
    {
        Console.WriteLine("Three of B");
        base.Two();
    }
} //end of class B

public class C : B
{
    public override void Four()
    {
        Console.WriteLine ("Four of C");
    }
} //end of class C

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

Java:

public class Test
{
    public static void main (String [] args)
    {

         // כאן יופיעו הפקודות שבסעיפים להלן

     }
}

C#:

public class Test
{
    public static void Main(string [] args)
    {

         // כאן יופיעו הפקודות שבסעיפים להלן

     }
}

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

א.

Java:

A a1 = new A();
((B) a1).two();

C#:

A a1 = new A();
((B) a1).Two();
(3 נקודות)
ב.

Java:

B b1 = new B();
((A) b1).three();

C#:

B b1 = new B();
((A) b1).Three();
(3 נקודות)
ג.

Java:

A a2 = new A();
a2.one();
((A) a2).two();

C#:

A a2 = new A();
a2.One();
((A) a2).Two();
(3 נקודות)
ד.

Java:

A a3 = new B();
a3.two();
((B) a3).two();
((B) a3).three();

C#:

A a3 = new B();
a3.Two();
((B) a3).Two();
((B) a3).Three();
(3 נקודות)
ה.

Java:

B b2 = new B();
b2.two();
((A) b2).two();

C#:

B b2 = new B();
b2.Two();
((A) b2).Two();
(3 נקודות)
ו.

Java:

B b3 = new C();
b3.four();
((B)new C()).four();

C#:

B b3 = new C();
b3.Four();
((B)new C()).Four();
(3 נקודות)
◂ פתרון מלא לשאלה 8

סעיף א

תשובה:

יודפס A ואז שגיאת זמן ריצה (ClassCastException ב-Java, InvalidCastException ב-C#).

1. `new A()` מפעיל את הבנאי של A – מודפס `A`.

2. `((B) a1)` – ההמרה עוברת הידור, כי B יורשת מ-A ומשתנה מטיפוס A יכול להפנות לעצם B. אבל בזמן ריצה העצם הוא A ולא B, ולכן ההמרה נכשלת: שגיאת זמן ריצה ClassCastException (ב-C#: InvalidCastException). two לא מופעלת.

A

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

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

סעיף ב

תשובה:

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

המהדר בודק אילו פעולות מותר לזמן לפי הטיפוס המוצהר של הביטוי. הביטוי `((A) b1)` הוא מטיפוס A, ובמחלקה A אין פעולה three (היא מוגדרת רק ב-B). לכן זו שגיאת הידור (cannot find symbol; ב-C#: 'A' does not contain a definition for 'Three'), והתוכנית לא רצה כלל – לא יודפס דבר, גם לא A ו-B של הבנאים.

תשובה: שגיאת הידור – לא ניתן לזמן את three על הפניה מטיפוס A.

סעיף ג

תשובה:

A / one of A / two of A / one of A

1. `new A()` – מודפס `A`.

2. `a2.one()` – העצם הוא A – מודפס `one of A`.

3. `((A) a2).two()` – ההמרה ל-A לא משנה דבר. two של A מדפיסה `two of A` וקוראת ל-`this.one()`; this הוא עצם A, ולכן מודפס `one of A`.

פלט ב-Java:

A
one of A
two of A
one of A

פלט ב-C#:

A
One of A
Two of A
One of A

תשובה: A, one of A, two of A, one of A.

סעיף ד

תשובה:

A / B / two of B / two of B / three of B / two of A / one of B

1. `new B()` – הבנאי של B קורא קודם (במובלע) לבנאי של A: מודפס `A` ואחריו `B`.

2. `a3.two()` – הטיפוס המוצהר A (יש בו two – ההידור תקין), והעצם בפועל B. הפעולה נדרסה ב-B, ולכן מופעלת two של B: `two of B`.

3. `((B) a3).two()` – ההמרה תקינה (העצם הוא B) – שוב `two of B`.

4. `((B) a3).three()` – three של B מדפיסה `three of B` וקוראת ל-`super.two()` (ב-C#: base.Two()) – זו קריאה ישירה ל-two של A, בלי פולימורפיזם: מודפס `two of A`. בתוכה `this.one()` – this הוא עצם B ו-one נדרסה ב-B, ולכן מודפס `one of B`.

פלט ב-Java:

A
B
two of B
two of B
three of B
two of A
one of B

פלט ב-C#:

A
B
Two of B
Two of B
Three of B
Two of A
One of B

תשובה: A, B, two of B, two of B, three of B, two of A, one of B.

סעיף ה

תשובה:

A / B / two of B / two of B

1. `new B()` – מודפס `A` ואחריו `B`.

2. `b2.two()` – two של B: `two of B`.

3. `((A) b2).two()` – ההמרה ל-A משנה רק את הטיפוס המוצהר; הפעולה שמופעלת נקבעת לפי העצם בפועל (B), ולכן שוב two של B: `two of B`.

פלט ב-Java:

A
B
two of B
two of B

פלט ב-C#:

A
B
Two of B
Two of B

תשובה: A, B, two of B, two of B.

סעיף ו

תשובה:

A / B / four of C / A / B / four of C

1. `new C()` – ל-C אין בנאי מפורש, ולכן יש לה בנאי ברירת מחדל שקורא לבנאי של B, שקורא לבנאי של A: מודפס `A` ואחריו `B`.

2. `b3.four()` – לטיפוס המוצהר B יש four (בירושה מ-A) – ההידור תקין. העצם הוא C, ו-four נדרסה ב-C: `four of C`.

3. `((B)new C()).four()` – נוצר עצם C חדש – שוב `A` ו-`B` – ההמרה ל-B תקינה, ומופעלת four של C: `four of C`.

פלט ב-Java:

A
B
four of C
A
B
four of C

פלט ב-C#:

A
B
Four of C
A
B
Four of C

תשובה: A, B, four of C, A, B, four of C.

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

נתונה הפעולה הרקורסיבית הבאה:

Java:

public static int secret(Stack<Integer> s1, Stack<Integer> s2)
{
       if(s1.isEmpty() || s2.isEmpty())
             return 0;
       if(s1.top() > s2.top())
             return s1.pop() + s2.top() + secret(s1, s2);
       else
             return s1.top() + s2.pop() + secret(s1, s2);
}

C#:

public static int Secret(Stack<int> s1, Stack<int> s2)
{
       if(s1.IsEmpty() || s2.IsEmpty())
             return 0;
       if(s1.Top() > s2.Top())
             return s1.Pop() + s2.Top() + Secret(s1, s2);
       else
             return s1.Top() + s2.Pop() + Secret(s1, s2);
}
א.

נתונות שתי המחסניות הבאות:

עקבו אחרי זימון הפעולה secret(st1, st2) וכתבו מה תחזיר הפעולה.

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

(8 נקודות)
ב.

נתונה הטענה הבאה:

secret(s1, s2) == secret(s2, s1)

האם הטענה נכונה לכל זוג מחסניות של מספרים שלמים s1 ו- s2? נמקו את תשובתכם.

אם הטענה לא נכונה, יש להביא דוגמה של זוג מחסניות s1 ו- s2 מתאים.

(4 נקודות)
ג.

נתונות שתי המחסניות הבאות:

האם קיים ערך X כזה שתוצאת זימון הפעולה secret(s1, s2) תהיה 19?

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

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

סעיף א

תשובה:

33 (בסוף s1 מכילה −1-1, 1 ו-s2 ריקה).

איך הפעולה עובדת: בכל קריאה משווים את שני הראשים. מוסיפים לתוצאה את שני הראשים, ומוציאים את הראש של המחסנית שראשה גדול יותר (ב-s1 – רק אם גדול ממש; בשוויון מוציאים מ-s2). מסתיימים כשאחת המחסניות מתרוקנת. (הזימון רשום בשאלה כ-secret(st1, st2); הכוונה למחסניות s1 ו-s2 שבאיור.)

המחסניות רשומות כשהראש משמאל: s1 = 7, 6, −1-1, 1 ו-s2 = 5, 2, 4, 3.

קריאהs1 לפניs2 לפניהשוואהפעולהערך שמתווסףs1 אחריs2 אחרי
17, 6, −1-1, 15, 2, 4, 37 > 5pop מ-s17+5=127+5=126, −1-1, 15, 2, 4, 3
26, −1-1, 15, 2, 4, 36 > 5pop מ-s16+5=116+5=11−1-1, 15, 2, 4, 3
3−1-1, 15, 2, 4, 3−1-1 ≤ 5pop מ-s2−1+5=4-1+5=4−1-1, 12, 4, 3
4−1-1, 12, 4, 3−1-1 ≤ 2pop מ-s2−1+2=1-1+2=1−1-1, 14, 3
5−1-1, 14, 3−1-1 ≤ 4pop מ-s2−1+4=3-1+4=3−1-1, 13
6−1-1, 13−1-1 ≤ 3pop מ-s2−1+3=2-1+3=2−1-1, 1ריקה
7−1-1, 1ריקהs2 ריקהreturn 00−1-1, 1ריקה

הערך המוחזר הוא סכום הערכים שהתווספו בכל הקריאות:

12+11+4+1+3+2+0=3312+11+4+1+3+2+0=33

בסוף הזימון ב-s1 נשארו −1-1 (בראש) ו-1, ו-s2 ריקה.

תשובה: הפעולה תחזיר 33.

סעיף ב

תשובה:

לא. כשהראשים שווים, secret(s1, s2) מוציאה מ-s2 ו-secret(s2, s1) מוציאה מ-s1. דוגמה: s1 = 5, s2 = 5, 1 (5 בראש): secret(s1, s2) = 16, secret(s2, s1) = 10.

ניתוח: כשהראשים שונים, שתי הקריאות מתנהגות אותו דבר: בשתיהן מוציאים את הראש הגדול מבין השניים ומוסיפים לתוצאה את סכום שני הראשים (החיבור חילופי). ההבדל מופיע רק כשהראשים שווים: אז התנאי `s1.top() > s2.top()` לא מתקיים ונבחר ה-else, שמוציא תמיד מהמחסנית שהועברה כפרמטר השני. ב-secret(s1, s2) יוצא איבר מ-s2, וב-secret(s2, s1) יוצא איבר מ-s1. מכאן ההמשך שונה, והתוצאה יכולה להיות שונה.

דוגמה נגדית (בכל זימון מתחילים מאותן מחסניות; הראש משמאל): s1 = 5 ו-s2 = 5, 1.

secret(s1, s2):

1. ראשים 5 ו-5 – שווים, else: 5+5=105+5=10, מוציאים מ-s2. עכשיו s1 = 5, s2 = 1.

2. 5 > 1 – מוציאים מ-s1: 5+1=65+1=6. s1 ריקה.

3. מוחזר 0.

סך הכול 10+6+0=1610+6+0=16.

secret(s2, s1) (עכשיו הפרמטר הראשון הוא 5, 1 והשני הוא 5):

1. ראשים 5 ו-5 – שווים, else: 5+5=105+5=10, מוציאים מהפרמטר השני (המחסנית 5), והיא מתרוקנת.

2. מוחזר 0.

סך הכול 10+0=1010+0=10.

16≠1016 \ne 10, ולכן הטענה לא נכונה לכל זוג מחסניות.

תשובה: הטענה לא נכונה. דוגמה: s1 = 5, s2 = 5, 1 (5 בראש) – secret(s1, s2) = 16 אבל secret(s2, s1) = 10.

סעיף ג

תשובה:

כן – יש שני ערכים: X = 1 או X = 7.

המחסניות (הראש משמאל): s1 = 4, X, −1-1 ו-s2 = 1, 2, 3, 4.

הקריאה הראשונה: 4 > 1 – מוציאים 4 מ-s1, ומתווסף 4+1=54+1=5. עכשיו s1 = X, −1-1 ו-s2 = 1, 2, 3, 4. ההמשך תלוי בהשוואה בין X לבין 1.

מקרה 1: X > 1.

1. X > 1 – מוציאים את X מ-s1, ומתווסף X+1X+1. s1 = −1-1.

2. −1-1 קטן מכל איברי s2, ולכן מוציאים את כולם אחד-אחד, ומתווספים −1+1=0-1+1=0, −1+2=1-1+2=1, −1+3=2-1+3=2, −1+4=3-1+4=3. s2 מתרוקנת ומוחזר 0.

סך הכול: 5+(X+1)+0+1+2+3=X+125+(X+1)+0+1+2+3=X+12.

X+12=19⇒X=7X+12=19 \Rightarrow X=7, ואכן 7>17>1 – הערך מתאים למקרה.

מקרה 2: X ≤ 1.

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

סך הכול: 5+(X+1)+(X+2)+(X+3)+(X+4)=4X+155+(X+1)+(X+2)+(X+3)+(X+4)=4X+15.

4X+15=19⇒X=14X+15=19 \Rightarrow X=1, ואכן 1≤11\le 1 – הערך מתאים למקרה.

בדיקה:

•עבור X = 1: 5+2+3+4+5=195+2+3+4+5=19.

•עבור X = 7: 5+8+0+1+2+3=195+8+0+1+2+3=19.

תשובה: כן. קיימים שני ערכים מתאימים: X = 1 ו-X = 7.

שאלה 10 · מחלקת קבוצת מספרים דרך ממשק בלבד

הגדרה:

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

לפניכם ממשק חלקי של המחלקה SetOfNumbers המייצגת קבוצת מספרים שלמים.

כותרת הפעולהתיאור הפעולה
`public SetOfNumbers ()`הפעולה בונה קבוצת מספרים ריקה
`public void addToSet(int num)` (C#: `public void AddToSet(int num)`)הפעולה מוסיפה לקבוצה את המספר num, אם המספר לא נמצא בקבוצה. אם num כבר נמצא בקבוצה, הפעולה לא עושה דבר
`public void removeFromSet(int num)` (C#: `public void RemoveFromSet(int num)`)הפעולה מוחקת מהקבוצה את המספר num, אם הוא נמצא בקבוצה. אם num לא נמצא בקבוצה, הפעולה לא עושה דבר
`public int getMax()` (C#: `public int GetMax()`)הפעולה מחזירה את מספר הגדול בקבוצה. הנחה: הקבוצה לא ריקה
`public boolean isEmpty()` (C#: `public bool IsEmpty()`)הפעולה מחזירה true אם הקבוצה הנוכחית ריקה, אחרת – הפעולה מחזירה false

שמו לב! מימוש של המחלקה SetOfNumbers לא ידוע, אפשר להשתמש אך ורק בפעולות הנתונות בממשק!

א.

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

הנחה: הקבוצה לא ריקה.

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

Java:

public int getMin()

C#:

public int GetMin()
(6 נקודות)
ב.

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

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

Java:

public boolean equals(SetOfNumbers other)

C#:

public bool Equals(SetOfNumbers other)
(6 נקודות)
ג.

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

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

Java:

public static SetOfNumbers make(SetOfNumbers sn)

C#:

public static SetOfNumbers Make(SetOfNumbers sn)
(4 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

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

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

1. יוצרים קבוצת עזר temp ריקה.

2. כל עוד this לא ריקה: min = getMax(), מוחקים את min מ-this ומוסיפים אותו ל-temp.

3. בסוף הלולאה min מכיל את האיבר האחרון שהוצא – המינימום.

4. מעבירים את כל האיברים מ-temp חזרה ל-this (שוב בעזרת getMax ו-removeFromSet).

5. מחזירים את min.

Java:

public int getMin()
{
    SetOfNumbers temp = new SetOfNumbers();
    int min = 0;
    while (!this.isEmpty())          // מוציאים כל פעם את הגדול ביותר
    {
        min = this.getMax();
        this.removeFromSet(min);
        temp.addToSet(min);
    }
    // האיבר האחרון שהוצא הוא הקטן ביותר
    while (!temp.isEmpty())          // משחזרים את הקבוצה
    {
        int x = temp.getMax();
        temp.removeFromSet(x);
        this.addToSet(x);
    }
    return min;
}

C#:

public int GetMin()
{
    SetOfNumbers temp = new SetOfNumbers();
    int min = 0;
    while (!this.IsEmpty())          // מוציאים כל פעם את הגדול ביותר
    {
        min = this.GetMax();
        this.RemoveFromSet(min);
        temp.AddToSet(min);
    }
    // האיבר האחרון שהוצא הוא הקטן ביותר
    while (!temp.IsEmpty())          // משחזרים את הקבוצה
    {
        int x = temp.GetMax();
        temp.RemoveFromSet(x);
        this.AddToSet(x);
    }
    return min;
}

דוגמה: בקבוצה {9, −12-12, 40} יוצאים בסדר 40, 9, −12-12, ולכן מוחזר −12-12, והקבוצה משוחזרת.

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

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

סעיף ב

תשובה:

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

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

1. יוצרים שתי קבוצות עזר temp1 (לאיברים של this) ו-temp2 (לאיברים של other), ומשתנה same = true.

2. כל עוד same, ושתי הקבוצות לא ריקות: משווים את getMax של שתיהן. אם המקסימומים שונים – same = false (יש איבר שנמצא באחת ולא בשנייה). אם שווים – מוחקים את המקסימום משתי הקבוצות ושומרים אותו בקבוצות העזר.

3. אחרי הלולאה, אם נשארו איברים באחת הקבוצות (גם כשהשנייה כבר ריקה) – הקבוצות בגודל שונה, same = false.

4. משחזרים את שתי הקבוצות מקבוצות העזר – הפעולה לא אמורה לשנות את this ולא את other.

5. מחזירים את same.

Java:

public boolean equals(SetOfNumbers other)
{
    SetOfNumbers temp1 = new SetOfNumbers();   // מה שהוצא מ-this
    SetOfNumbers temp2 = new SetOfNumbers();   // מה שהוצא מ-other
    boolean same = true;
    while (same && !this.isEmpty() && !other.isEmpty())
    {
        int m1 = this.getMax();
        int m2 = other.getMax();
        if (m1 != m2)
            same = false;
        else
        {
            this.removeFromSet(m1);
            temp1.addToSet(m1);
            other.removeFromSet(m2);
            temp2.addToSet(m2);
        }
    }
    if (!this.isEmpty() || !other.isEmpty())   // נשארו איברים באחת הקבוצות
        same = false;

    while (!temp1.isEmpty())                   // משחזרים את this
    {
        int x = temp1.getMax();
        temp1.removeFromSet(x);
        this.addToSet(x);
    }
    while (!temp2.isEmpty())                   // משחזרים את other
    {
        int x = temp2.getMax();
        temp2.removeFromSet(x);
        other.addToSet(x);
    }
    return same;
}

C#:

public bool Equals(SetOfNumbers other)
{
    SetOfNumbers temp1 = new SetOfNumbers();   // מה שהוצא מ-this
    SetOfNumbers temp2 = new SetOfNumbers();   // מה שהוצא מ-other
    bool same = true;
    while (same && !this.IsEmpty() && !other.IsEmpty())
    {
        int m1 = this.GetMax();
        int m2 = other.GetMax();
        if (m1 != m2)
            same = false;
        else
        {
            this.RemoveFromSet(m1);
            temp1.AddToSet(m1);
            other.RemoveFromSet(m2);
            temp2.AddToSet(m2);
        }
    }
    if (!this.IsEmpty() || !other.IsEmpty())   // נשארו איברים באחת הקבוצות
        same = false;

    while (!temp1.IsEmpty())                   // משחזרים את this
    {
        int x = temp1.GetMax();
        temp1.RemoveFromSet(x);
        this.AddToSet(x);
    }
    while (!temp2.IsEmpty())                   // משחזרים את other
    {
        int x = temp2.GetMax();
        temp2.RemoveFromSet(x);
        other.AddToSet(x);
    }
    return same;
}

דוגמאות: {1, 5, 9} ו-{9, 5, 1}: המקסימומים 9=9, 5=5, 1=1 ושתיהן מתרוקנות יחד – true. {1, 5, 9} ו-{5, 9}: 9=9, 5=5, ואז השנייה ריקה והראשונה לא – false. {1, 5, 9} ו-{1, 4, 9}: 9=9 ואז 5≠4 – false.

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

סעיף ג

תשובה:

מוציאים את כל איברי sn (בעזרת getMax) לקבוצת עזר; כל איבר שערכו המוחלט בין 10 ל-99 מוסיפים גם לקבוצה החדשה; בסוף מחזירים את האיברים מקבוצת העזר ל-sn ומחזירים את הקבוצה החדשה.

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

1. יוצרים קבוצה חדשה result וקבוצת עזר temp.

2. כל עוד sn לא ריקה: x = sn.getMax(), מוחקים את x מ-sn ומוסיפים ל-temp.

3. מספר שלם הוא דו-ספרתי אם הערך המוחלט שלו בין 10 ל-99 (כך נכללים גם מספרים שליליים כמו −45-45). אם כן – מוסיפים את x ל-result.

4. מחזירים את כל האיברים מ-temp ל-sn.

5. מחזירים את result.

Java:

public static SetOfNumbers make(SetOfNumbers sn)
{
    SetOfNumbers result = new SetOfNumbers();  // הקבוצה החדשה
    SetOfNumbers temp = new SetOfNumbers();    // לשחזור sn
    while (!sn.isEmpty())
    {
        int x = sn.getMax();
        sn.removeFromSet(x);
        temp.addToSet(x);
        int a = Math.abs(x);
        if (a >= 10 && a <= 99)                // מספר דו-ספרתי
            result.addToSet(x);
    }
    while (!temp.isEmpty())                    // מחזירים את המספרים ל-sn
    {
        int x = temp.getMax();
        temp.removeFromSet(x);
        sn.addToSet(x);
    }
    return result;
}

C#:

public static SetOfNumbers Make(SetOfNumbers sn)
{
    SetOfNumbers result = new SetOfNumbers();  // הקבוצה החדשה
    SetOfNumbers temp = new SetOfNumbers();    // לשחזור sn
    while (!sn.IsEmpty())
    {
        int x = sn.GetMax();
        sn.RemoveFromSet(x);
        temp.AddToSet(x);
        int a = Math.Abs(x);
        if (a >= 10 && a <= 99)                // מספר דו-ספרתי
            result.AddToSet(x);
    }
    while (!temp.IsEmpty())                    // מחזירים את המספרים ל-sn
    {
        int x = temp.GetMax();
        temp.RemoveFromSet(x);
        sn.AddToSet(x);
    }
    return result;
}

דוגמה: עבור sn = {5, −12-12, 40, 99, 100, 10, 9} תוחזר הקבוצה {−12-12, 10, 40, 99}, ו-sn נשארת כפי שהייתה.

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

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

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

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