如何實現羅馬數字的轉化

# 如何實現羅馬數字的轉化

## 引言

羅馬數字是古羅馬人使用的一種數字表示方法，由特定的字母組合表示不同的數值。盡管現代社會中阿拉伯數字更為常用，但羅馬數字仍廣泛應用于鐘表、書籍頁碼、電影發行年份等場景。理解羅馬數字的規則并實現其與阿拉伯數字之間的相互轉化，不僅有助于理解歷史數字系統，也是編程面試中的常見題目。本文將詳細介紹羅馬數字的構成規則，并提供具體的轉化算法實現。

## 羅馬數字的基本規則

羅馬數字由以下七個基本符號組成，每個符號對應一個固定的數值：

| 羅馬符號 | 對應數值 |
|----------|---------|
| 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 有時用于鐘表，需根據場景調整規則。

總結

羅馬數字的轉化核心在于理解其加減規則和符號限制。通過建立符號與數值的映射關系，并結合貪心算法（阿拉伯轉羅馬）或逆向遍歷（羅馬轉阿拉伯），可以高效實現兩者的相互轉化。這一過程不僅鍛煉了對歷史數字系統的理解，也是算法設計與實現的經典案例。

”`