Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х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' .

Что и требовалось доказать. Следовательно, рассмотренный алго­ритм упорядочения чисел правильный в целом.

Применим теперь данный способ упорядочения для решения задачи сортировки. Рассмотрим следующую задачу. Пусть дана не­которая партия товаров с заданной отпускной ценой, указана цена товаров и известны остатки от их продажи. Требуется подсчитать выручку от продажи и отсортировать товары по их остатку.

Данные о товарах представлены двумя таблицами:

 







Дата добавления: 2014-11-12; просмотров: 228. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.005 сек.) русская версия | украинская версия