例题
-
- 例题3-1 TeX中的引号（Tex Quotes, UVa 272）
- 例题3-2 WERTYU（WERTYU, UVa10082）
- 例题3-3 回文词（Palindromes, UVa401）
- 例题3-4 猜数字游戏的提示（Master-Mind Hints, UVa 340）
- 例题3-5 生成元（Digit Generator, UVa1583）
- 例题3-6 环状序列（Circular Sequence, UVa1584）
例题3-1 TeX中的引号（Tex Quotes, UVa 272）
题目描述： 在TeX中，左双引号是“``”（两个`），右双引号是“’’”（两个’）。输入一篇包含双引号的文章，你的任务是把它转换成TeX的格式。
输入： “To be or not to be,” quoth the Bard, “that is the question”.The programming contestant replied: “I must disagree.To
C' or not to
C’, that is The Question!”
输出：
To be or not to be,'' quoth the Bard,
that is the question’’.
The programming contestant replied: ``I must disagree.
To
C' or not to
C’, that is The Question!’’
代码实现
#include<stdio.h>
int main()
{
int c,flag;
flag = 1;
while((c=getchar())!=EOF)
{
if(c=='"')
{
if(flag)
printf("%s","``");
else
printf("%s","''");
flag=!flag;
}
else
printf("%c",c);
}
return 0;
}
思考
1.
scanf("%s",s)可以输入字符串，但在本题不能用，碰到空格或TAB就会停下来
2.
getchar()函数的返回类型是int型，如果到达文件末尾或发生读错误，返回EOF
例题3-2 WERTYU（WERTYU, UVa10082）
题目描述： 把手放在键盘上时，稍不注意就会往右错一位。这样，输入Q会变成输入W，输入J会变成输入K等。键盘如图所示
输入一个错位后敲出的字符串（所有字母均大写），输出打字员本来想打出的句子。输入保证合法，即一定是错位之后的字符串。例如输入中不会出现大写字母A。
输入： O S, GOMR YPFSU/
输出： I AM FINE TODAY.
代码实现：
#include<iostream>
#include<stdio.h>
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main()
{
int c,i;
while((c=getchar())!=EOF)
{
for(i = 1; s[i]&&s[i]!=c; ++i);
if(s[i])
printf("%c",s[i-1]);
else
printf("%c",c);
}
return 0;
}
思考
1.
直接定义一个常量字符数组，将键盘的字符存进去，无需定义该数组的大小
2.
循环继续的条件，s数组当前元素存在且还没有找到c字符
3.
s[i]为非空，输出它左边的字符，s[i]为空时，输出原来输入的字符
例题3-3 回文词（Palindromes, UVa401）
题目描述： 输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后和原串相同，如abba和madam。所有镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。在本题中，每个字符的镜像如图3-3所示（空白项表示该字符镜像后不能得到一个合法字符）。输入的每行包含一个字符串（保证只有上述字符。不含空白字符），判断它是否为回文串和镜像串（共4种组合）。每组数据之后输出一个空行。
输入：
NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA
输出：
NOTAPALINDROME – is not a palindrome.
ISAPALINILAPASI – is a regular palindrome.
2A3MEAS – is a mirrored string.
ATOYOTA – is a mirrored palindrome.
代码实现：
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<string.h>
const char rev[]="A 3 HTL JM O 2TUVWXY51SE Z 8 ";
const char msg[4][100]={"not a palindrome",
"a regular palindrome",
"a mirrored string",
"a mirrored palindrome"
};
char r(char ch)
{
if(isalpha(ch))
return rev[ch-'A'];
else
return rev[ch-'0'+25];
}
int main()
{
char s[30];
while(scanf("%s",s)==1)
{
int len = strlen(s);
int p = 1,m = 1;
for(int i = 0; i<(len+1)/2; ++i)
{
if(s[i]!=s[len-1-i])//判断是否是回文
p = 0;
if(r(s[i])!=s[len-1-i])//判断是否是镜像
m = 0;
}
printf("%s -- is %s.\n\n",s, msg[m*2+p]);
}
return 0;
}
思考
1.
isalpha用来判断字母的属性，是否是字母，包含在头文件ctype.h中
例题3-4 猜数字游戏的提示（Master-Mind Hints, UVa 340）
题目描述：
实现一个经典"猜数字"游戏。给定答案序列和用户猜的序列，统计有多少数字位置正确（A），有多少数字在两个序列都出现过但位置不对（B）。
输入包含多组数据。每组输入第一行为序列长度n，第二行是答案序列，接下来是若干猜测序列。猜测序列全0时该组数据结束。n=0时输入结束。
输入：
4
1 3 5 5
1 1 2 3
4 3 3 5
6 5 5 1
6 1 3 5
1 3 5 5
0 0 0 0
10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0
输出：
Game 1:
(1,1)
(2,0)
(1,2)
(1,2)
(4,0)
Game 2:
(2,4)
(3,2)
(5,0)
(7,0)
代码实现
#include<iostream>
#include<stdio.h>
using namespace std;
const int Max = 1e3+5;
int main()
{
int n,a[Max],b[Max];
int k=0;
while(scanf("%d",&n)==1&&n){
printf("Game %d:\n",++k);
for(int i = 0; i < n; ++i)
scanf("%d",&a[i]);
for(;;)
{
int A = 0,B = 0,count = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d",&b[i]);
if(a[i] == b[i])
A++;
if(b[i] == 0)
count++;
}
if(count == n) break;
for(int d = 1; d < 10; ++d)
{
int c1 = 0,c2 = 0;
for(int i = 0; i < n; ++i)
{
if(a[i]==d) c1++;
if(b[i]==d) c2++;
}
if(c1 < c2) B += c1;
else
B += c2;
}
printf(" (%d,%d)\n",A,B-A);
}
}
return 0;
}
思考
1.
首先计算A，在相同位置的字母出现多少次
，其次计算
每个数字在答案序列和测试序列出现的次数
，取其中最小的次数，再减去A，即是多少个数字在两个序列都出现过但位置不同
例题3-5 生成元（Digit Generator, UVa1583）
题目描述：
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0。
输入：
3
216
121
2005
输出：
198
1979
代码实现
#include<iostream>
#include<string.h>
using namespace std;
const int Max = 1e5+5;
int a[Max];
int main()
{
int t,n;
memset(a,0,sizeof(a));
for(int i = 1; i < Max; ++i)
{
int x,y;
x = y = i;
while(x > 0)
{
y=y+x%10;
x=x/10;
}
if(a[y] == 0||i < a[y]) a[y] = i;//数组未标记，或已经存了数字进去，判断i<a[y],保证生成元是最小的
}
cin >> t;
while(t--)
{
cin >> n;
cout << a[n] << endl;
}
return 0;
}
思考
1.
生成元m是一定比n小的，只要枚举1到n的数，判断它们加上各个数字是否等于n
，即可，但是由于多组输入，效率太低
2.可通过
建表
的方式，一次性将100000之内的数，它们加上各个数字和得到的结果存进数组
例题3-6 环状序列（Circular Sequence, UVa1584）
题目描述：
长度为n的环状串有n种表示法，分别为从某个位置开始顺时针得到。例如，图3-4的环状串有10种表示：CGAGTCAGCT，GAGTCAGCTC，AGTCAGCTCG等。在这些表示法中，字典序最小的称为"最小表示"。
输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。
输入：
2
CGAGTCAGCT
CTCC
输出：
AGCTCGAGTC
CCCT
代码实现
#include<iostream>
#include<string.h>
using namespace std;
const int Max = 1e6+5;
char target[Max];
char temp[Max];
int main()
{
int n;
cin >> n;
while(n--){
cin >> temp;
strcpy(target,temp);
int len = strlen(temp);
for(int i = 0; i < len; ++i)//种类数
{
char a = temp[0];
for(int j = 1; j < len; ++j)
temp[j-1] = temp[j];
temp[len-1] = a;
if(strcmp(temp,target)<0) strcpy(target,temp);
}
cout << target << endl;
}
return 0;
}
思考
所谓字典序，就是字符串在字典中的顺序
，这里用一个strcmp函数直接对两个字符串进行比较