מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2021 מועד א'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2021 מועד א', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 13)
בכל מבחן 13 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 10 נקודות.
שאלות 7-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 11-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 18 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטת 35 מספרים והדפסת הגדולים מהממוצע
כתבו קטע תוכנית הקולטת 35 מספרים שלמים. התוכנית תחשב את הממוצע ותדפיס כל מספר שגדול מהממוצע.
◂ פתרון מלא לשאלה 1
פתרון
שומרים את 35 המספרים במערך וצוברים את סכומם; ממוצע = סכום/35 (חילוק ממשי); במעבר שני על המערך מדפיסים כל איבר שגדול מהממוצע.
הרעיון: את הממוצע אפשר לדעת רק אחרי שכל 35 המספרים נקלטו, ורק אז אפשר להחליט אילו מספרים גדולים ממנו. לכן חייבים לשמור את המספרים במערך, ולעבור עליהם פעמיים:
1. מעבר ראשון (בזמן הקליטה): כל מספר נשמר בתא הבא במערך ומתווסף לצובר `sum`.
2. חישוב הממוצע: . מכיוון ש-`sum` שלם, ממירים ל-double לפני החילוק, אחרת החלק העשרוני ייחתך והממוצע יהיה שגוי. למשל, עבור המספרים ו- הממוצע הוא ו- גדול ממנו, אבל בחילוק שלמים נותן , ו- לא היה מודפס.
3. מעבר שני על המערך: מדפיסים כל איבר שמקיים `arr[i] > avg`.
הסיבוכיות: שני מעברים על 35 איברים, כלומר .
import java.util.Scanner;
public class Q1
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int[] arr = new int[35];
int sum = 0;
// קליטה ושמירה במערך, תוך צבירת הסכום
for (int i = 0; i < arr.length; i++)
{
arr[i] = in.nextInt();
sum += arr[i];
}
double avg = (double) sum / arr.length;
System.out.println("Average: " + avg);
// מעבר שני: הדפסת המספרים הגדולים מהממוצע
for (int i = 0; i < arr.length; i++)
{
if (arr[i] > avg)
System.out.println(arr[i]);
}
}
}using System;
class Program
{
static void Main(string[] args)
{
int[] arr = new int[35];
int sum = 0;
// קליטה ושמירה במערך, תוך צבירת הסכום
for (int i = 0; i < arr.Length; i++)
{
arr[i] = int.Parse(Console.ReadLine());
sum += arr[i];
}
double avg = (double)sum / arr.Length;
Console.WriteLine("Average: " + avg);
// מעבר שני: הדפסת המספרים הגדולים מהממוצע
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > avg)
Console.WriteLine(arr[i]);
}
}
}דוגמה קטנה (עם 5 מספרים במקום 35): עבור 4, 8, 1, 10, 7 הסכום 30 והממוצע 6.0, ויודפסו 8, 10, 7.
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · מערך מיקומי פחי אשפה שיש לרוקן
במסגרת פרויקט עיר ירוקה הוחלט למחשב את פחי האשפה בעיר. לשם כך הוגדרה המחלקה "פח אשפה" Garbage. להלן תכונות המחלקה:
•location - מיקום הפח מטיפוס מחרוזת, String.
•capacity - קיבולת מקסימלית בק"ג לפח מטיפוס ממשי, double.
•quantity - כמות ק"ג נוכחית בפח מטיפוס ממשי, double.
כמו כן הוגדרו פעולות get לכל תכונה.
יש לרוקן פח כאשר הוא מכיל יותר מחצי מהקיבולת המקסימלית.
כתבו פעולה חיצונית המקבלת מערך של פחי אשפה ומחזירה מערך של מיקומי פחי האשפה שיש לרוקן.
המערך שיוחזר צריך להכיל בדיוק את הפחים שיש לרוקנם. אין ליצור מקומות ריקים במערך.
◂ פתרון מלא לשאלה 2
פתרון
שני מעברים: סופרים כמה פחים מקיימים quantity > capacity/2, יוצרים מערך String בגודל הזה, ובמעבר שני מעתיקים אליו את המיקומים.
נתון: מערך עצמים מסוג Garbage עם פעולות `getLocation()`, `getCapacity()`, `getQuantity()`.
מבוקש: מערך מחרוזות שמכיל בדיוק את המיקומים של הפחים שיש לרוקן.
הבעיה: גודל מערך נקבע ברגע היצירה, ואנחנו לא יודעים מראש כמה פחים יש לרוקן. לכן עובדים בשני מעברים:
1. ספירה: עוברים על כל הפחים וסופרים כמה מהם מקיימים (פח "מלא יותר מחצי").
2. יצירת מערך מחרוזות בגודל `count` בדיוק - כך לא יהיו בו תאים ריקים.
3. העתקה: עוברים שוב על הפחים, ובכל פח שיש לרוקן מכניסים את המיקום שלו לתא הבא (אינדקס `k` שמתקדם רק כשמעתיקים).
התנאי זהה בשני המעברים, ולכן `k` מגיע בסוף בדיוק ל-`count`. הקיבולת והכמות ממשיות, ולכן החילוק `getCapacity() / 2` הוא חילוק ממשי. הסיבוכיות .
public static String[] binsToEmpty(Garbage[] arr)
{
// מעבר ראשון: כמה פחים יש לרוקן
int count = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getQuantity() > arr[i].getCapacity() / 2)
count++;
}
// מערך בגודל המדויק
String[] res = new String[count];
// מעבר שני: העתקת המיקומים
int k = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getQuantity() > arr[i].getCapacity() / 2)
{
res[k] = arr[i].getLocation();
k++;
}
}
return res;
}public static string[] BinsToEmpty(Garbage[] arr)
{
// מעבר ראשון: כמה פחים יש לרוקן
int count = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetQuantity() > arr[i].GetCapacity() / 2)
count++;
}
// מערך בגודל המדויק
string[] res = new string[count];
// מעבר שני: העתקת המיקומים
int k = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetQuantity() > arr[i].GetCapacity() / 2)
{
res[k] = arr[i].GetLocation();
k++;
}
}
return res;
}דוגמה: פחים (A: קיבולת 100, כמות 50), (B: קיבולת 100, כמות 51) - רק B מכיל יותר מחצי, ויוחזר המערך {"B"}.
תשובה: הפעולה `binsToEmpty` שלמעלה.
שאלה 3 · בדיקה אם מחרוזת היא שרשור של מחרוזת אחרת
מחרוזת s1 נקראת "שכפול K" של מחרוזת s2 אם אפשר לקבל את המחרוזת s1 על ידי שרשור של k מחרוזות s2 (k- מספר שלם וחיובי).
לדוגמה: המחרוזת s1="ABCDABCDABCD" היא "שכפול 3" של המחרוזת s2="ABCD"
כתבו פעולה המקבלת שתי מחרוזות s1 ו- s2 ובודקת אם s1 היא "שכפול K" של s2.
כותרת הפעולה
static boolean isCopyK(String s1, String s2)static bool IsCopyK(string s1, string s2)◂ פתרון מלא לשאלה 3
פתרון
אורך s1 חייב להיות כפולה חיובית של אורך s2, וכל תו s1[i] חייב להיות שווה ל-s2[i % len2]; אחרת false.
הרעיון: אם s1 בנויה מ-k עותקים של s2 זה אחר זה, אז:
1. האורך של s1 הוא , כלומר `len1 % len2 == 0` ו-`len1 > 0` (כי k חיובי).
2. התו במקום i ב-s1 נמצא בעותק מספר , במקום בתוך העותק. לכן צריך להתקיים `s1[i] == s2[i % len2]` לכל i.
שני התנאים יחד גם מספיקים: אם האורך מתחלק ו-s1 תואמת תו-תו את s2 במחזוריות, אז s1 היא בדיוק שרשור של עותקים של s2.
אם s2 ריקה אי אפשר לבנות ממנה מחרוזת לא ריקה, ולכן גם אז מחזירים false (וכך נמנע חילוק באפס).
הסיבוכיות: מעבר אחד על s1, כלומר .
static boolean isCopyK(String s1, String s2)
{
int len1 = s1.length();
int len2 = s2.length();
// אורך s1 חייב להיות כפולה שלמה וחיובית של אורך s2
if (len1 == 0 || len2 == 0 || len1 % len2 != 0)
return false;
// כל תו ב-s1 חייב להיות שווה לתו המתאים ב-s2
for (int i = 0; i < len1; i++)
{
if (s1.charAt(i) != s2.charAt(i % len2))
return false;
}
return true;
}static bool IsCopyK(string s1, string s2)
{
int len1 = s1.Length;
int len2 = s2.Length;
// אורך s1 חייב להיות כפולה שלמה וחיובית של אורך s2
if (len1 == 0 || len2 == 0 || len1 % len2 != 0)
return false;
// כל תו ב-s1 חייב להיות שווה לתו המתאים ב-s2
for (int i = 0; i < len1; i++)
{
if (s1[i] != s2[i % len2])
return false;
}
return true;
}בדיקה עם הדוגמה: s1="ABCDABCDABCD" (אורך 12), s2="ABCD" (אורך 4): , וכל תו מתאים, למשל s1[5]='B' ו-s2[5 % 4]=s2[1]='B'. הפעולה מחזירה true (k=3). עבור s1="ABCDABCDABC" (אורך 11) יוחזר false כי .
תשובה: הפעולה `isCopyK` שלמעלה.
שאלה 4 · מערך עולה-יורד ומציאת אינדקס הפסגה
מערך של מספרים שלמים ייקרא "מערך עולה-יורד" אם מתחילת המערך ועד למקום (אינדקס) מסוים איברי המערך הם סדרה עולה, וממקום זה ועד לסוף המערך איברי המערך הם סידרה יורדת. המיקום הזה נקרא "פסגה".
לדוגמה:
המערך {1,3,6,11,10,9,4,2,0} הוא מערך "עולה-יורד", אינדקס "פסגה" הוא 3.
כתבו פעולה המקבלת מערך מספרים שלמים ובודקת אם הוא מערך "עולה-יורד".
אם כן – הפעולה תחזיר אינדקס של "פסגה", אם לא – הפעולה תחזיר -1.
מהי סיבוכיות הפעולה מסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 4
סעיף א
עולים כל עוד arr[i] < arr[i+1] (הפסגה היא המקום שבו העלייה נעצרת), ואז יורדים כל עוד arr[i] > arr[i+1]; אם הגענו לסוף המערך והפסגה אינה בקצה - מחזירים אותה, אחרת -1.
הרעיון: עוברים על המערך פעם אחת, משמאל לימין, בשני שלבים:
1. שלב העלייה: מתקדמים עם i כל עוד האיבר הבא גדול מהנוכחי (`arr[i] < arr[i+1]`). כשהלולאה נעצרת, i הוא המקום האחרון של העלייה - זו ה"פסגה". שומרים אותו ב-`peak`.
2. בדיקת הפסגה: אם `peak == 0` לא הייתה עלייה כלל, ואם `peak == n-1` לא נשארה ירידה. במערך "עולה-יורד" יש גם קטע עולה וגם קטע יורד, ולכן בשני המקרים מחזירים -1.
3. שלב הירידה: ממשיכים מאותו i כל עוד האיבר הבא קטן מהנוכחי (`arr[i] > arr[i+1]`).
4. בדיקה סופית: אם שלב הירידה הגיע עד האיבר האחרון (`i == n-1`), כל המערך עולה ואז יורד, ומחזירים `peak`. אם הוא נעצר באמצע - יש שם עלייה חוזרת או שני איברים שווים, ומחזירים -1.
הסדרות עולה ויורדת ממש (שני איברים סמוכים שווים אינם עלייה ואינם ירידה), כמו בדוגמה.
public static int peakIndex(int[] arr)
{
int n = arr.length;
int i = 0;
// שלב 1: עולים כל עוד האיבר הבא גדול מהנוכחי
while (i < n - 1 && arr[i] < arr[i + 1])
i++;
int peak = i;
// הפסגה חייבת להיות אחרי עלייה ולפני ירידה
if (peak == 0 || peak == n - 1)
return -1;
// שלב 2: יורדים כל עוד האיבר הבא קטן מהנוכחי
while (i < n - 1 && arr[i] > arr[i + 1])
i++;
// אם הגענו לסוף המערך - הוא "עולה-יורד"
if (i == n - 1)
return peak;
return -1;
}public static int PeakIndex(int[] arr)
{
int n = arr.Length;
int i = 0;
// שלב 1: עולים כל עוד האיבר הבא גדול מהנוכחי
while (i < n - 1 && arr[i] < arr[i + 1])
i++;
int peak = i;
// הפסגה חייבת להיות אחרי עלייה ולפני ירידה
if (peak == 0 || peak == n - 1)
return -1;
// שלב 2: יורדים כל עוד האיבר הבא קטן מהנוכחי
while (i < n - 1 && arr[i] > arr[i + 1])
i++;
// אם הגענו לסוף המערך - הוא "עולה-יורד"
if (i == n - 1)
return peak;
return -1;
}מעקב על הדוגמה {1,3,6,11,10,9,4,2,0}: שלב העלייה עובר את 1<3<6<11 ונעצר ב-i=3 (כי 11>10), לכן peak=3 (לא 0 ולא 8). שלב הירידה עובר 11>10>9>4>2>0 ומגיע ל-i=8=n-1, ולכן מוחזר 3.
עבור {1,3,2,4}: peak=1, הירידה נעצרת ב-i=2 (כי 2<4), ולכן מוחזר -1.
תשובה: הפעולה `peakIndex` שלמעלה; עבור הדוגמה היא מחזירה 3.
סעיף ב
O(n) - האינדקס i רק מתקדם, וכל איבר נבדק לכל היותר פעם אחת בשני השלבים יחד.
n הוא מספר האיברים במערך. בשתי הלולאות משתמשים באותו אינדקס i, שמתחיל ב-0 ורק גדל, ואינו עובר את . לכן מספר הסיבובים בשתי הלולאות יחד הוא לכל היותר , ובכל סיבוב מתבצעת השוואה אחת ופעולה אחת - זמן קבוע. שאר הפעולות (בדיקת הפסגה והבדיקה הסופית) מתבצעות פעם אחת.
תשובה: סיבוכיות זמן ריצה לינארית, .
שאלה 5 · מעקב: סכום מקסימלי של רצף איברים
נתונה הפעולה what המקבלת מערך מספרים שלמים
public static int what(int [] arr)
{
int m =arr[0]; int s=0;
for( int i=0; i<arr.length; i++)
{
s=s+arr[i];
if(s>m)
m=s;
if(s<0)
s=0;
}
return m;
}public static int What(int [] arr)
{
int m =arr[0]; int s = 0;
for( int i=0; i<arr.Length; i++)
{
s=s + arr[i];
if(s > m)
m = s;
if(s < 0)
s = 0;
}
return m;
}עקבו בעזרת טבלת המעקב אחרי ביצוע הפעולה עבור המערך `int[] arr={-2,-3, 4, -1,-2, 1, 5, -3}`
ורשמו מה תחזיר הפעולה.
מה מבצעת הפעולה what באופן כללי?
ידוע שמערך brr מכיל מספרים אי-שליליים (חיוביים ואפסים) בלבד. מה תחזיר זימון הפעולה what(brr)?
◂ פתרון מלא לשאלה 5
סעיף א
7
בהתחלה ו-. בכל סיבוב: מוסיפים את arr[i] ל-s; אם s גדול מ-m מעדכנים את m; ואם s שלילי מאפסים אותו.
אחרי הלולאה מסתיימת ( אינו קטן מ-8), והפעולה מחזירה את m.
הערך 7 הוא סכום הרצף 4, -1, -2, 1, 5 (מקומות 2 עד 6): .
תשובה: הפעולה תחזיר 7.
סעיף ב
מחזירה את הסכום הגדול ביותר של רצף (תת-מערך) של איברים סמוכים במערך.
המשתנה s הוא הסכום של הרצף הנוכחי - רצף של איברים סמוכים שמסתיים במקום i. ברגע שסכום הרצף נעשה שלילי, אין טעם להמשיך אותו (רצף שיתחיל מחדש יהיה גדול יותר), ולכן מאפסים את s ומתחילים רצף חדש מהאיבר הבא.
המשתנה m שומר את הסכום הגדול ביותר שהתקבל עד כה. הוא מאותחל ל-arr[0] (רצף של איבר אחד), ולכן גם במערך שכל איבריו שליליים הפעולה מחזירה את האיבר הגדול ביותר - רצף של איבר בודד.
תשובה: הפעולה מחזירה את הסכום המקסימלי של רצף איברים סמוכים (תת-מערך רציף) במערך.
סעיף ג
את סכום כל איברי המערך brr.
כשכל האיברים אי-שליליים, הסכום s לעולם אינו יורד מתחת ל-0, ולכן הוא אף פעם אינו מתאפס, ובסוף הסיבוב ה-i הוא שווה ל-.
סכומים אלה רק גדלים (או נשארים), ולכן m מתעדכן לכל סכום חלקי שגדול ממנו, ובסוף הוא שווה לסכום של כל המערך. (אם כל האיברים 0 - , וזה גם הסכום.)
לדוגמה, עבור {3,0,5,1} יוחזר .
תשובה: what(brr) תחזיר את סכום כל איברי המערך.
שאלה 6 · מחלקת מקצוע לימוד וחישוב נקודות זכות
במכללה "מסודרת וממוחשבת" מלמדים מגוון מקצועות לימוד. כדי להיות זכאי לתעודת גמר על הסטודנט לצבור נקודות זכות. סטודנט מקבל נקודות זכות עבור מקצוע מסוים אם הוא הגיש לפחות חצי מהמטלות הנדרשות וקיבל ציון עובר בבחינה. לכל מקצוע יש מספר שונה של מטלות שסטודנט נדרש להגיש, ציון עובר ומספר נקודות זכות שמקנה סיום הקורס בהצלחה.
לדוגמה:
•במקצוע "אלגוריתמיקה א'" במשך הקורס יש להגיש שמונה מטלות, ציון "עובר" בבחינה הוא 70, הצלחה בקורס מקנה שלוש נקודות זכות.
•במקצוע "תכנות מונחה עצמים" במשך הקורס יש להגיש ארבע מטלות, ציון "עובר" בבחינה הוא 60, הצלחה בקורס מקנה ארבע נקודות זכות.
הגדירו את המחלקה Subject המייצגת מקצוע לימוד. יש להגדיר את תכונות המחלקה ולכתוב פעולה בונה המקבלת פרמטרים לכל תכונה.
כתבו פעולה המקבלת את מספר המטלות שהגיש סטודנט ואת הציון שקיבל בבחינה. אם סטודנט סיים קורס בהצלחה, הפעולה תחזיר מספר נקודות זכות, ואם לא הפעולה תחזיר 0.
כותרת הפעולה:
public int getPoints(int numOfWorks, int grade)public int GetPoints(int numOfWorks, int grade)כתבו פעולה חיצונית המקבלת את מערך המקצועות (מערך עצמים מסוג Subject) שהסטודנט למד. על הפעולה לקלוט עבור כל מקצוע את מספר המטלות שהגיש הסטודנט ואת הציון שקיבל בבחינה. הפעולה תדפיס את סה"כ נקודות הזכות שקיבל הסטודנט.
כותרת הפעולה:
public static void result(Subject[] arr)public static void Result(Subject[] arr)◂ פתרון מלא לשאלה 6
סעיף א
מחלקה Subject עם התכונות name, numOfWorks, passGrade, points ובנאי שמקבל ערך לכל אחת מהן.
מהתיאור עולה שלכל מקצוע ארבעה נתונים:
1. שם המקצוע - מחרוזת `name`.
2. מספר המטלות שיש להגיש - שלם `numOfWorks` (למשל 8).
3. הציון העובר בבחינה - שלם `passGrade` (למשל 70).
4. מספר נקודות הזכות שמקנה הקורס - שלם `points` (למשל 3).
התכונות פרטיות (private), והפעולה הבונה מקבלת פרמטר לכל תכונה ומציבה אותו בתכונה בעזרת `this`.
public class Subject
{
private String name; // שם המקצוע
private int numOfWorks; // מספר המטלות שיש להגיש
private int passGrade; // ציון עובר בבחינה
private int points; // נקודות הזכות שמקנה הקורס
public Subject(String name, int numOfWorks, int passGrade, int points)
{
this.name = name;
this.numOfWorks = numOfWorks;
this.passGrade = passGrade;
this.points = points;
}
}public class Subject
{
private string name; // שם המקצוע
private int numOfWorks; // מספר המטלות שיש להגיש
private int passGrade; // ציון עובר בבחינה
private int points; // נקודות הזכות שמקנה הקורס
public Subject(string name, int numOfWorks, int passGrade, int points)
{
this.name = name;
this.numOfWorks = numOfWorks;
this.passGrade = passGrade;
this.points = points;
}
}לדוגמה, המקצוע הראשון בשאלה נוצר כך: `new Subject("Algorithmics A", 8, 70, 3)`.
תשובה: המחלקה Subject שלמעלה.
סעיף ב
פעולה במחלקה Subject: אם 2*numOfWorks >= this.numOfWorks וגם grade >= passGrade מחזירים points, אחרת 0.
זו פעולה של המחלקה Subject (לא סטטית), ולכן היא ניגשת ישירות לתכונות של המקצוע.
סטודנט סיים בהצלחה אם שני התנאים מתקיימים יחד:
1. הגיש לפחות חצי מהמטלות: . כדי להימנע מחילוק שלמים (שבו ) כותבים את התנאי השקול .
2. קיבל ציון עובר: .
לפרמטר יש אותו שם כמו לתכונה (`numOfWorks`), ולכן לתכונה פונים דרך `this.numOfWorks`.
public int getPoints(int numOfWorks, int grade)
{
// לפחות חצי מהמטלות: 2*numOfWorks >= this.numOfWorks (בלי חילוק שלמים)
if (2 * numOfWorks >= this.numOfWorks && grade >= passGrade)
return points;
return 0;
}public int GetPoints(int numOfWorks, int grade)
{
// לפחות חצי מהמטלות: 2*numOfWorks >= this.numOfWorks (בלי חילוק שלמים)
if (2 * numOfWorks >= this.numOfWorks && grade >= passGrade)
return points;
return 0;
}דוגמה: במקצוע "אלגוריתמיקה א'" (8 מטלות, עובר 70, 3 נקודות): סטודנט שהגיש 4 מטלות וקיבל 70 - ו-, ויוחזר 3. סטודנט שהגיש 3 מטלות - , ויוחזר 0.
תשובה: הפעולה `getPoints` שלמעלה (נכתבת בתוך המחלקה Subject).
סעיף ג
לולאה על המקצועות: קולטים מספר מטלות וציון, צוברים את arr[i].getPoints(works, grade), ובסוף מדפיסים את הסכום.
1. מאתחלים צובר `total = 0`.
2. עוברים על כל המקצועות במערך. עבור כל מקצוע קולטים שני מספרים: כמה מטלות הגיש הסטודנט ואיזה ציון קיבל.
3. את ההחלטה אם הקורס הושלם ובכמה נקודות - כבר כתבנו בסעיף ב'. לכן מזמנים את `arr[i].getPoints(works, grade)` ומוסיפים את התוצאה (מספר הנקודות או 0) לצובר.
4. אחרי הלולאה מדפיסים את הצובר.
public static void result(Subject[] arr)
{
Scanner in = new Scanner(System.in);
int total = 0;
for (int i = 0; i < arr.length; i++)
{
int works = in.nextInt(); // מספר המטלות שהגיש
int grade = in.nextInt(); // הציון בבחינה
total += arr[i].getPoints(works, grade);
}
System.out.println("Total points: " + total);
}public static void Result(Subject[] arr)
{
int total = 0;
for (int i = 0; i < arr.Length; i++)
{
int works = int.Parse(Console.ReadLine()); // מספר המטלות שהגיש
int grade = int.Parse(Console.ReadLine()); // הציון בבחינה
total += arr[i].GetPoints(works, grade);
}
Console.WriteLine("Total points: " + total);
}דוגמה: עבור שני המקצועות מהשאלה, אם הסטודנט הגיש 8 מטלות וקיבל 75 באלגוריתמיקה, והגיש 2 מטלות וקיבל 60 בתכנות מונחה עצמים: , ויודפס 7. (ב-2 מתוך 4 מטלות - בדיוק חצי - התנאי "לפחות חצי" מתקיים.)
תשובה: הפעולה `result` שלמעלה.
שאלה 7 · מעקב: הדפסת תת-מחרוזות בין אותיות גדולות
נתונה הפעולה why הבאה המקבלת מחרוזת:
public static void why(String str)
{
int i = 0;
int j = str.length()-1;
while(i <= j)
{
if(str.charAt(i) < 'A' || str.charAt(i) > 'Z')
i++;
else if(str.charAt(j)< 'A' || str.charAt(j) > 'Z')
j--;
else
{
String temp = str.substring(i,j+1);
System.out.println(temp);
i++; // (*)
j--; // (**)
}
}
}public static void Why(string str)
{
int i=0;
int j=str.Length-1;
while(i<=j)
{
if(str[i] < 'A' || str[i] > 'Z')
i++;
else if(str[j]< 'A' || str[j] > 'Z')
j--;
else
{
string temp = str.Substring(i,j+1);
Console.WriteLine(temp);
i++; // (*)
j--; // (**)
}
}
}עקבו בעזרת טבלת מעקב אחרי זימון הפעולה why(str) עבור המחרוזת str="aBbCdDeFggHi3"
ורשמו מה יהיה הפלט של הפעולה.
הפקודה `i++;` המסומנת ב- (*) נמחקה. מה יהיה הפלט עבור זימון why(str) אחרי שינוי הפעולה?
אחרי השינוי שהתבצע בסעיף ב', נמחקה גם הפקודה `j--;` המסומנת ב-(). הסבירו מה תהיה התוצאה של שינוי זה.
◂ פתרון מלא לשאלה 7
סעיף א
Java: BbCdDeFggH, CdDeF, D (כל אחת בשורה נפרדת). C# (שבו Substring(i, j+1) פירושו j+1 תווים החל מ-i): BbCdDeFggHi, CdDeFggH, DeFggH.
הפעולה מקדמת את i משמאל עד שהיא מוצאת אות גדולה (בין 'A' ל-'Z'), ומורידה את j מימין עד שהיא מוצאת אות גדולה. כששני הקצוות הם אותיות גדולות, היא מדפיסה את תת-המחרוזת מ-i עד j כולל (`substring(i, j+1)` ב-Java), ומצמצמת את שני הקצוות פנימה.
המקומות במחרוזת (אורך 13, ולכן בהתחלה ):
אחרי הסיבוב ה-11: , , התנאי נכשל והלולאה מסתיימת.
שימו לב - גרסת C#: ב-C# הפרמטר השני של `Substring` הוא אורך ולא מקום סיום: `str.Substring(i, j+1)` מחזירה תווים החל מהמקום i. המעקב על i ו-j זהה לגמרי, אבל ההדפסות שונות:
•, : 11 תווים מהמקום 1 (מקומות 1-11) - BbCdDeFggHi
•, : 8 תווים מהמקום 3 (מקומות 3-10) - CdDeFggH
•, : 6 תווים מהמקום 5 (מקומות 5-10) - DeFggH
(בכל ההדפסות , ולכן אין חריגה מגבולות המחרוזת.)
תשובה: בגרסת Java הפלט הוא שלוש שורות:
BbCdDeFggH
CdDeF
D
בגרסת C# הפלט הוא: BbCdDeFggHi, CdDeFggH, DeFggH (כל אחת בשורה נפרדת).
סעיף ב
Java: BbCdDeFggH, BbCdDeF, BbCdD, BbC, B (כל אחת בשורה נפרדת). C#: BbCdDeFggHi, BbCdDeFg, BbCdDe, BbCd, Bb.
עכשיו אחרי הדפסה רק j יורד, ו-i נשאר על האות הגדולה הראשונה 'B' (מקום 1) עד סוף הפעולה. לכן כל ההדפסות מתחילות ב-B, ו-j עובר מימין לשמאל על כל האותיות הגדולות: H (10), F (7), D (5), C (3) ולבסוף B (1).
אחרי הסיבוב ה-13: והלולאה מסתיימת.
גרסת C#: ההדפסות הן `str.Substring(1, j+1)` עבור , כלומר 11, 8, 6, 4, 2 תווים החל מהמקום 1: BbCdDeFggHi, BbCdDeFg, BbCdDe, BbCd, Bb.
תשובה: בגרסת Java הפלט הוא חמש שורות:
BbCdDeFggH
BbCdDeF
BbCdD
BbC
B
בגרסת C# הפלט הוא: BbCdDeFggHi, BbCdDeFg, BbCdDe, BbCd, Bb (כל אחת בשורה נפרדת).
סעיף ג
לולאה אינסופית: אחרי ההדפסה הראשונה i ו-j לא משתנים, והמחרוזת BbCdDeFggH (ב-C#: BbCdDeFggHi) מודפסת שוב ושוב בלי סוף.
כמו קודם, i מגיע ל-1 (האות B) ו-j מגיע ל-10 (האות H), ושניהם מצביעים על אותיות גדולות, ולכן מתבצע ענף ה-else: מודפסת BbCdDeFggH.
אבל עכשיו בענף ה-else אין שום שינוי של i או של j. בסיבוב הבא המצב זהה בדיוק: , שני התווים אותיות גדולות, ושוב מודפסת אותה מחרוזת - וכך הלאה. התנאי לא ייעשה לעולם שקרי.
תשובה: הפעולה תיכנס ללולאה אינסופית ותדפיס את BbCdDeFggH (בגרסת C#: BbCdDeFggHi) שוב ושוב ללא הפסקה.
שאלה 8 · מחלקת מתנה ומציאת שלוש מתנות לגברים
החנות "Gift4U" מוכרת מתנות באמצעות האינטרנט. לשם כך הוגדרה המחלקה Gift המייצגת מתנה.
למחלקה שלוש תכונות:
•code - קוד מתנה מטיפוס מספר שלם, int.
•price - מחיר מתנה מטיפוס מספר ממשי, double.
•type - למי מיועדת המתנה מטיפוס תו, char.
התכונה מקבלת אחת מארבע אפשרויות:
'M' – לגברים, 'F' – לנשים, 'U' – גם לגברים וגם לנשים, 'K' – לילדים.
במחלקה הוגדרו פעולה בונה ופעולות get לכל תכונה.
כתבו פעולה
void setType(char type)void SetType(char type)הפעולה מעדכנת את התכונה type בהתאם לפרמטר.
אם הפרמטר שהפעולה מקבלת אינו תקין, העדכון לא מתבצע.
כתבו פעולה
boolean isForMan()bool IsForMan()הפעולה מחזירה true, אם המתנה מתאימה לגברים אחרת הפעולה תחזיר false.
כתבו פעולה חיצונית המקבלת מערך מתנות (עצמים מטיפוס Gift), arr, וסכום כסף sum.
הפעולה תבדוק אם יש שלוש מתנות שונות המתאימות לגברים שהסכום שלהן שווה ל- sum.
אם כן – הפעולה תדפיס את הקודים של שלוש המתנות, אם לא – הפעולה תדפיס הודעה מתאימה.
הערה: אם קיימות כמה אפשרויות לבחירת שלוש מתנות, יש להדפיס את כולן.
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
אם type הוא 'M', 'F', 'U' או 'K' מציבים this.type = type; אחרת לא עושים דבר.
פרמטר תקין הוא אחד מארבעת התווים 'M', 'F', 'U', 'K'. לכן בודקים אם הפרמטר שווה לאחד מהם, ורק אז מעדכנים את התכונה. לפרמטר אותו שם כמו לתכונה, ולכן לתכונה פונים דרך `this.type`. הפעולה נכתבת בתוך המחלקה Gift:
public void setType(char type)
{
if (type == 'M' || type == 'F' || type == 'U' || type == 'K')
this.type = type;
}public void SetType(char type)
{
if (type == 'M' || type == 'F' || type == 'U' || type == 'K')
this.type = type;
}תשובה: הפעולה `setType` שלמעלה: מעדכנת את type רק אם הפרמטר הוא 'M', 'F', 'U' או 'K'.
סעיף ב
מחזירה type == 'M' || type == 'U'.
מתנה מתאימה לגברים אם היא מיועדת לגברים ('M') או מיועדת גם לגברים וגם לנשים ('U'). לכן הפעולה מחזירה את הערך הבוליאני של התנאי `type == 'M' || type == 'U'`.
גם פעולה זו נכתבת בתוך המחלקה Gift:
public boolean isForMan()
{
return type == 'M' || type == 'U';
}public bool IsForMan()
{
return type == 'M' || type == 'U';
}תשובה: הפעולה `isForMan` שלמעלה.
סעיף ג
שלוש לולאות מקוננות i<j<k על מתנות שמתאימות לגברים (isForMan); אם סכום המחירים שווה ל-sum מדפיסים את שלושת הקודים ומסמנים שנמצא; אם לא נמצאה אף שלישייה - מודיעים על כך.
נתון: מערך מתנות arr וסכום sum.
מבוקש: להדפיס את כל השלישיות של מתנות שונות, המתאימות לגברים, שסכום מחיריהן הוא sum.
1. כדי לעבור על כל השלישיות של מתנות שונות, ובלי לקבל אותה שלישייה כמה פעמים בסדר אחר, משתמשים בשלוש לולאות מקוננות עם אינדקסים : j מתחיל ב- ו-k מתחיל ב-.
2. בכל רמה בודקים שהמתנה מתאימה לגברים בעזרת `isForMan()` מסעיף ב'. בודקים את i ואת j עוד לפני הלולאה הפנימית, וכך חוסכים מעברים מיותרים.
3. מחשבים את סכום שלושת המחירים. המחירים ממשיים (double), ולכן לא משווים בעזרת `==` אלא בודקים שההפרש מ-sum קטן מאוד (0.001), כדי שטעויות עיגול לא יפספסו שלישייה מתאימה.
4. כל שלישייה מתאימה מודפסת (כל השלישיות, לפי ההערה), ומשתנה בוליאני `found` מסמן שנמצאה לפחות אחת.
5. בסוף, אם `found` נשאר false, מדפיסים הודעה שאין שלוש מתנות מתאימות.
public static void threeGifts(Gift[] arr, double sum)
{
boolean found = false;
for (int i = 0; i < arr.length - 2; i++)
{
if (arr[i].isForMan())
{
for (int j = i + 1; j < arr.length - 1; j++)
{
if (arr[j].isForMan())
{
for (int k = j + 1; k < arr.length; k++)
{
double total = arr[i].getPrice() + arr[j].getPrice() + arr[k].getPrice();
// השוואת מספרים ממשיים עם סבולת קטנה
if (arr[k].isForMan() && Math.abs(total - sum) < 0.001)
{
System.out.println(arr[i].getCode() + " " + arr[j].getCode() + " " + arr[k].getCode());
found = true;
}
}
}
}
}
}
if (!found)
System.out.println("There are no three suitable gifts");
}public static void ThreeGifts(Gift[] arr, double sum)
{
bool found = false;
for (int i = 0; i < arr.Length - 2; i++)
{
if (arr[i].IsForMan())
{
for (int j = i + 1; j < arr.Length - 1; j++)
{
if (arr[j].IsForMan())
{
for (int k = j + 1; k < arr.Length; k++)
{
double total = arr[i].GetPrice() + arr[j].GetPrice() + arr[k].GetPrice();
// השוואת מספרים ממשיים עם סבולת קטנה
if (arr[k].IsForMan() && Math.Abs(total - sum) < 0.001)
{
Console.WriteLine(arr[i].GetCode() + " " + arr[j].GetCode() + " " + arr[k].GetCode());
found = true;
}
}
}
}
}
}
if (!found)
Console.WriteLine("There are no three suitable gifts");
}דוגמה: מתנות (קוד, מחיר, סוג): (1, 10.5, 'M'), (2, 20.25, 'F'), (3, 20.25, 'U'), (4, 9.25, 'M'), (6, 10.5, 'U'), ו-sum=40. מתנה 2 אינה מתאימה לגברים. השלישיות המתאימות: (קודים 1, 3, 4) ו- (קודים 3, 4, 6). שתיהן יודפסו.
תשובה: הפעולה `threeGifts` שלמעלה.
סעיף ד
O(n³) - שלוש לולאות מקוננות על המערך (n = מספר המתנות).
n הוא מספר המתנות במערך. במקרה הגרוע (כל המתנות מתאימות לגברים) הלולאות המקוננות עוברות על כל השלישיות , ומספרן
,
ובכל שלישייה מתבצעת עבודה קבועה (סכום, השוואה, אולי הדפסה). מספר זה הוא מסדר גודל של .
תשובה: סיבוכיות זמן הריצה היא .
שאלה 9 · מספר מתחלף: ספרות סמוכות בזוגיות שונה
הגדרה: מספר מתחלף הוא מספר שלם וחיובי שבו כל זוג ספרות סמוכות (צמודות) הוא בעל זוגיות שונה. כלומר, סמוך לכל ספרה זוגית יש ספרה אי זוגית. מספר חד ספרתי הוא מספר מתחלף.
•המספר 163458 הוא מספר מתחלף כי כל זוג ספרות סמוכות בו הוא בעל זוגיות שונה.
•המספר 1634589 הוא מספר מתחלף כי כל זוג ספרות סמוכות בו הוא בעל זוגיות שונה.
•המספר 163789 הוא לא מספר מתחלף כי הספרות 3 ו- 7 סמוכות ושתיהן אי-זוגיות.
•המספר 6 וגם המספר 12 הם מספרים מתחלפים.
כתבו פעולה
public static boolean exchange (int number)public static bool Exchange (int number)הפעולה מקבלת מספר שלם חיובי number ומחזירה את הערך true אם הוא מספר מתחלף, ולא – הפעולה תחזיר את הערך false.
כתבו פעולה המקבלת מערך מספרים שלמים וחיוביים ומחזירה מיקום (אינדקס) של מספר מתחלף שסכום ספרותיו הוא הקטן ביותר. אם במערך אין אף מספר מתחלף הפעולה תחזיר ערך -1.
◂ פתרון מלא לשאלה 9
סעיף א
מפרקים את המספר לספרות מהסוף להתחלה; אם שתי ספרות סמוכות שוות בזוגיות (d%2 == prev%2) מחזירים false; אם עברנו על כל הספרות - true.
הרעיון: עוברים על הספרות מימין לשמאל: `number % 10` היא ספרת האחדות, ו-`number /= 10` מוחק אותה. בכל שלב משווים את הספרה הנוכחית לספרה הקודמת (זו שמימינה), ששמורה ב-`prev`.
1. שומרים ב-`prev` את ספרת האחדות ומוחקים אותה.
2. כל עוד נשארו ספרות: לוקחים את הספרה הבאה `digit`. אם `digit % 2 == prev % 2` - לשתי ספרות סמוכות אותה זוגיות, והמספר אינו מתחלף: מחזירים false מיד.
3. אחרת מעדכנים `prev = digit` וממשיכים.
4. אם הלולאה הסתיימה בלי למצוא זוג "רע" - המספר מתחלף. במספר חד-ספרתי הלולאה לא מתבצעת כלל, ומוחזר true, כנדרש.
public static boolean exchange(int number)
{
int prev = number % 10; // ספרת האחדות
number /= 10;
while (number > 0)
{
int digit = number % 10;
if (digit % 2 == prev % 2) // שתי ספרות סמוכות באותה זוגיות
return false;
prev = digit;
number /= 10;
}
return true;
}public static bool Exchange(int number)
{
int prev = number % 10; // ספרת האחדות
number /= 10;
while (number > 0)
{
int digit = number % 10;
if (digit % 2 == prev % 2) // שתי ספרות סמוכות באותה זוגיות
return false;
prev = digit;
number /= 10;
}
return true;
}מעקב על 163789: prev=9; ספרה 8 (זוגיות שונה מ-9), prev=8; ספרה 7 (שונה מ-8), prev=7; ספרה 3: - מוחזר false. עבור 163458 כל זוג סמוך שונה בזוגיות, ומוחזר true; עבור 12 - true; עבור 6 - true.
תשובה: הפעולה `exchange` שלמעלה.
סעיף ב
פעולת עזר digitSum; עוברים על המערך, ולכל arr[i] שמקיים exchange בוחרים אותו אם הוא הראשון שנמצא או שסכום ספרותיו קטן מזה של המינימום הנוכחי; מחזירים את האינדקס (או -1).
נתון: מערך מספרים שלמים וחיוביים.
מבוקש: האינדקס של המספר המתחלף שסכום ספרותיו מינימלי, או -1 אם אין מספר מתחלף.
1. פעולת עזר `digitSum` מחשבת סכום ספרות: מוסיפה את `number % 10` לצובר ומוחקת את הספרה, עד שהמספר מתאפס.
2. משתנה `index` שומר את מיקום המספר המתחלף הטוב ביותר שנמצא עד כה. מאתחלים אותו ל- ("עוד לא נמצא"); כך, אם אין במערך אף מספר מתחלף, יוחזר בלי טיפול נוסף.
3. עוברים על המערך. איבר שאינו מספר מתחלף (לפי `exchange` מסעיף א') - מדלגים עליו. איבר מתחלף נבחר אם זה הראשון שנמצא (`index == -1`) או שסכום ספרותיו קטן מסכום הספרות של `arr[index]`.
4. מחזירים את `index`. (אם לכמה מספרים אותו סכום ספרות מינימלי, יוחזר הראשון מביניהם.)
public static int digitSum(int number)
{
int sum = 0;
while (number > 0)
{
sum += number % 10;
number /= 10;
}
return sum;
}
public static int minExchange(int[] arr)
{
int index = -1;
for (int i = 0; i < arr.length; i++)
{
if (exchange(arr[i]))
{
if (index == -1 || digitSum(arr[i]) < digitSum(arr[index]))
index = i;
}
}
return index;
}public static int DigitSum(int number)
{
int sum = 0;
while (number > 0)
{
sum += number % 10;
number /= 10;
}
return sum;
}
public static int MinExchange(int[] arr)
{
int index = -1;
for (int i = 0; i < arr.Length; i++)
{
if (Exchange(arr[i]))
{
if (index == -1 || DigitSum(arr[i]) < DigitSum(arr[index]))
index = i;
}
}
return index;
}דוגמה: עבור המערך {163458, 11, 1634589, 12}: 11 אינו מתחלף; סכומי הספרות של המספרים המתחלפים הם , , . המינימום הוא 3, במקום 3, ולכן יוחזר 3. עבור {11, 22, 163789} יוחזר .
תשובה: הפעולה `minExchange` שלמעלה (עם פעולת העזר `digitSum`).
שאלה 10 · מעקב: חלוקת מערך לפי שארית בחלוקה ב-3
נתונות שתי הפעולות הבאות:
public static void what(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void something(int[] arr) {
int a = 0, b = 0, k = arr.length-1;
while (b <= k)
{
if (arr[b] %3==0)
{
what(arr, a, b);
a++;
b++;
}
else if (arr[b] %3==1)
{
b++;
}
else
{
what(arr, b, k);
k--;
}
}
}public static void What(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void Something(int[] arr) {
int a = 0, b = 0, k = arr.Length-1;
while (b <= k)
{
if (arr[b] %3==0)
{
What(arr, a, b);
a++;
b++;
}
else if (arr[b] %3==1)
{
b++;
}
else
{
What(arr, b, k);
k--;
}
}
}נתון מערך a={1,3,2,6,10}. איך ייראה המערך אחרי הזימון what(a, 0, a.length-1)?
עקבו באמצעות טבלת מעקב אחר ביצוע something (arr) עבור המערך:
`int[] arr={1,3,4,2,8,12,7,6};`
רשמו מה יהיו הערכים של המערך arr אחרי הזימון.
הערה: אין צורך להראות מעקב אחרי הזימונים של הפעולה what.
האם קיים מערך arr של שמונה מספרים שלמים חיוביים שונים זה מזה שלא ישתנה אחרי הזימון something (arr)? אם כן – הביאו דוגמה למערך כזה, אם לא – הסבירו למה.
מה מבצעת הפעולה something (arr) עבור מערך כלשהו של מספרים שלמים וחיוביים?
◂ פתרון מלא לשאלה 10
סעיף א
{10,3,2,6,1}
הפעולה what מחליפה בין הערכים שבמקומות a ו-b בעזרת משתנה עזר temp. כאן , ולכן מוחלפים האיבר הראשון (1) והאחרון (10).
תשובה: a={10,3,2,6,1}.
סעיף ב
arr = {3,6,12,1,7,4,8,2}
בהתחלה , , . בכל סיבוב בודקים את `arr[b] % 3`:
•שארית 0: מחליפים את arr[a] ו-arr[b], ומקדמים את a ואת b.
•שארית 1: רק b++.
•שארית 2: מחליפים את arr[b] ו-arr[k], ומקטינים את k (b לא זז, כי לתא b הגיע ערך חדש שעוד לא נבדק).
אחרי הסיבוב ה-8: , והלולאה מסתיימת.
אפשר לראות שבמערך הסופי מופיעים קודם המספרים שמתחלקים ב-3 (3, 6, 12), אחריהם אלה שהשארית שלהם 1 (1, 7, 4), ובסוף אלה שהשארית שלהם 2 (8, 2).
תשובה: arr={3,6,12,1,7,4,8,2}.
סעיף ג
כן, למשל {3,6,9,12,1,4,7,10} - קודם כפולות של 3 ואחריהן מספרים שהשארית שלהם 1 (ולכל היותר מספר אחד עם שארית 2, בסוף).
כן. נבדוק מתי הפעולה לא מזיזה אף איבר:
1. כל עוד מופיעים בתחילת המערך מספרים שמתחלקים ב-3, מתקיים , וההחלפה `what(arr, a, b)` מחליפה תא עם עצמו - אין שינוי.
2. מספר שהשארית שלו 1 רק מקדם את b - אין שינוי. אבל אחרי שהופיע מספר כזה, , ולכן מספר שמתחלק ב-3 שיופיע אחריו כן יוחלף. לכן כל הכפולות של 3 צריכות להופיע לפני כל המספרים עם שארית 1.
3. מספר עם שארית 2 מוחלף עם arr[k]. אם יש שניים כאלה או יותר, ההחלפה מחליפה בין שני ערכים שונים והמערך משתנה. לכן מותר לכל היותר מספר אחד עם שארית 2, והוא חייב להיות האחרון (ואז וההחלפה היא עם עצמו).
דוגמה: arr={3,6,9,12,1,4,7,10}. ארבעת המספרים הראשונים מתחלקים ב-3 ומוחלפים כל אחד עם עצמו (), ואחר כך 1, 4, 7, 10 (שארית 1) רק מקדמים את b. המערך נשאר כפי שהיה.
תשובה: כן, למשל arr={3,6,9,12,1,4,7,10}.
סעיף ד
מסדרת מחדש את המערך (במעבר אחד) כך שבהתחלה כל המספרים שמתחלקים ב-3, אחריהם כל המספרים שהשארית שלהם בחלוקה ב-3 היא 1, ובסוף כל המספרים שהשארית שלהם 2.
הפעולה מחלקת את המערך לשלושה אזורים בעזרת שלושה אינדקסים:
•מקומות עד : מספרים שמתחלקים ב-3 (שארית 0).
•מקומות עד : מספרים ששארית החלוקה שלהם ב-3 היא 1.
•מקומות עד : מספרים שעוד לא נבדקו.
•מקומות עד הסוף: מספרים ששארית החלוקה שלהם ב-3 היא 2.
בכל סיבוב היא בודקת את arr[b] ומעבירה אותו לאזור המתאים: שארית 0 - מחליפה אותו עם האיבר הראשון באזור השארית 1 ומרחיבה את אזור השארית 0; שארית 1 - פשוט מרחיבה את האזור שלו; שארית 2 - מעבירה אותו לסוף ומקטינה את k. האזור שלא נבדק קטן בכל סיבוב, ולכן הלולאה מסתיימת אחרי n סיבובים בדיוק (). סדר המספרים בתוך כל קבוצה עשוי להשתנות (כמו בסעיף ב').
תשובה: הפעולה מסדרת את איברי המערך כך שבתחילתו כל המספרים שמתחלקים ב-3, אחריהם המספרים שהשארית שלהם בחלוקה ב-3 היא 1, ובסופו המספרים שהשארית שלהם 2.
שאלה 11 · חיתוך מערכים ובדיקת מערכים זרים
נתונות ההגדרות הבאות:
•המערך a נקרא "חיתוך" (intersection) של שני המערכים b ו- c אם הוא כולל את כל הערכים הקיימים גם במערך b וגם במערך c. כל ערך מופיע במערך חיתוך פעם אחת בלבד, אין חשיבות לסדר הערכים.
לדוגמה:
המערך a={1,3,5,10} הוא "חיתוך" של המערכים b={3,9,1,10,2,10,5} ו- c={1,3,4,10,5,7, 5,1,100, 7}.
•שני מערכים נקראים "זרים" אם אין להם אף מספר משותף אחד (אין אף מספר שנמצא בשני המערכים)
לדוגמה:
המערכים a={1,2,3,4} ו- b={6,7,8,9,10} הם מערכים "זרים".
כתבו פעולה המקבלת שני מערכים של מספרים שלמים חיוביים דו-ספרתיים ומחזירה את מערך ה"חיתוך" שלהם. כותרת הפעולה:
public static int[] intersect(int[] b, int[] c)int[] Intersect(int[] b, int[] c)כתבו פעולה המקבלת שני מערכים של מספרים שלמים חיוביים דו-ספרתיים ובודקת אם הם "זרים". אם כן – הפעולה תחזיר true, ולא הפעולה תחזיר false. כותרת הפעולה:
public static boolean areStrangers(int[] a, int[] b)bool AreStrangers(int[] a, int[] b)מהן סיבוכיות זמן הריצה של הפעולות שכתבת בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
מערך בוליאני inB[100] מסמן את ערכי b; במעבר על c מסמנים ב-common[100] כל ערך שנמצא גם ב-b (פעם אחת) וסופרים; יוצרים מערך בגודל המונה ומעתיקים אליו את הערכים המסומנים. O(n+m).
הרעיון: הערכים הם מספרים דו-ספרתיים, כלומר קטנים מ-100. לכן אפשר להשתמש במערך עזר שהאינדקס שלו הוא הערך עצמו ("מערך מונים"/סימון), במקום לחפש כל ערך בלולאה.
1. `inB` - מערך בוליאני בגודל 100. עוברים על b ומסמנים `inB[b[i]] = true` לכל ערך של b (ערך שחוזר ב-b מסומן שוב, בלי נזק).
2. `common` - מערך בוליאני בגודל 100 שמסמן ערכים שכבר נכנסו לחיתוך. עוברים על c: ערך `c[i]` שנמצא ב-b (`inB[c[i]]`) ועוד לא סומן ב-`common` - מסמנים אותו וסופרים. הבדיקה של `common` מבטיחה שכל ערך ייספר פעם אחת בלבד, גם אם הוא חוזר ב-c (כמו 1 ו-5 בדוגמה) או ב-b (כמו 10).
3. יוצרים מערך בגודל `count` בדיוק, ומעתיקים אליו את כל הערכים v שמסומנים ב-`common` (מעבר על ). הערכים יוצאים ממוינים, אבל לפי ההגדרה אין חשיבות לסדר.
public static int[] intersect(int[] b, int[] c)
{
boolean[] inB = new boolean[100]; // inB[v] - האם v נמצא ב-b
boolean[] common = new boolean[100]; // common[v] - האם v נמצא בשני המערכים
int count = 0;
for (int i = 0; i < b.length; i++)
inB[b[i]] = true;
for (int i = 0; i < c.length; i++)
{
if (inB[c[i]] && !common[c[i]]) // ערך משותף שעוד לא נספר
{
common[c[i]] = true;
count++;
}
}
int[] a = new int[count];
int k = 0;
for (int v = 0; v < 100; v++)
{
if (common[v])
{
a[k] = v;
k++;
}
}
return a;
}public static int[] Intersect(int[] b, int[] c)
{
bool[] inB = new bool[100]; // inB[v] - האם v נמצא ב-b
bool[] common = new bool[100]; // common[v] - האם v נמצא בשני המערכים
int count = 0;
for (int i = 0; i < b.Length; i++)
inB[b[i]] = true;
for (int i = 0; i < c.Length; i++)
{
if (inB[c[i]] && !common[c[i]]) // ערך משותף שעוד לא נספר
{
common[c[i]] = true;
count++;
}
}
int[] a = new int[count];
int k = 0;
for (int v = 0; v < 100; v++)
{
if (common[v])
{
a[k] = v;
k++;
}
}
return a;
}דוגמה: עבור b={3,9,1,10,2,10,5} מסומנים 1, 2, 3, 5, 9, 10. במעבר על c={1,3,4,10,5,7,5,1,7} נכנסים לחיתוך 1, 3, 10, 5 (ה-5 וה-1 השניים כבר מסומנים ב-common ולא נספרים שוב), ויוחזר {1,3,5,10}. (המספר 100 שבדוגמה של ההגדרה אינו דו-ספרתי ואינו חלק מהקלט של פעולה זו; הוא גם אינו ב-b.)
תשובה: הפעולה `intersect` שלמעלה.
סעיף ב
return intersect(a, b).length == 0; - שני מערכים זרים בדיוק כאשר מערך החיתוך שלהם ריק.
שני מערכים "זרים" אם אין להם אף ערך משותף, כלומר אם החיתוך שלהם ריק. מערך החיתוך מסעיף א' מכיל בדיוק את הערכים המשותפים, ולכן מספיק לבדוק שאורכו 0.
public static boolean areStrangers(int[] a, int[] b)
{
return intersect(a, b).length == 0;
}public static bool AreStrangers(int[] a, int[] b)
{
return Intersect(a, b).Length == 0;
}דוגמה: עבור a={1,2,3,4} ו-b={6,7,8,9,10} מערך החיתוך ריק, ומוחזר true. עבור {11,22} ו-{22} החיתוך הוא {22}, ומוחזר false.
תשובה: הפעולה `areStrangers` שלמעלה.
סעיף ג
שתיהן O(n+m), כאשר n ו-m הם אורכי המערכים (המעבר על 100 התאים של מערכי העזר הוא זמן קבוע).
נסמן ב-n את אורך המערך הראשון וב-m את אורך השני.
1. סעיף א': מעבר אחד על b - ; מעבר אחד על c - ; יצירת מערכי העזר והמעבר על 100 הערכים האפשריים - מספר קבוע של פעולות, שאינו תלוי בגודל הקלט, כלומר . בכל צעד מתבצעת גישה ישירה לתא לפי הערך - זמן קבוע. בסך הכול .
2. סעיף ב': זימון אחד של intersect - , ועוד בדיקת אורך - . בסך הכול .
(לשם השוואה: חיפוש כל איבר של c בלולאה על b היה נותן .)
תשובה: סיבוכיות זמן הריצה של שתי הפעולות היא - לינארית בסכום אורכי המערכים.
שאלה 12 · מעקב: מחיקת מופעים של תת-מחרוזת
נתונות הפעולות what ו- something הבאות:
public static boolean what(String s, String t, int ind)
{
for (int i=0; i<t.length(); i++)
{
if (s.charAt(ind+i) != t.charAt(i))
return false;
}
return true;
}
public static String something (String s, String t)
{
int i=0;
int lenT = t.length();
while (i<s.length()-lenT+1)
{
if (s.charAt(i) == t.charAt(0));
{
if (what(s, t, i))
{
s = s.substring(0,i)+s.substring(i+lenT);
i--;
}
}
i++;
}
return s;
}public static bool What(string s, string t, int ind)
{
for (int i=0; i<t.Length; i++)
{
if (s[ind+i] != t[i])
return false;
}
return true;
}
public static string Something (string s, string t)
{
int i=0;
int lenT = t.Length;
while (i<s.Length-lenT+1)
{
if (s[i] == t[0]);
{
if (What(s, t, i))
{
s = s.Substring(0,i)+s.Substring(i+lenT);
i--;
}
}
i++;
}
return s;
}נתונות שתי מחרוזות s1="ABCANCAD" ו- s2="CAN". מה צריך להיות ערכו של הפרמטר ind כך שהזימון what(s1, s2, ind) יחזיר ערך true?
נתונות שתי מחרוזות s1=" ACANBCCANAD " ו- s2="CAN".
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה something(s1, s2) ורשמו מה תחזיר הפעולה.
נתונה מחרוזת s1="AACANAAAA". מה צריכה להיות המחרוזת s2, כך שתוצאת הזימון something(s1, s2) תהיה המחרוזת "CAN"? הסבירו את תשובתכם.
מה מבצעות הפעולות what ו- something באופן כללי? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 12
סעיף א
ind = 2
הפעולה what משווה את התווים של t, אחד אחרי השני, לתווים של s החל מהמקום ind: התו t[i] מושווה ל-s[ind+i]. היא מחזירה true רק אם כל התווים שווים, כלומר אם t מופיעה ב-s בדיוק החל מהמקום ind.
המחרוזת "CAN" מופיעה ב-s1 במקומות 2, 3, 4: , , . בכל מקום התחלה אחר ההשוואה נכשלת: במקום 5 מתחיל "CAD" (התו השלישי D שונה מ-N), ובמקומות 0, 1, 3, 4 התו הראשון אינו C.
תשובה: ind=2.
סעיף ב
"ABCAD"
שימו לב: אחרי התנאי `if (s.charAt(i) == t.charAt(0))` יש נקודה-פסיק (`;`). לכן גוף ה-if הוא הוראה ריקה, והבלוק שאחריו מתבצע בכל סיבוב, בלי קשר לתנאי. התוצאה אינה משתנה (כי what בודקת ממילא גם את התו הראשון), אבל צריך לזכור זאת במעקב.
בכל סיבוב: אם t מופיעה ב-s במקום i (what מחזירה true), מוחקים אותה מ-s (מחברים את מה שלפניה ואת מה שאחריה) ומבצעים `i--`, כך שאחרי `i++` נבדוק שוב את אותו מקום. אחרת רק `i++`.
, ותנאי הלולאה הוא (לפי האורך הנוכחי של s, שמתקצר אחרי כל מחיקה). המחרוזת מתחילה כ-"ACANBCCANAD" (אורך 11). (בשאלון מודפסים רווחים בתוך המירכאות, כנראה בטעות הקלדה; אם הרווחים הם חלק מהמחרוזת, הם פשוט נשארים במקומם והפעולה מחזירה " ABCAD " - אותה תוצאה עם הרווחים.)
בסיבוב 6 מתקיים שקר, הלולאה מסתיימת, ומוחזרת s.
תשובה: הפעולה תחזיר "ABCAD".
סעיף ג
s2="AA"
צריך למחוק מ-"AACANAAAA" את שני ה-A שבהתחלה ואת ארבעת ה-A שבסוף, ולהשאיר את "CAN" (כולל ה-A שבאמצע שלה).
•s2="A" לא מתאימה: היא הייתה מוחקת גם את ה-A שבתוך CAN (ונשאר "CN").
•s2="AA" מתאימה: בתחילת המחרוזת יש זוג A אחד, ובסופה שני זוגות, ואין זוג AA בתוך "CAN".
מעקב עם s2="AA" ():
עכשיו שקר, והלולאה מסתיימת: מוחזר "CAN".
תשובה: s2="AA".
סעיף ד
what בודקת אם t מופיעה ב-s החל מהמקום ind; something מוחקת מ-s את המופעים של t (סורקת משמאל לימין, ואחרי כל מחיקה בודקת שוב את אותו מקום) ומחזירה את המחרוזת שנשארה.
1. what(s, t, ind) משווה תו-תו את t לתווים של s החל מהמקום ind, ומחזירה true אם כולם שווים - כלומר אם t היא תת-מחרוזת של s שמתחילה במקום ind (אחרת false).
2. something(s, t) עוברת על כל מקומות ההתחלה האפשריים i ב-s, משמאל לימין. בכל מקום שבו t מופיעה (לפי what), היא מוחקת את המופע מ-s ובודקת שוב את אותו מקום, כי אחרי המחיקה הגיעו אליו תווים חדשים (כך נמחקו שני ה-"AA" ברצף בסעיף ג'). בסוף היא מחזירה את המחרוזת שנשארה - s בלי המופעים של t.
(הנקודה-פסיק אחרי ה-if הופכת את בדיקת התו הראשון לחסרת השפעה, אבל לא משנה את התוצאה.)
תשובה: what בודקת אם המחרוזת t מופיעה ב-s החל מהמקום ind; something מוחקת מ-s את כל המופעים של t שהיא פוגשת בסריקה משמאל לימין ומחזירה את המחרוזת שהתקבלה.
שאלה 13 · מחלקות הודעה ותיבת דואר: תשובה, ספירה ושכיחות
עקב המגבלות של מגפת הקורונה, חלק מהבחינות מתבצע בצורה ממוחשבת כאשר הסטודנטים נמצאים בביתם ומבצעים מטלות באמצעות מערכת המבוססת על רשת האינטרנט. אם סטודנט רוצה לשאול שאלה על מטלה ספציפית הוא כותב אי-מייל למרכז תמיכה ומקבל תשובה מצוות המנחים גם היא בדואר האלקטרוני. בכל פנייה למרכז התמיכה יש לציין את מספר המטלה.
כדי ליעל את תהליך ההתכתבות בין סטודנט לצוות המנחים הוקם פרויקט הכולל שלוש מחלקות:
Time, Message, Mailbox
המחלקה Time מייצגת נקודת זמן לפי מספר שעות ומספר דקות.
public class Time
{
public Time(int hour, int minute){…}
public boolean before(Time other) {…}
public Time addFiveMinutes () {…}
…
}public class Time
{
public Time(int hour, int minute){…}
public bool Before(Time t) {…}
public Time AddFiveMinutes () {…}
…
}המחלקה Time כבר נתונה ואפשר להשתמש בפעולות שבה. אין צורך לממש אותן!
המחלקה מכילה:
•בנאי המקבל כפרמטרים שני מספרים המייצגים את השעה (בתחום 0-23), ואת הדקה (בתחום 0-59), ופעולות האחזור: getMinute(), getHour()
•הפעולה בוליאנית before(Time other) המקבלת הפנייה לאובייקט אחר other מסוג Time ומחזירה true אם הזמן המיוצג על-ידי האובייקט שמפעיל את הפעולה (this) קודם לזמן המיוצג באמצעות other. אחרת הפעולה מחזירה false.
•הפעולה addFiveMinutes() המחזירה הפנייה לאובייקט חדש, המייצג זמן חמש דקות אחרי הזמן שמייצג האובייקט המפעיל את הפעולה (this).
נתונה המחלקה Message המייצגת הודעת דואר אלקטרוני.
תכונות המחלקה הן:
•sender - כתובת השולח, מטיפוס String;
•subject - נושא ההודעה שהוא מספר המטלה עליה סטודנט רוצה לשאול שאלה, מטיפוס int;
•content - תוכן ההודעה, מטיפוס String;
•receivingTime - זמן קבלת ההודעה, מטיפוס Time;
•hasAttachment - אם ההודעה מכילה קובץ מצורף, מטיפוס boolean;
המחלקה Message כבר כתובה ואפשר להשתמש בפעולות שבה. אין צורך לממש אותן!
המחלקה מכילה:
•בנאי המקבל שישה פרמטרים שהם פרטי התכונות של האובייקט.
•פעולות האחזור (get methods). לכל תכונה יש פעולת אחזור משלה.
עליכם להוסיף במחלקה Message את הפעולה
public Message reply (String text)public Message Reply (string text)הפעולה המקבלת כפרמטר מחרוזת text המחזירה הודעה לשולח. הפעולה צריכה להחזיר אובייקט שהוא הודעה חדשה עם הפרמטרים המפורטים להלן:
•כתובת השולח החדשה תהיה "support@uni.ac.il"
•נושא ההודעה יהיה מספר שלילי ההפוך לנושא ההודעה הנוכחית
•תוכן ההודעה יישאר כשהיה, ויתווסף לו בסופו רווח, ואז תוכן הפרמטר text.
•זמן יהיה זמן של ההודעה שהתקבלה בתוספת חמש דקות.
•בהודעה החדשה אין קבצים מצורפים.
הייצוג נעשה באמצעות מערך ששומר את ההודעות. התכונות במחלקה הן:
•המערך של ההודעות Message [] inbox.
•מספר ההודעות שיש בתיבת הדואר int noOfMes.
כתבו במחלקה Mailbox את הבנאי (constructor) המקבל כפרמטר מספר שלם וחיובי num ויוצר אובייקט שבו מערך בגודל המקסימלי של num הודעות.
כתבו במחלקה Mailbox את הפעולות הבאות:
הפעולה `int howManyBetweenTimes(Time first, Time second)` המקבלת כפרמטרים שני זמנים, first ו- second ומחזירה את מספר ההודעות שהתקבלו בטווח בין הזמנים first ו- second (לא כולל את הזמנים עצמם).
הפעולה `int mostPopularSubject()` המחזירה את הנושא הפופולרי ביותר, כלומר מספר המטלה שלגביה היו הכי הרבה פניות של סטודנטים.
◂ פתרון מלא לשאלה 13
סעיף א
return new Message("support@uni.ac.il", -subject, content + " " + text, receivingTime.addFiveMinutes(), false);
הפעולה נכתבת בתוך המחלקה Message, ולכן היא ניגשת ישירות לתכונות של ההודעה הנוכחית (this). היא יוצרת הודעה חדשה בעזרת הבנאי ומחזירה אותה; ההודעה המקורית אינה משתנה.
את הערכים לבנאי בונים לפי הדרישות, אחת-אחת:
1. שולח: המחרוזת הקבועה "support@uni.ac.il".
2. נושא: המספר הנגדי לנושא הנוכחי, `-subject` (למשל נושא 3 הופך ל-), כך שאפשר לזהות שזו תשובה למטלה 3.
3. תוכן: `content + " " + text` - התוכן הקודם, רווח, ואחריו הטקסט החדש.
4. זמן: `receivingTime.addFiveMinutes()` - פעולה של Time שמחזירה עצם חדש, חמש דקות אחרי זמן הקבלה.
5. קובץ מצורף: `false`.
בשאלה נכתב שהבנאי מקבל "שישה פרמטרים", אך למחלקה חמש תכונות; לכן הנחנו שהבנאי מקבל פרמטר אחד לכל תכונה, לפי הסדר שבו התכונות מפורטות: (sender, subject, content, receivingTime, hasAttachment).
public class Message
{
private String sender;
private int subject;
private String content;
private Time receivingTime;
private boolean hasAttachment;
// הבנאי ופעולות האחזור כבר קיימים
public Message reply(String text)
{
return new Message("support@uni.ac.il", -subject, content + " " + text,
receivingTime.addFiveMinutes(), false);
}
}public class Message
{
private string sender;
private int subject;
private string content;
private Time receivingTime;
private bool hasAttachment;
// הבנאי ופעולות האחזור כבר קיימים
public Message Reply(string text)
{
return new Message("support@uni.ac.il", -subject, content + " " + text,
receivingTime.AddFiveMinutes(), false);
}
}דוגמה: להודעה עם נושא 3, תוכן "Hello" וזמן 10:20, הזימון `reply("Answer")` יחזיר הודעה מ-"support@uni.ac.il" עם נושא , תוכן "Hello Answer", זמן 10:25 ובלי קובץ מצורף.
תשובה: הפעולה `reply` שלמעלה.
סעיף ב
inbox = new Message[num]; noOfMes = 0;
הבנאי צריך לאתחל את שתי התכונות:
1. `inbox` - מערך חדש של הפניות להודעות בגודל num (זה המספר המקסימלי של הודעות שהתיבה יכולה להכיל).
2. `noOfMes` - בתיבה חדשה עוד אין הודעות, ולכן 0. ההודעות יישמרו בתאים עד של המערך.
הקוד המלא של המחלקה (כולל הבנאי) מופיע בסעיף ג'.
public Mailbox(int num)
{
inbox = new Message[num];
noOfMes = 0;
}public Mailbox(int num)
{
inbox = new Message[num];
noOfMes = 0;
}סעיף ג
סופרים את ההודעות i < noOfMes שמקיימות first.before(t) && t.before(second), כאשר t = inbox[i].getReceivingTime().
עוברים על ההודעות שבתיבה (תאים עד ). לכל הודעה לוקחים את זמן הקבלה שלה `t` בעזרת פעולת האחזור, ובודקים שהוא אחרי first וגם לפני second. את ההשוואה עושים בפעולה `before` של Time:
•`first.before(t)` - first קודם ל-t, כלומר t אחרי first;
•`t.before(second)` - t קודם ל-second.
`before` היא השוואה חזקה (זמן אינו "קודם" לעצמו), ולכן הודעה שהתקבלה בדיוק ב-first או ב-second לא נספרת - כנדרש ("לא כולל את הזמנים עצמם"). הנחנו ש-first מוקדם מ-second.
public int howManyBetweenTimes(Time first, Time second)
{
int count = 0;
for (int i = 0; i < noOfMes; i++)
{
Time t = inbox[i].getReceivingTime();
if (first.before(t) && t.before(second))
count++;
}
return count;
}public int HowManyBetweenTimes(Time first, Time second)
{
int count = 0;
for (int i = 0; i < noOfMes; i++)
{
Time t = inbox[i].GetReceivingTime();
if (first.Before(t) && t.Before(second))
count++;
}
return count;
}(הקוד של כל המחלקה Mailbox מופיע בסעיף 2.)
דוגמה: בתיבה הודעות שהתקבלו ב-9:00, 10:00, 11:00, 12:00. עבור first=9:00 ו-second=12:00 נספרות רק ההודעות של 10:00 ו-11:00, ויוחזר 2.
תשובה: הפעולה `howManyBetweenTimes` שלמעלה.
מערך מונים counters[13]: לכל הודעה עם נושא s בין 1 ל-12 מבצעים counters[s]++; מחזירים את s עם המונה הגדול ביותר.
הרעיון - מערך מונים: יש רק 12 נושאים אפשריים (מטלות 1 עד 12), ולכן מחזיקים מונה לכל נושא, באינדקס ששווה למספר המטלה.
1. יוצרים מערך `counters` בגודל 13 (משתמשים בתאים 1-12; תא 0 לא בשימוש). ב-Java וב-C# מערך חדש מאותחל באפסים.
2. עוברים על ההודעות שבתיבה. לכל הודעה לוקחים את הנושא `s`, ואם מגדילים את `counters[s]`. הבדיקה מסננת הודעות תשובה, שהנושא שלהן שלילי (לפי סעיף א') - הן אינן פניות של סטודנטים.
3. מוצאים את האינדקס של המונה הגדול ביותר: מתחילים מ-`max = 1`, ועוברים על ; אם `counters[s] > counters[max]` מעדכנים. מחזירים את `max` (אם יש שוויון - המטלה בעלת המספר הקטן).
כך עוברים על ההודעות פעם אחת בלבד: , ועוד 12 צעדים קבועים.
המחלקה Mailbox המלאה (סעיפים ב', ג1, ג2):
public class Mailbox
{
private Message[] inbox;
private int noOfMes;
// סעיף ב - הבנאי
public Mailbox(int num)
{
inbox = new Message[num];
noOfMes = 0;
}
// סעיף ג1
public int howManyBetweenTimes(Time first, Time second)
{
int count = 0;
for (int i = 0; i < noOfMes; i++)
{
Time t = inbox[i].getReceivingTime();
if (first.before(t) && t.before(second))
count++;
}
return count;
}
// סעיף ג2
public int mostPopularSubject()
{
int[] counters = new int[13]; // counters[s] - מספר הפניות על מטלה s (1..12)
for (int i = 0; i < noOfMes; i++)
{
int s = inbox[i].getSubject();
if (s >= 1 && s <= 12)
counters[s]++;
}
int max = 1;
for (int s = 2; s <= 12; s++)
{
if (counters[s] > counters[max])
max = s;
}
return max;
}
}public class Mailbox
{
private Message[] inbox;
private int noOfMes;
// סעיף ב - הבנאי
public Mailbox(int num)
{
inbox = new Message[num];
noOfMes = 0;
}
// סעיף ג1
public int HowManyBetweenTimes(Time first, Time second)
{
int count = 0;
for (int i = 0; i < noOfMes; i++)
{
Time t = inbox[i].GetReceivingTime();
if (first.Before(t) && t.Before(second))
count++;
}
return count;
}
// סעיף ג2
public int MostPopularSubject()
{
int[] counters = new int[13]; // counters[s] - מספר הפניות על מטלה s (1..12)
for (int i = 0; i < noOfMes; i++)
{
int s = inbox[i].GetSubject();
if (s >= 1 && s <= 12)
counters[s]++;
}
int max = 1;
for (int s = 2; s <= 12; s++)
{
if (counters[s] > counters[max])
max = s;
}
return max;
}
}דוגמה: אם בתיבה פניות בנושאים 3, 5, 5, 3, 5 ותשובה בנושא , אז , (התשובה אינה נספרת), ויוחזר 5.
תשובה: הפעולה `mostPopularSubject` שבמחלקה שלמעלה.
שאלה 14 · מספרים אחים ורמת הקרבה למערך
•שני מספרים שלמים נקראים "אחים" אם סכום הספרות של האחד שווה לסכום ספרות של האחר.
לדוגמה: המספרים num1=-156 ו-num2=39 הם "אחים".
- "רמת הקרבה" בין מספר שלם num למערך arr היא מספר ה"אחים" שיש ל- num במערך arr.
אם ל- num אין "אחים" במערך arr אז "רמת הקרבה" שלו למערך היא 0.
כתבו פעולה המקבלת שני מערכים של מספרים שלמים arr1 ו- arr2. הפעולה תחזיר את מיקומו (אינדקס) של איבר במערך arr1 ש"רמת הקרבה" שלו למערך arr2 היא הגבוהה ביותר.
הערה: אם יש כמה איברים במערך הראשון ש"רמת הקרבה" שלהם הגבוה ביותר יש להחזיר אינדקס של אחד ביניהם.
מהי סיבוכיות זמן הריצה של הפעולה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 14
סעיף א
פעולת עזר digitSum (על הערך המוחלט), פעולת עזר closeness שסופרת כמה איברים ב-arr2 בעלי אותו סכום ספרות, ומעבר על arr1 לשמירת האינדקס עם רמת הקרבה המקסימלית.
נתון: שני מערכים של מספרים שלמים (גם שליליים - כמו בדוגמה).
מבוקש: אינדקס ב-arr1 של איבר שרמת הקרבה שלו ל-arr2 מקסימלית.
מפרקים את הבעיה לשלוש פעולות:
1. `digitSum(num)` - סכום ספרות. לפי הדוגמה, ל- סכום ספרות , וגם ל-39: - ולכן הם "אחים". כלומר הסימן לא משנה, ולכן מחשבים על `Math.abs(num)`: מוסיפים את `num % 10` לצובר ומוחקים את הספרה, עד ש-num מתאפס.
2. `closeness(num, arr)` - רמת הקרבה. מחשבים פעם אחת את סכום הספרות של num, ואז סופרים כמה איברים ב-arr בעלי אותו סכום ספרות. אם אין כאלה, המונה נשאר 0, כמו בהגדרה.
3. `maxCloseness(arr1, arr2)` - חיפוש מקסימום. מתחילים מהאיבר הראשון (`index = 0`, ורמת הקרבה שלו היא המקסימום ההתחלתי), ועוברים על שאר האיברים. אם רמת הקרבה של `arr1[i]` גדולה ממש מהמקסימום - מעדכנים את המקסימום ואת האינדקס. בשוויון לא מעדכנים, ולכן מוחזר הראשון מבין המקסימליים (ההערה מתירה להחזיר כל אחד מהם).
// סכום הספרות של מספר שלם (גם שלילי)
public static int digitSum(int num)
{
num = Math.abs(num);
int sum = 0;
while (num > 0)
{
sum += num % 10;
num /= 10;
}
return sum;
}
// "רמת הקרבה" של num למערך arr
public static int closeness(int num, int[] arr)
{
int s = digitSum(num);
int count = 0;
for (int i = 0; i < arr.length; i++)
{
if (digitSum(arr[i]) == s)
count++;
}
return count;
}
public static int maxCloseness(int[] arr1, int[] arr2)
{
int index = 0;
int maxLevel = closeness(arr1[0], arr2);
for (int i = 1; i < arr1.length; i++)
{
int level = closeness(arr1[i], arr2);
if (level > maxLevel)
{
maxLevel = level;
index = i;
}
}
return index;
}// סכום הספרות של מספר שלם (גם שלילי)
public static int DigitSum(int num)
{
num = Math.Abs(num);
int sum = 0;
while (num > 0)
{
sum += num % 10;
num /= 10;
}
return sum;
}
// "רמת הקרבה" של num למערך arr
public static int Closeness(int num, int[] arr)
{
int s = DigitSum(num);
int count = 0;
for (int i = 0; i < arr.Length; i++)
{
if (DigitSum(arr[i]) == s)
count++;
}
return count;
}
public static int MaxCloseness(int[] arr1, int[] arr2)
{
int index = 0;
int maxLevel = Closeness(arr1[0], arr2);
for (int i = 1; i < arr1.Length; i++)
{
int level = Closeness(arr1[i], arr2);
if (level > maxLevel)
{
maxLevel = level;
index = i;
}
}
return index;
}דוגמה: arr1={10, -156, 5}, arr2={39, 48, 1, -93, 57}. סכומי הספרות של arr2: 12, 12, 1, 12, 12.
•ל-10 סכום ספרות 1 - רמת קרבה 1 (רק המספר 1).
•ל- סכום ספרות 12 - רמת קרבה 4.
•ל-5 סכום ספרות 5 - רמת קרבה 0.
המקסימום הוא 4, במקום 1, ולכן יוחזר 1.
תשובה: הפעולה `maxCloseness` שלמעלה (עם פעולות העזר `digitSum` ו-`closeness`).
סעיף ב
O(n·m), כאשר n אורך arr1 ו-m אורך arr2 (חישוב סכום ספרות של int הוא לכל היותר 10 צעדים - זמן קבוע).
נסמן ב-n את אורך arr1 וב-m את אורך arr2.
1. `digitSum` מבצעת סיבוב אחד לכל ספרה. למספר מטיפוס int יש לכל היותר 10 ספרות, ולכן זה זמן קבוע .
2. `closeness` עוברת על כל arr2 ומחשבת לכל איבר סכום ספרות: .
3. `maxCloseness` מזמנת את `closeness` פעם אחת לכל אחד מ-n האיברים של arr1: .
תשובה: סיבוכיות זמן הריצה היא .