Задача о ходе коня

Головоломка, в которой требуется найти маршрут хода коня на шахматной доске, проходящий через все клетки только один раз.

Алгоритм:
1. Создаем шахматную доску n x n, где n - размерность доски.
2. Инициализируем текущую позицию коня на доске.
3. Помечаем текущую позицию как посещенную.
4. Проверяем, есть ли еще непосещенные клетки на доске:
- Если все клетки посещены, то задача решена, и мы можем вернуть найденный маршрут.
- Если не все клетки посещены, переходим к следующему шагу.
5. Находим все возможные ходы коня из текущей позиции:
- Проверяем, что следующий ход находится в пределах доски и не был посещен.
6. Для каждого возможного хода коня:
- Передвигаем коня на следующий ход.
- Рекурсивно вызываем алгоритм для новой позиции коня.
- Если рекурсивный вызов вернул true (маршрут найден), то возвращаем true.
- Если рекурсивный вызов вернул false, отменяем текущий ход и ищем другие возможные ходы.

Сложность: O(8^n), где n - размерность доски.

Задача о сумме подмножеств

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

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

Сложность: O(n^2)

Поменять местами два числа без использования временной переменной (Используя сложение и вычитание)

Пусть у нас есть два числа a и b, и мы хотим поменять их местами.

Шаги для обмена местами:

Присвоим переменной a новое значение, которое будет суммой a и b.
Вычтем из переменной b исходное значение переменной a (которое мы присвоили в шаге 1).
Присвоим переменной a новое значение, которое будет разностью между новым значением a и исходным значением b.
Теперь переменная a содержит исходное значение b, а переменная b содержит исходное значение a, и мы успешно поменяли местами значения двух переменных.

Поменять местами два числа без использования временной переменной.
(Используя умножения и деления)

Пусть у нас есть два числа a и b, и мы хотим поменять их местами.

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

Поменять местами биты в заданном числе

Учитывая число X и две позиции (справа) в двоичном представлении X, можно поменять местами n бит в данных двух позициях. Кроме того, предусмотрим, что два набора битов не перекрываются.

Алгоритм:
1) Переместить все биты первого набора в крайнюю правую часть.
set1 = (x >> p1) & ((1U << n) - 1)
Здесь выражение (1U << n) - 1 дает число, которое содержит последние n битов, а остальные биты равны 0. Проделываем операцию & с этим выражением, чтобы биты, отличные от последнего n бит стали 0.
2) Переместить все биты второго набора в крайнюю правую сторону.
set2 = (x >> p2) & ((1U << n) - 1)
3) XOR двух наборов битов
xor = (set1 ^ set2)
4) Вернуть биты xor в исходное положение.
xor = (xor << p1) | (xor << p2)
5) Выполнить XOR xor с исходным номером.
result = x ^ xor

Самый быстрый способ поменять два числа местами

Побитовый оператор XOR можно использовать для замены двух переменных. Операция XOR двух чисел x и y возвращает число, все биты которого равны 1, если биты x и y различаются.

Например, XOR для 10 (в двоичном формате 1010) и 5 (в двоичном формате 0101) — это 1111, а XOR для 7 (0111) и 5 (0101) — это (0010).

Проверка четности. Простой способ

Четность числа — это свойство, которое определяет, четное или нечетное количество установленных битов (битов, равных 1) в числе. Если количество установленных битов четное, то четность равна 0 (false), если нечетное — 1 (true).

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

Проверка четности с помощью таблицы поиска. Метод с побитовым сдвигом

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

Метод с побитовым сдвигом заключается в уменьшении количества битов до одного байта, для которого затем можно использовать таблицу поиска. Он уменьшает 32-битное число до одного байта с помощью побитовых операций XOR.

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

PostgreSQL и DevOps: управление базой данных через CI/CD и Kubernetes

Как автоматизировать развёртывание, обслуживание и мониторинг PostgreSQL в продакшн-среде? На открытом вебинаре курса OTUS PostgreSQL. Advanced Антон Герасименко покажет, как объединить DevOps-практики и PostgreSQL 17, чтобы упростить работу с базой данных и повысить её отказоустойчивость.

→ 8 декабря, 18:00

PostgreSQL и DevOps — управляем базой данных через CI/CD и Kubernetes
— создание Docker-контейнера для PostgreSQL и его правильная настройка
— использование Kubernetes-операторов для автоматического развертывания
— мониторинг и алертинг через Prometheus и Grafana
— настройка репликации и standby-реплик в PostgreSQL 17
— интеграция миграций и бэкапов в CI/CD-процессы

Вебинар будет полезен DevOps-инженерам, администраторам баз данных и разработчикам, которые хотят упростить управление PostgreSQL и сделать инфраструктуру более гибкой и надёжной.

→ Зарегистрируйтесь: https://otus.pw/Wm78h/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Проверка четности с помощью таблицы поиска. Метод с указателем

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

Метод с указателем заключается в использовании указателя на байты числа и вычисление четности для XOR всех четырех байтов.

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

Проверка четности 32-битного числа с использованием умножения

Метод вычисления четности числа с использованием умножения позволяет эффективно вычислять четность 32-битных чисел с помощью всего восьми операций.

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.

Прикладная задача на структуры данных из продакшена Яндекс Еды.

Дано: ~500k ресторанов и ~3M зон доставки в виде многоугольников. Нужно по координате пользователя за ~50 мс найти все рестораны, которые реально могут привезти заказ, причём зоны постоянно меняются.

В статье ребята разбирают, почему для геоиндекса не подошли Geohash и H3, и как в итоге пришли к R-дереву с логарифмическим поиском и отдельными индексами для ресторанов, ритейла и самовывоза. Есть схемы вставки, поиска и оценка сложности.

👉 Ссылка на разбор

Проверка четности 64-битного числа с использованием умножения

Метод вычисления четности числа с использованием умножения позволяет эффективно вычислять четность 64-битных чисел с помощью всего восьми операций.

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.

Вычисление деления по модулю для степени двойки без оператора деления

Вычисление остатка от деления числа на степень двойки можно выполнить без использования оператора деления. Это делается с помощью побитового И (&) с маской, представляющей степень двойки минус один.

Пример использования:
Если n = 29 и s = 3, то делитель d = 8:
- В двоичной системе n=11101
- Маска d−1=7 или 0111
- m = 11101 & 0111 = 0101 (5 в десятичной системе)
Таким образом, 29 % 8 = 5.

Как восстановить базу PostgreSQL на конкретный момент времени

Можно ли вернуть базу данных к жизни после сбоя или случайного удаления данных? На открытом вебинаре курса OTUS PostgreSQL. Advanced Виктор Коробков покажет, как работает восстановление PostgreSQL до конкретного момента времени (Point-in-Time Recovery, PITR) и как правильно настраивать систему бэкапов, чтобы не потерять ни байта данных.

→ 23 декабря, 20:00

Как восстановить базу PostgreSQL на конкретный момент времени
— роль WAL-журналов и как их использовать для архивации
— настройка файлового резервного копирования PostgreSQL
— пошаговое восстановление базы данных до нужного времени
— принципы PITR и применение в облачных инфраструктурах
— типичные ошибки при восстановлении и способы их избежать

Вебинар будет полезен администраторам баз данных, DevOps- и Cloud-инженерам, а также всем, кто хочет уверенно управлять бэкапами и защитой данных PostgreSQL.

→ Зарегистрируйтесь: https://otus.pw/xe6kk/

Реклама. ООО «Отус онлайн‑образование», ОГРН 1177746618576

Вычисление деления по модулю для числа вида (1 << s) - 1 без оператора деления

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

Пример использования:
Если n = 29 и s = 3:
- Делитель d = 7.
- В цикле вычисляются промежуточные значения m, пока n не станет меньше или равно d.
- Результат m = 29 % 7 = 1.

👨‍💻Задачи точного покрытия — фундамент для многих алгоритмических подходов. Но пока теория лежит на полке, она мало что меняет в вашем инженерном мышлении

На открытом уроке мы разберем Dancing Links через практику: соберем пентамино на столе, представим фигуры в виде строк матрицы и разберемся, как работает поиск с возвратом. Когда алгоритм становится наглядным, вы начинаете понимать, что на самом деле происходит внутри.

Если вы хотите развивать алгоритмическое мышление, системно улучшать свои решения и уверенно чувствовать себя в задачах уровня middle+, такие разборы — обязательная часть роста.

📆 Встречаемся 22 декабря в 20:00 МСК в преддверие старта курса «Алгоритмы и структуры данных», регистрация открыта: https://otus.pw/eq4Y/?erid=2VtzqvhDroC

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Подсчет количества замыкающих нулевых битов справа с использованием деления по модулю и таблицы поиска

Этот метод позволяет быстро найти количество замыкающих нулевых битов в 32-битном числе, используя деление по модулю и таблицу поиска. Метод основан на уникальном соответствии значений остатка от деления на 37 позициям битов.

Преимущества метода
- Эффективность: Метод требует всего 4 операции, что делает его быстрым.
- Компактность: Использование небольшой таблицы позволяет значительно ускорить вычисления по сравнению с линейным методом.

Недостатки метода
- Ограниченность: Метод предназначен для 32-битных чисел и требует адаптации для чисел другой разрядности.

Произведения всех элементов массива, кроме текущего

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет массив, где i-ый элемент является произведением всех элементов nums, кроме nums[i] (каждое произведение гарантированно умещается в 32-битное целое число).

Для решения задачи без использования операции деления и за O(n) времени, можно использовать метод предварительного вычисления произведений. Идея заключается в том, чтобы использовать два прохода по массиву: один для вычисления произведений слева от текущего элемента и другой для вычисления произведений справа от текущего элемента.

Пример:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]