分治法 —— 黑白棋子移动
程序员文章站
2022-07-03 13:59:05
...
题目描述
有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:
○○○○○●●●●●
移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。如n=5时,成为:
○●○●○●○●○●
任务:编程打印出移动过程。
样例输入 Copy
7
样例输出 Copy
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*
题意解读
有2n个棋子(n≥4)排成一行 为什么n 至少要大于等于4呢?
我们再来看给出的样例,发现需要12步且每一步需要数字(%2d)来表示步骤的序号,我们可以发现都是两两交换,但是在4以及以后两两交换的方法和之前的交换不一样或者说无逻辑可言。
发现规律啦吧!那么该题是典型的分治策略,选择递归比较合适!
具体实现我们来看一下代码,嘿嘿!
Code
#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;
int n;
//n == 4 是一个边界, n = 7 的问题可以转化n = 6 的问题,最后转化到n = 4 的问题
//分治也可以分层递进
//主要是要找准规律
void print(char s[])
{
for (int i = 0; i < 2 * n + 2; i++)
printf("%c", s[i]);
printf("\n");
}
void Swap(char s[], int i, int j)//两个的字符的交换
{
char temp;
temp = s[i];
s[i] = s[j];
s[j] = temp;
temp = s[i + 1];
s[i + 1] = s[j + 1];
s[j + 1] = temp;
}
void fun(char a[],int m, int x)
{
if (m == 4)
{//m= 4时把无规律的情况直接打印输出即可,最后结束递归
printf("step%2d:", x++);Swap(a, 3, 8);print(a);
printf("step%2d:", x++);Swap(a, 3, 7);print(a);
printf("step%2d:", x++);Swap(a, 1, 7);print(a);
printf("step%2d:", x++);Swap(a, 1, 6);print(a);
printf("step%2d:", x++);Swap(a, 0, 6);print(a);
return ;
}
else {
// m != 4时,先进行两个字符的交换并打印,然后递归进入小规模问题中
printf("step%2d:", x++);Swap(a, m - 1, 2 * m);print(a);
printf("step%2d:", x++);Swap(a, m - 1, 2 * (m - 1));print(a);
fun(a, m - 1, x);//进入下一层递归,问题规模变小直到m = 4
}
}
int main ()
{
char a[200];
cin >> n;
int i;
for (i = 0; i < n; i++)
a[i] = 'o';
for (; i < 2 * n; i++)
a[i] = '*';
for (; i < 2 * n + 2; i++)
a[i] = '-';
//首先我们先输入n 以及 n个'o'和'*'以及 '-'
printf("step%2d:", 0);
print(a);
//打印0步骤的状态,即初始状态
fun(a, n, 1);//递归调用
return 0;
}
结语
其实代码部分对逻辑的阐述已经一目了然啦!该题根本点在于能否发现n >= 4 的核心点
当然本人刚刚学的分治算法,水平低下,讲解不一定清晰明了!
此处附上视频链接地址,推荐看一看来加深分治算法的理解!
参考链接 :https://www.bilibili.com/video/BV1kp4y197h7