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

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

לכל קטע יש לקבוע סיבוכיות זמן ומקום נוסף הדוקה Θ. כל סעיף שווה שליש מניקוד השאלה. יש להניח n חיובי, פעולות ו-printf/free/malloc בזמן קבוע, הקצאה של k איברים תופסת Θ(k) מקום, והקצאות מצליחות. יש לכלול את מחסנית הרקורסיה; אין להניח אופטימיזציית זנב. מנתחים את הקוד במודל הרגיל ללא גלישת מספרים וללא אופטימיזציות מהדר.

סעיף א

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

סעיף ב

int f2(int n) {
    if (n < 2)
        return 1;
    int* p = malloc(n*n*sizeof(int));
    int x = f2(n/2);
    int y = f2(n/2);
    free(p);
    return x+y;
}

סעיף ג

int g3(int n) {
    if (n < 2)
        return 1;
    return 2*g3(n/2);
}
void f3(int n) {
    for (int i = 0; i < g3(n); i++)
        printf("*");
}

שאלה 2 — 25 נקודות

נתונים שני מערכים a,b באורך n≥1. כל איברי b שונים והוא התקבל מסיבוב מעגלי של מערך ממוין בסדר עולה ממש. לכל איבר מקורי a[i], יש לכתוב במקומו את הערך ב-b שמרחקו ממנו מינימלי; בשוויון בחרו בערך הקטן יותר. החזירו את מספר האיברים המקוריים של a שהופיעו ב-b. אין לשנות את b. כל ערכי הקלט בין ‎−1000 ל-1000. כל n התאים של a הם חלק מהתוצאה.

דוגמאות — הפלט כולל את כל מה שה-main מדפיס

כתבו רק את הפונקציה המבוקשת ועזר מותר בקובץ השלד. אל תשנו את main, את החתימה או את פורמט הקלט והפלט.

שאלה 3 — 25 נקודות

נתונה מחרוזת s לא ריקה של אותיות a–z. כתבו ל-p את תת-הסדרה המינימלית בסדר מילוני שמכילה כל אות שונה של s פעם אחת בדיוק. תת-סדרה שומרת על סדר ההופעה, אך רשאית לדלג על תווים. החזירו את אורך p. אין לשנות את s. יש לסיים את p ב-'\0'.

דוגמאות — הפלט כולל את כל מה שה-main מדפיס

כתבו רק את הפונקציה המבוקשת ועזר מותר בקובץ השלד. אל תשנו את main, את החתימה או את פורמט הקלט והפלט.

שאלה 4 — 25 נקודות

נתון arr באורך 1≤n≤2000. החזירו את מספר הזוגות i<j שעבורם arr[i]>arr[j]. מותר לשנות את arr. כל איבר בין ‎−1000 ל-1000. הפונקציה עצמה וכל פונקציות העזר חייבות להיות רקורסיביות; אין לולאות, פונקציית מעטפת או הקצאה דינמית. אין דרישת סיבוכיות בשאלה זו. שוויון אינו נחשב היפוך.

דוגמאות — הפלט כולל את כל מה שה-main מדפיס

כתבו רק את הפונקציה המבוקשת ועזר מותר בקובץ השלד. אל תשנו את main, את החתימה או את פורמט הקלט והפלט.

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

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