מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2023 מועד ב'
הנדסת תוכנה · סמל 97104 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2023 מועד ב', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 13)
בכל מבחן 12 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 7-9: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 10-12: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 11 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטה עד מספר תלת ספרתי, מקסימום ומינימום
כתבו קטע קוד שקולט מספרים שלמים עד שייקלט מספר תלת ספרתי. יש להדפיס את מספר הגדול ביותר שנקלט ואת מספר הקטן שנקלט.
◂ פתרון מלא לשאלה 1
פתרון
לולאת `while` שקולטת מספרים כל עוד המספר אינו תלת ספרתי ( או ), ומעדכנת את `max` ואת `min` לכל מספר שנקלט (כולל המספר התלת ספרתי שעוצר את הקלט).
הרעיון: לא ידוע מראש כמה מספרים ייקלטו, ולכן משתמשים בלולאת `while` שתנאי העצירה שלה הוא "נקלט מספר תלת ספרתי".
1. קולטים את המספר הראשון לפני הלולאה, ומאתחלים בו גם את `max` וגם את `min`. כך אין צורך בערך התחלתי "מלאכותי": המספר הראשון הוא כרגע גם הגדול ביותר וגם הקטן ביותר.
2. מספר הוא תלת ספרתי אם הערך המוחלט שלו בין ל- (גם נחשב תלת ספרתי). לכן הלולאה ממשיכה כל עוד `Math.abs(num) < 100 || Math.abs(num) > 999`.
3. בכל סיבוב קולטים מספר חדש ומשווים אותו ל-`max` ול-`min`, ומעדכנים אם צריך.
4. גם המספר התלת ספרתי שעוצר את הלולאה נקלט, ולכן הוא נבדק לפני שהתנאי נבדק שוב ונכלל בחישוב.
5. אחרי הלולאה מדפיסים את שני הערכים.
int num = in.nextInt();
int max = num;
int min = num;
while (Math.abs(num) < 100 || Math.abs(num) > 999)
{
num = in.nextInt();
if (num > max)
max = num;
if (num < min)
min = num;
}
System.out.println("max = " + max);
System.out.println("min = " + min);int num = int.Parse(Console.ReadLine());
int max = num;
int min = num;
while (Math.Abs(num) < 100 || Math.Abs(num) > 999)
{
num = int.Parse(Console.ReadLine());
if (num > max)
max = num;
if (num < min)
min = num;
}
Console.WriteLine("max = " + max);
Console.WriteLine("min = " + min);דוגמה: עבור הקלט : המספר הוא בן ארבע ספרות ולכן הקליטה ממשיכה; תלת ספרתי ועוצר את הלולאה. יודפס `max = 1000` ו-`min = -40`.
תשובה: קטע הקוד שלמעלה.
שאלה 2 · בדיקת מחרוזת תקינה וספירת מחרוזות תקינות
מחרוזת "תקינה" היא מחרוזת העונה לשני תנאים הבאים:
•אורך המחרוזת אי-זוגי.
•תו ראשון זהה לתו אמצעי וזהה לתו האחרון.
לדוגמה: המחרוזת "AbbAc1A" היא "מחרוזת תקינה".
כתבו פעולה המקבלת מחרוזת ובודקת אם היא "מחרוזת תקינה".
אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר עריך `false`.
כותרת הפעולה:
public static boolean isValid (String s)public static bool IsValid (string s)כתבו קטע קוד הקולט 23 מחרוזות. הקטע יחשב וידפיס מספר "מחרוזות תקינות" ומספר מחרוזות לא תקינות. יש להשתמש בפעולה שכתבתם בסעיף א'.
◂ פתרון מלא לשאלה 2
סעיף א
אם האורך זוגי מחזירים `false`; אחרת מחזירים `true` רק אם `s.charAt(0)`, `s.charAt(len/2)` ו-`s.charAt(len-1)` שווים.
הרעיון: בודקים את שני התנאים לפי הסדר.
1. אם אורך המחרוזת `len` זוגי (`len % 2 == 0`) – המחרוזת לא תקינה, ומחזירים `false` מיד.
2. באורך אי-זוגי יש תו אמצעי אחד, במקום `len / 2` (חילוק שלם). לדוגמה ב-"AbbAc1A" האורך , והתו האמצעי במקום הוא `'A'`.
3. התו הראשון במקום והאחרון במקום `len - 1`. מחזירים `true` רק אם שלושת התווים שווים.
בדוגמה: התו הראשון `'A'`, האמצעי (מקום 3) `'A'`, האחרון (מקום 6) `'A'` – המחרוזת תקינה.
public static boolean isValid(String s)
{
int len = s.length();
if (len % 2 == 0)
return false;
char first = s.charAt(0);
char middle = s.charAt(len / 2);
char last = s.charAt(len - 1);
return first == middle && middle == last;
}public static bool IsValid(string s)
{
int len = s.Length;
if (len % 2 == 0)
return false;
char first = s[0];
char middle = s[len / 2];
char last = s[len - 1];
return first == middle && middle == last;
}תשובה: הפעולה `isValid` שלמעלה.
סעיף ב
לולאה של סיבובים: בכל סיבוב קולטים מחרוזת, מזמנים `isValid` ומגדילים את המונה המתאים; בסוף מדפיסים את שני המונים.
הרעיון: מספר המחרוזות ידוע (), ולכן משתמשים בלולאת `for`. מחזיקים שני מונים.
1. מאתחלים `valid = 0` ו-`notValid = 0`.
2. בכל אחד מ- הסיבובים קולטים מחרוזת ומזמנים את `isValid` מסעיף א'.
3. אם הפעולה החזירה `true` – מגדילים את `valid`, אחרת – את `notValid`.
4. אחרי הלולאה מדפיסים את שני המונים (סכומם תמיד ).
int valid = 0, notValid = 0;
for (int i = 0; i < 23; i++)
{
String str = in.next();
if (isValid(str))
valid++;
else
notValid++;
}
System.out.println("valid: " + valid);
System.out.println("not valid: " + notValid);int valid = 0, notValid = 0;
for (int i = 0; i < 23; i++)
{
string str = Console.ReadLine();
if (IsValid(str))
valid++;
else
notValid++;
}
Console.WriteLine("valid: " + valid);
Console.WriteLine("not valid: " + notValid);תשובה: קטע הקוד שלמעלה.
שאלה 3 · בדיקת מערך מאוזן והדפסתו בהתאם
מערך של מספרים שלמים נקרא "מערך מאוזן" אם הוא עונה על תנאים הבאים:
•כמות האיברים החיוביים שווה לכמות האיברים השליליים.
•המערך לא כולל אפסים.
כתבו פעולה המקבלת מערך של מספרים שלמים. אם המערך מאוזן יש להדפיס אותו מתחילתו ועד סופו בשורה אחת, ולא – יש להדפיס אותו בסדר הפוך (מסוף המערך להתחלה).
◂ פתרון מלא לשאלה 3
פתרון
סופרים חיוביים ושליליים ובודקים אם יש אפס; אם `pos == neg` ואין אפס – מדפיסים מההתחלה לסוף, אחרת – מהסוף להתחלה.
הרעיון: מעבר אחד על המערך אוסף את כל המידע הדרוש לבדיקה, ואחריו מעבר הדפסה בכיוון המתאים.
1. מונים: `pos` (חיוביים), `neg` (שליליים), ודגל `hasZero` שמסמן אם נמצא אפס.
2. עוברים על כל האיברים: איבר גדול מ- מגדיל את `pos`, קטן מ- מגדיל את `neg`, ואחרת (שווה ל-) מדליקים את `hasZero`.
3. המערך מאוזן אם `pos == neg` וגם `hasZero` כבה.
4. מאוזן – לולאה מ- עד `length - 1`; לא מאוזן – לולאה מ-`length - 1` עד . בשני המקרים ההדפסה בשורה אחת (`print`), ובסוף ירידת שורה.
public static void printBalanced(int[] arr)
{
int pos = 0, neg = 0;
boolean hasZero = false;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] > 0)
pos++;
else if (arr[i] < 0)
neg++;
else
hasZero = true;
}
if (pos == neg && !hasZero)
{
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
else
{
for (int i = arr.length - 1; i >= 0; i--)
System.out.print(arr[i] + " ");
}
System.out.println();
}public static void PrintBalanced(int[] arr)
{
int pos = 0, neg = 0;
bool hasZero = false;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > 0)
pos++;
else if (arr[i] < 0)
neg++;
else
hasZero = true;
}
if (pos == neg && !hasZero)
{
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " ");
}
else
{
for (int i = arr.Length - 1; i >= 0; i--)
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}•`{3, -1, 5, -7}`: שני חיוביים, שני שליליים, אין אפס – יודפס `3 -1 5 -7`.
•`{3, -1, 5, 7}`: שלושה חיוביים ושלילי אחד – יודפס בסדר הפוך `7 5 -1 3`.
•`{3, -1, 0, 5, -7}`: יש אפס – יודפס בסדר הפוך `-7 5 0 -1 3`.
תשובה: הפעולה שלמעלה. סיבוכיות .
שאלה 4 · מחלקת משלוח פרחים: בנאי וחישוב פיצוי
חברת "פרחי הארץ" מגדלת פרחים ושולחת אותם למכירה בחוץ לארץ.
נתונה מחלקה `FlowerPackage` המייצגת משלוח פרחים המיועד לשליחה לחו"ל. למחלקה יש את התכונות הבאות:
•`type` – סוג הפרח, מטיפוס מחרוזת, `String`.
•`num` – מספר פרחים במשלוח, מטיפוס מספר שלם, `int`.
•`time` – מספר שעות שניתן להחזיק את הפרחים ללא מים, מטיפוס מספר שלם `int`.
•`price` – מחיר פרח בודד, מטיפוס מספר ממשי `double`.
במחלקה הוגדרה פעולה בונה (בנאי) המקבל פרמטרים לכל התכונות, פעולות `set/get` לכל התכונות וגם פעולה `toString()`
כתבו פעולה בונה המקבלת סוג פרח ומחיר. הפעולה מייצרת משלוח סטנדרטי של 2,000 פרחים. זמן סטנדרטי שניתן להחזיק את הפרחים ללא מים – 12 שעות.
עקב בעיות לוגיסטיות, חברת התעופה מציעה מסלול טיסה ארוך יותר. חלק מהמשלוחים לא ישרדו טיסה ארוכה ואז אי אפשר יהיה למכור את הפרחים.
"פרחי הארץ" תדרוש מחברת התעופה פיצוי על ההפסד הכספי.
כתבו פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג `FlowerPackage` בשם `arr` ואורך הטיסה `flyTime`. הפעולה תדפיס פרטי המשלוחים שלא יהיו תקינים. פעולה גם תחשב ותדפיס סכום ש"פרחי הארץ" הפסידה.
כותרת העולה:
public static void compensation(FlowerPackage[] arr, int flyTime)public static void Compensation(FlowerPackage[] arr, int flyTime)הנחה: כל תא במערך מכיל הפניה לעצם מסוג `FlowerPackage` ואין תאים במערך שערכם שווה ל-`null`.
◂ פתרון מלא לשאלה 4
סעיף א
בנאי `FlowerPackage(String type, double price)` שמציב את שני הפרמטרים, ו-`num = 2000`, `time = 12`.
הרעיון: בנאי נוסף (העמסה – אותו שם, רשימת פרמטרים אחרת). שתי תכונות מקבלות את ערכי הפרמטרים, ושתי האחרות מקבלות את הערכים הסטנדרטיים הקבועים.
1. `type` ו-`price` – מהפרמטרים.
2. `num = 2000` – משלוח סטנדרטי.
3. `time = 12` – זמן סטנדרטי ללא מים.
הבנאי נכתב בתוך המחלקה `FlowerPackage`:
public FlowerPackage(String type, double price)
{
this.type = type;
this.price = price;
this.num = 2000; // משלוח סטנדרטי
this.time = 12; // זמן סטנדרטי ללא מים (שעות)
}public FlowerPackage(string type, double price)
{
this.type = type;
this.price = price;
this.num = 2000; // משלוח סטנדרטי
this.time = 12; // זמן סטנדרטי ללא מים (שעות)
}תשובה: הבנאי שלמעלה.
סעיף ב
עוברים על המערך; משלוח עם `getTime() < flyTime` לא ישרוד – מדפיסים אותו ומוסיפים להפסד `getNum() * getPrice()`; בסוף מדפיסים את ההפסד.
הרעיון: משלוח לא ישרוד את הטיסה אם הזמן שאפשר להחזיק בו את הפרחים בלי מים קצר מאורך הטיסה: `time < flyTime`. (אם `time == flyTime` הפרחים מחזיקים בדיוק עד הנחיתה, ולכן המשלוח נחשב תקין.)
1. מאתחלים `loss = 0` (מטיפוס `double`, כי המחיר ממשי).
2. עוברים על כל תאי המערך. הפעולה חיצונית, ולכן ניגשים לתכונות דרך פעולות ה-`get`.
3. למשלוח שאינו תקין: מדפיסים את פרטיו (הדפסת העצם מזמנת את `toString()`), ומוסיפים להפסד את שווי המשלוח – מספר הפרחים כפול מחיר פרח: `getNum() * getPrice()`.
4. אחרי הלולאה מדפיסים את סכום ההפסד.
public static void compensation(FlowerPackage[] arr, int flyTime)
{
double loss = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getTime() < flyTime)
{
System.out.println(arr[i]);
loss += arr[i].getNum() * arr[i].getPrice();
}
}
System.out.println("Loss: " + loss);
}public static void Compensation(FlowerPackage[] arr, int flyTime)
{
double loss = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetTime() < flyTime)
{
Console.WriteLine(arr[i].ToString());
loss += arr[i].GetNum() * arr[i].GetPrice();
}
}
Console.WriteLine("Loss: " + loss);
}דוגמה: מערך עם המשלוחים (ורדים, 2000 פרחים, 12 שעות, 1.5), (צבעונים, 1000, 20, 2.0), (חבצלות, 500, 10, 3.0), (אירוסים, 300, 15, 4.0), וטיסה של 15 שעות. לא ישרדו הוורדים () והחבצלות (); האירוסים () שורדים. ההפסד: .
תשובה: הפעולה `compensation` שלמעלה.
שאלה 5 · מעקב: ספירת ספרות אי-זוגיות ובחירת איבר
נתונה הפעולה `secret` המקבלת כפרמטר מספר שלם וחיובי `num`.
public static int secret(int num)
{
int res1 = 0, res2 = 0;
while (num > 0)
{
res1++;
if (num%2==0)
res2++;
num = num /10;
}
return res1 - res2;
}public static int Secret(int num)
{
int res1 = 0, res2 = 0;
while (num > 0)
{
res1++;
if (num % 2 == 0)
res2++;
num = num /10;
}
return res1 - res2;
}עקבו בעזרת טבלת המעקב אחרי ביצוע הפעולה עבור `num = 37245` ורשמו מה תחזיר הפעולה.
תנו דוגמה למספר שלם וחיובי `num > 1000`, שעבורו הפעולה תחזיר 0.
מה מבצעת הפעולה `secret` עבור מספר `num` שלם וחיובי כלשהו?
נתונה הפעולה `sod()` הבאה:
public static int sod(int[] arr)
{
int res = 0;
for (int i = 1; i < arr.length; i++)
{
if (secret(arr[i]) <= secret(arr[res]))
res = i;
}
return arr[res];
}public static int Sod(int[] arr)
{
int res = 0;
for (int i = 1; i < arr.Length; i++)
{
if (Secret(arr[i]) < Secret(arr[res]))
res = i;
}
return arr[res];
}עקבו באמצעות טבלת מעקב אחר ביצוע הפעולה `sod()` עבור המערך:
int[] arr = {7245, 64, 14783, 32, 824, 199 }מה מבצעת הפעולה `sod` באופן כללי עבור מערך כלשהו של מספרים שלמים וחיוביים?
◂ פתרון מלא לשאלה 5
סעיף א
הפעולה תחזיר .
בכל סיבוב `res1` גדל ב- (סופרים ספרה), `res2` גדל אם `num` זוגי (כלומר אם ספרת האחדות זוגית), ואחר כך מורידים את ספרת האחדות ב-`num = num / 10`.
כעת `num = 0`, התנאי `num > 0` לא מתקיים והלולאה מסתיימת.
מוחזר `res1 - res2` .
תשובה: הפעולה תחזיר .
למשל (כל הספרות זוגיות).
הפעולה מחזירה (מספר הספרות) פחות (מספר הספרות הזוגיות). התוצאה רק כאשר כל הספרות זוגיות.
דוגמה: . כל ארבע הספרות זוגיות, ולכן `res1` ו-`res2` , ומוחזר . (גם או מתאימים.)
תשובה: `num = 2468`.
מחזירה את מספר הספרות האי-זוגיות של `num`.
•בכל סיבוב מטפלים בספרה אחת (ספרת האחדות) ומסירים אותה ב-`num / 10`, ולכן `res1` סופר את כל הספרות של `num`.
•זוגיות של מספר נקבעת לפי ספרת האחדות שלו, ולכן הבדיקה `num % 2 == 0` בודקת אם הספרה הנוכחית זוגית, ו-`res2` סופר את הספרות הזוגיות.
•ההפרש `res1 - res2` הוא מספר הספרות האי-זוגיות.
תשובה: הפעולה מחזירה את מספר הספרות האי-זוגיות במספר `num`.
סעיף ב
Java (תנאי `<=`): הפעולה מחזירה . C# (תנאי `<`): הפעולה מחזירה .
לפי סעיף א, `secret(x)` הוא מספר הספרות האי-זוגיות של `x`:
`secret(7245)` (7, 5), `secret(64)` , `secret(14783)` (1, 7, 3), `secret(32)` (3), `secret(824)` , `secret(199)` (1, 9, 9).
`res` הוא אינדקס של "המועמד" הנוכחי; מתחילים ב-`res = 0`. בכל סיבוב משווים את האיבר במקום `i` לאיבר במקום `res`.
בשאלון יש הבדל בין הגרסאות: ב-Java התנאי הוא `<=` (מעדכנים גם בשוויון), וב-C# התנאי הוא `<` (מעדכנים רק כשקטן ממש). לכן הטבלה מראה את שתי הגרסאות.
•Java: בסוף `res = 4`, ומוחזר `arr[4]` .
•C#: בסוף `res = 1`, ומוחזר `arr[1]` .
ההבדל נובע מהשוויון ב-: גם ל- וגם ל- אין ספרות אי-זוגיות; עם `<=` המאוחר מחליף את הקודם, ועם `<` הקודם נשאר.
תשובה: ב-Java הפעולה מחזירה ; ב-C# הפעולה מחזירה .
מחזירה את האיבר שיש בו הכי מעט ספרות אי-זוגיות; אם יש כמה כאלה – ב-Java (`<=`) את האחרון מביניהם, ב-C# (`<`) את הראשון מביניהם.
•`res` שומר את האינדקס של האיבר שיש בו, עד כה, הכי מעט ספרות אי-זוגיות (הערך של `secret`). זהו חיפוש מינימום רגיל, רק שמשווים את ערכי `secret` ולא את האיברים עצמם, ומחזירים את האיבר (`arr[res]`) ולא את האינדקס.
•Java: איבר חדש מחליף את המועמד אם יש לו מספר קטן או שווה של ספרות אי-זוגיות, ולכן בתיקו נבחר האיבר המאוחר יותר (בדוגמה החליף את ).
•C#: החלפה רק כשהמספר קטן ממש, ולכן בתיקו נשאר האיבר הראשון (בדוגמה ).
•המערך עצמו אינו משתנה.
תשובה: הפעולה מחזירה את האיבר שמספר הספרות האי-זוגיות בו הוא הקטן ביותר; אם יש כמה איברים כאלה – ב-Java את האחרון מביניהם, וב-C# את הראשון מביניהם.
שאלה 6 · ניתוח פעולות על מחרוזות ומערך מחרוזות
נתונה הפעולה `secret()` הבאה המקבלת מחרוזת:
public static boolean secret(String str)
{
int i = 0;
while(i < str.length()/2)
{
if (str.charAt(i) < 'a' || str.charAt(i) > 'z')
{
return false;
}
i++;
}
if(str.length()%2!=0) i++;
while(i < str.length())
{
if (str.charAt(i) < 'A' || str.charAt(i) > 'Z')
{
return false;
}
i++;
}
return true;
}public static bool Secret(string str)
{
int i = 0;
while(i < str.Length/2)
{
if (str[i] < 'a' || str[i]> 'z')
{
return false;
}
i++;
}
if(str.Length%2!=0) i++;
while(i < str.Length)
{
if (str[i] < 'A' || str[i] > 'Z')
{
return false;
}
i++;
}
return true;
}תנו דוגמה למחרוזת באורך של שישה תווים שעבורה הפעולה `secret` תחזיר ערך `true`.
נתונה הטענה הבאה: אם זימון הפעולה `secret(str)` מחזיר ערך `true`, במחרוזת `str` יש רק אותיות (גדולות או קטנות). האם הטענה נכונה? הסבירו את תשובתכם.
נתונה הפעולה `mystery` המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה `secret`:
public static boolean mystery(String[] arr)
{
int i = 0;
int j = arr.length - 1;
while (i < j)
{
if (secret(arr[i]) != secret(arr[j]))
return false;
i++;
j--;
}
return true;
}public static bool Mystery(string[] arr)
{
int i = 0;
int j = arr.Length - 1;
while (i < j)
{
if (Secret(arr[i]) != Secret(arr[j]))
return false;
i++;
j--;
}
return true;
}תנו דוגמה למערך `arr` בגודל שישה תאים שעבורו הפעולה `mystery` תחזיר ערך `true`.
נתונה הטענה הבאה: אם זימון הפעולה `mystery(arr)` מחזיר ערך `true`, המערך `arr` לא כולל זוג מחרוזות זהות אשר נמצאות בתאים סמוכים. האם הטענה נכונה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
למשל `"abcDEF"`.
מה הפעולה בודקת: נסמן = אורך המחרוזת.
•הלולאה הראשונה עוברת על המקומות עד (המחצית הראשונה) ודורשת שכל תו יהיה אות קטנה `'a'`–`'z'`.
•אם אי-זוגי, מדלגים על התו האמצעי (`i++`) בלי לבדוק אותו.
•הלולאה השנייה עוברת על שאר התווים (המחצית השנייה) ודורשת שכל תו יהיה אות גדולה `'A'`–`'Z'`.
באורך : המקומות – צריכים להיות אותיות קטנות, והמקומות – אותיות גדולות.
עבור `"abcDEF"`: `a`, `b`, `c` קטנות; `D`, `E`, `F` גדולות – הפעולה מחזירה `true`.
תשובה: `"abcDEF"`.
לא נכונה. באורך אי-זוגי התו האמצעי לא נבדק, למשל `secret("ab5CD")` מחזיר `true` אף שיש בה הספרה 5.
הטענה אינה נכונה.
כאשר אורך המחרוזת אי-זוגי, הפקודה `if(str.length()%2!=0) i++;` מדלגת על התו האמצעי, ואף לולאה לא בודקת אותו. לכן התו האמצעי יכול להיות כל תו – ספרה, רווח או סימן.
דוגמה נגדית: `"ab5CD"` (אורך ):
1. הלולאה הראשונה בודקת את המקומות : `'a'`, `'b'` – אותיות קטנות.
2. האורך אי-זוגי, ולכן `i` עובר מ- ל-: התו `'5'` במקום לא נבדק.
3. הלולאה השנייה בודקת את המקומות : `'C'`, `'D'` – אותיות גדולות.
4. מוחזר `true`, אף שבמחרוזת יש את הספרה `5`.
תשובה: הטענה לא נכונה; דוגמה נגדית: `secret("ab5CD")` מחזיר `true`.
סעיף ב
למשל `{"abCD", "hello", "Q", "q", "WORLD", "xyZW"}`.
מה הפעולה בודקת: `i` מתחיל בתחילת המערך ו-`j` בסופו, והם מתקרבים זה לזה. בכל סיבוב משווים את התוצאה של `secret` עבור שני התאים הסימטריים (`arr[i]` ו-`arr[j]`). הפעולה מחזירה `true` אם לכל זוג תאים סימטריים יש אותה תוצאת `secret`, כלומר אם סדרת התוצאות של `secret` היא פלינדרום.
בגודל משווים את הזוגות , , .
עבור `{"abCD", "hello", "Q", "q", "WORLD", "xyZW"}`:
כל הזוגות שווים, ולכן הפעולה מחזירה `true`.
תשובה: `{"abCD", "hello", "Q", "q", "WORLD", "xyZW"}`.
לא נכונה. למשל `{"ab", "ab", "cd", "cd", "ab", "ab"}`: כל התוצאות `false`, הפעולה מחזירה `true`, ויש מחרוזות זהות בתאים סמוכים.
הטענה אינה נכונה. הפעולה משווה רק את תוצאות `secret` של תאים סימטריים (מתחילת המערך ומסופו), ולא בודקת בכלל את היחס בין תאים סמוכים. מחרוזות זהות בתאים סמוכים לא מפריעות לכך.
דוגמה נגדית: `{"ab", "ab", "cd", "cd", "ab", "ab"}`.
•`secret("ab")`: באורך המחצית השנייה היא `'b'`, שאינה אות גדולה, ולכן מוחזר `false`. באותו אופן `secret("cd")` מחזיר `false`.
•כל ששת התאים מחזירים `false`, ולכן בכל הזוגות , , התוצאות שוות, והפעולה מחזירה `true`.
•ועם זאת, בתאים הסמוכים ו- (וגם ו-, ו-) יש מחרוזות זהות.
תשובה: הטענה לא נכונה; דוגמה נגדית: `{"ab", "ab", "cd", "cd", "ab", "ab"}`.
שאלה 7 · מעקב אחר שני מצביעים: ספירת זוגות
נתונה פעולה `what` הבאה. הפעולה מקבלת מערך של מספרים שלמים `arr` ומספר שלם `num`.
המערך ממוין בסדר עולה.
public static int what(int[] arr, int num)
{
int c=0;
int left=0;
int right=arr.length-1;
while(left<right)
{
if(arr[left]+arr[right]>=num)
right--;
else
{
c+=(right - left);
left++;
}
}
return c;
}public static int What(int[] arr, int num)
{
int c=0;
int left=0;
int right=arr.Length-1;
while(left<right)
{
if(arr[left]+arr[right]>=num)
right--;
else
{
c+=(right - left);
left++;
}
}
return c;
}נתון המערך `arr` הבא:
arr:
עקבו בעזרת טבלת המעקב אחרי ביצוע זימון הפעולה `what(arr, 7)`. מה תהייה תוצאת הזימון?
עקבו בעזרת טבלת המעקב אחרי ביצוע זימון הפעולה `what(arr, 26)`. מה תהייה תוצאת הזימון?
מה מבצעת הפעולה `what(arr, num)` באופן כללי עבור מערך של מספרים שלמים ממוין בסדר עולה `arr` ומספר שלם `num`.
מהי הסיבוכיות של הפעולה `what`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
תוצאת הזימון: .
בכל סיבוב מחשבים את הסכום `arr[left] + arr[right]`. אם הוא גדול או שווה ל-`num` – מקטינים את `right`; אחרת מוסיפים ל-`c` את `right - left` ומגדילים את `left`. הלולאה רצה כל עוד `left < right`.
כעת `left = right = 1`, התנאי `left < right` לא מתקיים, ומוחזר `c` .
(אכן, הזוג היחיד שסכומו קטן מ- הוא .)
תשובה: `what(arr, 7)` מחזירה .
סעיף ב
תוצאת הזימון: .
אותו מעקב, עם `num = 26`:
כעת `left = right = 3`, הלולאה מסתיימת ומוחזר `c` .
בדיקה: הזוגות שסכומם קטן מ- הם: עם – (5 זוגות); עם – (4 זוגות); עם – (2 זוגות); כבר לא. סך הכול .
תשובה: `what(arr, 26)` מחזירה .
סעיף ג
מחזירה את מספר זוגות האיברים (במקומות שונים ) שסכומם קטן מ-`num`.
הפעולה סופרת זוגות של איברים במקומות שונים, `arr[i]` ו-`arr[j]` עם , שסכומם קטן מ-`num`.
למה זה עובד (המערך ממוין בסדר עולה):
1. אם `arr[left] + arr[right] < num`, אז גם `arr[left]` עם כל איבר שבין `left+1` ל-`right` נותן סכום קטן מ-`num` (האיברים האלה קטנים או שווים ל-`arr[right]`). אלה בדיוק `right - left` זוגות, ולכן מוסיפים אותם ל-`c`. כל הזוגות של `arr[left]` נספרו, ולכן מקדמים את `left`.
2. אם `arr[left] + arr[right] >= num`, אז גם `arr[right]` עם כל איבר שבין `left` ל-`right-1` נותן סכום גדול או שווה ל-`num` (האיברים האלה גדולים או שווים ל-`arr[left]`). ל-`arr[right]` אין זוג מתאים, ולכן מוותרים עליו ב-`right--`.
כך כל זוג נספר פעם אחת בדיוק.
תשובה: הפעולה מחזירה את מספר הזוגות של איברים במקומות שונים במערך שסכומם קטן מ-`num`.
סעיף ד
, כאשר אורך המערך.
בכל סיבוב של הלולאה בדיוק אחד מהמשתנים זז: `left` גדל ב- או `right` קטן ב-. לכן המרחק `right - left` קטן ב- בכל סיבוב. בהתחלה המרחק , והלולאה נעצרת כשהוא , כלומר מתבצעים בדיוק סיבובים, וכל סיבוב בזמן קבוע.
תשובה: סיבוכיות לינארית, .
שאלה 8 · מחלקת לקוח מים: עדכון קריאה ותשלום
לפי תקנון של רשות המים, חיוב עבור צריכת מים ביתית מתבצע לפי השיטה הבאה:
•צריכת המים נקבעת על פי קריאת מד המים. ההפרש בין הקריאה הנוכחית לקריאה הקודמת קובע את כמות הצריכה.
•תעריפי המים אחידים בכל הארץ וקובעת אותם הרשות הממשלתית למים וביוב. סכום החיוב הוא מכפלה של כמויות המים שנצרכו בתקופת החשבון בתעריפי המים.
•צריכה ביתית כוללת שני תעריפים:
•תעריף מוזל המתייחס לכמות של שבעה מ"ק לנפש המתגוררת ביחידת הדיור
•תעריף גבוה המתייחס ליתרת כמות המים שנצרכה ביחידת הדיור בתקופת החשבון.
אם הצריכה הביתית הייתה 35 מ"ק מים ובדירה מתגוררות ארבע נפשות יש לשלם עבור 7\*4=28 מ"ק לפי התעריף המוזל ועבור 35-28=7 מ"ק לפי התעריף הגבוה.
חברת "מי הארץ" החליטה למחשב את תהליך גביית התשלום. לצורך כך הגדירו את המחלקה לקוח (`Client`) המייצגת יחידת דיור
למחלקה התכונות הבאות:
•`address` – כתובת, מטיפוס מחרוזת, `String`
•`persons` – מספר נפשות, מטיפוס מספר שלם, `int`
•`current` – קריאת מד המים נוכחית, מטיפוס מספר שלם, `int`
•`prev` – קריאת מד המים קודמת, מטיפוס מספר שלם, `int`
במחלקה הוגדרה פעולה בונה (בנאי) המקבל פרמטרים לכל התכונות, פעולות `set/get` לכל התכונות וגם פעולה `toString()`.
כתבו במחלקה `Client` פעולה לעדכון קריאת מד המים נוכחית. הפעולה מקבלת מספר שלם `newCurrent` ומעדכנת תכונות `current` ו-`prev` בהתאם.
כותרת הפעולה:
public void updateCurrent(int newCurrent)public void UpdateCurrent(int newCurrent)כתבו במחלקה `Client` את הפעולה לחישוב תשלום. הפעולה מקבלת שני תעריפים `rate1` (תעריף מוזל) ו- `rate2` (תעריף גבוה). הפעולה תחזיר סכום לתשלום לפי התקנון של רשות המים.
כותרת הפעולה:
public double payment(double rate1, double rate2)public double Payment(double rate1, double rate2)הנהלת חברת "מי הארץ" החליטה להציע ללקוחות שלה בדיקת מד המים בחינם. בשלב ראשון הוחלט לבדוק את מד המים אצל לקוחות שהתשלום שלהם גבוה ביחס למשפחות עם אותו מספר נפשות.
כתבו פעולה חיצונית המקבלת מערך לקוחות (הפניות לעצמים מטיפוס `Client`), מספר שלם חיובי `num` המציין את מספר הנפשות ביחידת הדיור ושני תעריפים `rate1` (מוזל) ו-`rate2` (גבוה).
הפעולה תדפיס כתובת של כל הלקוחות שיש להם `num` נפשות ביחידת דיור והתשלום שלהם גבוה מממוצע התשלומים של לקוחות עם אותו מספר נפשות.
כותרת הפעולה:
public static void proposal(Client[] arr, int num,
double rate1, double rate2)public static void Proposal(Client[] arr, int num,
double rate1, double rate2)◂ פתרון מלא לשאלה 8
סעיף א
`prev = current;` ואחר כך `current = newCurrent;`.
הרעיון: כשמגיעה קריאה חדשה, הקריאה שהייתה עד עכשיו "נוכחית" הופכת ל"קודמת", והקריאה החדשה הופכת ל"נוכחית".
1. קודם מעתיקים את `current` ל-`prev`.
2. רק אחר כך מציבים את `newCurrent` ב-`current`.
הסדר חשוב: אם נציב קודם ב-`current`, הערך הישן יימחק ולא נוכל להעביר אותו ל-`prev`.
public void updateCurrent(int newCurrent)
{
this.prev = this.current; // הקריאה הנוכחית הופכת לקודמת
this.current = newCurrent; // הקריאה החדשה היא הנוכחית
}public void UpdateCurrent(int newCurrent)
{
this.prev = this.current; // הקריאה הנוכחית הופכת לקודמת
this.current = newCurrent; // הקריאה החדשה היא הנוכחית
}דוגמה: `prev = 1000`, `current = 1035`. אחרי `updateCurrent(1050)`: `prev = 1035`, `current = 1050`.
תשובה: הפעולה שלמעלה.
סעיף ב
צריכה = `current - prev`, כמות מוזלת = `persons * 7`; אם מחזירים , אחרת .
הרעיון: מחשבים את כמות הצריכה ומחלקים אותה בין שני התעריפים.
1. כמות הצריכה: `consumption = current - prev`.
2. הכמות בתעריף המוזל: `cheap = persons * 7` (שבעה מ"ק לנפש).
3. אם הצריכה לא עוברת את הכמות המוזלת – כל הצריכה בתעריף המוזל: `consumption * rate1`.
4. אחרת – `cheap` מ"ק בתעריף המוזל, והיתרה `consumption - cheap` בתעריף הגבוה.
public double payment(double rate1, double rate2)
{
int consumption = this.current - this.prev; // כמות הצריכה
int cheap = this.persons * 7; // כמות בתעריף המוזל
if (consumption <= cheap)
return consumption * rate1;
return cheap * rate1 + (consumption - cheap) * rate2;
}public double Payment(double rate1, double rate2)
{
int consumption = this.current - this.prev; // כמות הצריכה
int cheap = this.persons * 7; // כמות בתעריף המוזל
if (consumption <= cheap)
return consumption * rate1;
return cheap * rate1 + (consumption - cheap) * rate2;
}דוגמה (מהשאלה): צריכה מ"ק, נפשות, ונניח `rate1 = 5`, `rate2 = 10`. הכמות המוזלת , היתרה , והתשלום .
תשובה: הפעולה שלמעלה.
סעיף ג
מעבר ראשון: סכום ומספר התשלומים של הלקוחות עם `num` נפשות, וממוצע; מעבר שני: הדפסת הכתובות של לקוחות עם `num` נפשות שהתשלום שלהם גדול מהממוצע.
הרעיון: אי אפשר לדעת אם תשלום גבוה מהממוצע לפני שמחשבים את הממוצע, ולכן עוברים על המערך פעמיים.
1. מעבר ראשון: לכל לקוח עם `getPersons() == num` מחשבים את התשלום בעזרת `payment(rate1, rate2)` מסעיף ב, מוסיפים אותו ל-`sum`, ומגדילים את `count`.
2. אם אין אף לקוח עם `num` נפשות (`count == 0`) – אין מה להדפיס, ויוצאים (כך גם נמנעים מחלוקה באפס).
3. הממוצע: `avg = sum / count` (`sum` מטיפוס `double`, ולכן החילוק ממשי).
4. מעבר שני: לכל לקוח עם `num` נפשות שהתשלום שלו גדול ממש מ-`avg` – מדפיסים את הכתובת (`getAddress()`).
public static void proposal(Client[] arr, int num,
double rate1, double rate2)
{
double sum = 0;
int count = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getPersons() == num)
{
sum += arr[i].payment(rate1, rate2);
count++;
}
}
if (count == 0)
return;
double avg = sum / count;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getPersons() == num && arr[i].payment(rate1, rate2) > avg)
System.out.println(arr[i].getAddress());
}
}public static void Proposal(Client[] arr, int num,
double rate1, double rate2)
{
double sum = 0;
int count = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetPersons() == num)
{
sum += arr[i].Payment(rate1, rate2);
count++;
}
}
if (count == 0)
return;
double avg = sum / count;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetPersons() == num && arr[i].Payment(rate1, rate2) > avg)
Console.WriteLine(arr[i].GetAddress());
}
}דוגמה: `rate1 = 5`, `rate2 = 10`, `num = 4`, ושלושה לקוחות עם 4 נפשות: A צרך מ"ק (תשלום ), B צרך מ"ק (), D צרך מ"ק (). הממוצע , ולכן תודפס רק הכתובת של D.
תשובה: הפעולה `proposal` שלמעלה.
שאלה 9 · משקל נקי של מספר ומערכים ממוינים לפיו
נתונות ההגדרות הבאות:
•"משקל נקי" של מספר שלם חיובי הוא סכום הספרות של המספר בלי הספרה השמאלית ביותר ובלי הספרה הימנית ביותר.
ה"משקל הנקי" של 123 הוא 2.
ה"משקל הנקי" של 12345- הוא 2+3+4=9.
ה"משקל הנקי" של 18 הוא 0.
ה"משקל הנקי" של 9 הוא 0.
•מערך של מספרים שלמים נקרא "מערך ממוין לפי משקלים" אם ה"משקלים" של כל איברי המערך ממוינים בסדר עולה ממש (ללא חזרות של משקל).
לדוגמה: המערך הבא "ממוין לפי משקלים":
כתבו פעולה אשר מקבלת מספר שלם חיובי ומחזירה את ה"משקל הנקי" שלו.
כתבו פעולה אשר מקבלת מערך חד-ממדי של מספרים שלמים ומחזירה ערך `true` אם המערך הוא "מערך ממוין לפי משקלים", ולא הפעולה תחזיר ערך `false`.
כתבו פעולה אשר מקבלת שני מערכים חד-ממדיים של מספרים שלמים וחיוביים. כל אחד מהמערכים הוא "מערך ממוין לפי משקלים". הפעולה תדפיס את כל האיברים עם "משקל נקי" ייחודי (כלומר את כל האיברים מהמערך הראשון ש"המשקל הנקי" שלהם לא מופיע במערך השני ואת כל האיברים מהמערך השני ש"המשקל הנקי" שלהם לא מופיע במערך הראשון).
לדוגמה: עבור שני המערכים:
הפעולה תדפיס:
923, 358, 12349, 5821, 1742, 36621מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים ב' ו- ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
מורידים את ספרת האחדות (`num / 10`), ואז סוכמים ספרות כל עוד `num >= 10` (כך הספרה השמאלית לא נספרת).
הרעיון: מסירים את הספרה הימנית, ואז סוכמים את הספרות מימין לשמאל ועוצרים לפני הספרה השמאלית ביותר.
1. לפי ההגדרה המספר חיובי; ליתר ביטחון לוקחים ערך מוחלט, כך שהפעולה תקינה גם עבור מספר שלילי.
2. `num = num / 10` – הסרת הספרה הימנית ביותר.
3. כל עוד `num >= 10` (כלומר נשארו לפחות שתי ספרות), הספרה הימנית הנוכחית אינה השמאלית ביותר: מוסיפים `num % 10` לסכום ומסירים אותה.
4. כש-`num < 10` נשארה רק הספרה השמאלית ביותר, והיא לא נספרת.
מספר חד-ספרתי או דו-ספרתי מקבל משקל : אחרי שלב 2 נשאר מספר קטן מ-, והלולאה לא מתבצעת.
מעקב עבור 12345: אחרי הסרת האחדות `num = 1234`; מוסיפים (`num = 123`), (`num = 12`), (`num = 1`); עוצרים. משקל .
בדוגמאות האחרות: , , , כנדרש.
public static int netWeight(int num)
{
num = Math.abs(num);
num = num / 10; // מורידים את הספרה הימנית ביותר
int sum = 0;
while (num >= 10) // הספרה השמאלית ביותר (num < 10) לא נספרת
{
sum += num % 10;
num = num / 10;
}
return sum;
}public static int NetWeight(int num)
{
num = Math.Abs(num);
num = num / 10; // מורידים את הספרה הימנית ביותר
int sum = 0;
while (num >= 10) // הספרה השמאלית ביותר (num < 10) לא נספרת
{
sum += num % 10;
num = num / 10;
}
return sum;
}תשובה: הפעולה `netWeight` שלמעלה.
סעיף ב
אם לאיזשהו מתקיים `netWeight(arr[i]) <= netWeight(arr[i-1])` מחזירים `false`; אחרת `true`.
הרעיון: סדר עולה ממש פירושו שכל משקל גדול ממש מהמשקל שלפניו. מספיק לבדוק כל זוג איברים סמוכים.
1. עוברים על `i` מ- עד סוף המערך.
2. אם המשקל של `arr[i]` קטן או שווה למשקל של `arr[i-1]` – הסדר אינו עולה ממש (או שיש חזרה של משקל), ומחזירים `false` מיד.
3. אם הלולאה הסתיימה בלי הפרה – מחזירים `true`.
בדוגמה: המשקלים עולים ממש – מוחזר `true`.
public static boolean isSortedByWeight(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
if (netWeight(arr[i]) <= netWeight(arr[i - 1]))
return false;
}
return true;
}public static bool IsSortedByWeight(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (NetWeight(arr[i]) <= NetWeight(arr[i - 1]))
return false;
}
return true;
}תשובה: הפעולה `isSortedByWeight` שלמעלה.
סעיף ג
מעבר מקביל (כמו מיזוג) על שני המערכים: המשקל הקטן מבין השניים ייחודי – מדפיסים ומתקדמים בו; משקלים שווים – מדלגים על שניהם; בסוף מדפיסים את השארית. בדוגמה: `923, 358, 12349, 5821, 1742, 36621`.
הרעיון: בשני המערכים המשקלים עולים ממש, ולכן אפשר לעבור עליהם במקביל, כמו במיזוג של שני מערכים ממוינים, עם אינדקס `i` למערך הראשון ו-`j` לשני:
1. מחשבים `w1` (המשקל של `arr1[i]`) ו-`w2` (המשקל של `arr2[j]`).
2. אם `w1 < w2`: כל המשקלים במערך השני מהמקום `j` והלאה גדולים מ-`w1`, וכל המשקלים לפני `j` קטנים מ-`w1` (הם כבר טופלו). לכן `w1` לא מופיע במערך השני – מדפיסים את `arr1[i]` ומקדמים את `i`.
3. אם `w2 < w1`: באופן סימטרי מדפיסים את `arr2[j]` ומקדמים את `j`.
4. אם `w1 == w2`: המשקל מופיע בשני המערכים, ואף אחד מהשניים אינו ייחודי – מקדמים את שני האינדקסים בלי להדפיס. (אין חזרות משקל בתוך מערך, ולכן לכל משקל יש לכל היותר איבר אחד בכל מערך.)
5. כשאחד המערכים נגמר, כל האיברים שנשארו במערך השני ייחודיים – מדפיסים אותם.
המשתנה `sep` דואג שהפסיק יודפס רק בין איברים, כמו בפלט לדוגמה.
שני המערכים נגמרו. הפלט: `923, 358, 12349, 5821, 1742, 36621`, כמו בשאלה.
public static void printUnique(int[] arr1, int[] arr2)
{
int i = 0, j = 0;
String sep = "";
while (i < arr1.length && j < arr2.length)
{
int w1 = netWeight(arr1[i]);
int w2 = netWeight(arr2[j]);
if (w1 < w2)
{
System.out.print(sep + arr1[i]);
sep = ", ";
i++;
}
else if (w2 < w1)
{
System.out.print(sep + arr2[j]);
sep = ", ";
j++;
}
else // אותו משקל בשני המערכים - אף אחד מהם לא ייחודי
{
i++;
j++;
}
}
while (i < arr1.length)
{
System.out.print(sep + arr1[i]);
sep = ", ";
i++;
}
while (j < arr2.length)
{
System.out.print(sep + arr2[j]);
sep = ", ";
j++;
}
System.out.println();
}public static void PrintUnique(int[] arr1, int[] arr2)
{
int i = 0, j = 0;
string sep = "";
while (i < arr1.Length && j < arr2.Length)
{
int w1 = NetWeight(arr1[i]);
int w2 = NetWeight(arr2[j]);
if (w1 < w2)
{
Console.Write(sep + arr1[i]);
sep = ", ";
i++;
}
else if (w2 < w1)
{
Console.Write(sep + arr2[j]);
sep = ", ";
j++;
}
else // אותו משקל בשני המערכים - אף אחד מהם לא ייחודי
{
i++;
j++;
}
}
while (i < arr1.Length)
{
Console.Write(sep + arr1[i]);
sep = ", ";
i++;
}
while (j < arr2.Length)
{
Console.Write(sep + arr2[j]);
sep = ", ";
j++;
}
Console.WriteLine();
}תשובה: הפעולה `printUnique` שלמעלה; בדוגמה היא מדפיסה `923, 358, 12349, 5821, 1742, 36621`.
סעיף ד
סעיף ב: ; סעיף ג: ( אורכי המערכים; חישוב משקל לוקח זמן לפי מספר הספרות, שנחשב קבוע).
חישוב "משקל נקי" עובר על הספרות של המספר, כלומר כאשר מספר הספרות. עבור `int` יש לכל היותר ספרות, ולכן זהו זמן קבוע.
•סעיף ב: לולאה אחת על איברי המערך, ובכל סיבוב שני חישובי משקל בזמן קבוע – (ובמדויק ).
•סעיף ג: בכל סיבוב של הלולאה הראשית `i` או `j` (או שניהם) מתקדמים, והלולאות שאחריה רק משלימות את השארית. לכן כל איבר בשני המערכים מטופל פעם אחת – , כאשר ו- אורכי המערכים (ובמדויק ).
תשובה: סעיף ב – ; סעיף ג – .
שאלה 10 · מערך ממוין לפי שארית: בדיקה ובנייה
נתונה הגדרה הבאה:
מערך של מספרים שלמים חיוביים נקרא "מערך ממוין לפי שארית של k" אם הוא עונה על כלל הבא:
•בתחילת המערך מופיעים מספרים שמתחלקים ב- k ללא שארית (עם שארית 0).
•אחריהם מופעים מספרים שמתחלקים ב- k עם שארית 1.
•אחריהם מופעים מספרים שמתחלקים ב- k עם שארית 2.
•אחריהם מופעים מספרים שמתחלקים ב- k עם שארית 3.
•וכך הלאה.
לדוגמה:
המערך הבא "ממוין לפי שארית של 4":
המערך הבא "ממוין לפי שארית של 5":
כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים `arr` ומספר שלם חיובי `k` ובודקת אם הוא "מערך ממוין לפי שארית של k". אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
כתבו פעולה המקבל מערך של מספרים שלמים חיוביים `arr` ומספר שלם וחיובי `k`. הפעולה תחזיר מערך חדש "הממוין לפי k" הכולל את כל הערכים של המערך `arr`.
מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 10
סעיף א
מחזירים `false` אם לאיזשהו מתקיים `arr[i] % k < arr[i-1] % k`; אחרת `true`.
הרעיון: לפי ההגדרה, השאריות `arr[i] % k` צריכות להופיע בסדר לא יורד: קודם כל השאריות , אחריהן וכן הלאה. (לא חייבות להופיע כל השאריות; חשוב רק שהשאריות לא יורדות לאורך המערך.) לכן מספיק לבדוק כל זוג סמוך: אם שארית קטנה מהשארית שלפניה – המערך לא ממוין.
1. עוברים על `i` מ- עד סוף המערך.
2. אם `arr[i] % k < arr[i-1] % k` – מחזירים `false`.
3. אם לא נמצאה ירידה – מחזירים `true`.
בדוגמה הראשונה השאריות ב-: – לא יורדות, מוחזר `true`. בדוגמה השנייה השאריות ב-: – מוחזר `true`.
public static boolean isSortedByMod(int[] arr, int k)
{
for (int i = 1; i < arr.length; i++)
{
if (arr[i] % k < arr[i - 1] % k)
return false;
}
return true;
}public static bool IsSortedByMod(int[] arr, int k)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] % k < arr[i - 1] % k)
return false;
}
return true;
}תשובה: הפעולה `isSortedByMod` שלמעלה.
סעיף ב
יוצרים מערך חדש באותו אורך; לכל שארית `r` מ- עד (לפי הסדר) מעתיקים אליו את כל האיברים עם `arr[i] % k == r`.
הרעיון: בונים את המערך החדש "קבוצה אחרי קבוצה": קודם כל המספרים עם שארית , אחריהם כל המספרים עם שארית , וכן הלאה עד שארית (השארית הגדולה ביותר האפשרית בחלוקה ב-).
1. יוצרים מערך `res` באורך של `arr`, ומשתנה `pos` – המקום הפנוי הבא ב-`res`.
2. לולאה חיצונית על השאריות `r = 0, 1, ..., k-1`.
3. לולאה פנימית על כל `arr`: כל איבר ששארית החלוקה שלו ב-`k` היא `r` מועתק ל-`res[pos]`, ו-`pos` גדל.
4. כל איבר מופיע בדיוק בקבוצה אחת (יש לו שארית אחת), ולכן כל הערכים מועתקים פעם אחת בדיוק, והמערך שמתקבל ממוין לפי שארית של `k`.
public static int[] sortByMod(int[] arr, int k)
{
int[] res = new int[arr.length];
int pos = 0;
for (int r = 0; r < k; r++) // כל שארית אפשרית לפי הסדר
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i] % k == r)
{
res[pos] = arr[i];
pos++;
}
}
}
return res;
}public static int[] SortByMod(int[] arr, int k)
{
int[] res = new int[arr.Length];
int pos = 0;
for (int r = 0; r < k; r++) // כל שארית אפשרית לפי הסדר
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] % k == r)
{
res[pos] = arr[i];
pos++;
}
}
}
return res;
}דוגמה: עבור `arr = {9, 7, 4, 13, 2, 8, 15, 1}` ו-`k = 4`: שארית 0 – ; שארית 1 – ; שארית 2 – ; שארית 3 – . מוחזר `{4, 8, 9, 13, 1, 2, 7, 15}`.
תשובה: הפעולה `sortByMod` שלמעלה.
סעיף ג
סעיף א: ; סעיף ב: .
נסמן ב- את אורך המערך.
•סעיף א: לולאה אחת שעוברת על המערך פעם אחת, ובכל סיבוב השוואה בזמן קבוע – .
•סעיף ב: הלולאה החיצונית רצה פעמים (פעם לכל שארית), ובכל פעם הלולאה הפנימית עוברת על כל האיברים – .
(הערה: אפשר לשפר את סעיף ב ל- בעזרת מערך מונים לפי שארית – כמו מיון מנייה – אבל הפתרון שלמעלה פשוט ונכון.)
תשובה: סעיף א – ; סעיף ב – .
שאלה 11 · תמורות של מספרים ומערך תמורות דו-ממדי
נתונות הגדרות הבאות:
•זוג מספרים שלמים חיוביים שונים זה מזה נקרא "תמורה" (פרמוטציה) אם הם מורכבים מאותן הספרות אבל סדר המופעים של הספרות שונה.
זוג מספרים 123 ו-312 הוא "תמורה".
זוג מספרים 1234 ו-3214 הוא "תמורה".
זוג מספרים 1223 ו-1323 לא "תמורה".
זוג מספרים 123 ו-123 לא "תמורה".
•שורה במערך דו-ממדי של מספרים שלמים חיוביים נקראת "שורת תמורות" אם יש בו לפחות זוג אחד שהוא "תמורה".
•מערך דו-ממדי של מספרים שלמים חיוביים נקרא "מערך תמורות" אם כל שורות שלו "שורות תמורה".
כתבו פעולה המקבלת זוג מספרים שלמים חיוביים ובודקת האם הוא "תמורה".
אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isPerm(int num1, int num2)public static bool IsPerm(int num1, int num2)כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים חיוביים ובודקת אם הוא "מערך תמורות".
אם כן – הפעולה תחזיר ערך `true`, ולא – הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isPermArr(int[][] arr)public static bool IsPermArr(int[][] arr)מהי הסיבוכיות של הפעולות `isPerm` ו- `isPermArr`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
אם `num1 == num2` מחזירים `false`; אחרת סופרים את מופעי כל ספרה (מערך מונים בגודל 10: `++` עבור `num1`, `--` עבור `num2`) ומחזירים `true` רק אם כל המונים .
הרעיון: שני מספרים מורכבים מאותן ספרות אם כל ספרה – מופיעה בשניהם אותו מספר פעמים. (לכן ו- אינם תמורה: ב- יש שתי ספרות 2 ובשני – שתי ספרות 3.) בנוסף, לפי ההגדרה המספרים צריכים להיות שונים.
1. אם `num1 == num2` – לא תמורה, מחזירים `false` (כמו ו-).
2. מערך מונים `count` בגודל , תא לכל ספרה.
3. מפרקים את `num1` לספרות (`% 10`, `/ 10`), ולכל ספרה מגדילים את המונה שלה.
4. מפרקים את `num2` לספרות, ולכל ספרה מקטינים את המונה שלה.
5. אם כל המונים חזרו ל- – לשני המספרים בדיוק אותן ספרות באותן כמויות, ומחזירים `true`; אחרת `false`.
מספרים שונים עם אותן ספרות בהכרח שונים בסדר הספרות, ולכן תנאי "סדר המופעים שונה" מתקיים מעצמו.
public static boolean isPerm(int num1, int num2)
{
if (num1 == num2)
return false;
int[] count = new int[10]; // מונה לכל ספרה 0-9
while (num1 > 0)
{
count[num1 % 10]++;
num1 = num1 / 10;
}
while (num2 > 0)
{
count[num2 % 10]--;
num2 = num2 / 10;
}
for (int d = 0; d < 10; d++)
{
if (count[d] != 0)
return false;
}
return true;
}public static bool IsPerm(int num1, int num2)
{
if (num1 == num2)
return false;
int[] count = new int[10]; // מונה לכל ספרה 0-9
while (num1 > 0)
{
count[num1 % 10]++;
num1 = num1 / 10;
}
while (num2 > 0)
{
count[num2 % 10]--;
num2 = num2 / 10;
}
for (int d = 0; d < 10; d++)
{
if (count[d] != 0)
return false;
}
return true;
}בדיקה בדוגמאות: `isPerm(123, 312)` → `true`; `isPerm(1234, 3214)` → `true`; `isPerm(1223, 1323)` → `false`; `isPerm(123, 123)` → `false`.
תשובה: הפעולה `isPerm` שלמעלה.
סעיף ב
לכל שורה בודקים את כל הזוגות בעזרת `isPerm`; אם בשורה כלשהי לא נמצא אף זוג "תמורה" מחזירים `false`, אחרת `true`.
הרעיון: "מערך תמורות" = כל השורות הן "שורות תמורה". לכן מספיקה שורה אחת בלי זוג "תמורה" כדי להחזיר `false`.
1. עוברים על השורות `i`.
2. בכל שורה מחפשים זוג: שתי לולאות מקוננות על המקומות `j < k` בשורה, ולכל זוג מזמנים `isPerm(arr[i][j], arr[i][k])` מסעיף א. (בודקים רק `k > j`, כי `isPerm` סימטרית ואין טעם לבדוק כל זוג פעמיים.)
3. ברגע שנמצא זוג, `found = true`, והלולאות של השורה נעצרות (התנאי `!found`).
4. אם בסוף השורה `found` עדיין `false` – השורה אינה "שורת תמורות", ומחזירים `false`.
5. אם כל השורות עברו את הבדיקה – מחזירים `true`.
public static boolean isPermArr(int[][] arr)
{
for (int i = 0; i < arr.length; i++)
{
boolean found = false;
for (int j = 0; j < arr[i].length && !found; j++)
{
for (int k = j + 1; k < arr[i].length && !found; k++)
{
if (isPerm(arr[i][j], arr[i][k]))
found = true;
}
}
if (!found) // שורה בלי אף זוג "תמורה"
return false;
}
return true;
}public static bool IsPermArr(int[][] arr)
{
for (int i = 0; i < arr.Length; i++)
{
bool found = false;
for (int j = 0; j < arr[i].Length && !found; j++)
{
for (int k = j + 1; k < arr[i].Length && !found; k++)
{
if (IsPerm(arr[i][j], arr[i][k]))
found = true;
}
}
if (!found) // שורה בלי אף זוג "תמורה"
return false;
}
return true;
}דוגמה: עבור `{{5, 123, 7, 321}, {10, 1, 11, 101, 110}, {44, 12, 21}}` – בשורה הראשונה ו-, בשנייה ו-, בשלישית ו-; מוחזר `true`. עבור `{{5, 123, 7, 321}, {10, 2, 33}}` – בשורה השנייה אין זוג "תמורה", מוחזר `false`.
תשובה: הפעולה `isPermArr` שלמעלה.
סעיף ג
`isPerm`: ( מספר הספרות, למעשה קבוע); `isPermArr`: – כלומר – למערך עם שורות ו- עמודות.
•`isPerm`: שתי לולאות שעוברות על הספרות של כל מספר ( ספרות), ולולאה קבועה של סיבובים על המונים – . עבור `int` יש לכל היותר ספרות, ולכן זה זמן קבוע .
•`isPermArr`: נסמן שורות ו- איברים בשורה. בכל שורה, במקרה הגרוע (אין זוג "תמורה" או שהוא נמצא בסוף), נבדקים כל הזוגות: זוגות, כלומר זימונים של `isPerm`. על כל השורות: , ומאחר ש- קבוע – .
תשובה: `isPerm` – (קבוע); `isPermArr` – .
שאלה 12 · מעקב רקורסיה: רצף ספרות זהות ובחירת איבר
נתונות הפעולות הרקורסיביות `secret` ו-`what`:
public static int what(int num)
{
return what(num,1);
}
private static int what(int num, int c)
{
int a;
if(num < 10) return c;
if(num%10 ==num/10%10)
a = what(num/10, c+1);
else
a = what(num/10, 1);
return Math.max(a, c);
}
public static int secret(int[] arr)
{
return secret(arr, 0, arr.length-1);
}
private static int secret(int[] arr, int left, int right)
{
if(left == right) return arr[left];
if(what(arr[left]) < what(arr[right]))
return secret(arr, left +1, right);
return secret(arr, left, right -1);
}public static int What(int num)
{
return What(num,1);
}
private static int What(int num, int c)
{
int a;
if(num < 10) return c;
if(num%10 ==num/10%10)
a = What(num/10, c+1);
else
a = What(num/10, 1);
return Math.Max(a, c);
}
public static int Secret(int[] arr)
{
return Secret(arr, 0, arr.Length-1);
}
private static int Secret(int[] arr, int left, int right)
{
if(left == right) return arr[left];
if(What(arr[left]) < What(arr[right]))
return Secret(arr, left +1, right);
return Secret(arr, left, right -1);
}עקבו אחרי זימון `what(5777922)`. רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה `what(num)` עבור מספר שלם חיובי `num`?
עקבו אחרי זימון `secret(arr)` עבור המערך
int[] arr = {777922,111,623,221333,10000,22133,211,1001,99790}ורשמו את תוצאות הזימון.
האם קיים מערך של מספרים שלמים חיוביים `arr` בגודל חמישה תאים לפחות, שעבורו זימון הפעולה `secret (arr)` יחזיר 123? הסבירו את תשובתכם.
מה מבצעת הפעולה `secret(arr)` עבור מערך מספרים שלמים וחיוביים `arr`?
◂ פתרון מלא לשאלה 12
סעיף א
`what(5777922)` מחזירה .
`what(5777922)` מזמנת את `what(5777922, 1)`. בכל קריאה משווים את ספרת האחדות (`num%10`) לספרת העשרות (`num/10%10`): אם הן שוות, ממשיכים עם `c+1` (הרצף הנוכחי של ספרות זהות התארך); אחרת מתחילים רצף חדש עם `c = 1`. כשנשארת ספרה אחת (`num < 10`) מוחזר `c`. בחזרה מהרקורסיה כל קריאה מחזירה את המקסימום בין מה שחזר לבין ה-`c` שלה.
תשובה: `what(5777922)` מחזירה .
סעיף ב
מחזירה את אורך הרצף הארוך ביותר של ספרות זהות צמודות במספר `num`.
•הפרמטר `c` הוא אורך הרצף הנוכחי של ספרות זהות צמודות, שמסתיים בספרת האחדות של `num` (רצף שמתחיל מהספרה הנוכחית ימינה).
•אם ספרת האחדות שווה לספרת העשרות, הרצף ממשיך: ממשיכים עם `c+1`. אחרת הרצף נשבר, ומתחילים רצף חדש באורך .
•כל קריאה מחזירה את הגדול מבין הרצף שלה (`c`) לבין הרצף המקסימלי שנמצא בהמשך המספר (`a`), ולכן התוצאה היא המקסימום על כל הרצפים.
בדוגמה של סעיף א: ב- הרצפים הם , , , , והארוך ביותר באורך .
תשובה: הפעולה מחזירה את אורך הרצף הארוך ביותר של ספרות זהות סמוכות במספר.
סעיף ג
`secret(arr)` מחזירה .
לפי סעיף ב, ערכי `what` של איברי המערך (אורך הרצף הארוך ביותר של ספרות זהות):
`secret(arr)` מזמנת את `secret(arr, 0, 8)`. בכל קריאה, אם `what(arr[left]) < what(arr[right])` מקדמים את `left`, אחרת מקטינים את `right`; כש-`left == right` מוחזר `arr[left]`.
הערך מוחזר בלי שינוי דרך כל הקריאות עד הזימון המקורי.
תשובה: `secret(arr)` מחזירה .
סעיף ד
כן. למשל `{123, 45, 67, 89, 12}`: לכל האיברים `what` , בכל השוואה יש שוויון ולכן `right` קטן, ומוחזר `arr[0]` .
כן, קיים. לפי סעיף ה, `secret` מחזירה את האיבר השמאלי ביותר מבין האיברים שערך `what` שלהם מקסימלי. ל- אין ספרות זהות צמודות, ולכן `what(123)` . מספיק לבנות מערך ש- הוא האיבר הראשון בו, ולשאר האיברים גם `what` (בלי ספרות זהות צמודות).
דוגמה: `arr = {123, 45, 67, 89, 12}`.
•בכל קריאה `what(arr[left])` ו-`what(arr[right])` , התנאי `1 < 1` לא מתקיים, ולכן `right` קטן ב-: .
•כש-`left == right == 0` מוחזר `arr[0]` .
תשובה: כן, למשל `{123, 45, 67, 89, 12}`.
סעיף ה
מחזירה את האיבר שבו הרצף הארוך ביותר של ספרות זהות צמודות (הערך המקסימלי של `what`); אם יש כמה – את השמאלי ביותר מביניהם.
הפעולה מצמצמת את הטווח `[left, right]` מהקצוות עד שנשאר איבר אחד. בכל צעד היא מסלקת את האיבר שערך `what` שלו קטן יותר:
•אם `what(arr[left]) < what(arr[right])` – מסלקת את השמאלי (`left+1`).
•אחרת (גדול או שווה) – מסלקת את הימני (`right-1`).
איבר עם `what` מקסימלי לא מסולק לעולם על ידי איבר עם ערך קטן יותר: אם הוא בקצה השמאלי, התנאי `<` לא מתקיים ומסולק הימני; אם הוא בקצה הימני והשמאלי קטן ממנו – מסולק השמאלי. כאשר שני הקצוות מקסימליים (שוויון), מסולק הימני. לכן האיבר שנשאר הוא השמאלי ביותר מבין האיברים עם `what` מקסימלי.
בסעיף ג: הערך המקסימלי מופיע רק ב-, והוא שנבחר.
תשובה: הפעולה מחזירה את האיבר שבו הרצף הארוך ביותר של ספרות זהות סמוכות; אם יש כמה כאלה – את הראשון (השמאלי ביותר) מביניהם במערך.