- •1. Основные понятия сортировки и поиска.
- •1.1. Сортировка.
- •1.2. Поиск.
- •2.1. Лабораторная работа № 1. Сортировка методом попарной перестановки (“метод пузырька”).
- •Методические указания.
- •Порядок выполнения работы.
- •Массив чисел (ключей)
- •Содержание отчета.
- •Контрольные вопросы.
- •2.2. Лабораторная работа № 2. Сортировка информационных массивов методом подсчета.
- •Методические указания
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.3. Лабораторная работа № 3. Сортировка информационных массивов методом вставки.
- •Методические указания
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.4. Лабораторная работа № 4. Сортировка информационных массивов методом Шелла.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.5. Лабораторная работа № 5. Последовательный поиск в информационном массиве.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.6. Лабораторная работа № 6. Бинарный поиск в информационном массиве.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •3. Литература.
- •Приложение 5 Бинарный поиск
Порядок выполнения работы.
Ознакомится с общими методическими указаниями и с описаниями данной работы. Ознакомиться по литературе с основными понятиями обработки ИМ, алгоритмами поиска и требованиями к ним
Изучить блок-схему метода последовательного поиска.
Каждому студенту взять из таблицы 2.1. массив из n ключей {K1,K2, … , Kn} и набор значений аргумента поиска Z которые задаются номером варианта.
Провести поиск в заданном массиве вручную (см. пример).
Провести поиск в заданном массиве на ЭВМ.
Содержание отчета.
Краткое изложение целей и задач лабораторной работы, задачи поиска в ИМ и рассматриваемого метода поиска.
Блок-схема алгоритма последовательного поиска.
Результаты поиска вручную.
Результаты поиска на ЭВМ (распечатка с комментариями).
Контрольные вопросы.
Что понимается под обработкой ИМ?
В чем заключаются задача поиска в ИМ?
Что такое удачный и неудачный поиск?
Что такое отношение следования?
Накладывается ли на ИМ требование упорядочивания между его элементами?
Таблица 2.1
№ |
Массив чисел (ключей) |
Ключ поиска |
||||||||||||||
|
К1 |
К2 |
К3 |
К4 |
К5 |
К6 |
К7 |
К8 |
К9 |
К10 |
К11 |
К12 |
К13 |
К14 |
1 |
2 |
1. |
100 |
0 |
-50 |
6000 |
731 |
2 |
7 |
35 |
99543 |
-59 |
71 |
0 |
21 |
10 |
7 |
10 |
2. |
55 |
1 |
357 |
991 |
-777 |
30 |
22 |
1 |
71890 |
-1 |
0 |
9 |
-3 |
20 |
1 |
22 |
3. |
75 |
2 |
43 |
765 |
651 |
2 |
35 |
14 |
54233 |
-28 |
17 |
7 |
19 |
18 |
2 |
35 |
4. |
43 |
5 |
244 |
5935 |
-321 |
12 |
17 |
5 |
35555 |
-41 |
55 |
6 |
13 |
25 |
17 |
5 |
5. |
132 |
7 |
-22 |
785 |
-431 |
7 |
23 |
48 |
83421 |
-91 |
73 |
0 |
15 |
8 |
81 |
23 |
6. |
88 |
3 |
-69 |
435 |
893 |
27 |
1 |
3 |
12495 |
-12 |
38 |
2 |
20 |
17 |
20 |
3 |
7. |
39 |
1 |
-144 |
350 |
-150 |
25 |
28 |
1 |
86901 |
-10 |
36 |
4 |
1 |
11 |
23 |
1 |
8. |
34 |
4 |
450 |
734 |
534 |
13 |
91 |
85 |
12345 |
4 |
67 |
8 |
32 |
9 |
4 |
14 |
9. |
121 |
6 |
752 |
843 |
251 |
6 |
63 |
74 |
19831 |
-19 |
21 |
5 |
-5 |
14 |
6 |
63 |
10. |
44 |
8 |
92 |
453 |
-675 |
89 |
33 |
8 |
85163 |
-84 |
52 |
0 |
-93 |
26 |
52 |
8 |
11. |
62 |
9 |
88 |
354 |
-897 |
19 |
48 |
93 |
63517 |
9 |
81 |
1 |
-67 |
36 |
48 |
97 |
12. |
651 |
0 |
22 |
278 |
-451 |
67 |
83 |
0 |
43273 |
-86 |
74 |
5 |
-87 |
43 |
83 |
0 |
13. |
99 |
5 |
671 |
935 |
431 |
5 |
42 |
78 |
69543 |
-97 |
89 |
6 |
48 |
96 |
42 |
79 |
14. |
257 |
8 |
-23 |
5000 |
-978 |
22 |
34 |
8 |
27825 |
-3 |
62 |
7 |
85 |
63 |
22 |
8 |
15. |
32 |
9 |
144 |
955 |
-1 |
68 |
2 |
89 |
93561 |
9 |
81 |
3 |
22 |
78 |
89 |
15 |
16. |
400 |
7 |
35 |
671 |
-83 |
7 |
64 |
55 |
95672 |
-73 |
45 |
6 |
97 |
28 |
64 |
7 |
17. |
95 |
4 |
68 |
732 |
-45 |
44 |
87 |
69 |
45682 |
4 |
97 |
8 |
76 |
99 |
87 |
4 |
18. |
29 |
-6 |
81 |
-252 |
834 |
-6 |
58 |
72 |
10025 |
-68 |
93 |
1 |
-87 |
13 |
58 |
51 |
19. |
14 |
2 |
19 |
-86 |
238 |
89 |
75 |
63 |
98005 |
2 |
61 |
3 |
-94 |
55 |
19 |
44 |
20. |
88 |
5 |
84 |
-71 |
452 |
5 |
56 |
73 |
89504 |
-64 |
19 |
8 |
-36 |
50 |
73 |
92 |