Table of Contents
题目
分析
基本情况（\(n=4\)）
既然题目规定2n个棋子，而且\(n \ge 4\)，那么我们从\(n=4\)开始试做一下。
这个过程很简单，打印出来的话应该是这样的：
Step 1: oooo****--
Step 2: ooo--***o*
Step 3: ooo*o**--*
Step 4: o--*o**oo*
Step 5: o*o*o*--o*
Step 6: --o*o*o*o*我们看不出什么算法或者什么公式，那就可以作为一个基本情况、基本解法。
\(n=5, 6, ...\)
我们演示一下\(n=5\)时，进行的前面几步：
Step 1: ooooo*****--
Step 2: oooo--****o*
Step 3: oooo****--o* => 熟悉的模式(n=4)出现了
... ...可见，只要执行两步，黑白棋子的分布就可以简化为：\(n=4\)的排列+"--"+"o*"。
如果\(n=6\)，情况也是类似的：
Step 1: oooooo******--
Step 2: ooooo--*****o*
Step 3: ooooo*****--o* => 熟悉的模式(n=5)出现了
... ...所以我们可以找到规律了，对于n个白子和n个黑子来说：
- 将当中位置的一白一黑移动到最后；
- 将最后第3、第4个位置两个黑子移动到中间；
- 棋子排列成为\(n-1\)的排列+"--"+"o*"的形式。
- 递归处理前面的\(2\times(n-1)\)个棋子。
- 如果回到了基本情况（\(n=4\)），可以直接调用基本情况输出。
完整代码见答案。
在输出的时候，千万不要忘记每次n-1的时候，都会多出一个“尾巴”（"o*"），这也是要输出的。在本程序中，我们通过不断构造“尾巴”的方式来进行跟踪。
答案
