Требования к работе

Обработка одномерных массивов

Методические указания

к лабораторной работе № 3

Тверь, 2015

Содержание

1. Цель работы.. 3

2. Указание к работе. 3

3. Оформление отчета. 3

4. Требования к работе. 4

5. Теоретический материал. 5

Инициализация массива случайными числами. 5

Измерение времени работы программы.. 6

Сортировка пузырьком. 6

Сортировка выбором. 8

Сортировка вставками. 9

Сортировка подсчетом. 10

Сортировка слиянием. 11

Линейный поиск в массиве. 11

Двоичный поиск в массиве. 12

7. Варианты индивидуальных заданий. 13

Цель работы

Приобретение и закрепление навыков работы с одномерными массивами.

Указание к работе

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

Для выполнения задания необходимо использовать два одномерных массива целых чисел А[M] и В[N]. Размеры М и N вводятся с клавиатуры. Инициализируйте исходные массивы случайными числами, после чего выведите их на экран. Далее отсортируйте массивы с использованием алгоритма, указанного в вашем задании, и снова выведите. Создайте массив С, который содержит элементы, отвечающие условию задания. Выбор необходимых элементов должен производится с помощью алгоритма поиска, указанного в вашем варианте.

В массиве С элементы должны содержаться в одном экземпляре. Вспомогательные массивы использовать запрещается, если в алгоритме сортировки не оговорено обратное.

Б) Сравните время работы программы при следующих размерах исходных массивов: 100, 1000, 5000, 10000, 15000 элементов. Циклы вывода элементов на экран рекомендуется закомментировать.

Оформление отчета

В отчет включить:

· Тема и цель работы;

· Задание на выполнение (общая часть задания и конкретный вариант индивидуального задания);

· Алгоритм программы в виде псевдокода. Части алгоритма, выполняющие инициализацию, вывод, сортировку исходных массивов и поиск в них, целесообразно оформить в виде отдельных подалгоритмов;

· Текст программы с комментариями;

· Результаты выполнения программы (для всех заданных размеров исходных массивов):

o Для минимального количества элементов в исходных массивах (100 элементов) – с распечаткой содержимого всех трех массивов для контроля правильности работы алгоритма;

o Для прочих вариантов количества элементов (1000 и выше) – только данные о времени выполнения программы.

· Результаты сравнения времени выполнения программы при разных размерах массивов. Для наглядности целесообразно построить график изменения времени выполнения при различных размерах массивов.

Требования к работе

1. Приведенное выше содержание отчета достаточно для выполнения задания всех уровней сложности. Для максимальных уровней сложности задания (9 и 10) описание используемого алгоритма сортировки в задании не приводится, его необходимо найти и реализовать самостоятельно.

2. Требования по каждому критерию оценки:

2.1. Точное выполнение полученного варианта задания.

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

2.3. Обратить внимание на аккуратность оформления псевдокода. Следите за уровнями вложенности алгоритмических конструкций и отображайте их соответствующими отступами. Разбиение псевдокода на части (выделение подалгоритмов сортировки и поиска) позволяет уменьшить вложенность и избежать лишних ошибок.

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

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

2.6. Если при выполнении программы при каких-либо исходных данных могут возникнуть ситуации, приводящие к ошибке времени выполнения (например, к выходу индекса за пределы массива), необходимо это отслеживать. Отсутствие соответствующего контроля снижает надежность программы. Можно также добавить контроль корректного ввода размера массивов.

2.7. Основными конструкциями, используемыми в данной программе, являются циклы. Обращайте внимание на соответствие используемых в алгоритме и в программе видов циклов (while, do - while и for).

Не нашли, что искали? Воспользуйтесь поиском: