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

מתכונת 5 במדעי המחשב - יסודות מדעי המחשב 899371

1–2 יח"ל · שאלון 899371 · 6 שאלות · 2:30 שעות · פתרון מלא לכל סעיף

מבחן מתכונת במדעי המחשב, יסודות מדעי המחשב, במבנה של בחינת הבגרות. כל שאלה בו בנויה כמו שאלה מבגרות אחרת. לכל סעיף יש תשובה ופתרון מלא, וכל קוד מופיע ב-Java וב-C#. פתרו בזמן של הבחינה, ורק אחר כך פתחו את הפתרונות.

הוראות הבחינה

א. משך הבחינה: שעתיים וחצי.
ב. מבנה השאלון ומפתח ההערכה: בשאלון זה שני פרקים.
פרק ראשון – (20×2) – 40 נקודות
פרק שני – (30×2) – 60 נקודות
סך הכול – 100 נקודות
ג. חומר עזר מותר בשימוש: כל חומר עזר, חוץ ממחשבון שיש בו אפשרות תכנוּת.
ד. הוראה מיוחדת:
את כל התוכניות שיש לכתוב בשפת מחשב כתבו בשפה אחת בלבד – Java או C#.
הערה: לא יוּרדוּ נקודות אם תכתבו בתוכניות אות גדולה במקום אות קטנה או להפך.

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

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

בהצלחה!

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

הערה: בכל שאלה שנדרשת בה קליטה, אין צורך לבדוק את תקינות הקלט.
לפותרים בשפת Java: בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner scan = new Scanner (System.in);

פרק ראשון (40 נקודות)

ענו על שתיים מן השאלות 1–3 (לכל שאלה – 20 נקודות).

שאלה 1 · מעקב – שרשרת דומינו של ספרות (20 נקודות)

נתון מערך arr , המכיל מספרים שלמים חיוביים.

0123456
arr2533891552727114

לפניכם קטע תוכנית, הכתוב בשפות Java ו־ C# .

Java

Java
int count=0;
for (int i=1; i<arr.length; i++)
{
    int last=arr[i-1]%10;
    int first=arr[i];
    while (first>=10)
        first=first/10;
    if (last==first)
        count++;
}

C#

C#
int count=0;
for (int i=1; i<arr.Length; i++)
{
    int last=arr[i-1]%10;
    int first=arr[i];
    while (first>=10)
        first=first/10;
    if (last==first)
        count++;
}
א.

עקבו בעזרת טבלת מעקב אחר ביצוע קטע התוכנית עבור המערך arr , ורשמו את ערך המשתנה count לאחר ביצוע קטע התוכנית.
בטבלת המעקב יש לכלול עמודה עבור כל אחד מן המשתנים האלה: count , i , last , first .

ב.

כתבו דוגמה למערך arr בגודל 5 המכיל מספרים שלמים חיוביים (גדולים מ־ 0) שבסיום קטע התוכנית ערכו של המשתנה count יישאר 0 .

ג.

כתבו דוגמה למערך arr בגודל 5 המכיל מספרים שלמים חיוביים (גדולים מ־ 0) שבסיום קטע התוכנית ערכו של המשתנה count יהיה שווה ל־ 4 .

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

סעיף א

תשובה

count = 3 (בזוגות של תאים סמוכים 0–1 , 2–3 ו־ 5–6 ספרת האחדות של המספר הקודם שווה לספרה השמאלית של המספר הבא).

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

רעיון: הלולאה מתחילה מ־ i=1 ובודקת בכל פעם זוג תאים סמוכים: arr[i-1] ו־ arr[i].

•last = arr[i-1]%10 היא ספרת האחדות (הספרה הימנית) של המספר הקודם.
•לולאת ה־ while מחלקת את first ב־ 10 כל עוד הוא דו־ספרתי לפחות, ולכן בסופה first היא הספרה השמאלית (הראשונה) של arr[i].
•count סופר כמה זוגות סמוכים "משתלבים" כמו אבני דומינו: הספרה האחרונה של מספר שווה לספרה הראשונה של המספר שאחריו.

פתרון – טבלת מעקב (בעמודה first מופיעים כל הערכים ש־ first מקבל, עד היציאה מלולאת ה־ while):

iarr[i-1]arr[i]lastfirst (ערכים בלולאת while)last==first ?count
0
125338338 → 3כן1
2389158915 → 91 → 9לא1
391552552 → 5כן2
452727לא2
572717271 → 27 → 2לא2
627114114 → 1כן3
7(התנאי i<7 אינו מתקיים – יציאה מהלולאה)3

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

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

טעות נפוצה: להתחיל את המעקב מ־ i=0 (הלולאה מתחילה מ־ 1 , ויש רק 6 זוגות סמוכים במערך בן 7 תאים), או לחשוב ש־ first היא ספרת העשרות. עבור 915 לולאת ה־ while מתבצעת פעמיים: 915 → 91 → 9 . עבור 7 היא אינה מתבצעת כלל, ו־ first = 7 .

סעיף ב

תשובה

למשל arr = {12, 34, 56, 78, 91} (בכל זוג סמוך הספרה האחרונה של הקודם שונה מהספרה הראשונה של הבא).

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

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

פתרון: למשל

01234
arr1234567891

הזוגות: 2 מול 3 , 4 מול 5 , 6 מול 7 , 8 מול 9 – בכולם הספרות שונות, ולכן count נשאר 0 .

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

טעות נפוצה: לבחור מספר שחוזר על עצמו, כמו {11, 11, 11, 11, 11} – אז הספרה האחרונה של כל מספר שווה לספרה הראשונה של הבא, ו־ count = 4 . גם מספרים חד־ספרתיים זהים, כמו {3, 3, 3, 3, 3} , נותנים count = 4 , כי במספר חד־ספרתי הספרה הראשונה והאחרונה הן אותה ספרה.

סעיף ג

תשובה

למשל arr = {12, 23, 34, 45, 56} (כל מספר מתחיל בספרה שבה הסתיים המספר הקודם).

מה נדרש: מערך בגודל 5 שעבורו count = 4 – כלומר כל ארבעת הזוגות הסמוכים מקיימים את התנאי.

רעיון: בונים "שרשרת דומינו": כל מספר מתחיל בספרה שבה הסתיים המספר שלפניו.

פתרון: למשל

01234
arr1223344556
ilastfirstcount
1221
2332
3443
4554

בדיקה: על {12, 23, 34, 45, 56} מתקבל count = 4 . גם {11, 11, 11, 11, 11} נותן 4 . (4 הוא הערך הגדול ביותר האפשרי במערך בגודל 5 , כי יש בו רק 4 זוגות סמוכים.)

שאלה 2 · מדידות לחות בחממה

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

•ההפרש בין המדידה הגבוהה ביותר לבין המדידה הנמוכה ביותר באותו יום הוא לכל היותר 25 .
•אין באותו יום שתי מדידות רצופות שבשתיהן הלחות נמוכה מ־ 40 .
•לפחות שליש מן המדידות באותו יום הן 60 ומעלה.

דוגמה: ביום מסוים נעשו שש מדידות, לפי הסדר: 55 , 62 , 48 , 70 , 66 , 51 . ההפרש בין 70 ל־ 48 הוא 22 , אין מדידות הנמוכות מ־ 40 , ושלוש מתוך שש המדידות (62 , 70 , 66) הן 60 ומעלה – יותר משליש מהן. לכן זהו יום תקין.

דוגמה נוספת: ביום מסוים נעשו חמש מדידות, לפי הסדר: 45 , 38 , 39 , 50 , 60 . המדידות 38 ו־ 39 הן רצופות ושתיהן נמוכות מ־ 40 , ולכן זהו אינו יום תקין.

דוגמה נוספת: ביום מסוים נעשו ארבע מדידות, לפי הסדר: 72 , 58 , 45 , 61 . ההפרש בין 72 ל־ 45 הוא 27 , ולכן זהו אינו יום תקין.

כתבו פעולה חיצונית ששמה goodDay בשפת Java או GoodDay בשפת C# , המקבלת מספר שלם – num .
num מציין את מספר המדידות שנעשו בחממה ביום מסוים. הניחו כי num גדול מ־ 0 .
הפעולה תקלוט את num המדידות, לפי הסדר שבו נעשו.
הפעולה תחזיר true אם היום הוא יום תקין, אחרת תחזיר הפעולה false .

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

פתרון

תשובה

בלולאה אחת: קולטים כל מדידה, מעדכנים max ו־min, סופרים מדידות ≥ 60, ובודקים אם המדידה הנוכחית והקודמת שתיהן < 40. בסוף מחזירים max − min <= 25 && !twoLow && countHigh * 3 >= num.

מה נדרש: פעולה שקולטת num מדידות ומחזירה true רק אם שלושת התנאים מתקיימים יחד.

רעיון: בלולאה אחת שרצה num פעמים קולטים כל מדידה h ומעדכנים:

•max ו־min – המדידה הגבוהה והנמוכה ביותר. מאחר שהלחות תמיד בין 0 ל־100, אפשר להתחיל ב־max = 0 ו־min = 100 (או לאתחל אותם במדידה הראשונה);
•countHigh – כמה מדידות הן 60 ומעלה;
•twoLow – דגל: האם היו שתי מדידות רצופות מתחת ל־40. לשם כך שומרים את המדידה הקודמת prev. לפני המדידה הראשונה מציבים בו 100 (ערך שאינו נמוך מ־40), כדי שהמדידה הראשונה לא "תתחבר" לשום דבר.

אחרי הלולאה (רק אחרי שכל המדידות נקלטו!) בודקים את שלושת התנאים ומחזירים את ה־"וגם" (&&) שלהם:

•max - min <= 25 ("לכל היותר" – כולל 25);
•!twoLow;
•"לפחות שליש": countHigh * 3 >= num. כך נמנעים מחילוק שלמים (למשל num = 4: ‏4 / 3 = 1 בחילוק שלמים, אבל מדידה אחת מתוך ארבע היא פחות משליש).

פתרון: הקוד המלא – בלשונית Java/C#. ב־Java משתמשים ב־scan.nextInt(), וב־C# ב־int.Parse(Console.ReadLine()).

בדיקה: על שלוש הדוגמאות שבשאלה:

•55 , 62 , 48 , 70 , 66 , 51 → true;
•45 , 38 , 39 , 50 , 60 → false (שתי מדידות רצופות מתחת ל־40);
•72 , 58 , 45 , 61 → false (הפרש 27).

ומקרים נוספים: 50 , 55 , 61 , 52 , 48 → false (רק 1 מתוך 5 הן 60 ומעלה); 60 , 45 , 50 → true (בדיוק שליש); 38 , 45 , 60 → true (המדידות הנמוכות אינן רצופות); 35 , 60 → true (הפרש בדיוק 25); 35 , 61 → false; 39 , 39 , 60 → false.

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

הקוד המלא
import java.util.Scanner;

public class Greenhouse
{
    static Scanner scan = new Scanner(System.in);

    public static boolean goodDay(int num)
    {
        int max = 0, min = 100;    // הלחות תמיד בין 0 ל־100
        int countHigh = 0;         // מספר המדידות של 60 ומעלה
        boolean twoLow = false;    // האם היו שתי מדידות רצופות מתחת ל־40
        int prev = 100;            // המדידה הקודמת (לפני הראשונה – ערך "בטוח")
        for (int i = 0; i < num; i++)
        {
            int h = scan.nextInt();
            if (h > max)
                max = h;
            if (h < min)
                min = h;
            if (h >= 60)
                countHigh++;
            if (h < 40 && prev < 40)
                twoLow = true;
            prev = h;
        }
        return max - min <= 25 && !twoLow && countHigh * 3 >= num;
    }
}

שאלה 3 · ליקוט הזמנה במחסן – מחרוזות (20 נקודות)

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

לדוגמה: בעבור ההזמנה "KDRWP" ומחרוזת הליקוט "PWXDQ" :
שלושה מוצרים סומנו "נאסף" – D , W , P .
שני מוצרים סומנו "חסר" – K , R .
שני מוצרים סומנו "מיותר" – X , Q .

כתבו פעולה חיצונית ששמה checkPicking בשפת Java או CheckPicking בשפת C# , המקבלת שני פרמטרים:
מחרוזת הזמנה – order , ומחרוזת ליקוט – picked .
הניחו ששתי המחרוזות תקינות (כלומר מופיעות בהן רק האותיות Z–A וכל אות מופיעה בכל מחרוזת פעם אחת לכל היותר), ושמחרוזת ההזמנה אינה ריקה.
אם מחרוזת הליקוט ריקה (המלקט לא אסף דבר), הפעולה תדפיס הודעת שגיאה "Nothing Picked" .
אחרת, הפעולה תדפיס את מספר המוצרים שסומנו "נאסף", מספר המוצרים שסומנו "חסר" ומספר המוצרים שסומנו "מיותר" (כל הדפסה בשורה חדשה).

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

פתרון

תשובה

לכל אות ב־ order: picked.indexOf(...) != -1 → נאסף, אחרת חסר; לכל אות ב־ picked: order.indexOf(...) == -1 → מיותר. בדוגמה: 3, 2, 2

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

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

•לולאה על order: כל אות שנמצאת ב־ picked (indexOf ≠ -1) – "נאסף"; אחרת – "חסר".
•לולאה על picked: כל אות שאינה נמצאת ב־ order (indexOf == -1) – "מיותר".

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

פתרון: הקוד המלא – בלשונית Java / C#.

בדיקה:

orderpickedפלט
KDRWPPWXDQ3, 2, 2 (כמו בדוגמה)
KDRWP(ריקה)Nothing Picked
ABCCBA3, 0, 0
ABCXYZW0, 3, 4
ABBACD2, 0, 2
MNOPN1, 3, 0

הערה: אפשר גם לחשב את מספר המיותרים כ־ picked.length() − found (כל אות ב־ picked שאינה "נאסף" היא מיותרת), כי אין אותיות חוזרות.

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

הקוד המלא
public static void checkPicking(String order, String picked)
{
    if (picked.length() == 0)
    {
        System.out.println("Nothing Picked");
    }
    else
    {
        int found = 0, missing = 0, extra = 0;
        for (int i = 0; i < order.length(); i++)
        {
            if (picked.indexOf(order.charAt(i)) != -1)
                found++;
            else
                missing++;
        }
        for (int i = 0; i < picked.length(); i++)
        {
            if (order.indexOf(picked.charAt(i)) == -1)
                extra++;
        }
        System.out.println(found);
        System.out.println(missing);
        System.out.println(extra);
    }
}

פרק שני (60 נקודות)

ענו על שתיים מן השאלות 4–6 (לכל שאלה – 30 נקודות).

שאלה 4 · מסלול הדפסה לסטודנטים – PrintPlan (30 נקודות)

נתונה המחלקה PrintPlan – מסלול הדפסה חודשי של סטודנט במכון ההדפסה של האוניברסיטה, ולה חמש תכונות:

•studentId – מספר הזיהוי של הסטודנט, מטיפוס שלם
•fee – התשלום החודשי הקבוע על המסלול, מטיפוס שלם
•maxPages – מספר עמודי השחור־לבן הכלולים במסלול בכל חודש, מטיפוס שלם
•maxColor – מספר עמודי הצבע הכלולים במסלול בכל חודש, מטיפוס שלם
•extra – הסכום הנוסף לתשלום על חריגה ממספר העמודים הכלולים במסלול, מטיפוס שלם

תעריפי החריגה הם שקל אחד בעבור כל 5 עמודי שחור־לבן נוספים (רק קבוצות שלמות של 5 עמודים מחויבות; למשל, על חריגה של 27 עמודים משלמים 5 שקלים), ו־ 2 שקלים בעבור כל עמוד צבע נוסף.

הניחו שקיימות פעולות get/Get לתכונות המחלקה.

א.(1)

כתבו פעולה בונה במחלקה PrintPlan , המקבלת את מספר הזיהוי של הסטודנט – studentId , את התשלום החודשי – fee , את מספר עמודי השחור־לבן הכלולים במסלול – maxPages , ואת מספר עמודי הצבע הכלולים במסלול – maxColor .
הפעולה מאתחלת את תכונות המחלקה. התכונה extra מאותחלת ל־ 0 .

(2)

כתבו פעולה פנימית במחלקה PrintPlan ששמה setExtra בשפת Java או SetExtra בשפת C# , המקבלת את מספר עמודי השחור־לבן שהדפיס הסטודנט בפועל בחודש – pages (מטיפוס שלם), ואת מספר עמודי הצבע שהדפיס בפועל בחודש – color (מטיפוס שלם).
הפעולה קובעת ערך לתכונה extra בהתאם לחריגה ממסלול ההדפסה (ככל שיש) ולתעריפי החריגה.
הערה: extra היא 0 לפני הפעולה.

ב.(1)

נתון מערך מלא – plans מטיפוס PrintPlan , ובו נתוני המסלולים של סטודנטים שונים (לאחר שכבר חושב ועודכן הסכום הנוסף לתשלום בתכונה extra).

כתבו פעולה חיצונית ששמה countHigh בשפת Java או CountHigh בשפת C# , המקבלת את המערך plans , ומחזירה את מספר הסטודנטים שהסכום הנוסף שלהם (extra) גדול מן התשלום החודשי הקבוע שלהם (fee).

(2)

כתבו פעולה חיצונית ששמה highStudents בשפת Java או HighStudents בשפת C# , המקבלת את המערך plans .
הפעולה מחזירה מערך מטיפוס שלם ובו מספרי הזיהוי (studentId) של הסטודנטים שהסכום הנוסף שלהם גדול מן התשלום החודשי שלהם (גודל המערך הוא בדיוק כמספר הסטודנטים האלה). אין חשיבות לסדר ההופעה במערך.
הערה: חובה להיעזר בפעולה שכתבתם בסעיף ב(1).

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

סעיף א(1)

תשובה

public PrintPlan(int studentId, int fee, int maxPages, int maxColor) – השמה לארבע התכונות ו־ extra = 0.

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

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

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

public class PrintPlan
{
    private int studentId;
    private int fee;
    private int maxPages;
    private int maxColor;
    private int extra;

    public PrintPlan(int studentId, int fee, int maxPages, int maxColor)
    {
        this.studentId = studentId;
        this.fee = fee;
        this.maxPages = maxPages;
        this.maxColor = maxColor;
        this.extra = 0;
    }

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

בדיקה: new PrintPlan(1001, 40, 300, 20) – ‏getExtra() החזירה 0, ושאר פעולות ה־ get החזירו 1001, 40, 300, 20.

הקוד המלא
public class PrintPlan
{
    private int studentId;
    private int fee;
    private int maxPages;
    private int maxColor;
    private int extra;

    public PrintPlan(int studentId, int fee, int maxPages, int maxColor)
    {
        this.studentId = studentId;
        this.fee = fee;
        this.maxPages = maxPages;
        this.maxColor = maxColor;
        this.extra = 0;
    }

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

סעיף א(2)

תשובה

extra = (pages > maxPages ? (pages − maxPages) / 5 : 0) + (color > maxColor ? (color − maxColor) · 2 : 0) (חילוק בשלמים).

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

רעיון:

•חריגה בשחור־לבן קיימת רק אם pages > maxPages. מספר הקבוצות השלמות של 5 עמודים הוא (pages − maxPages) / 5 – חילוק בשלמים "זורק" את השארית, וזה בדיוק מה שנדרש (על קבוצה חלקית לא משלמים). כל קבוצה עולה שקל אחד.
•חריגה בצבע קיימת רק אם color > maxColor; התשלום: (color − maxColor) × 2.
•extra = סכום שני החלקים (אם אין חריגה – 0).

פתרון:

public void setExtra(int pages, int color)
{
    int sum = 0;
    if (pages > this.maxPages)
        sum = sum + (pages - this.maxPages) / 5;
    if (color > this.maxColor)
        sum = sum + (color - this.maxColor) * 2;
    this.extra = sum;
}

בדיקה:

•מסלול (1001, 40, 300, 20) עם pages = 327, color = 35: ‏27 / 5 = 5 שקלים + 15 × 2 = 30 שקלים → 35.
•מסלול (1002, 25, 200, 10) עם 204 ו־ 10: חריגה של 4 עמודים בלבד – אין קבוצה שלמה → 0.
•מסלול (1003, 30, 500, 0) עם 450 ו־ 18 → רק צבע: 36. מסלול (1004, 20, 100, 50) עם 230 ו־ 40 → רק שחור־לבן: 130 / 5 = 26.

טעות נפוצה: לחשב בלי תנאים (pages - maxPages) / 5 + (color - maxColor) * 2. כשהסטודנט הדפיס פחות מהכלול, ההפרש שלילי ו"מקזז" את החריגה בחלק השני. טעות נוספת: לחלק ב־ 5.0 (חילוק ממשי) – כך מחייבים גם על קבוצה חלקית.

הקוד המלא
public void setExtra(int pages, int color)
{
    int sum = 0;
    if (pages > this.maxPages)
        sum = sum + (pages - this.maxPages) / 5;
    if (color > this.maxColor)
        sum = sum + (color - this.maxColor) * 2;
    this.extra = sum;
}

סעיף ב(1)

תשובה

מונים את המסלולים שבהם getExtra() > getFee().

מה נדרש: למנות כמה מסלולים במערך מקיימים extra > fee.

רעיון: מונה שמתחיל ב־ 0; עוברים על כל המערך, ולכל מסלול משווים את getExtra() ל־ getFee() של אותו מסלול. אם extra גדול יותר – מגדילים את המונה.

פתרון:

public static int countHigh(PrintPlan[] plans)
{
    int count = 0;
    for (int i = 0; i < plans.length; i++)
    {
        if (plans[i].getExtra() > plans[i].getFee())
            count++;
    }
    return count;
}

בדיקה: מערך של חמשת המסלולים מסעיף א (extra/fee: ‏35/40, 0/25, 36/30, 26/20, 0/60) – הוחזר 2 (המסלולים 1003 ו־ 1004). על מערך שאין בו מסלול כזה הוחזר 0. מסלול שבו extra = fee = 12 לא נספר (נדרש "גדול").

טעות נפוצה: להשוות ל־ fee קבוע אחד, או להשתמש ב־ >= במקום >.

הקוד המלא
public static int countHigh(PrintPlan[] plans)
{
    int count = 0;
    for (int i = 0; i < plans.length; i++)
    {
        if (plans[i].getExtra() > plans[i].getFee())
            count++;
    }
    return count;
}

סעיף ב(2)

תשובה

int[] ids = new int[countHigh(plans)]; ממלאים בעזרת אינדקס נפרד k את studentId של כל מסלול שבו extra > fee.

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

רעיון:

1.את גודל המערך החדש יודעים מראש בעזרת countHigh (סעיף ב(1)).
2.עוברים על plans, ולכל מסלול שבו extra > fee מכניסים את studentId לתא הפנוי הבא במערך החדש. אינדקס נפרד k מציין את התא הפנוי הבא.

פתרון:

public static int[] highStudents(PrintPlan[] plans)
{
    int[] ids = new int[countHigh(plans)];
    int k = 0;
    for (int i = 0; i < plans.length; i++)
    {
        if (plans[i].getExtra() > plans[i].getFee())
        {
            ids[k] = plans[i].getStudentId();
            k++;
        }
    }
    return ids;
}

בדיקה: על מערך חמשת המסלולים הוחזר {1003, 1004}. על מערך שאין בו מסלול מתאים הוחזר מערך באורך 0.

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

הקוד המלא
public static int[] highStudents(PrintPlan[] plans)
{
    int[] ids = new int[countHigh(plans)];
    int k = 0;
    for (int i = 0; i < plans.length; i++)
    {
        if (plans[i].getExtra() > plans[i].getFee())
        {
            ids[k] = plans[i].getStudentId();
            k++;
        }
    }
    return ids;
}

שאלה 5 · מועדון צפרות – מינים שראו יחד (30 נקודות)

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

נתונה המחלקה Watcher – צפר, ולה שלוש תכונות:

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

הניחו שקיימות פעולות get/Get לתכונות המחלקה.

א.

כתבו במחלקה Watcher פעולה פנימית ששמה together בשפת Java או Together בשפת C#, המקבלת צפר (Watcher) אחר – other . הפעולה מחזירה את מספר מיני הציפורים השונים שראה לפחות אחד משני הצפרים.
דוגמה: אם הצפר הנוכחי ראה את המינים 4 , 9 , 15 , 22 ו־ other ראה את המינים 9 , 22 , 31 , הפעולה תחזיר 5 (המינים 4 , 9 , 15 , 22 , 31 ).

ב.

נתונה המחלקה BirdClub – מועדון צפרות, ולה תכונה אחת:

•members – מערך מטיפוס Watcher

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

המועדון מתכנן תחרות זוגות לצפר חדש. כתבו במחלקה BirdClub פעולה פנימית ששמה allReach בשפת Java או AllReach בשפת C#, המקבלת צפר (Watcher) – w , שאינו מופיע במערך, ומספר שלם – k . הפעולה מחזירה true אם לכל צפר במערך מתקיים: מספר מיני הציפורים השונים שראו הצפר ו־ w יחד הוא k לפחות. אחרת הפעולה מחזירה false .
הערה: אפשר להיעזר בפעולה שכתבתם בסעיף א.

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

סעיף א

תשובה

סופרים את המינים המשותפים (common) בלולאות מקוננות ומחזירים this.species.length + other.species.length − common.

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

רעיון
אם מחברים את גודלי שני המערכים, כל מין שראו שניהם נספר פעמיים. לכן סופרים קודם את המינים המשותפים (לולאות מקוננות: כל זוג i, j שבו species[i] == otherSpecies[j]), ומחסירים אותם פעם אחת:
מספר שונים = אורך this + אורך other − מספר משותפים.
בתוך כל מערך כל קוד מופיע פעם אחת, ולכן כל מין משותף נספר בדיוק פעם אחת.

פתרון
(הפעולה הבונה נכתבה לצורך הבדיקה בלבד.)

Java

Java
public class Watcher
{
    private String name;     // שם הצפר
    private int id;          // מספר חבר ייחודי
    private int[] species;   // קודי מיני הציפורים שהצפר ראה

    // פעולה בונה – לצורך הבדיקה בלבד
    public Watcher(String name, int id, int[] species)
    {
        this.name = name;
        this.id = id;
        this.species = species;
    }

    public String getName() { return this.name; }
    public int getId() { return this.id; }
    public int[] getSpecies() { return this.species; }

    // סעיף א
    public int together(Watcher other)
    {
        int[] otherSpecies = other.getSpecies();
        int common = 0;
        for (int i = 0; i < this.species.length; i++)
        {
            for (int j = 0; j < otherSpecies.length; j++)
            {
                if (this.species[i] == otherSpecies[j])
                {
                    common++;
                }
            }
        }
        return this.species.length + otherSpecies.length - common;
    }
}

C#

C#
public class Watcher
{
    private string name;     // שם הצפר
    private int id;          // מספר חבר ייחודי
    private int[] species;   // קודי מיני הציפורים שהצפר ראה

    // פעולה בונה – לצורך הבדיקה בלבד
    public Watcher(string name, int id, int[] species)
    {
        this.name = name;
        this.id = id;
        this.species = species;
    }

    public string GetName() { return this.name; }
    public int GetId() { return this.id; }
    public int[] GetSpecies() { return this.species; }

    // סעיף א
    public int Together(Watcher other)
    {
        int[] otherSpecies = other.GetSpecies();
        int common = 0;
        for (int i = 0; i < this.species.Length; i++)
        {
            for (int j = 0; j < otherSpecies.Length; j++)
            {
                if (this.species[i] == otherSpecies[j])
                {
                    common++;
                }
            }
        }
        return this.species.Length + otherSpecies.Length - common;
    }
}

בדיקה
a = {4, 9, 15, 22}, b = {9, 22, 31}, c = {50}, e = { }:

•a.together(b) = 4 + 3 − 2 = 5 (הדוגמה מהשאלה) ; b.together(a) = 5
•a.together(c) = 4 + 1 − 0 = 5
•a.together(a) = 4 + 4 − 4 = 4
•c.together(e) = 1

טעות נפוצה: להחזיר this.species.length + other.species.length בלי להחסיר את המשותפים – אז בדוגמה מתקבל 7 במקום 5.

הקוד המלא
public class Watcher
{
    private String name;     // שם הצפר
    private int id;          // מספר חבר ייחודי
    private int[] species;   // קודי מיני הציפורים שהצפר ראה

    // פעולה בונה – לצורך הבדיקה בלבד
    public Watcher(String name, int id, int[] species)
    {
        this.name = name;
        this.id = id;
        this.species = species;
    }

    public String getName() { return this.name; }
    public int getId() { return this.id; }
    public int[] getSpecies() { return this.species; }

    // סעיף א
    public int together(Watcher other)
    {
        int[] otherSpecies = other.getSpecies();
        int common = 0;
        for (int i = 0; i < this.species.length; i++)
        {
            for (int j = 0; j < otherSpecies.length; j++)
            {
                if (this.species[i] == otherSpecies[j])
                {
                    common++;
                }
            }
        }
        return this.species.length + otherSpecies.length - common;
    }
}

סעיף ב

תשובה

עוברים על members; אם members[i].together(w) < k מחזירים false מיד; אחרי הלולאה מחזירים true.

מה נדרש
פעולה פנימית ב-BirdClub (מחלקה שמכילה מערך של עצמים מטיפוס Watcher) שבודקת תנאי "לכל": לכל חבר במערך, האיחוד שלו עם w כולל לפחות k מינים.

רעיון
בדיקת "לכל" נעשית בחיפוש של דוגמה נגדית: עוברים על members, ולכל חבר מחשבים members[i].together(w) (סעיף א). אם נמצא חבר שעבורו התוצאה קטנה מ-k – התנאי אינו מתקיים, ומחזירים false מיד. אם הלולאה הסתיימה בלי דוגמה נגדית – מחזירים true.

פתרון
(הפעולה הבונה נכתבה לצורך הבדיקה בלבד.)

Java

Java
public class BirdClub
{
    private Watcher[] members;

    // פעולה בונה – לצורך הבדיקה בלבד
    public BirdClub(Watcher[] members)
    {
        this.members = members;
    }

    // סעיף ב
    public boolean allReach(Watcher w, int k)
    {
        for (int i = 0; i < this.members.length; i++)
        {
            if (this.members[i].together(w) < k)
            {
                return false;
            }
        }
        return true;
    }
}

C#

C#
public class BirdClub
{
    private Watcher[] members;

    // פעולה בונה – לצורך הבדיקה בלבד
    public BirdClub(Watcher[] members)
    {
        this.members = members;
    }

    // סעיף ב
    public bool AllReach(Watcher w, int k)
    {
        for (int i = 0; i < this.members.Length; i++)
        {
            if (this.members[i].Together(w) < k)
            {
                return false;
            }
        }
        return true;
    }
}

בדיקה
במועדון a = {4, 9, 15, 22}, b = {9, 22, 31}, c = {50}, ו-w = {9, 31, 60, 61}:
a יחד עם w ← 7 מינים, b יחד עם w ← 5, c יחד עם w ← 5.

•allReach(w, 5) ← true (המינימום הוא 5)
•allReach(w, 6) ← false (b ו-c מגיעים ל-5 בלבד)
•בעבור צפר e שלא ראה אף מין: allReach(e, 1) ← true, allReach(e, 2) ← false (c יחד עם e ← 1)

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

הקוד המלא
public class BirdClub
{
    private Watcher[] members;

    // פעולה בונה – לצורך הבדיקה בלבד
    public BirdClub(Watcher[] members)
    {
        this.members = members;
    }

    // סעיף ב
    public boolean allReach(Watcher w, int k)
    {
        for (int i = 0; i < this.members.length; i++)
        {
            if (this.members[i].together(w) < k)
            {
                return false;
            }
        }
        return true;
    }
}

שאלה 6 · שעות פלינדרום – הגרלה למערך עצמים (30 נקודות)

שעון דיגיטלי מציג את השעה בתבנית hh:mm – שתי ספרות לשעה (00 עד 23) ושתי ספרות לדקות (00 עד 59).
שעת פלינדרום היא שעה שבה ארבע הספרות המוצגות נקראות אותו הדבר משמאל לימין ומימין לשמאל.

דוגמאות:

שעהשעת פלינדרום?
13:31כן
05:50כן
22:22כן
10:10לא
12:34לא

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

נתונה המחלקה Time — שעה ביממה, ולה שתי תכונות:

Java
public class Time {
      private int hour ;
      private int minute ;
}

hour – מספר שלם מ־0 עד 23, minute – מספר שלם מ־0 עד 59.
הנח שקיימות פעולות get ו־set בשפת Java ופעולות Get ו־Set בשפת C# בעבור תכונות המחלקה.
לפניך ממשק חלקי של המחלקה Time בשפות Java ו־C#.
אפשר להשתמש בפעולות הממשק ללא צורך לממש אותן.

תיאור הפעולהכותרת הפעולה
פעולה בונה המקבלת ערכים בעבור תכונות המחלקה.public Time (int hour, int minute)
פעולה המחזירה true אם העצם הוא שעת פלינדרום, אחרת היא מחזירה false.בשפת Java: public boolean isPalindrome ()<br>בשפת C#: public bool IsPalindrome ()
פעולה המחזירה true אם לעצם הנוכחי ולעצם other יש אותה שעה ואותן דקות, אחרת היא מחזירה false.בשפת Java: public boolean sameAs (Time other)<br>בשפת C#: public bool SameAs (Time other)

לפניך כותרת פעולה חיצונית בשפת :

public static Time[] palindromeTimes (int n)

הפעולה palindromeTimes / PalindromeTimes בונה מערך ריק של עצמים מטיפוס Time בגודל n . בעבור כל תא במערך, הפעולה מגרילה שעה בין 0 ל־23 (כולל) ודקות בין 0 ל־59 (כולל). אם השעה שהוגרלה היא שעת פלינדרום וגם היא אינה נמצאת כבר באחד התאים הקודמים של המערך, מוכנס לתא עצם שערכי התכונות שלו הם הערכים שהוגרלו. אחרת, הפעולה ממשיכה להגריל עד שמתקבלת שעה כזאת, ואז מוכנס לתא עצם שערכי התכונות שלו הם הערכים שהוגרלו.
לאחר שהמערך מתמלא, הפעולה מחזירה את המערך.

הערה: הנח ש־n בין 1 ל־16 (כולל).

ממשו את הפעולה.

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

פתרון

תשובה

לכל תא i: חוזרים – מגרילים hour (0..23) ו־minute (0..59), ok = t.isPalindrome(), ואם ok – מחפשים בתאים 0..i−1 עצם ש־sameAs(t) ומאפסים את ok; עד ש־ok; times[i] = t. בסוף מחזירים את המערך.

מה נדרש: לממש את palindromeTimes(n): מערך של n שעות פלינדרום אקראיות שונות זו מזו.

רעיון:

1.יוצרים מערך Time[] בגודל n.
2.לכל תא i: לולאת while שרצה עד שמתקבלת שעה "טובה". בכל סיבוב:
•מגרילים hour בתחום 0..23 ו־minute בתחום 0..59 ויוצרים עצם t.
•ok = t.isPalindrome() – הבדיקה נעשית בפעולת המחלקה, בלי לממש אותה.
•אם ok – חיפוש סדרתי בתאים הקודמים 0..i−1: אם קיים j ש־times[j].sameAs(t), השעה כבר הוגרלה ו־ok = false. (התנאי j < i && ok עוצר את החיפוש כשנמצאה התאמה.)
3.כשהלולאה מסתיימת – t היא שעת פלינדרום חדשה, ומכניסים אותה לתא i. בסוף מחזירים את המערך.

הגבלת n ל־16 לכל היותר חשובה: יש רק 16 שעות פלינדרום, ולכן בעבור n גדול יותר לולאת ה־while בתא ה־17 לא הייתה מסתיימת.

הגרלה:

•Java: (int) (Math.random() * 24) נותן 0..23, ו־(int) (Math.random() * 60) נותן 0..59.
•C#: rnd.Next(0, 24) ו־rnd.Next(0, 60) – הגבול העליון אינו נכלל. עצם ה־Random נוצר פעם אחת.

פתרון: הקוד המלא – בלשונית Java/C#.

בדיקה: לבדיקה צריך את isPalindrome (הספרה הראשונה של השעה שווה לספרה האחרונה של הדקות, והספרה השנייה של השעה שווה לספרה הראשונה של הדקות: hour / 10 == minute % 10 && hour % 10 == minute / 10) ואת sameAs. מעבר על כל 1,440 השעות ביממה מצא בדיוק 16 שעות פלינדרום: 00:00, 01:10, 02:20, 03:30, 04:40, 05:50, 10:01, 11:11, 12:21, 13:31, 14:41, 15:51, 20:02, 21:12, 22:22, 23:32. בכל מערך שנוצר כל התאים מלאים, כל השעות הן שעות פלינדרום, ואין שתי שעות זהות (גם בעבור n = 16, שבו המערך מכיל את כל 16 השעות). דוגמה לפלט אחד עם n = 5: 13:31, 10:01, 23:32, 05:50, 21:12.

טעות נפוצה: לבדוק כפילות רק מול התא הקודם (times[i − 1]) במקום מול כל התאים הקודמים, או לחפש בכל המערך (עד n) – התאים שאחרי i עדיין null, והזימון times[j].sameAs(t) ייכשל. טעות נוספת: להשוות עצמים ב־== (בודק אם זה אותו עצם, לא אם יש להם אותה שעה) במקום sameAs.

הקוד המלא
public static Time[] palindromeTimes(int n)
{
    Time[] times = new Time[n];
    for (int i = 0; i < n; i++)
    {
        Time t = null;
        boolean ok = false;
        while (!ok)
        {
            int hour = (int) (Math.random() * 24);      // 0..23
            int minute = (int) (Math.random() * 60);    // 0..59
            t = new Time(hour, minute);
            ok = t.isPalindrome();
            for (int j = 0; j < i && ok; j++)           // האם כבר הוגרלה?
            {
                if (times[j].sameAs(t))
                    ok = false;
            }
        }
        times[i] = t;
    }
    return times;
}
טבלת התשובות
שאלהסעיףתשובה
1א

count = 3 (בזוגות של תאים סמוכים 0–1 , 2–3 ו־ 5–6 ספרת האחדות של המספר הקודם שווה לספרה השמאלית של המספר הבא).

ב

למשל arr = {12, 34, 56, 78, 91} (בכל זוג סמוך הספרה האחרונה של הקודם שונה מהספרה הראשונה של הבא).

ג

למשל arr = {12, 23, 34, 45, 56} (כל מספר מתחיל בספרה שבה הסתיים המספר הקודם).

2-

בלולאה אחת: קולטים כל מדידה, מעדכנים max ו־min, סופרים מדידות ≥ 60, ובודקים אם המדידה הנוכחית והקודמת שתיהן < 40. בסוף מחזירים max − min <= 25 && !twoLow && countHigh * 3 >= num.

3-

לכל אות ב־ order: picked.indexOf(...) != -1 → נאסף, אחרת חסר; לכל אות ב־ picked: order.indexOf(...) == -1 → מיותר. בדוגמה: 3, 2, 2

4א(1)

public PrintPlan(int studentId, int fee, int maxPages, int maxColor) – השמה לארבע התכונות ו־ extra = 0.

א(2)

extra = (pages > maxPages ? (pages − maxPages) / 5 : 0) + (color > maxColor ? (color − maxColor) · 2 : 0) (חילוק בשלמים).

ב(1)

מונים את המסלולים שבהם getExtra() > getFee().

ב(2)

int[] ids = new int[countHigh(plans)]; ממלאים בעזרת אינדקס נפרד k את studentId של כל מסלול שבו extra > fee.

5א

סופרים את המינים המשותפים (common) בלולאות מקוננות ומחזירים this.species.length + other.species.length − common.

ב

עוברים על members; אם members[i].together(w) < k מחזירים false מיד; אחרי הלולאה מחזירים true.

6-

לכל תא i: חוזרים – מגרילים hour (0..23) ו־minute (0..59), ok = t.isPalindrome(), ואם ok – מחפשים בתאים 0..i−1 עצם ש־sameAs(t) ומאפסים את ok; עד ש־ok; times[i] = t. בסוף מחזירים את המערך.

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

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

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