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

Алг «перестановки»

нач { 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' }

На первом шаге при 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' .

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)