מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2024 מועד א'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2024 מועד א', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב-Java (עמוד 2)
מבחן ב-C# (עמוד 12)
בכל מבחן 12 שאלות.
שאלות 5-1: מתוכן יש לענות על 3 שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 10-6: מתוכן יש לענות על 2 שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 12-11: מתוכן יש לענות על שאלה 1 בלבד. ערך שאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית מאוזנת: חיוביים, שליליים ואפסים
מחסנית של מספרים שלמים נקראת "מאוזנת" אם יש לה אותה כמות מספרים גם חיוביים, גם שליליים וגם אפסים.
כתבו פעולה המקבלת מחסנית של מספרים שלמים ובודקת אם היא "מאוזנת". יש לשמור על תוכן של המחסנית אחרי ביצוע הפעולה.
כותרת הפעולה:
public static boolean isBalanced(Stack<Integer> st)public static bool IsBalanced(Stack<int> st)מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
הפעולה isBalanced שלהלן: סופרת חיוביים, שליליים ואפסים תוך העברה למחסנית עזר, משחזרת את המחסנית ומחזירה true אם שלושת המונים שווים.
הרעיון: כדי לדעת אם המחסנית מאוזנת צריך לספור כמה איברים חיוביים, כמה שליליים וכמה אפסים יש בה, ולבדוק ששלושת המספרים שווים. כדי לעבור על האיברים חייבים לשלוף אותם, ולכן נעביר אותם למחסנית עזר ובסוף נחזיר אותם - כך תוכן המחסנית נשמר כפי שנדרש.
1. מאפסים שלושה מונים: `pos` (חיוביים), `neg` (שליליים), `zero` (אפסים).
2. כל עוד `st` אינה ריקה: שולפים איבר `x`, מגדילים את המונה המתאים לסימן שלו, ודוחפים את `x` למחסנית העזר `temp`.
3. מחזירים את כל האיברים מ-`temp` ל-`st`. היפוך כפול של הסדר מחזיר את המחסנית בדיוק למצבה ההתחלתי.
4. מחזירים `true` אם ורק אם `pos == neg` וגם `neg == zero`.
public static boolean isBalanced(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
int pos = 0, neg = 0, zero = 0;
while (!st.isEmpty())
{
int x = st.pop();
if (x > 0)
pos++;
else if (x < 0)
neg++;
else
zero++;
temp.push(x);
}
while (!temp.isEmpty()) // החזרת האיברים למחסנית המקורית
st.push(temp.pop());
return pos == neg && neg == zero;
}public static bool IsBalanced(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
int pos = 0, neg = 0, zero = 0;
while (!st.IsEmpty())
{
int x = st.Pop();
if (x > 0)
pos++;
else if (x < 0)
neg++;
else
zero++;
temp.Push(x);
}
while (!temp.IsEmpty()) // החזרת האיברים למחסנית המקורית
st.Push(temp.Pop());
return pos == neg && neg == zero;
}דוגמה: עבור מחסנית שבה (מלמעלה למטה) 1, -2, 0, 3, -5, 0 יש 2 חיוביים, 2 שליליים ו-2 אפסים, והפעולה מחזירה true; המחסנית נשארת כפי שהייתה. עבור 1, 2, 0, -1 יש 2 חיוביים ורק שלילי אחד ואפס אחד - מוחזר false. מחסנית ריקה (0, 0, 0) נחשבת מאוזנת.
תשובה: הפעולה isBalanced שלמעלה.
סעיף ב
, כאשר מספר האיברים במחסנית.
נסמן ב- את מספר האיברים במחסנית.
1. כל פעולות המחסנית (`push`, `pop`, `isEmpty`) מתבצעות ב-.
2. הלולאה הראשונה מבצעת סיבובים - בכל סיבוב שליפה, השוואות והגדלת מונה, ודחיפה: עבודה קבועה.
3. הלולאה השנייה מחזירה את האיברים: עוד סיבובים של עבודה קבועה.
4. בסך הכול סיבובים, כלומר הסיבוכיות לינארית.
תשובה: .
שאלה 2 · החלפת האיברים האמצעיים בתור
כתבו פעולה המקבלת תור של מספרים שלמים ו-2 מספרים נוספים x ו-y. אם אורך התור זוגי, הפעולה תחליף את 2 האיברים האמצעיים לערכים x ו-y. אם אורך התור אי-זוגי, הפעולה תיצור מספר אקראי בין x ל-y (כולל) ותחליף את האיבר האמצעי של התור לערך אקראי שנוצר. שאר איברי התור יישארו ללא שינוי.
עבור התור q הבא ופרמטרים x=20, y=30
התור q אחרי זימון הפעולה יהיה
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
הפעולה replaceMiddle שלהלן: סופרת את האיברים בעזרת תור עזר, ובהחזרתם לתור מחליפה את האיברים במקומות n/2-1 ו-n/2 ב-x ו-y (n זוגי) או את האיבר במקום n/2 במספר אקראי בין x ל-y (n אי-זוגי).
הרעיון: בתור אפשר לגשת רק לראשו, ולכן כדי לדעת איפה האמצע צריך קודם לדעת את אורך התור . נעביר את כל האיברים לתור עזר ונספור אותם. אחר כך נחזיר אותם אחד אחד לתור המקורי, וכשנגיע למקום האמצעי נכניס במקום האיבר המקורי את הערך החדש. מאחר שהעברה מתור לתור שומרת על הסדר, שאר האיברים חוזרים בדיוק למקומם.
נמספר את המקומות מ-0 (ראש התור) עד , ונסמן `mid = n / 2` (חלוקה שלמה):
•אם זוגי - שני האיברים האמצעיים נמצאים במקומות `mid - 1` ו-`mid`. בדוגמה , `mid = 4`, ואכן במקומות 3 ו-4 נמצאים 2 ו-3, שמוחלפים ב-20 ו-30.
•אם אי-זוגי - האיבר האמצעי נמצא במקום `mid` (למשל ל- במקום 2, השלישי בתור).
1. מעבירים את כל איברי `q` לתור העזר `temp` וסופרים אותם ב-`n`.
2. מגרילים מספר אקראי בין x ל-y כולל. ב-Java: `x + (int)(Math.random() * (y - x + 1))` - הביטוי `Math.random()` נותן מספר ב-, ולכן התוצאה היא שלם בין x ל-y. ב-C#: `rnd.Next(x, y + 1)` (הגבול העליון אינו כלול, ולכן y+1). מניחים .
3. מוציאים מ-`temp` את האיברים לפי הסדר (מונה `i` מ-0). לכל איבר בודקים אם הוא באחד המקומות האמצעיים; אם כן מכניסים ל-`q` את הערך החדש (x, y או המספר האקראי), אחרת את האיבר עצמו.
public static void replaceMiddle(Queue<Integer> q, int x, int y)
{
// שלב 1: ספירת האיברים (העברה לתור עזר והחזרה)
Queue<Integer> temp = new Queue<Integer>();
int n = 0;
while (!q.isEmpty())
{
temp.insert(q.remove());
n++;
}
// שלב 2: החזרת האיברים לתור תוך החלפת האמצע
int mid = n / 2; // מיקום (מ-0) של האיבר האמצעי, או של האמצעי השני כש-n זוגי
int rnd = x + (int)(Math.random() * (y - x + 1)); // מספר אקראי בין x ל-y כולל
for (int i = 0; i < n; i++)
{
int val = temp.remove();
if (n % 2 == 0 && i == mid - 1)
val = x;
else if (n % 2 == 0 && i == mid)
val = y;
else if (n % 2 == 1 && i == mid)
val = rnd;
q.insert(val);
}
}public static void ReplaceMiddle(Queue<int> q, int x, int y)
{
// שלב 1: ספירת האיברים (העברה לתור עזר והחזרה)
Queue<int> temp = new Queue<int>();
int n = 0;
while (!q.IsEmpty())
{
temp.Insert(q.Remove());
n++;
}
// שלב 2: החזרת האיברים לתור תוך החלפת האמצע
int mid = n / 2; // מיקום (מ-0) של האיבר האמצעי, או של האמצעי השני כש-n זוגי
Random rnd = new Random();
int r = rnd.Next(x, y + 1); // מספר אקראי בין x ל-y כולל
for (int i = 0; i < n; i++)
{
int val = temp.Remove();
if (n % 2 == 0 && i == mid - 1)
val = x;
else if (n % 2 == 0 && i == mid)
val = y;
else if (n % 2 == 1 && i == mid)
val = r;
q.Insert(val);
}
}בדיקה על הדוגמה: התור 8, 10, 11, 2, 3, 16, 12, 4 עם x=20, y=30: , `mid = 4`, האיברים במקומות 3 ו-4 (2 ו-3) מוחלפים, ומתקבל 8, 10, 11, 20, 30, 16, 12, 4 - כמו בדוגמה. עבור התור 1, 2, 3, 4, 5 מתקבל למשל 1, 2, 22, 4, 5 (האיבר 3 הוחלף במספר אקראי בין 20 ל-30).
תשובה: הפעולה replaceMiddle שלמעלה.
סעיף ב
, כאשר מספר האיברים בתור.
נסמן ב- את מספר האיברים בתור. פעולות התור (`insert`, `remove`, `isEmpty`) והגרלת המספר מתבצעות ב-.
1. הלולאה הראשונה מעבירה כל איבר פעם אחת לתור העזר: סיבובים.
2. הלולאה השנייה מחזירה כל איבר פעם אחת, עם כמה השוואות קבועות: עוד סיבובים.
3. בסך הכול סיבובים של עבודה קבועה - סיבוכיות לינארית.
תשובה: .
שאלה 3 · שרשרת חוליות: בדיקה ובניית סדרה יורדת
אם 2 האיברים של הסידרה הם 55 ו-34 אז סדרה יורדת תהיה:
55 34 21 13 8 5 3 2 1 1 0 1 1 ....
אם 2 האיברים של הסידרה הם 15 ו-40 אז סדרה יורדת תהיה:
15 40 25 10 15 5 10 5 5 0 ...
תזכורת: לחישוב הפרש יש להשתמש בפונקציה של ערך מוחלט (Math.abs)
כתבו פעולה המקבלת הפנייה לשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם ערכים של השרשרת הם סדרה יורדת. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isDownList (Node<Integer> chain)public static bool IsDownList (Node<int> chain)
כתבו פעולה המקבלת מספר שלם וחיובי num וזוג מספרים שלמים a ו-b. הפעולה תחזיר הפנייה לחוליה הראשונה של שרשרת חוליות שאבריה הם num המספרים הראשונים של סדרה יורדת המתחילה במספרים a ו-b.
כותרת הפעולה:
public static Node<Integer> buildDown (int num, int a, int b)public static Node<int> BuildDown (int num, int a, int b)לדוגמה: עבור הזימון buildDown(9, 55, 34) הפעולה תחזיר הפנייה לחוליה הראשונה של שרשרת החוליות הבאה:
מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
הפעולה isDownList שלהלן: עוברת על כל שלשה של חוליות סמוכות ובודקת שהשלישית שווה לערך המוחלט של הפרש שתי הקודמות; שרשרת עם פחות מ-3 איברים נחשבת סדרה יורדת.
הרעיון: לפי ההגדרה, כל איבר החל מהשלישי נקבע על ידי שני קודמיו. לכן נעבור על השרשרת עם מצביע `p`, ובכל צעד נסתכל על שלוש חוליות סמוכות: `p`, החוליה שאחריה, והחוליה שאחריה. אם הערך השלישי שונה מ- - הסדרה אינה יורדת ומחזירים false מיד. אם הגענו לסוף בלי למצוא הפרה - מחזירים true.
1. אם בשרשרת פחות מ-3 איברים (ריקה, או שהחוליה הראשונה היא גם האחרונה, או שתי חוליות) - אין איבר שצריך לקיים את התנאי, ולכן מחזירים true (כך גם בשרשרת של 2 איברים: הלולאה לא מתבצעת).
2. כל עוד יש שתי חוליות אחרי `p` (`p.getNext().getNext() != null`): לוקחים את שלושת הערכים `a`, `b`, `c` ובודקים `c == Math.abs(a - b)`.
3. מקדמים את `p` בחוליה אחת, כך שכל שלשה סמוכה נבדקת.
public static boolean isDownList(Node<Integer> chain)
{
if (chain == null || chain.getNext() == null)
return true; // פחות מ-3 איברים: אין מה לבדוק
Node<Integer> p = chain;
while (p.getNext().getNext() != null)
{
int a = p.getValue();
int b = p.getNext().getValue();
int c = p.getNext().getNext().getValue();
if (c != Math.abs(a - b))
return false;
p = p.getNext();
}
return true;
}public static bool IsDownList(Node<int> chain)
{
if (chain == null || chain.GetNext() == null)
return true; // פחות מ-3 איברים: אין מה לבדוק
Node<int> p = chain;
while (p.GetNext().GetNext() != null)
{
int a = p.GetValue();
int b = p.GetNext().GetValue();
int c = p.GetNext().GetNext().GetValue();
if (c != Math.Abs(a - b))
return false;
p = p.GetNext();
}
return true;
}דוגמה: עבור 55, 34, 21, 13, 8, 5, 3, 2, 1 כל השלשות תקינות (, , ...) - מוחזר true. עבור 1, 2, 3: - מוחזר false.
הערה: בדוגמה השנייה שבשאלה נפלה טעות בסדר האיברים: לפי ההגדרה הסדרה המתחילה ב-15 ו-40 היא 15, 40, 25, 15, 10, 5, 5, 0, 5, 5, ... (למשל , ולא 10).
תשובה: הפעולה isDownList שלמעלה.
סעיף ב
הפעולה buildDown שלהלן: יוצרת חוליות a ו-b, ואחר כך מוסיפה בסוף השרשרת (בעזרת מצביע לחוליה האחרונה) את עד שיש num חוליות.
הרעיון: בונים את השרשרת משמאל לימין. כל איבר חדש תלוי בשני האיברים האחרונים בשרשרת, ולכן נחזיק שני מצביעים: `last` - החוליה האחרונה, ו-`prev` - החוליה שלפניה. בכל צעד מחשבים `Math.abs(prev - last)`, מוסיפים חוליה חדשה אחרי `last`, ומקדמים את שני המצביעים. כך כל הוספה נעשית בזמן קבוע, בלי לעבור כל פעם על כל השרשרת.
1. יוצרים את החוליה הראשונה עם הערך a. אם `num == 1` מחזירים אותה (השרשרת מכילה רק את a).
2. יוצרים חוליה עם b ומחברים אותה אחרי a. עכשיו `prev` = חוליית a, `last` = חוליית b.
3. עבור `i` מ-3 עד `num`: מחשבים את הערך הבא , מחברים חוליה חדשה אחרי `last`, ומקדמים: `prev = last`, `last` = החוליה החדשה.
4. מחזירים הפנייה לחוליה הראשונה.
public static Node<Integer> buildDown(int num, int a, int b)
{
Node<Integer> first = new Node<Integer>(a);
if (num == 1)
return first;
Node<Integer> last = new Node<Integer>(b); // החוליה האחרונה בשרשרת
first.setNext(last);
Node<Integer> prev = first; // החוליה שלפני האחרונה
for (int i = 3; i <= num; i++)
{
int next = Math.abs(prev.getValue() - last.getValue());
last.setNext(new Node<Integer>(next));
prev = last;
last = last.getNext();
}
return first;
}public static Node<int> BuildDown(int num, int a, int b)
{
Node<int> first = new Node<int>(a);
if (num == 1)
return first;
Node<int> last = new Node<int>(b); // החוליה האחרונה בשרשרת
first.SetNext(last);
Node<int> prev = first; // החוליה שלפני האחרונה
for (int i = 3; i <= num; i++)
{
int next = Math.Abs(prev.GetValue() - last.GetValue());
last.SetNext(new Node<int>(next));
prev = last;
last = last.GetNext();
}
return first;
}בדיקה על הדוגמה: buildDown(9, 55, 34): אחרי 55, 34 מתווספים , , 8, 5, 3, 2, 1 - בסך הכול 9 חוליות: 55, 34, 21, 13, 8, 5, 3, 2, 1, כמו באיור.
תשובה: הפעולה buildDown שלמעלה.
סעיף ג
isDownList: ( אורך השרשרת); buildDown: .
פעולות החוליה (`getValue`, `getNext`, `setNext`, יצירת חוליה) ו-`Math.abs` מתבצעות ב-.
1. isDownList: נסמן ב- את מספר החוליות. הלולאה מתקדמת חוליה אחת בכל סיבוב ומתבצעת פעמים לכל היותר, ובכל סיבוב מספר קבוע של פעולות. לכן הסיבוכיות .
2. buildDown: הלולאה מתבצעת פעמים, ובכל סיבוב חישוב אחד, יצירת חוליה אחת וקידום שני מצביעים - עבודה קבועה, כי בזכות המצביע `last` אין צורך לחפש את סוף השרשרת. לכן הסיבוכיות . (אם היינו מוסיפים כל איבר בסוף השרשרת על ידי מעבר מההתחלה, כל הוספה הייתה עולה והסיבוכיות הייתה .)
תשובה: סעיף א' - ; סעיף ב' - .
שאלה 4 · ירושה: המרות טיפוסים ומהירות כלי רכב
נתון עץ הירושה הבא המתאר סוגי כלי תחבורה שונים:

לפניכם קטע קוד מתוך הפעולה הראשית:
Vehicle v1 = new Vehicle();
Vehicle v2 = new Car();
Vehicle v3 = new Truck();
Car c = new Truck ();לפניכם 8 קטעי קוד. עבור כל אחד מהסעיפים יש לציין, אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (שגיאת קומפילציה / הידור או שגיאת זמן ריצה).
1. Car c1 = new Vehicle ();
2. Car c2 = v1;
3. Car c3 = (Car) v2;
4. Car c4 = (Car) v3;
5. Car c5 = (Car) v1;
6.
Motorcycle m = new Motorcycle();
Vehicle v6 = m;
Car c6 = (Car) s6;
7. Vehicle v7 = (Car)(new Truck ());
8. Car c8 = (Vehicle)(new Truck ());רוצים לכתוב פעולה אשר מקבלת מערך של כלי תחבורה (מערך הפניות לעצמים מטיפוס Vehicle) ומחזירה את המהירות הממוצעת של כל האופנועים (Motorcycle) ומכוניות המירוץ (RacingCar). באיזו מחלקה או מחלקות יש להוסיף את הפעולה double speed() המחזירה את המהירות?
כתבו פעולה המקבלת מערך כלי תחבורה ומחזירה את האופנוע שמהירותו היא הגבוהה ביותר. אם במערך אין אף אופנוע, הפעולה תחזיר null.
כותרת הפעולה:
public static Motorcycle maxSpeed(Vehicle[] arr)public static Motorcycle MaxSpeed(Vehicle[] arr)◂ פתרון מלא לשאלה 4
סעיף א
1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקין; 4 - תקין; 5 - שגיאת זמן ריצה; 6 - שגיאת זמן ריצה (s6 הוא v6); 7 - תקין; 8 - שגיאת הידור.
•בזמן הידור המהדר מסתכל רק על הטיפוס המוצהר של המשתנה. מותר להציב עצם של מחלקה יורשת במשתנה של מחלקת בסיס (Car הוא Vehicle), אבל לא להפך בלי המרה מפורשת. המרה מפורשת `(Car)` מותרת רק בין טיפוסים שיש ביניהם קשר ירושה.
•בזמן ריצה המרה מפורשת נבדקת מול הטיפוס האמיתי של העצם: אם העצם אינו Car (או מחלקה שיורשת מ-Car), נזרקת חריגה (`ClassCastException` ב-Java, `InvalidCastException` ב-C#).
לפי קטע הקוד: `v1` מפנה לעצם Vehicle, `v2` לעצם Car, `v3` לעצם Truck (Truck יורש מ-Car).
(אם קוראים את קטע 6 כפי שהודפס, עם `s6`, זו שגיאת הידור כי המשתנה `s6` אינו מוגדר.)
תשובה: תקינים - 3, 4, 7. שגיאת הידור - 1, 2, 8. שגיאת זמן ריצה - 5, 6.
סעיף ב
במחלקה Vehicle (הגדרה כללית), ודריסה שלה במחלקות Motorcycle ו-RacingCar (ובמידת הצורך גם ב-Car).
1. הפעולה החיצונית עוברת על מערך מטיפוס `Vehicle[]`, ולכן היא מזמנת את `arr[i].speed()` דרך הפניה מטיפוס Vehicle. כדי שהזימון יעבור הידור, הפעולה חייבת להיות מוגדרת במחלקה Vehicle (בראש עץ הירושה).
2. המהירות מחושבת אחרת לכל סוג כלי תחבורה, ולכן דורסים את `speed()` במחלקות Motorcycle ו-RacingCar (ב-C# - `virtual` ב-Vehicle ו-`override` במחלקות היורשות). בזמן ריצה, בזכות פולימורפיזם, תופעל הגרסה של הטיפוס האמיתי של העצם.
3. RacingCar יורשת מ-Car; אם גם למכונית רגילה יש חישוב מהירות משלה, מוסיפים דריסה גם ב-Car, ו-RacingCar דורסת אותה שוב.
4. אפשרות אחרת - להגדיר את `speed()` רק ב-Motorcycle וב-RacingCar ולהמיר כל איבר לטיפוס המתאים אחרי בדיקת `instanceof`; הפתרון עם Vehicle עדיף כי הקוד פשוט יותר וקל להרחבה.
תשובה: להגדיר את `speed()` במחלקה Vehicle ולדרוס אותה ב-Motorcycle וב-RacingCar (ואם צריך גם ב-Car).
סעיף ג
הפעולה maxSpeed שלהלן: עוברת על המערך, בודקת לכל איבר אם הוא Motorcycle, ושומרת את האופנוע המהיר ביותר; אם אין אופנוע מוחזר null.
הרעיון: חיפוש מקסימום רגיל, אבל רק על האיברים שהם אופנועים. בודקים את הטיפוס האמיתי של כל איבר בעזרת `instanceof` (ב-C#: `is`), ממירים אותו ל-Motorcycle ומשווים את מהירותו למהירות של האופנוע הטוב ביותר שנמצא עד כה. המשתנה `best` מתחיל ב-null; אם לא נמצא אף אופנוע הוא נשאר null, וזה בדיוק הערך שצריך להחזיר.
1. `best = null`.
2. לכל `arr[i]`: אם הוא Motorcycle - ממירים ל-`m`. אם `best` עדיין null, או ש-`m.speed()` גדולה מ-`best.speed()` - מעדכנים `best = m`.
3. מחזירים את `best`.
הפעולה משתמשת ב-`speed()` מסעיף ב'.
public static Motorcycle maxSpeed(Vehicle[] arr)
{
Motorcycle best = null;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof Motorcycle)
{
Motorcycle m = (Motorcycle) arr[i];
if (best == null || m.speed() > best.speed())
best = m;
}
}
return best;
}public static Motorcycle MaxSpeed(Vehicle[] arr)
{
Motorcycle best = null;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is Motorcycle)
{
Motorcycle m = (Motorcycle) arr[i];
if (best == null || m.Speed() > best.Speed())
best = m;
}
}
return best;
}תשובה: הפעולה maxSpeed שלמעלה.
שאלה 5 · מעקב אחר פעולות על שרשרת חוליות
נתונה הפעולה why הבאה:
public static Node<Integer> why(Node<Integer> chain, boolean flag)
{
int count = 0;
Node<Integer> p = chain;
while(p != null)
{
int x = p.getValue();
boolean f = (x % 2 ==0);
if( f == flag)
count ++;
p = p.getNext();
}
return new Node<Integer>(count);
}public static Node<int> Why(Node<int> chain, bool flag)
{
int count = 0;
Node<int> p = chain;
while(p != null)
{
int x = p.GetValue();
bool f = (x % 2 ==0);
if( f == flag)
count ++;
p = p.GetNext();
}
return new Node<int>(count);
}נתונה שרשרת חוליות הבאה:

מה תחזיר הפעולה why(chain, false)?
נתונה הפעולה what הבאה:
public static void what(Node<Integer> chain)
{
Node<Integer> p = chain;
Node<Integer> temp;
while (p != null)
{
if(p.getValue()%2 ==0)
temp = why(p.getNext(), false);
else
temp = why(p.getNext(), true);
temp.setNext(p.getNext());
p.setNext(temp);
p = temp.getNext();
}
}public static void What(Node<int> chain)
{
Node<int> p = chain;
Node<int> temp;
while (p != null)
{
if(p.GetValue()%2 ==0)
temp = Why(p.GetNext(), false);
else
temp = Why(p.GetNext(), true);
temp.SetNext(p.GetNext());
p.SetNext(temp);
p = temp.GetNext();
}
}עקבו אחרי ביצוע זימון הפעולה what(chain) ורשמו איך תראה השרשרת אחרי זימון הפעולה.
מה מבצעות הפעולות what(chain) ו- why(chain,flag) באופן כללי?
◂ פתרון מלא לשאלה 5
סעיף א
הפנייה לחוליה חדשה שערכה 3 (מספר האיברים האי-זוגיים בשרשרת).
מה הפעולה בודקת: לכל חוליה `f` הוא true אם הערך זוגי. `count` גדל כאשר `f == flag`. בזימון עם `flag = false` נספרות החוליות שבהן `f` הוא false, כלומר הערכים האי-זוגיים. בסוף מוחזרת חוליה חדשה שערכה `count`.
טבלת מעקב (השרשרת: 10, 7, 14, 5, 7, 2, 4):
אחרי החוליה האחרונה `p` הופך ל-null והלולאה מסתיימת. מוחזרת `new Node(3)`.
תשובה: הפעולה מחזירה הפנייה לחוליה חדשה (בודדת) שערכה 3.
סעיף ב
10 → 3 → 7 → 3 → 14 → 2 → 5 → 2 → 7 → 2 → 2 → 0 → 4 → 0
מה קורה בכל סיבוב: עבור החוליה `p`: אם הערך שלה זוגי - `why(p.getNext(), false)` סופרת את האי-זוגיים שאחרי `p`; אם הערך אי-זוגי - `why(..., true)` סופרת את הזוגיים שאחריה. החוליה החדשה `temp` (עם המונה) משורשרת מיד אחרי `p`, ו-`p` מתקדם לחוליה המקורית הבאה (`temp.getNext()`), כך שהחוליות החדשות אינן נבדקות.
טבלת מעקב (השרשרת המקורית: 10, 7, 14, 5, 7, 2, 4):
אחרי הסיבוב השביעי `p = temp.getNext()` הוא null והלולאה מסתיימת.
תשובה: השרשרת אחרי הזימון: 10 → 3 → 7 → 3 → 14 → 2 → 5 → 2 → 7 → 2 → 2 → 0 → 4 → 0.
סעיף ג
why מחזירה חוליה חדשה שערכה מספר החוליות שזוגיותן מתאימה ל-flag (true - זוגיים, false - אי-זוגיים); what מוסיפה אחרי כל חוליה מקורית חוליה עם מספר החוליות שאחריה בעלות זוגיות הפוכה לשלה.
1. why(chain, flag): סופרת כמה ערכים בשרשרת הם זוגיים (כאשר `flag` הוא true) או אי-זוגיים (כאשר `flag` הוא false), ומחזירה הפנייה לחוליה חדשה שערכה המספר הזה. השרשרת עצמה אינה משתנה.
2. what(chain): לכל חוליה מקורית בשרשרת מוסיפה מיד אחריה חוליה חדשה, שערכה מספר החוליות המקוריות שאחריה שהזוגיות שלהן הפוכה לזוגיות שלה (אחרי ערך זוגי - מספר האי-זוגיים שאחריו; אחרי ערך אי-זוגי - מספר הזוגיים שאחריו). אורך השרשרת מוכפל.
תשובה: why סופרת את הערכים בזוגיות שנקבעה ב-flag ומחזירה חוליה עם הספירה; what משבצת אחרי כל איבר את מספר האיברים שאחריו בעלי זוגיות הפוכה.
שאלה 6 · מחסניות: מחיקת מופעים ואיחוד ערכים
כתבו פעולה המקבלת מחסנית של מספרים שלמים st ומספר נוסף num. הפעולה תמחק ממחסנית st את כל המופעים של num.
כותרת הפעולה:
public static void remove(Stack<Integer> st, int num)public static void Remove(Stack<int> st, int num)
כתבו פעולה המקבלת 2 מחסניות של מספרים שלמים st1 ו-st2. הפעולה תחזיר מחסנית חדשה הכוללת כל ערך מ-2 המחסניות. כל ערך במחסנית החדשה צריך להופיע פעם אחת. סדר האיברים במחסנית החדשה לא חשוב.
לדוגמה: עבור 2 מחסניות הבאות st1 ו-st2 הפעולה תחזיר מחסנית st3.
כותרת הפעולה:
public static Stack<Integer> commonValues(Stack<Integer> s1,
Stack<Integer> s2)public static Stack<int> CommonValues(Stack<int> s1,
Stack<int> s2)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
הפעולה remove שלהלן: מעבירה למחסנית עזר רק את האיברים השונים מ-num ומחזירה אותם ל-st.
הרעיון: שולפים את כל איברי `st`. כל איבר ששונה מ-`num` נדחף למחסנית עזר, ואיבר ששווה ל-`num` פשוט לא נשמר (נמחק). בסוף מחזירים את מחסנית העזר ל-`st`; ההיפוך הכפול שומר על הסדר המקורי של האיברים שנשארו.
1. כל עוד `st` אינה ריקה: שולפים `x`; אם `x != num` דוחפים אותו ל-`temp`.
2. מחזירים את כל איברי `temp` ל-`st`.
public static void remove(Stack<Integer> st, int num)
{
Stack<Integer> temp = new Stack<Integer>();
while (!st.isEmpty())
{
int x = st.pop();
if (x != num) // שומרים רק איברים השונים מ-num
temp.push(x);
}
while (!temp.isEmpty()) // החזרה - הסדר המקורי נשמר
st.push(temp.pop());
}public static void Remove(Stack<int> st, int num)
{
Stack<int> temp = new Stack<int>();
while (!st.IsEmpty())
{
int x = st.Pop();
if (x != num) // שומרים רק איברים השונים מ-num
temp.Push(x);
}
while (!temp.IsEmpty()) // החזרה - הסדר המקורי נשמר
st.Push(temp.Pop());
}דוגמה: עבור st = (מלמעלה למטה) 1, 5, 2, 5, 5, 3 ו-num = 5 מתקבל 1, 2, 3.
תשובה: הפעולה remove שלמעלה.
סעיף ב
הפעולה commonValues שלהלן: מעתיקה את שתי המחסניות למחסנית עזר אחת (ומשחזרת אותן), ואז שולפת ממנה ערך, מוחקת את כל מופעיו בעזרת remove ודוחפת אותו פעם אחת למחסנית התוצאה.
הרעיון: המחסנית החדשה היא האיחוד של הערכים בשתי המחסניות, בלי כפילויות. נאסוף את כל הערכים משתי המחסניות למחסנית עזר אחת `all`. אחר כך, כל עוד `all` אינה ריקה, נשלוף ממנה ערך `x`, נמחק מ-`all` את כל שאר המופעים של `x` בעזרת הפעולה `remove` מסעיף א', ונדחוף את `x` פעם אחת ל-`st3`. כך כל ערך מגיע ל-`st3` בדיוק פעם אחת. את המחסניות המקוריות נשחזר במהלך ההעתקה, כדי לא לפגוע בהן.
1. העתקת s1: מעבירים את `s1` למחסנית `temp` (בסדר הפוך), ואז מוציאים מ-`temp` כל איבר, דוחפים אותו חזרה ל-`s1` וגם ל-`all`. `s1` חוזרת למצבה המקורי.
2. העתקת s2: אותו דבר עבור `s2`.
3. בניית התוצאה: כל עוד `all` אינה ריקה: `x = all.pop()`, `remove(all, x)`, `st3.push(x)`.
4. מחזירים את `st3`.
public static Stack<Integer> commonValues(Stack<Integer> s1, Stack<Integer> s2)
{
// שלב 1: העתקת שתי המחסניות למחסנית עזר אחת, תוך שחזור המקוריות
Stack<Integer> all = new Stack<Integer>();
Stack<Integer> temp = new Stack<Integer>();
while (!s1.isEmpty())
temp.push(s1.pop());
while (!temp.isEmpty())
{
int x = temp.pop();
s1.push(x);
all.push(x);
}
while (!s2.isEmpty())
temp.push(s2.pop());
while (!temp.isEmpty())
{
int x = temp.pop();
s2.push(x);
all.push(x);
}
// שלב 2: כל ערך עובר פעם אחת למחסנית התוצאה, וכל מופעיו נמחקים מ-all
Stack<Integer> st3 = new Stack<Integer>();
while (!all.isEmpty())
{
int x = all.pop();
remove(all, x);
st3.push(x);
}
return st3;
}public static Stack<int> CommonValues(Stack<int> s1, Stack<int> s2)
{
// שלב 1: העתקת שתי המחסניות למחסנית עזר אחת, תוך שחזור המקוריות
Stack<int> all = new Stack<int>();
Stack<int> temp = new Stack<int>();
while (!s1.IsEmpty())
temp.Push(s1.Pop());
while (!temp.IsEmpty())
{
int x = temp.Pop();
s1.Push(x);
all.Push(x);
}
while (!s2.IsEmpty())
temp.Push(s2.Pop());
while (!temp.IsEmpty())
{
int x = temp.Pop();
s2.Push(x);
all.Push(x);
}
// שלב 2: כל ערך עובר פעם אחת למחסנית התוצאה, וכל מופעיו נמחקים מ-all
Stack<int> st3 = new Stack<int>();
while (!all.IsEmpty())
{
int x = all.Pop();
Remove(all, x);
st3.Push(x);
}
return st3;
}בדיקה על הדוגמה: st1 = 5, 7, 5, 4, 9 ו-st2 = 4, 9, 3, 1, 7, 9, 4, 3 (מלמעלה למטה). הערכים השונים הם 5, 7, 4, 9, 3, 1 - שישה ערכים, כמו ב-st3 שבדוגמה (הסדר עשוי להיות שונה, וזה מותר). st1 ו-st2 נשארות ללא שינוי.
תשובה: הפעולה commonValues שלמעלה.
סעיף ג
remove: ; commonValues: , כאשר מספר האיברים הכולל בשתי המחסניות.
פעולות המחסנית מתבצעות ב-.
1. remove: נסמן ב- את מספר האיברים ב-`st`. כל איבר נשלף פעם אחת ולכל היותר נדחף ונשלף מ-`temp` ונדחף חזרה - עבודה קבועה לאיבר. הסיבוכיות .
2. commonValues: נסמן - מספר האיברים הכולל. ההעתקה בשלבים 1-2 היא . בשלב 3 הלולאה מתבצעת לכל היותר פעמים (פעם לכל ערך שונה), ובכל סיבוב יש קריאה ל-`remove` על `all`, שבה עד איברים - . במקרה הגרוע (כל הערכים שונים) מתקבל פעולות, כלומר .
תשובה: סעיף א' - ; סעיף ב' - .
שאלה 7 · ממשקים וירושה: מערכת לניהול חנות ספרים
החנות "ספר לכל" מוכרת סוגים שונים של ספרים: ספרים מודפסים, ספרי שמע, ספרים אלקטרוניים. חלק מהמוצרים ניתן לרכוש באריזת מתנה (בעבור תשלום נוסף).
לשם קידום מכירות ספרים, חנות "ספר לכל" פיתחה מערכת לניהול מלאי הספרים הכוללת את המחלקות הבאות GiftEBook, PaperBook, EBook, AudioBook, Book ו-2 ממשקים IGiftable ו-IDownloadable.
לפניכם תרשים UML המתאר קשרים בין המחלקות והממשקים:

כתבו עבור כל מחלקה, את כותרת המחלקה ואת הכותרות של כל הפעולות שחייבות להיות במחלקה.
המחיר של כל ספר תלוי בסוג הספר. לשם כך הוחלט להגדיר 3 קבועים המציינים מקדמי מחיר עבור ספרים אלקטרוניים, ספרי שמע וספרים מודפסים:
final double EBOOK_FACTOR = 0.8;
final double AUDIOBOOK_FACTOR = 1.2;
final double PAPERBOOK_FACTOR = 1.0;const double EBOOK_FACTOR = 0.8;
const double AUDIOBOOK_FACTOR = 1.2;
const double PAPERBOOK_FACTOR = 1.0;באיזו מחלקה או באילו מחלקות יש להוסיף את הקבועים הנ"ל? הסבירו את תשובתכם.
כתבו פעולה או פעולות המחזירה את מחיר הספר (ללא אריזת מתנה), עבור כל סוג ספר, יש לציין באיזו מחלקה צריך להוסיף את הפעולה או את הפעולות.
כתבו פעולה חיצונית המקבלת מערך ספרים המתאר את מלאי החנות וסכום כסף שלקוח רוצה להשקיע. הפעולה תדפיס את פרטי הספרים שמחירם אינו עולה על הסכום שהלקוח רוצה להשקיע.
כתבו פעולה חיצונית המקבלת מערך ספרים המתאר את מלאי החנות. הפעולה תדפיס את מספר הספרים שאפשר לרכוש אותם באריזת מתנה.
◂ פתרון מלא לשאלה 7
סעיף א
AudioBook ו-EBook יורשות מ-Book ומממשות את IDownloadable (download, getSize); PaperBook יורשת מ-Book ומממשת את IGiftable (getAdditionPrice, getGiftType); GiftEBook יורשת מ-EBook ומממשת את IGiftable (getAdditionPrice, getGiftType).
קריאת התרשים: חץ רציף מסמן ירושה (extends), וחץ מקווקו מסמן מימוש ממשק (implements). מחלקה שמממשת ממשק חייבת לממש את כל הפעולות שבו (אחרת היא לא תעבור הידור), ולכן אלה הפעולות שחייבות להופיע במחלקה. בנוסף לכל מחלקה בנאי שמאתחל את התכונות שלה.
ל-GiftEBook אין צורך לממש מחדש את `download()` ו-`getSize()` - היא יורשת אותן מ-EBook, ולכן היא מקיימת את IDownloadable דרך הירושה. בתרשים GiftEBook מסומנת "ספר", אבל לפי מקומה בתרשים היא ספר אלקטרוני שאפשר לקנות כמתנה.
להלן הממשקים והמחלקות עם הכותרות (גופי הפעולות פשוטים ומובאים להשלמה):
public interface IDownloadable
{
void download();
int getSize();
}
public interface IGiftable
{
double getAdditionPrice();
String getGiftType();
}
public class Book
{
protected String name;
protected String author;
protected double price;
public Book(String name, String author, double price)
{
this.name = name;
this.author = author;
this.price = price;
}
}
public class AudioBook extends Book implements IDownloadable
{
private int duration;
public AudioBook(String name, String author, double price, int duration)
{
super(name, author, price);
this.duration = duration;
}
public void download()
{
System.out.println("Downloading " + name);
}
public int getSize()
{
return duration;
}
}
public class EBook extends Book implements IDownloadable
{
protected int fileSize;
public EBook(String name, String author, double price, int fileSize)
{
super(name, author, price);
this.fileSize = fileSize;
}
public void download()
{
System.out.println("Downloading " + name);
}
public int getSize()
{
return fileSize;
}
}
public class PaperBook extends Book implements IGiftable
{
private int year;
private int pages;
private double addition;
public PaperBook(String name, String author, double price,
int year, int pages, double addition)
{
super(name, author, price);
this.year = year;
this.pages = pages;
this.addition = addition;
}
public double getAdditionPrice()
{
return addition;
}
public String getGiftType()
{
return "Gift box";
}
}
public class GiftEBook extends EBook implements IGiftable
{
private double addition;
public GiftEBook(String name, String author, double price,
int fileSize, double addition)
{
super(name, author, price, fileSize);
this.addition = addition;
}
public double getAdditionPrice()
{
return addition;
}
public String getGiftType()
{
return "Gift card";
}
}public interface IDownloadable
{
void Download();
int GetSize();
}
public interface IGiftable
{
double GetAdditionPrice();
string GetGiftType();
}
public class Book
{
protected string name;
protected string author;
protected double price;
public Book(string name, string author, double price)
{
this.name = name;
this.author = author;
this.price = price;
}
}
public class AudioBook : Book, IDownloadable
{
private int duration;
public AudioBook(string name, string author, double price, int duration)
: base(name, author, price)
{
this.duration = duration;
}
public void Download()
{
Console.WriteLine("Downloading " + name);
}
public int GetSize()
{
return duration;
}
}
public class EBook : Book, IDownloadable
{
protected int fileSize;
public EBook(string name, string author, double price, int fileSize)
: base(name, author, price)
{
this.fileSize = fileSize;
}
public void Download()
{
Console.WriteLine("Downloading " + name);
}
public int GetSize()
{
return fileSize;
}
}
public class PaperBook : Book, IGiftable
{
private int year;
private int pages;
private double addition;
public PaperBook(string name, string author, double price,
int year, int pages, double addition)
: base(name, author, price)
{
this.year = year;
this.pages = pages;
this.addition = addition;
}
public double GetAdditionPrice()
{
return addition;
}
public string GetGiftType()
{
return "Gift box";
}
}
public class GiftEBook : EBook, IGiftable
{
private double addition;
public GiftEBook(string name, string author, double price,
int fileSize, double addition)
: base(name, author, price, fileSize)
{
this.addition = addition;
}
public double GetAdditionPrice()
{
return addition;
}
public string GetGiftType()
{
return "Gift card";
}
}תשובה: כמפורט בטבלה ובקוד שלמעלה.
סעיף ב
EBOOK_FACTOR במחלקה EBook, AUDIOBOOK_FACTOR במחלקה AudioBook, PAPERBOOK_FACTOR במחלקה PaperBook (כקבועים סטטיים).
1. כל מקדם שייך לסוג ספר אחד בלבד, ומשמש רק לחישוב המחיר של אותו סוג. לכן נכון לשים כל קבוע במחלקה של הסוג שלו - כך כל מחלקה מכילה רק את המידע שנוגע לה (כימוס).
2. הקבוע זהה לכל העצמים של המחלקה, ולכן מגדירים אותו `static final` ב-Java (ב-C# `const` הוא סטטי ממילא), ואין צורך בעותק בכל עצם.
3. GiftEBook יורשת מ-EBook, ולכן היא משתמשת ב-EBOOK_FACTOR בלי להגדיר אותו שוב.
4. גם פתרון שבו שלושת הקבועים מוגדרים במחלקה Book (המשותפת לכולן) אפשרי, אבל אז כל סוג ספר "רואה" גם מקדמים שאינם שלו.
// במחלקה EBook
public static final double EBOOK_FACTOR = 0.8;
// במחלקה AudioBook
public static final double AUDIOBOOK_FACTOR = 1.2;
// במחלקה PaperBook
public static final double PAPERBOOK_FACTOR = 1.0;// במחלקה EBook
public const double EBOOK_FACTOR = 0.8;
// במחלקה AudioBook
public const double AUDIOBOOK_FACTOR = 1.2;
// במחלקה PaperBook
public const double PAPERBOOK_FACTOR = 1.0;תשובה: EBOOK_FACTOR ב-EBook (ו-GiftEBook יורשת אותו), AUDIOBOOK_FACTOR ב-AudioBook, PAPERBOOK_FACTOR ב-PaperBook.
סעיף ג
getPrice() במחלקה Book (מחזירה price), ודריסה ב-EBook (price·0.8, ו-GiftEBook יורשת), ב-AudioBook (price·1.2) וב-PaperBook (price·1.0).
הרעיון: פולימורפיזם. מגדירים במחלקת הבסיס Book פעולה `getPrice()` שמחזירה את מחיר הבסיס, וכל מחלקה יורשת דורסת אותה ומכפילה את `price` (תכונה `protected` של Book, ולכן נגישה במחלקות היורשות) במקדם שלה. כך אפשר לזמן `getPrice()` על כל הפניה מטיפוס Book, ותתבצע הגרסה של הטיפוס האמיתי של הספר.
1. Book: `getPrice()` מחזירה `price` (ב-C# מוגדרת `virtual`).
2. EBook: מחזירה `price * EBOOK_FACTOR`. GiftEBook יורשת פעולה זו - המחיר בלי אריזת המתנה זהה לספר אלקטרוני רגיל.
3. AudioBook: מחזירה `price * AUDIOBOOK_FACTOR`.
4. PaperBook: מחזירה `price * PAPERBOOK_FACTOR`.
(התוספת של אריזת המתנה, `addition`, אינה נכללת - היא מוחזרת בנפרד ב-`getAdditionPrice()`.)
// במחלקה Book - מחיר בסיס
public double getPrice()
{
return this.price;
}
// במחלקה EBook (המחלקה GiftEBook יורשת פעולה זו)
public double getPrice()
{
return this.price * EBOOK_FACTOR;
}
// במחלקה AudioBook
public double getPrice()
{
return this.price * AUDIOBOOK_FACTOR;
}
// במחלקה PaperBook
public double getPrice()
{
return this.price * PAPERBOOK_FACTOR;
}// במחלקה Book - מחיר בסיס
public virtual double GetPrice()
{
return this.price;
}
// במחלקה EBook (המחלקה GiftEBook יורשת פעולה זו)
public override double GetPrice()
{
return this.price * EBOOK_FACTOR;
}
// במחלקה AudioBook
public override double GetPrice()
{
return this.price * AUDIOBOOK_FACTOR;
}
// במחלקה PaperBook
public override double GetPrice()
{
return this.price * PAPERBOOK_FACTOR;
}דוגמה: לספר אלקטרוני שמחיר הבסיס שלו 100: ; לספר שמע במחיר בסיס 100: .
תשובה: getPrice() ב-Book, ודריסה שלה ב-EBook, ב-AudioBook וב-PaperBook כמו בקוד שלמעלה.
סעיף ד
הפעולה printAffordable שלהלן: מדפיסה כל ספר שעבורו getPrice() <= money.
הרעיון: עוברים על המערך, ולכל ספר מחשבים את מחירו בעזרת `getPrice()` מסעיף ג' (פולימורפיזם - המחיר המתאים לסוג הספר). אם המחיר אינו עולה על הסכום - מדפיסים את פרטי הספר.
נניח שבמחלקה Book מוגדרת הפעולה `toString()` (ב-C#: `ToString()` עם `override`) שמחזירה את פרטי הספר: שם, מחבר ומחיר.
public static void printAffordable(Book[] books, double money)
{
for (int i = 0; i < books.length; i++)
{
if (books[i].getPrice() <= money)
System.out.println(books[i]); // toString של הספר
}
}public static void PrintAffordable(Book[] books, double money)
{
for (int i = 0; i < books.Length; i++)
{
if (books[i].GetPrice() <= money)
Console.WriteLine(books[i]); // ToString של הספר
}
}תשובה: הפעולה printAffordable שלמעלה.
סעיף ה
הפעולה printGiftCount שלהלן: סופרת את הספרים שהם instanceof IGiftable ומדפיסה את המספר.
הרעיון: ספר שאפשר לקנות באריזת מתנה הוא ספר שמחלקתו מממשת את הממשק IGiftable (PaperBook ו-GiftEBook). לכן סופרים את איברי המערך שעבורם `books[i] instanceof IGiftable` (ב-C#: `books[i] is IGiftable`) ומדפיסים את המונה. הבדיקה מול הממשק, ולא מול שמות המחלקות, נשארת נכונה גם אם בעתיד יתווספו סוגי ספרים נוספים שמממשים את IGiftable.
public static void printGiftCount(Book[] books)
{
int count = 0;
for (int i = 0; i < books.length; i++)
{
if (books[i] instanceof IGiftable)
count++;
}
System.out.println(count);
}public static void PrintGiftCount(Book[] books)
{
int count = 0;
for (int i = 0; i < books.Length; i++)
{
if (books[i] is IGiftable)
count++;
}
Console.WriteLine(count);
}תשובה: הפעולה printGiftCount שלמעלה.
שאלה 8 · עץ בינרי "שרשרת עולה"
הגדרה: עץ "שרשרת עולה" הוא עץ בינארי של מספרים שלמים העונה על הכלל הבא:
•לכל צומת פרט לעלים יש בדיוק בן אחד.
•ערכים של כל הצמתים הם מספרים חיוביים זוגיים.
•הערך של צומת הבן גדול מהערך של צומת האב.
ציירו עץ "שרשרת עולה" הכולל לפחות 6 צמתים.
כתבו פעולה המקבלת הפנייה לשורש של עץ בינרי של מספרים שלמים. הפעולה תבדוק אם העץ הוא "שרשרת עולה". אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
◂ פתרון מלא לשאלה 8
סעיף א
למשל: 2 (שורש) ← בן ימני 4 ← בן שמאלי 6 ← בן ימני 8 ← בן ימני 10 ← בן ימני 12 (עלה).
בונים "שרשרת" של צמתים: לכל צומת בן אחד בלבד (שמאלי או ימני - לא משנה), כל הערכים חיוביים וזוגיים, וכל בן גדול מאביו.
1. השורש: 2.
2. בן ימני של 2: הצומת 4.
3. בן שמאלי של 4: הצומת 6.
4. בן ימני של 6: הצומת 8.
5. בן ימני של 8: הצומת 10.
6. בן ימני של 10: הצומת 12 - עלה.
לכל צומת פנימי בן אחד בדיוק, כל הערכים זוגיים וחיוביים, והערכים עולים לאורך השרשרת: . יש 6 צמתים.
תשובה: העץ 2 → 4 → 6 → 8 → 10 → 12, שבו לכל צומת בן אחד (כמו בציור).

סעיף ב
הפעולה הרקורסיבית isUpChain שלהלן: בודקת שהצומת חיובי וזוגי, שאין לו שני בנים, שהבן היחיד גדול ממנו, וממשיכה ברקורסיה לבן; עלה תקין מחזיר true.
הרעיון: עץ "שרשרת עולה" הוא למעשה מסלול אחד מהשורש לעלה. נבדוק ברקורסיה: הצומת הנוכחי תקין, ואם יש לו בן - הבן גדול ממנו, ותת-העץ שמתחיל בבן הוא גם "שרשרת עולה".
1. אם `t` הוא null (עץ ריק) - מחזירים false (מניחים שעץ ללא צמתים אינו "שרשרת עולה"; הקריאה הרקורסיבית תמיד נעשית על בן קיים).
2. אם הערך `x` של `t` אינו חיובי או אינו זוגי - מחזירים false.
3. אם `t` הוא עלה (אין לו בנים) - הוא סוף תקין של השרשרת: מחזירים true.
4. אם יש ל-`t` שני בנים - הכלל "בדיוק בן אחד" מופר: מחזירים false.
5. אחרת יש בן יחיד `child` (שמאלי או ימני). אם ערכו קטן או שווה ל-`x` - מחזירים false.
6. מחזירים את תוצאת הקריאה הרקורסיבית על `child`.
public static boolean isUpChain(BinNode<Integer> t)
{
if (t == null)
return false; // עץ ריק אינו "שרשרת עולה"
int x = t.getValue();
if (x <= 0 || x % 2 != 0) // הערך חייב להיות חיובי וזוגי
return false;
if (!t.hasLeft() && !t.hasRight()) // עלה תקין - סוף השרשרת
return true;
if (t.hasLeft() && t.hasRight()) // לצומת פנימי יש שני בנים
return false;
BinNode<Integer> child; // הבן היחיד
if (t.hasLeft())
child = t.getLeft();
else
child = t.getRight();
if (child.getValue() <= x) // הבן חייב להיות גדול מהאב
return false;
return isUpChain(child);
}public static bool IsUpChain(BinNode<int> t)
{
if (t == null)
return false; // עץ ריק אינו "שרשרת עולה"
int x = t.GetValue();
if (x <= 0 || x % 2 != 0) // הערך חייב להיות חיובי וזוגי
return false;
if (!t.HasLeft() && !t.HasRight()) // עלה תקין - סוף השרשרת
return true;
if (t.HasLeft() && t.HasRight()) // לצומת פנימי יש שני בנים
return false;
BinNode<int> child; // הבן היחיד
if (t.HasLeft())
child = t.GetLeft();
else
child = t.GetRight();
if (child.GetValue() <= x) // הבן חייב להיות גדול מהאב
return false;
return IsUpChain(child);
}דוגמאות: העץ מסעיף א' (2 → 4 → 6 → 8 → 10 → 12) מחזיר true. שרשרת 2 → 4 → 7 → 8 מחזירה false (7 אי-זוגי). שרשרת 2 → 4 → 6 → 6 מחזירה false (הבן אינו גדול מהאב). עץ שבו לשורש 2 שני בנים 4 ו-6 מחזיר false.
סיבוכיות: כל צומת נבדק פעם אחת בעבודה קבועה - .
תשובה: הפעולה isUpChain שלמעלה.
שאלה 9 · תורים: איבר במקום נתון ומיזוג הפוך
•אין להשתמש במבני נתונים נוספים.
•אפשר להניח שקיימת פעולה sizeQ המחזירה את מספר האיברים בתור. כותרת הפעולה:
public static int sizeQ(Queue<Integer> q)public static int SizeQ(Queue<int> q)כתבו פעולה המקבלת תור של מספרים שלמים וחיוביים q ומספר שלם חיובי pos. הפעולה תחזיר איבר אשר נמצא במקום pos בתור בלי להוציא אותו מהתור. אם אין מקום pos בתור, הפעולה תחזיר ערך (-1).
הערה: האיבר הנמצא בראש התור הוא איבר במקום 1, איבר אחריו – במקום 2 וכו'.
כותרת הפעולה:
public static int valueAt(Queue<Integer> q, int pos)public static int ValueAt(Queue<int> q, int pos)כתבו פעולה המקבלת 2 תורים של מספרים שלמים q1 ו – q2. הפעולה תיצור ותחזיר תור חדש לפי כלל הבא:
•קודם כול מכניסים איבר ראשון מהתור q1, ואחריו – איבר האחרון מהתור q2.
•איבר 2 מהתור q1, איבר לפני האחרון מהתור q2.
•וכך הלאה.
אפשר להניח שאורכם של 2 התורים שווה.
כותרת הפעולה:
public static Queue<Integer> merge (Queue<Integer>q1,
Queue<Integer>q2)public static Queue<int> Merge (Queue<int>q1, Queue<int>q2)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
הפעולה valueAt שלהלן: אם pos מחוץ לתחום מחזירה -1; אחרת מסובבת את התור סיבוב שלם (remove ואז insert לכל איבר) ושומרת את האיבר שבמקום pos.
הרעיון: אסור להשתמש בתור עזר, ולכן נשתמש בתור עצמו: נוציא כל איבר מהראש ונכניס אותו מיד לסוף. אחרי צעדים (n = מספר האיברים) כל איבר חוזר למקומו המקורי, והתור לא השתנה. במהלך הסיבוב, כשמגיעים לאיבר ה-pos, שומרים את ערכו.
1. `n = sizeQ(q)`. אם `pos < 1` או `pos > n` - אין מקום כזה, מחזירים -1.
2. עבור `i` מ-1 עד `n`: `x = q.remove()`; אם `i == pos` שומרים `result = x`; מכניסים את `x` חזרה לסוף התור.
3. מחזירים את `result`.
חשוב לא לעצור באמצע הסיבוב - אחרת סדר התור ישתנה.
public static int valueAt(Queue<Integer> q, int pos)
{
int n = sizeQ(q);
if (pos < 1 || pos > n)
return -1;
int result = -1;
for (int i = 1; i <= n; i++) // סיבוב שלם: כל איבר יוצא ונכנס חזרה לסוף
{
int x = q.remove();
if (i == pos)
result = x;
q.insert(x);
}
return result;
}public static int ValueAt(Queue<int> q, int pos)
{
int n = SizeQ(q);
if (pos < 1 || pos > n)
return -1;
int result = -1;
for (int i = 1; i <= n; i++) // סיבוב שלם: כל איבר יוצא ונכנס חזרה לסוף
{
int x = q.Remove();
if (i == pos)
result = x;
q.Insert(x);
}
return result;
}דוגמה: עבור התור 5, 8, 2, 7 (5 בראש): valueAt(q, 3) מחזירה 2, valueAt(q, 5) מחזירה -1, והתור נשאר 5, 8, 2, 7.
תשובה: הפעולה valueAt שלמעלה.
סעיף ב
הפעולה merge שלהלן: עבור i מ-1 עד n מכניסה לתור החדש את valueAt(q1, i) ואחריו את valueAt(q2, n-i+1).
הרעיון: האיבר ה- מתחילת q1 הוא במקום , והאיבר ה- מסוף q2 הוא במקום (כאשר אורך התורים). הפעולה valueAt מסעיף א' מחזירה איבר בכל מקום בלי לשנות את התור, ולכן אפשר לבנות את התור החדש ישירות, בלי מבנה עזר נוסף, ושני התורים המקוריים נשארים ללא שינוי.
1. `n = sizeQ(q1)` (שני התורים באותו אורך).
2. עבור `i` מ-1 עד `n`: מכניסים ל-`result` את `valueAt(q1, i)` ואחריו את `valueAt(q2, n - i + 1)`.
3. מחזירים את `result`.
public static Queue<Integer> merge(Queue<Integer> q1, Queue<Integer> q2)
{
Queue<Integer> result = new Queue<Integer>();
int n = sizeQ(q1); // אורך שני התורים שווה
for (int i = 1; i <= n; i++)
{
result.insert(valueAt(q1, i)); // האיבר ה-i מתחילת q1
result.insert(valueAt(q2, n - i + 1)); // האיבר ה-i מסוף q2
}
return result;
}public static Queue<int> Merge(Queue<int> q1, Queue<int> q2)
{
Queue<int> result = new Queue<int>();
int n = SizeQ(q1); // אורך שני התורים שווה
for (int i = 1; i <= n; i++)
{
result.Insert(ValueAt(q1, i)); // האיבר ה-i מתחילת q1
result.Insert(ValueAt(q2, n - i + 1)); // האיבר ה-i מסוף q2
}
return result;
}דוגמה: q1 = 1, 2, 3, 4 ו-q2 = 10, 20, 30, 40 (הראש משמאל): התור החדש הוא 1, 40, 2, 30, 3, 20, 4, 10.
תשובה: הפעולה merge שלמעלה.
סעיף ג
valueAt: ; merge: .
נסמן ב- את מספר האיברים בתור. פעולות התור הן , ו-sizeQ עוברת על התור - .
1. valueAt: קריאה ל-sizeQ - , ולולאה של סיבובים עם `remove` ו-`insert` - . בסך הכול .
2. merge: הלולאה מתבצעת פעמים, ובכל סיבוב שתי קריאות ל-valueAt, כל אחת . בסך הכול .
תשובה: סעיף א' - ; סעיף ב' - .
שאלה 10 · ירושה ודריסה: מעקב פלט וספירת טיפוסים
נתונות 2 המחלקות הבאות:
public class AA{
public AA(){
System.out.println("AA constructor");
}
public void one() {
System.out.println("one in AA");
}
public void two() {
one();
}
}
public class BB extends AA{
public BB(){
System.out.println("BB constructor");
}
public void one(){
System.out.println("one in BB");
}
public void two() {
System.out.println("two in BB");
}
public void three() {
super.two();
}
}public class AA{
public AA(){
Console.WriteLine("AA constructor");
}
public virtual void One() {
Console.WriteLine("One in AA");
}
public virtual void Two() {
One();
}
}
public class BB : AA{
public BB(){
Console.WriteLine("BB constructor");
}
public override void One(){
Console.WriteLine("One in BB");
}
public override void Two() {
Console.WriteLine("Two in BB");
}
public void Three() {
base.Two();
}
}נתון קטע הקוד הבא (מספרי שורות לא חלק של הקוד)
(1) AA a = new AA();
(2) BB b = new BB();
(3) AA ab = new BB();
(4) a.one();
(5) ab.one();
(6) b.one();
(7) a.two();
(8) ab.two();
(9) b.two();
(10) ((BB)(ab)).three();
(11) b.three();(1) AA a = new AA();
(2) BB b = new BB();
(3) AA ab = new BB();
(4) a.One();
(5) ab.One();
(6) b.One();
(7) a.Two();
(8) ab.Two();
(9) b.Two();
(10) ((BB)(ab)).Three();
(11) b.Three();עקבו אחרי ביצוע קטע הקוד ורשמו מה יהיה הפלט
האם אפשר להוסיף לקטע הקוד את 2 הפקודות הבאות? הסבירו את תשובתכם
a.three();
((BB)a).three();a.Three();
((BB)a).Three();כתבו פעולה המקבלת מערך הפניות לעצמים מסוג Object. הפעולה תדפיס כמה עצמים הם מסוג BB, כמה עצמים הם מסוג AA ולא סוג BB וכמה עצמים הם לא מסוג AA.
◂ פתרון מלא לשאלה 10
סעיף א
AA constructor / AA constructor, BB constructor / AA constructor, BB constructor / one in AA / one in BB / one in BB / one in AA / two in BB / two in BB / one in BB / one in BB
•יצירת עצם של BB מפעילה קודם את הבנאי של AA (מחלקת הבסיס) ואחר כך את הבנאי של BB.
•זימון פעולה שנדרסה נקבע לפי הטיפוס האמיתי של העצם, לא לפי טיפוס המשתנה (פולימורפיזם).
•`super.two()` (ב-C#: `base.Two()`) מפעיל את הגרסה של AA ל-`two`; אבל בתוכה הזימון `one()` הוא זימון רגיל על העצם הנוכחי, ולכן גם הוא נקבע לפי הטיפוס האמיתי.
ב-C# הפלט זהה, עם אות ראשונה גדולה בשמות הפעולות (`One in AA`, `One in BB`, `Two in BB`), כפי שמודפס במחלקות.
תשובה: הפלט (שורה אחרי שורה):
AA constructor
AA constructor
BB constructor
AA constructor
BB constructor
one in AA
one in BB
one in BB
one in AA
two in BB
two in BB
one in BB
one in BBלא. a.three() - שגיאת הידור (ל-AA אין פעולה three); ((BB)a).three() - עוברת הידור אבל גורמת לשגיאת זמן ריצה (a מפנה לעצם AA, שאינו BB).
1. `a.three();` - הטיפוס המוצהר של `a` הוא AA, ובמחלקה AA אין פעולה `three`. המהדר בודק זימונים לפי הטיפוס המוצהר, ולכן זו שגיאת הידור.
2. `((BB)a).three();` - המרה מ-AA ל-BB מותרת בהידור (BB יורשת מ-AA), ואחרי ההמרה יש ל-BB פעולה `three`, ולכן השורה עוברת הידור. אבל בזמן ריצה `a` מפנה לעצם שנוצר ב-`new AA()`, שאינו BB, ולכן ההמרה נכשלת - שגיאת זמן ריצה (`ClassCastException` ב-Java, `InvalidCastException` ב-C#).
תשובה: אי אפשר: הפקודה הראשונה היא שגיאת הידור, והשנייה גורמת לשגיאת זמן ריצה.
סעיף ב
הפעולה countTypes שלהלן: לכל איבר - אם instanceof BB מגדילה מונה BB, אחרת אם instanceof AA מגדילה מונה AA-לא-BB, אחרת מונה לא-AA; ומדפיסה את שלושת המונים.
הרעיון: `instanceof` (ב-C#: `is`) מחזיר true גם עבור עצם של מחלקה יורשת. עצם BB הוא גם AA, ולכן הסדר בבדיקות חשוב: קודם בודקים BB; אם העצם אינו BB בודקים AA - ואז הוא AA ולא BB; ואם גם זה לא - העצם אינו AA. כך כל עצם נספר בדיוק בקבוצה אחת.
public static void countTypes(Object[] arr)
{
int countBB = 0, countAAnotBB = 0, countNotAA = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof BB)
countBB++;
else if (arr[i] instanceof AA)
countAAnotBB++;
else
countNotAA++;
}
System.out.println("BB: " + countBB);
System.out.println("AA and not BB: " + countAAnotBB);
System.out.println("not AA: " + countNotAA);
}public static void CountTypes(object[] arr)
{
int countBB = 0, countAAnotBB = 0, countNotAA = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is BB)
countBB++;
else if (arr[i] is AA)
countAAnotBB++;
else
countNotAA++;
}
Console.WriteLine("BB: " + countBB);
Console.WriteLine("AA and not BB: " + countAAnotBB);
Console.WriteLine("not AA: " + countNotAA);
}דוגמה: עבור מערך שבו `a`, `b`, `ab` מקטע הקוד, מחרוזת, מספר ועוד `new AA()` - יודפסו BB: 2 (b, ab), AA and not BB: 2, not AA: 2.
תשובה: הפעולה countTypes שלמעלה.
שאלה 11 · מחלקות סטודנט ומאגר מתנדבים
ארגון סטודנטים מתנדבים "עזרה לגיל זהב" מחזיק מאגר מידע של סטודנטים הרוצים להתנדב ולעזור לקשישים, בצורה ממוחשבת . עבור כל סטודנט נשמרים הנתונים הבאים:
•מספר תעודת הזהות (מחרוזת)
•שם (מחרוזת)
•יישוב מגורים (מחרוזת)
•אם יש לו רכב (ערך בוליאני, true – כן, false – לא)
•שפת האם (מחרוזת)
•שפה נוספת שסטודנט שולט בה ברמה גבוהה (מחרוזת)
כתבו את כותרת המחלקה ואת התכונות עבור כל אחת מהמחלקות הבאות:
•Student המתארת סטודנט.
•StudentsData המתארת מידע על כל הסטודנטים.
אפשר להניח שבמחלקה Student קיימים בנאים, פעולות get ו-set לכל תכונה.
בסיום שנת הלימודים יש לעדכן את המערכת ולהוציא מהמאגר (אוסף הנתונים) את הסטודנטים שסיימו ללמוד. כתבו פעולה במחלקה StudentsData המקבלת מספר תעודת זהות של מתנדב ומוציאה אותו מהמאגר. כותרת הפעולה:
public void eraseStudent(String id)public void EraseStudent(string id)מדי פעם מתקבלת בקשה לעזרה מאזרח וותיק אשר מדבר בשפה מסוימת והמתגורר ביישוב מסוים. כתבו במחלקה StudentsData את הפעולה:
public void print(String city, String lang)public void Print(string city, string lang)הפעולה תדפיס את שמות המתנדבים אשר מדברים בשפה lang ומתגוררים ביישוב city.
הנהלת הארגון רוצה לארגן כנס למתנדבים. הוחלט שהכנס יתקיים בעיר שמתגוררים בה הכי הרבה מתנדבים חברי הארגון.
כתבו פעולה במחלקה StudentsData המקבלת שם של עיר ומחזירה את מספר המתנדבים המתגוררים בה. כותרת הפעולה:
public int numStudents(String city)public int NumStudents(string city)כתבו פעולה במחלקה StudentsData המקבלת מערך של שמות ערים (מערך מסוג מחרוזת) ומחזירה את שם העיר שגרים בה הכי הרבה מתנדבים. כותרת הפעולה:
public String cityName(String[] cities)public string CityName(string[] cities)◂ פתרון מלא לשאלה 11
סעיף א
Student: id, name, city (String), hasCar (boolean), motherLang, otherLang (String). StudentsData: Node<Student> students - שרשרת חוליות של כל הסטודנטים.
1. Student: תכונה לכל נתון שברשימה, בטיפוס שנקבע בשאלה: מחרוזות לתעודת זהות, שם, יישוב, שפת אם ושפה נוספת, וערך בוליאני לרכב. התכונות פרטיות (`private`), והגישה אליהן דרך פעולות get/set.
2. StudentsData: צריך אוסף של סטודנטים שאפשר לעבור עליו, להוסיף לו ולמחוק ממנו. נבחר שרשרת חוליות `Node<Student>`: אפשר לעבור עליה בלי להרוס אותה (בניגוד למחסנית ותור) ולמחוק ממנה חוליה באמצע. התכונה `students` מפנה לחוליה הראשונה, ו-null מסמן מאגר ריק.
בפתרון נשתמש בפעולות הגישה `getId()`, `getName()`, `getCity()`, `getHasCar()`, `getMotherLang()`, `getOtherLang()` (ב-C#: `GetId()` וכו').
public class Student
{
private String id; // מספר תעודת זהות
private String name; // שם
private String city; // יישוב מגורים
private boolean hasCar; // האם יש לו רכב
private String motherLang; // שפת האם
private String otherLang; // שפה נוספת ברמה גבוהה
// בנאים, פעולות get ו-set לכל תכונה (לפי הנתון)
}
public class StudentsData
{
private Node<Student> students; // שרשרת חוליות של כל הסטודנטים במאגר
// (null כשהמאגר ריק)
}public class Student
{
private string id; // מספר תעודת זהות
private string name; // שם
private string city; // יישוב מגורים
private bool hasCar; // האם יש לו רכב
private string motherLang; // שפת האם
private string otherLang; // שפה נוספת ברמה גבוהה
// בנאים, פעולות Get ו-Set לכל תכונה (לפי הנתון)
}
public class StudentsData
{
private Node<Student> students; // שרשרת חוליות של כל הסטודנטים במאגר
// (null כשהמאגר ריק)
}תשובה: כמו בקוד שלמעלה.
סעיף ב
הפעולה eraseStudent שלהלן: אם הסטודנט בחוליה הראשונה - מקדמת את students; אחרת מחפשת את החוליה שלפניו ומדלגת עליו עם setNext.
הרעיון: מחיקה משרשרת חוליות נעשית על ידי "עקיפה": החוליה שלפני החוליה שנמחקת מפנה ישירות לחוליה שאחריה. לכן מחפשים את החוליה שהבאה אחריה מכילה את הסטודנט. מקרה מיוחד: הסטודנט בחוליה הראשונה - אז מעדכנים את `students` עצמו.
1. אם המאגר ריק - אין מה למחוק.
2. אם לסטודנט בחוליה הראשונה יש תעודת הזהות `id` - `students = students.getNext()`.
3. אחרת עוברים עם `p`; כאשר `p.getNext()` מכיל את הסטודנט המבוקש - `p.setNext(p.getNext().getNext())` ומסיימים.
4. אם הסטודנט לא נמצא - המאגר לא משתנה.
ב-Java משווים מחרוזות עם `equals` (ולא `==`, שמשווה הפניות); ב-C# האופרטור `==` משווה את תוכן המחרוזות.
public void eraseStudent(String id)
{
if (students == null)
return;
if (students.getValue().getId().equals(id)) // הסטודנט בחוליה הראשונה
{
students = students.getNext();
return;
}
Node<Student> p = students;
while (p.getNext() != null)
{
if (p.getNext().getValue().getId().equals(id))
{
p.setNext(p.getNext().getNext()); // עקיפת החוליה שנמחקת
return;
}
p = p.getNext();
}
}public void EraseStudent(string id)
{
if (students == null)
return;
if (students.GetValue().GetId() == id) // הסטודנט בחוליה הראשונה
{
students = students.GetNext();
return;
}
Node<Student> p = students;
while (p.GetNext() != null)
{
if (p.GetNext().GetValue().GetId() == id)
{
p.SetNext(p.GetNext().GetNext()); // עקיפת החוליה שנמחקת
return;
}
p = p.GetNext();
}
}תשובה: הפעולה eraseStudent שלמעלה.
סעיף ג
הפעולה print שלהלן: מעבר ראשון מדפיס את דוברי lang הגרים ב-city ומסמן אם נמצא מישהו; אם לא - מעבר שני מדפיס את דוברי lang שיש להם רכב.
הרעיון: סטודנט "מדבר בשפה lang" אם זו שפת האם שלו או השפה הנוספת שלו - נכתוב לכך פעולת עזר `speaks`. עוברים על השרשרת פעם אחת ומדפיסים את מי שגר ב-city ומדבר lang, ובמשתנה בוליאני `found` זוכרים אם הודפס מישהו. אם לא - עוברים פעם שנייה ומדפיסים את דוברי lang שיש להם רכב (הם יכולים להגיע מיישוב אחר).
1. `found = false`; עוברים על כל החוליות. אם הסטודנט גר ב-`city` ו-`speaks(s, lang)` - מדפיסים את שמו ו-`found = true`.
2. אם `found` נשאר false - עוברים שוב מהתחלה ומדפיסים כל סטודנט שעבורו `speaks(s, lang)` וגם `getHasCar()`.
private static boolean speaks(Student s, String lang)
{
return s.getMotherLang().equals(lang) || s.getOtherLang().equals(lang);
}
public void print(String city, String lang)
{
boolean found = false;
Node<Student> p = students;
while (p != null) // מעבר ראשון: יישוב ושפה
{
Student s = p.getValue();
if (s.getCity().equals(city) && speaks(s, lang))
{
System.out.println(s.getName());
found = true;
}
p = p.getNext();
}
if (!found) // מעבר שני: דוברי השפה בעלי רכב
{
p = students;
while (p != null)
{
Student s = p.getValue();
if (speaks(s, lang) && s.getHasCar())
System.out.println(s.getName());
p = p.getNext();
}
}
}private static bool Speaks(Student s, string lang)
{
return s.GetMotherLang() == lang || s.GetOtherLang() == lang;
}
public void Print(string city, string lang)
{
bool found = false;
Node<Student> p = students;
while (p != null) // מעבר ראשון: יישוב ושפה
{
Student s = p.GetValue();
if (s.GetCity() == city && Speaks(s, lang))
{
Console.WriteLine(s.GetName());
found = true;
}
p = p.GetNext();
}
if (!found) // מעבר שני: דוברי השפה בעלי רכב
{
p = students;
while (p != null)
{
Student s = p.GetValue();
if (Speaks(s, lang) && s.GetHasCar())
Console.WriteLine(s.GetName());
p = p.GetNext();
}
}
}תשובה: הפעולה print שלמעלה (עם פעולת העזר speaks).
סעיף ד
הפעולה numStudents שלהלן: סופרת את החוליות שבהן getCity() שווה ל-city.
הרעיון: מעבר אחד על שרשרת הסטודנטים עם מונה: כל סטודנט שהיישוב שלו שווה ל-`city` מגדיל את המונה.
public int numStudents(String city)
{
int count = 0;
Node<Student> p = students;
while (p != null)
{
if (p.getValue().getCity().equals(city))
count++;
p = p.getNext();
}
return count;
}public int NumStudents(string city)
{
int count = 0;
Node<Student> p = students;
while (p != null)
{
if (p.GetValue().GetCity() == city)
count++;
p = p.GetNext();
}
return count;
}תשובה: הפעולה numStudents שלמעלה.
הפעולה cityName שלהלן: מחשבת numStudents לכל עיר במערך ומחזירה את העיר עם המספר הגדול ביותר.
הרעיון: חיפוש מקסימום על המערך, כשהערך של כל עיר מחושב בפעולה `numStudents` מסעיף 1. מתחילים מהעיר הראשונה כמקסימום זמני ומשווים אליה את שאר הערים. (מניחים שהמערך אינו ריק.)
1. `best = cities[0]`, `max = numStudents(cities[0])`.
2. לכל עיר נוספת: `n = numStudents(cities[i])`; אם `n > max` - מעדכנים `max` ו-`best`.
3. מחזירים את `best`.
public String cityName(String[] cities)
{
String best = cities[0];
int max = numStudents(cities[0]);
for (int i = 1; i < cities.length; i++)
{
int n = numStudents(cities[i]);
if (n > max)
{
max = n;
best = cities[i];
}
}
return best;
}public string CityName(string[] cities)
{
string best = cities[0];
int max = NumStudents(cities[0]);
for (int i = 1; i < cities.Length; i++)
{
int n = NumStudents(cities[i]);
if (n > max)
{
max = n;
best = cities[i];
}
}
return best;
}תשובה: הפעולה cityName שלמעלה.
שאלה 12 · פעולות רקורסיביות על שרשרת חוליות
נתונה פעולה רקורסיבית הבאה:
public static void one(Node<Integer> n){
if(n!=null)
{
if(n.getValue()% 2==0)
{
n.setNext(new Node<Integer> (0,n.getNext()));
n = n.getNext();
}
one(n.getNext());
}
}public static void One(Node<int> n){
if(n!=null)
{
if(n.GetValue()% 2==0)
{
n.SetNext(new Node<int> (0,n.GetNext()));
n = n.GetNext();
}
One(n.GetNext());
}
}
עקבו אחרי זימון הפעולה one(chain) ורשמו איך תיראה השרשרת אחרי ביצוע הפעולה.
מה מבצעת הפעולה one באופן כללי?
נתונה פעולה רקורסיבית two הבאה:
public static void two(Node<Integer> n){
if(n.getNext()!=null)
{
if(n.getNext().getValue()%2 == 0)
n.setNext(n.getNext().getNext());
else
n=n.getNext();
two(n);
}
}public static void Two(Node<int> n){
if(n.GetNext()!=null)
{
if(n.GetNext().GetValue()%2 == 0)
n.SetNext(n.GetNext().GetNext());
else
n=n.GetNext();
Two(n);
}
}עקבו אחרי זימון הפעולה two(chain) ורשמו איך תיראה השרשרת אחרי ביצוע הפעולה.
מה מבצעת הפעולה two באופן כללי?
נתונה הפעולה three המשתמשת בפעולה two.
public static Node<Integer> three(Node<Integer>n){
if(n == null) return null;
if(n.getValue()%2 == 0)
return three(n.getNext());
else
{
two(n);
return n;
}
}public static Node<int> Three(Node<int>n){
if(n == null) return null;
if(n.GetValue()%2 == 0)
return Three(n.GetNext());
else
{
Two(n);
return n;
}
}מה יהיה התוכן של הרשימה chain אחרי ביצוע הפקודה הבאה.
chain = three(chain);chain = Three(chain);מה מבצעת הפעולה three באופן כללי?
◂ פתרון מלא לשאלה 12
סעיף א
10 → 0 → 12 → 0 → 5 → 3 → 6 → 0 → 1 → 4 → 0
מה קורה בכל זימון: אם הערך בחוליה `n` זוגי, נוצרת אחריה חוליה חדשה עם 0, ו-`n` מתקדם לחוליה החדשה. אחר כך הרקורסיה ממשיכה מהחוליה שאחרי `n` - כלומר מהחוליה המקורית הבאה (החוליה עם 0 לא נבדקת).
טבלת מעקב (השרשרת: 10, 12, 5, 3, 6, 1, 4):
תשובה: 10 → 0 → 12 → 0 → 5 → 3 → 6 → 0 → 1 → 4 → 0.
סעיף ב
מוסיפה חוליה עם הערך 0 אחרי כל חוליה שערכה זוגי בשרשרת.
מהמעקב בסעיף א': הפעולה עוברת על כל החוליות המקוריות של השרשרת, ואחרי כל חוליה שהערך שלה זוגי היא משבצת חוליה חדשה עם הערך 0. חוליות עם ערך אי-זוגי אינן משתנות. אין יצירה של שרשרת חדשה - השרשרת הקיימת משתנה.
תשובה: הפעולה מכניסה 0 אחרי כל איבר זוגי בשרשרת.
סעיף ג
10 → 5 → 3 → 1
מה קורה בכל זימון: בודקים את החוליה שאחרי `n`. אם הערך שלה זוגי - מוחקים אותה (`n` מדלג עליה) ו-`n` נשאר במקומו, כדי לבדוק גם את החוליה החדשה שאחריו. אם הערך אי-זוגי - `n` מתקדם אליה. העצירה כאשר אין ל-`n` חוליה עוקבת. החוליה הראשונה עצמה אף פעם לא נבדקת.
המעקב על השרשרת שבאיור (10, 12, 5, 3, 6, 1, 4):
(גם אם מפעילים את two על השרשרת שהתקבלה בסעיף א' מתקבלת אותה תוצאה, כי כל האפסים וכל הערכים הזוגיים שאחרי החוליה הראשונה נמחקים.)
תשובה: 10 → 5 → 3 → 1.
סעיף ד
מוחקת מהשרשרת את כל החוליות בעלות ערך זוגי, החל מהחוליה השנייה (החוליה הראשונה נשארת תמיד).
מהמעקב בסעיף ג': הפעולה בודקת כל חוליה שאחרי החוליה הנוכחית ומוחקת אותה אם הערך שלה זוגי. כך נמחקות מהשרשרת הקיימת כל החוליות הזוגיות פרט לחוליה הראשונה, שאינה נבדקת כלל (גם אם היא זוגית, כמו 10 בדוגמה). נשארים: החוליה הראשונה וכל החוליות האי-זוגיות, באותו סדר.
תשובה: two מוחקת את כל האיברים הזוגיים בשרשרת, חוץ מהאיבר הראשון.
סעיף ה
chain = 5 → 3 → 1; three מדלגת על החוליות הזוגיות שבתחילת השרשרת עד לחוליה האי-זוגית הראשונה, מוחקת אחריה את כל החוליות הזוגיות (בעזרת two) ומחזירה הפנייה אליה - כלומר שרשרת של האיברים האי-זוגיים בלבד (null אם אין כאלה).
מעקב על השרשרת שבאיור (10, 12, 5, 3, 6, 1, 4):
1. `three(10)`: 10 זוגי - מחזירה `three(12)`.
2. `three(12)`: 12 זוגי - מחזירה `three(5)`.
3. `three(5)`: 5 אי-זוגי - מזמנת `two(5)`. כמו בסעיף ג', two מוחקת את החוליות הזוגיות שאחרי 5: נמחקים 6 ו-4, ומהחוליה 5 והלאה נשאר 5, 3, 1. מוחזרת הפנייה לחוליה 5.
4. ההפניה חוזרת דרך כל הקריאות, ו-`chain` מקבל את החוליה 5.
(אותה תוצאה מתקבלת גם על השרשרת שאחרי סעיף א': החוליות 10, 0, 12, 0 שבהתחלה זוגיות ומדולגות.)
באופן כללי: three מדלגת על כל החוליות הזוגיות שבתחילת השרשרת עד החוליה האי-זוגית הראשונה. מהחוליה הזאת היא מפעילה את two, שמוחקת את כל החוליות הזוגיות שאחריה, ומחזירה הפנייה אליה. מכיוון שהחוליה הראשונה של התוצאה אי-זוגית, התוצאה היא שרשרת שמכילה רק את האיברים האי-זוגיים של השרשרת המקורית, בסדרם המקורי. אם אין בשרשרת אף איבר אי-זוגי - מוחזר null.
תשובה: chain = 5 → 3 → 1. three מחזירה את השרשרת כשהיא מכילה רק את האיברים האי-זוגיים (מסירה את כל הזוגיים).