Что такое отладка и тестирование программы
5. Отладка и тестирование. Под отладкой программы понимается процесс испытания работы программы и исправления обнаруженных при этом ошибок. Обнаружить ошибки, связанные с нарушением правил записи программы на Паскале (синтаксические и семантические ошибки), помогает используемая система программирования. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет попытку исполнить программу.
Поиск алгоритмических ошибок в программе производится с помощью тестирования. Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста — необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария.
Нашу программу, например, можно протестировать на значении N = 6.На экране должно получиться:
Введите число букв: 6
Из 6 букв можно составить 720 слов.
6. Проведение расчетов и анализ полученных результатов — этот этап технологической цепочки реализуется при разработке практически полезных (не учебных) программ. Например, программы «Расчет прогноза погоды». Ясно, что ею будут пользоваться длительное время, и правильность ее работы очень важна для практики. А поэтому в процессе эксплуатации эта программа может дорабатываться и совершенствоваться.
Коротко о главном
Последовательность этапов работы программиста при решении задачи на компьютере называется технологией решения задачи на компьютере. Таких этапов шесть: 1) постановка задачи; 2) математическая формализация; 3) построение алгоритма; 4) составление программы на языке программирования; 5) отладка и тестирование программы; 6) проведение расчетов и анализ полученных результатов.
Количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Число перестановок равно N! (N факториал):
N! = 1·2· ... ·N.
Любой циклический алгоритм может быть построен с помощью команды «цикл-пока» (цикл с предусловием).
Формат оператора цикла с предусловием в Паскале:
while <выражение> do <оператор>
Оператор, составляющий тело цикла, может быть простым или составным.
Вопросы и задания
1. Как блок-схемой и на алгоритмическом языке представляется команда цикла с предусловием?
2. Как программируется цикл с предусловием на Паскале?
3. Почему алгоритм вычисления N1 должен быть циклическим?
4. Из каких этапов состоит работа программиста по решению задачи на компьютере?
5. Что такое математическая формализация задачи?
6. Что такое отладка программы? Что называется тестом?
7. Составьте алгоритм вычисления суммы всех натуральных чисел, не превышающих заданного натурального числа N. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
8. Дано целое число X и натуральное N. Составьте алгоритм вычисления XN. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
ЕК ЦОР: часть 2, глава 6, § 39. ЦОР № 7, 13-16.
§16
Алгоритм Евклида
Основные темы параграфа:
■ наибольший общий делитель;
■ идея алгоритма Евклида;
■ описание алгоритма Евклида блок-схемой;
■ алгоритм на АЯ и программа на Паскале.
Наибольший общий делитель
Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.
Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они оба делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
НОД(12, 18) = 6.
Обозначим исходные данные как M и N. Постановка задачи выглядит следующим образом:
Дано: М, N.
Найти: НОД(M, N).
В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(M, N) по значениям M и N. Нозато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.
Идея алгоритма Евклида
Идея этого алгоритма основана на том свойстве, что если M>N, то
НОД(M, N) = НОД(М -N, N).
Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.
Легко доказать это свойство. Пусть K — общий делитель M и N (M > N). Это значит, что M = mK, N = nK, где m, n — натуральные числа, причем m> n. Тогда M - N = K(m - n), откуда следует, что K — делитель числа M - N. Значит, все общие делители чисел M и N являются делителями их разности M - N, в том числе и наибольший общий делитель.
Второе очевидное свойство:
НОД(M, M) = M.
Для «ручного» счета алгоритм Евклида выглядит так:
1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;
2) заменить большее число разностью большего и меньшего из чисел;
3) вернуться к выполнению п. 1.
Рассмотрим этот алгоритм на примере M=32, N=24:
| M | ||||
| N |
Получили: НОД(32, 24) = НОД(8, 8) = 8, что верно.