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

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

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

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

א.

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

ב.

int f2(int n) {
    if (n <= 1) return 1;
    int* a = (int*) malloc(n * sizeof(int));
    if (a == NULL) return 0;
    for (int i = 0; i < n; i++)
        a[i] = i;
    free(a);
    return f2(n - 1);
}

ג.

void f3(int n) {
    for (int i = 1; i < n; i *= 2)
        for (int j = 1; j < i; j *= 2)
            printf("*");
}

שאלה 2 25 נק'

הגדרה: מערך arr באורך n ייקרא מערך חזית אם קיים k, 0 ≤ k ≤ n, כך ש-arr[0] > arr[1] > ... > arr[k-1] > 0 וכל יתר התאים, מ-k והלאה, מכילים 0. הערך k אינו נתון ועשוי להיות קטן בהרבה מ-n.

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

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

שאלה 3 25 נק'

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

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

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

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

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

על הפונקציה להחזיר 1 אם ניתן לקבל את a מתוך b על ידי מחיקת תו אחד בדיוק (לא פחות ולא יותר), ו-0 אחרת.

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

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

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

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