Задание 1. Разработайте программу, которая обеспечивает быстрый поиск информации о сотрудниках фирмы с использованием бинарных деревьев: имя, фамилия, отчество, отдел, должность, служебный телефон, домашний адрес и телефон. Определите, во сколько раз быстрее в среднем будет выполняться поиск информации по сравнению с последовательным поиском, если количество сотрудников фирмы 10, 100, 1000 человек.
Задание 2. Для программы предыдущего задания оцените объем оперативной памяти, необходимой для размещения информации о 300 сотрудниках фирмы. Определите долю памяти, отводимой для хранения адресов элементов.
4 Контрольные вопросы
1. Дайте определение рекурсии. Из каких двух частей состоит рекурсивное утверждение?
2. Что такое взаиморекурсия? Как программно ее можно реализовать?
3. Что такое активация рекурсивной программы и фрейм активации? Как он влияет на емкостную сложность программы? Чем опасен большой объем фрейма активации?
4. Как рассчитать объем фрейма активации? Как можно уменьшить фрейм активации?
|
|
5. Дайте описание структуры рекурсивной программы.
6. Какова особенность выполнения операторов до и после рекурсивного вызова?
7. Что такое линейная и древовидная рекурсия? Особенности спуска и подъема каждой их этих разновидностей рекурсий.
8. Что такое полный и ограниченный перебор?
9. Особенности задач полного перебора.
10. Способы уменьшения количества рассматриваемых вариантов при полном переборе.
11. В чем преимущество использования рекурсии при решении задач полного и ограниченного перебора.
12. Дайте определение бинарного дерева.
13. Чем отличается рекурсивная процедура построения бинарного дерева?
14. В чем особенности процедуры удаления вершины бинарного дерева?
ЗАКЛЮЧЕНИЕ
В учебном пособии приведены базовые сведения по рекурсии и рекурсивным алгоритмам. Рассмотрены особенности описания, разработки и выполнения рекурсивных программ. Приведены примеры программ, реализующих рекурсивные алгоритмы.
Предлагаемое учебное пособие позволит более подробно ознакомиться со структурой рекурсивной программы, особенностями ее программирования и отладки. В результате использования пособия студенты научатся видеть рекурсивный алгоритм и программировать его на языке программирования С++, определять и контролировать выполнение и завершение такой программы, выполнять тестирование отладку, оценивать фрейм активации и его влияние на размер используемого стека. Это позволит изучить более сложные возможности языков высокого уровня и сложных структур данных.
|
|
Кроме того, в пособии приведены примеры применения рекурсивных алгоритмов в различных областях: полный и ограниченный перебор, сортировка с использованием бинарных деревьев, исследование функций.
Рассмотренные материалы помогут студентам выполнять лабораторные работы, домашние задания и контрольные работы по теме «разработка рекурсивных программ» по дисциплине «Информатика».
СПИСОК ЛИТЕРАТУРЫ
1. Г.С. Иванова, Т.Н. Ничушкина, Р.С. Самарев. Средства процедурного программирования Microsoft Visual С++ 2008. Учебное пособие. – М.: Издательство МГТУ им. Н.Э. Баумана, 2011.
2. В.В. Подбельский. Язык С++: Учеб. пособие. – М.: Финансы и статистика, 2006.
3. Г.С. Иванова. Программирование. Учебник для ВУЗов. – М.: Кнорус, 2013.- 432 с.
4. Г.С. Иванова. Технология программирования. Учебник для ВУЗов. – М.: Кнорус, 2013. – 336 с.
5. Н.Вирт. Алгоритмы и структуры данных: перевод с англ. – М.: ДМК Пресс, 2011. – 272 с.
6. Pollice G., Selkow S., George T. Heineman. Algorithms in a Nutshell: O'ReillyMedia Inc., 2008 – 358 p.
7. Steven S Skiena, The Algorithm Design Manual: Springer Science & Business Media, 2009 - 77 p.
8. Программирование на С и С++. [Электронный ресурс] Электрон. текстовые дан. – Онлайн справочник программиста на С и С++. – Режим доступа: http://www.c-cpp.ru/books/rekursiya