「PAT乙级真题解析」Basic Level 1090 危险品装箱 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设给定一组不相容的数值对, 然后给定多组数值, 要求检查每组数值中是否存在不相容的数值对。 所以本题的核心是数据的存储, 然后循环进行数据查询和比对。 如果使用的编程语言有哈希表和集合的数据结构, 可以直接将编号作为哈希表的键, 使用集合作为值来存储与其不相容的数值。 C语言中, 需要用数组存储, 然后手动遍历数据来实现"检查元素是否在集合中"。
#算法#数据结构#需求分析#c语言#pat考试
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT (Basic Level) Practice 1090 危险品装箱
问题分析
- 题设给定一组不相容的数值对, 然后给定多组数值, 要求检查每组数值中是否存在不相容的数值对。
- 所以本题的核心是数据的存储, 然后循环进行数据查询和比对。
- 如果使用的编程语言有哈希表和集合的数据结构, 可以直接将编号作为哈希表的键, 使用集合作为值来存储与其不相容的数值。
- C语言中, 需要用数组存储, 然后手动遍历数据来实现"检查元素是否在集合中"。
完整描述步骤
- 获取输入: 不相容的数值对数, 需要检查的数组数量
- 初始化统计器:
- 与其不相同的数值 = {}
- 获取输入: 每一对不相同的数值:
- 将 数值2 放入 与其不相同的数值[数值1] 中
- 将 数值1 放入 与其不相同的数值[数值2] 中
- 对于每一个需要检查的数组:
- 获取输入: 各个数值
- 对于每一个数值:
- 检查其他数值是否出现在该数值的不相同数值集合中
- 如果有:
- 输出"No"
- 直接进入下一个数组的检查
- 如果没有:
- 输出"Yes"
- 如果有:
- 检查其他数值是否出现在该数值的不相同数值集合中
伪代码描述
- get input: pair_amount, case_amount
- init recorder:
- incompatible_things = {}
- items_found_incompatible;
- for case pair:
- get input: item_1, item_2
- incompatible_things[item_1].append(item_2)
- incompatible_things[item_2].append(item_1)
- for each case:
- get input: items
- reset items_found_incompatible = False;
- for item_1 in range(0, len(items)):
- for item_2 in range(item_1, len(items)):
- if item_2 in incompatible_things[item_1]:
- print("No");
- items_found_incompatible = True;
- break;
- if item_2 in incompatible_things[item_1]:
- if items_found_incompatible:
- break;
- for item_2 in range(item_1, len(items)):
- if items_found_incompatible:
- print("No");
- else:
- print("Yes");
完整提交代码
/*
# 问题分析
题设给定一组不相容的数值对, 然后给定多组数值, 要求检查每组数值中是否存在不相容的数值对。
所以本题的核心是数据的存储, 然后循环进行数据查询和比对。
如果使用的编程语言有哈希表和集合的数据结构, 可以直接将编号作为哈希表的键, 使用集合作为值来存储与其不相容的数值。
C语言中, 需要用数组存储, 然后手动遍历数据来实现"检查元素是否在集合中"。
# 完整描述步骤
1. 获取输入: 不相容的数值对数, 需要检查的数组数量
2. 初始化统计器:
- 与其不相同的数值 = {}
3. 获取输入: 每一对不相同的数值:
- 将 数值2 放入 与其不相同的数值[数值1] 中
- 将 数值1 放入 与其不相同的数值[数值2] 中
4. 对于每一个需要检查的数组:
- 获取输入: 各个数值
- 对于每一个数值:
- 检查其他数值是否出现在该数值的不相同数值集合中
- 如果有:
- 输出"No"
- 直接进入下一个数组的检查
- 如果没有:
- 输出"Yes"
# 伪代码描述
1. get input: pair_amount, case_amount
2. init recorder:
- incompatible_things = {}
- items_found_incompatible;
3. for case pair:
- get input: item_1, item_2
- incompatible_things[item_1].append(item_2)
- incompatible_things[item_2].append(item_1)
4. for each case:
- get input: items
- reset items_found_incompatible = False;
- for item_1 in range(0, len(items)):
- for item_2 in range(item_1, len(items)):
- if item_2 in incompatible_things[item_1]:
- print("No");
- items_found_incompatible = True;
- break;
- if items_found_incompatible:
- break;
- if items_found_incompatible:
- print("No");
- else:
- print("Yes");
*/
# include<stdio.h>
int incompatible_things[100000][100000];
int things_is_incompatible(int *items, int item_amount, int *incompatible_amount){
for (int i = 0; i < item_amount; i++){
int item_ID = items[i];
int check_amount = incompatible_amount[item_ID];
for (int j = i+1; j < item_amount; j++){
for(int k = 0; k < check_amount; k++){
if (incompatible_things[item_ID][k] == items[j]){
return 1;
}
}
}
}
return 0;
}
int main(){
int incompatible_amount[100000];
for (int i = 0; i < 100000; i++){
incompatible_amount[i] = 0;
}
int pair_amount;
int case_amount;
scanf("%d %d", &pair_amount, &case_amount);
int ID_1, ID_2;
for (int i = 0; i < pair_amount; i++){
scanf("%d %d", &ID_1, &ID_2);
incompatible_things[ID_1][incompatible_amount[ID_1]] = ID_2;
incompatible_amount[ID_1]++;
incompatible_things[ID_2][incompatible_amount[ID_2]] = ID_1;
incompatible_amount[ID_2]++;
}
int item_amount, item_ID;
int incompatible_flag = 0;
for (int i = 0; i < case_amount; i++){
scanf("%d", &item_amount);
int items[item_amount];
for (int j = 0; j < item_amount; j++){
scanf("%d", &items[j]);
}
if (things_is_incompatible(items, item_amount, incompatible_amount)){
printf("No\n");
} else {
printf("Yes\n");
}
}
return 0;
}