722 lines
17 KiB
Markdown
722 lines
17 KiB
Markdown
# 第9课编程题（教师版）
|
||
|
||
## 本课知识点覆盖表
|
||
|
||
| 核心知识点 | 等级定位 | 对应课堂题 |
|
||
|---|---|---|
|
||
| 数值映射下标、计数数组初始化与边界 | 三级工具，服务一二级统计 | 课堂1 |
|
||
| 最高频打擂台与并列规则 | 三级工具，服务分支判断 | 课堂2 |
|
||
| 去重与按下标顺序输出 | 三级工具，服务循环遍历 | 课堂3 |
|
||
| 负数偏移映射与适用范围判断 | 三级工具，服务类型转换 | 课堂4 |
|
||
|
||
## 一、课堂练习（4题）
|
||
|
||
### 课堂1：成绩频次表【适中】
|
||
|
||
**题目描述：** 输入若干名学生的成绩，按分数从小到大输出每个出现过的分数及人数。
|
||
|
||
**输入格式：** 第一行输入学生人数；第二行输入每名学生的成绩。
|
||
|
||
**输出格式：** 每行输出一个出现过的分数和对应人数。
|
||
|
||
**数据范围：** 学生人数为 1～1000，成绩为 0～100。
|
||
|
||
**输入样例：**
|
||
```text
|
||
6
|
||
80 90 80 75 90 80
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
75 1
|
||
80 3
|
||
90 2
|
||
```
|
||
|
||
**解题思路：** 分数可直接作为下标；每读到一个分数，对应计数加一，最后从 0 遍历到 100。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[101] = {0};
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int score;
|
||
cin >> score;
|
||
count[score]++;
|
||
}
|
||
for (int score = 0; score <= 100; score++) {
|
||
if (count[score] > 0)
|
||
cout << score << " " << count[score] << "\n";
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 允许分数 100，所以数组至少需要 101 个位置。
|
||
|
||
### 课堂2：最受欢迎的号码【适中】
|
||
|
||
**题目描述：** 输入若干个 1～50 的号码，输出出现次数最多的号码及次数；若并列，输出较小号码。
|
||
|
||
**输入格式：** 第一行输入号码总数；第二行输入所有号码。
|
||
|
||
**输出格式：** 输出最受欢迎的号码及其出现次数。
|
||
|
||
**数据范围：** 号码总数为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
7
|
||
8 3 8 5 3 8 3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3 3
|
||
```
|
||
|
||
**解题思路：** 先计数，再从小到大打擂台；只有次数严格更多才更新，便能保留并列时较小号码。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[51] = {0};
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
int bestNumber = 1;
|
||
for (int number = 2; number <= 50; number++) {
|
||
if (count[number] > count[bestNumber])
|
||
bestNumber = number;
|
||
}
|
||
cout << bestNumber << " " << count[bestNumber];
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 更新条件不能写大于等于，否则并列时会留下较大号码。
|
||
|
||
### 课堂3：去重并升序输出【适中】
|
||
|
||
**题目描述：** 输入若干个 0～100 的整数，去掉重复数字并升序输出，同时输出不同数字的个数。
|
||
|
||
**输入格式：** 第一行输入整数数量；第二行输入所有整数。
|
||
|
||
**输出格式：** 第一行输出不同数字的个数；第二行升序输出不同数字。
|
||
|
||
**数据范围：** 整数数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
8
|
||
4 2 4 1 2 9 1 5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
5
|
||
1 2 4 5 9
|
||
```
|
||
|
||
**解题思路：** 计数后从小到大遍历下标，次数大于 0 就输出一次并增加不同数字个数。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[101] = {0}, kinds = 0;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
for (int number = 0; number <= 100; number++)
|
||
if (count[number] > 0) kinds++;
|
||
cout << kinds << "\n";
|
||
bool first = true;
|
||
for (int number = 0; number <= 100; number++) {
|
||
if (count[number] > 0) {
|
||
if (!first) cout << " ";
|
||
cout << number;
|
||
first = false;
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 下标从小到大遍历时，答案天然有序。
|
||
|
||
### 课堂4：温度统计【适中】
|
||
|
||
**题目描述：** 输入若干个 -20～50 的整数温度，输出每个出现过的温度及次数，并输出出现次数最多的温度；并列取较低温度。
|
||
|
||
**输入格式：** 第一行输入记录数量；第二行输入所有温度。
|
||
|
||
**输出格式：** 先按温度从低到高输出频次表，最后一行输出最高频温度。
|
||
|
||
**数据范围：** 记录数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
6
|
||
-2 0 -2 3 0 -2
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
-2 3
|
||
0 2
|
||
3 1
|
||
BEST -2
|
||
```
|
||
|
||
**解题思路：** 温度加 20 后映射到 0～70；输出和比较时再把下标减 20 还原。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[71] = {0};
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int temperature;
|
||
cin >> temperature;
|
||
count[temperature + 20]++;
|
||
}
|
||
int best = 0;
|
||
for (int index = 0; index <= 70; index++) {
|
||
if (count[index] > 0)
|
||
cout << index - 20 << " " << count[index] << "\n";
|
||
if (count[index] > count[best]) best = index;
|
||
}
|
||
cout << "BEST " << best - 20;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 负数不能直接作为数组下标；映射和还原必须使用相同偏移量。
|
||
|
||
## 二、课后作业（3题）
|
||
|
||
### 课后1：查询出现次数【简单】
|
||
|
||
**题目描述：** 输入若干个 0～50 的整数和一个查询数字，输出该数字出现次数。
|
||
|
||
**输入格式：** 第一行输入整数数量；第二行输入所有整数；第三行输入查询数字。
|
||
|
||
**输出格式：** 查询数字的出现次数。
|
||
|
||
**数据范围：** 整数数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5
|
||
1 3 3 8 3
|
||
3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3
|
||
```
|
||
|
||
**解题思路：** 使用计数数组统计后，直接访问查询数字对应的位置。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[51] = {0}, query;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
cin >> query;
|
||
cout << count[query];
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 数字本身是下标，数组中保存的是次数。
|
||
|
||
### 课后2：最少出现的数字【简单】
|
||
|
||
**题目描述：** 输入若干个 0～100 的整数，输出出现次数最少且确实出现过的数字；并列取较小者。
|
||
|
||
**输入格式：** 第一行输入整数数量；第二行输入所有整数。
|
||
|
||
**输出格式：** 满足条件的数字和出现次数。
|
||
|
||
**数据范围：** 整数数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
6
|
||
2 2 3 4 4 4
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3 1
|
||
```
|
||
|
||
**解题思路：** 遍历时跳过次数为 0 的数字，再用打擂台寻找最小正次数。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[101] = {0}, answer = -1;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
for (int number = 0; number <= 100; number++) {
|
||
if (count[number] == 0) continue;
|
||
if (answer == -1 || count[number] < count[answer])
|
||
answer = number;
|
||
}
|
||
cout << answer << " " << count[answer];
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 没出现过的数字次数为 0，但不能参加“最少出现”比较。
|
||
|
||
### 课后3：成绩分段【简单】
|
||
|
||
**题目描述：** 输入若干成绩，依次统计不及格、60～79、80～89、90～100 四个分数段的人数。
|
||
|
||
**输入格式：** 第一行输入学生人数；第二行输入每名学生的成绩。
|
||
|
||
**输出格式：** 依次输出四个分数段的人数。
|
||
|
||
**数据范围：** 学生人数为 1～1000，成绩为 0～100。
|
||
|
||
**输入样例：**
|
||
```text
|
||
6
|
||
55 60 79 80 90 100
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
1 2 1 2
|
||
```
|
||
|
||
**解题思路：** 先按具体分数计数，再按四个区间累加频次。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[101] = {0}, group[4] = {0};
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int score;
|
||
cin >> score;
|
||
count[score]++;
|
||
}
|
||
for (int score = 0; score <= 100; score++) {
|
||
if (score < 60) group[0] += count[score];
|
||
else if (score < 80) group[1] += count[score];
|
||
else if (score < 90) group[2] += count[score];
|
||
else group[3] += count[score];
|
||
}
|
||
cout << group[0] << " " << group[1] << " "
|
||
<< group[2] << " " << group[3];
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 分数段边界必须首尾相接，不能遗漏 60、80、90 和 100。
|
||
|
||
## 三、扩展练习（7题）
|
||
|
||
### 扩展1：缺少的号码【基础综合】
|
||
|
||
**题目描述：** 1～若干号中每个号码本应出现一次，实际记录中缺少一个号码。输出缺少的号码。
|
||
|
||
**输入格式：** 第一行输入完整号码范围的上界；第二行输入其余所有号码。
|
||
|
||
**输出格式：** 缺少的号码。
|
||
|
||
**数据范围：** 上界为 2～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5
|
||
1 2 5 3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
4
|
||
```
|
||
|
||
**解题思路：** 用计数数组记录出现情况，再寻找次数为 0 的号码。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int limit, count[1001] = {0};
|
||
cin >> limit;
|
||
for (int i = 1; i < limit; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
for (int number = 1; number <= limit; number++) {
|
||
if (count[number] == 0) {
|
||
cout << number;
|
||
break;
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 实际输入数量比完整范围少 1。
|
||
|
||
### 扩展2：字母频次表【基础综合】
|
||
|
||
**题目描述：** 输入一个只含大小写英文字母的字符串，忽略大小写，按字母顺序输出出现过的字母和次数。
|
||
|
||
**输入格式：** 输入一个不含空格的英文字母串。
|
||
|
||
**输出格式：** 每行输出一个小写字母和对应次数。
|
||
|
||
**数据范围：** 字符串长度为 1～500。
|
||
|
||
**输入样例：**
|
||
```text
|
||
GespG
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
e 1
|
||
g 2
|
||
p 1
|
||
s 1
|
||
```
|
||
|
||
**解题思路：** 先统一为小写，再用字母减去小写字母起点得到 0～25 的下标。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
#include <string>
|
||
#include <cctype>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
string s;
|
||
int count[26] = {0};
|
||
cin >> s;
|
||
for (char c : s) {
|
||
c = (char)tolower(c);
|
||
count[c - 'a']++;
|
||
}
|
||
for (int i = 0; i < 26; i++) {
|
||
if (count[i] > 0)
|
||
cout << (char)('a' + i) << " " << count[i] << "\n";
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 大写和小写统一后才能计入同一个位置。
|
||
|
||
### 扩展3：只出现一次的最小数【中等】
|
||
|
||
**题目描述：** 输入若干个 0～1000 的整数，输出只出现一次的最小数字；不存在时输出 `NONE`。
|
||
|
||
**输入格式：** 第一行输入整数数量；第二行输入所有整数。
|
||
|
||
**输出格式：** 满足条件的数字或 `NONE`。
|
||
|
||
**数据范围：** 整数数量为 1～2000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
7
|
||
5 2 5 3 8 2 9
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3
|
||
```
|
||
|
||
**解题思路：** 计数后从小到大寻找第一个次数等于 1 的下标。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[1001] = {0}, answer = -1;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
for (int number = 0; number <= 1000; number++) {
|
||
if (count[number] == 1) {
|
||
answer = number;
|
||
break;
|
||
}
|
||
}
|
||
if (answer == -1) cout << "NONE";
|
||
else cout << answer;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** “只出现一次”必须判断次数恰好等于 1。
|
||
|
||
### 扩展4：公共数字【中等】
|
||
|
||
**题目描述：** 输入两组 0～100 的整数，升序输出两组中都出现过的数字，每个数字只输出一次；没有则输出 `NONE`。
|
||
|
||
**输入格式：** 第一行输入第一组数量和所有数字；第二行输入第二组数量和所有数字。
|
||
|
||
**输出格式：** 两组共有的不同数字。
|
||
|
||
**数据范围：** 每组数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5 1 2 2 5 8
|
||
4 2 3 5 5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
2 5
|
||
```
|
||
|
||
**解题思路：** 分别用两个计数数组记录，两边次数都大于 0 的下标就是公共数字。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int firstCount[101] = {0}, secondCount[101] = {0};
|
||
int n, number;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> number;
|
||
firstCount[number]++;
|
||
}
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> number;
|
||
secondCount[number]++;
|
||
}
|
||
bool found = false;
|
||
for (int value = 0; value <= 100; value++) {
|
||
if (firstCount[value] > 0 && secondCount[value] > 0) {
|
||
if (found) cout << " ";
|
||
cout << value;
|
||
found = true;
|
||
}
|
||
}
|
||
if (!found) cout << "NONE";
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 只判断是否出现，不按较小次数重复输出。
|
||
|
||
### 扩展5：两数之和查询【中等】
|
||
|
||
**题目描述：** 输入若干个 0～1000 的整数和目标和，判断能否从中选出两个不同位置的数，使它们之和等于目标。
|
||
|
||
**输入格式：** 第一行输入整数数量和目标和；第二行输入所有整数。
|
||
|
||
**输出格式：** 可以则输出 `YES`，否则输出 `NO`。
|
||
|
||
**数据范围：** 整数数量为 2～2000，目标和为 0～2000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5 10
|
||
2 8 4 4 7
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
YES
|
||
```
|
||
|
||
**解题思路：** 计数后枚举第一个数，检查补数是否出现；两个数相同时必须至少出现两次。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, target, count[1001] = {0};
|
||
cin >> n >> target;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
bool found = false;
|
||
for (int value = 0; value <= 1000; value++) {
|
||
int other = target - value;
|
||
if (other < 0 || other > 1000) continue;
|
||
if (value != other && count[value] > 0 && count[other] > 0)
|
||
found = true;
|
||
if (value == other && count[value] >= 2)
|
||
found = true;
|
||
}
|
||
cout << (found ? "YES" : "NO");
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** “不同位置”允许数值相同，但该数必须出现至少两次。
|
||
|
||
### 扩展6：频次最接近目标【略难】
|
||
|
||
**题目描述：** 输入若干个 0～100 的整数和目标次数，找出出现次数与目标次数差值最小且确实出现过的数字；并列取较小数字。
|
||
|
||
**输入格式：** 第一行输入整数数量和目标次数；第二行输入所有整数。
|
||
|
||
**输出格式：** 满足条件的数字及实际出现次数。
|
||
|
||
**数据范围：** 整数数量为 1～1000，目标次数为 0～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
8 3
|
||
1 1 2 2 2 2 5 5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
1 2
|
||
```
|
||
|
||
**解题思路：** 计数后对出现过的数字进行二次打擂台，比较频次与目标的距离。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
#include <cmath>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, target, count[101] = {0}, answer = -1;
|
||
cin >> n >> target;
|
||
for (int i = 0; i < n; i++) {
|
||
int number;
|
||
cin >> number;
|
||
count[number]++;
|
||
}
|
||
for (int value = 0; value <= 100; value++) {
|
||
if (count[value] == 0) continue;
|
||
if (answer == -1 ||
|
||
abs(count[value] - target) < abs(count[answer] - target))
|
||
answer = value;
|
||
}
|
||
cout << answer << " " << count[answer];
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 没出现的数字不能参加比较；从小到大遍历且并列不更新即可保留较小数字。
|
||
|
||
### 扩展7：最多能配成多少对【略难】
|
||
|
||
**题目描述：** 输入若干只手套的颜色编号，每两只相同颜色手套可以配成一对。输出可配成的总对数、剩余单只数量，并按颜色升序输出每种颜色的对数。
|
||
|
||
**输入格式：** 第一行输入手套数量；第二行输入每只手套的颜色编号。
|
||
|
||
**输出格式：** 第一行输出总对数和剩余数量；随后输出每种能配对颜色的编号和对数。
|
||
|
||
**数据范围：** 手套数量为 1～2000，颜色编号为 1～100。
|
||
|
||
**输入样例：**
|
||
```text
|
||
8
|
||
1 1 1 2 2 3 3 3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3 2
|
||
1 1
|
||
2 1
|
||
3 1
|
||
```
|
||
|
||
**解题思路：** 每种颜色的对数是次数除以 2，剩余数是次数除以 2 的余数，再分别累加。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count[101] = {0}, pairs = 0, single = 0;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
int color;
|
||
cin >> color;
|
||
count[color]++;
|
||
}
|
||
for (int color = 1; color <= 100; color++) {
|
||
pairs += count[color] / 2;
|
||
single += count[color] % 2;
|
||
}
|
||
cout << pairs << " " << single << "\n";
|
||
for (int color = 1; color <= 100; color++) {
|
||
if (count[color] / 2 > 0)
|
||
cout << color << " " << count[color] / 2 << "\n";
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 同一颜色出现三次只能组成一对并剩下一只。
|