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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

פתרון

תשובה:

לולאה של 50 סיבובים מגרילה מספר בין 100 ל-999 ומעדכנת מינימום; אחרי הלולאה מפרקים את המינימום לספרות (%10, /10) ומדפיסים אותו ואת סכום ספרותיו.

הרעיון: מספר תלת-ספרתי חיובי הוא מספר בין 100 ל-999 (כולל), ולכן מגרילים לפי הנוסחה מההנחיות עם X=100X=100 ו-Y=999Y=999. בזמן ההגרלה שומרים את הקטן ביותר עד כה, ובסוף מחשבים את סכום ספרותיו.

1. מינימום: מאתחלים `min = 1000` – ערך גדול מכל מספר תלת-ספרתי, כך שהמספר הראשון שיוגרל בוודאות יחליף אותו. בכל סיבוב, אם המספר החדש קטן מ-min, מעדכנים את min. (אפשר גם לאתחל את min במספר הראשון שהוגרל.)

2. סכום ספרות: אחרי הלולאה עובדים על עותק `n` של המינימום. בכל סיבוב `n % 10` היא הספרה הימנית – מוסיפים אותה לסכום, ו-`n / 10` מוחק אותה. כשמגיעים ל-0 עברנו על כל הספרות. למשל עבור 107: 7+0+1=87+0+1=8.

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

סיבוכיות: 50 סיבובים ועוד 3 סיבובים לפירוק הספרות – מספר קבוע של פעולות.

Java:

import java.util.Random;

public class Q1
{
    public static void main(String[] args)
    {
        Random rand = new Random();
        int min = 1000;                  // גדול מכל מספר תלת-ספרתי
        for (int i = 0; i < 50; i++)
        {
            int num = 100 + rand.nextInt(999 - 100 + 1);   // מספר בין 100 ל-999
            System.out.print(num + " ");
            if (num < min)
                min = num;
        }
        System.out.println();

        int sum = 0;
        int n = min;                     // עותק, כדי לא לקלקל את min
        while (n > 0)
        {
            sum += n % 10;               // הספרה הימנית
            n /= 10;                     // מוחקים אותה
        }
        System.out.println("Min: " + min);
        System.out.println("Sum of digits: " + sum);
    }
}

C#:

using System;

class Q1
{
    static void Main(string[] args)
    {
        Random rand = new Random();
        int min = 1000;                  // גדול מכל מספר תלת-ספרתי
        for (int i = 0; i < 50; i++)
        {
            int num = rand.Next(100, 999 + 1);              // מספר בין 100 ל-999
            Console.Write(num + " ");
            if (num < min)
                min = num;
        }
        Console.WriteLine();

        int sum = 0;
        int n = min;                     // עותק, כדי לא לקלקל את min
        while (n > 0)
        {
            sum += n % 10;               // הספרה הימנית
            n /= 10;                     // מוחקים אותה
        }
        Console.WriteLine("Min: " + min);
        Console.WriteLine("Sum of digits: " + sum);
    }
}

תשובה: קטע התוכנית שלמעלה: מגרילים 50 מספרים בין 100 ל-999, שומרים את הקטן ביותר, ובסוף מדפיסים אותו ואת סכום ספרותיו.

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

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

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

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

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

פתרון

תשובה:

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

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

1. ספירת 'A': לכל מחרוזת עוברים בלולאה על כל התווים `str.charAt(i)` (ב-C#: `str[i]`) ומגדילים מונה `countA` בכל פעם שהתו הוא `'A'`. המונה מאופס מחדש לכל מחרוזת, ומודפס מיד אחרי המעבר עליה. למשל עבור BANANA יודפס 3.

2. אורך זוגי: מחרוזת היא באורך זוגי אם `str.length() % 2 == 0`; במקרה כזה מגדילים את `evenCount`. המונה הזה אינו מאופס – הוא צובר לאורך כל הקלט ומודפס אחרי הלולאה.

3. עצירה: הלולאה ממשיכה כל עוד `str.charAt(0) != str.charAt(str.length() - 1)`. מניחים שכל מחרוזת שנקלטת אינה ריקה (אחרת אין לה תו ראשון).

דוגמה: עבור הקלט AAB, xyzw, BANANA, AbA יודפסו 2, 0, 3, 2 (הקלט נעצר ב-AbA, שמתחילה ומסתיימת ב-A), ובסוף מספר המחרוזות באורך זוגי: 2 (xyzw ו-BANANA).

Java:

import java.util.Scanner;

public class Q2
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int evenCount = 0;                     // מספר המחרוזות באורך זוגי
        String str;
        do
        {
            str = in.next();
            int countA = 0;                    // כמה פעמים מופיעה 'A' במחרוזת הנוכחית
            for (int i = 0; i < str.length(); i++)
            {
                if (str.charAt(i) == 'A')
                    countA++;
            }
            System.out.println(str + ": " + countA);
            if (str.length() % 2 == 0)
                evenCount++;
        }
        while (str.charAt(0) != str.charAt(str.length() - 1));   // עוצרים כשהתו הראשון = התו האחרון

        System.out.println("Even length: " + evenCount);
    }
}

C#:

using System;

class Q2
{
    static void Main(string[] args)
    {
        int evenCount = 0;                     // מספר המחרוזות באורך זוגי
        string str;
        do
        {
            str = Console.ReadLine();
            int countA = 0;                    // כמה פעמים מופיעה 'A' במחרוזת הנוכחית
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == 'A')
                    countA++;
            }
            Console.WriteLine(str + ": " + countA);
            if (str.Length % 2 == 0)
                evenCount++;
        }
        while (str[0] != str[str.Length - 1]);  // עוצרים כשהתו הראשון = התו האחרון

        Console.WriteLine("Even length: " + evenCount);
    }
}

תשובה: קטע התוכנית שלמעלה (לולאת do-while; מונה 'A' לכל מחרוזת ומונה כולל של מחרוזות באורך זוגי).

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

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

לדוגמה:

המערך הבא הוא מערך "מאוזן":

0123456
1237155126
א.

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

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

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

כתבו פעולה המקבלת מספר שלם וחיובי size>2 ושני פרמטרים נוספים x ו- y, מטיפוס מספר שלם.

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

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

public static int[] fill(int size, int x, int y)
public static int[] Fill(int size, int x, int y)

אפשר להניח ש- x<y.

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

סעיף א

תשובה:

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

הרעיון: עוברים פעם אחת על המערך. האינדקס i קובע לאיזה סכום שייך התא: אם `i % 2 == 0` המקום זוגי, אחרת אי-זוגי. בסוף משווים את שני הסכומים.

1. מאתחלים שני צוברים: `evenSum = 0` ו-`oddSum = 0`.

2. לכל i מוסיפים את `arr[i]` לצובר המתאים לזוגיות של i.

3. מחזירים `evenSum == oddSum` – ביטוי בוליאני שערכו true בדיוק כשהמערך מאוזן.

בדיקה עם הדוגמה: במקומות הזוגיים 0, 2, 4, 6: 12+7+5+6=3012+7+5+6=30; במקומות האי-זוגיים 1, 3, 5: 3+15+12=303+15+12=30. הסכומים שווים, והפעולה מחזירה true.

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

Java:

public static boolean isBalanced(int[] arr)
{
    int evenSum = 0, oddSum = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (i % 2 == 0)
            evenSum += arr[i];      // מקום זוגי
        else
            oddSum += arr[i];       // מקום אי-זוגי
    }
    return evenSum == oddSum;
}

C#:

public static bool IsBalanced(int[] arr)
{
    int evenSum = 0, oddSum = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (i % 2 == 0)
            evenSum += arr[i];      // מקום זוגי
        else
            oddSum += arr[i];       // מקום אי-זוגי
    }
    return evenSum == oddSum;
}

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

סעיף ב

תשובה:

יוצרים מערך בגודל size וממלאים אותו במספרים אקראיים בין x ל-y שוב ושוב (do-while) עד ש-isBalanced מחזירה true; מחזירים את המערך.

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

1. יוצרים מערך `arr` בגודל size.

2. בלולאת do-while: ממלאים כל תא במספר אקראי בין x ל-y כולל, לפי הנוסחה מההנחיות: `x + rand.nextInt(y - x + 1)` (ב-C#: `rand.Next(x, y + 1)`).

3. תנאי ההמשך הוא `!isBalanced(arr)` – כל עוד המערך אינו מאוזן ממלאים אותו מחדש.

4. כשהלולאה מסתיימת המערך מאוזן, ומחזירים אותו.

הערה: כש-size זוגי תמיד קיים מילוי מאוזן (למשל כל הערכים שווים), ולכן הלולאה תסתיים. כש-size אי-זוגי יש מקום זוגי אחד יותר ממקומות אי-זוגיים, ואם x ו-y גדולים וקרובים זה לזה ייתכן שאין שום מילוי מאוזן (למשל size=3size=3, x=5x=5, y=6y=6: arr[0]+arr[2]≥10arr[0]+arr[2]\ge 10 אבל arr[1]≤6arr[1]\le 6). מניחים שהנתונים מאפשרים מערך מאוזן, כפי שהשאלה מניחה.

Java:

public static int[] fill(int size, int x, int y)
{
    Random rand = new Random();          // import java.util.Random;
    int[] arr = new int[size];
    do
    {
        for (int i = 0; i < size; i++)
            arr[i] = x + rand.nextInt(y - x + 1);   // מספר בין x ל-y כולל
    }
    while (!isBalanced(arr));            // ממלאים מחדש עד שהמערך מאוזן
    return arr;
}

C#:

public static int[] Fill(int size, int x, int y)
{
    Random rand = new Random();
    int[] arr = new int[size];
    do
    {
        for (int i = 0; i < size; i++)
            arr[i] = rand.Next(x, y + 1);           // מספר בין x ל-y כולל
    }
    while (!IsBalanced(arr));            // ממלאים מחדש עד שהמערך מאוזן
    return arr;
}

תשובה: הפעולה fill שלמעלה (מילוי אקראי חוזר עד שהמערך מאוזן).

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

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

•מחלקה 1 – נעלי נשים

•מחלקה 2 – נעלי גברים

•מחלקה 3 – נעלי ילדים

•מחלקה 4 – נעלי ספורט

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

לדוגמה: המספר 321 בקטלוג מציין נעל ילדים אשר קוד המוצר שלה הוא 21.

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

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

אפשר להניח שקלט תקין.

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

פתרון

תשובה:

לולאת while עד מספר קטלוג 0; קוד המחלקה הוא catalog/100, ומספר הזוגות מתווסף למונה pairs[dept] ולסכום הכולל; בסוף מדפיסים את ארבעת המונים ואת הסכום.

הרעיון: צריך ארבעה צוברים, אחד לכל מחלקה, ולכן נוח להשתמש במערך מונים שהאינדקס שלו הוא קוד המחלקה. קוד המחלקה הוא ספרת המאות של מספר הקטלוג, כלומר `catalog / 100` (חילוק שלמים). למשל 321/100=3321/100=3 – מחלקה 3, נעלי ילדים.

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

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

3. טיפול בשורה: `dept = catalog / 100`, ואז `pairs[dept] += count` ו-`total += count`. מספר הקטלוג יכול להופיע כמה פעמים – הזוגות פשוט מצטברים.

4. פלט: אחרי הלולאה מדפיסים את `pairs[1]` עד `pairs[4]` ואת `total`. (הסכום הכולל שווה גם לסכום ארבעת המונים.)

דוגמה: עבור הקלט 321 5, 105 2, 412 3, 230 4, 399 1, 0 יודפס: מחלקה 1 – 2, מחלקה 2 – 4, מחלקה 3 – 5+1=65+1=6, מחלקה 4 – 3, ובסך הכול 2+4+6+3=152+4+6+3=15 זוגות.

Java:

import java.util.Scanner;

public class Q4
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int[] pairs = new int[5];       // pairs[1]..pairs[4] – מונה זוגות לכל מחלקה
        int total = 0;                  // סך כל הזוגות שמכר המפעל

        int catalog = in.nextInt();
        while (catalog != 0)
        {
            int count = in.nextInt();   // מספר הזוגות שנמכרו מקוד זה
            int dept = catalog / 100;   // ספרת המאות = קוד המחלקה
            pairs[dept] += count;
            total += count;
            catalog = in.nextInt();
        }

        for (int d = 1; d <= 4; d++)
            System.out.println("Department " + d + ": " + pairs[d]);
        System.out.println("Total: " + total);
    }
}

C#:

using System;

class Q4
{
    static void Main(string[] args)
    {
        int[] pairs = new int[5];       // pairs[1]..pairs[4] – מונה זוגות לכל מחלקה
        int total = 0;                  // סך כל הזוגות שמכר המפעל

        int catalog = int.Parse(Console.ReadLine());
        while (catalog != 0)
        {
            int count = int.Parse(Console.ReadLine());   // מספר הזוגות שנמכרו מקוד זה
            int dept = catalog / 100;   // ספרת המאות = קוד המחלקה
            pairs[dept] += count;
            total += count;
            catalog = int.Parse(Console.ReadLine());
        }

        for (int d = 1; d <= 4; d++)
            Console.WriteLine("Department " + d + ": " + pairs[d]);
        Console.WriteLine("Total: " + total);
    }
}

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

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

א.

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

Java:

public static double one(int num)
{
    double x = 0;
    int y = 0;
    while (num > 0)
    {
        x += (num % 10);
        y ++;
        num /= 10;
    }
    return x/y;
}

C#:

public static double One(int num)
{
    double x = 0;
    int y = 0;
    while (num > 0)
    {
        x += (num % 10);
        y ++;
        num /= 10;
    }
    return x/y;
}
(1)

מה תחזיר הפעולה עבור num=12345? עקבו באמצעות טבלת מעקב אחר זימון הפעולה one(12345).

(2)

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

(6 נקודות)
ב.

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

Java:

public static void two(int[] arr)
{
    int res = 0;

    for (int i = 1; i < arr.length; i++)
    {
        if (one(arr[i]) > one(arr[res]))
       {
            res = i;
        }
    }
    System.out.println(arr[res]);
}

C#:

public static void Two(int[] arr)
{
    int res = 0;

    for (int i = 1; i < arr.Length; i++)
    {
        if (One(arr[i]) > One(arr[res]))
       {
            res = i;
        }
    }
    Console.WriteLine(arr[res]);
}

נתון מערך של מספרים שלמים וחיוביים arr הבא:

int[] arr = {24, 34783, 1245, 68, 468, 95};
(1)

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

(2)

הסבירו מה תבצע הפעולה two(arr) עבור מערך כלשהו של מספרים שלמים וחיוביים.

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

סעיף א

(1)
תשובה:

one(12345) מחזירה 3.0.

עוקבים אחרי המשתנים בכל סיבוב של הלולאה. בכל סיבוב `num % 10` היא הספרה הימנית, היא מתווספת ל-x, y גדל ב-1 ו-num מאבד את ספרתו הימנית.

סיבובnum בתחילת הסיבובnum % 10xynum בסוף הסיבוב
לפני הלולאה12345–0.00–
11234555.011234
2123449.02123
3123312.0312
412214.041
51115.050

כש-num מגיע ל-0 הלולאה מסתיימת, והפעולה מחזירה xy=15.05=3.0\frac{x}{y}=\frac{15.0}{5}=3.0. מכיוון ש-x מטיפוס double, החילוק הוא ממשי.

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

(2)
תשובה:

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

בלולאה x צובר את כל הספרות של num (סכום הספרות), ו-y סופר כמה ספרות יש. בסוף מוחזר xy\frac{x}{y} – סכום הספרות חלקי מספר הספרות, כלומר הממוצע של ספרות המספר. למשל עבור 12345: 1+2+3+4+55=3.0\frac{1+2+3+4+5}{5}=3.0.

תשובה: הפעולה מחזירה את ממוצע הספרות של num.

סעיף ב

(1)
תשובה:

יודפס 68.

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

איברספרותone(איבר)
242, 462=3.0\frac{6}{2}=3.0
347833, 4, 7, 8, 3255=5.0\frac{25}{5}=5.0
12451, 2, 4, 5124=3.0\frac{12}{4}=3.0
686, 8142=7.0\frac{14}{2}=7.0
4684, 6, 8183=6.0\frac{18}{3}=6.0
959, 5142=7.0\frac{14}{2}=7.0

עכשיו עוקבים אחרי הלולאה (בהתחלה res=0res=0):

סיבוב: iarr[i]one(arr[i])one(arr[res])one(arr[i]) > one(arr[res])?res
לפני הלולאה––––0
1347835.03.0כן1
212453.05.0לא1
3687.05.0כן3
44686.07.0לא3
5957.07.0לא (שוויון)3

בסוף מודפס `arr[3]`. שימו לב שגם ל-95 ממוצע 7.0, אבל ההשוואה היא `>` חזק, ולכן הוא אינו מחליף את 68.

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

(2)
תשובה:

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

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

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

שאלה 6 · מעקב: פיצול תווי מחרוזת לפי מחרוזת שנייה

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

Java:

public static String mystery(String s1, String s2)
{
    String out1 = "";
    String out2 = "";
    for(int i=0; i<s1.length(); i++)
    {
        char ch = s1.charAt(i);
        int pos = s2.indexOf(ch);
        if(pos == -1)
        {
            if(out1.indexOf(ch) == -1)
                out1 = out1 + ch;
        }
        else
        {
            if(out2.indexOf(ch) == -1)
                out2 =out2 + ch;
        }
    }
    return out1 + out2;
}

C#:

public static string  Mystery (string  s1, string  s2)
{
    string  out1 = "";
    string  out2 = "";
    for(int i=0; i<s1.Length; i++)
    {
        char ch = s1[i];
        int pos = s2.IndexOf(ch);
        if(pos == -1)
        {
            if(out1.IndexOf(ch) == -1)
                out1 = out1 + ch;
        }
        else
        {
            if(out2.IndexOf(ch) == -1)
                out2 =out2 + ch;
        }
    }
    return out1 + out2;
}
א.

נתונות שתי מחרוזות s1="COMPUTERS" ו- s2="CANNOTTHINK"

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

(6 נקודות)
ב.

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

(3 נקודות)
ג.

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

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

סעיף א

תשובה:

mystery(s1, s2) מחזירה "MPUERSCOT".

עוברים על התווים של s1 לפי הסדר. לכל תו בודקים את מקומו ב-s2 (pos). אם הוא לא מופיע ב-s2 (pos=−1pos=-1) הוא מתווסף ל-out1, אחרת ל-out2 – ובשני המקרים רק אם הוא עוד לא נמצא שם.

במחרוזת s2="CANNOTTHINK" המקומות הם: C–0, A–1, N–2, N–3, O–4, T–5, T–6, H–7, I–8, N–9, K–10.

סיבוב: ichpos = s2.indexOf(ch)out1out2
לפני הלולאה––""""
0C0"""C"
1O4"""CO"
2M−1-1"M""CO"
3P−1-1"MP""CO"
4U−1-1"MPU""CO"
5T5"MPU""COT"
6E−1-1"MPUE""COT"
7R−1-1"MPUER""COT"
8S−1-1"MPUERS""COT"

בסוף מוחזר out1 + out2 = "MPUERS" + "COT".

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

סעיף ב

תשובה:

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

•out1 אוסף את התווים של s1 שאינם מופיעים ב-s2.

•out2 אוסף את התווים של s1 שכן מופיעים ב-s2.

•הבדיקה `indexOf(ch) == -1` על out1 / out2 מונעת כפילויות: כל תו נכנס פעם אחת בלבד, בסדר ההופעה הראשונה שלו ב-s1.

תשובה: הפעולה מחזירה מחרוזת של התווים השונים של s1, לפי סדר הופעתם: קודם התווים שאינם מופיעים ב-s2, ואחריהם התווים שמופיעים גם ב-s2.

סעיף ג

תשובה:

כן. למשל s1="ABA" ו-s2="AB": שני הזימונים מחזירים "AB".

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

ניקח s1="ABA" ו-s2="AB":

1. mystery("ABA", "AB"): A מופיע ב-s2 ← out2="A"; B מופיע ← out2="AB"; A שוב – כבר קיים ב-out2 ולא מתווסף. out1="" ולכן מוחזר "AB".

2. mystery("AB", "ABA"): A מופיע ב-"ABA" ← out2="A"; B מופיע ← out2="AB". מוחזר "AB".

שתי התוצאות שוות, למרות ש-"ABA" ≠ "AB".

תשובה: כן, למשל s1="ABA" ו-s2="AB" – שני הזימונים מחזירים "AB".

שאלה 7 · מחלקת צעצוע: בנאי, מעקב והשלמת קוד

נתונה המחלקה צעצוע Toy שיש לה ארבע תכונות:

•קוד צעצוע – code, מטיפוס שלם, int

•גיל מינימלי – age, מטיפוס שלם, int

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

•האם אפשר להזמין באינטרנט isPossible, מטיפוס בוליאני, boolean (true – אפשר להזמין, false – אי אפשר להזמין)?

במחלקה הוגדרה פעולה הבונה (בנאי, constructor)

public Toy (int code, int age, double price, boolean isPossible)
public Toy (int code, int age, double price, bool isPossible)

לכל תכונות של המחלקה הוגדרו פעולות get/set

א.

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

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

public Toy(int code, double price)
(4 נקודות)
ב.

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

Java:

Toy t1 = new Toy(1122, 10, 120.0, true);
Toy t2 = new Toy (2233, 55.0);
//  (*)  כאן יש להוסיף פקודה/פקודות בסעיף ג'
if( t1.getAge()> 6 && !t1.getIsPossible())
  System.out.println("1");
else
  System.out.println("2");
if(t2.getPrice()< 100)
  System.out.println("3");
else
  if(!t2.getIsPossible())
    System.out.println("4");

C#:

Toy t1 = new Toy(1122, 10, 120.0, true);
Toy t2 = new Toy (2233, 55.0);
//  (*)  כאן יש להוסיף פקודה/פקודות בסעיף ג'
if( t1.GetAge()> 6 && !t1.GetIsPossible())
  Console.WriteLine("1");
else
  Console.WriteLine("2");
if(t2.GetPrice()< 100)
  Console.WriteLine("3");
else
  if(!t2.GetIsPossible())
    Console.WriteLine("4");
(4 נקודות)
ג.

השלימו בקוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה "1" בלבד.

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

סעיף א

תשובה:

בנאי שמציב את code ו-price מהפרמטרים, age = 10 ו-isPossible = false.

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

Java:

public Toy(int code, double price)
{
    this.code = code;
    this.price = price;
    this.age = 10;              // גיל מינימלי עשר
    this.isPossible = false;    // אי אפשר להזמין באינטרנט
}

C#:

public Toy(int code, double price)
{
    this.code = code;
    this.price = price;
    this.age = 10;              // גיל מינימלי עשר
    this.isPossible = false;    // אי אפשר להזמין באינטרנט
}

(אפשר גם לזמן את הבנאי המלא: ב-Java `this(code, 10, price, false);` וב-C# `: this(code, 10, price, false)`.)

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

סעיף ב

תשובה:

הפלט: 2 ואחריו 3 (בשתי שורות).

קודם רושמים את מצב העצמים אחרי היצירה. t1 נוצר בבנאי המלא; t2 נוצר בבנאי מסעיף א', ולכן הגיל שלו 10 ואי אפשר להזמין אותו באינטרנט.

עצםcodeagepriceisPossible
t1112210120.0true
t222331055.0false

עכשיו עוקבים אחרי התנאים:

תנאיחישובערךפלט
`t1.getAge() > 6 && !t1.getIsPossible()`10>610>6 אמת, `!true` שקרfalse2
`t2.getPrice() < 100`55.0<10055.0<100true3

כיוון שהתנאי השני אמת, ה-else שלו (הבדיקה של "4") אינו מתבצע.

תשובה: יודפס 2 ובשורה הבאה 3.

סעיף ג

תשובה:

t1.setIsPossible(false); t2.setPrice(150.0); t2.setIsPossible(true);

נתון: הקוד מסעיף ב'. מבוקש: שיודפס רק "1".

1. כדי שיודפס "1" (ולא "2"): צריך ש-`t1.getAge() > 6` (כבר מתקיים, הגיל 10) וגם `!t1.getIsPossible()` – כלומר t1 לא ניתן להזמנה באינטרנט. לכן: `t1.setIsPossible(false);`

2. כדי שלא יודפס "3": צריך ש-`t2.getPrice() < 100` יהיה שקר, כלומר מחיר t2 לפחות 100. למשל `t2.setPrice(150.0);`

3. כדי שלא יודפס "4": כשהתנאי של "3" שקר נבדק `!t2.getIsPossible()`. כדי שהוא יהיה שקר צריך ש-t2 יהיה ניתן להזמנה: `t2.setIsPossible(true);`

Java:

t1.setIsPossible(false);
t2.setPrice(150.0);
t2.setIsPossible(true);

C#:

t1.SetIsPossible(false);
t2.SetPrice(150.0);
t2.SetIsPossible(true);

עם הפקודות האלה: התנאי הראשון 10>610>6 וגם `!false` – אמת, יודפס 1; 150.0<100150.0<100 שקר; `!true` שקר – לא יודפס דבר נוסף.

תשובה: במקום (*) מוסיפים `t1.setIsPossible(false); t2.setPrice(150.0); t2.setIsPossible(true);` (כל מחיר של 100 ומעלה מתאים).

שאלה 8 · מספרים זרים ומערך זרים

א.

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

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

public static boolean exist(int num, int digit)
public static bool Exist(int num, int digit)
(3 נקודות)
ב.

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

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

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

public static boolean isStrangers(int num1, int num2)
public static bool IsStrangers(int num1, int num2)
(4 נקודות)
ג.

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

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

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

public static boolean isItStrangers(int[] arr)
public static bool IsItStrangers(int[] arr)
(5 נקודות)
ד.

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

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

סעיף א

תשובה:

מפרקים את num לספרות (%10, /10) ומחזירים true ברגע שספרה שווה ל-digit; אם לא נמצאה – false.

הרעיון: עוברים על ספרות num מימין לשמאל: `num % 10` היא הספרה הימנית ו-`num /= 10` מוחק אותה. אם אחת הספרות שווה ל-digit – מחזירים מיד true. אם הלולאה הסתיימה (num הגיע ל-0) בלי למצוא – מחזירים false.

למשל exist(1234, 3): הספרות 4, 3 – בספרה השנייה נמצאה התאמה, true. exist(1234, 5): עוברים על 4, 3, 2, 1 – false.

Java:

public static boolean exist(int num, int digit)
{
    while (num > 0)
    {
        if (num % 10 == digit)      // הספרה הימנית שווה ל-digit
            return true;
        num /= 10;                  // מוחקים את הספרה הימנית
    }
    return false;
}

C#:

public static bool Exist(int num, int digit)
{
    while (num > 0)
    {
        if (num % 10 == digit)      // הספרה הימנית שווה ל-digit
            return true;
        num /= 10;                  // מוחקים את הספרה הימנית
    }
    return false;
}

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

סעיף ב

תשובה:

לכל ספרה של num1 בודקים בעזרת exist אם היא נמצאת ב-num2; אם כן – false, ואם אף ספרה לא נמצאה – true.

הרעיון: שני מספרים אינם זרים אם יש ספרה של num1 שמופיעה גם ב-num2. לכן מפרקים את num1 לספרות, ולכל ספרה משתמשים בפעולה מסעיף א' כדי לבדוק אם היא קיימת ב-num2. ברגע שנמצאה ספרה משותפת מחזירים false; אם עברנו על כל הספרות – המספרים זרים, ומחזירים true.

למשל isStrangers(123, 456): אף אחת מ-3, 2, 1 אינה ב-456 – true. isStrangers(123, 345): הספרה 3 נמצאת ב-345 – false.

Java:

public static boolean isStrangers(int num1, int num2)
{
    while (num1 > 0)
    {
        if (exist(num2, num1 % 10))     // ספרה של num1 נמצאת גם ב-num2
            return false;
        num1 /= 10;
    }
    return true;
}

C#:

public static bool IsStrangers(int num1, int num2)
{
    while (num1 > 0)
    {
        if (Exist(num2, num1 % 10))     // ספרה של num1 נמצאת גם ב-num2
            return false;
        num1 /= 10;
    }
    return true;
}

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

סעיף ג

תשובה:

בודקים כל זוג איברים i<j בעזרת isStrangers; אם זוג אחד אינו זר – false, אחרת true.

הרעיון: "כל האיברים זרים זה לזה" פירושו שכל זוג איברים במקומות שונים הם זרים. עוברים על כל הזוגות בשתי לולאות מקוננות: i מ-0 עד הלפני-אחרון, ו-j מ-i+1i+1 עד הסוף (כך כל זוג נבדק פעם אחת, ואיבר אינו מושווה לעצמו). אם נמצא זוג שאינו זר – מחזירים false מיד; אם כל הזוגות זרים – true.

למשל {12, 345, 67, 890} הוא מערך זרים (אין ספרה שחוזרת בשני מספרים), אבל {12, 345, 61} אינו – ל-12 ול-61 יש את הספרה 1.

Java:

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

C#:

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

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

סעיף ד

תשובה:

א: O(d)O(d) (מספר הספרות של num); ב: O(d1⋅d2)O(d_1\cdot d_2); ג: O(n2⋅d2)O(n^2\cdot d^2), ומכיוון שמספר הספרות של int חסום (עד 10) – O(n2)O(n^2).

נסמן ב-d את מספר הספרות של מספר (עבור num זה d≈log⁡10numd\approx\log_{10}num), וב-n את אורך המערך.

1. סעיף א' (exist): הלולאה מסתובבת לכל היותר פעם אחת לכל ספרה של num, ובכל סיבוב מספר קבוע של פעולות – O(d)O(d).

2. סעיף ב' (isStrangers): הלולאה עוברת על d1d_1 הספרות של num1, ובכל סיבוב מזמנת את exist על num2 בעלות O(d2)O(d_2). בסך הכול O(d1⋅d2)O(d_1\cdot d_2).

3. סעיף ג' (isItStrangers): הלולאות המקוננות בודקות במקרה הגרוע את כל הזוגות: n(n−1)2\frac{n(n-1)}{2} זוגות, וכל בדיקה עולה O(d2)O(d^2). בסך הכול O(n2⋅d2)O(n^2\cdot d^2).

מספר מטיפוס int הוא בן 10 ספרות לכל היותר, ולכן d חסום בקבוע. אם מתייחסים לכך: סעיפים א' ו-ב' הם O(1)O(1), וסעיף ג' הוא O(n2)O(n^2).

תשובה: א – O(d)O(d); ב – O(d1⋅d2)O(d_1\cdot d_2); ג – O(n2⋅d2)O(n^2\cdot d^2), כלומר O(n2)O(n^2) במונחי גודל המערך.

שאלה 9 · מחלקת מדד איכות אוויר: דירוג והדפסות

מדד איכות האוויר (Air Quality Index - AIQ) משמש להערכת רמת הזיהום של אוויר באזורים שונים של הארץ. מדד AIQ הוא מספר שלם נע בין 0 ל- 500. המשרד לאיכות הסביבה מפרסם כל יום "מפת זיהום ארצית" הכוללת נתונים של רמת הזיהום ביישובים שונים. לשם כך פיתחו מתכנתי המשרד מחלקה AIQData. למחלקה ארבע תכונות:

•תאריך – date, מטיפוס מחרוזת, String

•שם היישוב – city, מטיפוס מחרוזת, String

•מספר תושבים – popul, מטיפוס מספר שלם, int

•מדד איכות האוויר – aiq, מטיפוס שלם, int

אפשר להניח שקיימות פעולות get לכל התכונות של המחלקה.

א.

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

ערך AIQ0 - 4950 - 99100 - 149150 - 199200 - 500
הסברטובמתוןלא בריא לקבוצות רגישותלא בריאמסוכן
דירוג12345

כתבו פעולה פנימית במחלקה AIQData המחזירה דירוג לפי מדד איכות האוויר. כותרת הפעולה:

public int raiting()
public int Raiting()
(3 נקודות)
ב.

כתבו פעולה המקבלת מערך נתונים של איכות האוויר (מערך הפניות לעצמים מטיפוס AIQData) ותאריך מסוים checkDate. על הפעולה להדפיס שמות של כל היישובים שאיכות האוויר בתאריך זה הייתה "לא בריאה" או "מסוכנת". חובה להשתמש בפעולה שכתבתם בסעיף א'.

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

public static void printDangerous(AIQData[] arr, String checkDate)
public static void PrintDangerous(AIQData[] arr, string checkDate)
(6 נקודות)
ג.

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

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

public static void printCities(AIQData[] arr, String[] cities)
public static void PrintCities(AIQData[] arr, string[] cities)
(6 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

שרשרת תנאים על aiq: עד 49 – 1, עד 99 – 2, עד 149 – 3, עד 199 – 4, אחרת (200-500) – 5.

הרעיון: הפעולה פנימית, ולכן ניגשים ישירות לתכונה aiq של העצם. הטווחים בטבלה רצופים ולא חופפים, ולכן בודקים את הגבול העליון של כל טווח לפי הסדר: אם aiq לא עבר את 49 – הדירוג 1; אחרת, אם לא עבר את 99 – 2; וכן הלאה. כל `return` מסיים את הפעולה, כך שאין צורך לבדוק גם את הגבול התחתון. מה שנשאר אחרי 199 הוא הטווח 200–500 – דירוג 5.

בדיקת גבולות: 49 ← 1, 50 ← 2, 99 ← 2, 100 ← 3, 149 ← 3, 150 ← 4, 199 ← 4, 200 ← 5.

Java:

public int raiting()
{
    if (aiq <= 49)
        return 1;       // טוב
    if (aiq <= 99)
        return 2;       // מתון
    if (aiq <= 149)
        return 3;       // לא בריא לקבוצות רגישות
    if (aiq <= 199)
        return 4;       // לא בריא
    return 5;           // מסוכן (200-500)
}

C#:

public int Raiting()
{
    if (aiq <= 49)
        return 1;       // טוב
    if (aiq <= 99)
        return 2;       // מתון
    if (aiq <= 149)
        return 3;       // לא בריא לקבוצות רגישות
    if (aiq <= 199)
        return 4;       // לא בריא
    return 5;           // מסוכן (200-500)
}

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

סעיף ב

תשובה:

עוברים על המערך ומדפיסים את שם היישוב של כל רשומה שהתאריך שלה שווה ל-checkDate והדירוג שלה 4 או 5.

הרעיון: "לא בריא" הוא דירוג 4 ו"מסוכן" הוא דירוג 5, כלומר מחפשים רשומות עם `raiting() >= 4`. כל רשומה במערך היא מדידה של יישוב אחד בתאריך אחד, ולכן עוברים על כל הרשומות ומדפיסים את שם היישוב כשמתקיימים שני תנאים:

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

2. הדירוג שמחזירה הפעולה מסעיף א' הוא 4 או יותר.

הפעולה סטטית (מחוץ למחלקה), ולכן ניגשים לתכונות דרך פעולות ה-get.

Java:

public static void printDangerous(AIQData[] arr, String checkDate)
{
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i].getDate().equals(checkDate) && arr[i].raiting() >= 4)
            System.out.println(arr[i].getCity());
    }
}

C#:

public static void PrintDangerous(AIQData[] arr, string checkDate)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i].GetDate() == checkDate && arr[i].Raiting() >= 4)
            Console.WriteLine(arr[i].GetCity());
    }
}

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

סעיף ג

תשובה:

לכל יישוב ב-cities עוברים על כל המערך arr, סופרים רשומות של אותו יישוב עם דירוג 1 (טוב) ועם דירוג 5 (מסוכן), ומדפיסים את שני המונים.

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

סיבוכיות: אם ב-cities יש m יישובים וב-arr יש n רשומות – O(m⋅n)O(m\cdot n).

Java:

public static void printCities(AIQData[] arr, String[] cities)
{
    for (int c = 0; c < cities.length; c++)
    {
        int good = 0, danger = 0;
        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i].getCity().equals(cities[c]))
            {
                if (arr[i].raiting() == 1)          // טוב
                    good++;
                else if (arr[i].raiting() == 5)     // מסוכן
                    danger++;
            }
        }
        System.out.println(cities[c] + ": good " + good + ", dangerous " + danger);
    }
}

C#:

public static void PrintCities(AIQData[] arr, string[] cities)
{
    for (int c = 0; c < cities.Length; c++)
    {
        int good = 0, danger = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i].GetCity() == cities[c])
            {
                if (arr[i].Raiting() == 1)          // טוב
                    good++;
                else if (arr[i].Raiting() == 5)     // מסוכן
                    danger++;
            }
        }
        Console.WriteLine(cities[c] + ": good " + good + ", dangerous " + danger);
    }
}

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

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

א.

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

Java:

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

C#:

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

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

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

(2)

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

(5 נקודות)
ב.

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

Java:

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

C#:

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

נתון מערך `int [] arr = {123, -45, -678, 12, -345, 67}`.

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

(2)

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

(3)

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

(5 נקודות)
ג.

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

(3 נקודות)
ד.

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

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

סעיף א

(1)
תשובה:

{-344, -46, 12, 0, 670, 0}

הפעולה ממלאה מערך עזר temp בשני מעברים, ו-k מצביע על התא הפנוי הבא ב-temp.

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

סיבוב: iarr[i]arr[i] < 0?k אחריtemp
012לא0{}
10לא0{}
2−344-344כן1{-344}
3−46-46כן2{-344, -46}
4670לא2{-344, -46}
50לא2{-344, -46}

2. מעבר שני – רק האי-שליליים (≥0\ge 0), לפי הסדר: 12 (k=3), 0 (k=4), 670 (k=5), 0 (k=6). עכשיו temp = {-344, -46, 12, 0, 670, 0}.

3. מעבר שלישי: מעתיקים את temp חזרה ל-arr.

תשובה: arr = {-344, -46, 12, 0, 670, 0}.

(2)
תשובה:

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

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

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

סעיף ב

(1)
תשובה:

{-345, -45, -678, 12, 123, 67}

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

מצביע startendarr[start]arr[end]פעולההמערך
051236767≥067\ge 0: end--{123, -45, -678, 12, -345, 67}
04123−345-345החלפה{-345, -45, -678, 12, 123, 67}
04−345-345123−345<0-345<0: start++ללא שינוי
14−45-45123−45<0-45<0: start++ללא שינוי
24−678-678123−678<0-678<0: start++ללא שינוי
3412123123≥0123\ge 0: end--ללא שינוי
33––start<endstart<end לא מתקיים, יציאה{-345, -45, -678, 12, 123, 67}

תשובה: arr = {-345, -45, -678, 12, 123, 67}.

(2)
תשובה:

למשל brr = {-5, -3, 1, 2, 4} (כל השליליים לפני כל האי-שליליים).

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

ניקח brr = {-5, -3, 1, 2, 4}: start מתקדם על −5-5 ו-−3-3 עד start=2start=2 (הערך 1); אז end נסוג על 4 ו-2 עד end=2end=2, התנאי start<endstart<end כבר לא מתקיים והלולאה נגמרת – בלי אף החלפה.

תשובה: למשל brr = {-5, -3, 1, 2, 4} (גם מערך שכולו שליליים או שכולו אי-שליליים מתאים).

(3)
תשובה:

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

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

בניגוד ל-why, החלוקה נעשית "במקום" (בלי מערך עזר), אבל הסדר בתוך כל קבוצה עלול להשתנות – בסעיף 1 ה-123 עבר ממקום 0 למקום 4, אחרי ה-12, וה-−345-345 עבר לפני ה-−45-45.

תשובה: what מחלקת את המערך – שליליים בתחילתו ואי-שליליים בסופו – בעזרת החלפות, בלי מערך עזר ובלי לשמור על הסדר המקורי.

סעיף ג

תשובה:

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

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

1. why מעתיקה את השליליים לפי הסדר ואחריהם את האי-שליליים לפי הסדר – בדיוק המערך המקורי.

2. what אינה מבצעת אף החלפה (כמו בסעיף ב2) – המערך נשאר כמו שהוא.

לכן, למשל, עבור crr = {-1, -2, 3, 4, 5, 6} שתי הפעולות משאירות את המערך {-1, -2, 3, 4, 5, 6}.

תשובה: כן, למשל crr = {-1, -2, 3, 4, 5, 6} (כל מערך שבו השליליים כבר לפני האי-שליליים).

סעיף ד

תשובה:

שתיהן O(n)O(n).

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

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

תשובה: סיבוכיות זמן הריצה של שתי הפעולות היא O(n)O(n), כאשר n אורך המערך.

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

א.

נתונה מחרוזת s="aMrAdDYrM". עקבו בעזרת טבלת המעקב אחרי זימון הפעולה why(s) ורשמו מהי תוצאת הזימון.

Java:

public static boolean why(String s)
{
  while(s.length() > 1)
   {
    if(s.charAt(0)<'A' || s.charAt(0)>'Z')
     {
      s = s.substring(1);
     }
    else
     if(s.charAt(s.length()-1)<'A' || s.charAt(s.length()-1)>'Z')
      {
       s = s.substring(0,s.length()-1);
      }
     else
      {
       if(s.charAt(0)!=s.charAt(s.length()-1)) return false;
       s = s.substring(1, s.length()-1);
      }
   }
  return true;
}

C#:

public static bool Why(string  s)
{
  while(s.Length > 1)
   {
    if(s[0]<'A' || s[0]>'Z')
     {
      s = s.Substring(1);
     }
    else
     if(s[s.Length-1]<'A' || s[s.Length-1]>'Z')
      {
       s = s.Substring(0,s.Length-1);
      }
     else
      {
       if(s[0]!=s[s.Length-1]) return false;
       s = s.Substring(1, s.Length-2);
      }
   }
  return true;
}
(8 נקודות)
ב.

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

Java:

public static boolean what(String s)
{
   while(s.length() > 1)
    {
      if(s.charAt(0) != s.charAt(s.length()-1)) return false;
      s = s.substring(1, s.length()-1);
    }
   return true;
}

C#:

public static bool What(string  s)
{
   while(s.Length > 1)
    {
      if(s[0] != s[s.Length-1]) return false;
      s = s.Substring(1, s.Length-1);
    }
   return true;
}

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

(4 נקודות)
ג.

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

Java:

public static boolean where(String s)
{
  String str = "";
  for(int i = 0; i < s.length(); i++)
      if(s.charAt(i)>='A' && s.charAt(i)<='Z') str += s.charAt(i);

  return what(str);
}

C#:

public static bool Where(string  s)
{
  string  str = "";
  for(int i = 0; i < s.Length; i++)
      if(s[i]>='A' && s[i]<='Z') str += s[i];

  return What(str);
}

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

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

סעיף א

תשובה:

why("aMrAdDYrM") מחזירה false.

בכל סיבוב הפעולה בודקת את התו הראשון והאחרון: אם התו הראשון אינו אות גדולה (מחוץ לטווח 'A'–'Z') – מוחקים אותו; אחרת, אם האחרון אינו אות גדולה – מוחקים אותו; ואם שניהם אותיות גדולות – משווים ביניהם: אם הם שונים מחזירים false, ואם שווים מוחקים את שניהם. (ב-C# `s.Substring(1, s.Length-2)` – תת-מחרוזת באורך Length−2Length-2 ממקום 1 – היא בדיוק המחרוזת בלי התו הראשון והאחרון, כמו `s.substring(1, s.length()-1)` ב-Java.)

סיבובsאורךתו ראשוןתו אחרוןפעולה
1aMrAdDYrM9a (לא גדולה)Mמוחקים את התו הראשון
2MrAdDYrM8MMשתיהן גדולות ושוות – מוחקים את שתיהן
3rAdDYr6r (לא גדולה)rמוחקים את התו הראשון
4AdDYr5Ar (לא גדולה)מוחקים את התו האחרון
5AdDY4AYשתיהן גדולות ו-A ≠ Y – מחזירים false

תשובה: תוצאת הזימון why(s) היא false.

סעיף ב

תשובה:

Java: כל פלינדרום באורך 6, למשל "ABCCBA". בגרסת C# הפעולה מחזירה true רק כשכל התווים שווים, למשל "AAAAAA" (מחרוזת זו מתאימה לשתי הגרסאות).

גרסת Java: בכל סיבוב משווים את התו הראשון לאחרון; אם הם שונים מחזירים false, ואם שווים מוחקים את שניהם (`substring(1, s.length()-1)`) וממשיכים פנימה. הפעולה מחזירה true בדיוק כשהמחרוזת היא פלינדרום (נקראת אותו דבר משני הכיוונים).

דוגמה: s="ABCCBA":

1. A = A ← s="BCCB"

2. B = B ← s="CC"

3. C = C ← s="" (אורך 0), הלולאה נגמרת ומוחזר true.

גרסת C#: בשאלון ה-C# כתוב `s.Substring(1, s.Length-1)`, וב-C# הפרמטר השני הוא אורך תת-המחרוזת. לכן זו המחרוזת בלי התו הראשון בלבד – התו האחרון נשאר. בכל סיבוב משווים את התו הראשון של הסיפא הנוכחית לאותו תו אחרון, ולכן What מחזירה true רק אם כל התווים במחרוזת שווים. עבור "ABCCBA" גרסת C# מחזירה false (בסיבוב השני B ≠ A). דוגמה שמתאימה לה: "AAAAAA" – בכל סיבוב A = A, עד שנשאר תו אחד ומוחזר true. מחרוזת זו היא גם פלינדרום, ולכן מתאימה גם לגרסת Java.

תשובה: למשל s="AAAAAA" (מחזירה true בשתי הגרסאות); בגרסת Java מתאים כל פלינדרום באורך 6, למשל "ABCCBA".

סעיף ג

תשובה:

Java: כן – שתיהן בודקות אם רצף האותיות הגדולות במחרוזת (לפי הסדר) הוא פלינדרום. בגרסת C# הן אינן שקולות: עבור s="ABA" Why מחזירה true ו-Where מחזירה false.

גרסת Java – כן, הפעולות שקולות.

1. where: מעתיקה ל-str רק את האותיות הגדולות של s, לפי הסדר, ומזמנת את what – כלומר בודקת אם רצף האותיות הגדולות הוא פלינדרום.

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

למשל עבור "aMrAdDYrM" רצף האותיות הגדולות הוא "MADYM", שאינו פלינדרום (A ≠ Y), ושתי הפעולות מחזירות false (כמו בסעיף א'). עבור "xAbBA" הרצף "ABA" הוא פלינדרום ושתיהן מחזירות true.

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

גרסת C# – לא שקולות. Why זהה לגרסת Java (בודקת פלינדרום של האותיות הגדולות), אבל Where מזמנת את What של C#, שכפי שראינו בסעיף ב' בודקת אם כל התווים שווים. לכן עבור s="ABA":

•Why("ABA"): A = A ← s="B" – מוחזר true.

•Where("ABA"): str="ABA", ו-What("ABA"): A = A ← s="BA"; B ≠ A ← מוחזר false.

תשובה (C#): לא; למשל עבור s="ABA" Why מחזירה true ו-Where מחזירה false.

שאלה 12 · מספר מאוזן ומערך דו-ממדי סופר מאוזן

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

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

לדוגמה:

המספרים 121, 134, 41111, 2334 הם "מספרים מאוזנים".

המספרים 43, 186, -121, 35 הם לא "מספרים מאוזנים".

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

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

א.

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

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

(8 נקודות)
ב.

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

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

סעיף א

תשובה:

שלוש פעולות: isBalancedNum (חיובי וסכום הספרות הזוגיות = סכום האי-זוגיות), isBalancedEdges (המקסימום והמינימום של שורה מאוזנים), isSuperBalanced (כל השורות מאוזנות בקצוות).

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

1. isBalancedNum(num) – מספר מאוזן. "ספרות זוגיות" הן ספרות שערכן זוגי (0, 2, 4, 6, 8), כפי שעולה מהדוגמאות: ב-134 הספרה הזוגית 4 והאי-זוגיות 1+3=41+3=4. מפרקים את המספר לספרות ומוסיפים כל ספרה לצובר המתאים לזוגיותה; המספר מאוזן אם הצוברים שווים. מספר שאינו חיובי (0 או שלילי, כמו −121-121 בדוגמה) אינו מאוזן לפי ההגדרה, ולכן מחזירים עבורו false. בדיקה: 2334 – זוגיות 2+4=62+4=6, אי-זוגיות 3+3=63+3=6 ✓; 43 – 4≠34\ne 3 ✗.

2. isBalancedEdges(arr) – מערך מאוזן בקצוות. מוצאים במעבר אחד את הערך הגדול ביותר ואת הקטן ביותר, ומחזירים true רק אם שניהם מספרים מאוזנים. שימו לב שאם בשורה יש מספר שלילי או 0, הוא עלול להיות המינימום – ואז השורה אינה מאוזנת בקצוות.

3. isSuperBalanced(mat) – מערך דו-ממדי סופר מאוזן. עוברים על השורות; אם שורה כלשהי אינה מאוזנת בקצוות מחזירים false מיד, ואם כולן מאוזנות – true. ב-Java כל שורה `mat[i]` היא מערך חד-ממדי ואפשר להעביר אותה ישירות; ב-C# במערך מלבני `int[,]` מעתיקים את השורה למערך עזר.

דוגמה: עבור המערך שבו השורות {121, 500, 2334} ו-{134, 2334, 41111}: בשורה הראשונה המקסימום 2334 והמינימום 121 – שניהם מאוזנים; בשורה השנייה המקסימום 41111 והמינימום 134 – מאוזנים. התוצאה true. אם בשורה השנייה 41111 מוחלף ב-43, המינימום הוא 43, שאינו מאוזן, והתוצאה false.

Java:

// מספר מאוזן: סכום הספרות הזוגיות שווה לסכום הספרות האי-זוגיות
public static boolean isBalancedNum(int num)
{
    if (num <= 0)
        return false;           // רק מספר שלם וחיובי יכול להיות מאוזן
    int evenSum = 0, oddSum = 0;
    while (num > 0)
    {
        int d = num % 10;
        if (d % 2 == 0)
            evenSum += d;
        else
            oddSum += d;
        num /= 10;
    }
    return evenSum == oddSum;
}

// מערך מאוזן בקצוות: המקסימום והמינימום הם מספרים מאוזנים
public static boolean isBalancedEdges(int[] arr)
{
    int max = arr[0], min = arr[0];
    for (int i = 1; i < arr.length; i++)
    {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }
    return isBalancedNum(max) && isBalancedNum(min);
}

// סופר מאוזן: כל השורות מאוזנות בקצוות
public static boolean isSuperBalanced(int[][] mat)
{
    for (int i = 0; i < mat.length; i++)
    {
        if (!isBalancedEdges(mat[i]))
            return false;
    }
    return true;
}

C#:

// מספר מאוזן: סכום הספרות הזוגיות שווה לסכום הספרות האי-זוגיות
public static bool IsBalancedNum(int num)
{
    if (num <= 0)
        return false;           // רק מספר שלם וחיובי יכול להיות מאוזן
    int evenSum = 0, oddSum = 0;
    while (num > 0)
    {
        int d = num % 10;
        if (d % 2 == 0)
            evenSum += d;
        else
            oddSum += d;
        num /= 10;
    }
    return evenSum == oddSum;
}

// מערך מאוזן בקצוות: המקסימום והמינימום הם מספרים מאוזנים
public static bool IsBalancedEdges(int[] arr)
{
    int max = arr[0], min = arr[0];
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }
    return IsBalancedNum(max) && IsBalancedNum(min);
}

// סופר מאוזן: כל השורות מאוזנות בקצוות
public static bool IsSuperBalanced(int[,] mat)
{
    for (int i = 0; i < mat.GetLength(0); i++)
    {
        int[] row = new int[mat.GetLength(1)];      // מעתיקים את שורה i
        for (int j = 0; j < row.Length; j++)
            row[j] = mat[i, j];
        if (!IsBalancedEdges(row))
            return false;
    }
    return true;
}

תשובה: הפעולה isSuperBalanced (עם פעולות העזר isBalancedEdges ו-isBalancedNum) שלמעלה.

סעיף ב

תשובה:

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

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

1. isBalancedNum: מספר הסיבובים הוא מספר הספרות, ולמספר int יש לכל היותר 10 ספרות – O(1)O(1).

2. isBalancedEdges: מעבר אחד על השורה למציאת מקסימום ומינימום – O(m)O(m), ועוד שתי בדיקות של O(1)O(1).

3. isSuperBalanced: במקרה הגרוע (כל השורות מאוזנות) קוראים ל-isBalancedEdges עבור כל אחת מ-n השורות: n⋅O(m)n\cdot O(m).

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

שאלה 13 · מחלקות תאריך, נוסע וטיול

חברת "טיולי עם" מארגנת טיולים ליעדים שונים בעולם. למערכת הממוחשבת של החברה יש שלוש מחלקות: Date, Traveler, Travel.

המחלקה Date מציינת תאריך. למחלקה יש שלוש תכונות:

day – יום, month – חודש, year – שנה.

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

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

public boolean before(Date other)
public bool Before(Date other)

המחלקה Traveler מייצגת נוסע. למחלקה יש את התכונות הבאות:

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

•תאריך התפוגה של הדרכון – expireDate – מטיפוס תאריך, Date

•יעד הנסיעה הרצוי – destination – מטיפוס מחרוזת, String

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

למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות.

א.

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

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

public boolean canGo(Date start, int price, String dest)
public bool CanGo(Date start, int price, string  dest)
(3 נקודות)

המחלקה Travel מייצגת טיול. למחלקה ארבע תכונות:

•יעד הטיול – destination, מטיפוס מחרוזת, String

•מערך נרשמים לטיול – travelers, מערך הפניות לעצמים מטיפוס Traveler

•מחיר הטיול – price, מטיפוס מספר שלם, int

•תאריך היציאה לטיול – startDate, מטיפוס תאריך, Date

למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות.

ב.

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

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

public void notValidNames()
public void NotValidNames()
(4 נקודות)
ג.

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

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

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

public boolean isGuaranted(int minNum)
public bool IsGuaranted(int minNum)
(4 נקודות)
◂ פתרון מלא לשאלה 13

סעיף א

תשובה:

פעולה פנימית ב-Traveler: מחזירה true אם התפוגה אינה לפני start (!expireDate.before(start)), destination שווה ל-dest, ו-payment*2 >= price.

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

1. הדרכון בתוקף בתאריך היציאה: הדרכון פג אם תאריך התפוגה הוא לפני תאריך היציאה, כלומר `expireDate.before(start)`. לכן התנאי הוא השלילה שלו: `!expireDate.before(start)`. משתמשים בפעולה before שהוגדרה במחלקה Date. (אם תאריך התפוגה הוא בדיוק יום היציאה – הדרכון עדיין בתוקף באותו יום.)

2. היעד: היעד הרצוי של הנוסע שווה ליעד הטיול – השוואת מחרוזות: ב-Java `destination.equals(dest)`, ב-C# `destination == dest`.

3. מקדמה של לפחות חצי: payment≥price2payment\ge\frac{price}{2}. כדי להימנע מחילוק שלמים (למשל 50012=2500\frac{5001}{2}=2500 בחילוק שלמים), כותבים את התנאי השקול 2⋅payment≥price2\cdot payment\ge price.

Java:

// במחלקה Traveler
public boolean canGo(Date start, int price, String dest)
{
    boolean validPassport = !this.expireDate.before(start);   // הדרכון לא פג לפני היציאה
    boolean sameDest = this.destination.equals(dest);         // היעד הרצוי = יעד הטיול
    boolean paidHalf = this.payment * 2 >= price;              // שילם לפחות חצי
    return validPassport && sameDest && paidHalf;
}

C#:

// במחלקה Traveler
public bool CanGo(Date start, int price, string dest)
{
    bool validPassport = !this.expireDate.Before(start);      // הדרכון לא פג לפני היציאה
    bool sameDest = this.destination == dest;                 // היעד הרצוי = יעד הטיול
    bool paidHalf = this.payment * 2 >= price;                 // שילם לפחות חצי
    return validPassport && sameDest && paidHalf;
}

תשובה: הפעולה canGo שלמעלה, במחלקה Traveler.

סעיף ב

תשובה:

פעולה פנימית ב-Travel: עוברת על travelers ומדפיסה את שם כל נוסע שתאריך התפוגה שלו לפני startDate.

הרעיון: הפעולה פנימית במחלקה Travel, ולכן יש לה גישה ישירה למערך travelers ולתאריך startDate של הטיול. עבור כל נרשם מקבלים את תאריך התפוגה שלו בעזרת `getExpireDate()` (התכונה פרטית למחלקה Traveler), ובודקים בעזרת before אם הוא לפני תאריך היציאה – זה בדיוק המקרה שבו הדרכון אינו בתוקף (ההפך מהתנאי בסעיף א'). במקרה כזה מדפיסים את השם בעזרת `getName()`.

אם המערך אינו מלא עד הסוף (יש בו תאים ריקים), הבדיקה `travelers[i] != null` מונעת שגיאה.

Java:

// במחלקה Travel
public void notValidNames()
{
    for (int i = 0; i < travelers.length; i++)
    {
        if (travelers[i] != null && travelers[i].getExpireDate().before(this.startDate))
            System.out.println(travelers[i].getName());
    }
}

C#:

// במחלקה Travel
public void NotValidNames()
{
    for (int i = 0; i < travelers.Length; i++)
    {
        if (travelers[i] != null && travelers[i].GetExpireDate().Before(this.startDate))
            Console.WriteLine(travelers[i].GetName());
    }
}

תשובה: הפעולה notValidNames שלמעלה, במחלקה Travel.

סעיף ג

תשובה:

פעולה פנימית ב-Travel: סופרת את הנרשמים ש-canGo(startDate, price, destination) מחזירה עבורם true, ומחזירה count >= minNum.

הרעיון: נוסע "יכול לצאת לטיול" בדיוק כשהפעולה canGo מסעיף א' מחזירה true עבור הנתונים של הטיול הזה: תאריך היציאה `startDate`, המחיר `price` והיעד `destination` – כולם תכונות של העצם Travel שמפעיל את הפעולה.

1. מאפסים מונה count.

2. עוברים על כל הנרשמים, ולכל נרשם מזמנים `travelers[i].canGo(startDate, price, destination)`; אם התשובה true מגדילים את count.

3. הטיול מובטח אם יש לפחות minNum כאלה: מחזירים `count >= minNum`.

Java:

// במחלקה Travel
public boolean isGuaranted(int minNum)
{
    int count = 0;
    for (int i = 0; i < travelers.length; i++)
    {
        if (travelers[i] != null && travelers[i].canGo(this.startDate, this.price, this.destination))
            count++;
    }
    return count >= minNum;
}

C#:

// במחלקה Travel
public bool IsGuaranted(int minNum)
{
    int count = 0;
    for (int i = 0; i < travelers.Length; i++)
    {
        if (travelers[i] != null && travelers[i].CanGo(this.startDate, this.price, this.destination))
            count++;
    }
    return count >= minNum;
}

תשובה: הפעולה isGuaranted שלמעלה, במחלקה Travel.

שאלה 14 · רקורסיה: זוגות עם סכום והפרש נתונים

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

Java:

public static boolean what(int[] arr, int num)
{
    return what(arr, num, 0,arr.length-1, false);
}
public static boolean what(int[] arr, int num, int i, int k,
                           boolean f)
{
    if(i >= k) return f;
    if(arr[i] + arr[k] < num)
        return what(arr, num, i+1,k,f);
    if(arr[i] + arr[k] > num)
        return what(arr, num, i,k-1,f);
    System.out.println(arr[i]+ " " + arr[k]);
    return what(arr, num, i+1, k-1, true);
}

C#:

public static bool What(int[] arr, int num)
{
    return What(arr, num, 0,arr.Length-1, false);
}
public static bool What(int[] arr, int num, int i, int k,
                           bool f)
{
    if(i >= k) return f;
    if(arr[i] + arr[k] < num)
        return What(arr, num, i+1,k,f);
    if(arr[i] + arr[k] > num)
        return What(arr, num, i,k-1,f);
    Console.WriteLine(arr[i]+ " " + arr[k]);
    return What(arr, num, i+1, k-1, true);
}
א.

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

int[] a={2,4,7,13,18,21,30};

עקבו אחרי זימון what(a, 20) רשמו את תוצאת הזימון. יש להראות מעקב!

(4 נקודות)
ב.

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

(2 נקודות)

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

Java:

public static int why(int[] arr, int num)
{
    return why(arr, num, 0,1, 0);
}
public static int why(int[] arr, int num, int i, int k, int f)
{
    if(i == arr.length-1)return f;
    if(k == arr.length)return f;
    if(arr[k] - arr[i] < num)
        return why(arr, num, i, k+1, f);
    if(arr[k] - arr[i] > num)
        return why(arr, num, i+1, k, f);
    System.out.println(arr[i]+" " + arr[k]);
    return why(arr, num, i+1,k+1, f+1);
}

C#:

public static int Why(int[] arr, int num)
{
    return Why(arr, num, 0,1, 0);
}
public static int Why(int[] arr, int num, int i, int k, int f)
{
    if(i == arr.Length-1)return f;
    if(k == arr.Length)return f;
    if(arr[k] - arr[i] < num)
        return Why(arr, num, i, k+1, f);
    if(arr[k] - arr[i] > num)
        return Why(arr, num, i+1, k, f);
    Console.WriteLine(arr[i]+" " + arr[k]);
    return Why(arr, num, i+1,k+1, f+1);
}
ג.

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

int[] a={2,4,7,13,18,21,30};

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

(3 נקודות)
ד.

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

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

סעיף א

תשובה:

יודפס "2 18" ואחריו "7 13", והזימון מחזיר true.

i מתחיל בתחילת המערך ו-k בסופו. בכל זימון: אם i≥ki\ge k מחזירים את f; אם הסכום a[i]+a[k]a[i]+a[k] קטן מ-20 מקדמים את i (צריך מספר גדול יותר); אם הסכום גדול מ-20 מורידים את k; ואם הוא שווה ל-20 מדפיסים את הזוג וממשיכים עם i+1i+1, k−1k-1 ו-f=truef=true.

המערך: a[0..6]a[0..6] = 2, 4, 7, 13, 18, 21, 30.

זימוןikfa[i]a[k]a[i]+a[k]פעולה
106false2303232>2032>20: k-1
205false2212323>2023>20: k-1
304false21820שווה: הדפסה "2 18", i+1, k-1, f=true
413true4131717<2017<20: i+1
523true71320שווה: הדפסה "7 13", i+1, k-1, f=true
632true–––i≥ki\ge k: מחזירים true

הערך true חוזר דרך כל הזימונים עד הזימון הראשון.

פלט:

2 18
7 13

תשובה: יודפסו הזוגות "2 18" ו-"7 13", ותוצאת הזימון היא true.

סעיף ב

תשובה:

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

זו שיטת "שני המצביעים" על מערך ממוין: i מתקדם מההתחלה ו-k נסוג מהסוף. כשהסכום קטן מדי, הגדלת i מגדילה אותו; כשהסכום גדול מדי, הקטנת k מקטינה אותו. כך עוברים על כל הזוגות האפשריים שסכומם num, ומדפיסים כל זוג שנמצא. הפרמטר f מתחיל ב-false והופך ל-true ברגע שנמצא זוג ראשון, וזה הערך שמוחזר בסוף.

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

סעיף ג

תשובה:

כן. למשל num=3: יודפסו "4 7" ו-"18 21" והזימון יחזיר 2.

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

ההפרשים בין איברים סמוכים: 4−2=24-2=2, 7−4=37-4=3, 13−7=613-7=6, 18−13=518-13=5, 21−18=321-18=3, 30−21=930-21=9. ההפרש 3 מופיע פעמיים: 7−4=37-4=3 ו-21−18=321-18=3, ואין זוג נוסף שהפרשו 3 (שאר ההפרשים גדולים מ-3 או שווים ל-2). ניקח num=3num=3 ונעקוב:

זימוןikfa[i]a[k]a[k]-a[i]פעולה
10102422<32<3: k+1
20202755>35>3: i+1
3120473שווה: הדפסה "4 7", i+1, k+1, f=1
423171366>36>3: i+1
5331131300<30<3: k+1
6341131855>35>3: i+1
7441181800<30<3: k+1
845118213שווה: הדפסה "18 21", i+1, k+1, f=2
9562213099>39>3: i+1
10662–––i=arr.length−1i=arr.length-1: מחזירים 2

פלט:

4 7
18 21

(גם num=5num=5, 9, 11, 14 או 17 מתאימים – לכל אחד מהם בדיוק שני זוגות.)

תשובה: כן, למשל num=3: יודפסו "4 7" ו-"18 21" והזימון יחזיר 2.

סעיף ד

תשובה:

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

גם כאן יש שני מצביעים, אבל שניהם נעים קדימה: i על האיבר הקטן ו-k על הגדול. אם ההפרש arr[k]−arr[i]arr[k]-arr[i] קטן מ-num מקדמים את k (מגדילים את ההפרש); אם הוא גדול מ-num מקדמים את i (מקטינים את ההפרש); ואם הוא שווה – מדפיסים את הזוג, מקדמים את שניהם ומגדילים את המונה f. הרקורסיה נעצרת כש-i מגיע לאיבר האחרון או ש-k יוצא מהמערך, ומוחזר f.

תשובה: why מדפיסה את כל זוגות האיברים שההפרש ביניהם שווה ל-num ומחזירה כמה זוגות כאלה נמצאו.

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

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

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