מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2022 מועד א'
הנדסת תוכנה · סמל 97105 · 11 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2022 מועד א', כל 11 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 15)
בכל מבחן 11 שאלות.
שאלות 1-4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 15 נקודות.
שאלות 5-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה 15 נקודות.
שאלות 9-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה 12 נקודות.
נקודה אחת תינתן על הערכה.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · שרשרת הפרשים בשרשרת חוליות
"שרשרת ההפרשים" של שרשרת מטיפוס שלם היא שרשרת חוליות אשר כל אחד מאיבריה הוא ההפרש בערך מוחלט בין כל זוג איברים סמוכים מהשרשרת המקורית.
עבור השרשרת הבאה (5, 20, 9, 6, 5, 8, 2)
שרשרת ההפרשים תהיה (15, 11, 3, 1, 3, 6)
|20-5|=15, |9-20|=11, |6-9|=3, |5-6|=1, |8-5|=3, |2-8|=6


כתבו פעולה חיצונית differenceList (ב-C#: DifferenceList) המקבלת הפניה לחוליה ראשונה של שרשרת חוליות ומחזירה הפניה לחוליה הראשונה של "שרשרת ההפרשים".
כתבו פעולה חיצונית בשם theSurvives (ב-C#: TheSurvives) המקבלת הפניה לחוליה ראשונה של שרשרת חוליות.
על הפעולה לחשב לכל שרשרת הפרשים את שרשרת ההפרשים שלה עד שמתקבלת רשימה עם איבר אחד. איבר זה הוא ה"שורד". על הפעולה להדפיס את כל השרשראות המתקבלות ולהחזיר את ערכו של האיבר ה"שורד".
מומלץ להשתמש בפעולה שכתבתם בסעיף א'.
5 , 20 , 9 , 6 , 5 , 8 , 2
15 , 11 , 3 , 1 , 3 , 6
4 , 8 , 2 , 2 , 3
4 ,6 ,0 ,1
2 , 6 , 1
4 , 5
1הפעולה תחזיר 1
◂ פתרון מלא לשאלה 1
סעיף א
בונים שרשרת חדשה: לכל זוג חוליות סמוכות p ו-p.getNext() מוסיפים לסוף השרשרת החדשה חוליה עם |p.getNext().getValue() - p.getValue()|; מחזירים את החוליה הראשונה שלה (null אם בשרשרת המקורית פחות משתי חוליות).
הרעיון: עוברים על השרשרת עם מצביע p. בכל צעד p ו-`p.getNext()` הם זוג איברים סמוכים, ולכן ההפרש ביניהם הוא האיבר הבא בשרשרת ההפרשים. בשרשרת של k חוליות יש k-1 זוגות סמוכים, ולכן לשרשרת ההפרשים יהיו k-1 חוליות.
1. מחזיקים שתי הפניות לשרשרת החדשה: first (החוליה הראשונה – אותה נחזיר) ו-last (החוליה האחרונה – אליה נחבר את החוליה הבאה, כדי לשמור על סדר האיברים).
2. הלולאה רצה כל עוד ל-p יש חוליה עוקבת (`p.getNext() != null`), כי רק אז יש זוג.
3. מחשבים את ההפרש בערך מוחלט עם `Math.abs`, יוצרים חוליה חדשה ומחברים אותה: אם השרשרת החדשה עדיין ריקה – היא החוליה הראשונה, אחרת מחברים אותה אחרי last.
4. מקדמים את p. השרשרת המקורית אינה משתנה.
5. אם בשרשרת המקורית פחות משתי חוליות – הלולאה לא מתבצעת ומוחזר null (שרשרת הפרשים ריקה).
public static Node<Integer> differenceList(Node<Integer> lst)
{
Node<Integer> first = null; // החוליה הראשונה בשרשרת החדשה
Node<Integer> last = null; // החוליה האחרונה בשרשרת החדשה
Node<Integer> p = lst;
while (p != null && p.getNext() != null)
{
int diff = Math.abs(p.getNext().getValue() - p.getValue());
Node<Integer> n = new Node<Integer>(diff);
if (first == null)
first = n;
else
last.setNext(n);
last = n;
p = p.getNext();
}
return first;
}public static Node<int> DifferenceList(Node<int> lst)
{
Node<int> first = null; // החוליה הראשונה בשרשרת החדשה
Node<int> last = null; // החוליה האחרונה בשרשרת החדשה
Node<int> p = lst;
while (p != null && p.GetNext() != null)
{
int diff = Math.Abs(p.GetNext().GetValue() - p.GetValue());
Node<int> n = new Node<int>(diff);
if (first == null)
first = n;
else
last.SetNext(n);
last = n;
p = p.GetNext();
}
return first;
}בדיקה על הדוגמה: עבור 5, 20, 9, 6, 5, 8, 2 מתקבלים הזוגות (5,20), (20,9), (9,6), (6,5), (5,8), (8,2) וההפרשים 15, 11, 3, 1, 3, 6 – כמו בשאלה.
יעילות: מעבר אחד על השרשרת – .
תשובה: הפעולה differenceList שלמעלה.
סעיף ב
מדפיסים את השרשרת, ובלולאה – כל עוד יש בה יותר מחוליה אחת – מחליפים אותה בשרשרת ההפרשים שלה (סעיף א) ומדפיסים; מחזירים את ערך החוליה היחידה שנשארה (בדוגמה: 1).
הרעיון: כל הפעלה של differenceList מקצרת את השרשרת בחוליה אחת. לכן אם מפעילים אותה שוב ושוב, אחרי n-1 פעמים נשארת שרשרת עם חוליה אחת בדיוק – ה"שורד".
1. פעולת עזר printList מדפיסה שרשרת אחת בשורה, האיברים מופרדים בפסיקים (כמו בדוגמה).
2. מדפיסים את השרשרת המקורית (גם היא מופיעה בפלט לדוגמה).
3. כל עוד לחוליה הראשונה יש חוליה עוקבת (כלומר בשרשרת יותר מאיבר אחד): מחשבים את שרשרת ההפרשים, מעבירים את lst להצביע עליה ומדפיסים אותה.
4. כשהלולאה נגמרת בשרשרת חוליה אחת – מחזירים את ערכה.
5. הנחה: השרשרת שמתקבלת אינה ריקה (אם יש בה חוליה אחת בלבד – היא מודפסת והיא עצמה ה"שורד").
public static void printList(Node<Integer> lst)
{
Node<Integer> p = lst;
while (p != null)
{
System.out.print(p.getValue());
if (p.getNext() != null)
System.out.print(" , ");
p = p.getNext();
}
System.out.println();
}
public static int theSurvives(Node<Integer> lst)
{
printList(lst); // השרשרת המקורית
while (lst.getNext() != null) // יש יותר מאיבר אחד
{
lst = differenceList(lst);
printList(lst);
}
return lst.getValue(); // ה"שורד"
}public static void PrintList(Node<int> lst)
{
Node<int> p = lst;
while (p != null)
{
Console.Write(p.GetValue());
if (p.GetNext() != null)
Console.Write(" , ");
p = p.GetNext();
}
Console.WriteLine();
}
public static int TheSurvives(Node<int> lst)
{
PrintList(lst); // השרשרת המקורית
while (lst.GetNext() != null) // יש יותר מאיבר אחד
{
lst = DifferenceList(lst);
PrintList(lst);
}
return lst.GetValue(); // ה"שורד"
}נשארה חוליה אחת שערכה 1, והפעולה מחזירה 1.
יעילות: בשרשרת של n איברים יש n-1 סבבים, ובסבב ה-k עוברים על n-k+1 חוליות, ולכן סך הכול .
תשובה: הפעולה theSurvives שלמעלה; בדוגמה היא מדפיסה 7 שורות ומחזירה 1.
שאלה 2 · בדיקת סכומים במחסנית
כתבו פעולה חיצונית המקבלת מחסנית שאיבריה מטיפוס שלם. הפעולה תחזיר true אם ערכו של כל איבר במחסנית (פרט לאיבר הנמצא בראש המחסנית) גדול מסכום ערכם של כל האיברים שנמצאים לפניו במחסנית, אם לא הפעולה תחזיר false. אפשר להשתמש במבני נתונים נוספים.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
מוציאים את האיברים מהראש כלפי מטה ושומרים במחסנית עזר; צוברים את סכום האיברים שהוצאו, וכל איבר (חוץ מהראשון שבראש) חייב להיות גדול מהסכום הזה – אחרת false. בסוף מחזירים את כל האיברים למחסנית המקורית.
הרעיון: "האיברים שלפניו" הם האיברים שנמצאים מעליו במחסנית, כלומר אלה שיוצאים לפניו. לכן מוציאים את האיברים אחד-אחד מהראש, ומחזיקים משתנה sum – סכום כל האיברים שכבר הוצאו. כשמוציאים איבר x, sum הוא בדיוק סכום האיברים שלפניו, ומספיק לבדוק ש-`x > sum`.
1. את האיבר שבראש המחסנית לא בודקים (אין לפניו איברים): מוציאים אותו, שומרים במחסנית עזר temp ומאתחלים בו את sum.
2. לכל איבר הבא x: מעבירים אותו ל-temp; אם `x <= sum` – התנאי לא מתקיים ומפסיקים (ok = false); אחרת מוסיפים את x ל-sum וממשיכים.
3. בסוף מחזירים את כל האיברים מ-temp למחסנית s. מאחר ש-temp הפוכה, ההעברה חזרה משחזרת את הסדר המקורי – הפעולה לא משנה את המחסנית שקיבלה.
4. מחסנית ריקה או עם איבר אחד – אין איבר שצריך לבדוק, ומוחזר true.
public static boolean isBigger(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
boolean ok = true;
int sum = 0; // סכום האיברים שהוצאו עד עכשיו (אלה שלפני האיבר)
if (!s.isEmpty())
{
int x = s.pop(); // האיבר שבראש המחסנית - לא נבדק
temp.push(x);
sum = x;
}
while (!s.isEmpty() && ok)
{
int x = s.pop();
temp.push(x);
if (x <= sum)
ok = false; // האיבר אינו גדול מסכום האיברים שלפניו
sum = sum + x;
}
while (!temp.isEmpty()) // החזרת המחסנית למצבה המקורי
s.push(temp.pop());
return ok;
}public static bool IsBigger(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
bool ok = true;
int sum = 0; // סכום האיברים שהוצאו עד עכשיו (אלה שלפני האיבר)
if (!s.IsEmpty())
{
int x = s.Pop(); // האיבר שבראש המחסנית - לא נבדק
temp.Push(x);
sum = x;
}
while (!s.IsEmpty() && ok)
{
int x = s.Pop();
temp.Push(x);
if (x <= sum)
ok = false; // האיבר אינו גדול מסכום האיברים שלפניו
sum = sum + x;
}
while (!temp.IsEmpty()) // החזרת המחסנית למצבה המקורי
s.Push(temp.Pop());
return ok;
}דוגמה: מחסנית שבראשה 1 ואחריו 2, 4, 8, 20: , , , – מוחזר true. מחסנית שבראשה 1 ואחריו 2, 3, 8: אינו מתקיים – מוחזר false.
תשובה: הפעולה isBigger שלמעלה.
סעיף ב
– כל אחד מ-n האיברים מוצא מהמחסנית פעם אחת ומוחזר אליה פעם אחת, וכל פעולה של מחסנית היא .
נסמן ב-n את מספר האיברים במחסנית.
1. בלולאה הראשונה כל איבר מוצא מ-s ונדחף ל-temp לכל היותר פעם אחת; בכל איבר מבצעים מספר קבוע של פעולות (pop, push, השוואה, חיבור), וכל פעולה של מחסנית מתבצעת ב-.
2. בלולאה השנייה כל איבר שהוצא מוחזר פעם אחת – שוב לכל היותר n פעמים .
3. סך הכול לכל היותר צעדים בסדר גודל קבוע, כלומר סיבוכיות לינארית.
תשובה: , כאשר n מספר האיברים במחסנית.
שאלה 3 · מעקב אחר ירושה ופולימורפיזם
נתונות ארבע המחלקות הבאות:
public class A {
protected int x;
public A() {
x = 0;
}
public void method(int num) {
x += num;
}
public String toString() {
return "" + x;
}
}// end of class A
public class B extends A{
private int y;
public B()
{
super();
y = 1;
}
public void method(int num) {
x -= num;
y += num;
}
public String toString() {
return "" + x + "." + y;
}
}// end of class B
public class C extends A{
private int y;
public C()
{
super();
y = 10;
}
public void method(int num) {
x += num;
y += num;
}
public String toString() {
return "" + x + "/"+ y;
}
} // end of class C
public class Test
{
public static void main (String [] args)
{
A [] array = new A[4];
array[0] = new C();
array[1] = new B();
array[2] = new A();
array[3] = new B();
for (int i = 0; i < array.length; i ++)
{
System.out.println ("array[" + i + "] = " + array[i]);
array[i].method(i+2);
System.out.println ("array[" + i + "] = " + array[i]);
}
}
}public class A {
protected int x;
public A() {
x = 0;
}
public virtual void Method(int num) {
x += num;
}
public override string ToString() {
return "" + x;
}
}// end of class A
public class B : A{
private int y;
public B()
{
y = 1;
}
public override void Method(int num) {
x -= num;
y += num;
}
public override string ToString () {
return "" + x + "." + y;
}
}// end of class B
public class C : A{
private int y;
public C()
{
y = 10;
}
public override void Method(int num) {
x += num;
y += num;
}
public override string ToString() {
return "" + x + "/"+ y;
}
} // end of class C
public class Test
{
public static void Main (string [] args)
{
A [] array = new A[4];
array[0] = new C();
array[1] = new B();
array[2] = new A();
array[3] = new B();
for (int i = 0; i < array.length; i ++)
{
Console.WriteLine("array[" + i + "] = " + array[i]);
array[i].Method(i+2);
Console.WriteLine("array[" + i + "] = " + array[i]);
}
}
}עקבו אחרי ביצוע הפעולה הראשית של המחלקה Test וכתבו מה יהיה הפלט של הפעולה.
חובה להציג באיור את כל העצמים שנוצרו ואת התכונות שלהם.
◂ פתרון מלא לשאלה 3
פתרון
array[0] = 0/10, array[0] = 2/12, array[1] = 0.1, array[1] = -3.4, array[2] = 0, array[2] = 4, array[3] = 0.1, array[3] = -5.6 (כל אחד בשורה נפרדת).
הרעיון: המערך array הוא מטיפוס A, אבל כל תא מפנה לעצם מהמחלקה שבה נוצר. בזמן ריצה הפעולות method ו-toString נבחרות לפי הטיפוס האמיתי של העצם (פולימורפיזם – B ו-C דורסות את שתיהן). כשמשרשרים עצם למחרוזת ב-println מופעלת toString שלו.
1. יצירת העצמים. בבנאי של B ושל C מופעל קודם הבנאי של A (`super()`, וב-C# הבנאי של המחלקה הבסיסית מופעל אוטומטית), ולכן לכל עצם x = 0. אחר כך נקבע y.
(באיור: המערך array בן 4 תאים; כל תא מצביע על עצם נפרד עם התכונות שבטבלה. לשני עצמי B יש עותק נפרד של x ושל y.)
2. הלולאה. לכל i: מדפיסים את העצם, מפעילים `method(i+2)`, ומדפיסים שוב. toString של C מחזירה "x/y", של B "x.y", ושל A רק "x". שימו לב: method של B מחסירה את num מ-x (`x -= num`) ומוסיפה אותו ל-y, ולכן x של עצמי B נעשה שלילי.
array[0] = 0/10
array[0] = 2/12
array[1] = 0.1
array[1] = -3.4
array[2] = 0
array[2] = 4
array[3] = 0.1
array[3] = -5.6הערה לגרסת C#: בלולאה מודפס `array.length`, ושם התכונה ב-C# הוא `array.Length` (באות גדולה). בהנחה שהכוונה ל-Length, הפלט זהה (Console.WriteLine מפעילה את ToString הנדרסת).
array[0] = 0/10
array[0] = 2/12
array[1] = 0.1
array[1] = -3.4
array[2] = 0
array[2] = 4
array[3] = 0.1
array[3] = -5.6שאלה 4 · דריסה, העמסה והמרות טיפוסים
נתונות שלוש המחלקות הבאות:
public class A {
protected int num;
public A(int n)
{
num = n;
}
public int getNum()
{
return num;
}
public boolean f(A a)
{
System.out.println("F in A");
return num == a.num * 2;
}
}// end of class A
public class B extends A {
public B(int n)
{
super(n);
}
public boolean f(B b)
{
System.out.println("F in B");
return num == b.num;
}
}// end of class B
public class C extends A {
public C (int n)
{
System.out.println("F in C");
super(n);
}
public boolean f(A a)
{
return a instanceof C && num == a.num;
}
} //end of class Cpublic class A {
protected int num;
public A(int n)
{
num = n;
}
public int GetNum()
{
return num;
}
public virtual bool F(A a)
{
Console.WriteLine("F in A");
return num == a.num * 2;
}
}// end of class A
public class B : A {
public B(int n): base(n)
{
}
public bool F(B b)
{
Console.WriteLine("F in B");
return num == b.num;
}
}// end of class B
public class C : A {
public C (int n): base(n)
{
}
public override bool F(A a)
{
Console.WriteLine("F in C");
return a is C && num == ((C)a).num;
}
} //end of class Cהאם קיימות דריסה (overriding) או העמסה (overloading) של הפעולות? הסבירו את תשובתכם.
נתונה הפעולה ראשית main במחלקה Driver
public class Driver
{
public static void main(String[] args)
{
A y1 = new B(10);
B y2 = new B(10);
A z1 = new C(10);
C z2 = new C(10);
(****)
}
}public class Driver
{
public static void Main(string[] args)
{
A y1 = new B(10);
B y2 = new B(10);
A z1 = new C(10);
C z2 = new C(10);
(****)
}
}בכל אחד מסעיפים הבאים השורה () תוחלף בשורת קוד משורות הקוד 1-6.
כתבו עבור כל אחד מהסעיפים, אם קוד תקין או לא. אם הקוד תקין, יש לציין מה יהיה הפלט, אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (קומפילציה או זמן ריצה).
1. System.out.println(y1.getNum()==((B)z1).getNum());
2. System.out.println(y1.f(y2));
3. System.out.println(y2.f(y1));
4. System.out.println(z1.f(z2));
5. System.out.println(z1.f(y1));
6. System.out.println(z2.f((C)y2));1. Console.WriteLine(y1.GetNum()==((B)z1).GetNum());
2. Console.WriteLine(y1.F(y2));
3. Console.WriteLine(y2.F(y1));
4. Console.WriteLine(z1.F(z2));
5. Console.WriteLine(z1.F(y1));
6. Console.WriteLine(z2.F((C)y2));◂ פתרון מלא לשאלה 4
סעיף א
כן. ב-B יש העמסה: f(B b) היא פעולה חדשה עם פרמטר מטיפוס אחר מ-f(A a) שירשה מ-A. ב-C יש דריסה: f(A a) של C היא באותה חתימה בדיוק כמו f(A a) של A ומחליפה אותה.
ההגדרות: דריסה (overriding) – מחלקה יורשת מגדירה מחדש פעולה של מחלקת הבסיס באותה חתימה בדיוק (שם, מספר וטיפוסי פרמטרים), והפעולה שמופעלת נקבעת בזמן ריצה לפי הטיפוס האמיתי של העצם. העמסה (overloading) – באותה מחלקה (כולל מה שירשה) יש כמה פעולות באותו שם עם רשימת פרמטרים שונה, והבחירה ביניהן נעשית בזמן הידור לפי טיפוסי הארגומנטים.
1. מחלקה B: היא יורשת מ-A את `f(A a)` ומגדירה `f(B b)`. הפרמטר מטיפוס אחר, ולכן זו העמסה ולא דריסה: ב-B יש שתי פעולות f. (ב-C# בהתאם: F(B b) אינה מסומנת override – פעולה חדשה.)
2. מחלקה C: מגדירה `f(A a)` – אותה חתימה כמו ב-A, ולכן זו דריסה (ב-C#: `override` של הפעולה `virtual`). עצם מטיפוס C שיופעל עליו f(A) יריץ את הגרסה של C.
3. הבנאים B(int) ו-C(int) אינם דריסה – בנאים אינם עוברים בירושה; הם רק מפעילים את בנאי A.
תשובה: קיימות שתיהן: העמסה של f במחלקה B (f(B b) לצד f(A a) שירשה), ודריסה של f(A a) במחלקה C.
סעיף ב
Java: 1 – שגיאת זמן ריצה (ClassCastException); 2 – F in A, false; 3 – F in A, false; 4 – true; 5 – false; 6 – שגיאת קומפילציה. C#: 1 – שגיאת זמן ריצה (InvalidCastException); 2 – F in A, False; 3 – F in A, False; 4 – F in C, True; 5 – F in C, False; 6 – שגיאת קומפילציה.
שני כללים: (1) בזמן הידור בודקים רק לפי הטיפוס המוצהר של המשתנה אילו פעולות קיימות ואיזו גרסה (מתוך העמסות) נבחרת לפי טיפוסי הארגומנטים. (2) בזמן ריצה, אם הגרסה שנבחרה נדרסה במחלקה של העצם האמיתי – מופעלת הגרסה הדורסת.
הבדל בין הגרסאות: ב-Java ההדפסה "F in C" נמצאת בבנאי של C, ו-f של C אינה מדפיסה דבר. ב-C# הבנאי של C ריק, וההדפסה "F in C" נמצאת בפעולה F של C. לכן התשובות לשורות 4 ו-5 שונות בין הגרסאות.
הערה על גרסת Java: בבנאי של C ההוראה `System.out.println("F in C")` כתובה לפני `super(n)`. ב-Java (בגרסאות שנלמדות) הקריאה ל-super חייבת להיות ההוראה הראשונה בבנאי, ולכן כפי שהודפס המחלקה C אינה עוברת הידור. כדי שהשאלה תהיה בעלת משמעות נניח שההדפסה באה מיד אחרי `super(n)`. אז ביצירת z1 ו-z2 (לפני השורה ()) מודפס פעמיים "F in C" – בכל אחד מהסעיפים הפלט מתחיל בשתי השורות האלה, ולהלן נכתוב רק את מה שהשורה עצמה מוסיפה.
העצמים: y1 – מוצהר A, בפועל B (num = 10); y2 – מוצהר B, בפועל B (num = 10); z1 – מוצהר A, בפועל C (num = 10); z2 – מוצהר C, בפועל C (num = 10).
1. `y1.getNum()==((B)z1).getNum()` – ההמרה מ-A ל-B מותרת בהידור (B יורשת מ-A, ייתכן שהעצם הוא B). אבל בזמן ריצה z1 הוא עצם מטיפוס C, ו-C אינה B. שגיאת זמן ריצה: ClassCastException (ב-C#: InvalidCastException). לא מודפס דבר.
2. `y1.f(y2)` – y1 מוצהר A, וב-A יש רק f(A a); y2 (B) מתאים לפרמטר A. בזמן ריצה y1 הוא B, ו-B לא דרסה את f(A) (רק העמיסה f(B)) – מופעלת f של A: מודפס "F in A" ומוחזר , כלומר false. פלט: F in A, false.
3. `y2.f(y1)` – y2 מוצהר B, ויש לו שתי גרסאות: f(A) ו-f(B). הארגומנט y1 מוצהר A, ולכן רק f(A a) מתאימה (אין המרה אוטומטית מ-A ל-B). מופעלת f של A: "F in A" ו- – false. פלט: F in A, false.
4. `z1.f(z2)` – z1 מוצהר A, נבחרת f(A). בזמן ריצה z1 הוא C, ו-C דרסה את f(A) – מופעלת f של C: z2 הוא C וגם – מוחזר true. פלט ב-Java: true. ב-C#: F של C מדפיסה קודם "F in C", ואז True.
5. `z1.f(y1)` – שוב f של C; y1 הוא B ולא C, ולכן התנאי הראשון false (ובגלל `&&` המקוצר השני לא נבדק). פלט ב-Java: false. ב-C#: "F in C" ואז False.
6. `z2.f((C)y2)` – y2 מוצהר B. B ו-C הן מחלקות "אחיות" (שתיהן יורשות מ-A ואף אחת אינה יורשת מהשנייה), ולכן עצם מטיפוס B לעולם אינו יכול להיות C. המהדר פוסל את ההמרה: שגיאת קומפילציה (incompatible types / Cannot convert type B to C).
תשובה: 1 – שגיאת זמן ריצה; 2 – F in A, false; 3 – F in A, false; 4 – Java: true, C#: F in C, True; 5 – Java: false, C#: F in C, False; 6 – שגיאת קומפילציה.
שאלה 5 · פירמידת ליצנים במחסנית
פירמידה של ליצנים מתארת ליצנים העומדים זה על זה.
נתונה המחלקה Clown (ליצן) הבאה:
class Clown
{
private String name; // שם ליצן
private int weight; // משקל ליצן
}class Clown
{
private string name; // שם ליצן
private int weight; // משקל ליצן
}אפשר להניח כי במחלקה הוגדרו בנאי ופעולות get לכל תכונה, אין צורך לממש.
הגדירו מחלקה Pyramid המתארת פירמידה של ליצנים. יש לבחור תכונות של המחלקה ולכתוב בנאי ליצירת פירמידה ריקה.
פירמידה תיקרא פירמידה יציבה אם הליצן שבתחתית הפירמידה הוא הכבד ביותר, מעליו האדם שמשקלו הוא במקום השני וכך הלאה עד שבראש הפירמידה נמצא הליצן בעל המשקל הקל ביותר.
כתבו פעולה פנימית הבודקת אם הפירמידה היא "פירמידה יציבה". כותרת הפעולה:
public boolean isStable()public bool IsStable()כתבו פעולה בוליאנית המקבלת ליצן. על הפעולה להוסיף את הליצן לפירמידה כך שהיא תישאר יציבה.
אם הדבר אפשרי – הפעולה מוסיפה את הליצן ומחזירה true, ואם לא – היא מחזירה false.
כותרת הפעולה:
public boolean addClown(Clown c)public bool AddClown(Clown c)◂ פתרון מלא לשאלה 5
סעיף א
תכונה אחת: מחסנית ליצנים `Stack<Clown> clowns` (ראש המחסנית = הליצן העליון בפירמידה); הבנאי יוצר מחסנית ריקה.
בחירת מבנה הנתונים: בפירמידה מוסיפים ומורידים ליצנים רק מלמעלה – הליצן האחרון שעלה הוא הראשון שירד. זה בדיוק פרוטוקול LIFO של מחסנית, ולכן נשמור את הליצנים במחסנית: ראש המחסנית הוא הליצן שבראש הפירמידה, ובתחתית המחסנית הליצן שבתחתית. מספר הליצנים אינו ידוע מראש – והמחסנית גדלה לפי הצורך.
1. תכונה: `clowns` – מחסנית של עצמי Clown.
2. בנאי: יוצר מחסנית ריקה – פירמידה בלי ליצנים.
public class Pyramid
{
private Stack<Clown> clowns; // ראש המחסנית = הליצן שבראש הפירמידה
public Pyramid()
{
this.clowns = new Stack<Clown>(); // פירמידה ריקה
}
...
}public class Pyramid
{
private Stack<Clown> clowns; // ראש המחסנית = הליצן שבראש הפירמידה
public Pyramid()
{
this.clowns = new Stack<Clown>(); // פירמידה ריקה
}
...
}(בהמשך, הפעולות של סעיפים ב ו-ג נכתבות בתוך המחלקה.)
תשובה: מחלקה Pyramid עם תכונה `Stack<Clown> clowns` ובנאי שיוצר מחסנית ריקה.
סעיף ב
מוציאים את הליצנים מלמעלה למטה למחסנית עזר; אם ליצן כבד מהליצן שמתחתיו (`c.getWeight() > clowns.top().getWeight()`) – הפירמידה אינה יציבה. בסוף מחזירים את הליצנים ומחזירים את התוצאה (פירמידה ריקה – יציבה).
הרעיון: הפירמידה יציבה אם המשקלים יורדים מלמטה למעלה. מספיק לבדוק כל זוג ליצנים סמוכים: הליצן העליון לא כבד מהליצן שמתחתיו. אם זה מתקיים לכל זוג, אז מהתחתית לראש כל ליצן קל או שווה לקודמו – והתחתון הוא הכבד ביותר והעליון הקל ביותר.
1. מוציאים ליצן c מראש המחסנית. אם נשארו ליצנים, הליצן שמתחתיו הוא `clowns.top()`, ומשווים את משקליהם (דרך פעולות get, כי התכונות של Clown פרטיות).
2. אם c כבד יותר מהליצן שמתחתיו – הפירמידה אינה יציבה, ואפשר להפסיק לבדוק.
3. כל ליצן שהוצא נשמר במחסנית עזר temp, ובסוף מחזירים את כולם ל-clowns – מחסנית העזר הפוכה, ולכן הסדר המקורי משוחזר והפירמידה לא משתנה.
4. פירמידה ריקה או עם ליצן אחד – יציבה.
5. ליצנים בעלי משקל שווה הנחנו כמותרים ("לא כבד יותר"); אם רוצים לדרוש משקלים שונים, מחליפים את `>` ב-`>=`.
public boolean isStable()
{
Stack<Clown> temp = new Stack<Clown>();
boolean stable = true;
while (!this.clowns.isEmpty() && stable)
{
Clown c = this.clowns.pop(); // ליצן מלמעלה למטה
if (!this.clowns.isEmpty() &&
c.getWeight() > this.clowns.top().getWeight())
stable = false; // הליצן כבד מהליצן שמתחתיו
temp.push(c);
}
while (!temp.isEmpty()) // החזרת הליצנים למקומם
this.clowns.push(temp.pop());
return stable;
} public bool IsStable()
{
Stack<Clown> temp = new Stack<Clown>();
bool stable = true;
while (!this.clowns.IsEmpty() && stable)
{
Clown c = this.clowns.Pop(); // ליצן מלמעלה למטה
if (!this.clowns.IsEmpty() &&
c.GetWeight() > this.clowns.Top().GetWeight())
stable = false; // הליצן כבד מהליצן שמתחתיו
temp.Push(c);
}
while (!temp.IsEmpty()) // החזרת הליצנים למקומם
this.clowns.Push(temp.Pop());
return stable;
}דוגמה: מלמטה למעלה 90, 70, 50 – כל ליצן קל מזה שמתחתיו: true. מלמטה למעלה 90, 70, 80 – הליצן העליון (80) כבד מ-70 שמתחתיו: false.
יעילות: – כל ליצן מוצא ומוחזר פעם אחת.
תשובה: הפעולה isStable שלמעלה.
סעיף ג
בודקים ש-isStable() מחזירה true; מעלים את הליצן לראש (push) ובודקים שוב – אם יציבה מחזירים true, אחרת מורידים אותו (pop) ומחזירים false. אם הפירמידה לא יציבה מלכתחילה – false בלי להוסיף.
הרעיון: ליצן חדש עולה לראש הפירמידה (push למחסנית). הפירמידה תישאר יציבה רק אם היא הייתה יציבה קודם, וגם הליצן החדש לא כבד מהליצן שבראש. נשתמש בפעולה isStable לשתי הבדיקות:
1. לפני ההוספה: אם הפירמידה אינה יציבה מלכתחילה – לפי ההנחיה לא מוסיפים, ומחזירים false.
2. מוסיפים את הליצן לראש המחסנית.
3. אחרי ההוספה: אם הפירמידה עדיין יציבה – ההוספה הצליחה, מחזירים true.
4. אחרת הליצן החדש כבד מהליצן שמתחתיו: מוציאים אותו (pop) כדי להחזיר את הפירמידה למצבה, ומחזירים false.
public boolean addClown(Clown c)
{
if (!this.isStable()) // פירמידה שאינה יציבה מלכתחילה
return false;
this.clowns.push(c); // הליצן עולה לראש הפירמידה
if (this.isStable())
return true;
this.clowns.pop(); // הפירמידה הפכה ללא יציבה - מורידים אותו
return false;
} public bool AddClown(Clown c)
{
if (!this.IsStable()) // פירמידה שאינה יציבה מלכתחילה
return false;
this.clowns.Push(c); // הליצן עולה לראש הפירמידה
if (this.IsStable())
return true;
this.clowns.Pop(); // הפירמידה הפכה ללא יציבה - מורידים אותו
return false;
}דוגמה: בפירמידה ריקה מוסיפים ליצנים במשקל 90, 70 – שניהם נוספים (true). ליצן במשקל 80 – אחרי ההוספה 80 עומד על 70, הפירמידה לא יציבה, הוא מוצא ומוחזר false. ליצן במשקל 50 – נוסף (true).
תשובה: הפעולה addClown שלמעלה.
שאלה 6 · היררכיית מחלקות וממשקים
נתונה היררכיית המחלקות הבאה הכוללת חמש מחלקות Point, Shape, Circle, Square, Rectangle ושני ממשקים ITurnable ו- IFillable.
(בגרסת C# של התרשים: `void Fill(string color)`, `void Left(int degree)`, `void Right(int degree)`, `protected string color`.)

כתבו עבור כל מחלקה, את כותרת המחלקה ואת הכותרות של כל הפעולות שחייבות להיות במחלקה.
נתון קטע קוד בפעולה הראשית (main):
Shape s = new Square(new Point(50,50),10);
Shape c = new Circle(new Point(50,50),8);
ITurnable t; IFillable f;
(***)Shape s = new Square(new Point(50,50),10);
Shape c = new Circle(new Point(50,50),8);
ITurnable t;
IFillable f;
(***)כתבו כותרת לכל הבנאים הנדרשים להרצה תקינה של קטע הקוד.
בהתייחס לכל אחד מהקטעים הבאים, כתבו מה יקרה בעקבות הוספתו לשיטה main שלעיל, במקום שמסומן בכוכביות *.
אם הקוד אינו תקין יש להסביר ולציין את סוג השגיאה (קומפילציה או זמן ריצה).
(1) f =(IFillable) c;
(2) t = s;
t.fill("Green");
(3) f = c;
f.fill("Red");
(4) ((Circle)s).left (45);
(5) Shape d = c;
d.fill("Yellow");
(6) f = new Rectangle(new Point(10,10),10,20);
f.left(Math.PI);
(7) c = s;
c.left (90);(1) f =(IFillable) c;
(2) t = s;
t.Fill("Green");
(3) f = c;
f.Fill("Red");
(4) ((Circle)s).Left (45);
(5) Shape d = c;
d.Fill("Yellow");
(6) f = new Rectangle(new Point(10,10),10,20);
f.Left(Math.PI);
(7) c = s;
c.Left (90);◂ פתרון מלא לשאלה 6
סעיף א
Point, Shape – בלי פעולות חובה; Circle extends Shape implements IFillable – fill(String); Square extends Shape implements IFillable, ITurnable – fill(String), left(int), right(int); Rectangle extends Square – בלי פעולות חובה (יורשת אותן מ-Square).
קריאת התרשים: חץ רציף עם ראש משולש = ירושה (extends); חץ מקווקו אל ממשק = מימוש (implements); קו עם מעוין מלא בין Shape ל-Point = הרכבה – ל-Shape יש תכונה מטיפוס Point.
1. Point – מחלקה רגילה (התכונות x, y). אינה יורשת ואינה מממשת – אין פעולות שחייבות להיות בה.
2. Shape – מחלקת הבסיס של הצורות, עם התכונות color ו-point. אינה מממשת ממשק – אין פעולות חובה. (אפשר גם להגדיר אותה abstract, כי אין צורה "סתם".)
3. Circle – יורשת מ-Shape ומממשת את IFillable (חץ מקווקו אחד). מחלקה שמממשת ממשק חייבת לממש את כל הפעולות שלו: `fill(String color)`.
4. Square – יורשת מ-Shape ומממשת את IFillable ואת ITurnable (שני חצים מקווקווים). חייבת לממש `fill`, `left` ו-`right`.
5. Rectangle – יורשת מ-Square. היא מקבלת בירושה את המימוש של fill, left, right (ומממשת בעקיפין את שני הממשקים), ולכן אין פעולות שחייבות להופיע בה (אפשר לדרוס אותן אם רוצים).
גם הממשקים עצמם מוגדרים עם כותרות הפעולות שלהם.
interface IFillable
{
void fill(String color);
}
interface ITurnable
{
void left(int degree);
void right(int degree);
}
class Point
{
private int x;
private int y;
}
class Shape
{
protected String color;
protected Point point; // הרכבה: לכל צורה יש נקודה
}
class Circle extends Shape implements IFillable
{
private double radius;
public void fill(String color) { this.color = color; }
}
class Square extends Shape implements IFillable, ITurnable
{
protected double length1;
public void fill(String color) { this.color = color; }
public void left(int degree) { /* סיבוב שמאלה */ }
public void right(int degree) { /* סיבוב ימינה */ }
}
class Rectangle extends Square
{
private double length2;
}interface IFillable
{
void Fill(string color);
}
interface ITurnable
{
void Left(int degree);
void Right(int degree);
}
class Point
{
private int x;
private int y;
}
class Shape
{
protected string color;
protected Point point; // הרכבה: לכל צורה יש נקודה
}
class Circle : Shape, IFillable
{
private double radius;
public void Fill(string color) { this.color = color; }
}
class Square : Shape, IFillable, ITurnable
{
protected double length1;
public void Fill(string color) { this.color = color; }
public void Left(int degree) { /* סיבוב שמאלה */ }
public void Right(int degree) { /* סיבוב ימינה */ }
}
class Rectangle : Square
{
private double length2;
}תשובה: הכותרות שלמעלה; פעולות חובה רק ב-Circle (fill) וב-Square (fill, left, right).
סעיף ב
Point(int x, int y); Shape(Point point); Square(Point point, double length1); Circle(Point point, double radius).
בקטע הקוד נוצרים עצמים בעזרת `new`, ולכל קריאה צריך בנאי מתאים:
1. `new Point(50,50)` – בנאי של Point עם שני שלמים: x ו-y.
2. `new Square(new Point(50,50),10)` – בנאי של Square עם נקודה ואורך צלע. הצלע length1 מטיפוס double; הערך 10 (int) מומר אוטומטית ל-double.
3. `new Circle(new Point(50,50),8)` – בנאי של Circle עם נקודה ורדיוס (double).
4. הבנאים של Square ושל Circle מפעילים את הבנאי של מחלקת הבסיס Shape כדי לאתחל את point; לכן נדרש גם בנאי `Shape(Point point)` (ב-C# הקריאה אליו: `: base(point)`).
public Point(int x, int y)
public Shape(Point point)
public Square(Point point, double length1)
public Circle(Point point, double radius)public Point(int x, int y)
public Shape(Point point)
public Square(Point point, double length1) : base(point)
public Circle(Point point, double radius) : base(point)(בקטע (6) של סעיף ג נוצר גם `new Rectangle(new Point(10,10),10,20)`; לשם כך נדרש הבנאי `Rectangle(Point point, double length1, double length2)` שמפעיל את בנאי Square.)
תשובה: Point(int x, int y), Shape(Point point), Square(Point point, double length1), Circle(Point point, double radius).
סעיף ג
(1) תקין, אין פלט. (2) שגיאת קומפילציה. (3) שגיאת קומפילציה. (4) שגיאת קומפילציה. (5) שגיאת קומפילציה. (6) שגיאת קומפילציה (בשורה של left). (7) שגיאת קומפילציה (בשורה של left).
הכלל: המהדר מתיר השמה והפעלת פעולה לפי הטיפוס המוצהר בלבד. השמה ממחלקה לממשק בלי המרה מפורשת מותרת רק אם הטיפוס המוצהר מממש את הממשק; ופעולה אפשר להפעיל רק אם היא קיימת בטיפוס המוצהר. המרה מפורשת (casting) נבדקת שוב בזמן ריצה מול העצם האמיתי. s מוצהר Shape ובפועל Square; c מוצהר Shape ובפועל Circle.
1. (1) `f = (IFillable) c;` – המרה מפורשת ממחלקה (Shape) לממשק מותרת בהידור, כי ייתכן שעצם Shape הוא ממחלקה שמממשת את IFillable. בזמן ריצה c הוא Circle, שמממש את IFillable – ההמרה מצליחה. תקין, אין פלט.
2. (2) `t = s;` – s מוצהר Shape, ו-Shape אינה מממשת את ITurnable; בלי המרה מפורשת אין השמה. שגיאת קומפילציה. (גם `t.fill` שגויה: בממשק ITurnable אין פעולה fill.)
3. (3) `f = c;` – אותה בעיה: Shape אינה מממשת את IFillable, ולכן אי אפשר להציב את c ב-f בלי המרה. שגיאת קומפילציה.
4. (4) `((Circle)s).left(45);` – לאחר ההמרה הטיפוס הוא Circle, ובמחלקה Circle אין פעולה left (היא מממשת רק את IFillable). שגיאת קומפילציה. (גם אילו הייתה – בזמן ריצה s הוא Square ולא Circle, וההמרה הייתה נכשלת.)
5. (5) `Shape d = c;` תקין, אבל `d.fill("Yellow")` – d מוצהר Shape, וב-Shape אין פעולה fill. שגיאת קומפילציה.
6. (6) `f = new Rectangle(...)` תקין – Rectangle יורשת מ-Square, שמממשת את IFillable. אבל `f.left(Math.PI)` – f מוצהר IFillable, ובממשק זה אין left (וגם Math.PI מטיפוס double, בעוד הפרמטר של left מטיפוס int). שגיאת קומפילציה.
7. (7) `c = s;` תקין (שניהם מוצהרים Shape; כעת c מפנה ל-Square). אבל `c.left(90)` – ב-Shape אין פעולה left. שגיאת קומפילציה.
תשובה: רק קטע (1) תקין; בקטעים (2)–(7) שגיאת קומפילציה.
שאלה 7 · מעקב אחר פעולות רקורסיביות על עץ בינארי
לפניכם שלוש פעולות:
public static void what1(BinNode<Integer> bt)
{
if(bt!=null){
int x=bt.getValue();
if(what2(bt.getLeft(),x) && what2(bt.getRight(),x))
System.out.println(x);
what1(bt.getLeft());
what1(bt.getRight());
}
}
public static boolean what2(BinNode<Integer> bt, int x)
{
if(bt==null)return true;
if(bt.getValue()==x)return false;
return what2(bt.getLeft(), x) && what2(bt.getRight(), x);
}public static void What1(BinNode<int> bt)
{
if(bt!=null){
int x=bt.GetValue();
if(What2(bt.GetLeft(),x) && What2(bt.GetRight(),x))
Console.WriteLine(x);
What1(bt.GetLeft());
What1(bt.GetRight());
}
}
public static bool What2(BinNode<int> bt, int x)
{
if(bt==null)return true;
if(bt.GetValue()==x)return false;
return What2(bt.GetLeft(), x) && What2(bt.GetRight(), x);
}נתון העץ הבינארי הבא:

מה תהיה תוצאת זימון הפעולה what2(bt, 10)? חובה להראות את המעקב!
תנו דוגמה של הפרמטר x, שעבורו זימון הפעולה what2(bt, x) יחזיר תוצאה שונה מזו שהתקבלה בסעיף א'.
מה מבצעת הפעולה what2(BinNode<Integer> bt, int x) באופן כללי?
מה תהיה תוצאת הזימון what1(bt) לעץ הנתון bt? חובה להראות את המעקב!
הערה: אין צורך במעקב אחרי הפעולה what2
מה מבצעת הפעולה what1(bt) באופן כללי?
◂ פתרון מלא לשאלה 7
סעיף א
false – הערך 10 מופיע בעץ (בבן הימני של השורש).
נתאר את העץ: שורש 3; בנו השמאלי 3 (עם בן שמאלי 1 ובן ימני 3, שלו בן ימני 2); בנו הימני 10 (עם בן שמאלי 9, שלו בן שמאלי 7, ובן ימני 7, שלו בן ימני 10).
what2 מחזירה false ברגע שהיא פוגשת צומת שערכו x, ואחרת ממשיכה לשני תתי-העצים. האופרטור `&&` מקוצר: אם תת-העץ השמאלי החזיר false, את הימני לא בודקים.
תת-העץ השמאלי החזיר true, תת-העץ הימני החזיר false, ולכן בשורש: true && false = false.
תשובה: false.
סעיף ב
למשל x = 5 (כל מספר שאינו מופיע בעץ) – what2(bt, 5) מחזירה true.
לפי סעיף א, what2 מחזירה false כשהערך נמצא בעץ. כדי לקבל true צריך ערך שאינו מופיע באף צומת. בעץ מופיעים רק הערכים 1, 2, 3, 7, 9, 10. עבור x = 5 כל ההשוואות נכשלות, כל קריאה מגיעה בסוף ל-null שמחזיר true, ולכן התוצאה true.
תשובה: x = 5 (או כל מספר אחר שאינו 1, 2, 3, 7, 9, 10) – מוחזר true.
סעיף ג
מחזירה true אם הערך x אינו מופיע באף צומת של העץ bt (ובעץ ריק), ו-false אם x מופיע בעץ.
1. עץ ריק (null) – אין בו אף ערך, ולכן מוחזר true.
2. אם בשורש נמצא x – מוחזר false.
3. אחרת מוחזר true רק אם גם בתת-העץ השמאלי וגם בתת-העץ הימני x אינו מופיע.
כלומר הפעולה בודקת שהערך x אינו נמצא בעץ (השלילה של "x נמצא בעץ").
תשובה: what2 מחזירה true אם x לא מופיע בעץ bt, ו-false אם הוא מופיע בו.
סעיף ד
יודפסו (כל מספר בשורה): 1, 3, 2, 9, 7, 7, 10.
what1 עוברת על העץ בסדר תחילי (צומת, תת-עץ שמאלי, תת-עץ ימני). בכל צומת היא מדפיסה את ערכו x אם what2 מחזירה true לשני תתי-העצים שלו – כלומר אם x אינו מופיע באף צאצא של הצומת.
("כן" בעמודה = what2 מחזירה false לתת-העץ הזה; בשורש תת-העץ השמאלי כבר החזיר false, ובגלל `&&` המקוצר את הימני לא בודקים.)
1
3
2
9
7
7
10תשובה: 1, 3, 2, 9, 7, 7, 10 (כל מספר בשורה נפרדת).
סעיף ה
מדפיסה, בסדר תחילי (preorder), את ערכי הצמתים שערכם אינו מופיע באף צומת בתת-העצים שלהם (באף צאצא שלהם).
1. what1 מבקרת בכל צומת של העץ בסדר תחילי: קודם הצומת, אחר כך כל תת-העץ השמאלי ואז כל תת-העץ הימני.
2. בכל צומת שערכו x היא בודקת בעזרת what2 (סעיף ג) ש-x אינו מופיע בתת-העץ השמאלי וגם אינו מופיע בתת-העץ הימני – כלומר אף צאצא של הצומת אינו בעל אותו ערך.
3. רק אז היא מדפיסה את x. בפרט כל עלה מודפס (אין לו צאצאים).
תשובה: what1 מדפיסה בסדר תחילי את ערכי כל הצמתים שערכם אינו חוזר באף אחד מצאצאיהם.
שאלה 8 · תורים ושרשרת של תורים
כתבו פעולה המקבלת תור של מספרים שלמים ומחזירה סכום איברים שנמצאים בתור.
כותרת הפעולה
public static int sumQueue(Queue<Integer> q)public static int SumQueue(Queue<int> q)כתבו פעולה המקבלת תור של מספרים שלמים ומחזירה את הערך של המספר האחרון שנמצא בתור (את הערך הנמצא בסוף התור).
כותרת הפעולה
public static int lastValue(Queue<Integer> q)public static int LastValue(Queue<int> q)שרשרת תורים היא שרשרת חוליות מסוג `Node<Queue<Integer>>` (ב-C#: `Node<Queue<int>>`). כלומר, הערך (value) של כל חוליה הוא הפניה לתור של מספרים שלמים.

כתבו פעולה המקבלת הפניה לחוליה ראשונה של שרשרת תורים.
הפעולה תחזיר תור של מספרים שלמים באופן הבא:
עבור כל תור שנמצא בשרשרת תורים שהערך הנמצא בראשו הוא אי זוגי, יוכנס לתור החדש ערך השווה לסכום האיברים בתור, ואילו עבור כל תור שערך הנמצא בראשו הוא זוגי הפעולה תכניס לתור החדש את הערך הנמצא בסוף התור.
עבור שרשרת התורים הבאה (באיור לסעיף; ראש כל תור משמאל): 1, 4, 2 ; 10, 7, 1, 3 ; 9, 1, 8
7, 3, 18 (7 בראש התור)
•עבור החוליה הראשונה יתקבל סכום של איברים כי הערך בראש התור הוא אי זוגי.
סכום הוא 7 = 1+4+2
•עבור החוליה השנייה יתקבל מספר בסוף התור (3) כי הערך בראש התור הוא זוגי.
•עבור החוליה השלישית יתקבל סכום של איברים כי ערך בראש התור הוא אי זוגי.
סכום הוא 18 = 9+1+8.
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף ג'? הסבירו את תשובתכם!
◂ פתרון מלא לשאלה 8
סעיף א
מוציאים את כל האיברים, צוברים את סכומם ומעבירים אותם לתור עזר; אחר כך מחזירים אותם לתור המקורי באותו סדר ומחזירים את הסכום.
הרעיון: בתור אפשר להגיע לאיבר רק אחרי שהוצאו כל האיברים שלפניו. לכן מוציאים את כל האיברים, מוסיפים כל אחד לסכום, ושומרים אותם בתור עזר. כדי שהפעולה לא תהרוס את התור שקיבלה, בסוף מעבירים את האיברים חזרה – תור העזר שומר על סדר FIFO, ולכן הסדר המקורי נשמר.
1. כל עוד התור אינו ריק: מוציאים איבר x, מוסיפים אותו ל-sum ומכניסים ל-temp.
2. מעבירים את כל האיברים מ-temp חזרה ל-q.
3. מחזירים את sum (תור ריק – 0).
public static int sumQueue(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int sum = 0;
while (!q.isEmpty())
{
int x = q.remove();
sum = sum + x;
temp.insert(x);
}
while (!temp.isEmpty()) // החזרת האיברים לתור המקורי, באותו סדר
q.insert(temp.remove());
return sum;
}public static int SumQueue(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int sum = 0;
while (!q.IsEmpty())
{
int x = q.Remove();
sum = sum + x;
temp.Insert(x);
}
while (!temp.IsEmpty()) // החזרת האיברים לתור המקורי, באותו סדר
q.Insert(temp.Remove());
return sum;
}דוגמה: עבור התור 1, 4, 2 מוחזר , והתור נשאר 1, 4, 2.
תשובה: הפעולה sumQueue שלמעלה.
סעיף ב
מוציאים את כל האיברים לתור עזר תוך שמירת האיבר האחרון שהוצא – הוא האיבר שבסוף התור; מחזירים את האיברים לתור המקורי ומחזירים את הערך.
הרעיון: בממשק התור יש גישה רק לראש (head), לא לסוף. האיבר שבסוף התור הוא האיבר האחרון שיוצא, ולכן מוציאים את כל האיברים, ובכל הוצאה שומרים את הערך ב-last – אחרי הלולאה last מחזיק את האיבר האחרון.
1. כל עוד התור אינו ריק: `last = q.remove()` והאיבר עובר לתור עזר.
2. מחזירים את כל האיברים לתור המקורי, באותו סדר.
3. מחזירים את last. (הנחה: התור אינו ריק; בתור ריק יוחזר 0.)
public static int lastValue(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int last = 0;
while (!q.isEmpty())
{
last = q.remove(); // בסוף הלולאה זה האיבר שהיה בסוף התור
temp.insert(last);
}
while (!temp.isEmpty())
q.insert(temp.remove());
return last;
}public static int LastValue(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int last = 0;
while (!q.IsEmpty())
{
last = q.Remove(); // בסוף הלולאה זה האיבר שהיה בסוף התור
temp.Insert(last);
}
while (!temp.IsEmpty())
q.Insert(temp.Remove());
return last;
}דוגמה: עבור התור 10, 7, 1, 3 (10 בראש) מוחזר 3.
תשובה: הפעולה lastValue שלמעלה.
סעיף ג
עוברים על השרשרת; לכל תור: אם head() אי-זוגי מכניסים לתור התוצאה את sumQueue שלו, אחרת את lastValue שלו; מחזירים את תור התוצאה (בדוגמה: 7, 3, 18).
הרעיון: עוברים על חוליות השרשרת לפי הסדר. הערך של כל חוליה הוא תור; מסתכלים על הראש שלו בעזרת `head()` (בלי להוציא אותו), ולפי הזוגיות שלו מכניסים לתור התוצאה את הסכום (פעולה מסעיף א) או את הערך האחרון (פעולה מסעיף ב). מאחר ששתי הפעולות משחזרות את התור, התורים בשרשרת לא משתנים.
1. יוצרים תור ריק result.
2. לכל חוליה p: `q = p.getValue()`. אם `q.head() % 2 != 0` (אי-זוגי; הבדיקה `!= 0` נכונה גם למספרים שליליים) – `result.insert(sumQueue(q))`; אחרת – `result.insert(lastValue(q))`.
3. מתקדמים לחוליה הבאה; בסוף מחזירים את result. הסדר בתור התוצאה הוא סדר החוליות.
4. הנחה: התורים בשרשרת אינם ריקים (אחרת אין ערך בראש התור).
public static Queue<Integer> newQueue(Node<Queue<Integer>> lst)
{
Queue<Integer> result = new Queue<Integer>();
Node<Queue<Integer>> p = lst;
while (p != null)
{
Queue<Integer> q = p.getValue();
if (q.head() % 2 != 0) // בראש התור מספר אי-זוגי
result.insert(sumQueue(q));
else // בראש התור מספר זוגי
result.insert(lastValue(q));
p = p.getNext();
}
return result;
}public static Queue<int> NewQueue(Node<Queue<int>> lst)
{
Queue<int> result = new Queue<int>();
Node<Queue<int>> p = lst;
while (p != null)
{
Queue<int> q = p.GetValue();
if (q.Head() % 2 != 0) // בראש התור מספר אי-זוגי
result.Insert(SumQueue(q));
else // בראש התור מספר זוגי
result.Insert(LastValue(q));
p = p.GetNext();
}
return result;
}תשובה: הפעולה שלמעלה; בדוגמה מוחזר התור 7, 3, 18.
סעיף ד
, כאשר n מספר החוליות בשרשרת ו-m מספר האיברים בתור הגדול ביותר; ובמדויק , כאשר N סך כל האיברים בכל התורים – כל איבר מוצא ומוכנס פעמיים בלבד.
נסמן: n – מספר החוליות (התורים) בשרשרת; – מספר האיברים בתור ה-i; – סך כל האיברים; m – אורך התור הארוך ביותר.
1. הלולאה הראשית עוברת על n החוליות. בכל חוליה: `getValue`, `head`, בדיקת זוגיות, `insert` לתור התוצאה ו-`getNext` – כולן .
2. בנוסף בכל חוליה נקראת sumQueue או lastValue על תור בגודל . כל אחת מהן מוציאה את האיברים לתור עזר ומחזירה אותם – פעולות של , כלומר .
3. סך הכול: . בחסם עליון פשוט, כל תור לכל היותר m איברים, ולכן .
תשובה: (ליתר דיוק – לינארית בסך כל האיברים בכל התורים).
שאלה 9 · היררכיית דירות וחישוב מחיר
לשם קידום מכירת דירות של חברת "קנה ביתך" פותח פרויקט לניהול שיווק דירות הכולל את המחלקות הבאות:
Appartment – דירה רגילה.
GardenApp – דירת גן.
Penthouse – דירת פנטהאוז.
Luxary – דירת פאר.
לדירה (Appartment) יש התכונות הבאות:
•owner – שם בעל דירה, מטיפוס מחרוזות, String.
•floor – מספר קומה, מטיפוס שלם, int.
•numApp – מספר דירה, מטיפוס שלם, int.
•area – שטח דירה, מטיפוס שלם, int.
לדירה גן (GardenApp) יש התכונות הבאות:
•owner – שם בעל דירה, מטיפוס מחרוזות, String.
•floor – מספר קומה, מטיפוס שלם, int.
•numApp – מספר דירה, מטיפוס שלם, int.
•area – שטח דירה, מטיפוס שלם, int.
•gardenArea – שטח גינה, מטיפוס שלם, int.
לדירת פנטהאוז (Penthouse) יש התכונות הבאות:
•owner – שם בעל דירה, מטיפוס מחרוזות, String.
•floor – מספר קומה, מטיפוס שלם, int.
•numApp – מספר דירה, מטיפוס שלם, int.
•area – שטח דירה, מטיפוס שלם, int.
•numTerr – מספר מרפסות, מטיפוס שלם, int.
•terraceArea – השטח הכולל של המרפסות, מטיפוס שלם, int.
•seaView – נוף לים, כן/לא, מטיפוס boolean.
לדירת מיני-פנטהאוז (Luxary) יש התכונות הבאות:
•owner – שם בעל דירה, מטיפוס מחרוזות, String.
•floor – מספר קומה, מטיפוס שלם, int.
•numApp – מספר דירה, מטיפוס שלם, int.
•area – שטח דירה, מטיפוס שלם, int.
•terraceArea – שטח מרפסת, מטיפוס שלם, int.
(בגרסת C#: string ו-bool.)
סרטטו תרשים UML המתאר את הקשר בין המחלקות:
באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.
לכל אחת מהמחלקות Appartment, GardenApp, Penthouse, Luxary כתבו:
– כותרת המחלקה.
– תכונות.
למחלקה Appartment הוגדרה פעולה הבונה (בנאי, constructor) המייצרת דירה רגילה מוכנה למכירה:
public Appartment(int floor, int numApp, int area)
{
this.owner = "FREE";
this.floor = floor;
this.numApp = numApp;
this.area = area;
}public Appartment(int floor, int numApp, int area)
{
this.owner = "FREE";
this.floor = floor;
this.numApp = numApp;
this.area = area;
}ופעולה הקובעת את שם בעל הדירה אחרי המכירה:
public void setOwner(String name)
{
this.owner = name;
}public void SetOwner(string name)
{
this.owner = name;
}המחיר של כל דירה תלוי בשטח הדירה, בשטח המרפסת (אם יש) ובשטח הגינה (אם יש). לשם כך הוחלט להגדיר שלושה קבועים המציינים מחיר למטר מרובע של דירה, מרפסת וגן, בהתאם:
final int COST_APP = 1000;
final int COST_TERRACE = 300;
final int COST_GARDEN = 50;const int COST_APP = 1000;
const int COST_TERRACE = 300;
const int COST_GARDEN = 50;באיזו מחלקה או באילו מחלקות יש להוסיף את הקבועים הנ"ל? הסבירו את תשובתכם.
כדי לקדם את המכירות של דירות הפנטהאוז הוחלט לתת הנחה של 5% לדירות שאין להן נוף לים.
כתבו פעולה או פעולות לחישוב ולהחזרת מחיר הדירה. יש לציין באיזו מחלקה צריך להוסיף את הפעולה או את הפעולות.
כתבו פעולה חיצונית המקבלת מערך דירות המתאר בניין מסוים וסכום כסף שלקוח רוצה להשקיע.
הפעולה תדפיס פרטי דירות שפנויות למכירה ומחירן אינו עולה על הסכום שאותו הלקוח רוצה להשקיע.
הערה: הניחו שהפעולות get ו-toString מוגדרות בעבור כל תכונה בכל אחת מהמחלקות הפרויקט.
◂ פתרון מלא לשאלה 9
סעיף א
Appartment היא מחלקת הבסיס; GardenApp ו-Luxary יורשות ממנה; Penthouse יורשת מ-Luxary.
העיקרון: תכונה משותפת מגדירים פעם אחת, במחלקה הכללית ביותר שיש לה אותה, ומחלקה שיש לה את כל התכונות של מחלקה אחרת ועוד – יורשת ממנה ("היא סוג של").
1. ארבע התכונות owner, floor, numApp, area משותפות לכל הדירות – הן במחלקת הבסיס Appartment.
2. GardenApp = דירה + gardenArea – יורשת מ-Appartment.
3. Luxary = דירה + terraceArea – יורשת מ-Appartment.
4. Penthouse = כל התכונות של Luxary (כולל terraceArea, שבפנטהאוז הוא השטח הכולל של המרפסות) + numTerr + seaView – לכן יורשת מ-Luxary ולא ישירות מ-Appartment. כך terraceArea וחישוב מחיר המרפסות לא נכתבים פעמיים.
התרשים (החץ מצביע מהמחלקה היורשת אל מחלקת הבסיס; בכל מחלקה רק התכונות שהיא מוסיפה):
Appartment
owner, floor, numApp, area
^ ^
| |
GardenApp Luxary
gardenArea terraceArea
^
|
Penthouse
numTerr, seaViewתשובה: Appartment ← GardenApp, Appartment ← Luxary ← Penthouse (ירושה).
סעיף ב
Appartment: owner, floor, numApp, area; GardenApp extends Appartment: gardenArea; Luxary extends Appartment: terraceArea; Penthouse extends Luxary: numTerr, seaView.
לפי ההיררכיה מסעיף א, בכל מחלקה מגדירים רק את התכונות שהיא מוסיפה; השאר עוברות בירושה. התכונות פרטיות (private) לפי עקרון הכימוס, והגישה אליהן מהמחלקות היורשות ומבחוץ – דרך פעולות get (לפי ההערה בשאלה הן קיימות).
public class Appartment
{
private String owner; // שם בעל הדירה
private int floor; // מספר קומה
private int numApp; // מספר דירה
private int area; // שטח הדירה
}
public class GardenApp extends Appartment
{
private int gardenArea; // שטח הגינה
}
public class Luxary extends Appartment
{
private int terraceArea; // שטח המרפסת (בפנטהאוז: השטח הכולל של המרפסות)
}
public class Penthouse extends Luxary
{
private int numTerr; // מספר מרפסות
private boolean seaView; // נוף לים - כן/לא
}public class Appartment
{
private string owner; // שם בעל הדירה
private int floor; // מספר קומה
private int numApp; // מספר דירה
private int area; // שטח הדירה
}
public class GardenApp : Appartment
{
private int gardenArea; // שטח הגינה
}
public class Luxary : Appartment
{
private int terraceArea; // שטח המרפסת (בפנטהאוז: השטח הכולל של המרפסות)
}
public class Penthouse : Luxary
{
private int numTerr; // מספר מרפסות
private bool seaView; // נוף לים - כן/לא
}תשובה: הכותרות והתכונות שלמעלה.
סעיף ג
COST_APP במחלקה Appartment (כל הדירות משתמשות בו); COST_GARDEN במחלקה GardenApp; COST_TERRACE במחלקה Luxary (ו-Penthouse מקבלת אותו בירושה).
העיקרון: כל קבוע מגדירים במחלקה הכללית ביותר שצריכה אותו – כך הוא זמין בירושה לכל מי שצריך, ולא מופיע במחלקות שאין להן שימוש בו.
1. COST_APP – מחיר מ"ר של דירה משמש לחישוב המחיר של כל סוגי הדירות, ולכן הוא במחלקת הבסיס Appartment. כל המחלקות היורשות מקבלות אותו.
2. COST_GARDEN – רק לדירת גן יש גינה, ולכן הוא במחלקה GardenApp.
3. COST_TERRACE – מרפסת יש ל-Luxary ול-Penthouse. מאחר ש-Penthouse יורשת מ-Luxary, מספיק להגדיר אותו ב-Luxary.
מגדירים אותם protected (או public) כדי שהמחלקות היורשות יוכלו להשתמש בהם. (אפשר גם להגדיר אותם static, כי הערך זהה לכל העצמים; ב-C# קבוע const הוא סטטי ממילא.)
public class Appartment
{
protected final int COST_APP = 1000; // מחיר למ"ר של דירה
...
}
public class GardenApp extends Appartment
{
protected final int COST_GARDEN = 50; // מחיר למ"ר של גינה
...
}
public class Luxary extends Appartment
{
protected final int COST_TERRACE = 300; // מחיר למ"ר של מרפסת
...
}public class Appartment
{
protected const int COST_APP = 1000; // מחיר למ"ר של דירה
...
}
public class GardenApp : Appartment
{
protected const int COST_GARDEN = 50; // מחיר למ"ר של גינה
...
}
public class Luxary : Appartment
{
protected const int COST_TERRACE = 300; // מחיר למ"ר של מרפסת
...
}תשובה: COST_APP ב-Appartment, COST_GARDEN ב-GardenApp, COST_TERRACE ב-Luxary.
סעיף ד
getPrice בכל ארבע המחלקות: Appartment – area·1000; GardenApp – super + gardenArea·50; Luxary – super + terraceArea·300; Penthouse – super של Luxary, ואם אין נוף לים כפול 0.95.
הרעיון: פעולה אחת getPrice שכל מחלקה דורסת ומרחיבה: כל מחלקה מוסיפה רק את החלק שלה למחיר, ואת שאר המחיר מקבלת מ-`super.getPrice()` (ב-C#: `base.GetPrice()`, והפעולה במחלקת הבסיס מוגדרת virtual). כך, בזכות הפולימורפיזם, אפשר לקרוא ל-getPrice על כל דירה – גם דרך הפניה מטיפוס Appartment – ולקבל את המחיר הנכון.
1. Appartment: מחיר = שטח הדירה × COST_APP.
2. GardenApp: מחיר הדירה (super) + שטח הגינה × COST_GARDEN.
3. Luxary: מחיר הדירה (super) + שטח המרפסת × COST_TERRACE.
4. Penthouse: המחיר של Luxary (דירה + מרפסות, כי terraceArea הוא השטח הכולל של המרפסות); אם אין נוף לים – כופלים ב-0.95 (הנחה של 5%).
המחלקות המלאות (עם בנאים ופעולות get שהשאלה מניחה):
public class Appartment
{
protected final int COST_APP = 1000; // מחיר למ"ר של דירה
private String owner; // שם בעל הדירה
private int floor; // מספר קומה
private int numApp; // מספר דירה
private int area; // שטח הדירה
public Appartment(int floor, int numApp, int area)
{
this.owner = "FREE";
this.floor = floor;
this.numApp = numApp;
this.area = area;
}
public void setOwner(String name) { this.owner = name; }
public String getOwner() { return this.owner; }
public int getArea() { return this.area; }
public double getPrice()
{
return this.area * COST_APP;
}
public String toString()
{
return "owner: " + owner + ", floor: " + floor + ", app: " + numApp + ", area: " + area;
}
}
public class GardenApp extends Appartment
{
protected final int COST_GARDEN = 50; // מחיר למ"ר של גינה
private int gardenArea; // שטח הגינה
public GardenApp(int floor, int numApp, int area, int gardenArea)
{
super(floor, numApp, area);
this.gardenArea = gardenArea;
}
public int getGardenArea() { return this.gardenArea; }
public double getPrice()
{
return super.getPrice() + this.gardenArea * COST_GARDEN;
}
}
public class Luxary extends Appartment
{
protected final int COST_TERRACE = 300; // מחיר למ"ר של מרפסת
private int terraceArea; // שטח המרפסת (בפנטהאוז: השטח הכולל של המרפסות)
public Luxary(int floor, int numApp, int area, int terraceArea)
{
super(floor, numApp, area);
this.terraceArea = terraceArea;
}
public int getTerraceArea() { return this.terraceArea; }
public double getPrice()
{
return super.getPrice() + this.terraceArea * COST_TERRACE;
}
}
public class Penthouse extends Luxary
{
private int numTerr; // מספר מרפסות
private boolean seaView; // נוף לים - כן/לא
public Penthouse(int floor, int numApp, int area, int numTerr,
int terraceArea, boolean seaView)
{
super(floor, numApp, area, terraceArea);
this.numTerr = numTerr;
this.seaView = seaView;
}
public int getNumTerr() { return this.numTerr; }
public boolean getSeaView() { return this.seaView; }
public double getPrice()
{
double price = super.getPrice(); // דירה + מרפסות
if (!this.seaView)
price = price * 0.95; // הנחה של 5% לפנטהאוז בלי נוף לים
return price;
}
}public class Appartment
{
protected const int COST_APP = 1000; // מחיר למ"ר של דירה
private string owner; // שם בעל הדירה
private int floor; // מספר קומה
private int numApp; // מספר דירה
private int area; // שטח הדירה
public Appartment(int floor, int numApp, int area)
{
this.owner = "FREE";
this.floor = floor;
this.numApp = numApp;
this.area = area;
}
public void SetOwner(string name) { this.owner = name; }
public string GetOwner() { return this.owner; }
public int GetArea() { return this.area; }
public virtual double GetPrice()
{
return this.area * COST_APP;
}
public override string ToString()
{
return "owner: " + owner + ", floor: " + floor + ", app: " + numApp + ", area: " + area;
}
}
public class GardenApp : Appartment
{
protected const int COST_GARDEN = 50; // מחיר למ"ר של גינה
private int gardenArea; // שטח הגינה
public GardenApp(int floor, int numApp, int area, int gardenArea)
: base(floor, numApp, area)
{
this.gardenArea = gardenArea;
}
public int GetGardenArea() { return this.gardenArea; }
public override double GetPrice()
{
return base.GetPrice() + this.gardenArea * COST_GARDEN;
}
}
public class Luxary : Appartment
{
protected const int COST_TERRACE = 300; // מחיר למ"ר של מרפסת
private int terraceArea; // שטח המרפסת (בפנטהאוז: השטח הכולל של המרפסות)
public Luxary(int floor, int numApp, int area, int terraceArea)
: base(floor, numApp, area)
{
this.terraceArea = terraceArea;
}
public int GetTerraceArea() { return this.terraceArea; }
public override double GetPrice()
{
return base.GetPrice() + this.terraceArea * COST_TERRACE;
}
}
public class Penthouse : Luxary
{
private int numTerr; // מספר מרפסות
private bool seaView; // נוף לים - כן/לא
public Penthouse(int floor, int numApp, int area, int numTerr,
int terraceArea, bool seaView)
: base(floor, numApp, area, terraceArea)
{
this.numTerr = numTerr;
this.seaView = seaView;
}
public int GetNumTerr() { return this.numTerr; }
public bool GetSeaView() { return this.seaView; }
public override double GetPrice()
{
double price = base.GetPrice(); // דירה + מרפסות
if (!this.seaView)
price = price * 0.95; // הנחה של 5% לפנטהאוז בלי נוף לים
return price;
}
}דוגמה: פנטהאוז בשטח 150 מ"ר עם מרפסות בשטח כולל 50 מ"ר: ; בלי נוף לים: . דירת גן 100 מ"ר עם גינה 40 מ"ר: .
תשובה: פעולה getPrice בכל אחת מארבע המחלקות, כמו בקוד שלמעלה.
סעיף ה
עוברים על המערך ומדפיסים כל דירה שבעליה "FREE" (פנויה) ו-getPrice() שלה קטן או שווה לסכום.
הרעיון: דירה פנויה למכירה היא דירה שהבנאי קבע לה owner = "FREE" ועדיין לא נקבע לה בעלים בפעולה setOwner. המערך הוא מטיפוס Appartment, אבל כל תא יכול להכיל כל סוג דירה, והקריאה ל-getPrice מפעילה את הגרסה של הטיפוס האמיתי (פולימורפיזם) – כך המחיר נכון לכל סוג.
1. עוברים על כל תאי המערך (מדלגים על תא ריק, null).
2. אם `getOwner()` שווה ל-"FREE" (ב-Java משווים מחרוזות עם equals) וגם `getPrice() <= money` – מדפיסים את הדירה (println מפעילה את toString שלה).
public static void printForSale(Appartment[] arr, double money)
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i] != null &&
arr[i].getOwner().equals("FREE") && // הדירה פנויה למכירה
arr[i].getPrice() <= money) // המחיר אינו עולה על הסכום
System.out.println(arr[i]);
}
}public static void PrintForSale(Appartment[] arr, double money)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] != null &&
arr[i].GetOwner() == "FREE" && // הדירה פנויה למכירה
arr[i].GetPrice() <= money) // המחיר אינו עולה על הסכום
Console.WriteLine(arr[i]);
}
}דוגמה: בבניין: דירה רגילה 100 מ"ר שכבר נמכרה, דירת גן (102000), דירת פאר 120 מ"ר עם מרפסת 20 מ"ר () ופנטהאוז בלי נוף לים ב-156750. ללקוח עם 150000 יודפסו דירת הגן ודירת הפאר (הפנטהאוז יקר מהסכום, והדירה הרגילה כבר אינה פנויה).
תשובה: הפעולה printForSale שלמעלה.
שאלה 10 · מצלמות מהירות ורשת מצלמות
במסגרת המלחמה בתאונות הדרכים, הציבו בכבישים ברחבי הארץ מצלמות אוטומטיות (מכמונות) למדידת מהירות כלי הרכב.
בכל כביש מציבים מצלמה אחת לכל היותר.
מספר המצלמות שמפוזרים בכבישים עשוי להשתנות מעת לעת עפ"י החלטת המשטרה.
במשטרת התנועה מנהלים מערכת ממוחשבת המרכזת את המידע לגבי מיקום המצלמות, וכן מידע על מכוניות אשר צולמו על ידי המצלמה.
מצלמה מהירות SpeedCamera מיוצגת באמצעות:
•קוד המצלמה.
•מספר הכביש שבו היא מוצבת.
•המהירות המקסימלית המותרת בכביש זה.
•אוסף מספרי כלי הרכב אשר נסעו במהירות גבוהה מהמהירות המותרת בכביש זה.
כתבו את כותרת המחלקה SpeedCamera ואת התכונות שלה.
כתבו את הבנאי של המחלקה המקבל את קוד המצלמה, את מספר כביש ואת המהירות המותרת.
הבנאי מאתחל אוסף מספרי כלי הרכב להיות ריק.
כתבו פעולה addCar (ב-C#: AddCar). הפעולה מקבלת את מספר מכונית שצולמה ואת המהירות שלה. אם המהירות גבוהה מהמותר בכביש זה, הפעולה תוסיף מכונית זו לאוסף של המכוניות שנסעו מהר מהמותר.
הערה: הניחו שבמחלקה SpeedCamera קיימות פעולות get ואין צורך לממש אותן.
בכל יום מציבה המשטרה 100 מצלמות לכל היותר (ייתכן אף פחות). רשת המצלמות המוצבות בכבישים ביום נתון, מיוצגת באמצעות המחלקה SpeedCameraNetwork.
כתבו את כותרת המחלקה SpeedCameraNetwork ואת התכונות שלה.
כתבו את הפעולה addSpeedCamera (ב-C#: AddSpeedCamera) המוסיפה את מצלמת המהירות sc לרשת המצלמות.
אפשר להניח שהמצלמה sc אינה מופיעה ברשת המצלמות.
במסגרת פעולות האכיפה מעוניינים לדעת מהם הכבישים המצריכים אכיפה מוגברת. כביש הדורש אכיפה מוגברת הוא כביש שבוצעו בו מעל 200 עבירות מהירות ליום.
כתבו פעולה המדפיסה את מספרי הכבישים שבהם יש לבצע אכיפה מוגברת. ציינו באיזו מחלקה יש לכתוב את הפעולה.
במשטרה רוצים לבדוק אם רכב מסוים צולם כאשר נסע במהירות הגבוהה מהמותר.
כתבו פעולה המקבלת מספר רכב. הפעולה תבדוק אם הרכב צולם כאשר נסע במהירות גבוהה מהמותר.
אם כן – הפעולה תדפיס את מספר המצלמה אשר צילמה את העבירה ותחזיר true, ואם לא – הפעולה תחזיר false.
הערה: אם רכב עשה כמה עבירות יש להדפיס את המספרים של כל המצלמות שצילמו את העבירות.
◂ פתרון מלא לשאלה 10
סעיף א
SpeedCamera עם התכונות: code, road, maxSpeed (int), cars – שרשרת חוליות `Node<Integer>` של מספרי הרכבים שעברו את המהירות, ו-numCars – מונה העבירות (תכונה נוספת).
בחירת הייצוג: לאוסף מספרי הרכב נבחר שרשרת חוליות (`Node<Integer>`): מספר העבירות לא ידוע מראש, הוספה בתחילת השרשרת היא , ובניגוד למחסנית ולתור אפשר לעבור על השרשרת ולחפש בה בלי להוציא ולהחזיר איברים (נצטרך זאת בסעיף ז). נוסיף תכונה numCars שסופרת את העבירות, כדי שלא נצטרך לספור את השרשרת בסעיף ו.
public class SpeedCamera
{
private int code; // קוד המצלמה
private int road; // מספר הכביש שבו המצלמה מוצבת
private int maxSpeed; // המהירות המקסימלית המותרת בכביש
private Node<Integer> cars; // אוסף מספרי כלי הרכב שנסעו מהר מהמותר (שרשרת חוליות)
private int numCars; // תכונה נוספת: כמה עבירות צולמו (גודל האוסף)
...
}public class SpeedCamera
{
private int code; // קוד המצלמה
private int road; // מספר הכביש שבו המצלמה מוצבת
private int maxSpeed; // המהירות המקסימלית המותרת בכביש
private Node<int> cars; // אוסף מספרי כלי הרכב שנסעו מהר מהמותר (שרשרת חוליות)
private int numCars; // תכונה נוספת: כמה עבירות צולמו (גודל האוסף)
...
}תשובה: כותרת `public class SpeedCamera` והתכונות המתועדות שלמעלה.
סעיף ב
הבנאי מציב את שלושת הפרמטרים בתכונות, ומאתחל cars = null (שרשרת ריקה) ו-numCars = 0.
הבנאי מציב את הנתונים שקיבל בתכונות המתאימות. אוסף ריק בייצוג של שרשרת חוליות הוא הפניה null, והמונה מתחיל ב-0.
public SpeedCamera(int code, int road, int maxSpeed)
{
this.code = code;
this.road = road;
this.maxSpeed = maxSpeed;
this.cars = null; // אוסף ריק
this.numCars = 0;
} public SpeedCamera(int code, int road, int maxSpeed)
{
this.code = code;
this.road = road;
this.maxSpeed = maxSpeed;
this.cars = null; // אוסף ריק
this.numCars = 0;
}תשובה: הבנאי שלמעלה.
סעיף ג
אם speed > maxSpeed – יוצרים חוליה חדשה עם מספר הרכב בתחילת השרשרת cars ומגדילים את numCars.
1. משווים את המהירות שנמדדה למהירות המותרת בכביש (התכונה maxSpeed). רק מהירות גבוהה מהמותר היא עבירה.
2. במקרה כזה מוסיפים את מספר הרכב לאוסף: חוליה חדשה שהעוקבת שלה היא תחילת השרשרת הנוכחית, והיא הופכת לתחילת השרשרת – הוספה ב- (הסדר באוסף לא חשוב).
3. מגדילים את מונה העבירות.
public void addCar(int carNum, int speed)
{
if (speed > this.maxSpeed)
{
this.cars = new Node<Integer>(carNum, this.cars); // הוספה בתחילת השרשרת
this.numCars++;
}
} public void AddCar(int carNum, int speed)
{
if (speed > this.maxSpeed)
{
this.cars = new Node<int>(carNum, this.cars); // הוספה בתחילת השרשרת
this.numCars++;
}
}תשובה: הפעולה addCar שלמעלה.
סעיף ד
SpeedCameraNetwork עם מערך `SpeedCamera[] cameras` בגודל 100 ומונה count של המצלמות שהוצבו בפועל.
מספר המצלמות חסום (100 לכל היותר), ולכן נשתמש במערך בגודל 100 ובמונה count שאומר כמה תאים בשימוש (התאים 0 עד count-1).
public class SpeedCameraNetwork
{
private SpeedCamera[] cameras; // המצלמות המוצבות היום (100 לכל היותר)
private int count; // מספר המצלמות שהוצבו בפועל
public SpeedCameraNetwork()
{
this.cameras = new SpeedCamera[100];
this.count = 0;
}
...
}public class SpeedCameraNetwork
{
private SpeedCamera[] cameras; // המצלמות המוצבות היום (100 לכל היותר)
private int count; // מספר המצלמות שהוצבו בפועל
public SpeedCameraNetwork()
{
this.cameras = new SpeedCamera[100];
this.count = 0;
}
...
}תשובה: כותרת `public class SpeedCameraNetwork` והתכונות cameras ו-count.
סעיף ה
אם count < 100 – מציבים את sc בתא cameras[count] ומגדילים את count.
1. בודקים שיש מקום במערך (`count < cameras.length`) – אי אפשר להציב יותר מ-100 מצלמות.
2. מציבים את המצלמה בתא הפנוי הראשון, שמספרו count, ומגדילים את count.
public void addSpeedCamera(SpeedCamera sc)
{
if (this.count < this.cameras.length) // יש עוד מקום במערך
{
this.cameras[this.count] = sc;
this.count++;
}
} public void AddSpeedCamera(SpeedCamera sc)
{
if (this.count < this.cameras.Length) // יש עוד מקום במערך
{
this.cameras[this.count] = sc;
this.count++;
}
}תשובה: הפעולה addSpeedCamera שלמעלה.
סעיף ו
במחלקה SpeedCameraNetwork: עוברים על המצלמות ומדפיסים את מספר הכביש של כל מצלמה שמונה העבירות שלה (getNumCars) גדול מ-200.
באיזו מחלקה: הפעולה צריכה לעבור על כל המצלמות, ולכן היא שייכת ל-SpeedCameraNetwork, שמחזיקה את המערך.
הרעיון: בכל כביש יש מצלמה אחת לכל היותר, ולכן מספר העבירות בכביש הוא מספר הרכבים באוסף של המצלמה שלו – הערך של numCars (פעולת get).
1. עוברים על התאים 0 עד count-1.
2. אם למצלמה יותר מ-200 עבירות – מדפיסים את מספר הכביש שלה.
public void printEnforcement()
{
for (int i = 0; i < this.count; i++)
{
if (this.cameras[i].getNumCars() > 200)
System.out.println(this.cameras[i].getRoad());
}
} public void PrintEnforcement()
{
for (int i = 0; i < this.count; i++)
{
if (this.cameras[i].GetNumCars() > 200)
Console.WriteLine(this.cameras[i].GetRoad());
}
}(אילו לא הוספנו את numCars, היה צורך בפעולה ב-SpeedCamera שסופרת את חוליות השרשרת cars.)
תשובה: הפעולה printEnforcement במחלקה SpeedCameraNetwork.
סעיף ז
ב-SpeedCamera פעולת עזר isCaught(carNum) שמחפשת את המספר בשרשרת cars; ב-SpeedCameraNetwork הפעולה checkCar עוברת על כל המצלמות, מדפיסה את קוד כל מצלמה שבה הרכב נמצא, ומחזירה true אם נמצא לפחות פעם אחת, אחרת false.
הרעיון: הבדיקה נעשית בשני שלבים, כל אחד במחלקה שמחזיקה את הנתונים:
1. SpeedCamera – isCaught: עוברים על שרשרת מספרי הרכב של המצלמה ומחזירים true אם מספר הרכב נמצא בה. המעבר על השרשרת לא משנה אותה.
2. SpeedCameraNetwork – checkCar: עוברים על כל המצלמות (לא עוצרים במצלמה הראשונה, כי לפי ההערה יש להדפיס את כל המצלמות שצילמו את הרכב). לכל מצלמה שבה הרכב נמצא – מדפיסים את קוד המצלמה ומסמנים found = true.
3. בסוף מחזירים את found: true אם הרכב צולם לפחות פעם אחת, אחרת false.
public boolean isCaught(int carNum)
{
Node<Integer> p = this.cars;
while (p != null)
{
if (p.getValue() == carNum)
return true;
p = p.getNext();
}
return false;
} public bool IsCaught(int carNum)
{
Node<int> p = this.cars;
while (p != null)
{
if (p.GetValue() == carNum)
return true;
p = p.GetNext();
}
return false;
} public boolean checkCar(int carNum)
{
boolean found = false;
for (int i = 0; i < this.count; i++)
{
if (this.cameras[i].isCaught(carNum))
{
System.out.println(this.cameras[i].getCode());
found = true;
}
}
return found;
} public bool CheckCar(int carNum)
{
bool found = false;
for (int i = 0; i < this.count; i++)
{
if (this.cameras[i].IsCaught(carNum))
{
Console.WriteLine(this.cameras[i].GetCode());
found = true;
}
}
return found;
}דוגמה: רכב שצולם במצלמות 11 ו-33 – מודפסים 11 ו-33 ומוחזר true; רכב שלא צולם – לא מודפס דבר ומוחזר false.
תשובה: הפעולות isCaught ו-checkCar שלמעלה.
שאלה 11 · תכונות עץ שמקיים תנאי מקומי
נתונה פעולה הבאה:
public static boolean what(BinNode<Integer> t)
{
if (t==null) return true;
int x = t.getValue();
if (t.getLeft()!=null && t.getLeft().getValue()>=x)
return false;
if (t.getRight()!=null && t.getRight().getValue()<x)
return false;
return what(t.getLeft()) && what(t.getRight());
}public static bool What(BinNode<int> t)
{
if (t == null) return true;
int x = t.GetValue();
if (t.GetLeft()!=null && t.GetLeft().GetValue() >= x)
return false;
if (t.GetRight()!=null && t.GetRight().GetValue() < x)
return false;
return What(t.GetLeft()) && What(t.GetRight());
}נתון עץ בינארי t שעבורו הפעולה what(t) מחזירה ערך true. עבור כל אחת מטענות הבאות ענו אם היא נכונה או לא. אם הטענה אינה נכונה, יש לצייר דוגמת עץ סותרת.
אם בשורש העץ הופיע המספר 13 , 13 יכול להופיע שוב רק כבנו הימני של השורש.
אם בשורש העץ הופיע המספר 13 , 13 יכול להופיע שוב רק בתת-עץ הימני של השורש.
אם בשורש העץ הופיע המספר 13 , 13 יכול להופיע במקומות רבים בעץ, כולל תת העץ השמאלי, אך לא כבנו של צומת שערכו 13 או פחות.
לא ייתכנו בעץ t שני אחים בעלי ערך זהה.
אם אין בעץ t אף בן ימני, (עץ 'שרוך'), סריקתו בסדר תחילי תדפיס ערכים ממוינים מהגדול לקטן.
סריקת העץ בסדר תוכי תדפיס תמיד ערכים ממוינים.
◂ פתרון מלא לשאלה 11
פתרון
לא נכונה. דוגמה סותרת: שורש 13, בן שמאלי 10, ולצומת 10 בן ימני 13.
מה what בודקת: בכל צומת שערכו x – אם יש בן שמאלי, ערכו קטן ממש מ-x; אם יש בן ימני, ערכו גדול או שווה ל-x. הבדיקה היא רק בין צומת לבניו הישירים, ולא מול כל הצאצאים (בשונה מעץ חיפוש בינארי).
לכן ערך שווה לשורש יכול להופיע עמוק יותר בעץ, גם בתת-העץ השמאלי. דוגמה סותרת: עץ שבשורשו 13, לשורש בן שמאלי 10, ולצומת 10 בן ימני 13 (ואין צמתים נוספים).
בדיקה: בשורש – הבן השמאלי ; בצומת 10 – הבן הימני ; העלה 13 תקין. לכן what מחזירה true.
המספר 13 מופיע שוב – אבל לא כבנו הימני של השורש (אלא בתת-העץ השמאלי).
תשובה: לא נכונה.
לא נכונה. אותה דוגמה סותרת: שורש 13, בן שמאלי 10, ולצומת 10 בן ימני 13 – 13 בתת-העץ השמאלי.
התנאי מחייב רק שהבן השמאלי הישיר של השורש יהיה קטן מ-13. צאצאים עמוקים יותר בתת-העץ השמאלי נבדקים רק מול ההורים שלהם, ולכן יכולים להיות 13 ואף יותר.
דוגמה סותרת: עץ שבשורשו 13, לשורש בן שמאלי 10, ולצומת 10 בן ימני 13 (ואין צמתים נוספים).
בדיקה: בשורש – הבן השמאלי ; בצומת 10 – הבן הימני ; העלה 13 תקין. לכן what מחזירה true.
13 מופיע בתת-העץ השמאלי של השורש.
תשובה: לא נכונה.
לא נכונה. 13 יכול להיות בן ימני של צומת שערכו 13 או פחות – למשל שורש 13 ובנו הימני 13.
החלק הראשון של הטענה נכון: 13 יכול להופיע במקומות רבים, כולל בתת-העץ השמאלי (ראו טענה 1). אבל החלק השני אינו נכון:
1. כבן שמאלי של צומת שערכו 13 או פחות – 13 באמת אינו יכול להופיע (בן שמאלי חייב להיות קטן ממש מאביו).
2. כבן ימני – התנאי הוא רק שהבן יהיה גדול או שווה לאביו, ולכן 13 יכול להיות בנו הימני של צומת שערכו 13 או פחות.
דוגמה סותרת: עץ שבשורשו 13 ולשורש בן ימני 13. בדיקה: , ולכן what מחזירה true – ו-13 הוא בנו של צומת שערכו 13. (גם בדוגמה של טענה 1, 13 הוא בנו הימני של הצומת 10.)
תשובה: לא נכונה.
נכונה. לכל צומת x: בן שמאלי < x ≤ בן ימני, ולכן הבן השמאלי קטן ממש מהבן הימני.
יהיו לצומת שערכו x שני בנים, שמאלי L וימני R. כי what מחזירה true, התנאי מתקיים בכל צומת, ובפרט בצומת הזה:
וגם , ולכן , כלומר .
שני אחים הם תמיד בן שמאלי ובן ימני של אותו צומת, ולכן ערכיהם תמיד שונים.
תשובה: נכונה.
נכונה. בעץ שרוך שמאלי כל צומת גדול ממש מבנו השמאלי, וסריקה תחילית עוברת מהשורש כלפי מטה – ערכים יורדים ממש.
1. אם אין אף בן ימני, העץ הוא שרשרת: שורש, בנו השמאלי, בנו השמאלי של הבן וכן הלאה.
2. סריקה בסדר תחילי מבקרת קודם בצומת ואחר כך בתת-העץ השמאלי, ולכן היא עוברת על השרשרת מלמעלה למטה.
3. לפי התנאי בכל צומת, הבן השמאלי קטן ממש מאביו. לכן כל ערך שמודפס קטן מהקודם – הסדר ממוין מהגדול לקטן.
לדוגמה: 9 ← 5 ← 2 (כל אחד בנו השמאלי של הקודם) – הסריקה התחילית מדפיסה 9, 5, 2.
תשובה: נכונה.
לא נכונה. דוגמה סותרת: שורש 13, בן שמאלי 10, ולצומת 10 בן ימני 20 – what מחזירה true, והסריקה התוכית מדפיסה 10, 20, 13.
סריקה תוכית ממיינת רק עץ חיפוש בינארי, שבו כל צאצאי תת-העץ השמאלי קטנים מהצומת. כאן התנאי בודק רק את הבנים הישירים, ולכן צאצא עמוק בתת-העץ השמאלי יכול להיות גדול מהשורש.
דוגמה סותרת: עץ שבשורשו 13, לשורש בן שמאלי 10, ולצומת 10 בן ימני 20.
בדיקה: בשורש, בצומת 10 – what מחזירה true.
סריקה תוכית (שמאל, צומת, ימין): בתת-העץ של 10 – 10 ואז 20, ואחר כך השורש 13. מודפס 10, 20, 13 – לא ממוין.
תשובה: לא נכונה.