Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






 

Результатом лабораторной работы является:

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 с.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.