Romeinse cijfer algoritmen: Implementatie in Python, JavaScript & Java

Het converteren tussen Romeinse cijfers en integers is een klassiek programmeerprobleem dat voorkomt in technische interviews, competitief programmeren en praktijktoepassingen. Deze gids biedt geoptimaliseerde implementaties in Python, JavaScript en Java, samen met uitleg van de onderliggende algoritmen.

Het probleem begrijpen

We moeten twee gerelateerde problemen oplossen:

1. Integer naar Romeins: Converteer een Arabisch getal (bijv. 1994) naar Romeinse cijfers (MCMXCIV)
2. Romeins naar Integer: Converteer Romeinse cijfers (bijv. MCMXCIV) naar een Arabisch getal (1994)

Beperkingen

• Invoerbereik: 1 tot 3999 (standaard Romeinse cijferbereik)
• Gebruik standaard aftrekherschrijving (IV, IX, XL, XC, CD, CM)
• Verwerk alle geldige combinaties van Romeinse cijfers

De Greedy Algoritme benadering

Beide conversies maken gebruik van een greedy algoritme strategie:

Integer naar Romeins (Greedy)

1. Maak een mapping van waarden naar Romeinse cijfers in aflopende volgorde
2. Voor elk waarde-cijfer paar:
   • Gebruik zoveel mogelijk van dat cijfer
   • Trek de waarde af van het resterende getal
3. Herhaal dit totdat het getal nul bereikt

Romeins naar Integer (Greedy)

1. Scan de Romeinse cijferreeks van links naar rechts
2. Voor elk symbool:
   • Als het kleiner is dan het volgende symbool, trek het er dan van af (aftrekherschrijving)
   • Tel het anders op
3. Retourneer de verzamelde som

Python Implementatie

Integer naar Romeins

def int_to_roman(num: int) -> str:
    """
    Converteer een integer naar Romeinse cijfers.

    Args:
        num: Integer tussen 1 en 3999

    Returns:
        Romeinse cijferreeks

    Tijdcomplexiteit: O(1) - vast aantal iteraties (13)
    Ruimtecomplexiteit: O(1) - vaste grootte mapping
    """
    # Mapping in aflopende volgorde (inclusief aftrekcombinaties)
    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:
        # Hoe vaak past deze waarde?
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)


# Voorbeelden
print(int_to_roman(1994))   # MCMXCIV
print(int_to_roman(58))     # LVIII
print(int_to_roman(3999))   # MMMCMXCIX

Romeins naar Integer

def roman_to_int(s: str) -> int:
    """
    Converteer Romeinse cijfers naar een integer.

    Args:
        s: Romeinse cijferreeks

    Returns:
        Integer waarde

    Tijdcomplexiteit: O(n) waarbij n de lengte van de string is
    Ruimtecomplexiteit: O(1) - vaste grootte mapping
    """
    # Mapping van Romeinse cijfers naar waarden
    roman_map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }

    result = 0
    prev_value = 0

    # Scan van rechts naar links
    for char in reversed(s):
        value = roman_map[char]

        # Als de huidige waarde kleiner is dan de vorige, aftrekken
        if value < prev_value:
            result -= value
        else:
            result += value

        prev_value = value

    return result


# Voorbeelden
print(roman_to_int('MCMXCIV'))  # 1994
print(roman_to_int('LVIII'))    # 58
print(roman_to_int('IX'))       # 9

JavaScript Implementatie

Integer naar Romeins

/**
 * Converteer een integer naar Romeinse cijfers
 * @param {number} num - Integer tussen 1 en 3999
 * @returns {string} Romeinse cijferreeks
 */
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;
}

Java Implementatie

Integer naar Romeins

public class RomanConverter {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(numerals[i]);
                num -= values[i];
            }
        }

        return result.toString();
    }
}

Algoritme Analyse

Tijdcomplexiteit

Integer naar Romeins:

• O(1) - Constante tijd
• Doorloopt altijd precies 13 waarde-cijfer paren
• Onafhankelijk van de grootte van de invoer

Romeins naar Integer:

• O(n) - Lineaire tijd
• Waarbij n de lengte van de Romeinse cijferreeks is
• Elk karakter moet één keer worden onderzocht

Ruimtecomplexiteit

Beide algoritmen:

• O(1) - Constante ruimte
• Mappings van vaste grootte, ongeacht de invoer

Waarom het Greedy Algoritme werkt

Het greedy algoritme werkt voor Romeinse cijfers omdat:

1. Optimale substructuur: De optimale oplossing bevat optimale oplossingen voor deelproblemen.
2. Greedy choice property: Lokaal optimale keuzes leiden naar een globaal optimale oplossing.
3. Altijd de grootst mogelijke waarde eerst gebruiken garandeert de kortste Romeinse cijferweergave.

Conclusie

Algoritmen voor het converteren van Romeinse cijfers tonen de kracht van de greedy benadering aan. Of je je nu voorbereidt op programmeerinterviews of een documentgenerator bouwt, deze implementaties bieden een solide basis.

Voor een gebruiksvriendelijke interface zonder code te schrijven, kun je onze online Romeinse cijfer converter proberen voor direct resultaat.

---

Meer leren? Ontdek onze volledige gids voor Romeinse cijfers of bekijk hoe je Romeinse cijfers in Excel gebruikt.