第四章循环结构的程序设计¶

基础数学知识¶

分数与小数除法：分数表示除法；分子、分母都是整数时，数学上的分数仍可能不是整数。对应 1059—1061、1072、1078、1079、1082。
百分数与逐年增长：\(0.1\%=0.001\)，每年增长 \(0.1\%\)，下一年应在上一年的基础上乘 \(1.001\)；利息也要分清按哪一部分本金计算。对应 1070、1074。
乘方与阶乘：正整数次幂 \(a^n\) 是 \(n\) 个 \(a\) 相乘；非零数的零次幂为 \(1\)。\(n!=1\times2\times\cdots\times n\)，约定 \(0!=1\)。对应 2019、1069、1083、1084、2026、2033、1091—1093。
数列与递推关系：根据前面的项求后一项，例如 \(F_n=F_{n-1}+F_{n-2}\)；更新时要保留计算所需的旧值。对应 1071、1078。
等差数列求和：\(1+2+\cdots+n=\frac{n(n+1)}2\)，可通过正序与倒序配对推导。对应 2016、1081、2020、1100。
平面坐标、勾股定理与平方根：点 \((x,y)\) 到原点的距离是 \(\sqrt{x^2+y^2}\)。平方根表示“哪个非负数的平方等于这个数”。对应 1073、2030、2031。
向上取整：不小于原数的最小整数，例如 \(\lceil3.2\rceil=4\)、\(\lceil3\rceil=3\)。对应 1073，代码用 ceil。
余数与周期：只关心周期位置或末几位时，可保留除以周期或 \(10\) 的幂所得的余数；乘法每一步都取余，不改变最终余数。对应 1080、1082—1084、2033。
负数与整数除法：数学上的向下取整与 C++ 的向零截断不同。C++ 中 -38 / 10 为 \(-3\)，-38 % 10 为 \(-8\)，仍满足“被除数等于商乘除数加余数”。对应 1089。
质数、最大公约数与质因数分解：质数是大于 \(1\)、只有 \(1\) 和自身两个正约数的整数；最大公约数是两个正整数最大的公共约数；质因数分解是把整数写成质数的乘积。对应 2021、2030、2032、1098、1099。
完全平方数、立方与数位表示：完全平方数可以写成整数的平方；三位数 \(100a+10b+c\) 的各数位立方和是 \(a^3+b^3+c^3\)。对应 2029、2031。
用字母列方程与非负整数解：把数量、价格关系写成等式，非负整数包括 \(0\)。已知部分未知数后，可以用等式求出其余未知数，再检查是否满足条件。对应 2028、1101。

第一节 for语句¶

2016：【例4.1】for循环求和 ¶

提示 1：把手算加法交给循环

先写出1加到4的四次加法，下一次每次增加的是哪个数？

提示 2：总和从0开始

读入n，让sum从0开始：

for (int i = 1; i <= n; i++) sum += i;

若把<=写成<，少加的是哪一项？

常见错误

不要把 sum 定义在循环内部，否则每次都会清零。用 \(n=3\) 检查总和是否依次变成 \(1,3,6\)。

自测

输入：1 → 预期输出：1

输入：100 → 预期输出：5050

自己试试：先选一个较小的 \(n\)，自己把加法写出来。

再测 \(n+1\)，两次答案应该相差多少？

参考代码

#include <bits/stdc++.h>

using namespace std;

int sum, n;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) sum += i;

    cout << sum;

    return 0;
}

2017：【例4.2】输出偶数 ¶

提示 1：不满足条件就跳过

从1到6逐个看，哪些数需要输出？

输入1时，一个符合条件的数也没有，不要补0。

提示 2：把判断放进循环

i依次取1到n：

if (i % 2 == 0) cout << i << ' ';

用奇数上限5与偶数上限6比较，输出会差哪个数？

常见错误

不要从 \(0\) 开始输出，题目从 \(1\) 开始。\(n=1\) 时没有偶数，不输出字符，也不要补一个 \(0\)。

自测

输入：1 → 预期输出：不输出任何字符

输入：6 → 预期输出：2 4 6

自己试试：自己选一对相邻的奇数、偶数作为上限。

两次输出会多出哪个数？

方法一：逐个判断

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) cout << i << ' ';
    }

    return 0;
}

方法二：每次增加 2

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i += 2) cout << i << ' ';

    return 0;
}

2018：【例4.3】输出奇偶数之和 ¶

提示 1：两份和分开记

从1到5，把奇数圈起来、偶数画下划线，各自求和。

提示 2：每个数只进一个总和

先设odd = 0、even = 0，i从1走到n：

if (i % 2 == 0) even += i;
else odd += i;

按题目要求先输出偶数和；两者相加应等于哪题的结果？

常见错误

题目描述先说奇数，输出顺序却先要偶数。拿 \(n=3\) 检查，应输出 2 4。

自测

输入：1 → 预期输出：0 1

输入：10 → 预期输出：30 25

自己试试：自己选一个上限，分别手算奇数和、偶数和。

两者相加，能否用前面“for循环求和”那题的结果检查？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int odd = 0, even = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) even += i;
        else odd += i;
    }

    cout << even << ' ' << odd;

    return 0;
}

2019：【例4.4】求阶乘 ¶

提示 1：阶乘不是把数加起来

把\(4!\)写成乘法，最开始的乘积应该用0还是1？

提示 2：每次多乘当前项

读入n，先设long long ans = 1;：

for (int i = 1; i <= n; i++) ans *= i;

大类型要用在乘积变量上；算20的阶乘时int还能装下吗？

知识补充

\(5!=120\)，\(6!=6\times5!=720\)。阶乘的感叹号是数学记号；在 C++ 里，! 表示逻辑非，不能用 n! 写阶乘。

常见错误

把乘积初始化为 \(0\)，后面就一直是 \(0\)。C++ 的 ^ 不是乘方，也不能用它表示阶乘。

自测

输入：1 → 预期输出：1

输入：20 → 预期输出：2432902008176640000

自己试试：自己选一个能手算的 \(n\)，再测 \(n+1\)。

后一结果应该是前一结果的多少倍？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    long long ans = 1;
    for (int i = 1; i <= n; i++) ans *= i;

    cout << ans;

    return 0;
}

1059：求平均年龄 ¶

提示 1：总人数已给，不必保存所有年龄

先用15、16手算均值，为什么结果要带小数？

提示 2：每读一个就加进去

读入个数n，总和sum = 0；循环里读年龄x后：

sum += x;

读完n次后用1.0 * sum / n计算，保留两位小数。

常见错误

sum / n 两边都是整数时会先丢掉小数，事后存进 double 也补不回来。用平均数不是整数的数据检查。

自测

输入：2 15 16 → 预期输出：15.50

输入：1 25 → 预期输出：25.00

自己试试：在题目年龄范围内选两个不同年龄，让平均数带小数。

这组数据能检查出整数除法的问题吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        sum += x;
    }

    printf("%.2lf", 1.0 * sum / n);

    return 0;
}

1060：均值 ¶

提示 1：小数从读入时就保留

输入-1.5、0、3，若每个数先存int，会在哪里丢掉信息？

提示 2：循环里加，循环外除

n已读入，总和sum和每次读入的x都用double。

sum += x;

重复n次后除以n并输出四位小数；不要每轮就把总和除掉。

常见错误

不要用 int 读入小数；也不要照搬上一题的两位小数。用正负数抵消的情况检查。

自测

输入：2 1.0 3.0 → 预期输出：2.0000

输入：3 -1.5 0 3 → 预期输出：0.5000

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    double sum = 0;
    for (int i = 0; i < n; i++) {
        double x;
        cin >> x;
        sum += x;
    }

    printf("%.4lf", sum / n);

    return 0;
}

1061：求整数的和与均值 ¶

提示 1：一次读入得到两种结果

先手算1、2的总和与平均数，两项需要保留的小数位相同吗？

提示 2：先完整累加再算均值

sum = 0，每读入整数x就执行sum += x;，共读n次。

printf("%d %.5lf", sum, 1.0 * sum / n);

为什么第二项不能直接写sum / n？

常见错误

总和与均值之间要有空格。不要先做整数除法；用 \(1,2\) 检查小数部分。

自测

输入：2 1 2 → 预期输出：3 1.50000

输入：3 -2 0 2 → 预期输出：0 0.00000

自己试试：在题目范围内选几个正负数，让总和为零。

再只改其中一个数，先算出总和与均值各会怎样变化。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x;
    }

    printf("%d %.5lf", sum, 1.0 * sum / n);

    return 0;
}

1062：最高的分数 ¶

提示 1：第一个分数先当擂主

读完n，第一个分数先放到ans里，当擂主。

想一下，还有几个分数没读？

提示 2：后来读到的分数挑战它

循环里读到x后：

ans = max(ans, x);

循环执行n - 1次；输入只有一个0分时，还需要比较吗？

常见错误

不要每读到一个分数就直接覆盖答案。检查最高分在开头、末尾，以及只有一个分数的情况。

自测

输入：1 0 → 预期输出：0

输入：4 100 60 90 70 → 预期输出：100

自己试试：自己造一组分数，让最高分出现在最前面。

只调换位置，把它移到最后，答案应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, ans;
    cin >> n >> ans;

    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        ans = max(ans, x);
    }

    cout << ans;

    return 0;
}

1063：最大跨度值 ¶

提示 1：跨度只看最大和最小

对8、2、10、5，先找两端，再算跨度。

提示 2：两份纪录一起更新

第一个数x已读入，让maxn = minn = x，以后每读到一个数：

maxn = max(maxn, x);
minn = min(minn, x);

最后输出谁减谁？只有一个数时跨度是多少？

常见错误

不要用最后一个数减第一个数，输入不保证排好序。全部相同时，跨度应为 \(0\)。

自测

输入：1 7 → 预期输出：0

输入：4 8 2 10 5 → 预期输出：8

自己试试：把同一个数重复几次，先预测跨度。

再只改一个数，看看最大值和最小值分别怎样变化。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    int maxn = x, minn = x;
    for (int i = 1; i < n; i++) {
        cin >> x;
        maxn = max(maxn, x);
        minn = min(minn, x);
    }

    cout << maxn - minn;

    return 0;
}

1064：奥运奖牌计数 ¶

提示 1：三列分别累加

先把两天的金银铜奖牌上下对齐，每列各加一次。

提示 2：别把日总数和类别总数混在一起

三类总和suma、sumb、sumc从0开始，读一天的a b c后：

suma += a;
sumb += b;
sumc += c;

循环结束再算三类总数，检查输出是否恰好四项。

常见错误

不要把三类奖牌混在一个总和里后，就无法分别输出了。拿一天全为 \(0\) 的情况检查初始化。

自测

输入：1 0 0 0 → 预期输出：0 0 0 0

输入：2 1 2 3 2 0 1 → 预期输出：3 2 4 9

自己试试：自己造两天的数据，让某一类奖牌全为零。

四个输出之间，有什么关系可以用来检查？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int suma = 0, sumb = 0, sumc = 0;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        suma += a;
        sumb += b;
        sumc += c;
    }

    cout << suma << ' ' << sumb << ' ' << sumc << ' ' << suma + sumb + sumc;

    return 0;
}

1065：奇数求和 ¶

提示 1：先在区间里圈奇数

对2到7手算，包含右端点7吗？

提示 2：筛选和累加放在一层循环

sum = 0，i从m到n：

if (i % 2 != 0) sum += i;

试只有一个奇数的合法区间，看看循环有没有漏掉端点。

常见错误

不要漏掉右端点。i & 2 不能判断奇数；当前直接用 % 2。用端点本身为奇数的情况检查。

自测

输入：3 3 → 预期输出：3

输入：2 7 → 预期输出：15

自己试试：自己选一个包含奇数的合法区间。

只把右端点增加 \(1\)，总和可能不变，也可能增加，你能分别造出来吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    int sum = 0;
    for (int i = m; i <= n; i++)
        if (i % 2 != 0) sum += i;

    cout << sum;

    return 0;
}

1066：满足条件的数累加 ¶

提示 1：先列出17的倍数

在50到85中找出能被17整除的数，先算总和。

提示 2：符合才累加

区间端点m、n已读入，sum从0开始：

for (int i = m; i <= n; i++)
    if (i % 17 == 0) sum += i;

一个也找不到时，为什么直接输出sum即可？

常见错误

不要把条件记成不能整除，也不要混入其他除数。拿样例区间 \([50,85]\) 手算，符合条件的是 \(51,68,85\)，和为 \(204\)。

自测

输入：50 85 → 预期输出：204

输入：1 2 → 预期输出：0

输入：16 18 → 预期输出：17

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    int sum = 0;
    for (int i = m; i <= n; i++)
        if (i % 17 == 0) sum += i;

    cout << sum;

    return 0;
}

1067：整数的个数 ¶

提示 1：次数不是数值之和

读到1、5、5、10，三个计数各是多少？

提示 2：每类有自己的计数器

让a、b、c从0开始，读到x时：

if (x == 1) a++;
else if (x == 5) b++;
else if (x == 10) c++;

补读入循环，最后分三行输出，其他整数是否需要改变计数？

常见错误

cnt += x 是求和，统计个数应写 cnt++。没有出现的数字也要输出 \(0\)。

自测

输入：5 1 5 8 10 5，预期输出：

1
2
1

输入：2 8 8，预期输出：

0
0
0

自己试试：在题目允许的数字里，造一组没有 \(1\)、\(5\)、\(10\) 的数据。

再只替换其中一个数，预测哪一行输出会改变。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    cin >> k;

    int a = 0, b = 0, c = 0;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        if (x == 1) a++;
        else if (x == 5) b++;
        else if (x == 10) c++;
    }

    cout << a << '\n' << b << '\n' << c;

    return 0;
}

1068：与指定数字相同的数的个数 ¶

提示 1：目标在这一题提前给出

先读n m，随后每个数都可以立刻与目标m比较。

提示 2：命中一次就加一次

cnt = 0，循环里读到x后：

if (x == m) cnt++;

后面可能还有相同的数呢，n个都要看完。

常见错误

比较是 ==，不是赋值 =。先确认输入顺序，不要把 \(m\) 当成数列的第一个数。

自测

输入：5 2 2 1 2 3 2 → 预期输出：3

输入：1 9 8 → 预期输出：0

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x == m) cnt++;
    }

    cout << cnt;

    return 0;
}

1069：乘方计算 ¶

提示 1：先写出三次乘法

读入a、n，\(a^3\)是三个a相乘，不是a ^ 3。

提示 2：乘积从1开始

用long long res = 1;，每轮：

res *= a;

重复n次，自己补循环；负底数的正负怎样随指数变化？

常见错误

C++ 的 a ^ n 是按位异或，不是数学乘方。乘积初值不能是 \(0\)；负数底数要区分奇数次幂和偶数次幂。

自测

输入：-2 3 → 预期输出：-8

输入：10 6 → 预期输出：1000000

输入：0 1 → 预期输出：0

输入：-1 10000 → 预期输出：1

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, n;
    cin >> a >> n;

    long long res = 1ll;
    while (n--) {
        res *= a;
    }

    printf("%lld", res);

    return 0;
}

1070：人口增长 ¶

提示 1：第二年要用新人口

初始100人，第一年乘1.001；第二年还乘初始100，还是第一年的结果？

提示 2：让变量保留上一年的结果

人口x用double、年数为n：

for (int i = 0; i < n; i++) x *= 1.001;

循环中不要取整，全部算完才输出四位小数。

常见错误

不要把 \(0.1\%\) 写成 \(0.1\)，也不要只算最初人口的固定增量。中途别四舍五入，最后输出时统一保留位数。

自测

输入：1 1 → 预期输出：1.0010

输入：100 2 → 预期输出：100.2001

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    double x;
    int n;
    cin >> x >> n;

    for (int i = 0; i < n; i++) x *= 1.001;

    printf("%.4lf", x);

    return 0;
}

1071：菲波那契数 ¶

提示 1：只需记前两项

把1、1、2、3、5写出来，下一项由谁相加？

提示 2：先算新项，再更新旧项

初始化a = b = c = 1，从第3项开始：

c = a + b;
a = b;
b = c;

把a = b挪到最前面试一下，旧的a还在吗？

再想想，只求第1项、第2项时，要不要进循环。

常见错误

如果先改 a 再算 c，就丢掉旧值了。用 \(n=1,2,3\) 分别检查初始化与循环起点。

自测

输入：1 → 预期输出：1

输入：2 → 预期输出：1

输入：30 → 预期输出：832040

输入：46 → 预期输出：1836311903

自己试试：自己选相邻的三个合法项号，分别运行。

不用查答案表，能用数列关系检查这三个输出吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int a = 1, b = 1, c = 1;  // 在这里，对c进行初始化，就可以解决n<=2的情况

    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }

    cout << c;

    return 0;
}

1072：鸡尾酒疗法 ¶

提示 1：先留住第一组数据

第一组是原疗法，后面每组都只和它比较。

用两个变量留住原人数、原有效人数，读下一组时不要覆盖它们。

提示 2：差一点和刚好相差，要分开

原疗法100人中50人有效，新疗法分别试55人、56人有效。

前一组恰好高出0.05，还算same；后一组才算better。

提示 3：把比较写成整数关系

下面这一步，用整数来比。

如果乘20这里没跟上，先展开后面的知识补充，看一下怎么换过来的。

原人数、有效人数是total、good，新组是newtotal、newgood，都用int。

循环外先保存int base = 20 * good;，每读一组再算：

int diff = 20 * newgood * total - base * newtotal;
int limit = total * newtotal;

先补diff > limit输出better，再补更差和其余情况。

知识补充：为什么乘20

原有效率为\(\frac{50}{100}\)，新有效率为\(\frac{55}{100}\)，两者相差\(\frac5{100}=\frac1{20}=0.05\)。

人数不同也一样，先用“有效人数除以总人数”求各自的有效率。

为了用整数准确比较，把“新减旧大于\(\frac1{20}\)”两边都乘20，再乘两个正的总人数，得到：

\[ 20(\text{newgood}\times\text{total}-\text{good}\times\text{newtotal})>\text{total}\times\text{newtotal}. \]

代码用diff、limit分别保存两边；大于才算更好，等于仍算same。

20 * good对每组都一样，用base在循环外算一次。

更差时比较diff < -limit，其余都是same。

人数不超过\(10000\)，有效人数不超过总人数，中间乘积和差的绝对值最多为\(2\times10^9\)，int可以保存。

常见错误

不要把原疗法算进输出，也不要用 >=。比较基准始终是第一组，不能每次换成上一组。

自测

输入：4 100 50 100 55 100 56 100 44，预期输出：

same
better
worse

输入：2 100 50 100 45，预期输出：

same

自己试试：自己选一个原有效率，再配一个恰好高出 \(0.05\) 的新疗法。

先确认病例数都符合题目范围，再预测它与“多高出一点”的情况有何区别。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, total, good;
    cin >> n >> total >> good;

    int base = 20 * good;
    for (int i = 1; i < n; i++) {
        int newtotal, newgood;
        cin >> newtotal >> newgood;

        int diff = 20 * newgood * total - base * newtotal;
        int limit = total * newtotal;
        if (diff > limit) cout << "better" << '\n';
        else if (diff < -limit) cout << "worse" << '\n';
        else cout << "same" << '\n';
    }

    return 0;
}

1073：救援 ¶

提示 1：往返路程和接人时间分开算

坐标30、40离原点50米，船要去几趟单程？

每人上、下船总共1.5分钟，别只计一边。

提示 2：一次救援加进总用时

ret初值为0，当前坐标x、y用double，人数z用int：

ret += sqrt(x * x + y * y) * 2 / 50 + 1.5 * z;

处理完所有屋顶后才用ceil(ret)向上取整，能不能每趟先取整再加？

常见错误

不要把坐标读成整数，不要只算去程，也不要每次救援都先取整。可以画出往返路线，逐段核对。

自测

输入：1 30 40 1 → 预期输出：4

输入：2 0 0 1 0 0 1 → 预期输出：3

参考代码

#include <bits/stdc++.h>

using namespace std;

double ret;

int main() {
    int n;
    cin >> n;

    while (n--) {
        double x, y;
        int z;

        cin >> x >> y >> z;

        ret += sqrt(x * x + y * y) * 2 / 50 + 1.5 * z;
    }

    cout << (int)ceil(ret);

    return 0;
}

1074：津津的储蓄计划 ¶

提示 1：先记一个月的钱去了哪里

每月先拿到300元，再付预算，最后把剩下的整百元存起来。

先拿第一个月试一下，预算180元，存多少，手里还剩多少？

提示 2：不够付时，先停下来

cash记手中现金，saved记已存的钱，都从0开始。

每月先给cash加300；若不够付cost，输出负月份并结束。

付完预算后再存钱：

saved += cash / 100 * 100;
cash %= 100;

提示 3：十二个月都够，才算年末的钱

妈妈保管的saved增加20%利息，手里的cash原样加回来。

不能把两笔钱先合起来再乘1.2。

常见错误

失败后不要再输出年末余额；利息只给妈妈保管的存款，不能把手头零钱也乘 \(1.2\)。如果模拟对不上，带着月份表、出错输入和实际输出一起找老师看。

自测

输入：300 300 300 300 300 300 300 300 300 300 300 300 → 预期输出：0

输入：0 0 0 0 0 0 0 0 0 0 0 0 → 预期输出：4320

输入：301 0 0 0 0 0 0 0 0 0 0 0 → 预期输出：-1

自己试试：试着安排预算，让前一个月还能支付，下一个月第一次不够。

先在纸上记下每月现金，再检查输出的是哪个月份。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int cash = 0, saved = 0;
    for (int month = 1; month <= 12; month++) {
        int cost;
        cin >> cost;

        cash += 300;
        if (cash < cost) {
            cout << -month;

            return 0;
        }
        cash -= cost;
        saved += cash / 100 * 100;
        cash %= 100;
    }

    cout << cash + saved + saved / 5;

    return 0;
}

1075：药房管理 ¶

提示 1：不够给这人，后面还要继续

库存5，先来的人要6、后一个要5；两人各能否取到？

提示 2：成功才扣库存

读入库存m、人数n，让cnt = 0，每读需求x后：

if (x > m) cnt++;
else m -= x;

把这段放进循环；若先扣库存再判断，哪一步会出错？

常见错误

被拒绝时不要扣库存，也不能直接结束循环。后面需求较小的人仍可能拿到药。

自测

输入：5 3 6 5 1 → 预期输出：2

输入：10 2 4 6 → 预期输出：0

自己试试：自己造一组需求，让一个人被拒绝后，下一个人仍能成功取药。

这组数据主要检查哪一步有没有误改库存？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        if (x > m) cnt++;
        else m -= x;
    }

    cout << cnt;

    return 0;
}

1076：正常血压 ¶

提示 1：看的是连续，不是累计正常次数

把正常、正常、异常、正常画成四格，最长连续长度是多少？

提示 2：正常延长，异常中断

cnt记当前长度，ret记最长，两者从0开始。

两个血压值a、b要同时落在90到140、60到90，包含端点。

cnt++;
ret = max(ret, cnt);

放进正常分支；异常只把cnt清0，能把ret也清0吗？

常见错误

两个范围都包含端点，且用 && 连接。不要遇到不正常就把历史最大值一起清零。

自测

输入：4 90 60 140 90 89 80 100 80 → 预期输出：2

输入：1 141 90 → 预期输出：0

自己试试：自己安排两段长度不同的正常记录，中间插入一次不正常。

先标出最长的一段，再想想怎样检查最后一段也被统计了。

参考代码

#include <bits/stdc++.h>

using namespace std;

int ret, cnt;

int main() {
    int n;
    cin >> n;

    while (n--) {
        int a, b;
        cin >> a >> b;

        if (a >= 90 && a <= 140 && b >= 60 && b <= 90) {
            cnt++;
            ret = max(ret, cnt);
        }
        else {
            cnt = 0;
        }
    }

    cout << ret;

    return 0;
}

1077：统计满足条件的4位数 ¶

提示 1：先拆一个四位数

把1349的千、百、十、个位列出，用个位减去前三位之和。

等于0符合“严格大于0”吗？

提示 2：让数位分别进变量

当前数为x，先取：

int a = x / 1000, b = x / 100 % 10;

补十位c、个位d，用d - a - b - c > 0决定计数是否加一。

常见错误

这里拆的是刚读到的 x，不是循环变量 i。差恰好为 \(0\) 时不计入，拿 \(1113\) 检查。

自测

输入：5 1234 1349 6119 2123 5017 → 预期输出：3

输入：2 1113 1001 → 预期输出：0

自己试试：自己造一个“个位恰好等于其余三位之和”的四位数。

再只改个位，让差变为正数，先预测计数会怎样变化。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int a = x / 1000, b = x / 100 % 10;
        int c = x / 10 % 10, d = x % 10;
        if (d - a - b - c > 0) cnt++;
    }

    cout << cnt;

    return 0;
}

1078：求分数序列和 ¶

提示 1：先找下一项从哪里来

先写\(\frac21,\frac32,\frac53\)，分子记为q，分母记为p。

下一项的分母用旧分子，下一项的分子用旧分子加旧分母。

提示 2：旧分母先留一份

q = 2、p = 1，double sum = 0；循环里先把当前分数加进总和：

sum += 1.0 * q / p;
int t = p;
p = q;
q = q + t;

第一轮算完，p = 2、q = 3。

第二轮你接着算，别光看这四行代码。

把第二次的旧值、新值写在纸上，再补重复n次的循环。

常见错误

不能先执行 p = q 再直接 q += p，那样会加到两个旧分子。手算两次更新，检查是否得到 \(3/2\)、\(5/3\)。

自测

输入：1 → 预期输出：2.0000

输入：3 → 预期输出：5.1667

输入：30 → 预期输出：48.8406

自己试试：自己续写前几项分数，再选一个小的项数手算总和。

如果结果不对，先检查是分数更新错了，还是求和错了。

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
double sum;

int main() {
    cin >> n;

    int q = 2, p = 1;
    for (int i = 1; i <= n; i++) {
        sum += 1.0 * q / p;
        int t = p;
        p = q;
        q = q + t;
    }

    printf("%.4lf", sum);

    return 0;
}

1079：计算分数加减表达式的值 ¶

提示 1：加减号跟项号走

前三项是1减二分之一加三分之一，奇数项和偶数项分别做什么？

提示 2：小数除法别丢掉1.0

sum用double从0开始，项号i从1到n：

if (i % 2 == 1) sum += 1.0 / i;
else sum -= 1.0 / i;

用前两项检查符号，最后输出四位小数。

常见错误

1 / i 在 i > 1 时是整数 \(0\)，应写 1.0 / i。用 \(n=2\) 检查是否得到 \(0.5000\)。

自测

输入：1 → 预期输出：1.0000

输入：2 → 预期输出：0.5000

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    double sum = 0.0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) sum += 1.0 / i;
        else sum -= 1.0 / i;
    }

    printf("%.4lf", sum);

    return 0;
}

1080：余数相同问题 ¶

提示 1：从最小允许除数开始试

1总能让余数相同，但题目从大于1的数中找最小值。

所以从2开始逐个试。

提示 2：三个余数需要两次相等比较

a、b、c已读入，试除数x：

if (a % x == b % x && b % x == c % x) {
    cout << x;
    break;
}

仿照补从2递增的循环，第一次找到后为什么可以停？

常见错误

C++ 不能写 a % x == b % x == c % x 表示三者相等，要拆成两个比较，用 && 连接。

自测

输入：300 262 205 → 预期输出：19

输入：5 5 5 → 预期输出：2

自己试试：先选一个希望得到的最小除数，再造三个余数相同的数。

它们会不会在更小的除数处就满足条件？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    for (int x = 2; ; x++) {
        if (a % x == b % x && b % x == c % x) {
            cout << x;
            break;
        }
    }

    return 0;
}

1081：分苹果 ¶

提示 1：最少又互不相同

每人至少一个，把数量从小到大排，前四人最少可分1、2、3、4。

第n个人最少拿几个？

提示 2：把最少数量逐项加起来

n已读入，sum = 0：

for (int i = 1; i <= n; i++) sum += i;

先写熟循环，再想能否用首尾配对求同一个和。

常见错误

从 \(0\) 开始会让一个孩子拿不到苹果。公式中乘法先算再除以 \(2\)，不要先用整数除法计算 (n + 1) / 2。

自测

输入：1 → 预期输出：1

输入：8 → 预期输出：36

方法一：循环累加

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 1; i <= n; i++) sum += i;

    cout << sum;

    return 0;
}

方法二：等差数列求和公式

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    cout << (1 + n) * n / 2;

    return 0;
}

1082：求小数的某一位 ¶

提示 1：回到竖式除法

1除以8，算出第一位1之后，下一步接着用的是余数2。

第10000位，可不是多输出几位小数就行了。

这题咱们接着用余数往下算。

提示 2：每轮只算一位

digit是“数位”的意思，这里用来存当前算出的一位数字，值是0到9。

a、b、位数n已读入，余数从r = a % b开始：

r *= 10;
digit = r / b;
r %= b;

重复n轮，只输出最后一次digit；除尽后r为0，后面的位会怎样？

知识补充

例如 \(1\div8\)：余数 \(1\) 乘 \(10\)，商 \(1\) 余 \(2\)；余数 \(2\) 乘 \(10\)，商 \(2\) 余 \(4\)；余数 \(4\) 乘 \(10\)，商 \(5\) 余 \(0\)。所以小数是 \(0.125\)，再往后都是 \(0\)。

常见错误

不要用浮点数先算出整个小数再截取，第 \(10000\) 位远超浮点精度。余数变成 \(0\) 后，后面的每一位都是 \(0\)。

自测

输入：1 8 3 → 预期输出：5

输入：1 2 10000 → 预期输出：0

自己试试：分别选一个能除尽的分数、一个有循环小数的分数。

自己指定要查的位数，先用竖式或循环规律写下那个数字。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    int r = a % b, digit = 0;
    for (int i = 1; i <= n; i++) {
        r *= 10;
        digit = r / b;
        r %= b;
    }

    cout << digit;

    return 0;
}

1083：计算星期几 ¶

提示 1：星期只看除7的余数

从星期日开始过7天又回到星期日，必须算出完整\(a^b\)吗？

提示 2：边乘边取余

a、b已读入，先令a %= 7、t = 1：

t = t * a % 7;

重复b次，余数0对应Sunday、1对应Monday；自己补其他对应关系。

常见错误

数学的 \(a^b\) 不能写成 C++ 的 a ^ b。不要先求完整幂再取余，大整数溢出后再 % 7 不能补救。

自测

输入：2 3 → 预期输出：Monday

输入：7 1 → 预期输出：Sunday

方法一：分支输出星期

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    a %= 7;
    int t = 1;
    for (int i = 0; i < b; i++) {
        t *= a;
        t %= 7;
    }

    if (t == 0) cout << "Sunday";
    if (t == 1) cout << "Monday";
    if (t == 2) cout << "Tuesday";
    if (t == 3) cout << "Wednesday";
    if (t == 4) cout << "Thursday";
    if (t == 5) cout << "Friday";
    if (t == 6) cout << "Saturday";

    return 0;
}

方法二：数组查表（拓展）

#include <bits/stdc++.h>

using namespace std;

string ans[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

int main() {
    int a, b;
    cin >> a >> b;

    a %= 7;
    int t = 1;
    for (int i = 0; i < b; i++) {
        t *= a;
        t %= 7;
    }

    cout << ans[t];

    return 0;
}

1084：幂的末尾 ¶

提示 1：先确定要留哪三位

末三位等于对1000取余，但数值8要显示8还是008？

提示 2：每乘一次就剪掉前面部分

res = 1，底数a、指数b已读入：

res = res * a % 1000;

重复b次后补前导零；也可用printf("%03d", res)检查输出。

常见错误

不能漏掉 000、008 的前导零；也不能以为 long long 能装下任意大的幂。

自测

输入：2 3 → 预期输出：008

输入：10 3 → 预期输出：000

输入：2 10 → 预期输出：024

自己试试：自己选底数与指数，让结果末三位不足三位。

还能造出末三位全为零的情况吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int res = 1;
    for (int i = 1; i <= b; i++) {
        res *= a;
        res %= 1000;
    }

    if (res < 10) cout << "00" << res;
    else if (res < 100) cout << "0" << res;
    else cout << res;

    return 0;
}

第二节 while语句¶

2020：【例4.5】第几项 ¶

提示 1：超过，还是刚好达到

1加2刚好等于3，题目要求“超过3”，此时能停吗？

提示 2：项号先加一，再累加

long long sum = 0, n = 0，输入上限m后：

while (sum <= m) {
    n++;
    sum += n;
}

退出时n就是哪一项？用m为3手走一遍。

常见错误

“超过”是严格大于，等于还要继续。用 \(m=3\) 检查，应到第 \(3\) 项才超过。

自测

输入：3 → 预期输出：3

输入：1000 → 预期输出：45

自己试试：自己选一个项号，先手算前面所有项的和，把这个和作为输入。

题目要求“超过”，程序应该停在你选的项号吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long m;
    cin >> m;

    long long sum = 0, n = 0;
    while (sum <= m) {
        n++;
        sum += n;
    }

    cout << n;

    return 0;
}

2021：【例4.6】最大公约数 ¶

提示 1：公约数从哪里向下找

12和18的公约数能大于12吗？

方法一从较小值往下试，第一个符合的就是最大值。

提示 2：两个余数都要为0

if (m % i == 0 && n % i == 0) {
    cout << i;
    break;
}

m、n已读入，自己补i从min(m,n)递减的循环；辗转相除方法在后面作对照。

常见错误

枚举从 max(m, n) 开始会多做无用检查。辗转相除时先保存余数，再交换两数，不能丢掉旧的 b。

自测

输入：12 18 → 预期输出：6

输入：7 7 → 预期输出：7

输入：8 9 → 预期输出：1

自己试试：先选一个希望得到的公约数，再构造两个数。

怎样确认它确实是最大公约数，而不只是其中一个公约数？

方法一：从大到小枚举

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    for (int i = min(m, n); i >= 1; i--) {
        if (m % i == 0 && n % i == 0) {
            cout << i;
            break;
        }
    }

    return 0;
}

方法二：辗转相除

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }

    cout << a;

    return 0;
}

2022：【例4.7】最小n值 ¶

提示 1：恰好达到就能停

1、二分之一、三分之一逐项加，这题要求总和至少为m。

m为1时，加完第一项要继续吗？

提示 2：未达到时才加入下一项

sum用double初值0，n = 0：

while (sum < m) {
    n++;
    sum += 1.0 / n;
}

先增加n再除；和1087比较，循环条件为什么差一个等号？

常见错误

不要照搬 1087 的严格大于条件。\(m=1\) 时，本题第一项已经达到，应输出 \(1\)。

自测

输入：1 → 预期输出：1

输入：2 → 预期输出：4

参考代码

#include <bits/stdc++.h>

using namespace std;

double sum;

int main() {
    int m;
    cin >> m;

    int n = 0;
    while (sum < m) {
        n++;
        sum += 1.0 / n;
    }

    cout << n;

    return 0;
}

2023：【例4.8】数据统计 ¶

提示 1：没给个数，就边读边数

每次成功读到x，更新最大、最小、总和、个数四份记录。

提示 2：第一项用来定两个最值

总和sum、个数n初值为0，放在while (cin >> x)里：

if (n == 0) minn = maxn = x;
minn = min(minn, x);
maxn = max(maxn, x);

再补求和与n加一；全是负数时，为什么不能让最大值一直从0比较？

提示 3：输入结束后再算均值

用1.0 * sum / n保留小数，按最小、最大、均值顺序输出。

终端里最后还要结束输入，操作见下面知识补充。

知识补充

回车只是换行，不代表输入结束。

输入完最后一个数，先按回车到新行。

Windows：按 Ctrl+Z，再按回车。

macOS：按 Control+D。

常见错误

不要把第一个数当成个数 \(n\)。

程序还在等待时，先检查是否已经结束输入。

自测

输入：1 2 3 → 预期输出：1 3 2.000

输入：-5 → 预期输出：-5 -5 -5.000

自己试试：自己写几组数，分别把最小值、最大值放在开头和末尾。

每组先手算均值，输入完后记得结束输入。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int x, minn = 0, maxn = 0, n = 0;
    long long sum = 0;
    while (cin >> x) {
        if (n == 0) minn = maxn = x;
        minn = min(minn, x);
        maxn = max(maxn, x);
        sum += x;
        n++;
    }

    if (n > 0) printf("%d %d %.3lf", minn, maxn, 1.0 * sum / n);

    return 0;
}

1085：球弹跳高度的计算 ¶

提示 1：画出前两次落地的路程

第一次只向下走，第二次落地之前还走了上、下两段。

第十次落地后的反弹，要算进已走的总路程吗？

提示 2：第一次单列，后面加往返

初始高度h已读入，先令sum = h，第2到10次落地每轮：

h /= 2;
sum += 2 * h;

循环后再把h减半，才是第十次反弹高度；自己检查两次输出的含义。

常见错误

总路程不包含第十次落地后的向上路程；不能把这次反弹高度也加进去。拿 \(h=1\) 手算前两次，核对循环次数。

自测

输入：20，预期输出：

59.9219
0.0195312

输入：1，预期输出：

2.99609
0.000976562

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    double h;
    cin >> h;

    double sum = h;
    for (int i = 2; i <= 10; i++) {
        h /= 2;
        sum += 2 * h;
    }
    h /= 2;

    cout << sum << '\n' << h;

    return 0;
}

1086：角谷猜想 ¶

提示 1：先把一条等式写完整

从3开始，第一步是3*3+1=10，旧数3不能在输出前丢掉。

提示 2：输出后才更新

n用long long，奇数分支：

printf("%lld*3+1=%lld\n", n, n * 3 + 1);
n = n * 3 + 1;

仿照补偶数除2，循环条件是n != 1，结束后输出End。

常见错误

不能把 \(1\) 继续变成 \(4\)。不要只按初始输入的范围选择类型，过程中的数可能更大。

自测

输入：1，预期输出：

End

输入：3，预期输出：

3*3+1=10
10/2=5
5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
End

自己试试：自己选一个经过多次变化才到 \(1\) 的小整数。

把每一步等式写在纸上，逐行核对，而不只看最后的 End。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long n;
    cin >> n;

    while (n != 1) {
        if (n % 2 == 1) {
            printf("%lld*3+1=%lld\n", n, n * 3 + 1);
            n = n * 3 + 1;
        } else {
            printf("%lld/2=%lld\n", n, n / 2);
            n /= 2;
        }
    }
    cout << "End";

    return 0;
}

1087：级数求和 ¶

提示 1：相等时仍要继续

本题总和要严格大于k，和2022的“至少达到”不同。

用k为1检查：第一项加完能停吗？

提示 2：把等号留在继续条件里

double sum = 0、int n = 0：

while (sum <= k) {
    n++;
    sum += 1.0 / n;
}

先在纸上走到第一次超过，再核对输出的项号。

常见错误

循环条件不能写成 sum < k。用 \(k=1\) 检查，第一项等于 \(1\)，要加第二项才超过。

自测

输入：1 → 预期输出：2

输入：2 → 预期输出：4

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    cin >> k;

    double sum = 0;
    int n = 0;
    while (sum <= k) {
        n++;
        sum += 1.0 / n;
    }

    cout << n;

    return 0;
}

1088：分离整数的各个数 ¶

提示 1：每次只拿最右一位

120先输出0，去掉个位后剩12，再输出哪一位？

提示 2：取位和删位配成一组

正整数n已读入：

while (n) {
    cout << n % 10 << ' ';
    n /= 10;
}

如果漏掉n /= 10，循环会不会结束？

常见错误

不要把取余 % 10 和除法 / 10 写反。原数末尾的零也要输出，例如 \(120\) 要先输出 \(0\)。

自测

输入：120 → 预期输出：0 2 1

输入：1 → 预期输出：1

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    while (n) {
        cout << n % 10 << ' ';
        n /= 10;
    }

    return 0;
}

1089：数字反转 ¶

提示 1：反转结果是一个整数

120反转成21，末尾零不需要保留成前导零；负号仍在前面。

提示 2：把旧结果向左挪一位

n已读入，t = 0：

t = t * 10 + n % 10;
n /= 10;

放进while (n)；用-380手走，C++的负数取余会怎样参与计算？

常见错误

不要把反转理解成逐字符倒序输出，否则 \(120\) 会输出 021，负号也会跑到末尾。\(n=0\) 时答案仍是 \(0\)。

自测

输入：-380 → 预期输出：-83

输入：120 → 预期输出：21

输入：0 → 预期输出：0

自己试试：自己选一个末尾有零的负整数，再预测反转结果。

你希望这组数据同时检查哪两个地方？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int t = 0;
    while (n) {
        t = t * 10 + n % 10;
        n /= 10;
    }

    cout << t;

    return 0;
}

1090：含k个3的数 ¶

提示 1：两件事都要满足

数出k个3，还没完呢，能不能被19整除，也得检查。

先把原数m留下，用副本x拆位。

提示 2：拆一位就检查一位

x = m、cnt = 0：

while (x) {
    if (x % 10 == 3) cnt++;
    x /= 10;
}

结束后用m % 19 == 0 && cnt == k判断，别拿已经拆完的x去判整除。

常见错误

“恰好”不能写成 >= k。拆位会改变数值，不能等原数已经除成 \(0\) 才拿它判断整除。

自测

输入：43833 3 → 预期输出：YES

输入：39331 3 → 预期输出：NO

输入：43833 2 → 预期输出：NO

自己试试：先写一个恰好含指定个数 \(3\) 的数。

它是否还能被 \(19\) 整除，需要怎样检查？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, k;
    cin >> m >> k;

    int x = m, cnt = 0;
    while (x) {
        if (x % 10 == 3) cnt++;
        x /= 10;
    }

    if (m % 19 == 0 && cnt == k) cout << "YES";
    else cout << "NO";

    return 0;
}

第三节 do-while语句¶

第四节循环嵌套¶

2026：【例4.12】阶乘和 ¶

提示 1：每项先求阶乘，再加到和里

先写\(1!+2!+3!\)，总和与单项阶乘是同一个变量吗？

提示 2：内层乘积每项重来

外层i从1到n，当前阶乘先令t = 1：

for (int j = 1; j <= i; j++) t *= j;
s += t;

总和s从0开始，放在外层循环外；把t也放外面不重置会发生什么？

常见错误

累加总和从 \(0\) 开始，阶乘从 \(1\) 开始。两层循环的方法里，每次开始计算新阶乘时，要把乘积重新设成 \(1\)。

自测

输入：3 → 预期输出：9

输入：5 → 预期输出：153

输入：10 → 预期输出：4037913

自己试试：选一个较小的 \(n\)，分别手算 \(n!\) 和前 \(n\) 项阶乘和。

这两个结果能帮你分辨程序漏加了哪一项吗？

方法一：两层循环求阶乘和

#include <bits/stdc++.h>

using namespace std;

int s, n;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int t = 1;
        for (int j = 1; j <= i; j++) t *= j;

        s += t;
    }

    cout << s;

    return 0;
}

方法二：利用上一项阶乘

#include <bits/stdc++.h>

using namespace std;

int s, n;

int main() {
    cin >> n;

    int t = 1;
    for (int i = 1; i <= n; i++) {
        t *= i;
        s += t;
    }

    cout << s;

    return 0;
}

2027：【例4.13】三角形 ¶

提示 1：一行要打几个星号

行号从1开始，第1、2、3行分别有几个星号？

提示 2：内层管字符，外层管换行

固定第i行：

for (int j = 1; j <= i; j++) cout << '*';
cout << '\n';

外面再让i从1到n，换行应放在内层循环里还是外？

常见错误

换行应放在内层循环结束之后。放到内层会每个星号占一行；忘记换行则全部挤在一起。

自测

输入：1，预期输出：

输入：3，预期输出：

*
**
***

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) cout << '*';
        cout << '\n';
    }

    return 0;
}

2028：【例4.14】百钱买百鸡 ¶

提示 1：钱和只数要同时凑齐

公鸡x只、母鸡y只、小鸡z只，总共100只。

三只小鸡一元，小鸡数量先按3的倍数试。

提示 2：枚举后用两个条件筛选

x + y + z == 100 && 5 * x + 3 * y + z / 3 == 100

从单价推公鸡、母鸡数量上限；用三层循环枚举，符合条件才输出。

常见错误

小鸡三只一元，不能直接用整数 z / 3 代替准确价格而不检查 z % 3 == 0。允许某一种数量为 \(0\)，不要擅自从 \(1\) 开始。

自测

无需输入，预期输出：

方法一：三层枚举

#include <bits/stdc++.h>

using namespace std;

int main() {
    for (int x = 0; x <= 20; x++)
        for (int y = 0; y <= 33; y++)
            for (int z = 0; z <= 100; z += 3)
                if (x + y + z == 100 && 5 * x + 3 * y + z / 3 == 100) cout << x << ' ' << y << ' ' << z << '\n';

    return 0;
}

方法二：由总数确定小鸡数量

#include <bits/stdc++.h>

using namespace std;

int main() {
    for (int x = 0; x <= 20; x++)
        for (int y = 0; y <= 33; y++) {
            int z = 100 - x - y;
            if (z >= 0 && z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100) cout << x << ' ' << y << ' ' << z << '\n';
        }

    return 0;
}

2029：【例4.15】水仙花数 ¶

提示 1：先验一个熟悉的水仙花数

把153拆成1、5、3，三次方之和是多少？

提示 2：逐个三位数检查

i从100到999，分别取出百位a、十位b、个位c：

if (a * a * a + b * b * b + c * c * c == i) cout << i << '\n';

自己补取位表达式；这里不能把三次方写成a ^ 3。

常见错误

题目要求输出符合条件的数，不是只输出个数。立方写成 a * a * a，不能写 a ^ 3。

自测

无需输入，预期输出：

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    for (int i = 100; i <= 999; i++) {
        int a = i / 100, b = i / 10 % 10, c = i % 10;
        if (a * a * a + b * b * b + c * c * c == i) cout << i << '\n';
    }

    return 0;
}

2030：【例4.16】找素数 ¶

提示 1：找不到因数才说明是质数

先拿9试一下，除以2没除尽。

这就能说它是质数了吗？再拿3试试。

提示 2：遇到因数就否定

候选数i至少为2，先设prime = true，试除数j从2开始：

if (i % j == 0) {
    prime = false;
    break;
}

试到j <= i / j即可；把除数范围补进内层循环。

提示 3：每换一个候选数重新设标记

prime要在每个新i开始时重设；试除结束后再决定输出。

用区间1到4，检查1是否被错误输出。

常见错误

\(1\) 不是素数。检查约数时必须包含平方根，否则 \(4\)、\(9\) 会被误判；每个新候选数都要重新设置标记。

自测

输入：1 10，预期输出：

输入：8 9 → 预期输出：不输出任何字符

自己试试：自己选一小段合法区间，让里面包含一个质数的平方。

这个数能检查出试除范围漏掉端点的问题吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    for (int i = max(a, 2); i <= b; i++) {
        bool prime = true;
        for (int j = 2; j <= i / j; j++) {
            if (i % j == 0) {
                prime = false;
                break;
            }
        }
        if (prime) cout << i << '\n';
    }

    return 0;
}

2031：【例4.17】四位完全平方数 ¶

提示 1：先认出两组重复数字

四位数的千位等于百位，十位等于个位；先拿7744试一下。

提示 2：重复数位与平方都要通过

当前候选为i，先比较数位，符合后：

int x = sqrt(i);
if (x * x == i) cout << i << '\n';

为什么不能只看sqrt能算出一个小数就认定是完全平方数？

常见错误

不能只看 sqrt(i) 能否赋给整数，赋值本来就会截去小数；必须再乘回去检查。十位与个位可以是 \(0\)，不要自行排除。

自测

无需输入，预期输出：7744

方法一：枚举四位数

#include <bits/stdc++.h>

using namespace std;

int main() {
    for (int i = 1000; i <= 9999; i++) {
        if (i / 1000 == i / 100 % 10 && i / 10 % 10 == i % 10) {
            int x = sqrt(i);
            if (x * x == i) cout << i << '\n';
        }
    }

    return 0;
}

方法二：枚举平方根

#include <bits/stdc++.h>

using namespace std;

int main() {
    for (int x = 32; x <= 99; x++) {
        int i = x * x;
        if (i / 1000 == i / 100 % 10 && i / 10 % 10 == i % 10) cout << i << '\n';
    }

    return 0;
}

2032：【例4.18】分解质因数 ¶

提示 1：同一质因数可能除好几次

12除以2得6，6还能再除2，不能只判断一次。

提示 2：除尽当前因数再换下一个

当前因数i从2递增，原式左边先输出原来的n：

while (n % i == 0) {
    // 输出因数i，处理因数间的乘号
    n /= i;
}

第一次因数前不加星号，后面才加；为什么这里需要while而不是if？

知识补充

以 \(12\) 为例：先除以 \(2\) 剩 \(6\)，再除以 \(2\) 剩 \(3\)，最后的 \(3\) 是质数，因此 \(12=2\times2\times3\)。

常见错误

这里输出的是全部质因子，不是 1098 的较大质因子。用质数输入检查剩余因子的处理，用 \(8\) 检查重复因子。

自测

输入：12 → 预期输出：12=2*2*3

输入：13 → 预期输出：13=13

输入：8 → 预期输出：8=2*2*2

自己试试：分别用一个质数和一个质数的幂作输入，数值要在题目范围内。

这两类数据各能检查分解过程中的哪一步？

方法一：从小到大反复试除

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    bool flag = false;
    cout << n << "=";
    for(int i = 2; i <= n; i++) {
        while(n % i == 0) {
            if (flag) cout << "*";
            flag = true;

            cout << i;
            n /= i;
        }
    }

    return 0;
}

方法二：只试到剩余数的平方根

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    bool flag = false;
    printf("%d=", n);
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            if (flag) printf("*");
            printf("%d", i);
            n /= i;
            flag = true;
        }
    }

    if (n > 1) {
        if (flag) printf("*");
        printf("%d", n);
    }

    return 0;
}

2033：【例4.19】阶乘之和 ¶

提示 1：只保留最后六位

不必求出巨大的阶乘，乘积和总和都可以在每步对一百万取余。

提示 2：当前阶乘和总和分别更新

常量MOD = 1000000，先令long long t = 1、ret = 0：

t = t * i % MOD;
ret = (ret + t) % MOD;

这两句顺序能交换吗？先用前三项试一遍。

知识补充：为什么只算到25

\(25!\)中，5、10、15、20各提供一个因子5，25提供两个，共有6个。

因子2更多，配对后至少有6个10，因此\(25!\)是\(10^6\)的倍数。

后面的阶乘也都是\(10^6\)的倍数，不再改变最后六位。

常见错误

不要先让整数溢出，再取余。也不要把“末六位”直接理解成固定宽度输出，样例 \(n=10\) 的答案是 37913。

自测

输入：10 → 预期输出：37913

输入：3 → 预期输出：9

输入：25 → 预期输出：940313

自己试试：自己选一对相邻的合法项数，让新增的阶乘是 \(10^6\) 的倍数。

先预测两次输出是否相同，再运行。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000;

int main() {
    int n;
    cin >> n;

    long long t = 1;
    int ret = 0;
    for (int i = 1; i <= min(n, 25); i++) {
        t = t * i % MOD;
        ret = (ret + t) % MOD;
    }

    cout << ret;

    return 0;
}

1091：求阶乘的和 ¶

提示 1：新阶乘能接着上一个乘

已算出\(3!\)，求\(4!\)还要从1重乘吗？

提示 2：先更新阶乘，再加入总和

t = 1、sum = 0，i依次从1到n：

t *= i;
sum += t;

用n为2走两轮，若先加后乘，漏了哪一项？

常见错误

先更新阶乘，再加入总和。顺序反了就会少算最后一项；只输出 t 则变成了求阶乘。

自测

输入：2 → 预期输出：3

输入：5 → 预期输出：153

输入：11 → 预期输出：43954713

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int t = 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        t *= i;
        sum += t;
    }

    cout << sum;

    return 0;
}

1092：求出e的值 ¶

提示 1：后一项等于前一项除几

先写1、1、二分之一、六分之一，分别对应从0阶乘开始的倒数。

提示 2：别先算巨大阶乘

double term = 1, sum = 1已经计入第0项，i从1到n：

term /= i;
sum += term;

n为0时循环不执行，结果应是多少？

常见错误

开头的 \(1\) 不能漏掉。若计算阶乘再取倒数，必须留意类型；直接维护 double 的倒数更省事。

自测

输入：0 → 预期输出：1.0000000000

输入：10 → 预期输出：2.7182818011

自己试试：自己选相邻的两个合法项数。

两次结果在保留十位小数之前，应当相差哪一项？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    double term = 1, sum = 1;
    for (int i = 1; i <= n; i++) {
        term /= i;
        sum += term;
    }

    printf("%.10lf", sum);

    return 0;
}

1093：计算多项式的值 ¶

提示 1：幂次从常数项开始

多项式\(1+x+x^2+\cdots+x^n\)一共有几项？

常数项1先放入sum，当前幂t也从1开始。

提示 2：每次多乘一个x

x已读为double，循环n轮：

t *= x;
sum += t;

用x为2、n为3逐项核对，别漏最前面的1。

常见错误

不要每一项都从头乘一次，也不要漏掉常数项 \(1\)。输入顺序是 x、n；数学乘方不能写成 ^。

自测

输入：2.0 4 → 预期输出：31.00

输入：1.0 3 → 预期输出：4.00

自己试试：在题目范围内取 \(x=1\)，自己选一个项数。

不逐项乘方，能直接写出预期结果吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

double sum = 1.0;

int main() {
    int n;
    double x;
    cin >> x >> n;

    double t = 1.0;
    for (int i = 1; i <= n; i++) {
        t *= x;
        sum += t;
    }

    printf("%.2lf", sum);

    return 0;
}

1094：与7无关的数 ¶

提示 1：两种与7有关的数都排除

14不含数字7，但能被7整除；17含7却不能被7整除。

这两种都不能加平方。

提示 2：在本题范围内拆十位个位

i从1到n，按本题的数据范围检查：

if (i % 7 != 0 && i / 10 != 7 && i % 10 != 7) sum += i * i;

sum从0开始；如果将来范围扩到三位数，这个数位判断还能照搬吗？

常见错误

三个“无关”条件用 &&，不是 ||。例如 \(17\) 不被 \(7\) 整除，但含有数字 \(7\)，仍然不能计入。

自测

输入：7 → 预期输出：91

输入：8 → 预期输出：155

自己试试：自己找一个含数字 \(7\)、却不能被 \(7\) 整除的两位数。

用它作上限时，怎样确认程序没有把它的平方加进去？

方法一：直接检查十位和个位

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 1; i <= n; i++)
        if (i % 7 != 0 && i / 10 != 7 && i % 10 != 7) sum += i * i;

    cout << sum;

    return 0;
}

方法二：循环检查各个数位

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int x = i;
        bool has7 = false;
        while (x) {
            if (x % 10 == 7) has7 = true;
            x /= 10;
        }
        if (i % 7 != 0 && !has7) sum += i * i;
    }

    cout << sum;

    return 0;
}

1095：数1的个数 ¶

提示 1：一个数里可能有两个1

11给答案贡献1次还是2次？

枚举整数之后，还需要逐位检查。

提示 2：拆副本，不改外层编号

外层i从1到n，让x = i：

while (x) {
    if (x % 10 == 1) cnt++;
    x /= 10;
}

cnt在所有循环外从0开始；为什么不能直接反复除i？

常见错误

拆位不能直接修改外层循环变量 i。遇到 \(11\) 后只加一次，会把“出现次数”算成“整数个数”。

自测

输入：1 → 预期输出：1

输入：11 → 预期输出：4

自己试试：自己找一个含有两个数字 \(1\) 的数，并用它作上限。

与上限少 \(1\) 的结果比较，计数应增加多少？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x) {
            if (x % 10 == 1) cnt++;
            x /= 10;
        }
    }

    cout << cnt;

    return 0;
}

1096：数字统计 ¶

提示 1：区间端点也要计入

区间20到22，先分别数三个整数里的数字2。

提示 2：每个数独立拆位

外层枚举l到r，复制x = i后：

if (x % 10 == 2) cnt++;
x /= 10;

用while重复拆x，计数器cnt从0开始并放在外层循环外。

常见错误

左右端点都要包含。每个整数可能贡献多个 \(2\)，不能找到一个就 break。

自测

输入：2 2 → 预期输出：1

输入：20 22 → 预期输出：4

自己试试：自己选一个含有多个数字 \(2\) 的合法整数，让左右端点都等于它。

这时数的是整数个数，还是数字出现次数？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int L, R;
    cin >> L >> R;

    int cnt = 0;
    for (int i = L; i <= R; i++) {
        int x = i;
        while (x) {
            if (x % 10 == 2) cnt++;
            x /= 10;
        }
    }

    cout << cnt;

    return 0;
}

1097：画矩形 ¶

提示 1：先画出空心矩形的边

用3行4列画一遍，哪些位置一定要输出字符？

只有一行或一列时，还有内部空格吗？

提示 2：每格只选择一种字符

行i从1到n、列j从1到m，已读绘图字符c和标志flag：

if (flag != 0 || i == 1 || i == n || j == 1 || j == m) cout << c;
else cout << ' ';

每行结束换行，别在每个字符后换行。

常见错误

非零表示实心，不能只认 flag == 1。空心内部应输出空格，不能跳过位置；高和宽也不要颠倒。

自测

输入：3 4 * 0，预期输出：

****
*  *
****

输入：3 3 # 2，预期输出：

###
###
###

自己试试：自己选择题目允许的最小高度和宽度，画出空心矩形。

再保持尺寸不变，改成实心，哪些位置应该变化？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, flag;
    char c;
    cin >> n >> m >> c >> flag;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (flag != 0 || i == 1 || i == n || j == 1 || j == m) cout << c;
            else cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}

1098：质因数分解 ¶

提示 1：两个质数乘积，先找小的

77由7和11相乘，若从2开始试，第一个因数是哪一个？

题面保证是两个不同质数的乘积，不必处理一般合数。

提示 2：找到一个，另一个用除法求

n已读入，i从2试到i <= n / i：

if (n % i == 0) {
    cout << n / i;
    break;
}

为什么此时输出的是较大的那个质因数？

常见错误

不要输出第一个除数本身，题目要较大的质因子。这里能直接输出商，是因为题面保证恰好是两个不同质数的乘积，不能随意推广到所有合数。

自测

输入：6 → 预期输出：3

输入：77 → 预期输出：11

自己试试：自己选两个不同的小质数，相乘作为输入。

打乱你选择它们的先后顺序，预期输出会改变吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            cout << n / i;
            break;
        }
    }

    return 0;
}

1099：第n小的质数 ¶

提示 1：名次不是数值

第5个质数是11，不是数字5；先列前五个质数。

提示 2：试到一个质数才增加名次

候选x从2开始，cnt从0开始；先通过试除判断prime。

if (prime) {
    cnt++;
    if (cnt == n) break;
}

它外面需要不断增加候选数的循环，换一个数，就重新设一次prime，别把上一个数的判断带过来。

常见错误

\(1\) 不是质数。试除要包含平方根；每个候选数开始时，都要重置质数标记。

自测

输入：1 → 预期输出：2

输入：5 → 预期输出：11

输入：10000 → 预期输出：104729

自己试试：自己列出前几个质数，选两个相邻的名次作输入。

它们的差总是 \(1\) 吗，这能检查程序的哪种误解？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0, x = 2;
    while (true) {
        bool prime = true;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            cnt++;
            if (cnt == n) break;
        }
        x++;
    }

    cout << x;

    return 0;
}

1100：金币 ¶

提示 1：发几枚和发几天一起变

先写前六天收入：1、2、2、3、3、3。

第i组每天发i枚，一共持续几天？

提示 2：按组发，但到天数就停

n表示还剩几天，sum从0开始；第i组可写：

for (int j = 1; j <= i && n; j++) {
    sum += i;
    n--;
}

外层让i从1增加；内层为什么还要检查n？

常见错误

第 \(i\) 组是每天发 \(i\) 枚，发 \(i\) 天，不是整组只发 \(i\) 枚。最后一组可能只发一部分，用第 \(4\) 天检查。

自测

输入：1 → 预期输出：1

输入：4 → 预期输出：8

输入：6 → 预期输出：14

自己试试：先找一组金币刚好发完的那一天。

自己测试它的前一天和后一天，分别手算会少发、多发多少枚。

参考代码

#include <bits/stdc++.h>

using namespace std;

int sum;

int main() {
    int n;
    cin >> n;

    for (int i = 1; n; i++)
        for (int j = 1; j <= i && n; j++) sum += i, n--;

    cout << sum;

    return 0;
}

1101：不定方程求解 ¶

提示 1：零也可以是一组解的坐标

对\(2x+3y=6\)，把x为0时的情况也列出来。

x、y要求非负，枚举起点不要写成1。

提示 2：先圈定有限范围

a、b、c已读入，x最多c / a，y最多c / b。

if (a * x + b * y == c) cnt++;

cnt从0开始，自己补两层循环；每组x、y只枚举一次。

常见错误

非负包括 \(0\)，不能从 \(1\) 开始。第二种方法必须控制 x <= c / a，保证剩余量非负；不用再枚举 \(y\)。

自测

输入：2 3 6 → 预期输出：2

输入：4 6 5 → 预期输出：0

输入：1 1 3 → 预期输出：4

自己试试：先选合法的 \(a,b\) 和一对非负整数 \(x,y\)，算出正整数 \(c\)。

这能保证至少有一组解，但你怎样找出可能遗漏的其他解？

方法一：枚举两个未知数

#include <bits/stdc++.h>

using namespace std;

int cnt;
int a, b, c;

int main() {
    cin >> a >> b >> c;

    for (int x = 0; x <= c / a; x++)
        for (int y = 0; y <= c / b; y++)
            if (a * x + b * y == c) cnt++;

    cout << cnt;

    return 0;
}

方法二：用余数确定另一个未知数

#include <bits/stdc++.h>

using namespace std;

//ax+by=c
int a, b, c;
int cnt;

int main() {
    cin >> a >> b >> c;

    for (int x = 0; x <= c / a; x++)
        if ((c - a * x) % b == 0) cnt++;

    cout << cnt;

    return 0;
}

第四章 循环结构的程序设计¶

基础数学知识¶

第一节 for语句¶

第二节 while语句¶

第三节 do-while语句¶

第四节 循环嵌套¶

第四章循环结构的程序设计¶

第四节循环嵌套¶