מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2024 מועד ב'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2024 מועד ב', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 15)
בכל מבחן 14 שאלות.
שאלות 1-7: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 12 נקודות.
שאלות 8-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.
שאלות 12-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטה עד אפס: שליליים וממוצע חיוביים
כתבו קטע תוכנית שקולט מספרים שלמים. הקלט יסתיים כאשר ייקלט המספר 0.
על התוכנית לחשב ולהדפיס:
•את כמות המספרים השליליים שנקלטו
•את ממוצע מספרים חיוביים שנקלטו.
הערה: אם לא נקלט אף מספר חיובי יש להדפיס הודעה מתאימה.
◂ פתרון מלא לשאלה 1
פתרון
לולאת `while` שרצה עד שנקלט : מונה לשליליים, מונה וצובר לחיוביים; בסוף מדפיסים את מונה השליליים, ואת הממוצע `sumPos / countPos` (בחילוק ממשי) או הודעה אם `countPos == 0`.
הרעיון: מספר הנתונים לא ידוע מראש – הקלט נעצר כשנקלט – ולכן משתמשים בלולאת `while` עם "זקיף".
1. מגדירים שלושה משתנים: `countNeg` – מונה השליליים, `countPos` – מונה החיוביים, `sumPos` – צובר (סכום) החיוביים. כולם מאותחלים ל-.
2. קולטים את המספר הראשון לפני הלולאה, כדי שהתנאי `num != 0` ייבדק כבר עליו (אם הוא – הלולאה לא מתבצעת בכלל).
3. בתוך הלולאה: אם המספר שלילי – מגדילים את `countNeg`; אחרת (הוא חיובי, כי לא נכנס ללולאה) – מגדילים את `countPos` ומוסיפים אותו ל-`sumPos`. בסוף הסיבוב קולטים את המספר הבא.
4. המספר שעוצר את הקלט אינו נספר.
5. אחרי הלולאה מדפיסים את `countNeg`. לממוצע צריך לחלק ב-`countPos`, ולכן קודם בודקים שהוא אינו (אחרת – חילוק באפס). אם אין חיוביים מדפיסים הודעה, ואחרת מדפיסים `(double) sumPos / countPos` – ההמרה ל-`double` מונעת חילוק שלמים שהיה חותך את השבר.
int countNeg = 0; // מונה המספרים השליליים
int countPos = 0; // מונה המספרים החיוביים
int sumPos = 0; // סכום המספרים החיוביים
int num = in.nextInt();
while (num != 0)
{
if (num < 0)
countNeg++;
else
{
countPos++;
sumPos += num;
}
num = in.nextInt();
}
System.out.println("negative numbers: " + countNeg);
if (countPos == 0)
System.out.println("no positive numbers were entered");
else
System.out.println("average of positives: " + (double) sumPos / countPos);int countNeg = 0; // מונה המספרים השליליים
int countPos = 0; // מונה המספרים החיוביים
int sumPos = 0; // סכום המספרים החיוביים
int num = int.Parse(Console.ReadLine());
while (num != 0)
{
if (num < 0)
countNeg++;
else
{
countPos++;
sumPos += num;
}
num = int.Parse(Console.ReadLine());
}
Console.WriteLine("negative numbers: " + countNeg);
if (countPos == 0)
Console.WriteLine("no positive numbers were entered");
else
Console.WriteLine("average of positives: " + (double) sumPos / countPos);דוגמה: עבור הקלט : השליליים הם , כלומר מספרים; החיוביים , סכומם וממוצעם .
עבור הקלט יודפס `negative numbers: 2` ואחריו ההודעה שלא נקלטו מספרים חיוביים.
תשובה: קטע הקוד שלמעלה.
שאלה 2 · קליטת 20 מחרוזות: תו ראשון ואחרון
כתבו קטע תוכנית הקולט 20 מחרוזות.
עבור כל מחרוזת באורך זוגי יש להדפיס את התו הראשון ואת התו האחרון שלה.
כמו כן, יש למנות ולהדפיס את כמות המחרוזות אשר מתחילות או מסתיימות באות 'A'.
◂ פתרון מלא לשאלה 2
פתרון
לולאת `for` של סיבובים: לכל מחרוזת לוקחים את התו במקום ואת התו במקום `length-1`; אם האורך זוגי מדפיסים אותם; אם אחד מהם הוא `'A'` מגדילים מונה; בסוף מדפיסים את המונה.
הרעיון: מספר המחרוזות ידוע (), ולכן לולאת `for`. לכל מחרוזת בודקים שני דברים נפרדים (שני `if` עצמאיים, לא `else`), כי מחרוזת יכולה לקיים את שניהם.
1. מאתחלים מונה `countA = 0`.
2. בכל סיבוב קולטים מחרוזת `str` ושומרים את התו הראשון (מקום ) ואת התו האחרון (מקום `str.length() - 1`).
3. אורך זוגי: אם `str.length() % 2 == 0` – מדפיסים את שני התווים.
4. מתחילה או מסתיימת ב-'A': אם `first == 'A' || last == 'A'` – מגדילים את המונה. ה"או" כולל גם מחרוזת שגם מתחילה וגם מסתיימת ב-'A', והיא נספרת פעם אחת בלבד.
5. אחרי הלולאה מדפיסים את המונה.
int countA = 0; // מחרוזות שמתחילות או מסתיימות ב-'A'
for (int i = 0; i < 20; i++)
{
String str = in.next();
char first = str.charAt(0);
char last = str.charAt(str.length() - 1);
if (str.length() % 2 == 0)
System.out.println(first + " " + last);
if (first == 'A' || last == 'A')
countA++;
}
System.out.println("strings that start or end with A: " + countA);int countA = 0; // מחרוזות שמתחילות או מסתיימות ב-'A'
for (int i = 0; i < 20; i++)
{
string str = Console.ReadLine();
char first = str[0];
char last = str[str.Length - 1];
if (str.Length % 2 == 0)
Console.WriteLine(first + " " + last);
if (first == 'A' || last == 'A')
countA++;
}
Console.WriteLine("strings that start or end with A: " + countA);דוגמה: עבור המחרוזות `"ABCA"` (אורך ) יודפס `A A` והיא נספרת; עבור `"Abc"` (אורך ) לא מודפס דבר, אבל היא נספרת (מתחילה ב-'A'); עבור `"xy"` יודפס `x y` והיא לא נספרת.
תשובה: קטע הקוד שלמעלה.
שאלה 3 · מספרים אקראיים וספירת מספרי "שבע-בול"
מספר "שבע-בול" הוא מספר שמתחלק ב- 7 ללא שארית לפחות אחת מהספרות שלו היא 7.
כתבו קטע תוכנית המייצרת 365 מספרים אקראיים תלת-ספרתיים שלמים חיוביים.
על התוכנית לחשב ולהדפיס כמה מהמספרים שנוצרו הם מספרים "שבע-בול".
◂ פתרון מלא לשאלה 3
פתרון
לולאה של סיבובים: מגרילים `num` בין ל-, מפרקים לספרות מאות, עשרות ואחדות, ומגדילים מונה אם `num % 7 == 0` וגם אחת הספרות שווה ; בסוף מדפיסים את המונה.
הרעיון: מגרילים מספרים בלולאה, ולכל אחד בודקים את שני התנאים של "שבע-בול": (1) מתחלק ב- ללא שארית, (2) לפחות אחת מספרותיו היא . שני התנאים צריכים להתקיים יחד (`&&`).
1. הגרלה: מספר תלת-ספרתי חיובי הוא בין ל-. לפי ההנחיות: `100 + (int)(Math.random() * (999 - 100 + 1))`, כלומר `100 + (int)(Math.random() * 900)`.
2. פירוק לספרות: ספרת האחדות `num % 10`, ספרת העשרות `num / 10 % 10`, ספרת המאות `num / 100`. לדוגמה, עבור : , , .
3. בדיקה: `num % 7 == 0` וגם (`units == 7 || tens == 7 || hundreds == 7`). אם כן – מגדילים את המונה.
4. אחרי הלולאה מדפיסים את המונה.
int count = 0; // מונה מספרי "שבע-בול"
for (int i = 1; i <= 365; i++)
{
int num = 100 + (int)(Math.random() * 900); // מספר אקראי בין 100 ל-999
int units = num % 10; // ספרת האחדות
int tens = num / 10 % 10; // ספרת העשרות
int hundreds = num / 100; // ספרת המאות
if (num % 7 == 0 && (units == 7 || tens == 7 || hundreds == 7))
count++;
}
System.out.println("sheva-bul numbers: " + count);Random rand = new Random();
int count = 0; // מונה מספרי "שבע-בול"
for (int i = 1; i <= 365; i++)
{
int num = rand.Next(100, 1000); // מספר אקראי בין 100 ל-999
int units = num % 10; // ספרת האחדות
int tens = num / 10 % 10; // ספרת העשרות
int hundreds = num / 100; // ספרת המאות
if (num % 7 == 0 && (units == 7 || tens == 7 || hundreds == 7))
count++;
}
Console.WriteLine("sheva-bul numbers: " + count);דוגמאות: ויש בו ספרה – "שבע-בול". – גם הוא "שבע-בול". – מתחלק ב- אבל אין בו ספרה , ולכן אינו "שבע-בול". – "שבע-בול".
תשובה: קטע הקוד שלמעלה.
שאלה 4 · בדיקת "מערך משולש"
מערך של מספרים שלמים נקרא "משולש" אם הוא עונה על שלושה תנאים:
•מספר איברי המערך מתחלק בשלוש.
•סכום ערכי האיברים הנמצאים בכל שליש מתחלק גם הוא בשלוש ללא שארית.
•במערך יש בדיוק שלושה איברים בעלי ערך 3.
המערך הבא הוא "מערך משולש":
כתבו פעולה המקבלת מערך של מספרים שלמים `arr`. הפעולה תחזיר ערך `true`, אם המערך הוא "מערך משולש", ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isTripple(int[] arr)public static bool IsTripple(int[] arr)◂ פתרון מלא לשאלה 4
פתרון
בודקים לפי הסדר: `arr.length % 3 == 0`; לכל אחד משלושת השלישים (בכל אחד `n/3` איברים) סכום שמתחלק ב-; ומונה האיברים השווים ל- שווה בדיוק . אם תנאי כלשהו נכשל – `false`.
הרעיון: בודקים את שלושת התנאים בזה אחר זה, ומחזירים `false` ברגע שאחד מהם לא מתקיים.
1. תנאי 1: אם `n % 3 != 0` (כאשר `n` אורך המערך) – מחזירים `false`. אחרת, בכל שליש יש `third = n / 3` איברים.
2. תנאי 2: השליש ה-`t` (עבור ) תופס את המקומות מ-`t * third` ועד `(t + 1) * third - 1`. מסכמים כל שליש בנפרד; אם סכום כלשהו אינו מתחלק ב- – מחזירים `false`. (גם סכום שלילי מתחלק ב- כאשר `sum % 3 == 0`.)
3. תנאי 3: סופרים את האיברים שערכם , ומחזירים `true` רק אם המונה שווה בדיוק .
בדיקה על הדוגמה: איברים, , ובכל שליש איברים:
•שליש ראשון (מקומות –): , מתחלק ב-.
•שליש שני (מקומות –): , מתחלק ב-.
•שליש שלישי (מקומות –): , מתחלק ב-.
•האיברים שערכם נמצאים במקומות – בדיוק שלושה.
לכן הפעולה מחזירה `true`.
public static boolean isTripple(int[] arr)
{
int n = arr.length;
if (n % 3 != 0) // תנאי 1
return false;
int third = n / 3; // מספר האיברים בכל שליש
for (int t = 0; t < 3; t++) // תנאי 2: כל שליש בנפרד
{
int sum = 0;
for (int i = t * third; i < (t + 1) * third; i++)
sum += arr[i];
if (sum % 3 != 0)
return false;
}
int count3 = 0; // תנאי 3: מספר האיברים שערכם 3
for (int i = 0; i < n; i++)
if (arr[i] == 3)
count3++;
return count3 == 3;
}public static bool IsTripple(int[] arr)
{
int n = arr.Length;
if (n % 3 != 0) // תנאי 1
return false;
int third = n / 3; // מספר האיברים בכל שליש
for (int t = 0; t < 3; t++) // תנאי 2: כל שליש בנפרד
{
int sum = 0;
for (int i = t * third; i < (t + 1) * third; i++)
sum += arr[i];
if (sum % 3 != 0)
return false;
}
int count3 = 0; // תנאי 3: מספר האיברים שערכם 3
for (int i = 0; i < n; i++)
if (arr[i] == 3)
count3++;
return count3 == 3;
}תשובה: הפעולה `isTripple` שלמעלה; עבור מערך הדוגמה היא מחזירה `true`.
שאלה 5 · איבר "נפילה" במערך וספירת נפילות
איבר במערך נקרא "נפילה" אם ערכו קטן מערכים של שני שכניו. תא ראשון או תא אחרון לא יכולים להיות נפילה.
כתבו פעולה המקבלת מערך של מספרים שלמים ומספר שלם המציין אינדקס (מיקום) במערך.
הפעולה תבדוק אם איבר שנמצא במקום הנתון הוא "נפילה". אם כן – הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isFall(int[] arr, int index)public static bool IsFall(int[] arr, int index)כתבו פעולה המקבלת מערך של מספרים שלמים ומחזירה את מספר הנפילות שיש בו.
חובה להשתמש בפעולה שכתבתם בסעיף א'.
מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו- ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 5
סעיף א
אם `index` הוא התא הראשון או האחרון (או מחוץ למערך) – `false`; אחרת מחזירים `arr[index] < arr[index-1] && arr[index] < arr[index+1]`.
הרעיון: לאיבר יש שני שכנים רק אם הוא אינו בקצה המערך. לכן קודם מטפלים בקצוות, ורק אחר כך משווים לשכנים.
1. אם `index <= 0` (התא הראשון) או `index >= arr.length - 1` (התא האחרון) – האיבר אינו יכול להיות "נפילה", ומחזירים `false`. בדיקה זו גם מונעת גישה ל-`arr[index - 1]` או ל-`arr[index + 1]` מחוץ לגבולות המערך.
2. אחרת, מחזירים `true` רק אם האיבר קטן ממש משני שכניו: `arr[index] < arr[index - 1]` וגם `arr[index] < arr[index + 1]`.
public static boolean isFall(int[] arr, int index)
{
if (index <= 0 || index >= arr.length - 1) // איבר ראשון, אחרון או מקום לא חוקי
return false;
return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
}public static bool IsFall(int[] arr, int index)
{
if (index <= 0 || index >= arr.Length - 1) // איבר ראשון, אחרון או מקום לא חוקי
return false;
return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
}דוגמה: במערך : במקום הערך קטן מ- ומ- – "נפילה"; במקום הערך קטן מ- ומ- – "נפילה"; מקום ומקום – לא.
תשובה: הפעולה `isFall` שלמעלה.
סעיף ב
עוברים על המקומות עד `arr.length-2`, מזמנים לכל מקום את `isFall`, וסופרים כמה פעמים הוחזר `true`.
הרעיון: "נפילה" יכולה להיות רק בתא פנימי, ולכן עוברים על המקומות מ- ועד `arr.length - 2` ולכל אחד שואלים את `isFall` מסעיף א'.
1. מאתחלים מונה `count = 0`.
2. בלולאה על `i` מ- כל עוד `i < arr.length - 1`: אם `isFall(arr, i)` מחזירה `true` – מגדילים את המונה.
3. מחזירים את המונה. במערך עם פחות משלושה איברים הלולאה לא מתבצעת ומוחזר , כנדרש (אין בו תא פנימי).
public static int countFalls(int[] arr)
{
int count = 0;
for (int i = 1; i < arr.length - 1; i++)
if (isFall(arr, i))
count++;
return count;
}public static int CountFalls(int[] arr)
{
int count = 0;
for (int i = 1; i < arr.Length - 1; i++)
if (IsFall(arr, i))
count++;
return count;
}דוגמה: עבור המערך הפעולה מחזירה (המקומות ו-; הערך במקום אינו קטן ממש מהשכן שבמקום ).
תשובה: הפעולה `countFalls` שלמעלה.
סעיף ג
`isFall` – ; `countFalls` – , כאשר אורך המערך.
1. `isFall` (סעיף א'): מבצעת מספר קבוע של השוואות (בדיקת הקצוות ושתי השוואות לשכנים), ללא לולאה, בלי תלות בגודל המערך. לכן הסיבוכיות .
2. `countFalls` (סעיף ב'): הלולאה רצה פעמים, ובכל סיבוב מזמנת את `isFall` שעולה . סך הכול .
תשובה: סעיף א' – ; סעיף ב' – .
שאלה 6 · מעקב אחר פעולת חלוקה לפי ספרת אחדות
נתונה הפעולה `mystery`. הפעולה מקבלת מערך של מספרים שלמים חיוביים `arr` וסיפרה `k`
public static void mystery(int[] arr, int k) {
int left = 0;
int right = arr.length-1;
while(left!=right)
{
if(arr[left]%10 < k)
left++;
else
if(arr[right]%10 > k)
right--;
else
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
right--;
}
}
}public static void Mystery(int[] arr, int k) {
int left = 0;
int right = arr.Length-1;
while(left!=right)
{
if(arr[left]%10 < k)
left++;
else
if(arr[right]%10 > k)
right--;
else
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
right--;
}
}
}נתון מערך מספרים שלמים `int[] arr = {128, 14, 313, 420, 17, 101}`.
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `mystery(arr, 4)` ורשמו מה יהיה תוכן של המערך `arr` אחרי ביצוע הפעולה.
נתון מערך מספרים שלמים `int[] arr = {128, 14, 313, 420, 17, 101}`
תנו דוגמה של מספר `k` כך שתוכן המערך הנתון `arr` לא ישתנה אחרי זימון הפעולה
`mystery(arr, k)`
האם קיימת ספרה `k` שעבורה כל מערך של מספרים שלמים וחיוביים `arr` לא ישתנה אחרי זימון הפעולה `mystery(arr, k)`? הסבירו את תשובתכם.
מה מבצעת הפעולה `mystery(a, k)` באופן כללי?
◂ פתרון מלא לשאלה 6
סעיף א
אחרי הפעולה: `arr = {101, 420, 313, 14, 17, 128}`.
בכל סיבוב בודקים קודם את ספרת האחדות של `arr[left]`: אם היא קטנה מ- – מקדמים את `left`. אחרת בודקים את ספרת האחדות של `arr[right]`: אם היא גדולה מ- – מקטינים את `right`. אחרת מחליפים בין `arr[left]` ל-`arr[right]` ומקטינים את `right`. הלולאה נעצרת כאשר `left == right`.
מצב התחלתי: `left = 0`, `right = 5`, המערך .
כעת `left = right = 2`, והלולאה מסתיימת.
תשובה: תוכן המערך אחרי הפעולה: .
סעיף ב
.
המערך משתנה רק כאשר מתבצעת החלפה, והחלפה מתבצעת רק כאשר ספרת האחדות של `arr[left]` אינה קטנה מ-`k`. לכן אם ספרות האחדות של כל האיברים קטנות מ-`k`, בכל סיבוב מתבצע `left++` בלבד, עד ש-`left` מגיע ל-`right`, ואין אף החלפה.
ספרות האחדות במערך הן , והגדולה שבהן . עבור כולן קטנות מ-: `left` מתקדם מ- עד בחמישה סיבובים, והמערך נשאר .
(זו הספרה היחידה שמתאימה: עבור כל בין ל- מתבצעת לפחות החלפה אחת שמשנה את המערך.)
תשובה: .
סעיף ג
לא. לכל ספרה המערך משתנה: שתי ספרות האחדות שוות ל-, ולכן מתבצעת החלפה והמערך הופך ל-.
לא קיימת ספרה כזאת. כדי להראות זאת מספיק למצוא, לכל ספרה , מערך אחד שמשתנה.
1. ניקח את המערך בן שני האיברים . שני האיברים חיוביים ושונים זה מזה, וספרת האחדות של שניהם היא .
2. בסיבוב הראשון `left = 0`, `right = 1`. ספרת האחדות של `arr[0]` היא , שאינה קטנה מ-; ספרת האחדות של `arr[1]` היא , שאינה גדולה מ-. לכן מתבצעת החלפה, ו-`right` יורד ל- והלולאה נעצרת.
3. המערך הפך ל- – כלומר השתנה.
לדוגמה, עבור (הספרה שהתאימה בסעיף ב') המערך הופך ל-.
תשובה: לא קיימת ספרה כזאת.
סעיף ד
מסדרת מחדש את המערך כך שכל האיברים שספרת האחדות שלהם קטנה מ-`k` נמצאים בתחילתו, ואחריהם כל האיברים שספרת האחדות שלהם גדולה מ-`k` או שווה לה.
הפעולה מחלקת את המערך לשני חלקים לפי ספרת האחדות של האיברים, בדומה לשלב החלוקה במיון מהיר:
1. `left` מתקדם מההתחלה כל עוד ספרת האחדות של `arr[left]` קטנה מ-`k`. כל מה שמשמאל ל-`left` הוא איבר "קטן" (ספרת אחדות קטנה מ-`k`).
2. `right` יורד מהסוף כל עוד ספרת האחדות של `arr[right]` גדולה מ-`k`. כל מה שמימין ל-`right` הוא איבר "גדול" (ספרת אחדות גדולה מ-`k` או שווה לה).
3. כאשר `arr[left]` אינו "קטן" ו-`arr[right]` אינו גדול מ-`k`, מחליפים ביניהם. האיבר שעבר למקום `right` ספרת האחדות שלו גדולה מ-`k` או שווה לה, ולכן אפשר להוציא אותו מהתחום (`right--`). האיבר שעבר ל-`left` ייבדק בסיבוב הבא.
4. הלולאה מסתיימת כאשר `left == right`, וכל איבר נמצא בצד הנכון.
בסעיף א', למשל, עבור התקבל : ספרות האחדות (קטנות מ-) בהתחלה, ואחריהן .
הפעולה אינה ממיינת: הסדר בתוך כל אחד משני החלקים יכול להשתנות.
תשובה: הפעולה מסדרת את המערך כך שבתחילתו כל האיברים שספרת האחדות שלהם קטנה מ-`k`, ואחריהם כל האיברים שספרת האחדות שלהם גדולה מ-`k` או שווה לה.
שאלה 7 · המחלקה Game: החלפת משחקים ומתנה לתאומים
החנות "Game4U" מוכרת משחקי שולחן לילדים. לשם ניהול ממוחשב של המכירות הוגדרה המחלקה `Game` ולה ארבע תכונות:
שם המשחק – `name`, מטיפוס מחרוזת, `String`
גיל מינימלי – `minAge`, מטיפוס מספר שלם, `int`
מספר שחקנים – `numPlayers`, מטיפוס מספר שלם, `int`
מחיר – `price`, מטיפוס מספר ממשי, `double`
למחלקה הוגדרו פעולה בונה (constructor), פעולות `get/set` והפעולה `toString`
לקוח יכול להחליף את המשחק שקנה למשחק אחר בתנאי שהגיל מינימלי של שני משחקים זהה והמחיר של המשחק האחר לא גבוה מהמחיר שקנה הלקוח.
כתבו פעולה המקבלת הפניה למשחק בשם `other` (הפניה לעצם מטיפוס `Game`). הפעולה תבדוק אם אפשר להחליף משחק `this` למשחק `other`. אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`. כותרת הפעולה:
public boolean canReplace(Game other)כתבו פעולה המקבלת מערך משחקים `arr` ומשחק `myGame` שהלקוח מעוניין להחליף. הפעולה תמנה ותחזיר את מספר המשחקים אשר מתאימים להחלפה.
כותרת הפעולה:
public static int replace(Game[] arr, Game myGame)סבא וסבתא של התאומים אורי ודורון רוצים לקנות להם מתנות ליום ההולדת החמישי שלהם.
ליאור, האחות הגדולה של התאומים, ביקשה שבכל משחק יוכלו לשחק לפחות שלושה שחקנים.
כתבו פעולה המקבלת מערך משחקים ומדפיסה את כל הצירופים האפשריים של שני משחקים שונים שעולים יחד פחות מ- 200 ₪.
כותרת הפעולה:
public static void giftForTwins(Game[] arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים ב' ו- ג'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
מחזירים `this.minAge == other.getMinAge() && other.getPrice() <= this.price`.
הרעיון: הפעולה נכתבת בתוך המחלקה `Game`, ולכן יש לה גישה ישירה לתכונות של `this`. את התכונות של `other` קוראים בעזרת פעולות ה-`get`.
שני התנאים להחלפה צריכים להתקיים יחד (`&&`):
1. הגיל המינימלי זהה: `this.minAge == other.getMinAge()`.
2. מחיר המשחק האחר "לא גבוה" ממחיר המשחק שנקנה, כלומר קטן או שווה: `other.getPrice() <= this.price`.
מחזירים ישירות את ערך הביטוי הבוליאני.
public boolean canReplace(Game other)
{
return this.minAge == other.getMinAge() && other.getPrice() <= this.price;
}public bool canReplace(Game other)
{
return this.minAge == other.GetMinAge() && other.GetPrice() <= this.price;
}תשובה: הפעולה `canReplace` שלמעלה.
סעיף ב
עוברים על המערך וסופרים את המשחקים `arr[i]` (שאינם `myGame` עצמו) שעבורם `myGame.canReplace(arr[i])` מחזירה `true`.
הרעיון: משחק `arr[i]` מתאים להחלפה אם אפשר להחליף אליו את `myGame`, כלומר אם `myGame.canReplace(arr[i])` (מסעיף א') מחזירה `true`. עוברים על כל המערך וסופרים.
1. מאתחלים מונה `count = 0`.
2. לכל `i`: אם `arr[i]` אינו העצם `myGame` עצמו (החלפה של משחק בעצמו אינה החלפה) וגם `myGame.canReplace(arr[i])` – מגדילים את המונה.
3. מחזירים את המונה.
public static int replace(Game[] arr, Game myGame)
{
int count = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] != myGame && myGame.canReplace(arr[i]))
count++;
return count;
}public static int replace(Game[] arr, Game myGame)
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
if (arr[i] != myGame && myGame.canReplace(arr[i]))
count++;
return count;
}דוגמה: אם `myGame` הוא משחק לגיל במחיר , ובמערך יש עוד משחקים לגיל במחירים ו- ומשחקים לגיל – הפעולה מחזירה .
תשובה: הפעולה `replace` שלמעלה.
סעיף ג
שתי לולאות מקוננות על זוגות ; מדפיסים את הזוג אם בשני המשחקים `getMinAge() <= 5` (מתאים לילדים בני ) וגם `getNumPlayers() >= 3`, וגם סכום המחירים קטן מ-.
הרעיון: צירוף של שני משחקים שונים הוא זוג מקומות במערך. כדי שכל זוג יודפס פעם אחת בלבד (ולא גם בסדר הפוך, ולא משחק עם עצמו), הלולאה הפנימית מתחילה ב-`j = i + 1`.
1. הלולאה החיצונית עוברת על `i` מ- עד `arr.length - 2`, והפנימית על `j` מ-`i + 1` עד `arr.length - 1`.
2. לכל זוג בודקים שלושה תנאים:
•שני המשחקים מתאימים לגיל התאומים: המתנה היא ליום ההולדת החמישי, ולכן הגיל המינימלי של כל משחק לכל היותר : `getMinAge() <= 5` לשניהם;
•בכל אחד משני המשחקים יכולים לשחק לפחות שלושה שחקנים: `getNumPlayers() >= 3` לשניהם (הבקשה של ליאור);
•המחיר המשותף פחות מ- ₪: `arr[i].getPrice() + arr[j].getPrice() < 200`.
3. אם כל התנאים מתקיימים – מדפיסים את שני המשחקים (בעזרת `toString` של המחלקה).
public static void giftForTwins(Game[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
for (int j = i + 1; j < arr.length; j++)
if (arr[i].getMinAge() <= 5 && arr[j].getMinAge() <= 5 // מתאים לגיל 5
&& arr[i].getNumPlayers() >= 3 && arr[j].getNumPlayers() >= 3
&& arr[i].getPrice() + arr[j].getPrice() < 200)
System.out.println(arr[i] + " + " + arr[j]);
}public static void giftForTwins(Game[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
for (int j = i + 1; j < arr.Length; j++)
if (arr[i].GetMinAge() <= 5 && arr[j].GetMinAge() <= 5 // מתאים לגיל 5
&& arr[i].GetNumPlayers() >= 3 && arr[j].GetNumPlayers() >= 3
&& arr[i].GetPrice() + arr[j].GetPrice() < 200)
Console.WriteLine(arr[i] + " + " + arr[j]);
}דוגמה: עבור המשחקים: "Memory" (גיל , שחקנים, ₪), "Ladders" (גיל , שחקנים, ₪), "Domino" (גיל , שחקנים, ₪), "Lotto" (גיל , שחקנים, ₪) ו-"Uno" (גיל , שחקנים, ₪): "Domino" נפסל (רק שחקנים), "Uno" נפסל (גיל ). מבין הזוגות הנותרים רק Memory + Ladders עולה פחות מ- (); Memory + Lotto עולה ו-Ladders + Lotto עולה . לכן יודפס זוג אחד.
תשובה: הפעולה `giftForTwins` שלמעלה.
סעיף ד
`replace` – ; `giftForTwins` – , כאשר מספר המשחקים במערך.
נסמן ב- את מספר המשחקים במערך.
1. `replace` (סעיף ב'): לולאה אחת של סיבובים, ובכל סיבוב זימון של `canReplace` שמבצעת שתי השוואות בלבד – . סך הכול .
2. `giftForTwins` (סעיף ג'): שתי לולאות מקוננות שעוברות על כל הזוגות . מספר הזוגות הוא , ולכל זוג מתבצעת בדיקה בזמן קבוע. סך הכול .
תשובה: סעיף ב' – ; סעיף ג' – .
שאלה 8 · "סט שלם של ספרות" במערך ובתת-מערך
כתבו פעולה המקבלת מספר שלם וחיובי `num` וספרה `dig`. הפעולה תבדוק אם `dig` היא אחת מהספרות של `num`. אם כן, הפעולה תחזיר `true`, ולא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static boolean exists(int num, int dig)public static bool Exists(int num, int dig)אוסף של מספרים שלמים חיוביים נקרא "סט שלם של ספרות" אם כל הספרות בין 0 ל- 9 מופיעות בו לפחות פעם אחת.
המערך `arr1` הוא "סט שלם של ספרות"
arr1:
גם שני תת-מערכים
הם "סט שלם של ספרות" כל אחד
המערך הבא הוא לא " סט שלם של ספרות " כי סיפרה 7 לא מופיעה באף אחד מהאיברי המערך.
arr2:
כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים ושני מספרים נוספים המציינים אינדקס (מיקום במערך). הפעולה תבדוק אם תת-מערך (רצף תאים בין שני האינדקסים) הוא "סט שלם של ספרות". אם כן – הפעולה תחזיר ערך `true`, ולא – תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isFullSet(int[] arr, int left, int right)public static bool IsFullSet(int[] arr, int left, int right)כתבו פעולה המקבלת מערך של מספרים שלמים וחיוביים. הפעולה תחזיר אורך (מספר תאים) של תת-המערך הקטן ביותר, שהוא "סט שלם של ספרות" (כהגדרתו בסעיף ב'). אם אין אף תת-מערך שהוא "סט שלם של ספרות", הפעולה תחזיר ערך (1-).
עבור המערך `arr1` (מהדוגמה בסעיף ב') הפעולה תחזיר 5, עבור המערך `arr2` (מהדוגמה בסעיף ב') הפעולה תחזיר (1-).
כותרת הפעולה:
public static int minFullSet(int[] arr)public static int MinFullSet(int[] arr)◂ פתרון מלא לשאלה 8
סעיף א
מפרקים את `num` לספרות (`num % 10`, ואז `num / 10`) ומחזירים `true` ברגע שספרה שווה ל-`dig`; אם הספרות נגמרו – `false`.
הרעיון: מפרקים את המספר לספרותיו מימין לשמאל: `num % 10` היא ספרת האחדות, ו-`num / 10` מוחק אותה. משווים כל ספרה ל-`dig`.
1. כל עוד `num > 0`: אם `num % 10 == dig` – הספרה נמצאה, ומחזירים `true`.
2. אחרת מקצרים את המספר: `num = num / 10`.
3. אם המספר הגיע ל- והספרה לא נמצאה – מחזירים `false`.
לדוגמה, `exists(205, 0)`: , ואז – מוחזר `true`. המספר חיובי, ולכן גם ספרה בתוך המספר מתגלה כך.
public static boolean exists(int num, int dig)
{
while (num > 0)
{
if (num % 10 == dig)
return true;
num = num / 10;
}
return false;
}public static bool Exists(int num, int dig)
{
while (num > 0)
{
if (num % 10 == dig)
return true;
num = num / 10;
}
return false;
}תשובה: הפעולה `exists` שלמעלה.
סעיף ב
לכל ספרה `dig` מ- עד מחפשים איבר בתחום `arr[left..right]` שעבורו `exists(arr[i], dig)`; אם יש ספרה שלא נמצאה – `false`, ואם כל עשר הספרות נמצאו – `true`.
הרעיון: התת-מערך הוא "סט שלם" אם כל אחת מעשר הספרות מופיעה באיבר כלשהו שלו. לכן לולאה חיצונית על הספרות –, ולולאה פנימית שמחפשת את הספרה באיברי התחום בעזרת `exists` מסעיף א'. (מניחים ש-`left <= right` ושניהם מקומות חוקיים במערך.)
1. לכל ספרה `dig` מ- עד : מאתחלים `found = false`.
2. עוברים על המקומות `i` מ-`left` עד `right` (כולל), ואם `exists(arr[i], dig)` – מסמנים `found = true` ומפסיקים לחפש.
3. אם אחרי החיפוש `found` עדיין `false` – הספרה חסרה, ומחזירים `false` מיד.
4. אם כל עשר הספרות נמצאו – מחזירים `true`.
בדיקה על הדוגמה: בתחום – של `arr1` () מופיעות הספרות – כל עשר הספרות, ולכן `isFullSet(arr1, 1, 5)` מחזירה `true`. ב-`arr2` אין אף איבר עם הספרה , ולכן `isFullSet(arr2, 0, 9)` מחזירה `false`.
public static boolean isFullSet(int[] arr, int left, int right)
{
for (int dig = 0; dig <= 9; dig++)
{
boolean found = false;
for (int i = left; i <= right && !found; i++)
if (exists(arr[i], dig))
found = true;
if (!found) // הספרה dig לא מופיעה באף איבר בתחום
return false;
}
return true;
}public static bool IsFullSet(int[] arr, int left, int right)
{
for (int dig = 0; dig <= 9; dig++)
{
bool found = false;
for (int i = left; i <= right && !found; i++)
if (Exists(arr[i], dig))
found = true;
if (!found) // הספרה dig לא מופיעה באף איבר בתחום
return false;
}
return true;
}תשובה: הפעולה `isFullSet` שלמעלה.
סעיף ג
עוברים על האורכים `len` מ- עד `n`, ולכל אורך על כל נקודות ההתחלה `left`; התת-מערך הראשון שעבורו `isFullSet(arr, left, left+len-1)` מחזירה `true` קובע את התשובה `len`; אם לא נמצא – .
הרעיון: בודקים את התת-מערכים לפי אורכם, מהקצר לארוך. ברגע שנמצא תת-מערך שהוא "סט שלם של ספרות", האורך שלו הוא בהכרח הקטן ביותר (כל האורכים הקטנים ממנו כבר נבדקו ונכשלו), ומחזירים אותו מיד.
1. נסמן `n = arr.length`.
2. לולאה חיצונית על האורך `len` מ- עד `n`.
3. לולאה פנימית על נקודת ההתחלה `left`, כל עוד התא האחרון `left + len - 1` נמצא בתוך המערך.
4. אם `isFullSet(arr, left, left + len - 1)` (מסעיף ב') מחזירה `true` – מחזירים `len`.
5. אם נבדקו כל התת-מערכים (כולל המערך כולו, `len = n`) ואף אחד אינו "סט שלם" – מחזירים .
•ב-`arr1` אף תת-מערך באורך או פחות אינו מכיל את כל עשר הספרות, ותת-המערך במקומות – (אורך ) כן מכיל אותן. מוחזר .
•ב-`arr2` הספרה לא מופיעה כלל, ולכן אף תת-מערך אינו "סט שלם". מוחזר .
public static int minFullSet(int[] arr)
{
int n = arr.length;
for (int len = 1; len <= n; len++) // אורכים מהקטן לגדול
for (int left = 0; left + len - 1 < n; left++)
if (isFullSet(arr, left, left + len - 1))
return len; // האורך הראשון שנמצא הוא הקטן ביותר
return -1;
}public static int MinFullSet(int[] arr)
{
int n = arr.Length;
for (int len = 1; len <= n; len++) // אורכים מהקטן לגדול
for (int left = 0; left + len - 1 < n; left++)
if (IsFullSet(arr, left, left + len - 1))
return len; // האורך הראשון שנמצא הוא הקטן ביותר
return -1;
}תשובה: הפעולה `minFullSet` שלמעלה; עבור `arr1` היא מחזירה ועבור `arr2` היא מחזירה .
שאלה 9 · המחלקות Shirt ו-Storage: חולצות לפי מותג
החנות "חלץ לך חולצה" מוכרת חולצות של מותגים שונים באמצעות האינטרנט. לשם כך הוגדרו מחלקות `Shirt` ו- `Storage`.
המחלקה `Shirt` מייצגת חולצה. למחלקה ארבע התכונות הבאות:
•קוד מתנה – `code` – מטיפוס מספר שלם, `int`
•שם מותג – `brand` – מטיפוס מחרוזת, `String`
•מחיר – `price` – מטיפוס ממשי, `double`
•סוג חולצה (למי מיועדת החולצה) – `type` – מטיפוס תו, `char`.
התכונה יכולה לקבל אחת משלוש אפשרויות:
'F' – חולצות לנשים, 'M' – לגברים , 'K' – לילדים.
במחלקה הוגדרו פעולה בונה ופעולות `get` לכל תכונה.
כתבו פעולה `void setType(char type)`. הפעולה מעדכנת את התכונה `type` בהתאם לפרמטר.
<u>אם הפרמטר שהפעולה מקבלת אינו תקין, העדכון לא מתבצע.</u>
המחלקה `Storage` מייצגת מחסן של חנות. למחלקה שתי התכונות הבאות:
•מערך חולצות – `shirts` – מערך עצמים מסוג `Shirt`
•מערך מותגים שהחנות מוכרת – `brands` – מערך של מחרוזות
כתבו במחלקה `Storage` פעולה המקבלת שם מותג וסוג חולצה. הפעולה תחזיר מערך חולצות של אותו מותג וסוג.
כותרת הפעולה:
public Shirt[] shirtsByBrand(String brand, char type)public Shirt[] ShirtsByBrand(string brand, char type)אם בחנות אין חולצות מתאימות, הפעולה תחזיר ערך `null`.
החנות רוצה להכריז על מבצע המיועד למשפחות: כל מי שמזמין שתי חולצות של אותו מותג (אחת לנשים ואחרת לגברים), יכול לקבל חולצה לילד (של אותו המותג) במתנה.
כתבו במחלקה `Storage` פעולה המדפיסה שמות של כל המותגים אשר יוכלו להשתתף במבצע.
כותרת הפעולה:
public void print()public void print()מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיפים ב' ו- ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
מעדכנים `this.type = type` רק אם `type` הוא `'F'`, `'M'` או `'K'`; אחרת לא עושים דבר.
הרעיון: ערך תקין הוא אחד משלושת התווים `'F'`, `'M'`, `'K'`. בודקים את הפרמטר, ומעדכנים את התכונה רק אם הוא תקין.
1. אם `type == 'F' || type == 'M' || type == 'K'` – מבצעים `this.type = type` (ה-`this` מבדיל בין התכונה לפרמטר בעל אותו שם).
2. אחרת – הפעולה מסתיימת בלי לשנות דבר.
public void setType(char type)
{
if (type == 'F' || type == 'M' || type == 'K')
this.type = type;
}public void setType(char type)
{
if (type == 'F' || type == 'M' || type == 'K')
this.type = type;
}תשובה: הפעולה `setType` שלמעלה.
סעיף ב
מעבר ראשון סופר את החולצות שהמותג שלהן `brand` והסוג שלהן `type`; אם אין – `null`; אחרת יוצרים מערך בגודל המונה ובמעבר שני מעתיקים אליו את החולצות המתאימות.
הרעיון: את גודל המערך שמוחזר צריך לדעת לפני שיוצרים אותו, ולכן עוברים על מערך החולצות פעמיים: פעם לספירה ופעם להעתקה.
1. ספירה: עוברים על `shirts` וסופרים את החולצות שהמותג שלהן שווה ל-`brand` (השוואת מחרוזות ב-`equals`) וגם הסוג שלהן שווה ל-`type`.
2. אם המונה – אין חולצות מתאימות, ומחזירים `null`.
3. העתקה: יוצרים מערך `result` בגודל המונה, ובמעבר שני מעתיקים אליו את החולצות המתאימות. המשתנה `k` מסמן את המקום הפנוי הבא ב-`result`.
4. מחזירים את `result`.
public Shirt[] shirtsByBrand(String brand, char type)
{
int count = 0; // מעבר ראשון: כמה חולצות מתאימות
for (int i = 0; i < shirts.length; i++)
if (shirts[i].getBrand().equals(brand) && shirts[i].getType() == type)
count++;
if (count == 0)
return null;
Shirt[] result = new Shirt[count]; // מעבר שני: העתקת החולצות המתאימות
int k = 0;
for (int i = 0; i < shirts.length; i++)
if (shirts[i].getBrand().equals(brand) && shirts[i].getType() == type)
{
result[k] = shirts[i];
k++;
}
return result;
}public Shirt[] ShirtsByBrand(string brand, char type)
{
int count = 0; // מעבר ראשון: כמה חולצות מתאימות
for (int i = 0; i < shirts.Length; i++)
if (shirts[i].GetBrand() == brand && shirts[i].GetType() == type)
count++;
if (count == 0)
return null;
Shirt[] result = new Shirt[count]; // מעבר שני: העתקת החולצות המתאימות
int k = 0;
for (int i = 0; i < shirts.Length; i++)
if (shirts[i].GetBrand() == brand && shirts[i].GetType() == type)
{
result[k] = shirts[i];
k++;
}
return result;
}תשובה: הפעולה `shirtsByBrand` שלמעלה.
סעיף ג
לכל מותג במערך `brands` מדפיסים את שמו אם `shirtsByBrand` מחזירה מערך (לא `null`) עבור כל אחד משלושת הסוגים `'F'`, `'M'` ו-`'K'`.
הרעיון: מותג יכול להשתתף במבצע רק אם בחנות יש ממנו חולצה לנשים, חולצה לגברים (את שתיהן הלקוח קונה) וגם חולצה לילדים (המתנה). את הבדיקה לכל סוג אפשר לעשות בעזרת `shirtsByBrand` מסעיף ב': היא מחזירה `null` בדיוק כשאין חולצה מתאימה.
1. עוברים על כל שמות המותגים במערך `brands`.
2. לכל מותג `b` בודקים ש-`shirtsByBrand(b, 'F')`, `shirtsByBrand(b, 'M')` ו-`shirtsByBrand(b, 'K')` כולן שונות מ-`null`.
3. אם כן – מדפיסים את שם המותג.
public void print()
{
for (int i = 0; i < brands.length; i++)
{
String b = brands[i];
if (shirtsByBrand(b, 'F') != null && shirtsByBrand(b, 'M') != null
&& shirtsByBrand(b, 'K') != null)
System.out.println(b);
}
}public void print()
{
for (int i = 0; i < brands.Length; i++)
{
string b = brands[i];
if (ShirtsByBrand(b, 'F') != null && ShirtsByBrand(b, 'M') != null
&& ShirtsByBrand(b, 'K') != null)
Console.WriteLine(b);
}
}תשובה: הפעולה `print` שלמעלה.
סעיף ד
`shirtsByBrand` – ; `print` – , כאשר מספר החולצות ו- מספר המותגים.
נסמן ב- את מספר החולצות במערך `shirts` וב- את מספר המותגים במערך `brands`.
1. `shirtsByBrand` (סעיף ב'): שני מעברים נפרדים (לא מקוננים) על מערך החולצות, ובכל צעד השוואה בזמן קבוע (אורך שם מותג אינו תלוי ב-). סך הכול צעדים, כלומר .
2. `print` (סעיף ג'): לולאה על המותגים, ובכל סיבוב עד שלושה זימונים של `shirtsByBrand`, כל אחד . סך הכול .
תשובה: סעיף ב' – ; סעיף ג' – .
שאלה 10 · פעולת השוואה בין שני מערכים ושיפור יעילות
נתונה הפעולה `what` המקבלת שני מערכים של מספרים שלמים:
public static boolean what(int[] arr1, int[] arr2)
{
for (int i = 0; i < arr1.length; i++)
{
for (int k = 0; k < arr2.length; k++)
{
if (arr1[i] >= arr2[k])
return true; // (*)
}
}
return false; // (**)
}public static bool What(int[] arr1, int[] arr2)
{
for (int i = 0; i < arr1.Length; i++)
{
for (int k = 0; k < arr2.Length; k++)
{
if (arr1[i] >= arr2[k])
return true; // (*)
}
}
return false; // (**)
}עקבו בעזרת טבלת מעקב אחר ביצוע הפעולה `what` עבור הפרמטרים הבאים:
int[] arr1 = {4,6,2,7}
int[] arr2 = {8,7,9}מה מבצעת הפעולה `what` באופן כללי?
מהי הסיבוכיות של הפעולה `what`? הסבירו את תשובתכם.
כתבו פעולה חדשה, יעילה יותר, אשר מבצעת אותה מטלה כמו הפעולה `what`.
מהי הסיבוכיות של הפעולה החדשה? הסבירו את תשובתכם.
בפעולה `what` נעשו שני שינויים:
•הפקודה `(*)` הוחלפה ל- `return false`
•הפקודה `()` הוחלפה ל- `return true`
מה מבצעת הפעולה `what` באופן כללי אחרי השינוי?
◂ פתרון מלא לשאלה 10
סעיף א
הפעולה מחזירה `true` (בהשוואה `arr1[3] >= arr2[1]`, כלומר ).
הלולאה החיצונית עוברת על איברי `arr1`, והפנימית משווה כל אחד מהם לכל איברי `arr2`. ברגע שמתקיים `arr1[i] >= arr2[k]` הפעולה מחזירה `true` (שורה `(*)`).
תשובה: הפעולה מחזירה `true`.
סעיף ב
מחזירה `true` אם יש איבר ב-`arr1` שגדול או שווה לאיבר כלשהו ב-`arr2` (כלומר המקסימום של `arr1` גדול או שווה למינימום של `arr2`), ואחרת `false`.
הפעולה בודקת את כל הזוגות של איבר מ-`arr1` ואיבר מ-`arr2`:
1. אם נמצא זוג אחד לפחות שבו `arr1[i] >= arr2[k]` – מוחזר `true`.
2. אם כל הזוגות נבדקו ואין כזה – כלומר כל איברי `arr1` קטנים ממש מכל איברי `arr2` – מוחזר `false`.
ניסוח שקול: קיים זוג כזה בדיוק כאשר האיבר הגדול ביותר ב-`arr1` גדול או שווה לאיבר הקטן ביותר ב-`arr2`. (אם הגדול ב-`arr1` קטן מהקטן ב-`arr2`, כל איבר ב-`arr1` קטן מכל איבר ב-`arr2`.)
בסעיף א' האיבר הגדול ב-`arr1` הוא והקטן ב-`arr2` הוא , ו-, ולכן התקבל `true`.
תשובה: הפעולה מחזירה `false` אם כל איברי `arr1` קטנים מכל איברי `arr2`, ואחרת `true`.
סעיף ג
, כאשר ו- אורכי `arr1` ו-`arr2`.
נסמן – אורך `arr1`, – אורך `arr2`. במקרה הגרוע (כאשר מוחזר `false`) הלולאות המקוננות בודקות את כל הזוגות, וכל בדיקה בזמן קבוע.
תשובה: .
סעיף ד
מוצאים את המקסימום של `arr1` ואת המינימום של `arr2` (בשתי לולאות נפרדות) ומחזירים `max1 >= min2` (ועבור מערך ריק – `false`).
הרעיון: לפי סעיף ב', `what` מחזירה `true` בדיוק כאשר האיבר הגדול ביותר ב-`arr1` גדול או שווה לאיבר הקטן ביותר ב-`arr2`. לכן אין צורך לבדוק את כל הזוגות: מספיק למצוא את המקסימום של `arr1` ואת המינימום של `arr2`.
1. אם אחד המערכים ריק – `what` המקורית אינה נכנסת לבדיקה ומחזירה `false`; גם הפעולה החדשה מחזירה `false`.
2. מוצאים את `max1` – האיבר הגדול ביותר ב-`arr1` – במעבר אחד.
3. מוצאים את `min2` – האיבר הקטן ביותר ב-`arr2` – במעבר אחד.
4. מחזירים `max1 >= min2`.
public static boolean whatFast(int[] arr1, int[] arr2)
{
if (arr1.length == 0 || arr2.length == 0)
return false;
int max1 = arr1[0]; // האיבר הגדול ביותר ב-arr1
for (int i = 1; i < arr1.length; i++)
if (arr1[i] > max1)
max1 = arr1[i];
int min2 = arr2[0]; // האיבר הקטן ביותר ב-arr2
for (int k = 1; k < arr2.length; k++)
if (arr2[k] < min2)
min2 = arr2[k];
return max1 >= min2;
}public static bool WhatFast(int[] arr1, int[] arr2)
{
if (arr1.Length == 0 || arr2.Length == 0)
return false;
int max1 = arr1[0]; // האיבר הגדול ביותר ב-arr1
for (int i = 1; i < arr1.Length; i++)
if (arr1[i] > max1)
max1 = arr1[i];
int min2 = arr2[0]; // האיבר הקטן ביותר ב-arr2
for (int k = 1; k < arr2.Length; k++)
if (arr2[k] < min2)
min2 = arr2[k];
return max1 >= min2;
}עבור הדוגמה של סעיף א': `max1` , `min2` , ו- – מוחזר `true`, כמו ב-`what`.
תשובה: הפעולה `whatFast` שלמעלה.
סעיף ה
.
הפעולה עוברת פעם אחת על `arr1` ( צעדים) ופעם אחת על `arr2` ( צעדים), בשתי לולאות נפרדות (לא מקוננות), וכל צעד בזמן קבוע. סך הכול צעדים.
תשובה: – סיבוכיות לינארית.
סעיף ו
מחזירה `true` רק אם כל איברי `arr1` קטנים ממש מכל איברי `arr2` (המקסימום של `arr1` קטן מהמינימום של `arr2`), ואחרת `false` – ההפך מהפעולה המקורית.
אחרי השינוי:
1. ברגע שנמצא זוג שבו `arr1[i] >= arr2[k]` – מוחזר `false`.
2. אם כל הזוגות נבדקו ואין זוג כזה – מוחזר `true`.
כלומר מוחזר `true` בדיוק כאשר לכל ולכל מתקיים `arr1[i] < arr2[k]` – כל איברי `arr1` קטנים ממש מכל איברי `arr2`, ובניסוח שקול: האיבר הגדול ביותר ב-`arr1` קטן מהאיבר הקטן ביותר ב-`arr2`. התוצאה היא תמיד ההפך מהתוצאה של הפעולה המקורית.
לדוגמה, עבור המערכים של סעיף א' הפעולה אחרי השינוי מחזירה `false` (כי ).
תשובה: הפעולה בודקת אם כל איברי `arr1` קטנים מכל איברי `arr2`; אם כן מחזירה `true`, ואחרת `false`.
שאלה 11 · מעקב אחר פעולות מחרוזת: הסרת מופעי תו
נתונות פעולות הבאות:
public static String one(String s, char ch, int k)
{
String res = "";
while(k>0 && s.length() > 0)
{
if(s.charAt(0) == ch)
{
k = k - 1;
}
else
{
res = res + s.charAt(0);
}
s = s.substring(1);
}
return res + s;
}
public static boolean two(String[] arr, char ch)
{
for(int i =1; i < arr.length; i+=2)
{
if(!arr[i].equals(one(arr[i-1], ch, i)))
{
return false;
}
}
return true;
}public static string One(string s, char ch, int k)
{
string res = "";
while(k>0 && s.Length > 0)
{
if(s[0] == ch)
{
k = k - 1;
}
else
{
res = res + s[0];
}
s = s.Substring(1);
}
return res + s;
}
public static bool Two(string[] arr, char ch)
{
for(int i =1; i < arr.Length; i+=2)
{
if(arr[i] != (One(arr[i-1], ch, i)))
{
return false;
}
}
return true;
}מה תהיה תוצאת הזימון `one(s1, 'A', 2)` עבור מחרוזת `s1="AABBAAD"`? יש להראות מעקב!
מה תהיה תוצאת הזימון `one(s1, 'F', 3)` עבור מחרוזת `s1="AABBAAD"`?
נתונה מחרוזת `s2="AABCCDDC"`. תנו דוגמה לפרמטרים `k` ו- `ch` כך שתוצאת הזימון `one(s2, ch, k)` תהיה מחרוזת `s3="AABDDC"`.
מה מבצעת הפעולה `one`?
תנו דוגמה למערך `arr` של שמונה מחרוזות שונות זו מזו , שעבורו זימון הפעולה `two(arr, 'Z')` יחזיר `true`.
◂ פתרון מלא לשאלה 11
סעיף א
`"BBAAD"`.
בכל סיבוב בודקים את התו הראשון של `s`: אם הוא `ch` – מקטינים את `k` (התו "נמחק"), ואחרת מוסיפים אותו ל-`res`. בסוף הסיבוב מסירים את התו הראשון מ-`s`. הלולאה נעצרת כאשר `k` מגיע ל- או כאשר `s` מתרוקנת, ואז מוחזר `res + s`.
מצב התחלתי: `s = "AABBAAD"`, `ch = 'A'`, `k = 2`, `res = ""`.
כעת `k = 0` והלולאה נעצרת. מוחזר `res + s` `"" + "BBAAD"` `"BBAAD"`.
תשובה: `"BBAAD"`.
סעיף ב
`"AABBAAD"` (המחרוזת לא משתנה).
התו `'F'` אינו מופיע ב-`s1`, ולכן `k` נשאר כל הזמן, וכל תו מועבר מ-`s` ל-`res`:
`s` התרוקנה והלולאה נעצרת. מוחזר `"AABBAAD" + ""`.
תשובה: `"AABBAAD"`.
סעיף ג
`ch = 'C'`, `k = 2`.
משווים את `s2 = "AABCCDDC"` ל-`s3 = "AABDDC"`: ב-`s3` חסרים שני התווים `'C'` שבמקומות ו-, וה-`'C'` האחרון נשאר. הפעולה `one` מוחקת את המופעים הראשונים של `ch`, לכל היותר `k` מופעים, ולכן צריך `ch = 'C'` ו-`k = 2`.
בדיקה: `"A"`, `"A"`, `"B"` עוברים ל-`res`; שני ה-`'C'` נמחקים ו-`k` יורד ל-; הלולאה נעצרת עם `res = "AAB"` ו-`s = "DDC"`, ומוחזר `"AABDDC"`.
תשובה: `one(s2, 'C', 2)`.
סעיף ד
מחזירה את המחרוזת `s` אחרי מחיקת `k` המופעים הראשונים של התו `ch` (או כל המופעים, אם יש פחות מ-`k`).
כל מופע של `ch` שנמצא בתחילת `s` אינו מועתק ל-`res` ומקטין את `k` ב-; כל תו אחר מועתק ל-`res` לפי הסדר. כאשר `k` מגיע ל-, שאר המחרוזת מצורף כמו שהוא. לכן התוצאה היא `s` בלי `k` המופעים הראשונים של `ch`. אם `ch` מופיע פחות מ-`k` פעמים – כל מופעיו נמחקים. אם `k <= 0` – המחרוזת מוחזרת ללא שינוי.
תשובה: הפעולה מחזירה את `s` אחרי מחיקת `k` המופעים הראשונים של התו `ch`.
סעיף ה
למשל `{"ZA", "A", "ZZZB", "B", "ZZZZZC", "C", "ZD", "D"}`.
מה בודקת `two`: לכל מקום אי-זוגי `i` () היא בודקת ש-`arr[i]` שווה ל-`one(arr[i-1], 'Z', i)`, כלומר ל-`arr[i-1]` אחרי מחיקת `i` המופעים הראשונים של `'Z'`. אם כל הבדיקות מצליחות מוחזר `true`.
1. כל מחרוזת במקום זוגי חייבת להכיל `'Z'`: אחרת `one` מחזירה אותה ללא שינוי, והמחרוזת במקום שאחריה תהיה זהה לה – בניגוד לדרישה שהמחרוזות שונות.
2. נבחר בכל מקום זוגי מחרוזת עם `'Z'`, ובמקום שאחריה את המחרוזת בלי ה-`'Z'`:
בכל שורה מספר ה-`'Z'` במחרוזת לכל היותר `i`, ולכן כולן נמחקות. כל שמונה המחרוזות שונות זו מזו, וכל ארבע הבדיקות מצליחות.
תשובה: `arr = {"ZA", "A", "ZZZB", "B", "ZZZZZC", "C", "ZD", "D"}`.
שאלה 12 · "זוג מתאים": ערכי קיצון בעמודות מטריצה
מערך חד-ממדי `arr` ומערך דו-ממדי `mat` נקראים "זוג מתאים" אם מתקיימים התנאים הבאים:
•מספר העמודות במערך `mat` שווה למספר התאים במערך `arr`
•כל איבר `arr[k]` הוא ערך קיצון (הכי גדול או הכי קטן) בעמודה `k` של המערך `mat`.
לדוגמה:
שני מערכים `arr` ו-`mat` הבאים הם "זוג מתאים"
arr:
mat:
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `mat`, מספר עמודה `col` וערך שלם `value`. הפעולה תבדוק אם ערך `value` הוא ערך "קיצון" (הכי גדול או הכי קטן) בעמודה `col`. אם כן – הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isExtreme (int[][] mat, int col, int value)public static bool IsExtreme (int[,] mat, int col, int value)כתבו פעולה המקבלת מערך דו-ממדי `mat` ומערך חד-ממדי `arr`. הפעולה תבדוק אם המערכים הם "זוג מתאים". אם כן – הפעולה תחזיר `true`, ולא – הפעולה תחזיר `false`.
כותרת הפעולה:
public static boolean isPair (int[][] mat, int[] arr)public static bool IsPair (int[,] mat, int[] arr)מהי הסיבוכיות של הפעולה `isPair`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 12
סעיף א
מוצאים את המקסימום ואת המינימום של עמודה `col` (לולאה על השורות) ומחזירים `value == max || value == min`.
הרעיון: `value` הוא ערך קיצון בעמודה אם הוא שווה לערך הגדול ביותר בה או לערך הקטן ביותר בה. לכן מוצאים את שניהם במעבר אחד על העמודה.
1. מאתחלים `max` ו-`min` לאיבר הראשון בעמודה, `mat[0][col]`.
2. עוברים על השורות מ- עד `mat.length - 1` ומעדכנים את `max` ואת `min` לפי `mat[row][col]`.
3. מחזירים `value == max || value == min`.
לדוגמה, בעמודה של `mat` הערכים : המקסימום והמינימום , ולכן `isExtreme(mat, 0, 4)` מחזירה `true`.
public static boolean isExtreme(int[][] mat, int col, int value)
{
int max = mat[0][col];
int min = mat[0][col];
for (int row = 1; row < mat.length; row++)
{
if (mat[row][col] > max)
max = mat[row][col];
if (mat[row][col] < min)
min = mat[row][col];
}
return value == max || value == min;
}public static bool IsExtreme(int[,] mat, int col, int value)
{
int max = mat[0, col];
int min = mat[0, col];
for (int row = 1; row < mat.GetLength(0); row++)
{
if (mat[row, col] > max)
max = mat[row, col];
if (mat[row, col] < min)
min = mat[row, col];
}
return value == max || value == min;
}תשובה: הפעולה `isExtreme` שלמעלה.
סעיף ב
אם מספר העמודות `mat[0].length` שונה מ-`arr.length` – `false`; אחרת לכל `k` בודקים `isExtreme(mat, k, arr[k])`, ואם אחד נכשל – `false`; אחרת `true`.
הרעיון: בודקים את שני התנאים של "זוג מתאים". לתנאי השני משתמשים בפעולה `isExtreme` מסעיף א', פעם אחת לכל עמודה.
1. תנאי 1: מספר העמודות במטריצה הוא אורך שורה, `mat[0].length`. אם הוא שונה מ-`arr.length` – מחזירים `false`.
2. תנאי 2: לכל `k` מ- עד `arr.length - 1`: אם `isExtreme(mat, k, arr[k])` מחזירה `false` – מחזירים `false` מיד.
3. אם כל העמודות עברו את הבדיקה – מחזירים `true`.
•עמודה : – מינימום `arr[0]`.
•עמודה : – מקסימום `arr[1]`.
•עמודה : – מקסימום `arr[2]`.
•עמודה : – מינימום `arr[3]`.
לכן הפעולה מחזירה `true`.
public static boolean isPair(int[][] mat, int[] arr)
{
if (mat[0].length != arr.length) // תנאי 1: מספר העמודות שווה לאורך arr
return false;
for (int k = 0; k < arr.length; k++) // תנאי 2: כל arr[k] קיצוני בעמודה k
if (!isExtreme(mat, k, arr[k]))
return false;
return true;
}public static bool IsPair(int[,] mat, int[] arr)
{
if (mat.GetLength(1) != arr.Length) // תנאי 1: מספר העמודות שווה לאורך arr
return false;
for (int k = 0; k < arr.Length; k++) // תנאי 2: כל arr[k] קיצוני בעמודה k
if (!IsExtreme(mat, k, arr[k]))
return false;
return true;
}תשובה: הפעולה `isPair` שלמעלה.
סעיף ג
, כאשר מספר השורות ו- מספר העמודות של `mat`.
נסמן – מספר השורות ב-`mat`, – מספר העמודות (ששווה לאורך `arr`).
1. `isExtreme` עוברת פעם אחת על כל השורות של עמודה אחת: .
2. `isPair` מזמנת את `isExtreme` פעם אחת לכל אחת מ- העמודות (במקרה הגרוע, כשהמערכים הם "זוג מתאים"): .
כלומר כל איבר של המטריצה נבדק פעם אחת.
תשובה: – לינארית במספר איברי המטריצה.
שאלה 13 · המחלקות Property ו-CityData: הנחות בארנונה
בעיריית דימונה קיימת מערכת ממוחשבת לגביית מיסוי עירוני (ארנונה). במערכת הוגדרה המחלקה `Property` (נכס) ולה התכונות הבאות:
•מספר הנכס – `num`, מטיפוס מחרוזת, `String`
•מספר תעודת הזהות של המשלם – `id`, מטיפוס מחרוזת, `String`
•כתובת הנכס – `address`, מטיפוס מחרוזת, `String`
•שטח הנכס – `area`, מטיפוס מספר ממשי, `double`
•זכאות להנחה – `discount`, מספר שלם בין 0 ל- 3, כאשר:
0 – מציין שאין הנחה, תשלום מלא,
1 – תשלום מופחת, הנחה של 10%,
2 – הנחה של 50%,
3 – פטור מלא מתשלומי ארנונה
במחלקה הוגדרו בנאים, פעולות `set/get` לכל התכונות.
במחלקה הוגדרה פעולה פנימית `double account()` המחזירה סכום חשבון מלא של ארנונה.
כתבו פעולה פנימית לחישוב סכום לתשלום בהתאם לזכאות להנחה של הנכס.
כותרת הפעולה:
public double realAccount()public double RealAccount()המחלקה `CityData` מאחסנת נתונים של כל נכסים בעיר.
למחלקה תכונה אחת – מערך `arr`, מערך הפניות לעצמים מסוג `Property`.
כתבו במחלקה `CityData` פעולה לחישוב סכום כולל של כל ההנחות בתשלומי הארנונה.
כותרת הפעולה:
public double totalDiscount()public double TotalDiscount()תושבי העיר רשאים להגיש בקשה לעדכון רמת הזכאות להנחה. מדי פעם, העירייה אוספת את כל הבקשות לעדכון ומטפלת בהן. לפי החוק העירוני, תושב העיר יכול לקבל הנחה אם מתקיימים התנאים הבאים:
•יש בבעלותו רק נכס אחד
•רמת הזכאות של נכס נמוכה מרמת הזכאות המבוקשת
כתבו פעולה במחלקה `CityData` המקבלת מערך תעודות זהות `ids` של מגישי בקשה לעדכון (הנחה), ורמת הזכאות המבוקשת `level`. הפעולה תבדוק אם יש מקום לעדכון. אם כן – הפעולה תבצע את העדכון, ולא – הפעולה תדפיס אחת משלוש הודעות:
- "תעודת הזהות אינה ברשימת משלמי ארנונה"
- "יש יותר מנכס אחד בבעלותו"
- "רמת הזכאות המבוקשת נמוכה מנוכחית"
כותרת הפעולה:
public void printDecision(String[] ids, int level)public void PrintDecision(string[] ids, int level)◂ פתרון מלא לשאלה 13
סעיף א
לפי `discount`: – `account()`; – `0.9 * account()`; – `0.5 * account()`; – .
הרעיון: הסכום לתשלום הוא הסכום המלא (`account()`) פחות ההנחה. מתרגמים כל רמת זכאות לחלק מהסכום שנשאר לתשלום:
1. שומרים את הסכום המלא `full = account()` (הפעולה הפנימית הנתונה).
2. לפי התכונה `discount` מחזירים את החלק המתאים. לדוגמה, עבור חשבון מלא של ₪ ורמה : ₪.
public double realAccount()
{
double full = account(); // סכום החשבון המלא
if (discount == 1)
return full * 0.9; // הנחה של 10%
if (discount == 2)
return full * 0.5; // הנחה של 50%
if (discount == 3)
return 0; // פטור מלא
return full; // discount == 0: תשלום מלא
}public double RealAccount()
{
double full = account(); // סכום החשבון המלא
if (discount == 1)
return full * 0.9; // הנחה של 10%
if (discount == 2)
return full * 0.5; // הנחה של 50%
if (discount == 3)
return 0; // פטור מלא
return full; // discount == 0: תשלום מלא
}תשובה: הפעולה `realAccount` שלמעלה.
סעיף ב
סכום, על כל הנכסים, של `account() - realAccount()`.
הרעיון: ההנחה של נכס אחד היא ההפרש בין הסכום המלא לסכום שמשלמים בפועל: `account() - realAccount()`. מסכמים את ההפרש הזה על כל הנכסים במערך.
1. מאתחלים צובר `total = 0`.
2. לכל נכס `arr[i]` מוסיפים ל-`total` את `arr[i].account() - arr[i].realAccount()`.
3. מחזירים את `total`.
לדוגמה, לנכס עם חשבון מלא של ₪ ורמה ההנחה היא ₪; לנכס עם חשבון מלא של ₪ ורמה ההנחה היא ₪.
public double totalDiscount()
{
double total = 0;
for (int i = 0; i < arr.length; i++)
total += arr[i].account() - arr[i].realAccount(); // ההנחה של נכס אחד
return total;
}public double TotalDiscount()
{
double total = 0;
for (int i = 0; i < arr.Length; i++)
total += arr[i].account() - arr[i].RealAccount(); // ההנחה של נכס אחד
return total;
}תשובה: הפעולה `totalDiscount` שלמעלה.
סעיף ג
לכל תעודת זהות סופרים את הנכסים הרשומים עליה: – הודעה ראשונה; יותר מ- – הודעה שנייה; נכס אחד שרמתו `>= level` – הודעה שלישית; אחרת `setDiscount(level)`.
הרעיון: מטפלים בכל בקשה (כל תעודת זהות במערך `ids`) בנפרד. לכל תעודת זהות סופרים בכמה נכסים היא מופיעה, ושומרים הפניה לנכס שנמצא; לפי התוצאה מחליטים.
1. לכל `ids[i]`: עוברים על כל הנכסים במערך `arr`, ולכל נכס שמספר תעודת הזהות שלו (`getId()`) שווה ל-`ids[i]` (השוואת מחרוזות ב-`equals`) מגדילים מונה `count` ושומרים את הנכס ב-`p`.
2. מחליטים לפי הסדר:
•`count == 0` – תעודת הזהות לא נמצאה: מדפיסים "תעודת הזהות אינה ברשימת משלמי ארנונה".
•`count > 1` – לתושב יותר מנכס אחד: מדפיסים "יש יותר מנכס אחד בבעלותו".
•נכס יחיד, אבל רמת הזכאות הנוכחית שלו אינה נמוכה מהמבוקשת (`p.getDiscount() >= level`): מדפיסים "רמת הזכאות המבוקשת נמוכה מנוכחית". (גם כאשר הרמות שוות אין מה לעדכן, כי התנאי בחוק הוא שהרמה הנוכחית נמוכה מהמבוקשת.)
•אחרת שני התנאים מתקיימים, ומעדכנים: `p.setDiscount(level)`.
public void printDecision(String[] ids, int level)
{
for (int i = 0; i < ids.length; i++)
{
int count = 0; // כמה נכסים רשומים על תעודת הזהות
Property p = null; // הנכס שנמצא
for (int j = 0; j < arr.length; j++)
if (arr[j].getId().equals(ids[i]))
{
count++;
p = arr[j];
}
if (count == 0)
System.out.println("תעודת הזהות אינה ברשימת משלמי ארנונה");
else if (count > 1)
System.out.println("יש יותר מנכס אחד בבעלותו");
else if (p.getDiscount() >= level)
System.out.println("רמת הזכאות המבוקשת נמוכה מנוכחית");
else
p.setDiscount(level); // יש מקום לעדכון
}
}public void PrintDecision(string[] ids, int level)
{
for (int i = 0; i < ids.Length; i++)
{
int count = 0; // כמה נכסים רשומים על תעודת הזהות
Property p = null; // הנכס שנמצא
for (int j = 0; j < arr.Length; j++)
if (arr[j].GetId() == ids[i])
{
count++;
p = arr[j];
}
if (count == 0)
Console.WriteLine("תעודת הזהות אינה ברשימת משלמי ארנונה");
else if (count > 1)
Console.WriteLine("יש יותר מנכס אחד בבעלותו");
else if (p.GetDiscount() >= level)
Console.WriteLine("רמת הזכאות המבוקשת נמוכה מנוכחית");
else
p.SetDiscount(level); // יש מקום לעדכון
}
}דוגמה: אם `ids = {"999", "222", "333", "111"}` ו-`level = 2`, כאשר `"999"` אינה רשומה, ל-`"222"` שני נכסים, לנכס של `"333"` רמה ולנכס של `"111"` רמה – יודפסו שלוש ההודעות לפי הסדר, ורמת הנכס של `"111"` תעודכן ל-.
תשובה: הפעולה `printDecision` שלמעלה.
שאלה 14 · רקורסיה: מספר מחלקים ובחירת איבר במערך
נתונה הפעולה הבאה המקבלת מספר שלם גדול מ- 0:
public static int secret(int n)
{
return secret(n, 1);
}
private static int secret(int n, int i)
{
if(i == n)
return 1;
if(n % i == 0) return 1 + secret(n, i + 1);
return secret(n, i+1);
}public static int Secret(int n)
{
return Secret(n, 1);
}
private static int Secret(int n, int i)
{
if(i == n)
return 1;
if(n % i == 0) return 1 + Secret(n, i + 1);
return Secret(n, i+1);
}עקבו אחרי הזימונים הבאים של הפעולה `secret` ורשמו מה תהיה התוצאה של כל זימון:
1. `secret(12)`
2. `secret(7)`
3. `secret(15)`
מה מבצעת הפעולה `secret(int n)` עבור מספר שלם גדול מ- 0?
נתונה הפעולה `sod` המקבלת מערך של מספרים שלמים גדולים מ- 0:
public static int sod(int[] arr)
{
return sod(arr, 0, arr.length-1);
}
private static int sod(int[] arr, int i, int j)
{
if(i == j) return arr[i];
if(secret(arr[i]) < secret(arr[j]))
j--;
else
i++;
return sod(arr, i, j);
}public static int Sod(int[] arr)
{
return Sod(arr, 0, arr.Length-1);
}
private static int Sod(int[] arr, int i, int j)
{
if(i == j) return arr[i];
if(Secret(arr[i]) < Secret(arr[j]))
j--;
else
i++;
return Sod(arr, i, j);
}עקבו אחרי זימון הפעולה `sod(arr)` עבור מערך הבא:
int[] arr = {4,6,12,17,24,15,10};ורשמו מה תהיה התוצאה של הזימון. יש להראות מעקב!
מה מבצעת הפעולה `sod` עבור מערך של מספרים שלמים גדולים מ-0?
◂ פתרון מלא לשאלה 14
סעיף א
`secret(12)` , `secret(7)` , `secret(15)` .
הפעולה `secret(n)` מזמנת את `secret(n, 1)`. בכל זימון: אם `i == n` מוחזר ; אחרת, אם `i` מחלק את `n` מוחזר `1 +` הזימון הבא, ואחרת – הזימון הבא בלבד. כלומר כל `i` בין ל- שמחלק את `n` מוסיף , ובסוף `i == n` מוסיף עוד .
כשהרקורסיה חוזרת מצטברים: .
התוצאה .
3. `secret(15)`: `i` מחלק את עבור (תרומה כל אחד); עבור השארית אינה (למשל , , , ) ואין תרומה; ב- העצירה מוסיפה . התוצאה .
תשובה: `secret(12)` מחזירה , `secret(7)` מחזירה , `secret(15)` מחזירה .
סעיף ב
מחזירה את מספר המחלקים של `n` (כולל ו-`n` עצמו).
הרקורסיה עוברת על כל `i` מ- עד ומוסיפה לכל `i` שמחלק את `n` ללא שארית; תנאי העצירה `i == n` מוסיף עבור `n` עצמו (שתמיד מחלק את עצמו). לכן התוצאה היא מספר המחלקים החיוביים של `n`.
בסעיף א': המחלקים של הם (שישה), של – (שניים, כי ראשוני), ושל – (ארבעה). עבור מוחזר מיד.
תשובה: הפעולה מחזירה את מספר המחלקים של `n`.
סעיף ג
הזימון מחזיר .
לפי סעיף ב', `secret(x)` היא מספר המחלקים של `x`. נחשב אותו לכל איברי המערך:
(למשל: – ; – ; ראשוני – .)
`sod(arr)` מזמנת את `sod(arr, 0, 6)`. בכל זימון: אם `secret(arr[i]) < secret(arr[j])` מקטינים את `j`, אחרת מגדילים את `i`; כש-`i == j` מוחזר `arr[i]`.
תשובה: `sod(arr)` מחזירה .
סעיף ד
מחזירה את האיבר שיש לו הכי מעט מחלקים; אם יש כמה כאלה – את האחרון מביניהם (הימני ביותר).
בכל זימון משווים את מספר המחלקים של שני הקצוות `arr[i]` ו-`arr[j]`, ו"מוותרים" על אחד מהם:
1. אם ל-`arr[i]` פחות מחלקים מאשר ל-`arr[j]` – `arr[j]` אינו המינימום, ו-`j` זז שמאלה.
2. אחרת (ל-`arr[i]` מחלקים כמו ל-`arr[j]` או יותר) – מוותרים על `arr[i]`, ו-`i` זז ימינה.
בכל זימון התחום קטן באיבר אחד, עד שנשאר איבר יחיד, והוא מוחזר.
למה נשאר דווקא האיבר עם הכי מעט מחלקים: נסמן ב- את המקום האחרון במערך שבו מספר המחלקים מינימלי. כאשר הוא הקצה הימני (`j`), לא ייתכן שלאיבר `arr[i]` פחות מחלקים ממנו, ולכן תמיד `i` זז ולא . כאשר הוא הקצה השמאלי (`i`), לכל איבר מימינו יש יותר מחלקים ממש (כי הוא המינימום האחרון), ולכן תמיד `j` זז. מכאן ש- לעולם לא מוצא מהתחום, והוא האיבר שמוחזר.
בסעיף ג' האיבר (מספר ראשוני, מחלקים) הוא היחיד עם מספר מחלקים מינימלי, והוא שהוחזר.
תשובה: הפעולה מחזירה את האיבר במערך שמספר המחלקים שלו הוא הקטן ביותר (ואם יש כמה כאלה – את האחרון מביניהם).