Monday, March 23, 2009

Algorithms: Romanian numbers

Задача: необходимо преобразовать число, представленное в римской системе счисления в число в десятичной системе счисления (ну вдруг кто не знает или забыл как это "римские цифры" - то тогда здесь).

Алгоритм решения этой задачи довольно простой. Итак, необходимо двигатся с конца строки, увеличивая или уменьшая результат.

Итак, для начала построим "карту" соответствия римских и арабских чисел:

C 100
D 500
I 1
L 50
M 1000
V 5
X 10

А теперь, на примере можно рассмотреть собственно сам алгоритм. Возьмем к примеру число XIV (т.е 14). И, как я уже упоминал, необходимо двигатся в конца строки. Возьмем первый символ - "V". Ему, в "карте" соответствует число 5. Запоминаем это число как текущий результат и сдвигаемся дальше влево на один символ. Далее у нас символ "I" - ему соответствует 1 в "карте". Необходимо вычесть 1 с уже имеющегося результата - 5. Из этого следует, что если текущее значение меньше предыдущего, то необходимо от результата отнять текущее значение, иначе - прибавить. Итак, 5 - 1 получаем 4 и двигаемся дальше. Дальше у нас "X" - и соответствующее ему число 10. Так как на предыдущем шаге у нас была 1, которая меньше 10, то полученную 10-ку надо прибавить к результату. В итоге получем - 14.

И реализация на C#:

    1 /// <summary>

    2 /// Convert Romanian number to Arabic.

    3 /// </summary>

    4 /// <param name="value">Value to be converted.</param>

    5 /// <returns>Converted value if successful, otherwise 0.</returns>

    6 public static Int32 RomanToInt32(String value)

    7 {

    8     // Validate input parameters.

    9     if (String.IsNullOrEmpty(value))

   10     {

   11         throw new ArgumentNullException("value");

   12     }

   13 

   14     // Update string.

   15     value = value.Trim().ToUpper();

   16 

   17     var romanDigitDictionary = new Dictionary<String, Int32>

   18     {

   19         {"C", 100}, {"D", 500}, {"I", 1}, {"L", 50}, {"M", 1000}, {"V", 5}, {"X", 10}

   20     };

   21 

   22     // Validate string.

   23     for (Int32 charIndex = 0; charIndex < value.Length; charIndex++)

   24     {

   25         if (!romanDigitDictionary.ContainsKey(value[charIndex].ToString()))

   26         {

   27             throw new InvalidOperationException("String contains invalid characters");

   28         }

   29     }

   30 

   31     // Start conversion.

   32     Int32 result = 0;

   33     Int32 lastValue = 0;

   34 

   35     for (Int32 charIndex = value.Length - 1; charIndex >= 0; charIndex--)

   36     {

   37         Int32 currentValue;

   38         if (!romanDigitDictionary.TryGetValue(

   39             value[charIndex].ToString(),

   40             out currentValue))

   41         {

   42             throw new InvalidOperationException();

   43         }

   44 

   45         if (currentValue < lastValue)

   46         {

   47             result -= currentValue;

   48         }

   49         else

   50         {

   51             result += currentValue;

   52             lastValue = currentValue;

   53         }

   54     }

   55 

   56     return result;

   57 }

 

Сложность такого алгоритма - O(n).

 

PS: В следующий раз я  раскажу как проверить являются ли два слова анаграммами.

 

Happy coding...

No comments :

Post a Comment