שיחת פורטל:מתמטיקה/חידה/49

פתרון נוסף

הבנתי ממישהו שיש פתרון יעיל יותר. הייתכן? הדס - שיחה 23:53, 15 ביולי 2008 (IDT)

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

סיבוכיות הפתרון שפורסם גבוהה מדי.

הפתרון המוצג לחלקה השני של החידה לא שלם בעיני. להכפיל כל מספר מ - 0 עד N זו פעולה ארוכה וקשה לחישוב, אפילו יותר מאשר מעבר נוסף על המערך (למעשה כנראה אפילו N מעברים) ולכן לטעמי פתרון זה כפי שהוא לא נכון. ניתן לשפר פתרון זה עם כפל מודולו N+2, זהו פתרון יותר יעיל בהרבה. פתרון שלטעמי יותר יפה זה לסכום את ריבועי המספרים, ולפתור בקלות שוב, עם 2 משוואות בשני נעלמים.