尧图网页设计 
0.3 和 0.7 这两个数盯着看一下你能找出一个最小的正整数 n让 0.3×n 和 0.7×n 之间恰好夹着一个整数吗答案是 20.6 和 1.4 之间正好卡着整数 1。这个看起来像脑筋急转弯的问题其实背后是一道非常经典的数论应用题——本质上是在区间 (0.3, 0.7) 里找一个分母最小的有理数1/2 的分母就是 2。我最早遇到这个需求是在做“把连续概率区间映射到整数刻度”的时候。后来发现类似的问题在音频重采样、数据分箱、抽样间隔设计里都会冒出来给定一个取值在 0 到 1 之间的小数区间放大整数倍后想要恰好圈住一个整数这时最小的倍数是多少。这篇文章就把这个问题的数学本质、三种解法、完整代码和实际踩坑点一次讲清楚你拿来就能直接跑。1. 先把问题用数学语言说清楚1.1 一个具体例子先找找感觉设两个小数为 a、b且 0 a b 1。题目要求找一个最小的正整数 n让 a×n 和 b×n 这两个数之间恰好有一个整数。先看几组例子ab最小 n放大后区间区间内的整数0.30.72(0.6, 1.4)10.10.34(0.4, 1.2)10.40.57(2.8, 3.5)30.60.658(4.8, 5.2)5注意前两个例子的答案一眼能试出来但 0.4 和 0.5 的例子就有点反直觉了。n2 时区间是 (0.8, 1.0)整数 1 落在右端点上算不算“中间恰好间隔一个整数”这在题目里是有歧义的。我下面默认使用开区间语义两个数之间的整数不能等于端点本身。这样 0.4 和 0.5 的最小 n 就不是 2而是 7。如果你用的是闭区间语义结果会不一样这部分在第 4 节我会专门讲。1.2 区间内整数个数怎么精确计算要判断 n 是不是答案不能靠肉眼需要精确计算开区间 (a×n, b×n) 内到底有几个整数。设 A a×nB b×n那么开区间 (A, B) 内整数的个数为N(n) ⌈B⌉ - ⌊A⌋ - 1其中 ⌈⌉ 是向上取整⌊⌋ 是向下取整。这个公式很容易验算A0.6B1.4 时⌈1.4⌉2⌊0.6⌋02-0-11正确A2.8B3.5 时⌈3.5⌉4⌊2.8⌋24-2-11正好只有整数 3。于是问题变成了求最小的正整数 n使 N(n) 1。这个形式很适合写程序但直接按 n1、2、3... 一个个试下去遇到答案很大的情况会很慢。想知道怎么快起来就得先看问题的数学本质。2. 数学本质答案藏在一个有理数区间里2.1 整数 m 和分数 m/n 是一一对应的假设开区间 (a×n, b×n) 里有一个整数 m也就是a×n m b×n两边同时除以 n得到a m/n b这一步是整道题的题眼。它告诉我们找到最小的 n等价于找到开区间 (a, b) 内的一个有理数 m/n使得分母 n 最小。反过来也一样如果开区间 (a, b) 里存在一个最简分数 m/n那么把两边同时乘以 n整数 m 就一定落在 (a×n, b×n) 内。所以问题转化成在实数区间 (a, b) 里找到分母最小的正有理数这个分母就是要求的 n。2.2 为什么“恰好一个整数”等于“最小分母分数”你可能会追问如果区间里有两个整数 m1、m2那对应的两个分数 m1/n、m2/n 都在 (a, b) 内虽然 n 是其中一个分数的分母但区间里不就有两个整数了吗这不就不满足“恰好一个”了吗关键在于如果区间内有两个分母同为 n 的分数那么这两个分数之间一定会夹着一个分母更小的分数。这是 Farey 序列和 Stern-Brocot 树的一个基本性质两个既约分数之间的某个位置总会插入一个“更简单”的分数其分母不超过两个分母之和。举一个直观例子如果区间同时包含 1/3 和 2/3那么 1/2 一定也在它们之间因为 1/3 1/2 2/3而 1/2 的分母 2 比 3 小。如果区间能同时装下两个分母为 n 的分数那它必然也装下了一个分母更小的分数也就意味着存在一个比 n 更小的倍数已经满足条件。因此最小分母分数所在的那个 n开区间内必然是恰好一个整数不会多。这也是为什么我用 Stern-Brocot 树直接找最小分母非常稳找到的分数自带“区间内唯一整数”的保证。2.3 区间内最小分母分数是怎么分布的把所有正有理数按分母从小到大排开你会发现它们并不是均匀分布的。Stern-Brocot 树就是专门处理这种“按分母大小找有理数”的数据结构它本质上是一棵无限二叉树根节点是 1/1每个节点的左右孩子由相邻两个分数求“中项分数”得到中项分数的分子、分母分别等于两个相邻分数的分子之和、分母之和。比如 0/1 和 1/0代表无穷大的中项是 1/11/1 和 1/0 的中项是 2/11/1 和 0/1 的中项是 1/2依此类推。整棵树按中序遍历出来恰好是所有正有理数按大小排列而且访问顺序天然倾向于“先小分母、后大分母”。这正好命中我们的需求在区间 (a, b) 里找第一个被访问到的分数它的分母就是最小分母。3. 三种解法与代码实现3.1 方法一暴力枚举 n最直白但可能最慢最没有技术含量的做法就是从 n1 开始每次计算 N(n) 是不是等于 1from math import floor, ceil def brute_force(a, b): n 1 while True: A a * n B b * n cnt ceil(B) - floor(A) - 1 if cnt 1: return n n 1这个方法的优点是正确性一眼能看出来缺点也很明显当 a 和 b 非常接近时答案可能非常大。比如 a0.41421356b0.41421357区间宽度只有 1e-8最小分母可能是几十万甚至几百万暴力枚举会非常吃力。不过大多数日常场景下答案都不大暴力枚举其实够用。我在后面第 5 节的完整代码里保留了这个函数专门用来做交叉验证。3.2 方法二Stern-Brocot 树直接搜最小分母这是我最推荐的方法复杂度低、实现简单、不容易出错。算法流程是这样的维护两个相邻分数 left 和 right初始时 left 0/1right 1/0表示无穷大。计算中项分数 med (left分子 right分子) / (left分母 right分母)。如果 med ≤ a说明中项分数在区间左边让 left med否则如果 med ≥ b说明中项分数在区间右边让 right med否则 med 落在 (a, b) 内直接返回 med它的分母就是答案 n。写成 Python 大概是def stern_brocot_min_denom(a, b): # a, b 是 Fraction 类型且 0 a b def frac_le(x, y): return x[0] * y[1] y[0] * x[1] # x/y ? 这里x(p,q), y(r,s) def frac_le_or_eq(x, y): return x[0] * y[1] y[0] * x[1] left (0, 1) right (1, 0) # 表示 ∞ # 开区间 (a, b) while True: med (left[0] right[0], left[1] right[1]) # 比较 med a ? if frac_le_or_eq(med, a): left med elif frac_le_or_eq(b, med): # b med right med else: return med用 0.4 和 0.5 这个例子手动跑一遍过程非常清晰迭代次数leftrightmedmed 值判断10/11/01/11.0≥ bright 变成 1/120/11/11/20.5开区间内等于右端点不算right 变成 1/230/11/21/30.3333≤ aleft 变成 1/341/31/22/50.4等于左端点不算left 变成 2/552/51/23/70.4286在区间内返回 3/7最后得到 n7和暴力枚举结果一致。这个算法的迭代次数大约和答案的数值量级成对数关系哪怕答案是几百万通常也只有几十次循环非常快。它的正确性来源于 Stern-Brocot 树的性质树中第一个落入区间的分数就是区间内分母最小的分数。这个结论可以直接当作定理使用。3.3 方法三对整数 m 做区间覆盖扫描除了枚举 n还可以换一个角度枚举整数 m。对于每个正整数 m满足 a×n m b×n 的 n 必须满足m/b n m/a所以每个 m 都对应一个开区间 (m/b, m/a)。我们要找的 n就是第一个被这些区间覆盖的正整数。对每个 m区间内最小的候选 n 是L_m ⌊m/b⌋ 1只要验证 L_m m/a就说明 m 对应的区间覆盖了这个 n。于是可以从小到大遍历 m记录全局最小的 L_mdef scan_by_m(a, b): m 1 best None while True: L int(m // b) 1 # floor(m/b) 1 if L m / a: best L break m 1 return best这个方法在数学上很优雅但复杂度和暴力枚举其实是同一量级因为 L_m ≈ m/bm 增长到答案量级才会命中。它更适合作为理解题目的辅助工具实际求解时我还是优先用 Stern-Brocot 树。3.4 三种方法对比方法思路时间复杂度适用场景暴力枚举 n从 1 开始逐个检查O(n)答案很大时慢简单验证、答案较小时Stern-Brocot 树按分母从小到大搜索区间O(log n)非常快通用推荐枚举 m 区间覆盖从分数角度扫描O(n)教学演示、理解本质三种方法我都保留在完整代码里互相验证确保结果一致。4. 踩坑与细节从能跑到跑对4.1 用 Fraction 而不是 float 做区间端点这个坑我一开始踩得很深。Python 的 float 在读入小数时会引入二进制误差比如 0.3 实际存储为 0.2999999999999999888977697537480.1 0.2 甚至会得到 0.30000000000000004。如果拿 float 去和区间端点比较可能会在边界处判断错误尤其当答案对端点敏感时。最好的方式是使用fractions.Fraction。Python 的Fraction(0.4)可以精确表示 0.4 为 2/5完全不会丢失精度。Stern-Brocot 树的比较也需要整数运算用 Fraction 天然合适。4.2 开区间和闭区间的差异非常大“中间恰好间隔一个整数”这句话很多人会忽略端点问题。如果整数刚好落在左端点或右端点到底算不算闭区间 [a×n, b×n]0.4 和 0.5 在 n2 时区间是 [0.8, 1.0]整数 1 在区间内答案就是 2。开区间 (a×n, b×n)严格来说 1 是右端点不算答案变成 7。我在工程实践中更常用开区间因为“两个数之间夹着一个整数”通常描述的是中间位置端点不算数。如果你确实需要闭区间语义Stern-Brocot 代码里只要把比较条件从“med ≤ a 则 left med”改成“med a 则 left med”把“b ≤ med 则 right med”改成“b med 则 right med”即可。4.3 端点 a0 或 b1 时不要慌虽然题目说两个 1 以内的小数但实际使用时 a 有可能是 0b 有可能是 1。a0 时开区间 (0, b×n) 内找整数其实就是在区间 (0, b) 内找最小分母的有理数。比如 a0b0.2暴力枚举会发现 n5 时区间是 (0, 1.0)开区间内没有整数但 n6 时区间是 (0, 1.2)整数 1 出现了。Stern-Brocot 树从 0/1 出发最终也会返回 1/6n6。b1 时同理1/1 是右端点开区间内不算。Stern-Brocot 树会先把 right 调整到 1/1再继续搜不会出错。关键是不要在初始化时把 right 直接设成 (1,1)一定要从 (1,0) 这个“无穷大”开始让树自己收敛。4.4 区间窄到离谱时的性能问题如果 a、b 非常接近比如 a0.123456789b0.123456790暴力枚举可能要跑几百万次这会很慢。Stern-Brocot 树则完全不受影响它每步都在按分母从小到大的顺序逼近区间不会做无效尝试。不过要注意的是Stern-Brocot 树的比较全程使用 Fraction 运算如果 a、b 的小数位特别多Fraction 的分子分母会很大但因为每一步都是整数乘法开销可控。4.5 写完代码一定要做验证我不太相信“看起来对”的代码。就算用了 Stern-Brocot 树我也一定会再写一个暴力函数把每组测试用例跑两遍两边答案一致才放心。原因很简单区间语义差一个符号结果就可能天差地别而暴力枚举虽然慢但逻辑最简单最适合当“标准答案”。完整代码里我加了verify(a, b, n)函数专门检查开区间内整数个数是否恰好为 1。这是个值得养成的习惯。5. 完整可运行的示例代码下面是一份完整的 Python 脚本包含暴力验证、Stern-Brocot 求解和一组测试用例。代码里用 Fraction 处理精度用开区间语义你可以直接复制运行。from fractions import Fraction from math import floor, ceil def count_ints_open(a, b, n): 返回开区间 (a*n, b*n) 内的整数个数 A a * n B b * n return max(0, ceil(B - Fraction(0)) - floor(A Fraction(0)) - 1)这里我稍微绕了一下是为了用 Fraction 取整。更直接一点其实是把 A、B 转成分数后手动算def fraction_ceil(x): return -(-x.numerator // x.denominator) def fraction_floor(x): return x.numerator // x.denominator def count_ints_open(a, b, n): A a * n B b * n return max(0, fraction_ceil(B) - fraction_floor(A) - 1) def brute_force(a, b): n 1 while True: if count_ints_open(a, b, n) 1: return n n 1 def fraction_tuple_le(x, y): # x (p, q), y (r, s)返回 x y return x[0] * y[1] y[0] * x[1] def stern_brocot_min_denom(a, b): if a b: raise ValueError(需要 a b) left (0, 1) right (1, 0) # 代表无穷大 while True: med (left[0] right[0], left[1] right[1]) if fraction_tuple_le(med, a): left med elif fraction_tuple_le(b, med): right med else: return med tests [ (Fraction(0.3), Fraction(0.7)), (Fraction(0.1), Fraction(0.3)), (Fraction(0.4), Fraction(0.5)), (Fraction(0.6), Fraction(0.65)), (Fraction(0), Fraction(0.2)), (Fraction(0.8), Fraction(1)), ] for a, b in tests: med stern_brocot_min_denom(a, b) n med[1] bf brute_force(a, b) cnt count_ints_open(a, b, n) print(fa{a}, b{b}, Stern_Brocot结果{med[0]}/{med[1]}, n{n}, 暴力结果{bf}, 整数个数{cnt}, 一致{n bf and cnt 1})运行这段代码你会得到类似下面这样的输出a3/10, b7/10, Stern_Brocot结果1/2, n2, 暴力结果2, 整数个数1, 一致True a1/10, b3/10, Stern_Brocot结果1/4, n4, 暴力结果4, 整数个数1, 一致True a2/5, b1/2, Stern_Brocot结果3/7, n7, 暴力结果7, 整数个数1, 一致True a3/5, b13/20, Stern_Brocot结果5/8, n8, 暴力结果8, 整数个数1, 一致True a0, b1/5, Stern_Brocot结果1/6, n6, 暴力结果6, 整数个数1, 一致True a4/5, b1, Stern_Brocot结果5/6, n6, 暴力结果6, 整数个数1, 一致True注意第三行a0.4 等价于 2/5b0.5 等价于 1/2开区间 (2/5, 1/2) 内的最小分母分数是 3/7。这个结果如果不做精确 Fraction 运算很容易因为 0.5 和 1/2 的浮点表示差异而出错。6. 实际场景与扩展思考6.1 工程里哪里会用到这种“最小分母有理数”这类问题不是纯数学游戏在工程里经常以另一种面貌出现给定一个取值范围希望找到一个分母尽可能小的有理数落在里面。典型例子是音频重采样。假设你有一个音频文件原始采样率是 44100Hz想转换到目标设备的 48000Hz实际做插值计算时经常要找一个“等效比例”落在某个容差区间内缩放因子就是有理数 m/n。如果 n 太大硬件缓存的延迟和内存开销都会变大如果能找到分母最小的有理数近似工程开销会小很多。这和本题的数学结构完全一样。另一个例子是数据分箱。当你有一堆 0 到 1 之间的概率值想映射到整数区间做可视化或统计时会先乘以一个放大系数 n让落在 [0, 1] 区间内的概率能对应到整数刻度上。如果你希望某个概率区间恰好对应一个整数刻度本质就是在问哪个 n 最小。还有抽样间隔设计。在定时器中断里当两个触发事件之间的时间比例落在某个区间内我们常常需要找一个最小公倍数的近似倍数使得两个事件正好差一个计数节拍。这类问题都可以用 Stern-Brocot 树直接求解。6.2 如果想夹住 k 个整数怎么办原题要求恰好夹住一个整数稍作扩展如果要求开区间 (a×n, b×n) 内恰好有 k 个整数呢利用前面的计数公式条件变成⌈B⌉ - ⌊A⌋ - 1 k暴力枚举依然可行但效率不高。快速解法可以这样考虑先找到一个 n0让区间内至少出现 k 个整数然后再向前找边界。不过因为 ⌈B⌉ 和 ⌊A⌋ 都是阶梯函数边界往往不是平滑的需要结合 Stern-Brocot 树做分段搜索。坦白说这个问题我到现在也没有找到一个像原题这样干净漂亮的解法一般直接用“倍增 二分”的思路处理先按指数增长找上界再在区间里二分。如果你有更好的数学构造很值得写一篇文章分享。6.3 一个常被人忽略的小技巧最后分享一个我在实际使用中发现的细节当 a、b 都是有限小数时先把它俩转成最简分数再输入 Stern-Brocot 树速度会更快因为比较时涉及的整数更小。比如直接传 Fraction(0.4) 和 Fraction(0.5)Python 内部会把 0.4 当成 3602879701896397/9007199254740992 这种超大分数但你先手动转为 2/5 和 1/2所有整数运算的规模会小好几个量级。虽然最终答案一样但多花一行代码体验完全不同。这个问题让我印象最深的一点是它把“搜索”和“数论”连接得如此自然。表面上你只是在找一个最小的 n实际上你却在地图里展开了一棵 Stern-Brocot 树让所有有理数按分母大小排队等你检索。下次再遇到类似“区间内找最小分母”的需求别忘了这棵树。 区间内找最小分母有理数：Stern-Brocot树算法与Python实现
0.3 和 0.7 这两个数盯着看一下你能找出一个最小的正整数 n让 0.3×n 和 0.7×n 之间恰好夹着一个整数吗答案是 20.6 和 1.4 之间正好卡着整数 1。这个看起来像脑筋急转弯的问题其实背后是一道非常经典的数论应用题——本质上是在区间 (0.3, 0.7) 里找一个分母最小的有理数1/2 的分母就是 2。我最早遇到这个需求是在做“把连续概率区间映射到整数刻度”的时候。后来发现类似的问题在音频重采样、数据分箱、抽样间隔设计里都会冒出来给定一个取值在 0 到 1 之间的小数区间放大整数倍后想要恰好圈住一个整数这时最小的倍数是多少。这篇文章就把这个问题的数学本质、三种解法、完整代码和实际踩坑点一次讲清楚你拿来就能直接跑。1. 先把问题用数学语言说清楚1.1 一个具体例子先找找感觉设两个小数为 a、b且 0 a b 1。题目要求找一个最小的正整数 n让 a×n 和 b×n 这两个数之间恰好有一个整数。先看几组例子ab最小 n放大后区间区间内的整数0.30.72(0.6, 1.4)10.10.34(0.4, 1.2)10.40.57(2.8, 3.5)30.60.658(4.8, 5.2)5注意前两个例子的答案一眼能试出来但 0.4 和 0.5 的例子就有点反直觉了。n2 时区间是 (0.8, 1.0)整数 1 落在右端点上算不算“中间恰好间隔一个整数”这在题目里是有歧义的。我下面默认使用开区间语义两个数之间的整数不能等于端点本身。这样 0.4 和 0.5 的最小 n 就不是 2而是 7。如果你用的是闭区间语义结果会不一样这部分在第 4 节我会专门讲。1.2 区间内整数个数怎么精确计算要判断 n 是不是答案不能靠肉眼需要精确计算开区间 (a×n, b×n) 内到底有几个整数。设 A a×nB b×n那么开区间 (A, B) 内整数的个数为N(n) ⌈B⌉ - ⌊A⌋ - 1其中 ⌈⌉ 是向上取整⌊⌋ 是向下取整。这个公式很容易验算A0.6B1.4 时⌈1.4⌉2⌊0.6⌋02-0-11正确A2.8B3.5 时⌈3.5⌉4⌊2.8⌋24-2-11正好只有整数 3。于是问题变成了求最小的正整数 n使 N(n) 1。这个形式很适合写程序但直接按 n1、2、3... 一个个试下去遇到答案很大的情况会很慢。想知道怎么快起来就得先看问题的数学本质。2. 数学本质答案藏在一个有理数区间里2.1 整数 m 和分数 m/n 是一一对应的假设开区间 (a×n, b×n) 里有一个整数 m也就是a×n m b×n两边同时除以 n得到a m/n b这一步是整道题的题眼。它告诉我们找到最小的 n等价于找到开区间 (a, b) 内的一个有理数 m/n使得分母 n 最小。反过来也一样如果开区间 (a, b) 里存在一个最简分数 m/n那么把两边同时乘以 n整数 m 就一定落在 (a×n, b×n) 内。所以问题转化成在实数区间 (a, b) 里找到分母最小的正有理数这个分母就是要求的 n。2.2 为什么“恰好一个整数”等于“最小分母分数”你可能会追问如果区间里有两个整数 m1、m2那对应的两个分数 m1/n、m2/n 都在 (a, b) 内虽然 n 是其中一个分数的分母但区间里不就有两个整数了吗这不就不满足“恰好一个”了吗关键在于如果区间内有两个分母同为 n 的分数那么这两个分数之间一定会夹着一个分母更小的分数。这是 Farey 序列和 Stern-Brocot 树的一个基本性质两个既约分数之间的某个位置总会插入一个“更简单”的分数其分母不超过两个分母之和。举一个直观例子如果区间同时包含 1/3 和 2/3那么 1/2 一定也在它们之间因为 1/3 1/2 2/3而 1/2 的分母 2 比 3 小。如果区间能同时装下两个分母为 n 的分数那它必然也装下了一个分母更小的分数也就意味着存在一个比 n 更小的倍数已经满足条件。因此最小分母分数所在的那个 n开区间内必然是恰好一个整数不会多。这也是为什么我用 Stern-Brocot 树直接找最小分母非常稳找到的分数自带“区间内唯一整数”的保证。2.3 区间内最小分母分数是怎么分布的把所有正有理数按分母从小到大排开你会发现它们并不是均匀分布的。Stern-Brocot 树就是专门处理这种“按分母大小找有理数”的数据结构它本质上是一棵无限二叉树根节点是 1/1每个节点的左右孩子由相邻两个分数求“中项分数”得到中项分数的分子、分母分别等于两个相邻分数的分子之和、分母之和。比如 0/1 和 1/0代表无穷大的中项是 1/11/1 和 1/0 的中项是 2/11/1 和 0/1 的中项是 1/2依此类推。整棵树按中序遍历出来恰好是所有正有理数按大小排列而且访问顺序天然倾向于“先小分母、后大分母”。这正好命中我们的需求在区间 (a, b) 里找第一个被访问到的分数它的分母就是最小分母。3. 三种解法与代码实现3.1 方法一暴力枚举 n最直白但可能最慢最没有技术含量的做法就是从 n1 开始每次计算 N(n) 是不是等于 1from math import floor, ceil def brute_force(a, b): n 1 while True: A a * n B b * n cnt ceil(B) - floor(A) - 1 if cnt 1: return n n 1这个方法的优点是正确性一眼能看出来缺点也很明显当 a 和 b 非常接近时答案可能非常大。比如 a0.41421356b0.41421357区间宽度只有 1e-8最小分母可能是几十万甚至几百万暴力枚举会非常吃力。不过大多数日常场景下答案都不大暴力枚举其实够用。我在后面第 5 节的完整代码里保留了这个函数专门用来做交叉验证。3.2 方法二Stern-Brocot 树直接搜最小分母这是我最推荐的方法复杂度低、实现简单、不容易出错。算法流程是这样的维护两个相邻分数 left 和 right初始时 left 0/1right 1/0表示无穷大。计算中项分数 med (left分子 right分子) / (left分母 right分母)。如果 med ≤ a说明中项分数在区间左边让 left med否则如果 med ≥ b说明中项分数在区间右边让 right med否则 med 落在 (a, b) 内直接返回 med它的分母就是答案 n。写成 Python 大概是def stern_brocot_min_denom(a, b): # a, b 是 Fraction 类型且 0 a b def frac_le(x, y): return x[0] * y[1] y[0] * x[1] # x/y ? 这里x(p,q), y(r,s) def frac_le_or_eq(x, y): return x[0] * y[1] y[0] * x[1] left (0, 1) right (1, 0) # 表示 ∞ # 开区间 (a, b) while True: med (left[0] right[0], left[1] right[1]) # 比较 med a ? if frac_le_or_eq(med, a): left med elif frac_le_or_eq(b, med): # b med right med else: return med用 0.4 和 0.5 这个例子手动跑一遍过程非常清晰迭代次数leftrightmedmed 值判断10/11/01/11.0≥ bright 变成 1/120/11/11/20.5开区间内等于右端点不算right 变成 1/230/11/21/30.3333≤ aleft 变成 1/341/31/22/50.4等于左端点不算left 变成 2/552/51/23/70.4286在区间内返回 3/7最后得到 n7和暴力枚举结果一致。这个算法的迭代次数大约和答案的数值量级成对数关系哪怕答案是几百万通常也只有几十次循环非常快。它的正确性来源于 Stern-Brocot 树的性质树中第一个落入区间的分数就是区间内分母最小的分数。这个结论可以直接当作定理使用。3.3 方法三对整数 m 做区间覆盖扫描除了枚举 n还可以换一个角度枚举整数 m。对于每个正整数 m满足 a×n m b×n 的 n 必须满足m/b n m/a所以每个 m 都对应一个开区间 (m/b, m/a)。我们要找的 n就是第一个被这些区间覆盖的正整数。对每个 m区间内最小的候选 n 是L_m ⌊m/b⌋ 1只要验证 L_m m/a就说明 m 对应的区间覆盖了这个 n。于是可以从小到大遍历 m记录全局最小的 L_mdef scan_by_m(a, b): m 1 best None while True: L int(m // b) 1 # floor(m/b) 1 if L m / a: best L break m 1 return best这个方法在数学上很优雅但复杂度和暴力枚举其实是同一量级因为 L_m ≈ m/bm 增长到答案量级才会命中。它更适合作为理解题目的辅助工具实际求解时我还是优先用 Stern-Brocot 树。3.4 三种方法对比方法思路时间复杂度适用场景暴力枚举 n从 1 开始逐个检查O(n)答案很大时慢简单验证、答案较小时Stern-Brocot 树按分母从小到大搜索区间O(log n)非常快通用推荐枚举 m 区间覆盖从分数角度扫描O(n)教学演示、理解本质三种方法我都保留在完整代码里互相验证确保结果一致。4. 踩坑与细节从能跑到跑对4.1 用 Fraction 而不是 float 做区间端点这个坑我一开始踩得很深。Python 的 float 在读入小数时会引入二进制误差比如 0.3 实际存储为 0.2999999999999999888977697537480.1 0.2 甚至会得到 0.30000000000000004。如果拿 float 去和区间端点比较可能会在边界处判断错误尤其当答案对端点敏感时。最好的方式是使用fractions.Fraction。Python 的Fraction(0.4)可以精确表示 0.4 为 2/5完全不会丢失精度。Stern-Brocot 树的比较也需要整数运算用 Fraction 天然合适。4.2 开区间和闭区间的差异非常大“中间恰好间隔一个整数”这句话很多人会忽略端点问题。如果整数刚好落在左端点或右端点到底算不算闭区间 [a×n, b×n]0.4 和 0.5 在 n2 时区间是 [0.8, 1.0]整数 1 在区间内答案就是 2。开区间 (a×n, b×n)严格来说 1 是右端点不算答案变成 7。我在工程实践中更常用开区间因为“两个数之间夹着一个整数”通常描述的是中间位置端点不算数。如果你确实需要闭区间语义Stern-Brocot 代码里只要把比较条件从“med ≤ a 则 left med”改成“med a 则 left med”把“b ≤ med 则 right med”改成“b med 则 right med”即可。4.3 端点 a0 或 b1 时不要慌虽然题目说两个 1 以内的小数但实际使用时 a 有可能是 0b 有可能是 1。a0 时开区间 (0, b×n) 内找整数其实就是在区间 (0, b) 内找最小分母的有理数。比如 a0b0.2暴力枚举会发现 n5 时区间是 (0, 1.0)开区间内没有整数但 n6 时区间是 (0, 1.2)整数 1 出现了。Stern-Brocot 树从 0/1 出发最终也会返回 1/6n6。b1 时同理1/1 是右端点开区间内不算。Stern-Brocot 树会先把 right 调整到 1/1再继续搜不会出错。关键是不要在初始化时把 right 直接设成 (1,1)一定要从 (1,0) 这个“无穷大”开始让树自己收敛。4.4 区间窄到离谱时的性能问题如果 a、b 非常接近比如 a0.123456789b0.123456790暴力枚举可能要跑几百万次这会很慢。Stern-Brocot 树则完全不受影响它每步都在按分母从小到大的顺序逼近区间不会做无效尝试。不过要注意的是Stern-Brocot 树的比较全程使用 Fraction 运算如果 a、b 的小数位特别多Fraction 的分子分母会很大但因为每一步都是整数乘法开销可控。4.5 写完代码一定要做验证我不太相信“看起来对”的代码。就算用了 Stern-Brocot 树我也一定会再写一个暴力函数把每组测试用例跑两遍两边答案一致才放心。原因很简单区间语义差一个符号结果就可能天差地别而暴力枚举虽然慢但逻辑最简单最适合当“标准答案”。完整代码里我加了verify(a, b, n)函数专门检查开区间内整数个数是否恰好为 1。这是个值得养成的习惯。5. 完整可运行的示例代码下面是一份完整的 Python 脚本包含暴力验证、Stern-Brocot 求解和一组测试用例。代码里用 Fraction 处理精度用开区间语义你可以直接复制运行。from fractions import Fraction from math import floor, ceil def count_ints_open(a, b, n): 返回开区间 (a*n, b*n) 内的整数个数 A a * n B b * n return max(0, ceil(B - Fraction(0)) - floor(A Fraction(0)) - 1)这里我稍微绕了一下是为了用 Fraction 取整。更直接一点其实是把 A、B 转成分数后手动算def fraction_ceil(x): return -(-x.numerator // x.denominator) def fraction_floor(x): return x.numerator // x.denominator def count_ints_open(a, b, n): A a * n B b * n return max(0, fraction_ceil(B) - fraction_floor(A) - 1) def brute_force(a, b): n 1 while True: if count_ints_open(a, b, n) 1: return n n 1 def fraction_tuple_le(x, y): # x (p, q), y (r, s)返回 x y return x[0] * y[1] y[0] * x[1] def stern_brocot_min_denom(a, b): if a b: raise ValueError(需要 a b) left (0, 1) right (1, 0) # 代表无穷大 while True: med (left[0] right[0], left[1] right[1]) if fraction_tuple_le(med, a): left med elif fraction_tuple_le(b, med): right med else: return med tests [ (Fraction(0.3), Fraction(0.7)), (Fraction(0.1), Fraction(0.3)), (Fraction(0.4), Fraction(0.5)), (Fraction(0.6), Fraction(0.65)), (Fraction(0), Fraction(0.2)), (Fraction(0.8), Fraction(1)), ] for a, b in tests: med stern_brocot_min_denom(a, b) n med[1] bf brute_force(a, b) cnt count_ints_open(a, b, n) print(fa{a}, b{b}, Stern_Brocot结果{med[0]}/{med[1]}, n{n}, 暴力结果{bf}, 整数个数{cnt}, 一致{n bf and cnt 1})运行这段代码你会得到类似下面这样的输出a3/10, b7/10, Stern_Brocot结果1/2, n2, 暴力结果2, 整数个数1, 一致True a1/10, b3/10, Stern_Brocot结果1/4, n4, 暴力结果4, 整数个数1, 一致True a2/5, b1/2, Stern_Brocot结果3/7, n7, 暴力结果7, 整数个数1, 一致True a3/5, b13/20, Stern_Brocot结果5/8, n8, 暴力结果8, 整数个数1, 一致True a0, b1/5, Stern_Brocot结果1/6, n6, 暴力结果6, 整数个数1, 一致True a4/5, b1, Stern_Brocot结果5/6, n6, 暴力结果6, 整数个数1, 一致True注意第三行a0.4 等价于 2/5b0.5 等价于 1/2开区间 (2/5, 1/2) 内的最小分母分数是 3/7。这个结果如果不做精确 Fraction 运算很容易因为 0.5 和 1/2 的浮点表示差异而出错。6. 实际场景与扩展思考6.1 工程里哪里会用到这种“最小分母有理数”这类问题不是纯数学游戏在工程里经常以另一种面貌出现给定一个取值范围希望找到一个分母尽可能小的有理数落在里面。典型例子是音频重采样。假设你有一个音频文件原始采样率是 44100Hz想转换到目标设备的 48000Hz实际做插值计算时经常要找一个“等效比例”落在某个容差区间内缩放因子就是有理数 m/n。如果 n 太大硬件缓存的延迟和内存开销都会变大如果能找到分母最小的有理数近似工程开销会小很多。这和本题的数学结构完全一样。另一个例子是数据分箱。当你有一堆 0 到 1 之间的概率值想映射到整数区间做可视化或统计时会先乘以一个放大系数 n让落在 [0, 1] 区间内的概率能对应到整数刻度上。如果你希望某个概率区间恰好对应一个整数刻度本质就是在问哪个 n 最小。还有抽样间隔设计。在定时器中断里当两个触发事件之间的时间比例落在某个区间内我们常常需要找一个最小公倍数的近似倍数使得两个事件正好差一个计数节拍。这类问题都可以用 Stern-Brocot 树直接求解。6.2 如果想夹住 k 个整数怎么办原题要求恰好夹住一个整数稍作扩展如果要求开区间 (a×n, b×n) 内恰好有 k 个整数呢利用前面的计数公式条件变成⌈B⌉ - ⌊A⌋ - 1 k暴力枚举依然可行但效率不高。快速解法可以这样考虑先找到一个 n0让区间内至少出现 k 个整数然后再向前找边界。不过因为 ⌈B⌉ 和 ⌊A⌋ 都是阶梯函数边界往往不是平滑的需要结合 Stern-Brocot 树做分段搜索。坦白说这个问题我到现在也没有找到一个像原题这样干净漂亮的解法一般直接用“倍增 二分”的思路处理先按指数增长找上界再在区间里二分。如果你有更好的数学构造很值得写一篇文章分享。6.3 一个常被人忽略的小技巧最后分享一个我在实际使用中发现的细节当 a、b 都是有限小数时先把它俩转成最简分数再输入 Stern-Brocot 树速度会更快因为比较时涉及的整数更小。比如直接传 Fraction(0.4) 和 Fraction(0.5)Python 内部会把 0.4 当成 3602879701896397/9007199254740992 这种超大分数但你先手动转为 2/5 和 1/2所有整数运算的规模会小好几个量级。虽然最终答案一样但多花一行代码体验完全不同。这个问题让我印象最深的一点是它把“搜索”和“数论”连接得如此自然。表面上你只是在找一个最小的 n实际上你却在地图里展开了一棵 Stern-Brocot 树让所有有理数按分母大小排队等你检索。下次再遇到类似“区间内找最小分母”的需求别忘了这棵树。