Содержание
Вариант 3.1. История команд терминала
Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Постановка задачи
Событие — введённая пользователем команда терминала. text хранит её условное обозначение одним токеном. Программа хранит последние c вводов, включая повторные команды.
Разработайте программу хранения ограниченной истории событий. При поступлении нового события заполненная история теряет самое старое событие. Пользователь может изменить число сохраняемых событий.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
Данные и начальное состояние
text— непустой токен события по общему формату.c— ёмкость от 0 до 100000;i— индекс записи, начиная с 0 от самой старой.- До первой команды INIT история не инициализирована.
Операции
| Команда | Действие | Ответ |
|---|---|---|
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.1, 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.1, 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.1, 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.1, created by Ivan Ivanov. Error: STATE OK OK Error: RANGE ITEMS 0
