Algorithmes de Chiffres Romains : Implémentation Python, JavaScript & Java

La conversion entre chiffres romains et entiers est un problème de programmation classique qui apparaît dans les entretiens de codage, la programmation compétitive et les applications réelles. Ce guide fournit des implémentations optimisées en Python, JavaScript et Java, ainsi que des explications des algorithmes sous-jacents.

Comprendre le Problème

Nous devons résoudre deux problèmes liés :

1. Entier vers Romain : Convertir un nombre arabe (ex. 1994) en chiffres romains (MCMXCIV)
2. Romain vers Entier : Convertir des chiffres romains (ex. MCMXCIV) en nombre arabe (1994)

Contraintes

• Plage d'entrée : 1 à 3999 (plage standard des chiffres romains)
• Utiliser la notation soustractive standard (IV, IX, XL, XC, CD, CM)
• Gérer toutes les combinaisons valides de chiffres romains

L'Approche de l'Algorithme Glouton

Les deux conversions utilisent une stratégie d'algorithme glouton :

Entier vers Romain (Glouton)

1. Créer un mappage de valeurs vers chiffres romains en ordre décroissant
2. Pour chaque paire valeur-chiffre :
   • Utiliser autant de ce chiffre que possible
   • Soustraire la valeur du nombre restant
3. Répéter jusqu'à ce que le nombre atteigne zéro

Romain vers Entier (Glouton)

1. Scanner la chaîne de chiffres romains de gauche à droite
2. Pour chaque symbole :
   • S'il est plus petit que le symbole suivant, le soustraire (notation soustractive)
   • Sinon, l'ajouter
3. Retourner la somme accumulée

Implémentation Python

Entier vers Romain

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)

Romain vers Entier

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

Exemples d'Utilisation

# Entier vers Romain
print(int_to_roman(1994))  # Output: MCMXCIV
print(int_to_roman(58))    # Output: LVIII
print(int_to_roman(9))     # Output: IX

# Romain vers Entier
print(roman_to_int("MCMXCIV"))  # Output: 1994
print(roman_to_int("LVIII"))    # Output: 58
print(roman_to_int("IX"))       # Output: 9

Implémentation JavaScript

Entier vers Romain

/**
 * 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;
}

Romain vers Entier

/**
 * 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;
}

Exemples d'Utilisation

// Entier vers Romain
console.log(intToRoman(1994));  // Output: MCMXCIV
console.log(intToRoman(58));    // Output: LVIII
console.log(intToRoman(9));     // Output: IX

// Romain vers Entier
console.log(romanToInt("MCMXCIV"));  // Output: 1994
console.log(romanToInt("LVIII"));    // Output: 58
console.log(romanToInt("IX"));       // Output: 9

Implémentation Java

Entier vers Romain

/**
 * 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();
    }
}

Romain vers Entier

/**
 * 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;
    }
}

Exemples d'Utilisation

public class Main {
    public static void main(String[] args) {
        // Entier vers Romain
        System.out.println(RomanConverter.intToRoman(1994));  // Output: MCMXCIV
        System.out.println(RomanConverter.intToRoman(58));    // Output: LVIII
        System.out.println(RomanConverter.intToRoman(9));     // Output: IX

        // Romain vers Entier
        System.out.println(RomanConverter.romanToInt("MCMXCIV"));  // Output: 1994
        System.out.println(RomanConverter.romanToInt("LVIII"));    // Output: 58
        System.out.println(RomanConverter.romanToInt("IX"));       // Output: 9
    }
}

Analyse de Complexité

Complexité Temporelle

Opération	Complexité	Explication
Entier vers Romain	O(1)	Nombre fixe d'itérations (13 paires valeur-chiffre)
Romain vers Entier	O(n)	Un passage à travers la chaîne d'entrée de longueur n

Complexité Spatiale

Les deux algorithmes utilisent O(1) espace car la taille du mappage est fixe indépendamment de la taille d'entrée.

Pourquoi Cette Approche est Optimale

1. Le glouton fonctionne : Le problème a une structure de sous-structure optimale
2. Pas de retour en arrière : Chaque décision est finale et correcte
3. Performance prévisible : Temps d'exécution constant ou linéaire

Cas Limites et Validation

Cas Limites Importants

# Valeurs limites
assert int_to_roman(1) == "I"
assert int_to_roman(3999) == "MMMCMXCIX"

# Combinaisons soustractives
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"

# Nombres complexes
assert int_to_roman(1994) == "MCMXCIV"
assert int_to_roman(3888) == "MMMDCCCLXXXVIII"

Validation d'Entrée

def int_to_roman_safe(num: int) -> str:
    """Version avec validation d'entrée"""
    if not isinstance(num, int):
        raise TypeError("L'entrée doit être un entier")
    if num < 1 or num > 3999:
        raise ValueError("Le nombre doit être entre 1 et 3999")
    return int_to_roman(num)

def roman_to_int_safe(s: str) -> int:
    """Version avec validation d'entrée"""
    if not isinstance(s, str):
        raise TypeError("L'entrée doit être une chaîne")
    if not s:
        raise ValueError("La chaîne ne peut pas être vide")

    valid_chars = set('IVXLCDM')
    if not all(c in valid_chars for c in s):
        raise ValueError("Caractères romains invalides")

    return roman_to_int(s)

Optimisations de Performance

1. Implémentation avec Dictionnaire (Python)

def int_to_roman_dict(num: int) -> str:
    """Version alternative utilisant un dictionnaire pour des recherches plus rapides"""
    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. Anticipation (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]];

        // Si la valeur actuelle est inférieure à la suivante, soustraire
        if (next && current < next) {
            total -= current;
        } else {
            total += current;
        }
    }

    return total;
}

3. StringBuilder pour Java

public static String intToRomanOptimized(int num) {
    // StringBuilder est plus efficace que la concaténation de String
    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();
}

Comparaison de Performance

Benchmarks (1 million de conversions)

Langage	Entier vers Romain	Romain vers Entier
Python	~450ms	~380ms
JavaScript (Node.js)	~180ms	~150ms
Java	~120ms	~95ms

Note : Les benchmarks sont approximatifs et varient selon le matériel

Conseils d'Optimisation

1. Précalculer les valeurs courantes : Mettre en cache les conversions fréquentes
2. Utiliser des types primitifs : Éviter le boxing/unboxing en Java
3. Minimiser les allocations : Réutiliser les tampons lorsque possible
4. Profilage : Mesurer avant d'optimiser

Problèmes Courants et Solutions

Problème 1 : Ordre de Mappage Incorrect

# ❌ INCORRECT - ordre croissant
values = [(1, 'I'), (5, 'V'), (10, 'X')]  # Ne fonctionnera pas

# ✅ CORRECT - ordre décroissant
values = [(10, 'X'), (5, 'V'), (1, 'I')]

Problème 2 : Oublier les Combinaisons Soustractives

# ❌ INCORRECT - notation soustractive manquante
values = [(1000, 'M'), (500, 'D'), (100, 'C')]  # 900 devient DCCCC

# ✅ CORRECT - inclut toutes les combinaisons soustractives
values = [(1000, 'M'), (900, 'CM'), (500, 'D')]  # 900 devient CM

Problème 3 : Direction de Scan dans Romain vers Entier

# ❌ INCORRECT - scan de gauche à droite sans logique d'anticipation
def roman_to_int_wrong(s):
    total = 0
    for char in s:
        total += roman_map[char]  # Ne gère pas la notation soustractive
    return total

# ✅ CORRECT - scan de droite à gauche ou anticipation
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

Questions d'Entretien

Questions Courantes

1. Q : Pourquoi l'approche gloutonne fonctionne-t-elle ? R : Parce que les chiffres romains ont une structure de sous-structure optimale - utiliser le plus grand symbole possible conduit toujours à la solution optimale.

2. Q : Comment gérez-vous la notation soustractive ? R : Incluez les combinaisons soustractives (IV, IX, XL, XC, CD, CM) dans le mappage de valeurs comme entrées séparées.

3. Q : Quelle est la complexité temporelle ? R : O(1) pour entier vers romain (nombre fixe d'itérations), O(n) pour romain vers entier (où n est la longueur de la chaîne).

4. Q : Pouvez-vous gérer des nombres supérieurs à 3999 ? R : Oui, en utilisant la notation de barre (vinculum) pour les multiples de 1000, mais cela nécessite une logique supplémentaire.

5. Q : Comment validez-vous l'entrée ? R : Vérifiez la plage (1-3999) pour les entiers et les caractères valides (IVXLCDM) pour les chaînes romaines.

Variations du Problème

1. Validation de chiffres romains : Vérifier si une chaîne est un chiffre romain valide
2. Notation étendue : Gérer les nombres supérieurs à 3999 avec des barres
3. Conversion par lots : Optimiser pour plusieurs conversions
4. Arithmétique romaine : Effectuer des opérations directement en notation romaine

Cas d'Utilisation Réels

1. Numérotation de Chapitres

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

2. Années de Copyright

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

3. Numérotation de Listes

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

Conclusion

Les algorithmes de conversion de chiffres romains démontrent la puissance de l'approche gloutonne pour les problèmes avec une sous-structure optimale. Les implémentations fournies ici sont :

• Efficaces : O(1) pour entier vers romain, O(n) pour romain vers entier
• Lisibles : Logique claire qui correspond aux règles mathématiques
• Robustes : Gèrent toutes les entrées valides dans la plage standard
• Testées : Fonctionnent pour tous les nombres de 1 à 3999

Que vous vous prépariez pour des entretiens de codage, construisiez un générateur de documents, ou soyez simplement curieux des algorithmes, ces implémentations fournissent une base solide.

Pour une interface conviviale sans écrire de code, essayez notre convertisseur de chiffres romains en ligne avec des résultats instantanés et un support pour la notation étendue.

---

Vous voulez en savoir plus ? Explorez notre guide complet des chiffres romains ou voyez comment utiliser les chiffres romains dans Excel.