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

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

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

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

א.

void f1(int n) {
    for (int i = 0; i < n; i++)
        printf("*");
}

ב.

void f2(int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("*");
}

ג.

int f3(int n) {
    if (n <= 1)
        return 1;
    return f3(n / 2);
}

---

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

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

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

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

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

שאלה 3 (25 נק') - היפוך מחרוזת

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

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

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

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

שאלה 4 (25 נק') - סכום האיברים הזוגיים

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

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

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

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

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

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

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