「PAT乙级真题解析」Basic Level 1015 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目给出了一批考生的德才分数, 要求根据"司马光的理论"给出录取排名. 于是, 我们需要明确一下什么是"司马光的理论"
#算法#数据结构#需求分析#c语言#pat考试
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目给出了一批考生的德才分数, 要求根据"司马光的理论"给出录取排名. 于是, 我们需要明确一下什么是"司马光的理论"
"司马光的理论"
- 圣人: 才德全尽
- 愚人: 才德兼亡
- 君子: 徳胜于才
- 小人: 才胜于徳
排序顺序: 圣人 > 君子 > 愚人 > 小人
额外的输出要求
按照司马光的理论, 依次输出 圣人, 君子, 愚人, 小人. 每类人也要进行排序, 排序逻辑:
- 总分不同按总分从高到低
- 总分相同德分不同按德分从高到低
- 德分也相同按照准考证号从小到大
所以整理题目内容到这里, 我们隐约可以感受到"分类"和"排序"可能是这道题目的两个重点。
数据储存方式
需要考虑数据存储的原因在于, 由于参与排序的有德分, 才分, 准考证三个部分.
- 如果我们是用三个数组分别存储每个人的这三个信息的话, 那么排序时对这三个数据的排序/移动, 就会变得复杂 (复杂到我们无法在脑海里想象要怎么移动, 这暗示我们要改进这种存储方式)
- 如果我们用搜索引擎搜索C语言是否有"将几个信息作为一个整体进行存储"的方式, 我们会接触到C语言的"结构体".
结构体定义
结构体将几个变量囊括在一起, 用来表示一个"具有指定结构的个体/整体". 语法定义方式如下:
typedef struture{
结构体变量类型1 结构体变量名称1;
结构体变量类型2 结构体变量名称2;
......
} 结构体名称;可以用结构体名称定义结构体变量, 方式如下:
结构体的简称 变量名;
所以我们定义考生结构体如下:
typedef struture{
int person_ID;
int moral_score;
int talent_score;
} person;- 结构体定义之后, 作为一个整体, 可以像int, double这些基本类型一样使用.
- 如果要访问结构体的内部特征(字段/成员/...), 则可以使用
结构体变量名.字段名称来访问, 而且可以跟使用基本类型一样赋值. - 结构体也可以像基本类型赋值一样进行整体赋值, 比如:
结构体变量1 = 结构体变量2;
完整地描述步骤
- 读入数据(考生人数, 最低分数线, 最高分数线, 各个考生的具体数据)
- 检查各个考生的分数符合哪个人群的分类标准, 将考生归入对应类别;
- 排序各个类别的考生
- 按照司马光的理论顺序输出排序号的各个类别的考生
伪代码描述步骤
-
定义变量用于存储考生人数, 最低分数线, 最高分数线
-
定义变量
- 用于存储每次读入的考生准考证号, 德分, 才分
- 用于存储各个类别的考生(一个类别一个数组, 用二维数组来表示存储多个类别的考生)
- (需要存储每个类别的考生个数, 同时指明将考生放入对应类别时, 要放置在数组中的位置索引, 毕竟这是C语言)
-
循环读取每个考生的数据, 并进行如下操作(分类):
- if 德分和才分都大于等于最高分数线, 则是圣人类别, 放入分组0
- else if 德分大于等于最高分数线 (走这个逻辑的话说明德分和才分有一个低于最高分数线, 所以只要检查德分就可以), 则是君子, 放入分组1
- else if 德分大于才分, 则是愚人, 放入分组2
- else 是个小人, 放入分组3
-
对每个分组进行排序
-
输出合格的考生人数
-
依次打印出每个分组中的考生信息
【实现细节上的补充】
- C语言中, 是否有现成的排序方法, 如何使用?
- 需要
#include<stdlib.h>来导入排序方法 - 排序函数名为qsort
- 使用方法/调用传参格式为: qsort(待排序的数组名, 数组中要排序的元素个数, 单个元素大小/sizeof(单个元素类型), 自定义的排序逻辑)
- 需要
- 自定义排序逻辑如何写
- 自定义排序逻辑是一个函数, 函数参数为(const void * 参数名1, const void* 参数名2)
- void是为了兼容对任意类型, 需要自己在函数内部实现中自行进行类型转换
- 比如我们要排序整数, 则需要
int 新的变量名 = *(int *)参数名1; - 比如我们要排序结构体, 则需要
person 新的变量名 = *(person *)参数名1;
- 返回值为0, 代表比较的两个数相等
- 返回值为1(或者大于0), 代表 参数1 大于 参数2
- 返回值为-1(或者小于0), 代表 参数1 小于 参数2
- 排序默认是从小到大排序的,所以比如我们希望参数1小于参数2时, 应该返回负数(比如
number1 < number 2, 由于事实上number1的值比number2大, 所以实际返回的是-1)
- 自定义排序逻辑是一个函数, 函数参数为(const void * 参数名1, const void* 参数名2)
完整提交代码
/*
# 问题分析
题目给出了一批考生的德才分数, 要求根据"司马光的理论"给出录取排名.
于是, 我们需要明确一下什么是"司马光的理论"
## "司马光的理论"
圣人: 才德全尽
愚人: 才德兼亡
君子: 徳胜于才
小人: 才胜于徳
排序顺序: 圣人 > 君子 > 愚人 > 小人
## 额外的输出要求
按照司马光的理论, 依次输出 圣人, 君子, 愚人, 小人.
每类人也要进行排序, 排序逻辑:
- 总分不同按总分从高到低
- 总分相同德分不同按德分从高到低
- 德分也相同按照准考证号从小到大
所以整理题目内容到这里, 我们隐约可以感受到"分类"和"排序"可能是这道题目的两个重点。
# 数据储存方式
需要考虑数据存储的原因在于, 由于参与排序的有德分, 才分, 准考证三个部分.
如果我们是用三个数组分别存储每个人的这三个信息的话, 那么排序时对这三个数据的排序/移动, 就会变得复杂(复杂到我们无法在脑海里想象要怎么移动, 这暗示我们要改进这种存储方式)
如果我们用搜索引擎搜索C语言是否有"将几个信息作为一个整体进行存储"的方式, 我们会接触到C语言的"结构体".
## 结构体定义
结构体将几个变量囊括在一起, 用来表示一个"具有指定结构的个体/整体". 语法定义方式如下:
typedef struture{
结构体变量类型1 结构体变量名称1;
结构体变量类型2 结构体变量名称2;
......
} 结构体名称;
可以用结构体名称定义结构体变量, 方式如下:
结构体的简称 变量名;
所以我们定义考生结构体如下:
typedef struture{
int person_ID;
int moral_score;
int talent_score;
} person;
结构体定义之后, 作为一个整体, 可以像int, double这些基本类型一样使用.
如果要访问结构体的内部特征(字段/成员/...), 则可以使用`结构体变量名.字段名称`来访问, 而且可以跟使用基本类型一样赋值.
结构体也可以像基本类型赋值一样进行整体赋值, 比如: `结构体变量1 = 结构体变量2;`
# 完整地描述步骤
1. 读入数据(考生人数, 最低分数线, 最高分数线, 各个考生的具体数据)
2. 检查各个考生的分数符合哪个人群的分类标准, 将考生归入对应类别;
3. 排序各个类别的考生
4. 按照司马光的理论顺序输出排序号的各个类别的考生
# 伪代码描述步骤
1. 定义变量用于存储考生人数, 最低分数线, 最高分数线
2. 定义变量
- 用于存储每次读入的考生准考证号, 德分, 才分
- 用于存储各个类别的考生(一个类别一个数组, 用二维数组来表示存储多个类别的考生)
- (需要存储每个类别的考生个数, 同时指明将考生放入对应类别时, 要放置在数组中的位置索引, 毕竟这是C语言)
2. 循环读取每个考生的数据, 并进行如下操作(分类):
- if 德分和才分都大于等于最高分数线, 则是圣人类别, 放入分组0
- else if 德分大于等于最高分数线 (走这个逻辑的话说明德分和才分有一个低于最高分数线, 所以只要检查德分就可以), 则是君子, 放入分组1
- else if 德分大于才分, 则是愚人, 放入分组2
- else 是个小人, 放入分组3
3. 对每个分组进行排序
4. 输出合格的考生人数
5. 依次打印出每个分组中的考生信息
【实现细节上的补充】
1. C语言中, 是否有现成的排序方法, 如何使用?
- 需要`#include<stdlib.h>`来导入排序方法
- 排序函数名为qsort
- 使用方法/调用传参格式为: qsort(待排序的数组名, 数组中要排序的元素个数, 单个元素大小/sizeof(单个元素类型), 自定义的排序逻辑)
2. 自定义排序逻辑如何写
- 自定义排序逻辑是一个函数, 函数参数为(const void * 参数名1, const void* 参数名2)
- void是为了兼容对任意类型, 需要自己在函数内部实现中自行进行类型转为
- 比如我们要排序整数, 则需要`int 新的变量名 = *(int *)参数名1;`
- 比如我们要排序结构体, 则需要`person 新的变量名 = *(person *)参数名1;`
- 返回值为0, 代表比较的两个数相等
- 返回值为1(或者大于0), 代表 参数1 大于 参数2
- 返回值为-1(或者小于0), 代表 参数1 小于 参数2
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int person_ID;
int moral_score;
int talent_score;
} person;
int logic_to_sort_persons(const void *a, const void *b)
{
person person_1 = *(person *)a;
person person_2 = *(person *)b;
if ((person_1.moral_score + person_1.talent_score) != (person_2.moral_score + person_2.talent_score))
return (person_1.moral_score + person_1.talent_score) < (person_2.moral_score + person_2.talent_score);
if (person_1.moral_score != person_2.moral_score)
return person_1.moral_score < person_2.moral_score;
return person_1.person_ID > person_2.person_ID;
}
int main()
{
int person_amount, lowest_score_line, highest_score_line;
scanf("%d %d %d", &person_amount, &lowest_score_line, &highest_score_line);
person groups[4][person_amount];
int group_index[4] = {0, 0, 0, 0};
int over_baseline_amount = 0;
int person_ID, moral_score, talent_score, group_num;
for (int i = 0; i < person_amount; i++)
{
scanf("%d %d %d", &person_ID, &moral_score, &talent_score);
if (moral_score < lowest_score_line || talent_score < lowest_score_line)
continue;
if (moral_score >= highest_score_line && talent_score >= highest_score_line)
group_num = 0;
else if (moral_score >= highest_score_line)
group_num = 1;
else if (moral_score >= talent_score)
group_num = 2;
else
group_num = 3;
person current_person = {person_ID, moral_score, talent_score};
groups[group_num][group_index[group_num]] = current_person;
group_index[group_num]++;
over_baseline_amount++;
}
printf("%d\n", over_baseline_amount);
for (int i = 0; i < 4; i++)
{
qsort(groups[i], group_index[i], sizeof(groups[i][0]), logic_to_sort_persons);
for (int j = 0; j < group_index[i]; j++)
{
printf("%d %d %d\n", groups[i][j].person_ID, groups[i][j].moral_score, groups[i][j].talent_score);
}
}
return 0;
}