Javascript - Перевод числа в римскую систему счисления - Stack Overflow на русском
Опубликовано: 06.09.2018
Само быстро работает массив. Второй по скорости - двоичный поиск, который позволяет за меньшее к-во шагов найти решение. Смешаный алгоритм даст лучший результат. Массив нужно выбрать... теоретически от 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..., Хотя нет - тут нужно убрать циклы вообще, просто грамотно построить дерево, и сверху вниз сравнивать + двоичный поиск. Думаю... переставлять ветви можно, и меняя их для отдельных случаев можно добится более оптимального результата, допустим если извесно что большие числа редко будут попадаться, то можно нагрузить верх "дерева" и т д.