Romiešu uz veselu skaitļu konvertāciju
Izmēģiniet to GFG praksē 
Izvade
Izvade
Ņemot vērā virkni, kas attēlo romiešu ciparu, atrodiet atbilstošo veselo skaitli.
Romiešu cipari tiek veidoti, izmantojot šādus simbolus: I = 1 V = 5 x = 10 l = 50 c = 100 d = 500 un M = 1000.
Skaitļi parasti veidojas, apvienojot šos simbolus no kreisās uz labo pusi, pievienojot vai atņemot to vērtības, pamatojoties uz īpašiem noteikumiem.
Kā darbojas pārveidošana?
- Ja pirms atņemšanas nāk mazāks vērtības simbols. Pretējā gadījumā mēs pievienojam.
- IV es nāku pirms V un V ir lielāka vērtība 5. Tātad mūsu rezultāts ir 5 - 1 = 4.
- VI V nāk pirms I un man ir mazāka vērtība 1. Tātad mūsu rezultāts ir 5 + 1 = 6.
- II iekšpusē mums ir vienādas vērtības, tāpēc mēs pievienojam un saņemam 1 + 1 = 2
- Vairāk nekā 2 rakstzīmju gadījumā mēs šķērsojam no kreisās uz labo un grupām tikai tad, kad pēc mazākas vērtības rakstzīmes redzam lielāku vērtības rakstzīmi. Piemēram, MXVII ir 1000 + 10 + 5 + 1 + 1 = 1017. un XLVII ir (50 - 10) + 5 + 1 + 1 = 47. Ņemiet vērā, ka L ir lielāks un nāk pēc X.
Piemēri:
Ievade: s = 'ix'
Izlaide: 9
Paskaidrojums: IX ir romiešu simbols, kas apzīmē 10 - 1 = 9Ievade: s = 'XL'
Izlaide: 40
Paskaidrojums: XL ir romiešu simbols, kas apzīmē 50–10 = 40Ievade: s = 'McMiv'
Izlaide: 1904
Paskaidrojums: M ir 1000 cm ir 1000 - 100 = 900 un IV ir 4. Tātad mums ir kopsumma 1000 + 900 + 4 = 1904
Satura rādītājs
- [Paredzamā pieeja 1] Izmantojot iteratīvo salīdzinājumu - O (n) laiks un O (1) telpa
- [Paredzamā pieeja 2] Izmantojot hashing - o (n) laiku un O (1) telpu
[Paredzamā pieeja 1] Izmantojot iteratīvo salīdzinājumu - O (n) laiks un O (1) telpa
C++Ideja par romiešu ciparu pārveidošanu par veselu skaitli ir tāda, ka mums ir jāietver virkne no kreisās uz labo pusi. Katram simbolam to salīdziniet ar nākamo simbolu (ja tāds pastāv). Ja strāvas simbols ir lielāks vai vienāds ar nākamo simbolu, tad rezultātam pievienojiet tā vērtību. Pretējā gadījumā atņemiet tā vērtību no nākamā simbola vērtības un pievienojiet rezultātu kopējam un izlaidiet nākamo simbolu.
#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 ));
Izvade
9
[Paredzamā pieeja 2] Izmantojot hashing - o (n) laiku un O (1) telpu
C++Romiešu simbolu vērtību saglabāšanai mēs varam izmantot hash karti vai vārdnīcu. Un, lai atrisinātu problēmu, mums ir jāatstāj caur virkni un katram simbolam pārbaudiet, vai pašreizējā vērtība ir mazāka par nākamo vērtību. Ja tā, atņemiet pašreizējo vērtību no nākamās vērtības un pievienojiet rezultātu kopējai. Pretējā gadījumā pievienojiet kopējai pašreizējo vērtību.
#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 ));
Izvade
9
