Книга: Основы объектно-ориентированного программирования
Упражнения
Упражнения
У11.1 Комплексные числа
Напишите спецификацию АТД для класса COMPLEX, описывающую понятие комплексных чисел с арифметическими операциями. Исходите из точной арифметики.
У11.2 Класс и его АТД
Проверьте все предусловия и аксиомы АТД STACK, введенного в предыдущих лекциях, и покажите, отображаются ли они в классе STACK4, а если да, то как.
У11.3 Полные утверждения для стеков
Покажите, что введение закрытой функции body, возвращающей тело стека, сделает возможным утверждениям класса STACK полностью отражать спецификацию соответствующего АТД. Обсудите теоретическую и практическую значимость такого подхода.
У11.4 Экспортирование размера
Почему capacity экспортируется для реализации стеков ограниченных размеров, класс STACK2?
У11.5 Инвариант реализации
Напишите инвариант реализации для класса STACK3.
У11.6 Утверждения и экспорт
Обсудите использование функций в утверждениях, в частности, введение функции correct_index в предусловия программ put и item. Если добавить эту функцию в класс ARRAY, то какой статус экспорта следует ей дать?
У11.7 Поиск жучков (bugs)
Покажите, что каждая из четырех попыток бинарного поиска, объявленная как "ошибочная", действительно некорректна. (Подсказка: в отличие от доказательства корректности, для доказательства некорректности достаточно предъявить один пример, на котором алгоритм приводит к неверному результату: не завершается, выполняет запрещенную операцию, такую, как выход индекса за допустимые границы, любое другое нарушение предусловия).
У11.8 Нарушение инварианта
В этой лекции было показано, что нарушение предусловия указывает на ошибку клиента, а нарушение постусловия указывает на ошибку поставщика. Объясните, почему нарушение инварианта также указывает на ошибку поставщика.
У11.9 Генерация случайных чисел
Напишите класс, реализующий алгоритм получения псевдослучайных чисел, основанный на последовательности: ni = f(ni - 1), где функция f задана, а начальное значение n0 определяется клиентом класса. Функция не должна иметь побочных эффектов. Определение функции f можно найти в учебниках, таких как [Knuth 1981] и в библиотеках по численным методам.
У11.10 Модуль "очередь"
Напишите класс, реализующий очередь (стратегию доступа "первый пришел - первый ушел", FIFO - "first in - first out"). Задайте подходящие утверждения в стиле класса STACK этой лекции.
У11.11 Модуль "множество"
Напишите класс, реализующий множество элементов произвольного типа со стандартными операциями: проверка принадлежности, добавление нового элемента, объединение, пересечение и другими. Не забудьте включить подходящие утверждения. Приемлема любая корректная реализация, основанная на массивах или связных списках.
- У11.1 Комплексные числа
- У11.2 Класс и его АТД
- У11.3 Полные утверждения для стеков
- У11.4 Экспортирование размера
- У11.5 Инвариант реализации
- У11.6 Утверждения и экспорт
- У11.7 Поиск жучков (bugs)
- У11.8 Нарушение инварианта
- У11.9 Генерация случайных чисел
- У11.10 Модуль "очередь"
- У11.11 Модуль "множество"