דילוג לתוכן המרכזי

מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2026 מועד א'

הנדסת תוכנה · סמל 97104 · 10 שאלות · פתרון מלא לכל סעיף

מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2026 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.

הנחיות הבחינה

משך הבחינה: ארבע שעות וחצי.

מבנה השאלון: בשאלון זה שני מבחנים. עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:

מבחן ב-C# (עמוד 2)

מבחן ב-Java (עמוד 12)

בכל מבחן 10 שאלות.

חלק א' – 36 נקודות

שאלות 1–4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה – 12 נקודות.

חלק ב' – 30 נקודות

שאלות 5–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.

חלק ג' – 34 נקודות

שאלות 8–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 17 נקודות.

בסך הכול: 100 נקודות.

חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).

2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.

אין לצרף ספרים או חוברות עם פתרונות.

מילון עזר.

שאלה 1 · מחרוזת ייחודית: בדיקת תווים כפולים

מחרוזת נקראת "מחרוזת ייחודית" אם כל תו המופיע בה מופיע פעם אחת בלבד (כלומר, אין בה תווים כפולים).

לדוגמה:

•המחרוזת `"abc12!"` היא מחרוזת ייחודית;

•המחרוזת `"aA12"` היא מחרוזת ייחודית (האות `'a'` שונה מ-`'A'`);

•המחרוזת `"apple1"` אינה ייחודית (התו `'p'` מופיע פעמיים);

•המחרוזת `"121"` אינה ייחודית (התו `'1'` מופיע פעמיים).

א.

כתבו פעולה המקבלת מחרוזת ובודקת אם היא "ייחודית". אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.

(8 נקודות)
ב.

כתבו קטע קוד הקולט סדרת מחרוזות עד אשר נקלטת מחרוזת המתחילה באות `'R'`. בסיום יש להדפיס כמה מחרוזות מתוך המחרוזות שנקלטו (לא כולל מחרוזת הסיום) היו "מחרוזות ייחודיות".

(4 נקודות)
◂ פתרון מלא לשאלה 1

סעיף א

תשובה:

פעולה עם שתי לולאות מקוננות שמשווה כל זוג תווים (`i < j`); אם נמצא זוג שווה מוחזר `false`, ואחרת `true`.

הרעיון: מחרוזת אינה ייחודית אם ורק אם יש בה שני מקומות שונים i<ji<j שבהם אותו תו. לכן משווים כל תו לכל התווים שאחריו:

1. הלולאה החיצונית בוחרת תו במקום `i` (מ-00 עד האורך פחות 22).

2. הלולאה הפנימית עוברת על כל המקומות `j` שאחרי `i` ומשווה את התווים.

3. ברגע שנמצאו שני תווים שווים – המחרוזת אינה ייחודית, ומחזירים `false` מיד.

4. אם הלולאות הסתיימו בלי למצוא זוג שווה – כל תו מופיע פעם אחת, ומחזירים `true`.

ההשוואה בין תווים מבחינה בין אות גדולה לקטנה (`'a'` שונה מ-`'A'`), בדיוק כנדרש. מחרוזת ריקה או בת תו אחד היא ייחודית (אין בה זוג תווים). סיבוכיות: O(n2)O(n^2) עבור מחרוזת באורך nn.

C#:

public static bool IsUnique(string s)
{
    for (int i = 0; i < s.Length - 1; i++)
    {
        for (int j = i + 1; j < s.Length; j++)
        {
            if (s[i] == s[j])
                return false;   // נמצא תו שמופיע פעמיים
        }
    }
    return true;
}

Java:

public static boolean isUnique(String s)
{
    for (int i = 0; i < s.length() - 1; i++)
    {
        for (int j = i + 1; j < s.length(); j++)
        {
            if (s.charAt(i) == s.charAt(j))
                return false;   // נמצא תו שמופיע פעמיים
        }
    }
    return true;
}

בדיקה בדוגמאות: `"abc12!"` ו-`"aA12"` – אין זוג תווים שווים, מוחזר `true`; ב-`"apple1"` נמצא `s[1] == s[2]` (`'p'`), מוחזר `false`; ב-`"121"` נמצא `s[0] == s[2]` (`'1'`), מוחזר `false`.

תשובה: הפעולה `IsUnique` (ב-Java: `isUnique`) שלמעלה.

סעיף ב

תשובה:

לולאת `while` עם קליטה לפני הלולאה ובסוף כל סיבוב; כל עוד התו הראשון אינו `'R'` – אם המחרוזת ייחודית (סעיף א) מגדילים מונה; בסוף מדפיסים את המונה.

הרעיון: מחרוזת הסיום אינה נספרת, לכן צריך לבדוק את תנאי העצירה לפני שבודקים את המחרוזת. מתאימה לולאת `while` עם "קליטה מקדימה":

1. מאתחלים מונה `count = 0` וקולטים את המחרוזת הראשונה.

2. כל עוד התו הראשון של המחרוזת (מקום 00) אינו `'R'`, המחרוזת היא חלק מהנתונים: בודקים אותה בעזרת הפעולה מסעיף א, ואם היא ייחודית – מגדילים את `count`.

3. בסוף כל סיבוב קולטים את המחרוזת הבאה, והתנאי נבדק שוב.

4. כשנקלטת מחרוזת שמתחילה ב-`'R'` הלולאה מסתיימת בלי לבדוק אותה, ומדפיסים את `count`.

(מניחים שכל מחרוזת שנקלטת אינה ריקה, כך שיש לה תו במקום 00.)

C#:

int count = 0;
string str = Console.ReadLine();
while (str[0] != 'R')
{
    if (IsUnique(str))
        count++;
    str = Console.ReadLine();
}
Console.WriteLine(count);

Java:

int count = 0;
String str = in.next();
while (str.charAt(0) != 'R')
{
    if (isUnique(str))
        count++;
    str = in.next();
}
System.out.println(count);

דוגמה: עבור הקלט `abc`, `apple`, `aA12`, `121`, `xyz`, `Rest` – המחרוזות הייחודיות הן `abc`, `aA12`, `xyz`, ומחרוזת הסיום `Rest` אינה נבדקת. יודפס `3`.

תשובה: קטע הקוד שלמעלה.

שאלה 2 · ספרה מובילה ושלשות סמוכות במערך

א.

"ספרה מובילה" של מספר שלם חיובי היא הספרה השמאלית ביותר שלו.

לדוגמה: הספרה המובילה של 452 היא 4, הספרה המובילה של 19 היא 1, הספרה המובילה של 9 היא 9.

כתבו פעולה המקבלת מספר שלם חיובי ומחזירה את הספרה המובילה שלו.

(5 נקודות)
ב.

רצף של שלושה מספרים סמוכים במערך ייקרא "שלשת ראש זהה" אם בכל שלושת המספרים ברצף הספרה המובילה זהה.

לדוגמה:

במערך `int[] a = {58, 612, 61, 6929, 13, 12, 21, 22, 239}`

יש שתי "שלשות ראש זהה".

כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים ומחזירה את כמות "שלשות ראש זהה".

יש להשתמש בפעולה שכתבתם בסעיף א'

(7 נקודות)
◂ פתרון מלא לשאלה 2

סעיף א

תשובה:

מחלקים את המספר ב-10 (חלוקה בשלמים) כל עוד הוא לפחות 10; מה שנשאר הוא הספרה המובילה.

הרעיון: חלוקה בשלמים ב-1010 מוחקת את ספרת האחדות. אם נמחק שוב ושוב את הספרה הימנית, בסוף תישאר רק הספרה השמאלית ביותר.

1. כל עוד `num >= 10` (יש במספר לפחות שתי ספרות) – מבצעים `num = num / 10`.

2. כשהלולאה נגמרת, `num` הוא מספר חד-ספרתי – זו הספרה המובילה, ומחזירים אותו.

דוגמה: 452→45→4452 \to 45 \to 4, מוחזר 44. עבור 1919: 19→119 \to 1. עבור 99 הלולאה לא מתבצעת כלל ומוחזר 99. סיבוכיות: O(d)O(d), כאשר dd מספר הספרות.

C#:

public static int LeadingDigit(int num)
{
    while (num >= 10)       // כל עוד יש יותר מספרה אחת
        num = num / 10;     // מוחקים את ספרת האחדות
    return num;
}

Java:

public static int leadingDigit(int num)
{
    while (num >= 10)       // כל עוד יש יותר מספרה אחת
        num = num / 10;     // מוחקים את ספרת האחדות
    return num;
}

תשובה: הפעולה `LeadingDigit` (ב-Java: `leadingDigit`) שלמעלה.

סעיף ב

תשובה:

עוברים על כל מקום התחלה `i` מ-0 עד `Length-3`, ואם לשלושת האיברים `arr[i]`, `arr[i+1]`, `arr[i+2]` אותה ספרה מובילה (לפי סעיף א) מגדילים מונה; מחזירים את המונה.

הרעיון: כל "שלשת ראש זהה" נקבעת לפי המקום `i` של האיבר הראשון שלה: האיברים `arr[i]`, `arr[i+1]`, `arr[i+2]`. לכן עוברים על כל מקומות ההתחלה האפשריים ובודקים כל שלשה:

1. מקום ההתחלה האחרון האפשרי הוא `Length - 3` (כדי ש-`i+2` יהיה בתוך המערך), ולכן הלולאה רצה כל עוד `i < Length - 2`.

2. מחשבים בעזרת הפעולה מסעיף א את הספרה המובילה `d` של `arr[i]`, ובודקים שגם ל-`arr[i+1]` ול-`arr[i+2]` ספרה מובילה `d`.

3. אם כן – מגדילים את המונה. בסוף מחזירים אותו.

שלשות יכולות לחפוף: למשל ב-`{1, 12, 13, 145}` יש שתי שלשות (מהמקומות 00 ו-11). במערך עם פחות משלושה איברים הלולאה לא מתבצעת ומוחזר 00.

בדיקה בדוגמה: הספרות המובילות של `a` הן 5,6,6,6,1,1,2,2,25, 6, 6, 6, 1, 1, 2, 2, 2. השלשות המתאימות מתחילות במקום 11 (`612, 61, 6929`) ובמקום 66 (`21, 22, 239`), ולכן מוחזר 22.

C#:

public static int CountSameHead(int[] arr)
{
    int count = 0;
    for (int i = 0; i < arr.Length - 2; i++)
    {
        int d = LeadingDigit(arr[i]);
        if (LeadingDigit(arr[i + 1]) == d && LeadingDigit(arr[i + 2]) == d)
            count++;        // arr[i], arr[i+1], arr[i+2] - שלשת ראש זהה
    }
    return count;
}

Java:

public static int countSameHead(int[] arr)
{
    int count = 0;
    for (int i = 0; i < arr.length - 2; i++)
    {
        int d = leadingDigit(arr[i]);
        if (leadingDigit(arr[i + 1]) == d && leadingDigit(arr[i + 2]) == d)
            count++;        // arr[i], arr[i+1], arr[i+2] - שלשת ראש זהה
    }
    return count;
}

תשובה: הפעולה `CountSameHead` (ב-Java: `countSameHead`) שלמעלה; עבור המערך שבדוגמה היא מחזירה 22.

שאלה 3 · מעקב: סימנים מתחלפים בין איברים סמוכים

נתונה פעולה הבאה:

C#:

public static bool Secret(int[] arr) {
    int right = arr.Length - 1;
    int left = right - 1;
    int count = 0;

    while (left >= 0) {
        if (arr[left] * arr[right] < 0) {
            count++;
        }
        right--;
        left--;
    }
    if (count == arr.Length - 1) {
        return true;
    }
    return false;
}

Java:

public static boolean secret(int[] arr) {
    int right = arr.length - 1;
    int left = right - 1;
    int count = 0;

    while (left >= 0) {
        if (arr[left] * arr[right] < 0) {
            count++;
        }
        right--;
        left--;
    }
    if (count == arr.length - 1) {
        return true;
    }
    return false;
}
א.

נתון המערך `int[] arr={1, -5, 2, -8, 4, 10, -3}`

(1)

עקבו בעזרת טבלת מעקב אחר הזימון `Secret (arr)`, ורשמו מה תחזיר הפעולה.

(2)

האם אפשר לשנות את סדר האיברים במערך `arr` כך שזימון `Secret(arr)` יחזיר תוצאה שונה מהתוצאה שהתקבלה בסעיף א1? הסבירו את תשובתכם.

(6 נקודות)
ב.

מה מבצעת הפעולה `Secret` באופן כללי?

(3 נקודות)
ג.

נתונה טענה הבאה: אם הפעולה `Secret` החזירה `true` עבור מערך מסוים, הרי שבהכרח אין במערך זה את המספר 0.

קבעו אם הטענה הבאה נכונה או לא נכונה, ונמקו את קביעתכם.

(3 נקודות)
◂ פתרון מלא לשאלה 3

סעיף א

(1)
תשובה:

`count = 5`, ו-`arr.Length - 1 = 6`, ולכן הפעולה מחזירה `false`.

בהתחלה: `right = 7 - 1 = 6`, `left = 5`, `count = 0`. בכל סיבוב בודקים את זוג האיברים הסמוכים `arr[left]`, `arr[right]`, וזזים זוג אחד שמאלה. הלולאה נעצרת כש-`left` נעשה −1-1.

סיבובleftrightarr[left]arr[right]מכפלהמכפלה < 0?count
15610-3-30כן1
24541040לא1
334-84-32כן2
4232-8-16כן3
512-52-10כן4
6011-5-5כן5

אחרי הסיבוב השישי `left = -1` והלולאה מסתיימת. בודקים: `count == arr.Length - 1`, כלומר 5=65 = 6? לא. לכן מוחזר `false` (הזוג 4,104, 10 – שני חיוביים – "שובר" את התחלופה).

תשובה: הפעולה מחזירה `false`.

(2)
תשובה:

כן. למשל `{1, -5, 2, -8, 4, -3, 10}` – כל זוג סמוך בסימנים הפוכים, `count = 6`, ומוחזר `true`.

הפעולה מחזירה `true` רק אם כל זוגות האיברים הסמוכים הם בעלי סימנים הפוכים, כלומר החיוביים והשליליים מתחלפים לסירוגין.

1. במערך יש 44 מספרים חיוביים (1,2,4,101, 2, 4, 10) ו-33 שליליים (−5,−8,−3-5, -8, -3), ואין אפסים.

2. כדי לסדר 77 איברים לסירוגין צריך 44 מסוג אחד ו-33 מהסוג השני, כשהסוג הגדול בקצוות: חיובי, שלילי, חיובי, שלילי, חיובי, שלילי, חיובי. זה בדיוק המצב כאן.

3. לדוגמה: `{1, -5, 2, -8, 4, -3, 10}`. ששת הזוגות הסמוכים: (1,−5)(1,-5), (−5,2)(-5,2), (2,−8)(2,-8), (−8,4)(-8,4), (4,−3)(4,-3), (−3,10)(-3,10) – בכולם המכפלה שלילית, ולכן `count = 6 = arr.Length - 1` ומוחזר `true`.

תשובה: כן. בסידור `{1, -5, 2, -8, 4, -3, 10}` הפעולה תחזיר `true` (שונה מ-`false` שהתקבל בסעיף א1).

סעיף ב

תשובה:

מחזירה `true` אם כל שני איברים סמוכים במערך הם בעלי סימנים הפוכים (חיובי ושלילי לסירוגין, בלי אפסים), ואחרת `false`.

1. המשתנים `left` ו-`right` מצביעים תמיד על שני איברים סמוכים (`left = right - 1`), והלולאה עוברת על כל n−1n-1 הזוגות הסמוכים במערך, מהסוף להתחלה.

2. המכפלה `arr[left] * arr[right]` שלילית אם ורק אם לאחד האיברים סימן חיובי ולשני שלילי (אם אחד מהם 00 המכפלה 00, ואינה שלילית).

3. `count` סופר כמה זוגות סמוכים הם בעלי סימנים הפוכים, ובסוף בודקים אם כל n−1n-1 הזוגות כאלה.

תשובה: הפעולה בודקת אם סימני האיברים במערך מתחלפים – כל איבר חיובי צמוד רק לשליליים ולהפך (ואין אפסים). אם כן היא מחזירה `true`, אחרת `false`.

סעיף ג

תשובה:

עבור מערך עם שני איברים לפחות הטענה נכונה (זוג שיש בו 0 נותן מכפלה 0, לא שלילית). אבל באופן מוחלט היא אינה נכונה: עבור המערך `{0}` מוחזר `true` (`count = 0 = Length - 1`).

1. מערך עם שני איברים או יותר: נניח שיש במערך 00 במקום כלשהו. ל-00 יש לפחות שכן אחד, ובזוג הזה המכפלה היא 00, שאינה קטנה מ-00. לכן הזוג הזה לא נספר, `count` קטן מ-n−1n-1, והפעולה מחזירה `false`. כלומר, אם הוחזר `true` – אין במערך 00. במקרה הזה הטענה נכונה.

2. מערך עם איבר אחד: `right = 0`, `left = -1`, והלולאה לא מתבצעת כלל. אז `count = 0` וגם `arr.Length - 1 = 0`, ולכן מוחזר `true` – בלי קשר לערך האיבר. עבור `{0}` הפעולה מחזירה `true` למרות שיש במערך 00.

לכן הטענה, כפי שהיא מנוסחת ("בהכרח"), אינה נכונה: המערך `{0}` הוא דוגמה נגדית. היא נכונה רק למערכים בני שני איברים לפחות.

תשובה: הטענה אינה נכונה באופן כללי – דוגמה נגדית: `Secret({0})` מחזירה `true`. עבור מערכים בני שני איברים או יותר הטענה נכונה, כי זוג סמוך שיש בו 00 נותן מכפלה 00 ואינו נספר.

שאלה 4 · מחלקת טיסה: סכום נוסעים וטיסות מתאימות

נתונה המחלקה `Flight` המייצגת טיסה. למחלקה כמה תכונות:

•מספר הטיסה – `int flightNum`;

•יעד הטיסה – `string destination`; (ב-Java: `String destination`)

•מספר הנוסעים הרשומים לטיסה – `int passengers`;

•קיבולת המטוס (מספר המקומות הכולל במטוס) – `int capacity`;

אפשר להניח כי במחלקה `Flight` קיימות כל הפעולות `Get`, `Set`.

א.

כתבו פעולה חיצונית המקבלת מערך של טיסות `flights` (מערך של עצמים מסוג `Flight`) ושם של יעד `dest`. הפעולה תחזיר את מספר הנוסעים הכולל הרשומים לכל הטיסות ש-`dest` הוא היעד שלהן.

(6 נקודות)
ב.

קבוצת תיירים המונה `num` אנשים מעוניינת לטוס ליעד `dest`. טיסה נחשבת "מתאימה" לקבוצה אם היעד שלה הוא היעד המבוקש, ויש בה מספיק מקומות פנויים לכל חברי הקבוצה.

כתבו פעולה חיצונית המקבלת מערך של טיסות, שם יעד ומספר תיירים. הפעולה תדפיס את מספרי הטיסות המתאימות לקבוצה.

(6 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

עוברים על המערך, ולכל טיסה שהיעד שלה שווה ל-`dest` מוסיפים לסכום את מספר הנוסעים שלה; מחזירים את הסכום.

הרעיון: סכימה מותנית – עוברים על כל הטיסות ומצרפים לסכום רק את הטיסות ליעד המבוקש.

1. מאתחלים `sum = 0`.

2. לכל טיסה במערך משווים את היעד שלה (בעזרת `GetDestination`) ל-`dest`. ב-C# משווים מחרוזות עם `==`, וב-Java עם `equals` (האופרטור `==` ב-Java משווה הפניות ולא תוכן).

3. אם היעד מתאים – מוסיפים ל-`sum` את מספר הנוסעים (`GetPassengers`).

4. בסוף מחזירים את `sum` (אם אין אף טיסה ליעד – מוחזר 00).

הפעולה חיצונית, ולכן ניגשים לתכונות רק דרך פעולות ה-`Get`. סיבוכיות: O(n)O(n).

C#:

public static int TotalPassengers(Flight[] flights, string dest)
{
    int sum = 0;
    for (int i = 0; i < flights.Length; i++)
    {
        if (flights[i].GetDestination() == dest)
            sum += flights[i].GetPassengers();
    }
    return sum;
}

Java:

public static int totalPassengers(Flight[] flights, String dest)
{
    int sum = 0;
    for (int i = 0; i < flights.length; i++)
    {
        if (flights[i].getDestination().equals(dest))
            sum += flights[i].getPassengers();
    }
    return sum;
}

דוגמה: טיסות 101101 (Rome, 150150 נוסעים), 102102 (Paris, 100100), 103103 (Rome, 175175), 104104 (Rome, 9090). עבור `"Rome"` מוחזר 150+175+90=415150+175+90=415.

תשובה: הפעולה `TotalPassengers` (ב-Java: `totalPassengers`) שלמעלה.

סעיף ב

תשובה:

לכל טיסה מחשבים מקומות פנויים `capacity - passengers`; אם היעד שווה ל-`dest` ומספר המקומות הפנויים לפחות `num` – מדפיסים את מספר הטיסה.

הרעיון: מספר המקומות הפנויים בטיסה הוא הקיבולת פחות מספר הנוסעים הרשומים. טיסה מתאימה אם מתקיימים שני התנאים יחד:

1. היעד שלה שווה ל-`dest`;

2. מספר המקומות הפנויים גדול או שווה ל-`num` (כל חברי הקבוצה נכנסים).

עוברים על כל הטיסות, ולכל טיסה שעומדת בשני התנאים מדפיסים את מספר הטיסה (`GetFlightNum`). סיבוכיות: O(n)O(n).

C#:

public static void PrintSuitable(Flight[] flights, string dest, int num)
{
    for (int i = 0; i < flights.Length; i++)
    {
        int free = flights[i].GetCapacity() - flights[i].GetPassengers();   // מקומות פנויים
        if (flights[i].GetDestination() == dest && free >= num)
            Console.WriteLine(flights[i].GetFlightNum());
    }
}

Java:

public static void printSuitable(Flight[] flights, String dest, int num)
{
    for (int i = 0; i < flights.length; i++)
    {
        int free = flights[i].getCapacity() - flights[i].getPassengers();   // מקומות פנויים
        if (flights[i].getDestination().equals(dest) && free >= num)
            System.out.println(flights[i].getFlightNum());
    }
}

דוגמה: עם הטיסות מסעיף א (קיבולות 180180, 120120, 180180, 200200), קבוצה של 3030 ל-`"Rome"`: בטיסה 101101 פנויים 180−150=30180-150=30 – מתאימה; בטיסה 103103 פנויים 180−175=5180-175=5 – לא; בטיסה 104104 פנויים 200−90=110200-90=110 – מתאימה. יודפסו 101101 ו-104104.

תשובה: הפעולה `PrintSuitable` (ב-Java: `printSuitable`) שלמעלה.

שאלה 5 · איברים פורצים במערך

נגדיר מספר במערך כ"איבר פורץ" אם הוא גדול ממש מכל האיברים המופיעים לפניו (משמאלו) במערך.

הערה: האיבר הראשון במערך (באינדקס 0) נחשב תמיד ל"איבר פורץ".

לדוגמה: עבור המערך `int[] arr = {7, 2, 9, 9, 15, 3}` האיברים הפורצים הם 7, 9, 15

כי 7 הוא הראשון, 9 גדול מ-7 ומ-2, 15 גדול מכל קודמיו.

א.

כתבו פעולה בשם `IsBreakthrough` המקבלת מערך של מספרים שלמים `arr` ואינדקס `k`.

הפעולה תחזיר `true` אם האיבר במיקום `k` הוא "איבר פורץ", ואם לא – הפעולה תחזיר `false`.

(5 נקודות)
ב.

כתבו פעולה בשם `AllBreakthroughs` המקבלת מערך של מספרים שלמים ומחזירה מערך חדש המכיל את כל האיברים הפורצים מתוך המערך המקורי, לפי סדר הופעתם.

יש להשתמש בפעולה שכתבתם בסעיף א'.

(6 נקודות)
ג.

נתון מערך `arr` בגודל `n`.

(1)

מהו האורך המינימלי האפשרי של המערך המוחזר מסעיף ב'? תנו דוגמה למערך קלט בגודל `n=4` שיקיים זאת.

(2)

מהו האורך המקסימלי האפשרי של המערך המוחזר מסעיף ב'? תנו דוגמה למערך קלט בגודל `n=4` שיקיים זאת.

(4 נקודות)
◂ פתרון מלא לשאלה 5

סעיף א

תשובה:

עוברים על המקומות `0` עד `k-1`; אם יש איבר `>= arr[k]` מחזירים `false`, אחרת `true` (עבור `k = 0` הלולאה ריקה ומוחזר `true`).

הרעיון: `arr[k]` הוא איבר פורץ אם הוא גדול ממש מכל האיברים שלפניו. מספיק שיהיה לפניו איבר אחד גדול ממנו או שווה לו כדי שלא יהיה פורץ.

1. עוברים על המקומות `i` מ-00 עד `k-1`.

2. אם `arr[i] >= arr[k]` – מחזירים `false` מיד.

3. אם לא נמצא איבר כזה – מחזירים `true`.

עבור `k = 0` הלולאה לא מתבצעת ומוחזר `true`, בהתאם להערה שהאיבר הראשון תמיד פורץ. סיבוכיות: O(k)O(k).

בדוגמה: עבור `k = 3` (`arr[3] = 9`) נמצא `arr[2] = 9 >= 9`, ולכן מוחזר `false` – ה-9 השני אינו פורץ.

C#:

public static bool IsBreakthrough(int[] arr, int k)
{
    for (int i = 0; i < k; i++)
    {
        if (arr[i] >= arr[k])
            return false;   // יש לפניו איבר גדול ממנו או שווה לו
    }
    return true;
}

Java:

public static boolean isBreakthrough(int[] arr, int k)
{
    for (int i = 0; i < k; i++)
    {
        if (arr[i] >= arr[k])
            return false;   // יש לפניו איבר גדול ממנו או שווה לו
    }
    return true;
}

תשובה: הפעולה `IsBreakthrough` (ב-Java: `isBreakthrough`) שלמעלה.

סעיף ב

תשובה:

מעבר ראשון סופר בעזרת `IsBreakthrough` כמה איברים פורצים יש; יוצרים מערך בגודל הזה; מעבר שני מעתיק אליו את האיברים הפורצים לפי הסדר.

הרעיון: את גודל המערך החדש צריך לדעת לפני שיוצרים אותו, לכן עובדים בשני מעברים:

1. מעבר ראשון – ספירה: לכל מקום `k` בודקים בעזרת `IsBreakthrough(arr, k)` אם האיבר פורץ, וסופרים ב-`count`.

2. יוצרים מערך `result` בגודל `count` בדיוק.

3. מעבר שני – מילוי: עוברים שוב על המקומות לפי הסדר; כל איבר פורץ מועתק למקום `j` במערך החדש, ו-`j` גדל ב-11. כך נשמר סדר ההופעה.

4. מחזירים את `result`.

סיבוכיות: כל זימון של `IsBreakthrough` עולה O(k)O(k), ולכן סך הכול O(n2)O(n^2).

C#:

public static int[] AllBreakthroughs(int[] arr)
{
    // מעבר ראשון: כמה איברים פורצים יש?
    int count = 0;
    for (int k = 0; k < arr.Length; k++)
    {
        if (IsBreakthrough(arr, k))
            count++;
    }
    // מעבר שני: העתקת האיברים הפורצים לפי הסדר
    int[] result = new int[count];
    int j = 0;
    for (int k = 0; k < arr.Length; k++)
    {
        if (IsBreakthrough(arr, k))
        {
            result[j] = arr[k];
            j++;
        }
    }
    return result;
}

Java:

public static int[] allBreakthroughs(int[] arr)
{
    // מעבר ראשון: כמה איברים פורצים יש?
    int count = 0;
    for (int k = 0; k < arr.length; k++)
    {
        if (isBreakthrough(arr, k))
            count++;
    }
    // מעבר שני: העתקת האיברים הפורצים לפי הסדר
    int[] result = new int[count];
    int j = 0;
    for (int k = 0; k < arr.length; k++)
    {
        if (isBreakthrough(arr, k))
        {
            result[j] = arr[k];
            j++;
        }
    }
    return result;
}

בדוגמה: עבור `{7, 2, 9, 9, 15, 3}` נספרים 33 איברים פורצים (במקומות 00, 22, 44), ומוחזר `{7, 9, 15}`.

תשובה: הפעולה `AllBreakthroughs` (ב-Java: `allBreakthroughs`) שלמעלה.

סעיף ג

(1)
תשובה:

האורך המינימלי הוא 1. דוגמה: `{9, 5, 3, 1}` (מוחזר `{9}`).

1. האיבר הראשון (מקום 00) הוא תמיד איבר פורץ, ולכן במערך המוחזר יש לפחות איבר אחד (עבור n≥1n \ge 1).

2. אפשר להגיע בדיוק ל-11: אם האיבר הראשון הוא הגדול ביותר או שווה לכל השאר, אף איבר אחר אינו גדול ממנו ממש, ולכן אף איבר אחר אינו פורץ.

3. דוגמה עם n=4n=4: `{9, 5, 3, 1}` (סדר יורד) – מוחזר `{9}`. גם `{4, 4, 4, 4}` מתאים, כי "גדול ממש" אינו מתקיים בשוויון.

תשובה: האורך המינימלי הוא 11; למשל `{9, 5, 3, 1}`.

(2)
תשובה:

האורך המקסימלי הוא `n`. דוגמה: `{1, 2, 3, 4}` (מוחזר `{1, 2, 3, 4}`).

1. המערך המוחזר מכיל רק איברים מתוך המערך המקורי, ולכן אורכו לכל היותר nn.

2. האורך הוא nn כאשר כל איבר פורץ, כלומר כל איבר גדול ממש מכל קודמיו – המערך ממוין בסדר עולה ממש.

3. דוגמה עם n=4n=4: `{1, 2, 3, 4}` – כל איבר גדול מכל מה שלפניו, ומוחזר `{1, 2, 3, 4}` באורך 44.

תשובה: האורך המקסימלי הוא nn; למשל `{1, 2, 3, 4}`.

שאלה 6 · מחלקות תרומה ופרויקט: בנאי, סכום ומקסימום

לפניכם הגדרות של שתי מחלקות המייצגות מערכת לניהול פרויקטים של תרומות:

המחלקה `Donation` מייצגת תרומה בודדת ולה התכונות האלה:

•שם התורם – `string donorName`; (ב-Java: `String donorName`)

•סכום התרומה – `double amount`;

•סוג התרומה – `char type` (`'F'` עבור מזון, `'C'` עבור ביגוד, `'M'` עבור כסף).

המחלקה `CharityProject` מייצגת פרויקט צדקה. למחלקה התכונות האלה:

•מספר זיהוי של הפרויקט – `int projectID`;

•שם היישוב שבו נערך הפרויקט – `string location`; (ב-Java: `String location`)

•מערך תרומות `Donation[] donations`. המערך תמיד מלא באובייקטים מסוג `Donation` ואין בו תאי `null`.

בשתי המחלקות הוגדרו בנאים ופעולות `Get/Set` עבור כל התכונות.

א.

כתבו בנאי (`Constructor`) למחלקה `Donation` המקבל ערכים עבור כל תכונותיה. הבנאי יבדוק את תקינות הפרמטרים:

•סכום התרומה (`amount`) חייב להיות חיובי ממש. אם לא, ייקבע ערך ברירת מחדל של 10.

•סוג התרומה (`type`) חייב להיות אחד מהתווים `'F'`, `'C'` או `'M'`. אם לא, ייקבע ערך ברירת מחדל של `'M'`.

(3 נקודות)
ב.

כתבו במחלקה `CharityProject` פעולה פנימית בשם `GetTypeTotal` המקבלת תו המייצג סוג תרומה. הפעולה תחזיר את הסכום הכולל של כל התרומות מסוג זה הקיימות במערך התרומות של הפרויקט.

(6 נקודות)
ג.

כתבו פעולה חיצונית המקבלת מערך של פרויקטים (אובייקטים מסוג `CharityProject`) ותו המייצג סוג תרומה. הפעולה תדפיס את שם היישוב (`location`) של הפרויקט שבו נאסף סכום הכסף הגבוה ביותר עבור סוג התרומה שהתקבל.

הנחה: כל יישוב מופיע במערך הפרויקטים פעם אחת לכל היותר.

(6 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

בנאי שמציב את שם התורם; את `amount` מציב רק אם הוא גדול מ-0 (אחרת 10); את `type` מציב רק אם הוא `'F'`, `'C'` או `'M'` (אחרת `'M'`).

הרעיון: הבנאי מקבל שלושה פרמטרים, אחד לכל תכונה, ומציב כל אחד בתכונה המתאימה – אבל רק אחרי בדיקת תקינות:

1. שם התורם מוצב כמו שהוא (אין עליו דרישה).

2. סכום: אם `amount > 0` מציבים אותו; אחרת (אפס או שלילי) מציבים 1010.

3. סוג: אם התו שווה לאחד משלושת התווים המותרים מציבים אותו; אחרת מציבים `'M'`.

המילה `this` מבחינה בין התכונה של העצם לבין הפרמטר שיש לו אותו שם.

C#:

public Donation(string donorName, double amount, char type)
{
    this.donorName = donorName;
    if (amount > 0)
        this.amount = amount;
    else
        this.amount = 10;      // ערך ברירת מחדל
    if (type == 'F' || type == 'C' || type == 'M')
        this.type = type;
    else
        this.type = 'M';       // ערך ברירת מחדל
}

Java:

public Donation(String donorName, double amount, char type)
{
    this.donorName = donorName;
    if (amount > 0)
        this.amount = amount;
    else
        this.amount = 10;      // ערך ברירת מחדל
    if (type == 'F' || type == 'C' || type == 'M')
        this.type = type;
    else
        this.type = 'M';       // ערך ברירת מחדל
}

דוגמה: `new Donation("Dana", -3, 'Z')` יוצר תרומה עם סכום 1010 וסוג `'M'`.

תשובה: הבנאי שלמעלה.

סעיף ב

תשובה:

עוברים על מערך `donations`, ולכל תרומה שהסוג שלה שווה לתו שהתקבל מוסיפים את סכומה; מחזירים את הסכום (`double`).

הרעיון: הפעולה פנימית, ולכן יש לה גישה ישירה למערך `donations` של הפרויקט. עבור התרומות (עצמים מסוג `Donation`) ניגשים לתכונות דרך פעולות ה-`Get`.

1. מאתחלים `sum = 0` (מסוג `double`, כי הסכומים ממשיים).

2. עוברים על כל התרומות במערך (המערך מלא ואין בו `null`, ולכן אין צורך לבדוק זאת).

3. אם סוג התרומה (`GetType`) שווה לתו שהתקבל – מוסיפים ל-`sum` את סכום התרומה (`GetAmount`).

4. מחזירים את `sum`. סיבוכיות: O(d)O(d) עבור dd תרומות.

C#:

public double GetTypeTotal(char type)
{
    double sum = 0;
    for (int i = 0; i < donations.Length; i++)
    {
        if (donations[i].GetType() == type)
            sum += donations[i].GetAmount();
    }
    return sum;
}

Java:

public double getTypeTotal(char type)
{
    double sum = 0;
    for (int i = 0; i < donations.length; i++)
    {
        if (donations[i].getType() == type)
            sum += donations[i].getAmount();
    }
    return sum;
}

הערה ל-C#: למחלקה `object` כבר יש פעולה בשם `GetType()`; לפי השאלה הגטר של התכונה `type` נקרא כך. אם רוצים להימנע מהתנגשות, אפשר לקרוא לגטר `GetDonationType()` ולהשתמש בו באותו אופן.

דוגמה: בפרויקט עם התרומות: 100100 מסוג `'M'`, 5050 מסוג `'F'` ו-3030 מסוג `'M'`, הזימון `GetTypeTotal('M')` מחזיר 100+30=130100+30=130.

תשובה: הפעולה `GetTypeTotal` (ב-Java: `getTypeTotal`) שלמעלה.

סעיף ג

תשובה:

חיפוש מקסימום: לכל פרויקט מחשבים `GetTypeTotal(type)` (סעיף ב), שומרים את מקום הפרויקט עם הסכום הגבוה ביותר, ובסוף מדפיסים את `GetLocation()` שלו.

הרעיון: זהו חיפוש מקסימום רגיל, כשהערך שמשווים לכל פרויקט הוא הסכום שנאסף בו עבור הסוג המבוקש – ואותו כבר יודעים לחשב בעזרת `GetTypeTotal` מסעיף ב.

1. אם המערך ריק – אין מה להדפיס, ויוצאים.

2. מתחילים מהפרויקט הראשון: `best = 0`, ו-`maxSum` הוא הסכום שלו.

3. עוברים על שאר הפרויקטים. לכל פרויקט מחשבים את הסכום עבור הסוג; אם הוא גדול מ-`maxSum` – מעדכנים את `maxSum` ואת `best`.

4. בסוף מדפיסים את שם היישוב של הפרויקט במקום `best` (בעזרת `GetLocation`, כי הפעולה חיצונית).

לפי ההנחה, כל יישוב מופיע פעם אחת, ולכן אין צורך לצרף סכומים של כמה פרויקטים באותו יישוב. אם כמה פרויקטים שווים בסכום המקסימלי, מודפס הראשון מביניהם. סיבוכיות: OO של מספר כל התרומות בכל הפרויקטים.

C#:

public static void PrintBestLocation(CharityProject[] projects, char type)
{
    if (projects.Length == 0)
        return;                                    // אין פרויקטים
    int best = 0;                                  // מקום הפרויקט הטוב ביותר עד כה
    double maxSum = projects[0].GetTypeTotal(type);
    for (int i = 1; i < projects.Length; i++)
    {
        double sum = projects[i].GetTypeTotal(type);
        if (sum > maxSum)
        {
            maxSum = sum;
            best = i;
        }
    }
    Console.WriteLine(projects[best].GetLocation());
}

Java:

public static void printBestLocation(CharityProject[] projects, char type)
{
    if (projects.length == 0)
        return;                                    // אין פרויקטים
    int best = 0;                                  // מקום הפרויקט הטוב ביותר עד כה
    double maxSum = projects[0].getTypeTotal(type);
    for (int i = 1; i < projects.length; i++)
    {
        double sum = projects[i].getTypeTotal(type);
        if (sum > maxSum)
        {
            maxSum = sum;
            best = i;
        }
    }
    System.out.println(projects[best].getLocation());
}

דוגמה: Haifa – תרומות כסף 100+30=130100+30=130; Eilat – תרומת כסף 200200; Ashdod – אין תרומות כסף (00). עבור `'M'` יודפס `Eilat`.

תשובה: הפעולה `PrintBestLocation` (ב-Java: `printBestLocation`) שלמעלה.

שאלה 7 · מעקב: חפיפת סיפא ורישא של מחרוזות

לפניכם שתי פעולות `Secret` ו-`Sod`:

C#:

public static int Secret(string s, string t) {
    int v = 0;
    int n = s.Length;
    int m = t.Length;
    int len = (n < m) ? n : m;

    for (int i = 1; i <= len; i++) {
        string p1 = s.Substring(n - i);
        string p2 = t.Substring(0, i);

        if (p1 == p2) {
            v = i;
        }
    }
    return v;
}

public static bool Sod(string[] arr) {
    for (int j = 0; j < arr.Length - 1; j++) {
      (*) if (Secret(arr[j], arr[j + 1]) == 0) {
            return false;
        }
    }
    return true;
}

Java:

public static int secret(String s, String t) {
    int v = 0;
    int n = s.length();
    int m = t.length();
    int len = (n < m) ? n : m;

    for (int i = 1; i <= len; i++) {
        String p1 = s.substring(n - i);
        String p2 = t.substring(0, i);

        if (p1.equals(p2)) {
            v = i;
        }
    }
    return v;
}

public static boolean sod(String[] arr) {
    for (int j = 0; j < arr.length - 1; j++) {
      (*) if (secret(arr[j], arr[j + 1]) == 0) {
            return false;
        }
    }
    return true;
}
א.
(1)

עקבו בעזרת טבלת המעקב אחרי זימון הפעולה `Secret("Windstorm", "stormy")`.

בטבלת המעקב יש להציג את ערכי המשתנים p1, p2, i, v בכל סיבוב (איטרציה) של הלולאה.

(2)

תנו דוגמה לזוג מחרוזות שונות שעבורן הפעולה תחזיר ערך 3.

(3)

מה מבצעת הפעולה `Secret` באופן כללי עבור שתי מחרוזות `s1, s2`?

(8 נקודות)
ב.
(1)

נתון מערך:

`string[] arr = {"Basketball", "ballroom", "Roommate", "material"}`

עקבו אחרי זימון הפעולה `Sod(arr)` ורשמו מה תהיה תוצאת הזימון.

(2)

פקודת התנאי (*) השתנה לפקודה הבאה:

`if (Secret(arr[j], arr[j + 1]) !=3)`

תנו דוגמה למערך `arr` בגודל שישה תאים שעבורו זימון הפעולה `Sod(arr)` יחזיר ערך `true`.

(7 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

(1)
תשובה:

הפעולה מחזירה 5 (`"storm"` הוא הסיפא של `"Windstorm"` והרישא של `"stormy"`).

ערכים התחלתיים: `n = 9` (אורך `"Windstorm"`), `m = 6` (אורך `"stormy"`), `len = 6`, `v = 0`.

בכל סיבוב `p1` הוא ii התווים האחרונים של `s` (מהמקום n−in-i עד הסוף), ו-`p2` הוא ii התווים הראשונים של `t`.

סיבוב ip1p2p1 == p2?v
1"m""s"לא0
2"rm""st"לא0
3"orm""sto"לא0
4"torm""stor"לא0
5"storm""storm"כן5
6"dstorm""stormy"לא5

אחרי i=6i=6 הלולאה מסתיימת ומוחזר `v = 5`.

תשובה: `Secret("Windstorm", "stormy")` מחזירה 55.

(2)
תשובה:

למשל `Secret("Sunset", "setup")` מחזירה 3.

צריך ש-33 התווים האחרונים של המחרוזת הראשונה יהיו שווים ל-33 התווים הראשונים של השנייה, ושלא תהיה חפיפה ארוכה יותר (כי `v` שומר את ה-ii האחרון, כלומר הגדול ביותר, שבו יש שוויון).

דוגמה: `s = "Sunset"`, `t = "setup"` (`len = 5`):

•i=1i=1: `"t"` מול `"s"` – לא; i=2i=2: `"et"` מול `"se"` – לא;

•i=3i=3: `"set"` מול `"set"` – כן, `v = 3`;

•i=4i=4: `"nset"` מול `"setu"` – לא; i=5i=5: `"unset"` מול `"setup"` – לא.

מוחזר 33.

תשובה: `s = "Sunset"`, `t = "setup"`.

(3)
תשובה:

מחזירה את האורך של החפיפה הארוכה ביותר בין סוף `s1` לתחילת `s2` (הסיפא הארוכה ביותר של `s1` שהיא גם רישא של `s2`); אם אין חפיפה – 0.

1. לכל אורך ii מ-11 עד האורך של המחרוזת הקצרה, הפעולה משווה את ii התווים האחרונים של `s1` ל-ii התווים הראשונים של `s2`.

2. כשיש שוויון, `v` מקבל את ii. מאחר ש-ii עולה, בסוף `v` שווה ל-ii הגדול ביותר שבו היה שוויון.

3. אם לא היה שוויון באף אורך, `v` נשאר 00.

ההשוואה רגישה לאותיות גדולות וקטנות (`'R'` שונה מ-`'r'`).

תשובה: הפעולה מחזירה את אורך החלק הארוך ביותר שבו סוף המחרוזת `s1` זהה לתחילת המחרוזת `s2` ("כמה תווים אפשר להדביק בחפיפה"), ו-00 אם אין חפיפה כזאת.

סעיף ב

(1)
תשובה:

`Sod(arr)` מחזירה `false`: עבור `j = 1` החפיפה בין `"ballroom"` ל-`"Roommate"` היא 0 (`'R'` גדולה שונה מ-`'r'`).

`Sod` עוברת על זוגות סמוכים, ומחזירה `false` ברגע שלזוג כלשהו אין חפיפה (`Secret` מחזירה 00). הלולאה רצה עבור j=0,1,2j = 0, 1, 2.

מקום jarr[j]arr[j+1]Secret(arr[j], arr[j+1])שווה ל-0?פעולה
0"Basketball""ballroom"4 (`"ball"`)לאממשיכים
1"ballroom""Roommate"0כן`return false`

פירוט עבור j=1j=1: הסיפות של `"ballroom"` מתחילות באותיות קטנות (`"m"`, `"om"`, `"oom"`, `"room"`, ...) והרישות של `"Roommate"` מתחילות ב-`'R'` גדולה (`"R"`, `"Ro"`, `"Roo"`, `"Room"`, ...). למשל `"room"` שונה מ-`"Room"`, כי `'r'` שונה מ-`'R'`. לכן אין אף שוויון ו-`Secret` מחזירה 00.

הזוג j=2j=2 (`"Roommate"`, `"material"`, חפיפה 44 – `"mate"`) כבר לא נבדק.

תשובה: `Sod(arr)` מחזירה `false`.

(2)
תשובה:

למשל `{"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"}` – לכל זוג סמוך החפיפה היא בדיוק 3.

אחרי השינוי `Sod` מחזירה `false` לכל זוג סמוך שהחפיפה שלו שונה מ-33. כדי לקבל `true` צריך שלכל 55 הזוגות הסמוכים החפיפה המקסימלית תהיה בדיוק 33: שלושת התווים האחרונים של כל מחרוזת הם שלושת התווים הראשונים של הבאה, ואין חפיפה ארוכה יותר.

בונים שרשרת של מחרוזות באורך 66, שכל אחת מתחילה בשלושת התווים האחרונים של הקודמת:

`string[] arr = {"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"};`

בדיקה של הזוג הראשון: i=3i=3: `"def"` מול `"def"` – שוויון; i=1,2i=1,2 (`"f"`/`"d"`, `"ef"`/`"de"`) ו-i=4,5,6i=4,5,6 (`"cdef"`/`"defg"`, ...) – אין שוויון. לכן `Secret` מחזירה 33. כך גם לכל שאר הזוגות (`"ghi"`, `"jkl"`, `"mno"`, `"pqr"`). כל חמשת הזוגות מחזירים 33, התנאי `!= 3` אף פעם לא מתקיים, ו-`Sod` מחזירה `true`.

תשובה: `{"abcdef", "defghi", "ghijkl", "jklmno", "mnopqr", "pqrstu"}`.

שאלה 8 · מערך דו-ממדי מיוחד: מסגרת ותאים פנימיים

א.

הגדרה:

•מסגרת מערך הדו-ממדי מורכבת מהתאים הנמצאים בשורה 0, עמודה 0, שורה אחרונה ועמודה אחרונה.

•תא פנימי במערך דו-ממדי הוא איבר שאינו נמצא במסגרת המערך.

•מערך דו-ממדי נקרא "מערך מיוחד" אם כל האיברים הנמצאים במסגרת קטנים ממש מכל האיברים הנמצאים בתאים פנימיים.

הנחה: גודל המערך הוא לפחות 3X3

לדוגמה, המערך הבא הוא מערך מיוחד:

שורה עמודה01234
015364
1-610891
211512213
3452-70

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים. הפעולה תבדוק אם המערך הוא מערך מיוחד. אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.

כותרת הפעולה:

C#:

public static bool IsSpecial(int[,] arr)

Java:

public static boolean isSpecial(int[][] arr)
(8 נקודות)
ב.

מהי סיבוכיות זמן הריצה של כל הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.

(3 נקודות)
ג.

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr` ושני מספרים שלמים `low` ו-`high`.

הפעולה תמלא את המערך במספרים אקראיים בטווח בין `low` ל-`high` (כולל), כך שיתקבל מערך "מיוחד".

כותרת הפעולה:

C#:

public static void MakeSpecial(int[,] arr, int low, int high)

Java:

public static void makeSpecial(int[][] arr, int low, int high)

הנחה: הטווח בין `low` ל-`high` גדול מספיק (לפחות 2 ערכים שונים).

הנחיה: בצעו את המילוי בדרך שאינה מסתמכת על מזל בלבד, אלא מבטיחה את התנאי מראש.

(6 נקודות)
◂ פתרון מלא לשאלה 8

סעיף א

תשובה:

מחשבים במעבר אחד את המקסימום של תאי המסגרת ואת המינימום של התאים הפנימיים, ומחזירים `maxFrame < minInner`.

הרעיון: "כל איבר במסגרת קטן ממש מכל איבר פנימי" שקול לתנאי אחד: הגדול ביותר במסגרת קטן ממש מהקטן ביותר בפנים. (אם המקסימום של המסגרת קטן מהמינימום של הפנים, כל איבר במסגרת קטן מכל איבר בפנים; ואם לא – הזוג של שניהם מפר את התנאי.) כך אין צורך להשוות כל זוג תאים.

1. מאתחלים את `maxFrame` בתא `[0,0]` (תמיד במסגרת) ואת `minInner` בתא `[1,1]` (תמיד פנימי, כי המערך לפחות 3×33 \times 3).

2. עוברים על כל התאים. תא נמצא במסגרת אם הוא בשורה 00, בשורה האחרונה, בעמודה 00 או בעמודה האחרונה. לתא במסגרת מעדכנים את `maxFrame`, ולתא פנימי את `minInner`.

3. מחזירים `maxFrame < minInner` (קטן ממש).

בדיקה בדוגמה: במסגרת הערכים 1,5,3,6,4,−6,1,1,3,4,5,2,−7,01,5,3,6,4,-6,1,1,3,4,5,2,-7,0 – המקסימום 66. בפנים 10,8,9,15,12,2110,8,9,15,12,21 – המינימום 88. 6<86<8, ולכן מוחזר `true`.

C#:

public static bool IsSpecial(int[,] arr)
{
    int rows = arr.GetLength(0);
    int cols = arr.GetLength(1);
    int maxFrame = arr[0, 0];     // המקסימום של המסגרת
    int minInner = arr[1, 1];     // המינימום של התאים הפנימיים
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
            {
                if (arr[i, j] > maxFrame)
                    maxFrame = arr[i, j];       // תא במסגרת
            }
            else
            {
                if (arr[i, j] < minInner)
                    minInner = arr[i, j];       // תא פנימי
            }
        }
    }
    return maxFrame < minInner;
}

Java:

public static boolean isSpecial(int[][] arr)
{
    int rows = arr.length;
    int cols = arr[0].length;
    int maxFrame = arr[0][0];     // המקסימום של המסגרת
    int minInner = arr[1][1];     // המינימום של התאים הפנימיים
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
            {
                if (arr[i][j] > maxFrame)
                    maxFrame = arr[i][j];       // תא במסגרת
            }
            else
            {
                if (arr[i][j] < minInner)
                    minInner = arr[i][j];       // תא פנימי
            }
        }
    }
    return maxFrame < minInner;
}

תשובה: הפעולה `IsSpecial` (ב-Java: `isSpecial`) שלמעלה.

סעיף ב

תשובה:

O(n⋅m)O(n \cdot m) עבור מערך בן nn שורות ו-mm עמודות (ליניארי במספר התאים; O(n2)O(n^2) למערך ריבועי).

1. נסמן ב-nn את מספר השורות וב-mm את מספר העמודות.

2. הפעולה עוברת פעם אחת על כל התאים בעזרת שתי לולאות מקוננות: n⋅mn \cdot m סיבובים.

3. בכל סיבוב יש מספר קבוע של פעולות (בדיקה אם התא במסגרת, השוואה ואולי עדכון) – O(1)O(1).

4. האתחול וההשוואה בסוף הם O(1)O(1).

סך הכול n⋅m⋅O(1)=O(n⋅m)n \cdot m \cdot O(1) = O(n \cdot m). זה גם המינימום האפשרי, כי כדי לדעת שהמערך מיוחד חייבים לבדוק כל תא לפחות פעם אחת.

תשובה: O(n⋅m)O(n \cdot m) (במערך ריבועי n×nn \times n: O(n2)O(n^2)).

סעיף ג

תשובה:

מחלקים את הטווח בנקודה `mid = low + (high - low) / 2`: תאי המסגרת מקבלים מספר אקראי בין `low` ל-`mid`, והתאים הפנימיים מספר אקראי בין `mid + 1` ל-`high`.

הרעיון: כדי להבטיח מראש שכל איבר במסגרת קטן מכל איבר פנימי, מחלקים את הטווח לשני חלקים זרים – חלק תחתון למסגרת וחלק עליון לפנים:

1. מחשבים נקודת חלוקה `mid = low + (high - low) / 2`.

2. תא במסגרת מקבל מספר אקראי בטווח `low..mid`, ותא פנימי מספר אקראי בטווח `mid+1..high`.

3. כל ערך במסגרת ≤mid<mid+1≤\le mid < mid+1 \le כל ערך פנימי, ולכן המערך מיוחד בוודאות, בלי תלות במזל.

למה שני הטווחים לא ריקים: לפי ההנחה `high - low` ≥1\ge 1. אז `mid` ≥\ge `low` (הטווח `low..mid` מכיל לפחות ערך אחד), ו-`mid` << `high` כי ⌊(high−low)/2⌋<high−low\lfloor (high-low)/2 \rfloor < high-low (הטווח `mid+1..high` מכיל לפחות ערך אחד). למשל עבור `low = 1`, `high = 2`: `mid = 1`, המסגרת כולה 11 והפנים כולו 22. כל המספרים בטווח `low..high`, כנדרש.

הגרלה: ב-C# `rand.Next(a, b + 1)` נותן מספר בין `a` ל-`b` כולל; ב-Java `a + rand.nextInt(b - a + 1)`. סיבוכיות: O(n⋅m)O(n \cdot m).

C#:

public static void MakeSpecial(int[,] arr, int low, int high)
{
    Random rand = new Random();
    int mid = low + (high - low) / 2;   // המסגרת: low..mid, הפנים: mid+1..high
    int rows = arr.GetLength(0);
    int cols = arr.GetLength(1);
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
                arr[i, j] = rand.Next(low, mid + 1);        // תא במסגרת
            else
                arr[i, j] = rand.Next(mid + 1, high + 1);   // תא פנימי
        }
    }
}

Java:

public static void makeSpecial(int[][] arr, int low, int high)
{
    Random rand = new Random();
    int mid = low + (high - low) / 2;   // המסגרת: low..mid, הפנים: mid+1..high
    int rows = arr.length;
    int cols = arr[0].length;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1)
                arr[i][j] = low + rand.nextInt(mid - low + 1);      // תא במסגרת
            else
                arr[i][j] = mid + 1 + rand.nextInt(high - mid);     // תא פנימי
        }
    }
}

דוגמה: עבור `low = 0`, `high = 100`: `mid = 50`, המסגרת מקבלת ערכים בין 00 ל-5050 והתאים הפנימיים ערכים בין 5151 ל-100100.

תשובה: הפעולה `MakeSpecial` (ב-Java: `makeSpecial`) שלמעלה.

שאלה 9 · מרכז למידה: רישום לקורסים וקורסי מצטיינים

מרכז למידה מעוניין לנהל את הרישום לקורסים שלו. לשם כך הוגדרו שלוש מחלקות:

המחלקה `Student` מייצגת תלמיד. למחלקה שתי תכונות:

•שם מלא (`fullName`) – מחרוזת, `string`; (ב-Java: `String`)

•ציון ממוצע (`grade`) – מספר ממשי, `double`.

במחלקה הוגדרו בנאי, פעולות `Get/Set` ופעולה `ToString`.

המחלקה `Course` מייצגת קורס בודד. למחלקה התכונות האלה:

•שם קורס (`courseName`) – מחרוזת, `string`;

•ציון סף לקבלה לקורס (`minEntryGrade`) – מספר ממשי, `double`;

•מספר מקסימלי של מקומות בקורס (`maxStudents`) – מספר שלם, `int`;

•תלמידים שנרשמו (`registered`) – מערך של אובייקטים מסוג `Student`;

•מספר תלמידים שנרשמו בפועל (`count`) – מספר שלם, `int`.

במחלקה הוגדרו פעולות `Get/Set` והפעולה `ToString`.

המחלקה `LearningCenter` מייצגת את המרכז כולו. למחלקה שתי תכונות:

•שם מרכז (`centerName`) – מחרוזת, `string`;

•רשימת קורסים (`courses`) – מערך של אובייקטים מסוג `Course`. המערך מלא ולא כולל ערכי `null`.

א.
(1)

כתבו במחלקה `Course` פעולה בונה המקבלת שם קורס, ציון סף לקבלה ומספר מקסימלי של מקומות.

הפעולה מאתחלת קורס ללא רשומים.

(2)

כתבו במחלקה `Course` פעולה בשם `AddStudent`. הפעולה תוסיף את התלמיד לקורס אם יש מקום פנוי בקורס והציון הממוצע של התלמיד גדול או שווה לציון הסף של הקורס. אם ההוספה הצליחה – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר ערך `false`. כותרת הפעולה:

C#:

public bool AddStudent(string name, double grade)

Java:

public boolean addStudent(String name, double grade)
(3)

קורס נקרא "קורס מצטיינים" אם לפחות חצי מהרשומים בקורס הם בעלי ציון ממוצע הגבוה מ-90.

כתבו במחלקה `Course` פעולה בשם `IsHonorsCourse`. אם קורס הוא "קורס מצטיינים" – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר ערך `false`. אם אין תלמידים רשומים כלל, הפעולה תחזיר `false`.

(9 נקודות)
ב.
(1)

כתבו במחלקה `LearningCenter` פעולה בשם `PrintFullCourses`. הפעולה תדפיס את שמות הקורסים שאין בהם מקומות פנויים.

(2)

כתבו עבור המחלקה `LearningCenter` פעולה בשם `GetExcellentCourses`. הפעולה תיצור ותחזיר מערך חדש המכיל את שמות הקורסים המוגדרים כ"קורסי מצטיינים".

הערה: עליכם להקצות למערך החדש גודל מתאים בדיוק למספר הקורסים שנמצאו. אם אין אף קורס מתאים, הפעולה תחזיר מערך בגודל 0.

(8 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

(1)
תשובה:

מציבים את שלושת הפרמטרים בתכונות, יוצרים `registered = new Student[maxStudents]` ומאתחלים `count = 0`.

הרעיון: שלוש תכונות מקבלות את ערכי הפרמטרים. "ללא רשומים" פירושו שמספר הרשומים בפועל `count` הוא 00. את מערך הרשומים יוצרים בגודל המקסימלי `maxStudents`, כדי שיהיה בו מקום לכל תלמיד שאפשר לרשום; התאים שלו יתמלאו לפי הסדר מהמקום 00, ו-`count` יציין כמה מהם בשימוש.

C#:

public Course(string courseName, double minEntryGrade, int maxStudents)
{
    this.courseName = courseName;
    this.minEntryGrade = minEntryGrade;
    this.maxStudents = maxStudents;
    this.registered = new Student[maxStudents];   // מקום לכל התלמידים האפשריים
    this.count = 0;                                // עדיין אין רשומים
}

Java:

public Course(String courseName, double minEntryGrade, int maxStudents)
{
    this.courseName = courseName;
    this.minEntryGrade = minEntryGrade;
    this.maxStudents = maxStudents;
    this.registered = new Student[maxStudents];   // מקום לכל התלמידים האפשריים
    this.count = 0;                                // עדיין אין רשומים
}

תשובה: הפעולה הבונה שלמעלה.

(2)
תשובה:

אם `count < maxStudents` וגם `grade >= minEntryGrade` – יוצרים `new Student(name, grade)`, מכניסים למקום `count`, מגדילים את `count` ומחזירים `true`; אחרת `false`.

הרעיון: שני תנאים חייבים להתקיים יחד:

1. יש מקום פנוי: `count < maxStudents`.

2. הציון עובר את הסף: `grade >= minEntryGrade`.

אם שניהם מתקיימים – יוצרים עצם `Student` חדש מהשם ומהציון (בעזרת הבנאי של `Student`), שמים אותו בתא הפנוי הראשון `registered[count]`, מגדילים את `count` ב-11 ומחזירים `true`. אחרת לא משנים דבר ומחזירים `false`.

C#:

public bool AddStudent(string name, double grade)
{
    if (count < maxStudents && grade >= minEntryGrade)
    {
        registered[count] = new Student(name, grade);
        count++;
        return true;
    }
    return false;
}

Java:

public boolean addStudent(String name, double grade)
{
    if (count < maxStudents && grade >= minEntryGrade)
    {
        registered[count] = new Student(name, grade);
        count++;
        return true;
    }
    return false;
}

דוגמה: בקורס עם סף 8080 ו-33 מקומות: תלמיד עם 9595 נוסף (`true`), תלמיד עם 7070 נדחה (`false`), תלמידים עם 8585 ו-9999 נוספים (`true`), ותלמיד עם 100100 נדחה כי הקורס מלא (`false`).

תשובה: הפעולה `AddStudent` (ב-Java: `addStudent`) שלמעלה.

(3)
תשובה:

אם `count == 0` מחזירים `false`; אחרת סופרים את הרשומים עם ציון גבוה מ-90 ומחזירים `excellent * 2 >= count`.

הרעיון:

1. אם `count == 0` – מחזירים `false` מיד (כך נדרש, ואחרת התנאי היה מתקיים "בטעות" כי 0≥00 \ge 0).

2. עוברים רק על `count` התאים הראשונים של `registered` (שאר התאים ריקים) וסופרים את התלמידים שהציון שלהם גבוה ממש מ-9090.

3. "לפחות חצי" פירושו excellent≥count2excellent \ge \frac{count}{2}. כדי להימנע מחלוקה בשלמים (שמעגלת כלפי מטה) משווים בצורה השקולה 2⋅excellent≥count2 \cdot excellent \ge count.

דוגמה: בקורס מסעיף 2 רשומים 9595, 8585, 9999 – שניים מעל 9090, 2⋅2=4≥32 \cdot 2 = 4 \ge 3, ולכן `true`. בקורס עם 9191, 6060, 6565 – רק אחד, 2<32 < 3, ולכן `false`.

C#:

public bool IsHonorsCourse()
{
    if (count == 0)
        return false;               // אין רשומים
    int excellent = 0;
    for (int i = 0; i < count; i++)
    {
        if (registered[i].GetGrade() > 90)
            excellent++;
    }
    return excellent * 2 >= count;  // לפחות חצי מהרשומים
}

Java:

public boolean isHonorsCourse()
{
    if (count == 0)
        return false;               // אין רשומים
    int excellent = 0;
    for (int i = 0; i < count; i++)
    {
        if (registered[i].getGrade() > 90)
            excellent++;
    }
    return excellent * 2 >= count;  // לפחות חצי מהרשומים
}

תשובה: הפעולה `IsHonorsCourse` (ב-Java: `isHonorsCourse`) שלמעלה.

סעיף ב

(1)
תשובה:

עוברים על `courses` ומדפיסים את `GetCourseName()` של כל קורס שבו `GetCount() == GetMaxStudents()`.

הרעיון: בקורס אין מקומות פנויים כאשר מספר הרשומים בפועל שווה למספר המקסימלי של מקומות. הפעולה נמצאת ב-`LearningCenter`, ולכן לתכונות של כל `Course` ניגשים דרך פעולות ה-`Get`:

1. עוברים על כל הקורסים במערך `courses` (המערך מלא, בלי `null`).

2. אם `GetCount() == GetMaxStudents()` – מדפיסים את שם הקורס.

C#:

public void PrintFullCourses()
{
    for (int i = 0; i < courses.Length; i++)
    {
        if (courses[i].GetCount() == courses[i].GetMaxStudents())
            Console.WriteLine(courses[i].GetCourseName());
    }
}

Java:

public void printFullCourses()
{
    for (int i = 0; i < courses.length; i++)
    {
        if (courses[i].getCount() == courses[i].getMaxStudents())
            System.out.println(courses[i].getCourseName());
    }
}

תשובה: הפעולה `PrintFullCourses` (ב-Java: `printFullCourses`) שלמעלה.

(2)
תשובה:

מעבר ראשון סופר בעזרת `IsHonorsCourse()` את קורסי המצטיינים; יוצרים `string[]` בגודל הזה (אולי 0); מעבר שני ממלא אותו בשמות הקורסים לפי הסדר.

הרעיון: הגודל המדויק של המערך ידוע רק אחרי ספירה, לכן שני מעברים:

1. ספירה: עוברים על הקורסים וסופרים ב-`num` את אלה שעבורם `IsHonorsCourse()` (מסעיף א3) מחזירה `true`.

2. יוצרים מערך מחרוזות בגודל `num`. אם אין אף קורס מתאים, `num = 0` ונוצר מערך בגודל 00, כנדרש.

3. מילוי: עוברים שוב, וכל קורס מצטיינים מוסיף את שמו (`GetCourseName()`) למקום `k`, ו-`k` גדל ב-11.

4. מחזירים את המערך.

C#:

public string[] GetExcellentCourses()
{
    // מעבר ראשון: כמה קורסי מצטיינים יש?
    int num = 0;
    for (int i = 0; i < courses.Length; i++)
    {
        if (courses[i].IsHonorsCourse())
            num++;
    }
    // מעבר שני: מילוי מערך השמות בגודל המדויק
    string[] result = new string[num];
    int k = 0;
    for (int i = 0; i < courses.Length; i++)
    {
        if (courses[i].IsHonorsCourse())
        {
            result[k] = courses[i].GetCourseName();
            k++;
        }
    }
    return result;
}

Java:

public String[] getExcellentCourses()
{
    // מעבר ראשון: כמה קורסי מצטיינים יש?
    int num = 0;
    for (int i = 0; i < courses.length; i++)
    {
        if (courses[i].isHonorsCourse())
            num++;
    }
    // מעבר שני: מילוי מערך השמות בגודל המדויק
    String[] result = new String[num];
    int k = 0;
    for (int i = 0; i < courses.length; i++)
    {
        if (courses[i].isHonorsCourse())
        {
            result[k] = courses[i].getCourseName();
            k++;
        }
    }
    return result;
}

תשובה: הפעולה `GetExcellentCourses` (ב-Java: `getExcellentCourses`) שלמעלה.

שאלה 10 · רקורסיה: מספר מיוחד ומקסימום מיוחד במערך

א.

נתונה הפעולה `Special` המקבלת מספר שלם `num` ובודקת אם הוא "מספר מיוחד":

C#:

public static bool Special(int num) {
    if(num < 10) return false;
    return Special(num, 0);
}
public static bool Special(int num, int diff) {
    if(num == 0){
        return diff == 0;
    }
    int last = num % 10;
    return Special(num/10, last - diff);
}

Java:

public static boolean special(int num) {
    if(num < 10) return false;
    return special(num, 0);
}
public static boolean special(int num, int diff) {
    if(num == 0){
        return diff == 0;
    }
    int last = num % 10;
    return special(num/10, last - diff);
}
(1)

מה תהיה תוצאת זימון הפעולה `Special(12551)`? יש להראות מעקב.

(2)

מה תהיה תוצאת זימון הפעולה `Special(4254)`?

(3)

מה מבצעת הפעולה `Special(num)` באופן כללי עבור מספר שלם `num`?

יש להתייחס למקרים שונים של `num`.

(6 נקודות)
ב.

נתונה הפעולה `Secret` המקבלת מערך של מספרים שלמים. הפעולה משתמשת בפעולה `Special`.

C#:

public static int Secret(int[] arr){
    return Secret(arr, 0);
}

public static int Secret(int[] arr, int i) {
    if (i == arr.Length) {
        return -1;
    }
    int res = Secret(arr, i + 1);

    if (Special(arr[i]) && arr[i] > res) {
        return arr[i];
    }
    return res;
}

Java:

public static int secret(int[] arr){
    return secret(arr, 0);
}

public static int secret(int[] arr, int i) {
    if (i == arr.length) {
        return -1;
    }
    int res = secret(arr, i + 1);

    if (special(arr[i]) && arr[i] > res) {
        return arr[i];
    }
    return res;
}

נתון מערך `arr`:

`int[] arr = {1234, 55, 1012, 363, 44, 827, 198}`

(1)

מה תהיה תוצאת זימון הפעולה `Secret(arr)`? יש להראות מעקב זימון הפעולה.

אין צורך במעקב אחרי הפעולה `Special`.

(2)

מה מבצעת הפעולה `Secret` באופן כללי?

(6 נקודות)
ג.

כתבו הפעולה רקורסיבית המקבלת מערך של מספרים שלמים. הפעולה תבדוק שכל המספרים במערך הם "מיוחדים" (כלומר הפעולה `Special` תחזיר ערך `true` עבורם).

אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.

(5 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

(1)
תשובה:

`true`.

12551≥1012551 \ge 10, ולכן מזמנים `Special(12551, 0)`. בכל זימון: `last` היא ספרת האחדות, והזימון הבא מקבל `num/10` ו-`last - diff`.

זימוןnumdifflast = num % 10הזימון הבא
11255101Special(1255, 1 - 0 = 1)
2125515Special(125, 5 - 1 = 4)
312545Special(12, 5 - 4 = 1)
41212Special(1, 2 - 1 = 1)
5111Special(0, 1 - 1 = 0)
600–מחזיר `diff == 0` → `true`

הערך `true` עובר חזרה בלי שינוי דרך כל הזימונים.

תשובה: `Special(12551)` מחזירה `true`.

(2)
תשובה:

`false` (בסוף `diff = 3`).

4254≥104254 \ge 10, ולכן מזמנים `Special(4254, 0)`:

זימוןnumdifflastהזימון הבא
1425404Special(425, 4 - 0 = 4)
242545Special(42, 5 - 4 = 1)
34212Special(4, 2 - 1 = 1)
4414Special(0, 4 - 1 = 3)
503–מחזיר `3 == 0` → `false`

תשובה: `Special(4254)` מחזירה `false`.

(3)
תשובה:

עבור `num < 10` (חד-ספרתי, 0 או שלילי) מחזירה `false`. עבור `num >= 10` מחזירה `true` אם ורק אם סכום הספרות במקומות הזוגיים שווה לסכום הספרות במקומות האי-זוגיים (הסכום המתחלף של הספרות הוא 0).

1. מקרה `num < 10`: מספר חד-ספרתי, 00 או מספר שלילי – הפעולה מחזירה `false` מיד.

2. מקרה `num >= 10`: נסמן את הספרות מימין לשמאל d0,d1,d2,…d_0, d_1, d_2, \dots (אחדות, עשרות, ...). לפי הקוד:

•אחרי ספרה אחת: diff=d0diff = d_0;

•אחרי שתיים: diff=d1−d0diff = d_1 - d_0;

•אחרי שלוש: diff=d2−d1+d0diff = d_2 - d_1 + d_0; וכן הלאה.

כלומר, בסוף diffdiff הוא (עד כדי סימן) הסכום המתחלף d0−d1+d2−d3+…d_0 - d_1 + d_2 - d_3 + \dots, והפעולה מחזירה `true` אם ורק אם הוא 00.

3. במילים: מספר הוא "מיוחד" אם יש לו לפחות שתי ספרות, וסכום הספרות במקומות הזוגיים (אחדות, מאות, ...) שווה לסכום הספרות במקומות האי-זוגיים (עשרות, אלפים, ...).

בדיקה: 1255112551: 1+5+1=71+5+1 = 7 ו-5+2=75+2 = 7 – שווים, `true`. 42544254: 4+2=64+2 = 6 ו-5+4=95+4 = 9 – לא שווים, `false` (ההפרש 33 הוא בדיוק `diff` האחרון).

הערה: כל מספר מיוחד מתחלק ב-1111 (כי הסכום המתחלף שלו 00), אבל לא להפך – למשל 209209 מתחלק ב-1111 אך הסכום המתחלף שלו הוא 9−0+2=11≠09-0+2=11 \ne 0 (הוא 209=11⋅19209 = 11 \cdot 19, ו-`Special(209)` מחזירה `false`).

תשובה: עבור `num < 10` מוחזר `false`; עבור `num >= 10` מוחזר `true` אם ורק אם סכום הספרות במקומות הזוגיים שווה לסכום הספרות במקומות האי-זוגיים.

סעיף ב

(1)
תשובה:

`Secret(arr)` מחזירה 1012.

`Secret(arr)` מזמנת את `Secret(arr, 0)`. כל זימון קורא קודם לזימון של `i+1`, ולכן הזימונים "יורדים" עד `i = 7` (סוף המערך), שמחזיר −1-1, והחישוב מתבצע בדרך חזרה – מסוף המערך להתחלה.

קודם בודקים אילו מספרים מיוחדים (סכום מתחלף של הספרות 00): 12341234: 4−3+2−1=24-3+2-1=2 – לא; 5555: 5−5=05-5=0 – כן; 10121012: 2−1+0−1=02-1+0-1=0 – כן; 363363: 3−6+3=03-6+3=0 – כן; 4444 – כן; 827827: 7−2+8=137-2+8=13 – לא; 198198: 8−9+1=08-9+1=0 – כן.

מקום iarr[i]Special(arr[i])res = Secret(arr, i+1)arr[i] > res?מוחזר
7––––-1 (תנאי עצירה)
6198true-1כן198
5827false198–198
444true198לא198
3363true198כן363
21012true363כן1012
155true1012לא1012
01234false1012–1012

תשובה: `Secret(arr)` מחזירה 10121012.

(2)
תשובה:

מחזירה את המספר המיוחד הגדול ביותר במערך, ו-1- אם אין במערך אף מספר מיוחד.

1. `Secret(arr, i)` מחזירה ערך שמתייחס לחלק המערך מהמקום `i` עד הסוף. עבור חלק ריק (`i == arr.Length`) מוחזר −1-1.

2. בכל שלב, `res` הוא התוצאה של החלק שמימין. אם `arr[i]` מיוחד וגדול מ-`res`, הוא מחליף אותו; אחרת נשאר `res`.

3. זהו חיפוש מקסימום רקורסיבי רק בין המספרים המיוחדים. −1-1 משמש כערך התחלתי: כל מספר מיוחד הוא לפחות 1010, ולכן גדול ממנו, ו-−1-1 נשאר רק אם אין אף מספר מיוחד.

תשובה: הפעולה מחזירה את המספר ה"מיוחד" הגדול ביותר במערך; אם אין במערך מספר מיוחד – היא מחזירה −1-1.

סעיף ג

תשובה:

פעולת מעטפת `AllSpecial(arr)` שמזמנת `AllSpecial(arr, 0)`: אם `i == Length` מחזירים `true`; אם `arr[i]` אינו מיוחד – `false`; אחרת מזמנים עם `i + 1`.

הרעיון: כמו בסעיף ב, משתמשים בפעולת עזר עם אינדקס `i`, שבודקת את חלק המערך מ-`i` עד הסוף. פעולה עם פרמטר אחד (המערך) מזמנת אותה עם `i = 0`.

1. תנאי עצירה: אם `i == Length` – לא נשארו איברים לבדוק, וכל מה שנבדק היה מיוחד: מחזירים `true`. (למערך ריק מוחזר `true` – אין בו מספר שאינו מיוחד.)

2. צעד: אם `arr[i]` אינו מיוחד (`Special` מחזירה `false`) – מחזירים `false` מיד.

3. אחרת, התשובה היא התשובה עבור שאר המערך: מזמנים רקורסיבית עם `i + 1`.

C#:

public static bool AllSpecial(int[] arr)
{
    return AllSpecial(arr, 0);
}

public static bool AllSpecial(int[] arr, int i)
{
    if (i == arr.Length)
        return true;                    // עברנו על כל המערך
    if (!Special(arr[i]))
        return false;                   // נמצא מספר שאינו מיוחד
    return AllSpecial(arr, i + 1);      // בודקים את המשך המערך
}

Java:

public static boolean allSpecial(int[] arr)
{
    return allSpecial(arr, 0);
}

public static boolean allSpecial(int[] arr, int i)
{
    if (i == arr.length)
        return true;                    // עברנו על כל המערך
    if (!special(arr[i]))
        return false;                   // נמצא מספר שאינו מיוחד
    return allSpecial(arr, i + 1);      // בודקים את המשך המערך
}

דוגמה: עבור `{55, 1012, 363}` מוחזר `true`; עבור `{55, 1234}` מוחזר `false` (כי 12341234 אינו מיוחד).

תשובה: הפעולה הרקורסיבית `AllSpecial` (ב-Java: `allSpecial`) שלמעלה.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.