递归——黑白棋子的移动

算法记录-1

递归——黑白棋子的移动

题目如下：

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

○○○○○●●●●●

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

○●○●○●○●○●

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

思路：

找规律
因为本人比较喜欢二进制，所以在这里，白棋用“1”代替，黑棋用“0”代替，空格用“2”代替。
假设有数组{1,1,1,1,1,1,1,0,0,0,0,0,0,0,2,2},即1的个数为7.在这里我们要找的东西有两个。
第一个是“1 0”

第二个是“2 2”

他们的位置在最开始时，是已知的。即"1"的位置是数组下标为6，“0”的位置是数组下标为7.而“2 2”的位置分别是数组的（length）长度length-1和length-2.
开始运行

刚开始的数组如下：

开始交换“1 0 ”和“2 2”，数组变成如下

再次交换，使得出现“1 1 1 1 1 1 0 0 0 0 0 0 2 2 1 0”，因为为了方便拿到“ 1 0 ”所以每次都让数组出现“1 0”的情况。此时只要把“1 1 1 1 1 1 2 2 0 0 0 0 0 0 1 0”这里的“2 2 ”与后面的“ 0 0 ”交换即可满足条件

这样有回到了刚开始的情况，刚开始也是这种的情况即“ 1 1 1 1 1 1 1 0 0 0 0 0 0 2 2”，只不过是我们把“2 2”后面的“1 0 ”忽略而已。所以按此思路下去，使用递归直到

可能有些人不明白为什么运行到最后会变成这样。我先把代码和运行效果贴出来

public class Black_While {
//	len = 16
//	13 -3 
	static int flag = 7;
	static int[] a = {1,1,1,1,1,1,1,0,0,0,0,0,0,0,2,2};
	public static void main(String[] args) {
		//right = 13 , left = 0
		sortArray(a, a.length-2, a.length-1,flag);
	}
//	int i = arr.length-1,j = arr.length-2;
	public static void sortArray(int[] arr,int i,int j,int flag) {
//		i ， j是空位

		int midright = flag;
		int midleft = midright-1;
		if(midleft==0) return;
		swapArray(midleft, midright, i, j);
		i-=2;j-=2;
		swapArray(midleft, midright, i, j);
		flag--;
		sortArray(arr,i,j,flag);

	}
//	 i1 = 6,j1 = 7   i2 = 13  j2=14
	public static void swapArray(int i1,int j1,int i2,int j2) {
		System.out.println(Arrays.toString(a));
		int temp1,temp2;
		temp1 = a[i1];
		temp2 = a[j1];
		a[i1] = a[i2];
		a[j1] = a[j2];
		a[i2] = temp1;
		a[j2] = temp2;
	}
}

** 效果如下**

可以看到，当“2 2”的第一个“2”位置为数组下标为1时，前面是没有两位数交换位置的！所以在这里我们要做一个判断，当“2 2”的第一个下标位置为1时，更换如下的位置！

这样即可完成完整交换，也满足了题意要求！

贴上完整代码

import java.util.Arrays;

public class Black_While {
	static int flag = 7;
	static int[] a = {1,1,1,1,1,1,1,0,0,0,0,0,0,0,2,2};
	public static void main(String[] args) {
		//right = 13 , left = 0
		sortArray(a, a.length-2, a.length-1,flag);
		System.out.println(Arrays.toString(a));
	}
//	int i = arr.length-1,j = arr.length-2;
	public static void sortArray(int[] arr,int i,int j,int flag) {
//		i ， j是空位

		int midright = flag;
		int midleft = midright-1;
		if(midleft==0) return;
		if(flag==2) {
			swapArray(midleft, midright, i, j);
			i -=2;
			j -=2;
			midright--;
			midleft--;

			int temp = 0;
			temp = a[i];
			a[i] = a[midleft];
			a[midleft] = temp;
		}else {
			swapArray(midleft, midright, i, j);
			i-=2;j-=2;
			swapArray(midleft, midright, i, j);
			flag--;
			sortArray(arr,i,j,flag);
		}

	}
//	 i1 = 6,j1 = 7   i2 = 13  j2=14
	public static void swapArray(int i1,int j1,int i2,int j2) {
		int temp1,temp2;
		temp1 = a[i1];
		temp2 = a[j1];
		a[i1] = a[i2];
		a[j1] = a[j2];
		a[i2] = temp1;
		a[j2] = temp2;
	}
}