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

מה נדרש: לעקוב אחרי ביצוע הלולאה על המערך הנתון (עמודות i , arr[i] , count) ולרשום את המערך בסוף.

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

פתרון – טבלת מעקב (לפני הלולאה: count = 0)

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

בדיקה: הקטע מדפיס 2 7 3 5 18 3 15, בדיוק כמו בטבלה.

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

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

רעיון: מתי תא הופך ל־0?

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

פתרון: למשל המערך:

אחרי הביצוע: 0 , 0 , 0 , 3 , 5 – בדיוק שלושה אפסים.

בדיקה: על {7,1,3,6,5} מתקבל 0 0 0 3 5, ועל {1,3,5,2,4} מתקבל 0 0 0 1 2. בנוסף בדקנו בתוכנית את כל המערכים בגודל 5 עם ערכים מ־5− עד 5 (ללא 0): יש בדיוק שלושה אפסים אם ורק אם שלושת התאים הראשונים אי־זוגיים ו־arr[3] זוגי.

טעות נפוצה: לבחור למשל {1, 3, 5, 7, 2} – כאן ארבעה תאים אי־זוגיים מופיעים לפני הזוגי הראשון, ולכן מתקבלים ארבעה אפסים ולא שלושה.

מה נדרש: פעולה המחזירה בכמה מעלות הטמפרטורה חורגת מן הטווח [low, high], או 0 אם היא בתוכו.

רעיון: אם temp < low – החריגה היא המרחק עד low, כלומר low − temp (מספר חיובי). אם temp > high – החריגה היא temp − high. אחרת הטמפרטורה בטווח (כולל הגבולות) ומחזירים 0.

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

if (temp < low) return low - temp;
if (temp > high) return temp - high;
return 0;

בדיקה: low = 2, high = 8: עבור 11 → 3, עבור -1 → 2 − (−1) = 3, עבור 2 → 0, עבור 8 → 0, עבור 5 → 0.

טעות נפוצה: להחזיר temp − low כאשר הטמפרטורה נמוכה מדי – מתקבל מספר שלילי (עבור -1: −3) במקום הסטייה החיובית 3.

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

רעיון: יוצרים מערך result בגודל temps.length ועוברים על כל האינדקסים: result[i] = getDeviation(temps[i], low, high). המערך temps רק נקרא.

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

בדיקה: על המערך מהדוגמה (low = 2, high = 8) התקבל [0, 1, 3, 0, 1, 3, 0], כמו בשאלה, והמערך temps נשאר ללא שינוי.

מה נדרש: להחזיר true אם אין מדידה עם סטייה גדולה מ־ 3 ואין שתי מדידות רצופות מחוץ לטווח.

רעיון: מקבלים את מערך הסטיות dev מ־ getAllDeviations. מדידה מחוץ לטווח היא מדידה שהסטייה שלה גדולה מ־ 0. עוברים על המערך: אם dev[i] > 3 – המשלוח נפסל. אם i > 0 ושני התאים dev[i] ו־ dev[i − 1] גדולים מ־ 0 – שתי מדידות רצופות מחוץ לטווח, והמשלוח נפסל. אם הלולאה הסתיימה בלי לפסול – מחזירים true.

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

בדיקה (low = 2, high = 8):

טעות נפוצה: לבדוק dev[i + 1] בלולאה עד i < dev.length – חריגה מגבולות המערך בתא האחרון. לכן משווים כל תא לתא שלפניו ומתחילים את בדיקת הזוג מ־ i = 1 (התנאי i > 0).

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

רעיון:

פתרון:

public static void fillTicket(int[] arr)
{
    Random rnd = new Random();
    int count = 0;
    while (count < arr.length)
    {
        int num = rnd.nextInt(37) + 1;
        boolean found = false;
        for (int i = 0; i < count; i++)
        {
            if (arr[i] == num)
                found = true;
        }
        if (!found)
        {
            arr[count] = num;
            count++;
        }
    }
    for (int i = 0; i < arr.length; i++)
    {
        System.out.println(arr[i]);
    }
}

(ב־ Java צריך import java.util.Random; בראש הקובץ. אפשר גם להגריל בעזרת (int)(Math.random() * 37) + 1 .)

בדיקה: על מערך בגודל 6 מתקבל למשל 37 30 28 8 34 23 – כל הערכים בין 1 ל־ 37 , שונים זה מזה, והשורות שמודפסות זהות לתאי המערך. בדיקה קשה יותר: מערך בגודל 37 – הכרטיס חייב להכיל בדיוק את כל המספרים 1 עד 37 . ובמערך בגודל 37 מתקבל תמיד סידור של כל 37 המספרים.

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

מה נדרש: לממש את הפעולה הבונה Container(code, num).

רעיון: הפעולה מציבה את הקוד בתכונה code ויוצרת מערך חדש של num הפניות לעצמים מטיפוס Sack (תאיו null – השקים עוד לא הוכנסו). כיוון ששם הפרמטר code זהה לשם התכונה, חובה לכתוב this.code = code;.

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

בדיקה: אחרי new Container("TST-1", 4) התקבל (בשתי השפות): code = "TST-1", אורך sacks הוא 4, ו־sacks[3] הוא null.

טעות נפוצה: לכתוב code = code; – ההשמה היא של הפרמטר לעצמו, והתכונה code נשארת null.

מה נדרש: להחזיר true אם המשקל הכולל של המכולה גדול מ־limit.

רעיון: את המשקל הכולל מחשבת הפעולה totalWeight, שמותר להשתמש בה בלי לממש אותה. מזמנים אותה על העצם הנוכחי ומחזירים ישירות את תוצאת ההשוואה totalWeight() > limit (אין צורך ב־if).

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

בדיקה (limit = 180):

טעות נפוצה: לכתוב >= – מכולה שמשקלה שווה בדיוק ל־limit אינה חורגת (ראו VN-505 עם limit = 300 בסעיף ג).

מה נדרש: פעולה חיצונית שמדפיסה את הקודים של המכולות שמשקלן אינו גדול מ־limit.

רעיון: עוברים על כל המכולות. מכולה יכולה לצאת למשלוח בדיוק כאשר isOverweight(limit) מחזירה false, ולכן התנאי הוא השלילה !port[i].isOverweight(limit). את limit מעבירים הלאה לפעולה של המכולה. הקוד מודפס בעזרת getCode(), כי התכונה code פרטית.

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

בדיקה: על חמש המכולות מהטבלה בסעיף ב מודפסים:

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

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

רעיון:

(אפשר גם לבדוק ישירות שלוש השוואות בערך מוחלט: |p−f| ≤ 1 && |p−t| ≤ 1 && |f−t| ≤ 1.)

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

בדיקה (נ – נוסעים, מ – משא, כ – מכל, א – אחר):

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

מה נדרש: להחזיר true אם יש לפחות מקטע אחד (מבין המקטעים הקבועים 0..m−1, m..2m−1, ...) שבו כל הקרונות הם קרונות נוסעים.

רעיון: "קיים מקטע כך שלכל קרון בו ...":

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

בדיקה:

טעות נפוצה: לחפש 4 קרונות נוסעים רצופים בכל מקום ברכבת (start++ במקום start += m). בדוגמה יש 4 קרונות נוסעים רצופים בתאים 1–4, אבל הם אינם מקטע אחד, ולכן התשובה בעבור m = 4 היא false.

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

רעיון
מפרקים את המספר לספרות בלולאה: הספרה הימנית היא temp % 10, ואחר כך מקצצים אותה בעזרת temp / 10, עד ש-temp מגיע ל-0. עובדים על עותק (temp) כי את num עצמו צריך בסוף לבדיקת החלוקה. num חיובי, ולכן sum ≥ 1 ואין חלוקה באפס.

פתרון
Java

// סעיף א(1)
public static boolean isHarshad(int num)
{
    int sum = 0;
    int temp = num;
    while (temp > 0)
    {
        sum = sum + temp % 10;
        temp = temp / 10;
    }
    return num % sum == 0;
}

C#

// סעיף א(1)
public static bool IsHarshad(int num)
{
    int sum = 0;
    int temp = num;
    while (temp > 0)
    {
        sum = sum + temp % 10;
        temp = temp / 10;
    }
    return num % sum == 0;
}

בדיקה

בין 1 ל-999 יש 212 מספרי הרשד.

טעות נפוצה: לפרק את num עצמו (num = num / 10) ואז לבדוק num % sum – בסוף הלולאה num כבר 0, והתשובה תמיד true.

מה נדרש
להדפיס את כל מספרי הרשד בתחום [low, high], כולל הקצוות.

רעיון
לולאה על כל המספרים מ-low עד high (כולל), ולכל מספר קריאה לפעולה מסעיף א(1).

פתרון
Java

// סעיף א(2)
public static void printHarshad(int low, int high)
{
    for (int i = low; i <= high; i++)
    {
        if (isHarshad(i))
        {
            System.out.println(i);
        }
    }
}

C#

// סעיף א(2)
public static void PrintHarshad(int low, int high)
{
    for (int i = low; i <= high; i++)
    {
        if (IsHarshad(i))
        {
            Console.WriteLine(i);
        }
    }
}

בדיקה

טעות נפוצה: לכתוב i < high – אז high עצמו (למשל 21 בדוגמה) לא נבדק.

מה נדרש
לבדוק אם בתחום 10–999,999 יש שישה מספרים עוקבים שכולם מספרי הרשד; להחזיר true אם אין רצף כזה.

רעיון
עוברים על המספרים לפי הסדר ומחזיקים מונה run – אורך הרצף הנוכחי של מספרי הרשד שמסתיים במספר הנוכחי. אם i הוא מספר הרשד – run גדל ב-1; אחרת – run מתאפס. ברגע ש-run מגיע ל-6 נמצא רצף כזה, ומחזירים false מיד. אם הלולאה הסתיימה – מחזירים true.

פתרון
Java

// סעיף ב
public static boolean noSixInRow()
{
    int run = 0;   // אורך הרצף הנוכחי של מספרי הרשד עוקבים
    for (int i = 10; i <= 999999; i++)
    {
        if (isHarshad(i))
        {
            run++;
            if (run == 6)
            {
                return false;
            }
        }
        else
        {
            run = 0;
        }
    }
    return true;
}

C#

// סעיף ב
public static bool NoSixInRow()
{
    int run = 0;   // אורך הרצף הנוכחי של מספרי הרשד עוקבים
    for (int i = 10; i <= 999999; i++)
    {
        if (IsHarshad(i))
        {
            run++;
            if (run == 6)
            {
                return false;
            }
        }
        else
        {
            run = 0;
        }
    }
    return true;
}

בדיקה
הפעולה מחזירה true. הרצף הארוך ביותר בתחום 10–999,999 הוא באורך 5, והוא מופיע פעמיים – 131052 עד 131056 ו-491424 עד 491428. (שימו לב: מחוץ לתחום יש רצפים ארוכים יותר – למשל 1 עד 10 הם עשרה מספרי הרשד עוקבים – ולכן ההשערה מנוסחת מ-10.)

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