顺排序变成逆排序的问题（段位制的编辑）

大烟头

记得小时候有玩过这样一个智力游戏：<br><br>道具：拿出一付牌的其中一色，把A到K的13张牌按顺序排好。<br>游戏规则：一次可以抽出连续的几张牌，然后插入其他牌的中间。<br>问：最少要几次能让这13张牌从原先的从小到大的排序变成从大到小的排序？<br><br>这个智力游戏可能很多人都玩过，挺有意思的。（呵，13张牌是多了点，一般人是玩5张的，但咱们玩魔方的人是不怕难的，特别论坛里还有几位理论大师在看场，整天无所事事地在吵架，呵，玩笑）<br><br>今天我突然想起这个，是因为前几天讨论的段位制的时间定制是：<br><br><span style="font-weight: bold;">----业余分三个级</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">业余初级：50.01-60秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">业余中级：40.01-50秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">业余高级：30.01-40秒</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">----专业分九个段</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">专业初段：26.01-30秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业二段：23.01-26秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业三段：20.01-23秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业四段：18.01-20秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业五段：16.01-18秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业六段：14.01-16秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业七段：13.01-14秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业八段：12.01-13秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业九段：00.00-12秒</span><br><br>我觉得要编辑成这样更好看一点：<br><br><span style="font-weight: bold;">----专业分九个段</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">专业九段：00.00-12秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业八段：12.01-13秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业七段：13.01-14秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业六段：14.01-16秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业五段：16.01-18秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业四段：18.01-20秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业三段：20.01-23秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业二段：23.01-26秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">专业初段：26.01-30秒</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">----业余分三个级</span><br style="font-weight: bold;"><br style="font-weight: bold;"><span style="font-weight: bold;">业余高级：30.01-40秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">业余中级：40.01-50秒</span><br style="font-weight: bold;"><span style="font-weight: bold;">业余初级：50.01-60秒<br><br></span>编辑过程就是不断的剪切与粘贴，所以我就想到了插牌倒序的游戏了。<br><br>现在我在想啊：如果要完成这个编辑，最少要剪切与粘贴几次？<br><br><br><br><span style="font-weight: bold;"></span>

[ 本帖最后由 大烟头 于 2008-2-22 23:07 编辑 ]

superacid

这是我的一个数学竞赛训练题

ares_g

按照38楼noski兄所说“无序”问题，最“无序”的应该是“倒序”吧。就是说倒排是最远状态

大烟头

13个数字随机排列，那最远状态的最少步是几步呢？

Cielo

<P>哇太厉害了！能发现这样的规律<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border=0 smilieid="1"> </P>
<P>&nbsp;</P>
<P>想问一下，如何证明那就是最少步了呢？</P>

金眼睛

<P><STRONG>回复34#的帖子</STRONG></P>
<P><STRONG></STRONG>&nbsp;</P>
<P>呵呵，我也不太清楚flipud()具体的算法，我测试了一下，1万个数需要0.016秒，也说不定是一个一个往前提吧？呵呵！</P>
<P>&nbsp;</P>
<P><STRONG>回复35#的帖子</STRONG></P>
<P><STRONG></STRONG>&nbsp;</P>
<P>我要是二郎神就好了，肯定给你一个，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> </P>
<P>&nbsp;</P>
<P>对于随机序列，各种排序算法的算法复杂度不同。不过由于lucky case，同一个算法复杂度下，运行时间也不一样吧！</P>

noski

我这样想的：要是可以把数字的乱序度看成“熵”一样的话，比如设定一个数字其后面有几个比它大的，熵就加几。那么题中从正序到逆序，就是最乱的情况。所以N个随机打乱的数字排序的最少步数最多也就是33#那么多。

ares_g

如果是一个由互不相等的自然数随机排列的有限数列，那最多要几步完成排序呀？

ggglgq

&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 呵呵，数学高手们都云集到这里来了，看样子这个问题离解决的日子不遥远了！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17">&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;<BR>&nbsp;

ares_g

33楼有几只金眼睛，也分我一只吧