C++ 信息学奥赛入门系列教材——第14课 循环结构综合应用
- 2026-11-21 23:29:48
本课学习目标:
1. 掌握角谷猜想(冰雹猜想)的算法实现
2. 学会用逐位取数法解决数字统计问题
3. 理解NOIP真题的解题思路
4. 掌握素数判定的基本方法和优化
一、角谷猜想(冰雹猜想)
1.1 题目描述
角谷猜想(又称冰雹猜想)是一个著名的数学猜想:
对于任意一个正整数:
● 如果它是奇数 → 乘3加1(n = n×3+1)
● 如果它是偶数 → 除以2(n = n/2)
不断重复这个过程,最终一定会得到1。
例如,从5开始:
5(奇数)→ 5×3+1=16 → 16/2=8 → 8/2=4 → 4/2=2 → 2/2=1 → 结束
过程:5 → 16 → 8 → 4 → 2 → 1,共5步。
编程要求:
输入一个正整数n(n ≤ 2,000,000),输出从n到1的每一步计算过程。
如果输入为1,直接输出"End"。
1.2 算法分析
循环次数不确定(不同的数需要的步骤不同),所以用 while 循环最合适。
循环条件:n != 1(只要还没到1就继续)

1.3 参考代码
#include<bits/stdc++.h>using namespace std;intmain(){long long n; // 用long long防止中间值溢出cin >> n;while(n != 1) { // 当n不等于1时继续循环if(n % 2 != 0) { // 判断n是否为奇数cout << n << "*3+1=" << n*3+1 << endl;n = n * 3 + 1; // 更新n的值} else { // n是偶数cout << n << "/2=" << n/2 << endl;n = n / 2; // 更新n的值}}cout << "End" << endl; // 最后输出Endreturn 0;}
1.4 易错点
⚠ 为什么用 long long?
奇数乘3加1后可能变得很大。例如2,000,000 → 6,000,001 → 18,000,004 → ...
虽然int最大约21亿,但某些数的中间值可能超过int范围,用long long更安全。
⚠ 输入为1的情况:
while(n != 1) 天然处理了这种情况——n已经是1了,循环一次都不执行,直接输出"End"。
二、NOIP普及组 数字统计
2.1 题目描述
请统计某个给定范围 [L, R] 的所有整数中,数字2出现的次数。
例如范围 [2, 22]:
● 数字2:2出现1次
● 数字12:2出现1次
● 数字20:2出现1次
● 数字21:2出现1次
● 数字22:2出现2次
共 1+1+1+1+2 = 6 次。
输入格式:两个正整数 L 和 R(1 ≤ L ≤ R ≤ 100000)
输出格式:数字2出现的总次数
样例输入:2 100
样例输出:20
2.2 核心技巧:逐位取数法
如何检查一个数中每一位是否为2?这就需要【逐位取数法】。
方法:反复做两步操作——
1. t % 10 → 取出个位数字
2. t = t / 10 → 去掉个位(整数除法)
重复直到 t 变为0。
以 t = 234 为例:
第1轮:t%10=4 → 检查4是否为2 → t=234/10=23
第2轮:t%10=3 → 检查3是否为2 → t=23/10=2
第3轮:t%10=2 → 检查2是否为2 → 是!计数+1 → t=2/10=0
结束。
2.3 参考代码
#include<bits/stdc++.h>using namespace std;intmain(){int L, R, ans = 0;cin >> L >> R;for(int i = L; i <= R; i++) { // 外层:遍历L到R的每个数int t = i; // 临时变量保存当前数while(t > 0) { // 内层:逐位检查if(t % 10 == 2) // 个位是否为2ans++;t = t / 10; // 去掉个位}}cout << ans;return 0;}
注意:这里用了 for + while 的嵌套!外层是for(已知范围),内层是while(逐位取数)。
三、NOIP2015普及组 金币
3.1 题目描述
国王将金币作为工资发放给骑士:
● 第1天:骑士收到1枚金币
● 第2~3天:每天收到2枚金币(共2天)
● 第4~6天:每天收到3枚金币(共3天)
● 第7~10天:每天收到4枚金币(共4天)
● ...以此类推
规律:连续n天每天收到n枚金币后,接下来连续n+1天每天收到n+1枚。
请计算前k天一共获得多少金币。
输入格式:一个正整数k(1 ≤ k ≤ 10000)
输出格式:前k天获得的金币总数
样例输入:6
样例输出:14
解释:第1天1枚 + 第2、3天各2枚 + 第4、5、6天各3枚 = 1+2+2+3+3+3 = 14
3.2 算法分析
这是一道经典的【模拟题】——按照题目描述的规则一步步模拟。
用双重循环:
● 外层循环i:表示当前每天发i枚金币(i从1开始递增)
● 内层循环j:表示这一轮要连续发i天(j从1到i)
● 计数器:day记录总天数,coin累计金币数
● 当天数达到k时,输出答案并结束程序
3.3 参考代码
#include<bits/stdc++.h>using namespace std;intmain(){int k, coin = 0, day = 0;cin >> k;for(int i = 1; ; i++) { // 外层:当前发i枚金币,无终止条件for(int j = 1; j <= i; j++) { // 内层:连续发i天coin += i; // 每天加i枚金币day++; // 天数+1if(day == k) { // 达到k天cout << coin << endl;return 0; // 直接结束程序}}}return 0;}
为什么for(;;)没有第二个表达式?
因为我们不知道k天会经历多少轮,但一定能达到k天。
用 return 0 直接结束程序,比设置标志变量更简洁。
四、素数判定
4.1 什么是素数?
素数(质数):大于1的自然数,除了1和它本身,不能被其他任何数整除。
例如:2, 3, 5, 7, 11, 13, 17, 19, 23, 29...
不是素数的叫合数:4=2×2, 6=2×3, 8=2×4, 9=3×3...
注意:
● 1 不是素数也不是合数
● 2 是最小的素数,也是唯一的偶素数
4.2 如何判断n是否为素数?
基本思路:用2到n-1的每个数去除n,如果都不能整除,就是素数。
优化:只需检查到√n(根号n)即可!
原因:如果 n = a×b,且 a > √n,那么 b = n/a < √n。
小的因子b一定已经在前面被检查过了。
所以循环条件写成 i*i <= n 就够了。

4.3 参考代码
#include<bits/stdc++.h>using namespace std;intmain(){int n;cin >> n;if(n <= 1) { // 小于等于1不是素数cout << n << " 不是素数" << endl;return 0;}bool isPrime = true; // 假设n是素数for(int i = 2; i * i <= n; i++) { // 检查到√n即可if(n % i == 0) { // 能被整除isPrime = false; // 不是素数break; // 不用再查了}}if(isPrime)cout << n << " 是素数" << endl;elsecout << n << " 不是素数" << endl;return 0;}
4.4 易错点
⚠ n=2的情况:
i*i <= n 即 2*2=4 <= 2 为假,循环不执行,isPrime保持true → 2是素数。正确!
⚠ n=4的情况:
i=2时,4%2==0 → isPrime=false → 4不是素数。正确!
五、综合编程训练
训练1:输出1~100之间的所有素数
思路:双重循环——外层遍历1~100,内层判断每个数是否为素数。
#include<bits/stdc++.h>using namespace std;intmain(){for(int n = 2; n <= 100; n++) {bool isPrime = true;for(int i = 2; i * i <= n; i++) {if(n % i == 0) {isPrime = false;break;}}if(isPrime)cout << n << " ";}return 0;}
训练2:水仙花数
水仙花数:一个三位数,它的每位数字的立方和等于它本身。
例如:153 = 1³ + 5³ + 3³ = 1 + 125 + 27 = 153
思路:遍历100~999,逐个取出百位、十位、个位判断。
#include<bits/stdc++.h>using namespace std;intmain(){for(int n = 100; n <= 999; n++) {int a = n / 100; // 百位int b = n / 10 % 10; // 十位int c = n % 10; // 个位if(a*a*a + b*b*b + c*c*c == n)cout << n << " ";}return 0;}
训练3:统计数字出现次数
思路:外层遍历范围,内层用逐位取数法检查每一位。
#include<bits/stdc++.h>using namespace std;intmain(){int L, R, digit, ans = 0;cin >> L >> R >> digit;for(int i = L; i <= R; i++) {int t = i;while(t > 0) {if(t % 10 == digit)ans++;t /= 10;}}cout << ans;return 0;}