如何实现罗马数字的转化

# 如何实现罗马数字的转化

## 引言

罗马数字是古罗马人使用的一种数字表示方法，由特定的字母组合表示不同的数值。尽管现代社会中阿拉伯数字更为常用，但罗马数字仍广泛应用于钟表、书籍页码、电影发行年份等场景。理解罗马数字的规则并实现其与阿拉伯数字之间的相互转化，不仅有助于理解历史数字系统，也是编程面试中的常见题目。本文将详细介绍罗马数字的构成规则，并提供具体的转化算法实现。

## 罗马数字的基本规则

罗马数字由以下七个基本符号组成，每个符号对应一个固定的数值：

| 罗马符号 | 对应数值 |
|----------|---------|
| I        | 1       |
| V        | 5       |
| X        | 10      |
| L        | 50      |
| C        | 100     |
| D        | 500     |
| M        | 1000    |

罗马数字的构成遵循以下核心规则：

1. **相加规则**：当较小的符号出现在较大符号的右侧时，将它们的值相加。例如：
   - `VI = 5 + 1 = 6`
   - `XV = 10 + 5 = 15`

2. **相减规则**：当较小的符号出现在较大符号的左侧时，用较大符号的值减去较小符号的值。例如：
   - `IV = 5 - 1 = 4`
   - `IX = 10 - 1 = 9`

3. **符号限制**：
   - `I` 只能出现在 `V` 和 `X` 的左侧。
   - `X` 只能出现在 `L` 和 `C` 的左侧。
   - `C` 只能出现在 `D` 和 `M` 的左侧。
   - 其他符号（如 `V`, `L`, `D`）不能用于减法表示。

4. **重复限制**：
   - `I`, `X`, `C`, `M` 可以重复最多三次（例如 `III = 3`）。
   - `V`, `L`, `D` 不能重复。

## 罗马数字转阿拉伯数字

### 算法思路
1. 创建一个映射表，将罗马符号对应到数值。
2. 初始化结果变量 `total = 0`。
3. 从左到右遍历罗马数字字符串：
   - 如果当前符号的值小于下一个符号的值，则从 `total` 中减去当前值（相减规则）。
   - 否则，将当前值加到 `total` 中（相加规则）。
4. 返回 `total`。

### Python实现
```python
def roman_to_int(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 
                 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev_value = 0
    
    for char in reversed(s):  # 从右向左遍历更直观
        current_value = roman_map[char]
        if current_value < prev_value:
            total -= current_value
        else:
            total += current_value
        prev_value = current_value
    return total

# 示例
print(roman_to_int("MCMXCIV"))  # 输出: 1994

复杂度分析

• 时间复杂度：O(n)，其中 n 是罗马数字字符串的长度。
• 空间复杂度：O(1)，仅使用固定大小的额外空间。

阿拉伯数字转罗马数字

算法思路

1. 创建一个按值从大到小排序的列表，包含罗马符号及其对应的数值。
2. 初始化结果字符串 result = ""。
3. 遍历列表中的每个符号：
   • 当当前数值大于等于符号值时，将该符号追加到 result 中，并减去对应的数值。
   • 重复直到当前数值小于符号值。
4. 返回 result。

Python实现

def int_to_roman(num: int) -> str:
    val_symbols = [
        (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")
    ]
    result = []
    
    for value, symbol in val_symbols:
        while num >= value:
            result.append(symbol)
            num -= value
        if num == 0:
            break
    return "".join(result)

# 示例
print(int_to_roman(1994))  # 输出: "MCMXCIV"

复杂度分析

• 时间复杂度：O(1)，因为 val_symbols 的长度固定（13个符号），最多循环常数次。
• 空间复杂度：O(1)，结果字符串的长度有限（最长罗马数字为3888的”MMMDCCCLXXXVIII”）。

边界情况与验证

输入验证

1. 罗马数字转阿拉伯数字：

   • 确保输入字符串只包含 IVXLCDM。
   • 检查符号顺序是否合法（如 IIV 是非法的）。

2. 阿拉伯数字转罗马数字：

   • 确保输入数字在 1~3999 范围内（传统罗马数字无零且上限为3999）。

测试用例

# 罗马转阿拉伯
assert roman_to_int("III") == 3
assert roman_to_int("LVIII") == 58
assert roman_to_int("MCMXCIV") == 1994

# 阿拉伯转罗马
assert int_to_roman(3) == "III"
assert int_to_roman(58) == "LVIII"
assert int_to_roman(1994) == "MCMXCIV"

扩展思考

1. 大数表示：传统罗马数字无法表示超过3999的数，但现代扩展中可通过在数字上方添加横线表示乘以1000（如 V̅=5000）。
2. 零的表示：古罗马没有零的概念，编程实现时需额外处理。
3. 非标准形式：如 IIII 有时用于钟表，需根据场景调整规则。

总结

罗马数字的转化核心在于理解其加减规则和符号限制。通过建立符号与数值的映射关系，并结合贪心算法（阿拉伯转罗马）或逆向遍历（罗马转阿拉伯），可以高效实现两者的相互转化。这一过程不仅锻炼了对历史数字系统的理解，也是算法设计与实现的经典案例。

”`