 |
 |
 |
 |
|
 |
 |
90
Таким образом можно высказать окончательное
Утверждение. Конечным результатом выполнения будет
у = х
5
для любых значений х.
Доказательство. Исходя из описания результатов выполнения присваиваний значение у
будет равно
у = v2
x = (v1
v,)
x = ((х
х).(х
х)))
х = x
5
.
Что и требовалось доказать.
Техника анализа и доказательства правильности алгоритмов и программ во многом сов-
падает с техникой доказательства любых других утверждений и состоит в применении следующих
четырех приемов:
разбор случаев;
подбор контрпримеров;
выделение лемм;
индуктивный вывод.
Разбор случаев применяется для анализа результатов выполнения конструкций альтерна-
тивного выбора. В качестве примера проведем анализ приведенного выше алгоритма «выбора»
максимума трех чисел, содержащего выбор альтернатив.
алг «у = тах(а, b,с)»
Результаты
нач
если а > b то
при а > b
у := а
у = а
инес b > с то
при b > с
у := b
у = b
инес с > а то
при с > а
у := с
у = с
кесли
при не (b > с)
кон
Справа от алгоритма приведены результаты вычислений с указанием условий, при которых
они получаются. На основании этих фактов можно заключить, что конечные результаты вычисле-
ния имеют три варианта:
а, при а > b,
у =
b, при b > с и b
а,
с, при с > а и с
b.
В то же время значение максимума должно быть равно:
а, при а
b и а
с,
mах = b, при b
с и b
а,
с, при с
а и с
b.
Во всех трех случаях видны различия в условиях получения и определения максимальных
значений. Покажем, что эти различия существенны и утверждение о том, что алгоритм дает пра-
вильные результаты для всех данных, неверно.
Для опровержения общего утверждения достаточно указать хотя бы один контрпример. В
данном случае утверждение о правильности алгоритма гласило бы: для любых значений перемен-
ных а, b, с конечным было бы значение mах (а, b, с).
Контрпримером в данном случае будут значения: а = 2, b = 1, с = 3. Для этих данных по
определению mах = 3, а по результатам выполнения алгоритма у = 2. Следовательно, в алгоритме
содержится ошибка.
Однако оказывается, что это не единственная ошибка. Более тонкие ошибки вскрывает
второй контрпример: а = 1, b = 1, c = 1. Для этих данных в алгоритме вовсе не определен результат
вычислений у = ? и конечный результат выполнения программы будет непредсказуем!?
Правильное решение этой задачи можно получить применением систематических методов,
составив постановку и описание метода решения.