חידה יפה

[nautilus7791]

חידה יפה

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

 

[yossiea]

על פניו...

זה נראה כאילו הרעיון הוא לחלק את הערמה ל-2 בכל פעם ולבדוק כל חלק בנפרד. אחרי לא יותר מ-log N בדיקות נמצא את המטבע. אבל אני חושד שהאלגוריתם האופטימלי יכול להיות קצת יותר טוב מלוגריתם בבסיס 2 של n אחרת לא היית שואל. אם נחלק את n ל-3 בכל פעם זה נראה יותר טוב. בעקרון עם חלקים גדולים יותר יש פחות חלקים לבדוק אבל מצד שני יותר בדיקות בכל חלק אחרי שמאתרים את החלק הבעייתי. אז צריך למצוא את האיזון בין גודל החלקים לבין מספר הבדיקות. זה הכיוון הנכון? זה מעניין. צריך לחשוב על זה.

 

[nautilus7791]

נכון,הפתרון הוא logN בבסיס 3

 

[nautilus7791]

כעת מותר לשים על כל צעד של המאזניים

עד K מטבאות.מה הסיבוכיות כעת?

 

[ELIELI22]

נחמד ..

כן באמת לחלק ל-3 עדיף קצת על 2.