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

שאלה 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++;
    }
}

ב.

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

ג.

void f3(int n) {
    for (int i = n; i > 2; i = (int) sqrt(i))
        printf("*");
}

שאלה 2 25 נק'

נתון מערך arr באורך n של מספרים שלמים אי-שליליים, ומספר שלם D המקיים 1 ≤ D ≤ n.

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

על הפונקציה להחזיר את העלות המינימלית האפשרית על פני כל החלוקות החוקיות.

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

שאלה 3 25 נק'

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

מילה היא רצף רציף ומקסימלי של אותיות. רווח הוא רצף רציף ומקסימלי של תווי '$'. לכל רווח יש מילה שמאלית ומילה ימנית — ואם הרווח נמצא בתחילת המחרוזת או בסופה, אורך המילה החסרה נחשב 0.

יש להחליף כל רווח בתו בודד, לפי הכלל:

• '+' — אם אורך הרווח גדול ממש משתי המילים השכנות;
• '*' — אם אורך הרווח קטן ממש משתי המילים השכנות;
• '=' — בכל מקרה אחר.

על הפונקציה לבצע את ההחלפות במקום, בתוך s עצמה (תוך הזזת שאר התווים שמאלה וסיום ב-'\0'), ולהחזיר את מספר הרווחים שהוחלפו ב-'='.

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

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

נתונים שני מספרים שלמים: n חיובי, ו-k אי-שלילי.

פירוק מסודר של n לאורך k הוא סדרה של k מספרים שלמים, כל אחד גדול או שווה ל-2, שמכפלתם היא n. שני פירוקים נחשבים שונים אם סדר הגורמים בהם שונה — כך 2×6 ו-6×2 הם שני פירוקים שונים של 12.

על הפונקציה להחזיר את מספר הפירוקים המסודרים של n לאורך k בדיוק. עבור k = 0 יש פירוק אחד אם n = 1, ואפס אחרת.

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

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

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

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