 |
 |
 |
 |
|
 |
 |
88
4. Зачем нужны описания методов?
5. Как проверяется правильность методов?
6. Зачем нужны описания результатов?
З
а
д
а
ч
и
1. В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М - за-
данное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований.
Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания
дневного спроса на них.
2. Каждый из N магазинов в течение месяца работал D дней (N и D - заданные числа 1, 2, .... N). Известна
прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам
список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по
всем магазинам.
3. Каждое из N предприятий города выпускает М одинаковых наименований продукции (N и М, наименова-
ния продукции и названия предприятий известны). Заданы объем выпуска и стоимость единицы продукции каждого
вида для каждого из предприятий. Необходимо для каждого вида продукции определить предприятия, выпускающие
наибольший объем этой продукции.
4. Из разных городов выбрали N семей (N - заданное число). Каждая семья характеризуется числом членов и
доходом каждого из них.
Для каждого города сформировать перечень семей с минимальным доходом в пересчете на
отдельного члена семьи, указав порядковые номера семей из общего списка.
5. Ассортимент N магазинов состоит из М товаров (N, М и названия товаров заданы). Каждый товар характе-
ризуется наличием или отсутствием его в магазине, а также наличием или отсутствием на него спроса покупателей.
Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос
отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магази-
нов) товаров.
5.4. Элементы доказательного программирования
Доказательное программирование - это составление программ с доказательством их пра-
вильности. Сложность составления и доказательства правильности алгоритмов и программ состо-
ит в следующем.
Для заключений о наличии ошибок в алгоритме или в программе достаточно указать тест,
при котором произойдет сбой, отказ или будут получены неправильные результаты. Поиск и ис-
правление ошибок в программах обычно проводится на ЭВМ.
Для утверждений о правильности программ необходимо показать, что правильные ре-
зультаты будут получаться для всех допустимых данных. Такие утверждения могут быть доказаны
только путем исчерпывающего анализа результатов выполнения программ при любых допусти-
мых данных.
Существуют два подхода к проверке программ - прагматический и доказательный. При
прагматическом подходе проверка программ выполняется на ЭВМ путем тестирования.
Тестирование - это проверка программ на ЭВМ с помощью некоторого набора тестов. Яс-
но, что тестирование не дает гарантий правильности выполнения программ на всех допустимых
данных. Следовательно, тестирование в общем случае не может дать и не дает полных гарантий
отсутствия ошибок в программах.
Напомним, что отладка программ - это процесс поиска и исправления ошибок в програм-
мах на ЭВМ. Однако поскольку поиск ошибок при отладке программ проводится с помощью тес-
тов, то полных гарантий нахождения и исправления всех ошибок в программах отладка не дает и в
принципе дать не может.
По этой же причине не ясно, когда процесс отладки программ - процесс поиска и исправ-
ления ошибок на ЭВМ - может считаться завершенным. А выявлены или нет все ошибки в про-
грамме при ее отладке не может сказать никто.
Таким образом, прагматический подход чреват созданием программ, содержащих ошибки
даже после «завершения» отладки, что и наблюдается практически во всех больших программах
для ЭВМ.
Рассмотрим в качестве иллюстрации принципов тестирования алгоритм и программу вы-
числения максимума из трех чисел: а, b, с.