המרה רומאית של מספר שלם
נסה את זה בתרגול GFG 
תְפוּקָה
תְפוּקָה
בהינתן מחרוזת המייצגת ספר רומאי מצא שזה ערך מספר שלם.
ספרות רומיות נוצרות באמצעות הסמלים הבאים: i = 1 V = 5 x = 10 L = 50 C = 100 D = 500 ו- M = 1000.
מספרים נוצרים בדרך כלל על ידי שילוב של סמלים אלה משמאל לימין להוסיף או לחסר את ערכיהם על סמך כללים ספציפיים.
איך ההמרה עובדת?
- אם מגיע סמל ערך קטן יותר לפני שנחסר. אחרת אנחנו מוסיפים.
- ב- IV אני מגיע לפני V ו- V יש ערך גדול יותר 5. אז התוצאה שלנו היא 5 - 1 = 4.
- ב- VI V מגיע לפני שיש לי ערך קטן יותר 1. אז התוצאה שלנו היא 5 + 1 = 6.
- ב- II יש לנו ערכים זהה ולכן אנו מוסיפים ומקבלים 1 + 1 = 2
- במקרה של יותר משתי תווים אנו עוברים משמאל לימין וקבוצה רק כאשר אנו רואים אופי ערך גדול יותר על פי אופי ערך קטן יותר. לדוגמה, MXVII הוא 1000 + 10 + 5 + 1 + 1 = 1017. ו- XLVII הוא (50 - 10) + 5 + 1 + 1 = 47. שימו לב ש- L גדול יותר ומגיע אחרי X.
דוגמאות:
קֶלֶט: s = 'ix'
תְפוּקָה: 9
הֶסבֵּר: Ix הוא סמל רומאי המייצג 10 - 1 = 9קֶלֶט: s = 'xl'
תְפוּקָה: 40
הֶסבֵּר: XL הוא סמל רומאי המייצג 50 - 10 = 40קֶלֶט: s = 'mcmiv'
תְפוּקָה: 1904
הֶסבֵּר: M הוא 1000 ס"מ הוא 1000 - 100 = 900 ו- IV הוא 4. אז יש לנו סה"כ כ 1000 + 900 + 4 = 1904
טבלת תוכן
- [גישה צפויה 1] באמצעות השוואה איטרטיבית - O (n) זמן ו- O (1) שטח
- [גישה צפויה 2] שימוש ב- Hashing - O (n) זמן ו- O (1) שטח
[גישה צפויה 1] שימוש בהשוואה איטרטיבית - O (n) זמן ו- O (1) שטח
C++הרעיון להמרת ספר רומאי למספר שלם הוא שעלינו לחצות את המיתר משמאל לימין. עבור כל סמל השווה אותו לסמל הבא (אם הוא קיים). אם הסמל הנוכחי גדול או שווה לסמל הבא, הוסף את ערכו לתוצאה. אחרת הפחיתו את ערכו מערך הסמל הבא והוסיפו את התוצאה לסך הכל ודלגו על הסמל הבא.
#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 ));
תְפוּקָה
9
[גישה צפויה 2] שימוש ב- Hashing - O (n) זמן ו- O (1) שטח
C++אנו יכולים להשתמש במפת חשיש או במילון כדי לאחסן את ערכי הסמלים הרומאים. וכדי לפתור את הבעיה שיש לנו לחזור דרך המחרוזת ולכל סמל בדוק אם הערך הנוכחי פחות מהערך הבא. אם הפחיתו את הערך הנוכחי מהערך הבא והוסיפו את התוצאה לסך הכל. אחרת הוסף את הערך הנוכחי לסך הכל.
#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 ));
תְפוּקָה
9
