Алгоритмы

Ниже представлена таблица сравнительного анализа скорости сортировки, при использовании разных алгоритмов. На вход подавался список из случайно сгенерированных чисел в интервале от 0 до 99, длинна списка — 10000. Замер скорости при помощи встроенного python модуля timeit № Алгоритм сортировки Затраченное на сортировку время (сек.) 1 Пузырьком 54.965114210004685 2 Вставкой 26.21249842699035 3 Слиянием 0.5282726000004914 4 … Читать далее

Дано: В офисе имеется комната для переговоров, сотрудники подают заявки для проведения совещаний в переговорке. Каждая заявка содержит время начала и время окончания совещания. Задача, спланировать расписание таким образом, что бы удовлетворить максимальное число заявок. Схематично это можно представить так (верхняя линия — время работы переговорки, нижние линии — заявки на проведение совещания): Алгоритм решения … Читать далее

Ввод: список точек на прямой. Вывод: Минимальное количество отрезков единичной длинны, с помощью которых можно покрыть все эти точки. Пример реализации #1. В этом примере мы покрыли все точки 4-мя отрезками, что является не оптимальным решением: Пример # 2 правильная реализации покрытия: Так для того, что бы покрыть точки минимальным количество отрезков, необходимо: Отсортировать все … Читать далее

Алгоритм нахождения НОД (наибольшего общего делителя). Вычисляется при помощи алгоритма Евклида. НОД — для не отрицательных чисел a и b, которые > 0 — это не отрицательное, целое число которое делит и а и b. Алгоритм Евклида Если а = 0, вернуть b Если b = 0, вернуть a Далее, необходимо поделить большее из 2-ух … Читать далее

Алгоритм сортировки улиткой. Вернуть элементы массива, расположенные от самых внешних элементов к среднему элементу, по часовой стрелке. array = [[1,2,3], [4,5,6], [7,8,9]] snail_sort # => [1,2,3,6,9,8,7,4,5] def snail(array): a = [] while array: a.extend(list(array.pop(0))) array = list(zip(*array)) array.reverse() return a a.extend(list(array.pop(0))) a = [1, 2, 3] array = [[4, 5, 6], [7, 8, 9]] array … Читать далее

BFS — алгоритм обхода графа в ширину «»» ****** Стандартный алгоритм обхода графа в ширину (bfs). **** Алгоритм работает следующим образом: 1. Начните с размещения любой вершины графа в конце очереди. 2. Возьмите передний элемент очереди и добавьте его в список посещенных. 3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке … Читать далее

Алгоритм обхода графа в глубину «»» ****** Стандартный алгоритм обхода графа в глубину. **** 1. Начните с размещения любой вершины графа на вершине стека. 2. Возьмите верхний элемент стека и добавьте его в список посещенных. 3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в начало стека. 4. Продолжайте повторять … Читать далее

Алгоритм нахождения n-ого числа в последовательности Фибоначи def fib(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a  

Алгоритм представления числа в виде суммы квадратов # Сумма квадратов чисел n = 2 i = 1 # начинать с нуля не имеет смысла, т.к. 0^2 = 0 sum = 0 # наш цикл должен работать так же, как и for i in range(1, n+1). Поэтому условие именно такое, а на каждой итерации увеличиваем i … Читать далее