Министерство образования и науки, молодёжи и спорта Украины

Национальный аэрокосмический университет им. Н.Е.Жуковского

«Харьковский авиационный институт»

Пояснительная записка

к домашнему заданию

по курсу «Дискретная математика»

студента 126 группы

Кастриной А.М.

проверил доц. каф. 105

Бабак И.Н.

Харьков, 2011

СОДЕРЖАНИЕ

1.Постановка задачи…....................................................................................3

2.Теоретическая часть.....................................................................................4

3.Инструкция программиста..........................................................................5

4.Руководство пользователя...........................................................................6

5.Выводы………...............................................................................................7

Список использованных источников

1.Постановка задачи

Разработать программу сортировки последовательных чисел естественным слиянием.

2.Теоретическая часть

Сортировка слиянием означает объединение двух (или более)

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

1. Последовательность a разбивается на две половины b и c.

2. Последовательности b и c сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя a, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четвёрки.

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

В качестве примера рассмотрим последовательность

13 56 10 37 96 15 09 63

На первом шаге разбиение даёт последовательности

13 56 10 37

96 15 09 63

Слияние отдельных компонент в упорядоченные пары даёт

13 96 ’ 56 15 ’ 10 09 ’ 37 63

Новое разбиение пополам и слияние упорядоченных пар дают

09 10 13 96 ’ 15 37 56 63

Третье разбиение и слияние приводят, наконец, к нужному результату:

09 10 13 15 37 56 63 96

Данная программа предназначена для сортировки последовательных

чисел методом простого слияния. Данные вводятся пользователем с клавиатуры.

Входной информацией является массив, который программа будет сортировать.

Выходной информацией является отсортированный методом простого слияния массив.

3.Инструкция программиста

Данная программа написана на языке TurboPascal. Программа используется в учебных целях, поэтому ее область применения очень ограничена.

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

в диапазоне от 0 до 100. Далее на экран выводятся исходный массив и отсортированный.

Программа использует одну процедуру:

Procedure MergeSort (Var m:mas; n:integer) – предназначена для сортировки элементов массива методом простого слияния.

4.Руководство пользователя

Для запуска программы необходимо наличие файла с именем DZ_DISCR.EXE.

При запуске программы появится диалоговое окно, в котором пользователю с клавиатуры нужно ввести количество элементов массива, затем нажать клавишу «Enter».

После нажатия «Enter» пользователь увидит две строки, в первой строке будет исходный массив, а во второй – сортировка этого массива методом простого слияния.

Для завершения работы программы следует нажать клавишу «Enter».

5.Выводы

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

Список использованных источников

1. Вирт Н. Алгоритмы+структуры данных=программы. – М.: Мир, 1985. – 406 с., ил.

Поиск по сайту: