2116: 【2018冬令营栈及递归】棋子（chess）

有2n个棋子（n≥4）排成一行，开始时白子全部在左边，黑子全部在右边，如下图为n=5的情况：
○○○○○●●●●●
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：
○●○●○●○●○●
任务：编程打印出移动过程。

一个整数n(n<=50)

输出移动步骤，每一个步骤占一行。

4

4,5-->9,10
8,9-->4,5
2,3-->8,9
7,8-->2,3
1,2-->7,8

【提示】
以n=4为例:
初 始：○○○○●●●●——{—表示空位}
第1步：○○○——●●●○●  
第2步：○○○●○●●——●
第3步：○——●○●●○○●
第4步：○●○●○●——○●
第5步：——○●○●○●○●

如果n=5呢？
我们继续尝试，希望看出一些规律
初 始：○○○○○●●●●●——
第1步：○○○○——●●●●○●
第2步：○○○○●●●●——○●
这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把它缩小为规模为n-1的相同类型子问题。