【题目描述】

有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。

如n=5时，成为：○●○●○●○●○●

任务：编程打印出移动过程。

【输入描述】

输入n。

【输出描述】

移动过程。

【样例输入】

7

【样例输出】

step 0:ooooooo*******--  step 1:oooooo--******o*  step 2:oooooo******--o*  step 3:ooooo--*****o*o*  step 4:ooooo*****--o*o*  step 5:oooo--****o*o*o*  step 6:oooo****--o*o*o*  step 7:ooo--***o*o*o*o*  step 8:ooo*o**--*o*o*o*  step 9:o--*o**oo*o*o*o*  step10:o*o*o*--o*o*o*o*  step11:--o*o*o*o*o*o*o*

【题目分析】

观察样例： 

乍一看没啥规律，但是如果你仔细观察，可能会发现，样例中的第三行，是这样的：

oooooo******--o*

可以看到，前面一部分形成了六白六黑两个空的情形。这不就是n=6的情况吗？

再往下两行（样例中的第五行）则是这样的：

ooooo*****--o*o*

没错，前面又形成了n=5的情况。

再往下两行呢？（样例中的第七行）：

oooo****--o*o*o*

前面又形成了n=4的情况。

而题目中的数据范围是4≤n≤100，也就是n最小取4。

那么我们就差不多明白了，这是一道分治，不断的分解情况，将n=k的情况转化为n=k?1的情况，一直到n=4。

那么这是怎么转化的呢？还是一样观察样例，我们看看是怎么从n=7的情况转化为n=6的情况的。

ooooooo*******--                ||     ||  oooooo--******o*        	||    ||  oooooo******--o*

看起来是把前边的中间的一黑一白移到最后的两个空位，然后再将原来排列的最后两颗星星补上前面的空位。（移动的部分已经用||标出。）

那么n=6或者n=5呢

oooooo******--o*       ||     ||  ooooo--*****o*o*       ||   ||  ooooo*****--o*o*

没错，还是这个套路。

转化的方法我们知道了，那么接下来再看$n=4$是怎么处理的吧。

oooo****--o*o*o*     	||   ||  ooo--***o*o*o*o*     	||  ||  ooo*o**--*o*o*o*   	 ||    ||  o--*o**oo*o*o*o*   	||   ||  o*o*o*--o*o*o*o*  	||    ||  --o*o*o*o*o*o*o*

这个看起来没什么规律，应该是$\mathrm{<span\; class="s267f6d"></span>}$$\mathrm{<span\; class="s267f6d">n</span>}<span\; class="s267f6d">=</span>\mathrm{<span\; class="s267f6d">4</span>}$的基本情况了。在代码中我们直接按照这种方法，照葫芦画瓢式移动就行。

【参考代码】

#include <iostream>  #include <cstdio>  using namespace std;  const int maxn = 105;  int n;  char s[maxn * 2 + 5];  int empty_idx;//empty_idx记录的是两个空位中的前面那个空位的下标。    void print() {//输出函数  	for(int i = 1; i <= 2 * n + 2; i++)  		cout << s[i];  	cout <<  endl;  	return ;  }    void init() {//初始化函数  	for(int i = 1; i <= n; i++)   		s[i] = 'o';  	for(int i = n + 1; i <= 2 * n; i++)   		s[i] = '*';  	for(int i = 2 * n + 1; i <= 2 * n + 2; i++)   		s[i] = '-';  	empty_idx = 2 * n + 1;  	print();//别忘了最初情况也需要输出  	return ;  }    void move(int x) {//移动函数  	s[empty_idx] = s[x];  	s[empty_idx + 1] = s[x + 1];  	s[x] = s[x + 1] = '-';  	empty_idx = x;  	print();  }  //move(x)的效果：将第x个棋与第x + 1个棋一起分别移到两个空位上    void solve(int k) {//分治函数  	if(k == 4) {  		move(4);  		move(8);  		move(2);  		move(7);  		move(1);  		//k=4的情况就是完全照葫芦画瓢咯。  	} else {  		move(k);//先把中间的移最后  		move(2 * k - 1);//再移后边的两个*移中间  		solve(k - 1);//分治  	}  }    int main() {  	cin >> n;//读入  	init();//初始化  	solve(n);//调用分治  	return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});