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

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

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

סעיף א

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

סעיף ב

int g2(int n) {
    int k = 0;
    while (k < n) {
        k += 3;
        n--;
    }
    return n;
}
int f2(int n) {
    if (n < 4)
        return 0;
    return 1+f2(g2(n));
}

סעיף ג

void f3(int n) {
    if (n < 1)
        return;
    int* p = malloc(n*sizeof(int));
    f3(n-1);
    free(p);
}

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

כל אחד מהמערכים a,b באורך n≥1 מייצג מספר שלם לא שלילי בבסיס עשר, הספרה המשמעותית ביותר ראשונה. כל איבר הוא ספרה 0–9, ואפסים מובילים מותרים. כתבו ל-a את n הספרות האחרונות של הסכום, והחזירו את ספרת הנשא הנוספת (0 או 1). אין לשנות את b. אין להמיר את המערך למספר מטיפוס שלם יחיד.

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

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

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

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

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

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

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

נתון arr באורך 1≤n≤2000. החזירו את מספר תתי-המערכים הרציפים באורך לפחות 2 שעולים ממש. תת-מערך באורך 1 אינו נספר. אין לשנות את arr. הפונקציה עצמה וכל עזר חייבים להיות רקורסיביים; אין לולאות, פונקציית מעטפת או הקצאה דינמית. אין דרישת סיבוכיות.

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

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

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

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