Информатика


              

На втором шаге второй элемент


На первом шаге при k = 1 первый элемент последовательности
х1' = Min (x1, х2, ..., хN),
На втором шаге второй элемент последовательности
x2' = Min (х2, ..., хN).
В силу свойств минимума последовательности чисел будем иметь
х1' = Min(x1, x2, ..., хN) = min (x1, Min (х2, ..., хN) £ (Min (х2, ..., хN) = x2'.
Таким образом, при k = 2 результатом станут значения х1' и x2', такие что
х1' £ x2'
На третьем шаге выполнения основного цикла результатом станет
х3 = Мin(х3, ..., хN).
Опять же в силу свойств минимума последовательности имеем
х2' = Min (х2, х3, ..., хN) = min (x2, Min (x3, ..., хN)) £ Min (x3, ..., хN) = x2'.
Таким образом, после третьего шага при k = 3 первые три значе­ния последовательности х1', x2', x3' будут удовлетворять условию
х1'£ x2'£ x3'
Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-м шаге выполнения основного цикла первые k членов последовательности х1', x2', .... хk' будут удов­летворять условию
х1'£ x2'£  … £ xk'.
Данное предположение доказывается с помощью математической индукции. На начальных шагах при k == 2 и k = 3 оно уже показано. Покажем, что оно будет выполнено на (k + 1)-м шаге, если это усло­вие выполнено на k-м. шаге.
В силу Леммы 2 на k-м и (k + 1)-м шагах выполнения основного цикла промежуточными результатами будут
хk'   = Min(xk, xk+1, ..., хN),
хk+1' = Min (xk+1, ..., хN).
В силу свойств минимума последовательности чисел имеем
хk' = Min(xk, xk+1, ..., хN) = min (хk, Min (хk+1, ...,хN)) £ Min (xk+1, ..., хN) = хk+1'.
Таким образом, хk £ xk+1 и в силу индуктивного предположения получаем, что
x1' £ х2' £ ... £ хk' £ xk+'1.
Что и требовалось доказать.
Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу Леммы 2 результатом будет значение
xN-'1 = Min (xN-1, xN) £
хN'.
Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности

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