מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2026 מועד א'
הנדסת תוכנה · סמל 97104 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2026 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב-C# (עמוד 2)
מבחן ב-Java (עמוד 12)
בכל מבחן 10 שאלות.
שאלות 1–4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה – 12 נקודות.
שאלות 5–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
שאלות 8–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 17 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
מילון עזר.
שאלה 1 · מחרוזת ייחודית: בדיקת תווים כפולים
מחרוזת נקראת "מחרוזת ייחודית" אם כל תו המופיע בה מופיע פעם אחת בלבד (כלומר, אין בה תווים כפולים).
•המחרוזת `"abc12!"` היא מחרוזת ייחודית;
•המחרוזת `"aA12"` היא מחרוזת ייחודית (האות `'a'` שונה מ-`'A'`);
•המחרוזת `"apple1"` אינה ייחודית (התו `'p'` מופיע פעמיים);
•המחרוזת `"121"` אינה ייחודית (התו `'1'` מופיע פעמיים).
כתבו פעולה המקבלת מחרוזת ובודקת אם היא "ייחודית". אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.
כתבו קטע קוד הקולט סדרת מחרוזות עד אשר נקלטת מחרוזת המתחילה באות `'R'`. בסיום יש להדפיס כמה מחרוזות מתוך המחרוזות שנקלטו (לא כולל מחרוזת הסיום) היו "מחרוזות ייחודיות".
◂ פתרון מלא לשאלה 1
סעיף א
פעולה עם שתי לולאות מקוננות שמשווה כל זוג תווים (`i < j`); אם נמצא זוג שווה מוחזר `false`, ואחרת `true`.
הרעיון: מחרוזת אינה ייחודית אם ורק אם יש בה שני מקומות שונים שבהם אותו תו. לכן משווים כל תו לכל התווים שאחריו:
1. הלולאה החיצונית בוחרת תו במקום `i` (מ- עד האורך פחות ).
2. הלולאה הפנימית עוברת על כל המקומות `j` שאחרי `i` ומשווה את התווים.
3. ברגע שנמצאו שני תווים שווים – המחרוזת אינה ייחודית, ומחזירים `false` מיד.
4. אם הלולאות הסתיימו בלי למצוא זוג שווה – כל תו מופיע פעם אחת, ומחזירים `true`.
ההשוואה בין תווים מבחינה בין אות גדולה לקטנה (`'a'` שונה מ-`'A'`), בדיוק כנדרש. מחרוזת ריקה או בת תו אחד היא ייחודית (אין בה זוג תווים). סיבוכיות: עבור מחרוזת באורך .
public static bool IsUnique(string s)
{
for (int i = 0; i < s.Length - 1; i++)
{
for (int j = i + 1; j < s.Length; j++)
{
if (s[i] == s[j])
return false; // נמצא תו שמופיע פעמיים
}
}
return true;
}public static boolean isUnique(String s)
{
for (int i = 0; i < s.length() - 1; i++)
{
for (int j = i + 1; j < s.length(); j++)
{
if (s.charAt(i) == s.charAt(j))
return false; // נמצא תו שמופיע פעמיים
}
}
return true;
}בדיקה בדוגמאות: `"abc12!"` ו-`"aA12"` – אין זוג תווים שווים, מוחזר `true`; ב-`"apple1"` נמצא `s[1] == s[2]` (`'p'`), מוחזר `false`; ב-`"121"` נמצא `s[0] == s[2]` (`'1'`), מוחזר `false`.
תשובה: הפעולה `IsUnique` (ב-Java: `isUnique`) שלמעלה.
סעיף ב
לולאת `while` עם קליטה לפני הלולאה ובסוף כל סיבוב; כל עוד התו הראשון אינו `'R'` – אם המחרוזת ייחודית (סעיף א) מגדילים מונה; בסוף מדפיסים את המונה.
הרעיון: מחרוזת הסיום אינה נספרת, לכן צריך לבדוק את תנאי העצירה לפני שבודקים את המחרוזת. מתאימה לולאת `while` עם "קליטה מקדימה":
1. מאתחלים מונה `count = 0` וקולטים את המחרוזת הראשונה.
2. כל עוד התו הראשון של המחרוזת (מקום ) אינו `'R'`, המחרוזת היא חלק מהנתונים: בודקים אותה בעזרת הפעולה מסעיף א, ואם היא ייחודית – מגדילים את `count`.
3. בסוף כל סיבוב קולטים את המחרוזת הבאה, והתנאי נבדק שוב.
4. כשנקלטת מחרוזת שמתחילה ב-`'R'` הלולאה מסתיימת בלי לבדוק אותה, ומדפיסים את `count`.
(מניחים שכל מחרוזת שנקלטת אינה ריקה, כך שיש לה תו במקום .)
int count = 0;
string str = Console.ReadLine();
while (str[0] != 'R')
{
if (IsUnique(str))
count++;
str = Console.ReadLine();
}
Console.WriteLine(count);int count = 0;
String str = in.next();
while (str.charAt(0) != 'R')
{
if (isUnique(str))
count++;
str = in.next();
}
System.out.println(count);דוגמה: עבור הקלט `abc`, `apple`, `aA12`, `121`, `xyz`, `Rest` – המחרוזות הייחודיות הן `abc`, `aA12`, `xyz`, ומחרוזת הסיום `Rest` אינה נבדקת. יודפס `3`.
תשובה: קטע הקוד שלמעלה.
שאלה 2 · ספרה מובילה ושלשות סמוכות במערך
"ספרה מובילה" של מספר שלם חיובי היא הספרה השמאלית ביותר שלו.
לדוגמה: הספרה המובילה של 452 היא 4, הספרה המובילה של 19 היא 1, הספרה המובילה של 9 היא 9.
כתבו פעולה המקבלת מספר שלם חיובי ומחזירה את הספרה המובילה שלו.
רצף של שלושה מספרים סמוכים במערך ייקרא "שלשת ראש זהה" אם בכל שלושת המספרים ברצף הספרה המובילה זהה.
במערך `int[] a = {58, 612, 61, 6929, 13, 12, 21, 22, 239}`
יש שתי "שלשות ראש זהה".
כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים ומחזירה את כמות "שלשות ראש זהה".
◂ פתרון מלא לשאלה 2
סעיף א
מחלקים את המספר ב-10 (חלוקה בשלמים) כל עוד הוא לפחות 10; מה שנשאר הוא הספרה המובילה.
הרעיון: חלוקה בשלמים ב- מוחקת את ספרת האחדות. אם נמחק שוב ושוב את הספרה הימנית, בסוף תישאר רק הספרה השמאלית ביותר.
1. כל עוד `num >= 10` (יש במספר לפחות שתי ספרות) – מבצעים `num = num / 10`.
2. כשהלולאה נגמרת, `num` הוא מספר חד-ספרתי – זו הספרה המובילה, ומחזירים אותו.
דוגמה: , מוחזר . עבור : . עבור הלולאה לא מתבצעת כלל ומוחזר . סיבוכיות: , כאשר מספר הספרות.
public static int LeadingDigit(int num)
{
while (num >= 10) // כל עוד יש יותר מספרה אחת
num = num / 10; // מוחקים את ספרת האחדות
return num;
}public static int leadingDigit(int num)
{
while (num >= 10) // כל עוד יש יותר מספרה אחת
num = num / 10; // מוחקים את ספרת האחדות
return num;
}תשובה: הפעולה `LeadingDigit` (ב-Java: `leadingDigit`) שלמעלה.
סעיף ב
עוברים על כל מקום התחלה `i` מ-0 עד `Length-3`, ואם לשלושת האיברים `arr[i]`, `arr[i+1]`, `arr[i+2]` אותה ספרה מובילה (לפי סעיף א) מגדילים מונה; מחזירים את המונה.
הרעיון: כל "שלשת ראש זהה" נקבעת לפי המקום `i` של האיבר הראשון שלה: האיברים `arr[i]`, `arr[i+1]`, `arr[i+2]`. לכן עוברים על כל מקומות ההתחלה האפשריים ובודקים כל שלשה:
1. מקום ההתחלה האחרון האפשרי הוא `Length - 3` (כדי ש-`i+2` יהיה בתוך המערך), ולכן הלולאה רצה כל עוד `i < Length - 2`.
2. מחשבים בעזרת הפעולה מסעיף א את הספרה המובילה `d` של `arr[i]`, ובודקים שגם ל-`arr[i+1]` ול-`arr[i+2]` ספרה מובילה `d`.
3. אם כן – מגדילים את המונה. בסוף מחזירים אותו.
שלשות יכולות לחפוף: למשל ב-`{1, 12, 13, 145}` יש שתי שלשות (מהמקומות ו-). במערך עם פחות משלושה איברים הלולאה לא מתבצעת ומוחזר .
בדיקה בדוגמה: הספרות המובילות של `a` הן . השלשות המתאימות מתחילות במקום (`612, 61, 6929`) ובמקום (`21, 22, 239`), ולכן מוחזר .
public static int CountSameHead(int[] arr)
{
int count = 0;
for (int i = 0; i < arr.Length - 2; i++)
{
int d = LeadingDigit(arr[i]);
if (LeadingDigit(arr[i + 1]) == d && LeadingDigit(arr[i + 2]) == d)
count++; // arr[i], arr[i+1], arr[i+2] - שלשת ראש זהה
}
return count;
}public static int countSameHead(int[] arr)
{
int count = 0;
for (int i = 0; i < arr.length - 2; i++)
{
int d = leadingDigit(arr[i]);
if (leadingDigit(arr[i + 1]) == d && leadingDigit(arr[i + 2]) == d)
count++; // arr[i], arr[i+1], arr[i+2] - שלשת ראש זהה
}
return count;
}תשובה: הפעולה `CountSameHead` (ב-Java: `countSameHead`) שלמעלה; עבור המערך שבדוגמה היא מחזירה .
שאלה 3 · מעקב: סימנים מתחלפים בין איברים סמוכים
נתונה פעולה הבאה:
public static bool Secret(int[] arr) {
int right = arr.Length - 1;
int left = right - 1;
int count = 0;
while (left >= 0) {
if (arr[left] * arr[right] < 0) {
count++;
}
right--;
left--;
}
if (count == arr.Length - 1) {
return true;
}
return false;
}public static boolean secret(int[] arr) {
int right = arr.length - 1;
int left = right - 1;
int count = 0;
while (left >= 0) {
if (arr[left] * arr[right] < 0) {
count++;
}
right--;
left--;
}
if (count == arr.length - 1) {
return true;
}
return false;
}נתון המערך `int[] arr={1, -5, 2, -8, 4, 10, -3}`
עקבו בעזרת טבלת מעקב אחר הזימון `Secret (arr)`, ורשמו מה תחזיר הפעולה.
האם אפשר לשנות את סדר האיברים במערך `arr` כך שזימון `Secret(arr)` יחזיר תוצאה שונה מהתוצאה שהתקבלה בסעיף א1? הסבירו את תשובתכם.
מה מבצעת הפעולה `Secret` באופן כללי?
נתונה טענה הבאה: אם הפעולה `Secret` החזירה `true` עבור מערך מסוים, הרי שבהכרח אין במערך זה את המספר 0.
קבעו אם הטענה הבאה נכונה או לא נכונה, ונמקו את קביעתכם.
◂ פתרון מלא לשאלה 3
סעיף א
`count = 5`, ו-`arr.Length - 1 = 6`, ולכן הפעולה מחזירה `false`.
בהתחלה: `right = 7 - 1 = 6`, `left = 5`, `count = 0`. בכל סיבוב בודקים את זוג האיברים הסמוכים `arr[left]`, `arr[right]`, וזזים זוג אחד שמאלה. הלולאה נעצרת כש-`left` נעשה .
אחרי הסיבוב השישי `left = -1` והלולאה מסתיימת. בודקים: `count == arr.Length - 1`, כלומר ? לא. לכן מוחזר `false` (הזוג – שני חיוביים – "שובר" את התחלופה).
תשובה: הפעולה מחזירה `false`.
כן. למשל `{1, -5, 2, -8, 4, -3, 10}` – כל זוג סמוך בסימנים הפוכים, `count = 6`, ומוחזר `true`.
הפעולה מחזירה `true` רק אם כל זוגות האיברים הסמוכים הם בעלי סימנים הפוכים, כלומר החיוביים והשליליים מתחלפים לסירוגין.
1. במערך יש מספרים חיוביים () ו- שליליים (), ואין אפסים.
2. כדי לסדר איברים לסירוגין צריך מסוג אחד ו- מהסוג השני, כשהסוג הגדול בקצוות: חיובי, שלילי, חיובי, שלילי, חיובי, שלילי, חיובי. זה בדיוק המצב כאן.
3. לדוגמה: `{1, -5, 2, -8, 4, -3, 10}`. ששת הזוגות הסמוכים: , , , , , – בכולם המכפלה שלילית, ולכן `count = 6 = arr.Length - 1` ומוחזר `true`.
תשובה: כן. בסידור `{1, -5, 2, -8, 4, -3, 10}` הפעולה תחזיר `true` (שונה מ-`false` שהתקבל בסעיף א1).
סעיף ב
מחזירה `true` אם כל שני איברים סמוכים במערך הם בעלי סימנים הפוכים (חיובי ושלילי לסירוגין, בלי אפסים), ואחרת `false`.
1. המשתנים `left` ו-`right` מצביעים תמיד על שני איברים סמוכים (`left = right - 1`), והלולאה עוברת על כל הזוגות הסמוכים במערך, מהסוף להתחלה.
2. המכפלה `arr[left] * arr[right]` שלילית אם ורק אם לאחד האיברים סימן חיובי ולשני שלילי (אם אחד מהם המכפלה , ואינה שלילית).
3. `count` סופר כמה זוגות סמוכים הם בעלי סימנים הפוכים, ובסוף בודקים אם כל הזוגות כאלה.
תשובה: הפעולה בודקת אם סימני האיברים במערך מתחלפים – כל איבר חיובי צמוד רק לשליליים ולהפך (ואין אפסים). אם כן היא מחזירה `true`, אחרת `false`.
סעיף ג
עבור מערך עם שני איברים לפחות הטענה נכונה (זוג שיש בו 0 נותן מכפלה 0, לא שלילית). אבל באופן מוחלט היא אינה נכונה: עבור המערך `{0}` מוחזר `true` (`count = 0 = Length - 1`).
1. מערך עם שני איברים או יותר: נניח שיש במערך במקום כלשהו. ל- יש לפחות שכן אחד, ובזוג הזה המכפלה היא , שאינה קטנה מ-. לכן הזוג הזה לא נספר, `count` קטן מ-, והפעולה מחזירה `false`. כלומר, אם הוחזר `true` – אין במערך . במקרה הזה הטענה נכונה.
2. מערך עם איבר אחד: `right = 0`, `left = -1`, והלולאה לא מתבצעת כלל. אז `count = 0` וגם `arr.Length - 1 = 0`, ולכן מוחזר `true` – בלי קשר לערך האיבר. עבור `{0}` הפעולה מחזירה `true` למרות שיש במערך .
לכן הטענה, כפי שהיא מנוסחת ("בהכרח"), אינה נכונה: המערך `{0}` הוא דוגמה נגדית. היא נכונה רק למערכים בני שני איברים לפחות.
תשובה: הטענה אינה נכונה באופן כללי – דוגמה נגדית: `Secret({0})` מחזירה `true`. עבור מערכים בני שני איברים או יותר הטענה נכונה, כי זוג סמוך שיש בו נותן מכפלה ואינו נספר.
שאלה 4 · מחלקת טיסה: סכום נוסעים וטיסות מתאימות
נתונה המחלקה `Flight` המייצגת טיסה. למחלקה כמה תכונות:
•מספר הטיסה – `int flightNum`;
•יעד הטיסה – `string destination`; (ב-Java: `String destination`)
•מספר הנוסעים הרשומים לטיסה – `int passengers`;
•קיבולת המטוס (מספר המקומות הכולל במטוס) – `int capacity`;
אפשר להניח כי במחלקה `Flight` קיימות כל הפעולות `Get`, `Set`.
כתבו פעולה חיצונית המקבלת מערך של טיסות `flights` (מערך של עצמים מסוג `Flight`) ושם של יעד `dest`. הפעולה תחזיר את מספר הנוסעים הכולל הרשומים לכל הטיסות ש-`dest` הוא היעד שלהן.
קבוצת תיירים המונה `num` אנשים מעוניינת לטוס ליעד `dest`. טיסה נחשבת "מתאימה" לקבוצה אם היעד שלה הוא היעד המבוקש, ויש בה מספיק מקומות פנויים לכל חברי הקבוצה.
כתבו פעולה חיצונית המקבלת מערך של טיסות, שם יעד ומספר תיירים. הפעולה תדפיס את מספרי הטיסות המתאימות לקבוצה.
◂ פתרון מלא לשאלה 4
סעיף א
עוברים על המערך, ולכל טיסה שהיעד שלה שווה ל-`dest` מוסיפים לסכום את מספר הנוסעים שלה; מחזירים את הסכום.
הרעיון: סכימה מותנית – עוברים על כל הטיסות ומצרפים לסכום רק את הטיסות ליעד המבוקש.
1. מאתחלים `sum = 0`.
2. לכל טיסה במערך משווים את היעד שלה (בעזרת `GetDestination`) ל-`dest`. ב-C# משווים מחרוזות עם `==`, וב-Java עם `equals` (האופרטור `==` ב-Java משווה הפניות ולא תוכן).
3. אם היעד מתאים – מוסיפים ל-`sum` את מספר הנוסעים (`GetPassengers`).
4. בסוף מחזירים את `sum` (אם אין אף טיסה ליעד – מוחזר ).
הפעולה חיצונית, ולכן ניגשים לתכונות רק דרך פעולות ה-`Get`. סיבוכיות: .
public static int TotalPassengers(Flight[] flights, string dest)
{
int sum = 0;
for (int i = 0; i < flights.Length; i++)
{
if (flights[i].GetDestination() == dest)
sum += flights[i].GetPassengers();
}
return sum;
}public static int totalPassengers(Flight[] flights, String dest)
{
int sum = 0;
for (int i = 0; i < flights.length; i++)
{
if (flights[i].getDestination().equals(dest))
sum += flights[i].getPassengers();
}
return sum;
}דוגמה: טיסות (Rome, נוסעים), (Paris, ), (Rome, ), (Rome, ). עבור `"Rome"` מוחזר .
תשובה: הפעולה `TotalPassengers` (ב-Java: `totalPassengers`) שלמעלה.
סעיף ב
לכל טיסה מחשבים מקומות פנויים `capacity - passengers`; אם היעד שווה ל-`dest` ומספר המקומות הפנויים לפחות `num` – מדפיסים את מספר הטיסה.
הרעיון: מספר המקומות הפנויים בטיסה הוא הקיבולת פחות מספר הנוסעים הרשומים. טיסה מתאימה אם מתקיימים שני התנאים יחד:
1. היעד שלה שווה ל-`dest`;
2. מספר המקומות הפנויים גדול או שווה ל-`num` (כל חברי הקבוצה נכנסים).
עוברים על כל הטיסות, ולכל טיסה שעומדת בשני התנאים מדפיסים את מספר הטיסה (`GetFlightNum`). סיבוכיות: .
public static void PrintSuitable(Flight[] flights, string dest, int num)
{
for (int i = 0; i < flights.Length; i++)
{
int free = flights[i].GetCapacity() - flights[i].GetPassengers(); // מקומות פנויים
if (flights[i].GetDestination() == dest && free >= num)
Console.WriteLine(flights[i].GetFlightNum());
}
}public static void printSuitable(Flight[] flights, String dest, int num)
{
for (int i = 0; i < flights.length; i++)
{
int free = flights[i].getCapacity() - flights[i].getPassengers(); // מקומות פנויים
if (flights[i].getDestination().equals(dest) && free >= num)
System.out.println(flights[i].getFlightNum());
}
}דוגמה: עם הטיסות מסעיף א (קיבולות , , , ), קבוצה של ל-`"Rome"`: בטיסה פנויים – מתאימה; בטיסה פנויים – לא; בטיסה פנויים – מתאימה. יודפסו ו-.
תשובה: הפעולה `PrintSuitable` (ב-Java: `printSuitable`) שלמעלה.
שאלה 5 · איברים פורצים במערך
נגדיר מספר במערך כ"איבר פורץ" אם הוא גדול ממש מכל האיברים המופיעים לפניו (משמאלו) במערך.
הערה: האיבר הראשון במערך (באינדקס 0) נחשב תמיד ל"איבר פורץ".
לדוגמה: עבור המערך `int[] arr = {7, 2, 9, 9, 15, 3}` האיברים הפורצים הם 7, 9, 15
כי 7 הוא הראשון, 9 גדול מ-7 ומ-2, 15 גדול מכל קודמיו.
כתבו פעולה בשם `IsBreakthrough` המקבלת מערך של מספרים שלמים `arr` ואינדקס `k`.
הפעולה תחזיר `true` אם האיבר במיקום `k` הוא "איבר פורץ", ואם לא – הפעולה תחזיר `false`.
כתבו פעולה בשם `AllBreakthroughs` המקבלת מערך של מספרים שלמים ומחזירה מערך חדש המכיל את כל האיברים הפורצים מתוך המערך המקורי, לפי סדר הופעתם.
נתון מערך `arr` בגודל `n`.
מהו האורך המינימלי האפשרי של המערך המוחזר מסעיף ב'? תנו דוגמה למערך קלט בגודל `n=4` שיקיים זאת.
מהו האורך המקסימלי האפשרי של המערך המוחזר מסעיף ב'? תנו דוגמה למערך קלט בגודל `n=4` שיקיים זאת.
◂ פתרון מלא לשאלה 5
סעיף א
עוברים על המקומות `0` עד `k-1`; אם יש איבר `>= arr[k]` מחזירים `false`, אחרת `true` (עבור `k = 0` הלולאה ריקה ומוחזר `true`).
הרעיון: `arr[k]` הוא איבר פורץ אם הוא גדול ממש מכל האיברים שלפניו. מספיק שיהיה לפניו איבר אחד גדול ממנו או שווה לו כדי שלא יהיה פורץ.
1. עוברים על המקומות `i` מ- עד `k-1`.
2. אם `arr[i] >= arr[k]` – מחזירים `false` מיד.
3. אם לא נמצא איבר כזה – מחזירים `true`.
עבור `k = 0` הלולאה לא מתבצעת ומוחזר `true`, בהתאם להערה שהאיבר הראשון תמיד פורץ. סיבוכיות: .
בדוגמה: עבור `k = 3` (`arr[3] = 9`) נמצא `arr[2] = 9 >= 9`, ולכן מוחזר `false` – ה-9 השני אינו פורץ.
public static bool IsBreakthrough(int[] arr, int k)
{
for (int i = 0; i < k; i++)
{
if (arr[i] >= arr[k])
return false; // יש לפניו איבר גדול ממנו או שווה לו
}
return true;
}public static boolean isBreakthrough(int[] arr, int k)
{
for (int i = 0; i < k; i++)
{
if (arr[i] >= arr[k])
return false; // יש לפניו איבר גדול ממנו או שווה לו
}
return true;
}תשובה: הפעולה `IsBreakthrough` (ב-Java: `isBreakthrough`) שלמעלה.
סעיף ב
מעבר ראשון סופר בעזרת `IsBreakthrough` כמה איברים פורצים יש; יוצרים מערך בגודל הזה; מעבר שני מעתיק אליו את האיברים הפורצים לפי הסדר.
הרעיון: את גודל המערך החדש צריך לדעת לפני שיוצרים אותו, לכן עובדים בשני מעברים:
1. מעבר ראשון – ספירה: לכל מקום `k` בודקים בעזרת `IsBreakthrough(arr, k)` אם האיבר פורץ, וסופרים ב-`count`.
2. יוצרים מערך `result` בגודל `count` בדיוק.
3. מעבר שני – מילוי: עוברים שוב על המקומות לפי הסדר; כל איבר פורץ מועתק למקום `j` במערך החדש, ו-`j` גדל ב-. כך נשמר סדר ההופעה.
4. מחזירים את `result`.
סיבוכיות: כל זימון של `IsBreakthrough` עולה , ולכן סך הכול .
public static int[] AllBreakthroughs(int[] arr)
{
// מעבר ראשון: כמה איברים פורצים יש?
int count = 0;
for (int k = 0; k < arr.Length; k++)
{
if (IsBreakthrough(arr, k))
count++;
}
// מעבר שני: העתקת האיברים הפורצים לפי הסדר
int[] result = new int[count];
int j = 0;
for (int k = 0; k < arr.Length; k++)
{
if (IsBreakthrough(arr, k))
{
result[j] = arr[k];
j++;
}
}
return result;
}public static int[] allBreakthroughs(int[] arr)
{
// מעבר ראשון: כמה איברים פורצים יש?
int count = 0;
for (int k = 0; k < arr.length; k++)
{
if (isBreakthrough(arr, k))
count++;
}
// מעבר שני: העתקת האיברים הפורצים לפי הסדר
int[] result = new int[count];
int j = 0;
for (int k = 0; k < arr.length; k++)
{
if (isBreakthrough(arr, k))
{
result[j] = arr[k];
j++;
}
}
return result;
}בדוגמה: עבור `{7, 2, 9, 9, 15, 3}` נספרים איברים פורצים (במקומות , , ), ומוחזר `{7, 9, 15}`.
תשובה: הפעולה `AllBreakthroughs` (ב-Java: `allBreakthroughs`) שלמעלה.
סעיף ג
האורך המינימלי הוא 1. דוגמה: `{9, 5, 3, 1}` (מוחזר `{9}`).
1. האיבר הראשון (מקום ) הוא תמיד איבר פורץ, ולכן במערך המוחזר יש לפחות איבר אחד (עבור ).
2. אפשר להגיע בדיוק ל-: אם האיבר הראשון הוא הגדול ביותר או שווה לכל השאר, אף איבר אחר אינו גדול ממנו ממש, ולכן אף איבר אחר אינו פורץ.
3. דוגמה עם : `{9, 5, 3, 1}` (סדר יורד) – מוחזר `{9}`. גם `{4, 4, 4, 4}` מתאים, כי "גדול ממש" אינו מתקיים בשוויון.
תשובה: האורך המינימלי הוא ; למשל `{9, 5, 3, 1}`.
האורך המקסימלי הוא `n`. דוגמה: `{1, 2, 3, 4}` (מוחזר `{1, 2, 3, 4}`).
1. המערך המוחזר מכיל רק איברים מתוך המערך המקורי, ולכן אורכו לכל היותר .
2. האורך הוא כאשר כל איבר פורץ, כלומר כל איבר גדול ממש מכל קודמיו – המערך ממוין בסדר עולה ממש.
3. דוגמה עם : `{1, 2, 3, 4}` – כל איבר גדול מכל מה שלפניו, ומוחזר `{1, 2, 3, 4}` באורך .
תשובה: האורך המקסימלי הוא ; למשל `{1, 2, 3, 4}`.
שאלה 6 · מחלקות תרומה ופרויקט: בנאי, סכום ומקסימום
לפניכם הגדרות של שתי מחלקות המייצגות מערכת לניהול פרויקטים של תרומות:
המחלקה `Donation` מייצגת תרומה בודדת ולה התכונות האלה:
•שם התורם – `string donorName`; (ב-Java: `String donorName`)
•סכום התרומה – `double amount`;
•סוג התרומה – `char type` (`'F'` עבור מזון, `'C'` עבור ביגוד, `'M'` עבור כסף).
המחלקה `CharityProject` מייצגת פרויקט צדקה. למחלקה התכונות האלה:
•מספר זיהוי של הפרויקט – `int projectID`;
•שם היישוב שבו נערך הפרויקט – `string location`; (ב-Java: `String location`)
•מערך תרומות `Donation[] donations`. המערך תמיד מלא באובייקטים מסוג `Donation` ואין בו תאי `null`.
בשתי המחלקות הוגדרו בנאים ופעולות `Get/Set` עבור כל התכונות.
כתבו בנאי (`Constructor`) למחלקה `Donation` המקבל ערכים עבור כל תכונותיה. הבנאי יבדוק את תקינות הפרמטרים:
•סכום התרומה (`amount`) חייב להיות חיובי ממש. אם לא, ייקבע ערך ברירת מחדל של 10.
•סוג התרומה (`type`) חייב להיות אחד מהתווים `'F'`, `'C'` או `'M'`. אם לא, ייקבע ערך ברירת מחדל של `'M'`.
כתבו במחלקה `CharityProject` פעולה פנימית בשם `GetTypeTotal` המקבלת תו המייצג סוג תרומה. הפעולה תחזיר את הסכום הכולל של כל התרומות מסוג זה הקיימות במערך התרומות של הפרויקט.
כתבו פעולה חיצונית המקבלת מערך של פרויקטים (אובייקטים מסוג `CharityProject`) ותו המייצג סוג תרומה. הפעולה תדפיס את שם היישוב (`location`) של הפרויקט שבו נאסף סכום הכסף הגבוה ביותר עבור סוג התרומה שהתקבל.
הנחה: כל יישוב מופיע במערך הפרויקטים פעם אחת לכל היותר.
◂ פתרון מלא לשאלה 6
סעיף א
בנאי שמציב את שם התורם; את `amount` מציב רק אם הוא גדול מ-0 (אחרת 10); את `type` מציב רק אם הוא `'F'`, `'C'` או `'M'` (אחרת `'M'`).
הרעיון: הבנאי מקבל שלושה פרמטרים, אחד לכל תכונה, ומציב כל אחד בתכונה המתאימה – אבל רק אחרי בדיקת תקינות:
1. שם התורם מוצב כמו שהוא (אין עליו דרישה).
2. סכום: אם `amount > 0` מציבים אותו; אחרת (אפס או שלילי) מציבים .
3. סוג: אם התו שווה לאחד משלושת התווים המותרים מציבים אותו; אחרת מציבים `'M'`.
המילה `this` מבחינה בין התכונה של העצם לבין הפרמטר שיש לו אותו שם.
public Donation(string donorName, double amount, char type)
{
this.donorName = donorName;
if (amount > 0)
this.amount = amount;
else
this.amount = 10; // ערך ברירת מחדל
if (type == 'F' || type == 'C' || type == 'M')
this.type = type;
else
this.type = 'M'; // ערך ברירת מחדל
}public Donation(String donorName, double amount, char type)
{
this.donorName = donorName;
if (amount > 0)
this.amount = amount;
else
this.amount = 10; // ערך ברירת מחדל
if (type == 'F' || type == 'C' || type == 'M')
this.type = type;
else
this.type = 'M'; // ערך ברירת מחדל
}דוגמה: `new Donation("Dana", -3, 'Z')` יוצר תרומה עם סכום וסוג `'M'`.
תשובה: הבנאי שלמעלה.
סעיף ב
עוברים על מערך `donations`, ולכל תרומה שהסוג שלה שווה לתו שהתקבל מוסיפים את סכומה; מחזירים את הסכום (`double`).
הרעיון: הפעולה פנימית, ולכן יש לה גישה ישירה למערך `donations` של הפרויקט. עבור התרומות (עצמים מסוג `Donation`) ניגשים לתכונות דרך פעולות ה-`Get`.
1. מאתחלים `sum = 0` (מסוג `double`, כי הסכומים ממשיים).
2. עוברים על כל התרומות במערך (המערך מלא ואין בו `null`, ולכן אין צורך לבדוק זאת).
3. אם סוג התרומה (`GetType`) שווה לתו שהתקבל – מוסיפים ל-`sum` את סכום התרומה (`GetAmount`).
4. מחזירים את `sum`. סיבוכיות: עבור תרומות.
public double GetTypeTotal(char type)
{
double sum = 0;
for (int i = 0; i < donations.Length; i++)
{
if (donations[i].GetType() == type)
sum += donations[i].GetAmount();
}
return sum;
}public double getTypeTotal(char type)
{
double sum = 0;
for (int i = 0; i < donations.length; i++)
{
if (donations[i].getType() == type)
sum += donations[i].getAmount();
}
return sum;
}הערה ל-C#: למחלקה `object` כבר יש פעולה בשם `GetType()`; לפי השאלה הגטר של התכונה `type` נקרא כך. אם רוצים להימנע מהתנגשות, אפשר לקרוא לגטר `GetDonationType()` ולהשתמש בו באותו אופן.
דוגמה: בפרויקט עם התרומות: מסוג `'M'`, מסוג `'F'` ו- מסוג `'M'`, הזימון `GetTypeTotal('M')` מחזיר .
תשובה: הפעולה `GetTypeTotal` (ב-Java: `getTypeTotal`) שלמעלה.
סעיף ג
חיפוש מקסימום: לכל פרויקט מחשבים `GetTypeTotal(type)` (סעיף ב), שומרים את מקום הפרויקט עם הסכום הגבוה ביותר, ובסוף מדפיסים את `GetLocation()` שלו.
הרעיון: זהו חיפוש מקסימום רגיל, כשהערך שמשווים לכל פרויקט הוא הסכום שנאסף בו עבור הסוג המבוקש – ואותו כבר יודעים לחשב בעזרת `GetTypeTotal` מסעיף ב.
1. אם המערך ריק – אין מה להדפיס, ויוצאים.
2. מתחילים מהפרויקט הראשון: `best = 0`, ו-`maxSum` הוא הסכום שלו.
3. עוברים על שאר הפרויקטים. לכל פרויקט מחשבים את הסכום עבור הסוג; אם הוא גדול מ-`maxSum` – מעדכנים את `maxSum` ואת `best`.
4. בסוף מדפיסים את שם היישוב של הפרויקט במקום `best` (בעזרת `GetLocation`, כי הפעולה חיצונית).
לפי ההנחה, כל יישוב מופיע פעם אחת, ולכן אין צורך לצרף סכומים של כמה פרויקטים באותו יישוב. אם כמה פרויקטים שווים בסכום המקסימלי, מודפס הראשון מביניהם. סיבוכיות: של מספר כל התרומות בכל הפרויקטים.
public static void PrintBestLocation(CharityProject[] projects, char type)
{
if (projects.Length == 0)
return; // אין פרויקטים
int best = 0; // מקום הפרויקט הטוב ביותר עד כה
double maxSum = projects[0].GetTypeTotal(type);
for (int i = 1; i < projects.Length; i++)
{
double sum = projects[i].GetTypeTotal(type);
if (sum > maxSum)
{
maxSum = sum;
best = i;
}
}
Console.WriteLine(projects[best].GetLocation());
}public static void printBestLocation(CharityProject[] projects, char type)
{
if (projects.length == 0)
return; // אין פרויקטים
int best = 0; // מקום הפרויקט הטוב ביותר עד כה
double maxSum = projects[0].getTypeTotal(type);
for (int i = 1; i < projects.length; i++)
{
double sum = projects[i].getTypeTotal(type);
if (sum > maxSum)
{
maxSum = sum;
best = i;
}
}
System.out.println(projects[best].getLocation());
}דוגמה: Haifa – תרומות כסף ; Eilat – תרומת כסף ; Ashdod – אין תרומות כסף (). עבור `'M'` יודפס `Eilat`.
תשובה: הפעולה `PrintBestLocation` (ב-Java: `printBestLocation`) שלמעלה.
שאלה 7 · מעקב: חפיפת סיפא ורישא של מחרוזות
לפניכם שתי פעולות `Secret` ו-`Sod`:
public static int Secret(string s, string t) {
int v = 0;
int n = s.Length;
int m = t.Length;
int len = (n < m) ? n : m;
for (int i = 1; i <= len; i++) {
string p1 = s.Substring(n - i);
string p2 = t.Substring(0, i);
if (p1 == p2) {
v = i;
}
}
return v;
}
public static bool Sod(string[] arr) {
for (int j = 0; j < arr.Length - 1; j++) {
(*) if (Secret(arr[j], arr[j + 1]) == 0) {
return false;
}
}
return true;
}public static int secret(String s, String t) {
int v = 0;
int n = s.length();
int m = t.length();
int len = (n < m) ? n : m;
for (int i = 1; i <= len; i++) {
String p1 = s.substring(n - i);
String p2 = t.substring(0, i);
if (p1.equals(p2)) {
v = i;
}
}
return v;
}
public static boolean sod(String[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
(*) if (secret(arr[j], arr[j + 1]) == 0) {
return false;
}
}
return true;
}עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `Secret("Windstorm", "stormy")`.
בטבלת המעקב יש להציג את ערכי המשתנים p1, p2, i, v בכל סיבוב (איטרציה) של הלולאה.
תנו דוגמה לזוג מחרוזות שונות שעבורן הפעולה תחזיר ערך 3.
מה מבצעת הפעולה `Secret` באופן כללי עבור שתי מחרוזות `s1, s2`?
נתון מערך:
`string[] arr = {"Basketball", "ballroom", "Roommate", "material"}`
עקבו אחרי זימון הפעולה `Sod(arr)` ורשמו מה תהיה תוצאת הזימון.
פקודת התנאי (*) השתנה לפקודה הבאה:
`if (Secret(arr[j], arr[j + 1]) !=3)`
תנו דוגמה למערך `arr` בגודל שישה תאים שעבורו זימון הפעולה `Sod(arr)` יחזיר ערך `true`.
◂ פתרון מלא לשאלה 7
סעיף א
הפעולה מחזירה 5 (`"storm"` הוא הסיפא של `"Windstorm"` והרישא של `"stormy"`).
ערכים התחלתיים: `n = 9` (אורך `"Windstorm"`), `m = 6` (אורך `"stormy"`), `len = 6`, `v = 0`.
בכל סיבוב `p1` הוא התווים האחרונים של `s` (מהמקום עד הסוף), ו-`p2` הוא התווים הראשונים של `t`.
אחרי הלולאה מסתיימת ומוחזר `v = 5`.
תשובה: `Secret("Windstorm", "stormy")` מחזירה .
למשל `Secret("Sunset", "setup")` מחזירה 3.
צריך ש- התווים האחרונים של המחרוזת הראשונה יהיו שווים ל- התווים הראשונים של השנייה, ושלא תהיה חפיפה ארוכה יותר (כי `v` שומר את ה- האחרון, כלומר הגדול ביותר, שבו יש שוויון).
דוגמה: `s = "Sunset"`, `t = "setup"` (`len = 5`):
•: `"t"` מול `"s"` – לא; : `"et"` מול `"se"` – לא;
•: `"set"` מול `"set"` – כן, `v = 3`;
•: `"nset"` מול `"setu"` – לא; : `"unset"` מול `"setup"` – לא.
מוחזר .
תשובה: `s = "Sunset"`, `t = "setup"`.
מחזירה את האורך של החפיפה הארוכה ביותר בין סוף `s1` לתחילת `s2` (הסיפא הארוכה ביותר של `s1` שהיא גם רישא של `s2`); אם אין חפיפה – 0.
1. לכל אורך מ- עד האורך של המחרוזת הקצרה, הפעולה משווה את התווים האחרונים של `s1` ל- התווים הראשונים של `s2`.
2. כשיש שוויון, `v` מקבל את . מאחר ש- עולה, בסוף `v` שווה ל- הגדול ביותר שבו היה שוויון.
3. אם לא היה שוויון באף אורך, `v` נשאר .
ההשוואה רגישה לאותיות גדולות וקטנות (`'R'` שונה מ-`'r'`).
תשובה: הפעולה מחזירה את אורך החלק הארוך ביותר שבו סוף המחרוזת `s1` זהה לתחילת המחרוזת `s2` ("כמה תווים אפשר להדביק בחפיפה"), ו- אם אין חפיפה כזאת.
סעיף ב
`Sod(arr)` מחזירה `false`: עבור `j = 1` החפיפה בין `"ballroom"` ל-`"Roommate"` היא 0 (`'R'` גדולה שונה מ-`'r'`).
`Sod` עוברת על זוגות סמוכים, ומחזירה `false` ברגע שלזוג כלשהו אין חפיפה (`Secret` מחזירה ). הלולאה רצה עבור .
פירוט עבור : הסיפות של `"ballroom"` מתחילות באותיות קטנות (`"m"`, `"om"`, `"oom"`, `"room"`, ...) והרישות של `"Roommate"` מתחילות ב-`'R'` גדולה (`"R"`, `"Ro"`, `"Roo"`, `"Room"`, ...). למשל `"room"` שונה מ-`"Room"`, כי `'r'` שונה מ-`'R'`. לכן אין אף שוויון ו-`Secret` מחזירה .
הזוג (`"Roommate"`, `"material"`, חפיפה – `"mate"`) כבר לא נבדק.
תשובה: `Sod(arr)` מחזירה `false`.
למשל `{"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"}` – לכל זוג סמוך החפיפה היא בדיוק 3.
אחרי השינוי `Sod` מחזירה `false` לכל זוג סמוך שהחפיפה שלו שונה מ-. כדי לקבל `true` צריך שלכל הזוגות הסמוכים החפיפה המקסימלית תהיה בדיוק : שלושת התווים האחרונים של כל מחרוזת הם שלושת התווים הראשונים של הבאה, ואין חפיפה ארוכה יותר.
בונים שרשרת של מחרוזות באורך , שכל אחת מתחילה בשלושת התווים האחרונים של הקודמת:
`string[] arr = {"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"};`
בדיקה של הזוג הראשון: : `"def"` מול `"def"` – שוויון; (`"f"`/`"d"`, `"ef"`/`"de"`) ו- (`"cdef"`/`"defg"`, ...) – אין שוויון. לכן `Secret` מחזירה . כך גם לכל שאר הזוגות (`"ghi"`, `"jkl"`, `"mno"`, `"pqr"`). כל חמשת הזוגות מחזירים , התנאי `!= 3` אף פעם לא מתקיים, ו-`Sod` מחזירה `true`.
תשובה: `{"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"}`.
שאלה 8 · מערך דו-ממדי מיוחד: מסגרת ותאים פנימיים
•מסגרת מערך הדו-ממדי מורכבת מהתאים הנמצאים בשורה 0, עמודה 0, שורה אחרונה ועמודה אחרונה.
•תא פנימי במערך דו-ממדי הוא איבר שאינו נמצא במסגרת המערך.
•מערך דו-ממדי נקרא "מערך מיוחד" אם כל האיברים הנמצאים במסגרת קטנים ממש מכל האיברים הנמצאים בתאים פנימיים.
הנחה: גודל המערך הוא לפחות 3X3
לדוגמה, המערך הבא הוא מערך מיוחד:
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים. הפעולה תבדוק אם המערך הוא מערך מיוחד. אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static bool IsSpecial(int[,] arr)public static boolean isSpecial(int[][] arr)מהי סיבוכיות זמן הריצה של כל הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr` ושני מספרים שלמים `low` ו-`high`.
הפעולה תמלא את המערך במספרים אקראיים בטווח בין `low` ל-`high` (כולל), כך שיתקבל מערך "מיוחד".
כותרת הפעולה:
public static void MakeSpecial(int[,] arr, int low, int high)public static void makeSpecial(int[][] arr, int low, int high)הנחה: הטווח בין `low` ל-`high` גדול מספיק (לפחות 2 ערכים שונים).
הנחיה: בצעו את המילוי בדרך שאינה מסתמכת על מזל בלבד, אלא מבטיחה את התנאי מראש.
◂ פתרון מלא לשאלה 8
סעיף א
מחשבים במעבר אחד את המקסימום של תאי המסגרת ואת המינימום של התאים הפנימיים, ומחזירים `maxFrame < minInner`.
הרעיון: "כל איבר במסגרת קטן ממש מכל איבר פנימי" שקול לתנאי אחד: הגדול ביותר במסגרת קטן ממש מהקטן ביותר בפנים. (אם המקסימום של המסגרת קטן מהמינימום של הפנים, כל איבר במסגרת קטן מכל איבר בפנים; ואם לא – הזוג של שניהם מפר את התנאי.) כך אין צורך להשוות כל זוג תאים.
1. מאתחלים את `maxFrame` בתא `[0,0]` (תמיד במסגרת) ואת `minInner` בתא `[1,1]` (תמיד פנימי, כי המערך לפחות ).
2. עוברים על כל התאים. תא נמצא במסגרת אם הוא בשורה , בשורה האחרונה, בעמודה או בעמודה האחרונה. לתא במסגרת מעדכנים את `maxFrame`, ולתא פנימי את `minInner`.
3. מחזירים `maxFrame < minInner` (קטן ממש).
בדיקה בדוגמה: במסגרת הערכים – המקסימום . בפנים – המינימום . , ולכן מוחזר `true`.
public static bool IsSpecial(int[,] arr)
{
int rows = arr.GetLength(0);
int cols = arr.GetLength(1);
int maxFrame = arr[0, 0]; // המקסימום של המסגרת
int minInner = arr[1, 1]; // המינימום של התאים הפנימיים
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
{
if (arr[i, j] > maxFrame)
maxFrame = arr[i, j]; // תא במסגרת
}
else
{
if (arr[i, j] < minInner)
minInner = arr[i, j]; // תא פנימי
}
}
}
return maxFrame < minInner;
}public static boolean isSpecial(int[][] arr)
{
int rows = arr.length;
int cols = arr[0].length;
int maxFrame = arr[0][0]; // המקסימום של המסגרת
int minInner = arr[1][1]; // המינימום של התאים הפנימיים
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
{
if (arr[i][j] > maxFrame)
maxFrame = arr[i][j]; // תא במסגרת
}
else
{
if (arr[i][j] < minInner)
minInner = arr[i][j]; // תא פנימי
}
}
}
return maxFrame < minInner;
}תשובה: הפעולה `IsSpecial` (ב-Java: `isSpecial`) שלמעלה.
סעיף ב
עבור מערך בן שורות ו- עמודות (ליניארי במספר התאים; למערך ריבועי).
1. נסמן ב- את מספר השורות וב- את מספר העמודות.
2. הפעולה עוברת פעם אחת על כל התאים בעזרת שתי לולאות מקוננות: סיבובים.
3. בכל סיבוב יש מספר קבוע של פעולות (בדיקה אם התא במסגרת, השוואה ואולי עדכון) – .
4. האתחול וההשוואה בסוף הם .
סך הכול . זה גם המינימום האפשרי, כי כדי לדעת שהמערך מיוחד חייבים לבדוק כל תא לפחות פעם אחת.
תשובה: (במערך ריבועי : ).
סעיף ג
מחלקים את הטווח בנקודה `mid = low + (high - low) / 2`: תאי המסגרת מקבלים מספר אקראי בין `low` ל-`mid`, והתאים הפנימיים מספר אקראי בין `mid + 1` ל-`high`.
הרעיון: כדי להבטיח מראש שכל איבר במסגרת קטן מכל איבר פנימי, מחלקים את הטווח לשני חלקים זרים – חלק תחתון למסגרת וחלק עליון לפנים:
1. מחשבים נקודת חלוקה `mid = low + (high - low) / 2`.
2. תא במסגרת מקבל מספר אקראי בטווח `low..mid`, ותא פנימי מספר אקראי בטווח `mid+1..high`.
3. כל ערך במסגרת כל ערך פנימי, ולכן המערך מיוחד בוודאות, בלי תלות במזל.
למה שני הטווחים לא ריקים: לפי ההנחה `high - low` . אז `mid` `low` (הטווח `low..mid` מכיל לפחות ערך אחד), ו-`mid` `high` כי (הטווח `mid+1..high` מכיל לפחות ערך אחד). למשל עבור `low = 1`, `high = 2`: `mid = 1`, המסגרת כולה והפנים כולו . כל המספרים בטווח `low..high`, כנדרש.
הגרלה: ב-C# `rand.Next(a, b + 1)` נותן מספר בין `a` ל-`b` כולל; ב-Java `a + rand.nextInt(b - a + 1)`. סיבוכיות: .
public static void MakeSpecial(int[,] arr, int low, int high)
{
Random rand = new Random();
int mid = low + (high - low) / 2; // המסגרת: low..mid, הפנים: mid+1..high
int rows = arr.GetLength(0);
int cols = arr.GetLength(1);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
arr[i, j] = rand.Next(low, mid + 1); // תא במסגרת
else
arr[i, j] = rand.Next(mid + 1, high + 1); // תא פנימי
}
}
}public static void makeSpecial(int[][] arr, int low, int high)
{
Random rand = new Random();
int mid = low + (high - low) / 2; // המסגרת: low..mid, הפנים: mid+1..high
int rows = arr.length;
int cols = arr[0].length;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
arr[i][j] = low + rand.nextInt(mid - low + 1); // תא במסגרת
else
arr[i][j] = mid + 1 + rand.nextInt(high - mid); // תא פנימי
}
}
}דוגמה: עבור `low = 0`, `high = 100`: `mid = 50`, המסגרת מקבלת ערכים בין ל- והתאים הפנימיים ערכים בין ל-.
תשובה: הפעולה `MakeSpecial` (ב-Java: `makeSpecial`) שלמעלה.
שאלה 9 · מרכז למידה: רישום לקורסים וקורסי מצטיינים
מרכז למידה מעוניין לנהל את הרישום לקורסים שלו. לשם כך הוגדרו שלוש מחלקות:
המחלקה `Student` מייצגת תלמיד. למחלקה שתי תכונות:
•שם מלא (`fullName`) – מחרוזת, `string`; (ב-Java: `String`)
•ציון ממוצע (`grade`) – מספר ממשי, `double`.
במחלקה הוגדרו בנאי, פעולות `Get/Set` ופעולה `ToString`.
המחלקה `Course` מייצגת קורס בודד. למחלקה התכונות האלה:
•שם קורס (`courseName`) – מחרוזת, `string`;
•ציון סף לקבלה לקורס (`minEntryGrade`) – מספר ממשי, `double`;
•מספר מקסימלי של מקומות בקורס (`maxStudents`) – מספר שלם, `int`;
•תלמידים שנרשמו (`registered`) – מערך של אובייקטים מסוג `Student`;
•מספר תלמידים שנרשמו בפועל (`count`) – מספר שלם, `int`.
במחלקה הוגדרו פעולות `Get/Set` והפעולה `ToString`.
המחלקה `LearningCenter` מייצגת את המרכז כולו. למחלקה שתי תכונות:
•שם מרכז (`centerName`) – מחרוזת, `string`;
•רשימת קורסים (`courses`) – מערך של אובייקטים מסוג `Course`. המערך מלא ולא כולל ערכי `null`.
כתבו במחלקה `Course` פעולה בונה המקבלת שם קורס, ציון סף לקבלה ומספר מקסימלי של מקומות.
הפעולה מאתחלת קורס ללא רשומים.
כתבו במחלקה `Course` פעולה בשם `AddStudent`. הפעולה תוסיף את התלמיד לקורס אם יש מקום פנוי בקורס והציון הממוצע של התלמיד גדול או שווה לציון הסף של הקורס. אם ההוספה הצליחה – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר ערך `false`. כותרת הפעולה:
public bool AddStudent(string name, double grade)public boolean addStudent(String name, double grade)קורס נקרא "קורס מצטיינים" אם לפחות חצי מהרשומים בקורס הם בעלי ציון ממוצע הגבוה מ-90.
כתבו במחלקה `Course` פעולה בשם `IsHonorsCourse`. אם קורס הוא "קורס מצטיינים" – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר ערך `false`. אם אין תלמידים רשומים כלל, הפעולה תחזיר `false`.
כתבו במחלקה `LearningCenter` פעולה בשם `PrintFullCourses`. הפעולה תדפיס את שמות הקורסים שאין בהם מקומות פנויים.
כתבו עבור המחלקה `LearningCenter` פעולה בשם `GetExcellentCourses`. הפעולה תיצור ותחזיר מערך חדש המכיל את שמות הקורסים המוגדרים כ"קורסי מצטיינים".
הערה: עליכם להקצות למערך החדש גודל מתאים בדיוק למספר הקורסים שנמצאו. אם אין אף קורס מתאים, הפעולה תחזיר מערך בגודל 0.
◂ פתרון מלא לשאלה 9
סעיף א
מציבים את שלושת הפרמטרים בתכונות, יוצרים `registered = new Student[maxStudents]` ומאתחלים `count = 0`.
הרעיון: שלוש תכונות מקבלות את ערכי הפרמטרים. "ללא רשומים" פירושו שמספר הרשומים בפועל `count` הוא . את מערך הרשומים יוצרים בגודל המקסימלי `maxStudents`, כדי שיהיה בו מקום לכל תלמיד שאפשר לרשום; התאים שלו יתמלאו לפי הסדר מהמקום , ו-`count` יציין כמה מהם בשימוש.
public Course(string courseName, double minEntryGrade, int maxStudents)
{
this.courseName = courseName;
this.minEntryGrade = minEntryGrade;
this.maxStudents = maxStudents;
this.registered = new Student[maxStudents]; // מקום לכל התלמידים האפשריים
this.count = 0; // עדיין אין רשומים
}public Course(String courseName, double minEntryGrade, int maxStudents)
{
this.courseName = courseName;
this.minEntryGrade = minEntryGrade;
this.maxStudents = maxStudents;
this.registered = new Student[maxStudents]; // מקום לכל התלמידים האפשריים
this.count = 0; // עדיין אין רשומים
}תשובה: הפעולה הבונה שלמעלה.
אם `count < maxStudents` וגם `grade >= minEntryGrade` – יוצרים `new Student(name, grade)`, מכניסים למקום `count`, מגדילים את `count` ומחזירים `true`; אחרת `false`.
הרעיון: שני תנאים חייבים להתקיים יחד:
1. יש מקום פנוי: `count < maxStudents`.
2. הציון עובר את הסף: `grade >= minEntryGrade`.
אם שניהם מתקיימים – יוצרים עצם `Student` חדש מהשם ומהציון (בעזרת הבנאי של `Student`), שמים אותו בתא הפנוי הראשון `registered[count]`, מגדילים את `count` ב- ומחזירים `true`. אחרת לא משנים דבר ומחזירים `false`.
public bool AddStudent(string name, double grade)
{
if (count < maxStudents && grade >= minEntryGrade)
{
registered[count] = new Student(name, grade);
count++;
return true;
}
return false;
}public boolean addStudent(String name, double grade)
{
if (count < maxStudents && grade >= minEntryGrade)
{
registered[count] = new Student(name, grade);
count++;
return true;
}
return false;
}דוגמה: בקורס עם סף ו- מקומות: תלמיד עם נוסף (`true`), תלמיד עם נדחה (`false`), תלמידים עם ו- נוספים (`true`), ותלמיד עם נדחה כי הקורס מלא (`false`).
תשובה: הפעולה `AddStudent` (ב-Java: `addStudent`) שלמעלה.
אם `count == 0` מחזירים `false`; אחרת סופרים את הרשומים עם ציון גבוה מ-90 ומחזירים `excellent * 2 >= count`.
1. אם `count == 0` – מחזירים `false` מיד (כך נדרש, ואחרת התנאי היה מתקיים "בטעות" כי ).
2. עוברים רק על `count` התאים הראשונים של `registered` (שאר התאים ריקים) וסופרים את התלמידים שהציון שלהם גבוה ממש מ-.
3. "לפחות חצי" פירושו . כדי להימנע מחלוקה בשלמים (שמעגלת כלפי מטה) משווים בצורה השקולה .
דוגמה: בקורס מסעיף 2 רשומים , , – שניים מעל , , ולכן `true`. בקורס עם , , – רק אחד, , ולכן `false`.
public bool IsHonorsCourse()
{
if (count == 0)
return false; // אין רשומים
int excellent = 0;
for (int i = 0; i < count; i++)
{
if (registered[i].GetGrade() > 90)
excellent++;
}
return excellent * 2 >= count; // לפחות חצי מהרשומים
}public boolean isHonorsCourse()
{
if (count == 0)
return false; // אין רשומים
int excellent = 0;
for (int i = 0; i < count; i++)
{
if (registered[i].getGrade() > 90)
excellent++;
}
return excellent * 2 >= count; // לפחות חצי מהרשומים
}תשובה: הפעולה `IsHonorsCourse` (ב-Java: `isHonorsCourse`) שלמעלה.
סעיף ב
עוברים על `courses` ומדפיסים את `GetCourseName()` של כל קורס שבו `GetCount() == GetMaxStudents()`.
הרעיון: בקורס אין מקומות פנויים כאשר מספר הרשומים בפועל שווה למספר המקסימלי של מקומות. הפעולה נמצאת ב-`LearningCenter`, ולכן לתכונות של כל `Course` ניגשים דרך פעולות ה-`Get`:
1. עוברים על כל הקורסים במערך `courses` (המערך מלא, בלי `null`).
2. אם `GetCount() == GetMaxStudents()` – מדפיסים את שם הקורס.
public void PrintFullCourses()
{
for (int i = 0; i < courses.Length; i++)
{
if (courses[i].GetCount() == courses[i].GetMaxStudents())
Console.WriteLine(courses[i].GetCourseName());
}
}public void printFullCourses()
{
for (int i = 0; i < courses.length; i++)
{
if (courses[i].getCount() == courses[i].getMaxStudents())
System.out.println(courses[i].getCourseName());
}
}תשובה: הפעולה `PrintFullCourses` (ב-Java: `printFullCourses`) שלמעלה.
מעבר ראשון סופר בעזרת `IsHonorsCourse()` את קורסי המצטיינים; יוצרים `string[]` בגודל הזה (אולי 0); מעבר שני ממלא אותו בשמות הקורסים לפי הסדר.
הרעיון: הגודל המדויק של המערך ידוע רק אחרי ספירה, לכן שני מעברים:
1. ספירה: עוברים על הקורסים וסופרים ב-`num` את אלה שעבורם `IsHonorsCourse()` (מסעיף א3) מחזירה `true`.
2. יוצרים מערך מחרוזות בגודל `num`. אם אין אף קורס מתאים, `num = 0` ונוצר מערך בגודל , כנדרש.
3. מילוי: עוברים שוב, וכל קורס מצטיינים מוסיף את שמו (`GetCourseName()`) למקום `k`, ו-`k` גדל ב-.
4. מחזירים את המערך.
public string[] GetExcellentCourses()
{
// מעבר ראשון: כמה קורסי מצטיינים יש?
int num = 0;
for (int i = 0; i < courses.Length; i++)
{
if (courses[i].IsHonorsCourse())
num++;
}
// מעבר שני: מילוי מערך השמות בגודל המדויק
string[] result = new string[num];
int k = 0;
for (int i = 0; i < courses.Length; i++)
{
if (courses[i].IsHonorsCourse())
{
result[k] = courses[i].GetCourseName();
k++;
}
}
return result;
}public String[] getExcellentCourses()
{
// מעבר ראשון: כמה קורסי מצטיינים יש?
int num = 0;
for (int i = 0; i < courses.length; i++)
{
if (courses[i].isHonorsCourse())
num++;
}
// מעבר שני: מילוי מערך השמות בגודל המדויק
String[] result = new String[num];
int k = 0;
for (int i = 0; i < courses.length; i++)
{
if (courses[i].isHonorsCourse())
{
result[k] = courses[i].getCourseName();
k++;
}
}
return result;
}תשובה: הפעולה `GetExcellentCourses` (ב-Java: `getExcellentCourses`) שלמעלה.
שאלה 10 · רקורסיה: מספר מיוחד ומקסימום מיוחד במערך
נתונה הפעולה `Special` המקבלת מספר שלם `num` ובודקת אם הוא "מספר מיוחד":
public static bool Special(int num) {
if(num < 10) return false;
return Special(num, 0);
}
public static bool Special(int num, int diff) {
if(num == 0){
return diff == 0;
}
int last = num % 10;
return Special(num/10, last - diff);
}public static boolean special(int num) {
if(num < 10) return false;
return special(num, 0);
}
public static boolean special(int num, int diff) {
if(num == 0){
return diff == 0;
}
int last = num % 10;
return special(num/10, last - diff);
}מה תהיה תוצאת זימון הפעולה `Special(12551)`? יש להראות מעקב.
מה תהיה תוצאת זימון הפעולה `Special(4254)`?
מה מבצעת הפעולה `Special(num)` באופן כללי עבור מספר שלם `num`?
נתונה הפעולה `Secret` המקבלת מערך של מספרים שלמים. הפעולה משתמשת בפעולה `Special`.
public static int Secret(int[] arr){
return Secret(arr, 0);
}
public static int Secret(int[] arr, int i) {
if (i == arr.Length) {
return -1;
}
int res = Secret(arr, i + 1);
if (Special(arr[i]) && arr[i] > res) {
return arr[i];
}
return res;
}public static int secret(int[] arr){
return secret(arr, 0);
}
public static int secret(int[] arr, int i) {
if (i == arr.length) {
return -1;
}
int res = secret(arr, i + 1);
if (special(arr[i]) && arr[i] > res) {
return arr[i];
}
return res;
}נתון מערך `arr`:
`int[] arr = {1234, 55, 1012, 363, 44, 827, 198}`
מה תהיה תוצאת זימון הפעולה `Secret(arr)`? יש להראות מעקב זימון הפעולה.
אין צורך במעקב אחרי הפעולה `Special`.
מה מבצעת הפעולה `Secret` באופן כללי?
כתבו הפעולה רקורסיבית המקבלת מערך של מספרים שלמים. הפעולה תבדוק שכל המספרים במערך הם "מיוחדים" (כלומר הפעולה `Special` תחזיר ערך `true` עבורם).
אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.
◂ פתרון מלא לשאלה 10
סעיף א
`true`.
, ולכן מזמנים `Special(12551, 0)`. בכל זימון: `last` היא ספרת האחדות, והזימון הבא מקבל `num/10` ו-`last - diff`.
הערך `true` עובר חזרה בלי שינוי דרך כל הזימונים.
תשובה: `Special(12551)` מחזירה `true`.
`false` (בסוף `diff = 3`).
, ולכן מזמנים `Special(4254, 0)`:
תשובה: `Special(4254)` מחזירה `false`.
עבור `num < 10` (חד-ספרתי, 0 או שלילי) מחזירה `false`. עבור `num >= 10` מחזירה `true` אם ורק אם סכום הספרות במקומות הזוגיים שווה לסכום הספרות במקומות האי-זוגיים (הסכום המתחלף של הספרות הוא 0).
1. מקרה `num < 10`: מספר חד-ספרתי, או מספר שלילי – הפעולה מחזירה `false` מיד.
2. מקרה `num >= 10`: נסמן את הספרות מימין לשמאל (אחדות, עשרות, ...). לפי הקוד:
•אחרי ספרה אחת: ;
•אחרי שתיים: ;
•אחרי שלוש: ; וכן הלאה.
כלומר, בסוף הוא (עד כדי סימן) הסכום המתחלף , והפעולה מחזירה `true` אם ורק אם הוא .
3. במילים: מספר הוא "מיוחד" אם יש לו לפחות שתי ספרות, וסכום הספרות במקומות הזוגיים (אחדות, מאות, ...) שווה לסכום הספרות במקומות האי-זוגיים (עשרות, אלפים, ...).
בדיקה: : ו- – שווים, `true`. : ו- – לא שווים, `false` (ההפרש הוא בדיוק `diff` האחרון).
הערה: כל מספר מיוחד מתחלק ב- (כי הסכום המתחלף שלו ), אבל לא להפך – למשל מתחלק ב- אך הסכום המתחלף שלו הוא (הוא , ו-`Special(209)` מחזירה `false`).
תשובה: עבור `num < 10` מוחזר `false`; עבור `num >= 10` מוחזר `true` אם ורק אם סכום הספרות במקומות הזוגיים שווה לסכום הספרות במקומות האי-זוגיים.
סעיף ב
`Secret(arr)` מחזירה 1012.
`Secret(arr)` מזמנת את `Secret(arr, 0)`. כל זימון קורא קודם לזימון של `i+1`, ולכן הזימונים "יורדים" עד `i = 7` (סוף המערך), שמחזיר , והחישוב מתבצע בדרך חזרה – מסוף המערך להתחלה.
קודם בודקים אילו מספרים מיוחדים (סכום מתחלף של הספרות ): : – לא; : – כן; : – כן; : – כן; – כן; : – לא; : – כן.
תשובה: `Secret(arr)` מחזירה .
מחזירה את המספר המיוחד הגדול ביותר במערך, ו-1- אם אין במערך אף מספר מיוחד.
1. `Secret(arr, i)` מחזירה ערך שמתייחס לחלק המערך מהמקום `i` עד הסוף. עבור חלק ריק (`i == arr.Length`) מוחזר .
2. בכל שלב, `res` הוא התוצאה של החלק שמימין. אם `arr[i]` מיוחד וגדול מ-`res`, הוא מחליף אותו; אחרת נשאר `res`.
3. זהו חיפוש מקסימום רקורסיבי רק בין המספרים המיוחדים. משמש כערך התחלתי: כל מספר מיוחד הוא לפחות , ולכן גדול ממנו, ו- נשאר רק אם אין אף מספר מיוחד.
תשובה: הפעולה מחזירה את המספר ה"מיוחד" הגדול ביותר במערך; אם אין במערך מספר מיוחד – היא מחזירה .
סעיף ג
פעולת מעטפת `AllSpecial(arr)` שמזמנת `AllSpecial(arr, 0)`: אם `i == Length` מחזירים `true`; אם `arr[i]` אינו מיוחד – `false`; אחרת מזמנים עם `i + 1`.
הרעיון: כמו בסעיף ב, משתמשים בפעולת עזר עם אינדקס `i`, שבודקת את חלק המערך מ-`i` עד הסוף. פעולה עם פרמטר אחד (המערך) מזמנת אותה עם `i = 0`.
1. תנאי עצירה: אם `i == Length` – לא נשארו איברים לבדוק, וכל מה שנבדק היה מיוחד: מחזירים `true`. (למערך ריק מוחזר `true` – אין בו מספר שאינו מיוחד.)
2. צעד: אם `arr[i]` אינו מיוחד (`Special` מחזירה `false`) – מחזירים `false` מיד.
3. אחרת, התשובה היא התשובה עבור שאר המערך: מזמנים רקורסיבית עם `i + 1`.
public static bool AllSpecial(int[] arr)
{
return AllSpecial(arr, 0);
}
public static bool AllSpecial(int[] arr, int i)
{
if (i == arr.Length)
return true; // עברנו על כל המערך
if (!Special(arr[i]))
return false; // נמצא מספר שאינו מיוחד
return AllSpecial(arr, i + 1); // בודקים את המשך המערך
}public static boolean allSpecial(int[] arr)
{
return allSpecial(arr, 0);
}
public static boolean allSpecial(int[] arr, int i)
{
if (i == arr.length)
return true; // עברנו על כל המערך
if (!special(arr[i]))
return false; // נמצא מספר שאינו מיוחד
return allSpecial(arr, i + 1); // בודקים את המשך המערך
}דוגמה: עבור `{55, 1012, 363}` מוחזר `true`; עבור `{55, 1234}` מוחזר `false` (כי אינו מיוחד).
תשובה: הפעולה הרקורסיבית `AllSpecial` (ב-Java: `allSpecial`) שלמעלה.