Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Заблокирован
1

Анализ алгоритмов поиска

30.03.2011, 19:47. Просмотров 1669. Ответов 1
Метки нет (Все метки)

Написать программу, в которой используются четыре метода поиска:
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→∞.

0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.03.2011, 19:47
Ответы с готовыми решениями:

Анализ алгоритмов
почему для этого примера: tmp = a; a = b; b = tmp; О-нотация равна O(1), а не O(3) или для...

Асимптотический анализ алгоритмов
Здравствуйте. Помогите разобраться, что такое асимптотический анализ алгоритмов. Я мало что помню...

Анализ алгоритмов сортировки
Доброго времени суток . На кануне меня попросили реализовать программу для анализа двух алгоритмов...

Анализ сложности алгоритмов в с++
Напишите программы, реализующие алгоритм обменной сортировки методом пузырька и алгоритм сортировки...

1
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 19:48 2
имхо - с таким во фриланс
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.03.2011, 19:48

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Сравнительный анализ алгоритмов сортировки
Помогите пожалуйста реализовать программу для сравнения алгоритмов сортировок. Нужно отдельно...

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

Разработка алгоритмов поиска в массивов [Задача]
Всем привет. Кто поможет написать задачку? Дано натуральное число n. Выяснить, сколько...

Подскажите название алгоритмов поиска и сортировки информации
У меня есть код, но я не знаю какой это метод поиска информации: void DataBase::find(double...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.