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

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

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

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

א.

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 = malloc(n * sizeof(int));
    if (!a)
        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; j++)
            printf("*");
        m *= 2;
    }
}

---

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

המערכים a ו-b מייצגים שני מספרים בני n ספרות בבסיס 10, ספרה לתא, הספרה המשמעותית ביותר ראשונה (כל ערך בין 0 ל-9).

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

דוגמה: a = {9,9,9}, b = {0,0,1} -> מחזיר 1, a = {0,0,0}

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

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

שאלה 3 (25 נק') - הסרת אותיות כפולות

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

דוגמה: s = "banana" -> מחזיר 3, p = "ban"

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

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

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

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

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

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

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

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

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

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