注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

尛乐

心独往之,情独钟之,力独施之,行必补之,努力实现自己的人生价值。

 
 
 

日志

 
 

【转载】移格子游戏  

2015-01-14 09:50:07|  分类: 有趣的数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这个游戏是,如何把左边混乱排列的8个小方格,通过上下左右移动,变成右边从小到大顺序排列结构。

【转载】移格子游戏 - 贾乐梅 - 尛乐

上图右边图形中八个小方格,按照第一行从左到右,接着第二行从左到右,再到第三行从左到右这个顺序排列,那么,这种排列是没有逆序的。所谓逆序是指前面的数字比后面的大,逆序数是指一串数中逆序的个数。比如,“21”的逆序数是1;“321”的逆序数是3,因为3比2大,3比1大,2比1大。“5392”的逆序数是“4”,因为5比3大,5比2大,3比2大,9比2大。


下面我们关注逆序数的奇偶性。并且研究一下一个格子左右、上下移动会对逆序数及逆序数的奇偶性产生什么影响。

【转载】移格子游戏 - 贾乐梅 - 尛乐

上图的逆序数是0,是偶数。我们把“8”左右移动,是不影响总数列“12345678”的逆序数的。而一个数上下移动,则逆序数会发生变化,但奇偶性不变。为什么,我们不妨实验一下。上图中,把6向下移动,这相当于把6从7和8之前移到了7和8之后,于是产生两个逆序“76”和“86”,逆序数从0变为2,奇偶性不变。而6,7,8这三个数都仍然在1,2,3,4,5之后,所以,总逆序数就是2。我们再来看一下下面的这个情况:

【转载】移格子游戏 - 贾乐梅 - 尛乐

我们打算把5向下移动,也就是把5从8和4之前移到到它们之后,那么,原来54这个逆序消失,但产生了一个新的逆序85,所以,逆序数不变,即奇偶性不变。还有一种情形,如下图所示:

【转载】移格子游戏 - 贾乐梅 - 尛乐

把5向下移,因为5后面的两个数3和4都比5小,有两个逆序53和54,向下移后,这两个逆序都消失,但奇偶性仍然不变。


以上几种情况都考虑到了。所以,可以下结论:


只要逆序数是偶数,那么,我们就可以把混乱排列的结构,通过上下左右移动的办法,变换到最终从小到大顺序排列的结构。而如果逆序数是奇数,那么肯定不能做到。


回到开始时所给的那个混乱结构。我们需要数一数它的逆序数,也就是下图的逆序数:

【转载】移格子游戏 - 贾乐梅 - 尛乐

6后面有5,2,4,1,3比它小,逆序数是5;5后面有2,4,1,3比它小,逆序数是4;2后面只有1比它小,逆序数是1;4后面有1,3比它小,逆序数是2;7后面有1,3比它小,逆序数是2;8后面有1,3比它小,逆序数是2。把这些逆序数加起来,5+4+1+2+2+2=16,是偶数,所以,我们是能够做到把上图移动到标准的从小到大的顺序结构。


好了,你可以在PPT中画出格子,用鼠标拖动方格,试一试。

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017