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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

לדוגמה: מספר 12 הוא מספר מושלם, מספר 24 הוא מספר מושלם, מספר 25 אינו מספר מושלם.

כתבו קטע תוכנית להדפסת כל המספרים המושלמים מ- 1 עד 1,000.

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

פתרון

תשובה:

לולאה על num מ-1 עד 1000; לכל מספר מחשבים את סכום ספרותיו (פעולת עזר) ומדפיסים אותו אם num % sum == 0.

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

1. סכום הספרות – פעולת עזר `sumDigits`: כל עוד המספר גדול מ-0, מוסיפים לסכום את ספרת האחדות (`num % 10`) ומורידים אותה (`num /= 10`). לדוגמה, עבור 24: מוסיפים 4, נשאר 2, מוסיפים 2, נשאר 0 – הסכום 6.

2. בדיקת "מושלם" – המספר מתחלק בסכום ספרותיו אם `num % sumDigits(num) == 0`. עבור 24: 24%6=024 \% 6 = 0 – מושלם; עבור 25: סכום הספרות 7 ו-25%7=425 \% 7 = 4 – לא מושלם.

3. סכום הספרות של מספר חיובי הוא לפחות 1, ולכן אין חילוק ב-0.

4. הפעולה מקבלת עותק של המספר, כך שהשינוי של `num` בתוכה לא משפיע על משתנה הלולאה ב-main.

Java:

public class Q1
{
    // סכום הספרות של מספר שלם חיובי
    public static int sumDigits(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            sum += num % 10;   // ספרת האחדות
            num /= 10;         // מורידים את ספרת האחדות
        }
        return sum;
    }

    public static void main(String[] args)
    {
        for (int num = 1; num <= 1000; num++)
        {
            if (num % sumDigits(num) == 0)
                System.out.println(num);
        }
    }
}

C#:

using System;

class Program
{
    // סכום הספרות של מספר שלם חיובי
    public static int SumDigits(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            sum += num % 10;   // ספרת האחדות
            num /= 10;         // מורידים את ספרת האחדות
        }
        return sum;
    }

    public static void Main(string[] args)
    {
        for (int num = 1; num <= 1000; num++)
        {
            if (num % SumDigits(num) == 0)
                Console.WriteLine(num);
        }
    }
}

הפלט מתחיל ב-1, 2, ..., 9 (כל מספר חד-ספרתי מתחלק בעצמו), ואחריהם 10, 12, 18, 20, 21, 24, 27, ... ומסתיים ב-1000 (סכום הספרות 1). בסך הכול מודפסים 213 מספרים.

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

שאלה 2 · קליטת מחרוזות עד מספר נייד תקין

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

•שלושת התווים ראשונים הם קידומת (050, 051, 052, 053, 054, 055, 056, 057, 058).

•התו הרביעי הוא מקף (-).

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

לדוגמה: המחרוזת 050-1230567 היא מספר נייד תקין.

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

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

פתרון

תשובה:

פעולת עזר isValidPhone (אורך 11, "05" ואז ספרה 0-8, מקף במקום 3, שבע ספרות); לולאת while קולטת ומונה מחרוזות כל עוד המחרוזת אינה תקינה, ובסוף מדפיסה את המונה.

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

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

1. אורך: 3 תווי קידומת + מקף + 7 ספרות = 11 תווים. אם האורך שונה – לא תקין (זה גם מבטיח שלא נחרוג מגבולות המחרוזת בבדיקות הבאות).

2. קידומת: התו במקום 0 הוא '0', במקום 1 הוא '5', והתו במקום 2 הוא ספרה בין '0' ל-'8' – בדיוק הקידומות 050 עד 058.

3. מקף: התו במקום 3 הוא '-'.

4. ספרות: כל תו במקומות 4 עד 10 נמצא בין '0' ל-'9' (משווים קודים של תווים).

5. אם כל התנאים התקיימו – מחזירים true.

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

Java:

import java.util.Scanner;

public class Q2
{
    // האם המחרוזת היא מספר נייד תקין
    public static boolean isValidPhone(String str)
    {
        if (str.length() != 11)                         // 3 + 1 + 7 תווים
            return false;
        if (str.charAt(0) != '0' || str.charAt(1) != '5')
            return false;
        if (str.charAt(2) < '0' || str.charAt(2) > '8') // קידומת 050 עד 058
            return false;
        if (str.charAt(3) != '-')
            return false;
        for (int i = 4; i < 11; i++)                    // שבע ספרות
        {
            if (str.charAt(i) < '0' || str.charAt(i) > '9')
                return false;
        }
        return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int count = 0;
        String str = in.next();
        while (!isValidPhone(str))
        {
            count++;
            str = in.next();
        }
        System.out.println(count);
    }
}

C#:

using System;

class Program
{
    // האם המחרוזת היא מספר נייד תקין
    public static bool IsValidPhone(string str)
    {
        if (str.Length != 11)                   // 3 + 1 + 7 תווים
            return false;
        if (str[0] != '0' || str[1] != '5')
            return false;
        if (str[2] < '0' || str[2] > '8')       // קידומת 050 עד 058
            return false;
        if (str[3] != '-')
            return false;
        for (int i = 4; i < 11; i++)            // שבע ספרות
        {
            if (str[i] < '0' || str[i] > '9')
                return false;
        }
        return true;
    }

    public static void Main(string[] args)
    {
        int count = 0;
        string str = Console.ReadLine();
        while (!IsValidPhone(str))
        {
            count++;
            str = Console.ReadLine();
        }
        Console.WriteLine(count);
    }
}

דוגמה: עבור הקלט abc, 059-1234567, 050-123, 050-1230567 – שלוש המחרוזות הראשונות אינן תקינות (קידומת 059 אינה ברשימה; אורך שגוי), והרביעית תקינה. יודפס 3.

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

שאלה 3 · מערך מסודר: זוגיים לפני אי-זוגיים

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

לדוגמא:

המערכים הבאים הם מערכים "מסודרים":

0123456
6241284437
012345
6241281622
א.

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

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

Java:

public static boolean isOrdered(int[] arr)

C#:

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

כתבו פעולה המקבלת שלושה פרמטרים מטיפוס מספר שלם: size, x, y.

הפעולה צריכה ליצור מערך מסודר של מספרים שלמים בגודל size המלא במספרים אקראיים בין x ל-y (כולל).

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

Java:

public static int[] buildOrderedArray(int size, int x, int y)

C#:

public static int[] BuildOrderedArray(int size, int x, int y)

אפשר להניח ש- size>0 וגם x<y.

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

סעיף א

תשובה:

מדלגים על הרצף הזוגי שבתחילת המערך; אם אחריו מופיע ערך זוגי כלשהו – false, אחרת true. סיבוכיות O(n)O(n).

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

1. מתחילים ב-`i = 0` ומקדמים את `i` כל עוד הערך זוגי (`arr[i] % 2 == 0`). כך מדלגים על כל הקטע הזוגי שבתחילת המערך; `i` נעצר באי-הזוגי הראשון (או בסוף המערך).

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

3. אם הגענו לסוף בלי למצוא זוגי כזה – מחזירים true.

הבדיקה `% 2 == 0` נכונה גם למספרים שליליים (למשל −3%2=−1≠0-3 \% 2 = -1 \ne 0). כל תא נבדק פעם אחת, ולכן הסיבוכיות O(n)O(n).

דוגמאות: עבור {6,24,12,8,44,3,7}\{6,24,12,8,44,3,7\} – הלולאה הראשונה עוצרת ב-3 (מקום 5), ואחריו רק 3 ו-7 – יוחזר true. עבור {6,3,8}\{6,3,8\} – עוצרים ב-3, ואחריו 8 זוגי – יוחזר false.

Java:

public static boolean isOrdered(int[] arr)
{
    int i = 0;
    // מדלגים על הקטע הזוגי שבתחילת המערך
    while (i < arr.length && arr[i] % 2 == 0)
        i++;
    // מכאן והלאה כל הערכים חייבים להיות אי-זוגיים
    while (i < arr.length)
    {
        if (arr[i] % 2 == 0)
            return false;
        i++;
    }
    return true;
}

C#:

public static bool IsOrdered(int[] arr)
{
    int i = 0;
    // מדלגים על הקטע הזוגי שבתחילת המערך
    while (i < arr.Length && arr[i] % 2 == 0)
        i++;
    // מכאן והלאה כל הערכים חייבים להיות אי-זוגיים
    while (i < arr.Length)
    {
        if (arr[i] % 2 == 0)
            return false;
        i++;
    }
    return true;
}

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

סעיף ב

תשובה:

מגרילים size מספרים בתחום [x, y]; זוגי נכתב במקום הפנוי הבא מתחילת המערך (left++), ואי-זוגי במקום הפנוי הבא מסוף המערך (right--), עד ש-left > right.

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

•`left` – המקום הפנוי הבא בתחילת המערך, שם מכניסים מספרים זוגיים;

•`right` – המקום הפנוי הבא בסוף המערך, שם מכניסים מספרים אי-זוגיים.

1. מגרילים מספר בתחום [x,y][x, y] לפי ההנחיות: ב-Java `x + rand.nextInt(y - x + 1)`, וב-C# `rand.Next(x, y + 1)`.

2. אם המספר זוגי – כותבים אותו ב-`arr[left]` ומקדמים את `left`; אם הוא אי-זוגי – כותבים אותו ב-`arr[right]` ומורידים את `right`.

3. ממשיכים כל עוד `left <= right`, כלומר כל עוד יש מקום פנוי. בכל סיבוב מתמלא בדיוק תא אחד, ולכן אחרי size סיבובים המערך מלא.

למה המערך מסודר? כל הזוגיים נכתבו ברצף מתחילת המערך (מקומות 0..left−10..left-1) וכל האי-זוגיים ברצף מסופו (מקומות right+1..size−1right+1..size-1), ובסוף שני הקטעים נפגשים. לכן כל הזוגיים לפני כל האי-זוגיים. כל המספרים הוגרלו בתחום [x,y][x, y], כנדרש. מכיוון ש-x<yx<y, בתחום יש גם זוגי וגם אי-זוגי, כך שכל סידור אפשרי יכול להתקבל.

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

ב-Java יש להוסיף `import java.util.Random;` בראש הקובץ.

Java:

public static int[] buildOrderedArray(int size, int x, int y)
{
    Random rand = new Random();
    int[] arr = new int[size];
    int left = 0;          // המקום הפנוי הבא לזוגי (מההתחלה)
    int right = size - 1;  // המקום הפנוי הבא לאי-זוגי (מהסוף)
    while (left <= right)
    {
        int num = x + rand.nextInt(y - x + 1);
        if (num % 2 == 0)
        {
            arr[left] = num;
            left++;
        }
        else
        {
            arr[right] = num;
            right--;
        }
    }
    return arr;
}

C#:

public static int[] BuildOrderedArray(int size, int x, int y)
{
    Random rand = new Random();
    int[] arr = new int[size];
    int left = 0;          // המקום הפנוי הבא לזוגי (מההתחלה)
    int right = size - 1;  // המקום הפנוי הבא לאי-זוגי (מהסוף)
    while (left <= right)
    {
        int num = rand.Next(x, y + 1);
        if (num % 2 == 0)
        {
            arr[left] = num;
            left++;
        }
        else
        {
            arr[right] = num;
            right--;
        }
    }
    return arr;
}

דוגמה לפלט עבור `buildOrderedArray(8, 1, 20)`: {10,10,14,8,19,3,17,11}\{10, 10, 14, 8, 19, 3, 17, 11\} – ארבעה זוגיים ואחריהם ארבעה אי-זוגיים.

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

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

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

Java:

public class Time
{
      private int hour; //0-23 שעה
      private int min; //0-59 דקות

      public Time(int hour, int min)
      {
          this.hour = hour;
          this.min = min;
      }
}

C#:

public class Time
{
      private int hour; //0-23 שעה
      private int min; //0-59 דקות

      public Time(int hour, int min)
      {
          this.hour = hour;
          this.min = min;
      }
}
א.

כתבו במחלקה Time פעולה difference המקבלת הפניה לאובייקט other מטיפוס Time ומחזירה את מספר הדקות שעברו בין הזמן המיוצג על-ידי האובייקט שמפעיל את הפעולה (this) לזמן המיוצג באמצעות other. אפשר להניח ש- this לפני other.

(6 נקודות)
ב.

חברת משלוחים מבטיחה ללקוחותיה שכל משלוח יגיע למען לא מאוחר משלוש שעות (180 דקות) מהרגע שהתקבל בחברה.

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

לדוגמה: עבור משלוח שהתקבל בחברה ב-10:50 ונמסר ללקוח ב- 12:20 יש לקלוט ארבעה מספרים: 10, 50, 12, 20.

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

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

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

סעיף א

תשובה:

ממירים כל זמן לדקות מתחילת היום (hour*60+min) ומחזירים את ההפרש otherMinutes − thisMinutes.

נתון: שני זמנים (שעה ודקות), ו-this מוקדם מ-other. מבוקש: מספר הדקות ביניהם.

הרעיון: קשה להחסיר "שעות ודקות" ישירות (למשל 12:20 פחות 10:50 דורש "פריטה" של שעה). לכן ממירים כל זמן למספר אחד – דקות מתחילת היום – ומחסירים.

1. מספר הדקות מתחילת היום: hour⋅60+minhour \cdot 60 + min.

2. מכיוון ש-this לפני other, ההפרש otherMinutes−thisMinutesotherMinutes - thisMinutes אינו שלילי, וזה מספר הדקות שעברו.

3. הפעולה כתובה בתוך המחלקה Time, ולכן מותר לגשת ישירות לתכונות הפרטיות של other (`other.hour`, `other.min`).

לדוגמה, מ-10:50 עד 12:20: 12⋅60+20−(10⋅60+50)=740−650=9012 \cdot 60 + 20 - (10 \cdot 60 + 50) = 740 - 650 = 90 דקות.

Java:

public int difference(Time other)
{
    int thisMinutes = this.hour * 60 + this.min;     // דקות מתחילת היום
    int otherMinutes = other.hour * 60 + other.min;
    return otherMinutes - thisMinutes;
}

C#:

public int Difference(Time other)
{
    int thisMinutes = this.hour * 60 + this.min;     // דקות מתחילת היום
    int otherMinutes = other.hour * 60 + other.min;
    return otherMinutes - thisMinutes;
}

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

סעיף ב

תשובה:

לולאה של 100 משלוחים: יוצרים עצם Time לקבלה ועצם Time למסירה; אם received.difference(delivered) > 180 – ההבטחה הופרה (דגל false). בסוף מדפיסים הודעה לפי הדגל.

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

הרעיון: ההבטחה קוימה רק אם כל המשלוחים עמדו בה. לכן משתמשים בדגל בוליאני `kept` שמתחיל ב-true והופך ל-false ברגע שנמצא משלוח אחד שאיחר.

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

2. יוצרים שני עצמים: `received` (זמן הקבלה) ו-`delivered` (זמן המסירה).

3. מזמנים את הפעולה מסעיף א על העצם המוקדם: `received.difference(delivered)` – כך מתקיימת ההנחה ש-this לפני other, והתוצאה היא מספר הדקות שהמשלוח היה בדרך.

4. "לא מאוחר משלוש שעות" פירושו שמשך של 180 דקות בדיוק עדיין תקין; לכן ההבטחה מופרת רק כאשר ההפרש גדול מ-180.

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

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

Java:

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    boolean kept = true;   // האם ההבטחה קוימה בכל המשלוחים
    for (int i = 0; i < 100; i++)
    {
        int recHour = in.nextInt();
        int recMin = in.nextInt();
        int delHour = in.nextInt();
        int delMin = in.nextInt();
        Time received = new Time(recHour, recMin);    // זמן הקבלה בחברה
        Time delivered = new Time(delHour, delMin);   // זמן המסירה ללקוח
        if (received.difference(delivered) > 180)
            kept = false;
    }
    if (kept)
        System.out.println("The company kept its promise");
    else
        System.out.println("The company did not keep its promise");
}

C#:

public static void Main(string[] args)
{
    bool kept = true;   // האם ההבטחה קוימה בכל המשלוחים
    for (int i = 0; i < 100; i++)
    {
        int recHour = int.Parse(Console.ReadLine());
        int recMin = int.Parse(Console.ReadLine());
        int delHour = int.Parse(Console.ReadLine());
        int delMin = int.Parse(Console.ReadLine());
        Time received = new Time(recHour, recMin);    // זמן הקבלה בחברה
        Time delivered = new Time(delHour, delMin);   // זמן המסירה ללקוח
        if (received.Difference(delivered) > 180)
            kept = false;
    }
    if (kept)
        Console.WriteLine("The company kept its promise");
    else
        Console.WriteLine("The company did not keep its promise");
}

דוגמה: משלוח 10:50 → 12:20 נמשך 90 דקות – תקין; משלוח 8:00 → 11:01 נמשך 181 דקות – איחור, ותודפס ההודעה שההבטחה לא קוימה.

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

שאלה 5 · מעקב: מקומות זוגיים עולים, אי-זוגיים יורדים

נתונה הפעולה what המקבלת מערך של מספרים שלמים באורך זוגי:

Java:

public static boolean what(int[] a)
{
    for(int i = 2; i < a.length-1;i++)
    {
        if(a[i] < a[i-2]) return false;
        i++;
        if(a[i] > a[i-2]) return false;
    }
    return true;
}

C#:

public static bool What(int[] a)
{
    for(int i = 2; i < a.Length-1;i++)
    {
        if(a[i] < a[i-2]) return false;
        i++;
        if(a[i] > a[i-2]) return false;
    }
    return true;
}

נתון מערך מספרים שלמים a:

01234567
12538104205
א.

עקבו בעזרת טבלת מעקב אחרי ביצוע הפעולה ורשמו מה תחזיר הפעולה.

(5 נקודות)
ב.

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

(2 נקודות)
ג.

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

(2 נקודות)
ד.

נתון מערך b של מספרים שלמים. ידוע שתוצאת הזימון what(b) היא true.

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

מהי סיבוכיות הפעולה שכתבתם?

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

סעיף א

תשובה:

false (ב-i = 7: a[7] = 5 > a[5] = 4).

מה הפעולה עושה בכל סיבוב: בתחילת הסיבוב `i` זוגי, ונבדק `a[i] < a[i-2]`; אחר כך `i++` בתוך הגוף, ונבדק `a[i] > a[i-2]` עבור `i` אי-זוגי; ה-`i++` של הלולאה מעביר לזוגי הבא. הלולאה רצה כל עוד `i < a.length-1`, כלומר i<7i < 7.

אורך המערך 8.

שלבiהתנאי שנבדקערכיםתוצאת התנאי
12`a[2] < a[0]`3 < 1false – ממשיכים
23`a[3] > a[1]`8 > 25false – ממשיכים
34`a[4] < a[2]`10 < 3false – ממשיכים
45`a[5] > a[3]`4 > 8false – ממשיכים
56`a[6] < a[4]`20 < 10false – ממשיכים
67`a[7] > a[5]`5 > 4true – `return false`

במקומות האי-זוגיים הסדרה 25, 8, 4, 5 – הערך 5 גדול מ-4 שלפניו, ולכן הפעולה מחזירה false.

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

סעיף ב

תשובה:

למשל {1, 25, 3, 20, 10, 8, 20, 5, 30, 2}.

כדי שהפעולה תחזיר true, אף בדיקה לא צריכה להיכשל:

•במקומות הזוגיים (0, 2, 4, 6, 8) כל ערך גדול או שווה לקודמו – סדרה לא יורדת;

•במקומות האי-זוגיים (1, 3, 5, 7, 9) כל ערך קטן או שווה לקודמו – סדרה לא עולה.

נבחר במקומות הזוגיים 1, 3, 10, 20, 30 ובמקומות האי-זוגיים 25, 20, 8, 5, 2:

0123456789
125320108205302

הלולאה בודקת i=2..9i=2..9: 3≥13 \ge 1, 20≤2520 \le 25, 10≥310 \ge 3, 8≤208 \le 20, 20≥1020 \ge 10, 5≤85 \le 8, 30≥2030 \ge 20, 2≤52 \le 5 – אף תנאי לא מתקיים, והפעולה מחזירה true.

תשובה: למשל `{1, 25, 3, 20, 10, 8, 20, 5, 30, 2}`.

סעיף ג

תשובה:

מחזירה true אם האיברים במקומות הזוגיים מסודרים בסדר עולה (לא יורד) והאיברים במקומות האי-זוגיים בסדר יורד (לא עולה); אחרת false.

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

•עבור מקום זוגי היא נכשלת אם a[i]<a[i−2]a[i] < a[i-2], כלומר דורשת שהאיברים במקומות 0, 2, 4, ... יהיו בסדר עולה (לא יורד);

•עבור מקום אי-זוגי היא נכשלת אם a[i]>a[i−2]a[i] > a[i-2], כלומר דורשת שהאיברים במקומות 1, 3, 5, ... יהיו בסדר יורד (לא עולה).

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

סעיף ד

תשובה:

המקסימום הוא הגדול מבין b[1] (ראש הסדרה היורדת במקומות האי-זוגיים) ו-b[b.length-2] (סוף הסדרה העולה במקומות הזוגיים); סיבוכיות O(1)O(1).

הרעיון: לפי סעיף ג, מכיוון ש-`what(b)` החזירה true:

•במקומות הזוגיים הסדרה לא יורדת, ולכן הגדול ביניהם הוא האחרון – במקום `b.length-2` (האורך זוגי, ולכן המקום הזוגי האחרון הוא n−2n-2);

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

כל איבר במערך נמצא באחת משתי הקבוצות, ולכן המקסימום של כל המערך הוא הגדול מבין שני הערכים `b[1]` ו-`b[b.length-2]`. אין צורך לעבור על המערך. (המערך באורך זוגי, ולכן יש בו לפחות שני תאים.)

Java:

public static int getMax(int[] b)
{
    // b[1] - הגדול במקומות האי-זוגיים, b[b.length-2] - הגדול במקומות הזוגיים
    if (b[1] > b[b.length - 2])
        return b[1];
    return b[b.length - 2];
}

C#:

public static int GetMax(int[] b)
{
    // b[1] - הגדול במקומות האי-זוגיים, b[b.Length-2] - הגדול במקומות הזוגיים
    if (b[1] > b[b.Length - 2])
        return b[1];
    return b[b.Length - 2];
}

לדוגמה, עבור המערך מסעיף ב: b[1]=25b[1]=25, b[8]=30b[8]=30 – יוחזר 30.

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

תשובה: הפעולה שלמעלה; סיבוכיות O(1)O(1).

שאלה 6 · ניתוח פעולות על מחרוזות ומערך מחרוזות

א.

נתונה הפעולה secret() הבאה המקבלת מחרוזת:

Java:

public static boolean secret(String str)
{
    for (int i = 0; i < str.length(); i+=2)
    {
        if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z')
      {
            return false;
        }
    }
    for (int i = 1; i < str.length(); i+=2)
    {
        if (str.charAt(i) < 'A' || str.charAt(i) > 'Z')
      {
            return false;
        }
    }

     return true;
}

C#:

public static bool Secret(string str)
{
    for (int i = 0; i < str.Length; i+=2)
    {
        if (str[i]>= 'A' && str[i]<= 'Z')
      {
            return false;
        }
    }
    for (int i = 1; i < str.Length; i+=2)
    {
        if (str[i]< 'A' || str[i]> 'Z')
      {
            return false;
        }
    }

     return true;
}
(1)

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

(2)

נתונה טענה הבאה: אם זימון הפעולה secret(str) מחזיר ערך true, במחרוזת str אין רצף תווים זהים. האם הטענה נכונה? הסבירו את תשובתכם.

(3)

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

(6 נקודות)
ב.

נתונה הפעולה mystery המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה secret:

Java:

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

C#:

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

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

(2)

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

(3)

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

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

סעיף א

(1)
תשובה:

למשל "aA1BsC".

מה בודקת הפעולה: הלולאה הראשונה עוברת על המקומות הזוגיים (0, 2, 4, ...) ומחזירה false אם יש שם אות גדולה ('A'-'Z'). הלולאה השנייה עוברת על המקומות האי-זוגיים (1, 3, 5, ...) ומחזירה false אם יש שם תו שאינו אות גדולה. כלומר, הפעולה מחזירה true אם ורק אם במקומות הזוגיים אין אותיות גדולות ובמקומות האי-זוגיים יש רק אותיות גדולות.

נבנה מחרוזת באורך 6: במקומות 0, 2, 4 תווים שאינם אותיות גדולות ('a', '1', 's'), ובמקומות 1, 3, 5 אותיות גדולות ('A', 'B', 'C'):

מקום012345
תוaA1BsC
אות גדולה?לאכןלאכןלאכן

תשובה: למשל `"aA1BsC"`.

(2)
תשובה:

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

כל שני תווים סמוכים, במקומות ii ו-i+1i+1, נמצאים אחד במקום זוגי ואחד במקום אי-זוגי. אם `secret(str)` החזירה true, אז התו שבמקום הזוגי אינו אות גדולה, והתו שבמקום האי-זוגי הוא אות גדולה. תו שהוא אות גדולה ותו שאינו אות גדולה לא יכולים להיות אותו תו, ולכן אין במחרוזת שני תווים זהים צמודים – אין רצף של תווים זהים.

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

(3)
תשובה:

O(n)O(n), כאשר n אורך המחרוזת.

נסמן ב-nn את אורך המחרוזת. הלולאה הראשונה עוברת על המקומות הזוגיים – כ-n2\frac{n}{2} סיבובים, והשנייה על המקומות האי-זוגיים – עוד כ-n2\frac{n}{2} סיבובים. כל סיבוב מבצע מספר קבוע של פעולות. במקרה הגרוע (כשהפעולה מחזירה true) עוברים על כל nn התווים פעם אחת.

תשובה: O(n)O(n), כאשר nn הוא אורך המחרוזת.

סעיף ב

(1)
תשובה:

למשל {"aB", "Ab", "as", "aB", "Dc", "eF"}.

מה בודקת הפעולה: היא עוברת על המערך בזוגות – תאים (0,1), (2,3), (4,5), ... – ומחזירה false אם בזוג כלשהו `secret` מחזירה אותה תוצאה לשתי המחרוזות. כדי לקבל true צריך שבכל זוג מחרוזת אחת תקבל true מ-`secret` והשנייה false.

מקום012345
מחרוזת"aB""Ab""as""aB""Dc""eF"
secrettruefalsefalsetruefalsetrue

- "aB": במקום 0 'a' (לא גדולה), במקום 1 'B' (גדולה) – true.

- "Ab": במקום 0 'A' גדולה – false.

- "as": במקום 1 's' אינה גדולה – false.

- "Dc": 'D' גדולה במקום 0 – false; "eF" – true.

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

תשובה: למשל `{"aB", "Ab", "as", "aB", "Dc", "eF"}`.

(2)
תשובה:

הטענה אינה נכונה: הפעולה משווה רק את הזוגות (0,1), (2,3), ...; למשל {"aB","Ab","Ab","aB","Dc","eF"} מחזיר true אף ש-"Ab" מופיעה בתאים הסמוכים 1 ו-2.

בתוך זוג שהפעולה בודקת (תאים ii ו-i+1i+1 עם ii זוגי), שתי מחרוזות זהות היו מקבלות מ-`secret` אותה תוצאה, והפעולה הייתה מחזירה false – שם אכן לא ייתכנו מחרוזות זהות. אבל הפעולה לא משווה בין תאים סמוכים שנמצאים בזוגות שונים, למשל תאים 1 ו-2 או 3 ו-4.

דוגמה נגדית:

מקום012345
מחרוזת"aB""Ab""Ab""aB""Dc""eF"
secrettruefalsefalsetruefalsetrue

בכל אחד מהזוגות (0,1), (2,3), (4,5) התוצאות שונות, ולכן `mystery` מחזירה true – אך בתאים הסמוכים 1 ו-2 נמצאת אותה מחרוזת "Ab".

תשובה: הטענה אינה נכונה (דוגמה נגדית: `{"aB", "Ab", "Ab", "aB", "Dc", "eF"}`).

(3)
תשובה:

O(n⋅m)O(n \cdot m), כאשר n מספר התאים במערך ו-m אורך המחרוזת הארוכה ביותר.

נסמן ב-nn את מספר התאים במערך וב-mm את אורך המחרוזת הארוכה ביותר. הלולאה מבצעת כ-n2\frac{n}{2} סיבובים, ובכל סיבוב מזמנת את `secret` פעמיים. לפי סעיף א3, כל זימון של `secret` עולה O(m)O(m). לכן במקרה הגרוע:

n2⋅2⋅O(m)=O(n⋅m)\frac{n}{2} \cdot 2 \cdot O(m) = O(n \cdot m)

(אם אורך המחרוזות חסום בקבוע, הסיבוכיות היא O(n)O(n).)

תשובה: O(n⋅m)O(n \cdot m).

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

נתונה המחלקה Coffee, המייצגת קפסולות למכונת קפה. תכונות המחלקה הן:

•שם היצרן- name, מטיפוס מחרוזת- String

•סוג קפה- type, מטיפוס מחרוזת- String

•רמת החוזק- strength, מטיפוס מספר שלם- int (בין 1 ל-12)

•מחיר- price, מטיפוס מספר ממשי- double

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

כמו כן יש פעולות get/set לכל אחת מהתכונות ופעולה toString().

א.

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

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

Java:

public static boolean sameProducer(Coffee[] crr)

C#:

public static bool SameProducer(Coffee[] crr)

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

(5 נקודות)
ב.

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

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

Java:

public static String[] weakSorts(Coffee[] crr, int num)

C#:

public static string[] WeakSorts(Coffee[] crr, int num)

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

(5 נקודות)
ג.

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

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

Java:

public static void mostExpensive(Coffee[] crr)

C#:

public static void MostExpensive(Coffee[] crr)

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

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

סעיף א

תשובה:

שומרים את שם היצרן של crr[0] ומשווים אליו (equals) את שם היצרן של כל שאר הקפסולות; שונה – false, אחרת true.

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

1. שומרים במשתנה `producer` את שם היצרן של `crr[0]` (דרך `getName()`, כי התכונות פרטיות).

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

3. אם הלולאה הסתיימה – כל היצרנים זהים, ומחזירים true.

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

Java:

public static boolean sameProducer(Coffee[] crr)
{
    String producer = crr[0].getName();   // היצרן של הקפסולה הראשונה
    for (int i = 1; i < crr.length; i++)
    {
        if (!crr[i].getName().equals(producer))
            return false;
    }
    return true;
}

C#:

public static bool SameProducer(Coffee[] crr)
{
    string producer = crr[0].GetName();   // היצרן של הקפסולה הראשונה
    for (int i = 1; i < crr.Length; i++)
    {
        if (crr[i].GetName() != producer)
            return false;
    }
    return true;
}

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

סעיף ב

תשובה:

מעבר ראשון סופר את הקפסולות עם strength < num (אם 0 – מחזירים null); יוצרים מערך String בגודל זה, ובמעבר שני מכניסים אליו את ה-type של כל קפסולה כזו.

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

1. ספירה: סופרים כמה קפסולות יש עם `getStrength() < num`.

2. אם המונה 0 – אין אף קפסולה חלשה, ומחזירים `null` כנדרש.

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

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

הסיבוכיות O(n)O(n) – שני מעברים על המערך.

Java:

public static String[] weakSorts(Coffee[] crr, int num)
{
    // מעבר ראשון: כמה קפסולות חלשות יש
    int count = 0;
    for (int i = 0; i < crr.length; i++)
    {
        if (crr[i].getStrength() < num)
            count++;
    }
    if (count == 0)
        return null;

    // מעבר שני: מילוי המערך החדש בסוגי הקפה
    String[] result = new String[count];
    int k = 0;
    for (int i = 0; i < crr.length; i++)
    {
        if (crr[i].getStrength() < num)
        {
            result[k] = crr[i].getType();
            k++;
        }
    }
    return result;
}

C#:

public static string[] WeakSorts(Coffee[] crr, int num)
{
    // מעבר ראשון: כמה קפסולות חלשות יש
    int count = 0;
    for (int i = 0; i < crr.Length; i++)
    {
        if (crr[i].GetStrength() < num)
            count++;
    }
    if (count == 0)
        return null;

    // מעבר שני: מילוי המערך החדש בסוגי הקפה
    string[] result = new string[count];
    int k = 0;
    for (int i = 0; i < crr.Length; i++)
    {
        if (crr[i].GetStrength() < num)
        {
            result[k] = crr[i].GetType();
            k++;
        }
    }
    return result;
}

דוגמה: עבור קפסולות בחוזק 10, 4, 2 (מסוגים Ristretto, Lungo, Decaf) ו-num=5num = 5 יוחזר `{"Lungo", "Decaf"}`; עבור num=1num = 1 יוחזר `null`.

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

סעיף ג

תשובה:

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

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

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

2. מעבר שני – הדפסה: עוברים שוב על המערך ומדפיסים את פרטי כל קפסולה שמחירה שווה ל-`maxPrice`. ההדפסה של העצם מזמנת את `toString()` שקיימת במחלקה.

השוואת ה-double ב-`==` כאן בטוחה, כי משווים ערכים שהועתקו מאותן תכונות בלי חישוב. הסיבוכיות O(n)O(n).

Java:

public static void mostExpensive(Coffee[] crr)
{
    // מעבר ראשון: המחיר הגבוה ביותר
    double maxPrice = crr[0].getPrice();
    for (int i = 1; i < crr.length; i++)
    {
        if (crr[i].getPrice() > maxPrice)
            maxPrice = crr[i].getPrice();
    }
    // מעבר שני: הדפסת כל הקפסולות שזה מחירן
    for (int i = 0; i < crr.length; i++)
    {
        if (crr[i].getPrice() == maxPrice)
            System.out.println(crr[i]);   // מזמן את toString()
    }
}

C#:

public static void MostExpensive(Coffee[] crr)
{
    // מעבר ראשון: המחיר הגבוה ביותר
    double maxPrice = crr[0].GetPrice();
    for (int i = 1; i < crr.Length; i++)
    {
        if (crr[i].GetPrice() > maxPrice)
            maxPrice = crr[i].GetPrice();
    }
    // מעבר שני: הדפסת כל הקפסולות שזה מחירן
    for (int i = 0; i < crr.Length; i++)
    {
        if (crr[i].GetPrice() == maxPrice)
            Console.WriteLine(crr[i]);   // מזמן את ToString()
    }
}

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

שאלה 8 · מערכים הפוכים ובדיקת תת-מערך רציף

א.

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

לדוגמא: המערכים a ו-b הם מערכים הפוכים:

מערך01234567
a:12538104205
b:52041083251
(5 נקודות)
ב.

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

(1 נקודות)
ג.

נתונה הפעולה what המקבלת שני מערכים של מספרים שלמים:

Java:

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

C#:

public static bool What(int[] a, int[] b)
{
     int n = a.Length;
     int m = b.Length;
     bool f;
     for (int i = 0; i < n-m+1; i++)
        {
            f = true;
            for (int k = m-1; k >= 0; k--)
            {
                if (a[i+k] != b[k])
                      f = false;
            }
            if(f)return true;
        }
     return false;
}

עקבו אחר ביצוע הפעולה what עבור הפרמטרים הבאים:

int[] a = {8,6,7,10,13,2}
int[] b = {2,7,6}
(4 נקודות)
ד.

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

(2 נקודות)
ה.

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

(2 נקודות)
ו.

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

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

סעיף א

תשובה:

אם האורכים שונים – false; אחרת משווים a[i] ל-b[n−1−i] לכל i; הבדל כלשהו – false, אחרת true.

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

a[i]=b[n−1−i]a[i] = b[n-1-i]

1. אם האורכים שונים – המערכים לא יכולים להיות הפוכים, ומחזירים false (זה גם מונע חריגה מגבולות b).

2. עוברים על i=0..n−1i = 0..n-1 ומשווים את `a[i]` ל-`b[n-1-i]`. בהבדל הראשון מחזירים false.

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

בדוגמה: a[0]=1=b[7]a[0]=1=b[7], a[1]=25=b[6]a[1]=25=b[6], ..., a[7]=5=b[0]a[7]=5=b[0] – יוחזר true.

Java:

public static boolean isReversed(int[] a, int[] b)
{
    if (a.length != b.length)
        return false;
    int n = a.length;
    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[n - 1 - i])   // התא המקביל מהסוף
            return false;
    }
    return true;
}

C#:

public static bool IsReversed(int[] a, int[] b)
{
    if (a.Length != b.Length)
        return false;
    int n = a.Length;
    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[n - 1 - i])   // התא המקביל מהסוף
            return false;
    }
    return true;
}

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

סעיף ב

תשובה:

O(n)O(n) – לולאה אחת על n התאים.

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

תשובה: O(n)O(n), כאשר nn אורך המערכים.

סעיף ג

תשובה:

false – אף אחד מארבעת המקומות i = 0..3 לא נותן התאמה מלאה.

נתונים: n=6n = 6, m=3m = 3. הלולאה החיצונית רצה כל עוד i<n−m+1=4i < n-m+1 = 4, כלומר i=0,1,2,3i = 0, 1, 2, 3. בכל סיבוב `f` מתחיל ב-true, והלולאה הפנימית משווה את `a[i+k]` ל-`b[k]` עבור k=2,1,0k = 2, 1, 0; כל אי-שוויון הופך את `f` ל-false.

שלבika[i+k]b[k]שונים?f
102a[2] = 76כןfalse
201a[1] = 67כןfalse
300a[0] = 82כןfalse
412a[3] = 106כןfalse
511a[2] = 77לאfalse
610a[1] = 62כןfalse
722a[4] = 136כןfalse
821a[3] = 107כןfalse
920a[2] = 72כןfalse
1032a[5] = 26כןfalse
1131a[4] = 137כןfalse
1230a[3] = 102כןfalse

בסוף כל סיבוב של הלולאה החיצונית `f` הוא false, ולכן `return true` לא מתבצע. אחרי i=3i = 3 הלולאה מסתיימת והפעולה מחזירה false. (המספרים 2, 7, 6 מופיעים ב-a, אבל לא ברצף ובסדר הזה.)

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

סעיף ד

תשובה:

למשל b = {6, 7, 10, 13}.

לפי סעיף ה, הפעולה מחזירה true כאשר b מופיע ב-a כרצף של תאים סמוכים באותו סדר. נבחר ארבעה תאים רצופים מתוך a={8,6,7,10,13,2}a = \{8,6,7,10,13,2\} – למשל המקומות 1 עד 4: {6,7,10,13}\{6,7,10,13\}.

בדיקה: n−m+1=3n - m + 1 = 3; עבור i=0i = 0 יש אי-התאמה (a[3]=10≠13a[3]=10 \ne 13), ועבור i=1i = 1 כל ההשוואות שוות: a[4]=13a[4]=13, a[3]=10a[3]=10, a[2]=7a[2]=7, a[1]=6a[1]=6 – `f` נשאר true והפעולה מחזירה true.

תשובה: למשל `int[] b = {6,7,10,13}` (גם `{8,6,7,10}` או `{7,10,13,2}` מתאימים).

סעיף ה

תשובה:

מחזירה true אם המערך b מופיע בתוך המערך a כרצף של תאים סמוכים (באותו סדר), החל ממקום כלשהו; אחרת false.

לכל מקום התחלה אפשרי ii ב-a (מ-0 עד n−mn-m, כך שהקטע לא יחרוג מהמערך) הפעולה בודקת אם a[i+k]=b[k]a[i+k] = b[k] לכל k=0..m−1k = 0..m-1, כלומר אם הקטע של a באורך mm שמתחיל ב-ii זהה ל-b. ברגע שנמצא קטע כזה מוחזר true; אם אין אף קטע כזה – false. (אם b ארוך מ-a, הלולאה לא מתבצעת ומוחזר false.)

תשובה: הפעולה בודקת אם b הוא תת-מערך רציף של a – כלומר אם איברי b מופיעים ב-a ברצף ובאותו סדר החל ממקום כלשהו.

סעיף ו

תשובה:

O(n⋅m)O(n \cdot m) – (n−m+1) סיבובים חיצוניים, בכל אחד m השוואות.

הלולאה החיצונית מבצעת n−m+1n - m + 1 סיבובים, והלולאה הפנימית מבצעת בכל אחד מהם בדיוק mm השוואות (אין בה יציאה מוקדמת). במקרה הגרוע (אין התאמה) מספר הפעולות הוא (n−m+1)⋅m(n-m+1) \cdot m, שחסום על ידי n⋅mn \cdot m.

תשובה: O(n⋅m)O(n \cdot m), כאשר nn אורך a ו-mm אורך b.

שאלה 9 · מחלקה המונה את ספרות המספר

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

למחלקה Digits תכונה אחת בלבד arrDigits – מערך חד ממדי בן עשרה תאים מטיפוס מספר שלם, המייצג את מספר הפעמים שבו כל ספרה בין 9-0 מופיעה במספר.

לדוגמה: עבור התכונה arrDigits הבאה:

0123456789
0010200030

המידע המתקבל עבור מספר מסוים הוא:

•הספרה 2 מופיעה במספר פעם אחת.

•הספרה 4 מופיעה במספר פעמיים.

•הספרה 8 מופיעה במספר שלוש פעמים.

א.

כתבו במחלקה Digits פעולה בונה (constructor) המקבלת כפרמטר מספר שלם חיובי כלשהו ומאתחלת את התכונה arrDigits בהתאם (כלומר המערך יכיל את מספר הפעמים שכל ספרה מופיעה בו).

(4 נקודות)
ב.

כתבו במחלקה Digits פעולה equals המקבלת הפניה לעצם אחר מטיפוס Digits.

הפעולה תחזיר ערך true אם שני העצמים זהים, ולא – הפעולה תחזיר ערך false.

(3 נקודות)
ג.

נתונה פעולה main במחלקה אחרת:

Java:

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    int num1 = in.nextInt();
    int num2 = in.nextInt();
    Digits dg1 = new Digits(num1);
    Digits dg2 = new Digits(num2);
    if(dg1.equals(dg2))
        System.out.println("The numbers are equal");
    else
        System.out.println("The numbers are not equal");
}

C#:

public static void Main(string[] args)
{
     int num1 = int.Parse(Console.ReadLine());
     int num2 = int.Parse(Console.ReadLine());
     Digits dg1 = new Digits(num1);
     Digits dg2 = new Digits(num2);
     if(dg1.Equals(dg2))
          Console.WriteLine("The numbers are equal");
     else
          Console.WriteLine("The numbers are not equal");
}

האם הפעולה מדפיסה תוצאה נכונה עבור כל זוג מספרים שלמים וחיובים num1 ו-num2?

הסבירו את תשובתכם.

(3 נקודות)
ד.

כתבו במחלקה Digits פעולה compareTo המקבלת כפרמטר הפניה לעצם other מטיפוס Digits.

•הפעולה תחזיר 1 אם מספר המיוצג על ידי העצם המפעיל את הפעולה (this) גדול ממספר המיוצג על ידי העצם שהתקבל כפרמטר (other).

•הפעולה תחזיר 2 אם המספר המיוצג על ידי העצם המפעיל את הפעולה (this) קטן מהמספר המיוצג על ידי העצם שהתקבל כפרמטר (other).

•אם אין אפשרות לתשובה חד משמעית, הפעולה תחזיר 0.

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

סעיף א

תשובה:

יוצרים arrDigits = new int[10]; כל עוד num > 0 מגדילים את arrDigits[num % 10] ומחלקים את num ב-10.

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

1. יוצרים את המערך בגודל 10; ב-Java וב-C# כל תאיו מאותחלים ל-0.

2. כל עוד המספר גדול מ-0: ספרת האחדות היא `num % 10`, והיא משמשת כמקום במערך – מגדילים את `arrDigits[num % 10]` ב-1.

3. מורידים את ספרת האחדות: `num /= 10`.

לדוגמה, עבור 48284: הספרות מימין לשמאל הן 4, 8, 2, 8, 4, ולכן בסוף arrDigits[2]=1arrDigits[2]=1, arrDigits[4]=2arrDigits[4]=2, arrDigits[8]=2arrDigits[8]=2.

Java:

public class Digits
{
    private int[] arrDigits;

    public Digits(int num)
    {
        arrDigits = new int[10];    // כל המונים מתחילים ב-0
        while (num > 0)
        {
            arrDigits[num % 10]++;  // ספרת האחדות היא מקום המונה
            num /= 10;
        }
    }
}

C#:

public class Digits
{
    private int[] arrDigits;

    public Digits(int num)
    {
        arrDigits = new int[10];    // כל המונים מתחילים ב-0
        while (num > 0)
        {
            arrDigits[num % 10]++;  // ספרת האחדות היא מקום המונה
            num /= 10;
        }
    }
}

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

סעיף ב

תשובה:

משווים את עשרת המונים של this ושל other; הבדל כלשהו – false, אחרת true.

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

(השוואה `this.arrDigits == other.arrDigits` הייתה שגויה – היא משווה הפניות למערכים ולא את התוכן.)

Java:

public boolean equals(Digits other)
{
    for (int i = 0; i < 10; i++)
    {
        if (this.arrDigits[i] != other.arrDigits[i])
            return false;
    }
    return true;
}

C#:

public bool Equals(Digits other)
{
    for (int i = 0; i < 10; i++)
    {
        if (this.arrDigits[i] != other.arrDigits[i])
            return false;
    }
    return true;
}

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

סעיף ג

תשובה:

לא. העצם שומר רק כמה פעמים מופיעה כל ספרה ולא את מיקומה, ולכן למשל עבור 123 ו-312 יודפס "The numbers are equal" אף שהמספרים שונים.

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

דוגמה נגדית: num1=123num1 = 123, num2=312num2 = 312. בשני העצמים arrDigits[1]=arrDigits[2]=arrDigits[3]=1arrDigits[1]=arrDigits[2]=arrDigits[3]=1 ושאר התאים 0, ולכן יודפס "The numbers are equal" – אף ש-123≠312123 \ne 312.

ההודעה נכונה רק כשהמספרים שונים במספר הופעות של ספרה כלשהי (אז מודפס בצדק "not equal"), או כשהם באמת שווים.

תשובה: לא – למשל עבור 123 ו-312 תודפס ההודעה שהמספרים שווים, אף שאינם שווים.

סעיף ד

תשובה:

משווים קודם את מספר הספרות (יותר ספרות – 1, פחות – 2). באותו מספר ספרות: אם המספר הקטן ביותר שאפשר לבנות מספרות this גדול מהגדול ביותר של other – 1; אם הגדול ביותר של this קטן מהקטן ביותר של other – 2; אחרת 0.

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

1. מספר הספרות – סכום המונים. מספר חיובי עם יותר ספרות גדול תמיד ממספר עם פחות ספרות (בלי אפסים מובילים). לכן: יותר ספרות – מחזירים 1; פחות – מחזירים 2.

2. אותו מספר ספרות – בונים לכל עצם:

•את המספר הקטן ביותר האפשרי: הספרה הקטנה ביותר שאינה 0 בהתחלה, ואחריה שאר הספרות בסדר עולה (כולל האפסים). למשל מהספרות 0, 1, 3 – המספר 103.

•את המספר הגדול ביותר האפשרי: כל הספרות בסדר יורד. למשל 310.

3. this גדול מ-other בכל מקרה אם ורק אם הקטן ביותר של this גדול מהגדול ביותר של other – מחזירים 1. באופן סימטרי, אם הגדול ביותר של this קטן מהקטן ביותר של other – מחזירים 2. אחרת יש סידורים שבהם this גדול וסידורים שבהם הוא לא – מחזירים 0.

4. כדי לא לחרוג מטווח int (מספר בן 10 ספרות שסודר מחדש עלול לחרוג), בונים את המספרים כמחרוזות. למחרוזות ספרות באותו אורך הסדר המילוני זהה לסדר המספרי, ולכן משווים אותן ב-`compareTo` (ב-C#: `string.CompareOrdinal`).

דוגמאות:

- 21 מול 32: ל-this האפשרויות 12, 21; ל-other 23, 32. הגדול ביותר של this (21) קטן מהקטן ביותר של other (23) – מוחזר 2.

- 19 מול 22: this יכול להיות 19 או 91, other רק 22 – אין תשובה חד משמעית, מוחזר 0.

- 1000 מול 999: ארבע ספרות מול שלוש – מוחזר 1.

Java (בתוך המחלקה Digits):

// מספר הספרות במספר
private int countDigits()
{
    int count = 0;
    for (int i = 0; i < 10; i++)
        count += arrDigits[i];
    return count;
}

// המספר הקטן ביותר שאפשר לבנות מהספרות (בלי 0 מוביל)
private String minNumber()
{
    int[] c = new int[10];
    for (int i = 0; i < 10; i++)
        c[i] = arrDigits[i];
    String s = "";
    int first = 1;              // הספרה הקטנה ביותר שאינה 0
    while (c[first] == 0)
        first++;
    s += first;
    c[first]--;
    for (int d = 0; d <= 9; d++)            // שאר הספרות בסדר עולה
        for (int j = 0; j < c[d]; j++)
            s += d;
    return s;
}

// המספר הגדול ביותר שאפשר לבנות מהספרות
private String maxNumber()
{
    String s = "";
    for (int d = 9; d >= 0; d--)            // הספרות בסדר יורד
        for (int j = 0; j < arrDigits[d]; j++)
            s += d;
    return s;
}

public int compareTo(Digits other)
{
    int len1 = this.countDigits();
    int len2 = other.countDigits();
    if (len1 > len2)
        return 1;
    if (len1 < len2)
        return 2;
    // אותו מספר ספרות: מחרוזות באותו אורך משוות לפי סדר מילוני
    if (this.minNumber().compareTo(other.maxNumber()) > 0)
        return 1;
    if (this.maxNumber().compareTo(other.minNumber()) < 0)
        return 2;
    return 0;
}

C#:

// מספר הספרות במספר
private int CountDigits()
{
    int count = 0;
    for (int i = 0; i < 10; i++)
        count += arrDigits[i];
    return count;
}

// המספר הקטן ביותר שאפשר לבנות מהספרות (בלי 0 מוביל)
private string MinNumber()
{
    int[] c = new int[10];
    for (int i = 0; i < 10; i++)
        c[i] = arrDigits[i];
    string s = "";
    int first = 1;              // הספרה הקטנה ביותר שאינה 0
    while (c[first] == 0)
        first++;
    s += first;
    c[first]--;
    for (int d = 0; d <= 9; d++)            // שאר הספרות בסדר עולה
        for (int j = 0; j < c[d]; j++)
            s += d;
    return s;
}

// המספר הגדול ביותר שאפשר לבנות מהספרות
private string MaxNumber()
{
    string s = "";
    for (int d = 9; d >= 0; d--)            // הספרות בסדר יורד
        for (int j = 0; j < arrDigits[d]; j++)
            s += d;
    return s;
}

public int CompareTo(Digits other)
{
    int len1 = this.CountDigits();
    int len2 = other.CountDigits();
    if (len1 > len2)
        return 1;
    if (len1 < len2)
        return 2;
    // אותו מספר ספרות: מחרוזות באותו אורך משוות לפי סדר מילוני
    if (string.CompareOrdinal(this.MinNumber(), other.MaxNumber()) > 0)
        return 1;
    if (string.CompareOrdinal(this.MaxNumber(), other.MinNumber()) < 0)
        return 2;
    return 0;
}

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

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

שאלה 10 · מחלקות בניין, דירה וחדר: חשבונית ניקיון חודשית

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

לצורך מחשוב הוגדרו שלוש מחלקות: Building, App, Room.

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

•type – סוג חדר (חדר שינה, חדר עבודה, שירותים, אמבטיה, מטבח וכו').

•area – שטח במטרים מרובעים.

•freq – תדירות הניקיון בחודש (0 – לא צריך לנקות, 1 – יש לנקות פעם אחת בחודש, 2 – פעמיים בחודש, 3 – שלוש פעמים וכד').

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

•appNum – מס' דירה.

•owner – שם בעל הדירה.

•rooms – מערך חדרים השייכים לדירה.

•rate – מחיר הניקיון של מטר מרובע אחד בדירה זו.

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

המחלקה Building מייצגת בניין. פרטי הבניין הם:

•address – כתובת בניין (רחוב ומספר).

•apartments – מערך דירות שחברה נותנת להן שרותי ניקיון.

א.

כתבו כותרות של שלוש המחלקות Building, App, Room והגדירו את התכונות שלהם.

כתבו לכל מחלקה פעולה בונה.

(3 נקודות)

בסעיפים הבאים אפשר להניח שקיימות פעולות get/set לכל התכונות וגם פעולות toString() בכל שלוש המחלקות.

ב.

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

כתבו במחלקה App פעולה המחזירה מחיר חודשי של ניקיון הדירה.

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

Java:

public double monthCost()

C#:

public double MonthCost()
(3 נקודות)
ג.

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

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

Java:

public static void monthReport(Building[] bArr, String[] clients)

C#:

public static void MonthReport(Building[] bArr, string[] clients)
(5 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

Room(type, area, freq); App(appNum, owner, rooms, rate) כאשר rooms מערך Room; Building(address, apartments) כאשר apartments מערך App; תכונות פרטיות ובנאי שמקבל ערך לכל תכונה.

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

•התכונות מוגדרות `private` (הסתרת מידע), בטיפוס שמתאים לתיאור: שמות וכתובת – מחרוזת; מספר דירה ותדירות – מספר שלם; שטח ומחיר למ"ר – מספר ממשי (double), כי הם יכולים להיות לא שלמים;

•`rooms` הוא מערך של עצמי `Room`, ו-`apartments` מערך של עצמי `App`;

•הפעולה הבונה מקבלת ערך לכל תכונה ומציבה אותו בתכונה בעזרת `this`.

Java:

public class Room
{
    private String type;   // סוג חדר
    private double area;   // שטח במטרים מרובעים
    private int freq;      // תדירות הניקיון בחודש

    public Room(String type, double area, int freq)
    {
        this.type = type;
        this.area = area;
        this.freq = freq;
    }
}

public class App
{
    private int appNum;     // מספר דירה
    private String owner;   // שם בעל הדירה
    private Room[] rooms;   // מערך החדרים בדירה
    private double rate;    // מחיר ניקיון של מטר מרובע בדירה זו

    public App(int appNum, String owner, Room[] rooms, double rate)
    {
        this.appNum = appNum;
        this.owner = owner;
        this.rooms = rooms;
        this.rate = rate;
    }
}

public class Building
{
    private String address;    // כתובת הבניין
    private App[] apartments;  // הדירות שמקבלות שירותי ניקיון

    public Building(String address, App[] apartments)
    {
        this.address = address;
        this.apartments = apartments;
    }
}

C#:

public class Room
{
    private string type;   // סוג חדר
    private double area;   // שטח במטרים מרובעים
    private int freq;      // תדירות הניקיון בחודש

    public Room(string type, double area, int freq)
    {
        this.type = type;
        this.area = area;
        this.freq = freq;
    }
}

public class App
{
    private int appNum;     // מספר דירה
    private string owner;   // שם בעל הדירה
    private Room[] rooms;   // מערך החדרים בדירה
    private double rate;    // מחיר ניקיון של מטר מרובע בדירה זו

    public App(int appNum, string owner, Room[] rooms, double rate)
    {
        this.appNum = appNum;
        this.owner = owner;
        this.rooms = rooms;
        this.rate = rate;
    }
}

public class Building
{
    private string address;    // כתובת הבניין
    private App[] apartments;  // הדירות שמקבלות שירותי ניקיון

    public Building(string address, App[] apartments)
    {
        this.address = address;
        this.apartments = apartments;
    }
}

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

סעיף ב

תשובה:

מחיר חודשי = rate × Σ(area × freq) על כל חדרי הדירה (חדר עם freq = 0 תורם 0).

נתון: לכל חדר שטח ותדירות ניקיון חודשית; לדירה מחיר למטר מרובע. מבוקש: המחיר החודשי של הדירה.

הרעיון: חדר בשטח areaarea שמנקים freqfreq פעמים בחודש דורש בחודש ניקוי של area⋅freqarea \cdot freq מטרים מרובעים. לכן:

monthCost=rate⋅∑roomsarea⋅freqmonthCost = rate \cdot \sum_{rooms} area \cdot freq

1. מאתחלים צובר `total` ל-0.

2. עוברים על מערך החדרים של הדירה ומוסיפים לצובר `area * freq` של כל חדר. חדר שאין צורך לנקות (freq=0freq = 0) מוסיף 0, ולכן אין צורך בתנאי מיוחד.

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

לדוגמה, דירה עם חדר שינה 12 מ"ר פעמיים בחודש, מטבח 10 מ"ר ארבע פעמים, מחסן 5 מ"ר בתדירות 0, ומחיר 5 למ"ר: (12⋅2+10⋅4+5⋅0)⋅5=64⋅5=320(12 \cdot 2 + 10 \cdot 4 + 5 \cdot 0) \cdot 5 = 64 \cdot 5 = 320.

Java:

public double monthCost()
{
    double total = 0;   // סכום (שטח × תדירות) על כל החדרים
    for (int i = 0; i < rooms.length; i++)
        total += rooms[i].getArea() * rooms[i].getFreq();
    return total * rate;
}

C#:

public double MonthCost()
{
    double total = 0;   // סכום (שטח × תדירות) על כל החדרים
    for (int i = 0; i < rooms.Length; i++)
        total += rooms[i].GetArea() * rooms[i].GetFreq();
    return total * rate;
}

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

סעיף ג

תשובה:

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

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

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

2. לולאה על הבניינים (`j`): מקבלים את מערך הדירות של הבניין בעזרת `getApartments()`.

3. לולאה על הדירות (`k`): אם בעל הדירה (`getOwner()`) הוא הלקוח הנוכחי – מחשבים את התשלום החודשי בעזרת `monthCost()` מסעיף ב, מדפיסים את פרטי הדירה (כתובת הבניין ו-`toString()` של הדירה) ואת התשלום, ומוסיפים אותו ל-`total`.

4. בסוף הטיפול בלקוח מדפיסים את התשלום הכולל שלו.

השוואת השמות ב-Java נעשית ב-`equals`. הסיבוכיות היא (מספר הלקוחות) × (מספר הדירות הכולל).

Java:

public static void monthReport(Building[] bArr, String[] clients)
{
    for (int i = 0; i < clients.length; i++)
    {
        System.out.println("Invoice for: " + clients[i]);
        double total = 0;   // סך התשלום של הלקוח
        for (int j = 0; j < bArr.length; j++)
        {
            App[] apps = bArr[j].getApartments();
            for (int k = 0; k < apps.length; k++)
            {
                if (apps[k].getOwner().equals(clients[i]))
                {
                    double cost = apps[k].monthCost();
                    System.out.println(bArr[j].getAddress() + ", " + apps[k]
                                       + ", monthly cost: " + cost);
                    total += cost;
                }
            }
        }
        System.out.println("Total to pay: " + total);
    }
}

C#:

public static void MonthReport(Building[] bArr, string[] clients)
{
    for (int i = 0; i < clients.Length; i++)
    {
        Console.WriteLine("Invoice for: " + clients[i]);
        double total = 0;   // סך התשלום של הלקוח
        for (int j = 0; j < bArr.Length; j++)
        {
            App[] apps = bArr[j].GetApartments();
            for (int k = 0; k < apps.Length; k++)
            {
                if (apps[k].GetOwner() == clients[i])
                {
                    double cost = apps[k].MonthCost();
                    Console.WriteLine(bArr[j].GetAddress() + ", " + apps[k]
                                      + ", monthly cost: " + cost);
                    total += cost;
                }
            }
        }
        Console.WriteLine("Total to pay: " + total);
    }
}

דוגמה: אם ל-Dana דירה 3 ב-"Herzl 5" (320 לחודש) ודירה 1 ב-"Ben Yehuda 12" (240 לחודש), החשבונית שלה תכלול את שתי הדירות עם התשלום של כל אחת, ובסוף "Total to pay: 560.0" (ב-C# יודפס "Total to pay: 560", כי double שלם מודפס בלי ".0").

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

שאלה 11 · מערך דו-ממדי "בריא": אלכסון ראשי ותאי רופא

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

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

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

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

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

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

תזכורת: מערך ריבועי זה מערך שמספר השורות בו שווה למספר העמודות. האלכסון הראשי כולל את התאים (0,0), (1,1), (2,2) וכו'.

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

פתרון

תשובה:

פעולות עזר: isSick (מספר אי-זוגי) ו-isDoctorCell (אין בשורה ובעמודה ערך גדול מהתא); isHealthy מחזירה false אם תא כלשהו (i,i) אינו אי-זוגי או אינו תא רופא, אחרת true.

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

•"חולה": אם למספר יש מחלק זוגי, אז 2 מחלק אותו והוא זוגי; ולהפך, מספר זוגי מתחלק ב-2 (מחלק זוגי). לכן מספר חיובי הוא "חולה" אם ורק אם הוא אי-זוגי – בדיקה אחת: `num % 2 != 0`. (2 עצמו מחלק זוגי של כל זוגי, ולכן אין צורך לעבור על כל המחלקים.)

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

•"בריא": כל תאי האלכסון הראשי (i,i)(i,i) מקיימים את שני התנאים.

מבנה הפתרון – שלוש פעולות:

1. `isSick(num)` – מחזירה true אם המספר אי-זוגי.

2. `isDoctorCell(mat, row, col)` – עוברת על כל השורה `row` ובודקת שאין ערך גדול מ-`mat[row][col]`, ואז על כל העמודה `col` באותו אופן. ערך גדול יותר – false; אחרת true.

3. `isHealthy(mat)` – עוברת על תאי האלכסון (i,i)(i,i), i=0..n−1i = 0..n-1. אם תא אינו "חולה" או אינו "תא רופא" – מחזירה false מיד; אם כל התאים עברו – true.

סיבוכיות: לכל אחד מ-nn תאי האלכסון בודקים שורה ועמודה – 2n2n פעולות, בסך הכול O(n2)O(n^2).

Java:

// מספר "חולה" - אין לו מחלקים זוגיים, כלומר הוא אי-זוגי
public static boolean isSick(int num)
{
    return num % 2 != 0;
}

// האם התא (row, col) הוא "תא רופא": אין בשורה ובעמודה שלו ערך גדול ממנו
public static boolean isDoctorCell(int[][] mat, int row, int col)
{
    for (int j = 0; j < mat[row].length; j++)
    {
        if (mat[row][j] > mat[row][col])
            return false;
    }
    for (int i = 0; i < mat.length; i++)
    {
        if (mat[i][col] > mat[row][col])
            return false;
    }
    return true;
}

public static boolean isHealthy(int[][] mat)
{
    for (int i = 0; i < mat.length; i++)
    {
        if (!isSick(mat[i][i]) || !isDoctorCell(mat, i, i))
            return false;
    }
    return true;
}

C# (מערך דו-ממדי `int[,]`):

// מספר "חולה" - אין לו מחלקים זוגיים, כלומר הוא אי-זוגי
public static bool IsSick(int num)
{
    return num % 2 != 0;
}

// האם התא (row, col) הוא "תא רופא": אין בשורה ובעמודה שלו ערך גדול ממנו
public static bool IsDoctorCell(int[,] mat, int row, int col)
{
    for (int j = 0; j < mat.GetLength(1); j++)
    {
        if (mat[row, j] > mat[row, col])
            return false;
    }
    for (int i = 0; i < mat.GetLength(0); i++)
    {
        if (mat[i, col] > mat[row, col])
            return false;
    }
    return true;
}

public static bool IsHealthy(int[,] mat)
{
    for (int i = 0; i < mat.GetLength(0); i++)
    {
        if (!IsSick(mat[i, i]) || !IsDoctorCell(mat, i, i))
            return false;
    }
    return true;
}

דוגמה:

שורהעמודה 0עמודה 1עמודה 2
0924
1173
25611

האלכסון: 9, 7, 11 – כולם אי-זוגיים. 9 הגדול בשורה 0 (9, 2, 4) ובעמודה 0 (9, 1, 5); 7 הגדול בשורה 1 ובעמודה 1 (2, 7, 6); 11 הגדול בשורה 2 ובעמודה 2 – המערך "בריא" ויוחזר true. אם נחליף את 7 ב-8 – יוחזר false (8 זוגי); אם נחליף את 2 ב-12 – יוחזר false (9 כבר אינו מקסימלי בשורה 0).

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

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

נתונות הפעולות הרקורסיביות secret ו- what:

Java:

public static int secret(int num)
{
    if(num == 0)
        return 1;
    return 10 * secret(num/10);
}

public static boolean what(int num1, int num2)
{
    int d = secret(num2);
    return what(num1, num2, d);
}

private static boolean what(int num1, int num2, int d)
{
    if(num1 < num2)
        return false;
    if(num1 % d == num2)
        return true;
    return what(num1/10,num2, d);
}

C#:

public static int Secret(int num)
{
    if(num == 0)
        return 1;
    return 10 * Secret(num/10);
}

public static bool What(int num1, int num2)
{
    int d = Secret(num2);
    return What(num1, num2, d);
}

private static bool What(int num1, int num2, int d)
{
    if(num1 < num2)
        return false;
    if(num1 % d == num2)
        return true;
    return What(num1/10,num2, d);
}
א.

עקבו אחרי זימון secret(123) רשמו את תוצאת הזימון. יש להראות מעקב!

(2 נקודות)
ב.

מה מבצעת הפעולה secret(num) עבור מספר שלם חיובי num?

(2 נקודות)
ג.

עקבו אחרי זימון what(124567,234) ורשמו את תוצאות הזימון.

יש להראות מעקב אחרי הפעולה what, אין צורך במעקב אחרי הפעולה secret.

(4 נקודות)
ד.

תנו דוגמה למספר תלת-סיפרתי num שעבורו זימון what(456789, num) יחזיר ערך true.

(1 נקודות)
ה.

מה מבצעת הפעולה what(num1,num2) עבור שני מספרים שלמים וחיוביים num1 ו-num2?

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

סעיף א

תשובה:

1000

כל זימון עם num≠0num \ne 0 מזמן את `secret(num/10)` (מוריד את ספרת האחדות) וכופל את התוצאה ב-10; הזימון עם num=0num = 0 הוא תנאי העצירה ומחזיר 1.

שלב הזימונים (כלפי מטה):

זימוןnumnum == 0?מחזיר
secret(123)123לא10 * secret(12)
secret(12)12לא10 * secret(1)
secret(1)1לא10 * secret(0)
secret(0)0כן1

שלב החזרה (כלפי מעלה): `secret(0)` = 1 ← `secret(1)` = 10⋅1=1010 \cdot 1 = 10 ← `secret(12)` = 10⋅10=10010 \cdot 10 = 100 ← `secret(123)` = 10⋅100=100010 \cdot 100 = 1000.

תשובה: `secret(123)` מחזירה 1000.

סעיף ב

תשובה:

מחזירה 10k10^k, כאשר k מספר הספרות של num.

כל קריאה רקורסיבית מורידה ספרה אחת מ-num ומכפילה ב-10. למספר בעל kk ספרות יש kk קריאות עם num≠0num \ne 0 עד שמגיעים ל-0, ולכן התוצאה היא 10⋅10⋯10⋅1=10k10 \cdot 10 \cdots 10 \cdot 1 = 10^k. זו החזקה הקטנה ביותר של 10 שגדולה מ-num (למשל עבור 123 – 1000, עבור 7 – 10).

תשובה: הפעולה מחזירה 10k10^k, כאשר kk הוא מספר הספרות של num.

סעיף ג

תשובה:

false

הכנה: `what(124567, 234)` מחשבת d=secret(234)=1000d = secret(234) = 1000 (לשלוש ספרות, לפי סעיף ב), ומזמנת את `what(124567, 234, 1000)`. בכל זימון: אם num1<num2num1 < num2 – מחזירים false; אם שלוש הספרות האחרונות של num1 (num1%1000num1 \% 1000) שוות ל-234 – מחזירים true; אחרת מורידים את ספרת האחדות של num1 וממשיכים.

זימוןnum1num1 < 234?num1 % 1000שווה ל-234?המשך
what(124567, 234, 1000)124567לא567לאwhat(12456, 234, 1000)
what(12456, 234, 1000)12456לא456לאwhat(1245, 234, 1000)
what(1245, 234, 1000)1245לא245לאwhat(124, 234, 1000)
what(124, 234, 1000)124כן––מחזיר false

הערך false מוחזר דרך כל הזימונים עד לזימון המקורי.

תשובה: `what(124567, 234)` מחזירה false.

סעיף ד

תשובה:

למשל 567 (גם 456, 678, 789).

לפי סעיף ה, הפעולה מחזירה true כאשר הספרות של num מופיעות ב-456789 ברצף. ניקח, למשל, num=567num = 567: d=1000d = 1000, ו-

•456789%1000=789≠567456789 \% 1000 = 789 \ne 567 → `what(45678, 567, 1000)`;

•45678%1000=678≠56745678 \% 1000 = 678 \ne 567 → `what(4567, 567, 1000)`;

•4567%1000=5674567 \% 1000 = 567 – שווה, מוחזר true.

תשובה: למשל num=567num = 567 (מתאימים גם 456, 678, 789).

סעיף ה

תשובה:

מחזירה true אם הספרות של num2 מופיעות ב-num1 ברצף ובאותו סדר (num2 הוא "תת-מספר" של num1), אחרת false.

נסמן ב-kk את מספר הספרות של num2; אז d=10kd = 10^k, ו-num1%dnum1 \% d הוא המספר שבנוי מ-kk הספרות האחרונות של num1. בכל קריאה רקורסיבית מורידים את הספרה האחרונה של num1, ולכן בודקים בזה אחר זה את כל הקטעים של kk ספרות רצופות ב-num1 – מהקטע הימני ביותר שמאלה. אם אחד מהם שווה ל-num2 – מוחזר true. כאשר num1 נעשה קטן מ-num2, לא נשארו מספיק ספרות לקטע שיהיה שווה ל-num2, ומוחזר false.

תשובה: הפעולה בודקת אם num2 מופיע בתוך num1 כרצף ספרות (באותו סדר) – מחזירה true אם כן, ו-false אחרת. למשל `what(1234567, 456)` מחזירה true.

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

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

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