Разработка алгоритма исчерпывающего поиска
Автор: Ольга Ольга • Октябрь 23, 2023 • Лабораторная работа • 1,607 Слов (7 Страниц) • 56 Просмотры
ГУАП
КАФЕДРА № 53
ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ _____________________
ПРЕПОДАВАТЕЛЬ
Ассистент | ||||
должность, уч. степень, звание | подпись, дата | инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ № 4 РАЗРАБОТКА АЛГОРИТМА ИСЧЕРПЫВАЮЩЕГО ПОИСКА |
по курсу: ОСНОВЫ ПРОГРАММИРОВАНИЯ |
РАБОТУ ВЫПОЛНИЛ(А)
СТУДЕНТ ГР. № | 2222 | В.А. Трофимова | |||
подпись, дата | инициалы, фамилия |
2022
ОГЛАВЛЕНИЕ
Постановка задачи 3
Индивидуальное задание 4
Описание переменных 4
Схема алгоритма решения 5
Листинг программы 6
Результат 8
Результаты измерения времени работы 9
Заключение 10
ПОСТАНОВКА ЗАДАЧИ
Реализовать алгоритм на языке C/С++, выполняющий поставленную задачу (АЛГОРИТМ ДОЛЖЕН БЫТЬ РЕАЛИЗОВАН ПУТЕМ ПЕРЕБОРА ВСЕХ ВОЗМОЖНЫХ ВАРИАНТОВ РЕШЕНИЯ). Вариант задания, пример входных и выходных данных представлен в таблице 1. Глобальные параметры использовать запрещено; допустимо использование дополнительных функций.
₋ Разработанный алгоритм должен быть реализован в виде цельной программной функции (или нескольких функций) так, чтобы мог быть многократно применим с различными исходными данными и при этом не включал команды, не относящиеся к решаемой задаче, например, ввод и вывод исходных данных на консоль или в файл.
₋ Произвести экспериментальную проверку времени работы разработанного алгоритма, определив его класс сложности для среднего случая. Измерить среднее время для Test_Count повторений при различных размерностях входных данных. !ВАЖНО: при относительной небольшой размерности входных данных программа может потребовать для выполнения значительное время, рекомендуется не ждать выполнения программы в случае превышения времени выполнения 15 минут.
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ
Проверить работоспособность программы и составить отчёт по лабораторной работе.
В таблице 1 продемонстрированы данные к варианту
Таблица 1. Данные к заданию 9-го варианта
№ вар. | Задание | Вход | Выход |
9 | Данные: Две строки A, B размером NA, NB соответственно. Задача: − Определить максимальную общую строку символов методом полного перебора. Максимальная общая строка – набор символов максимально возможной длины, который может быть получен из каждой из строк A, B путем удаления из них некоторого числа символов. В случае нескольких вариантов вывести все. | A = “bedcadb” B = “abcdede” | bed (“bedcadb”, “abcdede”) bcd (“bedcadb”, “abcdede”) |
ОПИСАНИЕ ПЕРЕМЕННЫХ
В таблице 2 дано описание используемых в программе идентификаторов
Таблица 2. Идентификаторы программы 9-го варианта
Имя | Тип | Размер, байт | Назначение |
S1 | String | Вводимая строка | |
S2 | String | Вводимая строка | |
it | Int | 4 | элемент переданной строки под номером it |
mx_len | Int | 4 | размер максимальной общей строки |
res | String | Конкатенация элементов переданной строки под номером it | |
ans | String | Контейнер общих максимальных подстрок |
СХЕМА АЛГОРИТМА РЕШЕНИЯ
На рисунке 1 представлена блок-схема основной программы.
[pic 1]
...