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

מה נדרש: לעקוב אחרי ביצוע הקטע (עמודות a, b, big, small) ולכתוב מה יודפס.

רעיון: בכל סיבוב בוחרים את הגדול (big) ואת הקטן (small) מבין a ו־ b, מציבים ב־ a את ההפרש big − small וב־ b את הקטן. הלולאה נמשכת כל עוד a ≠ b. זהו אלגוריתם אוקלידס בגרסת החיסור, ולכן הערך המודפס הוא המחלק המשותף הגדול ביותר של 84 ו־ 30.

פתרון – טבלת מעקב:

הקטע מדפיס: 6

בדיקה: הפלט של הקטע הוא 6, והוא אכן המחלק המשותף הגדול ביותר של 84 ו־ 30.

טעות נפוצה: להציב ב־ b את big במקום את small, או להתבלבל בסדר: a מקבל את ההפרש, ו־ b מקבל את הקטן – גם כאשר הקטן היה a.

מה נדרש: ערכים התחלתיים שונים, גדולים מ־ 1, שבעבורם יודפס 1.

רעיון: חיסור הקטן מן הגדול אינו משנה את המחלקים המשותפים של שני המספרים, לכן בסוף a = b = המחלק המשותף הגדול ביותר של הערכים ההתחלתיים. יודפס 1 בדיוק כאשר למספרים אין מחלק משותף גדול מ־ 1 (מספרים זרים).

פתרון: למשל a = 9, b = 4: (9,4) → (5,4) → (1,4) → (3,1) → (2,1) → (1,1) – יודפס 1.
(מתאימים גם 5 ו־ 3, 8 ו־ 15, 10 ו־ 7 וכו'.)

בדיקה: עם a = 9, b = 4 הפלט הוא 1. בדיקה על כל הזוגות השונים בתחום 2–40 הראתה שמודפס 1 בדיוק בעבור הזוגות הזרים.

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

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

פתרון:

public static boolean playSong(int[] recent, int song)
{
    int pos = -1;
    for (int i = 0; i < recent.length && pos == -1; i++)
    {
        if (recent[i] == song)
            pos = i;
    }
    boolean isNew = (pos == -1);
    if (isNew)
        pos = recent.length - 1;
    for (int i = pos; i > 0; i--)
    {
        recent[i] = recent[i - 1];
    }
    recent[0] = song;
    return isNew;
}

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

טעות נפוצה: להזיז משמאל לימין (for i = 1 ...: recent[i] = recent[i-1]) – כך הערך של תא 0 מועתק לכל התאים. טעות נוספת: כאשר השיר כבר נמצא, להזיז את כל המערך ימינה – כך השיר מופיע פעמיים והשיר שבתא האחרון נמחק בטעות.

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

רעיון: מפרקים את המספר לספרות מהסוף להתחלה: num % 10 היא ספרת האחדות, ו־num / 10 מוריד אותה. הספרה עצמה משמשת מציין במערך המונים, ולכן counts[num % 10]++ מוסיף 1 בדיוק לתא של הספרה הזאת. ממשיכים כל עוד num > 0. מערך חדש מאותחל אוטומטית לאפסים.

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

בדיקה:

טעות נפוצה: לכתוב counts[i]++ עם מונה לולאה במקום להשתמש בספרה עצמה כמציין, או לעצור כש־num % 10 == 0 – אז האפסים במספר כמו 1000000 לא ייספרו.

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

רעיון:

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

בדיקה: בדוגמה מהשאלה: 1203 (ספרות 1,2,0,3), 3315 (3,3,1,5), 90 (9,0), ואז 444 – זוכה. total: לספרה 3 – 3 הופעות, ל־0 ול־1 – 2, ל־2, 5, 9 – 1. מודפס 3. מקרים נוספים: 12, 21, 5 ⇒ תיקו בין 1 ל־2 ⇒ מודפס 1; 505, 6 ⇒ מודפס 5.

טעות נפוצה: לבדוק "כרטיס זוכה" בעזרת num % 11 == 0 או השוואה לספרה הראשונה בלבד. הבדיקה הנכונה היא שבמערך המונים יש תא אחד בלבד שאינו 0.

מה נדרש: פעולה בונה Parking(lotID, ratePerHour) שיוצרת חנייה של שעה אחת של נהג שאינו תושב העיר.

רעיון: את lotID ו־ ratePerHour מעתיקים מהפרמטרים; hours מקבלת 1 ו־ resident מקבלת false ("אינו תושב העיר"). (בקוד מוצגות גם הגדרות התכונות של המחלקה.)

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

בדיקה: new Parking(7, 12.5) – מתקבלים lotID = 7, ratePerHour = 12.5, hours = 1, resident = false.

מה נדרש: סכום החנייה הבסיסי, בלי הנחה ובלי תקרה.

רעיון: הסכום הוא התעריף לשעה כפול מספר השעות: ratePerHour * hours (התוצאה ממשית כי ratePerHour ממשי).

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

בדיקה: תעריף 12.5 ו־ 4 שעות – הוחזר 50.0; תעריף 12 ו־ 10 שעות – הוחזר 120.0.

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

רעיון:

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

בדיקה:

טעות נפוצה: לבדוק את התקרה לפני ההנחה (על basePrice). תושב שחנה 6 שעות בתעריף 12.5 ישלם אז 60 * 0.6 = 36 במקום 45 – ההנחה מחושבת קודם, ורק אחר כך התקרה.

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

רעיון: מספר החניון (0–29) משמש ישירות כאינדקס. יוצרים double[30] (כל התאים מאותחלים ל־ 0), ועוברים פעם אחת על dayParkings: לכל חנייה מוסיפים את finalPrice() לתא שהאינדקס שלו הוא getLotID(). הצבירה היא של הסכום הסופי (פעולה ב(2)), לא של basePrice.

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

בדיקה: חניות: (חניון 3, 10 ש"ח × 2 שעות, לא תושב) → 20, (חניון 0, 8 × 3, תושב) → 14.4, (חניון 3, 15 × 5, לא תושב) → 60 (תקרה), (חניון 29, 9 × 4, לא תושב) → 36, (חניון 3, 12.5 × 6, תושב) → 45. התקבל מערך בגודל 30 ובו תא 3 = 125.0 (כמו בדוגמה), תא 0 ≈ 14.4, תא 29 = 36.0, ושאר התאים 0.

טעות נפוצה: להגדיר מערך int – ההכנסות הן מספרים ממשיים (למשל 14.4), ולכן המערך חייב להיות מטיפוס double.

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

רעיון: חיפוש מקסימום, שבו ההשוואה בין שני מקומות נעשית בפעולה northOf של Location. שומרים את האינדקס של המשלוח ה"צפוני" ביותר עד כה (מתחילים מ־0), ועוברים על שאר התאים: אם מקום האיסוף של orders[i] צפוני למקום האיסוף של המשלוח השמור – מעדכנים. בסוף מדפיסים את קוד ההזמנה.

פתרון: הקוד המלא – בלשונית Java/C#. בשרשרת orders[i].getPickup().northOf(orders[maxIndex].getPickup()) מקבלים קודם את עצם ה־Location של מקום האיסוף, ועליו מפעילים את northOf.

בדיקה: 5 משלוחים שמקומות האיסוף שלהם ברחובות 34 , 87 , 12 , 95 , 60. המשלוח D-404 נאסף מרחוב 95 – מודפס D-404. במערך של משלוח אחד מודפס הקוד שלו.

טעות נפוצה: להשוות את מקומות המסירה (dropoff) במקום מקומות האיסוף, או לכתוב orders[i].getPickup() > ... – אי אפשר להשוות עצמים באופרטור >.

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

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

פתרון:

public int distance()
{
    return pickup.blocks(dropoff);
}

(אפשר גם getPickup().blocks(getDropoff()).)

בדיקה: איסוף ברחוב 34 שדרה 5, מסירה ברחוב 40 שדרה 7 → 6 + 2 = 8; איסוף 95/9, מסירה 70/3 → 25 + 6 = 31.

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

רעיון: לכל משלוח מוסיפים 15 שקלים. מחשבים d = distance(); אם d > 10, הבלוקים החל מה־11 הם d - 10 בלוקים, ועל כל אחד מוסיפים 2 שקלים. סוכמים על כל המערך.

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

בדיקה:

הפעולה החזירה 119 = 15 + 17 + 15 + 57 + 15.

טעות נפוצה: לשלם 2 שקלים על כל הבלוקים כשהמשלוח ארוך מ־10 בלוקים, או לשכוח את 15 השקלים של משלוח קצר (משלוח של 10 בלוקים בדיוק מקבל 15 שקלים בלבד).

מה נדרש
לבדוק אם ל-num יש מחלק בין 2 ל-num − 1.

רעיון
מחפשים מחלק d החל מ-2. מספיק לבדוק עד √num (התנאי d * d <= num): אם num = d · e ושני הגורמים גדולים מ-√num, המכפלה הייתה גדולה מ-num. ברגע שנמצא מחלק – מחזירים false; אם לא נמצא – true. (גם לולאה עד num − 1 נכונה, רק איטית יותר.)

פתרון
Java

// סעיף א(1)
public static boolean isPrime(int num)
{
    for (int d = 2; d * d <= num; d++)
    {
        if (num % d == 0)
        {
            return false;
        }
    }
    return true;
}

C#

// סעיף א(1)
public static bool IsPrime(int num)
{
    for (int d = 2; d * d <= num; d++)
    {
        if (num % d == 0)
        {
            return false;
        }
    }
    return true;
}

בדיקה

טעות נפוצה: לכתוב d * d < num – אז ריבוע של ראשוני (למשל 49 או 9) מזוהה בטעות כראשוני.

מה נדרש
להדפיס כל זוג p, p + 2 ששניהם ראשוניים ושניהם בתחום [low, high].

רעיון
עוברים על כל p מ-low. כדי שגם p + 2 יהיה בתחום, הלולאה רצה כל עוד p + 2 <= high. לכל p בודקים בעזרת סעיף א(1) אם p ראשוני וגם p + 2 ראשוני, ואם כן – מדפיסים את הזוג.

פתרון
Java

// סעיף א(2)
public static void printTwins(int low, int high)
{
    for (int p = low; p + 2 <= high; p++)
    {
        if (isPrime(p) && isPrime(p + 2))
        {
            System.out.println(p + " " + (p + 2));
        }
    }
}

C#

// סעיף א(2)
public static void PrintTwins(int low, int high)
{
    for (int p = low; p + 2 <= high; p++)
    {
        if (IsPrime(p) && IsPrime(p + 2))
        {
            Console.WriteLine(p + " " + (p + 2));
        }
    }
}

בדיקה

טעות נפוצה: להריץ את הלולאה עד p <= high – אז עלול להיות מודפס זוג שהמספר השני שבו גדול מ-high (למשל בעבור high = 41 יודפס 41 43).

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

רעיון
לולאה חיצונית על המספרים הזוגיים n = 4, 6, ..., 10000 (קפיצות של 2). לכל n – חיפוש סדרתי של ראשוני p כך ש-n − p גם ראשוני. מספיק לחפש p עד n / 2 (אם p > n/2, אז n − p < n/2 והזוג כבר נבדק בסדר ההפוך). משתנה found עוצר את החיפוש כשנמצא פירוק. אם בסוף החיפוש found הוא false – זו דוגמה נגדית, ומחזירים false מיד. אם כל המספרים עברו – מחזירים true.

פתרון
Java

// סעיף ב
public static boolean goldbach()
{
    for (int n = 4; n <= 10000; n = n + 2)
    {
        boolean found = false;
        for (int p = 2; p <= n / 2 && !found; p++)
        {
            if (isPrime(p) && isPrime(n - p))
            {
                found = true;
            }
        }
        if (!found)
        {
            return false;
        }
    }
    return true;
}

C#

// סעיף ב
public static bool Goldbach()
{
    for (int n = 4; n <= 10000; n = n + 2)
    {
        bool found = false;
        for (int p = 2; p <= n / 2 && !found; p++)
        {
            if (IsPrime(p) && IsPrime(n - p))
            {
                found = true;
            }
        }
        if (!found)
        {
            return false;
        }
    }
    return true;
}

בדיקה

הפעולה מחזירה true.

טעות נפוצה: להתחיל את החיפוש של p מ-3 ("ראשוני אי-זוגי") – אז 4 = 2 + 2 לא נמצא והפעולה מחזירה false. או לכתוב return true בתוך הלולאה החיצונית מיד אחרי המספר הראשון שנמצא לו פירוק.