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

מבחן מה"ט אלגוריתמיקה ותכנות (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 · מחרוזת תקינה: אותיות גדולות וקטנות, קליטה עד תנאי

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

א.

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

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

פעולה שעוברת על התווים, סופרת אותיות גדולות וקטנות, מחזירה `false` מיד בתו שאינו אות, ובסוף מחזירה `upper > lower`.

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

1. אם התו בין `'A'` ל-`'Z'` – זו אות גדולה, ומגדילים את המונה `upper`.

2. אם התו בין `'a'` ל-`'z'` – זו אות קטנה, ומגדילים את המונה `lower`.

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

4. אם סיימנו את הלולאה, כל התווים הם אותיות, ונשאר לבדוק את התנאי השני: המחרוזת תקינה רק אם `upper > lower` (גדול ממש).

שימו לב: למחרוזת ריקה 0>00>0 אינו מתקיים, ולכן היא אינה תקינה. סיבוכיות: O(n)O(n), כאשר nn אורך המחרוזת.

C#:

public static bool IsValid(string s)
{
    int upper = 0;   // מונה אותיות גדולות
    int lower = 0;   // מונה אותיות קטנות
    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if (c >= 'A' && c <= 'Z')
            upper++;
        else if (c >= 'a' && c <= 'z')
            lower++;
        else
            return false;   // תו שאינו אות - המחרוזת לא תקינה
    }
    return upper > lower;
}

Java:

public static boolean isValid(String s)
{
    int upper = 0;   // מונה אותיות גדולות
    int lower = 0;   // מונה אותיות קטנות
    for (int i = 0; i < s.length(); i++)
    {
        char c = s.charAt(i);
        if (c >= 'A' && c <= 'Z')
            upper++;
        else if (c >= 'a' && c <= 'z')
            lower++;
        else
            return false;   // תו שאינו אות - המחרוזת לא תקינה
    }
    return upper > lower;
}

דוגמאות: `"ABc"` – שתי גדולות ואחת קטנה, מוחזר `true`; `"Ab"` – אחת מול אחת, מוחזר `false`; `"AB1"` – יש ספרה, מוחזר `false`.

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

סעיף ב

תשובה:

לולאת `do-while` שקולטת מחרוזת, מגדילה מונה אם התו הראשון או האחרון הוא `'A'`, ועוצרת כשהפעולה מסעיף א מחזירה `true`; בסוף מדפיסים את המונה.

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

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

2. בכל סיבוב קולטים מחרוזת `str`.

3. בודקים אם התו הראשון שלה (מקום 00) או התו האחרון (מקום אורך פחות 11) הוא `'A'`. אם כן – מגדילים את `count`. הבדיקה `Length > 0` מגינה מפני מחרוזת ריקה (שאין לה תו ראשון).

4. הלולאה ממשיכה כל עוד המחרוזת אינה תקינה – משתמשים בפעולה מסעיף א.

5. אחרי הלולאה מדפיסים את `count`.

המחרוזת התקינה שמסיימת את הקלט נקלטה גם היא, ולכן גם היא נבדקת ונספרת אם היא מתחילה או מסתיימת ב-`'A'`. (מי שמפרש שהמחרוזת המסיימת אינה חלק מהנתונים יבדוק את התנאי `!IsValid(str)` לפני הספירה.)

C#:

int count = 0;
string str;
do
{
    str = Console.ReadLine();
    if (str.Length > 0 && (str[0] == 'A' || str[str.Length - 1] == 'A'))
        count++;
} while (!IsValid(str));
Console.WriteLine("count = " + count);

Java:

int count = 0;
String str;
do
{
    str = in.next();
    if (str.length() > 0 && (str.charAt(0) == 'A' || str.charAt(str.length() - 1) == 'A'))
        count++;
} while (!isValid(str));
System.out.println("count = " + count);

דוגמה: עבור הקלט `Abc`, `xyzA`, `hello`, `Bob`, `ABc`: המחרוזת `Abc` מתחילה ב-`'A'`, `xyzA` מסתיימת ב-`'A'`, ו-`ABc` מתחילה ב-`'A'` והיא גם תקינה (שתי גדולות מול קטנה אחת) ולכן מסיימת את הקלט. יודפס `count = 3`.

תשובה: קטע התוכנית שלמעלה.

שאלה 2 · מספר מתחלף: זוגיות ספרות שכנות

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

לדוגמה:

•המספר 18345 הוא מספר מתחלף.

•המספר 2347 הוא מספר מתחלף.

•המספר 4 הוא מספר מתחלף.

•המספר 23441 אינו מספר מתחלף.

•המספר ‎-1234 אינו מספר מתחלף.

א.

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

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

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

הרעיון: לפי ההגדרה, מספר מתחלף הוא שלם חיובי, ולכן מספר שלילי או אפס מחזיר `false` מיד (כמו ‎-1234 בדוגמה).

עבור מספר חיובי מפרקים אותו לספרות מימין לשמאל:

1. כל עוד יש במספר לפחות שתי ספרות (`num >= 10`), לוקחים את ספרת האחדות `num % 10` ואת הספרה שמשמאלה `(num / 10) % 10`.

2. שתי ספרות הן בעלות אותה זוגיות אם השארית שלהן בחלוקה ל-22 שווה. במקרה כזה המספר אינו מתחלף – מחזירים `false`.

3. אחרת מוחקים את ספרת האחדות (`num = num / 10`) ועוברים לזוג הבא. כך נבדקים כל הזוגות השכנים.

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

סיבוכיות: O(d)O(d), כאשר dd מספר הספרות.

C#:

public static bool IsAlternating(int num)
{
    if (num <= 0)
        return false;               // רק מספר שלם חיובי יכול להיות מתחלף
    while (num >= 10)               // כל עוד יש לפחות שתי ספרות
    {
        int right = num % 10;           // ספרת האחדות
        int left = (num / 10) % 10;     // הספרה שמשמאלה
        if (right % 2 == left % 2)
            return false;           // שתי ספרות שכנות עם אותה זוגיות
        num = num / 10;             // מוחקים את ספרת האחדות
    }
    return true;
}

Java:

public static boolean isAlternating(int num)
{
    if (num <= 0)
        return false;               // רק מספר שלם חיובי יכול להיות מתחלף
    while (num >= 10)               // כל עוד יש לפחות שתי ספרות
    {
        int right = num % 10;           // ספרת האחדות
        int left = (num / 10) % 10;     // הספרה שמשמאלה
        if (right % 2 == left % 2)
            return false;           // שתי ספרות שכנות עם אותה זוגיות
        num = num / 10;             // מוחקים את ספרת האחדות
    }
    return true;
}

בדיקה מול הדוגמאות: עבור 18345 הזוגות (מימין) הם 4-5, 3-4, 8-3, 1-8 – כולם בזוגיות שונה, מוחזר `true`. עבור 23441 הזוג 4-4 זוגי-זוגי, מוחזר `false`. עבור 4 מוחזר `true`, ועבור ‎-1234 מוחזר `false`.

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

סעיף ב

תשובה:

עוברים על המערך ומוסיפים לסכום כל איבר שהפעולה מסעיף א מחזירה עבורו `true`.

הרעיון: סכימה עם תנאי. מאתחלים `sum = 0`, עוברים על כל איברי המערך, ולכל איבר מזמנים את הפעולה מסעיף א. אם האיבר הוא מספר מתחלף – מוסיפים אותו לסכום. בסוף מחזירים את `sum`.

C#:

public static int SumAlternating(int[] arr)
{
    int sum = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (IsAlternating(arr[i]))
            sum += arr[i];
    }
    return sum;
}

Java:

public static int sumAlternating(int[] arr)
{
    int sum = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (isAlternating(arr[i]))
            sum += arr[i];
    }
    return sum;
}

דוגמה: עבור המערך `{18345, 2347, 4, 23441, -1234}` המספרים המתחלפים הם 18345, 2347 ו-4, והפעולה מחזירה 18345+2347+4=2069618345+2347+4=20696.

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

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

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

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

C#:

public static bool Secret(int[] arr, int num)
{
  int i = 0;
  int j = arr.Length-1;
  int s;
  while(i < j)
  {
    s = arr[i] + arr[j];
    if(s > num)
    {
      i++;
    }
    else
    {
      if(s < num)
      {
        j--;
      }
      else
      {
        return true;
      }
    }
  }
  return false;
}

Java:

public static boolean secret(int[] arr, int num)
{
  int i = 0;
  int j = arr.length-1;
  int s;
  while(i < j)
  {
    s = arr[i] + arr[j];
    if(s > num)
    {
      i++;
    }
    else
    {
      if(s < num)
      {
        j--;
      }
      else
      {
        return true;
      }
    }
  }
  return false;
}
א.

נתון המערך `int[] arr={20, 16, 9, 4, 2}`

(1)

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

(2)

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

שימו לב: אין לשנות את המערך `arr`!

(5 נקודות)
ב.

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

(2 נקודות)
ג.

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

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

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

סעיף א

(1)
תשובה:

הפעולה תחזיר `false`.

בכל סיבוב מחשבים `s = arr[i] + arr[j]`: אם `s > num` מקדמים את `i` (עוברים לאיבר קטן יותר משמאל), אם `s < num` מקטינים את `j` (עוברים לאיבר גדול יותר מימין), ואם `s == num` מחזירים `true`. הלולאה רצה כל עוד `i < j`.

סיבובijarr[i]arr[j]sהשוואה ל-12פעולה
10420222s > numi = 1
21416218s > numi = 2
3249211s < numj = 3
4239413s > numi = 3
סיום33`i < j` לא מתקייםreturn false

אכן, אין במערך שני איברים שסכומם 1212.

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

(2)
תשובה:

למשל `num = 13`: הפעולה מחזירה `true` (כי 9+4=139+4=13).

צריך `num` שעבורו יוחזר `true`, כלומר סכום של שני איברים במקומות שונים במערך. נבחר 9+4=139+4=13.

סיבובijarr[i]arr[j]sהשוואה ל-13פעולה
10420222s > numi = 1
21416218s > numi = 2
3249211s < numj = 3
4239413s == numreturn true

(גם כל אחד מהערכים 6,11,18,20,22,24,25,29,366, 11, 18, 20, 22, 24, 25, 29, 36 מתאים.)

תשובה: `num = 13`, ואז `Secret(arr, 13)` מחזירה `true`.

סעיף ב

תשובה:

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

`i` מתחיל באיבר הגדול ביותר (משמאל) ו-`j` באיבר הקטן ביותר (מימין).

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

2. אם הסכום קטן מדי, מגדילים אותו על ידי החלפת `arr[j]` באיבר גדול יותר – `j--`. האיבר `arr[j]` לא יכול להשתתף בזוג מתאים: גם עם הגדול ביותר שנותר הסכום קטן מדי.

3. בכל צעד נפסל איבר אחד, ולכן הלולאה מסתיימת אחרי לכל היותר n−1n-1 סיבובים – סיבוכיות O(n)O(n).

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

סעיף ג

תשובה:

כן, ההנחה הכרחית (למשל עבור `{2, 20, 9, 4}` ו-`num = 13` מוחזר `false` אף ש-9+4=139+4=13). פעולה חדשה: שתי לולאות מקוננות שבודקות כל זוג `i < j`.

ההנחה הכרחית. ההחלטה להזיז את `i` או את `j` מבוססת על כך ש-`arr[i]` הוא הגדול ביותר בטווח ו-`arr[j]` הוא הקטן ביותר. במערך לא ממוין הפסילה של איבר אינה מוצדקת, והפעולה עלולה לפספס זוג.

דוגמה נגדית: `arr = {2, 20, 9, 4}`, `num = 13`:

סיבובijarr[i]arr[j]sפעולה
103246s < num, j = 2
2022911s < num, j = 1
30122022s > num, i = 1
סיום11return false

אבל 9+4=139+4=13, כלומר התשובה הנכונה היא `true`.

פעולה חדשה לכל מערך: בודקים את כל הזוגות. הלולאה החיצונית עוברת על `i` מ-00 עד לפני האחרון, והפנימית על `j` מ-`i + 1` עד הסוף, כך שכל זוג של שני מקומות שונים נבדק פעם אחת. ברגע שנמצא זוג שסכומו `num` מחזירים `true`; אם עברנו על כל הזוגות – `false`. סיבוכיות: O(n2)O(n^2).

C#:

public static bool HasPairSum(int[] arr, int num)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[i] + arr[j] == num)
                return true;
        }
    }
    return false;
}

Java:

public static boolean hasPairSum(int[] arr, int num)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        for (int j = i + 1; j < arr.length; j++)
        {
            if (arr[i] + arr[j] == num)
                return true;
        }
    }
    return false;
}

(אפשרות נוספת: למיין עותק של המערך בסדר יורד ולזמן את `Secret` – סיבוכיות O(nlog⁡n)O(n\log n).)

תשובה: כן, ההנחה הכרחית; הפעולה `HasPairSum` (ב-Java: `hasPairSum`) שלמעלה מבצעת את המשימה לכל מערך.

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

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

•מספר הרישוי – `string truckId` (ב-Java: `String truckId`).

•שם הנהג – `string driverName` (ב-Java: `String driverName`).

•המשקל המרבי (מקסימלי) לאחסון – `int maxWeight`.

•האם המשאית מיועדת לקירור? – `bool isRefrigeration` (ב-Java: `boolean isRefrigeration`).

•האם המשאית פנויה להובלה? – `bool isFree` (ב-Java: `boolean isFree`).

אפשר להניח כי במחלקה `Truck` קיימות כל הפעולות `Get, Set` (ב-Java: `get, set`).

א.

כתבו במחלקה `Truck` את הפעולה הבונה (בנאי, `constructor`) המקבלת את מספר הרישוי ואת שם הנהג. הפעולה מאתחלת את המשאית הפנויה להובלה, עם משקל מרבי של 4,000 קילוגרם ושאינה מיועדת לקירור.

(3 נקודות)
ב.

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

(4 נקודות)
ג.

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

אם אין אף משאית פנויה שמיועדת לקירור, הפעולה תחזיר מחרוזת `"NONAME"`.

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

סעיף א

תשובה:

בנאי `Truck(truckId, driverName)` שמציב את שני הפרמטרים, `maxWeight = 4000`, `isRefrigeration = false`, `isFree = true`.

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

C#:

public Truck(string truckId, string driverName)
{
    this.truckId = truckId;
    this.driverName = driverName;
    this.maxWeight = 4000;          // משקל מרבי 4,000 ק"ג
    this.isRefrigeration = false;   // אינה מיועדת לקירור
    this.isFree = true;             // פנויה להובלה
}

Java:

public Truck(String truckId, String driverName)
{
    this.truckId = truckId;
    this.driverName = driverName;
    this.maxWeight = 4000;          // משקל מרבי 4,000 ק"ג
    this.isRefrigeration = false;   // אינה מיועדת לקירור
    this.isFree = true;             // פנויה להובלה
}

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

סעיף ב

תשובה:

לולאה על המערך; לכל משאית שמיועדת לקירור ו-`maxWeight >= 10000` מדפיסים את `truckId` דרך פעולת ה-Get.

הפעולה אינה במחלקה `Truck`, ולכן ניגשים לתכונות דרך פעולות ה-Get (ההנחה בשאלה). "משקלן" מתפרש כמשקל המרבי לאחסון, `maxWeight` – זו התכונה היחידה של משקל במחלקה.

1. עוברים על כל המשאיות במערך.

2. לכל משאית בודקים שני תנאים יחד (`&&`): היא מיועדת לקירור, והמשקל המרבי שלה לפחות 1000010000 (`>=`, כי "לפחות" כולל את 1000010000 עצמו).

3. אם שני התנאים מתקיימים – מדפיסים את מספר הרישוי שלה.

C#:

public static void PrintRefrigerated(Truck[] trucks)
{
    for (int i = 0; i < trucks.Length; i++)
    {
        if (trucks[i].GetIsRefrigeration() && trucks[i].GetMaxWeight() >= 10000)
            Console.WriteLine(trucks[i].GetTruckId());
    }
}

Java:

public static void printRefrigerated(Truck[] trucks)
{
    for (int i = 0; i < trucks.length; i++)
    {
        if (trucks[i].getIsRefrigeration() && trucks[i].getMaxWeight() >= 10000)
            System.out.println(trucks[i].getTruckId());
    }
}

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

סעיף ג

תשובה:

חיפוש מקסימום של `maxWeight` רק בין המשאיות הפנויות והמיועדות לקירור; שומרים את שם הנהג; ערך התחלתי `"NONAME"`.

הרעיון: חיפוש מקסימום עם סינון.

1. מאתחלים `name = "NONAME"` ו-`max = -1` (קטן מכל משקל אפשרי). כך, אם אף משאית לא עומדת בתנאים, יוחזר `"NONAME"` בלי בדיקה נוספת.

2. עוברים על כל המשאיות. משאית "מועמדת" רק אם היא פנויה וגם מיועדת לקירור.

3. אם מועמדת ומשקלה המרבי גדול מ-`max`, מעדכנים את `max` ושומרים את שם הנהג שלה.

4. בסוף מחזירים את `name`. אם יש כמה משאיות עם אותו משקל מרבי, מוחזר שם הנהג של הראשונה מביניהן (בגלל `>` ולא `>=`).

C#:

public static string BestDriver(Truck[] trucks)
{
    string name = "NONAME";
    int max = -1;
    for (int i = 0; i < trucks.Length; i++)
    {
        if (trucks[i].GetIsFree() && trucks[i].GetIsRefrigeration()
                && trucks[i].GetMaxWeight() > max)
        {
            max = trucks[i].GetMaxWeight();
            name = trucks[i].GetDriverName();
        }
    }
    return name;
}

Java:

public static String bestDriver(Truck[] trucks)
{
    String name = "NONAME";
    int max = -1;
    for (int i = 0; i < trucks.length; i++)
    {
        if (trucks[i].getIsFree() && trucks[i].getIsRefrigeration()
                && trucks[i].getMaxWeight() > max)
        {
            max = trucks[i].getMaxWeight();
            name = trucks[i].getDriverName();
        }
    }
    return name;
}

דוגמה: אם יש משאית פנויה לקירור של 10,000 ק"ג (נהג יוסי), משאית לקירור של 12,000 ק"ג שאינה פנויה (נהגת רינה), ומשאית פנויה לקירור של 8,000 ק"ג (נהג אבי) – יוחזר שם הנהג יוסי: המשאית של רינה כבדה יותר אך אינה פנויה.

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

שאלה 5 · מחלקים: מספר משוכלל, חסר ועתיר

א.

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

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

C#:

public static int SumOfProperDivisors(int num)

Java:

public static int sumOfProperDivisors(int num)

לדוגמה:

עבור המספר 10 הפעולה תחזיר 8=1+2+58 = 1+2+5

עבור המספר 6 הפעולה תחזיר 6=1+2+36 = 1+2+3

עבור המספר 12 הפעולה תחזיר 16=1+2+3+4+616 = 1+2+3+4+6

(6 נקודות)
ב.

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

•`'P'` – אם `num` שווה לסכום מחלקיו (מספר משוכלל – `Perfect`).

•`'D'` – אם `num` גדול מסכום מחלקיו (מספר חסר – `Deficient`).

•`'A'` – אם `num` קטן מסכום מחלקיו (מספר עתיר – `Abundant`).

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

C#:

public static char CheckNumberType(int num)

Java:

public static char checkNumberType(int num)

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

(3 נקודות)
ג.

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

לדוגמה:

עבור המספר `num = 60` וסוג המספר `numType='A'` הפעולה תחזיר את המערך:

`{12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56}`

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

C#:

public static int[] AllNumbersByType(int limit, char numType)

Java:

public static int[] allNumbersByType(int limit, char numType)
(6 נקודות)
◂ פתרון מלא לשאלה 5

סעיף א

תשובה:

לולאה על `d` מ-1 עד `num / 2`; כל `d` שמחלק את `num` (`num % d == 0`) מתווסף לסכום.

הרעיון: מחלק של `num` הוא מספר `d` שעבורו `num % d == 0`. המחלק הגדול ביותר של `num` שקטן ממנו הוא לכל היותר num2\frac{num}{2} (כי המחלק הקטן ביותר שגדול מ-11 הוא 22), ולכן מספיק לבדוק את `d` מ-11 עד `num / 2`. כך גם `num` עצמו לא נכלל בסכום.

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

2. לכל `d` מ-11 עד `num / 2`: אם `d` מחלק את `num` – מוסיפים אותו ל-`sum`.

3. מחזירים את `sum`. עבור `num = 1` הלולאה לא מתבצעת ומוחזר 00 (אין ל-11 מחלקים חוץ ממנו).

C#:

public static int SumOfProperDivisors(int num)
{
    int sum = 0;
    for (int d = 1; d <= num / 2; d++)
    {
        if (num % d == 0)       // d מחלק את num
            sum += d;
    }
    return sum;
}

Java:

public static int sumOfProperDivisors(int num)
{
    int sum = 0;
    for (int d = 1; d <= num / 2; d++)
    {
        if (num % d == 0)       // d מחלק את num
            sum += d;
    }
    return sum;
}

בדיקה: עבור 1212 נבדקים d=1..6d=1..6; המחלקים 1,2,3,4,61,2,3,4,6 וסכומם 1616. עבור 1010: 1+2+5=81+2+5=8; עבור 66: 1+2+3=61+2+3=6 – כמו בדוגמאות.

תשובה: הפעולה `SumOfProperDivisors` שלמעלה.

סעיף ב

תשובה:

מחשבים `sum = SumOfProperDivisors(num)` ומחזירים `'P'` אם `num == sum`, `'D'` אם `num > sum`, ו-`'A'` אחרת.

מזמנים פעם אחת את הפעולה מסעיף א ושומרים את הסכום במשתנה (כדי לא לחשב אותו שלוש פעמים). אחר כך משווים את `num` לסכום: שווה – `'P'`; גדול – `'D'`; אחרת (קטן) – `'A'`.

C#:

public static char CheckNumberType(int num)
{
    int sum = SumOfProperDivisors(num);
    if (num == sum)
        return 'P';     // מספר משוכלל
    if (num > sum)
        return 'D';     // מספר חסר
    return 'A';         // מספר עתיר
}

Java:

public static char checkNumberType(int num)
{
    int sum = sumOfProperDivisors(num);
    if (num == sum)
        return 'P';     // מספר משוכלל
    if (num > sum)
        return 'D';     // מספר חסר
    return 'A';         // מספר עתיר
}

דוגמאות: 66: הסכום 66, מוחזר `'P'`. 1010: הסכום 8<108<10, מוחזר `'D'`. 1212: הסכום 16>1216>12, מוחזר `'A'`.

תשובה: הפעולה `CheckNumberType` שלמעלה.

סעיף ג

תשובה:

שני מעברים על 1,…,limit−11,\dots,limit-1: הראשון סופר כמה מספרים מהסוג המבוקש (לפי `CheckNumberType`), ואז יוצרים מערך בגודל הזה, והשני ממלא אותו.

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

1. מעבר ראשון – ספירה: לכל `i` מזמנים את `CheckNumberType(i)` מסעיף ב, וסופרים כמה פעמים התוצאה שווה ל-`numType`.

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

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

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

(בדוגמה בשאלה כתוב `num = 60`; הכוונה לפרמטר `limit = 60`.)

C#:

public static int[] AllNumbersByType(int limit, char numType)
{
    // מעבר ראשון: כמה מספרים מהסוג המבוקש יש?
    int count = 0;
    for (int i = 1; i < limit; i++)
    {
        if (CheckNumberType(i) == numType)
            count++;
    }
    // מעבר שני: מילוי המערך
    int[] result = new int[count];
    int k = 0;
    for (int i = 1; i < limit; i++)
    {
        if (CheckNumberType(i) == numType)
        {
            result[k] = i;
            k++;
        }
    }
    return result;
}

Java:

public static int[] allNumbersByType(int limit, char numType)
{
    // מעבר ראשון: כמה מספרים מהסוג המבוקש יש?
    int count = 0;
    for (int i = 1; i < limit; i++)
    {
        if (checkNumberType(i) == numType)
            count++;
    }
    // מעבר שני: מילוי המערך
    int[] result = new int[count];
    int k = 0;
    for (int i = 1; i < limit; i++)
    {
        if (checkNumberType(i) == numType)
        {
            result[k] = i;
            k++;
        }
    }
    return result;
}

בדיקה מול הדוגמה: עבור `limit = 60` ו-`numType = 'A'` המספרים העתירים הקטנים מ-6060 הם 12,18,20,24,30,36,40,42,48,54,5612, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56 (למשל ל-1818: 1+2+3+6+9=21>181+2+3+6+9=21>18; ל-2020: 1+2+4+5+10=22>201+2+4+5+10=22>20), ולכן מוחזר המערך מהדוגמה. עבור `numType = 'P'` היה מוחזר `{6, 28}`.

תשובה: הפעולה `AllNumbersByType` שלמעלה.

שאלה 6 · סיבוב מחרוזת שמאלה וגלגול K

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

לדוגמה: אם `s = "ABCD"` אזי תוצאת הפעולה היא: `"BCDA"`.

מחרוזת `s2` היא "גלגול K" של מחרוזת `s1` אם אפשר לקבל את מחרוזת `s2` באמצעות K סיבובים שמאלה של מחרוזת `s1`.

לדוגמה: אם `s1 = "ABCDE"` אזי `s2= "CDEAB"` היא גלגול 2 של מחרוזת `s1`.

א.

כתבו פעולה המקבלת שתי מחרוזות `s1` ו-`s2` ומספר שלם חיובי `k`. הפעולה תבדוק אם מחרוזת `s2` היא "גלגול K" של מחרוזת `s1`. אם כן – הפעולה תחזיר `true`, ולא – הפעולה תחזיר `false`.

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

C#:

public static bool IsKRolling(string s1, string s2, int k)

Java:

public static boolean isKRolling(String s1, String s2, int k)
(5 נקודות)
ב.

כתבו פעולה המקבלת שתי מחרוזות `s1` ו-`s2`. הפעולה תחזיר מספר שלם `k` שעבורו מחרוזת `s2` היא "גלגול K" של מחרוזת `s1`. אם אין שום מספר `k`, הפעולה תחזיר ‎-1.

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

C#:

public static int FindRollingK(string s1, string s2)

Java:

public static int findRollingK(String s1, String s2)
(5 נקודות)
ג.

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

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

C#:

public static bool AreAllRotations(string[] arr, string s)

Java:

public static boolean areAllRotations(String[] arr, String s)
(5 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

אם האורכים שונים – `false`; אחרת `r = k % n`, ומשווים את `s1.Substring(r) + s1.Substring(0, r)` ל-`s2`.

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

1. אם אורכי המחרוזות שונים, `s2` בוודאי אינה גלגול של `s1` (סיבוב לא משנה אורך) – מחזירים `false`.

2. אחרי nn סיבובים (כאשר nn אורך המחרוזת) המחרוזת חוזרת למצבה המקורי, ולכן kk סיבובים שקולים ל-r=k mod nr = k \bmod n סיבובים. כך הפעולה נכונה גם עבור k≥nk \ge n.

3. תוצאת rr סיבובים: החלק מהמקום rr ועד הסוף, ואחריו rr התווים הראשונים: `s1.Substring(r) + s1.Substring(0, r)`.

4. משווים את התוצאה ל-`s2` (ב-Java עם `equals`).

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

C#:

public static bool IsKRolling(string s1, string s2, int k)
{
    if (s1.Length != s2.Length)
        return false;               // סיבוב לא משנה את האורך
    if (s1.Length == 0)
        return true;                // שתי מחרוזות ריקות
    int r = k % s1.Length;          // n סיבובים מחזירים את המחרוזת למצבה
    string rolled = s1.Substring(r) + s1.Substring(0, r);
    return rolled == s2;
}

Java:

public static boolean isKRolling(String s1, String s2, int k)
{
    if (s1.length() != s2.length())
        return false;               // סיבוב לא משנה את האורך
    if (s1.length() == 0)
        return true;                // שתי מחרוזות ריקות
    int r = k % s1.length();        // n סיבובים מחזירים את המחרוזת למצבה
    String rolled = s1.substring(r) + s1.substring(0, r);
    return rolled.equals(s2);
}

בדיקה: `s1 = "ABCDE"`, `k = 2`: `r = 2`, `"CDE" + "AB" = "CDEAB"`, ולכן `IsKRolling("ABCDE", "CDEAB", 2)` מחזירה `true`; עם `k = 7` גם `r = 2` ומוחזר `true`; עם `k = 3` מתקבל `"DEABC"` ומוחזר `false`.

תשובה: הפעולה `IsKRolling` שלמעלה.

סעיף ב

תשובה:

מנסים `k = 1, 2, ..., n` עם `IsKRolling`; מחזירים את ה-`k` הראשון שמתאים, ואם אין – ‎-1.

הרעיון: יש רק nn גלגולים שונים של מחרוזת באורך nn (גלגול nn מחזיר את המחרוזת המקורית, ומשם התוצאות חוזרות על עצמן). לכן מספיק לנסות את k=1,2,…,nk = 1, 2, \dots, n בעזרת הפעולה מסעיף א:

1. אם עבור `k` כלשהו `IsKRolling(s1, s2, k)` מחזירה `true` – מחזירים את `k` (הקטן ביותר שמתאים).

2. אם אף `k` לא התאים – מחזירים ‎-1. גם אורכים שונים מגיעים לכאן, כי הפעולה מסעיף א מחזירה `false` לכל `k`.

אם `s1` ו-`s2` שוות, מוחזר ה-`k` החיובי הקטן ביותר שמחזיר את המחרוזת לעצמה (למשל nn, או 22 עבור `"ABAB"`), בהתאם לכך ש-`k` בסעיף א הוא חיובי.

C#:

public static int FindRollingK(string s1, string s2)
{
    for (int k = 1; k <= s1.Length; k++)
    {
        if (IsKRolling(s1, s2, k))
            return k;
    }
    return -1;
}

Java:

public static int findRollingK(String s1, String s2)
{
    for (int k = 1; k <= s1.length(); k++)
    {
        if (isKRolling(s1, s2, k))
            return k;
    }
    return -1;
}

דוגמאות: `FindRollingK("ABCDE", "CDEAB")` מחזירה 22; `FindRollingK("ABCDE", "ACBDE")` מחזירה ‎-1.

תשובה: הפעולה `FindRollingK` שלמעלה.

סעיף ג

תשובה:

עוברים על המערך; אם עבור מחרוזת כלשהי `FindRollingK(s, arr[i]) == -1` מחזירים `false`; אחרת בסוף `true`.

הרעיון: בדיקת "לכל" – מחפשים דוגמה נגדית. מחרוזת `arr[i]` היא גלגול כלשהו של `s` בדיוק כאשר הפעולה מסעיף ב מוצאת עבורה `k`, כלומר אינה מחזירה ‎-1 (שימו לב לסדר הפרמטרים: `s` היא המחרוזת המקורית).

1. עוברים על כל המחרוזות במערך.

2. ברגע שנמצאת מחרוזת שעבורה `FindRollingK(s, arr[i])` מחזירה ‎-1 – מחזירים `false`.

3. אם הלולאה הסתיימה – כל המחרוזות הן גלגולים של `s`, ומחזירים `true`.

C#:

public static bool AreAllRotations(string[] arr, string s)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (FindRollingK(s, arr[i]) == -1)
            return false;           // נמצאה מחרוזת שאינה גלגול של s
    }
    return true;
}

Java:

public static boolean areAllRotations(String[] arr, String s)
{
    for (int i = 0; i < arr.length; i++)
    {
        if (findRollingK(s, arr[i]) == -1)
            return false;           // נמצאה מחרוזת שאינה גלגול של s
    }
    return true;
}

דוגמה: עבור `s = "ABCD"` והמערך `{"BCDA", "DABC", "ABCD"}` מוחזר `true`; עבור `{"BCDA", "DACB"}` מוחזר `false` (`"DACB"` אינה גלגול של `"ABCD"`).

תשובה: הפעולה `AreAllRotations` שלמעלה.

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

נתונה הפעולה `What` המקבלת מערך של מספרים שלמים חיוביים `arr` ופרמטר נוסף `exp`. הפרמטר `exp` יכול לקבל ערכים שהם חזקות של 10 (כגון 1, 10, 100, 1000...).

C#:

public static int[] What(int[] arr, int exp) {
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    // **** סיום שלב 1*****

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // **** סיום שלב 2*****

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    // **** סיום שלב 3*****

    return output;
}

Java:

public static int[] what(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    // **** סיום שלב 1*****

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // **** סיום שלב 2*****

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    // **** סיום שלב 3*****

    return output;
}
א.

נתון מערך `int[] arr = {23, 15, 9, 71, 25}`

עקבו אחרי זימון הפעולה `int[] out1 = What(arr, 1)` ורשמו מה יהיה תוכן המערך `out1` אחרי זימון הפעולה.

יש להראות את תוכן המערך `count` אחרי סיום של כל אחד מהשלבים 1–3.

(6 נקודות)
ב.

נתון מערך `int[] arr = {23, 15, 9, 71, 25}`

עקבו אחרי זימון הפעולה `int[] out2 = What(arr, 10)` ורשמו מה יהיה תוכן המערך `out2` אחרי זימון הפעולה.

(6 נקודות)
ג.

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

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

סעיף א

תשובה:

`count` אחרי שלב 1: `{0,1,0,1,0,2,0,0,0,1}`; אחרי שלב 2: `{0,1,1,2,2,4,4,4,4,5}`; אחרי שלב 3: `{0,0,1,1,2,2,4,4,4,4}`. `out1 = {71, 23, 15, 25, 9}`.

עם `exp = 1` הביטוי `(arr[i] / 1) % 10` הוא ספרת האחדות. ספרות האחדות: 23→323 \to 3, 15→515 \to 5, 9→99 \to 9, 71→171 \to 1, 25→525 \to 5.

שלב 1 – ספירה: `count[d]` = כמה מספרים שספרת האחדות שלהם dd.

אינדקס0123456789
count אחרי שלב 10101020001

שלב 2 – סכומים מצטברים: `count[i] += count[i-1]`, כלומר `count[d]` = כמה מספרים שספרתם קטנה או שווה ל-dd (זה המקום שאחרי האחרון של קבוצת dd במערך הממוין).

אינדקס0123456789
count אחרי שלב 20112244445

שלב 3 – פיזור מהסוף להתחלה: כל איבר מוכנס למקום `count[digit] - 1`, ואז `count[digit]` קטן ב-11.

iarr[i]digitcount[digit] לפנימקום ב-outputcount[digit] אחריoutput
4255433{0, 0, 0, 25, 0}
3711100{71, 0, 0, 25, 0}
299544{71, 0, 0, 25, 9}
1155322{71, 0, 15, 25, 9}
0233211{71, 23, 15, 25, 9}
אינדקס0123456789
count אחרי שלב 30011224444

המערך ממוין לפי ספרת האחדות (1,3,5,5,91, 3, 5, 5, 9), ו-15 נשאר לפני 25 כמו במערך המקורי.

תשובה: `out1 = {71, 23, 15, 25, 9}`.

סעיף ב

תשובה:

`out2 = {9, 15, 23, 25, 71}`.

עם `exp = 10` הביטוי `(arr[i] / 10) % 10` הוא ספרת העשרות: 23→223 \to 2, 15→115 \to 1, 9→09 \to 0, 71→771 \to 7, 25→225 \to 2.

אינדקס0123456789
count אחרי שלב 11120000100
count אחרי שלב 21244444555

שלב 3:

iarr[i]digitcount[digit] לפנימקום ב-outputcount[digit] אחריoutput
4252433{0, 0, 0, 25, 0}
3717544{0, 0, 0, 25, 71}
290100{9, 0, 0, 25, 71}
1151211{9, 15, 0, 25, 71}
0232322{9, 15, 23, 25, 71}

(בסוף: `count = {0, 1, 2, 4, 4, 4, 4, 4, 5, 5}`.) המערך ממוין לפי ספרת העשרות (0,1,2,2,70, 1, 2, 2, 7); 23 ו-25 בעלי אותה ספרת עשרות ונשארו בסדרם המקורי.

תשובה: `out2 = {9, 15, 23, 25, 71}`.

סעיף ג

תשובה:

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

1. שלב 1 סופר לכל ספרה 00–99 כמה איברים יש לה במקום `exp`.

2. שלב 2 הופך את המונים לסכומים מצטברים: `count[d]` הוא מספר האיברים שספרתם קטנה או שווה ל-dd, כלומר הגבול העליון של "התא" של ספרה dd במערך הפלט.

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

זהו מיון מנייה (Counting Sort) לפי ספרה אחת – השלב הבסיסי של מיון בסיס (Radix Sort). המערך המקורי לא משתנה. סיבוכיות: O(n)O(n).

תשובה: הפעולה מחזירה מערך עם איברי `arr` ממוינים בסדר עולה לפי הספרה שבמקום `exp` (ספרת האחדות עבור 1, העשרות עבור 10 וכו'), כאשר איברים עם אותה ספרה נשארים בסדרם המקורי.

שאלה 8 · פרחים במערך דו-ממדי: לב ועלי כותרת

נגדיר "פרח" במערך כך:

•ה"פרח" מורכב מחמישה איברים בתת-מערך בגודל 3X3. האיבר המרכזי בתת-המערך הוא "לב הפרח". ארבעת האיברים הצמודים לו בפינותיו (אלכסוניים) הם "עלי הכותרת" של ה"פרח".

•הערך של "לב הפרח" שווה לסכום "עלי הכותרת" של הפרח.

•בכל פרח צריכים להיות בדיוק ארבעה "עלי כותרת".

לדוגמה: במערך הזה יש שני פרחים: אחד עם לב הפרח 6, ושני עם לב הפרח 15.

א.

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים `arr` ושני מספרים שלמים נוספים המציינים מיקום איבר במערך `row` (שורה) ו-`col` (עמודה). הפעולה תבדוק אם איבר זה הוא "לב הפרח".

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

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

C#:

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

Java:

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

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

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

C#:

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

Java:

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

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

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

סעיף א

תשובה:

אם האיבר בשורה/עמודה הראשונה או האחרונה – `false` (אין לו ארבעה עלי כותרת); אחרת מחזירים אם `arr[row][col]` שווה לסכום ארבעת השכנים האלכסוניים.

הרעיון: עלי הכותרת של האיבר במקום `(row, col)` הם ארבעת השכנים האלכסוניים: `(row-1, col-1)`, `(row-1, col+1)`, `(row+1, col-1)`, `(row+1, col+1)`.

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

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

3. מחזירים `true` אם ערך האיבר שווה לסכום, אחרת `false`.

ב-C# מספר השורות הוא `arr.GetLength(0)` ומספר העמודות `arr.GetLength(1)`; ב-Java – `arr.length` ו-`arr[0].length`.

C#:

public static bool IsFlower(int[,] arr, int row, int col)
{
    // לב הפרח חייב להיות פנימי: אחרת חסרים לו עלי כותרת
    if (row < 1 || row > arr.GetLength(0) - 2 || col < 1 || col > arr.GetLength(1) - 2)
        return false;
    int sum = arr[row - 1, col - 1] + arr[row - 1, col + 1]
            + arr[row + 1, col - 1] + arr[row + 1, col + 1];
    return arr[row, col] == sum;
}

Java:

public static boolean isFlower(int[][] arr, int row, int col)
{
    // לב הפרח חייב להיות פנימי: אחרת חסרים לו עלי כותרת
    if (row < 1 || row > arr.length - 2 || col < 1 || col > arr[0].length - 2)
        return false;
    int sum = arr[row - 1][col - 1] + arr[row - 1][col + 1]
            + arr[row + 1][col - 1] + arr[row + 1][col + 1];
    return arr[row][col] == sum;
}

בדיקה מול הדוגמה: האיבר 6 נמצא במקום `(1, 1)`; עלי הכותרת שלו 3,1,0,23, 1, 0, 2 וסכומם 66 – מוחזר `true`. האיבר 15 נמצא במקום `(3, 3)`; עלי הכותרת 2,8,7,−22, 8, 7, -2 וסכומם 1515 – מוחזר `true`.

תשובה: הפעולה `IsFlower` שלמעלה.

סעיף ב

תשובה:

מעבר ראשון על כל התאים סופר בעזרת `IsFlower` כמה לבבות יש; אם 00 – מחזירים `null`; אחרת יוצרים מערך בגודל הזה וממלאים אותו במעבר שני.

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

1. ספירה: עוברים בשתי לולאות מקוננות על כל השורות והעמודות, וסופרים כמה תאים הם "לב הפרח". (את הבדיקה שהתא פנימי מבצעת `IsFlower`, ולכן אפשר לעבור על כל התאים.)

2. אם לא נמצא אף פרח (`count == 0`) – מחזירים `null`, כנדרש.

3. יוצרים מערך `hearts` בגודל `count`.

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

5. מחזירים את `hearts`.

C#:

public static int[] FlowerHearts(int[,] arr)
{
    // מעבר ראשון: ספירת הפרחים
    int count = 0;
    for (int i = 0; i < arr.GetLength(0); i++)
        for (int j = 0; j < arr.GetLength(1); j++)
            if (IsFlower(arr, i, j))
                count++;
    if (count == 0)
        return null;
    // מעבר שני: מילוי מערך הלבבות
    int[] hearts = new int[count];
    int k = 0;
    for (int i = 0; i < arr.GetLength(0); i++)
        for (int j = 0; j < arr.GetLength(1); j++)
            if (IsFlower(arr, i, j))
            {
                hearts[k] = arr[i, j];
                k++;
            }
    return hearts;
}

Java:

public static int[] flowerHearts(int[][] arr)
{
    // מעבר ראשון: ספירת הפרחים
    int count = 0;
    for (int i = 0; i < arr.length; i++)
        for (int j = 0; j < arr[0].length; j++)
            if (isFlower(arr, i, j))
                count++;
    if (count == 0)
        return null;
    // מעבר שני: מילוי מערך הלבבות
    int[] hearts = new int[count];
    int k = 0;
    for (int i = 0; i < arr.length; i++)
        for (int j = 0; j < arr[0].length; j++)
            if (isFlower(arr, i, j))
            {
                hearts[k] = arr[i][j];
                k++;
            }
    return hearts;
}

בדוגמה: הלבבות נמצאים במקומות `(1, 1)` ו-`(3, 3)`, והפעולה מחזירה `{6, 15}` – בתנאי שהתאים הריקים באיור מכילים ערכים שאינם יוצרים פרחים נוספים. (אם, למשל, כל התאים הריקים היו 00, אז גם תא פנימי עם 00 שכל שכניו האלכסוניים 00 היה "לב פרח" שערכו 00.)

תשובה: הפעולה `FlowerHearts` שלמעלה.

סעיף ג

תשובה:

`IsFlower` – O(1)O(1); `FlowerHearts` – O(n⋅m)O(n \cdot m) עבור מערך בן nn שורות ו-mm עמודות.

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

2. `FlowerHearts`: נסמן ב-nn את מספר השורות וב-mm את מספר העמודות. בכל אחד משני המעברים יש שתי לולאות מקוננות שעוברות על n⋅mn \cdot m תאים, ולכל תא מזמנים את `IsFlower` שעולה O(1)O(1). סך הכול 2⋅n⋅m⋅O(1)2 \cdot n \cdot m \cdot O(1), כלומר O(n⋅m)O(n \cdot m) – ליניארי במספר התאים. (במערך ריבועי n×nn \times n: O(n2)O(n^2).)

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

שאלה 9 · חניון חברות: מחלקות, מכסות ומקומות חניה

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

המחלקה "רכב חברה" (CompanyCar) ולה התכונות:

•מספר הרישוי (`licensePlate`) – מחרוזת, `string`

•היצרן (`manufacturer`) – מחרוזת, `string`

•שם החברה שהרכב משויך אליה (`company`) – מחרוזת, `string`

המחלקה "מגבלת חברה" (CompanyLimit) ולה התכונות:

•שם החברה (`companyName`) – מחרוזת, `string`

•המגבלה המקסימלית (`companyLimit`) – מספר שלם, `int`

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

(ב-Java: הטיפוס `String` והפעולות `get/set` ו-`toString`.)

א.
(1)

הגדירו מחלקה בשם "חניון חברות" (Parking) הכוללת את התכונות הבאות:

•מערך של רכבים (`cars`) – מערך של עצמים מסוג "רכב חברה" בגודל מקסימלי של 150.

•מערך של מקומות חניה (`parkingSpots`) – מערך של מחרוזות (`string`) באותו הגודל, המציין את מקום החניה של הרכב המתאים (לדוגמה: `"Q21"`, `"A4"`, `"P10"`).

•מספר הרכבים הנוכחי בחניה (`currentCars`) – מספר שלם, `int`.

•מגבלות חניה (`limits`) – מערך של עצמים מסוג `CompanyLimit`, המכיל את המכסות לכל חברה.

(2)

כתבו במחלקה `Parking` פעולה בונה, המקבלת מערך `limits` מאותחל (עם החברות והמגבלות שלהן), ומייצרת חניון ללא רכבים, כלומר מאתחלת את מערכי הרכבים ומקומות החניה בגודל 150 ואת התכונה `currentCars` ל-0.

(4 נקודות)
ב.

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

C#:

public bool CheckSpot(string spot)

Java:

public boolean checkSpot(String spot)
(5 נקודות)
ג.

כתבו במחלקה "חניון חברות" פעולה המקבלת את פרטי הרכב ואת מקום החניה (`spot`) ומנסה לחנות אותו:

•אם החניה `spot` תפוסה על ידי רכב אחר, הפעולה תדפיס הודעה מתאימה ותחזיר `false`.

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

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

C#:

public bool ParkCar(string license, string manufacturer,
                            string company, string spot)

Java:

public boolean parkCar(String license, String manufacturer,
                                     String company, String spot)

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

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

סעיף א

(1)
תשובה:

מחלקה `Parking` עם התכונות `CompanyCar[] cars`, `string[] parkingSpots`, `int currentCars`, `CompanyLimit[] limits` (הקוד המלא בסעיף א.2).

מגדירים את ארבע התכונות כפרטיות (`private`), כמקובל בתכנות מונחה עצמים. שני המערכים הם מערכים מקבילים: הרכב `cars[i]` חונה במקום `parkingSpots[i]`. הרכבים שמורים ברצף במקומות 00 עד `currentCars - 1`, ולכן `currentCars` הוא גם המקום הפנוי הבא בשני המערכים.

הגדרת המחלקה המלאה, יחד עם הפעולה הבונה, מופיעה בסעיף א.2.

תשובה: התכונות `CompanyCar[] cars`, `string[] parkingSpots` (ב-Java: `String[]`), `int currentCars`, `CompanyLimit[] limits`.

(2)
תשובה:

הבנאי יוצר `new CompanyCar[150]` ו-`new string[150]`, מציב `currentCars = 0`, ושומר את `limits` שהתקבל.

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

C#:

public class Parking
{
    private CompanyCar[] cars;          // הרכבים שבחניון
    private string[] parkingSpots;      // parkingSpots[i] - מקום החניה של cars[i]
    private int currentCars;            // מספר הרכבים הנוכחי
    private CompanyLimit[] limits;      // המכסות של החברות

    public Parking(CompanyLimit[] limits)
    {
        this.cars = new CompanyCar[150];
        this.parkingSpots = new string[150];
        this.currentCars = 0;
        this.limits = limits;
    }
}

Java:

public class Parking
{
    private CompanyCar[] cars;          // הרכבים שבחניון
    private String[] parkingSpots;      // parkingSpots[i] - מקום החניה של cars[i]
    private int currentCars;            // מספר הרכבים הנוכחי
    private CompanyLimit[] limits;      // המכסות של החברות

    public Parking(CompanyLimit[] limits)
    {
        this.cars = new CompanyCar[150];
        this.parkingSpots = new String[150];
        this.currentCars = 0;
        this.limits = limits;
    }
}

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

סעיף ב

תשובה:

עוברים על `parkingSpots[0..currentCars-1]`; אם אחד מהם שווה ל-`spot` – `false`, אחרת `true`.

הרעיון: מקום תפוס אם הוא מופיע במערך מקומות החניה של הרכבים שבחניון. בודקים רק את המקומות 00 עד `currentCars - 1` – שאר התאים ריקים (`null`), ובדיקה שלהם ב-Java (`equals` על `null`) הייתה גורמת לשגיאה.

1. עוברים על המקומות התפוסים.

2. אם נמצא מקום ששווה ל-`spot` – מחזירים `false` (תפוס).

3. אם לא נמצא – מחזירים `true` (פנוי).

השוואת מחרוזות: ב-C# עם `==`, וב-Java עם `equals`.

C#:

public bool CheckSpot(string spot)
{
    for (int i = 0; i < currentCars; i++)
    {
        if (parkingSpots[i] == spot)
            return false;       // המקום תפוס
    }
    return true;
}

Java:

public boolean checkSpot(String spot)
{
    for (int i = 0; i < currentCars; i++)
    {
        if (parkingSpots[i].equals(spot))
            return false;       // המקום תפוס
    }
    return true;
}

תשובה: הפעולה `CheckSpot` שלמעלה.

סעיף ג

תשובה:

אם `CheckSpot(spot)` מחזירה `false` – הודעה ו-`false`; מוצאים ב-`limits` את מכסת החברה וסופרים את רכביה שבחניון; אם המספר הגיע למכסה – הודעה ו-`false`; אחרת יוצרים `CompanyCar`, מוסיפים במקום `currentCars` בשני המערכים, מגדילים את `currentCars` ומחזירים `true`.

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

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

2. מציאת המכסה: עוברים על מערך `limits` ומחפשים את העצם ששם החברה שלו שווה ל-`company`; לוקחים ממנו את המכסה (`GetCompanyLimit`). אם החברה אינה מופיעה במערך – אין לה מכסה, ולכן `limit` נשאר 00 והרכב לא יחנה.

3. ניצול המכסה: סופרים כמה מהרכבים שבחניון (`cars[0..currentCars-1]`) שייכים לחברה. אם `count >= limit` – החברה ניצלה את מכסתה: מדפיסים הודעה ומחזירים `false`.

4. הוספה: אחרת יוצרים עצם חדש `CompanyCar` עם הפרטים שהתקבלו, מציבים אותו ב-`cars[currentCars]`, את מקום החניה ב-`parkingSpots[currentCars]` (אותו אינדקס – מערכים מקבילים), מגדילים את `currentCars` ומחזירים `true`. לפי ההנחה בשאלה יש מקום פנוי בחניון, ולכן `currentCars < 150` ואין צורך לבדוק זאת.

C#:

public bool ParkCar(string license, string manufacturer,
                    string company, string spot)
{
    // 1. האם המקום תפוס?
    if (!CheckSpot(spot))
    {
        Console.WriteLine("Spot " + spot + " is taken");
        return false;
    }
    // 2. מציאת המכסה של החברה
    int limit = 0;
    for (int i = 0; i < limits.Length; i++)
    {
        if (limits[i].GetCompanyName() == company)
            limit = limits[i].GetCompanyLimit();
    }
    // 3. כמה רכבים של החברה כבר חונים?
    int count = 0;
    for (int i = 0; i < currentCars; i++)
    {
        if (cars[i].GetCompany() == company)
            count++;
    }
    if (count >= limit)
    {
        Console.WriteLine("Company " + company + " has used its quota");
        return false;
    }
    // 4. הוספת הרכב בסוף החלק המלא של המערכים
    cars[currentCars] = new CompanyCar(license, manufacturer, company);
    parkingSpots[currentCars] = spot;
    currentCars++;
    return true;
}

Java:

public boolean parkCar(String license, String manufacturer,
                       String company, String spot)
{
    // 1. האם המקום תפוס?
    if (!checkSpot(spot))
    {
        System.out.println("Spot " + spot + " is taken");
        return false;
    }
    // 2. מציאת המכסה של החברה
    int limit = 0;
    for (int i = 0; i < limits.length; i++)
    {
        if (limits[i].getCompanyName().equals(company))
            limit = limits[i].getCompanyLimit();
    }
    // 3. כמה רכבים של החברה כבר חונים?
    int count = 0;
    for (int i = 0; i < currentCars; i++)
    {
        if (cars[i].getCompany().equals(company))
            count++;
    }
    if (count >= limit)
    {
        System.out.println("Company " + company + " has used its quota");
        return false;
    }
    // 4. הוספת הרכב בסוף החלק המלא של המערכים
    cars[currentCars] = new CompanyCar(license, manufacturer, company);
    parkingSpots[currentCars] = spot;
    currentCars++;
    return true;
}

דוגמה: נניח שלחברה `"Intel"` מכסה 22. חניית רכב שלה ב-`"A1"` מצליחה (`true`); ניסיון נוסף לחנות ב-`"A1"` נכשל – המקום תפוס; חנייה ב-`"A2"` מצליחה; ניסיון שלישי, ב-`"A3"`, נכשל – החברה ניצלה את המכסה.

תשובה: הפעולה `ParkCar` שלמעלה.

שאלה 10 · רקורסיה: חזקות, ריבועים ופלט רקורסיבי

בשאלה זו אין קשר בין הסעיפים

א.

נתונה הפעולה `What` המקבלת שני מספרים שלמים חיוביים `a` ו-`b` (גדולים מאפס).

C#:

public static bool What(int a, int b) {
    return What(a, b, 1);
}
public static bool What(int a, int b, int n) {
    if(a == 1)
        return b == 1;
    if(n == b)
        return true;
    if(n > b)
        return false;
    return What(a, b, n*a);
}

Java:

public static boolean what(int a, int b) {
    return what(a, b, 1);
}
public static boolean what(int a, int b, int n) {
    if(a == 1)
        return b == 1;
    if(n == b)
        return true;
    if(n > b)
        return false;
    return what(a, b, n*a);
}
(1)

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

(2)

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

(3)

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

(6 נקודות)
ב.

נתונה הפעולה `Why` המקבלת מספר שלם `n`.

C#:

public static bool Why(int n){
    return Why(n, n);
}
public static bool Why(int n, int x){
    if(n > x * x)
        return false;
    if(n < x * x)
        return Why(n, x-1);
    return true;
}

Java:

public static boolean why(int n){
    return why(n, n);
}
public static boolean why(int n, int x){
    if(n > x * x)
        return false;
    if(n < x * x)
        return why(n, x-1);
    return true;
}
(1)

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

(2)

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

(3)

מה מבצעת הפעולה `Why` באופן כללי עבור מספר שלם `n`? יש להתייחס למקרים שונים של n.

(6 נקודות)
ג.

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

C#:

public static void Display(int n){
    if(n>0) {
        Display(n/10);
        Console.Write(n % 10);
        Display(n/10);
    }
}

Java:

public static void display (int n){
    if(n>0) {
        display(n/10);
        System.out.print(n % 10);
        display(n/10);
    }
}
(1)

מה יהיה פלט עבור זימון הפעולה `Display(12)`? יש להראות מעקב.

(2)

מה יהיה פלט עבור זימון הפעולה `Display(123)`?

(3)

מה יהיה פלט עבור זימון הפעולה `Display(1234)`?

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

סעיף א

(1)
תשובה:

`false`.

הזימון `What(2, 15)` מזמן את `What(2, 15, 1)`. בכל זימון `n` מוכפל ב-`a = 2`, עד ש-`n` שווה ל-`b` או עובר אותו.

זימוןabna == 1?n == b?n > b?פעולה
12151לאלאלאWhat(2, 15, 2)
22152לאלאלאWhat(2, 15, 4)
32154לאלאלאWhat(2, 15, 8)
42158לאלאלאWhat(2, 15, 16)
521516לאלאכןreturn false

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

תשובה: `What(2, 15)` מחזירה `false`.

(2)
תשובה:

`b = 27` (או `b = 81`).

הפעולה מחזירה `true` כאשר `n` מגיע בדיוק ל-`b`. הערכים של `n` עבור `a = 3` הם 1,3,9,27,81,243,…1, 3, 9, 27, 81, 243, \dots – חזקות של 33. החזקות הדו-ספרתיות הן 27=3327 = 3^3 ו-81=3481 = 3^4.

מעקב עבור `What(3, 27)`: n=1→3→9→27n = 1 \to 3 \to 9 \to 27, ובזימון האחרון `n == b` ומוחזר `true`.

תשובה: `b = 27` (גם `b = 81` מתאים).

(3)
תשובה:

מחזירה `true` אם `b` הוא חזקה שלמה של `a` (b=akb = a^k עבור k≥0k \ge 0 שלם), אחרת `false`; עבור `a = 1` – `true` רק אם `b = 1`.

1. `n` מתחיל ב-1=a01 = a^0 ובכל זימון מוכפל ב-`a`, ולכן מקבל את הערכים a0,a1,a2,…a^0, a^1, a^2, \dots.

2. אם אחד מהם שווה ל-`b` – מוחזר `true`; ברגע שהם עוברים את `b` – מוחזר `false`. כיוון ש-a≥2a \ge 2, הסדרה עולה ממש, ולכן הרקורסיה תמיד מסתיימת.

3. המקרה `a = 1` מטופל בנפרד, כי אז `n` היה נשאר 11 לתמיד (רקורסיה אינסופית). כל החזקות של 11 שוות 11, ולכן מוחזר `true` רק אם `b == 1`.

4. גם `b = 1` מחזיר תמיד `true`, כי 1=a01 = a^0.

תשובה: הפעולה בודקת אם `b` הוא חזקה של `a`, כלומר אם קיים k≥0k \ge 0 שלם כך ש-b=akb = a^k.

סעיף ב

(1)
תשובה:

`false`.

`Why(10)` מזמנת את `Why(10, 10)`. בכל זימון משווים את `n = 10` ל-`x * x`; כל עוד 10<x210 < x^2 מקטינים את `x` ב-11.

זימוןnxx * xהשוואהפעולה
11010100n < x*xWhy(10, 9)
210981n < x*xWhy(10, 8)
310864n < x*xWhy(10, 7)
410749n < x*xWhy(10, 6)
510636n < x*xWhy(10, 5)
610525n < x*xWhy(10, 4)
710416n < x*xWhy(10, 3)
81039n > x*xreturn false

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

(2)
תשובה:

`n = 16` (וכל ריבוע דו-ספרתי: 16, 25, 36, 49, 64, 81).

הפעולה מחזירה `true` רק כאשר נמצא `x` שעבורו `n == x * x`, כלומר כש-`n` הוא ריבוע של מספר שלם.

מעקב עבור `Why(16)`: x=16→15→⋯→5x = 16 \to 15 \to \dots \to 5 (16<x216 < x^2 בכל פעם), ואז x=4x = 4: x2=16=nx^2 = 16 = n, ומוחזר `true`.

תשובה: `n = 16` (גם 25, 36, 49, 64, 81 מתאימים).

(3)
תשובה:

עבור n>0n>0: `true` אם ורק אם `n` ריבוע שלם; עבור n=0n=0: `true`; עבור n<0n<0: רקורסיה אינסופית (חריגת מחסנית), אין ערך מוחזר.

הפעולה מתחילה ב-`x = n` ומקטינה את `x` ב-11 כל עוד n<x2n < x^2.

1. n>0n > 0: בהתחלה x=nx = n ולכן x2=n2≥nx^2 = n^2 \ge n. `x` יורד עד הערך הראשון שעבורו x2≤nx^2 \le n, כלומר x=⌊n⌋x = \lfloor\sqrt{n}\rfloor. אם x2=nx^2 = n מוחזר `true`, ואם x2<nx^2 < n מוחזר `false`. לכן הפעולה מחזירה `true` אם ורק אם `n` הוא ריבוע של מספר שלם (1, 4, 9, 16, ...). (עבור n=1n = 1: כבר בזימון הראשון 1=1⋅11 = 1 \cdot 1, ומוחזר `true`.)

2. n=0n = 0: x=0x = 0, ו-0=0⋅00 = 0 \cdot 0, ולכן מוחזר `true` מיד (0=020 = 0^2 הוא ריבוע).

3. n<0n < 0: `x` מתחיל בערך שלילי, ו-x2x^2 חיובי ולכן תמיד גדול מ-`n`. בכל זימון `x` קטן ב-11 ו-x2x^2 רק גדל, כך שהתנאי `n < x * x` מתקיים תמיד, ואין תנאי עצירה – רקורסיה אינסופית. בפועל התוכנית תיעצר עם חריגת גלישת מחסנית (StackOverflowException ב-C#, StackOverflowError ב-Java) ולא יוחזר ערך.

תשובה: עבור `n` חיובי – הפעולה בודקת אם `n` ריבוע שלם; עבור `n = 0` – מחזירה `true`; עבור `n` שלילי – רקורסיה אינסופית (גלישת מחסנית).

סעיף ג

(1)
תשובה:

`121`

כל זימון עם `n > 0` מבצע שלושה דברים לפי הסדר: זימון רקורסיבי עם `n/10`, הדפסת ספרת האחדות `n % 10`, ושוב זימון רקורסיבי עם `n/10`. זימון עם `n = 0` אינו עושה דבר.

שלבזימוןפעולהפלט מצטבר
1Display(12)מזמנת Display(1)
2Display(1)מזמנת Display(0) – לא עושה דבר
3Display(1)מדפיסה 1 % 10 = 11
4Display(1)מזמנת Display(0) – לא עושה דבר, וחוזרת1
5Display(12)מדפיסה 12 % 10 = 212
6Display(12)מזמנת Display(1)12
7Display(1)Display(0), מדפיסה 1, Display(0)121

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

(2)
תשובה:

`1213121`

לפי מבנה הפעולה, הפלט של `Display(n)` הוא: הפלט של `Display(n/10)`, אחריו ספרת האחדות של `n`, ואחריו שוב הפלט של `Display(n/10)`.

עבור `n = 123`: `n/10 = 12`, שהפלט שלו (מסעיף 1) הוא `121`, וספרת האחדות היא 3. לכן הפלט: `121` + `3` + `121`.

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

(3)
תשובה:

`121312141213121`

באותו אופן: `1234/10 = 123`, שהפלט שלו (מסעיף 2) הוא `1213121`, וספרת האחדות היא 4. לכן הפלט: `1213121` + `4` + `1213121`.

(באופן כללי, למספר בן dd ספרות מודפסות 2d−12^d - 1 ספרות: 33 עבור 12, 77 עבור 123 ו-1515 עבור 1234.)

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

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

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

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