אלגוריתמיקה - מציאת סכום האיברים הנותן תוצאה הכי קרובה למספר?

[Shay Ben Moshe]

נכתב במקור על ידי MasterT

לא הבנתי בדיוק למה התכוונת. זה חלק ממטרה יותר גדולה כאשר בחלק מהתכנון של דרך הפתרון נתקלתי בדבר זה.

Exa.co.il: אבל בסופו של דבר אני רץ על הכל כדי להיות בטוח (או עוצר כשאני מתרחק יותר) ואני מחפש משהו יותר יעיל...

אני לא רוצה כיצד עץ בינארי יעזור כאן לפתרון...

שיי: זה +/- איבר.
תזכור שאין תמיד 3 - יכול להיות 2 ויכול להיות 10. בכל מקרה, זה שדבר ראשון צריך למיין כמו ששניכם אמרתם, אני מסכים.
נניח שאני מסדר (סדר עולה).
אני יכול לקחת את האיבר הראשון, ונניח ש-p הוא המטרה, אז D = p - a1
אם p - a1 + a2 קטן יותר מ-D, אז D שווה לביטוי שכרגע הראיתי, וממשיך הלאה עם כל שאר האיברים. אם לא אז מנסה פעולה חיסור וממשיך. וחוזר חלילה. נראה לי הדרך הכי אינטואיטיבית שבן אדם יעשה.


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

בהנחה שאתה עובר על כולם הסיבוכיות היא n^2 - n, בהנחה שאתה עובר עם רשימה עולה של המספרים על כל קומבינציות החיבור (מבלי לחזור על ביטויים שווים a+b b+a) והחיסור (אך אם עשית b-a לא תעשה a-b כיוון שהמספר או שללי או חיובי.
ניתן להוכיח בקלות לכל n:
למספר הראשון נחבר את כל הבאים אחריו (n - 1).
לשני נחבר את כל הבאים אחריו (n - 2).
...
לn - 2 נחבר את כל הבאים אחריו (2).
לn - 1 נחבר את כל הבאים אחריו (1).
לn לא נחבר דבר.
משמע הסכום הוא מk = 1 עד k = n-1 של k. סכום הסדרה הוא 1 + (n-1) כל זה כפול n-1 חלקי שתיים. במילים פשוטות (n^2 - n)/2.
זו ההוכחה לחיבור, לחיסור מתקיים או דבר, מהגדול ביותר מחסרים את כל השאר, מזה שאחריו את כל מי שתחתיו וכולי.
נחבר (n^2 - n)/2 ל(n^2 - n)/2 ונקבל n^2 - n.

כמה שאני אוהב מתמטיקה D: