砂漠の旅行の問題の解き方 (2)

分析
最後の 3 ステップは、手持ちの食料で移動
手持ちの食料を減らさずに、移動するには、途中に一つずつの食料が必要
行って、戻って来るには、途中にニつずつの食料が必要
再起を利用した、一般の n の解法
n > 3 とし
1 〜 n - 3 まで一つずつ食料をおいて、
三つの食料をもって、スタートから移動を開始すればよい
n 番目に食料を置くには、
まず、1 〜 n - 1 に二つずつ食料を置いて
三つの食料をもって、その場所に行って置いて帰って来る
1 〜 n に食料を置くには
n に置いた後に、1 〜 n - 1 に置けば良い