渡河問題(River Crossing Problem)
問題一 : 土人及傳教士
- 三個傳教士與三個土人一起渡河,船小一次僅能載二人,傳教士知道土人的習慣,如果土人比傳教士的人數多,則土人會吃掉傳教士,那麼如何安排才能安全渡河?如果有100個傳教士與100個土人一起渡河,這艘船最少需要來回幾趟(來回各算一趟)讓所有人安全渡河?
問題二 : 一家人與獵人
- 有一家人和獵人要渡河,這家人有爸爸、媽媽及兩個兒子、兩個女兒,獵人有一隻狼犬,因船小每次渡河只能載兩人(狼犬算一個人),且只有爸爸、媽媽以及獵人會划船;當爸爸不在時,媽媽會毆打兒子;當媽媽不在時,爸爸會毆打女兒;當獵人不在時,狼犬會咬這一家的所有人;請問要如何安排才能安全渡河?這艘船最少需要來回幾趟(來回各算一趟)讓所有人安全渡河?