Что и требовалось.
Кон
Кон
Кесли
Нач
хтп := xk
imn := k
от i = k + 1 до N цикл
если xi < хтп то
хтп := xi
imn := i
кцикл { xmn = Min (хk, ..., х1) }
конечным результатом вычислений будет значение
xmn = Min (хk, ..., хN).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmnk = xk.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
xk+1 при xk+1 < xmnk,
xmnk+l =
xmnk при xk+1 ³ xmnk.
На втором шаге цикла будет получен минимум первых трех чисел:
xmnk+2 = min (xk+2, min (хk+1, хk)) = Min (хk+2, хk+1, хk).
Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет минимальное значение среди чисел xk , ..., xi
хmni = Min (хk, ..., хi).
Данное утверждение доказывается с помощью математической индукции. На первых двух шагах при i = k + 1, k + 2 оно уже установлено. Покажем, что оно будет выполняться на (i + 1)-м шаге. Действительно, на следующем шаге цикла результатом будет:
xi+1 при хi+1 < xmni = min(xi+1, хmni)
хmni+1 =
хmni при хi+1 ³ хmni = min(xi+1, xmni)
= min (xi+1, Min (хk , ..., хi)) = Min (хk, ..., хi, xi+1).
Что и требовалось показать. Следовательно, в силу принципа математической индукции конечным результатом выполнения рассматриваемого цикла будет значение:
xmnN = Min (xk, ..., хN)
Что и требовалось доказать.
Лемма 2. Для вспомогательного алгоритма
алг «перестановки»
нач { xmn = Min (хk, ..., хN) }
xi¢mn= xk
конечным результатом будет значение хk' = Min (хk, ..., хN).
Доказательство.В силу леммы 1 xmn = Min (xk, ..., хN). А так как в этом алгоритме хk' = xmn, то в итоге получим
хk' = xmn = Min (хk, ..., хN).
Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х1', ..., хN', удовлетворяющая условию х1' £ х2' £ ... £ хN'.
Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты выполнения основного цикла основного алгоритма:
алг «упорядочение чисел»