לחץ ▶ Run כדי להדר ולהריץ את הקובץ. אם התוכנית תבקש קלט, תוכל להקליד אותו כאן למטה.
לכל סעיף ציינו סיבוכיות זמן וסיבוכיות מקום נוסף, בסימון Θ, כפונקציה של n.
חובה לפשט את הביטוי ככל שניתן. הניחו כי סיבוכיות הזמן והמקום של printf ו-free היא Θ(1),
וכי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות המקום שלה היא Θ(n).
הניחו כי sqrt פועלת בזמן Θ(1).
שימו לב: אין הבטחה ששלושת הסעיפים מקבלים תשובות שונות.
חשבו כל סעיף מחדש — ובפרט שימו לב לערכי חזרה של פונקציות עזר, למשתנים שמשתנים בין איטרציות,
ולמיקום של free ביחס לקריאה הרקורסיבית.
א.
void f1(int n) {
for (int i = 1; i < n; i++)
for (int j = i; j < n; j += i)
printf("*");
}
ב.
int f2(int n) {
if (n <= 1) return 1;
return f2(n - 1) + f2(n - 2);
}
ג.
void f3(int n) {
for (int i = n; i > 2; i = (int) sqrt(i))
printf("*");
}
נתון מערך arr באורך n של מספרים שלמים שונים זה מזה,
הממוין בסדר עולה ממש. ייתכנו במערך מספרים שליליים ואפס.
על הפונקציה להחזיר את המספר השלם החיובי הקטן ביותר שאינו מופיע במערך (המספרים החיוביים מתחילים מ-1).
| קלט | פלט | הסבר |
|---|---|---|
| arr = {1,2,3,5,6}, n = 5 | 4 | 1,2,3 קיימים, 4 חסר |
| arr = {-3,-1,1,2,4}, n = 5 | 3 | השליליים אינם רלוונטיים |
| arr = {2,3,4}, n = 3 | 1 | 1 עצמו חסר |
| arr = {1,2,3}, n = 3 | 4 | אין חסר בתוך המערך |
n ≥ 1 וכי המערך עולה ממש.j
הוא האינדקס היחסי בתוך החלק החיובי, הערך הצפוי הוא j+1 — והתנאי
"הערך גדול מהצפוי" הוא מונוטוני. שני חיפושים בינאריים משורשרים.נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד.
לכל אינדקס i המקיים 1 ≤ i < n, נסמן ב-L את קבוצת
התווים השונים המופיעים ב-s[0..i-1], וב-R את קבוצת התווים השונים
המופיעים ב-s[i..n-1].
נאמר ש-i הוא אינדקס מכיל אם L מוכלת ממש
ב-R — כלומר כל תו של L מופיע גם ב-R, וגם
קיים לפחות תו אחד ב-R שאינו ב-L.
על הפונקציה להחזיר את מספר האינדקסים המכילים.
| קלט | פלט | הסבר |
|---|---|---|
| s = "abab" | 1 | רק i=1: {a} מוכלת ממש ב-{a,b} |
| s = "abcabc" | 2 | — |
| s = "aaa" | 0 | הקבוצות תמיד שוות, ולכן ההכלה אינה ממש |
| s = "abcd" | 0 | — |
s, אפילו לא באופן זמני.n אינו מותר.L אם ורק אם ההופעה הראשונה שלו לפני
i, ונמצא ב-R אם ורק אם ההופעה האחרונה שלו היא i או אחריה.
שימו לב שהכלה ממש דורשת שתי בדיקות נפרדות, לא אחת.נתונים שני מספרים שלמים: n אי-שלילי, ו-k חיובי.
הרכבה מסודרת של n היא סדרה של מספרים שלמים חיוביים שסכומם
n. שתי הרכבות נחשבות שונות אם סדר האיברים בהן שונה —
כך 1+2 ו-2+1 הן שתי הרכבות שונות של 3.
על הפונקציה להחזיר את מספר ההרכבות המסודרות של n שבהן כל איבר
הוא לכל היותר k. עבור n = 0 יש הרכבה אחת (הריקה).
| קלט | פלט | הסבר |
|---|---|---|
| n = 4, k = 2 | 5 | איברים מתוך {1,2} |
| n = 4, k = 3 | 7 | איברים מתוך {1,2,3} |
| n = 5, k = 5 | 16 | ללא הגבלה אפקטיבית |
| n = 3, k = 1 | 1 | רק 1+1+1 |
רמז: סכמו על גודל האיבר הראשון. הסכימה עצמה היא לולאה — ולכן גם היא חייבת להפוך לרקורסיה, בפונקציית עזר נפרדת.
examT_q4 רשאית לקרוא לפונקציית עזר רקורסיבית שמבצעת את עיקר העבודה.main./grade.