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

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

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

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

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

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

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

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

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

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

חלק א' – 48 נקודות

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

חלק ב' – 30 נקודות

שאלות 8–11: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 15 נקודות.

חלק ג' – 22 נקודות

שאלות 12–14: יש לענות על שתי שאלות בלבד. ערך כל שאלה – 11 נקודות.

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

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

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

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

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

כתבו קטע תוכנית הקולטת מספרים שלמים. הקלט יסתיים כאשר סכום המספרים שנקלטו יעלה על 100 או כאשר ייקלטו יותר מ-15 מספרים.

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

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

פתרון

תשובה:

לולאת while שממשיכה כל עוד sum <= 100 וגם count <= 15; בכל סיבוב קולטים מספר, מוסיפים לסכום, מגדילים את המונה וסופרים חיוביים; בסוף מדפיסים sum/count (כממשי) ואת מספר החיוביים.

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

•`sum` – צובר את סכום המספרים (נחוץ גם לתנאי העצירה וגם לממוצע);

•`count` – מונה את המספרים שנקלטו (נחוץ לתנאי העצירה ולממוצע);

•`positives` – מונה את המספרים החיוביים (גדולים מ-0).

1. תנאי ההמשך הוא ההפך של תנאי העצירה. הקלט מסתיים כאשר sum>100sum>100 או count>15count>15, ולכן ממשיכים לקלוט כל עוד sum≤100sum\le 100 וגם count≤15count\le 15.

2. בכל סיבוב: קולטים מספר, מוסיפים אותו ל-`sum`, מגדילים את `count`, ואם המספר חיובי – מגדילים את `positives`.

3. אחרי הלולאה מחשבים את הממוצע sumcount\frac{sum}{count}. מבצעים המרה ל-`double` לפני החילוק, אחרת מתבצע חילוק שלמים והחלק העשרוני הולך לאיבוד. אין חשש לחילוק ב-0: הלולאה מתבצעת לפחות פעם אחת, כי בהתחלה sum=0sum=0 ו-count=0count=0.

4. הנוסח "יותר מ-15 מספרים" מתפרש כלשונו: אחרי שנקלט המספר ה-16 הקלט נעצר. אם הכוונה היא לכל היותר 15 מספרים, מחליפים את התנאי ל-`count < 15`.

דוגמה: קלט 50, 60 – אחרי 50 הסכום 50 (ממשיכים), אחרי 60 הסכום 110 > 100 ועוצרים. הממוצע 1102=55\frac{110}{2}=55, ויש 2 מספרים חיוביים.

Java:

Scanner in = new Scanner(System.in);
int sum = 0;          // סכום המספרים שנקלטו
int count = 0;        // כמות המספרים שנקלטו
int positives = 0;    // כמות המספרים החיוביים
while (sum <= 100 && count <= 15)
{
    int num = in.nextInt();
    sum += num;
    count++;
    if (num > 0)
        positives++;
}
double avg = (double) sum / count;
System.out.println("Average: " + avg);
System.out.println("Positive numbers: " + positives);

C#:

int sum = 0;          // סכום המספרים שנקלטו
int count = 0;        // כמות המספרים שנקלטו
int positives = 0;    // כמות המספרים החיוביים
while (sum <= 100 && count <= 15)
{
    int num = int.Parse(Console.ReadLine());
    sum += num;
    count++;
    if (num > 0)
        positives++;
}
double avg = (double) sum / count;
Console.WriteLine("Average: " + avg);
Console.WriteLine("Positive numbers: " + positives);

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

שאלה 2 · מחרוזת ארוכה וקצרה ומחרוזות באות גדולה

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

כמו כן, יש למנות ולהדפיס את כמות המחרוזות אשר מתחילות או מסתיימות באות גדולה ('A'..'Z').

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

פתרון

תשובה:

קולטים את המחרוזת הראשונה כארוכה וכקצרה; עבור כל אחת מ-29 הבאות מעדכנים longest/shortest לפי האורך; מונים מחרוזת אם התו הראשון או האחרון בין 'A' ל-'Z'; מדפיסים את שלושת הנתונים.

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

1. אתחול: את המחרוזת הראשונה קולטים לפני הלולאה, והיא משמשת ערך התחלתי גם ל-`longest` וגם ל-`shortest` (כך אין צורך לנחש אורך התחלתי). בודקים גם אותה לגבי האות הגדולה.

2. לולאה על 29 המחרוזות הנותרות (מהשנייה עד השלושים): אם אורך המחרוזת החדשה גדול מאורך `longest` – היא הארוכה החדשה; אם קטן מאורך `shortest` – היא הקצרה החדשה. כשיש כמה מחרוזות באותו אורך, נשמרת הראשונה מביניהן (השוואה חזקה `>` / `<`).

3. אות גדולה: פעולת העזר `isCapital` בודקת אם התו נמצא בטווח `'A'` עד `'Z'`. מחרוזת נספרת אם התו הראשון (מקום 0) או התו האחרון (מקום `length-1`) הוא אות גדולה. מחרוזת שמתחילה וגם מסתיימת באות גדולה נספרת פעם אחת בלבד, כי זה תנאי אחד עם "או".

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

Java:

// פעולת עזר: האם התו הוא אות גדולה באנגלית
public static boolean isCapital(char c)
{
    return c >= 'A' && c <= 'Z';
}
// קטע התוכנית (בתוך main)
Scanner in = new Scanner(System.in);
String longest = in.next();      // המחרוזת הראשונה היא בינתיים גם הארוכה וגם הקצרה
String shortest = longest;
int count = 0;                   // מחרוזות המתחילות או מסתיימות באות גדולה
if (isCapital(longest.charAt(0)) || isCapital(longest.charAt(longest.length() - 1)))
    count++;
for (int i = 2; i <= 30; i++)
{
    String str = in.next();
    if (str.length() > longest.length())
        longest = str;
    if (str.length() < shortest.length())
        shortest = str;
    if (isCapital(str.charAt(0)) || isCapital(str.charAt(str.length() - 1)))
        count++;
}
System.out.println("Longest: " + longest);
System.out.println("Shortest: " + shortest);
System.out.println("Start or end with a capital letter: " + count);

C#:

// פעולת עזר: האם התו הוא אות גדולה באנגלית
public static bool IsCapital(char c)
{
    return c >= 'A' && c <= 'Z';
}

// קטע התוכנית (בתוך Main)
string longest = Console.ReadLine();   // המחרוזת הראשונה היא בינתיים גם הארוכה וגם הקצרה
string shortest = longest;
int count = 0;                         // מחרוזות המתחילות או מסתיימות באות גדולה
if (IsCapital(longest[0]) || IsCapital(longest[longest.Length - 1]))
    count++;
for (int i = 2; i <= 30; i++)
{
    string str = Console.ReadLine();
    if (str.Length > longest.Length)
        longest = str;
    if (str.Length < shortest.Length)
        shortest = str;
    if (IsCapital(str[0]) || IsCapital(str[str.Length - 1]))
        count++;
}
Console.WriteLine("Longest: " + longest);
Console.WriteLine("Shortest: " + shortest);
Console.WriteLine("Start or end with a capital letter: " + count);

דוגמה: עבור המחרוזות `abc`, `Hello`, `x`, `worlD` ועוד 26 פעמים `mm`: הארוכה `Hello`, הקצרה `x`, ונספרות 2 מחרוזות (`Hello` מתחילה באות גדולה, `worlD` מסתיימת באות גדולה).

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

שאלה 3 · מספרים אקראיים: זוגיים ומספרים עם ספרה זוגית

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

•כמה מספרים זוגיים נוצרו.

•בכמה מהמספרים שנוצרו יש לפחות ספרה זוגית אחת.

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

פתרון

תשובה:

60 פעמים מגרילים מספר בין 100 ל-999; מונים אותו כזוגי אם num % 2 == 0, ומונים אותו במונה השני אם פעולת עזר מוצאת בו ספרה זוגית (פירוק בעזרת %10 ו-/10); מדפיסים את שני המונים.

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

1. הגרלה: מספר תלת-ספרתי חיובי הוא בין 100 ל-999. לפי ההנחיות, X=100X=100, Y=999Y=999, כלומר ב-Java `100 + rand.nextInt(900)` (כי Y−X+1=900Y-X+1=900), וב-C# `rand.Next(100, 1000)`.

2. מספר זוגי: `num % 2 == 0`.

3. ספרה זוגית: פעולת העזר `hasEvenDigit` עוברת על ספרות המספר מימין לשמאל: ספרת האחדות היא `num % 10`; אם היא זוגית – מחזירים `true` מיד. אחרת מורידים אותה (`num /= 10`) וממשיכים. אם הספרות נגמרו ולא נמצאה ספרה זוגית – מחזירים `false`. לדוגמה: עבור 357 כל הספרות אי-זוגיות – false; עבור 325 הספרה 2 זוגית – true.

4. שימו לב שמספר זוגי תמיד נספר גם במונה השני (ספרת האחדות שלו זוגית), אבל לא להפך: 325 אינו זוגי ובכל זאת יש בו ספרה זוגית.

Java:

// פעולת עזר: האם יש במספר לפחות ספרה זוגית אחת
public static boolean hasEvenDigit(int num)
{
    while (num > 0)
    {
        if (num % 10 % 2 == 0)
            return true;
        num /= 10;
    }
    return false;
}
// קטע התוכנית (בתוך main)
Random rand = new Random();
int evenCount = 0;        // כמה מספרים זוגיים
int evenDigitCount = 0;   // בכמה מספרים יש ספרה זוגית
for (int i = 1; i <= 60; i++)
{
    int num = 100 + rand.nextInt(900);   // מספר תלת-ספרתי: 100 עד 999
    if (num % 2 == 0)
        evenCount++;
    if (hasEvenDigit(num))
        evenDigitCount++;
}
System.out.println("Even numbers: " + evenCount);
System.out.println("Numbers with an even digit: " + evenDigitCount);

C#:

// פעולת עזר: האם יש במספר לפחות ספרה זוגית אחת
public static bool HasEvenDigit(int num)
{
    while (num > 0)
    {
        if (num % 10 % 2 == 0)
            return true;
        num /= 10;
    }
    return false;
}

// קטע התוכנית (בתוך Main)
Random rand = new Random();
int evenCount = 0;        // כמה מספרים זוגיים
int evenDigitCount = 0;   // בכמה מספרים יש ספרה זוגית
for (int i = 1; i <= 60; i++)
{
    int num = rand.Next(100, 1000);   // מספר תלת-ספרתי: 100 עד 999
    if (num % 2 == 0)
        evenCount++;
    if (HasEvenDigit(num))
        evenDigitCount++;
}
Console.WriteLine("Even numbers: " + evenCount);
Console.WriteLine("Numbers with an even digit: " + evenDigitCount);

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

שאלה 4 · מחלקת כלב בכלבייה: התאמה, הדפסה וספירה

הנהלת הכלבייה "Best Friend" החליטה למחשב את פרטי הכלבים שבכלבייה. לשם כך הוגדרה המחלקה Dog המייצגת כלב. למחלקה חמש תכונות:

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

•סוג הכלב – type, מטיפוס מחרוזת, String

•מין הכלב – gender, מטיפוס תווי, char. ('M' עבור זכר ו-'F' עבור נקבה)

•גיל הכלב – age, מטיפוס מספר שלם, int. הערך אפס מציין שגיל הכלב אינו ידוע.

•קיבל חיסון? – isImunned, מטיפוס בוליאני, boolean (true – קיבל חיסון, false – לא)

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

(במבחן ב-C#: הטיפוסים string ו-bool, פעולות Get/Set והפעולה ToString.)

א.

כאשר מישהו רוצה לאמץ כלב, הוא מוסר להנהלת הכלבייה את מין הכלב הרצוי ואת הגיל המקסימלי שלו.

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

Java:

public boolean isItSuitable(char gender, int age)

C#:

public bool IsItSuitable(char gender, int age)
(4 נקודות)
ב.

טליה מבקשת מהוריה מתנה ליום ההולדת השמיני שלה: כלב ממין זכר, בן שנה או שנתיים. ההורים מסכימים לאמץ את הכלב רק אם הוא קיבל חיסון.

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

Java:

public static void print(Dog[] arr)

C#:

public static void Print(Dog[] arr)

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

(4 נקודות)
ג.

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

Java:

public static int countNoAge(Dog[] arr)

C#:

public static int CountNoAge(Dog[] arr)
(4 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

הכלב מתאים אם this.gender == gender, הגיל ידוע (age != 0) ו-this.age <= age.

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

1. השוואת מין: `this.gender == gender` – התכונה של הכלב (this) מול הפרמטר. כיוון שלפרמטר ולתכונה אותו שם, משתמשים ב-`this` כדי לפנות לתכונה.

2. השוואת גיל: `this.age <= age` – "גיל מקסימלי" פירושו שגם גיל שווה מתאים.

3. גיל לא ידוע: הערך 0 מציין שהגיל אינו ידוע, ולכן אי אפשר לוודא שהכלב עומד בדרישת הגיל המרבי. נחליט שכלב כזה אינו מתאים (`this.age != 0`). בלי הבדיקה הזו, כלב שגילו לא ידוע היה נחשב תמיד מתאים, כי 0≤age0\le age.

4. הפעולה פנימית, ולכן ניגשת ישירות לתכונות הפרטיות של העצם.

Java:

// בתוך המחלקה Dog
public boolean isItSuitable(char gender, int age)
{
    // גיל 0 = גיל לא ידוע: אי אפשר לוודא שהכלב אינו מבוגר מהגיל המרבי
    return this.gender == gender && this.age != 0 && this.age <= age;
}

C#:

// בתוך המחלקה Dog
public bool IsItSuitable(char gender, int age)
{
    // גיל 0 = גיל לא ידוע: אי אפשר לוודא שהכלב אינו מבוגר מהגיל המרבי
    return this.gender == gender && this.age != 0 && this.age <= age;
}

תשובה: הפעולה מחזירה `this.gender == gender && this.age != 0 && this.age <= age`.

סעיף ב

תשובה:

עוברים על המערך ומדפיסים שם וסוג של כל כלב שעבורו isItSuitable('M', 2) מחזירה true וגם getIsImunned() מחזירה true.

הרעיון: הבקשה של טליה היא בדיוק "בקשת אימוץ" מסעיף א': מין `'M'` וגיל מרבי 2. התנאי של ההורים הוא תנאי נוסף – הכלב קיבל חיסון.

1. "בן שנה או שנתיים" פירושו גיל 1 או 2. הקריאה `isItSuitable('M', 2)` מחזירה true בדיוק לזכרים שגילם ידוע (לא 0) ואינו עולה על 2 – כלומר גילם 1 או 2.

2. את החיסון בודקים בפעולת ה-get של התכונה `isImunned`, כי הפעולה `print` היא פעולה סטטית מחוץ למחלקה ואין לה גישה ישירה לתכונות הפרטיות.

3. לכל כלב שעומד בשני התנאים מדפיסים את שמו ואת סוגו (בעזרת פעולות get).

Java:

public static void print(Dog[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {
        // זכר, בן שנה או שנתיים (גיל ידוע ולכל היותר 2), וקיבל חיסון
        if (arr[i].isItSuitable('M', 2) && arr[i].getIsImunned())
            System.out.println(arr[i].getName() + " " + arr[i].getType());
    }
}

C#:

public static void Print(Dog[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        // זכר, בן שנה או שנתיים (גיל ידוע ולכל היותר 2), וקיבל חיסון
        if (arr[i].IsItSuitable('M', 2) && arr[i].GetIsImunned())
            Console.WriteLine(arr[i].GetName() + " " + arr[i].GetType());
    }
}

דוגמה: עבור הכלבים Rex (זכר, 1, מחוסן), Bella (נקבה, 1, מחוסנת), Max (זכר, 2, מחוסן), Tom (זכר, גיל לא ידוע), Rocky (זכר, 3), Bob (זכר, 2, לא מחוסן) – יודפסו רק Rex ו-Max עם הסוגים שלהם.

תשובה: הפעולה שלמעלה – מדפיסה את השם והסוג של כל כלב שעבורו `isItSuitable('M', 2)` וגם `getIsImunned()` מחזירות true.

סעיף ג

תשובה:

מונה את הכלבים שעבורם getIsImunned() == false וגם getAge() == 0, ומחזירה את המונה.

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

1. מאתחלים מונה `count = 0`.

2. עוברים על כל הכלבים. כלב נספר אם הוא לא קיבל חיסון (`!getIsImunned()`) וגם גילו אינו ידוע (`getAge() == 0`, כי הערך 0 מציין גיל לא ידוע).

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

Java:

public static int countNoAge(Dog[] arr)
{
    int count = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (!arr[i].getIsImunned() && arr[i].getAge() == 0)
            count++;
    }
    return count;
}

C#:

public static int CountNoAge(Dog[] arr)
{
    int count = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (!arr[i].GetIsImunned() && arr[i].GetAge() == 0)
            count++;
    }
    return count;
}

תשובה: הפעולה מחזירה את מספר הכלבים שעבורם `getIsImunned()` הוא false וגם `getAge()` הוא 0.

שאלה 5 · מערך יפה: בדיקה ובנייה אקראית

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

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

לדוגמה, המערך הזה הוא "מערך יפה":

012345678
5341133127

כי 13=3+1+2+7=5+3+4+113=3+1+2+7=5+3+4+1

א.

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

כותרת הפעולה:

Java:

public static boolean isNice(int[] arr)

C#:

public static bool IsNice(int[] arr)
(6 נקודות)
ב.

כתבו פעולה המקבלת מספר שלם אי-זוגי size. הפעולה תיצור מערך של מספרים שלמים בגודל size (אפשר להניח ש- size>4 ) ותמלא אותו במספרים אקראיים תלת-ספרתיים חיוביים כך שיתקבל "מערך יפה".

כותרת הפעולה:

Java:

public static int[]  doItNice(int size)

C#:

public static int[]  DoItNice(int size)
(6 נקודות)
◂ פתרון מלא לשאלה 5

סעיף א

תשובה:

אם האורך זוגי – false; אחרת mid = length/2, מסכמים את האיברים שלפני mid ואת האיברים שאחריו, ומחזירים true אם שני הסכומים שווים ל-arr[mid].

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

1. אורך אי-זוגי: אם `arr.length % 2 == 0` – אין איבר מרכזי, והמערך אינו יפה.

2. האיבר המרכזי: במערך באורך nn אי-זוגי, מקומו mid=⌊n/2⌋mid=\lfloor n/2\rfloor (חילוק שלמים). לפניו בדיוק midmid איברים (מקומות 00 עד mid−1mid-1), ואחריו גם midmid איברים (מקומות mid+1mid+1 עד n−1n-1).

3. שני הסכומים בלולאה אחת: בסיבוב ii (מ-0 עד mid−1mid-1) מוסיפים ל-`sumLeft` את `arr[i]` ול-`sumRight` את `arr[mid+1+i]`.

4. תנאי היופי: מחזירים true רק אם `sumLeft == arr[mid]` וגם `sumRight == arr[mid]`. לפי הדוגמה מהשאלה: עבור המערך באורך 9, mid=4mid=4, sumLeft=5+3+4+1=13sumLeft=5+3+4+1=13, sumRight=3+1+2+7=13sumRight=3+1+2+7=13 ו-`arr[4]` הוא 13 – true.

Java:

public static boolean isNice(int[] arr)
{
    if (arr.length % 2 == 0)         // מערך יפה הוא באורך אי-זוגי
        return false;
    int mid = arr.length / 2;        // מקום האיבר המרכזי
    int sumLeft = 0, sumRight = 0;
    for (int i = 0; i < mid; i++)
    {
        sumLeft += arr[i];           // איבר לפני המרכז
        sumRight += arr[mid + 1 + i]; // איבר אחרי המרכז
    }
    return sumLeft == arr[mid] && sumRight == arr[mid];
}

C#:

public static bool IsNice(int[] arr)
{
    if (arr.Length % 2 == 0)         // מערך יפה הוא באורך אי-זוגי
        return false;
    int mid = arr.Length / 2;        // מקום האיבר המרכזי
    int sumLeft = 0, sumRight = 0;
    for (int i = 0; i < mid; i++)
    {
        sumLeft += arr[i];           // איבר לפני המרכז
        sumRight += arr[mid + 1 + i]; // איבר אחרי המרכז
    }
    return sumLeft == arr[mid] && sumRight == arr[mid];
}

סיבוכיות: מעבר אחד על המערך, O(n)O(n).

תשובה: הפעולה שלמעלה – false לאורך זוגי; אחרת true אם ורק אם סכום האיברים שלפני המרכז וסכום האיברים שאחריו שווים שניהם לאיבר המרכזי.

סעיף ב

תשובה:

צד שמאל: half=size/2 מספרים אקראיים בין 100 ל-999/half; המרכז = סכומם; צד ימין: מחלקים את הסכום באקראי ל-half מספרים תלת-ספרתיים (כל אחד בין 100 לערך שמשאיר לפחות 100 לכל הבאים), והאחרון משלים. אפשרי רק כאשר size <= 19.

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

•מגרילים את צד שמאל;

•האיבר המרכזי נקבע להיות הסכום של צד שמאל;

•את צד ימין מגרילים כך שסכומו יהיה בדיוק אותו סכום.

מגבלת התחום. כל האיברים, כולל האיבר המרכזי, צריכים להיות תלת-ספרתיים (100 עד 999). נסמן half=size−12half=\frac{size-1}{2} – מספר האיברים בכל צד. סכום הצד הוא לפחות 100⋅half100\cdot half, והוא חייב להיות לכל היותר 999. לכן צריך 100⋅half≤999100\cdot half\le 999, כלומר half≤9half\le 9 ו-size≤19size\le 19. עבור size≥21size\ge 21 אין מערך יפה שכל איבריו תלת-ספרתיים; נניח שהפעולה נקראת עם 5≤size≤195\le size\le 19 (נתון חסר בשאלה).

1. צד שמאל: כדי שהסכום לא יעלה על 999, מגבילים כל איבר ל-max=⌊999/half⌋max=\lfloor 999/half\rfloor. כך הסכום לכל היותר half⋅max≤999half\cdot max\le 999. לדוגמה, עבור size=7size=7: half=3half=3, max=333max=333, וכל איבר בצד שמאל בין 100 ל-333.

2. האיבר המרכזי: `arr[mid] = sum`. מתקיים 100⋅half≤sum≤999100\cdot half\le sum\le 999 – תלת-ספרתי.

3. צד ימין: מחזיקים את `rest` – הסכום שעוד צריך לחלק. בכל מקום (חוץ מהאחרון), אם אחריו יבואו עוד `left` איברים, צריך להשאיר להם לפחות 100⋅left100\cdot left. לכן מגרילים בין 100 ל-top=min⁡(999, rest−100⋅left)top=\min(999,\ rest-100\cdot left). ערך זה תמיד לפחות 100, כי rest≥100⋅(left+1)rest\ge 100\cdot(left+1).

4. האיבר האחרון מקבל את מה שנשאר: `rest`. הוא לפחות 100 (בזכות צעד 3) ולכל היותר sum≤999sum\le 999, ולכן תלת-ספרתי, וסכום צד ימין שווה בדיוק ל-`sum`.

Java:

public static int[] doItNice(int size)
{
    Random rand = new Random();
    int[] arr = new int[size];
    int mid = size / 2;              // מקום האיבר המרכזי
    int half = mid;                  // מספר האיברים בכל צד
    int max = 999 / half;            // ערך מרבי לאיבר בצד שמאל, כך שהסכום לא יעלה על 999
    int sum = 0;
    // 1. צד שמאל: מספרים תלת-ספרתיים אקראיים בין 100 ל-max
    for (int i = 0; i < mid; i++)
    {
        arr[i] = 100 + rand.nextInt(max - 100 + 1);
        sum += arr[i];
    }
    // 2. האיבר המרכזי שווה לסכום צד שמאל (תלת-ספרתי, כי 100 <= sum <= 999)
    arr[mid] = sum;
    // 3. צד ימין: מחלקים את sum באקראי ל-half מספרים תלת-ספרתיים
    int rest = sum;                  // הסכום שעוד צריך לחלק
    for (int i = mid + 1; i < size - 1; i++)
    {
        int left = size - 1 - i;     // מספר האיברים שיבואו אחרי איבר זה
        int top = Math.min(999, rest - 100 * left); // משאירים לפחות 100 לכל אחד מהם
        arr[i] = 100 + rand.nextInt(top - 100 + 1);
        rest -= arr[i];
    }
    arr[size - 1] = rest;            // האיבר האחרון משלים את הסכום
    return arr;
}

C#:

public static int[] DoItNice(int size)
{
    Random rand = new Random();
    int[] arr = new int[size];
    int mid = size / 2;              // מקום האיבר המרכזי
    int half = mid;                  // מספר האיברים בכל צד
    int max = 999 / half;            // ערך מרבי לאיבר בצד שמאל, כך שהסכום לא יעלה על 999
    int sum = 0;
    // 1. צד שמאל: מספרים תלת-ספרתיים אקראיים בין 100 ל-max
    for (int i = 0; i < mid; i++)
    {
        arr[i] = rand.Next(100, max + 1);
        sum += arr[i];
    }
    // 2. האיבר המרכזי שווה לסכום צד שמאל (תלת-ספרתי, כי 100 <= sum <= 999)
    arr[mid] = sum;
    // 3. צד ימין: מחלקים את sum באקראי ל-half מספרים תלת-ספרתיים
    int rest = sum;                  // הסכום שעוד צריך לחלק
    for (int i = mid + 1; i < size - 1; i++)
    {
        int left = size - 1 - i;     // מספר האיברים שיבואו אחרי איבר זה
        int top = Math.Min(999, rest - 100 * left); // משאירים לפחות 100 לכל אחד מהם
        arr[i] = rand.Next(100, top + 1);
        rest -= arr[i];
    }
    arr[size - 1] = rest;            // האיבר האחרון משלים את הסכום
    return arr;
}

דוגמה לפלט עבור size=7size=7: `{189, 200, 125, 514, 286, 119, 109}` – כאן 189+200+125=514189+200+125=514 וגם 286+119+109=514286+119+109=514.

תשובה: הפעולה שלמעלה – צד שמאל אקראי (כל איבר עד ⌊999/half⌋\lfloor 999/half\rfloor), מרכז = סכום צד שמאל, וצד ימין חלוקה אקראית של אותו סכום למספרים תלת-ספרתיים (בתנאי ש-size≤19size\le 19).

שאלה 6 · מערך מונים של ציונים: מצטיינים, מקסימום ושכיח

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

כלומר, הערך בתא 0 הוא מספר הסטודנטים שקיבלו ציון 0, הערך בתא 1 הוא מספר הסטודנטים שקיבלו ציון 1 וכן הלאה, הערך בתא 100 הוא מספר הסטודנטים שקיבלו ציון 100.

א.

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

כותרת הפעולה:

Java:

public static int excellent(int[] gradesCountingArray)

C#:

public static int Excellent(int[] gradesCountingArray)
(4 נקודות)
ב.

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

כותרת הפעולה:

Java:

public static int higherGrade(int[] gradesCountingArray)

C#:

public static int HigherGrade(int[] gradesCountingArray)
(4 נקודות)
ג.

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

כותרת הפעולה:

Java:

public static int mostCommonScore(int[] counArr)

C#:

public static int MostCommonScore(int[] gradesCountingArray)
(4 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

סכום הערכים בתאים 91 עד 100.

הרעיון: במערך מונים, האינדקס הוא הציון והערך הוא מספר הסטודנטים. "ציון גבוה מ-90" הוא ציון 91 עד 100, ולכן מספר הסטודנטים הוא סכום הערכים בתאים 91 עד 100 (לא מספר התאים!).

1. מאתחלים `count = 0`.

2. עוברים על הציונים 91 עד 100 ומוסיפים ל-`count` את `gradesCountingArray[grade]`.

3. מחזירים את `count`.

Java:

public static int excellent(int[] gradesCountingArray)
{
    int count = 0;
    for (int grade = 91; grade <= 100; grade++)   // ציונים גבוהים מ-90
        count += gradesCountingArray[grade];
    return count;
}

C#:

public static int Excellent(int[] gradesCountingArray)
{
    int count = 0;
    for (int grade = 91; grade <= 100; grade++)   // ציונים גבוהים מ-90
        count += gradesCountingArray[grade];
    return count;
}

דוגמה: אם 4 סטודנטים קיבלו 90, 2 קיבלו 91 ו-1 קיבל 95 – הפעולה מחזירה 2+1=32+1=3 (ציון 90 אינו גבוה מ-90).

תשובה: הפעולה מחזירה את סכום `gradesCountingArray[91]` עד `gradesCountingArray[100]`.

סעיף ב

תשובה:

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

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

1. עוברים על התאים מ-100 כלפי מטה.

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

3. אם לא נמצא אף תא כזה (אין אף ציון במערך), מחזירים -1 כסימן לכך.

Java:

public static int higherGrade(int[] gradesCountingArray)
{
    for (int grade = 100; grade >= 0; grade--)    // מהציון הגבוה כלפי מטה
    {
        if (gradesCountingArray[grade] > 0)
            return grade;                          // הציון הראשון שמישהו קיבל
    }
    return -1;                                     // אין אף ציון במערך
}

C#:

public static int HigherGrade(int[] gradesCountingArray)
{
    for (int grade = 100; grade >= 0; grade--)    // מהציון הגבוה כלפי מטה
    {
        if (gradesCountingArray[grade] > 0)
            return grade;                          // הציון הראשון שמישהו קיבל
    }
    return -1;                                     // אין אף ציון במערך
}

דוגמה: אם הציונים שהתקבלו הם 50, 70, 85, 90, 91 ו-95 – הפעולה מחזירה 95.

תשובה: הפעולה מחזירה את האינדקס הגדול ביותר שבו `gradesCountingArray[grade] > 0`.

סעיף ג

תשובה:

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

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

1. כדי שבשוויון ייבחר הציון הגבוה, סורקים מהציון הגבוה לנמוך: מתחילים עם `best = 100`, ועוברים על 99 עד 0.

2. מחליפים את `best` רק אם השכיחות של הציון הנוכחי גדולה ממש מהשכיחות של `best`. בשוויון לא מחליפים, ולכן נשאר הציון הגבוה יותר (שנבדק קודם).

3. מחזירים את `best`.

Java:

public static int mostCommonScore(int[] counArr)
{
    int best = 100;                                // הציון הנפוץ ביותר עד כה
    for (int grade = 99; grade >= 0; grade--)      // מהגבוה לנמוך
    {
        if (counArr[grade] > counArr[best])        // רק שכיחות גדולה ממש מחליפה
            best = grade;
    }
    return best;
}

C#:

public static int MostCommonScore(int[] gradesCountingArray)
{
    int best = 100;                                // הציון הנפוץ ביותר עד כה
    for (int grade = 99; grade >= 0; grade--)      // מהגבוה לנמוך
    {
        if (gradesCountingArray[grade] > gradesCountingArray[best]) // רק שכיחות גדולה ממש מחליפה
            best = grade;
    }
    return best;
}

דוגמה: אם 5 סטודנטים קיבלו 70 ו-5 קיבלו 85 (וזו השכיחות הגבוהה ביותר) – הפעולה מחזירה 85.

תשובה: הפעולה מחזירה את הציון שבו `counArr[grade]` מרבי; בשוויון – הציון הגבוה ביותר מביניהם.

שאלה 7 · מעקב אחר פעולה על מחרוזת

נתונה הפעולה secret הבאה המקבלת מחרוזות:

Java:

public static String secret (String s)
  {
    String res="";
    int i;
    for(i=0; i < s.length()-1; i++)
    {
      if(s.charAt(i)>='A' && s.charAt(i)<='Z')
      {
        if(s.charAt(i) != s.charAt(i+1))
            res+= s.charAt(i);
      }
      else
      {
        if(s.charAt(i) == s.charAt(i+1))
        {
          res+= s.charAt(i);
        }
      }
    }
    res+= s.charAt(i);

    return res;
  }

C#:

public static string Secret (string s)
  {
    string res="";
    int i;
    for(i=0; i < s.Length - 1; i++)
    {
      if(s[i]>='A' && s[i]<='Z')
      {
        if(s[i] != s[i+1])
            res+= s[i];
      }
      else
      {
        if(s[i] == s[i+1])
        {
          res+= s[i];
        }
      }
    }
    res+= s[i];

    return res;
  }
א.

עקבו בעזרת טבלת המעקב אחרי זימון הפעולה secret("K%%ABB23CCC??DD") ורשמו מה תהיה תוצאת הזימון.

(5 נקודות)
ב.

האם קיימת מחרוזת לא ריקה str כך שזימון הפעולה secret(str) יחזיר מחרוזת זהה ל- str?

אם כן – תנו דוגמה למחרוזת, אם לא – הסבירו למה אין מחרוזת כזאת.

(2 נקודות)
ג.

האם קיימות שתי מחרוזות שונות str1 ו- str2 כך שתוצאות הזימונים secret(str1) ו- secret(str2) יהיו זהות? אם כן – תנו דוגמה לזוג מחרוזות str1 ו- str2, אם לא – הסבירו למה אין זוג כזה.

(2 נקודות)
ד.

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

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

סעיף א

תשובה:

"K%ABC?D"

עוקבים אחרי הלולאה. אורך המחרוזת 15, ולכן `i` רץ מ-0 עד 13 (התנאי `i < 14`), ובכל סיבוב משווים את התו `s[i]` לתו שאחריו:

•אם `s[i]` אות גדולה – מוסיפים אותו רק אם הוא שונה מהתו הבא;

•אחרת – מוסיפים אותו רק אם הוא שווה לתו הבא.

אחרי הלולאה `i` שווה 14, ומוסיפים את התו האחרון `s[14]`.

סיבוב is[i]s[i+1]s[i] אות גדולה?s[i] == s[i+1]?מוסיפים את s[i]?res
0K%כןלאכןK
1%%לאכןכןK%
2%AלאלאלאK%
3ABכןלאכןK%A
4BBכןכןלאK%A
5B2כןלאכןK%AB
623לאלאלאK%AB
73CלאלאלאK%AB
8CCכןכןלאK%AB
9CCכןכןלאK%AB
10C?כןלאכןK%ABC
11??לאכןכןK%ABC?
12?DלאלאלאK%ABC?
13DDכןכןלאK%ABC?
אחרי הלולאה, i=14D–––תמידK%ABC?D

תשובה: `secret("K%%ABB23CCC??DD")` מחזירה `"K%ABC?D"`.

סעיף ב

תשובה:

כן, למשל "AB" (וגם "A").

כן. צריך שכל תו בלולאה יתווסף, ולכן נבחר אותיות גדולות שכל אחת שונה מהבאה אחריה.

עבור `str = "AB"`:

1. i=0i=0: `'A'` אות גדולה ושונה מ-`'B'` – מוסיפים: `res = "A"`.

2. הלולאה מסתיימת (i=1i=1), ומוסיפים את התו האחרון `'B'`: `res = "AB"`.

התוצאה זהה ל-str. (גם `"A"` מתאימה: הלולאה לא מתבצעת כלל, ומוסיפים רק את התו האחרון – `"A"`.)

תשובה: כן, למשל `"AB"`.

סעיף ג

תשובה:

כן, למשל str1="AA" ו-str2="A": שתיהן מחזירות "A".

כן. הפעולה "מוחקת" תווים, ולכן מחרוזות שונות יכולות להגיע לאותה תוצאה.

•`secret("AA")`: i=0i=0 – `'A'` אות גדולה ושווה לתו הבא, לא מוסיפים. אחרי הלולאה מוסיפים את התו האחרון – `"A"`.

•`secret("A")`: הלולאה לא מתבצעת, ומוסיפים את התו האחרון – `"A"`.

תשובה: כן, למשל `str1 = "AA"` ו-`str2 = "A"` – שתיהן מחזירות `"A"`.

סעיף ד

תשובה:

מצמצמת כל רצף של אות גדולה זהה לאות אחת, ומכל רצף של תו אחר (שאינו אות גדולה) משמיטה את התו האחרון ברצף (תו בודד נמחק); התו האחרון של המחרוזת נשאר תמיד.

נחלק את המחרוזת לרצפים של תווים זהים צמודים (למשל `"K%%ABB23CCC??DD"` = K | %% | A | BB | 2 | 3 | CCC | ?? | DD).

1. רצף של אות גדולה: כל תו ברצף שווה לתו שאחריו, חוץ מהאחרון ברצף. אות גדולה נוספת רק אם היא שונה מהבאה, ולכן מכל רצף נשאר תו אחד בלבד (האחרון). כך `BB` הופך ל-`B` ו-`CCC` ל-`C`.

2. רצף של תו שאינו אות גדולה (ספרה, סימן, אות קטנה): תו כזה נוסף רק אם הוא שווה לתו שאחריו, ולכן מרצף באורך kk נשארים k−1k-1 תווים – התו האחרון ברצף נמחק. תו בודד (רצף באורך 1) נמחק לגמרי: `2` ו-`3` נעלמו, `%%` הפך ל-`%`, ו-`??` ל-`?`.

3. התו האחרון במחרוזת מתווסף תמיד אחרי הלולאה, ולכן הרצף האחרון במחרוזת לא מאבד את התו האחרון שלו.

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

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

נתון מערך של מספרים שלמים באורך אי-זוגי שבו כל האיברים שונים זה מזה (אין חזרות).

הגדרה:

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

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

0123456
21071813421
א.

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

כותרת הפעולה:

Java:

public static int median(int[] arr)

C#:

public static int Median(int[] arr)
(6 נקודות)

נתונה הגדרה נוספת:

"מערך מיוחד" הוא מערך בגודל אי-זוגי העונה לתנאים האלה:

•החציון נמצא במרכז המערך.

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

לדוגמה, המערך שלפניכם הוא "מערך מיוחד":

0123456
27410182113
ב.

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

כותרת הפעולה:

Java:

public static int[] buildSpecial(int[] arr)

C#:

public static int[] BuildSpecial(int[] arr)
(6 נקודות)
ג.

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

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

סעיף א

תשובה:

לכל איבר סופרים כמה איברים קטנים ממנו; האיבר שעבורו המספר שווה ל-length/2 הוא החציון. סיבוכיות O(n²).

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

1. עוברים בלולאה חיצונית על כל איבר `arr[i]` – "מועמד" להיות חציון.

2. בלולאה פנימית סופרים כמה איברים קטנים ממנו (`smaller`).

3. אם `smaller == arr.length / 2`, מספר הגדולים ממנו הוא n−1−smallern-1-smaller, וגם הוא שווה ל-n−12\frac{n-1}{2}. לכן `arr[i]` הוא החציון ומחזירים אותו.

4. במערך תקין תמיד יש חציון (האיבר האמצעי בסדר ממוין), ולכן ההחזרה של -1 בסוף רק משלימה את הפעולה מבחינה תחבירית.

בדיקה על הדוגמה: עבור 10 – הקטנים ממנו הם 2, 7, 4 (שלושה), והגדולים 18, 13, 21 (שלושה). 7/2=37/2=3 ולכן מוחזר 10.

Java:

public static int median(int[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {
        int smaller = 0;                     // כמה איברים קטנים מ-arr[i]
        for (int j = 0; j < arr.length; j++)
        {
            if (arr[j] < arr[i])
                smaller++;
        }
        // אין חזרות, ולכן כל שאר האיברים (פרט ל-arr[i] עצמו) גדולים ממנו
        if (smaller == arr.length / 2)
            return arr[i];
    }
    return -1;   // לא יקרה במערך תקין באורך אי-זוגי בלי חזרות
}

C#:

public static int Median(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        int smaller = 0;                     // כמה איברים קטנים מ-arr[i]
        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] < arr[i])
                smaller++;
        }
        // אין חזרות, ולכן כל שאר האיברים (פרט ל-arr[i] עצמו) גדולים ממנו
        if (smaller == arr.Length / 2)
            return arr[i];
    }
    return -1;   // לא יקרה במערך תקין באורך אי-זוגי בלי חזרות
}

תשובה: הפעולה מחזירה את האיבר שמספר האיברים הקטנים ממנו שווה ל-`arr.length / 2` (בדוגמה – 10).

סעיף ב

תשובה:

מוצאים את החציון med (סעיף א) ושמים אותו ב-res[n/2]; עוברים על arr: איבר קטן מ-med נכתב ב-res[left++] (מ-0), איבר גדול נכתב ב-res[right++] (מ-n/2+1).

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

1. `med = median(arr)`, `mid = arr.length / 2`, ו-`res[mid] = med`.

2. שני "מצביעים" למקום הפנוי הבא: `left` מתחיל ב-0 (לאיברים קטנים), ו-`right` מתחיל ב-`mid + 1` (לאיברים גדולים).

3. עוברים על `arr`: איבר קטן מ-`med` נכתב ב-`res[left]` ו-`left` גדל; איבר גדול מ-`med` נכתב ב-`res[right]` ו-`right` גדל; החציון עצמו כבר במקומו, ולכן מדלגים עליו.

4. בדיוק `mid` איברים קטנים מהחציון ו-`mid` גדולים ממנו, ולכן `left` מגיע בדיוק עד `mid` ו-`right` בדיוק עד סוף המערך – כל התאים מתמלאים ואין חריגה.

Java:

public static int[] buildSpecial(int[] arr)
{
    int med = median(arr);
    int[] res = new int[arr.length];
    int mid = arr.length / 2;
    res[mid] = med;                 // החציון במרכז
    int left = 0;                   // המקום הפנוי הבא לאיבר קטן
    int right = mid + 1;            // המקום הפנוי הבא לאיבר גדול
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] < med)
        {
            res[left] = arr[i];
            left++;
        }
        else if (arr[i] > med)
        {
            res[right] = arr[i];
            right++;
        }
    }
    return res;
}

C#:

public static int[] BuildSpecial(int[] arr)
{
    int med = Median(arr);
    int[] res = new int[arr.Length];
    int mid = arr.Length / 2;
    res[mid] = med;                 // החציון במרכז
    int left = 0;                   // המקום הפנוי הבא לאיבר קטן
    int right = mid + 1;            // המקום הפנוי הבא לאיבר גדול
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] < med)
        {
            res[left] = arr[i];
            left++;
        }
        else if (arr[i] > med)
        {
            res[right] = arr[i];
            right++;
        }
    }
    return res;
}

דוגמה: עבור `{2, 10, 7, 18, 13, 4, 21}`: החציון 10 נכתב ב-`res[3]`; הקטנים 2, 7, 4 נכתבים במקומות 0–2, והגדולים 18, 13, 21 במקומות 4–6. מתקבל `{2, 7, 4, 10, 18, 13, 21}` – מערך מיוחד (הסדר בתוך כל צד לא חשוב).

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

סעיף ג

תשובה:

median: O(n²); buildSpecial: O(n²) (קריאה ל-median ועוד מעבר אחד O(n)).

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

1. `median` (סעיף א'): לולאה חיצונית על nn איברים, ובתוכה לולאה פנימית על nn איברים. במקרה הגרוע (החציון הוא האיבר האחרון במערך) מתבצעות n⋅n=n2n\cdot n=n^2 השוואות. הסיבוכיות O(n2)O(n^2).

2. `buildSpecial` (סעיף ב'): קריאה אחת ל-`median` – O(n2)O(n^2), ואחריה מעבר אחד על המערך – O(n)O(n). בסך הכול O(n2)+O(n)=O(n2)O(n^2)+O(n)=O(n^2); הקריאה ל-`median` היא החלק הדומיננטי.

(אפשר היה למצוא חציון ב-O(nlog⁡n)O(n\log n) על ידי מיון עותק של המערך ולקיחת האיבר האמצעי, אבל הפעולות שכתבנו הן O(n2)O(n^2).)

תשובה: `median` – O(n2)O(n^2) (לולאה מקוננת); `buildSpecial` – O(n2)O(n^2) (קריאה ל-`median` ועוד מעבר לינארי).

שאלה 9 · מחלקות תאריך ותינוק: התפתחות ותאומים

מערכת מידע העוקבת אחר התפתחות תינוקות בקופות חולים כוללת שתי מחלקות: Date ו-Baby.

המחלקה Date מייצגת תאריך ולה שלוש תכונות:

day – יום, month – חודש, year – שנה.

למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות.

וכן הוגדרו שתי פעולות: equals ו-tomorrow.

•הפעולה boolean equals(Date other) המקבלת כפרמטר תאריך מסוים other, ובודקת אם הוא זהה לתאריך המיוצג על ידי האובייקט שמפעיל את הפעולה (this).

•הפעולה Date tomorrow() המחזירה את התאריך שלמוחרת התאריך this.

המחלקה Baby מייצגת תינוק ולה שש תכונות:

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

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

•מספר זהות – id, מטיפוס מחרוזת, String

•תאריך לידה – birth, מטיפוס Date

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

•גובה – height, מטיפוס שלם, int

למחלקה הוגדרו פעולה בונה, ופעולות set/get לכל התכונות.

(במבחן ב-C#: bool equals(Date other), הטיפוס string ופעולות Set/Get.)

א.

כתבו במחלקה Baby את הפעולה compareTo המקבלת כפרמטר תינוק other ומחזירה מספר שלם המציין הבדל ברמות התפתחות של שני תינוקות:

•אם המשקל של התינוק הנוכחי (שמיוצג באמצעות האובייקט שמפעיל את הפעולה, this) שווה למשקל של התינוק other, וגם הגובה של this שווה לגובה של other, הפעולה תחזיר 0.

•אם גם המשקל של this גדול מהמשקל של other וגם הגובה של this גדול מהגובה של other, הפעולה תחזיר 1.

•אם רק המשקל של this גדול מהמשקל של other, הפעולה תחזיר 2.

•אם רק הגובה של this גדול מהגובה של other הפעולה תחזיר 3.

•אחרת, הפעולה תחזיר 4.

(במבחן ב-C#: הפעולה CompareTo.)

(3 נקודות)
ב.

כתבו במחלקה Baby את הפעולה הבוליאנית areTwins המקבלת כפרמטר תינוק נוסף other ובודקת אם הוא תאום של התינוק המיוצג באובייקט שמפעיל את הפעולה (this).

אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false .

התינוקות הם תאומים אם:

•שם המשפחה שלהם זהה.

•השם הפרטי שלהם שונה.

•מספרי הזהות של התינוקות שונים זה מזה.

•תאריך הלידה שלהם זהה או שונה ביום אחד בדיוק (כלומר, נולדו באותו יום או בימים עוקבים).

(במבחן ב-C#: הפעולה AreTwins.)

(3 נקודות)
ג.

כתבו פעולה המקבלת מערך תינוקות babies (מערך של עצמים מסוג Baby) תינוק baby נוסף.

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

כותרת הפעולה:

Java:

public static void print(Baby[] babies, Baby baby)

C#:

public static void Print(Baby[] babies, Baby baby)

חובה להשתמש בפעולה שכתבתם בסעיף א'

(4 נקודות)
ד.

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

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

סעיף א

תשובה:

בדיקות לפי הסדר: משקל וגובה שווים – 0; שניהם גדולים – 1; רק המשקל גדול – 2; רק הגובה גדול – 3; אחרת 4.

הרעיון: סדרת תנאים לפי הסדר שבשאלה. הסדר חשוב: אחרי שבדקנו את המקרה "גם המשקל וגם הגובה גדולים", אם המשקל גדול – בהכרח הגובה לא גדול, ולכן זה בדיוק המקרה "רק המשקל גדול". כך גם לגבי הגובה.

1. משקל שווה וגם גובה שווה – מחזירים 0.

2. משקל גדול וגם גובה גדול – מחזירים 1.

3. (כבר ידוע שלא שניהם גדולים) משקל גדול – מחזירים 2.

4. (כבר ידוע שהמשקל לא גדול) גובה גדול – מחזירים 3.

5. כל מקרה אחר (למשל שניהם קטנים, או משקל שווה וגובה קטן) – מחזירים 4.

הפעולה פנימית במחלקה Baby, ולכן ניגשת ישירות לתכונות `weight`, `height` גם של `this` וגם של `other` (אותה מחלקה).

Java:

// בתוך המחלקה Baby
public int compareTo(Baby other)
{
    if (this.weight == other.weight && this.height == other.height)
        return 0;                          // אותה רמת התפתחות
    if (this.weight > other.weight && this.height > other.height)
        return 1;                          // גם כבד יותר וגם גבוה יותר
    if (this.weight > other.weight)
        return 2;                          // רק המשקל גדול יותר
    if (this.height > other.height)
        return 3;                          // רק הגובה גדול יותר
    return 4;                              // כל מקרה אחר
}

C#:

// בתוך המחלקה Baby
public int CompareTo(Baby other)
{
    if (this.weight == other.weight && this.height == other.height)
        return 0;                          // אותה רמת התפתחות
    if (this.weight > other.weight && this.height > other.height)
        return 1;                          // גם כבד יותר וגם גבוה יותר
    if (this.weight > other.weight)
        return 2;                          // רק המשקל גדול יותר
    if (this.height > other.height)
        return 3;                          // רק הגובה גדול יותר
    return 4;                              // כל מקרה אחר
}

דוגמה: this – 3.5 ק"ג ו-52 ס"מ, other – 3.2 ק"ג ו-50 ס"מ: מוחזר 1. this – 3.5 ק"ג ו-49 ס"מ מול אותו other: מוחזר 2.

תשובה: הפעולה שלמעלה (0 – זהים, 1 – שניהם גדולים, 2 – רק משקל, 3 – רק גובה, 4 – אחרת).

סעיף ב

תשובה:

lastName שווה, firstName שונה, id שונה, ו-birth שווה או birth.tomorrow() שווה ל-other.birth או other.birth.tomorrow() שווה ל-birth.

הרעיון: ארבעה תנאים שכולם צריכים להתקיים (וגם). שלושת הראשונים הם השוואות מחרוזות; התנאי הרביעי משתמש בפעולות `equals` ו-`tomorrow` של המחלקה Date.

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

2. תאריך לידה: "שונה ביום אחד בדיוק" יכול להיות בשני הכיוונים, ולכן יש שלוש אפשרויות:

•`this.birth.equals(other.birth)` – נולדו באותו יום;

•`this.birth.tomorrow().equals(other.birth)` – other נולד יום אחרי this;

•`other.birth.tomorrow().equals(this.birth)` – this נולד יום אחרי other.

השימוש ב-`tomorrow` מטפל נכון גם במעבר חודש ושנה (למשל 31.12.2024 ו-1.1.2025), בלי לחשב בעצמנו ימים בחודש.

3. מחזירים את ה"וגם" של ארבעת התנאים.

Java:

// בתוך המחלקה Baby
public boolean areTwins(Baby other)
{
    boolean sameLast = this.lastName.equals(other.lastName);
    boolean diffFirst = !this.firstName.equals(other.firstName);
    boolean diffId = !this.id.equals(other.id);
    boolean closeBirth = this.birth.equals(other.birth)               // באותו יום
                      || this.birth.tomorrow().equals(other.birth)    // other נולד יום אחרי this
                      || other.birth.tomorrow().equals(this.birth);   // this נולד יום אחרי other
    return sameLast && diffFirst && diffId && closeBirth;
}

C#:

// בתוך המחלקה Baby
public bool AreTwins(Baby other)
{
    bool sameLast = this.lastName == other.lastName;
    bool diffFirst = this.firstName != other.firstName;
    bool diffId = this.id != other.id;
    bool closeBirth = this.birth.equals(other.birth)               // באותו יום
                   || this.birth.tomorrow().equals(other.birth)    // other נולד יום אחרי this
                   || other.birth.tomorrow().equals(this.birth);   // this נולד יום אחרי other
    return sameLast && diffFirst && diffId && closeBirth;
}

דוגמה: Dan Cohen (מ"ז 1, נולד 31.12.2024) ו-Noa Cohen (מ"ז 2, נולדה 1.1.2025) – תאומים (true). Dan Cohen ו-Dan Cohen אחר – false (השם הפרטי זהה).

תשובה: הפעולה מחזירה true אם שם המשפחה זהה, השם הפרטי שונה, מספר הזהות שונה ותאריכי הלידה זהים או עוקבים (בעזרת `equals` ו-`tomorrow`).

סעיף ג

תשובה:

מדפיסים את getId() של כל babies[i] שעבורו babies[i].compareTo(baby) == 0.

הרעיון: "אותה רמת התפתחות" פירושה בדיוק שהפעולה `compareTo` מסעיף א' מחזירה 0 (אותו משקל ואותו גובה).

1. עוברים על כל התינוקות במערך.

2. לכל תינוק מפעילים `babies[i].compareTo(baby)`. אם התוצאה 0 – מדפיסים את מספר הזהות שלו בעזרת `getId()` (התכונה פרטית, והפעולה הסטטית נמצאת מחוץ למחלקה).

Java:

public static void print(Baby[] babies, Baby baby)
{
    for (int i = 0; i < babies.length; i++)
    {
        if (babies[i].compareTo(baby) == 0)          // אותה רמת התפתחות
            System.out.println(babies[i].getId());
    }
}

C#:

public static void Print(Baby[] babies, Baby baby)
{
    for (int i = 0; i < babies.Length; i++)
    {
        if (babies[i].CompareTo(baby) == 0)          // אותה רמת התפתחות
            Console.WriteLine(babies[i].GetId());
    }
}

תשובה: הפעולה מדפיסה את `getId()` של כל תינוק במערך שעבורו `compareTo(baby)` מחזירה 0.

סעיף ד

תשובה:

לולאה כפולה על כל הזוגות i<j, וסופרים את הזוגות שעבורם babies[i].areTwins(babies[j]) מחזירה true.

הרעיון: עוברים על כל זוגות התינוקות במערך, כל זוג פעם אחת בלבד, ובודקים כל זוג בעזרת `areTwins` מסעיף ב'.

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

2. אם `babies[i].areTwins(babies[j])` – מגדילים את המונה.

3. מחזירים את המונה. (בשלישייה יש שלושה זוגות תאומים, וכולם נספרים.)

Java:

public static int countTwins(Baby[] babies)
{
    int count = 0;
    for (int i = 0; i < babies.length - 1; i++)
    {
        for (int j = i + 1; j < babies.length; j++)  // כל זוג נבדק פעם אחת
        {
            if (babies[i].areTwins(babies[j]))
                count++;
        }
    }
    return count;
}

C#:

public static int CountTwins(Baby[] babies)
{
    int count = 0;
    for (int i = 0; i < babies.Length - 1; i++)
    {
        for (int j = i + 1; j < babies.Length; j++)  // כל זוג נבדק פעם אחת
        {
            if (babies[i].AreTwins(babies[j]))
                count++;
        }
    }
    return count;
}

סיבוכיות: n(n−1)2\frac{n(n-1)}{2} בדיקות, כלומר O(n2)O(n^2).

דוגמה: Dan, Noa ו-Tal Cohen שנולדו ב-31.12.2024 / 1.1.2025 / 31.12.2024 עם מספרי זהות שונים – 3 זוגות תאומים.

תשובה: הפעולה מחזירה את מספר הזוגות i<ji<j שעבורם `babies[i].areTwins(babies[j])` מחזירה true.

שאלה 10 · מעקב: ספרות עולות ממש ומקום המקסימום

א.

נתונה הפעולה one המקבלת כפרמטר מספר שלם וחיובי num :

Java:

public static boolean one(int num){
    while (num > 9)
    {
        if(num % 10 <= num/10%10)
          return false;
        num = num / 10;
    }
    return true;
}

C#:

public static bool One(int num){
    while (num > 9)
    {
        if(num % 10 <= num/10%10)
          return false;
        num = num / 10;
    }
    return true;
}
(1)

תנו דוגמה של מספר num > 1000 כך שתוצאת הזימון one(num) תהיה true.

(2)

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

(5 נקודות)
ב.

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

Java:

public static int two(int[] arr){
    int  res = -1;

    for (int i = 0; i < arr.length; i++)
    {
          if(one(arr[i]))
          {
            if(res == -1 || arr[i]> arr[res])
               res = i;
          }
    }
    return res;
}

C#:

public static int Two(int[] arr){
    int  res = -1;

    for (int i = 0; i < arr.Length; i++)
    {
          if(One(arr[i]))
          {
            if(res == -1 || arr[i]> arr[res])
               res = i;
          }
    }
    return res;
}

נתון מערך של מספרים שלמים וחיוביים arr:

Java:

int[] arr = {21, 13, 34783, 68, 131, 468, 761};

C#:

int[] arr = {21, 13, 34783, 68, 131, 468, 761};
(1)

עקבו באמצעות טבלת מעקב אחר ביצוע זימון הפעולה two(arr) ורשמו מה יהיה הפלט.

(2)

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

(5 נקודות)
ג.

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

Java:

public static int three(int[] arr){

    boolean flag = true;
    for (int i = 0; i < arr.length; i++)
    {
        if (!one(arr[i]))
        {
            flag = false;
        }
    }
     if(flag) return two(arr);
     return -1;
}

C#:

public static int Three(int[] arr){

    bool flag = true;
    for (int i = 0; i < arr.Length; i++)
    {
        if (!One(arr[i]))
        {
            flag = false;
        }
    }
     if(flag) return Two(arr);
     return -1;
}
(1)

תנו דוגמה למערך arr בגודל שישה תאים שעבורו תוצאת זימון הפעולה three(arr) תהיה 3.

(2)

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

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

סעיף א

(1)
תשובה:

למשל 1234.

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

נבדוק את num=1234num=1234:

1. 4≤34 \le 3? לא. num=123num=123.

2. 3≤23 \le 2? לא. num=12num=12.

3. 2≤12 \le 1? לא. num=1num=1 – הלולאה מסתיימת (1≤91\le 9).

4. מוחזר true.

תשובה: `num = 1234` (וכל מספר גדול מ-1000 שספרותיו עולות ממש משמאל לימין, כמו 1357 או 2589).

(2)
תשובה:

מחזירה true אם ספרות המספר עולות ממש משמאל לימין (כל ספרה גדולה מזו שמשמאלה); אחרת false. מספר חד-ספרתי – true.

בכל סיבוב הפעולה משווה את ספרת האחדות `num % 10` לספרת העשרות `num / 10 % 10`. אם ספרת האחדות קטנה או שווה לספרה שמשמאלה – מוחזר false. אחרת מורידים את ספרת האחדות (`num / 10`) וממשיכים לזוג הבא. כך נבדקים כל זוגות הספרות הצמודות.

הלולאה מסתיימת כאשר נשארת ספרה אחת (num≤9num\le 9), ואז מוחזר true. מספר חד-ספרתי מחזיר true מיד.

תשובה: הפעולה מחזירה true אם ספרות המספר מסודרות בסדר עולה ממש משמאל לימין (כל ספרה גדולה מהספרה שמשמאלה; חד-ספרתי – true), ואחרת false.

סעיף ב

(1)
תשובה:

5

`res` מתחיל ב-1-. לכל איבר בודקים קודם את `one` (ספרות עולות ממש). רק אם התוצאה true, משווים אותו לאיבר במקום `res` (או מעדכנים מיד אם `res` עדיין 1-).

- 21: 1≤21\le 2 – false. 34783: 3≤83\le 8 – false. 131: 1≤31\le 3 – false. 761: 1≤61\le 6 – false.

- 13, 68, 468 – ספרות עולות ממש, true.

iarr[i]one(arr[i])res לפניarr[res] לפניres אחרי
021false-1–-1
113true-1–1
234783false1131
368true1133
4131false3683
5468true3685
6761false54685

תשובה: הפעולה מחזירה 5 (המקום של 468).

(2)
תשובה:

מחזירה את המקום (האינדקס) של האיבר הגדול ביותר מבין האיברים שספרותיהם עולות ממש; אם אין כזה – 1-.

הפעולה עוברת על המערך ומתייחסת רק לאיברים שעבורם `one` מחזירה true, כלומר מספרים שספרותיהם עולות ממש. מבין אלה היא מחפשת את המקסימום, ושומרת ב-`res` את המקום שלו. ההשוואה `>` חזקה, ולכן בשוויון נשמר המקום הראשון. אם אין במערך אף איבר כזה, `res` נשאר 1-.

תשובה: הפעולה מחזירה את האינדקס של האיבר הגדול ביותר מבין האיברים שספרותיהם עולות ממש משמאל לימין (בשוויון – הראשון), ו-1- אם אין איבר כזה.

סעיף ג

(1)
תשובה:

למשל {12, 3, 45, 789, 6, 123}.

כדי ש-`three` לא תחזיר 1-, כל איברי המערך צריכים להיות בעלי ספרות עולות ממש. אז מוחזרת התוצאה של `two`, כלומר המקום של האיבר הגדול ביותר. לכן צריך שהמקסימום יהיה במקום 3.

נבחר `arr = {12, 3, 45, 789, 6, 123}`:

1. כל האיברים בעלי ספרות עולות ממש: 12, 3, 45, 789, 6, 123 – `flag` נשאר true.

2. `two(arr)`: המקסימום הוא 789, במקום 3.

תשובה: למשל `arr = {12, 3, 45, 789, 6, 123}`, ו-`three(arr)` מחזירה 3.

(2)
תשובה:

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

הלולאה בודקת את כל האיברים: אם יש לפחות איבר אחד שעבורו `one` מחזירה false, `flag` הופך ל-false והפעולה מחזירה 1-. אם כל האיברים עברו את הבדיקה, כל האיברים "משתתפים" ב-`two`, ולכן `two` מחזירה את מקום המקסימום של המערך כולו.

תשובה: אם בכל איברי המערך הספרות עולות ממש משמאל לימין, הפעולה מחזירה את האינדקס של האיבר הגדול ביותר במערך (הראשון מביניהם בשוויון); אחרת היא מחזירה 1-.

שאלה 11 · מחלקות פיקסל ותמונה: שחור, לבן ומסגרת

פיקסל - Pixel היא יחידת מידע גרפית בסיסית במחשב המתארת נקודה בתמונה דיגיטלית. כל פיקסל מורכב משלושה צבעים: אדום – red, ירוק – green, וכחול – blue. כל אחד משלושת הצבעים מורכב מערך מספרי בין 0 ל-255.

שילוב שלושת הצבעים אדום, ירוק וכחול בערכים שונים בין 0 ל-255, נותן את קשת הצבעים במחשב.

לדוגמה :

•אדום – 0, ירוק – 0, כחול – 0 : מתקבל צבע שחור

•אדום – 255, ירוק – 255, כחול – 255 : מתקבל צבע לבן.

•אדום – 255, ירוק – 0, כחול – 0 : מתקבל צבע אדום.

למחלקה Pixel שלוש תכונות:

private int red;   // מייצגת את הצבע האדום
private int green; // מייצגת את הצבע הירוק
private int blue;  // מייצגת את הצבע הכחול

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

א.

כתבו במחלקה Pixel את הפעולה isBlack() הבודקת האם מהערכים של שלושת הצבעים מתקבל צבע שחור. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

(במבחן ב-C#: IsBlack().)

(3 נקודות)

נתונה המחלקה Picture המייצגת תמונה.

למחלקה תכונה אחת בלבד, מערך דו-ממדי מטיפוס Pixel בגודל 256x256 בשם pixels:

private Pixel[] pixels = new Pixels[256][256];
ב.

כתבו במחלקה Picture את הפעולה isBalancedPicture().

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

(במבחן ב-C#: IsBalancedPicture().)

(4 נקודות)
ג.

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

כתבו במחלקה Picture את הפעולה isBlackWhite(). הפעולה תבדוק אם התמונה היא "תמונת שחור לבן". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

(במבחן ב-C#: IsBlackWhite().)

(4 נקודות)
ד.

"מסגרת התמונה" היא השורה הראשונה, השורה האחרונה, העמודה הראשונה והעמודה האחרונה.

כתבו במחלקה Picture את הפעולה setWhiteBorder() . הפעולה תצבע את המסגרת של התמונה בלבן.

(במבחן ב-C#: SetWhiteBorder().)

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

סעיף א

תשובה:

return red == 0 && green == 0 && blue == 0;

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

לסעיפים הבאים נוסיף גם פעולת עזר דומה, `isWhite()`, שבודקת אם שלושת הרכיבים שווים 255 (צבע לבן).

Java:

// בתוך המחלקה Pixel
public boolean isBlack()
{
    return red == 0 && green == 0 && blue == 0;
}

// בתוך המחלקה Pixel – פעולת עזר: האם הפיקסל לבן
public boolean isWhite()
{
    return red == 255 && green == 255 && blue == 255;
}

C#:

// בתוך המחלקה Pixel
public bool IsBlack()
{
    return red == 0 && green == 0 && blue == 0;
}

// בתוך המחלקה Pixel – פעולת עזר: האם הפיקסל לבן
public bool IsWhite()
{
    return red == 255 && green == 255 && blue == 255;
}

תשובה: `isBlack()` מחזירה `red == 0 && green == 0 && blue == 0`.

סעיף ב

תשובה:

סופרים בלולאה כפולה פיקסלים לבנים (isWhite) ושחורים (isBlack) ומחזירים white == black.

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

הערה: בשאלון ההגדרה מודפסת כ-`Pixel[] pixels = new Pixels[256][256]`; הכוונה למערך דו-ממדי – ב-Java `Pixel[][] pixels = new Pixel[256][256]`, וב-C# `Pixel[,] pixels = new Pixel[256, 256]`.

1. מאתחלים `white = 0`, `black = 0`.

2. לכל פיקסל: אם הוא לבן (`isWhite()` – פעולת העזר מסעיף א') מגדילים את `white`; אחרת, אם הוא שחור, מגדילים את `black`. פיקסל צבעוני לא נספר באף מונה.

3. מחזירים `white == black`.

Java:

// בתוך המחלקה Picture
public boolean isBalancedPicture()
{
    int white = 0, black = 0;
    for (int i = 0; i < pixels.length; i++)
    {
        for (int j = 0; j < pixels[i].length; j++)
        {
            if (pixels[i][j].isWhite())
                white++;
            else if (pixels[i][j].isBlack())
                black++;
        }
    }
    return white == black;
}

C#:

// בתוך המחלקה Picture (ב-C#: private Pixel[,] pixels = new Pixel[256, 256];)
public bool IsBalancedPicture()
{
    int white = 0, black = 0;
    for (int i = 0; i < pixels.GetLength(0); i++)
    {
        for (int j = 0; j < pixels.GetLength(1); j++)
        {
            if (pixels[i, j].IsWhite())
                white++;
            else if (pixels[i, j].IsBlack())
                black++;
        }
    }
    return white == black;
}

סיבוכיות: מעבר אחד על 256⋅256256\cdot 256 הפיקסלים.

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

סעיף ג

תשובה:

לולאה כפולה; אם נמצא פיקסל שאינו שחור וגם אינו לבן – false מיד; בסוף – true.

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

1. עוברים על כל הפיקסלים בלולאה כפולה.

2. אם הפיקסל לא שחור וגם לא לבן – מחזירים false.

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

Java:

// בתוך המחלקה Picture
public boolean isBlackWhite()
{
    for (int i = 0; i < pixels.length; i++)
    {
        for (int j = 0; j < pixels[i].length; j++)
        {
            if (!pixels[i][j].isBlack() && !pixels[i][j].isWhite())
                return false;              // נמצא פיקסל צבעוני
        }
    }
    return true;
}

C#:

// בתוך המחלקה Picture
public bool IsBlackWhite()
{
    for (int i = 0; i < pixels.GetLength(0); i++)
    {
        for (int j = 0; j < pixels.GetLength(1); j++)
        {
            if (!pixels[i, j].IsBlack() && !pixels[i, j].IsWhite())
                return false;              // נמצא פיקסל צבעוני
        }
    }
    return true;
}

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

סעיף ד

תשובה:

לולאה k=0..255: צובעים בלבן (red=green=blue=255 בעזרת set) את pixels[0][k], pixels[255][k], pixels[k][0], pixels[k][255].

הרעיון: אין צורך לעבור על כל התמונה – מספיקה לולאה אחת על kk מ-0 עד 255, ובכל סיבוב צובעים ארבעה פיקסלים: אחד מכל צלע של המסגרת.

1. `last = pixels.length - 1`, כלומר 255 – מקום השורה האחרונה והעמודה האחרונה.

2. בסיבוב kk:

•`pixels[0][k]` – השורה הראשונה;

•`pixels[last][k]` – השורה האחרונה;

•`pixels[k][0]` – העמודה הראשונה;

•`pixels[k][last]` – העמודה האחרונה.

3. "צביעה בלבן" = קביעת שלושת הרכיבים ל-255 בעזרת פעולות ה-set של Pixel. כדי לא לחזור על שלוש פקודות ארבע פעמים, נכתוב פעולת עזר `setWhite(Pixel p)`.

4. הפינות (למשל `pixels[0][0]`) נצבעות פעמיים – אין בכך נזק. בסך הכול נצבעים 4⋅256−4=10204\cdot 256-4=1020 פיקסלים שונים.

Java:

// בתוך המחלקה Picture
public void setWhiteBorder()
{
    int last = pixels.length - 1;          // 255
    for (int k = 0; k <= last; k++)
    {
        setWhite(pixels[0][k]);            // השורה הראשונה
        setWhite(pixels[last][k]);         // השורה האחרונה
        setWhite(pixels[k][0]);            // העמודה הראשונה
        setWhite(pixels[k][last]);         // העמודה האחרונה
    }
}

// פעולת עזר: צביעת פיקסל בלבן
private static void setWhite(Pixel p)
{
    p.setRed(255);
    p.setGreen(255);
    p.setBlue(255);
}

C#:

// בתוך המחלקה Picture
public void SetWhiteBorder()
{
    int last = pixels.GetLength(0) - 1;    // 255
    for (int k = 0; k <= last; k++)
    {
        SetWhite(pixels[0, k]);            // השורה הראשונה
        SetWhite(pixels[last, k]);         // השורה האחרונה
        SetWhite(pixels[k, 0]);            // העמודה הראשונה
        SetWhite(pixels[k, last]);         // העמודה האחרונה
    }
}

// פעולת עזר: צביעת פיקסל בלבן
private static void SetWhite(Pixel p)
{
    p.SetRed(255);
    p.SetGreen(255);
    p.SetBlue(255);
}

תשובה: לולאה אחת על k=0..255k=0..255 שצובעת בלבן את `pixels[0][k]`, `pixels[255][k]`, `pixels[k][0]` ו-`pixels[k][255]`.

שאלה 12 · תכנון מחלקות לרשת מרכזים רפואיים

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

לכל מרכז שמורים הפרטים האלה:

•שם המרכז

•היישוב שבו נמצא המרכז (יכולים להיות כמה מרכזים באותו היישוב)

•מערך המרפאות במרכז (לב, אורולוגיה, אף אוזן גרון וכדו'). בכל מרכז יש לכל היותר חמש עשרה מרפאות שונות.

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

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

א.

כתבו את כותרת המחלקה, את התכונות ואת פעולות הבונות (בנאים) עבור כל אחת מהמחלקות:

•מרפאה Clinic

•מרכז Center

•רשת מרכזים Chain

(3 נקודות)
ב.

כתבו פעולה פנימית במחלקה Center המקבלת את שם המרפאה ובודקת אם המרפאה מטפלת בילדים. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false. אם המרפאה לא קיימת במרכז, הפעולה תחזיר ערך false.

(4 נקודות)
ג.

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

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

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

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

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

סעיף א

תשובה:

Clinic: name, phone, status (1 – מבוגרים, 2 – ילדים, 3 – שניהם) ובנאי עם שלושה פרמטרים; Center: name, city, Clinic[15] clinics, numClinics ובנאי (name, city); Chain: Center[40] centers ובנאי.

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

1. Clinic – מרפאה: שם (מחרוזת), טלפון (מחרוזת – מספר טלפון יכול להתחיל ב-0 ולהכיל מקף, ולכן לא מספר), וסטטוס. לסטטוס יש שלושה מצבים, ולכן נייצג אותו במספר שלם עם שלושה קבועים: `ADULTS = 1` (רק מבוגרים), `CHILDREN = 2` (רק ילדים), `BOTH = 3` (גם וגם). נוסיף פעולות get/set שנצטרך בסעיפים הבאים.

2. Center – מרכז: שם, יישוב, מערך מרפאות בגודל 15 (המספר המרבי), ומונה `numClinics` – כמה מרפאות קיימות בפועל. המרפאות שמורות ברצף בתאים 0 עד `numClinics-1`. הבנאי יוצר מרכז ריק (0 מרפאות); מרפאות מוסיפים בפעולה `addClinic` (סעיף ג').

3. Chain – רשת: מערך של 40 מרכזים. נניח שאחרי הבנייה כל 40 התאים מתמלאים במרכזים.

Java:

public class Clinic
{
    // ערכים אפשריים לסטטוס המרפאה
    public static final int ADULTS = 1;     // רק מבוגרים
    public static final int CHILDREN = 2;   // רק ילדים
    public static final int BOTH = 3;       // גם מבוגרים וגם ילדים

    private String name;     // שם המרפאה
    private String phone;    // מספר הטלפון לקביעת תור
    private int status;      // ADULTS / CHILDREN / BOTH

    public Clinic(String name, String phone, int status)
    {
        this.name = name;
        this.phone = phone;
        this.status = status;
    }

    public String getName() { return name; }
    public int getStatus() { return status; }
    public void setStatus(int status) { this.status = status; }
}

public class Center
{
    public static final int MAX_CLINICS = 15;

    private String name;         // שם המרכז
    private String city;         // היישוב
    private Clinic[] clinics;    // המרפאות במרכז
    private int numClinics;      // מספר המרפאות הקיימות בפועל

    public Center(String name, String city)
    {
        this.name = name;
        this.city = city;
        this.clinics = new Clinic[MAX_CLINICS];
        this.numClinics = 0;
    }
}

public class Chain
{
    public static final int NUM_CENTERS = 40;

    private Center[] centers;    // 40 המרכזים של הרשת

    public Chain()
    {
        this.centers = new Center[NUM_CENTERS];
    }
}

C#:

public class Clinic
{
    // ערכים אפשריים לסטטוס המרפאה
    public const int ADULTS = 1;     // רק מבוגרים
    public const int CHILDREN = 2;   // רק ילדים
    public const int BOTH = 3;       // גם מבוגרים וגם ילדים

    private string name;     // שם המרפאה
    private string phone;    // מספר הטלפון לקביעת תור
    private int status;      // ADULTS / CHILDREN / BOTH

    public Clinic(string name, string phone, int status)
    {
        this.name = name;
        this.phone = phone;
        this.status = status;
    }

    public string GetName() { return name; }
    public int GetStatus() { return status; }
    public void SetStatus(int status) { this.status = status; }
}

public class Center
{
    public const int MAX_CLINICS = 15;

    private string name;         // שם המרכז
    private string city;         // היישוב
    private Clinic[] clinics;    // המרפאות במרכז
    private int numClinics;      // מספר המרפאות הקיימות בפועל

    public Center(string name, string city)
    {
        this.name = name;
        this.city = city;
        this.clinics = new Clinic[MAX_CLINICS];
        this.numClinics = 0;
    }
}

public class Chain
{
    public const int NUM_CENTERS = 40;

    private Center[] centers;    // 40 המרכזים של הרשת

    public Chain()
    {
        this.centers = new Center[NUM_CENTERS];
    }
}

תשובה: המחלקות שלמעלה – Clinic (שם, טלפון, סטטוס), Center (שם, יישוב, מערך 15 מרפאות ומונה), Chain (מערך 40 מרכזים).

סעיף ב

תשובה:

פעולת עזר findClinic מחפשת את המרפאה לפי שם (או null); treatsChildren מחזירה false אם לא נמצאה, ואחרת status != ADULTS.

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

1. פעולת עזר `findClinic` (במחלקה Center). טענת כניסה: שם מרפאה. טענת יציאה: המרפאה בשם זה במרכז, או `null` אם אין כזו. הפעולה עוברת רק על התאים המלאים (0 עד `numClinics-1`) ומשווה שמות. נשתמש בה גם בסעיף ג'.

2. `treatsChildren`: אם `findClinic` החזירה `null` – המרפאה לא קיימת, ומחזירים false. אחרת מחזירים `status != ADULTS` (כלומר CHILDREN או BOTH).

Java:

// בתוך המחלקה Center – פעולת עזר: מחזירה את המרפאה בשם הנתון, או null אם אין כזו
public Clinic findClinic(String clinicName)
{
    for (int i = 0; i < numClinics; i++)
    {
        if (clinics[i].getName().equals(clinicName))
            return clinics[i];
    }
    return null;
}

// בתוך המחלקה Center
public boolean treatsChildren(String clinicName)
{
    Clinic c = findClinic(clinicName);
    if (c == null)
        return false;                          // המרפאה לא קיימת במרכז
    return c.getStatus() != Clinic.ADULTS;     // CHILDREN או BOTH
}

C#:

// בתוך המחלקה Center – פעולת עזר: מחזירה את המרפאה בשם הנתון, או null אם אין כזו
public Clinic FindClinic(string clinicName)
{
    for (int i = 0; i < numClinics; i++)
    {
        if (clinics[i].GetName() == clinicName)
            return clinics[i];
    }
    return null;
}

// בתוך המחלקה Center
public bool TreatsChildren(string clinicName)
{
    Clinic c = FindClinic(clinicName);
    if (c == null)
        return false;                          // המרפאה לא קיימת במרכז
    return c.GetStatus() != Clinic.ADULTS;     // CHILDREN או BOTH
}

תשובה: `treatsChildren(clinicName)` מחזירה false אם המרפאה לא קיימת במרכז, ואחרת true אם הסטטוס שלה אינו "רק מבוגרים".

סעיף ג

תשובה:

לכל מרכז: eyes = findClinic("עיניים"); אם null – addClinic(new Clinic("עיניים", "", BOTH)) (נכשלת בשקט אם יש 15 מרפאות); אם status == ADULTS – setStatus(BOTH); אחרת לא משנים.

הרעיון: עוברים על כל 40 המרכזים, ולכל מרכז מבחינים בין שלושה מצבים של מרפאת ה"עיניים" שלו.

1. פעולת עזר `addClinic` (במחלקה Center). טענת כניסה: מרפאה. טענת יציאה: אם יש במרכז פחות מ-15 מרפאות – המרפאה נוספת בתא `numClinics`, המונה גדל, ומוחזר true; אחרת לא נוסף דבר ומוחזר false.

2. `updateEyeClinics` (במחלקה Chain). לכל מרכז מחפשים את מרפאת "עיניים" בעזרת `findClinic` מסעיף ב':

•אין מרפאת עיניים: פותחים מרפאה חדשה שמטפלת גם בילדים (סטטוס BOTH). אם יש כבר 15 מרפאות, `addClinic` לא מוסיפה דבר – כפי שנדרש ב"שימו לב".

•יש מרפאה שמטפלת רק במבוגרים: משנים את הסטטוס ל-BOTH ולא פותחים מרפאה נוספת.

•יש מרפאה שכבר מטפלת בילדים (CHILDREN או BOTH): לא עושים דבר.

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

Java:

// בתוך המחלקה Center – פעולת עזר: הוספת מרפאה אם יש מקום. מחזירה true אם נוספה
public boolean addClinic(Clinic c)
{
    if (numClinics == MAX_CLINICS)
        return false;                          // כבר יש 15 מרפאות
    clinics[numClinics] = c;
    numClinics++;
    return true;
}

// בתוך המחלקה Chain
public void updateEyeClinics()
{
    for (int i = 0; i < centers.length; i++)
    {
        Clinic eyes = centers[i].findClinic("עיניים");
        if (eyes == null)
        {
            // אין מרפאת עיניים: פותחים מרפאה חדשה שמטפלת גם בילדים (אם יש מקום)
            centers[i].addClinic(new Clinic("עיניים", "", Clinic.BOTH));
        }
        else if (eyes.getStatus() == Clinic.ADULTS)
        {
            // יש מרפאה למבוגרים בלבד: משנים את הסטטוס כך שתטפל גם בילדים
            eyes.setStatus(Clinic.BOTH);
        }
        // אחרת – המרפאה כבר מטפלת בילדים, ואין מה לעשות
    }
}

C#:

// בתוך המחלקה Center – פעולת עזר: הוספת מרפאה אם יש מקום. מחזירה true אם נוספה
public bool AddClinic(Clinic c)
{
    if (numClinics == MAX_CLINICS)
        return false;                          // כבר יש 15 מרפאות
    clinics[numClinics] = c;
    numClinics++;
    return true;
}

// בתוך המחלקה Chain
public void UpdateEyeClinics()
{
    for (int i = 0; i < centers.Length; i++)
    {
        Clinic eyes = centers[i].FindClinic("עיניים");
        if (eyes == null)
        {
            // אין מרפאת עיניים: פותחים מרפאה חדשה שמטפלת גם בילדים (אם יש מקום)
            centers[i].AddClinic(new Clinic("עיניים", "", Clinic.BOTH));
        }
        else if (eyes.GetStatus() == Clinic.ADULTS)
        {
            // יש מרפאה למבוגרים בלבד: משנים את הסטטוס כך שתטפל גם בילדים
            eyes.SetStatus(Clinic.BOTH);
        }
        // אחרת – המרפאה כבר מטפלת בילדים, ואין מה לעשות
    }
}

תשובה: הפעולה שלמעלה – במרכז בלי מרפאת עיניים נוספת מרפאה חדשה בסטטוס "גם וגם" (אם יש פחות מ-15 מרפאות); מרפאת עיניים למבוגרים בלבד מקבלת סטטוס "גם וגם"; מרפאה שכבר מטפלת בילדים לא משתנה.

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

נתונות פעולות רקורסיביות mystery ו-secret:

Java:

public static int mystery (String s1, String s2) {
    if(s1.length() == 0 && s2.length() == 0) return 0;
    if(s1.length() == 0) return -1;
    if(s2.length() == 0) return 1;
    if(s1.charAt(0) < s2.charAt(0)) return -1;
    if(s1.charAt(0) > s2.charAt(0)) return 1;
    return mystery (s1.substring(1), s2.substring(1));
}

public static String[] secret(String[] arr, String s){
     String[] temp=new String[arr.length];
     secretHelp(arr, temp, s, 0,0, temp.length-1);
     return temp;
}

private static void secretHelp (String[] arr, String[] temp,
                          String s, int i, int left, int right)
{
    if(i < arr.length)
     {
      if(mystery(arr[i], s) < 0)
        {
             temp[left] = arr[i];
             secretHelp (arr, temp, s, i+1, left+1, right);
        }
       else
        {
             temp[right] = arr[i];
             secretHelp (arr, temp, s, i+1, left, right-1);
        }
     }
}

C#:

public static int Mystery (string s1, string s2) {
    if(s1.Length == 0 && s2.Length == 0) return 0;
    if(s1.Length == 0) return -1;
    if(s2.Length == 0) return 1;
    if(s1[0] < s2[0]) return -1;
    if(s1[0] > s2[0]) return 1;
    return Mystery (s1.Substring(1), s2.Substring(1));
}

public static string[] Secret(string[] arr, string s){
     string[] temp=new string[arr.Length];
     SecretHelp(arr, temp, s, 0,0, temp.Length-1);
     return temp;
}

private static void SecretHelp (string[] arr, string[] temp,
                          string s, int i, int left, int right)
{
    if(i < arr.Length)
     {
      if(Mystery(arr[i], s) < 0)
        {
             temp[left] = arr[i];
             SecretHelp (arr, temp, s, i+1, left+1, right);
        }
       else
        {
             temp[right] = arr[i];
             SecretHelp (arr, temp, s, i+1, left, right-1);
        }
     }
}

(במבחן ב-C# שמות הפעולות Mystery, Secret ו-SecretHelp.)

א.

עקבו אחרי זימון mystery("HELLO","HELP") ורשמו את תוצאת הזימון.

יש להראות מעקב!

(3 נקודות)
ב.

מה מבצעת הפעולה mystery(s1, s2) עבור שתי מחרוזות s1, s2?

(1 נקודות)
ג.

נתון מערך מחרוזות:

Java:

String[] arr = {"HELLO", "WORLD", "GOOD", "DAY","FOR","TEST"}

C#:

string[] arr = {"HELLO", "WORLD", "GOOD", "DAY","FOR","TEST"}

עקבו אחרי הזימון secret(arr, "JAVA") ורשמו את תוצאות הזימון.

יש להראות מעקב אחרי הפעולה secret, אין צורך במעקב אחרי הפעולה mystery.

(4 נקודות)
ד.

מה מבצעת הפעולה secret(arr, s) עבור מערך מחרוזות arr ומחרוזת s.

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

סעיף א

תשובה:

-1

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

קריאהs1s2בדיקהערך מוחזר
1"HELLO""HELP"'H' == 'H' – קריאה רקורסיבית-1
2"ELLO""ELP"'E' == 'E' – קריאה רקורסיבית-1
3"LLO""LP"'L' == 'L' – קריאה רקורסיבית-1
4"LO""P"'L' < 'P'-1

בקריאה 4 משווים `'L'` ל-`'P'`; `'L'` קודם ל-`'P'` (קוד התו קטן יותר), ולכן מוחזר 1-, והערך עובר דרך כל הקריאות חזרה.

תשובה: `mystery("HELLO","HELP")` מחזירה 1-.

סעיף ב

תשובה:

משווה את המחרוזות לפי סדר מילוני: 1- אם s1 קודמת ל-s2, 0 אם הן שוות, 1 אם s1 באה אחרי s2.

הפעולה משווה את המחרוזות תו אחרי תו מההתחלה. בתו הראשון שבו הן נבדלות, היא מחזירה 1- אם התו של s1 קטן (קודם) ו-1 אם הוא גדול. אם אחת המחרוזות נגמרה קודם, היא תחילית של השנייה ולכן קודמת לה: אם s1 נגמרה – מוחזר 1-, אם s2 נגמרה – מוחזר 1. אם שתיהן נגמרו יחד – הן זהות, ומוחזר 0.

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

סעיף ג

תשובה:

{"HELLO", "GOOD", "DAY", "FOR", "TEST", "WORLD"}

`secret` יוצרת מערך `temp` באורך 6 וקוראת ל-`secretHelp` עם `i = 0`, `left = 0`, `right = 5`. בכל קריאה, לפי הסעיף הקודם, `mystery(arr[i], "JAVA") < 0` פירושו ש-`arr[i]` קודמת ל-"JAVA" בסדר מילוני (משווים את האות הראשונה ל-`'J'`):

•מחרוזת קודמת ל-"JAVA" נכתבת במקום `left` מצד שמאל, ו-`left` גדל;

•אחרת היא נכתבת במקום `right` מצד ימין, ו-`right` קטן.

קריאהileftrightarr[i]mystery(arr[i], "JAVA")פעולהtemp אחרי הקריאה
1005"HELLO"-1temp[0] = "HELLO"{HELLO, –, –, –, –, –}
2115"WORLD"1temp[5] = "WORLD"{HELLO, –, –, –, –, WORLD}
3214"GOOD"-1temp[1] = "GOOD"{HELLO, GOOD, –, –, –, WORLD}
4324"DAY"-1temp[2] = "DAY"{HELLO, GOOD, DAY, –, –, WORLD}
5434"FOR"-1temp[3] = "FOR"{HELLO, GOOD, DAY, FOR, –, WORLD}
6544"TEST"1temp[4] = "TEST"{HELLO, GOOD, DAY, FOR, TEST, WORLD}
7643––i=6i=6 – עצירה–

תשובה: `secret(arr, "JAVA")` מחזירה את המערך `{"HELLO", "GOOD", "DAY", "FOR", "TEST", "WORLD"}`.

סעיף ד

תשובה:

מחזירה מערך חדש: בתחילתו המחרוזות הקודמות ל-s בסדר מילוני (בסדר הופעתן), ובסופו המחרוזות שאינן קודמות ל-s (שוות או באות אחריו) בסדר הפוך להופעתן.

הפעולה עוברת ברקורסיה על איברי `arr` לפי הסדר (`i` גדל ב-1 בכל קריאה) ומחלקת אותם לשתי קבוצות לפי ההשוואה המילונית ל-s:

1. מחרוזות קודמות ל-s נכתבות משמאל לימין מתחילת `temp` – ולכן נשמר ביניהן הסדר המקורי.

2. מחרוזות שוות ל-s או באות אחריה נכתבות מימין לשמאל מסוף `temp` – ולכן הן מופיעות בסדר הפוך לסדר שבו הופיעו ב-`arr`.

3. בכל קריאה ממלאים תא אחד, ולכן אחרי `arr.length` קריאות `temp` מלא; המערך המקורי לא משתנה.

תשובה: הפעולה מחזירה מערך חדש שבו מופיעות קודם כל המחרוזות שקודמות ל-s בסדר מילוני (בסדר המקורי שלהן), ואחריהן כל המחרוזות השוות ל-s או באות אחריה (בסדר הפוך לסדר המקורי).

שאלה 14 · מערך דו-ממדי מסודר לפי ספרות העמודות

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

מערך דו-ממדי של מספרים שלמים נקרא "מערך מסודר" אם הוא עונה על שלושת התנאים האלה:

•מספר השורות במערך שווה למספר העמודות (מערך ריבועי).

•כל האיברים במערך הם מספרים חיוביים.

•כל איבר בעמודה 0 כולל את הספרה 0, כל איבר בעמודה 1 כולל את הספרה 1 וכן הלאה.

לדוגמה, המערך שלפניכם הוא "מערך מסודר":

שורה עמודה0123
010312122031
16051134213
2701521305
31003601200203
א.

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

אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

(8 נקודות)
ב.

מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.

רמז: מומלץ לכתוב פעולות עזר!

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

סעיף א

תשובה:

בודקים שכל שורה באורך n (ריבועי); לכל mat[i][j] בודקים שהוא חיובי ושהספרה j מופיעה בו (פעולת עזר hasDigit בעזרת %10 ו-/10); בכישלון – false, בסוף – true.

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

1. פעולת עזר `hasDigit(num, digit)`. טענת כניסה: מספר חיובי `num` וספרה `digit`. טענת יציאה: true אם `digit` מופיעה בין ספרות `num`. מפרקים את המספר: `num % 10` היא ספרת האחדות; אם היא שווה ל-`digit` מחזירים true, אחרת מורידים אותה (`num /= 10`) וממשיכים עד שהמספר מתאפס. לדוגמה, `hasDigit(1220, 2)`: ספרת האחדות 0, אחר כך 2 – true.

2. מערך ריבועי: מספר השורות הוא nn = `mat.length`. ב-Java כל שורה היא מערך נפרד, ולכן בודקים שאורך כל שורה `mat[i].length` שווה ל-nn. ב-C# מערך דו-ממדי `int[,]` הוא מלבני, ולכן מספיק להשוות `GetLength(1)` ל-`GetLength(0)`.

3. מספרים חיוביים: אם `mat[i][j] <= 0` – false. (הבדיקה גם מבטיחה ש-`hasDigit` תקבל מספר חיובי.)

4. הספרה של העמודה: איבר בעמודה jj חייב לכלול את הספרה jj: אם `!hasDigit(mat[i][j], j)` – false. במערך עם יותר מ-10 עמודות, בעמודה 10 ומעלה אין "ספרה" מתאימה; `hasDigit` מחזירה שם false (ספרה בודדת לעולם אינה שווה ל-10), ולכן מערך כזה אינו מסודר.

5. אם כל הבדיקות עברו – מחזירים true.

Java:

// פעולת עזר: האם הספרה digit מופיעה במספר החיובי num
public static boolean hasDigit(int num, int digit)
{
    while (num > 0)
    {
        if (num % 10 == digit)
            return true;
        num /= 10;
    }
    return false;
}

public static boolean isOrdered(int[][] mat)
{
    int n = mat.length;
    for (int i = 0; i < n; i++)
    {
        if (mat[i].length != n)             // תנאי 1: מערך ריבועי
            return false;
        for (int j = 0; j < n; j++)
        {
            if (mat[i][j] <= 0)             // תנאי 2: מספר חיובי
                return false;
            if (!hasDigit(mat[i][j], j))    // תנאי 3: האיבר בעמודה j מכיל את הספרה j
                return false;
        }
    }
    return true;
}

C#:

// פעולת עזר: האם הספרה digit מופיעה במספר החיובי num
public static bool HasDigit(int num, int digit)
{
    while (num > 0)
    {
        if (num % 10 == digit)
            return true;
        num /= 10;
    }
    return false;
}

public static bool IsOrdered(int[,] mat)
{
    int n = mat.GetLength(0);
    if (mat.GetLength(1) != n)              // תנאי 1: מערך ריבועי
        return false;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mat[i, j] <= 0)             // תנאי 2: מספר חיובי
                return false;
            if (!HasDigit(mat[i, j], j))    // תנאי 3: האיבר בעמודה j מכיל את הספרה j
                return false;
        }
    }
    return true;
}

בדיקה על הדוגמה: המערך 4×44\times 4, כל האיברים חיוביים, ובכל עמודה jj כל איבר מכיל את הספרה jj (למשל בעמודה 2: 1220, 1342, 21, 200) – מוחזר true. אם מחליפים את 15 (שורה 2, עמודה 1) ב-25 – אין בו הספרה 1, ומוחזר false.

תשובה: הפעולה שלמעלה – false אם המערך לא ריבועי, או אם יש איבר לא חיובי, או איבר בעמודה jj שאין בו הספרה jj; אחרת true.

סעיף ב

תשובה:

O(n²) עבור מערך n×n (בכל אחד מ-n² האיברים בדיקת ספרות באורך מספר הספרות d, כלומר O(n²·d), ו-d חסום – לכל היותר 10 ספרות ל-int).

נסמן ב-nn את מספר השורות (והעמודות) של המערך.

1. בדיקת הריבועיות (ב-Java) – מעבר אחד על nn השורות: O(n)O(n).

2. הלולאה הכפולה עוברת על כל n⋅n=n2n\cdot n=n^2 האיברים (במקרה הגרוע – מערך מסודר, שבו לא יוצאים מוקדם).

3. לכל איבר קוראים ל-`hasDigit`, שעוברת על ספרות המספר. אם נסמן ב-dd את מספר הספרות המרבי של איבר, זו עבודה של O(d)O(d). ב-int יש לכל היותר 10 ספרות, כך ש-dd חסום בקבוע.

4. בסך הכול O(n2⋅d)O(n^2\cdot d), וכיוון ש-d≤10d\le 10 הוא קבוע – O(n2)O(n^2), כלומר לינארי במספר האיברים במערך.

תשובה: O(n2)O(n^2) – לולאה כפולה על n2n^2 האיברים, ולכל איבר בדיקת ספרות שאורכה חסום בקבוע (מספר הספרות, O(n2⋅d)O(n^2\cdot d)).

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

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

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