算法刷题笔记「Day 2.5｜循环进阶补充篇」

Day 2.5｜循环进阶补充篇：break、flag 与 pow 的边界

• 🎯 前言
• 一、break 到底跳出哪一层：数字 9（牛客）
• • 题目
  • 三个错误版本，三个典型坑
  • 正确写法：外层枚举 + 内层逐位 + 内层 break
  • 拓展：同一道题的三种境界
  • 深度思考：break 为什么只跳一层？这与 goto 和"提前退出"的设计哲学有什么关系？
• 二、迭代替代 pow：球弹跳高度（洛谷 B2076）
• • 题目
  • 方案一：临时项不断除以 2（最推荐）
  • 方案二：维护分母不断乘 2
  • 方案三：纯数学降维（O(1)，直接套等比数列）
  • 为什么不用 pow？
  • 深度思考：为什么浮点递推（term/=2）比闭式公式（pow/幂）有时更可靠？这与数值稳定性有关吗？
• 三、统计一个正整数有几位：三种循环的选型
• • 题目
  • 三种写法
  • 三种循环的选型原则
  • 深度思考：数位剥离 n /= 10 为什么能统计位数？进制的本质是什么？
• 四、flag 状态翻转：交错调和级数（洛谷 B2070）
• • 题目
  • 我的第一版：用 pow(-1, n-1)
  • 参考版：一个 flag 翻转解决符号
  • 深度思考：flag = -flag 本质上是在做什么？为什么说它是一个二态自动机？
• 📝 总结

当你能用一个变量的翻转替代一次幂运算，你就开始从"会写循环"走向"会设计状态"了。

🎯 前言

Day 2 我把循环的"状态管理"理顺了，刷完之后又攒下四道"边角料"题——本来以为是散的，写完发现它们其实在共同回答一个更尖锐的问题：循环和数学，到底该各管哪一段？ 这一篇是 Day 2 的补充进阶，我把它编号成 Day 2.5。四道题分别是牛客的「数字 9」（break 的作用域 + 三种境界）、洛谷 B2076（球弹跳，等比数列）、一道统计位数的小题（三种循环选型），以及洛谷 B2070（交错调和级数，flag 翻转干掉 pow）。它们把 Day 2 没讲透的 break 跳出层级、循环变量副本、状态翻转、库函数性能这几个点全补上了。

#mermaid-svg-9Yvy43cDlJU22XGc{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-9Yvy43cDlJU22XGc .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-9Yvy43cDlJU22XGc .error-icon{fill:#552222;}#mermaid-svg-9Yvy43cDlJU22XGc .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-9Yvy43cDlJU22XGc .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-9Yvy43cDlJU22XGc .marker{fill:#333333;stroke:#333333;}#mermaid-svg-9Yvy43cDlJU22XGc .marker.cross{stroke:#333333;}#mermaid-svg-9Yvy43cDlJU22XGc svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-9Yvy43cDlJU22XGc p{margin:0;}#mermaid-svg-9Yvy43cDlJU22XGc .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-9Yvy43cDlJU22XGc .cluster-label text{fill:#333;}#mermaid-svg-9Yvy43cDlJU22XGc .cluster-label span{color:#333;}#mermaid-svg-9Yvy43cDlJU22XGc .cluster-label span p{background-color:transparent;}#mermaid-svg-9Yvy43cDlJU22XGc .label text,#mermaid-svg-9Yvy43cDlJU22XGc span{fill:#333;color:#333;}#mermaid-svg-9Yvy43cDlJU22XGc .node rect,#mermaid-svg-9Yvy43cDlJU22XGc .node circle,#mermaid-svg-9Yvy43cDlJU22XGc .node ellipse,#mermaid-svg-9Yvy43cDlJU22XGc .node polygon,#mermaid-svg-9Yvy43cDlJU22XGc .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-9Yvy43cDlJU22XGc .rough-node .label text,#mermaid-svg-9Yvy43cDlJU22XGc .node .label text,#mermaid-svg-9Yvy43cDlJU22XGc .image-shape .label,#mermaid-svg-9Yvy43cDlJU22XGc .icon-shape .label{text-anchor:middle;}#mermaid-svg-9Yvy43cDlJU22XGc .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-9Yvy43cDlJU22XGc .rough-node .label,#mermaid-svg-9Yvy43cDlJU22XGc .node .label,#mermaid-svg-9Yvy43cDlJU22XGc .image-shape .label,#mermaid-svg-9Yvy43cDlJU22XGc .icon-shape .label{text-align:center;}#mermaid-svg-9Yvy43cDlJU22XGc .node.clickable{cursor:pointer;}#mermaid-svg-9Yvy43cDlJU22XGc .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-9Yvy43cDlJU22XGc .arrowheadPath{fill:#333333;}#mermaid-svg-9Yvy43cDlJU22XGc .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-9Yvy43cDlJU22XGc .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-9Yvy43cDlJU22XGc .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-9Yvy43cDlJU22XGc .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-9Yvy43cDlJU22XGc .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-9Yvy43cDlJU22XGc .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-9Yvy43cDlJU22XGc .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-9Yvy43cDlJU22XGc .cluster text{fill:#333;}#mermaid-svg-9Yvy43cDlJU22XGc .cluster span{color:#333;}#mermaid-svg-9Yvy43cDlJU22XGc div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-9Yvy43cDlJU22XGc .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-9Yvy43cDlJU22XGc rect.text{fill:none;stroke-width:0;}#mermaid-svg-9Yvy43cDlJU22XGc .icon-shape,#mermaid-svg-9Yvy43cDlJU22XGc .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-9Yvy43cDlJU22XGc .icon-shape p,#mermaid-svg-9Yvy43cDlJU22XGc .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-9Yvy43cDlJU22XGc .icon-shape .label rect,#mermaid-svg-9Yvy43cDlJU22XGc .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-9Yvy43cDlJU22XGc .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-9Yvy43cDlJU22XGc .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-9Yvy43cDlJU22XGc :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

循环与数学的边界

数字9break作用域

B2076球弹跳/等比

统计位数三种循环

B2070flag翻转

break只跳内层

副本+容斥+数位DP

term/=2迭代

pow溢出陷阱

while次数未知

循环选型

flag=-flag

替代pow(-1,n)

一、break 到底跳出哪一层：数字 9（牛客）

题目

1~2019 中，有多少个数包含数字 9？答案是 544。包含数字 9 指某一位是 9，比如 2019、199。

这题我连错三次，错误一个比一个隐蔽，值得完整复盘。

三个错误版本，三个典型坑

错误 1：只检查了一个数。

cin >> n;
while (n) {
if (n % 10 == 9) count++;
n /= 10;
}

题目范围写死在 1~2019，根本没有输入，cin >> n 就不该存在；而且只拆了一个数，没有遍历整个区间；更糟的是没有 break，像 199 这种有两个 9 的数会被计数两次。

错误 2：break 放错了循环。

for (int i = 0; i < n; i++) {
if (i % 10 == 9) {
count++;
break; // 跳出的是整个外层 for！
}
}

break 写在外层 for 里，遇到第一个数（i=9）就把整个统计提前终止了，结果恒为 1；而且 i % 10 只看个位，90、199 这些 9 在其他位的数全漏掉。

错误 3：判断变量写错。

for (int i = 0; i < 2019; i++) {
int n = i;
while (n) {
if (i % 10 == 9) { ... } // 应为 n % 10
n /= 10;
}
}

n /= 10 一直在剥离 n 的个位，判断却写的是 i % 10，每一轮查的都是同一个值（i 的个位），剥离等于白做；另外 i < 2019 还漏掉了 2019 本身（它含 9），应是 i <= 2019。

正确写法：外层枚举 + 内层逐位 + 内层 break

int count = 0;
for (int i = 1; i <= 2019; i++) { // 外层：遍历每个数
int n = i; // 备份 i，避免破坏循环变量
while (n) { // 内层：逐位检查
if (n % 10 == 9) {
count++;
break; // 只跳出内层 while，每个数最多计 1 次
}
n /= 10; // 去掉个位，查下一位
}
}
cout << count << endl; // 544

这里有四个必须刻进肌肉的点：

拓展：同一道题的三种境界

题做对了不算完，我还收集了三种层层递进的解法：

境界一：数学容斥（O(位数)，不算出每个数）

不去枚举，而是直接算"不含 9 的数有几个"，再用总数减。逐位用排列组合：

int total = 2019, no_nine = 0;
no_nine += 8; // 1 位数(1~9)不含9：1~8，共 8
no_nine += 8 * 9; // 2 位数：十位 8 种(1~8)，个位 9 种(0~8)
no_nine += 8 * 9 * 9; // 3 位数(100~999)
no_nine += 9 * 9 * 9; // 1000~1999：后三位均不含9
no_nine += 1 * 2 * 9; // 2000~2019：百位只能0，十位0~1两种，个位0~8九种
cout << total – no_nine; // 544

境界二：字符串法（代码最简洁，工程首选）

把数字转成字符串，直接 find('9')，循环都不用嵌套：

#include <string>
int count = 0;
for (int i = 1; i <= 2019; ++i) {
string s = to_string(i);
if (s.find('9') != string::npos) count++;
}

境界三：数位 DP（通用性最强，竞赛终极武器）

如果范围变成 1 到 10^100，或者题目改成"不含 4 但包含 9"，暴力和简单容斥都失效。这时要用记忆化 DFS，按位枚举，用 dp[pos][limit][hasNine] 记录"处理到第 pos 位、是否贴着上界、之前是否出现过 9"的方案数。它是后续数位统计问题的通用框架，这里先埋个伏笔。

深度思考：break 为什么只跳一层？这与 goto 和"提前退出"的设计哲学有什么关系？

核心在于**结构化程序设计（structured programming）**对控制流的约束。

C/C++ 规定 break 只终止最内层的 for/while/switch，这是一种刻意的"作用域受限"设计。Dijkstra 在《Go To Statement Considered Harmful》里主张控制流应当可静态追踪：如果一条语句能跳到任意位置，读者就无法在局部范围内推理程序状态。break 只跳一层，使得它的影响半径被严格限定在当前循环块内，这与 Day 2 讲的"for 循环变量有块作用域"是同一种哲学——让破坏性操作的爆炸半径最小化。

三种循环退出方式的对比：

正因为 break 只有一层能力，"跳出多层循环"才需要专门手段：要么用一个 bool found 标志位让外层条件也变假，要么把逻辑抽进函数用 return，要么（在被严格限制的场景下）goto 到统一的清理标签——Linux 内核里大量的 goto err 就是后一种的经典用法。

📖 结论：break 的"只跳一层"不是缺陷，而是把控制流约束在可局部推理范围内的设计；要表达"个体结束"用 break，"整体结束"用 return，跨层退出才考虑标志位或 goto。

二、迭代替代 pow：球弹跳高度（洛谷 B2076）

题目

球从高度 h 落下，每次反弹到原高度的一半再落下。求它第 10 次落地时共经过多少米，以及第 10 次反弹多高。

第一次落地只经过 h（下落，没有反弹）；之后每一次落地，都包含"反弹上去 + 落下来"两段。

方案一：临时项不断除以 2（最推荐）

double h;
cin >> h;
double total = h; // 第一次下落
double term = h / 2.0; // 第一项：h/2
for (int i = 1; i <= 9; i++) {
total += 2 * term; // 弹起 + 落下
term /= 2.0; // 下一项 h/4, h/8 …
}
double tenth_bounce = term / 2.0; // 第 10 次反弹高度
cout << total << endl << tenth_bounce << endl;

关键还是 Day 2 的滚动思想：不每次去算 h / pow(2, i)，而是让 term 记住当前高度，每轮 /2.0 自动滚到下一项。

方案二：维护分母不断乘 2

double divisor = 2.0;
for (int i = 1; i <= 9; i++) {
total += 2 * (h / divisor);
divisor *= 2.0; // 分母 2, 4, 8 …
}
double tenth_bounce = h / divisor; // 循环结束 divisor = 1024 = 2^10

方案三：纯数学降维（O(1)，直接套等比数列）

这本质是个等比数列求和。括号内 h/2 + h/4 + … + h/2^9 是首项 h/2、公比 1/2 的等比数列，可以直接化简：

double total = h * 767.0 / 256.0; // 总路程的最简公比系数
double tenth_bounce = h / 1024.0; // h / 2^10

为什么不用 pow？

这题最容易想到 pow(2, i)，但它有两个实打实的问题：一是性能，pow 是通用浮点函数（要处理任意实数指数），函数调用和内部对数/指数运算的开销远大于一次除法；二是溢出/精度，假如题目改成第 1000 次落地，pow(2,1000) 直接把 double 撑爆变成 inf，而方案一的 term /= 2.0 只会让项越来越小、永远稳定。

我顺手把这一类"数列求和"系统整理了一下：

深度思考：为什么浮点递推（term/=2）比闭式公式（pow/幂）有时更可靠？这与数值稳定性有关吗？

需要区分算法稳定性与表达式求值范围两个层面。

表面上看闭式公式（closed-form）一步算出结果，似乎既快又准；但在浮点（IEEE-754 double）语境下有两个隐患：

这在数值分析里对应**向前误差（forward error）**的控制：每一步只引入一次相对舍入，且公比 |q|<1 时误差还会被后续项"稀释"。但要注意反例——若 |q|>1，递推会让项和误差同时放大，此时递推反而不稳定，闭式或更复杂的数值方法更优。

📖 结论：递推以"每步一次基本运算、中间值有界"换取稳定性，在 |q|<1 的衰减序列上优于含大幂的闭式表达；但稳定性是有条件的，公比放大时结论会反转。选公式前先判断序列是收敛还是发散。

三、统计一个正整数有几位：三种循环的选型

题目

输入一个正整数，计算它是几位数。比如 123 是 3 位，9 是 1 位。

这题本身简单，但它特别适合用来回答 Day 2 留下的问题：for、while、do-while 到底怎么选？

三种写法

while（最常见）：

int n, cnt = 0;
cin >> n;
while (n > 0) {
cnt++;
n /= 10;
}
cout << cnt;

do-while（本题在数学上最严谨）：

int n, cnt = 0;
cin >> n;
do {
cnt++;
n /= 10;
} while (n > 0);

为什么 do-while 在这里更优？因为它保证至少执行一次。即便输入是 0，位数也应该是 1 位（0 本身是一个一位数），而纯 while(n>0) 对 0 一次都不执行，会错误地输出 0。凡是"无论如何至少处理一次"的逻辑，do-while 是天然选择。

for（把计数器和剥离动作收进一行）：

int n, cnt;
cin >> n;
for (cnt = 0; n > 0; n /= 10) cnt++;
cout << cnt;

更新部分直接写 n /= 10，循环体只剩计数，非常紧凑——但可读性见仁见智。

三种循环的选型原则

本质上三者在汇编层面可以互相改写，差别只在于谁最贴合你的思维：次数已知用 for，先判断后执行用 while，先干一次再说用 do-while。

深度思考：数位剥离 n /= 10 为什么能统计位数？进制的本质是什么？

核心在于**位置记数法（positional notation）**与整数除法的"去尾"语义。

一个十进制数 n 的值是

∑

d

k

10

k

\\sum d_k 10^k

∑dk​10k。整数除法 n /= 10 在数学上等于

⌊

n

/

10

⌋

\\lfloor n/10 \\rfloor

⌊n/10⌋，它精确地抹掉最低位：123 → 12 → 1 → 0。每抹掉一位，计数器加一，直到数变成 0——剥离的次数恰好等于最高位的权值指数加一，也就是位数。这个操作之所以能用简单除法完成，是因为十进制系统里"位"的权重是基数 10 的幂，除一次基数就整体右移一位。

推广开就触达了进制的本质：把 10 换成任意基数 b，同一套代码就在做 b 进制的数位遍历。

• n % b 取最低位（b 进制下的个位数字）；
• n /= b 右移一位；
• 配合栈或 n % b 逆序输出，就是十进制转 b 进制；
• b=2 时 n & 1 等价 n % 2、n >> 1 等价 n / 2，这正是位运算优化数位题的来源。

所以数位 DP（第一题境界三）的状态按"位"推进、% 10 取当前位、/10 进入下一位，全都是这一条位置记数法规则的延伸。

📖 结论：/10 抹位、%10 取位是位置记数法在整数算术上的直接投影；换成任意基数 b，同一套剥离逻辑就是通用的进制转换与数位算法基石。

四、flag 状态翻转：交错调和级数（洛谷 B2070）

题目

计算

S

n

=

1

−

1

2

+

1

3

−

1

4

+

⋯

+

(

−

1

)

n

−

1

n

S_n = 1 – \\dfrac{1}{2} + \\dfrac{1}{3} – \\dfrac{1}{4} + \\cdots + \\dfrac{(-1)^{n-1}}{n}

Sn​=1−21​+31​−41​+⋯+n(−1)n−1​，保留四位小数。

我的第一版：用 pow(-1, n-1)

while (n) {
Sn = Sn + pow(–1, n – 1) * (1.0 / n);
n—;
}
cout << fixed << setprecision(4) << Sn << endl;

能跑，但有两个我当时没意识到的毛病：一是 pow(-1, n-1) 每次都调用浮点库函数去算一个明明只有 ±1 的符号，又慢又可能有精度毛刺；二是 n– 破坏了输入值，而且逆序累加（从第 n 项加到第 1 项）和题目公式顺序相反，读代码要倒着推。

参考版：一个 flag 翻转解决符号

int n;
double sn = 0;
int flag = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
sn += flag * 1.0 / i;
flag = –flag; // 1 -> -1 -> 1，符号交替
}
printf("%.4f\\n", sn);

这一改让我特别有感触，它在三个层面都更优：

深度思考：flag = -flag 本质上是在做什么？为什么说它是一个二态自动机？

这一现象的本质是用一个变量编码一个二元状态，并在每次迭代中施加确定性的状态转移。

符号

(

−

1

)

i

−

1

(-1)^{i-1}

(−1)i−1 在数学上看似依赖"当前是第几项"这个全局信息，但它有一个关键性质：下一项的符号只由当前项符号唯一决定——取反即可。这正是 Day 2 讲的无后效性：不需要记住 i，也不需要重算幂，只要保留一个比特的历史（当前是 + 还是 -），状态转移函数是

f

(

s

)

=

−

s

f(s) = -s

f(s)=−s。于是 flag 构成了一个只有两个状态 {+1, -1} 的有限状态自动机（FSM），每来一项就做一次状态迁移。

对比两种实现的代价：

更一般地，凡是"周期切换"的逻辑都能这样状态化：棋盘格用 (i+j)&1、三态循环用 flag=(flag+1)%3、开关门问题用 bool open=!open。把"第几轮决定什么状态"改写成"上一状态如何转移到下一状态"，是从公式翻译走向状态机设计的关键一步，也是后面图论 BFS 染色、模拟题、动态规划的共同思维原型。

📖 结论：flag = -flag 是一个二态有限自动机的单步转移，用一个比特的记忆替代了对全局项数的幂运算；凡周期性交替，皆可抽象为"状态 + 转移函数"，这正是模拟与状态机算法的起点。

📝 总结

Day 2.5 这四道补充题，帮我把"循环与数学的边界"彻底划清了：

Day 1 管"值对不对"，Day 2 管"状态稳不稳"，Day 2.5 补上了"控制流收得住不住、库函数该不该用"。循环这块地基，到这儿算是夯实了。

点个赞收藏一下呗～有理解不对的地方欢迎评论区指正

参考资料：

• 牛客网「数字 9（含错误解答总结）」
• 洛谷 B2076 球弹跳高度的计算、B2070 分数序列求和
• 《算法竞赛入门经典（第 2 版）》刘汝佳
• Dijkstra《Go To Statement Considered Harmful》
• IEEE-754 浮点标准与数值稳定性相关资料

标签： C++ 算法竞赛 洛谷 牛客 循环结构 状态机 数值稳定性 刷题笔记