Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/24: Рейтинг темы: голосов - 24, средняя оценка - 4.58
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
1

Запись числа римскими цифрами

08.11.2013, 14:36. Просмотров 4592. Ответов 18
Метки нет (Все метки)

Всем доброго времени суток. Третий день не могу подобрать более-менее внятный алгоритм к такой задаче - на вход программе задаётся строка определённой длины, элементы которой -"цифры" римской системы счисления (т.е. M, D, C, L, X, V, I, их "веса" соответственно 1000, 500, 100, 50, 10, 5, 1), также на вход задаётся число десятичной системы счисления. Необходимо проверить, можно ли, используя ВСЕ до единого символы из введённой строки, записать данное десятичное число в римской СС. Если можно, то вывести один из вариантов его записи, если нельзя, то вернуть соответствующее сообщение. Перевод числа из римской в десятичную СС осуществляется по принципу: Ищется самая значимая цифра в записи, если таковых несколько, то точкой отсчёта считается самая левая из них, можно обозначить её вес как a. Суммарный вес того, что левее неё как b, а того, что правее как с, тогда суммарное значение данного числа в десятичной СС равно a+c-b. Т.е. при таком методе как я понимаю есть явный намёк на динамическое программирование.

Т.е. например мы имеем на вход строку VIICVXX и число 90, тогда его можно записать как IXVXICV.
Если у нас, например, на входе строка XIVX, то число 17 мы записать не сможем.
Прошу помочь с объяснением алгоритма для такой задачи. С последующей реализацией на сам язык программирования проблем нет, тут ступор непосредственно на более раннем уровне решения.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.11.2013, 14:36
Ответы с готовыми решениями:

для записи римскими цифрами...
Для записи римскими цифрами используются символы I, V, X, L, C, D, M...

Найти такие числа, запись которых совпадает с последними цифрами записи их квадратов
Дано натуральное число n. Среди чисел 1,..., n найти такие, запись которых...

Среди чисел 1,…,n найти все такие, запись которых совпадает с последними цифрами их куба
Дано натуральное число n. Среди чисел 1,…,n найти все такие, запись которых...

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

Проверить, есть ли в записи числа m цифры, совпадающие с цифрами в записи числа n
не решается задачка :с помогите, пожалуйста. все что смог, изложил. это...

18
buntar
524 / 525 / 181
Регистрация: 16.03.2012
Сообщений: 1,160
Записей в блоге: 2
08.11.2013, 15:20 2
http://all-blogspot.com/2009/09/c_15.html
Вот полный код
http://rabus.ru/Arab2Roman.html
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 15:44  [ТС] 3
Эм... Тут же вроде немного не то... Тут на входе только число и выводится первый возможный его вид в римской СС, т.е. оно заведомо переводимо, и набор знаков у нас неограничен, а в задаче выше набор знаков строго задан на вход, причём должен использоваться весь, и не факт, что с его помощью можно будет что-то записать.
0
buntar
524 / 525 / 181
Регистрация: 16.03.2012
Сообщений: 1,160
Записей в блоге: 2
08.11.2013, 16:17 4
Цитата Сообщение от vindex Посмотреть сообщение
Эм... Тут же вроде немного не то... Тут на входе только число и выводится первый возможный его вид в римской СС, т.е. оно заведомо переводимо, и набор знаков у нас неограничен, а в задаче выше набор знаков строго задан на вход, причём должен использоваться весь, и не факт, что с его помощью можно будет что-то записать.
А вы думаете вам уже готовый код на блюдечке будет? Никто и не говорил что допиливать не придется!
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 16:21  [ТС] 5
Так методика совсем другая, ибо задача отличается условием на самом корню. Да и код я как бы не просила, мне бы понять очерёдность действий на пути к формированию ответа.... Как-то так...
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
08.11.2013, 19:06 6
Цитата Сообщение от vindex Посмотреть сообщение
Т.е. например мы имеем на вход строку VIICVXX и число 90, тогда его можно записать как IXVXICV.
Почему его можно так записать? Это соответствует правилам записи римских чисел? Я не могу прочитать это число как 90
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 19:32  [ТС] 7
Вот в том-то и дело, что для записи используется в условии данной задачи слегка странноватый алгоритм (придумала его не я, поверьте, у меня нет задачи кого-либо тут преднамеренно вводить в заблуждения ошибочными данными),
по алгоритму находим самый большой символ (С), это 100, раскладываем левую от этого С часть - там находим самый большой символ (левый X, что равно 10, слева от него 1, справа до С невключительно снова раскладываем (там остаются 'VXI'), находим среди них больший (Х), это 10, слева V(5), справа I(1), восстанавливаем ответ по алгоритму выше - к 10 прибавляем 1, отнимаем 5, это 6, возвращаемся на "уровень" назад слева от левой Х остался I, т.е. единица, справа получили данные 6, 10+6-1=15, т.е. в итоге то, что левее С это 15. Теперь о том, что правее С:там лишь один символ - это V, вес правой относительно С части равен 5, по алгоритму задачи итоговый ответ С+правая часть-левая часть это 100+5-15=90. Фууухххх... Вроде всё.
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
08.11.2013, 21:52 8
Но ведь задача обратная: из десятичной записи перевести в римскую и записать. Т.е. задача сводится к получению заданного числа из набора чисел, используя только сложение и вычитание. Пример с 90 можно записать как:
Код
{5, 1, 1, 100, 5, 10, 10} = 100 - (10 - 5 + 1) - (10 - 1) + 5
Как разложить на эти составляющие? Вот над чем нужно думать

Добавлено через 1 минуту
ничего, кроме перебора всех вариантов сочетаний плюсов и минусов пока в голову не приходит
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 22:04  [ТС] 9
Да, задача обратная, эт ещё больше сложности и прибавляет... Нашла чуть больше информации по входным данным - кол-во римских цифр в строке не более 50, т.е. в принципе количество переборов потенциально не самое высокое... Но как устроить такой перебор, идей пока нету. Начать я так понимаю нужно с поиска самой большой по весу римской цифры в строке, сравнить её значение со входным числом, и от этого уже как-то дальше заполнять запись в соответствующем порядке.
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
08.11.2013, 22:08 10
Последовательность рассуждений:
  1. 100 - 10 = 90
  2. 100 - 10 + 10 = 100
  3. 100 - 10 + 10 - 5 = 95
  4. 100 - 10 + 10 - 5 - 5 = 90
  5. 100 - 10 + 10 - 5 - 5 + 1 = 91
  6. 100 - 10 + 10 - 5 - 5 + 1 - 1 = 90
На словах.
Берём максимальное число. Вычитаем из него максимальное из оставшихся. Если результат меньше или равен искомому числу, прибавляем максимальное из оставшихся. Если результат больше искомого числа - вычитаем максимальное из оставшихся. Продолжаем действовать таким образом, пока не закончатся все числа. Если исчерпались все числа, а результат не равен искомому числу, значит искомое число невозможно записать используя все данные числа (требуется доказательство, что это так)
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 22:21  [ТС] 11
Спасибо за идею, попробую более-менее расписать метод на бумаге, единственное, что меня смущало с самого первого прочтения, это следствие из того метода представления чисел, т.е. по сути набором {X, X, I} 19 может быть одновременно как 'IXX' и как 'XIX'... Как бы по ходу рассчётов какое-то единственно верное возможное решение не потерять.
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
08.11.2013, 22:26 12
Цитата Сообщение от vindex Посмотреть сообщение
т.е. по сути набором {X, X, I} 19 может быть одновременно как 'IXX' и как 'XIX'...
Не может. При записи IXX это будет не 19 (10+10-1), а 11 (10 - (10 - 1)), потому что веса обоих X равны и они не могут складываться. Кроме того, как мне кажется, нужно, чтобы правее числа с самым большим весом не было чисел большего или равного веса.
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
08.11.2013, 22:36  [ТС] 13
Вот тут я так понимаю главная сложность в подборе алгоритма и состоит в том, что вес числа считается по схеме "большой символ"+вес того, что справа - вес того, что слева. Это уже подтверждённый факт (на каком-то сайте нашла и перечитала ещё раз эту задачу, всё верно, манера записи преднамеренно отличается от классической записи римскими цифрами). Возможно придётся тупо создавать какую-то процедуру, которая перебирает вообще все возможные расположения элементов в данной строке и подсчитывает по той указанной схеме значение получившегося числа, потом это значение каждый раз сравнивать со входным десятичным числом, и так до первого равенства, либо до исчерпания всех возможных перестановок в строке... Ну это самый громоздкий метод, я не спорю...
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
08.11.2013, 23:11 14
Правильно. Пошагово я расписал. Дальше группируем: самый большой вес справа. Берём следующий самый большой. Он должен быть слева. Начинаем вокруг него выстраивать число и т.д. Последнее оставшееся число (если осталось) ставим справа от самого большого веса.
Ведь посмотри на запись, там X идёт через один символ. Это не случайно. Так будет всегда. Отвлечёмся от числа 90. Возьмём другой набор римских цифр: LCDXXXIVII. Что из этого можно записать? Запись то, однозначной должна быть? Значит имеем:
Запись числаОставшиеся числаАрабская запись
1DCDXXXIVII500
2CDLXXXIVII500 - 100
3LCDXXXIVII500 - (100 - 50)
4LCXDXXIVII500 - (100 - 50 + 10)
5XLCXDXIVII500 - (100 - 50 + 10) - 10
6VXLCXDXIII500 - (100 - 50 + 10) - (10 - 5)
7VXILCXDXII500 - (100 - 50 + 10) - (10 - 5 + 1)
8XVXILCXDII500 - (100 - 50 + 10) - (10 - 5 + 1) - 10
9IXVXILCXDI500 - (100 - 50 + 10) - (10 - 5 + 1) - (10 - 1)
10IXVXILCXDI 500 - (100 - 50 + 10) - (10 - 5 + 1) - (10 - 1) +1
Или я ошибаюсь?
Равно 426
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
09.11.2013, 11:12  [ТС] 15
Извините, Вы, наверное, меня неправильно поняли. Десятичное число, возможность составления которого мы проверяем, задаётся на вход вместе с множеством римских цифр. Покажу на примере, как лично я поняла решение задачи.
Пусть на вход задалась строка 'XVIII' и нужно проверить, можно ли, используя все и только все элементы данной строки, записать число "6". Начинаем перебирать все возможные варианты последовательностей с использованием всех элементов входной строки:
XVIII - десятичное 18 (определяем значение строковой последовательности по заданному в задаче алгоритму, так же определяем и в дальнейшем), не равно 6, продолжаем перебор
...
IVXIII - десятичное 9, не равно 6, продолжаем перебор
...
XIVII - десятичное 16, не равно 6, продолжаем перебор
...
IVIXI - десятичное 6, первый (возможно и последний) вариант записи заданного десятичного числа заданным набором знаков найден, выводим его.
Где троеточия, там, разумеется, были ещё какие-то варианты, которые не были равны 6 при переводе в десятичную систему, ну и я не говорю, что перебираться все возможные строки будут в таком порядке. Потому что вот это я как раз всё ещё и не понимаю, как грамотно, не потеряв ни одного варианта, организовать цикл, в котором бы перебирались все до единой возможные строки длиной n, содержащие в себе все n элементов, заданных с клавиатуры.
0
ViterAlex
6462 / 3633 / 1484
Регистрация: 11.02.2013
Сообщений: 7,991
Завершенные тесты: 3
09.11.2013, 19:04 16
Я всё правильно понял. Просто я ставлю задачу более общо: не подбирать сочетание, а определить его. Ведь сочетаний может быть n! Кстати, полученный тобой результат для 6, почти подтвердил мои выкладки: самый большой вес стоит справа. Но выкладки были не совсем верны: я их реализовал в программе и результат не всегда тот, что ожидается. Но я буду копать. Самому интересно
0
vindex
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 12
09.11.2013, 20:03  [ТС] 17
В общем готово. Заполняла ответ в 2 строки (левая и правая части записи числа), которые потом склеивала в ответе. Использовала счётчик, изначально равный 0, на всех заходах сравнивала его со входным десятичным числом, если счётчик >= введёного числа, то вычитала из счётчика вес текущей найденной максимальной цифры и писала саму цифру в левую строку, если счётчик на данный момент меньше входного числа, то вес текущей максимальной цифры к счётчику прибавляла, а цифру записывала в правую строку , единственное исключение - при первом заходе в цикл найдётся самая большая цифра, её я ставила в правую строку (ну чтобы при склейке эта цифра была посерёдке так сказать). При этом в конце каждого прохода из исходной строки удалялась только что обработанная цифра, цикл до тех пор, пока входная строка не станет пустой. Далее сравниваю счётчик с введённым изначально числом, если между ними можно ставить =, то склеиваю 2 строки и вывожу, если не равны, то вывожу "нельзя". Вроде правильно. Ваша методика сработала, спасибо. Даже для отрицательных вроде рябит.

Добавлено через 10 минут
Вот пример для CLLLLL и числа -150:
1) Счётчик=0 > -150, Счётчик = 0-100 (вес С) = -100, проход 1й, С пишем в правую подстроку выходной записи, во входной строке LLLLL, в правой C.
2) Счётчик -100>-150, Счётчик = -100-50=-150, L пишем в левую подстроку, во входной LLLL, в правой C, в левой L.
3) Счётчик -150=-150, Счётчик=-150-50=-200, L в левую подстроку, входная LLL, правая C, левая LL.
4) Счётчик -200<-150, Счётчик= -200+50=-150, L в правую подстроку, входная LL, правая CL, левая LL.
5) Счётчик -150=-150, Счётчик -150-50=-200, L в левую подстроку, входная L, правая CL, левая LLL.
6) Счётчик -200<-150, Счётчик -200+50=-150, L в правую подстроку, входная пустая, цикл завершается, правая CLL, левая LLL.
Сравниваем: -150=-150
Склеиваем: LLL-CLL, выводим LLLCLL.
0
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 542
03.03.2014, 07:57 18
В инете есть вариант алгоритма на паскале
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
RD: array [1..13] of string[2]=('I','IV','V','IX','X','XL','L','XC','C','CD','D','CM','M');
AN: array [1..13] of integer=(1,4,5,9,10,40,50,90,100,400,500,900,1000);
procedure RtoA(s:string);
var
  i, j, res: integer;
begin
  res:=0;i:=13; 
  for j:=1 to length(s) do
    s[j]:=UpCase(s[j]);
  j:=1; 
  while j<=length(s) do begin
    while (copy(s,j,length(RD[i]))<>RD[i])and(i>0) do
      i:=i-1;
    res:=res+AN[i]; 
    j:=j+length(RD[i]);
  end;
  if AToR(res)=s then writeln(res)
  else writeln(cnv('ошибка записи римского числа'));
end;
.
Не очень, так как вообще не фига не контролирует входную строку как на допустимые символы
так и на правильность последовательности допустимых.
Как известно (википедия) проги используют 2 формы записи - классическую и т.н. упрощенную
Пример
10-ичная959949919501999
Классич.XCVXCIXCDXCIXMCMLMIXIXIX
Упрощен.VCICXDIX, IDMLMMIM
Прога выше контроль правильности делает обратным преобразованием результата в строку римских - дубовый способ, да еще может подвиснуть.
Если на вход проги выше подать не то что недопустимые символы но даже а даже упрощенную форму записи римского числа то она даст i=0 что в паскале приводит к выходу за границу массива
Я чуть модифицировал код выше добавив обработку события i=0
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
procedure RtoA(s:string);
var
  i, j, res: integer;
begin
  res:=0;i:=13; 
  for j:=1 to length(s) do
    s[j]:=UpCase(s[j]);
  j:=1; 
  while j<=length(s) do begin
    while (copy(s,j,length(RD[i]))<>RD[i])and(i>0) do
      i:=i-1;
        if i=0 then
            begin writeln(cnv('недопустимый символ или последовательность')); exit; end;
    res:=res+AN[i]; 
    j:=j+length(RD[i]);
  end;
  if AToR(res)=s then writeln(res)
  else writeln(cnv('ошибка записи римского числа'));
end;
. Если хотите чтоб прога работала и с упрощенной записью надо видимо расширить массивы RD и AN
0
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 542
05.03.2014, 09:13 19
А как вы переведете интересно число XCXC ?
В одном источнике сказано что это 9090 (несмотря на ограничения 3999 в классической записи).
А вот например, онлайн калькулятор http://planetcalc.ru/378/
выдает 180 т.е. 90+90. Кто прав? Там что - переводят каждый символ и пару символов в число и затем складывают? Так римляне не поступали
0
05.03.2014, 09:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2014, 09:13

Элементы массива, являющиеся цифрами числа n, вывести на экран
Дано натуральное число n (n &lt;= 999999). Заполнить массив его цифрами,...

Перевести числа, написанные словами, в числа, написанные цифрами
В общем это код перевода чисел, написанных цифрами, в числа, написанные...

Даны два положительных целых числа А,В. Напечатать слово "ДА" или "НЕТ" в соответствии с тем, можно ли получить десятичную запись числа А путем вычерк
Даны два положительных целых числа А,В. Напечатать слово &quot;ДА&quot; или &quot;НЕТ&quot; в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru