Перевод числа в римскую систему счисления — javascript алгоритм инспекция-кода

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд
Загрузка...

Вопрос:


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

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

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

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

Автор вопроса:

Решение через 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));

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

Само быстро работает массив. Второй по скорости — двоичный поиск, который позволяет за меньшее к-во шагов найти решение. Смешаный алгоритм даст лучший результат. Массив нужно выбрать… теоретически от 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…, Хотя нет — тут нужно убрать циклы вообще, просто грамотно построить дерево, и сверху вниз сравнивать + двоичный поиск. Думаю… переставлять ветви можно, и меняя их для отдельных случаев можно добится более оптимального результата, допустим если извесно что большие числа редко будут попадаться, то можно нагрузить верх «дерева» и т д.

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

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

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

Источник

Вам также может быть интересно:

Переадресация запросов по данным из тела запроса — java nginx spring-mvc
Вопрос: Существует сервис с "кучей" контроллеров. Стоит задача "распилить" данный сервис на микросервисы. Сами микросервисы будут крутится на самостоятельных машинах. Основная проблема в том, что есть ...
Java. Деление в столбик. Съезжает вывод в консоль — java
Вопрос: Кто-нибудь может подсказать почему при делении 1034/15 съезжает вывод в консоль? public class Division { private StringBuffer result = new StringBuffer(); ...
Доступ к cookies другого сайта — javascript
Вопрос: Не знаю, или правильно написал вопрос в заголовке. Вообще вопрос такой. Есть, например виджет коминтариев фб, его можно установить на свой сайт. При заходе, он ...
Не видит загрузочной флешки с Ubuntu — linux windows ubuntu
Вопрос: Решил установить Ubuntu второй ОС. Скачал образ и установил его на флешку. Память для будущей Ubuntu выделил ещё когда устанавливал Windows. Проблема в том, что когда ...
Как устроен Netty? — java async netty
Вопрос: Немного почитал про асинхронные сокеты и про фреймворк Netty, но у меня возник вопрос о том как устроен механизм обработки многочисленных запросов к Netty. ...
Как реализовать правильную связь классов в javascript? — javascript ооп полиморфизм
Вопрос: Теперь в деталях : имеются несколько классов : class RemovedItem { constructor(value, key) { this.value = value; ...
Модификация Observable при помощи дополнительного запроса в сеть — android kotlin rxjava
Вопрос: работаю с Vk.APi и произвожу поиск списка групп. В ответе с API получаю список групп, но проблема в том, что каждая из них не содержит ...
Как загрузить Layout в Activity или View из переменной типа String — android xml activity
Вопрос: Обычно внешний вид Activity или View загружается из файлов типа *.xml, вложенных в папку res/layout проекта. А как сделать, чтобы внешний вид загружался из ...
Как выбрать максимальное значение в столбце? — sql sql-server
Вопрос: У меня есть таблица которая состоит из 2 столбцов OrderID OrderDate ------------------------------- 1021 1976-07-04 00:00:00 2312 ...
Форма TextView XML — android xml
Вопрос: Прошу понять меня правильно: Я не прошу что-то сделать за меня и предоставить готовый код ВОПРОС: Какие атрибуты необходимо использовать, чтобы выполнить такой же вид ...
Отловить закрытие консольной программы — c# console
Вопрос: Есть консольное приложение (C#), мне нужно отловить событие его закрытия. Это может быть и Ctrl+C и нажатие на крестик, вообще любое событие после которого ...
Странное поведение jQuery — jquery
Вопрос: Есть веб-страница, на которой естественно имеются стили и скрипты. При очистке кэша и полной перезагрузке страницы (Ctrl + F5) jQuery неправильно определяет height() и ...
Оверлей для любой программы и игры DirectX в фуллскрине через инжект dll — c# wpf
Вопрос: Всем привет. Хочу сделать универсальный оверлей, который при запуске из консольного приложения будет инжектить dll с самим оверлеем в любую программу, как у стима/дискорда. Про инжект ...
Использование, связка бинов в Java — java netbeans xhtml
Вопрос: У меня есть example.xhtml, я не знаю как правильно его заполнить, так как NetBeans предлагает один вариант, а видео, где все работает, заполняют по-другому.Netbeans: <?xml ...
Удалил rfremix-relese при попытке обновления — linux fedora
Вопрос: Сегодня хотел обновить Руссиан Федора Ремикс (RFRemix) 28->29. dnf upgrade выдал сообщение о конфликте в пакете rfremix-release-2.ххххххх Немного посомневался, но решил что это модуль именно ремикса ...

Оставьте ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *