 |
 |
 |
 |
|
 |
 |
127
Таким образом, индуктивное утверждение доказано. В силу математической индукции это
утверждение верно для всех 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
неизвестно, то неопределено значение результата
выполнения первого шага цикла. Аналогичное утверждение можно сделать о втором и всех последу-
ющих шагах выполнения цикла: