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

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

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

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

א.

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

ב.

void f2(int n) {
    for (int i = n; i > 0; i /= 2) {
        int* p = (int*) malloc(i * sizeof(int));
        if (p == NULL) return;
        for (int j = 0; j < i; j++)
            printf("*");
        free(p);
    }
}

ג.

int f3(int n) {
    if (n <= 1) return 1;
    for (int i = 0; i < n; i++)
        printf("*");
    return f3(n / 2);
}

שאלה 2 25 נק'

נתון מערך arr של מספרים שלמים, ממוין בסדר לא-יורד, שאורכו אינו נתון לכם. סוף הנתונים מסומן על ידי הערך המיוחד EMPTY (המוגדר בשלד כ-INT_MIN): כל תא מהאינדקס n והלאה מכיל EMPTY, ואף איבר אמיתי אינו שווה ל-EMPTY.

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

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

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

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד.

לכל i, נגדיר את האות השלטת בקידומת s[0..i] כאות המופיעה בה הכי הרבה פעמים. במקרה של שוויון בין כמה אותיות, השלטת היא הקטנה ביותר לקסיקוגרפית מביניהן.

על הפונקציה להחזיר את מספר האינדקסים i (כאשר 1 ≤ i < n) שבהם האות השלטת ב-s[0..i] שונה מזו שב-s[0..i-1] — כלומר, כמה פעמים מתחלפת האות השלטת לאורך המחרוזת.

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

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

נתונות שתי מחרוזות a ו-b המכילות אותיות אנגליות קטנות בלבד.

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

על הפונקציה להחזיר את מספר ההופעות של a כתת-סדרה של b.

רמז: הסתכלו על התו הראשון של b. אם הוא מתאים לתו הראשון של a, יש שתי אפשרויות נפרדות — לצרוך אותו, או לדלג עליו — ויש לסכום את שתיהן. אם אינו מתאים, נותרה אפשרות אחת בלבד.

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

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

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