【递归】黑白棋子的移动

时间:2021-05-22 18:04:27

描述

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

○○○○○●●●●●

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

○●○●○●○●○●

题目

编程打印出移动过程。

输入

一个整数n(n<=100)

输出

若干行,表示初始状态和每次移动的状态,用"o"表示白子,"*"表示黑子,"-"表示空行。

输入样例1

7

输出样例1

ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
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*

解题思路

  其实主要就是一种递归的思想,整体来说很简单

  大致思路就是把n个棋子转换成n-1个棋子做,由于4很特殊

  所以单独输出;

  初始化——(向后移——向前移——判断)(循环递归)——暴力枚举——输出

题解

 1 #include<bits/stdc  .h>//万能头文件
 2 using namespace std;
 3 void hou(long long n);
 4 void qian(long long n);
 5 void si(long long n);
 6 void chu(long long n);
 7 void shu(long long x);
 8 char a[100001]; 
 9 bool j=true;
10 long long n,x=0;
11 int main()//主程序(好少)
12 {
13 
14     cin>>n; 
15     chu(n); 
16     return 0;
17 }
18 void chu(long long n)//初始化 
19 {
20     if(j)//赋值一下 
21     {
22         for(int i=1;i<=2*n;i  )//把棋子初始化
23             a[i]=o;
24         for(int i=n 1;i<=2*n;i  )
25             a[i]=*;
26         for(int i=2*n 1;i<=2*n 2;i  )
27             a[i]=-;
28         shu(x);
29         j=false;
30     }
31     if(n==4) si(n); //如果还剩四个,单独输出
32     if(n>4) hou(n); //否则继续操作
33 }
34 void hou(long long n) //向后移
35 {
36     if(a[1]!=-)
37    {  
38     swap(a[n],a[2*n 1]);//交换位置
39     swap(a[n 1],a[2*n 2]);
40     shu(x);    //输出输出 
41     qian(n);//做向前操作
42     } 
43     else return;
44  } 
45 void qian(long long n)//向前移 
46 {
47     swap(a[n],a[2*n-1]);//交换为主
48     swap(a[n 1],a[2*n]);
49     n--;
50     shu(x);//一波输出 
51     chu(n);//一波操作做完判断是否大于4 
52 }
53 void si(long long n)//4单独输出(暴力枚举) 
54 {
55     swap(a[4],a[9]);
56     swap(a[5],a[10]);
57     shu(x);
58     swap(a[4],a[8]);
59     swap(a[5],a[9]);
60     shu(x);
61     swap(a[2],a[8]);
62     swap(a[3],a[9]);
63     shu(x);
64     swap(a[2],a[7]);
65     swap(a[3],a[8]);
66     shu(x);
67     swap(a[1],a[7]);
68     swap(a[2],a[8]);
69     shu(x);
70     return;
71 } 
72 void shu(long long y)//负责输出 
73 {
74     for(int i=1;i<=n*2 2;i  )
75         cout<<a[i];
76     cout<<endl;
77     x  ;
78 }

借鉴专用区(大家都懂)

 1 #include<bits/stdc  .h>
 2 using namespace std;
 3 void hou(long long n);
 4 void qian(long long n);
 5 void si(long long n);
 6 void chu(long long n);
 7 void shu(long long x);
 8 char a[100001]; 
 9 bool j=true;
10 long long n,x=0;
11 int main()
12 {
13 
14     cin>>n; 
15     chu(n); 
16     return 0;
17 }
18 void chu(long long n)
19 {
20     if(j)
21     {
22         for(int i=1;i<=2*n;i  )
23             a[i]=o;
24         for(int i=n 1;i<=2*n;i  )
25             a[i]=*;
26         for(int i=2*n 1;i<=2*n 2;i  )
27             a[i]=-;
28         shu(x);
29         j=false;
30     }
31     if(n==4) si(n);
32     if(n>4) hou(n); 
33 }
34 void hou(long long n) 
35 {
36     if(a[1]!=-)
37    {  
38     swap(a[n],a[2*n 1]);
39     swap(a[n 1],a[2*n 2]);
40     shu(x);  
41     qian(n);
42     } 
43     else return;
44  } 
45 void qian(long long n) 
46 {
47     swap(a[n],a[2*n-1]);
48     swap(a[n 1],a[2*n]);
49     n--;
50     shu(x);
51     chu(n);
52 }
53 void si(long long n)
54 {
55     swap(a[4],a[9]);
56     swap(a[5],a[10]);
57     shu(x);
58     swap(a[4],a[8]);
59     swap(a[5],a[9]);
60     shu(x);
61     swap(a[2],a[8]);
62     swap(a[3],a[9]);
63     shu(x);
64     swap(a[2],a[7]);
65     swap(a[3],a[8]);
66     shu(x);
67     swap(a[1],a[7]);
68     swap(a[2],a[8]);
69     shu(x);
70     return;
71 } 
72 void shu(long long y)
73 {
74     for(int i=1;i<=n*2 2;i  )
75         cout<<a[i];
76     cout<<endl;
77     x  ;
78 }