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

ares_g

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

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

大烟头

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

乌木

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

ares_g

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

noski

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

金眼睛：
          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

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

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 编辑 ]

大烟头

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

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

ares_g

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

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

noski

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

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

ares_g

鼓捣数字都被你发现了，哈哈。真的是每次都移动N个，你自己看看啊，如果说2个就不好确定规律了 看看大烟头“/”和“（）”的距离，对吧？