Перевод числа в римскую систему счисления — 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;
}

Источник

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

Использование вложенных маршрутов в React Router — javascript reactjs react-router
Вопрос: Для организации маршрутов в приложении использую React Router. <Route path="/" component={...}> <IndexRoute component={...}/> <Route path="user/:userId" component={...}> ...
Как с помощью Retrofit 2.0 отправить данные в JSON на сервер и получить ответ? — java android retrofit
Вопрос: Только начал читать про Retrofit 2.0 до этого использовал HttpURLConnection. Как я работаю с HttpURLConnection, формирую Json перевожу его в byte, ставлю header в ...
Не приходят push уведомления. FCM — android firebase android-notification
Вопрос: Появилась необходимость реализовать push уведомления. Прописал в манифесте сервис: <service android:name=".MyFirebaseMessagingService"> <intent-filter> ...
Принцип браузерной игры в линукс терминале — java linux terminal
Вопрос: Наткнулся на Java библиотеку CHARVA. И хотел бы уточнить у знающих людей, возможно ли на основе данной библиотеки сделать программу по принципу браузерной игры, но ...
Мерцание заблокированного экрана при выключенной подсветке в Debian 8 Gnome 3 — linux debian экран
Вопрос: На ноутбуке с Debian 8 Jessie и Gnome 3 имеется следующая проблема. При выключенном заблокированном экране сквозь него можно наблюдать, как весь экран становится белым, ...
Создание WCF клиента на готовый SOAP web сервер — c# wcf
Вопрос: Доброго времени суток. Появилась задача опрашивать web сервер с клиента на котором планируется написать WCF клиентскую часть. Информации про сервер очень мало (не знаю платформу ...
Безопасно ли удалить файл логов general_log.txt? — mysql
Вопрос: При выполнении запроса со вставкой данных большого объёма SQLyog начал вылетать с ошибкой: not enough memory application terminated В связи с этим я решила ...
Callback функции создания таблицы mysql в nodejs — mysql node.js callback
Вопрос: Есть функция, которая при запуске создает базу даных, function showDb() { pool.query("show databases like 'bt' ",function (err, ...
Как создать Adapter с неограниченным количеством строк и с неограниченным разным количеством столбцов в каждой строке — java android
Вопрос: Как создать Adapter с неограниченным количеством строк и с неограниченным разным количеством столбцов в каждой строке Автор вопроса: Salut Amigo Источник
Не могу передать байтовый массив в контроллер — c# asp.net-mvc entity-framework
Вопрос: У меня изображения храняться в бд в формате байтового массива, через форич отлично все выводит, но когда я хочу открыть страницу для работы с ...
proguard release error — java android mvp
Вопрос: Включил в проекте proguard, apk собирается, все хорошо, но приложение не работает) Proguard-rules.pro -keepattributes InnerClasses -keepattributes EnclosingMethod -keepattributes *Annotation* -dontoptimize # Keep Butterknife -keep class butterknife.** { *; } -dontwarn butterknife.internal.** -keep ...
Не отрабатывает page:update — javascript ruby-on-rails
Вопрос: Есть мой учебный проект на ruby. Делаю редактирование объектов с помощью JS. Сейчас работает так: Редактирую первый раз - всё нормально. Не обновляя страницу, ...
Как найти определенный символ в строке и удалить значение после него (и вместе с ним) Jquery — javascript html jquery
Вопрос: Здравствуйте, есть определенный набор строк, типа "L / Красный / 12345", как можно на странице найти их, и вырезать из них все что находится ...
Почему не работает wildcard module declaration? — typescript
Вопрос: Почему не работает такой способ декларации: declare module "*!text" {} ? Цель - использовать контент файла в переменной: import layout = require("/js/views/layouts/wnd.html!text"); или так: import layout from "/js/views/layouts/wnd.html!text"; Если ...
Как прервать 3rd-party код? — c# многопоточность .net-core
Вопрос: Есть 3rd-party код из библиотеки который "зависает" в ожидании где-то в работе с сетью. CancellationToken поддержки нет, таймаутов нет. Запускаю я его через: Task.Run(() => ...

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

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