Conversie van Romeins naar geheel getal
Probeer het eens op GfG Practice 
Uitvoer
Uitvoer
Gegeven een string s die een Romeins cijfer vertegenwoordigt, zoek dan de bijbehorende gehele waarde.
Romeinse cijfers worden gevormd met behulp van de volgende symbolen: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 en M = 1000.
Getallen worden doorgaans gevormd door deze symbolen van links naar rechts te combineren en hun waarden op te tellen of af te trekken op basis van specifieke regels.
Hoe werkt de conversie?
- Als er een kleiner waardesymbool komt voordat we aftrekken. Anders voegen wij toe.
- In IV komt I vóór V en heeft V een grotere waarde 5. Ons resultaat is dus 5 - 1 = 4.
- In VI komt V vóór I en I heeft een kleinere waarde 1. Ons resultaat is dus 5 + 1 = 6.
- In II hebben we dezelfde waarden, dus we tellen op en krijgen 1 + 1 = 2
- In het geval van meer dan 2 tekens doorlopen we van links naar rechts en groeperen we alleen als we na een teken met een kleinere waarde een teken met een grotere waarde zien. MXVII is bijvoorbeeld 1000 + 10 + 5 + 1 + 1 = 1017. En XLVII is (50 - 10) + 5 + 1 + 1 = 47. Merk op dat L groter is en na X komt.
Voorbeelden:
Invoer: s = 'IX'
Uitgang: 9
Uitleg: IX is een Romeins symbool dat 10 - 1 = 9 vertegenwoordigtInvoer: s = 'XL'
Uitgang: 40
Uitleg: XL is een Romeins symbool dat 50 - 10 = 40 vertegenwoordigtInvoer: s = 'MCMIV'
Uitgang: 1904
Uitleg: M is 1000 CM is 1000 - 100 = 900 en IV is 4. Dus we hebben een totaal van 1000 + 900 + 4 = 1904
Inhoudsopgave
- [Verwachte aanpak 1] Iteratieve vergelijking gebruiken - O(n) tijd en O(1) ruimte
- [Verwachte aanpak 2] Hashing gebruiken - O(n) tijd en O(1) ruimte
[Verwachte aanpak 1] Iteratieve vergelijking gebruiken - O(n) tijd en O(1) ruimte
C++Het idee voor het omzetten van een Romeins cijfer naar een geheel getal is dat we de string van links naar rechts moeten doorlopen. Vergelijk elk symbool met het volgende symbool (als het bestaat). Als het huidige symbool groter is dan of gelijk is aan het volgende symbool, tel dan de waarde ervan op bij het resultaat. Trek anders de waarde ervan af van de waarde van het volgende symbool, tel het resultaat op bij het totaal en sla het volgende symbool over.
#include using namespace std ; // this function returns value of a Roman symbol int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return -1 ; } // returns decimal value of roman numeral int romanToDecimal ( string & s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // Compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( String s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { //get value of current symbol int s1 = value ( s . charAt ( i )); // compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s . charAt ( i + 1 )); // If current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python # this function returns value of a Roman symbol def value ( r ): if r == 'I' : return 1 if r == 'V' : return 5 if r == 'X' : return 10 if r == 'L' : return 50 if r == 'C' : return 100 if r == 'D' : return 500 if r == 'M' : return 1000 return - 1 # returns decimal value of roman numeral def romanToDecimal ( s ): res = 0 i = 0 while i < len ( s ): # get value of current symbol s1 = value ( s [ i ]) # compare with the next symbol if it exists if i + 1 < len ( s ): s2 = value ( s [ i + 1 ]) # if current value is greater or equal # add it to result if s1 >= s2 : res += s1 else : # else add the difference and # skip next symbol res += ( s2 - s1 ) i += 1 else : res += s1 i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( string s ) { int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . Length ) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript // this function returns value of a Roman symbol function value ( r ) { if ( r === 'I' ) return 1 ; if ( r === 'V' ) return 5 ; if ( r === 'X' ) return 10 ; if ( r === 'L' ) return 50 ; if ( r === 'C' ) return 100 ; if ( r === 'D' ) return 500 ; if ( r === 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral function romanToDecimal ( s ) { let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // get value of current symbol let s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . length ) { let s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and // skip next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Uitvoer
9
[Verwachte aanpak 2] Hashing gebruiken - O(n) tijd en O(1) ruimte
C++We kunnen een hashkaart of woordenboek gebruiken om de waarden van Romeinse symbolen op te slaan. En om het probleem op te lossen moeten we de string doorlopen en voor elk symbool controleren of de huidige waarde kleiner is dan de volgende waarde. Trek in dat geval de huidige waarde af van de volgende waarde en tel het resultaat bij het totaal op. Voeg anders de huidige waarde toe aan het totaal.
#include #include using namespace std ; int romanToDecimal ( string & s ) { unordered_map < char int > romanMap = {{ 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 }}; int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java import java.util.HashMap ; class GfG { static int romanToDecimal ( String s ) { HashMap < Character Integer > romanMap = new HashMap <> (); romanMap . put ( 'I' 1 ); romanMap . put ( 'V' 5 ); romanMap . put ( 'X' 10 ); romanMap . put ( 'L' 50 ); romanMap . put ( 'C' 100 ); romanMap . put ( 'D' 500 ); romanMap . put ( 'M' 1000 ); int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap . get ( s . charAt ( i )) < romanMap . get ( s . charAt ( i + 1 ))) { res += romanMap . get ( s . charAt ( i + 1 )) - romanMap . get ( s . charAt ( i )); // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap . get ( s . charAt ( i )); } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python def romanToDecimal ( s ): romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 } res = 0 i = 0 while i < len ( s ): # if the current value is less than the next value # subtract current from next and add to res if i + 1 < len ( s ) and romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]: res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]] # skip the next symbol i += 1 else : # otherwise add the current value to res res += romanMap [ s [ i ]] i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; using System.Collections.Generic ; class GfG { static int romanToDecimal ( string s ) { // create a map to store the Roman numeral values Dictionary < char int > romanMap = new Dictionary < char int > { { 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 } }; int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . Length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript function romanToDecimal ( s ) { // create a map to store the Roman numeral values const romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 }; let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Uitvoer
9
