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

שאלה 1 25 נק' — סיבוכיות

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

שימו לב: אין הבטחה ששלושת הסעיפים מקבלים תשובות שונות. חשבו כל סעיף מחדש — ובפרט שימו לב לערכי חזרה של פונקציות עזר, למשתנים שמשתנים בין איטרציות, ולמיקום של free ביחס לקריאה הרקורסיבית.

א.

void f1(int n) {
    for (int i = n; i > 0; i /= 2) {
        int* p = (int*) malloc(i * sizeof(int));
        if (p == NULL) return;
        for (int j = 0; j < i; j++)
            printf("*");
        free(p);
    }
}

ב.

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

ג.

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

שאלה 2 25 נק'

הגדרה: מערך arr באורך n ייקרא מערך הררי אם קיים אינדקס p, כאשר 0 < p < n-1, כך ש-

• arr[0] < arr[1] < ... < arr[p]  (עולה ממש עד p), וגם
• arr[p] > arr[p+1] > ... > arr[n-1]  (יורד ממש מ-p והלאה)

האינדקס p אינו נתון.

על הפונקציה להחזיר את האינדקס שבו מופיע x במערך, או -1 אם x אינו מופיע. אם x מופיע בשתי הצלעות, ניתן להחזיר כל אחד מהאינדקסים.

• ניתן להניח כי הקלט תקין, כי n ≥ 3 וכי המערך אכן הררי.
• אין לשנות את תוכן המערך ואין להקצות זיכרון דינמי.
• שימו לב: נדרשים כאן שלושה חיפושים בינאריים — אחד לאיתור השיא ואחד בכל צלע. הצלע היורדת דורשת השוואה הפוכה.

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד.

תת-מחרוזת של s תיקרא סיסמה חזקה אם מתקיימים כל התנאים הבאים:

• אורכה לפחות 3;
• היא מכילה לפחות תנועה אחת (a, e, i, o, u);
• היא מכילה לפחות עיצור אחד (כל אות שאינה תנועה);
• אף אות אינה מופיעה בה יותר מפעמיים.

על הפונקציה להחזיר את מספר תתי-המחרוזות של s שהן סיסמאות חזקות. תתי-מחרוזות במקומות שונים נספרות בנפרד, גם אם תוכנן זהה.

• אין לשנות את תוכן המחרוזת s, אפילו לא באופן זמני.
• ניתן להניח כי הקלט תקין וכי s אינה ריקה.
• מערך בגודל קבוע (26 תאים) נחשב מקום Θ(1). אין להקצות זיכרון דינמי.
• בשלד נתונה לכם פונקציית העזר is_vowel. אינכם חייבים להשתמש בה.
• שימו לב לדרישת הזמן — כאן היא ריבועית, לא לינארית. התנאי "אף אות לא יותר מפעמיים" נשבר לתמיד ברגע שנשבר, וזה מאפשר עצירה מוקדמת.

שאלה 4 25 נק' — רקורסיה

נתון מערך arr של מספרים שלמים באורך n ≥ 1. ייתכנו איברים שליליים, חיוביים ואפסים.

תת-מערך רציף הוא קטע רציף ולא ריק של המערך.

על הפונקציה להחזיר את הסכום המרבי של תת-מערך רציף. שימו לב שתת-המערך חייב להכיל לפחות איבר אחד — ולכן אם כל האיברים שליליים, התשובה היא האיבר הגדול ביותר (והיא שלילית).

רמז: הפרידו בין שני גדלים: הסכום המרבי של תת-מערך המסתיים בדיוק באיבר האחרון, והסכום המרבי בקידומת הקצרה יותר. הראשון מתקבל מהראשון של הקידומת, והתשובה היא המקסימום בין השניים.

• על הפונקציה להיות רקורסיבית בלבד, ללא שימוש בלולאות — בכל הפונקציות שתכתבו.
• אסור להשתמש בפונקציית מעטפת — examT_q4 עצמה חייבת לקרוא לעצמה.
• ניתן להשתמש בפונקציות עזר, יש לממש את כולן, וגם הן חייבות להיות רקורסיביות בלבד.
• אין להקצות זיכרון דינמי ואין להשתמש במשתנים סטטיים או גלובליים.
• אין דרישות סיבוכיות בשאלה זו.

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

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