「PAT乙级真题解析」Basic Level 1065 单身狗 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设给定几组数对, 代表几对情侣, 随后给出一组数, 要求判断哪些数没有和它的情侣数一起出现在这组数中. 看到这里, 这道题明显是一道查找题/搜索题, 搜索题的主要核心是数据存储与比较。 于是这里只涉及5位整数, 所以存储用整型数组存储即可, 数组的索引和索引位置所存储数值代表一对情侣数。 而查找的过程, 只需要使用一个数组作为是否出席的标志位数组, 将给出的所有数作为索引值, 索引位置值置为1, 代表这些数出现过。 然后再次遍历给定的这组数, 对于每一个数, 先从第一个数组中拿到其对应的情侣数, 然后到标
#算法#数据结构#需求分析#pat考试#c语言
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT乙级BasicLevelPractice 1065 单身狗
问题分析
题设给定几组数对, 代表几对情侣, 随后给出一组数, 要求判断哪些数没有和它的情侣数一起出现在这组数中. 看到这里, 这道题明显是一道查找题/搜索题, 搜索题的主要核心是数据存储与比较。 于是这里只涉及5位整数, 所以存储用整型数组存储即可, 数组的索引和索引位置所存储数值代表一对情侣数。 而查找的过程, 只需要使用一个数组作为是否出席的标志位数组, 将给出的所有数作为索引值, 索引位置值置为1, 代表这些数出现过。 然后再次遍历给定的这组数, 对于每一个数, 先从第一个数组中拿到其对应的情侣数, 然后到标志位数组中查看这个情侣数索引位置的值是否为1, 如果标志位数组值为1, 所以这个数的情侣数也出现在给定的数中; 是题设要求的单身狗数, 需要将其输出. 于是输出的时候要按照递增顺序, 所以我们可以用一个是否是单身狗数标志位的数组再次记录这些数, 然后按照索引顺序输出;
完整描述步骤
- 获取输入: 情侣数对数;
- 初始化情侣数记录器
- 对于每一对情侣数:
- 第一个数作为记录器的键(索引), 第二个数作为对应值
- 同时, 第二个数作为记录器的键(索引), 第一个数作为对应值
- 获取输入: 当场人数, 到场的人的ID
- 初始化到场标志位记录器
- 对于每一个ID, 将其在到场标志位记录器中的值置为1, 代表这个人出席了活动
- 初始化单身狗记录器, 单身狗数量统计器
- 对于每一个ID:
- 从情侣数记录器获取这个ID对应的情侣数
- 检查到场标志位记录器中这个情侣数的值是否为1, 即检查这个情侣数代表的人是否出席活动
- 如果值为0, 说明当前ID是我们要找的单身狗, 在单身狗记录器中对应索引位置的值置为1
- 单身狗数量统计器+1
- 按照递增顺序访问单身狗记录器中的索引:
- 如果索引位置对应的值为1, 则输出这个索引值(即,单身狗ID)
伪代码描述
- get input: couple_amount
- init recorder:
- all_couple
- get input: all couple
- for each couple:
- all_couple[couple[0]] = all_couple[couple[1]];
- all_couple[couple[1]] = all_couple[couple[0]];
- init recorder:
- checked = {0}
- get input: guest_amount, all guests_ID
- for each guests_ID:
- checked[guests_ID] = 1;
- init recorder:
- single = {0}
- single_amount = 0
- for each guests_ID:
- its couple = all_couple[guests_ID];
- if checked[couple] == 0:
- single_amount++;
- single[guests_ID] = 1;
- for index in single:
- if single[index] == 1:
- print(index)
- if single[index] == 1:
完整提交代码
/*
# 问题分析
题设给定几组数对, 代表几对情侣, 随后给出一组数, 要求判断哪些数没有和它的情侣数一起出现在这组数中.
看到这里, 这道题明显是一道查找题/搜索题, 搜索题的主要核心是数据存储与比较。
于是这里只涉及5位整数, 所以存储用整型数组存储即可, 数组的索引和索引位置所存储数值代表一对情侣数。
而查找的过程, 只需要使用一个数组作为是否出席的标志位数组, 将给出的所有数作为索引值, 索引位置值置为1, 代表这些数出现过。
然后再次遍历给定的这组数, 对于每一个数, 先从第一个数组中拿到其对应的情侣数, 然后到标志位数组中查看这个情侣数索引位置的值是否为1,
如果标志位数组值为1, 所以这个数的情侣数也出现在给定的数中; 是题设要求的单身狗数, 需要将其输出.
于是输出的时候要按照递增顺序, 所以我们可以用一个是否是单身狗数标志位的数组再次记录这些数, 然后按照索引顺序输出;
# 完整描述步骤
1. 获取输入: 情侣数对数;
2. 初始化情侣数记录器
3. 对于每一对情侣数:
- 第一个数作为记录器的键(索引), 第二个数作为对应值
- 同时, 第二个数作为记录器的键(索引), 第一个数作为对应值
4. 获取输入: 当场人数, 到场的人的ID
5. 初始化到场标志位记录器
5. 对于每一个ID, 将其在到场标志位记录器中的值置为1, 代表这个人出席了活动
6. 初始化单身狗记录器, 单身狗数量统计器
7. 对于每一个ID:
- 从情侣数记录器获取这个ID对应的情侣数
- 检查到场标志位记录器中这个情侣数的值是否为1, 即检查这个情侣数代表的人是否出席活动
- 如果值为0, 说明当前ID是我们要找的单身狗, 在单身狗记录器中对应索引位置的值置为1
- 单身狗数量统计器+1
8. 按照递增顺序访问单身狗记录器中的索引:
- 如果索引位置对应的值为1, 则输出这个索引值(即,单身狗ID)
# 伪代码描述
1. get input: couple_amount
2. init recorder:
- all_couple
3. get input: all couple
4. for each couple:
- all_couple[couple[0]] = all_couple[couple[1]];
- all_couple[couple[1]] = all_couple[couple[0]];
5. init recorder:
- checked = {0}
6. get input: guest_amount, all guests_ID
7. for each guests_ID:
- checked[guests_ID] = 1;
8. init recorder:
- single = {0}
- single_amount = 0
8. for each guests_ID:
- its couple = all_couple[guests_ID];
- if checked[couple] == 0:
- single_amount++;
- single[guests_ID] = 1;
7. for index in single:
- if single[index] == 1:
- print(index)
*/
# include<stdio.h>
# define MAX_AMOUNT 100000
int main(){
int couple_amount;
scanf("%d", &couple_amount);
int all_couple[MAX_AMOUNT];
memset(all_couple, -1, MAX_AMOUNT * sizeof(int));
int ID_1, ID_2;
for (int i = 0; i < couple_amount; i++){
scanf("%d %d", &ID_1, &ID_2);
all_couple[ID_1] = ID_2;
all_couple[ID_2] = ID_1;
}
int guest_amount;
int checked[MAX_AMOUNT] = {0};
scanf("%d", &guest_amount);
int guests_ID[guest_amount];
for (int i = 0; i < guest_amount; i++){
scanf("%d", &guests_ID[i]);
checked[guests_ID[i]] = 1;
}
int single_amount = 0;
int single[MAX_AMOUNT] = {0};
for (int i = 0; i < guest_amount; i++){
if (all_couple[guests_ID[i]] == -1 || checked[all_couple[guests_ID[i]]] != 1){
single_amount++;
single[guests_ID[i]] = 1;
}
}
printf("%d\n", single_amount);
for (int i = 0; i < MAX_AMOUNT && single_amount > 0; i++){
if (single[i] == 1){
printf("%05d", i);
single_amount--;
if (single_amount != 0){
printf(" ");
}
}
}
return 0;
}