Алгоритмы и структуры данных. Подгруппа 107-1 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Задачи 26.01) |
(→Семинар 26.01) |
||
| Строка 1: | Строка 1: | ||
| − | == | + | == Домашние задания == |
| + | Задача из домашнего задания засчитывается, если выполнены 2 условия. | ||
| + | 1. Она была сдана в контест до дедлайна и прошла все тесты. | ||
| + | 2. Были исправлены все замечания по review. | ||
| + | |||
| + | === Общие замечания по ДЗ1 === | ||
| + | 1. В задача E должна быть решена через функцию Partition. | ||
| + | 2. QuickSort в задаче E должен работать за O(n log n) в среднем, вне зависимости от входных данных. Решения, где pivot всегда выбирается как средний элемент, и другие алгоритмы, работающие за O(n^2) в худшем случае, нужно будет исправить. | ||
=== Задачи 26.01 === | === Задачи 26.01 === | ||
# Дан массив длинны n не содержащий повторяющихся элементов. Найти в нем любой локальный минимум(элемент меньше своих соседей). | # Дан массив длинны n не содержащий повторяющихся элементов. Найти в нем любой локальный минимум(элемент меньше своих соседей). | ||
# Модифицировать алгоритм сортировки подсчётом с семинара, так чтобы можно было сортировать пары (int, T). | # Модифицировать алгоритм сортировки подсчётом с семинара, так чтобы можно было сортировать пары (int, T). | ||
| + | |||
| + | === Задачи 09.02 === | ||
| + | # Дана строка S и словарь D. Найти количество разбиений строки S на слова из словаря D. | ||
| + | # Дан массив положительных чисел. Робот начинает движение с нулевой ячейки. Он может прыгать в право на число ячеек не превышающее значения текущей ячейки. Найти минимальное количество прыжков, которое нужно сделать, чтобы выпрыгнуть за правую границу массива. | ||
| + | # Даны 3 строки. Является ли первая строка перемешиванием двух других. | ||
| + | |||
| + | === Задачи 12.02 === | ||
| + | # Есть набор вещей с разными весами и рюкзак в котором можно унести R килограмм. Какой максимальный вес можно набрать? | ||
Версия 14:03, 9 февраля 2015
Содержание
Домашние задания
Задача из домашнего задания засчитывается, если выполнены 2 условия. 1. Она была сдана в контест до дедлайна и прошла все тесты. 2. Были исправлены все замечания по review.
Общие замечания по ДЗ1
1. В задача E должна быть решена через функцию Partition. 2. QuickSort в задаче E должен работать за O(n log n) в среднем, вне зависимости от входных данных. Решения, где pivot всегда выбирается как средний элемент, и другие алгоритмы, работающие за O(n^2) в худшем случае, нужно будет исправить.
Задачи 26.01
- Дан массив длинны n не содержащий повторяющихся элементов. Найти в нем любой локальный минимум(элемент меньше своих соседей).
- Модифицировать алгоритм сортировки подсчётом с семинара, так чтобы можно было сортировать пары (int, T).
Задачи 09.02
- Дана строка S и словарь D. Найти количество разбиений строки S на слова из словаря D.
- Дан массив положительных чисел. Робот начинает движение с нулевой ячейки. Он может прыгать в право на число ячеек не превышающее значения текущей ячейки. Найти минимальное количество прыжков, которое нужно сделать, чтобы выпрыгнуть за правую границу массива.
- Даны 3 строки. Является ли первая строка перемешиванием двух других.
Задачи 12.02
- Есть набор вещей с разными весами и рюкзак в котором можно унести R килограмм. Какой максимальный вес можно набрать?
