מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2024 מועד א'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2024 מועד א', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 16)
בכל מבחן 14 שאלות.
שאלות 7-1: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 11-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 14-12: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 11 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מכפלת ספרות וספירת מספרים אי-זוגיים
כתבו קטע תוכנית שיקלוט 30 מספרים חיוביים ושלמים.
•עבור כל מספר תלת ספרתי שנקלט יש להדפיס את מכפלת ספרותיו.
לדוגמה: עבור מספר 123 יש להדפיס 6 (3\*2\*1).
•על הקוד לחשב ולהדפיס כמה מספרים אי זוגיים נקלטו.
◂ פתרון מלא לשאלה 1
פתרון
לולאת for של 30 קליטות; מונים כל מספר שמקיים `num % 2 == 1`; אם מדפיסים את מכפלת הספרות `(num%10)*(num/10%10)*(num/100)`; בסוף מדפיסים את המונה.
הרעיון: מספר הקלטים ידוע מראש (30), ולכן לולאת for. בכל סיבוב קולטים מספר אחד ומבצעים עליו שתי בדיקות בלתי תלויות: האם הוא אי-זוגי (לצורך המונה) והאם הוא תלת-ספרתי (לצורך הדפסת המכפלה).
1. מספר הוא אי-זוגי אם השארית בחלוקה ב-2 היא 1: `num % 2 == 1` (המספרים חיוביים, ולכן השארית אינה שלילית). במקרה כזה מגדילים את המונה `oddCount`.
2. מספר חיובי הוא תלת-ספרתי אם ורק אם .
3. במספר תלת-ספרתי יש בדיוק שלוש ספרות, ולכן אפשר לחלץ כל אחת ישירות:
•ספרת האחדות: `num % 10`
•ספרת העשרות: `num / 10 % 10`
•ספרת המאות: `num / 100` (חילוק שלמים)
4. מדפיסים את מכפלת שלוש הספרות. למשל עבור 123: .
5. אחרי הלולאה, כשכל 30 המספרים נקלטו, מדפיסים את המונה.
int oddCount = 0; // מונה המספרים האי-זוגיים
for (int i = 0; i < 30; i++)
{
int num = in.nextInt();
if (num % 2 == 1) // מספר אי-זוגי
oddCount++;
if (num >= 100 && num <= 999) // מספר תלת-ספרתי
{
int units = num % 10; // ספרת האחדות
int tens = num / 10 % 10; // ספרת העשרות
int hundreds = num / 100; // ספרת המאות
System.out.println(units * tens * hundreds);
}
}
System.out.println("odd numbers: " + oddCount);int oddCount = 0; // מונה המספרים האי-זוגיים
for (int i = 0; i < 30; i++)
{
int num = int.Parse(Console.ReadLine());
if (num % 2 == 1) // מספר אי-זוגי
oddCount++;
if (num >= 100 && num <= 999) // מספר תלת-ספרתי
{
int units = num % 10; // ספרת האחדות
int tens = num / 10 % 10; // ספרת העשרות
int hundreds = num / 100; // ספרת המאות
Console.WriteLine(units * tens * hundreds);
}
}
Console.WriteLine("odd numbers: " + oddCount);דוגמה: עבור הקלט 123 יודפס 6, עבור 250 יודפס 0 (), ועבור 45 לא תודפס מכפלה (המספר אינו תלת-ספרתי), אבל הוא ייספר כאי-זוגי.
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · עיבוד מחרוזות עד מחרוזת קצרה
כתבו קטע תוכנית הקולטת מחרוזות עד שתיקלט מחרוזת שאורכה קטן משישה תווים.
עבור כל מחרוזת באורך אי זוגי יודפס התו האמצעי במחרוזת.
נוסף על כך יש לחשב ולהדפיס:
•כמה מחרוזות מתחילות באות גדולה ('A'...'Z').
•כמה מחרוזות לא מסתיימות בספרה ('0'..'9').
◂ פתרון מלא לשאלה 2
פתרון
לולאת while שרצה כל עוד אורך המחרוזת לפחות 6; באורך אי-זוגי מדפיסים את התו במקום `len/2`; מונים מחרוזות שהתו הראשון שלהן בין 'A' ל-'Z' ומחרוזות שהתו האחרון שלהן אינו בין '0' ל-'9'; בסוף מדפיסים את שני המונים.
הרעיון: מספר המחרוזות אינו ידוע מראש - הקליטה נעצרת לפי תנאי, ולכן לולאת while עם "קליטה מקדימה": קולטים מחרוזת לפני הלולאה, ובסוף כל סיבוב קולטים את הבאה. המחרוזת שאורכה קטן מ-6 רק מסיימת את הקלט ואינה מעובדת.
1. תנאי הלולאה: `str.length() >= 6` (כל עוד האורך אינו קטן משישה).
2. התו האמצעי: במחרוזת באורך אי-זוגי `len` התו האמצעי נמצא במקום `len / 2` (חילוק שלמים). למשל באורך 7 המקומות הם 0-6, והאמצעי הוא 3.
3. מתחילה באות גדולה: בודקים את התו הראשון: `'A' <= str.charAt(0) <= 'Z'`, ואם כן מגדילים את `bigCount`.
4. לא מסתיימת בספרה: התו האחרון נמצא במקום `len - 1`. אם הוא אינו בין `'0'` ל-`'9'`, מגדילים את `notDigitCount`.
5. אחרי הלולאה מדפיסים את שני המונים.
int bigCount = 0; // מחרוזות שמתחילות באות גדולה
int notDigitCount = 0; // מחרוזות שלא מסתיימות בספרה
String str = in.next();
while (str.length() >= 6)
{
int len = str.length();
if (len % 2 == 1) // אורך אי-זוגי
System.out.println(str.charAt(len / 2));
char first = str.charAt(0);
if (first >= 'A' && first <= 'Z')
bigCount++;
char last = str.charAt(len - 1);
if (!(last >= '0' && last <= '9'))
notDigitCount++;
str = in.next();
}
System.out.println("start with capital: " + bigCount);
System.out.println("not end with digit: " + notDigitCount);int bigCount = 0; // מחרוזות שמתחילות באות גדולה
int notDigitCount = 0; // מחרוזות שלא מסתיימות בספרה
string str = Console.ReadLine();
while (str.Length >= 6)
{
int len = str.Length;
if (len % 2 == 1) // אורך אי-זוגי
Console.WriteLine(str[len / 2]);
char first = str[0];
if (first >= 'A' && first <= 'Z')
bigCount++;
char last = str[len - 1];
if (!(last >= '0' && last <= '9'))
notDigitCount++;
str = Console.ReadLine();
}
Console.WriteLine("start with capital: " + bigCount);
Console.WriteLine("not end with digit: " + notDigitCount);דוגמה: עבור הקלט `abcdefg`, `Hello12`, `ABCDEFGH`, `xyz123`, `Zebra99x`, `abc` יודפסו התווים `d` ו-`l` (שתי המחרוזות הראשונות באורך 7), ואחר כך: 3 מחרוזות מתחילות באות גדולה ו-3 מחרוזות לא מסתיימות בספרה. המחרוזת `abc` מסיימת את הקלט.
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · מערך מאורגן: בדיקה ומילוי אקראי
מערך של מספרים שלמים נקרא "מערך מאורגן" אם כל הערכים הנמצאים במקומות הזוגיים גדולים מכל הערכים הנמצאים במקומות האי-זוגיים.
המערך הבא הוא מערך "מאורגן":
כתבו פעולה המקבלת מערך של מספרים שלמים `arr`. הפעולה תחזיר ערך `true`, אם המערך "מאורגן", ולא, הפעולה תחזיר ערך `false`. כותרת הפעולה:
public static boolean isArranged(int[] arr)public static bool IsArranged(int[] arr)כתבו פעולה המקבלת מערך של מספרים שלמים `arr` ושני פרמטרים נוספים `a` ו-`b`, מטיפוס מספר שלם. הפעולה תמלא מערך `arr` במספרים אקראיים בין `a` ל-`b` (כולל) עד שהמערך יהיה מאורגן.
כותרת הפעולה:
public static void fill(int[]arr, int a, int b)public static void Fill(int[]arr, int a, int b)◂ פתרון מלא לשאלה 3
סעיף א
מחשבים את המינימום במקומות הזוגיים ואת המקסימום במקומות האי-זוגיים; המערך מאורגן אם ורק אם המינימום הזוגי גדול מהמקסימום האי-זוגי.
הרעיון: התנאי "כל ערך במקום זוגי גדול מכל ערך במקום אי-זוגי" שקול לתנאי אחד: הקטן ביותר מבין הערכים במקומות הזוגיים גדול מהגדול ביותר מבין הערכים במקומות האי-זוגיים. כך אין צורך להשוות כל זוג, ומספיק מעבר אחד על המערך.
1. מאתחלים `minEven = arr[0]` (מקום 0 זוגי) ו-`maxOdd = arr[1]` (מקום 1 אי-זוגי). במערך יש לפחות שני תאים, ולכן שני התאים קיימים.
2. עוברים על המקומות מ-2 עד הסוף: במקום זוגי מעדכנים את המינימום, ובמקום אי-זוגי מעדכנים את המקסימום.
3. מחזירים `minEven > maxOdd`.
בדיקה בדוגמה: במקומות הזוגיים 12, 7, 15, 6 - המינימום 6. במקומות האי-זוגיים 3, 5, 2 - המקסימום 5. מכיוון ש- יוחזר `true`.
סיבוכיות: מעבר יחיד על המערך - .
public static boolean isArranged(int[] arr)
{
int minEven = arr[0]; // הקטן ביותר במקומות הזוגיים
int maxOdd = arr[1]; // הגדול ביותר במקומות האי-זוגיים
for (int i = 2; i < arr.length; i++)
{
if (i % 2 == 0)
{
if (arr[i] < minEven)
minEven = arr[i];
}
else
{
if (arr[i] > maxOdd)
maxOdd = arr[i];
}
}
return minEven > maxOdd;
}public static bool IsArranged(int[] arr)
{
int minEven = arr[0]; // הקטן ביותר במקומות הזוגיים
int maxOdd = arr[1]; // הגדול ביותר במקומות האי-זוגיים
for (int i = 2; i < arr.Length; i++)
{
if (i % 2 == 0)
{
if (arr[i] < minEven)
minEven = arr[i];
}
else
{
if (arr[i] > maxOdd)
maxOdd = arr[i];
}
}
return minEven > maxOdd;
}תשובה: הפעולה שלמעלה.
סעיף ב
לולאת do-while: ממלאים את כל המערך במספרים אקראיים בין a ל-b, וחוזרים על המילוי כל עוד `isArranged(arr)` מחזירה false.
הרעיון: "ממלאים עד שהמערך יהיה מאורגן" - כלומר ממלאים את כל המערך במספרים אקראיים, בודקים בעזרת הפעולה מסעיף א', ואם המערך אינו מאורגן ממלאים אותו מחדש. מכיוון שצריך למלא לפחות פעם אחת לפני הבדיקה, מתאימה לולאת do-while.
1. יוצרים עצם `Random` אחד לפני הלולאה.
2. בכל סיבוב ממלאים כל תא במספר אקראי בטווח : ב-Java `a + rand.nextInt(b - a + 1)`, וב-C# `rand.Next(a, b + 1)`.
3. תנאי החזרה: `!isArranged(arr)` - חוזרים כל עוד המערך אינו מאורגן.
4. למה הלולאה מסתיימת: מכיוון ש-, קיים מילוי מאורגן (למשל בכל המקומות הזוגיים ו- בכל המקומות האי-זוגיים), ולכן בכל סיבוב יש הסתברות חיובית להגיע למערך מאורגן, והלולאה תסתיים בוודאות כמעט מלאה.
public static void fill(int[] arr, int a, int b)
{
Random rand = new Random();
do
{
for (int i = 0; i < arr.length; i++)
arr[i] = a + rand.nextInt(b - a + 1);
}
while (!isArranged(arr));
}public static void Fill(int[] arr, int a, int b)
{
Random rand = new Random();
do
{
for (int i = 0; i < arr.Length; i++)
arr[i] = rand.Next(a, b + 1);
}
while (!IsArranged(arr));
}דוגמה: עבור מערך באורך 7 ו- אפשר לקבל למשל `{9, 1, 8, 3, 8, 5, 9}`: המינימום במקומות הזוגיים 8 גדול מהמקסימום במקומות האי-זוגיים 5.
תשובה: הפעולה שלמעלה.
שאלה 4 · מחלקת תינוק: מדידות, ממוצע ו-BMI
המחלקה `Baby` (תינוק) משמשת למעקב התפתחותי של התינוקות המגיעים למרפאה במהלך השנה הראשונה לחייהם.
כל תינוק מוזמן לביקורת __אחת לחודש__. בכל ביקורת שוקלים ומודדים את גובה התינוק ושומרים את התוצאות.
שימו לב: במקרה שתינוק לא הגיע לביקורת בחודש מסוים ערך המדידות יהיה 0 בחודש זה.
אפשר להניח שבחודש שבו הגיע לביקורת תהיה גם מדידת משקל וגם מדידת גובה.
תכונות המחלקה:
private String name; // שם
private double[] height; // מדידת גובה חודשית
private double[] weight; // מדידת משקל חודשיתprivate string name; // שם
private double[] height; // מדידת גובה חודשית
private double[] weight; // מדידת משקל חודשיתהערה: אורך המערכים `height` ו-`weight` הוא 12. בתא מספר אפס שומרים מדידות שנעשו בחודש הראשון אחרי לידה, בתא מספר אחד – מדידות שנעשו בחודש השני אחרי לידה וכך הלאה.
לדוגמה:
שני מערכים מתארים התפתחות הילד ב-12 חודשים הראשונים:
משקל בקילוגרמים (`weight`):
גובה במטרים (`height`):
המדידה הראשונה הייתה בחודש 1, המדידה האחרונה הייתה בחודש 12.
שימו לב: בחודשים 2, 6, 8, 9, 11 לא היו מדידות.
כתבו פעולה המקבלת מספר חודש `month`, גובה `h` ומשקל `w` ומעדכנת את מערכי המדידות בהתאם.
כותרת הפעולה:
public void setData(int month, double h, double w)public void SetData(int month, double h, double w)כתבו פעולה המחזירה את ממוצע המשקל על פי כל המדידות שהתקיימו.
כותרת הפעולה:
public double avgWeight()public double AvgWeight()המדד מסת גוף (`BMI - BodyMassIndex`) משקלל את משקל עם הגובה. המדד הזה חשוב להערכה אם התפתחות הילד תקינה. חישוב ה-`BMI` מתבצע לפי הנוסחה הבאה: משקל חלקי גובה בריבוע:
כתבו פעולה המחזירה מדד ה-`BMI` של התינוק על פי המדידה האחרונה שלו.
כותרת הפעולה:
public double getLastBmi()public double GetLastBmi()◂ פתרון מלא לשאלה 4
סעיף א
`height[month - 1] = h; weight[month - 1] = w;` (חודש 1 נשמר בתא 0).
הרעיון: לפי ההערה בשאלה, המדידות של החודש הראשון נשמרות בתא 0, של החודש השני בתא 1 וכן הלאה. לכן חודש `month` (בין 1 ל-12) נשמר בתא `month - 1`.
1. מחשבים את מקום התא: `month - 1`.
2. מציבים את הגובה במערך `height` ואת המשקל במערך `weight` באותו מקום.
public void setData(int month, double h, double w)
{
height[month - 1] = h; // חודש 1 נשמר בתא 0
weight[month - 1] = w;
}public void SetData(int month, double h, double w)
{
height[month - 1] = h; // חודש 1 נשמר בתא 0
weight[month - 1] = w;
}תשובה: הפעולה שלמעלה.
סעיף ב
סוכמים ומונים רק את התאים שבהם `weight[i] > 0` ומחזירים סכום חלקי מונה; בדוגמה: ק"ג.
הרעיון: חודש שבו לא הייתה ביקורת מסומן במשקל 0, ואסור לכלול אותו בממוצע. לכן עוברים על המערך, ולוקחים בחשבון רק תאים עם משקל חיובי: צובר לסכום ומונה למספר המדידות.
1. `sum = 0`, `count = 0`.
2. לכל תא שבו `weight[i] > 0`: מוסיפים את המשקל לסכום ומגדילים את המונה.
3. מחזירים `sum / count`. אם לא הייתה אף מדידה (`count == 0`) מחזירים 0, כדי לא לחלק באפס.
בדיקה בדוגמה: יש 7 מדידות:
ק"ג.
public double avgWeight()
{
double sum = 0;
int count = 0; // מספר הביקורות שהתקיימו
for (int i = 0; i < weight.length; i++)
{
if (weight[i] > 0) // בחודש זה הייתה מדידה
{
sum += weight[i];
count++;
}
}
if (count == 0) // לא הייתה אף מדידה
return 0;
return sum / count;
}public double AvgWeight()
{
double sum = 0;
int count = 0; // מספר הביקורות שהתקיימו
for (int i = 0; i < weight.Length; i++)
{
if (weight[i] > 0) // בחודש זה הייתה מדידה
{
sum += weight[i];
count++;
}
}
if (count == 0) // לא הייתה אף מדידה
return 0;
return sum / count;
}תשובה: הפעולה שלמעלה (בדוגמה מוחזר בערך 9.272).
סעיף ג
מחפשים מהסוף את התא האחרון שבו `weight[i] > 0` ומחזירים `weight[i] / (height[i] * height[i])`; בדוגמה: .
הרעיון: המדידה האחרונה היא התא האחרון במערך שבו המשקל אינו 0. הדרך הנוחה היא לעבור על המערך מהסוף להתחלה ולעצור בתא הראשון עם מדידה. באותו תא נמצאים גם המשקל וגם הגובה של אותה ביקורת.
1. לולאה מ-`i = 11` עד `i = 0`.
2. בתא הראשון (מהסוף) שבו `weight[i] > 0` מחזירים = `weight[i] / (height[i] * height[i])`.
3. אם לא נמצאה אף מדידה מחזירים 0.
בדיקה בדוגמה: המדידה האחרונה בתא 11 (חודש 12): , :
.
public double getLastBmi()
{
for (int i = weight.length - 1; i >= 0; i--)
{
if (weight[i] > 0) // המדידה האחרונה שהתקיימה
return weight[i] / (height[i] * height[i]);
}
return 0; // לא הייתה אף מדידה
}public double GetLastBmi()
{
for (int i = weight.Length - 1; i >= 0; i--)
{
if (weight[i] > 0) // המדידה האחרונה שהתקיימה
return weight[i] / (height[i] * height[i]);
}
return 0; // לא הייתה אף מדידה
}תשובה: הפעולה שלמעלה (בדוגמה מוחזר בערך 23.44).
שאלה 5 · העברת פרמטרים: ערך מול הפניה למערך
נתונות שתי הפעולות `what` ו-`where` והפעולה הראשית `main` הבאות:
public static void what(int a, int b)
{
System.out.println(a+" "+b);
a = a + b;
b = a - b;
a = a - b;
System.out.println(a +" "+ b);
}
public static void where(int[] arr)
{
System.out.println(arr[0] +" "+ arr[1]);
arr[0] = arr[0] + arr[1];
arr[1] = arr[0] - arr[1];
arr[0] = arr[0] - arr[1];
System.out.println(arr[0] +" "+ arr[1]);
}
public static void main(String[] args)
{
int x = 3, y = 7;
int[] z = {3, 7};
what(x, y);
where(z);
System.out.println("x, y: "+x +" "+ y);
System.out.println("z: "+z[0] +" "+ z[1]);
}public static void What(int a, int b)
{
Console.WriteLine(a+" "+b);
a = a + b;
b = a - b;
a = a - b;
Console.WriteLine(a +" "+ b);
}
public static void Where(int[] arr)
{
Console.WriteLine(arr[0] +" "+ arr[1]);
arr[0] = arr[0] + arr[1];
arr[1] = arr[0] - arr[1];
arr[0] = arr[0] - arr[1];
Console.WriteLine(arr[0] +" "+ arr[1]);
}
public static void Main(string[] args)
{
int x = 3, y = 7;
int[] z = {3, 7};
What(x, y);
Where(z);
Console.WriteLine("x, y: "+x +" "+ y);
Console.WriteLine("z: "+z[0] +" "+ z[1]);
}עקבו בעזרת טבלת מעקב אחרי ביצוע הפעולה `main` ורשמו מה יהיה הפלט.
הפעולה `where` השתנתה לפעולה הבאה:
public static void where(int[] arr)
{
System.out.println(arr[0] +" "+ arr[1]);
what(arr[0], arr[1]);
System.out.println(arr[0] +" "+ arr[1]);
}public static void Where(int[] arr)
{
Console.WriteLine(arr[0] +" "+ arr[1]);
What(arr[0], arr[1]);
Console.WriteLine(arr[0] +" "+ arr[1]);
}מה יהיה הפלט של הפעולה `main` אחרי השינוי?
◂ פתרון מלא לשאלה 5
סעיף א
הפלט: `3 7`, `7 3`, `3 7`, `7 3`, `x, y: 3 7`, `z: 7 3` (כל אחד בשורה).
הרעיון: הפעולה `what` מקבלת שני משתנים מטיפוס `int` - הם מועברים לפי ערך, כלומר `a` ו-`b` הם עותקים, וההחלפה ביניהם לא משפיעה על `x` ו-`y`. הפעולה `where` מקבלת הפניה למערך, ולכן השינויים ב-`arr[0]` ו-`arr[1]` הם שינויים במערך `z` עצמו.
שלוש הפקודות `a = a + b; b = a - b; a = a - b;` מחליפות בין שני הערכים בלי משתנה עזר: מ- מתקבל , אחר כך , ואחר כך .
תשובה: הפלט הוא
3 7
7 3
3 7
7 3
x, y: 3 7
z: 7 3סעיף ב
הפלט: `3 7`, `7 3`, `3 7`, `3 7`, `7 3`, `3 7`, `x, y: 3 7`, `z: 3 7`.
הרעיון: עכשיו `where` לא משנה את המערך בעצמה, אלא שולחת את הערכים `arr[0]` ו-`arr[1]` לפעולה `what`. בתוך `what` מוחלפים רק העותקים `a` ו-`b`, ולכן המערך `z` נשאר `{3,7}`.
1. `what(x, y)` - כמו בסעיף א': מדפיסה `3 7` ואחר כך `7 3`; `x` ו-`y` לא משתנים.
2. `where(z)`:
•מדפיסה את המערך: `3 7`.
•`what(3, 7)` מדפיסה `3 7` ואחר כך `7 3` (ההחלפה רק בעותקים).
•מדפיסה שוב את המערך, שלא השתנה: `3 7`.
3. `main` מדפיסה `x, y: 3 7` ו-`z: 3 7`.
תשובה: הפלט הוא
3 7
7 3
3 7
3 7
7 3
3 7
x, y: 3 7
z: 3 7שאלה 6 · ניתוח פעולות על מחרוזות ומערך מחרוזות
נתונה הפעולה `secret()` הבאה המקבלת שתי מחרוזות:
public static boolean secret(String s1, String s2)
{
if(s1.equals(s2)) return false;
while(s1.length() != 0 && s2.length() != 0 )
{
int pos = s2.indexOf(s1.charAt(0));
if(pos == -1) return false;
s1 = s1.substring(1);
s2 = s2.substring(0,pos) + s2.substring(pos+1);
}
return s1.length() == 0;
}public static bool Secret(string s1, string s2)
{
if(s1.Equals(s2)) return false;
while(s1.Length != 0&& s2.Length != 0 )
{
int pos = s2.IndexOf(s1[0]);
if(pos == -1) return false;
s1 = s1.Substring(1);
s2 = s2.Substring(0,pos) + s2.Substring(pos+1);
}
return s1.Length == 0;
}תנו דוגמה למחרוזת `s2` באורך של שישה תווים שעבורה הפעולה `secret("HELLO!", s2)` תחזיר ערך `true`.
נתונה הטענה הבאה:
אם זימון הפעולה `secret(s1, s2)` מחזיר ערך `true`, גם זימון הפעולה `secret(s2, s1)` יחזיר ערך `true`.
האם הטענה נכונה? הסבירו את תשובתכם.
מה מבצעת הפעולה `secret` באופן כללי?
נתונה הפעולה `mystery` המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה `secret`:
public static boolean mystery(String[] arr)
{
for (int i = 0; i<arr.length -1; i+=2)
{
if (!secret(arr[i], arr[i+1]))
return false;
}
return true;
}public static bool Mystery(string[] arr)
{
for (int i = 0; i<arr.Length -1; i+=2)
{
if (!Secret(arr[i], arr[i+1]))
return false;
}
return true;
}תנו דוגמה למערך `arr` בגודל שישה תאים שעבורו הפעולה `mystery` תחזיר ערך `true`.
נתונה הטענה הבאה: אם זימון הפעולה `mystery(arr)` מחזיר ערך `true`, המערך `arr` לא כולל זוג מחרוזות זהות אשר נמצאות בתאים סמוכים. האם הטענה נכונה? הסבירו את תשובתכם.
מהי הסיבוכיות של הפעולה `mystery`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `s2 = "HELL!O"` (כל סידור אחר של התווים H, E, L, L, O, ! השונה מ-"HELLO!").
הרעיון: בכל סיבוב הלולאה לוקחים את התו הראשון של `s1`, מחפשים אותו ב-`s2`, ומוחקים אותו משתי המחרוזות. אם תו של `s1` לא נמצא ב-`s2` מוחזר `false`. בנוסף, אם המחרוזות זהות מוחזר `false` כבר בשורה הראשונה.
לכן `s2` צריכה להכיל בדיוק את ששת התווים של `"HELLO!"` (כולל שני L), אבל בסדר אחר. למשל `s2 = "HELL!O"`:
הלולאה נעצרת כש-`s1` ריקה, ומוחזר `s1.length() == 0`, כלומר `true`.
תשובה: `s2 = "HELL!O"`.
לא נכונה. למשל `secret("AB", "ABC")` מחזירה true, אבל `secret("ABC", "AB")` מחזירה false (התו C לא נמצא).
הרעיון: `secret(s1, s2)` בודקת רק שכל תו של `s1` נמצא ב-`s2`. ב-`s2` יכולים להיות תווים נוספים. כשמחליפים את הסדר, התווים הנוספים האלה נמצאים ב-`s1` החדשה ולא יימצאו ב-`s2` החדשה.
דוגמה נגדית: `s1 = "AB"`, `s2 = "ABC"`.
1. `secret("AB", "ABC")`: המחרוזות שונות; A נמצא ונמחק (`s2 = "BC"`), B נמצא ונמחק (`s2 = "C"`); `s1` ריקה, ולכן מוחזר `true`.
2. `secret("ABC", "AB")`: A ו-B נמצאים ונמחקים, ואז `s2` ריקה והלולאה נעצרת כש-`s1 = "C"`. מוחזר `s1.length() == 0`, כלומר `false`.
תשובה: הטענה אינה נכונה (דוגמה נגדית: "AB" ו-"ABC").
מחזירה true אם המחרוזות שונות וכל תו של s1 מופיע ב-s2 לפחות אותו מספר פעמים (בלי חשיבות לסדר); אחרת false.
1. אם `s1` ו-`s2` זהות מוחזר `false`.
2. אחרת, כל תו של `s1` מחפשים ב-`s2` ומוחקים מופע אחד שלו מ-`s2`. לכן תו שמופיע ב-`s1` פעמיים צריך להופיע ב-`s2` לפחות פעמיים. מכיוון שהחיפוש הוא בכל `s2` (ולא מהמקום הקודם), הסדר של התווים אינו משנה.
3. אם כל התווים של `s1` נמצאו, `s1` מתרוקנת ומוחזר `true`. אם תו אחד לא נמצא (או ש-`s2` התרוקנה קודם), מוחזר `false`.
תשובה: הפעולה מחזירה `true` אם `s1` שונה מ-`s2` וכל התווים של `s1` נמצאים ב-`s2` (כל תו לפחות באותה כמות שבה הוא מופיע ב-`s1`, בכל סדר); אחרת היא מחזירה `false`. במילים אחרות: אפשר לקבל את `s1` ממחיקת חלק מהתווים של `s2` וסידור מחדש של השאר, והמחרוזות אינן זהות.
סעיף ב
למשל `{"CAT", "ACT", "DOG", "GOD", "EAR", "ARE"}`.
הרעיון: הלולאה עוברת על הזוגות (0,1), (2,3), (4,5) - `i` גדל ב-2. לכל זוג צריך ש-`secret(arr[i], arr[i+1])` תחזיר `true`, כלומר שתי מחרוזות שונות שהתווים של הראשונה כולם נמצאים בשנייה.
נבחר שלושה זוגות של מילים שהן סידור אחר של אותן אותיות:
`arr = {"CAT", "ACT", "DOG", "GOD", "EAR", "ARE"}`
•`secret("CAT", "ACT")` - המחרוזות שונות ו-C, A, T נמצאות כולן: `true`.
•`secret("DOG", "GOD")` - `true`.
•`secret("EAR", "ARE")` - `true`.
לכן `mystery` מחזירה `true`.
תשובה: `{"CAT", "ACT", "DOG", "GOD", "EAR", "ARE"}`.
לא נכונה. `mystery` בודקת רק את הזוגות (0,1), (2,3), ...; למשל `{"ab", "ba", "ba", "ab"}` מחזיר true, אבל בתאים הסמוכים 1 ו-2 יש מחרוזות זהות.
הרעיון: נכון שבתוך כל זוג נבדק (`arr[i]`, `arr[i+1]` עם `i` זוגי) המחרוזות שונות, כי `secret` מחזירה `false` על מחרוזות זהות. אבל `mystery` לא בודקת זוגות סמוכים שמתחילים במקום אי-זוגי, כמו `arr[1]` ו-`arr[2]`.
דוגמה נגדית: `arr = {"ab", "ba", "ba", "ab"}`
1. `i = 0`: `secret("ab", "ba")` - שונות, ו-a, b נמצאות: `true`.
2. `i = 2`: `secret("ba", "ab")` - `true`.
3. הלולאה מסתיימת ומוחזר `true`, אף על פי ש-`arr[1]` ו-`arr[2]` שתיהן `"ba"` והן בתאים סמוכים.
תשובה: הטענה אינה נכונה.
, כאשר n גודל המערך ו-m האורך המרבי של מחרוזת.
נסמן: - מספר התאים במערך, - האורך המרבי של מחרוזת במערך.
1. הסיבוכיות של `secret`: ההשוואה `equals` עולה . בלולאה יש לכל היותר סיבובים (בכל סיבוב נמחק תו אחד מ-`s1`). בכל סיבוב `indexOf` סורקת את `s2`, ו-`substring` ושרשור בונים מחרוזות חדשות - כל אחת מהפעולות האלה עולה . לכן .
2. הסיבוכיות של `mystery`: הלולאה מבצעת זימונים של `secret` (במקרה הגרוע, כשכולם מחזירים `true`), כל אחד ב-.
תשובה: .
שאלה 7 · מחלקת ספר: פעולה, מעקב והשלמת קוד
נתונה המחלקה `Book` שיש לה שלוש תכונות:
•קוד ספר – `code`, מטיפוס שלם.
•שנת הוצאה – `year`, מטיפוס שלם.
•האם כתוב בעברית – `isHebrew`, מטיפוס בוליאני.
במחלקה הוגדרה פעולה הבונה (בנאי, `constructor`)
public Book (int code, int year, boolean isHebrew)public Book (int code, int year, bool isHebrew)לכל תכונות של המחלקה הוגדרו פעולות `get/set`
כתבו פעולה המקבלת מספר שלם וחיובי `year1` המציין שנה ובודקת אם עברו יותר מעשר שנים משנת ההוצאה עד לשנה `year1` (כולל). אם כן – הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public boolean oldBook(int year1)public bool OldBook(int year1)לפניכם קטע קוד בפעולה הראשית `main()`. עקבו בעזרת טבלת המעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט.
Book b1 = new Book(1122, 1998, false);
Book b2 = new Book (2233, 2010, true);
// כאן יש להוסיף פקודה/פקודות בסעיף ג' (*)
if( b1.oldBook(2014)&& !b1.getIsHebrew())
System.out.println("###");
else
System.out.println("***");
if(b2.oldBook(2015))
System.out.println("!!!");
else
if(b2.getIsHebrew())
System.out.println("???");Book b1 = new Book(1122, 1998, false);
Book b2 = new Book (2233, 2010, true);
// כאן יש להוסיף פקודה/פקודות בסעיף ג' (*)
if( b1.OldBook(2014)&& !b1.GetIsHebrew())
Console.WriteLine("###");
else
Console.WriteLine("***");
if(b2.OldBook(2015))
Console.WriteLine("!!!");
else
if(b2.GetIsHebrew())
Console.WriteLine("???");נא השלימו בקוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה `*` בלבד.
◂ פתרון מלא לשאלה 7
סעיף א
`return year1 - this.year + 1 > 10;` (שקול ל-`year1 - year >= 10`).
הרעיון: סופרים את השנים משנת ההוצאה `year` עד `year1` כולל שתי הקצוות: מספרן הוא . הספר "ישן" אם מספר זה גדול מ-10, כלומר , שזה אותו דבר כמו .
לדוגמה, ספר משנת 2010: עד 2019 כולל יש 10 שנים - לא יותר מעשר, ולכן `false`; עד 2020 כולל יש 11 שנים, ולכן `true`.
התכונה `year` היא של העצם המפעיל, ולכן ניגשים אליה ישירות (`this.year`).
public boolean oldBook(int year1)
{
// מספר השנים מ-year עד year1 כולל הוא year1 - year + 1
return year1 - this.year + 1 > 10;
}public bool OldBook(int year1)
{
// מספר השנים מ-year עד year1 כולל הוא year1 - year + 1
return year1 - this.year + 1 > 10;
}תשובה: הפעולה שלמעלה.
סעיף ב
הפלט: `###` ואחריו `???`.
הרעיון: מחשבים לכל ספר את ערך `oldBook` לפי הנוסחה מסעיף א' (), ואז עוקבים אחרי התנאים.
תשובה: הפלט הוא
###
???סעיף ג
`b1.setIsHebrew(true);` ו-`b2.setIsHebrew(false);` (ב-C#: `b1.SetIsHebrew(true); b2.SetIsHebrew(false);`).
הרעיון: צריך לשנות את התוצאה של שני משפטי ה-if:
1. כדי שיודפס `*` ולא `###`: התנאי `b1.oldBook(2014) && !b1.getIsHebrew()` צריך להיות `false`. הדרך הפשוטה: להגדיר ש-b1 כתוב בעברית, ואז `!b1.getIsHebrew()` הוא `false`. (אפשרות אחרת: לשנות את שנת ההוצאה של b1 לשנה שבה , למשל 2010.)
2. כדי שלא יודפס דבר בחלק השני: `b2.oldBook(2015)` כבר `false` (), ולכן נכנסים ל-else. שם יודפס `???` אם b2 בעברית - לכן צריך להגדיר ש-b2 אינו בעברית. אז אף תנאי לא מתקיים ולא מודפס דבר.
b1.setIsHebrew(true);
b2.setIsHebrew(false);b1.SetIsHebrew(true);
b2.SetIsHebrew(false);בדיקה: התנאי הראשון: `true && !true` = `false`, ולכן מודפס `*`. התנאי השני: `b2.oldBook(2015)` = `false`, ובתוך ה-else `b2.getIsHebrew()` = `false`, ולכן לא מודפס דבר.
תשובה: במקום (*) כותבים `b1.setIsHebrew(true);` ו-`b2.setIsHebrew(false);`.
שאלה 8 · מספרים אחים ומערך אחים
שני מספרים שלמים וחיוביים נקראים "אחים" אם יש להם מספר ספרות זהה וסכום ספרות גם הוא זהה.
כתבו פעולה המקבלת שני מספרים שלמים וחיוביים. הפעולה תבדוק אם הם "אחים"
אם כן – הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isItBrothers(int num1, int num2)public static bool IsItBrothers(int num1, int num2)מערך של מספרים שלמים וחיוביים נקרא "מערך אחים" אם כל איברי המערך "אחים" זה לזה.
כתבו פעולה המקבלת מערך מספרים שלמים וחיוביים ובודקת אם הוא "מערך אחים".
אם כן – הפעולה תחזיר ערך `true`, ולא, הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isItBrothers(int[] arr)public static bool IsItBrothers(int[] arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
מפרקים כל מספר לספרות בעזרת `%10` ו-`/10`, סופרים ספרות וסוכמים אותן, ומחזירים `count1 == count2 && sum1 == sum2`.
הרעיון: לכל אחד משני המספרים מחשבים שני נתונים - מספר הספרות וסכום הספרות - בלולאת פירוק רגילה: `num % 10` היא ספרת האחדות, ו-`num / 10` מוחקת אותה. המספרים "אחים" אם שני הנתונים שווים.
1. לולאה על `num1`: בכל סיבוב מוסיפים את ספרת האחדות ל-`sum1`, מגדילים את `count1` ומוחקים את הספרה, עד ש-`num1` מתאפס.
2. אותו דבר עבור `num2`.
3. מחזירים `count1 == count2 && sum1 == sum2`.
דוגמאות: 123 ו-321: שלוש ספרות, סכום 6 בשניהם - אחים. 123 ו-51: סכום 6 בשניהם, אבל מספר הספרות שונה - לא אחים. 15 ו-24: שתי ספרות, סכומים 6 ו-6 - אחים.
public static boolean isItBrothers(int num1, int num2)
{
int count1 = 0, sum1 = 0; // מספר הספרות וסכום הספרות של num1
while (num1 > 0)
{
sum1 += num1 % 10;
count1++;
num1 /= 10;
}
int count2 = 0, sum2 = 0; // מספר הספרות וסכום הספרות של num2
while (num2 > 0)
{
sum2 += num2 % 10;
count2++;
num2 /= 10;
}
return count1 == count2 && sum1 == sum2;
}public static bool IsItBrothers(int num1, int num2)
{
int count1 = 0, sum1 = 0; // מספר הספרות וסכום הספרות של num1
while (num1 > 0)
{
sum1 += num1 % 10;
count1++;
num1 /= 10;
}
int count2 = 0, sum2 = 0; // מספר הספרות וסכום הספרות של num2
while (num2 > 0)
{
sum2 += num2 % 10;
count2++;
num2 /= 10;
}
return count1 == count2 && sum1 == sum2;
}תשובה: הפעולה שלמעלה.
סעיף ב
משווים כל איבר לאיבר הראשון בעזרת הפעולה מסעיף א'; אם זוג אחד אינו "אחים" מחזירים false, אחרת true.
הרעיון: לכאורה צריך לבדוק כל זוג איברים. אבל היחס "אחים" מוגדר על ידי שוויון של שני נתונים (מספר ספרות וסכום ספרות), ולכן הוא מעבר: אם כל איבר הוא אח של `arr[0]`, לכל האיברים יש אותו מספר ספרות ואותו סכום ספרות כמו ל-`arr[0]`, ולכן כל שניים מהם אחים. מספיק אם כן להשוות כל איבר לאיבר הראשון - מעבר אחד על המערך.
1. לולאה מ-`i = 1` עד סוף המערך.
2. אם `isItBrothers(arr[0], arr[i])` מחזירה `false` - מצאנו זוג שאינו אחים, ומחזירים `false` מיד.
3. אם הלולאה הסתיימה - כל האיברים אחים, ומחזירים `true`.
שתי הפעולות נקראות באותו שם ונבדלות ברשימת הפרמטרים (העמסה), ולכן הקריאה עם שני מספרים מפעילה את הפעולה מסעיף א'.
דוגמה: `{123, 312, 600, 222}` - לכולם 3 ספרות וסכום 6: מוחזר `true`. `{123, 312, 60}` - ל-60 שתי ספרות: מוחזר `false`.
public static boolean isItBrothers(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
if (!isItBrothers(arr[0], arr[i])) // משווים כל איבר לאיבר הראשון
return false;
}
return true;
}public static bool IsItBrothers(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (!IsItBrothers(arr[0], arr[i])) // משווים כל איבר לאיבר הראשון
return false;
}
return true;
}תשובה: הפעולה שלמעלה.
סעיף ג
סעיף א': , כאשר d מספר הספרות (כלומר ); סעיף ב': , כאשר n מספר האיברים במערך.
נסמן: - מספר הספרות המרבי של מספר (כלומר ), - מספר האיברים במערך.
1. סעיף א': כל לולאת פירוק מבצעת סיבוב אחד לכל ספרה, ובכל סיבוב מספר קבוע של פעולות. שתי לולאות כאלה: .
2. סעיף ב': הלולאה מבצעת זימונים של הפעולה מסעיף א', כל אחד :
.
אם מתייחסים למספרים כבעלי מספר ספרות חסום (למשל `int`, לכל היותר 10 ספרות), סעיף א' הוא וסעיף ב' הוא .
תשובה: סעיף א' - ; סעיף ב' - .
שאלה 9 · מחלקות תאריך ועובד: השוואה וחיפוש
המחלקה `Date` מייצגת תאריך.
public class Date
{
private int day; //מייצגת את היום (שלמים בין 1 ל- 31)
private int month; //מייצגת את החודש (שלמים בין 1 ל- 12)
private int year; // מייצגת את השנה (שלמים חיוביים בני ארבע ספרות)
public Date(int day, int month, int year)
{
this.day = day;
this.month = month;
this.year = year;
}
}public class Date
{
private int day; //מייצגת את היום (שלמים בין 1 ל- 31)
private int month; //מייצגת את החודש (שלמים בין 1 ל- 12)
private int year; // מייצגת את השנה (שלמים חיוביים בני ארבע ספרות)
public Date(int day, int month, int year)
{
this.day = day;
this.month = month;
this.year = year;
}
}למחלקה הוגדרו פעולות `get/set`.
כתבו פעולה המקבלת כפרמטר תאריך מסוים ובודקת אם התאריך הנוכחי (התאריך שמיוצג באמצעות האובייקט שמפעיל את הפעולה `this`), מאוחר מהתאריך `other` שהתקבל כפרמטר.
כותרת הפעולה:
public boolean after(Date other)public bool After(Date other)המחלקה `Worker` מייצגת עובד בחברה. למחלקה שתי תכונות:
•`name` – שם העובד, מטיפוס מחרוזת, `String`.
•`birthday` – יום ההולדת, מטיפוס `Date`.
למחלקה הוגדרו פעולות `get/set`.
כתבו פעולה בונה:
public Worker(String name, int day, int month, int year)public Worker(string name, int day, int month, int year)בחברת "חג לעובדים" נהוג לשלוח ברכה ומתנה לכל עובד לכבוד יום ההולדת שלו. לשם כך, מזכירת החברה מדפיסה בתחילת כל חודש את שמות העובדים שיום ההולדת שלהם חל באותו החודש.
כתבו פעולה המקבלת מערך עובדי החברה ומספר שלם המציין מספר חודש ומדפיסה את שמות העובדים שאמורים לקבל מתנה.
כותרת הפעולה:
public static void printByMonth(Worker[] arr, int month)public static void PrintByMonth(Worker[] arr, int month)כתבו פעולה המקבלת מערך עובדי החברה ומחזירה שם העובד הצעיר ביותר.
כותרת הפעולה:
public static String youngest(Worker[] arr)public static string Youngest(Worker[] arr)◂ פתרון מלא לשאלה 9
סעיף א
משווים קודם שנים, אם שוות - חודשים, ואם גם הם שווים - ימים; מחזירים true רק אם התאריך הנוכחי גדול יותר (בתאריכים זהים - false).
הרעיון: משווים תאריכים כמו שמשווים מילים במילון: קודם הרכיב החשוב ביותר (השנה). רק אם השנים שוות עוברים לחודש, ורק אם גם החודשים שווים עוברים ליום.
1. אם השנים שונות - התאריך מאוחר אם ורק אם השנה שלו גדולה יותר.
2. אחרת, אם החודשים שונים - מאוחר אם ורק אם החודש שלו גדול יותר.
3. אחרת (אותה שנה ואותו חודש) - מאוחר אם ורק אם היום שלו גדול יותר. בתאריכים זהים מוחזר `false`, כי תאריך אינו מאוחר מעצמו.
בתוך המחלקה `Date` מותר לגשת לתכונות הפרטיות של עצם אחר מאותה מחלקה, ולכן כותבים `other.year` ישירות.
דוגמה: 1/1/2000 לעומת 31/12/1999: השנים שונות ו- - מוחזר `true`.
public boolean after(Date other)
{
if (this.year != other.year) // שנים שונות - השנה מכריעה
return this.year > other.year;
if (this.month != other.month) // אותה שנה, חודשים שונים
return this.month > other.month;
return this.day > other.day; // אותה שנה ואותו חודש
}public bool After(Date other)
{
if (this.year != other.year) // שנים שונות - השנה מכריעה
return this.year > other.year;
if (this.month != other.month) // אותה שנה, חודשים שונים
return this.month > other.month;
return this.day > other.day; // אותה שנה ואותו חודש
}תשובה: הפעולה שלמעלה.
סעיף ב
`this.name = name; this.birthday = new Date(day, month, year);`
הרעיון: הבנאי מקבל את רכיבי התאריך כשלושה מספרים, אבל התכונה `birthday` היא עצם מטיפוס `Date`. לכן יוצרים עצם `Date` חדש בעזרת הבנאי של `Date` ומציבים את ההפניה אליו בתכונה.
public Worker(String name, int day, int month, int year)
{
this.name = name;
this.birthday = new Date(day, month, year); // יוצרים עצם תאריך חדש
}public Worker(string name, int day, int month, int year)
{
this.name = name;
this.birthday = new Date(day, month, year); // יוצרים עצם תאריך חדש
}תשובה: הבנאי שלמעלה.
סעיף ג
עוברים על המערך ומדפיסים את `arr[i].getName()` לכל עובד שמקיים `arr[i].getBirthday().getMonth() == month`.
הרעיון: עוברים על כל העובדים. לכל עובד ניגשים לתאריך הלידה שלו (`getBirthday()`), ומהתאריך לחודש (`getMonth()`). אם החודש שווה לחודש שהתקבל - מדפיסים את שם העובד. הפעולה חיצונית, ולכן הגישה לתכונות היא רק דרך פעולות get.
דוגמה: עבור העובדים Dana (5/3/1990), Avi (20/7/1995), Rina (2/3/1995) והחודש 3 יודפסו Dana ו-Rina.
public static void printByMonth(Worker[] arr, int month)
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getBirthday().getMonth() == month)
System.out.println(arr[i].getName());
}
}public static void PrintByMonth(Worker[] arr, int month)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetBirthday().GetMonth() == month)
Console.WriteLine(arr[i].GetName());
}
}תשובה: הפעולה שלמעלה.
סעיף ד
חיפוש מקסימום: העובד הצעיר ביותר הוא בעל תאריך הלידה המאוחר ביותר; מחליפים את המועמד כש-`arr[i].getBirthday().after(young.getBirthday())`, ומחזירים את שמו.
הרעיון: העובד הצעיר ביותר הוא מי שנולד אחרון, כלומר בעל תאריך הלידה המאוחר ביותר. זהו חיפוש "מקסימום" רגיל, כשההשוואה נעשית בעזרת הפעולה `after` מסעיף א'.
1. המועמד הראשון: `young = arr[0]`.
2. לכל עובד אחר: אם תאריך הלידה שלו מאוחר מתאריך הלידה של המועמד - הוא הופך למועמד.
3. בסוף מחזירים את שם המועמד (`getName()`).
דוגמה: מבין Dana (5/3/1990), Avi (20/7/1995), Rina (2/3/1995) ו-Moshe (21/7/1995) יוחזר `Moshe`.
public static String youngest(Worker[] arr)
{
Worker young = arr[0]; // הצעיר ביותר עד כה
for (int i = 1; i < arr.length; i++)
{
// הצעיר ביותר הוא מי שנולד בתאריך המאוחר ביותר
if (arr[i].getBirthday().after(young.getBirthday()))
young = arr[i];
}
return young.getName();
}public static string Youngest(Worker[] arr)
{
Worker young = arr[0]; // הצעיר ביותר עד כה
for (int i = 1; i < arr.Length; i++)
{
// הצעיר ביותר הוא מי שנולד בתאריך המאוחר ביותר
if (arr[i].GetBirthday().After(young.GetBirthday()))
young = arr[i];
}
return young.GetName();
}תשובה: הפעולה שלמעלה.
שאלה 10 · חיפוש במערך ובדיקת תת-סדרה
נתונה הפעולה `why` הבאה:
public static int why(int[] a, int x, int k){
for(int i = k; i <a.length; i++)
if(a[i] == x)
return i;
return -1;
}public static int Why(int[] a, int x, int k){
for(int i = k; i < a.Length; i++)
if(a[i] == x)
return i;
return -1;
}תנו דוגמה של מערך מספרים שלמים `arr` שעבורו זימון הפעולה `why(arr, 5, 3)` יחזיר ערך 5 וזימון הפעולה `why(arr, 3, 5)` יחזיר ערך (-1).
מה מבצעת הפעולה `why` באופן כללי?
נתונה הפעולה `where` הבאה:
public static boolean where(int[] a, int[] b) {
int k = -1;
for(int i = 0; i < b.length; i++)
{
k = why(a, b[i], k+1);
if(k == -1)
return false;
}
return true;
}public static bool Where(int[] a, int[] b) {
int k = -1;
for(int i = 0; i < b.Length; i++)
{
k = Why(a, b[i], k+1);
if(k == -1)
return false;
}
return true;
}נתונים שני המערכים הבאים:
int[] a = {2,4,9,0,2,3};
int[] b = {2,4,0,9,3};מהי תוצאת הזימון `where(a, b)`?
נתונה הפעולה `what` הבאה:
public static boolean what(int[] a, int[] b) {
int i = 0, j = 0;
while(i < a.length && j < b.length)
{
if(a[i] == b[j])
{
i++;
j++;
}
else
i++;
}
return j == b.length;
}public static bool What(int[] a, int[] b) {
int i = 0, j = 0;
while(i < a.Length && j < b.Length)
{
if(a[i] == b[j])
{
i++;
j++;
}
else
i++;
}
return j == b.Length;
}האם הפעולה `what` שקולה (מבצעת בדיוק אותו הדבר) לפעולה `where`? אם כן – הסבירו מה מבצעות שתי הפעולות באופן כללי, ולא – תנו דוגמה של שני המערכים `a` ו-`b` שעבורם תוצאות הזימונים `what(a,b)` ו-`where(a,b)` יהיו שונות.
◂ פתרון מלא לשאלה 10
סעיף א
למשל `arr = {1, 2, 3, 4, 7, 5}`.
הרעיון: `why(arr, x, k)` מחפשת את הערך `x` החל מהמקום `k`.
•כדי ש-`why(arr, 5, 3)` תחזיר 5: הערך 5 צריך להיות במקום 5, ולא במקומות 3 או 4.
•כדי ש-`why(arr, 3, 5)` תחזיר -1: הערך 3 לא יופיע החל מהמקום 5 (המקום 5 תפוס כבר על ידי 5, ולכן מספיק שהמערך באורך 6).
נבחר `arr = {1, 2, 3, 4, 7, 5}`:
1. `why(arr, 5, 3)`: במקום 3 יש 4, במקום 4 יש 7, במקום 5 יש 5 - מוחזר 5.
2. `why(arr, 3, 5)`: נבדק רק המקום 5, ובו 5 ולא 3 - מוחזר -1. (הערך 3 נמצא במקום 2, לפני תחילת החיפוש.)
תשובה: `arr = {1, 2, 3, 4, 7, 5}`.
מחזירה את המקום הראשון החל מהמקום k (ועד סוף המערך) שבו נמצא הערך x, או -1 אם x לא נמצא בקטע זה.
הלולאה עוברת על המקומות `k, k+1, ...` עד סוף המערך, ובמקום הראשון שבו `a[i] == x` מחזירה את `i`. אם הלולאה הסתיימה בלי למצוא - מוחזר -1.
תשובה: הפעולה מחפשת את הערך `x` במערך `a` החל מהמקום `k`, ומחזירה את המקום של המופע הראשון שלו מ-`k` והלאה; אם אין כזה היא מחזירה -1.
סעיף ב
`false` (הערך 9 לא נמצא במערך a אחרי המקום 3).
הרעיון: `where` מחפשת כל איבר של `b` במערך `a`, ובכל פעם מתחילה את החיפוש אחרי המקום שבו נמצא האיבר הקודם (`k+1`).
`a = {2,4,9,0,2,3}` (מקומות 0-5), `b = {2,4,0,9,3}`.
בשלב `i = 3` מחפשים את 9 במקומות 4-5 (הערכים 2, 3) ולא מוצאים, כי 9 נמצא רק במקום 2 - לפני ה-0 שכבר "נוצל".
תשובה: `where(a, b)` מחזירה `false`.
סעיף ג
כן, הפעולות שקולות: שתיהן מחזירות true אם ורק אם איברי b מופיעים ב-a באותו סדר (לא בהכרח ברצף), כלומר b היא תת-סדרה של a.
הרעיון: נראה ששתי הפעולות מבצעות את אותו חיפוש "חמדני": מוצאות את האיבר הראשון של `b` במופע הראשון שלו ב-`a`, את השני - במופע הראשון אחרי זה, וכן הלאה.
1. `where`: בעזרת `why` מחפשים את `b[i]` החל מהמקום שאחרי המקום שבו נמצא `b[i-1]`. אם אחד האיברים לא נמצא - `false`; אם כולם נמצאו - `true`.
2. `what`: שני מצביעים: `i` על `a` ו-`j` על `b`. כש-`a[i] == b[j]` נמצא האיבר `b[j]`, ומתקדמים בשני המערכים; אחרת מתקדמים רק ב-`a`. כלומר `i` רץ על `a` עד שהוא מוצא את `b[j]` - בדיוק המופע הראשון של `b[j]` אחרי המקום שבו נמצא `b[j-1]`, כמו ב-`where`. מוחזר `true` אם `j` הגיע לסוף `b`, כלומר כל האיברים נמצאו.
3. גם במקרי הקצה התוצאה זהה: אם `b` ריק שתיהן מחזירות `true`; אם `a` ריק ו-`b` לא - שתיהן מחזירות `false`.
4. בדיקה בדוגמה מסעיף ב': `what` מוצאת 2 (מקום 0), 4 (מקום 1), 0 (מקום 3), ואז מחפשת 9 במקומות 4-5 ולא מוצאת; `i` מגיע לסוף ו-`j = 3 ≠ 5`, ולכן `false` - כמו `where`.
תשובה: כן, הפעולות שקולות. שתיהן בודקות אם כל איברי המערך `b` מופיעים במערך `a` באותו סדר (לא בהכרח במקומות סמוכים; ב-`a` יכולים להיות ערכים נוספים ביניהם), כלומר אם `b` היא תת-סדרה של `a`. אם כן מוחזר `true`, ואחרת `false`.
שאלה 11 · לוח שנה 2024: ימים מתחילת השנה ויום בשבוע
נתונה המחלקה `Calendar2024` המתארת לוח שנה 2024.
למחלקה תכונה אחת `days` שהיא מערך מספרים שלמים בגודל 12 אשר בכל אחד מתאיו, החל מהתא הראשון, רשום מספר הימים בחודש המתאים למיקומו של התא.
•בתא 0 (הראשון במערך) יהיה רשום 31 כי בחודש ינואר (החודש הראשון בשנה) יש 31 ימים.
•בתא 1 (השני במערך) יהיה רשום 29 כי בחודש פברואר (החודש השני בשנה) יש 29 ימים.
•בתא 2 (השלישי במערך ) יהיה רשום 31 כי בחודש מארס יש 31 ימים וכו'.
כתבו במחלקה `Calendar2024` פעולה המקבלת כפרמטרים שני מספרים שלמים. הראשון מציין יום בחודש, השני מציין את מספר החודש (ביחד מציינים מספרים אלו תאריך).
הפעולה תחשב ותחזיר את מספר הימים שעברו מתחילת השנה (1 בינואר) ועד התאריך שהתקבל.
לדוגמה:
עבור התאריך: 22,1 (22/1) יוחזר המספר: 21
עבור התאריך: 22,3 (22/3) יוחזר המספר: 81 (31+29+21)
עבור התאריך: 1,5 (1/5) יוחזר המספר: 121 (31+29+31+30)
כותרת הפעולה:
public int numOfDays(int day, int month)public int NumOfDays(int day, int month)יום 1.1 (היום הראשון של השנה) חל בשנה 2024 על יום ב' (יום שני, יום מספר 2 בשבוע).
כתבו פעולה המקבלת כפרמטרים שני מספרים שלמים. הראשון מציין יום בחודש, השני מציין את מספר החודש (ביחד מציינים מספרים אלו תאריך). הפעולה תחשב ותחזיר את מספר היום בשבוע שבו הוא חל.
לדוגמה:
עבור היום 1.1 יש להחזיר 2
עבור היום 8.1 יש להחזיר 2
עבור היום 1.2 יש להחזיר 5
עבור היום 22.3 יש להחזיר 6
כותרת הפעולה:
public int weekday(int day, int month)public int Weekday(int day, int month)הערה: אפשר להשתמש בפעולה של סעיף א' גם אם לא כתבתם אותה
כתבו במחלקה `Calendar2024` פעולה המדפיסה יום בשבוע עבור כל יום ראשון וכל יום אחרון של 12 חודשי השנה 2024.
כותרת הפעולה:
public void printFirstLast()public void PrintFirstLast()הערה: אפשר להשתמש בפעולות של סעיפים א' ו-ב' גם אם לא כתבתם אותן
◂ פתרון מלא לשאלה 11
סעיף א
סוכמים את `days[0]` עד `days[month-2]` (החודשים שלפני month) ומוסיפים `day - 1`.
הרעיון: הימים שעברו מ-1 בינואר עד התאריך מורכבים משני חלקים:
1. כל החודשים המלאים שלפני החודש `month` - החודשים 1 עד `month-1`, שנמצאים בתאים 0 עד `month-2`.
2. הימים שעברו בתוך החודש `month` עצמו: מה-1 בחודש עד היום `day` עברו `day - 1` ימים.
לכן: .
- 22/1: אין חודשים מלאים לפני ינואר: .
- 22/3: .
- 1/5: .
public int numOfDays(int day, int month)
{
int sum = 0;
for (int i = 0; i < month - 1; i++) // כל החודשים המלאים שלפני month
sum += days[i];
return sum + day - 1; // הימים שעברו בחודש month עצמו
}public int NumOfDays(int day, int month)
{
int sum = 0;
for (int i = 0; i < month - 1; i++) // כל החודשים המלאים שלפני month
sum += days[i];
return sum + day - 1; // הימים שעברו בחודש month עצמו
}תשובה: הפעולה שלמעלה.
סעיף ב
`return (numOfDays(day, month) + 1) % 7 + 1;`
הרעיון: הימים בשבוע חוזרים במחזור של 7. נסמן = מספר הימים שעברו מ-1.1 (סעיף א'). ב-1.1 () היום הוא 2, ובכל יום שעובר מספר היום עולה ב-1, ואחרי 7 (שבת) חוזרים ל-1 (ראשון).
כדי לחשב במחזור עם `%`, נעבור לספירה מ-0: יום ראשון = 0, שני = 1, ..., שבת = 6. ב-1.1 הערך הוא 1, ולכן אחרי ימים הוא . חוזרים לספירה מ-1 על ידי הוספת 1:
- 1.1: : .
- 8.1: : .
- 1.2: : .
- 22.3: : .
- 7.1 (יום ראשון): : . (חשוב להפעיל את `%` על כל הביטוי: הנוסחה הייתה נותנת כאן 8, שאינו יום בשבוע.)
public int weekday(int day, int month)
{
// 1.1 הוא יום 2; כל 7 ימים היום בשבוע חוזר על עצמו
return (numOfDays(day, month) + 1) % 7 + 1;
}public int Weekday(int day, int month)
{
// 1.1 הוא יום 2; כל 7 ימים היום בשבוע חוזר על עצמו
return (NumOfDays(day, month) + 1) % 7 + 1;
}תשובה: הפעולה שלמעלה.
סעיף ג
לולאה על החודשים 1-12: מדפיסים `weekday(1, m)` ו-`weekday(days[m-1], m)`.
הרעיון: לכל חודש `m` (1 עד 12):
1. היום הראשון בחודש הוא 1, ולכן מספר היום בשבוע שלו הוא `weekday(1, m)`.
2. היום האחרון בחודש הוא מספר הימים בחודש, שרשום בתא `days[m - 1]`, ולכן מספר היום בשבוע שלו הוא `weekday(days[m - 1], m)`.
3. מדפיסים את שני הערכים.
public void printFirstLast()
{
for (int m = 1; m <= 12; m++)
{
int first = weekday(1, m); // היום הראשון בחודש
int last = weekday(days[m - 1], m); // היום האחרון בחודש
System.out.println("month " + m + ": first day " + first + ", last day " + last);
}
}public void PrintFirstLast()
{
for (int m = 1; m <= 12; m++)
{
int first = Weekday(1, m); // היום הראשון בחודש
int last = Weekday(days[m - 1], m); // היום האחרון בחודש
Console.WriteLine("month " + m + ": first day " + first + ", last day " + last);
}
}למשל ינואר מתחיל ביום ב' (2) ומסתיים ביום ד' (4): , .
תשובה: הפעולה שלמעלה.
שאלה 12 · מערכת בנק: חשבונות, סניפים ומעבר לקוח
מערכת מחשוב של בנק "`SimpleBank`" כוללת שתי מחלקות הבאות: `Account` ו-`Branch`.
למחלקה `Account` (חשבון) ארבע תכונות:
•מספר חשבון – `num`, מטיפוס מספר שלם – `int`
•תעודת הזהות של הלקוח – `id`, מטיפוס מחרוזת – `String` (ב-C#: `string`)
•יתרה בחשבון – `balance`, מטיפוס מספר ממשי – `double`
•מצב חשבון – `isActive`, מטיפוס `boolean` (ב-C#: `bool`) (`true` – חשבון פעיל, ו-`false` – חשבון לא פעיל)
בעת פתיחת חשבון לקוח מקבל מתנה 100 ₪ ליתרת חשבון.
למחלקה `Branch` (סניף) תכונות הבאות:
•מספר סניף – `branchNum`, מטיפוס שלם – `int`
•מערך חשבונות – `accounts` – מערך הפניות לעצמים מסוג `Account`
•מספר חשבונות בפועל – `current`, מטיפוס מספר שלם – `int`
בעת פתיחת סניף חדש יש ליצור מערך בגודל `maxAccount` (מספר החשבונות המקסימלי בסניף המתקבל כפרמטר) ללא חשבונות בפועל.
כתבו במחלקות `Account` ו-`Branch` פעולות בונות (`constructors`):
public Account(int num, String id)
public Branch(int branchNum, int maxAccount)public Account(int num, string id)
public Branch(int branchNum, int maxAccount)במחלקה `Branch` קיימת פעולה פנימית ליצירת מספר חשבון, המבטיחה שמספר חשבון יהיה ייחודי בסניף. אפשר להשתמש בפעולה זו ולא צריך לממש אותה.
כותרת הפעולה:
public int generateNum()public int GenerateNum()כדי למשוך לקוחות חדשים החליטה הנהלת הבנק על מבצע הבא: כל לקוח חדש (זה שאין לו חשבון בסניף) מקבל מתנה של 500 ₪ בעת פתיחת חשבון (אם ללקוח יש כבר חשבון הוא מקבל מתנה "רגילה" של 100 ₪).
כתבו במחלקה `Branch` פעולה להוספת חשבון חדש:
public void addAccount(String id)public void AddAccount(string id)כאשר לקוח רוצה לעבור מסניף `br1` לסניף `br2` כל החשבונות שלו בסניף `br1` נסגרים (הופכים להיות "לא פעילים") ובסניף `br2` נפתח חשבון חדש עם יתרה השווה לסכום היתרות שהיו לו בסניף הקודם. אין צורך במחיקה חשבונות שנסגרו.
כתבו פעולה חיצונית המבצעת מעבר לקוח מסניף לסניף. כותרת הפעולה:
public static void moveClient(String id, Branch br1, Branch br2)public static void MoveClient(string id, Branch br1, Branch br2)◂ פתרון מלא לשאלה 12
סעיף א
Account: מציבים num ו-id, יתרה 100 ומצב פעיל (true). Branch: מציבים branchNum, יוצרים מערך `new Account[maxAccount]` ו-`current = 0`.
הרעיון: הבנאי קובע את המצב ההתחלתי של העצם לפי תיאור השאלה.
1. Account: מספר החשבון ותעודת הזהות מתקבלים כפרמטרים. בעת פתיחת חשבון הלקוח מקבל מתנה של 100 ₪, ולכן היתרה ההתחלתית 100. חשבון חדש הוא חשבון פעיל, ולכן `isActive = true`.
2. Branch: מספר הסניף מתקבל כפרמטר. יוצרים מערך הפניות בגודל `maxAccount` (כל התאים `null`), ומספר החשבונות בפועל הוא 0.
public Account(int num, String id)
{
this.num = num;
this.id = id;
this.balance = 100; // מתנה בעת פתיחת חשבון
this.isActive = true; // חשבון חדש הוא פעיל
}
public Branch(int branchNum, int maxAccount)
{
this.branchNum = branchNum;
this.accounts = new Account[maxAccount]; // מערך ריק בגודל המקסימלי
this.current = 0; // אין עדיין חשבונות בפועל
}public Account(int num, string id)
{
this.num = num;
this.id = id;
this.balance = 100; // מתנה בעת פתיחת חשבון
this.isActive = true; // חשבון חדש הוא פעיל
}
public Branch(int branchNum, int maxAccount)
{
this.branchNum = branchNum;
this.accounts = new Account[maxAccount]; // מערך ריק בגודל המקסימלי
this.current = 0; // אין עדיין חשבונות בפועל
}תשובה: הבנאים שלמעלה.
סעיף ב
בודקים אם בתאים 0 עד current-1 יש חשבון עם אותו id; יוצרים `new Account(generateNum(), id)` (יתרה 100), ואם הלקוח חדש קובעים יתרה 500; מציבים בתא `accounts[current]` ומגדילים את current.
הרעיון: קודם בודקים אם הלקוח חדש בסניף, ואז יוצרים את החשבון ומוסיפים אותו למקום הפנוי הראשון במערך.
1. האם הלקוח חדש: עוברים רק על החשבונות הקיימים בפועל - התאים 0 עד `current - 1` (שאר התאים הם `null`). אם לאחד מהם תעודת זהות שווה ל-`id` (השוואת מחרוזות בעזרת `equals`), הלקוח אינו חדש.
2. יצירת החשבון: `new Account(generateNum(), id)` - מספר חשבון ייחודי מהפעולה הפנימית. הבנאי מסעיף א' כבר קובע יתרה של 100 ₪ (המתנה ה"רגילה").
3. מתנת מבצע: אם הלקוח חדש - מעדכנים את היתרה ל-500 ₪ (המתנה של המבצע במקום המתנה הרגילה).
4. הוספה: החשבונות תופסים את התאים 0 עד `current - 1`, ולכן התא הפנוי הראשון הוא `accounts[current]`. מציבים בו את החשבון ומגדילים את `current` ב-1.
public void addAccount(String id)
{
boolean isNew = true; // האם הלקוח חדש בסניף
for (int i = 0; i < current; i++)
{
if (accounts[i].getId().equals(id))
isNew = false;
}
Account acc = new Account(generateNum(), id); // יתרה 100
if (isNew)
acc.setBalance(500); // מתנה ללקוח חדש
accounts[current] = acc;
current++;
}public void AddAccount(string id)
{
bool isNew = true; // האם הלקוח חדש בסניף
for (int i = 0; i < current; i++)
{
if (accounts[i].GetId() == id)
isNew = false;
}
Account acc = new Account(GenerateNum(), id); // יתרה 100
if (isNew)
acc.SetBalance(500); // מתנה ללקוח חדש
accounts[current] = acc;
current++;
}דוגמה: בסניף ריק: `addAccount("111")` יוצר חשבון עם 500 ₪, `addAccount("222")` - חשבון עם 500 ₪, ו-`addAccount("111")` נוסף - חשבון עם 100 ₪ (ללקוח 111 כבר יש חשבון).
תשובה: הפעולה שלמעלה.
סעיף ג
עוברים על החשבונות של br1; לכל חשבון פעיל של id מוסיפים את היתרה לסכום ומסמנים אותו לא פעיל; אחר כך `br2.addAccount(id)` וקובעים ליתרת החשבון החדש (בתא `current-1`) את הסכום - במקום המתנה.
הרעיון: הפעולה חיצונית, ולכן כל הגישה לסניפים ולחשבונות היא דרך פעולות get/set. העבודה מתחלקת לשני שלבים: סגירת החשבונות ב-`br1` תוך סכימת היתרות, ופתיחת חשבון אחד ב-`br2` עם הסכום.
1. סגירה ב-br1: מקבלים את מערך החשבונות `br1.getAccounts()` ועוברים על התאים 0 עד `br1.getCurrent() - 1`. לכל חשבון של הלקוח (`getId().equals(id)`) שעדיין פעיל: מוסיפים את היתרה ל-`sum` ומסמנים אותו כלא פעיל (`setIsActive(false)`). חשבונות שכבר נסגרו קודם אינם נספרים - היתרה שלהם כבר הועברה.
2. פתיחה ב-br2: אם נמצא לפחות חשבון אחד, פותחים חשבון בעזרת `br2.addAccount(id)` - כך מתקבל מספר חשבון ייחודי והחשבון נכנס למקום הנכון במערך. הפעולה `addAccount` נותנת מתנה (100 או 500), אבל ללקוח עובר לא מגיעה מתנה, ולכן מיד אחר כך קובעים את היתרה של החשבון החדש לסכום `sum`. החשבון החדש הוא האחרון שנוסף, כלומר בתא `br2.getCurrent() - 1`.
public static void moveClient(String id, Branch br1, Branch br2)
{
Account[] acc1 = br1.getAccounts();
double sum = 0; // סכום היתרות בסניף br1
boolean found = false;
for (int i = 0; i < br1.getCurrent(); i++)
{
if (acc1[i].getId().equals(id) && acc1[i].getIsActive())
{
sum += acc1[i].getBalance();
acc1[i].setIsActive(false); // סגירת החשבון
found = true;
}
}
if (found)
{
br2.addAccount(id); // פתיחת חשבון ב-br2
Account[] acc2 = br2.getAccounts();
acc2[br2.getCurrent() - 1].setBalance(sum); // היתרה במקום המתנה
}
}public static void MoveClient(string id, Branch br1, Branch br2)
{
Account[] acc1 = br1.GetAccounts();
double sum = 0; // סכום היתרות בסניף br1
bool found = false;
for (int i = 0; i < br1.GetCurrent(); i++)
{
if (acc1[i].GetId() == id && acc1[i].GetIsActive())
{
sum += acc1[i].GetBalance();
acc1[i].SetIsActive(false); // סגירת החשבון
found = true;
}
}
if (found)
{
br2.AddAccount(id); // פתיחת חשבון ב-br2
Account[] acc2 = br2.GetAccounts();
acc2[br2.GetCurrent() - 1].SetBalance(sum); // היתרה במקום המתנה
}
}דוגמה: ללקוח 111 ב-br1 שני חשבונות פעילים עם 700 ₪ ו-100 ₪. אחרי `moveClient("111", br1, br2)` שני החשבונות ב-br1 לא פעילים, וב-br2 נוסף חשבון פעיל של 111 עם יתרה של 800 ₪ בדיוק.
תשובה: הפעולה שלמעלה.
שאלה 13 · מספר מיוחד, מערך מיוחד ומערך דו-ממדי
נתונות הגדרות הבאות:
•מספר שלם וחיובי נקרא "מספר מיוחד" אם ספרות המספר (משמאל לימין) מהוות סידרה עולה.
לדוגמה:
המספרים 12, 138, 2689, 4 הם "מספרים מיוחדים".
המספרים 43, 176, -123, 33 הם לא "מספרים מיוחדים"
•מערך חד-ממדי של מספרים שלמים (חיוביים, שליליים ואפסים) נקרא "מיוחד" אם יש בו לפחות "מספר מיוחד" אחד וערכי המערך ממוינים בסדר עולה.
•מערך דו-ממדי של מספרים שלמים נקרא "מיוחד" אם כל השורות שלו מהוות מערכים "מיוחדים".
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים ובודקת האם הוא מערך "מיוחד".
אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 13
סעיף א
שלוש פעולות: isSpecialNum (ספרות עולות ממש, רק למספר חיובי), isSpecialArray (ממוין בסדר עולה וכולל לפחות מספר מיוחד אחד), isSpecialMat (כל שורה מיוחדת).
הרעיון: מפרקים את הבעיה לפי שלוש ההגדרות, ופעולה לכל הגדרה:
1. `isSpecialNum(num)` - מספר מיוחד:
•מספר שאינו חיובי (שלילי או 0) אינו מיוחד.
- "סדרה עולה משמאל לימין" פירושה שכל ספרה קטנה ממש מהספרה שמימינה (לכן 33 אינו מיוחד). מפרקים את המספר מימין: שומרים את הספרה הימנית `right`, ובכל סיבוב לוקחים את הספרה שמשמאלה `left`. אם `left >= right` - הסדרה אינה עולה, ומוחזר `false`.
•מספר חד-ספרתי (למשל 4) מיוחד - הלולאה לא מתבצעת ומוחזר `true`.
2. `isSpecialArray(arr)` - מערך חד-ממדי מיוחד: במעבר אחד בודקים את שני התנאים:
•ממוין בסדר עולה: כל איבר גדול מקודמו (`arr[i] > arr[i-1]`); אם לא - `false` מיד.
•יש לפחות מספר מיוחד אחד: דגל `hasSpecial` שהופך ל-`true` כשנמצא מספר מיוחד.
בסוף מחזירים את הדגל.
3. `isSpecialMat(mat)` - מערך דו-ממדי מיוחד: עוברים על השורות; כל שורה `mat[i]` היא מערך חד-ממדי. אם שורה אחת אינה מיוחדת - `false`; אחרת `true`.
ב-C# המערך הדו-ממדי הוא `int[,]`, ולכן במקום להעביר שורה כמערך מעבירים את מספר השורה, ומספר העמודות מתקבל מ-`GetLength(1)`.
דוגמה: `{{-5, 0, 12, 40}, {3, 7, 100}}`: השורה הראשונה ממוינת וכוללת את 12; השורה השנייה ממוינת וכוללת את 3 (וגם 7) - המערך מיוחד. לעומת זאת `{{-5, 12, 12}}` אינו ממוין בסדר עולה (12 חוזר), ולכן אינו מיוחד.
public static boolean isSpecialNum(int num)
{
if (num <= 0) // רק מספר חיובי יכול להיות מיוחד
return false;
int right = num % 10; // הספרה הימנית שנבדקה
num /= 10;
while (num > 0)
{
int left = num % 10; // הספרה שמשמאלה
if (left >= right) // הסדרה אינה עולה
return false;
right = left;
num /= 10;
}
return true;
}
public static boolean isSpecialArray(int[] arr)
{
boolean hasSpecial = false;
for (int i = 0; i < arr.length; i++)
{
if (i > 0 && arr[i] <= arr[i - 1]) // המערך לא ממוין בסדר עולה
return false;
if (isSpecialNum(arr[i]))
hasSpecial = true;
}
return hasSpecial;
}
public static boolean isSpecialMat(int[][] mat)
{
for (int i = 0; i < mat.length; i++)
{
if (!isSpecialArray(mat[i])) // שורה שאינה "מיוחדת"
return false;
}
return true;
}public static bool IsSpecialNum(int num)
{
if (num <= 0) // רק מספר חיובי יכול להיות מיוחד
return false;
int right = num % 10; // הספרה הימנית שנבדקה
num /= 10;
while (num > 0)
{
int left = num % 10; // הספרה שמשמאלה
if (left >= right) // הסדרה אינה עולה
return false;
right = left;
num /= 10;
}
return true;
}
public static bool IsSpecialRow(int[,] mat, int row)
{
bool hasSpecial = false;
for (int j = 0; j < mat.GetLength(1); j++)
{
if (j > 0 && mat[row, j] <= mat[row, j - 1]) // השורה לא ממוינת בסדר עולה
return false;
if (IsSpecialNum(mat[row, j]))
hasSpecial = true;
}
return hasSpecial;
}
public static bool IsSpecialMat(int[,] mat)
{
for (int i = 0; i < mat.GetLength(0); i++)
{
if (!IsSpecialRow(mat, i)) // שורה שאינה "מיוחדת"
return false;
}
return true;
}תשובה: הפעולה `isSpecialMat` שלמעלה (עם פעולות העזר).
סעיף ב
: n שורות, m עמודות, d מספר הספרות המרבי של איבר.
נסמן: - מספר השורות, - מספר העמודות, - מספר הספרות המרבי של איבר במערך.
1. `isSpecialNum` - סיבוב אחד לכל ספרה: .
2. `isSpecialArray` על שורה - איברים, ולכל אחד השוואה לקודמו () ובדיקת "מספר מיוחד" (): .
3. `isSpecialMat` - במקרה הגרוע בודקים את כל השורות: .
אם מתייחסים למספר הספרות כחסום (מספר `int` הוא לכל היותר בן 10 ספרות), הסיבוכיות היא - מעבר יחיד על כל איברי המערך.
תשובה: , ובפועל .
שאלה 14 · רקורסיה: מיקום המינימום ומיון בסדר יורד
נתונה הפעולה הרקורסיביות `secret`:
public static int secret(int[] a)
{
return secret(a,a.length-1);
}
public static int secret(int[] a, int i)
{
if(i == 0) return 0;
int k = secret(a,i-1);
if(a[i] <a [k])
return i;
return k;
}public static int Secret(int[] a)
{
return Secret(a, a.Length-1);
}
public static int Secret(int[] a, int i)
{
if(i == 0) return 0;
int k = Secret(a, i-1);
if(a[i] < a[k])
return i;
return k;
}נתון המערך הבא של מספרים שלמים:
int[] a = {3,5,1,2,10,9}עקבו אחרי זימון `secret(a)` רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `secret(a)` באופן כללי?
נתונה הפעולה הרקורסיביות `mystery` הבאה
public static void mystery(int[] a)
{
mystery(a, a.length-1);
}
public static void mystery(int[] a, int i)
{
if(i > 0)
{
int k = secret(a,i);
int temp = a[i];
a[i] = a[k];
a[k] = temp;
mystery(a, i-1);
}
}public static void Mystery(int[] a)
{
Mystery(a, a.Length-1);
}
public static void Mystery(int[] a, int i)
{
if(i > 0)
{
int k = Secret(a,i);
int temp = a[i];
a[i] = a[k];
a[k] = temp;
Mystery(a, i-1);
}
}נתון המערך הבא של מספרים שלמים:
int[] a = {3,5,1,2,10,9}עקבו אחרי זימון `mystery(a)` ורשמו את תוצאות הזימון.
מה מבצעת הפעולה `mystery(a)` באופן כללי?
◂ פתרון מלא לשאלה 14
סעיף א
`secret(a)` מחזירה 2.
הרעיון: `secret(a)` קוראת ל-`secret(a, 5)`. כל זימון `secret(a, i)` קורא קודם ל-`secret(a, i-1)`, ולכן הקריאות יורדות עד `i = 0` (תנאי העצירה, מוחזר 0), ואז הערכים חוזרים מלמטה למעלה. בכל שלב בחזרה משווים את `a[i]` ל-`a[k]`: אם `a[i]` קטן יותר מוחזר `i`, אחרת מוחזר `k`.
`a = {3,5,1,2,10,9}` (מקומות 0-5).
(הטבלה מסודרת לפי סדר החזרה מהרקורסיה: `secret(a, 5)` נקראה ראשונה אבל מסתיימת אחרונה.)
תשובה: `secret(a)` מחזירה 2 - המקום של הערך 1.
סעיף ב
מחזירה את המקום (האינדקס) של הערך הקטן ביותר במערך (במקרה של כמה מופעים - המופע הראשון).
`secret(a, i)` מחזירה את המקום של האיבר הקטן ביותר בקטע `a[0..i]`:
1. עבור `i = 0` יש איבר אחד, והוא הקטן ביותר - מוחזר 0.
2. אם `k` הוא המקום של המינימום בקטע `a[0..i-1]`, אז המינימום של `a[0..i]` הוא `a[i]` אם הוא קטן ממש מ-`a[k]`, ואחרת נשאר `a[k]`. לכן בשוויון נשמר המקום המוקדם יותר.
`secret(a)` מפעילה זאת על כל המערך (`i = a.length - 1`).
תשובה: הפעולה מחזירה את המקום של הערך המינימלי במערך (אם המינימום מופיע כמה פעמים - את המקום הראשון שלו).
סעיף ג
בסוף המערך הוא `{10, 9, 5, 3, 2, 1}`.
הרעיון: `mystery(a, i)` מוצאת בעזרת `secret(a, i)` את המקום `k` של האיבר הקטן ביותר בקטע `a[0..i]`, מחליפה בינו לבין `a[i]` (כך הקטן ביותר עובר לסוף הקטע), וממשיכה ברקורסיה על הקטע הקצר יותר `a[0..i-1]`. הרקורסיה נעצרת כש-`i = 0`.
`mystery(a)` קוראת ל-`mystery(a, 5)`:
תשובה: אחרי הזימון המערך הוא `{10, 9, 5, 3, 2, 1}`.
סעיף ד
ממיינת את המערך בסדר יורד (מיון בחירה: בכל שלב הקטן ביותר מועבר לסוף הקטע).
בכל זימון `mystery(a, i)` האיבר הקטן ביותר בקטע `a[0..i]` מועבר למקום `i`. בזימון הראשון הקטן ביותר בכל המערך עובר למקום האחרון, בזימון הבא הקטן ביותר מבין הנותרים עובר למקום שלפניו, וכן הלאה. זהו מיון בחירה (Selection Sort) שבונה את המערך מהסוף, ולכן בסופו האיברים מסודרים מהגדול לקטן.
תשובה: הפעולה ממיינת את המערך `a` בסדר יורד.