Что и требовалось
Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х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' } На первом шаге при 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 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности x1' £ x2' £... £ хN'. Что и требовалось доказать. Следовательно, рассмотренный алгоритм упорядочения чисел правильный в целом. Применим теперь данный способ упорядочения для решения задачи сортировки. Рассмотрим следующую задачу. Пусть дана некоторая партия товаров с заданной отпускной ценой, указана цена товаров и известны остатки от их продажи. Требуется подсчитать выручку от продажи и отсортировать товары по их остатку. Данные о товарах представлены двумя таблицами:
|
