C语言程序设计100例之（64）：黑白棋子的移动
例64 黑白棋子的移动
问题描述
有2n个棋子排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为n=5 的情况：
○○○○○●●●●●
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如 n=5时，成为：
○●○●○●○●○●
任务：编程打印出移动过程。
输入
一个整数 n（4≤n≤100）。
输出
若干行，表示初始状态和每次移动的状态，用"o"表示白子，"*"表示黑子，"-"表示空行。
输入样例
输出样例
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*
（1）编程思路。
由输出样例可以看出，对于n>4的棋子的移动，每次移动棋子的操作可以把中间两个棋子“o*”移到最后，再把连续黑子中的后面两个棋子“**”移到中间，这样n个棋子的移动变成了n-1个棋子的移动，一直递归调用到n==4的时候，按样例固定输出即可。
（2）源程序。
#include
char chess[205];
void move(int x,int y)
{
char ch;
ch=chess[x];
chess[x]=chess[y];
chess[y]=ch;
}
void work (int n)
{
int i;
if (n==4)
{
move(3,8); move(4,9);
printf("%s\n",chess);
move(3,7); move(4,8);
printf("%s\n",chess);
move(1,7); move(2,8);
printf("%s\n",chess);
move(1,6); move(2,7);
printf("%s\n",chess);
move(0,6); move(1,7);
printf("%s\n",chess);
return;
}
move(n-1,2*n);
move(n,2*n+1);
printf("%s\n",chess);
move(n-1,2*n-2);
move(n,2*n-1);
printf("%s\n",chess);
work (n-1);
}
int main()
{
int n;
scanf("%d", &n);
int i;
for (i=0;i chess[i]='o'; for (i=n;i<2*n;i++) chess[i]='*'; chess[2*n]='-'; chess[2*n+1]='-'; chess[2*n+2]='\0'; printf("%s\n",chess); work (n); return 0; } 问题描述 任何一个正整数都可以用2的幂次方表示。例如 137=27 +23+20。 同时约定方次用括号来表示，即 ab可表示为a(b)。 由此可知，137 可表示为 2(7)+2(3)+2(0) 进一步： 7=22 +2+20 (21用2表示)，并且 3=2+20。 所以最后137 可表示为2(2(2)+2+2(0))+2(2+2(0))+2(0)。 又如：1315=210+28+25+2+1 所以1315最后可表示为：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 输入 一个正整数n（n≤20000）。 输出 一行，符合约定的n的0，2表示（在表示中不能有空格）。 输入样例 1315 输出样例 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) （1）编程思路。 编写递归函数void work(int n)将正整数n用2的幂次方表示。 首先将整数n转换为二进制数，保存在数组int b[16]中，例如，若n=1315，则对应数组b中，b[10]=b[8]=b[5]=b[1]=b[0]=1，其余元素均为0。然后用循环依次输出b数组中值为1的对应项，例如，b[10]=1，输出“2（10）”，由于括号中的值10不为0或1，因此递归调用work(10)将整数10用2的幂次方表示。 当n==0（2的0次幂，对应整数为1）或n=1（2的1次幂，对应整数为2）直接输出。 （2）源程序。 #include void work(int n); int main() { int n; scanf("%d",&n); work(n); return 0; } void work(int n) { int i,j,first,b[16]; if (n==0) printf("0"); else { i=0; first=1; while (n!=0) { b[i++]=n%2; n=n/2; } for (j=i-1;j>=0;j--) { if (b[j]==1) { if (first==1) first=0; else printf("+"); if (j==1) printf("2"); else { printf("2("); work(j); printf(")"); } } } } } 问题描述 对于连续的若干个相同的子串“X”可以压缩为“[DX]”的形式（D 是一个整数且1≤D≤99），比如说字符串“CBCBCBCB”可压缩为“[4CB]”或者“[2[2CB]]”，类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2CB]]]”则是三重的。现在给你一个压缩后的字符串，请你对其进行解压缩。 输入 第一行：一个字符串，字符串中保证只包含数字、大写字母、“[”和“]”。 输出 第一行：一个字符串，解压后的字符串长度在 20000 以内。 输入样例 AC[3FUN] 输出样例 ACFUNFUNFUN （1）编程思路。 编写递归函数void work(int left ,int right)对字符串left~right之间的字符进行解压缩。显然，初始调用时，left<=right，若left>right，则递归调用结束。 从left位置的字符开始进行处理，直到left>right。 1）若left位置的字符是大写字母，则直接输出； 2）若left位置的字符为“]”，则直接跳过,left++； 3）若left位置的字符为“[”，则后面一定会跟着一个整数D，用循环读取这些连续的数字并求得对应的数值sum（也是重复次数），此时left会移到数字的下一个位置，之后用循环找到与这个左括号相匹配的右括号“]”的位置i，重复sum次递归调用work(left,i-1)进行解压缩；这一递归调用结束后，在递归调用work(i+1,right)进行后续的处理。 下面以两个示例进行描述。 例1，解压缩“AC[3FUN]”，递归调用work(0,7)，left=0、1时，是字母，直接输出“AC”；left=2时为字符“[”，此时后面一定是数字，读取数字sum=3后，left=4，与left=2这个左括号“[”匹配的右括号“]”位置为7，递归调用work(4,6)三次，每次直接输出FUN，因此解压缩后，结果为：ACFUNFUNFUN。 例2，解压缩“AC[2FUN[3BD[2XY]]]MN”，递归调用work(0,19)，left=0、1时，是字母，直接输出“AC”；left=2时为字符“[”，此时后面一定是数字，读取数字sum=2后，left=4，与left=2这个左括号“[”匹配的右括号“]”位置为17，递归调用work(4,16)两次； 递归调用work(4,16)实际上是对字符串“FUN[3BD[2XY]]”进行解压缩，left=4、5、6时，是字母，直接输出“FUN”；left=7时为字符“[”，此时后面一定是数字，读取数字sum=3后，left=9，与left=7这个左括号“[”匹配的右括号“]”位置为16，递归调用work(9,15)三次； 递归调用work(9,15)实际上是对字符串“BD[2XY]”解压缩，left=9、10时，是字母，直接输出“BD”；left=11时为字符“[”，此时后面一定是数字，读取数字sum=2后，left=13，与left=11这个左括号“[”匹配的右括号“]”位置为15，递归调用work(13,14)两次；每次直接输出XY； 这样，字符串“BD[2XY]”解压缩的结果为：BDXYXY； 字符串“FUN[3BD[2XY]]” 解压缩的结果为：FUNBDXYXYBDXYXYBDXYXY； 递归调用work(4,16)结束后，再递归调用work(18,19)，每次直接输出MN。 因此解压缩后，结果为：ACFUNBDXYXYBDXYXYBDXYXYFUNBDXYXYBDXYXYBDXYXYMN。 （2）源程序。 #include #include char a[20005]; void work(int left ,int right) { if (left>right) return ; while (a[left] == ']') left++; while (a[left]>='A' && a[left]<='Z') // 字母直接输出 { printf("%c",a[left]); left++; if (left>right) return ; } if (left > right) return ; int level = 0; // 括号层数 if (a[left] == '[') { level++; left++; } int sum = 0; while (a[left] >='0' && a[left] <='9') { sum =sum*10+a[left] - '0'; left++; } int i,j,index; for (i = left;i<=right;i++) { if (a[i] == '[') level++; if (a[i] == ']') level--; if (level==0) { for (j=1;j<=sum;j++) { work(left,i-1); } index =i; break; } } work(index+1,right); return ; } int main () { scanf ("%s",a); int len=strlen(a); work(0,len-1); return 0; } 问题描述 在纺织CAD系统开发过程中，经常会遇到纱线排列的问题。 该问题的描述是这样的：常用纱线的品种一般不会超过25种，分别用小写字母表示不同的纱线，例如：abc表示三根纱线的排列；重复可以用数字和括号表示，例如：2(abc)表示abcabc；1(a)=1a表示a；2ab表示aab。如果括号前面没有表示重复的数字出现，则就可认为是1被省略了，如：cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑，也易于理解；但是计算机却不能理解。为了使计算机接受，就必须将简单紧凑的表达方式展开。请你把这个程序编写完成。 已知条件：输入的简单紧凑表达方式的长度不超过250个字符；括号前表示重复的数不超过1000；不会出现除了数字、括号、小写字母以外的任何其他字符；不会出现括号不配对等错误的情况。 输入 输入包括多个测试数据组，第一行输入的就是数据组数N，接着就是N行表达式，表达式是按照前面介绍的意义书写的。 输出 输出时含有N行，每行对应一个输入的表达式。 输入样例 1(1a2b1(ab)1c) 3(ab2(4ab)) 输出样例 abbabc abaaaabaaaababaaaabaaaababaaaabaaaab （1）编程思路。 本题相比习题64-2要简单些。同样从左到右解析字符串并展开，采用递归求解。 设递归函数int work(int pos)的功能是对pos位置开始的字符串进行展开，从pos位置开始进行如下处理： 1）若pos位置的字符是数字，用循环读取这些连续的数字并求得对应的数值cnt（也是重复次数）； 2）若pos位置的字符是小写字母，则重复输出cnt个该字符（若cnt=0，置cnt=1）； 3）若pos位置的字符为“(”，则递归调用work(pos+1)，这一递归直到碰到对应匹配的“)”（设位置为x）结束；递归处理之后，置pos=x+1，继续展开后续的字符串； 4）若pos位置字符为结束符“\0”，则这个处理展开结束。 （2）源程序。 #include #include char s[255]; int work(int pos) { while (s[pos]!=')'&& s[pos]!='\0') { int cnt=0; while (s[pos]>='0' && s[pos]<='9') cnt=cnt*10+s[pos++]-'0'; if (cnt==0) cnt++; int x=-1; while(cnt--) { if(s[pos]=='(') x=work(pos+1); else printf("%c",s[pos]); } if (x!=-1) pos=x; pos++; } return pos; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%s",s); work(0); printf("\n"); } return 0; }习题64
64-1 幂次方
64-2 字符串解压缩
64-3 展开字符串