691 lines
15 KiB
Markdown
691 lines
15 KiB
Markdown
# 第5课编程题（教师版）
|
||
|
||
## 本课知识点覆盖表
|
||
|
||
| 核心知识点 | GESP等级 | 对应课堂题 |
|
||
|---|---|---|
|
||
| `for`、累加、累乘与循环边界 | 一级必考 | 课堂1 |
|
||
| `while`、取个位、去个位、数字反转 | 一级/二级 | 课堂2 |
|
||
| `break`、`continue` 与循环控制 | 一级必考 | 课堂3 |
|
||
| 双层循环、外层枚举对象、内层检查条件 | 一级巩固/二级 | 课堂4 |
|
||
|
||
> 本课包含 6 道双层循环题，作为第 6 课嵌套循环的过渡。
|
||
|
||
## 一、课堂练习（4题）
|
||
|
||
### 课堂1：奇偶分组统计【适中】
|
||
|
||
**题目描述：** 输入正整数 `n`，分别求 `1～n` 中奇数之和、偶数之和，并计算 `1～n` 的乘积。若乘积超过 `10^18`，输出 `TOO LARGE`。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 第一行奇数和与偶数和；第二行乘积或 `TOO LARGE`。
|
||
|
||
**数据范围：** `1≤n≤30`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
9 6
|
||
120
|
||
```
|
||
|
||
**解题思路：** 一个 `for` 循环同时完成奇偶累加；累乘前判断 `product>10^18/i`，避免溢出。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
long long oddSum = 0, evenSum = 0, product = 1;
|
||
bool tooLarge = false;
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
if (i % 2 == 0) evenSum += i;
|
||
else oddSum += i;
|
||
if (!tooLarge) {
|
||
if (product > 1000000000000000000LL / i) tooLarge = true;
|
||
else product *= i;
|
||
}
|
||
}
|
||
cout << oddSum << " " << evenSum << "\n";
|
||
if (tooLarge) cout << "TOO LARGE";
|
||
else cout << product;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 范围是 `1～n`，循环条件必须为 `i<=n`；累加器和累乘器的初值分别为 0 和 1。
|
||
|
||
### 课堂2：数字分析报告【适中】
|
||
|
||
**题目描述：** 输入一个非负整数，输出它的位数、各位数字之和、最大数字和反转数。
|
||
|
||
**输入格式：** 输入一个非负整数。
|
||
|
||
**输出格式：** 依次输出位数、各位和、最大数字、反转数。
|
||
|
||
**数据范围：** `0≤n≤10^9`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
50230
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
5 10 5 3205
|
||
```
|
||
|
||
**解题思路：** 备份原数，用 `while` 重复“取个位、使用个位、去个位”；单独处理 `n=0`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
#include <algorithm>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
if (n == 0) {
|
||
cout << "1 0 0 0";
|
||
return 0;
|
||
}
|
||
int temp = n, count = 0, sum = 0, biggest = 0, reversed = 0;
|
||
while (temp > 0) {
|
||
int digit = temp % 10;
|
||
count++;
|
||
sum += digit;
|
||
biggest = max(biggest, digit);
|
||
reversed = reversed * 10 + digit;
|
||
temp /= 10;
|
||
}
|
||
cout << count << " " << sum << " " << biggest << " " << reversed;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 反转后的前导零不会保留；0 本身有一位，不能被普通循环漏掉。
|
||
|
||
### 课堂3：寻找第一个合格数【适中】
|
||
|
||
**题目描述：** 从 `1～n` 中寻找第一个同时满足“能被 7 整除、不能被 5 整除、各位和大于 10”的数。跳过所有含数字 4 的数；找到后立即输出，否则输出 `NONE`。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 第一个合格数或 `NONE`。
|
||
|
||
**数据范围：** `1≤n≤100000`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
100
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
77
|
||
```
|
||
|
||
**解题思路：** 外层枚举数字；拆位检查含 4 和各位和。含 4 时 `continue`，找到答案时 `break`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, answer = -1;
|
||
cin >> n;
|
||
for (int x = 1; x <= n; x++) {
|
||
int temp = x, sum = 0;
|
||
bool hasFour = false;
|
||
while (temp > 0) {
|
||
int digit = temp % 10;
|
||
if (digit == 4) hasFour = true;
|
||
sum += digit;
|
||
temp /= 10;
|
||
}
|
||
if (hasFour) continue;
|
||
if (x % 7 == 0 && x % 5 != 0 && sum > 10) {
|
||
answer = x;
|
||
break;
|
||
}
|
||
}
|
||
if (answer == -1) cout << "NONE";
|
||
else cout << answer;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** `continue` 跳过本轮，`break` 结束整个当前循环，两者含义不同。
|
||
|
||
### 课堂4：区间素数统计【适中·双层循环】
|
||
|
||
**题目描述：** 输入 `L` 和 `R`，输出闭区间内的所有素数及素数个数。
|
||
|
||
**输入格式：** 输入区间的左端点和右端点。
|
||
|
||
**输出格式：** 第一行按升序输出素数；第二行输出个数。没有素数时第一行输出 `NONE`。
|
||
|
||
**数据范围：** `1≤L≤R≤10000`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
10 20
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
11 13 17 19
|
||
4
|
||
```
|
||
|
||
**解题思路：** 外层枚举候选数，内层从 2 检查到平方根；找到因数立即 `break`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int L, R, count = 0;
|
||
cin >> L >> R;
|
||
for (int x = L; x <= R; x++) {
|
||
if (x < 2) continue;
|
||
bool prime = true;
|
||
for (int d = 2; d * d <= x; d++) {
|
||
if (x % d == 0) {
|
||
prime = false;
|
||
break;
|
||
}
|
||
}
|
||
if (prime) {
|
||
if (count) cout << " ";
|
||
cout << x;
|
||
count++;
|
||
}
|
||
}
|
||
if (count == 0) cout << "NONE";
|
||
cout << "\n" << count;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 1 不是素数；内层的 `break` 只结束因数检查，不会结束外层枚举。
|
||
|
||
## 二、课后作业（3题）
|
||
|
||
### 课后1：从 1 加到 n【简单】
|
||
|
||
**题目描述：** 输入 `n`，用循环求 `1+2+…+n`。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 累加和。
|
||
|
||
**数据范围：** `1≤n≤10^6`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
15
|
||
```
|
||
|
||
**解题思路：** 累加器从 0 开始，循环范围为 `1～n`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
long long sum = 0;
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) sum += i;
|
||
cout << sum;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 和可能超过 `int`，使用 `long long`。
|
||
|
||
### 课后2：各位数字之和【简单】
|
||
|
||
**题目描述：** 输入一个正整数，输出各位数字之和。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 各位数字之和。
|
||
|
||
**数据范围：** `1≤n≤10^9`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
5082
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
15
|
||
```
|
||
|
||
**解题思路：** 每轮用 `n%10` 取个位并累加，再用 `n/=10` 去个位。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, sum = 0;
|
||
cin >> n;
|
||
while (n > 0) {
|
||
sum += n % 10;
|
||
n /= 10;
|
||
}
|
||
cout << sum;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 循环内必须更新 `n`，否则会形成死循环。
|
||
|
||
### 课后3：跳过 3 的倍数【简单】
|
||
|
||
**题目描述：** 输出 `1～n` 中所有不是 3 的倍数的数。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 符合条件的数，以空格分隔。
|
||
|
||
**数据范围：** `1≤n≤100`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
7
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
1 2 4 5 7
|
||
```
|
||
|
||
**解题思路：** 遇到 3 的倍数时使用 `continue`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
bool first = true;
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
if (i % 3 == 0) continue;
|
||
if (!first) cout << " ";
|
||
cout << i;
|
||
first = false;
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 输出空格时用 `first` 控制，可避免行末多余空格。
|
||
|
||
## 三、扩展练习（7题）
|
||
|
||
### 扩展1：回文数判断【基础综合】
|
||
|
||
**题目描述：** 输入一个非负整数，判断是否为回文数。
|
||
|
||
**输入格式：** 输入一个非负整数。
|
||
|
||
**输出格式：** 是回文数输出 `YES`，否则输出 `NO`。
|
||
|
||
**数据范围：** `0≤n≤10^9`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
12321
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
YES
|
||
```
|
||
|
||
**解题思路：** 备份原数，构造反转数并比较。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, temp, reversed = 0;
|
||
cin >> n;
|
||
temp = n;
|
||
while (temp > 0) {
|
||
reversed = reversed * 10 + temp % 10;
|
||
temp /= 10;
|
||
}
|
||
cout << (reversed == n ? "YES" : "NO");
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 0 的反转仍是 0，因此程序也能正确判断。
|
||
|
||
### 扩展2：三位水仙花数【中等·双层思维】
|
||
|
||
**题目描述：** 输出 `100～n` 中所有水仙花数。三位数各位数字立方和等于原数时称为水仙花数。
|
||
|
||
**输入格式：** 输入一个整数，表示枚举范围的上界。
|
||
|
||
**输出格式：** 所有水仙花数，以空格分隔；没有则输出 `NONE`。
|
||
|
||
**数据范围：** `100≤n≤999`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
400
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
153 370 371
|
||
```
|
||
|
||
**解题思路：** 外层枚举三位数，内层 `while` 拆出三位并累加立方。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count = 0;
|
||
cin >> n;
|
||
for (int x = 100; x <= n; x++) {
|
||
int temp = x, sum = 0;
|
||
while (temp > 0) {
|
||
int d = temp % 10;
|
||
sum += d * d * d;
|
||
temp /= 10;
|
||
}
|
||
if (sum == x) {
|
||
if (count) cout << " ";
|
||
cout << x;
|
||
count++;
|
||
}
|
||
}
|
||
if (count == 0) cout << "NONE";
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 判断时要与原数 `x` 比较，不能与已变成 0 的 `temp` 比较。
|
||
|
||
### 扩展3：因数清单【中等·双层循环】
|
||
|
||
**题目描述：** 对 `1～n` 中的每个数，输出该数及它的所有正因数，每个数占一行。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 第 `x` 行先输出 `x:`，再输出 `x` 的所有正因数。
|
||
|
||
**数据范围：** `1≤n≤30`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
3
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
1: 1
|
||
2: 1 2
|
||
3: 1 3
|
||
```
|
||
|
||
**解题思路：** 外层枚举数字 `x`，内层枚举可能的因数 `d`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
for (int x = 1; x <= n; x++) {
|
||
cout << x << ":";
|
||
for (int d = 1; d <= x; d++) {
|
||
if (x % d == 0) cout << " " << d;
|
||
}
|
||
cout << "\n";
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 内层上界随当前数字 `x` 变化，不是固定使用 `n`。
|
||
|
||
### 扩展4：完数统计【中等·双层循环】
|
||
|
||
**题目描述：** 一个正整数的所有真因数（不含自身）之和等于它本身，则称为完数。输出 `2～n` 中所有完数。
|
||
|
||
**输入格式：** 输入一个正整数。
|
||
|
||
**输出格式：** 所有完数；没有则输出 `NONE`。
|
||
|
||
**数据范围：** `2≤n≤10000`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
30
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
6 28
|
||
```
|
||
|
||
**解题思路：** 外层枚举候选数，内层枚举 `1～x/2` 并累加因数。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, count = 0;
|
||
cin >> n;
|
||
for (int x = 2; x <= n; x++) {
|
||
int sum = 0;
|
||
for (int d = 1; d <= x / 2; d++) {
|
||
if (x % d == 0) sum += d;
|
||
}
|
||
if (sum == x) {
|
||
if (count) cout << " ";
|
||
cout << x;
|
||
count++;
|
||
}
|
||
}
|
||
if (count == 0) cout << "NONE";
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 真因数不包含自身；每次检查新数字时 `sum` 都要清零。
|
||
|
||
### 扩展5：乘积等于目标的数对【中等·双层循环】
|
||
|
||
**题目描述：** 输入 `n` 和目标 `m`，输出所有满足 `1≤a<b≤n` 且 `a*b=m` 的数对。
|
||
|
||
**输入格式：** 输入枚举上界和目标乘积。
|
||
|
||
**输出格式：** 每行一对 `a b`；没有则输出 `NONE`。
|
||
|
||
**数据范围：** `1≤n≤1000`，`1≤m≤10^6`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
10 24
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
3 8
|
||
4 6
|
||
```
|
||
|
||
**解题思路：** 外层枚举 `a`，内层只从 `a+1` 枚举 `b`，避免重复和 `a=b`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, m, count = 0;
|
||
cin >> n >> m;
|
||
for (int a = 1; a <= n; a++) {
|
||
for (int b = a + 1; b <= n; b++) {
|
||
if (a * b == m) {
|
||
cout << a << " " << b << "\n";
|
||
count++;
|
||
}
|
||
}
|
||
}
|
||
if (count == 0) cout << "NONE";
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** `b` 从 `a+1` 开始，才能保证每个无序数对只输出一次。
|
||
|
||
### 扩展6：回文素数【略难·双层循环】
|
||
|
||
**题目描述：** 输出 `L～R` 中既是回文数又是素数的数。
|
||
|
||
**输入格式：** 输入区间的左端点和右端点。
|
||
|
||
**输出格式：** 所有回文素数；没有则输出 `NONE`。
|
||
|
||
**数据范围：** `1≤L≤R≤100000`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
10 150
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
11 101 131
|
||
```
|
||
|
||
**解题思路：** 外层枚举；先反转判断回文，通过后再用内层循环判断素数。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int L, R, count = 0;
|
||
cin >> L >> R;
|
||
for (int x = L; x <= R; x++) {
|
||
int temp = x, reversed = 0;
|
||
while (temp > 0) {
|
||
reversed = reversed * 10 + temp % 10;
|
||
temp /= 10;
|
||
}
|
||
if (reversed != x || x < 2) continue;
|
||
|
||
bool prime = true;
|
||
for (int d = 2; d * d <= x; d++) {
|
||
if (x % d == 0) {
|
||
prime = false;
|
||
break;
|
||
}
|
||
}
|
||
if (prime) {
|
||
if (count) cout << " ";
|
||
cout << x;
|
||
count++;
|
||
}
|
||
}
|
||
if (count == 0) cout << "NONE";
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 先判断回文可减少素数检查次数；1 仍然不是素数。
|
||
|
||
### 扩展7：最接近目标的因数积【略难·双层循环】
|
||
|
||
**题目描述：** 输入 `n` 和目标 `target`。在所有满足 `1≤a≤b≤n` 的数对中，寻找乘积与目标差的绝对值最小的一对；并列时先选较小的 `a`，再选较小的 `b`。
|
||
|
||
**输入格式：** 输入数对中每个数的上界和目标值。
|
||
|
||
**输出格式：** 输出 `a b a*b`。
|
||
|
||
**数据范围：** `1≤n≤500`，`1≤target≤250000`。
|
||
|
||
**输入样例：**
|
||
```text
|
||
10 53
|
||
```
|
||
|
||
**输出样例：**
|
||
```text
|
||
6 9 54
|
||
```
|
||
|
||
**解题思路：** 双层枚举所有合法数对，用二次打擂台比较乘积距离、`a`、`b`。
|
||
|
||
**参考代码：**
|
||
```cpp
|
||
#include <iostream>
|
||
#include <cmath>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, target;
|
||
cin >> n >> target;
|
||
int bestA = 1, bestB = 1;
|
||
for (int a = 1; a <= n; a++) {
|
||
for (int b = a; b <= n; b++) {
|
||
int now = a * b;
|
||
int best = bestA * bestB;
|
||
if (abs(now - target) < abs(best - target) ||
|
||
(abs(now - target) == abs(best - target) && a < bestA) ||
|
||
(abs(now - target) == abs(best - target) &&
|
||
a == bestA && b < bestB)) {
|
||
bestA = a;
|
||
bestB = b;
|
||
}
|
||
}
|
||
}
|
||
cout << bestA << " " << bestB << " " << bestA * bestB;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**易错提醒：** 枚举范围允许 `a=b`；并列规则必须按顺序完整处理。
|