ПРЕОБРАЗУВАНЕ НА ДЕСЕТИЧНИЯ БРОЙ, ЛЕЖАЩ МЕЖДУ 1 ДО 3999 В РИМСКИ ЦИФРИ

Опитайте го на GFG практика ' title=

Като се има предвид цяло число, което го преобразува в еквивалентното му римско число представяне.

Забележка: Следва списъкът на римските символи (включително изваждане):

Символ	Стойност
I	1
IV	4
V	5
Ix	9
X	10
XL	40
L	50
Xc	90
C	100
CD	400
Г	500
Cm	900
M	1000

Примери:

Вход: 9
Резултат: Ix
Обяснение: 9 е написан като „IX“ в римски цифри, използвайки изваждаща нотация - поставяйки по -малка цифра преди по -голяма.
java е равно
I= 1X= 10
IXозначава 10 - 1 = 9
Вход: 40
Резултат: XL
Обяснение: 40 е написан като 'xl' в римски цифри, използвайки изваждане на нотация - поставяйки по -малка цифра преди по -голяма.

X= 10 L = 50
XLозначава 50 - 10 = 40

[Решение с общо предназначение] - O (n) време и o (n) пространство

Сравнете дадено число с базови стойности в поръчката 1000 900 500 400 100 90 50 40 10 9 5 4 1. След като намерим най -голямата базова стойност, която е по -малка от даденото число, ние разделяме числото с базовата стойност и повтаряме процеса за по -малки базови стойности и коефициент. Добавяме римския символ, съответстващ на основната стойност, намерена за броя на резултатите, равни на коефициента, и повтаряме процеса за остатък.

Нека разберем подхода с пример 3549

pyspark sql

Итерация 1

От 3549> = 1000; Най -голямата базова стойност ще бъде 1000 първоначално.
Разделете 3549/1000. Quotient = 3 res = 'mmm' (Забележка M принадлежи към 1000)
Остатък = 549

Итерация 2

1000> 549> = 500; Най -голямата базова стойност ще бъде 500.
Разделете 549/500. Когато = 1 .res = '300'
Остатък = 49

Итерация 3

50> 49> = 40; Най -голямата базова стойност е 40.
Разделете 49/40. Quotient = 1 res = 'mmmdxl'
Остатък = 9.

Итерация 4

Номер 9 присъства в списъка. res = 'mmmdxl'
Остатък = 0.

C++

#include    using namespace std; // Function to convert decimal to Roman Numerals string toRoman(int x) {  // array of values and symbols  vector<int> base = {1 4 5 9 10 40 50 90 100 400 500 900 1000};  vector<string> sym = {'I' 'IV' 'V' 'IX' 'X' 'XL' 'L' 'XC' 'C' 'CD' 'D' 'CM' 'M'};  // to store result  string res = '';  // Loop from the right side to find  // the largest smaller base value  int i = base.size() - 1;  while (x > 0) {  int div = x / base[i];  while (div) {  res += sym[i];  div--;  }    // Repeat the process for remainder  x = x % base[i];    i--;  }  return res; } int main() {  int x = 3549;  cout << toRoman(x);  return 0; }

Java

// Function to convert decimal to Roman Numerals public class RomanConverter {  public static String toRoman(int x) {    // array of values and symbols  int[] base = {1 4 5 9 10 40 50 90 100 400 500 900 1000};  String[] sym = {'I' 'IV' 'V' 'IX' 'X' 'XL' 'L' 'XC' 'C' 'CD' 'D' 'CM' 'M'};  // to store result  StringBuilder res = new StringBuilder();  // Loop from the right side to find  // the largest smaller base value  int i = base.length - 1;  while (x > 0) {  int div = x / base[i];  while (div > 0) {  res.append(sym[i]);  div--;  }    // Repeat the process for remainder  x = x % base[i];  i--;  }  return res.toString();  }  public static void main(String[] args) {  int x = 3549;  System.out.println(toRoman(x));  } }

Python

# Function to convert decimal to Roman Numerals def to_roman(x): # array of values and symbols base = [1 4 5 9 10 40 50 90 100 400 500 900 1000] sym = ['I' 'IV' 'V' 'IX' 'X' 'XL' 'L' 'XC' 'C' 'CD' 'D' 'CM' 'M'] # to store result res = '' # Loop from the right side to find # the largest smaller base value i = len(base) - 1 while x > 0: div = x // base[i] while div: res += sym[i] div -= 1 # Repeat the process for remainder x %= base[i] i -= 1 return res x = 3549 print(to_roman(x))

// Function to convert decimal to Roman Numerals public class RomanConverter {  public static string ToRoman(int x) {    // array of values and symbols  int[] baseValues = {1 4 5 9 10 40 50 90 100 400 500 900 1000};  string[] symbols = {'I' 'IV' 'V' 'IX' 'X' 'XL' 'L' 'XC' 'C' 'CD' 'D' 'CM' 'M'};  // to store result  string res = '';  // Loop from the right side to find  // the largest smaller base value  int i = baseValues.Length - 1;  while (x > 0) {  int div = x / baseValues[i];  while (div > 0) {  res += symbols[i];  div--;  }    // Repeat the process for remainder  x %= baseValues[i];  i--;  }  return res;  }  public static void Main() {  int x = 3549;  Console.WriteLine(ToRoman(x));  } }

JavaScript

// Function to convert decimal to Roman Numerals function toRoman(x) {    // array of values and symbols  const base = [1 4 5 9 10 40 50 90 100 400 500 900 1000];  const sym = ['I' 'IV' 'V' 'IX' 'X' 'XL' 'L' 'XC' 'C' 'CD' 'D' 'CM' 'M'];  // to store result  let res = '';  // Loop from the right side to find  // the largest smaller base value  let i = base.length - 1;  while (x > 0) {  let div = Math.floor(x / base[i]);  while (div) {  res += sym[i];  div--;  }    // Repeat the process for remainder  x %= base[i];  i--;  }  return res; } let x = 3549; console.log(toRoman(x));

Изход

MMMDXLIX

Сложност на времето: O (n) където n е дължината на низ на отговора, който съхранява преобразуването.
Спомагателно пространство: O (n)

САЩ колко града

[За ограничен обхват] - o (n) време и o (n) пространство

Идеята се основава на факта, че имаме ограничен диапазон до прикритие от 0 до 3999. Изолираме цифрите, съответстващи на хилядите стотици десетки и такива, и след това картографираме всяка цифра към съответния му римски числов еквивалент въз основа на неговата позиция.
Съхранявайте картографиране на символи M за различни коефициенти 0 1 2 3
Съхранявайте картографиране на C L и I за различни коефициенти от 0 до 9.
Използвайки горните карти, ние директно генерираме низ на резултатите.

C++

#include    using namespace std; // Function to convert decimal to Roman Numerals string toRoman(int val) {   // storing roman values of digits from 0-9  // when placed at different places  vector<string> m = {'' 'M' 'MM' 'MMM'};  vector<string> c = {'' 'C' 'CC' 'CCC' 'CD'  'D' 'DC' 'DCC' 'DCCC' 'CM'};  vector<string> x = {'' 'X' 'XX' 'XXX' 'XL'  'L' 'LX' 'LXX' 'LXXX' 'XC'};  vector<string> i = {'' 'I' 'II' 'III' 'IV'  'V' 'VI' 'VII' 'VIII' 'IX'};  // Converting to roman  string thousands = m[val / 1000];  string hundreds = c[(val % 1000) / 100];  string tens = x[(val % 100) / 10];  string ones = i[val % 10];  string ans = thousands + hundreds + tens + ones;  return ans; } int main() {  int val = 3549;  cout << toRoman(val);  return 0; }