close

Вход

Забыли?

вход по аккаунту

?

Лабораторная работа №11-1

код для вставкиСкачать
Лабораторная работа № 11 "Анализ алгоритмов поиска"
Написать программу, в которой используются четыре метода поиска:
1. Линейный поиск в массиве.
2. Бинарный поиск в заранее отсортированном массиве (использовать любой алгоритм сортировки из Л/Р№10).
3. Поиск по алгоритму грубой силы подстроки в строке.
4. Поиск по алгоритму Бойеера-Мура подстроки в строке.
По скорости сравниваются 1со 2 алгоритмы, а также 3 с 4.
Для сравнения алгоритма 1 и 2 программа должна автоматизировать следующие действия:
1. Задать начальный размер массива (подбирается самостоятельно, например 5тыс элементов или более).
2. Заполнить массив случайным образом целочисленными константами из диапазона [-1000;1000].
3. Выбрать случайное число для поиска.
4. Засечь время T1 поиска в нем по алгоритму 1.
5. Засечь время T2 поиска в нем по алгоритму 2.
6. Зафиксировать результат в одну строчку таблицы со столбцами - N, T1,T2.
7. Увеличить размер массива, например на 10тыс. элементов, и повторить п.2-7, как минимум 10 раз (или более).
В результате получается таблица (выдается на экран) со столбцами N, T1,T2. В ней должно быть как минимум 10 строк.
Далее в отчете построить графики зависимостей Т1(N), Т2(N) по точкам из таблицы.
Графики можно строить вручную, или в EXCEL, или в самой программе, используя руководство к лабораторной работе для построения графиков в консольном приложении (в текстовом режиме). В случае построения графиков программно в ТЕКСТОВОМ РЕЖИМЕ, за это можно получить ДОПОЛНИТЕЛЬНЫЕ 10 баллов.
Сделать в отчете выводы по графикам.
Используя руководство по аппроксимации функций, найти формулы для зависимостей Т1(N), Т2(N) и сделать в отчете выводы, а также дать прогнозы по времени поиска при N→∞.
Для сравнения алгоритма 3 и 4 программа должна автоматизировать следующие действия:
1. Подготовить не менее 10 текстовых файлов разных размеров. 2. Засечь время T1i поиска нескольких шаблонов в очередном файле по алгоритму 3.
3. Засечь время T2i поиска нескольких шаблонов в очередном файле по алгоритму 4.
4. Зафиксировать результатs в таблицt со столбцами - N, T1,T2.
5. Перейти к следующему файлу и повторить п.2-5, как минимум 10 раз (или более).
В результате получается таблица (выдается на экран) со столбцами N, T1,T2. В ней должно быть как минимум 10 строк.
Далее в отчете построить графики зависимостей Т1(N), Т2(N) по точкам из таблицы.
Графики можно строить вручную, или в EXCEL, или в самой программе, используя руководство к лабораторной работе для построения графиков в консольном приложении (в текстовом режиме). В случае построения графиков программно в ТЕКСТОВОМ РЕЖИМЕ, за это можно получить ДОПОЛНИТЕЛЬНЫЕ 10 баллов.
Сделать в отчете выводы по графикам.
Используя руководство по аппроксимации функций, найти формулы для зависимостей Т1(N), Т2(N) и сделать в отчете выводы, а также дать прогнозы по времени поиска при N→∞.
Документ
Категория
Рефераты
Просмотров
11
Размер файла
36 Кб
Теги
работа, лабораторная
1/--страниц
Пожаловаться на содержимое документа