欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分治法 —— 黑白棋子移动

程序员文章站 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

相关标签: 分治算法