МІНІСТЕРСТВО ОСВІТИ І НАУКИ. НАЦІОНАЛЬНИЙ АВІАЦІЙНІЙ УНІВЕРСИТЕТ. Інститут заочного та дистанційного навчання. КУРСОВА РОБОТА. З дисципліни : Інформатика. Виконав студент 2-курсу ІЗДН. Спеціальність : 6.050802. Погорєлов Михайло Геннадійович. Процедура

Стр 1 из 3Следующая ⇒

МІНІСТЕРСТВО ОСВІТИ І НАУКИ

НАЦІОНАЛЬНИЙ АВІАЦІЙНІЙ УНІВЕРСИТЕТ

Інститут заочного та дистанційного навчання

КУРСОВА РОБОТА

З дисципліни : Інформатика

Виконав студент 2-курсу ІЗДН

Спеціальність : 6.050802

“Електронні пристрої та системи”

Погорєлов Михайло Геннадійович

Зал.кн. №18.0504

2014 р.

Зміст

Задание………………………………………………………………………………………………3

Процедура слияния…………………………………………………………………………………3

Сортировка слиянием………………………………………………………………………………4

Лістинг програми……………………………………………………………………………………6

Задание:Ввести массивы А и В. В массив С перенести те четные элементы массива А, левее которых стоят элементы с нечетным значением . Также в массив С перенести элементы В, который по значению ближе всех к (min+max)/2? где min – значение минимального элемента массива В, а max - значение максимального элемента массива В. Массивы А,В и С отсортировать по возрастанию, используя сортировку методом слияния.

Процедура слияния

Допустим, у нас есть два отсортированных массива A и B размерами и соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:

Рис. 1. Пример работы процедуры слияния

Алгоритм слияния формально можно записать следующим образом:

(1)

Для обеспечения стабильности алгоритма сортировки нужно, чтобы в случае равенства элементов тот элемент, что идёт раньше во входном массиве, попадал в результирующий массив в первую очередь. Мы увидим далее, что если два элемента попали в разные массивы (A и B), то тот элемент, что шёл раньше, попадёт в массив A. Следовательно, в случае равенства элемент из массива A должен иметь приоритет. Поэтому в алгоритме стои́т знак вместо < при сравнении элементов.

Недостатком представленного алгоритма является необходимость дописывать оставшийся кусок, из-за чего при дальнейших модификациях алгоритма нам придётся писать много повторяющегося кода. Чтобы этого избежать, будем использовать чуть менее эффективный, но более короткий алгоритм, в котором копирование «хвоста» встроено в основной цикл:

(2)

Время работы процедуры слияния составляет .

Реализация процедуры слияния на языке программирования C++ представлена в листинге 1.

template<class T> void Merge(T const *const A, int const nA,
T const *const B, int const nB,
T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
// и массива B, содержащего nB элементов.
// Результат записать в массив C.

int a(0), b(0); //Номера текущих элементов в массивах A и B

while( a+b < nA+nB ) //Пока остались элементы в массивах
{
if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )
{ //Копирую элемент из массива A
C[a+b] = A[a];
++a;
} else { //Копирую элемент из массива B
C[a+b] = B[b];
++b;
}
}
}

Листинг 1. Компактная (не самая быстрая) реализация процедуры слияния

12 3 Следующая ⇒