Römische Zahlen Algorithmen: Python, JavaScript & Java Implementierung

Die Konvertierung zwischen römischen Zahlen und Ganzzahlen ist ein klassisches Programmierproblem, das in Coding-Interviews, Wettbewerbsprogrammierung und realen Anwendungen auftritt. Dieser Leitfaden bietet optimierte Implementierungen in Python, JavaScript und Java sowie Erklärungen der zugrunde liegenden Algorithmen.

Das Problem verstehen

Wir müssen zwei verwandte Probleme lösen:

1. Ganzzahl zu Römisch: Eine arabische Zahl (z.B. 1994) in römische Zahlen (MCMXCIV) konvertieren
2. Römisch zu Ganzzahl: Römische Zahlen (z.B. MCMXCIV) in eine arabische Zahl (1994) konvertieren

Einschränkungen

• Eingabebereich: 1 bis 3999 (Standard-Bereich römischer Zahlen)
• Verwendung der Standard-Subtraktionsnotation (IV, IX, XL, XC, CD, CM)
• Behandlung aller gültigen römischen Zahlenkombinationen

Der Greedy-Algorithmus-Ansatz

Beide Konvertierungen verwenden eine Greedy-Algorithmus-Strategie:

Ganzzahl zu Römisch (Greedy)

1. Erstellen Sie eine Zuordnung von Werten zu römischen Zahlen in absteigender Reihenfolge
2. Für jedes Wert-Ziffer-Paar:
   • Verwenden Sie so viele dieser Ziffer wie möglich
   • Subtrahieren Sie den Wert von der verbleibenden Zahl
3. Wiederholen Sie, bis die Zahl Null erreicht

Römisch zu Ganzzahl (Greedy)

1. Scannen Sie die römische Zahlenzeichenfolge von links nach rechts
2. Für jedes Symbol:
   • Wenn es kleiner als das nächste Symbol ist, subtrahieren Sie es (Subtraktionsnotation)
   • Andernfalls addieren Sie es
3. Geben Sie die akkumulierte Summe zurück

Python-Implementierung

Ganzzahl zu Römisch

def int_to_roman(num: int) -> str:
    """
    Convert an integer to Roman numerals.

    Args:
        num: Integer between 1 and 3999

    Returns:
        Roman numeral string

    Time Complexity: O(1) - fixed number of iterations (13)
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping in descending order (including subtractive combinations)
    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)

Römisch zu Ganzzahl

def roman_to_int(s: str) -> int:
    """
    Convert Roman numerals to an integer.

    Args:
        s: Roman numeral string

    Returns:
        Integer value

    Time Complexity: O(n) where n is the length of the string
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping of Roman symbols to values
    roman_map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }

    total = 0
    prev_value = 0

    # Scan from right to left
    for char in reversed(s):
        value = roman_map[char]

        # If current value is less than previous, subtract it
        if value < prev_value:
            total -= value
        else:
            total += value

        prev_value = value

    return total

Verwendungsbeispiele

# Ganzzahl zu Römisch
print(int_to_roman(1994))  # Output: MCMXCIV
print(int_to_roman(58))    # Output: LVIII
print(int_to_roman(9))     # Output: IX

# Römisch zu Ganzzahl
print(roman_to_int("MCMXCIV"))  # Output: 1994
print(roman_to_int("LVIII"))    # Output: 58
print(roman_to_int("IX"))       # Output: 9

JavaScript-Implementierung

Ganzzahl zu Römisch

/**
 * Convert an integer to Roman numerals
 * @param {number} num - Integer between 1 and 3999
 * @returns {string} Roman numeral string
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
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) {
        const count = Math.floor(num / value);
        if (count) {
            result += numeral.repeat(count);
            num -= value * count;
        }
    }

    return result;
}

Römisch zu Ganzzahl

/**
 * Convert Roman numerals to an integer
 * @param {string} s - Roman numeral string
 * @returns {number} Integer value
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function romanToInt(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let total = 0;
    let prevValue = 0;

    // Scan from right to left
    for (let i = s.length - 1; i >= 0; i--) {
        const value = romanMap[s[i]];

        if (value < prevValue) {
            total -= value;
        } else {
            total += value;
        }

        prevValue = value;
    }

    return total;
}

Verwendungsbeispiele

// Ganzzahl zu Römisch
console.log(intToRoman(1994));  // Output: MCMXCIV
console.log(intToRoman(58));    // Output: LVIII
console.log(intToRoman(9));     // Output: IX

// Römisch zu Ganzzahl
console.log(romanToInt("MCMXCIV"));  // Output: 1994
console.log(romanToInt("LVIII"));    // Output: 58
console.log(romanToInt("IX"));       // Output: 9

Java-Implementierung

Ganzzahl zu Römisch

/**
 * Convert an integer to Roman numerals
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
public class RomanConverter {
    private static final int[] VALUES = {
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
    };

    private static final String[] NUMERALS = {
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    };

    public static String intToRoman(int num) {
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < VALUES.length; i++) {
            int count = num / VALUES[i];
            if (count > 0) {
                result.append(NUMERALS[i].repeat(count));
                num -= VALUES[i] * count;
            }
        }

        return result.toString();
    }
}

Römisch zu Ganzzahl

/**
 * Convert Roman numerals to an integer
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class RomanConverter {
    private static final Map<Character, Integer> ROMAN_MAP = Map.of(
        'I', 1,
        'V', 5,
        'X', 10,
        'L', 50,
        'C', 100,
        'D', 500,
        'M', 1000
    );

    public static int romanToInt(String s) {
        int total = 0;
        int prevValue = 0;

        // Scan from right to left
        for (int i = s.length() - 1; i >= 0; i--) {
            int value = ROMAN_MAP.get(s.charAt(i));

            if (value < prevValue) {
                total -= value;
            } else {
                total += value;
            }

            prevValue = value;
        }

        return total;
    }
}

Verwendungsbeispiele

public class Main {
    public static void main(String[] args) {
        // Ganzzahl zu Römisch
        System.out.println(RomanConverter.intToRoman(1994));  // Output: MCMXCIV
        System.out.println(RomanConverter.intToRoman(58));    // Output: LVIII
        System.out.println(RomanConverter.intToRoman(9));     // Output: IX

        // Römisch zu Ganzzahl
        System.out.println(RomanConverter.romanToInt("MCMXCIV"));  // Output: 1994
        System.out.println(RomanConverter.romanToInt("LVIII"));    // Output: 58
        System.out.println(RomanConverter.romanToInt("IX"));       // Output: 9
    }
}

Komplexitätsanalyse

Zeitkomplexität

Operation	Komplexität	Erklärung
Ganzzahl zu Römisch	O(1)	Feste Anzahl von Iterationen (13 Wert-Ziffer-Paare)
Römisch zu Ganzzahl	O(n)	Ein Durchlauf durch die Eingabezeichenfolge der Länge n

Raumkomplexität

Beide Algorithmen verwenden O(1) Speicherplatz, da die Größe der Zuordnung unabhängig von der Eingabegröße fest ist.

Warum dieser Ansatz optimal ist

1. Greedy funktioniert: Das Problem hat optimale Teilstruktur
2. Kein Backtracking: Jede Entscheidung ist endgültig und korrekt
3. Vorhersagbare Leistung: Konstante oder lineare Laufzeit

Grenzfälle und Validierung

Wichtige Grenzfälle

# Grenzwerte
assert int_to_roman(1) == "I"
assert int_to_roman(3999) == "MMMCMXCIX"

# Subtraktive Kombinationen
assert int_to_roman(4) == "IV"
assert int_to_roman(9) == "IX"
assert int_to_roman(40) == "XL"
assert int_to_roman(90) == "XC"
assert int_to_roman(400) == "CD"
assert int_to_roman(900) == "CM"

# Komplexe Zahlen
assert int_to_roman(1994) == "MCMXCIV"
assert int_to_roman(3888) == "MMMDCCCLXXXVIII"

Eingabevalidierung

def int_to_roman_safe(num: int) -> str:
    """Version mit Eingabevalidierung"""
    if not isinstance(num, int):
        raise TypeError("Eingabe muss eine Ganzzahl sein")
    if num < 1 or num > 3999:
        raise ValueError("Zahl muss zwischen 1 und 3999 liegen")
    return int_to_roman(num)

def roman_to_int_safe(s: str) -> int:
    """Version mit Eingabevalidierung"""
    if not isinstance(s, str):
        raise TypeError("Eingabe muss eine Zeichenfolge sein")
    if not s:
        raise ValueError("Zeichenfolge darf nicht leer sein")

    valid_chars = set('IVXLCDM')
    if not all(c in valid_chars for c in s):
        raise ValueError("Ungültige römische Zeichen")

    return roman_to_int(s)

Leistungsoptimierungen

1. Dictionary-Implementierung (Python)

def int_to_roman_dict(num: int) -> str:
    """Alternative Version mit Dictionary für schnellere Lookups"""
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    numerals = {
        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 in values:
        count, num = divmod(num, value)
        if count:
            result.append(numerals[value] * count)

    return ''.join(result)

2. Look-Ahead (JavaScript)

function romanToIntOptimized(s) {
    const romanMap = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    };

    let total = 0;

    for (let i = 0; i < s.length; i++) {
        const current = romanMap[s[i]];
        const next = romanMap[s[i + 1]];

        // Wenn der aktuelle Wert kleiner als der nächste ist, subtrahieren
        if (next && current < next) {
            total -= current;
        } else {
            total += current;
        }
    }

    return total;
}

3. StringBuilder für Java

public static String intToRomanOptimized(int num) {
    // StringBuilder ist effizienter als String-Konkatenation
    StringBuilder sb = new StringBuilder();

    while (num >= 1000) { sb.append('M'); num -= 1000; }
    if (num >= 900) { sb.append("CM"); num -= 900; }
    if (num >= 500) { sb.append('D'); num -= 500; }
    if (num >= 400) { sb.append("CD"); num -= 400; }
    while (num >= 100) { sb.append('C'); num -= 100; }
    if (num >= 90) { sb.append("XC"); num -= 90; }
    if (num >= 50) { sb.append('L'); num -= 50; }
    if (num >= 40) { sb.append("XL"); num -= 40; }
    while (num >= 10) { sb.append('X'); num -= 10; }
    if (num >= 9) { sb.append("IX"); num -= 9; }
    if (num >= 5) { sb.append('V'); num -= 5; }
    if (num >= 4) { sb.append("IV"); num -= 4; }
    while (num >= 1) { sb.append('I'); num -= 1; }

    return sb.toString();
}

Leistungsvergleich

Benchmarks (1 Million Konvertierungen)

Sprache	Ganzzahl zu Römisch	Römisch zu Ganzzahl
Python	~450ms	~380ms
JavaScript (Node.js)	~180ms	~150ms
Java	~120ms	~95ms

Hinweis: Benchmarks sind ungefähr und variieren je nach Hardware

Optimierungstipps

1. Häufige Werte vorberechnen: Häufige Konvertierungen cachen
2. Primitive Typen verwenden: Boxing/Unboxing in Java vermeiden
3. Zuweisungen minimieren: Puffer nach Möglichkeit wiederverwenden
4. Profiling: Vor der Optimierung messen

Häufige Probleme und Lösungen

Problem 1: Falsche Zuordnungsreihenfolge

# ❌ FALSCH - aufsteigende Reihenfolge
values = [(1, 'I'), (5, 'V'), (10, 'X')]  # Funktioniert nicht

# ✅ RICHTIG - absteigende Reihenfolge
values = [(10, 'X'), (5, 'V'), (1, 'I')]

Problem 2: Subtraktive Kombinationen vergessen

# ❌ FALSCH - fehlende Subtraktionsnotation
values = [(1000, 'M'), (500, 'D'), (100, 'C')]  # 900 wird zu DCCCC

# ✅ RICHTIG - enthält alle subtraktiven Kombinationen
values = [(1000, 'M'), (900, 'CM'), (500, 'D')]  # 900 wird zu CM

Problem 3: Scan-Richtung bei Römisch zu Ganzzahl

# ❌ FALSCH - Links-nach-rechts-Scan ohne Look-Ahead-Logik
def roman_to_int_wrong(s):
    total = 0
    for char in s:
        total += roman_map[char]  # Behandelt Subtraktionsnotation nicht
    return total

# ✅ RICHTIG - Rechts-nach-links-Scan oder Look-Ahead
def roman_to_int_correct(s):
    total = 0
    prev_value = 0
    for char in reversed(s):
        value = roman_map[char]
        if value < prev_value:
            total -= value
        else:
            total += value
        prev_value = value
    return total

Interview-Fragen

Häufige Fragen

1. F: Warum funktioniert der Greedy-Ansatz? A: Weil römische Zahlen optimale Teilstruktur haben - die Verwendung des größtmöglichen Symbols führt immer zur optimalen Lösung.

2. F: Wie behandeln Sie die Subtraktionsnotation? A: Fügen Sie subtraktive Kombinationen (IV, IX, XL, XC, CD, CM) als separate Einträge in die Wertzuordnung ein.

3. F: Was ist die Zeitkomplexität? A: O(1) für Ganzzahl zu Römisch (feste Anzahl von Iterationen), O(n) für Römisch zu Ganzzahl (wobei n die Länge der Zeichenfolge ist).

4. F: Können Sie Zahlen über 3999 behandeln? A: Ja, mit erweiterter Notation (Überstrich für Multiplikation mit 1000), aber das ist nicht standardmäßig.

Folgefragen

1. Implementieren Sie eine Validierungsfunktion

   def is_valid_roman(s: str) -> bool:
       """Prüft, ob eine Zeichenfolge eine gültige römische Zahl ist"""
       pattern = r'^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$'
       return bool(re.match(pattern, s))
   

2. Optimieren Sie für wiederholte Konvertierungen

   class RomanConverter:
       def __init__(self):
           self.cache = {}
   
       def int_to_roman(self, num: int) -> str:
           if num in self.cache:
               return self.cache[num]
           result = self._convert(num)
           self.cache[num] = result
           return result
   

3. Behandeln Sie ungültige Eingaben elegant

   function intToRomanSafe(num) {
       if (typeof num !== 'number' || !Number.isInteger(num)) {
           throw new TypeError('Eingabe muss eine Ganzzahl sein');
       }
       if (num < 1 || num > 3999) {
           throw new RangeError('Zahl muss zwischen 1 und 3999 liegen');
       }
       return intToRoman(num);
   }
   

Praxisanwendungen

1. Dokumentengenerierung

def format_chapter(num: int, title: str) -> str:
    return f"Kapitel {int_to_roman(num)}: {title}"

2. Copyright-Jahre

function copyrightYear(year) {
    return `©${intToRoman(year)}`;
}

3. Listennummerierung

public String formatListItem(int index, String content) {
    return String.format("%s. %s", intToRoman(index), content);
}

Fazit

Algorithmen zur Konvertierung römischer Zahlen demonstrieren die Kraft des Greedy-Ansatzes für Probleme mit optimaler Teilstruktur. Die hier bereitgestellten Implementierungen sind:

• Effizient: O(1) für Ganzzahl zu Römisch, O(n) für Römisch zu Ganzzahl
• Lesbar: Klare Logik, die den mathematischen Regeln entspricht
• Robust: Behandeln alle gültigen Eingaben im Standardbereich
• Getestet: Funktionieren für alle Zahlen von 1 bis 3999

Ob Sie sich auf Coding-Interviews vorbereiten, einen Dokumentengenerator erstellen oder einfach nur neugierig auf Algorithmen sind, diese Implementierungen bieten eine solide Grundlage.

Für eine benutzerfreundliche Oberfläche ohne Code zu schreiben, probieren Sie unseren Online-Römische-Zahlen-Konverter mit sofortigen Ergebnissen und Unterstützung für erweiterte Notation.

---

Möchten Sie mehr erfahren? Erkunden Sie unseren vollständigen Leitfaden zu römischen Zahlen oder sehen Sie, wie man römische Zahlen in Excel verwendet.