Содержание

Вариант 3.6. Буфер показаний датчика

Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Удовлетворительно.

Постановка задачи

Событие — показание датчика. text — условное текстовое обозначение измерения, включая его тип или метку; арифметические действия над ним не нужны. Хранятся последние c измерений.

Разработайте программу хранения ограниченной истории событий. При поступлении нового события заполненная история теряет самое старое событие. Пользователь может изменить число сохраняемых событий.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
INIT c Очистить историю и установить ёмкость c. Повторная инициализация разрешена. OK
ADD text Добавить событие в конец; если места нет, удалить самое старое. При c=0 событие не сохраняется. OK
RESIZE c Изменить ёмкость. При уменьшении оставить c самых новых событий в прежнем относительном порядке. OK
GET i Получить запись с индексом i. VALUE text; если i вне [0,n), Error: RANGE
LIST Получить все сохранённые события от самого старого к самому новому. ITEMS n, затем n строк text

Правила выполнения и ошибки

Повторяющиеся события сохраняются отдельно. Расширение ёмкости не восстанавливает удалённые события. Все команды, кроме INIT, до инициализации возвращают Error: STATE после проверки синтаксиса и статических диапазонов аргументов.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

ADD и GET — O(1); RESIZE и INIT — O(c+n); LIST — O(n). Дополнительная память, включая хранение событий, — O©; длина каждого токена ограничена константой общего формата.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 3.6, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Хранение и вытеснение

Ввод:

1
6
INIT 2
ADD first
ADD second
ADD third
LIST
GET 0

Вывод:

Course work for option 3.6, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 2
second
third
VALUE second

Пример 2. Сжатие и последующее расширение

Ввод:

1
6
INIT 2
ADD first
ADD second
RESIZE 1
RESIZE 3
LIST

Вывод:

Course work for option 3.6, created by Ivan Ivanov.
OK
OK
OK
OK
OK
ITEMS 1
second

Пример 3. Ошибки и нулевая ёмкость

Ввод:

1
5
ADD first
INIT 0
ADD first
GET 0
LIST

Вывод:

Course work for option 3.6, created by Ivan Ivanov.
Error: STATE
OK
OK
Error: RANGE
ITEMS 0