棋子移动题解

1.棋子移动：

魔法世界的历史上曾经出现过一位赫赫有名的不败战神陈庆之，陈庆之以棋道悟兵法，一辈子身经数百战，没有一场败绩，并且没有一场不是在绝对的劣势中大胜敌军。

受此影响，魔法世界开始流行一种叫棋子移动的游戏，即有2N个棋子(N≥4)排成一行，开始位置为白子所有在左边，黑子所有在右边，例如当N=4时，棋子排列状况为：

〇〇〇〇●●●●

移动棋子的规则是:每次必须同时移动相邻两个棋子，颜色不限，能够左移也能够右移到空位上去,但不能调换两个棋子的左右位置.每次移动必须跳过若干个棋子

(不能平移)，要求最后能移成黑白相间的一行棋子。例如当N=4时，最终排列状况为：

〇●〇●〇●〇●

试求出移动步骤。

题解：

这道题刚刚看到咱们不难推测出这是一道递归题，并且是一道和“汉诺塔”极其类似的题。以后有的人和我同样去手算了一遍样例，但后来我发现其实不用列举太多：ios

根据前面咱们推测出这是一道与汉诺塔类似的题，那就和“汉诺塔”同样去推测棋子移动的规律：
经过观测题目给出的样例web

4,5-->9,10

    8,9-->4,5

    2,3-->8,9

    7,8-->2,3

    1,2-->7,8

把上面的分红两个一组来看，有规律： n, n + 1 --> 2 * n + 1, 2 * n + 2 和 2 * n, 2 * n + 1–>n, n + 1有了这个规律咱们就只用考虑n是多少就能够了。其次让咱们继续来枚举n为5时，根据上面的规律可得：（—为空格）svg

第一步：5,6–>11,12 〇〇〇〇●●●●——〇● 让后就变成了n = 4的状况，这样两两关系就出来了，因而乎递推也出来了。spa

AC代码：

#include <iostream>
#include <cstdio> 
#include <cstring>
#include <algorithm>
using namespace std;
int n, k = 0;
void pr(int j){
	printf("%d,%d-->%d,%d\n\n",j, j + 1, k, k + 1);
	k = j;
}
void ss(int s){
	if(s == 4){
		pr(4);
		pr(8);
		pr(2);
		pr(7);
		pr(1);
	}
	else{
		pr(s);
		pr(2 * s - 1);
		ss(s - 1);
	}
	
}
int main() {
	scanf("%d", &n);
	k = 2 * n + 1;
	ss(n);
	return 0;
}