 |
 |
 |
 |
|
 |
 |
97
Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет
минимальное значение среди чисел xk , ..., xi
хmn
i
= Min (х
k
, ..., х
i
).
Данное утверждение доказывается с помощью математической индукции. На первых двух
шагах при i = k + 1, k + 2 оно уже установлено. Покажем, что оно будет выполняться на (i + 1)-м
шаге. Действительно, на следующем шаге цикла результатом будет:
x
i+1
при х
i+1
< xmn
i
= min(x
i+1
, хmn
i
)
хmn
i+1
=
хmn
i
при х
i+1
хmn
i
= min(x
i+1
, xmn
i
)
= min (x
i+1
, Min (х
k
, ..., х
i
)) = Min (х
k
, ..., х
i
, x
i+1
).
Что и требовалось показать. Следовательно, в силу принципа математической индукции конечным
результатом выполнения рассматриваемого цикла будет значение:
xmn
N
= Min (x
k
, ..., х
N
)
Что и требовалось доказать.
Лемма 2. Для вспомогательного алгоритма
алг «перестановки»
нач
{ xmn = Min (х
k
, ..., х
N
) }
x
i
mn
= x
k
кон
конечным результатом будет значение х
k
' = Min (х
k
, ..., х
N
).
Доказательство. В силу леммы 1 xmn = Min (x
k
, ..., х
N
). А так как в этом алгоритме х
k
' =
xmn, то в итоге получим
х
k
' = xmn = Min (х
k
, ..., х
N
).
Что и требовалось.
Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная после-
довательность чисел х1', ..., х
N
', удовлетворяющая условию х1'
х2'
...
х
N
'.
Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты
выполнения основного цикла основного алгоритма:
алг «упорядочение чисел»
нач
от k = 1 до N - 1 цикл
xmn := х
k
...............
{ xmn = Min (х
k
, ..., х
i
) }
х
k
= xmn
N
хmп
= х
k
кцикл
{ х
k
' = Min (х
k
, ..., х
N
) }
кон
{ х1'
х2'
...
х
k
' }
На первом шаге при k = 1 первый элемент последовательности
х1' = Min (x1, х2, ..., х
N
),
На втором шаге второй элемент последовательности
x2' = Min (х2, ..., х
N
).
В силу свойств минимума последовательности чисел будем иметь
х1' = Min(x1, x2, ..., х
N
) = min (x1, Min (х2, ..., хN)
(Min (х2, ..., хN) = x2'.
Таким образом, при k = 2 результатом станут значения х1' и x2', такие что
х1'
x2'
На третьем шаге выполнения основного цикла результатом станет
х3 = Мin(х3, ..., х
N
).
Опять же в силу свойств минимума последовательности имеем
х2' = Min (х2, х3, ..., х
N
) = min (x2, Min (x3, ..., х
N
))
Min (x3, ..., х
N
) = x2'.
Таким образом, после третьего шага при k = 3 первые три значения последовательности х1',
x2', x3' будут удовлетворять условию
х1'
x2'
x3'