Постановка задачи
Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.
M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.
Входные данные
В строке записано два числа в римской системе счисления, между которыми стоит знак + .
Выходные данные
Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами.
Алгоритм решения
Считываем два числа и представляем каждое из них в десятичной системе счисления. Чтобы перевести число из римской системы в десятичную, нужно изначально считать, что в десятичной системе оно равно нулю. Это число будет нашим результатом. Далее, нужно перебрать все цифры римского числа, следуя таким правилам:
- если цифра, стоящая слева от даной цифры, больше нее, то вычитаем ее из результата;
- если цифра, стоящая слева от даной цифры, меньше нее, то прибавляем ее к результату;
- если слева от даной цифры нет цифр, ничего не делаем.
После перебора всех цифр римского числа, значение результата будет совпадать со значением даного римского числа в десятичной системе счисления. Теперь нам необходимо сложить два полученый числа и представить сумму уже в римской системе. Для этого нам понадобятся вспомогательные числа, представленые ниже как в римской, так и в десятичной системе счисления в порядке возрастания.
| Вспомогательные числа | |
| В римской системе счисления | В десятичной системе счисления |
| 1 | I |
| 4 | IV |
| 5 | V |
| 9 | IX |
| 10 | X |
| 40 | XL |
| 50 | L |
| 90 | XC |
| 100 | C |
| 400 | CD |
| 500 | D |
| 900 | CM |
| 1000 | M |
Выбираем самое последнее число из таблицы, которое является самым большим, и, пока оно не превышает суммы, вычитаем из суммы это число и выводим выбраное число в римской системе счисления. Далее выбираем предыдущее число и проделываем аналогичные действия. Эти действия проделываем до тех пор, пока сумма не окажется равной нулю. Таким образом мы получим сумму, представленную в римской системе счисления.
Тесты
| Входные данные | Выходные данные |
| I+I | II |
| IV+VIII | XII |
| MM+CXC | MMCXC |
| CXCIX+I | CC |
Реализация
ideone: ссылка
Засчитаное решение на e-olymp: ссылка
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <cstring> using namespace std; int parse(char digit) { int result; switch(digit) { case 'I': result = 1; break; case 'V': result = 5; break; case 'X': result = 10; break; case 'L': result = 50; break; case 'C': result = 100; break; case 'D': result = 500; break; case 'M': result = 1000; break; default: result = 0; } return result; } int parse(char *number) { int result = 0, previous = parse(number[0]), current; for(int i = 1; (current = parse(number[i])) != 0; i++) { result += previous < current ? -previous : previous; previous = current; } result += previous; return result; } void print(int number) { char result[1000]{'\0'}; const int values[] = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 }; const char *symbols[] = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" }; int counter = sizeof(symbols) / sizeof(symbols[0]) - 1 // last array element while(counter >= 0) { while(number >= values[counter]) { number -= values[counter]; strcat(result, symbols[counter]); } counter--; } cout << result << endl; } int main() { char line[1000]; cin >> line; char *a = strtok(line, "+"); char *b = strtok(NULL, ""); print(parse(a) + parse(b)); return 0; } |