 |
 |
 |
 |
|
 |
 |
131
от i = k + 1 до N цикл
если x
i
< хтп то
хтп := x
i
imn := i
кесли
кцикл
{ xmn = Min (х
k
, ..., х1) }
кон
конечным результатом вычислений будет значение
xmn = Min (х
k
, ..., х
N
).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmn
k
= x
k
.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
x
k+1
при x
k+1
< xmn
k
,
xmn
k+l
=
xmn
k
при x
k+1
xmn
k
.
На втором шаге цикла будет получен минимум первых трех чисел:
xmn
k+2
= min (x
k+2
, min (х
k+1
, х
k
)) = Min (х
k+2
, х
k+1
, х
k
).
Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет
минимальное значение среди чисел 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
).