ALGORITHMS
Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.
В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер.
Алгоритм работает за O (n+m), где n — число вершин, m — число рёбер.
Описание…
Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в n-ую степень за O(log n) умножений (вместо n умножений при обычном подходе).
Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется…
Функция Эйлера phi (n) — это количество чисел от 1 до n, взаимно простых с n. Иными словами, это количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице.
18 апр 2020
Дан неориентированный граф G с n вершинами и m рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.
Алгоритм решения:
Для…
22 окт 2020
Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).
Алгоритм
Работать с отрезками будем как с прямыми: построим…
Решето Сундарама — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа n. Разработан индийским студентом Сундарамом в 1934 году.
26 апр 2020
Дана окружность (координатами своего центра и радиусом) и прямая (своим уравнением). Требуется найти точки их пересечения (одна, две, либо ни одной).…
30 ноя 2020
Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.
`
ОЖИДАНИЕ РЕКЛАМЫ...