מבוא למדעי המחשב - חיפוש

• עבור המערך arr הבא:

• עבור המערך arr הבא: int[] arr = {1, 1, 1, 1} השיטה תחזיר $2$
• עבור המערך arr הבא: int[] arr = {1, 2, 3, 4} השיטה תחזיר $5$
• עבור המערך arr הבא: int[] arr = {5, -1, 3, 1, 0, -2, 2} השיטה תחזיר $4$
• עבור המערך arr הבא: int[] arr = {7, 8, 9, 11, 12, 14} השיטה תחזיר $1$

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

• הפונקציה תחזיר את האורך של מסלול הקצר ביותר העובר בכל היישובים והעומד בקריטריונים, אחרת תחזיר $-1$.
• טבלת המרחקים אינה בהכרח סימטרית.
• ניתן להניח שבכל איברי האלכסון רשום $0$.
• ניתן לעבור ביישוב פעם אחת בדיוק, והמסלול לא חייב להתחיל ביישוב שמספרו $0$.
• ניתן להניח כי $N$ מוגדר ב-define והוא חיובי.

• יש להשתמש בשיטת backtracking כפי שנלמדה בכיתה.
• בשאלה זו אין דרישות סיבוכיות.
• ניתן ומומלץ להשתמש בפונקציות עזר (ויש לממש את כולן).

• 3.1 אם סכום האיברים של $L$ במיקומים $low$ ו-$high$ שווה ל-$z$: נחזיר $True$.
• 3.2 אחרת אם סכום זה קטן מ-$z$: נעדכן $low+=1$.
• 3.3 אחרת: נעדכן $high-=1$.

• עליכם לממש רעיון דומה מאוד לזה של סעיף ב.
• יש להשתמש בשתי הפונקציות שבסעיף ד.
• על הפתרון לעבוד בסיבוכיות זיכרון נוסף של $O(1)$. כלומר בכל שלב על האלגוריתם לשמור בזיכרון כמות קבועה של איברים מתוך הקלט.
• שימו לב: קיים פתרון פשוט שלא מייצר שום StopIteration ואליו אנו מכוונים.

>>> M = [[1, 5, 8, 20], [2, 9, 19, 21], [12, 15, 25, 30], [14, 22, 98, 99]]

>>> x = find_val(M, 10)
>>> x is None
True
>>> y = find_val(M, 19)
>>> y
(1, 2)