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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 1 · הצפנת מחרוזת בשיטת שלושה שלבים

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

לשיטה שלושה שלבים:

•הסרת רווחים מהמסר המקורי.

•החלפת סדר התווים בכל זוג תווים צמודים (אם מספר התווים אי-זוגי, התו האחרון נשאר ללא שינוי).

•כתיבת התווים מהסוף להתחלה (הפיכת סדר התווים).

לדוגמה:

אם הטקסט המקורי היה "HelloWorld!" אז הטקסט המוצפן יהיה "!ldoroWllHe".

Hello World! → HelloWorld! → eHllWorodl! → !ldoroWllHe

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

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

פתרון

תשובה:

פעולה encrypt: מסירים רווחים, מחליפים כל זוג תווים צמודים (תו אחרון בודד נשאר), והופכים את המחרוזת; עבור "Hello World!" מתקבל "!ldoroWllHe".

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

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

2. החלפת זוגות – עוברים על `noSpaces` בקפיצות של 2: עבור הזוג שמתחיל במקום `i` מוסיפים קודם את התו `i+1` ואחריו את התו `i`. הלולאה רצה כל עוד יש זוג שלם (`i+1` קיים). אם בסוף נשאר תו בודד (מספר תווים אי-זוגי) – מוסיפים אותו כמו שהוא.

3. היפוך – עוברים על המחרוזת מהתו האחרון לראשון ובונים את התוצאה.

מעקב על הדוגמה: "Hello World!" → אחרי הסרת הרווח "HelloWorld!" (11 תווים) → הזוגות He, ll, oW, or, ld הופכים ל-eH, ll, Wo, ro, dl והתו "!" נשאר: "eHllWorodl!" → אחרי ההיפוך "!ldoroWllHe", כמו בדוגמה.

Java:

// הצפנת "סטופיד": הסרת רווחים, החלפת זוגות, היפוך
public static String encrypt(String message)
{
    // שלב 1: הסרת הרווחים
    String noSpaces = "";
    for (int i = 0; i < message.length(); i++)
    {
        if (message.charAt(i) != ' ')
            noSpaces = noSpaces + message.charAt(i);
    }

    // שלב 2: החלפת סדר התווים בכל זוג צמוד
    String swapped = "";
    int i = 0;
    while (i + 1 < noSpaces.length())
    {
        swapped = swapped + noSpaces.charAt(i + 1) + noSpaces.charAt(i);
        i += 2;
    }
    if (i < noSpaces.length())          // מספר תווים אי-זוגי: התו האחרון נשאר
        swapped = swapped + noSpaces.charAt(i);

    // שלב 3: היפוך סדר התווים
    String result = "";
    for (int k = swapped.length() - 1; k >= 0; k--)
        result = result + swapped.charAt(k);
    return result;
}

C#:

// הצפנת "סטופיד": הסרת רווחים, החלפת זוגות, היפוך
public static string Encrypt(string message)
{
    // שלב 1: הסרת הרווחים
    string noSpaces = "";
    for (int i = 0; i < message.Length; i++)
    {
        if (message[i] != ' ')
            noSpaces = noSpaces + message[i];
    }

    // שלב 2: החלפת סדר התווים בכל זוג צמוד
    string swapped = "";
    int j = 0;
    while (j + 1 < noSpaces.Length)
    {
        swapped = swapped + noSpaces[j + 1] + noSpaces[j];
        j += 2;
    }
    if (j < noSpaces.Length)            // מספר תווים אי-זוגי: התו האחרון נשאר
        swapped = swapped + noSpaces[j];

    // שלב 3: היפוך סדר התווים
    string result = "";
    for (int k = swapped.Length - 1; k >= 0; k--)
        result = result + swapped[k];
    return result;
}

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

תשובה: הפעולה שלמעלה; עבור "Hello World!" היא מחזירה "!ldoroWllHe".

שאלה 2 · מציאת נקודת איזון של מכפלות במערך

נתון מערך arr בגודל n המכיל מספרים שלמים שונים זה מזה.

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

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

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

פתרון

תשובה:

לכל k מ-0 והלאה מחשבים את מכפלת האיברים שמשמאל (אתחול ל-1) ואת מכפלת האיברים שמימין; ה-k הראשון שבו הן שוות מוחזר, ואם אין – −1-1.

הרעיון: בודקים את האינדקסים לפי הסדר משמאל לימין. לכל אינדקס `k` מחשבים שתי מכפלות – של האיברים שבמקומות 0..k−10..k-1 ושל האיברים שבמקומות k+1..n−1k+1..n-1 – ומשווים ביניהן. האינדקס הראשון שבו הן שוות הוא נקודת האיזון הראשונה מצד שמאל, ולכן מחזירים אותו מיד. אם הלולאה הסתיימה בלי החזרה – אין נקודת איזון ומחזירים −1-1.

1. את שתי המכפלות מאתחלים ל-1 (האיבר הניטרלי של הכפל) ולא ל-0. כך, עבור k=0k=0 אין איברים משמאל והמכפלה השמאלית היא 1, ועבור k=n−1k=n-1 המכפלה הימנית היא 1.

2. לולאה פנימית אחת עוברת על i=0..k−1i=0..k-1 ולולאה שנייה על i=k+1..n−1i=k+1..n-1 – לא נוגעים ב-`arr[k]` עצמו ולא חורגים מגבולות המערך.

3. מכפלות גדלות מהר, לכן הן נשמרות במשתנה מטיפוס `long`.

לדוגמה, עבור המערך {2, 3, 7, 6, 1}: ב-k=0k=0: 11 מול 3⋅7⋅6⋅1=1263\cdot7\cdot6\cdot1=126; ב-k=1k=1: 22 מול 7⋅6⋅1=427\cdot6\cdot1=42; ב-k=2k=2: 2⋅3=62\cdot3=6 מול 6⋅1=66\cdot1=6 – שוות, ולכן מוחזר 2.

Java:

// מחזירה את נקודת האיזון הראשונה מצד שמאל, או -1 אם אין
public static int balancePoint(int[] arr)
{
    for (int k = 0; k < arr.length; k++)
    {
        long left = 1;                      // מכפלת האיברים משמאל ל-k
        for (int i = 0; i < k; i++)
            left *= arr[i];

        long right = 1;                     // מכפלת האיברים מימין ל-k
        for (int i = k + 1; i < arr.length; i++)
            right *= arr[i];

        if (left == right)
            return k;
    }
    return -1;
}

C#:

// מחזירה את נקודת האיזון הראשונה מצד שמאל, או -1 אם אין
public static int BalancePoint(int[] arr)
{
    for (int k = 0; k < arr.Length; k++)
    {
        long left = 1;                      // מכפלת האיברים משמאל ל-k
        for (int i = 0; i < k; i++)
            left *= arr[i];

        long right = 1;                     // מכפלת האיברים מימין ל-k
        for (int i = k + 1; i < arr.Length; i++)
            right *= arr[i];

        if (left == right)
            return k;
    }
    return -1;
}

סיבוכיות הזמן O(n2)O(n^2): לכל אחד מ-nn האינדקסים עוברים על כל שאר המערך.

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

שאלה 3 · מעקב: אורך הרצף הארוך של זוגיים

נתונה הפעולה what:

Java:

public static int what(int[] arr)
{
    int c = 0;
    int m = 0;
    for(int i = 0; i<arr.length; i++)
    {
        if(arr[i]%2 == 0)
        {
            c++;
        }
        else
        {
            if(c > m)
            {
                m = c;
            }
            c = 0;
        }
    }
    if(c > m)
        return c;
    return m;
}

C#:

public static int What(int[] arr)
{
    int c = 0;
    int m = 0;
    for(int i = 0; i<arr.Length; i++)
    {
        if(arr[i]%2 == 0)
        {
            c++;
        }
        else
        {
            if(c > m)
            {
                m = c;
            }
            c = 0;
        }
    }
    if(c > m)
        return c;
    return m;
}
א.

נתון מערך arr = {12,6,3,17,4,5, 2, 8, 10, 13}.

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

(4 נקודות)
ב.

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

(3 נקודות)
ג.

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

(3 נקודות)
ד.

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

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

סעיף א

תשובה:

what(arr) מחזירה 3.

עוקבים אחרי המשתנים: `c` סופר כמה מספרים זוגיים רצופים ראינו עד עכשיו, ו-`m` שומר את הרצף הארוך ביותר שהסתיים. כשמגיע מספר אי-זוגי – הרצף הנוכחי נגמר: אם הוא ארוך מ-`m` מעדכנים את `m`, ומאפסים את `c`.

צעד iarr[i]זוגי?פעולהcm
התחלה–––00
012כןc++10
16כןc++20
23לא2>0 ולכן m=2, איפוס c02
317לא0>2 לא, איפוס c02
44כןc++12
55לא1>2 לא, איפוס c02
62כןc++12
78כןc++22
810כןc++32
913לא3>2 ולכן m=3, איפוס c03

אחרי הלולאה: `c > m` כלומר 0>30>3 – לא, ולכן מוחזר `m`, שערכו 3.

תשובה: what(arr) מחזירה 3.

סעיף ב

תשובה:

לדוגמה {2, 4, 6, 8, 3, 1}.

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

לדוגמה {2, 4, 6, 8, 3, 1}: ארבעת הזוגיים הראשונים מעלים את `c` ל-4; ב-3 (אי-זוגי) 4>04>0 ולכן `m`=4 ו-`c`=0; ב-1 `c` נשאר 0. בסוף 0>40>4 לא – מוחזר 4.

תשובה: לדוגמה arr = {2, 4, 6, 8, 3, 1}.

סעיף ג

תשובה:

0; לדוגמה {1, 3, 5, 7, 9, 11}.

המשתנים `c` ו-`m` מתחילים ב-0, `c` רק גדל או מתאפס ל-0, ו-`m` מקבל רק ערכים של `c` הגדולים ממנו – לכן שניהם לעולם אינם שליליים, והערך המוחזר הוא לפחות 0.

הערך 0 מתקבל כשאין במערך אף מספר זוגי: `c` לא גדל אף פעם, `m` נשאר 0, ומוחזר 0. לדוגמה {1, 3, 5, 7, 9, 11}.

תשובה: הערך הקטן ביותר הוא 0, למשל עבור arr = {1, 3, 5, 7, 9, 11}.

סעיף ד

תשובה:

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

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

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

שאלה 4 · מחלקת עובד: חישוב שכר וממוצע

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

•עבור כל אחת מ-160 שעות העבודה הראשונות פועל מקבל 80 ₪ ומהנדס – 150 ₪.

•עבור כל שעה נוספת מקבל העובד תוספת של 70 ₪.

נתונה מחלקה:

Java:

class Employee
{
    private String id;// ת.ז. של עובד
    private int status; // 1- מהנדס, 2- פועל
    private int hours; // מספר שעות עבודה בחודש
    public Employee (String id, int st) //פעולה בונה
    {
        this.id=id;
        this.status=st;
        this.hours=0;
    }
}

C#:

class Employee
{
    private string id;// ת.ז. של עובד
    private int status; // 1- מהנדס, 2- פועל
    private int hours; // מספר שעות עבודה בחודש
    public Employee (string id, int st) //פעולה בונה
    {
        this.id=id;
        this.status=st;
        this.hours=0;
    }
}

במחלקה הוגדרו כל הפעולות set ו-get וגם הפעולה toString().

א.

כתבו במחלקה Employee פעולה getSalary() לחישוב המשכורת החודשית של עובד.

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

Java:

public int getSalary ()

C#:

public int GetSalary ()
(3 נקודות)
ב.

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

השלימו את החסר:

Java:

Scanner in=new Scanner(System.in);
int s = 0;
String n =    __________(1)____________;
int t =  __________(2)____________;

Employee emp = __________(3)____;
for (int i = 1; i<25;  i++)
{
    int a=in.nextInt();
    int b=in.nextInt();
    s=   __________(4)___;
}
emp.setHours(____(5)__);
System.out.println(________(6)______);

C#:

int s=0;
string n=     __________(1)____________;
int t=   __________(2)____________;

Employee emp = __________(3)____;
for (int i=1; i<25;i++)
{
    int a=int.Parse(Console.ReadLine());
    int b=int.Parse(Console.ReadLine());
    s=   __________(4)___;
}
emp.SetHours(____(5)__);
Console.WriteLine(________(6)______);
(3 נקודות)
ג.

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

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

סעיף א

תשובה:

תעריף 150 למהנדס (status=1) ו-80 לפועל; אם hours ≤ 160 – hours·rate, אחרת 160·rate + (hours−160)·70.

נתון: status=1 – מהנדס, status=2 – פועל; hours – שעות העבודה בחודש. מבוקש: המשכורת החודשית.

1. בוחרים את התעריף לשעה ב-160 השעות הראשונות לפי הסטטוס: 150 ₪ למהנדס, 80 ₪ לפועל.

2. אם העובד עבד עד 160 שעות – המשכורת היא hours⋅ratehours\cdot rate.

3. אחרת – 160 השעות הראשונות מחושבות לפי התעריף, וכל שעה נוספת מזכה ב-70 ₪: 160⋅rate+(hours−160)⋅70160\cdot rate + (hours-160)\cdot 70.

לדוגמה, פועל שעבד 200 שעות: 160⋅80+40⋅70=12800+2800=15600160\cdot 80 + 40\cdot 70 = 12800 + 2800 = 15600 ₪; מהנדס שעבד 170 שעות: 160⋅150+10⋅70=24700160\cdot150 + 10\cdot70 = 24700 ₪.

Java:

// סעיף א: המשכורת החודשית
public int getSalary()
{
    int rate;                          // תעריף לשעה ב-160 השעות הראשונות
    if (this.status == 1)
        rate = 150;                    // מהנדס
    else
        rate = 80;                     // פועל

    if (this.hours <= 160)
        return this.hours * rate;
    return 160 * rate + (this.hours - 160) * 70;
}

C#:

public int GetSalary()
{
    int rate;                          // תעריף לשעה ב-160 השעות הראשונות
    if (this.status == 1)
        rate = 150;                    // מהנדס
    else
        rate = 80;                     // פועל

    if (this.hours <= 160)
        return this.hours * rate;
    return 160 * rate + (this.hours - 160) * 70;
}

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

סעיף ב

תשובה:

(1) in.next() (2) in.nextInt() (3) new Employee(n, t) (4) s + (b - a) (5) s (6) emp.getSalary(); ב-C#: Console.ReadLine(), int.Parse(Console.ReadLine()), ..., emp.GetSalary().

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

1. `n` היא מחרוזת – תעודת הזהות של העובד: `in.next()` (ב-C#: `Console.ReadLine()`).

2. `t` הוא מספר שלם – הסטטוס (1 מהנדס, 2 פועל): `in.nextInt()` (ב-C#: `int.Parse(Console.ReadLine())`).

3. יוצרים את העובד בעזרת הפעולה הבונה: `new Employee(n, t)`.

4. בכל יום `a` היא שעת ההתחלה ו-`b` שעת הסיום, ולכן העובד עבד b−ab-a שעות; צוברים: `s + (b - a)`.

5. אחרי הלולאה `s` הוא סך השעות בחודש: `emp.setHours(s)` (ב-C#: `emp.SetHours(s)`).

6. מדפיסים את השכר שחושב בסעיף א: `emp.getSalary()` (ב-C#: `emp.GetSalary()`).

הערה: בלולאה כפי שהיא כתובה בשאלה, `for (int i = 1; i<25; i++)`, מתבצעות 24 חזרות בלבד. כדי לקלוט את כל 25 ימי העבודה יש לכתוב `i <= 25`, כמו בקטע המלא:

Java:

Scanner in = new Scanner(System.in);
int s = 0;
String n = in.next();                          // (1)
int t = in.nextInt();                          // (2)

Employee emp = new Employee(n, t);             // (3)
for (int i = 1; i <= 25; i++)
{
    int a = in.nextInt();
    int b = in.nextInt();
    s = s + (b - a);                           // (4)
}
emp.setHours(s);                               // (5)
System.out.println(emp.getSalary());           // (6)

C#:

int s = 0;
string n = Console.ReadLine();                    // (1)
int t = int.Parse(Console.ReadLine());            // (2)

Employee emp = new Employee(n, t);                // (3)
for (int i = 1; i <= 25; i++)
{
    int a = int.Parse(Console.ReadLine());
    int b = int.Parse(Console.ReadLine());
    s = s + (b - a);                              // (4)
}
emp.SetHours(s);                                  // (5)
Console.WriteLine(emp.GetSalary());               // (6)

תשובה: (1) `in.next()`; (2) `in.nextInt()`; (3) `new Employee(n, t)`; (4) `s + (b - a)`; (5) `s`; (6) `emp.getSalary()`.

סעיף ג

תשובה:

מעבר ראשון: סכום ומספר המהנדסים (status=1) → ממוצע; מעבר שני: הדפסת getId() של כל פועל (status=2) ש-getSalary() שלו גדול מהממוצע.

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

1. ממוצע המהנדסים: לכל עובד שה-`getStatus()` שלו 1 מוסיפים את `getSalary()` לסכום ומגדילים את המונה. הממוצע הוא הסכום חלקי המונה – מחלקים כ-`double` כדי לא לאבד את החלק השברי.

2. אם אין אף מהנדס – אין ממוצע (חלוקה ב-0), ולכן מדפיסים הודעה ומסיימים.

3. הדפסה: לכל עובד שה-`getStatus()` שלו 2 (פועל) ו-`getSalary()` שלו גדול מהממוצע – מדפיסים את `getId()`.

הפנייה לתכונות היא דרך פעולות ה-get, כי התכונות פרטיות (private).

Java:

// סעיף ג
public static void printWorkers(Employee[] arr)
{
    int sum = 0, count = 0;
    for (int i = 0; i < arr.length; i++)       // ממוצע המשכורות של המהנדסים
    {
        if (arr[i].getStatus() == 1)
        {
            sum += arr[i].getSalary();
            count++;
        }
    }
    if (count == 0)
    {
        System.out.println("There are no engineers");
        return;
    }
    double avg = (double) sum / count;

    for (int i = 0; i < arr.length; i++)       // פועלים שמשכורתם גבוהה מהממוצע
    {
        if (arr[i].getStatus() == 2 && arr[i].getSalary() > avg)
            System.out.println(arr[i].getId());
    }
}

C#:

public static void PrintWorkers(Employee[] arr)
{
    int sum = 0, count = 0;
    for (int i = 0; i < arr.Length; i++)       // ממוצע המשכורות של המהנדסים
    {
        if (arr[i].GetStatus() == 1)
        {
            sum += arr[i].GetSalary();
            count++;
        }
    }
    if (count == 0)
    {
        Console.WriteLine("There are no engineers");
        return;
    }
    double avg = (double)sum / count;

    for (int i = 0; i < arr.Length; i++)       // פועלים שמשכורתם גבוהה מהממוצע
    {
        if (arr[i].GetStatus() == 2 && arr[i].GetSalary() > avg)
            Console.WriteLine(arr[i].GetId());
    }
}

לדוגמה: מהנדסים עם 160 ו-170 שעות (24000 ו-24700 ₪, ממוצע 24350 ₪) ופועלים עם 500 ו-200 שעות (36600 ו-15600 ₪) – יודפס רק מספר הזהות של הפועל הראשון.

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

שאלה 5 · מספרים ראשוניים והשערת גולדבך

הגדרה:

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

א.

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

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

Java:

public static boolean isPrimary(int num)

C#:

public static bool IsPrimary(int num)
(4 נקודות)

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

לדוגמה:

•8=3+58 = 3+5 (או 1+71+7)

•16=5+1116 = 5+11 (או 3+133+13)

•24=5+1924 = 5+19 (או 7+177+17 או 1+231+23 או 11+1311+13)

•46=3+4346 = 3+43 (או 5+415+41 או 23+2323+23)

ב.

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

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

Java:

public static int countPrimaryPairs(int num)

C#:

public static int CountPrimaryPairs(int num)
(4 נקודות)
ג.

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

לדוגמה:

עבור המספר 42 הפעולה תחזיר את המערך {1, 41, 5, 37, 11, 31, 13,29, 19, 23} כי:

•42=41+142=41 + 1

•42=37+542=37 + 5

•42=31+1142 = 31 + 11

•42=29+1342 = 29 + 13

•42=23+1942 = 23 + 19

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

Java:

public static int[] allPrimaryPairs(int num)

C#:

public static int[] AllPrimaryPairs(int num)
(4 נקודות)
ד.

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

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

סעיף א

תשובה:

num < 2 – false; אחרת בודקים מחלקים i מ-2 כל עוד i·i ≤ num; נמצא מחלק – false, אחרת true.

הרעיון: מספר הוא ראשוני אם אין לו מחלק בין 2 לבין עצמו. מספיק לבדוק מחלקים עד num\sqrt{num}: אם num=a⋅bnum=a\cdot b עם a≤ba\le b, אז a⋅a≤numa\cdot a\le num, כלומר לכל מספר פריק יש מחלק שאינו גדול מהשורש שלו.

1. 1 אינו ראשוני (יש לו מחלק אחד בלבד), ולכן עבור num<2num<2 מחזירים false.

2. עוברים על i=2,3,…i=2,3,\dots כל עוד i⋅i≤numi\cdot i\le num (תנאי שקול ל-i≤numi\le\sqrt{num} בלי חישוב שורש). אם num%i=0num \% i = 0 – נמצא מחלק, ומחזירים false מיד.

3. אם הלולאה הסתיימה בלי למצוא מחלק – מחזירים true. (את true מחזירים רק אחרי הלולאה, לא בתוכה.)

לדוגמה: עבור 97 בודקים i=2..9i=2..9 (10⋅10>9710\cdot10>97) ואף אחד אינו מחלק – ראשוני; עבור 9 כבר i=3i=3 מחלק – לא ראשוני.

Java:

// סעיף א: האם num ראשוני
public static boolean isPrimary(int num)
{
    if (num < 2)
        return false;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

C#:

// סעיף א: האם num ראשוני
public static bool IsPrimary(int num)
{
    if (num < 2)
        return false;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

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

סעיף ב

תשובה:

סופרים את ה-i בתחום 2..num/2 שעבורם isPrimary(i) וגם isPrimary(num−i); למשל 42 – 4 זוגות, 24 – 3 זוגות.

הרעיון: כל זוג num=i+(num−i)num=i+(num-i) נספר פעם אחת אם עוברים רק על המחובר הקטן, i≤num/2i\le num/2. לכל ii כזה בודקים בעזרת `isPrimary` מסעיף א אם גם ii וגם num−inum-i ראשוניים.

1. מתחילים מ-i=2i=2, הראשוני הקטן ביותר. 1 אינו נחשב ראשוני (ראו סעיף א), ולכן הזוגות עם 1, כמו 1+71+7, 1+231+23, 1+411+41, אינם נספרים (ראו הערה למטה).

2. עוצרים ב-num/2num/2, כך שהזוג 5+35+3 לא נספר שוב אחרי 3+53+5, והזוג 23+2323+23 נספר פעם אחת.

לדוגמה: עבור 24 נמצאים 5+195+19, 7+177+17, 11+1311+13 – 3 זוגות; עבור 46: 3+433+43, 5+415+41, 17+2917+29, 23+2323+23 – 4 זוגות; עבור 42: 4 זוגות.

Java:

// סעיף ב: מספר הזוגות של ראשוניים שסכומם num
public static int countPrimaryPairs(int num)
{
    int count = 0;
    for (int i = 2; i <= num / 2; i++)      // i הוא המחובר הקטן בזוג
    {
        if (isPrimary(i) && isPrimary(num - i))
            count++;
    }
    return count;
}

C#:

// סעיף ב: מספר הזוגות של ראשוניים שסכומם num
public static int CountPrimaryPairs(int num)
{
    int count = 0;
    for (int i = 2; i <= num / 2; i++)      // i הוא המחובר הקטן בזוג
    {
        if (IsPrimary(i) && IsPrimary(num - i))
            count++;
    }
    return count;
}

הערה: בדוגמאות שבשאלה מופיעים גם זוגות עם 1 (כמו 1+71+7), אבל לפי ההגדרה המקובלת 1 אינו מספר ראשוני (יש לו מחלק חיובי אחד בלבד, ולא שני מחלקים שונים), ולכן זוגות אלה אינם נספרים. מי שמחשיב את 1 כראשוני, כמו בדוגמאות, צריך רק להחזיר true עבור 1 ב-isPrimary ולהתחיל את הלולאה מ-i=1i=1; אז למשל עבור 42 יתקבלו 5 זוגות.

תשובה: הפעולה שלמעלה (למשל עבור 42 היא מחזירה 4).

סעיף ג

תשובה:

מערך בגודל 2·countPrimaryPairs(num); לכל i ≤ num/2 ש-i ו-num−i ראשוניים כותבים את i ואת num−i בשני תאים צמודים; עבור 42: {5, 37, 11, 31, 13, 29, 19, 23}.

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

1. `result = new int[2 * countPrimaryPairs(num)]`.

2. `index` מצביע על התא הפנוי הבא. לכל ii מ-2 עד num/2num/2 שבו ii ו-num−inum-i ראשוניים: `result[index] = i`, `result[index+1] = num - i`, ו-`index` גדל ב-2.

3. מחזירים את המערך.

עבור 42 מתקבל {5, 37, 11, 31, 13, 29, 19, 23}. המערך בדוגמה שבשאלה מתחיל גם ב-1, 41, אבל 1 אינו ראשוני (ראו ההערה בסעיף ב), ולכן זוג זה אינו נכלל; מי שמחשיב את 1 כראשוני יקבל את המערך שבדוגמה, {1, 41, 5, 37, 11, 31, 13, 29, 19, 23}.

Java:

// סעיף ג: מערך של כל הזוגות (כל זוג בשני תאים צמודים)
public static int[] allPrimaryPairs(int num)
{
    int[] result = new int[2 * countPrimaryPairs(num)];
    int index = 0;
    for (int i = 2; i <= num / 2; i++)
    {
        if (isPrimary(i) && isPrimary(num - i))
        {
            result[index] = i;              // המחובר הקטן
            result[index + 1] = num - i;    // המחובר הגדול
            index += 2;
        }
    }
    return result;
}

C#:

// סעיף ג: מערך של כל הזוגות (כל זוג בשני תאים צמודים)
public static int[] AllPrimaryPairs(int num)
{
    int[] result = new int[2 * CountPrimaryPairs(num)];
    int index = 0;
    for (int i = 2; i <= num / 2; i++)
    {
        if (IsPrimary(i) && IsPrimary(num - i))
        {
            result[index] = i;              // המחובר הקטן
            result[index + 1] = num - i;    // המחובר הגדול
            index += 2;
        }
    }
    return result;
}

תשובה: הפעולה שלמעלה; עבור 42 היא מחזירה {5, 37, 11, 31, 13, 29, 19, 23}.

סעיף ד

תשובה:

isPrimary – O(n)O(\sqrt{n}); countPrimaryPairs – O(nn)O(n\sqrt{n}); allPrimaryPairs – O(nn)O(n\sqrt{n}) (n = num).

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

1. isPrimary: הלולאה רצה כל עוד i⋅i≤ni\cdot i\le n, כלומר לכל היותר כ-n\sqrt{n} חזרות, ובכל חזרה מספר קבוע של פעולות: O(n)O(\sqrt{n}).

2. countPrimaryPairs: הלולאה רצה n/2n/2 פעמים, ובכל חזרה עד שתי קריאות ל-isPrimary, כל אחת O(n)O(\sqrt{n}) לכל היותר: n2⋅O(n)=O(nn)\frac{n}{2}\cdot O(\sqrt{n}) = O(n\sqrt{n}).

3. allPrimaryPairs: קריאה אחת ל-countPrimaryPairs – O(nn)O(n\sqrt{n}), ועוד לולאה זהה של n/2n/2 חזרות עם קריאות ל-isPrimary – שוב O(nn)O(n\sqrt{n}). יחד: O(nn)+O(nn)=O(nn)O(n\sqrt{n})+O(n\sqrt{n})=O(n\sqrt{n}).

תשובה: isPrimary – O(n)O(\sqrt{n}); countPrimaryPairs – O(nn)O(n\sqrt{n}); allPrimaryPairs – O(nn)O(n\sqrt{n}), כאשר nn הוא num.

שאלה 6 · מחלקת מחסן דגלים: הוספה ושאילתות

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

לשם כך הוגדרה המחלקה "דגל" (Flag) ולה התכונות האלה:

•שם מדינה (country) - מחרוזת (String)

•אורך (length) - מספר שלם (int)

•רוחב (width) - מספר שלם (int)

במחלקה הוגדרה פעולה בונה המקבלת ערכים לכל התכונות והפעולות get/set ו-toString.

א.

הגדירו מחלקה בשם "מחסן דגלים" (Warehouse) הכוללת את התכונות האלה:

•מערך של דגלים (flags) - מערך של עצמים מסוג "דגל" (Flag) בגודל מקסימלי של 100.

•מערך של כמויות (quantities) - מערך של מספרים שלמים (int) באותו הגודל כמו מערך הדגלים, כאשר כל תא מציין את הכמות של הדגל המתאים במערך הדגלים (הדגל במקום ה-i במערך הדגלים מתאים לכמות במקום ה-i במערך הכמויות).

•מספר הדגלים הנוכחי במחסן (currentFlags) - מספר שלם (int).

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

(3 נקודות)
ב.

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

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

Java:

public void add(String country, int length, int width, int quant)

C#:

public void Add(string country, int length, int width, int quant)
(4 נקודות)
ג.

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

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

Java:

public void flagsWithMinQuantity (int minQuality)

C#:

public void FlagsWithMinQuantity (int minQuality)
(4 נקודות)
ד.

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

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

Java:

public void printFlags(String[] countries)

C#:

public void PrintFlags(string[] countries)
(4 נקודות)
◂ פתרון מלא לשאלה 6

סעיף א

תשובה:

תכונות private: Flag[] flags, int[] quantities, int currentFlags; הבנאי: flags = new Flag[100], quantities = new int[100], currentFlags = 0.

מגדירים את שלוש התכונות כפרטיות. שני המערכים הם "מערכים מקבילים": התא `i` ב-`quantities` שומר את הכמות של הדגל שבתא `i` ב-`flags`. `currentFlags` הוא מספר התאים התפוסים, והוא גם המקום הפנוי הבא בשני המערכים.

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

Java:

class Warehouse
{
    private Flag[] flags;
    private int[] quantities;
    private int currentFlags;

    // סעיף א
    public Warehouse()
    {
        this.flags = new Flag[100];
        this.quantities = new int[100];
        this.currentFlags = 0;
    }
    ...
}

C#:

class Warehouse
{
    private Flag[] flags;
    private int[] quantities;
    private int currentFlags;

    // סעיף א
    public Warehouse()
    {
        this.flags = new Flag[100];
        this.quantities = new int[100];
        this.currentFlags = 0;
    }
    ...
}

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

סעיף ב

תשובה:

מחפשים בין currentFlags הדגלים דגל עם אותם מדינה, אורך ורוחב – אם נמצא, quantities[i] += quant; אחרת אם המחסן מלא – הודעה; אחרת יוצרים Flag חדש בתא currentFlags, שומרים את הכמות ומגדילים את currentFlags.

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

1. עוברים רק על התאים התפוסים, 0..currentFlags−10..currentFlags-1 (שאר התאים מכילים null). התכונות של `Flag` פרטיות, ולכן משווים בעזרת פעולות ה-get; מחרוזות משווים ב-`equals` (ב-C# אפשר `==`).

2. אם נמצא דגל זהה – מוסיפים את `quant` לכמות שלו וסיימנו.

3. אם לא נמצא ו-`currentFlags` שווה ל-100 – המחסן מלא: מדפיסים הודעה.

4. אחרת יוצרים עצם `Flag` חדש, שמים אותו בתא `currentFlags`, שומרים את הכמות באותו מקום ב-`quantities` ומגדילים את `currentFlags` ב-1.

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

Java:

// סעיף ב
public void add(String country, int length, int width, int quant)
{
    for (int i = 0; i < currentFlags; i++)
    {
        if (flags[i].getCountry().equals(country) &&
            flags[i].getLength() == length && flags[i].getWidth() == width)
        {
            quantities[i] += quant;          // דגל קיים - עדכון הכמות
            return;
        }
    }
    if (currentFlags == flags.length)
    {
        System.out.println("The warehouse is full");
        return;
    }
    flags[currentFlags] = new Flag(country, length, width);
    quantities[currentFlags] = quant;
    currentFlags++;
}

C#:

public void Add(string country, int length, int width, int quant)
{
    for (int i = 0; i < currentFlags; i++)
    {
        if (flags[i].GetCountry() == country &&
            flags[i].GetLength() == length && flags[i].GetWidth() == width)
        {
            quantities[i] += quant;          // דגל קיים - עדכון הכמות
            return;
        }
    }
    if (currentFlags == flags.Length)
    {
        Console.WriteLine("The warehouse is full");
        return;
    }
    flags[currentFlags] = new Flag(country, length, width);
    quantities[currentFlags] = quant;
    currentFlags++;
}

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

סעיף ג

תשובה:

לולאה על i מ-0 עד currentFlags−1; אם quantities[i] < minQuality – מדפיסים את flags[i].toString() ואת הכמות.

עוברים על הדגלים שבמחסן (עד `currentFlags`, לא עד סוף המערך) ובודקים את הכמות המקבילה ב-`quantities`. אם היא קטנה מהכמות המינימלית שהתקבלה – מדפיסים את פרטי הדגל בעזרת `toString()` ואת הכמות. (הפרמטר נקרא בשאלה `minQuality`; הכוונה לכמות מינימלית.)

Java:

// סעיף ג
public void flagsWithMinQuantity(int minQuality)
{
    for (int i = 0; i < currentFlags; i++)
    {
        if (quantities[i] < minQuality)
            System.out.println(flags[i].toString() + ", quantity: " + quantities[i]);
    }
}

C#:

public void FlagsWithMinQuantity(int minQuality)
{
    for (int i = 0; i < currentFlags; i++)
    {
        if (quantities[i] < minQuality)
            Console.WriteLine(flags[i].ToString() + ", quantity: " + quantities[i]);
    }
}

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

סעיף ד

תשובה:

לולאה חיצונית על המדינות; לכל מדינה total=0 ולולאה פנימית על הדגלים במחסן שמוסיפה quantities[i] כאשר flags[i].getCountry() שווה לשם המדינה; מדפיסים את המדינה ואת total.

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

1. לולאה חיצונית על שמות המדינות שבמערך `countries`.

2. לכל מדינה מאפסים את הסכום `total` (בתוך הלולאה החיצונית – אחרת הכמויות של מדינה קודמת יצטברו).

3. לולאה פנימית על הדגלים שבמחסן (0..currentFlags−10..currentFlags-1): אם שם המדינה של הדגל שווה לשם הנוכחי – מוסיפים את הכמות שלו.

4. מדפיסים את שם המדינה ואת הסכום (0 אם אין לה דגלים במחסן).

לדוגמה: במחסן 30 דגלי Israel במידה 100×70100\times70, 5 דגלי Israel במידה 200×140200\times140 ו-30 דגלי France. עבור {"Israel", "France", "Japan"} יודפס: Israel: 35, France: 30, Japan: 0.

Java:

// סעיף ד
public void printFlags(String[] countries)
{
    for (int c = 0; c < countries.length; c++)
    {
        int total = 0;                       // מתאפס לכל מדינה
        for (int i = 0; i < currentFlags; i++)
        {
            if (flags[i].getCountry().equals(countries[c]))
                total += quantities[i];
        }
        System.out.println(countries[c] + ": " + total);
    }
}

C#:

public void PrintFlags(string[] countries)
{
    for (int c = 0; c < countries.Length; c++)
    {
        int total = 0;                       // מתאפס לכל מדינה
        for (int i = 0; i < currentFlags; i++)
        {
            if (flags[i].GetCountry() == countries[c])
                total += quantities[i];
        }
        Console.WriteLine(countries[c] + ": " + total);
    }
}

סיבוכיות: O(k⋅m)O(k\cdot m), כאשר kk מספר המדינות ברשימה ו-mm מספר הדגלים במחסן.

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

שאלה 7 · מעקב רקורסיה: ממוצע ספרות וחלוקת מערך

נתונות ארבע פעולות:

Java:

public static double one (int num)
{
    return  two (num,0,0);
}
private static double two (int num, int s,int c)
{
    if(num == 0) return (double)s/c;
    return two (num/10, s+ (num % 10), c+1);
}
public static int[] three (int[] arr, int p)
{
    int n = arr.length;
    int[] temp=new int [n];
    four(arr, temp, 0, 0, n-1,p);
    return temp;
}
private static void four (int[] arr, int[] temp, int k,
                          int left, int right, int p)
{
    if (k <arr.length)
    {
        if (one(arr[k]) > one(arr[p]))
        {
            temp[right] = arr[k];
            four(arr, temp, k+1, left, right-1, p);
        }
        else
        {
            temp[left] = arr[k];
            four(arr, temp, k+1, left+1, right, p);
        }
    }
}

C#:

public static double One (int num)
{
    return  Two (num,0,0);
}
private static double Two (int num, int s,int c)
{
    if(num == 0) return (double)s/c;
    return Two (num/10, s+ (num % 10), c+1);
}
public static int[] Three (int[] arr, int p)
{
    int n = arr.Length;
    int[] temp=new int [n];
    Four(arr, temp, 0, 0, n-1,p);
    return temp;
}
private static void Four (int[] arr, int[] temp, int k,
                          int left, int right, int p)
{
    if (k <arr.Length)
    {
        if (One(arr[k]) > One(arr[p]))
        {
            temp[right] = arr[k];
            Four(arr, temp, k+1, left, right-1, p);
        }
        else
        {
            temp[left] = arr[k];
            Four(arr, temp, k+1, left+1, right, p);
        }
    }
}
א.
(1)

עקבו אחרי זימון הפעולה one(6123) ורשמו את תוצאת הזימון. יש להראות מעקב!

(2)

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

(3)

מה מבצעת הפעולה one(num) עבור מספר שלם num?

(5 נקודות)
ב.

נתון המערך `int[] a = {126,9,35,2684,8941,24}`

(1)

עקבו אחרי זימון הפעולה three(a, 3) ורשמו מה תהיה תוצאת הזימון.

יש להראות מעקב אחרי ביצוע הפעולה three, אין צורך להראות מעקב אחרי הפעולות one ו-two.

(2)

האם קיים ערך p שעבורו זימון הפעולה three(a, p) יגרום לשגיאה? הסבירו את תשובתכם.

(3)

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

(4)

מה מבצעת הפעולה three(a, p) עבור מערך של מספרים שלמים arr וערך שלם p?

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

סעיף א

(1)
תשובה:

one(6123) מחזירה 3.0.

`one` קוראת ל-`two(num, 0, 0)`. בכל קריאה `two` מוסיפה ל-`s` את ספרת האחדות (`num % 10`), מגדילה את `c` ב-1 ומורידה את ספרת האחדות (`num/10`). כש-`num` מגיע ל-0 מוחזר s/cs/c כמספר ממשי.

קריאהnumscפעולה
two(6123, 0, 0)612300קריאה ל-two(612, 0+3, 1)
two(612, 3, 1)61231קריאה ל-two(61, 3+2, 2)
two(61, 5, 2)6152קריאה ל-two(6, 5+1, 3)
two(6, 6, 3)663קריאה ל-two(0, 6+6, 4)
two(0, 12, 4)0124מחזירה 12/4=3.012/4=3.0

הערך 3.0 עובר ללא שינוי בחזרה דרך כל הקריאות.

תשובה: one(6123) מחזירה 3.0.

(2)
תשובה:

לדוגמה 5546 (או 159).

הפעולה מחזירה את ממוצע הספרות (ראו סעיף 3), לכן צריך מספר גדול מ-100 שממוצע ספרותיו 5, כלומר סכום הספרות שווה פי 5 ממספר הספרות.

לדוגמה 5546: 5+5+4+64=204=5.0\frac{5+5+4+6}{4}=\frac{20}{4}=5.0. גם 159 מתאים: 1+5+93=153=5.0\frac{1+5+9}{3}=\frac{15}{3}=5.0.

תשובה: לדוגמה 5546.

(3)
תשובה:

מחזירה את ממוצע הספרות של num (סכום הספרות חלקי מספר הספרות).

`two` סוכמת ב-`s` את ספרות המספר וסופרת ב-`c` את מספרן, ובסוף מחזירה s/cs/c כמספר ממשי. לכן `one(num)` מחזירה את ממוצע הספרות של num.

(עבור num=0 מתקבל 0/00/0 בחלוקה ממשית, כלומר NaN – אין ספרות למצע.)

תשובה: one(num) מחזירה את ממוצע הספרות של num.

סעיף ב

(1)
תשובה:

{126, 35, 2684, 24, 8941, 9}

`three` יוצרת מערך `temp` באורך n=6n=6 וקוראת ל-`four(a, temp, 0, 0, 5, 3)`. ערך ההשוואה הוא ממוצע הספרות של `a[3] = 2684`: 2+6+8+44=5.0\frac{2+6+8+4}{4}=5.0.

`four` עוברת על התאים לפי הסדר (`k` מ-0 עד 5): איבר שממוצע ספרותיו גדול מ-5.0 נכתב במקום `right` (מהסוף), ו-`right` קטן ב-1; אחרת הוא נכתב במקום `left` (מההתחלה), ו-`left` גדל ב-1.

צעד ka[k]one(a[k])גדול מ-5.0?leftrightהשמה
01263.0לא05temp[0] = 126
199.0כן15temp[5] = 9
2354.0לא14temp[1] = 35
326845.0לא (שווה)24temp[2] = 2684
489415.5כן34temp[4] = 8941
5243.0לא33temp[3] = 24
6–––43k = 6 – עצירה

(העמודות left ו-right מראות את ערכיהם בתחילת הקריאה.)

תשובה: three(a, 3) מחזירה את המערך {126, 35, 2684, 24, 8941, 9}.

(2)
תשובה:

כן – כל p מחוץ לתחום 0..a.length−1 (p < 0 או p ≥ 6) גורם לחריגה מגבולות המערך בגישה a[p].

בקריאה הראשונה ל-`four` (כאשר k=0<nk=0<n) מחושב `one(arr[p])`, כלומר יש גישה לתא `arr[p]`. אם p<0p<0 או p≥a.lengthp\ge a.length (עבור המערך הנתון p≥6p\ge 6) – זו גישה לתא שאינו קיים, והתוכנית נעצרת בשגיאת חריגה מגבולות המערך (ב-Java: ArrayIndexOutOfBoundsException, ב-C#: IndexOutOfRangeException).

עבור כל pp בין 0 ל-a.length−1a.length-1 אין שגיאה: האינדקסים `left` ו-`right` נשארים בתחום, כי בכל קריאה נכתב תא אחד ונכתבים בדיוק nn תאים.

תשובה: כן. כל ערך p שאינו אינדקס חוקי במערך (p < 0 או p ≥ a.length) גורם לשגיאה.

(3)
תשובה:

אפשרי: מערך שבו לכל המספרים אותו ממוצע ספרות, למשל {111, 111, 111, 111, 111, 111} או {123, 114, 3320, 141, 312, 213}.

איבר עובר לחלק הימני רק אם ממוצע ספרותיו גדול מזה של `arr[p]`. אם לכל האיברים אותו ממוצע ספרות, התנאי לא מתקיים אף פעם, ולכן כל איבר נכתב במקום `left` – לפי הסדר מתחילת המערך. התוצאה זהה למערך המקורי, וזה נכון לכל pp תקין.

לדוגמה {111, 111, 111, 111, 111, 111} (ממוצע 1.0 לכולם), או עם מספרים שונים {123, 114, 3320, 141, 312, 213}, שבו ממוצע הספרות של כל מספר הוא 2.0.

תשובה: אפשרי, למשל arr = {123, 114, 3320, 141, 312, 213}.

(4)
תשובה:

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

הפעולה מחלקת את איברי המערך לשתי קבוצות לפי ממוצע הספרות שלהם (`one`), בהשוואה לממוצע הספרות של האיבר שבמקום p:

•האיברים שממוצע ספרותיהם קטן או שווה לזה של `arr[p]` (כולל `arr[p]` עצמו) נכתבים בתחילת המערך החדש, לפי הסדר המקורי.

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

המערך המקורי אינו משתנה; מוחזר מערך חדש.

תשובה: three מחזירה מערך חדש שבו קודם מופיעים (בסדרם) האיברים שממוצע ספרותיהם אינו גדול מזה של arr[p], ואחריהם (בסדר הפוך) האיברים שממוצע ספרותיהם גדול ממנו.

שאלה 8 · תפזורת: חיפוש מילה במטריצת אותיות

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

לדוגמה, המילה HELP מופיעה במטריצה שלפניכם שלוש פעמים:

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

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

Java:

public static boolean exist(char[][] arr, String word)

C#:

public static bool Exist(char[][] arr, string word)
◂ פתרון מלא לשאלה 8

פתרון

תשובה:

לכל תא (i, j) ולכל אחד מארבעת הכיוונים (ימינה, שמאלה, למטה, למעלה) בודקים אם word מתחילה בתא ונמשכת בכיוון בלי לצאת מגבולות המטריצה; נמצאה התאמה – true, אחרת false.

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

כיווןdrdc
משמאל לימין01
מימין לשמאל0−1-1
מלמעלה למטה10
מלמטה למעלה−1-10

האות ה-kk של המילה צריכה להופיע בתא (row+k⋅dr, col+k⋅dc)(row+k\cdot dr,\ col+k\cdot dc). כך פעולת עזר אחת, `existFrom`, בודקת את כל ארבעת הכיוונים, במקום ארבע פעולות כמעט זהות.

1. existFrom(arr, word, row, col, dr, dc): עוברים על אותיות המילה, k=0..L−1k=0..L-1. לכל אות מחשבים את התא המתאים. אם הוא מחוץ למטריצה (שורה או עמודה שלילית, או גדולה מהגודל) – המילה לא נכנסת בכיוון הזה ומחזירים false. אם האות בתא שונה מ-`word.charAt(k)` – מחזירים false. אם כל האותיות התאימו – true.

2. exist: שלוש לולאות מקוננות – על השורות, על העמודות ועל ארבעת הכיוונים. ברגע ש-`existFrom` מחזירה true – מחזירים true. אם נבדקו כל האפשרויות – מחזירים false.

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

בדוגמה שבשאלה: מהתא (0,1)(0,1) בכיוון ימינה נקרא H-E-L-P; מהתא (1,5)(1,5) בכיוון למטה נקרא H-E-L-P; ומהתא (3,3)(3,3) בכיוון שמאלה נקרא H-E-L-P (בשורה P L E H). מילה כמו HTD (באלכסון) לא תימצא, כי אלכסונים אינם חלק מהכללים.

Java:

// האם המילה word מופיעה במטריצה arr בשורה או בעמודה, באחד מארבעת הכיוונים
public static boolean exist(char[][] arr, String word)
{
    int[] dRow = {0, 0, 1, -1};      // ימינה, שמאלה, למטה, למעלה
    int[] dCol = {1, -1, 0, 0};
    for (int i = 0; i < arr.length; i++)
    {
        for (int j = 0; j < arr[i].length; j++)
        {
            for (int d = 0; d < 4; d++)
            {
                if (existFrom(arr, word, i, j, dRow[d], dCol[d]))
                    return true;
            }
        }
    }
    return false;
}

// האם המילה מתחילה בתא (row, col) ונמשכת בכיוון (dr, dc)
public static boolean existFrom(char[][] arr, String word, int row, int col, int dr, int dc)
{
    for (int k = 0; k < word.length(); k++)
    {
        int r = row + k * dr;
        int c = col + k * dc;
        if (r < 0 || r >= arr.length || c < 0 || c >= arr[r].length)
            return false;                    // יצאנו מגבולות המטריצה
        if (arr[r][c] != word.charAt(k))
            return false;
    }
    return true;
}

C#:

// האם המילה word מופיעה במטריצה arr בשורה או בעמודה, באחד מארבעת הכיוונים
public static bool Exist(char[][] arr, string word)
{
    int[] dRow = {0, 0, 1, -1};      // ימינה, שמאלה, למטה, למעלה
    int[] dCol = {1, -1, 0, 0};
    for (int i = 0; i < arr.Length; i++)
    {
        for (int j = 0; j < arr[i].Length; j++)
        {
            for (int d = 0; d < 4; d++)
            {
                if (ExistFrom(arr, word, i, j, dRow[d], dCol[d]))
                    return true;
            }
        }
    }
    return false;
}

// האם המילה מתחילה בתא (row, col) ונמשכת בכיוון (dr, dc)
public static bool ExistFrom(char[][] arr, string word, int row, int col, int dr, int dc)
{
    for (int k = 0; k < word.Length; k++)
    {
        int r = row + k * dr;
        int c = col + k * dc;
        if (r < 0 || r >= arr.Length || c < 0 || c >= arr[r].Length)
            return false;                    // יצאנו מגבולות המטריצה
        if (arr[r][c] != word[k])
            return false;
    }
    return true;
}

סיבוכיות: O(R⋅C⋅L)O(R\cdot C\cdot L), כאשר R×CR\times C גודל המטריצה ו-LL אורך המילה.

תשובה: הפעולה exist ופעולת העזר existFrom שלמעלה.

שאלה 9 · מחלקות חשבון ומשתמשים: אבטחת סיסמאות

המערכת "ארגונית" לניהול חשבונות משתמשים כוללת שתי מחלקות: Account ו-Users.

למחלקה Account התכונות הבאות:

•שם משתמש - username, מסוג מחרוזות, String

•סיסמה הנוכחית – currentPass, מסוג מחרוזות, String

•סיסמאות קודמות – passHistory, מסוג מערך של 10 מחרוזות, String. המערך ישמור עד 10 סיסמאות הקודמות של החשבון.

א.

כתבו בנאי (constructor) למחלקה Account שמקבל שם משתמש וסיסמה ראשונית כפרמטרים. הבנאי יאתחל את username, יאחסן את הסיסמה הראשונית ב-currentPass ובמקום הראשון במערך passHistory.

(2 נקודות)
ב.

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

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

•הסיסמה צריכה להכיל שתי אותיות גדולות ('A'-'Z') לפחות.

•הסיסמה צריכה להכיל לפחות ספרה אחת ('0'-'9').

•הסיסמה צריכה להכיל לפחות תו מיוחד אחד (כל תו שאינו אות או ספרה).

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

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

(4 נקודות)
ג.

כתבו במחלקה Account את הפעולה updatePassword המקבלת כפרמטר סיסמה חדשה.

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

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

(2 נקודות)

למחלקה Users שתי תכונות:

•חשבונות משתמשים – accounts, מסוג מערך עצמים מסוג Account, בגודל מקסימלי 100.

•מספר משתמשים פעילים – numOfAccounts, מסוג מספר שלם, int.

ד.

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

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

אם שם המשתמש לא קיים והמערך accounts אינו מלא, הפעולה תיצור אובייקט חדש מסוג Account, תוסיף אותו למערך accounts ותעדכן את ה-numOfAccounts.

(2 נקודות)
ה.

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

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

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

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

יש לתעד היטב את הצעתכם.

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

סעיף א

תשובה:

username = username; currentPass = firstPass; passHistory = new String[10]; passHistory[0] = firstPass.

הבנאי מאתחל את שם המשתמש ואת הסיסמה הנוכחית, יוצר את מערך ההיסטוריה בגודל 10 ושם את הסיסמה הראשונית בתא 0. בכל המחלקה נשמור על הכלל: בתא 0 של `passHistory` נמצאת תמיד הסיסמה הנוכחית, ואחריה הסיסמאות הקודמות מהחדשה לישנה (תאים ריקים מכילים null).

נוסיף גם פעולות get לשם המשתמש ולסיסמה הנוכחית – נשתמש בהן בהמשך.

Java:

// סעיף א
public Account(String username, String firstPass)
{
    this.username = username;
    this.currentPass = firstPass;
    this.passHistory = new String[10];
    this.passHistory[0] = firstPass;
}

public String getUsername() { return username; }

public String getCurrentPass() { return currentPass; }

C#:

// סעיף א
public Account(string username, string firstPass)
{
    this.username = username;
    this.currentPass = firstPass;
    this.passHistory = new string[10];
    this.passHistory[0] = firstPass;
}

public string GetUsername() { return username; }
public string GetCurrentPass() { return currentPass; }

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

סעיף ב

תשובה:

מעבר אחד על התווים: סופרים אותיות גדולות, מסמנים ספרה, תו מיוחד ותווים צמודים זהים; סופרים כמה מחמשת התנאים מתקיימים ומחזירים count >= 3.

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

1. לכל תו `ch`: אם הוא בין 'A' ל-'Z' – מגדילים את מונה האותיות הגדולות; אם הוא בין '0' ל-'9' – יש ספרה; אחרת, אם הוא גם אינו אות קטנה – זה תו מיוחד (לא אות ולא ספרה).

2. באותו מעבר משווים כל תו לתו שלפניו (מ-i=1i=1); אם הם שווים – התנאי "אין תווים זהים צמודים" נכשל.

3. סופרים: אורך ≥8\ge 8, לפחות 2 אותיות גדולות, ספרה, תו מיוחד, אין זוג צמוד זהה. מחזירים `count >= 3`.

לדוגמה: "abcdefgh" עומדת רק בתנאי האורך ובתנאי "אין תווים צמודים" – 2 תנאים, לא תקינה; "abcdefg1" – אורך, ספרה, אין צמודים – 3 תנאים, תקינה; "aa1!" – ספרה ותו מיוחד בלבד – לא תקינה.

Java:

// סעיף ב: לפחות 3 מתוך 5 התנאים
public boolean isPasswordValid(String pass)
{
    int upper = 0;
    boolean digit = false, special = false, noDouble = true;
    for (int i = 0; i < pass.length(); i++)
    {
        char ch = pass.charAt(i);
        if (ch >= 'A' && ch <= 'Z')
            upper++;
        else if (ch >= '0' && ch <= '9')
            digit = true;
        else if (!(ch >= 'a' && ch <= 'z'))
            special = true;                  // לא אות ולא ספרה
        if (i > 0 && ch == pass.charAt(i - 1))
            noDouble = false;                // שני תווים זהים צמודים
    }
    int count = 0;
    if (pass.length() >= 8) count++;
    if (upper >= 2) count++;
    if (digit) count++;
    if (special) count++;
    if (noDouble) count++;
    return count >= 3;
}

C#:

// סעיף ב: לפחות 3 מתוך 5 התנאים
public bool IsPasswordValid(string pass)
{
    int upper = 0;
    bool digit = false, special = false, noDouble = true;
    for (int i = 0; i < pass.Length; i++)
    {
        char ch = pass[i];
        if (ch >= 'A' && ch <= 'Z')
            upper++;
        else if (ch >= '0' && ch <= '9')
            digit = true;
        else if (!(ch >= 'a' && ch <= 'z'))
            special = true;                  // לא אות ולא ספרה
        if (i > 0 && ch == pass[i - 1])
            noDouble = false;                // שני תווים זהים צמודים
    }
    int count = 0;
    if (pass.Length >= 8) count++;
    if (upper >= 2) count++;
    if (digit) count++;
    if (special) count++;
    if (noDouble) count++;
    return count >= 3;
}

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

סעיף ג

תשובה:

אם !isPasswordValid – הודעה; אם הסיסמה מופיעה ב-passHistory (כולל הנוכחית בתא 0) – הודעה; אחרת מזיזים את התאים 0..8 מקום אחד ימינה (תא 9 נדרס), passHistory[0] = newPass, currentPass = newPass.

1. תקינות: קוראים ל-`isPasswordValid` מסעיף ב. אם הסיסמה לא תקינה – מדפיסים הודעה ויוצאים.

2. שונה מהקודמות: הסיסמה הנוכחית שמורה בתא 0 של `passHistory`, ולכן מספיק לסרוק את כל המערך. `newPass.equals(passHistory[i])` מחזיר false עבור תא ריק (null), כך שאין צורך לבדוק null בנפרד. אם נמצאה התאמה – הודעה ויציאה.

3. הוספה לתחילת ההיסטוריה: מזיזים את הסיסמאות מקום אחד ימינה, מהסוף להתחלה (מ-i=9i=9 עד i=1i=1: `passHistory[i] = passHistory[i-1]`), כדי לא לדרוס ערך לפני שהועתק. הערך שהיה בתא 9 – הסיסמה הישנה ביותר – נדרס. אחר כך שמים את הסיסמה החדשה בתא 0 ומעדכנים את `currentPass`.

Java:

// סעיף ג
public void updatePassword(String newPass)
{
    if (!isPasswordValid(newPass))
    {
        System.out.println("הסיסמה אינה תקינה");
        return;
    }
    for (int i = 0; i < passHistory.length; i++)
    {
        if (newPass.equals(passHistory[i]))  // הנוכחית נמצאת בתא 0
        {
            System.out.println("הסיסמה כבר הייתה בשימוש");
            return;
        }
    }
    for (int i = passHistory.length - 1; i > 0; i--)
        passHistory[i] = passHistory[i - 1];   // הישנה ביותר (תא 9) נדרסת
    passHistory[0] = newPass;
    currentPass = newPass;
}

C#:

// סעיף ג
public void UpdatePassword(string newPass)
{
    if (!IsPasswordValid(newPass))
    {
        Console.WriteLine("הסיסמה אינה תקינה");
        return;
    }
    for (int i = 0; i < passHistory.Length; i++)
    {
        if (newPass == passHistory[i])       // הנוכחית נמצאת בתא 0
        {
            Console.WriteLine("הסיסמה כבר הייתה בשימוש");
            return;
        }
    }
    for (int i = passHistory.Length - 1; i > 0; i--)
        passHistory[i] = passHistory[i - 1];   // הישנה ביותר (תא 9) נדרסת
    passHistory[0] = newPass;
    currentPass = newPass;
}

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

סעיף ד

תשובה:

סריקה של accounts[0..numOfAccounts−1] – שם קיים → הודעה; numOfAccounts == 100 → הודעה; אחרת accounts[numOfAccounts] = new Account(username, pass) ו-numOfAccounts++.

1. סורקים את החשבונות הפעילים (0..numOfAccounts−10..numOfAccounts-1) ומשווים את שם המשתמש של כל אחד (בעזרת `getUsername()`) לשם שהתקבל. אם נמצא – מדפיסים הודעה ויוצאים.

2. אם `numOfAccounts` שווה לגודל המערך (100) – אין מקום: מדפיסים הודעה ויוצאים.

3. אחרת יוצרים עצם `Account` חדש בעזרת הבנאי מסעיף א, שמים אותו בתא `numOfAccounts` (התא הפנוי הראשון) ומגדילים את `numOfAccounts` ב-1.

Java:

public Users()
{
    this.accounts = new Account[100];
    this.numOfAccounts = 0;
}

// סעיף ד
public void addUser(String username, String firstPass)
{
    for (int i = 0; i < numOfAccounts; i++)
    {
        if (accounts[i].getUsername().equals(username))
        {
            System.out.println("שם המשתמש כבר קיים");
            return;
        }
    }
    if (numOfAccounts == accounts.length)
    {
        System.out.println("אין מקום למשתמש חדש");
        return;
    }
    accounts[numOfAccounts] = new Account(username, firstPass);
    numOfAccounts++;
}

C#:

public Users()
{
    this.accounts = new Account[100];
    this.numOfAccounts = 0;
}

// סעיף ד
public void AddUser(string username, string firstPass)
{
    for (int i = 0; i < numOfAccounts; i++)
    {
        if (accounts[i].GetUsername() == username)
        {
            Console.WriteLine("שם המשתמש כבר קיים");
            return;
        }
    }
    if (numOfAccounts == accounts.Length)
    {
        Console.WriteLine("אין מקום למשתמש חדש");
        return;
    }
    accounts[numOfAccounts] = new Account(username, firstPass);
    numOfAccounts++;
}

תשובה: הפעולה שלמעלה (במחלקה Users).

סעיף ה

תשובה:

שני תנאים חדשים וחובה: לפחות אות קטנה אחת, והסיסמה לא מכילה את שם המשתמש; ובנוסף נדרשים 4 (במקום 3) מחמשת התנאים הקודמים. ב-Account: checkConditions, isPasswordValid חדשה, failedConditions; ב-Users: printWeakPasswords שמדפיסה כל משתמש שסיסמתו אינה עומדת בדרישות ואת התנאים שנכשלו.

ההצעה – שיפורים לחיזוק הסיסמאות:

1. תנאי חדש 6 – לפחות אות קטנה אחת ('a'-'z'). יחד עם האותיות הגדולות, הספרות והתווים המיוחדים, הסיסמה משלבת את כל סוגי התווים, ומספר הסיסמאות האפשריות שתוקף צריך לנסות גדל.

2. תנאי חדש 7 – הסיסמה אינה מכילה את שם המשתמש (בלי הבדל בין אותיות גדולות לקטנות). סיסמה כמו "Dana123!" לחשבון dana היא מהניחושים הראשונים של תוקף.

3. הקשחת הסף: נדרשים לפחות 4 מחמשת התנאים הקודמים (במקום 3).

הכלל החדש: סיסמה תקינה אם היא עומדת בלפחות 4 מחמשת התנאים הקודמים וגם בשני התנאים החדשים (6 ו-7 הם חובה).

המימוש במחלקה Account:

1. מערך קבוע `CONDITIONS` עם שמות שבעת התנאים – לצורך ההדפסה.

2. פעולה `checkConditions(pass)` עוברת פעם אחת על התווים (כמו בסעיף ב, ועכשיו מזהה גם אות קטנה) ומחזירה מערך בוליאני בגודל 7: תא kk הוא true אם הסיסמה עומדת בתנאי kk. את תנאי 7 בודקים בעזרת `indexOf` על שתי המחרוזות אחרי המרה לאותיות קטנות.

3. `isPasswordValid` מוחלפת בגרסה החדשה: סופרת את התנאים המתקיימים מבין 0..4 ומחזירה true רק אם יש לפחות 4 וגם תאים 5 ו-6 הם true. מכיוון ש-`updatePassword` מסעיף ג קוראת ל-`isPasswordValid`, מעכשיו כל סיסמה חדשה תיבדק לפי הכללים החדשים, בלי לשנות את `updatePassword`.

4. פעולה `failedConditions(pass)` מחזירה מחרוזת עם שמות כל התנאים שהסיסמה אינה עומדת בהם.

Java:

// סעיף ה: שמות שבעת התנאים (5 הקודמים + 2 חדשים)
private static final String[] CONDITIONS = {
    "לפחות 8 תווים", "לפחות 2 אותיות גדולות", "לפחות ספרה אחת",
    "לפחות תו מיוחד אחד", "אין תווים זהים צמודים",
    "לפחות אות קטנה אחת", "לא מכילה את שם המשתמש"};

// סעיף ה: מחזירה מערך שבו תא k הוא true אם הסיסמה עומדת בתנאי k
public boolean[] checkConditions(String pass)
{
    int upper = 0;
    boolean lower = false, digit = false, special = false, noDouble = true;
    for (int i = 0; i < pass.length(); i++)
    {
        char ch = pass.charAt(i);
        if (ch >= 'A' && ch <= 'Z')
            upper++;
        else if (ch >= 'a' && ch <= 'z')
            lower = true;
        else if (ch >= '0' && ch <= '9')
            digit = true;
        else
            special = true;
        if (i > 0 && ch == pass.charAt(i - 1))
            noDouble = false;
    }
    boolean[] ok = new boolean[7];
    ok[0] = pass.length() >= 8;
    ok[1] = upper >= 2;
    ok[2] = digit;
    ok[3] = special;
    ok[4] = noDouble;
    ok[5] = lower;                                           // תנאי חדש
    ok[6] = pass.toLowerCase().indexOf(username.toLowerCase()) == -1;   // תנאי חדש
    return ok;
}

// סעיף ה: הדרישה החדשה - לפחות 4 מ-5 התנאים הקודמים, ושני התנאים החדשים חובה
public boolean isPasswordValid(String pass)
{
    boolean[] ok = checkConditions(pass);
    int count = 0;
    for (int k = 0; k < 5; k++)
    {
        if (ok[k])
            count++;
    }
    return count >= 4 && ok[5] && ok[6];
}

// סעיף ה: רשימת התנאים שהסיסמה אינה עומדת בהם
public String failedConditions(String pass)
{
    boolean[] ok = checkConditions(pass);
    String list = "";
    for (int k = 0; k < ok.length; k++)
    {
        if (!ok[k])
            list += " [" + CONDITIONS[k] + "]";
    }
    return list;
}

C#:

// סעיף ה: שמות שבעת התנאים (5 הקודמים + 2 חדשים)
private static string[] CONDITIONS = {
    "לפחות 8 תווים", "לפחות 2 אותיות גדולות", "לפחות ספרה אחת",
    "לפחות תו מיוחד אחד", "אין תווים זהים צמודים",
    "לפחות אות קטנה אחת", "לא מכילה את שם המשתמש"};

// סעיף ה: מחזירה מערך שבו תא k הוא true אם הסיסמה עומדת בתנאי k
public bool[] CheckConditions(string pass)
{
    int upper = 0;
    bool lower = false, digit = false, special = false, noDouble = true;
    for (int i = 0; i < pass.Length; i++)
    {
        char ch = pass[i];
        if (ch >= 'A' && ch <= 'Z')
            upper++;
        else if (ch >= 'a' && ch <= 'z')
            lower = true;
        else if (ch >= '0' && ch <= '9')
            digit = true;
        else
            special = true;
        if (i > 0 && ch == pass[i - 1])
            noDouble = false;
    }
    bool[] ok = new bool[7];
    ok[0] = pass.Length >= 8;
    ok[1] = upper >= 2;
    ok[2] = digit;
    ok[3] = special;
    ok[4] = noDouble;
    ok[5] = lower;                                            // תנאי חדש
    ok[6] = pass.ToLower().IndexOf(username.ToLower()) == -1; // תנאי חדש
    return ok;
}

// סעיף ה: הדרישה החדשה - לפחות 4 מ-5 התנאים הקודמים, ושני התנאים החדשים חובה
public bool IsPasswordValid(string pass)
{
    bool[] ok = CheckConditions(pass);
    int count = 0;
    for (int k = 0; k < 5; k++)
    {
        if (ok[k])
            count++;
    }
    return count >= 4 && ok[5] && ok[6];
}

// סעיף ה: רשימת התנאים שהסיסמה אינה עומדת בהם
public string FailedConditions(string pass)
{
    bool[] ok = CheckConditions(pass);
    string list = "";
    for (int k = 0; k < ok.Length; k++)
    {
        if (!ok[k])
            list += " [" + CONDITIONS[k] + "]";
    }
    return list;
}

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

Java:

// סעיף ה: הדפסת המשתמשים שסיסמתם הנוכחית אינה עומדת בדרישות החדשות
public void printWeakPasswords()
{
    int count = 0;
    for (int i = 0; i < numOfAccounts; i++)
    {
        String pass = accounts[i].getCurrentPass();
        if (!accounts[i].isPasswordValid(pass))
        {
            System.out.println(accounts[i].getUsername() + " - יש לחזק את הסיסמה. תנאים שלא מתקיימים:"
                               + accounts[i].failedConditions(pass));
            count++;
        }
    }
    if (count == 0)
        System.out.println("כל הסיסמאות עומדות בדרישות החדשות");
}

C#:

// סעיף ה: הדפסת המשתמשים שסיסמתם הנוכחית אינה עומדת בדרישות החדשות
public void PrintWeakPasswords()
{
    int count = 0;
    for (int i = 0; i < numOfAccounts; i++)
    {
        string pass = accounts[i].GetCurrentPass();
        if (!accounts[i].IsPasswordValid(pass))
        {
            Console.WriteLine(accounts[i].GetUsername() + " - יש לחזק את הסיסמה. תנאים שלא מתקיימים:"
                              + accounts[i].FailedConditions(pass));
            count++;
        }
    }
    if (count == 0)
        Console.WriteLine("כל הסיסמאות עומדות בדרישות החדשות");
}

לדוגמה, עבור המשתמשים dana עם "Ab1!", avi עם "XAvi12#Q" ו-moshe עם "AbCd1234!x" יודפס:

dana - יש לחזק את הסיסמה. תנאים שלא מתקיימים: [לפחות 8 תווים] [לפחות 2 אותיות גדולות]
avi - יש לחזק את הסיסמה. תנאים שלא מתקיימים: [לא מכילה את שם המשתמש]

(הסיסמה של moshe עומדת בכל התנאים ולכן הוא אינו מודפס.)

תשובה: השיפורים: אות קטנה חובה, איסור על שם המשתמש בתוך הסיסמה, ו-4 מתוך 5 התנאים הקודמים. נוספו ל-Account הפעולות checkConditions ו-failedConditions והוחלפה isPasswordValid; נוספה ל-Users הפעולה printWeakPasswords.

שאלה 10 · מעקב: היפוכי קטעים והזזה מעגלית במערך

נתונות הפעולות הבאות: what ו-secret, ושתי פעולות העזר why ו-mystery.

Java:

public static void secret(int[] a, int s) {
    s %= a.length;
    mystery(a, 0, a.length - 1);
    mystery(a, 0, s - 1);
    mystery(a, s, a.length - 1);
}
public static void mystery(int[] a, int start, int end) {
    int temp;
    while (start < end) {
        temp = a[start];
        a[start] = a[end];
        a[end] = temp;
        start++;
        end--;
    }
}
public static void what(int[] a, int d){
    why(a, d, 0);
}
public static void why(int[] a, int d, int i){
    if (i<a.length) {
        int j = (i + d) % a.length;
        int rest = a[j];
        why(a, d, i + 1);
        a[i] = rest;
    }
}

C#:

public static void Secret(int[] a, int s) {
    s %= a.Length;
    Mystery(a, 0, a.Length - 1);
    Mystery(a, 0, s - 1);
    Mystery(a, s, a.Length - 1);
}
public static void Mystery(int[] a, int start, int end) {
    int temp;
    while (start < end) {
        temp = a[start];
        a[start] = a[end];
        a[end] = temp;
        start++;
        end--;
    }
}
public static void What(int[] a, int d){
    Why(a, d, 0);
}
public static void Why(int[] a, int d, int i){
    if (i<a.Length) {
        int j = (i + d) % a.Length;
        int rest = a[j];
        Why(a, d, i + 1);
        a[i] = rest;
    }
}

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

אינדקס0123456
arr103682115
א.

עקבו אחרי זימון הפעולה mystery(arr, 1, 4) ורשמו מה יהיה תוכן המערך אחרי הזימון.

(2 נקודות)
ב.

עקבו אחרי זימון הפעולה secret(arr, 3) ורשמו מה יהיה תוכן המערך אחרי הזימון.

(2 נקודות)
ג.

מה מבצעת הפעולה secret(a, d) עבור מערך של מספרים שלמים a ומספר שלם וחיובי d?

(2 נקודות)
ד.

עקבו אחרי זימון הפעולה what(arr, 3) ורשמו מה יהיה תוכן המערך אחרי הזימון.

יש להראות ערכי המשתנים בכל זימון הרקורסיבי

(3 נקודות)
ה.

אחרי זימון הפעולה what(brr, 2) יתקבל המערך brr הזה:

אינדקס012345
brr102030405060

מה היה תוכן המערך brr לפני זימון הפעולה?

(5 נקודות)
ו.

מה מבצעת הפעולה what(a, d) עבור מערך של מספרים שלמים a ומספר שלם וחיובי d?

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

סעיף א

תשובה:

{10, 2, 8, 6, 3, 11, 5}

`mystery` מחליפה את התאים `start` ו-`end`, מקרבת אותם זה לזה, וממשיכה כל עוד `start < end` – כלומר היא הופכת את סדר האיברים בקטע שבין `start` ל-`end`.

ערך startendstart < end?החלפההמערך אחרי ההחלפה
14כןa[1]=3 ↔ a[4]=2{10, 2, 6, 8, 3, 11, 5}
23כןa[2]=6 ↔ a[3]=8{10, 2, 8, 6, 3, 11, 5}
32לא–סיום

תשובה: אחרי הזימון arr = {10, 2, 8, 6, 3, 11, 5}.

סעיף ב

תשובה:

{2, 11, 5, 10, 3, 6, 8} (על המערך המקורי).

מבצעים על המערך המקורי {10, 3, 6, 8, 2, 11, 5} (אורך 7).

1. `s %= a.length`: 3%7=33 \% 7 = 3, כלומר s=3.

2. `mystery(a, 0, 6)` – היפוך כל המערך: {5, 11, 2, 8, 6, 3, 10}.

3. `mystery(a, 0, 2)` – היפוך שלושת התאים הראשונים (5, 11, 2): {2, 11, 5, 8, 6, 3, 10}.

4. `mystery(a, 3, 6)` – היפוך התאים 3 עד 6 (8, 6, 3, 10): {2, 11, 5, 10, 3, 6, 8}.

התוצאה: שלושת האיברים האחרונים של המערך המקורי (2, 11, 5) עברו להתחלה, וכל השאר זזו שלושה מקומות ימינה.

(אם מבצעים את הזימון על המערך כפי שהוא אחרי סעיף א, {10, 2, 8, 6, 3, 11, 5}, מתקבל באותה דרך {3, 11, 5, 10, 2, 8, 6}.)

תשובה: arr = {2, 11, 5, 10, 3, 6, 8}.

סעיף ג

תשובה:

הזזה מעגלית (סיבוב) של המערך d מקומות ימינה: d האיברים האחרונים עוברים להתחלה.

נסמן nn = אורך המערך, ו-s=d%ns=d\%n (הזזה ב-nn מקומות מחזירה את המערך לעצמו, ולכן מספיקה השארית).

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

•היפוך הקטע 0..s−10..s-1 מחזיר את ss האיברים האלה לסדרם המקורי, והיפוך הקטע s..n−1s..n-1 עושה את אותו הדבר לשאר.

התוצאה: כל איבר זז ss מקומות ימינה, ואיברים ש"נופלים" מהסוף חוזרים להתחלה: האיבר שהיה במקום ii עובר למקום (i+d)%n(i+d)\%n. כך ראינו בסעיף ב: {10, 3, 6, 8, 2, 11, 5} הפך ל-{2, 11, 5, 10, 3, 6, 8}.

תשובה: secret מזיזה את איברי המערך באופן מעגלי d מקומות ימינה (d האיברים האחרונים עוברים להתחלה).

סעיף ד

תשובה:

{8, 2, 11, 5, 10, 3, 6}

מבצעים על המערך המקורי {10, 3, 6, 8, 2, 11, 5} (n=7n=7, d=3). `what` קוראת ל-`why(a, 3, 0)`.

בכל קריאה `why` מחשבת j=(i+3)%7j=(i+3)\%7, שומרת במשתנה המקומי `rest` את `a[j]` לפני הקריאה הרקורסיבית, ורק אחרי שהקריאה הרקורסיבית חוזרת כותבת `a[i] = rest`. לכן כל הקריאות קוראות מהמערך המקורי (שלב הירידה), וכל הכתיבות קורות בשלב החזרה.

שלב הירידה:

קריאהij = (i+3)%7rest = a[j]
why(a, 3, 0)038
why(a, 3, 1)142
why(a, 3, 2)2511
why(a, 3, 3)365
why(a, 3, 4)4010
why(a, 3, 5)513
why(a, 3, 6)626
why(a, 3, 7)7–7<77<7 לא – חוזרת

שלב החזרה (מהקריאה העמוקה החוצה): a[6]=6, a[5]=3, a[4]=10, a[3]=5, a[2]=11, a[1]=2, a[0]=8.

תשובה: arr = {8, 2, 11, 5, 10, 3, 6}.

סעיף ה

תשובה:

{50, 60, 10, 20, 30, 40}

כפי שראינו בסעיף ד, כל הקריאות מתבצעות לפני הכתיבות, ולכן `what(a, d)` מבצעת: anew[i]=aold[(i+d)%n]a_{new}[i] = a_{old}[(i+d)\%n].

כאן n=6n=6, d=2, ולכן aold[(i+2)%6]=anew[i]a_{old}[(i+2)\%6] = a_{new}[i]:

i(i+2)%6a_new[i]ולכן
0210brr[2] = 10
1320brr[3] = 20
2430brr[4] = 30
3540brr[5] = 40
4050brr[0] = 50
5160brr[1] = 60

בדיקה: what על {50, 60, 10, 20, 30, 40} עם d=2: a[0]=a[2]=10a[0]=a[2]=10, a[1]=a[3]=20a[1]=a[3]=20, a[2]=a[4]=30a[2]=a[4]=30, a[3]=a[5]=40a[3]=a[5]=40, a[4]=a[0]=50a[4]=a[0]=50, a[5]=a[1]=60a[5]=a[1]=60 – מתקבל {10, 20, 30, 40, 50, 60}, כנדרש.

תשובה: לפני הזימון brr = {50, 60, 10, 20, 30, 40}.

סעיף ו

תשובה:

הזזה מעגלית (סיבוב) של המערך d מקומות שמאלה: a[i] מקבל את הערך שהיה ב-a[(i+d)%n].

כל קריאה של `why` שומרת את `a[(i+d)%n]` לפני הקריאה הרקורסיבית וכותבת אותו ל-`a[i]` רק בשלב החזרה, אחרי שכל הערכים המקוריים כבר נקראו. לכן אף ערך לא הולך לאיבוד, ובסוף a[i]a[i] מכיל את הערך שהיה במקום (i+d)%n(i+d)\%n.

כלומר כל איבר זז d מקומות שמאלה, ו-d האיברים הראשונים עוברים לסוף המערך. כך ראינו בסעיף ד: {10, 3, 6, 8, 2, 11, 5} הפך ל-{8, 2, 11, 5, 10, 3, 6}. זו הפעולה ההפוכה ל-secret, שמזיזה ימינה.

תשובה: what מזיזה את איברי המערך באופן מעגלי d מקומות שמאלה (d האיברים הראשונים עוברים לסוף).

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

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

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