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

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

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

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

א.

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

ב.

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

ג.

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

שאלה 2 25 נק'

נתון מערך arr באורך n של מספרים שלמים, הממוין בסדר עולה ממש (arr[0] < arr[1] < ... < arr[n-1]), ומספר שלם c (ייתכן שלילי).

על הפונקציה להחזיר את מספר האינדקסים i שעבורם arr[i] - i == c (0 אם אין כאלה).

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

שאלה 3 25 נק'

נתונות שתי מחרוזות s ו-t המכילות אותיות אנגליות קטנות בלבד. נסמן n = |s| ו-m = |t|, וניתן להניח m ≤ n.

נאמר שתת-מחרוזת של s באורך m היא כמעט-אנגרמה של t אם ניתן להפוך אותה לאנגרמה של t על ידי שינוי תו אחד בדיוק (לא פחות ולא יותר).

על הפונקציה להחזיר את מספר תתי-המחרוזות של s באורך m שהן כמעט-אנגרמות של t.

• אין לשנות את s או t, אפילו לא באופן זמני.
• מערך בגודל קבוע (26 תאים) נחשב מקום Θ(1).
• רמז: חלון הוא אנגרמה בדיוק כאשר סכום ההפרשים המוחלטים בין שתי ההיסטוגרמות הוא 0. מהו הסכום כאשר דרוש בדיוק שינוי אחד? שימו לב ששינוי תו מוריד מונה אחד ומעלה אחר.

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

נתון מערך arr של מספרים שלמים באורך n (ייתכנו שליליים ואפסים), ומספר שלם x.

על הפונקציה להחזיר את מספר הזוגות (i, j) המקיימים 0 ≤ i < j < n וגם arr[i] + arr[j] == x.

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

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

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