Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рекомендации по проведению аналитического исследования и требования к оформлению результатов работы
|
|
Результатом лабораторной работы является:
1. Компьютерная программа, разработанная на языке программирования C\C++.
2. Отчет по лабораторной работе, содержащий следующие разделы:
· Титульный лист.
· Содержание.
· Задание.
· Текст кода основных процедур и функций программы.
· Пример работы программы.
· Таблицу экспериментальных данных.
· Графики исследуемых зависимостей.
· Выводы и заключения.
С целью определения зависимости числа сравнений и перестановок от длины массива для различных методов сортировки необходимо с помощью разработанной программы провести серию экспериментов. Для каждого метода требуется зафиксировать длину массива и выполнить операцию сортировки 3, 5 или 7 раз. После выполнения каждой операции сортировки записываются значения счетчиков сравнений и перестановок. Далее необходимо многократно повторить эти действия, изменяя длину массива.
Для автоматизации и упрощения процесса проведения эксперимента предлагается организовать в программе глобальный цикл, на каждом шаге которого изменятся длина массива и выполняется несколько операций сортировки. Значения счетчиков при этом после каждой операции сортировки выводятся в файл. Полученный файл импортировать в табличный редактор для дальнейшей обработки.
Результаты экспериментов оформляются в виде таблицы и включаются в отчет по работе.
| Длинна массива | ... | ... | |||||||||
| Метод | № эксперимента | Срав-ия | Пер-ки | Срав-ия | Пер-ки | Срав-ия | Пер-ки | Срав-ия | Пер-ки | Срав-ия | Пер-ки |
| Простая обменная сортировка | 100 | 23 | … | ... | … | ... | … | ... | … | ... | |
| 100 | 62 | … | … | … | … | … | … | … | … | ||
| 100 | 45 | … | … | … | … | … | … | … | … | ||
| Метод Шелла | 87 | 44 | … | … | … | … | … | … | … | … | |
| 76 | 65 | … | … | … | … | … | … | … | … | ||
| 69 | 21 | … | … | … | … | … | … | … | … | ||
| Быстрая соритровка | 45 | 13 | … | … | … | … | … | … | … | … | |
| 65 | 56 | … | … | … | … | … | … | … | … | ||
| 68 | 23 | … | … | … | … | … | … | … | … |
Таблица 1. Пример оформления таблицы экспериментальных данных (Таблица зависимостей числа сравнений и перестановок от длины сортируемого массива)
На основе полученных данных, по средним значениям точек, требуется построить кривые зависимости числа сравнений и перестановок от длины массива.
Кривые строятся на двух графиках. Первый график должен содержать три (по одной на каждый исследуемый метод) кривые зависимостей числа сравнений, второй график – три кривые зависимостей числа перестановок, соответственно.
По характеру построенных кривых необходимо определить, какими известными математическими функциями их можно оценить асимптотически – логарифм, полином, показательная функция, и т.д. Рассуждения и оценки необходимо включить в раздел «Выводы и заключения» отчета по работе.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. Керниган Б., Ритчи Д. Язык программирования Си. – СПб.: Невский диалект, 2000. – 352 с.
2. Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. – М.: Вильямс, 2008 г. – 824 с.
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2004. – 960 с.