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

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

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

סעיף א

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

סעיף ב

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

סעיף ג

int g3(int n) {
    int v = 0;
    for (int i = 0; i < n; i++)
        v++;
    return v;
}
void f3(int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < g3(n); j++)
            printf("*");
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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