[求助][算法]巧移黑白子问题！

爱你爱到西元

开始时，把n个黑子与n个白子排成一行：**..*OO..O（*：黑 O白）
经过n次移动，2n个子交错排列 ：*O*O*O*O*O..或者O*O*O*O*O*..


移动规则：
1. 每次只能将相邻的（中间有空格的两粒棋子视为不相邻）两粒棋子同时移动到与某
棋子相邻的同一行的空位处，在移动过程中不许交换被移动的两粒棋子的左右顺序。
2. 与这一行棋子的内部空格相邻的任何棋子不许移动。
3. 在每一次移动结束后，这一行棋子的内部最多允许出现两个空格，且两个空格必
须连续。
4. 最左边的两粒棋子不许向左移动，最右边的两粒棋子不许向右移动。
注意，第n次移动结束后，连续排列的2 n粒黑白相间的棋子内部不能有空格。
下面是n =3时，移动棋子的演示过程：

开始： ***OOO
t1 ： *OOO**
t2 ： *OO *O*
t3 ： O*O*O*

求助：n = 4的移动过程，还有n为任意正整数时的方法。

爱我后悔

0000****
00****00
00***0* 0
0 **0*0*0
*0*0*0*0

红星

其他的不会了 嘿嘿

████

****0000
*** 000*0
***000 *0 回到3的情况 递归

*****00000
**** 0000*0
****0000 *0回到4的情况 递归

.｀D.D`地`

2楼似乎没明白移动规则。

楼上的,我在想想，直接按你的来好象还是有个问题，不过是种思考的途径。

小嘛怪

当然，你真正写程序的时候还是不用递归的好，这个程序我初中的时候写过，
开始用递归，效率不高。后来就按那种方法直接一步一步的循环移动做的

不过现在处理器快，内存大，应该也没什么了。。

最ヅ后愛上你

继续顶

jane

以下是引用maoguoqing在2007-8-7 13:29:15的发言：

当然，你真正写程序的时候还是不用递归的好，这个程序我初中的时候写过，
开始用递归，效率不高。后来就按那种方法直接一步一步的循环移动做的

不过现在处理器快，内存大，应该也没什么了。。
佩服！

絕版kun騙孖

*** 000*0如何变化到
***000 *0
虚心求教斑竹！

tilord

数学归纳法证明：
1）找出这个游戏的五个特解：
n=3，4，5，6，7，
把棋子位置编号，移动方式用数字表示
例如黑白棋子各三个，排成一行如下图：
○○○●●●
一步；＃＃○●●●○○
二步：＃＃○●●＃＃○●○
三步：＃＃＃＃●○●○●○
表示为：1 2→7 8;6 7→9 10;3 4→6 7
n=4：2 3→9 10；5 6→2 3；8 9→5 6；1 2→8 9
n=5：2 3→11 12；8 9→2 3；5 6→8 9；10 11→5 6；1 2→10 11
n=6：2 3→13 14；8 9→2 3；4 5→8 9；9 10→4 5；12 13→9 10；1 2→12 13
n=7：2 3→15 16；11 12→2 3；5 6→11 12；10 11→5 6；7 8→10 11；14 15→7 8；1 2→14 15

2）设n=k时，有解，
证明n=k+4，时有解，
原式 ○○○○，○○○○○○○●●●●●●●，●●●●
一步:○ # #○，○○○○○○○●●●●●●●，●●●●○○
二步:○●●○，○○○○○○○●●●●●●●， # #●●○○

中间k步，将中间部分变换成：●○●○●○●○●○●○

n-1步:○●●○，●○●○●○●○●○●○， ●# #○
n步: ●○●○●○●○●○●○●○●○●○●○●○
证毕！
证明方法借鉴于新浪爱问知识人的好友 姑苏寒士
特例是自己找到的