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

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

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

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

א.

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

ב.

void f2(int n) {
    for (int i = n; i > 0; i /= 2) {
        int* p = malloc(i * sizeof(int));
        if (!p)
            return;
        for (int j = 0; j < i; j++)
            printf("*");
        free(p);
    }
}

ג.

void f3(int n) {
    for (int i = n; i > 2; i = (int) sqrt(i))
        printf("*");
}

---

שאלה 2 (25 נק') - דירוג כל איבר מול מערך ממוין

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

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

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

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

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

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

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

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

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

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

על הפונקציה להחזיר 1 אם arr הוא פלינדרום (זהה לעצמו הפוך), ו-0 אחרת.

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

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

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

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

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

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