Анализ правильности алгоритмов - часть 4

Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.

Алгоритм считается правильным, если он дает правильные резуль­таты для любых допустимых исходных данных. Правильность алго­ритмов решения прикладных задач и наличие в них ошибок можно проверять двумя основными способами.

Первый способ - проверка основных этапов построения алго­ритма:

задача ® постановка ® метод ® алгоритм

Второй способ - анализ результатов выполнения алгоритмов и их сравнение с выбранными методами решения и постановкой задачи:

задача ¬ постановка ¬ метод ¬ алгоритм

Приведем пример построения алгоритма с одновременным ана­лизом его правильности.

Задача: Определить периметр треугольника, заданного на плос­кости координатами вершин.

XС,УС

 

 

 

 

 

XА,УА                         Xв,Ув

 

Постановка задачи

Определение периметра треугольника, заданного на плоскости.

Дано:  А = (ХА, УА)

В = (ХВ, УВ)     - координаты вершин треугольника

С = (XС,УС) 

Треб.: Р - периметр

Метод решения

    Р = LАВ +LВС+LСА

    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

Сравнение результатов выполнения алгоритма с описанием метода решения показывает, что это одна и та же система формул, что подтверждает правильность алгоритма.

Систематические методы анализа правильности алгоритмов и программ опираются на сопоставление тех же самых описаний, которые используются при их систематическом составлении.

Анализ правильности:

задача            ¬    способ

¯                              ¯

Начало  Назад  Вперед