小菜鸡第一天做PAT
1001 卡拉兹猜想
卡拉兹(Callatz)猜想：
对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？
这个还挺基础的，随便写写。
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>
int callatz(int n)
{
int step = 0;
while(n != 1){
if(n%2 == 0){
n = n/2;
} else {
n = (3*n + 1) / 2;
}
step++;
}
return step;
}
int main()
{
int n, step;
scanf("%d",&n);
step = callatz(n);
printf("%d\n",step);
return 0;
}
|
1002 写出这个数
读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。
输入格式：
每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10100。
输出格式：
在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。
输入样例：
1
| 1234567890987654321123456789
|
输出样例：
从这道题开始，需要动脑子了。一开始我将n作为整数读取，然而，后面发现这个输入样例真的很长，10100用整数处理也太难了。查阅了大佬们的代码，决定用字符串的格式读入。但是最后还是没有通过全部的测试，我也不知道为什么（笑）。
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main()
{
int sum=0,m=0,t;
char str[1024],output[1024]="";
gets(str);
for(int i=0;i<strlen(str);i++){
sum += str[i] - '0';
}
t = sum;
while(sum / 10 != 0){
m++;
sum = sum / 10;
}
sum = t;
while(sum /10 != 0){
int i = sum / (int)pow(10,m);
switch(i){
case 0:
strcat(output,"ling ");
break;
case 1:
strcat(output,"yi ");
break;
case 2:
strcat(output,"er ");
break;
case 3:
strcat(output,"san ");
break;
case 4:
strcat(output,"si ");
break;
case 5:
strcat(output,"wu ");
break;
case 6:
strcat(output,"liu ");
break;
case 7:
strcat(output,"qi ");
break;
case 8:
strcat(output,"ba ");
break;
case 9:
strcat(output,"jiu ");
break;
}
sum = sum % (int)pow(10,m);
m--;
}
switch(sum){
case 0:
strcat(output,"ling");
break;
case 1:
strcat(output,"yi");
break;
case 2:
strcat(output,"er");
break;
case 3:
strcat(output,"san");
break;
case 4:
strcat(output,"si");
break;
case 5:
strcat(output,"wu");
break;
case 6:
strcat(output,"liu");
break;
case 7:
strcat(output,"qi");
break;
case 8:
strcat(output,"ba");
break;
case 9:
strcat(output,"jiu");
break;
}
printf("%s\n",output);
return 0;
}
|
1003 我要通过！
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
得到“答案正确”的条件是：
- 字符串中必须仅有
P、 A、 T这三种字符，不可以包含其它字符；
- 任意形如
xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
- 如果
aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。
输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。
输入样例：
1
2
3
4
5
6
7
8
9
| 8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
|
输出样例：
1
2
3
4
5
6
7
8
| YES
YES
YES
YES
NO
NO
NO
NO
|
这道题的条件非常绕，尤其是第三条，乍一看看不出是什么规则。不过我在想这道题能不能用正则去做，虽然我还不太懂正则（悲）。
首先第一个条件可以直接遍历字符串判断，这个没什么问题。
第二个条件可以先从xPATx的形式判断起，先跳过首位的空字符和A，再匹配PAT，再判断末尾是否是空字符或者A。
第三个条件，可以尝试归纳法。以下是参照知乎上大佬的分析方法
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <stdio.h>
#include <string.h>
int func()
{
char input[1024];
char *p;
int lena,lenb,lenend;
lena = 0;lenb = 0;lenend = 0;
scanf("%s",input);
for(int i=0;i<strlen(input);i++){
if(input[i] != 'P' && input[i] != 'A' && input[i] != 'T'){
return 1;
}
}
p = input;
while(*p == 'A'){
p++;
lena++;
}
if(*p != 'P'){
return 1;
} else{
p++;
if(*p != 'A'){
return 1;
} else{
while(*p == 'A'){
p++;
lenb++;
}
if(*p != 'T'){
return 1;
}
}
}
p++;
while(*p == 'A'){
p++;
lenend++;
}
if(*p != NULL){
return 1;
}
if(lenend != lenb*lena){
return 1;
}
return 0;
}
int main()
{
int n,result[1024];
scanf("%d",&n);
for(int i=0;i<n;i++){
result[i] = func();
}
for(int i=0;i<n;i++){
if(result[i] == 0)
printf("YES\n");
else
printf("NO\n");
}
}
|
1004 成绩排名
读入 n（>0）名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。
输入格式：
每个测试输入包含 1 个测试用例，格式为
1
2
3
4
5
| 第 1 行：正整数 n
第 2 行：第 1 个学生的姓名 学号 成绩
第 3 行：第 2 个学生的姓名 学号 成绩
... ... ...
第 n+1 行：第 n 个学生的姓名 学号 成绩
|
其中姓名和学号均为不超过 10 个字符的字符串，成绩为 0 到 100 之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。
输出格式：
对每个测试用例输出 2 行，第 1 行是成绩最高学生的姓名和学号，第 2 行是成绩最低学生的姓名和学号，字符串间有 1 空格。
输入样例：
1
2
3
4
| 3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
|
输出样例：
1
2
| Mike CS991301
Joe Math990112
|
这道题很简单啊，可是小菜鸡在写scanf()的时候忘记加&了，然后就绕路写了一个分隔函数。。。
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
| void string_process(char * input, struct student stu)
{
char *stu_name,*stu_num,*stu_grade;
int grade_int;
printf("input:%s\n",input);
stu_name = input;
stu_num = input;
while(*stu_num != ' '){
stu_num++;
}
*stu_num = '\0';
printf("name:%s\n",stu_name);
stu_num++;
stu_grade = stu_num;
while(*stu_grade != ' '){
stu_grade++;
}
*stu_grade = '\0';
printf("num:%s\n",stu_num);
stu_grade++;
strcpy(stu.name,stu_name);
strcpy(stu.number,stu_num);
grade_int = (int)(*stu_grade - '0') * 10 + (int)(*(stu_grade+1)-'0');
stu.grade = grade_int;
printf("grade:%d\n",grade_int);
}
|
其中的’ '可以用sep取代，必可活用于下一次……
代码如下：
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
| #include <stdio.h>
#include <string.h>
struct student
{
char name[20];
char number[20];
int grade;
};
int main()
{
int n,max=0,min=100;
struct student students[1024],top_student,bottom_student;
scanf("%d\n",&n);
for(int i=0;i<n;i++){
char input[1024];
scanf("%s %s %d",students[i].name,students[i].number,&(students[i].grade));
if(students[i].grade > max){
max = students[i].grade;
top_student = students[i];
}
if(students[i].grade < min){
min = students[i].grade;
bottom_student = students[i];
}
}
printf("%s %s\n",top_student.name,top_student.number);
printf("%s %s\n",bottom_student.name,bottom_student.number);
return 0;
}
|
1005 继续(3n+1)猜想
卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
输入格式：
每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。
输出格式：
每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。
输入样例：
输出样例：
这道题小菜鸡dubug了好久（吐血），然而还是有一个测试没有通过，先po一下代码在这里。
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <stdio.h>
int callatz(int n,int *becovered,int len)
{
int i;
while(n != 1){
if(len == 0){
becovered[0] = n;
len++;
}
if(n%2 == 0){
n = n/2;
} else {
n = (3*n + 1) / 2;
}
for(i=0;i<len;i++){
if(n == becovered[i]){
return len;
}
}
if(i == len){
becovered[len] = n;
len++;
}
}
return len;
}
int main()
{
int n,arr[1024],becovered[1024],output[1024];
int i,j,k,tmp;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
int len=0;
for(i=0;i<n;i++){
len = callatz(arr[i],becovered,len);
}
k=0;
for(i=0;i<n;i++){
for(j=0;j<len;j++){
if(arr[i] == becovered[j])
break;
}
if(j == len){
output[k] = arr[i];
k++;
}
}
for(i=0;i<k;i++){
for(j=i+1;j<k;j++){
if(output[i] < output[j]){
tmp = output[i];
output[i] = output[j];
output[j] = tmp;
}
}
if(i != k-1){
printf("%d ",output[i]);
} else {
printf("%d\n",output[i]);
}
}
}
|
