שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2017 - מערכים

כתבו שיטה יעילה המקבלת כפרמטר מערך חד-ממדי arr המלא במספרים שלמים חיוביים **הממוינים בסדר לא יורד**. השיטה תחזיר מהו המספר הקטן ביותר שאי אפשר להיות סכום של קבוצת מספרים מהמערך. חתימת השיטה היא: ```java public static int findSmallest(int[] arr) ``` **דוגמאות:** - עבור המערך arr הבא: | 0 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 2 | 6 | 10 | 11 | 15 | מהו המספר הקטן ביותר שלא יכול להיות סכום של חלק מאיברי המערך? 1 יכול להיות כי הוא הסכום של arr[0]. 2 יכול להיות כי הוא הסכום של arr[1]. 3 יכול להיות כי הוא הסכום של arr[0] ו-arr[1]. 4 לא יכול להיות סכום של חלק מאיברי המערך (ולא דרושה רצופים). לכן השיטה תחזיר 4. - עבור המערך arr הבא: $\{1, 1, 1, 1\}$ - השיטה תחזיר 5 - עבור המערך arr הבא: $\{1, 1, 3, 4\}$ - השיטה תחזיר 10 - עבור המערך arr הבא: $\{1, 3, 5, 10, 20, 40\}$ - השיטה תחזיר 2 - עבור המערך arr הבא: $\{1, 2, 4, 10, 11, 15\}$ - השיטה תחזיר 8 אפשר להניח שהמערך מלא במספרים שלמים חיוביים והוא ממוין בסדר לא יורד. השיטה שתכתבו צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. תשובה שאינה יעילה תקבל מעט נקודות בלבד. כתבו מה סיבוכיות הזמן וסיבוכיות המקום של השיטה שכתבתם.

רמז: עברו על המערך משמאל לימין ושמרו משתנה res שמייצג את המספר הקטן ביותר שלא ניתן ליצור. אם arr[i] <= res, אפשר להרחיב את הטווח.

פתרון: הרעיון: נשמור משתנה `res` שמייצג את המספר הקטן ביותר שלא ניתן ליצור כסכום. נתחיל עם `res = 1`. עוברים על המערך: אם `arr[i] <= res`, אז ניתן ליצור את כל המספרים עד `res + arr[i] - 1`, ולכן נעדכן `res = res + arr[i]`. אם `arr[i] > res`, אז `res` הוא התשובה. ```java public static int findSmallest(int[] arr) { int res = 1; for (int i = 0; i < arr.length; i++) { if (arr[i] <= res) res += arr[i]; else return res; } return res; } ``` **הסבר:** מתחילים עם `res = 1`. בכל שלב, אם `arr[i] <= res`, אז בעזרת `arr[i]` ניתן להרחיב את טווח הסכומים האפשריים מ-$[1, res-1]$ ל-$[1, res + arr[i] - 1]$. אם `arr[i] > res`, יש "חור" ו-`res` לא ניתן לייצוג. **סיבוכיות זמן:** $O(n)$ - מעבר יחיד על המערך. **סיבוכיות מקום:** $O(1)$ - משתנה עזר יחיד.