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

@~~alinarh93~~ · 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→∞.

@iama · 30.03.2011, 19:48

имхо - с таким во фриланс

@~~alinarh93~~ Заблокирован
		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

@iama 1334 / 985 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	30.03.2011, 19:48	2
	имхо - с таким во фриланс 0

Опции темы