Ctrl+Enter
Так как листок пишется с нуля, то в нём хватает опечаток, неточностей и ошибок. Если вы заметили опечатку или ошибку, выделите её, нажмите Ctrl+Enter и опишите проблему. Желательно также написать ещё и её решение.Точно также можно поступить, если какой-то кусок текста совсем непонятен. А если вы можете предложить замену некоторой части на гораздо более понятный текст — то будет просто замечательно!
PS. Перед тем, как отправить ошибку, обновите страницу. Возможно, ошибка уже исправлена.
PSS. Не нужно тестировать эту функцию просто так, она вроде работает. Но каждое замечание я буду вынужден читать :)
Что будем делать
В данном необязательном листке мы займёмся изучением структур данных.
Изучать мы их будем в следующей модельной ситуации: наше электронное вычислительное устройство и операции, которое оно поддерживает, крайне просто. Нет никаких сложных структур данных вроде питоновских словарей и множеств или плюсовых векторов. Только переменные типа «целое число», переменные типа «массив целых чисел фиксированной длины» и переменная типа «указатель на некоторую позицию в оперативной памяти», которая на самом деле является целым числом. Кроме арифметических операций есть также операция «выделить оперативную память заданной длины и вернуть указатель на её начало». Массив чисел длины n — это на самом деле указатель на n последовательных чисел в оперативной памяти. Доступ к элементу с номером i получается просто прибавлением к указателю на начала массива числа i.
На самом деле модельная ситуация не такая уж модельная, микроконтроллеры зачастую живут примерно в таких условиях.
Как сдавать
Решение теоретической задачи нужно сдавать в виде текста решения или pdf-файла с записанным в LaTeX решением. Пример такого решения будет ниже. При желании вы можете написать код на питоне или си, реализующий данную структуру данных.class _StackItem: """Класс _StackItem - один элемент стека. Хранит значение и ссылку на предыдущий элемент, или None, если такого нет """ __slots__ = ['value', 'prev'] def __init__(self, value, prev): self.value = value # Значение self.prev = prev # Ссылка на предыдущий элемент class Stack: """Класс Stack - ссылочная реализация стека. """ __slots__ = ['_len', '_top'] def __init__(self): """Создать пустой стек""" self._len = 0 self._top = None def push(self, value): """Добавить в стек новое значение""" self._top = _StackItem(value, self._top) self._len += 1 def pop(self): """Изъять с головы стека значение. Бросить ошибку, если стек пуст""" if self._top is None: raise(IndexError('pop from empty stack')) old_top = self._top value = old_top.value self._top = old_top.prev self._len -= 1 del(old_top) return value def top(self): """Вернуть содержимое вершины стека. Бросить ошибку, если стек пуст""" if self._top is None: raise(IndexError('stack is empty')) return self._top.value def clear(self): """Очистить стек""" while self._top: old_top = self._top self._top = old_top.prev del(old_top) self._len = 0 def len(self): """Вернуть текущую длину стека""" return self._len ################################################################################ # Модульное тестирование класса Stack # Используем модуль unittest: https://docs.python.org/3.5/library/unittest.html # Только для ценителей "прекрасного" import unittest class TestStack(unittest.TestCase): def test_init(self): t_stack = Stack() self.assertIsNotNone(t_stack) self.assertEqual(t_stack.len(), 0) def test_one_push_one_pop(self): t_stack = Stack() t_stack.push(179) self.assertEqual(t_stack.top(), 179) self.assertEqual(t_stack.len(), 1) self.assertEqual(t_stack.pop(), 179) self.assertEqual(t_stack.len(), 0) self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_10000_push_pop(self): t_stack = Stack() for i in range(10000): self.assertEqual(t_stack.len(), 0, msg='len should be 0') t_stack.push(i) self.assertEqual(t_stack.len(), 1, msg='len should be 1') self.assertEqual(t_stack.top(), i, msg='top should be {}'.format(i)) self.assertEqual(t_stack.pop(), i, msg='pop should return {}'.format(i)) self.assertEqual(t_stack.len(), 0, msg='len should be 0') self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_10000_push_10000_pop(self): t_stack = Stack() for i in range(10000): self.assertEqual(t_stack.len(), i) t_stack.push(i) self.assertEqual(t_stack.len(), i + 1) self.assertEqual(t_stack.top(), i) for i in range(9999, -1, -1): self.assertEqual(t_stack.len(), i + 1) self.assertEqual(t_stack.pop(), i) self.assertEqual(t_stack.len(), i) self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_clear_0(self): t_stack = Stack() t_stack.clear() self.assertEqual(t_stack.len(), 0) self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_clear_1(self): t_stack = Stack() t_stack.push(179) t_stack.clear() self.assertEqual(t_stack.len(), 0) self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_clear_10000(self): t_stack = Stack() for i in range(10000): t_stack.push(i) t_stack.clear() self.assertEqual(t_stack.len(), 0) self.assertRaises(IndexError, t_stack.pop) self.assertRaises(IndexError, t_stack.top) def test_541_stacks(self): t_stacks = [Stack() for i in range(541)] for i in range(10000): cur_stack = t_stacks[i % len(t_stacks)] cur_stack.push(i) self.assertEqual(cur_stack.top(), i) self.assertEqual(cur_stack.len(), i // len(t_stacks) + 1) for i in range(9999, -1, -1): cur_stack = t_stacks[i % len(t_stacks)] self.assertEqual(cur_stack.pop(), i) self.assertEqual(cur_stack.len(), i // len(t_stacks)) if __name__ == '__main__': unittest.main(verbosity=2)
Решение практической задачи — это код на любом языке программирование, плюс минимальные тесты, проверяющие работоспособность структуры, в том числе нагрузочные тесты. Выше приведено два в одном.
Игры со стеками
Стек — одна из самых базовых структур данных. Он должен поддерживать следующие операции:- Создать новый стек;
- Добавить элемент в голову ;
- Снять элемент с головы;
- Посмотреть на элемент в голове;
- Узнать, пуст ли стек.
01. Ограниченный стек в массиве
Будем считать, что количество элементов в стеке не превосходит некоторого числа n. Придумайте, как организовать стек в массиве так, чтобы каждая операция, кроме создания нового стека, требовало время, ограниченное константой, не зависящей от длины стека.
Опишите, как хранить части стека в памяти, и как реализовывать каждую из 5 операций.
Пример начала решения.
Будем хранить текущую длину стека в отдельной переменнойstack_len
.
Операция "Создать новый стек" — это уставка
stack_len
в 0.
Операцию "Добавить элемент в голову" будем выполнять так: увеличиваем
stack_len
на единицу и добавляем новое значие в массив по индексу stack_len
.
...
Пример в виде кода
class Stack(): N = 1000 def __init__(self): self._stack_len = 0 self._array = [0] * self.N def push(self, elem): self._stack_len += 1 self._array[self._stack_len] = elem ...
02. Два стека по цене одного
Реализуйте с помощью одного массива два стека, суммарное количество элементов в которых ограничено длиной массива; все действия со стеками должны выполняться за время, ограниченное константой, не зависящей от длины стеков.
03. Стеки оптом
Реализуйте k стеков, общее количество элементов в которых не превосходит n, с использованием массивов суммарной длины \(C(n + k)\), затрачивая на каждое действие со стеками (кроме начальных действий, выделяющих память и делающих все стеки пустыми) время не более некоторой константы C. (Как говорят, общая длина массивов должна быть O(n + k), a время на каждую операцию — O(1).)
Мы пришли, а там — очередь!
Очередь — вторая из самых базовых структур данных. Она должна поддерживать следующие операции:- Создать новую очередь;
- Добавить элемент в хвост;
- Снять элемент с головы;
- Посмотреть на элемент в голове;
- Узнать, пуста ли очередь.
04. Ограниченная очередь в массиве
Будем считать, что количество элементов в очереди не превосходит некоторого числа n. Придумайте, как организовать очередь в массиве так, чтобы каждая операция, кроме создания новой очереди, требовало время, ограниченное константой, не зависящей от длины очереди.
05. Очередь из двух стеков
Придумать способ моделирования очереди с помощью двух стеков (и фиксированного числа переменных). При этом отработка n операций с очередью (начатых, когда очередь была пуста) должна требовать порядка n действий. (То есть не обязательно любая операция требует константу времени. Иногда могут требоваться «тяжёлые» операции, требующие вообще говоря сколь угодно много времени. Однако в среднем число операций должно быть линейно).
Крекс, пекс, декс!
Деком называют структуру, сочетающую очередь и стек: класть и забирать элементы можно с обоих концов. То есть дек поддерживает следующие операции:- Создать новый дек;
- Добавить элемент в хвост;
- Добавить элемент в голову;
- Снять элемент с хвоста;
- Снять элемент с головы;
- Посмотреть на элемент в хвосте;
- Посмотреть на элемент в голове;
- Узнать, пуст ли дек.
06. Ограниченный дек в массиве
Как реализовать дек ограниченного размера на базе массива так, чтобы каждая операция требовала ограниченного числа действий?
07. Узнать длину дека и ничего не испортить
Имеется дек и конечное число переменных. В начальном состоянии в деке некоторое число элементов. Составить программу, после исполнения которой в деке остались бы те же самые элементы, а их число было бы в одной из целых переменных.
08. А зачем нам, извините, столько очередей?
Реализуйте k очередей с ограниченной суммарной длиной n, используя память O(n + k), затрачивая O(1) на каждое действие со очередями (кроме начальных действий, выделяющих память и делающих их все пустыми).
Множества. Быстро, экономно, качественно: выберите любые два
Существует много способов хранить (конечные) множества элементов. Выбор между ними определяется ограничениями на данные и набором требуемых операций.
Начнём с более простых — с подмножества множества \(\{1\ldots n\}\).
09. Подмножество — 1
Используя память \(O(n)\), хранить подмножества множества \(\{1\ldots n\}\), поддерживая следующие операции:
Операция | Время |
---|---|
Создать или очистить | \(O(n)\) |
Проверить принадлежность | \(O(1)\) |
Добавить | \(O(1)\) |
Удалить | \(O(1)\) |
Проверка пустоты | \(O(n)\) |
10. Подмножество — 2
То же, но
Операция | Время |
---|---|
Проверка пустоты | \(O(1)\) |
Минимальный элемент | \(O(n)\) |
11. Подмножество — 3
То же, но
Операция | Время |
---|---|
Создать или очистить | \(O(n)\) |
Проверить принадлежность | \(O(1)\) |
Добавить | \(O(1)\) |
Удалить | \(O(n)\) |
Проверка пустоты | \(O(1)\) |
Минимальный элемент | \(O(1)\) |
12. Подмножество — 4
То же, но
Операция | Время |
---|---|
Создать или очистить | \(O(n)\) |
Проверить принадлежность | \(O(1)\) |
Добавить | \(O(n)\) |
Удалить | \(O(1)\) |
Проверка пустоты | \(O(1)\) |
Минимальный элемент | \(O(1)\) |
Множества целых чисел
В следующих задачах величина элементов множества не ограничена, но их количество не превосходит n.13. Множество — 1
Используя память \(O(n)\), хранить не более, чем n-элементные множества, поддерживая следующие операции:
Операция | Время |
---|---|
Создать | \(O(n)\) |
Очистить | \(O(1)\) |
Число элементов | \(O(1)\) |
Проверить принадлежность | \(O(n)\) |
Добавить новый (заведомо отсутствующий) | \(O(1)\) |
Удалить | \(O(n)\) |
Минимальный элемент | \(O(n)\) |
Взять какой-то элемент | \(O(1)\) |
14. Множество — 2
То же, но
Операция | Время |
---|---|
Очистить | \(O(1)\) |
Число элементов | \(O(1)\) |
Проверить принадлежность | \(O(\log n)\) |
Добавить | \(O(n)\) |
Удалить | \(O(n)\) |
Минимальный элемент | \(O(1)\) |
Ссылочные структуры
15. Стек на односвязном списке
Придумайте, как организовать стек так, чтобы его размер ограничивался лишь размером оперативной памяти (требуя при этом \(O(n)\) памяти), и чтобы сложность всех стандартных операций со стеком была \(O(1)\).
16. Двусвязный список
Двусвязный список — это такая структура данных, требующая \(O(n)\) памяти (где \(n\) — текущее количество элементов в списке), и поддерживающая следующие операции:
Операция | Время |
---|---|
Создать пустым | \(O(1)\) |
Очистить | \(O(n)\) |
Получить число элементов | \(O(1)\) |
Добавить элемент в голову или в хвост | \(O(1)\) |
Посмотреть на элемент в голове или в хвосте | \(O(1)\) |
Снять элемент с головы или с хвоста | \(O(1)\) |
Установить новый итератор в голову или в хвост | \(O(1)\) |
Проверить, что выбранный итератор находится в голове или в хвосте | \(O(1)\) |
Сдвинуть выбранный итератор в сторону головы или хвоста | \(O(1)\) |
Посмотреть элемент, на который указывает итератор | \(O(1)\) |
Снять элемент, на который указывает итератор, и перевести итератор на соседа | \(O(1)\) |
Добавить новый элемент со стороны головы или хвоста от итератора | \(O(1)\) |