172 lines
4.4 KiB
Markdown
172 lines
4.4 KiB
Markdown
# 第9课：数组计数法（学生版）
|
||
|
||
## 教学目标
|
||
|
||
- 理解“数值作下标、次数存数组”的计数思想
|
||
- 掌握数组计数的核心写法
|
||
- 能用计数数组完成频次统计、最高频查找和去重升序输出
|
||
- 知道数组计数法的适用条件和下标范围限制
|
||
|
||
## 核心考点：数值映射为下标的数组计数思想
|
||
|
||
### 考什么
|
||
统计整数的出现次数，寻找最高频数字，或完成________和有序输出。
|
||
|
||
### 必须理解
|
||
用数组下标 x 表示________，用 `cnt[x]` 表示________。每读到一次 x，就执行________。数组大小必须覆盖题目给出的全部________。
|
||
|
||
### 核心写法
|
||
```cpp
|
||
int cnt[________] = {};
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
____________________;
|
||
}
|
||
for (int i = 0; i <= 100; i++) {
|
||
if (____________________) cout << i;
|
||
}
|
||
```
|
||
|
||
### 常见错误
|
||
- 范围是0～100时，数组为什么要开101？________________
|
||
- 计数数组为什么必须清零？________________
|
||
- 负数能否直接作为数组下标？________
|
||
|
||
### 判断是否掌握
|
||
- [ ] 我能根据数据范围确定数组大小。
|
||
- [ ] 我能解释下标与计数值分别代表什么。
|
||
- [ ] 我能用计数数组完成频次或去重任务。
|
||
|
||
---
|
||
|
||
## 课前认识：什么是数组计数法
|
||
|
||
如果输入的数字都在 `0~100` 之间，可以准备一个 `cnt[101]` 数组。
|
||
|
||
- 数字 `x` 对应数组下标：________
|
||
- `cnt[x]` 保存：________________
|
||
- 每读到一个数字 x，执行：________________
|
||
|
||
---
|
||
|
||
## 课堂编程题
|
||
|
||
### 课堂1：成绩频次表【适中】
|
||
|
||
**题目描述：** 输入若干名学生的成绩，按分数从小到大输出每个出现过的分数及人数。
|
||
|
||
**输入格式：** 第一行输入学生人数；第二行输入每名学生的成绩。
|
||
|
||
**输出格式：** 每行输出一个出现过的分数和对应人数。
|
||
|
||
**数据范围：** 学生人数为 1～1000，成绩为 0～100。
|
||
|
||
**输入样例：**
|
||
```text
|
||
6
|
||
80 90 80 75 90 80
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
75 1
|
||
80 3
|
||
90 2
|
||
```
|
||
|
||
**解题思路：** 分数可直接作为下标；每读到一个分数，对应计数加一，最后从 0 遍历到 100。
|
||
|
||
**易错提醒：** 允许分数 100，所以数组至少需要 101 个位置。
|
||
|
||
---
|
||
|
||
### 课堂2：最受欢迎的号码【适中】
|
||
|
||
**题目描述：** 输入若干个 1～50 的号码，输出出现次数最多的号码及次数；若并列，输出较小号码。
|
||
|
||
**输入格式：** 第一行输入号码总数；第二行输入所有号码。
|
||
|
||
**输出格式：** 输出最受欢迎的号码及其出现次数。
|
||
|
||
**数据范围：** 号码总数为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
7
|
||
8 3 8 5 3 8 3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3 3
|
||
```
|
||
|
||
**解题思路：** 先计数，再从小到大打擂台；只有次数严格更多才更新，便能保留并列时较小号码。
|
||
|
||
**易错提醒：** 更新条件不能写大于等于，否则并列时会留下较大号码。
|
||
|
||
---
|
||
|
||
### 课堂3：去重并升序输出【适中】
|
||
|
||
**题目描述：** 输入若干个 0～100 的整数，去掉重复数字并升序输出，同时输出不同数字的个数。
|
||
|
||
**输入格式：** 第一行输入整数数量；第二行输入所有整数。
|
||
|
||
**输出格式：** 第一行输出不同数字的个数；第二行升序输出不同数字。
|
||
|
||
**数据范围：** 整数数量为 1～1000。
|
||
|
||
**输入样例：**
|
||
```text
|
||
8
|
||
4 2 4 1 2 9 1 5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
5
|
||
1 2 4 5 9
|
||
```
|
||
|
||
**解题思路：** 计数后从小到大遍历下标，次数大于 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 还原。
|
||
|
||
**易错提醒：** 负数不能直接作为数组下标；映射和还原必须使用相同偏移量。
|
||
|
||
---
|
||
|
||
## 课后作业
|
||
|
||
> 请完成本课对应的课后作业，见编程题文件。
|