מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2021 מועד א'
הנדסת תוכנה · סמל 97104 · 13 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2021 מועד א', כל 13 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 15)
בכל מבחן 13 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 10 נקודות.
שאלות 7-9: יש לענות על שתיים שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 10-13: יש לענות על שתיים שאלות בלבד. ערך כל שאלה - 18 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטת 40 מספרים: סכום ספרות, זוגיים ואי-זוגיים
כתוב קטע תוכנית שיקלוט 40 מספרים חיוביים ושלמים:
עבור כל מספר תלת ספרתי שנקלט, יש להדפיס את סכום ספרותיו.
על הקוד לחשב ולהדפיס את כמות המספרים הזוגיים שנקלטו ואת סכום המספרים האי זוגיים שנקלטו.
◂ פתרון מלא לשאלה 1
סעיף א
בתוך לולאה של 40 קליטות: אם מדפיסים `num%10 + num/10%10 + num/100`.
הרעיון: מספר הקלטים ידוע מראש (40), ולכן משתמשים בלולאת for. כל מספר שנקלט מטופל מיד בתוך הלולאה.
1. מספר חיובי הוא תלת-ספרתי אם .
2. פירוק מספר תלת-ספרתי לספרות בעזרת שארית וחילוק בשלמים:
•ספרת האחדות: `num % 10`
•ספרת העשרות: `num / 10 % 10`
•ספרת המאות: `num / 100`
3. מדפיסים את סכום שלוש הספרות. לדוגמה, עבור 456: .
הקוד המלא (יחד עם סעיף ב, כי שני הסעיפים עובדים על אותה לולאת קליטה):
Scanner in = new Scanner(System.in);
int countEven = 0; // מונה המספרים הזוגיים
int sumOdd = 0; // צובר המספרים האי-זוגיים
for (int i = 1; i <= 40; i++)
{
int num = in.nextInt();
// סעיף א: מספר תלת-ספרתי - נדפיס את סכום ספרותיו
if (num >= 100 && num <= 999)
{
int units = num % 10;
int tens = num / 10 % 10;
int hundreds = num / 100;
System.out.println(units + tens + hundreds);
}
// סעיף ב: מונה לזוגיים, צובר לאי-זוגיים
if (num % 2 == 0)
countEven++;
else
sumOdd += num;
}
System.out.println("Even numbers: " + countEven);
System.out.println("Sum of odd numbers: " + sumOdd);int countEven = 0; // מונה המספרים הזוגיים
int sumOdd = 0; // צובר המספרים האי-זוגיים
for (int i = 1; i <= 40; i++)
{
int num = int.Parse(Console.ReadLine());
// סעיף א: מספר תלת-ספרתי - נדפיס את סכום ספרותיו
if (num >= 100 && num <= 999)
{
int units = num % 10;
int tens = num / 10 % 10;
int hundreds = num / 100;
Console.WriteLine(units + tens + hundreds);
}
// סעיף ב: מונה לזוגיים, צובר לאי-זוגיים
if (num % 2 == 0)
countEven++;
else
sumOdd += num;
}
Console.WriteLine("Even numbers: " + countEven);
Console.WriteLine("Sum of odd numbers: " + sumOdd);דוגמה: אם נקלטו (בין השאר) 123, 456, 999, 100, יודפסו עבורם 6, 15, 27, 1. מספרים כמו 7 או 1000 אינם תלת-ספרתיים ולכן לא מודפס עבורם דבר.
תשובה: בתוך לולאת הקליטה, לכל מספר שמקיים מדפיסים את סכום שלוש ספרותיו.
סעיף ב
מונה countEven (גדל כאשר `num % 2 == 0`) וצובר sumOdd (מוסיפים לו את num אחרת), מאופסים לפני הלולאה ומודפסים אחריה.
הרעיון: צריך שני משתני עזר שמאותחלים ל-0 לפני הלולאה:
1. מונה `countEven` – כמות המספרים הזוגיים.
2. צובר `sumOdd` – סכום המספרים האי-זוגיים.
בכל סיבוב בודקים את השארית בחלוקה ב-2: אם `num % 2 == 0` המספר זוגי ומגדילים את המונה ב-1; אחרת הוא אי-זוגי ומוסיפים אותו לצובר. כל מספר הוא זוגי או אי-זוגי, ולכן מתאים כאן `if ... else`.
אחרי הלולאה (כשכל 40 המספרים כבר נקלטו) מדפיסים את שני הערכים. הבדיקה של סעיף א היא `if` נפרד, כי מספר תלת-ספרתי יכול להיות גם זוגי וגם אי-זוגי – שתי הבדיקות בלתי תלויות.
הקוד המלא מופיע בסעיף א (החלק המסומן "סעיף ב").
דוגמה קטנה: עבור הקלטים 123, 456, 7 (ושאר הקלטים) – 456 זוגי ולכן המונה גדל ב-1, ו-123 ו-7 אי-זוגיים ולכן הצובר גדל ב-.
תשובה: מונה לזוגיים וצובר לאי-זוגיים בתוך הלולאה, והדפסת שניהם אחריה.
שאלה 2 · מחלקת קופסה: בנאי וקופסה בנפח מינימלי
למחלקה קופסה (תיבה) – Box יש ארבע תכונות:
•צבע – color, מטיפוס מחרוזת - String
•אורך – length, מטיפוס מספר שלם - int
•רוחב – width, מטיפוס מספר שלם - int
•גובה - height מטיפוס מספר שלם - int
במחלקה Box הוגדרה פעולה בונה (בנאי, constructor) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות get/set לכל אחת מהתכונות.
הבהרה (נמסרה לנבחנים במהלך הבחינה): הנוסחה לחישוב נפח תיבה: אורך x רוחב x גובה
כתוב פעולה בונה המייצרת קופסה בצבע color, שכל הממדים שלה (אורך, רוחב וגובה) שווים ל- 10.
כותרת הפעולה: `public Box(String color)`.
כתוב פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג Box בשם arr ומחזירה את הצבע של קופסה במערך עם ערך הנפח הקטן ביותר. כותרת הפעולה `public static String smallBox(Box[] arr)`.
הנחה: כל תא במערך מכיל הפניה לעצם מסוג Box ואין תאים במערך שערכם שווה ל- null
◂ פתרון מלא לשאלה 2
סעיף א
בנאי שמציב `this.color = color` ו-10 בשלוש התכונות length, width, height.
הרעיון: בנאי נכתב בתוך המחלקה Box, ושמו כשם המחלקה. הוא מקבל רק את הצבע, ולכן את שלושת הממדים הוא קובע בעצמו לערך הקבוע 10.
1. מציבים את הפרמטר `color` בתכונה `this.color` (המילה `this` מבדילה בין התכונה לפרמטר בעל אותו שם).
2. מציבים 10 בתכונות `length`, `width`, `height`.
הבנאי נמצא בתוך המחלקה, ולכן מותר לו לגשת ישירות לתכונות הפרטיות.
public Box(String color)
{
this.color = color;
this.length = 10;
this.width = 10;
this.height = 10;
}public Box(string color)
{
this.color = color;
this.length = 10;
this.width = 10;
this.height = 10;
}תשובה: הבנאי מציב את הצבע שהתקבל ואת הערך 10 באורך, ברוחב ובגובה.
סעיף ב
מעבר על המערך, חישוב נפח `getLength()*getWidth()*getHeight()` לכל קופסה ושמירת המקום של הנפח הקטן ביותר; מחזירים את `getColor()` של הקופסה במקום זה.
הרעיון: זהו חיפוש מינימום במערך. הפעולה חיצונית (לא בתוך Box), ולכן אין לה גישה ישירה לתכונות – משתמשים בפעולות get.
1. נפח של קופסה = אורך × רוחב × גובה, כלומר `arr[i].getLength() * arr[i].getWidth() * arr[i].getHeight()`.
2. מתחילים בהנחה שהקופסה הראשונה (`arr[0]`) היא הקטנה ביותר: שומרים את הנפח שלה ב-`minVolume` ואת המקום שלה ב-`minIndex`.
3. עוברים על שאר התאים (מ-1 עד הסוף). אם נפח הקופסה הנוכחית קטן מ-`minVolume` – מעדכנים את הנפח ואת המקום.
4. בסוף מחזירים את הצבע של הקופסה במקום `minIndex`.
שומרים את המקום ולא רק את הנפח, כי מה שמוחזר הוא הצבע של הקופסה, לא הנפח. אם יש כמה קופסאות בנפח המינימלי, מוחזר הצבע של הראשונה מהן (ההשוואה היא `<` ולא `<=`).
public static String smallBox(Box[] arr)
{
int minIndex = 0;
int minVolume = arr[0].getLength() * arr[0].getWidth() * arr[0].getHeight();
for (int i = 1; i < arr.length; i++)
{
int volume = arr[i].getLength() * arr[i].getWidth() * arr[i].getHeight();
if (volume < minVolume)
{
minVolume = volume;
minIndex = i;
}
}
return arr[minIndex].getColor();
}public static string SmallBox(Box[] arr)
{
int minIndex = 0;
int minVolume = arr[0].GetLength() * arr[0].GetWidth() * arr[0].GetHeight();
for (int i = 1; i < arr.Length; i++)
{
int volume = arr[i].GetLength() * arr[i].GetWidth() * arr[i].GetHeight();
if (volume < minVolume)
{
minVolume = volume;
minIndex = i;
}
}
return arr[minIndex].GetColor();
}דוגמה: עבור הקופסאות red (), blue (), green () תוחזר המחרוזת "blue".
תשובה: הפעולה מחזירה את `getColor()` של הקופסה שהנפח שלה מינימלי.
שאלה 3 · מחלקת מיכל דלק: מילוי, ריקון והעברה
במחלקה מיכל דלק - Tank קיימות התכונות:
•קיבולת מיכל הדלק - capacity, מטיפוס מספר שלם - int
•כמות דלק - amount מטיפוס שלם - int
במחלקה Tank הוגדרה פעולה בונה (בנאי, constructor) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות get/set לכל אחת מהתכונות.
כתוב פעולה בונה המקבלת את קיבולת מיכל הדלק ומייצרת מיכל ריק.
כתוב במחלקה Tank פעולה פנימית המחזירה true אם במיכל יש דלק, אחרת הפעולה מחזירה false.
כתוב במחלקה Tank פעולה פנימית `boolean isPossible(int num, char op)`.
הפעולה תקבל את סוג המשימה op ואת כמות הדלק num.
סוג המשימה יכול להיות אחד מהתווים '+' או '-'.
אם op שווה ל- '+' יש להוסיף כמות הדלק num למיכל,
אם op שווה ל- '-' יש להוריד את כמות הדלק num מהמיכל.
אם אפשר לבצע את המשימה, הפעולה תחזיר true, אחרת הפעולה תחזיר false.
כתוב פעולה חיצונית `static int fill (Tank t1, Tank t2)`.
הפעולה מחזירה את כמות הדלק המקסימלית שאפשר להעביר ממיכל t1 למיכל t2.
◂ פתרון מלא לשאלה 3
סעיף א
`public Tank(int capacity)` שמציב את הקיבולת ו-`amount = 0`.
הרעיון: "מיכל ריק" פירושו שכמות הדלק בו היא 0. הבנאי מקבל רק את הקיבולת, מציב אותה בתכונה `capacity`, ומאפס את `amount`.
public Tank(int capacity)
{
this.capacity = capacity;
this.amount = 0;
}public Tank(int capacity)
{
this.capacity = capacity;
this.amount = 0;
}תשובה: בנאי שמקבל capacity ומציב `amount = 0`.
סעיף ב
`return this.amount > 0;`
הרעיון: במיכל יש דלק בדיוק כאשר כמות הדלק גדולה מ-0. הביטוי `this.amount > 0` הוא עצמו ערך בוליאני, ולכן אפשר להחזיר אותו ישירות (בלי if).
public boolean hasFuel()
{
return this.amount > 0;
}public bool HasFuel()
{
return this.amount > 0;
}תשובה: הפעולה מחזירה את ערך הביטוי `amount > 0`.
סעיף ג
'+': אפשרי אם (מוסיפים ומחזירים true); '-': אפשרי אם (מורידים ומחזירים true); אחרת false בלי שינוי.
הרעיון: לכל סוג משימה יש תנאי אחר שקובע אם אפשר לבצע אותה. אם התנאי מתקיים – מבצעים (מעדכנים את `amount`) ומחזירים true; אם לא – לא משנים דבר ומחזירים false.
1. הוספה (`'+'`): אסור לעבור את קיבולת המיכל, ולכן התנאי הוא .
2. הורדה (`'-'`): אי אפשר להוציא יותר דלק ממה שיש, ולכן התנאי הוא .
3. בכל מקרה אחר (התנאי לא מתקיים, או תו אחר) מחזירים false.
דוגמה: מיכל בקיבולת 50 עם 30 ליטר: `isPossible(20, '+')` מחזירה true והכמות הופכת ל-50; `isPossible(30, '+')` מחזירה false () והכמות נשארת 30; `isPossible(60, '-')` מחזירה false.
public boolean isPossible(int num, char op)
{
if (op == '+' && this.amount + num <= this.capacity)
{
this.amount += num; // יש מספיק מקום - מוסיפים
return true;
}
if (op == '-' && num <= this.amount)
{
this.amount -= num; // יש מספיק דלק - מורידים
return true;
}
return false;
}public bool IsPossible(int num, char op)
{
if (op == '+' && this.amount + num <= this.capacity)
{
this.amount += num; // יש מספיק מקום - מוסיפים
return true;
}
if (op == '-' && num <= this.amount)
{
this.amount -= num; // יש מספיק דלק - מורידים
return true;
}
return false;
}תשובה: הפעולה מבצעת את ההוספה/ההורדה ומחזירה true רק אם התנאי המתאים מתקיים; אחרת מחזירה false.
סעיף ד
המינימום בין הדלק שיש ב-t1 לבין המקום הפנוי ב-t2: .
הרעיון: הכמות שאפשר להעביר מוגבלת משני כיוונים:
1. אי אפשר להעביר יותר דלק ממה שיש ב-t1, כלומר `t1.getAmount()`.
2. אי אפשר להכניס ל-t2 יותר מהמקום הפנוי בו: `t2.getCapacity() - t2.getAmount()`.
הכמות המקסימלית היא הקטנה מבין שתי המגבלות. הפעולה חיצונית, ולכן משתמשים בפעולות get. הפעולה רק מחשבת ומחזירה את הכמות – היא לא מבצעת את ההעברה.
public static int fill(Tank t1, Tank t2)
{
int space = t2.getCapacity() - t2.getAmount(); // המקום הפנוי ב-t2
if (t1.getAmount() < space)
return t1.getAmount();
return space;
}public static int Fill(Tank t1, Tank t2)
{
int space = t2.GetCapacity() - t2.GetAmount(); // המקום הפנוי ב-t2
if (t1.GetAmount() < space)
return t1.GetAmount();
return space;
}דוגמאות: ב-t1 יש 40, ו-t2 בקיבולת 60 עם 10 (מקום פנוי 50) – מוחזר 40. ב-t1 יש 80 ובאותו t2 – מוחזר 50.
תשובה: מוחזר .
שאלה 4 · בדיקת "מערך מושלם" וסיבוכיות
מערך של מספרים שלמים נקרא "מושלם" אם הוא מקיים את התנאים הבאים:
•גודל המערך הוא מספר אי-זוגי.
•בחצי הראשון של המערך יש רק מספרים חיובים חד ספרתיים.
•האיבר המרכזי (אמצעי) הוא 0.
•בחצי השני של המערך אין אף מספר חיובי חד-ספרתי.
המערך arr={1, 7,3, 0, 13, 131, 44} הוא "מערך מושלם" מאחר שהוא עונה על כל ארבע הדרישות.
•אורך המערך 7 אי-זוגי.
•החצי הראשון {1,7,3} מכיל רק מספרים חד-ספרתיים.
•חצי השני {13,131,44} אינו מכיל מספרים חד-ספרתיים.
•האיבר המרכזי הוא 0.
כתוב פעולה המקבלת מערך של מספרים שלמים ומחזירה ערך true אם הוא "מערך מושלם", אם לא, הפעולה תחזיר ערך false.
מהי סיבוכיות הפעולה שבסעיף א'? הסבר את תשובתך.
◂ פתרון מלא לשאלה 4
סעיף א
בודקים: אורך אי-זוגי; `arr[n/2]==0`; כל איבר לפני האמצע בין 1 ל-9; אף איבר אחרי האמצע אינו בין 1 ל-9. כשל באחד – false.
הרעיון: בודקים את ארבעת התנאים אחד אחרי השני. ברגע שתנאי אחד נכשל מחזירים false; אם כולם עברו – מחזירים true.
נסמן = אורך המערך. כאשר אי-זוגי, האיבר האמצעי נמצא במקום `mid = n / 2` (למשל עבור : ), החצי הראשון הוא המקומות והחצי השני הוא .
1. אם זוגי (`n % 2 == 0`) – false. בדיקה זו קודמת לשאר, כי רק במערך באורך אי-זוגי יש איבר אמצעי.
2. אם `arr[mid] != 0` – false.
3. "מספר חיובי חד-ספרתי" הוא מספר בין 1 ל-9. בחצי הראשון כל איבר חייב להיות כזה: אם יש איבר עם `arr[i] < 1 || arr[i] > 9` – false.
4. בחצי השני אסור שיהיה איבר כזה: אם יש איבר עם `arr[i] >= 1 && arr[i] <= 9` – false. (מספרים כמו 0, שליליים או רב-ספרתיים מותרים בחצי השני.)
5. אם לא הוחזר false באף בדיקה – המערך מושלם, מחזירים true.
public static boolean isPerfect(int[] arr)
{
int n = arr.length;
if (n % 2 == 0) // תנאי 1: גודל אי-זוגי
return false;
int mid = n / 2;
if (arr[mid] != 0) // תנאי 3: האיבר האמצעי הוא 0
return false;
for (int i = 0; i < mid; i++) // תנאי 2: בחצי הראשון רק 1..9
if (arr[i] < 1 || arr[i] > 9)
return false;
for (int i = mid + 1; i < n; i++) // תנאי 4: בחצי השני אף 1..9
if (arr[i] >= 1 && arr[i] <= 9)
return false;
return true;
}public static bool IsPerfect(int[] arr)
{
int n = arr.Length;
if (n % 2 == 0) // תנאי 1: גודל אי-זוגי
return false;
int mid = n / 2;
if (arr[mid] != 0) // תנאי 3: האיבר האמצעי הוא 0
return false;
for (int i = 0; i < mid; i++) // תנאי 2: בחצי הראשון רק 1..9
if (arr[i] < 1 || arr[i] > 9)
return false;
for (int i = mid + 1; i < n; i++) // תנאי 4: בחצי השני אף 1..9
if (arr[i] >= 1 && arr[i] <= 9)
return false;
return true;
}בדיקה עם הדוגמה: {1, 7, 3, 0, 13, 131, 44}: אי-זוגי, ו-`arr[3]=0`, האיברים 1, 7, 3 כולם בין 1 ל-9, והאיברים 13, 131, 44 אינם בין 1 ל-9 – מוחזר true. לעומת זאת עבור {1, 7, 3, 0, 13, 5, 44} מוחזר false בגלל ה-5 בחצי השני.
תשובה: הפעולה שלמעלה.
סעיף ב
– כל איבר נבדק לכל היותר פעם אחת (שתי לולאות על חצאי המערך).
נסמן = אורך המערך.
1. בדיקת הזוגיות של האורך ובדיקת האיבר האמצעי – מספר קבוע של פעולות, .
2. הלולאה הראשונה עוברת על איברים והשנייה על איברים, ובכל סיבוב יש מספר קבוע של פעולות. יחד הן עוברות על איברים – כל איבר לכל היותר פעם אחת.
3. סך הכול: . במקרה הגרוע (מערך מושלם) עוברים על כל המערך; זו סיבוכיות לינארית.
תשובה: .
שאלה 5 · מעקב: חיפוש זוג שסכומו נתון במערך ממוין
הגדרה: מערך נקרא "מערך ממוין בסדר עולה" אם כל איבר (פרט לאיבר הראשון) גדול מהאיבר הקודם לו או שווה לו. נתונה פעולה what המקבלת מערך מספרים שלמים ממוין בסדר עולה ומספר שלם נוסף.
public static boolean what(int[] arr, int num)
{
int k = 0;
int p = arr.length-1;
int s;
while(k < p)
{
s = arr[k] + arr[p];
if(s < num)
{
k++;
}
else
{
if(s > num)
{
p--;
}
else
{
return true;
}
}
}
return false;
}public static bool What(int[] arr, int num)
{
int k = 0;
int p = arr.Length-1;
int s;
while(k < p)
{
s = arr[k] + arr[p];
if(s < num)
{
k++;
}
else
{
if(s > num)
{
p--;
}
else
{
return true;
}
}
}
return false;
}נתון מערך `int[] arr={2, 4, 7, 12, 18}`
עקוב בעזרת טבלת מעקב אחר הזימון what(arr, 10) ורשום מה תחזיר הפעולה.
תן דוגמה לפרמטר num כך שזימון what(arr, num) יחזיר תוצאה שונה מתוצאה שהתקבלה בסעיף א.1
שים לב: אין לשנות את המערך arr!
מה מבצעת הפעולה באופן כללי?
מהי סיבוכיות זמן הריצה של הפעולה what? הסבר את תשובתך.
◂ פתרון מלא לשאלה 5
סעיף א
false
עוקבים אחרי המשתנים k, p, s. בהתחלה (המקום הראשון) ו- (המקום האחרון, `arr.length-1`).
כל הזוגות שנבדקו (20, 14, 9, 11) שונים מ-10, ו-k ו-p נפגשו, ולכן הפעולה מחזירה false. (ואכן אין במערך שני איברים שסכומם 10.)
תשובה: `what(arr, 10)` מחזירה false.
למשל num = 9 (כי ) – הפעולה תחזיר true.
בסעיף א.1 התקבל false, ולכן צריך num שעבורו יוחזר true, כלומר num שהוא סכום של שני איברים במקומות שונים במערך.
ניקח . מעקב קצר:
(גם 6, 11, 14, 16, 19, 20, 22, 25, 30 הם תשובות נכונות.)
תשובה: num = 9, ואז `what(arr, 9)` מחזירה true.
סעיף ב
מחזירה true אם יש במערך שני איברים (בשני מקומות שונים) שסכומם שווה ל-num, אחרת false.
הפעולה משתמשת בשני מצביעים: k מתחיל בתחילת המערך (האיבר הקטן) ו-p בסופו (האיבר הגדול).
1. אם הסכום `arr[k] + arr[p]` קטן מ-num – צריך סכום גדול יותר, ולכן מקדמים את k לאיבר גדול יותר (המערך ממוין בסדר עולה).
2. אם הסכום גדול מ-num – צריך סכום קטן יותר, ולכן מזיזים את p שמאלה לאיבר קטן יותר.
3. אם הסכום שווה ל-num – נמצא זוג, מחזירים true.
4. אם k ו-p נפגשו – נבדקו כל האפשרויות ואין זוג כזה, מחזירים false.
התנאי `k < p` מבטיח שהזוג מורכב משני איברים במקומות שונים.
תשובה: הפעולה בודקת אם קיימים במערך הממוין שני איברים (במקומות שונים) שסכומם num: מחזירה true אם כן ו-false אם לא.
סעיף ג
– בכל סיבוב k גדל או p קטן, ולכן יש לכל היותר סיבובים.
נסמן = אורך המערך. בתחילה המרחק בין המצביעים הוא . בכל סיבוב של הלולאה (שלא מסתיים ב-return) k גדל ב-1 או p קטן ב-1, כלומר המרחק קטן ב-1. הלולאה נעצרת כשהמרחק מגיע ל-0, ולכן יש לכל היותר סיבובים, ובכל סיבוב מספר קבוע של פעולות.
תשובה: סיבוכיות לינארית, .
שאלה 6 · בדיקת תקינות מחרוזת לפי מיקום נקודות
מחרוזת תהא תקינה אם מופיע בה התו '.' (נקודה) לפחות פעם אחת, אך לא ברציפות, ולא בתחילת המחרוזת או בסופה, לדוגמה:
מחרוזות תקינות: `www.sport5.il` `Lionel.Messi`
מחרוזות שאינן תקינות: `abc..def` `.ab.Cd` `efG.` `ABC`
כתוב פעולה המקבלת מחרוזת ומחזירה true אם מחרוזת תקינה, אם לא הפעולה תחזיר false.
◂ פתרון מלא לשאלה 6
פתרון
false אם התו הראשון או האחרון הוא נקודה (או מחרוזת ריקה); מעבר על התווים הפנימיים: נקודה שאחריה נקודה – false; בסוף מחזירים אם נמצאה נקודה לפחות פעם אחת.
הרעיון: יש שלושה תנאים לתקינות, וכל אחד נבדק בנפרד:
1. לא בתחילה ולא בסוף: אם `s.charAt(0)` או `s.charAt(n-1)` הוא נקודה – המחרוזת לא תקינה (כך נפסלות `.ab.Cd` ו-`efG.`). מחרוזת ריקה גם היא לא תקינה, כי אין בה נקודה.
2. לא ברציפות: עוברים על התווים הפנימיים (מקום 1 עד ). אם בתו נמצאת נקודה וגם בתו שאחריו – לא תקינה (כך נפסלת `abc..def`). הגישה ל-`i + 1` בטוחה, כי .
3. לפחות פעם אחת: משתנה בוליאני `hasDot` מקבל true כשנמצאת נקודה. בסוף מחזירים את ערכו (כך נפסלת `ABC`).
נקודה יכולה להופיע רק בתווים הפנימיים (את הקצוות כבר בדקנו), ולכן מספיק לחפש אותה בלולאה.
public static boolean isValid(String s)
{
int n = s.length();
if (n == 0 || s.charAt(0) == '.' || s.charAt(n - 1) == '.')
return false; // נקודה בהתחלה או בסוף
boolean hasDot = false;
for (int i = 1; i < n - 1; i++)
{
if (s.charAt(i) == '.')
{
hasDot = true;
if (s.charAt(i + 1) == '.') // שתי נקודות ברצף
return false;
}
}
return hasDot; // לפחות נקודה אחת
}public static bool IsValid(string s)
{
int n = s.Length;
if (n == 0 || s[0] == '.' || s[n - 1] == '.')
return false; // נקודה בהתחלה או בסוף
bool hasDot = false;
for (int i = 1; i < n - 1; i++)
{
if (s[i] == '.')
{
hasDot = true;
if (s[i + 1] == '.') // שתי נקודות ברצף
return false;
}
}
return hasDot; // לפחות נקודה אחת
}בדיקה עם הדוגמאות: `www.sport5.il` ו-`Lionel.Messi` – true; `abc..def`, `.ab.Cd`, `efG.`, `ABC` – false, כל אחת מהסיבה שצוינה למעלה.
תשובה: הפעולה שלמעלה.
שאלה 7 · מחלקות סוללה וחבילת סוללות: בנאים ופעולות
הערה: אפשר להניח שבשתי המחלקות קיימות פעולות get/set. אם השתמשת בפעולות נוספות, עליך לכתוב את הפעולות!
נתונה המחלקה סוללה (Battery), אשר לה ארבע תכונות:
•יצרן – manufacturer, מטיפוס מחרוזת - String
•גודל – size, מטיפוס תו - char
לדוגמה: 'A' , 'B' , 'C' , 'D'
•מתח חשמלי – volt, מטיפוס ממשי - double
•האם תקינה? – isNormal, מטיפוס בוליאני - boolean
כתוב בנאי (constructor) למחלקה Battery המקבל פרמטר של כל תכונה ומייצר עצם מסוג Battery בהתאם לערכי הפרמטרים.
כתוב בנאי למחלקה Battery אשר מייצר עצם מסוג Battery תקין של היצרן "Duracell".
הבנאי מקבל מתח וגודל כפרמטרים.
נתונה המחלקה חבילת-סוללות (BatteryPack), אשר לה שתי תכונות:
•מחיר – price , מטיפוס ממשי, double.
•סוללות – batteries, מערך מטיפוס Battery באורך 12.
כתוב פעולה חיצונית checkPrice, אשר מקבלת כפרמטר עצם מטיפוס BatteryPack, ומספר ממשי sum שהוא הסכום שהלקוח מוכן לשלם.
•אם הסכום שהלקוח מוכן לשלם גבוה ממחיר חבילת הסוללות, אזי אפשר לקנות את החבילה ולכן הפעולה תדפיס הודעה "אפשר לרכוש" ואת העודף שנשאר אחרי הקנייה.
•אם הסכום שהלקוח מוכן לשלם נמוך ממחיר חבילת הסוללות, אזי אי אפשר לקנות את החבילה ולכן הפעולה תדפיס הודעה "אי אפשר לרכוש" ואת הסכום שחסר.
•אם סכום שלקוח מוכן לשלם שווה למחיר חבילת הסוללות, אפשר לקנות את החבילה ולכן הפעולה תדפיס הודעה "O.K.".
כתוב את הפעולה `isEnough(double v)`, אשר מקבלת כפרמטר מספר ממשי v המציין מתח חשמלי הנדרש ומחזירה ערך בוליאני.
אם סכום המתחים החשמליים של כל הסוללות התקינות בחבילה קטן מ- v, הפעולה תחזיר שקר, אחרת תחזיר אמת.
◂ פתרון מלא לשאלה 7
סעיף א
בנאי עם ארבעה פרמטרים שמציב כל פרמטר בתכונה המתאימה.
הרעיון: הבנאי מקבל ארבעה פרמטרים, אחד לכל תכונה ומאותו טיפוס, ומעתיק כל אחד לתכונה המתאימה בעזרת `this`.
public Battery(String manufacturer, char size, double volt, boolean isNormal)
{
this.manufacturer = manufacturer;
this.size = size;
this.volt = volt;
this.isNormal = isNormal;
}public Battery(string manufacturer, char size, double volt, bool isNormal)
{
this.manufacturer = manufacturer;
this.size = size;
this.volt = volt;
this.isNormal = isNormal;
}תשובה: הבנאי שלמעלה.
בנאי `Battery(double volt, char size)` שמציב את המתח והגודל, `manufacturer = "Duracell"` ו-`isNormal = true`.
הרעיון: הבנאי מקבל רק שני פרמטרים (מתח וגודל). את שתי התכונות האחרות הוא קובע לפי הדרישה: היצרן הוא תמיד "Duracell", והסוללה "תקינה", כלומר `isNormal = true`.
אפשר להגדיר את שני הבנאים באותה מחלקה, כי רשימות הפרמטרים שלהם שונות (העמסת בנאים).
public Battery(double volt, char size)
{
this.manufacturer = "Duracell";
this.size = size;
this.volt = volt;
this.isNormal = true;
}public Battery(double volt, char size)
{
this.manufacturer = "Duracell";
this.size = size;
this.volt = volt;
this.isNormal = true;
}תשובה: הבנאי שלמעלה.
סעיף ב
משווים את sum ל-`pack.getPrice()`: גדול – "אפשר לרכוש" ו-sum−price; קטן – "אי אפשר לרכוש" ו-price−sum; שווה – "O.K.".
הרעיון: הפעולה חיצונית, ולכן מקבלת את המחיר בעזרת `pack.getPrice()`. יש שלושה מקרים שמוציאים זה את זה, ולכן משתמשים ב-`if ... else if ... else`:
1. : מדפיסים "אפשר לרכוש" ואת העודף .
2. : מדפיסים "אי אפשר לרכוש" ואת הסכום החסר .
3. אחרת (): מדפיסים "O.K.".
הפעולה רק מדפיסה, ולכן טיפוס הערך המוחזר הוא void.
public static void checkPrice(BatteryPack pack, double sum)
{
double price = pack.getPrice();
if (sum > price)
System.out.println("אפשר לרכוש, העודף: " + (sum - price));
else if (sum < price)
System.out.println("אי אפשר לרכוש, חסר: " + (price - sum));
else
System.out.println("O.K.");
}public static void CheckPrice(BatteryPack pack, double sum)
{
double price = pack.GetPrice();
if (sum > price)
Console.WriteLine("אפשר לרכוש, העודף: " + (sum - price));
else if (sum < price)
Console.WriteLine("אי אפשר לרכוש, חסר: " + (price - sum));
else
Console.WriteLine("O.K.");
}דוגמה: לחבילה במחיר 25.5: עבור sum = 30 יודפס "אפשר לרכוש, העודף: 4.5"; עבור sum = 20 יודפס "אי אפשר לרכוש, חסר: 5.5"; עבור sum = 25.5 יודפס "O.K.".
תשובה: הפעולה שלמעלה.
פעולה פנימית ב-BatteryPack: צוברים את `getVolt()` של כל סוללה שאינה null ו-`getIsNormal()` אמת; מחזירים `total >= v`.
הרעיון: הפעולה מקבלת רק את v, ולכן היא פעולה פנימית של המחלקה BatteryPack – היא פועלת על מערך הסוללות של העצם עצמו (`this.batteries`).
1. צובר `total` מאותחל ל-0.
2. עוברים על כל 12 התאים. סוללה נספרת רק אם היא תקינה (`getIsNormal()` מחזירה true); לסוללה כזו מוסיפים את המתח שלה (`getVolt()`) לצובר. נוסף על כך בודקים שהתא אינו null, למקרה שהחבילה אינה מלאה – הבדיקה הזאת לא מזיקה כשהחבילה מלאה.
3. לפי הדרישה, אם מחזירים false, אחרת true – כלומר מחזירים את ערך הביטוי `total >= v`.
הפעולה `getIsNormal()` היא פעולת ה-get של התכונה isNormal (לפי ההערה, פעולות get/set קיימות).
public boolean isEnough(double v)
{
double total = 0; // סכום המתחים של הסוללות התקינות
for (int i = 0; i < this.batteries.length; i++)
{
if (this.batteries[i] != null && this.batteries[i].getIsNormal())
total += this.batteries[i].getVolt();
}
return total >= v;
}public bool IsEnough(double v)
{
double total = 0; // סכום המתחים של הסוללות התקינות
for (int i = 0; i < this.batteries.Length; i++)
{
if (this.batteries[i] != null && this.batteries[i].GetIsNormal())
total += this.batteries[i].GetVolt();
}
return total >= v;
}דוגמה: בחבילה 11 סוללות תקינות של וסוללה אחת לא תקינה של : הסכום הוא (הסוללה הלא תקינה לא נספרת). `isEnough(16.5)` מחזירה true ו-`isEnough(16.6)` מחזירה false.
תשובה: הפעולה שלמעלה.
שאלה 8 · מחלקת נהג: מעקב אחר עצמים ומערך שמות
נתונה המחלקה Driver, המייצגת נהג שקבל רישיון נהיגה. תכונות המחלקה הן:
•שם - name, מטיפוס מחרוזת - String
•תעודת זהות – id , מטיפוס מחרוזת - String
•שנת לידה – year, מטיפוס מספר שלם - int
•מספר מבחני נהיגה כולל – tests, מטיפוס מספר שלם - int
במחלקה הוגדרה פעולה בונה (constructor) המקבלת פרמטר לכל תכונה ויוצרת עצם מסוג Driver, המכיל את הערכים האלו בתכונות.
כמו כן יש פעולות get/set לכל אחת מהתכונות.
עקוב אחרי קטע התוכנית, לכל עצם רשום את השמות של כל התכונות שלו, את הערכים של כל התכונות ואת השינויים שהיו בהם, ורשום את הפלט.
Driver [] d=new Driver[5];
d[0] = new Driver("Yossi", "1234", 2000, 3);
d[1] = new Driver("Avi", "7596", 1980, 7);
d[2] = new Driver("Sara", "6051", 1995, 1);
d[3] = new Driver("Dani", "4472", 1998, 2);
d[4] = d[3];
int m = 0, s = 0;
int x = d[1].getTests();
d[1].setTests(d[3].getTests()+2);
d[3].setTests(x);
for (int i = 0; i < d.length; i++)
{
System.out.println (d[i].getTests());
s=s + d[i].getTests();
if (d[i].getYear() > 1995)
m++;
}
System.out.println ((double)s/d.length);
System.out.println (m);Driver [] d=new Driver[5];
d[0] = new Driver("Yossi", "1234", 2000, 3);
d[1] = new Driver("Avi", "7596", 1980, 7);
d[2] = new Driver("Sara", "6051", 1995, 1);
d[3] = new Driver("Dani", "4472", 1998, 2);
d[4] = d[3];
int m = 0, s = 0;
int x = d[1].GetTests();
d[1].SetTests(d[3].GetTests()+2);
d[3].SetTests(x);
for (int i = 0; i < d.Length; i++)
{
Console.WriteLine (d[i].GetTests());
s=s + d[i].GetTests();
if (d[i].GetYear() > 1995)
m++;
}
Console.WriteLine ((double)s/d.Length);
Console.WriteLine (m);כתוב פעולה המקבלת מערך של עצמים מסוג Driver, ומספר שלם num, ומחזירה מערך הכולל את השמות של הנהגים שעברו את הטסט בפחות מ- num מבחנים.
◂ פתרון מלא לשאלה 8
סעיף א
נוצרים 4 עצמים (d[4] מפנה לאותו עצם כמו d[3]); tests של Avi: 7→4, של Dani: 2→7. הפלט: 3, 4, 1, 7, 7, 4.4, 3 (כל אחד בשורה).
שלב 1 – יצירת העצמים. נוצרים ארבעה עצמים בלבד. ההוראה `d[4] = d[3]` אינה יוצרת עצם חדש: היא מעתיקה את ההפניה, ולכן d[3] ו-d[4] מפנים לאותו עצם (Dani). כל שינוי דרך d[3] נראה גם דרך d[4].
1. `x = d[1].getTests()` – .
2. `d[1].setTests(d[3].getTests()+2)` – ל-Avi מוצב .
3. `d[3].setTests(x)` – ל-Dani מוצב 7 (וזה גם הערך של d[4]).
מצב העצמים (החץ מסמן שינוי):
שלב 3 – הלולאה. עוברים על חמשת התאים (`d.length` = 5), מדפיסים את tests, צוברים אותם ב-s, ומונים ב-m את הנהגים שנולדו אחרי 1995:
שלב 4 – אחרי הלולאה. `(double)s/d.length` = (ההמרה ל-double מונעת חילוק בשלמים, שהיה נותן 4), ואחר כך מודפס .
3
4
1
7
7
4.4
3תשובה: הפלט הוא 3, 4, 1, 7, 7, 4.4, 3 (כל ערך בשורה נפרדת).
סעיף ב
מעבר ראשון סופר כמה נהגים עם `getTests() < num`; יוצרים מערך String בגודל זה; מעבר שני מעתיק את שמותיהם (`getName()`) ומחזירים אותו.
הרעיון: גודל המערך המוחזר צריך להיות בדיוק מספר הנהגים המתאימים, ואותו לא יודעים מראש. לכן עוברים על המערך פעמיים:
1. מעבר ראשון: סופרים כמה נהגים עברו בפחות מ-num מבחנים, כלומר `getTests() < num`.
2. יוצרים מערך מחרוזות בגודל שנספר.
3. מעבר שני: כל נהג מתאים – מעתיקים את שמו (`getName()`) למקום הפנוי הבא במערך החדש. המשתנה k מציין את המקום הזה ומתקדם רק כשמעתיקים שם.
4. מחזירים את המערך החדש.
אם אין אף נהג מתאים, מוחזר מערך באורך 0.
public static String[] fewTests(Driver[] arr, int num)
{
int count = 0; // מעבר 1: כמה נהגים מתאימים
for (int i = 0; i < arr.length; i++)
if (arr[i].getTests() < num)
count++;
String[] names = new String[count];
int k = 0; // המקום הבא הפנוי במערך החדש
for (int i = 0; i < arr.length; i++) // מעבר 2: העתקת השמות
{
if (arr[i].getTests() < num)
{
names[k] = arr[i].getName();
k++;
}
}
return names;
}public static string[] FewTests(Driver[] arr, int num)
{
int count = 0; // מעבר 1: כמה נהגים מתאימים
for (int i = 0; i < arr.Length; i++)
if (arr[i].GetTests() < num)
count++;
string[] names = new string[count];
int k = 0; // המקום הבא הפנוי במערך החדש
for (int i = 0; i < arr.Length; i++) // מעבר 2: העתקת השמות
{
if (arr[i].GetTests() < num)
{
names[k] = arr[i].GetName();
k++;
}
}
return names;
}דוגמה: עבור המערך d מסעיף א (אחרי השינויים: 3, 4, 1, 7, 7) ו- מוחזר המערך {"Yossi", "Avi", "Sara"}.
תשובה: הפעולה שלמעלה.
שאלה 9 · פלינדרום של אותיות גדולות במחרוזת ובמערך
"פָּלִינְדְרוֹם" הוא כל רצף תווים שקריאתו מימין לשמאל ומשמאל לימין היא זהה.
דוגמאות לפלינדרום:
`ABCCBA, 12A21, a0XX0a`
"פלינדרום גדולים", הוא פלינדרום המורכב רק מאותיות A..Z (שאר התווים לא משנה)
לדוגמה:
`fA%B##rkC1^BAdd`
הוא פלינדרום גדולים.
כתוב פעולה המקבלת מחרוזת ומחזירה true אם המחרוזת היא פלינדרום גדולים, אחרת הפעולה תחזיר false.
כתוב פעולה המקבלת מערך מחרוזות ומחזירה מחרוזת הארוכה ביותר שהיא "פלינדרום גדולים".
אפשר להניח שיש לפחות מחרוזת אחת שהיא פלינדרום גדולים.
◂ פתרון מלא לשאלה 9
סעיף א
בונים מחרוזת של האותיות A..Z בלבד (לפי הסדר) ובודקים בשני מצביעים שהיא פלינדרום; אם אין אותיות גדולות – false.
הרעיון: "שאר התווים לא משנה", ולכן מסננים אותם: בונים מחרוזת `caps` שמכילה רק את התווים בין 'A' ל-'Z', לפי סדר הופעתם. המחרוזת המקורית היא פלינדרום גדולים אם `caps` היא פלינדרום.
1. סינון: עוברים על כל התווים; תו `ch` שמקיים `ch >= 'A' && ch <= 'Z'` משורשר ל-`caps`.
2. בדיקת פלינדרום: מצביע `left` מתחילת `caps` ומצביע `right` מסופה. כל עוד `left < right`: אם התווים שונים – false; אחרת מקדמים את left ומחזירים את right. אם המצביעים נפגשו בלי סתירה – true.
3. אם אין במחרוזת אף אות גדולה, אין "פלינדרום המורכב מאותיות A..Z", ולכן מחזירים false.
בדיקה עם הדוגמה: במחרוזת `fA%B##rkC1^BAdd` האותיות הגדולות הן A, B, C, B, A, כלומר `caps = "ABCBA"`. משווים A–A, B–B, ומגיעים ל-C באמצע – פלינדרום, מוחזר true.
public static boolean isBigPalindrome(String s)
{
String caps = ""; // רק האותיות A..Z, לפי הסדר
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (ch >= 'A' && ch <= 'Z')
caps += ch;
}
if (caps.length() == 0)
return false; // אין אף אות גדולה
int left = 0, right = caps.length() - 1;
while (left < right)
{
if (caps.charAt(left) != caps.charAt(right))
return false;
left++;
right--;
}
return true;
}public static bool IsBigPalindrome(string s)
{
string caps = ""; // רק האותיות A..Z, לפי הסדר
for (int i = 0; i < s.Length; i++)
{
char ch = s[i];
if (ch >= 'A' && ch <= 'Z')
caps += ch;
}
if (caps.Length == 0)
return false; // אין אף אות גדולה
int left = 0, right = caps.Length - 1;
while (left < right)
{
if (caps[left] != caps[right])
return false;
left++;
right--;
}
return true;
}תשובה: הפעולה שלמעלה.
סעיף ב
מעבר על המערך; לכל מחרוזת שהפעולה מסעיף א מחזירה עבורה true משווים את אורכה לאורך הארוכה שנמצאה עד כה ומעדכנים; מחזירים אותה.
הרעיון: חיפוש מקסימום (לפי אורך), אבל רק בין המחרוזות שהן פלינדרום גדולים – את זה בודקים בפעולה מסעיף א.
1. המשתנה `longest` מאותחל ל-null ("עדיין לא נמצאה מחרוזת מתאימה"). אי אפשר לאתחל אותו ל-`arr[0]`, כי ייתכן ש-`arr[0]` אינה פלינדרום גדולים.
2. לכל מחרוזת במערך: אם היא פלינדרום גדולים, וגם (`longest` עדיין null או שהיא ארוכה מ-`longest`) – מעדכנים את `longest`.
3. מחזירים את `longest`. לפי ההנחה קיימת לפחות מחרוזת מתאימה אחת, ולכן לא מוחזר null.
האורך הנמדד הוא אורך המחרוזת כולה (`length()`). אם יש כמה מחרוזות באותו אורך מקסימלי, מוחזרת הראשונה מהן.
public static String longestBigPalindrome(String[] arr)
{
String longest = null;
for (int i = 0; i < arr.length; i++)
{
if (isBigPalindrome(arr[i]))
{
if (longest == null || arr[i].length() > longest.length())
longest = arr[i];
}
}
return longest;
}public static string LongestBigPalindrome(string[] arr)
{
string longest = null;
for (int i = 0; i < arr.Length; i++)
{
if (IsBigPalindrome(arr[i]))
{
if (longest == null || arr[i].Length > longest.Length)
longest = arr[i];
}
}
return longest;
}דוגמה: עבור המערך {"AB", "12A21", "fA%B##rkC1^BAdd", "ABCCBA", "xyz"}: "AB" ו-"xyz" אינן פלינדרום גדולים; מבין השאר הארוכה ביותר היא `fA%B##rkC1^BAdd` (15 תווים), והיא מוחזרת.
תשובה: הפעולה שלמעלה.
שאלה 10 · דרגת זוגיות של מספר ומערך מסודר לפי דרגות
נתונות ההגדרות הבאות:
•"דרגת הזוגיות" של מספר שלם היא כמות הספרות הזוגיות במספר.
לדוגמה:
"דרגת הזוגיות" של מספר 12347 היא 2.
"דרגת הזוגיות" של מספר 1860 היא 3.
"דרגת הזוגיות" של מספר 0 היא 1.
•"דרגת העל" של מערך חד-ממדי של מספרים שלמים היא "דרגת הזוגיות" הגבוהה ביותר שיש בו.
•מערך חד-ממדי של מספרים שלמים נקרא "מערך מסודר לפי דרגות הזוגיות" אם הוא כולל את כל דרגות הזוגיות מ- 0 עד "דרגת על" וכל דרגה מופיעה בו בדיוק פעם אחת.
כתוב פעולה אשר מקבלת מספר שלם ומחזירה את "דרגת הזוגיות" שלו.
כתוב פעולה אשר מקבלת מערך חד-ממדי ומחזירה את "דרגת העל" שלו.
כתוב פעולה אשר מקבלת מערך חד-ממדי. הפעולה מחזירה true אם המערך מסודר לפי דרגות הזוגיות, אחרת הפעולה מחזירה false.
מהן סיבוכיות זמן הריצה של כל הפעולות שכתבת? הסבר את תשובתך.
◂ פתרון מלא לשאלה 10
סעיף א
פירוק המספר (בערך מוחלט) לספרות בלולאת do-while וספירת הספרות הזוגיות; עבור 0 מוחזר 1.
הרעיון: מפרקים את המספר לספרות: הספרה הימנית היא `num % 10`, ו-`num / 10` מוחק אותה. ספרה זוגית אם `digit % 2 == 0`; סופרים כמה כאלה יש.
1. אם המספר שלילי הופכים אותו לחיובי – הסימן לא משנה את הספרות (וכך גם `%` מחזיר ספרות חיוביות).
2. משתמשים בלולאת do-while ולא while: כך גם המספר 0 עובר סיבוב אחד, הספרה 0 נספרת כזוגית, ומוחזר 1, כפי שנדרש בהגדרה. בלולאת while רגילה עבור 0 הלולאה לא הייתה מתבצעת והיה מוחזר 0.
3. הלולאה ממשיכה כל עוד נשארו ספרות (`num > 0`).
בדיקה: 12347 – הספרות הזוגיות 2, 4, כלומר 2. 1860 – הספרות 8, 6, 0, כלומר 3. 0 – כלומר 1. כמו בהגדרה.
public static int parityDegree(int num)
{
if (num < 0)
num = -num; // הסימן לא משנה את הספרות
int count = 0;
do
{
int digit = num % 10; // הספרה הימנית
if (digit % 2 == 0)
count++;
num = num / 10; // מוחקים אותה
} while (num > 0);
return count;
}public static int ParityDegree(int num)
{
if (num < 0)
num = -num; // הסימן לא משנה את הספרות
int count = 0;
do
{
int digit = num % 10; // הספרה הימנית
if (digit % 2 == 0)
count++;
num = num / 10; // מוחקים אותה
} while (num > 0);
return count;
}תשובה: הפעולה שלמעלה.
סעיף ב
מקסימום של `parityDegree(arr[i])` על כל איברי המערך.
הרעיון: "דרגת העל" היא המקסימום של דרגות הזוגיות של האיברים. זהו חיפוש מקסימום רגיל, כשלכל איבר מחשבים את הדרגה בעזרת הפעולה מסעיף א.
1. מתחילים מהדרגה של האיבר הראשון (מניחים שהמערך אינו ריק).
2. עוברים על שאר האיברים; אם דרגת האיבר גדולה מהמקסימום הנוכחי – מעדכנים.
3. מחזירים את המקסימום.
public static int superDegree(int[] arr)
{
int max = parityDegree(arr[0]);
for (int i = 1; i < arr.length; i++)
{
int d = parityDegree(arr[i]);
if (d > max)
max = d;
}
return max;
}public static int SuperDegree(int[] arr)
{
int max = ParityDegree(arr[0]);
for (int i = 1; i < arr.Length; i++)
{
int d = ParityDegree(arr[i]);
if (d > max)
max = d;
}
return max;
}דוגמה: עבור {12347, 1860, 0, 135} הדרגות הן 2, 3, 1, 0, ולכן דרגת העל היא 3.
תשובה: הפעולה שלמעלה.
סעיף ג
מחשבים sup = דרגת העל; מערך מונים `count` בגודל sup+1 סופר כמה איברים יש מכל דרגה; מחזירים true רק אם `count[d] == 1` לכל .
הרעיון: לפי ההגדרה, כל דרגה מ-0 עד דרגת העל צריכה להופיע בדיוק פעם אחת. נשתמש במערך מונים:
1. מחשבים `sup` = דרגת העל של המערך (סעיף ב). אף איבר אינו בעל דרגה גדולה מ-sup.
2. יוצרים מערך `count` בגודל (מקומות ), כך ש-`count[d]` יספור כמה איברים יש בדרגה d.
3. עוברים על המערך ומגדילים ב-1 את `count[parityDegree(arr[i])]`.
4. עוברים על `count`: אם ערך כלשהו שונה מ-1 – דרגה חסרה (0) או מופיעה יותר מפעם אחת (2 או יותר) – מחזירים false.
5. אחרת מחזירים true.
הסדר של האיברים במערך לא משנה – ההגדרה דורשת רק שכל דרגה תופיע פעם אחת.
public static boolean isOrdered(int[] arr)
{
int sup = superDegree(arr);
int[] count = new int[sup + 1]; // count[d] = כמה איברים בדרגה d
for (int i = 0; i < arr.length; i++)
count[parityDegree(arr[i])]++;
for (int d = 0; d <= sup; d++)
if (count[d] != 1) // דרגה חסרה או כפולה
return false;
return true;
}public static bool IsOrdered(int[] arr)
{
int sup = SuperDegree(arr);
int[] count = new int[sup + 1]; // count[d] = כמה איברים בדרגה d
for (int i = 0; i < arr.Length; i++)
count[ParityDegree(arr[i])]++;
for (int d = 0; d <= sup; d++)
if (count[d] != 1) // דרגה חסרה או כפולה
return false;
return true;
}- {135, 4, 1860, 24}: הדרגות 0, 1, 3, 2; דרגת העל 3, וכל אחת מהדרגות 0, 1, 2, 3 מופיעה פעם אחת – true.
- {135, 12347, 1860, 7}: הדרגות 0, 2, 3, 0; הדרגה 0 מופיעה פעמיים והדרגה 1 חסרה – false.
תשובה: הפעולה שלמעלה.
סעיף ד
א: ( = מספר הספרות, לכל היותר 10 ב-int, כלומר ); ב: ; ג: .
נסמן = אורך המערך ו- = מספר הספרות של מספר.
1. סעיף א (`parityDegree`): הלולאה מתבצעת פעם אחת לכל ספרה, ולכן . מספר מטיפוס int הוא בעל 10 ספרות לכל היותר, כלומר זו סיבוכיות קבועה, (ובמונחי ערך המספר: ).
2. סעיף ב (`superDegree`): לולאה אחת על האיברים, ובכל סיבוב קריאה לפעולה מסעיף א: , כלומר .
3. סעיף ג (`isOrdered`): קריאה לסעיף ב – ; לולאה על המערך עם קריאה לסעיף א – ; לולאה על מערך המונים – סיבובים (כי יש לכל היותר 10 ספרות), כלומר . סך הכול .
תשובה: סעיף א – (לינארי במספר הספרות); סעיפים ב ו-ג – .
שאלה 11 · רקורסיה על מערך: סכומי סיפא וסכומי שכנים
לפניך הפעולה one המקבלת מערך של מספרים שלמים, ושני מספרים נוספים:
public static void one (int[] a, int start, int stop)
{
if(start < stop)
{
one(a, start+1, stop);
a[start]=a[start]+a[start+1];
}
}public static void One (int[] a, int start, int stop)
{
if(start < stop)
{
One(a, start+1, stop);
a[start]=a[start]+a[start+1];
}
}עקוב אחר זימון one (b, 0, b.length-1) עבור המערך:
וציין מה יהיה תוכן איברי המערך בסיום ביצוע פעולה.
מהי מטרת הפעולה one? בתשובה יש להתייחס למערך שפעולה מקבלת כפרמטר.
לפניך פעולה אחרת, two, המקבלת מערך של מספרים שלמים, ושני מספרים נוספים.
public static void two (int[] a, int start, int stop)
{
if(start < stop)
{
a[start]=a[start]+a[start+1];
two (a, start+1, stop);
}
}public static void Two (int[] a, int start, int stop)
{
if(start < stop)
{
a[start]=a[start]+a[start+1];
Two (a, start+1, stop);
}
}אחרי זימון two(c, 0, c.length-1) תוכן של מערך c הוא:
מה היה התוכן של c לפני ביצוע הזימון?
מהי מטרת הפעולה two? בתשובה יש להתייחס למערך שהפעולה מקבלת כפרמטר.
◂ פתרון מלא לשאלה 11
סעיף א
b = {84, 74, 69, 66, 50, 30}
הרעיון: הקריאה הרקורסיבית מופיעה לפני ההשמה. לכן הפעולה קודם "יורדת" עד `start == stop` בלי לשנות דבר, וההשמות מתבצעות בדרך חזרה – מהסוף להתחלה. כשמתבצעת ההשמה ל-`a[start]`, התא `a[start+1]` כבר עודכן.
הזימון הוא `one(b, 0, 5)` (כי `b.length-1` = 5). שרשרת הקריאות: one(b,0,5) → one(b,1,5) → … → one(b,5,5), שבה שקרי והיא חוזרת מיד. בטבלה – סדר החזרה מלמטה למעלה:
תשובה: בסיום: b = {84, 74, 69, 66, 50, 30}.
כל תא a[i] בתחום start..stop הופך לסכום האיברים המקוריים מ-a[i] ועד a[stop] (סכום "סיפא"); a[stop] ושאר התאים לא משתנים.
ההשמות מתבצעות מהסוף להתחלה: `a[stop]` לא משתנה, `a[stop-1]` הופך ל-, ובכל צעד `a[start]` מקבל את ערכו המקורי ועוד `a[start+1]`, שכבר מכיל את סכום כל האיברים שמימינו עד stop.
לכן בסיום, לכל :
( = הערכים המקוריים). בסעיף 1: , וכן הלאה.
הפעולה משנה את המערך עצמו (מערך מועבר כהפניה), ולכן השינוי נשאר גם אחרי הזימון.
תשובה: הפעולה מחליפה כל איבר בתחום start..stop בסכום שלו ושל כל האיברים שאחריו עד המקום stop (סכומים מצטברים מהסוף).
סעיף ב
c = {−1, 11, −3, 15, 5, 10}
הרעיון: כאן ההשמה מתבצעת לפני הקריאה הרקורסיבית, ולכן ההשמות מתבצעות מההתחלה לסוף. כשמעדכנים את `a[i]`, התא `a[i+1]` עוד לא שונה, נסמן ב- את הערכים לפני הזימון וב- את הערכים אחריו. אז:
לכל , והתא האחרון לא משתנה: .
מכאן , ולכן משחזרים מהסוף להתחלה:
התקבל בדיוק המערך הנתון.
תשובה: לפני הזימון: c = {−1, 11, −3, 15, 5, 10}.
כל תא a[i] עבור start ≤ i < stop הופך לסכום שלו ושל השכן הימני המקורי a[i+1]; a[stop] לא משתנה.
בכל קריאה `a[start]` מקבל `a[start] + a[start+1]`, ורק אחר כך עוברים לתא הבא. לכן בזמן העדכון של כל תא, השכן שלו עוד מכיל את ערכו המקורי. בסיום, לכל :
והתא `a[stop]` נשאר כמו שהיה.
ההבדל בין one לבין two הוא רק בסדר שתי השורות: ב-one ההשמה אחרי הקריאה (מהסוף להתחלה, ולכן מצטברים כל הערכים שמימין), וב-two ההשמה לפני הקריאה (מההתחלה לסוף, ולכן נוסף רק השכן הקרוב).
תשובה: הפעולה מחליפה כל איבר בתחום start..stop−1 בסכום שלו ושל האיבר שאחריו (לפי הערכים המקוריים); האיבר במקום stop לא משתנה.
שאלה 12 · מערכת לניהול משימות לפי עדיפות
כדי לממש מערכת לניהול משימות הגדירו את המחלקה Task (משימה) שיש לה ארבע תכונות:
•כותרת המשימה - title מטיפוס מחרוזת – String.
•מספר הדקות הנדרש לסיום ביצוע המשימה - minutes מטיפוס מספר שלם – int.
•דרגת העדיפות של המשימה - priority – שהיא מספר שלם חיובי - int. (מספר גבוה יותר מייצג דרגת עדיפות גבוהה יותר).
•האם המשימה בוצעה? - isComplete מטיפוס בוליאני- boolean (הערך false משמעותו שהמשימה לא הסתיימה).
ניתן להניח כי פעולות get, set הוגדרו לכל התכונות.
כדי לנהל את המשימות הוגדרה המחלקה TaskManager המכילה 2 תכונות:
•מערך של משימות – tasks - בגודל 100 של Task.
•מספר שלם numOfTasks המציין את מספר המשימות שיש כרגע.
בכל הפעולות במחלקה זו עליכם לוודא שהערך numOfTasks מעודכן.
כתוב במחלקה Task את הפעולה `int doIt(int num)`.
הפעולה מקבלת מספר דקות num לביצוע המשימה. אם הפרמטר num גדול ממספר הדקות הנדרש לביצוע המשימה, הפעולה מחזירה את מספר הדקות ה"עודפות" (כלומר הדקות שיותר ממה שנדרש), אחרת היא מחזירה 0.
הפעולה גם מעדכנת תכונות minutes ו- isComplete בהתאם.
כתוב במחלקה TaskManager את הפעולה `boolean addTask(Task t)`.
הפעולה מקבלת משימה חדשה t ומכניסה אותה למקום הראשון הפנוי במערך המשימות, אם אין מקום, הפעולה תחפש משימה שהסתיימה כבר, ותכניס במקומה את המשימה החדשה.
הפעולה תחזיר true אם המשימה הוכנסה, אחרת הפעולה תחזיר false.
הפעולה גם תעדכן את התכונה numOfTasks בהתאם.
כתוב במחלקה TaskManager את הפעולה `int importantTask( )`.
הפעולה מחזירה את המיקום במערך tasks של המשימה בעדיפות הגבוהה ביותר שהביצוע שלה עוד לא הסתיים. אם יש כמה פעולות בעדיפות הגבוהה ביותר שלא הושלמו, הפעולה תחזיר מיקום (אינדקס) של אחת מהן. אם אין אף משימה שביצועה עדיין לא הסתיים, הפעולה תחזיר את הערך -1.
כתוב במחלקה TaskManager את הפעולה `void work(int num)`.
הפעולה מקבלת מספר שלם המייצג את הזמן בדקות שהוקצה לעבודה. הפעולה תשקיע את הזמן בביצוע משימה כלשהי שעדיין לא הסתיימה ובעדיפות הגבוהה ביותר שיש במערך tasks.
הפעולה תעדכן את תכונות המשימה בהתאם. אם אחרי ביצוע המשימה יישאר זמן, הפעולה תמצא משימה נוספת בעדיפות הגבוהה ביותר שעוד לא הסתיימה ותטפל בה.
הפעולה תסיים את העבודה כאשר יסתיים ביצוע של כל המשימות או יגמר זמן שהוקצה לעבודה.
◂ פתרון מלא לשאלה 12
סעיף א
אם : מחזירים , ומציבים minutes = 0 ו-isComplete = true; אחרת minutes -= num ומחזירים 0.
הרעיון: minutes הוא הזמן שעוד נשאר כדי לסיים את המשימה. יש שני מקרים:
1. – הזמן מספיק: המשימה מסתיימת. הדקות העודפות הן ; אחרי הסיום לא נשאר זמן נדרש (`minutes = 0`) והמשימה בוצעה (`isComplete = true`). כאשר העודף הוא 0 – בדיוק כפי שנדרש ("אחרת היא מחזירה 0"), והמשימה מסתיימת.
2. – הזמן לא מספיק: עובדים num דקות, כך שנשארות דקות; המשימה לא הסתיימה, ומחזירים 0.
את העודף שומרים במשתנה לפני שמאפסים את minutes, אחרת החישוב היה משתמש בערך 0.
public int doIt(int num)
{
if (num >= this.minutes) // הזמן מספיק לסיום המשימה
{
int extra = num - this.minutes; // הדקות העודפות
this.minutes = 0;
this.isComplete = true;
return extra;
}
this.minutes = this.minutes - num; // המשימה התקדמה אך לא הסתיימה
return 0;
}public int DoIt(int num)
{
if (num >= this.minutes) // הזמן מספיק לסיום המשימה
{
int extra = num - this.minutes; // הדקות העודפות
this.minutes = 0;
this.isComplete = true;
return extra;
}
this.minutes = this.minutes - num; // המשימה התקדמה אך לא הסתיימה
return 0;
}דוגמה: למשימה שנדרשות לה 10 דקות: `doIt(4)` מחזירה 0 ונשארות 6 דקות; אחר כך `doIt(10)` מחזירה 4, minutes = 0 ו-isComplete = true.
תשובה: הפעולה שלמעלה.
סעיף ב
מחפשים את התא הראשון שהוא null – מכניסים, numOfTasks++, true; אם אין, מחפשים משימה עם isComplete – מחליפים (numOfTasks לא משתנה), true; אחרת false.
הרעיון: שני שלבי חיפוש לפי סדר העדיפות שבשאלה:
1. מקום פנוי: תא פנוי במערך הוא תא שערכו null. עוברים מההתחלה, ובתא ה-null הראשון מכניסים את t. נוספה משימה, ולכן מגדילים את numOfTasks ב-1, ומחזירים true.
2. אין מקום פנוי: כל 100 התאים מלאים. מחפשים משימה שהסתיימה (`getIsComplete()` מחזירה true) ומכניסים את t במקומה. משימה אחת יצאה ואחת נכנסה, ולכן numOfTasks לא משתנה. מחזירים true.
3. אם המערך מלא ואין משימה שהסתיימה – לא הכנסנו דבר, מחזירים false.
בשלב 2 כל התאים מלאים (אחרת היינו נעצרים בשלב 1), ולכן אין צורך לבדוק null.
public boolean addTask(Task t)
{
for (int i = 0; i < this.tasks.length; i++) // חיפוש מקום פנוי
{
if (this.tasks[i] == null)
{
this.tasks[i] = t;
this.numOfTasks++; // נוספה משימה
return true;
}
}
for (int i = 0; i < this.tasks.length; i++) // אין מקום: משימה שהסתיימה
{
if (this.tasks[i].getIsComplete())
{
this.tasks[i] = t; // החלפה: מספר המשימות לא משתנה
return true;
}
}
return false;
}public bool AddTask(Task t)
{
for (int i = 0; i < this.tasks.Length; i++) // חיפוש מקום פנוי
{
if (this.tasks[i] == null)
{
this.tasks[i] = t;
this.numOfTasks++; // נוספה משימה
return true;
}
}
for (int i = 0; i < this.tasks.Length; i++) // אין מקום: משימה שהסתיימה
{
if (this.tasks[i].GetIsComplete())
{
this.tasks[i] = t; // החלפה: מספר המשימות לא משתנה
return true;
}
}
return false;
}תשובה: הפעולה שלמעלה.
סעיף ג
חיפוש מקסימום של priority בין התאים שאינם null ו-isComplete שלהם false; index מאותחל ל-1- ומוחזר.
הרעיון: חיפוש מקסימום, אבל רק בין המשימות המתאימות – משימות שקיימות (התא אינו null) ושעדיין לא הסתיימו (`!getIsComplete()`).
1. `index` מאותחל ל-1-, כלומר "עדיין לא נמצאה משימה מתאימה". אם לא תימצא אף אחת, זה בדיוק הערך שצריך להחזיר.
2. עבור כל משימה מתאימה: אם `index` עדיין 1- (זו המשימה המתאימה הראשונה), או שהעדיפות שלה גבוהה מהעדיפות של המשימה במקום `index` – מעדכנים את `index` למקום הנוכחי.
3. מחזירים את `index`.
ההשוואה היא `>` ולכן במקרה של שוויון בעדיפות מוחזרת הראשונה מבין המשימות – השאלה מאפשרת להחזיר כל אחת מהן.
public int importantTask()
{
int index = -1;
for (int i = 0; i < this.tasks.length; i++)
{
if (this.tasks[i] != null && !this.tasks[i].getIsComplete())
{
if (index == -1 || this.tasks[i].getPriority() > this.tasks[index].getPriority())
index = i;
}
}
return index;
}public int ImportantTask()
{
int index = -1;
for (int i = 0; i < this.tasks.Length; i++)
{
if (this.tasks[i] != null && !this.tasks[i].GetIsComplete())
{
if (index == -1 || this.tasks[i].GetPriority() > this.tasks[index].GetPriority())
index = i;
}
}
return index;
}תשובה: הפעולה שלמעלה.
סעיף ד
לולאה כל עוד num > 0: i = importantTask(); אם i == -1 מסיימים; אחרת num = tasks[i].doIt(num).
הרעיון: משלבים את שתי הפעולות שכבר כתבנו:
•`importantTask()` (סעיף ג) מוצאת את המשימה הבאה שצריך לטפל בה.
•`doIt(num)` (סעיף א) משקיעה בה את הזמן, מעדכנת את minutes ו-isComplete, ומחזירה את הזמן שנשאר (העודף).
1. כל עוד נשאר זמן (`num > 0`): מוצאים את המשימה החשובה ביותר שלא הסתיימה.
2. אם אין כזו (`importantTask()` מחזירה 1-) – כל המשימות הסתיימו, ומסיימים.
3. אחרת מפעילים עליה את `doIt(num)`, וה-num החדש הוא הזמן העודף שהוחזר.
4. אם הזמן לא הספיק לסיום המשימה, `doIt` מחזירה 0 והלולאה נעצרת – הזמן נגמר.
המשימה שהסתיימה מקבלת isComplete = true, ולכן בסיבוב הבא `importantTask()` כבר לא תבחר בה. numOfTasks לא משתנה, כי לא נוספות ולא נמחקות משימות.
public void work(int num)
{
while (num > 0)
{
int i = this.importantTask();
if (i == -1)
return; // כל המשימות הסתיימו
num = this.tasks[i].doIt(num); // הזמן שנשאר אחרי המשימה
}
}public void Work(int num)
{
while (num > 0)
{
int i = this.ImportantTask();
if (i == -1)
return; // כל המשימות הסתיימו
num = this.tasks[i].DoIt(num); // הזמן שנשאר אחרי המשימה
}
}דוגמה: משימות A (30 דקות, עדיפות 2), B (20, עדיפות 5), C (50, עדיפות 5), D (10, עדיפות 1), ו-`work(45)`: נבחרת B (העדיפות הגבוהה ביותר, הראשונה מבין השתיים), מסתיימת אחרי 20 דקות ונשארות 25; אחר כך נבחרת C, ונשארות לה דקות; `doIt` מחזירה 0 והעבודה נגמרת.
תשובה: הפעולה שלמעלה.
שאלה 13 · רקורסיה על מחרוזות: בדיקת תמורה (אנגרמה)
נתונה פעולה רקורסיבית:
public static boolean what (String s1, String s2)
{
if(s1.length() != s2.length())
return false;
if(s1.length() == 0)
return true;
int place = s2.indexOf(s1.charAt(0));
if(place < 0)
return false;
else
{
String a = s2.substring(0, place);
String b = s2.substring(place+1);
String c = a.concat(b);
return what(s1.substring(1),c);
}
}public static bool What (string s1, string s2)
{
if(s1.Length != s2.Length)
return false;
if(s1.Length == 0)
return true;
int place = s2.IndexOf(s1[0]);
if(place < 0)
return false;
else
{
string a = s2.Substring(0, place);
string b = s2.Substring(place+1);
string c = String.Concat(a, b);
return What(s1.Substring(1),c);
}
}עקוב אחרי זימון הפעולה what(s1, s2) עבור s1="hello", s2= "oeloh" ורשום מה תהיה תוצאת הזימון.
תן דוגמה למחרוזת s3 כך שתוצאת הזימון what("hello", s3) תהיה שונה מהתוצאה של סעיף א'.
מה מבצעת הפעולה what באופן כללי?
כתוב את הפעולה what המבצעת אותה משימה בצורה לא רקורסיבית.
◂ פתרון מלא לשאלה 13
סעיף א
false
הרעיון: בכל קריאה הפעולה לוקחת את התו הראשון של s1, מחפשת אותו ב-s2, ואם מצאה – מוחקת אותו מ-s2 (המחרוזת c היא s2 בלי התו במקום place) וממשיכה עם שארית s1 ועם c.
בקריאה 4 התו 'l' לא נמצא ב-"oo" (ב-"oeloh" יש רק 'l' אחד, והוא כבר נוצל בקריאה 3), ולכן מוחזר false. הערך הזה עובר כמו שהוא בחזרה דרך כל הקריאות (`return what(...)`).
תשובה: `what("hello", "oeloh")` מחזירה false.
סעיף ב
למשל s3 = "olleh" – יוחזר true.
צריך s3 שעבורה יוחזר true, כלומר מחרוזת באורך 5 עם אותם תווים כמו "hello" (h פעם אחת, e פעם אחת, l פעמיים, o פעם אחת), בסדר כלשהו. ניקח s3 = "olleh":
תשובה: s3 = "olleh" (וכל סידור אחר של האותיות של "hello"), ואז מוחזר true.
סעיף ג
מחזירה true אם s2 מורכבת בדיוק מאותם תווים כמו s1 (כל תו באותו מספר פעמים, בסדר כלשהו) – כלומר s2 היא תמורה (אנגרמה) של s1; אחרת false.
1. אם האורכים שונים – אי אפשר ששתי המחרוזות יכילו אותם תווים, ומוחזר false.
2. כל קריאה "מתאימה" את התו הראשון של s1 לתו זהה ב-s2 ומוחקת אותו מ-s2, כך שכל תו של s2 יכול לשמש פעם אחת בלבד. אם תו של s1 לא נמצא (כולל מקרה שבו כל המופעים שלו כבר נוצלו) – מוחזר false.
3. אם כל התווים של s1 הותאמו, שתי המחרוזות מתרוקנות יחד ומוחזר true.
לכן מוחזר true בדיוק כאשר בשתי המחרוזות אותם תווים, וכל תו מופיע באותו מספר פעמים, בלי קשר לסדר.
תשובה: הפעולה בודקת אם s2 היא תמורה (סידור מחדש, אנגרמה) של s1.
סעיף ד
בודקים שהאורכים שווים; בלולאה על התווים של s1: מחפשים כל תו ב-s2 (indexOf), אם אינו נמצא – false, אחרת מוחקים אותו מ-s2; בסוף true.
הרעיון: הרקורסיה מעבדת בכל קריאה את התו הבא של s1. את אותו דבר עושה לולאה שעוברת על התווים של s1 לפי הסדר, ומחזיקה במשתנה s2 את מה שנשאר ממנה:
1. אם האורכים שונים – false (כמו בתנאי הראשון של הפעולה הרקורסיבית).
2. לכל תו `s1.charAt(i)`: מחפשים אותו ב-s2 בעזרת `indexOf`. אם לא נמצא – false.
3. אם נמצא – מוחקים אותו מ-s2: `s2.substring(0, place) + s2.substring(place + 1)`, בדיוק כמו המחרוזת c בפעולה המקורית.
4. אם הלולאה הסתיימה, כל התווים הותאמו (ומכיוון שהאורכים שווים, s2 התרוקנה) – true. זה מקביל לתנאי העצירה `s1.length() == 0`.
השינוי של s2 בתוך הפעולה לא משפיע על המחרוזת של מי שקרא לפעולה, כי מחרוזות אינן ניתנות לשינוי, וההשמה משנה רק את הפרמטר המקומי.
public static boolean what(String s1, String s2)
{
if (s1.length() != s2.length())
return false;
for (int i = 0; i < s1.length(); i++)
{
int place = s2.indexOf(s1.charAt(i));
if (place < 0)
return false; // התו חסר ב-s2 (או שכבר נוצל)
s2 = s2.substring(0, place) + s2.substring(place + 1); // מוחקים אותו
}
return true;
}public static bool What(string s1, string s2)
{
if (s1.Length != s2.Length)
return false;
for (int i = 0; i < s1.Length; i++)
{
int place = s2.IndexOf(s1[i]);
if (place < 0)
return false; // התו חסר ב-s2 (או שכבר נוצל)
s2 = s2.Substring(0, place) + s2.Substring(place + 1); // מוחקים אותו
}
return true;
}בדיקה: `what("hello", "oeloh")` מחזירה false ו-`what("hello", "olleh")` מחזירה true, כמו הגרסה הרקורסיבית.
תשובה: הפעולה שלמעלה.