Как понять насколько близки две строки? Как поисковая система все равно находит то, что надо, даже если вы совершили пару опечаток в запросе? В этом вопросе нам поможет расстояние по Левенштейну или редакционное расстояние. Почему редакционное? Потому что мы считаем, сколько действий по редактированию одной строки нужно совершить, чтобы получить другую строку. Действия бывают следующими:…
Метка: алгоритмы
Пишем Brainfuck на Python
Есть мнение, что каждый программист должен написать в жизни хотя бы один язык программирования, либо реализовать уже существующий, но своими руками. В качестве примера мы начнем с самого простого и создадим Brainfuck. Согласно Вики: Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем.Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос…
Короткое замыкание
Поговорим о логических операциях. Допустим у нас есть цепочка из or: Чтобы print сработал, нужно, чтобы хотя бы один из трех вызовов давал бы True (или приводился к True). Что если x() сразу вернет True? Тогда, очевидно, все выражение будет равняться True в любом случае и независимо от того, что будет в y() и z().…
Сортировка пузырьком
Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4]. Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы…
Куча и очередь с приоритетом
Очередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).