整数转罗马数字(Integer to Roman Numeral):Python 贪心查表法的完整实现与原理剖析
整数转罗马数字(Integer to Roman Numeral):Python 贪心查表法的完整实现与原理剖析
导读
to_roman_numeral 是 30-seconds-of-python 仓库中一个短小精悍的数学与字符串处理片段,用于将 1 到 3999(含边界)范围内的整数转换为对应的罗马数字表示。它利用"贪心 + 查表"策略,配合 Python 内置的 divmod(),将传统上繁琐的罗马数字规则压缩为十余行代码。读完本文,你将掌握罗马数字的表示规则、divmod() 的底层语义、查表顺序为何必须从大到小,以及如何将该片段扩展到真实业务场景。
片段速览:完整源码与用法
原始文档位于 snippets/to-roman-numeral.md,核心实现如下:
def to_roman_numeral(num):
lookup = [
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'CD'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I'),
]
res = ''
for (n, roman) in lookup:
(d, num) = divmod(num, n)
res += roman * d
return res
三个典型调用结果:
to_roman_numeral(3) # 'III'
to_roman_numeral(11) # 'XI'
to_roman_numeral(1998) # 'MCMXCVIII'
函数的适用前提是输入 num 位于 [1, 3999] 闭区间内,该约束直接对应罗马数字在传统记法下的可表示范围(最大可记的 3999 即 MMMCMXCIX)。文档并未在函数体内做显式校验,调用方需自行保证输入合法,这一点在使用时需要格外留意。
罗马数字表示规则:为什么需要 13 个查表项
要把整数正确转换为罗马数字,必须先理解其表示规则。标准罗马数字体系由 7 个基础符号构成:
| 符号 | 数值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
除了基础的累加记法(如 VI 表示 6),还存在"减性记法":较小的数字放在较大数字左侧时表示相减,例如 IV 表示 4(5 − 1)、IX 表示 9(10 − 1)。正是这组特殊组合,让查表法需要额外引入 6 个复合条目(CM、CD、XC、XL、IX、IV),再加上 7 个基础符号,共 13 个查表项。
以 1998 为例可以直观体会这套规则:
1998 = 1000 + 900 + 90 + 5 + 1 + 1 + 1
= M + CM + XC + V + I + I + I
= 'MCMXCVIII'
为何上限是 3999
由于传统罗马数字没有表示 4000 及以上数值的规范符号(虽然存在带横线的扩展记法,如 MMMM 或 ↀ,但均非常规),因此 3999 成为标准记法下能表达的最大整数。3999 = MMMCMXCIX,恰好对应查表中从 1000 到 1 的全部条目被使用的极端情况。这也是该片段在文档中明确标注输入范围为 1~3999 的数学根源。
贪心查表:算法的核心思想
该片段采用的策略本质上是贪心算法(greedy algorithm)。它的思想非常直接:
每一步都优先使用当前可用的最大面额,尽可能多地消费掉剩余数值,然后继续处理余数。
查表条目的排列顺序至关重要——lookup 必须严格按数值从大到小排列。处理 1998 时,程序会先从 1000 开始:1998 // 1000 = 1,于是写入一个 M;接着处理余数 998,查表项 900 恰好命中,写入 CM……以此类推。若顺序打乱,贪心策略将无法保证生成最短且合法的罗马数字。
一个容易忽略的细节是:查表中的 900、400、90、40、9、4 这些复合值正是对"减性记法"的显式编码。贪心算法本身并不会自动生成 IV 这类组合——如果没有这些复合查表项,4 会被分解成 IIII(4 个 I),这在传统罗马数字记法中是不规范的。正是通过把减性记法固化为查表条目,算法才在保持简单的逐项除法逻辑的同时,天然规避了"四连重复"的非法写法。
算法步骤还原
按原文档的说明,整个转换过程分为三步:
- 建立查表:创建形如
(罗马数值, 整数)的元组列表lookup,覆盖所有基础符号与减性组合; - 迭代查表:用
for循环按数值从大到小遍历lookup; - 整除与取余:对每个条目用
divmod()同时求出商d和余数,把roman * d追加到结果字符串,并用余数更新num继续下一轮。
divmod():一个调用同时拿到商和余数
divmod() 是 Python 内置函数,它一次返回包含两个元素的元组:第一个元素是 a // b 的整数商,第二个是 a % b 的余数。例如:
divmod(1998, 1000) # (1, 998)
在片段中:
(d, num) = divmod(num, n)
d:当前面额n在剩余值num中出现的次数,直接决定roman符号要重复拼接几次(res += roman * d);num:被立即更新为余数,作为下一轮查表的基础,因此无需手动维护中间变量。
比起分开调用 num // n 和 num % n,divmod() 让代码更紧凑,也避免了两次除法带来的重复计算。这与仓库中其他数学片段的风格一致——例如 digitize.md 用 map(int, str(n)) 拆分数字、num-to-range.md 用比例映射区间,都是以最少的 Python 内置能力完成核心逻辑。
逐轮推演:1998 → 'MCMXCVIII'
以 to_roman_numeral(1998) 为例,完整推演如下:
| 轮次 | 查表值 n | divmod 结果 (d, 余数) | 拼接 |
|---|---|---|---|
| 1 | 1000 | (1, 998) | 'M' |
| 2 | 900 | (1, 98) | 'MCM' |
| 3 | 500 | (0, 98) | 'MCM' |
| 4 | 400 | (0, 98) | 'MCM' |
| 5 | 100 | (0, 98) | 'MCM' |
| 6 | 90 | (1, 8) | 'MCMXC' |
| 7 | 50 | (0, 8) | 'MCMXC' |
| 8 | 40 | (0, 8) | 'MCMXC' |
| 9 | 10 | (0, 8) | 'MCMXC' |
| 10 | 9 | (0, 8) | 'MCMXC' |
| 11 | 5 | (1, 3) | 'MCMXCV' |
| 12 | 4 | (0, 3) | 'MCMXCV' |
| 13 | 1 | (3, 0) | 'MCMXCVIII' |
注意中间若干轮(如 500、400、100 等)的商为 0,此时 roman * 0 得到空字符串,结果保持不变,循环得以快速跳过不适用的面额。最终余数归零,返回 'MCMXCVIII'。
边界情况与输入校验
虽然文档声明输入范围为 [1, 3999],但函数本身没有防御性校验。实际使用时应考虑:
def to_roman_numeral_safe(num):
if not 1 <= num <= 3999:
raise ValueError("num must be between 1 and 3999")
lookup = [ ... ] # 同前
res = ''
for (n, roman) in lookup:
(d, num) = divmod(num, n)
res += roman * d
return res
需要关注的行为包括:
num = 1:走完循环后得到'I',是最小合法输入;num = 3999:得到'MMMCMXCIX',是最大合法输入;num = 0:所有除法商均为 0,返回空字符串''(非法,因为罗马数字没有 0 的表示);num < 0:除法语义异常,结果不可预期;num > 3999:没有对应的查表条目,会退化成多段累加符号,产生非规范结果。
从代码结构看,若需要投入生产使用,最稳妥的做法是在函数入口处增加上述 ValueError 校验,将非法输入拦截在转换之前。
复杂度与工程价值
时间复杂度:查表长度固定为 13,每次迭代执行常数次整数除法与字符串拼接,因此整体为 O(1)(常数时间),与输入数值大小无关——这也是该片段适合高频调用的重要原因。
空间复杂度:仅需一个固定大小的查表与结果字符串,为 O(1) 级辅助空间(输出字符串长度本身与输入成正比,最多约 15 个字符)。
工程价值:该实现把"规则驱动"的转换问题转化为"数据驱动"的查表问题,具有以下可迁移性:
- 逻辑简单、无分支嵌套,便于代码审查与测试;
- 查表可扩展——只要维护好有序表项,就能轻松适配其他进制或符号体系的转换;
- 与 to-binary.md(
bin()转二进制)、to-hex.md(hex()转十六进制)形成互补:后两者依赖 Python 内置进制转换,而罗马数字无内置支持,必须自建算法,本片段正是这一场景的最小完备实现。
常见应用场景
罗马数字在现实开发中仍有不少用途:
- 文件命名与版本号:如
Chapter_IV.md、v1.II等格式化输出; - 时间与日期:表盘刻度(
I~XII)、月份的罗马记法; - 图书目录:前言与正文部分的罗马页码;
- 合规展示:法律文书、序章、荣誉编号等需要正式记法的场合。
使用时只需调用 to_roman_numeral(n) 并自行处理输入范围即可。若需反向转换,可参考仓库中其他查表思路自行扩展,本片段未包含该部分。
小结
to_roman_numeral 用 13 个查表条目与 divmod() 的组合,完整覆盖了罗马数字从 1 到 3999 的全部表示规则,是"贪心 + 查表"范式在 Python 中的典型范例。它的核心要点可归纳为三条:查表必须按数值从大到小排列;减性记法(4、9、40、90、400、900)必须显式编码为查表项;divmod() 一次调用同时解决"取符号数量"与"更新余数"两个问题。对于任何需要在代码中输出罗马数字的场景,这一片段都是开箱即用的可靠选择。