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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · קליטת זוגות עד זוג נגדיים

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

דוגמאות למספרים נגדיים: (2, -2), (-10, 10).

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

•כמה מספרים נקלטו.

•סכום של כל המספרים החיוביים שנקלטו.

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

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

פתרון

תשובה:

לולאת while כל עוד a != -b; מגדילים מונה ב-2 בכל זוג, צוברים את המספרים החיוביים וסופרים זוגות שבהם a == b.

הרעיון: מספר הזוגות אינו ידוע מראש, ולכן משתמשים בלולאת while: קולטים זוג לפני הלולאה, וכל עוד הזוג אינו זוג נגדיים מטפלים בו וקולטים את הזוג הבא. שני מספרים a,ba,b נגדיים כאשר a=−ba=-b, ולכן תנאי ההמשך של הלולאה הוא `a != -b`. הזוג הנגדי רק מסמן את סוף הקלט, ולכן אינו נספר.

1. מונה `count` למספרים שנקלטו: בכל סיבוב נקלטים שני מספרים, ולכן מגדילים אותו ב-2.

2. צובר `sumPos`: כל אחד משני המספרים נבדק בנפרד, ואם הוא חיובי (>0>0) מוסיפים אותו לסכום.

3. מונה `equalPairs`: אם `a == b` הזוג הוא זוג של מספרים שווים.

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

שימו לב: זוג של אפסים (0, 0) הוא גם זוג נגדיים (0=−00=-0), ולכן גם הוא מסיים את הקלט.

Java:

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    int count = 0;       // כמה מספרים נקלטו
    int sumPos = 0;      // סכום המספרים החיוביים
    int equalPairs = 0;  // כמה זוגות של מספרים שווים

    int a = in.nextInt();
    int b = in.nextInt();
    while (a != -b)
    {
        count += 2;
        if (a > 0)
            sumPos += a;
        if (b > 0)
            sumPos += b;
        if (a == b)
            equalPairs++;
        a = in.nextInt();
        b = in.nextInt();
    }

    System.out.println("Numbers read: " + count);
    System.out.println("Sum of positives: " + sumPos);
    System.out.println("Equal pairs: " + equalPairs);
}

C#:

static void Main(string[] args)
{
    int count = 0;       // כמה מספרים נקלטו
    int sumPos = 0;      // סכום המספרים החיוביים
    int equalPairs = 0;  // כמה זוגות של מספרים שווים

    int a = int.Parse(Console.ReadLine());
    int b = int.Parse(Console.ReadLine());
    while (a != -b)
    {
        count += 2;
        if (a > 0)
            sumPos += a;
        if (b > 0)
            sumPos += b;
        if (a == b)
            equalPairs++;
        a = int.Parse(Console.ReadLine());
        b = int.Parse(Console.ReadLine());
    }

    Console.WriteLine("Numbers read: " + count);
    Console.WriteLine("Sum of positives: " + sumPos);
    Console.WriteLine("Equal pairs: " + equalPairs);
}

דוגמה: עבור הזוגות (3, 3), (5, -2), (-4, -4), (7, 0) ואחריהם (2, -2) המסיים, יודפס: נקלטו 8 מספרים, סכום החיוביים 3+3+5+7=183+3+5+7=18, ונקלטו 2 זוגות של מספרים שווים: (3, 3) ו-(-4, -4).

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

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

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

יש לבצע את מילוי המערך בלולאה אחת בלבד!

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

פתרון

תשובה:

בלולאה אחת: tens אקראי 1-8, units אקראי tens+1 עד 9, arr[i] = tens*10 + units.

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

1. ספרת העשרות `tens`: המספר דו-ספרתי חיובי, ולכן העשרות לפחות 1. ספרת האחדות צריכה להיות גדולה ממנה ולכל היותר 9, ולכן העשרות לכל היותר 8. מגרילים `tens` בתחום 1..81..8.

2. ספרת האחדות `units`: מגרילים בתחום tens+1..9tens+1..9. לפי ההוראה בדף ההנחיות, מספר אקראי בין XX ל-YY הוא `X + rand.nextInt(Y - X + 1)`; כאן X=tens+1X=tens+1, Y=9Y=9, ולכן מספר הערכים האפשריים הוא 9−(tens+1)+1=9−tens9-(tens+1)+1=9-tens.

3. המספר הוא `tens * 10 + units`. לדוגמה tens=3tens=3, units=7units=7 נותנים 37.

כל תא מתמלא בסיבוב אחד, ולכן יש לולאת for אחת בלבד.

Java:

public static int[] buildArray(int num)
{
    Random rand = new Random();
    int[] arr = new int[num];
    for (int i = 0; i < num; i++)
    {
        int tens = 1 + rand.nextInt(8);                   // 1..8
        int units = tens + 1 + rand.nextInt(9 - tens);    // tens+1..9
        arr[i] = tens * 10 + units;
    }
    return arr;
}

C#:

public static int[] BuildArray(int num)
{
    Random rand = new Random();
    int[] arr = new int[num];
    for (int i = 0; i < num; i++)
    {
        int tens = rand.Next(1, 9);               // 1..8
        int units = rand.Next(tens + 1, 10);      // tens+1..9
        arr[i] = tens * 10 + units;
    }
    return arr;
}

ב-C# הפעולה `rand.Next(a, b)` מחזירה מספר בין aa ל-b−1b-1, ולכן `rand.Next(1, 9)` נותנת 1..81..8 ו-`rand.Next(tens + 1, 10)` נותנת tens+1..9tens+1..9.

כל 36 המספרים המתאימים (12, 13, ..., 19, 23, ..., 89) יכולים להתקבל, ואף מספר אחר אינו יכול להתקבל.

תשובה: הפעולה שלמעלה: לולאה אחת, ובכל תא מגרילים ספרת עשרות 1-8 וספרת אחדות גדולה ממנה (עד 9).

שאלה 3 · בדיקת מערך משולש וסיבוכיות

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

לדוגמה:

•המערך `int[] a = {13,6,3,13,6,3,13,6,3}` הוא "מערך משולש".

•המערך `int[] b = {1,1,1,1,1,1}` הוא "מערך משולש".

•המערך `int[] c = {1,2,3,4,1,2,3,4,1,2,3}` הוא לא "מערך משולש".

•המערך `int[] d = {1,2,1,2,2,2}` הוא לא "מערך משולש".

א.

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

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

(7 נקודות)
ב.

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

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

סעיף א

תשובה:

בודקים ש-n מתחלק ב-3, ואז משווים כל arr[i] ל-arr[i+k] ול-arr[i+2k] עבור i<k=n/3.

הרעיון:

1. אם אורך המערך nn אינו מתחלק ב-3, אי אפשר לחלק אותו לשלושה חלקים שווים, ומחזירים false (כך המערך `c` שאורכו 11).

2. אחרת אורך כל שליש הוא k=n/3k=n/3. השליש הראשון הוא המקומות 0..k−10..k-1, השני k..2k−1k..2k-1 והשלישי 2k..3k−12k..3k-1. התא ה-ii בשליש הראשון מתאים לתאים i+ki+k ו-i+2ki+2k בשני השלישים האחרים.

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

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

Java:

public static boolean isTriple(int[] arr)
{
    int n = arr.length;
    if (n % 3 != 0)
        return false;
    int k = n / 3;                 // אורך כל שליש
    for (int i = 0; i < k; i++)
    {
        if (arr[i] != arr[i + k] || arr[i] != arr[i + 2 * k])
            return false;
    }
    return true;
}

C#:

public static bool IsTriple(int[] arr)
{
    int n = arr.Length;
    if (n % 3 != 0)
        return false;
    int k = n / 3;                 // אורך כל שליש
    for (int i = 0; i < k; i++)
    {
        if (arr[i] != arr[i + k] || arr[i] != arr[i + 2 * k])
            return false;
    }
    return true;
}

בדיקה בדוגמאות: עבור `a` (n=9n=9, k=3k=3): 13=13=1313=13=13, 6=6=66=6=6, 3=3=33=3=3, ולכן true. עבור `d` (n=6n=6, k=2k=2): d[0]=1d[0]=1, d[2]=1d[2]=1 אבל d[4]=2d[4]=2, ולכן false.

תשובה: הפעולה שלמעלה: אם n%3≠0n\%3\ne 0 מחזירה false; אחרת משווה כל arr[i]arr[i] ל-arr[i+k]arr[i+k] ול-arr[i+2k]arr[i+2k] עבור 0≤i<k0\le i<k.

סעיף ב

תשובה:

O(n)O(n): לולאה אחת של n/3n/3 סיבובים עם מספר קבוע של השוואות בכל סיבוב.

נספור כמה פעולות מבצעת הפעולה כפונקציה של אורך המערך nn.

1. הבדיקה `n % 3 != 0` והחישוב של kk הם מספר קבוע של פעולות: O(1)O(1).

2. הלולאה רצה לכל היותר k=n/3k=n/3 פעמים, ובכל סיבוב יש שתי השוואות (מספר קבוע של פעולות).

3. סך הכול לכל היותר n3⋅2+c\frac{n}{3}\cdot 2+c פעולות, כלומר מספר הפעולות גדל באופן ליניארי עם nn (כל תא במערך נבדק פעם אחת לכל היותר).

תשובה: הסיבוכיות היא O(n)O(n) (ליניארית).

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

בבית קולנוע יש שישה אולמות, ממוספרים 1-6, בכל אולם יש 200 מקומות.

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

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

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

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

הנהלת הקולנוע, מעוניינת לקבל בכל ערב (בסיום מכירת הכרטיסים) את המידע הבא:

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

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

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

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

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

פתרון

תשובה:

מערך מונים tickets[1..6]; מדפיסים אולמות 2-6 עם פחות מ-10 צופים, אולמות מקרינים עם 200-tickets[h] מקומות פנויים, ו-ceil(kids/8) פיצות ו-ceil(kids/20) ארגזי טרופית.

הרעיון: בכל קנייה צריך לזכור כמה כרטיסים נמכרו לכל אולם, ולכן מחזיקים מערך מונים `tickets` בגודל 7, שבו `tickets[h]` הוא מספר הכרטיסים שנמכרו לאולם hh (תא 0 אינו בשימוש, כדי שמספר האולם יהיה גם האינדקס).

1. קליטה: קולטים מספר אולם. כל עוד הוא תקין (1≤hall≤61\le hall\le 6) קולטים את כמות הכרטיסים, מוסיפים אותה ל-`tickets[hall]` וקולטים את מספר האולם הבא. מספר אולם לא תקין מסיים את הקלט (בלי לקלוט אחריו כמות).

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

3. אולמות עם מקומות פנויים: אלה האולמות שבהם כן תיערך הקרנה (לפחות 10 צופים) ושמכרו פחות מ-200 כרטיסים. מספר הצופים שאפשר להעביר אליהם הוא מספר המקומות הפנויים 200−tickets[h]200-tickets[h]. את אולם 1 לא כוללים, כי הוא מיועד לסרטי ילדים ואין מעבירים אליו צופים מאולמות אחרים.

4. פיצות וטרופית: מספר הילדים הוא `tickets[1]`. כל ילד מקבל משולש פיצה אחד וטרופית אחת, ולכן צריך ⌈kids/8⌉\lceil kids/8\rceil פיצות ו-⌈kids/20⌉\lceil kids/20\rceil ארגזים (עיגול כלפי מעלה – גם ילד אחד "עודף" מחייב פיצה או ארגז שלמים). בחילוק שלמים מחשבים עיגול כלפי מעלה כך: ⌈a/b⌉\lceil a/b\rceil = `(a + b - 1) / b`.

Java:

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    final int HALLS = 6;          // מספר האולמות
    final int SEATS = 200;        // מקומות בכל אולם
    final int MIN_VIEWERS = 10;   // מינימום צופים להקרנה

    int[] tickets = new int[HALLS + 1];   // tickets[h] = כרטיסים שנמכרו לאולם h (תא 0 לא בשימוש)

    int hall = in.nextInt();
    while (hall >= 1 && hall <= HALLS)
    {
        int amount = in.nextInt();
        tickets[hall] += amount;
        hall = in.nextInt();
    }

    // 1. אולמות שבהם לא תיערך הקרנה (אולם 1 תמיד מקרין)
    System.out.println("Halls without screening:");
    for (int h = 2; h <= HALLS; h++)
        if (tickets[h] < MIN_VIEWERS)
            System.out.println(h);

    // 2. אולמות מקרינים (2-6) עם מקומות פנויים, וכמה צופים אפשר להעביר אליהם
    System.out.println("Halls with free seats:");
    for (int h = 2; h <= HALLS; h++)
        if (tickets[h] >= MIN_VIEWERS && tickets[h] < SEATS)
            System.out.println("hall " + h + ": " + (SEATS - tickets[h]) + " free seats");

    // 3. ארגזי טרופית ופיצות לאולם הילדים
    int kids = tickets[1];
    int pizzas = (kids + 7) / 8;      // עיגול כלפי מעלה של kids/8
    int boxes = (kids + 19) / 20;     // עיגול כלפי מעלה של kids/20
    System.out.println("Pizzas: " + pizzas + ", Tropit boxes: " + boxes);
}

C#:

static void Main(string[] args)
{
    const int HALLS = 6;          // מספר האולמות
    const int SEATS = 200;        // מקומות בכל אולם
    const int MIN_VIEWERS = 10;   // מינימום צופים להקרנה

    int[] tickets = new int[HALLS + 1];   // tickets[h] = כרטיסים שנמכרו לאולם h (תא 0 לא בשימוש)

    int hall = int.Parse(Console.ReadLine());
    while (hall >= 1 && hall <= HALLS)
    {
        int amount = int.Parse(Console.ReadLine());
        tickets[hall] += amount;
        hall = int.Parse(Console.ReadLine());
    }

    // 1. אולמות שבהם לא תיערך הקרנה (אולם 1 תמיד מקרין)
    Console.WriteLine("Halls without screening:");
    for (int h = 2; h <= HALLS; h++)
        if (tickets[h] < MIN_VIEWERS)
            Console.WriteLine(h);

    // 2. אולמות מקרינים (2-6) עם מקומות פנויים, וכמה צופים אפשר להעביר אליהם
    Console.WriteLine("Halls with free seats:");
    for (int h = 2; h <= HALLS; h++)
        if (tickets[h] >= MIN_VIEWERS && tickets[h] < SEATS)
            Console.WriteLine("hall " + h + ": " + (SEATS - tickets[h]) + " free seats");

    // 3. ארגזי טרופית ופיצות לאולם הילדים
    int kids = tickets[1];
    int pizzas = (kids + 7) / 8;      // עיגול כלפי מעלה של kids/8
    int boxes = (kids + 19) / 20;     // עיגול כלפי מעלה של kids/20
    Console.WriteLine("Pizzas: " + pizzas + ", Tropit boxes: " + boxes);
}

דוגמה: עבור הקלט: אולם 1 – 15 כרטיסים, אולם 3 – 5, אולם 2 – 50, אולם 4 – 200, אולם 1 – 2, אולם 5 – 9, אולם 3 – 4, אולם 2 – 30, ואז מספר אולם 7 (לא תקין):

•נמכרו: אולם 1 – 17, אולם 2 – 80, אולם 3 – 9, אולם 4 – 200, אולם 5 – 9, אולם 6 – 0.

•אולמות בלי הקרנה: 3, 5, 6.

•אולמות עם מקומות פנויים: אולם 2, אפשר להעביר אליו 200−80=120200-80=120 צופים (אולם 4 מלא).

•פיצות: ⌈17/8⌉=3\lceil 17/8\rceil=3, ארגזי טרופית: ⌈17/20⌉=1\lceil 17/20\rceil=1.

תשובה: התוכנית שלמעלה (מערך מונים לפי מספר אולם, ואחר כך שלושה חישובים: אולמות 2-6 עם פחות מ-10 צופים, מקומות פנויים 200−tickets[h]200-tickets[h] באולמות המקרינים, ו-⌈kids/8⌉\lceil kids/8\rceil פיצות ו-⌈kids/20⌉\lceil kids/20\rceil ארגזים).

שאלה 5 · מחלקות שיר ודיסק: בנאי, חיפוש והשוואה

המחלקה שיר (`Song`) מאפיין שירים ומורכב משלוש תכונות:

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

•`performer` – שם המבצע, מטיפוס מחרוזת.

•`length` – אורך השיר בשניות, מטיפוס מספר שלם.

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

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

Java:

Song ns=new Song("Ququ",120,"Buku");
System.out.println(ns.status());

C#:

Song ns=new Song("Ququ",120,"Buku");
Console.WriteLine(ns.Status());

התקבל הפלט הבא:

Buku/Ququ:120
א.

כתבו את בנאי המחלקה ואת הפעולה `status()` בהתאם לפלט שהתקבל.

(3 נקודות)

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

•שם הדיסק (`discName`), מטיפוס מחרוזת.

•מערך שירים (מערך עצמים מטיפוס `Song`) `songs`.

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

ב.

כתבו במחלקה `Disc` את הפעולה:

Java:

public boolean  exist(String nSong, String pSong)

C#:

public bool  Exist(string nSong, string pSong)

הפעולה תבדוק אם שיר בעל שם `nSong` ושם המבצע `pSong` נמצא בדיסק.

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

(3 נקודות)
ג.

כתבו את הפעולה החיצונית:

Java:

public static String largeDiscName(Disc d1, Disc d2)

C#:

public static String largeDiscName(Disc d1, Disc d2)

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

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

סעיף א

תשובה:

בנאי Song(String name, int length, String performer); status() מחזירה performer + "/" + name + ":" + length.

הרעיון: את סדר הפרמטרים של הבנאי מסיקים מהזימון `new Song("Ququ",120,"Buku")`: מחרוזת, מספר שלם, מחרוזת. "Ququ" הוא שם השיר, 120 אורכו בשניות, ו-"Buku" הוא המבצע (כי בפלט הוא מופיע לפני הקו הנטוי, ושם השיר אחריו).

1. הבנאי מקבל `(String name, int length, String performer)` ומציב כל פרמטר בתכונה המתאימה.

2. לפי הפלט `Buku/Ququ:120`, הפעולה `status` מחזירה מחרוזת במבנה: מבצע, "/", שם השיר, ":", אורך.

Java:

class Song
{
    private String name;        // שם השיר
    private int length;         // אורך השיר בשניות
    private String performer;   // שם המבצע

    public Song(String name, int length, String performer)
    {
        this.name = name;
        this.length = length;
        this.performer = performer;
    }

    public String status()
    {
        return this.performer + "/" + this.name + ":" + this.length;
    }

    // פעולות get/set ו-toString - כפי שהוגדרו במחלקה
}

C#:

class Song
{
    private string name;        // שם השיר
    private int length;         // אורך השיר בשניות
    private string performer;   // שם המבצע

    public Song(string name, int length, string performer)
    {
        this.name = name;
        this.length = length;
        this.performer = performer;
    }

    public string Status()
    {
        return this.performer + "/" + this.name + ":" + this.length;
    }

    // פעולות Get/Set ו-ToString - כפי שהוגדרו במחלקה
}

תשובה: בנאי `Song(String name, int length, String performer)`, והפעולה `status()` מחזירה `performer + "/" + name + ":" + length`.

סעיף ב

תשובה:

חיפוש סדרתי במערך songs: true אם יש שיר ששמו nSong והמבצע שלו pSong, אחרת false.

הרעיון: חיפוש סדרתי במערך השירים של הדיסק. לכל שיר משווים את שמו ל-`nSong` ואת המבצע שלו ל-`pSong` (בעזרת פעולות ה-get של המחלקה `Song`). רק אם שני התנאים מתקיימים באותו שיר – השיר נמצא, ומחזירים true מיד. אם עברנו על כל המערך ולא מצאנו – מחזירים false.

ב-Java משווים מחרוזות עם `equals` (ולא עם `==`, שמשווה הפניות). הבדיקה `s != null` מגינה למקרה שהמערך אינו מלא עד הסוף.

Java:

public boolean exist(String nSong, String pSong)
{
    for (int i = 0; i < this.songs.length; i++)
    {
        Song s = this.songs[i];
        if (s != null && s.getName().equals(nSong) && s.getPerformer().equals(pSong))
            return true;
    }
    return false;
}

C#:

public bool Exist(string nSong, string pSong)
{
    for (int i = 0; i < this.songs.Length; i++)
    {
        Song s = this.songs[i];
        if (s != null && s.GetName() == nSong && s.GetPerformer() == pSong)
            return true;
    }
    return false;
}

הסיבוכיות היא O(n)O(n), כאשר nn מספר השירים בדיסק.

תשובה: הפעולה שלמעלה: לולאה על `songs`, מחזירה true אם יש שיר שגם שמו `nSong` וגם המבצע שלו `pSong`, אחרת false.

סעיף ג

תשובה:

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

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

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

Java:

public static String largeDiscName(Disc d1, Disc d2)
{
    if (d1.getSongs().length >= d2.getSongs().length)
        return d1.getDiscName();
    return d2.getDiscName();
}

C#:

public static string largeDiscName(Disc d1, Disc d2)
{
    if (d1.GetSongs().Length >= d2.GetSongs().Length)
        return d1.GetDiscName();
    return d2.GetDiscName();
}

תשובה: משווים את `d1.getSongs().length` ל-`d2.getSongs().length` ומחזירים את שם הדיסק שאורך מערך השירים שלו גדול יותר.

שאלה 6 · מעקב: סכום שלושת הגדולים במערך

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

Java:

public static int what(int[] arr)
 {
    int x = arr[0];
    int y = 0;
    int z = 0;
    for (int i = 1; i < arr.length; i++)
    {
        if (arr[i] > x)
        {
            z = y;
            y = x;
            x = arr[i];
        }
        else
          if (arr[i] > y)
          {
             z = y;
             y = arr[i];
          }
          else
            if (arr[i] > z)
            {
                z = arr[i];
            }
    }
    return x + y + z;
}

C#:

public static int What(int[] arr)
 {
    int x = arr[0];
    int y = 0;
    int z = 0;
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] > x)
        {
            z = y;
            y = x;
            x = arr[i];
        }
        else
          if (arr[i] > y)
          {
             z = y;
             y = arr[i];
          }
          else
            if (arr[i] > z)
            {
                z = arr[i];
            }
    }
    return x + y + z;
}
א.

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

`int[] arr={12, 13, 1, 10, 34}`

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

(5 נקודות)
ב.

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

(3 נקודות)
ג.

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

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

סעיף א

תשובה:

59 (x=34x=34, y=13y=13, z=12z=12).

נעקוב אחרי המשתנים. בהתחלה x=arr[0]=12x=arr[0]=12, y=0y=0, z=0z=0. בכל סיבוב בודקים את arr[i]arr[i] מול xx, אחר כך מול yy, ואחר כך מול zz, ומבצעים את הענף הראשון שתנאו מתקיים.

סיבוב (i)arr[i]התנאי שמתקייםxyz
התחלה1200
11313>x=1213>x=1213120
211>z=01>z=013121
31010>z=110>z=1131210
43434>x=1334>x=13341312

בסיבוב 1 ו-4 הערך החדש גדול מ-xx, ולכן כל הערכים "יורדים מדרגה": z←yz\leftarrow y, y←xy\leftarrow x, x←arr[i]x\leftarrow arr[i].

אחרי הלולאה מוחזר x+y+z=34+13+12=59x+y+z=34+13+12=59.

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

סעיף ב

תשובה:

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

1. המשתנים מחזיקים בכל רגע את שלושת הערכים הגדולים ביותר שנראו עד כה: xx הגדול ביותר, yy השני, zz השלישי.

2. כשמגיע ערך גדול מ-xx – הוא הגדול החדש, ו-xx ו-yy הקודמים יורדים למקום השני והשלישי. כשמגיע ערך בין yy ל-xx – הוא השני החדש ו-yy הקודם יורד לשלישי. כשמגיע ערך בין zz ל-yy – הוא מחליף את zz.

3. מכיוון שכל המספרים חיוביים, ההתחלה y=z=0y=z=0 קטנה מכל איבר, ולכן אינה פוגעת בתוצאה.

בסוף הפעולה מחזירה את סכום שלושת המספרים הגדולים ביותר במערך (בדוגמה: 34+13+1234+13+12). אם יש ערכים חוזרים, כל מופע נחשב בנפרד (למשל עבור {5,5,5,1}\{5,5,5,1\} יוחזר 15). אם יש במערך פחות משלושה איברים, יוחזר סכום כל האיברים.

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

סעיף ג

תשובה:

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

1. לפני הלולאה יש שלוש השמות – מספר קבוע של פעולות.

2. הלולאה עוברת פעם אחת על המערך: n−1n-1 סיבובים, כאשר nn אורך המערך.

3. בכל סיבוב יש לכל היותר שלוש השוואות ושלוש השמות – מספר קבוע שאינו תלוי ב-nn.

לכן מספר הפעולות הוא לכל היותר c⋅(n−1)+dc\cdot(n-1)+d, כלומר ליניארי ב-nn.

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

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

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

Java:

public class Student
{
     private String id;  // תעודת זהות
     private int[] arrGradesSemesterA;  // 'מערך ציוני סמסטר א
     private int[] arrGradesSemesterB;  // 'מערך ציוני סמסטר ב
}

C#:

public class Student
{
     private string id;  // תעודת זהות
     private int[] arrGradesSemesterA;  // 'מערך ציוני סמסטר א
     private int[] arrGradesSemesterB;  // 'מערך ציוני סמסטר ב
}

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

•התכונה id מחזיקה את תעודת הזהות של הסטודנט.

•המערכים arrGradesSemesterA ו- arrGradesSemesterB, מחזיקים את ציוני הסטודנט בסמסטר א' ו- ב' בהתאמה עבור הקורסים בסמסטר א' וסמסטר ב', שני המערכים באותו האורך.

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

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

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

א.

כתבו את הפעולה `public boolean isImproved()`.

הפעולה מחזירה true אם סטודנט הוא "סטודנט משתפר" ואם לא, הפעולה מחזירה false.

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

לדוגמה: אם נתון מערך ציוני מחצית א' הבא:

מקום012345
ציון605080-16070

ומערך ציוני מחצית ב':

מקום012345
ציון80909075-170

הפעולה `isImproved` תחזיר true כיוון שעבור כל ציון במחצית א', הציון המתאים במחצית ב' לא היה נמוך יותר, ואילו היה מערך ציוני מחצית ב' הבא:

מקום012345
ציון80905075-170

הפעולה `isImproved` תחזיר false מכיוון שעבור המקצוע השלישי (מיקום 2) הציון בסמסטר ב' היה נמוך יותר מהציון של בסמסטר א'.

(6 נקודות)
ב.

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

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

סעיף א

תשובה:

עוברים על המקצועות המשותפים (שני הציונים שונים מ-1-); false אם באחד מהם gradeB < gradeA; בסוף true רק אם היה מקצוע משותף.

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

1. מקצוע שבו באחד המערכים מופיע −1-1 לא נלמד בשני הסמסטרים – מדלגים עליו.

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

3. בסוף הלולאה לא נמצאה ירידה. מחזירים true רק אם היה לפחות מקצוע משותף אחד (`common > 0`), אחרת false, כנדרש.

הפעולה פנימית במחלקה, ולכן ניגשת לתכונות ישירות.

Java:

public boolean isImproved()
{
    int common = 0;   // כמה מקצועות נלמדו בשני הסמסטרים
    for (int i = 0; i < this.arrGradesSemesterA.length; i++)
    {
        int gradeA = this.arrGradesSemesterA[i];
        int gradeB = this.arrGradesSemesterB[i];
        if (gradeA != -1 && gradeB != -1)
        {
            common++;
            if (gradeB < gradeA)
                return false;      // ירידה במקצוע אחד מספיקה
        }
    }
    return common > 0;
}

C#:

public bool IsImproved()
{
    int common = 0;   // כמה מקצועות נלמדו בשני הסמסטרים
    for (int i = 0; i < this.arrGradesSemesterA.Length; i++)
    {
        int gradeA = this.arrGradesSemesterA[i];
        int gradeB = this.arrGradesSemesterB[i];
        if (gradeA != -1 && gradeB != -1)
        {
            common++;
            if (gradeB < gradeA)
                return false;      // ירידה במקצוע אחד מספיקה
        }
    }
    return common > 0;
}

בדיקה בדוגמה: המקצועות המשותפים הם במקומות 0, 1, 2, 5 (במקום 3 חסר ציון בסמסטר א', ובמקום 4 בסמסטר ב'). במערך ב' הראשון: 80≥6080\ge60, 90≥5090\ge50, 90≥8090\ge80, 70≥7070\ge70 – יוחזר true. במערך ב' השני במקום 2: 50<8050<80 – יוחזר false.

תשובה: הפעולה שלמעלה: false ברגע שנמצא מקצוע משותף שבו הציון ב-B קטן מהציון ב-A; בסוף true רק אם היה לפחות מקצוע משותף אחד.

סעיף ב

תשובה:

שני מעברים: ספירת המשתפרים (בעזרת isImproved), ואז מערך מחרוזות בגודל זה עם תעודות הזהות שלהם; null אם אין.

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

1. מעבר ראשון: סופרים כמה סטודנטים במערך הם משתפרים (`count`).

2. אם `count == 0` – אין אף סטודנט משתפר, ומחזירים null.

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

Java:

public static String[] improvedIds(Student[] arr)
{
    // מעבר ראשון: כמה סטודנטים משתפרים יש
    int count = 0;
    for (int i = 0; i < arr.length; i++)
        if (arr[i].isImproved())
            count++;

    if (count == 0)
        return null;

    // מעבר שני: העתקת תעודות הזהות למערך בגודל המדויק
    String[] ids = new String[count];
    int k = 0;
    for (int i = 0; i < arr.length; i++)
        if (arr[i].isImproved())
        {
            ids[k] = arr[i].getId();
            k++;
        }
    return ids;
}

C#:

public static string[] ImprovedIds(Student[] arr)
{
    // מעבר ראשון: כמה סטודנטים משתפרים יש
    int count = 0;
    for (int i = 0; i < arr.Length; i++)
        if (arr[i].IsImproved())
            count++;

    if (count == 0)
        return null;

    // מעבר שני: העתקת תעודות הזהות למערך בגודל המדויק
    string[] ids = new string[count];
    int k = 0;
    for (int i = 0; i < arr.Length; i++)
        if (arr[i].IsImproved())
        {
            ids[k] = arr[i].GetId();
            k++;
        }
    return ids;
}

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

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

שאלה 8 · מכרז ויקרי: הוספת משתתף ומציאת זוכה

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

נגדיר טיפוס משתתף במכרז – Participant המאופיין כך:

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

•תעודת זהות – id מטיפוס מחרוזת.

•המחיר אותו המשתתף מציע – price מטיפוס שלם.

הטיפוס מכרז ויקרי VickeryAuction מאופיין על-ידי:

•תיאור המוצר הנמכר – product מטיפוס מחרוזת.

•ערך ריאלי של המוצר – realPrice מטיפוס שלם.

•מערך arr בגודל 100 של משתתפים מטיפוס Participant.

•מספר המשתתפים שנרשמו בפועל – current מטיפוס שלם.

א.

כתבו את כותרות המחלקות Participant ו- VickeryAuction ואת התכונות שלהן.

(3 נקודות)

משתתף יכול להתווסף למערך המשתתפים רק אם יש מקום פנוי וכן המחיר שאותו הוא מציע גבוה מ- 50% הערך הריאלי של המוצר.

ב.

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

(2 נקודות)

הטיפוס Winner מאופיין על-ידי שם המשתתף- name, והסכום שעליו לשלם בהתאם לכללי מכרז ויקרי lastPrice.

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

Java:

public Winner(String name, int lastPrice)

C#:

public Winner(string name, int lastPrice)
ג.

כתבו פעולה פנימית במחלקה VickeryAuction המחזירה עצם מטיפוס Winner.

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

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

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

סעיף א

תשובה:

public class Participant עם name, id (String) ו-price (int); public class VickeryAuction עם product (String), realPrice (int), Participant[] arr ו-current (int).

כותרת מחלקה היא `public class` ושם המחלקה, ובתוכה התכונות כמשתנים פרטיים (`private`), כל אחת עם הטיפוס שנקבע בשאלה. המערך `arr` הוא מערך של עצמים מטיפוס `Participant`; את גודלו (100) קובעים בבנאי, למשל `this.arr = new Participant[100];`, ובבנאי גם מאתחלים `current = 0`.

Java:

public class Participant
{
    private String name;   // שם המשתתף
    private String id;     // תעודת זהות
    private int price;     // המחיר שהמשתתף מציע
}

public class VickeryAuction
{
    private String product;          // תיאור המוצר הנמכר
    private int realPrice;           // ערך ריאלי של המוצר
    private Participant[] arr;       // מערך המשתתפים (בגודל 100)
    private int current;             // מספר המשתתפים שנרשמו בפועל
}

C#:

public class Participant
{
    private string name;   // שם המשתתף
    private string id;     // תעודת זהות
    private int price;     // המחיר שהמשתתף מציע
}

public class VickeryAuction
{
    private string product;          // תיאור המוצר הנמכר
    private int realPrice;           // ערך ריאלי של המוצר
    private Participant[] arr;       // מערך המשתתפים (בגודל 100)
    private int current;             // מספר המשתתפים שנרשמו בפועל
}

תשובה: שתי המחלקות שלמעלה עם התכונות הפרטיות name, id, price ו-product, realPrice, arr, current.

סעיף ב

תשובה:

אם current < arr.length וגם 2⋅price>realPrice2\cdot price>realPrice: arr[current++] = p ומחזירים true; אחרת false.

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

1. יש מקום פנוי אם `current < arr.length` (כלומר פחות מ-100 משתתפים).

2. המחיר גבוה מ-50% מהערך הריאלי אם price>0.5⋅realPriceprice>0.5\cdot realPrice. כדי להישאר במספרים שלמים כותבים זאת כ-2⋅price>realPrice2\cdot price>realPrice.

3. אם שני התנאים מתקיימים – מכניסים את המשתתף לתא `arr[current]`, מגדילים את `current` ומחזירים true. אחרת מחזירים false.

Java:

public boolean addParticipant(Participant p)
{
    // יש מקום פנוי, והמחיר המוצע גבוה מ-50% מהערך הריאלי
    if (this.current < this.arr.length && p.getPrice() * 2 > this.realPrice)
    {
        this.arr[this.current] = p;
        this.current++;
        return true;
    }
    return false;
}

C#:

public bool AddParticipant(Participant p)
{
    // יש מקום פנוי, והמחיר המוצע גבוה מ-50% מהערך הריאלי
    if (this.current < this.arr.Length && p.GetPrice() * 2 > this.realPrice)
    {
        this.arr[this.current] = p;
        this.current++;
        return true;
    }
    return false;
}

דוגמה: עבור realPrice=1000realPrice=1000: הצעה של 500 נדחית (2⋅500=10002\cdot500=1000, לא גבוה יותר), והצעה של 501 מתקבלת.

תשובה: מוסיפים את p ל-arr[current] ומחזירים true אם current < 100 וגם 2⋅price>realPrice2\cdot price>realPrice; אחרת false.

סעיף ג

תשובה:

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

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

1. `first` – האינדקס של ההצעה הגבוהה ביותר עד כה; `second` – האינדקס של השנייה בגובהה.

2. לפי ההנחה יש לפחות שני משתתפים, ולכן מאתחלים לפי שני הראשונים: הגבוה מביניהם ב-`first` והשני ב-`second`.

3. לכל משתתף נוסף (ii מ-2 עד `current-1`): אם ההצעה שלו גבוהה מ-`first` – הוא המוביל החדש, והמוביל הקודם יורד למקום השני. אחרת, אם היא גבוהה מ-`second` – הוא השני החדש.

4. בסוף יוצרים עצם `Winner` עם שם הזוכה `arr[first]` והסכום `arr[second].getPrice()`.

Java:

public Winner getWinner()
{
    // first - אינדקס ההצעה הגבוהה ביותר, second - אינדקס ההצעה השנייה בגובהה
    int first = 0, second = 1;
    if (this.arr[1].getPrice() > this.arr[0].getPrice())
    {
        first = 1;
        second = 0;
    }
    for (int i = 2; i < this.current; i++)
    {
        int price = this.arr[i].getPrice();
        if (price > this.arr[first].getPrice())
        {
            second = first;
            first = i;
        }
        else if (price > this.arr[second].getPrice())
            second = i;
    }
    return new Winner(this.arr[first].getName(), this.arr[second].getPrice());
}

C#:

public Winner GetWinner()
{
    // first - אינדקס ההצעה הגבוהה ביותר, second - אינדקס ההצעה השנייה בגובהה
    int first = 0, second = 1;
    if (this.arr[1].GetPrice() > this.arr[0].GetPrice())
    {
        first = 1;
        second = 0;
    }
    for (int i = 2; i < this.current; i++)
    {
        int price = this.arr[i].GetPrice();
        if (price > this.arr[first].GetPrice())
        {
            second = first;
            first = i;
        }
        else if (price > this.arr[second].GetPrice())
            second = i;
    }
    return new Winner(this.arr[first].GetName(), this.arr[second].GetPrice());
}

דוגמה: משתתפים עם הצעות 501 (רינה), 1500 (אבי), 1200 (נועה): אחרי האתחול firstfirst=אבי, secondsecond=רינה; נועה (1200) אינה גבוהה מ-1500 אבל גבוהה מ-501, ולכן היא השנייה. הזוכה – אבי, ומשלם 1200.

תשובה: מעבר אחד על המשתתפים ששומר את האינדקסים של ההצעה הגבוהה ביותר ושל השנייה בגובהה; מוחזר `new Winner(arr[first].getName(), arr[second].getPrice())`.

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

מחרוזת "יפה" היא מחרוזת אשר מורכבת מאותיות גדולות וקטנות בלבד כך שכמות אותיות a שווה לכמות אותיות A, כמות אותיות b שווה לכמות אותיות B וכו'.

לדוגמה: מחרוזת `faBdBAbbDF` היא מחרוזת "יפה".

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

תזכורת: באלפבית האנגלי יש 26 אותיות גדולות ו- 26 אותיות קטנות.

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

פתרון

תשובה:

מערך מונים בגודל 26: אות גדולה מוסיפה 1, אות קטנה מחסירה 1; מחזירים true אם כל המונים 0.

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

1. האינדקס של אות גדולה `ch` הוא `ch - 'A'` (למשל 'A' → 0, 'B' → 1), ושל אות קטנה `ch - 'a'`. לפי ההגדרה מחרוזת "יפה" מורכבת מאותיות בלבד, ולכן אם מופיע תו שאינו אות (ספרה, רווח וכו') – מחזירים מיד false.

2. עוברים פעם אחת על המחרוזת ומעדכנים את המונים.

3. עוברים על 26 התאים: אם יש תא שונה מ-0, יש אות שכמות הגדולות שלה שונה מכמות הקטנות – מחזירים false. אחרת – true.

Java:

public static boolean isNice(String str)
{
    int[] count = new int[26];   // count[k] = (כמות האות הגדולה) - (כמות האות הקטנה) של האות ה-k
    for (int i = 0; i < str.length(); i++)
    {
        char ch = str.charAt(i);
        if (ch >= 'A' && ch <= 'Z')
            count[ch - 'A']++;
        else if (ch >= 'a' && ch <= 'z')
            count[ch - 'a']--;
        else
            return false;        // תו שאינו אות - המחרוזת אינה "יפה"
    }
    for (int k = 0; k < 26; k++)
        if (count[k] != 0)
            return false;
    return true;
}

C#:

public static bool IsNice(string str)
{
    int[] count = new int[26];   // count[k] = (כמות האות הגדולה) - (כמות האות הקטנה) של האות ה-k
    for (int i = 0; i < str.Length; i++)
    {
        char ch = str[i];
        if (ch >= 'A' && ch <= 'Z')
            count[ch - 'A']++;
        else if (ch >= 'a' && ch <= 'z')
            count[ch - 'a']--;
        else
            return false;        // תו שאינו אות - המחרוזת אינה "יפה"
    }
    for (int k = 0; k < 26; k++)
        if (count[k] != 0)
            return false;
    return true;
}

בדיקה בדוגמה `faBdBAbbDF`: האות f/F – קטנה אחת וגדולה אחת (הפרש 0); a/A – 1 ו-1; b/B – שתי קטנות ושתי גדולות; d/D – 1 ו-1. כל המונים 0, ולכן מוחזר true. לעומת זאת עבור "aAb" המונה של b יהיה −1-1 ויוחזר false.

סיבוכיות: O(n)O(n) למעבר על המחרוזת ועוד 26 בדיקות קבועות.

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

שאלה 10 · זוגות זהב: ספרות קצה ומספר ספרות

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

לדוגמה: מספרים 17723 ו- 18113, 3456 ו- 3786, 34 ו- 34 מהווים "זוגות זהב".

א.

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

(5 נקודות)
ב.

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

אם אין אף "זוג זהב" תודפס הודעה מתאימה.

(5 נקודות)
ג.

מהן סיבוכיות של הפעולות שכתבתם בסעיפים א' ו- ב'? בתשובה יש להתייחס גם לגודל המערך וגם למספר הספרות באיברי המערך.

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

סעיף א

תשובה:

בודקים a%10 == b%10, מחלקים את שניהם ב-10 יחד עד שאחד חד-ספרתי, ומחזירים true אם שניהם חד-ספרתיים ושווים.

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

1. ספרת האחדות היא `num % 10`. אם היא שונה בשני המספרים – מחזירים false.

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

3. כשהלולאה נעצרת, אם לשניהם אותו מספר ספרות, שניהם נעשו חד-ספרתיים באותו סיבוב, והם עכשיו הספרה השמאלית של כל מספר. אם לאחד יותר ספרות, הוא עדיין ≥10\ge 10, ומחזירים false.

4. לכן התשובה היא true אם שניהם <10<10 וגם שווים.

Java:

public static boolean isGoldenPair(int a, int b)
{
    // ספרת האחדות (הקצה הימני)
    if (a % 10 != b % 10)
        return false;
    // מורידים ספרות משני המספרים יחד עד שאחד מהם הופך לחד-ספרתי
    while (a >= 10 && b >= 10)
    {
        a = a / 10;
        b = b / 10;
    }
    // אם מספר הספרות שווה - שניהם חד-ספרתיים עכשיו, וזו הספרה השמאלית של כל אחד
    return a < 10 && b < 10 && a == b;
}

C#:

public static bool IsGoldenPair(int a, int b)
{
    // ספרת האחדות (הקצה הימני)
    if (a % 10 != b % 10)
        return false;
    // מורידים ספרות משני המספרים יחד עד שאחד מהם הופך לחד-ספרתי
    while (a >= 10 && b >= 10)
    {
        a = a / 10;
        b = b / 10;
    }
    // אם מספר הספרות שווה - שניהם חד-ספרתיים עכשיו, וזו הספרה השמאלית של כל אחד
    return a < 10 && b < 10 && a == b;
}

בדיקה בדוגמה 17723 ו-18113: ספרות האחדות 3=33=3; אחרי ארבע חלוקות: 11 ו-11 – true. לעומת זאת 343 ו-33: אחרי חלוקה אחת 3434 ו-33, הלולאה נעצרת ו-34 עדיין דו-ספרתי – false.

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

סעיף ב

תשובה:

שתי לולאות על כל הזוגות i<j, מדפיסים כל זוג זהב (בעזרת סעיף א'), והודעה אם אין.

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

Java:

public static void printGoldenPairs(int[] arr)
{
    boolean found = false;
    for (int i = 0; i < arr.length - 1; i++)
        for (int j = i + 1; j < arr.length; j++)
            if (isGoldenPair(arr[i], arr[j]))
            {
                System.out.println(arr[i] + " , " + arr[j]);
                found = true;
            }
    if (!found)
        System.out.println("There are no golden pairs in the array");
}

C#:

public static void PrintGoldenPairs(int[] arr)
{
    bool found = false;
    for (int i = 0; i < arr.Length - 1; i++)
        for (int j = i + 1; j < arr.Length; j++)
            if (IsGoldenPair(arr[i], arr[j]))
            {
                Console.WriteLine(arr[i] + " , " + arr[j]);
                found = true;
            }
    if (!found)
        Console.WriteLine("There are no golden pairs in the array");
}

דוגמה: עבור המערך {17723,34,3456,18113,34,3786,5}\{17723, 34, 3456, 18113, 34, 3786, 5\} יודפסו הזוגות: 17723 , 18113; 34 , 34; 3456 , 3786.

תשובה: שתי לולאות מקוננות על כל הזוגות i<ji<j, הדפסת כל זוג שעבורו הפעולה מסעיף א' מחזירה true, והודעה אם לא נמצא אף זוג.

סעיף ג

תשובה:

א' – O(d)O(d); ב' – O(n2⋅d)O(n^2\cdot d) (nn גודל המערך, dd מספר הספרות).

נסמן ב-nn את גודל המערך וב-dd את מספר הספרות המרבי של איבר במערך.

1. סעיף א': הלולאה מורידה בכל סיבוב ספרה אחת, ולכן מתבצעת לכל היותר dd פעמים: O(d)O(d).

2. סעיף ב': מספר הזוגות שנבדקים הוא (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(d)O(d). סך הכול O(n2⋅d)O(n^2\cdot d).

אם מספר הספרות חסום (למשל int, עד 10 ספרות), dd הוא קבוע, ואז הסיבוכיות היא O(1)O(1) בסעיף א' ו-O(n2)O(n^2) בסעיף ב'.

תשובה: סעיף א' – O(d)O(d); סעיף ב' – O(n2⋅d)O(n^2\cdot d).

שאלה 11 · מספר מיוחד ומערך מיוחד

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

א.

כתבו פעולה סטטית שחתימתה:

Java:

public static boolean specialNumber(int num)

C#:

public static bool SpecialNumber(int num)

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

דוגמאות:

•עבור הזימון `specialNumber(12551)` הפעולה מחזירה true (1+5+1=2+51 + 5 + 1 = 2 + 5).

•עבור הזימון `specialNumber(4254)` הפעולה מחזירה false (4+5≠2+44 + 5 \neq 2 + 4).

•עבור הזימון `specialNumber(4)` הפעולה מחזירה false (כי המספר חד ספרתי).

•עבור הזימון `specialNumber(-561)` הפעולה מחזירה false (כי הוא לא חיובי).

(4 נקודות)

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

לדוגמה:

•המערך `arr = {12551, 6215, 77, 4254, 4, -561}` הוא "מערך מיוחד" (המספרים המיוחדים: 12551, 6215, 77).

•המערך `brr = {12551, 4, 6215, 77, 4254, -561}` הוא לא "מערך מיוחד" (המספרים המיוחדים: 12551, 6215, 77).

ב.

כתבו פעולה `isSpecialArray(int[] arr)`. הפעולה מקבלת מערך מספרים שלמים ומחזירה true אם הוא "מערך מיוחד", ולא הפעולה תחזיר false.

(7 נקודות)
ג.

כתבו פעולה `buildSpecialArray(int[] arr1, int[] arr2)`. הפעולה מקבלת שני מערכים של מספרים שלמים `arr1, arr2` ומחזירה מערך חדש שהוא "מערך מיוחד" הכולל את כל הערכים שנמצאים ב- `arr1` ואת כל הערכים שנמצאים ב- `arr2`.

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

סעיף א

תשובה:

false אם num < 10; אחרת סוכמים את הספרות לסירוגין לשני סכומים ומחזירים אם הם שווים.

הרעיון:

1. מספר שאינו חיובי או שהוא חד-ספרתי אינו מיוחד. שני המקרים יחד הם בדיוק `num < 10`, ומחזירים false.

2. מפרקים את המספר לספרות מימין לשמאל (`num % 10` נותן את הספרה הימנית, `num / 10` מוריד אותה). משתנה בוליאני `even` מתחלף בכל ספרה, וכך הספרות נצברות לסירוגין לשני סכומים: `sumEven` ו-`sumOdd`.

3. בסוף מחזירים אם שני הסכומים שווים.

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

Java:

public static boolean specialNumber(int num)
{
    if (num < 10)              // לא חיובי, או חד-ספרתי
        return false;
    int sumEven = 0, sumOdd = 0;
    boolean even = true;       // הספרה הנוכחית במקום זוגי?
    while (num > 0)
    {
        if (even)
            sumEven += num % 10;
        else
            sumOdd += num % 10;
        even = !even;
        num = num / 10;
    }
    return sumEven == sumOdd;
}

C#:

public static bool SpecialNumber(int num)
{
    if (num < 10)              // לא חיובי, או חד-ספרתי
        return false;
    int sumEven = 0, sumOdd = 0;
    bool even = true;          // הספרה הנוכחית במקום זוגי?
    while (num > 0)
    {
        if (even)
            sumEven += num % 10;
        else
            sumOdd += num % 10;
        even = !even;
        num = num / 10;
    }
    return sumEven == sumOdd;
}

בדיקה בדוגמאות: 12551 – הספרות מימין: 1, 5, 5, 2, 1; sumEven=1+5+1=7sumEven=1+5+1=7, sumOdd=5+2=7sumOdd=5+2=7 – true. 4254 – הספרות מימין: 4, 5, 2, 4; sumEven=4+2=6sumEven=4+2=6, sumOdd=5+4=9sumOdd=5+4=9 – false. 4 ו-561- נפסלים כבר בבדיקה `num < 10`.

תשובה: הפעולה שלמעלה: false אם num<10num<10, אחרת סוכמת את הספרות לסירוגין לשני סכומים ומחזירה אם הם שווים.

סעיף ב

תשובה:

מדלגים על הרצף ההתחלתי של מספרים מיוחדים; false אם אחריו יש עוד מספר מיוחד, אחרת true.

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

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

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

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

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

Java:

public static boolean isSpecialArray(int[] arr)
{
    int i = 0;
    // מדלגים על הרצף ההתחלתי של מספרים מיוחדים
    while (i < arr.length && specialNumber(arr[i]))
        i++;
    // מכאן והלאה אסור שיופיע מספר מיוחד
    while (i < arr.length)
    {
        if (specialNumber(arr[i]))
            return false;
        i++;
    }
    return true;
}

C#:

public static bool IsSpecialArray(int[] arr)
{
    int i = 0;
    // מדלגים על הרצף ההתחלתי של מספרים מיוחדים
    while (i < arr.Length && SpecialNumber(arr[i]))
        i++;
    // מכאן והלאה אסור שיופיע מספר מיוחד
    while (i < arr.Length)
    {
        if (SpecialNumber(arr[i]))
            return false;
        i++;
    }
    return true;
}

בדיקה בדוגמאות: ב-`arr` הלולאה הראשונה עוברת על 12551, 6215, 77 ונעצרת ב-4254; האיברים 4254, 4, 561- אינם מיוחדים – true. ב-`brr` הלולאה הראשונה נעצרת ב-4 (מקום 1), והלולאה השנייה פוגשת את 6215 שהוא מיוחד – false.

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

סעיף ג

תשובה:

מערך בגודל arr1.length+arr2.length; מספרים מיוחדים נכתבים מתחילתו ולא-מיוחדים מסופו.

הרעיון: המערך החדש מכיל את כל האיברים של שני המערכים, ולכן גודלו arr1.length+arr2.lengtharr1.length+arr2.length. כדי שיהיה "מערך מיוחד" צריך שכל המספרים המיוחדים יהיו בתחילתו וכל הלא-מיוחדים אחריהם. משתמשים בשני מצביעים:

1. `front` – מתחיל ב-0 ומתקדם ימינה: לשם נכנס כל מספר מיוחד.

2. `back` – מתחיל בתא האחרון ומתקדם שמאלה: לשם נכנס כל מספר לא מיוחד.

3. עוברים על `arr1` ואחר כך על `arr2`, ולכל איבר בודקים בעזרת הפעולה מסעיף א' לאיזה צד הוא שייך.

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

Java:

public static int[] buildSpecialArray(int[] arr1, int[] arr2)
{
    int[] res = new int[arr1.length + arr2.length];
    int front = 0;               // המקום הבא למספר מיוחד (מתחילת המערך)
    int back = res.length - 1;   // המקום הבא למספר לא מיוחד (מסוף המערך)

    for (int i = 0; i < arr1.length; i++)
    {
        if (specialNumber(arr1[i]))
        {
            res[front] = arr1[i];
            front++;
        }
        else
        {
            res[back] = arr1[i];
            back--;
        }
    }
    for (int i = 0; i < arr2.length; i++)
    {
        if (specialNumber(arr2[i]))
        {
            res[front] = arr2[i];
            front++;
        }
        else
        {
            res[back] = arr2[i];
            back--;
        }
    }
    return res;
}

C#:

public static int[] BuildSpecialArray(int[] arr1, int[] arr2)
{
    int[] res = new int[arr1.Length + arr2.Length];
    int front = 0;               // המקום הבא למספר מיוחד (מתחילת המערך)
    int back = res.Length - 1;   // המקום הבא למספר לא מיוחד (מסוף המערך)

    for (int i = 0; i < arr1.Length; i++)
    {
        if (SpecialNumber(arr1[i]))
        {
            res[front] = arr1[i];
            front++;
        }
        else
        {
            res[back] = arr1[i];
            back--;
        }
    }
    for (int i = 0; i < arr2.Length; i++)
    {
        if (SpecialNumber(arr2[i]))
        {
            res[front] = arr2[i];
            front++;
        }
        else
        {
            res[back] = arr2[i];
            back--;
        }
    }
    return res;
}

דוגמה: עבור arr1={4,12551,−561}arr1=\{4, 12551, -561\} ו-arr2={6215,4254,77}arr2=\{6215, 4254, 77\} יוחזר {12551,6215,77,4254,−561,4}\{12551, 6215, 77, 4254, -561, 4\} – שלושת המיוחדים בהתחלה, וזהו "מערך מיוחד".

תשובה: מערך חדש בגודל סכום האורכים; מעבר על שני המערכים, מספר מיוחד נכתב מההתחלה (front++) ומספר לא מיוחד מהסוף (back--).

שאלה 12 · נמל תעופה: מחלקות טיסה וזמן

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

לצורך כך נגדיר שלוש מחלקות: Airport, Flight, Time

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

Java:

public class Time
{
    public Time(int hour, int minute){…}
    public boolean before(Time other) {…}
    …
}

C#:

public class Time
{
    public Time(int hour, int minute){…}
    public bool Before(Time other) {…}
    …
}

המחלקה מכילה:

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

•פעולה בוליאנית `before(Time other)` המקבלת הפנייה לאובייקט אחר (other) מסוג Time ומחזירה true אם הזמן המיוצג על-ידי האובייקט שמפעיל את הפעולה (this) קודם לזמן המיוצג באמצעות other ולא הפעולה מחזירה false.

•במחלקה Time הוגדרו פעולות get ו- set ופעולה toString.

•המחלקה Time כבר נתונה ואפשר להשתמש בפעולות שבה אין צורך לממש אותן!

המחלקה Flight מייצגת טיסה.

תכונות המחלקה הן:

•code – קוד בין לאומי של הטיסה, מטיפוס String.

•destination – שם העיר שבה נוחתת הטיסה, מטיפוס String.

•departureTime – זמן ההמראה של הטיסה, מטיפוס Time.

•duration – משך זמן הטיסה בדקות, מטיפוס int.

•int numOfPassengers – מספר הנוסעים בטיסה, מטיפוס int.

•isFull – האם הטיסה מלאה, מטיפוס boolean.

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

במחלקה Flight הוגדרו פעולות get ו- set ופעולה toString. אין צורך לממש אותן!

א.

כתבו למחלקה Flight את הפעולות הבאות:

(1)

פעולה הבונה (בנאי, constructor) שמקבל כפרמטרים:

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

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

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

(2)

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

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

Java:

public boolean addPassengers (int num)

C#:

public bool AddPassengers (int num)
(3)

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

Java:

public Time getArrivalTime()

C#:

public Time GetArrivalTime()
(6 נקודות)

המחלקה Airport מייצגת את לוח הטיסות בשדה התעופה ביממה.

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

•מערך של הטיסות: `Flight [] flightsSchedule`

•מספר הטיסות בלוח הטיסות (במערך): `int numOfFlights`

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

המערך צריך להישאר כך (ללא חורים) לאחר כל פעולה.

ב.

כתבו במחלקה Airport את הפעולות הבאות:

(1)

פעולה `firstFlightToPlace` המקבלת עיר כלשהי place, מחזירה את הזמן בו ממריאה הטיסה הראשונה למקום place. אם אין אף טיסה למקום place יוחזר null.

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

Java:

public Time firstFlightToPlace(String place)

C#:

public Time FirstFlightToPlace(string place)
(2)

פעולה `movePassengers` מקבלת קוד טיסה codeF ומספר שלם num המייצג מספר נוסעים שרוצים להקדים את הטיסה שלהם. הקדמת הטיסה אפשרית אם מתקיימים תנאים הבאים:

•קיימת טיסה אחרת לאותה עיר הנחיתה וטיסה זו נוחתת לפני הטיסה codeF.

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

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

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

Java:

public boolean movePassengers(String codeF, int num)

C#:

public bool MovePassengers(string codeF, int num)

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

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

סעיף א

(1)
תשובה:

בנאי שמציב את התכונות, יוצר departureTime = new Time(hour, minute) וקובע isFull = (numOfPassengers == MAX_CAPACITY).

הרעיון: הבנאי מציב כל פרמטר בתכונה המתאימה. את שעת ההמראה מקבלים כשני מספרים (שעה ודקה), ולכן יוצרים מהם עצם חדש `new Time(hour, minute)`. התכונה `isFull` לא מתקבלת כפרמטר: היא true רק אם מספר הנוסעים שווה לקיבולת המרבית `MAX_CAPACITY` (הפרמטרים תקינים, ולכן אין יותר נוסעים מהמותר).

שלוש הפעולות של סעיף א' כחלק מהמחלקה Flight (הערך של `MAX_CAPACITY` אינו נתון בשאלה; 200 הוא ערך לדוגמה):

Java:

class Flight
{
    public static final int MAX_CAPACITY = 200;   // לדוגמה

    private String code;
    private String destination;
    private Time departureTime;
    private int duration;
    private int numOfPassengers;
    private boolean isFull;

    // 1. פעולה בונה
    public Flight(String code, String destination, int hour, int minute,
                  int duration, int numOfPassengers)
    {
        this.code = code;
        this.destination = destination;
        this.departureTime = new Time(hour, minute);
        this.duration = duration;
        this.numOfPassengers = numOfPassengers;
        this.isFull = (numOfPassengers == MAX_CAPACITY);
    }

    // 2. הוספת נוסעים
    public boolean addPassengers(int num)
    {
        if (this.numOfPassengers + num > MAX_CAPACITY)
            return false;                       // אין מקום לכולם - לא מוסיפים אף אחד
        this.numOfPassengers += num;
        this.isFull = (this.numOfPassengers == MAX_CAPACITY);
        return true;
    }

    // 3. זמן הנחיתה
    public Time getArrivalTime()
    {
        int total = this.departureTime.getHour() * 60
                  + this.departureTime.getMinute() + this.duration;   // דקות מתחילת היממה
        return new Time((total / 60) % 24, total % 60);
    }

    // פעולות get/set ו-toString - נתונות
}

C#:

class Flight
{
    public const int MAX_CAPACITY = 200;   // לדוגמה

    private string code;
    private string destination;
    private Time departureTime;
    private int duration;
    private int numOfPassengers;
    private bool isFull;

    // 1. פעולה בונה
    public Flight(string code, string destination, int hour, int minute,
                  int duration, int numOfPassengers)
    {
        this.code = code;
        this.destination = destination;
        this.departureTime = new Time(hour, minute);
        this.duration = duration;
        this.numOfPassengers = numOfPassengers;
        this.isFull = (numOfPassengers == MAX_CAPACITY);
    }

    // 2. הוספת נוסעים
    public bool AddPassengers(int num)
    {
        if (this.numOfPassengers + num > MAX_CAPACITY)
            return false;                       // אין מקום לכולם - לא מוסיפים אף אחד
        this.numOfPassengers += num;
        this.isFull = (this.numOfPassengers == MAX_CAPACITY);
        return true;
    }

    // 3. זמן הנחיתה
    public Time GetArrivalTime()
    {
        int total = this.departureTime.GetHour() * 60
                  + this.departureTime.GetMinute() + this.duration;   // דקות מתחילת היממה
        return new Time((total / 60) % 24, total % 60);
    }

    // פעולות Get/Set ו-ToString - נתונות
}

תשובה: הבנאי `Flight(code, destination, hour, minute, duration, numOfPassengers)` מציב את התכונות, יוצר `departureTime = new Time(hour, minute)` וקובע `isFull = (numOfPassengers == MAX_CAPACITY)`.

(2)
תשובה:

אם numOfPassengers + num > MAX_CAPACITY מחזירים false; אחרת מוסיפים, מעדכנים isFull ומחזירים true.

הרעיון: ההוספה מותרת רק אם כל num הנוסעים נכנסים, כלומר אם numOfPassengers+num≤MAX_CAPACITYnumOfPassengers+num\le MAX\_CAPACITY.

1. אם הסכום חורג מהקיבולת – לא משנים דבר ומחזירים false.

2. אחרת מוסיפים את num למספר הנוסעים.

3. מעדכנים את `isFull`: הטיסה מלאה אם מספר הנוסעים הגיע בדיוק לקיבולת.

4. מחזירים true.

(הקוד – בפעולה `addPassengers` במחלקה שבסעיף 1.)

דוגמה: עבור MAX_CAPACITY=200MAX\_CAPACITY=200 וטיסה עם 195 נוסעים: הוספת 5 מצליחה ו-`isFull` נעשה true; הוספה נוספת של נוסע אחד נכשלת ומחזירה false.

תשובה: אם numOfPassengers+num>MAX_CAPACITYnumOfPassengers+num>MAX\_CAPACITY מחזירים false; אחרת מוסיפים, מעדכנים `isFull = (numOfPassengers == MAX_CAPACITY)` ומחזירים true.

(3)
תשובה:

total = hour*60 + minute + duration; מוחזר new Time((total/60)%24, total%60).

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

1. total=hour⋅60+minute+durationtotal=hour\cdot 60+minute+duration.

2. השעה היא ⌊total/60⌋\lfloor total/60\rfloor, והדקה היא total mod 60total\bmod 60.

3. אם הטיסה נוחתת אחרי חצות, השעה עוברת את 23, ולכן לוקחים אותה מודולו 24 (הבנאי של Time מקבל שעה 0-23).

4. מחזירים עצם Time חדש.

(הקוד – בפעולה `getArrivalTime` במחלקה שבסעיף 1.)

דוגמה: המראה ב-10:30 ומשך 200 דקות: total=10⋅60+30+200=830total=10\cdot60+30+200=830, שעה ⌊830/60⌋=13\lfloor 830/60\rfloor=13, דקה 830 mod 60=50830\bmod 60=50 – נחיתה ב-13:50. המראה ב-23:10 ומשך 300 דקות: total=1690total=1690, שעה 28 mod 24=428\bmod 24=4, דקה 10 – נחיתה ב-04:10.

תשובה: `total = hour*60 + minute + duration`, ומוחזר `new Time((total/60) % 24, total % 60)`.

סעיף ב

(1)
תשובה:

חיפוש מינימום (בעזרת before) של זמני ההמראה של הטיסות ליעד place; null אם אין.

הרעיון: זה חיפוש מינימום, אבל רק בין הטיסות שהיעד שלהן הוא place. הטיסות נמצאות ברצף במקומות 0..numOfFlights−10..numOfFlights-1.

1. המשתנה `first` שומר את זמן ההמראה המוקדם ביותר שנמצא עד כה. בהתחלה הוא null – עוד לא נמצאה אף טיסה ל-place.

2. לכל טיסה שהיעד שלה הוא place: אם זו הטיסה הראשונה שנמצאה (`first == null`), או שזמן ההמראה שלה קודם ל-`first` (בעזרת הפעולה `before` של Time) – מעדכנים את `first`.

3. בסוף מחזירים את `first`. אם לא נמצאה אף טיסה, נשאר null, כנדרש.

Java:

public Time firstFlightToPlace(String place)
{
    Time first = null;   // זמן ההמראה המוקדם ביותר שנמצא עד עכשיו
    for (int i = 0; i < this.numOfFlights; i++)
    {
        Flight f = this.flightsSchedule[i];
        if (f.getDestination().equals(place))
        {
            if (first == null || f.getDepartureTime().before(first))
                first = f.getDepartureTime();
        }
    }
    return first;
}

C#:

public Time FirstFlightToPlace(string place)
{
    Time first = null;   // זמן ההמראה המוקדם ביותר שנמצא עד עכשיו
    for (int i = 0; i < this.numOfFlights; i++)
    {
        Flight f = this.flightsSchedule[i];
        if (f.GetDestination() == place)
        {
            if (first == null || f.GetDepartureTime().Before(first))
                first = f.GetDepartureTime();
        }
    }
    return first;
}

תשובה: חיפוש מינימום בעזרת `before` על זמני ההמראה של הטיסות שהיעד שלהן place; null אם אין כאלה.

(2)
תשובה:

מוצאים את codeF, מחפשים טיסה אחרת לאותו יעד שנוחתת לפניה ושבה addPassengers(num) מצליחה; מפחיתים num מהמקורית, isFull=false, מדפיסים את הקוד החדש ומחזירים true; אחרת הודעה ו-false.

הרעיון: שלושה שלבים:

1. מוצאים את הטיסה המקורית `from` – הטיסה שהקוד שלה codeF (חיפוש סדרתי עם `getCode().equals`).

2. מחפשים טיסה חלופית `other` שמקיימת את כל התנאים:

•זו טיסה אחרת (`other != from`) לאותה עיר נחיתה (`getDestination`);

•היא נוחתת לפני הטיסה המקורית: `other.getArrivalTime().before(from.getArrivalTime())` (הפעולה מסעיף א3 והפעולה `before` של Time);

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

3. מעדכנים את הנתונים: בטיסה החלופית הנוסעים כבר נוספו (כולל עדכון `isFull` שלה בתוך `addPassengers`). בטיסה המקורית מפחיתים num נוסעים, ומכיוון שירדו ממנה נוסעים היא בוודאי אינה מלאה: `setIsFull(false)`. מדפיסים את קוד הטיסה החדשה ומחזירים true.

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

Java:

public boolean movePassengers(String codeF, int num)
{
    // שלב 1: חיפוש הטיסה codeF
    Flight from = null;
    for (int i = 0; i < this.numOfFlights; i++)
        if (this.flightsSchedule[i].getCode().equals(codeF))
            from = this.flightsSchedule[i];

    if (from != null)
    {
        // שלב 2: חיפוש טיסה אחרת לאותו יעד שנוחתת לפניה ויש בה מקום ל-num נוסעים
        for (int i = 0; i < this.numOfFlights; i++)
        {
            Flight other = this.flightsSchedule[i];
            if (other != from
                && other.getDestination().equals(from.getDestination())
                && other.getArrivalTime().before(from.getArrivalTime())
                && other.addPassengers(num))          // מוסיפה רק אם יש מקום לכולם
            {
                // שלב 3: עדכון הטיסה המקורית
                from.setNumOfPassengers(from.getNumOfPassengers() - num);
                from.setIsFull(false);
                System.out.println(other.getCode());
                return true;
            }
        }
    }
    System.out.println("The flight cannot be brought forward");
    return false;
}

C#:

public bool MovePassengers(string codeF, int num)
{
    // שלב 1: חיפוש הטיסה codeF
    Flight from = null;
    for (int i = 0; i < this.numOfFlights; i++)
        if (this.flightsSchedule[i].GetCode() == codeF)
            from = this.flightsSchedule[i];

    if (from != null)
    {
        // שלב 2: חיפוש טיסה אחרת לאותו יעד שנוחתת לפניה ויש בה מקום ל-num נוסעים
        for (int i = 0; i < this.numOfFlights; i++)
        {
            Flight other = this.flightsSchedule[i];
            if (other != from
                && other.GetDestination() == from.GetDestination()
                && other.GetArrivalTime().Before(from.GetArrivalTime())
                && other.AddPassengers(num))          // מוסיפה רק אם יש מקום לכולם
            {
                // שלב 3: עדכון הטיסה המקורית
                from.SetNumOfPassengers(from.GetNumOfPassengers() - num);
                from.SetIsFull(false);
                Console.WriteLine(other.GetCode());
                return true;
            }
        }
    }
    Console.WriteLine("The flight cannot be brought forward");
    return false;
}

דוגמה: טיסה LY001 לרומא ממריאה ב-10:30 ל-200 דקות (נוחתת ב-13:50) עם 150 נוסעים, וטיסה LY004 לרומא ממריאה ב-09:00 ל-230 דקות (נוחתת ב-12:50) עם 100 נוסעים. הזימון `movePassengers("LY001", 30)` מדפיס LY004 ומחזיר true; אחריו ב-LY001 יש 120 נוסעים וב-LY004 – 130.

תשובה: מוצאים את הטיסה codeF, מחפשים טיסה אחרת לאותו יעד שנוחתת לפניה ושבה `addPassengers(num)` מצליחה; אז מפחיתים num מהטיסה המקורית, קובעים לה isFull=false, מדפיסים את קוד הטיסה החדשה ומחזירים true; אחרת הודעה ו-false.

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

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

Java:

public static char fun1(String s){
    while (s.length() > 1){
        if (s.charAt(1) < s.charAt(0))
            s = s.substring(1);
        else
            s = s.charAt(0) + s.substring(2);
    }
    return s.charAt(0);
}
public static String fun2(String s, char c){
    int i=0;
    while( i < s.length() && s.charAt(i) != c){
        i++;
    }
    if (i < s.length())
        s = s.substring(0, i) + s.substring(i + 1);
    return s;
}
public static String something(String s){
    String ans = "";
    while (s.length() > 0){
        char a = fun1(s);
        s = fun2(s, a);
        ans = ans + a;
    }
    return ans;
}

C#:

public static char Fun1(string s){
    while (s.Length > 1){
        if (s[1] < s[0])
            s = s.Substring(1);
        else
            s = s[0] + s.Substring(2);
    }
    return s[0];
}
public static string Fun2(string s, char c){
    int i=0;
    while( i < s.Length && s[i] != c){
        i++;
    }
    if (i < s.Length)
        s = s.Substring(0, i) + s.Substring(i + 1);
    return s;
}
public static string Something(string s){
    string ans = "";
    while (s.Length > 0){
        char a = Fun1(s);
        s = Fun2(s, a);
        ans = ans + a;
    }
    return ans;
}
א.

עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `fun1("BANANA")` ורשמו מה תחזיר הפעולה.

(5 נקודות)
ב.

עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `fun2("BANANA",'N')` ורשמו מה תחזיר הפעולה.

(5 נקודות)
ג.

עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `something("BANANA")` ורשמו מה תחזיר הפעולה. אין צורך לעקוב אחרי פעולות fun1 ו- fun2.

(5 נקודות)
ד.

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

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

סעיף א

תשובה:

'A'

בכל סיבוב משווים את התו השני לתו הראשון. אם התו השני קטן יותר – מוחקים את הראשון (`s.substring(1)`); אחרת – מוחקים את השני (`s.charAt(0) + s.substring(2)`). כך התו הקטן מבין השניים נשאר תמיד בהתחלה.

סיבובs בתחילת הסיבובs.charAt(1) < s.charAt(0)?s אחרי הסיבוב
1BANANA'A' < 'B' – כןANANA
2ANANA'N' < 'A' – לאAANA
3AANA'A' < 'A' – לאANA
4ANA'N' < 'A' – לאAA
5AA'A' < 'A' – לאA

עכשיו s.length()=1s.length()=1, הלולאה מסתיימת ומוחזר `s.charAt(0)`.

תשובה: הפעולה מחזירה את התו 'A' (התו הקטן ביותר במחרוזת).

סעיף ב

תשובה:

"BAANA"

הלולאה מקדמת את `i` עד שנמצא התו 'N' (או עד סוף המחרוזת).

ערך is.charAt(i)i < 6 וגם s.charAt(i) != 'N'?
0Bכן – i++
1Aכן – i++
2Nלא – יציאה מהלולאה

מכיוון ש-i=2<6i=2<6, מוחקים את התו במקום 2: `s.substring(0, 2) + s.substring(3)` = "BA" + "ANA" = "BAANA".

תשובה: הפעולה מחזירה "BAANA" (המחרוזת בלי המופע הראשון של 'N').

סעיף ג

תשובה:

"AAABNN"

כפי שראינו, `fun1(s)` מחזירה את התו הקטן ביותר ב-s, ו-`fun2(s, a)` מוחקת את המופע הראשון של a. בכל סיבוב של `something`:

סיבובs לפניa = fun1(s)s = fun2(s, a)ans
התחלהBANANA""
1BANANAABNANAA
2BNANAABNNAAA
3BNNAABNNAAA
4BNNBNNAAAB
5NNNNAAABN
6NN""AAABNN

כעת s.length()=0s.length()=0 והלולאה מסתיימת.

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

סעיף ד

תשובה:

מחזירה את תווי המחרוזת ממוינים בסדר עולה (מיון בחירה).

1. `fun1` מחזירה את התו הקטן ביותר במחרוזת (לפי סדר קודי התווים).

2. `fun2` מוחקת מהמחרוזת את המופע הראשון של התו הזה.

3. `something` חוזרת על כך עד שהמחרוזת מתרוקנת, ובכל פעם מוסיפה את התו הקטן ביותר שנותר לסוף `ans`.

כך התווים נוספים ל-`ans` מהקטן לגדול – זהו מיון בחירה (selection sort) של תווי המחרוזת.

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

שאלה 14 · מערך דו-ממדי: תאים עצובים

הגדרה:

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

- "תא פנימי" במערך דו-ממדי הוא איבר שלא נמצא במסגרת המערך.

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

ערך שנימצא ב"תא עצוב" נקרא "ערך עצוב".

לדוגמא:

•תא (1,1) הוא "תא עצוב" כי ערכים של כל שכנים שלו שונים מערכו. שכנים של תא (1,1) מסומנים באפור. ערך 10 הוא "ערך עצוב".

•גם תא (3,2) הוא תא "עצוב", ערך 21 הוא ערך עצוב.

•גם תא (1,4) הוא תא "עצוב", ערך 123 הוא ערך עצוב.

•תא (2,3) או תא (3,3) הם לא "עצובים".

א.

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

(6 נקודות)
ב.

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

(6 נקודות)
ג.

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

עבור דוגמה הנ"ל הפעולה תדפיס 21.

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

סעיף א

תשובה:

מעבר על התאים הפנימיים; true אם יש תא שערכו num וכל שמונת שכניו שונים ממנו (פעולת עזר isSadCell).

הרעיון: נכתוב פעולת עזר `isSadCell(arr, i, j)` שבודקת אם תא פנימי הוא "עצוב", ונשתמש בה גם בסעיפים ב' ו-ג'.

1. פעולת העזר: שמונת השכנים של התא (i,j)(i,j) הם כל התאים (r,c)(r,c) עם i−1≤r≤i+1i-1\le r\le i+1 ו-j−1≤c≤j+1j-1\le c\le j+1, חוץ מהתא עצמו. עוברים עליהם בשתי לולאות; אם לאחד מהם אותו ערך – התא אינו עצוב. מכיוון שהתא פנימי, כל שמונת השכנים נמצאים בתוך המערך ואין חריגה מהגבולות.

2. הפעולה הראשית: עוברים רק על התאים הפנימיים – שורות 1..rows−21..rows-2 ועמודות 1..cols−21..cols-2. אם נמצא תא שערכו num והוא עצוב – מחזירים true. אם לא נמצא – false.

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

Java:

// האם התא הפנימי (i, j) הוא "תא עצוב"
public static boolean isSadCell(int[][] arr, int i, int j)
{
    for (int r = i - 1; r <= i + 1; r++)
        for (int c = j - 1; c <= j + 1; c++)
            if ((r != i || c != j) && arr[r][c] == arr[i][j])
                return false;
    return true;
}

public static boolean isSadValue(int[][] arr, int num)
{
    for (int i = 1; i < arr.length - 1; i++)
        for (int j = 1; j < arr[i].length - 1; j++)
            if (arr[i][j] == num && isSadCell(arr, i, j))
                return true;
    return false;
}

C#:

// האם התא הפנימי (i, j) הוא "תא עצוב"
public static bool IsSadCell(int[,] arr, int i, int j)
{
    for (int r = i - 1; r <= i + 1; r++)
        for (int c = j - 1; c <= j + 1; c++)
            if ((r != i || c != j) && arr[r, c] == arr[i, j])
                return false;
    return true;
}

public static bool IsSadValue(int[,] arr, int num)
{
    for (int i = 1; i < arr.GetLength(0) - 1; i++)
        for (int j = 1; j < arr.GetLength(1) - 1; j++)
            if (arr[i, j] == num && IsSadCell(arr, i, j))
                return true;
    return false;
}

בדיקה בדוגמה: עבור num=10: התא (1,1)(1,1) פנימי, ערכו 10 וכל שכניו (5, 4, 1, 1, 7, 6, 1, 7) שונים מ-10 – יוחזר true. עבור num=7: בתא (1,2)(1,2) השכן (2,2)(2,2) הוא 7, ובתא (2,2)(2,2) השכן (1,2)(1,2) הוא 7 – יוחזר false.

תשובה: הפעולה שלמעלה: מעבר על התאים הפנימיים, ו-true אם יש תא שערכו num וכל שמונת שכניו שונים ממנו.

סעיף ב

תשובה:

איסוף ערכי התאים העצובים בלי כפילויות למערך עזר והעתקה למערך בגודל המדויק; null אם אין. בדוגמה: {10, 123, 21}.

הרעיון: מספר הערכים העצובים אינו ידוע מראש, אבל הוא לכל היותר מספר התאים הפנימיים (rows−2)(cols−2)(rows-2)(cols-2). לכן:

1. יוצרים מערך עזר `temp` בגודל זה ומונה `count` של הערכים שנאספו.

2. עוברים על כל התאים הפנימיים. לכל תא עצוב (פעולת העזר מסעיף א') בודקים אם הערך שלו כבר נמצא ב-`temp` (בין 00 ל-count−1count-1). רק אם לא – מוסיפים אותו. כך כל ערך מופיע פעם אחת בלבד, כנדרש.

3. אם `count == 0` (או שאין בכלל תאים פנימיים) מחזירים null.

4. אחרת מעתיקים את `count` הערכים הראשונים של `temp` למערך בגודל המדויק ומחזירים אותו.

Java:

public static int[] sadValues(int[][] arr)
{
    int rows = arr.length, cols = arr[0].length;
    if (rows < 3 || cols < 3)
        return null;                         // אין תאים פנימיים
    int[] temp = new int[(rows - 2) * (cols - 2)];
    int count = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (isSadCell(arr, i, j))
            {
                // בודקים שהערך עוד לא נכנס למערך
                boolean exists = false;
                for (int k = 0; k < count; k++)
                    if (temp[k] == arr[i][j])
                        exists = true;
                if (!exists)
                {
                    temp[count] = arr[i][j];
                    count++;
                }
            }
    if (count == 0)
        return null;
    int[] res = new int[count];
    for (int k = 0; k < count; k++)
        res[k] = temp[k];
    return res;
}

C#:

public static int[] SadValues(int[,] arr)
{
    int rows = arr.GetLength(0), cols = arr.GetLength(1);
    if (rows < 3 || cols < 3)
        return null;                         // אין תאים פנימיים
    int[] temp = new int[(rows - 2) * (cols - 2)];
    int count = 0;
    for (int i = 1; i < rows - 1; i++)
        for (int j = 1; j < cols - 1; j++)
            if (IsSadCell(arr, i, j))
            {
                // בודקים שהערך עוד לא נכנס למערך
                bool exists = false;
                for (int k = 0; k < count; k++)
                    if (temp[k] == arr[i, j])
                        exists = true;
                if (!exists)
                {
                    temp[count] = arr[i, j];
                    count++;
                }
            }
    if (count == 0)
        return null;
    int[] res = new int[count];
    for (int k = 0; k < count; k++)
        res[k] = temp[k];
    return res;
}

בדיקה בדוגמה: התאים העצובים במערך הם (1,1)=10(1,1)=10, (1,4)=123(1,4)=123 ו-(3,2)=21(3,2)=21 (בכל שאר התאים הפנימיים יש שכן עם אותו ערך), ולכן יוחזר המערך {10,123,21}\{10, 123, 21\}.

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

סעיף ג

תשובה:

מקסימום בין ערכי התאים העצובים בתחום 10-99, או הודעה אם אין; בדוגמה 21.

הרעיון: חיפוש מקסימום מותנה: עוברים על התאים הפנימיים, ומתעניינים רק בתא שערכו מספר דו-ספרתי חיובי (10≤v≤9910\le v\le 99) והוא עצוב (פעולת העזר מסעיף א').

1. המשתנה `max` מאותחל ל-−1-1 – ערך שאינו דו-ספרתי, ולכן מסמן "עוד לא נמצא".

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

3. בסוף: אם `max` נשאר −1-1 – מדפיסים הודעה, ואחרת מדפיסים את `max`.

Java:

public static void printMaxTwoDigitSad(int[][] arr)
{
    int max = -1;   // עדיין לא נמצא ערך מתאים
    for (int i = 1; i < arr.length - 1; i++)
        for (int j = 1; j < arr[i].length - 1; j++)
        {
            int v = arr[i][j];
            if (v >= 10 && v <= 99 && v > max && isSadCell(arr, i, j))
                max = v;
        }
    if (max == -1)
        System.out.println("There is no sad cell with a positive two-digit value");
    else
        System.out.println(max);
}

C#:

public static void PrintMaxTwoDigitSad(int[,] arr)
{
    int max = -1;   // עדיין לא נמצא ערך מתאים
    for (int i = 1; i < arr.GetLength(0) - 1; i++)
        for (int j = 1; j < arr.GetLength(1) - 1; j++)
        {
            int v = arr[i, j];
            if (v >= 10 && v <= 99 && v > max && IsSadCell(arr, i, j))
                max = v;
        }
    if (max == -1)
        Console.WriteLine("There is no sad cell with a positive two-digit value");
    else
        Console.WriteLine(max);
}

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

תשובה: חיפוש מקסימום בין ערכי התאים העצובים שבתחום 10-99; בדוגמה יודפס 21, ואם אין כזה – הודעה.

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

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

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