Количество диагоналей в n-стороннем выпуклом многоугольнике

Чтобы найти количество диагоналей в n-стороннем выпуклом многоугольнике, можно воспользоваться следующей формулой:

Количество диагоналей = (n * (n - 3)) / 2

Эта формула выведена из того факта, что в выпуклом многоугольнике с n сторонами каждая вершина может быть соединена с любой другой вершиной диагональю, за исключением самой себя, соседних с ней вершин и двух соседних с ними вершин. В результате из каждой вершины можно провести n — 3 диагонали. Однако вы должны разделить это на 2, чтобы не считать каждую диагональ дважды (поскольку, например, соединение вершины A с вершиной B — это то же самое, что соединение вершины B с вершиной A).

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

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

Алгоритм:
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, и мы успешно поменяли местами значения двух переменных.

⁉️Машинное обучение кажется чем-то сложным и недосягаемым? Всё проще, чем вы думаете!

Первый шаг — разобраться, как устроен ML-процесс и научиться работать в Jupyter Notebook — инструменте, с которого начинают все специалисты в Data Science.

На открытом уроке вы шаг за шагом поймёте, как строится путь от данных до модели. Научитесь запускать эксперименты в Jupyter Notebook и Google Colab, работать с виртуальными окружениями и не бояться “сломать” систему. Всё — в формате простых и наглядных примеров.

После урока вы сможете уверенно начать свой первый ML-проект и поймёте, какие инструменты нужны, чтобы перейти от теории к практике.

➡️ 13 ноября в 20:00 МСК. Открытый вебинар проходит в преддверии старта курса «Machine Learning. Basic». Регистрируйтесь и сделайте первый шаг в машинное обучение без страха и путаницы: https://otus.pw/jfhE/

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

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

Учитывая число 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

AI-Ops для PostgreSQL: нейросети против узких мест и деградации производительности

Как заставить PostgreSQL не только работать быстрее, но и самостоятельно объяснять, где и почему всё тормозит? На открытом вебинаре курса OTUS PostgreSQL. Advanced Дмитрий Золотов покажет, как применять AI и LLM-модели для анализа производительности, поиска узких мест и предотвращения деградации ещё до того, как она станет проблемой.

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

AI-Ops для PostgreSQL: нейросети против узких мест и деградации производительности
— применение AIOps-подхода для анализа метрик, логов и планов выполнения запросов
— автоматическая интерпретация EXPLAIN ANALYZE и рекомендации по оптимизации
— использование ML-моделей для прогнозирования деградации и роста нагрузки
— примеры внедрения AI-мониторинга в продакшн

Вебинар будет полезен DBA, DevOps-инженерам, архитекторам высоких нагрузок и разработчикам, которые ищут новые способы автоматизации и анализа систем.

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

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

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

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

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