Задача о дробном рюкзаке

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

Алгоритм:
1. Рассчитываем отношение стоимости к весу для каждого предмета.
2. Сортируем предметы по убыванию этого отношения.
3. Идем по отсортированному списку предметов и добавляем их в рюкзак до тех пор, пока рюкзак не станет полным или пока не закончатся предметы.
4. Если последний предмет не помещается полностью в рюкзак, добавляем его частично, пропорционально оставшемуся месту.
5. Возвращаем суммарную стоимость предметов в рюкзаке.

Сложность: O(n log n) времени, где n - количество предметов.

Центрированный тип обхода

Центрированный тип обхода является одним из трех базовых типов обхода бинарного дерева. В центрированном типе обхода сначала обрабатывается левое поддерево узла, затем сам узел и, наконец, правое поддерево.

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Прямой тип обхода

Прямой тип обхода является одним из трех базовых типов обхода бинарного дерева. Выполняет обработку узлов в следующем порядке: сначала сам узел, затем его левое поддерево и, наконец, правое поддерево.

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обратный тип обхода

Обратный тип обхода является одним из трех базовых типов обхода бинарного дерева. Выполняет обработку узлов в следующем порядке: сначала левое поддерево, затем правое поддерево и, наконец, сам узел.

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обход по порядку уровней бинарного дерева

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

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

Сложность: O(n), где n - количество узлов в дереве. В худшем случае каждый узел будет посещён один раз.

Обход границы на бинарном дереве

Метод обхода бинарного дерева, который проходит по границе дерева в определенном порядке.

Он включает следующие этапы:
1. Обход левой границы с вершины до левого листа, включая вершину.
2. Обход всех левых листьев сверху вниз.
3. Обход правой границы снизу вверх, исключая правый лист.
4. Обход всех правых листьев снизу вверх.

Сложность: O(n), где n - количество узлов в дереве. В худшем случае каждый узел будет посещен один раз.

Диагональный обход бинарного дерева

Метод обхода, который выполняется по диагоналям (возрастающей) от верхнего левого узла до нижнего правого узла.

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

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

Метод скользящего окна

алгоритмический подход, который применяется для решения задач, связанных с обработкой последовательных данных. Он основывается на применении фиксированного окна переменной ширины, которое "скользит" по последовательности данных, выполняя определенные операции на каждом шаге.

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

Сложность: O(n), где n - общее количество элементов в последовательности данных.

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

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

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

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

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

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

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

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

Раскраска графов

Алгоритм присвоения цветов вершинам графа таким образом, чтобы каждая пара смежных вершин имела разные цвета.

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

Сложность: O(n^2), где n - количество вершин в графе.

Гамильтонов цикл

Гамильтонов цикл — это цикл в графе, который посещает каждый узел ровно один раз и возвращается в начальный узел.

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

Сложность: O(N!), где N — количество вершин.

Подсчет инверсий

Счетчик инверсий для массива указывает, насколько далеко (или близко) находится массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0, но если массив отсортирован в обратном порядке, счетчик инверсий будет максимальным.

Алгоритм:
1. Создайте функцию merge, которая подсчитывает количество инверсий при слиянии двух половин массива.
⁃ Создайте два индекса i и j, i — индекс первой половины, а j — индекс второй половины.
⁃ Если a[i] больше, чем a[j], то происходят инверсии (mid – i), поскольку левый и правый подмассивы отсортированы, поэтому все оставшиеся элементы в левом подмассиве (a[i+1], a[i +2] … a[mid]) будет больше, чем a[j].
2. Создайте рекурсивную функцию, чтобы разделить массив пополам и найти ответ, суммируя количество инверсий в первой половине, количество инверсий во второй половине и количество инверсий путем слияния двух.

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

Ближайшая пара точек с использованием алгоритма «Разделяй и властвуй»

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

Алгоритм:
1. Найдите среднюю точку, которая равна P[n/2].
2. Разделите массив на две половины: от P[0] до P[n/2] и от P[n/2+1] до P[n-1].
3. Рекурсивно находим минимальные расстояния в обеих половинах, получая dl и dr.
4. Пусть d будет минимумом dl и dr.
5. Создайте массив «полосы», содержащий точки ближе, чем d к средней вертикальной линии, и отсортируйте его по координатам y.
6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.

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

Проверить, находится ли данная точка внутри или снаружи многоугольника?

Алгоритм предполагает подсчет количества раз, когда луч, идущий из точки, пересекает края многоугольника. Если количество пересечений нечетное, точка находится внутри многоугольника; если оно четное, то точка находится снаружи.

Сложность: O(N)

Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?

Алгоритм:
1. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.
2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.
3. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении по часовой стрелке. Сохраните их в векторе.
4. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении против часовой стрелки. Сохраните эти точки в векторе.
5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».
6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.

Сложность: O(N * log(N))

Выпуклая оболочка с использованием алгоритма Грэхема

Метод поиска выпуклой оболочки набора точек в двумерном пространстве. Выпуклая оболочка — это наименьший выпуклый многоугольник, охватывающий все заданные точки.

Алгоритм:
1. Найдите самую нижнюю точку P0, сравнивая Y всех точек. В случае равенства по Y выберите тот, у которого X меньше.
2. Отсортируйте оставшиеся n-1 точек по углам вокруг P0 против часовой стрелки. Если углы одинаковы, сначала отдайте приоритет ближайшей точке.
3. Удалите точки с одинаковым углом, оставив только самую дальнюю от P0. Пусть размер нового массива будет m.
4. Если m меньше 3, верните «Выпуклая оболочка невозможна».
5. Создайте пустой стек «S» и поместите первые три точки в «S».
6. Обрабатываем оставшиеся m-3 точки одну за другой. Для каждой точки:
⁃ Пока ориентация двух верхних точек в стеке и «points[i]» не против часовой стрелки, извлекайте точки из стека
⁃ Положите «points[i]» в «S».
7. Стек «S» теперь содержит точки выпуклой оболочки.

Сложность: O(nLogn)

Ориентация 3-х упорядоченных точек

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

Ориентация упорядоченной тройки точек на плоскости может быть:
⁃ Против часовой стрелки: математически ориентация является против часовой стрелки, если векторное произведение векторов AB и BC положительно.
⁃ По часовой стрелке: математически ориентация по часовой стрелке, если векторное произведение векторов AB и BC отрицательно.
⁃ Коллинеарность: Если ориентация коллинеарна, это означает, что точки A, B и C находятся на одной прямой. Математически ориентация коллинеарна, если векторное произведение векторов AB и BC равно нулю.

Сложность определение ориентации точек: O(1)

Найдите простой замкнутый путь для заданного набора точек

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

Алгоритм:
1. Сначала отсортируйте заданные точки по их полярным углам относительно опорной точки. Ориентиром может быть любая точка из набора.
2. Постройте путь: начиная с контрольной точки, посещайте точки в отсортированном порядке. Двигаясь от одной точки к другой, соединяйте их отрезками линий. Убедитесь, что путь не пересекает сам себя.
3. После посещения всех точек соедините последнюю точку с контрольной точкой, чтобы закрыть путь.

Сложность: O(n Log n), если мы используем алгоритм сортировки O(nLogn) для сортировки точек.

Проверка, пересекаются ли два заданных отрезка

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

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

Сложность: O(1)