Рекурсивные алгоритмы
Автор: AstralXXX • Апрель 26, 2023 • Лабораторная работа • 492 Слов (2 Страниц) • 162 Просмотры
ЛАБОРАТОРНАЯ РАБОТА
- Выполнил
- студент гр.
<подпись>
- Преподаватель
- асс. преподавателя
<подпись>
- Санкт-Петербург
- 2023
- Цель работы
Овладеть навыками работы с рекурсивными алгоритмами.
- Постановка задачи
Необходимо разработать программу, которая реализует поиск палиндрома с использованием рекурсии. Пользователем на вход подается строка, сгенерированная случайным образом длинной до 30 символов. Программе необходимо найти максимальный палиндром во входной строке. В конце работы программы необходимо вывести палиндром максимального размера, а также символы, которые были удалены и их индексы. Если было найдено несколько палиндромов одинаковой длины, то программа выводит первый полученный палиндром. Нельзя использовать функции строк и любые функции, позволяющие определить палиндром, подстроку в строке, длину строки и пр. Можно использовать функции scanf, printf (или их аналоги).
- Теоретические исследования
Есть несколько решений данной задачи, алгоритм Манакера и метод полного перебора. Самым оптимальным решением был алгоритм Манакера, он менее затратен по памяти и времени, однако из-за незнания данного способа во время выполнения работы, был выбран метод полного перебора.
- Описание решения
Поиск палиндрома происходит следующим образом, на вход подается строка длиной до 30 символов. Производиться проверка является ли введенная строка палиндромом. Если да, то программа его выводит. В ином случае происходит сравнение крайних элементов строки. Если они различаются, то строка переписывается в два других массива, в первом массиве удаляется не совпадающий элемент слева, в другом справа, далее программа рекурсивно продолжает данную процедуры пока не будет найден палиндром. Если палиндром был найден, то программа продолжит поиск пока не переберет все случаи, если будет найден палиндром длиннее, чем предыдущий, то он будет переписан. На рисунке 1 изображена схема работы программы.
...