Algorytmy liczb rzymskich: Implementacja w Python, JavaScript i Java

Konwersja między liczbami rzymskimi a całkowitymi to klasyczny problem programistyczny, który pojawia się na rozmowach kwalifikacyjnych, w programowaniu konkurencyjnym i rzeczywistych aplikacjach. Ten przewodnik zawiera zoptymalizowane implementacje w językach Python, JavaScript i Java wraz z wyjaśnieniem stosowanych algorytmów.

Zrozumienie problemu

Musimy rozwiązać dwa powiązane problemy:

1. Integer na rzymskie: Konwersja liczby arabskiej (np. 1994) na rzymską (MCMXCIV).
2. Rzymskie na całkowite: Konwersja liczb rzymskich (np. MCMXCIV) na arabskie (1994).

Ograniczenia

• Zakres wejściowy: od 1 do 3999 (standardowy zakres liczb rzymskich).
• Użycie standardowej notacji odejmowania (IV, IX, XL, XC, CD, CM).
• Obsługa wszystkich poprawnych kombinacji znaków rzymskich.

Podejście zachłanne (Greedy Algorithm)

Obie konwersje wykorzystują strategię algorytmu zachłannego:

Integer na rzymskie (Zachłanny)

1. Stwórz mapowanie wartości na symbole rzymskie w porządku malejącym.
2. Dla każdej pary wartość-symbol:
   • Użyj tyle symboli, ile się da.
   • Odejmij wartość od pozostałej liczby.
3. Powtarzaj, aż liczba osiągnie zero.

Rzymskie na całkowite (Zachłanny)

1. Skanuj ciąg rzymski od lewej do prawej.
2. Dla każdego symbolu:
   • Jeśli jest mniejszy od następnego, odejmij go (notacja odejmowania).
   • W przeciwnym razie dodaj go.
3. Zwróć skumulowaną sumę.

Implementacja w Python

Integer na rzymskie

def int_to_roman(num: int) -> str:
    """
    Konwertuje liczbę całkowitą na rzymską.

    Złożoność czasowa: O(1) - stała liczba iteracji (13)
    Złożoność pamięciowa: O(1)
    """
    # Mapowanie w porządku malejącym
    values = [
        (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, numeral in values:
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)

Rzymskie na całkowite

def roman_to_int(s: str) -> int:
    """
    Konwertuje liczbę rzymską na całkowitą.

    Złożoność czasowa: O(n) gdzie n to długość ciągu
    Złożoność pamięciowa: O(1)
    """
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }

    result = 0
    prev_value = 0

    # Skanowanie od prawej do lewej
    for char in reversed(s):
        value = roman_map[char]

        if value < prev_value:
            result -= value
        else:
            result += value

        prev_value = value

    return result

Implementacja w JavaScript

Integer na rzymskie

function intToRoman(num) {
    const values = [
        [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']
    ];

    let result = '';

    for (const [value, numeral] of values) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }

    return result;
}

Analiza algorytmu

Złożoność czasowa

Integer na rzymskie:

• O(1) - Czas stały. Algorytm zawsze przechodzi przez dokładnie 13 par wartości.

Rzymskie na całkowite:

• O(n) - Czas liniowy. Musimy zbadać każdy znak ciągu wejściowego dokładnie raz.

Dlaczego algorytm zachłanny działa?

Algorytm zachłanny sprawdza się w przypadku liczb rzymskich, ponieważ:

1. Optymalna podstruktura: Optymalne rozwiązanie zawiera w sobie optymalne rozwiązania podproblemów.
2. Brak nakładających się podproblemów: Każda wartość jest używana niezależnie.
3. Wybór największej możliwej wartości gwarantuje najkrótszy możliwy zapis rzymski.

Podsumowanie

Algorytmy konwersji liczb rzymskich to doskonały przykład wykorzystania podejścia zachłannego. Przedstawione implementacje są wydajne, czytelne i odporne na błędy w standardowym zakresie 1-3999.

Jeśli potrzebujesz narzędzia do konwersji bez pisania własnego kodu, wypróbuj nasz konwerter liczb rzymskich online zapewniający natychmiastowe wyniki.

---

Chcesz wiedzieć więcej? Sprawdź nasz kompletny przewodnik po cyfrach rzymskich lub dowiedz się jak używać liczb rzymskich w Excelu.