בתשובה להקשה המקשה, 04/08/03 18:45
 |
|
 |
||
|
||||
 |
הדרך היעילה לאיתור האסטרטגיות היא בדיוק כמו בחידת הקלפים - "תכנות דינמי" או פשוט פתרון באינדוקציה. גם כאן דומני שאין פתרון סגור לערך התוחלת המינימלי, ועבור 100 קומות ושני כדורים הוא יוצא 10.3 עם זריקה ראשונה מהקומה ה-13. חולשה קטנה של השאלה הזו לעומת השאלה המקורית הוא שהיא תלויה בהנחה על ההתפלגות (ברור שהתשובה משתנה אם ההתפלגות איננה אחידה - למי ששאל, כדאי לחשוב על כדור אחד ושלוש קומות). דרך אגב, התשובה הנומרית לעיל מניחה שלכל קומה יש סיכוי של 1/100 להיות הקומה הקריטית, ובפרט הכדורים בטוח נשברים בזריקה מהקומה האחרונה. אינני חושב שיש פתרון אלגנטי יותר עבור מספר כדורים כללי. עבור שני כדורים האסטרטגיה היא תמיד כמו לחידה המקורית, לדעתי: לרשום את מספר הקומות (פחות אחד, כי אין טעם לזרוק מהקומה האחרונה) כסכום 2+1+...+m ולזרוק מהקומה ה-m, אח"כ לעלות m-1 קומות, וכו' עם תיקונים קטנים כאשר המספר איננו משולשי. למשל 99=1+2+3+4+5+6+7+8+8+9+10+11+12+13 מתאר את האסטרטגיה ל-100 קומות. ערך התוחלת הוא (שוב!) בערך שורש n. |
 |
 |
 |
|
|
|
||
|
||||
|
שוב אני צועד בעקבותיך. גם לי יצא 10.3 כתוחלת, אבל יש משהו מוזר (כנראה טעות שלי): בהנתן שני כדורים, ככל שיש יותר קומות צריך להתחיל לזרוק מקומה גבוהה יותר. זה נראה הגיוני, אבל יש יוצא דופן: המקרה של 26 קומות. עבור 25 קומות, צריך לזרוק מקומה 6. גם עבור 27 קומות צריך להתחיל מ- 6. אבל כשיש 26 קומות, השיטה ממליצה לנסות קודם כל את קומה 7. טעות? |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי שיש לך טעות, רק משהו קצת מוזר במימוש: יש הרבה פעמים (תמיד?) ניוון באיזור הקומה האופטימלית, ואם אינני טועה ב-26 קומות אפשר להתחיל או ב-6 או ב-7 עם אותה תוחלת, 76/13. האם מימשת בסביבה חישובית עם נקודה צפה...? |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |