מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2020 מועד ב'
הנדסת תוכנה · סמל 97104 · 13 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2020 מועד ב', כל 13 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: בבחינה זו, מותר לך לענות על מספר שאלות כרצונך, אך סך כל הנקודות שתוכל לצבור בכלל הבחינה לא יעלה על 120. ניתן לצבור נקודות גם מחלקי שאלות.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 15)
בכל מבחן 13 שאלות.
חלק א': שאלות 6-1 (ערך כל שאלה – 10 נקודות)
חלק ב': שאלות 9-7 (ערך כל שאלה – 12 נקודות)
חלק ג': שאלות 13-10 (ערך כל שאלה – 18 נקודות)
חומר עזר: 1. מחשבון. (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטת מחרוזות, הדפסת תווים ומונים
כתוב קטע תוכנית הקולטת 50 מחרוזות.
עבור כל מחרוזת באורך זוגי תודפס האות הראשונה במחרוזת, ועבור כל מחרוזת באורך אי זוגי תודפס האות האחרונה במחרוזת.
בנוסף, על התוכנית לחשב ולהדפיס:
•כמה מחרוזות מתחילות באות 'A'.
•כמה מחרוזות מסתיימות בספרה ('0'..'9').
◂ פתרון מלא לשאלה 1
פתרון
לולאה של 50 קליטות; לפי זוגיות האורך מודפס התו הראשון או האחרון; שני מונים - מחרוזות שמתחילות ב-'A' ומחרוזות שהתו האחרון שלהן בין '0' ל-'9' - מודפסים בסוף.
הרעיון: עוברים בלולאה 50 פעמים, ובכל סיבוב קולטים מחרוזת אחת ומטפלים בה מיד (אין צורך לשמור את כל המחרוזות):
1. מחשבים את האורך `len`. אם `len % 2 == 0` (אורך זוגי) מדפיסים את התו הראשון, במקום 0; אחרת מדפיסים את התו האחרון, במקום `len - 1`.
2. מונה `countA`: אם התו הראשון שווה ל-`'A'` מגדילים אותו ב-1.
3. מונה `countDigit`: התו האחרון הוא ספרה אם הוא בין `'0'` ל-`'9'` (התווים של הספרות רצופים בטבלת התווים), ואז מגדילים את המונה.
4. אחרי הלולאה מדפיסים את שני המונים.
ב-Java נעשה שימוש ב-`in` שהוגדר לפי ההנחיות (`Scanner in=new Scanner(System.in);`).
int countA = 0; // strings that start with 'A'
int countDigit = 0; // strings that end with a digit
for (int i = 0; i < 50; i++)
{
String str = in.next();
int len = str.length();
if (len % 2 == 0)
System.out.println(str.charAt(0));
else
System.out.println(str.charAt(len - 1));
if (str.charAt(0) == 'A')
countA++;
char last = str.charAt(len - 1);
if (last >= '0' && last <= '9')
countDigit++;
}
System.out.println("Start with A: " + countA);
System.out.println("End with a digit: " + countDigit);int countA = 0; // strings that start with 'A'
int countDigit = 0; // strings that end with a digit
for (int i = 0; i < 50; i++)
{
string str = Console.ReadLine();
int len = str.Length;
if (len % 2 == 0)
Console.WriteLine(str[0]);
else
Console.WriteLine(str[len - 1]);
if (str[0] == 'A')
countA++;
char last = str[len - 1];
if (last >= '0' && last <= '9')
countDigit++;
}
Console.WriteLine("Start with A: " + countA);
Console.WriteLine("End with a digit: " + countDigit);לדוגמה, עבור המחרוזות `Abc`, `hello`, `A1`, `xy9`: מודפסים `c` (אורך 3, אי זוגי - האחרונה), `o`, `A` (אורך 2, זוגי - הראשונה), `9`; המחרוזות שמתחילות ב-'A' הן `Abc` ו-`A1`, והמסתיימות בספרה הן `A1` ו-`xy9`.
תשובה: קטע התוכנית שלמעלה - לולאה של 50 קליטות, הדפסת התו הראשון או האחרון לפי זוגיות האורך, ושני מונים שמודפסים בסוף.
שאלה 2 · מערך עצמים: ממוצע והדפסת מעל הממוצע
במחלקה קופץ לרוחק – `Jumper` יש שתי תכונות:
שם – `name` מטיפוס מחרוזת, ומרחק הקפיצה הטובה ביותר – `score` מטיפוס ממשי.
כמו כן יש במחלקה פעולות `get/set` לכל אחת מהתכונות.
כתוב פעולה המקבלת מערך של קופצים לרוחק `arr`. הפעולה תחזיר ממוצע קפיצות.
כתוב פעולה המקבלת מערך של קופצים לרוחק `arr` ומדפיסה את שמותיהם של הקופצים, שתוצאת הקפיצה שלהם גבוהה מן הממוצע.
הנחה: כל תא במערך מכיל הפניה לקופץ ואין תאים ריקים (שערכם שווה ל-`null`).
◂ פתרון מלא לשאלה 2
סעיף א
סוכמים את `getScore()` של כל הקופצים ומחזירים את הסכום חלקי `arr.length`.
הרעיון: ממוצע = סכום התוצאות חלקי מספר הקופצים.
1. צובר `sum` מטיפוס ממשי מתחיל ב-0.
2. עוברים על כל תאי המערך ומוסיפים לצובר את תוצאת הקופץ, דרך פעולת הגישה `getScore()` (התכונה פרטית).
3. מחזירים `sum / arr.length`. מכיוון ש-`sum` ממשי, החילוק הוא חילוק ממשי.
לפי ההנחה אין תאים ריקים, ולכן אפשר לקרוא ל-`getScore()` על כל תא.
public static double average(Jumper[] arr)
{
double sum = 0;
for (int i = 0; i < arr.length; i++)
sum += arr[i].getScore();
return sum / arr.length;
}public static double Average(Jumper[] arr)
{
double sum = 0;
for (int i = 0; i < arr.Length; i++)
sum += arr[i].GetScore();
return sum / arr.Length;
}לדוגמה, עבור שלושה קופצים עם התוצאות 7.5, 6.0, 8.1 הסכום הוא 21.6 והממוצע .
תשובה: הפעולה `average` שלמעלה מחזירה את סכום התוצאות חלקי מספר הקופצים.
סעיף ב
מחשבים פעם אחת את הממוצע בעזרת הפעולה מסעיף א, ומדפיסים את `getName()` של כל קופץ ש-`getScore()` שלו גדול מהממוצע.
הרעיון: משתמשים בפעולה מסעיף א.
1. מחשבים את הממוצע פעם אחת, לפני הלולאה, ושומרים אותו במשתנה `avg` (אם נקרא ל-`average` בתוך הלולאה, נחשב אותו מחדש בכל סיבוב, וזה מיותר).
2. עוברים על המערך; עבור כל קופץ שתוצאתו גדולה ממש מהממוצע (`>`) מדפיסים את שמו בעזרת `getName()`.
public static void printAboveAverage(Jumper[] arr)
{
double avg = average(arr);
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getScore() > avg)
System.out.println(arr[i].getName());
}
}public static void PrintAboveAverage(Jumper[] arr)
{
double avg = Average(arr);
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetScore() > avg)
Console.WriteLine(arr[i].GetName());
}
}בדוגמה מסעיף א (ממוצע 7.2) יודפסו שמות הקופצים עם 7.5 ו-8.1.
סיבוכיות: מעבר אחד לחישוב הממוצע ומעבר אחד להדפסה - , כאשר הוא מספר הקופצים.
תשובה: הפעולה `printAboveAverage` שלמעלה.
שאלה 3 · מעקב: כפל בחיבור חוזר וחזקה
נתונה הפעולה `what` המקבלת כפרמטרים שני מספרים שלמים חיוביים:
public static int what(int a, int b)
{
int c = 0;
while(a > 0)
{
c = c + b;
a--;
}
return c;
}public static int What(int a, int b)
{
int c = 0;
while(a > 0)
{
c = c + b;
a--;
}
return c;
}עקוב בעזרת טבלת מעקב אחר הזימון: `what (4,3)` ורשום מה תחזיר הפעולה.
אילו ערכים צריך להעביר לפעולה `what` כדי שיוחזר הערך 15?
נתונה הטענה הבאה: `what(n1, n2)==what(n2, n1)` לכל זוג מספרים `n1>0, n2>0`.
האם הטענה נכונה? הסבר את תשובתך.
מה מבצעת הפעולה באופן כללי?
נתונה הפעולה `why` המקבלת כפרמטרים שני מספרים שלמים חיוביים:
public static int why(int x, int y)
{
int z=1;
while(y > 0)
{
z = what(z, x);
y--;
}
return z;
}public static int Why(int x, int y)
{
int z=1;
while(y > 0)
{
z = What(z, x);
y--;
}
return z;
}עקוב בעזרת טבלת מעקב אחר הזימון: `why (4,3)` ורשום מה תחזיר הפעולה?
אילו ערכים צריך להעביר לפעולה `why` כדי שיוחזר הערך 16?
נתונה הטענה הבאה: `why(n1, n2)==why(n2, n1)` לכל זוג מספרים `n1>0, n2>0`.
האם הטענה נכונה? הסבר את תשובתך.
מה מבצעת הפעולה באופן כללי?
◂ פתרון מלא לשאלה 3
סעיף א
`what(4,3)` מחזירה 12.
עוקבים אחרי המשתנים `a`, `b`, `c` בכל סיבוב של הלולאה. בכל סיבוב מוסיפים את `b` ל-`c` ומקטינים את `a` ב-1, עד ש-`a` מגיע ל-0.
הפעולה מחזירה את `c`.
תשובה: הפעולה מחזירה 12.
למשל `what(3,5)` או `what(5,3)` (גם `what(1,15)` או `what(15,1)`).
מהמעקב רואים שהפעולה מוסיפה את `b` ל-`c` בדיוק `a` פעמים, כלומר מחזירה . לכן צריך שני מספרים חיוביים שמכפלתם 15:
.
בדיקה עבור `what(3,5)`: , ואחרי שלושה סיבובים , והפעולה מחזירה 15.
תשובה: למשל `what(3,5)` או `what(5,3)` (וגם `what(1,15)`, `what(15,1)`).
נכונה: שני הזימונים מחזירים , והכפל חילופי.
`what(n1, n2)` מוסיפה את `n2` בדיוק `n1` פעמים, ולכן מחזירה .
`what(n2, n1)` מוסיפה את `n1` בדיוק `n2` פעמים, ולכן מחזירה .
מכיוון שהכפל חילופי (), שני הזימונים מחזירים אותו ערך (רק מספר הסיבובים בלולאה שונה). לדוגמה `what(4,3)` ו-`what(3,4)` מחזירות שתיהן 12.
תשובה: הטענה נכונה, כי שני הזימונים מחזירים את המכפלה .
מחזירה את המכפלה (כפל בעזרת חיבור חוזר).
הלולאה רצה `a` פעמים, ובכל פעם מוסיפה את `b` לצובר `c` שמתחיל ב-0. לכן בסוף
.
תשובה: הפעולה מחשבת ומחזירה את המכפלה בעזרת חיבור חוזר.
סעיף ב
`why(4,3)` מחזירה 64.
כאן ו-. בכל סיבוב `z` מוחלף ב-`what(z, x)`, כלומר (לפי סעיף א) ב-, ו-`y` קטן ב-1.
תשובה: הפעולה מחזירה 64.
למשל `why(2,4)` או `why(4,2)` (וגם `why(16,1)`).
מהמעקב רואים ש-`z` מתחיל ב-1 ומוכפל ב-`x` בדיוק `y` פעמים, כלומר הפעולה מחזירה . צריך :
, , .
בדיקה עבור `why(2,4)`: .
תשובה: למשל `why(2,4)` או `why(4,2)` (וגם `why(16,1)`).
לא נכונה: `why(2,3)` מחזירה ו-`why(3,2)` מחזירה .
`why(n1, n2)` מחזירה ו-`why(n2, n1)` מחזירה . חזקה אינה פעולה חילופית, ולכן מספיקה דוגמה נגדית אחת:
`why(2,3)` , אבל `why(3,2)` , ו-.
(יש זוגות שעבורם יש שוויון, למשל , או `why(2,4)` ו-`why(4,2)` ששתיהן 16 - אבל הטענה נדרשת לכל זוג.)
תשובה: הטענה אינה נכונה; דוגמה נגדית: `why(2,3)=8` ו-`why(3,2)=9`.
מחזירה את החזקה .
`z` מתחיל ב-1, ובכל אחד מ-`y` הסיבובים מוכפל ב-`x` (בעזרת `what`, שמחשבת מכפלה). לכן בסוף
.
תשובה: הפעולה מחשבת ומחזירה את בחזקת (), בעזרת כפל חוזר.
שאלה 4 · בדיקת מערך "מסודר" לפי סכומי חצאים
מערך של מספרים שלמים יקרא "מסודר" אם הוא מקיים את התנאים הבאים:
•גודל המערך ארבעה תאים לפחות.
•גודל המערך הוא מספר זוגי
•סכום האיברים הנמצאים בחצי הראשון של המערך שווה לסכום האיברים הנמצאים בחצי השני של המערך
המערך `arr={22, 56, 10, 13, 31, 44}` הוא "מערך מסודר" מאחר שהוא עונה על כל שלוש הדרישות:
•אורכו של המערך הוא 6 - גדול מ- 4 וזוגי.
•סכום האיברים בחצי הראשון במערך 88 (22+56+10) והוא שווה לסכום האיברים הנמצאים בחצי השני של המערך (13+31+44).
כתוב פעולה המקבלת מערך של מספרים שלמים ומחזירה ערך `true` אם הוא "מערך מסודר", אם לא, הפעולה תחזיר ערך `false`.
מהי סיבוכיות הפעולה מסעיף א'? הסבר את תשובתך.
◂ פתרון מלא לשאלה 4
סעיף א
אם האורך קטן מ-4 או אי זוגי - `false`; אחרת סוכמים את החצי הראשון ואת החצי השני בלולאה אחת ומחזירים האם הסכומים שווים.
1. תנאי סף: אם אורך המערך קטן מ-4 או אי זוגי (`n % 2 != 0`), המערך אינו מסודר - מחזירים `false` מיד.
2. סכומים: אורך כל חצי הוא . בלולאה אחת על מוסיפים את `arr[i]` לסכום החצי הראשון, ואת `arr[i + n/2]` (האיבר המתאים בחצי השני) לסכום החצי השני.
3. השוואה: מחזירים `true` אם שני הסכומים שווים, ו-`false` אחרת.
public static boolean isOrdered(int[] arr)
{
int n = arr.length;
if (n < 4 || n % 2 != 0)
return false;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n / 2; i++)
{
sum1 += arr[i]; // first half
sum2 += arr[i + n / 2]; // second half
}
return sum1 == sum2;
}public static bool IsOrdered(int[] arr)
{
int n = arr.Length;
if (n < 4 || n % 2 != 0)
return false;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n / 2; i++)
{
sum1 += arr[i]; // first half
sum2 += arr[i + n / 2]; // second half
}
return sum1 == sum2;
}בדיקה על הדוגמה: , ; , - מוחזר `true`. עבור `{1,2,3,4}`: - מוחזר `false`; עבור מערך באורך 2 או 5 - מוחזר `false` כבר בתנאי הסף.
תשובה: הפעולה `isOrdered` שלמעלה.
סעיף ב
, כאשר הוא אורך המערך: לולאה אחת של סיבובים עם מספר קבוע של פעולות בכל סיבוב.
נסמן ב- את מספר האיברים במערך.
1. בדיקת תנאי הסף - מספר קבוע של פעולות, .
2. הלולאה רצה פעמים, ובכל סיבוב שתי פעולות חיבור - בסך הכול כל אחד מ- האיברים נקרא פעם אחת.
3. ההשוואה וההחזרה - .
סך הכול - סיבוכיות לינארית.
תשובה: , כאשר הוא אורך המערך.
שאלה 5 · מעקב ושיפור בדיקת מערך ממוין
נתונה הפעולה `five()` המקבלת מערך של מספרים שלמים:
public static boolean five(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
for (int k = i + 1; k < arr.length; k++)
{
if (arr[i] > arr[k])
{
return false;
}
}
}
return true;
}public static bool Five(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int k = i + 1; k < arr.Length; k++)
{
if (arr[i] > arr[k])
{
return false;
}
}
}
return true;
}נתון המערך הבא: `int[] arr={3,5,7,6};`. עקוב בעזרת טבלת מעקב אחרי ביצוע הפעולה ורשום מה תחזיר הפעולה.
תן דוגמה למערך בגודל שישה תאים שעבורו הפעולה `five` תחזיר ערך `true`.
מה מבצעת הפעולה `five` באופן כללי?
מהי הסיבוכיות של הפעולה? הסבר את תשובתך.
האם אפשר לכתוב את הפעולה `five` בצורה יעילה יותר?
אם כן – הצע רעיון או כתוב את הפעולה היעילה יותר. אם לא – הסבר למה.
◂ פתרון מלא לשאלה 5
סעיף א
הפעולה מחזירה `false` (כאשר , : ).
הלולאה החיצונית בוחרת איבר `arr[i]`, והפנימית משווה אותו לכל איבר שאחריו `arr[k]`. ברגע שנמצא איבר קודם הגדול מאיבר מאוחר - מוחזר `false` והמעקב נעצר.
תשובה: הפעולה מחזירה `false`.
סעיף ב
למשל `{1, 2, 3, 4, 5, 6}`.
הפעולה מחזירה `true` רק אם אף איבר אינו גדול מאיבר שמופיע אחריו, כלומר המערך ממוין בסדר עולה (שוויון מותר). מערך כזה בגודל 6, למשל `{1, 2, 3, 4, 5, 6}`: כל 15 ההשוואות שקריות, והפעולה מגיעה ל-`return true`. (גם `{1, 2, 2, 3, 3, 9}` מתאים.)
תשובה: `{1, 2, 3, 4, 5, 6}`.
סעיף ג
בודקת אם המערך ממוין בסדר עולה (לא יורד): מחזירה `true` אם כן, `false` אחרת.
הפעולה משווה כל זוג איברים `arr[i]`, `arr[k]` עם . אם יש זוג שבו האיבר המוקדם גדול מהמאוחר - המערך אינו ממוין ומוחזר `false`. אם אין זוג כזה, כל איבר קטן או שווה לכל איבר שאחריו, כלומר המערך ממוין בסדר עולה, ומוחזר `true`.
תשובה: הפעולה בודקת אם המערך ממוין בסדר עולה (כל איבר קטן או שווה לאיברים שאחריו), ומחזירה `true` אם כן ו-`false` אם לא.
סעיף ד
במקרה הגרוע, כאשר הוא אורך המערך.
נסמן ב- את אורך המערך. במקרה הגרוע (מערך ממוין, שבו לא יוצאים מוקדם) הלולאה הפנימית רצה פעמים עבור , פעמים עבור , וכן הלאה עד פעם אחת. מספר ההשוואות:
(למשל עבור : השוואות). זה סדר גודל של .
תשובה: , כאשר הוא אורך המערך.
סעיף ה
כן: מספיק להשוות כל איבר לאיבר שאחריו (`arr[i] > arr[i+1]`), בלולאה אחת - .
כן. אין צורך להשוות כל זוג. אם כל איבר קטן או שווה לשכן שאחריו (), אז לפי טרנזיטיביות כל איבר קטן או שווה לכל איבר מאוחר יותר. ולהפך: אם יש זוג עם , אז בשרשרת שבין ל- חייב להיות זוג שכנים שבו האיבר הקודם גדול מהבא. לכן הבדיקה על זוגות שכנים בלבד נותנת בדיוק אותה תוצאה.
public static boolean five(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}public static bool Five(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}לולאה אחת של השוואות - סיבוכיות במקום . עבור `{3,5,7,6}` מוחזר `false` בהשוואה .
תשובה: כן - משווים רק איברים סמוכים, בלולאה אחת, בסיבוכיות .
שאלה 6 · מעקב על פעולות מחרוזת עם אותיות גדולות
נתונה הפעולה `why()` הבאה המקבלת מחרוזת:
public static int why(String str)
{
int c=0;
System.out.print("#");
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) >='A' && str.charAt(i) <= 'Z')
{
System.out.print(i+" ");
}
else c++;
}
System.out.print("#");
return c;
}public static int Why(string str)
{
int c=0;
Console.Write("#");
for (int i = 0; i < str.Length; i++)
{
if (str[i] >='A' && str[i] <= 'Z')
{
Console.Write (i+" ");
}
else c++;
}
Console.Write ("#");
return c;
}תן דוגמה למחרוזת באורך של שישה תווים לכל הפחות שעבורה הפעולה `why` תדפיס את המחרוזת הבאה: `#1 3 5 #`
תן דוגמה למחרוזת באורך של שישה תווים לכל הפחות שעבורה הפעולה `why` תדפיס את המחרוזת `##`
מה מבצעת הפעולה? הסבר את תשובתך.
נתונה הפעולה `mystery` המקבלת מערך מחרוזות באורך זוגי. הפעולה משתמשת בפעולה `why`:
public static boolean mystery(String[] arr)
{
for (int i = 0; i < arr.length; i+=2)
{
if (why(arr[i]) != why(arr[i+1]))
return false;
}
return true;
}public static bool Mystery(string[] arr)
{
for (int i = 0; i < arr.Length; i+=2)
{
if (Why(arr[i]) != Why(arr[i+1]))
return false;
}
return true;
}תן דוגמה למערך מחרוזות `arr` בגודל שישה תאים שעבורו הפעולה `mystery` תחזיר ערך `true`.
מה יהיה הפלט של הפעולה עבור מערך שנתת בסעיף ב'1?
מהי סיבוכיות של הפעולה `mystery`? הסבר את תשובתך.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `"aBcDeF"`.
הפעולה מדפיסה `#`, אחר כך את המקום (האינדקס) של כל אות גדולה ('A' עד 'Z') ואחריו רווח, ובסוף `#`. כדי לקבל `#1 3 5 #` צריך אותיות גדולות בדיוק במקומות 1, 3, 5, ובכל שאר המקומות תווים שאינם אותיות גדולות.
המחרוזת `"aBcDeF"` (אורך 6):
הפלט: `#1 3 5 #` (והפעולה מחזירה 3).
תשובה: `"aBcDeF"`.
למשל `"abcdef"` (אין בה אותיות גדולות).
בין שני סימני ה-`#` מודפסים רק מקומות של אותיות גדולות. כדי שיודפס `##` צריך מחרוזת בלי אף אות גדולה, למשל `"abcdef"`: לא מודפס דבר בתוך הלולאה, ו-`c` גדל בכל תו עד 6.
תשובה: `"abcdef"` (הפלט `##`, והפעולה מחזירה 6).
מדפיסה בין שני `#` את המקומות של האותיות הגדולות במחרוזת (כל אחד עם רווח אחריו), ומחזירה את מספר התווים שאינם אותיות גדולות.
1. לפני הלולאה ואחריה מודפס `#`.
2. בלולאה עוברים על כל תו: אם הוא אות גדולה באנגלית (בין `'A'` ל-`'Z'`) מודפס המקום שלו `i` ואחריו רווח; אחרת המונה `c` גדל ב-1.
3. מוחזר `c`.
תשובה: הפעולה מדפיסה, בין שני סימני `#`, את המקומות של האותיות הגדולות במחרוזת, ומחזירה את מספר התווים במחרוזת שאינם אותיות גדולות.
סעיף ב
למשל `{"ab", "cd", "Ab", "Cd", "ABc", "DEf"}`.
הפעולה עוברת על זוגות התאים (0,1), (2,3), (4,5) ומשווה את הערכים ש-`why` מחזירה, כלומר את מספר התווים שאינם אותיות גדולות. היא מחזירה `true` אם בכל זוג המספרים שווים.
נבחר `arr = {"ab", "cd", "Ab", "Cd", "ABc", "DEf"}`:
כל הזוגות שווים, והלולאה מסתיימת ב-`return true`.
תשובה: `{"ab", "cd", "Ab", "Cd", "ABc", "DEf"}`.
הפלט: `#####0 ##0 ##0 1 ##0 1 #` (והפעולה מחזירה `true`).
הפעולה `mystery` עצמה לא מדפיסה, אבל כל זימון של `why` מדפיס. מזמנים את `why` על כל שש המחרוזות לפי הסדר:
ההדפסות נעשות ב-`print`, בלי מעבר שורה, ולכן הן מודפסות ברצף בשורה אחת:
#####0 ##0 ##0 1 ##0 1 #תשובה: `#####0 ##0 ##0 1 ##0 1 #`, והערך המוחזר `true`.
- מחרוזות במערך, האורך המרבי של מחרוזת (כלומר לינארית בסך כל התווים).
נסמן: - מספר המחרוזות במערך, - האורך המרבי של מחרוזת.
1. זימון אחד של `why` עובר על כל תווי המחרוזת פעם אחת - .
2. הלולאה ב-`mystery` רצה פעמים, ובכל סיבוב שני זימונים של `why`, כלומר במקרה הגרוע (כשלא חוזרים מוקדם) `why` נקראת פעם אחת לכל אחת מ- המחרוזות.
סך הכול - פרופורציוני למספר התווים הכולל במערך. (אם כל המחרוזות קצרות, באורך חסום, זה .)
תשובה: .
שאלה 7 · קליטת יישובים עד זקיף ובדיקת התאמה לסקר
לנוכח התפרצות נגיף הקורונה החליט משרד הבריאות לערוך סקר במטרה לבדוק את רמת שביעת הרצון של התושבים מהתנהלות מערכת הבריאות ביישובים שונים בארץ. יישוב מתאים לסקר אם הוא עונה על הקריטריונים שקובע משרד הבריאות. הקריטריונים משתנים מדי חודש.
לצורך כך הגדירו את המחלקה הבאה:
שם המחלקה `City`, למחלקה התכונות הבאות:
•שם יישוב – `name` מסוג מחרוזת.
•מספר תושבים - `popul` מסוג מספר שלם.
•מספר הסניפים של קופות החולים השונות ביישוב – `branch` מסוג מספר שלם.
במחלקה הוגדרה פעולה בונה (בנאי) המקבל פרמטרים לכל התכונות:
public City(String name, int popul, int branch) {…}public City(string name, int popul, int branch) {…}גם כל הפעולות `set/get`.
הוגדרה פעולה נוספת `isFit()`. הפעולה מחזירה `true`, אם היישוב מתאים לסקר, אם לא הפעולה מחזירה `false`.
כותרת הפעולה:
public boolean isFit() {…}public bool IsFit() {…}כתוב תוכנית שתקלוט את הפרטים הבאים:
•שם היישוב.
•מספר התושבים ביישוב.
•מספר הסניפים של קופות החולים ביישוב.
הקלט יסתיים כאשר תיקלט המילה "Stop" עבור שם היישוב.
על התוכנית להדפיס עבור כל יישוב אם הוא מתאים לסקר או לא, ואת מספר היישובים שאינם מתאימים לסקר.
בחודש אוגוסט של שנה 2020 הוחלט שבסקר ישתתפו רק יישובים אשר בהם ישנם יותר מארבעה סניפים של קופות החולים ויותר מ- 5,000 תושבים.
ממש את הפעולה `isFit` בהתאם לתנאים של חודש אוגוסט 2020.
◂ פתרון מלא לשאלה 7
סעיף א
לולאת זקיף על שם היישוב (עד "Stop"); לכל יישוב יוצרים עצם `City`, מזמנים `isFit()`, מדפיסים מתאים/לא מתאים וסופרים את הלא מתאימים; בסוף מדפיסים את המונה.
הרעיון: זו לולאת זקיף - לא ידוע מראש כמה יישובים יש, והערך "Stop" בשם היישוב מסמן את הסוף.
1. קולטים את השם הראשון לפני הלולאה.
2. כל עוד השם אינו "Stop" (ב-Java משווים מחרוזות עם `equals`, לא עם `==`):
•קולטים את מספר התושבים ואת מספר הסניפים;
•יוצרים עצם `City` בעזרת הבנאי הנתון;
•מזמנים את `isFit()` של העצם: אם מוחזר `true` מדפיסים שהיישוב מתאים, אחרת מדפיסים שאינו מתאים ומגדילים את המונה `notFit`;
•קולטים את שם היישוב הבא (בסוף גוף הלולאה, כדי שהתנאי יבדוק אותו).
3. אחרי הלולאה מדפיסים את `notFit`.
התוכנית אינה תלויה בקריטריונים עצמם - הם מוסתרים בתוך `isFit()`, ולכן כשהקריטריונים משתנים מדי חודש משנים רק את `isFit()` ולא את התוכנית.
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int notFit = 0;
String name = in.next();
while (!name.equals("Stop"))
{
int popul = in.nextInt();
int branch = in.nextInt();
City c = new City(name, popul, branch);
if (c.isFit())
System.out.println(name + " fits the survey");
else
{
System.out.println(name + " does not fit the survey");
notFit++;
}
name = in.next();
}
System.out.println("Cities that do not fit: " + notFit);
}public static void Main(string[] args)
{
int notFit = 0;
string name = Console.ReadLine();
while (name != "Stop")
{
int popul = int.Parse(Console.ReadLine());
int branch = int.Parse(Console.ReadLine());
City c = new City(name, popul, branch);
if (c.IsFit())
Console.WriteLine(name + " fits the survey");
else
{
Console.WriteLine(name + " does not fit the survey");
notFit++;
}
name = Console.ReadLine();
}
Console.WriteLine("Cities that do not fit: " + notFit);
}לדוגמה, עבור הקלט `Haifa 280000 40`, `Kfar 3000 5`, `Town 6000 4`, `Stop` ולפי הקריטריונים של סעיף ב: Haifa מתאים, Kfar ו-Town אינם מתאימים, ומודפס בסוף 2.
תשובה: התוכנית שלמעלה.
סעיף ב
`return this.getBranch() > 4 && this.getPopul() > 5000;`
הרעיון: שני התנאים צריכים להתקיים יחד, ולכן מחברים אותם ב-"וגם" (`&&`):
1. "יותר מארבעה סניפים" - `branch > 4` (גדול ממש; 4 סניפים לא מספיקים).
2. "יותר מ-5,000 תושבים" - `popul > 5000` (5,000 בדיוק לא מספיק).
הפעולה היא פעולה של המחלקה `City` ואינה מקבלת פרמטרים - היא בודקת את התכונות של העצם עצמו, דרך פעולות `get`.
public boolean isFit()
{
return this.getBranch() > 4 && this.getPopul() > 5000;
}public bool IsFit()
{
return this.GetBranch() > 4 && this.GetPopul() > 5000;
}לדוגמה: יישוב עם 6,000 תושבים ו-4 סניפים - `false` (4 אינו גדול מ-4); יישוב עם 5,001 תושבים ו-5 סניפים - `true`.
תשובה: `isFit` מחזירה `this.getBranch() > 4 && this.getPopul() > 5000`.
שאלה 8 · ממוצע ספרות ובדיקת סדר עולה
נתונה הפעולה `what` המקבלת כפרמטר מספר שלם חיובי `num`.
public static double what(int num)
{
int c = 0;
int sum = 0;
while (num > 0)
{
c ++;
sum += num%10;
num /= 10;
}
if(c == 0)
return 0;
return (double)sum / c ;
}public static double What(int num)
{
int c = 0;
int sum = 0;
while (num > 0)
{
c ++;
sum += num%10;
num /= 10;
}
if(c == 0)
return 0;
return (double)sum / c ;
}מה תחזיר הפעולה עבור `num=1245`? חובה לכתוב מעקב בטבלה.
תן דוגמה למספר שלם `num`, שעבורו הפעולה תחזיר 4.
מה מבצעת הפעולה עבור מספר `num` שלם חיובי כלשהו? הסבר באופן כללי.
נתונה הפעולה `why()` הבאה:
public static boolean why(int[] arr)
{
double prev= what(arr[0]);
double curr;
for (int i = 1; i < arr.length; i++)
{
curr = what(arr[i]);
if (curr > prev)
{
prev = curr;
}
else
return false;
}
return true;
}public static bool Why(int[] arr)
{
double prev= What(arr[0]);
double curr;
for (int i = 1; i < arr.Length; i++)
{
curr = What(arr[i]);
if (curr > prev)
{
prev = curr;
}
else
return false;
}
return true;
}עקוב באמצעות טבלת מעקב אחר ביצוע הפעולה `why(arr)` עבור המערך:
int[] arr = {2002, 28, 129, 468 };ורשום מה תהיה תוצאת הזימון.
הערה: אין צורך להראות מעקב אחרי הזימונים של הפעולה `what`.
האם אפשר לשנות את סדר האיברים במערך הנתון `arr`, וכך הזימון `why(arr)` יחזיר תוצאה שונה מתוצאה של סעיף ב'1? הסבר את תשובתך.
מה מבצעת הפעולה `why(arr)` עבור מערך כלשהו של מספרים שלמים?
◂ פתרון מלא לשאלה 8
סעיף א
3.0
בכל סיבוב: `c` גדל ב-1, הספרה הימנית (`num%10`) מתווספת ל-`sum`, והספרה הזו נמחקת (`num /= 10`, חילוק בשלמים).
הלולאה נעצרת כש-. מכיוון ש-, מוחזר (חילוק ממשי בגלל ההמרה ל-`double`).
תשובה: הפעולה מחזירה 3.0.
למשל `num=35` () או `num=4`.
הפעולה מחזירה את ממוצע הספרות, ולכן צריך מספר שממוצע ספרותיו 4.
`num=35`: . (גם `num=4`, `num=44` או `num=129`: .)
תשובה: למשל `num=35`.
מחזירה את ממוצע הספרות של `num` (סכום הספרות חלקי מספר הספרות), כמספר ממשי.
1. הלולאה מפרקת את המספר לספרותיו מימין לשמאל: `num%10` היא ספרת האחדות, ו-`num /= 10` מוחקת אותה.
2. `sum` צובר את סכום הספרות, ו-`c` סופר את מספר הספרות.
3. מוחזר כמספר ממשי. (הבדיקה `c == 0` מטפלת במקרה `num=0` שבו אין סיבובים, כדי לא לחלק ב-0.)
תשובה: הפעולה מחזירה את ממוצע הספרות של `num`: סכום הספרות חלקי מספר הספרות.
סעיף ב
`false` (עבור : אינו מתקיים).
הפעולה שומרת ב-`prev` את ממוצע הספרות של האיבר הקודם, ובכל סיבוב מחשבת ב-`curr` את ממוצע הספרות של האיבר הנוכחי. אם `curr > prev` ממשיכים (ו-`prev` מתעדכן), אחרת מוחזר מיד `false`.
ממוצעי הספרות (לפי סעיף א): `what(2002)` , `what(28)` , `what(129)` .
האיבר 468 כבר לא נבדק.
תשובה: הזימון מחזיר `false`.
כן: בסדר `{2002, 129, 28, 468}` הממוצעים 1.0, 4.0, 5.0, 6.0 עולים ממש, ומוחזר `true`.
נחשב את ממוצע הספרות של כל איבר:
•`2002`:
•`129`:
•`28`:
•`468`:
הפעולה מחזירה `true` רק אם כל ממוצע גדול ממש מקודמו. כל ארבעת הממוצעים שונים זה מזה, ולכן אפשר לסדר את האיברים כך שהממוצעים עולים ממש: `{2002, 129, 28, 468}`. אז בכל סיבוב (, , ), הלולאה מסתיימת, ומוחזר `true` - תוצאה שונה מ-`false`.
תשובה: כן; למשל בסדר `{2002, 129, 28, 468}` הזימון מחזיר `true`.
מחזירה `true` אם ממוצעי הספרות של איברי המערך עולים ממש מאיבר לאיבר, ו-`false` אחרת.
הפעולה משווה את ממוצע הספרות של כל איבר (`curr`) לזה של האיבר שלפניו (`prev`). אם בשלב כלשהו הממוצע הנוכחי אינו גדול ממש מהקודם (קטן או שווה), מוחזר `false`. אם עברנו על כל המערך, הממוצעים עולים ממש, ומוחזר `true`.
תשובה: הפעולה בודקת אם ממוצעי הספרות של איברי המערך מסודרים בסדר עולה ממש (לכל איבר ממוצע ספרות גדול מזה של קודמו): `true` אם כן, `false` אם לא.
שאלה 9 · ראשי תיבות של מילים במחרוזת
כתוב פעולה המקבלת מחרוזת המורכבת משתי מילים או יותר כאשר רווח יחיד מפריד בין כל מילה ומילה.
על הפעולה להחזיר מחרוזת חדשה המורכבת מהאות הראשונה של כל מילה עם נקודה בין כל שתי אותיות, כאשר גם בסוף יש נקודה.
דוגמה: עבור המחרוזת: `READ ONLY MEMORY`
תוחזר המחרוזת: `R.O.M.`
הערה: אפשר להניח שמילים מורכבות רק מאותיות (A..Z)
◂ פתרון מלא לשאלה 9
פתרון
מתחילים ב-`str[0] + "."`; עבור כל תו שלפניו רווח מוסיפים את התו ונקודה; מחזירים את התוצאה (`READ ONLY MEMORY` → `R.O.M.`).
הרעיון: האות הראשונה של כל מילה היא:
•התו הראשון במחרוזת (המילה הראשונה), או
•כל תו שמופיע מיד אחרי רווח (כי רווח יחיד מפריד בין המילים).
1. מתחילים את התוצאה `res` בתו הראשון ונקודה.
2. עוברים על המקומות עד סוף המחרוזת; אם התו הקודם `str[i-1]` הוא רווח, אז `str[i]` פותח מילה חדשה - מוסיפים אותו ונקודה.
3. מחזירים את `res`. מכיוון שאחרי כל אות נוספת נקודה, יש נקודה בין כל שתי אותיות וגם בסוף.
public static String initials(String str)
{
String res = "" + str.charAt(0) + ".";
for (int i = 1; i < str.length(); i++)
{
if (str.charAt(i - 1) == ' ')
res = res + str.charAt(i) + ".";
}
return res;
}public static string Initials(string str)
{
string res = "" + str[0] + ".";
for (int i = 1; i < str.Length; i++)
{
if (str[i - 1] == ' ')
res = res + str[i] + ".";
}
return res;
}מעקב על `READ ONLY MEMORY`: בהתחלה `res="R."`; במקום 5 (התו `O`, שלפניו רווח במקום 4) - `res="R.O."`; במקום 10 (התו `M`, שלפניו רווח במקום 9) - `res="R.O.M."`. מוחזר `R.O.M.`.
סיבוכיות: מעבר אחד על המחרוזת - , כאשר אורך המחרוזת.
תשובה: הפעולה `initials` שלמעלה.
שאלה 10 · "מרחק" של מספר מקצוות המערך
נתון מערך המכיל מספרים שלמים.
נגדיר "מרחק" של מספר במערך כסכום המרחקים הקטנים ביותר של מופע אותו המספר מקצוות המערך.
דוגמה 1: ה"מרחק" של המספר 71 במערך הוא 5 (2 מימין ו- 3 משמאל).
דוגמה 2: ה"מרחק" של המספר 13 המערך הוא 9 (7 מימין ו- 2 משמאל).


כתוב פעולה `public static int dist(int[] arr, int num)`.
הפעולה מקבלת מערך מספרים שלמים `arr` ומספר `num` ומחזירה את "המרחק" של המספר `num`.
הערה: אם `num` לא נמצא במערך `arr` יוחזר `-1`.
כתוב פעולה `public static int minNum(int[] arr)`.
הפעולה מקבלת מערך מספרים שלמים ומחזירה את המספר בעל "המרחק" הקטן ביותר.
(עבור הדוגמה הנ"ל הפעולה תחזיר 10 כי "המרחק" שלו שווה ל- 1 והוא הקטן בין כל "המרחקים")
◂ פתרון מלא לשאלה 10
סעיף א
מוצאים את המקום הראשון `first` ואת המקום האחרון `last` של `num`; אם אינו קיים - `-1`; אחרת מחזירים `first + (arr.length - 1 - last)`.
הרעיון: מהדוגמאות רואים:
•המרחק "משמאל" הוא מספר התאים שלפני המופע הראשון של המספר - זה בדיוק האינדקס שלו, `first`. (עבור 71 המופע הראשון במקום 3, ולפניו 3 תאים.)
•המרחק "מימין" הוא מספר התאים שאחרי המופע האחרון - , כאשר אורך המערך. (עבור 71 המופע האחרון במקום 7, ואחריו תאים.)
- "המרחק" הוא הסכום: . עבור 71: ; עבור 13 (): - כמו בדוגמאות.
השלבים:
1. מחפשים מההתחלה את המופע הראשון (הלולאה נעצרת כשנמצא).
2. אם לא נמצא - מחזירים `-1`.
3. אחרת מחפשים מהסוף את המופע האחרון (הוא בוודאי קיים, כי המספר נמצא במערך).
4. מחזירים את סכום שני המרחקים.
public static int dist(int[] arr, int num)
{
int first = -1;
for (int i = 0; i < arr.length && first == -1; i++)
if (arr[i] == num)
first = i;
if (first == -1)
return -1; // num is not in the array
int last = arr.length - 1;
while (arr[last] != num)
last--;
return first + (arr.length - 1 - last);
}public static int Dist(int[] arr, int num)
{
int first = -1;
for (int i = 0; i < arr.Length && first == -1; i++)
if (arr[i] == num)
first = i;
if (first == -1)
return -1; // num is not in the array
int last = arr.Length - 1;
while (arr[last] != num)
last--;
return first + (arr.Length - 1 - last);
}בדיקה על המערך שבאיורים: `dist(arr, 71)` מחזירה 5, `dist(arr, 13)` מחזירה 9, `dist(arr, 10)` מחזירה , ו-`dist(arr, 99)` מחזירה `-1`.
סיבוכיות: כל חיפוש עובר על המערך לכל היותר פעם אחת - .
תשובה: הפעולה `dist` שלמעלה.
סעיף ב
עוברים על כל איברי המערך, מחשבים לכל אחד `dist(arr, arr[i])` בעזרת סעיף א, ושומרים את המספר בעל המרחק המינימלי; מחזירים אותו (בדוגמה: 10).
הרעיון: חיפוש מינימום רגיל, כאשר הערך שמשווים הוא "המרחק" שמחושב בפעולה מסעיף א.
1. מניחים שהמספר הטוב ביותר הוא `arr[0]`, ושומרים את המרחק שלו ב-`minDist`.
2. עוברים על שאר האיברים; לכל איבר מחשבים `dist(arr, arr[i])`. אם הוא קטן מ-`minDist`, מעדכנים את המינימום ואת המספר `best`.
3. מחזירים את `best`.
כל מספר שמופיע במערך נבדק (פעם אחת או יותר - לא מזיק, כי המרחק שלו זהה בכל פעם). אם לכמה מספרים אותו מרחק מינימלי, מוחזר הראשון ביניהם (בגלל ההשוואה `<` הקפדנית).
public static int minNum(int[] arr)
{
int best = arr[0];
int minDist = dist(arr, arr[0]);
for (int i = 1; i < arr.length; i++)
{
int d = dist(arr, arr[i]);
if (d < minDist)
{
minDist = d;
best = arr[i];
}
}
return best;
}public static int MinNum(int[] arr)
{
int best = arr[0];
int minDist = Dist(arr, arr[0]);
for (int i = 1; i < arr.Length; i++)
{
int d = Dist(arr, arr[i]);
if (d < minDist)
{
minDist = d;
best = arr[i];
}
}
return best;
}בדוגמה שבאיורים, המרחקים הם: 4 → , 10 → , 13 → 9, 71 → 5, 2 → . המינימום 1, ולכן מוחזר 10.
סיבוכיות: זימונים של `dist`, כל אחד - בסך הכול .
תשובה: הפעולה `minNum` שלמעלה (עבור הדוגמה מחזירה 10).
שאלה 11 · רקורסיה: חיפוש ספרה וסידור מערך
נתונה פעולה רקורסיבית `secret` המקבלת שני מספרים שלמים אי-שליליים (גדולים ושווים ל- 0):
public static boolean secret (int n1, int n2)
{
if (n1 < 10)
return (n1 == n2);
if (n1%10 == n2)
return true;
return secret (n1 / 10, n2);
}public static bool Secret (int n1, int n2)
{
if (n1 < 10)
return (n1 == n2);
if (n1%10 == n2)
return true;
return Secret (n1 / 10, n2);
}עקוב אחר הזימון הבא: `secret (528, 5)`.
מה מבצעת הפעולה `secret`?
נתונה פעולה רקורסיבית `bigSecret` המקבלת מערך מספרים שלמים אי-שליליים ומחזירה מערך חדש:
public static int[] bigSecret (int[] arr)
{
int[] temp=new int [arr.length];
mystery(arr, temp, 0, 0, temp.length-1);
return temp;
}
private static void mystery (int[] arr, int[] temp, int k, int low, int high)
{
if (k < arr.length)
{
if (secret (arr[k] / 10, arr[k] % 10))
{
temp[high] = arr[k];
mystery (arr, temp, k+1, low, high-1);
}
else
{
temp[low] = arr[k];
mystery (arr, temp, k+1, low+1, high);
}
}
}public static int[] BigSecret (int[] arr)
{
int[] temp = new int [arr.Length];
Mystery(arr, temp, 0, 0, temp.Length-1);
return temp;
}
private static void Mystery (int[] arr, int[] temp, int k, int low, int high)
{
if (k < arr.Length)
{
if (Secret (arr[k] / 10, arr[k] % 10))
{
temp[high] = arr[k];
Mystery (arr, temp, k+1, low, high-1);
}
else
{
temp[low] = arr[k];
Mystery (arr, temp, k+1, low+1, high);
}
}
}נתון מערך חד ממדי `arr={424, 57547, 130, 57675, 12}`.
עקוב אחר ביצוע הפעולה `bigSecret(arr)` ורשום את הערך המוחזר.
הערה: אין צורך להראות מעקב אחר הפעולה `secret`.
מה מבצעת הפעולה `bigSecret`?
◂ פתרון מלא לשאלה 11
סעיף א
`secret(528,5)` → `secret(52,5)` → `secret(5,5)` → `true`; מוחזר `true`.
בכל זימון בודקים: אם (ספרה אחת) מחזירים האם ; אחרת, אם ספרת האחדות שווה ל- מחזירים `true`; אחרת קוראים שוב עם (מחיקת ספרת האחדות).
הערך `true` חוזר מזימון 3 לזימון 2, ומשם לזימון 1.
תשובה: הזימון מחזיר `true`.
בודקת אם הספרה `n2` מופיעה בין הספרות של `n1`: `true` אם כן, `false` אם לא.
הפעולה עוברת על ספרות `n1` מימין לשמאל: בכל זימון בודקת את ספרת האחדות ומוחקת אותה בקריאה הבאה. כשנשארת ספרה אחת () משווה אותה ל-`n2`. לכן מוחזר `true` אם ורק אם אחת מספרות `n1` שווה ל-`n2`. (למשל `secret(528, 5)` - `true`, `secret(528, 3)` - `false`.)
תשובה: הפעולה מחזירה `true` אם הספרה `n2` מופיעה במספר `n1`, ו-`false` אחרת.
סעיף ב
`{130, 12, 57675, 57547, 424}`
`bigSecret` יוצרת מערך `temp` באורך 5 וקוראת ל-`mystery(arr, temp, 0, 0, 4)`. בכל זימון של `mystery` מחושב `secret(arr[k] / 10, arr[k] % 10)`, כלומר (לפי סעיף א) האם ספרת האחדות של `arr[k]` מופיעה שוב בשאר הספרות שלו. אם כן - האיבר נכתב ל-`temp[high]` ו-`high` קטן; אם לא - נכתב ל-`temp[low]` ו-`low` גדל.
תשובה: מוחזר המערך `{130, 12, 57675, 57547, 424}`.
מחזירה מערך חדש: בתחילתו (לפי הסדר המקורי) המספרים שספרת האחדות שלהם אינה מופיעה בשאר ספרותיהם, ובסופו (בסדר הפוך) המספרים שספרת האחדות שלהם מופיעה שוב במספר.
1. `secret(arr[k] / 10, arr[k] % 10)` בודקת אם ספרת האחדות של `arr[k]` מופיעה בין שאר הספרות שלו (`arr[k] / 10` הוא המספר בלי ספרת האחדות).
2. מספר שבו ספרת האחדות אינה חוזרת נכתב במקום `low`, ש"מתקדם" מתחילת `temp` קדימה - לכן המספרים האלה מופיעים בתחילת המערך החדש, באותו סדר כמו ב-`arr`.
3. מספר שבו ספרת האחדות חוזרת נכתב במקום `high`, ש"מתקדם" מסוף `temp` אחורה - לכן המספרים האלה מופיעים בסוף המערך החדש, בסדר הפוך לסדרם ב-`arr`.
4. כל איבר נכתב פעם אחת, ובסוף , כך שכל תאי `temp` מתמלאים. המערך המקורי אינו משתנה.
תשובה: הפעולה מחזירה מערך חדש שבו קודם (לפי הסדר המקורי) כל המספרים שספרת האחדות שלהם אינה מופיעה בשאר ספרותיהם, ואחריהם (בסדר הפוך) כל המספרים שספרת האחדות שלהם מופיעה גם בשאר ספרותיהם.
שאלה 12 · מחלקת עובד: משכורת, קליטת שעות וסיכום
במפעל מסוים יש שני סוגים של עובדים: פועלים ומהנדסים. שכרו של כל עובד מחושב כך:
- 160 שעות עבודה או פחות נקראות "שעות בסיס" (basic) והעובד מקבל עבור כל שעה שכר לפי תפקידו: פועל מקבל 50 ש''ח לשעת עבודה ומהנדס – 90 ש''ח.
•עבור כל שעה נוספת (extra) מקבל העובד (ללא תלות בתפקיד) 100 ש''ח.
לדוגמה: מהנדס שעבד בחודש מסוים 200 שעות יקבל משכורת של `18,400=(160*90+40*100)` ש"ח.
נתונה המחלקה הבאה:
class Worker
{
private String id;// ת.ז. של עובד
private int status; //1- מהנדס, 2- פועל
private int basic; // מספר שעות בסיס בחודש
private int extra; // מספר שעות נוספות בחודש
public Worker(String id, int status) //פעולה בונה
{
this.id = id;
this.status = status;
this.basic = 0;
this.extra = 0;
}class Worker
{
private string id;// ת.ז. של עובד
private int status; //1- מהנדס, 2- פועל
private int basic; // מספר שעות בסיס בחודש
private int extra; // מספר שעות נוספות בחודש
public Worker(string id, int status) //פעולה בונה
{
this.id = id;
this.status = status;
this.basic = 0;
this.extra = 0;
}במחלקה הוגדרו כל הפעולות `set` ו- `get` וגם הפעולה `toString()`.
נתונה כותרת של פעולה לחישוב המשכורת של עובד:
public int getSalary (){…}public int GetSalary (){…}השלם את גוף הפעולה.
כתוב במחלקה `Worker` פעולה `input()` לקליטת נתוני עבודה של עובד מסוים:
עבור כל אחד מ- 20 ימי העבודה בחודש ייקלטו שעת תחילת העבודה ושעת סיום העבודה.
אחרי קליטת הנתונים יש לעדכן את התכונות הרלוונטיות.
אפשר להניח ששעת תחילת העבודה קטנה תמיד משעת הסיום.
כתוב פעולה אשר מקבלת מערך עצמים מסוג `Worker` השומר את נתוני השכר של כל עובדי המפעל.
על הפעולה להדפיס, עבור כל אחד מהעובדים, את מספר תעודת הזהות שלו, את מספר שעות העבודה ואת משכורתו.
הפעולה גם תדפיס את השכר הכולל של כל המהנדסים ואת השכר הכולל של כל הפועלים.
◂ פתרון מלא לשאלה 12
סעיף א
`basic * rate + extra * 100`, כאשר `rate` הוא 90 למהנדס (`status == 1`) ו-50 לפועל.
הרעיון: התכונות `basic` ו-`extra` כבר מפרידות בין שעות הבסיס לשעות הנוספות, ולכן:
1. קובעים את התעריף לשעת בסיס לפי `status`: 1 - מהנדס, 90 ש"ח; 2 - פועל, 50 ש"ח.
2. המשכורת = שעות בסיס × תעריף + שעות נוספות × 100.
הפעולה שייכת למחלקה ואינה מקבלת פרמטרים. ניגשים לתכונות דרך פעולות `get`.
public int getSalary()
{
int rate;
if (this.getStatus() == 1) // engineer
rate = 90;
else // worker
rate = 50;
return this.getBasic() * rate + this.getExtra() * 100;
}public int GetSalary()
{
int rate;
if (this.GetStatus() == 1) // engineer
rate = 90;
else // worker
rate = 50;
return this.GetBasic() * rate + this.GetExtra() * 100;
}בדיקה על הדוגמה: מהנדס עם , : ש"ח, כמו בשאלה.
תשובה: `getSalary` מחזירה `getBasic() * rate + getExtra() * 100`, עם `rate` = 90 למהנדס ו-50 לפועל.
סעיף ב
סוכמים 20 פעמים `end - start`; אם הסכום עד 160 - `basic` = הסכום ו-`extra` = 0; אחרת `basic` = 160 ו-`extra` = הסכום פחות 160.
1. בלולאה של 20 סיבובים (ימי העבודה) קולטים שעת התחלה ושעת סיום, ומוסיפים לצובר `total` את שעות היום: `end - start`.
2. אחרי הלולאה מחלקים את סך השעות:
•אם - כל השעות הן שעות בסיס: `basic = total`, `extra = 0`.
•אחרת - 160 שעות בסיס, והשאר שעות נוספות: `basic = 160`, `extra = total - 160`.
3. מעדכנים את התכונות בעזרת פעולות `set`.
השעות נקלטות כמספרים שלמים, כמו טיפוס התכונות `basic` ו-`extra`.
public void input()
{
Scanner in = new Scanner(System.in);
int total = 0;
for (int day = 1; day <= 20; day++)
{
int start = in.nextInt();
int end = in.nextInt();
total += end - start;
}
if (total <= 160)
{
this.setBasic(total);
this.setExtra(0);
}
else
{
this.setBasic(160);
this.setExtra(total - 160);
}
}public void Input()
{
int total = 0;
for (int day = 1; day <= 20; day++)
{
int start = int.Parse(Console.ReadLine());
int end = int.Parse(Console.ReadLine());
total += end - start;
}
if (total <= 160)
{
this.SetBasic(total);
this.SetExtra(0);
}
else
{
this.SetBasic(160);
this.SetExtra(total - 160);
}
}לדוגמה: אם בכל יום העובד עבד מ-8 עד 18, אז , ולכן , . אם עבד מ-8 עד 15, אז , , .
תשובה: הפעולה `input` שלמעלה.
סעיף ג
לכל עובד: מדפיסים `getId()`, `getBasic()+getExtra()` ו-`getSalary()`, ומוסיפים את המשכורת לצובר המהנדסים (`status == 1`) או לצובר הפועלים; בסוף מדפיסים את שני הצוברים.
1. שני צוברים: `sumEng` לשכר המהנדסים ו-`sumWork` לשכר הפועלים, מתחילים ב-0.
2. עוברים על המערך. לכל עובד:
•מספר שעות העבודה = שעות בסיס + שעות נוספות;
•המשכורת מחושבת בפעולה `getSalary()` מסעיף א;
•מדפיסים תעודת זהות, שעות ומשכורת;
•לפי `getStatus()` מוסיפים את המשכורת לצובר המתאים (1 - מהנדסים, אחרת - פועלים).
3. אחרי הלולאה מדפיסים את שני הצוברים.
הפעולה סטטית (מחוץ למחלקה `Worker`), ולכן ניגשת לנתונים רק דרך פעולות `get`.
public static void printSalaries(Worker[] arr)
{
int sumEng = 0, sumWork = 0;
for (int i = 0; i < arr.length; i++)
{
int hours = arr[i].getBasic() + arr[i].getExtra();
int salary = arr[i].getSalary();
System.out.println(arr[i].getId() + " " + hours + " " + salary);
if (arr[i].getStatus() == 1)
sumEng += salary;
else
sumWork += salary;
}
System.out.println("Engineers total: " + sumEng);
System.out.println("Workers total: " + sumWork);
}public static void PrintSalaries(Worker[] arr)
{
int sumEng = 0, sumWork = 0;
for (int i = 0; i < arr.Length; i++)
{
int hours = arr[i].GetBasic() + arr[i].GetExtra();
int salary = arr[i].GetSalary();
Console.WriteLine(arr[i].GetId() + " " + hours + " " + salary);
if (arr[i].GetStatus() == 1)
sumEng += salary;
else
sumWork += salary;
}
Console.WriteLine("Engineers total: " + sumEng);
Console.WriteLine("Workers total: " + sumWork);
}דוגמה: מהנדס `111` עם 160+40 שעות (18,400), פועל `222` עם 150 שעות (), מהנדס `333` עם 160 שעות (), פועל `444` עם 160+10 שעות (). יודפסו ארבע שורות העובדים, ואחריהן שכר המהנדסים ושכר הפועלים .
תשובה: הפעולה `printSalaries` שלמעלה.
שאלה 13 · רקורסיה: מחיקת k מופעים ראשונים של תו
נתונה פעולה רקורסיבית `what(String s, char ch, int k)` הבאה:
public static String what(String s, char ch, int k)
{
if(k == 0)
return s;
if(s.length() == 0)
return s;
if(s.charAt(0) == ch)
return what(s.substring(1), ch, k-1);
return s.charAt(0) + what(s.substring(1), ch, k);
}public static string What(string s, char ch, int k)
{
if(k == 0)
return s;
if(s.Length == 0)
return s;
if(s[0] == ch)
return What(s.Substring(1), ch, k-1);
return s[0] + What(s.Substring(1), ch, k);
}מה תהיה תוצאת הזימון `what(s1, 'a', 2)` עבור מחרוזת `s1="aabbaad"`?
מה תהיה תוצאת הזימון `what(s1, 'f', 3)` עבור מחרוזת `s1=" aabbaad"`?
נתונה מחרוזת `s2="aabccddc"`. תן דוגמה לפרמטרים `k` ו- `ch` כך שתוצאת הזימון `what(s2, ch, k)` תהיה מחרוזת `s3="aabddc"`.
מה מבצעת הפעולה `what`?
כתוב פעולה `what` המבצעת אותה משימה בצורה לא רקורסיבית.
◂ פתרון מלא לשאלה 13
סעיף א
`"bbaad"`
בכל זימון: אם או שהמחרוזת ריקה - מוחזרת המחרוזת כמו שהיא. אחרת, אם התו הראשון הוא `ch` - הוא נשמט וממשיכים עם ; אם לא - הוא נשמר לפני תוצאת הקריאה על שאר המחרוזת.
הערך `"bbaad"` חוזר ללא שינוי מזימון 3 לזימון 2 ולזימון 1 (בזימונים 1 ו-2 התו הראשון נשמט, ולכן לא נוסף דבר).
תשובה: `"bbaad"`.
סעיף ב
המחרוזת אינה משתנה: `"aabbaad"` (אין בה `'f'`).
במחרוזת אין אף תו `'f'`, ולכן אף פעם לא מגיעים לשורה שמשמיטה תו, ו-`k` נשאר 3. בכל זימון התו הראשון נשמר ומחובר לתוצאת הקריאה על שאר המחרוזת, עד שהמחרוזת ריקה ומוחזר `""`:
`'a' + ('a' + ('b' + ('b' + ('a' + ('a' + ('d' + ""))))))` `"aabbaad"`.
(אם במחרוזת המודפסת יש רווח בתחילתה, גם הוא נשמר באותו אופן, והתוצאה זהה למחרוזת המקורית.)
תשובה: מוחזרת המחרוזת המקורית ללא שינוי, `"aabbaad"`.
סעיף ג
`ch='c'`, `k=2`.
משווים את `s2="aabccddc"` ל-`s3="aabddc"`: חסרים שני התווים `cc` שבמקומות 3 ו-4 - שני המופעים הראשונים של `'c'`, וה-`'c'` האחרון נשאר. לכן `ch='c'` ו-`k=2`.
בדיקה: `a`, `a`, `b` נשמרים; שני ה-`c` נשמטים ( יורד ל-0); כאשר מוחזר שאר המחרוזת `"ddc"` כמו שהוא. התוצאה `"aab"+"ddc"="aabddc"`. (עם היה נמחק גם ה-`c` האחרון.)
תשובה: `ch='c'`, `k=2`.
סעיף ד
מחזירה את `s` אחרי מחיקת `k` המופעים הראשונים של התו `ch` (אם יש פחות מ-`k` מופעים - כולם נמחקים).
הפעולה עוברת על המחרוזת משמאל לימין. כל מופע של `ch` נשמט ומקטין את `k` ב-1; שאר התווים נשמרים. כש- מגיע ל-0, שאר המחרוזת מוחזר כמו שהוא. לכן נמחקים בדיוק `k` המופעים הראשונים של `ch` (או כל המופעים, אם יש פחות מ-`k`), וסדר שאר התווים נשמר.
תשובה: הפעולה מחזירה מחרוזת שבה נמחקו `k` המופעים הראשונים של התו `ch` מתוך `s`.
סעיף ה
לולאה על תווי `s`: אם התו הוא `ch` ו-`k > 0` - מדלגים עליו ומקטינים את `k`; אחרת מוסיפים אותו למחרוזת התוצאה.
הרעיון: בונים את מחרוזת התוצאה בלולאה אחת:
1. `res` מתחילה כמחרוזת ריקה.
2. לכל תו של `s`: אם הוא שווה ל-`ch` ועדיין - זה אחד מ-`k` המופעים הראשונים: לא מוסיפים אותו, ומקטינים את `k`.
3. אחרת (תו אחר, או ש-`k` כבר 0) - מוסיפים את התו ל-`res`.
4. מחזירים את `res`.
`k` הוא פרמטר המועבר לפי ערך, ולכן מותר לשנות אותו בתוך הפעולה.
public static String what(String s, char ch, int k)
{
String res = "";
for (int i = 0; i < s.length(); i++)
{
if (s.charAt(i) == ch && k > 0)
k--; // skip this occurrence
else
res = res + s.charAt(i);
}
return res;
}public static string What(string s, char ch, int k)
{
string res = "";
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ch && k > 0)
k--; // skip this occurrence
else
res = res + s[i];
}
return res;
}בדיקה: `what("aabbaad", 'a', 2)` מחזירה `"bbaad"`, `what("aabbaad", 'f', 3)` מחזירה `"aabbaad"`, ו-`what("aabccddc", 'c', 2)` מחזירה `"aabddc"` - כמו הפעולה הרקורסיבית.
תשובה: הפעולה `what` הלא רקורסיבית שלמעלה.