Информатика


              

Решение сложных задач - часть 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)-м шаге. Действительно, на следующем шаге цикла результатом будет:

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

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

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

нач

от k = 1 до N - 1 цикл

xmn

:= хk

...............                                                         { xmn = Min (хk, ..., хi) }

х¢k

= xmnN

хmп¢

= хk 

кцикл                                                         { хk' = Min (хk, ..., хN) }

кон                                                                  { х1' £ х2' £ ... £ хk' }




Содержание  Назад  Вперед