Задания для самопроверки

Задание 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