Algoritmi per i numeri romani: Implementazione in Python, JavaScript e Java
Scopri come implementare gli algoritmi di conversione dei numeri romani in Python, JavaScript e Java. Include codice ottimizzato, analisi della complessità e spiegazione dell'algoritmo greedy.
La conversione tra numeri romani e interi è un classico problema di programmazione che compare spesso nei colloqui tecnici, nelle gare di programmazione e nelle applicazioni reali. Questa guida fornisce implementazioni ottimizzate in Python, JavaScript e Java, insieme alle spiegazioni degli algoritmi sottostanti.
Comprendere il problema
Dobbiamo risolvere due problemi correlati:
- Da intero a romano: Convertire un numero arabo (es. 1994) in numeri romani (MCMXCIV)
- Da romano a intero: Convertire i numeri romani (es. MCMXCIV) in un numero arabo (1994)
Vincoli
- Intervallo di input: da 1 a 3999 (intervallo standard dei numeri romani)
- Utilizzo della notazione sottrattiva standard (IV, IX, XL, XC, CD, CM)
- Gestione di tutte le combinazioni valide di numeri romani
L'approccio dell'algoritmo Greedy
Entrambe le conversioni utilizzano una strategia di algoritmo greedy:
Da intero a romano (Greedy)
- Creare una mappatura dei valori nei numeri romani in ordine decrescente
- Per ogni coppia valore-numero romano:
- Usare il maggior numero possibile di quel numero romano
- Sottrarre il valore dal numero rimanente
- Ripetere fino a quando il numero raggiunge lo zero
Da romano a intero (Greedy)
- Scansionare la stringa del numero romano da sinistra a destra
- Per ogni simbolo:
- Se è più piccolo del simbolo successivo, sottrarlo (notazione sottrattiva)
- Altrimenti, sommarlo
- Restituire la somma accumulata
Implementazione in Python
Da intero a romano
def int_to_roman(num: int) -> str:
"""
Converte un intero in numeri romani.
Args:
num: Intero tra 1 e 3999
Returns:
Stringa del numero romano
Complessità temporale: O(1) - numero fisso di iterazioni (13)
Complessità spaziale: O(1) - mappatura a dimensione fissa
"""
# Mappatura in ordine decrescente (incluse le combinazioni sottrattive)
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:
# Quante volte questo valore entra nel numero?
count = num // value
if count:
result.append(numeral * count)
num -= value * count
return ''.join(result)
# Esempi
print(int_to_roman(1994)) # MCMXCIV
print(int_to_roman(58)) # LVIII
print(int_to_roman(3999)) # MMMCMXCIX
Da romano a intero
def roman_to_int(s: str) -> int:
"""
Converte i numeri romani in un intero.
Args:
s: Stringa del numero romano
Returns:
Valore intero
Complessità temporale: O(n) dove n è la lunghezza della stringa
Complessità spaziale: O(1) - mappatura a dimensione fissa
"""
# Mappatura dei numeri romani ai valori
roman_map = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
result = 0
prev_value = 0
# Scansiona da destra a sinistra
for char in reversed(s):
value = roman_map[char]
# Se il valore corrente è inferiore al precedente, sottrai
if value < prev_value:
result -= value
else:
result += value
prev_value = value
return result
# Esempi
print(roman_to_int('MCMXCIV')) # 1994
print(roman_to_int('LVIII')) # 58
print(roman_to_int('IX')) # 9
Implementazione in JavaScript
Da intero a romano
/**
* Converte un intero in numeri romani
* @param {number} num - Intero tra 1 e 3999
* @returns {string} Stringa del numero romano
*/
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) {
while (num >= value) {
result += numeral;
num -= value;
}
}
return result;
}
Implementazione in Java
Da intero a romano
public class RomanConverter {
public String intToRoman(int num) {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder result = new StringBuilder();
for (int i = 0; i < values.length; i++) {
while (num >= values[i]) {
result.append(numerals[i]);
num -= values[i];
}
}
return result.toString();
}
}
Analisi dell'algoritmo
Complessità temporale
Da intero a romano:
- O(1) - Tempo costante
- Itera sempre attraverso esattamente 13 coppie valore-numero romano
- Indipendente dalla dimensione dell'input
Da romano a intero:
- O(n) - Tempo lineare
- Dove n è la lunghezza della stringa del numero romano
- Deve esaminare ogni carattere una volta
Complessità spaziale
Entrambi gli algoritmi:
- O(1) - Spazio costante
- Mappature a dimensione fissa indipendentemente dall'input
Perché l'algoritmo Greedy funziona
L'algoritmo greedy funziona per i numeri romani perché:
- Sottostruttura ottimale: La soluzione ottimale contiene soluzioni ottimali ai sottoproblemi.
- Proprietà della scelta greedy: Le scelte localmente ottimali portano a una soluzione globalmente ottimale.
- Usare sempre il valore più grande possibile garantisce la rappresentazione più breve del numero romano.
Conclusione
Gli algoritmi di conversione dei numeri romani dimostrano la potenza dell'approccio greedy per problemi con sottostruttura ottimale. Che tu ti stia preparando per un colloquio di programmazione o stia costruendo un generatore di documenti, queste implementazioni forniscono una base solida.
Per un'interfaccia facile da usare senza scrivere codice, prova il nostro convertitore di numeri romani online con risultati istantanei.
Vuoi saperne di più? Esplora la nostra guida completa ai numeri romani o scopri come usare i numeri romani in Excel.