Перевод числа в римскую систему счисления

#javascript #алгоритм #инспекция_кода

Сегодня нашел задачу для перевода числа в римскую систему счисления. Как многие знают
римляне не использовали отрицательных значений, ноль и дроби.

Решил задачу следующим образом:



function convertToRoman(number) {
  let roman = {
    "M": 1000,
    "CM": 900,
    "D": 500,
    "CD": 400,
    "C": 100,
    "XC": 90,
    "L": 50,
    "XL": 40,
    "X": 10,
    "IX": 9,
    "V": 5,
    "IV": 4,
    "I": 1
  };
  let result = "";

  for (var i of Object.keys(roman)) {
    var repeat = Math.floor(number / roman[i]);
    number -= repeat * roman[i];
    result += i.repeat(repeat);
  }

  return result;
}

//Тесты для примера
console.log(convertToRoman(100));
console.log(convertToRoman(5789));
console.log(convertToRoman(952));
console.log(convertToRoman(782));




Можно ли решить эту задачу за наименьшее количество операций? 
    

Ответы

Ответ 1

Решение через reduce:

Выглядит не тривиально, но время исполнения в 2.5 раза быстрее при 100 повторах подряд.


function convertToRoman(number) {
    return [
        { value: 1000, char: 'M' },
        { value: 900, char: 'CM' },
        { value: 500, char: 'D' },
        { value: 400, char: 'CD' },
        { value: 100, char: 'C' },
        { value: 90, char: 'XC' },
        { value: 50, char: 'L' },
        { value: 40, char: 'XL' },
        { value: 10, char: 'X' },
        { value: 9, char: 'IX' },
        { value: 5, char: 'V' },
        { value: 4, char: 'IV' },
        { value: 1, char: 'I' }
    ].reduce((result, currentValue) => {
        while (number >= currentValue.value) {
            result += currentValue.char;
            number -= currentValue.value;
        }

        return result;
    }, '');
}

//Тесты для примера
console.log(convertToRoman(100));
console.log(convertToRoman(5789));
console.log(convertToRoman(952));
console.log(convertToRoman(782));




Предлагайте свои решения, кому интересно.


Ответ 2

Само быстро работает массив. Второй по скорости - двоичный поиск, который позволяет
за меньшее к-во шагов найти решение. Смешаный алгоритм даст лучший результат. Массив
нужно выбрать... теоретически от 5 до 20. При такой реализации возможно лучше будет 40:)

var rom_hlp = ['','I','II','III','IV','V','VI','VII','VIII','IX','X'];
function convertToRoman(number) {
  if (number >= 400)  {
      if (number >= 900) {
        if (number >= 1000) return "M" + convertToRoman(number - 1000);
        else return "CM" + convertToRoman(number - 900);
        } else {
        if (number >= 500) return "D" +  convertToRoman(number - 500);
        else  return "CD" + convertToRoman(number - 400);
        }
   } else {
       if (number >=90)  {
         if (number >=100) return "C" +   convertToRoman(number - 100);
         else  return "XC" +   convertToRoman(number - 90);
       } else {
         if (number <= 10) return rom_hlp[number];
         if (number >= 40) {
             if (number >=50) return "L" +   convertToRoman(number - 50);
             else return "XL" +   convertToRoman(number - 40);
             }
         return "X" +  convertToRoman(number - 10);
       }
   }
 }


Беда, что в Javascript массив и switch работают достаточно медленно, на с++ первый
вариант с массивом на 40 дал бы лучший результат чем алгоритм ниже, за счёт того, что
массив позволяет убрать лишнии шаги, но для с++ лучше тоже убрать рекурсию.
Вариант без рекурсии, с псевдо-массивом на 10, специально что б побить reduce.

 function convertToRoman(number) {

      var r = "";


      while (number >= 400)  { /*ветвь 1*/
          if (number >= 900) {
            if (number >= 1000) { r+= "M"; number -= 1000; continue; }
            else {r += "CM"; number -= 900; continue;}
            } else { /*ветвь 1.2*/
              if (number >= 500) {
                r += "D";  number -= 500;
                if (number >= 500) {r += "D";  number -= 500;
                if (number >= 500) {r += "D";  number -= 500;
                if (number >= 400) {r += "CD";  number -= 400;}}}
                break;
               }
              else { r += "CD" ; number -=400;break;}
            }
       }; 

      if (number >=90)  /*Дерево вторая половина*/
             if (number >=100) 
                {                  
                if (number >=100)   {r += "C" ;   number -=100;
                if (number >=100)   {r += "C" ;   number -=100;
                if (number >=90) { r += "XC" ;   number -=90; }}};   
            } else { r += "XC" ;   number -=90;}



      if (number >= 40) { /*Дерево остаток*/
                 if (number >=50) {
                      r += "L" ;   number -=50; 
                    if (number >=50) {r += "L" ;   number -=50; 
                    if (number >=50) {r += "L" ;   number -=50; 
                    if (number >=40) {r += "XL" ;   number -=40; }}}

                  }
                 else {r += "XL" ;   number -=40;}
                 }                           
     if (number > 9) {
          r += "X" ;   number -=10; 
           if (number > 9) { r += "X" ;   number -=10; 
           if (number > 9) { r += "X" ;   number -=10; }}}
 // цикл нельзя (долго), switch нельзя (долго), а так - можно   
 return (number==0)?r : r+ "    I   II  III IV  V   VI  VII VIIIIX  X   ".substr(number*4,4).trim(); 
       }


Наверное совершенству нет предела, тут... я бы поискал способ поделить пополам получше,
и... добавил бы ещё goto..., Хотя нет - тут нужно убрать циклы вообще, просто грамотно
построить дерево, и сверху вниз сравнивать + двоичный поиск. Думаю... переставлять
ветви можно, и меняя их для отдельных случаев можно добится более оптимального результата,
допустим если извесно что большие числа редко будут попадаться, то можно нагрузить
верх "дерева" и т д.


Ответ 3

Ну для разнообразия:



const roman = {
  "M": 1000,
  "CM": 900,
  "D": 500,
  "CD": 400,
  "C": 100,
  "XC": 90,
  "L": 50,
  "XL": 40,
  "X": 10,
  "IX": 9,
  "V": 5,
  "IV": 4,
  "I": 1
};
const _roman = Object.entries(roman);

function toRoman (num) {
  let result = '';
  
  while (num > 0) {
    _roman.some(([key, n]) => n <= num && n % num % 1 === 0 ? (result += key, num
-= n, true) : false);
  }
  
  return result;
}

console.info(toRoman(101));
console.info(toRoman(100));
console.info(toRoman(5789));
console.info(toRoman(952));
console.info(toRoman(782));


Ответ 4

https://stackoverflow.com/questions/9083037/convert-a-number-into-a-roman-numeral-in-javascript

http://blog.stevenlevithan.com/archives/javascript-roman-numeral-converter

function romanize (num) {
    if (!+num)
        return NaN;
    var digits = String(+num).split(""),
        key = ["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM",
               "","X","XX","XXX","XL","L","LX","LXX","LXXX","XC",
               "","I","II","III","IV","V","VI","VII","VIII","IX"],
        roman = "",
        i = 3;
    while (i--)
        roman = (key[+digits.pop() + (i * 10)] || "") + roman;
    return Array(+digits.join("") + 1).join("M") + roman;
}