4.4 KiB
第9课：数组计数法（学生版）
教学目标
- 理解“数值作下标、次数存数组”的计数思想
- 掌握数组计数的核心写法
- 能用计数数组完成频次统计、最高频查找和去重升序输出
- 知道数组计数法的适用条件和下标范围限制
核心考点：数值映射为下标的数组计数思想
考什么
统计整数的出现次数，寻找最高频数字，或完成________和有序输出。
必须理解
用数组下标 x 表示________，用 cnt[x] 表示________。每读到一次 x，就执行________。数组大小必须覆盖题目给出的全部________。
核心写法
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。
输入样例：
6
80 90 80 75 90 80
输出样例：
75 1
80 3
90 2
解题思路： 分数可直接作为下标；每读到一个分数，对应计数加一，最后从 0 遍历到 100。
易错提醒： 允许分数 100，所以数组至少需要 101 个位置。
课堂2：最受欢迎的号码【适中】
题目描述： 输入若干个 1～50 的号码，输出出现次数最多的号码及次数；若并列，输出较小号码。
输入格式： 第一行输入号码总数；第二行输入所有号码。
输出格式： 输出最受欢迎的号码及其出现次数。
数据范围： 号码总数为 1～1000。
输入样例：
7
8 3 8 5 3 8 3
输出样例：
3 3
解题思路： 先计数，再从小到大打擂台；只有次数严格更多才更新，便能保留并列时较小号码。
易错提醒： 更新条件不能写大于等于，否则并列时会留下较大号码。
课堂3：去重并升序输出【适中】
题目描述： 输入若干个 0～100 的整数，去掉重复数字并升序输出，同时输出不同数字的个数。
输入格式： 第一行输入整数数量；第二行输入所有整数。
输出格式： 第一行输出不同数字的个数；第二行升序输出不同数字。
数据范围： 整数数量为 1～1000。
输入样例：
8
4 2 4 1 2 9 1 5
输出样例：
5
1 2 4 5 9
解题思路： 计数后从小到大遍历下标，次数大于 0 就输出一次并增加不同数字个数。
易错提醒： 下标从小到大遍历时，答案天然有序。
课堂4：温度统计【适中】
题目描述： 输入若干个 -20～50 的整数温度，输出每个出现过的温度及次数，并输出出现次数最多的温度；并列取较低温度。
输入格式： 第一行输入记录数量；第二行输入所有温度。
输出格式： 先按温度从低到高输出频次表，最后一行输出最高频温度。
数据范围： 记录数量为 1～1000。
输入样例：
6
-2 0 -2 3 0 -2
输出样例：
-2 3
0 2
3 1
BEST -2
解题思路： 温度加 20 后映射到 0～70；输出和比较时再把下标减 20 还原。
易错提醒： 负数不能直接作为数组下标；映射和还原必须使用相同偏移量。
课后作业
请完成本课对应的课后作业，见编程题文件。