• Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)

    • Tutorial
    Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки.
    Читать дальше →
  • Расчет биномиальных коэффициентов на Си (С++) и Python

      При решении задач комбинаторики часто возникает необходимость в расчете биномиальные коэффициентов. Бином Ньютона, т.е. разложение image также использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: image или использовать рекуррентную формулу:image Из бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа. На данном примере хотелось показать, что даже при решении несложной задачи можно наступить на грабли.
      Читать дальше →
    • О сортировках (пузырьковой, быстрой, расческой...)

      Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.

      Читать дальше →
    • И снова о Юникоде (Unicode)

        Конечно, о юникоде (Unicode) в интернете море информации (см, например Юникод, некоторые фрагменты текста я взял оттуда), я ни в коей мере не претендую на полное и исчерпывающее описание. Это просто некоторая дополнительная «информация к размышлению».
        Читать дальше →
      • О кодировках и кодовых страницах

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

        Начну с небольшого экскурса в историю компьютера. Поскольку компьютер использовался для обработки информации, то он просто обязан представлять эту информацию в «человеческом» виде. Компьютер хранит информацию в виде чисел (байтов), а человек воспринимает символы (буквы, цифры, различные знаки). Значит, надо сделать сопоставление число <-> символ и задача будет решена. Сначала посчитаем, сколько символов нам надо (не забудем, что «мы» — американцы, использующие латинский алфавит). Нам надо 10 цифр + 26 заглавных букв английского алфавита + 26 строчных букв + математические знаки (хотя бы +-/*=><%) + знаки препинания (.,!?:;’” ) + различные скобки + служебные символы (_^%$@|) + 32 непечатных управляющих символов для работы с устройствами (в первую очередь, с телетайпом). В общем, 128 символов хватает «впритык» и этот стандартный набор символов «мы» назвали ASCII, т.е. «American Standard Code for Information Interchange»
        Читать дальше →