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

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

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

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

א.

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

ב.

int f2(int n) {
    if (n <= 1) return 1;
    int* a = (int*) malloc(n * sizeof(int));
    if (a == NULL) return 0;
    int r = f2(n - 1);
    free(a);
    return r;
}

ג.

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

שאלה 2 25 נק'

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

על הפונקציה להחזיר את המרחק המינימלי בין x לבין איבר כלשהו במערך — כלומר את הערך המינימלי של |arr[i] - x| על פני כל i.

• ניתן להניח כי הקלט תקין וכי n ≥ 1.
• אין לשנות את תוכן המערך ואין להקצות זיכרון דינמי.
• שימו לב: לאחר שמצאתם את הגבול, יש שני מועמדים שיש להשוות ביניהם.

שאלה 3 25 נק'

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

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

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

• אין לשנות את תוכן המחרוזת s, אפילו לא באופן זמני.
• אין להקצות זיכרון דינמי ואין להשתמש במערך עזר שגודלו תלוי ב-n.
• ניתן להניח כי הקלט תקין וכי s אינה ריקה.
• שימו לב: יש להתחשב גם בפלינדרומים באורך זוגי וגם באורך אי-זוגי.

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

נתונים שני מספרים שלמים וחיוביים n ו-k.

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

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

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

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

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