: 行了如下吉普車的後勤問題。 : ﹝問題﹞ : 有台吉普車，要橫越2000km的沙漠，但車上所能裝載的汽油量至多可跑 200km。 : 因此必需如下的來回往返才能橫越沙漠。 : 先開至50km處，放下供 100km的油箱在此，接著返回裝滿油。 : 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。 : 接著再開至50km處，放下供 100km的油箱在此，接著返回裝滿油。 : 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。 : 此時 100km處有供 200km的油， : 第三趟一次開至 100km處，加滿，再往前跑至 150km處，再回來....... : 問：若要橫越沙漠，最少要耗掉多少的油量，其方法為何？ : (前三次不一定要照我上面所舉的例子) : ﹝備註﹞ : 我不知答案.... : 關於來源的部份，我現在手邊沒書，只憑印象。 來回答一下這個老問題，最近在瀏覽板上的問題，發現這個問題相當有趣 平凡的題目，答案卻是複雜到極點。 首先回答這個題目，根據我程式所跑的結果，是有問題的!! 最多可裝200km的油要跑長達2000km的沙漠。需要高達數萬個儲油點!! 亦即最少能跑好幾百萬km的汽油，雖然有解但極度不合理 (應該說很不漂亮，非程式加入否則用數學邏輯方法無法求詳細解) 後來上網查，其題目原本型態為: 最多可裝500km的汽油，要跑1000km的沙漠 這就有一個合理的解 我將之改變題目如下: =============================================================== 中東情勢危急，你被迫逃離家鄉，然而前往中立國途中，必須穿越1000公里的沙漠公路， 然而你的愛車只能承載500公升的汽油(為了簡化題目，一公升汽油都是跑一公里)，勢必 要先載汽油到路上放著，然後再回家鄉補充汽油，重複這些步驟以能穿越公路。 試問，你最少需要從家鄉拿多少公升汽油，才能到達目標呢? =============================================================== 我有將其解答過程(結答與網路上所得相同)詳細寫在自己Blog上 若板主允許，可將之整理發表在此，也歡迎大家一起思考這一題!! -- — 請多指教喔!! ／＼●／＼ )) (( ／ /▲\ ＼ \\ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.244.54.130