מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2023 מועד א'
הנדסת תוכנה · סמל 97104 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2023 מועד א', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 14)
בכל מבחן 14 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 7-9: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 10-12: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 11 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · סכום ספרות של מספרים תלת-ספרתיים
כתבו קטע תוכנית שיקלוט 100 מספרים חיוביים ושלמים. עבור כל מספר תלת ספרתי שנקלט, יש להדפיס את סכום ספרותיו.
◂ פתרון מלא לשאלה 1
פתרון
לולאת for של 100 קליטות; אם מפרקים את המספר לספרות בעזרת `%10` ו-`/10`, מסכמים ומדפיסים את הסכום.
הרעיון: מספר הקלטים ידוע מראש (100), ולכן לולאת for. לכל מספר בודקים אם הוא תלת-ספרתי, ורק אז מחשבים את סכום ספרותיו.
1. מספר חיובי הוא תלת-ספרתי אם ורק אם .
2. פירוק לספרות: `temp % 10` נותן את ספרת האחדות, ו-`temp / 10` (חילוק שלמים) מוחק אותה. חוזרים על כך עד ש-temp מתאפס, ובכל סיבוב מוסיפים את הספרה לצובר `sum`.
3. עובדים על עותק `temp` כדי שהמספר המקורי `num` יישאר לצורך ההדפסה.
4. הצובר `sum` מאופס מחדש לכל מספר (בתוך ה-if), אחרת הסכומים של מספרים שונים יצטברו זה על זה.
import java.util.Scanner;
public class Q1
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
for (int i = 0; i < 100; i++)
{
int num = in.nextInt();
if (num >= 100 && num <= 999) // מספר תלת-ספרתי
{
int sum = 0;
int temp = num;
while (temp > 0)
{
sum += temp % 10; // ספרת האחדות
temp /= 10; // מחיקת ספרת האחדות
}
System.out.println(num + ": " + sum);
}
}
}
}using System;
class Program
{
static void Main(string[] args)
{
for (int i = 0; i < 100; i++)
{
int num = int.Parse(Console.ReadLine());
if (num >= 100 && num <= 999) // מספר תלת-ספרתי
{
int sum = 0;
int temp = num;
while (temp > 0)
{
sum += temp % 10; // ספרת האחדות
temp /= 10; // מחיקת ספרת האחדות
}
Console.WriteLine(num + ": " + sum);
}
}
}
}דוגמה: עבור הקלט 457 יודפס `457: 16` (); עבור 45 או 1000 לא יודפס דבר.
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · ספירת מחרוזות עם X וללא Y
כתבו קטע תוכנית הקולט מחרוזות עד שתיקלט מחרוזת שאורכה גדול מ- 13 תווים. הקטע יחשב וידפיס את מספר המחרוזות שכוללות את האות 'X' אבל לא כוללות את האות 'Y'.
◂ פתרון מלא לשאלה 2
פתרון
לולאת while שרצה כל עוד אורך המחרוזת ; מונים מחרוזת אם `indexOf('X') != -1` וגם `indexOf('Y') == -1`; בסוף מדפיסים את המונה.
הרעיון: מספר המחרוזות אינו ידוע מראש, והקלט מסתיים כאשר נקלטת מחרוזת שאורכה גדול מ-13. לכן לולאת while עם "זקיף": קולטים מחרוזת לפני הלולאה, וכל עוד אורכה לכל היותר 13 מטפלים בה וקולטים את הבאה. המחרוזת הארוכה שמסיימת את הקלט אינה נבדקת.
1. `str.indexOf('X')` מחזירה את מקום ההופעה הראשונה של התו 'X' במחרוזת, או אם הוא אינו מופיע.
2. לכן המחרוזת כוללת 'X' אם `indexOf('X') != -1`, ואינה כוללת 'Y' אם `indexOf('Y') == -1`. שני התנאים נדרשים יחד, ולכן `&&`.
3. כאשר שני התנאים מתקיימים מגדילים את המונה `count`, ובסוף מדפיסים אותו.
import java.util.Scanner;
public class Q2
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int count = 0;
String str = in.next();
while (str.length() <= 13)
{
if (str.indexOf('X') != -1 && str.indexOf('Y') == -1)
count++;
str = in.next();
}
System.out.println("Number of strings: " + count);
}
}using System;
class Program
{
static void Main(string[] args)
{
int count = 0;
string str = Console.ReadLine();
while (str.Length <= 13)
{
if (str.IndexOf('X') != -1 && str.IndexOf('Y') == -1)
count++;
str = Console.ReadLine();
}
Console.WriteLine("Number of strings: " + count);
}
}דוגמה: עבור הקלט `AXB`, `XY`, `abc`, `X`, `ABCDEFGHIJKLMN` (14 תווים - מסיים) יודפס 2 (המחרוזות `AXB` ו-`X`).
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · בדיקת מערך ערכים ייחודיים
מערך של מספרים שלמים נקרא "מערך ערכים ייחודיים" אם כל ערך במערך מופיע פעם אחת בלבד (ללא חזרות).
כתבו פעולה המקבלת מערך של מספרים שלמים `arr`, מספר שלם המציין מיקום במערך `ind` וערך נוסף `value`. הפעולה תבדוק אם הערך `value` נמצא במערך אחרי המיקום `index`.
אם כן, הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isInArray(int[] arr, int ind, int value)public static bool IsInArray(int[] arr, int ind, int value)כתבו פעולה המקבלת מערך של מספרים שלמים ובודקת אם הוא "מערך ערכים ייחודיים".
אם כן, הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isUniqueArray(int[] arr)public static bool IsUniqueArray(int[] arr)◂ פתרון מלא לשאלה 3
סעיף א
לולאה מ-`ind+1` עד סוף המערך; אם נמצא תא השווה ל-`value` מחזירים true, ואם הלולאה הסתיימה - false.
הרעיון: חיפוש סדרתי, אבל רק בחלק של המערך שאחרי המקום `ind` (בשאלה הוא נקרא גם index). לכן הלולאה מתחילה ב-`ind + 1` ומסתיימת בתא האחרון.
1. אם באחד התאים `arr[i] == value` - מצאנו את הערך, ומחזירים true מיד.
2. אם הלולאה הסתיימה בלי למצוא - הערך אינו מופיע אחרי `ind`, ומחזירים false.
3. אם `ind` הוא התא האחרון, הלולאה לא מתבצעת כלל ומוחזר false - נכון, כי אין תאים אחריו.
public static boolean isInArray(int[] arr, int ind, int value)
{
for (int i = ind + 1; i < arr.length; i++)
{
if (arr[i] == value)
return true;
}
return false;
}public static bool IsInArray(int[] arr, int ind, int value)
{
for (int i = ind + 1; i < arr.Length; i++)
{
if (arr[i] == value)
return true;
}
return false;
}דוגמה: עבור `arr = {5, 4, 5}`: `isInArray(arr, 0, 5)` מחזירה true (5 נמצא במקום 2), ו-`isInArray(arr, 2, 5)` מחזירה false.
תשובה: הפעולה שלמעלה.
סעיף ב
לכל i בודקים `isInArray(arr, i, arr[i])`; אם הערך חוזר אחרי מקומו מחזירים false, ואם אף ערך לא חוזר - true. סיבוכיות .
הרעיון: אם ערך מופיע במערך יותר מפעם אחת, אז בהופעה הראשונה שלו הוא מופיע שוב אחרי המקום שלו. לכן מספיק לבדוק, לכל תא `i`, אם הערך `arr[i]` נמצא אחרי המקום `i` - וזה בדיוק מה שהפעולה מסעיף א' עושה.
1. עוברים על כל התאים `i` מ-0 עד סוף המערך.
2. אם `isInArray(arr, i, arr[i])` מחזירה true, נמצאה חזרה - המערך אינו "מערך ערכים ייחודיים", ומחזירים false.
3. אם אף תא לא חוזר אחרי מקומו - כל ערך מופיע פעם אחת, ומחזירים true.
4. סיבוכיות: לכל אחד מ- התאים הפעולה isInArray עוברת על עד תאים, ולכן .
public static boolean isUniqueArray(int[] arr)
{
for (int i = 0; i < arr.length; i++)
{
if (isInArray(arr, i, arr[i])) // הערך arr[i] חוזר מאוחר יותר
return false;
}
return true;
}public static bool IsUniqueArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (IsInArray(arr, i, arr[i])) // הערך arr[i] חוזר מאוחר יותר
return false;
}
return true;
}דוגמה: `{1, 2, 3}` - true. `{1, 2, 1}` - כבר עבור הערך 1 נמצא במקום 2, ולכן false.
תשובה: הפעולה שלמעלה.
שאלה 4 · מחלקת אוטובוס: מעקב הפניות ומערך תוצאה
נתונה המחלקה Bus, המייצגת אוטובוס. תכונות המחלקה הן:
•שם נהג – `name`, מטיפוס מחרוזת – `String`.
•לוחות רישוי – `plateNumber`, מטיפוס מחרוזת – `String`.
•מספר קו – `routeNumber`, מטיפוס מחרוזת – `String`.
•מספר נוסעים – `passengers`, מטיפוס מספר שלם - `int`.
במחלקה הוגדרה פעולה בונה (constructor) המקבלת פרמטר לכל תכונה ויוצרת עצם מסוג Bus, המכיל את הערכים האלו בתכונות. כמו כן יש פעולות get/set לכל אחת מהתכונות.
עקבו אחרי קטע התוכנית, לכל עצם רשמו את השמות של כל התכונות שלו, את הערכים של כל התכונות ואת השינויים שהיו בהם, רשמו את הפלט.
Bus [] b=new Bus [5];
b[0] = new Bus ("Alex", "1234", "14", 18);
b[1] = new Bus ("Benny", "7596", "26A", 17);
b[2] = new Bus ("Charly", "6051", "26B", 16);
b[3] = new Bus ("Dani", "4472", "778", 21);
b[4] = b[3];
int m = 0, s = 0;
int x = b[1].getPassengers();
b[1].setPassengers (b[3]. getPassengers ()+5);
b[3].setPassengers (x);
for (int i = 0; i < b.length; i++)
{
System.out.println (b[i].getName()+" "+ b[i]. getPassengers ());
s=s + b[i].getPassengers ();
if (b[i].getPassengers () > 20) m++;
}
System.out.println ((double)s/b.length);
System.out.println (m); Bus [] b=new Bus [5];
b[0] = new Bus ("Alex", "1234", "14", 18);
b[1] = new Bus ("Benny", "7596", "26A", 17);
b[2] = new Bus ("Charly", "6051", "26B", 16);
b[3] = new Bus ("Dani", "4472", "778", 21);
b[4] = b[3];
int m = 0, s = 0;
int x = b[1].GetPassengers();
b[1].SetPassengers (b[3]. GetPassengers ()+5);
b[3].SetPassengers (x);
for (int i = 0; i < b.Length; i++)
{
Console.WriteLine (b[i].GetName()+" "+ b[i]. GetPassengers ());
s=s + b[i].GetPassengers ();
if (b[i].GetPassengers () > 20) m++;
}
Console.WriteLine ((double)s/b.Length);
Console.WriteLine (m);כתבו פעולה המקבלת מערך של עצמים מסוג `Bus`, ומספר שלם `num`.
הפעולה תחזיר מערך חדש הכולל את לוחות הרישוי של האוטובוסים שיש להם פחות מ- `num` נוסעים.
כותרת הפעולה:
public static String[] notPopular(Bus[] b, int num)public static string[] NotPopular(Bus[] b, int num)◂ פתרון מלא לשאלה 4
סעיף א
b[3] ו-b[4] מפנים לאותו עצם; אחרי העדכונים: Benny 26, Dani 17. הפלט: Alex 18, Benny 26, Charly 16, Dani 17, Dani 17, אחר כך 18.8 ו-1.
הנקודה החשובה: ההוראה `b[4] = b[3];` אינה יוצרת עצם חדש. היא מעתיקה את ההפניה, ולכן `b[3]` ו-`b[4]` מפנים לאותו עצם (Dani). כל שינוי דרך `b[3]` נראה גם דרך `b[4]`.
1. `m = 0`, `s = 0`.
2. `x = b[1].getPassengers()` - כלומר .
3. `b[1].setPassengers(b[3].getPassengers() + 5)` - מספר הנוסעים של Benny הופך ל-.
4. `b[3].setPassengers(x)` - מספר הנוסעים של Dani הופך ל-17. מכיוון ש-`b[4]` מפנה לאותו עצם, גם `b[4].getPassengers()` הוא עכשיו 17.
המצב אחרי העדכונים:
שלב 3 - הלולאה: בכל סיבוב מדפיסים שם ומספר נוסעים, צוברים ב-`s`, ומגדילים את `m` אם יש יותר מ-20 נוסעים.
אחרי הלולאה: `(double)s / b.length` (ההמרה ל-double לפני החילוק מונעת חילוק שלמים), ואחר כך מודפס .
Alex 18
Benny 26
Charly 16
Dani 17
Dani 17
18.8
1תשובה: הפלט שלמעלה; b[3] ו-b[4] הם אותו עצם, ולכן שניהם מראים 17 נוסעים.
סעיף ב
מעבר ראשון סופר כמה אוטובוסים עם פחות מ-num נוסעים; יוצרים מערך מחרוזות בגודל הזה; מעבר שני ממלא אותו בלוחות הרישוי (getPlateNumber).
הרעיון: גודל המערך החדש תלוי במספר האוטובוסים המתאימים, ואת המספר הזה לא יודעים מראש. לכן עוברים על המערך פעמיים:
1. מעבר ראשון - ספירה: מונים כמה אוטובוסים מקיימים `getPassengers() < num`.
2. יוצרים מערך מחרוזות בגודל `count` בדיוק.
3. מעבר שני - מילוי: לכל אוטובוס מתאים מכניסים את `getPlateNumber()` למקום `k` במערך החדש ומקדמים את `k`. האינדקס `k` נפרד מ-`i`, כי המערך החדש קצר יותר ונמלא ברצף.
4. מחזירים את המערך החדש. אם אין אף אוטובוס מתאים, מוחזר מערך בגודל 0.
התכונות פרטיות, ולכן הגישה אליהן מהפעולה החיצונית היא דרך פעולות ה-get.
public static String[] notPopular(Bus[] b, int num)
{
// שלב 1: ספירת האוטובוסים שיש בהם פחות מ-num נוסעים
int count = 0;
for (int i = 0; i < b.length; i++)
{
if (b[i].getPassengers() < num)
count++;
}
// שלב 2: יצירת מערך בגודל המדויק ומילויו
String[] res = new String[count];
int k = 0;
for (int i = 0; i < b.length; i++)
{
if (b[i].getPassengers() < num)
{
res[k] = b[i].getPlateNumber();
k++;
}
}
return res;
}public static string[] NotPopular(Bus[] b, int num)
{
// שלב 1: ספירת האוטובוסים שיש בהם פחות מ-num נוסעים
int count = 0;
for (int i = 0; i < b.Length; i++)
{
if (b[i].GetPassengers() < num)
count++;
}
// שלב 2: יצירת מערך בגודל המדויק ומילויו
string[] res = new string[count];
int k = 0;
for (int i = 0; i < b.Length; i++)
{
if (b[i].GetPassengers() < num)
{
res[k] = b[i].GetPlateNumber();
k++;
}
}
return res;
}דוגמה: עבור המערך מסעיף א' (אחרי השינויים) ו- יוחזר `{"6051", "4472", "4472"}` (Charly עם 16, ו-Dani עם 17 שמופיע פעמיים במערך).
תשובה: הפעולה שלמעלה.
שאלה 5 · מספרים אחים: ספרה ימנית ושמאלית
שני מספרים שונים נקראים "אחים" אם יש להם אותה ספרה הימנית ואותה ספרה השמאלית.
לדוגמה:
123 ו- 13 הם אחים, 34567 ו- 357 הם אחים, 7 ו- 7007 הם אחים.
כתבו פעולה המקבלת שני מספרים שלמים וחיוביים (גדולים מ- 0) ובודקת אם הם "אחים".
אם כן – הפעולה תחזיר ערך `true`, ולא – תחזיר `false`.
כותרת הפעולה:
public static boolean brothers(int num1, int num2)public static bool Brothers(int num1, int num2)נתונה פעולה `what` הבאה. הפעולה מקבלת שני מערכים המכילים מספרים שלמים וחיוביים.
הפעולה משתמשת בפעולה brothers שתוארה בסעיף א'.
public static boolean what(int[] a, int []b)
{
for(int i=0; i < a.length; i++)
{
boolean flag = false;
for(int k=0; k < b.length; k++)
{
if(brothers(a[i],b[k]))
{
flag = true;
}
}
if(!flag) return false;
}
return true;
}public static bool What(int[] a, int []b)
{
for(int i=0; i < a.Length; i++)
{
bool flag = false;
for(int k=0; k < b.Length; k++)
{
if(Brothers(a[i], b[k]))
{
flag = true;
}
}
if(!flag) return false;
}
return true;
}נתון מערך מספרים שלמים a:
תנו דוגמה למערך b כך שזימון הפעולה `what(a,b)` יחזיר `true`.
האם לכל זוג מערכים של מספרים שלמים חיוביים a ו- b תוצאת הזימון `what(a,b)` תהיה זהה לתוצאת הזימון `what(b,a)`? הסבירו את תשובתכם.
מה מבצעת הפעולה `what` באופן כללי?
◂ פתרון מלא לשאלה 5
סעיף א
המספרים שונים, ספרות האחדות שוות (`num % 10`) והספרות השמאליות שוות (מחלקים ב-10 עד שנשארת ספרה אחת) - true; אחרת false.
הרעיון: צריך להשוות שתי ספרות בכל מספר:
1. הספרה הימנית (ספרת האחדות) - שארית החלוקה ב-10: `num % 10`.
2. הספרה השמאלית - מחלקים את המספר ב-10 (חילוק שלמים) כל עוד הוא לפחות 10; מה שנשאר בסוף הוא הספרה השמאלית. למשל .
3. לפי ההגדרה המספרים צריכים להיות שונים, ולכן אם `num1 == num2` מחזירים false. כמו כן, ליתר ביטחון, מחזירים false עבור מספר שאינו חיובי.
4. מחזירים true רק אם שתי ההשוואות מתקיימות יחד.
עבור מספר חד-ספרתי הלולאה לא מתבצעת, והספרה השמאלית והימנית הן המספר עצמו - כך 7 ו-7007 הם אחים, כמו בדוגמה.
public static boolean brothers(int num1, int num2)
{
if (num1 <= 0 || num2 <= 0 || num1 == num2)
return false;
// ספרות האחדות (הספרות הימניות)
int right1 = num1 % 10;
int right2 = num2 % 10;
// הספרה השמאלית: מחלקים ב-10 עד שנשארת ספרה אחת
int left1 = num1;
while (left1 >= 10)
left1 /= 10;
int left2 = num2;
while (left2 >= 10)
left2 /= 10;
return right1 == right2 && left1 == left2;
}public static bool Brothers(int num1, int num2)
{
if (num1 <= 0 || num2 <= 0 || num1 == num2)
return false;
// ספרות האחדות (הספרות הימניות)
int right1 = num1 % 10;
int right2 = num2 % 10;
// הספרה השמאלית: מחלקים ב-10 עד שנשארת ספרה אחת
int left1 = num1;
while (left1 >= 10)
left1 /= 10;
int left2 = num2;
while (left2 >= 10)
left2 /= 10;
return right1 == right2 && left1 == left2;
}בדיקה מול הדוגמאות: `brothers(123, 13)`: ימניות 3 ו-3, שמאליות 1 ו-1 - true. `brothers(34567, 357)`: 7 ו-7, 3 ו-3 - true. `brothers(7, 7007)`: 7 ו-7, 7 ו-7 - true.
תשובה: הפעולה שלמעלה.
סעיף ב
למשל `int[] b = {1003, 72, 51, 7007, 2345};` (לכל איבר של a יש אח ב-b).
הרעיון: הפעולה עוברת על כל איבר `a[i]` ומחפשת לו "אח" במערך b (הדגל `flag` נעשה true אם נמצא אח). אם לאיבר כלשהו של a אין אח - מוחזר false. לכן כדי לקבל true צריך שלכל אחד מששת האיברים של a יהיה ב-b מספר שונה ממנו עם אותה ספרה שמאלית ואותה ספרה ימנית.
נבנה את b איבר אחר איבר:
int[] b = {1003, 72, 51, 7007, 2345};לכל איבר של a נמצא אח, הדגל נעשה true בכל סיבוב של הלולאה החיצונית, והפעולה מגיעה ל-`return true`.
שימו לב: 7 צריך אח שונה ממנו (למשל 7007); המספר 7 עצמו אינו "אח" של 7 לפי ההגדרה.
תשובה: `int[] b = {1003, 72, 51, 7007, 2345};`
סעיף ג
לא. למשל a = {123}, b = {13, 45}: `what(a,b)` = true אבל `what(b,a)` = false, כי ל-45 אין אח ב-a.
לא. הפעולה אינה סימטרית: `what(a,b)` בודקת שלכל איבר של a יש אח ב-b, אבל אינה בודקת דבר על איברי b שאין להם אח ב-a. בזימון `what(b,a)` התפקידים מתחלפים.
דוגמה נגדית: `a = {123}`, `b = {13, 45}`.
1. `what(a, b)`: ל-123 יש אח ב-b (13) - מוחזר true.
2. `what(b, a)`: ל-13 יש אח ב-a (123), אבל ל-45 (שמאלית 4, ימנית 5) אין אח ב-a - מוחזר false.
תשובה: לא; למשל עבור a = {123}, b = {13, 45} מתקבל `what(a,b) = true` אבל `what(b,a) = false`.
סעיף ד
מחזירה true אם לכל איבר במערך a יש לפחות "אח" אחד במערך b, ואחרת false.
לכל איבר `a[i]` הלולאה הפנימית עוברת על כל b ומסמנת בדגל אם נמצא לו אח. אם עבור איבר כלשהו הדגל נשאר false, מוחזר false מיד; אם כל האיברים עברו - מוחזר true.
תשובה: הפעולה מחזירה true אם לכל איבר במערך a קיים לפחות "אח" אחד במערך b, ואחרת מחזירה false.
שאלה 6 · מעקב: ספירת אותיות גדולות במחרוזות
נתונה הפעולה `why()` הבאה המקבלת מחרוזת:
public static int why(String str)
{
int c = 0;
System.out.print("%");
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) < 'A' || str.charAt(i) > 'Z')
{
System.out.print(i + " ");
}
else c++;
}
System.out.println("%");
return c;
}public static int Why(string str)
{
int c = 0;
Console.Write("%");
for (int i = 0; i < str.Length; i++)
{
if (str[i] < 'A' || str[i] > 'Z')
{
Console.Write(i + " ");
}
else c++;
}
Console.WriteLine("%");
return c;
}עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `why("AxyBZ3")` ורשמו מה יהיה הפלט של הפעולה ומה היא תחזיר.
תנו דוגמה למחרוזת באורך של שישה תווים לכל הפחות שעבורה הפעולה `why` תדפיס את המחרוזת הבאה: `%1 3 5 %`.
מה מבצעת הפעולה `why` באופן כללי?
נתונה הפעולה mystery המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה why:
public static boolean mystery(String[] arr)
{
for (int k = 0; k < arr.length; k++)
{
if (why(arr[k]) != k )
return false;
}
return true;
}public static bool Mystery(string[] arr)
{
for (int k = 0; k < arr.Length; k++)
{
if (Why(arr[k]) != k )
return false;
}
return true;
}תנו דוגמה למערך מחרוזות `arr` בגודל שישה תאים שעבורו הפעולה `mystery` תחזיר ערך `true`.
מה יהיה הפלט של הפעולה עבור מערך שנתתם בסעיף ב'1?
◂ פתרון מלא לשאלה 6
סעיף א
הפלט: `%1 2 5 %`; הערך המוחזר: 3.
הפעולה מדפיסה `%`, ואז לכל תו: אם הוא אינו אות גדולה (קטן מ-'A' או גדול מ-'Z') מודפס המקום שלו ואחריו רווח; אחרת מגדילים את המונה c. בסוף מודפס `%` וירידת שורה.
תשובה: הפלט הוא `%1 2 5 %` והפעולה מחזירה 3.
למשל `"AxByC6"`.
המספרים המודפסים הם המקומות של התווים שאינם אותיות גדולות. כדי לקבל בדיוק `1 3 5`:
1. במקומות 1, 3, 5 - תווים שאינם אותיות גדולות (אות קטנה, ספרה וכו').
2. במקומות 0, 2, 4 - אותיות גדולות.
3. אם המחרוזת ארוכה מ-6 תווים, כל התווים ממקום 6 והלאה חייבים להיות אותיות גדולות (אחרת יודפסו מקומות נוספים).
למשל `"AxByC6"`: במקומות 0, 2, 4 נמצאות A, B, C, ובמקומות 1, 3, 5 נמצאים x, y, 6. הפלט הוא `%1 3 5 %` (והפעולה מחזירה 3).
תשובה: `"AxByC6"` (וכל מחרוזת דומה).
מדפיסה בין שני סימני % את המקומות של התווים שאינם אותיות גדולות (A-Z), ומחזירה את מספר האותיות הגדולות במחרוזת.
המונה c גדל רק בענף ה-else, כלומר כאשר התו נמצא בין 'A' ל-'Z' - אות גדולה. עבור כל תו אחר מודפס המקום שלו.
תשובה: הפעולה מדפיסה, בין שני סימני `%`, את המקומות (האינדקסים) של כל התווים במחרוזת שאינם אותיות גדולות באנגלית, ומחזירה את מספר האותיות הגדולות במחרוזת.
סעיף ב
למשל `{"a", "Ab", "ABc", "ABCd", "ABCDe", "ABCDEf"}` - במחרוזת שבמקום k יש בדיוק k אותיות גדולות.
הפעולה מחזירה true רק אם לכל k מתקיים `why(arr[k]) == k`. לפי סעיף א3, `why` מחזירה את מספר האותיות הגדולות, ולכן המחרוזת שבמקום k צריכה להכיל בדיוק k אותיות גדולות:
String[] arr = {"a", "Ab", "ABc", "ABCd", "ABCDe", "ABCDEf"};תשובה: המערך שלמעלה (במקום k מחרוזת עם בדיוק k אותיות גדולות).
שש שורות: `%0 %`, `%1 %`, `%2 %`, `%3 %`, `%4 %`, `%5 %`; הפעולה מחזירה true.
הפעולה mystery עצמה אינה מדפיסה; הפלט נוצר מזימוני `why`, אחד לכל תא (אף זימון אינו מחזיר ערך השונה מ-k, ולכן הלולאה עוברת על כל ששת התאים). בכל מחרוזת מהמערך שלנו יש תו אחד בלבד שאינו אות גדולה - התו האחרון, שנמצא במקום k:
%0 %
%1 %
%2 %
%3 %
%4 %
%5 %תשובה: שש השורות שלמעלה, והפעולה mystery מחזירה true.
שאלה 7 · מחלקת קופסה: בנאי אקראי וחיפוש מקסימום
למחלקה קופסה (תיבה) – `Box` יש חמש תכונות:
•צבע – `color`, מטיפוס מחרוזת – `String`.
•אורך – `length`, מטיפוס מספר שלם – `int`.
•רוחב – `width`, מטיפוס מספר שלם – `int`.
•גובה – `height` מטיפוס מספר שלם – `int`.
•משקל – `weight` מטיפוס מספר ממשי - `double`
במחלקה `Box` הוגדרה פעולה בונה (בנאי, `constructor`) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות `get/set` לכל אחת מהתכונות.
כתבו פעולה בונה המייצרת קופסה בצבע `color` ומשקל `weight`, שכל הממדים שלה (אורך, רוחב וגובה) הם מספרים אקראיים בין 1 ל- 10 (כולל).
כותרת הפעולה:
public Box(String color, double weight)public Box(string color, double weight)כתבו פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג `Box` בשם `arr` ומחזירה את הצבע של הקופסה בעלת המשקל הגדול ביותר במערך.
כותרת הפעולה:
public static String heaviestBox(Box[] arr)public static string HeaviestBox(Box[] arr)__הנחה__: כל תא במערך מכיל הפניה לעצם מסוג `Box` ואין תאים במערך שערכם שווה ל- `null`.
כתבו פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג `Box` בשם `arr`, צבע `color` ומחזירה את הקופסה בצבע `color` בעלת המשקל הגדול ביותר במערך. אם אין במערך אף קופסה בצבע `color`, הפעולה תחזיר `null`.
כותרת הפעולה:
public static Box heaviestColorBox (Box[] arr, String color)public static Box HeaviestColorBox (Box[] arr, string color)__הנחה__: כל תא במערך מכיל הפניה לעצם מסוג `Box` ואין תאים במערך שערכם שווה ל- `null`.
◂ פתרון מלא לשאלה 7
סעיף א
מציבים את color ו-weight מהפרמטרים, ולכל אחד מ-length, width, height מגרילים מספר שלם בין 1 ל-10: `1 + (int)(Math.random() * 10)` (ב-C#: `rand.Next(1, 11)`).
הרעיון: את הצבע ואת המשקל הבנאי מקבל כפרמטרים ומציב בתכונות. את שלושת הממדים הוא מגריל בעצמו.
לפי ההנחיות הכלליות, מספר שלם אקראי בין X ל-Y (כולל) מתקבל כך: `X + (int)(Math.random() * (Y - X + 1))`. עבור , : , כלומר `1 + (int)(Math.random() * 10)`:
1. `Math.random()` מחזירה מספר ממשי בתחום .
2. כפול 10 - תחום ; ההמרה ל-int חותכת לשלם בין 0 ל-9.
3. ועוד 1 - שלם בין 1 ל-10.
ב-C# משתמשים ב-`rand.Next(1, 11)` (הגבול העליון אינו נכלל, ולכן 11). עצם ה-Random מוגדר פעם אחת כתכונה סטטית, כדי שקופסאות שנוצרות ברצף לא יקבלו את אותם מספרים.
כל ממד מוגרל בנפרד, כדי שהאורך, הרוחב והגובה יהיו בלתי תלויים זה בזה.
public Box(String color, double weight)
{
this.color = color;
this.weight = weight;
this.length = 1 + (int)(Math.random() * 10); // 1..10
this.width = 1 + (int)(Math.random() * 10); // 1..10
this.height = 1 + (int)(Math.random() * 10); // 1..10
}private static Random rand = new Random(); // תכונה סטטית במחלקה Box
public Box(string color, double weight)
{
this.color = color;
this.weight = weight;
this.length = rand.Next(1, 11); // 1..10
this.width = rand.Next(1, 11); // 1..10
this.height = rand.Next(1, 11); // 1..10
}תשובה: הבנאי שלמעלה.
סעיף ב
חיפוש מקסימום: maxIndex מתחיל ב-0, ולכל i שבו `arr[i].getWeight()` גדול מהמשקל במקום maxIndex מעדכנים; מחזירים `arr[maxIndex].getColor()`.
הרעיון: חיפוש מקסימום רגיל, אבל שומרים את המקום של הקופסה הכבדה ולא רק את משקלה, כי בסוף צריך את הצבע שלה.
1. מניחים שהקופסה במקום 0 היא הכבדה ביותר: `maxIndex = 0` (לפי ההנחה כל התאים מכילים קופסה).
2. עוברים על שאר הקופסאות. אם משקל הקופסה הנוכחית גדול ממשקל הקופסה במקום `maxIndex`, מעדכנים את `maxIndex`.
3. בסוף מחזירים את הצבע של הקופסה במקום `maxIndex`.
התחלה מהאיבר הראשון (ולא מ-0 כמשקל התחלתי) נכונה לכל משקל, גם אם כל המשקלים קטנים או שווים לאפס. הפעולה חיצונית, ולכן הגישה לתכונות היא דרך `getWeight()` ו-`getColor()`.
public static String heaviestBox(Box[] arr)
{
int maxIndex = 0; // מקום הקופסה הכבדה ביותר עד כה
for (int i = 1; i < arr.length; i++)
{
if (arr[i].getWeight() > arr[maxIndex].getWeight())
maxIndex = i;
}
return arr[maxIndex].getColor();
}public static string HeaviestBox(Box[] arr)
{
int maxIndex = 0; // מקום הקופסה הכבדה ביותר עד כה
for (int i = 1; i < arr.Length; i++)
{
if (arr[i].GetWeight() > arr[maxIndex].GetWeight())
maxIndex = i;
}
return arr[maxIndex].GetColor();
}תשובה: הפעולה שלמעלה.
סעיף ג
משתנה `max = null`; לכל קופסה שצבעה שווה ל-color (`equals`), אם max עדיין null או שהיא כבדה ממנו - מעדכנים; מחזירים max (null אם לא נמצאה קופסה בצבע).
הרעיון: חיפוש מקסימום רק בין הקופסאות בצבע המבוקש. כאן אי אפשר להתחיל מ-`arr[0]`, כי ייתכן שהיא בצבע אחר. לכן מתחילים מ-`max = null`, שמשמעו "עדיין לא נמצאה קופסה בצבע color".
1. עוברים על כל הקופסאות. משווים צבעים עם `equals` (ב-Java השוואת מחרוזות ב-`==` משווה הפניות ולא תוכן; ב-C# האופרטור `==` על string משווה תוכן).
2. אם הקופסה בצבע המבוקש: אם `max` עדיין null (זו הקופסה הראשונה בצבע הזה) או שהיא כבדה מ-`max` - מעדכנים את `max` להפניה אליה.
3. בסוף מחזירים את `max`. אם לא נמצאה אף קופסה בצבע `color`, הוא נשאר null - בדיוק מה שהשאלה דורשת.
הסדר בתנאי `max == null || ...` חשוב: אם max הוא null, הבדיקה השנייה לא מתבצעת (הערכה מקוצרת), ולכן לא יהיה זימון `getWeight()` על null.
public static Box heaviestColorBox(Box[] arr, String color)
{
Box max = null; // עדיין לא נמצאה קופסה בצבע המבוקש
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getColor().equals(color))
{
if (max == null || arr[i].getWeight() > max.getWeight())
max = arr[i];
}
}
return max;
}public static Box HeaviestColorBox(Box[] arr, string color)
{
Box max = null; // עדיין לא נמצאה קופסה בצבע המבוקש
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetColor() == color)
{
if (max == null || arr[i].GetWeight() > max.GetWeight())
max = arr[i];
}
}
return max;
}דוגמה: עבור קופסאות (red, 3), (blue, 7.5), (red, 5), (green, 2): `heaviestColorBox(arr, "red")` מחזירה את הקופסה (red, 5), ו-`heaviestColorBox(arr, "pink")` מחזירה null.
תשובה: הפעולה שלמעלה.
שאלה 8 · השוואת מערכים: כל איברי a גדולים מ-b
נתונה הפעולה `what` המקבלת שני מערכים של מספרים שלמים:
public static boolean what (int[] a, int[] b)
{
for (int i = 0; i < a.length; i++)
{
for (int k = 0; k < b.length; k++)
{
if (a[i] <= b[k])
return false;
}
}
return true;
}public static bool What (int[] a, int[] b)
{
for (int i = 0; i < a.Length; i++)
{
for (int k = 0; k < b.Length; k++)
{
if (a[i] <= b[k])
return false;
}
}
return true;
}עקבו אחר ביצוע הפעולה `what` עבור הפרמטרים הבאים:
int[] a = {8,15,7,10}
int[] b = {6,7,2}תנו דוגמה למערכים a ו- b בגודל של ארבעה תאים כל אחד שעבורם זימון הפעולה `what(a,b)` יחזיר תוצאה שונה מהתוצאה של סעיף א'.
מה מבצעת הפעולה `what` באופן כללי?
מהי הסיבוכיות של הפעולה `what`? הסבירו את תשובתכם.
כתבו פעולה חדשה, יעילה יותר, אשר מבצעת אותה מטלה כמו הפעולה `what`.
מהי הסיבוכיות של הפעולה החדשה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
הפעולה מחזירה false: עבור , מתקיים .
הפעולה משווה כל איבר של a לכל איבר של b, ועוצרת ומחזירה false ברגע שנמצא זוג שבו `a[i] <= b[k]`.
האיבר אינו נבדק כלל, כי הפעולה הסתיימה קודם.
תשובה: הפעולה מחזירה false.
סעיף ב
למשל `a = {8,15,7,10}`, `b = {6,4,2,3}` - כל איבר של a גדול מכל איבר של b, ולכן מוחזר true.
בסעיף א' התקבל false, ולכן צריך דוגמה שבה מוחזר true - כלומר אין אף זוג שבו `a[i] <= b[k]`. זה קורה כאשר כל איבר של a גדול ממש מכל איבר של b, כלומר הקטן ביותר ב-a גדול מהגדול ביותר ב-b.
int[] a = {8, 15, 7, 10}; // הקטן ביותר: 7
int[] b = {6, 4, 2, 3}; // הגדול ביותר: 6, ולכן כל ההשוואות נכשלות, הלולאות מסתיימות והפעולה מחזירה true.
תשובה: `a = {8,15,7,10}`, `b = {6,4,2,3}`.
סעיף ג
מחזירה true אם כל איבר במערך a גדול ממש מכל האיברים במערך b, ואחרת false.
הפעולה מחזירה false ברגע שנמצא איבר של a שקטן או שווה לאיבר כלשהו של b. אם לא נמצא זוג כזה - מוחזר true.
תשובה: הפעולה מחזירה true אם כל איבר במערך a גדול ממש מכל האיברים במערך b (כלומר המינימום של a גדול מהמקסימום של b), ואחרת false.
סעיף ד
, כאשר n אורך a ו-m אורך b.
נסמן - אורך המערך a, - אורך המערך b. במקרה הגרוע (כאשר מוחזר true) הלולאה החיצונית רצה פעמים, ובכל אחת מהן הלולאה הפנימית רצה פעמים, כלומר השוואות.
תשובה: (ואם שני המערכים באורך n - ).
סעיף ה
מוצאים את המינימום של a (מעבר אחד) ואת המקסימום של b (מעבר אחד), ומחזירים `minA > maxB`.
הרעיון: כל איבר של a גדול מכל איבר של b אם ורק אם הקטן ביותר ב-a גדול מהגדול ביותר ב-b. לכן אין צורך להשוות כל זוג:
1. מעבר אחד על a - מציאת המינימום `minA`.
2. מעבר אחד על b - מציאת המקסימום `maxB`.
3. מחזירים `minA > maxB`.
מקרה קצה: אם אחד המערכים ריק, הפעולה המקורית מחזירה true (אין אף זוג להשוואה). כדי לבצע בדיוק אותה מטלה, מטפלים במקרה זה בתחילת הפעולה (וגם נמנעים מגישה ל-`a[0]` או `b[0]` שאינם קיימים).
public static boolean what2(int[] a, int[] b)
{
if (a.length == 0 || b.length == 0)
return true; // אין זוג להשוות - כמו בפעולה המקורית
int minA = a[0];
for (int i = 1; i < a.length; i++)
{
if (a[i] < minA)
minA = a[i];
}
int maxB = b[0];
for (int k = 1; k < b.length; k++)
{
if (b[k] > maxB)
maxB = b[k];
}
return minA > maxB;
}public static bool What2(int[] a, int[] b)
{
if (a.Length == 0 || b.Length == 0)
return true; // אין זוג להשוות - כמו בפעולה המקורית
int minA = a[0];
for (int i = 1; i < a.Length; i++)
{
if (a[i] < minA)
minA = a[i];
}
int maxB = b[0];
for (int k = 1; k < b.Length; k++)
{
if (b[k] > maxB)
maxB = b[k];
}
return minA > maxB;
}בדיקה: עבור סעיף א': , , אינו מתקיים - false, כמו בפעולה המקורית. עבור סעיף ב': - true.
תשובה: הפעולה שלמעלה.
סעיף ו
.
הפעולה עוברת פעם אחת על a ( צעדים) ופעם אחת על b ( צעדים), והלולאות אינן מקוננות אלא באות זו אחר זו. סך הכול צעדים.
תשובה: - סיבוכיות לינארית.
שאלה 9 · פלינדרום רגיל ופלינדרום אותיות
נתונות הגדרות הבאות:
"פָּלִינְדְּרוֹם רגיל" הוא כל רצף תווים שקריאתו מימין לשמאל ומשמאל לימין היא זהה.
דוגמאות פלינדרום רגיל:
ABCCBA, 12A21, a0X%11%X0aכתבו פעולה המקבלת מחרוזת ומחזירה ערך `true`, אם המחרוזת היא "פלינדרום רגיל",
ולא – הפעולה תחזיר `false`.
"פָּלִינְדְּרוֹם אותיות" הוא מחרוזת שכוללת אותיות גדולות וקטנות ותווים אחרים, וכך אם נתעלם מתווים שאינם אותיות, נקבל "פלינדרום רגיל".
דוגמאות פלינדרום אותיות:
f12d4A%B##C1^BAd?f01, ABCCBA, AbbCbbAכתבו פעולה המקבלת מחרוזת ומחזירה ערך `true`, אם המחרוזת היא "פלינדרום אותיות",
ולא – הפעולה תחזיר `false`.
כתבו פעולה המקבלת מערך מחרוזות ומחזירה מערך חדש הכולל רק מחרוזות שהן "פלינדרום אותיות".
◂ פתרון מלא לשאלה 9
סעיף א
שני אינדקסים מהקצוות (left, right) שמתקרבים זה לזה; אם נמצאו תווים שונים - false, ואם נפגשו - true.
הרעיון: מחרוזת היא פלינדרום אם התו הראשון שווה לאחרון, השני ללפני-אחרון, וכן הלאה. משתמשים בשני אינדקסים: `left` מתחיל בתחילת המחרוזת ו-`right` בסופה.
1. כל עוד `left < right`: אם התווים במקומות האלה שונים - המחרוזת אינה פלינדרום, ומחזירים false.
2. אחרת מקדמים את `left` ומורידים את `right`.
3. אם האינדקסים נפגשו או עברו זה את זה בלי שנמצא הבדל - מחזירים true. (באורך אי-זוגי התו האמצעי אינו נבדק, כי הוא שווה לעצמו.)
סיבוכיות: - כל תו נבדק פעם אחת לכל היותר.
public static boolean isPalindrome(String str)
{
int left = 0;
int right = str.length() - 1;
while (left < right)
{
if (str.charAt(left) != str.charAt(right))
return false;
left++;
right--;
}
return true;
}public static bool IsPalindrome(string str)
{
int left = 0;
int right = str.Length - 1;
while (left < right)
{
if (str[left] != str[right])
return false;
left++;
right--;
}
return true;
}בדיקה: עבור `"12A21"`: '1'='1', '2'='2', ואז - true. עבור `"ABCA"`: 'A'='A', אבל 'B'≠'C' - false.
תשובה: הפעולה שלמעלה.
סעיף ב
כמו בסעיף א' עם left ו-right, אבל מדלגים על תווים שאינם אותיות (`Character.isLetter`) בכל צד; משווים רק אות מול אות.
הרעיון: אותו אלגוריתם של שני אינדקסים מסעיף א', אבל מתעלמים מתווים שאינם אותיות. ההשוואה בין אותיות היא מדויקת (אות גדולה ואות קטנה נחשבות שונות), כפי שרואים בדוגמה `AbbCbbA`.
בכל סיבוב של הלולאה (כל עוד `left < right`):
1. אם התו במקום `left` אינו אות - מדלגים עליו: `left++`.
2. אחרת, אם התו במקום `right` אינו אות - מדלגים עליו: `right--`.
3. אחרת שני התווים הם אותיות: אם הם שונים - מחזירים false; אם שווים - מקדמים את שני האינדקסים.
אם הלולאה הסתיימה - כל זוגות האותיות התאימו, ומחזירים true. בכל סיבוב לפחות אחד האינדקסים זז, ולכן הלולאה מסתיימת אחרי סיבובים לכל היותר - סיבוכיות .
`Character.isLetter` (ב-C#: `char.IsLetter`) מחזירה true לאות. אפשר גם לבדוק ישירות: `(ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')`.
public static boolean isLetterPalindrome(String str)
{
int left = 0;
int right = str.length() - 1;
while (left < right)
{
if (!Character.isLetter(str.charAt(left)))
left++; // מדלגים על תו שאינו אות משמאל
else if (!Character.isLetter(str.charAt(right)))
right--; // מדלגים על תו שאינו אות מימין
else
{
if (str.charAt(left) != str.charAt(right))
return false;
left++;
right--;
}
}
return true;
}public static bool IsLetterPalindrome(string str)
{
int left = 0;
int right = str.Length - 1;
while (left < right)
{
if (!char.IsLetter(str[left]))
left++; // מדלגים על תו שאינו אות משמאל
else if (!char.IsLetter(str[right]))
right--; // מדלגים על תו שאינו אות מימין
else
{
if (str[left] != str[right])
return false;
left++;
right--;
}
}
return true;
}בדיקה: ב-`"f12d4A%B##C1^BAd?f01"` האותיות לפי הסדר הן `fdABCBAdf` - פלינדרום, ולכן true. ב-`"x1y"` האותיות הן `xy` - false.
תשובה: הפעולה שלמעלה.
סעיף ג
מעבר ראשון סופר בעזרת isLetterPalindrome כמה מחרוזות מתאימות; יוצרים מערך בגודל הזה; מעבר שני מעתיק אליו את המחרוזות המתאימות.
הרעיון: כמו בשאלה 4 ב', גודל המערך החדש אינו ידוע מראש, ולכן שני מעברים:
1. ספירה: לכל מחרוזת מזמנים את הפעולה מסעיף ב', ומונים כמה מחרוזות הן "פלינדרום אותיות".
2. יוצרים מערך מחרוזות בגודל הזה.
3. מילוי: מעבר שני מעתיק את המחרוזות המתאימות למערך החדש, לפי אינדקס `k` נפרד.
4. מחזירים את המערך החדש.
public static String[] letterPalindromes(String[] arr)
{
int count = 0;
for (int i = 0; i < arr.length; i++)
{
if (isLetterPalindrome(arr[i]))
count++;
}
String[] res = new String[count];
int k = 0;
for (int i = 0; i < arr.length; i++)
{
if (isLetterPalindrome(arr[i]))
{
res[k] = arr[i];
k++;
}
}
return res;
}public static string[] LetterPalindromes(string[] arr)
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
{
if (IsLetterPalindrome(arr[i]))
count++;
}
string[] res = new string[count];
int k = 0;
for (int i = 0; i < arr.Length; i++)
{
if (IsLetterPalindrome(arr[i]))
{
res[k] = arr[i];
k++;
}
}
return res;
}דוגמה: עבור `{"f12d4A%B##C1^BAd?f01", "Hello", "A1b2A", "AbbCbbA", "ab"}` יוחזר `{"f12d4A%B##C1^BAd?f01", "A1b2A", "AbbCbbA"}`.
תשובה: הפעולה שלמעלה.
שאלה 10 · השכרת רכב: השוואת מכוניות, מחיר ודוח
החברה "`Rent4Me`" עוסקת בהשכרת רכב ללקוחות פרטיים. לצורך מחשוב הוגדרו שמחלקות: `Date, Car, Rent`.
המחלקה Date מייצגת תאריך לפי יום, חודש ושנה. המחלקה מכילה בין היתר את הפעולה difference.
המחלקה Date כבר נתונה ואפשר להשתמש בפעולות שבה. אין צורך לממש אותן!
המחלקה Car מייצגת מכונית.
לכל רכב בצי המכוניות שומרים את הפרטים הבאים: מספר רישוי, דירוג (רמה A, רמה B, רמה C או רמה D), יצרן (למשל "Mazda"), ואם לרכב תיבת הילוכים ידנית או אוטומטית.
תכונות המחלקה:
•מספר הרישוי – `id` – מטיפוס מחרוזת, `String`.
•דירוג – `type` – מטיפוס תו, `char`.
•יצרן – `brand` – מטיפוס מחרוזת, `String`.
•האם תיבת ההילוכים ידנית? – `isManual` – מטיפוס `boolean` (`true` – ידנית, `false` – אוטומטית).
במחלקה Car הוגדרו בנאי (`constructor`), פעולות `get` ו- `set` ופעולה `toString`.
המחלקה Rent מייצגת השכרה של רכב.
תכונות המחלקה:
•שם לקוח – `name` – מטיפוס מחרוזת, `String`.
•המכונית המושכרת – `car` – מטיפוס `Car`.
•תאריך קבלת המכונית – `pickDate` – מטיפוס `Date`.
•תאריך החזרת המכונית – `returnDate` – מטיפוס `Date`.
במחלקה `Rent` הוגדרו בנאי (`constructor`), פעולות `get` ו- `set` ופעולה `toString`.
כתבו במחלקה `Car` פעולה better המקבלת כפרמטר מכונית אחרת ומחזירה `true` אם המכונית שעליה מופעלת הפעולה "טובה" יותר מאשר המכונית האחרת, ואם לא – הפעולה תחזיר `false`.
מכונית תיחשב לטובה יותר ממכונית אחרת אם הדירוג שלה גבוה יותר (לדוגמה, דירוג B גבוה יותר מדירוג A). אם לשתיהן אותו הדירוג, אז מכונית אוטומטית תיחשב טובה יותר מידנית.
כותרת הפעולה:
public boolean better (Car other)public bool Better (Car other)לכל אחת מדרגות הרכב מוגדר מחיר ליום:
•דרגה A – 100 ₪
•דרגה B – 150 ₪
•דרגה C – 180 ₪
•דרגה D – 240 ₪
כתבו במחלקה `Rent` את הפעולה `getPrice` המחשבת את המחיר הכולל של תקופת ההשכרה.
כותרת הפעולה:
public int getPrice()public int GetPrice()כתבו פעולה חיצונית המקבלת מערך השכרות ומערך שמות של לקוחות החברה.
הפעולה תדפיס עבור כל לקוח את הפרטים של כל ההשכרות שלו ואת הסכום הכולל שהלקוח שילם.
כותרת הפעולה:
public static void clientsReport(Rent[] rents, String[] names)public static void ClientsReport(Rent[] rents, string[] names)◂ פתרון מלא לשאלה 10
סעיף א
אם הדירוגים שונים מחזירים `this.type > other.type`; אם שווים - true רק כאשר this אוטומטית (`!isManual`) ו-other ידנית.
הרעיון: הדירוג הוא תו, ותווים מושווים לפי הקוד שלהם: . לכן "דירוג גבוה יותר" הוא פשוט תו גדול יותר.
1. אם הדירוגים שונים - ההחלטה לפי הדירוג בלבד: מחזירים `this.type > other.type`.
2. אם הדירוגים שווים - המכונית הנוכחית טובה יותר רק אם היא אוטומטית (`isManual == false`) והאחרת ידנית (`isManual == true`). בכל מקרה אחר (שתיהן ידניות, שתיהן אוטומטיות, או הנוכחית ידנית והאחרת אוטומטית) היא אינה "טובה יותר", ומוחזר false.
הפעולה נכתבת בתוך המחלקה Car, ולכן מותר לגשת ישירות לתכונות הפרטיות `type` ו-`isManual` גם של `other` (הרשאת private היא ברמת המחלקה).
public boolean better(Car other)
{
if (this.type != other.type)
return this.type > other.type; // 'D' > 'C' > 'B' > 'A'
// אותו דירוג: עדיפה מכונית אוטומטית על פני ידנית
return !this.isManual && other.isManual;
}public bool Better(Car other)
{
if (this.type != other.type)
return this.type > other.type; // 'D' > 'C' > 'B' > 'A'
// אותו דירוג: עדיפה מכונית אוטומטית על פני ידנית
return !this.isManual && other.isManual;
}דוגמאות: מכונית B ידנית לעומת מכונית A אוטומטית - true (הדירוג קובע). מכונית B אוטומטית לעומת B ידנית - true. מכונית B ידנית לעומת B ידנית - false.
תשובה: הפעולה שלמעלה.
סעיף ב
מספר הימים = `pickDate.difference(returnDate)` (בערך מוחלט); המחיר ליום לפי `car.getType()` (A-100, B-150, C-180, D-240); מחזירים ימים × מחיר ליום.
הרעיון: המחיר הכולל = מספר ימי ההשכרה × המחיר ליום לפי דרגת המכונית.
1. מספר הימים: מזמנים את הפעולה הנתונה `difference` על תאריך הקבלה, עם תאריך ההחזרה כפרמטר: `pickDate.difference(returnDate)`. השאלה אינה מגדירה את סימן ההפרש, ולכן לוקחים את הערך המוחלט כדי לקבל מספר ימים חיובי.
2. המחיר ליום: הדרגה שמורה במכונית המושכרת. התכונה `type` פרטית במחלקה Car, ולכן ניגשים אליה דרך `car.getType()`. בוחרים את המחיר בשרשרת if-else: A - 100, B - 150, C - 180, D - 240.
3. מחזירים את המכפלה.
דוגמה: השכרה של מכונית בדרגה B לתקופה של 3 ימים: ₪. השכרה של מכונית בדרגה D ל-2 ימים: ₪.
הערה ל-C#: פעולת ה-Get של התכונה type נקראת `GetType`, ושם זה קיים כבר ב-object. לכן במחלקה Car היא מוגדרת עם המילה `new`: `public new char GetType() { return type; }`, וכך `car.GetType()` מחזירה את הדירוג.
public int getPrice()
{
int days = this.pickDate.difference(this.returnDate);
if (days < 0)
days = -days; // מספר הימים כערך חיובי
int pricePerDay;
char type = this.car.getType();
if (type == 'A')
pricePerDay = 100;
else if (type == 'B')
pricePerDay = 150;
else if (type == 'C')
pricePerDay = 180;
else
pricePerDay = 240; // 'D'
return days * pricePerDay;
}public int GetPrice()
{
int days = this.pickDate.Difference(this.returnDate);
if (days < 0)
days = -days; // מספר הימים כערך חיובי
int pricePerDay;
char type = this.car.GetType();
if (type == 'A')
pricePerDay = 100;
else if (type == 'B')
pricePerDay = 150;
else if (type == 'C')
pricePerDay = 180;
else
pricePerDay = 240; // 'D'
return days * pricePerDay;
}תשובה: הפעולה שלמעלה.
סעיף ג
לולאה על השמות; לכל שם - לולאה על ההשכרות: אם `rents[j].getName()` שווה לשם, מדפיסים `rents[j].toString()` וצוברים `getPrice()`; אחרי הלולאה הפנימית מדפיסים את הסכום.
הרעיון: לולאות מקוננות - החיצונית על הלקוחות, והפנימית על כל ההשכרות, כדי למצוא את ההשכרות של כל לקוח.
1. לכל לקוח `names[i]` מדפיסים את שמו ומאפסים צובר `sum` (הצובר מאופס לכל לקוח מחדש).
2. עוברים על כל ההשכרות. אם שם הלקוח בהשכרה (`getName()`) שווה ל-`names[i]` (השוואה ב-`equals`):
•מדפיסים את פרטי ההשכרה בעזרת `toString()` הנתונה;
•מוסיפים לצובר את המחיר `getPrice()` מסעיף ב'.
3. אחרי שעברנו על כל ההשכרות מדפיסים את הסכום הכולל של הלקוח.
סיבוכיות: , כאשר מספר הלקוחות ו- מספר ההשכרות.
public static void clientsReport(Rent[] rents, String[] names)
{
for (int i = 0; i < names.length; i++)
{
System.out.println("Client: " + names[i]);
int sum = 0;
for (int j = 0; j < rents.length; j++)
{
if (rents[j].getName().equals(names[i]))
{
System.out.println(rents[j].toString());
sum += rents[j].getPrice();
}
}
System.out.println("Total: " + sum);
}
}public static void ClientsReport(Rent[] rents, string[] names)
{
for (int i = 0; i < names.Length; i++)
{
Console.WriteLine("Client: " + names[i]);
int sum = 0;
for (int j = 0; j < rents.Length; j++)
{
if (rents[j].GetName() == names[i])
{
Console.WriteLine(rents[j].ToString());
sum += rents[j].GetPrice();
}
}
Console.WriteLine("Total: " + sum);
}
}דוגמה: אם ל-Dana שתי השכרות במחירים 450 ו-500, יודפסו פרטי שתי ההשכרות ואחריהם `Total: 950`.
תשובה: הפעולה שלמעלה.
שאלה 11 · תא בודד במערך דו-ממדי
נתונות הגדרות הבאות:
•תא במערך דו-ממדי הנמצא בשורה `row` ובעמודה `col` נקרא "תא בודד" אם בשורה `row` ובעמודה `col` __אין אף תא__ עם ערך זהה לו.
•ערך הנמצא ב"תא בודד" נקרא "ערך בדידות".
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `mat`, מספר שורה `row` ומספר עמודה `col`. אם התא `mat[row][col]` הוא "תא בודד" הפעולה תחזיר `true`,
ולא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static boolean isLone (int[][] mat, int row, int col)public static bool IsLone (int[,] mat, int row, int col)כתבו פעולה המקבלת מערך דו-ממדי המכיל מספרים שלמים חיוביים (גדולים מ- 0).
הפעולה תחזיר "ערך בדידות" הגדול ביותר. אם במערך אין אף "תא בודד", הפעולה תחזיר `-1`.
כותרת הפעולה:
public static int maxLone (int[][] mat)public static int MaxLone (int[,] mat)מהן הסיבוכיות של הפעולות `isLone` ו- `maxLone`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
משווים את `mat[row][col]` לכל תא אחר בשורה row ולכל תא אחר בעמודה col; אם נמצא ערך זהה - false, אחרת true. סיבוכיות .
הרעיון: שומרים את הערך `val = mat[row][col]` ובודקים שתי לולאות נפרדות:
1. השורה row: עוברים על כל העמודות `j`. אם `j != col` (לא התא עצמו) והערך `mat[row][j]` שווה ל-`val` - נמצא תא זהה, ומחזירים false.
2. העמודה col: עוברים על כל השורות `i`. אם `i != row` והערך `mat[i][col]` שווה ל-`val` - מחזירים false.
3. אם שתי הלולאות הסתיימו - אין תא זהה בשורה או בעמודה, והתא "בודד": מחזירים true.
התנאים `j != col` ו-`i != row` נחוצים, כי אחרת התא היה "מוצא" את עצמו ואף תא לא היה בודד.
public static boolean isLone(int[][] mat, int row, int col)
{
int val = mat[row][col];
// בדיקת השורה row (כל העמודות חוץ מ-col)
for (int j = 0; j < mat[row].length; j++)
{
if (j != col && mat[row][j] == val)
return false;
}
// בדיקת העמודה col (כל השורות חוץ מ-row)
for (int i = 0; i < mat.length; i++)
{
if (i != row && mat[i][col] == val)
return false;
}
return true;
}public static bool IsLone(int[,] mat, int row, int col)
{
int val = mat[row, col];
// בדיקת השורה row (כל העמודות חוץ מ-col)
for (int j = 0; j < mat.GetLength(1); j++)
{
if (j != col && mat[row, j] == val)
return false;
}
// בדיקת העמודה col (כל השורות חוץ מ-row)
for (int i = 0; i < mat.GetLength(0); i++)
{
if (i != row && mat[i, col] == val)
return false;
}
return true;
}דוגמה: במערך
1 2 3
4 1 6
7 8 6התא `mat[0][1]` (הערך 2) בודד - true. התא `mat[1][2]` (הערך 6) אינו בודד, כי גם `mat[2][2]` הוא 6 - false.
תשובה: הפעולה שלמעלה.
סעיף ב
max = -1; לכל תא (i, j) שעבורו `isLone(mat, i, j)` מחזירה true ו-`mat[i][j] > max` - מעדכנים; מחזירים max.
הרעיון: חיפוש מקסימום רק בין התאים הבודדים.
1. מאתחלים `max = -1`. מכיוון שכל הערכים חיוביים, כל "ערך בדידות" גדול מ-, ואם לא יימצא אף תא בודד יוחזר כנדרש.
2. עוברים על כל התאים בשתי לולאות מקוננות. לכל תא בודקים בעזרת הפעולה מסעיף א' אם הוא "תא בודד", ואם כן ואם ערכו גדול מ-`max` - מעדכנים.
3. מחזירים את `max`.
public static int maxLone(int[][] mat)
{
int max = -1; // אם לא יימצא "תא בודד" יוחזר -1
for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat[i].length; j++)
{
if (isLone(mat, i, j) && mat[i][j] > max)
max = mat[i][j];
}
}
return max;
}public static int MaxLone(int[,] mat)
{
int max = -1; // אם לא יימצא "תא בודד" יוחזר -1
for (int i = 0; i < mat.GetLength(0); i++)
{
for (int j = 0; j < mat.GetLength(1); j++)
{
if (IsLone(mat, i, j) && mat[i, j] > max)
max = mat[i, j];
}
}
return max;
}דוגמה: במערך מסעיף א' התאים הבודדים מכילים את הערכים 1, 2, 3, 4, 1, 7, 8 (שני התאים עם 6 אינם בודדים), ולכן יוחזר 8. במערך `{{5,5},{5,5}}` אין תא בודד, ויוחזר .
תשובה: הפעולה שלמעלה.
סעיף ג
עבור מערך של n שורות ו-m עמודות: isLone - ; maxLone - .
נסמן - מספר השורות, - מספר העמודות.
1. isLone: לולאה אחת על השורה ( תאים) ולולאה אחת על העמודה ( תאים), זו אחר זו. סך הכול .
2. maxLone: עוברת על כל התאים, ולכל תא מזמנת את isLone שעולה . סך הכול . עבור מערך ריבועי זה .
תשובה: isLone - ; maxLone - .
שאלה 12 · רקורסיה: תחילית ותת-מחרוזת
נתונות פעולות רקורסיביות `mystery` ו- `secret`:
public static boolean mystery(String s1, String s2)
{
if(s2.length()>s1.length()) return false;
if(s2.length()==0) return true;
if(s1.charAt(0)!=s2.charAt(0)) return false;
return mystery(s1.substring(1), s2.substring(1));
}
public static boolean secret (String s1, String s2)
{
if(s2.length()==0) return true;
if(s1.length()<s2.length()) return false;
return mystery(s1,s2) || secret(s1.substring(1), s2);
}public static bool Mystery(string s1, string s2)
{
if(s2.Length > s1.Length) return false;
if(s2.Length == 0) return true;
if(s1[0]!=s2[0]) return false;
return Mystery(s1.Substring(1), s2.Substring(1));
}
public static bool Secret (string s1, string s2)
{
if(s2.Length == 0) return true;
if(s1.Length < s2.Length) return false;
return Mystery(s1,s2) || Secret(s1.Substring(1), s2);
}עקבו אחרי זימון `mystery("HELLO","HELP")` ורשמו את תוצאת הזימון.
מה מבצעת הפעולה `mystery(s1,s2)` עבור שתי מחרוזות `s1,s2`?
עקבו אחרי זימון `secret ("MYJOBTEST" , "JOB")` ורשמו את תוצאות הזימון.
מה מבצעת הפעולה `secret(s1, s2)` עבור שתי מחרוזות `s1,s2`?
כתבו את הפעולה `secret` המבצעת אותה משימה בצורה לא רקורסיבית.
◂ פתרון מלא לשאלה 12
סעיף א
false: אחרי שלושה זימונים רקורסיביים מגיעים ל-`mystery("LO","P")`, ושם .
בכל זימון בודקים לפי הסדר: אם s2 ארוכה מ-s1 - false; אם s2 ריקה - true; אם התווים הראשונים שונים - false; אחרת זימון רקורסיבי בלי התו הראשון של כל מחרוזת.
הערך false חוזר מזימון 4 דרך כל הזימונים הקודמים.
תשובה: `mystery("HELLO","HELP")` מחזירה false.
סעיף ב
מחזירה true אם s2 היא תחילית של s1 (s1 מתחילה ב-s2), ואחרת false.
הפעולה משווה את s2 ל-s1 תו אחר תו מההתחלה. היא מחזירה true כאשר כל התווים של s2 נגמרו בלי אי-התאמה, ו-false אם נמצא תו שונה או ש-s2 ארוכה מ-s1.
תשובה: הפעולה בודקת אם s2 היא תחילית של s1, כלומר אם s1 מתחילה במחרוזת s2 (מחרוזת ריקה היא תחילית של כל מחרוזת).
סעיף ג
true: secret("MYJOBTEST","JOB") → secret("YJOBTEST","JOB") → secret("JOBTEST","JOB"), ושם mystery מחזירה true.
בכל זימון של secret: אם s2 ריקה - true; אם s1 קצרה מ-s2 - false; אחרת בודקים אם s1 מתחילה ב-s2 (mystery), ואם לא - ממשיכים רקורסיבית עם s1 בלי התו הראשון.
בזימון 3 הביטוי `mystery(s1,s2) || ...` מקבל true כבר מהחלק הראשון, ולכן החלק השני אינו מחושב. הערך true חוזר לזימונים 2 ו-1.
תשובה: `secret("MYJOBTEST","JOB")` מחזירה true.
סעיף ד
מחזירה true אם s2 היא תת-מחרוזת (רצף תווים צמוד) של s1 במקום כלשהו, ואחרת false.
secret בודקת אם s1 מתחילה ב-s2; אם לא - היא מוחקת את התו הראשון של s1 ובודקת שוב. כך היא בודקת את כל מקומות ההתחלה האפשריים ב-s1.
תשובה: הפעולה בודקת אם s2 מופיעה כתת-מחרוזת (רצף צמוד של תווים) במקום כלשהו בתוך s1.
סעיף ה
לולאה על כל מקום התחלה i ב-s1 (כל עוד ); לולאה פנימית משווה תו אחר תו; אם כל התווים של s2 תאמו - true; בסוף - false.
הרעיון: במקום רקורסיה שמקצרת את s1, עוברים בלולאה על כל מקומות ההתחלה `i` ב-s1 שמהם s2 עוד יכולה להיכנס עד סוף s1, כלומר `i + s2.length() <= s1.length()`.
1. לכל מקום `i`, לולאה פנימית משווה את `s1.charAt(i + k)` ל-`s2.charAt(k)`, כל עוד התווים שווים (זה התפקיד של mystery).
2. אם `k` הגיע לאורך של s2 - כל התווים תאמו, ומחזירים true.
3. אם אף מקום התחלה לא התאים - מחזירים false.
מקרי הקצה זהים לפעולה הרקורסיבית: אם s2 ריקה, כבר עבור הלולאה הפנימית לא מתבצעת, שווה לאורך s2, ומוחזר true; אם s1 קצרה מ-s2, הלולאה החיצונית לא מתבצעת ומוחזר false.
(אפשר גם בשורה אחת: `return s1.contains(s2);` ב-Java, או `return s1.Contains(s2);` ב-C#.)
public static boolean secret(String s1, String s2)
{
// מנסים כל מקום התחלה i ב-s1 שממנו s2 עוד יכולה להיכנס
for (int i = 0; i + s2.length() <= s1.length(); i++)
{
int k = 0;
while (k < s2.length() && s1.charAt(i + k) == s2.charAt(k))
k++;
if (k == s2.length()) // כל התווים של s2 תאמו
return true;
}
return false;
}public static bool Secret(string s1, string s2)
{
// מנסים כל מקום התחלה i ב-s1 שממנו s2 עוד יכולה להיכנס
for (int i = 0; i + s2.Length <= s1.Length; i++)
{
int k = 0;
while (k < s2.Length && s1[i + k] == s2[k])
k++;
if (k == s2.Length) // כל התווים של s2 תאמו
return true;
}
return false;
}תשובה: הפעולה שלמעלה.