Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade3:1

Вариант 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
courses/algorithms_structures/cw_2026/grade3/1.txt · Последнее изменение: — 127.0.0.1