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

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

ב.

int f2(int n) {
    if (n <= 1)
        return 1;
    int* a = malloc(n * sizeof(int));
    if (!a)
        return 0;
    int r = f2(n / 2) + f2(n / 2);
    free(a);
    return r;
}

ג.

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

---

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

נתונים שני מערכים באורך n. המערך b הוא תמורה של 0..n-1 (כל ערך מופיע בדיוק פעם אחת).

על הפונקציה לסדר מחדש את a כך שבסיום יתקיים a_new[i] = a_old[b[i]] לכל i, במקום, ולהחזיר את מספר המחזורים בתמורה b.

מותר לשנות את b.

דוגמה: a = {10,20,30,40}, b = {1,0,3,2} -> מחזיר 2, a = {20,10,40,30}

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

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

שאלה 3 (25 נק') - תת-הסדרה הקטנה לקסיקוגרפית עם כל האותיות

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

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

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

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

שאלה 4 (25 נק') - סכום מרבי בתת-מערך רציף

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

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

דוגמה: arr = {-2,1,-3,4,-1,2,1,-5,4} -> 6 (התת-מערך {4,-1,2,1})

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

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

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

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