צטט: השכן ממול 2011-12-21 15:52:00

צטט: אופק_כהן 2011-12-20 20:25:25

צטט: השכן ממול 2011-12-20 15:45:24

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

 

 

הדרך חשיבה נכונה אך ניתן לבצע בפחות מ 19 בדיקות

 

צודק.

אפשר לשפר את השיטה ולהגיע למקסימום של 14 בדיקות.

הסבר בלבן

באמצעות הכדור ראשון נבדוק (עד שיתנפץ) את הקומות לפי הסדר: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 (אם הוא לא התנפץ ב 99 אז נבדוק את 100).

הרעיון הוא להתחיל ב 14 לעלות 13 קומות ואחרי זה 12 קומות וכן הלאה.

ובכל צעד מקטינים את הקפיצה ב 1.

 

אם הכדור הראשון התנפץ בבדיקה n יש לבדוק בעזרת הכדור השני את כל הקומות שבין הקומה שנבדקה בבדיקה n-1 לבדיקה שבה הכדור נשבר.

 

מספר יפה@@@הבדיקות שנבצע עם הכדור הראשון עד שיתנפץ + מספר הקומות בין הבדיקה שבה התנפץ הכדור הראשון לבדיקה שלפניה יהיה תמיד 14.

 

למשל אם הכדור יתנפץ בקומה 84, יוצא שעשינו 8 בדיקות עם הכדור הראשון. עם הכדור השני נצטרך במקרה הגרוע ביותר לבדוק את 6 הקומות שבין 78 (את 77 כבר בדקנו עם הכדור הראשון) עד 83 (כולל)ככה שסה"כ בדקנו 14.

 

למה דוקא 14?

כי אם היינו מתחילים מ 15 התוצאה במקרה הגרוע הייתה 15. ואם היינו מתחילים מ 13 לא היינו מצליחים לכסות את כל הבניין.

יפה!!! ונכון

הנה עוד הסבר:

כאשר יש לנו כדור אחד, אנחנו חייבים לבדוק את כל הקומות מלמטה כלפי מעלה. כאשר יש לנו שני כדורים אנחנו יכולים לחלק את התחום לשניים ע"י השלכת כדור מקומה כלשהי ואז יש שתי אפשרויות: אם הכדור נשבר, אנחנו נשארים עם כדור אחד וצריכים לבדוק בעזרתו את כל הקומות שמתחת לזו שבדקנו מלמטה כלפי מעלה. אם הכדור נשאר שלם, אנחנו יכולים לחלק את התחום שמעל לקומה שנבדקה שוב לשניים ולהמשיך באותו אופן. השאלה היא איך לחלק את התחום.

נבדוק כמה קומות אפשר לכסות עם לא יותר מ-4 בדיקות: נתחיל מקומה 4 כך שאם הכדור ישבר ישארו לנו שלוש קומות לבדוק עם הכדור שנותר. אם הכדור לא נשבר נוכל להשליך את הכדור מהקומה השביעית (בדיקה שניה) כך שאם הכדור ישבר ישארו לנו שתי קומות (5 ו-6) לבדוק. אם שוב הכדור לא נשבר, נוכל להשליך אותו מקומה 9 (בדיקה שלישית) ואז אם הוא ישבר נבדוק את קומה 8 ואם לא ישבר נבדוק את קומה 10. כלומר, בעזרת 4 בדיקות נוכל לבדוק 4+3+2+1=10 קומות.

בעזרת 5 בדיקות נוכל לבדוק 15 קומות ובעזרת 6 נוכל לבדוק 21 קומות. אם נמשיך כך נוכל לראות שבעזרת 13 בדיקות נוכל לכסות 91 קומות ובעזרת 14 בדיקות 105 קומות. מכאן שבשיטה זו ניתן לבדוק את כל 100 הקומות בלא יותר מ-14 בדיקות. 

המספר האופטימלי הוא 14.

צריך סדרה חשבונית יורדת שסכומה גדול או שווה 100. כך בכל תור נשאר לכדור השני נסיון אחד פחות (כי הכדור הראשון ניצל אותו) כדי למצוא את המקרה הגרוע. כלומר, נזרוק את הכדור הראשון מהקומות 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. כשהוא יישבר נזרוק את הכדור השני מהקומות שבין לבין.

זה לדעתי המהלך האופטימאלי. (פירוט בלבן).

מפילים מהקומה החמישים. אם נשבר צריך לבדוק בקומות שלמטה, אם לא נשבר צריך לבדוק בקומות שלמעלה.

אם צריך לרדת למטה, יורדים לקומה ה25. ומפילים אם נשבר יורדים לחצי (קומה 12)אם לא עולים לחצי(37). וכך הלאה.

סך הכל 7 בדיקות. קומות , למשל 50 25 12 6 3 2 1  במידה שתמיד צריך לרדת למטה.

צטט: שליימ'לה 2012-02-22 22:07:02

מפילים מהקומה החמישים. אם נשבר צריך לבדוק בקומות שלמטה, אם לא נשבר צריך לבדוק בקומות שלמעלה.

אם צריך לרדת למטה, יורדים לקומה ה25. ומפילים אם נשבר יורדים לחצי (קומה 12)אם לא עולים לחצי(37). וכך הלאה.

 

סך הכל 7 בדיקות. קומות , למשל 50 25 12 6 3 2 1  במידה שתמיד צריך לרדת למטה.

אם נשבר לך הכדור השני בקומה ה25 - לא נשארו לך יותר כדורים לרדת איתם לקומות הנמוכות יותר.