我前段时间被一个小问题卡住了有两个 0 到 1 之间的小数 (a) 和 (b)想找一个最小的正整数 (n)让 (a \times n) 和 (b \times n) 之间刚好夹着一个整数。乍一看像是初中数学真上手才发现里面全是坑。后来我把问题转化成“在区间 ((a, b)) 里找一个分母最小的分数”事情一下就清楚了。这篇文章就把从暴力枚举到 Stern-Brocot 树的完整思路记录下来顺便聊聊实际工程里怎么避开浮点数精度这类隐蔽问题。不管你是写游戏 Tick 对齐、信号采样还是单纯喜欢这种小算法题都值得看下去。我会先给一个最直觉的暴力解法再给一个数学上更漂亮的解法最后补上边界条件和验证器尽量让你看完就能直接抄代码。1. 问题重述一句话里的数学结构1.1 先别急着写循环题目到底在问什么题目给的原始描述是“两个 1 以内的小数乘 (n) 后中间恰好间隔一个整数”。我们先把这句话翻译成数学语言。假设 (0ab1)。我们要找最小的正整数 (n)使得存在一个整数 (k)满足[ a \times n k b \times n ]这个“中间”我用严格的开区间理解端点上的整数不算因为“中间”天然排除了两边。这里 (k) 就是那个被夹住的整数。不等式两边同时除以 (n)因为 (n0)不等号方向不变就变成[ a \frac{k}{n} b ]也就是说真正要回答的问题是在开区间 ((a,b)) 内找一个分母最小的分数 (\frac{k}{n})这个分母 (n) 就是答案。为什么一定是“分母最小”因为题面要求最小的 (n)。如果分数能约分约掉公因子后分母更小那原分数就不可能是最优解。所以最优解对应的一定是最简分数。举个例子。(a0.2)(b0.3)一眼能看出 (\frac{1}{4}0.25) 落在区间内分母是 4。所以最小 (n) 是 4。验证一下(0.2\times40.8)(0.3\times41.2)中间夹着整数 1严格满足条件。1.2 “最小 n”不是简单除以差值很多人第一反应是算区间长度 (b-a)然后取倒数向上取整。理由是区间长度变大之后总能“盖住”一个整数。但这是错的。还是用 (a0.2)(b0.3)。区间长度是 0.1(\frac{1}{0.1}10)似乎答案应该是 10但实际答案是 4。为什么直觉失效因为区间里有没有整数不仅看长度还要看整数落在什么位置。区间长度可以小于 1但仍然包住一个整数。比如 (n7) 时区间是 ((1.4,2.1))长度只有 0.7但中间夹着整数 2。反过来区间长度大于 1 也不一定保证“恰好一个”。真正靠谱的做法是把问题看成有理数区间内的分母最小分数搜索。1.3 必须提前定好的规则开区间、排序、边界在写代码之前有几个规则如果不先定好后面调试会非常痛苦。第一默认 (ab)。如果传入的是 (ab)直接交换。如果 (ab)区间是空的无解。第二端点整数不算“中间”。所以 ((1,2)) 里面没有整数((1,2.1)) 里面有整数 2但 ((1.9,2)) 里面同样没有整数。这个开区间的定义直接影响判定条件特别是当 (a\times n) 或 (b\times n) 恰好是整数时必须严格排除。第三(a0) 或 (b1) 是可以接受的。因为区间 ((0,0.3)) 里有 (\frac{1}{4})分母是 4。区间 ((0.2,1)) 里有 (\frac{1}{2})分母是 2。我的算法会把 (0) 当作 (\frac{0}{1})把 (1) 当作 (\frac{1}{1}) 作为搜索边界这两种情况天然支持。2. 暴力解法能跑但不是终点2.1 判定“恰好一个整数”的精确写法暴力解法的思路很简单令 (n1,2,3,\dots)依次检查区间 ((a\times n, b\times n)) 内是否恰好有一个整数。怎么判断“恰好一个”设[ left a \times n,\quad right b \times n ]那么严格大于 (left) 的最小整数是[ first \lfloor left \rfloor 1 ]如果这个整数落在区间内那么它必须小于 (right)即[ first right ]同时区间里不能有第二个整数。下一个整数是 (first1)它必须不在区间内也就是[ first 1 \ge right ]但是因为区间是开区间如果 (first1 right)说明第二个整数在右端点上不算“中间”。所以严格条件应该是[ first 1 right ]两个条件合起来first right 且 first 1 right这表示区间内有且仅有一个整数 (first)。2.2 第一版代码用 Fraction 解决浮点污染如果直接用 Python 的float很快会踩精度坑。比如 (0.3) 在二进制里是一个无限循环小数计算 (0.3\times4) 可能是 (1.1999999999999997)边界判断就错得莫名其妙。所以我第一时间用fractions.Fraction。它把小数转成精确分数比较运算完全可靠。from fractions import Fraction def min_n_bruteforce(a, b, limit1_000_000): 暴力枚举 n在开区间 (a, b) 内找最小的分母 n。 a, b 都是 Fraction且 0 a b 1。 if a b: a, b b, a for n in range(1, limit 1): left a * n right b * n first int(left) 1 # 严格大于 left 的最小整数 if first right and first 1 right: return n return None # 超过 limit 还没找到测试一下print(min_n_bruteforce(Fraction(1, 5), Fraction(3, 10))) # 4 print(min_n_bruteforce(Fraction(1, 5), Fraction(1, 4))) # 9 print(min_n_bruteforce(Fraction(0), Fraction(1))) # 2第二个用例是区间 ((0.2,0.25))。注意 ((1/4)0.25) 在右端点上不能选。(1/50.2) 在左端点上也不能选。真正落在中间的最小分母分数是 (2/9)所以答案是 9。2.3 暴力什么时候撑不住暴力法虽然直观但在某些区间上会非常慢。看一个极端例子区间 ((0.1999999,\ 0.2))。(0.2) 本身是右端点不能选。要找的是比 (0.2) 小一点点、但又大于 (0.1999999) 的最简分数。这个分数的最小分母可能接近一千万。用暴力法要循环几百万甚至几千万次效率惨不忍睹。实际业务场景里虽然很少遇到这种极端区间但一旦遇到暴力法就会让你等到怀疑人生。这也是我要讲下一个算法的原因。3. Stern-Brocot 树找到区间内分母最小的分数3.1 问题本质区间内找分母最小的有理数前面已经推出要找最小 (n)等价于在区间 ((a,b)) 内找一个分母最小的有理数 (\frac{k}{n})。有理数集合里按分数的分子分母大小排成一个无穷树就是 Stern-Brocot 树。这棵树从 (\frac{0}{1}) 和 (\frac{1}{1}) 开始每一步在相邻两个分数 (\frac{p}{q}) 和 (\frac{r}{s}) 之间插入它们的“中位分数”[ \frac{pr}{qs} ]这个中位分数有个非常重要的性质如果两个分数的行列式为 1也就是 (rq - ps 1)那么它们之间任何分母更小的分数都不存在中位分数就是它们之间分母最小的分数。算法过程其实很像二分查找。维护两个边界分数一个下界一个上界。每次取出中位分数判断它落在了区间左边、区间里面还是区间右边。如果在区间里面直接返回它的分母如果小于等于 (a)把它当成新的下界如果大于等于 (b)把它当成新的上界。不断缩小范围直到命中。3.2 中间分数为什么是最小分母候选这里值得稍微展开一下因为很多人第一次看到会困惑“凭什么中位分数就是最优”你不需要把整棵 Stern-Brocot 树背下来只需要记住一个局部结论当两个相邻分数 (\frac{p}{q}\frac{r}{s}) 满足 (rq-ps1) 时它们之间不可能再存在一个分母小于 (qs) 的分数而中位分数正好是分母为 (qs) 的那个。在树的搜索过程中每一步的上下界始终保持这种相邻关系或者经过边界替换后重新恢复这种关系。所以当中位分数第一次落进区间时它就是这个区间内分母最小的分数。这个性质背后是法里序列的经典结论感兴趣的话可以搜“法里分数”和“中间分数”。对我们工程用途来说知道结论、会用代码就已经足够。3.3 实现与边界处理下面是完整的 Stern-Brocot 解法。上下界分别用两个分数表示初始为 (0/1) 和 (1/1)。from fractions import Fraction def min_n_sb(a, b): 用 Stern-Brocot 树在开区间 (a, b) 内找最小分母 n。 a, b 都是 Fraction且 0 a b 1。 if a b: a, b b, a left_p, left_q 0, 1 # 下界 0/1 right_p, right_q 1, 1 # 上界 1/1 while True: mid_p left_p right_p mid_q left_q right_q mid Fraction(mid_p, mid_q) if a mid b: return mid_q if mid a: left_p, left_q mid_p, mid_q else: # mid b right_p, right_q mid_p, mid_q测试print(min_n_sb(Fraction(1, 5), Fraction(3, 10))) # 4 print(min_n_sb(Fraction(1, 5), Fraction(1, 4))) # 9 print(min_n_sb(Fraction(0), Fraction(1))) # 2 print(min_n_sb(Fraction(199, 1000), Fraction(1, 5))) # 1001最后一个用例是区间 ((0.199, 0.2))答案是 1001。因为分母 1000 的分数里分子必须满足 (199 k 200)没有整数 (k) 可选。到分母 1001 时(\frac{200}{1001} \approx 0.1998)刚好落在区间内。3.4 复杂度不是银弹但通常很有用严格来说Stern-Brocot 算法的最坏复杂度并不低。如果区间是 ((0.1999999, 0.2)) 这种贴着有理数边界的超窄区间算法也会循环接近一千万次。虽然比暴力法少一些但仍然不小。但随机区间下的表现比暴力法好得多。大部分情况下几十轮循环就结束了。而且它不是靠运气而是靠数论结构保证的每一步都跳过大量不可能成为答案的分母。如果你要处理的是理论数学里的高精度极端场景还可以用连分数来做更激进的批处理跳跃。但对绝大多数实际需求Stern-Brocot 版本已经够用代码也短一眼能看懂。4. 工程视角从“找到 n”到“可靠落地”4.1 用字符串构造 Fraction别用浮点数中转很多读者喜欢写Fraction(0.2)这其实有坑。0.2在 Python 里是一个floatFraction(0.2)得到的是二进制浮点数精确值Fraction(0.2) # Fraction(3602879701896397, 18014398509481984)这个分数并不是真正的 (1/5)。虽然数值差距很小但在边界判断里它可能让你选出一个错误的 (n)。正确做法是用字符串构造Fraction(0.2) # Fraction(1, 5)如果小数是动态生成的可以用str()转成字符串再构造。比如用户输入0.20Fraction(0.20)会得到Fraction(1, 5)完全符合十进制语义。如果不想引入Fraction也可以用decimal.Decimal。但Fraction的优势是天然支持有理数比较写起来最省心。4.2 两个典型应用场景这个问题的实用价值比表面看起来要广。我举两个我实际遇到过的场景。第一个是游戏或实时系统的 Tick 对齐。假设一个动画事件发生的时间窗口是某个区间系统只能按固定 Tick 周期触发事件。你想知道最小 Tick 倍率使得某个整数 Tick 落进这个时间窗口。这个“窗口”往往就是两个小数之间的区间。第二个是采样步长选择。两个传感器事件之间的相对时间是 ((0.2, 0.3)) 秒你想找一个最小的时间伸缩倍数使得某个整数毫秒数能正好落进窗口。如果你把秒换算成单位 1本质就是同一道题。这俩场景都不需要做浮点模糊匹配而是需要严格保证边界行为。用暴力枚举加浮点数判断早晚会在边界上出诡异 bug。4.3 把算法封装成一个干净函数综合前面所有内容我通常把一个完整的工具函数写成这样from fractions import Fraction def smallest_n_between(a_str, b_str): 给定两个十进制数字符串 a_str, b_str 返回最小的正整数 n使得 a*n 与 b*n 之间恰好有一个整数。 a Fraction(a_str) b Fraction(b_str) if a b: a, b b, a if a b: return None # 区间为空 # Stern-Brocot 搜索 left_p, left_q 0, 1 right_p, right_q 1, 1 while True: mid_p left_p right_p mid_q left_q right_q mid Fraction(mid_p, mid_q) if a mid b: return mid_q if mid a: left_p, left_q mid_p, mid_q else: right_p, right_q mid_p, mid_q调用示例print(smallest_n_between(0.2, 0.3)) # 4 print(smallest_n_between(0.2, 0.25)) # 9这个函数不依赖浮点数测试起来很舒服。5. 常见问题与避坑记录5.1 边界点到底算不算“中间”最常踩的坑就是边界问题。比如 (a0.2)(b0.25)如果错误地用了闭区间你可能会认为 (n4) 时 (0.25\times41) 是整数答案应该是 4。但实际上题目说的是“中间恰好间隔一个整数”端点整数不算。真正的区间是 ((0.8, 1))里面没有整数。所以在代码里我特意用first right和first 1 right两个都是严格不等号。如果你想改造成闭区间语义只需要把改成把改成但那样答案会不同。5.2 ab、ab、a0 或 b1 如何处理(ab)交换即可区间 ((b,a))。(ab)区间为空返回None。(a0)区间 ((0,b))算法从 (0/1) 开始天然支持。(b1)区间 ((a,1))算法从 (1/1) 开始天然支持。(a0, b1)答案是 2因为 (0\times20)(1\times22)中间刚好有整数 1。这个用例建议写进测试用例里防止以后重构代码时被破坏。5.3 为什么两个实现的结果可能不同如果暴力法和 Stern-Brocot 法在某个用例上返回不同结果先别急着怀疑数学。最常见的原因是浮点数精度污染。比如Fraction(0.2)和Fraction(0.2)根本不是同一个数。前者可能比 (0.2) 略大一点点导致区间边界判断翻转。排查方法很简单在测试里统一用字符串构造Fraction或者直接用整数构造。另一个原因可能是暴力循环的上限太小漏掉了答案。如果你用暴力法做交叉验证上限一定要设得比 Stern-Brocot 返回的答案大得多。5.4 一个稳妥的验证器我习惯在写完算法后加一个验证器随机生成测试用例确保每个结果都真的满足题意。import random def verify(a, b, n): left a * n right b * n first int(left) 1 return first right and first 1 right def run_random_tests(times5000): for _ in range(times): x Fraction(random.randint(0, 999), 1000) y Fraction(random.randint(0, 999), 1000) if x y: continue a, b (x, y) if x y else (y, x) n min_n_sb(a, b) assert verify(a, b, n), ffail: a{a}, b{b}, n{n} # 所有更小的 n 都不应该满足 for m in range(1, n): assert not verify(a, b, m), fsmaller n found: {m}这个验证器把两层约束都查了第一返回的 (n) 确实满足“恰好一个整数”第二更小的 (n) 都不满足也就是“最小性”。有这两个约束兜底代码怎么重构都不怕。我个人在实际操作中的体会是这类小算法题最容易栽的从来不是“想不到 Stern-Brocot”而是“边界语义没定清楚”。开区间还是闭区间端点算不算浮点数用不用精确类型任何一个细节没定结果都会在不经意间给你来一下。如果你也遇到类似的问题建议先把输入规范和边界规则写进测试用例再上算法。顺序反了debug 时间会翻好几倍。最后再分享一个小技巧如果只是临时算一次答案完全可以用暴力枚举加Fraction代码短也不容易出错。只有当区间极窄、分母可能要跑到几十万上百万时才值得把 Stern-Brocot 版本请出来。工程上的事情够用、好懂、能测试往往比数学上的优雅更重要。