בגרות במדעי המחשב יסודות מדעי המחשב 899371 - קיץ 2024

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

רעיון: arr[i]/10 היא חלוקה בשלמים – היא "מורידה" את ספרת האחדות. לכן num%10 היא ספרת העשרות של arr[i]. הקטע סופר כמה תאים יש שבהם ספרת העשרות של הערך שווה לאינדקס של התא.

פתרון – טבלת מעקב:

בסיום הקטע: count = 2.

בדיקה: על המערך מתקבל count = 2.

טעות נפוצה: לחשוב ש־ num%10 היא ספרת האחדות של arr[i]. היא ספרת האחדות של num, כלומר ספרת העשרות של arr[i]. למשל עבור 6: ‏6/10 = 0, ולכן digit = 0 (ולא 6).

מה נדרש: מערך בגודל 4 של מספרים חיוביים שעבורו count נשאר 0.

רעיון: count גדל רק כאשר ספרת העשרות של arr[i] שווה ל־ i (כאשר i הוא 0, 1, 2 או 3). די לבחור מספרים שספרת העשרות שלהם אינה אף אחד מן הערכים 0–3, למשל ספרת עשרות 9 בכל התאים.

פתרון: למשל

בכל תא: num = 9, digit = 9, ו־ 9 שונה מכל אינדקס 0–3, ולכן count נשאר 0.

בדיקה: על {99, 99, 99, 99} מתקבל count = 0. (יש עוד תשובות נכונות רבות.)

טעות נפוצה: לבחור מספרים חד־ספרתיים (למשל {5, 5, 5, 5}). עבורם num = 0 ו־ digit = 0, ובתא 0 מתקיים digit==i, ולכן count יהיה 1 ולא 0.

מה נדרש: מערך בגודל 4 של מספרים חיוביים שעבורו count = 4 בסוף.

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

פתרון: למשל

בדיקה: על {5, 12, 23, 34} מתקבל count = 4. (שימו לב: בתא 0 צריך מספר חיובי שספרת העשרות שלו 0, כמו מספר חד־ספרתי או 105.)

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

רעיון:

פתרון:

public static boolean getPass(int[] arr, int password)
{
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] == password)
            return false;
    }
    for (int i = arr.length - 1; i > 0; i--)
    {
        arr[i] = arr[i - 1];
    }
    arr[0] = password;
    return true;
}

בדיקה (על המערך מהשאלה):

טעות נפוצה: להזיז משמאל לימין (for i = 1 ...: arr[i] = arr[i-1]). כך הערך של תא 0 מועתק לכל התאים ושאר הסיסמאות נמחקות. ההזזה ימינה חייבת להתחיל מהתא האחרון.

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

רעיון:

פתרון:

public static void shuffle(int[] arr)
{
    Random rnd = new Random();
    int count = 0;
    while (count < 30)
    {
        int i = rnd.nextInt(arr.length);
        int j = rnd.nextInt(arr.length);
        if (i != j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            count++;
        }
    }
    for (int k = 0; k < arr.length; k++)
    {
        System.out.println(arr[k]);
    }
}

(ב־ Java צריך import java.util.Random; בראש הקובץ. אפשר גם להגריל בעזרת (int)(Math.random() * arr.length).)

בדיקה: על המערך {10, 20, 30, 40, 50, 60, 70} מודפסות 7 שורות, והתוצאה היא סידור מחדש של אותם ערכים (הסדר משתנה מהפעלה להפעלה). בדיקה נוספת שמוודאת שנספרות בדיוק 30 החלפות אמיתיות: במערך בן 2 תאים {1, 2} כל החלפה אמיתית מחליפה את שני התאים, ואחרי 30 החלפות (מספר זוגי) המערך חוזר להיות {1, 2}.

טעות נפוצה: לספור את הסיבוב גם כאשר i==j (לולאת for של 30 סיבובים), בניגוד להערה בשאלה. (הערה: הפעולה מניחה שבמערך יש לפחות 2 תאים, אחרת אי אפשר להגריל שני אינדקסים שונים.)

מה נדרש: פעולה בונה שמקבלת ארבעה פרמטרים ומאתחלת את חמש התכונות (extra ל־ 0).

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

פתרון (תחילת המחלקה: התכונות והפעולה הבונה):

public class TourPackage
{
    private int id;
    private int price;
    private int maxTime;
    private int maxData;
    private int extra;

    public TourPackage(int id, int price, int maxTime, int maxData)
    {
        this.id = id;
        this.price = price;
        this.maxTime = maxTime;
        this.maxData = maxData;
        this.extra = 0;
    }

    // ... (setExtra ופעולות get בהמשך המחלקה)
// }

בדיקה: new TourPackage(111, 50, 100, 10) – ‏getExtra() החזירה 0, ושאר ה־ get החזירו את הערכים שהתקבלו.

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

רעיון:

פתרון:

public void setExtra(int minutes, int usage)
{
    int sum = 0;
    if (minutes > this.maxTime)
        sum = sum + (minutes - this.maxTime) * 1;
    if (usage > this.maxData)
        sum = sum + (usage - this.maxData) * 2;
    this.extra = sum;
}

בדיקה (חבילה עם maxTime = 100, maxData = 10):

טעות נפוצה: לחשב (minutes - maxTime) + (usage - maxData) * 2 בלי תנאים. כאשר השימוש קטן מהחבילה, ההפרש שלילי ו"מקזז" את החריגה בחלק השני – ומתקבל סכום שגוי.

מה נדרש: לספור כמה חבילות במערך יש להן extra גדול מ־ 0.

רעיון: לקוח צריך לשלם תוספת אם ורק אם extra > 0 (ה־ extra כבר חושב). עוברים על המערך וסופרים בעזרת getExtra().

פתרון:

public static int calculate(TourPackage[] packages)
{
    int count = 0;
    for (int i = 0; i < packages.length; i++)
    {
        if (packages[i].getExtra() > 0)
            count++;
    }
    return count;
}

בדיקה: מערך של 4 חבילות עם extra = 34, 0, 6, 15 (מספרי זיהוי 111, 222, 333, 444) → הוחזר 3.

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

רעיון:

פתרון:

public static int[] customers(TourPackage[] packages)
{
    int[] ids = new int[calculate(packages)];
    int k = 0;
    for (int i = 0; i < packages.length; i++)
    {
        if (packages[i].getExtra() > 0)
        {
            ids[k] = packages[i].getId();
            k++;
        }
    }
    return ids;
}

בדיקה: על אותו מערך (extra = 34, 0, 6, 15) הוחזר המערך {111, 333, 444}. על מערך שבו אף לקוח לא חרג הוחזר מערך באורך 0.

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

מה נדרש: להשוות את שעת ההתחלה של השיעור הנוכחי (this) לשעת ההתחלה של other.

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

פתרון:

public boolean isLater(Lesson other)
{
    int thisStart = this.hh * 60 + this.mm;
    int otherStart = other.getHh() * 60 + other.getMm();
    return thisStart > otherStart;
}

(אפשר גם בלי המרה: hh > other.getHh() || (hh == other.getHh() && mm > other.getMm()).)

בדיקה: 13:05 לעומת 13:00 → true; ‏13:00 לעומת 13:05 → false; ‏8:00 לעומת 10:15 → false; שיעור לעומת עצמו → false.

טעות נפוצה: להשוות רק את הדקות או רק את השעות, או hh > other.hh && mm > other.mm – שנותן false עבור 13:05 לעומת 12:30.

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

רעיון: חיפוש "מקסימום" במערך לא ממוין: מחזיקים הפניה לשיעור המאוחר ביותר שנמצא עד עכשיו (latest), ומתחילים מ־ arr[0]. לכל שיעור אחר בודקים בעזרת isLater (סעיף א(1)) אם הוא מתחיל מאוחר יותר מ־ latest, ואם כן – מעדכנים. בסוף מדפיסים את ה־ id של latest.

פתרון (בשאלה מופיע רק השם last; ב־ C# נקרא לפעולה Last לפי המוסכמה):

public static void last(Lesson[] arr)
{
    Lesson latest = arr[0];
    for (int i = 1; i < arr.length; i++)
    {
        if (arr[i].isLater(latest))
            latest = arr[i];
    }
    System.out.println(latest.getId());
}

בדיקה: על מערך של 6 שיעורים שמתחילים ב־ 10:15, 8:00, 12:30, 13:05, 9:45, 13:00 (עם הקודים 5, 7, 5, 3, 9, 3) הודפס 3 (השיעור של 13:05). על מערך נוסף שבו המאוחר הוא האחרון הודפס הקוד שלו (2).

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

מה נדרש: סכום משכי כל השיעורים שקוד המקצוע שלהם שווה ל־ id.

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

פתרון:

public static int sumDuration(Lesson[] arr, int id)
{
    int sum = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i].getId() == id)
            sum = sum + arr[i].getDuration();
    }
    return sum;
}

בדיקה: באותו מערך – למקצוע 5 יש שיעורים של 40 ו־ 70 דקות → הוחזר 110 (כמו בדוגמה בשאלה); למקצוע 3 (45 + 20) → 65; למקצוע שאינו במערך → 0.

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

רעיון: לכל שיעור במערך מחשבים בעזרת sumDuration (סעיף ב(1)) את סך הדקות של המקצוע שלו, ומחפשים מקסימום. מתחילים מהמקצוע של arr[0]. כאשר נמצא סכום גדול יותר (השוואה חזקה), מעדכנים את הסכום המקסימלי ואת קוד המקצוע. מקצוע שמופיע כמה פעמים ייבדק כמה פעמים – זה לא מזיק, כי הסכום שלו זהה בכל פעם.

פתרון:

public static int longest(Lesson[] arr)
{
    int maxId = arr[0].getId();
    int maxSum = sumDuration(arr, maxId);
    for (int i = 1; i < arr.length; i++)
    {
        int sum = sumDuration(arr, arr[i].getId());
        if (sum > maxSum)
        {
            maxSum = sum;
            maxId = arr[i].getId();
        }
    }
    return maxId;
}

בדיקה: במערך מסעיף א(2) הסכומים הם: מקצוע 5 – 110, מקצוע 7 – 90, מקצוע 3 – 65, מקצוע 9 – 100 → הוחזר 5. במערך שבו המקסימום שייך למקצוע של התא הראשון (1: ‏70 דקות; 2: ‏30+30) הוחזר 1.

הערה על יעילות: לכל אחד מ־ n התאים מופעלת sumDuration שעוברת על n תאים, כלומר בערך n² פעולות – זה פתרון פשוט ומתאים לשאלה, שדורשת להיעזר ב־ sumDuration.

מה נדרש: להפעיל digitSum שוב ושוב עד שמתקבל מספר חד־ספרתי, ולהחזיר אותו.

רעיון: מספר אי־שלילי הוא חד־ספרתי אם ורק אם הוא קטן מ־ 10. לכן: כל עוד num1 ≥ 10 – מחליפים אותו בסכום הספרות שלו. מספר חד־ספרתי (כמו 5) לא נכנס ללולאה כלל ומוחזר כמו שהוא.

פתרון:

public static int deepSum(int num1)
{
    while (num1 >= 10)
    {
        num1 = digitSum(num1);
    }
    return num1;
}

בדיקה: 5 → 5; ‏36 → 9; ‏942378 → 33 → 6; ‏0 → 0; ‏999999999 → 81 → 9.

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

רעיון: עוברים בלולאה על כל i מ־ 1 עד 999999, מחשבים deepSum(i) (סעיף א(1)) וסופרים בשני מונים: זוגי ואי־זוגי. בסוף מחזירים את תוצאת ההשוואה countEven > countOdd.

פתרון:

public static boolean isCorrect()
{
    int countEven = 0;
    int countOdd = 0;
    for (int i = 1; i <= 999999; i++)
    {
        if (deepSum(i) % 2 == 0)
            countEven++;
        else
            countOdd++;
    }
    return countEven > countOdd;
}

בדיקה: מתקבל countEven = 444444, ‏countOdd = 555555, ולכן הפעולה מחזירה false – הטענה אינה נכונה.
הסבר מתמטי (לא נדרש בבחינה): "סכום הספרות העמוק" של מספר חיובי חוזר במחזור 1, 2, ..., 9, 1, 2, ... (הוא שארית החלוקה ב־ 9, כאשר שארית 0 נותנת 9). בתחום 1–999999 יש ‏999999 = 9 × 111111 מספרים, ולכן כל אחת מהספרות 1–9 מתקבלת בדיוק 111111 פעמים. הזוגיות הן 4 ספרות (2, 4, 6, 8) והאי־זוגיות 5 (1, 3, 5, 7, 9): ‏4 × 111111 = 444444 לעומת 5 × 111111 = 555555.

טעות נפוצה: לבדוק את הזוגיות של המספר i עצמו או של digitSum(i) במקום של deepSum(i).

מה נדרש: שני תנאים שחייבים להתקיים יחד: deepSum(num1) מופיע כספרה ב־ num2, וגם deepSum(num2) מופיע כספרה ב־ num1.

רעיון: deepSum מחזירה מספר חד־ספרתי, כלומר ספרה, ולכן אפשר להעביר אותה ישירות כפרמטר digit לפעולה הנתונה digitExists. מחברים את שתי הבדיקות ב־ && (וגם).

פתרון:

public static boolean inBoth(int num1, int num2)
{
    return digitExists(num2, deepSum(num1)) && digitExists(num1, deepSum(num2));
}

בדיקה:

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