Информатика
Решение сложных задач - часть 3
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)-м шаге. Действительно, на следующем шаге цикла результатом будет:
при х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'.
Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты выполнения основного цикла основного алгоритма:
алг «упорядочение чисел»
нач
от k = 1 до N - 1 цикл
xmn
:= хk
............... { xmn = Min (хk, ..., хi) }
х¢k
= xmnN
хmп¢
= хk
кцикл { хk' = Min (хk, ..., хN) }
кон { х1' £ х2' £ ... £ хk' }