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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Решенные задания по инфор-ке http://www.cyberforum.ru/cpp-beginners/thread267206.html
Доброго времени суток!Если кому надо есть некоторые решенные задачи (11 штук).Задачи простые, но мало ли что бывает))))))))
C++ Написать функцию itoa (n,s) преобразования целого числа n в стринг s Написать функцию itoa (n,s) преобразования целого числа n в стринг s http://www.cyberforum.ru/cpp-beginners/thread267203.html
Протестировать функции заданий 13 и 14 на наличие в них операторов возврата как с выражением ,так и без него C++
Протестировать функции заданий 13 и 14 на наличие в них операторов возврата как с выражением ,так и без него
Производная скобочек C++
Допустим есть у нас "x(x+1)(x+2)...(x+last-1)" - такая скобочка (где last - понятное дело, число уже не входящее в произведение). Производная такой скобочки равна:...
C++ swith не работает http://www.cyberforum.ru/cpp-beginners/thread267192.html
#include <stdafx.h> #include <iostream> #include <stdlib.h> #include <conio.h> #include <string.h> #include <locale> using namespace std; void zad1() {
C++ WIN API Доброе время суток. Учусь в институте и дали сделать такую хрень: Реализовать приложения Win32API: 1. Окно в центре экрана с фоном цвета трехмерных элементов содержит переключатели, имитирующие... подробнее

Показать сообщение отдельно
alinarh93
Заблокирован

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

30.03.2011, 19:47. Просмотров 1215. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru