遍历算法
求一个遍历算法
如图，有一8*8的方格，要求从任一点出发，到达不同色的另一个随机格。
要求：1.必须经过所有的64格；
2.每个方格只能经过一次。
------解决方案--------------------
骑士周游问题。
------解决方案--------------------
大概想了一下 有一个思路 探讨一下
大体上就是证明 2^n边长的黑白间隔的方阵 从任意黑格出发 可以遍历整个方阵到达任意白格
对于n=1的情况 非常好证明
# 0
0 #
从任何一个#都可以到任何一个0
我把这四个位置分别叫做4个象限
2 1
3 4
对于n=2的情况
# 0 # 0
0 # 0 #
# 0 # 0
0 # 0 #
如果把这个4*4的方阵看成是一个大号的2*2 方阵 每个元素又是一个2*2方阵
不妨假设起点的#在第2象限里 那么当终点的位置在第1或第3象限的时候 就和n=1的情况一样了
也很容易找到终点位置也在第2象限或第4象限的解法。
也就是说 对于一个2^n边长的黑白间隔的方阵 用数学归纳法来证明
当2^(n-1)边长的黑白间隔的方阵 满足从任意黑格出发 可以遍历整个方阵到达任意白格 这个条件
就可以把这个问题转化为 以下3种情况
1. 起点和终点在相临的象限里
2. 起点和终点在同一个象限里
3. 起点和终点在对角的象限里
自己考虑一下 就会发现非常的简单
举例：
对于n=2的情况
# 0 # 0
0 # 0 #
# 0 # 0
0 # 0 #
不妨假设 起点的#在00或者11位置 也就是第2象限
对于1. 起点和终点在相临的象限里 比如终点在第1象限 可以按象限逆时针遍历
对于2. 起点和终点在同一个象限里 终点在第2象限
起点出发以后 在第一象限内可以到终点的遍历过程中 一定会经过整个方阵正中心的四个点之一（2，2）
在经过这些点的时候 可以依次遍历其它象限 然后回到第一象限。
对于3. 起点和终点在对角的象限里 终点在第4象限 可以认为是在遍历第1象限的过程中 路过相邻象限时 去遍历一下再回来
把第1象限的终点设置到另一个相邻的象限的边上 。大体上说 遍历的顺序就是 2->3->2->1->4
------解决方案--------------------
那么讨论caozl提出的三种情况，他已经给出了证明，我这里是我的方案，大家参考，以下中，所有通过路径上的象限时都是对象限的完整遍历：
1.起点和终点在相邻的象限，如起点在2象限，终点在1或3象限，这是最简单的，只需按照2->3->4->1或2->1->4->3依次进行大象限的完整遍历即可，同caozl的证明；
如图，有一8*8的方格，要求从任一点出发，到达不同色的另一个随机格。
要求：1.必须经过所有的64格；
2.每个方格只能经过一次。
------解决方案--------------------
骑士周游问题。
------解决方案--------------------
大概想了一下 有一个思路 探讨一下
大体上就是证明 2^n边长的黑白间隔的方阵 从任意黑格出发 可以遍历整个方阵到达任意白格
对于n=1的情况 非常好证明
# 0
0 #
从任何一个#都可以到任何一个0
我把这四个位置分别叫做4个象限
2 1
3 4
对于n=2的情况
# 0 # 0
0 # 0 #
# 0 # 0
0 # 0 #
如果把这个4*4的方阵看成是一个大号的2*2 方阵 每个元素又是一个2*2方阵
不妨假设起点的#在第2象限里 那么当终点的位置在第1或第3象限的时候 就和n=1的情况一样了
也很容易找到终点位置也在第2象限或第4象限的解法。
也就是说 对于一个2^n边长的黑白间隔的方阵 用数学归纳法来证明
当2^(n-1)边长的黑白间隔的方阵 满足从任意黑格出发 可以遍历整个方阵到达任意白格 这个条件
就可以把这个问题转化为 以下3种情况
1. 起点和终点在相临的象限里
2. 起点和终点在同一个象限里
3. 起点和终点在对角的象限里
自己考虑一下 就会发现非常的简单
举例：
对于n=2的情况
# 0 # 0
0 # 0 #
# 0 # 0
0 # 0 #
不妨假设 起点的#在00或者11位置 也就是第2象限
对于1. 起点和终点在相临的象限里 比如终点在第1象限 可以按象限逆时针遍历
对于2. 起点和终点在同一个象限里 终点在第2象限
起点出发以后 在第一象限内可以到终点的遍历过程中 一定会经过整个方阵正中心的四个点之一（2，2）
在经过这些点的时候 可以依次遍历其它象限 然后回到第一象限。
对于3. 起点和终点在对角的象限里 终点在第4象限 可以认为是在遍历第1象限的过程中 路过相邻象限时 去遍历一下再回来
把第1象限的终点设置到另一个相邻的象限的边上 。大体上说 遍历的顺序就是 2->3->2->1->4
------解决方案--------------------
那么讨论caozl提出的三种情况，他已经给出了证明，我这里是我的方案，大家参考，以下中，所有通过路径上的象限时都是对象限的完整遍历：
1.起点和终点在相邻的象限，如起点在2象限，终点在1或3象限，这是最简单的，只需按照2->3->4->1或2->1->4->3依次进行大象限的完整遍历即可，同caozl的证明；