33,008
社区成员
发帖
与我相关
我的任务
分享难道无解？
路径问题，如下所示：
1 2 3 4 5
6 7 8 9 10
11 12 13 15 14
16 17 18 19 NULL
只有一个NULL格，每次只能移动一个格，要求交换14，15使得按照顺序排列。
PS：是不是所有情况都会有一种移动路径，不会存在无解的情况？
1 2 3 4 5
6 7 8 9 10
11 12 13 15 14
16 17 18 19 NULL
只有一个NULL格，每次只能移动一个格，要求交换14，15使得按照顺序排列。
PS：是不是所有情况都会有一种移动路径，不会存在无解的情况？
...全文
请发表友善的回复…
发表回复
linren 2009-08-19
- 打赏
- 举报
[Quote=引用 5 楼 linren 的回复:]
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
[/Quote]
证明上述观点
只要证明√2是无限不循环小数就可以了……
【反证法】
假设√2 是m/n（m，n互质）
m=√2×n
m^2=2n^2
于是m是偶数
同理n也应是偶数
互相矛盾（m，n互质）
即√2不是无限不循环小数
所以无限不循环小数……
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
[/Quote]
证明上述观点
只要证明√2是无限不循环小数就可以了……
【反证法】
假设√2 是m/n（m，n互质）
m=√2×n
m^2=2n^2
于是m是偶数
同理n也应是偶数
互相矛盾（m，n互质）
即√2不是无限不循环小数
所以无限不循环小数……
ToBeTough 2009-08-19
- 打赏
- 举报
有趣 ！
linren 2009-08-19
- 打赏
- 举报
[Quote=引用 4 楼 newjerryj 的回复:]
引用 2 楼 linren 的回复:
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
感谢！
请教大侠，以上两句为什么？为什么对角线无法逾越？
[/Quote]
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
引用 2 楼 linren 的回复:
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
感谢！
请教大侠，以上两句为什么？为什么对角线无法逾越？
[/Quote]
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
NewJerryj 2009-08-19
- 打赏
- 举报
[Quote=引用 2 楼 linren 的回复:]
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
[/Quote]
感谢！
请教大侠，以上两句为什么？为什么对角线无法逾越？
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
[/Quote]
感谢！
请教大侠，以上两句为什么？为什么对角线无法逾越？
绿色夹克衫 2009-08-19
- 打赏
- 举报
存在无解的情况，可以利用交换次数的奇偶性或逆序数来判断，LZ可以看看这个帖子。
http://topic.csdn.net/u/20080926/23/301801ca-2fe0-4d24-84e3-fbd454be4604.html
http://topic.csdn.net/u/20080926/23/301801ca-2fe0-4d24-84e3-fbd454be4604.html
linren 2009-08-19
- 打赏
- 举报
恩
的确是无解的
这种移位的拼图有通用的解法
如果最后仅剩下2个没有到达正确位置且2个位置相邻（左右相邻或上下相邻）
那么这个拼图就是无解的……
上面的图中说明了1点
要想把14和15的顺序调换过来
起码需要用上、下、左、右的移动来达到与走对角线等价的效果……
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
的确是无解的
这种移位的拼图有通用的解法
如果最后仅剩下2个没有到达正确位置且2个位置相邻（左右相邻或上下相邻）
那么这个拼图就是无解的……
初始状态：
1 2 3 4 5
6 7 8 9 10
11 12 13 15 14
16 17 18 19 NULL
为了把两个数进行交换，我们可以让15向对角线的方向移动（当然这是不允许的）
1 2 3 4 5
6 7 8 9 10
11 12 13 NULL 14
16 17 18 19 15
然后……
1 2 3 4 5
6 7 8 9 10
11 12 13 14 NULL
16 17 18 19 15
成功排好顺序……
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 NULL
上面的图中说明了1点
要想把14和15的顺序调换过来
起码需要用上、下、左、右的移动来达到与走对角线等价的效果……
然而无论怎样上、下、左、右移动都无法做到这点……
对角线那边的世界和这边的世界是无法逾越的……
NewJerryj 2009-08-19
- 打赏
- 举报
显示有点错位，都不好调整，是5*4的格盘
NewJerryj 2009-08-19
- 打赏
- 举报
[Quote=引用 7 楼 linren 的回复:]
引用 5 楼 linren 的回复:
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
证明上述观点
只要证明√2是无限不循环小数就可以了……
【反证法】
假设√2 是m/n（m，n互质）
m=√2×n
m^2=2n^2
于是m是偶数
同理n也应是偶数
互相矛盾（m，n互质）
即√2不是无限不循环小数
所以无限不循环小数……
[/Quote]
明白了！感谢大侠耐心讲解！等会给你分！
引用 5 楼 linren 的回复:
上下左右移动的步长为1
走对角线的步长为√2
m*1=n*√2
不存在m和n的整数解……
证明上述观点
只要证明√2是无限不循环小数就可以了……
【反证法】
假设√2 是m/n（m，n互质）
m=√2×n
m^2=2n^2
于是m是偶数
同理n也应是偶数
互相矛盾（m，n互质）
即√2不是无限不循环小数
所以无限不循环小数……
[/Quote]
明白了！感谢大侠耐心讲解！等会给你分！
