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

שאלה 1 (25 נק') - סיבוכיות

לכל סעיף ציינו סיבוכיות זמן וסיבוכיות מקום נוסף בסימון Theta, כפונקציה של n.

הניחו כי malloc פועלת בזמן Theta(1) ותופסת מקום כגודל ההקצאה, וכי printf, free ו-sqrt הן Theta(1).

א.

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

ב.

int f2(int n) {
    if (n <= 1)
        return 1;
    int* a = malloc(n * sizeof(int));
    if (!a)
        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++)
        for (int j = i; j < n; j += i)
            printf("*");
}

---

שאלה 2 (25 נק') - הסרת ערכים המופיעים ב-b

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

דוגמה: a = {1,2,3,4,5}, b = {2,4,6,8,9} -> מחזיר 3, a = {1,3,5,-1,-1}

דרישות סיבוכיות: זמן Theta(n) - מקום נוסף Theta(1)

אין להקצות זיכרון דינמי ואין להשתמש בפונקציות ספרייה.

שאלה 3 (25 נק') - כיווץ רצפים

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

דוגמה: s = "aaabbbcca" -> מחזיר 4, p = "abca"

דרישות סיבוכיות: זמן Theta(n) - מקום נוסף Theta(1)

אין להקצות זיכרון דינמי ואין להשתמש בפונקציות ספרייה.

שאלה 4 (25 נק') - ספירת שיאים

איבר נקרא שיא אם הוא גדול ממש מכל האיברים שלפניו. האיבר הראשון תמיד שיא.

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

רקורסיה בלבד, ללא לולאות, ללא פונקציית מעטפת.

דוגמה: arr = {3,1,4,1,5} -> 3 (3, 4, 5)

דרישות סיבוכיות: אין דרישת סיבוכיות

אין להקצות זיכרון דינמי ואין להשתמש במשתנים גלובליים או סטטיים.

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

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