מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2022 מועד א'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2022 מועד א', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 15)
בכל מבחן 14 שאלות.
שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה – 10 נקודות.
שאלות 7-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 12 נקודות
שאלות 11-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 18 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטת מחרוזות עד זקיף וספירה
כתבו קטע תוכנית הקולט מחרוזות עד שתיקלט מחרוזת המתחילה ומסתיימת באות 'A'.
הקטע יחשב וידפיס את מספר המחרוזות אשר מתחילות או מסתיימות באות 'Z'.
◂ פתרון מלא לשאלה 1
פתרון
לולאת while שקולטת מחרוזות כל עוד המחרוזת אינה מתחילה ומסתיימת ב-'A'; מונה גדל כאשר התו הראשון או האחרון הוא 'Z'; בסוף מדפיסים את המונה.
הרעיון: מספר המחרוזות אינו ידוע מראש, ולכן משתמשים בלולאת while עם "זקיף": קולטים מחרוזת לפני הלולאה, וכל עוד היא אינה מחרוזת הסיום מטפלים בה וקולטים את הבאה.
1. התו הראשון של המחרוזת הוא `str.charAt(0)` והתו האחרון הוא `str.charAt(str.length() - 1)`.
2. תנאי הסיום: התו הראשון הוא 'A' וגם התו האחרון הוא 'A'. הלולאה רצה כל עוד התנאי הזה לא מתקיים, ולכן תנאי הלולאה הוא השלילה שלו: `!(first == 'A' && last == 'A')`.
3. בתוך הלולאה סופרים מחרוזת אם התו הראשון הוא 'Z' או התו האחרון הוא 'Z' (מחרוזת כמו "ZOZ" שמתחילה וגם מסתיימת ב-'Z' נספרת פעם אחת בלבד, כי זה `if` אחד עם `||`).
4. מחרוזת הסיום עצמה אינה נספרת: היא מתחילה ב-'A', ולכן ממילא אינה מתחילה ב-'Z', ובכל מקרה הלולאה נעצרת לפני הטיפול בה.
import java.util.Scanner;
public class Q1
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int count = 0; // מונה מחרוזות שמתחילות או מסתיימות ב-'Z'
String str = in.next();
// ממשיכים כל עוד המחרוזת אינה מתחילה ומסתיימת ב-'A'
while (!(str.charAt(0) == 'A' && str.charAt(str.length() - 1) == 'A'))
{
if (str.charAt(0) == 'Z' || str.charAt(str.length() - 1) == 'Z')
count++;
str = in.next();
}
System.out.println("Number of strings: " + count);
}
}using System;
class Q1
{
static void Main(string[] args)
{
int count = 0; // מונה מחרוזות שמתחילות או מסתיימות ב-'Z'
string str = Console.ReadLine();
// ממשיכים כל עוד המחרוזת אינה מתחילה ומסתיימת ב-'A'
while (!(str[0] == 'A' && str[str.Length - 1] == 'A'))
{
if (str[0] == 'Z' || str[str.Length - 1] == 'Z')
count++;
str = Console.ReadLine();
}
Console.WriteLine("Number of strings: " + count);
}
}דוגמה: עבור הקלט ZOO, baZ, ABC, hello, Z, AXA יודפס 3 (נספרו ZOO, baZ ו-Z; המחרוזת AXA מסיימת את הקלט).
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · מעקב אחר פעולת חלוקה של מערך
נתונה פעולה הבאה:
public static void what(int[] arr, int num)
{
int left = 0;
int right = arr.length-1;
while(left!=right)
{
if(arr[left] < num)
left++;
else
if(arr[right] > num)
right--;
else
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
}public static void What(int[] arr, int num)
{
int left = 0;
int right = arr.Length-1;
while(left!=right)
{
if(arr[left] < num)
left++;
else
if(arr[right] > num)
right--;
else
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
}נתון מערך מספרים שלמים `int[] arr={18, 10, 3, 12, 17, 1};`.
עקבו בעזרת טבלת המעקב אחרי זימון הפעולה what(arr, 4) ורשמו מה יהיה תוכן של המערך arr אחרי ביצוע הפעולה.
נתון מערך מספרים שלמים `int[] arr={18, 10, 3, 12, 17, 1}`
תנו דוגמה של מספר num כך שתוכן המערך הנתון arr לא ישתנה אחרי זימון הפעולה what(arr, num)
מה מבצעת הפעולה what(a, num) באופן כללי?
◂ פתרון מלא לשאלה 2
סעיף א
אחרי הזימון: arr = {1, 3, 10, 12, 17, 18}.
נעקוב אחרי הלולאה. בכל סיבוב בודקים קודם את `arr[left] < num`; אם לא – את `arr[right] > num`; ואם גם זה לא – מחליפים בין `arr[left]` ל-`arr[right]`. כאן num = 4, ובהתחלה left = 0, right = 5.
אחרי הסיבוב השביעי left = right = 2, תנאי הלולאה `left != right` נכשל והפעולה מסתיימת.
תשובה: תוכן המערך: 1, 3, 10, 12, 17, 18.
סעיף ב
למשל num = 100 (כל num גדול מ-18, או כל num קטן מ-1, למשל 0).
המערך משתנה רק כאשר מתבצעת החלפה, כלומר כאשר `arr[left] >= num` וגם `arr[right] <= num`. נבחר num שעבורו זה לא קורה אף פעם.
1. ניקח num = 100, גדול מכל איברי המערך. אז בכל סיבוב `arr[left] < 100` מתקיים, ולכן רק left גדל: 0, 1, 2, 3, 4, 5. כאשר left = 5 = right הלולאה נעצרת, ולא בוצעה אף החלפה.
2. באותו אופן גם num קטן מכל האיברים (למשל num = 0) מתאים: אז `arr[left] < 0` אף פעם לא מתקיים, אבל `arr[right] > 0` תמיד מתקיים, ולכן רק right קטן עד שהוא פוגש את left.
תשובה: למשל num = 100 (כל מספר גדול מ-18 או קטן מ-1).
סעיף ג
מסדרת מחדש את המערך כך שהאיברים הקטנים מ-num נמצאים בתחילתו והאיברים הגדולים מ-num בסופו (חלוקה סביב num).
1. left מתקדם ימינה כל עוד הוא עובר על איברים קטנים מ-num – הם כבר במקום טוב (בצד שמאל).
2. right מתקדם שמאלה כל עוד הוא עובר על איברים גדולים מ-num – הם כבר במקום טוב (בצד ימין).
3. כאשר left נעצר על איבר שאינו קטן מ-num ו-right נעצר על איבר שאינו גדול מ-num, שניהם "במקום הלא נכון", ולכן מחליפים ביניהם.
4. הלולאה מסתיימת כאשר left ו-right נפגשים. בסוף, כל האיברים משמאל לנקודת המפגש קטנים מ-num וכל האיברים מימינה גדולים מ-num (כמו שלב החלוקה במיון מהיר). הסדר בתוך כל צד אינו נשמר בהכרח, וזה אינו מיון.
הערה: אם num מופיע במערך יותר מפעם אחת, הפעולה עלולה להיכנס ללולאה אינסופית (שני ערכים השווים ל-num מוחלפים זה בזה שוב ושוב). במערך שבשאלה זה לא קורה.
תשובה: הפעולה מחלקת את המערך: איברים קטנים מ-num מועברים לתחילת המערך ואיברים גדולים מ-num לסופו.
שאלה 3 · בדיקת מערך מאוזן וסיבוכיות
מערך של מספרים שלמים נקרא "מאוזן" אם הוא עונה על תנאים הבאים:
•כמות האיברים החיוביים שווה לכמות האיברים השלילים.
•המערך לא כולל אפסים.
כתבו פעולה המקבלת מערך של מספרים שלמים ובודקת אם הוא "מערך מאוזן".
אם כן – הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
מהי סיבוכיות הפעולה מסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
מעבר אחד על המערך: אם יש 0 מחזירים false; אחרת סופרים חיוביים ושליליים ומחזירים countPos == countNeg.
הרעיון: עוברים פעם אחת על המערך ומטפלים בכל איבר לפי הסימן שלו.
1. אם נמצא איבר השווה ל-0, התנאי השני מופר ואפשר להחזיר false מיד, בלי להמשיך.
2. אחרת האיבר חיובי או שלילי, ומגדילים את המונה המתאים: countPos או countNeg.
3. בסוף הלולאה (אין אפסים) המערך מאוזן בדיוק כאשר שני המונים שווים, ולכן מחזירים את תוצאת ההשוואה `countPos == countNeg`.
public static boolean isBalanced(int[] arr)
{
int countPos = 0; // מונה איברים חיוביים
int countNeg = 0; // מונה איברים שליליים
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
return false; // יש אפס - המערך אינו מאוזן
if (arr[i] > 0)
countPos++;
else
countNeg++;
}
return countPos == countNeg;
}public static bool IsBalanced(int[] arr)
{
int countPos = 0; // מונה איברים חיוביים
int countNeg = 0; // מונה איברים שליליים
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == 0)
return false; // יש אפס - המערך אינו מאוזן
if (arr[i] > 0)
countPos++;
else
countNeg++;
}
return countPos == countNeg;
}דוגמה: עבור {3, -1, 5, -7} יש שני חיוביים ושני שליליים ואין אפסים – מוחזר true. עבור {3, -1, 0, -7, 2} מוחזר false כבר כשמגיעים ל-0.
תשובה: הפעולה שלמעלה.
סעיף ב
, כאשר n הוא אורך המערך.
1. נסמן ב-n את אורך המערך.
2. הפעולה עוברת על המערך בלולאה אחת, וכל איבר נבדק פעם אחת לכל היותר.
3. בכל סיבוב מתבצע מספר קבוע של פעולות (השוואה ל-0, השוואה לחיובי, הגדלת מונה).
4. במקרה הגרוע (אין אפסים) מתבצעים n סיבובים, ולכן זמן הריצה פרופורציוני ל-n. הזיכרון הנוסף קבוע (שני מונים).
תשובה: סיבוכיות הזמן היא .
שאלה 4 · מחלקת ילד: ספירת בנים ובנות
בתחנה לטיפול באם ובילד שומרים מידע על ילדים אשר מטופלים בתחנה.
לשם כך פותחה מחלקה Child ולה תכונות הבאות:
•שם הילד – name – מסוג מחרוזת, String
•מין הילד – gender – מסוג תו, char
•שנת לידה – year – מסוג מספר שלם, int
•חודש לידה – month – מסוג מספר שלם, int
במחלקה הוגדרו בנאי (constructor) ופעולות get לכל התכונות.
כתבו פעולה המקבלת מערך עצמים מסוג Child ומספר שלם year. הפעולה תדפיס את מספר הבנים ואת מספר הבנות אשר נולדו בשנה year.
כותרת הפעולה:
public static void printByYear(Child[] arr, int year)public static void PrintByYear(Child[] arr, int year)כתבו פעולה המקבלת מערך עצמים מסוג Child. הפעולה תדפיס עבור כל אחד מ- 12 חודשי השנה את מספר הבנים ואת מספר הבנות אשר נולדו באותו חודש.
כותרת הפעולה:
public static void printByMonth(Child[] arr)public static void PrintByMonth(Child[] arr)◂ פתרון מלא לשאלה 4
סעיף א
עוברים על המערך; לילד שנולד בשנה year מגדילים מונה בנים (gender == 'M') או מונה בנות; בסוף מדפיסים את שני המונים.
הנחה: בשאלה לא נקבע איך מסומן המין בתו gender. נניח ש-'M' מסמן בן ו-'F' מסמנת בת (בכל סימון אחר משנים רק את התו בהשוואה).
הרעיון: שני מונים, ומעבר אחד על המערך.
1. לכל ילד בודקים בעזרת `getYear()` אם שנת הלידה שלו היא year. ילדים משנים אחרות אינם נספרים.
2. לילד שנולד בשנה year בודקים את המין בעזרת `getGender()`: 'M' – מגדילים את boys, אחרת – את girls.
3. אחרי הלולאה מדפיסים את שני המונים.
הגישה לתכונות היא דרך פעולות ה-get, כי התכונות של Child פרטיות והפעולה כתובה מחוץ למחלקה.
public static void printByYear(Child[] arr, int year)
{
int boys = 0, girls = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getYear() == year)
{
if (arr[i].getGender() == 'M')
boys++;
else
girls++;
}
}
System.out.println("Year " + year + ": boys " + boys + ", girls " + girls);
}public static void PrintByYear(Child[] arr, int year)
{
int boys = 0, girls = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetYear() == year)
{
if (arr[i].GetGender() == 'M')
boys++;
else
girls++;
}
}
Console.WriteLine("Year " + year + ": boys " + boys + ", girls " + girls);
}תשובה: הפעולה שלמעלה.
סעיף ב
שני מערכי מונים בגודל 12 (בנים ובנות); לכל ילד מגדילים את התא month-1 במערך המתאים; בסוף מדפיסים 12 שורות.
הרעיון: במקום 24 משתנים נפרדים משתמשים בשני מערכי מונים בגודל 12: התא m-1 סופר את הילדים שנולדו בחודש m (חודש 1 בתא 0, ..., חודש 12 בתא 11). כך מספיק מעבר אחד על מערך הילדים.
1. יוצרים `boys = new int[12]` ו-`girls = new int[12]` (מאותחלים באפסים).
2. לכל ילד: לוקחים את חודש הלידה m בעזרת `getMonth()`, ולפי המין מגדילים את `boys[m-1]` או את `girls[m-1]` (אותה הנחה כמו בסעיף א: 'M' = בן).
3. בסוף עוברים על החודשים 1 עד 12 ומדפיסים לכל חודש את שני המונים.
public static void printByMonth(Child[] arr)
{
int[] boys = new int[12]; // boys[m-1] = מספר הבנים שנולדו בחודש m
int[] girls = new int[12]; // girls[m-1] = מספר הבנות שנולדו בחודש m
for (int i = 0; i < arr.length; i++)
{
int m = arr[i].getMonth();
if (arr[i].getGender() == 'M')
boys[m - 1]++;
else
girls[m - 1]++;
}
for (int m = 1; m <= 12; m++)
System.out.println("Month " + m + ": boys " + boys[m - 1] + ", girls " + girls[m - 1]);
}public static void PrintByMonth(Child[] arr)
{
int[] boys = new int[12]; // boys[m-1] = מספר הבנים שנולדו בחודש m
int[] girls = new int[12]; // girls[m-1] = מספר הבנות שנולדו בחודש m
for (int i = 0; i < arr.Length; i++)
{
int m = arr[i].GetMonth();
if (arr[i].GetGender() == 'M')
boys[m - 1]++;
else
girls[m - 1]++;
}
for (int m = 1; m <= 12; m++)
Console.WriteLine("Month " + m + ": boys " + boys[m - 1] + ", girls " + girls[m - 1]);
}סיבוכיות: מעבר אחד על n הילדים ועוד 12 הדפסות – .
תשובה: הפעולה שלמעלה.
שאלה 5 · מחלקת סרט: בנאים, מעקב ומקסימום
לצורך אחסון נתוני כרטיסים שנמכרו לסרט קולנוע הוגדרה מחלקה בשם Movie בעלת שלוש תכונות:
•שם הסרט – name – מסוג מחרוזת, String.
•מחיר כרטיס – price – מסוג מספר ממשי, double.
•מספר כרטיסים שנמכרו – num – מסוג מספר שלם, int.
לפניכם מחלקה TestMovie המשתמשת במחלקה Movie:
public class TestMovie
{
public static double totalSum(Movie m)
{
return m.getPrice()*m.getNum();
}
public static void main(String[] args)
{
Movie a = new Movie();
a.setName("Avatar");
a.setPrice(30.0);
a.setNum(100);
System.out.println(totalSum(a));
a.setNum(50);
Movie b = new Movie (a.getName(), 20.0, a.getNum());
System.out.println(totalSum(b));
}
}public class TestMovie
{
public static double TotalSum(Movie m)
{
return m.GetPrice()*m.GetNum();
}
public static void Main(string[] args)
{
Movie a = new Movie();
a.SetName("Avatar");
a.SetPrice(30.0);
a.SetNum(100);
Console.WriteLine(TotalSum(a));
a.SetNum(50);
Movie b = new Movie (a.GetName(), 20.0, a.GetNum());
Console.WriteLine(TotalSum(b));
}
}עבור המחלקה Movie:
כתבו את כותרת המחלקה ואת התכונות שלה.
כתבו את הכותרות של שתי הפעולות הבונות של המחלקה.
עקבו אחרי הביצוע של הפעולה הראשית main ורשמו מה יהיה הפלט.
כתבו במחלקה TestMovie פעולה המקבלת מערך סרטים ומחזירה שם הסרט שמספר הכרטיסים שנמכרו לו הוא הכי גדול.
כותרת הפעולה:
public static String getMostPopularMovie(Movie[] t)public static string GetMostPopularMovie(Movie[] t)◂ פתרון מלא לשאלה 5
סעיף א
`public class Movie` עם התכונות `private String name; private double price; private int num;` (ב-C#: `string name`).
המחלקה צריכה להיות ציבורית (TestMovie משתמשת בה), והתכונות פרטיות – הגישה אליהן נעשית דרך פעולות get ו-set, כפי שרואים ב-main. הטיפוסים נלקחים מתיאור התכונות.
public class Movie
{
private String name; // שם הסרט
private double price; // מחיר כרטיס
private int num; // מספר כרטיסים שנמכרוpublic class Movie
{
private string name; // שם הסרט
private double price; // מחיר כרטיס
private int num; // מספר כרטיסים שנמכרותשובה: כותרת המחלקה והתכונות שלמעלה.
`public Movie()` ו-`public Movie(String name, double price, int num)` (ב-C#: `string name`).
את הבנאים מזהים לפי השימוש ב-main:
1. `new Movie()` – בנאי בלי פרמטרים (הערכים נקבעים אחר כך בפעולות set).
2. `new Movie(a.getName(), 20.0, a.getNum())` – בנאי עם שלושה פרמטרים: מחרוזת, מספר ממשי ומספר שלם, בסדר name, price, num.
public Movie()
public Movie(String name, double price, int num)public Movie()
public Movie(string name, double price, int num)תשובה: שתי הכותרות שלמעלה.
סעיף ב
ב-Java: 3000.0 ואחריו 1000.0 (ב-C#: 3000 ואחריו 1000).
1. totalSum מחזירה מחיר כפול מספר כרטיסים. עבור a: .
2. אחרי `setNum(50)` נוצר b עם השם של a, מחיר 20.0 ו-50 כרטיסים (הערך הנוכחי של num ב-a). עבור b: .
3. הערך המוחזר הוא double, ולכן ב-Java הוא מודפס עם נקודה עשרונית: 3000.0 ו-1000.0. ב-C# `Console.WriteLine` מדפיסה double שלם בלי ".0": 3000 ו-1000.
3000.0
1000.0(ב-C#: 3000 ו-1000.)
סעיף ג
חיפוש מקסימום: שומרים את מקום הסרט עם הכי הרבה כרטיסים (getNum()) ובסוף מחזירים את getName() שלו.
הרעיון: חיפוש מקסימום רגיל, אבל שומרים את המקום של הסרט הטוב ביותר (ולא רק את מספר הכרטיסים), כי בסוף צריך להחזיר את שמו.
1. מניחים שהסרט הראשון (מקום 0) הוא הנבחר.
2. עוברים על שאר הסרטים; אם לסרט במקום i נמכרו יותר כרטיסים מאשר לנבחר (השוואה בעזרת `getNum()`), הוא הופך לנבחר.
3. בסוף מחזירים את שם הסרט הנבחר בעזרת `getName()`. אם יש כמה סרטים עם אותו מקסימום, מוחזר הראשון מביניהם.
(מניחים שהמערך אינו ריק.)
public static String getMostPopularMovie(Movie[] t)
{
int maxIndex = 0; // מקום הסרט הנבחר עד כה
for (int i = 1; i < t.length; i++)
{
if (t[i].getNum() > t[maxIndex].getNum())
maxIndex = i;
}
return t[maxIndex].getName();
}public static string GetMostPopularMovie(Movie[] t)
{
int maxIndex = 0; // מקום הסרט הנבחר עד כה
for (int i = 1; i < t.Length; i++)
{
if (t[i].GetNum() > t[maxIndex].GetNum())
maxIndex = i;
}
return t[maxIndex].GetName();
}תשובה: הפעולה שלמעלה.
שאלה 6 · פעולות על ספרות של זוג מספרים
נתונות שתי הפעולות הבאות: what, where המקבלות כל אחת זוג מספרים שלמים וחיוביים:
public static boolean what(int num1, int num2){
while(num1 >= 10 || num2 >= 10)
{
if(num1 >= 10 && num2 >= 10)
{
num1 = num1/10;
num2 = num2/10;
}
else
{
if(num1 >= 10)
{
num1 = num1/10;
}
else
{
num2 = num2/10;
}
if(num1 == num2)
{
return true;
}
}
}
return false;
}
public static boolean where(int num1, int num2){
while(num1>0 || num2>0)
{
if(num1*num2==0)
return true;
num1=num1/10;
num2=num2/10;
}
return false;
}public static bool What(int num1, int num2){
while(num1 >= 10 || num2 >= 10)
{
if(num1 >= 10 && num2 >= 10)
{
num1 = num1/10;
num2 = num2/10;
}
else
{
if(num1 >= 10)
{
num1 = num1/10;
}
else
{
num2 = num2/10;
}
if(num1 == num2)
{
return true;
}
}
}
return false;
}
public static bool Where(int num1, int num2){
while(num1>0 || num2>0)
{
if(num1*num2==0)
return true;
num1=num1/10;
num2=num2/10;
}
return false;
}עקבו בעזרת טבלת המעקב אחרי זימון הפעולה what(1804,1957) ורשמו מה תהיה תוצאת הזימון.
מה מבצעת הפעולה what באופן כללי עבור זוג מספרים שלמים וחיוביים?
מה מבצעת הפעולה where באופן כללי עבור זוג מספרים שלמים וחיוביים?
תנו דוגמה לזוג מספרים בני שלוש ספרות ומעלה שעבורם הפעולה תחזיר false.
◂ פתרון מלא לשאלה 6
סעיף א
הפעולה מחזירה false.
בכל סיבוב: אם שני המספרים לפחות דו-ספרתיים מקצצים ספרה מכל אחד (בלי השוואה); אחרת מקצצים ספרה רק מהמספר הארוך ואז משווים.
אחרי הסיבוב השלישי num1 = 1 ו-num2 = 1, ושניהם קטנים מ-10, ולכן תנאי הלולאה נכשל. אף על פי שהמספרים שווים, ההשוואה `num1 == num2` נמצאת רק בענף ה-else, ולא בוצעה. הפעולה מגיעה ל-`return false`.
תשובה: הזימון what(1804,1957) מחזיר false.
סעיף ב
מחזירה true אם ורק אם למספרים מספר ספרות שונה והספרה השמאלית (הראשונה) שלהם שווה; אחרת false.
1. כל עוד שני המספרים לפחות דו-ספרתיים, מוחקים מכל אחד את ספרת האחדות. אם לשניהם אותו מספר ספרות, הם הופכים לחד-ספרתיים באותו סיבוב, הלולאה נגמרת בלי שבוצעה השוואה, ומוחזר false (כמו בסעיף א).
2. אם למספרים מספר ספרות שונה, המספר הקצר הופך ראשון לחד-ספרתי – לספרה השמאלית שלו. מעכשיו בכל סיבוב מקצצים רק את המספר הארוך ומשווים.
3. מספר חד-ספרתי יכול להיות שווה רק למספר חד-ספרתי, ולכן ההשוואה יכולה להצליח רק בסיבוב שבו גם הארוך הופך לספרה השמאלית שלו. אז מוחזר true אם הספרות השמאליות שוות, ואחרת הלולאה נגמרת ומוחזר false.
דוגמאות: what(1234, 19) מחזירה true (שתיהן מתחילות ב-1, אורכים 4 ו-2); what(5, 57) מחזירה true; what(123, 456) ו-what(1804, 1957) מחזירות false.
תשובה: what מחזירה true אם למספרים מספר ספרות שונה והספרה הראשונה (השמאלית) שלהם זהה, אחרת false.
סעיף ג
מחזירה true אם למספרים מספר ספרות שונה, ו-false אם מספר הספרות שווה. דוגמה ל-false: where(123, 456).
1. בכל סיבוב מוחקים ספרה אחת מכל מספר, ולכן מספר בן d ספרות הופך ל-0 אחרי d סיבובים בדיוק.
2. המכפלה `num1*num2` שווה 0 רק כאשר אחד המספרים כבר 0 (שני המספרים אינם שליליים).
3. אם למספרים מספר ספרות שונה, הקצר מגיע ל-0 קודם, בזמן שהארוך עדיין חיובי: תנאי הלולאה עדיין מתקיים, המכפלה 0, ומוחזר true.
4. אם מספר הספרות שווה, שניהם מגיעים ל-0 באותו סיבוב. בכל הסיבובים שלפני כן שניהם חיוביים (המכפלה אינה 0), ואחרי שהם מתאפסים תנאי הלולאה נכשל ומוחזר false.
דוגמה ל-false: where(123, 456) – שני המספרים בני שלוש ספרות:
אחרי הסיבוב השלישי num1 = num2 = 0, הלולאה נגמרת, ומוחזר false.
תשובה: where בודקת אם למספרים מספר ספרות שונה (true) או שווה (false). דוגמה ל-false: 123 ו-456 (כל זוג בעל אותו מספר ספרות).
שאלה 7 · מחלקת הצבעות לתוכנית ריאליטי
בתוכנית הטלוויזיה "האח הקטן" יש n משתתפים. לכל משתתף מספר סידורי בין 1 ל- n.
בסוף כל שבוע נערכת הצבעה של צופי התוכנית. משתתף שמקבל הכי מעט קולות עוזב את בית ה"אח הקטן".
שלושת המשתתפים האחרונים שנשארים מגיעים לשלב הגמר.
כדי לנהל את התוכנית הוגדרה המחלקה SmallBrother ולה שתי תכונות:
•votes – מערך מספרים שלמים. תוכן תאי המערך מציין את מצב המשתתף: 0 עבור משתתף שנמצא בבית ו- (-1) עבור משתתף שמחוץ לבית.
•numOfPart – מספר המשתתפים הממשיכים להשתתף בתוכנית.
להלן המחלקה:
public class SmallBrother
{
private int[] votes;
private int numOfPart;
public SmallBrother(int n)
{
this.votes = new int[n];
this.numOfPart = n;
}
public int getNumOfPart(){ return this.numOfPart;}
public void Init()
{
for(int i=0; i < votes.length; i++)
{
if(votes[i]!=-1) votes[i] = 0;
}
}
}public class SmallBrother
{
private int[] votes;
private int num;
public SmallBrother(int n)
{
this.votes = new int[n];
this.numOfPart = n;
}
public int GetNumOfPart(){ return this.numOfPart;}
public void Init()
{
for(int i=0; i<votes.Length; i++)
{
if(votes[i]!=-1) votes[i] = 0;
}
}
}כתבו פעולה הקולטת את הצבעות הצופים (מספר משתתף בין 1 ל- n). קלט מסתיים כאשר מספר משתתף שנקלט ערכו 0. הפעולה מעדכנת את כמות ההצבעות של המשתתפים שנמצאים עדיין בבית.
אם צופה הצביע עבור משתתף שכבר עזב את הבית, אין להתייחס להצבעה זו.
כותרת הפעולה:
public void voting()public void Voting()כתבו פעולה הבודקת מהו מספרו של המשתתף שנמצא בבית וקיבל הכי פחות קולות וצריך לעזוב את הבית. הפעולה תעדכן את מצבו ואת מספר המשתתפים שממשיכים להשתתף בתוכנית.
כותרת הפעולה:
public void update()public void Update()כתבו פעולה הבודקת אם תכנית הטלוויזיה הסתיימה, כלומר, נשארו רק שלושה משתתפים בבית.
אם כן – הפעולה תדפיס מספרים סידוריים של המשתתפים שמגיעים לגמר ומחזירה true,
ואם לא – הפעולה תחזיר false.
כותרת הפעולה:
public boolean isFinish()public bool IsFinish()◂ פתרון מלא לשאלה 7
סעיף א
קולטים מספרים עד 0; לכל מספר num, אם votes[num-1] != -1 מגדילים את votes[num-1] ב-1.
הרעיון: המערך votes משמש גם כמערך מונים: למשתתף שבבית התא מתחיל ב-0 (אחרי Init) וכל הצבעה מגדילה אותו ב-1. למשתתף שעזב התא הוא -1, ואותו לא משנים.
1. משתתף מספר num נמצא בתא `num - 1` (המספור מתחיל ב-1 והמערך ב-0).
2. קולטים מספר לפני הלולאה, וכל עוד הוא שונה מ-0 מטפלים בו וקולטים את הבא (0 הוא זקיף).
3. אם `votes[num - 1] != -1` – המשתתף עדיין בבית, ומגדילים את מונה הקולות שלו. אחרת מתעלמים מההצבעה.
ב-Java נגדיר במחלקה עצם קלט אחד: `private static Scanner in = new Scanner(System.in);` (וב-`import java.util.Scanner;` בראש הקובץ), כדי שכל זימון של הפעולה ישתמש באותו עצם.
public void voting()
{
int num = in.nextInt(); // מספר המשתתף (1 עד n)
while (num != 0)
{
if (this.votes[num - 1] != -1) // המשתתף עדיין בבית
this.votes[num - 1]++;
num = in.nextInt();
}
}public void Voting()
{
int num = int.Parse(Console.ReadLine()); // מספר המשתתף (1 עד n)
while (num != 0)
{
if (this.votes[num - 1] != -1) // המשתתף עדיין בבית
this.votes[num - 1]++;
num = int.Parse(Console.ReadLine());
}
}תשובה: הפעולה שלמעלה.
סעיף ב
מחפשים מינימום רק בין התאים ששונים מ-1-; את התא שנמצא קובעים ל-1- ומקטינים את numOfPart ב-1.
הרעיון: חיפוש מינימום, אבל רק בין המשתתפים שבבית (תאים ששונים מ-1-). אי אפשר להתחיל מ-`votes[0]`, כי ייתכן שמשתתף 1 כבר עזב; לכן מתחילים עם `minIndex = -1` שמשמעותו "עוד לא נמצא אף משתתף".
1. עוברים על כל התאים. תא שערכו -1 מדלגים עליו.
2. אם עוד לא נבחר אף משתתף (`minIndex == -1`), או שלמשתתף הנוכחי פחות קולות מאשר לנבחר – הוא הופך לנבחר.
3. אחרי הלולאה, המשתתף במקום minIndex (מספרו minIndex + 1) עוזב: קובעים `votes[minIndex] = -1` ומקטינים את numOfPart ב-1.
public void update()
{
int minIndex = -1;
for (int i = 0; i < this.votes.length; i++)
{
if (this.votes[i] != -1) // רק משתתפים שבבית
{
if (minIndex == -1 || this.votes[i] < this.votes[minIndex])
minIndex = i;
}
}
this.votes[minIndex] = -1; // המשתתף עוזב את הבית
this.numOfPart--;
}public void Update()
{
int minIndex = -1;
for (int i = 0; i < this.votes.Length; i++)
{
if (this.votes[i] != -1) // רק משתתפים שבבית
{
if (minIndex == -1 || this.votes[i] < this.votes[minIndex])
minIndex = i;
}
}
this.votes[minIndex] = -1; // המשתתף עוזב את הבית
this.numOfPart--;
}דוגמה: n = 5 והקולות: משתתף 1 – 1, ומשתתפים 2 עד 5 – 2 כל אחד. update מוציאה את משתתף 1 (תא 0 הופך ל-1-) ו-numOfPart יורד מ-5 ל-4.
תשובה: הפעולה שלמעלה.
סעיף ג
אם numOfPart != 3 מחזירים false; אחרת מדפיסים i+1 לכל תא שערכו שונה מ-1- ומחזירים true.
1. מספר המשתתפים שבבית שמור בתכונה numOfPart (update מעדכנת אותה), ולכן התוכנית הסתיימה בדיוק כאשר `numOfPart == 3`.
2. אם לא – מחזירים false מיד.
3. אם כן – עוברים על המערך ומדפיסים את המספר הסידורי (`i + 1`) של כל משתתף שהתא שלו שונה מ-1- (כלומר הוא עדיין בבית), ומחזירים true.
public boolean isFinish()
{
if (this.numOfPart != 3)
return false;
for (int i = 0; i < this.votes.length; i++)
{
if (this.votes[i] != -1)
System.out.println(i + 1); // המספר הסידורי = המקום + 1
}
return true;
}public bool IsFinish()
{
if (this.numOfPart != 3)
return false;
for (int i = 0; i < this.votes.Length; i++)
{
if (this.votes[i] != -1)
Console.WriteLine(i + 1); // המספר הסידורי = המקום + 1
}
return true;
}הערה ל-C#: במחלקה המודפסת התכונה השנייה נקראת num, אבל הבנאי והפעולה GetNumOfPart משתמשים ב-numOfPart; ברור שהכוונה היא לתכונה numOfPart, ובה השתמשנו.
תשובה: הפעולה שלמעלה.
שאלה 8 · מחלקת רכבת: מעקב ומימוש פעולה
לפניכם המחלקה Train הכוללת מערך קרונות השומר את מספר הנוסעים בקרון ברגע נתון וכן את מספר הנוסעים המקסימלי בקרון. המחלקה כוללת פעולה הבונה רכבת ריקה מנוסעים ושתי פעולות נוספות:
•הפעולה addToCarr המוסיפה numPass לקרון carrId.
•הפעולה carrNumber המקבלת מספר נוסעים ומחזירה את מספר קרון היכול לאכלס את מספר הנוסעים הזה. אם אין מספיק מקום באף קרון הפעולה תחזיר -1.
public class Train {
private int[] carr; // מערך הקרונות
private int maxInCarr; // מספר נוסעים מקסימלי בקרון
public Train (int n, int max){ // פעולה בונה
this.maxInCarr = max;
this.carr = new int[n];
}
public void addToCarr(int carrNum, int numPass){
this.carr[carrNum -1] = this.carr[carrNum -1] + numPass;
}
public int carrNumber(int numPass) {. . . . .}public class Train {
private int[] carr; // מערך הקרונות
private int maxInCarr; // מספר נוסעים מקסימלי בקרון
public Train (int n, int max){ // פעולה בונה
this.maxInCarr = max;
this.carr = new int[n];
}
public void AddToCarr(int carrNum, int numPass){
this.carr[carrNum -1] = this.carr[carrNum -1] + numPass;
}
public int CarrNumber(int numPass) {. . . . .}נתונה מחלקה Run הבאה:
public class Run {
public static void main(String[] args){
Scanner in = new Scanner((System.in));
Train t = new Train(5,20);
int carrNum;
int pass = in.nextInt();
while(pass > 0)
{
carrNum = t.carrNumber(pass);
if(carrNum == -1)
System.out.println("No seats left");
else
{
t.addToCarr(carrNum, pass);
System.out.println ("Your seats in "+ carrNum);
}
pass = in.nextInt();
}//while
}
}public class Run {
public static void Main(string[] args){
Train t = new Train(5,20);
int carrNum;
int pass = int.Parse(Console.ReadLine());
while(pass > 0)
{
carrNum = t.CarrNumber(pass);
if(carrNum == -1)
Console.WriteLine ("No seats left");
else
{
t.AddToCarr(carrNum, pass);
Console.WriteLine("Your seats in "+ carrNum);
}
pass = int.Parse(Console.ReadLine());
}//while
}
}עקבו בעזרת טבלת מעקב אחר הפעולה main עבור הקלט הבא (משמאל לימין):
10, 2, 12, 4, 15, 3, 15, 4, 8, 2, 10, 3, -99
עליכם לכלול בטבלה עמודה לכל משתנה (כולל עמודה לעצם t) עמודה לתנאי הלולאה (pass>0) ועמודה לפלט.
ממשו את הפעולה carrNumber.
◂ פתרון מלא לשאלה 8
סעיף א
הפלט: Your seats in 1, 1, 2, 1, 3, 1, 4, 2, 5, 2, 5, 3 (12 שורות; אף פעם לא No seats left). בסוף t.carr = {19, 18, 18, 15, 18}.
הנחה לגבי carrNumber (את מימושה כותבים בסעיף ב): הפעולה מחזירה את מספר הקרון הראשון (הקטן ביותר) שבו יש מקום לכל numPass הנוסעים, כלומר הקרון הראשון שבו מספר הנוסעים הנוכחי ועוד numPass אינו עולה על 20.
הרכבת t נבנית עם 5 קרונות ריקים ו-maxInCarr = 20. בעמודה t מופיע תוכן המערך carr (הקרונות 1 עד 5) אחרי הסיבוב.
הסבר לכמה שורות:
1. pass = 12 (שורה 3): בקרון 1 יש 12 נוסעים, ו-, ולכן נבחר קרון 2 ().
2. pass = 15 (שורה 5): בקרון 1 – , בקרון 2 – ; שניהם מעל 20, ונבחר קרון 3.
3. pass = 8 (שורה 9): קרונות 1 עד 4 מכילים 19, 16, 15, 15 נוסעים, ובכל אחד הסכום עם 8 עולה על 20; נבחר קרון 5.
4. pass = 3 (שורה 12): , , ובקרון 3: – נבחר קרון 3.
כאשר נקלט -99 תנאי הלולאה נכשל והתוכנית מסתיימת.
תשובה: הפלט הוא:
Your seats in 1
Your seats in 1
Your seats in 2
Your seats in 1
Your seats in 3
Your seats in 1
Your seats in 4
Your seats in 2
Your seats in 5
Your seats in 2
Your seats in 5
Your seats in 3סעיף ב
עוברים על הקרונות לפי הסדר; מחזירים i+1 עבור הקרון הראשון שבו carr[i] + numPass <= maxInCarr; אם אין כזה מחזירים -1.
הרעיון: חיפוש לינארי של הקרון הראשון שיש בו מקום.
1. עוברים על הקרונות מהראשון לאחרון.
2. בקרון שבמקום i יש `carr[i]` נוסעים. יש בו מקום לכל הקבוצה אם `carr[i] + numPass <= maxInCarr`.
3. ברגע שנמצא קרון כזה מחזירים את מספר הקרון, שהוא `i + 1` (מספור הקרונות מתחיל ב-1, כמו ב-addToCarr שניגשת ל-`carr[carrNum - 1]`).
4. אם הלולאה הסתיימה ולא נמצא קרון מתאים, מחזירים -1.
public int carrNumber(int numPass)
{
for (int i = 0; i < this.carr.length; i++)
{
if (this.carr[i] + numPass <= this.maxInCarr)
return i + 1; // מספרי הקרונות מתחילים ב-1
}
return -1; // אין קרון עם מספיק מקום
}public int CarrNumber(int numPass)
{
for (int i = 0; i < this.carr.Length; i++)
{
if (this.carr[i] + numPass <= this.maxInCarr)
return i + 1; // מספרי הקרונות מתחילים ב-1
}
return -1; // אין קרון עם מספיק מקום
}תשובה: הפעולה שלמעלה (הסיבוכיות , n מספר הקרונות).
שאלה 9 · בדיקת מחרוזת מיוחדת וסיבוכיות
מחרוזת מיוחדת (special) היא מחרוזת אשר מורכבת מאותיות קטנות של הא"ב האנגלי בלבד (a..z), וכל האותיות במחרוזת שונות זו מזו.
המחרוזות "c", "adb" הן מיוחדות.
המחרוזות "AB", "abca", "ab*cd" אינן מיוחדות.
מחרוזת ריקה אינה מיוחדת.
כתבו פעולה אשר מקבלת כפרמטר מחרוזת ובודקת אם היא "מחרוזת מיוחדת".
אם כן – הפעולה תחזיר ערך true ואם לא, הפעולה תחזיר false.
מהי סיבוכיות של הפעולה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
מחרוזת ריקה – false; אחרת עוברים על התווים: תו שאינו בין 'a' ל-'z' או אות שכבר סומנה במערך seen בגודל 26 – false; בסוף true.
הרעיון: צריך לבדוק שלושה דברים: שהמחרוזת אינה ריקה, שכל תו הוא אות קטנה, ושאין אות שחוזרת. לבדיקת החזרות משתמשים במערך בוליאני `seen` בגודל 26 – תא לכל אות: האות ch מתאימה לתא `ch - 'a'` (למשל 'a' לתא 0 ו-'z' לתא 25).
1. אם אורך המחרוזת 0 – מחזירים false.
2. עוברים על התווים לפי הסדר. אם התו קטן מ-'a' או גדול מ-'z' – זו אינה אות קטנה, ומחזירים false (כך נפסלות "AB" ו-"ab\*cd").
3. אם `seen[ch - 'a']` כבר true – האות הופיעה קודם, ומחזירים false (כך נפסלת "abca" כשמגיעים ל-'a' השנייה).
4. אחרת מסמנים `seen[ch - 'a'] = true` וממשיכים.
5. אם עברנו על כל התווים בלי לפסול – המחרוזת מיוחדת, ומחזירים true.
public static boolean isSpecial(String s)
{
if (s.length() == 0)
return false; // מחרוזת ריקה אינה מיוחדת
boolean[] seen = new boolean[26]; // seen[k] - האם האות 'a'+k כבר הופיעה
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (ch < 'a' || ch > 'z')
return false; // תו שאינו אות קטנה
if (seen[ch - 'a'])
return false; // אות שחוזרת פעמיים
seen[ch - 'a'] = true;
}
return true;
}public static bool IsSpecial(string s)
{
if (s.Length == 0)
return false; // מחרוזת ריקה אינה מיוחדת
bool[] seen = new bool[26]; // seen[k] - האם האות 'a'+k כבר הופיעה
for (int i = 0; i < s.Length; i++)
{
char ch = s[i];
if (ch < 'a' || ch > 'z')
return false; // תו שאינו אות קטנה
if (seen[ch - 'a'])
return false; // אות שחוזרת פעמיים
seen[ch - 'a'] = true;
}
return true;
}בדיקה עם הדוגמאות: "c" ו-"adb" – true; "AB", "abca", "ab\*cd" והמחרוזת הריקה – false.
תשובה: הפעולה שלמעלה.
סעיף ב
, כאשר n הוא אורך המחרוזת (מעבר אחד, עבודה קבועה לכל תו).
1. נסמן ב-n את אורך המחרוזת.
2. יצירת המערך seen בגודל 26 היא פעולה בזמן קבוע (26 אינו תלוי ב-n).
3. הלולאה עוברת על כל תו פעם אחת לכל היותר, ולכל תו מתבצעות מספר קבוע של פעולות: השוואה לטווח 'a'..'z', בדיקה של תא במערך, וסימון תא. הגישה לתא במערך היא בזמן קבוע.
4. לכן זמן הריצה במקרה הגרוע פרופורציוני ל-n.
הערה: מחרוזת מיוחדת מכילה לכל היותר 26 אותיות שונות, ולכן הלולאה נעצרת לכל המאוחר בתו ה-27; כלומר בפועל מספר הסיבובים חסום גם על ידי קבוע. בניסוח הרגיל, כתלות באורך הקלט, הסיבוכיות היא .
תשובה: .
שאלה 10 · פעולה על מערך דו-ממדי: מילוי וטווחים
נתונה פעולה what הבאה:
public static boolean what (int[][]mat)
{
for (int i=0; i<mat.length-1; i++)
for (int j=0; j<mat[0].length-1; j++)
{
if(mat[i][j]<0)
return false;
if (mat[i][j] >= mat[i+1][j])
return false;
if (mat[i][j] >= mat[i][j+1])
return false;
}
return true;
}public static bool What (int[,]mat)
{
for (int i=0; i<mat.GetLength(0)-1; i++)
for (int j=0; j<mat.GetLength(1)-1; j++)
{
if(mat[i,j]<0)
return false;
if (mat[i,j] >= mat[i+1,j])
return false;
if (mat[i,j] >= mat[i,j+1])
return false;
}
return true;
}נתון מערך mat של מספרים שלמים הבא:
מלאו את המערך mat כך שאם נעביר אותו כפרמטר לפעולה what, הפעולה תחזיר את הערך true.
מהו טווח הערכים שיכול לקבל הערך mat[0][0] כך שזימון הפעולה what(mat) יחזיר ערך true?
הסבירו את תשובתכם.
מהו טווח הערכים שיכול לקבל הערך mat[2][4] כך שזימון הפעולה what(mat) יחזיר ערך true?
הסבירו את תשובתכם.
מה מבצעת הפעולה what באופן כללי?
◂ פתרון מלא לשאלה 10
סעיף א
למשל: שורה 0: 0, 1, 2, 3, 4; שורה 1: 1, 2, 10, 11, 12; שורה 2: 2, 3, 11, 12, 13.
מה הפעולה דורשת: הלולאות עוברות על כל התאים שאינם בשורה האחרונה ואינם בעמודה האחרונה (i = 0, 1 ו-j = 0 עד 3). כל תא כזה חייב להיות אי-שלילי, קטן ממש מהתא שמתחתיו וקטן ממש מהתא שמימינו. אחרת מוחזר false.
כדי לקיים זאת, נמלא כך שכל שורה עולה משמאל לימין וכל עמודה עולה מלמעלה למטה, ונשאיר את 10 במקום [1][2]:
1. כל התאים הנבדקים (שורות 0-1, עמודות 0-3) אי-שליליים.
2. שורה 0 ו-שורה 1 עולות ממש: ו-.
3. עמודות 0 עד 3 עולות ממש מלמעלה למטה: , , , .
4. בפרט התא [1][2] = 10 קטן מ-[2][2] = 11 ומ-[1][3] = 11, והתאים [0][2] = 2 ו-[1][1] = 2 קטנים מ-10.
לכן אף תנאי `return false` אינו מתקיים, והפעולה מחזירה true.
תשובה: המילוי בטבלה שלמעלה (כל מילוי שבו השורות 0-1 והעמודות 0-3 עולות ממש, והערכים אי-שליליים).
סעיף ב
.
1. חסם תחתון: התא [0][0] נבדק ב-`if(mat[i][j]<0)`, ולכן .
2. חסם עליון: בשורה 0 הערכים עולים ממש: , ובעמודה 2: . במספרים שלמים, "קטן ממש" פירושו קטן לפחות ב-1:
, , .
(אותו חסם מתקבל גם בדרך השנייה: .)
3. הערך 7 אכן אפשרי, למשל עם שורה 0: 7, 8, 9, 20, 21; שורה 1: 8, 9, 10, 21, 22; שורה 2: 9, 10, 11, 22, 23. כל ערך בין 0 ל-7 אפשרי באותו אופן (עם מילוי כמו בסעיף א).
תשובה: (המספרים השלמים 0 עד 7).
סעיף ג
כל ערך שלם – התא mat[2][4] אינו נבדק כלל.
1. הלולאות רצות על i < mat.length-1, כלומר i = 0, 1, ועל j < mat[0].length-1, כלומר j = 0 עד 3.
2. בכל סיבוב ניגשים לשלושה תאים בלבד: [i][j], [i+1][j] (מתחת) ו-[i][j+1] (מימין).
3. כדי לגשת ל-[2][4] היה צריך [i+1][j] עם i = 1, j = 4 (אבל j מגיע רק עד 3), או [i][j+1] עם i = 2 (אבל i מגיע רק עד 1). לכן התא הימני-התחתון לעולם אינו נקרא, וערכו אינו משפיע על התוצאה.
תשובה: mat[2][4] יכול לקבל כל ערך שלם (גם שלילי).
סעיף ד
בודקת שכל תא שאינו בשורה האחרונה או בעמודה האחרונה אי-שלילי וקטן ממש מהתא שמימינו ומהתא שמתחתיו – כלומר שהמערך ממוין בסדר עולה ממש בשורות ובעמודות (חוץ מהשורה האחרונה והעמודה האחרונה, שלא נבדקות בתוכן עצמן, והפינה הימנית-התחתונה שאינה נבדקת כלל).
1. הפעולה עוברת על כל התאים שאינם בשורה האחרונה ואינם בעמודה האחרונה.
2. לכל תא כזה היא מחזירה false אם הוא שלילי, או אם הוא גדול או שווה לשכן שמתחתיו או לשכן שמימינו.
3. אם אף תא לא נפסל, מוחזר true.
כלומר, הפעולה מחזירה true אם המערך "ממוין בסדר עולה ממש" גם לאורך השורות וגם לאורך העמודות, עם ערכים אי-שליליים. בדיוק:
•כל שורה פרט לאחרונה עולה ממש משמאל לימין (כולל המעבר לעמודה האחרונה);
•כל עמודה פרט לאחרונה עולה ממש מלמעלה למטה (כולל המעבר לשורה האחרונה);
•הסדר בתוך השורה האחרונה ובתוך העמודה האחרונה אינו נבדק, והתא בפינה הימנית-התחתונה אינו נבדק כלל (סעיף ג).
תשובה: what בודקת שהמערך עולה ממש בשורות ובעמודות ושערכיו אי-שליליים (למעט השורה האחרונה, העמודה האחרונה והפינה, כמפורט).
שאלה 11 · שכפול מערך ובדיקת שכפול
הערה: אין להשתמש במחלקות הקיימות כמו String, Arrays וכד'.
כתבו פעולה המקבלת מערך מספרים שלמים ומספר שלם וחיובי k. הפעולה תחזיר מערך "משוכפל" k פעמים בצורה הבאה:
עבור המספר k=3 המערך
הפעולה תחזיר מערך
כותרת הפעולה:
public static int[] buildK(int[] a, int k)public static int[] BuildK(int[] a, int k)כתבו פעולה המקבלת שני מערכים של מספרים שלמים arr ו- brr. הפעולה תבדוק אם המערך brr הוא "שכפול" k פעמים של המערך arr. אם כן – הפעולה תחזיר את המספר k, ולא – הפעולה תחזיר 0.
עבור המערך arr=
והמערך brr=
הפעולה תחזיר k=2.
כותרת הפעולה:
public static int isCopyK(int[] arr, int[] brr)public static int IsCopyK(int[] arr, int[] brr)מהי סיבוכיות הפעולה isCopyK? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
יוצרים מערך res בגודל a.length·k, ולכל i ולכל j בין 0 ל-k-1 מציבים res[i·k + j] = a[i].
הרעיון: כל איבר של a תופס במערך החדש "בלוק" של k תאים רצופים. האיבר a[i] נמצא בבלוק מספר i, שמתחיל במקום ומסתיים במקום .
1. גודל המערך החדש הוא (בדוגמה ).
2. לולאה חיצונית על i (איברי a), ולולאה פנימית על j מ-0 עד k-1 (העותקים). העותק ה-j של a[i] נכתב במקום .
3. לדוגמה, a[2] = 3 עם k = 3 נכתב במקומות 6, 7, 8 – בדיוק כמו בדוגמה.
public static int[] buildK(int[] a, int k)
{
int[] res = new int[a.length * k];
for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < k; j++)
{
res[i * k + j] = a[i]; // העותק ה-j של a[i]
}
}
return res;
}public static int[] BuildK(int[] a, int k)
{
int[] res = new int[a.Length * k];
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < k; j++)
{
res[i * k + j] = a[i]; // העותק ה-j של a[i]
}
}
return res;
}סיבוכיות: כל אחד מ- התאים של המערך החדש נכתב פעם אחת – .
תשובה: הפעולה שלמעלה.
סעיף ב
אם אורך brr אינו כפולה של אורך arr מחזירים 0; אחרת k = brr.length / arr.length, ובודקים לכל i ש-brr[i] == arr[i / k]; אם הכול מתאים מחזירים k, אחרת 0.
הרעיון: אם brr הוא שכפול k פעמים של arr, אז בהכרח . לכן אין צורך לנחש את k: הוא נקבע לפי האורכים, ונשאר רק לבדוק את התוכן.
1. בדיקת אורכים: אם אחד המערכים ריק, או ש-brr.length אינו מתחלק ב-arr.length, אין k מתאים – מחזירים 0. (הבדיקה של arr ריק גם מונעת חילוק ב-0.)
2. חישוב k: `k = brr.length / arr.length`.
3. בדיקת התוכן: לפי סעיף א, במקום i של המערך המשוכפל נמצא העותק של האיבר `arr[i / k]` (חילוק בשלמים: המקומות 0 עד k-1 שייכים ל-arr[0], המקומות k עד 2k-1 ל-arr[1], וכן הלאה). עוברים על כל brr, ואם נמצא מקום שבו `brr[i] != arr[i / k]` מחזירים 0.
4. אם כל המקומות התאימו – מחזירים k.
public static int isCopyK(int[] arr, int[] brr)
{
if (arr.length == 0 || brr.length == 0 || brr.length % arr.length != 0)
return 0;
int k = brr.length / arr.length; // המספר היחיד שיכול להתאים
for (int i = 0; i < brr.length; i++)
{
if (brr[i] != arr[i / k]) // brr[i] צריך להיות עותק של arr[i/k]
return 0;
}
return k;
}public static int IsCopyK(int[] arr, int[] brr)
{
if (arr.Length == 0 || brr.Length == 0 || brr.Length % arr.Length != 0)
return 0;
int k = brr.Length / arr.Length; // המספר היחיד שיכול להתאים
for (int i = 0; i < brr.Length; i++)
{
if (brr[i] != arr[i / k]) // brr[i] צריך להיות עותק של arr[i/k]
return 0;
}
return k;
}בדיקה עם הדוגמה: arr.length = 3, brr.length = 6, ולכן k = 2. המקומות 0,1 משווים ל-arr[0] = 1, המקומות 2,3 ל-arr[1] = 2, המקומות 4,5 ל-arr[2] = 3 – הכול מתאים, ומוחזר 2.
דוגמאות נוספות: עבור brr = {1, 1, 2, 3, 3, 3} מוחזר 0 (במקום 3 נמצא 3 במקום 2); עבור brr = {1, 1, 2, 2, 3} מוחזר 0 (5 אינו מתחלק ב-3); עבור brr זהה ל-arr מוחזר 1.
תשובה: הפעולה שלמעלה.
סעיף ג
, כאשר m הוא אורך brr (כלומר ).
1. נסמן ב-n את אורך arr וב-m את אורך brr.
2. בדיקת האורכים וחישוב k הם מספר קבוע של פעולות – .
3. הלולאה עוברת על brr פעם אחת לכל היותר, ובכל סיבוב מתבצעים חישוב `i / k`, גישה לשני תאים והשוואה – זמן קבוע.
4. לכן במקרה הגרוע (כאשר brr באמת שכפול) מתבצעים m סיבובים. מאחר ש-, אפשר לכתוב זאת גם .
תשובה: סיבוכיות לינארית באורך brr: .
שאלה 12 · מחלקות תאריך, עוגה ומקרר
החברה "Cake4Me" מספקת עוגות למסעדות ולאולמי האירועים.
לצורך מחשוב ובקרת איכות הוגדרו שלוש מחלקות: Date, Cake, Refrigerator.
המחלקה Date מייצגת תאריך לפי יום, חודש ושנה.
המחלקה מכילה:
(ב-C#: `public bool Equals(Date other)`, `public bool Before(Date other)`.)
המחלקה Date כבר נתונה ואפשר להשתמש בפעולות שבה. אין צורך לממש אותן!
המחלקה Cake מייצגת עוגה.
תכונות המחלקה הן:
•שם העוגה – name – מטיפוס מחרוזת, String.
•תאריך תפוגה – lastDate – מטיפוס תאריך, Date.
•מחיר – price – מטיפוס מספר שלם, int.
•האם חלבי? – hasMilk – מטיפוס boolean, true – חלבי, false – פרווה.
במחלקה Cake הוגדרו פעולות get ו- set ופעולה toString. אין צורך לממש אותן!
כתבו למחלקה Cake את פעולות הבאות:
פעולה בונה (בנאי, constructor) שמקבל כפרמטרים:
שם העוגה, שלושה מספרים שלמים המייצגים יום, חודש ושנה של תאריך התפוגה, מחיר וערך בוליאני (true/false) המציין אם העוגה חלבית או לא.
אפשר להניח שכל הפרמטרים תקינים ואין צורך לבדוק זאת.
פעולה isFresh המקבלת כפרמטר תאריך d ומחזירה true אם בתאריך d העוגה עדיין טרייה (כלומר, התאריך d אינו מאוחר מתאריך התפוגה).
כותרת הפעולה:
public boolean isFresh (Date d)public bool IsFresh (Date d)פעולה isReplaceable המקבלת כפרמטר עוגה other ובודקת אם ניתן להחליף אותה עם העוגה הנוכחית. אפשר להחליף שתי עוגות אם יש להן תאריך תפוגה זהה, סוג זהה (חלבי או פרווה) והפרש מחירים שאינו עולה על 10 שקלים. אם כן – הפעולה תחזיר true, ואם לא – הפעולה תחזיר false.
כותרת הפעולה:
public boolean isReplaceable (Cake other)public bool IsReplaceable (Date d)המחלקה Refrigerator מייצגת מקרר ובו נמצאות עוגות.
הייצוג נעשה באמצעות מערך ששומר את העוגות. התכונות במחלקה הן:
•מערך של העוגות – arr – מערך עצמים מטיפוס Cake.
•מספר העוגות שיש במקרר – numOfCakes – מסוג מספר שלם, int.
כמו כן קיים קבוע מספרי בשם MAX המציין את הגודל המקסימלי של המערך – 30.
העוגות (כלומר האובייקטים מהמחלקה Cake) נמצאים במערך ברצף, ללא "חורים" מתחילת המערך.
כתבו במחלקה את הפעולות הבאות:
פעולה בשם mostFresh המחזירה את העוגה שהיא הכי טרייה במקרר. אם יש כמה כאלו, תוחזר אחת מהן. אם המקרר ריק יוחזר null. נגדיר שעוגה א' טרייה יותר מעוגה ב' אם תאריך התפוגה של עוגה א' מאוחר יותר מתאריך התפוגה של עוגה ב'.
כותרת הפעולה:
public Cake mostFresh()public Cake MostFresh()פעולה בשם removeNotFresh המקבלת כפרמטר תאריך d ומוחקת מהמקרר את כל העוגות שתאריך התפוגה שלהם הוא לפני התאריך d (כלומר, את כל המוצרים שהם מקולקלים בתאריך d, כי תאריך התפוגה שלהם כבר עבר). אם אין כאלו, או אם המערך ריק, הפעולה לא תעשה כלום. שימו לב שצריך למחוק ממש את המוצר מהמערך, ושלא יישארו חורים במערך. אין צורך לשמור על הסדר הפנימי בין העוגות.
כותרת הפעולה:
public void removeNotFresh(Date d)public void RemoveNotFresh(Date d)פעולה בשם purchaseOrder המקבלת כפרמטר מערך names של שמות העוגות שלקוח רוצה לקנות. הפעולה תבדוק אם אפשר לבצע את ההזמנה. אם כן – הפעולה תדפיס את פרט העוגות שבהזמנה ותחזיר את הסכום הכולל של ההזמנה, אם לא – הפעולה תדפיס את השמות של העוגות החסרות ותחזיר 0.
כותרת הפעולה:
public int purchaseOrder(String[] names)public int PurchaseOrder(string[] names)אפשר להניח שלקוח רוצה לקנות עוגות שונות (כל שם מופיע במערך names פעם אחת).
◂ פתרון מלא לשאלה 12
סעיף א
בנאי עם שישה פרמטרים: מציב name, price, hasMilk, ויוצר `lastDate = new Date(day, month, year)`.
1. התכונות name, price ו-hasMilk מקבלות את ערכי הפרמטרים המתאימים.
2. התכונה lastDate היא עצם מטיפוס Date, אבל הבנאי מקבל שלושה מספרים. לכן יוצרים ממנה עצם חדש בעזרת הבנאי הנתון של Date: `new Date(day, month, year)`.
הקוד המלא של המחלקה, עם שלוש הפעולות של סעיף א:
public class Cake
{
private String name; // שם העוגה
private Date lastDate; // תאריך תפוגה
private int price; // מחיר
private boolean hasMilk; // true - חלבי, false - פרווה
// 1. פעולה בונה
public Cake(String name, int day, int month, int year, int price, boolean hasMilk)
{
this.name = name;
this.lastDate = new Date(day, month, year); // יוצרים עצם תאריך חדש
this.price = price;
this.hasMilk = hasMilk;
}
// 2. העוגה טרייה בתאריך d אם d אינו אחרי תאריך התפוגה
public boolean isFresh(Date d)
{
return d.before(this.lastDate) || d.equals(this.lastDate);
}
// 3. אותו תאריך תפוגה, אותו סוג, והפרש מחירים של 10 לכל היותר
public boolean isReplaceable(Cake other)
{
return this.lastDate.equals(other.lastDate)
&& this.hasMilk == other.hasMilk
&& Math.abs(this.price - other.price) <= 10;
}
// פעולות get, set ו-toString נתונות
}public class Cake
{
private string name; // שם העוגה
private Date lastDate; // תאריך תפוגה
private int price; // מחיר
private bool hasMilk; // true - חלבי, false - פרווה
// 1. פעולה בונה
public Cake(string name, int day, int month, int year, int price, bool hasMilk)
{
this.name = name;
this.lastDate = new Date(day, month, year); // יוצרים עצם תאריך חדש
this.price = price;
this.hasMilk = hasMilk;
}
// 2. העוגה טרייה בתאריך d אם d אינו אחרי תאריך התפוגה
public bool IsFresh(Date d)
{
return d.Before(this.lastDate) || d.Equals(this.lastDate);
}
// 3. אותו תאריך תפוגה, אותו סוג, והפרש מחירים של 10 לכל היותר
public bool IsReplaceable(Cake other)
{
return this.lastDate.Equals(other.lastDate)
&& this.hasMilk == other.hasMilk
&& Math.Abs(this.price - other.price) <= 10;
}
// פעולות Get, Set ו-ToString נתונות
}תשובה: הבנאי `Cake(String name, int day, int month, int year, int price, boolean hasMilk)` שבקוד.
`return d.before(lastDate) || d.equals(lastDate);`
"d אינו מאוחר מתאריך התפוגה" פירושו: d קודם לתאריך התפוגה או שווה לו (ביום התפוגה עצמו העוגה עדיין טרייה).
1. `d.before(this.lastDate)` – d קודם לתאריך התפוגה.
2. `d.equals(this.lastDate)` – d הוא בדיוק תאריך התפוגה.
3. מחזירים את ה"או" של שני התנאים. (שקול לכך: `!this.lastDate.before(d)` – תאריך התפוגה אינו לפני d.)
הקוד – בתוך המחלקה שבסעיף 1.
תשובה: `return d.before(this.lastDate) || d.equals(this.lastDate);`
מחזירה true כאשר `lastDate.equals(other.lastDate)`, `hasMilk == other.hasMilk` ו-`Math.abs(price - other.price) <= 10`.
שלושת התנאים צריכים להתקיים יחד, ולכן מחברים אותם ב-`&&`:
1. אותו תאריך תפוגה: משווים בין שני עצמי Date בעזרת `equals` של Date (ולא בעזרת `==`, שמשווה הפניות ולא ערכים).
2. אותו סוג: `this.hasMilk == other.hasMilk`.
3. הפרש מחירים עד 10: ההפרש יכול להיות שלילי, ולכן לוקחים ערך מוחלט: `Math.abs(this.price - other.price) <= 10`.
מכיוון שהפעולה כתובה בתוך המחלקה Cake, מותר לה לגשת ישירות לתכונות הפרטיות של other.
הקוד – בתוך המחלקה שבסעיף 1. (בכותרת שבשאלון ה-C# הפרמטר מופיע כ-`Date d`; לפי תיאור הפעולה הפרמטר הוא עוגה, ולכן כתבנו `IsReplaceable(Cake other)`.)
דוגמה: עוגות חלביות עם אותו תאריך במחירים 50 ו-60 – true; 50 ו-61 – false (הפרש 11); חלבית ופרווה – false.
תשובה: `return lastDate.equals(other.lastDate) && hasMilk == other.hasMilk && Math.abs(price - other.price) <= 10;`
סעיף ב
אם numOfCakes == 0 מחזירים null; אחרת חיפוש מקסימום לפי תאריך תפוגה: best מתחלפת ב-arr[i] כאשר best.getLastDate().before(arr[i].getLastDate()).
הרעיון: חיפוש "מקסימום" לפי תאריך התפוגה. העוגות נמצאות רק במקומות 0 עד numOfCakes-1, ולכן עוברים רק עליהם (שאר התאים הם null).
1. אם המקרר ריק (`numOfCakes == 0`) – מחזירים null.
2. מניחים שהעוגה הראשונה היא הטרייה ביותר.
3. לכל עוגה אחרת: אם תאריך התפוגה של best קודם לתאריך התפוגה שלה (`before`), היא טרייה יותר והופכת ל-best.
4. במקרה של תאריכים שווים best אינה מתחלפת, וזה בסדר – מותר להחזיר כל אחת מהן.
public Cake mostFresh()
{
if (this.numOfCakes == 0)
return null; // המקרר ריק
Cake best = this.arr[0];
for (int i = 1; i < this.numOfCakes; i++)
{
// arr[i] טרייה יותר אם תאריך התפוגה של best קודם לשלה
if (best.getLastDate().before(this.arr[i].getLastDate()))
best = this.arr[i];
}
return best;
}public Cake MostFresh()
{
if (this.numOfCakes == 0)
return null; // המקרר ריק
Cake best = this.arr[0];
for (int i = 1; i < this.numOfCakes; i++)
{
// arr[i] טרייה יותר אם תאריך התפוגה של best קודם לשלה
if (best.GetLastDate().Before(this.arr[i].GetLastDate()))
best = this.arr[i];
}
return best;
}תשובה: הפעולה שלמעלה.
עוברים עם i על העוגות; עוגה שתאריך התפוגה שלה before(d) מוחלפת בעוגה האחרונה, התא האחרון מקבל null ו-numOfCakes קטן ב-1 (בלי לקדם את i); אחרת i++.
הרעיון: מכיוון שאין צורך לשמור על הסדר, מוחקים עוגה במקום i כך: מעבירים אליו את העוגה האחרונה במערך, מאפסים את התא האחרון ל-null ומקטינים את numOfCakes. כך לא נוצר חור, וכל מחיקה עולה זמן קבוע.
1. עוברים בלולאת while עם i מ-0 כל עוד `i < numOfCakes` (הגבול משתנה תוך כדי, ולכן לא for עם גבול קבוע).
2. עוגה מקולקלת בתאריך d אם תאריך התפוגה שלה לפני d: `arr[i].getLastDate().before(d)`.
3. אם היא מקולקלת – מבצעים את המחיקה שלמעלה, ולא מקדמים את i: לתא i הגיעה עכשיו עוגה אחרת שעוד לא נבדקה (וייתכן שגם היא מקולקלת).
4. אחרת – מקדמים את i.
5. עדכוני הנתונים הנדרשים: גם המערך (בלי חורים, התאים שהתפנו מקבלים null) וגם המונה numOfCakes. אם המקרר ריק או שאין עוגות מקולקלות, הלולאה אינה משנה דבר.
public void removeNotFresh(Date d)
{
int i = 0;
while (i < this.numOfCakes)
{
if (this.arr[i].getLastDate().before(d))
{
// מעבירים את העוגה האחרונה למקום שהתפנה
this.arr[i] = this.arr[this.numOfCakes - 1];
this.arr[this.numOfCakes - 1] = null;
this.numOfCakes--;
// לא מקדמים את i: העוגה שהועברה למקום i עוד לא נבדקה
}
else
i++;
}
}public void RemoveNotFresh(Date d)
{
int i = 0;
while (i < this.numOfCakes)
{
if (this.arr[i].GetLastDate().Before(d))
{
// מעבירים את העוגה האחרונה למקום שהתפנה
this.arr[i] = this.arr[this.numOfCakes - 1];
this.arr[this.numOfCakes - 1] = null;
this.numOfCakes--;
// לא מקדמים את i: העוגה שהועברה למקום i עוד לא נבדקה
}
else
i++;
}
}דוגמה: במקרר Choco (10/7/2022), Cheese (5/7/2022), Apple (20/7/2022), Lemon (1/7/2022), Carrot (6/7/2022), ו-d = 6/7/2022. Cheese ו-Lemon מקולקלות: Cheese מוחלפת ב-Carrot, ו-Lemon (שהפכה לאחרונה) נמחקת. נשארות Choco, Carrot, Apple ו-numOfCakes = 3. Carrot, שתאריכה בדיוק d, אינה נמחקת.
סיבוכיות: כל סיבוב מקדם את i או מקטין את numOfCakes, ולכן יש לכל היותר n סיבובים – .
תשובה: הפעולה שלמעלה.
מעבר ראשון: לכל שם מחפשים עוגה במקרר; שם שלא נמצא מודפס וההזמנה נכשלת – מחזירים 0. אחרת מעבר שני: מדפיסים כל עוגה (toString) וסוכמים את המחירים; מחזירים את הסכום.
הרעיון: צריך לדעת אם כל העוגות קיימות לפני שמדפיסים פרטים, ולכן עובדים בשני מעברים. לחיפוש עוגה לפי שם כותבים פעולת עזר indexOf שמחזירה את מקום העוגה במערך או -1.
1. indexOf(name): עוברת על העוגות 0 עד numOfCakes-1 ומשווה את `getName()` לשם המבוקש (ב-Java משווים מחרוזות עם `equals`, לא עם `==`).
2. מעבר ראשון: לכל שם ב-names, אם indexOf מחזירה -1 – העוגה חסרה: מדפיסים את השם ומסמנים `ok = false`. ממשיכים בלולאה כדי להדפיס את כל השמות החסרים.
3. אם `ok` הוא false – מחזירים 0.
4. מעבר שני (כל העוגות קיימות): לכל שם מוצאים את העוגה, מדפיסים את פרטיה (הדפסת העצם מפעילה את toString הנתונה) ומוסיפים את מחירה לסכום.
5. מחזירים את הסכום.
ההנחה שכל שם מופיע ב-names פעם אחת מבטיחה שאין צורך לבדוק אם יש במקרר מספיק עותקים של אותה עוגה. השאלה אינה דורשת להוציא את העוגות מהמקרר, ולכן המקרר אינו משתנה.
// פעולת עזר: מחזירה את המקום של עוגה בשם name, או -1 אם אין כזו
private int indexOf(String name)
{
for (int i = 0; i < this.numOfCakes; i++)
{
if (this.arr[i].getName().equals(name))
return i;
}
return -1;
}
public int purchaseOrder(String[] names)
{
boolean ok = true;
// מעבר ראשון: מחפשים כל עוגה; עוגה חסרה - מדפיסים את שמה
for (int i = 0; i < names.length; i++)
{
if (indexOf(names[i]) == -1)
{
System.out.println(names[i]);
ok = false;
}
}
if (!ok)
return 0;
// מעבר שני: כל העוגות קיימות - מדפיסים פרטים וסוכמים מחירים
int sum = 0;
for (int i = 0; i < names.length; i++)
{
Cake c = this.arr[indexOf(names[i])];
System.out.println(c); // toString של Cake
sum += c.getPrice();
}
return sum;
}// פעולת עזר: מחזירה את המקום של עוגה בשם name, או -1 אם אין כזו
private int IndexOf(string name)
{
for (int i = 0; i < this.numOfCakes; i++)
{
if (this.arr[i].GetName() == name)
return i;
}
return -1;
}
public int PurchaseOrder(string[] names)
{
bool ok = true;
// מעבר ראשון: מחפשים כל עוגה; עוגה חסרה - מדפיסים את שמה
for (int i = 0; i < names.Length; i++)
{
if (IndexOf(names[i]) == -1)
{
Console.WriteLine(names[i]);
ok = false;
}
}
if (!ok)
return 0;
// מעבר שני: כל העוגות קיימות - מדפיסים פרטים וסוכמים מחירים
int sum = 0;
for (int i = 0; i < names.Length; i++)
{
Cake c = this.arr[IndexOf(names[i])];
Console.WriteLine(c); // ToString של Cake
sum += c.GetPrice();
}
return sum;
}דוגמה: במקרר Choco (120 ש"ח) ו-Apple (80 ש"ח) ועוד עוגות. עבור names = {"Choco", "Apple"} יודפסו פרטי שתי העוגות ויוחזר . עבור names = {"Choco", "Banana", "Kiwi"} יודפסו Banana ו-Kiwi ויוחזר 0.
סיבוכיות: לכל אחד מ-k השמות מתבצע חיפוש על n העוגות – .
תשובה: הפעולה שלמעלה.
שאלה 13 · מעקב אחר פעולות על מחרוזות ומיון
נתונות שלוש הפעולות הבאות:
public static int one(String s, int i)
{
int m = 0;
for (int j = 1; j <= i; j++)
{
if (s.charAt(j) < s.charAt(m))
m = j;
}
return m;
}
public static String two(String s, int i)
{
String r ="";
for(int j = 0;j <= i;j++)
{
r += s.charAt(i-j);
}
r += s.substring(i+1);
return r ;
}
public static String three(String s)
{
for (int i = s.length()-1; i > 0; i--)
{
int m = one(s, i);
s = two(s, m);
s = two(s, i);
}
return s;
}public static int One(string s, int i)
{
int m = 0;
for (int j = 1; j <= i; j++)
{
if (s[j] < s[m])
m = j;
}
return m;
}
public static string Two(string s, int i)
{
string r ="";
for(int j = 0;j <= i; j++)
{
r += s[i - j];
}
r += s.Substring(i+1);
return r ;
}
public static string Three(string s)
{
for (int i = s.Length-1; i > 0; i--)
{
int m = One(s, i);
s = Two(s, m);
s = Two(s, i);
}
return s;
}תזכורת: הפונקציה s.charAt(k) מחזירה תו שנמצא במקום k במחרוזת s. (ב-C#: הפונקציה s.Substring(k) מחזירה תת-מחרוזת ממקום k עד סוף המחרוזת.)
עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `one("VACCINE",6)` ורשמו מה תחזיר הפעולה.
עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `two("VACCINE",3)` ורשמו מה תחזיר הפעולה.
עקבו בעזרת טבלת מעקב אחרי זימון הפעולה `three("VACCINE")` ורשמו מה תחזיר הפעולה.
אין צורך לעקוב אחרי פעולות one ו- two.
מה מבצעת הפעולה three באופן כללי?
◂ פתרון מלא לשאלה 13
סעיף א
הפעולה מחזירה 1.
המחרוזת לפי מקומות: 0-V, 1-A, 2-C, 3-C, 4-I, 5-N, 6-E. הפעולה מתחילה עם m = 0 ועוברת על j = 1 עד 6; אם התו במקום j קטן (לפי סדר הא"ב) מהתו במקום m, m מתעדכן ל-j.
הפעולה מחזירה את מקום התו הקטן ביותר בין המקומות 0 עד i – כאן 'A' במקום 1.
תשובה: one("VACCINE",6) מחזירה 1.
סעיף ב
הפעולה מחזירה "CCAVINE".
הלולאה מוסיפה ל-r את התווים מהמקום i = 3 אחורה עד מקום 0, ואחר כך מוסיפה את שאר המחרוזת מהמקום i+1 = 4.
אחרי הלולאה: `s.substring(4)` = "INE", ולכן r = "CCAV" + "INE" = "CCAVINE".
כלומר two הופכת את סדר התווים במקומות 0 עד i ומשאירה את שאר המחרוזת כמו שהיא.
תשובה: two("VACCINE",3) מחזירה "CCAVINE".
סעיף ג
הפעולה מחזירה "VNIECCA".
לפי סעיפים א ו-ב: `one(s, i)` מחזירה את מקום התו הקטן ביותר בין המקומות 0 עד i, ו-`two(s, k)` הופכת את התחילית s[0..k]. בכל סיבוב:
1. `two(s, m)` מביאה את התו הקטן ביותר (מבין 0..i) למקום 0;
2. `two(s, i)` הופכת את 0..i, וכך התו הזה עובר למקום i.
i מתחיל ב-6 (אורך המחרוזת פחות 1) ויורד עד 1.
כאשר i = 0 תנאי הלולאה `i > 0` נכשל, ומוחזרת s.
תשובה: three("VACCINE") מחזירה "VNIECCA".
סעיף ד
ממיינת את תווי המחרוזת בסדר יורד (מהגדול לקטן) ומחזירה את המחרוזת הממוינת.
1. בכל סיבוב, החלק s[0..i] הוא החלק שעוד לא סודר, והחלק s[i+1..] כבר מסודר.
2. one מוצאת את התו הקטן ביותר בחלק הלא מסודר; two(s, m) מביאה אותו לתחילת המחרוזת, ו-two(s, i) מעבירה אותו לסוף החלק הלא מסודר – למקום i.
3. כך במקום האחרון נקבע התו הקטן ביותר, לפניו הקטן הבא, וכן הלאה. בסוף התווים מסודרים מהגדול (בהתחלה) לקטן (בסוף) לפי סדר הא"ב (קודי התווים). זהו מיון שבו מזיזים איבר רק בעזרת היפוך של תחילית (מיון "פנקייק").
לדוגמה, ב-"VACCINE" התווים בסדר יורד הם V, N, I, E, C, C, A – בדיוק "VNIECCA" מסעיף ג.
תשובה: three ממיינת את תווי המחרוזת בסדר יורד (מהתו הגדול לקטן) ומחזירה את המחרוזת הממוינת.
שאלה 14 · כתמים במערך דו-ממדי ומערך מלוכלך
מערך דו-ממדי 2x2 נקרא "כתם" אם כל האיברים שלו שווים לאותו ערך. הערך הזה נקרא "צבע הכתם".
לדוגמה: במערך הנתון יש ארבעה "כתמים":
שני "כתמים" של 0, כתם עם של 1 וכתם של 3.

כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים וערך value. הפעולה תבדוק אם במערך קיים "כתם" עם ערך value. אם כן – הפעולה תחזיר true, ולא – הפעולה תחזיר false.
מערך דו-ממדי נקרא "מלוכלך" אם יש בו יותר מ- 3 "כתמים" של צבעים שונים.
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים חד ספרתיים (בין 0 ל- 9). הפעולה תבדוק אם המערך הוא "מערך מלוכלך". אם כן – הפעולה תחזיר true, ולא – הפעולה תחזיר false.
מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 14
סעיף א
עוברים על כל פינה שמאלית-עליונה (i, j) עם i < rows-1 ו-j < cols-1; אם ארבעת התאים [i][j], [i][j+1], [i+1][j], [i+1][j+1] שווים ל-value מחזירים true; בסוף false.
הרעיון: כל כתם נקבע על ידי הפינה השמאלית-העליונה שלו (i, j); הכתם כולל את התאים [i][j], [i][j+1], [i+1][j], [i+1][j+1]. כדי ששני התאים הימניים והתחתונים יהיו בתוך המערך, i רץ עד מספר השורות פחות 2 ו-j עד מספר העמודות פחות 2.
1. עוברים בשתי לולאות על כל הפינות האפשריות.
2. לכל פינה בודקים שארבעת התאים שווים ל-value (ארבעה תנאים מחוברים ב-`&&`).
3. ברגע שנמצא כתם כזה מחזירים true; אם עברנו על כל הפינות ולא נמצא – false.
// א. האם יש "כתם" 2x2 שכל איבריו שווים ל-value
public static boolean hasStain(int[][] mat, int value)
{
for (int i = 0; i < mat.length - 1; i++)
{
for (int j = 0; j < mat[0].length - 1; j++)
{
// (i, j) הוא הפינה השמאלית-העליונה של ריבוע 2x2
if (mat[i][j] == value && mat[i][j + 1] == value
&& mat[i + 1][j] == value && mat[i + 1][j + 1] == value)
return true;
}
}
return false;
}// א. האם יש "כתם" 2x2 שכל איבריו שווים ל-value
public static bool HasStain(int[,] mat, int value)
{
for (int i = 0; i < mat.GetLength(0) - 1; i++)
{
for (int j = 0; j < mat.GetLength(1) - 1; j++)
{
// (i, j) הוא הפינה השמאלית-העליונה של ריבוע 2x2
if (mat[i, j] == value && mat[i, j + 1] == value
&& mat[i + 1, j] == value && mat[i + 1, j + 1] == value)
return true;
}
}
return false;
}בדיקה עם המערך שבשאלה: עבור value = 0, 1, 3 מוחזר true, ועבור כל ערך אחר (2, 4, 5, ..., 9) מוחזר false.
תשובה: הפעולה שלמעלה.
סעיף ב
לכל צבע 0 עד 9 בודקים בעזרת הפעולה מסעיף א אם יש כתם בצבע הזה וסופרים את הצבעים; מחזירים true אם מספרם גדול מ-3.
הרעיון: סופרים צבעים שונים, לא כתמים: שני כתמים באותו צבע נספרים פעם אחת. מאחר שכל הערכים חד-ספרתיים, יש רק 10 צבעים אפשריים (0 עד 9), ולכן אפשר פשוט לבדוק כל צבע בעזרת הפעולה מסעיף א.
1. מונה colors מתחיל ב-0.
2. לכל value מ-0 עד 9: אם `hasStain(mat, value)` מחזירה true – יש לפחות כתם אחד בצבע הזה, ומגדילים את colors.
3. המערך מלוכלך אם יש יותר מ-3 צבעים כאלה, כלומר `colors > 3` (לפחות 4).
// ב. "מלוכלך": יותר מ-3 כתמים בצבעים שונים
public static boolean isDirty(int[][] mat)
{
int colors = 0; // מספר הצבעים השונים שיש להם כתם
for (int value = 0; value <= 9; value++)
{
if (hasStain(mat, value))
colors++;
}
return colors > 3;
}// ב. "מלוכלך": יותר מ-3 כתמים בצבעים שונים
public static bool IsDirty(int[,] mat)
{
int colors = 0; // מספר הצבעים השונים שיש להם כתם
for (int value = 0; value <= 9; value++)
{
if (HasStain(mat, value))
colors++;
}
return colors > 3;
}בדיקה עם המערך שבשאלה: יש בו ארבעה כתמים, אבל רק בשלושה צבעים שונים (0, 1, 3). לכן colors = 3 והפעולה מחזירה false – המערך אינו מלוכלך. אם נוסיף כתם של 5 (למשל במקומות [0][2], [0][3], [1][2], [1][3]), יתקבל colors = 4 ויוחזר true.
תשובה: הפעולה שלמעלה.
סעיף ג
שתיהן (n שורות, m עמודות): סעיף א עובר פעם אחת על כל הפינות; סעיף ב מפעיל את א 10 פעמים – קבוע.
נסמן ב-n את מספר השורות וב-m את מספר העמודות.
1. סעיף א: שתי הלולאות עוברות על פינות לכל היותר, ולכל פינה מתבצעות לכל היותר ארבע השוואות – זמן קבוע. לכן במקרה הגרוע (אין כתם) הזמן הוא .
2. סעיף ב: הפעולה מזמנת את פעולת סעיף א 10 פעמים בדיוק (לצבעים 0 עד 9). 10 הוא קבוע שאינו תלוי בגודל המערך, ולכן הזמן הוא .
תשובה: הסיבוכיות של שתי הפעולות היא – לינארית במספר התאים של המערך.