渡河問題
有一農夫帶著一隻狼、一隻羊及一個高麗菜渡河,而農夫划著小舟,一次只能載一物件。當農夫不在場時,狼會吃掉羊,羊會吃掉菜。只有農夫在場時,才不會發生上述情形。討論其最小移動次數及方法總數。
將菜、羊、狼編號為1、2、3,規定2能吃掉1,3能吃掉2,食性距離為一。其移動次數為7,方法總數為2。再將物件總數增加至n,利用合法狀態、連線數得到移動次數為7,方法總數為。另外討論平均移動次數,以了解物件編號為奇數與偶數不同的移動情形。
當了解距離為一時的移動情況後,延伸至距離大於等於二時,最後分成三個種類來討論。分別為:
(一)物件總數:n ? d+1:
走法總數:n2 - n 種走法
次數:3次
(二)物件總數n=(β(d+1)+1):
走法總數:-Y種走法
次數:5次
(三)物件總數n=(β(d+1)+R),其中(R?{2~d}:
走法總數:-Z種走法
次數:3次