Re: [問題] 橫越沙漠的駱駝

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者penguin7272 (企鵝)時間19年前 (2006/10/04 22:57)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串5/6 (看更多)

有一隻駱駝，它的負重上限是1000根香蕉，要穿過1000公里的沙漠。現在起點有香蕉三捆，各1000根。駱駝每走一公里要吃一根香蕉。駱駝可以在中途缷下香蕉，折返回去拿香蕉(同樣一公里要吃一根) ,過上次途中缷下的香蕉可以進行補充。問駱駝最多能載多少重香蕉到終點？ (1) 載1000根。到200公里處，身上剩800根，放下600根，帶200根回起點，剩0根。 (2) 載1000根。到200公里處，身上剩800根，載上200根，留下400根，到533公里處，身上剩667根，放下334根，帶333根回200公里處，剩0根。載上200根，留下200根，回起點，剩0根。 (3) 載1000根。到200公里處，身上剩800根，載上200根，到533公里處，身上剩667根，載上333根，留下1根，到終點，剩533根。所以533是構造的出來的以下證明此方法為最多定義折返點為駱駝到達後改變負載後往反方向前進的點上例中折返點為200,533兩個如果最好的方式只有一個折返點，設為x ├───────┼───────┤ 0 x 1000 2000根 ─────→放1000-2x 2000根 ←─────── 1000根 ─────→放1000-2x 1000根 ←─────── 0根 ────→拿2(1000-2x)─────→到達在最好的情形下最後拿2(1000-2x)之後應該有1000根所以x=2(1000-2x) x=400 到達終點時還剩400根，這當然不是最好剩下的部分分兩類 (1)說明在兩個折返點時，200,533最好 (2)三個以上折返點是浪費因為我還有報告要寫先打到這裡明天再繼續謝謝 -- 企鵝的網誌 www.wretch.cc/blog/demipenguin 胡言亂語瘋瘋癲癲 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.70.168.103