Постановка задач



бет1/8
Дата07.04.2023
өлшемі0,65 Mb.
#80314
  1   2   3   4   5   6   7   8
Байланысты:
KURSOVAYa YaZYKI 2




Содержание




Аннотация

4

1

Постановка задач

5

2

Метод решения

6

2.1

Методы поиска

6

2.1.1

Линейный поиск

6

2.1.2

Двоичный поиск

7

2.2

Методы сортировок

9

2.2.1

Сортировка Шелла

9

2.2.2

Сортировка методом дерева

13

3

Алгоритмы реализации

16

3.1

Алгоритм вычисления для процедуры form

16

3.2

Алгоритм вычисления для процедуры form_random

16

3.3

Алгоритм вычисления для процедуры print

17

3.4

Алгоритм вычисления для процедуры line

17

3.5

Алгоритм вычисления для процедуры binary_search

18

3.6

Алгоритм вычисления для процедуры сортировки Shella

18

3.7

Алгоритм выполнения для процедуры Tree_Sort

19

4

Руководство по пользованию программой

20

4.1

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

20

4.2

Руководство программиста

21

4.3

Область и условия применения программы

22

5

Анализ результатов

23

5.1

Анализ результатов поиска

23

5.2

Анализ результатов сортировок

26




Заключение

29




Список литературы

30




Приложения

31




Приложение А. Идентификаторы программы

32




Приложение Б. Листинг программы

33




Приложение В. Результаты программы

44




Приложение Г. Блок-схемы программы

60

Аннотация
В курсовом проекте рассматривается нечисленная обработка данных:
сортировка и поиск. Выполняется сортировка целочисленных массивов методом Шелла и дерева. Реализован поиск заданных значений методами двоичного и линейного поиска. Разработаны алгоритмы названных методов. Программа реализована на языке Pascal АВС.


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

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

  1. сформировать входной набор данных длиной n=16,128,512, 1024 элементов. При n≤16 предусмотреть формирование набора путем ввода значений с клавиатуры, в остальных случаях датчиком случайных чисел;

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

  3. выполнить тестирование программы;

  4. выполнить оценку сортировки и поиска по числу сравнений в зависимости от размера массива;

Требования к программе:



  1. основные алгоритмы оформить в виде подпрограмм;

  2. полученные данные записать в текстовый файл;

  3. программа должна быть самодокументированной, т.е. содержать комментарии основных параметров и действий.

2 Методы решения задач
2.1 Методы поиска
2.1.1. Линейный поиск
Для таблицы, в которой величины не упорядочены (путем сортировки или каким-либо другим способом), единственный путь для поиска данного ключевого слова состоит в сравнении каждого элемента таблицы с данным ключевым словом. Этот метод называется линейным поиском.
Описанный цикл будет сравнивать ключевое слово с каждым последовательным элементом таблицы. Когда происходит совпадение ключевого слова с элементом таблицы, цикл просмотра заканчивается.
При линейном поиске иногда просматривается половина, а то и больше элементов исходного массива. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива. В среднем время поиска составляет:

где N – длина массива. Этот метод удобен и прост для массивов с меньшей длиной. Для массивов большей длины это метод вызывает затруднения, так как время поиска будет очень медленным.
Рассмотрим линейный поиск на примере массива из 16 элементов. Пусть дан неупорядоченный массив А: 14 22 11 15 20 25 31 74 85 92 47 58 10 1 7 44 и необходимо найти элемент х со значением 10.

Таблица 1.Линейный поиск



Порядковый номер

Сравнение

Количество шагов

1

14 ≠ 10

1

2

22 ≠ 10

2

3

11 ≠ 10

3

4

15 ≠ 10

4

5

20 ≠ 10

5

6

25 ≠ 10

6

7

31≠ 10

7

8

74 ≠ 10

8

9

85 ≠ 10

9

10

92 ≠ 10

10

11

47 ≠ 10

11

12

58 ≠ 10

12

13

10 = 10

13

14

1




15

7




16

44



Из таблицы 1 видно, что для нахождения элемента х=10 пришлось выполнить 13 сравнений. Если бы элемента 10 не оказалось под номером 13, то поиск выполнялся бы до его нахождения, либо до окончания массива. (1, с. 97)


2.1.2 Двоичный (бинарный) поиск
Поиск начинается с середины массива, затем сравниваем ключевое число с элементом, находящимся в середине таблицы. Ключевое число может быть равно, больше или меньше проверяемой величины. Дальнейшие действия для каждого из элементов зависит от результата сравнения:

  1. Если ключ и элемент массива равны, то элемент найден. Поиск завершается.

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

  3. Если меньше, использовать нижнюю половину массива

Этот метод фактически делит массив пополам при каждой проверке, систематически локализуя искомую величину. Поиск является безуспешным, если длина последнего массива для поиска уменьшается до 1, а искомая величина не найдена. [1, стр99]
Принцип бинарного поиска основан на том, что поиск начинается с середины массива, затем сравниваем ключевое слово с элементом, находящимся в середине массива. Ключевое слово может быть равно, больше или меньше проверяемой величины. Если оно равно, то элемент найден. Если элемент больше, то необходимо взять верхнюю половину данного массива в качестве новой области для поиска. Если же меньше, то необходимо использовать нижнюю половину массива
Этот метод фактически делит массив пополам при каждой проверке. Поиск является безуспешным, если длина последнего массива для поиска уменьшается до1, а искомый элемент не найден.
Введем условную единицу времени, равную времени, затраченному на сравнение двух элементов. Следовательно, среднее время поиска элемента в массиве равно
Tср = [время проверки] * log2N,
Где N – количество элементов в массиве. [2, стр201]
Рассмотрим двоичный поиск на тех же (упорядоченных) элементах, что и в линейном поиске:
1 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92
Необходимо найти элемент х=10
Элемент был найден на шаге 3:
Шаг 1:найдем номер среднего элемента =8, так как 101 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92
Шаг 2: рассматриваем элементы, начиная с первого; находим индекс среднего элемента этой части =4. 101 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92
Шаг 3: рассматриваем пять элементов, значение =2.
10>а [2],следовательно, далее рассматриваем элементы, индексы которых больше a[2].
1 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92
Шаг 4: рассматриваем три элемента, значение =3.
1 0=а[3]. Элемент найден, его порядковый номер 3.
1 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92

2.2.2. Метод сортировки по дереву


Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива(списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например из файла, сокета или консоли).
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память. [https://ru.wikipedia.org/wiki]
Рассмотрим сортировку Шелла по возрастанию на тех же (упорядоченных) элементах, что в линейном и двоичном поисках:
1 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92
Ш аг 1: обозначим элемент а[1] корнем дерева.
1

Ш аг 2: а[1]< а[2]. Переносим элемент а[2] вправо.


1
7
Ш аг 3: Так как а[1], а[2]< а[3], переносим элемент а[3] вправо.
1
7
10
Ш аг 4: Так как элементы а[1], а[2], а[3] < а[4], переносим элемент а[4] вправо.
1
7
10
11
Шаг 5: Так как элементы а[1], а[2], а[3], а[4] < а[5], переносим элемент а[5] вправо.
1
7
10
11
14
Шаг 6: Так как элементы а[1], а[2], а[3], а[4], а[5] < а[6], переносим элемент а[6] вправо.

1
7
10
11
14
15
Шаг 6: Так как элементы а[1], а[2], а[3], а[4], а[5], а[6] < а[7], переносим элемент а[7] вправо.
1
7
10
11
14
15
20
Шаг 6: Если сравнить таким алгоритмом до а[16], можно понять, что все элементы будут находиться справа от корня дерева.
Шаг 7: В сортировке методом дерева счет начинается с самого левого элемента. Так как слева элементы отсутствуют, массив сортируется, начиная с корня, то есть с 1.
Массив отсортирован методом дерева:1 7 10 11 14 15 20 22 25 31 44 47 58 74 85 92

3 Алгоритмы реализации


При рассмотрении задачи, ее выполнение было разделено на несколько этапов. Формулировка задачи включает следующие этапы:

  1. Формирование массива:

  • Путем ввода элементов с клавиатуры для массивов, включающих 16 или меньше элементов;

  • С помощью датчика случайных чисел для массивов, включающих 17 или больше элементов;

  1. Вывод содержимого исходной матрицы на экран и в текстовый файл;

  2. Поиск заданного элемента в неупорядоченном массиве:

  • Линейный поиск;

  • Двоичный поиск;

  1. Сортировка элементов массива методом Шелла;

  2. Сортировка элементом массива методом дерева.

Схемы алгоритмов приведены в приложении Г, текст программы в приложении Б.
3.1 Алгоритм вычисления для процедуры form.
Формирование массива с помощью ввода элементов с клавиатуры осуществляет процедура form.

  1. Для i от 1 до n выполнять:

1.1 Вывод ‘Введите i-й элемент массива’;
1.2 Ввод i-го элемента массива, a[i];
2. Закончить.

3.2 Алгоритм вычисления для процедуры form_random.


Формирование массива с помощью датчика случайных чисел осуществляет процедура form_random.

  1. Вызов процедуры randomize для включения генератора случайных чисел;

  2. Для i от 1 до n выполнять:

2.1Задавать значение каждого элемента массива как результат функции random(999);
3. Закончить.

3.3 Алгоритм вычисления для процедуры print.


Вывод на экран содержимого массива осуществляет процедура print.

  1. Для i от 1 до n выполнять:

1.1 Если размерность массива меньше 20, n<=20 тогда выполнять:
1.2 Еслиi делится на 5 без остатка то печатать элемент массива с переходом на новую строку иначе на той же строке, иначе i делится на 10 то печатать элемент массива с переходом на новую строку иначе на той же строке;

  1. Закончить.

3.3 Алгоритм вычисления для процедуры line:


Линейный поиск искомого элемента в массиве осуществляет процедура linei.

  1. Открыть текстовый файл для записи;

  2. Установить k:=0{переменная для присвоения индекса элемента};

  3. Ввод элемента, необходимого найти;

  4. Установить h:=0 {начальное количество шагов при поиске}; признак успешности pr:=false{элемент не найден};i:=1; {начальный индекс элемента}

  5. Пока(i<=n) и (pr=false) выполнять:

5.1Если a[i]=x тогда выполнять:
5.1.1 Присвоить индекс элемента, k:=i;pr:=true;{элемент найден}
5.2 Увеличить количество шага при поиске на 1, h:=h+1;

  1. Если pr=true тогда вывод ‘Элемента x обнаружен. Порядковый номер элемента - k’,иначе вывод ‘Элемент отсутствует в массиве’;

  2. Закончить.

3.5 Алгоритм вычисления для процедуры binary_search.
Двоичный поиск элемента в массиве осуществляет процедур аbinary_search.

  1. Необходимого найти ввод элемента;

  2. Установить нижнюю и верхнюю границы массива, l:=1; r:=n; h:=0;{начальное значение количества шагов при поиске}

  3. Установить признак успешности, s:= ‘NO’ {элемент не найден};

  4. Пока (l<=r) и (s= ‘NO’) выполнять

4.1 Вычислить значение среднего индекса массива m:=(l+r) div 2;
4.2Если xa[m], то установить l:=m+1 иначе s:= ‘YES’;
5. Если s= ‘YES’ то вывод ‘Элемент найден. Позиция элемента "x" –m’ иначе вывод ‘Элемент не найден’;
6. Закончить.

3.6 Алгоритм вычисления для процедуры обменной сортировки.


Сортировку по методом пузырька в массиве осуществляет процедура пузырька .
1. Установить начальные значения переменных, SP=0; KP=0 {количество перестановок};
2. Переменной d присвоить целочисленную часть числа k/2 с помощью функции trunc, где k- размерность массива;
3. Пока d<>0 (расстояние) выполнять:
3.1 Пока массив не упорядочен выполнять:
3.1.1 Для i=1 до k-d выполнять:
3.1.1.1 Если t[i]>t[i+d] тогда:
3.1.1.1.1 Если элемент стоящиий от i-го на расстояние d больше меняем их местами, MM:=T[i]; T[i]:=T[i+d]; T[i+d]:=MM;
3.1.1.1.2 Увеличить количество перестановок на 1, kp:=kp+1;
3.1.1.2 Расстоянию присваиваем значение два раза меньше предыдущего, sp:=sp+k-d; d:=trunc(d/2);
3.7 Алгоритм выполнения для процедуры Tree_Sort.
Сортировку методом дерева в массиве осуществляет процедура Tree_Sor.
Алгоритм выполнения для процедуры сортировки методом дерева.

  1. Установить начальные значения переменой m=0 {количество перестановок};

  2. Для i=1 до n, для j=1 до 5 выполнять;

  3. Расстоянию b1 присваиваем b, а значениям I, k присваиваем 1, 0 соответсвенно;

  4. Если b[i,3]<>0, тогда:

    1. i присваиваем b[i,3;

  5. Увеличить количество перестановок на 1, m: = m+1;

    1. Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];

    2. Увеличить k на 1, k:=k+1;

    3. Присваиваем b1[k,1]:=b[i,1] и b1[k,2]:=b[i,2];

    4. Если b[i,4]<>0, тогда i присваиваем b[i,4];

  6. Увеличить количество перестановок на 1, m: = m+1;

    1. Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];

    2. Присваиваем j:=i и i:=b[i,5];

    3. Если i<>0 и если b[i,1]> b[j,1], тогда goto l2 else goto l3;

    4. Увеличить количество перестановок на 1, m: = m+1;

    5. Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];

4 Руководство по пользованию программой


4.1 Руководство пользователя
Назначение программы:
Программа Aigerim предназначена для сортировки и поиска элементов массива методами сортировка подсчетом и линейный вставка.
Входные параметры:
n –длина массива;
x –элемент для поиска.
Выходные параметры:
m -позиция элемента;
h -количество шагов при поиске;
c -среднее время поиска при линейном поиске;
k -порядковый номер элемента;
m -количество перестановок.
Запуск программы осуществляется открытием исполняемого файла Aigerim.exe.
Вначале необходимо ввести количество элементов массива, с которым программа будет работать. Если n>16, то ввод будет автоматическим(массив будет сформирован из случайных чисел). Дальнейшая работа определяется сообщениями программы:

  • На окне вывода появится сообщение «Исходный массив» и будет распечатан неупорядоченный массив А;

  • На окне вывода появится сообщение «Отсортированный методом пузырька:». После будет распечатан упорядоченный массив, полученный методом пузырька;

  • На окне вывод появится сообщение «Отсортированный методом дерева:». После будет распечатан упорядоченный массив, полученный методом дерева;

  • На окне вывода появится сообщения «Линейный поиск элемента» и «Введите элемент, который хотите найти -». После информация об искомом элементе.

  • На окне вывод появится сообщение «Для завершения поиска введите слово "end", иначе нажмите "enter"»;

  • На окне вывода появится сообщения «Двоичный поиск элемента» и «Введите элемент, который хотите найти -». После информация об искомом элементе.

  • На окне вывод появится сообщение «Для завершения поиска введите слово "end", иначе нажмите "enter"»;

4.2 Руководство программиста


Программа project состоит из основного блока и семи процедур:

  1. Процедура form – предназначена для формирования элементов массива с помощью ввода с клавиатуры. Вызов процедуры имеет следующий вид: form(A,n), где А – исходный массив, n – количество элементов.

  2. Процедура form_random – предназначена для формирования элементов массива, задавая значение каждого элемента результатом случайной функции Random(R). Вызов процедуры имеет следующий вид: form_random(A,n), где А – исходный массив, n – количество элементов.

  3. Процедура print – предназначена для печати элементов массива на каждую строку по 5 элементов, если количество элементов массива меньше 20, иначе по 10 элементов. Вызов процедуры осуществляется следующим образом: print(A), где А – исходный массив.

  4. Процедура linei – предназначена для линейного поиска искомого элемента. Вызов процедуры осуществляется следующим образом: linei(A,x), где А – исходный массив,x- элемент для поиска.

  5. Процедура binar_search – предназначена для двоичного поиска искомого элемента. Вызов процедуры осуществляется следующим образом: binar_search (A,x), где А – исходный массив, x- элемент для поиска.

  6. Процедура обменная сортировка – предназначена, чтобы привести массив к упорядоченному виду методом Шелла. Вызов процедуры осуществляется следующим образом: Shella (T,K,KP), где T – исходный массив, 1,n – индексы массива, h- количество перестановок при поиске.

  7. Процедура Tree_Sort – предназначена, чтобы привести массив к упорядоченному виду сортировкой методом дерева. Вызов процедуры осуществляется следующим образом: Tree_Sort (a, n, b), где a – исходный массив, m – количество перестановок при поиске.

5 Анализ результатов


5.1 Анализ результатов поиска
Для проверки корректности программы линейного поиска выполнено тестирование программы на 32 тестовых примерах (4 примеров для каждого заданного размера массива). Результаты тестирования приведены в таблице 1. В таблице 2 показано среднее теоретическое время линейного поиска в зависимости от размера массива. Среднее теоретическое время получено по формуле n/2, где n-размерность массива.
Таблица1. Среднее время линейного поиска (практическое)

Размерность массив

16

128

512

1024

В начале

1

1

1

1

В середине

5

75

316

141

В середине

7

74

415

550

В конце

15

127

512

1024

Нет в массиве

16

128

512

1024

Нет в массиве

16

128

512

1024

В конце

16

128

511

1023

В середине

8

82

434

53

Среднее время поиска

10,25

92,88

401.63



605,00

Таблица 2. Среднее время линейного поиска (теоретическое)



Размерность массива

16

128

512

1024

Среднее время поиска

8

64

256

512

По данным, представленным в таблицах 1 и 2,построен график зависимости времени поиска от числа элементов в массиве (рис. 4).



Рисунок 4 – График линейного поиска
Как видно из графика в целом сохраняется линейная зависимость времени поиска (числа сравнении) от размерности массива. Важно отметить, что при размерностях массива n=16 и n=128 происходит искажение графика. Это можно объяснить автоматически выбранным в Excelмасштабом по оси Х. Для более точной оценки эффективности метода линейного поиска необходимо выполнить больше практических реализаций проверок.
Для проверки корректности программы двоичного поиска выполнено тестирование программы на 16 тестовых примерах (4 примеров для каждого заданного размера массива). Результаты тестирования приведены в таблице 3. В таблице 4 показано среднее теоретическое время двоичного поиска от размера массива, вычисленное по формуле , где n-размерность массива.
Таблица 3. Среднее время двоичного поиска (практическое)

Размерность массив

16

128

512

1024

В середине

5

6

7

8

В начале

3

7

9

10

В конце

5

8

10

11

Нет в массиве

5

8

10

11

Среднее время поиска

4,5

7,25

9,00

9,5

Таблица 4. Среднее время двоичного поиска (теоретическое)



Размерность массива

16

128

512

1024

Время поиска

4

7

9

10

По данным, представленные в таблицах 3 и 4 нарисуем график зависимости времени поиска от числа элементов в массиве (рис. 5).


Рисунок 5 – График двоичного поиска
При двоичном поиске график сохраняет логарифмическую зависимость, вычисленную по формуле (рисунок 5).Как и проиллюстрировано, значения практического времени поиска близки к теоретическим вычислениям, что и доказывает корректность реализации поиска в программе.
5.2 Анализ методов сортировок
Результаты сортировки с деревом представлены в виде таблицы. Среднее теоретическое время сортировки вычислялось по формуле (таблица 6). Результаты оценки метода сортировки путем реализации программы представлены в таблице 5.
Таблица 5 Среднее время обменной сортировки

Размерность массива

16

128

512

1024

Перестановки

49

769

4097

9217

Таблица 6 Среднее время сортировки деревом



Размерность массива

16

128

512

1024

Перестановки

64

896

4608

10240

По данным, представленным в таблицах 5 и 6,построен график зависимости времени поиска от числа элементов в массиве (рис. 6).



Рисунок 6 - Оценка эффективности сортировки методом пузырька (практическая и теоретическая).

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


Результаты сортировки методом дерева с практическими вычислениями представлены в виде таблицы 7. Среднее теоретическое время сортировки данным методом вычислялось по формуле (таблица 8).

Таблица 7 Среднее время сортировки методом дерева (практическое)



Размерность массива

16

128

512

1024

Перестановки

18

130

514

1026

Таблица 8 Среднее время обменной сортировки методом дерева (теоретическое)



Размерность массива

16

128

512

1024

Перестановки

64

896

4608

10240

По данным, представленным в таблицах 7 и 8,построен график зависимости времени поиска от числа элементов в массиве:


Рисунок 7 – График метода обменной сортировки с разделением


В ходе оценки эффективности методов сортировок, выяснилось, что при использовании обоих методов, упорядочение массива практически выполняется за меньшее время по сравнению с теоретическими оценками.
Заключение

В ходе курсового проектирования выполнено следующее:



  • Разработаны алгоритмы сортировок (Шелла и деревом) и поисков (линейного и двоичного)

  • Выполнена реализация разработанных алгоритмов в среде ABCPascal

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

  • Разработаны схемы алгоритмов

  • Выполнены тестирование и отладка программы для одномерного целочисленного массива с числом элементов N=16,128,512,1024.

  • Выполнен анализ результата работыпрограммы (оценена эффективность программы в зависимости от объема обрабатываемых данных)

  • Построены графики зависимости времени от количества элементов сортировок и поисков

  • Проведенный анализ показал, что при поиске для малых N нужно использовать линейный поиск, а для больших N – двоичный.

  • В ходе исследования было выявлено, что сортировка методом дерева является более эффективной, чем метод Шелла, однако занимает больше памяти.

Список используемой литературы


1 Донован Дж. Системное программирование. М.: Мир,1975, с.540
2 Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. М.: «Вильямс», 2007, с. 824.
3 Лорин Г. Сортировка и система сортировки. –М.: Наука,1978 г;
4 Колдаев В,Л. Структуры и алгоритмы обработки данных. М.: РИОР-ИНФРА-М, 2014, с. 296.
5 Конспект по дисциплине: «Языки и методы программирование».



Достарыңызбен бөлісу:
  1   2   3   4   5   6   7   8




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет