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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · קליטה עד זקיף: סכום ספרות וממוצע

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

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

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

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

פתרון

תשובה:

לולאת while עד קליטת 500 (הזקיף לא נספר); לכל מספר אי-זוגי מפרקים לספרות בעזרת %10 ו-/10 ומדפיסים את הסכום; בסוף מדפיסים סכום חלקי מונה (חילוק ממשי).

הרעיון: מספר הקלטים אינו ידוע מראש, ולכן משתמשים בלולאת while עם "זקיף": קולטים מספר לפני הלולאה, וכל עוד הוא שונה מ-500 מטפלים בו וקולטים את הבא. המספר 500 רק מסמן סוף, ולכן אינו נכנס לממוצע.

1. ממוצע: צריך מונה `count` וצובר `sum`. כל מספר שנקלט (חוץ מ-500) מגדיל את המונה ב-1 ומתווסף לצובר. אחרי הלולאה הממוצע הוא `sum / count`; ממירים ל-double לפני החילוק, אחרת החילוק בין שני שלמים יחתוך את השבר. אם הוקלד מיד 500, לא נקלט אף מספר ואין ממוצע – לכן בודקים `count > 0` כדי לא לחלק ב-0.

2. אי-זוגי: מספר אי-זוגי אם `num % 2 != 0`. כותבים "שונה מ-0" ולא "שווה ל-1", כי עבור מספר שלילי אי-זוגי השארית היא −1-1.

3. סכום ספרות: עובדים על עותק חיובי `n = |num|` (כדי שגם למספר שלילי נקבל ספרות חיוביות, ובלי לקלקל את num). בכל סיבוב `n % 10` היא הספרה הימנית – מוסיפים אותה לסכום, ו-`n / 10` מוחק אותה. כשהמספר מגיע ל-0 עברנו על כל הספרות. למשל עבור 375: 5+7+3=155+7+3=15.

סיבוכיות: כל מספר מטופל בזמן שפרופורציונלי למספר ספרותיו, כלומר בערך O(1)O(1) לכל קלט.

Java:

import java.util.Scanner;

public class Q1
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int count = 0;   // כמה מספרים נקלטו (בלי 500)
        int sum = 0;     // סכום המספרים שנקלטו

        int num = in.nextInt();
        while (num != 500)
        {
            count++;
            sum += num;
            if (num % 2 != 0)                 // מספר אי-זוגי
            {
                int n = Math.abs(num);
                int digitSum = 0;
                while (n > 0)
                {
                    digitSum += n % 10;       // הספרה הימנית
                    n /= 10;                  // מוחקים אותה
                }
                System.out.println("Sum of digits of " + num + ": " + digitSum);
            }
            num = in.nextInt();
        }

        if (count > 0)
            System.out.println("Average: " + (double) sum / count);
        else
            System.out.println("No numbers");
    }
}

C#:

using System;

class Q1
{
    static void Main(string[] args)
    {
        int count = 0;   // כמה מספרים נקלטו (בלי 500)
        int sum = 0;     // סכום המספרים שנקלטו

        int num = int.Parse(Console.ReadLine());
        while (num != 500)
        {
            count++;
            sum += num;
            if (num % 2 != 0)                 // מספר אי-זוגי
            {
                int n = Math.Abs(num);
                int digitSum = 0;
                while (n > 0)
                {
                    digitSum += n % 10;       // הספרה הימנית
                    n /= 10;                  // מוחקים אותה
                }
                Console.WriteLine("Sum of digits of " + num + ": " + digitSum);
            }
            num = int.Parse(Console.ReadLine());
        }

        if (count > 0)
            Console.WriteLine("Average: " + (double)sum / count);
        else
            Console.WriteLine("No numbers");
    }
}

דוגמה: עבור הקלט 13, −25-25, 8, 7, 500 יודפס: עבור 13 סכום ספרות 4, עבור −25-25 סכום 7, עבור 7 סכום 7 (8 זוגי ולא מודפס), והממוצע 13−25+8+74=34=0.75\frac{13-25+8+7}{4}=\frac{3}{4}=0.75.

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

שאלה 2 · ספירת מחרוזות תקינות לפי האות A

מחרוזת נקראת "מחרוזת תקינה" אם המחרוזת כוללת לפחות שתי אותיות 'A' אבל לא כוללת רצף "AA".

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

לדוגמה:

המחרוזת ABBA כוללת שתי אותיות 'A' ולא כוללת את הרצף "AA" ולכן מקיימת את התנאי למחרוזת תקינה

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

פתרון

תשובה:

לולאה של 23 קליטות; לכל מחרוזת סופרים אותיות 'A' ובודקים אם יש 'A' שלפניה 'A'; מחרוזת תקינה אם מספר ה-'A' לפחות 2 ואין רצף "AA"; מדפיסים את המונה.

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

1. `countA` – כמה פעמים מופיעה האות 'A'.

2. `hasAA` – האם יש רצף "AA". רצף כזה קיים בדיוק כאשר יש מקום i שבו התו הוא 'A' וגם התו שלפניו (i−1) הוא 'A'. התנאי `i > 0` מונע גישה לתו שלפני הראשון.

אחרי המעבר על המחרוזת, היא תקינה אם `countA >= 2` וגם `hasAA` שקר; אז מגדילים את המונה `valid`. אחרי 23 המחרוזות מדפיסים אותו.

Java:

import java.util.Scanner;

public class Q2
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int valid = 0;                         // מספר המחרוזות התקינות
        for (int k = 1; k <= 23; k++)
        {
            String s = in.next();
            int countA = 0;                    // כמה אותיות 'A'
            boolean hasAA = false;             // האם יש רצף "AA"
            for (int i = 0; i < s.length(); i++)
            {
                if (s.charAt(i) == 'A')
                {
                    countA++;
                    if (i > 0 && s.charAt(i - 1) == 'A')
                        hasAA = true;
                }
            }
            if (countA >= 2 && !hasAA)
                valid++;
        }
        System.out.println("Valid strings: " + valid);
    }
}

C#:

using System;

class Q2
{
    static void Main(string[] args)
    {
        int valid = 0;                         // מספר המחרוזות התקינות
        for (int k = 1; k <= 23; k++)
        {
            string s = Console.ReadLine();
            int countA = 0;                    // כמה אותיות 'A'
            bool hasAA = false;                // האם יש רצף "AA"
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == 'A')
                {
                    countA++;
                    if (i > 0 && s[i - 1] == 'A')
                        hasAA = true;
                }
            }
            if (countA >= 2 && !hasAA)
                valid++;
        }
        Console.WriteLine("Valid strings: " + valid);
    }
}

דוגמאות: ABBA – שתי אותיות A, אין "AA" – תקינה. ABA – תקינה. BAAB – יש "AA" – לא תקינה. ABC – רק A אחת – לא תקינה.

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

שאלה 3 · מערך חברים: כל ערך מופיע פעמיים

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

א.

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

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

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

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

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

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

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

סעיף א

תשובה:

לכל איבר סופרים בלולאה פנימית כמה פעמים הוא מופיע; אם יש איבר שמספר מופעיו שונה מ-2 מחזירים false, אחרת true. סיבוכיות O(n2)O(n^2).

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

1. עוברים על כל מקום i במערך.

2. בלולאה פנימית סופרים כמה תאים j מכילים את אותו ערך `arr[i]` (כולל התא i עצמו).

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

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

סיבוכיות: שתי לולאות מקוננות על n איברים – O(n2)O(n^2).

Java:

public static boolean isSetOfFriends(int[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {
        int count = 0;                     // כמה פעמים מופיע arr[i]
        for (int j = 0; j < arr.length; j++)
            if (arr[j] == arr[i])
                count++;
        if (count != 2)
            return false;                  // ערך שלא מופיע בדיוק פעמיים
    }
    return true;
}

C#:

public static bool IsSetOfFriends(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        int count = 0;                     // כמה פעמים מופיע arr[i]
        for (int j = 0; j < arr.Length; j++)
            if (arr[j] == arr[i])
                count++;
        if (count != 2)
            return false;                  // ערך שלא מופיע בדיוק פעמיים
    }
    return true;
}

דוגמאות: {3, 7, 3, 7} – כל ערך פעמיים – true. {3, 7, 3, 7, 7} – הערך 7 מופיע 3 פעמים – false. {5, 5, 5, 5} – false.

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

סעיף ב

תשובה:

לולאת do-while: מגרילים 10 מספרים בין 10 ל-99 לתאים 0-9, מעתיקים כל אחד גם לתא i+10, וחוזרים כל עוד isSetOfFriends(arr) מחזירה false (כלומר כל עוד הוגרל ערך יותר מפעם אחת).

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

1. יוצרים מערך בגודל 20.

2. מילוי: מספר אקראי דו-ספרתי חיובי הוא מספר בין 10 ל-99 כולל. לפי ההנחיות: `X + (int)(Math.random()*(Y - X + 1))` עם X=10X=10, Y=99Y=99 (ב-C#: `rand.Next(10, 99 + 1)`).

3. למה לא להגריל את כל 20 התאים בנפרד? במילוי עיוור של 20 תאים כמעט אף פעם לא יתקבל מצב שבו כל ערך מופיע בדיוק פעמיים (הסיכוי הוא בערך 1.1⋅10−111.1\cdot 10^{-11}), והלולאה כמעט לא תסתיים. לכן מגרילים 10 מספרים לתאים 0 עד 9, ומעתיקים כל אחד מהם גם לתא i+10i+10. כך כל ערך שהוגרל מופיע לפחות פעמיים.

4. תנאי ההמשך: המערך הוא "מערך חברים" אם 10 המספרים שהוגרלו שונים זה מזה. אם אותו מספר הוגרל פעמיים, הוא יופיע במערך 4 פעמים, `isSetOfFriends` תחזיר false, וממלאים מחדש. הסיכוי ש-10 ההגרלות שונות הוא 90⋅89⋯819010≈0.6\frac{90\cdot 89\cdots 81}{90^{10}}\approx 0.6, ולכן בממוצע מספיקים פחות משני סיבובים.

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

Java:

int[] arr = new int[20];
do
{
    for (int i = 0; i < 10; i++)
    {
        arr[i] = 10 + (int)(Math.random() * (99 - 10 + 1));   // 10..99
        arr[i + 10] = arr[i];                                  // אותו ערך פעם שנייה
    }
} while (!isSetOfFriends(arr));

C#:

Random rand = new Random();
int[] arr = new int[20];
do
{
    for (int i = 0; i < 10; i++)
    {
        arr[i] = rand.Next(10, 99 + 1);                        // 10..99
        arr[i + 10] = arr[i];                                  // אותו ערך פעם שנייה
    }
} while (!IsSetOfFriends(arr));

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

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

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

למחלקה קופסה (תיבה) – Box יש ארבע תכונות:

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

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

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

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

במחלקה Box הוגדרה פעולה בונה (בנאי, constructor) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות get/set לכל אחת מהתכונות.

א.

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

public Box(String color)
public Box(string color)
(6 נקודות)
ב.

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

public static boolean isBlackWhite(Box[] arr)
public static bool IsBlackWhite(Box[] arr)

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

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

סעיף א

תשובה:

הבנאי מציב את הצבע שהתקבל (בזימון new Box("black")) ומגריל כל ממד בנפרד בין 20 ל-100: 20 + (int)(Math.random()*81).

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

1. צבע: כותרת הפעולה מקבלת פרמטר color, ולכן מציבים אותו בתכונה. הקופסה השחורה נוצרת בזימון `new Box("black")`. (אם רוצים שהבנאי ייצור תמיד קופסה שחורה בלי תלות בפרמטר, אפשר לכתוב במקום זאת `this.color = "black";`.)

2. ממדים: כל ממד מוגרל בנפרד (שלוש הגרלות), כי הממדים לא חייבים להיות שווים. מספר אקראי בין X=20X=20 ל-Y=100Y=100 כולל: `20 + (int)(Math.random() * (100 - 20 + 1))` – הביטוי `Math.random()*81` נותן מספר ממשי בתחום [0,81)[0,81), החלק השלם שלו הוא 0 עד 80, ואחרי הוספת 20 מקבלים 20 עד 100.

3. ב-C# יוצרים עצם Random אחד סטטי למחלקה (כדי שבנאים שנקראים ברצף לא יקבלו אותו זרע) ומשתמשים ב-`rand.Next(20, 100 + 1)`.

Java:

public Box(String color)
{
    this.color = color;                                        // "black"
    this.length = 20 + (int)(Math.random() * (100 - 20 + 1));  // 20..100
    this.width  = 20 + (int)(Math.random() * (100 - 20 + 1));
    this.height = 20 + (int)(Math.random() * (100 - 20 + 1));
}

C#:

private static Random rand = new Random();

public Box(string color)
{
    this.color = color;                       // "black"
    this.length = rand.Next(20, 100 + 1);     // 20..100
    this.width  = rand.Next(20, 100 + 1);
    this.height = rand.Next(20, 100 + 1);
}

תשובה: הבנאי שלמעלה; זימון: `Box b = new Box("black");`.

סעיף ב

תשובה:

שני דגלים hasBlack, hasWhite; קופסה בצבע אחר – מחזירים false מיד; בסוף מחזירים hasBlack && hasWhite.

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

1. מחזיקים שני דגלים בוליאניים, `hasBlack` ו-`hasWhite`, שמאותחלים ל-false.

2. עוברים על כל הקופסאות ומקבלים את הצבע בעזרת `getColor()` (התכונה פרטית, ולכן פונים דרך פעולת get מחוץ למחלקה).

3. צבע "black" – מדליקים את hasBlack; צבע "white" – מדליקים את hasWhite; כל צבע אחר – התנאי השלישי הופר, ומחזירים false מיד.

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

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

Java:

public static boolean isBlackWhite(Box[] arr)
{
    boolean hasBlack = false;
    boolean hasWhite = false;
    for (int i = 0; i < arr.length; i++)
    {
        String c = arr[i].getColor();
        if (c.equals("black"))
            hasBlack = true;
        else if (c.equals("white"))
            hasWhite = true;
        else
            return false;              // קופסה בצבע אחר
    }
    return hasBlack && hasWhite;
}

C#:

public static bool IsBlackWhite(Box[] arr)
{
    bool hasBlack = false;
    bool hasWhite = false;
    for (int i = 0; i < arr.Length; i++)
    {
        string c = arr[i].GetColor();
        if (c == "black")
            hasBlack = true;
        else if (c == "white")
            hasWhite = true;
        else
            return false;              // קופסה בצבע אחר
    }
    return hasBlack && hasWhite;
}

דוגמאות: {לבן, שחור} – true; {שחור, שחור} – false (אין לבנה); {לבן, שחור, אדום} – false.

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

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

שאלה 5 · מעקב: מינימום ומקסימום בעזרת ממוצע והפרש

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

Java:

  public static int sod (int[] arr)
  {
    int m = arr[0];
    double k1, k2;
    for (int i = 1; i < arr.length; i++)
    {
      k1 = (m + arr[i])/2.0;
      k2 = Math.abs((m - arr[i])/2.0);
      m = (int)(k1 - k2);
    }
    return m;
  }// end of sod


  public static int secret (int[] arr)
  {
    int m = arr[0];
    double k1, k2;
    for (int i = 1; i < arr.length; i++)
    {
      k1 = (m + arr[i])/2.0;
      k2 = Math.abs((m - arr[i])/2.0);
      m = (int)(k1 + k2);
    }
    return m;
  } // end of secret

C#:

  public static int Sod (int[] arr)
  {
    int m = arr[0];
    double k1, k2;
    for (int i = 1; i < arr.Length; i++)
    {
      k1 = (m + arr[i])/2.0;
      k2 = Math.Abs((m - arr[i])/2.0);
      m = (int)(k1 - k2);
    }
    return m;
  }// end of sod


  public static int Secret (int[] arr)
  {
    int m = arr[0];
    double k1, k2;
    for (int i = 1; i < arr.Length; i++)
    {
      k1 = (m + arr[i])/2.0;
      k2 = Math.Abs((m - arr[i])/2.0);
      m = (int)(k1 + k2);
    }
    return m;
  } // end of secret

נתון מערך מספרים שלמים `int[] arr = {6, 2, -8, 12, -4}`.

א.

עקבו בעזרת טבלת המעקב אחרי זימון הפעולה sod(arr) וכתבו מה תהיה תוצאת הזימון.

(5 נקודות)
ב.

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

(2 נקודות)
ג.

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

`sod(arr) > secret(brr)`

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

סעיף א

תשובה:

sod(arr) מחזירה −8-8.

הרעיון: בכל סיבוב מחשבים k1=m+arr[i]2k1=\frac{m+arr[i]}{2} (הממוצע של שני המספרים) ו-k2=∣m−arr[i]2∣k2=\left|\frac{m-arr[i]}{2}\right| (חצי המרחק ביניהם), ואז m=k1−k2m=k1-k2.

1. מתחילים עם m=arr[0]=6m=arr[0]=6.

2. בכל סיבוב i מ-1 עד 4 מציבים את m הנוכחי ואת arr[i]:

סיבוב: iarr[i]k1 = (m+arr[i])/2.0k2 = abs((m−arr[i])/2.0)m = (int)(k1−k2)
לפני הלולאה–––6
12(6+2)/2.0 = 4.0abs(4/2.0) = 2.02
2−8(2−8)/2.0 = −3.0abs(10/2.0) = 5.0−8
312(−8+12)/2.0 = 2.0abs(−20/2.0) = 10.0−8
4−4(−8−4)/2.0 = −6.0abs(−4/2.0) = 2.0−8

3. אחרי הסיבוב האחרון i=5i=5 והלולאה מסתיימת; מוחזר m=−8m=-8.

תשובה: תוצאת הזימון sod(arr) היא −8-8.

סעיף ב

תשובה:

sod מחזירה את הערך הקטן ביותר במערך (המינימום).

הנימוק: לשני מספרים a, b מתקיים:

a+b2−∣a−b2∣=min⁡(a,b),a+b2+∣a−b2∣=max⁡(a,b)\frac{a+b}{2}-\left|\frac{a-b}{2}\right|=\min(a,b),\qquad \frac{a+b}{2}+\left|\frac{a-b}{2}\right|=\max(a,b)

כי הממוצע נמצא בדיוק באמצע בין שני המספרים, וחצי המרחק ביניהם מוביל ממנו אל הקטן (בחיסור) או אל הגדול (בחיבור). למשל: a=2, b=−8a=2,\ b=-8: −3−5=−8-3-5=-8.

לכן בכל סיבוב m=min⁡(m,arr[i])m=\min(m, arr[i]): m הוא המינימום של התאים שנבדקו עד כה, ובסוף – של כל המערך. ההמרה `(int)` אינה מאבדת דבר, כי התוצאה k1−k2k1-k2 היא תמיד אחד משני המספרים השלמים.

(באותו אופן secret מחשבת m=max⁡(m,arr[i])m=\max(m, arr[i]) ומחזירה את המקסימום של המערך.)

תשובה: sod מחזירה את הערך המינימלי במערך.

סעיף ג

תשובה:

למשל brr = {-9, -10, -20, -15, -30, -11}: secret(brr) = -9 < -8 = sod(arr).

נתון: sod(arr)=−8sod(arr)=-8 (סעיף א). מבוקש: מערך brr של 6 תאים עם secret(brr)<−8secret(brr)<-8.

1. לפי סעיף ב, secret מחזירה את המקסימום של המערך. לכן התנאי −8>secret(brr)-8>secret(brr) אומר שהאיבר הגדול ביותר ב-brr קטן מ-−8-8, כלומר כל האיברים ב-brr קטנים מ-−8-8.

2. נבחר: `int[] brr = {-9, -10, -20, -15, -30, -11};`

3. בדיקה: המקסימום של brr הוא −9-9, ולכן secret(brr)=−9secret(brr)=-9, ומתקיים sod(arr)=−8>−9=secret(brr)sod(arr)=-8>-9=secret(brr).

תשובה: למשל brr = {-9, -10, -20, -15, -30, -11} (כל איבר קטן מ-−8-8).

שאלה 6 · מעקב: צמצום רצפים של אותיות גדולות

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

Java:

public static String what(String s)
  {
    String str="";
    int i;
    for(i=0; i < s.length()-1; i++)
    {
      if(s.charAt(i)<'A' || s.charAt(i)>'Z')
      {
        str+= s.charAt(i);
      }
      else
      {
        if(s.charAt(i) != s.charAt(i+1))
        {
          str+= s.charAt(i);
        }
      }
    }
    str+= s.charAt(i);
    return str;
  }

C#:

public static string What(string s)
  {
    string str="";
    int i;
    for(i=0; i < s.Length-1; i++)
    {
      if(s[i]<'A' || s[i]>'Z')
      {
        str+= s[i];
      }
      else
      {
        if(s[i] != s[i+1])
        {
          str+= s[i];
        }
      }
    }
    str+= s[i];
    return str;
  }
א.

עקבו בעזרת טבלת המעקב אחרי זימון הפעולה what("%%ABBCCC??DD") ורשמו מה תהיה תוצאת הזימון.

(5 נקודות)
ב.

האם קיימת מחרוזת לא ריקה str כך שזימון הפעולה what(str) יחזיר מחרוזת זהה ל- str?

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

(2 נקודות)
ג.

האם קיימות שתי מחרוזות שונות str1 ו- str2 כך תוצאות הזימונים what(str1) ו- what(str2) יהיו זהות. אם כן – תנו דוגמה לזוג מחרוזות str1 ו- str2, אם לא – הסבירו למה אין זוג כזה.

(2 נקודות)
ד.

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

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

סעיף א

תשובה:

"%%ABC??D"

הרעיון: הלולאה עוברת על המקומות 0 עד length−2length-2 (אורך המחרוזת 12, לכן i מ-0 עד 10). בכל מקום:

•אם התו אינו אות גדולה ('A' עד 'Z') – הוא נוסף ל-str;

•אם הוא אות גדולה – הוא נוסף רק אם התו שאחריו שונה ממנו.

אחרי הלולאה i=11i=11, והתו האחרון s.charAt(11) נוסף תמיד.

is.charAt(i)s.charAt(i+1)אות גדולה?פעולהstr
0%%לאמוסיפים%
1%Aלאמוסיפים%%
2ABכןשונה מהבא – מוסיפים%%A
3BBכןשווה לבא – מדלגים%%A
4BCכןשונה מהבא – מוסיפים%%AB
5CCכןשווה לבא – מדלגים%%AB
6CCכןשווה לבא – מדלגים%%AB
7C?כןשונה מהבא – מוסיפים%%ABC
8??לאמוסיפים%%ABC?
9?Dלאמוסיפים%%ABC??
10DDכןשווה לבא – מדלגים%%ABC??
11 (אחרי הלולאה)D––מוסיפים את התו האחרון%%ABC??D

תשובה: תוצאת הזימון היא המחרוזת "%%ABC??D".

סעיף ב

תשובה:

כן. למשל "ABC" (אין שתי אותיות גדולות זהות צמודות) – what("ABC") מחזירה "ABC".

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

דוגמה: str = "ABC". בסיבוב 0: 'A' שונה מ-'B' – נוסף; בסיבוב 1: 'B' שונה מ-'C' – נוסף; אחרי הלולאה נוסף 'C'. התוצאה "ABC".

(גם "aa" או "%%" מתאימות – אלה אינן אותיות גדולות, ולכן הן לא מושמטות.)

תשובה: כן, למשל str = "ABC".

סעיף ג

תשובה:

כן. למשל str1 = "AAB", str2 = "AB": שתיהן מחזירות "AB".

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

דוגמה: str1 = "AAB".

•i=0: 'A' שווה ל-'A' שאחריו – מדלגים.

•i=1: 'A' שונה מ-'B' – str = "A".

•אחרי הלולאה מוסיפים 'B' – התוצאה "AB".

str2 = "AB": i=0: 'A' שונה מ-'B' – str = "A"; אחרי הלולאה – "AB".

שתי המחרוזות שונות, והתוצאות זהות: "AB".

תשובה: כן, למשל str1 = "AAB" ו-str2 = "AB".

סעיף ד

תשובה:

מחזירה עותק של המחרוזת שבו כל רצף של אות גדולה זהה שחוזרת ברצף מצומצם לאות אחת; שאר התווים נשארים כמו שהם.

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

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

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

שאלה 7 · מחלקות מוצר ומלאי: השוואה, מינימום ועדכון

א.

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

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

•סוג מוצר – category, מטיפוס מחרוזת – String (טלוויזיה, מחשב, מכונת כביסה וכד')

•מספר יחידות – count, מטיפוס מספר שלם – int

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

במחלקה Product הוגדרה פעולה בונה (בנאי, constructor) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות get/set לכל אחת מהתכונות.

(1)

כתבו פעולה פנימית במחלקה Product המקבלת הפניה למוצר other. הפעולה מחזירה true אם המוצר הנוכחי (עצם המפעיל את הפעולה) זול יותר ממוצר other. כותרת הפעולה:

public boolean isCheaper(Product other)
public bool IsCheaper(Product other)
(2)

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

public boolean isSame(Product other)
public bool IsSame(Product other)
(6 נקודות)
ב.

המחלקה Stock מייצגת את המלאי בחנות.

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

•מערך המוצרים – `Product [] stock`

•מספר המוצרים שיש בחנות – `int numOfProducts`

אפשר להניח שאין יותר מ- 100 מוצרים שונים.

(1)

כתבו בנאי ברירת-מחדל (default constructor) של המחלקה Stock היוצר אובייקט שבו מערך בגודל המקסימלי של 100 מוצרי חשמל. בהתחלה המערך ריק ומספר המוצרים שבו שווה ל- 0.

(2)

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

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

public Product mostCheaper(String category)
public Product MostCheaper(string category)

אם במלאי אין מוצרים של אותו סוג category, הפעולה תחזיר null.

(3)

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

public void updateStock(String name, String category, int count,
                        double price)
public void UpdateStock(String name, string category, int count,
                        double price)

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

המחיר במלאי יהיה הזול בין מחיר הקיים והפרמטר price.

•אם מוצר לא קיים במלאי הפעולה תוסיף מוצר חדש לפי פרמטרים של הפעולה.

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

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

סעיף א

(1)
תשובה:

return this.price < other.getPrice();

הרעיון: "זול יותר" פירושו שהמחיר של העצם הנוכחי קטן ממש מהמחיר של other. הפעולה פנימית, ולכן ניגשים ישירות לתכונה `this.price`; את המחיר של other מקבלים בעזרת `getPrice()` (אפשר גם `other.price`, כי זו אותה מחלקה). ביטוי ההשוואה עצמו הוא ערך בוליאני, ולכן מחזירים אותו ישירות.

הקוד של שתי הפעולות (1 ו-2) מופיע יחד בסוף סעיף 2.

תשובה: `return this.price < other.getPrice();`

(2)
תשובה:

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

הרעיון: "זהה פרט למחיר ולמספר היחידות" – משווים רק את שתי התכונות האחרות: שם המוצר name וסוג המוצר category. שתיהן מחרוזות, ולכן ב-Java משווים בעזרת `equals` (האופרטור `==` היה משווה הפניות ולא תוכן). המוצרים זהים רק אם שתי ההשוואות מתקיימות – לכן `&&`.

Java:

// פעולות בתוך המחלקה Product

public boolean isCheaper(Product other)
{
    return this.price < other.getPrice();
}

public boolean isSame(Product other)
{
    return this.name.equals(other.getName())
        && this.category.equals(other.getCategory());
}

C#:

// פעולות בתוך המחלקה Product

public bool IsCheaper(Product other)
{
    return this.price < other.GetPrice();
}

public bool IsSame(Product other)
{
    return this.name == other.GetName()
        && this.category == other.GetCategory();
}

תשובה: הפעולות isCheaper ו-isSame שלמעלה.

סעיף ב

(1)
תשובה:

stock = new Product[100]; numOfProducts = 0;

הרעיון: בנאי ברירת מחדל אינו מקבל פרמטרים. הוא יוצר מערך הפניות בגודל 100 (כל התאים מאותחלים אוטומטית ל-null – המערך "ריק"), ומאפס את מונה המוצרים. המונה numOfProducts הוא גם המקום הפנוי הבא במערך: המוצרים תמיד שמורים בתאים 0 עד numOfProducts−1.

הקוד המלא של המחלקה מופיע בסוף סעיף 3.

תשובה: `stock = new Product[100]; numOfProducts = 0;`

(2)
תשובה:

עוברים על התאים 0..numOfProducts-1; בין המוצרים מהסוג category שומרים את הזול ביותר (מתחילים מ-null); מחזירים אותו (null אם לא נמצא).

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

1. משתנה `cheapest` מאותחל ל-null – עדיין לא נמצא מוצר מהסוג.

2. עוברים רק על התאים התפוסים (עד numOfProducts, ולא עד 100 – שאר התאים null).

3. מוצר שהסוג שלו שווה ל-category: אם זה הראשון מהסוג (`cheapest == null`) או שהוא זול מהמינימום הנוכחי (`isCheaper` מסעיף א1) – הוא הופך ל-cheapest.

4. בסוף מחזירים את cheapest. אם לא היה אף מוצר מהסוג, הוא נשאר null – בדיוק כנדרש.

סיבוכיות: O(n)O(n), כאשר n מספר המוצרים.

תשובה: הפעולה mostCheaper בקוד שבסוף סעיף 3.

(3)
תשובה:

יוצרים Product מהפרמטרים ומחפשים במלאי מוצר זהה (isSame). נמצא – מוסיפים count למספר היחידות ומעדכנים מחיר אם החדש זול יותר; לא נמצא – מכניסים לתא numOfProducts ומגדילים את המונה.

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

1. יוצרים עצם `p` מהפרמטרים – כך אפשר להשתמש בפעולות isSame ו-isCheaper שכתבנו בסעיף א.

2. עוברים על המוצרים במלאי. מוצר "קיים" אם הוא זהה ל-p פרט למחיר ולמספר היחידות, כלומר `stock[i].isSame(p)`.

3. המוצר קיים: יחידות חדשות הגיעו למלאי, ולכן מספר היחידות גדל: `count` החדש מתווסף למספר הקיים. אם המחיר החדש זול מהמחיר במלאי (`p.isCheaper(stock[i])`), מעדכנים את המחיר – כך המחיר במלאי הוא הזול מבין השניים. אחרי העדכון יוצאים מהפעולה (return), כדי לא להוסיף את המוצר שוב.

4. המוצר לא נמצא: מכניסים את p לתא הפנוי הראשון `stock[numOfProducts]` ומגדילים את המונה. לפי הנתון יש מקום במערך.

Java:

public class Stock
{
    private Product[] stock;
    private int numOfProducts;

    // 1. בנאי ברירת מחדל
    public Stock()
    {
        this.stock = new Product[100];
        this.numOfProducts = 0;
    }

    // 2. המוצר הזול ביותר מסוג נתון
    public Product mostCheaper(String category)
    {
        Product cheapest = null;
        for (int i = 0; i < numOfProducts; i++)
        {
            if (stock[i].getCategory().equals(category))
            {
                if (cheapest == null || stock[i].isCheaper(cheapest))
                    cheapest = stock[i];
            }
        }
        return cheapest;
    }

    // 3. עדכון המלאי
    public void updateStock(String name, String category, int count,
                            double price)
    {
        Product p = new Product(name, category, count, price);
        for (int i = 0; i < numOfProducts; i++)
        {
            if (stock[i].isSame(p))                       // המוצר כבר קיים
            {
                stock[i].setCount(stock[i].getCount() + count);
                if (p.isCheaper(stock[i]))
                    stock[i].setPrice(price);
                return;
            }
        }
        stock[numOfProducts] = p;                         // מוצר חדש
        numOfProducts++;
    }
}

C#:

public class Stock
{
    private Product[] stock;
    private int numOfProducts;

    // 1. בנאי ברירת מחדל
    public Stock()
    {
        this.stock = new Product[100];
        this.numOfProducts = 0;
    }

    // 2. המוצר הזול ביותר מסוג נתון
    public Product MostCheaper(string category)
    {
        Product cheapest = null;
        for (int i = 0; i < numOfProducts; i++)
        {
            if (stock[i].GetCategory() == category)
            {
                if (cheapest == null || stock[i].IsCheaper(cheapest))
                    cheapest = stock[i];
            }
        }
        return cheapest;
    }

    // 3. עדכון המלאי
    public void UpdateStock(string name, string category, int count,
                            double price)
    {
        Product p = new Product(name, category, count, price);
        for (int i = 0; i < numOfProducts; i++)
        {
            if (stock[i].IsSame(p))                       // המוצר כבר קיים
            {
                stock[i].SetCount(stock[i].GetCount() + count);
                if (p.IsCheaper(stock[i]))
                    stock[i].SetPrice(price);
                return;
            }
        }
        stock[numOfProducts] = p;                         // מוצר חדש
        numOfProducts++;
    }
}

דוגמה: מוסיפים ("LG55", "TV", 3, 3000), ואז שוב ("LG55", "TV", 4, 2000). בפעם השנייה המוצר נמצא: מספר היחידות 3+4=73+4=7 והמחיר יורד ל-2000.

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

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

א.

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

Java:

public static void what(int[] arr){
    int i = 0;
    int j = arr.length - 1;
    int temp;
    while (i < j)
    {
        if (arr[i] <= 0)
            i++;
        else if (arr[j] >0)
            j--;
        else
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

C#:

public static void What(int[] arr){
    int i = 0;
    int j = arr.Length - 1;
    int temp;
    while (i < j)
    {
        if (arr[i] <= 0)
            i++;
        else if (arr[j] >0)
            j--;
        else
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
(1)

נתון מערך `int [] arr={123, 45, -15, 15, -8}`.

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

(2)

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

(3)

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

(6 נקודות)
ב.

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

Java:

public static void why(int[] arr){
    int[] newArr = new int[arr.length];
    int ind = 0;
    for (int i = 0; i < arr.length; i++)
        if (arr[i] <= 0)
            newArr [ind++] = arr[i];
    for (int i = 0; i < arr.length; i++)
        if (arr[i] > 0)
            newArr [ind++] = arr[i];
    for (int i = 0; i < arr.length; i++)
         arr[i] = newArr [i];
}

C#:

public static void Why(int[] arr){
    int[] newArr = new int[arr.Length];
    int ind = 0;
    for (int i = 0; i < arr.Length; i++)
        if (arr[i] <= 0)
            newArr [ind++] = arr[i];
    for (int i = 0; i < arr.Length; i++)
        if (arr[i] > 0)
            newArr [ind++] = arr[i];
    for (int i = 0; i < arr.Length; i++)
         arr[i] = newArr [i];
}
(1)

נתון מערך `int [] arr={-12, 55, 0, -46, 67}`.

מה יהיה תוכן המערך אחרי זימון הפעולה why(arr)?

(2)

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

(3)

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

(6 נקודות)
ג.

מה הן סיבוכיות זמן הריצה של הפעולות what ו- why?

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

סעיף א

(1)
תשובה:

arr = {-8, -15, 45, 15, 123}

הרעיון: i מתקדם משמאל כל עוד arr[i] אינו חיובי (≤ 0), ו-j מתקדם מימין כל עוד arr[j] חיובי. כאשר i נעצר על מספר חיובי ו-j נעצר על מספר שאינו חיובי – מחליפים ביניהם. הלולאה רצה כל עוד i<ji<j.

מתחילים עם i=0i=0, j=4j=4:

סיבובijarr[i]arr[j]פעולהarr אחרי הסיבוב
104123−8123 > 0 ו-−8 ≤ 0 – החלפה{−8, 45, −15, 15, 123}
204−8123−8 ≤ 0 – i++ללא שינוי, i = 1
31445123123 > 0 – j−−ללא שינוי, j = 3
413451515 > 0 – j−−ללא שינוי, j = 2
51245−1545 > 0 ו-−15 ≤ 0 – החלפה{−8, −15, 45, 15, 123}
612−1545−15 ≤ 0 – i++ללא שינוי, i = 2

אחרי סיבוב 6: i=2i=2, j=2j=2, התנאי i<ji<j נכשל והלולאה מסתיימת.

תשובה: אחרי הזימון arr = {-8, -15, 45, 15, 123}.

(2)
תשובה:

למשל brr = {-3, 0, -1, 7, 2} (קודם כל האי-חיוביים ואחריהם כל החיוביים).

הנימוק: החלפה מתבצעת רק כאשר יש מספר חיובי שנמצא משמאל למספר שאינו חיובי. אם כל המספרים שאינם חיוביים (≤ 0) כבר נמצאים לפני כל החיוביים, i יתקדם על החלק השמאלי ו-j על החלק הימני עד שייפגשו, בלי אף החלפה.

דוגמה: `int[] brr = {-3, 0, -1, 7, 2};`

i עובר על −3, 0, −1 (כולם ≤ 0) עד i=3i=3; אז arr[3] = 7 > 0, ו-j יורד מ-4 ל-3 כי arr[4] = 2 > 0; עכשיו i=j=3i=j=3 והלולאה נגמרת. המערך לא השתנה.

(גם מערך שכולו חיובי או כולו אי-חיובי מתאים.)

תשובה: למשל brr = {-3, 0, -1, 7, 2}.

(3)
תשובה:

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

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

הסדר הפנימי לא נשמר: בסעיף 1 התקבל {−8, −15, ...} אף שבמערך המקורי −15 הופיע לפני −8.

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

סעיף ב

(1)
תשובה:

arr = {-12, 0, -46, 55, 67}

הרעיון: הפעולה בונה מערך חדש בשלושה מעברים.

1. לולאה ראשונה – מעתיקה לפי הסדר את האיברים ≤ 0: −12, 0, −46 → newArr = {−12, 0, −46, _, _}, ind = 3.

2. לולאה שנייה – מעתיקה לפי הסדר את האיברים החיוביים: 55, 67 → newArr = {−12, 0, −46, 55, 67}, ind = 5.

3. לולאה שלישית – מעתיקה את newArr חזרה ל-arr.

iarr[i]לולאה 1 (≤ 0)לולאה 2 (> 0)
0−12newArr[0] = −12–
155–newArr[3] = 55
20newArr[1] = 0–
3−46newArr[2] = −46–
467–newArr[4] = 67

תשובה: אחרי הזימון arr = {-12, 0, -46, 55, 67}.

(2)
תשובה:

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

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

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

(3)
תשובה:

כן. למשל crr = {-3, 0, -1, 7, 2}: שתי הפעולות משאירות אותו ללא שינוי.

הנימוק: שתי הפעולות מחלקות את המערך לאי-חיוביים ואחריהם חיוביים; הן נבדלות רק בסדר בתוך כל קבוצה. אם המערך כבר מחולק, what לא מבצעת אף החלפה (סעיף א2), ו-why מעתיקה את האיברים באותו סדר שבו הם נמצאים – כך ששתיהן משאירות את המערך כמו שהוא.

דוגמה: `int[] crr = {-3, 0, -1, 7, 2};`

•what(crr) – לפי סעיף א2 המערך לא משתנה: {−3, 0, −1, 7, 2}.

•why(crr) – לולאה 1 מעתיקה −3, 0, −1; לולאה 2 מעתיקה 7, 2; התוצאה {−3, 0, −1, 7, 2}.

תשובה: כן, למשל crr = {-3, 0, -1, 7, 2} – שתי הפעולות מחזירות {-3, 0, -1, 7, 2}.

סעיף ג

תשובה:

שתיהן O(n)O(n); what במקום (זיכרון נוסף O(1)O(1)), why עם מערך עזר (זיכרון נוסף O(n)O(n)).

what: בכל סיבוב של הלולאה מתבצע אחד משלושה דברים: i גדל, j קטן, או החלפה. אחרי החלפה, arr[i] הוא אי-חיובי, ולכן בסיבוב הבא i בהכרח גדל. המרחק j−ij-i מתחיל ב-n−1n-1 וקטן ב-1 בכל סיבוב שאינו החלפה, ולכל היותר כל סיבוב שני הוא החלפה – כלומר לכל היותר כ-2n2n סיבובים. סיבוכיות זמן: O(n)O(n).

why: שלוש לולאות נפרדות (לא מקוננות), כל אחת בדיוק n סיבובים – 3n3n פעולות. סיבוכיות זמן: O(n)O(n).

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

תשובה: סיבוכיות הזמן של what היא O(n)O(n) ושל why היא O(n)O(n).

שאלה 9 · מחרוזות הניתנות לחלוקה לחלקים זהים

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

מחרוזת ניתנת לחלוקה היא מחרוזת המורכבת מ- K חלקים זהים.

לדוגמה:

אפשר לחלק את המחרוזת ABCABC לשתי מחרוזות זהות (ABC,ABC).

אפשר לחלק את המחרוזת ABABABAB לשתי מחרוזות זהות (ABAB, ABAB) וגם לארבע מחרוזות זהות (AB,AB,AB,AB).

אפשר לחלק את המחרוזת AAAAA לחמש מחרוזות זהות (A,A,A,A,A).

את המחרוזת ABCA אי אפשר לחלק.

א.

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

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

public static boolean isDivisible(String s, int k)
public static bool IsDivisible(string s, int k)
(5 נקודות)
ב.

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

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

public static int maxDivisor (String s)
public static int MaxDivisor (string s)
(5 נקודות)
ג.

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

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

סעיף א

תשובה:

אם האורך n אינו מתחלק ב-k – false; אחרת part = n/k, ובודקים שכל תו שווה לתו שנמצא part מקומות לפניו (s.charAt(i) == s.charAt(i - part)).

הרעיון:

1. כדי לחלק מחרוזת באורך n ל-k חלקים שווים, האורך חייב להתחלק ב-k. אחרת מחזירים false מיד.

2. אורך כל חלק הוא part=nkpart=\frac{n}{k}.

3. כל החלקים זהים לחלק הראשון אם ורק אם כל תו שווה לתו שנמצא part מקומות לפניו: s[i]=s[i−part]s[i]=s[i-part] לכל i≥parti\ge part. (כך החלק השני שווה לראשון, השלישי לשני, וכן הלאה.) מספיק תו אחד שונה כדי להחזיר false.

דוגמה: s = "ABABABAB", k = 4: n=8n=8, part=2part=2, ובודקים s[2]=s[0]='A', s[3]=s[1]='B', ... – כולם שווים, true. עבור k = 3: 8%3≠08\%3\ne 0 – false.

עבור k = 1 הלולאה לא רצה ומוחזר true – כל מחרוזת היא "חלק אחד" של עצמה. סיבוכיות: O(n)O(n).

הקוד של שלושת הסעיפים מופיע יחד בסוף סעיף ג.

תשובה: הפעולה isDivisible בקוד שבסוף סעיף ג.

סעיף ב

תשובה:

בודקים את k מ-s.length() יורד עד 2 בעזרת isDivisible ומחזירים את הראשון שמצליח; אם אף אחד – מחזירים -1.

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

עוצרים ב-2 ולא ב-1: חלוקה ל"חלק אחד" אפשרית תמיד, ולפי ההגדרה ABCA "אי אפשר לחלק" – כלומר חלוקה פירושה לפחות שני חלקים. אם אף k בין 2 ל-n אינו מתאים, מחזירים −1-1.

דוגמאות: "ABABABAB" – k = 8..5 נכשלים, k = 4 מצליח – מוחזר 4. "AAAAA" – k = 5 מצליח מיד – 5. "ABCABC" – 2. "ABCA" – אף k – −1-1.

סיבוכיות: עד n בדיקות של O(n)O(n) כל אחת – O(n2)O(n^2).

תשובה: הפעולה maxDivisor בקוד שבסוף סעיף ג.

סעיף ג

תשובה:

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

הרעיון: מחרוזת אינה ניתנת לחלוקה בדיוק כאשר `maxDivisor` מסעיף ב מחזירה −1-1. גודל מערך ב-Java/C# נקבע ביצירתו, ולכן עובדים בשני מעברים:

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

2. יוצרים מערך חדש בדיוק בגודל הזה.

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

Java:

// סעיף א
public static boolean isDivisible(String s, int k)
{
    int n = s.length();
    if (n % k != 0)
        return false;                       // האורך לא מתחלק ב-k
    int part = n / k;                       // אורך כל חלק
    for (int i = part; i < n; i++)
        if (s.charAt(i) != s.charAt(i - part))
            return false;
    return true;
}

// סעיף ב
public static int maxDivisor(String s)
{
    for (int k = s.length(); k >= 2; k--)
        if (isDivisible(s, k))
            return k;
    return -1;
}

// סעיף ג
public static String[] notDivisible(String[] arr)
{
    int count = 0;                          // כמה מחרוזות אינן ניתנות לחלוקה
    for (int i = 0; i < arr.length; i++)
        if (maxDivisor(arr[i]) == -1)
            count++;
    String[] res = new String[count];
    int ind = 0;
    for (int i = 0; i < arr.length; i++)
        if (maxDivisor(arr[i]) == -1)
        {
            res[ind] = arr[i];
            ind++;
        }
    return res;
}

C#:

// סעיף א
public static bool IsDivisible(string s, int k)
{
    int n = s.Length;
    if (n % k != 0)
        return false;                       // האורך לא מתחלק ב-k
    int part = n / k;                       // אורך כל חלק
    for (int i = part; i < n; i++)
        if (s[i] != s[i - part])
            return false;
    return true;
}

// סעיף ב
public static int MaxDivisor(string s)
{
    for (int k = s.Length; k >= 2; k--)
        if (IsDivisible(s, k))
            return k;
    return -1;
}

// סעיף ג
public static string[] NotDivisible(string[] arr)
{
    int count = 0;                          // כמה מחרוזות אינן ניתנות לחלוקה
    for (int i = 0; i < arr.Length; i++)
        if (MaxDivisor(arr[i]) == -1)
            count++;
    string[] res = new string[count];
    int ind = 0;
    for (int i = 0; i < arr.Length; i++)
        if (MaxDivisor(arr[i]) == -1)
        {
            res[ind] = arr[i];
            ind++;
        }
    return res;
}

דוגמה: עבור {"ABCABC", "ABCA", "AAAAA", "AB", "XYXYXY"} יוחזר {"ABCA", "AB"}.

תשובה: הפעולות isDivisible, maxDivisor ו-notDivisible שלמעלה.

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

חנות צעצועים "כדורי" מוכרת חבילות כדורים לגני ילדים.

לפניכם הגדרה לטיפוס כדור- Ball:

•color – צבע כדור מטיפוס מחרוזת, String

•size – קוטר הכדור מטיפוס מספר שלם, int

•material – החומר שממנו עשוי הכדור (גומי, פלסטיק, עץ...) מטיפוס מחרוזת, String

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

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

•balls – מערך כדורים (מערך עצמים מטיפוס Ball). גודל המערך מוגדר בפעולה הבונה.

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

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

•numOfBalls – מספר הכדורים בחבילה.

•material – החומר שממנו עשויים הכדורים (כל הכדורים עשויים מאותו חומר).

•minSize – קוטר מינימלי של הכדור בחבילה.

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

Java:

public BallPack (int num, String[] cols, int min, String mat){
    this.balls = new Ball[num];
    this.colors = cols;
    this. numOfBalls = 0;
    this.minSize = min;
    this.material = mat;
}

C#:

public BallPack (int num, string[] cols, int min, string mat){
    this.balls = new Ball[num];
    this.colors = cols;
    this. numOfBalls = 0;
    this.minSize = min;
    this.material = mat;
}

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

א.

כתבו פעולה המקבלת כפרמטר כדור (הפניה לעצם מטיפוס Ball) ומחזירה true אם הוא מתאים לחבילה, ואם לא, הפעולה תחזיר false. כותרת הפעולה:

public boolean isFit ( Ball b )
public bool IsFit ( Ball b )
(2 נקודות)
ב.

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

public boolean add ( Ball b )
public bool Add ( Ball b )

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

(2 נקודות)
ג.

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

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

public int countColor (String color)
public int CountColor (string color)
(2 נקודות)
ד.

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

public String[] missingColors()
public string[] MissingColors()

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

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

סעיף א

תשובה:

true אם b.getSize() >= minSize, החומר שווה ל-material, והצבע נמצא במערך colors; אחרת false.

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

1. הקוטר אינו קטן מ-minSize: אם `b.getSize() < minSize` – false.

2. החומר זהה לחומר של החבילה (השוואת מחרוזות ב-equals) – אחרת false.

3. הצבע הוא אחד מצבעי המערך colors: חיפוש ליניארי; ברגע שנמצא צבע שווה מחזירים true. אם הלולאה הסתיימה בלי התאמה – false.

הכדור שייך למחלקה אחרת, ולכן ניגשים לתכונותיו דרך פעולות get; לתכונות החבילה ניגשים ישירות (הפעולה פנימית ב-BallPack).

הקוד של כל הסעיפים מופיע יחד בסוף סעיף ד.

תשובה: הפעולה isFit בקוד שבסוף סעיף ד.

סעיף ב

תשובה:

אם numOfBalls < balls.length וגם isFit(b): balls[numOfBalls] = b, numOfBalls++, מחזירים true; אחרת false.

הרעיון: הכדורים שמורים בתאים 0 עד numOfBalls−1, ולכן numOfBalls הוא גם המקום הפנוי הבא.

1. "בחבילה יש מקום" – `numOfBalls < balls.length`.

2. "הכדור מתאים" – משתמשים בפעולה isFit מסעיף א.

3. אם שני התנאים מתקיימים: מכניסים את הכדור לתא `balls[numOfBalls]`, מגדילים את numOfBalls ב-1 (זה עדכון התכונות) ומחזירים true. אחרת מחזירים false והחבילה לא משתנה.

תשובה: הפעולה add בקוד שבסוף סעיף ד.

סעיף ג

תשובה:

מונה על התאים 0..numOfBalls-1; מגדילים כאשר balls[i].getColor() שווה ל-color.

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

תשובה: הפעולה countColor בקוד שבסוף סעיף ד.

סעיף ד

תשובה:

צבע חסר אם countColor(colors[i]) == 0; סופרים את החסרים, אם 0 מחזירים null, אחרת יוצרים מערך בגודל הזה וממלאים אותו בצבעים החסרים.

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

1. מעבר ראשון: סופרים כמה צבעים חסרים.

2. אם המונה 0 – אין צבעים חסרים, ומחזירים null כנדרש.

3. אחרת יוצרים מערך מחרוזות בגודל המונה.

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

סיבוכיות: לכל אחד מ-c הצבעים סופרים על n כדורים – O(c⋅n)O(c\cdot n).

Java:

// פעולות בתוך המחלקה BallPack

// סעיף א
public boolean isFit(Ball b)
{
    if (b.getSize() < this.minSize)
        return false;                       // קטן מדי
    if (!b.getMaterial().equals(this.material))
        return false;                       // חומר לא מתאים
    for (int i = 0; i < colors.length; i++)
        if (b.getColor().equals(colors[i]))
            return true;                    // הצבע הוא מצבעי החבילה
    return false;
}

// סעיף ב
public boolean add(Ball b)
{
    if (numOfBalls < balls.length && isFit(b))
    {
        balls[numOfBalls] = b;
        numOfBalls++;
        return true;
    }
    return false;
}

// סעיף ג
public int countColor(String color)
{
    int count = 0;
    for (int i = 0; i < numOfBalls; i++)
        if (balls[i].getColor().equals(color))
            count++;
    return count;
}

// סעיף ד
public String[] missingColors()
{
    int count = 0;                          // כמה צבעים חסרים
    for (int i = 0; i < colors.length; i++)
        if (countColor(colors[i]) == 0)
            count++;
    if (count == 0)
        return null;
    String[] res = new String[count];
    int ind = 0;
    for (int i = 0; i < colors.length; i++)
        if (countColor(colors[i]) == 0)
        {
            res[ind] = colors[i];
            ind++;
        }
    return res;
}

C#:

// פעולות בתוך המחלקה BallPack

// סעיף א
public bool IsFit(Ball b)
{
    if (b.GetSize() < this.minSize)
        return false;                       // קטן מדי
    if (b.GetMaterial() != this.material)
        return false;                       // חומר לא מתאים
    for (int i = 0; i < colors.Length; i++)
        if (b.GetColor() == colors[i])
            return true;                    // הצבע הוא מצבעי החבילה
    return false;
}

// סעיף ב
public bool Add(Ball b)
{
    if (numOfBalls < balls.Length && IsFit(b))
    {
        balls[numOfBalls] = b;
        numOfBalls++;
        return true;
    }
    return false;
}

// סעיף ג
public int CountColor(string color)
{
    int count = 0;
    for (int i = 0; i < numOfBalls; i++)
        if (balls[i].GetColor() == color)
            count++;
    return count;
}

// סעיף ד
public string[] MissingColors()
{
    int count = 0;                          // כמה צבעים חסרים
    for (int i = 0; i < colors.Length; i++)
        if (CountColor(colors[i]) == 0)
            count++;
    if (count == 0)
        return null;
    string[] res = new string[count];
    int ind = 0;
    for (int i = 0; i < colors.Length; i++)
        if (CountColor(colors[i]) == 0)
        {
            res[ind] = colors[i];
            ind++;
        }
    return res;
}

דוגמה: חבילה עם colors = {"red", "blue", "green"} ובה שני כדורים אדומים: countColor("red") = 2, ו-missingColors() מחזירה {"blue", "green"}.

תשובה: הפעולות isFit, add, countColor ו-missingColors שלמעלה.

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

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

א.

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

מערך הפרש הוא מערך המכיל את הערכים שנמצאים במערך הראשון ולא נמצאים במערך השני.

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

לדוגמה: עבור

מערך הראשון:

1215402117158021

ומערך השני:

122521861217

הפעולה תחזיר:

154080
(4 נקודות)
ב.

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

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

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

לדוגמה: עבור שני המערכים הנתונים בדוגמה בסעיף א' המערך השלמה יכלול את כל המספרים הדו-ספרתיים פרט למספרים 12,15,17,21,25,40,80,86.

(5 נקודות)
ג.

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

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

סעיף א

תשובה:

מערך בוליאני inB[100] מסמן את ערכי המערך השני; עוברים על המערך הראשון ובוחרים כל ערך שאינו ב-inB ועוד לא נבחר (מערך taken); מעתיקים למערך תוצאה בגודל המתאים. בדוגמה: {15, 40, 80}.

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

1. סימון המערך השני: `inB[v] = true` לכל v במערך b.

2. בחירה וספירה: עוברים על המערך הראשון a. ערך a[i] נכנס להפרש אם הוא לא במערך השני (`!inB[a[i]]`) ועוד לא נבחר (`!taken[a[i]]`) – התנאי השני מבטיח שכל ערך יופיע פעם אחת בלבד. מסמנים אותו ב-taken וסופרים.

3. בניית התוצאה: יוצרים מערך בגודל count, ועוברים שוב על a לפי הסדר. כל ערך מסומן ב-taken מועתק, והסימון שלו מבוטל – כדי שמופע נוסף שלו לא יועתק שוב.

בדוגמה: המערך השני מסמן {12, 25, 21, 86, 17}. במערך הראשון: 12 – במערך השני; 15 – נבחר; 40 – נבחר; 21, 17 – במערך השני; 15 – כבר נבחר; 80 – נבחר; 21 – במערך השני. התוצאה {15, 40, 80} – כמו בשאלה.

הקוד של שני הסעיפים מופיע יחד בסוף סעיף ב.

תשובה: הפעולה difference בקוד שבסוף סעיף ב; בדוגמה היא מחזירה {15, 40, 80}.

סעיף ב

תשובה:

מסמנים במערך בוליאני exists[100] את כל ערכי שני המערכים; כל v מ-10 עד 99 שאינו מסומן נכנס למערך ההשלמה. בדוגמה: 82 ערכים (90 פחות 8).

הרעיון: ה"עולם" הוא כל המספרים הדו-ספרתיים: 10 עד 99, כלומר 99−10+1=9099-10+1=90 ערכים. מערך ההשלמה מכיל את אלה שלא מופיעים באף אחד משני המערכים.

1. סימון: מערך בוליאני `exists` בגודל 100; מסמנים בו את כל ערכי המערך הראשון ואת כל ערכי המערך השני.

2. ספירה: עוברים על v מ-10 עד 99 וסופרים כמה ערכים לא מסומנים.

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

בדוגמה: מסומנים 8 ערכים שונים: 12, 15, 17, 21, 25, 40, 80, 86. לכן מערך ההשלמה מכיל 90−8=8290-8=82 ערכים: 10, 11, 13, 14, 16, 18, ..., 99 (כל הדו-ספרתיים פרט לשמונה האלה).

Java:

// סעיף א
public static int[] difference(int[] a, int[] b)
{
    boolean[] inB = new boolean[100];      // inB[v] – האם v נמצא במערך b
    for (int i = 0; i < b.length; i++)
        inB[b[i]] = true;

    boolean[] taken = new boolean[100];    // taken[v] – האם v כבר נבחר להפרש
    int count = 0;
    for (int i = 0; i < a.length; i++)
        if (!inB[a[i]] && !taken[a[i]])
        {
            taken[a[i]] = true;
            count++;
        }

    int[] res = new int[count];
    int ind = 0;
    for (int i = 0; i < a.length; i++)
        if (taken[a[i]])
        {
            res[ind] = a[i];
            ind++;
            taken[a[i]] = false;           // כדי שלא ייכנס פעם נוספת
        }
    return res;
}

// סעיף ב
public static int[] complement(int[] a, int[] b)
{
    boolean[] exists = new boolean[100];   // exists[v] – האם v באחד המערכים
    for (int i = 0; i < a.length; i++)
        exists[a[i]] = true;
    for (int i = 0; i < b.length; i++)
        exists[b[i]] = true;

    int count = 0;
    for (int v = 10; v <= 99; v++)
        if (!exists[v])
            count++;

    int[] res = new int[count];
    int ind = 0;
    for (int v = 10; v <= 99; v++)
        if (!exists[v])
        {
            res[ind] = v;
            ind++;
        }
    return res;
}

C#:

// סעיף א
public static int[] Difference(int[] a, int[] b)
{
    bool[] inB = new bool[100];            // inB[v] – האם v נמצא במערך b
    for (int i = 0; i < b.Length; i++)
        inB[b[i]] = true;

    bool[] taken = new bool[100];          // taken[v] – האם v כבר נבחר להפרש
    int count = 0;
    for (int i = 0; i < a.Length; i++)
        if (!inB[a[i]] && !taken[a[i]])
        {
            taken[a[i]] = true;
            count++;
        }

    int[] res = new int[count];
    int ind = 0;
    for (int i = 0; i < a.Length; i++)
        if (taken[a[i]])
        {
            res[ind] = a[i];
            ind++;
            taken[a[i]] = false;           // כדי שלא ייכנס פעם נוספת
        }
    return res;
}

// סעיף ב
public static int[] Complement(int[] a, int[] b)
{
    bool[] exists = new bool[100];         // exists[v] – האם v באחד המערכים
    for (int i = 0; i < a.Length; i++)
        exists[a[i]] = true;
    for (int i = 0; i < b.Length; i++)
        exists[b[i]] = true;

    int count = 0;
    for (int v = 10; v <= 99; v++)
        if (!exists[v])
            count++;

    int[] res = new int[count];
    int ind = 0;
    for (int v = 10; v <= 99; v++)
        if (!exists[v])
        {
            res[ind] = v;
            ind++;
        }
    return res;
}

תשובה: הפעולות difference ו-complement שלמעלה; בדוגמה מערך ההשלמה כולל 82 ערכים.

סעיף ג

תשובה:

שתיהן O(n+m)O(n+m) (n, m – אורכי המערכים): כל מערך נסרק מספר קבוע של פעמים, והמעבר על 90 הערכים האפשריים קבוע.

נסמן ב-n את אורך המערך הראשון וב-m את אורך המערך השני.

סעיף א: סימון המערך השני – m צעדים; שני מעברים על המערך הראשון – 2n2n צעדים. כל בדיקה במערך הבוליאני היא גישה ישירה לתא, בזמן קבוע. סך הכול O(n+m)O(n+m).

סעיף ב: סימון שני המערכים – n+mn+m צעדים; שני מעברים על הערכים 10 עד 99 – 2⋅90=1802\cdot 90=180 צעדים, מספר קבוע שאינו תלוי בגודל הקלט. סך הכול O(n+m)O(n+m).

הסיבוכיות הליניארית מתאפשרת כי הערכים מוגבלים לתחום קטן וידוע (דו-ספרתיים), ולכן אפשר להשתמש במערך סימון במקום לולאה מקוננת (שהייתה נותנת O(n⋅m)O(n\cdot m)).

תשובה: סיבוכיות הזמן של שתי הפעולות היא O(n+m)O(n+m).

שאלה 12 · מערך דו-ממדי: מספרים חמודים ועמודה נחמדה

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

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

לדוגמה:

המספרים 2378, 737, 16, 48 הם מספרים "חמודים" כי בכל אחד מהמספרים האלה הספרה הימנית ביותר מתחלקת בספרה השמאלית ביותר ללא שארית.

•עמודה במערך דו-ממדי נקראת "נחמדה" אם כל הערכים הנמצאים בעמודה זו הם "חמודים".

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

א.

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

(8 נקודות)
ב.

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

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

סעיף א

תשובה:

שלוש פעולות: isCute (ספרה ימנית num%10, שמאלית – חילוק ב-10 עד שנשארת ספרה אחת; right % left == 0), isNiceColumn (כל איברי העמודה חמודים), isSweetie (קיימת עמודה נחמדה).

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

1. isCute(num) – מספר "חמוד":

•הספרה הימנית: `num % 10`.

•הספרה השמאלית: מחלקים ב-10 שוב ושוב כל עוד נשארו לפחות שתי ספרות (`left >= 10`). למשל 2378 → 237 → 23 → 2.

•הימנית היא כפולה של השמאלית אם היא מתחלקת בה ללא שארית: `right % left == 0`. הספרה השמאלית של מספר חיובי אינה 0, ולכן אין חילוק ב-0.

•בדיקה על הדוגמאות: 2378: 8%2=08\%2=0; 737: 7%7=07\%7=0; 16: 6%1=06\%1=0; 48: 8%4=08\%4=0 – כולם חמודים. לעומת זאת 23: 3%2=13\%2=1 – לא חמוד.

2. isNiceColumn(mat, col) – עמודה "נחמדה": עוברים על כל השורות בעמודה col. מספיק מספר אחד שאינו חמוד כדי להחזיר false; אם כולם חמודים – true.

3. isSweetie(mat) – מערך "מותק": עוברים על העמודות (מספר העמודות הוא אורך שורה, `mat[0].length`). ברגע שנמצאה עמודה נחמדה מחזירים true; אם אף עמודה אינה נחמדה – false.

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

Java:

// האם המספר "חמוד"
public static boolean isCute(int num)
{
    int right = num % 10;              // הספרה הימנית
    int left = num;
    while (left >= 10)                 // מוחקים ספרות עד שנשארת השמאלית
        left /= 10;
    return right % left == 0;
}

// האם העמודה col "נחמדה"
public static boolean isNiceColumn(int[][] mat, int col)
{
    for (int row = 0; row < mat.length; row++)
        if (!isCute(mat[row][col]))
            return false;
    return true;
}

// סעיף א: האם המערך "מותק"
public static boolean isSweetie(int[][] mat)
{
    for (int col = 0; col < mat[0].length; col++)
        if (isNiceColumn(mat, col))
            return true;               // נמצאה עמודה "נחמדה"
    return false;
}

C#:

// האם המספר "חמוד"
public static bool IsCute(int num)
{
    int right = num % 10;              // הספרה הימנית
    int left = num;
    while (left >= 10)                 // מוחקים ספרות עד שנשארת השמאלית
        left /= 10;
    return right % left == 0;
}

// האם העמודה col "נחמדה"
public static bool IsNiceColumn(int[,] mat, int col)
{
    for (int row = 0; row < mat.GetLength(0); row++)
        if (!IsCute(mat[row, col]))
            return false;
    return true;
}

// סעיף א: האם המערך "מותק"
public static bool IsSweetie(int[,] mat)
{
    for (int col = 0; col < mat.GetLength(1); col++)
        if (IsNiceColumn(mat, col))
            return true;               // נמצאה עמודה "נחמדה"
    return false;
}

דוגמה: במערך

(23167482113113015)\begin{pmatrix}23 & 16 & 7\\ 48 & 21 & 13\\ 11 & 30 & 15\end{pmatrix}

עמודה 0 אינה נחמדה (23), עמודה 1 אינה נחמדה (21: 1%2≠01\%2\ne 0), ועמודה 2 נחמדה (7, 13, 15 – כל אחד מתחלק בספרה השמאלית). לכן המערך "מותק" – מוחזר true.

תשובה: הפעולה isSweetie (עם פעולות העזר isCute ו-isNiceColumn) שלמעלה.

סעיף ב

תשובה:

O(n⋅m)O(n\cdot m) עבור מערך של n שורות ו-m עמודות (במקרה הגרוע עוברים על כל התאים, ובדיקת מספר חמוד היא לפי מספר ספרותיו – קבוע לכל היותר 10 עבור int).

נסמן: n – מספר השורות, m – מספר העמודות.

1. isCute: לולאת החילוק ב-10 רצה כמספר הספרות d של המספר. עבור int יש לכל היותר 10 ספרות, ולכן זה זמן קבוע, O(d)=O(1)O(d)=O(1).

2. isNiceColumn: קוראת ל-isCute לכל היותר n פעמים – O(n)O(n).

3. isSweetie: קוראת ל-isNiceColumn לכל היותר m פעמים – O(n⋅m)O(n\cdot m).

המקרה הגרוע: אין עמודה נחמדה, ובכל עמודה המספר הלא-חמוד נמצא בשורה האחרונה – אז נבדקים כל n⋅mn\cdot m התאים. (אם רוצים לכלול את מספר הספרות: O(n⋅m⋅d)O(n\cdot m\cdot d).) במקרה הטוב העמודה הראשונה נחמדה, ונבדקים רק n תאים.

תשובה: סיבוכיות הזמן היא O(n⋅m)O(n\cdot m) – ליניארית במספר התאים של המערך.

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

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

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