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

שאלה 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 = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 1; k < n; k *= 2)
                printf("*");
}

ג.

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

שאלה 2 25 נק'

נתונה מטריצה mat בעלת m שורות ו-N עמודות (N מוגדר ב-#define בשלד, אך אינו נחשב קבוע לצורך הסיבוכיות). כל שורה בנפרד ממוינת בסדר לא-יורד; אין שום קשר בין שורה לשורה.

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

• ניתן להניח כי הקלט תקין וכי m ≥ 1. ייתכנו ערכים שליליים וערכים חוזרים.
• אין לשנות את תוכן המטריצה ואין להקצות זיכרון דינמי.
• פתרון בזמן Θ(m·N) אינו עומד בדרישה.

שאלה 3 25 נק'

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

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

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

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

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

נתון מספר שלם ואי-שלילי n. יש לרצף לוח בגודל 2 × n באמצעות שני סוגי אריחים:

• דומינו בגודל 1 × 2, שניתן להניח אנכית או אופקית;
• ריבוע בגודל 2 × 2.

האריחים אינם חופפים ואינם חורגים מהלוח, ויש לכסות אותו במלואו.

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

רמז: חשבו על העמודה השמאלית ביותר. כמה דרכים יש לכסות אותה, וכמה עמודות כל אחת מהן "צורכת"? מכאן נובעת נוסחת נסיגה עם שני איברים קודמים ומקדם שאינו 1.

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

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

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