Это последний пост из серии Решение задач программирования с помощью PEDAC Process. В этом посте я подробно описываю, как я использовал PEDAC для написания кода, который преобразует индийско-арабские цифры (целые числа) до 3000 в эквивалентные им римские цифры.
Что такое ПЕДАК? Краткое введение.
описание проблемы
The Romans were a clever bunch. They conquered most of Europe and ruled it for hundreds of years. They invented concrete and straight roads and even bikinis. One thing they never discovered though was the number zero. This made writing and dating extensive histories of their exploits slightly more challenging, but the system of numbers they came up with is still in use today. For example the BBC uses Roman numerals to date their programmes.
The Romans wrote numbers using letters - I, V, X, L, C, D, M. (notice these letters have lots of straight lines and are hence easy to hack into stone tablets).
1 => I
10 => X
7 => VII
There is no need to be able to convert numbers larger than about 3000. (The Romans themselves didn't tend to go any higher)
Wikipedia says: Modern Roman numerals ... are written by expressing each digit separately starting with the left most digit and skipping any digit with a value of zero.
To see this in practice, consider the example of 1990. In Roman numerals 1990 is MCMXC:
1000=M
900=CM
90=XC
2008 is written as MMVIII:
2000=MM
8=VIII
Часть I. Понимание проблемы
Ввод представляет собой число в индийско-арабской системе счисления. Один из очевидных входных форматов, учитывая примеры в описании задачи, это Integer. . Первый вопрос, который возник у меня в голове, был: «Является ли целочисленная строка, например "1024" , допустимым вводом?»
Я бы точно задал этот вопрос, если бы был на собеседовании. Для целей этого поста я предполагаю, что строка целого числа является допустимым вводом.
Другие возможные вопросы:
- Что должно быть на выходе программы, если на входе ноль, поскольку в римских цифрах нет нулевого представления? Следует ли считать это плохим входом? А отрицательные числа?
- Как следует обрабатывать неверные входные данные?
Я бы обрабатывал неправильные входные данные (включая ноль и отрицательные числа), просто возвращая фразу "Invalid input”.
Я разбил проблему следующим образом:
input
- an integer or string of integer between 1 and 3000 inclusive
- convert valid inputs to their Roman numerals equivalent
- implicit knowledge
- Numbers up to 1000 and their Roman numerals equivalent
1 = I
5 = V
10 = X
50 = L
100 = C
500 = D
1000 = M
- Hindu-Arabic to Roman numerals conversion rules
- start with left most digit
- skip any digit with value zero
- for a digit between 1 and 3, its Roman equivalent is:
- Roman equivalent of its place value, digit times
examples:
- digit = 3, its place value = 1000s,
Roman equivalent is 'M', 3 times = 'MMM'
- digit = 2, its place value = 1s,
Roman Numeral equivalent is 'I', 2 times = 'II'
- digit = 1, its place value = 100s,
Roman Numeral equivalent is 'C', one time = 'C'
- if a digit is 4, or 9, its Roman equivalent is:
- Roman equivalent of its place value,
prepended to Roman equivalent of (digit + 1) * place value
examples
4
place value of 4 = 1
Roman 1 = 'I' and (4 + 1) * 1 = V
4 = I prepended to V = IV
400
place value of 4 = 100
Roman 100 = 'C' and (4 + 1) * 100 = 'D'
400 = 'C' prepended to 'D' = 'CD'
9
place value of 9 = 1
Roman 1 = 'I' and (9 + 1) * 1 = 10 = 'X'
9 = 'I' prepended to 'X' = 'IX'
90
place value of 9 = 10
Roman 10 = 'X' and (9 + 1) * 10 = 100 = 'C'
90 = 'X' prepended to 'C' = 'XC'
- if a digit is between 6 and 8, its Roman equivalent
Roman 5 prepended to Roman (digit - 5), in digit's place value
example
80
place value of 8 = 10,
Roman 5 in 10s place value = 'L',
Roman (8 - 5) in 10s place value = 'XXX'
80 = 'L' prepended to 'XXX' = 'LXXX'
output
- return Roman numeral equivalent of the input
Часть II: Примеры
Следующие примеры были даны с проблемой в качестве тестового набора
console.log(toRoman(1)); // returns 'I' console.log(toRoman(2)); // returns 'II' console.log(toRoman(3)); // returns 'III' console.log(toRoman(4)); // returns 'IV' console.log(toRoman(5)); // returns 'V' console.log(toRoman(6)); // returns 'VI' console.log(toRoman(9)); // returns 'IX' console.log(toRoman(27)); // returns 'XXVII' console.log(toRoman(48)); // returns 'XLVIII' console.log(toRoman(59)); // returns 'LIX' console.log(toRoman(93)); // returns 'XCIII' console.log(toRoman(141)); // returns 'CXLI' console.log(toRoman(163)); // returns 'CLXIII' console.log(toRoman(402)); // returns 'CDII' console.log(toRoman(575)); // returns 'DLXXV' console.log(toRoman(911)); // returns 'CMXI' console.log(toRoman(1024)); // returns 'MXXIV' console.log(toRoman(3000)); // returns 'MMM'
Я скопировал несколько примеров из набора тестов и преобразовал входные данные в целые строки,
console.log(toRoman('163')); // returns 'CLXIII'
console.log(toRoman('402')); // returns 'CDII'
console.log(toRoman('575')); // returns 'DLXXV'
console.log(toRoman('911')); // returns 'CMXI'
console.log(toRoman('1024')); // returns 'MXXIV'
console.log(toRoman('3000')); // returns 'MMM'
…и добавил несколько плохих входных данных:
console.log(toRoman(0)); // returns 'Invalid input'
console.log(toRoman(00)); // returns 'Invalid input'
console.log(toRoman(-1)); // returns 'Invalid input'
console.log(toRoman('1a4')); // returns 'Invalid input'
console.log(toRoman([208])); // returns 'Invalid input'
console.log(toRoman('0')); // returns 'Invalid input'
console.log(toRoman('0000')); // returns 'Invalid input'
console.log(toRoman('1,000')); // returns 'Invalid input'
console.log(toRoman('2 9')); // returns 'Invalid input'
console.log(toRoman(3001)); // returns 'Invalid input'
console.log(toRoman(10.24)); // returns 'Invalid input'
console.log(toRoman('10.24')); // returns 'Invalid input'
Часть III: Структура данных
Мне нужно было извлекать по одной цифре за раз, что может быть достигнуто либо с помощью оператора остатка (%) в цикле while, либо я могу преобразовать входное число в массив цифровых символов и использовать встроенные в Array итераторы, такие как карта. Я выбрал последнее, потому что абстракции приведут к более читаемому и легкому коду.
- Array. Turn input number into array of digits or digit characters
- index (position) matters (determines place value)
- map to determine value of each character(digit)
- based on place value/index
- join Roman numerals equivalent of individual digits
alternatively,
- Integer
- reminder operator(%) to get digit & place value
- hash/object
- look up table to map digits+place values with Roman equivalents
Я, вероятно, иногда буду пропускать часть ментальной модели. Я предпочитаю обдумывать и объяснять, почему я выбрал конкретную структуру данных, которая не только помогает мне иногда увидеть глупость моего выбора, но и вдвойне служит моей ментальной моделью.
Часть IV: Алгоритм
Обычно я сосредотачиваюсь только на алгоритме «счастливого пути» и беспокоюсь о защитных предложениях для неправильных входных данных и тому подобном, когда исходный код работает. Основываясь на разбивке проблемы и структуре данных, ниже приведен алгоритм, который я придумал.
- create dictionary to translate numbers to Roman symbols
RomanDictionary = {'1': 'I', '5': 'V', ..... '1000': M }
- convert input number to string, split it to array of chars, digits
- map digits toRomanNum(), join results & return Rom Num string
- toRomNum(digit, idx)
place_value = last_idx - idx
if digit < 4
return toRomanSymbol(place_value) times digit
if digit = 4 or 9
return toRomanSymbol(place_value) +
toRomanSymbol((digit + 1) * place_value)
if digit >= 6 and <= 8
return toRomanSymbol(5 * place_value) +
toRomanSymbol(place_value) times (digit - 5)
- toRomanSymbol(integer)
convert integer to string of integer, integer_string
return RomanDictionary[integer_string]
Часть V: Код
После части алгоритма исходный код, который я придумал
Приведенный выше код работает для всех допустимых входных данных, целых чисел или строковых целых чисел от 1 до 3000, но либо вызывал исключение, либо возвращал недопустимые римские цифры для неверных входных данных.
Я добавил защитное предложение для проверки недопустимых входных данных. Ниже приведен алгоритм для сторожевого предложения:
1. Check input num for valid types (string or integer)
- for string, check whether its valid
- split into array of chars
- every char must be >= '0' and <= '9'
- if valid string, convert it into an integer
- If num is integer(from input, or converted from string above)
- return num > 0 and num <= 3000
- if we reach this point, its a bad input, return false
Результирующий код ниже после добавления сторожевого предложения возвращает ожидаемые результаты для всех проверенных входных данных; действительные и недействительные.
На этом эта серия заканчивается. Спасибо за чтение.
Предыдущий пост: Использование процесса PEDAC для решения проблемы подсчета слов
