אם יש מערך בעל 99 איברים, ובכל תא מספר כל שהוא בין 1 - 100 כך שיש מספר אחד שחסר

מהי הדרך היעילה ביותר לגלות את המספר שחסר?

תחשוב איזו פעולה מתמטית פשוטה אפשר לעשות על כל איברי המערך.

אפשר לסכום את האיברים במערך , לחסר המהתוצאה שצריכה להיות (סדרה חשבונית) ולמצוא את האיבר, זה ב o(n)

השאלה אם יש דרך יותר טובה

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

מעקב

אשמח אם מישהו יכול להסביר את השאלה בכלל...

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

אם המערך היה מכיל בדיוק את כל המספרים מ1 עד 100 (בלי מספר חסר) אז סכום כל איברי המערך היה בדיוק 5050. כיוון שחסר מספר כלשהו, סכום כל האיברים הוא בדיוק 5050 פחות המספר הזה. לכן האלגוריתם הוא לסכום את איברים המערך ולהחסיר את התוצאה מ5050. יש מבין?

כשתוצאת החיסור היא המספר החסר.

עברתי על המשמעות המתמטית של זה למי שמעוניין:

TOTAL = (1+99)*100 / 2

כלומר, סכום סדרה.

100, לא 99.

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

אם המערך היה מכיל בדיוק את כל המספרים מ1 עד 100 (בלי מספר חסר) אז סכום כל איברי המערך היה בדיוק 5050. כיוון שחסר מספר כלשהו, סכום כל האיברים הוא בדיוק 5050 פחות המספר הזה. לכן האלגוריתם הוא לסכום את איברים המערך ולהחסיר את התוצאה מ5050. יש מבין?

אהבתי.

נקי ויעיל