 |
 |
 |
 |
|
 |
 |
93
Таким образом, индуктивное утверждение доказано. В силу математической индукции это
утверждение верно для всех k = l, 2, ..., N. Следовательно, на последнем шаге конечным результа-
том выполнения цикла станет значение
S
N
= S
N-1
(N-1) + X[N]/N = X[1]/N + ... + X[N]/N.
Исходя из этого утверждения конечным результатом выполнения алгоритма в целом будет
среднее арифметическое значение
Xcp = S
N
= X[1]/N + ... + X[N]/N.
Следовательно, приведенный алгоритм, несмотря на содержащуюся в нем «ошибку», явля-
ется правильным. В целом анализ правильности алгоритмов с циклами во многом построен на ис-
пользовании индукции.
Индукция - это вывод общих суждений из частных примеров. При анализе циклов она ис-
пользуется для подбора индуктивных утверждений о промежуточных результатах выполнения
циклов. Однако для доказательства правильности индуктивных утверждений о результатах вы-
полнения циклов используется полная математическая индукция.
Математическая индукция - это принцип доказательства последовательностей утвержде-
ний Р(1), Р(2), Р(3), ..., P(N), .... когда известно, что верны первые утверждения для n = 1, 2, 3 и из
истинности (n - 1)-го утверждения следует истинность n-го утверждения:
Принцип математической индукции: если первое утверждение Р(1) истинно и из утвер-
ждения Р(n - 1) следует утверждение Р(n), то истинны все утверждения Р(1), Р(2), Р(3), ..., Р(n), ... .
Приведем примеры индуктивного анализа циклов для алгоритма нахождения минимально-
го значения в последовательности чисел, который в этот раз действительно будет ошибочным.
алг «нахождение минимума»
массив x[1:N]
нач
Результаты:
от k = 1 до N цикл
если x[k] < min то
тп := x[k]
mn
k
= { x[k], при x[k] < mn
k-1
,
все
{ mn
k-1
, в ином случае
кцикл
[ k = (1 ... N)]
Min := тп
Min = mn
N
кон
Утверждение. Приведенный алгоритм определения минимального значения последова-
тельности чисел неправильный.
Доказательство. Для демонстрации ошибок необходимо привести контрпример. Для по-
строения контрпримера разберем результаты выполнения на первом шаге цикла.
Результаты выполнения первого шага цикла при k = 1:
х[1] при х[1] < mn
0
mn1 =
= min (х[1], mn
0
).
mn
0
при х[1]
mn
0
Следовательно, результатом будет
mn1 = min (x[l], mn
0
)
Однако поскольку начальное значение mn
0
неизвестно, то неопределено значение результа-
та выполнения первого шага цикла. Аналогичное утверждение можно сделать о втором и всех по-
следующих шагах выполнения цикла:
mn
k
= min (x[k], Min(x[k-l], ..., х[1], mn
0
) = Min (x[k], x
k-1], ..., х[1], mn
0
).
В силу математической индукции это утверждение справедливо при k = N:
mn
N
= Min (x[N], x[N - 1], ..., x[2], х[1], mn
0
),
Таким образом на основании этого утверждения можно сделать заключение о конечном ре-
зультате выполнения алгоритма в целом:
Min = mn
N
= Min (x[N], x[N - 1], ..., x[2], х[1], mn
0
).