מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2026 מועד ב'
הנדסת תוכנה · סמל 97104 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2026 מועד ב', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב-C# (עמוד 2)
מבחן ב-Java (עמוד 14)
בכל מבחן 10 שאלות.
שאלות 1–4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה – 12 נקודות.
שאלות 5–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
שאלות 8–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 17 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
מילון עזר.
שאלה 1 · מחרוזת תקינה: אורך זוגי ותו ראשון ייחודי
מחרוזת "תקינה" היא מחרוזת העונה על שני תנאים:
•אורך המחרוזת זוגי;
•התו הראשון זהה לתו האחרון ותו זה אינו מופיע במקומות האחרים של המחרוזת.
לדוגמה: המחרוזת `"Abbc1A"` היא "מחרוזת תקינה".
המחרוזת `"Abc1A"` אינה "מחרוזת תקינה".
המחרוזת `"Abbc1D"` אינה "מחרוזת תקינה".
המחרוזת `"AbAc1A"` אינה "מחרוזת תקינה".
כתבו פעולה המקבלת מחרוזת ובודקת אם היא "מחרוזת תקינה". אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static bool IsValid (string s)public static boolean isValid (String s)כתבו קטע קוד הקולט 30 מחרוזות. הקטע יחשב וידפיס את מספר "המחרוזות התקינות" ואת מספר המחרוזות שאינן תקינות. יש להשתמש בפעולה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 1
סעיף א
פעולה שמחזירה `false` אם האורך אינו זוגי (או 0), אם התו האחרון שונה מהראשון, או אם התו הראשון מופיע באחד המקומות עד ; אחרת מחזירה `true`.
הרעיון: בודקים את שני התנאים לפי הסדר, ומחזירים `false` ברגע שאחד מהם נכשל:
1. אורך זוגי: אם `n % 2 != 0` – המחרוזת לא תקינה. מחרוזת ריקה (אורך ) גם נפסלת, כי אין לה תו ראשון ואחרון.
2. התו הראשון שווה לאחרון: שומרים את התו הראשון במשתנה `first` ומשווים אותו לתו במקום .
3. התו הראשון לא מופיע במקומות האחרים: עוברים בלולאה על המקומות עד (כל המקומות פרט לראשון ולאחרון). אם באחד מהם מופיע `first` – מחזירים `false`.
4. אם עברנו את כל הבדיקות – המחרוזת תקינה, ומחזירים `true`.
סיבוכיות: – מעבר אחד על המחרוזת.
public static bool IsValid(string s)
{
int n = s.Length;
if (n == 0 || n % 2 != 0)
return false; // אורך המחרוזת אינו זוגי (או מחרוזת ריקה)
char first = s[0];
if (s[n - 1] != first)
return false; // התו האחרון שונה מהתו הראשון
for (int i = 1; i < n - 1; i++) // המקומות האחרים: בין הראשון לאחרון
{
if (s[i] == first)
return false; // התו הראשון מופיע גם באמצע
}
return true;
}public static boolean isValid(String s)
{
int n = s.length();
if (n == 0 || n % 2 != 0)
return false; // אורך המחרוזת אינו זוגי (או מחרוזת ריקה)
char first = s.charAt(0);
if (s.charAt(n - 1) != first)
return false; // התו האחרון שונה מהתו הראשון
for (int i = 1; i < n - 1; i++) // המקומות האחרים: בין הראשון לאחרון
{
if (s.charAt(i) == first)
return false; // התו הראשון מופיע גם באמצע
}
return true;
}תשובה: הפעולה `IsValid` (ב-Java: `isValid`) שלמעלה.
סעיף ב
לולאת `for` של 30 סיבובים: קולטים מחרוזת, ולפי הפעולה מסעיף א מגדילים את מונה התקינות או את מונה הלא-תקינות; אחרי הלולאה מדפיסים את שני המונים.
הרעיון: מספר המחרוזות ידוע מראש (30), ולכן משתמשים בלולאת `for`.
1. מאתחלים שני מונים: `validCount = 0` למחרוזות התקינות ו-`invalidCount = 0` לשאינן תקינות.
2. בכל סיבוב קולטים מחרוזת ושולחים אותה לפעולה מסעיף א.
3. אם הפעולה החזירה `true` – מגדילים את `validCount`, אחרת – את `invalidCount`.
4. אחרי הלולאה מדפיסים את שני המונים. (בסוף תמיד מתקיים `validCount + invalidCount = 30`.)
int validCount = 0; // מונה המחרוזות התקינות
int invalidCount = 0; // מונה המחרוזות שאינן תקינות
string str;
for (int i = 1; i <= 30; i++)
{
str = Console.ReadLine();
if (IsValid(str))
validCount++;
else
invalidCount++;
}
Console.WriteLine("valid: " + validCount);
Console.WriteLine("not valid: " + invalidCount);int validCount = 0; // מונה המחרוזות התקינות
int invalidCount = 0; // מונה המחרוזות שאינן תקינות
String str;
for (int i = 1; i <= 30; i++)
{
str = in.next();
if (isValid(str))
validCount++;
else
invalidCount++;
}
System.out.println("valid: " + validCount);
System.out.println("not valid: " + invalidCount);תשובה: קטע הקוד שלמעלה.
שאלה 2 · ספרה מקסימלית ומינימום הספרות המקסימליות במערך
כתבו פעולה המקבלת מספר שלם חיובי ומחזירה את הספרה המקסימלית (הגדולה ביותר) המופיעה בו.
עבור המספר 12734 הפעולה תחזיר 7.
כותרת הפעולה:
public static int MaxDigit(int num)public static int maxDigit(int num)כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים. עבור כל איבר במערך, הפעולה תמצא את הספרה הגדולה ביותר ותחזיר את הערך המינימלי (הקטן ביותר) מבין כל הספרות המקסימליות שנמצאו.
עבור המערך `arr = {1283, 45, 1971, 613}` הפעולה תחזיר 5.
כותרת הפעולה:
public static int MinOfMaxDigits(int[] arr)public static int minOfMaxDigits(int[] arr)◂ פתרון מלא לשאלה 2
סעיף א
מפרקים את המספר לספרות בעזרת `% 10` ו-`/ 10` ושומרים את הספרה הגדולה ביותר; עבור 12734 מוחזר 7.
הרעיון: מפרקים את המספר לספרותיו מימין לשמאל: `num % 10` נותן את ספרת האחדות, ו-`num / 10` מוחק אותה. זהו חיפוש מקסימום רגיל:
1. מאתחלים את `max` בספרת האחדות, ומוחקים אותה מהמספר.
2. כל עוד נשארו ספרות (`num > 0`) – לוקחים את הספרה הבאה, ואם היא גדולה מ-`max` מעדכנים את `max`.
3. מחזירים את `max`.
האתחול בספרה אמיתית של המספר (ולא ב-0 שרירותי) נכון תמיד. סיבוכיות: , כאשר מספר הספרות.
public static int MaxDigit(int num)
{
int max = num % 10; // ספרת האחדות היא המועמדת הראשונה
num = num / 10;
while (num > 0)
{
int dig = num % 10;
if (dig > max)
max = dig;
num = num / 10;
}
return max;
}public static int maxDigit(int num)
{
int max = num % 10; // ספרת האחדות היא המועמדת הראשונה
num = num / 10;
while (num > 0)
{
int dig = num % 10;
if (dig > max)
max = dig;
num = num / 10;
}
return max;
}מוחזר 7, כמו בדוגמה.
תשובה: הפעולה `MaxDigit` (ב-Java: `maxDigit`) שלמעלה.
סעיף ב
מחשבים `MaxDigit` לכל איבר ומחזירים את הקטן מבין הערכים; עבור `{1283, 45, 1971, 613}` מוחזר 5.
הרעיון: חיפוש מינימום על הערכים `MaxDigit(arr[i])`:
1. מאתחלים את `min` בספרה המקסימלית של האיבר הראשון.
2. עוברים על שאר האיברים, מחשבים לכל אחד את הספרה המקסימלית שלו בעזרת הפעולה מסעיף א, ואם היא קטנה מ-`min` – מעדכנים.
3. מחזירים את `min`.
public static int MinOfMaxDigits(int[] arr)
{
int min = MaxDigit(arr[0]); // הספרה המקסימלית של האיבר הראשון
for (int i = 1; i < arr.Length; i++)
{
int curMax = MaxDigit(arr[i]);
if (curMax < min)
min = curMax;
}
return min;
}public static int minOfMaxDigits(int[] arr)
{
int min = maxDigit(arr[0]); // הספרה המקסימלית של האיבר הראשון
for (int i = 1; i < arr.length; i++)
{
int curMax = maxDigit(arr[i]);
if (curMax < min)
min = curMax;
}
return min;
}הקטנה מבין היא .
תשובה: הפעולה `MinOfMaxDigits` (ב-Java: `minOfMaxDigits`) שלמעלה.
שאלה 3 · מעקב: השוואת ספרה מובילה ומספר ספרות
נתונה הפעולה `What` המקבלת שני מספרים שלמים חיוביים `num1` ו-`num2`:
public static bool What(int num1, int num2)
{
if(num1 == num2) return false;
while(num1 > 9 && num2 > 9)
{
num1 = num1 /10;
num2 = num2/10;
}
return num1 == num2;
}public static boolean what(int num1, int num2)
{
if(num1 == num2) return false;
while(num1 > 9 && num2 > 9)
{
num1 = num1 /10;
num2 = num2/10;
}
return num1 == num2;
}תנו דוגמה למספר שלם וחיובי `num` שעבורו זימון הפעולה `What(1234, num)` יחזיר ערך `true`.
מה מבצעת הפעולה `What` באופן כללי?
נתונה הפעולה `Secret` המקבלת שני מערכים המכילים מספרים שלמים חיוביים ומשתמשת בפעולה `What`:
public static bool Secret(int[] a, int[] b) {
for (int i = 0; i < a.Length; i++) {
bool flag = false;
for (int k = 0; k < b.Length; k++) {
if (What(a[i], b[k])) {
flag = true;
}
}
if (!flag) return false;
}
return true;
}public static boolean secret(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
boolean flag = false;
for (int k = 0; k < b.length; k++) {
if (what(a[i], b[k])) {
flag = true;
}
}
if (!flag) return false;
}
return true;
}נתון מערך מספרים שלמים `a = {46, 127, 415, 104, 491, 371, 49}`
תנו דוגמה למערך `b` בעל מספר האיברים הקטן ביותר שעבורו זימון הפעולה `Secret(a, b)` יחזיר ערך `true`.
האם לכל זוג מערכים של מספרים שלמים חיוביים `a` ו-`b`, תוצאת זימון הפעולה `Secret(a, b)` תהיה זהה לתוצאת זימון הפעולה `Secret(b, a)`? הסבירו את תשובתכם.
מה מבצעת הפעולה `Secret` באופן כללי?
◂ פתרון מלא לשאלה 3
סעיף א
למשל `num = 1000` (כל מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234).
הרעיון: הלולאה מוחקת ספרת אחדות משני המספרים יחד, כל עוד בשניהם יש לפחות שתי ספרות. כדי שבסוף יתקבל `num1 == num2`, צריך ששני המספרים יגיעו לספרה בודדת באותו סיבוב (כלומר יהיה להם אותו מספר ספרות) ושהספרה שתישאר (הספרה השמאלית) תהיה זהה. בנוסף המספרים צריכים להיות שונים, אחרת השורה הראשונה מחזירה `false`.
עבור `num1 = 1234` נבחר מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234, למשל `num = 1000`.
בסוף `num1 == num2` (שניהם 1), ולכן מוחזר `true`.
תשובה: `num = 1000` (או כל מספר בין 1000 ל-1999 פרט ל-1234).
מחזירה `true` אם המספרים שונים, בעלי אותו מספר ספרות ואותה ספרה שמאלית (ספרה מובילה); אחרת `false`.
1. אם `num1 == num2` – מוחזר `false` מיד.
2. הלולאה מחלקת את שני המספרים ב-10 בכל סיבוב, ועוצרת כשאחד מהם הופך לחד-ספרתי.
•אם למספרים אותו מספר ספרות – שניהם הופכים לחד-ספרתיים באותו סיבוב, ונשארות הספרות השמאליות שלהם. ההשוואה בודקת אם הספרות השמאליות שוות.
•אם למספרים מספר ספרות שונה – כשהקצר הופך לחד-ספרתי, לארוך עדיין יש לפחות שתי ספרות, ולכן הם שונים ומוחזר `false`.
תשובה: הפעולה מחזירה `true` אם `num1` ו-`num2` שונים זה מזה, יש להם אותו מספר ספרות, והספרה השמאלית (הבכירה) שלהם זהה; אחרת היא מחזירה `false`.
סעיף ב
מערך בן 4 איברים, למשל `b = {40, 100, 400, 300}`.
הרעיון: `Secret(a, b)` מחזירה `true` רק אם לכל איבר `a[i]` יש איבר `b[k]` שעבורו `What(a[i], b[k])` מחזירה `true`, כלומר איבר שונה ממנו, עם אותו מספר ספרות ואותה ספרה שמאלית (לפי סעיף א.2).
1. נמיין את איברי `a` לקבוצות לפי (מספר ספרות, ספרה שמאלית):
2. איבר של `b` יכול "לשרת" רק קבוצה אחת (יש לו מספר ספרות אחד וספרה שמאלית אחת), ולכן צריך לפחות 4 איברים.
3. לכל קבוצה בוחרים מספר שמתאים לה ושונה מכל איבריה: `40` (שונה מ-46 ומ-49), `100` (שונה מ-127 ומ-104), `400` (שונה מ-415 ומ-491), `300` (שונה מ-371).
בדיקה: לכל איבר של `a` נמצא איבר מתאים ב-`b`, ולכן כל הדגלים `flag` מקבלים `true` והפעולה מחזירה `true`.
תשובה: `b = {40, 100, 400, 300}` – 4 איברים (זה המינימום).
לא. למשל עבור `a = {10}`, `b = {11, 20}`: `Secret(a, b)` מחזירה `true` ו-`Secret(b, a)` מחזירה `false`.
הפעולה בודקת שלכל איבר של המערך הראשון יש "בן זוג" במערך השני – הבדיקה אינה סימטרית: `Secret(a, b)` לא בודקת דבר על איברי `b` שאין להם בן זוג ב-`a`.
דוגמה נגדית: `a = {10}`, `b = {11, 20}`.
1. `Secret(a, b)`: עבור 10 יש ב-`b` את 11 (שונה, דו-ספרתי, מתחיל ב-1), ולכן מוחזר `true`.
2. `Secret(b, a)`: עבור 11 יש ב-`a` את 10 – מתאים. עבור 20 – האיבר היחיד ב-`a` הוא 10, שמתחיל ב-1 ולא ב-2, ולכן `flag` נשאר `false` ומוחזר `false`.
תשובה: לא. התוצאות יכולות להיות שונות, כמו בדוגמה שלמעלה.
מחזירה `true` אם לכל איבר של `a` יש ב-`b` איבר שונה ממנו עם אותו מספר ספרות ואותה ספרה שמאלית; אחרת `false`.
1. הלולאה החיצונית עוברת על כל איבר `a[i]`.
2. הלולאה הפנימית מחפשת ב-`b` איבר שעבורו `What(a[i], b[k])` מחזירה `true`, ואם יש כזה – `flag` הופך ל-`true`.
3. אם לאיבר כלשהו של `a` לא נמצא איבר כזה – מוחזר `false` מיד. אם כל האיברים עברו – מוחזר `true`.
תשובה: הפעולה בודקת אם לכל איבר במערך `a` קיים במערך `b` איבר השונה ממנו, בעל אותו מספר ספרות ואותה ספרה שמאלית (בכירה). אם כן – מוחזר `true`, אחרת `false`.
שאלה 4 · מחלקת מחשב נייד: בנאי ופעולות על מערך
מעבדת מחשבים החליטה למחשב את ניהול המחשבים הניידים המגיעים אליה לתיקון. לשם כך הוגדרה המחלקה `Laptop`. למחלקה התכונות הבאות:
•`string serialNum` (ב-Java: `String serialNum`) – מספר סידורי של המחשב;
•`string ownerName` (ב-Java: `String ownerName`) – שם בעל המחשב;
•`int ramSize` – זיכרון ה-RAM של המחשב (ב-GB);
•`bool isTouchScreen` (ב-Java: `boolean isTouchScreen`) – האם למחשב יש מסך מגע? (כן – `true`, לא – `false`);
•`bool isRepaired` (ב-Java: `boolean isRepaired`) – האם המחשב תוקן ומוכן לאיסוף? (כן – `true`, לא – `false`).
כתבו במחלקה `Laptop` את הפעולה הבונה (`Constructor`) המקבלת כפרמטרים את המספר הסידורי ואת שם הבעלים בלבד. הפעולה תאתחל את שאר התכונות כך שהמחשב יהיה בעל זיכרון RAM של 8 GB, ללא מסך מגע, ואינו מוכן לאיסוף.
כתבו פעולה חיצונית המקבלת מערך של מחשבים ניידים (מערך הפניות לעצמים מטיפוס `Laptop`) ומחזירה את מספר המחשבים שהם בעלי מסך מגע וגם הזיכרון שלהם הוא לפחות 8 GB.
כתבו פעולה חיצונית המקבלת מערך של מחשבים ניידים (מערך הפניות לעצמים מטיפוס `Laptop`) ומדפיסה את שמות הבעלים של המחשבים עם מסך מגע המוכנים לאיסוף.
אם אין אף מחשב כזה (שמוכן לאיסוף וגם בעל מסך מגע), הפעולה תדפיס הודעה מתאימה.
◂ פתרון מלא לשאלה 4
סעיף א
בנאי שמציב את שני הפרמטרים, ובנוסף `ramSize = 8`, `isTouchScreen = false`, `isRepaired = false`.
הרעיון: הבנאי מקבל רק שני פרמטרים ומציב אותם בתכונות המתאימות. את שלוש התכונות האחרות מאתחלים בערכים קבועים לפי הדרישה:
1. `serialNum` ו-`ownerName` – מהפרמטרים.
2. זיכרון RAM של 8 GB – `ramSize = 8`.
3. ללא מסך מגע – `isTouchScreen = false`.
4. אינו מוכן לאיסוף – `isRepaired = false`.
public Laptop(string serialNum, string ownerName)
{
this.serialNum = serialNum;
this.ownerName = ownerName;
this.ramSize = 8; // זיכרון RAM של 8 GB
this.isTouchScreen = false; // ללא מסך מגע
this.isRepaired = false; // עדיין לא מוכן לאיסוף
}public Laptop(String serialNum, String ownerName)
{
this.serialNum = serialNum;
this.ownerName = ownerName;
this.ramSize = 8; // זיכרון RAM של 8 GB
this.isTouchScreen = false; // ללא מסך מגע
this.isRepaired = false; // עדיין לא מוכן לאיסוף
}תשובה: הבנאי שלמעלה.
סעיף ב
עוברים על המערך וסופרים את המחשבים שעבורם `GetIsTouchScreen()` הוא `true` וגם `GetRamSize() >= 8`; מחזירים את המונה.
הרעיון: ספירה בתנאי. הפעולה חיצונית למחלקה, ולכן ניגשים לתכונות דרך פעולות ה-Get (הנחנו שמותיהן `GetIsTouchScreen`, `GetRamSize`; ב-Java: `getIsTouchScreen`, `getRamSize`).
1. מאתחלים מונה `count = 0`.
2. עוברים על כל המחשבים במערך. אם למחשב יש מסך מגע וגם הזיכרון שלו לפחות 8 (כלומר `>= 8`) – מגדילים את המונה.
3. מחזירים את המונה.
public static int CountTouchBigRam(Laptop[] laptops)
{
int count = 0;
for (int i = 0; i < laptops.Length; i++)
{
if (laptops[i].GetIsTouchScreen() && laptops[i].GetRamSize() >= 8)
count++;
}
return count;
}public static int countTouchBigRam(Laptop[] laptops)
{
int count = 0;
for (int i = 0; i < laptops.length; i++)
{
if (laptops[i].getIsTouchScreen() && laptops[i].getRamSize() >= 8)
count++;
}
return count;
}תשובה: הפעולה `CountTouchBigRam` (ב-Java: `countTouchBigRam`) שלמעלה.
סעיף ג
עוברים על המערך ומדפיסים `GetOwnerName()` של כל מחשב עם מסך מגע שתוקן; משתנה בוליאני `found` מסמן אם הודפס שם, ואם לא – מדפיסים הודעה.
הרעיון: מעבר על המערך עם הדפסה בתנאי, ובנוסף "דגל" שזוכר אם נמצא מחשב מתאים, כדי לדעת בסוף אם להדפיס את ההודעה.
1. מאתחלים `found = false`.
2. לכל מחשב: אם יש לו מסך מגע וגם הוא מוכן לאיסוף – מדפיסים את שם הבעלים ומציבים `found = true`.
3. אחרי הלולאה, אם `found` נשאר `false` – לא הודפס אף שם, ולכן מדפיסים הודעה מתאימה.
public static void PrintReadyTouch(Laptop[] laptops)
{
bool found = false; // האם נמצא לפחות מחשב אחד מתאים
for (int i = 0; i < laptops.Length; i++)
{
if (laptops[i].GetIsTouchScreen() && laptops[i].GetIsRepaired())
{
Console.WriteLine(laptops[i].GetOwnerName());
found = true;
}
}
if (!found)
Console.WriteLine("אין מחשב עם מסך מגע המוכן לאיסוף");
}public static void printReadyTouch(Laptop[] laptops)
{
boolean found = false; // האם נמצא לפחות מחשב אחד מתאים
for (int i = 0; i < laptops.length; i++)
{
if (laptops[i].getIsTouchScreen() && laptops[i].getIsRepaired())
{
System.out.println(laptops[i].getOwnerName());
found = true;
}
}
if (!found)
System.out.println("אין מחשב עם מסך מגע המוכן לאיסוף");
}תשובה: הפעולה `PrintReadyTouch` (ב-Java: `printReadyTouch`) שלמעלה.
שאלה 5 · דרגת אי-זוגיות, דרגת שיא ומערך מלא
נתונה הגדרה הבאה:
•"דרגת האי-זוגיות" של מספר שלם היא כמות הספרות האי-זוגיות במספר.
"דרגת האי-זוגיות" של המספר 12347 היא 3.
"דרגת האי-זוגיות" של המספר 1860 היא 1.
"דרגת האי-זוגיות" של המספר 246 היא 0.
"דרגת האי-זוגיות" של המספר (-3145) היא 3.
כתבו פעולה המקבלת מספר שלם ומחזירה את "דרגת האי-זוגיות" שלו.
כותרת הפעולה:
public static int OddDegree(int num)public static int oddDegree(int num)•"דרגת השיא" של מערך של מספרים שלמים היא "דרגת האי-זוגיות" הגבוהה ביותר שיש בו.
כתבו פעולה המקבלת מערך חד-ממדי ומחזירה את "דרגת השיא" שלו.
כותרת הפעולה:
public static int PeekDegree(int[] arr)public static int peekDegree(int[] arr)•מערך של מספרים שלמים נקרא "מערך מלא לפי דרגות האי-זוגיות" אם הוא כולל את כל דרגות האי-זוגיות מ-0 ועד "דרגת השיא" וכל דרגה מופיעה בו בדיוק פעם אחת.
כתבו פעולה המקבלת מערך חד-ממדי של מספרים שלמים. הפעולה מחזירה `true` אם המערך מלא לפי דרגות האי-זוגיות, אחרת הפעולה מחזירה `false`.
כותרת הפעולה:
public static bool IsFullArray(int[] arr)public static boolean isFullArray(int[] arr)◂ פתרון מלא לשאלה 5
סעיף א
הופכים מספר שלילי לחיובי, ואז סופרים את הספרות `dig` שעבורן `dig % 2 == 1` בעזרת `% 10` ו-`/ 10`.
הרעיון: מפרקים את המספר לספרות וסופרים את האי-זוגיות.
1. אם המספר שלילי – הופכים אותו לחיובי. הסימן אינו ספרה, ובלי ההיפוך `num % 10` של מספר שלילי מחזיר ערך שלילי והלולאה `while (num > 0)` לא תרוץ כלל.
2. כל עוד `num > 0`: לוקחים את ספרת האחדות `num % 10`; אם היא אי-זוגית (`dig % 2 == 1`) – מגדילים את המונה; מוחקים את הספרה (`num / 10`).
3. מחזירים את המונה. עבור 0 מוחזר 0 (אין ספרות אי-זוגיות).
public static int OddDegree(int num)
{
if (num < 0)
num = -num; // הסימן לא משנה את הספרות
int count = 0;
while (num > 0)
{
int dig = num % 10;
if (dig % 2 == 1)
count++; // ספרה אי-זוגית
num = num / 10;
}
return count;
}public static int oddDegree(int num)
{
if (num < 0)
num = -num; // הסימן לא משנה את הספרות
int count = 0;
while (num > 0)
{
int dig = num % 10;
if (dig % 2 == 1)
count++; // ספרה אי-זוגית
num = num / 10;
}
return count;
}בדיקה מול הדוגמאות: 12347 – הספרות האי-זוגיות 1, 3, 7, ולכן 3. 1860 – רק 1, ולכן 1. 246 – אין, ולכן 0. -3145 – הופך ל-3145, הספרות 3, 1, 5, ולכן 3.
תשובה: הפעולה `OddDegree` (ב-Java: `oddDegree`) שלמעלה.
סעיף ב
חיפוש מקסימום על `OddDegree(arr[i])` לכל איברי המערך.
הרעיון: חיפוש מקסימום על דרגות האי-זוגיות של האיברים.
1. מאתחלים `max = 0` – דרגת אי-זוגיות אינה שלילית לעולם, ולכן 0 הוא ערך התחלתי בטוח.
2. לכל איבר מחשבים את דרגתו בעזרת הפעולה מסעיף א, ואם היא גדולה מ-`max` – מעדכנים.
3. מחזירים את `max`.
public static int PeekDegree(int[] arr)
{
int max = 0; // דרגה היא תמיד לפחות 0
for (int i = 0; i < arr.Length; i++)
{
int deg = OddDegree(arr[i]);
if (deg > max)
max = deg;
}
return max;
}public static int peekDegree(int[] arr)
{
int max = 0; // דרגה היא תמיד לפחות 0
for (int i = 0; i < arr.length; i++)
{
int deg = oddDegree(arr[i]);
if (deg > max)
max = deg;
}
return max;
}דוגמה: עבור `{12347, 1860, 246}` הדרגות הן , ולכן "דרגת השיא" היא 3.
תשובה: הפעולה `PeekDegree` (ב-Java: `peekDegree`) שלמעלה.
סעיף ג
מחשבים `peak = PeekDegree(arr)`; אם אורך המערך שונה מ-`peak + 1` מחזירים `false`; אחרת סופרים במערך מונים בגודל `peak + 1` כמה פעמים מופיעה כל דרגה, ומחזירים `false` אם דרגה כלשהי מופיעה פעמיים, אחרת `true`.
1. מחשבים את "דרגת השיא" `peak` בעזרת הפעולה מסעיף ב. הדרגות שצריכות להופיע הן – בסך הכול דרגות, כל אחת בדיוק פעם אחת. לכן במערך מלא יש בדיוק איברים, ואם האורך שונה – מחזירים `false` מיד.
2. כל איבר הוא בעל דרגה בין 0 ל-`peak` (כי `peak` היא הגבוהה ביותר). לכן אפשר להשתמש במערך מונים `count` בגודל `peak + 1`, שבו `count[d]` סופר כמה איברים בעלי דרגה `d`.
3. עוברים על המערך ומגדילים את המונה של דרגת כל איבר. אם מונה כלשהו מגיע ל-2 – יש דרגה שמופיעה פעמיים, ומחזירים `false`.
4. אם סיימנו: יש איברים ואף דרגה לא חזרה, ולכן כל אחת מ- הדרגות מופיעה בדיוק פעם אחת – מחזירים `true`.
סיבוכיות: , כאשר אורך המערך ו- מספר הספרות המרבי (חישוב הדרגות).
public static bool IsFullArray(int[] arr)
{
int peak = PeekDegree(arr);
if (arr.Length != peak + 1)
return false; // חייב להיות איבר אחד בדיוק לכל דרגה 0..peak
int[] count = new int[peak + 1]; // count[d] = כמה איברים בעלי דרגה d
for (int i = 0; i < arr.Length; i++)
{
int deg = OddDegree(arr[i]);
count[deg]++;
if (count[deg] > 1)
return false; // דרגה שמופיעה פעמיים
}
return true;
}public static boolean isFullArray(int[] arr)
{
int peak = peekDegree(arr);
if (arr.length != peak + 1)
return false; // חייב להיות איבר אחד בדיוק לכל דרגה 0..peak
int[] count = new int[peak + 1]; // count[d] = כמה איברים בעלי דרגה d
for (int i = 0; i < arr.length; i++)
{
int deg = oddDegree(arr[i]);
count[deg]++;
if (count[deg] > 1)
return false; // דרגה שמופיעה פעמיים
}
return true;
}•`{246, 12347, 1860, 13}`: הדרגות , דרגת השיא 3, האורך ואין חזרות – מוחזר `true`.
•`{246, 12347, 1860}`: דרגת השיא 3 אבל האורך 3 (חסרה דרגה 2) – מוחזר `false`.
•`{246, 1860, 13}`: הדרגות – מוחזר `true`.
תשובה: הפעולה `IsFullArray` (ב-Java: `isFullArray`) שלמעלה.
שאלה 6 · מזהי מכשירים במחרוזות: תקינות, חדר ושמות
במערכת `"SmartHome"` כל מכשיר מקבל מזהה ייחודי (`string`; ב-Java: `String`) המורכב משם החדר, התו נקודתיים (`":"`) ושם מכשיר.
לדוגמה: `"KITCHEN:LIGHT"`, `"ROOM_2:TV"`, `"MICROWAVE:KITCHEN"`.
כתבו פעולה המקבלת מחרוזת המייצגת מזהה מכשיר. הפעולה תבדוק אם המזהה תקין. אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`. מזהה תקין הוא מחרוזת שמתקיימים בה שני תנאים:
•היא מכילה בדיוק פעם אחת את התו נקודתיים (`":"`);
•התו נקודתיים אינו מופיע בתחילת המחרוזת ואינו מופיע בסופה.
כותרת הפעולה:
public static bool IsValidDevice(string deviceId)public static boolean isValidDevice(String deviceId)כדי לייעל את צריכת החשמל, על המערכת לדעת אם שני מכשירים נמצאים באותו החדר.
כתבו פעולה המקבלת שתי מחרוזות `dev1` ו-`dev2` המייצגות מזהי מכשירים. הפעולה תבדוק אם שני המכשירים נמצאים באותו החדר. אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static bool AreInSameRoom(string dev1, string dev2)public static boolean areInSameRoom(String dev1, String dev2)כתבו פעולה המקבלת מערך של מחרוזות `allDevices` ומחרוזת נוספת `roomName`. הפעולה תחזיר מערך חדש המכיל רק את שמות המכשירים הנמצאים בחדר `roomName`.
כותרת הפעולה:
public static string[] GetDevicesInRoom(string[] allDevices,
string roomName)public static String[] args getDevicesInRoom(String[] allDevices,
String roomName)לדוגמה: עבור החדר `roomName = "KITCHEN"` מערך המכשירים `allDevices` הבא
`allDevices ={"KITCHEN:LIGHT" ,"ROOM_2:TV" ,"KITCHEN:MICROWAVE"}`
הפעולה תחזיר מערך חדש `{"LIGHT", "MICROWAVE"}`.
אם לא נמצאו מכשירים בחדר המבוקש, הפעולה תחזיר מערך ריק, כלומר מערך באורך 0.
◂ פתרון מלא לשאלה 6
סעיף א
סופרים את התווים `':'`; אם המספר שונה מ-1 מוחזר `false`; אחרת מוחזר `true` רק אם התו הראשון והתו האחרון אינם `':'`.
1. פעם אחת בדיוק: עוברים על המחרוזת וסופרים כמה פעמים מופיע התו `':'`. אם המונה שונה מ-1 – המזהה לא תקין.
2. לא בהתחלה ולא בסוף: אחרי שידוע שיש בדיוק נקודתיים אחד, בודקים שהתו במקום 0 והתו האחרון (מקום אורך פחות 1) אינם `':'`.
כאשר המונה שווה ל-1 המחרוזת בוודאי אינה ריקה, ולכן הגישה לתו הראשון ולתו האחרון בטוחה.
public static bool IsValidDevice(string deviceId)
{
int count = 0; // מספר הנקודתיים במחרוזת
for (int i = 0; i < deviceId.Length; i++)
{
if (deviceId[i] == ':')
count++;
}
if (count != 1)
return false; // אין נקודתיים, או שיש יותר מפעם אחת
return deviceId[0] != ':' && deviceId[deviceId.Length - 1] != ':';
}public static boolean isValidDevice(String deviceId)
{
int count = 0; // מספר הנקודתיים במחרוזת
for (int i = 0; i < deviceId.length(); i++)
{
if (deviceId.charAt(i) == ':')
count++;
}
if (count != 1)
return false; // אין נקודתיים, או שיש יותר מפעם אחת
return deviceId.charAt(0) != ':' && deviceId.charAt(deviceId.length() - 1) != ':';
}דוגמאות: `"KITCHEN:LIGHT"` – נקודתיים אחד באמצע, מוחזר `true`; `":TV"` – נקודתיים בהתחלה, `false`; `"A:B:C"` – פעמיים, `false`; `"TV"` – אין נקודתיים, `false`.
תשובה: הפעולה `IsValidDevice` (ב-Java: `isValidDevice`) שלמעלה.
סעיף ב
גוזרים מכל מזהה את החלק שלפני `':'` (`Substring(0, IndexOf(':'))`) ומחזירים אם שני שמות החדרים שווים.
הרעיון: שם החדר הוא החלק של המזהה שלפני הנקודתיים. מכיוון שהמזהים תקינים, יש בכל אחד בדיוק נקודתיים אחד.
1. מוצאים את מקום הנקודתיים בכל מזהה בעזרת `IndexOf(':')` (ב-Java: `indexOf`).
2. גוזרים את תת-המחרוזת מתחילת המזהה עד הנקודתיים (לא כולל) – זה שם החדר.
3. משווים את שני שמות החדרים (ב-Java בעזרת `equals`, כי `==` משווה הפניות ולא תוכן).
שימו לב: לא מספיק לבדוק ש-`dev2` מתחיל ב-`room1`, כי למשל `"KITCHEN:TV"` ו-`"KITCHEN2:TV"` נמצאים בחדרים שונים. משווים את שם החדר המלא.
public static bool AreInSameRoom(string dev1, string dev2)
{
string room1 = dev1.Substring(0, dev1.IndexOf(':')); // שם החדר = החלק שלפני הנקודתיים
string room2 = dev2.Substring(0, dev2.IndexOf(':'));
return room1 == room2;
}public static boolean areInSameRoom(String dev1, String dev2)
{
String room1 = dev1.substring(0, dev1.indexOf(':')); // שם החדר = החלק שלפני הנקודתיים
String room2 = dev2.substring(0, dev2.indexOf(':'));
return room1.equals(room2);
}דוגמה: `"KITCHEN:LIGHT"` ו-`"KITCHEN:MICROWAVE"` – בשניהם החדר `"KITCHEN"`, מוחזר `true`; `"KITCHEN:LIGHT"` ו-`"ROOM_2:TV"` – מוחזר `false`.
תשובה: הפעולה `AreInSameRoom` (ב-Java: `areInSameRoom`) שלמעלה.
סעיף ג
שני מעברים: בראשון סופרים את המזהים שהחלק שלפני `':'` בהם שווה ל-`roomName`, יוצרים מערך בגודל זה, ובשני מעתיקים אליו את החלק שאחרי `':'`; עבור הדוגמה מוחזר `{"LIGHT", "MICROWAVE"}`.
(בכותרת ה-Java המודפסת מופיעה המילה `args` בטעות; הכותרת התקינה היא `public static String[] getDevicesInRoom(String[] allDevices, String roomName)`.)
הרעיון: גודל מערך נקבע ביצירתו, ולכן עובדים בשני מעברים:
1. ספירה: לכל מזהה מוצאים את מקום הנקודתיים `pos`, גוזרים את שם החדר `Substring(0, pos)` ומשווים ל-`roomName`. סופרים כמה מזהים מתאימים – `count`.
2. יצירה: יוצרים מערך מחרוזות חדש בגודל `count`. אם אין מכשירים בחדר, `count = 0` ומתקבל מערך באורך 0, כנדרש.
3. העתקה: עוברים שוב על המזהים, ולכל מזהה מתאים מעתיקים את שם המכשיר – החלק שאחרי הנקודתיים, `Substring(pos + 1)` – למקום הפנוי הבא `j` במערך החדש.
4. מחזירים את המערך החדש.
סיבוכיות: , כאשר מספר המזהים ו- אורך מזהה.
public static string[] GetDevicesInRoom(string[] allDevices, string roomName)
{
// מעבר ראשון: ספירת המכשירים שבחדר, כדי לדעת את גודל המערך החדש
int count = 0;
for (int i = 0; i < allDevices.Length; i++)
{
int pos = allDevices[i].IndexOf(':');
if (allDevices[i].Substring(0, pos) == roomName)
count++;
}
// מעבר שני: העתקת שמות המכשירים (החלק שאחרי הנקודתיים)
string[] result = new string[count];
int j = 0; // המקום הפנוי הבא ב-result
for (int i = 0; i < allDevices.Length; i++)
{
int pos = allDevices[i].IndexOf(':');
if (allDevices[i].Substring(0, pos) == roomName)
{
result[j] = allDevices[i].Substring(pos + 1);
j++;
}
}
return result;
}public static String[] getDevicesInRoom(String[] allDevices, String roomName)
{
// מעבר ראשון: ספירת המכשירים שבחדר, כדי לדעת את גודל המערך החדש
int count = 0;
for (int i = 0; i < allDevices.length; i++)
{
int pos = allDevices[i].indexOf(':');
if (allDevices[i].substring(0, pos).equals(roomName))
count++;
}
// מעבר שני: העתקת שמות המכשירים (החלק שאחרי הנקודתיים)
String[] result = new String[count];
int j = 0; // המקום הפנוי הבא ב-result
for (int i = 0; i < allDevices.length; i++)
{
int pos = allDevices[i].indexOf(':');
if (allDevices[i].substring(0, pos).equals(roomName))
{
result[j] = allDevices[i].substring(pos + 1);
j++;
}
}
return result;
}`count = 2`, והמערך המוחזר הוא `{"LIGHT", "MICROWAVE"}`.
תשובה: הפעולה `GetDevicesInRoom` (ב-Java: `getDevicesInRoom`) שלמעלה.
שאלה 7 · מעקב: ספרה מינימלית ומקסימלית במחלקה
נתונה המחלקה `DigitInfo`:
class DigitInfo {
private int dig1;
private int dig2;
public DigitInfo(int num) {
if (num < 0) num = num * (-1);
int dig = num % 10;
this.dig1 = dig;
this.dig2 = dig;
num = num / 10;
while (num > 0) {
dig = num % 10;
if (dig < this.dig1)
this.dig1 = dig;
else if (dig > this.dig2)
this.dig2 = dig;
num = num / 10;
}
}
public override string ToString() {
return this.dig1 + "," + this.dig2;
}
public int Combine() {
return this.dig1 + this.dig2;
}
}class DigitInfo {
private int dig1;
private int dig2;
public DigitInfo(int num) {
if (num < 0) num = num * (-1);
int dig = num % 10;
this.dig1 = dig;
this.dig2 = dig;
num = num / 10;
while (num > 0) {
dig = num % 10;
if (dig < this.dig1)
this.dig1 = dig;
else if (dig > this.dig2)
this.dig2 = dig;
num = num / 10;
}
}
public String toString() {
return this.dig1 + "," + this.dig2;
}
public int combine() {
return this.dig1 + this.dig2;
}
}עקבו אחרי ביצוע קטע הקוד שלפניכם ורשמו מה יהיה הפלט:
DigitInfo info = new DigitInfo(48291);
Console.WriteLine(info);
Console.WriteLine(info.Combine());DigitInfo info = new DigitInfo(48291);
System.out.println(info);
System.out.println(info.combine());מהו הערך הגדול ביותר ומהו הערך הקטן ביותר שיכולה להחזיר הפעולה `Combine()`?
נתונה הפעולה `Mystery`:
public static void Mystery(int[] arr) {
DigitInfo temp1 = new DigitInfo(arr[0]);
DigitInfo temp2 = new DigitInfo(arr[0]);
int ind1 = 0;
int ind2 = 0;
DigitInfo cur;
for (int i = 1; i < arr.Length; i++) {
cur = new DigitInfo(arr[i]);
if (cur.Combine() > temp1.Combine()) {
temp2 = temp1;
temp1 = cur;
ind2 = ind1;
ind1 = i;
} else {
if (cur.Combine() > temp2.Combine()) {
temp2 = cur;
ind2 = i;
}
}
}
Console.WriteLine(arr[ind1]+" "+arr[ind2]);
}public static void mystery(int[] arr) {
DigitInfo temp1 = new DigitInfo(arr[0]);
DigitInfo temp2 = new DigitInfo(arr[0]);
int ind1 = 0;
int ind2 = 0;
DigitInfo cur;
for (int i = 1; i < arr.length; i++) {
cur = new DigitInfo(arr[i]);
if (cur.combine() > temp1.combine()) {
temp2 = temp1;
temp1 = cur;
ind2 = ind1;
ind1 = i;
} else {
if (cur.combine() > temp2.combine()) {
temp2 = cur;
ind2 = i;
}
}
}
System.out.println(arr[ind1]+" "+arr[ind2]);
}עקבו אחרי ביצוע קטע הקוד שלפניכם ורשמו מה יהיה הפלט:
int[] a = {3458,45, 7341, 6, 13579, 86 };
Mystery(a);int[] a = {3458,45, 7341, 6, 13579, 86 };
mystery(a);◂ פתרון מלא לשאלה 7
סעיף א
הפלט: `1,9` ובשורה הבאה `10`.
מה עושה הבנאי: `dig1` ו-`dig2` מאותחלים בספרת האחדות. אחר כך, לכל ספרה נוספת: אם היא קטנה מ-`dig1` היא נשמרת ב-`dig1`, ואם היא גדולה מ-`dig2` היא נשמרת ב-`dig2`. כך `dig1` היא הספרה הקטנה ביותר ו-`dig2` הספרה הגדולה ביותר במספר.
(בעמודת `num` מופיע הערך אחרי החלוקה ב-10 בסוף השלב.)
1. הדפסת העצם `info` מפעילה את `ToString` (ב-Java: `toString`), שמחזירה `dig1 + "," + dig2`, כלומר `1,9`.
2. `Combine` מחזירה .
תשובה: יודפס
1,9
10סעיף ב
הגדול ביותר 18, הקטן ביותר 0.
`Combine` מחזירה את סכום הספרה הקטנה ביותר והספרה הגדולה ביותר של המספר (בערכו המוחלט). כל ספרה היא בין 0 ל-9.
1. המקסימום: – מתקבל כשהספרה הקטנה ביותר היא 9, כלומר כל הספרות הן 9 (למשל 9, 99, -999).
2. המינימום: – מתקבל רק כשגם הספרה הגדולה ביותר היא 0, כלומר עבור המספר 0.
(מקרה קצה טכני בלבד: עבור הערך השלילי הקטן ביותר של `int`, הכפלה ב- גולשת וחוזרת לאותו ערך שלילי, והפעולה תחזיר . למספרים רגילים התחום הוא 0 עד 18.)
תשובה: הערך הגדול ביותר הוא 18 והקטן ביותר הוא 0.
סעיף ג
יודפס `86 6`.
הרעיון של הפעולה: `temp1` שומר את העצם עם ערך `Combine` הגדול ביותר עד כה (ומקומו ב-`ind1`), ו-`temp2` את השני בגודלו (מקומו ב-`ind2`). כשמגיע ערך גדול מהמקסימום – המקסימום הישן "יורד" למקום השני.
1. ערכי `Combine` של האיברים (ספרה קטנה + ספרה גדולה):
2. מעקב אחר הלולאה (בהתחלה `temp1` ו-`temp2` שניהם של 3458, כלומר 11, ו-`ind1 = ind2 = 0`):
3. בסוף `ind1 = 5` ו-`ind2 = 3`, ומודפס `arr[5] + " " + arr[3]`.
תשובה: יודפס `86 6`.
שאלה 8 · פסגות במערך דו-ממדי
•מסגרת מערך הדו-ממדי מורכבת מתאים הנמצאים בשורה 0, בעמודה 0, בשורה אחרונה ובעמודה אחרונה.
•תא פנימי במערך דו-ממדי הוא איבר שאינו נמצא במסגרת המערך.
•תא פנימי במערך נקרא "פסגה" אם הערך המאוחסן בו גדול מכל הערכים שבשמונת שכניו (כלומר, התאים הסמוכים לו).
•התא במיקום (1,1) הוא "פסגה" כיוון שערכו (10) גדול מכל שכניו (המסומנים באפור).
•גם התא במיקום (3,2) הוא "פסגה" (ערכו 21).
•גם התא (1,4) הוא "פסגה".

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום איבר במערך `row` (שורה) ו-`col` (עמודה). הפעולה תבדוק אם האיבר במיקום זה `arr[row, col]` (ב-Java: `arr[row][col]`) הוא "פסגה". אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static bool IsPeak(int[,] arr, int row, int col)public static boolean isPeak(int[][] arr, int row, int col)כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr`. הפעולה תחזיר מערך חד-ממדי המכיל את הערכים של כל "הפסגות" הקיימות במערך `arr`. אם אין שום "פסגה" במערך, הפעולה תחזיר `null`.
כותרת הפעולה:
public static int[] GetPeaksArray(int[,] arr)public static int[] getPeaksArray(int[][] arr)מהי סיבוכיות זמן הריצה של כל הפעולות שכתבתם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
אם התא אינו פנימי (`row` לא בין 1 לשורה הלפני אחרונה, או `col` לא בין 1 לעמודה הלפני אחרונה) מוחזר `false`; אחרת עוברים על 8 השכנים ומחזירים `false` אם אחד מהם גדול מהתא או שווה לו, אחרת `true`.
1. תא פנימי: "פסגה" מוגדרת רק לתא פנימי. לכן אם `row` הוא 0 או השורה האחרונה, או `col` הוא 0 או העמודה האחרונה (או מחוץ לתחום) – מחזירים `false`. תנאי זה גם מבטיח שלא ניגש מחוץ לגבולות המערך כשנבדוק שכנים.
2. שמונת השכנים: השכנים נמצאים בשורות `row-1` עד `row+1` ובעמודות `col-1` עד `col+1`, פרט לתא עצמו. עוברים עליהם בלולאה כפולה ומדלגים על התא `(row, col)`.
3. התא חייב להיות גדול מכל שכניו, ולכן אם שכן כלשהו גדול ממנו או שווה לו – מחזירים `false`.
4. אם כל השכנים קטנים ממנו – מחזירים `true`.
public static bool IsPeak(int[,] arr, int row, int col)
{
int rows = arr.GetLength(0);
int cols = arr.GetLength(1);
// תא במסגרת (או מחוץ למערך) אינו תא פנימי ולכן אינו "פסגה"
if (row < 1 || row > rows - 2 || col < 1 || col > cols - 2)
return false;
for (int i = row - 1; i <= row + 1; i++)
{
for (int j = col - 1; j <= col + 1; j++)
{
if ((i != row || j != col) && arr[i, j] >= arr[row, col])
return false; // שכן שגדול מהתא או שווה לו
}
}
return true;
}public static boolean isPeak(int[][] arr, int row, int col)
{
int rows = arr.length;
int cols = arr[0].length;
// תא במסגרת (או מחוץ למערך) אינו תא פנימי ולכן אינו "פסגה"
if (row < 1 || row > rows - 2 || col < 1 || col > cols - 2)
return false;
for (int i = row - 1; i <= row + 1; i++)
{
for (int j = col - 1; j <= col + 1; j++)
{
if ((i != row || j != col) && arr[i][j] >= arr[row][col])
return false; // שכן שגדול מהתא או שווה לו
}
}
return true;
}בדיקה מול הדוגמה: התא (1,1) ערכו 10, ושכניו – כולם קטנים מ-10, לכן מוחזר `true`. התא (2,3) ערכו 10, אבל שכנו (1,4) ערכו 123, לכן מוחזר `false`. התא (0,0) נמצא במסגרת – מוחזר `false`.
תשובה: הפעולה `IsPeak` (ב-Java: `isPeak`) שלמעלה.
סעיף ב
שני מעברים על התאים הפנימיים בעזרת `IsPeak`: הראשון סופר את הפסגות (אם 0 – מוחזר `null`), השני ממלא מערך בגודל זה בערכי הפסגות; עבור המערך שבאיור מוחזר `{10, 123, 21}`.
הרעיון: מספר הפסגות לא ידוע מראש, וגודל המערך נקבע ביצירתו – לכן שני מעברים:
1. ספירה: עוברים על כל התאים הפנימיים (שורות 1 עד הלפני אחרונה, עמודות 1 עד הלפני אחרונה) וסופרים את התאים שעבורם הפעולה מסעיף א מחזירה `true`. אין צורך לבדוק את המסגרת – תא במסגרת אינו פסגה.
2. אם לא נמצאה אף פסגה – מחזירים `null`.
3. מילוי: יוצרים מערך בגודל המונה, עוברים שוב על התאים הפנימיים ומעתיקים את ערכי הפסגות למקום הפנוי הבא `k`.
public static int[] GetPeaksArray(int[,] arr)
{
int rows = arr.GetLength(0);
int cols = arr.GetLength(1);
// מעבר ראשון: ספירת הפסגות (רק תאים פנימיים)
int count = 0;
for (int i = 1; i < rows - 1; i++)
for (int j = 1; j < cols - 1; j++)
if (IsPeak(arr, i, j))
count++;
if (count == 0)
return null; // אין אף פסגה
// מעבר שני: העתקת ערכי הפסגות למערך החדש
int[] peaks = new int[count];
int k = 0;
for (int i = 1; i < rows - 1; i++)
for (int j = 1; j < cols - 1; j++)
if (IsPeak(arr, i, j))
{
peaks[k] = arr[i, j];
k++;
}
return peaks;
}public static int[] getPeaksArray(int[][] arr)
{
int rows = arr.length;
int cols = arr[0].length;
// מעבר ראשון: ספירת הפסגות (רק תאים פנימיים)
int count = 0;
for (int i = 1; i < rows - 1; i++)
for (int j = 1; j < cols - 1; j++)
if (isPeak(arr, i, j))
count++;
if (count == 0)
return null; // אין אף פסגה
// מעבר שני: העתקת ערכי הפסגות למערך החדש
int[] peaks = new int[count];
int k = 0;
for (int i = 1; i < rows - 1; i++)
for (int j = 1; j < cols - 1; j++)
if (isPeak(arr, i, j))
{
peaks[k] = arr[i][j];
k++;
}
return peaks;
}דוגמה: עבור המערך שבאיור, הפסגות לפי סדר המעבר (שורה אחר שורה) הן (1,1), (1,4), (3,2), ולכן מוחזר `{10, 123, 21}`.
תשובה: הפעולה `GetPeaksArray` (ב-Java: `getPeaksArray`) שלמעלה.
סעיף ג
`IsPeak` – ; `GetPeaksArray` – , כאשר מספר השורות ו- מספר העמודות.
1. `IsPeak`: בודקת לכל היותר 9 תאים (3 שורות על 3 עמודות) – מספר קבוע של פעולות שאינו תלוי בגודל המערך. לכן הסיבוכיות היא .
2. `GetPeaksArray`: עוברת פעמיים על התאים הפנימיים – כ- תאים בכל מעבר – ולכל תא מזמנת את `IsPeak`, שעולה . סך הכול כ-, כלומר , כאשר מספר השורות ו- מספר העמודות (ליניארי במספר התאים במערך).
תשובה: `IsPeak` – ; `GetPeaksArray` – .
שאלה 9 · קווי אוטובוס: זמן, מסלול ומערכת קווים
חברת "דן" מעוניינת למחשב את שירותי המודיעין שלה עבור קווי האוטובוס בעיר. לצורך כך הוגדרו שלוש מחלקות: `Time`, `BusRoute` ו-`CityTransport`.
המחלקה `Time` מייצגת נקודת זמן לפי מספר שעות ומספר דקות.
public class Time{
private int hour;
private int minute;במחלקה הוגדרו שתי פעולות בונות:
// הפעולה מקבלת שעה h ודקה m
public Time(int h, int m){
this.hour = h;
this.minute = m;
}
// הפעולה מקבלת מספר דקות totalMin שעברו מחצות
public Time(int totalMin){
this.hour = totalMin / 60;
this.minute = totalMin % 60;
}לדוגמה: אם עברו 210 דקות נקודת הזמן הנוכחית היא 3:30.
במחלקה `Time` הוגדרו פעולות Get (ב-Java: get) וגם פעולה `minFromMidnight` המחזירה את מספר הדקות שעברו מחצות (0:00). אין צורך לממש אותן!
כתבו במחלקה `Time` את הפעולה `Add` (ב-Java: `add`) המקבלת את המספר השלם החיובי `minToAdd`. הפעולה תחזיר אובייקט חדש מסוג `Time` המייצג את נקודת הזמן לאחר הוספת `minToAdd` דקות לזמן הנוכחי.
כותרת הפעולה:
public Time Add(int minToAdd)public Time add(int minToAdd)לדוגמה, אם האובייקט הנוכחי הוא 8:30 והפעולה קיבלה 45, יוחזר אובייקט חדש המייצג את נקודת הזמן 9:15.
המחלקה `BusRoute` מייצגת מסלול של קו אוטובוס. תכונות המחלקה:
•`lineNo` – מספר קו (למשל: `"61"`) – מטיפוס מחרוזת, `string` (ב-Java: `String`);
•`stops` – מערך השמות של תחנות העצירה, מסלול – מטיפוס מערך מחרוזות, `string[]` (ב-Java: `String[]`);
•`durations` – מערך מספרים שלמים – `int[]`. הערך `k` במערך מציין את מספר הדקות הדרושות לאוטובוס כדי להגיע מתחנה `k` לתחנה `k+1`.
אם המערך `stops` הוא:
והמערך `durations` הוא:
האוטובוס נוסע 12 דקות מעמידר לקניון איילון, 15 דקות מקניון איילון לבורסה, 10 דקות מהבורסה למיניסטור לונדון, 8 דקות ממיניסטור לונדון לכרמלית.
במחלקה `BusRoute` הוגדרו פעולות Get (ב-Java: get). אין צורך לממש אותן!
כתבו במחלקה `BusRoute` את שתי הפעולות הבאות:
פעולה בוליאנית המקבלת שמות של שתי תחנות `st1` ו-`st2` ובודקת האם ניתן להגיע מ-`st1` ל-`st2` באמצעות קו זה (כלומר, ששתיהן קיימות במערך תחנות ו-`st2` מופיעה אחרי `st1`).
כותרת הפעולה:
public bool IsRoutePossible(string st1, string st2)public boolean isRoutePossible(String st1, String st2)פעולה המקבלת שם של תחנת יעד `stopName` וזמן יציאה למסלול `startTime`. הפעולה תחזיר את זמן ההגעה לתחנה זו. אפשר להניח שהתחנה `stopName` קיימת במסלול.
כותרת הפעולה:
public Time GetArrivalTime(Time startTime, string stopName)public Time getArrivalTime(Time startTime, String stopName)המחלקה `CityTransport` מייצגת מערכת הקווים העירונית. למחלקה תכונה אחת:
•`BusRoute[] routes` – מערך של עצמים מסוג קו אוטובוס
כתבו במחלקה `CityTransport` את הפעולה המקבלת תחנת מוצא ותחנת יעד. הפעולה תדפיס מספרי הקווים (`lineNo`) המאפשרים נסיעה מתחנת מוצא לתחנת יעד.
כותרת הפעולה:
public void PrintRelevantLines(string origin, string destination)public void printRelevantLines(String origin, String destination)◂ פתרון מלא לשאלה 9
סעיף א
מחשבים `total = minFromMidnight() + minToAdd` (ומצמצמים ב-`% 1440` למעבר חצות) ומחזירים `new Time(total)`; עבור 8:30 ו-45 מתקבל 9:15.
הרעיון: הדרך הנוחה לחבר זמנים היא לעבור לדקות: כך לא צריך לטפל בנפרד ב"גלישה" של הדקות לשעה הבאה.
1. מחשבים כמה דקות עברו מחצות עד הזמן הנוכחי – `minFromMidnight()` – ומוסיפים את `minToAdd`.
2. יוצרים עצם חדש בעזרת הבנאי שמקבל מספר דקות מחצות; הבנאי עצמו מפרק אותו לשעות (`/ 60`) ולדקות (`% 60`).
3. אם הסכום עובר את חצות (1440 דקות ביממה), מצמצמים אותו בעזרת `% (24 * 60)` כדי שהשעה תהיה בין 0 ל-23. (השאלה לא מחייבת זאת, אבל כך השעה נשארת תקינה.)
העצם הנוכחי אינו משתנה – מוחזר עצם חדש, כנדרש.
public Time Add(int minToAdd)
{
int total = this.minFromMidnight() + minToAdd; // דקות מחצות עד הזמן החדש
total = total % (24 * 60); // מעבר חצות מתחיל יום חדש
return new Time(total);
}public Time add(int minToAdd)
{
int total = this.minFromMidnight() + minToAdd; // דקות מחצות עד הזמן החדש
total = total % (24 * 60); // מעבר חצות מתחיל יום חדש
return new Time(total);
}בדיקה מול הדוגמה: 8:30 הוא דקות מחצות. , ו-, , כלומר 9:15.
תשובה: הפעולה `Add` (ב-Java: `add`) שלמעלה.
סעיף ב
מוצאים את המיקומים `ind1`, `ind2` של שתי התחנות במערך `stops` (-1 אם לא נמצאה) ומחזירים `ind1 != -1 && ind2 != -1 && ind1 < ind2`.
הרעיון: האוטובוס נוסע רק בכיוון המסלול – מתחנה `k` לתחנה `k+1`. לכן אפשר להגיע מ-`st1` ל-`st2` רק אם שתיהן במסלול ו-`st2` נמצאת אחרי `st1` במערך.
1. מאתחלים `ind1 = -1` ו-`ind2 = -1` (סימן ל"לא נמצאה").
2. עוברים על מערך התחנות ושומרים את מיקום `st1` ב-`ind1` ואת מיקום `st2` ב-`ind2`. (ב-Java משווים מחרוזות עם `equals`.)
3. מחזירים `true` רק אם שתי התחנות נמצאו וגם `ind1 < ind2`. עבור `st1 == st2` מתקבל `ind1 == ind2`, ולכן מוחזר `false` – אין נסיעה מתחנה לעצמה.
הפעולה נכתבת בתוך המחלקה, ולכן ניגשים ישירות לתכונה `stops`.
public bool IsRoutePossible(string st1, string st2)
{
int ind1 = -1; // מיקום st1 במסלול
int ind2 = -1; // מיקום st2 במסלול
for (int i = 0; i < this.stops.Length; i++)
{
if (this.stops[i] == st1)
ind1 = i;
if (this.stops[i] == st2)
ind2 = i;
}
return ind1 != -1 && ind2 != -1 && ind1 < ind2;
}public boolean isRoutePossible(String st1, String st2)
{
int ind1 = -1; // מיקום st1 במסלול
int ind2 = -1; // מיקום st2 במסלול
for (int i = 0; i < this.stops.length; i++)
{
if (this.stops[i].equals(st1))
ind1 = i;
if (this.stops[i].equals(st2))
ind2 = i;
}
return ind1 != -1 && ind2 != -1 && ind1 < ind2;
}דוגמה: עבור המסלול בשאלה, `IsRoutePossible("עמידר", "בורסה")` מחזירה `true` (מקום 0 לפני מקום 2), ו-`IsRoutePossible("בורסה", "עמידר")` מחזירה `false`.
תשובה: הפעולה `IsRoutePossible` (ב-Java: `isRoutePossible`) שלמעלה.
סוכמים את `durations[0]` עד `durations[k-1]`, כאשר `k` מיקום `stopName`, ומחזירים `startTime.Add(sum)`; למשל יציאה ב-8:00 לבורסה – דקות, הגעה ב-8:27.
הרעיון: האוטובוס יוצא מהתחנה הראשונה (מקום 0) בזמן `startTime`. כדי להגיע לתחנה במקום `k` הוא עובר את הקטעים , , ..., , ולכן זמן הנסיעה הוא `durations[0] + ... + durations[k-1]`.
1. מאתחלים `sum = 0` ו-`k = 0`.
2. כל עוד התחנה במקום `k` אינה `stopName` – מוסיפים ל-`sum` את זמן הקטע `durations[k]` ומתקדמים לתחנה הבאה. מכיוון שהתחנה קיימת במסלול, הלולאה תיעצר.
3. מחזירים את זמן היציאה ועוד `sum` דקות, בעזרת הפעולה `Add` מסעיף א. אם `stopName` היא התחנה הראשונה, `sum = 0` ומוחזר זמן שווה לזמן היציאה.
public Time GetArrivalTime(Time startTime, string stopName)
{
int sum = 0; // סכום דקות הנסיעה מתחנת המוצא
int k = 0;
while (this.stops[k] != stopName)
{
sum += this.durations[k]; // זמן הנסיעה מתחנה k לתחנה k+1
k++;
}
return startTime.Add(sum);
}public Time getArrivalTime(Time startTime, String stopName)
{
int sum = 0; // סכום דקות הנסיעה מתחנת המוצא
int k = 0;
while (!this.stops[k].equals(stopName))
{
sum += this.durations[k]; // זמן הנסיעה מתחנה k לתחנה k+1
k++;
}
return startTime.add(sum);
}דוגמה: יציאה ב-8:00 ותחנת יעד "בורסה" (מקום 2): , ולכן זמן ההגעה הוא 8:27. לכרמלית (מקום 4): , הגעה ב-8:45.
תשובה: הפעולה `GetArrivalTime` (ב-Java: `getArrivalTime`) שלמעלה.
סעיף ג
עוברים על המערך `routes`, ולכל קו שעבורו `IsRoutePossible(origin, destination)` מחזירה `true` מדפיסים `GetLineNo()`.
הרעיון: את הבדיקה אם קו מאפשר נסיעה בין שתי תחנות כבר כתבנו בסעיף ב.1, ולכן כאן רק עוברים על כל הקווים ומשתמשים בה:
1. לכל קו `routes[i]` מזמנים `IsRoutePossible(origin, destination)`.
2. אם הוחזר `true` – מדפיסים את מספר הקו. התכונה `lineNo` פרטית במחלקה `BusRoute`, ולכן ניגשים אליה דרך פעולת ה-Get (הנחנו ששמה `GetLineNo`; ב-Java: `getLineNo`).
public void PrintRelevantLines(string origin, string destination)
{
for (int i = 0; i < this.routes.Length; i++)
{
if (this.routes[i].IsRoutePossible(origin, destination))
Console.WriteLine(this.routes[i].GetLineNo());
}
}public void printRelevantLines(String origin, String destination)
{
for (int i = 0; i < this.routes.length; i++)
{
if (this.routes[i].isRoutePossible(origin, destination))
System.out.println(this.routes[i].getLineNo());
}
}תשובה: הפעולה `PrintRelevantLines` (ב-Java: `printRelevantLines`) שלמעלה.
שאלה 10 · רקורסיה: ספרות יורדות וחלוקת מערך
נתונה הפעולה `What` המקבלת מספר שלם חיובי `n`:
public static bool What(int n) {
if (n < 10) return true;
return What(n / 10, n % 10);
}
private static bool What(int n, int k) {
if (n == 0) return true;
if (n % 10 <= k) return false;
return What(n / 10, n % 10);
}public static boolean what(int n) {
if (n < 10) return true;
return what(n / 10, n % 10);
}
private static boolean what(int n, int k) {
if (n == 0) return true;
if (n % 10 <= k) return false;
return what(n / 10, n % 10);
}מה תהיה תוצאת זימון הפעולה `What(8652)`? יש להראות מעקב.
תנו דוגמה למספר תלת-ספרתי `n` שעבורו תוצאת זימון הפעולה `What(n)` תהיה `true`.
מה מבצעת הפעולה `What(n)` באופן כללי עבור מספר שלם חיובי `n`?
נתונה הפעולה `Secret` המקבלת מערך מספרים שלמים:
public static void Secret(int[] a) {
Secret(a, 0, a.Length-1);
}
private static void Secret(int[] a, int low, int high) {
if (low < high) {
if (What(a[low])) {
Secret(a, low + 1, high);
} else if (!What(a[high])) {
Secret(a, low, high - 1);
} else {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
Secret(a, low + 1, high - 1);
}
}
}public static void secret(int[] a) {
secret(a, 0, a.length-1);
}
private static void secret(int[] a, int low, int high) {
if (low < high) {
if (what(a[low])) {
secret(a, low + 1, high);
} else if (!what(a[high])) {
secret(a, low, high - 1);
} else {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
secret(a, low + 1, high - 1);
}
}
}עקבו אחרי זימון הפעולה `Secret(a)` עבור המערך הבא:
`int[] a = {17, 863, 19, 542, 123,542};`
רשמו מה תהיה התוצאה של הזימון. יש להראות מעקב.
תנו דוגמה של מערך `b` הכולל חמישה מספרים תלת-ספרתיים, כך שזימון הפעולה `Secret(b)` לא יגרום לשינוי במערך.
תנו דוגמה של מערך `c` הכולל חמישה מספרים תלת-ספרתיים, כך שזימון הפעולה `Secret(c)` יגרום להפיכת סדר איברים במערך.
מה מבצעת הפעולה `Secret` באופן כללי עבור מערך של מספרים שלמים חיוביים?
◂ פתרון מלא לשאלה 10
סעיף א
`true`.
הפעולה החיצונית מעבירה לפעולת העזר את המספר בלי ספרת האחדות (`n / 10`) ואת ספרת האחדות (`n % 10`) בתור `k`. פעולת העזר בודקת שספרת האחדות של `n` גדולה מ-`k` (הספרה שהייתה מימינה), וממשיכה שמאלה.
הערך `true` חוזר לאורך כל שרשרת הזימונים.
תשובה: `What(8652)` מחזירה `true`.
למשל `n = 321`.
לפי המעקב בסעיף 1, הפעולה מחזירה `true` כשכל ספרה גדולה ממש מהספרה שמימינה. נבחר מספר תלת-ספרתי שספרותיו יורדות משמאל לימין: `321`.
בדיקה: `What(321)` → `What(32, 1)`: ? לא → `What(3, 2)`: ? לא → `What(0, 3)` → `true`.
תשובה: `n = 321` (וגם למשל 210, 975, 863).
מחזירה `true` אם ספרות `n` יורדות ממש משמאל לימין (כל ספרה גדולה מהספרה שמימינה), אחרת `false`; מספר חד-ספרתי מחזיר `true`.
1. מספר חד-ספרתי – מוחזר `true` מיד.
2. אחרת פעולת העזר משווה כל פעם ספרה לספרה שמימינה (`k`): אם הספרה השמאלית קטנה או שווה ל-`k` – מוחזר `false`. אם עברנו את כל הספרות (`n == 0`) בלי כישלון – מוחזר `true`.
למשל `What(123)` מחזירה `false` (כבר ), ו-`What(8662)` מחזירה `false` (כי ).
תשובה: הפעולה בודקת אם ספרות המספר יורדות ממש משמאל לימין (כל ספרה גדולה מהספרה שמימינה לה). אם כן – מחזירה `true`, אחרת `false`.
סעיף ב
המערך הופך ל-`{542, 863, 542, 19, 123, 17}`.
הרעיון: `low` מתקדם מההתחלה ו-`high` מהסוף. איבר שעבורו `What` מחזירה `true` (ספרות יורדות) נשאר בצד שמאל, ואיבר שעבורו מוחזר `false` נשאר בצד ימין. כשמשמאל יש איבר `false` ומימין איבר `true` – מחליפים ביניהם.
1. ערכי `What` לאיברים (לפי סעיף א.3):
2. מעקב אחר הזימונים:
תשובה: אחרי הזימון המערך הוא `{542, 863, 542, 19, 123, 17}`.
למשל `b = {321, 432, 543, 654, 765}` (כל האיברים בעלי ספרות יורדות).
החלפה מתבצעת רק כשמשמאל יש איבר שעבורו `What` מחזירה `false` ומימין איבר שעבורו היא מחזירה `true`. אם כל האיברים בעלי ספרות יורדות, `What(a[low])` תמיד `true`, `low` רק מתקדם, ולא מתבצעת אף החלפה.
`b = {321, 432, 543, 654, 765}`: בכל זימון `What(b[low])` מחזירה `true`, והזימונים הם `(0,4)`, `(1,4)`, `(2,4)`, `(3,4)`, `(4,4)` – עצירה ללא החלפה.
(באופן כללי, כל מערך שבו כל איברי ה-`true` נמצאים לפני כל איברי ה-`false` לא ישתנה.)
תשובה: `b = {321, 432, 543, 654, 765}`.
למשל `c = {123, 456, 789, 321, 654}` – אחרי הזימון `{654, 321, 789, 456, 123}`.
הרעיון: הפיכת סדר של 5 איברים פירושה החלפת `c[0]` עם `c[4]` ו-`c[1]` עם `c[3]` (האיבר האמצעי נשאר במקומו). החלפה מתבצעת כש-`What(c[low])` מחזירה `false` ו-`What(c[high])` מחזירה `true`, ואחריה `low` ו-`high` מתקרבים יחד. לכן נבחר:
•`c[0]` ו-`c[1]` – ספרות לא יורדות (`What` מחזירה `false`): 123, 456.
•`c[3]` ו-`c[4]` – ספרות יורדות (`What` מחזירה `true`): 321, 654.
•`c[2]` – כל מספר, למשל 789.
התקבל המערך המקורי בסדר הפוך.
תשובה: `c = {123, 456, 789, 321, 654}`.
מסדרת מחדש את המערך כך שכל המספרים שספרותיהם יורדות ממש (`What` מחזירה `true`) נמצאים בתחילתו, ואחריהם כל שאר המספרים.
1. `low` מתקדם מתחילת המערך כל עוד האיבר בו "טוב" (`What` מחזירה `true`), ו-`high` נסוג מסוף המערך כל עוד האיבר בו "לא טוב".
2. כשמשמאל נמצא איבר "לא טוב" ומימין איבר "טוב" – מחליפים ביניהם וממשיכים פנימה.
3. כשהמצביעים נפגשים, כל האיברים שמשמאל הם "טובים" וכל האיברים שמימין "לא טובים".
זוהי חלוקה (partition) של המערך לשתי קבוצות, בדומה לשלב החלוקה במיון מהיר. הסדר הפנימי בתוך כל קבוצה אינו נשמר בהכרח.
תשובה: הפעולה משנה את סדר האיברים במערך כך שכל המספרים שספרותיהם יורדות ממש משמאל לימין יופיעו בתחילת המערך, ואחריהם יופיעו כל שאר המספרים.