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

מה נדרש
לעקוב אחר ביצוע הפעולה על המערך {6, 8, 3, 5, 5, 7, 9, 12, 4} בטבלת מעקב עם העמודות i, c, m, ולכתוב את הערך שהיא מחזירה.

רעיון

פתרון – טבלת מעקב
בכל שורה רשומים ערכי c ו-m בסוף הסיבוב.

כאשר i = 9 התנאי i < 9 אינו מתקיים, הלולאה מסתיימת והפעולה מחזירה את m.

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

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

בדיקה
על המערך הנתון מודפס 4. הדפסת c ו-m בסוף כל סיבוב נתנה בדיוק את השורות שבטבלה. בדיקות נוספות: {1, 2, 3} ← 3, ‏{3, 2, 1} ← 1, ‏{4} ← 1.

טעות נפוצה: להמשיך את הרצף כשיש שני איברים שווים (5, 5 בתאים 3–4). התנאי הוא > ולא >=, ולכן בשלב 4 c חוזר ל-1, והרצף 3, 5, 5, 7, 9, 12 אינו נספר כרצף אחד באורך 6.

מה נדרש: פעולה המסווגת בקבוק אחד: 1 (חסר), 2 (עודף – נפסל) או 0 (תקין).

רעיון: "קטנה ביותר מ־ tol מן הכמות הרצויה" פירושו target − volume > tol, כלומר volume < target − tol. באותו אופן "גדולה ביותר מ־ tol" פירושו volume > target + tol. בודקים את שני התנאים, ואם אף אחד מהם אינו מתקיים – מחזירים 0.

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

if (volume < target - tol) return 1;
if (volume > target + tol) return 2;
return 0;

בדיקה: target = 500, tol = 5: עבור 494 → 1, עבור 495 → 0 (סטייה של 5 בדיוק מותרת), עבור 505 → 0, עבור 506 → 2.

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

מה נדרש: מערך חדש באותו גודל, שבו כל תא הוא תוצאת getCheck על התא המתאים ב־ volumes.

רעיון: יוצרים מערך result בגודל volumes.length ועוברים בלולאה על כל האינדקסים: result[i] = getCheck(volumes[i], target, tol). המערך volumes רק נקרא – לא משנים אותו.

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

בדיקה: על המערך מהדוגמה (target = 500, tol = 5) התקבל [0, 1, 2, 0, 0, 2, 1], כמו בשאלה, והמערך volumes נשאר ללא שינוי.

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

רעיון: בקבוק תקין בדיוק כאשר הערך שלו במערך מ־ getAllChecks הוא 0. סופרים את התאים השווים ל־ 0 (ok) ובודקים ok < ¾·length. כדי להימנע משברים ומחילוק שלמים כופלים את שני האגפים ב־ 4: ok * 4 < volumes.length * 3.

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

בדיקה: בדוגמה 3 תקינים מתוך 7: 3·4 = 12 < 21 → true. נבדקו גם: 3 מתוך 4 → false (12 < 12 אינו מתקיים), 2 מתוך 4 → true, 6 מתוך 8 → false, 5 מתוך 7 → true (20 < 21).

טעות נפוצה: לכתוב ok < volumes.length * 3 / 4 – בחילוק שלמים 7·3 / 4 = 21 / 4 = 5, ואז 5 תקינים מתוך 7 (פחות מ־ 5.25) יחזירו false בטעות.

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

רעיון: עוברים על כל תווי המחרוזת. לכל תו בודקים לאיזה סוג הוא שייך בעזרת השוואת תווים: אות – בין 'a' ל־'z' או בין 'A' ל־'Z'; ספרה – בין '0' ל־'9'; אחרת – תו אחר. כאן מתאים if – else if – else, כי כל תו שייך לסוג אחד בדיוק. מגדילים את התא המתאים.

פתרון: הקוד המלא – בלשונית Java/C#. (ב־Java: pw.length() ו־pw.charAt(i); ב־C#: pw.Length ו־pw[i].)

בדיקה:

טעות נפוצה: לבדוק רק אותיות קטנות, או לכתוב c >= 0 && c <= 9 (מספרים) במקום '0' ו־'9' (תווים).

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

רעיון: לולאת זקיף שהתנאי שלה נבדק בעזרת analyze:

ב־Java קולטים מחרוזת בלי רווחים עם input.next(); ב־C# עם Console.ReadLine().

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

בדיקה: קלט: Gal#2026, tamar1234, Noa!5, Yoni$77$x, pass, 2580.

הפלט: 2,3. כשהסיסמה הראשונה היא #$% מודפס 0,0.

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

מה נדרש: פעולה פנימית במחלקה Greenhouse שמחזירה את אורך הרצף הארוך ביותר של "שעות חמות" (hot = true) או של "שעות קרות" (hot = false).

רעיון: זו בעיית "רצף מקסימלי". מחזיקים שני משתנים:

עוברים על כל התאים. שעה מהסוג המבוקש היא temps[i] > high כאשר hot הוא true, ו־temps[i] < low כאשר hot הוא false. אם השעה מהסוג המבוקש – מגדילים את count ובודקים אם הוא גדול מ־max; אחרת הרצף נקטע ומאפסים את count. אם אין אף שעה מתאימה, max נשאר 0. כיוון שהפעולה פנימית, ניגשים ישירות לתכונות temps , low , high.

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

בדיקה: בדוגמה (low = 18, high = 30):

מתקבל longestRun(true) = 3 ו־longestRun(false) = 2, כמו בשאלה. נבדק גם מערך שכולו "קר" (10 , 10 , 10 → 3, הרצף מסתיים בסוף המערך) ומערך עם טמפרטורות השוות בדיוק ל־low ול־high (18 , 30 , 24 → 0 לשני הסוגים).

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

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

רעיון: longestRun(true) נותנת את הרצף החם הארוך ביותר ו־longestRun(false) את הרצף הקר הארוך ביותר. "לא היה רצף של יותר משתיים" שקול ל"הרצף הארוך ביותר הוא לכל היותר 2". שני התנאים צריכים להתקיים – לכן &&.

פתרון:

public boolean isSafe()
{
    return longestRun(true) <= 2 && longestRun(false) <= 2;
}

בדיקה: בדוגמה הרצף החם הארוך ביותר הוא 3 > 2 ולכן false. עבור 20 , 31 , 31 , 25 , 17 , 17 , 22 (low = 18, high = 30) שני הרצפים באורך 2 בדיוק – התקבל true.

טעות נפוצה: לכתוב < 2 – רצף של שתי שעות בדיוק מותר. או לכתוב || במקום && – מספיק שאחד הרצפים ארוך מדי כדי שהחממה לא תהיה "בטוחה".

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

רעיון: חיפוש מקסימום, שבו ההשוואה בין שני קרטונים נעשית בפעולה biggerThan של Size. שומרים את האינדקס של החבילה עם הקרטון הגדול ביותר עד כה (מתחילים מ־0); אם הקרטון של shipments[i] גדול ממנו – מעדכנים. בסוף מדפיסים את הקוד.

פתרון: הקוד המלא – בלשונית Java/C#. בשרשרת shipments[i].getBox().biggerThan(shipments[maxIndex].getBox()) מקבלים את עצם ה־Size של הקרטון ועליו מפעילים את biggerThan.

בדיקה: 5 חבילות עם קרטונים בנפחים 6000 , 24000 , 4000 , 5000 , 13500 – מודפס PK-42 (הקרטון 40×30×20 = 24000).

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

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

רעיון: מפעילים את volume על הקרטון ועל המוצר ומחסירים.

פתרון:

public int emptySpace()
{
    return box.volume() - item.volume();
}

בדיקה: קרטון 30×20×10 = 6000 ומוצר 25×15×8 = 3000 → 3000; קרטון 30×30×15 = 13500 ומוצר 10×10×10 = 1000 → 12500.

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

רעיון: לכל חבילה מחשבים space = emptySpace() ובודקים את המדרגות מהגבוהה לנמוכה: יותר מ־8000 → 12 שקלים; אחרת, יותר מ־2000 → 5 שקלים; אחרת – 0. סוכמים על כל המערך.

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

בדיקה:

הפעולה החזירה 29 = 5 + 12 + 0 + 0 + 12. נבדקו גם מקרי הגבול: חלל ריק של 8000 בדיוק → 5, וחלל ריק של 2001 → 5.

טעות נפוצה: לבדוק קודם space > 2000 – אז גם חלל של 20000 מקבל 5 שקלים ולא 12. או לטעות בגבולות (2000 בדיוק – ללא עלות; 8000 בדיוק – 5 שקלים).

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

רעיון: לולאת while כל עוד num > 0: מחסירים מ־ num את maxDigit(num) ומגדילים מונה צעדים. כאשר num > 0 יש בו לפחות ספרה אחת שאינה 0, ולכן maxDigit(num) ≥ 1 והמספר קטן בכל צעד – הלולאה מסתיימת. עבור num = 0 הלולאה לא מתבצעת ומוחזר 0.

פתרון:

public static int stepsToZero(int num)
{
    int steps = 0;
    while (num > 0)
    {
        num = num - maxDigit(num);
        steps++;
    }
    return steps;
}

בדיקה: stepsToZero(0) = 0, ‏stepsToZero(7) = 1, ‏stepsToZero(10) = 2 (10 → 9 → 0), ‏stepsToZero(24) = 5, ‏stepsToZero(57) = 11, ‏stepsToZero(100) = 17.

טעות נפוצה: להחסיר את maxDigit של המספר המקורי בכל צעד (לחשב אותו פעם אחת לפני הלולאה) – הספרה הגדולה ביותר משתנה תוך כדי (ב־ 24: קודם 4, אחר כך 2, 8, 1, 9).

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

רעיון: עוברים בלולאה על כל i מ־ 1 עד 9999, מחשבים stepsToZero(i) (סעיף א(1)) וסופרים בשני מונים: זוגי ואי־זוגי. בסוף מחזירים countOdd > countEven.

פתרון:

public static boolean isCorrect()
{
    int countEven = 0;
    int countOdd = 0;
    for (int i = 1; i <= 9999; i++)
    {
        if (stepsToZero(i) % 2 == 0)
            countEven++;
        else
            countOdd++;
    }
    return countOdd > countEven;
}

בדיקה: מתקבל countEven = 5002, ‏countOdd = 4997, ולכן הפעולה מחזירה false – הטענה אינה נכונה (בהפרש קטן מאוד – אי אפשר לנחש את התשובה, ויש לחשב אותה).

טעות נפוצה: לבדוק את הזוגיות של i עצמו, או להחזיר countOdd >= countEven.

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

רעיון: מחשבים לכל מספר את מספר הצעדים שלו (סעיף א(1)) ובודקים בעזרת isPrime אם הוא ראשוני. "בדיוק אחד" = הראשון ראשוני והשני לא, או השני ראשוני והראשון לא. (אפשר גם לכתוב prime1 != prime2.)

פתרון:

public static boolean onlyOnePrime(int num1, int num2)
{
    boolean prime1 = isPrime(stepsToZero(num1));
    boolean prime2 = isPrime(stepsToZero(num2));
    return (prime1 && !prime2) || (!prime1 && prime2);
}

בדיקה: onlyOnePrime(24, 7) → true (5 ו־ 1); ‏onlyOnePrime(24, 10) → false (5 ו־ 2, שניהם ראשוניים); ‏onlyOnePrime(9, 0) → false (1 ו־ 0, אף אחד אינו ראשוני); ‏onlyOnePrime(100, 7) → true (17 ו־ 1).

טעות נפוצה: לכתוב prime1 || prime2 – זה "לפחות אחד" ולא "בדיוק אחד", ונותן true גם עבור 24 ו־ 10.