PAT乙级

发表于 | 分类于

PAT乙级(一共80题)

1001. 害死人不偿命的(3n+1)猜想 (15)

卡拉兹(Callatz)猜想：

对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？
·
输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。

输出格式：输出从n计算到1需要的步数。

输入样例：
3
输出样例：
5

思路

读入题目给定的n，之后用while做循环，反复判断n是否为1

  1. 如果n==1,则退出循环，
  2. 如果n!=1,则判断n是否是偶数，是则n除以2；否则n为(3*n+1)除以2.之后令计数器step加1
    程序执行完后，step就是答案

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
int main(){
    int n = 0, step = 0;    //要初始化，不然vs2008输入数字是终止
    scanf("%d", &n);
    while(n != 1){
        if (n % 2 == 0){    //也可以用(n&1) == 0  但是判断奇偶是不能用 n%2 !=0
            n = n / 2;
        }else {
            n = (3*n + 1)/2;
        }
        step++;
    }
    printf("%d", step);
    return 0;
}

1009. 说反话 (20)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。

输出格式：每个测试用例的输出占一行，输出倒序后的句子。

输入样例：
Hello World Here I Come
输出样例：
Come I Here World Hello

思路

使用gets函数读入一整行，从左至右枚举每一个字符，以空格为分隔符对单词进行划分，并按顺序存放到二维字符数组中，最后按单词输入顺序的逆序来输出所有单词。

代码参考

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
#include <cstdio>
int main(){
    int num = 0;
    char ans[90][90] = {};
    while(scanf("%s", ans[num]) != EOF) {
        num++;
    }

    for(int i = num -1; i >= 0; i--) {
        printf("%s", ans[i]);
        if(i > 0) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <cstring>
int main() {
    char str[90] = {};
    gets(str);
    int len = strlen(str), r = 0, h = 0;
    char ans[90][90] = {};
    for(int i = 0; i < len; i++) {
        if(str[i] != ' ') {         //还没到空格就存入
            ans[r][h++] = str[i];
        }else {             
            ans[r][h] = '\0';   //是空格就在末尾加\0 控制%s输出
            r++;
            h = 0;
        }
    }
 
    for(int i = r; i >= 0; i--) {
        printf("%s", ans[i]);
        if(i > 0) {
            printf(" ");
        }
    }
    return 0;
}

1022. D进制的A+B (20)

输入两个非负10进制整数A和B(<=230-1)，输出A+B的D (1 < D <= 10)进制数。

输入格式：

输入在一行中依次给出3个整数A、B和D。

输出格式：

输出A+B的D进制数。

输入样例：
123 456 8
输出样例：
1103

思路

先计算A+B的按10进制，然后把结果转成D进制，除基取余法。

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
int main(){
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    int sum = a + b;
    int ans[31], num = 0;       //存放D进制每一位 31表示以2进制表示最多31个位置就够了
    do {
        ans[num++] = sum % d;
        sum /= d;
    }while(sum);

    for(int i = num-1; i >= 0; i--){    //逆序输出
        printf("%d", ans[i]);
    }
    return 0;
}

1032. 挖掘机技术哪家强(20)

为了用事实说明挖掘机技术到底哪家强，PAT组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：

输入在第1行给出不超过105的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从1开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例：
2 150

思路

  • 用一个数组school[maxn]，下标表示学校，内容表示分数，初始为0。对于每读入一个学校的schID和分数score，相应school[schID]+=score;
  • 令变量k记录最高总分学校编号，变量MAX记录最高总分，初值-1.由于学校是连续编号的从1开始，因此枚举编号1~N， 不断更新k和MAX值就好

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
int main(){
    const int maxn = 100001;
    int school[maxn] = {0};     //初始化

    int n = 0, schID = 0, score = 0;
    scanf("%d", &n);            //不判断n是否合法，因为给定就是在10^5内
    for(int i = 0; i < n; i++){
        scanf("%d%d", &schID, &score);
        school[schID] += score;
    }

    int k =1, MAX = -1;
    for(int i = 1; i <= n; i++){
        if(school[i] > MAX){
            MAX = school[i];
            k = i;
        }
    }

    printf("%d %d", k, MAX);
    return 0;
}

1036. 跟奥巴马一起编程(15)

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长N（3<=N<=20）和组成正方形边的某种字符C，间隔一个空格。

输出格式：

输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。

输入样例：
10 a
输出样例：
aaaaaaaaaa
a a
a a
a a
aaaaaaaaaa

思路

看到上面正方形是9*10的。在看有字母的，行数是列数的50%(四舍五入)。

第1行和最后一行全输出n个a，2~row-1行奇数行不输出，偶数行就头尾有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
#include <cstdio>
int main(){
    int row, col;
    char c;
    scanf("%d %c", &col, &c);   //输入列数和使用字符
    if(col % 2 == 1) {          //四舍五入得row
        row = col / 2 +1;
    }else{
        row = col / 2;
    }
    //frist row 1 这里就是从1开始 row表示数量，不用当做数组看，col还是按从0开始看
    for(int i = 0; i <= col-1; i++ ){
        printf("%c", c);
    }
    printf("\n");               //第一行后的空行 

    //2~row-1
    for(int i = 2; i <= row-1; i++ ){
        printf("%c", c);        //第一个c
        for(int j = 1; j < col-1; j++){
            printf(" ");        //输出col-2个空格
        }
        printf("%c\n", c);        //最后一个c
    }

    //最后一行 row
    for(int i = 0; i < col; i++ ){
        printf("%c", c);
    }

    return 0;
}