CPGE Mohammedia 2024-2025

MPSI - INFORMATIQUE
[Link]

TP n°5: Algorithmique et Programmation:

Problème : Les nombres en chiffres romains

Contraintes générales :
— Les chiffres romains sont les suivants : I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
— Dans un nombre romain, Le même chiffre ne peut pas être employé quatre fois consécutivement sauf M.
— Exemple des nombres romains corrects : VII, VIIXXXL, MMMMCMXCIX
— Exemple des nombres romains incorrects : VIIII, VIIXXXXL
— Pour connaı̂tre la valeur d’un nombre écrit en chiffres romains, il faut lire le nombre de droite à gauche :
— On prend comme somme la valeur du premier chiffre
— Si le deuxième chiffre du nombre a une valeur inférieure au premier, alors on le soustrait de la somme,
sinon on l’additionne à la somme
— On répète l’opération avec le troisième et le deuxième . . .jusqu’à le dernier chiffre
— La somme obtenue est le nombre arabe

Exemple :
— XVI = 1 + 5 + 10 = 16
— XIV = 5 - 1 + 10 = 14, car I est inférieur à V
— DIX = 10 - 1 + 500 = 509, car I est inférieur à X
— MMMMCMXCIX = 10 - 1 + 100 - 10 + 1000 - 100 + 1000 * 4 = 4999
— MMMMDCCCLXXXVIII = 4888, est le nombre romain le plus long en quantité de symboles
Dans ce problème, on va représenter un nombre romain comme étant une chaı̂ne de caractères non nulle,
composée uniquement de sept lettres romains et que chaque lettre ne peut pas être employée quatre fois
consécutivement sauf ’M’.

Question 1 :
Écrire la fonction Consecutive(R) qui reçoit comme argument un nombre romain R et qui retourne 1 si
R contient un chiffre romain employé quatre fois consécutivement sauf ’M’ et 0 sinon.
Exemple :
— Pour le nombre romain R=’VIIII’ la fonction Consecutive(R) retourne 1
— Pour le nombre romain R=’MMMMCXM’ la fonction Consecutive(R) retourne 0

Question 2 :
Écrire la fonction Valide(R) qui reçoit comme argument un nombre romain R et qui retourne 1 si R est un
nombre romain valide et 0 sinon.
Rappel :
Un nombre romain est valide s’il est composé uniquement des sept lettres romains (I, V, X, L, C, D, M) et que
chaque lettre ne peut pas être employée quatre fois consécutivement sauf ’M’.
Exemple :

1
 — Pour le nombre romain R=’VHIII’ la fonction Valide(R) retourne 0
— Pour le nombre romain R=’XIV’ la fonction Valide(R) retourne 1
— Pour le nombre romain R=’XIIIIV’ la fonction Valide(R) retourne 0

Question 3 :
On suppose qu’on a un dictionnaire de conversion d (romain vers arabe) qui fait correspondre à chaque
chiffre romain un chiffre arabe :

d = {’I’:1, ’V’:5, ’X’:10, ’L’:50, ’C’:100, ’D’:500, ’M’:1000}

Écrire la fonction Convert(d) qui prend en argument un dictionnaire de conversion (romain vers arabe) et
qui retourne un autre dictionnaire de conversion (arabe vers romain).
Exemple :
Pour le dictionnaire d = {’I’ :1, ’V’ :5, ’X’ :10, ’L’ :50, ’C’ :100, ’D’ :500, ’M’ :1000} la fonction Convert(d)
retourne le dictionnaire suivant :
d1 = {1 :’I’, 5 :’V’, 10 :’X’, 50 :’L’, 100 :’C’, 500 :’D’, 1000 :’M’}

Question 4 :
Écrire la fonction Romain2Arabe(R,d) qui reçoit en argument un nombre romain R et un dictionnaire
de conversion d (romain vers arabe) et qui retourne un nombre arabe équivalent.
Exemple :
— Pour le nombre romain R=’XVI’ et le dictionnaire d = {’I’ :1, ’V’ :5, ’X’ :10, ’L’ :50, ’C’ :100, ’D’ :500,
’M’ :1000} la fonction Romain2Arabe(R,d) retourne le nombre arabe : 16
— Pour le nombre romain R=’DIX’ et le dictionnaire d = {’I’ :1, ’V’ :5, ’X’ :10, ’L’ :50, ’C’ :100, ’D’ :500,
’M’ :1000} la fonction Romain2Arabe(R,d) retourne le nombre arabe : 509

Question 5 :
Écrire la fonction Arabe2Romain(N,d1) qui reçoit en argument un nombre arabe N et un dictionnaire
de conversion d1 (arabe vers romain) et qui retourne un nombre romain équivalent. On supposera que N est
strictement positif et inférieur à 5000.
Exemple :
— Pour N = 16 et d1 = {1 :’I’, 5 :’V’, 10 :’X’, 50 :’L’, 100 :’C’, 500 :’D’, 1000 :’M’}, la fonction retourne
’XVI’
— Pour N = 509 et d1 = {1 :’I’, 5 :’V’, 10 :’X’, 50 :’L’, 100 :’C’, 500 :’D’, 1000 :’M’}, la fonction retourne
’DIX’

Question 6 :
Écrire la fonction NombreOccurrences(R) qui reçoit comme argument un nombre romain R et qui re-
tourne un dictionnaire contenant le nombre d’occurrences de chaque chiffre romain dans R.
Exemple :
— Pour R = ’MMMDCCCXLIV’, la fonction retourne {’M’ :3, ’D’ :1, ’C’ :3, ’X’ :1, ’L’ :1, ’I’ :1, ’V’ :1}

Question 7 :
Écrire une fonction EstSubtractif(R,d) qui reçoit en argument un nombre romain R et le dictionnaire de
conversion d, et qui retourne 1 si le nombre utilise la notation soustractive (comme dans IV ou IX) et 0 sinon.
Exemple :
— Pour R = ’XIV’, la fonction retourne 1
— Pour R = ’XIII’, la fonction retourne 0

2
Question 8 :
Écrire une fonction SimplifieRomain(R,d) qui reçoit en argument un nombre romain R et le dictionnaire
de conversion d, et qui retourne le nombre romain le plus court possible représentant la même valeur.
Exemple :
— Pour R = ’VIIII’, la fonction retourne ’IX’
— Pour R = ’XIIIIII’, la fonction retourne ’XVI’

Question 9 :
Écrire une fonction Addition(R1,R2,d,d1) qui reçoit en argument deux nombres romains R1 et R2, le
dictionnaire de conversion romain vers arabe d et le dictionnaire de conversion arabe vers romain d1, et qui
retourne la somme de ces deux nombres en chiffres romains sous sa forme la plus simple.
Exemple :
— Pour R1 = ’XIV’ et R2 = ’III’, la fonction retourne ’XVII’
— Pour R1 = ’CCCXL’ et R2 = ’DCCCLIX’, la fonction retourne ’MCXCIX’
Indication : On pourra utiliser les fonctions précédentes pour :
— Convertir les nombres romains en nombres arabes
— Effectuer l’addition
— Convertir le résultat en nombre romain
— Simplifier le résultat si nécessaire

Question 10 :
Écrire une fonction OperationsRomaines(expr,d,d1) qui reçoit en argument une expression arithmétique
expr sous forme de chaı̂ne de caractères contenant des nombres romains et les opérateurs ’+’ et ’-’ (séparés par
des espaces), ainsi que les dictionnaires de conversion d et d1. La fonction doit retourner le résultat de l’expression
en chiffres romains sous sa forme la plus simple.
Exemple :
— Pour expr = ”XIV + III - II”, la fonction retourne ’XV’
— Pour expr = ”C + L - XXV + X”, la fonction retourne ’CXXXV’
— Pour expr = ”MM - D + C”, la fonction retourne ’MDC’
Indication :
— Découper l’expression en utilisant la méthode split()
— Traiter les opérateurs dans l’ordre d’apparition
— Vérifier que les expressions sont valides
— Gérer les nombres négatifs intermédiaires
Contraintes :
— Le résultat final doit toujours être positif
— Les nombres romains dans l’expression doivent être valides
— Les opérateurs doivent être séparés par des espaces
— Le résultat doit être sous la forme la plus simple possible