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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

מילון עזר.

שאלה 1 · מחרוזת תקינה: אורך זוגי ותו ראשון ייחודי

א.

מחרוזת "תקינה" היא מחרוזת העונה על שני תנאים:

•אורך המחרוזת זוגי;

•התו הראשון זהה לתו האחרון ותו זה אינו מופיע במקומות האחרים של המחרוזת.

לדוגמה: המחרוזת `"Abbc1A"` היא "מחרוזת תקינה".

המחרוזת `"Abc1A"` אינה "מחרוזת תקינה".

המחרוזת `"Abbc1D"` אינה "מחרוזת תקינה".

המחרוזת `"AbAc1A"` אינה "מחרוזת תקינה".

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

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

C#:

public static bool IsValid (string s)

Java:

public static boolean isValid (String s)
(6 נקודות)
ב.

כתבו קטע קוד הקולט 30 מחרוזות. הקטע יחשב וידפיס את מספר "המחרוזות התקינות" ואת מספר המחרוזות שאינן תקינות. יש להשתמש בפעולה שכתבתם בסעיף א'.

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

סעיף א

תשובה:

פעולה שמחזירה `false` אם האורך אינו זוגי (או 0), אם התו האחרון שונה מהראשון, או אם התו הראשון מופיע באחד המקומות 11 עד n−2n-2; אחרת מחזירה `true`.

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

1. אורך זוגי: אם `n % 2 != 0` – המחרוזת לא תקינה. מחרוזת ריקה (אורך 00) גם נפסלת, כי אין לה תו ראשון ואחרון.

2. התו הראשון שווה לאחרון: שומרים את התו הראשון במשתנה `first` ומשווים אותו לתו במקום n−1n-1.

3. התו הראשון לא מופיע במקומות האחרים: עוברים בלולאה על המקומות 11 עד n−2n-2 (כל המקומות פרט לראשון ולאחרון). אם באחד מהם מופיע `first` – מחזירים `false`.

4. אם עברנו את כל הבדיקות – המחרוזת תקינה, ומחזירים `true`.

סיבוכיות: O(n)O(n) – מעבר אחד על המחרוזת.

C#:

public static bool IsValid(string s)
{
    int n = s.Length;
    if (n == 0 || n % 2 != 0)
        return false;                 // אורך המחרוזת אינו זוגי (או מחרוזת ריקה)
    char first = s[0];
    if (s[n - 1] != first)
        return false;                 // התו האחרון שונה מהתו הראשון
    for (int i = 1; i < n - 1; i++)   // המקומות האחרים: בין הראשון לאחרון
    {
        if (s[i] == first)
            return false;             // התו הראשון מופיע גם באמצע
    }
    return true;
}

Java:

public static boolean isValid(String s)
{
    int n = s.length();
    if (n == 0 || n % 2 != 0)
        return false;                 // אורך המחרוזת אינו זוגי (או מחרוזת ריקה)
    char first = s.charAt(0);
    if (s.charAt(n - 1) != first)
        return false;                 // התו האחרון שונה מהתו הראשון
    for (int i = 1; i < n - 1; i++)   // המקומות האחרים: בין הראשון לאחרון
    {
        if (s.charAt(i) == first)
            return false;             // התו הראשון מופיע גם באמצע
    }
    return true;
}

בדיקה מול הדוגמאות:

מחרוזתאורךראשון = אחרון?הראשון מופיע באמצע?תוצאה
`"Abbc1A"`6 (זוגי)כן (`A`)לא`true`
`"Abc1A"`5 (אי-זוגי)––`false`
`"Abbc1D"`6לא (`A` מול `D`)–`false`
`"AbAc1A"`6כןכן (מקום 2)`false`

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

סעיף ב

תשובה:

לולאת `for` של 30 סיבובים: קולטים מחרוזת, ולפי הפעולה מסעיף א מגדילים את מונה התקינות או את מונה הלא-תקינות; אחרי הלולאה מדפיסים את שני המונים.

הרעיון: מספר המחרוזות ידוע מראש (30), ולכן משתמשים בלולאת `for`.

1. מאתחלים שני מונים: `validCount = 0` למחרוזות התקינות ו-`invalidCount = 0` לשאינן תקינות.

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

3. אם הפעולה החזירה `true` – מגדילים את `validCount`, אחרת – את `invalidCount`.

4. אחרי הלולאה מדפיסים את שני המונים. (בסוף תמיד מתקיים `validCount + invalidCount = 30`.)

C#:

int validCount = 0;     // מונה המחרוזות התקינות
int invalidCount = 0;   // מונה המחרוזות שאינן תקינות
string str;
for (int i = 1; i <= 30; i++)
{
    str = Console.ReadLine();
    if (IsValid(str))
        validCount++;
    else
        invalidCount++;
}
Console.WriteLine("valid: " + validCount);
Console.WriteLine("not valid: " + invalidCount);

Java:

int validCount = 0;     // מונה המחרוזות התקינות
int invalidCount = 0;   // מונה המחרוזות שאינן תקינות
String str;
for (int i = 1; i <= 30; i++)
{
    str = in.next();
    if (isValid(str))
        validCount++;
    else
        invalidCount++;
}
System.out.println("valid: " + validCount);
System.out.println("not valid: " + invalidCount);

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

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

א.

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

לדוגמה:

עבור המספר 12734 הפעולה תחזיר 7.

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

C#:

public static int MaxDigit(int num)

Java:

public static int maxDigit(int num)
(6 נקודות)
ב.

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

לדוגמה:

עבור המערך `arr = {1283, 45, 1971, 613}` הפעולה תחזיר 5.

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

C#:

public static int MinOfMaxDigits(int[] arr)

Java:

public static int minOfMaxDigits(int[] arr)

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

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

סעיף א

תשובה:

מפרקים את המספר לספרות בעזרת `% 10` ו-`/ 10` ושומרים את הספרה הגדולה ביותר; עבור 12734 מוחזר 7.

הרעיון: מפרקים את המספר לספרותיו מימין לשמאל: `num % 10` נותן את ספרת האחדות, ו-`num / 10` מוחק אותה. זהו חיפוש מקסימום רגיל:

1. מאתחלים את `max` בספרת האחדות, ומוחקים אותה מהמספר.

2. כל עוד נשארו ספרות (`num > 0`) – לוקחים את הספרה הבאה, ואם היא גדולה מ-`max` מעדכנים את `max`.

3. מחזירים את `max`.

האתחול בספרה אמיתית של המספר (ולא ב-0 שרירותי) נכון תמיד. סיבוכיות: O(d)O(d), כאשר dd מספר הספרות.

C#:

public static int MaxDigit(int num)
{
    int max = num % 10;        // ספרת האחדות היא המועמדת הראשונה
    num = num / 10;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig > max)
            max = dig;
        num = num / 10;
    }
    return max;
}

Java:

public static int maxDigit(int num)
{
    int max = num % 10;        // ספרת האחדות היא המועמדת הראשונה
    num = num / 10;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig > max)
            max = dig;
        num = num / 10;
    }
    return max;
}

מעקב עבור 12734:

שלב`num``dig``max`
אתחול1273–4
סיבוב 112734
סיבוב 21277
סיבוב 3127
סיבוב 4017

מוחזר 7, כמו בדוגמה.

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

סעיף ב

תשובה:

מחשבים `MaxDigit` לכל איבר ומחזירים את הקטן מבין הערכים; עבור `{1283, 45, 1971, 613}` מוחזר 5.

הרעיון: חיפוש מינימום על הערכים `MaxDigit(arr[i])`:

1. מאתחלים את `min` בספרה המקסימלית של האיבר הראשון.

2. עוברים על שאר האיברים, מחשבים לכל אחד את הספרה המקסימלית שלו בעזרת הפעולה מסעיף א, ואם היא קטנה מ-`min` – מעדכנים.

3. מחזירים את `min`.

C#:

public static int MinOfMaxDigits(int[] arr)
{
    int min = MaxDigit(arr[0]);            // הספרה המקסימלית של האיבר הראשון
    for (int i = 1; i < arr.Length; i++)
    {
        int curMax = MaxDigit(arr[i]);
        if (curMax < min)
            min = curMax;
    }
    return min;
}

Java:

public static int minOfMaxDigits(int[] arr)
{
    int min = maxDigit(arr[0]);            // הספרה המקסימלית של האיבר הראשון
    for (int i = 1; i < arr.length; i++)
    {
        int curMax = maxDigit(arr[i]);
        if (curMax < min)
            min = curMax;
    }
    return min;
}

בדיקה מול הדוגמה:

איבר1283451971613
ספרה מקסימלית8596

הקטנה מבין 8,5,9,68, 5, 9, 6 היא 55.

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

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

א.

נתונה הפעולה `What` המקבלת שני מספרים שלמים חיוביים `num1` ו-`num2`:

C#:

public static bool What(int num1, int num2)
{
   if(num1 == num2) return false;
   while(num1 > 9 && num2 > 9)
   {
     num1 = num1 /10;
     num2 = num2/10;
   }
   return num1 == num2;
}

Java:

public static boolean what(int num1, int num2)
{
   if(num1 == num2) return false;
   while(num1 > 9 && num2 > 9)
   {
     num1 = num1 /10;
     num2 = num2/10;
   }
   return num1 == num2;
}
(1)

תנו דוגמה למספר שלם וחיובי `num` שעבורו זימון הפעולה `What(1234, num)` יחזיר ערך `true`.

(2)

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

(4 נקודות)
ב.

נתונה הפעולה `Secret` המקבלת שני מערכים המכילים מספרים שלמים חיוביים ומשתמשת בפעולה `What`:

C#:

public static bool Secret(int[] a, int[] b) {
    for (int i = 0; i < a.Length; i++) {
        bool flag = false;
        for (int k = 0; k < b.Length; k++) {
            if (What(a[i], b[k])) {
                flag = true;
            }
        }
        if (!flag) return false;
    }
    return true;
}

Java:

public static boolean secret(int[] a, int[] b) {
    for (int i = 0; i < a.length; i++) {
        boolean flag = false;
        for (int k = 0; k < b.length; k++) {
            if (what(a[i], b[k])) {
                flag = true;
            }
        }
        if (!flag) return false;
    }
    return true;
}
(1)

נתון מערך מספרים שלמים `a = {46, 127, 415, 104, 491, 371, 49}`

תנו דוגמה למערך `b` בעל מספר האיברים הקטן ביותר שעבורו זימון הפעולה `Secret(a, b)` יחזיר ערך `true`.

(2)

האם לכל זוג מערכים של מספרים שלמים חיוביים `a` ו-`b`, תוצאת זימון הפעולה `Secret(a, b)` תהיה זהה לתוצאת זימון הפעולה `Secret(b, a)`? הסבירו את תשובתכם.

(3)

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

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

סעיף א

(1)
תשובה:

למשל `num = 1000` (כל מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234).

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

עבור `num1 = 1234` נבחר מספר ארבע-ספרתי שמתחיל ב-1 ושונה מ-1234, למשל `num = 1000`.

מעקב אחר `What(1234, 1000)`:

שלב`num1``num2``num1 > 9 && num2 > 9`
התחלה12341000(`num1 == num2`? לא) `true`
סיבוב 1123100`true`
סיבוב 21210`true`
סיבוב 311`false`

בסוף `num1 == num2` (שניהם 1), ולכן מוחזר `true`.

תשובה: `num = 1000` (או כל מספר בין 1000 ל-1999 פרט ל-1234).

(2)
תשובה:

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

1. אם `num1 == num2` – מוחזר `false` מיד.

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

•אם למספרים אותו מספר ספרות – שניהם הופכים לחד-ספרתיים באותו סיבוב, ונשארות הספרות השמאליות שלהם. ההשוואה בודקת אם הספרות השמאליות שוות.

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

תשובה: הפעולה מחזירה `true` אם `num1` ו-`num2` שונים זה מזה, יש להם אותו מספר ספרות, והספרה השמאלית (הבכירה) שלהם זהה; אחרת היא מחזירה `false`.

סעיף ב

(1)
תשובה:

מערך בן 4 איברים, למשל `b = {40, 100, 400, 300}`.

הרעיון: `Secret(a, b)` מחזירה `true` רק אם לכל איבר `a[i]` יש איבר `b[k]` שעבורו `What(a[i], b[k])` מחזירה `true`, כלומר איבר שונה ממנו, עם אותו מספר ספרות ואותה ספרה שמאלית (לפי סעיף א.2).

1. נמיין את איברי `a` לקבוצות לפי (מספר ספרות, ספרה שמאלית):

קבוצהאיברים מ-`a`
דו-ספרתי שמתחיל ב-446, 49
תלת-ספרתי שמתחיל ב-1127, 104
תלת-ספרתי שמתחיל ב-4415, 491
תלת-ספרתי שמתחיל ב-3371

2. איבר של `b` יכול "לשרת" רק קבוצה אחת (יש לו מספר ספרות אחד וספרה שמאלית אחת), ולכן צריך לפחות 4 איברים.

3. לכל קבוצה בוחרים מספר שמתאים לה ושונה מכל איבריה: `40` (שונה מ-46 ומ-49), `100` (שונה מ-127 ומ-104), `400` (שונה מ-415 ומ-491), `300` (שונה מ-371).

בדיקה: לכל איבר של `a` נמצא איבר מתאים ב-`b`, ולכן כל הדגלים `flag` מקבלים `true` והפעולה מחזירה `true`.

תשובה: `b = {40, 100, 400, 300}` – 4 איברים (זה המינימום).

(2)
תשובה:

לא. למשל עבור `a = {10}`, `b = {11, 20}`: `Secret(a, b)` מחזירה `true` ו-`Secret(b, a)` מחזירה `false`.

הפעולה בודקת שלכל איבר של המערך הראשון יש "בן זוג" במערך השני – הבדיקה אינה סימטרית: `Secret(a, b)` לא בודקת דבר על איברי `b` שאין להם בן זוג ב-`a`.

דוגמה נגדית: `a = {10}`, `b = {11, 20}`.

1. `Secret(a, b)`: עבור 10 יש ב-`b` את 11 (שונה, דו-ספרתי, מתחיל ב-1), ולכן מוחזר `true`.

2. `Secret(b, a)`: עבור 11 יש ב-`a` את 10 – מתאים. עבור 20 – האיבר היחיד ב-`a` הוא 10, שמתחיל ב-1 ולא ב-2, ולכן `flag` נשאר `false` ומוחזר `false`.

תשובה: לא. התוצאות יכולות להיות שונות, כמו בדוגמה שלמעלה.

(3)
תשובה:

מחזירה `true` אם לכל איבר של `a` יש ב-`b` איבר שונה ממנו עם אותו מספר ספרות ואותה ספרה שמאלית; אחרת `false`.

1. הלולאה החיצונית עוברת על כל איבר `a[i]`.

2. הלולאה הפנימית מחפשת ב-`b` איבר שעבורו `What(a[i], b[k])` מחזירה `true`, ואם יש כזה – `flag` הופך ל-`true`.

3. אם לאיבר כלשהו של `a` לא נמצא איבר כזה – מוחזר `false` מיד. אם כל האיברים עברו – מוחזר `true`.

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

שאלה 4 · מחלקת מחשב נייד: בנאי ופעולות על מערך

מעבדת מחשבים החליטה למחשב את ניהול המחשבים הניידים המגיעים אליה לתיקון. לשם כך הוגדרה המחלקה `Laptop`. למחלקה התכונות הבאות:

•`string serialNum` (ב-Java: `String serialNum`) – מספר סידורי של המחשב;

•`string ownerName` (ב-Java: `String ownerName`) – שם בעל המחשב;

•`int ramSize` – זיכרון ה-RAM של המחשב (ב-GB);

•`bool isTouchScreen` (ב-Java: `boolean isTouchScreen`) – האם למחשב יש מסך מגע? (כן – `true`, לא – `false`);

•`bool isRepaired` (ב-Java: `boolean isRepaired`) – האם המחשב תוקן ומוכן לאיסוף? (כן – `true`, לא – `false`).

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

א.

כתבו במחלקה `Laptop` את הפעולה הבונה (`Constructor`) המקבלת כפרמטרים את המספר הסידורי ואת שם הבעלים בלבד. הפעולה תאתחל את שאר התכונות כך שהמחשב יהיה בעל זיכרון RAM של 8 GB, ללא מסך מגע, ואינו מוכן לאיסוף.

(3 נקודות)
ב.

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

(4 נקודות)
ג.

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

אם אין אף מחשב כזה (שמוכן לאיסוף וגם בעל מסך מגע), הפעולה תדפיס הודעה מתאימה.

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

סעיף א

תשובה:

בנאי שמציב את שני הפרמטרים, ובנוסף `ramSize = 8`, `isTouchScreen = false`, `isRepaired = false`.

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

1. `serialNum` ו-`ownerName` – מהפרמטרים.

2. זיכרון RAM של 8 GB – `ramSize = 8`.

3. ללא מסך מגע – `isTouchScreen = false`.

4. אינו מוכן לאיסוף – `isRepaired = false`.

C#:

public Laptop(string serialNum, string ownerName)
{
    this.serialNum = serialNum;
    this.ownerName = ownerName;
    this.ramSize = 8;              // זיכרון RAM של 8 GB
    this.isTouchScreen = false;    // ללא מסך מגע
    this.isRepaired = false;       // עדיין לא מוכן לאיסוף
}

Java:

public Laptop(String serialNum, String ownerName)
{
    this.serialNum = serialNum;
    this.ownerName = ownerName;
    this.ramSize = 8;              // זיכרון RAM של 8 GB
    this.isTouchScreen = false;    // ללא מסך מגע
    this.isRepaired = false;       // עדיין לא מוכן לאיסוף
}

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

סעיף ב

תשובה:

עוברים על המערך וסופרים את המחשבים שעבורם `GetIsTouchScreen()` הוא `true` וגם `GetRamSize() >= 8`; מחזירים את המונה.

הרעיון: ספירה בתנאי. הפעולה חיצונית למחלקה, ולכן ניגשים לתכונות דרך פעולות ה-Get (הנחנו שמותיהן `GetIsTouchScreen`, `GetRamSize`; ב-Java: `getIsTouchScreen`, `getRamSize`).

1. מאתחלים מונה `count = 0`.

2. עוברים על כל המחשבים במערך. אם למחשב יש מסך מגע וגם הזיכרון שלו לפחות 8 (כלומר `>= 8`) – מגדילים את המונה.

3. מחזירים את המונה.

C#:

public static int CountTouchBigRam(Laptop[] laptops)
{
    int count = 0;
    for (int i = 0; i < laptops.Length; i++)
    {
        if (laptops[i].GetIsTouchScreen() && laptops[i].GetRamSize() >= 8)
            count++;
    }
    return count;
}

Java:

public static int countTouchBigRam(Laptop[] laptops)
{
    int count = 0;
    for (int i = 0; i < laptops.length; i++)
    {
        if (laptops[i].getIsTouchScreen() && laptops[i].getRamSize() >= 8)
            count++;
    }
    return count;
}

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

סעיף ג

תשובה:

עוברים על המערך ומדפיסים `GetOwnerName()` של כל מחשב עם מסך מגע שתוקן; משתנה בוליאני `found` מסמן אם הודפס שם, ואם לא – מדפיסים הודעה.

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

1. מאתחלים `found = false`.

2. לכל מחשב: אם יש לו מסך מגע וגם הוא מוכן לאיסוף – מדפיסים את שם הבעלים ומציבים `found = true`.

3. אחרי הלולאה, אם `found` נשאר `false` – לא הודפס אף שם, ולכן מדפיסים הודעה מתאימה.

C#:

public static void PrintReadyTouch(Laptop[] laptops)
{
    bool found = false;      // האם נמצא לפחות מחשב אחד מתאים
    for (int i = 0; i < laptops.Length; i++)
    {
        if (laptops[i].GetIsTouchScreen() && laptops[i].GetIsRepaired())
        {
            Console.WriteLine(laptops[i].GetOwnerName());
            found = true;
        }
    }
    if (!found)
        Console.WriteLine("אין מחשב עם מסך מגע המוכן לאיסוף");
}

Java:

public static void printReadyTouch(Laptop[] laptops)
{
    boolean found = false;   // האם נמצא לפחות מחשב אחד מתאים
    for (int i = 0; i < laptops.length; i++)
    {
        if (laptops[i].getIsTouchScreen() && laptops[i].getIsRepaired())
        {
            System.out.println(laptops[i].getOwnerName());
            found = true;
        }
    }
    if (!found)
        System.out.println("אין מחשב עם מסך מגע המוכן לאיסוף");
}

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

שאלה 5 · דרגת אי-זוגיות, דרגת שיא ומערך מלא

א.

נתונה הגדרה הבאה:

•"דרגת האי-זוגיות" של מספר שלם היא כמות הספרות האי-זוגיות במספר.

לדוגמה:

"דרגת האי-זוגיות" של המספר 12347 היא 3.

"דרגת האי-זוגיות" של המספר 1860 היא 1.

"דרגת האי-זוגיות" של המספר 246 היא 0.

"דרגת האי-זוגיות" של המספר (‎-3145) היא 3.

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

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

C#:

public static int OddDegree(int num)

Java:

public static int oddDegree(int num)
(4 נקודות)
ב.

•"דרגת השיא" של מערך של מספרים שלמים היא "דרגת האי-זוגיות" הגבוהה ביותר שיש בו.

כתבו פעולה המקבלת מערך חד-ממדי ומחזירה את "דרגת השיא" שלו.

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

C#:

public static int PeekDegree(int[] arr)

Java:

public static int peekDegree(int[] arr)
(4 נקודות)
ג.

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

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

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

C#:

public static bool IsFullArray(int[] arr)

Java:

public static boolean isFullArray(int[] arr)
(7 נקודות)
◂ פתרון מלא לשאלה 5

סעיף א

תשובה:

הופכים מספר שלילי לחיובי, ואז סופרים את הספרות `dig` שעבורן `dig % 2 == 1` בעזרת `% 10` ו-`/ 10`.

הרעיון: מפרקים את המספר לספרות וסופרים את האי-זוגיות.

1. אם המספר שלילי – הופכים אותו לחיובי. הסימן אינו ספרה, ובלי ההיפוך `num % 10` של מספר שלילי מחזיר ערך שלילי והלולאה `while (num > 0)` לא תרוץ כלל.

2. כל עוד `num > 0`: לוקחים את ספרת האחדות `num % 10`; אם היא אי-זוגית (`dig % 2 == 1`) – מגדילים את המונה; מוחקים את הספרה (`num / 10`).

3. מחזירים את המונה. עבור 0 מוחזר 0 (אין ספרות אי-זוגיות).

C#:

public static int OddDegree(int num)
{
    if (num < 0)
        num = -num;              // הסימן לא משנה את הספרות
    int count = 0;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig % 2 == 1)
            count++;             // ספרה אי-זוגית
        num = num / 10;
    }
    return count;
}

Java:

public static int oddDegree(int num)
{
    if (num < 0)
        num = -num;              // הסימן לא משנה את הספרות
    int count = 0;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig % 2 == 1)
            count++;             // ספרה אי-זוגית
        num = num / 10;
    }
    return count;
}

בדיקה מול הדוגמאות: 12347 – הספרות האי-זוגיות 1, 3, 7, ולכן 3. 1860 – רק 1, ולכן 1. 246 – אין, ולכן 0. ‎-3145 – הופך ל-3145, הספרות 3, 1, 5, ולכן 3.

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

סעיף ב

תשובה:

חיפוש מקסימום על `OddDegree(arr[i])` לכל איברי המערך.

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

1. מאתחלים `max = 0` – דרגת אי-זוגיות אינה שלילית לעולם, ולכן 0 הוא ערך התחלתי בטוח.

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

3. מחזירים את `max`.

C#:

public static int PeekDegree(int[] arr)
{
    int max = 0;                         // דרגה היא תמיד לפחות 0
    for (int i = 0; i < arr.Length; i++)
    {
        int deg = OddDegree(arr[i]);
        if (deg > max)
            max = deg;
    }
    return max;
}

Java:

public static int peekDegree(int[] arr)
{
    int max = 0;                         // דרגה היא תמיד לפחות 0
    for (int i = 0; i < arr.length; i++)
    {
        int deg = oddDegree(arr[i]);
        if (deg > max)
            max = deg;
    }
    return max;
}

דוגמה: עבור `{12347, 1860, 246}` הדרגות הן 3,1,03, 1, 0, ולכן "דרגת השיא" היא 3.

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

סעיף ג

תשובה:

מחשבים `peak = PeekDegree(arr)`; אם אורך המערך שונה מ-`peak + 1` מחזירים `false`; אחרת סופרים במערך מונים בגודל `peak + 1` כמה פעמים מופיעה כל דרגה, ומחזירים `false` אם דרגה כלשהי מופיעה פעמיים, אחרת `true`.

הרעיון:

1. מחשבים את "דרגת השיא" `peak` בעזרת הפעולה מסעיף ב. הדרגות שצריכות להופיע הן 0,1,…,peak0, 1, \dots, peak – בסך הכול peak+1peak+1 דרגות, כל אחת בדיוק פעם אחת. לכן במערך מלא יש בדיוק peak+1peak+1 איברים, ואם האורך שונה – מחזירים `false` מיד.

2. כל איבר הוא בעל דרגה בין 0 ל-`peak` (כי `peak` היא הגבוהה ביותר). לכן אפשר להשתמש במערך מונים `count` בגודל `peak + 1`, שבו `count[d]` סופר כמה איברים בעלי דרגה `d`.

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

4. אם סיימנו: יש peak+1peak+1 איברים ואף דרגה לא חזרה, ולכן כל אחת מ-peak+1peak+1 הדרגות מופיעה בדיוק פעם אחת – מחזירים `true`.

סיבוכיות: O(n⋅d)O(n \cdot d), כאשר nn אורך המערך ו-dd מספר הספרות המרבי (חישוב הדרגות).

C#:

public static bool IsFullArray(int[] arr)
{
    int peak = PeekDegree(arr);
    if (arr.Length != peak + 1)
        return false;                    // חייב להיות איבר אחד בדיוק לכל דרגה 0..peak
    int[] count = new int[peak + 1];     // count[d] = כמה איברים בעלי דרגה d
    for (int i = 0; i < arr.Length; i++)
    {
        int deg = OddDegree(arr[i]);
        count[deg]++;
        if (count[deg] > 1)
            return false;                // דרגה שמופיעה פעמיים
    }
    return true;
}

Java:

public static boolean isFullArray(int[] arr)
{
    int peak = peekDegree(arr);
    if (arr.length != peak + 1)
        return false;                    // חייב להיות איבר אחד בדיוק לכל דרגה 0..peak
    int[] count = new int[peak + 1];     // count[d] = כמה איברים בעלי דרגה d
    for (int i = 0; i < arr.length; i++)
    {
        int deg = oddDegree(arr[i]);
        count[deg]++;
        if (count[deg] > 1)
            return false;                // דרגה שמופיעה פעמיים
    }
    return true;
}

דוגמאות:

•`{246, 12347, 1860, 13}`: הדרגות 0,3,1,20, 3, 1, 2, דרגת השיא 3, האורך 4=3+14 = 3+1 ואין חזרות – מוחזר `true`.

•`{246, 12347, 1860}`: דרגת השיא 3 אבל האורך 3 (חסרה דרגה 2) – מוחזר `false`.

•`{246, 1860, 13}`: הדרגות 0,1,20, 1, 2 – מוחזר `true`.

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

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

במערכת `"SmartHome"` כל מכשיר מקבל מזהה ייחודי (`string`; ב-Java: `String`) המורכב משם החדר, התו נקודתיים (`":"`) ושם מכשיר.

לדוגמה: `"KITCHEN:LIGHT"`, `"ROOM_2:TV"`, `"MICROWAVE:KITCHEN"`.

א.

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

•היא מכילה בדיוק פעם אחת את התו נקודתיים (`":"`);

•התו נקודתיים אינו מופיע בתחילת המחרוזת ואינו מופיע בסופה.

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

C#:

public static bool IsValidDevice(string deviceId)

Java:

public static boolean isValidDevice(String deviceId)
(4 נקודות)
ב.

כדי לייעל את צריכת החשמל, על המערכת לדעת אם שני מכשירים נמצאים באותו החדר.

כתבו פעולה המקבלת שתי מחרוזות `dev1` ו-`dev2` המייצגות מזהי מכשירים. הפעולה תבדוק אם שני המכשירים נמצאים באותו החדר. אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.

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

C#:

public static bool AreInSameRoom(string dev1, string dev2)

Java:

public static boolean areInSameRoom(String dev1, String dev2)

אפשר להניח שהמזהים תקינים.

(4 נקודות)
ג.

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

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

C#:

public static string[] GetDevicesInRoom(string[] allDevices,
                                        string roomName)

Java:

public static String[] args getDevicesInRoom(String[] allDevices,
                                        String roomName)

לדוגמה: עבור החדר `roomName = "KITCHEN"` מערך המכשירים `allDevices` הבא

`allDevices ={"KITCHEN:LIGHT" ,"ROOM_2:TV" ,"KITCHEN:MICROWAVE"}`

הפעולה תחזיר מערך חדש `{"LIGHT", "MICROWAVE"}`.

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

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

סעיף א

תשובה:

סופרים את התווים `':'`; אם המספר שונה מ-1 מוחזר `false`; אחרת מוחזר `true` רק אם התו הראשון והתו האחרון אינם `':'`.

הרעיון:

1. פעם אחת בדיוק: עוברים על המחרוזת וסופרים כמה פעמים מופיע התו `':'`. אם המונה שונה מ-1 – המזהה לא תקין.

2. לא בהתחלה ולא בסוף: אחרי שידוע שיש בדיוק נקודתיים אחד, בודקים שהתו במקום 0 והתו האחרון (מקום אורך פחות 1) אינם `':'`.

כאשר המונה שווה ל-1 המחרוזת בוודאי אינה ריקה, ולכן הגישה לתו הראשון ולתו האחרון בטוחה.

C#:

public static bool IsValidDevice(string deviceId)
{
    int count = 0;                       // מספר הנקודתיים במחרוזת
    for (int i = 0; i < deviceId.Length; i++)
    {
        if (deviceId[i] == ':')
            count++;
    }
    if (count != 1)
        return false;                    // אין נקודתיים, או שיש יותר מפעם אחת
    return deviceId[0] != ':' && deviceId[deviceId.Length - 1] != ':';
}

Java:

public static boolean isValidDevice(String deviceId)
{
    int count = 0;                       // מספר הנקודתיים במחרוזת
    for (int i = 0; i < deviceId.length(); i++)
    {
        if (deviceId.charAt(i) == ':')
            count++;
    }
    if (count != 1)
        return false;                    // אין נקודתיים, או שיש יותר מפעם אחת
    return deviceId.charAt(0) != ':' && deviceId.charAt(deviceId.length() - 1) != ':';
}

דוגמאות: `"KITCHEN:LIGHT"` – נקודתיים אחד באמצע, מוחזר `true`; `":TV"` – נקודתיים בהתחלה, `false`; `"A:B:C"` – פעמיים, `false`; `"TV"` – אין נקודתיים, `false`.

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

סעיף ב

תשובה:

גוזרים מכל מזהה את החלק שלפני `':'` (`Substring(0, IndexOf(':'))`) ומחזירים אם שני שמות החדרים שווים.

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

1. מוצאים את מקום הנקודתיים בכל מזהה בעזרת `IndexOf(':')` (ב-Java: `indexOf`).

2. גוזרים את תת-המחרוזת מתחילת המזהה עד הנקודתיים (לא כולל) – זה שם החדר.

3. משווים את שני שמות החדרים (ב-Java בעזרת `equals`, כי `==` משווה הפניות ולא תוכן).

שימו לב: לא מספיק לבדוק ש-`dev2` מתחיל ב-`room1`, כי למשל `"KITCHEN:TV"` ו-`"KITCHEN2:TV"` נמצאים בחדרים שונים. משווים את שם החדר המלא.

C#:

public static bool AreInSameRoom(string dev1, string dev2)
{
    string room1 = dev1.Substring(0, dev1.IndexOf(':'));   // שם החדר = החלק שלפני הנקודתיים
    string room2 = dev2.Substring(0, dev2.IndexOf(':'));
    return room1 == room2;
}

Java:

public static boolean areInSameRoom(String dev1, String dev2)
{
    String room1 = dev1.substring(0, dev1.indexOf(':'));   // שם החדר = החלק שלפני הנקודתיים
    String room2 = dev2.substring(0, dev2.indexOf(':'));
    return room1.equals(room2);
}

דוגמה: `"KITCHEN:LIGHT"` ו-`"KITCHEN:MICROWAVE"` – בשניהם החדר `"KITCHEN"`, מוחזר `true`; `"KITCHEN:LIGHT"` ו-`"ROOM_2:TV"` – מוחזר `false`.

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

סעיף ג

תשובה:

שני מעברים: בראשון סופרים את המזהים שהחלק שלפני `':'` בהם שווה ל-`roomName`, יוצרים מערך בגודל זה, ובשני מעתיקים אליו את החלק שאחרי `':'`; עבור הדוגמה מוחזר `{"LIGHT", "MICROWAVE"}`.

(בכותרת ה-Java המודפסת מופיעה המילה `args` בטעות; הכותרת התקינה היא `public static String[] getDevicesInRoom(String[] allDevices, String roomName)`.)

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

1. ספירה: לכל מזהה מוצאים את מקום הנקודתיים `pos`, גוזרים את שם החדר `Substring(0, pos)` ומשווים ל-`roomName`. סופרים כמה מזהים מתאימים – `count`.

2. יצירה: יוצרים מערך מחרוזות חדש בגודל `count`. אם אין מכשירים בחדר, `count = 0` ומתקבל מערך באורך 0, כנדרש.

3. העתקה: עוברים שוב על המזהים, ולכל מזהה מתאים מעתיקים את שם המכשיר – החלק שאחרי הנקודתיים, `Substring(pos + 1)` – למקום הפנוי הבא `j` במערך החדש.

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

סיבוכיות: O(n⋅L)O(n \cdot L), כאשר nn מספר המזהים ו-LL אורך מזהה.

C#:

public static string[] GetDevicesInRoom(string[] allDevices, string roomName)
{
    // מעבר ראשון: ספירת המכשירים שבחדר, כדי לדעת את גודל המערך החדש
    int count = 0;
    for (int i = 0; i < allDevices.Length; i++)
    {
        int pos = allDevices[i].IndexOf(':');
        if (allDevices[i].Substring(0, pos) == roomName)
            count++;
    }
    // מעבר שני: העתקת שמות המכשירים (החלק שאחרי הנקודתיים)
    string[] result = new string[count];
    int j = 0;                                   // המקום הפנוי הבא ב-result
    for (int i = 0; i < allDevices.Length; i++)
    {
        int pos = allDevices[i].IndexOf(':');
        if (allDevices[i].Substring(0, pos) == roomName)
        {
            result[j] = allDevices[i].Substring(pos + 1);
            j++;
        }
    }
    return result;
}

Java:

public static String[] getDevicesInRoom(String[] allDevices, String roomName)
{
    // מעבר ראשון: ספירת המכשירים שבחדר, כדי לדעת את גודל המערך החדש
    int count = 0;
    for (int i = 0; i < allDevices.length; i++)
    {
        int pos = allDevices[i].indexOf(':');
        if (allDevices[i].substring(0, pos).equals(roomName))
            count++;
    }
    // מעבר שני: העתקת שמות המכשירים (החלק שאחרי הנקודתיים)
    String[] result = new String[count];
    int j = 0;                                   // המקום הפנוי הבא ב-result
    for (int i = 0; i < allDevices.length; i++)
    {
        int pos = allDevices[i].indexOf(':');
        if (allDevices[i].substring(0, pos).equals(roomName))
        {
            result[j] = allDevices[i].substring(pos + 1);
            j++;
        }
    }
    return result;
}

מעקב על הדוגמה:

מזההשם החדרמתאים ל-`"KITCHEN"`?שם המכשיר
`"KITCHEN:LIGHT"``KITCHEN`כן`LIGHT`
`"ROOM_2:TV"``ROOM_2`לא–
`"KITCHEN:MICROWAVE"``KITCHEN`כן`MICROWAVE`

`count = 2`, והמערך המוחזר הוא `{"LIGHT", "MICROWAVE"}`.

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

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

נתונה המחלקה `DigitInfo`:

C#:

class DigitInfo {
    private int dig1;
    private int dig2;

    public DigitInfo(int num) {
        if (num < 0) num = num * (-1);
        int dig = num % 10;
        this.dig1 = dig;
        this.dig2 = dig;
        num = num / 10;
        while (num > 0) {
            dig = num % 10;
            if (dig < this.dig1)
                this.dig1 = dig;
            else if (dig > this.dig2)
                this.dig2 = dig;
            num = num / 10;
        }
    }

    public override string ToString() {
        return this.dig1 + "," + this.dig2;
    }

    public int Combine() {
        return this.dig1 + this.dig2;
    }
}

Java:

class DigitInfo {
    private int dig1;
    private int dig2;

    public DigitInfo(int num) {
        if (num < 0) num = num * (-1);
        int dig = num % 10;
        this.dig1 = dig;
        this.dig2 = dig;
        num = num / 10;
        while (num > 0) {
            dig = num % 10;
            if (dig < this.dig1)
                this.dig1 = dig;
            else if (dig > this.dig2)
                this.dig2 = dig;
            num = num / 10;
        }
    }

    public String toString() {
        return this.dig1 + "," + this.dig2;
    }

    public int combine() {
        return this.dig1 + this.dig2;
    }
}
א.

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

C#:

DigitInfo info = new DigitInfo(48291);
Console.WriteLine(info);
Console.WriteLine(info.Combine());

Java:

DigitInfo info = new DigitInfo(48291);
System.out.println(info);
System.out.println(info.combine());
(5 נקודות)
ב.

מהו הערך הגדול ביותר ומהו הערך הקטן ביותר שיכולה להחזיר הפעולה `Combine()`?

(2 נקודות)

נתונה הפעולה `Mystery`:

C#:

public static void Mystery(int[] arr) {
    DigitInfo temp1 = new DigitInfo(arr[0]);
    DigitInfo temp2 = new DigitInfo(arr[0]);
    int ind1 = 0;
    int ind2 = 0;

    DigitInfo cur;
    for (int i = 1; i < arr.Length; i++) {
        cur = new DigitInfo(arr[i]);
        if (cur.Combine() > temp1.Combine()) {
            temp2 = temp1;
            temp1 = cur;
            ind2 = ind1;
            ind1 = i;
        } else {
            if (cur.Combine() > temp2.Combine()) {
                temp2 = cur;
                ind2 = i;
            }
        }
    }
     Console.WriteLine(arr[ind1]+" "+arr[ind2]);
}

Java:

public static void mystery(int[] arr) {
    DigitInfo temp1 = new DigitInfo(arr[0]);
    DigitInfo temp2 = new DigitInfo(arr[0]);
    int ind1 = 0;
    int ind2 = 0;

    DigitInfo cur;
    for (int i = 1; i < arr.length; i++) {
        cur = new DigitInfo(arr[i]);
        if (cur.combine() > temp1.combine()) {
            temp2 = temp1;
            temp1 = cur;
            ind2 = ind1;
            ind1 = i;
        } else {
            if (cur.combine() > temp2.combine()) {
                temp2 = cur;
                ind2 = i;
            }
        }
    }
     System.out.println(arr[ind1]+" "+arr[ind2]);
}
ג.

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

C#:

int[] a = {3458,45, 7341, 6, 13579, 86 };
Mystery(a);

Java:

int[] a = {3458,45, 7341, 6, 13579, 86 };
mystery(a);
(8 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

תשובה:

הפלט: `1,9` ובשורה הבאה `10`.

מה עושה הבנאי: `dig1` ו-`dig2` מאותחלים בספרת האחדות. אחר כך, לכל ספרה נוספת: אם היא קטנה מ-`dig1` היא נשמרת ב-`dig1`, ואם היא גדולה מ-`dig2` היא נשמרת ב-`dig2`. כך `dig1` היא הספרה הקטנה ביותר ו-`dig2` הספרה הגדולה ביותר במספר.

מעקב אחר `new DigitInfo(48291)`:

שלב`num``dig``dig1``dig2`
אתחול4829111
סיבוב 1482919
סיבוב 248219
סיבוב 34819
סיבוב 40419

(בעמודת `num` מופיע הערך אחרי החלוקה ב-10 בסוף השלב.)

1. הדפסת העצם `info` מפעילה את `ToString` (ב-Java: `toString`), שמחזירה `dig1 + "," + dig2`, כלומר `1,9`.

2. `Combine` מחזירה 1+9=101+9=10.

תשובה: יודפס

1,9
10

סעיף ב

תשובה:

הגדול ביותר 18, הקטן ביותר 0.

`Combine` מחזירה את סכום הספרה הקטנה ביותר והספרה הגדולה ביותר של המספר (בערכו המוחלט). כל ספרה היא בין 0 ל-9.

1. המקסימום: 9+9=189+9=18 – מתקבל כשהספרה הקטנה ביותר היא 9, כלומר כל הספרות הן 9 (למשל 9, 99, ‎-999).

2. המינימום: 0+0=00+0=0 – מתקבל רק כשגם הספרה הגדולה ביותר היא 0, כלומר עבור המספר 0.

(מקרה קצה טכני בלבד: עבור הערך השלילי הקטן ביותר של `int`, הכפלה ב-(−1)(-1) גולשת וחוזרת לאותו ערך שלילי, והפעולה תחזיר −16-16. למספרים רגילים התחום הוא 0 עד 18.)

תשובה: הערך הגדול ביותר הוא 18 והקטן ביותר הוא 0.

סעיף ג

תשובה:

יודפס `86 6`.

הרעיון של הפעולה: `temp1` שומר את העצם עם ערך `Combine` הגדול ביותר עד כה (ומקומו ב-`ind1`), ו-`temp2` את השני בגודלו (מקומו ב-`ind2`). כשמגיע ערך גדול מהמקסימום – המקסימום הישן "יורד" למקום השני.

1. ערכי `Combine` של האיברים (ספרה קטנה + ספרה גדולה):

מקום012345
איבר345845734161357986
`dig1,dig2`3,84,51,76,61,96,8
`Combine`1198121014

2. מעקב אחר הלולאה (בהתחלה `temp1` ו-`temp2` שניהם של 3458, כלומר 11, ו-`ind1 = ind2 = 0`):

סיבוב `i``cur.Combine()`השוואה`temp1.Combine()``temp2.Combine()``ind1``ind2`
התחלה––111100
199>119>11? לא; 9>119>11? לא111100
288>118>11? לא; 8>118>11? לא111100
31212>1112>11? כן121130
41010>1210>12? לא; 10>1110>11? לא121130
51414>1214>12? כן141253

3. בסוף `ind1 = 5` ו-`ind2 = 3`, ומודפס `arr[5] + " " + arr[3]`.

תשובה: יודפס `86 6`.

שאלה 8 · פסגות במערך דו-ממדי

הגדרה:

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

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

•תא פנימי במערך נקרא "פסגה" אם הערך המאוחסן בו גדול מכל הערכים שבשמונת שכניו (כלומר, התאים הסמוכים לו).

לדוגמה:

•התא במיקום (1,1) הוא "פסגה" כיוון שערכו (10) גדול מכל שכניו (המסומנים באפור).

•גם התא במיקום (3,2) הוא "פסגה" (ערכו 21).

•גם התא (1,4) הוא "פסגה".

א.

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום איבר במערך `row` (שורה) ו-`col` (עמודה). הפעולה תבדוק אם האיבר במיקום זה `arr[row, col]` (ב-Java: `arr[row][col]`) הוא "פסגה". אם כן – הפעולה תחזיר `true`, ואם לא – הפעולה תחזיר `false`.

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

C#:

public static bool IsPeak(int[,] arr, int row, int col)

Java:

public static boolean isPeak(int[][] arr, int row, int col)
(5 נקודות)
ב.

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr`. הפעולה תחזיר מערך חד-ממדי המכיל את הערכים של כל "הפסגות" הקיימות במערך `arr`. אם אין שום "פסגה" במערך, הפעולה תחזיר `null`.

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

C#:

public static int[] GetPeaksArray(int[,] arr)

Java:

public static int[] getPeaksArray(int[][] arr)
(10 נקודות)
ג.

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

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

סעיף א

תשובה:

אם התא אינו פנימי (`row` לא בין 1 לשורה הלפני אחרונה, או `col` לא בין 1 לעמודה הלפני אחרונה) מוחזר `false`; אחרת עוברים על 8 השכנים ומחזירים `false` אם אחד מהם גדול מהתא או שווה לו, אחרת `true`.

הרעיון:

1. תא פנימי: "פסגה" מוגדרת רק לתא פנימי. לכן אם `row` הוא 0 או השורה האחרונה, או `col` הוא 0 או העמודה האחרונה (או מחוץ לתחום) – מחזירים `false`. תנאי זה גם מבטיח שלא ניגש מחוץ לגבולות המערך כשנבדוק שכנים.

2. שמונת השכנים: השכנים נמצאים בשורות `row-1` עד `row+1` ובעמודות `col-1` עד `col+1`, פרט לתא עצמו. עוברים עליהם בלולאה כפולה ומדלגים על התא `(row, col)`.

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

4. אם כל השכנים קטנים ממנו – מחזירים `true`.

C#:

public static bool IsPeak(int[,] arr, int row, int col)
{
    int rows = arr.GetLength(0);
    int cols = arr.GetLength(1);
    // תא במסגרת (או מחוץ למערך) אינו תא פנימי ולכן אינו "פסגה"
    if (row < 1 || row > rows - 2 || col < 1 || col > cols - 2)
        return false;
    for (int i = row - 1; i <= row + 1; i++)
    {
        for (int j = col - 1; j <= col + 1; j++)
        {
            if ((i != row || j != col) && arr[i, j] >= arr[row, col])
                return false;            // שכן שגדול מהתא או שווה לו
        }
    }
    return true;
}

Java:

public static boolean isPeak(int[][] arr, int row, int col)
{
    int rows = arr.length;
    int cols = arr[0].length;
    // תא במסגרת (או מחוץ למערך) אינו תא פנימי ולכן אינו "פסגה"
    if (row < 1 || row > rows - 2 || col < 1 || col > cols - 2)
        return false;
    for (int i = row - 1; i <= row + 1; i++)
    {
        for (int j = col - 1; j <= col + 1; j++)
        {
            if ((i != row || j != col) && arr[i][j] >= arr[row][col])
                return false;            // שכן שגדול מהתא או שווה לו
        }
    }
    return true;
}

בדיקה מול הדוגמה: התא (1,1) ערכו 10, ושכניו 5,4,1,1,7,6,1,75, 4, 1, 1, 7, 6, 1, 7 – כולם קטנים מ-10, לכן מוחזר `true`. התא (2,3) ערכו 10, אבל שכנו (1,4) ערכו 123, לכן מוחזר `false`. התא (0,0) נמצא במסגרת – מוחזר `false`.

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

סעיף ב

תשובה:

שני מעברים על התאים הפנימיים בעזרת `IsPeak`: הראשון סופר את הפסגות (אם 0 – מוחזר `null`), השני ממלא מערך בגודל זה בערכי הפסגות; עבור המערך שבאיור מוחזר `{10, 123, 21}`.

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

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

2. אם לא נמצאה אף פסגה – מחזירים `null`.

3. מילוי: יוצרים מערך בגודל המונה, עוברים שוב על התאים הפנימיים ומעתיקים את ערכי הפסגות למקום הפנוי הבא `k`.

C#:

public static int[] GetPeaksArray(int[,] arr)
{
    int rows = arr.GetLength(0);
    int cols = arr.GetLength(1);
    // מעבר ראשון: ספירת הפסגות (רק תאים פנימיים)
    int count = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (IsPeak(arr, i, j))
                count++;
    if (count == 0)
        return null;                     // אין אף פסגה
    // מעבר שני: העתקת ערכי הפסגות למערך החדש
    int[] peaks = new int[count];
    int k = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (IsPeak(arr, i, j))
            {
                peaks[k] = arr[i, j];
                k++;
            }
    return peaks;
}

Java:

public static int[] getPeaksArray(int[][] arr)
{
    int rows = arr.length;
    int cols = arr[0].length;
    // מעבר ראשון: ספירת הפסגות (רק תאים פנימיים)
    int count = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (isPeak(arr, i, j))
                count++;
    if (count == 0)
        return null;                     // אין אף פסגה
    // מעבר שני: העתקת ערכי הפסגות למערך החדש
    int[] peaks = new int[count];
    int k = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (isPeak(arr, i, j))
            {
                peaks[k] = arr[i][j];
                k++;
            }
    return peaks;
}

דוגמה: עבור המערך שבאיור, הפסגות לפי סדר המעבר (שורה אחר שורה) הן (1,1), (1,4), (3,2), ולכן מוחזר `{10, 123, 21}`.

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

סעיף ג

תשובה:

`IsPeak` – O(1)O(1); `GetPeaksArray` – O(n⋅m)O(n \cdot m), כאשר nn מספר השורות ו-mm מספר העמודות.

1. `IsPeak`: בודקת לכל היותר 9 תאים (3 שורות על 3 עמודות) – מספר קבוע של פעולות שאינו תלוי בגודל המערך. לכן הסיבוכיות היא O(1)O(1).

2. `GetPeaksArray`: עוברת פעמיים על התאים הפנימיים – כ-(n−2)(m−2)(n-2)(m-2) תאים בכל מעבר – ולכל תא מזמנת את `IsPeak`, שעולה O(1)O(1). סך הכול כ-2(n−2)(m−2)⋅O(1)2(n-2)(m-2) \cdot O(1), כלומר O(n⋅m)O(n \cdot m), כאשר nn מספר השורות ו-mm מספר העמודות (ליניארי במספר התאים במערך).

תשובה: `IsPeak` – O(1)O(1); `GetPeaksArray` – O(n⋅m)O(n \cdot m).

שאלה 9 · קווי אוטובוס: זמן, מסלול ומערכת קווים

חברת "דן" מעוניינת למחשב את שירותי המודיעין שלה עבור קווי האוטובוס בעיר. לצורך כך הוגדרו שלוש מחלקות: `Time`, `BusRoute` ו-`CityTransport`.

המחלקה `Time` מייצגת נקודת זמן לפי מספר שעות ומספר דקות.

public class Time{
    private int hour;
    private int minute;

במחלקה הוגדרו שתי פעולות בונות:

// הפעולה מקבלת שעה h ודקה m
public Time(int h, int m){
  this.hour = h;
  this.minute = m;
}

// הפעולה מקבלת מספר דקות totalMin שעברו מחצות
public Time(int totalMin){
  this.hour = totalMin / 60;
  this.minute = totalMin % 60;
}

לדוגמה: אם עברו 210 דקות נקודת הזמן הנוכחית היא 3:30.

במחלקה `Time` הוגדרו פעולות Get (ב-Java: get) וגם פעולה `minFromMidnight` המחזירה את מספר הדקות שעברו מחצות (0:00). אין צורך לממש אותן!

א.

כתבו במחלקה `Time` את הפעולה `Add` (ב-Java: `add`) המקבלת את המספר השלם החיובי `minToAdd`. הפעולה תחזיר אובייקט חדש מסוג `Time` המייצג את נקודת הזמן לאחר הוספת `minToAdd` דקות לזמן הנוכחי.

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

C#:

public Time Add(int minToAdd)

Java:

public Time add(int minToAdd)

לדוגמה, אם האובייקט הנוכחי הוא 8:30 והפעולה קיבלה 45, יוחזר אובייקט חדש המייצג את נקודת הזמן 9:15.

(4 נקודות)
ב.

המחלקה `BusRoute` מייצגת מסלול של קו אוטובוס. תכונות המחלקה:

•`lineNo` – מספר קו (למשל: `"61"`) – מטיפוס מחרוזת, `string` (ב-Java: `String`);

•`stops` – מערך השמות של תחנות העצירה, מסלול – מטיפוס מערך מחרוזות, `string[]` (ב-Java: `String[]`);

•`durations` – מערך מספרים שלמים – `int[]`. הערך `k` במערך מציין את מספר הדקות הדרושות לאוטובוס כדי להגיע מתחנה `k` לתחנה `k+1`.

לדוגמה:

אם המערך `stops` הוא:

מקום k01234
stops[k]עמידרקניון איילוןבורסהמיניסטור לונדוןכרמלית

והמערך `durations` הוא:

k0123
durations[k]1215108

האוטובוס נוסע 12 דקות מעמידר לקניון איילון, 15 דקות מקניון איילון לבורסה, 10 דקות מהבורסה למיניסטור לונדון, 8 דקות ממיניסטור לונדון לכרמלית.

במחלקה `BusRoute` הוגדרו פעולות Get (ב-Java: get). אין צורך לממש אותן!

כתבו במחלקה `BusRoute` את שתי הפעולות הבאות:

(1)

פעולה בוליאנית המקבלת שמות של שתי תחנות `st1` ו-`st2` ובודקת האם ניתן להגיע מ-`st1` ל-`st2` באמצעות קו זה (כלומר, ששתיהן קיימות במערך תחנות ו-`st2` מופיעה אחרי `st1`).

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

C#:

public bool IsRoutePossible(string st1, string st2)

Java:

public boolean isRoutePossible(String st1, String st2)
(2)

פעולה המקבלת שם של תחנת יעד `stopName` וזמן יציאה למסלול `startTime`. הפעולה תחזיר את זמן ההגעה לתחנה זו. אפשר להניח שהתחנה `stopName` קיימת במסלול.

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

C#:

public Time GetArrivalTime(Time startTime, string stopName)

Java:

public Time getArrivalTime(Time startTime, String stopName)
(8 נקודות)
ג.

המחלקה `CityTransport` מייצגת מערכת הקווים העירונית. למחלקה תכונה אחת:

•`BusRoute[] routes` – מערך של עצמים מסוג קו אוטובוס

כתבו במחלקה `CityTransport` את הפעולה המקבלת תחנת מוצא ותחנת יעד. הפעולה תדפיס מספרי הקווים (`lineNo`) המאפשרים נסיעה מתחנת מוצא לתחנת יעד.

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

C#:

public void PrintRelevantLines(string origin, string destination)

Java:

public void printRelevantLines(String origin, String destination)
(5 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

מחשבים `total = minFromMidnight() + minToAdd` (ומצמצמים ב-`% 1440` למעבר חצות) ומחזירים `new Time(total)`; עבור 8:30 ו-45 מתקבל 9:15.

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

1. מחשבים כמה דקות עברו מחצות עד הזמן הנוכחי – `minFromMidnight()` – ומוסיפים את `minToAdd`.

2. יוצרים עצם חדש בעזרת הבנאי שמקבל מספר דקות מחצות; הבנאי עצמו מפרק אותו לשעות (`/ 60`) ולדקות (`% 60`).

3. אם הסכום עובר את חצות (1440 דקות ביממה), מצמצמים אותו בעזרת `% (24 * 60)` כדי שהשעה תהיה בין 0 ל-23. (השאלה לא מחייבת זאת, אבל כך השעה נשארת תקינה.)

העצם הנוכחי אינו משתנה – מוחזר עצם חדש, כנדרש.

C#:

public Time Add(int minToAdd)
{
    int total = this.minFromMidnight() + minToAdd;   // דקות מחצות עד הזמן החדש
    total = total % (24 * 60);                      // מעבר חצות מתחיל יום חדש
    return new Time(total);
}

Java:

public Time add(int minToAdd)
{
    int total = this.minFromMidnight() + minToAdd;   // דקות מחצות עד הזמן החדש
    total = total % (24 * 60);                      // מעבר חצות מתחיל יום חדש
    return new Time(total);
}

בדיקה מול הדוגמה: 8:30 הוא 8⋅60+30=5108 \cdot 60 + 30 = 510 דקות מחצות. 510+45=555510 + 45 = 555, ו-555/60=9555 / 60 = 9, 555%60=15555 \% 60 = 15, כלומר 9:15.

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

סעיף ב

(1)
תשובה:

מוצאים את המיקומים `ind1`, `ind2` של שתי התחנות במערך `stops` (‎-1 אם לא נמצאה) ומחזירים `ind1 != -1 && ind2 != -1 && ind1 < ind2`.

הרעיון: האוטובוס נוסע רק בכיוון המסלול – מתחנה `k` לתחנה `k+1`. לכן אפשר להגיע מ-`st1` ל-`st2` רק אם שתיהן במסלול ו-`st2` נמצאת אחרי `st1` במערך.

1. מאתחלים `ind1 = -1` ו-`ind2 = -1` (סימן ל"לא נמצאה").

2. עוברים על מערך התחנות ושומרים את מיקום `st1` ב-`ind1` ואת מיקום `st2` ב-`ind2`. (ב-Java משווים מחרוזות עם `equals`.)

3. מחזירים `true` רק אם שתי התחנות נמצאו וגם `ind1 < ind2`. עבור `st1 == st2` מתקבל `ind1 == ind2`, ולכן מוחזר `false` – אין נסיעה מתחנה לעצמה.

הפעולה נכתבת בתוך המחלקה, ולכן ניגשים ישירות לתכונה `stops`.

C#:

public bool IsRoutePossible(string st1, string st2)
{
    int ind1 = -1;   // מיקום st1 במסלול
    int ind2 = -1;   // מיקום st2 במסלול
    for (int i = 0; i < this.stops.Length; i++)
    {
        if (this.stops[i] == st1)
            ind1 = i;
        if (this.stops[i] == st2)
            ind2 = i;
    }
    return ind1 != -1 && ind2 != -1 && ind1 < ind2;
}

Java:

public boolean isRoutePossible(String st1, String st2)
{
    int ind1 = -1;   // מיקום st1 במסלול
    int ind2 = -1;   // מיקום st2 במסלול
    for (int i = 0; i < this.stops.length; i++)
    {
        if (this.stops[i].equals(st1))
            ind1 = i;
        if (this.stops[i].equals(st2))
            ind2 = i;
    }
    return ind1 != -1 && ind2 != -1 && ind1 < ind2;
}

דוגמה: עבור המסלול בשאלה, `IsRoutePossible("עמידר", "בורסה")` מחזירה `true` (מקום 0 לפני מקום 2), ו-`IsRoutePossible("בורסה", "עמידר")` מחזירה `false`.

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

(2)
תשובה:

סוכמים את `durations[0]` עד `durations[k-1]`, כאשר `k` מיקום `stopName`, ומחזירים `startTime.Add(sum)`; למשל יציאה ב-8:00 לבורסה – 12+15=2712+15=27 דקות, הגעה ב-8:27.

הרעיון: האוטובוס יוצא מהתחנה הראשונה (מקום 0) בזמן `startTime`. כדי להגיע לתחנה במקום `k` הוא עובר את הקטעים 0→10 \to 1, 1→21 \to 2, ..., (k−1)→k(k-1) \to k, ולכן זמן הנסיעה הוא `durations[0] + ... + durations[k-1]`.

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

2. כל עוד התחנה במקום `k` אינה `stopName` – מוסיפים ל-`sum` את זמן הקטע `durations[k]` ומתקדמים לתחנה הבאה. מכיוון שהתחנה קיימת במסלול, הלולאה תיעצר.

3. מחזירים את זמן היציאה ועוד `sum` דקות, בעזרת הפעולה `Add` מסעיף א. אם `stopName` היא התחנה הראשונה, `sum = 0` ומוחזר זמן שווה לזמן היציאה.

C#:

public Time GetArrivalTime(Time startTime, string stopName)
{
    int sum = 0;     // סכום דקות הנסיעה מתחנת המוצא
    int k = 0;
    while (this.stops[k] != stopName)
    {
        sum += this.durations[k];   // זמן הנסיעה מתחנה k לתחנה k+1
        k++;
    }
    return startTime.Add(sum);
}

Java:

public Time getArrivalTime(Time startTime, String stopName)
{
    int sum = 0;     // סכום דקות הנסיעה מתחנת המוצא
    int k = 0;
    while (!this.stops[k].equals(stopName))
    {
        sum += this.durations[k];   // זמן הנסיעה מתחנה k לתחנה k+1
        k++;
    }
    return startTime.add(sum);
}

דוגמה: יציאה ב-8:00 ותחנת יעד "בורסה" (מקום 2): sum=12+15=27sum = 12 + 15 = 27, ולכן זמן ההגעה הוא 8:27. לכרמלית (מקום 4): 12+15+10+8=4512+15+10+8 = 45, הגעה ב-8:45.

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

סעיף ג

תשובה:

עוברים על המערך `routes`, ולכל קו שעבורו `IsRoutePossible(origin, destination)` מחזירה `true` מדפיסים `GetLineNo()`.

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

1. לכל קו `routes[i]` מזמנים `IsRoutePossible(origin, destination)`.

2. אם הוחזר `true` – מדפיסים את מספר הקו. התכונה `lineNo` פרטית במחלקה `BusRoute`, ולכן ניגשים אליה דרך פעולת ה-Get (הנחנו ששמה `GetLineNo`; ב-Java: `getLineNo`).

C#:

public void PrintRelevantLines(string origin, string destination)
{
    for (int i = 0; i < this.routes.Length; i++)
    {
        if (this.routes[i].IsRoutePossible(origin, destination))
            Console.WriteLine(this.routes[i].GetLineNo());
    }
}

Java:

public void printRelevantLines(String origin, String destination)
{
    for (int i = 0; i < this.routes.length; i++)
    {
        if (this.routes[i].isRoutePossible(origin, destination))
            System.out.println(this.routes[i].getLineNo());
    }
}

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

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

נתונה הפעולה `What` המקבלת מספר שלם חיובי `n`:

C#:

public static bool What(int n) {
    if (n < 10) return true;
    return What(n / 10, n % 10);
}
private static bool What(int n, int k) {
    if (n == 0) return true;
    if (n % 10 <= k) return false;
    return What(n / 10, n % 10);
}

Java:

public static boolean what(int n) {
    if (n < 10) return true;
    return what(n / 10, n % 10);
}
private static boolean what(int n, int k) {
    if (n == 0) return true;
    if (n % 10 <= k) return false;
    return what(n / 10, n % 10);
}
א.
(1)

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

(2)

תנו דוגמה למספר תלת-ספרתי `n` שעבורו תוצאת זימון הפעולה `What(n)` תהיה `true`.

(3)

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

(6 נקודות)

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

C#:

public static void Secret(int[] a) {
          Secret(a, 0, a.Length-1);
}
private static void Secret(int[] a, int low, int high) {
    if (low < high) {
        if (What(a[low])) {
            Secret(a, low + 1, high);
        } else if (!What(a[high])) {
            Secret(a, low, high - 1);
        } else {
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
            Secret(a, low + 1, high - 1);
        }
    }
}

Java:

public static void secret(int[] a) {
          secret(a, 0, a.length-1);
}
private static void secret(int[] a, int low, int high) {
    if (low < high) {
        if (what(a[low])) {
            secret(a, low + 1, high);
        } else if (!what(a[high])) {
            secret(a, low, high - 1);
        } else {
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
            secret(a, low + 1, high - 1);
        }
    }
}
ב.
(1)

עקבו אחרי זימון הפעולה `Secret(a)` עבור המערך הבא:

`int[] a = {17, 863, 19, 542, 123,542};`

רשמו מה תהיה התוצאה של הזימון. יש להראות מעקב.

(2)

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

(3)

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

(4)

מה מבצעת הפעולה `Secret` באופן כללי עבור מערך של מספרים שלמים חיוביים?

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

סעיף א

(1)
תשובה:

`true`.

הפעולה החיצונית מעבירה לפעולת העזר את המספר בלי ספרת האחדות (`n / 10`) ואת ספרת האחדות (`n % 10`) בתור `k`. פעולת העזר בודקת שספרת האחדות של `n` גדולה מ-`k` (הספרה שהייתה מימינה), וממשיכה שמאלה.

מעקב:

זימון`n``k``n == 0`?`n % 10``n % 10 <= k`?הזימון הבא
`What(8652)`8652–(n<10n<10? לא)––`What(865, 2)`
`What(865, 2)`8652לא55≤25 \le 2? לא`What(86, 5)`
`What(86, 5)`865לא66≤56 \le 5? לא`What(8, 6)`
`What(8, 6)`86לא88≤68 \le 6? לא`What(0, 8)`
`What(0, 8)`08כן – מוחזר `true`–––

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

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

(2)
תשובה:

למשל `n = 321`.

לפי המעקב בסעיף 1, הפעולה מחזירה `true` כשכל ספרה גדולה ממש מהספרה שמימינה. נבחר מספר תלת-ספרתי שספרותיו יורדות משמאל לימין: `321`.

בדיקה: `What(321)` → `What(32, 1)`: 2≤12 \le 1? לא → `What(3, 2)`: 3≤23 \le 2? לא → `What(0, 3)` → `true`.

תשובה: `n = 321` (וגם למשל 210, 975, 863).

(3)
תשובה:

מחזירה `true` אם ספרות `n` יורדות ממש משמאל לימין (כל ספרה גדולה מהספרה שמימינה), אחרת `false`; מספר חד-ספרתי מחזיר `true`.

1. מספר חד-ספרתי – מוחזר `true` מיד.

2. אחרת פעולת העזר משווה כל פעם ספרה לספרה שמימינה (`k`): אם הספרה השמאלית קטנה או שווה ל-`k` – מוחזר `false`. אם עברנו את כל הספרות (`n == 0`) בלי כישלון – מוחזר `true`.

למשל `What(123)` מחזירה `false` (כבר 2≤32 \le 3), ו-`What(8662)` מחזירה `false` (כי 6≤66 \le 6).

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

סעיף ב

(1)
תשובה:

המערך הופך ל-`{542, 863, 542, 19, 123, 17}`.

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

1. ערכי `What` לאיברים (לפי סעיף א.3):

איבר1786319542123542
ספרות יורדות?לא (1<71<7)כןלאכןלאכן
`What``false``true``false``true``false``true`

2. מעקב אחר הזימונים:

זימון`low``high``What(a[low])``What(a[high])`פעולההמערך אחרי הפעולה
105`What(17)=false``What(542)=true`החלפה של `a[0]` ו-`a[5]``{542, 863, 19, 542, 123, 17}`
214`What(863)=true`–`low+1`ללא שינוי
324`What(19)=false``What(123)=false``high-1`ללא שינוי
423`What(19)=false``What(542)=true`החלפה של `a[2]` ו-`a[3]``{542, 863, 542, 19, 123, 17}`
532––low<highlow < high לא מתקיים – עצירה–

תשובה: אחרי הזימון המערך הוא `{542, 863, 542, 19, 123, 17}`.

(2)
תשובה:

למשל `b = {321, 432, 543, 654, 765}` (כל האיברים בעלי ספרות יורדות).

החלפה מתבצעת רק כשמשמאל יש איבר שעבורו `What` מחזירה `false` ומימין איבר שעבורו היא מחזירה `true`. אם כל האיברים בעלי ספרות יורדות, `What(a[low])` תמיד `true`, `low` רק מתקדם, ולא מתבצעת אף החלפה.

`b = {321, 432, 543, 654, 765}`: בכל זימון `What(b[low])` מחזירה `true`, והזימונים הם `(0,4)`, `(1,4)`, `(2,4)`, `(3,4)`, `(4,4)` – עצירה ללא החלפה.

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

תשובה: `b = {321, 432, 543, 654, 765}`.

(3)
תשובה:

למשל `c = {123, 456, 789, 321, 654}` – אחרי הזימון `{654, 321, 789, 456, 123}`.

הרעיון: הפיכת סדר של 5 איברים פירושה החלפת `c[0]` עם `c[4]` ו-`c[1]` עם `c[3]` (האיבר האמצעי נשאר במקומו). החלפה מתבצעת כש-`What(c[low])` מחזירה `false` ו-`What(c[high])` מחזירה `true`, ואחריה `low` ו-`high` מתקרבים יחד. לכן נבחר:

•`c[0]` ו-`c[1]` – ספרות לא יורדות (`What` מחזירה `false`): 123, 456.

•`c[3]` ו-`c[4]` – ספרות יורדות (`What` מחזירה `true`): 321, 654.

•`c[2]` – כל מספר, למשל 789.

מעקב:

זימון`low``high``What(c[low])``What(c[high])`פעולההמערך
104`What(123)=false``What(654)=true`החלפה`{654, 456, 789, 321, 123}`
213`What(456)=false``What(321)=true`החלפה`{654, 321, 789, 456, 123}`
322––עצירה–

התקבל המערך המקורי בסדר הפוך.

תשובה: `c = {123, 456, 789, 321, 654}`.

(4)
תשובה:

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

1. `low` מתקדם מתחילת המערך כל עוד האיבר בו "טוב" (`What` מחזירה `true`), ו-`high` נסוג מסוף המערך כל עוד האיבר בו "לא טוב".

2. כשמשמאל נמצא איבר "לא טוב" ומימין איבר "טוב" – מחליפים ביניהם וממשיכים פנימה.

3. כשהמצביעים נפגשים, כל האיברים שמשמאל הם "טובים" וכל האיברים שמימין "לא טובים".

זוהי חלוקה (partition) של המערך לשתי קבוצות, בדומה לשלב החלוקה במיון מהיר. הסדר הפנימי בתוך כל קבוצה אינו נשמר בהכרח.

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

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

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

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