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)\) |