Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
alinarh93
Заблокирован
#1

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

30.03.2011, 19:47. Просмотров 1225. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2011, 19:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Анализ алгоритмов поиска (C++):

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

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

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

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

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

Подскажите название алгоритмов поиска и сортировки информации - C++
У меня есть код, но я не знаю какой это метод поиска информации: void DataBase::find(double price) { int cnt =...

1
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 19:48 #2
имхо - с таким во фриланс
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2011, 19:48
Привет! Вот еще темы с ответами:

Разработать программу для сравнительного графического анализа алгоритмов сортировки и поиска - C++
Разработать программу для сравнительного графического анализа алгоритмов сортировки и поиска;Задача разработчика сгенерировать массив, над...

С++/алгоритм/Тема:"Анализ производительности алгоритмов" - C++
Преобразовать одномерный массив,состоящий из n целых элементов,таким образом,чтобы сначала располагались все положительные элементы,а потом...

Поиска в записанном ранее файле по фамилии или по группе с выбором параметра поиска - C++
Нужно написать код для поиска в записанном ранее файле по фамилии или по группе с выбором параметра поиска. Помогите пожайлуйста, потому...

Нужно отредактировать код поиска в некоторых папках. Добавить функцию поиска в архивах - C++
Нашёл одну программку, работает отлично, но вот не идёт поиск в таких местах как С:\users или C:\Windows Как это исправить?(желательно...


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

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

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