Monday, March 30, 2009

Algorithms: What are the differences between array and linked list?

Итак, в чем же разница между массивом и односвязным списком?

Space:

1. В случае массивов, для хранения 10 элементов нам потребуется 10 * sizeof(element) байт памяти.
2. А в случае со односвязным списком, нам понадобится 10 * (sizeof(element) + sizeof(pointer)) места.

Следовательно, нам понадобится больше места/памяти в случае списка (по сравнению с массивом).

Time:

Т. к. массив предоставляет возможнось доступа к элементу по индексу, то в случае массива время доступа к произвольному элементу будет O(1), в то время как поиск элемента в списке потребует O(n) времени.

НО:

1. Некоторые структуры данных удобней представлять в виде именно связных списков, а не массивов.
2. Удаление и добавление новых элементов проще производить в списках, чем в массивах (массивы не расширяемы).
3. В случае массивов нет фрагментации памяти (т.к. элементы массива следуют друг за другом в памяти), как это может быть со связным списком.

Algorithms: Find string combinations

Задача: найти все комбинации заданой строки.

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

Для начала в двух словах раскажу что такое комбинации в строке. Рассмотрим строку "abcd". В этой строке, например, две пары "ab" и "bc" являются комбинациями, в то время как "ab" и "ba" - нет.

Запишем теперь возможные комбинации для слова "abcd":

a b c d
ab bc cd  
abc bcd    
abcd bd    
abd      
ac      
acd      
ad      

В таблице выше представлены все возможные комбинации слова "abcd".

Итак, что мы можем получить из такого представления? А мы можем получить собственно сам алгоритм генерации комбинаций. Рассмотрим, к примеру, колонку "c" - как мы можем получить все комбинации для "c" - очень просто, берем "c", это будет одна комбинация, затем поочередно прибавляем значения со всех колонок справа. Получаем: "c" и "cd". Далее, расмотрим "b" - для "b" действует то же правило, берем "b", а затем к символу "b" прибавляем все значения из колонок справа... и так далее.

Следовательно, мы приходим к следующему рекурсивному алгоритму:

Для каждого символа во входящей строке, начиная со стартовой позиции и до конца
  Выбираем символ из входящей строки в результирующую
  Печатаем комбинацию
  Если текущий символ во входящей строке
    Переходим на следующий цикл рекурсии, начиная при этом с символа, следующим за текущим символом.

Приведу реализацию этого алгоритма на C# (и я думаю сразу "все станет на свои места"):

    1 /// <summary>

    2 /// Print string combinations.

    3 /// </summary>

    4 /// <param name="inputChars">Input string characters.</param>

    5 public static void PrintCombinations(char[] inputChars)

    6 {

    7     char[] outChars = new char[inputChars.Length];

    8     DoPrintCombinations(inputChars, outChars, 0, 0);

    9 }

   10 

   11 private static void DoPrintCombinations(char[] inputChars, char[] outChars, int level, int start)

   12 {

   13     for (int index = start; index < inputChars.Length; index++)

   14     {

   15         outChars[level] = inputChars[index];

   16         outChars.PrintArray();

   17         if (index < inputChars.Length - 1)

   18         {

   19             DoPrintCombinations(inputChars, outChars, level + 1, index + 1);

   20             outChars[level + 1] = '\0';

   21         }

   22     }

   23 }

Напомню, что PrintArray - это extension-метод, который мы ввели для облегчения вывода массивов на консоль.

 

Пример:

    1 public static void Main()

    2 {

    3     CommonAlgorithms.PrintCombinations("abcd".ToCharArray());

    4 }

 

Результатом работы этой програмки приведен ниже:

 

image

 

В следующий раз раскажу о поиске всех перестановок (хотя об этом надо было расказать сначала :))..

 

Happy coding...

Sunday, March 29, 2009

Крымские виды (панорама)


Posted by Picasa

Давненько это было. Снято еще "стареньким" Olympus 570 UZ (точно уже и не помню). Снял давно, и вот только сейчас дошли руки сделать панорамки.

Monday, March 23, 2009

Algorithms: Check whether two words are anagrams

Задача: необходимо проверить, являются ли два слова анаграммами.

Для начала давайте вспомним (или узнаем) что такое анаграммы. Итак:

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

Итак, есть много (и довольно разных) вариантов решения этой задачи. Раскажу об одном из них. Итак, для начал предположим что у нас слова, которые мы будем сравнивать - находятся в кодировке ASCII. Далее, оба слова необходимо перевести в нижний регистр (для этого можно использовать String.ToLower() ну или придумать свою замену, если посчитаете, что ToLower() может отнимать много времени).

После того как оба слова переведены, можно для первого слова построить "гистограмму" вхождения буквы в слово. Например, у нас есть слово "streaming", следовательно гистограмма для это слова будет выглядеть как

s - 1
t - 1
r - 1
e - 1
a - 1
m - 1
i - 1
n - 1
g - 1

Далее, анализируя второе слово, мы можем уменьшать значения в гистограмме. И на последнем шаге необходимо пробежатся по всем значениям в "гистограмме" и проверить все ли значения равны 0. Если нет - то сравниваемые два слова не анаграммы.

Приведу пример реализации этого алгоритма на C#:

    1 /// <summary>

    2 /// Check whether two words are anagrams.

    3 /// </summary>

    4 /// <param name="value1">First word.</param>

    5 /// <param name="value2">Second word.</param>

    6 /// <returns>True if two specified word are anagrams, otherwise false.</returns>

    7 public static Boolean IsAnagram(String value1, String value2)

    8 {

    9     if (String.IsNullOrEmpty(value1) || String.IsNullOrEmpty(value2) ||

   10         value1.Length != value2.Length)

   11     {

   12         return false;

   13     }

   14 

   15     // convert strings to lowercase.

   16     value1 = value1.ToLower();

   17     value2 = value2.ToLower();

   18 

   19     int[] histogram = new int[256];

   20 

   21     for (int index = 0; index < value1.Length; index++)

   22     {

   23         histogram[value1[index] - 'a']++;

   24     }

   25 

   26     for (int index = 0; index < value2.Length; index++)

   27     {

   28         int charIndex = value2[index] - 'a';

   29         if (histogram[charIndex] == 0)

   30         {

   31             return false;

   32         }

   33 

   34         histogram[charIndex]--;

   35     }

   36 

   37     return true;

   38 }

 

Сложность - O(n).

 

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

 

Happy coding...

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...

Sunday, March 22, 2009

Високосный год и JavaScript

Иногда возникает необходимость определить, является ли введенный/выбранный (например, из списка) пользователем год високосным.
В C# все просто:
bool isLeap = DateTime.IsLeapYear(1996);

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

function IsLeapYear(year) {
    if(year%4 == 0) {
        if(year%100 == 0) {
            if(year%400 == 0) {
                return true;
            }
            else
                return false;
        }
        else
            return true;
    }
    return false;
}

Анализируя функцию, возникает вопрос: а не проще ли сделать year%4 == 0 и получить високосный год. Ответ: нет. Алгоритм вычисления высокосного года немного сложнее (поблагодарим Папу Георгия ХIII). Год считается високосным только в том случае если он делится на 4 без остатка (это мы знаем со школы), но при этом не делится на 100 без остатка, или, если делится на 100, должен делится и на 400 без остатка.

Happy coding...

Проблема при установке SQL Server 2005 на машину с AMD Phenom 8450 Triple-Core

Хочу немного рассказать о проблеме, с которой я столкнулся при установке SQL Server 2005 на компьютер с AMD Phenom 8450 Triple-Core. Выяснения в чем дело заняли у меня почти целый день (к сожалению, у меня не было интернета под рукой, поэтому «погуглить» я не мог).

Итак, при установке сервиса SQL Server инсталлер пытался запускать службу, которая без видимых причин падала со следующей ошибкой:

An unhandled win32 exception occurred in sqlservr.exe [1456]. Just-In-Time debugging this exception failed with the following error: No such interface supported

Check the documentation index for 'Just-in-time debugging, errors' for more information.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

После долгих поисков (хорошо, что установка шла на новую систему, и я успел поэкспериментировать и с Windows XP, как с сервиспаками так и без, и с Windows 2003), наконец-то я выяснил J, что проблема (по части) «в железе».

Итак, способ лечения:

  1. С командной строки запустить msconfig 
    1
  2. Перейти на закладку BOOT.INI и нажать там кнопку Advanced Options… 
    2
  3. В появившемся окне отметить опцию /NUMPROC= и выбрать значение кратное 2-м: 
    3
  4. Сохраняем изменения. Перезагружаем компьютер.
  5. Устанавливаем SQL Server 2005 и Service Pack 2 (обязательно!).
  6. После установки Service Pack 2 необходимо проделать пункты 1-3 еще раз, но при этом в окне BOOT.INI Advanced Options снять флажок /NUMPROC= (вернув при этом 3 ядра «в строй»).

Hope this helps…

Algorithms: Convert string to integer

Задача: необходимо преобразовать строку в число.

Для начала предположим, что строка у нас находится в кодировке ASCII. Наиболее очевидным и простым решением является проход строки справа налево.

Давайте на примере рассмотрим решение задачи. Итак, у нас есть строка "437". Двигаясь слева направо, мы на первом шаге берем символ "4". Как мы можем перевести "4" в соответствующее число: 4? Так как у нас строка в ASCII кодировке, мы можем взять '4' - у которого числовое представление 52 и вычесть 48, т.е. числовое представление '0'.

Примечание: более подробную информацию по кодировке ASCII можно найти здесь: American Standard Code for Information Interchange (ASCII).

Далее, получив второй символ "3" нам необходимо умножить предыдущее число 4 на 10 и найти числовое представление символа "3". После этого результат складываем и запоминаем: 4 * 10 + 3. На следующем шаге получим (4 * 10 + 3) * 10 + 7.

Этот алгорим можно представить как:

Start number at 0
If the first character is '-'
    Set the negative flag
    Start scanning with the next character
For each character in the string
    Multiply number by 10
    Add (digit character - '0') to number
Return number

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

    1 /// <summary>

    2 /// Converts string to integer.

    3 /// </summary>

    4 /// <param name="input">Input string.</param>

    5 /// <returns>Resulting integer value.</returns>

    6 public static Int32 StringToInt32(String input)

    7 {

    8     // Validate input parameter.

    9     if (String.IsNullOrEmpty(input))

   10     {

   11         throw new ArgumentNullException("input");

   12     }

   13 

   14     Int32 position = 0;

   15     Boolean isNegative = false;

   16     Int32 result = 0;

   17 

   18     if (input.Length == 1 && !char.IsDigit(input[position]))

   19     {

   20         throw new InvalidOperationException();

   21     }

   22 

   23     // Validate whether input string starts with "-".

   24     if (input[position] == '-')

   25     {

   26         isNegative = true;

   27         position = 1;

   28     }

   29 

   30     while (position < input.Length)

   31     {

   32         if (!char.IsDigit(input[position]))

   33         {

   34             throw new InvalidOperationException();

   35         }

   36 

   37         result *= 10;

   38         result += (input[position] - '0');

   39 

   40         position++;

   41     }

   42 

   43     if (isNegative)

   44     {

   45         result *= -1;

   46     }

   47 

   48     return result;

   49 }

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

PS: В следующий раз я покажу как перевести число из римской системы счисления в арабскую: XXI -> 21.

Happy coding...

Algorithms: Convert Integer to string

Задача: перевести число в строку.

Возможно несколько вариантов рещения этой задачи.
Первый вариант - идем слева направо. Например, у нас есть число -123. Во-первых, мы во всех вариантах должны сначал проверить является ли число отрицательным, и перевести его в положительное (при этом запомнив, что изначально оно отрицательное). Далее, как мы можем получить число "1" из 123? Следующим образом:

123 / 100 = 1; 123 - 1 * 100 = 23 - первое число
23 / 10 = 2; 23 - 2 * 10 = 3 - второе число
3 / 1 = 3; 3 - 3 * 1 = 0 - третье число

Второй вариант предполагает проход числа справа налево. При этом как мы можем получить самое последнее число? Получив остаток от деления на 10: 123 / 10 = 3;

Алгоритм решения этой задачи приведен ниже:

If number less than zero
  Multiply number by -1
  Set negative flag
While number not equal to 0
  Add '0' to number % 10 and write this to temp buffer
  Integer divide number by 10
If negative flag is set
  Write '-' into next position in temp buffer
Write characters in temp buffer into output string in reverse order

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

    1 /// <summary>

    2 /// Converts integer value to int string representation.

    3 /// </summary>

    4 /// <param name="value">Target integer value.</param>

    5 /// <returns>String representation of specified value.</returns>

    6 public static String Int32ToString(Int32 value)

    7 {

    8     char[] output = new char[10];

    9     bool isNegative = false;

   10     int i = 0;

   11 

   12     // First of all, check whether value is negative.

   13     if (value < 0)

   14     {

   15         isNegative = true;

   16         value *= -1;

   17     }

   18 

   19     do

   20     {

   21         // Find current number and shift to the corresponding char.

   22         output[i++] = (char)((value % 10) + '0');

   23 

   24         // Divide by 10, so on the next iteration we still

   25         // can obtain valid last number.

   26         value /= 10;

   27     }

   28     while (value > 0);

   29 

   30     // Add a minus sign "-" if isNegative flag is set.

   31     if (isNegative)

   32     {

   33         output[i] = '-';

   34     }

   35 

   36     // Construct the output string.

   37     string result = string.Empty;

   38     int position = output.Length - 1;

   39     while (position >= 0)

   40     {

   41         if (output[position] != '\0')

   42         {

   43             result += output[position];

   44         }

   45         position--;

   46     }

   47 

   48     return result;

   49 }

В следующий раз я раскажу как сделать обратное - из строки число.

Happy coding...

Saturday, March 21, 2009

Algorithms: Distinct an array

Внимание 
Код приведенный в этой заметке написан на C#.

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

Рассмотрим простой пример. Возмем массив в котором есть 2 повторяющихся числа: {1, 2, 3, 3, 4, 5, 5, 5, 6}. В данном массиве числа 3 и 5 повторяются несколько раз. В результате необходимо вернуть массив: {1, 2, 3, 4, 5, 6, 0, 0, 0}.

Приведу возможное решение задачи (коментарии по коду):

    1 /// <summary>

    2 /// Task: distinct an array.

    3 /// Requirements: array of integers, sorted in ascending order.

    4 /// Use the same array object and return its distinct value.

    5 /// Distinct values should come first, and the remaining

    6 /// elements must be filled with zeros.

    7 /// For instance:

    8 /// {1, 2, 2, 3, 4, 4, 5 } => {1, 2, 3, 4, 5, 0, 0}.

    9 ///

   10 /// Complexity: O(n).

   11 /// </summary>

   12 /// <param name="input">Target array.</param>

   13 /// <returns>Distinct array.</returns>

   14 public static int[] DistinctArray(int[] input)

   15 {

   16     // First of all, we need to check the input array.

   17     if (input == null || input.Length == 0)

   18     {

   19         throw new ArgumentNullException("input");

   20     }

   21 

   22     int position = 0;

   23     for (int index = 1; index < input.Length; index++)

   24     {

   25         if (input[index] != input[position])

   26         {

   27             input[++position] = input[index];

   28         }

   29     }

   30 

   31     for (int index = position + 1; index < input.Length; index++)

   32     {

   33         input[index] = 0;

   34     }

   35 

   36     return input;

   37 }

Такое решение имеет сложность O(n).

И в заключение - пример использования:

    1 int[] inputArray = { 1, 2, 3, 3, 4, 5, 5, 5, 6 };

    2 inputArray.PrintArray();

    3 var outputArray = ArrayUtilities.DistinctArray(inputArray);

    4 outputArray.PrintArray();

Запускаем, и....

image

PS:

наверное у кого-то может возникнуть вопрос: "как так получилось - inputArray.PrintArray()?" - так вот это всего лишь вспомогательный extension-метод. Приведу его кот потому что он может нам (мне и тебе ув. %username%) еще пригодится.

    1 /// <summary>

    2 /// Prints an array.

    3 /// </summary>

    4 /// <typeparam name="T">Array type.</typeparam>

    5 /// <param name="input">Input array instance.</param>

    6 public static void PrintArray<T>(this T[] input)

    7 {

    8     if (input == null)

    9     {

   10         Console.WriteLine("Input array is null.");

   11         return;

   12     }

   13 

   14     Console.Write(typeof(T).Name + "[" + input.Length + "] = {");

   15     for (var index = 0; index < input.Length; index++)

   16     {

   17         Console.Write(input[index]);

   18         if (index < input.Length - 1)

   19         {

   20             Console.Write(", ");

   21         }

   22     }

   23     Console.WriteLine("}");

   24 }

В следующий раз я раскажу как перевести число в строку :) (без использования int.ToString()).

Happy coding...