מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2023 מועד א'
הנדסת תוכנה · סמל 97105 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2023 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 16)
בכל מבחן 10 שאלות.
שאלות 1-4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 5-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 9-10: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.
חומר עזר: 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` אחרי הכנסתו).
כותרת הפעולה:
public static int putInPlace(Queue<Integer> q, int num)public static int PutInPlace(Queue<int> q, int num)

כתבו פעולה חיצונית המקבלת תור `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
כותרת הפעולה:
public static void moveToFront(Queue<Integer> q, int k)public static void MoveToFront(Queue<int> q, int k)מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
מרוקנים את `q` לשני תורי עזר (קטנים מ-`num` / גדולים או שווים), מחזירים לתור את הקטנים, אחריהם את `num` ואחריו את הגדולים; המיקום המוחזר הוא מספר הקטנים ועוד 1.
הרעיון: את התור אפשר לעבור רק מהראש, ולכן מפצלים אותו לשני תורי עזר:
1. מוציאים את כל איברי `q`. כל איבר קטן מ-`num` נכנס לתור `small`, וכל איבר גדול או שווה ל-`num` נכנס לתור `big`.
2. `q` עכשיו ריק. מכניסים אליו בחזרה את כל איברי `small` וסופרים אותם. המשתנה `place` מתחיל ב-1, ולכן אחרי הלולאה הוא שווה למספר הקטנים ועוד 1 - בדיוק המיקום הסידורי של `num`.
3. מכניסים את `num`, ואחריו את כל איברי `big`.
4. מחזירים את `place`.
כך כל הקטנים לפני `num` וכל הגדולים או השווים אחריו, כנדרש (הסדר בתוך כל קבוצה נשמר, אבל הוא ממילא לא חשוב).
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;
}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` האחרונים הגיעו לראש התור.
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());
}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` סיבובים של ראש התור לסופו).
סעיף ג
שתי הפעולות , כאשר מספר האיברים בתור.
נסמן ב- את מספר האיברים בתור.
1. סעיף א' (`putInPlace`): כל איבר יוצא מ-`q` פעם אחת (לתור `small` או `big`) ונכנס חזרה ל-`q` פעם אחת. כל פעולת תור (`insert`, `remove`, `head`, `isEmpty`) היא , ולכן בסך הכול כ- פעולות: .
2. סעיף ב' (`moveToFront`): הפעולה `size` עוברת על התור פעמיים (הוצאה לתור עזר והחזרה) - פעולות. אחר כך סיבובים, כל אחד . בסך הכול לכל היותר פעולות: .
תשובה: סעיף א' - , סעיף ב' - .
שאלה 2 · סידור זוגיים ואי-זוגיים בשרשרת דו-כיוונית
בעזרת המחלקה `BinNode` אפשר לממש שרשרת חוליות דו-כיוונית.


כתבו פעולה המקבלת הפנייה לחוליה הראשונה (הכי שמאלית) של שרשרת חוליות הדו-כיוונית ומסדרת אותה כך שכל הערכים הזוגיים יהיו בתחילת השרשרת וכל הערכים האי-זוגיים יהיו בסופה.
סדר האיברים לא חשוב.
אם לפני הפעולה השרשרת הייתה: 1, 11, 4, 6, 3
אז אחרי הפעולה היא __יכולה להיות__: 6, 4, 11, 1, 3
כותרת הפעולה:
public static void order(BinNode<Integer> chain)public static void Order(BinNode<int> chain)מהי סיבוכיות הפעולה `order` שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
שני מצביעים: `posL` מתחילת השרשרת ו-`posR` מסופה. `posL` מתקדם ימינה על זוגיים, `posR` זז שמאלה על אי-זוגיים, וכשהם נעצרים (אי-זוגי משמאל, זוגי מימין) מחליפים את הערכים; עוצרים כשהמצביעים נפגשים.
הרעיון: אסור להשתמש במבנה נתונים נוסף, ולכן לא מזיזים חוליות אלא מחליפים ערכים בתוך השרשרת. בשרשרת דו-כיוונית אפשר ללכת גם שמאלה (`getLeft`), ולכן משתמשים בשני מצביעים שמתקרבים זה לזה (כמו בחלוקה של מיון מהיר):
1. `posL` מצביע על החוליה הראשונה. `posR` מתקדם עד החוליה האחרונה (כל עוד יש לה חוליה מימין).
2. כל עוד `posL != posR`:
•אם הערך ב-`posL` זוגי - הוא כבר במקום הנכון, ו-`posL` מתקדם ימינה.
•אחרת (ב-`posL` אי-זוגי), אם הערך ב-`posR` אי-זוגי - הוא במקום הנכון, ו-`posR` זז שמאלה.
•אחרת: ב-`posL` אי-זוגי וב-`posR` זוגי - מחליפים את שני הערכים. בסיבוב הבא `posL` יתקדם (כי עכשיו יש בו זוגי).
3. נכונות: בכל שלב, כל החוליות משמאל ל-`posL` מכילות ערכים זוגיים וכל החוליות מימין ל-`posR` מכילות ערכים אי-זוגיים. בכל סיבוב אחד המצביעים זז לכיוון השני או שמתבצעת החלפה שאחריה `posL` זז, ולכן המצביעים נפגשים והלולאה מסתיימת - ואז כל הזוגיים לפני כל האי-זוגיים.
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);
}
}
}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`):
התוצאה `6, 4, 11, 1, 3` - בדיוק כמו בדוגמה.
תשובה: הפעולה שלמעלה (שני מצביעים מהקצוות והחלפת ערכים).
סעיף ב
, כאשר מספר החוליות בשרשרת.
נסמן ב- את מספר החוליות בשרשרת.
1. ההגעה לחוליה האחרונה עם `posR`: מעבר אחד על השרשרת, צעדים.
2. בלולאה הראשית, בכל סיבוב אחד המצביעים מתקרב לשני בחוליה אחת, או שמתבצעת החלפה () שאחריה `posL` מתקדם. המרחק בין המצביעים הוא לכל היותר , ולכן יש לכל היותר כ- סיבובים.
3. בסך הכול כל חוליה נסרקת מספר קבוע של פעמים: .
תשובה: .
שאלה 3 · ירושה, הרשאות גישה והמרות טיפוס
נתונות שתי המחלקות `Flower` ו- `Rose`:
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;
}
}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`.
לפניכם קטע קוד מהתוכנית הראשית:
Flower first = new Rose (20, "RED");
Flower second = new Flower (93);Flower first = new Rose (20, "RED");
Flower second = new Flower (93);בעבור כל אחת מההוראות שלפניך קבעו אם היא תקינה או אינה תקינה.
אם היא אינה תקינה, נמקו את קביעתכם וכתבו אם זו שגיאת ריצה או שגיאת הידור (קומפילציה).
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;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;כתבו פעולה המקבלת מערך עצמים מטיפוס `Object`. על הפעולה להדפיס כמה עצמים הם מטיפוס Rose, כמה עצמים מטיפוס Flower ואינו מטיפוס Rose וכמה עצמים הם לא מטיפוס Flower.
◂ פתרון מלא לשאלה 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, ו-, ולכן `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. בסוף מדפיסים את שלושת המונים. הפעולה עוברת פעם אחת על המערך: .
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);
}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 · ממשקים, המרות טיפוס ויחסי ירושה
בפרויקט מסוים הוגדרו שלשה ממשקים ושתי מחלקות:
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");
( *****)
}
}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`: תכתבו כותרות של הפעולות החסרות בה.
בכל אחד מסעיפים הבאים השורה `( *)` תוחלף בשורת קוד משורות הקוד 1-6. כתבו, עבור כל אחד מהסעיפים, אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (קומפילציה או זמן ריצה).
(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();(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();נתונה הפעולה `main` הבאה:
public static void main(String[] args)
{
C c = new A();
B b1 = (B)(new A());
B b2 = new D();
A a = new D();
}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.
◂ פתרון מלא לשאלה 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`.
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
}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
כותרת הפעולה:
public static void buildFreqList(Node<Integer> chain)public static void BuildFreqList(Node<int> chain)כתבו פעולה המקבלת הפניה לחוליה ראשונה של שרשרת חוליות ומחזירה את המספר __המופיע הכי הרבה__ פעמים בשרשרת. בעבור הרשימה הנתונה בסעיף א' הפעולה תחזיר 20.
כותרת הפעולה:
public static int mostPopularNumber(Node<Integer> chain)public static int MostPopularNumber(Node<int> chain)מהי סיבוכיות הפעולות `buildFreqList` ו-`mostPopularNumber` מהסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 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` אל החוליה שאחרי חוליית המונה - הערך החדש הבא.
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(); // עוברים לערך הבא
}
}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(); // עוברים לערך הבא
}
}תשובה: הפעולה שלמעלה; בדוגמה מתקבלת הרשימה `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`. (בתיקו נשאר המספר שהופיע ראשון.)
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;
}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.
סעיף ג
שתיהן , כאשר מספר האיברים ברשימה המקורית.
נסמן ב- את מספר האיברים ברשימה המקורית.
1. `buildFreqList`: לכל ערך שונה סורקים את כל המשך הרשימה. במקרה הגרוע (כל הערכים שונים) הסריקות הן באורך , ובסך הכול
פעולות - סכום של סדרה חשבונית, כלומר .
2. `mostPopularNumber`: מזמנת את `buildFreqList` () ואחר כך עוברת פעם אחת על רשימת התדירויות, שאורכה לכל היותר (). בסך הכול .
תשובה: `buildFreqList` - ; `mostPopularNumber` - .
שאלה 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` באופן __המתאים ביותר לעקרונות של תכנות מונחה עצמים__.
לכל אחת מהמחלקות `Room`, `FamilyRoom`, `Suite` כתבו כותרת המחלקה ותכונות שלה.
לאחר עזיבת האורחים יש להחליף מצעים בכל אחת מהמיטות שבחדר, לשטוף את הריצפה ולנקות אבק בחדר ובמרפסת, להוציא מיטת תינוק בחדר משפחה (אם יש), לנקות את הג'קוזי בסוויטה (אם יש) ולשאוב שטיחים בסוויטה.
•החלפת מצעים למיטה אחת – חמש דקות,
•שטיפת ריצפה וניקוי אבק – עשר דקות בחדר רגיל וחדר משפחה, עשרים דקות בסוויטה
•ניקוי מרפסת – חמש דקות
•קיפול והוצאת מיטת תינוק – חמש דקות
•ניקוי ג'קוזי – עשרים דקות
•שאיבת שטיחים – חמש עשרה דקות
כתבו פעולה או פעולות לחישוב ולהחזרה של הזמן הדרוש לניקיון חדר.
יש לציין באיזו מחלקה צריך להוסיף את הפעולה או את הפעולות.
למחלקה `Hotel` (מלון) יש תכונה אחת – מערך של חדרי המלון.
כתבו את כותרת המחלקה והגדירו את התכונה.
בסוף כל יום עבודה האחראי על הניקיון מכין תוכנית העבודה ליום המחרת. לשם כך הוא מקבל רשימה של __מספרי חדרים__ שיתפנו למחרת.
כתבו במחלקה `Hotel` פעולה פנימית המקבלת מערך של מספרים שלמים (מערך מספרי חדרים).
הפעולה תחשב ותחזיר את הזמן הכולל של הניקיון. הפעולה גם תדפיס את מספר מיטות התינוק שיתפנו.
כותרת הפעולה:
public int totalTime(int[] numArr)public int TotalTime(int[] numArr)◂ פתרון מלא לשאלה 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`.
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; // האם יש ג'קוזי
}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 דקות לשאיבת שטיחים.
// במחלקה 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;
}// במחלקה 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 מיטות: דקות.
•חדר משפחה עם 4 מיטות, מרפסת ומיטת תינוק: דקות.
•סוויטה עם 2 מיטות וג'קוזי: דקות.
תשובה: הפעולה `cleaningTime()` ב-`Room`, ודריסה שלה ב-`FamilyRoom` וב-`Suite`, כמו בקוד שלמעלה.
סעיף ד
`public class Hotel { private Room[] rooms; }` - מערך מטיפוס `Room` שיכול להכיל גם `FamilyRoom` וגם `Suite`.
המערך מוגדר מטיפוס מחלקת הבסיס `Room`. בזכות הירושה כל תא יכול להפנות לחדר רגיל, לחדר משפחה או לסוויטה.
public class Hotel
{
private Room[] rooms; // מערך חדרי המלון
}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` שמותר להניח שקיימות.
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;
}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` והפעולה תחזיר דקות.
סיבוכיות: לכל אחד מ- מספרי החדרים סורקים את חדרי המלון: .
תשובה: הפעולה שלמעלה.
שאלה 7 · פעולות רקורסיביות על עץ בינרי ועץ חיפוש
לפניכם פעולה רקורסיבית המקבלת הפנייה לשורש של עץ בינרי:
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);
}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`.
מהי מטרת הפעולה `special`?
נתונות שתי פעולות המקבלות הפנייה לשורש של עץ חיפוש בינרי (Binary Search Tree):
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();
}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`?
האם קיים עץ חיפוש בינרי `bt` הכולל לפחות שלושה צמתים שעבורו מתקיים:
`what(bt) = where(bt)`?
אם כן – ציירו את העץ ולא – הסבירו מדוע עץ כזה לא קיים.
◂ פתרון מלא לשאלה 7
סעיף א
לדוגמה: שורש 12; בנים 8 (שמאלי) ו-15 (ימני); ל-8 בן ימני 17; ל-15 בן ימני 9; ל-9 בן שמאלי 10. כל ערך גדול או שווה לרמה שלו, ולכן מוחזר `true`.
מה הפעולה בודקת: הפרמטר `r` הוא הרמה של הצומת: השורש נבדק עם `r = 0`, ובכל ירידה לבן `r` גדל ב-1. הפעולה מחזירה `false` אם בצומת כלשהו הערך קטן מהרמה שלו, ו-`true` אם כל הצמתים עברו את הבדיקה (עץ ריק מחזיר `true`).
לכן צריך עץ עם לפחות 6 צמתים שבו כל ערך גדול או שווה לרמה שבה הוא נמצא.
דוגמה (העץ באיור):
לאף צומת הבדיקה לא מתקיימת, וכל הקריאות על בנים ריקים (`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` רק אם בכל הצמתים מתקיים: ערך הצומת הרמה שלו.
תשובה: הפעולה בודקת אם ערכו של כל צומת בעץ גדול או שווה לרמה (העומק) שבה הוא נמצא; אם כן מחזירה `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 · מעקב אחר ירושה, דריסה ומונים סטטיים
נתונות שתי המחלקות הבאות:
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 Busing 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לפניכם קטע קוד מהתוכנית הראשית:
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);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);מה יהיה הפלט של קטע התוכנית? הסבירו את תשובתכם.
נתונה המחלקה `Tester` הבאה:
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 Testerusing 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`) ורשמו מה יהיה פלט התוכנית. יש להציג את התכונות של כל העצמים שנוצרו במהלך ביצוע התוכנית.
◂ פתרון מלא לשאלה 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`:
שימו לב: `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`).
לבסוף מודפסים המונים הסטטיים: `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`:
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);
}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);
}מה יחזיר זימון הפעולה `what(q,5)` עבור התור `q:[5,5,5,3,3,2,8]` (5 בראש התור)?
אחרי זימון הפעולה `what(q, x)` עבור התור `q` לא ריק, התור `q` נשאר ללא שינוי.
האם הטענה "ערך `x` לא מופיע בתור" נכונה? הסבירו את תשובתכם.
תנו דוגמה של תור `q` שעבורו זימון הפעולה `what(q, 7)` תחזיר 4. איך ייראה התור אחרי זימון הפעולה?
מה מבצעת הפעולה ?
נתונה הפעולה `secret` המקבלת תור של מספרים `q`:
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;
}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`.
מהו הערך המוחזר מהפעולה `secret`?
איך ייראה התור בסיום הפעולה `secret`?
__אחרי__ זימון הפעולה `secret(q)` התור `q` נראה כך: `q:[6,16,2,3]` (6 בראש התור)
איך נראה התור `q` __לפני__ זימון הפעולה?
◂ פתרון מלא לשאלה 9
סעיף א
הפעולה מחזירה 3, והתור נשאר `[3,3,2,8]`.
הפעולה בודקת אם התור ריק או אם הראש שונה מ-`x`; אם כן מחזירה 0. אחרת מוציאה את הראש וממשיכה ברקורסיה (עם `x` שווה לאיבר שהוצא).
הערכים חוזרים מהקריאה הרביעית כלפי מעלה: .
תשובה: `what(q,5)` מחזירה 3, ובסיום התור הוא `[3,3,2,8]`.
לא נכונה: אפשר להסיק רק ש-`x` אינו בראש התור; הוא יכול להופיע בהמשך התור.
1. התור לא ריק ולא השתנה, כלומר כבר בקריאה הראשונה תנאי העצירה התקיים בגלל `x != q.head()` - הראש שונה מ-`x`, ושום איבר לא הוצא.
2. הפעולה בודקת רק את ראש התור, ולא את שאר האיברים. לכן `x` יכול להופיע במקום אחר בתור.
3. דוגמה נגדית: `q:[3,5]` (3 בראש התור) ו-`x = 5`. הראש 3 שונה מ-5, הפעולה מחזירה 0 והתור לא משתנה - אבל 5 מופיע בתור.
תשובה: הטענה אינה נכונה. אפשר לקבוע רק ש-`x` אינו נמצא בראש התור.
לדוגמה `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. בסך הכול .
הפעולה מוציאה את ארבעת ה-7, ולכן אחרי הזימון התור הוא `q:[1,8]`.
תשובה: למשל `q:[7,7,7,7,1,8]`; אחרי הזימון `q:[1,8]` (1 בראש התור).
הפעולה סופרת כמה פעמים `x` מופיע ברצף בראש התור, מוציאה את המופעים האלה מהתור ומחזירה את מספרם.
1. כל עוד בראש התור נמצא `x`, הפעולה מוציאה אותו ומוסיפה 1 לתוצאה.
2. כשהתור מתרוקן או שבראשו ערך אחר, היא מפסיקה ומחזירה 0.
3. לכן התוצאה היא אורך הרצף של `x` בתחילת התור, והרצף הזה נמחק מהתור. מופעים של `x` שאינם ברצף ההתחלתי נשארים.
תשובה: הפעולה מחזירה את מספר המופעים הרצופים של `x` בראש התור ומוציאה אותם מהתור.
סעיף ב
5
מה עושה כל קריאה: `x` הוא הראש, `what(q, x)` מוציאה את הרצף של `x` בראש התור ומחזירה את אורכו, ו-`z` הוא `x` כפול האורך. אחר כך קריאה רקורסיבית על שאר התור, ורק אחרי שהיא חוזרת מכניסים את `z` לסוף התור. הפעולה מחזירה (התוצאה של הקריאה הבאה), כלומר את מספר הרצפים.
החזרה מהרקורסיה (מהקריאה העמוקה כלפי מעלה):
תשובה: הפעולה מחזירה 5 (מספר הרצפים בתור).
`q:[6,5,12,2,10]` (6 בראש התור).
לפי טבלת החזרה מהרקורסיה בסעיף 1: ההכנסות לתור מתבצעות בסדר הפוך לסדר הרצפים (מהרצף האחרון לראשון), כי כל קריאה מכניסה את `z` שלה רק אחרי שהקריאה הבאה הסתיימה.
•הרצפים בתור המקורי: 5 פעמיים (), 1 פעמיים (), 4 שלוש פעמים (), 5 פעם אחת (), 6 פעם אחת ().
•סדר ההכנסה: 6, 5, 12, 2, 10.
תשובה: `q:[6,5,12,2,10]` (6 בראש התור).
לדוגמה `q:[3,1,1,4,4,4,4,2,2,2]` (3 בראש התור).
חושבים הפוך: מסעיפים 1-2 ראינו שכל רצף של ערך באורך הופך לאיבר אחד , והאיברים נכנסים לתור בסדר הפוך לסדר הרצפים.
1. התור בסיום הוא `[6,16,2,3]`, ולכן ברשימה המקורית היו 4 רצפים, ומכפלות הרצפים לפי הסדר המקורי הן: 3, 2, 16, 6.
2. בוחרים לכל מכפלה ערך ואורך, כך ששני רצפים סמוכים יהיו בעלי ערכים שונים (אחרת הם היו מתאחדים לרצף אחד):
•: האיבר 3 פעם אחת.
•: האיבר 1 פעמיים.
•: האיבר 4 ארבע פעמים.
•: האיבר 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]` (מכפלות ) מתאים.
תשובה: למשל `q:[3,1,1,4,4,4,4,2,2,2]` (3 בראש התור).
שאלה 10 · משחק קלפים: השוואת קלפים ומחלקת חפיסה
המחלקה `Card` מייצגת קלף למשחק ילדים Eka.
במשחק משתתפים קלפים בארבעה צבעים: אדום (R), ירוק (G), כחול (B) וצהוב (Y). על כל קלף רשום מספר בין 1 ל-9. סה"כ משתמשים במשחק 36 קלפים שונים.
public class Card
{
private char color;
private int digit;
public Card(char c, int d)
{
this.color = c;
this.digit = d;
}
}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.
כותרת הפעולה:
public int compareTo(Card other)public int CompareTo(Card other)למשחק Eka כללים הבאים:
שני שחקנים לוקחים כל אחד קלף מראש החפיסה משותפת. שחקן שהקלף שלו "חזק יותר" מוסיף את זוג הקלפים לחפיסה שלו. אם אחד מהשחקנים צבר את כל הקלפים מצבע כלשהו, הוא ניצח במשחק.
אם כל הקלפים חולקו ואין מנצח – מכריזים על תיקו.
המחלקה `Deck` מייצגת חפיסת קלפים. במחלקה הוגדרו פעולות הבאות:
כתבו פעולה חיצונית המקבלת חפיסת קלפים מלאה (הכוללת את כל 36 הקלפים) ומדמה את תהליך המשחק. הפעולה תדפיס הודעה על תוצאת המשחק – אחת מההודעות הבאות: "הראשון מנצח", "השני מנצח" או "תיקו".
כותרת הפעולה:
public static void game(Deck d)public static void Game(Deck d)כתבו את המחלקה `Deck`: הגדירו תכונה או תכונות של המחלקה וממשו את כל פעולות שהוגדרו בה.
הערה: שימו לב שבמחלקה `Card` אין פעולות get ואי אפשר להוסיף אותן!
◂ פתרון מלא לשאלה 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` היא ברמת המחלקה).
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;
}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 הסבבים בלי מנצח - כל הקלפים חולקו, ומדפיסים "תיקו".
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("תיקו");
}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` - הקלף העליון בחפיסה (האחרון שנוסף). כך ההוצאה היא .
5. `exist(c)`: אין פעולות `get` ב-`Card`, ולכן לא ניתן להשוות צבע ומספר ישירות. במקום זה משתמשים ב-`compareTo` מסעיף א': היא מחזירה 0 בדיוק כשלשני הקלפים אותו מספר ואותו צבע.
6. `isFull(color)`: בצבע אחד יש 9 קלפים (המספרים 1 עד 9). יוצרים לכל מספר `d` קלף `new Card(color, d)` ובודקים בעזרת `exist` אם הוא בחפיסה. אם אחד חסר - `false`; אם כולם נמצאו - `true`.
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;
}
}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;
}
}תשובה: המחלקה שלמעלה.