בתשובה להקשה המקשה, 04/08/03 18:45
מצעדנו המרעים 161580
easy • בתשובה להקשה המקשה יום ג', 5/8/2003, 0:46
1. עם כדור בודד האסטרטגיה היחידה היא להתחיל מקומה 1 ולעלות בכל פעם קומה אחת.
2. עם 100 כדורים (או מספר לא מוגבל של כדורים) כבר הוצעה שיטת אריה במדבר - היא אכן היעילה ביותר.
3. עם שני כדורים, האסטרטגיה המיטבית היא להתחיל מקומה 14, אם נשבר לעבור לקומה 1 ולעלות קומה אחת בכל פעם, אם לא נשבר לעבור לקומה 27, אם נשבר לעבור לקומה 15 ולעלות קומה אחת בכל פעם, אם לא לעבור לקומה 39, וכך הלאה לקומות 50, 60, 69, 77, 84, 90, 95, 99, 100, כאשר אם בקומה מסוימת הכדור נשבר יורדים לקומה אחת מעל הקומה האחרונה בה הכדור לא נשבר וממשיכים משם בזהירות - קומה אחת בכל פעם.
במקרה הגרוע ביותר צריך 14 זריקות.
עבור בנין בן N קומות צריך להתחיל מהקומה ה
1/2(sqrt(1+8N)-1)
מעוגל כלפי מעלה וזה גם מספר ההטלות המקסימלי שידרש במקרה הגרוע ביותר.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161582
האייל האלמוני • בתשובה לeasy יום ג', 5/8/2003, 1:00
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161586
easy • בתשובה להאייל האלמוני יום ג', 5/8/2003, 1:36
לשם הפשטות, נניח שהבנין הוא בן 105 קומות וכן שההסתברות לקומה הקריטית להיות X היא אחידה. (1/105)
אין אף קומה קריטית שניתן לגלות בזריקה יחידה.
יש קומה קריטית אחת שניתן לגלות ב2 זריקות. (1)
יש שתי קומות קריטיות שניתן לגלות ב3 זריקות. (2 ו15)
יש שלוש קומות קריטיות שניתן לגלות ב4 זריקות. (3, 16 ו 28)
וכך הלאה כלומר התוחלת היא הסכום
1/105(1*2 + 2*3 + 3*4 + ... 15*14)=10.67
לא מדהים, בהשוואה ל7 זריקות בשיטת אריה במדבר, אבל נדמה לי שזאת התוחלת המינימלית עם 2 כדורים.
אני אשן על זה ואם אני אמצא הוכחה פשוטה או דרך יותר מוצלחת, אני מבטיח לשתף.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161613
easy • בתשובה לeasy יום ג', 5/8/2003, 9:28
יש לי טעות בחישוב התוחלת - האיבר האחרון בסכום הוא 14*14 שבא אחרי 13*14.
התוחלת היא קצת יותר מ 10.5.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161672
הקשה המקשה • בתשובה לeasy יום ג', 5/8/2003, 14:27
לצרכי המחשה, נסה להשוות זאת לתוחלת המתקבלת עבור האסטרטגיה בה שומטים את הכדור הראשון מהקומות 10, 20, 30, ...
כמובן שזו אינה יכולה להיות האסטרטגיה האופטימלית (מבחינת התוחלת) כי אם הכדור שרד את הנפילה מהקומה ה- 90, אין זה מעשה נבון להמשיך ישר לקומה ה- 100.
אתה צודק 161686
easy • בתשובה להקשה המקשה יום ג', 5/8/2003, 15:46
בשיטה הזאת יש קומה קריטית אחת שניתן למצוא בשתי זריקות, (1) שתי קומות קריטיות שניתן למצוא ב 3 זריקות, (2, 11) וכך הלאה עד 8 קומות קריטיות שניתן למצוא ב9 זריקות. (8, 17, 26 .. 71)
ב10 זריקות ניתן למצוא 11 קומות (9, 10, 18, 27 .. 81, 91)
ב11 זריקות ניתן למצוא 10 קומות (19, 20, 28 .. 82, 92)
ב12 זריקות ניתן למצוא 9 קומות (29, 30, 38, 47 .. 83, 93)
וכך הלאה עד שב18 זריקות מוצאים את הקומות 89, 90, ו99 וב19 זריקות את קומה 100.
התוחלת (בהנחה של התפלגות אחידה) היא טובה בהרבה - בערך 8.8.
אתה צודק 161728
הקשה המקשה • בתשובה לeasy יום ג', 5/8/2003, 17:47
אם הבנתי נכון, "ספירת המלאי" שרשמת מתיחסת לאסטרטגיה לפיה אחרי הקומה ה- 90 עוברים ל- 91 , 92, וכן הלאה. הלא כן?
התוחלת שיצאה לי עבור אסטרטגיה זו היא 10.81 . יתכן שטעיתי, אבל הפער בין התוצאות שלנו משמעותי (מבחינת השאלה שבדיון). בכל אופן, גם תוצאה זו כבר די קרובה לתוחלת של פתרון-החסם-המינימלי.

נניח שאני רוצה לכתוב תכנית מחשב שתמצא את האסטרטגיה האופטימלית. את מציאת המספר הכולל של אסטרטגיות אפשריות אני משאיר לחכמי הקומבינטוריקה והסיבוכיות (משהו יפה, עם נוסחת סטירלינג נניח, או פונקציות גמא, או סתם פונקציה היפרגאומטרית, יתקבל בברכה :) ). האם יש אפשרות ליעל את התהליך כך שלא יהיה צורך להתעסק עם אסטרטגיות שאינן "מבטיחות"?
אתה צודק 161865
אלון עמית • בתשובה להקשה המקשה יום ד', 6/8/2003, 9:29
אם אתה כבר יודע את התשובה לכל מספר קומות עד 99, אתה מוצא את האסטרטגיה האופטימלית ע"י חישוב פשוט שבודק רק את האפשרויות לזריקה הראשונה. בדרך זו אתה "ממשיך" את האסטרטגיה האופטימלית לבניין יותר נמוך (במקרה זה, עם 87 קומות) לאסטרטגיה אופטימלית ל-‏100 קומות. זה יעיל מאוד, ובוודאי לא מתעסק עם אסטרטגיות לא מבטיחות - זה בערך "חמדני".
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות