C&C++   发布时间:2022-04-13  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了C语言程序设计100例之(64):黑白棋子的移动大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

例64  黑白棋子的移动

问题描述

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

○○○○○●●●●●

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

○●○●○●○●○●

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

输入

一个整数 n(4≤n≤100)。

输出

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

输入样例

7

输出样例

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 <stdio.h>

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<n;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;

}

习题64

64-1  幂次方

问题描述

任何一个正整数都可以用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 <stdio.h>

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(")");

               }

            }

        }

    }

}

64-2  字符串解压缩

问题描述

对于连续的若干个相同的子串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。

       因此解压缩后,结果为:ACFUNBDXYXYBDXYXYBDXYXYFUNBDXYXYBDXYXYBDXYXY@H_210_242@mN。

       (2)源程序。

#include <stdio.h>

#include <String.h>

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;

}

64-3  展开字符串

问题描述

在纺织CAD系统开发过程中,经常会遇到纱线排列的问题。

该问题的描述是这样的:常用纱线的品种一般不会超过25种,分别用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abC)表示abcabc;1(a)=1a表示a;2ab表示aab。如果括号前面没有表示重复的数字出现,则就可认为是1被省略了,如:cd(abC)=cd1(abC)=cdabc;这种表示方法非常简单紧凑,也易于理解;但是计算机却不能理解。为了使计算机接受,就必须将简单紧凑的表达方式展开。请你把这个程序编写完成。

已知条件:输入的简单紧凑表达方式的长度不超过250个字符;括号前表示重复的数不超过1000;不会出现除了数字、括号、小写字母以外的任何其他字符;不会出现括号不配对等错误的情况。

输入

输入包括多个测试数据组,第一行输入的就是数据组数N,接着就是N行表达式,表达式是按照前面介绍的意义书写的。

输出

输出时含有N行,每行对应一个输入的表达式。

输入样例

2

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 <stdio.h>

#include <String.h>

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;

}

大佬总结

以上是大佬教程为你收集整理的C语言程序设计100例之(64):黑白棋子的移动全部内容,希望文章能够帮你解决C语言程序设计100例之(64):黑白棋子的移动所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: