Элементы доказательного программирования - часть 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х' = с

кесли

кон

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

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

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