 |
 |
 |
 |
|
 |
 |
132
Доказательство. В силу леммы 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
) = x3'.
Таким образом, после третьего шага при k = 3 первые три значения последовательности х1', x2', x3'
будут удовлетворять условию
х1'
x2'
x3'
Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-
м шаге выполнения основного цикла первые k членов последовательности х1', x2', .... х
k
' будут удов-
летворять условию