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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · זוגות מספרים: ספירת דו-ספרתיים וסכום זוגיים

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

על התוכנית לחשב ולהדפיס:

•את כמות המספרים הדו-ספרתיים שנקלטו.

•את סכום כל המספרים הזוגיים שנקלטו.

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

פתרון

תשובה:

לולאה של 20 סיבובים, בכל סיבוב קולטים שני מספרים; מונה למספרים בין 10 ל-99 וצובר למספרים זוגיים, ובסוף מדפיסים את שניהם.

נתון: 20 זוגות של מספרים שלמים חיוביים, כלומר 40 מספרים. מבוקש: כמה מהם דו-ספרתיים, ומה סכום הזוגיים שבהם.

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

1. מונה `countTwoDigit` מתחיל ב-0. מספר חיובי הוא דו-ספרתי אם הוא בין 10 ל-99 (כולל), ואז מגדילים את המונה ב-1.

2. צובר `sumEven` מתחיל ב-0. מספר זוגי אם השארית שלו בחלוקה ב-2 היא 0 (`a % 2 == 0`), ואז מוסיפים אותו לצובר.

3. שתי הבדיקות נפרדות (שני `if` ולא `else`), כי מספר יכול להיות גם דו-ספרתי וגם זוגי (למשל 12) – ואז הוא נספר במונה וגם נצבר בסכום.

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

Java:

Scanner in = new Scanner(System.in);
int countTwoDigit = 0;   // כמות המספרים הדו-ספרתיים
int sumEven = 0;         // סכום המספרים הזוגיים
for (int i = 0; i < 20; i++)
{
    int a = in.nextInt();   // המספר הראשון בזוג
    int b = in.nextInt();   // המספר השני בזוג
    if (a >= 10 && a <= 99)
        countTwoDigit++;
    if (b >= 10 && b <= 99)
        countTwoDigit++;
    if (a % 2 == 0)
        sumEven += a;
    if (b % 2 == 0)
        sumEven += b;
}
System.out.println("Two-digit numbers: " + countTwoDigit);
System.out.println("Sum of even numbers: " + sumEven);

C#:

int countTwoDigit = 0;   // כמות המספרים הדו-ספרתיים
int sumEven = 0;         // סכום המספרים הזוגיים
for (int i = 0; i < 20; i++)
{
    int a = int.Parse(Console.ReadLine());   // המספר הראשון בזוג
    int b = int.Parse(Console.ReadLine());   // המספר השני בזוג
    if (a >= 10 && a <= 99)
        countTwoDigit++;
    if (b >= 10 && b <= 99)
        countTwoDigit++;
    if (a % 2 == 0)
        sumEven += a;
    if (b % 2 == 0)
        sumEven += b;
}
Console.WriteLine("Two-digit numbers: " + countTwoDigit);
Console.WriteLine("Sum of even numbers: " + sumEven);

דוגמה: אם הזוגות הראשונים הם (5, 12), (10, 99), (100, 9) – הדו-ספרתיים הם 12, 10, 99 (שלושה), והזוגיים 12, 10, 100 (סכום 122).

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

שאלה 2 · קליטת מחרוזות עד אורך אי-זוגי

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

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

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

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

פתרון

תשובה:

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

נתון: סדרת מחרוזות שמסתיימת במחרוזת באורך אי-זוגי. מבוקש: לכל מחרוזת – הודעה אם יש בה 'Z'; ובסוף – כמה מחרוזות מתחילות ומסתיימות באותו תו.

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

1. בדיקת 'Z': הפעולה `indexOf('Z')` מחזירה את המקום הראשון של 'Z' במחרוזת, או 1- אם התו לא מופיע. לפי זה מדפיסים אחת משתי הודעות.

2. התו הראשון והאחרון: התו הראשון נמצא במקום 0 והאחרון במקום `length-1`. אם הם שווים – מגדילים את המונה `countSame`.

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

4. מניחים שהמחרוזות אינן ריקות (למחרוזת ריקה אין תו ראשון).

Java:

Scanner in = new Scanner(System.in);
int countSame = 0;              // מחרוזות שמתחילות ומסתיימות באותו תו
String str = in.next();
while (str.length() % 2 == 0)   // ממשיכים כל עוד האורך זוגי
{
    if (str.indexOf('Z') != -1)
        System.out.println(str + " contains Z");
    else
        System.out.println(str + " does not contain Z");
    if (str.charAt(0) == str.charAt(str.length() - 1))
        countSame++;
    str = in.next();
}
System.out.println("Same first and last char: " + countSame);

C#:

int countSame = 0;              // מחרוזות שמתחילות ומסתיימות באותו תו
string str = Console.ReadLine();
while (str.Length % 2 == 0)     // ממשיכים כל עוד האורך זוגי
{
    if (str.IndexOf('Z') != -1)
        Console.WriteLine(str + " contains Z");
    else
        Console.WriteLine(str + " does not contain Z");
    if (str[0] == str[str.Length - 1])
        countSame++;
    str = Console.ReadLine();
}
Console.WriteLine("Same first and last char: " + countSame);

דוגמה: עבור הקלט abZb, abca, ZZ, xy, abc – יודפס ש-abZb ו-ZZ מכילות Z, ו-abca ו-xy לא; המחרוזות abca ו-ZZ מתחילות ומסתיימות באותו תו, ולכן יודפס 2. המחרוזת abc (אורך 3) מסיימת את הקלט.

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

שאלה 3 · מספרים אקראיים: השכיח ביותר ומספרים שלא נוצרו

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

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

•אילו מספרים לא נוצרו.

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

פתרון

תשובה:

מערך מונים count בגודל 100 (count[x] = מספר הפעמים שנוצר x); מגרילים 40 מספרים בין 10 ל-99 ומגדילים את המונה; מחפשים את המיקום עם המונה המרבי ומדפיסים את כל x שהמונה שלו 0.

נתון: 40 מספרים אקראיים בין 10 ל-99. מבוקש: המספר שנוצר הכי הרבה פעמים, ורשימת המספרים שלא נוצרו כלל.

הרעיון: מערך מונים. יש רק 90 ערכים אפשריים (10 עד 99), ולכן נוח להחזיק מערך `count` בגודל 100 שבו התא `count[x]` סופר כמה פעמים נוצר המספר x (התאים 0-9 לא בשימוש). כך אין צורך לשמור את 40 המספרים עצמם.

1. הגרלה: מספר דו-ספרתי חיובי הוא בין X=10X=10 ל-Y=99Y=99. לפי ההנחיות: `10 + rand.nextInt(99 - 10 + 1)`, כלומר `10 + rand.nextInt(90)` (ב-C#: `rand.Next(10, 100)`). אחרי כל הגרלה מגדילים את `count[num]` ב-1.

2. השכיח ביותר: מחפשים מקסימום על המונים. מתחילים מ-`maxNum = 10` ועוברים על 11 עד 99; אם `count[x]` גדול (ממש) מהמונה של `maxNum` – מעדכנים. כשיש כמה מספרים עם אותו מונה מרבי נשאר הראשון מביניהם, וזה מותר לפי השאלה.

3. מספרים שלא נוצרו: עוברים שוב על 10 עד 99 ומדפיסים כל x שהמונה שלו 0.

4. מכיוון שיש 90 ערכים אפשריים ורק 40 הגרלות, לפחות 50 מספרים בוודאות לא ייווצרו.

Java:

Random rand = new Random();
int[] count = new int[100];          // count[x] = כמה פעמים נוצר המספר x
for (int i = 0; i < 40; i++)
{
    int num = 10 + rand.nextInt(90); // מספר אקראי בין 10 ל-99
    count[num]++;
}
int maxNum = 10;                     // המספר שנוצר הכי הרבה פעמים עד כה
for (int x = 11; x <= 99; x++)
    if (count[x] > count[maxNum])
        maxNum = x;
System.out.println("Most frequent: " + maxNum);
System.out.println("Not generated:");
for (int x = 10; x <= 99; x++)
    if (count[x] == 0)
        System.out.print(x + " ");

C#:

Random rand = new Random();
int[] count = new int[100];          // count[x] = כמה פעמים נוצר המספר x
for (int i = 0; i < 40; i++)
{
    int num = rand.Next(10, 100);    // מספר אקראי בין 10 ל-99
    count[num]++;
}
int maxNum = 10;                     // המספר שנוצר הכי הרבה פעמים עד כה
for (int x = 11; x <= 99; x++)
    if (count[x] > count[maxNum])
        maxNum = x;
Console.WriteLine("Most frequent: " + maxNum);
Console.WriteLine("Not generated:");
for (int x = 10; x <= 99; x++)
    if (count[x] == 0)
        Console.Write(x + " ");

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

שאלה 4 · מחלקת מנה: החלפת מנות ומבצע זוגות

המסעדה "Chef4U" מציעה משלוח מנות שף קטנות במחיר מוזל עד לבית הלקוח.

המחלקה Food מייצגת מנה. למחלקה 4 תכונות:

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

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

•מנה חלבית – isMilk, מטיפוס בוליאני, boolean (true – מנה חלבית, false – לא).

•דירוג המנה – raiting, מטיפוס מספר שלם. דירוג המנה הוא מספר שלם מ- 1 (הכי נמוך) עד 10 (הכי גבוה) למחלקה הוגדרו פעולה בונה (constructor), פעולות get/set והפעולה toString.

א.

לפעמים המסעדה נאלצת להחליף את המנה הנוכחית (this) למנה אחרת other.

אפשר להחליף בין המנות אם שתיהן מאותו סוג (חלבי או לא), יש להן אותו הדירוג ומחיר המנה other לא גבוה ממחיר של המנה this.

כתבו פעולה המקבלת מנה אחרת (הפנייה לעצם מטיפוס Food). הפעולה תבדוק אם ניתן להחליף מנה this למנה other. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false. כותרת הפעולה:

Java:

public boolean canChange(Food other)

C#:

public bool CanChange(Food other)
(3 נקודות)
ב.

כתבו פעולה המקבלת מערך מנות arr ומנה newFood. הפעולה תדפיס את שמות כל המנות שאפשר להחליף אותן למנה newFood. כותרת הפעולה:

Java:

public static void changes(Food[] arr, Food newFood)

C#:

public static void Changes(Food[] arr, Food newFood)
(3 נקודות)
ג.

המסעדה הכריזה על מבצע: שתי מנות שונות בפחות מ- 100 ₪.

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

Java:

public static void offers(Food[] arr)

C#:

public static void Offers(Food[] arr)
(4 נקודות)
ד.

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

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

סעיף א

תשובה:

מחזירים true אם ורק אם this.isMilk == other.isMilk, this.raiting == other.raiting וגם other.price <= this.price.

נתון: שתי מנות – this ו-other. מבוקש: האם מותר להחליף את this ב-other.

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

1. אותו סוג: `this.isMilk == other.isMilk` (שתיהן חלביות או שתיהן לא).

2. אותו דירוג: `this.raiting == other.raiting`.

3. מחיר other לא גבוה ממחיר this: `other.price <= this.price` (מחיר שווה מותר).

הפעולה כתובה בתוך המחלקה Food, ולכן מותר לגשת ישירות לתכונות הפרטיות של other. ערך הביטוי הבוליאני מוחזר ישירות.

למשל, this = מנה חלבית בדירוג 8 במחיר 60 ₪, other = מנה חלבית בדירוג 8 במחיר 50 ₪ – יוחזר true. אם other הייתה עולה 65 ₪ – יוחזר false.

Java:

public boolean canChange(Food other)
{
    return this.isMilk == other.isMilk      // אותו סוג (חלבי או לא)
        && this.raiting == other.raiting    // אותו דירוג
        && other.price <= this.price;       // other לא יקרה יותר
}

C#:

public bool CanChange(Food other)
{
    return this.isMilk == other.isMilk      // אותו סוג (חלבי או לא)
        && this.raiting == other.raiting    // אותו דירוג
        && other.price <= this.price;       // other לא יקרה יותר
}

לשלמות, כך נראית תחילת המחלקה (התכונות, הפעולה הבונה וחלק מפעולות ה-get) ב-Java:

public class Food
{
    private String name;      // שם המנה
    private double price;     // מחיר המנה
    private boolean isMilk;   // true - מנה חלבית
    private int raiting;      // דירוג 1-10

    public Food(String name, double price, boolean isMilk, int raiting)
    {
        this.name = name;
        this.price = price;
        this.isMilk = isMilk;
        this.raiting = raiting;
    }
    public String getName() { return this.name; }
    public double getPrice() { return this.price; }
    // ... שאר פעולות get/set והפעולה toString
}

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

סעיף ב

תשובה:

עוברים על המערך ומדפיסים את arr[i].getName() לכל i שעבורו arr[i].canChange(newFood) מחזירה true.

נתון: מערך מנות arr ומנה חדשה newFood. מבוקש: שמות כל המנות במערך שאפשר להחליף אותן ב-newFood.

הרעיון: משתמשים בפעולה מסעיף א. כל מנה במערך היא המנה ה"נוכחית" (this) ו-newFood היא המנה שמחליפה אותה (other), ולכן הזימון הוא `arr[i].canChange(newFood)`.

1. עוברים בלולאה על כל תאי המערך.

2. אם הזימון מחזיר true – מדפיסים את שם המנה בעזרת `getName()` (הפעולה סטטית, ולכן ניגשים לשם דרך פעולת get).

Java:

public static void changes(Food[] arr, Food newFood)
{
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i].canChange(newFood))      // אפשר להחליף את arr[i] ב-newFood
            System.out.println(arr[i].getName());
    }
}

C#:

public static void Changes(Food[] arr, Food newFood)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i].CanChange(newFood))      // אפשר להחליף את arr[i] ב-newFood
            Console.WriteLine(arr[i].GetName());
    }
}

דוגמה: במערך {Pizza (חלבית, 8, 60 ₪), Lasagna (חלבית, 8, 55 ₪), Burger (לא חלבית, 8, 70 ₪), Salad (לא חלבית, 6, 30 ₪), Quiche (חלבית, 8, 45 ₪)} ועם newFood = Pasta (חלבית, 8, 50 ₪) יודפסו Pizza ו-Lasagna. Quiche לא יודפס כי הוא זול מ-Pasta, ו-Burger ו-Salad לא מאותו סוג.

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

סעיף ג

תשובה:

לולאה כפולה על כל הזוגות i < j; אם arr[i].getPrice() + arr[j].getPrice() < 100 מדפיסים את שני השמות.

נתון: מערך מנות. מבוקש: כל הזוגות של שתי מנות שונות שמחירן יחד קטן מ-100 ₪.

הרעיון: צריך לבדוק כל זוג של מנות. לולאה כפולה שבה האינדקס הפנימי מתחיל אחרי החיצוני (`j = i + 1`) עוברת על כל זוג פעם אחת בדיוק:

1. מנה לא מוצמדת לעצמה (i ≠ j), ולכן שתי המנות שונות.

2. הזוג (i, j) לא מודפס שוב בסדר הפוך (j, i), כי זה אותו צירוף.

3. לכל זוג מחשבים את סכום המחירים, ואם הוא קטן ממש מ-100 – מדפיסים את שמות שתי המנות.

Java:

public static void offers(Food[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        for (int j = i + 1; j < arr.length; j++)   // כל זוג נבדק פעם אחת
        {
            if (arr[i].getPrice() + arr[j].getPrice() < 100)
                System.out.println(arr[i].getName() + " + " + arr[j].getName());
        }
    }
}

C#:

public static void Offers(Food[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = i + 1; j < arr.Length; j++)   // כל זוג נבדק פעם אחת
        {
            if (arr[i].GetPrice() + arr[j].GetPrice() < 100)
                Console.WriteLine(arr[i].GetName() + " + " + arr[j].GetName());
        }
    }
}

דוגמה: עבור המערך מסעיף ב יודפסו Pizza + Salad (90 ₪), Lasagna + Salad (85 ₪), Salad + Quiche (75 ₪). הזוג Lasagna + Quiche עולה 100 ₪ בדיוק ולכן לא יודפס.

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

סעיף ד

תשובה:

סעיף ב: O(n)O(n); סעיף ג: O(n2)O(n^2) (n – מספר המנות במערך).

נסמן ב-nn את מספר המנות במערך.

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

2. סעיף ג: לולאה כפולה. עבור i נבדקים n−1−in-1-i זוגות, ובסך הכול (n−1)+(n−2)+⋯+1=n(n−1)2(n-1)+(n-2)+\dots+1 = \frac{n(n-1)}{2} בדיקות, כל אחת בזמן קבוע. לכן הסיבוכיות O(n2)O(n^2).

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

שאלה 5 · מערך מושלם K ומערך סופר מושלם

מערך של מספרים שלמים חיוביים נקרא מערך "מושלם K" אם הוא עונה על התנאי הבא:

הסכום של כל K האיברים ההתחלתיים במערך (האיברים אשר נמצאים במקומות 0, 1, 2,..., K-1) מתחלק ב-K ללא שארית.

לדוגמה:

המערך הבא הוא מערך "מושלם 5":

012345678
714123123

כי סכום של חמשת האיברים הראשונים 7+1+4+1+2=15 מתחלק ב- 5.

א.

כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים arr ומספר שלם חיובי K.

הפעולה תחזיר ערך true, אם המערך "מושלם K", ולא, הפעולה תחזיר ערך false.

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

Java:

public static boolean isPerfectK(int[] arr, int k)

C#:

public static bool IsPerfectK(int[] arr, int k)
(5 נקודות)

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

לדוגמה:

המערך הנתון:

012345678
714123123

הוא לא מערך "סופר מושלם" כי הוא לא מערך "מושלם 4".

ב.

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

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

Java:

public static boolean isSuperPerfect(int[] arr)

C#:

public static bool IsSuperPerfect(int[] arr)
(5 נקודות)
ג.

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

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

סעיף א

תשובה:

אם k > arr.length מחזירים false; אחרת סוכמים את arr[0] עד arr[k-1] ומחזירים sum % k == 0.

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

1. אם במערך יש פחות מ-k איברים, אין "k איברים התחלתיים", ולכן מחזירים false (וכך גם לא חורגים מגבולות המערך).

2. סוכמים בלולאה את האיברים במקומות 0 עד k-1.

3. הסכום מתחלק ב-k ללא שארית אם `sum % k == 0`; מחזירים את ערך הביטוי.

בדיקה בדוגמה: עבור k = 5: 7+1+4+1+2=157+1+4+1+2 = 15 ו-15%5=015 \% 5 = 0 – true. עבור k = 4: 7+1+4+1=137+1+4+1 = 13 ו-13%4=113 \% 4 = 1 – false.

Java:

public static boolean isPerfectK(int[] arr, int k)
{
    if (k > arr.length)        // אין במערך K איברים
        return false;
    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];         // סכום K האיברים הראשונים
    return sum % k == 0;
}

C#:

public static bool IsPerfectK(int[] arr, int k)
{
    if (k > arr.Length)        // אין במערך K איברים
        return false;
    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];         // סכום K האיברים הראשונים
    return sum % k == 0;
}

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

סעיף ב

תשובה:

לולאה על k מ-1 עד arr.length; אם isPerfectK(arr, k) מחזירה false עבור k כלשהו – מחזירים false, ואחרי הלולאה מחזירים true.

נתון: מערך arr באורך n. מבוקש: האם המערך "מושלם K" לכל K = 1, 2, ..., n.

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

1. עוברים בלולאה על k מ-1 עד אורך המערך (כולל).

2. ברגע ש-`isPerfectK(arr, k)` מחזירה false – מחזירים false מיד.

3. אם הלולאה הסתיימה בלי כישלון – כל ערכי K תקינים, ומחזירים true.

בדיקה בדוגמה: k = 1: 7 מתחלק ב-1; k = 2: 8 מתחלק ב-2; k = 3: 12 מתחלק ב-3; k = 4: 13 לא מתחלק ב-4 – מוחזר false.

דוגמה למערך "סופר מושלם": {1, 3, 2, 6, 3, 9} – הסכומים 1, 4, 6, 12, 15, 24 מתחלקים ב-1, 2, 3, 4, 5, 6 בהתאמה.

Java:

public static boolean isSuperPerfect(int[] arr)
{
    for (int k = 1; k <= arr.length; k++)
    {
        if (!isPerfectK(arr, k))
            return false;      // נמצא K שעבורו המערך לא "מושלם K"
    }
    return true;
}

C#:

public static bool IsSuperPerfect(int[] arr)
{
    for (int k = 1; k <= arr.Length; k++)
    {
        if (!IsPerfectK(arr, k))
            return false;      // נמצא K שעבורו המערך לא "מושלם K"
    }
    return true;
}

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

סעיף ג

תשובה:

סעיף א: O(k)O(k), ובמקרה הגרוע O(n)O(n); סעיף ב: O(n2)O(n^2) (n – אורך המערך).

נסמן ב-nn את אורך המערך.

1. סעיף א: הלולאה סוכמת kk איברים, ולכן הסיבוכיות O(k)O(k). מכיוון שתמיד k≤nk \le n (אחרת הפעולה מסתיימת מיד), במקרה הגרוע זה O(n)O(n).

2. סעיף ב: במקרה הגרוע (המערך "סופר מושלם") מזמנים את isPerfectK עבור k=1,2,…,nk = 1, 2, \dots, n, וכל זימון עולה kk צעדים. בסך הכול 1+2+⋯+n=n(n+1)21+2+\dots+n = \frac{n(n+1)}{2} צעדים, כלומר O(n2)O(n^2).

(אפשר לשפר את סעיף ב ל-O(n)O(n) בעזרת סכום מצטבר: מוסיפים בכל שלב את arr[k−1]arr[k-1] לסכום ובודקים התחלקות ב-k, בלי לסכום מחדש.)

תשובה: סעיף א – O(k)O(k) (לכל היותר O(n)O(n)), סעיף ב – O(n2)O(n^2).

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

א.

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

Java:

public static int one(int num, int dig)
{
    int res = 0;
    while (num > 0)
    {
        if(num % 10 == dig)
          res++;
        num = num / 10;
    }
    return res;
}

C#:

public static int One(int num, int dig)
{
    int res = 0;
    while (num > 0)
    {
        if(num % 10 == dig)
          res++;
        num = num / 10;
    }
    return res;
}
(1)

תנו דוגמה של מספר num > 1000 כך שתוצאת הזימון one(num, 7) תהיה 3.

(2)

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

(4 נקודות)
ב.

נתונה הפעולה two המקבלת מערך arr של מספרים שלמים חיוביים וספרה dig:

Java:

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

    for (int i = 0; i < arr.length; i++)
    {
          res = res + one(arr[i], dig);
    }
    return res;
}

C#:

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

    for (int i = 0; i < arr.Length; i++)
    {
          res = res + One(arr[i], dig);
    }
    return res;
}

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

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

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

(2)

הסבירו מה מבצעת הפעולה two באופן כללי.

(4 נקודות)
ג.

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

Java:

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

    for (int i = 1; i < 10; i++)
    {
        if (two(arr, i) > two(arr, res))
        {
             res = i;
        }
    }
    return res;
}

C#:

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

    for (int i = 1; i < 10; i++)
    {
        if (Two(arr, i) > Two(arr, res))
        {
             res = i;
        }
    }
    return res;
}
(1)

תנו דוגמה של מערך arr בגודל שישה תאים שעבורו תוצאת זימון הפעולה three(arr) תהיה 6.

(2)

הסבירו מה מבצעת הפעולה three באופן כללי.

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

סעיף א

(1)
תשובה:

למשל num = 7707.

הפעולה מחזירה את מספר הספרות של num השוות ל-dig (ראו סעיף 2), ולכן צריך מספר גדול מ-1000 שבו הספרה 7 מופיעה בדיוק שלוש פעמים.

דוגמה: num = 7707. מעקב:

שלבnumnum % 10שווה ל-7?res
177077כן1
27700לא1
3777כן2
477כן3
50–הלולאה מסתיימת3

מוחזר 3. (גם 1777 או 7077 מתאימים.)

תשובה: num = 7707.

(2)
תשובה:

מחזירה כמה פעמים הספרה dig מופיעה במספר num.

בכל סיבוב `num % 10` היא ספרת האחדות של num; אם היא שווה ל-dig מגדילים את res. אחר כך `num / 10` מוחקת את ספרת האחדות. הלולאה מסתיימת כשכל הספרות נבדקו (num = 0).

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

סעיף ב

(1)
תשובה:

הפעולה מחזירה 6.

בכל סיבוב מוסיפים ל-res את מספר הפעמים שהספרה 4 מופיעה ב-arr[i] (הפעולה one).

iarr[i]one(arr[i], 4)res
–––0
02411
13478312
2124513
36803
446814
5944526

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

(2)
תשובה:

מחזירה כמה פעמים הספרה dig מופיעה בסך הכול בכל איברי המערך arr.

הפעולה עוברת על כל איברי המערך וצוברת ב-res את תוצאת one לכל איבר, כלומר את מספר המופעים של dig בכל מספר.

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

סעיף ג

(1)
תשובה:

למשל arr = {6, 6, 6, 6, 6, 6}.

לפי סעיף 2, הפעולה מחזירה את הספרה שמופיעה הכי הרבה פעמים בכל המערך. לכן צריך מערך בן 6 תאים שבו הספרה 6 מופיעה יותר מכל ספרה אחרת.

דוגמה: arr = {6, 6, 6, 6, 6, 6}: `two(arr, 6) = 6`, ולכל ספרה אחרת (כולל 0) התוצאה 0. בסיבוב i = 6 מתקיים 6>06 > 0 ו-res הופך ל-6; בסיבובים i = 7, 8, 9 התוצאה 0 ואינה גדולה מ-6. מוחזר 6.

(גם {16, 26, 36, 46, 56, 66} מתאים: הספרה 6 מופיעה 7 פעמים, וכל ספרה אחרת לכל היותר פעם אחת.)

תשובה: arr = {6, 6, 6, 6, 6, 6}.

(2)
תשובה:

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

res מתחיל ב-0, והלולאה עוברת על הספרות 1 עד 9. לכל ספרה i משווים את מספר המופעים שלה במערך (`two(arr, i)`) למספר המופעים של הספרה הטובה עד כה (`two(arr, res)`), ומעדכנים רק אם הוא גדול ממש. זה חיפוש מקסימום על מספרי המופעים.

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

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

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

Java:

public static int secret(String str)
{
    int c = 0;
    System.out.print("%");
    for (int i = 0; i < str.length(); i++)
    {
        if (str.charAt(i) >='A' && str.charAt(i) <= 'Z')
        {
             System.out.print(i+"#");
        }
        else
          if (str.charAt(i) >='a' && str.charAt(i) <= 'z')
           {
            System.out.print(i+"?");
           }
          else
            c++;
    }
    System.out.print("%");
    return c;
}

C#:

public static int Secret(string str)
{
    int c = 0;
    Console.Write ("%");
    for (int i = 0; i < str.Length; i++)
    {
        if (str[i] >='A' && str[i] <= 'Z')
        {
             Console.Write(i+"#");
        }
        else
          if (str[i] >='a' && str[i] <= 'z')
           {
            Console.Write (i+"?");
           }
          else
            c++;
    }
    Console.Write ("%");
    return c;
}
א.

תנו דוגמה למחרוזת באורך של 6 תווים לכל הפחות שעבורה הפעולה secret תדפיס את המחרוזת הבאה: %3?5#%. איזה ערך תחזיר הפעולה?

(4 נקודות)
ב.

תנו דוגמה למחרוזת באורך של 6 תווים לכל הפחות שעבורה הפעולה secret תדפיס את המחרוזת הבאה: %%. איזה ערך תחזיר הפעולה?

(3 נקודות)
ג.

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

מה תדפיס הפעולה?

(3 נקודות)
ד.

מה מבצעת הפעולה?

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

סעיף א

תשובה:

למשל "123a3A"; הפעולה מחזירה 4.

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

ניתוח הפלט %3?5#%: אחרי `%` מופיע `3?` – במקום 3 יש אות קטנה; אחר כך `5#` – במקום 5 יש אות גדולה. לא מופיעים מקומות אחרים, ולכן כל שאר התווים אינם אותיות.

דוגמה: "123a3A" (אורך 6). מעקב:

מקום istr[i]סוגפלטc
–––%0
01לא אות–1
12לא אות–2
23לא אות–3
3aאות קטנה3?3
43לא אות–4
5Aאות גדולה5#4
––סוף%4

הפלט: `%3?5#%`, והערך המוחזר 4 (ארבעה תווים שאינם אותיות).

תשובה: למשל "123a3A"; הפעולה מחזירה 4.

סעיף ב

תשובה:

למשל "123456"; הפעולה מחזירה 6.

הפלט `%%` אומר שבין שני סימני ה-% לא הודפס דבר, כלומר אין במחרוזת אף אות באנגלית. כל התווים נספרים ב-c.

דוגמה: "123456" – שישה תווים, אף אחד מהם אינו אות, ולכן c גדל שש פעמים.

תשובה: למשל "123456"; הפעולה מחזירה 6 (באופן כללי – את אורך המחרוזת).

סעיף ג

תשובה:

למשל "Aa12Aa"; יודפס %0#1?4#5?%.

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

דוגמה: "Aa12Aa":

מקום istr[i]סוגפלטc
–––%0
0Aאות גדולה0#0
1aאות קטנה1?0
21לא אות–1
32לא אות–2
4Aאות גדולה4#2
5aאות קטנה5?2
––סוף%2

תשובה: למשל "Aa12Aa"; הפעולה מחזירה 2 ומדפיסה `%0#1?4#5?%`.

סעיף ד

תשובה:

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

הפעולה עוברת על תווי המחרוזת לפי הסדר:

1. לכל אות גדולה ('A'-'Z') מדפיסה את המקום שלה ואחריו `#`.

2. לכל אות קטנה ('a'-'z') מדפיסה את המקום שלה ואחריו `?`.

3. כל תו אחר (ספרה, רווח, סימן) נספר ב-c.

את כל הפלט היא עוטפת ב-`%` בהתחלה ובסוף.

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

שאלה 8 · פלינדרום ופלינדרום של ערכים זוגיים

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

"פָּלִינְדְרוֹם" הוא רצף ערכים שקריאתו מימין לשמאל ומשמאל לימין היא זהה.

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

[1] , [10,10,10,10], [5,2,2,5] , [1,3,10,3,1]

א.

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

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

Java:

public static boolean isPalindrom(int[] arr)

C#:

public static bool IsPalindrom(int[] arr)
(6 נקודות)

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

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

דוגמאות לפלינדרומים של ערכים זוגיים ( הערכים המודגשים):

[1,3,2], [10,3,4,5,7,4,10], [3,5,7,1], [5,2,2,5], [1,3,10,3,1,10]

ב.

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

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

Java:

public static boolean isEvenPalindrom(int[] arr)

C#:

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

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

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

סעיף א

תשובה:

שני מצביעים i מההתחלה ו-j מהסוף; כל עוד i < j משווים arr[i] ל-arr[j] – אם שונים מחזירים false, אחרת מקדמים את שניהם; בסוף מחזירים true.

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

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

1. כל עוד `i < j` משווים את `arr[i]` ל-`arr[j]`.

2. אם הם שונים – המערך אינו פלינדרום, ומחזירים false מיד.

3. אחרת מקדמים את i ומורידים את j.

4. כשהמצביעים נפגשו (או עברו זה את זה) כל הזוגות נבדקו – מחזירים true. איבר אמצעי (באורך אי-זוגי) לא צריך בדיקה.

בדיקה: עבור [1,3,10,3,1]: 1=1, 3=3, ואז i = j = 2 – true. עבור [1,2]: 1≠2 – false.

Java:

public static boolean isPalindrom(int[] arr)
{
    int i = 0, j = arr.length - 1;   // מצביע משמאל ומצביע מימין
    while (i < j)
    {
        if (arr[i] != arr[j])
            return false;
        i++;
        j--;
    }
    return true;
}

C#:

public static bool IsPalindrom(int[] arr)
{
    int i = 0, j = arr.Length - 1;   // מצביע משמאל ומצביע מימין
    while (i < j)
    {
        if (arr[i] != arr[j])
            return false;
        i++;
        j--;
    }
    return true;
}

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

סעיף ב

תשובה:

שני מצביעים כמו בסעיף א, אבל מדלגים על איברים אי-זוגיים: אם arr[i] אי-זוגי מקדמים i, אם arr[j] אי-זוגי מורידים j, ואם שניהם זוגיים – משווים (שונים → false) ומקדמים את שניהם; בסוף true.

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

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

1. אם `arr[i]` אי-זוגי – מקדמים את i בלבד (מדלגים עליו).

2. אחרת, אם `arr[j]` אי-זוגי – מורידים את j בלבד.

3. אחרת שניהם זוגיים: זה זוג של ערכים זוגיים סימטריים, והם חייבים להיות שווים. אם הם שונים מחזירים false; אם שווים מקדמים את i ומורידים את j.

4. כשהלולאה מסתיימת (`i >= j`) כל הזוגות הזוגיים נבדקו – מחזירים true. מערך בלי ערכים זוגיים (כמו [3,5,7,1]) הוא פלינדרום של ערכים זוגיים, כי סדרה ריקה זהה להיפוכה.

הבדיקה `arr[i] % 2 != 0` נכונה גם למספרים שליליים (השארית של אי-זוגי שלילי היא 1-).

בדיקה: עבור [10,3,4,5,7,4,10]: 10=10; מדלגים על 3 משמאל; 4=4; ואז מדלגים על 5 ו-7 עד ש-i ≥ j – true. עבור [2,3,4,2]: 2=2; מדלגים על 3; i = j = 2 – true. עבור [2,4]: 2≠4 – false.

Java:

public static boolean isEvenPalindrom(int[] arr)
{
    int i = 0, j = arr.length - 1;
    while (i < j)
    {
        if (arr[i] % 2 != 0)          // מדלגים על אי-זוגי משמאל
            i++;
        else if (arr[j] % 2 != 0)     // מדלגים על אי-זוגי מימין
            j--;
        else
        {
            if (arr[i] != arr[j])     // שני זוגיים מתאימים - חייבים להיות שווים
                return false;
            i++;
            j--;
        }
    }
    return true;
}

C#:

public static bool IsEvenPalindrom(int[] arr)
{
    int i = 0, j = arr.Length - 1;
    while (i < j)
    {
        if (arr[i] % 2 != 0)          // מדלגים על אי-זוגי משמאל
            i++;
        else if (arr[j] % 2 != 0)     // מדלגים על אי-זוגי מימין
            j--;
        else
        {
            if (arr[i] != arr[j])     // שני זוגיים מתאימים - חייבים להיות שווים
                return false;
            i++;
            j--;
        }
    }
    return true;
}

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

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

סעיף ג

תשובה:

שתיהן O(n)O(n) (n – אורך המערך).

נסמן ב-nn את אורך המערך.

1. סעיף א: בכל סיבוב i גדל ו-j קטן, והלולאה נעצרת כשהם נפגשים – לכל היותר n2\frac{n}{2} סיבובים, כל אחד בזמן קבוע. לכן O(n)O(n).

2. סעיף ב: בכל סיבוב לפחות אחד המצביעים זז צעד אחד לכיוון השני, והמרחק ההתחלתי ביניהם הוא n−1n-1. לכן יש לכל היותר n−1n-1 סיבובים, כל אחד בזמן קבוע – O(n)O(n).

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

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

החברה "סע לך" מוכרת כרטיסי טיסה ליעדים שונים ברחבי העולם.

לצורך אחסון נתוני כרטיסים שנמכרו הוגדרה מחלקה בשם Destination ולה 3 תכונות:

•שם היעד – name – מסוג מחרוזת, String.

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

•מספר כרטיסים שנמכרו – num – מסוג מספר שלם, int.

לפניכם מחלקה TestDestination המשתמשת במחלקה Destination:

Java:

public class TestDestination
{
  public static double total (Destination d)
  {
     return d.getPrice()*d.getNum();
  }
  public static void main(String[] args)
  {
    Destination  d1 = new Destination("Paris");
    d1.setName("London");
    d1.setNum(200);
    d1.setPrice(300.0);
    System.out.println(total(d1));
    d1.setNum(50);
    Destination  d2 = new Destination (d1.getName(), 100.0,
                                       d1.getNum());
    System.out.println(total (d2));
  }
}

C#:

public class TestDestination
{
  public static double Total (Destination d)
  {
     return d.GetPrice()*d.GetNum();
  }
  public static void Main(string[] args)
  {
    Destination  d1 = new Destination("Paris");
    d1.SetName("London");
    d1.SetNum(200);
    d1.SetPrice(300.0);
    Console.WriteLine(Total(d1));
    d1.SetNum(50);
    Destination  d2 = new Destination (d1.GetName(), 100.0,
                                       d1.GetNum());
    Console.WriteLine (Total (d2));
  }
}
א.

כתבו במחלקה Destination כותרות של כל הפעולות הנדרשות לביצוע הפעולה הראשית main.

(4 נקודות)
ב.

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

(3 נקודות)
ג.

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

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

Java:

public static String getNotPopular(Destination[] dest)

C#:

public static string GetNotPopular(Destination[] dest)
(4 נקודות)
ד.

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

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

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

Java:

public static String[]cheapDests(Destination[] dest)

C#:

public static string[]CheapDests(Destination[] dest)
(4 נקודות)
◂ פתרון מלא לשאלה 9

סעיף א

תשובה:

שתי פעולות בונות – Destination(String name) ו-Destination(String name, double price, int num); getName, getPrice, getNum; setName, setPrice, setNum.

עוברים על main ועל total ורושמים כל פעולה של Destination שמופעלת, עם טיפוסי הפרמטרים וטיפוס הערך המוחזר:

1. `new Destination("Paris")` – פעולה בונה שמקבלת מחרוזת אחת (השם). המחיר ומספר הכרטיסים מאותחלים ל-0.

2. `new Destination(d1.getName(), 100.0, d1.getNum())` – פעולה בונה שנייה שמקבלת שם (String), מחיר (double) ומספר כרטיסים (int).

3. `setName("London")`, `setNum(200)`, `setPrice(300.0)` – פעולות set שמקבלות ערך מהטיפוס של התכונה ולא מחזירות ערך (void).

4. `getPrice()` ו-`getNum()` (בפעולה total) ו-`getName()`, `getNum()` (ביצירת d2) – פעולות get שמחזירות את ערך התכונה.

Java:

public Destination(String name)                          // פעולה בונה עם שם בלבד
public Destination(String name, double price, int num)   // פעולה בונה עם שלושה ערכים
public String getName()
public double getPrice()
public int getNum()
public void setName(String name)
public void setPrice(double price)
public void setNum(int num)

C#:

public Destination(string name)                          // פעולה בונה עם שם בלבד
public Destination(string name, double price, int num)   // פעולה בונה עם שלושה ערכים
public string GetName()
public double GetPrice()
public int GetNum()
public void SetName(string name)
public void SetPrice(double price)
public void SetNum(int num)

תשובה: שתי הפעולות הבונות, שלוש פעולות get ושלוש פעולות set, כפי שמופיע למעלה.

סעיף ב

תשובה:

יודפס 60000.0 ואחריו 5000.0 (ב-C#: 60000 ו-5000).

עוקבים אחרי מצב העצמים אחרי כל הוראה:

הוראהd1 (name, price, num)d2 (name, price, num)פלט
`d1 = new Destination("Paris")`Paris, 0.0, 0––
`d1.setName("London")`London, 0.0, 0––
`d1.setNum(200)`London, 0.0, 200––
`d1.setPrice(300.0)`London, 300.0, 200––
`println(total(d1))`London, 300.0, 200–60000.0
`d1.setNum(50)`London, 300.0, 50––
`d2 = new Destination("London", 100.0, 50)`London, 300.0, 50London, 100.0, 50–
`println(total(d2))`London, 300.0, 50London, 100.0, 505000.0

1. total(d1)=300.0⋅200=60000.0total(d1) = 300.0 \cdot 200 = 60000.0.

2. d2 נוצר עם השם והמספר של d1 ברגע היצירה (London ו-50) ועם מחיר 100.0, ולכן total(d2)=100.0⋅50=5000.0total(d2) = 100.0 \cdot 50 = 5000.0.

ב-Java ערך double מודפס עם נקודה עשרונית (60000.0). ב-C# הפקודה Console.WriteLine מדפיסה ערך double שלם בלי נקודה עשרונית (60000).

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

60000.0
5000.0

(ב-C#: 60000 ו-5000).

סעיף ג

תשובה:

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

נתון: מערך יעדים. מבוקש: שם היעד שמכר הכי מעט כרטיסים.

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

1. מתחילים מ-`minIndex = 0` (היעד הראשון).

2. עוברים על שאר היעדים; אם ליעד במקום i נמכרו פחות כרטיסים מאשר ליעד במקום minIndex – מעדכנים `minIndex = i`.

3. מחזירים `dest[minIndex].getName()`. אם יש כמה יעדים עם אותו מינימום – מוחזר הראשון מביניהם.

מניחים שהמערך אינו ריק.

Java:

public static String getNotPopular(Destination[] dest)
{
    int minIndex = 0;            // מיקום היעד עם הכי מעט כרטיסים עד כה
    for (int i = 1; i < dest.length; i++)
    {
        if (dest[i].getNum() < dest[minIndex].getNum())
            minIndex = i;
    }
    return dest[minIndex].getName();
}

C#:

public static string GetNotPopular(Destination[] dest)
{
    int minIndex = 0;            // מיקום היעד עם הכי מעט כרטיסים עד כה
    for (int i = 1; i < dest.Length; i++)
    {
        if (dest[i].GetNum() < dest[minIndex].GetNum())
            minIndex = i;
    }
    return dest[minIndex].GetName();
}

דוגמה: עבור {Rome (80 כרטיסים), Paris (30), Eilat (500), Athens (30)} מוחזר Paris.

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

סעיף ד

תשובה:

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

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

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

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

1. מעבר ראשון – ספירה: סופרים ב-count כמה יעדים מקיימים `getPrice() < maxPrice`.

2. יוצרים מערך מחרוזות בגודל count. אם אין אף יעד מתאים, count = 0 ונוצר מערך בגודל 0, כפי שנדרש.

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

Java:

public static String[] cheapDests(Destination[] dest, double maxPrice)
{
    int count = 0;               // מעבר ראשון: כמה יעדים זולים יש
    for (int i = 0; i < dest.length; i++)
    {
        if (dest[i].getPrice() < maxPrice)
            count++;
    }
    String[] names = new String[count];
    int k = 0;                   // המקום הפנוי הבא במערך השמות
    for (int i = 0; i < dest.length; i++)
    {
        if (dest[i].getPrice() < maxPrice)
        {
            names[k] = dest[i].getName();
            k++;
        }
    }
    return names;
}

C#:

public static string[] CheapDests(Destination[] dest, double maxPrice)
{
    int count = 0;               // מעבר ראשון: כמה יעדים זולים יש
    for (int i = 0; i < dest.Length; i++)
    {
        if (dest[i].GetPrice() < maxPrice)
            count++;
    }
    string[] names = new string[count];
    int k = 0;                   // המקום הפנוי הבא במערך השמות
    for (int i = 0; i < dest.Length; i++)
    {
        if (dest[i].GetPrice() < maxPrice)
        {
            names[k] = dest[i].GetName();
            k++;
        }
    }
    return names;
}

דוגמה: עבור {Rome 250, Paris 400, Eilat 90, Athens 180} ו-maxPrice = 200 יוחזר {"Eilat", "Athens"}; עבור maxPrice = 50 יוחזר מערך בגודל 0.

תשובה: הפעולה שלמעלה (עם הפרמטר maxPrice).

שאלה 10 · מעקב: היפוך קטעים והזזה מעגלית של מערך

נתונה הפעולה why המקבלת מערך של מספרים שלמים arr ומספר שלם חיובי s. הפעולה משתמשת בפעולת עזר what.

Java:

public static void why(int[] arr, int s) {
    s = s % arr.length;
    what(arr, 0, arr.length - 1);
    what(arr, 0, s - 1);
    what(arr, s, arr.length - 1);
  }
  public static void what(int[] arr, int start, int end) {
     int temp;
    while (start < end) {
      temp = arr [start];
      arr [start] = arr [end];
      arr [end] = temp;
      start ++;
      end --;
    }
  }

C#:

public static void Why(int[] arr, int s) {
    s = s % arr.Length;
    What(arr, 0, arr.Length - 1);
    What(arr, 0, s - 1);
    What(arr, s, arr.Length - 1);
  }
  public static void What(int[] arr, int start, int end) {
     int temp;
    while (start < end) {
      temp = arr [start];
      arr [start] = arr [end];
      arr [end] = temp;
      start ++;
      end --;
    }
  }

נתון מערך arr הבא:

0123456789
571215212640517184
א.

מה יהיה תוכן הרשימה אחרי זימון הפעולה what(arr, 2, 6)? יש להראות מעקב אחרי ביצוע הפעולה.

(5 נקודות)
ב.

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

(2 נקודות)
ג.

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

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

(4 נקודות)
ד.

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

(2 נקודות)
ה.

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

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

סעיף א

תשובה:

arr = {5, 7, 40, 26, 21, 15, 12, 51, 71, 84}.

בכל סיבוב מחליפים את `arr[start]` עם `arr[end]`, ואז start גדל ב-1 ו-end קטן ב-1. הלולאה רצה כל עוד start < end.

התחלה startסוף endstart < end?temparr[start] אחריarr[end] אחרי
26כן12arr[2] = 40arr[6] = 12
35כן15arr[3] = 26arr[5] = 15
44לא–––

האיבר האמצעי arr[4] = 21 נשאר במקומו.

0123456789
574026211512517184

תשובה: arr = {5, 7, 40, 26, 21, 15, 12, 51, 71, 84}.

סעיף ב

תשובה:

הופכת את סדר האיברים במערך arr בקטע שבין המקום start למקום end (כולל); שאר המערך לא משתנה.

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

תשובה: הפעולה הופכת את סדר האיברים במערך arr החל מהמקום start ועד המקום end (כולל). איברים מחוץ לקטע לא משתנים.

סעיף ג

תשובה:

arr = {40, 51, 71, 84, 5, 7, 12, 15, 21, 26}.

מתחילים מהמערך המקורי {5, 7, 12, 15, 21, 26, 40, 51, 71, 84} (באורך 10).

הוראהפעולהתוכן arr אחרי ההוראה
`s = s % arr.length`s=4%10=4s = 4 \% 10 = 4{5, 7, 12, 15, 21, 26, 40, 51, 71, 84}
`what(arr, 0, 9)`היפוך כל המערך{84, 71, 51, 40, 26, 21, 15, 12, 7, 5}
`what(arr, 0, 3)`היפוך מקומות 0-3{40, 51, 71, 84, 26, 21, 15, 12, 7, 5}
`what(arr, 4, 9)`היפוך מקומות 4-9{40, 51, 71, 84, 5, 7, 12, 15, 21, 26}

התוצאה: ארבעת האיברים האחרונים (40, 51, 71, 84) עברו להתחלה, וכל השאר זזו 4 מקומות ימינה.

תשובה: arr = {40, 51, 71, 84, 5, 7, 12, 15, 21, 26}.

סעיף ד

תשובה:

כן – כל s שהוא כפולה של אורך המערך (10, 20, 30, ...).

1. אם s כפולה של 10 (אורך המערך), אז אחרי `s = s % arr.length` מתקבל s = 0.

2. `what(arr, 0, 9)` הופכת את כל המערך.

3. `what(arr, 0, -1)` לא עושה דבר, כי start = 0 אינו קטן מ-end = -1.

4. `what(arr, 0, 9)` הופכת את כל המערך שוב, ושני היפוכים מחזירים את הסדר המקורי.

לכל s אחר, s%10s \% 10 הוא בין 1 ל-9 והמערך זז מעגלית בכמה מקומות (סעיף ה). מכיוון שכל איברי המערך הנתון שונים זה מזה, הזזה כזו משנה אותו.

תשובה: כן. עבור כל s שהוא כפולה של אורך המערך (10, 20, 30, ...) המערך חוזר למצבו המקורי: הוא מתהפך פעמיים, וההיפוך האמצעי what(arr, 0, -1) לא עושה דבר.

סעיף ה

תשובה:

מזיזה את איברי המערך arr באופן מעגלי ימינה ב-s מקומות (כלומר ב-s % arr.length מקומות).

נסמן nn = אורך המערך ו-s′=s%ns' = s \% n.

1. היפוך כל המערך מעביר את s′s' האיברים האחרונים להתחלה, אבל בסדר הפוך.

2. היפוך של s′s' האיברים הראשונים מחזיר אותם לסדרם המקורי.

3. היפוך של שאר האיברים (מהמקום s′s' עד הסוף) מחזיר גם אותם לסדרם המקורי.

בסך הכול כל איבר זז s′s' מקומות ימינה, והאיברים ש"נופלים" מהסוף חוזרים להתחלה. הזזה ב-s וב-s%ns \% n זהה, כי הזזה ב-n מקומות מחזירה את המערך למצבו.

תשובה: הפעולה מבצעת הזזה מעגלית ימינה של איברי המערך arr ב-s מקומות (בפועל ב-s % arr.length מקומות): כל איבר עובר מהמקום i למקום (i + s) % arr.length.

שאלה 11 · מחלקת Number: מספר ספרות וסכום ספרות

נתונה מחלקה Number הבאה:

Java:

class Number
{
  private int num1;
  private int num2;
  public Number(int num)
  {
    this.num1 = 0;
    this.num2 = 0;
    if(num<0)num = num*(-1);
    while(num > 0)
    {
      this.num1++;
      this.num2+= num % 10;
      num = num/10;
    }
  }
  public int getNum1(){return this.num1;}
  public int getNum2(){return this.num2;}

  public boolean equals(Number other)
  {
   return this.num1 == other.num1 && this.num2 == other.num2;
  }
  public boolean isSame(Number other)
  {
   return this.num1 * other.num2 == this.num2 * other.num1;
  }
}

C#:

class Number
{
  private int num1;
  private int num2;
  public Number(int num)
  {
    this.num1 = 0;
    this.num2 = 0;
    if(num<0)num = num*(-1);
    while(num > 0)
    {
      this.num1++;
      this.num2+= num % 10;
      num = num/10;
    }
  }
  public int GetNum1(){return this.num1;}
  public int GetNum2(){return this.num2;}

  public bool Equals(Number other)
  {
   return this.num1 == other.num1 && this.num2 == other.num2;
  }
  public bool IsSame(Number other)
  {
   return this.num1 * other.num2 == this.num2 * other.num1;
  }
}
א.

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

Java:

public static int mystery(int x, int y)
{
  Number a = new Number (x);
  Number b = new Number (y);
  if(x == y)return 1;
  if(a.equals(b))return 2;
  if(a.isSame(b))return 3;
  return 4;
}

C#:

public static int Mystery(int x, int y)
{
  Number a = new Number (x);
  Number b = new Number (y);
  if(x == y)return 1;
  if(a.Equals(b))return 2;
  if(a.IsSame(b))return 3;
  return 4;
}
(1)

תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 2.

(2)

תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 3.

(3)

תנו דוגמה לזוג פרמטרים שעבורו הפעולה תחזיר 4.

(4)

האם קיים מספר שלם תלת-ספרתי חיובי x שעבורו הפעולה mystery אף פעם לא תחזיר 2? הסבירו את תשובתכם.

(5)

האם קיים מספר שלם תלת-ספרתי חיובי x שעבורו הפעולה mystery אף פעם לא תחזיר 3? הסבירו את תשובתכם.

(7 נקודות)
ב.

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

Java:

public static boolean secret(int [] arr)
{
  Number temp1 = new Number (arr[0]);
  Number temp2 = new Number (arr[0]);
  int pos1 = 0;
  int pos2 = 0;

  Number cur;
  for(int i = 1; i < arr.length; i++)
  {
    cur = new Number(arr[i]);
    if(cur.getNum1() > temp1.getNum1())
    {
      pos1 = i;
      temp1 = cur;
    }
    if(cur.getNum2() > temp2.getNum2())
    {
      pos2 = i;
      temp2 = cur;
    }
  }
  return (pos1 == pos2);
}

C#:

public static bool Secret(int [] arr)
{
  Number temp1 = new Number (arr[0]);
  Number temp2 = new Number (arr[0]);
  int pos1 = 0;
  int pos2 = 0;

  Number cur;
  for(int i = 1; i < arr.Length; i++)
  {
    cur = new Number(arr[i]);
    if(cur.GetNum1() > temp1.GetNum1())
    {
      pos1 = i;
      temp1 = cur;
    }
    if(cur.GetNum2() > temp2.GetNum2())
    {
      pos2 = i;
      temp2 = cur;
    }
  }
  return (pos1 == pos2);
}

נתון המערך arr הבא:

0123456
3458-457681-87561357143

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

(6 נקודות)
ג.

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

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

סעיף א

(1)
תשובה:

למשל mystery(24, 15).

מה שומר עצם Number: הפעולה הבונה עובדת על הערך המוחלט של num. בכל סיבוב num1 גדל ב-1 ו-num2 מקבל את ספרת האחדות, ולכן num1 = מספר הספרות ו-num2 = סכום הספרות. (עבור 0 שניהם 0.)

לכן equals מחזירה true כאשר לשני המספרים אותו מספר ספרות ואותו סכום ספרות, ו-isSame מחזירה true כאשר num2num1\frac{num2}{num1} זהה, כלומר ממוצע הספרות זהה (הבדיקה נעשית בכפל בהצלבה).

כדי לקבל 2 צריך x≠yx \ne y עם אותו מספר ספרות ואותו סכום ספרות.

דוגמה: x = 24, y = 15: לשניהם 2 ספרות וסכום ספרות 6. x≠yx \ne y, ו-equals מחזירה true – מוחזר 2.

תשובה: mystery(24, 15) מחזירה 2.

(2)
תשובה:

למשל mystery(600, 22).

צריך x≠yx \ne y שאינם שווים במספר הספרות ובסכום (אחרת יוחזר 2), אבל עם אותו ממוצע ספרות.

דוגמה: x = 600: 3 ספרות, סכום 6. y = 22: 2 ספרות, סכום 4. equals – false (3≠23 \ne 2). isSame: 3⋅4=123 \cdot 4 = 12 ו-6⋅2=126 \cdot 2 = 12 – true. מוחזר 3.

תשובה: mystery(600, 22) מחזירה 3.

(3)
תשובה:

למשל mystery(12, 234).

צריך שכל שלושת התנאים ייכשלו: x≠yx \ne y, מספר ספרות או סכום שונים, וממוצע ספרות שונה.

דוגמה: x = 12: 2 ספרות, סכום 3. y = 234: 3 ספרות, סכום 9. equals – false. isSame: 2⋅9=182 \cdot 9 = 18 לעומת 3⋅3=93 \cdot 3 = 9 – false. מוחזר 4.

תשובה: mystery(12, 234) מחזירה 4.

(4)
תשובה:

לא. לכל x תלת-ספרתי, mystery(x, -x) מחזירה 2.

הפעולה הבונה של Number הופכת מספר שלילי לחיובי, ולכן ל-x ול-(-x) יש אותו מספר ספרות ואותו סכום ספרות. עבור y = -x:

1. x≠yx \ne y (כי x חיובי ו-y שלילי) – לא מוחזר 1.

2. equals מחזירה true – מוחזר 2.

למשל mystery(123, -123) מחזירה 2.

תשובה: לא קיים מספר כזה: לכל x תלת-ספרתי חיובי, הזוג (x, -x) מחזיר 2.

(5)
תשובה:

לא. לכל x (שונה מ-0), mystery(x, 0) מחזירה 3.

עבור y = 0 הלולאה בפעולה הבונה לא מתבצעת, ולכן num1 = 0 וגם num2 = 0. נבדוק את mystery(x, 0) עבור x תלת-ספרתי:

1. x≠0x \ne 0 – לא מוחזר 1.

2. equals: ל-x יש 3 ספרות ול-0 יש num1 = 0 – false, לא מוחזר 2.

3. isSame: num1x⋅0==num2x⋅0num1_x \cdot 0 == num2_x \cdot 0, כלומר 0==00 == 0 – true. מוחזר 3.

גם בלי להשתמש ב-0 תמיד יש זוג כזה: אם כותבים את ספרות x פעמיים ברצף (מספר בן 6 ספרות, למשל x = 100 ו-y = 100100), מספר הספרות וסכום הספרות מוכפלים פי 2, ולכן ממוצע הספרות זהה אבל equals נכשלת – מוחזר 3.

תשובה: לא קיים מספר כזה: לכל x תלת-ספרתי חיובי, mystery(x, 0) מחזירה 3.

סעיף ב

תשובה:

pos1 = 5, pos2 = 2, ולכן מוחזר false.

לכל איבר מחשבים num1 (מספר הספרות) ו-num2 (סכום הספרות של הערך המוחלט). temp1 שומר את האיבר עם הכי הרבה ספרות עד כה ו-pos1 את מיקומו; temp2 ו-pos2 – את האיבר עם סכום הספרות הגדול ביותר עד כה. העדכון מתבצע רק כשהערך גדול ממש.

התחלה: arr[0] = 3458 – num1 = 4, num2=3+4+5+8=20num2 = 3+4+5+8 = 20; pos1 = 0, pos2 = 0.

iarr[i]num1num2num1 > temp1?num2 > temp2?pos1pos2
1-45292 > 4 לא9 > 20 לא00
276814224 > 4 לא22 > 20 כן02
3-8753203 > 4 לא20 > 22 לא02
46161 > 4 לא6 > 22 לא02
5135715175 > 4 כן17 > 22 לא52
643272 > 5 לא7 > 22 לא52

בסוף pos1 = 5 ו-pos2 = 2, ו-`pos1 == pos2` הוא false.

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

סעיף ג

תשובה:

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

pos1 הוא המיקום של המספר הראשון (משמאל) שיש לו מספר ספרות מרבי, ו-pos2 הוא המיקום של המספר הראשון שסכום ספרותיו (של ערכו המוחלט) מרבי. בגלל ההשוואה `>` נשמר תמיד המופע הראשון של המקסימום.

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

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

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

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

לדוגמה:

המספרים 22, 2684, 8204, 20 הם "מספרים סופר זוגיים".

המספרים 43, 1233, -22, 442 הם לא "מספרים סופר זוגיים".

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

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

א.

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

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

(8 נקודות)
ב.

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

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

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

סעיף א

תשובה:

שלוש פעולות: isSuperEvenNum(num) – חיובי, כל הספרות זוגיות ומספר הספרות זוגי; isSuperEvenCol(mat, col) – מספר השורות זוגי ויותר ממחצית איברי העמודה סופר זוגיים; isSuperEvenMat(mat) – מספר העמודות זוגי וכל עמודה סופר זוגית.

נתון: מערך דו-ממדי mat (מלבני) עם n שורות ו-m עמודות. מבוקש: האם m זוגי וכל עמודה היא מערך "סופר זוגי".

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

1. isSuperEvenNum(num) – מקבלת מספר שלם ומחזירה true אם הוא "מספר סופר זוגי". מספר שאינו חיובי (0 או שלילי, כמו -22) אינו סופר זוגי לפי ההגדרה. אחרת מפרקים את המספר לספרות: אם יש ספרה אי-זוגית מחזירים false מיד; במקביל סופרים את הספרות, ובסוף בודקים שמספרן זוגי. למשל 2684: כל הספרות זוגיות ויש 4 ספרות – true; 442: 3 ספרות – false.

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

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

שימו לב: העמודות הן הנבדקות, לא השורות. עמודה j מורכבת מהאיברים `mat[0][j], mat[1][j], ..., mat[n-1][j]`.

Java:

// פעולת עזר: האם num הוא "מספר סופר זוגי"
public static boolean isSuperEvenNum(int num)
{
    if (num <= 0)                 // רק מספר חיובי יכול להיות סופר זוגי
        return false;
    int count = 0;                // מספר הספרות
    while (num > 0)
    {
        if (num % 10 % 2 != 0)    // ספרה אי-זוגית
            return false;
        count++;
        num = num / 10;
    }
    return count % 2 == 0;
}

// פעולת עזר: האם העמודה col של mat היא מערך "סופר זוגי"
public static boolean isSuperEvenCol(int[][] mat, int col)
{
    int rows = mat.length;        // אורך העמודה
    if (rows % 2 != 0)
        return false;
    int count = 0;                // כמה מספרים סופר זוגיים בעמודה
    for (int i = 0; i < rows; i++)
    {
        if (isSuperEvenNum(mat[i][col]))
            count++;
    }
    return count > rows / 2;      // יותר ממחצית האיברים
}

public static boolean isSuperEvenMat(int[][] mat)
{
    int cols = mat[0].length;     // מספר העמודות
    if (cols % 2 != 0)
        return false;
    for (int j = 0; j < cols; j++)
    {
        if (!isSuperEvenCol(mat, j))
            return false;
    }
    return true;
}

C#:

// פעולת עזר: האם num הוא "מספר סופר זוגי"
public static bool IsSuperEvenNum(int num)
{
    if (num <= 0)                 // רק מספר חיובי יכול להיות סופר זוגי
        return false;
    int count = 0;                // מספר הספרות
    while (num > 0)
    {
        if (num % 10 % 2 != 0)    // ספרה אי-זוגית
            return false;
        count++;
        num = num / 10;
    }
    return count % 2 == 0;
}

// פעולת עזר: האם העמודה col של mat היא מערך "סופר זוגי"
public static bool IsSuperEvenCol(int[,] mat, int col)
{
    int rows = mat.GetLength(0);  // אורך העמודה
    if (rows % 2 != 0)
        return false;
    int count = 0;                // כמה מספרים סופר זוגיים בעמודה
    for (int i = 0; i < rows; i++)
    {
        if (IsSuperEvenNum(mat[i, col]))
            count++;
    }
    return count > rows / 2;      // יותר ממחצית האיברים
}

public static bool IsSuperEvenMat(int[,] mat)
{
    int cols = mat.GetLength(1);  // מספר העמודות
    if (cols % 2 != 0)
        return false;
    for (int j = 0; j < cols; j++)
    {
        if (!IsSuperEvenCol(mat, j))
            return false;
    }
    return true;
}

דוגמה: עבור המערך

שורהעמודה 0עמודה 1
0223
1482084
2566
3246840

יש 2 עמודות (זוגי) ו-4 שורות (זוגי). בעמודה 0 המספרים 22, 48, 2468 סופר זוגיים – 3 מתוך 4, יותר מחצי. בעמודה 1 – 2084, 66, 40, גם 3 מתוך 4. לכן מוחזר true. אם במקום 2084 היה 7, בעמודה 1 היו רק 2 מתוך 4 (לא יותר מחצי) – false.

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

סעיף ב

תשובה:

O(n⋅m)O(n \cdot m) (n – מספר השורות, m – מספר העמודות).

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

1. isSuperEvenNum: מספר הצעדים כמספר הספרות. למספר מטיפוס int יש לכל היותר 10 ספרות, ולכן זה זמן קבוע O(1)O(1) (באופן כללי O(d)O(d), כאשר d מספר הספרות).

2. isSuperEvenCol: עוברת על nn איברי העמודה וקוראת לפעולה מסעיף 1 על כל אחד – O(n)O(n).

3. isSuperEvenMat: במקרה הגרוע (כל העמודות תקינות) קוראת ל-isSuperEvenCol עבור כל אחת מ-mm העמודות – m⋅O(n)=O(n⋅m)m \cdot O(n) = O(n \cdot m).

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

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

שאלה 13 · רשת מכללות: מחלקות, חיפוש לפי יישוב ומגמה

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

•שם מכללה.

•יישוב שבו נמצא קמפוס לימודי של המכללה.

•מערך המגמות הנלמדות במכללה. בכל מכללה יש לכל היותר עשר מגמות שונות.

כל מגמה מזוהה ע"י מספר המקצוע (code) ושם המגמה (majName).

א.

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

•מגמה Major

•מכללה College

•רשת מכללות Network

(3 נקודות)
ב.

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

(4 נקודות)
ג.

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

אם אין אף מכללה שבה אפשר לפתוח את המגמה יש להחזיר ערך null.

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

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

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

סעיף א

תשובה:

Major: int code, String majName; College: String name, String city, Major[] majors (בגודל 10), int numMajors; Network: College[] colleges (80 מכללות).

לכל מחלקה רושמים את הנתונים שהיא צריכה לשמור, כתכונות פרטיות (private):

1. Major – מגמה מזוהה בקוד המקצוע (מספר שלם) ובשם (מחרוזת).

2. College – שם, יישוב, ומערך מגמות. מכיוון שבמכללה יש לכל היותר 10 מגמות, המערך בגודל 10, ולצדו מונה numMajors שאומר כמה תאים תפוסים בפועל (המגמות נמצאות במקומות 0 עד numMajors-1).

3. Network – הרשת מחזיקה מערך של מכללות (80 מכללות). הקשר בין המחלקות הוא הכלה: רשת מכילה מכללות, ומכללה מכילה מגמות.

Java:

public class Major
{
    private int code;          // מספר המקצוע
    private String majName;    // שם המגמה
}

public class College
{
    private String name;       // שם המכללה
    private String city;       // יישוב הקמפוס
    private Major[] majors;    // מערך המגמות (בגודל 10)
    private int numMajors;     // מספר המגמות בפועל (0-10)
}

public class Network
{
    private College[] colleges;   // 80 המכללות של הרשת
}

C#:

public class Major
{
    private int code;          // מספר המקצוע
    private string majName;    // שם המגמה
}

public class College
{
    private string name;       // שם המכללה
    private string city;       // יישוב הקמפוס
    private Major[] majors;    // מערך המגמות (בגודל 10)
    private int numMajors;     // מספר המגמות בפועל (0-10)
}

public class Network
{
    private College[] colleges;   // 80 המכללות של הרשת
}

בהמשך מניחים שבכל מחלקה קיימות פעולות get לתכונות (getCode, getName, getCity, getNumMajors וכו').

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

סעיף ב

תשובה:

עוברים על colleges; לכל מכללה ש-getCity() שווה לשם היישוב מדפיסים את getName() ומסמנים דגל found; אם בסוף found הוא false – מדפיסים הודעה שאין מכללה ביישוב.

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

1. עוברים על מערך המכללות של הרשת (`this.colleges`).

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

3. אם היישוב זהה – מדפיסים את שם המכללה ומסמנים בדגל `found` שנמצאה לפחות מכללה אחת.

4. אחרי הלולאה, אם `found` עדיין false – מדפיסים הודעה שאין ביישוב מכללה של הרשת.

Java:

// במחלקה Network
public void printColleges(String city)
{
    boolean found = false;    // האם נמצאה מכללה ביישוב
    for (int i = 0; i < this.colleges.length; i++)
    {
        if (this.colleges[i].getCity().equals(city))
        {
            System.out.println(this.colleges[i].getName());
            found = true;
        }
    }
    if (!found)
        System.out.println("There is no college in " + city);
}

C#:

// במחלקה Network
public void PrintColleges(string city)
{
    bool found = false;       // האם נמצאה מכללה ביישוב
    for (int i = 0; i < this.colleges.Length; i++)
    {
        if (this.colleges[i].GetCity() == city)
        {
            Console.WriteLine(this.colleges[i].GetName());
            found = true;
        }
    }
    if (!found)
        Console.WriteLine("There is no college in " + city);
}

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

סעיף ג

תשובה:

פעולת עזר hasMajor(code) במחלקה College; ב-Network: מכללה מתאימה אם getNumMajors() < 10 וגם !hasMajor(code). סופרים את המתאימות; אם 0 מחזירים null, אחרת יוצרים מערך בגודל המונה וממלאים בשמות.

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

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

1. פעולת עזר במחלקה College – `hasMajor(int code)`: טענת כניסה – קוד של מגמה. טענת יציאה – מחזירה true אם במכללה קיימת מגמה עם הקוד הזה, אחרת false. היא עוברת על המגמות במקומות 0 עד numMajors-1 ומשווה את הקוד של כל אחת.

2. מעבר ראשון – ספירה: ב-Network סופרים כמה מכללות מקיימות `getNumMajors() < 10 && !hasMajor(code)`.

3. אם המונה 0 – מחזירים null, כפי שנדרש.

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

Java:

// פעולת עזר במחלקה College
// טענת כניסה: code - קוד של מגמה
// טענת יציאה: true אם במכללה קיימת מגמה עם הקוד code, אחרת false
public boolean hasMajor(int code)
{
    for (int i = 0; i < this.numMajors; i++)
    {
        if (this.majors[i].getCode() == code)
            return true;
    }
    return false;
}

// במחלקה Network
public String[] canOpenMajor(int code)
{
    int count = 0;            // מעבר ראשון: כמה מכללות מתאימות
    for (int i = 0; i < this.colleges.length; i++)
    {
        if (this.colleges[i].getNumMajors() < 10 && !this.colleges[i].hasMajor(code))
            count++;
    }
    if (count == 0)
        return null;          // אין מכללה שבה אפשר לפתוח את המגמה
    String[] names = new String[count];
    int k = 0;
    for (int i = 0; i < this.colleges.length; i++)
    {
        if (this.colleges[i].getNumMajors() < 10 && !this.colleges[i].hasMajor(code))
        {
            names[k] = this.colleges[i].getName();
            k++;
        }
    }
    return names;
}

C#:

// פעולת עזר במחלקה College
// טענת כניסה: code - קוד של מגמה
// טענת יציאה: true אם במכללה קיימת מגמה עם הקוד code, אחרת false
public bool HasMajor(int code)
{
    for (int i = 0; i < this.numMajors; i++)
    {
        if (this.majors[i].GetCode() == code)
            return true;
    }
    return false;
}

// במחלקה Network
public string[] CanOpenMajor(int code)
{
    int count = 0;            // מעבר ראשון: כמה מכללות מתאימות
    for (int i = 0; i < this.colleges.Length; i++)
    {
        if (this.colleges[i].GetNumMajors() < 10 && !this.colleges[i].HasMajor(code))
            count++;
    }
    if (count == 0)
        return null;          // אין מכללה שבה אפשר לפתוח את המגמה
    string[] names = new string[count];
    int k = 0;
    for (int i = 0; i < this.colleges.Length; i++)
    {
        if (this.colleges[i].GetNumMajors() < 10 && !this.colleges[i].HasMajor(code))
        {
            names[k] = this.colleges[i].GetName();
            k++;
        }
    }
    return names;
}

דוגמה: אם ברשת שלוש מכללות – Ort Haifa (מגמה 1 בלבד), Tech TA (ללא מגמות), Carmel (10 מגמות) – אז עבור code = 1 יוחזר {"Tech TA"}, ועבור code = 2 יוחזר {"Ort Haifa", "Tech TA"}. Carmel לעולם לא תופיע, כי יש בה כבר 10 מגמות.

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

שאלה 14 · רקורסיה: הפרשים וסכומים לסירוגין במערך

א.

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

Java:

public static void what (int[] arr, int begin, int end)
{
     if(begin < end)
      {
       what(arr, begin+1, end);
       arr[begin] = arr[begin] - arr[begin+1];
      }
}

C#:

public static void What (int[] arr, int begin, int end)
{
     if(begin < end)
      {
       What(arr, begin+1, end);
       arr[begin] = arr[begin] - arr[begin+1];
      }
}
(1)

עקבו אחר זימון what(brr, 0, brr.length-1) עבור המערך:

brr:

012345
155316108

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

(2)

מהי מטרת הפעולה what? בתשובה יש להתייחס למערך שהפעולה מקבלת כפרמטר.

(5 נקודות)
ב.

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

Java:

public static void where (int[] arr, int begin, int end)
{
     if(begin < end)
    {
       arr[begin] = arr[begin] - arr[begin+1];
       where (arr, begin+1, end);
     }
}

C#:

public static void Where (int[] arr, int begin, int end)
{
     if(begin < end)
    {
       arr[begin] = arr[begin] - arr[begin+1];
       Where (arr, begin+1, end);
     }
}
(1)

אחרי זימון where(crr, 0, crr.length-1) תוכן של מערך crr הוא:

crr:

012345
1-2-1-273

מה היה התוכן של crr לפני ביצוע הזימון?

(2)

מהי מטרת הפעולה where? בתשובה יש להתייחס למערך שהפעולה מקבלת כפרמטר.

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

סעיף א

(1)
תשובה:

brr = {-1, 16, -11, 14, 2, 8}.

בפעולה what הזימון הרקורסיבי מתבצע לפני ההשמה. לכן הזימונים "יורדים" עד begin = end = 5 בלי לשנות דבר, וההשמות מתבצעות בדרך חזרה – מהסוף להתחלה. כל השמה משתמשת ב-`arr[begin+1]` אחרי שכבר עודכן.

ירידה ברקורסיה: what(brr, 0, 5) ← what(brr, 1, 5) ← what(brr, 2, 5) ← what(brr, 3, 5) ← what(brr, 4, 5) ← what(brr, 5, 5) (תנאי העצירה: 5 < 5 לא מתקיים).

חזרה מהרקורסיה:

זימון שמסתייםהשמהbrr אחרי
what(brr, 4, 5)brr[4]=10−8=2brr[4] = 10 - 8 = 2{15, 5, 3, 16, 2, 8}
what(brr, 3, 5)brr[3]=16−2=14brr[3] = 16 - 2 = 14{15, 5, 3, 14, 2, 8}
what(brr, 2, 5)brr[2]=3−14=−11brr[2] = 3 - 14 = -11{15, 5, -11, 14, 2, 8}
what(brr, 1, 5)brr[1]=5−(−11)=16brr[1] = 5 - (-11) = 16{15, 16, -11, 14, 2, 8}
what(brr, 0, 5)brr[0]=15−16=−1brr[0] = 15 - 16 = -1{-1, 16, -11, 14, 2, 8}

תשובה: brr = {-1, 16, -11, 14, 2, 8}.

(2)
תשובה:

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

כש-`arr[begin]` מתעדכן, האיבר `arr[begin+1]` כבר מכיל את הסכום לסירוגין מ-begin+1 עד end. לכן:

arr[i]←arr[i]−(arr[i+1]−arr[i+2]+… )=arr[i]−arr[i+1]+arr[i+2]−⋯±arr[end]arr[i] \leftarrow arr[i] - (arr[i+1] - arr[i+2] + \dots) = arr[i] - arr[i+1] + arr[i+2] - \dots \pm arr[end]

(לפי הערכים המקוריים). בדיקה בסעיף 1: brr[0]=15−5+3−16+10−8=−1brr[0] = 15 - 5 + 3 - 16 + 10 - 8 = -1, וזה אכן מה שהתקבל.

תשובה: הפעולה מחליפה כל איבר במערך arr, מהמקום begin ועד המקום end-1, בסכום לסירוגין של האיברים המקוריים ממקומו ועד המקום end: arr[i]−arr[i+1]+arr[i+2]−⋯±arr[end]arr[i]-arr[i+1]+arr[i+2]-\dots\pm arr[end]. האיבר במקום end ואיברים מחוץ לקטע לא משתנים.

סעיף ב

(1)
תשובה:

crr = {6, 5, 7, 8, 10, 3}.

בפעולה where ההשמה מתבצעת לפני הזימון הרקורסיבי. לכן כשמעדכנים את `arr[begin]`, האיבר `arr[begin+1]` עדיין מקורי, ואחרי הזימון: crr[i]after=crr[i]before−crr[i+1]beforecrr[i]_{after} = crr[i]_{before} - crr[i+1]_{before} לכל i מ-0 עד 4, ו-crr[5]crr[5] לא משתנה.

מכאן crr[i]before=crr[i]after+crr[i+1]beforecrr[i]_{before} = crr[i]_{after} + crr[i+1]_{before}, ומחשבים מהסוף להתחלה:

מקום iחישובcrr[i] לפני
5לא משתנה3
47+37 + 310
3−2+10-2 + 108
2−1+8-1 + 87
1−2+7-2 + 75
01+51 + 56

בדיקה: where על {6, 5, 7, 8, 10, 3} נותנת 6−5=16-5=1, 5−7=−25-7=-2, 7−8=−17-8=-1, 8−10=−28-10=-2, 10−3=710-3=7, ו-3 נשאר – בדיוק המערך הנתון.

תשובה: crr = {6, 5, 7, 8, 10, 3}.

(2)
תשובה:

מחליפה כל איבר במקומות begin עד end-1 בהפרש בינו לבין האיבר המקורי שאחריו; האיבר במקום end לא משתנה.

בכל זימון מעדכנים את `arr[begin]` ל-`arr[begin] - arr[begin+1]`, כשהאיבר `arr[begin+1]` עוד לא שונה, ורק אחר כך עוברים לאיבר הבא. כך כל איבר מקבל את ההפרש בינו לבין שכנו המקורי מימין.

תשובה: הפעולה מחליפה כל איבר במערך arr, מהמקום begin ועד המקום end-1, בהפרש בינו לבין האיבר שאחריו (לפי הערכים המקוריים): arr[i]−arr[i+1]arr[i]-arr[i+1]. האיבר במקום end ואיברים מחוץ לקטע לא משתנים.

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

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

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