מתכונת 4 במדעי המחשב - יסודות מדעי המחשב 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 · מעקב אחר לולאה הסורקת מערך מהסוף
נתון מערך arr , המכיל מספרים שלמים:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| arr | 5 | 2 | 8 | 3 | 7 | 1 | 4 |
נתון קטע תוכנית, הכתוב בשפות Java ו־ C# :
Java
int mx = arr[arr.length - 1];
for (int i = arr.length - 2; i >= 0; i--)
{
if (arr[i] < mx)
arr[i] = mx - arr[i];
else
mx = arr[i];
}C#
int mx = arr[arr.Length - 1];
for (int i = arr.Length - 2; i >= 0; i--)
{
if (arr[i] < mx)
arr[i] = mx - arr[i];
else
mx = arr[i];
}עקבו בעזרת טבלת מעקב אחר ביצוע קטע התוכנית, ורשמו את תוכן המערך arr לאחר ביצוע קטע התוכנית.
בטבלת המעקב יש לכלול עמודה עבור כל אחד מן המשתנים האלה: i , arr[i] , mx .
כתבו דוגמה למערך arr בגודל 5 , שלא כל התאים שלו שווים ל־ 2 , ושלאחר ביצוע קטע התוכנית כל התאים שלו יכילו את הערך 2 .
◂ פתרון מלא לשאלה 1
סעיף א
arr = {3, 6, 8, 4, 7, 3, 4}
מה נדרש: לעקוב אחרי ביצוע הלולאה על המערך הנתון (עמודות i , arr[i] , mx) ולרשום את המערך בסוף.
רעיון: הלולאה עוברת על המערך מהסוף להתחלה (i יורד מ־5 עד 0). לפני הלולאה mx = arr[6] = 4.
בכל סיבוב:
כלומר mx הוא תמיד הערך המקורי הגדול ביותר מבין התאים שמימין לתא הנוכחי (כולל התא האחרון), וכל תא שקטן ממנו מוחלף ב"מרחק" שלו מהמקסימום הזה.
פתרון – טבלת מעקב (לפני הלולאה: mx = 4)
| i | i >= 0 ? | arr[i] < mx ? | arr[i] (בסוף הסיבוב) | mx (בסוף הסיבוב) |
|---|---|---|---|---|
| 5 | true | 1 < 4 – כן | 4 − 1 = 3 | 4 |
| 4 | true | 7 < 4 – לא | 7 | 7 |
| 3 | true | 3 < 7 – כן | 7 − 3 = 4 | 7 |
| 2 | true | 8 < 7 – לא | 8 | 8 |
| 1 | true | 2 < 8 – כן | 8 − 2 = 6 | 8 |
| 0 | true | 5 < 8 – כן | 8 − 5 = 3 | 8 |
| −1 | false | – | – | – |
המערך לאחר ביצוע קטע התוכנית:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| arr | 3 | 6 | 8 | 4 | 7 | 3 | 4 |
בדיקה: הקטע מדפיס 3 6 8 4 7 3 4, בדיוק כמו בטבלה.
טעות נפוצה: להתחיל את הלולאה ב־i = 6 או להמשיך עד i = 1 בלבד. הלולאה מתחילה ב־arr.length − 2 = 5 (התא האחרון לא משתנה – הוא ערך ההתחלה של mx) ומסתיימת ב־i = 0 (כולל). טעות נוספת: לשכוח לעדכן את mx כשהתנאי לא מתקיים.
סעיף ב
למשל {0, 2, 0, 0, 2} (הופך ל־{2, 2, 2, 2, 2}). כל מערך שבו arr[4] = 2 וכל שאר התאים הם 0 או 2 (ולא כולם 2) מתאים.
מה נדרש: מערך בגודל 5, לא כולו 2, שאחרי ביצוע הקטע כל תאיו שווים ל־2.
רעיון: נחשוב מהסוף להתחלה, כמו הלולאה:
לכן: arr[4] = 2, וכל אחד מ־arr[0..3] הוא 0 או 2 – ולפחות אחד מהם 0 (כדי שלא כל התאים יהיו 2).
פתרון: למשל המערך:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| arr | 0 | 2 | 0 | 0 | 2 |
| i | arr[i] < mx ? | arr[i] | mx |
|---|---|---|---|
| (לפני) | – | – | 2 |
| 3 | 0 < 2 – כן | 2 − 0 = 2 | 2 |
| 2 | 0 < 2 – כן | 2 − 0 = 2 | 2 |
| 1 | 2 < 2 – לא | 2 | 2 |
| 0 | 0 < 2 – כן | 2 − 0 = 2 | 2 |
אחרי הביצוע: 2 , 2 , 2 , 2 , 2. (גם {0, 0, 0, 0, 2} או {2, 0, 2, 0, 2} מתאימים.)
בדיקה: על {0,2,0,0,2}, {0,0,0,0,2} ו־{2,0,2,0,2} מתקבל בכל פעם 2 2 2 2 2. בנוסף בדקנו בתוכנית את כל המערכים בגודל 5 עם ערכים מ־3− עד 6: המערך הופך לכולו 2 בדיוק כאשר arr[4] = 2 וכל שאר התאים הם 0 או 2.
טעות נפוצה: לבחור תא עם הערך 4 ("4 − 2 = 2") – אבל 4 אינו קטן מ־mx = 2, ולכן הוא לא משתנה וגם מעדכן את mx ל־4.
שאלה 2 · מבחן שחייה – בדיקת "כל הזמנים" ומניה (20 נקודות)
במועדון שחייה נערך מבחן מהירות. כל שחיין שוחה כמה אורכי בריכה, ולכל אורך נמדד הזמן שלו בשניות (מספר ממשי). שחיין עובר את המבחן אם הזמן של כל אחד מהאורכים שלו קטן מ־ 40 שניות.
הערה: אין צורך לבדוק את תקינות הקלט.
לפותרים בשפת Java: הניחו שבתוכנית כתובה ההוראה:Scanner input = new Scanner(System.in);
כתבו ב־ Java פעולה בשם passTest (ב־ C# – PassTest) שתקבל מספר שלם וגדול מ־ 0 המייצג את מספר האורכים ששחיין שחה במבחן. הפעולה תקלוט את הזמן של כל אחד מהאורכים.
הפעולה תחזיר true אם השחיין עבר את המבחן, אחרת — הפעולה תחזיר false.
כתבו ב־ Java פעולה בשם testDay (ב־ C# – TestDay) שתקלוט בעבור כל אחד מ־ 64 השחיינים שנבחנו ביום מסוים את מספר האורכים שהוא שחה. הפעולה תדפיס את מספר השחיינים שעברו את המבחן ואת מספר השחיינים שלא עברו אותו.
ניתן להשתמש בפעולה שכתבתם בסעיף 1.
◂ פתרון מלא לשאלה 2
סעיף 1
pass = true; קולטים את כל הזמנים, ואם time >= 40 – pass = false; מחזירים pass.
מה נדרש: פעולה שמקבלת את מספר האורכים, קולטת זמן לכל אורך, ומחזירה true רק אם כל הזמנים קטנים מ־40.
רעיון: בדיקת "כל האיברים מקיימים תנאי" בעזרת משתנה בוליאני: pass מתחיל ב־true, ואם נקלט זמן שאינו קטן מ־40 (כלומר time >= 40) – pass הופך ל־false. חשוב: הלולאה ממשיכה עד הסוף וקולטת את כל הזמנים של השחיין גם אחרי שהתברר שהוא נכשל, כדי שהזמנים שלו לא ייקלטו בטעות כנתונים של השחיין הבא (בסעיף 2). הזמן נקלט כמספר ממשי (double).
פתרון: הקוד המלא – בלשונית Java/C#.
בדיקה:
| מספר אורכים | זמנים | מוחזר |
|---|---|---|
| 3 | 38.5, 39.9, 31.0 | true |
| 3 | 38.5, 40, 31.0 | false (40 אינו קטן מ־40) |
| 4 | 41.2, 35.0, 36.4, 33.3 | false |
| 1 | 39.99 | true |
טעות נפוצה: לכתוב return false; מיד כשנמצא זמן איטי. הפעולה תצא לפני שקלטה את שאר הזמנים של אותו שחיין, והם ייקלטו אחר כך כאילו היו מספר האורכים והזמנים של השחיין הבא.
public static boolean passTest(int laps)
{
boolean pass = true;
for (int i = 0; i < laps; i++)
{
double time = input.nextDouble();
if (time >= 40)
pass = false;
}
return pass;
}סעיף 2
64 פעמים: קולטים מספר אורכים; אם passTest(laps) – passed++; בסוף מדפיסים passed ו־64 − passed.
מה נדרש: לקלוט לכל אחד מ־64 השחיינים את מספר האורכים שלו, ולהדפיס כמה עברו את המבחן וכמה לא עברו.
רעיון: לולאה של 64 סיבובים. בכל סיבוב קולטים את מספר האורכים ומזמנים את passTest – היא עצמה קולטת את הזמנים ומחזירה האם השחיין עבר. מונים את העוברים; מספר שלא עברו הוא 64 פחות מספר העוברים. בסוף מדפיסים את שני המספרים.
פתרון: הקוד המלא – בלשונית Java/C#.
בדיקה: על קלט של שחיינים עם מספרי אורכים וזמנים שונים הפעולה מדפיסה בדיוק כמה עברו וכמה לא עברו. שתי הגרסאות הדפיסו 45 19.
טעות נפוצה: לקלוט את הזמנים גם ב־testDay. הקליטה של הזמנים נעשית רק בתוך passTest; testDay קולטת רק את מספר האורכים.
public static void testDay()
{
int passed = 0;
for (int i = 1; i <= 64; i++)
{
int laps = input.nextInt();
if (passTest(laps))
passed++;
}
System.out.println(passed + " " + (64 - passed));
}שאלה 3 · סבב מסחר באסימונים (20 נקודות)
במשחק קופסה כל שחקן מחזיק אסימונים. נתון מערך tokens מטיפוס שלם, שבו tokens[i] הוא מספר האסימונים של השחקן שמספרו i . במערך יש לפחות שני תאים, כל הערכים בו אינם שליליים, ולפחות לשחקן אחד יש אסימון.
"סבב מסחר" הוא התהליך המתואר לפניכם, המבוצע 25 פעמים:
i. מוגרלים שני מספרי אינדקס תקינים (בגבולות גודל המערך): הראשון הוא השחקן הנותן, והשני הוא השחקן המקבל.
ii. השחקן הנותן מעביר אסימון אחד לשחקן המקבל.
הערה: אם בהגרלה עלו שני מספרי אינדקס זהים, או שלשחקן הנותן אין אסימונים, ההגרלה לא תיחשב (כלומר היא לא תיספר כחלק מן התהליך המבוצע 25 פעמים).
כתבו פעולה חיצונית ששמה trade בשפת Java או Trade בשפת C# המקבלת את המערך tokens ומבצעת בו "סבב מסחר".
הפעולה תדפיס את מספר האסימונים של כל שחקן לפי הסדר בתום הסבב (כל ערך בשורה חדשה).
כתבו פעולה חיצונית ששמה trade בשפת Java או Trade בשפת C# המקבלת את המערך tokens ומבצעת בו "סבב מסחר".
הפעולה תדפיס את מספר האסימונים של כל שחקן לפי הסדר בתום הסבב (כל ערך בשורה חדשה).
◂ פתרון מלא לשאלה 3
פתרון
לולאת while עם מונה count שגדל רק כאשר giver ≠ receiver וגם tokens[giver] > 0 (ואז tokens[giver]-- ו־ tokens[receiver]++); בסוף מדפיסים את המערך, ערך בכל שורה.
מה נדרש: לבצע 25 העברות "חוקיות" של אסימון בודד בין שני שחקנים מוגרלים, ואחר כך להדפיס את המערך, ערך בכל שורה.
רעיון:
rnd.nextInt(tokens.length) ב־ Java או rnd.Next(tokens.Length) ב־ C# .tokens[giver]-- ו־ tokens[receiver]++ . התנאי tokens[giver] > 0 מבטיח שאף ערך לא יהיה שלילי.פתרון:
public static void trade(int[] tokens)
{
Random rnd = new Random();
int count = 0;
while (count < 25)
{
int giver = rnd.nextInt(tokens.length);
int receiver = rnd.nextInt(tokens.length);
if (giver != receiver && tokens[giver] > 0)
{
tokens[giver]--;
tokens[receiver]++;
count++;
}
}
for (int i = 0; i < tokens.length; i++)
{
System.out.println(tokens[i]);
}
}(ב־ Java צריך import java.util.Random; בראש הקובץ.)
בדיקה: על המערך {10, 3, 0, 7, 5} מתקבל למשל 6 1 3 12 3; סכום האסימונים נשאר 25 , אין ערך שלילי, והשורות שמודפסות זהות לתאי המערך. בדיקה שנספרות בדיוק 25 העברות חוקיות: במערך {1, 0} יש אסימון אחד, וכל העברה חוקית מעבירה אותו לשחקן השני. אחרי 25 העברות (מספר אי־זוגי) חייב להתקבל {0, 1} – וזה מה שהתקבל ב־ 100 הרצות בכל שפה.
טעות נפוצה: להשתמש בלולאת for של 25 סיבובים (שסופרת גם הגרלות שלא נחשבות), או לבדוק רק אחד משני התנאים – למשל לא לבדוק tokens[giver] > 0 , ואז מספר האסימונים של שחקן יכול להפוך לשלילי.
public static void trade(int[] tokens)
{
Random rnd = new Random();
int count = 0;
while (count < 25)
{
int giver = rnd.nextInt(tokens.length);
int receiver = rnd.nextInt(tokens.length);
if (giver != receiver && tokens[giver] > 0)
{
tokens[giver]--;
tokens[receiver]++;
count++;
}
}
for (int i = 0; i < tokens.length; i++)
{
System.out.println(tokens[i]);
}
}פרק שני (60 נקודות)
ענו על שתיים מן השאלות 4–6 (לכל שאלה – 30 נקודות).
שאלה 4 · מטען בטיסה – Passenger ו־ Bag (30 נקודות)
בחברת תעופה, כל נוסע רשאי לשלוח מזוודה אחת לבטן המטוס ולעלות למטוס עם תיק יד אחד.
נתונה המחלקה Bag – המטען של נוסע, ולה שתי תכונות:
במחלקה Bag יש פעולה בונה המקבלת ערכים לשתי התכונות, ופעולות get/Get לתכונות.
נתונה גם המחלקה Passenger – נוסע בטיסה, ולה ארבע תכונות:
תעריפי החריגה הם 30 שקלים בעבור כל ק"ג שבו משקל המזוודה עולה על allowed , ותשלום קבוע נוסף של 100 שקלים אם משקל תיק היד גדול מ־ 8 ק"ג.
הניחו שקיימות פעולות get/Get לתכונות המחלקה Passenger.
כתבו פעולה בונה במחלקה Passenger , המקבלת את מספר הכרטיס – ticket ואת משקל המזוודה הכלול במחיר הכרטיס – allowed .
הפעולה מאתחלת את תכונות המחלקה. לנוסע עדיין אין מטען רשום, ולכן התכונה bag מאותחלת ל־ null , והתכונה fee מאותחלת ל־ 0 .
כתבו פעולה פנימית במחלקה Passenger ששמה checkIn בשפת Java או CheckIn בשפת C# , המקבלת את המטען של הנוסע – b (מטיפוס Bag).
הפעולה שומרת את b בתכונה bag , וקובעת ערך לתכונה fee בהתאם לחריגה במטען (ככל שיש) ולתעריפי החריגה.
הערה: fee היא 0 לפני הפעולה.
נתון מערך מלא – passengers מטיפוס Passenger , ובו נתונים על נוסעי טיסה אחת (כל הנוסעים כבר עברו רישום מטען בעזרת הפעולה מסעיף א(2)).
כתבו פעולה חיצונית ששמה countHeavy בשפת Java או CountHeavy בשפת C# , המקבלת את המערך passengers ומספר שלם – limit . הפעולה מחזירה את מספר הנוסעים שמשקל המזוודה שלהם גדול מ־ limit .
כתבו פעולה חיצונית ששמה heavyTickets בשפת Java או HeavyTickets בשפת C# , המקבלת את המערך passengers ומספר שלם – limit .
הפעולה מחזירה מערך מטיפוס שלם ובו מספרי הכרטיסים (ticket) של הנוסעים שמשקל המזוודה שלהם גדול מ־ limit (גודל המערך הוא בדיוק כמספר הנוסעים האלה). אין חשיבות לסדר ההופעה במערך.
הערה: חובה להיעזר בפעולה שכתבתם בסעיף ב(1).
◂ פתרון מלא לשאלה 4
סעיף א(1)
public Passenger(int ticket, int allowed) – השמה ל־ ticket ול־ allowed, bag = null, fee = 0.
מה נדרש: פעולה בונה שמקבלת שני פרמטרים ומאתחלת את ארבע התכונות.
רעיון: התכונה bag היא עצם מטיפוס Bag – זו מחלקה מורכבת (מחלקה שמכילה עצם של מחלקה אחרת). בשלב הבנייה אין עדיין מטען, ולכן מציבים בה null. את fee מאתחלים ל־ 0.
פתרון (תחילת המחלקה: התכונות והפעולה הבונה):
public class Passenger
{
private int ticket;
private int allowed;
private Bag bag;
private int fee;
public Passenger(int ticket, int allowed)
{
this.ticket = ticket;
this.allowed = allowed;
this.bag = null;
this.fee = 0;
}
// ... (checkIn ופעולות get בהמשך המחלקה)
}בדיקה: new Passenger(501, 20) – getTicket() החזירה 501, getAllowed() 20, getFee() 0, ו־ getBag() החזירה null.
public class Passenger
{
private int ticket;
private int allowed;
private Bag bag;
private int fee;
public Passenger(int ticket, int allowed)
{
this.ticket = ticket;
this.allowed = allowed;
this.bag = null;
this.fee = 0;
}
// ... (checkIn ופעולות get בהמשך המחלקה)
}סעיף א(2)
bag = b; fee = (b.getWeight() > allowed ? (b.getWeight() − allowed) · 30 : 0) + (b.getHandWeight() > 8 ? 100 : 0).
מה נדרש: לשמור את המטען בתכונה bag ולחשב את סכום החריגה.
רעיון:
this.bag = b.פתרון:
public void checkIn(Bag b)
{
this.bag = b;
int sum = 0;
if (b.getWeight() > this.allowed)
sum = sum + (b.getWeight() - this.allowed) * 30;
if (b.getHandWeight() > 8)
sum = sum + 100;
this.fee = sum;
}בדיקה:
new Bag(23, 10) → 3 × 30 + 100 = 190, ו־ getBag() מחזירה את אותו העצם.new Bag(23, 8) → 0 (שני המשקלים בדיוק בגבול).new Bag(12, 9) → 100 בלבד; נוסע (504, 20) עם new Bag(26, 5) → 180.טעות נפוצה: לחשב 100 לכל ק"ג חריגה בתיק היד, או לשכוח לשמור את b בתכונה bag (ואז getBag() מחזירה null והסעיפים הבאים נכשלים).
public void checkIn(Bag b)
{
this.bag = b;
int sum = 0;
if (b.getWeight() > this.allowed)
sum = sum + (b.getWeight() - this.allowed) * 30;
if (b.getHandWeight() > 8)
sum = sum + 100;
this.fee = sum;
}סעיף ב(1)
מונים את הנוסעים שבהם getBag().getWeight() > limit.
מה נדרש: למנות כמה נוסעים במערך שולחים מזוודה ששוקלת יותר מ־ limit.
רעיון: משקל המזוודה שמור בתוך העצם Bag של הנוסע, ולכן ניגשים אליו בשרשור: passengers[i].getBag().getWeight() – קודם מקבלים את עצם המטען, ואז את המשקל שלו. מונים את הנוסעים שבהם המשקל גדול מ־ limit.
פתרון:
public static int countHeavy(Passenger[] passengers, int limit)
{
int count = 0;
for (int i = 0; i < passengers.length; i++)
{
if (passengers[i].getBag().getWeight() > limit)
count++;
}
return count;
}בדיקה: מערך חמשת הנוסעים מסעיף א (משקלי מזוודות 23, 23, 12, 26, 0): עבור limit = 20 הוחזר 3; עבור limit = 0 הוחזר 4.
טעות נפוצה: לכתוב passengers[i].getWeight() – לנוסע אין פעולה כזו; המשקל שייך למטען.
public static int countHeavy(Passenger[] passengers, int limit)
{
int count = 0;
for (int i = 0; i < passengers.length; i++)
{
if (passengers[i].getBag().getWeight() > limit)
count++;
}
return count;
}סעיף ב(2)
int[] tickets = new int[countHeavy(passengers, limit)]; ממלאים בעזרת אינדקס נפרד k את ticket של כל נוסע שמשקל המזוודה שלו גדול מ־ limit.
מה נדרש: מערך באורך מדויק ובו מספרי הכרטיסים של הנוסעים שמזוודתם כבדה מ־ limit.
רעיון:
פתרון:
public static int[] heavyTickets(Passenger[] passengers, int limit)
{
int[] tickets = new int[countHeavy(passengers, limit)];
int k = 0;
for (int i = 0; i < passengers.length; i++)
{
if (passengers[i].getBag().getWeight() > limit)
{
tickets[k] = passengers[i].getTicket();
k++;
}
}
return tickets;
}בדיקה: על מערך חמשת הנוסעים: limit = 20 → {501, 502, 504}; limit = 23 → {504}; limit = 30 → מערך באורך 0.
טעות נפוצה: להקצות מערך בגודל passengers.length – כך נשארים בסוף תאים ריקים (0), והמערך אינו בגודל הנדרש.
public static int[] heavyTickets(Passenger[] passengers, int limit)
{
int[] tickets = new int[countHeavy(passengers, limit)];
int k = 0;
for (int i = 0; i < passengers.length; i++)
{
if (passengers[i].getBag().getWeight() > limit)
{
tickets[k] = passengers[i].getTicket();
k++;
}
}
return tickets;
}שאלה 5 · רשימות השמעה – שירים חסרים (30 נקודות)
נתונה המחלקה Playlist – רשימת השמעה באפליקציית מוזיקה, ולה שלוש תכונות:
הניחו שקיימות פעולות get/Get לתכונות המחלקה.
כתבו במחלקה Playlist פעולה פנימית ששמה missingFrom בשפת Java או MissingFrom בשפת C#, המקבלת רשימת השמעה (Playlist) אחרת – other . הפעולה מחזירה את מספר השירים ברשימה הנוכחית שאינם מופיעים ברשימה other .
נתונה המחלקה MusicLibrary – ספריית מוזיקה, ולה תכונה אחת:
המערך אינו ממוין לפי סדר כלשהו, כל רשימה מופיעה בו פעם אחת בלבד, ואין בו ערכי null .
כתבו במחלקה MusicLibrary פעולה פנימית ששמה countCovering בשפת Java או CountCovering בשפת C#, המקבלת רשימת השמעה (Playlist) – p , שאינה מופיעה במערך. הפעולה מחזירה את מספר הרשימות במערך שמכילות את כל השירים של p .
הערה: אפשר להיעזר בפעולה שכתבתם בסעיף א.
◂ פתרון מלא לשאלה 5
סעיף א
לכל שיר ב-this.songs מחפשים אותו במערך של other (חיפוש סדרתי); אם לא נמצא – count++. מחזירים count.
מה נדרש
פעולה פנימית ב-Playlist שסופרת כמה שירים של הרשימה הנוכחית (this) חסרים ברשימה other.
רעיון
לולאות מקוננות: הלולאה החיצונית עוברת על השירים של this; לכל שיר מבצעים חיפוש סדרתי במערך השירים של other (שמתקבל בעזרת getSongs()). משתמשים במשתנה בוליאני found שמפסיק את החיפוש כשהשיר נמצא. אם בסוף החיפוש found עדיין false – השיר חסר, ומגדילים את המונה.
פתרון
(הפעולה הבונה נכתבה לצורך הבדיקה בלבד.)
Java
public class Playlist
{
private String title; // שם רשימת ההשמעה
private int code; // קוד ייחודי
private int[] songs; // קודי השירים ברשימה
// פעולה בונה – לצורך הבדיקה בלבד
public Playlist(String title, int code, int[] songs)
{
this.title = title;
this.code = code;
this.songs = songs;
}
public String getTitle() { return this.title; }
public int getCode() { return this.code; }
public int[] getSongs() { return this.songs; }
// סעיף א
public int missingFrom(Playlist other)
{
int[] otherSongs = other.getSongs();
int count = 0;
for (int i = 0; i < this.songs.length; i++)
{
boolean found = false;
for (int j = 0; j < otherSongs.length && !found; j++)
{
if (this.songs[i] == otherSongs[j])
{
found = true;
}
}
if (!found)
{
count++;
}
}
return count;
}
}C#
public class Playlist
{
private string title; // שם רשימת ההשמעה
private int code; // קוד ייחודי
private int[] songs; // קודי השירים ברשימה
// פעולה בונה – לצורך הבדיקה בלבד
public Playlist(string title, int code, int[] songs)
{
this.title = title;
this.code = code;
this.songs = songs;
}
public string GetTitle() { return this.title; }
public int GetCode() { return this.code; }
public int[] GetSongs() { return this.songs; }
// סעיף א
public int MissingFrom(Playlist other)
{
int[] otherSongs = other.GetSongs();
int count = 0;
for (int i = 0; i < this.songs.Length; i++)
{
bool found = false;
for (int j = 0; j < otherSongs.Length && !found; j++)
{
if (this.songs[i] == otherSongs[j])
{
found = true;
}
}
if (!found)
{
count++;
}
}
return count;
}
}בדיקה
a = {12, 40, 7, 33, 5}, b = {7, 40, 90}, c = {90, 7, 40, 12}, d = { } (רשימה ריקה):
שימו לב שהפעולה אינה סימטרית: a.missingFrom(b) ≠ b.missingFrom(a).
טעות נפוצה: להגדיל את המונה בתוך הלולאה הפנימית בכל פעם ש-songs[i] != otherSongs[j] – כך שיר נספר כמה פעמים. ההחלטה "חסר" מתקבלת רק אחרי שהחיפוש בכל המערך של other הסתיים.
public class Playlist
{
private String title; // שם רשימת ההשמעה
private int code; // קוד ייחודי
private int[] songs; // קודי השירים ברשימה
// פעולה בונה – לצורך הבדיקה בלבד
public Playlist(String title, int code, int[] songs)
{
this.title = title;
this.code = code;
this.songs = songs;
}
public String getTitle() { return this.title; }
public int getCode() { return this.code; }
public int[] getSongs() { return this.songs; }
// סעיף א
public int missingFrom(Playlist other)
{
int[] otherSongs = other.getSongs();
int count = 0;
for (int i = 0; i < this.songs.length; i++)
{
boolean found = false;
for (int j = 0; j < otherSongs.length && !found; j++)
{
if (this.songs[i] == otherSongs[j])
{
found = true;
}
}
if (!found)
{
count++;
}
}
return count;
}
}סעיף ב
עוברים על lists; אם p.missingFrom(lists[i]) == 0 – count++. מחזירים count.
מה נדרש
פעולה פנימית ב-MusicLibrary (מחלקה שמכילה מערך של עצמים מטיפוס Playlist) שסופרת כמה רשימות במערך מכילות את כל השירים של p.
רעיון
רשימה lists[i] מכילה את כל השירים של p בדיוק כאשר אין ל-p אף שיר שחסר ב-lists[i], כלומר p.missingFrom(lists[i]) == 0. שימו לב לכיוון הקריאה: הפעולה נקראת על p ומקבלת את lists[i]. עוברים על המערך וסופרים.
פתרון
(הפעולה הבונה נכתבה לצורך הבדיקה בלבד.)
Java
public class MusicLibrary
{
private Playlist[] lists;
// פעולה בונה – לצורך הבדיקה בלבד
public MusicLibrary(Playlist[] lists)
{
this.lists = lists;
}
// סעיף ב
public int countCovering(Playlist p)
{
int count = 0;
for (int i = 0; i < this.lists.length; i++)
{
if (p.missingFrom(this.lists[i]) == 0)
{
count++;
}
}
return count;
}
}C#
public class MusicLibrary
{
private Playlist[] lists;
// פעולה בונה – לצורך הבדיקה בלבד
public MusicLibrary(Playlist[] lists)
{
this.lists = lists;
}
// סעיף ב
public int CountCovering(Playlist p)
{
int count = 0;
for (int i = 0; i < this.lists.Length; i++)
{
if (p.MissingFrom(this.lists[i]) == 0)
{
count++;
}
}
return count;
}
}בדיקה
בספרייה הרשימות a = {12, 40, 7, 33, 5}, c = {90, 7, 40, 12}, g = {40, 3, 7}:
טעות נפוצה: לקרוא lists[i].missingFrom(p) == 0 – זה בודק שכל השירים של lists[i] נמצאים ב-p, כלומר את הכיוון ההפוך.
public class MusicLibrary
{
private Playlist[] lists;
// פעולה בונה – לצורך הבדיקה בלבד
public MusicLibrary(Playlist[] lists)
{
this.lists = lists;
}
// סעיף ב
public int countCovering(Playlist p)
{
int count = 0;
for (int i = 0; i < this.lists.length; i++)
{
if (p.missingFrom(this.lists[i]) == 0)
{
count++;
}
}
return count;
}
}שאלה 6 · סכום ספרות – מספר עצמאי (30 נקודות)
undefined
ממשו את הפעולה שלפניכם:
Java – public static int digitSum (int num)
C# – public static int DigitSum (int num)
num הוא מספר שלם חיובי.
הפעולה תחזיר את סכום הספרות של num .
דוגמה: עבור num = 4735 הפעולה תחזיר את המספר 19 (4 + 7 + 3 + 5).
ממשו את הפעולה שלפניכם:
Java – public static int generate (int num)
C# – public static int Generate (int num)
num הוא מספר שלם חיובי.
הפעולה תחזיר את המספר המתקבל מחיבור num עם סכום הספרות שלו. נאמר ש־ num מייצר את המספר המוחזר.
דוגמה: עבור num = 47 הפעולה תחזיר את המספר 58 (47 + 4 + 7), כלומר 47 מייצר את 58 .
יש להשתמש בפעולה שכתבתם בסעיף א.
מספר שלם חיובי נקרא "מספר עצמאי" אם אין אף מספר שלם חיובי שמייצר אותו (כפי שהוגדר בסעיף ב).
שתי דוגמאות: המספר 20 הוא "מספר עצמאי", והמספר 21 אינו "מספר עצמאי".
הסבר:
| המספר | האם יש מספר שמייצר אותו? | מסקנה |
|---|---|---|
| 21 | כן: המספר 15 מייצר אותו (15 + 1 + 5 = 21) | אינו מספר עצמאי |
| 20 | לא: המספרים 1–9 מייצרים את המספרים הזוגיים 2–18, והמספרים 10–19 מייצרים את המספרים האי־זוגיים 11–29 | מספר עצמאי |
כתבו פעולה חיצונית ששמה isSelfNumber בשפת Java או IsSelfNumber בשפת C# , המקבלת מספר שלם חיובי – num . הפעולה תחזיר true אם num הוא "מספר עצמאי", אחרת הפעולה תחזיר false .
יש להשתמש בפעולות שכתבתם בסעיפים א–ב.
שימו לב: כל מספר שמייצר את num קטן מ־ num .
◂ פתרון מלא לשאלה 6
סעיף א
sum += num % 10; num = num / 10; (עד ש־ num == 0)
מה נדרש: להחזיר את סכום הספרות של num.
רעיון: פירוק מספר לספרות: בכל סיבוב num % 10 היא ספרת האחדות – מוסיפים אותה לסכום, ו־ num / 10 מוחק אותה. ממשיכים כל עוד num > 0.
פתרון: הקוד המלא – בלשונית Java / C#.
בדיקה: 4735: 5 → 8 → 11 → 19; הוחזר 19. גם digitSum(9) = 9 ו־ digitSum(1000) = 1.
public static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum = sum + num % 10;
num = num / 10;
}
return sum;
}סעיף ב
return num + digitSum(num);
מה נדרש: להחזיר num ועוד סכום הספרות שלו.
רעיון: שורה אחת בעזרת הפעולה מסעיף א: num + digitSum(num).
פתרון: הקוד המלא – בלשונית Java / C#.
בדיקה: generate(47) = 58; generate(15) = 21; generate(999) = 1026.
public static int generate(int num)
{
return num + digitSum(num);
}סעיף ג
לכל m מ־ 1 עד num − 1: אם generate(m) == num – return false; בסוף return true
מה נדרש: לבדוק שאין אף מספר חיובי m שמקיים generate(m) == num.
רעיון: חיפוש סדרתי. לפי ההערה, מספר שמייצר את num קטן ממנו, ולכן מספיק לבדוק את m = 1, 2, …, num − 1. ברגע שנמצא m עם generate(m) == num – num אינו עצמאי ומחזירים false. אם הלולאה הסתיימה בלי למצוא – מחזירים true.
(הפעולה generate משתמשת ב־ digitSum, ולכן שתי הפעולות מסעיפים א–ב משמשות כאן.)
פתרון: הקוד המלא – בלשונית Java / C#.
בדיקה:
המספרים העצמאיים עד 120 שהתקבלו: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97, 108, 110.
טעות נפוצה: לבדוק אם num מייצר מספר כלשהו (generate(num)) – כל מספר מייצר מספר אחר; השאלה היא אם מספר אחר מייצר את num.
public static boolean isSelfNumber(int num)
{
for (int m = 1; m < num; m++)
{
if (generate(m) == num)
return false;
}
return true;
}טבלת התשובות
| שאלה | סעיף | תשובה |
|---|---|---|
| 1 | א | arr = {3, 6, 8, 4, 7, 3, 4} |
| ב | למשל {0, 2, 0, 0, 2} (הופך ל־{2, 2, 2, 2, 2}). כל מערך שבו arr[4] = 2 וכל שאר התאים הם 0 או 2 (ולא כולם 2) מתאים. | |
| 2 | 1 | pass = true; קולטים את כל הזמנים, ואם time >= 40 – pass = false; מחזירים pass. |
| 2 | 64 פעמים: קולטים מספר אורכים; אם passTest(laps) – passed++; בסוף מדפיסים passed ו־64 − passed. | |
| 3 | - | לולאת while עם מונה count שגדל רק כאשר giver ≠ receiver וגם tokens[giver] > 0 (ואז tokens[giver]-- ו־ tokens[receiver]++); בסוף מדפיסים את המערך, ערך בכל שורה. |
| 4 | א(1) | public Passenger(int ticket, int allowed) – השמה ל־ ticket ול־ allowed, bag = null, fee = 0. |
| א(2) | bag = b; fee = (b.getWeight() > allowed ? (b.getWeight() − allowed) · 30 : 0) + (b.getHandWeight() > 8 ? 100 : 0). | |
| ב(1) | מונים את הנוסעים שבהם getBag().getWeight() > limit. | |
| ב(2) | int[] tickets = new int[countHeavy(passengers, limit)]; ממלאים בעזרת אינדקס נפרד k את ticket של כל נוסע שמשקל המזוודה שלו גדול מ־ limit. | |
| 5 | א | לכל שיר ב-this.songs מחפשים אותו במערך של other (חיפוש סדרתי); אם לא נמצא – count++. מחזירים count. |
| ב | עוברים על lists; אם p.missingFrom(lists[i]) == 0 – count++. מחזירים count. | |
| 6 | א | sum += num % 10; num = num / 10; (עד ש־ num == 0) |
| ב | return num + digitSum(num); | |
| ג | לכל m מ־ 1 עד num − 1: אם generate(m) == num – return false; בסוף return true |