logo

TechCodeview

Roman til heltallkonvertering

Prøv det på GFG -praksis ' title=

Gitt en streng som representerer et romersk tall, finner det tilsvarende heltallverdien.
Romerske tall dannes ved bruk av følgende symboler: i = 1 V = 5 x = 10 l = 50 c = 100 d = 500 og m = 1000.
Tall dannes vanligvis ved å kombinere disse symbolene fra venstre til høyre å legge til eller trekke fra verdiene sine basert på spesifikke regler.

streng sammenlignet med java

Hvordan fungerer konverteringen?

  • Hvis et symbol på mindre verdier kommer før vi trekker fra. Ellers legger vi til.
  • I IV kommer jeg før V og V har en større verdi 5. Så resultatet vårt er 5 - 1 = 4.
  • I VI V kommer før jeg og jeg har en mindre verdi 1. Så resultatet vårt er 5 + 1 = 6.
  • I II har vi samme verdier, så vi legger til og får 1 + 1 = 2
  • I tilfelle av mer enn 2 tegn krysser vi fra venstre mot høyre og gruppe bare når vi ser en større verdiskarakter etter en karakter med mindre verdi. For eksempel er MXVII 1000 + 10 + 5 + 1 + 1 = 1017. Og XLVII er (50 - 10) + 5 + 1 + 1 = 47. Merk at L er større og kommer etter X.

Eksempler:



: s = 'ix'
Produksjon: 9
Forklaring: IX er et romersk symbol som representerer 10 - 1 = 9

: s = 'xl'
Produksjon: 40
Forklaring: XL er et romersk symbol som representerer 50 - 10 = 40

: s = 'McMiv'
Produksjon: 1904
Forklaring: M er 1000 cm er 1000 - 100 = 900 og IV er 4. så vi har totalt som 1000 + 900 + 4 = 1904

delvis derivatsymbol lateks

Tabell over innhold

[Forventet tilnærming 1] Bruke iterativ sammenligning - O (n) tid og O (1) plass

Ideen for å konvertere et romersk tall til et heltall er at vi må krysse strengen fra venstre til høyre. For hvert symbol sammenligner det med neste symbol (hvis det finnes). Hvis det gjeldende symbolet er større enn eller lik neste symbol, legger du verdien til resultatet. Ellers trekker verdien fra neste symbols verdi og legger resultatet til totalen og hopper over neste symbol.

ascii tabell java
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));

Produksjon 
9

[Forventet tilnærming 2] Bruke hashing - o (n) tid og o (1) plass

Vi kan bruke et hasjkart eller ordbok for å lagre verdiene til romerske symboler. Og for å løse problemet må vi iterere gjennom strengen og for hver symbolsjekk om gjeldende verdi er mindre enn neste verdi. I så fall trekker du gjeldende verdi fra neste verdi og legger resultatet til totalen. Ellers tilfører gjeldende verdi til totalen.

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));

Produksjon 
9