Integer to Roman

Q: Quelle est la complexité temporelle de Integer to Roman ?

O(1) . L'entrée est au plus égale à 3999, donc la boucle gloutonne vérifie 13 lignes du tableau et ajoute au maximum 15 symboles. Si des nombres plus grands étaient autorisés et écrits avec des M répétés, le temps augmenterait avec num / 1000 .

Q: Pourquoi 3999 est-il le plus grand nombre autorisé ?

M est la plus grande lettre et aucune lettre ne peut apparaître quatre fois de suite. Ainsi, MMM est la limite pour les milliers, et 3999 s’écrit MMMCMXCIX . Les nombres plus grands étaient écrits avec des marques supplémentaires, comme une barre au-dessus d’une lettre pour la multiplier par 1000.

MoyenMaths et simulation Glouton

+10

Les chiffres romains comportent sept lettres : M 1000, D 500, C 100, L 50, X 10, V 5 et I 1. Les lettres vont de la plus grande à la plus petite et s’additionnent : 7 s’écrit donc VII. Aucune lettre ne se répète quatre fois de suite : 4, 9, 40, 90, 400 et 900 s’écrivent IV, IX, XL, XC, CD et CM ; une lettre plus petite est alors soustraite de celle qui la suit, plus grande. Seules ces six paires placent une lettre plus petite en premier.

Étant donné un entier num, renvoie son chiffre romain.

Fonction

intToRoman(num: integer) → string

numinteger: un entier de 1 à 3999
Renvoiestring: le chiffre romain de num en majuscules

Contraintes

1 ≤ num ≤ 3999

Exemples

Entrée: num = 49
Sortie: "XLIX"
Explication: 49, c’est 40 + 9, donc le numéral est XL puis IX : XLIX. IL n’est pas autorisé, car I ne se soustrait que dans IV et IX.

Entrée: num = 2026
Sortie: "MMXXVI"
Explication: 2026 ne contient aucun chiffre 4 ni 9, donc aucune paire n’est nécessaire et les lettres s’additionnent : 1000 + 1000 + 10 + 10 + 5 + 1 donnent MMXXVI.

Entrée: num = 944
Sortie: "CMXLIV"
Explication: 944 est égal à 900 + 40 + 4, et chaque partie est une paire soustractive : CM, XL et IV se combinent pour former CMXLIV.

Pour aller plus loin

Étant donné une chaîne, peux-tu vérifier qu’il s’agit d’un chiffre romain sous cette forme standard, en acceptant XLIX et en rejetant IIII, IL et VX ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Ajoute les six paires soustractives à l’alphabet en tant que symboles à part entière, et écrire un nombre devient une opération de rendu de monnaie : prends toujours la plus grande valeur qui convient encore. L’entrée est au plus égale à 3999, donc le travail représente une petite quantité fixe.

Écrivez-le de manière additive, puis raccourcissez les formes longues

Intuition

Ignore d’abord les paires : écris autant de M que possible, puis D, et ainsi de suite jusqu’à I. Pour 944, cela donne DCCCCXXXXIIII. Cette forme additive ne diffère de la forme standard que lorsque le chiffre est 4 ou 9, et ces positions correspondent toujours à l’une des six chaînes qui ont une forme abrégée : DCCCC devient CM, CCCC devient CD, LXXXX devient XC, XXXX devient XL, VIIII devient IX et IIII devient IV.

Remplace DCCCC avant CCCC, sinon 900 devient DCD ; la même règle s’applique aux dizaines et aux unités. La forme additive compte au plus 18 lettres (3999), donc le travail est en O(1), au prix d’un second passage et de quelques chaînes temporaires.

Algorithme

Pour chacune des sept lettres, de M à I, ajoute-la tant que num est supérieur ou égal à sa valeur, et soustrais cette valeur à chaque fois.
Remplace DCCCC par CM, puis CCCC par CD.
Remplace LXXXX par XC, puis XXXX par XL.
Remplace VIIII par IX, puis IIII par IV.
Renvoie la chaîne.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Glouton sur les 13 valeurs

Intuition

Triez les sept lettres et les six paires par valeur : M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Prendre la plus grande valeur qui convient est toujours la bonne approche. Toute valeur d’un rang décimal inférieur est plus petite que la plus petite valeur du rang supérieur, de sorte que la boucle termine un rang avant de passer au suivant. À l’intérieur d’un rang, les valeurs 9, 5, 4 et 1 permettent d’écrire chaque chiffre de la manière standard : 9 est le symbole de 9, de 5 à 8 sont le symbole de 5 suivi d’un maximum de trois symboles de 1, 4 est le symbole de 4, et de 1 à 3 sont des symboles de 1.

Pour 3746, la boucle écrit MMM, D, CC, XL, V, I : MMMDCCXLVI. Le tableau comporte 13 lignes et la réponse compte au maximum 15 lettres ; le travail est donc en O(1), en un seul passage.

Algorithme

Liste les 13 valeurs avec leurs symboles, de 1000 à 1, y compris les paires.
Commence par une chaîne vide.
Pour chaque ligne, tant que num est supérieur ou égal à la valeur, ajoute le symbole et soustrais la valeur.
Renvoie la chaîne une fois toutes les lignes traitées.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Pièges et cas limites

Placer D avant CM dans le tableau. 900 donne alors DCD.
Utiliser if au lieu de while pour chaque ligne. 3000 nécessite M trois fois ; avec if, on obtient MCMDCDCXCX.
Inventer d’autres paires. 99 est XCIX, et non IC, et 45 est XLV, et non VL.
En C, utiliser un tampon trop petit. La réponse la plus longue, pour 3888, comporte 15 lettres ; il faut donc 16 octets avec le zéro terminal ; la forme additive en nécessite 19.

Questions fréquentes3

Quelle est la complexité temporelle de Integer to Roman ?

O(1). L'entrée est au plus égale à 3999, donc la boucle gloutonne vérifie 13 lignes du tableau et ajoute au maximum 15 symboles. Si des nombres plus grands étaient autorisés et écrits avec des M répétés, le temps augmenterait avec num / 1000.

Peux-tu convertir un entier en chiffres romains sans parcourir les valeurs à l’aide d’une boucle ?

Oui. Conserve une table par rang décimal avec les chaînes correspondant à ses chiffres, comme "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM pour les centaines. Recherche chaque chiffre de num et concatène les chaînes. C’est également O(1), avec 34 chaînes stockées.

Pourquoi 3999 est-il le plus grand nombre autorisé ?

M est la plus grande lettre et aucune lettre ne peut apparaître quatre fois de suite. Ainsi, MMM est la limite pour les milliers, et 3999 s’écrit MMMCMXCIX. Les nombres plus grands étaient écrits avec des marques supplémentaires, comme une barre au-dessus d’une lettre pour la multiplier par 1000.

def intToRoman(num):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

num = 49

Résultat attendu

"XLIX"