Лабораторная работа «Применение рекурсивных функций»

Тема занятия - Применение рекурсивных функций

Цель занятия: создать условия для:

• закрепление знаний о рекурсивном объекте ирекурсивномалгоритме,

• освоения приёмов применения рекурсивных функции при составлении программ на языке программированияPascal.

Задачи занятия:

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

Образовательные: Сформировать понятия рекурсивного объекта и рекурсивного определения, познакомить учащихся с рекурсивными алгоритмами, научить ребят составлять программы с использованием рекурсивных функций; выражений на алгоритмический язык. Продолжить изучение подпрограмм. Показать сущность рекурсии на конкретных примерах. Способствовать приобретению опыта применения рекурсивных функции при составлении программ.

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

Методическое оснащение

- ноутбук, проектор;

- раздаточный материал: методические указания к выполнению лабораторной работы.

Тип занятия – лабораторная работа.

Используемая литература:

1. Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования: Учебник для сред. проф. образования / И.Г. Семакин, А.П. Шестаков. — М.: Издательский центр "Академия", 2008. 

2. Рапаков Г.Г., Ржеуцкая С.Ю. Программирование на языке Pascal. – СПб.: БХВ-Петербург, 2005.

3. Зеленяк О., Практикум программирования на Turbo Pascal, К.: ДиаСофт,2007

4.Гуденко Д, Петроченко Д., Сборник задач по программированию, СПб.: Питер, 2003

5. Культин Н., Программирование в TurboPascal и Delphi, СПб.: БХВ-Петербург, 2001.

6. Попов В.Б., Turbo Pascal для школьников, М.: Финансы и статистика, 2004

ХОД ЗАНЯТИЯ

1. Организационный момент (5 мин) – Приветствие. Преподаватель отмечает отсутствующих.

Посмотрите, пожалуйста, на эту картину. Что вы здесь видите? Как называется это процесс? (рекурсия)

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

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

Для начала давайте повторим ранее изученный материал.

1. Актуализация опорных знаний (10 мин)

2.1 Фронтальный опрос: Фронтальный опрос по теме предыдущего урока.

- Что мы называем подпрограммой? (Подпрограмма - это именованная логически законченная группа операторов, которую можно вызвать для выполнения по имени любое количество раз из различных мест программы. )

- Какие бывают виды подпрограмм? (процедуры и функции)

- Какие три важные задачи решают подпрограммы? (избавляют от необходимости многократно повторять в тексте программы аналогичные фрагменты; улучшают структуру программы, облегчая ее понимание; повышают устойчивость к ошибкам программирования и непредвидимым последствиям при модификациях программы.)

- Что такое рекурсия? (Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма вызывает сама себя)

- Какие вы знаете условия применения рекурсивной подпрограммы?

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

- Что такое глубина рекурсии?

(Количество одновременно выполняемых подпрограмм называют глубиной рекурсии.)

- Какой должна быть глубина рекурсии? Почему?

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

1. Выполнение работы (60 мин)

3.1 Выполнение готового кода программы. (30 мин)

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

Пример 1. Вычислить факториал натурального числа n!

Решение. Типичной функцией, на которой объясняют рекурсию, является факториал n!=1*2*3*…*n. Он может быть описан следующим образом

То есть для вычисления факториала, если n>1, нужно сначала вычислить (n-1)!. А для вычисления последнего надо сначала вычислить (n-2)!. Соответственно, для вычисления (n-2)! надо знать (n-3)! и т.д. Значение 1! (0!) задается явно. В программе реализованы два метода вычисления факториала: с помощью рекурсии и итерационно – вычислением по формуле с использованием цикла.

varn: integer;

{подпрограмма без использованием рекурсии}

function Fact(n:integer): longint;

var i:integer;

p:longint;

begin

p:=1;

for i:=1 to n do p:=p*i;

fact:=p;

end;

{подпрограмма с использованием рекурсии}

function FactRec(n:integer): longint;

begin

if (n=1) or (n=0) then FactRec:=1 else FactRec:=n* FactRec (n-1);

end;

BEGIN {основнаяпрограмма }

write('Введите n='); read(n);

writeln('Рекурсия: n!=',FactRec(n));

writeln('Цикл: n!=',Fact(n));

END.

Проверьте работу программы для n=2, 4, 9. Запишите ответы.

Выполним пошаговую трассировку программы, чтобы понять принципы работы функций.

Рассмотрим выполнение рекурсивной функции при n=5, т.е. вычислим 5! Блок-схема:

Определите глубину рекурсии (Ответ: 5)

Пример 2. Вычислитьn-ое число Фибоначчи.

Числа Фибоначчи- это элементы числовой последовательности, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).

X₀=1X₁=1X_n=X_n-1+X_n-2

Например,11235813

Решение. Для закрепления понятия рекурсии запрограммируем вычисление n-го числа Фибоначчи также двумя методами: с использованием рекурсии и итерационным.

var n:integer;

{подпрограмма без использования рекурсии}

function Fib(n:integer):integer;

var a,b,c, i:integer;

begin

a:=1; b:=1;

if (n=1) or (n=0) then Fib:=1 else

begin

for i:=2 to n dobegin

c:=a+b;

a:=b;

b:=c;

end;

Fib:=c;

end;

end;

{подпрограмма с использованием рекурсии}

function FibRec(n:integer): integer;

begin

if (n=1) or (n=0) thenFibRec:=1

else FibRec:=FibRec(n-1) + FibRec(n-2);

end;

//основная программа

begin

write('Введите n=');

read(n);

writeln('Рекурсия: ',FibRec(n));

writeln('Цикл: ',Fib(n));

write('click <enter>');

readln;

end.

Проверьте работу программы для n=2, 6, 10. Запишите ответы.

3.2 Самостоятельная отработка материала. (30 мин)

Задание Б. Написать рекурсивную программу вычисления целой неотрицательной степени числа А.

По определению Аⁿ=A*A*A*…..*A=A^n-1*A (n>0); А⁰ =1

Из определения следует, что для того, чтобы вычислитьn-ю степень числа, необходимо знать значение (n-1)-й степени этого числа. Если же n=0, то значение степени равно 1.

Студенты выполняют работу. После завершения выделенного времени на выполнение работы, оформляют работы в тетрадях для лабораторных работ. И сдают преподавателю.

Процесс выполнения лабораторной работы студентами просматриваются педагогом с применением программы Discort на компьютере преподавателя.

1. Защита лабораторной работы (тест) (10 мин)

Студенты отвечают на вопросы теста. Тест выполняется студентами на компьютерах. Оценка выставляется автоматически.

Зачет за лабораторную работу ставится при выполнении двух условий:

1. Выполненная практическая часть лабораторной работы

2. Тест по теоретической части написан на положительную оценку («отлично», «хорошо» или «удовлетворительно»).

1. Задание на дом (Приложение А, слайд 33) (2 мин)

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

5.1. Работа с опорным конспектом, [4] 67-74, [9] 149-154

1. Объявление оценок за урок и рефлексия (3 мин)

Объявление и выставление в журнал оценок за лабораторную работу.

Итак, сегодня мы прошли с вами новую тему. Что вам было сложнее всего выполнить на уроке? Согласны ли вы со своими оценками? А теперь, в конце урока хочется, чтобы вы выразили свое отношение к нашей сегодняшней работе и всему уроку в целом. Ответьте на вопросы в листах рефлексии и сдайте их мне.

+ все понятно ± понятно частично- ничего не понятно

Опишите общее впечатление от урока, выбрав соответствующий смайл:

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/548341-laboratornaja-rabota-primenenie-rekursivnyh-f