Лабораторная работа асд. Лабораторные работы_по_АСД. Дисциплина Алгоритмы и структуры данных Отчёт по лабораторной работе

• Название: Дисциплина Алгоритмы и структуры данных Отчёт по лабораторной работе
• Анкор: Лабораторная работа асд
• Дата: 27.06.2022
• Размер: 3.09 Mb.
• Имя файла: Лабораторные работы_по_АСД.docx
• Тип: Лабораторная работа; #616986
• страница: 9 из 9

Лабораторная работа №8. Рекурсия. Алгоритм быстрой сортировки. Алгоритм сортировки слиянием

Задание

1. 
   Используя рекурсию, составить блок-схемы алгоритмов решения задач, их реализацию в виде программы на языке программирования и скрин экрана с результатом работы программы.
   
2. 
   Выполнить анализ работы алгоритмов при задании различных вариантов исходных данных и описать возможные ограничения по входным данным.
   
3. 
   Составить отчёт по выполненной лабораторной работе.
   

Решение
Задача 1.

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

Все используемые идентификаторы представлены в таблице 50

Таблица 50 – Идентификаторы

Имя переменной		Тип переменной	Пояснение (возможные ограничения по входным данным, назначение)
алгоритм	программа
Исходные данные
n	n	integer	Количество элементов в массиве
A	A	integer[]	Исходный массив
Промежуточные данные
i	i	integer	Переменная цикла
temp	temp	integer	Вспомогательная переменная для хранения элемента массива
start, end	start, end	integer	Текущие границы цикла
sep	sep	integer	Индекс барьерного элемента
Результирующие данные
A	A	integer[]	Массив после сортировки методом Хоара

Блок схема алгоритма решения задачи представлена на рисунке 99.



Рисунок 98. Блок схема алгоритма для задачи 1
Программа на C#:

using System;
namespace lr8_z1

{

class Program

{

static void Main(string[] args)

{

void HoareSort(int[] a, int start, int end)

{

int temp;

if (start >= end) return;
int sep = start;

for (int i = start; i <= end; i++)

{

if (a[i] < a[end])

{

temp = a[sep];

a[sep] = a[i];

a[i] = temp;

sep++;

}

}

temp = a[sep];

a[sep] = a[end];

a[end] = temp;
HoareSort(a, start, sep - 1);

HoareSort(a, sep + 1, end);

}
Console.Write("Введите количество элементов массива: ");

int n = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Введите массив:");

int[] A = new int[n];

for (int i = 0; i < n; i++)

A[i] = Convert.ToInt32(Console.ReadLine());

Console.WriteLine();

HoareSort(A, 0, n - 1);

Console.WriteLine("После сортировки Хоара по неубыванию:");

for (int i = 0; i < n; i++)

Console.Write(A[i] + " ");

Console.ReadKey();

}

}

}
Скриншот результата работы программы представлен на рисунке 100.





Рисунок 99. Скриншот результата работы программы задачи 1.


Задача 2. Сформировать из двух одномерных массивов третий, используя метод слияния.

Все используемые идентификаторы представлены в таблице 51

Таблица 51 – Идентификаторы

Имя переменной		Тип переменной	Пояснение (возможные ограничения по входным данным, назначение)
алгоритм	программа
Исходные данные
n, m	n, m	integer	Количество элементов в массивах
A, B	A, B	integer[]	Исходные массивы
Промежуточные данные
i	i	integer	Переменная цикла
x,y	x,y	integer	Текущие индексы элементов в массивах
Результирующие данные
C	C	integer[]	Массив после слияния

Блок схема алгоритма решения задачи представлена на рисунке 101.



Рисунок 100. Блок схема алгоритма решения задачи 2

Программа на C#:

using System;
namespace lr8_z2

{

class Program

{

static void Main(string[] args)

{
int[] Merge(int[] a, int[] b)

{
int x = 0, y = 0;

int[] c = new int[a.Length + b.Length];

for (int i = 0; i < a.Length + b.Length; i++)

{

if (y < b.Length && x < a.Length)

{

if (a[x] > b[y])

c[i] = b[y++];

else

c[i] = a[x++];

}

else

{

if (y < b.Length)

c[i] = b[y++];

else

c[i] = a[x++];

}

}

return c;

}
Console.Write("Введите количество элементов массива 1: ");

int n = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Введите массив 1:");

int[] A = new int[n];

for (int i = 0; i < n; i++)

A[i] = Convert.ToInt32(Console.ReadLine());

Console.Write("Введите количество элементов массива 2: ");

int m = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Введите массив 2:");

int[] B = new int[m];

for (int i = 0; i < m; i++)

B[i] = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("");

int[] C = new int[n + m];

C = Merge(A, B);

Console.WriteLine("Полученный массив:");

for (int i = 0; i < n + m ; i++)

{

Console.Write(C[i] + " ");

}

Console.ReadKey();
}

}

}
Скриншот результата работы программы представлен на рисунке 102.



Рисунок 101. Скриншот результата работы программы задачи 2.

Задача 3. Отсортировать одномерный массив методом слияния, используя рекурсию.

Все используемые идентификаторы представлены в таблице 52

Таблица 52 – Идентификаторы

Имя переменной		Тип переменной	Пояснение (возможные ограничения по входным данным, назначение)
алгоритм	программа
Исходные данные
n	n	integer	Количество элементов в массивах
A	A	integer[]	Исходный массив
Промежуточные данные
i	i	integer	Переменная цикла
sep	sep	integer	Точка разделения массива
a, b	a, b	integer[]	Массивы после разделения
x,y	x,y	integer	Текущие индексы элементов в массивах
c	c	integer[]	Массив после слияния
Результирующие данные
C	C	integer[]	Отсортированный массив

Блок схема алгоритма решения задачи представлена на рисунке 103.



Рисунок 102. Блок схема алгоритма решения задачи 3
Программа на C#:

using System;
namespace lr8_z3

{

class Program

{

static void Main(string[] args)

{
int[] Merge(int[] a, int[] b)

{
int x = 0, y = 0;

int[] c = new int[a.Length + b.Length];

for (int i = 0; i < a.Length + b.Length; i++)

{

if (y < b.Length && x < a.Length)

{

if (a[x] > b[y])

c[i] = b[y++];

else

c[i] = a[x++];

}

else

{

if (y < b.Length)

c[i] = b[y++];

else

c[i] = a[x++];

}

}

return c;

}

int[] MergeSort(int[] m)

{

if (m.Length == 1)

return m;

int sep = m.Length / 2;

int[] a = new int[sep];

int[] b = new int[m.Length - sep];

for (int i = 0; i < m.Length; i++)

{

if (i < sep)

a[i] = m[i];

else

b[i - sep] = m[i];

}

return Merge(MergeSort(a), MergeSort(b));

}
Console.Write("Введите количество элементов массива: ");

int n = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Введите массив:");

int[] A = new int[n];

for (int i = 0; i < n; i++)

A[i] = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("");

int[] C = new int[n];

C = MergeSort(A);

Console.WriteLine("После сортировки методом слияния:");

for (int i = 0; i < n; i++)

Console.Write(C[i] + " ");

Console.ReadKey();
}

}

}
Скриншот результата работы программы представлен на рисунке 104.





Рисунок 103. Скриншот результата работы программы задачи 3.