《程序员的数学》第三章，从强大的余数到分类问题，读书笔记

本来这一章没有想单独一份笔记发上来，但是看了几个问题之后，还是觉得挺有意思的，决定发一篇。

1.    寻找恋人问题

假设我有个恋人（“胡说，程序员不是在该bug就是在写bug，哪来的恋人”“说了是假设”“那也不行”“。。。”），我们两个的位置如下图所示，已知条件为她（他？）十二个月前在G（点？），且其移动规则为每一个月必须移动，不能原地踏步，且只能移动到相邻的点，问题：现在她有没有可能在A？

首先，看到这题目的问题时候，我在想：为啥十二个月？（给你个惊喜，手动狗头）。

作者的解题思路也很值得借鉴，先按比较小的数移动规律如下：

第一个月可能地点：C, F, H

第二个月可能地点：B, D, E, G

第三个月可能地点：A, C, F, H

第四个月可能地点：B, D, E, G

…

由此可见，当十二个月之后，恋人不会在A点出现（果然抛弃了你）

实际上，只要时间够长的话，可以将从起始点经过奇数次移动可以到达的点和起始点经过偶数次移动可以到达的点分为两个集合，这样就比较好理解了

2.    铺设草席

已知如图，用左边的草席能否完整铺完右边的炕？？？条件是不允许剪断左边的，已知左图的席子无限

分析：如果可以剪开就好了，只要数出右边的奇偶性就行了，但是不让剪开，就只能另辟蹊径了，给两个格子的草席图上颜色，按照规则对整个“炕”进行着色，由于最外边两个是奇数，所以只能将其涂成有色和空白间隔的样子，如下图：

最后数一下“炕”上的有色和无色格子各自是否相等即可得出答案è不能铺满“炕”~~~

3.    哥尼斯堡七桥问题引申到一笔画

经典问题了，问题原图如下来源网络：

问题是：找出一种走法，走遍七座桥，但不能重复经过同一座桥，起点和终点可以不同，陆地可以虽已经过多次

抽象成我们程序员眼中的问题就是如下图了，其中边代表桥，节点代表陆地：

那么问题就可以简化了，还是有边的时候可以走，但是每次经过一个边的时候，我们将这条边删除掉，最终不能移动的时候，整个图中是否还有边？

进而就转换为跟节点度有关的问题了（可以加点和边，解法相同），从起点出发，起点度减掉1，经过中间节点，度减掉（出和入两方面）2，到达终点，终点度减1，这样，若能完成条件所说，途中将不存在边，即原图中的节点的度要么全是偶数（起点与终点相同），要么只有两个点的度为奇数，其余节点的度均为偶数（起点与终点不同）
好啦，十一暂停不更，这篇算提前了，见谅啦~~~