חידה הבאה

[eug]

חידה הבאה

יש בניין של 100 קומות. יש 2 כדורי זכוכית זהים.ניתן לזרוק את הכדורים מכל קומה בבניין. צריך לבנות אלגוריתם זריקת כדורים מהבניין אשר מגלה את הקומה שהחל ממנה הכדורים נשברים כתוצאה מהנפילה תוך מספר זריקות מינימלי.

 

[פרובוקטור]

../images/Emo62.gif אני יודע!

מחלקים את הקומות שבבניין ל-3 חלקים (קבוצות): 1-33, 34-66, 66-99. לוקחים את הכדור הראשון וזורקים אותו מהקומה הכי גבוהה בכל קבוצה (קודם מ-33, אחר כך מ-66 ובסוף מ-99*). אם הכדור נשבר, לוקחים את השני וסורקים אחת-אחת את הקומות באותה קבוצה עד שמגיעים לקומה שבה הוא נשבר. מספר הזריקות המקסימלי שביטה זו הוא 35 זריקות (3+32=35). *אם הכדור לא ישבר בקומה 99 עלינו לבדוק האם הוא ישבר בקומה 100, או אולי הוא לא יישבר משום קומה. (דוגמא בציור: אם זורקים את הכדור הראשון והוא נשבר בנסיון הראשון [דהיינו בקומה 33] אז מתחיל לזרוק את הכדור מקומה 1, 2, 3, 4 .... עד הקומה הנמוכה ביותר שבה הכדור יתרסק. לחליפין אם הכדור הראשון ישבר בקומה 99 אז ננסה עם הכדור השני: 67, 68, 69, 70... עד שהכדור ישבר)

 

[פרובוקטור]

הדוגמא שבציור...

 

[alex11m]

אז למה לא לחלק ב 4

במקום לחלק ב3 את הבניין אפשר גם ב 4 ואז מספר הזריקות יהיה (100/4)+4=25+4=29

 

[alex11m]

או ב5

20+5=25

 

[פרובוקטור]

צריך לחלק ב-10 ואני אנמק

כי 10 זה השורש של מאה, ולכן חיבור של 10+10 (מספר הזריקות המקסימאלי) יהיה הכי נמוך.

 

[ycyclop]

אפשר יותר טוב

 

[Jjack]

למה לא לבצע

חיפוס בינארי? קומה 50, 75, 62, 56, 59, 58, 57--> 7 צעדים סה"כ

 

[Foma]

תשובה

כי יש לך רק 2 כדורים וכשתשבור את השני - נגמר הסיפור!

 

[nirshats]

קצת שכל...

לא שמתם לב: יש רק 2 כדורים. מה שאומר שצריך לחשוב תמיד על המצב בו הראשון נשבר , ככה שאם נתחיל גבוה מידי נצטרך לעלות קומה קומה. נראה לי שמצאתי את הפתרון הכי קצר , סה"כ 14 צעדים במקרה הכי גרוע, זה הולך ככה: נתחיל מקומה 14 , אם הוא ישבר נעלה עם השני מקומה 1 ככה שבמקרה הכי גרוע הוא ישבר ב13. אם הוא לא ישבר נעלה לקומה (+13)27 , ככה שבמקרה שבקומה הזאת הוא ישבר נצטרך לבדוק רק מ14 עד 27 (12 קומות הכי גרוע). וככה הלאה: לקומה ה (+12)39 ה (+11)50 (+10)60 (+9)69 (+8)77 (+7)84 (6)90 (5)95 (4)99 100 (אפשר אפילו 102 ,104 , 105) אולי אפשר לייעל עוד קצת , הבעייה היא שאם מתחילים מ13 אז צריך יותר נסיונות במקרה שהם לא נשברים עד קומה 100

 

[טלמון סילבר]

../images/Emo127.gif

בזמנו דניאל (Palidfull) הציג ניתוח מלא למספר כלשהו של קומות ולמספר כלשהו של כדורים, וליתר דיוק: למציאת מקסימום הקומות עבור מספר כלשהו של כדורים.

 

[nirshats]

../images/Emo45.gif עבור 2 כדורים פשוט

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