דילוג לתוכן המרכזי

מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2021 מועד ב'

הנדסת תוכנה · סמל 97104 · 13 שאלות · פתרון מלא לכל סעיף

מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2021 מועד ב', כל 13 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.

הנחיות הבחינה

משך הבחינה: ארבע שעות וחצי.

מבנה השאלון: בשאלון זה שני מבחנים. עליך לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:

מבחן ב- Java (עמוד 2)

מבחן ב- C# (עמוד 15)

בכל מבחן 13 שאלות.

חלק א' - 40 נקודות

שאלות 1-6: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 10 נקודות.

חלק ב' - 24 נקודות

שאלות 7-9: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 12 נקודות.

חלק ג' - 36 נקודות

שאלות 10-13: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 18 נקודות.

בסך הכול: 100 נקודות.

חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).

2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.

אין לצרף ספרים או חוברות עם פתרונות.

שאלה 1 · מספרים אקראיים: סכום ספרות וממוצע

כתוב קטע תוכנית שמייצר 39 מספרים אקראיים תלת-ספרתיים חיוביים.

•עבור כל מספר זוגי יש להדפיס את סכום ספרותיו.

•הקוד יחשב וידפיס את ממוצע של המספרים שנוצרו.

◂ פתרון מלא לשאלה 1

פתרון

תשובה:

לולאה של 39 סיבובים: מגרילים מספר בין 100 ל-999, צוברים אותו לסכום, ואם הוא זוגי מפרקים אותו לספרות ומדפיסים את סכומן; בסוף מדפיסים sum / 39 כמספר ממשי.

הרעיון: לולאה אחת של 39 סיבובים. בכל סיבוב:

1. הגרלה: מספר תלת-ספרתי חיובי הוא מספר בין 100 ל-999, כלומר יש 900 אפשרויות. ב-Java: `(int)(Math.random() * 900) + 100` (הביטוי `Math.random() * 900` נותן ערך ממשי בין 0 ל-899.99, ואחרי ההמרה ל-int והוספת 100 מתקבל 100..999). ב-C#: `rnd.Next(100, 1000)` (הגבול העליון אינו כלול).

2. צבירה לממוצע: מוסיפים את המספר למשתנה `sum` – הממוצע הוא של כל 39 המספרים, לא רק של הזוגיים.

3. מספר זוגי (`num % 2 == 0`): מפרקים אותו לספרות בעזרת עותק `temp`: הספרה הימנית היא `temp % 10`, ואז מקצצים אותה ב-`temp / 10`, עד ש-`temp` מתאפס. מדפיסים את סכום הספרות.

4. אחרי הלולאה: הממוצע הוא sum39\frac{sum}{39}. ממירים ל-double לפני החילוק, אחרת חילוק של שני שלמים יקצץ את השבר.

לדוגמה, אם הוגרל 516 (זוגי), יודפס 5+1+6=125+1+6=12.

Java:

int sum = 0;                                       // סכום כל המספרים שנוצרו
for (int i = 1; i <= 39; i++)
{
    int num = (int) (Math.random() * 900) + 100;   // מספר תלת-ספרתי 100..999
    sum += num;
    if (num % 2 == 0)                              // מספר זוגי
    {
        int temp = num, digitsSum = 0;
        while (temp > 0)                           // פירוק לספרות
        {
            digitsSum += temp % 10;
            temp = temp / 10;
        }
        System.out.println(num + ": " + digitsSum);
    }
}
double avg = (double) sum / 39;
System.out.println("Average: " + avg);

C#:

Random rnd = new Random();
int sum = 0;                                       // סכום כל המספרים שנוצרו
for (int i = 1; i <= 39; i++)
{
    int num = rnd.Next(100, 1000);                 // מספר תלת-ספרתי 100..999
    sum += num;
    if (num % 2 == 0)                              // מספר זוגי
    {
        int temp = num, digitsSum = 0;
        while (temp > 0)                           // פירוק לספרות
        {
            digitsSum += temp % 10;
            temp = temp / 10;
        }
        Console.WriteLine(num + ": " + digitsSum);
    }
}
double avg = (double) sum / 39;
Console.WriteLine("Average: " + avg);

תשובה: קטע התוכנית שלמעלה.

שאלה 2 · מחלקת חטיף: חטיף בריא וספירה במערך

במחלקה חטיף – Snack יש ארבע תכונות:

•שם – name מטיפוס מחרוזת, String

•משקל – weight מטיפוס מספר שלם, int

•מחיר – cost מטיפוס מספר ממשי, double

•מספר קלוריות – cal מטיפוס מספר שלם, int

במחלקה Snack הוגדרה פעולה בונה (בנאי, constructor) המקבלת פרמטר של כל תכונה וקובעת את הערכים של תכונות העצם. המחלקה כוללת פעולות get/set לכל אחת מהתכונות.

א.

משרד הבריאות מגדיר "חטיף בריא" חטיף שמספר הקלוריות שלו לכל 100 גרם משקל אינו עולה על 120. כתוב פעולה הבודקת אם חטיף עונה על הגדרה של "חטיף בריא". הפעולה תחזיר true, אם חטיף עונה על ההגדרה, אם לא הפעולה תחזיר false.

(5 נקודות)
ב.

כתוב פעולה חיצונית המקבלת מערך הפניות לעצמים מסוג Snack בשם arrS ומחזירה את מספר "החטיפים הבריאים" אשר מחירם נמוך מ- 10 ₪.

כותרת הפעולה: `public static int goodSnacks(Snack[] arrS)`

(5 נקודות)
◂ פתרון מלא לשאלה 2

סעיף א

תשובה:

פעולה פנימית isHealthy() שמחזירה cal * 100.0 / weight <= 120.

הרעיון: התכונה cal היא מספר הקלוריות בכל החטיף, שמשקלו weight גרם. כדי להשוות לסף של 120 קלוריות ל-100 גרם, ממירים לקלוריות ל-100 גרם:

calPer100=cal⋅100weight\text{calPer100}=\frac{cal\cdot 100}{weight}

החטיף בריא אם calPer100≤120\text{calPer100}\le 120.

1. הפעולה נכתבת בתוך המחלקה Snack (פעולה פנימית), ולכן ניגשת ישירות לתכונות.

2. כופלים ב-100.0 (ממשי) כדי שהחילוק לא יהיה חילוק שלמים.

3. דוגמה: חטיף של 200 גרם עם 240 קלוריות: 240⋅100200=120≤120\frac{240\cdot 100}{200}=120\le 120 – בריא. חטיף של 50 גרם עם 61 קלוריות: 61⋅10050=122>120\frac{61\cdot 100}{50}=122>120 – לא בריא.

Java:

public boolean isHealthy()
{
    double calPer100 = this.cal * 100.0 / this.weight;   // קלוריות ל-100 גרם
    return calPer100 <= 120;
}

C#:

public bool IsHealthy()
{
    double calPer100 = this.cal * 100.0 / this.weight;   // קלוריות ל-100 גרם
    return calPer100 <= 120;
}

תשובה: `isHealthy()` מחזירה `cal * 100.0 / weight <= 120`.

סעיף ב

תשובה:

עוברים על המערך וסופרים עצמים (לא null) שעבורם isHealthy() מחזירה true וגם getCost() < 10.

הרעיון: מונה שמתחיל ב-0, ולולאה על כל תאי המערך. לכל חטיף בודקים שני תנאים: שהוא בריא (בעזרת הפעולה מסעיף א) ושמחירו נמוך מ-10. הפעולה חיצונית, ולכן המחיר נקרא דרך `getCost()` (התכונה פרטית).

1. אם תא במערך ריק (null) מדלגים עליו, כדי לא לזמן פעולה על הפניה ריקה. בגלל הערכה מקוצרת של `&&`, אם `arrS[i] != null` שקרי – שאר התנאי לא מחושב.

2. אם שני התנאים מתקיימים – מגדילים את המונה.

3. בסוף מחזירים את המונה.

Java:

public static int goodSnacks(Snack[] arrS)
{
    int count = 0;
    for (int i = 0; i < arrS.length; i++)
    {
        if (arrS[i] != null && arrS[i].isHealthy() && arrS[i].getCost() < 10)
            count++;
    }
    return count;
}

C#:

public static int GoodSnacks(Snack[] arrS)
{
    int count = 0;
    for (int i = 0; i < arrS.Length; i++)
    {
        if (arrS[i] != null && arrS[i].IsHealthy() && arrS[i].GetCost() < 10)
            count++;
    }
    return count;
}

תשובה: `goodSnacks` מחזירה את מספר החטיפים שעבורם `isHealthy()` אמת ו-`getCost() < 10`.

שאלה 3 · מחלקות ספר וספרייה: חיפוש והוספה

נתונה המחלקה ספר – Book עם שלוש תכונות:

•שם הספר – name מטיפוס מחרוזת.

•שם המחבר – author מטיפוס מחרוזת.

•מספר עמודים – pages מטיפוס שלם.

א.

כתוב במחלקה Book את הפעולה isSameBook(Book b). הפעולה מחזירה true אם שם הספר ושם המחבר של העצם שמפעיל את הפעולה זהים לשם הספר ושם המחבר של העצם שמתקבל כפרמטר אם לא, הפעולה תחזיר false.

(2 נקודות)

נתונה המחלקה ספרייה – Library שיש לה שלוש תכונות:

•מערך bookArr מטיפוס Book.

•מערך copyArr מטיפוס שלם.

האיבר אשר נמצא במקום k במערך copyArr הוא מספר העותקים של הספר bookArr[k].

•מספר הספרים הנוכחי – current מטיפוס שלם אשר ערכו קטן מגודל המערך.

מספר זה הוא מספר הספרים אשר נמצאים בספריה ברגע נתון.

במחלקה Library הוגדרה הפעולה הבונה:

public Library()
{
    this.bookArr = new Book [2000];
    this.copyArr = new int [2000];
    this.current = 0;
}
ב.

כתוב במחלקה Library את הפעולה bookPosition(Book b). הפעולה בודקת אם ספר b נמצא בספרייה.

אם כן – הפעולה תחזיר את מיקומו במערך הספרים. אם הספר לא קיים – הפעולה תחזיר -1.

(3 נקודות)
ג.

כתוב במחלקה Library פעולה שתקבל הפנייה לעצם מסוג Book ותוסיף אותו לספרייה.

אם הספר כבר נמצא בספרייה הפעולה תעדכן מספר העותקים שלו.

אם הספר לא נמצא בספרייה הפעולה מוסיפה עותק אחד של הספר לספרייה.

אם הספר לא נמצא בספרייה אבל אין מקום להוסיף ספר חדש, הפעולה אינה מבצעת דבר.

הערה: חובה להשתמש בפעולה שכתבת בסעיף ב'.

(5 נקודות)
◂ פתרון מלא לשאלה 3

סעיף א

תשובה:

מחזירים את תוצאת ההשוואה של name וגם של author (ב-Java עם equals, ב-C# עם ==).

הרעיון: שני ספרים נחשבים אותו ספר אם גם השם וגם המחבר זהים (מספר העמודים אינו משתתף בהשוואה). מחזירים את הגימום (וגם) של שתי ההשוואות.

1. ב-Java משווים תוכן של מחרוזות בעזרת `equals` (האופרטור `==` משווה הפניות ולא תוכן).

2. ב-C# האופרטור `==` על string משווה את התוכן.

3. התכונות של `b` נקראות דרך פעולות get (או ישירות – מותר לגשת לתכונה פרטית של עצם אחר מאותה מחלקה).

Java:

public boolean isSameBook(Book b)
{
    return this.name.equals(b.getName()) && this.author.equals(b.getAuthor());
}

C#:

public bool IsSameBook(Book b)
{
    return this.name == b.GetName() && this.author == b.GetAuthor();
}

תשובה: `isSameBook` מחזירה `true` רק אם `name` ו-`author` של שני הספרים זהים.

סעיף ב

תשובה:

חיפוש סדרתי בתאים 0 עד current-1 בעזרת isSameBook; מחזירים את המקום הראשון שנמצא, אחרת -1.

הרעיון: חיפוש סדרתי. הספרים שמורים בתאים 0 עד `current-1` של `bookArr` (שאר התאים ריקים), ולכן הלולאה רצה רק עד `current`.

1. לכל מקום k בודקים בעזרת הפעולה מסעיף א אם `bookArr[k]` הוא אותו ספר כמו b.

2. אם כן – מחזירים מיד את k (המיקום במערך הספרים).

3. אם הלולאה הסתיימה בלי למצוא – הספר לא קיים, מחזירים -1.

Java:

public int bookPosition(Book b)
{
    for (int k = 0; k < this.current; k++)
    {
        if (this.bookArr[k].isSameBook(b))
            return k;
    }
    return -1;
}

C#:

public int BookPosition(Book b)
{
    for (int k = 0; k < this.current; k++)
    {
        if (this.bookArr[k].IsSameBook(b))
            return k;
    }
    return -1;
}

תשובה: `bookPosition` מחזירה את המקום k שבו `bookArr[k].isSameBook(b)`, או -1.

סעיף ג

תשובה:

pos = bookPosition(b); אם pos != -1 מגדילים את copyArr[pos]; אחרת, אם current קטן מגודל המערך, שמים את b ב-bookArr[current], copyArr[current] = 1 ומגדילים את current.

הרעיון: קודם מחפשים את הספר בעזרת `bookPosition` (סעיף ב), ולפי התוצאה מטפלים בשלושת המקרים:

1. הספר קיים (`pos != -1`): מוסיפים עותק – `copyArr[pos]++`.

2. הספר לא קיים ויש מקום (`current < bookArr.length`): התא הפנוי הראשון הוא `current`. שמים בו את הספר, מספר העותקים שלו הוא 1, ומגדילים את `current` ב-1.

3. הספר לא קיים ואין מקום: לא עושים דבר.

Java:

public void addBook(Book b)
{
    int pos = this.bookPosition(b);
    if (pos != -1)                                   // הספר כבר בספרייה
    {
        this.copyArr[pos]++;
    }
    else if (this.current < this.bookArr.length)     // ספר חדש ויש מקום
    {
        this.bookArr[this.current] = b;
        this.copyArr[this.current] = 1;
        this.current++;
    }
    // אחרת – אין מקום, לא עושים דבר
}

C#:

public void AddBook(Book b)
{
    int pos = this.BookPosition(b);
    if (pos != -1)                                   // הספר כבר בספרייה
    {
        this.copyArr[pos]++;
    }
    else if (this.current < this.bookArr.Length)     // ספר חדש ויש מקום
    {
        this.bookArr[this.current] = b;
        this.copyArr[this.current] = 1;
        this.current++;
    }
    // אחרת – אין מקום, לא עושים דבר
}

תשובה: הפעולה `addBook` שלמעלה (עדכון עותקים, הוספה ב-`current`, או כלום כשאין מקום).

שאלה 4 · בדיקת תקינות סיסמה וקליטה חוזרת

משתמש חדש שרצה להירשם לאתר "ללמוד מחשבים ולהצליח" חייב לבחור סיסמה. סיסמה תקינה צריכה לענות על 4 דרישות:

•אורך הסיסמה צריך להיות שמונה תווים לפחות.

•הסיסמה צריכה להתחיל באות אנגלית גדולה ('A'…'Z').

•הסיסמה צריכה להסתיים בספרה ('0'…'9').

•אין בסיסמה שני תווים צמודים זהים.

א.

כתוב פעולה המקבלת מחרוזת ובודקת אם המחרוזת היא סיסמה תקינה.

(5 נקודות)
ב.

כתוב קטע תוכנית הקולט מהמשתמש סיסמה עד שתיקלט סיסמה תקינה. אחרי סיום הקלט, קטע התוכנית ידפיס את מספר הפעמים שבו נקלטה סיסמה לא תקינה.

(5 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

פעולה isValid(s): false אם האורך קטן מ-8, אם התו הראשון אינו בין 'A' ל-'Z', אם התו האחרון אינו בין '0' ל-'9', או אם יש i שעבורו s[i] == s[i+1]; אחרת true.

הרעיון: בודקים את ארבע הדרישות אחת אחרי השנייה, ומחזירים false ברגע שדרישה אחת נכשלת. רק אם כולן עברו מחזירים true.

1. אורך: אם `s.length() < 8` – לא תקינה. (בדיקה זו קודמת, כך שבהמשך בטוח שיש תו ראשון ותו אחרון.)

2. תו ראשון: אות אנגלית גדולה – התו בטווח `'A'` עד `'Z'` (קודי התווים רציפים).

3. תו אחרון (במקום `length-1`): ספרה – בטווח `'0'` עד `'9'`.

4. תווים צמודים: עוברים על כל זוג סמוך (`i`, `i+1`) עבור `i` מ-0 עד `length-2`; אם נמצא זוג זהה – לא תקינה.

לדוגמה: `"Abcdefg1"` תקינה; `"Abcdeffg1"` לא תקינה (ff צמודים); `"Abcdefgh"` לא תקינה (לא מסתיימת בספרה).

Java:

public static boolean isValid(String s)
{
    if (s.length() < 8)                              // דרישה 1
        return false;
    char first = s.charAt(0);
    if (first < 'A' || first > 'Z')                  // דרישה 2
        return false;
    char last = s.charAt(s.length() - 1);
    if (last < '0' || last > '9')                    // דרישה 3
        return false;
    for (int i = 0; i < s.length() - 1; i++)         // דרישה 4
    {
        if (s.charAt(i) == s.charAt(i + 1))
            return false;
    }
    return true;
}

C#:

public static bool IsValid(string s)
{
    if (s.Length < 8)                                // דרישה 1
        return false;
    char first = s[0];
    if (first < 'A' || first > 'Z')                  // דרישה 2
        return false;
    char last = s[s.Length - 1];
    if (last < '0' || last > '9')                    // דרישה 3
        return false;
    for (int i = 0; i < s.Length - 1; i++)           // דרישה 4
    {
        if (s[i] == s[i + 1])
            return false;
    }
    return true;
}

תשובה: הפעולה `isValid` שלמעלה.

סעיף ב

תשובה:

קולטים סיסמה; כל עוד isValid מחזירה false מגדילים מונה וקולטים שוב; בסוף מדפיסים את המונה.

הרעיון: לולאת while שתנאי העצירה שלה הוא קליטת סיסמה תקינה (הפעולה מסעיף א). כל סיבוב של הלולאה מתאים לסיסמה לא תקינה אחת, ולכן מונה שגדל בכל סיבוב סופר בדיוק את הסיסמאות הלא תקינות.

1. קולטים סיסמה ראשונה לפני הלולאה.

2. כל עוד הסיסמה לא תקינה: מגדילים את המונה וקולטים סיסמה חדשה.

3. כשהלולאה מסתיימת נקלטה סיסמה תקינה (היא לא נספרת), ומדפיסים את המונה.

לדוגמה, עבור הקלט `abc`, `Abcdefgh`, `Abcdeffg1`, `Abcdefg1` יודפס 3.

Java:

int countBad = 0;
String pass = in.next();
while (!isValid(pass))
{
    countBad++;                  // הסיסמה שנקלטה לא תקינה
    pass = in.next();            // קולטים סיסמה חדשה
}
System.out.println(countBad);

C#:

int countBad = 0;
string pass = Console.ReadLine();
while (!IsValid(pass))
{
    countBad++;                  // הסיסמה שנקלטה לא תקינה
    pass = Console.ReadLine();   // קולטים סיסמה חדשה
}
Console.WriteLine(countBad);

תשובה: קטע התוכנית שלמעלה.

שאלה 5 · סדרה אקראית עולה ממש של מספרים דו-ספרתיים

הגדרה: סדרת מספרים "עולה ממש" היא סדרת מספרים שכל איבר בסדרה גדול מקודמו.

כתוב פעולה אשר קולטת מספר שלם וחיובי num ומייצרת ומדפיסה num מספרים אקראיים דו-ספרתיים חיוביים שהם סדרה "עולה ממש".

אפשר להניח ש- num<90

◂ פתרון מלא לשאלה 5

פתרון

תשובה:

מגרילים כל איבר בטווח שבין (הקודם + 1) לבין 99 פחות מספר האיברים שעוד נותרו אחריו; כך הסדרה עולה ממש ותמיד נשאר מקום לכל num האיברים.

הרעיון: כל איבר חייב להיות גדול ממש מהקודם, ולכן הגבול התחתון להגרלה הוא `prev + 1`. אבל אם נגריל מספר גדול מדי (למשל 99 כבר באיבר הראשון), לא יישאר מקום לאיברים הבאים. לכן גם הגבול העליון תלוי במקום: אחרי האיבר שמספרו k (מתחילים מ-0) נשארים עוד num−1−knum-1-k איברים, וכל אחד מהם גדול לפחות ב-1 מקודמו, ולכן האיבר הנוכחי יכול להיות לכל היותר 99−(num−1−k)99-(num-1-k).

1. אתחול: `prev = 9`, כך שהאיבר הראשון יהיה לפחות 10 (דו-ספרתי).

2. בכל סיבוב k: `low = prev + 1`, `high = 99 - (num - 1 - k)`, ומגרילים מספר שלם בטווח `[low, high]`: ב-Java `low + (int)(Math.random() * (high - low + 1))`, ב-C# `rnd.Next(low, high + 1)`.

3. מדפיסים את המספר ומעדכנים `prev`.

למה הטווח אף פעם לא ריק: באיבר הראשון low=10low=10 ו-high=100−num≥11high=100-num\ge 11 (כי num<90num<90). אם בסיבוב הקודם הוגרל לכל היותר 99−(num−k)99-(num-k), אז בסיבוב הנוכחי low≤100−num+k=highlow\le 100-num+k=high. באיבר האחרון (k=num−1k=num-1) מתקבל high=99high=99, כך שכל המספרים דו-ספרתיים.

דוגמה: עבור num=5num=5 האיבר הראשון מוגרל בין 10 ל-95; אם יצא 93, השני מוגרל בין 94 ל-96 וכן הלאה.

Java:

public static void increasingRandom()
{
    int num = in.nextInt();
    int prev = 9;                          // "קודם" לאיבר הראשון: האיבר הראשון לפחות 10
    for (int k = 0; k < num; k++)
    {
        int low = prev + 1;                // גדול ממש מהקודם
        int high = 99 - (num - 1 - k);     // משאירים מקום לאיברים שנותרו
        int x = low + (int) (Math.random() * (high - low + 1));
        System.out.print(x + " ");
        prev = x;
    }
    System.out.println();
}

C#:

public static void IncreasingRandom()
{
    Random rnd = new Random();
    int num = int.Parse(Console.ReadLine());
    int prev = 9;                          // "קודם" לאיבר הראשון: האיבר הראשון לפחות 10
    for (int k = 0; k < num; k++)
    {
        int low = prev + 1;                // גדול ממש מהקודם
        int high = 99 - (num - 1 - k);     // משאירים מקום לאיברים שנותרו
        int x = rnd.Next(low, high + 1);
        Console.Write(x + " ");
        prev = x;
    }
    Console.WriteLine();
}

(ב-Java מניחים, לפי ההנחיות, שבמחלקה מוגדר `Scanner in`.)

תשובה: הפעולה שלמעלה – הגרלה בטווח `[prev+1, 99-(num-1-k)]` לכל איבר.

שאלה 6 · מעקב: ספרה אחרונה מול ספרה ראשונה

א.

נתונה הפעולה what המקבלת שני מספרים שלמים וחיוביים:

Java:

public static boolean what(int n1, int n2)
{
  while (n2>9)
  {
    n2=n2/10;
  }
  if (n1%10 == n2)
    return true;
  return false;
}

C#:

public static bool What(int n1, int n2)
{
  while (n2 > 9)
  {
    n2 = n2/10;
  }
  if (n1%10 == n2)
    return true;
  return false;
}
(1)

עקוב בעזרת טבלת מעקב אחר ביצוע פעולה בעבור זימון what(183,39) וכתוב מה תחזיר הפעולה.

(2)

הגדר את טענת היציאה של הפעולה what (מה מבצעת הפעולה באופן כללי).

(5 נקודות)
ב.

נתון קטע של פעולה ראשית (main) המשתמש בפעולה what

Java:

int n1=in.nextInt();
boolean ok=true;
int n2, count=1;
while (ok == true)
{
  n2 = in.nextInt();
  count++;
  ok = what(n1, n2);
  n1 = n2;
}
System.out.println(count);

C#:

int n1=Int32.Parse(Console.ReadLine());

bool ok = true;
int n2, count = 1;
while (ok == true)
{
  n2= Int32.Parse(Console.ReadLine());
  count++;
  ok = What(n1, n2);
  n1 = n2;
}
Console.WriteLine(count);
(1)

עקוב בעזרת טבלת מעקב אחר ביצוע הקטע עבור הקלט הבא (משמאל לימין): 24,466,65,55,303 ורשום את הפלט.

אין צורך להראות מעקב אחר ביצוע הפעולה what.

(2)

תן דוגמה לקלט שעבורו יהיה הפלט ארבעה והערכים הנקלטים יהיו בני שלוש ספרות לפחות.

(5 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

(1)
תשובה:

n2 מתקצר מ-39 ל-3; 183%10=3183\%10=3 שווה ל-3, ולכן הפעולה מחזירה true.

נעקוב אחרי המשתנים: הלולאה מקצצת את n2 עד שנשארת ממנו ספרה אחת, ואז משווים את הספרה האחרונה של n1 ל-n2.

שלבn1n2n2>9n1%10n1%10 == n2פלט
התחלה18339true
אחרי סיבוב 11833false
אחרי הלולאה18333truetrue

1. 39>939>9, ולכן n2=39/10=3n2=39/10=3 (חילוק שלמים).

2. 3>93>9 שקר – יוצאים מהלולאה.

3. 183%10=3183\%10=3, ו-3==33==3, ולכן מוחזר true.

תשובה: הזימון `what(183,39)` מחזיר true.

(2)
תשובה:

הפעולה מחזירה true אם הספרה האחרונה (ספרת האחדות) של n1 שווה לספרה הראשונה (השמאלית) של n2, אחרת false.

1. הלולאה מחלקת את n2 ב-10 כל עוד יש בו יותר מספרה אחת, כלומר מסירה את הספרות מימין עד שנשארת רק הספרה השמאלית ביותר (הראשונה) של n2.

2. `n1 % 10` היא ספרת האחדות (הספרה האחרונה) של n1.

3. הפעולה משווה ביניהן.

תשובה: הפעולה מחזירה true אם הספרה האחרונה של n1 שווה לספרה הראשונה של n2, ואחרת false.

סעיף ב

(1)
תשובה:

יודפס 5.

הקטע קולט מספר ראשון, ואז קולט מספרים כל עוד כל מספר "מתחבר" לקודמו (הספרה האחרונה של הקודם = הספרה הראשונה של החדש). count סופר את כל המספרים שנקלטו, כולל המספר שבו השרשרת נשברה.

סיבובn1 (לפני)n2countwhat(n1, n2)okn1 (אחרי)
לפני הלולאה241true24
12446624 == 4 → truetrue466
24666536 == 6 → truetrue65
3655545 == 5 → truetrue55
45530355 ≠ 3 → falsefalse303

אחרי הסיבוב הרביעי ok הוא false והלולאה מסתיימת; מודפס count.

תשובה: הפלט הוא 5.

(2)
תשובה:

לדוגמה: 123, 345, 567, 999 (הפלט 4).

הרעיון: count מתחיל ב-1 וגדל עם כל מספר שנקלט בלולאה. כדי שיודפס 4 צריך לקלוט בלולאה 3 מספרים: שני הראשונים "מתחברים" לקודמם (what מחזירה true), והשלישי לא (what מחזירה false). בסך הכול 4 מספרים.

דוגמה: 123, 345, 567, 999

1. what(123, 345): הספרה האחרונה 3 = הספרה הראשונה 3 → true, count = 2.

2. what(345, 567): 5 = 5 → true, count = 3.

3. what(567, 999): 7 ≠ 9 → false, count = 4, והלולאה מסתיימת.

תשובה: הקלט 123, 345, 567, 999 – יודפס 4.

שאלה 7 · מחלקות עיר ומצב ארצי: שיטת הרמזור

עקב התפרצות מגפת הקורונה החליט משרד הבריאות להקים מערכת לטיפול שוטף במצב התחלואה במדינה.

א.

הוגדרה המחלקה עיר בקורונה CityK בעלת שתי תכונות:

•name – שם העיר מטיפוס מחרוזת.

•numOfResidents – מספר שלם המייצג את מספר התושבים בעיר.

•numOfPatients – מספר שלם המייצג את מספר החולים בעיר.

הנח כי קיימות פעולה בונה המקבלת את ערכי התכונות כפרמטרים, פעולות אחזור (get) וקביעה (set).

(1)

כתוב פעולה פנימית המקבלת עיר בקורונה, ומחזירה true אם לעיר הנוכחית ולעיר המתקבלת כפרמטר יש מספר חולים זהה, או false אם המספר שונה.

(2)

משרד הבריאות הגדיר את "שיטת הרמזור" שלפיה כל עיר מסומנת בצבע מסוים בהתאם לרמת התחלואה:

עיר ירוקה היא עיר שיש בה פחות מ- 5% חולים, עיר כתומה – 15%-5% חולים, ועיר אדומה – מעל 15% חולים.

כתוב פעולה פנימית המחזירה את קטגוריית העיר על-פי שיטת הרמזור. על הפעולה להחזיר אחת מהמחרוזות red/orange/green בהתאם למספרי התושבים והחולים.

שם הפעולה: `public String getCityColor()`

(5 נקודות)
ב.

הוגדרה המחלקה CountryStatus בעלת שלוש תכונות:

•date – תאריך עדכון המצב – מסוג מחרוזת.

•cities – מערך עצמים מסוג CityK. גודל המערך הוא 100.

•nCity – מספר שלם המייצג כמה ערים יש במערך.

Java:

public class CountryStatus
{
 private String date;
  private CityK  [] cities;
  private int nCity;
}

C#:

public class CountryStatus
{
 private string date;
  private CityK  [] cities;
  private int numOfCities ;
}
(1)

כתוב פעולה בונה במחלקה CountryStatus, המאתחלת מערך ערים ריק. הפעולה מקבלת תאריך עדכון כפרמטר.

(2)

כתוב פעולה פנימית בוליאנית בשם addCity המקבלת שם של עיר, מספר תושבים ואת מספר החולים בה, ומוסיפה עיר זו למערך ערים. הפעולה מחזירה true אם ההוספה הצליחה, או false אם הפעולה לא הצליחה.

אפשר להניח שהעיר עוד לא קיימת במערך ואין צורך לבדוק זאת.

(3)

כתוב פעולה פנימית המקבלת כפרמטר אחת מהמחרוזות red/orange/green ("צבע העיר" לפי שיטת הרמזור) ומחזירה מערך חדש הכולל שמות הערים לפי ה"צבע" המבוקש. עליך להיעזר בפעולה getCityColor שכתבת בסעיף א'.

(4)

משרד הבריאות מעוניין לבדוק אם חל שינוי במצב לאחר סגר כללי. כתוב פעולה חיצונית המקבלת שני עצמים cs1, cs2 מסוג CountryStatus ומדפיסה שמות של ערים שהיו בסטטוס "אדום" (red) ב- cs1 ואת הערים ששינו את הסטטוס ב- cs2.

הערה:

1. שים לב שמספר הערים וסדר הופעתן ב- cs1 ו- cs2 לא בהכרח זהים.

2. אפשר להניח שבשתי המחלקות קיימות פעולות get/set. אם השתמשת בפעולות נוספות, עליך לכתוב את הפעולות!

(7 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

(1)
תשובה:

samePatients(CityK other) מחזירה this.numOfPatients == other.getNumOfPatients().

הרעיון: הפעולה פנימית, ולכן מספר החולים של העיר הנוכחית זמין ישירות (`this.numOfPatients`), ואת זה של העיר שהתקבלה קוראים בפעולת האחזור. מחזירים את תוצאת ההשוואה.

Java:

public boolean samePatients(CityK other)
{
    return this.numOfPatients == other.getNumOfPatients();
}

C#:

public bool SamePatients(CityK other)
{
    return this.numOfPatients == other.GetNumOfPatients();
}

תשובה: `samePatients` מחזירה את תוצאת ההשוואה `this.numOfPatients == other.getNumOfPatients()`.

(2)
תשובה:

מחשבים percent = numOfPatients * 100.0 / numOfResidents; פחות מ-5 → green, עד 15 (כולל) → orange, מעל 15 → red.

הרעיון: מחשבים את אחוז החולים מתוך התושבים, ומשווים לגבולות של שיטת הרמזור.

1. אחוז החולים: percent=numOfPatients⋅100numOfResidents\text{percent}=\frac{numOfPatients\cdot 100}{numOfResidents}. כופלים ב-100.0 כדי שהחילוק יהיה ממשי (חילוק שלמים היה מקצץ, למשל 4.9% היה הופך ל-4).

2. אם percent<5\text{percent}<5 – "green".

3. אחרת, אם percent≤15\text{percent}\le 15 (כלומר בין 5% ל-15%, כולל הגבולות) – "orange".

4. אחרת (percent>15\text{percent}>15) – "red".

דוגמאות: 1000 תושבים ו-40 חולים: 4%4\% → green; 50 חולים: 5%5\% → orange; 150 חולים: 15%15\% → orange; 151 חולים: 15.1%15.1\% → red.

Java:

public String getCityColor()
{
    double percent = this.numOfPatients * 100.0 / this.numOfResidents;
    if (percent < 5)
        return "green";
    if (percent <= 15)
        return "orange";
    return "red";
}

C#:

public string GetCityColor()
{
    double percent = this.numOfPatients * 100.0 / this.numOfResidents;
    if (percent < 5)
        return "green";
    if (percent <= 15)
        return "orange";
    return "red";
}

תשובה: `getCityColor()` מחזירה "green" מתחת ל-5%, "orange" בין 5% ל-15%, ו-"red" מעל 15%.

סעיף ב

(1)
תשובה:

בנאי CountryStatus(String date): שומר את date, יוצר מערך CityK בגודל 100 ומאפס את nCity.

הרעיון: הבנאי שומר את התאריך שהתקבל, יוצר מערך חדש של 100 הפניות לערים (כולן null בהתחלה) ומאפס את מונה הערים – כך המערך "ריק".

Java:

public CountryStatus(String date)
{
    this.date = date;
    this.cities = new CityK[100];
    this.nCity = 0;
}

C#:

public CountryStatus(string date)
{
    this.date = date;
    this.cities = new CityK[100];
    this.numOfCities = 0;
}

תשובה: הבנאי שלמעלה.

(2)
תשובה:

אם nCity שווה לגודל המערך – false; אחרת יוצרים CityK חדש, שמים אותו ב-cities[nCity], מגדילים את nCity ומחזירים true.

הרעיון: הערים תופסות את התאים 0 עד `nCity-1`, ולכן התא הפנוי הבא הוא `nCity`. ההוספה נכשלת רק כשהמערך מלא.

1. אם `nCity == cities.length` (כבר 100 ערים) – אין מקום, מחזירים false.

2. אחרת יוצרים עצם CityK חדש מהנתונים בעזרת הבנאי, שמים אותו בתא `nCity`, ומגדילים את `nCity` ב-1.

3. מחזירים true.

Java:

public boolean addCity(String name, int numOfResidents, int numOfPatients)
{
    if (this.nCity == this.cities.length)            // המערך מלא
        return false;
    this.cities[this.nCity] = new CityK(name, numOfResidents, numOfPatients);
    this.nCity++;
    return true;
}

C#:

public bool AddCity(string name, int numOfResidents, int numOfPatients)
{
    if (this.numOfCities == this.cities.Length)      // המערך מלא
        return false;
    this.cities[this.numOfCities] = new CityK(name, numOfResidents, numOfPatients);
    this.numOfCities++;
    return true;
}

תשובה: הפעולה `addCity` שלמעלה.

(3)
תשובה:

שני מעברים: ספירת הערים שעבורן getCityColor() שווה לצבע, יצירת מערך מחרוזות בגודל זה, ומילויו בשמות הערים.

הרעיון: גודל מערך נקבע ביצירתו, ולא ידוע מראש כמה ערים בצבע המבוקש. לכן עוברים פעמיים על הערים:

1. מעבר ראשון: סופרים כמה ערים מחזירות `getCityColor()` ששווה לצבע שהתקבל.

2. יוצרים מערך מחרוזות בגודל המדויק הזה.

3. מעבר שני: עוברים שוב, ובכל פעם שהצבע מתאים כותבים את שם העיר בתא הבא (אינדקס k נפרד) של המערך החדש.

4. מחזירים את המערך (אם אין ערים בצבע – מוחזר מערך באורך 0).

ב-Java משווים מחרוזות עם `equals`; ב-C# עם `==`.

Java:

public String[] citiesByColor(String color)
{
    int count = 0;                                    // מעבר 1: כמה ערים בצבע
    for (int i = 0; i < this.nCity; i++)
        if (this.cities[i].getCityColor().equals(color))
            count++;

    String[] names = new String[count];               // מעבר 2: מילוי השמות
    int k = 0;
    for (int i = 0; i < this.nCity; i++)
    {
        if (this.cities[i].getCityColor().equals(color))
        {
            names[k] = this.cities[i].getName();
            k++;
        }
    }
    return names;
}

C#:

public string[] CitiesByColor(string color)
{
    int count = 0;                                    // מעבר 1: כמה ערים בצבע
    for (int i = 0; i < this.numOfCities; i++)
        if (this.cities[i].GetCityColor() == color)
            count++;

    string[] names = new string[count];               // מעבר 2: מילוי השמות
    int k = 0;
    for (int i = 0; i < this.numOfCities; i++)
    {
        if (this.cities[i].GetCityColor() == color)
        {
            names[k] = this.cities[i].GetName();
            k++;
        }
    }
    return names;
}

תשובה: הפעולה `citiesByColor` שלמעלה.

(4)
תשובה:

לוקחים מ-cs1 את מערך הערים האדומות (סעיף 3) ומדפיסים אותן; לכל אחת מחפשים לפי שם ב-cs2 (פעולת עזר findCity) ומדפיסים אותה אם שם צבעה אינו red.

הרעיון: מה שמעניין הן הערים שהיו אדומות ב-cs1. אותן נקבל מיד מהפעולה של סעיף 3. מכיוון שסדר הערים ומספרן ב-cs2 שונים, אי אפשר להשוות לפי מקום במערך – צריך לחפש כל עיר לפי שמה ב-cs2. לשם כך נוסיף ל-CountryStatus פעולת עזר `findCity` (כנדרש בהערה, היא כתובה במלואה).

1. `red1 = cs1.citiesByColor("red")` – שמות הערים האדומות ב-cs1. מדפיסים אותן.

2. לכל שם ב-red1 מחפשים ב-cs2 את העיר באותו שם (`findCity`, חיפוש סדרתי; מוחזר null אם העיר לא נמצאת).

3. אם העיר נמצאה וצבעה ב-cs2 (לפי `getCityColor`) אינו "red" – היא שינתה סטטוס, ומדפיסים את שמה ואת הצבע החדש. עיר שלא מופיעה ב-cs2 – אין עליה מידע, ולא מדפיסים אותה כמשנה סטטוס.

דוגמה: ב-cs1 העיר A עם 20% חולים והעיר E עם 15.1% (שתיהן אדומות); ב-cs2 ל-A יש 3% ול-E יש 30%. יודפסו A ו-E כערים האדומות, ותחת השינויים: `A -> green`.

Java:

// פעולה נוספת במחלקה CountryStatus: מחזירה את העיר ששמה name, או null
public CityK findCity(String name)
{
    for (int i = 0; i < this.nCity; i++)
        if (this.cities[i].getName().equals(name))
            return this.cities[i];
    return null;
}

// פעולה חיצונית
public static void printRedChanges(CountryStatus cs1, CountryStatus cs2)
{
    String[] red1 = cs1.citiesByColor("red");
    System.out.println("Red cities in cs1:");
    for (int i = 0; i < red1.length; i++)
        System.out.println(red1[i]);

    System.out.println("Changed status in cs2:");
    for (int i = 0; i < red1.length; i++)
    {
        CityK c = cs2.findCity(red1[i]);
        if (c != null && !c.getCityColor().equals("red"))
            System.out.println(red1[i] + " -> " + c.getCityColor());
    }
}

C#:

// פעולה נוספת במחלקה CountryStatus: מחזירה את העיר ששמה name, או null
public CityK FindCity(string name)
{
    for (int i = 0; i < this.numOfCities; i++)
        if (this.cities[i].GetName() == name)
            return this.cities[i];
    return null;
}

// פעולה חיצונית
public static void PrintRedChanges(CountryStatus cs1, CountryStatus cs2)
{
    string[] red1 = cs1.CitiesByColor("red");
    Console.WriteLine("Red cities in cs1:");
    for (int i = 0; i < red1.Length; i++)
        Console.WriteLine(red1[i]);

    Console.WriteLine("Changed status in cs2:");
    for (int i = 0; i < red1.Length; i++)
    {
        CityK c = cs2.FindCity(red1[i]);
        if (c != null && c.GetCityColor() != "red")
            Console.WriteLine(red1[i] + " -> " + c.GetCityColor());
    }
}

תשובה: הפעולה `printRedChanges` (עם פעולת העזר `findCity`) שלמעלה.

שאלה 8 · מציאת החציון במערך וסיבוכיות

נתונה פעולה what הבאה. הפעולה מקבלת מערך באורך אי-זוגי של מספרים שלמים. האיברים במערך שונים זה מזה.

Java:

public static int what(int[] arr) {
    int up, down;
    for (int i = 0; i < arr.length; i ++)
    {
        up = 0;
        down = 0;
        for (int j = 0; j < arr.length; j++)
        {
            if (arr[i] > arr[j])
                down++;
            if (arr[j] > arr[i])
                up++;
        }
        if (up == down)
            return arr[i];
    }
    return -1;
}

C#:

public static int What(int[] arr) {
    int up, down;
    for (int i = 0; i < arr.Length; i ++)
    {
        up = 0;
        down = 0;
        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[i] > arr[j])
                down++;
            if (arr[j] > arr[i])
                up++;
        }
        if (up==down)
            return arr[i];
    }
    return -1;
}
א.

מה תחזיר הפעולה בעבור המערך `int[] arr={5,2,10,6,12}`?

(4 נקודות)
ב.

מהי סיבוכיות זמן הריצה של הפעולה? הסבר את תשובתך.

(2 נקודות)
ג.

מה מבצעת הפעולה באופן כללי?

(2 נקודות)
ד.

נתון שהמערך arr ממוין. כתוב את הפעולה בצורה יעילה יותר (בסיבוכיות טובה יותר).

(2 נקודות)
ה.

מהי סיבוכיות זמן הריצה של הפעולה? הסבר את תשובתך.

(2 נקודות)
◂ פתרון מלא לשאלה 8

סעיף א

תשובה:

6

לכל איבר `arr[i]` הלולאה הפנימית סופרת: `down` – כמה איברים קטנים ממנו, `up` – כמה איברים גדולים ממנו. ברגע שהם שווים מוחזר האיבר.

מקום iarr[i]איברים קטנים ממנוdownאיברים גדולים ממנוupup == down
052110, 6, 123לא
12–05, 10, 6, 124לא
2105, 2, 63121לא
365, 2210, 122כן → return 6

תשובה: הפעולה מחזירה 6.

סעיף ב

תשובה:

O(n2)O(n^2)

נסמן ב-n את אורך המערך.

1. הלולאה החיצונית רצה עד n פעמים (ב-i).

2. בכל סיבוב שלה הלולאה הפנימית רצה בדיוק n פעמים, ובכל פעם מתבצעות 2 השוואות – פעולות בזמן קבוע.

3. במקרה הגרוע (החציון נמצא בסוף המערך) מתבצעים n⋅nn\cdot n סיבובים פנימיים.

החציון יכול להיות בכל מקום במערך; בממוצע הוא נמצא באמצע, ועדיין מתבצעים בערך n2⋅n\frac{n}{2}\cdot n סיבובים – אותו סדר גודל.

תשובה: O(n2)O(n^2) – לולאה כפולה, n סיבובים פנימיים לכל אחד מ-n הסיבובים החיצוניים.

סעיף ג

תשובה:

מחזירה את החציון – האיבר שמספר האיברים הקטנים ממנו שווה למספר האיברים הגדולים ממנו (האיבר האמצעי במערך הממוין).

הפעולה מחפשת איבר שמספר האיברים הקטנים ממנו (`down`) שווה למספר האיברים הגדולים ממנו (`up`). מכיוון שהאורך אי-זוגי והאיברים שונים, יש בדיוק איבר אחד כזה: מתוך n−1n-1 האיברים האחרים, n−12\frac{n-1}{2} קטנים ממנו ו-n−12\frac{n-1}{2} גדולים ממנו. זהו החציון – האיבר שהיה נמצא באמצע אילו המערך היה ממוין. (לכן במערך שעומד בתנאי השאלה `return -1` לא מתבצע לעולם.)

בדוגמה של סעיף א: המערך הממוין הוא 2, 5, 6, 10, 12, והאמצעי הוא 6.

תשובה: הפעולה מחזירה את החציון של המערך (האיבר האמצעי בסדר הגודל).

סעיף ד

תשובה:

return arr[arr.length / 2];

הרעיון: במערך ממוין באורך אי-זוגי n, החציון נמצא בדיוק באמצע – במקום n−12\frac{n-1}{2}, שהוא `n / 2` בחילוק שלמים. לפניו n−12\frac{n-1}{2} איברים (קטנים ממנו, אם המיון בסדר עולה) ואחריו אותו מספר איברים (גדולים ממנו). אם המערך ממוין בסדר יורד – זה עדיין אותו מקום, רק שהצדדים מתחלפים. לכן אין צורך בשום לולאה.

לדוגמה, עבור 2, 5, 6, 10, 12: n=5n=5, 5/2=25/2=2, ו-`arr[2]` = 6.

Java:

public static int what(int[] arr)
{
    return arr[arr.length / 2];
}

C#:

public static int What(int[] arr)
{
    return arr[arr.Length / 2];
}

תשובה: `return arr[arr.length / 2];`

סעיף ה

תשובה:

O(1)O(1)

הפעולה מסעיף ד מבצעת חישוב אינדקס אחד (`length / 2`) וגישה אחת לתא במערך. אין בה לולאה, ומספר הפעולות אינו תלוי באורך המערך.

תשובה: O(1)O(1) – זמן קבוע.

שאלה 9 · ספירת בלוקים באורך מינימלי במערך

הגדרה: בלוק במערך זה רצף תאים סמוכים שהערכים שלהם זהים.

לדוגמה: במערך arr הבא

32225661333312

יש שלושה בלוקים: {2,2,2} {6,6} {3,3,3,3}

כתוב פעולה המקבלת מערך של מספרים שלמים arr ומספר שלם וחיובי num ומחזירה את כמות הבלוקים במערך שאורכם לפחות num.

◂ פתרון מלא לשאלה 9

פתרון

תשובה:

עוברים על המערך רצף אחרי רצף, מודדים את אורך כל רצף של ערכים זהים, וסופרים רצפים שאורכם לפחות 2 (בלוק) וגם לפחות num. בדוגמה: עבור num=3 מוחזר 2.

הרעיון: מחלקים את המערך לרצפים מקסימליים של ערכים זהים. מתחילים במקום i, ומאריכים את הרצף כל עוד התא הבא שווה ל-`arr[i]`. כך מתקבל אורך הרצף `len`. לפי הדוגמה, תא בודד (כמו 5 או 1) אינו בלוק – בלוק הוא רצף של שני תאים לפחות. לכן סופרים רצף אם `len >= 2` וגם `len >= num`. אחר כך קופצים ישר לתחילת הרצף הבא (`i += len`), כך שכל תא נבדק פעם אחת – סיבוכיות O(n)O(n).

1. `count = 0`, `i = 0`.

2. כל עוד `i` בתוך המערך: `len = 1`, ומגדילים את `len` כל עוד `arr[i+len] == arr[i]` (ובודקים קודם שלא יצאנו מהמערך).

3. אם `len >= 2 && len >= num` – מגדילים את `count`. (הבדיקה `len >= 2` נחוצה רק עבור `num = 1`, כדי לא לספור תאים בודדים.)

4. `i = i + len`.

5. מחזירים `count`.

מעקב על הדוגמה (הרצפים לפי הסדר):

רצףערךlenבלוק?נספר עבור num=3?
מקום 031לאלא
מקומות 1-323כןכן
מקום 451לאלא
מקומות 5-662כןלא
מקום 711לאלא
מקומות 8-1134כןכן
מקום 1211לאלא
מקום 1321לאלא

עבור num=3 מוחזר 2; עבור num=2 (או 1) מוחזר 3; עבור num=4 מוחזר 1; עבור num=5 מוחזר 0.

Java:

public static int countBlocks(int[] arr, int num)
{
    int count = 0;
    int i = 0;
    while (i < arr.length)
    {
        int len = 1;                              // אורך הרצף שמתחיל ב-i
        while (i + len < arr.length && arr[i + len] == arr[i])
            len++;
        if (len >= 2 && len >= num)               // רצף של שני תאים לפחות הוא בלוק
            count++;
        i = i + len;                              // מדלגים לתחילת הרצף הבא
    }
    return count;
}

C#:

public static int CountBlocks(int[] arr, int num)
{
    int count = 0;
    int i = 0;
    while (i < arr.Length)
    {
        int len = 1;                              // אורך הרצף שמתחיל ב-i
        while (i + len < arr.Length && arr[i + len] == arr[i])
            len++;
        if (len >= 2 && len >= num)               // רצף של שני תאים לפחות הוא בלוק
            count++;
        i = i + len;                              // מדלגים לתחילת הרצף הבא
    }
    return count;
}

תשובה: הפעולה `countBlocks` שלמעלה; בדוגמה, עבור num=3 היא מחזירה 2.

שאלה 10 · משקל מספר ומערכים זהים לפי משקל

נתונות ההגדרות הבאות:

- "משקל" של מספר שלם הוא סכום הספרות של המספר.

לדוגמה:

המשקל של 123 הוא 6

המשקל של 345- הוא 12

המשקל של 8 הוא 8

•מערך של מספרים שלמים נקרא "מערך בלי חזרות משקל" אם ה"משקלים" של כל איברי המערך שונים זה מזה.

•שני מערכים של מספרים שלמים arr1 ו- arr2 נקראים "זהים לפי משקל" אם הם "מערכים בלי חזרות משקל" ולכל איבר ממערך arr1 יש איבר במערך arr2 בעל אותו "משקל".

א.

כתוב פעולה אשר מקבלת מספר שלם ומחזירה את ה"משקל" שלו.

(5 נקודות)
ב.

כתוב פעולה אשר מקבלת מערך חד-ממדי של מספרים שלמים ומחזירה true אם המערך הוא "מערך בלי חזרות משקל", ולא הפעולה תחזיר false.

(5 נקודות)
ג.

כתוב פעולה אשר מקבלת שני מערכים חד-ממדיים של מספרים שלמים. הפעולה מחזירה true אם המערכים "זהים לפי משקל", ולא הפעולה מחזירה false.

(5 נקודות)
ד.

מהן סיבוכיות זמן הריצה של הפעולות שכתבת בסעיפים ב' ו- ג'? הסבר את תשובתך.

(3 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

weight(n): הופכים n שלילי לחיובי, ומסכמים ספרות בעזרת n % 10 ו-n / 10 עד ש-n מתאפס.

הרעיון: סכום ספרות מחושב בפירוק המספר: הספרה הימנית היא `n % 10`, ואז מסירים אותה עם `n / 10`, עד שנשאר 0. לפי הדוגמה, המשקל של 345- הוא 12 – הסימן אינו משנה, ולכן קודם הופכים מספר שלילי לחיובי (אחרת ב-Java וב-C# השארית `n % 10` של מספר שלילי שלילית, והלולאה `while (n > 0)` לא הייתה רצה בכלל).

1. אם n<0n<0: n=−nn=-n.

2. `sum = 0`; כל עוד n>0n>0: `sum += n % 10`, `n = n / 10`.

3. מחזירים `sum`.

בדיקה: 123→3+2+1=6123\to 3+2+1=6; −345→345→5+4+3=12-345\to 345\to 5+4+3=12; 8→88\to 8. עבור 0 מוחזר 0.

Java:

public static int weight(int n)
{
    if (n < 0)
        n = -n;                 // הסימן אינו משפיע על הספרות
    int sum = 0;
    while (n > 0)
    {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}

C#:

public static int Weight(int n)
{
    if (n < 0)
        n = -n;                 // הסימן אינו משפיע על הספרות
    int sum = 0;
    while (n > 0)
    {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}

תשובה: הפעולה `weight` שלמעלה.

סעיף ב

תשובה:

לולאה כפולה על כל זוג i < j: אם weight(arr[i]) == weight(arr[j]) מחזירים false; בסוף true.

הרעיון: המערך "בלי חזרות משקל" אם אין שני איברים שונים (במקומות שונים) עם אותו משקל. בודקים כל זוג מקומות i<ji<j פעם אחת; ברגע שנמצא זוג עם משקל שווה – מחזירים false. אם לא נמצא אף זוג – true.

1. לולאה חיצונית על i מ-0 עד `length-2`, ולולאה פנימית על j מ-`i+1` עד `length-1` (כך כל זוג נבדק פעם אחת, ואיבר לא מושווה לעצמו).

2. אם `weight(arr[i]) == weight(arr[j])` – false.

3. אחרי הלולאות – true.

דוגמה: {123, 345-, 8} – משקלים 6, 12, 8, כולם שונים → true. {123, 51, 8} – המשקלים של 123 ו-51 הם 6 ו-6 → false.

Java:

public static boolean noRepeatWeight(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
        for (int j = i + 1; j < arr.length; j++)
            if (weight(arr[i]) == weight(arr[j]))
                return false;
    return true;
}

C#:

public static bool NoRepeatWeight(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
        for (int j = i + 1; j < arr.Length; j++)
            if (Weight(arr[i]) == Weight(arr[j]))
                return false;
    return true;
}

תשובה: הפעולה `noRepeatWeight` שלמעלה.

סעיף ג

תשובה:

אם אחד המערכים אינו בלי חזרות משקל – false; אחרת, לכל arr1[i] מחפשים ב-arr2 איבר באותו משקל, ואם לאיבר כלשהו אין כזה – false; אחרת true.

הרעיון: מממשים את ההגדרה בשני שלבים:

1. שני המערכים בלי חזרות משקל – בעזרת הפעולה מסעיף ב. אם אחד מהם לא – מחזירים false מיד.

2. לכל איבר של arr1 יש איבר ב-arr2 באותו משקל: לכל `arr1[i]` מחפשים חיפוש סדרתי ב-arr2 (הלולאה הפנימית נעצרת כשנמצא, בעזרת הדגל `found`). אם לאיבר כלשהו לא נמצא תואם – false.

3. אם כל האיברים מצאו תואם – true.

דוגמה: arr1 = {123, 345-, 8} (משקלים 6, 12, 8) ו-arr2 = {8-, 6, 1200, 39} (משקלים 8, 6, 3, 12): שני המערכים בלי חזרות, ולכל משקל של arr1 יש תואם ב-arr2 → true.

הערה: הפעולה מממשת את ההגדרה כלשונה – הדרישה היא רק בכיוון arr1 ← arr2. אילו רצינו התאמה הדדית, היה מספיק להוסיף בדיקה שאורכי המערכים שווים (כשאין חזרות משקל, התאמה בכיוון אחד ואורכים שווים מבטיחים התאמה מלאה).

Java:

public static boolean sameByWeight(int[] arr1, int[] arr2)
{
    if (!noRepeatWeight(arr1) || !noRepeatWeight(arr2))
        return false;
    for (int i = 0; i < arr1.length; i++)
    {
        boolean found = false;
        for (int j = 0; j < arr2.length && !found; j++)
            if (weight(arr1[i]) == weight(arr2[j]))
                found = true;
        if (!found)
            return false;       // לאיבר arr1[i] אין איבר באותו משקל
    }
    return true;
}

C#:

public static bool SameByWeight(int[] arr1, int[] arr2)
{
    if (!NoRepeatWeight(arr1) || !NoRepeatWeight(arr2))
        return false;
    for (int i = 0; i < arr1.Length; i++)
    {
        bool found = false;
        for (int j = 0; j < arr2.Length && !found; j++)
            if (Weight(arr1[i]) == Weight(arr2[j]))
                found = true;
        if (!found)
            return false;       // לאיבר arr1[i] אין איבר באותו משקל
    }
    return true;
}

תשובה: הפעולה `sameByWeight` שלמעלה.

סעיף ד

תשובה:

סעיף ב: O(n2)O(n^2); סעיף ג: O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m), ובאורכים דומים O(n2)O(n^2).

נסמן ב-n את אורך arr1 (או של המערך בסעיף ב) וב-m את אורך arr2. חישוב משקל (`weight`) לוקח זמן לפי מספר הספרות, ומספר הספרות של int חסום (לכל היותר 10), ולכן הוא O(1)O(1).

סעיף ב: לולאה כפולה על כל הזוגות i<ji<j. מספר ההשוואות במקרה הגרוע (אין חזרות):

(n−1)+(n−2)+⋯+1=n(n−1)2(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}

כל השוואה O(1)O(1), ולכן הסיבוכיות O(n2)O(n^2).

סעיף ג:

1. שתי הקריאות ל-`noRepeatWeight`: O(n2)+O(m2)O(n^2)+O(m^2).

2. הלולאה הכפולה: לכל אחד מ-n האיברים של arr1 חיפוש סדרתי ב-arr2 – במקרה הגרוע m השוואות, כלומר O(n⋅m)O(n\cdot m).

סך הכול O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m). אם אורכי המערכים מאותו סדר גודל (m≈nm\approx n) – O(n2)O(n^2).

תשובה: סעיף ב – O(n2)O(n^2); סעיף ג – O(n2+m2+n⋅m)O(n^2+m^2+n\cdot m), כלומר O(n2)O(n^2) כשהאורכים דומים.

שאלה 11 · מעקב רקורסיה: איבר אמצעי והשוואה לשאר

לפניך שתי פעולות:

Java:

public static double check(int[] a, int p, int q)
{
  if(p== q)return a[p];
  else
   if(p+1== q)
      return (double)(a[p]+a[q])/2;
   else
      return check(a, p+1,q-1);
}
public static boolean secret (int[] a, int p)
{
  if (p==a.length-1) return true;
  else
   return a[p] >check (a, p+1, a.length-1) && secret (a, p+1);
}

C#:

public static double Check(int[] a, int p, int q)
{
  if(p== q)return a[p];
  else
   if(p+1== q)
      return (double)(a[p]+a[q])/2;
   else
      return Check(a, p+1,q-1);
}
public static bool Secret (int[] a, int p)
{
  if (p==a.Length-1) return true;
  else
   return a[p] >Check (a, p+1, a.Length-1) && Secret (a, p+1);
}
א.

ערוך מעקב ורשום מה תחזיר הפעולה check(a,0,5) עבור מערך a הבא:

0123456
210123741
(6 נקודות)
ב.

ערוך מעקב ורשום מה מחזירה הפונקציה secret (a, 0) עבור המערך a:

01234
1710438
(6 נקודות)
ג.

תן דוגמה למערך b שיש בו לפחות שישה איברים כך שזימון secret(b,0) יחזיר "אמת".

(2 נקודות)
ד.

תן דוגמה למערך c שיש בו לפחות שישה איברים כך שזימון secret(c,0) יחזיר "שקר".

(2 נקודות)
ה.

מה מבצעת הפעולה secret, ומה מבצעת הפעולה check? הסבר בקצרה.

(2 נקודות)
◂ פתרון מלא לשאלה 11

סעיף א

תשובה:

7.5

הפעולה מצמצמת את הטווח [p,q][p,q] מצד ימין ומצד שמאל בבת אחת, עד שנשאר תא אחד (p=qp=q) או שני תאים סמוכים (p+1=qp+1=q).

זימוןpqp == q?p+1 == q?פעולהערך מוחזר
check(a,0,5)05לאלאcheck(a,1,4)7.5
check(a,1,4)14לאלאcheck(a,2,3)7.5
check(a,2,3)23לאכן(a[2]+a[3])/27.5

בזימון האחרון: a[2]+a[3]2=12+32=152=7.5\frac{a[2]+a[3]}{2}=\frac{12+3}{2}=\frac{15}{2}=7.5 (ההמרה ל-double לפני החילוק שומרת על השבר). הערך חוזר כמו שהוא דרך כל הזימונים.

תשובה: `check(a,0,5)` מחזירה 7.5.

סעיף ב

תשובה:

false

באורך 5, `a.length-1` = 4. בכל זימון `secret(a,p)` (עם p<4p<4) משווים את `a[p]` לערך `check(a, p+1, 4)`, ורק אם ההשוואה אמת ממשיכים ל-`secret(a, p+1)` (הערכה מקוצרת של `&&`).

חישובי check הדרושים:

•check(a,1,4) → check(a,2,3) → 4+32=3.5\frac{4+3}{2}=3.5

•check(a,2,4) → check(a,3,3) → a[3] = 3, כלומר 3.0

•check(a,3,4) → 3+82=5.5\frac{3+8}{2}=5.5

זימוןpa[p]check(a, p+1, 4)a[p] > checkהמשךערך מוחזר
secret(a,0)0173.5truesecret(a,1)false
secret(a,1)1103.0truesecret(a,2)false
secret(a,2)245.5false– (secret(a,3) לא מזומנת)false

ב-secret(a,2): 4>5.54>5.5 שקר, ולכן מוחזר false בלי לזמן את secret(a,3). ה-false חוזר דרך secret(a,1) ו-secret(a,0) (כי `true && false` הוא false).

תשובה: `secret(a,0)` מחזירה false.

סעיף ג

תשובה:

לדוגמה b = {60, 50, 40, 30, 20, 10}.

הרעיון: `secret` מחזירה אמת אם כל איבר (חוץ מהאחרון) גדול מהערך האמצעי של כל האיברים שאחריו. במערך יורד ממש כל איבר גדול מכל האיברים שאחריו, ובפרט מהאמצעי שלהם.

b = {60, 50, 40, 30, 20, 10} (אורך 6, `length-1` = 5):

pb[p]check(b, p+1, 5)b[p] > check
060b[3] = 30true
150(30+20)/2 = 25true
240b[4] = 20true
330(20+10)/2 = 15true
420b[5] = 10true
5––p == length-1 → true

תשובה: b = {60, 50, 40, 30, 20, 10} – הזימון `secret(b,0)` מחזיר אמת.

סעיף ד

תשובה:

לדוגמה c = {1, 2, 3, 4, 5, 6}.

מספיק שהאיבר הראשון לא יהיה גדול מהערך האמצעי של שאר האיברים.

c = {1, 2, 3, 4, 5, 6}: בזימון secret(c,0) מחשבים check(c,1,5) → check(c,2,4) → check(c,3,3) = c[3] = 4. ההשוואה 1>41>4 שקרית, ולכן מוחזר שקר מיד.

תשובה: c = {1, 2, 3, 4, 5, 6} – הזימון `secret(c,0)` מחזיר שקר.

סעיף ה

תשובה:

check(a,p,q) מחזירה את הערך האמצעי של קטע המערך a[p..q] (האיבר האמצעי, או ממוצע שני האמצעיים כשמספר האיברים זוגי). secret(a,p) מחזירה true אם כל איבר מהמקום p ועד הלפני-אחרון גדול מהערך האמצעי של קטע האיברים שאחריו.

check(a, p, q): בכל זימון מקדמים את p ומורידים את q ב-1, כלומר "מקלפים" איבר מכל קצה של הקטע `a[p..q]`, עד שמגיעים לאמצע. אם מספר האיברים בקטע אי-זוגי – מוחזר האיבר האמצעי (`p == q`); אם זוגי – מוחזר הממוצע של שני האיברים האמצעיים (`p+1 == q`). כלומר, check מחזירה את הערך שבאמצע הקטע לפי מיקום (לא לפי גודל – המערך לא ממוין).

secret(a, p): עוברת ברקורסיה על המקומות p, p+1, ..., עד הלפני-אחרון, ולכל מקום i בודקת אם `a[i]` גדול מהערך ש-check מחזירה עבור הקטע שאחריו, `a[i+1..length-1]`. היא מחזירה true רק אם התנאי מתקיים לכל המקומות (בהגעה לאיבר האחרון מוחזר true), ו-false ברגע שמקום אחד נכשל.

תשובה: check מחזירה את הערך האמצעי (או ממוצע שני האמצעיים) של הקטע `a[p..q]`; secret בודקת שכל איבר, מ-p עד הלפני-אחרון, גדול מהערך האמצעי של האיברים שאחריו.

שאלה 12 · מחלקות תאריך, מוצר מזון ומלאי

בעלי חנות מזון רוצים למחשב את מלאי המצרכים שברשותם.

לצורך כך הוגדרו שלוש מחלקות:

•המחלקה Date שתייצג תאריך.

•המחלקה FoodItem שתייצג מוצר מזון.

•המחלקה Stock שתייצג את המלאי בחנות המזון.

א.

למחלקה Date יש את התכונות הפרטיות הבאות:

•int day – שמייצגת את היום (שלמים בין 1 ל- 31);

•int month – שמייצגת את החודש (שלמים בין 1 ל- 12);

•int year – שמייצגת את השנה (שלמים חיוביים בני ארבע ספרות)

למחלקה הוגדרו פעולה הבונה (בנאי, constructor), פעולות get/set והפעולה toString.

(1)

כתוב פעולה equals המקבלת כפרמטר תאריך מסוים ובודקת אם עצם שמתקבל כפרמטר זהה לתאריך נוכחי (התאריך שמיוצג על ידי האובייקט עליו מופעלת הפעולה).

(2)

כתוב פעולה before המקבלת כפרמטר תאריך מסוים ובודקת אם התאריך הנוכחי (התאריך שמיוצג באמצעות האובייקט שעליו מופעלת הפעולה), קודם לתאריך שהתקבל כפרמטר.

(3 נקודות)
ב.

בחנות יש מוצרי מזון שונים.

הוגדרה מחלקה בשם FoodItem המייצגת מוצר מזון.

למחלקה FoodItem יש את התכונות הפרטיות הבאות:

•שם המוצר (name) מטיפוס String;

•כמות המוצר במלאי (quantity) מטיפוס int;

•תאריך הייצור של המוצר (productionDate);

•תאריך התפוגה של המוצר (expiryDate);

•הטמפרטורה המינימלית שבה המוצר יכול להתקיים (minTemperature) מטיפוס int;

•הטמפרטורה המקסימלית שבה המוצר יכול להתקיים (maxTemperature) מטיפוס int;

•מחיר המוצר (price) מטיפוס double.

למחלקה הוגדרו פעולה הבונה (constructor), פעולות get/set והפעולה toString.

(1)

כתוב פעולה הבוליאנית isFresh המקבלת תאריך מסוים d כפרמטר, ומחזירה true אם בתאריך הזה המוצר טרי (כלומר, נמצא לאחר תאריך הייצור שלו ולפני תאריך התפוגה שלו, כולל). אם לא, הפעולה מחזירה false.

(2)

כתוב פעולה howManyItems המקבלת מספר שלם שמייצג סכום של כסף, ומחזירה כמה פריטים של המוצר אפשר לקנות בסכום זה.

הערה:

יש לשים לב אם קיימת כמות מספיקה של פריטים במלאי.

לדוגמה:

אם מחירו של המוצר הוא שני שקלים ויש במלאי ארבעה פריטים, והסכום שמתקבל כפרמטר לפעולה הוא עשרה אפשר אומנם לקנות בסכום זה חמישה פריטים, אבל מכיוון שיש רק ארבעה פריטים במלאי, השיטה תחזיר את הערך ארבע.

(5 נקודות)
ג.

המחלקה Stock מייצגת את המלאי בחנות.

הייצוג נעשה באמצעות מערך ששומר את מוצרי המזון. התכונות במחלקה הן:

•מערך של המוצרים: `FoodItem [] stock`

•מספר המוצרים שיש בחנות: `int numOfItems`

אפשר להניח שאין יותר מ- 100 מוצרים שונים.

(1)

כתוב בנאי ברירת-מחדל (default constructor) של המחלקה היוצר אובייקט שבו מערך בגודל המקסימלי של 100 מוצרי מזון. בהתחלה המערך ריק ומספר המוצרים שבו שווה ל- 0.

(2)

כתוב פעולה howMany המקבלת מספר שלם temp שהוא הטמפרטורה שיש במקרר מסוים, ומחזירה את מספר המוצרים שאפשר לאחסן במקרר זה (כלומר, שהטמפרטורה של המקרר מתאימה לאחסון שלהם).

שימו לב, אם במלאי יש 5 יוגורטים שניתן להעביר למקרר, אז צריך לספור אותם כחמישה (5) ולא כמוצר אחד (יוגורט). אם המערך ריק יש להחזיר 0.

(3)

כתוב פעולה removeAfterDate המקבלת כפרמטר תאריך d ומוחקת מהמלאי את כל מוצרי המזון שתאריך התפוגה שלהם הוא לפני התאריך d (כלומר, את כל המוצרים שהם מקולקלים בתאריך d, כי תאריך התפוגה שלהם כבר עבר).

(10 נקודות)
◂ פתרון מלא לשאלה 12

סעיף א

(1)
תשובה:

equals(Date other) מחזירה true אם day, month ו-year של שני התאריכים שווים.

הרעיון: שני תאריכים זהים אם היום, החודש והשנה שלהם שווים. מחזירים את הגימום (וגם) של שלוש ההשוואות.

Java:

public boolean equals(Date other)
{
    return this.day == other.getDay() && this.month == other.getMonth()
            && this.year == other.getYear();
}

C#:

public bool Equals(Date other)
{
    return this.day == other.GetDay() && this.month == other.GetMonth()
            && this.year == other.GetYear();
}

(הפעולה מקבלת פרמטר מטיפוס Date, ולכן היא העמסה של `equals`/`Equals` שקיימת ב-Object, ואינה דורסת אותה.)

תשובה: `equals` מחזירה true רק אם `day`, `month` ו-`year` שווים.

(2)
תשובה:

משווים לפי סדר עדיפות: שנה, אחר כך חודש, אחר כך יום; מחזירים true אם התאריך הנוכחי קטן ממש.

הרעיון: השוואת תאריכים היא "מילונית": קודם השנה; רק אם השנים שוות – החודש; רק אם גם החודשים שווים – היום.

1. אם השנים שונות – התשובה היא `this.year < other.year`.

2. אחרת, אם החודשים שונים – `this.month < other.month`.

3. אחרת – `this.day < other.day`. (אם גם הימים שווים, התאריכים זהים ומוחזר false – תאריך אינו קודם לעצמו.)

דוגמאות: 31/12/2020 קודם ל-10/5/2021 (השנה קטנה, למרות שהחודש והיום גדולים); 10/5/2021 קודם ל-9/6/2021 (אותה שנה, החודש קטן).

Java:

public boolean before(Date other)
{
    if (this.year != other.getYear())
        return this.year < other.getYear();
    if (this.month != other.getMonth())
        return this.month < other.getMonth();
    return this.day < other.getDay();
}

C#:

public bool Before(Date other)
{
    if (this.year != other.GetYear())
        return this.year < other.GetYear();
    if (this.month != other.GetMonth())
        return this.month < other.GetMonth();
    return this.day < other.GetDay();
}

תשובה: `before` משווה שנה, אחר כך חודש, אחר כך יום, ומחזירה true אם התאריך הנוכחי מוקדם ממש.

סעיף ב

(1)
תשובה:

מחזירים true אם d אינו לפני תאריך הייצור וגם תאריך התפוגה אינו לפני d: !d.before(productionDate) && !expiryDate.before(d).

הרעיון: המוצר טרי בתאריך d אם productionDate≤d≤expiryDateproductionDate\le d\le expiryDate, כולל הגבולות. בעזרת הפעולה `before` מסעיף א:

1. "d לא מוקדם מתאריך הייצור", כלומר d≥productionDated\ge productionDate: `!d.before(productionDate)`.

2. "תאריך התפוגה לא מוקדם מ-d", כלומר d≤expiryDated\le expiryDate: `!expiryDate.before(d)`.

3. שני התנאים יחד (וגם).

השלילה של `before` נותנת "אחרי או שווה", ולכן הגבולות כלולים. לדוגמה, יוגורט שיוצר ב-1/5/2021 ותוקפו עד 20/5/2021: טרי ב-1/5, ב-10/5 וב-20/5, אבל לא ב-21/5 ולא ב-30/4.

Java:

public boolean isFresh(Date d)
{
    // טרי: תאריך הייצור <= d <= תאריך התפוגה
    return !d.before(this.productionDate) && !this.expiryDate.before(d);
}

C#:

public bool IsFresh(Date d)
{
    // טרי: תאריך הייצור <= d <= תאריך התפוגה
    return !d.Before(this.productionDate) && !this.expiryDate.Before(d);
}

תשובה: `isFresh(d)` מחזירה `!d.before(productionDate) && !expiryDate.before(d)`.

(2)
תשובה:

canBuy = (int)(money / price); מחזירים את הקטן מבין canBuy ו-quantity.

הרעיון: מספר הפריטים שאפשר לממן הוא החלק השלם של moneyprice\frac{money}{price} (אי אפשר לקנות חצי פריט). אבל אי אפשר לקנות יותר ממה שיש במלאי, ולכן התשובה היא המינימום בין שני המספרים.

1. `canBuy = (int)(money / price)` – החילוק ממשי (price הוא double), וההמרה ל-int מקצצת את השבר.

2. אם `canBuy > quantity` – מחזירים `quantity`, אחרת `canBuy`.

בדיקה עם הדוגמה: מחיר 2, מלאי 4, סכום 10: 102=5>4\frac{10}{2}=5>4, ולכן מוחזר 4. עם סכום 7: 72=3.5→3≤4\frac{7}{2}=3.5\to 3\le 4, מוחזר 3.

Java:

public int howManyItems(int money)
{
    int canBuy = (int) (money / this.price);    // כמה אפשר לממן
    if (canBuy > this.quantity)                 // אבל לא יותר ממה שיש במלאי
        return this.quantity;
    return canBuy;
}

C#:

public int HowManyItems(int money)
{
    int canBuy = (int) (money / this.price);    // כמה אפשר לממן
    if (canBuy > this.quantity)                 // אבל לא יותר ממה שיש במלאי
        return this.quantity;
    return canBuy;
}

תשובה: `howManyItems` מחזירה את המינימום בין `(int)(money / price)` לבין `quantity`.

סעיף ג

(1)
תשובה:

public Stock() { stock = new FoodItem[100]; numOfItems = 0; }

הרעיון: בנאי ברירת מחדל אינו מקבל פרמטרים. הוא יוצר מערך של 100 הפניות ל-FoodItem (כולן null – המערך ריק) ומאפס את מספר המוצרים.

Java:

public Stock()
{
    this.stock = new FoodItem[100];
    this.numOfItems = 0;
}

C#:

public Stock()
{
    this.stock = new FoodItem[100];
    this.numOfItems = 0;
}

תשובה: הבנאי שלמעלה.

(2)
תשובה:

סוכמים את quantity של כל המוצרים שעבורם minTemperature <= temp <= maxTemperature; במערך ריק מוחזר 0.

הרעיון: מוצר מתאים למקרר אם הטמפרטורה של המקרר נמצאת בטווח שבו המוצר יכול להתקיים: minTemperature≤temp≤maxTemperatureminTemperature\le temp\le maxTemperature. לפי ההבהרה סופרים יחידות, ולכן לכל מוצר מתאים מוסיפים את הכמות שלו במלאי (`quantity`), ולא 1.

1. `count = 0`.

2. לולאה על המוצרים 0 עד `numOfItems-1`; אם הטמפרטורה בטווח של המוצר – `count += quantity`.

3. מחזירים `count`. אם המערך ריק (`numOfItems == 0`) הלולאה לא רצה, ומוחזר 0 – כנדרש.

דוגמה: 5 יוגורטים (2 עד 6 מעלות), 4 שקיות אורז (5 עד 30), 3 קרטוני חלב (1 עד 4). עבור temp=4temp=4: יוגורט וחלב מתאימים → 5+3=85+3=8. עבור temp=5temp=5: יוגורט ואורז → 5+4=95+4=9.

Java:

public int howMany(int temp)
{
    int count = 0;
    for (int i = 0; i < this.numOfItems; i++)
    {
        if (this.stock[i].getMinTemperature() <= temp
                && temp <= this.stock[i].getMaxTemperature())
            count += this.stock[i].getQuantity();    // כל היחידות של המוצר
    }
    return count;
}

C#:

public int HowMany(int temp)
{
    int count = 0;
    for (int i = 0; i < this.numOfItems; i++)
    {
        if (this.stock[i].GetMinTemperature() <= temp
                && temp <= this.stock[i].GetMaxTemperature())
            count += this.stock[i].GetQuantity();    // כל היחידות של המוצר
    }
    return count;
}

תשובה: `howMany(temp)` מחזירה את סכום הכמויות של המוצרים ש-temp בטווח הטמפרטורות שלהם.

(3)
תשובה:

מעבר אחד עם אינדקס כתיבה k: מוצר שתאריך התפוגה שלו אינו לפני d מועתק ל-stock[k] ו-k גדל; בסוף מאפסים את התאים שמ-k ואילך ו-numOfItems = k.

הרעיון: מוחקים מוצר אם `expiryDate.before(d)` (פג תוקפו לפני d). כדי שהמוצרים שנשארים יישארו רצופים בתחילת המערך (בתאים 0 עד `numOfItems-1`), "מכווצים" את המערך במעבר אחד:

1. משתנה `k` = המקום הבא שבו נשמור מוצר שנשאר; בהתחלה 0.

2. עוברים על המוצרים לפי הסדר. מוצר שאינו פג תוקף מעתיקים ל-`stock[k]` ומגדילים את `k`. מוצר שפג תוקפו פשוט מדלגים עליו (הוא לא מועתק – נמחק).

3. אחרי הלולאה, k הוא מספר המוצרים שנשארו. מאפסים (null) את התאים שמ-k עד `numOfItems-1`, שכבר אינם בשימוש, ומעדכנים `numOfItems = k`.

כך סדר המוצרים שנשארו נשמר, וכל מוצר נבדק פעם אחת – O(n)O(n). (מחיקה בהזזת כל המוצרים שאחרי כל מוצר שנמחק הייתה עובדת גם היא, אבל ב-O(n2)O(n^2), וצריך להיזהר לא לדלג על המוצר שהוזז למקום הנמחק.)

דוגמה: המלאי יוגורט (תוקף 20/5/2021), אורז (1/1/2023), חלב (15/5/2021), ו-d = 16/5/2021. החלב פג תוקף (15/5 לפני 16/5) ונמחק; נשארים יוגורט ואורז, ו-`numOfItems` = 2.

Java:

public void removeAfterDate(Date d)
{
    int k = 0;                                   // המקום הבא למוצר שנשאר
    for (int i = 0; i < this.numOfItems; i++)
    {
        if (!this.stock[i].getExpiryDate().before(d))   // לא פג תוקף – נשאר
        {
            this.stock[k] = this.stock[i];
            k++;
        }
    }
    for (int i = k; i < this.numOfItems; i++)    // ניקוי התאים שהתפנו
        this.stock[i] = null;
    this.numOfItems = k;
}

C#:

public void RemoveAfterDate(Date d)
{
    int k = 0;                                   // המקום הבא למוצר שנשאר
    for (int i = 0; i < this.numOfItems; i++)
    {
        if (!this.stock[i].GetExpiryDate().Before(d))   // לא פג תוקף – נשאר
        {
            this.stock[k] = this.stock[i];
            k++;
        }
    }
    for (int i = k; i < this.numOfItems; i++)    // ניקוי התאים שהתפנו
        this.stock[i] = null;
    this.numOfItems = k;
}

תשובה: הפעולה `removeAfterDate` שלמעלה.

שאלה 13 · רקורסיה על מחרוזות: בדיקת תת-סדרה

Java:

public static boolean what (String s1, String s2)
{
  if(s1.length()==0)
     return true;
  if(s2.length() == 0)
     return false;
  if(s1.charAt(0)==s2.charAt(0))
     return what(s1.substring(1),s2.substring(1));
  return what(s1,s2.substring(1));
}

C#:

public static bool What (string s1, string s2)
{
  if(s1.Length == 0)
     return true;
  if(s2.Length == 0)
     return false;
  if(s1[0] == s2[0])
     return What(s1.Substring(1),s2.Substring(1));
  return What(s1, s2.Substring(1));
}
א.

עקוב אחרי זימון הפעולה what(s1, s2) עבור s1="HELLO", s2= "HERLOLOR" ורשום מה תהיה תוצאת הזימון.

(6 נקודות)
ב.

תן דוגמה למחרוזת s3 כך שתוצאת הזימון what("HELLO", s3) תהיה שונה מהתוצאה של סעיף א'.

(3 נקודות)
ג.

מה מבצעת הפעולה what באופן כללי?

(3 נקודות)
ד.

כתוב את הפעולה what המבצעת אותה משימה באופן לא רקורסיבי.

(6 נקודות)
◂ פתרון מלא לשאלה 13

סעיף א

תשובה:

true

בכל זימון: אם s1 ריקה – true; אם s2 ריקה – false; אם התווים הראשונים שווים – מקצצים תו משתי המחרוזות; אחרת – מקצצים תו רק מ-s2.

זימוןs1s2s1[0] מול s2[0]הזימון הבא
1"HELLO""HERLOLOR"H = Hwhat("ELLO", "ERLOLOR")
2"ELLO""ERLOLOR"E = Ewhat("LLO", "RLOLOR")
3"LLO""RLOLOR"L ≠ Rwhat("LLO", "LOLOR")
4"LLO""LOLOR"L = Lwhat("LO", "OLOR")
5"LO""OLOR"L ≠ Owhat("LO", "LOR")
6"LO""LOR"L = Lwhat("O", "OR")
7"O""OR"O = Owhat("", "R")
8"""R"s1 ריקהמחזיר true

הערך true חוזר כמו שהוא דרך כל הזימונים.

תשובה: תוצאת הזימון היא true.

סעיף ב

תשובה:

s3 = "HELO" (מחזיר false).

בסעיף א התקבל true, ולכן צריך s3 שעבורה יוחזר false – כלומר שאי אפשר למצוא בה את התווים H, E, L, L, O לפי הסדר.

s3 = "HELO" (יש בה רק L אחת):

1. what("HELLO", "HELO"): H = H → what("ELLO", "ELO")

2. E = E → what("LLO", "LO")

3. L = L → what("LO", "O")

4. L ≠ O → what("LO", "")

5. s2 ריקה ו-s1 לא → false.

תשובה: s3 = "HELO" – הזימון מחזיר false.

סעיף ג

תשובה:

מחזירה true אם s1 היא תת-סדרה של s2 – כל תווי s1 מופיעים ב-s2 באותו סדר (לא בהכרח ברצף); אחרת false.

הפעולה מחפשת את תווי s1 בתוך s2 לפי הסדר: כשהתו הראשון של s1 נמצא בתחילת s2 – "מסמנים" אותו ועוברים לתו הבא של s1; אחרת מדלגים על תו של s2. אם כל תווי s1 נמצאו (s1 התרוקנה) – true; אם s2 נגמרה לפני כן – false.

תשובה: הפעולה מחזירה true אם ניתן לקבל את s1 מ-s2 על ידי מחיקת תווים מ-s2 (כלומר, כל תווי s1 מופיעים ב-s2 באותו סדר, לא בהכרח צמודים), ו-false אחרת. מחרוזת ריקה s1 מחזירה תמיד true.

סעיף ד

תשובה:

שני מצביעים: i על s1 ו-j על s2; עוברים על s2, וכל פעם ש-s1[i] == s2[j] מקדמים את i; מחזירים i == s1.length().

הרעיון: במקום לקצץ מחרוזות, מחזיקים שני אינדקסים: `i` – התו של s1 שמחפשים עכשיו, ו-`j` – התו הנוכחי של s2. זו בדיוק הרקורסיה "פרוסה" ללולאה:

•התווים שווים (`s1[i] == s2[j]`) – מתקדמים בשתיהן (`i++` ו-`j++`), כמו `what(s1.substring(1), s2.substring(1))`.

•אחרת – מתקדמים רק ב-s2 (`j++`), כמו `what(s1, s2.substring(1))`.

•הלולאה נעצרת כש-s1 נגמרה (`i == s1.length()`, המקביל ל-"s1 ריקה → true") או כש-s2 נגמרה (המקביל ל-"s2 ריקה → false").

בסוף, התשובה היא true אם ורק אם נמצאו כל תווי s1, כלומר `i == s1.length()`. סיבוכיות: O(m)O(m), כאשר m אורך s2 (כל תו של s2 נבדק פעם אחת).

בדיקה עם סעיף א: עבור "HELLO" ו-"HERLOLOR", i מתקדם על התווים H(0), E(1), L(3), L(5), O(6) של s2 ומגיע ל-5 → true. עבור "HELO" (סעיף ב) i נעצר ב-4 → false.

Java:

public static boolean what(String s1, String s2)
{
    int i = 0;                                  // התו הבא שמחפשים ב-s1
    for (int j = 0; j < s2.length() && i < s1.length(); j++)
    {
        if (s1.charAt(i) == s2.charAt(j))
            i++;                                // נמצא – עוברים לתו הבא של s1
    }
    return i == s1.length();                    // נמצאו כל תווי s1 לפי הסדר
}

C#:

public static bool What(string s1, string s2)
{
    int i = 0;                                  // התו הבא שמחפשים ב-s1
    for (int j = 0; j < s2.Length && i < s1.Length; j++)
    {
        if (s1[i] == s2[j])
            i++;                                // נמצא – עוברים לתו הבא של s1
    }
    return i == s1.Length;                      // נמצאו כל תווי s1 לפי הסדר
}

תשובה: הפעולה האיטרטיבית שלמעלה.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.