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

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

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

א.

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

ב.

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

ג.

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

שאלה 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 אינו נתון.

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

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

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד, ומספר שלם וחיובי k.

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

נאמר שתת-מחרוזת היא מאוזנת אם כל תו שמופיע בה מופיע בה בדיוק k פעמים. (תו שאינו מופיע בתת-המחרוזת אינו מטיל שום דרישה.)

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

• אין לשנות את תוכן המחרוזת s, אפילו לא באופן זמני.
• ניתן להניח כי הקלט תקין, כי k ≥ 1 וכי s אינה ריקה.

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

נתון מערך arr של מספרים שלמים (ייתכנו גם שליליים ואפסים) באורך n, ומספר שלם k.

תת-מערך רציף של arr הוא רצף רציף ולא ריק של איברים במערך.

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

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

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

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