Что и требовалось

Кон

Кон

Кесли

Нач

хтп:= xk

imn:= k

от i = k + 1 до N цикл

если x_i < хтп то

хтп:= x_i

imn:= i

кцикл { xmn = Min (х_k,..., х₁) }

конечным результатом вычислений будет значение

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).

Доказательство. В силу леммы 1 xmn = Min (x_k,..., х_N). А так как в этом алгоритме х_k' = xmn, то в итоге получим

х_k' = xmn = Min (х_k,..., х_N).

Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х₁',..., х_N', удовлет­воряющая условию х₁' £ х₂' £... £ х_N'.

Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты выполнения основного цикла основного алгоритма:

алг «упорядочение чисел»

Дата добавления: 2014-11-25