Algoritmo da numero decimale a numero romano

[doom13]

Come scritto nel titolo, voi come fareste?

[Sla]

mah.. io proverei a pensare ad un algoritmo per convertire il numero decimale in romano (come da titolo )

[doom13]

è una presa per il culo xD?

[Sla]

Più o meno.. è che fa un po' ridere la domada.. perché in c++? ti aspettavi un itoa_ex(x, LANG_ROMAN)?
Mi sembra più il caso di fare una domanda in "Teoria" chiedendo un possibile algoritmo, e poi di provare a implementare il tutto in c/c++.

[doom13]

Mi sembra più il caso di fare una domanda in "Teoria" chiedendo un possibile algoritmo

Mi sembrava abbastanza ovvio...

[Sla]

Invece a me sembra tu abbia chiesto del codice in c++ per effettuare la conversione.. sarò scemo io

[doom13]

Invece a me sembra tu abbia chiesto del codice in c++ per effettuare la conversione.. sarò scemo io

Beh si in effetti hai ragione, modifico il titolo.

[Sla]

Ripristina il titolo ,altrimenti sembro idiota.
Comunque...
I simboli in ordine sono:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
Vado a intuito, potrei anche aver avuto un'idea sbagliata..
Crei un buffer di simboli (un array con molti spazi disponibili oppure una stack.. come vuoi tu)
Sia N il numero decimale intero di partenza, e value(S) il valore del simbolo S (S può essere M,D,C,L,X,V oppure I).
1) Con un ciclo che parte da S = M e risale ordinatamente fino a S=I poni C = N-Value(S).
1b) Ricorda ad ogni iterazione di controllare se N è 0, in questo caso esci dal ciclo perché la conversione è finita
2) Se C >= 0, fai un push nella stack (o buffer) con il simbolo S, poni N = C e ricominci il ciclo da capo (punto 1), con S = M )
3) altrimenti, continua il ciclo processando il prossimo simbolo

Il numero romano dovrebbe avere adesso i suoi simboli ordinatamente nella stack, il primo inserito è quello più a sinistra (il più significativo, diciamo).

[doom13]

Però c'è il problema del 9 per esempio, che comunque ha bisogno del simbolo X insieme al simbolo I.

[Sla]

Le scorciatoie di cui parli in realtà non sono necessarie (entrambe le notazioni sono accette, a quanto ricordo)

Spoiler

Per esempio per il numero 19 il mio algoritmo genererebbe
XVIIII
che è giusto.
Se proprio vuoi, però, con le giuste precauzioni, puoi fare un post-processing sulla stringa generata per cercare le "parti brutte" e sostituirle.
Il bello è che puoi operare su una qualunque parte della stringa rimpiazzando alcuni simboli con altri dal valore equivalente, questo perché la stringa romana è la stessa cosa di un polinomio {somma di più costanti}.
Il criterio per analizzare le stringhe è di avere una tabella associativa da consultare per le sostituzioni (le "giuste precauzioni" includono anche l'ordine da seguire)
IIII -> IV
LXXXX -> XC
XXXX -> XL
...

Nel caso specifico, in "XVIIII" potresti trovare la substringa "IIII" e rimpiazzarla con "IV" per ottenere "XVIV"

[doom13]

Ottenendo XVIV sarebbe quindi sbagliato perchè dovrebbe essere XIX. A questo punto servirebbe un altro controllo.

[Sla]

Hai ragione, mi chiedevo se riapplicato nuovamente il post processing si potesse ovviare..
Nel senso che nella tabella potrebbe esserci anche un VIV (=9) -> IX

[Sla]

potresti dover fare due post processing separati, con tabelle distinte.
Ma hai provato a cercare su google? la mia soluzione è intuitiva, non ci ho pensato per più di un minuto, ma figurati se non ci sono tonnellate di esempi sull'argomento in giro per il web

[doom13]

Non ho cercato su google. Questo post-processing non convince tanto anche perché le possibili combinazioni da controllare sono parecchie...

[Homunculus]

C'era la stessa domanda in un mio esame all'università (che ho prontamente saltato), ma ricordo che mi ha sorpreso la semplicità della soluzione proposta poi in seguito.

Se non ricordo male (e mi sembra che potrebbe funzionare) era una cosa del genere:

- Creo 4 array contenenti rispettivamente migliaia, centinaia, decine e unità (tipo: ["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"] per le decine)
- In seguito estraggo per ogni array l'indice adeguato in base alle migliaia, centinaia, decine e unità dal numero decimale in input (usando divisioni e moduli).
- Poi é solo una questione di concatenazione di 4 stringhe

[doom13]

Soluzione interessante. Proverò a scriverlo in c++

[BaronVsCorsar]

i numeri romani prevedono infiniti simboli per poter rappresentare infiniti numeri.
il primo passo per realizzare questo algoritmo è decidere fino a quali numeri può convertire.

per allenamento potrebbe essere intelligente partire con una conversione dei numeri da 1 a 10 (lo zero non esiste in numeri romani).
affrontato il problema dovrebbe essere più facile creare l'algoritmo (e la soluzione intelligente che propone Homu sembra proprio derivare da un allargamento degli orizzonti dell'algoritmo).