חידה

[yanivdan98]

הי

 

יש לי שאלה כזאת:

 

מערך בגודל N , למצוא בפחות מ- 2N השוואות את המינימום והמקסימום..

 

איך עושים את זה?

[Raf]

אתה בוחר כל פעם שני אברים (x,y) ואז משווה אותם. נניח ש-x<y

אתה מעדכן את הערך של המקסימום לפי מי שגדול מבין (y,max)

אתה מעדכן את הערך של המינימום לפי מי שקטן מבין (x,min)

בדרך הזאת אתה עושה 3 השוואות לכל שני איברים.

ז"א 1.5*N השוואות עבור N איברים

כמובן שאפשר לשפר עוד את הפתרון אבל ביקשת פחות מ-2N

[-ליאור]

זה לא מדוייק, אחרי שהוא השווה בין הראשון לשני, מה הלאה? בין השלישי והרביעי? ומי ישווה בין המקסימום והמינימום של שני השלבים האלה?

[Raf]

נגיד בהתחלה מציבים למינימום ולמקסימום את האיבר הראשון.

אח"כ משווים את הראשון לשני. נניח הראשון יותר גדול.

אח"כ משווים את הראשון (כי הוא יצא יותר גדול) למקסימום ואת השני למינימום ומציבים בהתאם.

ז"א 3 השוואות לכל 2 איברים

אח"כ עוברים לזוג המספרים הבא וכן הלאה

כל פעם המינימום והמקסימום מתעדכנים בהתאם

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