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

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

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

סעיף א

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

סעיף ב

int f2(int n) {
    if (n < 2)
        return 1;
    return f2(n/2)+f2(n/2);
}

סעיף ג

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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