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

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

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

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

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

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

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

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

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

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

חלק א' - 40 נקודות

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

חלק ב' - 24 נקודות

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

חלק ג' - 36 נקודות

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

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

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

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

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

שאלה 1 · קליטת מחרוזות עד זקיף ומונה

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

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

פתרון

תשובה:

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

הרעיון: זו לולאת זקיף - לא ידוע מראש כמה מחרוזות ייקלטו. המחרוזת שאורכה קטן מ-4 מסמנת את סוף הקלט, ולכן היא לא נספרת.

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

2. הלולאה ממשיכה כל עוד אורך המחרוזת גדול או שווה ל-4.

3. בתוך הלולאה בודקים אם המחרוזת לא כוללת את האות `'T'`: הפעולה `indexOf('T')` מחזירה −1-1 כשהתו לא נמצא. במקרה כזה מגדילים את המונה `count`.

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

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

ב-Java נעשה שימוש ב-`in` שהוגדר לפי ההנחיות (`Scanner in=new Scanner(System.in);`).

Java:

int count = 0;
String str = in.next();
while (str.length() >= 4)
{
    if (str.indexOf('T') == -1)
        count++;
    str = in.next();
}
System.out.println(count);

C#:

int count = 0;
string str = Console.ReadLine();
while (str.Length >= 4)
{
    if (str.IndexOf('T') == -1)
        count++;
    str = Console.ReadLine();
}
Console.WriteLine(count);

לדוגמה, עבור הקלט `Tree`, `abcd`, `TTTT`, `hello`, `xyzw`, `ab` - המחרוזת `ab` (אורך 2) עוצרת את הקליטה. מבין ארבע המחרוזות הקודמות, `abcd`, `hello` ו-`xyzw` לא כוללות את 'T', ולכן יודפס 3.

תשובה: קטע התוכנית שלמעלה - לולאת זקיף שעוצרת במחרוזת שאורכה קטן מ-4 וסופרת את המחרוזות שאין בהן 'T'.

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

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

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

א.

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

(2 נקודות)

במפעל מפרידים בין שלושה סוגים של שרשראות:

•שרשרת "אחידה" היא שרשרת שיש בה חרוזים רק מצבע אחד.

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

•שרשרת "משעממת" היא שרשרת שיש בה שני צבעים בלבד.

•שרשרת "רגילה" היא שרשרת שאינה אחידה, אינה מושלמת ואינה משעממת.

ב.

הוסיפו במחלקה `Necklace` פעולה פנימית המחזירה:

1 - אם השרשרת אחידה.

2 - אם השרשרת מושלמת.

3 - אם השרשרת משעממת.

4 - אם השרשרת רגילה.

(4 נקודות)
ג.

כתבו פעולה המקבלת מערך שרשראות (מערך עצמים מסוג `Necklace`) ומספר שלם וחיובי `num`.

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

הערה: הניחו שבמחלקה `Necklace` קיימות פעולות אחזור- `get` לכל אחת מהתכונות.

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

סעיף א

תשובה:

שלוש תכונות שלמות פרטיות `red`, `yellow`, `green` ופעולה בונה שמקבלת שלושה פרמטרים ומציבה אותם בתכונות.

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

Java:

public class Necklace
{
    private int red;     // מספר החרוזים האדומים
    private int yellow;  // מספר החרוזים הצהובים
    private int green;   // מספר החרוזים הירוקים

    public Necklace(int red, int yellow, int green)
    {
        this.red = red;
        this.yellow = yellow;
        this.green = green;
    }
}

C#:

public class Necklace
{
    private int red;     // מספר החרוזים האדומים
    private int yellow;  // מספר החרוזים הצהובים
    private int green;   // מספר החרוזים הירוקים

    public Necklace(int red, int yellow, int green)
    {
        this.red = red;
        this.yellow = yellow;
        this.green = green;
    }
}

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

סעיף ב

תשובה:

סופרים כמה מהתכונות גדולות מ-0: אם צבע אחד - 1; אחרת אם שלוש הכמויות שוות - 2; אחרת אם שני צבעים - 3; אחרת - 4.

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

1. סופרים במשתנה `colors` כמה מבין `red`, `yellow`, `green` גדולים מ-0.

2. אם `colors == 1` - יש צבע אחד בלבד: השרשרת אחידה, מחזירים 1.

3. אחרת, אם שלוש הכמויות שוות - השרשרת מושלמת, מחזירים 2. (כאן כבר ידוע שיש יותר מצבע אחד, ולכן כמויות שוות פירושן שלושה צבעים בכמות זהה.)

4. אחרת, אם `colors == 2` - שני צבעים בלבד: משעממת, מחזירים 3.

5. בכל מקרה אחר (שלושה צבעים בכמויות לא שוות) - רגילה, מחזירים 4.

הפעולה פנימית, ולכן ניגשת ישירות לתכונות. נקרא לה `getKind` (ב-C# - `GetKind`; את השם `GetType` לא בוחרים ב-C#, כי הוא כבר קיים בכל עצם).

Java:

public int getKind()
{
    int colors = 0;              // כמה צבעים מופיעים בשרשרת
    if (this.red > 0) colors++;
    if (this.yellow > 0) colors++;
    if (this.green > 0) colors++;

    if (colors == 1)
        return 1;                // אחידה
    if (this.red == this.yellow && this.yellow == this.green)
        return 2;                // מושלמת
    if (colors == 2)
        return 3;                // משעממת
    return 4;                    // רגילה
}

C#:

public int GetKind()
{
    int colors = 0;              // כמה צבעים מופיעים בשרשרת
    if (this.red > 0) colors++;
    if (this.yellow > 0) colors++;
    if (this.green > 0) colors++;

    if (colors == 1)
        return 1;                // אחידה
    if (this.red == this.yellow && this.yellow == this.green)
        return 2;                // מושלמת
    if (colors == 2)
        return 3;                // משעממת
    return 4;                    // רגילה
}

דוגמאות: (5,0,0)(5,0,0) - 1; (3,3,3)(3,3,3) - 2; (4,0,6)(4,0,6) - 3; (1,2,3)(1,2,3) - 4.

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

סעיף ג

תשובה:

עוברים על המערך וסופרים שרשראות ש-`getKind()` שלהן 3 ושסכום שלוש הכמויות (האורך) גדול מ-`num`.

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

1. מונה `count` מתחיל ב-0.

2. עבור כל שרשרת במערך מחשבים את אורכה בעזרת פעולות האחזור: `getRed() + getYellow() + getGreen()`.

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

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

Java:

public static int countBoring(Necklace[] arr, int num)
{
    int count = 0;
    for (int i = 0; i < arr.length; i++)
    {
        int len = arr[i].getRed() + arr[i].getYellow() + arr[i].getGreen();
        if (arr[i].getKind() == 3 && len > num)
            count++;
    }
    return count;
}

C#:

public static int CountBoring(Necklace[] arr, int num)
{
    int count = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        int len = arr[i].GetRed() + arr[i].GetYellow() + arr[i].GetGreen();
        if (arr[i].GetKind() == 3 && len > num)
            count++;
    }
    return count;
}

לדוגמה, עבור המערך של השרשראות (5,0,0)(5,0,0), (3,3,3)(3,3,3), (4,0,6)(4,0,6), (1,2,3)(1,2,3), (0,2,2)(0,2,2), (0,0,7)(0,0,7) ו-`num = 5`: המשעממות הן (4,0,6)(4,0,6) באורך 10 ו-(0,2,2)(0,2,2) באורך 4, ורק הראשונה ארוכה מ-5 - מוחזר 1.

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

שאלה 3 · הדפסת סיומות מחרוזת המתחילות בתו

כתבו פעולה המקבלת מחרוזת `s` ותו `ch`. על הפעולה להדפיס את כל התת-מחרוזות השונות של `s` אשר מתחילות ב- `ch`, ומסתיימות בסוף המחרוזת.

לדוגמה, עבור המחרוזת `s="Java is a good language"` והתו `ch='a'` יש להדפיס

ava is a good language
a is a good language
a good language
anguage
age
◂ פתרון מלא לשאלה 3

פתרון

תשובה:

עוברים על כל המקומות `i` במחרוזת; כאשר `s.charAt(i) == ch` מדפיסים את `s.substring(i)`.

הרעיון: תת-מחרוזת שמסתיימת בסוף המחרוזת נקבעת לגמרי על ידי מקום ההתחלה שלה: זו `s.substring(i)`. לכן מספיק לעבור על כל המקומות `i` ולהדפיס את `s.substring(i)` בכל מקום שבו התו הוא `ch`.

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

Java:

public static void printSubstrings(String s, char ch)
{
    for (int i = 0; i < s.length(); i++)
    {
        if (s.charAt(i) == ch)
            System.out.println(s.substring(i));
    }
}

C#:

public static void PrintSubstrings(string s, char ch)
{
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == ch)
            Console.WriteLine(s.Substring(i));
    }
}

בדוגמה: התו `'a'` מופיע במקומות 1, 3 (ב-"Java"), 8 (המילה "a"), 16 ו-20 (ב-"language"), ומודפסות חמש השורות שבשאלה, לפי הסדר.

סיבוכיות: מעבר אחד על המחרוזת (וההדפסה עצמה).

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

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

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

לדוגמה: המערך `arr` הוא "מערך מצטלב".

אינדקס012345678
ערך1928477412
א.

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

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

(6 נקודות)
ב.

כתבו פעולה המקבלת "מערך מצטלב" ומחזירה את הערך הקטן ביותר במערך.

אין להשתמש בלולאה!

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

סעיף א

תשובה:

שתי לולאות בקפיצות של 2: במקומות הזוגיים בודקים ש-`arr[i] <= arr[i+2]`, באי-זוגיים ש-`arr[i] >= arr[i+2]`; הפרה אחת - `false`, אחרת `true`.

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

1. לולאה על המקומות הזוגיים i=0,2,4,…i=0,2,4,\dots כל עוד `i + 2` בתוך המערך: אם `arr[i] > arr[i+2]` - הסדר העולה הופר, מחזירים `false`.

2. לולאה על המקומות האי-זוגיים i=1,3,5,…i=1,3,5,\dots: אם `arr[i] < arr[i+2]` - הסדר היורד הופר, מחזירים `false`.

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

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

Java:

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

C#:

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

בדוגמה: במקומות הזוגיים 1, 2, 4, 7, 12 - עולה; במקומות האי-זוגיים 9, 8, 7, 4 - יורד, ולכן מוחזר `true`. לעומת זאת עבור {1,9,2,10}\{1,9,2,10\} מוחזר `false`, כי 9<109<10 במקומות האי-זוגיים.

סיבוכיות: O(n)O(n).

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

סעיף ב

תשובה:

המינימום הוא הקטן מבין `arr[0]` (הקטן במקומות הזוגיים) לבין הערך באינדקס האי-זוגי האחרון (`length-1` אם האורך זוגי, `length-2` אם אי-זוגי).

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

•בסדרת המקומות הזוגיים (סדר עולה) הקטן ביותר הוא הראשון - `arr[0]`.

•בסדרת המקומות האי-זוגיים (סדר יורד) הקטן ביותר הוא האחרון - באינדקס האי-זוגי הגדול ביותר.

הערך הקטן ביותר במערך כולו הוא הקטן מבין שני אלה.

1. מוצאים את האינדקס האי-זוגי האחרון: אם אורך המערך זוגי, התא האחרון (`length-1`) הוא אי-זוגי; אם האורך אי-זוגי, התא האחרון זוגי, והאי-זוגי האחרון הוא `length-2`.

2. אם במערך תא אחד בלבד אין מקומות אי-זוגיים, ומחזירים את `arr[0]`.

3. מחזירים את הקטן מבין `arr[0]` ו-`arr[lastOdd]`.

Java:

public static int minCross(int[] arr)
{
    if (arr.length == 1)
        return arr[0];
    int lastOdd;                       // האינדקס האי-זוגי האחרון
    if (arr.length % 2 == 0)
        lastOdd = arr.length - 1;
    else
        lastOdd = arr.length - 2;
    return Math.min(arr[0], arr[lastOdd]);
}

C#:

public static int MinCross(int[] arr)
{
    if (arr.Length == 1)
        return arr[0];
    int lastOdd;                       // האינדקס האי-זוגי האחרון
    if (arr.Length % 2 == 0)
        lastOdd = arr.Length - 1;
    else
        lastOdd = arr.Length - 2;
    return Math.Min(arr[0], arr[lastOdd]);
}

בדוגמה: אורך 9 (אי-זוגי), ולכן lastOdd=7lastOdd=7, `arr[7] = 4`, `arr[0] = 1`, והפעולה מחזירה min⁡(1,4)=1\min(1,4)=1.

סיבוכיות: O(1)O(1) - מספר קבוע של פעולות, בלי לולאה.

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

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

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

Java:

public static boolean what(int[] arr, int num)    {
    int i = 0;
    int k = 1;
    int value = arr[i];
    while(k < arr.length && value!= num)  {
        if(value < num)
        {
            value += arr[k];
            k++;
        }
        else
        {
            value -= arr[i];
            i++;
        }
    }
    if(value == num)
        return true;
    return false;
}

C#:

public static bool What(int[] arr, int num)    {
    int i = 0;
    int k = 1;
    int value = arr[i];
    while(k < arr.Length && value!= num)  {
        if(value < num)
        {
            value += arr[k];
            k++;
        }
        else
        {
            value -= arr[i];
            i++;
        }
    }
    if(value == num)
        return true;
    return false;
}
א.

עקבו בעזרת טבלת המעקב אחרי ביצוע הפעולה עבור המערך `int[] arr={1,3, 2, 5, 7, 3, 6}` ו- `num=17` ורשמו מה תחזיר הפעולה.

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

הפעולה מחזירה `true` (בסוף `i=1`, `k=5`, `value=17`: סכום התאים 1 עד 4, 3+2+5+7=173+2+5+7=17).

עוקבים אחרי `i`, `k` ו-`value`. בכל סיבוב: אם `value < num` מוסיפים את `arr[k]` ומקדמים את `k`; אחרת מחסירים את `arr[i]` ומקדמים את `i`. הלולאה נעצרת כאשר `k` מגיע ל-7 (אורך המערך) או כאשר `value == num`.

שלבikvalueהתנאי `value < num`פעולה
התחלה011-`value = arr[0]`
סיבוב 10241<171<17 כן`value += arr[1]` (3)
סיבוב 20364<174<17 כן`value += arr[2]` (2)
סיבוב 304116<176<17 כן`value += arr[3]` (5)
סיבוב 4051811<1711<17 כן`value += arr[4]` (7)
סיבוב 5151718<1718<17 לא`value -= arr[0]` (1)

אחרי סיבוב 5 מתקיים `value == num` (17), ולכן הלולאה נעצרת (למרות ש-`k = 5 < 7`). התנאי `value == num` מתקיים, והפעולה מחזירה `true`.

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

סעיף ב

תשובה:

בודקת אם יש במערך רצף של תאים סמוכים שסכומם `num` (שיטת "חלון נע"); מחזירה `true` אם מצאה רצף כזה. (מגבלה: הלולאה נעצרת כש-`k` מגיע לסוף המערך, ולכן רצף שמסתיים בתא האחרון ודורש עוד צמצום מההתחלה לא נמצא, למשל {2,3,4}\{2,3,4\} עם 7.)

ניתוח: בכל רגע `value` הוא סכום התאים הרצופים מ-`arr[i]` עד `arr[k-1]` - "חלון" במערך.

1. אם הסכום קטן מ-`num` - מרחיבים את החלון ימינה (מוסיפים את `arr[k]`, `k++`). מכיוון שכל המספרים חיוביים, ההרחבה מגדילה את הסכום.

2. אם הסכום גדול מ-`num` - מצמצמים את החלון משמאל (מחסירים את `arr[i]`, `i++`), וזה מקטין את הסכום.

3. כשהסכום שווה ל-`num` - הלולאה נעצרת והפעולה מחזירה `true`.

כך הפעולה בודקת אם קיים במערך רצף של תאים סמוכים שסכום ערכיו שווה ל-`num`. בדוגמה מסעיף א זה הרצף 3,2,5,73,2,5,7 (תאים 1 עד 4).

הערה על מקרה קצה: הלולאה נעצרת גם כאשר `k` מגיע לאורך המערך, כלומר אחרי שנוסף התא האחרון. אם בשלב זה הסכום גדול מ-`num`, החלון כבר לא מצומצם, ולכן רצף שמסתיים בתא האחרון עלול לא להימצא. לדוגמה, עבור {2,3,4}\{2,3,4\} ו-`num = 7`: הסכום עולה ל-2, 5, 9, הלולאה נעצרת עם 9 והפעולה מחזירה `false`, אף על פי ש-3+4=73+4=7. כלומר, תשובה `true` אומרת בוודאות שיש רצף כזה, ותשובה `false` נכונה בכל המקרים חוץ ממקרה הקצה הזה.

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

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

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

•`license` – לוחית רישוי של הרכב, מטיפוס מחרוזת, `String`.

•`ownerNum` – מספר הטלפון הנייד של בעל הרכב, מטיפוס מחרוזת, `String`.

•`status` – מצב הטיפול של הרכב, מטיפוס תו, `char`.

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

כאשר הרכב נכנס למוסך הוא מקבל סטטוס 'S', כאשר הטיפול מתחיל הסטטוס של הרכב משתנה ל- 'W', וכאשר טיפול מסתיים, הסטטוס של הרכב משתנה ל- 'E'.

מחיר הטיפול נקבע ברגע סיום הטיפול.

א.

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

(2 נקודות)
ב.

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

כותרת הפעולה

Java:

public void endWork(double cost)

C#:

public void EndWork(double cost)

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

(4 נקודות)
ג.

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

הפעולה תבדוק אם רכב סיים את הטיפול. אם כן – הפעולה תדפיס את מחיר הטיפול ותחזיר `true`.

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

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

Java:

public static boolean  result (Car[] arr, String license)

C#:

public static bool  Result (Car[] arr, string license)

הערה: אפשר להניח שבמחלקה `Car` קיימות פעולות `get` לכל התכונות

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

סעיף א

תשובה:

ארבע תכונות פרטיות; הפעולה הבונה מציבה את `license` ו-`ownerNum` מהפרמטרים, `status = 'S'` ו-`cost = 0`.

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

•רכב חדש "נכנס למוסך", ולכן הסטטוס ההתחלתי הוא `'S'`.

•המחיר נקבע רק בסיום הטיפול, ולכן בינתיים הוא 0.

Java:

public class Car
{
    private String license;   // לוחית רישוי
    private String ownerNum;  // מספר הטלפון הנייד של בעל הרכב
    private char status;      // מצב הטיפול: 'S', 'W' או 'E'
    private double cost;      // מחיר הטיפול

    public Car(String license, String ownerNum)
    {
        this.license = license;
        this.ownerNum = ownerNum;
        this.status = 'S';    // רכב שנכנס למוסך
        this.cost = 0;        // המחיר נקבע רק בסיום הטיפול
    }
}

C#:

public class Car
{
    private string license;   // לוחית רישוי
    private string ownerNum;  // מספר הטלפון הנייד של בעל הרכב
    private char status;      // מצב הטיפול: 'S', 'W' או 'E'
    private double cost;      // מחיר הטיפול

    public Car(string license, string ownerNum)
    {
        this.license = license;
        this.ownerNum = ownerNum;
        this.status = 'S';    // רכב שנכנס למוסך
        this.cost = 0;        // המחיר נקבע רק בסיום הטיפול
    }
}

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

סעיף ב

תשובה:

אם `status == 'W'`: `status = 'E'` ו-`this.cost = cost`; אחרת לא משנים דבר.

הרעיון: אפשר לסיים רק טיפול שנמצא בעבודה, כלומר כשהסטטוס הוא `'W'`.

1. בודקים אם `status == 'W'`.

2. אם כן - משנים את הסטטוס ל-`'E'` ושומרים את המחיר שהתקבל בתכונה `cost` (המחיר נקבע ברגע סיום הטיפול). מכיוון שהפרמטר והתכונה נקראים באותו שם, ניגשים לתכונה דרך `this.cost`.

3. אחרת (`'S'` - הטיפול לא התחיל, או `'E'` - כבר הסתיים) לא עושים דבר.

Java:

public void endWork(double cost)
{
    if (this.status == 'W')   // רק טיפול שהתחיל אפשר לסיים
    {
        this.status = 'E';
        this.cost = cost;
    }
}

C#:

public void EndWork(double cost)
{
    if (this.status == 'W')   // רק טיפול שהתחיל אפשר לסיים
    {
        this.status = 'E';
        this.cost = cost;
    }
}

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

סעיף ג

תשובה:

מחפשים במערך רכב שלוחית הרישוי שלו שווה ל-`license`; אם הסטטוס `'E'` - מדפיסים את המחיר ומחזירים `true`, אחרת מדפיסים את הסטטוס ומחזירים `false`; אם לא נמצא - מדפיסים הודעה ומחזירים `false`.

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

1. עוברים על המערך. משווים מחרוזות בעזרת `equals` (ב-C# - בעזרת `==`), דרך פעולת האחזור `getLicense()`. מדלגים על תאים ריקים (`null`) למקרה שהמערך לא מלא.

2. כשנמצא הרכב:

•אם `getStatus() == 'E'` - הטיפול הסתיים: מדפיסים את `getCost()` ומחזירים `true`.

•אחרת מדפיסים את הסטטוס (`'S'` או `'W'`) ומחזירים `false`.

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

Java:

public static boolean result(Car[] arr, String license)
{
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] != null && arr[i].getLicense().equals(license))
        {
            if (arr[i].getStatus() == 'E')
            {
                System.out.println(arr[i].getCost());
                return true;
            }
            System.out.println(arr[i].getStatus());
            return false;
        }
    }
    System.out.println("The car " + license + " is not in the garage");
    return false;
}

C#:

public static bool Result(Car[] arr, string license)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] != null && arr[i].GetLicense() == license)
        {
            if (arr[i].GetStatus() == 'E')
            {
                Console.WriteLine(arr[i].GetCost());
                return true;
            }
            Console.WriteLine(arr[i].GetStatus());
            return false;
        }
    }
    Console.WriteLine("The car " + license + " is not in the garage");
    return false;
}

לדוגמה, אם במערך רכב "22" שסיים טיפול במחיר 250.5 ורכב "33" שבטיפול: עבור "22" יודפס 250.5 ויוחזר `true`; עבור "33" יודפס `W` ויוחזר `false`; עבור "99" תודפס ההודעה ויוחזר `false`.

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

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

נתונה הפעולה `why` הבאה המקבלת שתי מחרוזות:

Java:

public static String why(String s1, String s2)
{
    String res1 = "";
    String res2 = "";
    while(s1.length()>0)
    {
        char ch = s1.charAt(0);
        int p = s2.indexOf(ch);
        if(p == -1)
            res1 = res1 + ch;   // (*)
        else
        {
            res2 = res2 + ch;
            s2 = s2.substring(0, p) + s2.substring(p+1);
        }
        s1 = s1.substring(1);
    }
    return res2 + res1;
}

C#:

public static string Why(string s1, string s2)
{
    string res1 = "";
    string res2 = "";
    while(s1.Length>0)
    {
        char ch = s1[0];
        int p = s2.IndexOf(ch);
        if(p == -1)
            res1 = res1 + ch;   // (*)
        else
        {
            res2 = res2 + ch;
            s2 = s2.Substring(0, p) + s2.Substring(p+1);
        }
        s1 = s1.Substring(1);
    }
    return res2 + res1;
}
א.

נתונות שתי מחרוזות `s1="GOODDAY"` ו-`s2="BOYSANDGIRLS"`.

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

(4 נקודות)
ב.

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

(2 נקודות)
ג.

הפקודה `res1 = res1 + ch;` המסומנת ב- (*) הוחלפה לפקודה הבאה

res2 = res2 +'%';

רשמו מה תהיה תוצאת זימון הפעולה `why(s1, s2)` עבור שתי מחרוזות `s1="GOODDAY"` ו- `s2="BOYSANDGIRLS"`.

(4 נקודות)
ד.

מה מבצעת הפעולה `why` באופן כללי אחרי השינוי?

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

סעיף א

תשובה:

`"GODAYOD"`

בכל סיבוב לוקחים את התו הראשון `ch` של `s1` ומחפשים אותו ב-`s2`. אם הוא לא נמצא (`p == -1`) הוא מצטרף ל-`res1`; אם נמצא - הוא מצטרף ל-`res2`, והמופע שנמצא נמחק מ-`s2`. בסוף הסיבוב מוחקים את התו הראשון של `s1`.

סיבובchpres1res2s2 בסוף הסיבובs1 בסוף הסיבוב
התחלה--""""BOYSANDGIRLSGOODDAY
1G7""GBOYSANDIRLSOODDAY
2O1""GOBYSANDIRLSODDAY
3O-1OGOBYSANDIRLSDDAY
4D5OGODBYSANIRLSDAY
5D-1ODGODBYSANIRLSAY
6A3ODGODABYSNIRLSY
7Y1ODGODAYBSNIRLS""

כעת `s1` ריקה והלולאה נעצרת. הפעולה מחזירה `res2 + res1 = "GODAY" + "OD"`.

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

סעיף ב

תשובה:

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

מהמעקב רואים:

1. כל תו של `s1` נבדק לפי הסדר. אם יש לו מופע ב-`s2` - הוא עובר ל-`res2`, והמופע הזה נמחק מ-`s2`, כך שכל תו של `s2` "מתאים" לתו אחד בלבד של `s1`. (לכן ה-O השנייה וה-D השנייה ב-"GOODDAY" לא מצאו התאמה: ב-"BOYSANDGIRLS" יש רק O אחת ו-D אחת.)

2. תו שאין לו (יותר) מופע ב-`s2` עובר ל-`res1`.

3. מוחזר `res2 + res1`.

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

תשובה: הפעולה מחזירה את תווי `s1` כך שבהתחלה מופיעים התווים שנמצאים גם ב-`s2` (כל תו של `s2` משמש פעם אחת), ואחריהם התווים שאין להם התאמה ב-`s2`.

סעיף ג

תשובה:

`"GO%D%AY"`

אחרי השינוי, תו שלא נמצא ב-`s2` לא נשמר ב-`res1`, אלא במקומו נוסף התו `'%'` ל-`res2`. `res1` נשאר ריק לאורך כל הביצוע.

החיפוש ב-`s2` והמחיקה ממנה לא השתנו, ולכן ערכי `p` זהים לסעיף א:

סיבובchpמה מתווסף ל-res2res2
1G7GG
2O1OGO
3O-1%GO%
4D5DGO%D
5D-1%GO%D%
6A3AGO%D%A
7Y1YGO%D%AY

מוחזר `res2 + res1 = "GO%D%AY" + ""`.

תשובה: `"GO%D%AY"`.

סעיף ד

תשובה:

מחזירה את `s1` כשכל תו שאין לו התאמה (פנויה) ב-`s2` מוחלף ב-`'%'`; התווים שיש להם התאמה נשארים במקומם.

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

תשובה: הפעולה מחזירה את `s1` כשכל תו שאין לו התאמה ב-`s2` מוחלף ב-`'%'`.

שאלה 8 · מחלקת טקס: צבירת נקודות ומציאת זוכה

בטקס בחירת שיר השנה משתתפים 30 שירים (לכל שיר מספר סידורי בין 1-30). בתחרות יש מספר לא ידוע של שופטים נסתרים. כל שופט בוחר שלושה שירים בסדר עדיפות יורד ורושם את מספריהם על הפתק.

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

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

לדוגמה:

אם שופט רשם על הפתק 6,25,20 (משמאל לימין) אז:

•שיר מספר 6 (מקום ראשון) מקבל חמש נקודות.

•שיר מספר 25 (מקום שני) מקבל שלוש נקודות.

•שיר מספר 20 (מקום שלישי) מקבל נקודה אחת.

התהליך מסתיים כאשר שופט מוסר למארגני הטקס את הפתק של שלושה אפסים (0,0,0)

בסוף הטקס מכריזים על "שיר השנה" – השיר שזכה במספר הגדול ביותר של נקודות.

נתונה מחלקה `Main` לניהול הטקס והצגת תוצאתו:

Java:

class Main{
     public static void main(String[] args){
     Ceremony c=new Ceremony();
     c.doChoices();
     System.out.println(c.winner());
   }
}

C#:

class Program{
     public static void Main(string[] args){
     Ceremony c=new Ceremony();
     c.DoChoices();
     Console.WriteLine(c.Winner());
   }
}
א.

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

(4 נקודות)
ב.

כתבו במחלקה `Ceremony` את הפעולה `doChoices()`. הפעולה תקלוט בחירות של השופטים שלושה מספרים שלמים בין 1-30 (כולל) עד שייקלטו שלושה אפסים ומעדכנת את מספר הנקודות של כל שיר.

אפשר להניח שהקלט תקין ואין צורך בבדיקת תקינות הקלט.

(4 נקודות)
ג.

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

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

סעיף א

תשובה:

תכונה אחת: מערך מונים `int[] points` בגודל 31 (תא לכל שיר 1-30); הפעולה הבונה יוצרת אותו (כל התאים 0).

הרעיון: כדי לצבור נקודות ל-30 שירים משתמשים במערך מונים: התא `points[k]` שומר את סך הנקודות של שיר מספר `k`. בוחרים מערך בגודל 31 ומשתמשים בתאים 1 עד 30, כך שמספר השיר הוא האינדקס עצמו (תא 0 לא בשימוש). כך עדכון הניקוד לשיר הוא פעולה אחת, בלי חיפוש.

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

Java:

public class Ceremony
{
    private int[] points;   // points[k] = מספר הנקודות של שיר מספר k

    public Ceremony()
    {
        this.points = new int[31];   // תאים 1..30, תא 0 לא בשימוש
    }
}

C#:

public class Ceremony
{
    private int[] points;   // points[k] = מספר הנקודות של שיר מספר k

    public Ceremony()
    {
        this.points = new int[31];   // תאים 1..30, תא 0 לא בשימוש
    }
}

תשובה: המחלקה `Ceremony` שלמעלה, עם מערך הנקודות `points` בגודל 31.

סעיף ב

תשובה:

לולאת זקיף: קולטים שלושה מספרים; כל עוד הם לא שלושה אפסים מוסיפים 5, 3, 1 לתאים המתאימים ב-`points` וקולטים את הפתק הבא.

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

1. קולטים את שלושת המספרים של הפתק הראשון לפני הלולאה.

2. הלולאה ממשיכה כל עוד לא שלושתם אפס: `first != 0 || second != 0 || third != 0`.

3. בתוך הלולאה מוסיפים 5 נקודות לשיר במקום הראשון, 3 לשיר במקום השני ונקודה אחת לשיר במקום השלישי: `points[first] += 5` וכן הלאה (מספר השיר הוא האינדקס במערך).

4. בסוף הסיבוב קולטים את הפתק הבא.

ב-Java נוצר בפעולה עצם `Scanner` לקליטה (ב-C# קולטים עם `Console.ReadLine()`).

Java:

public void doChoices()
{
    Scanner in = new Scanner(System.in);
    int first = in.nextInt();
    int second = in.nextInt();
    int third = in.nextInt();
    while (first != 0 || second != 0 || third != 0)
    {
        this.points[first] += 5;
        this.points[second] += 3;
        this.points[third] += 1;
        first = in.nextInt();
        second = in.nextInt();
        third = in.nextInt();
    }
}

C#:

public void DoChoices()
{
    int first = int.Parse(Console.ReadLine());
    int second = int.Parse(Console.ReadLine());
    int third = int.Parse(Console.ReadLine());
    while (first != 0 || second != 0 || third != 0)
    {
        this.points[first] += 5;
        this.points[second] += 3;
        this.points[third] += 1;
        first = int.Parse(Console.ReadLine());
        second = int.Parse(Console.ReadLine());
        third = int.Parse(Console.ReadLine());
    }
}

לדוגמה, עבור הפתקים (6,25,20)(6,25,20), (6,1,2)(6,1,2), (25,6,3)(25,6,3), (0,0,0)(0,0,0): שיר 6 מקבל 5+5+3=135+5+3=13 נקודות, שיר 25 מקבל 3+5=83+5=8, שיר 1 מקבל 3, ושירים 20, 2 ו-3 מקבלים נקודה אחת כל אחד.

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

סעיף ג

תשובה:

מחפשים את האינדקס `k` בין 1 ל-30 שבו `points[k]` מקסימלי ומחזירים אותו.

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

1. מניחים ששיר 1 הוא המוביל (`best = 1`).

2. עוברים על השירים 2 עד 30; אם לשיר `k` יש יותר נקודות מלמוביל - הוא המוביל החדש.

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

Java:

public int winner()
{
    int best = 1;
    for (int k = 2; k <= 30; k++)
        if (this.points[k] > this.points[best])
            best = k;
    return best;
}

C#:

public int Winner()
{
    int best = 1;
    for (int k = 2; k <= 30; k++)
        if (this.points[k] > this.points[best])
            best = k;
    return best;
}

בדוגמה מסעיף ב שיר 6 צבר 13 נקודות - יותר מכל שיר אחר, ולכן התוכנית `Main` תדפיס 6.

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

שאלה 9 · מערך מלא: בדיקה במערך כללי וממוין

הגדרה:

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

לדוגמה: המערך `int[] a={23,30,24,29,25,28,26,31,27}` הוא "מערך מלא" כי הוא כולל את כל המספרים בין 23 ל-31.

א.

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

(8 נקודות)
ב.

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

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

סעיף א

תשובה:

מוצאים `min` ו-`max`; אם `max-min+1` שונה מאורך המערך - `false`; אחרת מסמנים כל ערך במערך בוליאני `seen[v-min]` ואם ערך מופיע פעמיים - `false`; אחרת `true`.

הרעיון: במערך מלא יש בדיוק את המספרים min,min+1,…,maxmin, min+1, \dots, max, כל אחד פעם אחת. לכן:

•מספר האיברים חייב להיות max−min+1max-min+1;

•ואין חזרות.

אם שני התנאים מתקיימים, יש במערך max−min+1max-min+1 ערכים שונים, כולם בטווח [min,max][min,max] שיש בו בדיוק max−min+1max-min+1 מספרים - כלומר כל מספר בטווח מופיע.

1. מוצאים את `min` ואת `max` במעבר אחד.

2. אם `max - min + 1 != arr.length` - מחזירים `false`.

3. בודקים חזרות בעזרת מערך בוליאני `seen` באורך המערך: הערך `v` "שייך" לתא `v - min` (בין 0 ל-`length-1`, לפי שלב 2). אם התא כבר מסומן - הערך מופיע פעמיים, מחזירים `false`; אחרת מסמנים אותו.

4. אם לא נמצאה חזרה - מחזירים `true`.

Java:

public static boolean isFull(int[] arr)
{
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++)
    {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    // צריך בדיוק max-min+1 מספרים שונים
    if (max - min + 1 != arr.length)
        return false;
    boolean[] seen = new boolean[arr.length];   // seen[v-min] - האם v כבר הופיע
    for (int i = 0; i < arr.length; i++)
    {
        int place = arr[i] - min;
        if (seen[place])
            return false;                       // מספר שמופיע פעמיים
        seen[place] = true;
    }
    return true;
}

C#:

public static bool IsFull(int[] arr)
{
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    // צריך בדיוק max-min+1 מספרים שונים
    if (max - min + 1 != arr.Length)
        return false;
    bool[] seen = new bool[arr.Length];   // seen[v-min] - האם v כבר הופיע
    for (int i = 0; i < arr.Length; i++)
    {
        int place = arr[i] - min;
        if (seen[place])
            return false;                 // מספר שמופיע פעמיים
        seen[place] = true;
    }
    return true;
}

בדוגמה: min=23min=23, max=31max=31, 31−23+1=931-23+1=9 - כמו אורך המערך, ואין חזרות - מוחזר `true`. עבור {1,2,2,4}\{1,2,2,4\}: 4−1+1=44-1+1=4 - האורך מתאים, אבל 2 מופיע פעמיים - מוחזר `false`. עבור {1,3}\{1,3\}: 3−1+1=3≠23-1+1=3\neq 2 - מוחזר `false`.

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

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

סעיף ב

תשובה:

`arr[arr.length-1] - arr[0] == arr.length - 1` - בדיקה אחת, O(1)O(1).

הרעיון: כשהמערך ממוין בסדר עולה ממש, אין חזרות, `arr[0]` הוא המינימום והאיבר האחרון הוא המקסימום. בין nn מספרים שלמים שונים ועולים, ההפרש בין האחרון לראשון הוא לפחות n−1n-1 (כל צעד מגדיל ב-1 לפחות), ושוויון מתקיים בדיוק כשכל צעד הוא 1 - כלומר כשאין "חורים".

לכן המערך מלא אם ורק אם arr[n−1]−arr[0]=n−1arr[n-1]-arr[0]=n-1.

Java:

public static boolean isFullSorted(int[] arr)
{
    return arr[arr.length - 1] - arr[0] == arr.length - 1;
}

C#:

public static bool IsFullSorted(int[] arr)
{
    return arr[arr.Length - 1] - arr[0] == arr.Length - 1;
}

לדוגמה, {3,4,5,6}\{3,4,5,6\}: 6−3=3=4−16-3=3=4-1 - מלא; {3,4,6}\{3,4,6\}: 6−3=3≠26-3=3\neq 2 - לא מלא.

סיבוכיות: O(1)O(1) - בלי לולאה.

תשובה: הפעולה `isFullSorted` שלמעלה - בודקת שההפרש בין האיבר האחרון לראשון שווה לאורך המערך פחות 1.

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

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

Java:

public static int what ( int[] arr )
{
    int answer = -1;
    for (int k = 0; k < arr.length-1 && answer  == -1; k++)
        if (arr[k] < arr[k+1])
            answer = k;
    return answer;
}


public static void something ( int[] arr, int k )
{
    int temp = arr[k];
    arr[k] = arr[k+1];
    arr[k+1] = temp;
}


public static void secret ( int[] arr )
{
    int k = what( arr );
    while (k != -1)
    {
        something( arr, k );
        k = what( arr );
    }
}

C#:

public static int What ( int[] arr )
{
    int answer = -1;
    for (int k = 0; k < arr.Length-1 && answer  == -1; k++)
        if (arr[k] < arr[k+1])
            answer = k;
    return answer;
}


public static void Something ( int[] arr, int k )
{
    int temp = arr[k];
    arr[k] = arr[k+1];
    arr[k+1] = temp;
}


public static void Secret ( int[] arr )
{
    int k = What( arr );
    while (k != -1)
    {
        Something( arr, k );
        k = What( arr );
    }
}
א.

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

`int[] a={17, 9, 4, 8, -3, 1, 4}`

(4 נקודות)
ב.

מה יחזיר זימון הפעולה `what(b)` עבור המערך `int[] b={-5, -3, 0, 11,13,15,18}`?

(1 נקודות)
ג.

תנו דוגמה למערך `c` בגודל שישה תאים שעבורו הזימון `what(c)` יחזיר -1.

(1 נקודות)
ד.

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

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

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

(4 נקודות)
ה.

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

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

סעיף א

תשובה:

`what(a)` מחזירה 2.

הפעולה `what` עוברת על זוגות של תאים סמוכים ועוצרת בזוג הראשון שבו `arr[k] < arr[k+1]`, כי אז `answer` כבר לא −1-1.

karr[k]arr[k+1]`arr[k] < arr[k+1]` ?answer
0179לא-1
194לא-1
248כן2
3--הלולאה נעצרת (`answer != -1`)2

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

סעיף ב

תשובה:

0

כבר בזוג הראשון −5<−3-5<-3, ולכן `answer = 0` והלולאה נעצרת.

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

סעיף ג

תשובה:

למשל `int[] c={6, 5, 4, 3, 2, 1}` (כל מערך שאינו עולה בשום זוג סמוך, כלומר ממוין בסדר יורד או שווה).

הפעולה מחזירה −1-1 רק אם אין אף זוג סמוך שבו `arr[k] < arr[k+1]`, כלומר כל איבר גדול או שווה לאיבר שאחריו - המערך ממוין בסדר יורד (לא עולה). לדוגמה {6,5,4,3,2,1}\{6,5,4,3,2,1\}: 6≥5≥4≥3≥2≥16\ge5\ge4\ge3\ge2\ge1. (גם {5,5,5,5,5,5}\{5,5,5,5,5,5\} מתאים.)

תשובה: `int[] c={6, 5, 4, 3, 2, 1}`.

סעיף ד

תשובה:

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

בכל סיבוב `what` מוצאת את הזוג הסמוך הראשון שבו האיבר השמאלי קטן מהימני, ו-`something` מחליפה בין שני האיברים. התהליך נעצר כש-`what` מחזירה −1-1.

סיבובהמערך לפניk = what(d)המערך אחרי something(d, k)
17, 9, 2, 8, 3, 109, 7, 2, 8, 3, 1
29, 7, 2, 8, 3, 129, 7, 8, 2, 3, 1
39, 7, 8, 2, 3, 119, 8, 7, 2, 3, 1
49, 8, 7, 2, 3, 139, 8, 7, 3, 2, 1
59, 8, 7, 3, 2, 1-1הלולאה נעצרת

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

סעיף ה

תשובה:

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

הסבר:

1. `what` מחזירה את המקום של הזוג הסמוך הראשון שבו `arr[k] < arr[k+1]` - זוג שנמצא "בסדר הפוך" ביחס למיון יורד.

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

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

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

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

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

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

לדוגמה:

- "רמת הזוגיות" של 543 היא -4.

- "רמת הזוגיות" של 4637 היא 0.

- "רמת הזוגיות" של 83 היא 5.

א.

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

(4 נקודות)

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

ב.

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

(6 נקודות)
ג.

כתבו פעולה המקבלת מערך של מספרים שלמים וחיוביים `arr` ומחזירה מערך חדש הבנוי לפי הכללים הבאים:

•אחרי כל ערך מ- `arr` מופיעה "רמת הזוגיות" שלו.

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

לדוגמה:

עבור המערך

אינדקס01234
ערך6745852221457

הפעולה תחזיר מערך חדש

אינדקס0123456789
ערך74-3457-858520662213
תוכןאיבר ממערךרמת הזוגיותאיבר ממערךרמת הזוגיותאיבר ממערךרמת הזוגיותאיבר ממערךרמת הזוגיותאיבר ממערךרמת הזוגיות
(8 נקודות)
◂ פתרון מלא לשאלה 11

סעיף א

תשובה:

מפרקים את המספר לספרות (`% 10`, `/ 10`); ספרה זוגית מוסיפים לצובר וספרה אי-זוגית מחסירים; מחזירים את הצובר.

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

1. כל עוד המספר גדול מ-0: הספרה הימנית היא `num % 10`.

2. אם הספרה זוגית (`dig % 2 == 0`) מוסיפים אותה לצובר `level`, אחרת מחסירים אותה.

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

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

Java:

public static int parityLevel(int num)
{
    int level = 0;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig % 2 == 0)
            level += dig;    // ספרה זוגית - מוסיפים
        else
            level -= dig;    // ספרה אי-זוגית - מחסירים
        num = num / 10;
    }
    return level;
}

C#:

public static int ParityLevel(int num)
{
    int level = 0;
    while (num > 0)
    {
        int dig = num % 10;
        if (dig % 2 == 0)
            level += dig;    // ספרה זוגית - מוסיפים
        else
            level -= dig;    // ספרה אי-זוגית - מחסירים
        num = num / 10;
    }
    return level;
}

בדיקה עם הדוגמאות: 543543: 4−(5+3)=−44-(5+3)=-4; 46374637: (4+6)−(3+7)=0(4+6)-(3+7)=0; 8383: 8−3=58-3=5.

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

סעיף ב

תשובה:

עבור כל איבר של `arr1` מחפשים ב-`arr2` איבר עם אותה רמת זוגיות (בעזרת הפעולה מסעיף א); אם לאיבר כלשהו אין כזה - `false`, אחרת `true`.

הרעיון: התנאי הוא "לכל מספר ב-`arr1` קיים מספר מתאים ב-`arr2`", ולכן: לולאה חיצונית על `arr1`, ובתוכה חיפוש ב-`arr2`.

1. עבור כל `arr1[i]` מחשבים את רמת הזוגיות שלו בעזרת `parityLevel` מסעיף א.

2. מחפשים ב-`arr2` איבר שרמת הזוגיות שלו שווה לה. משתנה בוליאני `found` עוצר את החיפוש כשנמצאה התאמה.

3. אם לא נמצאה התאמה - `arr1[i]` מפר את התנאי, ומחזירים `false` מיד.

4. אם כל האיברים של `arr1` מצאו התאמה - מחזירים `true`.

Java:

public static boolean isSubByLevel(int[] arr1, int[] arr2)
{
    for (int i = 0; i < arr1.length; i++)
    {
        int level = parityLevel(arr1[i]);
        boolean found = false;
        for (int j = 0; j < arr2.length && !found; j++)
            if (parityLevel(arr2[j]) == level)
                found = true;
        if (!found)
            return false;
    }
    return true;
}

C#:

public static bool IsSubByLevel(int[] arr1, int[] arr2)
{
    for (int i = 0; i < arr1.Length; i++)
    {
        int level = ParityLevel(arr1[i]);
        bool found = false;
        for (int j = 0; j < arr2.Length && !found; j++)
            if (ParityLevel(arr2[j]) == level)
                found = true;
        if (!found)
            return false;
    }
    return true;
}

לדוגמה, `arr1 = {543, 83}` (רמות −4-4 ו-55) ו-`arr2 = {345, 38, 1}` (רמות −4-4, 55, −1-1): לשני האיברים יש התאמה - מוחזר `true`. אם `arr2 = {5, 4637, 1, 8}` (רמות −5-5, 00, −1-1, 88) - ל-543 אין התאמה, ומוחזר `false`.

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

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

סעיף ג

תשובה:

יוצרים מערך באורך `2*arr.length` ועוברים על `arr` שלוש פעמים: קודם מעתיקים את המספרים עם רמה שלילית, אחר כך עם רמה 0, ואחר כך עם רמה חיובית - כל מספר ואחריו הרמה שלו.

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

1. במעבר הראשון מעתיקים רק מספרים עם רמת זוגיות שלילית;

2. במעבר השני - רק מספרים עם רמה 0;

3. במעבר השלישי - רק מספרים עם רמה חיובית.

בכל העתקה כותבים את המספר בתא `pos` ואת הרמה שלו בתא `pos + 1`, ומקדמים את `pos` ב-2. כך, בתוך כל קבוצה המספרים נשארים בסדר שבו הופיעו ב-`arr`, בדיוק כמו בדוגמה. כל מספר מועתק פעם אחת בדיוק (הוא שייך לקבוצה אחת), ולכן המערך החדש מתמלא עד הסוף.

Java:

public static int[] buildByLevel(int[] arr)
{
    int[] res = new int[2 * arr.length];
    int pos = 0;
    // מעבר 1: רמת זוגיות שלילית, מעבר 2: אפס, מעבר 3: חיובית
    for (int pass = 1; pass <= 3; pass++)
    {
        for (int i = 0; i < arr.length; i++)
        {
            int level = parityLevel(arr[i]);
            if ((pass == 1 && level < 0) || (pass == 2 && level == 0)
                    || (pass == 3 && level > 0))
            {
                res[pos] = arr[i];
                res[pos + 1] = level;
                pos += 2;
            }
        }
    }
    return res;
}

C#:

public static int[] BuildByLevel(int[] arr)
{
    int[] res = new int[2 * arr.Length];
    int pos = 0;
    // מעבר 1: רמת זוגיות שלילית, מעבר 2: אפס, מעבר 3: חיובית
    for (int pass = 1; pass <= 3; pass++)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            int level = ParityLevel(arr[i]);
            if ((pass == 1 && level < 0) || (pass == 2 && level == 0)
                    || (pass == 3 && level > 0))
            {
                res[pos] = arr[i];
                res[pos + 1] = level;
                pos += 2;
            }
        }
    }
    return res;
}

בדוגמה: הרמות הן 6→66\to6, 74→−374\to-3, 5852→05852\to0, 221→3221\to3, 457→−8457\to-8. במעבר הראשון נכתבים 74, -3, 457, -8; בשני 5852, 0; בשלישי 6, 6, 221, 3 - בדיוק המערך שבשאלה.

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

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

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

נתונה מחלקה `TwoNum` הבאה:

Java:

class TwoNum
{
  private int num1;
  private int num2;
  public TwoNum(int num)
  {
    if(num<0)num = num*(-1);
    int dig = num % 10;
    this.num1 = dig;
    this.num2 = dig;
    num = num / 10;
    while(num > 0)
    {
      dig = num % 10;
      if(dig < this.num1) this.num1 = dig;
      else
        if (dig> this.num2) this.num2 = dig;
      num=num/10;
    }
  }
  public String toString()
  {
    return this.num1+"-"+this.num2;
  }
  public int dif()
  {
    return this.num2 - this.num1;
  }
}

C#:

class TwoNum
{
  private int num1;
  private int num2;
  public TwoNum(int num)
  {
    if(num < 0)num = num*(-1);
    int dig = num % 10;
    this.num1 = dig;
    this.num2 = dig;
    num = num / 10;
    while(num > 0)
    {
      dig = num % 10;
      if(dig < this.num1) this.num1 = dig;
      else
        if (dig> this.num2) this.num2 = dig;
      num=num/10;
    }
  }
  public override string ToString()
  {
    return this.num1+"-"+this.num2;
  }
  public int Dif()
  {
    return this.num2 - this.num1;
  }
}
א.

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

Java:

TwoNum a = new TwoNum(23176);
System.out.println(a);
System.out.println(a.dif());

C#:

TwoNum a = new TwoNum(23176);
Console.WriteLine( a );
Console.WriteLine( a.Dif() );
(6 נקודות)
ב.

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

(2 נקודות)

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

Java:

public static int[] secret(int [] arr)
{
  TwoNum temp = new TwoNum(arr[0]);
  TwoNum temp1 = new TwoNum(arr[0]);
  int ind = 0;
  int ind1 = 0;

  TwoNum cur;
  for(int i = 1; i < arr.length; i++)
  {
    cur = new TwoNum(arr[i]);
    if(cur.dif() < temp.dif())
    {
      temp1 = temp;
      temp = cur;
      ind1 = ind;
      ind = i;
    }
    else
    {
      if(cur.dif() < temp1.dif())
      {
        temp1 = cur;
        ind1 = i;
      }
    }
  }
  int[] res = new int[2];
  res[0] = arr[ind];
  res[1] = arr[ind1];

  return res;
}

C#:

public static int[] Secret(int [] arr)
{
  TwoNum temp = new TwoNum(arr[0]);
  TwoNum temp1 = new TwoNum(arr[0]);
  int ind = 0;
  int ind1 = 0;

  TwoNum cur;
  for(int i = 1; i < arr.Length; i++)
  {
    cur = new TwoNum(arr[i]);
    if(cur.Dif() < temp.Dif())
    {
      temp1 = temp;
      temp = cur;
      ind1 = ind;
      ind = i;
    }
    else
    {
      if(cur.Dif() < temp1.Dif())
      {
        temp1 = cur;
        ind1 = i;
      }
    }
  }
  int[] res = new int[2];
  res[0] = arr[ind];
  res[1] = arr[ind1];

  return res;
}
ג.

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

Java:

int[] a = {3458,45, 7341, 6, 13579, 86 };
int[] b = secret(a);
System.out.println(b[0]+" "+b[1]);

C#:

int[] a = {3458,45, 7341, 6, 13579, 86 };
int[] b = Secret(a);
Console.WriteLine (b[0]+" "+b[1]);
(10 נקודות)
◂ פתרון מלא לשאלה 12

סעיף א

תשובה:

הפלט: `1-7` ובשורה הבאה `6`.

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

שלבdig`dig < num1` ?`dig > num2` ?num1num2num אחרי החילוק
לפני הלולאה6--662317
סיבוב 17לאכן67231
סיבוב 21כן(לא נבדק)1723
סיבוב 33לאלא172
סיבוב 42לאלא170

הלולאה נעצרת כש-`num` מגיע ל-0. בעצם `a`: `num1 = 1`, `num2 = 7`.

•הדפסת `a` מפעילה את `toString` ומדפיסה `1-7`.

•`a.dif()` מחזירה 7−1=67-1=6.

תשובה: הפלט הוא

1-7
6

סעיף ב

תשובה:

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

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

•ספרות הן בין 0 ל-9, ולכן ההפרש הגדול ביותר הוא 9−0=99-0=9, למשל עבור המספר 90.

•ההפרש הקטן ביותר הוא 00, כאשר כל הספרות שוות, למשל עבור 5 או 777. ההפרש לא יכול להיות שלילי, כי תמיד `num2` ≥\ge `num1`.

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

סעיף ג

תשובה:

הפלט: `6 45`.

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

אינדקסמספרספרה קטנה - גדולהdif()
034583-85
1454-51
273411-76
366-60
4135791-98
5866-82

בפעולה `secret`, `temp` הוא העצם עם ה-`dif` הקטן ביותר עד כה (במקום `ind`) ו-`temp1` הוא "השני" (במקום `ind1`). בהתחלה שניהם נוצרים מ-`arr[0]` (dif = 5), ו-`ind = ind1 = 0`.

iarr[i]cur.dif()השוואהtemp.dif()indtemp1.dif()ind1
התחלה---5050
14511<51<5: הראשון יורד למקום השני1150
2734166<16<1 לא, 6<56<5 לא1150
3600<10<1: הראשון יורד למקום השני0311
41357988<08<0 לא, 8<18<1 לא0311
58622<02<0 לא, 2<12<1 לא0311

בסוף `res[0] = arr[3] = 6` ו-`res[1] = arr[1] = 45`, והשורה המודפסת היא `b[0]+" "+b[1]`.

(באופן כללי `secret` מחזירה את שני המספרים עם ה-`dif` הקטן ביותר: הקטן ביותר בתא 0 והבא אחריו בתא 1.)

תשובה: הפלט הוא `6 45`.

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

לפניכם הגדרה לטיפוס עיפרון דו צבעי - `Pencil`:

•`color1` – צבע ראשון מטיפוס מחרוזת, `String`.

•`color2` – צבע שני מטיפוס מחרוזת, `String`.

•`size` – אורך העיפרון מטיפוס מספר שלם, `int`.

במחלקה `Pencil` קיימות פעולה בונה המקבלת פרמטרים לאתחול כל התכונות, פעולות מאחזרות (`get`) ופעולות קובעות (`set`) לכל התכונות של המחלקה.

א.

כתבו פעולה המקבלת כפרמטר עיפרון (עצם מטיפוס `Pencil`) ומחזירה `true` אם הצבעים של `other` זהים לצבעים של העצם שמפעיל את הפעולה (`this`), ולא הפעולה תחזיר `false`. כותרת הפעולה:

Java:

public boolean isSameColors(Pencil other)

C#:

public bool IsSameColors(Pencil other)
(2 נקודות)

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

•`allPencils` – מערך עפרונות (מערך עצמים מטיפוס `Pencil`). גודל המערך מוגדר בפעולה הבונה.

•`colors` – מערך צבעים מטיפוס מחרוזת, `String`. המערך צבעים יכול להשתנות מחבילה לחבילה וגם הוא מתקבל כפרמטר בפעולה הבונה.

•`currNum` – מספר העפרונות בחבילה.

•`max, min` – שני מספרים שלמים המציינים אורך מקסימלי ואורך מינימלי של העיפרון בחבילה.

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

Java:

public Pack(int num, String[] colors, int min, int max)
{
    this.allPencils = new Pencil[num];
    this.colors = colors;
    this.currNum = 0;
    this.min = min;
    this.max = max;
}

C#:

public Pack(int num, string[] colors, int min, int max)
{
    this.allPencils = new Pencil[num];
    this.colors = colors;
    this.currNum = 0;
    this.min = min;
    this.max = max;
}

עיפרון דו-צבעי מתאים לחבילה אם האורך שלו נמצא בטווח של `(min, max)` וצבעיו שונים זה מזה ומתאימים לצבעים של החבילה.

ב.

•כתבו פעולה המקבלת כפרמטר עיפרון (עצם מטיפוס `Pencil`) ומחזירה `true` אם הוא מתאים לחבילה. ולא הפעולה תחזיר `false`. כותרת הפעולה:

Java:

public boolean isFit ( Pencil p )

C#:

public bool IsFit ( Pencil p )

•כתבו פעולה המקבלת עיפרון (עצם מטיפוס `Pencil`) ומוסיפה אותו לחבילה. אפשר להוסיף עיפרון לחבילה אם הוא מתאים לחבילה ובחבילה יש מקום. כותרת הפעולה:

Java:

public boolean add ( Pencil p )

C#:

public bool Add ( Pencil p )

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

(6 נקודות)
ג.

כתבו פעולה `public int countColor (String color)`. הפעולה תחזיר מספר עפרונות שאחד מהצבעים שלהם הוא `color`.

(4 נקודות)
ד.

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

Java:

public String[] missing()

C#:

public string[] Missing()

אם אין צבעים (יש לפחות עיפרון אחד שבו יש צבע מתוך המערך `colors`) יש להחזיר מערך בגודל 0

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

סעיף א

תשובה:

מחזירה `true` אם זוג הצבעים זהה - באותו סדר (`color1`=`color1`, `color2`=`color2`) או בסדר הפוך.

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

1. התאמה ישירה: `color1` של `this` שווה ל-`color1` של `other`, ו-`color2` שווה ל-`color2`.

2. התאמה הפוכה: `color1` של `this` שווה ל-`color2` של `other`, ו-`color2` שווה ל-`color1`.

3. מחזירים `true` אם אחת מהן מתקיימת.

השוואת מחרוזות נעשית ב-Java עם `equals` (ב-C# אפשר עם `==`). הפעולה כתובה בתוך המחלקה `Pencil`.

Java:

public boolean isSameColors(Pencil other)
{
    return (this.color1.equals(other.getColor1()) && this.color2.equals(other.getColor2()))
        || (this.color1.equals(other.getColor2()) && this.color2.equals(other.getColor1()));
}

C#:

public bool IsSameColors(Pencil other)
{
    return (this.color1 == other.GetColor1() && this.color2 == other.GetColor2())
        || (this.color1 == other.GetColor2() && this.color2 == other.GetColor1());
}

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

סעיף ב

תשובה:

`isFit`: האורך בין `min` ל-`max`, שני הצבעים שונים, ושניהם מופיעים במערך `colors` (פעולת עזר `inColors`). `add`: אם העיפרון מתאים ו-`currNum` קטן מאורך המערך - מכניסים אותו לתא `currNum`, מגדילים את `currNum` ומחזירים `true`; אחרת `false`.

הרעיון ל-`isFit`: מתרגמים את ההגדרה לשלושה תנאים שכולם צריכים להתקיים:

1. האורך בטווח: `min <= size <= max`. (בשאלה כתוב "בטווח של (min, max)"; פירשנו את הטווח כולל הקצוות, כי `min` ו-`max` הם האורך המינימלי והמקסימלי המותרים בחבילה.)

2. שני הצבעים שונים זה מזה: `!color1.equals(color2)`.

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

לתנאי 3 כותבים פעולת עזר פרטית במחלקה `Pack`: `inColors(String c)` - טענת כניסה: צבע `c`; טענת יציאה: מחזירה `true` אם `c` נמצא במערך `colors` של החבילה, ואחרת `false`.

הרעיון ל-`add`: העיפרון נכנס רק אם הוא מתאים (`isFit`) ויש מקום (`currNum < allPencils.length`). העפרונות שמורים בתחילת המערך, בתאים 00 עד currNum−1currNum-1, ולכן התא הפנוי הבא הוא `allPencils[currNum]`. אחרי ההכנסה מגדילים את `currNum` ומחזירים `true`. אם אחד התנאים לא מתקיים - מחזירים `false` בלי לשנות דבר.

Java:

// פעולת עזר: האם הצבע c נמצא במערך הצבעים של החבילה
private boolean inColors(String c)
{
    for (int i = 0; i < this.colors.length; i++)
        if (this.colors[i].equals(c))
            return true;
    return false;
}

public boolean isFit(Pencil p)
{
    return p.getSize() >= this.min && p.getSize() <= this.max
        && !p.getColor1().equals(p.getColor2())
        && inColors(p.getColor1()) && inColors(p.getColor2());
}

public boolean add(Pencil p)
{
    if (!isFit(p) || this.currNum == this.allPencils.length)
        return false;
    this.allPencils[this.currNum] = p;
    this.currNum++;
    return true;
}

C#:

// פעולת עזר: האם הצבע c נמצא במערך הצבעים של החבילה
private bool InColors(string c)
{
    for (int i = 0; i < this.colors.Length; i++)
        if (this.colors[i] == c)
            return true;
    return false;
}

public bool IsFit(Pencil p)
{
    return p.GetSize() >= this.min && p.GetSize() <= this.max
        && p.GetColor1() != p.GetColor2()
        && InColors(p.GetColor1()) && InColors(p.GetColor2());
}

public bool Add(Pencil p)
{
    if (!IsFit(p) || this.currNum == this.allPencils.Length)
        return false;
    this.allPencils[this.currNum] = p;
    this.currNum++;
    return true;
}

לדוגמה, בחבילה עם הצבעים red, blue, green, black והאורכים 10 עד 20: עיפרון red-blue באורך 15 מתאים; red-red לא מתאים (צבעים זהים); red-pink לא מתאים (pink לא בחבילה); red-blue באורך 21 לא מתאים (ארוך מדי).

תשובה: הפעולות `isFit` ו-`add` שלמעלה (עם פעולת העזר `inColors`).

סעיף ג

תשובה:

עוברים על העפרונות בתאים 0 עד `currNum-1` וסופרים את אלה ש-`color1` או `color2` שלהם שווה ל-`color`.

הרעיון: ספירה בתנאי, על העפרונות שנמצאים בחבילה בלבד - בתאים 00 עד currNum−1currNum-1 (שאר התאים ריקים).

1. מונה `count` מתחיל ב-0.

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

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

ב-C# כותרת הפעולה: `public int CountColor (string color)`.

Java:

public int countColor(String color)
{
    int count = 0;
    for (int i = 0; i < this.currNum; i++)
        if (this.allPencils[i].getColor1().equals(color)
                || this.allPencils[i].getColor2().equals(color))
            count++;
    return count;
}

C#:

public int CountColor(string color)
{
    int count = 0;
    for (int i = 0; i < this.currNum; i++)
        if (this.allPencils[i].GetColor1() == color
                || this.allPencils[i].GetColor2() == color)
            count++;
    return count;
}

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

סעיף ד

תשובה:

צבע חסר = צבע מ-`colors` ש-`countColor` שלו 0. סופרים כמה כאלה, יוצרים מערך בגודל הזה וממלאים אותו בצבעים החסרים (אם אין - מוחזר מערך בגודל 0).

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

1. סופרים כמה צבעים מתוך `colors` חסרים.

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

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

Java:

public String[] missing()
{
    // שלב 1: סופרים כמה צבעים חסרים
    int cnt = 0;
    for (int i = 0; i < this.colors.length; i++)
        if (countColor(this.colors[i]) == 0)
            cnt++;
    // שלב 2: יוצרים מערך בגודל המדויק וממלאים אותו
    String[] res = new String[cnt];
    int pos = 0;
    for (int i = 0; i < this.colors.length; i++)
        if (countColor(this.colors[i]) == 0)
        {
            res[pos] = this.colors[i];
            pos++;
        }
    return res;
}

C#:

public string[] Missing()
{
    // שלב 1: סופרים כמה צבעים חסרים
    int cnt = 0;
    for (int i = 0; i < this.colors.Length; i++)
        if (CountColor(this.colors[i]) == 0)
            cnt++;
    // שלב 2: יוצרים מערך בגודל המדויק וממלאים אותו
    string[] res = new string[cnt];
    int pos = 0;
    for (int i = 0; i < this.colors.Length; i++)
        if (CountColor(this.colors[i]) == 0)
        {
            res[pos] = this.colors[i];
            pos++;
        }
    return res;
}

לדוגמה, בחבילה עם הצבעים red, blue, green, black שבה העפרונות red-blue, blue-green, red-green - הצבע black חסר, ומוחזר מערך עם המחרוזת "black" בלבד.

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

שאלה 14 · מאגר בתי ספר: מחלקות וחיפוש מורים

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

במשרד החינוך רשומים 200 בתי ספר הממוספרים מ- 1 עד 200.

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

•שם בית הספר

•שם מנהל בית הספר

•מערך המורים המלמדים בבית הספר

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

א.

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

•מורה `Teacher`

•בית הספר `School`

•מאגר בתי הספר `AllSchools`

(2 נקודות)
ב.

כתבו פעולה בונה ופעולה `toString()` לכל אחת מהמחלקות.

(4 נקודות)
ג.

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

(6 נקודות)
ד.

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

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

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

סעיף א

תשובה:

`Teacher`: `id`, `name`, `academic` (בוליאני - השכלה אוניברסיטאית); `School`: `name`, `manager`, `Teacher[] teachers`; `AllSchools`: `School[] schools` בגודל 200.

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

•מורה: מספר זיהוי ושם. סעיף ד שואל על מורים "בעלי השכלה אוניברסיטאית", ולכן מוסיפים (כפי שהשאלה מתירה) תכונה בוליאנית `academic` שמציינת אם למורה השכלה אוניברסיטאית.

•בית ספר: שם, שם המנהל ומערך של מורים (מערך עצמים מטיפוס `Teacher`).

•מאגר בתי הספר: מערך של 200 בתי ספר. בית הספר שמספרו kk (1 עד 200) נשמר בתא k−1k-1.

כל התכונות פרטיות.

Java:

public class Teacher
{
    private int id;              // מספר זיהוי
    private String name;         // שם המורה
    private boolean academic;    // האם בעל השכלה אוניברסיטאית
}

public class School
{
    private String name;         // שם בית הספר
    private String manager;      // שם מנהל בית הספר
    private Teacher[] teachers;  // מערך המורים המלמדים בבית הספר
}

public class AllSchools
{
    private School[] schools;    // schools[k-1] = בית הספר שמספרו k (1..200)
}

C#:

public class Teacher
{
    private int id;              // מספר זיהוי
    private string name;         // שם המורה
    private bool academic;       // האם בעל השכלה אוניברסיטאית
}

public class School
{
    private string name;         // שם בית הספר
    private string manager;      // שם מנהל בית הספר
    private Teacher[] teachers;  // מערך המורים המלמדים בבית הספר
}

public class AllSchools
{
    private School[] schools;    // schools[k-1] = בית הספר שמספרו k (1..200)
}

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

סעיף ב

תשובה:

בונה לכל מחלקה (ל-`AllSchools` - יוצרת מערך של 200 בתי ספר); `toString` מחזירה מחרוזת עם פרטי העצם, ובמחלקות המכילות - גם את ה-`toString` של העצמים שבמערך.

הרעיון:

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

•`School`: הבונה מקבלת שם, שם מנהל ומערך מורים. `toString` מחזירה את השם והמנהל, ובשורות נפרדות את ה-`toString` של כל מורה.

•`AllSchools`: הבונה יוצרת מערך של 200 תאים (בהתחלה ריקים - `null`, עד שבתי הספר נרשמים). `toString` מחברת את המחרוזות של כל בתי הספר הרשומים, כל אחד עם מספרו (k+1k+1 לתא kk), ומדלגת על תאים ריקים.

ב-C# הפעולה נקראת `ToString` ומוגדרת עם `override`.

Java:

// ---- במחלקה Teacher ----
public Teacher(int id, String name, boolean academic)
{
    this.id = id;
    this.name = name;
    this.academic = academic;
}

public String toString()
{
    String s = "Teacher " + this.id + " " + this.name;
    if (this.academic)
        s = s + " (academic)";
    return s;
}

// ---- במחלקה School ----
public School(String name, String manager, Teacher[] teachers)
{
    this.name = name;
    this.manager = manager;
    this.teachers = teachers;
}

public String toString()
{
    String s = "School: " + this.name + ", manager: " + this.manager + "\n";
    for (int i = 0; i < this.teachers.length; i++)
        s = s + this.teachers[i].toString() + "\n";
    return s;
}

// ---- במחלקה AllSchools ----
public AllSchools()
{
    this.schools = new School[200];
}

public String toString()
{
    String s = "";
    for (int k = 0; k < this.schools.length; k++)
        if (this.schools[k] != null)
            s = s + (k + 1) + ". " + this.schools[k].toString();
    return s;
}

C#:

// ---- במחלקה Teacher ----
public Teacher(int id, string name, bool academic)
{
    this.id = id;
    this.name = name;
    this.academic = academic;
}

public override string ToString()
{
    string s = "Teacher " + this.id + " " + this.name;
    if (this.academic)
        s = s + " (academic)";
    return s;
}

// ---- במחלקה School ----
public School(string name, string manager, Teacher[] teachers)
{
    this.name = name;
    this.manager = manager;
    this.teachers = teachers;
}

public override string ToString()
{
    string s = "School: " + this.name + ", manager: " + this.manager + "\n";
    for (int i = 0; i < this.teachers.Length; i++)
        s = s + this.teachers[i].ToString() + "\n";
    return s;
}

// ---- במחלקה AllSchools ----
public AllSchools()
{
    this.schools = new School[200];
}

public override string ToString()
{
    string s = "";
    for (int k = 0; k < this.schools.Length; k++)
        if (this.schools[k] != null)
            s = s + (k + 1) + ". " + this.schools[k].ToString();
    return s;
}

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

סעיף ג

תשובה:

פעולת עזר `hasTeacher(teachId)` ב-`School` מחפשת את המורה במערך המורים; `AllSchools` עוברת על כל בתי הספר ומדפיסה את שמו של כל בית ספר שבו `hasTeacher` מחזירה `true`.

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

פעולות האחזור שבהן משתמשים (ב-`Teacher` וב-`School`):

Java:

// פעולות אחזור שמשמשות את הסעיפים הבאים
// ---- במחלקה Teacher ----
public int getId() { return this.id; }
public boolean isAcademic() { return this.academic; }
// ---- במחלקה School ----
public String getName() { return this.name; }

C#:

// פעולות אחזור שמשמשות את הסעיפים הבאים
// ---- במחלקה Teacher ----
public int GetId() { return this.id; }
public bool IsAcademic() { return this.academic; }
// ---- במחלקה School ----
public string GetName() { return this.name; }

1. פעולת עזר במחלקה `School`: `hasTeacher(int teachId)` - טענת כניסה: מספר זיהוי של מורה; טענת יציאה: מחזירה `true` אם מורה עם מספר הזיהוי הזה מלמד בבית הספר, ואחרת `false`. היא עוברת על מערך המורים ומשווה את `getId()` של כל מורה ל-`teachId`.

2. במחלקה `AllSchools`: עוברים על 200 התאים, מדלגים על תאים ריקים, ועבור כל בית ספר שבו `hasTeacher(teachId)` מחזירה `true` מדפיסים את שמו (`getName()`).

Java:

// ---- במחלקה School: פעולת עזר ----
// מקבלת מספר זיהוי של מורה ומחזירה true אם המורה מלמד בבית הספר
public boolean hasTeacher(int teachId)
{
    for (int i = 0; i < this.teachers.length; i++)
        if (this.teachers[i].getId() == teachId)
            return true;
    return false;
}

// ---- במחלקה AllSchools ----
public void printSchoolsOf(int teachId)
{
    for (int k = 0; k < this.schools.length; k++)
        if (this.schools[k] != null && this.schools[k].hasTeacher(teachId))
            System.out.println(this.schools[k].getName());
}

C#:

// ---- במחלקה School: פעולת עזר ----
// מקבלת מספר זיהוי של מורה ומחזירה true אם המורה מלמד בבית הספר
public bool HasTeacher(int teachId)
{
    for (int i = 0; i < this.teachers.Length; i++)
        if (this.teachers[i].GetId() == teachId)
            return true;
    return false;
}

// ---- במחלקה AllSchools ----
public void PrintSchoolsOf(int teachId)
{
    for (int k = 0; k < this.schools.Length; k++)
        if (this.schools[k] != null && this.schools[k].HasTeacher(teachId))
            Console.WriteLine(this.schools[k].GetName());
}

תשובה: הפעולה `printSchoolsOf` במחלקה `AllSchools`, עם פעולת העזר `hasTeacher` במחלקה `School`.

סעיף ד

תשובה:

פעולת עזר `countAcademic()` ב-`School` סופרת מורים ש-`isAcademic()` שלהם `true`; `AllSchools` מוצאת את בית הספר עם הספירה הגדולה ביותר ומחזירה את שמו.

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

1. פעולת עזר במחלקה `School`: `countAcademic()` - טענת כניסה: אין; טענת יציאה: מחזירה את מספר המורים בבית הספר שיש להם השכלה אוניברסיטאית (`isAcademic()` מחזירה `true`).

2. במחלקה `AllSchools`: שומרים את הספירה הגדולה ביותר עד כה ב-`best` (מתחיל ב-−1-1, כדי שבית הספר הרשום הראשון ייבחר גם אם אין בו אקדמאים) ואת שם בית הספר שלה ב-`bestName`. עוברים על בתי הספר (מדלגים על תאים ריקים); אם הספירה של בית ספר גדולה מ-`best` - מעדכנים את שניהם.

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

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

Java:

// ---- במחלקה School: פעולת עזר ----
// מחזירה את מספר המורים בעלי השכלה אוניברסיטאית בבית הספר
public int countAcademic()
{
    int count = 0;
    for (int i = 0; i < this.teachers.length; i++)
        if (this.teachers[i].isAcademic())
            count++;
    return count;
}

// ---- במחלקה AllSchools ----
public String mostAcademic()
{
    String bestName = "";
    int best = -1;
    for (int k = 0; k < this.schools.length; k++)
    {
        if (this.schools[k] != null)
        {
            int c = this.schools[k].countAcademic();
            if (c > best)
            {
                best = c;
                bestName = this.schools[k].getName();
            }
        }
    }
    return bestName;
}

C#:

// ---- במחלקה School: פעולת עזר ----
// מחזירה את מספר המורים בעלי השכלה אוניברסיטאית בבית הספר
public int CountAcademic()
{
    int count = 0;
    for (int i = 0; i < this.teachers.Length; i++)
        if (this.teachers[i].IsAcademic())
            count++;
    return count;
}

// ---- במחלקה AllSchools ----
public string MostAcademic()
{
    string bestName = "";
    int best = -1;
    for (int k = 0; k < this.schools.Length; k++)
    {
        if (this.schools[k] != null)
        {
            int c = this.schools[k].CountAcademic();
            if (c > best)
            {
                best = c;
                bestName = this.schools[k].GetName();
            }
        }
    }
    return bestName;
}

לדוגמה, אם בבית הספר "Alon" המורים Dana (אקדמאית) ו-Avi, ובבית הספר "Brosh" המורות Dana ו-Rina (שתיהן אקדמאיות) - הספירות הן 1 ו-2, ומוחזר "Brosh".

תשובה: הפעולה `mostAcademic` במחלקה `AllSchools`, עם פעולת העזר `countAcademic` במחלקה `School`.

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

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

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