看到标题里的 P1423懂行的朋友应该已经知道我说的是洛谷上那道“小玉在游泳”。这道题在入门算法题里属于典型到不能再典型的顺序结构加循环结构练习很多初学 C 或者 Python 的人第一周就会碰到它。题目本身不长大意是小玉第一天能游 2 米之后每天游的距离是前一天的一半给定目标距离 s问几天能游完。看起来就是个简单的累加题但里面藏着的循环边界、浮点数判断、等比数列思想恰恰是新手从“照着写代码”过渡到“真的理解算法”的一个关键台阶。这篇文章我想从题目拆解、数学建模、多语言实现到避坑经验完整过一遍把我自己带训练时总结的那些细节都抖出来。不管你是刚接触编程的萌新还是已经开始刷题的同学应该都能从这里拿到一些能直接用的东西。1. 题目到底在说什么一个“每天减半”的经典场景1.1 从题面提取数学模型先把生活化描述翻译成数学语言。小玉第 1 天游 2 米第 2 天游 1 米第 3 天游 0.5 米。每天的距离不是随便给的它构成一个等比数列首项是 2公比是 0.5。也就是说第 n 天游的距离是 2 乘以 0.5 的 n-1 次方。我们需要找到最小的天数 n让前 n 天游的累计距离大于等于目标值 s。如果用符号表示就是求满足下式的最小整数 nS(n) 2 1 0.5 ... 2 × 0.5^(n-1) ≥ s这个式子一旦列出来题目就清晰了。它根本不是“游泳”题而是一道“给定一个递推序列求前 n 项和超过阈值的最少项数”的经典问题。这种结构在后面的很多题目里都会反复出现。我见过不少同学拿到题直接开始写 while 循环这没有错但如果你连上面这个等比数列的关系都没看出来后面碰到变体题就容易懵。先把数学模型抽出来代码只是把模型翻译成机器能跑的东西。1.2 这道题在刷题路线里的准确位置P1423 在入门题库里被归为“顺序结构”和“循环结构”的交界题。它的前置知识非常简单会定义变量、会写 while 或者 for、会读入浮点数、会输出整数。难点不在语法而在两件事上。第一件事是理解“条件循环”的退出时机。目标距离是 s累计距离是 sum只要 sum 还小于 s就要继续游所以循环条件是 while (sum s)不是 while (sum ! s)也不是 while (sum s)。初学者经常把条件写成相等判断这在浮点数场景下大概率翻车。第二件事是理清“当前步长”和“累计天数”的更新顺序。每天先游再减半还是先减半再游结果天差地别。这个细节我后面专门讲现在先记住代码顺序反映的是逻辑顺序不是随便排的。如果你正在学习算法基础这道题做完之后我建议你立刻去看几道同结构的题比如 P1035 级数求和。那道题是把等比数列换成了调和级数循环结构几乎一模一样。把这两题放在一起做一遍“循环累加直到满足条件”这个套路就算真正入门了。2. 核心思路拆解模拟循环为什么是这道题的标准解法2.1 三个变量的关系step、sum 与 day处理这种题我习惯先定义三个变量把它们的含义写清楚再开始写循环。step当前这一天能游的距离初始值是 2.0。sum已经游完的累计距离初始值是 0。day已经过去的天数初始值是 0。循环里每一轮做三件事把 step 累加到 sum 上把 day 加 1再把 step 减半。用 C 写就是int day 0; double sum 0.0; double step 2.0; while (sum s) { sum step; day; step / 2.0; } cout day endl;这三件事的顺序非常关键。sum 先加上 step代表“今天游完了”day 再自增代表“今天过去了”step 最后减半代表“为明天做准备”。顺序一换比如先把 step 除以 2 再加那第一天累计的距离就变成了 1 米而不是 2 米答案全错。Python 版本也一样无非是把声明和输出换成 Python 语法s float(input()) day 0 sum_dist 0.0 step 2.0 while sum_dist s: sum_dist step day 1 step / 2.0 print(day)很多人会问为什么不用 for 循环因为 for 循环适合“知道要循环几次”的场景而这里天数需要动态计算我们只知道循环结束条件不知道具体次数。当然你也可以用 for 写一个足够大的范围然后手动 break但那样既不直观也容易出错。while 是这种情况下最自然的表达。2.2 循环边界为什么用小于而不是小于等于接着看边界条件。如果目标距离 s 恰好是 3 米小玉第 1 天游 2 米累计 2 米没到 3 米第 2 天游 1 米累计正好 3 米。此时应该输出 2。用 while (sum s) 判断第 2 天结束后 sum 等于 s条件不再成立循环正常退出day 正好是 2。没问题。如果换成 while (sum s)当 sum 刚好等于 s 时还会再执行一次输出就变成了 3错误。所以这里必须用严格小于。再考虑 s 很小的情况比如 s 1。第一天 step 是 2sum 从 0 变成 2条件 2 1 不成立循环退出day 1。答案正确。这个用例是很好的自测数据很多人在 day 初始化上犯错跑这种边界数据一下就能暴露。2.3 一个隐藏的数学结论为什么泳程极限是 4 米这一节是很多人刷完题也没注意到的点。等比数列求和的公式是“首项乘以一减公比的 n 次方再除以一减公比”。代入首项 2、公比 0.5前 n 天总距离是S(n) 2 × (1 - 0.5^n) / (1 - 0.5) 4 × (1 - 0.5^n)当 n 越来越大0.5^n 越来越接近 0所以 S(n) 越来越接近 4但永远小于 4。换句话说小玉就算无限游下去累计距离也不会超过 4 米。这是一个典型的收敛级数场景。这个结论对做题有什么实际意义它告诉我们题目的输入 s 一定小于 4最多是 3.999 这种数否则无解。虽然 OJ 的测试数据会保证这一点但你自己写代码时如果拿 s 5 去测while 循环会陷入死循环这是非常典型的本地卡死原因。理解了这层数学背景你就能提前判断“是不是数据给超了”或者“我是不是读入读错了”。3. 多语言实现与细节讲解3.1 C 实现注意数据类型和读入C 版本上面已经贴过核心代码这里我补几个工程细节。第一个细节是读入时用 double 而不是 float。虽然这道题最多游二十来天float 精度也够但养成用 double 的习惯可以避免在高精度题目里吃亏。第二个细节是不要在循环里反复计算 step / 2.0写成 step * 0.5 也可以两种写法性能相同选自己看着顺眼的。完整可运行版本#include iostream using namespace std; int main() { double s; cin s; int day 0; double sum 0.0; double step 2.0; while (sum s) { sum step; day; step * 0.5; } cout day endl; return 0; }这里有个很小的优化点如果你担心 s 异常接近 4 导致循环次数偏多其实完全不必因为 20 天后 step 已经变成 2 的 20 次方分之一只有百万分之一米级别循环次数不会超过 30。所以模拟法在这个题里性能毫无压力。3.2 Python 实现浮点数读入注意事项Python 版本最需要留意的就是读入。输入是一个实数可能是带小数的所以要用 float(input())而不是 int(input())。有的题目输入可能带有多余空格或者换行Python 的 input() 会帮我们处理掉首尾空白这块不用操心。s float(input().strip()) day 0 total 0.0 step 2.0 while total s: total step day 1 step / 2.0 print(day).strip()在这里不是必须的但属于一种输入防御性写法。如果整道题只有一行输入不写也没问题。实际做题时我更关心的是另一件事Python 的浮点数累加会有误差累积但本题累计次数太少误差完全不影响判断。真正需要担心的是那些要循环几百万次的场景那道题的误差控制思路就和这里不一样了。3.3 公式解法用对数直接算出答案以及它的坑模拟解法已经足够简单但我还是建议认真看一下公式解法因为它能帮你理解“为什么数学思维在算法里那么重要”。从前面的求和公式出发要求 S(n) ≥ s即4 × (1 - 0.5^n) ≥ s移项得到 0.5^n ≤ 1 - s / 4两边取对数注意底数是 0.5它是小于 1 的取对数后不等号方向会变。所以 n 的最小值是向上取整 log(1 - s / 4) / log(0.5)。写成代码是#include bits/stdc.h using namespace std; int main() { double s; cin s; int ans ceil(log(1.0 - s / 4.0) / log(0.5)); cout ans endl; return 0; }这个版本代码很短但坑也不少。第一个坑是当 s 非常接近 4 的时候1 - s/4 是一个接近于 0 的浮点数取对数后是一个绝对值很大的负数再除以 log(0.5)结果可能因为浮点误差差出一整天。第二个坑是当 s 等于 4 时对数的真数是 0数学上无定义程序会得到一个负无穷或者引起运行时问题。我的建议是如果你要用公式法最后一定加一个保险校验用暴力循环从 ans-2 开始核对找到真正的答案。这个思想在算法竞赛里叫“二分答案后校验”的简化版也是一种很实用的工程态度公式给出近似位置循环修正精度。int ans (int)ceil(log(1.0 - s / 4.0) / log(0.5)); while (ans 1 4.0 * (1.0 - pow(0.5, ans - 1)) s) ans--; while (4.0 * (1.0 - pow(0.5, ans)) s) ans; cout ans endl;不过说实话对这道题而言模拟法又短又稳公式法更多是拿来练思维。我的结论很明确比赛里求稳就用模拟平时练习两种都写一遍最好。4. 常见问题与避坑实录4.1 浮点数比较的经典陷阱新手最容易犯的一个错误是判断条件写成 while (sum ! s)。这个写法在数学上没问题在计算机里却几乎必然出错。因为浮点数是用二进制表示的很多十进制小数无法精确存储比如 0.1 在计算机里就是一个无限循环的二进制小数累加之后 sum 和 s 的相等比较会失败。判断浮点数是否达到目标标准做法就是像我前面那样用sum s做循环条件退出后就代表已经大于或等于了。如果你确实需要判断两个浮点数是否“足够接近”应该用 abs(a - b) epsilon其中 epsilon 取 1e-9 这样的安全值而不是直接用 。这个经验在后续所有涉及浮点的算法题里都会用到。4.2 循环顺序写反的典型现场把 step / 2 放在 sum step 前面这是第二个高频错误。我有一次给别人 debug看他的代码while (sum s) { step / 2; sum step; day; }输入 s 1他输出是 3为什么因为循环第一次执行时step 先变成了 1然后 sum 加 1此时 sum 仍然小于 1不对sum 变成 1等于 s条件应退出day 是 1。感觉输出 1 才对那要看 s 是别的数。比如 s 2第一次循环 sum 加到了 1小于 2继续第二次 step 变成 0.5sum 变成 1.5第三次 sum 变成 1.75要很多次才超过 2。而正确代码第一天就游 2 米直接退出。所以 s 2 时错误写法会输出一个很大的数。这种 bug 的可怕之处在于输入小数据时它也能输出正确结果s 1 时碰巧对了输入稍大一点就错误。原因就是变量的更新顺序不对逻辑被悄悄改变了。我建议新手在纸上画一个表列三行表头分别是 day、step、sum然后手动模拟前三次循环把每次的值填进去。这个方法虽然笨但能根治顺序混乱的问题。4.3 边界样例自测表刷题提交之前我习惯带着下面这几个边界值过一遍代码确认输出符合预期。你也可以直接拿来自测。输入 s推导过程预期输出1第 1 天游 2 米超过 112第 1 天游 2 米刚好等于 213第 1 天游 2 米累计 2第 2 天游 1 米累计 323.753.75 4 × (1 - 0.5^4)第 4 天刚好达到43.994 × (1 - 0.5^n) ≥ 3.99解得 n ≥ 8.65向上取整9这些数据一方面帮你验证代码正确性另一方面也帮你直观感受这个级数收敛有多快。第 8 天的时候单日距离只有 0.015625 米后面几乎是在蹭了。5. 从这道题延伸出去的思考5.1 同类结构题目举一反三P1423 做完之后我强烈建议立刻做 P1035 级数求和。那道题求的是 1 1/2 1/3 ... 直到和大于给定值 k输出最小的 n。它的循环结构跟本题几乎一样k int(input()) n 0 total 0.0 while total k: n 1 total 1.0 / n print(n)注意两者的差别一个是每一项乘以固定比例 0.5另一个是每一项除以递增的 n。前者收敛到 4后者发散到无穷大所以 P1035 可能需要循环几十万次甚至更多。虽然模拟法也能过但它的循环次数和输入规模直接相关这时候就要稍微关心一下跑了多少轮了。对比这两道题你能悟出一个非常有用的判断标准如果递推项在迅速缩小比如每轮乘一个小于 1 的常数循环次数通常很少直接模拟如果递推项缩得很慢比如调和级数或者递推项本身在增大你就要先估算一下循环次数会不会超时再决定是模拟还是用公式。这是“算法复杂度直觉”的萌芽。5.2 什么时候该用数学公式什么时候该无脑模拟我见过不少人包括一些已经刷了几百题的同学遇到能推公式的题反而犹豫不决。这里我给一个很实际的经验法则不是比赛场景自己练习时优先写出模拟解法哪怕它慢一点。因为模拟解法逻辑直观出错概率低也容易调试。比赛或者时间受限时如果模拟的循环次数可能达到千万级别再考虑公式或二分。用公式解出的答案必须经过边界校验尤其当问题涉及浮点数取整、对数这类运算时。具体到 P1423模拟最多跑几十次公式优化的收益完全体现不出来。所以我的建议就是这一题直接用模拟把公式解法当作课后思考题去理解就行。5.3 把“约等于 4”这个结论用在后续题里等比数列求和的结论不只是这一道题用得上。很多递推题里会出现“每次减少一半”的描述比如每次感染传染一半、每次倒掉一半水、每次损坏一半长度本质上都是等比数列。只要公比绝对值小于 1总和就会有一个上限。这个“有上限”的特性经常被用来证明模拟不会死循环或者用来估算答案范围。比如有一类二分答案题判断函数里需要模拟一个不断减半的过程知道总量有上界就能提前判断某个 mid 是否可行。这些经验都是刷一道题看不出来的但把它记住后面会用得很爽。最后聊两句个人体会我在给新手讲这道题的时候经常问一个问题小玉游 10 天之后每天只能游不到 2 毫米这个数量级合理吗很多人会愣住因为他们从来没把代码里的 step 真正对应到现实距离上。我其实是想让大家养成一个习惯写一个算法题不要只盯着代码能不能过样例而是把每个变量的含义、每个数值的变化趋势都想透。P1423 的代码三五分钟就能写完但它背后的等比数列、收敛极限、循环边界这些点值得你反复咀嚼。还有一个实用小技巧分享给正在刷题的朋友提交之前在自己心里把题目的输入范围想清楚至少准备三组自测数据一组最小值、一组临界值、一组极端接近极限的值。拿 P1423 来说就是 s 1、s 3、s 3.999 这三组。跑一遍不出错再点提交注意输出个位数。这个习惯救过我很多次也是从这道最简单的小玉游泳题开始练成的。