תרגול מבחן 003

שאלה 1 — ניתוח סיבוכיות

לכל קטע קוד בחרו את סיבוכיות הזמן והמקום ההדוקות ביותר.

א

void grow(int n) {
    for (int i = 2; i < n; i *= i)
        putchar('.');
}

ב

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

void down(int n) {
    if (n <= 1) return;
    down(n - 1);
}

void both(int n) {
    half(n);
    down(n);
}

ג

void layers(int n) {
    for (int i = 1; i < n; i *= 2)
        for (int j = 0; j < n / i; j++)
            for (int k = 0; k < i; k++)
                putchar('.');
}

שאלה 2 — קיבולת משלוח מינימלית

חלקו את המערך, לפי הסדר, ל־D קבוצות רציפות בדיוק. החזירו את הערך המינימלי האפשרי של סכום הקבוצה הגדולה ביותר.

דוגמה: עבור המשקלים {1,2,3,4,5,6,7,8,9,10} ו־D=5 מוחזר 15.

דרישות: זמן O(n·log(sum(weights))), מקום נוסף O(1).

שאלה 3 — החלפת התבנית ab

סרקו משמאל לימין. החליפו כל הופעה לא חופפת של "ab" בתו '#', הזיזו את המשך המחרוזת שמאלה והחזירו את מספר ההחלפות.

דוגמה: "cababd" הופכת ל־"c##d", ומוחזר 2.

דרישות: שינוי במקום, זמן Θ(n), מקום נוסף Θ(1).

שאלה 4 — ספירת ביטים דלוקים

החזירו את מספר הביטים שערכם 1 בייצוג הבינארי של מספר שלם אי־שלילי.

דוגמה: עבור 13 (בבינארית 1101) מוחזר 3.

הפונקציה עצמה חייבת להיות רקורסיבית; אין פונקציית מעטפת ואין לולאות.