Студопедия — Что и требовалось
Студопедия Главная Случайная страница Обратная связь

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

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






Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х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; просмотров: 575. Нарушение авторских прав; Мы поможем в написании вашей работы!



Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Патристика и схоластика как этап в средневековой философии Основной задачей теологии является толкование Священного писания, доказательство существования Бога и формулировка догматов Церкви...

Основные симптомы при заболеваниях органов кровообращения При болезнях органов кровообращения больные могут предъявлять различные жалобы: боли в области сердца и за грудиной, одышка, сердцебиение, перебои в сердце, удушье, отеки, цианоз головная боль, увеличение печени, слабость...

Вопрос 1. Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации К коллективным средствам защиты относятся: вентиляция, отопление, освещение, защита от шума и вибрации...

Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия...

Механизм действия гормонов а) Цитозольный механизм действия гормонов. По цитозольному механизму действуют гормоны 1 группы...

Алгоритм выполнения манипуляции Приемы наружного акушерского исследования. Приемы Леопольда – Левицкого. Цель...

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