|
从最近一段时间发的推文来看，关于游戏的话题，还是最受朋友们喜欢，因此，数学佬决定投大家所好，继续介绍各种数学游戏及其解法和原理。借着玩迷宫的威风，我又玩了一阵子小学生常玩的游戏——一笔画。 所谓一笔画，就是一笔把一个图形画出来。例如下面是一个非常简单的一笔画题目。 其中的数字就是解法的路径顺序。当然解法不止一种，你完全可以走出不一样的解答。 而下面则是一个稍难的一笔画问题。 亲爱的朋友，你可以试一试哦，不那么容易的。 当然，也不那么难，当年有个年轻人，轻松解决了这个问题，并据此写成论文，这个年轻人叫欧拉，他写的这篇论文叫《哥尼斯堡的七桥》，这篇论文开启了一个数学分支。 当然，欧拉不会无聊地解一笔画问题，他是在解决一个实际问题。哥尼斯堡有条河，河中央有两个小岛，为了方便居民往里，一共建造了七座小桥，纵横交错，于是有不少人开始尝试，能否不重复地走完所有的桥？ 数学家欧拉首先很清晰地看到，解决这个问题绝不能自己亲自去走，当然拉着女朋友去走也是解决不了问题，第一步就必须从实际问题中跳出来。所有的桥，其实我们一点也不关心是不是石头桥是不是木头桥，也不关心栏杆上雕着狮子还是猴子，甚至我们也不关心桥连着的是小岛还是河岸。对吧，于是问题就转变成 这个图形中，是否能找到一条路径，不重复走遍所有边？ OK，伟大的欧拉还是没有直接寻找这个问题的答案，而是想，如果能找到，那么这个路径应该具有什么样的特点？显然，除了起点和终点，所有的中间点，都应该“只要有进就必须有出”，换言之，它们的边必须是偶数。 好的，问题解决了。我们称边为偶数的点为偶数点，边为奇数的点为奇数点，则 如果一个图的所有点都是偶数点，那么这个图一定能一笔画出，用任意一个点做起点和终点即可。 如果一个图的奇数点是2个，那么这个图也能够一笔画出，用其中一个点做起点，另一个点做终点即可。 除此之外，奇数点不是0个或2个，这个图无法一笔画出。 而哥尼斯堡的七桥问题中，4个点都是奇数点，当然是无法一笔画出了——答案居然是无解！ 后来的研究加了个条件，这个图首先得连着的，称为连通图。这个条件当然对，但是很无厘头。 后来又有人研究了，说如果这个图的奇数点有2n个，则它可以用n笔画出。（好吧，正确，可以写成论文，巴特，我认为没有创意） 废话不多说，我们已经知道了解一笔画问题的关键：数点的边。找出奇数点，没有奇数点则任意点为起点，有2个奇数点则一个起点一个终点。中间的路径很容易试，解法太多了。
在这个问题中，左右角的两个点是奇数点，选其中一个做起点一个做终点，哗哗哗就解决了。什么？怎么走？深度优先搜索呀。很快的，几乎不需要怎么回溯。 在网上的游戏中，为了增加难度，还设置了一些需要走两次的线（要点：根本就可以忽略不计，因为走两遍不就是回到原点嘛……），还有的设置一些单行线，（要点：这是真的障碍，因为单行线会大幅度减少解的个数），还有的设置了跳转，（要点：自动跳转就相当于一条边而已） 小结：一笔画问题，就是数一数每一个点的边数。如果全部是偶数点，则从任意一点出发可以走一个圈回到出发点；如果两个奇数点，则从其中一个点出发可以走一个链回到另一个奇数点。 |
|
|
