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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · קליטה עד שלושה אפסים: סכום וספירה

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

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

◂ פתרון מלא לשאלה 1

פתרון

תשובה:

לולאת while שרצה כל עוד מונה האפסים קטן מ-3; כל 0 מגדיל את מונה האפסים, מספר חיובי מתווסף לצובר, ומספר שלילי מגדיל את מונה השליליים; בסוף מדפיסים את הצובר ואת המונה.

הרעיון: מספר הקלטים אינו ידוע מראש – הקלט נגמר רק כשנקלט 0 בפעם השלישית. לכן משתמשים בלולאת while עם מונה אפסים `zeros`, והלולאה רצה כל עוד `zeros < 3`. (שלוש הפעמים של 0 לא חייבות להיות ברצף – סופרים כל 0 שנקלט.)

1. שלושה משתנים: `zeros` – כמה פעמים נקלט 0; `sumPos` – צובר לסכום החיוביים; `countNeg` – מונה לשליליים. כולם מתחילים ב-0.

2. בכל סיבוב קולטים מספר `num` ובודקים לאיזו משלוש הקבוצות הוא שייך:

•`num == 0` – מגדילים את `zeros` (האפס אינו חיובי ואינו שלילי, ולכן לא נכנס לחישובים);

•`num > 0` – מוסיפים אותו ל-`sumPos`;

•אחרת המספר שלילי – מגדילים את `countNeg`.

3. כשנקלט ה-0 השלישי, `zeros` נעשה 3, תנאי הלולאה נכשל והלולאה נגמרת. אחרי הלולאה מדפיסים את שתי התוצאות.

C#:

int zeros = 0;      // כמה פעמים נקלט אפס
int sumPos = 0;     // סכום המספרים החיוביים
int countNeg = 0;   // כמות המספרים השליליים
while (zeros < 3)
{
    int num = int.Parse(Console.ReadLine());
    if (num == 0)
        zeros++;
    else if (num > 0)
        sumPos += num;
    else
        countNeg++;
}
Console.WriteLine("Sum of positives: " + sumPos);
Console.WriteLine("Negatives: " + countNeg);

Java:

Scanner in = new Scanner(System.in);
int zeros = 0;      // כמה פעמים נקלט אפס
int sumPos = 0;     // סכום המספרים החיוביים
int countNeg = 0;   // כמות המספרים השליליים
while (zeros < 3)
{
    int num = in.nextInt();
    if (num == 0)
        zeros++;
    else if (num > 0)
        sumPos += num;
    else
        countNeg++;
}
System.out.println("Sum of positives: " + sumPos);
System.out.println("Negatives: " + countNeg);

דוגמה: עבור הקלט 1,−2,0,5,−3,0,7,01, -2, 0, 5, -3, 0, 7, 0 – החיוביים 1+5+7=131+5+7=13, השליליים −2-2 ו-−3-3 (שניים), והקלט נעצר אחרי ה-0 השלישי. יודפס: `Sum of positives: 13`, `Negatives: 2`.

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

שאלה 2 · ספירת מחרוזות לפי זוגיות האורך

כתבו קטע תוכנית הקולטת מחרוזות. הקלט מסתיים כאשר תיקלט מחרוזת המתחילה ומסתיימת באות 'Z'.

על התוכנית להדפיס את מספר המחרוזות באורך זוגי ואת מספר המחרוזות באורך אי-זוגי.

◂ פתרון מלא לשאלה 2

פתרון

תשובה:

לולאה שקולטת מחרוזת, מגדילה מונה זוגי או אי-זוגי לפי `length % 2`, ונעצרת כשהתו הראשון והתו האחרון הם 'Z'; בסוף מדפיסים את שני המונים.

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

1. שני מונים: `countEven` (אורך זוגי) ו-`countOdd` (אורך אי-זוגי), שניהם 0.

2. ספירה: אורך המחרוזת זוגי אם שארית החלוקה שלו ב-2 היא 0, כלומר `str.length() % 2 == 0` (ב-C#: `str.Length % 2 == 0`). לפי זה מגדילים את המונה המתאים.

3. תנאי העצירה: התו הראשון נמצא במקום 0 והתו האחרון במקום `length - 1`. אם שניהם `'Z'` – מציבים `stop = true`, והלולאה תסתיים. (גם המחרוזת `"Z"` בת התו האחד מתחילה ומסתיימת ב-'Z'.)

4. אחרי הלולאה מדפיסים את שני המונים.

C#:

int countEven = 0;   // מחרוזות באורך זוגי
int countOdd = 0;    // מחרוזות באורך אי-זוגי
bool stop = false;
while (!stop)
{
    string str = Console.ReadLine();
    if (str.Length % 2 == 0)
        countEven++;
    else
        countOdd++;
    // תנאי העצירה: האות הראשונה והאחרונה הן 'Z'
    if (str[0] == 'Z' && str[str.Length - 1] == 'Z')
        stop = true;
}
Console.WriteLine("Even length: " + countEven);
Console.WriteLine("Odd length: " + countOdd);

Java:

Scanner in = new Scanner(System.in);
int countEven = 0;   // מחרוזות באורך זוגי
int countOdd = 0;    // מחרוזות באורך אי-זוגי
boolean stop = false;
while (!stop)
{
    String str = in.next();
    if (str.length() % 2 == 0)
        countEven++;
    else
        countOdd++;
    // תנאי העצירה: האות הראשונה והאחרונה הן 'Z'
    if (str.charAt(0) == 'Z' && str.charAt(str.length() - 1) == 'Z')
        stop = true;
}
System.out.println("Even length: " + countEven);
System.out.println("Odd length: " + countOdd);

דוגמה: עבור הקלט `ab`, `abc`, `ZooZ` – `ab` באורך 2 (זוגי), `abc` באורך 3 (אי-זוגי), `ZooZ` באורך 4 (זוגי) ומסיימת את הקלט. יודפס: 2 מחרוזות באורך זוגי ו-1 באורך אי-זוגי.

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

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

שאלה 3 · מספרים אקראיים תלת-ספרתיים: מקסימום וסכום ספרות

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

•את המספר הגדול ביותר שנוצר;

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

◂ פתרון מלא לשאלה 3

פתרון

תשובה:

לולאת for של 40 סיבובים; בכל סיבוב מגרילים מספר בין 100 ל-999, מעדכנים מקסימום, ומחשבים סכום ספרות `num%10 + num/10%10 + num/100`; אם הוא 7 מגדילים מונה; בסוף מדפיסים את המקסימום ואת המונה.

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

1. הגרלה: לפי ההנחיות, מספר אקראי בין X=100X=100 ל-Y=999Y=999: ב-Java `100 + rand.nextInt(999 - 100 + 1)`, כלומר `100 + rand.nextInt(900)`; ב-C# `rand.Next(100, 1000)`.

2. מקסימום: מאתחלים `max = 0` (כל מספר תלת-ספרתי גדול מ-0, ולכן כבר המספר הראשון יחליף אותו). כל מספר שגדול מ-`max` מחליף אותו.

3. סכום ספרות: למספר תלת-ספרתי יש בדיוק שלוש ספרות:

•ספרת האחדות `num % 10`;

•ספרת העשרות `num / 10 % 10`;

•ספרת המאות `num / 100` (חילוק שלמים).

למשל עבור 214: 4+1+2=74+1+2=7. אם הסכום הוא 7 – מגדילים את `count7`.

4. אחרי הלולאה מדפיסים את `max` ואת `count7`.

C#:

Random rand = new Random();
int max = 0;          // כל מספר תלת-ספרתי גדול מ-0
int count7 = 0;       // מספרים שסכום ספרותיהם 7
for (int i = 1; i <= 40; i++)
{
    int num = rand.Next(100, 1000);         // 100..999
    if (num > max)
        max = num;
    int sum = num % 10 + num / 10 % 10 + num / 100;   // אחדות + עשרות + מאות
    if (sum == 7)
        count7++;
}
Console.WriteLine("Max: " + max);
Console.WriteLine("Digit sum 7: " + count7);

Java:

Random rand = new Random();
int max = 0;          // כל מספר תלת-ספרתי גדול מ-0
int count7 = 0;       // מספרים שסכום ספרותיהם 7
for (int i = 1; i <= 40; i++)
{
    int num = 100 + rand.nextInt(900);      // 100..999
    if (num > max)
        max = num;
    int sum = num % 10 + num / 10 % 10 + num / 100;   // אחדות + עשרות + מאות
    if (sum == 7)
        count7++;
}
System.out.println("Max: " + max);
System.out.println("Digit sum 7: " + count7);

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

שאלה 4 · מחלקת קופסת אחסון ומערך עצמים

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

למחלקת קופסת האחסון `StorageBox` יש שש תכונות:

•צבע – `color`, מטיפוס מחרוזת – `string`

•אורך – `length`, מטיפוס מספר שלם – `int`

•רוחב – `width`, מטיפוס מספר שלם – `int`

•גובה – `height`, מטיפוס מספר שלם – `int`

•מחיר – `cost`, מטיפוס מספר ממשי – `double`

•יש מכסה – `hasCover`, מטיפוס בוליאני – `bool` (יש מכסה – `true`, אין מכסה – `false`)

במחלקה `StorageBox` הוגדרה פעולה בונה (בנאי, `constructor`) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות `Get`/`Set` לכל אחת מהתכונות.

א.

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

C#:

public StorageBox(double cost)

Java:

public StorageBox(double cost)
(4 נקודות)
ב.

כתבו פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג `StorageBox` בשם `arr` וצבע `color`.

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

C#:

public static int NoCover(StorageBox[] arr, string color)

Java:

public static int noCover(StorageBox[] arr, String color)

הנחה: כל תא במערך מכיל הפניה לעצם מסוג `StorageBox` ואין תאים במערך שערכם שווה ל-`null`.

(4 נקודות)
ג.

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

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

C#:

public static bool IsUnique(StorageBox[] arr)

Java:

public static boolean isUnique(StorageBox[] arr)

הנחה: כל תא במערך מכיל הפניה לעצם מסוג `StorageBox` ואין תאים במערך שערכם שווה ל-`null`.

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

סעיף א

תשובה:

הבונה מציבה `color = "white"`, `hasCover = false`, `cost` מהפרמטר, ולכל ממד מספר אקראי בין 30 ל-100.

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

1. מספר אקראי בין X=30X=30 ל-Y=100Y=100: יש Y−X+1=100−30+1=71Y-X+1=100-30+1=71 ערכים אפשריים, ולכן ב-Java `30 + (int)(Math.random() * 71)`, וב-C# `rand.Next(30, 101)` (הגבול העליון ב-`Next` אינו נכלל, ולכן 101).

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

3. את `cost` מעתיקים מהפרמטר.

C#:

public StorageBox(double cost)
{
    Random rand = new Random();
    this.color = "white";
    this.length = rand.Next(30, 101);   // 30..100
    this.width  = rand.Next(30, 101);
    this.height = rand.Next(30, 101);
    this.cost = cost;
    this.hasCover = false;
}

Java:

public StorageBox(double cost)
{
    this.color = "white";
    this.length = 30 + (int)(Math.random() * 71);   // 30..100
    this.width  = 30 + (int)(Math.random() * 71);
    this.height = 30 + (int)(Math.random() * 71);
    this.cost = cost;
    this.hasCover = false;
}

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

סעיף ב

תשובה:

מונה שעובר על כל המערך וסופר קופסאות שצבען שווה ל-`color` ו-`hasCover` שלהן `false`.

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

1. עבור כל קופסה `arr[i]` בודקים שני תנאים יחד (וגם):

•הצבע שלה שווה ל-`color` – ב-Java משווים מחרוזות עם `equals`, ב-C# אפשר עם `==`;

•אין לה מכסה – `!arr[i].getHasCover()`.

2. אם שניהם מתקיימים – מגדילים את המונה.

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

C#:

public static int NoCover(StorageBox[] arr, string color)
{
    int count = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i].GetColor() == color && !arr[i].GetHasCover())
            count++;
    }
    return count;
}

Java:

public static int noCover(StorageBox[] arr, String color)
{
    int count = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i].getColor().equals(color) && !arr[i].getHasCover())
            count++;
    }
    return count;
}

תשובה: הפעולה `NoCover` / `noCover` שלמעלה.

סעיף ג

תשובה:

משווים כל קופסה לקופסה הראשונה: אם הצבע שונה או מצב המכסה שונה – `false`; אחרת `true`.

הרעיון: "כל הקופסאות באותו צבע" שקול ל"כל קופסה בצבע של הקופסה הראשונה", ובאותו אופן לגבי המכסה. לכן משווים כל קופסה ל-`arr[0]`, ועוצרים בקופסה הראשונה שחורגת.

1. עוברים על `i` מ-1 עד סוף המערך.

2. אם הצבע של `arr[i]` שונה מהצבע של `arr[0]` – זה לא סט אחיד, מחזירים `false`.

3. אם `hasCover` של `arr[i]` שונה מזה של `arr[0]` (לאחת יש מכסה ולשנייה אין) – מחזירים `false`.

4. אם הלולאה הסתיימה בלי חריגה – מחזירים `true`. (מערך עם קופסה אחת הוא סט אחיד.)

C#:

public static bool IsUnique(StorageBox[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i].GetColor() != arr[0].GetColor())
            return false;                       // צבע שונה
        if (arr[i].GetHasCover() != arr[0].GetHasCover())
            return false;                       // מצב מכסה שונה
    }
    return true;
}

Java:

public static boolean isUnique(StorageBox[] arr)
{
    for (int i = 1; i < arr.length; i++)
    {
        if (!arr[i].getColor().equals(arr[0].getColor()))
            return false;                       // צבע שונה
        if (arr[i].getHasCover() != arr[0].getHasCover())
            return false;                       // מצב מכסה שונה
    }
    return true;
}

תשובה: הפעולה `IsUnique` / `isUnique` שלמעלה.

שאלה 5 · מערך ממוין לפי מקומות זוגיים ולפי ערכים זוגיים

א.

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

לדוגמה, המערך הבא הוא "מערך ממוין לפי מקומות זוגיים":

012345678
53711019161435

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

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

C#:

public static bool IsOrderedPlaces(int[] arr)

Java:

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

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

לדוגמה, המערך הבא הוא "מערך ממוין לפי ערכים זוגיים":

012345678
538102319161835

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

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

C#:

public static bool IsOrderedValues(int[] arr)

Java:

public static boolean isOrderedValues(int[] arr)

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

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

סעיף א

תשובה:

עוברים על המקומות הזוגיים `i = 2, 4, ...` ומחזירים `false` אם `arr[i] <= arr[i-2]`; אחרת `true`.

הרעיון: המקומות הזוגיים הם 0,2,4,…0, 2, 4, \dots. הסדרה שלהם עולה אם כל איבר במקום זוגי גדול מהאיבר במקום הזוגי שלפניו, כלומר `arr[i] > arr[i-2]`. מספיק להשוות כל זוג "שכנים" כאלה.

1. לולאה על `i` מ-2 בקפיצות של 2 (`i += 2`), כל עוד `i < arr.length`.

2. אם `arr[i] <= arr[i-2]` – הסדר אינו עולה, מחזירים `false`.

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

בדוגמה: במקומות 0, 2, 4, 6, 8 נמצאים 5,7,10,16,355, 7, 10, 16, 35 – סדרה עולה, ולכן מוחזר `true`. המקומות האי-זוגיים (3,1,19,143, 1, 19, 14) לא נבדקים כלל.

C#:

public static bool IsOrderedPlaces(int[] arr)
{
    for (int i = 2; i < arr.Length; i += 2)
    {
        if (arr[i] <= arr[i - 2])     // לא עולה ביחס למקום הזוגי הקודם
            return false;
    }
    return true;
}

Java:

public static boolean isOrderedPlaces(int[] arr)
{
    for (int i = 2; i < arr.length; i += 2)
    {
        if (arr[i] <= arr[i - 2])     // לא עולה ביחס למקום הזוגי הקודם
            return false;
    }
    return true;
}

("בסדר עולה" פורש כאן כעולה ממש. אם מתירים ערכים שווים, מחליפים את התנאי ב-`arr[i] < arr[i - 2]`.)

תשובה: הפעולה `IsOrderedPlaces` / `isOrderedPlaces` שלמעלה.

סעיף ב

תשובה:

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

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

1. מאתחלים `last = -1`. כל איברי המערך חיוביים, ולכן −1-1 מסמן בבירור "עוד לא נמצא זוגי".

2. לכל `arr[i]` זוגי (`arr[i] % 2 == 0`):

•אם כבר נמצא זוגי קודם (`last != -1`) ו-`arr[i] <= last` – הסדר אינו עולה, מחזירים `false`;

•אחרת מעדכנים `last = arr[i]`.

3. איברים אי-זוגיים מדלגים עליהם.

4. בסוף מחזירים `true`.

בדוגמה: הזוגיים לפי הסדר הם 8,10,16,188, 10, 16, 18 – עולים, ולכן מוחזר `true`. (האי-זוגיים 5,3,23,19,355, 3, 23, 19, 35 לא משפיעים.)

C#:

public static bool IsOrderedValues(int[] arr)
{
    int last = -1;                    // הערך הזוגי הקודם (-1: עוד לא נמצא)
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] % 2 == 0)
        {
            if (last != -1 && arr[i] <= last)
                return false;
            last = arr[i];
        }
    }
    return true;
}

Java:

public static boolean isOrderedValues(int[] arr)
{
    int last = -1;                    // הערך הזוגי הקודם (-1: עוד לא נמצא)
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] % 2 == 0)
        {
            if (last != -1 && arr[i] <= last)
                return false;
            last = arr[i];
        }
    }
    return true;
}

תשובה: הפעולה `IsOrderedValues` / `isOrderedValues` שלמעלה.

שאלה 6 · מערך "גדול" ממערך אחר וחלוקת מערך

א.

נתונים שני מערכים של מספרים שלמים `arrA` ו-`arrB`. גודל המערכים זהה.

הגדרה: המערך `arrA` "גדול" מהמערך `arrB`, אם לכל אינדקס `k` מתקיים `arrA[k] > arrB[k]`.

לדוגמה:

המערך `arrA`

01234567
5113810023191618

גדול מהמערך `arrB`

01234567
532902061310

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

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

C#:

public static bool IsBig(int[] arrA, int[] arrB)

Java:

public static boolean isBig(int[] arrA, int[] arrB)
(4 נקודות)
ב.

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

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

C#:

public static void Divide(int[] arr, int[] arrA, int[] arrB)

Java:

public static void divide(int[] arr, int[] arrA, int[] arrB)

אפשר להניח שהמערך `arr` בגודל זוגי, וגודלם של המערכים `arrA` ו-`arrB` הוא חצי מגודל המערך `arr`.

(6 נקודות)
ג.

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

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

סעיף א

תשובה:

לולאה על כל `k`: אם `arrA[k] <= arrB[k]` מחזירים `false`; אחרת בסוף `true`.

הרעיון: התנאי צריך להתקיים לכל אינדקס, ולכן מספיק אינדקס אחד שבו `arrA[k] <= arrB[k]` כדי להחזיר `false`. אם לא נמצא כזה – מחזירים `true`.

1. לולאה על `k` מ-0 עד סוף המערכים (הם באותו גודל).

2. אם `arrA[k] <= arrB[k]` – מחזירים `false`.

3. אחרי הלולאה – `true`.

בדוגמה: 51>5, 13>3, 8>2, 100>90, 23>20, 19>6, 16>13, 18>1051>5,\ 13>3,\ 8>2,\ 100>90,\ 23>20,\ 19>6,\ 16>13,\ 18>10 – כל התנאים מתקיימים, מוחזר `true`.

C#:

public static bool IsBig(int[] arrA, int[] arrB)
{
    for (int k = 0; k < arrA.Length; k++)
    {
        if (arrA[k] <= arrB[k])
            return false;
    }
    return true;
}

Java:

public static boolean isBig(int[] arrA, int[] arrB)
{
    for (int k = 0; k < arrA.length; k++)
    {
        if (arrA[k] <= arrB[k])
            return false;
    }
    return true;
}

תשובה: הפעולה `IsBig` / `isBig` שלמעלה.

סעיף ב

תשובה:

לכל איבר סופרים כמה איברים קטנים ממנו; אם לפחות n/2n/2 – הוא בחצי הגדול ונכנס ל-`arrA`, אחרת ל-`arrB`. כך כל איבר ב-`arrA` גדול מכל איבר ב-`arrB`, ולכן `arrA` "גדול" מ-`arrB`.

הרעיון: נסמן ב-nn את גודל `arr`. אם נכניס ל-`arrA` את n/2n/2 המספרים הגדולים ביותר, ול-`arrB` את n/2n/2 הקטנים ביותר, אז כל איבר ב-`arrA` גדול מכל איבר ב-`arrB` (המספרים שונים זה מזה). בפרט `arrA[k] > arrB[k]` לכל `k` – בלי קשר לסדר שבו הם נכנסו.

איך יודעים אם איבר שייך לחצי הגדול? סופרים כמה איברים במערך קטנים ממנו. ל-n/2n/2 הקטנים ביותר יש 0,1,…,n/2−10, 1, \dots, n/2-1 איברים קטנים מהם; ל-n/2n/2 הגדולים יש n/2,…,n−1n/2, \dots, n-1. לכן:

•אם מספר האיברים הקטנים מ-`arr[i]` הוא לפחות n/2n/2 – `arr[i]` נכנס ל-`arrA`;

•אחרת – ל-`arrB`.

1. `half = arr.length / 2`, ושני מצביעים `a`, `b` למקום הפנוי הבא ב-`arrA` וב-`arrB`.

2. לכל `i`: לולאה פנימית סופרת ב-`smaller` כמה איברים קטנים מ-`arr[i]`.

3. לפי `smaller >= half` מעתיקים את `arr[i]` ל-`arrA[a++]` או ל-`arrB[b++]`.

4. בדיוק n/2n/2 איברים מקיימים את התנאי, ולכן כל אחד מהמערכים מתמלא בדיוק.

המערך `arr` עצמו אינו משתנה.

C#:

public static void Divide(int[] arr, int[] arrA, int[] arrB)
{
    int half = arr.Length / 2;
    int a = 0, b = 0;                 // המקום הפנוי הבא ב-arrA וב-arrB
    for (int i = 0; i < arr.Length; i++)
    {
        int smaller = 0;              // כמה איברים קטנים מ-arr[i]
        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] < arr[i])
                smaller++;
        }
        if (smaller >= half)          // arr[i] בחצי הגדול
        {
            arrA[a] = arr[i];
            a++;
        }
        else                          // arr[i] בחצי הקטן
        {
            arrB[b] = arr[i];
            b++;
        }
    }
}

Java:

public static void divide(int[] arr, int[] arrA, int[] arrB)
{
    int half = arr.length / 2;
    int a = 0, b = 0;                 // המקום הפנוי הבא ב-arrA וב-arrB
    for (int i = 0; i < arr.length; i++)
    {
        int smaller = 0;              // כמה איברים קטנים מ-arr[i]
        for (int j = 0; j < arr.length; j++)
        {
            if (arr[j] < arr[i])
                smaller++;
        }
        if (smaller >= half)          // arr[i] בחצי הגדול
        {
            arrA[a] = arr[i];
            a++;
        }
        else                          // arr[i] בחצי הקטן
        {
            arrB[b] = arr[i];
            b++;
        }
    }
}

דוגמה: עבור `arr = {7, -2, 9, 4, 0, 15}` (n=6n=6, `half = 3`): ל-7 יש 3 איברים קטנים ממנו (−2,4,0-2, 4, 0) – ל-`arrA`; ל-−2-2 אין – ל-`arrB`; ל-9 יש 4 – ל-`arrA`; ל-4 יש 2 – ל-`arrB`; ל-0 יש 1 – ל-`arrB`; ל-15 יש 5 – ל-`arrA`. מתקבל `arrA = {7, 9, 15}`, `arrB = {-2, 4, 0}`, ואכן 7>−2, 9>4, 15>07>-2,\ 9>4,\ 15>0.

(דרך אחרת: למיין עותק של `arr`, להעתיק את החצי הקטן ל-`arrB` ואת החצי הגדול ל-`arrA`.)

תשובה: הפעולה `Divide` / `divide` שלמעלה.

סעיף ג

תשובה:

סעיף א: O(n)O(n); סעיף ב: O(n2)O(n^2).

נסמן ב-nn את גודל המערכים (בסעיף ב – גודל `arr`).

•סעיף א: לולאה אחת שעוברת על המערכים פעם אחת לכל היותר, ובכל סיבוב השוואה אחת בזמן קבוע – O(n)O(n).

•סעיף ב: לכל אחד מ-nn האיברים, הלולאה הפנימית עוברת על כל nn האיברים כדי לספור את הקטנים ממנו – n⋅nn\cdot n השוואות, כלומר O(n2)O(n^2).

(בדרך של מיון העותק, הסיבוכיות היא כסיבוכיות המיון: O(nlog⁡n)O(n\log n) במיון יעיל.)

תשובה: סעיף א – O(n)O(n); סעיף ב – O(n2)O(n^2).

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

א.

נתונה הפעולה `What` המקבלת שתי מחרוזות `s1` ו-`s2`:

C#:

public static bool What(string s1, string s2)  {
  if(s1.Equals(s2)) return false;
  for(int i=0; i<s1.Length; i++)
  {
    int pos = s2.IndexOf(s1[i]);
    if(pos == -1) return false;
    s2 = s2.Substring(0,pos) + s2.Substring(pos+1);
  }
  return true;
}

Java:

public static boolean what(String s1, String s2)  {
  if(s1.equals(s2)) return false;
  for(int i=0; i<s1.length(); i++)
  {
    int pos = s2.indexOf(s1.charAt(i));
    if(pos == -1) return false;
    s2 = s2.substring(0,pos) + s2.substring(pos+1);
  }
  return true;
}
(1)

עקבו בעזרת טבלת המעקב אחרי זימון `What("HELLO","HELPME")` ורשמו מה תהיה תוצאת הזימון.

(2)

נתונה הטענה הבאה: אם זימון הפעולה `What(s1, s2)` מחזיר ערך `true`,

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

(3)

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

(6 נקודות)
ב.

נתונה הפעולה `Secret` המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה `What`:

C#:

public static bool Secret(string[] arr) {
    for (int i = 1; i<arr.Length; i++)
    {
        if (!What(arr[i], arr[0]))
            return false;
    }
    return true;
}

Java:

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

תנו דוגמה למערך `arr` בגודל שישה תאים הכולל מחרוזות שונות שעבורו הפעולה `Secret` תחזיר ערך `true`.

(2)

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

(3)

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

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

סעיף א

(1)
תשובה:

`false`

מה הפעולה עושה בכל סיבוב: לוקחת את התו `s1[i]`, מחפשת אותו ב-`s2`; אם לא נמצא (`pos == -1`) – מחזירה `false`; אם נמצא – מוחקת מ-`s2` את המופע הראשון שלו (משרשרת את מה שלפניו עם מה שאחריו).

נעקוב, עם `s1 = "HELLO"`, `s2 = "HELPME"`:

שלב`i``s1[i]``s2` לפני`pos``s2` אחרי
בדיקת שוויון––`"HELPME"`–`"HELLO"` שונה מ-`"HELPME"`, ממשיכים
10`'H'``"HELPME"`0`"ELPME"`
21`'E'``"ELPME"`0`"LPME"`
32`'L'``"LPME"`0`"PME"`
43`'L'``"PME"`−1-1`return false`

ב-`"HELPME"` יש רק `'L'` אחת. היא "נוצלה" עבור ה-`'L'` הראשונה של `"HELLO"`, ולכן עבור ה-`'L'` השנייה כבר אין `'L'` ב-`s2` והפעולה מחזירה `false`.

תשובה: תוצאת הזימון היא `false`.

(2)
תשובה:

לא נכונה. למשל `What("AB","ABC")` מחזיר `true` ואילו `What("ABC","AB")` מחזיר `false`.

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

1. `What(s1, s2)` מחזירה `true` כאשר כל תו של `s1` (כולל חזרות) נמצא ב-`s2`. אין שום דרישה שכל התווים של `s2` יופיעו ב-`s1` – `s2` יכולה להכיל תווים נוספים.

2. ניקח `s1 = "AB"`, `s2 = "ABC"`: המחרוזות שונות; `'A'` נמצא ונמחק (`s2 = "BC"`), `'B'` נמצא ונמחק (`s2 = "C"`). הלולאה הסתיימה – מוחזר `true`.

3. בכיוון ההפוך, `What("ABC", "AB")`: `'A'` ו-`'B'` נמצאים ונמחקים, ו-`s2` נעשית `""`; התו `'C'` אינו נמצא – מוחזר `false`.

תשובה: הטענה אינה נכונה – `What("AB","ABC")` מחזיר `true` אבל `What("ABC","AB")` מחזיר `false`.

(3)
תשובה:

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

1. אם המחרוזות שוות – מוחזר `false` מיד.

2. אחרת, כל תו של `s1` מחפשים ב-`s2`. כשהוא נמצא, מוחקים מ-`s2` מופע אחד שלו, כך שכל תו של `s2` יכול "לשמש" רק פעם אחת. לכן אם תו מופיע ב-`s1` שלוש פעמים, הוא צריך להופיע ב-`s2` לפחות שלוש פעמים.

3. אם תו כלשהו לא נמצא – `false`; אם כל התווים נמצאו – `true`.

הסדר של התווים אינו חשוב: למשל `What("AB","BA")` מחזיר `true`.

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

סעיף ב

(1)
תשובה:

`{"COMPUTER", "CUT", "TOP", "MORE", "PET", "ROPE"}`

מה צריך: `Secret` מחזירה `true` אם לכל `i` מ-1 והלאה `What(arr[i], arr[0])` מחזירה `true`, כלומר כל מחרוזת שאינה הראשונה שונה מ-`arr[0]` ובנויה מהתווים של `arr[0]`.

לכן בוחרים מחרוזת ראשונה "עשירה" בתווים, ואחריה חמש מחרוזות שונות הבנויות מהתווים שלה:

`arr = {"COMPUTER", "CUT", "TOP", "MORE", "PET", "ROPE"}`

בדיקה: ב-`"COMPUTER"` יש כל אחד מהתווים C, O, M, P, U, T, E, R פעם אחת.

•`"CUT"` – C, U, T נמצאים;

•`"TOP"` – T, O, P נמצאים;

•`"MORE"` – M, O, R, E נמצאים;

•`"PET"` – P, E, T נמצאים;

•`"ROPE"` – R, O, P, E נמצאים.

אף מחרוזת אינה מכילה תו פעמיים, וכולן שונות מ-`"COMPUTER"`, ולכן כל זימוני `What` מחזירים `true` והפעולה מחזירה `true`. כל שש המחרוזות שונות זו מזו.

תשובה: למשל `{"COMPUTER", "CUT", "TOP", "MORE", "PET", "ROPE"}`.

(2)
תשובה:

לא נכונה. למשל עבור `{"ABC", "A", "A"}` הפעולה מחזירה `true` אף שיש שתי מחרוזות זהות.

1. `Secret` משווה כל מחרוזת רק ל-`arr[0]`. מ-`What` נובע ש-`arr[i]` שונה מ-`arr[0]` (אחרת `What` מחזירה `false`), ולכן אף מחרוזת אינה זהה ל-`arr[0]`.

2. אבל אין שום השוואה בין `arr[i]` ל-`arr[j]` כאשר i,j≥1i, j \ge 1, ולכן שתיים מהן יכולות להיות זהות.

3. דוגמה נגדית: `arr = {"ABC", "A", "A"}`. `What("A","ABC")` מחזירה `true` (המחרוזות שונות ו-`'A'` נמצא) – פעמיים. לכן `Secret` מחזירה `true`, אבל `arr[1]` ו-`arr[2]` זהות.

תשובה: הטענה אינה נכונה – למשל `{"ABC", "A", "A"}`: מוחזר `true` ויש בו זוג מחרוזות זהות. (נכון רק שאף מחרוזת אינה זהה ל-`arr[0]`.)

(3)
תשובה:

מחזירה `true` אם כל מחרוזת במערך, פרט לראשונה, שונה מ-`arr[0]` וניתן לבנות אותה מתווי `arr[0]` (כל תו לכל היותר כמספר הופעותיו ב-`arr[0]`); אחרת `false`.

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

תשובה: הפעולה בודקת אם כל אחת מהמחרוזות `arr[1], arr[2], ...` שונה מהמחרוזת הראשונה וניתן להרכיב אותה מאותיות המחרוזת הראשונה (כל אות לכל היותר כמספר הופעותיה ב-`arr[0]`). אם כן – `true`, אחרת – `false`.

שאלה 8 · רמת זוגיות של מספר ומערכים זרים

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

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

לדוגמה:

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

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

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

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

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

א.

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

(4 נקודות)
ב.

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

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

(4 נקודות)
ג.

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

(4 נקודות)
ד.

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

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

סעיף א

תשובה:

מפרקים את ∣num∣|num| לספרות בעזרת `%10` ו-`/10` ומסכמים את הספרות הזוגיות.

הרעיון: עוברים על ספרות המספר מימין לשמאל: `num % 10` היא הספרה הימנית, ו-`num / 10` מוחק אותה. כל ספרה זוגית מוסיפים לסכום. המספר יכול להיות שלילי (כמו −1860-1860), ולכן עובדים עם הערך המוחלט – הסימן אינו ספרה.

1. `num = |num|`, `sum = 0`.

2. כל עוד `num > 0`: `digit = num % 10`; אם `digit % 2 == 0` – מוסיפים ל-`sum`; `num /= 10`.

3. מחזירים `sum`.

בדיקה עם הדוגמאות: 1234712347 – הספרות הזוגיות 4,24, 2, הסכום 66. −1860-1860 – הספרות הזוגיות 0,6,80, 6, 8, הסכום 1414. 135135 – אין ספרות זוגיות, הסכום 00.

C#:

public static int EvenLevel(int num)
{
    num = Math.Abs(num);              // הסימן לא משפיע על הספרות
    int sum = 0;
    while (num > 0)
    {
        int digit = num % 10;         // הספרה הימנית
        if (digit % 2 == 0)
            sum += digit;
        num /= 10;                    // מוחקים אותה
    }
    return sum;
}

Java:

public static int evenLevel(int num)
{
    num = Math.abs(num);              // הסימן לא משפיע על הספרות
    int sum = 0;
    while (num > 0)
    {
        int digit = num % 10;         // הספרה הימנית
        if (digit % 2 == 0)
            sum += digit;
        num /= 10;                    // מוחקים אותה
    }
    return sum;
}

תשובה: הפעולה `EvenLevel` / `evenLevel` שלמעלה.

סעיף ב

תשובה:

משווים את רמת הזוגיות של כל זוג איברים `i < j`; אם נמצא זוג עם רמה שווה – `false`; אחרת `true`.

הרעיון: "כל הרמות שונות זו מזו" פירושו שאין זוג איברים עם אותה רמה. לכן עוברים על כל הזוגות `i < j` (כל זוג פעם אחת) ומשווים את רמות הזוגיות שלהם בעזרת הפעולה מסעיף א.

1. לולאה חיצונית על `i` מ-0 עד `length - 2`, ולולאה פנימית על `j` מ-`i + 1` עד הסוף.

2. אם `EvenLevel(arr[i]) == EvenLevel(arr[j])` – מחזירים `false`.

3. אם לא נמצא זוג כזה – `true`.

למשל `{12347, -1860, 135}` – רמות 6,14,06, 14, 0 – שונות, מוחזר `true`; `{24, 42}` – שתיהן ברמה 66, מוחזר `false`.

C#:

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

Java:

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

תשובה: הפעולה `NoRepeat` / `noRepeat` שלמעלה.

סעיף ג

תשובה:

אם אחד המערכים אינו "בלי חזרות רמה" – `false`; אחרת משווים את רמת כל איבר של `arr1` לרמת כל איבר של `arr2`; אם נמצאה רמה משותפת – `false`, אחרת `true`.

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

1. כל מערך בפני עצמו – "מערך בלי חזרות רמה". משתמשים בפעולה מסעיף ב: אם `NoRepeat(arr1)` או `NoRepeat(arr2)` מחזירה `false` – מחזירים `false`.

2. בין המערכים – אין זוג (איבר מ-`arr1` ואיבר מ-`arr2`) עם אותה רמה. לולאה כפולה: לכל `i` ב-`arr1` ולכל `j` ב-`arr2` משווים `EvenLevel(arr1[i])` ל-`EvenLevel(arr2[j])`; אם הן שוות – `false`.

3. אם שני התנאים עברו – `true`.

למשל `{12347, 135}` (רמות 6,06, 0) ו-`{-1860, 8}` (רמות 14,814, 8) – כל מערך בלי חזרות ואין רמה משותפת, מוחזר `true`. אבל `{12347, 135}` ו-`{6}` – הרמה 66 משותפת, מוחזר `false`.

C#:

public static bool Strangers(int[] arr1, int[] arr2)
{
    if (!NoRepeat(arr1) || !NoRepeat(arr2))
        return false;
    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < arr2.Length; j++)
        {
            if (EvenLevel(arr1[i]) == EvenLevel(arr2[j]))
                return false;
        }
    }
    return true;
}

Java:

public static boolean strangers(int[] arr1, int[] arr2)
{
    if (!noRepeat(arr1) || !noRepeat(arr2))
        return false;
    for (int i = 0; i < arr1.length; i++)
    {
        for (int j = 0; j < arr2.length; j++)
        {
            if (evenLevel(arr1[i]) == evenLevel(arr2[j]))
                return false;
        }
    }
    return true;
}

תשובה: הפעולה `Strangers` / `strangers` שלמעלה.

סעיף ד

תשובה:

א: O(d)O(d) – מספר הספרות (קבוע עבור int, כלומר O(1)O(1)); ב: O(n2)O(n^2); ג: O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m).

נסמן ב-nn את גודל המערך (בסעיף ג – nn גודל `arr1` ו-mm גודל `arr2`), וב-dd את מספר הספרות במספר.

•סעיף א: הלולאה רצה פעם אחת לכל ספרה – O(d)O(d). מספר מטיפוס `int` הוא בן 10 ספרות לכל היותר, ולכן זה זמן קבוע, O(1)O(1).

•סעיף ב: הלולאה הכפולה עוברת על כל הזוגות: n(n−1)2\frac{n(n-1)}{2} השוואות, וכל השוואה מזמנת את פעולת סעיף א בזמן קבוע – O(n2)O(n^2).

•סעיף ג: שני זימונים של סעיף ב – O(n2)+O(m2)O(n^2)+O(m^2), ועוד לולאה כפולה של n⋅mn\cdot m השוואות – בסך הכול O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m). אם שני המערכים בגודל nn – O(n2)O(n^2).

תשובה: א – O(1)O(1) (לינארי במספר הספרות); ב – O(n2)O(n^2); ג – O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m), כלומר O(n2)O(n^2) למערכים בגודל דומה.

שאלה 9 · מתחם קניות: עסקים, דמי ארנונה והוספה

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

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

למערכת שתי מחלקות:

המחלקה `Business` מייצגת עסק במתחם. למחלקה התכונות הבאות:

•שם העסק – `name`, מטיפוס מחרוזת, `string`

•סוג העסק – `type`, מטיפוס מחרוזת, `string` (סוג העסק: חנות, מסעדה, בית קפה וכו')

•שטח העסק – `area`, מטיפוס מספר שלם, `int`

•שם בעל העסק – `owner`, מטיפוס מחרוזת, `string`

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

•שם המתחם – `name`, מטיפוס מחרוזת, `string`

•רשימת עסקים – `busArr`, מטיפוס מערך עצמים מסוג `Business`

•שטח פנוי במתחם – `freeArea`, מסוג מספר שלם, `int`

•מספר עסקים בפועל – `current`, מסוג מספר שלם, `int`

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

א.

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

•עבור מסעדה – 150 ₪ למ"ר

•עבור בית קפה – 120 ₪ למ"ר

•עבור חנות מוצרי מזון – 100 ₪ למ"ר

•עבור כל סוג עסק אחר – 80 ₪ למ"ר

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

(3 נקודות)
ב.

כתבו במחלקה `ShoppingCenter` פעולה בונה המייצרת מתחם קניות ללא בתי העסק.

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

C#:

public ShoppingCenter(string name, int totalArea)

Java:

public ShoppingCenter(String name, int totalArea)
(3 נקודות)
ג.

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

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

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

C#:

public bool AddBusiness(string name, string type, int area,
                        string owner)

Java:

public boolean addBusiness(String name, String type, int area,
                           String owner)

שימו לב: לא ניתן להוסיף עסק אם רשימת העסקים מלאה.

(4 נקודות)
ד.

כתבו פעולה המקבלת מערך שמות של בעלי עסקים `owners` ומדפיסה לכל בעל עסק את סך כל תשלומי הארנונה שעליו לשלם (עבור כל העסקים שבבעלותו).

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

C#:

public void PrintRent(string[] owner)

Java:

public void printRent(String[] owner)
(5 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

בוחרים מחיר למ"ר לפי `type` (150 / 120 / 100 / 80) ומחזירים מחיר × `area`.

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

1. שרשרת `if` / `else if` משווה את `type` למחרוזות `"מסעדה"`, `"בית קפה"`, `"חנות מוצרי מזון"`; כל סוג אחר מקבל 80.

2. מחזירים `price * area`. שני הגורמים שלמים, ולכן גם התוצאה שלמה (₪).

למשל מסעדה בשטח 100 מ"ר: 150⋅100=15000150\cdot 100=15000 ₪; בית קפה בשטח 50 מ"ר: 120⋅50=6000120\cdot 50=6000 ₪.

C#:

// במחלקה Business
public int CalculateRent()
{
    int price;                         // מחיר למ"ר לפי סוג העסק
    if (this.type == "מסעדה")
        price = 150;
    else if (this.type == "בית קפה")
        price = 120;
    else if (this.type == "חנות מוצרי מזון")
        price = 100;
    else
        price = 80;
    return price * this.area;
}

Java:

// במחלקה Business
public int calculateRent()
{
    int price;                         // מחיר למ"ר לפי סוג העסק
    if (this.type.equals("מסעדה"))
        price = 150;
    else if (this.type.equals("בית קפה"))
        price = 120;
    else if (this.type.equals("חנות מוצרי מזון"))
        price = 100;
    else
        price = 80;
    return price * this.area;
}

תשובה: הפעולה `CalculateRent` / `calculateRent` שלמעלה.

סעיף ב

תשובה:

`name` מהפרמטר, `busArr = new Business[120]`, `freeArea = totalArea`, `current = 0`.

הרעיון: מתחם חדש עדיין ריק מעסקים, ולכן:

1. `name` – מהפרמטר.

2. `busArr` – מערך חדש בגודל 120 (מספר העסקים המרבי במתחם); כל התאים `null`.

3. `freeArea` – אין עסקים, ולכן כל השטח `totalArea` פנוי.

4. `current = 0` – אין עדיין עסקים. המשתנה משמש גם כמקום הפנוי הבא במערך.

C#:

// במחלקה ShoppingCenter
public ShoppingCenter(string name, int totalArea)
{
    this.name = name;
    this.busArr = new Business[120];   // מקום ל-120 עסקים
    this.freeArea = totalArea;         // עדיין אין עסקים - כל השטח פנוי
    this.current = 0;
}

Java:

// במחלקה ShoppingCenter
public ShoppingCenter(String name, int totalArea)
{
    this.name = name;
    this.busArr = new Business[120];   // מקום ל-120 עסקים
    this.freeArea = totalArea;         // עדיין אין עסקים - כל השטח פנוי
    this.current = 0;
}

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

סעיף ג

תשובה:

אם `current` שווה לגודל המערך, או `area > freeArea`, או יש כבר עסק בשם זה – `false`; אחרת יוצרים עסק חדש ב-`busArr[current]`, מגדילים את `current`, מפחיתים את `area` מ-`freeArea` ומחזירים `true`.

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

1. הרשימה מלאה: `current == busArr.length` – מחזירים `false`.

2. אין מספיק שטח: `area > freeArea` – מחזירים `false`.

3. שם תפוס: עוברים על העסקים הקיימים בלבד (`i < current`, התאים שאחריהם `null`) ומשווים את שמם ל-`name`. אם נמצא שם זהה – `false`.

4. הוספה: יוצרים עצם `Business` חדש עם הבנאי של המחלקה (המקבל ערך לכל תכונה) ושמים אותו ב-`busArr[current]`. אחר כך מעדכנים את התכונות הרלוונטיות: `current++` (עסק נוסף) ו-`freeArea -= area` (השטח נתפס). מחזירים `true`.

C#:

// במחלקה ShoppingCenter
public bool AddBusiness(string name, string type, int area, string owner)
{
    if (this.current == this.busArr.Length)    // רשימת העסקים מלאה
        return false;
    if (area > this.freeArea)                  // אין מספיק שטח פנוי
        return false;
    for (int i = 0; i < this.current; i++)     // האם כבר יש עסק בשם זה
    {
        if (this.busArr[i].GetName() == name)
            return false;
    }
    this.busArr[this.current] = new Business(name, type, area, owner);
    this.current++;
    this.freeArea -= area;
    return true;
}

Java:

// במחלקה ShoppingCenter
public boolean addBusiness(String name, String type, int area, String owner)
{
    if (this.current == this.busArr.length)    // רשימת העסקים מלאה
        return false;
    if (area > this.freeArea)                  // אין מספיק שטח פנוי
        return false;
    for (int i = 0; i < this.current; i++)     // האם כבר יש עסק בשם זה
    {
        if (this.busArr[i].getName().equals(name))
            return false;
    }
    this.busArr[this.current] = new Business(name, type, area, owner);
    this.current++;
    this.freeArea -= area;
    return true;
}

דוגמה: במתחם בשטח 1000 מ"ר מוסיפים מסעדה של 100 מ"ר ובית קפה של 50 מ"ר – שתי ההוספות מצליחות, ו-`freeArea` יורד ל-850. ניסיון להוסיף עסק נוסף באחד השמות האלה ייכשל, וגם עסק בשטח 900 מ"ר ייכשל, כי 900>850900>850.

תשובה: הפעולה `AddBusiness` / `addBusiness` שלמעלה.

סעיף ד

תשובה:

לכל שם `owner[k]` עוברים על כל העסקים במתחם, מסכמים `CalculateRent()` של העסקים שבעליהם הוא `owner[k]`, ומדפיסים את השם ואת הסכום.

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

1. לולאה חיצונית על השמות `owner[k]` (בכותרת הפרמטר נקרא `owner`).

2. לכל שם: `sum = 0`, ולולאה פנימית על העסקים הקיימים `busArr[0..current-1]`.

3. אם בעל העסק `busArr[i]` הוא `owner[k]` – מוסיפים ל-`sum` את `busArr[i].calculateRent()`.

4. אחרי הלולאה הפנימית מדפיסים את השם ואת `sum`. (בעל עסק בלי עסקים במתחם יקבל 0.)

C#:

// במחלקה ShoppingCenter
public void PrintRent(string[] owner)
{
    for (int k = 0; k < owner.Length; k++)
    {
        int sum = 0;                           // סך הארנונה של בעל העסקים owner[k]
        for (int i = 0; i < this.current; i++)
        {
            if (this.busArr[i].GetOwner() == owner[k])
                sum += this.busArr[i].CalculateRent();
        }
        Console.WriteLine(owner[k] + ": " + sum);
    }
}

Java:

// במחלקה ShoppingCenter
public void printRent(String[] owner)
{
    for (int k = 0; k < owner.length; k++)
    {
        int sum = 0;                           // סך הארנונה של בעל העסקים owner[k]
        for (int i = 0; i < this.current; i++)
        {
            if (this.busArr[i].getOwner().equals(owner[k]))
                sum += this.busArr[i].calculateRent();
        }
        System.out.println(owner[k] + ": " + sum);
    }
}

דוגמה: ל-Dan מסעדה של 100 מ"ר ובית קפה של 50 מ"ר: 15000+6000=2100015000+6000=21000. ל-Rina חנות מוצרי מזון של 200 מ"ר ועסק אחר של 10 מ"ר: 20000+800=2080020000+800=20800. יודפס `Dan: 21000` ו-`Rina: 20800`.

תשובה: הפעולה `PrintRent` / `printRent` שלמעלה.

שאלה 10 · מעקב אחר פעולות החלפה ומיון

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

C#:

public static int One ( int[] arr ){
  int res = -1;
  for (int k = 0; k < arr.Length-1 && res  == -1; k++)
      if (arr[k] > arr[k+1])
            res = k;
  return res;
}
public static void Two ( int[] arr, int k ){
  int temp = arr[k];
  arr[k] = arr[k+1];
  arr[k+1] = temp;
}
public static void Three ( int[] arr ){
  int k = One( arr );
  while (k != -1)
   {
     Two( arr, k );
     k = One( arr );
   }
}

Java:

public static int one ( int[] arr ){
  int res = -1;
  for (int k = 0; k < arr.length-1 && res  == -1; k++)
      if (arr[k] > arr[k+1])
            res = k;
  return res;
}
public static void two ( int[] arr, int k ){
  int temp = arr[k];
  arr[k] = arr[k+1];
  arr[k+1] = temp;
}
public static void three ( int[] arr ){
  int k = one( arr );
  while (k != -1)
   {
     two( arr, k );
     k = one( arr );
   }
}
א.

עקבו בעזרת טבלת המעקב ורשמו מה יחזיר זימון הפעולה `One(arrA)` עבור המערך:

int[] arrA = {8, 9, 20, 17, -3, 1, 4};
(5 נקודות)
ב.

מה יחזיר זימון הפעולה `One(arrB)` עבור המערך:

int[] arrB = {-5, -3, 0, 11, 13, 15, 18};
(1 נקודות)
ג.

תנו דוגמה למערך `arrC` בגודל שישה תאים שעבורו הזימון `One(arrC)` יחזיר 4.

(1 נקודות)
ד.

נתון מערך `int[] arrD = {7, 9, 2, 8, 3, 1}`.

עקבו בעזרת טבלת המעקב ורשמו מה יהיה התוכן של המערך אחרי זימון הפעולה `Three(arrD)`.

אין צורך להראות מעקב אחרי הפעולות `One` ו-`Two`.

(5 נקודות)
ה.

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

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

סעיף א

תשובה:

2

מה הפעולה `One` עושה בכל סיבוב: משווה את `arr[k]` לאיבר שאחריו. אם `arr[k] > arr[k+1]`, נשמר `res = k`, ובסיבוב הבא תנאי הלולאה `res == -1` כבר נכשל – הלולאה נעצרת.

אורך המערך 7, ולכן `k < 6`:

שלב`k``k < 6 && res == -1``arr[k]``arr[k+1]``arr[k] > arr[k+1]``res`
אתחול–––––−1-1
10true89false−1-1
21true920false−1-1
32true2017true2
43false (`res` אינו −1-1)–––2

הירידה הראשונה במערך היא בין 20 (מקום 2) ל-17 (מקום 3).

תשובה: הזימון `One(arrA)` מחזיר 2.

סעיף ב

תשובה:

−1-1

המערך ממוין בסדר עולה: −5<−3<0<11<13<15<18-5<-3<0<11<13<15<18. לכן לאף `k` לא מתקיים `arr[k] > arr[k+1]`, `res` נשאר −1-1 והלולאה רצה עד `k = 6`.

תשובה: מוחזר −1-1.

סעיף ג

תשובה:

למשל `{1, 2, 3, 4, 9, 5}`

`One` מחזירה את המקום הראשון `k` שבו `arr[k] > arr[k+1]`. כדי לקבל 4 צריך:

•המקומות 0 עד 4 בסדר עולה (אין ירידה לפני מקום 4);

•`arr[4] > arr[5]`.

למשל `arrC = {1, 2, 3, 4, 9, 5}`: 1<2<3<4<91<2<3<4<9, ו-9>59>5.

תשובה: למשל `{1, 2, 3, 4, 9, 5}`.

סעיף ד

תשובה:

`{1, 2, 3, 7, 8, 9}`

מה `Three` עושה: `One` מוצאת את המקום הראשון `k` שבו איבר גדול מהאיבר שאחריו, ו-`Two` מחליפה בין שני האיברים האלה. החזרה ממשיכה עד ש-`One` מחזירה −1-1, כלומר עד שאין אף זוג סמוך בסדר הפוך.

בכל שורה בטבלה: הערך ש-`One` החזירה, והמערך אחרי ההחלפה:

סיבוב`k = One(arr)`הזוג שמוחלףהמערך אחרי `Two(arr, k)`
התחלה––`{7, 9, 2, 8, 3, 1}`
119, 2`{7, 2, 9, 8, 3, 1}`
207, 2`{2, 7, 9, 8, 3, 1}`
329, 8`{2, 7, 8, 9, 3, 1}`
439, 3`{2, 7, 8, 3, 9, 1}`
528, 3`{2, 7, 3, 8, 9, 1}`
617, 3`{2, 3, 7, 8, 9, 1}`
749, 1`{2, 3, 7, 8, 1, 9}`
838, 1`{2, 3, 7, 1, 8, 9}`
927, 1`{2, 3, 1, 7, 8, 9}`
1013, 1`{2, 1, 3, 7, 8, 9}`
1102, 1`{1, 2, 3, 7, 8, 9}`
סיום−1-1–`{1, 2, 3, 7, 8, 9}`

אחרי 11 החלפות אין יותר זוג סמוך שבו השמאלי גדול מהימני, `One` מחזירה −1-1 והלולאה נעצרת.

תשובה: אחרי הזימון `arrD = {1, 2, 3, 7, 8, 9}`.

סעיף ה

תשובה:

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

1. כל עוד יש במערך זוג סמוך בסדר הפוך (`arr[k] > arr[k+1]`), `One` מוצאת את הראשון שבהם ו-`Two` מחליפה ביניהם.

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

3. הלולאה נעצרת רק כש-`One` מחזירה −1-1, כלומר `arr[k] <= arr[k+1]` לכל `k` – המערך ממוין בסדר עולה.

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

תשובה: הפעולה ממיינת את המערך `arr` בסדר עולה.

שאלה 11 · טורניר שחמט: מערך דו-ממדי של תוצאות

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

המחלקה `Player` מייצגת שחקן. למחלקה התכונות הבאות:

•שם השחקן – `name`, מסוג מחרוזת, `string`

•דירוג השחקן – `rating`, מסוג מספר שלם, `int`. דירוג השחקן מתעדכן לפי התוצאות הסופיות של הטורניר.

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

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

•רשימת השחקנים – `players`, מערך עצמים מסוג `Player`.

•לוח תוצאות המשחקים – `results` – מערך דו-ממדי של מספרים שלמים.

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

לדוגמה:

012
020
101
221

המערך הזה מייצג את התוצאות האלה:

•שחקן 0 ניצח את שחקן 1

•שחקן 2 ניצח את שחקן 0

•שחקן 1 ושחקן 2 סיימו בתיקו

כלומר, הערך `results[i, j]` מציין את התוצאה של השחקן `i` מול השחקן `j`.

נתונה פעולה בונה של המחלקה `Tournament`:

C#:

public Tournament(Player[] players) {
 this.players = players;
 this.results = new int[players.Length, players.Length];
}

Java:

public Tournament(Player[] players) {
 this.players = players;
 this.results = new int[players.length][players.length];
}
א.

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

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

C#:

public int GetPlayerIndexByName(string name)

Java:

public int getPlayerIndexByName(String name)
(3 נקודות)
ב.

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

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

C#:

public void PlayMatch(string name1, string name2, int result1)

Java:

public void playMatch(String name1, String name2, int result1)
(3 נקודות)
ג.

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

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

C#:

public string GetNameOfWinnerPlayer()

Java:

public String getNameOfWinnerPlayer()
(4 נקודות)
ד.

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

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

C#:

public void UpdateRating()

Java:

public void updateRating()
(5 נקודות)
◂ פתרון מלא לשאלה 11

סעיף א

תשובה:

חיפוש סדרתי במערך `players`; מחזירים את האינדקס שבו השם שווה ל-`name`, או −1-1 אם אין שחקן כזה.

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

1. לולאה על `i` מ-0 עד סוף המערך.

2. אם `players[i].getName()` שווה ל-`name` – מחזירים `i`.

3. אם השם לא נמצא – מחזירים −1-1 (ערך שאינו אינדקס חוקי).

C#:

public int GetPlayerIndexByName(string name)
{
    for (int i = 0; i < this.players.Length; i++)
    {
        if (this.players[i].GetName() == name)
            return i;
    }
    return -1;                       // אין שחקן בשם זה
}

Java:

public int getPlayerIndexByName(String name)
{
    for (int i = 0; i < this.players.length; i++)
    {
        if (this.players[i].getName().equals(name))
            return i;
    }
    return -1;                       // אין שחקן בשם זה
}

תשובה: הפעולה `GetPlayerIndexByName` / `getPlayerIndexByName` שלמעלה.

סעיף ב

תשובה:

`i`, `j` – האינדקסים של שני השחקנים; `results[i][j] = result1`, `results[j][i] = 2 - result1`.

הרעיון: משחק אחד מעדכן שני תאים בלוח: את התוצאה של הראשון מול השני (`[i][j]`) ואת התוצאה של השני מול הראשון (`[j][i]`). בכל משחק מתחלקות בדיוק 2 נקודות: ניצחון–הפסד 2+02+0, תיקו 1+11+1. לכן אם לראשון יש `result1` נקודות, לשני יש 2−2-`result1`.

1. מוצאים את האינדקסים: `i = getPlayerIndexByName(name1)`, `j = getPlayerIndexByName(name2)` (הפעולה מסעיף א).

2. `results[i][j] = result1`.

3. `results[j][i] = 2 - result1`: אם `result1 = 2` לשני 0; אם 1 – גם לשני 1; אם 0 – לשני 2.

C#:

public void PlayMatch(string name1, string name2, int result1)
{
    int i = GetPlayerIndexByName(name1);
    int j = GetPlayerIndexByName(name2);
    this.results[i, j] = result1;          // הנקודות של השחקן הראשון
    this.results[j, i] = 2 - result1;      // הנקודות של השחקן השני
}

Java:

public void playMatch(String name1, String name2, int result1)
{
    int i = getPlayerIndexByName(name1);
    int j = getPlayerIndexByName(name2);
    this.results[i][j] = result1;          // הנקודות של השחקן הראשון
    this.results[j][i] = 2 - result1;      // הנקודות של השחקן השני
}

(ב-C# המערך הדו-ממדי הוא `int[,]` ונוצר בבנאי ב-`new int[players.Length, players.Length]`, והגישה לתא היא `results[i, j]`, כמו בנוסח השאלה.)

דוגמה: שלושת המשחקים של הדוגמה: `PlayMatch("P0","P1",2)`, `PlayMatch("P2","P0",2)`, `PlayMatch("P1","P2",1)` – בונים בדיוק את הלוח שבשאלה.

תשובה: הפעולה `PlayMatch` / `playMatch` שלמעלה.

סעיף ג

תשובה:

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

הרעיון: הנקודות של שחקן `i` מכל המשחקים שלו רשומות בשורה `i` של `results`. לכן סך הנקודות שלו הוא סכום השורה (התא `[i][i]` הוא 0 ולא משפיע). המנצח הוא השחקן עם הסכום הגדול ביותר – חיפוש מקסימום.

1. `bestSum = -1` (כל סכום גדול ממנו), `best = 0`.

2. לכל שחקן `i`: סוכמים את השורה `i`. אם הסכום גדול מ-`bestSum` – מעדכנים `bestSum` ו-`best = i`.

3. מחזירים `players[best].getName()`.

בדוגמה של השאלה: שחקן 0 – 2+0=22+0=2, שחקן 1 – 0+1=10+1=1, שחקן 2 – 2+1=32+1=3. המנצח הוא שחקן 2.

C#:

public string GetNameOfWinnerPlayer()
{
    int best = 0;                          // אינדקס המוביל עד כה
    int bestSum = -1;
    for (int i = 0; i < this.players.Length; i++)
    {
        int sum = 0;                       // סך הנקודות של שחקן i
        for (int j = 0; j < this.players.Length; j++)
            sum += this.results[i, j];
        if (sum > bestSum)
        {
            bestSum = sum;
            best = i;
        }
    }
    return this.players[best].GetName();
}

Java:

public String getNameOfWinnerPlayer()
{
    int best = 0;                          // אינדקס המוביל עד כה
    int bestSum = -1;
    for (int i = 0; i < this.players.length; i++)
    {
        int sum = 0;                       // סך הנקודות של שחקן i
        for (int j = 0; j < this.players.length; j++)
            sum += this.results[i][j];
        if (sum > bestSum)
        {
            bestSum = sum;
            best = i;
        }
    }
    return this.players[best].getName();
}

תשובה: הפעולה `GetNameOfWinnerPlayer` / `getNameOfWinnerPlayer` שלמעלה.

סעיף ד

תשובה:

לכל שחקן `i` סופרים בשורה `i` (בלי התא `[i][i]`) כמה תאים שווים 2 (ניצחונות) וכמה שווים 0 (הפסדים), ומציבים `rating + wins - losses`.

הרעיון: בשורה `i` של `results` רשומה התוצאה של שחקן `i` מול כל שחקן אחר: 2 – ניצחון, 1 – תיקו, 0 – הפסד. סופרים ניצחונות והפסדים ומעדכנים את הדירוג בעזרת `getRating` / `setRating`.

1. לכל שחקן `i`: `wins = 0`, `losses = 0`.

2. עוברים על העמודות `j` בשורה `i`, חוץ מ-`j == i` – התא `[i][i]` הוא 0, אבל זה לא משחק ואסור לספור אותו כהפסד.

3. ערך 2 – `wins++`; ערך 0 – `losses++`; ערך 1 (תיקו) לא משנה את הדירוג.

4. מעדכנים: `setRating(getRating() + wins - losses)`.

בדוגמה של השאלה: שחקן 0 – ניצחון אחד והפסד אחד, הדירוג לא משתנה; שחקן 1 – הפסד ותיקו, הדירוג יורד ב-1; שחקן 2 – ניצחון ותיקו, הדירוג עולה ב-1.

C#:

public void UpdateRating()
{
    for (int i = 0; i < this.players.Length; i++)
    {
        int wins = 0, losses = 0;
        for (int j = 0; j < this.players.Length; j++)
        {
            if (j != i)                    // התא [i, i] אינו משחק
            {
                if (this.results[i, j] == 2)
                    wins++;
                else if (this.results[i, j] == 0)
                    losses++;
            }
        }
        int r = this.players[i].GetRating();
        this.players[i].SetRating(r + wins - losses);
    }
}

Java:

public void updateRating()
{
    for (int i = 0; i < this.players.length; i++)
    {
        int wins = 0, losses = 0;
        for (int j = 0; j < this.players.length; j++)
        {
            if (j != i)                    // התא [i][i] אינו משחק
            {
                if (this.results[i][j] == 2)
                    wins++;
                else if (this.results[i][j] == 0)
                    losses++;
            }
        }
        int r = this.players[i].getRating();
        this.players[i].setRating(r + wins - losses);
    }
}

תשובה: הפעולה `UpdateRating` / `updateRating` שלמעלה.

שאלה 12 · רשת מלונות: תכנון מחלקות והזמנות

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

לכל מלון שמורים הפרטים הבאים:

•שם המלון

•מיקום המלון (עיר)

•מערך החדרים במלון (לכל מלון יש לכל היותר 50 חדרים)

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

•סוג החדר (רגיל, משפחתי, סוויטה)

•מחיר ללילה

•סטטוס (פנוי, תפוס)

עבור כל הזמנה נשמרים הפרטים הבאים:

•שם המזמין

•שם המלון

•סוג החדר

•תאריך ההזמנה

•מספר לילות

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

א.

כתבו את כותרת המחלקה, את התכונות ואת הפעולות הבונות (בנאים) עבור כל אחת מהמחלקות:

•חדר `Room`

•מלון `Hotel`

•רשת מלונות `Chain`

•הזמנה `Reservation`

(4 נקודות)
ב.

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

(3 נקודות)
ג.

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

(1)

ציינו באיזו מחלקה צריך להוסיף מערך הזמנות (מערך עצמים מסוג `Reservation`).

(2)

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

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

סעיף א

תשובה:

`Room` (סוג, מחיר, פנוי/תפוס); `Hotel` (שם, עיר, `Room[50]` ומונה חדרים); `Chain` (שם, `Hotel[20]` ומונה מלונות); `Reservation` (מזמין, מלון, סוג חדר, תאריך, לילות) – כל אחת עם בנאי.

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

1. `Room` – `type` (מחרוזת: "רגיל", "משפחתי", "סוויטה"), `price` (ממשי – מחיר ללילה), `isFree` (בוליאני – `true` פנוי, `false` תפוס). הבנאי מקבל סוג ומחיר; חדר חדש פנוי.

2. `Hotel` – `name`, `city`, מערך `rooms` בגודל 50 (המספר המרבי של חדרים) ו-`numRooms` – מספר החדרים בפועל. הבנאי יוצר מלון בלי חדרים; חדרים מוסיפים בפעולה `addRoom`.

3. `Chain` – `name`, מערך `hotels` בגודל 20 (ברשת 20 מלונות) ו-`numHotels`.

4. `Reservation` – `customer`, `hotelName`, `roomType`, `date` (מחרוזת, למשל "15/04/2025"), `nights` (שלם). הבנאי מקבל את כל הפרטים.

לכל מחלקה מוסיפים פעולות Get לפי הצורך (כאן מוצגות רק אלה שמשמשות בסעיפים הבאים). ב-C# הפעולה שמחזירה את סוג החדר נקראת `GetRoomType`, כדי לא להתנגש בפעולה `GetType` הקיימת בכל עצם.

C#:

public class Room
{
    private string type;      // סוג החדר: "רגיל", "משפחתי", "סוויטה"
    private double price;     // מחיר ללילה
    private bool isFree;      // סטטוס: true - פנוי, false - תפוס

    public Room(string type, double price)
    {
        this.type = type;
        this.price = price;
        this.isFree = true;   // חדר חדש פנוי
    }
    public string GetRoomType() { return this.type; }
    public bool GetIsFree() { return this.isFree; }
}

public class Hotel
{
    private string name;      // שם המלון
    private string city;      // מיקום המלון (עיר)
    private Room[] rooms;     // מערך החדרים - לכל היותר 50
    private int numRooms;     // מספר החדרים בפועל

    public Hotel(string name, string city)
    {
        this.name = name;
        this.city = city;
        this.rooms = new Room[50];
        this.numRooms = 0;
    }
    public string GetName() { return this.name; }
    public bool AddRoom(Room r)
    {
        if (this.numRooms == this.rooms.Length) return false;
        this.rooms[this.numRooms] = r;
        this.numRooms++;
        return true;
    }
}

public class Chain
{
    private string name;      // שם הרשת
    private Hotel[] hotels;   // 20 בתי המלון של הרשת
    private int numHotels;    // מספר המלונות שנוספו בפועל

    public Chain(string name)
    {
        this.name = name;
        this.hotels = new Hotel[20];
        this.numHotels = 0;
    }
}

public class Reservation
{
    private string customer;  // שם המזמין
    private string hotelName; // שם המלון
    private string roomType;  // סוג החדר
    private string date;      // תאריך ההזמנה, למשל "15/04/2025"
    private int nights;       // מספר לילות

    public Reservation(string customer, string hotelName, string roomType,
                       string date, int nights)
    {
        this.customer = customer;
        this.hotelName = hotelName;
        this.roomType = roomType;
        this.date = date;
        this.nights = nights;
    }
    public string GetHotelName() { return this.hotelName; }
    public string GetRoomType() { return this.roomType; }
}

Java:

public class Room
{
    private String type;      // סוג החדר: "רגיל", "משפחתי", "סוויטה"
    private double price;     // מחיר ללילה
    private boolean isFree;   // סטטוס: true - פנוי, false - תפוס

    public Room(String type, double price)
    {
        this.type = type;
        this.price = price;
        this.isFree = true;   // חדר חדש פנוי
    }
    public String getType() { return this.type; }
    public boolean getIsFree() { return this.isFree; }
}

public class Hotel
{
    private String name;      // שם המלון
    private String city;      // מיקום המלון (עיר)
    private Room[] rooms;     // מערך החדרים - לכל היותר 50
    private int numRooms;     // מספר החדרים בפועל

    public Hotel(String name, String city)
    {
        this.name = name;
        this.city = city;
        this.rooms = new Room[50];
        this.numRooms = 0;
    }
    public String getName() { return this.name; }
    public boolean addRoom(Room r)
    {
        if (this.numRooms == this.rooms.length) return false;
        this.rooms[this.numRooms] = r;
        this.numRooms++;
        return true;
    }
}

public class Chain
{
    private String name;      // שם הרשת
    private Hotel[] hotels;   // 20 בתי המלון של הרשת
    private int numHotels;    // מספר המלונות שנוספו בפועל

    public Chain(String name)
    {
        this.name = name;
        this.hotels = new Hotel[20];
        this.numHotels = 0;
    }
}

public class Reservation
{
    private String customer;  // שם המזמין
    private String hotelName; // שם המלון
    private String roomType;  // סוג החדר
    private String date;      // תאריך ההזמנה, למשל "15/04/2025"
    private int nights;       // מספר לילות

    public Reservation(String customer, String hotelName, String roomType,
                       String date, int nights)
    {
        this.customer = customer;
        this.hotelName = hotelName;
        this.roomType = roomType;
        this.date = date;
        this.nights = nights;
    }
    public String getHotelName() { return this.hotelName; }
    public String getRoomType() { return this.roomType; }
}

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

סעיף ב

תשובה:

סורקים את `rooms[0..numRooms-1]` וסופרים חדרים שסוגם שווה לסוג שהתקבל והם פנויים.

הרעיון: הפעולה נמצאת במחלקה `Hotel`, ולכן ניגשת ישירות למערך `rooms` ולמונה `numRooms`. עוברים רק על החדרים הקיימים (התאים שאחריהם `null`) וסופרים חדרים שמקיימים את שני התנאים: הסוג שווה ל-`type`, והחדר פנוי.

1. `count = 0`.

2. לכל `i` מ-0 עד `numRooms - 1`: אם `rooms[i].getType()` שווה ל-`type` וגם `rooms[i].getIsFree()` – `count++`.

3. מחזירים `count`.

C#:

// במחלקה Hotel
public int CountFree(string type)
{
    int count = 0;
    for (int i = 0; i < this.numRooms; i++)
    {
        if (this.rooms[i].GetRoomType() == type && this.rooms[i].GetIsFree())
            count++;
    }
    return count;
}

Java:

// במחלקה Hotel
public int countFree(String type)
{
    int count = 0;
    for (int i = 0; i < this.numRooms; i++)
    {
        if (this.rooms[i].getType().equals(type) && this.rooms[i].getIsFree())
            count++;
    }
    return count;
}

דוגמה: במלון עם שני חדרים משפחתיים פנויים וחדר רגיל פנוי: `countFree("משפחתי")` מחזירה 2, `countFree("רגיל")` מחזירה 1, ו-`countFree("סוויטה")` מחזירה 0.

תשובה: הפעולה `CountFree` / `countFree` שלמעלה.

סעיף ג

(1)
תשובה:

במחלקה `Chain` (רשת המלונות), יחד עם מונה ההזמנות.

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

C#:

// תכונות נוספות במחלקה Chain
private Reservation[] reservations;   // כל הזמנות הרשת
private int numRes;                   // מספר ההזמנות בפועל

// בפעולה הבונה של Chain מוסיפים:
//     this.reservations = new Reservation[1000];
//     this.numRes = 0;

Java:

// תכונות נוספות במחלקה Chain
private Reservation[] reservations;   // כל הזמנות הרשת
private int numRes;                   // מספר ההזמנות בפועל

// בפעולה הבונה של Chain מוסיפים:
//     this.reservations = new Reservation[1000];
//     this.numRes = 0;

(הגודל 1000 הוא בחירה – השאלה לא מגבילה את מספר ההזמנות.)

תשובה: במחלקה `Chain`.

(2)
תשובה:

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

הרעיון: עוברים על כל ההזמנות של הרשת (`reservations[0..numRes-1]`) וסופרים את אלה שמקיימות את שני התנאים: שם המלון בהזמנה שווה ל-`hotelName`, וסוג החדר הוא "משפחתי".

1. `count = 0`.

2. לכל הזמנה: אם `getHotelName()` שווה ל-`hotelName` וגם `getRoomType()` שווה ל-`"משפחתי"` – `count++`.

3. מחזירים `count`.

C#:

// במחלקה Chain
public int CountFamily(string hotelName)
{
    int count = 0;
    for (int i = 0; i < this.numRes; i++)
    {
        if (this.reservations[i].GetHotelName() == hotelName
                && this.reservations[i].GetRoomType() == "משפחתי")
            count++;
    }
    return count;
}

Java:

// במחלקה Chain
public int countFamily(String hotelName)
{
    int count = 0;
    for (int i = 0; i < this.numRes; i++)
    {
        if (this.reservations[i].getHotelName().equals(hotelName)
                && this.reservations[i].getRoomType().equals("משפחתי"))
            count++;
    }
    return count;
}

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

תשובה: הפעולה `CountFamily` / `countFamily` שלמעלה.

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

נתונות הפעולות `Why`, `What` ו-`WhyHelp`:

C#:

public static bool What(string s, char c, int k)
 {
   if(k == 0 && s.Length == 0) return true;
   if(s.Length == 0) return false;
   if(k < 0 ) return false;
   if(s[0] == c) return What(s.Substring(1),c, k-1);
   return What(s.Substring(1),c, k);
 }
 public static bool Why(char[] arr, string s)
 {
   return WhyHelp(arr, s, 0);
 }
 public static bool WhyHelp(char[] arr, string s, int k)
 {
   if(k == arr.Length) return true;
   if(!What(s, arr[k], k+1)) return false;
   return WhyHelp(arr, s, k+1);
 }

Java:

public static boolean what(String s, char c, int k)
 {
   if(k == 0 && s.length()==0) return true;
   if(s.length() == 0) return false;
   if(k < 0 ) return false;
   if(s.charAt(0)== c) return what(s.substring(1),c, k-1);
   return what(s.substring(1),c, k);
 }
 public static boolean why(char[] arr, String s)
 {
   return whyHelp(arr, s, 0);
 }
 public static boolean whyHelp(char[] arr, String s, int k)
 {
   if(k == arr.length) return true;
   if(!what(s, arr[k], k+1)) return false;
   return whyHelp(arr, s, k+1);
 }
א.

עקבו אחרי זימון `What("HELLO",'L',3)` ורשמו את תוצאת הזימון.

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

(3 נקודות)
ב.

תנו דוגמה למחרוזת `s` באורך חמישה תווים לפחות שעבורה זימון `What(s,'T',2)` יחזיר ערך `true`.

(1 נקודות)
ג.

מה מבצעת הפעולה `What(string s, char c, int k)` באופן כללי?

(1 נקודות)
ד.

נתונים מערך תווים

char[] arr = {'H','E','L','P'};

ומחרוזת

string s = "APHEEKLPPLVLZTP";

עקבו אחרי הזימון `Why(arr, s)` ורשמו את תוצאות הזימון.

(4 נקודות)
ה.

תנו דוגמה למחרוזת הקצרה ביותר `str` שעבורה זימון הפעולה `Why(arr, str)` יחזיר ערך `true`.

(1 נקודות)
ו.

מה מבצעת הפעולה `Why(arr, s)` באופן כללי?

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

סעיף א

תשובה:

`false`

מה הפעולה עושה בכל זימון: בודקת את התו הראשון של `s`. אם הוא `c` – ממשיכה עם שאר המחרוזת ו-`k-1`; אחרת – עם שאר המחרוזת ואותו `k`. כשהמחרוזת מתרוקנת: אם `k == 0` מוחזר `true`, אחרת `false`.

זימון`s``c``k``s[0] == c`מה מבוצע
1`"HELLO"``'L'`3false (`'H'`)`What("ELLO",'L',3)`
2`"ELLO"``'L'`3false (`'E'`)`What("LLO",'L',3)`
3`"LLO"``'L'`3true`What("LO",'L',2)`
4`"LO"``'L'`2true`What("O",'L',1)`
5`"O"``'L'`1false (`'O'`)`What("",'L',1)`
6`""``'L'`1–`k` אינו 0 ו-`s` ריקה: `return false`

הערך `false` חוזר דרך כל הזימונים אל הזימון הראשון. ב-`"HELLO"` יש רק שתי אותיות `'L'`, ולכן `k` ירד מ-3 רק עד 1 ולא הגיע ל-0.

תשובה: תוצאת הזימון היא `false`.

סעיף ב

תשובה:

למשל `"TATAA"`

לפי ניתוח הפעולה (סעיף ג), `What(s,'T',2)` מחזירה `true` כשהתו `'T'` מופיע ב-`s` בדיוק פעמיים. מחרוזת באורך 5 עם שתי אותיות `'T'` בדיוק: `"TATAA"`. בכל `'T'` הערך של `k` יורד ב-1 (מ-2 ל-0), ובסוף המחרוזת ריקה ו-`k == 0`, ולכן מוחזר `true`.

תשובה: למשל `s = "TATAA"`.

סעיף ג

תשובה:

מחזירה `true` אם התו `c` מופיע במחרוזת `s` בדיוק `k` פעמים, אחרת `false`.

כל זימון רקורסיבי "מוחק" את התו הראשון של `s`, ומקטין את `k` ב-1 רק כשהתו הזה הוא `c`. כשהמחרוזת מתרוקנת, `k` הוא הערך ההתחלתי פחות מספר המופעים של `c` ב-`s`. הפעולה מחזירה `true` רק אם אז `k == 0`, כלומר אם מספר המופעים שווה ל-`k`. התנאי `k < 0` עוצר מוקדם כשכבר נמצאו יותר מ-`k` מופעים.

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

סעיף ד

תשובה:

`true`

מה צריך: `Why(arr, s)` מזמנת `WhyHelp(arr, s, 0)`. בכל זימון `WhyHelp` בודקת, בעזרת `What`, אם התו `arr[k]` מופיע ב-`s` בדיוק `k+1` פעמים. אם כן – ממשיכה ל-`k+1`; אם לא – `false`. כש-`k` מגיע ל-4 (אורך `arr`) – `true`.

נספור את המופעים במחרוזת `"APHEEKLPPLVLZTP"` (15 תווים, מקומות 0–14):

•`'H'` – במקום 2: פעם אחת;

•`'E'` – במקומות 3, 4: פעמיים;

•`'L'` – במקומות 6, 9, 11: שלוש פעמים;

•`'P'` – במקומות 1, 7, 8, 14: ארבע פעמים.

זימון`k``k == 4``arr[k]``k+1`מופעי `arr[k]` ב-`s``What(s, arr[k], k+1)`המשך
`WhyHelp(arr,s,0)`0false`'H'`11true`WhyHelp(arr,s,1)`
`WhyHelp(arr,s,1)`1false`'E'`22true`WhyHelp(arr,s,2)`
`WhyHelp(arr,s,2)`2false`'L'`33true`WhyHelp(arr,s,3)`
`WhyHelp(arr,s,3)`3false`'P'`44true`WhyHelp(arr,s,4)`
`WhyHelp(arr,s,4)`4true––––`return true`

כל ארבע הבדיקות הצליחו, ו-`true` חוזר אל `Why`.

תשובה: הזימון `Why(arr, s)` מחזיר `true`.

סעיף ה

תשובה:

`"HEELLLPPPP"` (10 תווים)

כדי שיוחזר `true` צריך: `'H'` בדיוק פעם אחת, `'E'` בדיוק פעמיים, `'L'` בדיוק 3 פעמים ו-`'P'` בדיוק 4 פעמים. במחרוזת הקצרה ביותר אין תווים נוספים, ולכן אורכה 1+2+3+4=101+2+3+4=10. הסדר אינו חשוב.

תשובה: למשל `str = "HEELLLPPPP"` (באורך 10).

סעיף ו

תשובה:

מחזירה `true` אם לכל `k`, התו `arr[k]` מופיע ב-`s` בדיוק `k+1` פעמים; אחרת `false`.

`WhyHelp` עוברת ברקורסיה על המקומות `k = 0, 1, ..., arr.length-1` ובודקת בכל מקום, בעזרת `What` (סעיף ג), אם `arr[k]` מופיע ב-`s` בדיוק `k+1` פעמים. כישלון באחד מהם מחזיר `false`, והגעה לסוף המערך מחזירה `true`.

תשובה: הפעולה בודקת אם התו הראשון במערך מופיע ב-`s` פעם אחת בדיוק, התו השני פעמיים בדיוק, השלישי שלוש פעמים בדיוק וכן הלאה (`arr[k]` מופיע `k+1` פעמים). אם כן – `true`, אחרת – `false`.

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

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

מערך דו-ממדי של מספרים שלמים נקרא "מערך מסודר" אם הוא עונה על שלושת התנאים האלה:

•מספר השורות במערך שווה למספר העמודות בו (מערך ריבועי).

•בעמודה 0 אין מספרים שליליים, בעמודה 1 יש מספר שלילי אחד, בעמודה 2 יש 2 מספרים שליליים וכן הלאה.

לדוגמה, המערך שלפניכם הוא "מערך מסודר":

0123
0106-2-10
115-3-53
2518-15
30140-12
א.

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

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

(8 נקודות)
ב.

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

רמז: מומלץ לכתוב פעולות עזר.

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

סעיף א

תשובה:

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

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

פעולת עזר `CountNeg(mat, col)` (באותה מחלקה, סטטית):

•טענת כניסה: מערך דו-ממדי `mat` ומספר עמודה `col` חוקי;

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

היא עוברת על כל השורות `row` ובודקת את `mat[row][col] < 0`.

הפעולה הראשית:

1. תנאי 1 – ריבועי: `n` = מספר השורות. ב-Java מערך דו-ממדי הוא מערך של שורות, ולכן בודקים שכל שורה באורך `n`. ב-C# (`int[,]`) בודקים `mat.GetLength(1) == mat.GetLength(0)`. אם לא – `false`.

2. תנאי 2 – שליליים בעמודות: לכל עמודה `col` מ-0 עד n−1n-1 בודקים ש-`CountNeg(mat, col) == col` (בעמודה 0 אפס שליליים, בעמודה 1 אחד וכן הלאה). אם עמודה כלשהי לא מתאימה – `false`.

3. אם שני התנאים התקיימו – `true`.

בדוגמה: המערך 4×44\times 4. עמודה 0 (10,15,5,010, 15, 5, 0) – 0 שליליים; עמודה 1 (6,−3,1,146, -3, 1, 14) – 1; עמודה 2 (−2,−5,8,0-2, -5, 8, 0) – 2; עמודה 3 (−10,3,−15,−12-10, 3, -15, -12) – 3. מוחזר `true`.

C#:

// פעולת עזר: כמה מספרים שליליים יש בעמודה col
public static int CountNeg(int[,] mat, int col)
{
    int count = 0;
    for (int row = 0; row < mat.GetLength(0); row++)
    {
        if (mat[row, col] < 0)
            count++;
    }
    return count;
}

public static bool IsOrdered(int[,] mat)
{
    int n = mat.GetLength(0);              // מספר השורות
    if (mat.GetLength(1) != n)             // תנאי 1: מערך ריבועי
        return false;
    for (int col = 0; col < n; col++)      // תנאי 2: בעמודה col יש col שליליים
    {
        if (CountNeg(mat, col) != col)
            return false;
    }
    return true;
}

Java:

// פעולת עזר: כמה מספרים שליליים יש בעמודה col
public static int countNeg(int[][] mat, int col)
{
    int count = 0;
    for (int row = 0; row < mat.length; row++)
    {
        if (mat[row][col] < 0)
            count++;
    }
    return count;
}

public static boolean isOrdered(int[][] mat)
{
    int n = mat.length;                    // מספר השורות
    for (int row = 0; row < n; row++)      // תנאי 1: מערך ריבועי
    {
        if (mat[row].length != n)
            return false;
    }
    for (int col = 0; col < n; col++)      // תנאי 2: בעמודה col יש col שליליים
    {
        if (countNeg(mat, col) != col)
            return false;
    }
    return true;
}

תשובה: הפעולה `IsOrdered` / `isOrdered` עם פעולת העזר `CountNeg` / `countNeg` שלמעלה.

סעיף ב

תשובה:

O(n2)O(n^2), כאשר nn מספר השורות (והעמודות).

נסמן ב-nn את מספר השורות במערך (ובמערך ריבועי – גם את מספר העמודות).

1. בדיקת הריבועיות: מעבר אחד על nn השורות – O(n)O(n) (ב-C# – O(1)O(1)).

2. `CountNeg` עוברת על nn השורות של עמודה אחת – O(n)O(n).

3. הלולאה הראשית מזמנת את `CountNeg` עבור כל אחת מ-nn העמודות – n⋅O(n)=O(n2)n\cdot O(n)=O(n^2). בפועל כל תא במערך נבדק פעם אחת.

סך הכול O(n)+O(n2)=O(n2)O(n)+O(n^2)=O(n^2) – לינארי במספר התאים במערך, ואי אפשר פחות מזה, כי צריך לבדוק כל תא.

תשובה: O(n2)O(n^2).

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

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

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