Методичні рекомендації щодо виконання лабораторних робіт з дисципліни «організація комп'ютерних мереж» для студентів ХКТК НТУ «ХПІ» спеціальності: 5.05010301 «Розробка програмного забезпечення».
Розроблена викладачем Коломійцем П.Ю.
Розглянута і затверджена на засіданні циклової комісії комп'ютерних та інформаційних дисциплін.
Протокол № від « » 20 р.
Голова комісії _________________ Р.І.Манєва
Заступник директора
з навчальної роботи _______________ І.І.Дідух
ЗМІСТ
Лабораторна робота №14
Лабораторна робота №213
Лабораторна робота №317
ЛАБОРАТОРНАЯ РОБОТА №1
«Подпрограммы»
1. Тема работы: Процедуры и функции.
2. Цель работы: научиться правильно стоить и использовать подпрограммы, на примере разных сортировок.
Теоретический материал
Очень часто в программе встречаются части, которые нужно повторять много раз. И с этим очень хорошо справляются циклы. Но что если одни и те же действия нужно повторять не подряд, а в разные моменты программы? Решить этот вопрос позволяют подпрограммы.
Подпрограммы – это участки кода, имеющие имя и вызываемые из основной программы в любой момент времени. Если подпрограмму не вызывать, она не выполнится никогда.
Подпрограммы бывают двух видов: процедуры и функции. Различие между ними состоит в том, что функции после выполнения возвращают результат (и следовательно их можно приравнивать переменным, выводить на печать и пр.), процедуры же такой возможности не имеют.
Так же подпрограммы имеют параметры. Это переменные, массивы или просто значения, передаваемые в подпрограмму при её вызове. Таким образом, в отличии от цикла, подпрограмма может обрабатывать разные данные при каждом вызове. Это так же даёт дополнительные преимущества при составлении сложного программного кода.
Синтаксис подпрограмм:
Сначала требуется указать тип подпрограммы (в случае процедуры, вместо типа пишется слово void), затем, имя подпрограммы (желательно с большой буквы), затем в скобках перечислить типы параметров и их имена. Дальше, уже в операторских скобках, идёт текст самой подпрограммы. В случае функции, последней её строкой должна быть команда return и затем значение или переменная, либо выражение, которое она возвращает. Важно, чтобы тип возвращаемых данных совпадал с типом, указанным в заголовке подпрограммы.
Пример:
char PodProg (int a, int b, char c)
{
...;
...; // – текст подпрограммы
...;
return 'W'; // в процедурах эта строка
} отсутствует
Важно не забывать, что С++ регистрочувствительный язык, и следовательно при вызове подпрограммы большие и маленькие буквы должны в точности совпадать с тем, как они были указаны при её создании.
Так же важно, чтобы каждая вызываемая подпрограмма была написана выше вызывающей её подпрограммы (в том числе, выше процедурыmain!), однако, если это по какой-либо причине невозможно или неудобно, выйти из ситуации можно повторив заголовок вызываемой процедуры над вызывающей, ограничившись указанием типов параметров, без их названия.
Пример: char PodProg (int, int, char);
Сортировка – это алгоритм для упорядочения элементов в списке (например массиве) по определённому признаку (например, по возрастанию или убыванию).
Существует множество методов сортировки, отличающихся трудностью реализации и эффективностью. Эти два показателя прямо пропорциональны! Т.е. в большинстве случаев, чем сложнее метод сортировки в реализации, тем он эффективнее.
Самый простой метод сортировки – сортировка пузырьком. Он назван так потому, что одно число из массива меняет своё положение до тех пор, пока не займёт своё место, таким образом вызывая ассоциацию со всплыванием.
Алгоритм сортировки пузырьком таков: два соседних числа сравниваются, и если нужно, меняются местами (следует менять числа местами или нет, решается в зависимости от направления сортировки), затем сравниваются следующие два числа (одно из которых участвовало в предыдущем сравнении) и снова меняются местами, если это требуется. Это повторяется, пока сортировка не дойдёт до последнего элемента месива. Тогда она снова переходит к началу и повторяет эти действия до тех пор, пока массив не будет окончательно отсортирован. Усовершенствовать этот процесс можно исключая из сортировки те числа, которые уже заняли свои окончательные места (их количество совпадает с количеством полных проходов по массиву).
Сортировка выбором – немного более сложна в реализации и при этом эффективнее. Её отличие от метода пузырька заключается в том, что сравниваемые числа не сразу меняются местами. Сначала во всём массиве (за исключением уже отсортированных элементов, количество которых совпадает с количеством полных проходов) находится максимальный или минимальный элемент (по выбору программиста), затем он ставиться первым, либо последним в массиве (в зависимости от направления сортировки) среди неотсортированных элементов. Далее он исключается из дальнейшей сортировки и всё повторяется заново.
Сортировка выбором – одна из самых простых и неэффективных, она лишь немного сложнее и эффективнее самого простого метода – сортировки пузырьком.
Алгоритм сортировки выбором:
1. Находим номер элемента с минимальным значением.
2. Меняем местами значения первого сортируемого элемента и элемента с минимальным значением.
3. Повторяем действия 1 и 2, исключив из поиска отсортированные элементы.
Сортировка вставками отличается от всех остальных тем, что для её полного завершения достаточно всего одного прохода. Её словестное описание может звучать довольно запутано и сложно, но на самом деле, это одна из наиболее простых в реализации сортировок, и одна из наименее эффективных. Её суть заключается в том, что сортируемое число выбирается из ещё неотсортированных, а затем вставляется на своё место среди уже отсортированных элементов.
Если писать программу на русском языке, то выглядеть она будет так:
ОТ j=0 ДО N-1
i=j;
ПОКА (i>=0) И (a[i]>a[i+1])
Поменять местами элементы;
Уменьшить i;
Более наглядно (анимировано) это можно увидеть здесь.
Сортировка Шелла, по сути – это усложнённый метод сортировки вставками. Из рассматриваемых методов, он наиболее сложен в реализации, и наиболее эффективен.
Суть сортировки Шелла состоит в том, что изначально сравниваются не соседние элементы, а находящиеся на определённом расстоянии, но их обмен местами происходит точно так же, как в сортировке вставками. При таком подходе одного прохода уже не достаточно и поэтому в каждом новом проходе расстояние между сравниваемыми элементами уменьшается, до тех пор, пока не достигнет расстояния в 1, что будет означать уже полное соответствие сортировке вставками. Не смотря на большее количество проходов, такой метод сортировки на много более эффективен обычного метода вставок, за счёт так называемой предсортировки, достигаемой при сравнении удалённых друг от друга элементов. Обычно, первое расстояние между сравниваемыми элементами берётся в половину длинны массива, и с каждым проходом уменьшается вдвое. Но это не обязательные условия.
