שלום לכם!

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

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

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

שבוע טוב,

סקובידו



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

14 תגובות

  • דוד

    הגיוני אבל לא בגלל טענתך

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

  • רמי

    התשובה לשאלה?

    האם תשובתי הסופית לשאלה זו 2166 נכונה?
    או היא רק קרובה לתשובה?
    או שהפתרון שונה לחלוטין?

  • מומחה מצוות מכון דוידסוןסקובידו

    משוב

    איך הגעת לנקודות התדלוק בפתרונך מה- 14.9, 19:33?

    לדעתי אפשר עם קצת פחות...(פחות נקודות תדלוק ופחות קילומטרים)

  • רמי

    תהליך קבלת נקודות תדלוק למינימום דלק/מרחק נסיעה

    הגדרתי פונקציה רקורסיבית (f(KM) = (fuel,d שמקבלת מספר ק"מ של מדבר לחציה ומחזירה את מינימום הדלק הנדרש ואת המרחק לנקודת התדלוק הקרובה משם צריך לעבור כדי להשיג מינימום דלק זה.
    למשל אם נפעיל (f(181 נקבל (183,1) . כלומר מדבר ברוחב 181 ק"מ , המינימום יתקבל אם בק"מ ה 180 (1 ק"מ מנקודה 181)נתדלק וננוע עד סופו. בסה"כ נשתמש ב 183 ליטר דלק (וגם 183 ק"מ).
    למשל אם נפעיל (f(400 (זה בדיוק מה שאנו צריכים לתוצאה הסופית) התשובה תיהיה אוסף של נקודות בהם יש להתתדלק .הבדיקה תיהיה לחקור מי המינימלי בין כל האפשרויות הבאות :
    (f(399 , ו (f(398 , ... ו (f(311 ובמקביל תתקבל שרשרת נקודות תדלוק מינימלית . ולפעמים יותר משרשרת נקודות אחת.
    הנחת בסיס שלי : במרחק 180 מהיעד ליצור נקודת תדלוק לחציה רצופה של שארית המדבר. נראה לי כי זה מינימלי משיטות אחרות בסוף הדרך.

  • רמי

    דוגמא לשלבי הפתרון

    נקודה סה"כ הפרש
    ==== === =====
    [_0_] [_0__] [_0_]
    [180] [ 180] [180]
    [240] [ 360] [ 60]
    [276] [ 540] [ 36]
    [301] [ 715] [ 25]
    [321] [ 895] [ 20]
    [337] [1071] [ 16]
    [351] [1253] [ 14]
    [363] [1433] [ 12]
    [374] [1620] [ 11]
    [383] [1791] [ 9]
    [392] [1980] [ 9]
    [399] [2141] [ 7]
    [400] [2166] [ 1]

    נקודה - נקודת תדלוק. המרחק הישיר בין נקודת התדלוק לסוף המדבר (נקודת סיום)
    סה"כ - המרחק הכללי שהמשאית תצטרך לנסוע מנקודה זו עד סוף המדבר עם המעבר דרך נקודות התדלוק.
    הפרש - המרחק עד נקודת התדלוק הבאה

    (*) זו רק דוגמא אחת. אפשר ליצור הרבה דוגמאות אך המינימום מביניהן יתן 2166 ק"מ.

  • מומחה מצוות מכון דוידסוןסקובידו

    נקודות תדלוק

    הנחת הבסיס שלך מצוינת. בהמשך יש לשאול: איפה כדאי ליצור נקודת תדלוק שלפני האחרונה כך שיהיו 180 ליטרים דלק בנקודת תדלוק האחרונה. בסדרה 400, 220, 160, 124 יש חוקיות מסוימת שבהמשך אתה עוזב. ה"טעות" היא קטנה, כנראה טעות עיגול בלבד. בכל זאת אפשר לשפר את התוצאה טיפ-טיפה.

  • רמי

    הרחבת התשובה

    ניתן לבחון השאלה לגבי מרחקים אחרים וקיבולות אחרות של המשאית.
    להלן דוגמאות ממה שמצאתי :

    מרחק מינ. ק"מ קיבולת מיכל
    [300] [ 10306] [ 90]
    [300] [ 3680] [110]
    [300] [ 1870] [130]
    [300] [ 1154] [150]
    [320] [ 16158] [ 90]
    [320] [ 5312] [110]
    [320] [ 2552] [130]
    [320] [ 1508] [150]
    [340] [ 13132] [100]
    [340] [ 4962] [120]
    [340] [ 2568] [140]
    [340] [ 1584] [160]
    [360] [ 19668] [100]
    [360] [ 6944] [120]
    [360] [ 3424] [140]
    [360] [ 2038] [160]
    [360] [ 1388] [180]
    [380] [ 15968] [110]
    [380] [ 6464] [130]
    [380] [ 3374] [150]
    [380] [ 2114] [170]
    [380] [ 1464] [190]
    [400] [ 13596] [120]
    [400] [ 6092] [140]
    [400] [ 3370] [160]
    [400] [ 2166] [180]
    [400] [ 1548] [200]
    [420] [ 19030] [120]
    [420] [ 8124] [140]
    [420] [ 4334] [160]
    [420] [ 2710] [180]
    [420] [ 1892] [200]
    [440] [ 16374] [130]
    [440] [ 7558] [150]
    [440] [ 4296] [170]
    [440] [ 2764] [190]
    [440] [ 1954] [210]
    [460] [ 22324] [130]
    [460] [ 9886] [150]
    [460] [ 5444] [170]
    [460] [ 3414] [190]
    [460] [ 2366] [210]
    [460] [ 1774] [230]
    [480] [ 19262] [140]
    [480] [ 9222] [160]
    [480] [ 5302] [180]
    [480] [ 3454] [200]
    [480] [ 2442] [220]
    [480] [ 1848] [240]
    [500] [ 16908] [150]
    [500] [ 8744] [170]
    [500] [ 5212] [190]
    [500] [ 3468] [210]
    [500] [ 2514] [230]
    [500] [ 1926] [250]

  • רמי

    שיפותרון : 2166 ק"מ

    מצאתי שני פתרונות שונים מאוד הנותנים תוצאת מינימום זהה : 2166 ק"מ
    נראהשהתוצאות הקודמות שלי אינן מדוייקות .

    להלן נקודות התידלוק (שמהם נקבע באופן חד חד ערכי כמויות הדלק הנדרשות והקילומטראז' הנדרש עבורן) :

    1) 0 1 8 17 26 37 49 63 79 99 124 160 220 400 (14 נקודות תידלוק)

    2) 0 1 2 3 ... 218 220 400 (כל הנקודות מ 0 ועד (וכולל) 218) (220 נקודות תידלוק)

  • רמי

    שיפורתרון : 1866 ק"מ

    הסבר לשורות בטבלת המספרים:

    1) כמות הדלק בתחנה
    2) מרחק מתחילת מסלול של נקודות התידלוק
    3) סה"כ קילומטראז' אל כל נקודת תידלוק

    1) 0000 0042 0111 0213 0383 0559 0735 0909 1089 1267 1437 1618 1638
    2) 0400 0220 0178 0145 0109 0083 0063 0047 0033 0021 0011 0001 0000
    3) 0000 0180 0126 0099 0180 0182 0180 0176 0182 0180 0170 0190 0021

    מספר תחנות תדלוק (כולל נקודת התחלה וסיום) : 13
    סה"כ דלק נצרך : 8363 ליטר
    סה"כ המרחק שהמשאית נסעה : 1866 ק"מ

  • רמי

    שיפור פתרון אחרון : 2646 ק"מ

    הסבר לשורות בטבלת המספרים:

    1) דלק בתחנה
    2) מרחק בין תחנות תידלוק
    3) מרחק מתחילת מסלול של נקודות תידלוק
    4) קילומטראז' אל כל נקודת תידלוק

    1) 0000 0060 0230 0563 0917 1263 1433 1621 1801 2326 2646
    2) 0180 0060 0050 0033 0024 0010 0010 0008 0020 0005 0000
    3) 0400 0220 0160 0110 0077 0053 0043 0033 0025 0005 0000
    4) 0000 0180 0180 0350 0363 0360 0170 0190 0168 0540 0145

    סה"כ דלק נצרך : 12860 ליטר
    סה"כ המרחק שהמשאית נסעה : 2646 ק"מ

  • רמי

    פתרון טוב יותר : "רק" 2980 ק"מ

    הסבר לשורות בטבלת המספרים:

    1) דלק בתחנה
    2) מרחק בין תחנות תידלוק
    3) מרחק מתחילת מסלול של נקודות תידלוק
    4) קילומטראז' אל כל נקודת תידלוק

    1) 0000 0060 0210 0365 0680 1205 2000 2980
    2) 0180 0060 0030 0035 0035 0035 0025 0000
    3) 0400 0220 0160 0130 0095 0060 0025 0000
    4) 0000 0180 0180 0150 0315 0525 0805 0825

    סה"כ דלק נצרך : 7500 ליטר
    סה"כ המרחק שהמשאית נסעה : 2980 ק"מ

  • רמי

    הוכחת קיום פתרון

    דוגמא לפתרון (שאפשר לשפרו):
    ====================

    הסבר לשורות בטבלת המספרים:

    1) דלק בתחנה
    2) מרחק בין תחנות תידלוק
    3) מרחק מתחילת מסלול של נקודות תידלוק
    4) קילומטראז' אל כל נקודת תידלוק

    1) 0000 0180 0360 0720 1440 2880 5160
    2) 0180 0045 0045 0045 0045 0040 0000
    3) 0400 0220 0175 0130 0085 0040 0000
    4) 0000 0180 0180 0360 0720 1440 2280

    סה"כ דלק נצרך : 10740 ליטר
    סה"כ המרחק שהמשאית נסעה : 5160 ק"מ
    (הוספתי אפסים משמאל למען העימוד(*))

    (*) החלק הקשה והמאתגר בתהליך הפתרון הוא כתיבתו באתר החדש בצורה קריאה!!

  • שלי

    לא הגיוני

    אם המשאית יכולה להשאיר מיכלים לאורך הדרך שיהוו "תחנות דלק" עבורה, היא יכולה מראש להעמיס על עצמה מיכלים ובהם 220 ליטר הנידרשים להמשך הנסיעה, ולנסוע רק 400 ק"מ.

  • רמי

    כן הגיוני

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