魔方吧·中文魔方俱乐部

标题: 顺排序变成逆排序的问题（段位制的编辑） [打印本页]

作者: 大烟头 时间: 2008-2-22 23:00:49 标题: 顺排序变成逆排序的问题（段位制的编辑）

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

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

作者: 大头 时间: 2008-2-23 02:12:25

段位是8次么？级位是2次么

作者: 明华 时间: 2008-2-23 03:35:55

          N 张牌由原先的从小到大的排序变成从大到小的排序，最多 N - 1 次。呵呵！           烟头兄弟如果想找“理论大师”无聊争斗，请把该主题移到“理论篇”好了！那时本人还是 “免开尊口”的为好呀！免得被那里的“搅扰大师” 改帖、屏蔽弄得烟头看不下去........ 呵呵！                 烟头兄弟如果真要研究理论，不妨先研究一下“<A href="http://bbs.mf8-china.com/viewthread.php?tid=5798&extra=&page=2">0123 魔方的正六面体循环变换球面网</A>”， 谈一下感受！那里才是烟头 “有所事事”的好去处，呵呵！

作者: peiqi 时间: 2008-2-23 09:32:39

原帖由 明华 于 2008-2-23 03:35 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=87429&ptid=6150" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
    最多 N - 1 次。呵呵！

可是烟头兄问的是最少啊？

作者: 大烟头 时间: 2008-2-23 12:00:59

举个简单的5张牌例子： 这是1到5从小到大排列： 1 2 3 4 5 第一次操作把1和2两张抽出插入4与5的中间，成： 3 4 1 2 5 第二次操作把4和1两张抽出插入5的后面，成： 3 2 5 4 1 第三次操作把5和4两张抽出插入3的前面，成： 5 4 3 2 1 完成倒序，只抽插三次。5张牌很容易的，13张牌倒序想找出最少次数是非常难的，而这个段位制的编辑又不完全是倒序就更难了，各位无聊时候可以试试。 明华兄看错命题，但这个题说最多是N-1次也是不对的，随便乱插都没完成，那是不是可以说最多是无限次，所以这题目不能研究最多，只能研究最少步了。魔方最少步研究是太难了，看下这插牌的最少步有没有人能破解出来。

作者: 大烟头 时间: 2008-2-23 20:16:15

原帖由 大头 于 2008-2-23 02:12 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=87426&ptid=6150" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 段位是8次么？级位是2次么

----------------
----业余分三个级 业余初级：50.01-60秒 业余中级：40.01-50秒 业余高级：30.01-40秒 ----专业分九个段 专业初段：26.01-30秒 专业二段：23.01-26秒 专业三段：20.01-23秒 专业四段：18.01-20秒 专业五段：16.01-18秒 专业六段：14.01-16秒 专业七段：13.01-14秒 专业八段：12.01-13秒 专业九段：00.00-12秒 ---------------------------
可以把这个当成初始状态的14张牌。想找出最少步很难。

作者: 明华 时间: 2008-2-26 08:46:04

        “ N 张牌由原先的从小到大的排序变成从大到小的排序，最多 N - 1 次。”是没错的！             考虑再三，还是向大家再介绍一下数学术语，免得大家再出错！因为烟头兄弟以及 多数魔友毕竟不是学数学的，对数学中“最多”的含义理解错误是很正常的！         详细解释请大家参考： <A href="http://bbs.mf8-china.com/viewthread.php?tid=3866">[转帖]美专家证明任意状态魔方“最多”只需26步解开</A>        <A href="http://bbs.mf8-china.com/viewthread.php?tid=3866">http://bbs.mf8-china.com/viewthread.php?tid=3866</A>         在那里乌木先生也曾经犯过同样的错误认识！所以我在这里再澄清一下为好！            “ N 张牌由原先的从小到大的排序变成从大到小的排序，最多 N - 1 次。”是没错的！

作者: Pakhang 时间: 2008-2-26 13:19:33

改了下顺序确实好看多了..
如果是我的话我懒得复制粘贴,直接重打哈哈

作者: haohmaru 时间: 2008-4-30 00:57:35

先抛个砖:11步完成
初始:1 2 3 4 5 6 7 8 9 10 J Q K
1 2入Q K
3 4 5 6 7 8 9 10 J Q 1 2 K
Q 1 最后 3 4 5 6 7 8 9 10 J 2 K Q 1 J 2入Q 1
3 4 5 6 7 8 9 10 K Q J 2 1
3 4入9 10
5 6 7 8 9 3 4 10 K Q J 2 1 9 3入10 K
5 6 7 8 4 10 9 3 K Q J 2 1 10 9入8 4
5 6 7 8 10 9 4 3 K Q J 2 1 10 9 4 3入J 2
5 6 7 8 K Q J 10 9 4 3 2 1
5 6 入7 8
7 5 6 8 K Q J 10 9 4 3 2 1 8入7 5
7 8 5 6 K Q J 10 9 4 3 2 1 8 5入9 4
7 6 K Q J 10 8 5 9 4 3 2 1 7 6入8 5
K Q J 10 9 8 7 6 5 4 3 2 1
 
完全按照5张牌的方法逐步完成
下面的继续...

作者: haohmaru 时间: 2008-4-30 01:08:50

先完成12345 然后完成678910
最后完成ABJQK(其中A=54321,B=109876)
 
初始:
1 2 3 4 5 6 7 8 9 10 J Q K
1 2放入4 5
3 4 1 2 5 6 7 8 9 10 J Q K 4 1放入5 6
3 2 5 4 1 6 7 8 9 10 J Q K 5 4放到最前
5 4 3 2 1 6 7 8 9 10 J Q K
6 7放入9 10
5 4 3 2 1 8 9 6 7 10 J Q K 9 6放入10 J
5 4 3 2 1 8 7 10 9 6 J Q K 10 9放入1 8
5 4 3 2 1 10 9 8 7 6 J Q K
5 4 3 2 1 10 9 8 7 6放入Q K
J Q 5 4 3 2 1 10 9 8 7 6 K Q 5 4 3 2 1放到最后
J 10 9 8 7 6 K Q 5 4 3 2 1 K Q放到最前
K Q J 10 9 8 7 6 5 4 3 2 1
 
一共九步!!
继续研究...

[ 本帖最后由 haohmaru 于 2008-4-30 01:11 编辑 ]

作者: 大烟头 时间: 2008-4-30 01:28:05

期待有人破楼上这9步纪录，我会加分鼓励

作者: 大头 时间: 2008-4-30 09:33:37

随便说了一句，一不小心还占了个沙发

作者: Cielo 时间: 2008-5-9 00:58:19

因为12345可以3步变成54321，所以如果增加加4个数，只需要增加3步（因为1234A可以3步变为A4321）。那么13 = 5 + 4 x 2，所以 3 + 3 x 2 = 9 步可以完全把顺序倒过来。 我猜更少步是不可能了，但还不会证明<img smilieid="10" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border="0">

作者: 金眼睛 时间: 2008-6-6 12:06:21

推导出一个规律，对于1到N的序列，通过一次改变顺序的操作可以得到的情况数为：
 
1*(N-1)+2*(N-2)+ ... +(N-2)*2+(N-1)*1    (注：能再整理一下这个式子的朋友，请告知结果。)
 
              N=2    N=3    N=4    N=5    N=6    N=7    N=8    N=9    N=10    N=11    N=12    N=13
情况数    1        4        10      20       35      56      84      120    165       220      286      364
 
这些情况之间可以进行复合操作
比如6：34125和15：14523是12345的第六种和第十五种情况，那么如果进行复合
 
6-15-6：12345->34125(位置改变情况34125)->32541(位置改变情况14523)->54321(位置改变情况34125)
 
15-6-15：12345->14523(位置改变情况14523)->52143(位置改变情况34125)->54321(位置改变情况14523)
 
当N=6时，需要4步，但是4步能完成的情况数就很多了，可见最佳结果很可能不唯一。
 
当N=13时，如果运行7步，都需要364^7次运算，呵呵，时间有限，还是做一点理论上的铺垫吧，希望起到抛砖引玉的作用，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">

作者: Cielo 时间: 2008-6-6 12:49:45

尽管还不太明白楼上的意思，但里面那个式子还是会算的 1*(N-1)+2*(N-2)+ ... +(N-2)*2+(N-1)*1 =1xN-1^2 + 2xN-2^2 + … + (N-2)xN-(N-2)^2 + (N-1)xN-(N-1)^2 =(1+2+…+(N-2)+(N-1))xN - (1^2+2^2+…+(N-2)^2+(N-1)^2) 这个楼上肯定会算<img smilieid="12" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border="0"> 

[ 本帖最后由 Cielo 于 2008-6-6 12:52 编辑 ]

作者: 金眼睛 时间: 2008-6-6 16:09:12

<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> ，LS算得不错，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> ，按你的思路我又往下整理了一下，最后得到N(N+1)(N-1)/6或者(N^3-N)/6。
 
可能我说得还不是很清楚，看下面的例子。
 
  位置：   1    2    3     经过一次变换，可能会出现(3^3-3)/6=4种情况：
 
情况1：   2    1    3    情况2：   2    3    1    情况3：   3    1    2    情况4：   1    3    2
 
数列a b c经过三步，比如情况1-情况2-情况4，变化情况如下：a b c->b a c(情况1)-> a c b(情况2)->a b c(情况4) 
 
所以X步，就是在初始情况上进行X次复合操作。
 
顺便说一句，LZ提出的问题很好，可是剪切粘贴太麻烦，弄进文本文件a=textread('?.txt','%s');a=flipud(a);搞定！嘿嘿！
 

[ 本帖最后由金眼睛于 2008-9-3 16:21 编辑 ]

作者: Cielo 时间: 2008-6-6 16:44:02

哦我知道楼上的意思了，就是说编程从所有可能的情况里面找出结果对吧？ 呵呵估计要算出来还得花一些时间的吧<img smilieid="1" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border="0">

作者: 金眼睛 时间: 2008-6-6 22:02:22

原帖由 Cielo 于 2008-6-6 16:44 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=149843&ptid=6150" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 哦我知道楼上的意思了，就是说编程从所有可能的情况里面找出结果对吧？呵呵估计要算出来还得花一些时间的吧

呵呵，实际是我的电脑根本算不了，太慢了，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">
 
有待于发现另外的规律，以便在过程中加入一些限制条件。
 
我现在编了一个子程序可以将如5，(7，6)，1，(3，2)，4变成4，5，1，2，3，也就是已经成逆序的就不变了，连续三个的也可以判断，比如2，(7，6，5)，1，(4，3)变成2，4，1，3，只是还不知道怎么用，期待新规律的发现啊！呵呵！

作者: ares_g 时间: 2008-9-3 14:48:43

<UL>
<LI>达到8步不是很难，7个数可以用4步完成，13个数则如下：为了方便看，我把大段重复的数列用“-”或“+”代替 </LI>
<LI>0：1、2、3、4、5、6、7、8、9、10、J、Q、K </LI>
<LI>1：3、4、5、1、2、6、7+ </LI>
<LI>2：3、2、6、7+、4、5、1 </LI>
<LI>3：7+、4、3、2、6、5、1 </LI>
<LI>4：7、8、9、10、J、Q、K、6、5、4、3、2、1</LI>
<LI> 5：9、10、J、7、8、Q、K、6- </LI>
<LI>6：9、8、Q、K、10、J、7、6- </LI>
<LI>7：K、10、9、8、Q、J、7- </LI>
<LI>8：K、Q、J、10、9、8、7、6、5、4、3、2、1 </LI>
<LI>我想，每次移动数列后要保证左右都可移动，所以每次移动3个数比2个的效率要更高。</LI>
<LI>恩。</LI>
<LI>老大，提个要求，我想要能贴头像，行么？</LI></UL>

[ 本帖最后由 ares_g 于 2008-9-3 20:12 编辑 ]

作者: ares_g 时间: 2008-9-3 15:04:50

日的，大家是怎么换行的？我用回车怎就不灵呢？

0：1、2、3、4、5、6、7、8、9、10、J、Q、K

1：3、4、5、1、2、6、7+

作者: ares_g 时间: 2008-9-3 17:13:01

顺便补充一下：
1个数0步；
2个数1步；
3个书2步；
4个数3步；
5个数3步；
6个数4步；
7个数4步；
8个数5步。
 
不知道有没有更少的。
 
13个数时还没有试过每次移动4个数的，也可能移动5个数效率更高（直觉奇数比偶数快），有待测试。
 
 

[ 本帖最后由大烟头于 2008-9-5 00:35 编辑 ]

作者: 大烟头 时间: 2008-9-5 00:39:46

楼上总结的很好，期待有人破13张倒序玩法的8步纪录

作者: 乌木 时间: 2008-9-5 01:31:28 标题: 回复 21# 的帖子

可在“编辑”时编排格式。

作者: ares_g 时间: 2008-9-6 08:35:39

有没有人能先证明6步是不可能的？

作者: noski 时间: 2008-9-9 22:15:45

在外面看这个贴子名字好久了，竟然一直以为是段位制，昨天才发现这是一道有趣的题。。
总结一下之前的：

金眼睛：
N=2 N=3 N=4 N=5 N=6 N=7 N=8 N=9 N=10 N=11 N=12 N=13
情况数 1 4 10 20 35 56 84 120 165 220 286 364

ares_g：
20楼8步的解法；
顺便补充一下：
1个数0步；
2个数1步；
3个书2步；
4个数3步；
5个数3步；
6个数4步；
7个数4步；
8个数5步。
-------------------------------------------------

我又继续往下算了一下：
1个数0步，0
2个数1步，1种解法；
3个数2步，4种解法；
4个数3步，40种解法；
5个数3步，2种解法；
6个数4步，112种解法；
7个数4步，8种解法；
8个数5步，720种解法；
9个数5步，10种解法；
10个数6步，？种解法；
11个数?步，？
12个数?步，？
13个数?步，？

9个数和10个数是刚刚算的，10个数6步的解法总数没算出来，但找到答案了，而且也证明10个数5步是解决不了的。
研究上述的规律发现：2N个数字需要的步数比2N-1个数字的步数多1；奇数个数字的解法都很少，偶数个数字的解法则多得多。
下面是我的推理：
1. 当数字个数为 2N+1 时，解法的数量虽少，但仍有递增的趋势；
2. 当数字为 2N 时，解法的数量很多，但也是递增的趋势；
3. 由此假设：2N+1 个数字的解法数量总比 2N 个数字的解法数少；
4. 2N 个数字的解法总数比 2N-1 的多很多，可以理解为：2N 个数任意取两个数绑在一块，用 2N-1 的解法来做，最后加一步交换两个绑在一起的；
5. 2N+1 个数字的最小步数如果比 2N 个数字的最小步数多 1，那么 2N+1 个数字的解法数必比 2N 个数的解法多很多；
6. 由5和3的假设矛盾，得出 2N+1 个数字的最小步数与 2N 个数字的最小步数相同；
7. 结论：11个数需要6步，12个数需要7步，13个数需要7步。。

贴一个9个数字的5步解法：
1 2 3 4 5 6 7 8 9
3 4 5 6 1 2 7 8 9
3 2 7 8 9 4 5 6 1
9 4 3 2 7 8 5 6 1
9 8 5 4 3 2 7 6 1
9 8 7 6 5 4 3 2 1
而10个数字的6步解法把1和2绑在一起用这个方法就行了。

[ 本帖最后由 noski 于 2009-5-29 14:57 编辑 ]

作者: noski 时间: 2008-9-9 23:54:07

事实证明，我的推断是正确的。

9个数字的5步方法：
1 2 3 4 5 6 7 8 9
3 4 5 6 1 2 7 8 9
3 2 7 8 9 4 5 6 1
9 4 3 2 7 8 5 6 1
9 8 5 4 3 2 7 6 1
9 8 7 6 5 4 3 2 1

11个数字的6步方法：
1 2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 1 2 8 9 10 11
3 2 8 9 10 11 4 5 6 7 1
11 4 3 2 8 9 10 5 6 7 1
11 10 5 4 3 2 8 9 6 7 1
11 10 9 6 5 4 3 2 8 7 1
11 10 9 8 7 6 5 4 3 2 1

13个数字的7步方法：
1 2 3 4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 1 2 9 10 11 12 13
3 2 9 10 11 12 13 4 5 6 7 8 1
13 4 3 2 9 10 11 12 5 6 7 8 1
13 12 5 4 3 2 9 10 11 6 7 8 1
13 12 11 6 5 4 3 2 9 10 7 8 1
13 12 11 10 7 6 5 4 3 2 9 8 1
13 12 11 10 9 8 7 6 5 4 3 2 1

果然暴力穷举不靠谱，画来画去还是在纸上找到了规律，哈哈，你看出来了吗？

1. 先把1和2移到后面数字的中间（由于除了1、2剩奇数个数字，所以前一半要比后一半多一个，中间插入1、2）。

2. 接着把2和以后的部分移到3之后。

3. 好了，一对一对的往前挪直到全部解决。

因此，所有2N-1个数字从正序到逆序的最小步数都是N。

[ 本帖最后由 noski 于 2009-5-29 15:02 编辑 ]

作者: 大烟头 时间: 2008-9-10 00:29:48

9个数字的5步方法：
 
(1  2)  3  4  5  6/  7  8  9         3  (4  5  6  1)  2  7  8  9/         /3  2  7  8  (9  4)  5  6  1          9/  4  3  2  7  (8  5)  6  1          9  8/  5  4  3  2  (7  6)  1          9  8  7  6  5  4  3  2  1
 
11个数字的6步方法：
 
(1  2)  3  4  5  6  7/  8  9  10 11
 
3  (4  5  6  7  1)  2  8  9  10 11/
 
/3  2  8  9  10 (11 4)  5  6  7  1
 
11/ 4  3  2  8  9  (10 5)  6  7  1
 
11 10/ 5  4  3  2  8  (9  6)  7  1
 
11 10 9/  6  5  4  3  2  (8  7)  1
 
11 10 9  8  7  6  5  4  3  2  1      
 
13个数字的7步方法：
 
(1  2)  3  4  5  6  7  8/  9  10 11 12 13 3  (4  5  6  7  8  1)  2  9  10 11 12 13/ /3  2  9  10 11 12 (13 4)  5  6  7  8  1 13/ 4  3  2  9  10 11 (12 5)  6  7  8  1 13 12/ 5  4  3  2  9  10 (11 6)  7  8  1 13 12 11/ 6  5  4  3  2  9  (10 7)  8  1 13 12 11 10/ 7  6  5  4  3  2  (9  8)  1 13 12 11 10 9  8  7  6  5  4  3  2  1
 
-------------------------------------------
用（）内表示要移动的数字组，/表示插入的地方，仔细研究下，真的挺有规律的。
 
 
 
 
 

[ 本帖最后由大烟头于 2008-9-10 00:43 编辑 ]

作者: ares_g 时间: 2008-9-10 09:47:21

<

>有2N+1个数时，每次移动N个，要N+1步。是这意思么？我说noski这几天你怎么没动静了，原来在good shoes呢

[ 本帖最后由 ares_g 于 2008-9-10 09:52 编辑 ]

作者: noski 时间: 2008-9-10 13:14:35 标题: 回复 29# 的帖子

2N+1个数字，按上面的规律，N+1步必能完成。
但这个解法不是每次移动N个，只有第二步是移动N个，其它步都是移动2个。
我不能完全肯定这就是最小步，但这个方法的效率还挺高的，一次正好排好两个。
＝＝＝＝＝
嗯嗯，莫非俺神经，认为Good Shoes＝鼓捣数字。。

[ 本帖最后由 noski 于 2009-5-29 15:05 编辑 ]

作者: ares_g 时间: 2008-9-10 15:04:49

鼓捣数字都被你发现了，哈哈。真的是每次都移动N个，你自己看看啊，如果说2个就不好确定规律了

看看大烟头“/”和“（）”的距离，对吧？

作者: noski 时间: 2008-9-10 15:51:54 标题: 回复 31# 的帖子

对，的确可以看成是N个，那么这样编程会容易一点吧。不知各种程序语言函数库中的逆序函数，有没有这个效率高。 
不过，数字过大时会让人感觉不够好。比如我有201个数字，那么N＝100。你的说法是每次都挪100个数字，挪101次；而我的说法是只有一次需要挪100个数字，其余100次只要每次挪两个数字。当然两个实质是一回事。要是用链表的话，就打断再接上就行了。。

作者: 金眼睛 时间: 2008-9-10 21:47:54

哈哈，noski对数字还真是敏感，强，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> 
 
虽然也编了程序，但没想到这其中会有规律，所以只运行到6，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> ，其实利用指针，程序不大，就是比较耗时。
 
我把noski的规律再补充一下吧，别告我侵权啊，呵呵！！
 
我觉得第一步移动1，2规律性不强，对于13，应该进行如下操作(借用大烟头的符号)：
 
0：1，（2，3，4，5，6，7），8，9，10，11，12，13 /
1：/1，8，9，10，11，12，（13 ，2），3，4，5，6，7
2：13  /   2，1，8，9，10，11，（12，3），4，5，6，7
3：13，12  /  3， 2，1，8，9，10，（11，4），5，6，7
4：13，12，11  /  4，3， 2，1，8，9，（10，5），6，7
5：13，12，11，10  /  5，4，3， 2，1，8，（9，6），7
6：13，12，11，10，9  /  6，5，4，3， 2，1，（8，7）
7：13，12，11，10，9，8，7，6，5，4，3， 2，1
 
对于12，第一步为：（1，2，3，4，5，6），7，8，9，10，11，12 /
 
这样可以很明显的看出：
对于N（奇数）步数为：(N-1)/2+1=(N+1)/2
对于N（偶数）步数为：N/2+1
 

[ 本帖最后由金眼睛于 2008-9-10 21:56 编辑 ]

作者: noski 时间: 2008-9-10 23:19:57 标题: 回复 33# 的帖子

赞！这样一来规律性就更强了，一下子就能看出来移动的目的。 
先前后颠倒，再两个两个解决。你17楼说的函数flipud()的算法，不知有没有这个高效

作者: ares_g 时间: 2008-9-11 10:45:52

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

作者: ggglgq 时间: 2008-9-11 11:37:19

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

作者: ares_g 时间: 2008-9-11 12:22:59

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

作者: noski 时间: 2008-9-11 18:54:54 标题: 回复 37# 的帖子

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

作者: 金眼睛 时间: 2008-9-11 19:22:03

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

作者: Cielo 时间: 2008-9-12 10:45:04

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

作者: 大烟头 时间: 2008-9-12 14:35:10

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

作者: ares_g 时间: 2008-9-12 18:16:40

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

作者: superacid 时间: 2009-5-30 17:44:55

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)