例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，
因此解壓縮后，結果為：ACFUNBDXYXYBDXYXYBDXYXYFUNBDXYXYBDXYXYBDXYXYMN，
（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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/427398.html
標籤：C