נסו בחינם — מדעי המחשב

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

לדוגמה: בסדרה 2 5 7 4 2 1 8 המספרים 7 ו-1 הם איברים מחליפי כיוון.

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

דוגמאות:

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

הערה: אפשר להשתמש בפעולות המחלקה Stack<T> בלי לממש אותן.

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

public static void doubleTurns(Stack<Integer> s)
{
    int cur;
    int next;
    Stack<Integer> temp = new Stack<Integer>();
    int prev = s.pop();              // האיבר הראשון – אינו מחליף כיוון
    temp.push(prev);
    while (!s.isEmpty())
    {
        cur = s.pop();
        temp.push(cur);
        if (!s.isEmpty())            // לאיבר האחרון אין שכן שני
        {
            next = s.top();
            // מחליף כיוון: גדול משני שכניו או קטן משני שכניו
            if ((cur > prev && cur > next) || (cur < prev && cur < next))
                temp.push(cur);      // מכניסים איבר זהה אחריו
        }
        prev = cur;
    }
    while (!temp.isEmpty())          // החזרה למחסנית המקורית – הסדר נשמר
        s.push(temp.pop());
}

ב. סיבוכיות: כל איבר מוצא פעם אחת למחסנית העזר ומוחזר פעם אחת (לכל היותר פעמיים בגלל ההכפלה), וכל פעולת מחסנית היא O(1). לכן הסיבוכיות היא O(n), כאשר n מספר האיברים במחסנית.

לפניכם פעולה המקבלת כפרמטר תור q של מספרים שלמים הממוינים בסדר עולה. כל המספרים שונים זה מזה. הניחו שבתור יש לפחות שני מספרים.

public static int what(Queue<Integer> q)
{
    int x = q.remove();
    int y = q.head();
    q.insert(x);
    if (x > y)
        return 0;
    return what(q) + (y - x);
}

(1) עקבו אחר הפעולה what עבור התור q1 וכתבו את הערך שיוחזר. הראו את הערכים של x ושל y ואת התור לאחר כל זימון רקורסיבי.

(2) (i) מה מחזירה הפעולה עבור תור כלשהו של מספרים ממוינים בסדר עולה ושונים זה מזה? (ii) כיצד נראה התור לאחר סיום הפעולה?

(3) אם נחליף את התנאי if (x > y) בתנאי if (q.isEmpty()) תיווצר שגיאת זמן ריצה. מהי השגיאה? הסבירו.

(1) מעקב:

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

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

(ii) התור חוזר למצבו המקורי – כל איבר הוצא מהראש והוכנס לסוף פעם אחת (סיבוב שלם).

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

לפניכם ממשק המחלקה "תור-ביטול" (UndoQueue). המחלקה מגדירה אוסף עם פרוטוקול FIFO להכנסה והוצאה של ערכים שלמים וגדולים מ-0.

א. הראו את מצב התור-ביטול לאחר כל הוראה בקטע הקוד:

UndoQueue q = new UndoQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.remove();
q.insert(4);
q.undo();
q.undo();

ב. כתבו ב-Java את כותרת המחלקה UndoQueue ואת התכונות שלה, עם תיעוד לכל תכונה.

ג. ממשו את הפעולות insert, remove ו-undo. אפשר להשתמש בפעולות הממשק האחרות בלי לממש אותן.

א. (התור מוצג מהראש לסוף)

ב. תכונות: תור לערכים, ומחסנית של הפעולות שבוצעו – כי undo מבטל תמיד את הפעולה האחרונה (LIFO). מאחר שכל הערכים גדולים מ-0, נקודד: 0 = בוצע insert; x > 0 = בוצע remove שהוציא את x.

public class UndoQueue
{
    private Queue<Integer> q;      // ערכי התור-ביטול, לפי סדר FIFO
    private Stack<Integer> ops;    // היסטוריית פעולות: 0 = insert, x>0 = remove שהוציא את x

    public UndoQueue()
    {
        q = new Queue<Integer>();
        ops = new Stack<Integer>();
    }

    // ג.
    public void insert(int x)
    {
        q.insert(x);
        ops.push(0);               // רישום: בוצעה הכנסה
    }

    public int remove()
    {
        int x = q.remove();
        ops.push(x);               // רישום: הוצא x
        return x;
    }

    public void undo()
    {
        int x;
        if (ops.isEmpty())
            return;                // אין מה לבטל
        int op = ops.pop();
        Queue<Integer> temp = new Queue<Integer>();
        if (op == 0)
        {
            // ביטול insert: מוחקים את האיבר האחרון בתור
            while (!q.isEmpty())
            {
                x = q.remove();
                if (!q.isEmpty())  // x אינו האחרון – נשמר
                    temp.insert(x);
            }
        }
        else
        {
            // ביטול remove: מחזירים את op לראש התור
            temp.insert(op);
            while (!q.isEmpty())
                temp.insert(q.remove());
        }
        q = temp;
    }
    // isEmpty, head – לפי הממשק
}

סיבוכיות: insert ו-remove – O(1); undo – O(n).

"שרשרת מספרים שלמים חיוביים" היא שרשרת חוליות שכל חוליה בה מכילה מספר שלם הגדול מ-0.

"שרשרת ספרות" היא שרשרת חוליות שכל חוליה בה מכילה ספרה בין 0 ל-9 או את המספר (‎-9). כל רצף ספרות בשרשרת מייצג מספר: הספרה הראשונה מייצגת את האחדות, השנייה את העשרות וכן הלאה. לאחר כל רצף ספרות מופיע (‎-9), המסמן סוף של מספר.

דוגמה ל"שרשרת ספרות" המייצגת את המספרים 92, 4, 543:

כתבו פעולה חיצונית buildDigit המקבלת הפניה lst שאינה null ל"שרשרת מספרים שלמים חיוביים". הפעולה תחזיר "שרשרת ספרות" המייצגת את המספרים שב-lst לפי הסדר.

רעיון: בונים שרשרת חדשה עם הפניה לחוליה האחרונה ("זנב") כדי להוסיף בסוף ב-O(1). חוליית דמה בתחילה חוסכת טיפול מיוחד בחוליה הראשונה.

public static Node<Integer> buildDigit(Node<Integer> lst)
{
    int num;
    Node<Integer> dummy = new Node<Integer>(0);   // חוליית דמה
    Node<Integer> last = dummy;
    while (lst != null)
    {
        num = lst.getValue();
        while (num > 0)                            // ספרות מהאחדות והלאה
        {
            last.setNext(new Node<Integer>(num % 10));
            last = last.getNext();
            num = num / 10;
        }
        last.setNext(new Node<Integer>(-9));       // סימון סוף מספר
        last = last.getNext();
        lst = lst.getNext();
    }
    return dummy.getNext();
}

סיבוכיות: O(n·d), n – מספר החוליות, d – מספר הספרות המרבי (בפועל לינארי במספר הספרות הכולל).

א. ממשו את הפעולה public static void leaves(BinNode<Integer> t, Stack<Integer> s). הפעולה מקבלת עץ בינרי לא ריק t של מספרים שלמים, ומחסנית ריקה s. הפעולה מכניסה למחסנית את ערכי כל העלים של העץ t, על פי סדר סריקה מימין לשמאל.

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

// א.
public static void leaves(BinNode<Integer> t, Stack<Integer> s)
{
    if (t == null)
        return;
    if (!t.hasLeft() && !t.hasRight())     // עלה
        s.push(t.getValue());
    else
    {
        leaves(t.getRight(), s);           // קודם הצד הימני
        leaves(t.getLeft(), s);
    }
}

// ב.
public static boolean sameLeaves(BinNode<Integer> t1, BinNode<Integer> t2)
{
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    leaves(t1, s1);
    leaves(t2, s2);
    while (!s1.isEmpty() && !s2.isEmpty())
        if (!s1.pop().equals(s2.pop()))    // השוואת ערכי Integer
            return false;
    return s1.isEmpty() && s2.isEmpty();   // אותו מספר עלים
}

סיבוכיות: O(n1 + n2) – כל צומת נסרק פעם אחת. (שתי המחסניות באותו סדר, ולכן אפשר להשוות אותן בהוצאה.)

לפניכם פעולה המקבלת מערך חד-ממדי ar מטיפוס שלם, ושני מספרים שלמים x ו-y הגדולים או שווים ל-0, קטנים מגודל המערך, ו-x ≤ y.

public static int go(int[] ar, int x, int y)
{
    if (x == y) return (ar[x] % 10);
    if ((ar[x] % 10) < (ar[y] % 10))
        return go(ar, x + 1, y);
    return go(ar, x, y - 1);
}

(1) מה יחזיר הזימון go(ar1, 2, 5)? הראו מעקב רקורסיבי עם הערכים x, y, ar1[x], ar1[y].

(2) מה יחזיר הזימון go(ar1, 0, ar1.length - 1)?

(3) כתבו מה מבצעת הפעולה go עבור מערך כלשהו ו-x, y כמתואר.

(1)

הזימון מחזיר 7.

(2) ספרות האחדות: 1, 9, 6, 1, 7, 0, 4 – יוחזר 9.

(3) הפעולה מחזירה את ספרת האחדות הגדולה ביותר מבין האיברים ar[x]..ar[y]. בכל צעד "נזרק" הקצה שספרת האחדות שלו קטנה יותר. סיבוכיות O(y − x).

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

נתון קטע תוכנית, הכתוב בשפת Java:

int sum = arr[0];
for (int i=1; i< arr.length; i++)
{
    arr[i] = arr[i] - sum;
    sum += arr[i];
}

א. עקבו בעזרת טבלת מעקב אחר ביצוע קטע התוכנית, ורשמו את תוכן המערך arr לאחר ביצוע קטע התוכנית. בטבלת המעקב יש לכלול עמודה עבור כל אחד מן המשתנים האלה: i, arr[i], sum.

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

א. בהתחלה sum = arr[0] = 3. בכל סיבוב מחסירים מהתא את sum ואז מוסיפים לו את הערך החדש של התא.

תוכן המערך בסיום:

הסבר: אחרי כל סיבוב sum שווה לערך המקורי של arr[i] (כי sum + (arr[i] − sum) = arr[i]). לכן כל תא (חוץ מהראשון) הופך להפרש בין הערך המקורי שלו לערך המקורי של התא שלפניו.

ב. צריך תא ראשון חיובי ומערך עולה ממש, למשל:

לאחר הביצוע: 1, 1, 1, 1, 1 – כל התאים חיוביים (כל הפרש בין שני תאים סמוכים הוא 1).

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

אדם מצליח במשחק אם מתקיים לפחות אחד מן המקרים האלה:
- בממוצע הניקוד הוא מעל ל־5.0 נקודות.
- ברוב היריות הוא זכה ב־6 נקודות ומעלה.
- בירייה אחת או יותר הוא זכה ב־10 נקודות.

דוגמה: אדם ירה חמישה חיצים וזכה בניקוד: 5, 7, 9, 3, 3. בממוצע הוא זכה ב־5.4 נקודות, ולכן הוא הצליח במשחק.

דוגמה נוספת: אדם ירה שישה חיצים וזכה בניקוד: 7, 6, 1, 7, 8, 0. בארבע יריות מתוך השש (כלומר, ברוב היריות שלו) הוא זכה ב־6 נקודות ומעלה, ולכן הוא הצליח במשחק.

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

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

רעיון: קולטים את כל num הניקודים ובמהלך הקליטה צוברים שלושה נתונים: סכום, מספר יריות של 6 ומעלה, ומספר יריות של 10. רק אחרי שכל הקלט נקלט בודקים את שלושת התנאים (מספיק שאחד מתקיים – ||).

public static boolean success(int num)
{
    int sum = 0;        // סכום הנקודות
    int high = 0;       // יריות של 6 ומעלה
    int ten = 0;        // יריות של 10
    int score;
    int i;
    for (i = 0; i < num; i++)
    {
        score = scan.nextInt();
        sum += score;
        if (score >= 6)
            high++;
        if (score == 10)
            ten++;
    }
    return (double) sum / num > 5.0 || high * 2 > num || ten > 0;
}

הערות: הממוצע מחושב כממשי ((double) sum / num) כדי לא לאבד את החלק העשרוני (5.4). "ברוב היריות" = יותר מחצי: high * 2 > num.

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

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

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

הסבר: התו הראשון במסר המוצפן (r) מופיע במסר המקורי באינדקס 2, התו השני במסר המוצפן (d) מופיע במסר המקורי באינדקס 4, התו השלישי במסר המוצפן (o) מופיע במסר המקורי באינדקס 1, וכן הלאה.

א. רשמו את המערך המפענח עבור המסר Study, שהוצפן למסר dyutS.

ב. כתבו פעולה חיצונית ששמה originalText המקבלת מחרוזת מוצפנת – str ומערך מפענח – arr. הפעולה תחזיר את המחרוזת המקורית.

א. במסר המקורי: S=0, t=1, u=2, d=3, y=4. התווים המוצפנים לפי הסדר הם d, y, u, t, S, ולכן:

ב. רעיון: בונים את המחרוזת המקורית לפי הסדר – מקום 0, מקום 1, ... . עבור כל מקום k מחפשים במערך המפענח את התא j שבו arr[j] == k, ומוסיפים את התו str.charAt(j).

public static String originalText(String str, int[] arr)
{
    String res = "";
    int k;
    int j;
    for (k = 0; k < arr.length; k++)        // מקום k במסר המקורי
    {
        for (j = 0; j < arr.length; j++)    // מחפשים את התו שמקומו המקורי k
        {
            if (arr[j] == k)
                res = res + str.charAt(j);
        }
    }
    return res;
}

לדוגמה: originalText("rdoWl", {2,4,1,0,3}) מחזירה "World". סיבוכיות: O(n²).

נתונה המחלקה Results, המייצגת זמני שחיית 50 מטרים של שחיין בתקופה מסוימת. למחלקה שתי תכונות:
- arr – מערך מטיפוס שלם, המכיל את מספר השניות שארכה שחיית 50 המטרים של השחיין בכל יום בתקופה מסוימת
- name – שם השחיין, מטיפוס מחרוזת

הניחו שקיימות פעולות get/set עבור תכונות המחלקה.

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

א. כתבו פעולה פנימית ששמה deltas המקבלת פרמטר – isLonger מטיפוס בוליאני, ומחזירה מספר שלם בהתאם לאפיון שלפניכם:
- אם הפרמטר isLonger שהתקבל הוא true, הפעולה תחזיר את סך ההפרשים בימים שנחשבים "הרעה".
- אם הפרמטר isLonger שהתקבל הוא false, הפעולה תחזיר את סך ההפרשים בימים שנחשבים "שיפור".

לדוגמה, עבור המערך arr שלפניכם, אם isLonger הוא true הפעולה תחזיר 14, ואם isLonger הוא false הפעולה תחזיר 17.

הסבר: התאים באינדקסים 1, 3, 6 מייצגים ימים שנחשבים "הרעה", וסך ההפרשים בהם (7 + 3 + 4) הוא 14 שניות. התאים באינדקסים 2, 4 מייצגים ימים שנחשבים "שיפור", וסך ההפרשים בהם (2 + 15) הוא 17 שניות.

ב. כתבו פעולה פנימית ששמה improving המחזירה true אם סך ההפרשים בימים שנחשבים "שיפור" גדול מסך ההפרשים בימים שנחשבים "הרעה". אחרת הפעולה תחזיר false. למשל, בדוגמה שלעיל הפעולה תחזיר true (17 > 14). חובה להיעזר בפעולה שכתבתם בסעיף א.

א. עוברים על הימים מהיום השני ומחשבים diff = arr[i] - arr[i-1]. הפרש חיובי = הרעה, הפרש שלילי = שיפור (ואז מחברים את הערך המוחלט, -diff). הפרש 0 אינו נספר באף אחד.

ב. משתמשים ב־deltas פעמיים ומשווים.

public class Results
{
    private int[] arr;
    private String name;
    // פעולות get/set קיימות

    // א
    public int deltas(boolean isLonger)
    {
        int sum = 0;
        int diff;
        int i;
        for (i = 1; i < arr.length; i++)
        {
            diff = arr[i] - arr[i - 1];      // חיובי = הרעה, שלילי = שיפור
            if (isLonger && diff > 0)
                sum = sum + diff;
            else if (!isLonger && diff < 0)
                sum = sum - diff;            // ערך מוחלט
        }
        return sum;
    }

    // ב
    public boolean improving()
    {
        return deltas(false) > deltas(true);
    }
}