Алгоритмы и структуры данных. Подгруппа 107-1 — различия между версиями

Версия 15:08, 9 февраля 2015

Задача из домашнего задания засчитывается, если выполнены 2 условия.

В задача E должна быть решена через функцию Partition.
QuickSort в задаче F должен работать за O(n log n) в среднем, вне зависимости от входных данных. Решения, где pivot всегда выбирается как средний элемент, и другие алгоритмы, работающие за O(n^2) в худшем случае, нужно будет исправить.

Дан массив длинны n не содержащий повторяющихся элементов. Найти в нем любой локальный минимум(элемент меньше своих соседей).
Модифицировать алгоритм сортировки подсчётом с семинара, так чтобы можно было сортировать пары (int, T).

Дана строка S и словарь D. Найти количество разбиений строки S на слова из словаря D.
Дан массив положительных чисел. Робот начинает движение с нулевой ячейки. Он может прыгать в право на число ячеек не превышающее значения текущей ячейки. Найти минимальное количество прыжков, которое нужно сделать, чтобы выпрыгнуть за правую границу массива.
Даны 3 строки. Является ли первая строка перемешиванием двух других.

Есть набор вещей с разными весами и рюкзак в котором можно унести R килограмм. Какой максимальный вес можно набрать?

@@ Строка 4: / Строка 4: @@
 # Были исправлены все замечания по review.
-=== Общие замечания по ДЗ1 ===
+=== Общие замечания по ДЗ 1 ===
 # В задача E должна быть решена через функцию Partition.
 # QuickSort в задаче F должен работать за O(n log n) в среднем, вне зависимости от входных данных. Решения, где pivot всегда выбирается как средний элемент, и другие алгоритмы, работающие за O(n^2) в худшем случае, нужно будет исправить.