מבוא למדעי המחשב מ'/ח'

שאלה 1 25 נק' — סיבוכיות

לכל סעיף ציינו סיבוכיות זמן וסיבוכיות מקום נוסף, בסימון Θ, כפונקציה של n. חובה לפשט את הביטוי ככל שניתן. הניחו כי סיבוכיות הזמן והמקום של printf ו-free היא Θ(1), וכי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות המקום שלה היא Θ(n). הניחו כי sqrt פועלת בזמן Θ(1).

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

א.

void f1(int n) {
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 1)
            j /= 2;
        printf("*");
    }
}

ב.

void f2(int n) {
    int i = 0;
    while (i * i < n) {
        for (int j = 0; j < i; j++)
            printf("*");
        i++;
    }
}

ג.

int g(int n) {
    int s = 0;
    for (int i = 0; i < n; i++)
        s += i;
    return s;
}

void f3(int n) {
    for (int i = 0; i < g(n); i++)
        printf("*");
}

שאלה 2 25 נק'

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

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

• ניתן להניח כי הקלט תקין, כי n mod 3 == 1 וכי המבנה אכן כמתואר.
• אין לשנות את תוכן המערך ואין להקצות זיכרון דינמי.
• רמז: לפני הערך היחיד כל שלישייה מתחילה באינדקס המתחלק ב-3; אחריו ההיסט משתנה. יש ליישר את נקודת האמצע לתחילת שלישייה לפני ההשוואה.

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד, ומספר שלם וחיובי k.

תת-מחרוזת של s היא רצף רציף ולא ריק של תווים ב-s.

על הפונקציה להחזיר את מספר תתי-המחרוזות של s שמספר התווים השונים המופיעים בהן הוא בדיוק k. תתי-מחרוזות במקומות שונים נספרות בנפרד, גם אם תוכנן זהה.

• אין לשנות את תוכן המחרוזת s, אפילו לא באופן זמני.
• ניתן להניח כי הקלט תקין, כי k ≥ 1 וכי s אינה ריקה.
• מערך בגודל קבוע (26 תאים) נחשב מקום Θ(1).
• רמז: "בדיוק k" קל יותר לחשב כהפרש של שתי כמויות מסוג "לכל היותר".

שאלה 4 25 נק' — רקורסיה

נתון מערך arr של מספרים שלמים באורך n.

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

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

• על הפונקציה להיות רקורסיבית בלבד, ללא שימוש בלולאות — בכל הפונקציות שתכתבו, כולל מציאת המינימום.
• אסור להשתמש בפונקציית מעטפת — examT_q4 עצמה חייבת לקרוא לעצמה.
• אין להקצות זיכרון דינמי; המיון חייב להתבצע במקום.
• אין דרישות סיבוכיות בשאלה זו.

איך עובדים כאן

• כתבו בעורך שמשמאל. שלושה קבצים, לשונית לכל שאלה. אל תשנו את main.
• הרץ בדיקות מריץ את הפונקציה שלכם מול מקרי הבדיקה של השאלה — כולל בדיקות של האילוצים (לולאות ברקורסיה, שינוי הקלט, פונקציית מעטפת).
• סיבוכיות אינה נבדקת אוטומטית. פתרון שעובר את כל הבדיקות בסיבוכיות שגויה — נכשל בשאלה.
• בסיום לחצו סיום והגשה, שמרו את קובץ ההגשה, ובקשו מ-Claude ציון עם /grade.