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

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

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

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

א.

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

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

ב.

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;
    return f3(n - 1) + f3(n - 2);
}

שאלה 2 25 נק'

הגדרה: מערך arr באורך n ייקרא מערך עמק אם קיים אינדקס p, כאשר 0 < p < n-1, כך ש-

• arr[0] > arr[1] > ... > arr[p]  (יורד ממש עד p), וגם
• arr[p] < arr[p+1] < ... < arr[n-1]  (עולה ממש מ-p והלאה)

כלומר המערך יורד ממש עד לאיבר מינימלי יחיד ואז עולה ממש. האינדקס p אינו נתון.

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

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

שאלה 3 25 נק'

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

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

על הפונקציה לבצע את התהליך במקום, בתוך s עצמה, ולהחזיר את מספר המחיקות הכולל. יש להקפיד שהמחרוזת הסופית תסתיים ב-'\0'.

• ניתן להניח כי הקלט תקין וכי s אינה ריקה.
• אין להקצות זיכרון דינמי ואין להשתמש במערך עזר.
• יש לבצע מעבר יחיד על המחרוזת. פתרון שסורק מחדש אחרי כל מחיקה אינו עומד בדרישת הסיבוכיות.

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

נתון מספר שלם ואי-שלילי n.

נסתכל על הייצוג הבינארי של n. רצף אחדות הוא קטע רציף ומקסימלי של ביטים שערכם 1.

על הפונקציה להחזיר את אורכו של רצף האחדות הארוך ביותר בייצוג הבינארי של n (0 אם n הוא 0).

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

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

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

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