整数转罗马数字(Integer to Roman Numeral):Python 贪心查表法的完整实现与原理剖析

原创2026-10-14 10:20:051,047 阅读
文章标签:教程文档

整数转罗马数字(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),这在传统罗马数字记法中是不规范的。正是通过把减性记法固化为查表条目,算法才在保持简单的逐项除法逻辑的同时,天然规避了"四连重复"的非法写法。

算法步骤还原

按原文档的说明,整个转换过程分为三步:

  1. 建立查表:创建形如 (罗马数值, 整数) 的元组列表 lookup,覆盖所有基础符号与减性组合;
  2. 迭代查表:用 for 循环按数值从大到小遍历 lookup;
  3. 整除与取余:对每个条目用 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() 一次调用同时解决"取符号数量"与"更新余数"两个问题。对于任何需要在代码中输出罗马数字的场景,这一片段都是开箱即用的可靠选择。

登录后查看全文
30-seconds-of-python