Методические указания по освоению материала учебника

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

 учреждение высшего образования

«Московский государственный технический университет

Имени Н.Э. Баумана

(национальный исследовательский университет)»

(МГТУ им. Н.Э. Баумана)

 

 

Т.Н. Ничушкина

 

 

Разработка программ рекурсивной структуры

 

 

Учебное пособие по курсу «Информатика»

 

 

Москва

(С) 2018 МГТУ им. Н.Э. БАУМАНА

 

                               

 

УДК 004.432

 

Рецензент: доцент кафедры ИУ1  к.т.н. Задорожная Н.М.

                                                   

Т.Н. Ничушкина

Разработка программ рекурсивной структуры. Учебное пособие  по дисциплине «Информатика» -  М.: МГТУ имени Н.Э. Баумана, 2017. 33 с.

 

Учебное пособие содержат теоретические сведения по  разработке рекурсивных программ в языке С++. Приведены примеры рекурсивных алгоритмов и программ.

 Для студентов МГТУ имени Н.Э. Баумана, обучающихся по программе бакалавриата по направлению «Математика и компьютерные науки»

Рекомендовано Учебно-методической комиссией НУК «Информатика и системы управления» МГТУ им. Н.Э. Баумана

                                 Ничушкина Татьяна Николаевна

 

 

Разработка программ рекурсивной структуры.

Учебное пособие  по дисциплине «Информатика»

© Т.Н. Ничушкина, 2018

© МГТУ имени Н.Э. Баумана, 2018

 

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ_ 4

ВВЕДЕНИЕ_ 7

Глава 1. Рекурсия. Основные положения_ 8

1.1. Рекурсивные алгоритмы.. 8

1.2. Рекурсивные процедуры и функции. Взаиморекурсия. 10

1.3. Фрейм активации. 11

1.4 Линейная и древовидная рекурсии. 16

1.5 Примеры рекурсивных программ.. 19

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

Глава 2. Полный и ограниченный перебор. Использование рекурсии при программировании ограниченного перебора_ 27

2.1. Понятие полного перебора. Основные приемы его осуществления. 27

2.2. Использование рекурсии при реализации ограниченного перебора. 35

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

3 Использование рекурсии при обработке бинарных деревьев_ 41

3.1 Понятие бинарного дерева. 41

3.2 Использование рекурсивных алгоритмов обработки бинарных деревьев. 43

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

4 Контрольные вопросы_ 54

ЗАКЛЮЧЕНИЕ_ 55

СПИСОК ЛИТЕРАТУРЫ_ 56

 

ПРЕДИСЛОВИЕ

Учебное пособие предназначено для углубления знаний, полученных при освоении лекционного материала и семинарских занятий, а также самостоятельного изучения студентами темы «Рекурсия» по дисциплине «Информатика», входящей в основную образовательную программу подготовки бакалавров для студентов, обучающихся по направлению «Математика и компьютерные науки» 02.03.01.

Цель учебного пособия – закрепление теоретических знаний и практических навыков, необходимых при разработке алгоритмов и программ рекурсивной структуры, формирование умений и навыков в распознавании и реализации таких алгоритмов.

После изучения этой темы дисциплины студенты овладеют:

· базовыми знаниями теории рекурсивных алгоритмов, необходимыми для разработки математических моделей объектов и формализации задач разработки сложных программ;

· практическими навыками разработки рекурсивных алгоритмов;

· приемами тестирования и отладки программ рекурсивной структуры.

Планируемые результаты обучения

  Студент должен знать:

- виды задач с рекурсивной структурой;

- способы разработки задач с применением рекурсивных алгоритмов;

- область применения рекурсивных алгоритмов;

      – способы оценки необходимости применения рекурсивного алгоритма.

       Студент должен уметь:

- выполнять анализ задачи и обосновывать необходимость применения рекурсивных алгоритмов для ее решения;

- разрабатывать алгоритм решения задачи;

- выбирать способ реализации рекурсивного алгоритма на языке С++;

- программировать и отлаживать рекурсивные программы.

Студент должен иметь навыки:

    – анализа предметных областей решаемых задач;

– анализа содержательной и получения формальной постановки задач;

– анализа и применения методов решения задач рекурсивной структуры.

Для изучения темы необходимы знания, умения и навыки, полученные обучающимися при освоении школьной программы.

Методические указания по освоению материала учебника

Основной целью освоения материала учебного пособия является самостоятельное изучение студентами темы «Разработка программ рекурсивной структуры».

Учебное пособие состоит из трех глав.

В первой главе разъясняется понятие рекурсии, рассматривается применение рекурсии в программировании и особенности разработки рекурсивных алгоритмов. Приводится структура рекурсивных подпрограмм, способы реализации, особенности выполнения и отладки таких программ. Приведены примеры рекурсивных программ.

Во второй главе рассмотрены проблемы и особенности задач, требующих полного перебора всех возможных вариантов для получения решения. Приведены способы реализации полного перебора и применение рекурсивных алгоритмов для сокращения рассматриваемых вариантов.

В третьей главе дается определение и описание древовидных структур данных на примере бинарных деревьев. Демонстрируется возможность и необходимость применения рекурсивных алгоритмов для обработки таких структур данных. Приведены примеры программ обработки.

Главы учебного пособия следует прорабатывать последовательно, так как каждая из них обеспечивает успешное восприятие материала следующих глав.

Основные понятия и положения проиллюстрированы примерами. Для успешного освоения материала необходимо внимательно разбирать примеры, целесообразно прорабатывать аналогичные примеры.

В конце каждой главы есть задания, которые необходимо проработать, а в конце пособия приведены контрольные вопросы. Выполнение заданий обеспечит приобретение умений и навыков, необходимых для решения задач рекурсивной структуры в различных предметных областях. Ответы на вопросы позволят обучающемуся самому оценить степень понимания и усвоения теоретических положений.

При освоении студентами дисциплины по программе  бакалавриата для оценки степени понимания и усвоения теоретических положений, приобретения умений и навыков, указанных в программе, служат домашние задания, лабораторные работы, текущий контроль в виде рейтингов и семинарские занятия с элементами дискуссии.

 

 

ВВЕДЕНИЕ

Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики,  но наиболее широкое применение находит в математике и информатике.

 Рекурсия— это одна из жемчужин теории алгоритмов. Она является важнейшим приемом, который широко используется в различных разделах информатики и вычислительной техники.

Так, например, на рекурсии построен язык «Пролог», который используется в системах искусственного интеллекта. Рекурсия применяется в языках параллельного и динамического программирования. Возможности разработки рекурсивных алгоритмов заложены в современных универсальных языках программирования, таких, как Паскаль и С++.

Кроме того, в теории структур данных широкий класс структур относят к рекурсивным, как по описанию, так и по обработке. Например, списки и деревья.

Все это делает изучение рекурсивных алгоритмов и структур очень важным для понимания многих дисциплин профессионального цикла студентами, обучающимися по направлениям «Математика и компьютерные науки» и «Информатика и вычислительная техника».

Предлагаемое учебное пособие предназначено для студентов первого курса кафедры ФН-11, изучающих дисциплину «Информатика». Однако, они могут быть полезны при проведении семинаров, лабораторных работ и домашних заданий по теме «Рекурсия» студентам и преподавателям смежных специальностей.