阅读量:4
目录
一，追及问题
1，警察和小偷
如下图，警察先走，警察和小偷轮流一人走一步，每次只能沿着线走到相邻的圆圈，
问警察能不能抓到小偷？
答案：能
首先编号
如果警察走到5，那么小偷就只能走到1
然后如果警察走到6，那么小偷就只能走到2
然后如果警察走到4，那么小偷无论是走到1还是5，下一步都会被警察抓住。
2，旋转的4个硬币
问题：
有一个正方形棋盘,每个顶点上放了一枚硬币。你将要玩一个游戏，规则如下：
1、你不知道游戏开始时硬币的状态(各自是哪一面朝上),但已知它们不是同一面
2、游戏中任何时候你都无法看到任何硬币
3、每一轮你可以指定任意个硬币（指定位置），工作人员会将它们同时翻面.
3、每轮之后,如果棋盘上的所有硬币都是同一面朝上,也就是说都是正面或者都是背面,则判定你胜利,游戏结束
4、如果没有满足上述条件,棋盘将会被随机旋转（90°的整数倍）并进入下一轮，而且你也不知道转了多少度
请问最坏情况下最少需要几轮就可以保证获得胜利？
思路：
首先推理出，其实只需要3种操作：上、上下、上左。因为任意操作，其实都和这3个操作是等价的（轮换对称性）
其次根据这3个操作，很容易推出最快的方案，有7步。
答案：
按照 上下、上左、上下、上、上下、上左、上下 7步去操作，最多7步就胜利了。
PS：
这题抽象成图论的问题，其实和警察和小偷的规则差不多。当然，中间一些转化方法还是需要稍微思考下，转化成的图也稍微复杂一点。
3，抓狐狸
五个洞排成一排，其中一个洞里藏有一只狐狸。每个夜晚，狐狸都会跳到一个相邻的洞里；每个白天，你都只允许检查其中一个洞。怎样才能保证抓住狐狸？
答案：
依次检查第2、2、3、4、4、3、2个洞即可。
首先检查第2个洞，如果没抓到狐狸，说明这时狐狸可能在第1、3、4、5个洞
然后检查第2个洞，如果没抓到狐狸，说明这时狐狸可能在第3、4、5个洞
然后检查第3个洞，如果没抓到狐狸，说明这时狐狸可能在第2、4、5个洞
然后检查第4个洞，如果没抓到狐狸，说明这时狐狸可能在第1、3、5个洞
然后检查第4个洞，如果没抓到狐狸，说明这时狐狸可能在第2个洞
然后检查第3个洞，如果没抓到狐狸，说明这时狐狸可能在第1个洞
然后检查第2个洞，就一定会抓到狐狸了。
二，围堵问题
三，追及+围堵
老虎棋 老虎对羊是追及问题，羊对老虎是围堵问题
