Алг «поиск минимума»

Дата добавления: 2014-11-24 | Просмотров: 1476

Нач

хтп := xk

от 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. Для вспомогательного алгоритма