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

Ой, фу, тут куча!