Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки.
Пользователь
Расчет биномиальных коэффициентов на Си (С++) и Python
9 мин
58KПри решении задач комбинаторики часто возникает необходимость в расчете биномиальные коэффициентов. Бином Ньютона, т.е. разложение также использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: или использовать рекуррентную формулу: Из бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа. На данном примере хотелось показать, что даже при решении несложной задачи можно наступить на грабли.
+10
О сортировках (пузырьковой, быстрой, расческой...)
8 мин
54KRecovery Mode
Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.
-4
И снова о Юникоде (Unicode)
8 мин
20KКонечно, о юникоде (Unicode) в интернете море информации (см, например Юникод, некоторые фрагменты текста я взял оттуда), я ни в коей мере не претендую на полное и исчерпывающее описание. Это просто некоторая дополнительная «информация к размышлению».
+10
О кодировках и кодовых страницах
7 мин
40KВряд ли это сейчас сильно актуально, но может кому-то покажется интересным (или просто вспомнит былые годы).
Начну с небольшого экскурса в историю компьютера. Поскольку компьютер использовался для обработки информации, то он просто обязан представлять эту информацию в «человеческом» виде. Компьютер хранит информацию в виде чисел (байтов), а человек воспринимает символы (буквы, цифры, различные знаки). Значит, надо сделать сопоставление число <-> символ и задача будет решена. Сначала посчитаем, сколько символов нам надо (не забудем, что «мы» — американцы, использующие латинский алфавит). Нам надо 10 цифр + 26 заглавных букв английского алфавита + 26 строчных букв + математические знаки (хотя бы +-/*=><%) + знаки препинания (.,!?:;’” ) + различные скобки + служебные символы (_^%$@|) + 32 непечатных управляющих символов для работы с устройствами (в первую очередь, с телетайпом). В общем, 128 символов хватает «впритык» и этот стандартный набор символов «мы» назвали ASCII, т.е. «American Standard Code for Information Interchange»
Начну с небольшого экскурса в историю компьютера. Поскольку компьютер использовался для обработки информации, то он просто обязан представлять эту информацию в «человеческом» виде. Компьютер хранит информацию в виде чисел (байтов), а человек воспринимает символы (буквы, цифры, различные знаки). Значит, надо сделать сопоставление число <-> символ и задача будет решена. Сначала посчитаем, сколько символов нам надо (не забудем, что «мы» — американцы, использующие латинский алфавит). Нам надо 10 цифр + 26 заглавных букв английского алфавита + 26 строчных букв + математические знаки (хотя бы +-/*=><%) + знаки препинания (.,!?:;’” ) + различные скобки + служебные символы (_^%$@|) + 32 непечатных управляющих символов для работы с устройствами (в первую очередь, с телетайпом). В общем, 128 символов хватает «впритык» и этот стандартный набор символов «мы» назвали ASCII, т.е. «American Standard Code for Information Interchange»
+7
Информация
- В рейтинге
- Не участвует
- Зарегистрирован
- Активность