Элементы доказательного программирования - часть 5

Контрпримером в данном случае будут значения: а = 2, b = 1, с = 3. Для этих данных по определению mах = 3, а по результатам выполнения алгоритма у = 2. Следовательно, в алгоритме содержится ошибка.

Однако оказывается, что это не единственная ошибка.

Более тон­кие ошибки вскрывает второй контрпример: а = 1, b = 1, c = 1. Для этих данных в алгоритме вовсе не определен результат вычислений у = ? и конечный результат выполнения программы будет непред­сказуем!?

Правильное решение этой задачи можно получить применением систематических методов, составив постановку и описание метода решения.

 

Постановка задачи            Метод решения

Вычисление mах (а, b, с).

Дано:

а, b, с - три числа,      mх = mах(mах(а,b),с)

Треб.:

mх - максимум,         mах(х,у) =   х, при х ³ у

Где:

mх = mах (а, b, с).                              у, при у ³ х

Данный метод решения непосредственно состоит из формул определения максимумов из трех и двух чисел. Реализация этого метода в форме алгоритма может быть такой:

алг «тх = тах(а,b,с)»                                   Результаты

нач

если а ³  b то                                                при а ³ b

тх := а                                                      mx = a

иначе                                                              при b > а

mх := b                                                      mх = b

кесли { mх = mах(а,b) }                             при с < mх

если с ³ mх то                                           при с ³

mх

mх := с                                                    mх' = с

кесли

кон

Доказательство правильности алгоритмов можно проводить двумя способами. Первый способ - анализ правильности при по­строении алгоритмов. Второй способ - анализ правильности после построения алгоритмов.

Первый способ - показать, что алгоритм является корректной реализацией метода решения, и доказать, что метод - правильный.

Содержание  Назад  Вперед