מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2022 מועד ב'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2022 מועד ב', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 14)
בכל מבחן 14 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 10 נקודות.
שאלות 7-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 12 נקודות.
שאלות 11-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 18 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטת מחרוזות עד תנאי עצירה וספירה
כתבו קטע תוכנית הקולט מחרוזות עד שתיקלט מחרוזת המתחילה או מסתיימת באות 'Z'.
הקטע יחשב וידפיס את מספר המחרוזות אשר מתחילות וגם מסתיימות באות 'X'.
◂ פתרון מלא לשאלה 1
פתרון
לולאת while שקולטת מחרוזת כל עוד התו הראשון וגם התו האחרון שונים מ-'Z'; סופרים מחרוזות שהתו הראשון והאחרון שלהן 'X', ובסוף מדפיסים את המונה.
הרעיון: זו לולאה עם זקיף: לא יודעים מראש כמה מחרוזות ייקלטו, ולכן משתמשים ב-while. קולטים מחרוזת אחת לפני הלולאה, ובכל סיבוב בודקים אותה, ואז קולטים את הבאה.
1. התו הראשון של מחרוזת str הוא `str.charAt(0)` והתו האחרון הוא `str.charAt(str.length() - 1)` (ב-C#: `str[0]` ו-`str[str.Length - 1]`).
2. תנאי העצירה: המחרוזת מתחילה ב-'Z' או מסתיימת ב-'Z'. לכן הלולאה ממשיכה כל עוד התו הראשון שונה מ-'Z' וגם התו האחרון שונה מ-'Z' (שלילת "או" היא "וגם").
3. בתוך הלולאה: אם התו הראשון הוא 'X' וגם התו האחרון הוא 'X' – מגדילים את המונה count.
4. המחרוזת שעוצרת את הלולאה מתחילה או מסתיימת ב-'Z', ולכן בכל מקרה אינה יכולה להתחיל וגם להסתיים ב-'X'; אין צורך לבדוק אותה.
5. אחרי הלולאה מדפיסים את count.
נניח (כמקובל בקליטה) שכל מחרוזת שנקלטת אינה ריקה. מחרוזת של תו אחד "X" נספרת: התו הראשון והאחרון שלה הוא 'X'.
Scanner in = new Scanner(System.in);
int count = 0;
String str = in.next();
while (str.charAt(0) != 'Z' && str.charAt(str.length() - 1) != 'Z')
{
if (str.charAt(0) == 'X' && str.charAt(str.length() - 1) == 'X')
count++;
str = in.next();
}
System.out.println(count);int count = 0;
string str = Console.ReadLine();
while (str[0] != 'Z' && str[str.Length - 1] != 'Z')
{
if (str[0] == 'X' && str[str.Length - 1] == 'X')
count++;
str = Console.ReadLine();
}
Console.WriteLine(count);דוגמה: עבור הקלט XabX, hello, XX, X, AbX, XqqX, Zebra יודפס 4 (נספרות XabX, XX, X, XqqX; המחרוזת Zebra עוצרת את הקליטה).
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · מעקב אחר פעולה המחשבת מקסימום
נתונה הפעולה הבאה המקבלת מערך של מספרים חיוביים:
public static int what (double[] arr)
{
double m = 0;
int m1, m2;
for (int i = 0; i < arr.length; i++)
{
m1 = (m + arr[i])/2.0;
m2 = Math.abs((m - arr[i])/2.0);
m = m1 + m2;
}
return m;
}public static int What (double[] arr)
{
double m = 0;
int m1, m2;
for (int i = 0; i < arr.Length; i++)
{
m1 = (m + arr[i])/2.0;
m2 = Math.Abs((m - arr[i])/2.0);
m = m1 + m2;
}
return m;
}נתון מערך מספרים שלמים `int[] arr = {6, 2, 8, 12, 4}`
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה what(arr) וכתבו מה תהיה תוצאת הזימון.
מה מבצעת הפעולה what(arr) באופן כללי?
◂ פתרון מלא לשאלה 2
סעיף א
הזימון מחזיר 12.
הערה על הקוד: כפי שהוא מודפס, הקוד אינו עובר הידור: m1 ו-m2 הוגדרו int אבל מקבלים ביטוי מטיפוס double, הפעולה מוגדרת להחזיר int אבל מחזירה את m שהוא double, והמערך הנתון הוא int[] ולא double[]. הכוונה ברורה: כל החישובים נעשים במספרים ממשיים. נעקוב כאילו m1, m2 וערך ההחזרה הם double (בנתונים של הסעיף כל הערכים יוצאים שלמים, ולכן התוצאה זהה גם אם נחשב בשלמים).
בכל סיבוב: (הממוצע), (חצי המרחק), ו-.
אחרי i=4 התנאי `i < arr.length` (5 < 5) אינו מתקיים, הלולאה מסתיימת ומוחזר m.
תשובה: הפעולה מחזירה 12.
סעיף ב
מחזירה את הערך הגדול ביותר במערך (המקסימום).
לכל שני מספרים a ו-b מתקיים:
כי אם מקבלים , ואם מקבלים .
לכן בכל סיבוב : m שומר את הגדול מבין הערכים שנבדקו עד כה. m מתחיל ב-0, וכל המספרים במערך חיוביים, ולכן בסוף m הוא האיבר הגדול במערך (בדוגמה של סעיף א – 12).
תשובה: הפעולה מחזירה את הערך המקסימלי במערך.
שאלה 3 · פסגות במערך: בדיקה וספירה
איבר במערך נקרא "פסגה", אם ערכו גדול מערכים של שני שכניו.
כתבו פעולה המקבלת מערך של מספרים שלמים ומספר שלם המציין אינדקס (מיקום) במערך.
הפעולה תבדוק אם איבר שנמצא במקום הנתון הוא "פסגה". אם כן – הפעולה תחזיר ערך true,
ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isPeak(int[] arr, int index)public static bool IsPeak(int[] arr, int index)כתבו פעולה המקבלת מערך של מספרים שלמים ומחזירה את מספר הפסגות שיש בו.
חובה להשתמש בפעולה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 3
סעיף א
אם index הוא התא הראשון או האחרון (או מחוץ למערך) – false; אחרת מחזירים arr[index] > arr[index-1] && arr[index] > arr[index+1].
1. לתא הראשון (index = 0) ולתא האחרון (index = arr.length - 1) אין שני שכנים, ולפי ההגדרה הם לא יכולים להיות פסגה. לכן אם index קטן או שווה ל-0, או גדול או שווה ל-arr.length - 1, מחזירים false. הבדיקה גם מונעת גישה מחוץ לגבולות המערך.
2. אחרת משווים את האיבר לשני שכניו: הוא פסגה אם הוא גדול ממש מהשכן השמאלי arr[index-1] וגם מהשכן הימני arr[index+1]. מחזירים ישירות את ערך הביטוי הבוליאני.
public static boolean isPeak(int[] arr, int index)
{
if (index <= 0 || index >= arr.length - 1)
return false;
return arr[index] > arr[index - 1] && arr[index] > arr[index + 1];
}public static bool IsPeak(int[] arr, int index)
{
if (index <= 0 || index >= arr.Length - 1)
return false;
return arr[index] > arr[index - 1] && arr[index] > arr[index + 1];
}דוגמה: במערך {1, 5, 2, 7, 3, 3}: isPeak(arr, 1) מחזירה true (5 > 1 וגם 5 > 2), ו-isPeak(arr, 0) מחזירה false (תא ראשון).
תשובה: הפעולה שלמעלה.
סעיף ב
עוברים על כל האינדקסים, ולכל i שעבורו isPeak(arr, i) מחזירה true מגדילים מונה; מחזירים את המונה.
הרעיון: מונה count מתחיל ב-0. עוברים בלולאה על כל האינדקסים של המערך ומזמנים את isPeak מסעיף א לכל אחד. אם התא הוא פסגה – מגדילים את המונה. אפשר לעבור על כל התאים (כולל הראשון והאחרון), כי isPeak כבר מחזירה עבורם false. בסוף מחזירים את count. הסיבוכיות לינארית: , כאשר n אורך המערך.
public static int countPeaks(int[] arr)
{
int count = 0;
for (int i = 0; i < arr.length; i++)
if (isPeak(arr, i))
count++;
return count;
}public static int CountPeaks(int[] arr)
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
if (IsPeak(arr, i))
count++;
return count;
}דוגמה: במערך {1, 5, 2, 7, 3, 3, 4, 1} הפסגות הן 5 (אינדקס 1), 7 (אינדקס 3) ו-4 (אינדקס 6), והפעולה מחזירה 3. (ב-3, 3 אין פסגה, כי 3 אינו גדול ממש מ-3.)
תשובה: הפעולה שלמעלה.
שאלה 4 · מחלקות שחקן והצגה: הוספה וספירה
המחלקה שחקן התיאטרון (Actor) מאופיינת בתכונות הבאות:
•שם השחקן – name – מסוג מחרוזת, String.
•גיל השחקן – age – מסוג מספר שלם, int.
•מספר הצגות ששיחק עד היום – numActs – מסוג מספר שלם, int.
המחלקה הצגה (Act) מאופיינת בתכונות הבאות:
•שם ההצגה – actName – מסוג מחרוזת, String.
•אורך ההצגה בדקות – len – מסוג מספר שלם, int.
•מערך חד ממדי של שחקנים – actArr – מערך עצמים מסוג Actor.
•מספר השחקנים המשתתפים בהצגה – currentNum – מסוג שלם, int.
בכל הצגה יכולים לשחק לכל היותר 20 שחקנים.
כתבו את כותרת המחלקה Act, את התכונות ואת הפעולה הבונה המקבלת שני פרמטרים: שם ההצגה והאורך שלה. הפעולה הבונה מייצרת מערך שחקנים ריק.
שחקן יכול להשתתף בהצגה, אם הוא לפחות בן 45 ויש לו ניסיון של לפחות חמש הצגות בעבר.
כתבו במחלקה Act, פעולה המקבלת עצם מסוג שחקן ומוסיפה (אם אפשר) את השחקן להצגה.
כמו כן, הפעולה תחזיר אחת מהמחרוזות הבאות:
•אם אין מקום במערך תוחזר המחרוזת "no room".
•אם השחקן לא עמד בתנאים תוחזר המחרוזת "not suitable".
•אם השחקן התווסף להצגה, תוחזר המחרוזת "was added".
שחקן מנוסה הוא שחקן שיש לו ניסיון השתתפות בעשר הצגות לפחות.
כתבו במחלקה Act פעולה שמחזירה את מספר השחקנים המנוסים בהצגה.
◂ פתרון מלא לשאלה 4
סעיף א
מחלקה Act עם ארבע תכונות פרטיות; הבנאי Act(actName, len) מציב את הפרמטרים, יוצר actArr = new Actor[20] ומאפס את currentNum.
1. התכונות מוגדרות private (הסתרת מידע), לפי הטיפוסים שבשאלה.
2. הבנאי מקבל את שם ההצגה ואת האורך ומציב אותם בתכונות.
3. "מערך שחקנים ריק": בהצגה יכולים לשחק לכל היותר 20 שחקנים, ולכן יוצרים מערך של 20 הפניות (כולן null בהתחלה), ומספר השחקנים בפועל currentNum מתחיל ב-0. currentNum הוא גם המקום הפנוי הבא במערך.
public class Act
{
private String actName;
private int len;
private Actor[] actArr;
private int currentNum;
public Act(String actName, int len)
{
this.actName = actName;
this.len = len;
this.actArr = new Actor[20];
this.currentNum = 0;
}
}public class Act
{
private string actName;
private int len;
private Actor[] actArr;
private int currentNum;
public Act(string actName, int len)
{
this.actName = actName;
this.len = len;
this.actArr = new Actor[20];
this.currentNum = 0;
}
}תשובה: המחלקה שלמעלה.
סעיף ב
אם currentNum שווה לגודל המערך – "no room"; אם הגיל קטן מ-45 או מספר ההצגות קטן מ-5 – "not suitable"; אחרת מכניסים את השחקן ל-actArr[currentNum], מגדילים את currentNum ומחזירים "was added".
1. בודקים קודם אם יש מקום: המערך מלא כאשר currentNum שווה לגודלו (20). במקרה זה מחזירים "no room".
2. בודקים את התנאים של השחקן בעזרת פעולות ה-get של Actor (התכונות שלו פרטיות): השחקן לא מתאים אם גילו קטן מ-45 או שמספר ההצגות שלו קטן מ-5. במקרה זה מחזירים "not suitable".
3. אחרת מוסיפים את השחקן במקום הפנוי הראשון, actArr[currentNum], מגדילים את currentNum ב-1 ומחזירים "was added".
public String addActor(Actor actor)
{
if (this.currentNum == this.actArr.length)
return "no room";
if (actor.getAge() < 45 || actor.getNumActs() < 5)
return "not suitable";
this.actArr[this.currentNum] = actor;
this.currentNum++;
return "was added";
}public string AddActor(Actor actor)
{
if (this.currentNum == this.actArr.Length)
return "no room";
if (actor.GetAge() < 45 || actor.GetNumActs() < 5)
return "not suitable";
this.actArr[this.currentNum] = actor;
this.currentNum++;
return "was added";
}דוגמה: שחקן בן 45 עם 5 הצגות יתווסף ("was added"), שחקן בן 44 יקבל "not suitable", ואחרי 20 שחקנים כל ניסיון נוסף יחזיר "no room".
תשובה: הפעולה שלמעלה.
סעיף ג
סופרים את השחקנים במקומות 0 עד currentNum-1 שעבורם getNumActs() >= 10.
הרעיון: השחקנים נמצאים ברצף במקומות 0 עד currentNum - 1 (שאר התאים null), ולכן הלולאה רצה רק עד currentNum. לכל שחקן בודקים בעזרת getNumActs() אם שיחק לפחות 10 הצגות, וסופרים.
public int countExperienced()
{
int count = 0;
for (int i = 0; i < this.currentNum; i++)
if (this.actArr[i].getNumActs() >= 10)
count++;
return count;
}public int CountExperienced()
{
int count = 0;
for (int i = 0; i < this.currentNum; i++)
if (this.actArr[i].GetNumActs() >= 10)
count++;
return count;
}תשובה: הפעולה שלמעלה.
שאלה 5 · סיכום נתוני קורונה ממערך מדינות
בשל מגפת הקורונה ארגון הבריאות העולמי שומר לכל מדינה (Country) את הנתונים באים:
•שם המדינה – name – מטיפוס מחרוזת, String.
•מספר הנדבקים הכולל בקורונה עד כה – infected – מסוג שלם, int.
•מספר המחלימים עד כה – recovered – מסוג שלם, int.
•מספר המתים עד כה – dead – מסוג שלם, int.
במחלקה "מדינה" (Country) נתונה פעולה בונה המקבלת פרמטר לכל תכונה.
מצב נוכחי (Status) מאופיין באמצעות:
•מספר המדינות בהן אין נדבקים בקורונה – count1 – מסוג שלם, int.
•מספר המדינות בהן יותר מחלימים ממתים – count2 – מסוג שלם, int.
•שמות המדינות שבהן רוב הנדבקים החלימו – names – מסוג מחרוזת, String.
במחלקה "מצב נוכחי" (Status) נתונה פעולה בונה שאינה מקבלת פרמטרים:
public Status()
{
this.count1 = 0;
this.count2 = 0;
this.names = "";
}public Status()
{
this.count1 = 0;
this.count2 = 0;
this.names = "";
}כתבו פעולה חיצונית המקבלת כפרמטר מערך arr של עצמים מסוג "מדינה" (Country).
הפעולה תיצור ותחזיר עצם מסוג "מצב נוכחי" (Status) שערכי התכונות שלו ישקפו את נתוני כלל המדינות המופיעות במערך arr.
כותרת הפעולה:
public static Status worldStatus(Country[] arr)public static Status WorldStatus(Country[] arr)◂ פתרון מלא לשאלה 5
פתרון
יוצרים Status חדש; עוברים על המדינות: infected == 0 → count1++, recovered > dead → count2++, recovered*2 > infected → מוסיפים את השם ל-names; מציבים ב-set ומחזירים.
הרעיון: עוברים פעם אחת על כל המדינות ומעדכנים שלושה "צוברים": שני מונים ומחרוזת שמות. בסוף מציבים אותם בעצם Status חדש בעזרת פעולות ה-set (התכונות פרטיות, והפעולה חיצונית למחלקה).
1. יוצרים עצם `new Status()` – הבנאי מאפס את המונים ומציב מחרוזת ריקה.
2. לכל מדינה c במערך (נשתמש בפעולות ה-get שלה):
•אין נדבקים: `c.getInfected() == 0` → מגדילים את c1.
•יותר מחלימים ממתים: `c.getRecovered() > c.getDead()` → מגדילים את c2.
•רוב הנדבקים החלימו: מספר המחלימים גדול ממחצית הנדבקים. כדי להימנע מחילוק בשלמים כותבים `c.getRecovered() * 2 > c.getInfected()`. (במדינה בלי נדבקים: 0 > 0 אינו מתקיים, ולכן היא לא נכנסת לרשימה.) במקרה זה משרשרים את שם המדינה ורווח אחריו למחרוזת names.
3. מציבים את התוצאות ב-setCount1, setCount2, setNames ומחזירים את העצם.
public static Status worldStatus(Country[] arr)
{
Status st = new Status();
int c1 = 0;
int c2 = 0;
String names = "";
for (int i = 0; i < arr.length; i++)
{
Country c = arr[i];
if (c.getInfected() == 0)
c1++;
if (c.getRecovered() > c.getDead())
c2++;
if (c.getRecovered() * 2 > c.getInfected())
names = names + c.getName() + " ";
}
st.setCount1(c1);
st.setCount2(c2);
st.setNames(names);
return st;
}public static Status WorldStatus(Country[] arr)
{
Status st = new Status();
int c1 = 0;
int c2 = 0;
string names = "";
for (int i = 0; i < arr.Length; i++)
{
Country c = arr[i];
if (c.GetInfected() == 0)
c1++;
if (c.GetRecovered() > c.GetDead())
c2++;
if (c.GetRecovered() * 2 > c.GetInfected())
names = names + c.GetName() + " ";
}
st.SetCount1(c1);
st.SetCount2(c2);
st.SetNames(names);
return st;
}דוגמה: עבור המדינות A (0 נדבקים), B (100 נדבקים, 60 מחלימים, 5 מתים), C (100, 50, 1), D (10, 1, 3) מתקבל count1 = 1 (A), count2 = 2 (B ו-C), names = "B " (ב-C החלימו בדיוק חצי, זה לא רוב).
תשובה: הפעולה שלמעלה.
שאלה 6 · מעקב: חיפוש ספרה במספר
נתונות שתי הפעולות הבאות: what, where המקבלות כל אחת זוג מספרים שלמים וחיוביים:
public static boolean what(int num, int dig)
{
int s = 1;
int x;
while(num > 0)
{
x = num%10;
s = s*(x - dig);
num = num/10;
}
return s == 0;
}
public static boolean where(int[] arr)
{
for(int i = 0; i < arr.length; i++)
{
boolean isExist = what(arr[i]/10, arr[i]%10);
if(isExist)return false;
}
return true;
}public static bool What(int num, int dig)
{
int s = 1;
int x;
while(num > 0)
{
x = num%10;
s = s*(x - dig);
num = num/10;
}
return s == 0;
}
public static bool Where(int[] arr)
{
for(int i = 0; i < arr.Length; i++)
{
bool isExist = What(arr[i]/10, arr[i]%10);
if(isExist)return false;
}
return true;
}עקבו בעזרת טבלת המעקב אחרי זימון הפעולה what(18024,3) וכתבו מה תהיה תוצאת הזימון.
מה מבצעת הפעולה what(num, digit) באופן כללי עבור מספר שלם וחיובי num וספרה digit?
נתון המערך arr הבא המכיל מספרים שלמים:
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה where(arr) וכתבו את תוצאת הזימון.
אין צורך במעקב אחרי זימונים של הפעולה what.
◂ פתרון מלא לשאלה 6
סעיף א
s = -30 בסוף הלולאה, ולכן מוחזר false.
בכל סיבוב x מקבל את ספרת האחדות של num, s מוכפל ב-(x - dig), ו-num מאבד את ספרת האחדות. dig = 3.
num = 0, הלולאה נעצרת, והפעולה מחזירה את ערך הביטוי s == 0, כלומר -30 == 0 – שקר.
תשובה: what(18024,3) מחזירה false.
סעיף ב
מחזירה true אם הספרה digit מופיעה במספר num, אחרת false.
s הוא מכפלת ההפרשים (x - dig) על כל הספרות x של num. מכפלה של מספרים שלמים שווה 0 אם ורק אם אחד הגורמים שווה 0, כלומר אם ורק אם יש ספרה x ששווה ל-dig. (בסעיף א הספרה 3 אינה מופיעה ב-18024, ולכן התקבל false.)
תשובה: הפעולה בודקת אם הספרה digit מופיעה בין הספרות של num: מחזירה true אם כן ו-false אם לא.
סעיף ג
ב-i = 3 (8191) הספרה 1 מופיעה ב-819, isExist = true, והפעולה מחזירה false.
לכל איבר, where מפרידה את ספרת האחדות (arr[i]%10) משאר המספר (arr[i]/10) ושואלת בעזרת what (סעיף ב) אם ספרת האחדות מופיעה שוב בשאר הספרות. ברגע שנמצא איבר כזה מוחזר false.
האיבר 2402 (i = 4) כבר לא נבדק.
תשובה: where(arr) מחזירה false.
שאלה 7 · איגוד ספורט: הוספת מועדון, מקסימום ומצטיינים
נתונה המחלקה SportClube המתארת מועדון ספורט. למחלקה יש חמש תכונות:
•שם המועדון – name, מסוג מחרוזת.
•שם ענף הספורט – sportName, מסוג מחרוזת.
•העיר שבה מתקיימת הפעילות – city, מסוג מחרוזת.
•מספר הספורטאים – countOfPlayer, מסוג שלם.
•מספר המאמנים – countOfCoach, מסוג שלם.
איגוד הספורט הארצי SportUnion מאגד את מועדוני הספורט השונים.
למחלקה SportUnion שלוש תכונות:
•שם האיגוד – unionName מסוג מחרוזת.
•נתוני האיגוד – unionData – מערך המועדונים השייכים לאיגוד, מסוג SportClube, בגודל מקסימלי של 100.
•מספר המועדונים השייכים לאיגוד – numberUnion, מסוג שלם.
מספר המועדונים אינו עולה על גודל המקסימלי של המערך.
הניחו כי בשתי המחלקות קיימות פעולות מאחזרות (get) וקובעות (set).
אם מועדון ספורט רוצה להצטרף לאיגוד עליו להעביר אל האיגוד את נתוניו.
לא ניתן לצרף מועדון לאיגוד אם כבר קיים מועדון עם שם זהה מאותה עיר באותו ענף הספורט.
כתבו פעולה במחלקה SportUnion המקבלת מועדון (עצם מסוג SportClube) ובודקת אם אפשר לצרף את המועדון לאיגוד הארצי. אם כן – הפעולה מוסיפה את המועדון לאיגוד ומחזירה ערך true, אם לא – הפעולה מחזירה ערך false.
כתבו פעולה במחלקה SportUnion המחזירה את שם המועדון אשר יש לו הכי הרבה מאמנים.
אפשר להניח שיש רק מועדון אחד כזה.
איגוד ספורט נחשב מצטיין אם יש לו לפחות חמישה מועדונים, ובכל אחד מהמועדונים יש לפחות 50 ספורטאים. כתבו פעולה חיצונית המקבלת מערך איגודי הספורט (מערך עצמים מסוג SportUnion) ומדפיסה את שמות של כל איגודי הספורט המצטיינים.
◂ פתרון מלא לשאלה 7
סעיף א
אם המערך מלא או שקיים מועדון עם אותו שם, אותה עיר ואותו ענף – false; אחרת מוסיפים במקום numberUnion, מגדילים את numberUnion ומחזירים true.
1. אם המערך מלא (numberUnion שווה ל-100, גודל המערך) – אין מקום, מחזירים false.
2. עוברים על המועדונים הקיימים (מקומות 0 עד numberUnion - 1). אם נמצא מועדון שיש לו גם אותו שם, גם אותה עיר וגם אותו ענף ספורט כמו המועדון החדש – אסור לצרף, מחזירים false. השוואת מחרוזות נעשית ב-equals (ב-C# אפשר ב-==).
3. אם הלולאה הסתיימה בלי למצוא כפילות – מכניסים את המועדון למקום הפנוי הבא unionData[numberUnion], מגדילים את numberUnion ומחזירים true.
הפעולה נכתבת בתוך המחלקה SportUnion ולכן ניגשת ישירות לתכונות שלה, ולתכונות של SportClube – דרך פעולות ה-get.
public boolean addClub(SportClube club)
{
if (this.numberUnion == this.unionData.length)
return false;
for (int i = 0; i < this.numberUnion; i++)
{
SportClube c = this.unionData[i];
if (c.getName().equals(club.getName())
&& c.getCity().equals(club.getCity())
&& c.getSportName().equals(club.getSportName()))
return false;
}
this.unionData[this.numberUnion] = club;
this.numberUnion++;
return true;
}public bool AddClub(SportClube club)
{
if (this.numberUnion == this.unionData.Length)
return false;
for (int i = 0; i < this.numberUnion; i++)
{
SportClube c = this.unionData[i];
if (c.GetName() == club.GetName()
&& c.GetCity() == club.GetCity()
&& c.GetSportName() == club.GetSportName())
return false;
}
this.unionData[this.numberUnion] = club;
this.numberUnion++;
return true;
}דוגמה: אחרי הוספת ("Hapoel", "football", "Haifa"), ניסיון להוסיף מועדון נוסף בשם Hapoel בענף football בחיפה יחזיר false, אבל Hapoel בענף basketball בחיפה, או Hapoel בענף football באילת – יתווספו (true).
תשובה: הפעולה שלמעלה.
סעיף ב
חיפוש מקסימום לפי getCountOfCoach() על המועדונים 0 עד numberUnion-1, ומחזירים את getName() של המועדון שנמצא.
הרעיון: חיפוש מקסימום. שומרים את האינדקס maxIndex של המועדון עם הכי הרבה מאמנים עד כה (מתחילים מהמועדון הראשון), ועוברים על שאר המועדונים בטווח 1 עד numberUnion - 1. אם למועדון הנוכחי יש יותר מאמנים – מעדכנים את maxIndex. בסוף מחזירים את שמו. נניח שבאיגוד יש לפחות מועדון אחד (אחרת אין "מועדון עם הכי הרבה מאמנים").
public String maxCoachClub()
{
int maxIndex = 0;
for (int i = 1; i < this.numberUnion; i++)
if (this.unionData[i].getCountOfCoach() > this.unionData[maxIndex].getCountOfCoach())
maxIndex = i;
return this.unionData[maxIndex].getName();
}public string MaxCoachClub()
{
int maxIndex = 0;
for (int i = 1; i < this.numberUnion; i++)
if (this.unionData[i].GetCountOfCoach() > this.unionData[maxIndex].GetCountOfCoach())
maxIndex = i;
return this.unionData[maxIndex].GetName();
}תשובה: הפעולה שלמעלה.
סעיף ג
לכל איגוד: אם getNumberUnion() >= 5 וכל מועדון בו עם getCountOfPlayer() >= 50 – מדפיסים את getUnionName().
הרעיון: לכל איגוד בודקים שני תנאים:
1. מספר המועדונים (getNumberUnion()) לפחות 5.
2. בכל המועדונים יש לפחות 50 ספורטאים: משתנה בוליאני allBig מתחיל ב-true, ועוברים על המועדונים (getUnionData() במקומות 0 עד getNumberUnion() - 1). אם נמצא מועדון עם פחות מ-50 ספורטאים – allBig נהיה false והלולאה נעצרת.
אם שני התנאים מתקיימים – מדפיסים את שם האיגוד. הפעולה חיצונית, ולכן היא משתמשת רק בפעולות ה-get של SportUnion ו-SportClube.
public static void printExcellent(SportUnion[] unions)
{
for (int i = 0; i < unions.length; i++)
{
SportUnion u = unions[i];
if (u.getNumberUnion() >= 5)
{
SportClube[] clubs = u.getUnionData();
boolean allBig = true;
for (int j = 0; j < u.getNumberUnion() && allBig; j++)
if (clubs[j].getCountOfPlayer() < 50)
allBig = false;
if (allBig)
System.out.println(u.getUnionName());
}
}
}public static void PrintExcellent(SportUnion[] unions)
{
for (int i = 0; i < unions.Length; i++)
{
SportUnion u = unions[i];
if (u.GetNumberUnion() >= 5)
{
SportClube[] clubs = u.GetUnionData();
bool allBig = true;
for (int j = 0; j < u.GetNumberUnion() && allBig; j++)
if (clubs[j].GetCountOfPlayer() < 50)
allBig = false;
if (allBig)
Console.WriteLine(u.GetUnionName());
}
}
}תשובה: הפעולה שלמעלה.
שאלה 8 · מעקב: הסרת כפילויות סמוכות ממערך
נתונה פעולה הבאה:
public static int[] why(int[] arr)
{
int[] temp=new int[arr.length];
temp[0] = arr[0];
int count = 1;
for(int i = 1; i < arr.length; i++)
{
if(arr[i] != arr[i-1])
{
temp[count] = arr[i];
count++;
}
}
int[] res = new int[count];
for(int i = 0; i < count; i++)
res[i] = temp[i];
return res;
}public static int[] Why(int[] arr)
{
int[] temp=new int[arr.Length];
temp[0] = arr[0];
int count = 1;
for(int i = 1; i < arr.Length; i++)
{
if(arr[i] != arr[i-1])
{
temp[count] = arr[i];
count++;
}
}
int[] res = new int[count];
for(int i = 0; i < count; i++)
res[i] = temp[i];
return res;
}עקבו אחר ביצוע הפעולה עבור מערך הבא:
וכתבו מה תחזיר הפעולה
מה מבצעת הפעולה why באופן כללי?
◂ פתרון מלא לשאלה 8
סעיף א
הפעולה מחזירה את המערך {6, 2, 7, 9, 7, 3} (count = 6).
לפני הלולאה: temp[0] = arr[0] = 6, count = 1. בכל סיבוב משווים את arr[i] לאיבר שלפניו; אם הם שונים, arr[i] נכתב ל-temp[count] ו-count גדל.
בסוף count = 6, ולכן נוצר res בגודל 6, ומעתיקים אליו את temp[0] עד temp[5]:
תשובה: הפעולה מחזירה את המערך {6, 2, 7, 9, 7, 3}.
סעיף ב
מחזירה מערך חדש שבו כל רצף של איברים שווים וסמוכים מצומצם לאיבר אחד (מוחקת כפילויות סמוכות), בסדר המקורי.
איבר מועתק ל-temp רק אם הוא שונה מהאיבר שלפניו (האיבר הראשון מועתק תמיד). לכן מכל רצף של ערכים שווים הצמודים זה לזה נשאר רק הנציג הראשון, והסדר נשמר. ערך שחוזר שוב אחרי ערך אחר (כמו 7 בסעיף א) מופיע שוב. המערך המוחזר res הוא בגודל המדויק – מספר הרצפים count.
תשובה: הפעולה מחזירה מערך חדש שבו כל רצף של איברים סמוכים שווים מוחלף באיבר אחד, כלומר מוחקת חזרות רצופות ושומרת על הסדר.
שאלה 9 · בדיקת מחרוזת מיוחדת: אותיות ומופעים זוגיים
מחרוזת מיוחדת היא מחרוזת אשר מורכבת מאותיות קטנות של הא"ב האנגלי (a..z) בלבד או מאותיות גדולות של הא"ב האנגלי (A..Z) בלבד, וכל אות במחרוזת מופיעה מספר זוגי של הפעמים.
המחרוזות "cc", "abddba", "ZZRRYYYY" הן מיוחדות.
המחרוזות "AB", "abca", "ab*cd", "AAbb" אינן מיוחדות.
מחרוזת ריקה אינה מיוחדת.
כתבו פעולה אשר מקבלת כפרמטר מחרוזת ובודקת אם היא "מחרוזת מיוחדת".
אם כן – הפעולה תחזיר ערך true ואם לא, הפעולה תחזיר ערך false.
◂ פתרון מלא לשאלה 9
פתרון
מחרוזת ריקה – false; לפי התו הראשון קובעים טווח (a-z או A-Z, אחרת false); כל תו חייב להיות בטווח, וסופרים במערך מונים בגודל 26; בסוף כל המונים זוגיים – true.
הרעיון: יש שלושה תנאים: המחרוזת לא ריקה; כל התווים מאותו "סוג" (כולם קטנות או כולם גדולות); כל אות מופיעה מספר זוגי של פעמים.
1. מחרוזת ריקה – מחזירים false.
2. התו הראשון קובע את הטווח: אם הוא אות קטנה, הטווח הוא 'a' עד 'z'; אם הוא אות גדולה – 'A' עד 'Z'; אחרת (סימן כמו '*' או ספרה) – מחזירים false.
3. מערך מונים count בגודל 26 (אות לכל תא). עוברים על כל התווים: תו שאינו בטווח – מחזירים false (כך נפסלות "AAbb" ו-"ab*cd"). אחרת מגדילים את המונה של האות במקום `ch - low` (למשל עבור 'c' כשהטווח מ-'a': 'c' - 'a' = 2).
4. אחרי המעבר בודקים שכל המונים זוגיים (שארית 0 בחלוקה ב-2). מונה אי-זוגי – false (כך נפסלות "AB" ו-"abca"). אם כולם זוגיים – true. אות שלא הופיעה מונה 0, וזה זוגי.
הסיבוכיות: , כאשר n אורך המחרוזת (מעבר אחד על המחרוזת ועוד 26 בדיקות קבועות).
public static boolean isSpecial(String s)
{
if (s.length() == 0)
return false;
char low, high;
char first = s.charAt(0);
if (first >= 'a' && first <= 'z')
{
low = 'a';
high = 'z';
}
else if (first >= 'A' && first <= 'Z')
{
low = 'A';
high = 'Z';
}
else
return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (ch < low || ch > high)
return false;
count[ch - low]++;
}
for (int k = 0; k < 26; k++)
if (count[k] % 2 != 0)
return false;
return true;
}public static bool IsSpecial(string s)
{
if (s.Length == 0)
return false;
char low, high;
char first = s[0];
if (first >= 'a' && first <= 'z')
{
low = 'a';
high = 'z';
}
else if (first >= 'A' && first <= 'Z')
{
low = 'A';
high = 'Z';
}
else
return false;
int[] count = new int[26];
for (int i = 0; i < s.Length; i++)
{
char ch = s[i];
if (ch < low || ch > high)
return false;
count[ch - low]++;
}
for (int k = 0; k < 26; k++)
if (count[k] % 2 != 0)
return false;
return true;
}בדיקה מול הדוגמאות: "cc", "abddba", "ZZRRYYYY" ← true; "AB" (כל אות פעם אחת), "abca" (b ו-c פעם אחת), "ab*cd" ('*' אינו אות), "AAbb" (ערבוב גדולות וקטנות) ← false; "" ← false.
תשובה: הפעולה שלמעלה.
שאלה 10 · מעקב: שוויון סכומי שורות במערך דו-ממדי
נתונה פעולה what הבאה:
public static boolean what (int [][]arr)
{
int tempSum;
int sum=0;
for (int j = 0; j < arr[0].length; j++)
sum += arr[0][j];
for (int i = 1; i < arr.length; i++)
{
tempSum = 0;
for (int j = 0; j < arr[i].length; j++)
tempSum += arr[i][j];
if (tempSum != sum)
return false;
}
return true;
}public static bool What (int [,] arr)
{
int tempSum;
int sum=0;
for (int j = 0; j < arr.GetLength(1); j++)
sum += arr[0,j];
for (int i = 1; i < arr.GetLength(0); i++)
{
tempSum = 0;
for (int j = 0; j < arr. GetLength(1); j++)
tempSum += arr[i, j];
if (tempSum != sum)
return false;
}
return true;
}נתון מערך arr של מספרים שלמים הבא:
מלאו את המערך arr כך שאם נעביר אותו כפרמטר לפעולה what, הפעולה תחזיר את הערך true.
מה מבצעת הפעולה what באופן כללי?
מהי סיבוכיות הפעולה what כאשר היא מקבלת כפרמטר מערך דו-ממדי של N שורות ו- M עמודות.
◂ פתרון מלא לשאלה 10
סעיף א
כל שורה צריכה סכום 13, למשל שורה 1: 4, 1, 3, 5 ושורה 2: 10, 1, 1, 1.
הפעולה מחשבת את סכום השורה הראשונה ומחזירה true רק אם סכום כל שורה אחרת שווה לו. סכום שורה 0:
לכן צריך למלא את שורות 1 ו-2 כך שסכום כל אחת מהן יהיה 13. למשל:
מעקב: sum = 13; i = 1: tempSum = , שווה ל-sum, ממשיכים; i = 2: tempSum = , שווה; הלולאה מסתיימת ומוחזר true.
תשובה: כל מילוי שבו סכום שורה 1 וסכום שורה 2 שווים ל-13, למשל {4, 1, 3, 5} ו-{10, 1, 1, 1}.
סעיף ב
בודקת אם לכל השורות במערך הדו-ממדי אותו סכום (שווה לסכום השורה הראשונה): true אם כן, false אם לא.
הלולאה הראשונה מחשבת את sum – סכום שורה 0. הלולאה השנייה מחשבת לכל שורה i (מ-1 ועד האחרונה) את סכומה tempSum, ואם הוא שונה מ-sum מחזירה מיד false. אם כל השורות עברו את הבדיקה – מוחזר true.
תשובה: הפעולה בודקת אם סכומי כל השורות במערך שווים זה לזה; היא מחזירה true אם כן ו-false אם יש שורה שסכומה שונה מסכום השורה הראשונה.
סעיף ג
.
1. סכום השורה הראשונה: M פעולות.
2. במקרה הגרוע (כל הסכומים שווים, והפעולה מגיעה עד הסוף) הלולאה החיצונית רצה על שורות, ובכל אחת הלולאה הפנימית עוברת על M איברים: פעולות.
3. סך הכול – כל תא במערך נקרא פעם אחת לכל היותר.
תשובה: הסיבוכיות היא – במקרה הגרוע עוברים על כל התאים פעם אחת.
שאלה 11 · חשבוניות דלק: הוספה, סיכום יומי ומקסימום
בחברת הסעות מעוניינים לעקוב אחרי תצרוכת הדלק של כל אחד מכלי הרכב שהיא מפעילה לאורך תקופה של חודש (31 יום).
לשם כך, הוגדרה המחלקה חשבונית (Invoice) המכילה את פרטי התדלוק הבאים:
•יום התדלוק – day – בין 1 ל- 31 מסוג מספר שלם, int.
•מספר הרכב – num – מסוג מחרוזת, String.
•שם הנהג המתדלק – name – מסוג מחרוזת, String.
•כמות הדלק שתודלקה בתדלוק זה – fuel – מסוג מספר ממשי, double.
המידע על כל התדלוקים בחודש מסוים נשמר במחלקה MonthFuel.
למחלקה MonthFuel שתי תכונות:
•מערך חשבוניות – invoices – מערך עצמים מסוג Invoice.
•מספר חשבוניות בפועל – current – מסוג מספר שלם, int.
הכנסת הנתונים למערך החשבוניות לא בהכרח מתבצע לפי סדר הזמנים שבו החשבוניות הוצאו בפועל.
רכב יכול להיות מתודלק מספר פעמים בחודש או לא מתודלק כלל.
במחלקה MonthFuel הוגדר בנאי (constructor):
public MonthFuel()
{
this.invoices = new Invoice[1000];
this.current = 0;
}public MonthFuel()
{
this.invoices = new Invoice[1000];
this.current = 0;
}כתבו במחלקה MonthFuel פעולה בשם addInvoice המקבלת פרטי חשבונית (יום התדלוק, מספר הרכב, שם הנהג וכמות הדלק) ומוסיפה חשבונית למערך החשבוניות.
מערך החשבוניות יכיל את החשבוניות ברצף. אפשר להניח כי יש מקום להוספת החשבונית.
כתבו במחלקה MonthFuel פעולה בשם fuelPerDay המחזירה מערך בגודל 32 כך ש:
באינדקס 0 במערך – יהיה סה"כ כמות הדלק של כל רכבי החברה במשך החודש,
באינדקס 1 במערך – תהיה כמות הדלק שתדלקו בה את כל רכבי החברה ביום ה- 1 בחודש,
באינדקס 2 במערך – תהיה כמות הדלק שתדלקו בה את כל רכבי החברה ביום ה- 2 בחודש וכך הלאה.
כתבו במחלקה MonthFuel פעולה בשם maxFuelPerCar המחזירה את מספר הרכב שתדלק סה"כ הכי הרבה במהלך אותו החודש.
◂ פתרון מלא לשאלה 11
סעיף א
יוצרים new Invoice(day, num, name, fuel), מציבים ב-invoices[current] ומגדילים את current.
הרעיון: החשבוניות שמורות ברצף במקומות 0 עד current - 1, ולכן המקום הפנוי הבא הוא current. יוצרים עצם Invoice חדש בעזרת הבנאי שלו (מקבל פרמטר לכל תכונה), מציבים אותו ב-invoices[current] ומגדילים את current ב-1. לפי השאלה אין צורך לבדוק שיש מקום.
public void addInvoice(int day, String num, String name, double fuel)
{
this.invoices[this.current] = new Invoice(day, num, name, fuel);
this.current++;
}public void AddInvoice(int day, string num, string name, double fuel)
{
this.invoices[this.current] = new Invoice(day, num, name, fuel);
this.current++;
}תשובה: הפעולה שלמעלה.
סעיף ב
מערך צוברים double[32]: לכל חשבונית מוסיפים את fuel ל-res[day] וגם ל-res[0].
הרעיון: מערך צוברים שהאינדקס שלו הוא היום בחודש. אין צורך לעבור על החשבוניות לכל יום בנפרד: עוברים פעם אחת על כל החשבוניות, ולכל חשבונית מוסיפים את כמות הדלק שלה לתא של היום שלה (res[day], day בין 1 ל-31) וגם לתא 0 – הסכום החודשי. מערך double חדש ב-Java וב-C# מאותחל לאפסים. הסיבוכיות , כאשר n מספר החשבוניות.
public double[] fuelPerDay()
{
double[] res = new double[32];
for (int i = 0; i < this.current; i++)
{
Invoice inv = this.invoices[i];
res[inv.getDay()] += inv.getFuel();
res[0] += inv.getFuel();
}
return res;
}public double[] FuelPerDay()
{
double[] res = new double[32];
for (int i = 0; i < this.current; i++)
{
Invoice inv = this.invoices[i];
res[inv.GetDay()] += inv.GetFuel();
res[0] += inv.GetFuel();
}
return res;
}דוגמה: חשבוניות (יום 3, 40 ליטר), (יום 1, 30.5), (יום 3, 20), (יום 31, 5) נותנות res[0] = 95.5, res[1] = 30.5, res[3] = 60, res[31] = 5 ושאר התאים 0.
תשובה: הפעולה שלמעלה.
סעיף ג
לכל חשבונית i מחשבים את סך הדלק של הרכב שלה (סכום fuel על כל החשבוניות עם אותו num), ושומרים את הרכב עם הסכום המקסימלי; מחזירים את מספרו.
הרעיון: לרכב יכולות להיות כמה חשבוניות, מפוזרות במערך ולא לפי סדר, ולכן צריך לסכם לכל רכב את כל החשבוניות שלו.
1. עוברים על החשבוניות; לחשבונית i לוקחים את מספר הרכב car.
2. לולאה פנימית עוברת על כל החשבוניות ומסכמת את fuel של אלה שמספר הרכב שלהן שווה ל-car (השוואת מחרוזות ב-equals) – זה הסך החודשי של הרכב.
3. אם הסך גדול מהמקסימום עד כה – מעדכנים את המקסימום ואת מספר הרכב.
רכב עם כמה חשבוניות ייבדק כמה פעמים, אבל תמיד עם אותו סכום, ולכן התוצאה נכונה. רכב שלא תודלק כלל אינו מופיע במערך ואינו יכול להיות המקסימום. הסיבוכיות , כאשר n מספר החשבוניות. (אם אין חשבוניות כלל מוחזר null.)
public String maxFuelPerCar()
{
String maxCar = null;
double maxFuel = -1;
for (int i = 0; i < this.current; i++)
{
String car = this.invoices[i].getNum();
double total = 0;
for (int j = 0; j < this.current; j++)
if (this.invoices[j].getNum().equals(car))
total += this.invoices[j].getFuel();
if (total > maxFuel)
{
maxFuel = total;
maxCar = car;
}
}
return maxCar;
}public string MaxFuelPerCar()
{
string maxCar = null;
double maxFuel = -1;
for (int i = 0; i < this.current; i++)
{
string car = this.invoices[i].GetNum();
double total = 0;
for (int j = 0; j < this.current; j++)
if (this.invoices[j].GetNum() == car)
total += this.invoices[j].GetFuel();
if (total > maxFuel)
{
maxFuel = total;
maxCar = car;
}
}
return maxCar;
}דוגמה: עם החשבוניות מסעיף ב: רכב 11-222-33 תודלק ליטר ורכב 55-666-77 תודלק ליטר, ולכן מוחזר "55-666-77".
תשובה: הפעולה שלמעלה.
שאלה 12 · ספרייה: דירוג ספרים, השאלה וסינון
בספרייה העירונית יש מאגר מידע על הספרים שבה. בעבור כל ספר נשמר הדירוג שהתקבל על הספר מקוראי הספר על מידת ההנאה שלהם ממנו. כאשר קורא מחזיר ספר לספרייה הוא מזין את הדירוג שלו שהוא מספר שלם בין 0 לארבע, כאשר ארבע מציין את מידת ההנאה הגדולה ביותר. המידע על דירוג הספרים נשמר במאגר כך שאפשר לדעת כמה קוראים דרגו כל ספר בכל אחת מחמש הדרגות האפשריות (מערך מונים לפי דרגה).
עבור מאגר המידע הגדירו שתי מחלקות: המחלקה Book המייצגת ספר והמחלקה Library המייצגת ספרייה.
המחלקה Book מוגדרת באופן הבא:
public class Book
{
private int code; // קוד הספר
private String name; //שם הספר
private String genre; // סוג הספר (רומן, מתח, ילדים...)
private int numOfCopies; // מספר העותקים של הספר הזמינים עכשיו בספרייה (לא בהשאלה)
private int[] ratings; // מערך מונים של דרגות ההנאה של הקוראים מהספר
}public class Book
{
private int code; // קוד הספר
private string name; //שם הספר
private string genre; // סוג הספר (רומן, מתח, ילדים...)
private int numOfCopies; // מספר העותקים של הספר הזמינים עכשיו בספרייה (לא בהשאלה)
private int[] ratings; // מערך מונים של דרגות ההנאה של הקוראים מהספר
}כתבו במחלקה Book פעולה המקבלת דרוג חדש לספר ומעדכנת את מערך הדרוגים בהתאם.
כותרת הפעולה:
public void updateRating(int rate)public void UpdateRating(int rate)כתבו במחלקה Book פעולה לחישוב הדרוג הממוצע של הספר, המחושב ע"פ דרגות ההנאה שהספר קיבל. הפעולה תחזיר מספר ממשי המציין את דירוג הספר.
כותרת הפעולה:
public double calcRating()public double CalcRating()המחלקה Library מוגדרת באופן הבא:
public class Library
{
private Book [] books; // מערך הספרים בספרייה. כל ספר מופיע במערך פעם אחת.
}public class Library
{
private Book [] books; // מערך הספרים בספרייה. כל ספר מופיע במערך פעם אחת.
}כתבו במחלקה Library פעולה להשאלת ספר, הפעולה תקבל קוד ספר ותבדוק אם אפשר להשאילו (אם יש עותק זמין). אם אפשר להשאילו, הפעולה תעדכן את הספר בהתאם ותחזיר אמת, אם אי אפשר להשאיל את הספר הפעולה תחזיר שקר.
כותרת הפעולה:
public boolean isAvailable(int code)public bool IsAvailable(int code)כתבו במחלקה Library פעולה המקבלת את סוג הספר (רומן, מתח, ילדים וכו') ואת גובה הדירוג המינימאלי. הפעולה תדפיס את שמות הספרים העונים לקריטריונים האלה.
◂ פתרון מלא לשאלה 12
סעיף א
ratings[rate]++ – מגדילים את המונה של הדרגה שהתקבלה.
הרעיון: ratings הוא מערך מונים בגודל 5: התא ratings[r] שומר כמה קוראים נתנו לספר את הדרגה r (בין 0 ל-4). דירוג חדש rate פירושו קורא נוסף שנתן את הדרגה rate, ולכן מגדילים ב-1 את התא שהאינדקס שלו הוא rate. (נניח שהבנאי של Book יוצר את המערך בגודל 5, ושהדירוג תקין, בין 0 ל-4.)
public void updateRating(int rate)
{
this.ratings[rate]++;
}public void UpdateRating(int rate)
{
this.ratings[rate]++;
}תשובה: הפעולה שלמעלה.
סעיף ב
ממוצע משוקלל: (ו-0 אם אין דירוגים).
הרעיון: זה ממוצע משוקלל. כל דרגה r נספרת כמספר הקוראים שנתנו אותה:
המונה הוא סכום כל הדירוגים, והמכנה הוא מספר הקוראים שדירגו.
1. עוברים על r מ-0 עד 4: sum מצטבר ב-r * ratings[r], ו-count מצטבר ב-ratings[r].
2. אם אף קורא לא דירג (count = 0) מחזירים 0, כדי לא לחלק באפס.
3. אחרת מחזירים sum / count, עם המרה ל-double כדי שהחילוק לא יהיה חילוק בשלמים.
public double calcRating()
{
int sum = 0;
int count = 0;
for (int r = 0; r < this.ratings.length; r++)
{
sum += r * this.ratings[r];
count += this.ratings[r];
}
if (count == 0)
return 0;
return (double) sum / count;
}public double CalcRating()
{
int sum = 0;
int count = 0;
for (int r = 0; r < this.ratings.Length; r++)
{
sum += r * this.ratings[r];
count += this.ratings[r];
}
if (count == 0)
return 0;
return (double) sum / count;
}דוגמה: אם התקבלו הדירוגים 4, 3, 2, אז ratings = {0, 0, 1, 1, 1}, ו-
תשובה: הפעולה שלמעלה.
סעיף ג
מחפשים את הספר לפי getCode(); אם getNumOfCopies() > 0 – מקטינים את מספר העותקים ב-1 ומחזירים true, אחרת false.
1. מחפשים במערך books את הספר שהקוד שלו שווה ל-code (בעזרת getCode(), כי התכונות של Book פרטיות).
2. כשנמצא: אם יש עותק זמין (getNumOfCopies() > 0) – משאילים: מעדכנים את מספר העותקים הזמינים למספר הקודם פחות 1 בעזרת setNumOfCopies ומחזירים true. אם אין עותק זמין – מחזירים false.
3. הקוד תקין לפי השאלה, ולכן הספר תמיד יימצא; ה-return false בסוף נדרש רק כדי שהפעולה תעבור הידור.
public boolean isAvailable(int code)
{
for (int i = 0; i < this.books.length; i++)
{
if (this.books[i].getCode() == code)
{
int copies = this.books[i].getNumOfCopies();
if (copies > 0)
{
this.books[i].setNumOfCopies(copies - 1);
return true;
}
return false;
}
}
return false;
}public bool IsAvailable(int code)
{
for (int i = 0; i < this.books.Length; i++)
{
if (this.books[i].GetCode() == code)
{
int copies = this.books[i].GetNumOfCopies();
if (copies > 0)
{
this.books[i].SetNumOfCopies(copies - 1);
return true;
}
return false;
}
}
return false;
}דוגמה: לספר עם 2 עותקים זמינים: שני זימונים ראשונים מחזירים true (נשארים 1 ואז 0 עותקים), והזימון השלישי מחזיר false.
תשובה: הפעולה שלמעלה.
סעיף ד
עוברים על הספרים ומדפיסים את getName() של כל ספר ש-getGenre() שלו שווה לסוג שהתקבל ו-calcRating() שלו גדול או שווה לדירוג המינימלי.
הרעיון: עוברים על כל הספרים במערך. ספר עונה לקריטריונים אם:
1. הסוג שלו (getGenre()) שווה לסוג שהתקבל – השוואת מחרוזות ב-equals (ב-C# ב-==);
2. הדירוג הממוצע שלו, שמחושב בפעולה calcRating() מסעיף ב, גדול או שווה לדירוג המינימלי.
כל ספר כזה – מדפיסים את שמו. הדירוג המינימלי מתקבל כמספר ממשי, כי הדירוג הממוצע ממשי.
public void printBooks(String genre, double minRating)
{
for (int i = 0; i < this.books.length; i++)
{
Book b = this.books[i];
if (b.getGenre().equals(genre) && b.calcRating() >= minRating)
System.out.println(b.getName());
}
}public void PrintBooks(string genre, double minRating)
{
for (int i = 0; i < this.books.Length; i++)
{
Book b = this.books[i];
if (b.GetGenre() == genre && b.CalcRating() >= minRating)
Console.WriteLine(b.GetName());
}
}תשובה: הפעולה שלמעלה.
שאלה 13 · רקורסיה: ממוצע ספרות ובדיקת סדרה
נתונות הפעולות sod, secret הבאות:
הפעולה sod מקבלת מספר שלם וחיובי (גדול מ-0).
public static double sod (int n)
{
return sod (n,0,0);
}
private static double sod (int n, int c, double a)
{
if (n == 0 && c == 0) return 0;
else
if(n == 0) return a/c;
else return sod (n/10, c+1, a+ (n % 10));
}public static double Sod (int n)
{
return Sod (n,0,0);
}
private static double Sod (int n, int c, double a)
{
if (n == 0 && c == 0) return 0;
else
if(n == 0) return a/c;
else return Sod (n/10, c+1, a+ (n % 10));
}הפעולה secret מקבלת מערך מלא במספרים חיוביים (גדולים מ- 0).
public static boolean secret (int [] a)
{
return secret (a, a.length-1);
}
public static boolean secret (int[] a, int m)
{
if(m==0) return true;
else
return secret(a, m-1) && (sod(a[m]) - sod(a[m-1]) == 1);
}public static bool Secret (int [] a)
{
return Secret (a, a.Length-1);
}
public static bool Secret (int[] a, int m)
{
if(m==0) return true;
else
return Secret(a, m-1) && (Sod(a[m]) - Sod(a[m-1]) == 1);
}עקבו אחרי זימון sod (3234) ורשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה sod(n) עבור מספר שלם גדול מ- 0?
נתון מערך a בגודל n=6:
עקבו אחרי זימון secret (a) ורשמו את תוצאות הזימון. יש להראות מעקב! אין צורך במעקב אחרי הפעולה sod.
שנו את סדר האיברים במערך a כך שזימון secret (a) יחזיר את תוצאה ההפוכה לזו שהתקבלה בסעיף ג'.
מה מבצעת הפעולה secret(a) עבור מערך של מספרים שלמים גדולים מ- 0?
◂ פתרון מלא לשאלה 13
סעיף א
sod(3234) = 12/4 = 3.0
sod(3234) מזמנת את sod(3234, 0, 0). בכל קריאה רקורסיבית: n מאבד את ספרת האחדות, c (מונה הספרות) גדל ב-1, ו-a (סכום הספרות) גדל בספרת האחדות n % 10.
הערך 3.0 חוזר ללא שינוי דרך כל הקריאות (כל קריאה מחזירה את תוצאת הקריאה הבאה) עד לזימון המקורי.
תשובה: sod(3234) מחזירה 3.0.
סעיף ב
מחזירה את ממוצע הספרות של n.
בסוף הרקורסיה a הוא סכום כל הספרות של n ו-c הוא מספר הספרות, והפעולה מחזירה (חילוק ממשי, כי a מטיפוס double). בסעיף א: . (המקרה n == 0 && c == 0 קורה רק עבור n = 0, שאינו בתחום.)
תשובה: sod(n) מחזירה את ממוצע הספרות של n.
סעיף ג
secret(a) מחזירה false (ההפרש בין sod(51)=3 ל-sod(864)=6 אינו 1).
ממוצעי הספרות (sod) של איברי המערך:
secret(a) מזמנת את secret(a, 5). כל קריאה עם m > 0 מזמנת קודם את secret(a, m-1) (הצד השמאלי של &&), וכך הקריאות יורדות עד m = 0. אחר כך התוצאות חוזרות מלמטה למעלה:
תשובה: secret(a) מחזירה false.
סעיף ד
למשל {51, 17, 5, 864, 77, 789} – ממוצעי הספרות 3, 4, 5, 6, 7, 8, ו-secret מחזירה true.
בסעיף ג התקבל false, ולכן צריך סדר שעבורו יוחזר true: כל ממוצע ספרות גדול בדיוק ב-1 מהממוצע של האיבר שלפניו. ממוצעי הספרות של האיברים הם 4, 5, 6, 3, 7, 8 – כלומר בדיוק הערכים 3 עד 8, ולכן מסדרים את האיברים לפי ממוצע הספרות בסדר עולה:
כל ההפרשים הסמוכים שווים 1, ולכן כל הקריאות מחזירות true.
תשובה: a = {51, 17, 5, 864, 77, 789}, ו-secret(a) מחזירה true.
סעיף ה
מחזירה true אם ממוצע הספרות של כל איבר גדול בדיוק ב-1 מממוצע הספרות של האיבר שלפניו (סדרה עולה בהפרש 1), אחרת false.
secret(a, m) מחזירה true אם ורק אם secret(a, m-1) מחזירה true וגם . בפריסה של הרקורסיה מ-m = a.length - 1 עד 0 מקבלים שהתנאי חייב להתקיים לכל זוג סמוך במערך. (מערך עם איבר אחד – true.)
תשובה: הפעולה בודקת אם ממוצעי הספרות של איברי המערך יוצרים סדרה עולה שבה כל ממוצע גדול ב-1 בדיוק מהקודם: true אם כן, false אחרת.
שאלה 14 · זוג מתאים: מערך חד-ממדי ודו-ממדי
מערך חד-ממדי arr ומערך דו-ממדי mat נקראים "זוג מתאים" אם מתקיימים התנאים הבאים:
•מספר העמודות במערך mat שווה למספר התאים במערך arr.
•כל איבר arr[k] מופיע בעמודה k של המערך mat בדיוק k פעמים.
לדוגמה:
שני מערכים arr ו- mat הבאים הם "זוג מתאים".
arr:
mat:
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים mat, מספר עמודה col וערך שלם value.
הפעולה תחזיר את מספר המופעים של הערך value בעמודה col.
כותרת הפעולה:
public static int numValues (int[][] mat, int col, int value)public static int NumValues (int[ , ] mat, int col, int value)כתבו פעולה המקבלת מערך דו-ממדי mat ומערך חד-ממדי arr. הפעולה תבדוק אם המערכים הם "זוג מתאים". אם כן – הפעולה תחזיר true, ולא – הפעולה תחזיר false.
כותרת הפעולה:
public static boolean isPair (int[][] mat, int[] arr)public static bool IsPair (int[ , ] mat, int[] arr)מהי סיבוכיות של הפעולה isPair? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 14
סעיף א
מונה על כל השורות i: אם mat[i][col] == value מגדילים; מחזירים את המונה.
הרעיון: העמודה col קבועה, ועוברים על כל השורות (ב-Java: mat.length שורות; ב-C#: mat.GetLength(0)). בכל שורה i בודקים את התא mat[i][col] (ב-C#: mat[i, col]); אם הוא שווה ל-value – מגדילים מונה. הסיבוכיות , כאשר N מספר השורות.
public static int numValues(int[][] mat, int col, int value)
{
int count = 0;
for (int i = 0; i < mat.length; i++)
if (mat[i][col] == value)
count++;
return count;
}public static int NumValues(int[,] mat, int col, int value)
{
int count = 0;
for (int i = 0; i < mat.GetLength(0); i++)
if (mat[i, col] == value)
count++;
return count;
}דוגמה: במערך mat שבשאלה, numValues(mat, 3, 15) מחזירה 3 (שורות 1, 3, 4).
תשובה: הפעולה שלמעלה.
סעיף ב
אם מספר העמודות שונה מ-arr.length – false; אחרת לכל k: אם numValues(mat, k, arr[k]) != k – false; אם כולם עברו – true.
הרעיון: בודקים את שני התנאים של ההגדרה, ומשתמשים בפעולה מסעיף א:
1. מספר העמודות של mat (אורך שורה, mat[0].length; ב-C#: mat.GetLength(1)) חייב להיות שווה ל-arr.length. אחרת – false.
2. לכל אינדקס k במערך arr: מספר המופעים של arr[k] בעמודה k הוא numValues(mat, k, arr[k]), והוא חייב להיות בדיוק k. אם עבור k כלשהו המספר שונה – false.
3. אם כל הבדיקות עברו – true.
(נניח של-mat יש לפחות שורה אחת, וכל השורות באותו אורך.)
public static boolean isPair(int[][] mat, int[] arr)
{
if (mat[0].length != arr.length)
return false;
for (int k = 0; k < arr.length; k++)
if (numValues(mat, k, arr[k]) != k)
return false;
return true;
}public static bool IsPair(int[,] mat, int[] arr)
{
if (mat.GetLength(1) != arr.Length)
return false;
for (int k = 0; k < arr.Length; k++)
if (NumValues(mat, k, arr[k]) != k)
return false;
return true;
}בדיקה עם הדוגמה: 5 מופיע 0 פעמים בעמודה 0, 12 פעם אחת בעמודה 1, 4 פעמיים בעמודה 2 ו-15 שלוש פעמים בעמודה 3 – הפעולה מחזירה true. אם arr[3] היה 14 (מופיע פעם אחת בעמודה 3), או ש-arr היה באורך 3, הפעולה הייתה מחזירה false.
תשובה: הפעולה שלמעלה.
סעיף ג
, כאשר N מספר השורות ו-M מספר העמודות (אורך arr).
נסמן ב-N את מספר השורות של mat וב-M את מספר העמודות (ששווה לאורך arr אחרי הבדיקה הראשונה).
1. בדיקת מספר העמודות – פעולה אחת, .
2. במקרה הגרוע (זוג מתאים) הלולאה רצה M פעמים, ובכל סיבוב numValues עוברת על N שורות – .
3. סך הכול – כל תא במערך mat נבדק פעם אחת.
תשובה: הסיבוכיות היא .