Partage

[Algo] Convertisseur chiffre arabe-romain

1 novembre 2009 à 13:14:46

Bonjour, j'ai eu comme DM d'écrire un algo qui convertirait les chiffre romain en arabe et inversement. ( sachant que lors de la conversion d'un chiffre arabe en romain je dois rentrer un nbre compris entre 1 et 3999)
J'ai donc commencé par faire un 1er algo qui convertirait les chiffres arabes en romain, mais la en fait je suis un peu bloqué.
Je suis débutant en algo et je sais donc utiliser que les boucles "Si" "tant que" "répéter jusqu'à" " Pour" "suivant" "tableau a 1 et 2 dimension".
Donc dans cet algo je sais qu'il faut faire attention au chiffre du style 4 et 9 et qu'il n'ya que 3999 chiffres romains.

J'ai fait tout mes contrôles du début de l'algo et la c'est dans la structure à utiliser que je bloque.
J'ai bien pensé à une boucle suivant mais je pense pas que le prof apprécie un algo de 30 copie double :)!
C'est pour ça que j'aimerais une petite aide si possible sur au moins une structure pour me lancer dans le début de l'algo.

Merci par avance pour votre aide
Cordialement rorodu05

Saevit

1 novembre 2009 à 16:25:28

Voila, en Python, c'est la partie Chiffres arabes -> Chiffres romains ; c'est loin d'être le plus performant à mon avis, et il peut subsister des erreurs, ça a pas été trop dur à faire. Regarde seulement si tu ne trouves vraiment pas.

I, IV, V, IX, X, XL, L, XC, C, CD, D, CM, M = 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000
arabe = 3999

while(arabe - M >= 0):
    arabe -= M
    print('M')
while(arabe - CM >= 0):
    arabe -= CM
    print('CM')
while(arabe - D >= 0):
    arabe -= D
    print('D')
while(arabe - CD >= 0):
    arabe -= CD
    print('CD')
while(arabe - C >= 0):
    arabe -= C
    print('C')
while(arabe - XC >= 0):
    arabe -= XC
    print('XC')
while(arabe - L >= 0):
    arabe -= L
    print('L')
while(arabe - XL >= 0):
    arabe -= XL
    print('XL')
while(arabe - X >= 0):
    arabe -= X
    print('X')
while(arabe - IX >= 0):
    arabe -= IX
    print('IX')
while(arabe - V >= 0):
    arabe -= V
    print('V')
while(arabe - IV >= 0):
    arabe -= IV
    print('IV')
while(arabe - I >= 0):
    arabe -= I
    print('I')

MMMCMXCIX

J'ai d'abord listé toutes les valeurs existantes dans des variables, et ensuite j'ai fait des boucles de test, regarde le code, tu comprendras sûrement mieux !

ordiclic

1 novembre 2009 à 16:48:59

Normalement tu devrais obtenir IMMMM, donc ton code est un peu moyen.

Regarde sur dive into python, il y a des ébauches de code, facilement complétables.

Saevit

1 novembre 2009 à 16:57:14

Citation : ordiclic

Normalement tu devrais obtenir IMMMM, donc ton code est un peu moyen.

Regarde sur dive into python, il y a des ébauches de code, facilement complétables.

Je devrais obtenir IMMMM pour 3999 ?
Sur Wolfram|Alpha en tapant "3999 in roman", j'obtiens la même chose qu'avec mon code !

Anonyme

1 novembre 2009 à 18:03:26

IMMMM c'est pas un nombre en chiffre romain...

ordiclic

1 novembre 2009 à 18:05:46

MMCMXCIX pour 2999 ; alors que normalement je devrais obtenir IMMM

Anonyme

1 novembre 2009 à 18:08:19

Citation : ordiclic

MMCMXCIX pour 2999 ; alors que normalement je devrais obtenir IMMM

En chiffres romains, "IMMM" n'est pas un nombre. Navré.

Saevit

1 novembre 2009 à 19:13:13

Donc, mon code fonctionne bien n'est-ce pas ?

rorodu05

1 novembre 2009 à 20:11:34

je comprend vite fais ta boucle car sa fais a peine 2 mois que je fais de l'algo le truc c'est que je n'utilise pas Python, la c'est de l'algo sur papier et les méthodes qu'on utilise c'est apparement spécifique au BTS.
Le truc que je voudrais savoir c'est par quoi démarré en fait car je n'ai aucune idée de quelle structure utiliser .
Merci quand même pour ton aide

Saevit

1 novembre 2009 à 21:23:36

Bah, déjà, au début, tu créés des variables "chiffres romains", et tu leur affecte la valeur en chiffre arabe qui leur correspond : I = 1, V = 5, etc...
De plus, en chiffres romains, 4 s'écrit IV, donc tu rajoutes ces variables, c'est ma première ligne de code, j'ai fait :

AFFECTER 1 à I, AFFECTER 4 à IV, AFFECTER 5 à V, etc...

Dis moi si tu comprends jusqu'ici.

Ensuite, j'ai prit un nombre arabe au hasard, ici 3999.
Je fais donc des boucles pour savoir combien de fois inclure chaque terme. Je vérifie que le chiffre arabe moins le terme fait un total supérieur ou égal à 0. Si un terme est inclut une fois, je soustrais sa valeur au nombre arabe. Ensuite, quand le nombre arabe moins le terme romain donne un résultat inférieur à 0, je passe à la boucle suivante.
Désolé, je crois avoir très mal expliqué, dis moi ce que tu ne comprends pas.

arabe = 3999.

arabe - M = 2999, on est supérieur à 0, on entre dans la boucle.
On enlève 1000 à arabe : arabe = 2999 : on a une fois M ;

arabe - M = 1999, on est supérieur à 0, on entre dans la boucle.
On enlève 1000 à arabe : arabe = 1999 : on a deux fois M ;

arabe - M = 999, on est supérieur à 0, on entre dans la boucle.
On enlève 1000 à arabe : arabe = 999 : on a trois fois M ;

arabe - M = -1, on est inférieur à 0, on sort de la boucle !

arabe - CM = 99, on est supérieur à 0, on entre dans la boucle.
On enlève 900 à arabe : arabe = 99 : On a trois fois M et une fois CM.

Etc... Tu commences à comprendre ?

rorodu05

1 novembre 2009 à 21:36:38

Si j'ai bien compris toute les variables romaines du genres I V M ... je les affecte a leur équivalent arabe . Plus définir aussi les chiffres romains spéciaux ( IV , IX ... )
Sa s'écrirait en gros "V <- 5" non ?
Et après lorsque je saisi un nombre, le programme lui pour convertir le chiffre arabe en chiffre romain va a chaque fois soustraire le plus gros terme et tant que c'est supérieur à 0 je soustrais ce terme, si sa devient inférieur à 0 alors je passe au terme suivant c'est cela ?

je crois que je commence à comprendre le truc je te remercie pour ta patience et tes explications.

Saevit

1 novembre 2009 à 21:47:48

Voila, et encore, on est pas obligé de faire "V <- 5", on pourrait mettre directement "5" dans le code : "while(arabe - 5 >= 0):", mais je trouve cela plus lisible de mettre V ici.
Et sinon, d'après ton dernier paragraphe, je crois que tu as compris comment cela fonctionne.
Bravo !

(Et de rien, ça fait plaisir d'aider les autres !)

rorodu05

1 novembre 2009 à 21:52:43

Bon sava alors si déja j'ai compris sa mais encore une question dsl je suis chiant

c'est "while(arabe - 5 >= 0):" que je ne comprend vraiment pas la signification, quand tu me parlait de variables au début c'était bien de les définir avant de commencer le début de mon algo ?

Saevit

1 novembre 2009 à 21:58:38

while(arabe - 5 >= 0): = while(arabe - V >= 0): = TANT QUE arabe - 5 est SUPERIEUR ou EGALE à 0, on entre dans la boucle.
Définir les variables au début est facultatif ici, en effet, dans les boucles, que l'on mette V ou 5, ça ne change rien !

rorodu05

1 novembre 2009 à 22:03:29

Okey je crois que sa y'est je saisi le truc et par la même occasion j'ai compris pourquoi tu utiliser la boucle "tant que".
Merci pour ton aide

Saevit

1 novembre 2009 à 22:05:30

De rien !

bluestorm

2 novembre 2009 à 17:46:37

La même chose, sans les répétitions :

numlist = {1:'I', 4:'IV', 5:'V', 9:'IX', 10:'X', 40:'XL', 50:'L', 90:'XC', 100:'C', 400:'CD', 500:'D', 900:'CM', 1000:'M'}

def arabe(n):
    res = ""
    for k, v in reversed(sorted(numlist.iteritems())):
        while n >= k:
            n -= k
            res += v
    return res

print arabe(3999)

Lecureuil : quand tu utilises le copier/coller pour écrire un code, c'est forcément qu'il y a un problème, et que tu as oublié une méthode pour simplifier.

gorgonite

2 novembre 2009 à 18:55:42

pourquoi ne pas simplement coder en dur les cas de 1 à 10, puis appliquer une sorte d'algorithme glouton ?

à ma connaissance, ça serait suffisant, et je ne vois pas d'erreur possible...

Saevit

2 novembre 2009 à 23:16:10

Citation : bluestorm

La même chose, sans les répétitions :
numlist = {1:'I', 4:'IV', 5:'V', 9:'IX', 10:'X', 40:'XL', 50:'L', 90:'XC', 100:'C', 400:'CD', 500:'D', 900:'CM', 1000:'M'}

def arabe(n):
    res = ""
    for k, v in reversed(sorted(numlist.iteritems())):
        while n >= k:
            n -= k
            res += v
    return res

print arabe(3999)
Lecureuil : quand tu utilises le copier/coller pour écrire un code, c'est forcément qu'il y a un problème, et que tu as oublié une méthode pour simplifier.

Oui, je me disais bien qu'il y avait un petit problème avec mon code...
Je ne suis pas encore à ton niveau en Python (comme tu peux le voir si tu jettes un coup d'oeil à mon blog), donc c'est peut-être pour ça aussi ?
Je n'ai pas encore vu les 'def', les 'for ... in' ; j'espère que, arrivé à ce stade, j'arriverais à synthétiser mon code pour arriver au même niveau que le tient ! (impressionnant la différence entre nos deux codes !)

candide

3 novembre 2009 à 1:28:24

Citation : bluestorm

numlist = {1:'I', 4:'IV', 5:'V', 9:'IX', 10:'X', 40:'XL', 50:'L', 90:'XC', 100:'C', 400:'CD', 500:'D', 900:'CM', 1000:'M'}

def arabe(n):
    res = ""
    for k, v in reversed(sorted(numlist.iteritems())):
        while n >= k:
            n -= k
            res += v
    return res

print arabe(3999)

Joli !!

Cacophrene

3 novembre 2009 à 6:03:08

Salut !

Remarque banale en passant : puisqu'on passe en revue tous les éléments du dictionnaire par ordre décroissant, il me semble qu'il peut être remplacé par une liste de couples.

numlist = [(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')]

def arabe(n):
    res = ""
    for k, v in numlist:
        while n >= k:
            n -= k
            res += v
    return res

C'est juste histoire de mettre mon grain de sel... ça n'apporte rien de plus à ce qui a déjà été dit précédemment.

Allez, je me lance pour la conversion romain -> arabe. D'avance désolé pour les maladresses mais je ne code pas beaucoup en Python :

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

def romain(s):
  mem = res = 0
  for i in (s + "I"):
    k = dic[i]
    if mem > 0 and k > mem:
      res += k - mem
      mem = 0
    else:
      res += mem
      mem = k
  return res

Le principe consiste à décaler l'ajout dans res et la lecture d'un caractère. On peut ainsi tenir compte des notations de type 'XC' pour 90. Évidemment il faut ajouter une lettre à la chaîne pour que la valeur associée au dernier caractère soit elle-même prise en compte dans le résultat final.

Quelques exemples :

>>> romain(arabe(3540))
3540
>>> romain(arabe(1))
1
>>> romain(arabe(3654))
3654

Cordialement,
Cacophrène

APPLEII

3 novembre 2009 à 9:31:47

Si vous voulez 16 en chiffre romain, c'est simple, vous faîtes 10 + 6, ce qui donne XVI. Vous comprenez ? "Toujours du plus grand au plus petit"

On prend un nombre et on le décompose le plus possible.

Donc en algo :

1. Rédiger une petite table des nombres romains, avec les cas comme 19, jusqu'à 1000. Pas tous les nmbres d'accord, juste certaines exceptions.
2. Prendre un nombre
3. Connaître sa taille
4. Stocker ce nombre dans un tableau, chiffre par chiffre.
5. En connaissant la taille du nombre, commencer la décomposition.

Dans le cas de 16, voici la procédure :

(C'est shématisé, ok ?)

1. 16
2. Taille 2
3. { '1', '6' }
4. Jouer sur la taille

- Je prends le 1, j'ai taille 2
- Je retire 1 à la taille, il me reste donc qu'un seul zéro
- J'obtiens 10, j'ai donc déjà X

Maintenant pour le 6

- Je prends le 6, taille 1
- Je retire 1, il ne reste plus de zéro
- J'obtiens 6, donc VI.

Voili, voilou, bonne journée

candide

3 novembre 2009 à 10:03:21

Citation : Cacophrene

Allez, je me lance pour la conversion romain -> arabe.

Il faut reprendre l'astuce de bluestorm qui consiste à mettre dans le lexique (le dictionnaire) ce qu'on trouve habituellement dans la syntaxe. En première approximation, je ferais ça mais je l'ai pas testé intensément :

numlist={ 'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000, 'IV':-2, 'IX':-2, 'XL':-20, 'XC':-20,'CD':-200, 'CM':-200}

romain=raw_input()
for k in numlist:
    s+=romain.count(k)*numlist[k]
print s

Cacophrene

3 novembre 2009 à 13:07:56

Salut !

Citation : candide

Il faut reprendre l'astuce de bluestorm qui consiste à mettre dans le lexique (le dictionnaire) ce qu'on trouve habituellement dans la syntaxe.

Je ne suis pas d'accord avec le « Il faut ». C'est certes une manière de résoudre le problème, mais ce n'est pas la seule. Je te redonne ma solution pour t'en convaincre :

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

def romain(s):
  mem = res = 0
  for i in (s + "I"):
    k = dic[i]
    if mem > 0 and k > mem:
      res += k - mem
      mem = 0
    else:
      res += mem
      mem = k
  return res

Cordialement,
Cacophrène

candide

3 novembre 2009 à 14:48:28

Citation : Cacophrene

Je ne suis pas d'accord avec le « Il faut ».

C'est une façon de parler. Mon sous-entendu est de reprendre le problème en adaptant l'astuce de bluestorm et de faire du code pythonnique.

Citation : Cacophrene

Je te redonne ma solution pour t'en convaincre :

Pas la peine de me le redonner, j'ai bien vu ton code. Tu as une une bonne astuce de mémorisation mais c'est quand même un peu tordu et l'ajout du 'I' final n'est pas terrible (autant gérer une exception). Petit détail, en Python on peut écrire :

k > mem > 0

Sinon, pour rester plus naturel, je dirais plutôt ceci :

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

def r(s):
    n=0
    old=0
    for c in reversed(s):
        n=n+dic[c] if dic[c]>=old else n-dic[c]
        old=dic[c]
    return n

Cacophrene

3 novembre 2009 à 15:04:25

Salut !

Citation : candide

C'est quand même un peu tordu et l'ajout du 'I' final n'est pas terrible

C'est sûr qu'avec la fonction reversed (que je ne savais pas applicable aux chaînes de caractères), tout est plus simple; en lisant à l'envers, on évite le problème du caractère final... J'y vois plus un manque de pratique (je préfère les chameaux) qu'une différence de fond sur la manière de résoudre le problème. Qu'on code ça comme un manche (comme moi) ou en utilisant judicieusement les fonctions disponibles dans Python (c'est ton cas), on n'a pas besoin d'ajouter CM, IX, etc. dans le dictionnaire ! D'ailleurs le code « plus naturel » ainsi obtenu ne reprend pas cette astuce.

Cordialement,
Cacophrène

Anonyme

3 novembre 2009 à 15:11:33

Edit : ca fonctionne bien, et d'ailleurs le reversed, j'y avais pas pensé, c'est super!

APPLEII

3 novembre 2009 à 15:47:49

Et mon idée ?

candide

3 novembre 2009 à 16:02:32

Citation : Cacophrene

J'y vois plus un manque de pratique (je préfère les chameaux) qu'une différence de fond sur la manière de résoudre le problème.

"De fond", je n'irais pas jusque là car le problème de la conversion romain -> arabe reste quand même simple mais il y a quand même une différence d'approche. Ton mode de mémorisation (ton drapeau mem) ne m'a pas du tout semblé naturel même si ça s'avère assez astucieux. Je préfère qualque chose de plus naturel, même si pas très élégant. Exemple qui n'utilise pas reversed() :

def r2a(s):
    n= 0
    for i in range(len(s)):
        if i<len(s)-1 and dic[s[i+1]]>dic[s[i]]:
            n-=dic[s[i]]
        else :
            n+=dic[s[i]]
    return n

Je trouve que ce code colle exactement à la façon qu'un "humain" a de décoder une écriture en chiffres romains. Pour moi, le côté naturel dans l'algorithme a une grande importance, en tous cas, un algo doit d'abord essayer d'être naturel voire naïf avant d'être subtil.

Citation : candide

(je préfère les chameaux)

J'aime pas trop les déserts

. Mais je m'y mettrai peut-être un jour rien que pour voir comment les docs sont faites.

Citation : Cacophrene

Qu'on code ça comme un manche (comme moi)

Il n'y a que toi qui le dise

Allez, on va dire que tu codes comme un manchot ...

Citation : Cacophrene

on n'a pas besoin d'ajouter CM, IX, etc. dans le dictionnaire</italique> ! D'ailleurs le code « plus naturel » ainsi obtenu ne reprend pas cette astuce.

Absolument, néanmoins un langage c'est aussi des façons idiomatiques de procéder et je pense que la méthode de bluestorm bien que peu naturelle est très pythonnique, ça me fait penser aux bouts de code que je lis sur le forum du site Project Euler où on condense 40 lignes de C en 2 lignes de Python tout en restant lisible si on a un peu l'habitude. Le C est pousse-au-crime parce qu'il y a comme une pression historique à écrire de façon du code toujours plus optimisé et avec une exécution et une mémoire "rentabilisées" (ne pas relire une variable déjà accédé, ne faire qu'un passage au lieu de deux même si ça multiplie par 10 l'écriture du code, limiter les appels de fonctions, faire plusieurs choses en même temps, etc).

Cacophrene

3 novembre 2009 à 17:58:06

Re !

Citation : candide

Je trouve que ce code colle exactement à la façon qu'un "humain" a de décoder une écriture en chiffres romains. Pour moi, le côté naturel dans l'algorithme a une grande importance, en tous cas, un algo doit d'abord essayer d'être naturel voire naïf avant d'être subtil.

En effet, nous sommes en désaccord partiel sur ce point-là. Mais c'est intéressant d'avoir des points de vue différents issus de la pratique de langages différents. Bien entendu, quand on a le choix (rare !) entre deux implémentations de même efficacité, la plus simple (ou « naturelle ») prévaut. En revanche, je préfère une version moins immédiate, voire assez compliquée pour être accompagnée de doc, dès lors qu'elle est vraiment plus performante (je parle bien entendu d'un gain substantiel lié à un changement de complexité et non à un bidouillage affreux à base de trucs et astuces bas niveau). À mon sens les versions naïves ne sont là que pour fixer les idées. Elles sont sur le brouillon, voire dans les premiers jets, mais pas plus loin.

Bon, ici on en est bien loin. Le code demandé par le PO n'est pas critique et les considérations de performances sont nulles et non avenues.

Citation : candide

Néanmoins un langage c'est aussi des façons idiomatiques de procéder

Tout à fait. Je cerne bien celles d'OCaml, mais je n'ai aucune idée de ce qu'il est courant de faire en Python.

Citation : candide

Le C est pousse-au-crime parce qu'il y a comme une pression historique à écrire de façon du code toujours plus optimisé et avec une exécution et une mémoire "rentabilisées"

Peut-être aussi parce que c'est un langage bas niveau et que ses domaines d'application privilégiés favorisent cet état d'esprit. D'un autre côté cette pratique a ses avantages. Je ne suis pas trop d'accord avec l'idée selon laquelle on peut s'autoriser plus de choses qu'auparavant parce que les ordinateurs deviennent plus puissants. Après, c'est toujours pareil, il y a le pragmatisme : optimiser une horloge pour le bureau n'est ni utile ni intéressant, et on a parfois des délais à respecter.

C'est un débat intéressant qui mériterait sans doute une discussion séparée. Je crois que ce fil a déjà un peu trop dévié. :lol:

Cordialement,
Cacophrène