算法练习2

P020801

image.png

tips:

  1. fgetc(fin):它读取一个打开的文件fin,读取每一个字符,然后返回一个int值,如果文件结束,fgetc返回一个特殊标记EOF

  2. getchar():从标准输入读取每一个字符,等价于fgetc(stdin)

  3. 在使用fgetc和getchar时,应该尽量避免写出和操作系统相关的程序

  4. fgetc(buf,maxn,fin):读取完整的一行放在字符数组buf中,且不会读取超过maxn-1个字符

  5. C语言不会禁止程序读写”非法内存“,例如声明的是char s[100],完全可以赋值s[10000]=’a’,但是后果自负

  6. C语言中的gets(s)函数存在缓冲区溢出漏洞,在C11标准里面已经被删除

A020801

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h> 
int main(){
int c, q = 1;
while((c = getchar()) != EOF){
if(c == '"'){
printf("%s",q?"``":"''");
q=!q;
}
else{
printf("%c",c);
}
}
return 0;

}

P020802

1.png

A020802

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
char s[]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main(){
int i,c;
while((c=getchar())!=EOF){
for(i=1;s[i] && s[i]!=c;i++);
if(s[i])
putchar(s[i-1]);
else
putchar(c);
}
return 0;
}

P020803

2.png

image.png

镜像字符串就,通俗来说,在纸上写一个A,然后再A的右边放一面镜子,在镜子里看到到依然是字符A,而像(3,E),(J,L)等的大概就是长得像吧。

比如3AIAE,3和E,A和A,I和I

image.png

A020803

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#include<string.h>
#include<ctype.h>

const char* rev = "A 3 HIL JM O 2TUVWXY51SE Z 8 ";
const char* msg[] = {"not a palindrome","a regular palindrome","a mirrored str","a mirrored palindrome"};

char r(char ch){
if(isalpha(ch))
return rev[ch-'A'];
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;
}

tips:

  1. isalpha:判断字符是否为字母;类似的还有idigit、isprint等,再ctype.h中定义
  2. toupper/tolower:转换大小写

P021801

猜数字游戏的提示

实现一个经典”猜数字”游戏。给定答案序列和用户猜的序列,统计有多少数字位置正确 (A),有多少数字在两个序列都出现过但位置不对(B)。

输入包含多组数据。每组输入第一行为序列长度n,第二行是答案序列,接下来是若干猜测序列。猜测序列全0时该组数据结束。n=0时输入结束。

image.png

A021801

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h> 
#define maxn 1010

int main(){
int n,a[maxn],b[maxn];
int kase = 0;
while(scanf("%d,",&n) == 1 && n){
printf("Game %d:\n",++kase);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(;;){
int A = 0,B = 0;
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
if(a[i] == b[i])
A++;
}
if(b[0]==0)
break;
for(int d=1;d<=9;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;
}

P021802

生成元

如果x加上x的各个数字之和得到y,就说x是y的生成元。给出n(1≤n≤100000),求最小生成元。无解输出0。例如,n=216,121,2005时的解分别为198,0,1979。

A021802

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<string.h>
#define maxn 100005

int ans[maxn];
int main(){
int T,n;
memset(ans,0,sizeof(ans));
for(int m=1;m<maxn;m++){
int x = m,y = m;
while(x>0){
y += x%10;
x /= 10;
}
if(ans[y]==0 || m<ans[y])
ans[y] = m;

}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}

P021803

环状序列

长度为n的环状串有n种表示法,分别为从某个位置开始顺时针得到。例如,图3-4的环状串有10种表示:

image.png

CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。在这些表示法中,字典序最小的称为”最小表示”。

输入一个长度为n(n≤100)的环状DNA串(只包含A、C、G、T这4种字符)的一种表示法,你的任务是输出该环状串的最小表示。例如,CTCC的最小表示是 CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC。

本题出现了一个新概念:字典序。

所谓字典序,就是字符串在字典中的顺序。一般地, 对于两个字符串,从第一个字符开始比较,当某一个位置的字符不同时,该位置字符较小的串,字典序较小(例如,abc比bcd小);如果其中一个字符串已经没有更多字符,但另一个字符串还没结束,则较短的字符串的字典序较小(例如,hi比history小)。字典序的概念可以推广到任意序列,例如,序列1, 2, 4, 7比1, 2, 5小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<string.h>
#define maxn 105

int less(const char* s,int p,int q){
int n = strlen(s);
for(int i=0;i<n;i++){
if(s[(p+i)%n] != s[(q+i)%n])
return s[(p+i)%n]<s[(q+i)%n];
}
return 0;
}

int main(){
int T;
char s[maxn];
scanf("%d",&T);
while(T--){
scanf("%s",s);
int ans = 0;
int n = strlen(s);
for(int i = 1;i<n;i++){
if(less(s,i,ans))
ans = i;
}
for(int i=0;i<n;i++)
putchar(s[(i+ans)%n]);
putchar('\n');
}
return 0;
}
分享到:

评论完整模式加载中...如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理