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

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

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

סעיף א

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

סעיף ב

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

סעיף ג

void f3(int n) {
    for (int i = 1; i <= n; i *= 2) {
        int* p = malloc(i*sizeof(int));
        for (int j = 0; j < i; j++)
            p[j] = j;
        free(p);
    }
}

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

נתונים a,b באורך n≥1, ממוינים בסדר לא יורד, עם ערכים שלמים חיוביים. לכל ערך, הסירו מ-a מספר הופעות השווה למינימום בין מספר הופעותיו ב-a וב-b. כתבו את ההופעות שנותרו בתחילת a בסדר עולה, מלאו את כל יתר התאים באפס והחזירו את מספר ההופעות שנותרו. אין לשנות את b.

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

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

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

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

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

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

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

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

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

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

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

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