מתכונת 8 במדעי המחשב - יסודות מדעי המחשב 899371

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

רעיון: הלולאה עוברת על זוגות סימטריים במערך: התא הראשון עם האחרון, השני עם הלפני־אחרון וכן הלאה. j = a.length-1-i הוא המציין של "בן הזוג" של i. התנאי i < a.length/2 = 5 אומר שיש 5 איטרציות (i = 0..4) – בדיוק חצי מערך, כך שכל זוג נבדק פעם אחת. כאשר האיבר השמאלי גדול מבן הזוג שלו, ההפרש a[i] - a[j] נכתב ל־b במקום k, ו־k גדל ב־1.

פתרון – טבלת מעקב (בעמודה b[k] רשומה ההשמה כשהיא מתבצעת; k אחרי ביצוע גוף הלולאה):

המערך b לאחר ביצוע קטע התכנית:

בדיקה: על המערכים הנתונים מתקבל b = 7 9 3 0 0 ו־k = 3.

טעות נפוצה: להמשיך את הלולאה עד סוף המערך (i עד 9). הלולאה עוצרת באמצע, ולכן כל זוג נבדק פעם אחת בלבד – ו־b בגודל 5 מספיק.

מה נדרש: מערך a בגודל 10 עם מספרים גדולים מ־0, שבעבורו בסוף הביצוע אף תא של b לא יהיה 0.

רעיון: ל־b נכתב ערך רק כאשר a[i] > a[j], והערך שנכתב הוא a[i] - a[j] – מספר חיובי, כלומר שונה מ־0. יש בדיוק 5 איטרציות ו־5 תאים ב־b, ובכל השמה k מתקדם בתא אחד. לכן כל תאי b יתמלאו בערכים שונים מ־0 אם ורק אם התנאי מתקיים בכל 5 האיטרציות: a[0] > a[9], a[1] > a[8], a[2] > a[7], a[3] > a[6], a[4] > a[5].

פתרון: דוגמה מייצגת – מערך יורד:

ואז b = 9, 7, 5, 3, 1.

(המערך לא חייב להיות יורד. גם 6, 7, 9, 5, 8, 2, 4, 1, 3, 5 מתאים – כל זוג סימטרי מקיים את התנאי – ואז b = 1, 4, 8, 1, 6.)

בדיקה: בשתי הדוגמאות מתקבל b = 9 7 5 3 1 ו־b = 1 4 8 1 6, ובשתיהן k = 5. לעומת זאת, על המערך העולה 1, 2, …, 10 התקבל b = 0 0 0 0 0.

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

מה נדרש
לסדר מחדש את arr כך שבתחילתו יופיע כל מספר פעם אחת, לפי סדר ההופעה הראשונה שלו, ובשאר התאים ‎-1. הפעולה לא מחזירה ערך – היא משנה את arr עצמו.

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

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

פתרון

Java

public static void keepFirst(int[] arr)
{
    int[] temp = new int[arr.length];
    int k = 0;    // כמה מספרים שונים כבר הועתקו ל-temp
    for (int i = 0; i < arr.length; i++)
    {
        // חיפוש סדרתי: האם arr[i] כבר נמצא ב-temp?
        boolean found = false;
        for (int j = 0; j < k && !found; j++)
        {
            if (temp[j] == arr[i])
                found = true;
        }
        if (!found)
        {
            temp[k] = arr[i];
            k++;
        }
    }
    // העתקה חזרה ל-arr והשלמת התאים הנותרים ב-1-
    for (int i = 0; i < arr.length; i++)
    {
        if (i < k)
            arr[i] = temp[i];
        else
            arr[i] = -1;
    }
}

C#

public static void KeepFirst(int[] arr)
{
    int[] temp = new int[arr.Length];
    int k = 0;    // כמה מספרים שונים כבר הועתקו ל-temp
    for (int i = 0; i < arr.Length; i++)
    {
        // חיפוש סדרתי: האם arr[i] כבר נמצא ב-temp?
        bool found = false;
        for (int j = 0; j < k && !found; j++)
        {
            if (temp[j] == arr[i])
                found = true;
        }
        if (!found)
        {
            temp[k] = arr[i];
            k++;
        }
    }
    // העתקה חזרה ל-arr והשלמת התאים הנותרים ב-1-
    for (int i = 0; i < arr.Length; i++)
    {
        if (i < k)
            arr[i] = temp[i];
        else
            arr[i] = -1;
    }
}

בדיקה
על מערך הדוגמה {12, 7, 12, 5, 7, 7, 30, 5}:

גם המקרים {4, 4, 4} ← {4, -1, -1}, ‏{1, 2, 3} ← ללא שינוי, ‏{9} ← {9} ו-{3, 1, 3, 2, 1, 2} ← {3, 1, 2, -1, -1, -1} עובדים.

טעות נפוצה: לחפש את arr[i] בכל המערך arr (ולא רק בחלק שכבר נבנה) – כך כל מספר שמופיע פעמיים "נמצא" כבר בהופעה הראשונה שלו ולא נכנס כלל. טעות נוספת: לשכוח למלא את התאים הנותרים ב-‎-1 – אז נשארים בהם הערכים הישנים.

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

רעיון

פתרון

Java

public static boolean isSpy(int num)
{
    int sum = 0;
    int mult = 1;
    int temp = num;    // עובדים על עותק, כדי לא להרוס את num
    while (temp > 0)
    {
        int digit = temp % 10;
        sum = sum + digit;
        mult = mult * digit;
        temp = temp / 10;
    }
    return sum == mult;
}

C#

public static bool IsSpy(int num)
{
    int sum = 0;
    int mult = 1;
    int temp = num;    // עובדים על עותק, כדי לא להרוס את num
    while (temp > 0)
    {
        int digit = temp % 10;
        sum = sum + digit;
        mult = mult * digit;
        temp = temp / 10;
    }
    return sum == mult;
}

בדיקה

isSpy(1124) = true, isSpy(123) = true, isSpy(22) = true, isSpy(7) = true, isSpy(1412) = true; ‏isSpy(1234) = false, isSpy(10) = false, isSpy(105) = false, isSpy(2222) = false, isSpy(99) = false.

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

מה נדרש
להדפיס את כל "מספרי המרגל" מ-1 עד n, תוך שימוש ב-isSpy מסעיף א.

רעיון
לולאה על i מ-1 עד n (כולל); לכל i קוראים ל-isSpy(i), ואם התשובה true – מדפיסים את i.

פתרון

Java

public static void printSpies(int n)
{
    for (int i = 1; i <= n; i++)
    {
        if (isSpy(i))
        {
            System.out.println(i);
        }
    }
}

C#

public static void PrintSpies(int n)
{
    for (int i = 1; i <= n; i++)
    {
        if (IsSpy(i))
        {
            Console.WriteLine(i);
        }
    }
}

בדיקה
שימו לב: כל מספר חד-ספרתי הוא "מספר מרגל" (הסכום והמכפלה של ספרה אחת שווים לה עצמה), ולכן ההדפסה תמיד מתחילה ב-1.
printSpies(2000) מדפיסה (כל מספר בשורה נפרדת):
1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 123, 132, 213, 231, 312, 321, 1124, 1142, 1214, 1241, 1412, 1421
ו־printSpies(1) מדפיסה רק 1. התוצאות זהות לבדיקה עצמאית שכתבנו בנפרד (פירוק המספר כמחרוזת ספרות).

מה נדרש: פעולה פנימית במחלקה RiverGauge שסופרת את ימי ה"שיא" (peak = true) או את ימי ה"שפל" (peak = false).

רעיון: יום i הוא "שיא" אם levels[i] > levels[i-1] וגם levels[i] > levels[i+1], ו"שפל" אם levels[i] < levels[i-1] וגם levels[i] < levels[i+1]. לכל יום צריך גם את היום הקודם וגם את היום הבא, ולכן הלולאה רצה מ־1 עד levels.length - 2 (בלי היום הראשון והאחרון – כך גם אין חריגה מגבולות המערך). סופרים רק את סוג הימים שהפרמטר מבקש.

פתרון: הקוד המלא – בלשונית Java/C# (שתי הפעולות של סעיפים א ו־ב כתובות בתוך המחלקה RiverGauge).

בדיקה: על המערך שבשאלה:

מתקבל countTurns(true) = 3 ו־countTurns(false) = 1, כמו בשאלה. עבור מערך עולה (5 , 6 , 7 , 8) התקבל 0 לשני הסוגים, ועבור מערך של יום אחד – 0.

טעות נפוצה: להריץ את הלולאה מ־0 או עד levels.length - 1 ולגשת ל־levels[i-1] או ל־levels[i+1] מחוץ לגבולות המערך; או להשתמש ב־>= ולספור את יום 2 בדוגמה (128 , 128).

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

רעיון: countTurns(true) + countTurns(false) הוא מספר הימים שהם "שיא" או "שפל" (יום לא יכול להיות גם וגם). "גדול ממחצית" – בודקים turns * 2 > levels.length, וכך אין צורך בחילוק (ואין חשש מחילוק שלמים שמעגל כלפי מטה). אפשר גם לכתוב turns > levels.length / 2.0.

פתרון:

public boolean isRestless()
{
    int turns = countTurns(true) + countTurns(false);
    return turns * 2 > levels.length;
}

בדיקה: בדוגמה 4 · 2 = 8 > 9 לא מתקיים → false. עבור 50 , 60 , 40 , 70 , 30 , 55 יש 2 "שיא" ו־2 "שפל": 8 > 6 → true. עבור 10 , 20 , 10 , 20 יש 2 ימים מיוחדים מתוך 4 – בדיוק מחצית, לא יותר → false.

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

מה נדרש: פעולה פנימית ב־ Seat הבודקת אם שני מושבים צמודים.

רעיון: שני תנאים שחייבים להתקיים יחד (&&): אותה שורה, וההפרש בין מספרי המושבים הוא 1 בדיוק. ההפרש יכול להיות 1 או −1 (המושב השני משמאל או מימין), ולכן משתמשים בערך מוחלט: Math.abs (ב־ C#: Math.Abs).

פתרון: הקוד המלא – בלשונית Java / C#.

בדיקה: 7/12 מול 7/13 → true; 7/13 מול 7/12 → true; 7/12 מול 7/14 → false; 7/12 מול 8/13 → false; 7/12 מול 7/12 → false.

טעות נפוצה: לבדוק רק number − other.getNumber() == 1 – כך מושב שנמצא משמאל לא ייחשב צמוד.

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

רעיון: section הוא מטיפוס char, ולכן משווים אותו ישירות עם == ל־ other.getSection().

פתרון: הקוד המלא – בלשונית Java / C#.

בדיקה: אגף B מול אגף B → true; אגף B מול אגף C → false.

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

רעיון: זו מחלקה מורכבת – התכונה seat היא עצם מטיפוס Seat. את בדיקת הצמידות מעבירים לפעולה isNextTo של העצם seat:
this.seat.isNextTo(other.getSeat()), ומחברים עם sameSection(other) ב־ &&. בדיקת האגף הכרחית: שורה 7 מושב 12 באגף B ושורה 7 מושב 13 באגף C אינם צמודים באמת.

פתרון: הקוד המלא – בלשונית Java / C#.

בדיקה: B 7/12 מול B 7/13 → true; B 7/12 מול C 7/13 → false (אגף שונה); B 7/12 מול B 6/13 → false (שורה שונה).

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

רעיון: לולאה כפולה עם מונה. לכל כרטיס i מאפסים מונה, עוברים על כל הכרטיסים j, ואם j ≠ i ו־ tickets[i].sitTogether(tickets[j]) – מגדילים את המונה. בסוף הלולאה הפנימית, אם המונה שווה ל־ 2 – מדפיסים את getBuyerCode() של כרטיס i.
מכיוון שאין שני כרטיסים לאותו מושב, לכל כרטיס יש לכל היותר 2 שכנים (משמאל ומימין), ולכן הבדיקה == 2 שקולה ל־ >= 2.
(התנאי i != j אינו הכרחי כאן, כי מושב אינו צמוד לעצמו – ההפרש 0 – אבל הוא מבהיר את הכוונה.)

פתרון: הקוד המלא – בלשונית Java / C#.

בדיקה: מערך של 8 כרטיסים: 4101 = B 7/12, 4102 = B 7/13, 4103 = B 7/11, 4104 = C 7/14, 4105 = B 3/5, 4106 = B 3/6, 4107 = B 3/7, 4108 = A 7/12. לכרטיס 4101 שני שכנים (4102 ו־ 4103), לכרטיס 4106 שני שכנים (4105 ו־ 4107). לכרטיס 4102 שכן אחד בלבד – 4104 נמצא באגף אחר. מודפסים (כל אחד בשורה): 4101, 4106.

טעות נפוצה: להתחיל את הלולאה הפנימית מ־ j = i + 1 – כך לא נספרים השכנים שמופיעים במערך לפני i, ו"כרטיס אמצעי" עלול לא להיות מודפס.

מה נדרש: לחשב את "שורש המכפלה" – להפעיל את digitProduct שוב ושוב עד שמתקבל מספר חד־ספרתי.

רעיון: לולאת while: כל עוד num אינו חד־ספרתי (num >= 10) מחליפים אותו במכפלת ספרותיו. מספר חד־ספרתי (כולל 0) מוחזר כמו שהוא – הלולאה לא מתבצעת אף פעם.

פתרון:

public static int productRoot(int num)
{
    while (num >= 10)
    {
        num = digitProduct(num);
    }
    return num;
}

בדיקה: productRoot(7) = 7, ‏productRoot(39) = 4, ‏productRoot(25) = 0, ‏productRoot(4448) = 0 (512 → 10 → 0), ‏productRoot(77) = 8 (49 → 36 → 18 → 8), ‏productRoot(0) = 0.

טעות נפוצה: תנאי num > 10 – עבור 10 הלולאה לא מתבצעת ומוחזר 10, שאינו חד־ספרתי.

מה נדרש: לבדוק את הטענה על כל המספרים 1 עד 99999 ולהחזיר true אם ליותר מ־ 80% מהם "שורש מכפלה" 0.

רעיון: עוברים בלולאה על כל i מ־ 1 עד 99999, ומונים את המספרים שעבורם productRoot(i) == 0 (סעיף א(1)). "יותר מ־ 80 אחוזים" פירושו countZero / 99999 > 0.8. כדי להימנע מחילוק (ומחילוק בשלמים שמאבד את השבר) כופלים את שני האגפים: countZero × 100 > 99999 × 80. הערכים כאן (עד כ־ 10 מיליון) נכנסים בטיפוס int.

פתרון:

public static boolean isCorrect()
{
    int countZero = 0;
    for (int i = 1; i <= 99999; i++)
    {
        if (productRoot(i) == 0)
            countZero++;
    }
    return countZero * 100 > 99999 * 80;
}

בדיקה: מתקבל countZero = 82401 מתוך 99999 (כ־ 82.4%), ולכן הפעולה מחזירה true – הטענה נכונה.

טעות נפוצה: לכתוב countZero / 99999 > 0.8 – בחילוק בשלמים המנה היא 0, והתוצאה תמיד false.

מה נדרש: להשוות בין מספר ההופעות של שורש המכפלה של כל מספר בתוך המספר השני.

רעיון:

פתרון:

public static boolean isStronger(int num1, int num2)
{
    int count1 = countDigit(num2, productRoot(num1));
    int count2 = countDigit(num1, productRoot(num2));
    return count1 > count2;
}

בדיקה: isStronger(39, 4448) → true (3 > 0); ‏isStronger(4448, 39) → false (0 > 3 לא מתקיים); ‏isStronger(77, 88) → true (השורש של 77 הוא 8 ומופיע פעמיים ב־ 88; השורש של 88 הוא 8 ואינו מופיע ב־ 77); ‏isStronger(48, 84) → false (שני השורשים 6, ואינם מופיעים – 0 מול 0).

טעות נפוצה: להחליף את המספרים בקריאה – countDigit(num1, productRoot(num1)) – כלומר לחפש את השורש של מספר בתוך אותו מספר עצמו.