Информатика
Анализ правильности алгоритмов - часть 4
Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.
Алгоритм считается правильным, если он дает правильные результаты для любых допустимых исходных данных. Правильность алгоритмов решения прикладных задач и наличие в них ошибок можно проверять двумя основными способами.
Первый способ - проверка основных этапов построения алгоритма:
задача ® постановка ® метод ® алгоритм
Второй способ - анализ результатов выполнения алгоритмов и их сравнение с выбранными методами решения и постановкой задачи:
задача ¬ постановка ¬ метод ¬ алгоритм
Приведем пример построения алгоритма с одновременным анализом его правильности.
Задача: Определить периметр треугольника, заданного на плоскости координатами вершин.
XС,УС
 |
XА,УА Xв,Ув
Постановка задачи
Определение периметра треугольника, заданного на плоскости.
В = (ХВ, УВ) - координаты вершин треугольника
С = (XС,УС)
Треб.: Р - периметр
Метод решения
LАВ =
LВС =
LСА =
Где: Р = L(A,B) + L(B,C) + L(C,A);
здесь L[(x,y),(u,v)] =
Приведем алгоритм, полученный из описания метода упорядочением операций вычисления длин сторон треугольника с завершающим вычислением периметра. Результаты выполнения алгоритма приведены справа.
алг «периметр треугольника»
нач
LAB: =
LBC : =
LCA
: =
Р := LAB + LBC + LCA
кон
Р = LAB + LBC + LCA
Сравнение результатов выполнения алгоритма с описанием метода решения показывает, что это одна и та же система формул, что подтверждает правильность алгоритма.
Систематические методы анализа правильности алгоритмов и программ опираются на сопоставление тех же самых описаний, которые используются при их систематическом составлении.
Анализ правильности:
задача ¬ способ
¯ ¯
