三人三鬼问题解决思路

75 阅读 0 评论 50 点赞

我是靠谱客的博主飘逸乌冬面，最近开发中收集的这篇文章主要介绍三人三鬼问题解决思路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：
3人3鬼过河，船只能坐2个家伙，且那边的鬼都不能比人多，问该如何过河？
问题补充：鬼只要发现他们的数量比人多时就会攻击人，所以不仅是岸上鬼不能比人多，也不能出现

这张图的思想是：首先确定鬼和人的实际状态范围，直接在初期阶段就排除那些干扰项，具体的状态可能是：
1. 人为0，鬼可以是0,1,2,3;
2. 人为3，鬼可以是0,1,2,3;
3. 人数等于鬼数=0,1,2,3;
所以所有可能参与转换的状态有10种，如下图：

红色点：参与状态转换的点;
绿色数字：走步的顺序;
蓝色的0或1：无船和有船;

根据里面的规律：只要是标记蓝色0的就是无船的状态，他的下一个状态一定是增加的状态，就是在往上画或往右画，且每次画的格数为1或2（船的载重范围）;还有个小细节就是在转换的过程中比如是要增加啦不能让已经存在的消失（具体画了才会发现，呵呵）;

用这个方法很短的时间里就会解决这个问题，
-------------------------------------------------------------------------------------------EOF