מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2024 מועד ב'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2024 מועד ב', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 17)
בכל מבחן עשר שאלות.
שאלות 1-5: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 6-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 11-12: יש לענות על שאלה אחת בלבד. ערך השאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית שוויון: זוגיים מול אי-זוגיים
מחסנית של מספרים שלמים נקראת "מחסנית שוויון" אם היא עונה על שלושת התנאים הבאים:
•במחסנית יש רק ערכים החיוביים.
•מספר האיברים הזוגיים שווה למספר האיברים האי-זוגיים.
•סכום האיברים הזוגיים שווה לסכום האיברים האי-זוגיים.
כתבו פעולה המקבלת מחסנית של מספרים שלמים ובודקת אם היא "מחסנית שוויון".
יש לשמור על תוכן של המחסנית אחרי ביצוע הפעולה. כותרת הפעולה:
public static boolean isParityStack(Stack<Integer> st)public static bool IsParityStack(Stack<int> st)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
מעבר אחד עם מחסנית עזר: סופרים וסוכמים זוגיים ואי-זוגיים ובודקים שכל הערכים חיוביים; משחזרים את המחסנית ומחזירים true רק אם שלושת התנאים מתקיימים.
נתון: מחסנית `st` של מספרים שלמים.
מבוקש: לבדוק אם היא "מחסנית שוויון": כל הערכים חיוביים, מספר הזוגיים שווה למספר האי-זוגיים, וסכום הזוגיים שווה לסכום האי-זוגיים. בסוף המחסנית צריכה להישאר כפי שהייתה.
הרעיון: כל שלושת התנאים נבדקים במעבר אחד על המחסנית, בעזרת ארבעה מונים ודגל אחד:
1. מוציאים איבר `x` מהמחסנית ודוחפים אותו למחסנית עזר `temp`, כדי שנוכל לשחזר את המחסנית המקורית בסוף.
2. אם `x` אינו חיובי () – מכבים את הדגל `allPositive`.
3. אם `x` זוגי – מגדילים את מונה הזוגיים `countEven` ומוסיפים את `x` לסכום `sumEven`; אחרת – מגדילים את `countOdd` ומוסיפים ל-`sumOdd`.
4. אחרי שהמחסנית התרוקנה מחזירים את כל האיברים מ-`temp` ל-`st`. מכיוון שמחסנית הופכת את הסדר פעמיים, הסדר המקורי חוזר.
5. מחזירים true רק אם שלושת התנאים מתקיימים יחד: `allPositive`, `countEven == countOdd` ו-`sumEven == sumOdd`.
דוגמה: עבור מחסנית שבראשה : הזוגיים – שניים, סכומם ; האי-זוגיים – שניים, סכומם ; כל הערכים חיוביים, ולכן התשובה true. עבור סכום הזוגיים וסכום האי-זוגיים , ולכן התשובה false.
(מחסנית ריקה מקיימת את שלושת התנאים באופן ריק – זוגיים ו- אי-זוגיים, הסכומים – ולכן הפעולה מחזירה עבורה true.)
public static boolean isParityStack(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
boolean allPositive = true; // האם כל הערכים חיוביים
int countEven = 0, countOdd = 0; // מספר הזוגיים / האי-זוגיים
int sumEven = 0, sumOdd = 0; // סכום הזוגיים / האי-זוגיים
while (!st.isEmpty())
{
int x = st.pop();
temp.push(x);
if (x <= 0)
allPositive = false;
if (x % 2 == 0)
{
countEven++;
sumEven += x;
}
else
{
countOdd++;
sumOdd += x;
}
}
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return allPositive && countEven == countOdd && sumEven == sumOdd;
}public static bool IsParityStack(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
bool allPositive = true; // האם כל הערכים חיוביים
int countEven = 0, countOdd = 0; // מספר הזוגיים / האי-זוגיים
int sumEven = 0, sumOdd = 0; // סכום הזוגיים / האי-זוגיים
while (!st.IsEmpty())
{
int x = st.Pop();
temp.Push(x);
if (x <= 0)
allPositive = false;
if (x % 2 == 0)
{
countEven++;
sumEven += x;
}
else
{
countOdd++;
sumOdd += x;
}
}
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return allPositive && countEven == countOdd && sumEven == sumOdd;
}תשובה: מעבר אחד על המחסנית (דרך מחסנית עזר) שסופר ומסכם בנפרד זוגיים ואי-זוגיים ובודק שכל הערכים חיוביים; בסוף משחזרים את המחסנית ומחזירים true רק אם שלושת התנאים מתקיימים.
סעיף ב
נסמן ב- את מספר האיברים במחסנית.
1. הלולאה הראשונה מוציאה כל איבר פעם אחת – סיבובים, ובכל סיבוב מספר קבוע של פעולות : pop, push, השוואה, עדכון מונה וסכום.
2. הלולאה השנייה מחזירה את האיברים למחסנית – עוד סיבובים של .
3. סך הכול סיבובים, כלומר .
תשובה: – כל איבר מוצא מהמחסנית ומוחזר אליה פעם אחת בלבד.
שאלה 2 · מרחק בין שני איברים בתור
נתון התור q של מספרים שלמים. כל איבר בתור מופיע פעם אחת (אין חזרות). המרחק בין שני איברים בתור הוא כמות האיברים הנמצאים ביניהם.
כתבו פעולה המקבלת תור q ושני מספרים נוספים x ו- y. הפעולה תחשב ותחזיר את המרחק בין שני איברי התור שערכם x ו- y.
עבור התור q הבא ופרמטרים הפעולה תחזיר 4 כי בין הערכים 10 ו- 12 יש בתור ארבעה איברים:
עבור התור q ופרמטרים הפעולה גם תחזיר 4 כי בין הערכים 10 ו- 12 ישנם בתור ארבעה איברים.
אם בתור אין איבר שערכו x או אין איבר שערכו y, הפעולה תחזיר ערך .
כותרת הפעולה:
public static int distance(Queue<Integer> q, int x, int y)public static int Distance(Queue<int> q, int x, int y)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
מעבר אחד שמוצא את מקומות x ו-y (עם תור עזר ושחזור) ומחזיר , או אם אחד חסר; בדוגמה .
נתון: תור `q` של מספרים שלמים בלי חזרות, ושני מספרים `x`, `y`.
מבוקש: מספר האיברים שנמצאים בתור בין `x` ל-`y`, או אם אחד מהם אינו בתור.
הרעיון: בתור אין גישה לפי מיקום, ולכן עוברים על כל התור פעם אחת וממספרים את האיברים מ-0. כך מוצאים את המיקום של `x` (`posX`) ואת המיקום של `y` (`posY`).
1. מוציאים את האיברים מ-`q` אחד אחד, מעבירים אותם לתור עזר `temp`, ומקדמים מונה מיקום `i`. כשהערך שווה ל-`x` שומרים `posX = i`, וכשהוא שווה ל-`y` שומרים `posY = i`.
2. מחזירים את כל האיברים מ-`temp` ל-`q`. תור הוא FIFO, ולכן הסדר נשמר.
3. אם אחד המיקומים נשאר – אחד הערכים לא נמצא, ומחזירים .
4. אחרת, בין המקום `posX` למקום `posY` יש בדיוק איברים (המרחק בין המקומות פחות 1, כי שני האיברים עצמם אינם נספרים). הערך המוחלט מטפל גם במקרה ש-`y` נמצא לפני `x`.
בדיקה עם הדוגמה: בתור (מהראש): נמצא במקום ו- במקום , ולכן המרחק (האיברים ). עבור מתקבל , כמו בדוגמה.
public static int distance(Queue<Integer> q, int x, int y)
{
Queue<Integer> temp = new Queue<Integer>();
int posX = -1, posY = -1; // המיקומים של x ו-y בתור
int i = 0; // מיקום האיבר הנוכחי (מ-0)
while (!q.isEmpty())
{
int val = q.remove();
temp.insert(val);
if (val == x)
posX = i;
if (val == y)
posY = i;
i++;
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
if (posX == -1 || posY == -1)
return -1;
return Math.abs(posX - posY) - 1;
}public static int Distance(Queue<int> q, int x, int y)
{
Queue<int> temp = new Queue<int>();
int posX = -1, posY = -1; // המיקומים של x ו-y בתור
int i = 0; // מיקום האיבר הנוכחי (מ-0)
while (!q.IsEmpty())
{
int val = q.Remove();
temp.Insert(val);
if (val == x)
posX = i;
if (val == y)
posY = i;
i++;
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
if (posX == -1 || posY == -1)
return -1;
return Math.Abs(posX - posY) - 1;
}תשובה: מוצאים במעבר אחד את המיקומים של x ו-y (התור משוחזר דרך תור עזר) ומחזירים , או אם אחד מהם חסר. בדוגמה מוחזר .
סעיף ב
נסמן ב- את מספר האיברים בתור.
1. הלולאה הראשונה מעבירה כל איבר מ-`q` ל-`temp` – סיבובים של (הוצאה, הכנסה, שתי השוואות).
2. הלולאה השנייה מחזירה את האיברים – עוד סיבובים של .
3. החישוב בסוף הוא . סך הכול , כלומר .
תשובה: – כל איבר מוצא מהתור ומוחזר אליו פעם אחת.
שאלה 3 · שרשרת שבה כל ערך מופיע פעמיים
שרשרת נקראת "שרשרת חזרות" אם כל ערך שבה מופיע בדיוק פעמיים. כתבו פעולה המקבלת הפניה לחוליה ראשונה של שרשרת תווים. הפעולה תבדוק אם השרשרת היא "שרשרת חזרות". אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean repeatList(Node<Character> chain)public static bool RepeatList(Node<char> chain)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
לכל חוליה סופרים את מספר ההופעות של ערכה בשרשרת; אם מספר כלשהו שונה מ-2 – false, אחרת true.
נתון: הפניה לחוליה הראשונה של שרשרת תווים.
מבוקש: true אם כל ערך בשרשרת מופיע בה בדיוק פעמיים, אחרת false.
הרעיון: לכל חוליה `p` בשרשרת סופרים כמה פעמים הערך שלה מופיע בכל השרשרת (מעבר שני, מתחילתה, עם הפניה `r`). אם נמצא ערך שמספר הופעותיו שונה מ-2 – השרשרת אינה "שרשרת חזרות" ומחזירים false מיד. אם כל הערכים עברו את הבדיקה – מחזירים true.
1. לולאה חיצונית: `p` עובר על כל חוליות השרשרת.
2. לולאה פנימית: `r` עובר על כל השרשרת מההתחלה, וסופר ב-`count` את החוליות שערכן שווה לערך של `p`. הספירה כוללת גם את `p` עצמה.
3. אם `count != 2` – מחזירים false.
4. בסוף הלולאה החיצונית מחזירים true.
דוגמאות: בשרשרת `a → b → b → a` כל תו מופיע פעמיים – true. בשרשרת `a → a → b` התו `b` מופיע פעם אחת – false. בשרשרת `a → a → a` התו `a` מופיע שלוש פעמים – false. (עבור שרשרת ריקה, null, התנאי מתקיים באופן ריק והפעולה מחזירה true.)
public static boolean repeatList(Node<Character> chain)
{
Node<Character> p = chain;
while (p != null)
{
char c = p.getValue();
int count = 0; // מספר ההופעות של c בשרשרת
Node<Character> r = chain;
while (r != null)
{
if (r.getValue() == c)
count++;
r = r.getNext();
}
if (count != 2)
return false;
p = p.getNext();
}
return true;
}public static bool RepeatList(Node<char> chain)
{
Node<char> p = chain;
while (p != null)
{
char c = p.GetValue();
int count = 0; // מספר ההופעות של c בשרשרת
Node<char> r = chain;
while (r != null)
{
if (r.GetValue() == c)
count++;
r = r.GetNext();
}
if (count != 2)
return false;
p = p.GetNext();
}
return true;
}תשובה: לכל חוליה סופרים במעבר נוסף על השרשרת את מספר ההופעות של ערכה; אם מספר כלשהו שונה מ-2 מחזירים false, ואחרת true.
סעיף ב
נסמן ב- את מספר החוליות בשרשרת.
1. הלולאה החיצונית עוברת על חוליות.
2. לכל אחת מהן הלולאה הפנימית עוברת על כל החוליות, וכל סיבוב הוא .
3. במקרה הגרוע (כשהשרשרת היא אכן "שרשרת חזרות" ואין יציאה מוקדמת) מתבצעים סיבובים פנימיים.
תשובה: – לכל אחת מ- החוליות סופרים את ההופעות במעבר מלא על השרשרת.
שאלה 4 · ירושה ופולימורפיזם: מכתבים וחבילות
ברשות הדואר החליטו למחשב את המערך לקבלת דברי הדואר. לצורך כך הוגדרו שלוש מחלקות שונות:
Letter ,MailItem ו- Package.
המחלקה Letter מייצגת מכתב. בעבור כל מכתב יש לשמור את הנתונים הבאים:
•שם שולח המכתב, מטיפוס מחרוזת, String (ב-C#: string).
•מען המכתב (כתובת), מטיפוס מחרוזת, String (ב-C#: string).
•דואר רשום מטיפוס בוליאני, boolean (ב-C#: bool): true – עבור דואר רשום, false – עבור דואר רגיל.
•גודל המכתב, טיפוס תווי, char ('S' – עבור מכתב קטן, 'B' – עבור מכתב בגודל סטנדרטי, 'L' – עבור מכתב גדול).
•מחיר בסיסי למשלוח מכתב בגודל סטנדרטי, מטיפוס מספר ממשי, double
מחיר משלוח מכתב תלוי בגודלו ובסוגו: בעבור מכתב בדואר רשום יש להוסיף 10 ₪, עבור מכתב קטן יש הנחה של שני שקלים, עבור מכתב גדול יש תוספת של 3 ₪
המחלקה Package מייצגת חבילה. בעבור כל מכתב יש לשמור את הנתונים הבאים:
•שם שולח החבילה, מטיפוס מחרוזת, String (ב-C#: string).
•מען המכתב (כתובת), מטיפוס מחרוזת, String (ב-C#: string).
•משקל החבילה בקילוגרמים מטיפוס מספר שלם, int.
•האם שביר?: true – אם תוכן החבילה שביר, false – אם לא שביר.
•מחיר בסיסי למשלוח חבילה מטיפוס מספר ממשי, double.
מחיר משלוח חבילה תלוי בגודל החבילה וסוגה: בעבור משקל פחות מ- 5 קילוגרמים יש לשלם מחיר בסיסי. מעל 5 קילוגרמים יש לשלם תוספת של 3 ₪ לכל קילוגרם נוסף. אם התוכן שביר יש להוסיף עוד 15 ₪.
המחלקה MailItem היא מחלקת האב למחלקות Letter ו-Package (המחלקות Letter ו- Package יורשות מהמחלקה MailItem) בהתאם לעקרונות תכנות מונחה עצמים:

כתבו כותרות ותכונות של כל אחת מהמחלקות Letter ,MailItem ו- Package
כתבו פעולה
public double getRealPrice()public double GetRealPrice()הפעולה תחשב ותחזיר מחיר סופי של משלוח. יש לציין באיזה מחלקה/מחלקות צריך להוסיף את הפעולה בהתאם לעקרונות תכנות מונחה עצמים.
כתבו פעולה
public static String bigSender(MailItem[] args)public static string BigSender(MailItem[] args)הפעולה מקבלת מערך של משלוחים ומחזירה את שם השולח של החבילה היקרה ביותר (חבילה שמחיר המשלוח הוא הגבוה ביותר). אם אין אף חבילה במערך, הפעולה תחזיר ערך null. אפשר להניח שיש רק משלוח אחד כזה. אפשר להניח שקיימות פעולות set/get (ב-C#: Set/Get) בכל מחלקה.
◂ פתרון מלא לשאלה 4
סעיף א
MailItem (מופשטת): sender, address, basePrice; Letter extends MailItem: registered, size; Package extends MailItem: weight, fragile.
מה צריך לייצג: שלוש מחלקות בהיררכיית ירושה. הנתונים המשותפים למכתב ולחבילה – שם השולח, המען והמחיר הבסיסי – נכתבים פעם אחת במחלקת האב `MailItem`. כל מחלקה יורשת מוסיפה רק את התכונות המיוחדות לה:
1. MailItem: שם השולח (מחרוזת), המען (מחרוזת) והמחיר הבסיסי למשלוח (מספר ממשי). המחלקה מוגדרת מופשטת (abstract): אין משלוח "סתם", רק מכתב או חבילה, ובה תוצהר הפעולה המופשטת של סעיף ב'.
2. Letter יורשת מ-`MailItem` ומוסיפה: דואר רשום (בוליאני) וגודל המכתב (תו: 'S', 'B' או 'L').
3. Package יורשת מ-`MailItem` ומוסיפה: משקל בקילוגרמים (מספר שלם) והאם התוכן שביר (בוליאני).
התכונות פרטיות (private), והגישה אליהן נעשית בפעולות get/set, כפי שנאמר בשאלה. הפעולות הבונות של המחלקות היורשות קוראות לפעולה הבונה של מחלקת האב, שמאתחלת את התכונות המשותפות.
public abstract class MailItem
{
private String sender; // שם השולח
private String address; // מען (כתובת)
private double basePrice; // מחיר בסיסי למשלוח
public MailItem(String sender, String address, double basePrice)
{
this.sender = sender;
this.address = address;
this.basePrice = basePrice;
}
...
}
public class Letter extends MailItem
{
private boolean registered; // true - דואר רשום, false - דואר רגיל
private char size; // 'S' - קטן, 'B' - סטנדרטי, 'L' - גדול
public Letter(String sender, String address, double basePrice,
boolean registered, char size)
{
super(sender, address, basePrice);
this.registered = registered;
this.size = size;
}
...
}
public class Package extends MailItem
{
private int weight; // משקל בקילוגרמים
private boolean fragile; // true - שביר, false - לא שביר
public Package(String sender, String address, double basePrice,
int weight, boolean fragile)
{
super(sender, address, basePrice);
this.weight = weight;
this.fragile = fragile;
}
...
}public abstract class MailItem
{
private string sender; // שם השולח
private string address; // מען (כתובת)
private double basePrice; // מחיר בסיסי למשלוח
public MailItem(string sender, string address, double basePrice)
{
this.sender = sender;
this.address = address;
this.basePrice = basePrice;
}
...
}
public class Letter : MailItem
{
private bool registered; // true - דואר רשום, false - דואר רגיל
private char size; // 'S' - קטן, 'B' - סטנדרטי, 'L' - גדול
public Letter(string sender, string address, double basePrice,
bool registered, char size) : base(sender, address, basePrice)
{
this.registered = registered;
this.size = size;
}
...
}
public class Package : MailItem
{
private int weight; // משקל בקילוגרמים
private bool fragile; // true - שביר, false - לא שביר
public Package(string sender, string address, double basePrice,
int weight, bool fragile) : base(sender, address, basePrice)
{
this.weight = weight;
this.fragile = fragile;
}
...
}תשובה: `MailItem` (מופשטת): sender, address (מחרוזות), basePrice (ממשי). `Letter extends MailItem`: registered (בוליאני), size (תו). `Package extends MailItem`: weight (שלם), fragile (בוליאני).
סעיף ב
מופשטת ב-MailItem, נדרסת ב-Letter (בסיס, רשום, קטן, גדול) וב-Package (בסיס, לכל ק"ג מעל 5, שביר).
איפה כותבים את הפעולה: חישוב המחיר הסופי שונה במכתב ובחבילה, אבל לכל משלוח יש מחיר. לכן:
1. ב-`MailItem` מצהירים על הפעולה כמופשטת (abstract) – כך מובטח שלכל משלוח יש `getRealPrice()`, ואפשר לזמן אותה דרך הפניה מטיפוס `MailItem` (נשתמש בזה בסעיף ג').
2. ב-`Letter` וב-`Package` דורסים (override) את הפעולה, וכל אחת מחשבת לפי הכללים שלה. זהו פולימורפיזם: בזמן ריצה מופעלת הגרסה של הטיפוס האמיתי של העצם.
•מכתב: מתחילים מהמחיר הבסיסי; דואר רשום: ₪; מכתב קטן ('S'): ₪; מכתב גדול ('L'): ₪; מכתב סטנדרטי ('B'): ללא שינוי.
•חבילה: מתחילים מהמחיר הבסיסי; אם המשקל מעל 5 ק"ג מוסיפים 3 ₪ לכל קילוגרם נוסף, כלומר ; אם התוכן שביר: ₪.
דוגמאות: מכתב רשום וגדול במחיר בסיסי 20 ₪: ₪. חבילה לא שבירה במשקל 8 ק"ג ובמחיר בסיסי 30 ₪: ₪. חבילה שבירה במשקל 4 ק"ג ובמחיר בסיסי 30 ₪: ₪.
// במחלקה MailItem
public abstract double getRealPrice();
// במחלקה Letter
public double getRealPrice()
{
double price = getBasePrice();
if (this.registered)
price += 10; // תוספת לדואר רשום
if (this.size == 'S')
price -= 2; // הנחה למכתב קטן
else if (this.size == 'L')
price += 3; // תוספת למכתב גדול
return price;
}
// במחלקה Package
public double getRealPrice()
{
double price = getBasePrice();
if (this.weight > 5)
price += 3 * (this.weight - 5); // 3 ש"ח לכל ק"ג מעל 5
if (this.fragile)
price += 15; // תוספת לתוכן שביר
return price;
}// במחלקה MailItem
public abstract double GetRealPrice();
// במחלקה Letter
public override double GetRealPrice()
{
double price = GetBasePrice();
if (this.registered)
price += 10; // תוספת לדואר רשום
if (this.size == 'S')
price -= 2; // הנחה למכתב קטן
else if (this.size == 'L')
price += 3; // תוספת למכתב גדול
return price;
}
// במחלקה Package
public override double GetRealPrice()
{
double price = GetBasePrice();
if (this.weight > 5)
price += 3 * (this.weight - 5); // 3 ש"ח לכל ק"ג מעל 5
if (this.fragile)
price += 15; // תוספת לתוכן שביר
return price;
}תשובה: הפעולה מוצהרת מופשטת ב-`MailItem` ונדרסת ב-`Letter` (בסיס, לרשום, לקטן, לגדול) וב-`Package` (בסיס, לכל ק"ג מעל 5, לשביר).
סעיף ג
מעבר על המערך, רק על עצמים מטיפוס Package, חיפוש getRealPrice() המקסימלי והחזרת שם השולח שלו; null אם אין חבילות.
נתון: מערך `args` של משלוחים (מכתבים וחבילות).
מבוקש: שם השולח של החבילה שמחיר המשלוח שלה הגבוה ביותר, או null אם אין חבילות.
הרעיון: חיפוש מקסימום, אבל רק בין האיברים שהם חבילות:
1. עוברים על המערך. בעזרת `instanceof` (ב-C#: `is`) מדלגים על כל מה שאינו `Package`.
2. לכל חבילה מחשבים את המחיר הסופי ב-`getRealPrice()`. בזכות הפולימורפיזם של סעיף ב' מופעלת הגרסה של `Package`, בלי צורך בהמרה.
3. אם זו החבילה הראשונה שנמצאה (`name == null`), או שמחירה גבוה מהמקסימום עד כה – מעדכנים את המקסימום ושומרים את שם השולח (`getSender()`).
4. אם לא נמצאה אף חבילה, `name` נשאר null, וזה מה שמוחזר.
דוגמה: עבור המשלוחים מסעיף ב' – מכתב (33 ₪), חבילה של Avi (39 ₪), חבילה של Ron (45 ₪) – מוחזר "Ron". המכתב אינו נבדק כלל, גם אם מחירו גבוה.
public static String bigSender(MailItem[] args)
{
String name = null; // שם השולח של החבילה היקרה ביותר
double max = 0; // המחיר הגבוה ביותר עד כה
for (int i = 0; i < args.length; i++)
{
if (args[i] instanceof Package)
{
double price = args[i].getRealPrice();
if (name == null || price > max)
{
max = price;
name = args[i].getSender();
}
}
}
return name;
}public static string BigSender(MailItem[] args)
{
string name = null; // שם השולח של החבילה היקרה ביותר
double max = 0; // המחיר הגבוה ביותר עד כה
for (int i = 0; i < args.Length; i++)
{
if (args[i] is Package)
{
double price = args[i].GetRealPrice();
if (name == null || price > max)
{
max = price;
name = args[i].GetSender();
}
}
}
return name;
}תשובה: מעבר על המערך, סינון חבילות ב-`instanceof` (ב-C#: `is`) וחיפוש המחיר הסופי המקסימלי; מוחזר שם השולח שלה, או null אם אין חבילות.
שאלה 5 · מעקב אחרי פעולות על שרשראות
נתונה הפעולה what הבאה, מה מבצעת הפעולה?
public static int what(Node<Integer> ch){
int c = 0;
while(ch != null)
{
c++;
ch = ch.getNext();
}
return c;
}public static int What(Node<int> ch){
int c = 0;
while(ch != null)
{
c++;
ch = ch.GetNext();
}
return c;
}
נתונה הפעולה why המשתמשת בפעולה what, מה תחזיר הפעולה why(ch1, ch2) עבור שתי שרשרות החוליות הבאות: יש להראות מעקב אחרי ביצוע הפעולה why.
אין צורך במעקב אחרי what.
public static boolean why(Node<Integer> ch1, Node<Integer> ch2)
{
int len1 = what(ch1);
int len2 = what(ch2);
for(int i = 0; i < len1-len2; i++)
{
ch1 = ch1.getNext();
}
while(ch1!=null)
{
if(ch1.getValue() != ch2.getValue())
return false;
ch1 = ch1.getNext();
ch2 = ch2.getNext();
}
return true;
}public static bool Why(Node<int> ch1, Node<int> ch2) {
int len1 = What(ch1);
int len2 = What(ch2);
for(int i = 0; i < len1-len2; i++)
{
ch1 = ch1.GetNext();
}
while(ch1!=null)
{
if(ch1.GetValue() != ch2.GetValue())
return false;
ch1 = ch1.GetNext();
ch2 = ch2.GetNext();
}
return true;
}תנו דוגמה של שרשרת ch3 באורך של ארבע חוליות, באופן שבו זימון הפעולה why(ch1, ch3) יחזיר ערך שונה מזה שהוחזר בסעיף ב'.
תנו דוגמה של שרשרת ch4 באורך של ארבע חוליות, באופן שבו זימון הפעולה why(ch4, ch1) יחזיר ערך true. אם אי אפשר ליצור שרשרת כזאת, הסבירו למה.
מה מבצעות הפעולות what(ch) ו- why(ch1,ch2) באופן כללי?
◂ פתרון מלא לשאלה 5
סעיף א
מחזירה את מספר החוליות בשרשרת (אורך השרשרת).
הפעולה מקבלת הפניה לחוליה הראשונה של שרשרת.
1. המונה `c` מתחיל מ-0.
2. בכל סיבוב של הלולאה מוסיפים 1 ל-`c` ומתקדמים לחוליה הבאה.
3. הלולאה נעצרת כש-`ch` הופך ל-null, כלומר אחרי שעברנו על כל החוליות. לכן `c` שווה למספר החוליות.
למשל, עבור השרשרת ch1 של סעיף ב' יוחזר 7, ועבור ch2 יוחזר 4. עבור שרשרת ריקה (null) יוחזר 0.
תשובה: הפעולה מחזירה את מספר החוליות בשרשרת (אורך השרשרת).
סעיף ב
false (אחרי דילוג על 3 חוליות: , , ).
נתון: ch1: , ch2: .
מבוקש: הערך ש-`why(ch1, ch2)` מחזירה, עם מעקב.
1. `len1 = what(ch1) = 7`, `len2 = what(ch2) = 4`.
2. לולאת ה-for רצה כל עוד , כלומר 3 פעמים, ובכל פעם ch1 מתקדם חוליה אחת:
אחרי הלולאה ch1 מצביע על החוליה הרביעית (ערך 5), ונשארו בו בדיוק 4 חוליות – כמו ב-ch2.
3. לולאת ה-while משווה את הערכים בזוגות ומתקדמת בשתי השרשרות יחד:
(הערה: ב-Java הערכים הם עצמי `Integer`, והאופרטור `!=` משווה בין הפניות. עבור מספרים קטנים, בין ל-, Java משתמשת בעצמים שמורים, ולכן ההשוואה כאן מתנהגת כהשוואת ערכים. ב-C# הטיפוס הוא `int`, וההשוואה היא השוואת ערכים.)
תשובה: הפעולה מחזירה false: אחרי דילוג על 3 החוליות הראשונות של ch1, הערכים 5, 7 שווים, אבל 2 שונה מ-1.
סעיף ג
ch3: – מוחזר true.
מבוקש: שרשרת ch3 בת 4 חוליות שעבורה `why(ch1, ch3)` תחזיר true (הערך ההפוך מסעיף ב').
1. כמו בסעיף ב': , ולכן ch1 מדלג על 3 חוליות ומגיע לחוליה שערכה 5.
2. ההשוואה היא בין 4 החוליות האחרונות של ch1, כלומר , לבין 4 החוליות של ch3 לפי הסדר.
3. כדי שכל ההשוואות יעברו ויוחזר true, ch3 צריכה להיות בדיוק .
מעקב: , , , , ch1 מגיע ל-null, והפעולה מחזירה true.
תשובה: ch3: ; עבורה `why(ch1, ch3)` מחזירה true.
סעיף ד
ch4: – מוחזר true.
מבוקש: שרשרת ch4 בת 4 חוליות שעבורה `why(ch4, ch1)` תחזיר true, או הסבר למה אין כזו.
1. בזימון הזה הפרמטר הראשון הוא ch4, ולכן ו-.
2. תנאי לולאת ה-for הוא . כבר ב- התנאי שקר, ולכן אין דילוג בכלל.
3. לולאת ה-while רצה כל עוד הפרמטר הראשון (ch4) אינו null, כלומר 4 סיבובים. בהם משווים את 4 החוליות של ch4 עם 4 החוליות הראשונות של ch1: . הפרמטר השני ארוך יותר, ולכן הוא לא יגיע ל-null באמצע.
4. לכן, אם ch4 היא , כל ההשוואות שוות והפעולה מחזירה true.
תשובה: אפשר: ch4: (ארבעת הערכים הראשונים של ch1); עבורה `why(ch4, ch1)` מחזירה true.
סעיף ה
what – אורך השרשרת; why – true אם ch1 מסתיימת בדיוק בערכי ch2 (ch2 זהה לסוף של ch1); כש-ch1 קצרה מ-ch2 – true אם ch1 זהה להתחלה של ch2.
1. what(ch) – מחזירה את מספר החוליות בשרשרת (אורכה).
2. why(ch1, ch2) – כשהשרשרת ch1 ארוכה מ-ch2 או שווה לה באורכה, הפעולה מדלגת על החוליות הראשונות של ch1 ומשווה את מה שנשאר ל-ch2. לכן היא מחזירה true אם ורק אם ch2 זהה לסוף של ch1: החוליות האחרונות של ch1 שוות ל-ch2, ערך מול ערך ובאותו הסדר. בסעיף ב' זה לא מתקיים, ובסעיף ג' כן.
3. כש-ch1 קצרה מ-ch2 (כמו בסעיף ד'), אין דילוג. הפעולה משווה את כל ch1 לתחילת ch2, ולכן מחזירה true אם ורק אם ch1 זהה להתחלה של ch2.
תשובה: `what` מחזירה את אורך השרשרת; `why` בודקת אם ch2 היא "סיפא" של ch1, כלומר אם ch1 מסתיימת בדיוק בערכי ch2 (כש-ch1 קצרה יותר – אם ch1 היא התחלה של ch2).
שאלה 6 · הכפלת איברי תור והכפלת התור כולו

כתבו פעולה void one(Queue<Integer> q, int k) (ב-C#: void One(Queue<int> q, int k)) המקבלת תור של מספרים שלמים q ומספר שלם וחיובי k. הפעולה "תכפיל" את התור באופן הבא:
אם לפני זימון הפעולה התור q היה כך:
אחרי זימון הפעולה one(q, 2) התור q יהיה כך:
אחרי זימון הפעולה one(q, 3) התור q יהיה כך:
(ראש התור משמאל; שלושת התורים מוצגים באיור לסעיף א'.)

כתבו פעולה void two(Queue<Integer> q, int k) (ב-C#: void Two(Queue<int> q, int k)) המקבלת תור של מספרים שלמים q ומספר שלם וחיובי k. הפעולה "תכפיל" את תור בצורה הבאה:
אם לפני זימון הפעולה התור q היה:
אז אחרי ביצוע זימון הפעולה two(q, 2) התור q יהיה:
אז אחרי ביצוע זימון הפעולה two(q, 3) התור q יהיה:
(ראש התור משמאל; שלושת התורים מוצגים באיור לסעיף ב'.)
מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
מעבירים את התור לתור עזר ומחזירים כל איבר פעמים ברצף.
נתון: תור `q` ומספר שלם וחיובי `k`.
מבוקש: שכל איבר בתור יופיע פעמים ברצף, במקומו, וסדר האיברים יישמר.
הרעיון: אי אפשר להכניס איברים לתור תוך כדי מעבר עליו, כי אז נעבור גם על האיברים החדשים. לכן קודם מעבירים את כל התור לתור עזר, ואז בונים את `q` מחדש:
1. מעבירים את כל האיברים מ-`q` לתור עזר `temp`. עכשיו `q` ריק, ו-`temp` מכיל את האיברים באותו סדר.
2. מוציאים מ-`temp` איבר `x` אחד בכל פעם, ומכניסים אותו ל-`q` פעמים (לולאה פנימית). כך כל איבר מופיע פעמים ברצף, והסדר בין האיברים נשמר כי שני התורים FIFO.
בדיקה עם הדוגמה: התור (מהראש). עבור : מ-8 נכנסים , מ-10 נכנסים וכן הלאה, ומתקבל . עבור מתקבל , כמו באיור.
public static void one(Queue<Integer> q, int k)
{
Queue<Integer> temp = new Queue<Integer>();
while (!q.isEmpty()) // העברת כל התור לתור עזר
temp.insert(q.remove());
while (!temp.isEmpty())
{
int x = temp.remove();
for (int i = 0; i < k; i++) // x נכנס k פעמים ברצף
q.insert(x);
}
}public static void One(Queue<int> q, int k)
{
Queue<int> temp = new Queue<int>();
while (!q.IsEmpty()) // העברת כל התור לתור עזר
temp.Insert(q.Remove());
while (!temp.IsEmpty())
{
int x = temp.Remove();
for (int i = 0; i < k; i++) // x נכנס k פעמים ברצף
q.Insert(x);
}
}תשובה: מעבירים את התור לתור עזר, ומחזירים כל איבר פעמים ברצף; בדוגמה, עבור , מתקבל .
סעיף ב
מעבירים את התור לתור עזר (וסופרים ), ואז פעמים מעבירים את האיברים ל-q ובחזרה לסוף העזר.
נתון: תור `q` ומספר שלם וחיובי `k`.
מבוקש: שהתור כולו יופיע פעמים ברצף: התור המקורי, אחריו עוד עותק שלו, וכן הלאה.
הרעיון: שומרים עותק של התור בתור עזר, ו"מסובבים" אותו פעמים. בכל סיבוב מוציאים מהעזר כל איבר, מכניסים אותו ל-`q` וגם מחזירים אותו לסוף העזר, כך שהעזר חוזר למצבו ומוכן לסיבוב הבא:
1. מעבירים את כל האיברים מ-`q` ל-`temp` וסופרים אותם – . צריך את כדי לדעת מתי מסתיים סיבוב.
2. חוזרים פעמים: פעמים מוציאים איבר `x` מ-`temp`, מכניסים אותו ל-`q`, ומחזירים אותו לסוף `temp`.
3. אחרי סיבובים התור `q` מכיל עותקים רצופים של התור המקורי.
בדיקה עם הדוגמה: התור , ו-. עבור מתקבל . עבור מתקבל , כמו באיור.
public static void two(Queue<Integer> q, int k)
{
Queue<Integer> temp = new Queue<Integer>();
int n = 0; // מספר האיברים בתור
while (!q.isEmpty())
{
temp.insert(q.remove());
n++;
}
for (int r = 0; r < k; r++) // k עותקים של התור
{
for (int i = 0; i < n; i++)
{
int x = temp.remove();
q.insert(x);
temp.insert(x); // האיבר חוזר לסוף העזר לסיבוב הבא
}
}
}public static void Two(Queue<int> q, int k)
{
Queue<int> temp = new Queue<int>();
int n = 0; // מספר האיברים בתור
while (!q.IsEmpty())
{
temp.Insert(q.Remove());
n++;
}
for (int r = 0; r < k; r++) // k עותקים של התור
{
for (int i = 0; i < n; i++)
{
int x = temp.Remove();
q.Insert(x);
temp.Insert(x); // האיבר חוזר לסוף העזר לסיבוב הבא
}
}
}תשובה: מעבירים את התור לתור עזר וסופרים , ואז פעמים מעבירים את האיברים ל-`q` ובחזרה לסוף העזר; בדוגמה, עבור , מתקבל .
סעיף ג
שתיהן .
נסמן ב- את מספר האיברים בתור לפני הזימון.
1. ההעברה לתור העזר: פעולות של .
2. לכל אחד מ- האיברים מבצעים הכנסות – פעולות.
3. סך הכול , כלומר . זה גם גודל התור שמתקבל: לא ייתכן פחות, כי צריך להכניס איברים.
1. ההעברה והספירה: פעולות.
2. סיבובים, ובכל אחד איברים, וכל איבר מטופל ב- (הוצאה ושתי הכנסות) – פעולות.
3. סך הכול , כלומר .
תשובה: לשתי הפעולות סיבוכיות , כאשר הוא מספר האיברים בתור ו- מספר ההכפלות.
שאלה 7 · רשימת אבני דומינו מסודרת היטב
נתונה מחלקה המתארת אבן דומינו (Domino):
public class Domino
{
private int left; // ערך מספרי צד שמאלי בין 0 ל-6 (כולל)
private int right; // ערך מספרי צד ימני בין 0 ל-6 (כולל)
public Domino(int left, int right)
{
this.left = left;
this.right = right;
}
}public class Domino
{
private int left; // ערך מספרי צד שמאלי בין 0 ל-6 (כולל)
private int right; // ערך מספרי צד ימני בין 0 ל-6 (כולל)
public Domino(int left, int right)
{
this.left = left;
this.right = right;
}
}במחלקה הוגדרו פעולות set/get (ב-C#: Set/Get)
כתבו במחלקה Domino את הפעולה rotate() (ב-C#: Rotate()). הפעולה מסובבת את האבן הנוכחית
כלומר: מחליפה בין הערכים left ו- right.
נתונה המחלקה Deck המתארת רשימת אבני דומינו:
public class Deck
{
private Node<Domino> head;
public Deck()
{
this.head = null;
}
}public class Deck
{
private Node<Domino> head;
public Deck()
{
this.head = null;
}
}רשימת אבני דומינו נקראת "מסודרת היטב" אם ערך של מספרי צד ימני של כל אבן (פרט לאבן האחרונה ברשימה) זהה לערך של מספרי צד שמאלי של האבן הבאה.
לדוגמה: הרשימה הבאה מוגדרת "מסודרת היטב" (באיור לשאלה: האבנים , , , ).
רשימה ריקה או רשימה שיש בה רק אבן אחת, היא רשימה "מסודרת היטב".

כתבו במחלקה Deck פעולה הבודקת שרשימה היא "מסודרת היטב". אם כן – הפעולה תחזיר ערך true, ולא – תחזיר ערך false.
כתבו במחלקה Deck פעולה המקבלת אבן דומינו ובודקת אם אפשר להוסיף אותה לרשימה "מסודרת היטב" כך שהיא תישאר להיות "מסודרת היטב". אם כן – הפעולה תוסיף את האבן ותחזיר ערך true, ולא – תחזיר ערך false.
לדוגמה:
אפשר להוסיף לרשימה שבדוגמה בסעיף א' את האבנים הבאות , , .
אי אפשר להוסיף את האבנים הבאות: , , .
◂ פתרון מלא לשאלה 7
סעיף א
החלפת left ו-right בעזרת משתנה זמני.
מבוקש: פעולה שמחליפה בין הערך השמאלי לערך הימני של האבן הנוכחית (`this`).
החלפה בין שני משתנים דורשת משתנה עזר. בלי משתנה עזר, ההשמה הראשונה הייתה מוחקת את אחד הערכים:
1. שומרים את `left` במשתנה זמני `temp`.
2. מציבים ב-`left` את הערך של `right`.
3. מציבים ב-`right` את הערך השמור ב-`temp`.
למשל, האבן הופכת ל-.
public void rotate()
{
int temp = this.left;
this.left = this.right;
this.right = temp;
}public void Rotate()
{
int temp = this.left;
this.left = this.right;
this.right = temp;
}תשובה: החלפת `left` ו-`right` בעזרת משתנה זמני.
סעיף ב
מעבר על זוגות חוליות סמוכות: אם הערך הימני של אבן שונה מהערך השמאלי של הבאה – false, אחרת true.
מבוקש: פעולה במחלקה `Deck` שבודקת שלכל אבן ברשימה, חוץ מהאחרונה, הערך הימני שווה לערך השמאלי של האבן שאחריה.
הרעיון: עוברים על הרשימה בזוגות של חוליות סמוכות: `p` ו-`p.getNext()`.
1. מתחילים מ-`p = head`.
2. כל עוד ל-`p` יש חוליה הבאה, משווים את `p.getValue().getRight()` עם `p.getNext().getValue().getLeft()`. אם הם שונים – הרשימה אינה מסודרת, ומחזירים false.
3. אם כל הזוגות תקינים – מחזירים true.
רשימה ריקה (`head == null`) או רשימה של אבן אחת אינן נכנסות ללולאה כלל, ולכן מוחזר true, כנדרש בהגדרה.
בדיקה עם הדוגמה: האבנים : , , , ולכן מוחזר true.
public boolean isWellOrdered()
{
Node<Domino> p = this.head;
while (p != null && p.hasNext())
{
if (p.getValue().getRight() != p.getNext().getValue().getLeft())
return false;
p = p.getNext();
}
return true;
}public bool IsWellOrdered()
{
Node<Domino> p = this.head;
while (p != null && p.HasNext())
{
if (p.GetValue().GetRight() != p.GetNext().GetValue().GetLeft())
return false;
p = p.GetNext();
}
return true;
}תשובה: מעבר על זוגות סמוכים: אם בזוג כלשהו הערך הימני של אבן שונה מהערך השמאלי של האבן הבאה – false, אחרת true (גם לרשימה ריקה או לאבן אחת).
סעיף ג
הוספה בסוף (צד = ערך ימני של האחרונה) או בתחילה (צד = ערך שמאלי של הראשונה), עם סיבוב לפי הצורך; אבן כפולה גם באמצע, בין אבנים שהערך המשותף שלהן ; אחרת false.
נתון: רשימה "מסודרת היטב" ואבן `d`.
מבוקש: להוסיף את `d` כך שהרשימה תישאר "מסודרת היטב" ולהחזיר true, או להחזיר false אם אי אפשר.
איפה אפשר להוסיף אבן? נסמן ב-`start` את הערך השמאלי של האבן הראשונה, וב-`end` את הערך הימני של האבן האחרונה. מותר לסובב את האבן (בעזרת `rotate` מסעיף א'). יש שלוש אפשרויות:
1. בסוף הרשימה: אם אחד מצדי האבן שווה ל-`end`. מסובבים אותה, אם צריך, כך שהצד הזה יהיה בשמאל, ומחברים אותה אחרי האבן האחרונה.
2. בתחילת הרשימה: אם אחד מצדי האבן שווה ל-`start`. מסובבים אותה, אם צריך, כך שהצד הזה יהיה בימין, והיא הופכת לראש הרשימה.
3. באמצע הרשימה: בין שתי אבנים סמוכות, במקום שבו הערך המשותף הוא , אפשר להכניס רק אבן ששני צדיה שווים ל-, כלומר אבן כפולה . לכן עבור אבן כפולה מחפשים חוליה שהערך הימני שלה הוא ושיש אחריה חוליה, ומכניסים אחריה.
4. אם אף אפשרות לא מתאימה – מחזירים false והרשימה לא משתנה.
5. ברשימה ריקה כל אבן מתאימה: היא הופכת לחוליה היחידה.
בדיקה עם הדוגמה (הרשימה , ולכן , ):
התוצאות זהות לדוגמה שבשאלה.
public boolean add(Domino d)
{
if (this.head == null) // רשימה ריקה
{
this.head = new Node<Domino>(d);
return true;
}
Node<Domino> last = this.head; // מציאת החוליה האחרונה
while (last.hasNext())
last = last.getNext();
int end = last.getValue().getRight(); // הערך בקצה הימני של הרשימה
int start = this.head.getValue().getLeft(); // הערך בקצה השמאלי של הרשימה
if (d.getRight() == end && d.getLeft() != end)
d.rotate(); // הצד המתאים יפנה שמאלה
if (d.getLeft() == end) // 1. הוספה בסוף
{
last.setNext(new Node<Domino>(d));
return true;
}
if (d.getLeft() == start && d.getRight() != start)
d.rotate(); // הצד המתאים יפנה ימינה
if (d.getRight() == start) // 2. הוספה בתחילת הרשימה
{
this.head = new Node<Domino>(d, this.head);
return true;
}
if (d.getLeft() == d.getRight()) // 3. אבן כפולה - הוספה באמצע
{
Node<Domino> p = this.head;
while (p.hasNext())
{
if (p.getValue().getRight() == d.getLeft())
{
p.setNext(new Node<Domino>(d, p.getNext()));
return true;
}
p = p.getNext();
}
}
return false;
}public bool Add(Domino d)
{
if (this.head == null) // רשימה ריקה
{
this.head = new Node<Domino>(d);
return true;
}
Node<Domino> last = this.head; // מציאת החוליה האחרונה
while (last.HasNext())
last = last.GetNext();
int end = last.GetValue().GetRight(); // הערך בקצה הימני של הרשימה
int start = this.head.GetValue().GetLeft(); // הערך בקצה השמאלי של הרשימה
if (d.GetRight() == end && d.GetLeft() != end)
d.Rotate(); // הצד המתאים יפנה שמאלה
if (d.GetLeft() == end) // 1. הוספה בסוף
{
last.SetNext(new Node<Domino>(d));
return true;
}
if (d.GetLeft() == start && d.GetRight() != start)
d.Rotate(); // הצד המתאים יפנה ימינה
if (d.GetRight() == start) // 2. הוספה בתחילת הרשימה
{
this.head = new Node<Domino>(d, this.head);
return true;
}
if (d.GetLeft() == d.GetRight()) // 3. אבן כפולה - הוספה באמצע
{
Node<Domino> p = this.head;
while (p.HasNext())
{
if (p.GetValue().GetRight() == d.GetLeft())
{
p.SetNext(new Node<Domino>(d, p.GetNext()));
return true;
}
p = p.GetNext();
}
}
return false;
}(הסיבוב מתבצע רק כשהוא מוביל מיד להוספה, ולכן אבן שלא נוספה נשארת כפי שהייתה.)
תשובה: מנסים לחבר את האבן בסוף (צד ששווה לערך הימני של האבן האחרונה), אחר כך בתחילה (צד ששווה לערך השמאלי של הראשונה), עם סיבוב לפי הצורך; אבן כפולה אפשר להכניס גם באמצע, בין שתי אבנים שהערך המשותף שלהן . אם אף אפשרות לא מתאימה – false.
שאלה 8 · עץ בינרי מסודר: זוגיות ועלייה
הגדרה: עץ "מסודר" הוא עץ בינארי של מספרים שלמים העונה על הכללים הבאים:
•לכל צומת פרט לעלים יש ערך זוגי.
•הערכים של כל העלים הם מספרים אי-זוגיים.
•הערך של צומת הבן גדול מהערך של צומת האב.
ציירו עץ "מסודר" הכולל לפחות שישה צמתים.
כתבו פעולה המקבלת הפניה לשורש של עץ בינרי של מספרים שלמים. הפעולה תבדוק אם העץ הוא "עץ מסודר". אם כן – הפעולה תחזיר ערך true,
ולא – הפעולה תחזיר ערך false.
◂ פתרון מלא לשאלה 8
סעיף א
למשל: שורש 2, בניו 4 ו-6; בני 4: 5 ו-7; בני 6: 9 ו-11.
הדרישות: כל צומת שאינו עלה – ערך זוגי; כל עלה – ערך אי-זוגי; כל בן גדול מאביו. לכן הערכים גדלים לאורך כל מסלול מהשורש כלפי מטה, ובכל מסלול רק העלה האחרון אי-זוגי.
בנייה: בוחרים שורש זוגי קטן – 2. לו שני בנים זוגיים גדולים ממנו, 4 ו-6, וכל אחד מהם הוא צומת פנימי. לבנים של 4 בוחרים ערכים אי-זוגיים גדולים מ-4 – 5 ו-7, ולבנים של 6 ערכים אי-זוגיים גדולים מ-6 – 9 ו-11. אלה העלים. סך הכול 7 צמתים.
בדיקה: הצמתים הפנימיים 2, 4, 6 זוגיים; העלים 5, 7, 9, 11 אי-זוגיים; בכל שורה בטבלה שני הבנים גדולים מהאב. לכן העץ "מסודר".
תשובה: למשל העץ: שורש 2 עם הבנים 4 ו-6; לצומת 4 הבנים 5 ו-7, ולצומת 6 הבנים 9 ו-11 (7 צמתים).
סעיף ב
רקורסיה: עלה – אי-זוגי; צומת פנימי – זוגי, כל בן גדול ממנו, ותתי-העצים מסודרים; עץ ריק – true.
נתון: הפניה לשורש של עץ בינרי של מספרים שלמים.
מבוקש: true אם העץ "מסודר", אחרת false.
הרעיון – רקורסיה: עץ הוא "מסודר" אם השורש מקיים את הכללים מול הבנים הישירים שלו, ושני תתי-העצים "מסודרים" גם הם. כך נבדק כל צומת מול אביו:
1. עץ ריק (`t == null`): אין בו צומת שמפר כלל, ולכן מחזירים true. המקרה הזה מטפל גם בצומת שיש לו רק בן אחד.
2. עלה (אין בנים): הכלל היחיד שחל עליו הוא שהערך אי-זוגי, ולכן מחזירים `v % 2 != 0`.
3. צומת פנימי:
•אם הערך אי-זוגי – false (לצומת שאינו עלה חייב להיות ערך זוגי).
•אם יש בן שמאלי וערכו אינו גדול מ-`v` – false. כך גם לבן הימני.
•אחרת – מחזירים את התוצאה של בדיקה רקורסיבית לשני תתי-העצים: `isOrderedTree(left) && isOrderedTree(right)`.
בדיקה עם העץ מסעיף א': בשורש 2 – זוגי, והבנים 4 ו-6 גדולים ממנו. 4 – זוגי, והבנים 5 ו-7 גדולים ממנו; 5 ו-7 עלים אי-זוגיים. כך גם 6 עם 9 ו-11. מוחזר true. לעומת זאת, עץ שהוא עלה יחיד שערכו 4 – false (עלה זוגי). עץ שבו לשורש 4 יש בן 3 – false (הבן קטן מהאב).
public static boolean isOrderedTree(BinNode<Integer> t)
{
if (t == null)
return true;
int v = t.getValue();
if (!t.hasLeft() && !t.hasRight()) // עלה: חייב להיות אי-זוגי
return v % 2 != 0;
if (v % 2 != 0) // צומת פנימי: חייב להיות זוגי
return false;
if (t.hasLeft() && t.getLeft().getValue() <= v)
return false; // בן שמאלי לא גדול מהאב
if (t.hasRight() && t.getRight().getValue() <= v)
return false; // בן ימני לא גדול מהאב
return isOrderedTree(t.getLeft()) && isOrderedTree(t.getRight());
}public static bool IsOrderedTree(BinNode<int> t)
{
if (t == null)
return true;
int v = t.GetValue();
if (!t.HasLeft() && !t.HasRight()) // עלה: חייב להיות אי-זוגי
return v % 2 != 0;
if (v % 2 != 0) // צומת פנימי: חייב להיות זוגי
return false;
if (t.HasLeft() && t.GetLeft().GetValue() <= v)
return false; // בן שמאלי לא גדול מהאב
if (t.HasRight() && t.GetRight().GetValue() <= v)
return false; // בן ימני לא גדול מהאב
return IsOrderedTree(t.GetLeft()) && IsOrderedTree(t.GetRight());
}(הפעולה עוברת על כל צומת פעם אחת, ולכן סיבוכיותה , כאשר מספר הצמתים.)
תשובה: בדיקה רקורסיבית: עלה – true אם ורק אם ערכו אי-זוגי; צומת פנימי – זוגי, כל בן קיים גדול ממנו, ושני תתי-העצים "מסודרים"; עץ ריק – true.
שאלה 9 · מחסנית פירמידה: בנייה ובדיקה
מחסנית "פירמידה n" היא מחסנית של מספרים שלמים וחיוביים שהמספר הראשון (מספר שנימצא בראש המחסנית) הוא 1 וכל מספר נוסף מופיע בו ברצף, מספר פעמים השווה לערכו, עד N. כלומר, 1 יופיע פעם אחת, לאחריו 2 יופיע שתי פעמיים, מספר 3 מופיע שלוש פעמים וכו'.
לדוגמה: המחסנית "פירמידה 4" (מהראש):

כתבו פעולה המקבלת מספר שלם וחיובי n ומחזירה מחסנית "פירמידה n".
כתבו פעולה המקבלת מחסנית של מספרים שלמים. הפעולה תבדוק אם המחסנית היא "פירמידה n". אם כן – הפעולה תחזיר ערך true,
ולא – הפעולה תחזיר ערך false.
מהן סיבוכיות הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
עבור דוחפים את בדיוק פעמים (1 נדחף אחרון ונמצא בראש).
נתון: מספר שלם וחיובי .
מבוקש: מחסנית שבראשה 1, אחריו 2 פעמיים, 3 שלוש פעמים, וכן הלאה, ובתחתית מופיע פעמים.
הרעיון: במחסנית האיבר שנדחף אחרון נמצא בראש. לכן דוחפים קודם את מה שצריך להיות בתחתית: מתחילים מ- ויורדים עד 1.
1. לולאה חיצונית: רץ מ- עד 1.
2. לולאה פנימית: דוחפים את למחסנית פעמים.
3. האחרון שנדחף הוא 1 (פעם אחת), ולכן הוא בראש המחסנית.
בדיקה עם הדוגמה: עבור דוחפים , אחר כך , ולבסוף . מהראש מתקבל – "פירמידה 4", כמו באיור.
public static Stack<Integer> buildPyramid(int n)
{
Stack<Integer> st = new Stack<Integer>();
for (int i = n; i >= 1; i--) // מהתחתית (n) עד הראש (1)
for (int j = 0; j < i; j++) // i נדחף i פעמים
st.push(i);
return st;
}public static Stack<int> BuildPyramid(int n)
{
Stack<int> st = new Stack<int>();
for (int i = n; i >= 1; i--) // מהתחתית (n) עד הראש (1)
for (int j = 0; j < i; j++) // i נדחף i פעמים
st.Push(i);
return st;
}תשובה: דוחפים למחסנית ריקה, עבור , את בדיוק פעמים; 1 נדחף אחרון ולכן נמצא בראש.
סעיף ב
מעבר מהראש עם expected ו-left: כל איבר שווה ל-expected, ובסוף (קבוצה אחרונה שלמה); מחסנית ריקה – false.
נתון: מחסנית של מספרים שלמים.
מבוקש: true אם היא "פירמידה n" עבור חיובי כלשהו, אחרת false.
הרעיון: קוראים את המחסנית מהראש ומשווים אותה לסדרה הצפויה . משתמשים בשני משתנים:
•`expected` – הערך שאמור להופיע עכשיו (מתחיל ב-1);
•`left` – כמה פעמים הוא עוד צריך להופיע (מתחיל ב-1).
1. מוציאים איבר `x` ודוחפים אותו למחסנית עזר, כדי לשחזר את המחסנית בסוף.
2. אם `x` שונה מ-`expected` – המחסנית אינה פירמידה (`ok = false`), ומפסיקים.
3. אחרת מקטינים את `left`. אם הגיע ל-0, הקבוצה של `expected` הושלמה: עוברים לערך הבא (`expected++`), שצריך להופיע `expected` פעמים (`left = expected`).
4. בסוף, המחסנית היא פירמידה רק אם כל ההשוואות הצליחו וגם הקבוצה האחרונה הושלמה. קבוצה שהושלמה פותחת קבוצה חדשה שעוד לא התחילה, ולכן התנאי הוא `left == expected`. אם `left < expected`, הקבוצה האחרונה קטועה (למשל ).
5. מחסנית ריקה אינה "פירמידה n" עבור חיובי, ולכן מחזירים עבורה false.
6. מחזירים את האיברים ממחסנית העזר למחסנית המקורית.
public static boolean isPyramid(Stack<Integer> st)
{
if (st.isEmpty())
return false;
Stack<Integer> temp = new Stack<Integer>();
boolean ok = true;
int expected = 1; // הערך שצריך להופיע עכשיו
int left = 1; // כמה פעמים הוא עוד צריך להופיע
while (!st.isEmpty() && ok)
{
int x = st.pop();
temp.push(x);
if (x != expected)
ok = false;
else
{
left--;
if (left == 0) // הקבוצה של expected הושלמה
{
expected++;
left = expected;
}
}
}
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return ok && left == expected; // וגם הקבוצה האחרונה שלמה
}public static bool IsPyramid(Stack<int> st)
{
if (st.IsEmpty())
return false;
Stack<int> temp = new Stack<int>();
bool ok = true;
int expected = 1; // הערך שצריך להופיע עכשיו
int left = 1; // כמה פעמים הוא עוד צריך להופיע
while (!st.IsEmpty() && ok)
{
int x = st.Pop();
temp.Push(x);
if (x != expected)
ok = false;
else
{
left--;
if (left == 0) // הקבוצה של expected הושלמה
{
expected++;
left = expected;
}
}
}
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return ok && left == expected; // וגם הקבוצה האחרונה שלמה
}תשובה: מעבר אחד מהראש עם "ערך צפוי" ו"מספר הופעות שנותרו": כל איבר חייב להיות הערך הצפוי, ובסוף הקבוצה האחרונה חייבת להיות שלמה (); מחסנית ריקה – false. המחסנית משוחזרת.
סעיף ג
א' – ; ב' – , לינארית במספר האיברים במחסנית.
סעיף א' (buildPyramid): מספר הדחיפות הוא
,
וכל דחיפה היא . לכן הסיבוכיות . אי אפשר פחות, כי המחסנית המוחזרת מכילה איברים.
סעיף ב' (isPyramid): נסמן ב- את מספר האיברים במחסנית שהתקבלה. כל איבר מוצא לכל היותר פעם אחת ומוחזר פעם אחת, ובכל צעד מתבצע מספר קבוע של פעולות. לכן הסיבוכיות – לינארית בגודל המחסנית. אם המחסנית היא אכן "פירמידה n", אז , וזה במונחי .
תשובה: א' – (נדחפים איברים); ב' – , לינארית במספר האיברים במחסנית.
שאלה 10 · ירושה, הכלה ומונים סטטיים: מעקב ופלט
נתונות המחלקות A, B, C הבאות:
public class A
{
private static int countA = 0;
protected int x;
public A()
{
countA++;
this.x = 0;
}
public A(int x)
{
countA++;
this.x = x;
}
public String toString()
{
return "A:"+this.x;
}
public int doIt(int z)
{
return this.x * z;
}
public static int getCount(){ return countA; }
}// end of class A
public class B extends A
{
protected int y;
private static int countB = 0;
public B(int y)
{
this.y = y;
countB++;
}
public B(int x, int y)
{
super(x);
countB++;
this.y = y;
}
public String toString()
{
return "B:"+super.toString()+":"+this.y;
}
public static int getCount(){return countB;}
public int doIt(int z)
{
return super.doIt(z) + this.y;
}
} //end of class B
public class C extends B
{
private A myA;
private static int countC = 0;
public C(int x, int y)
{
super(x, y);
this.myA = new A(x+y);
countC++;
}
public static int getCount(){return countC;}
public String toString()
{
return "C:"+super.toString()+" ["+this.myA+"]";
}
}// end of class Cpublic class A
{
private static int countA = 0;
protected int x;
public A()
{
countA++;
this.x = 0;
}
public A(int x)
{
countA++;
this.x = x;
}
public override string ToString()
{
return "A:"+this.x;
}
public virtual int DoIt(int z)
{
return this.x * z;
}
public static int GetCount(){ return countA; }
}// end of class A
public class B : A
{
protected int y;
private static int countB = 0;
public B(int y)
{
this.y = y;
countB++;
}
public B(int x, int y):base(x)
{
countB++;
this.y = y;
}
public override string ToString()
{
return "B:"+base.ToString ()+":"+this.y;
}
public static new int GetCount(){return countB;}
public override int DoIt(int z)
{
return base.DoIt(z) + this.y;
}
} //end of class B
public class C : B
{
private A myA;
private static int countC = 0;
public C(int x, int y): base(x, y)
{
this.myA = new A(x+y);
countC++;
}
public static new int GetCount(){return countC;}
public override string ToString()
{
return "C:"+base. ToString()+" ["+this.myA+"]";
}
}// end of class Cציירו תרשים UML שמייצג את הקשרים בין המחלקות A, B, C.
יש לסמן ירושה באמצעות חץ ——▶ והכלה באמצעות הסימן ━━━◆
נתון קטע הקוד הבא, בפעולה הראשית במחלקה אחרת:
A[] arr = new A[5];
arr[0] = new A(13);
arr[1] = new B(5, 10);
arr[2] = new C(2, 7);
arr[3] = new C(3, 3);
arr[4] = new B(5);A[] arr = new A[5];
arr[0] = new A(13);
arr[1] = new B(5, 10);
arr[2] = new C(2, 7);
arr[3] = new C(3, 3);
arr[4] = new B(5);עקבו אחרי ביצוע קטע הקוד. יש לצייר את כל העצמים שנוצרו ולציין את ערכי התכונות שלהם.
לקוד של סעיף ב' התווסף הקוד הבא, רשמו מה יהיה הפלט בהתאם:
System.out.println("A objects: " + A.getCount());
System.out.println("B objects: " + B.getCount());
System.out.println("C objects: " + C.getCount());Console.WriteLine("A objects: " + A.GetCount());
Console.WriteLine("B objects: " + B.GetCount());
Console.WriteLine("C objects: " + C.GetCount());לקוד של סעיף ב' התווסף הקוד הבא, רשמו מה יהיה הפלט:
for (int k=0; k <arr.length; k++)
System.out.println(arr[k]);for (int k=0; k <arr.Length; k++)
Console.WriteLine(arr[k]);לקוד של סעיף ב' התווסף הקוד הבא, רשמו מה יהיה הפלט:
for (int k=0; k <arr.length; k++)
if(arr[k] instanceof B)
System.out.println(arr[k].doIt(k+1));for (int k=0; k <arr.Length; k++)
if(arr[k] is B)
Console.WriteLine(arr[k].DoIt(k+1));◂ פתרון מלא לשאלה 10
סעיף א
B יורשת מ-A, C יורשת מ-B (חיצי ירושה); C מכילה A (התכונה myA) – קו הכלה עם מעוין בצד של C.
1. ירושה: `B extends A` (ב-C#: `B : A`) – B יורשת מ-A. `C extends B` (ב-C#: `C : B`) – C יורשת מ-B.
2. הכלה: במחלקה C יש תכונה `private A myA` – עצם מסוג C מכיל עצם מסוג A.
•A: התכונות `countA` (static), `x`; הפעולות `A()`, `A(int x)`, `toString()`, `doIt(int z)`, `getCount()`.
•B: התכונות `y`, `countB` (static); הפעולות `B(int y)`, `B(int x, int y)`, `toString()`, `getCount()`, `doIt(int z)`.
•C: התכונות `myA`, `countC` (static); הפעולות `C(int x, int y)`, `getCount()`, `toString()`.
המלבנים מסודרים בשרשרת אנכית A ← B ← C, והקו של ההכלה עובר מ-C ישירות אל A.
תשובה: C יורשת מ-B ו-B יורשת מ-A (חיצי ירושה אל מחלקת האב); C מכילה עצם מסוג A (התכונה myA) – קו הכלה עם מעוין בצד של C.
סעיף ב
A(13); B(x=5,y=10); C(x=2,y=7,myA=A(9)); C(x=3,y=3,myA=A(6)); B(x=0,y=5); countA=7, countB=4, countC=2.
הדרך: בכל `new` מופעלת שרשרת הפעולות הבונות מלמעלה (A) למטה. כל פעולה בונה של A מגדילה את `countA`, של B את `countB`, ושל C את `countC`. המונים הם `static`, כלומר משותפים לכל העצמים של המחלקה.
1. `arr[0] = new A(13)`: נוצר עצם A עם . .
2. `arr[1] = new B(5, 10)`: `super(5)` (ב-C#: `base(5)`) מפעיל את `A(5)`, ולכן ו-. אחר כך ו-.
3. `arr[2] = new C(2, 7)`: `super(2, 7)` מפעיל את `B(2, 7)`, והוא את `A(2)`. לכן , , , . אחר כך נוצר עצם A נוסף עבור `myA` עם , ו-. לבסוף .
4. `arr[3] = new C(3, 3)`: באותה דרך , , , . נוצר `myA` חדש עם , ו-. .
5. `arr[4] = new B(5)`: לפעולה הבונה `B(int y)` אין קריאה מפורשת ל-`super`, ולכן מופעלת אוטומטית הפעולה הבונה בלי פרמטרים `A()`. לכן ו-. אחר כך ו-.
התכונות הסטטיות בסוף: , , .
תשובה: נוצרו 5 עצמים במערך: A(x=13), B(x=5, y=10), C(x=2, y=7, myA→A(x=9)), C(x=3, y=3, myA→A(x=6)), B(x=0, y=5), ועוד שני עצמי A פנימיים; , , .
סעיף ג
A objects: 7 / B objects: 4 / C objects: 2
כל `getCount` מחזירה את המונה הסטטי של המחלקה שלה, כפי שחושב בסעיף ב':
1. `A.getCount()` – . כל עצם מסוג B ו-C מפעיל גם פעולה בונה של A, ובנוסף נוצרו שני עצמי `myA`: .
2. `B.getCount()` – : arr[1], arr[2], arr[3], arr[4]. עצם C נבנה דרך פעולה בונה של B.
3. `C.getCount()` – : arr[2], arr[3].
A objects: 7
B objects: 4
C objects: 2תשובה: A objects: 7, B objects: 4, C objects: 2.
סעיף ד
A:13 / B:A:5:10 / C:B:A:2:7 [A:9] / C:B:A:3:3 [A:6] / B:A:0:5
הדפסת עצם מפעילה את `toString()` שלו (ב-C#: `ToString()`). זו פעולה נדרסת, ולכן מופעלת הגרסה של הטיפוס האמיתי של העצם, גם כשההפניה במערך מטיפוס A.
A:13
B:A:5:10
C:B:A:2:7 [A:9]
C:B:A:3:3 [A:6]
B:A:0:5תשובה: A:13 / B:A:5:10 / C:B:A:2:7 [A:9] / C:B:A:3:3 [A:6] / B:A:0:5
סעיף ה
20 / 13 / 15 / 5
1. התנאי `arr[k] instanceof B` (ב-C#: `arr[k] is B`) מתקיים לעצמים מסוג B וגם לעצמים מסוג C, כי C יורשת מ-B. לכן מודפס עבור , ו-arr[0] (מסוג A בלבד) מדולג.
2. `doIt` נדרסת ב-B, ולכן לעצמי B ו-C מופעלת הגרסה של B: `super.doIt(z) + y`, כלומר . ב-C אין דריסה נוספת, והיא יורשת את הגרסה של B.
3. הפרמטר הוא .
20
13
15
5תשובה: 20, 13, 15, 5 (כל אחד בשורה נפרדת).
שאלה 11 · מוקד תמיכה טלפונית: תורים ועמדות שירות
החברת Helpl4U נותנת שירותי תמיכה טלפונית. מוקד השירות כולל 15 עמדות תמיכה הממוספרות 0-14.
שירותי התמיכה מתנהלים באופן הבא:
•כל מתקשר משאיר את שמו ואת מספר הטלפון שלו לרכז מערכת.
•הרכז מצרף את פרטי המתקשר לאוסף הממתינים בעמדת התמיכה הכי פחות עמוסה.
•כאשר עמדת התמיכה מסיימת טיפול במתקשר, פרטיו נמחקים מאוסף הממתינים של העמדה.
מערכת לניהול שירות כוללת כמה מחלקות.
המחלקה Caller (מתקשר). למחלקה הוגדרו פעולה בונה ופעולות getName() ו- getPhone() (ב-C#: GetName() ו- GetPhone())
המחלקה Service מייצגת עמדת שירות. לפניכם ממשק חלקי של המחלקה Service:
כתבו את כותרת המחלקה Service ואת התכונות שלה
כתבו את הפעולה callback() (ב-C#: Callback())
ניהול מוקד השירות נעשה בעזרת המחלקה Support. לפניכם ממשק חלקי של המחלקה Support:
כתבו את כותרת המחלקה Support ואת התכונות שלה.
כתבו את הפעולה startSupport() (ב-C#: StartSupport()).
הנהלת החברה החליטה לציין בסוף כל יום עבודה את פקיד/ת השרות שטיפל/ה בהכי הרבה לקוחות. ציינו שינוים הנדרשים במחלקה/מחלקות וכתבו במחלקה Support פעולה theBest() (ב-C#: TheBest()) המחזירה את מספר העמדה של הפקיד הטוב ביותר (אפשר להניח שיש רק פקיד אחד).
◂ פתרון מלא לשאלה 11
סעיף א
class Service: Queue<Caller> callers (תור הממתינים), int numOfCallers (מספר הממתינים).
מה צריך לייצג: עמדת שירות אחת – את אוסף הממתינים בה.
1. הממתינים מטופלים לפי סדר ההגעה: מתקשר חדש מצטרף לסוף (addCaller), והמטופל הבא הוא הראשון (callback). זה בדיוק פרוטוקול FIFO, ולכן האוסף הוא תור `Queue<Caller>`.
2. בתור אין פעולה שמחזירה את מספר האיברים, ו-`getNumOfCallers()` נקראת הרבה (בכל הוספה של מתקשר למוקד, לכל 15 העמדות). לכן שומרים תכונה נוספת `numOfCallers`, שמתעדכנת בכל הוספה והוצאה, וכך הפעולה היא .
3. הפעולה הבונה יוצרת תור ריק ומאפסת את המונה.
public class Service
{
private Queue<Caller> callers; // תור הממתינים בעמדה, לפי סדר ההגעה
private int numOfCallers; // מספר הממתינים בעמדה כרגע
public Service()
{
this.callers = new Queue<Caller>();
this.numOfCallers = 0;
}
public void addCaller(Caller c)
{
this.callers.insert(c);
this.numOfCallers++;
}
public int getNumOfCallers()
{
return this.numOfCallers;
}
...
}public class Service
{
private Queue<Caller> callers; // תור הממתינים בעמדה, לפי סדר ההגעה
private int numOfCallers; // מספר הממתינים בעמדה כרגע
public Service()
{
this.callers = new Queue<Caller>();
this.numOfCallers = 0;
}
public void AddCaller(Caller c)
{
this.callers.Insert(c);
this.numOfCallers++;
}
public int GetNumOfCallers()
{
return this.numOfCallers;
}
...
}תשובה: `public class Service` עם התכונות `Queue<Caller> callers` (תור הממתינים, FIFO) ו-`int numOfCallers` (מספר הממתינים).
סעיף ב
מוציאים את ראש התור, מקטינים את numOfCallers ומחזירים את המתקשר.
מבוקש: להחזיר את המתקשר הראשון בתור ולמחוק אותו מאוסף הממתינים. לפי ההנחה, יש בעמדה ממתינים.
1. `remove()` של התור מוציא את האיבר הראשון ומחזיר אותו. כך המתקשר גם מוחזר וגם נמחק מהאוסף.
2. מקטינים את המונה `numOfCallers` ב-1, כדי ש-`getNumOfCallers()` תמשיך להחזיר ערך נכון.
3. מחזירים את המתקשר.
public Caller callback()
{
Caller c = this.callers.remove(); // הראשון בתור יוצא ונמחק מהאוסף
this.numOfCallers--;
return c;
}public Caller Callback()
{
Caller c = this.callers.Remove(); // הראשון בתור יוצא ונמחק מהאוסף
this.numOfCallers--;
return c;
}תשובה: מוציאים את ראש התור (`remove`), מקטינים את `numOfCallers` ב-1 ומחזירים את המתקשר.
סעיף ג
class Support: Service[] stations – מערך של 15 עמדות.
מה צריך לייצג: את מוקד השירות כולו – 15 עמדות תמיכה הממוספרות 0-14.
1. מספר העמדות קבוע וידוע, והגישה אליהן נעשית לפי מספר העמדה. לכן מתאים מערך `Service[]` בגודל 15: העמדה שמספרה נמצאת ב-`stations[i]`.
2. הפעולה הבונה יוצרת את המערך, ובכל תא יוצרת עצם `Service` חדש (עמדה ריקה). בלי זה התאים היו null.
public class Support
{
private Service[] stations; // 15 עמדות התמיכה, העמדה i נמצאת ב-stations[i]
public Support()
{
this.stations = new Service[15];
for (int i = 0; i < this.stations.length; i++)
this.stations[i] = new Service();
}
...
}public class Support
{
private Service[] stations; // 15 עמדות התמיכה, העמדה i נמצאת ב-stations[i]
public Support()
{
this.stations = new Service[15];
for (int i = 0; i < this.stations.Length; i++)
this.stations[i] = new Service();
}
...
}תשובה: `public class Support` עם התכונה `Service[] stations` – מערך של 15 עמדות (אינדקס = מספר העמדה).
סעיף ד
יוצרים Caller ומוסיפים אותו לעמדה הראשונה עם getNumOfCallers() מינימלי.
נתון: שם ומספר טלפון של מתקשר.
מבוקש: לצרף אותו לסוף התור של העמדה עם הכי מעט ממתינים, ואם יש כמה כאלה – לראשונה מביניהן.
1. יוצרים עצם `Caller` חדש מהשם ומהטלפון.
2. מחפשים את העמדה עם המינימום: מתחילים מ-`min = 0` ועוברים על העמדות 1-14. מחליפים את `min` רק כשמספר הממתינים קטן ממש (`<`) מהמינימום עד כה. כך, במקרה של שוויון, נשארת העמדה בעלת המספר הנמוך יותר – "הראשונה מביניהן".
3. מוסיפים את המתקשר לעמדה שנמצאה בעזרת `addCaller`. הפעולה מכניסה אותו לסוף התור ומעדכנת את המונה.
דוגמה: אם בעמדות 0-4 יש 2 ממתינים ובשאר העמדות 1, המתקשר הבא יגיע לעמדה 5 – הראשונה מבין העמדות עם ממתין אחד.
public void startSupport(String name, String phone)
{
Caller c = new Caller(name, phone);
int min = 0; // העמדה הפחות עמוסה עד כה
for (int i = 1; i < this.stations.length; i++)
if (this.stations[i].getNumOfCallers() < this.stations[min].getNumOfCallers())
min = i;
this.stations[min].addCaller(c);
}public void StartSupport(string name, string phone)
{
Caller c = new Caller(name, phone);
int min = 0; // העמדה הפחות עמוסה עד כה
for (int i = 1; i < this.stations.Length; i++)
if (this.stations[i].GetNumOfCallers() < this.stations[min].GetNumOfCallers())
min = i;
this.stations[min].AddCaller(c);
}תשובה: יוצרים Caller, מוצאים את העמדה עם `getNumOfCallers()` המינימלי (בהשוואה `<`, כדי שבשוויון תיבחר הראשונה) ומוסיפים אליה את המתקשר ב-`addCaller`.
סעיף ה
ב-Service: מונה handled שגדל בכל callback() ופעולה getHandled(); theBest() מחזירה את העמדה עם handled מקסימלי.
הבעיה: אוסף הממתינים בעמדה מכיל רק את מי שעדיין ממתין. מי שטופל נמחק ממנו ב-`callback()`, ולכן מהנתונים הקיימים אי אפשר לדעת כמה לקוחות כל פקיד טיפל בהם. צריך לשמור את המידע הזה.
1. במחלקה Service: מוסיפים תכונה `handled` – מספר הלקוחות שטופלו בעמדה. היא מאותחלת ל-0 בפעולה הבונה (וגם בתחילת כל יום עבודה).
2. בפעולה `callback()`: מתקשר יוצא מאוסף הממתינים כשהעמדה מסיימת לטפל בו, ולכן מוסיפים `this.handled++`.
3. במחלקה Service: מוסיפים פעולה `getHandled()` שמחזירה את המונה.
4. במחלקה Support: כותבים את `theBest()` – חיפוש מקסימום של `getHandled()` על 15 העמדות. מוחזר מספר העמדה (האינדקס), כי בכל עמדה עובד פקיד אחד. לפי השאלה אפשר להניח שהמקסימום יחיד.
// במחלקה Service
private int handled; // מספר הלקוחות שטופלו בעמדה (באתחול: 0)
public Caller callback()
{
Caller c = this.callers.remove();
this.numOfCallers--;
this.handled++; // עוד לקוח טופל בעמדה
return c;
}
public int getHandled()
{
return this.handled;
}
// במחלקה Support
public int theBest()
{
int best = 0; // העמדה עם הכי הרבה לקוחות עד כה
for (int i = 1; i < this.stations.length; i++)
if (this.stations[i].getHandled() > this.stations[best].getHandled())
best = i;
return best;
}// במחלקה Service
private int handled; // מספר הלקוחות שטופלו בעמדה (באתחול: 0)
public Caller Callback()
{
Caller c = this.callers.Remove();
this.numOfCallers--;
this.handled++; // עוד לקוח טופל בעמדה
return c;
}
public int GetHandled()
{
return this.handled;
}
// במחלקה Support
public int TheBest()
{
int best = 0; // העמדה עם הכי הרבה לקוחות עד כה
for (int i = 1; i < this.stations.Length; i++)
if (this.stations[i].GetHandled() > this.stations[best].GetHandled())
best = i;
return best;
}תשובה: מוסיפים ל-Service מונה `handled` (מאותחל ל-0), שגדל ב-1 בכל `callback()`, ופעולה `getHandled()`; `theBest()` ב-Support מחזירה את מספר העמדה שבה `getHandled()` מקסימלי.
שאלה 12 · מעקב אחרי פעולות רקורסיביות על שרשרת
נתונה השרשרת הבאה:

עקבו אחרי זימון הפעולה הרקורסיבית one(chain) הבאה וכתבו איך תיראה השרשרת אחרי ביצוע הפעולה ? כמו כן, כתבו מה מבצעת הפעולה one באופן כללי?
public static void one(Node<Integer> n){
if(n.hasNext())
{
n.setValue(n.getNext().getValue());
one(n.getNext());
}
else
{
n.setValue(0);
}
}public static void One(Node<int> n){
if(n.HasNext())
{
n.SetValue(n.GetNext().GetValue());
One(n.GetNext());
}
else
{
n.SetValue(0);
}
}נתונות הפעולה הרקורסיבית two הבאה, עקבו אחרי זימון הפעולה two(chain,10) ורשמו איך תיראה השרשרת אחרי ביצוע הפעולה? רשמו כמו כן מה מבצעת הפעולה באופן כללי?
public static void two(Node<Integer> n, int num){
if(n.hasNext())
{
two(n.getNext(), num);
}
else
{
n.setValue(num);
}
}public static void Two(Node<int> n, int num){
if(n.HasNext())
{
Two(n.GetNext(), num);
}
else
{
n.SetValue(num);
}
}נתונה הפעולה three הבאה, מה יהיה תוכן השרשרת chain אחרי זימון הפעולה three(chain)? כתבו מה מבצעת הפעולה באופן כללי?
public static void three(Node<Integer>n){
int x = n.getValue();
one(n);
two(n,x);
}public static void Three(Node<int>n){
int x = n.GetValue();
One(n);
Two(n,x);
}◂ פתרון מלא לשאלה 12
סעיף א
; מזיזה את הערכים מקום אחד לכיוון ההתחלה ומציבה 0 באחרונה.
נתון: השרשרת chain: .
מה עושה כל זימון: אם לחוליה יש חוליה הבאה – מעתיקים אליה את ערך הבאה, ואז ממשיכים רקורסיבית מהבאה. בחוליה האחרונה מציבים 0. ההעתקה בכל חוליה מתבצעת לפני הקריאה הרקורסיבית, כשהחוליה הבאה עדיין מכילה את הערך המקורי שלה. לכן כל חוליה מקבלת את הערך המקורי של הבאה.
מעקב (חוליה מספר – לפי המיקום בשרשרת, מ-1):
אחר כך הזימונים חוזרים בסדר הפוך בלי לבצע דבר נוסף.
השרשרת אחרי הביצוע: .
באופן כללי: הפעולה מזיזה את כל הערכים בשרשרת מקום אחד שמאלה (לכיוון ההתחלה). הערך הראשון נמחק, ובחוליה האחרונה מוצב 0. מספר החוליות לא משתנה.
תשובה: ; `one` מזיזה את הערכים מקום אחד לכיוון ראש השרשרת (הערך הראשון אובד) ומציבה 0 בחוליה האחרונה.
סעיף ב
; מציבה את num בחוליה האחרונה.
נתון: השרשרת chain: , ו-. (המעקב נעשה על השרשרת הנתונה בשאלה, כפי שהיא באיור.)
מה עושה כל זימון: אם לחוליה יש חוליה הבאה – הפעולה רק ממשיכה רקורסיבית אליה, בלי לשנות דבר. רק בחוליה האחרונה (תנאי העצירה) מוצב הערך `num`.
השרשרת אחרי הביצוע: .
(אם מפעילים את two(chain,10) על השרשרת שהתקבלה בסעיף א', מתקבל .)
באופן כללי: הפעולה מגיעה בעזרת רקורסיה לחוליה האחרונה בשרשרת ומציבה בה את הערך num. שאר החוליות לא משתנות.
תשובה: ; `two` מציבה את num בחוליה האחרונה של השרשרת.
סעיף ג
; הזזה מעגלית של הערכים – הראשון עובר לסוף.
נתון: השרשרת chain: .
1. `int x = n.getValue();` – שומרים את הערך של החוליה הראשונה: .
2. `one(n);` – לפי סעיף א', כל הערכים זזים מקום אחד לכיוון ההתחלה, ובחוליה האחרונה מוצב 0: .
3. `two(n, x);` – לפי סעיף ב', בחוליה האחרונה מוצב במקום ה-0: .
השרשרת אחרי הביצוע: .
באופן כללי: הפעולה מבצעת הזזה מעגלית של ערכי השרשרת מקום אחד שמאלה: כל ערך עובר לחוליה שלפניו, והערך הראשון עובר לחוליה האחרונה. הערך הראשון נשמר ב-`x` לפני ש-`one` מוחקת אותו, ו-`two` מחזירה אותו בסוף.
תשובה: ; `three` מסובבת את ערכי השרשרת מעגלית מקום אחד – הערך הראשון עובר לסוף.