Методическая разработка урока Информатики и ИКТ в соответствии с требованиями ФГОС по теме «Рекурсия. Рекурсивные алгоритмы»

• 1 слайд

  Рекурсия
  

• 2 слайд

  Что же такое рекурсия?
  Чтобы понять, что такое рекурсия, надо понять, что такое рекурсия.
  
  Рекурсия – это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения её операторов обращается сама к себе.
  

• 3 слайд

  РЕКУРСИЯ
  Числовая
  Графическая
  Символьная
  

• 4 слайд

  Особенности рекурсии.
  
  Рекурсия полезна, прежде всего, в случаях, когда основную задачу можно разделить на подзадачи, имеющие ту же структуру, что и первоначальная задача. Подпрограммы, реализующие рекурсию, называются рекурсивными.
  Использование рекурсивной формы организации алгоритма обычно выглядит более изящно.
  Недостатки рекурсии:
  если глубина рекурсии (количество одновременно выполняемых процедур) очень велика, то оттранслированная программа будет требовать во время исполнения много памяти – это может привести к переполнению стека,
  рекурсивные алгоритмы обычно выполняются более медленно.
  
  

• 5 слайд

  Задача 1. Ниже записан рекурсивный алгоритм F на языке Паскаль. Что напечатает программа? Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(2)?
  Procedure F (n: integer) ;
  begin
  writeln(n);
  if n<=4 then
  begin
  F(n*2);
  F(n+1);
  end;
  еnd;
  Решение. Так как в процедуре имеются два
  рекурсивных вызова F(n*2) и F(n+1), то дерево
  будет двоичным. Левым потомком будет вызов вида F(n*2),
  правым – F(n+1). Корень дерева – самый первый вызов F(2).
  Напечатали 2, вызвали F(2*2)=F(4); напечатали 4, проверяем 4<=4 – истина, вызывается F(2*4)=F(8) (8<=4 – ложь), выполнение программы продолжается в копии F(4 ) c оператора вызова F(4+1)…
  
  
  
  F(2)
  F(4)
  F(8)
  F(5)
  F(3)
  F(6)
  F(4)
  F(8)
  F(5)
  Ответ на первый вопрос: 2 4 8 5 3 6 4 8 5
  Ответ на второй вопрос: 2+4+8+5+3+6+4+8+5=45(сумма чисел в узлах дерева)
  

• 6 слайд

  Рассмотрим результат работы программы при ином расположении оператора печати:
  Procedure F(n: integer);
  begin
  if n<=4 then
  begin
  writeln (n);
  F(n*2);
  F(n+1);
  end;
  еnd;
  При том же дереве рекурсивных вызовов процедура F напечатает только значения, меньшие или равные четырем.
  Ответ будет 2 4 3 4, сумма их будет 2+4+3+4=13.
  
  

• 7 слайд

  Эту же задачу решим, если нас интересует итоговая сумма.
  Второй способ решения. Считаем, что F(n) – сумма чисел, которые будут выведены на экран при вызове F(n). Если n>=4, то F(n)=n (программа выводит число n и дальше не выполняется). При n<=4 рекуррентное выражение запишется: F(n)= n + F(2*n) + F(n+1). Так как подпрограмма выводит на экран число n, а также вызывает F(2*n) и F(n+1), которые добавляют на экран соответствующую сумму чисел, которые мы складываем. Начинаем запись с последнего натурального числа, которое удовлетворяет условию в операторе if.
  Для записи вызова функции F() в строку записываем или ранее вычисленное значение для этой функции (если оно есть), или просто число, получаемое в качестве аргумента функции.
  Начнем с F(8), так как наибольшее n, при котором будет вызываться F(n) – это F(4*2).
  F(8)=8, F(7)=7, F(6)=6, F(5)=5
  F(4)=4+F(2*4)+F(4+1)=4+F(8)+F(5)=4+8+5=17
  F(3)=3+F(2*3)+F(3+1)=3+F(6)+F(4)=3+6+17=26
  F(2)=2+F(2*2)+F(2+1)=2+F(4)+F(3)=2+17+26=45
  Ответ: 45
  

• 8 слайд

  Пример рекурсивной процедуры:
  procedure Rec(a: integer);
  begin
  if a>0 then
  Rec(a-1);
  writeln(a);
  end;
  Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов. Рассмотрим блок-схему работы рекурсивной программы.
  

• 9 слайд

  Рис. 1. Блок схема работы рекурсивной процедуры.
  

• 10 слайд

  Еще один визуальный образ происходящего представлен на рисунке:
  

• 11 слайд

  4. Практическая работа. Имеется рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln(n);
  if n<6 then begin
  F(n+1);
  F(n*2);
  end;
  end;
  Что напечатает программа при вызове F(2)? Запишите выводимые значения через пробел.
  Предлагаю сначала решить данную задачу в тетради, а затем проверить на компьютере.
  Ответ: 2 3 4 5 6 10 8 6 4 5 6 10 8.
  

• 12 слайд

  
  5. Работа в группах. Решите следующие задачи: Ниже записан рекурсивный алгоритм F на языке Паскаль. Что напечатает программа (ответ запишите через пробел)? Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(2)?
  1) Procedure F (n: integer) ; 2) Procedure F (n: integer);
  begin begin
  if n<=4 then if n<=4 then
  begin begin
  writeln(n); F(n*2);
  F(n*2); F(n+1);
  F(n+1); end;
  end; writeln(n);
  end; end;
  Ответ:2 4 3 4 ; 13 Ответ: 8 5 4 6 8 5 4 3 2; 46
  3) Procedure F (n: integer);
  begin
  if n<=4 then
  begin
  F(n*2);
  writeln(n);
  F(n+1);
  end;
  end;
  Ответ: 4 2 3 4; 13
  
  
  

• 13 слайд

  Разбор решения задания 11 демоверсии ЕГЭ
  Рекурсивные алгоритмы
  Задача1. Ниже записаны две рекурсивные процедуры, F и G:
  procedure F(n: integer); forward;
  procedure G(n: integer); forward;
  procedure F(n: integer);
  begin
    if n > 0 then
      G(n - 1);
  end;
  procedure G(n: integer);
  begin
    writeln('*');
    if n > 1 then
      F(n - 3);
  end;
  Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
  
  

• 14 слайд

  Решение:
  Паскаль, встретив команду F(11), вызывает процедуру F и передает ей параметр n = 11:
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G (10) после уменьшения n на 1;
  процедура G печатает звездочку и, в случае выполнения условия n > 1, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(7);
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G (6) после уменьшения n на 1;
  процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(3)
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G(2) после уменьшения n на 1;
  процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(-1)
  получив значение -1 и убедившись, что условие не выполнилось, Паскаль завершает выполнение программы.
  А нам остается подсчитать, сколько раз печаталась звездочка. В нашем случае это произошло ровно 3 раза.
  Ответ: 3
  

• 15 слайд

  Задача 2. Ниже записаны две рекурсивные процедуры F и G:
  Procedure F(n: integer); forward;
  Procedure G(n: integer); forward;
  Procedure F(n: integer);
  begin
  if n>0 then
  G(n-1);
  writeln (‘*’);
  end;
  Procedure G(n: integer);
  begin
  writeln(‘*’);
  If n>1 then
  F(n-2);
  end;
  Сколько символов “звездочка” будет напечатано на экране при выполнении вызова F(11)?
  
  
  

• 16 слайд

  Решение. Паскаль, встретив команду F(11), вызывает процедуру F и передает ей параметр n = 11:
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G (10) после уменьшения n на 1,
  процедура G печатает звездочку и, в случае выполнения условия n > 1, уменьшает значение n на 2, затем с новым параметром вызывает процедуру F(8);
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G (7) после уменьшения n на 1,
  процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 2, затем с новым параметром вызывает процедуру F(5);
  в случае выполнения условия n > 0 выполняется следующая строка: G(n - 1), вызывающая процедуру G(4) после уменьшения n на 1,
  процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 2, затем с новым параметром вызывает процедуру F(2);
  в случае выполнения условия n>0 выполняется следующая строка: G(n-1), вызывающая процедуру G (1), печатается звездочка, условие 1>1 не выполняется. Возвращаемся в F(2), печатаем звездочку, завершаем F(2), завершаем G(4), возвращаемся в F(5), печатаем звездочку, завершаем F(5), завершаем G(7), возвращаемся в F(8), печатаем звездочку, завершаем F(8), завершаем G(10), возвращаемся в F(11), печатаем звездочку, завершаем F(11). Паскаль завершает выполнение программы. Ответ: 8
  
  

• 17 слайд

  Домашнее задание:
  Задание №1. Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3);
  end;
  end;
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  

• 18 слайд

  Задание 2. Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  F(n+2);
  F(n*3);
  end;
  end;
  Найдите сумму чисел, которые будут выведены при вызове F(1). Что выведет программа на экран при вызове F(1)?
  
  

• 19 слайд

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

Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа №17

муниципального образования город – курорт Геленджик

Методическая разработка урока Информатики и ИКТ в

соответствии с требованиями ФГОС по теме

«Рекурсия. Рекурсивные алгоритмы»

Автор разработки: учитель информатики и ИКТ Писаревская Л.И.

Геленджик

2018 год

Цели занятия:

Предметные: -  формирование представления о рекурсивном объекте и рекурсивном алгоритме; освоение приемов применения рекурсивных подпрограмм на языке Pascal ABC.

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

 Личностные: - алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе; представление о программировании как сфере возможной профессиональной деятельности.

Решаемые учебные задачи:

1.     напомнить сущность понятия вспомогательного алгоритма,  подпрограммы;

2.     познакомить с правилами оформления подпрограммы в виде процедуры;

3.     познакомить с правилами оформления подпрограммы в виде функции;

4.     познакомить с примерами работы  рекурсивных процедур.

Вид занятия: изучение нового материала.

Тип урока: интегрированный.

Метод проведения: словесный, наглядный, практическая работа.

Формы работы: фронтальная, выполнение практической работы, работа в группах.
ТСО: компьютерный класс, оснащенный современными ПК в количестве 14 штук, на которых установлена ОС семейства Windows с пакетом программ Microsoft Office, мультимедийный проектор, компьютер учителя.

Структура занятия:

·       Организационный момент (1 мин.)

·       Мотивация учебной деятельности. Актуализация опорных знаний (2 мин.)

·       Изучение нового материала (15-20 мин.)

·       Практическая работа (10)

·       Закрепление нового материала. Самостоятельная работа учащихся в группах(10 мин.)

·       Рефлексия (1 мин.)

·       Сообщение домашнего задания (1 мин.)

Ход занятия

Этапы урока	Действия учителя	Действия учеников
1.Организационный момент	Учитель приветствует учеников, проверяет присутствие в классе	Ученики готовятся к уроку
2. Мотивация учебной деятельности (создание ситуации успеха)	Что такое подпрограмма? Какие виды подпрограмм существуют в языке Паскаль? Что такое формальные и фактические параметры? В каком случае используется в программе процедура? В каком случае удобно использовать в программе функцию? Давайте ответим на вопрос: «Процедура или функция может ли содержать вызов других процедур или функций?» Сформулируйте цели нашего урока.	Подпрограмма – это специальным образом оформленный алгоритм. В языке Паскаль существует два вида подпрограмм: процедура(PROCEDURE) и функция (FUNCTION). Формальные – условные обозначения в описании процедуры, описываются в ее заголовке. Фактические – перечисляются при вызове процедуры и с ними требуется выполнить процедуру. Процедура используется в случаях, когда в подпрограмме необходимо получить несколько результатов. Когда в подпрограмме необходимо получит единственный результат. Ученики высказывают свои версии ответов. Ученики формулируют цели урока.
3.Изучение нового материала сопровождается презентацией.	Основной ошибкой циклической программы является зацикливание, то есть бесконечное повторение тела цикла. Но есть вид циклических алгоритмов, которые применяют этот прием для решения класса задач. Эта структура называется рекурсией. Слово «рекурсия» происходит от латинского слова «recursio» - возвращение. Рекурсивные определения как мощный аналитический аппарат используется во многих областях науки, особенно в математике: арифметическая прогрессия (an+1=an+d); геометрическая прогрессия (bn+1=bnq, ); числа Фибоначчи, каждый элемент которого является суммой двух предыдущих; факториал (n!=1*2*3*4*5…). Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. При использовании рекурсии необходимо обращать особое внимание на выход из подпрограммы в нужный момент, чтобы не вызвать зацикливания программы. Бесконечный вызов рекурсии приводит к переполнению стека и возникновению ошибки времени исполнения. Людям, не имеющим отношения к программированию, проще всего понять суть явления так: вспомните, что получится, если выстроить туннель из зеркал. Вот вам и рекурсия! Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия. Рекурсивностью в Паскале могут обладать как функции, так и процедуры.	Ученики слушают учителя, записывают основные понятия.

3.1 Рассмотрим фрагмент программы с рекурсивной процедурой (программа записана на доске)

procedure rever(n:integer);

   begin

    write(n mod 10);

    if (n div 10) <>0 then rever (n div 10);

   end;

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

   begin

   rever(435);

   readln;

   end.

Мы вызываем из основной программы процедуру rever(435).  Процедура rever выводит на экран остаток от деления на 10, число 5 и вызывает  процедуру rever(n div 10).

Переход на новую строку не происходит, так как используется write.

Проверяется условие, 435 при целочисленном делении на 10, равно 43 и это не равно 0.

Вызывается rever с фактическим параметром, равным 43.

Запускается вторая процедура и выводит на экран цифру 3 и запускает третью процедуру с параметром 4, третья процедура ничего больше не вызывает, так как условие (4 div 10) <> 0  не выполняется.

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

      3.2  Мы с вами знаем, что на языке Pascal написано много стандартных функций (например, div, mod и другие), но все описать невозможно. А как поступаем мы, если нам необходимо воспользоваться в программе функцией? Рассмотрим программу (листинг программы выводится на экран ) и выясним какую задачу решает она.

Program rec2;

var n:integer; f:longint;

 {функция}

     function fakt(n:integer):longint;

{описание функции, n –формальный параметр,}

{ результат выполнения функции имеет тип longint}

   begin

        if n=1 then fakt:=1 {проверка завершения рекурсии}

 else fakt:=n*fakt(n-1); {рекурсивное вычисление  n!}

end;

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

   begin

    write('Введите число n для вычисления n! ');

    readln(n);

   f:=fakt(n); {вызов функции для фактического параметра}

   writeln(' Для числа ' ,n,'  значение факториала =  ' , f);

readln;

end.

Описание работы вызова функции:

1)      выделяется память для переменных, описанных в функции fakt;

2)      присваивается формальным параметрам значения фактических параметров n:=n;

3)      выполняется программа функции, т.е.  будет найден факториал числа n;

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

Рассмотрим работу функции fakt;

-         если n=1 выполняется, то функция fakt:=1, на этом выполнение функции завершается;

-         если n=1 не выполняется, то вычисляется произведение n*fakt(n-1).

Вычисление произведения носит рекурсивный характер, т.к. при этом осуществляется вызов функции fakt(n-1), значение которой вычисляется, в свою очередь, через вызов функции fakt, параметром которой также будет функция fakt и т. д. до тех пор пока значение формального параметра n=1. Так как базовая часть описания рекурсивной функции fakt определяет значение fakt для n равным единице, то рекурсивные вызовы функции fakt больше не выполняются. Вместо этого выполняется вычисление функции fakt для чисел, возрастающих от 1 до n, причем функция fakt всякий раз возвращает значение, равное произведению очередного числа k на факториал от числа k-1. Последнее возвращение результата вычисления функции fakt присвоит переменной f значение произведения всех чисел от 1 до n, то есть факториал числа n.

Мы в основной программе ввели n=5,  вызвали функцию f:=fakt(5), n<>1, fakt:=5*fakt(4); n=4,fakt:=4*fakt(3); n=3,fakt:=3*fakt(2); n=2,fakt:=2*fakt(1).

n=1, fakt:=1 и происходит вычисление функции fakt:=2*fakt(1)=1*2=2, fakt:=3*fakt(2)=3*2=6, fakt:=4*fakt(3)=4*6=24, fakt:=5*fakt(4)=24*5=120.

 В основной программе происходит присвоение f вычисленное значение fakt, равное 120. В результате работы программы мы нашли факториал числа.

Факториал любого числа по определению является целым числом. В силу того, что n! – быстрорастущая функция, уже для n=13 возникает выход за границу диапазона типа longint (длинный целый:  -2147483648 до 2147483647), т.е. четыре байта памяти.

3.3   Рассмотрим работу  рекурсивных алгоритмов с помощью презентации.

Приложение1

1)    Слайд 2 – определение рекурсии

2)    Слайд 3 – виды рекурсии

3)    Слайд 4 – особенности рекурсии.

4)    На пятом слайде рассматривается работа рекурсивного алгоритма:

 Procedure F (n: integer) ;

begin

    writeln(n);

    if n<=4 then

    begin

        F(n*2);

        F(n+1);

   end;

еnd;

5)    На слайде 6 рассматривается изменение результата работы программы при расположении оператора печати после условного оператора. Вывод : результаты работы программы изменяются.

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

7)    Восьмой  и десятый слайды знакомят учащихся с работой рекурсивной программы с помощью блок-схемы. Учитель обращает внимание учащихся на определение  глубины рекурсии

8)    На Слайде 11 ребятам предлагается решить следующий алгоритм: что выведет программа при вызове F(2)?

procedure F(n: integer);

begin

    writeln(n);

     if n<6 then begin

     F(n+1);

     F(n*2);

    end;

end;

Результат проверить на компьютере.

Учитель проверяет работу в тетрадях и полученный результат на компьютере.  

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

10)    На слайдах 13-16 рассматриваются две задачи, предложенные учащимся на ЕГЭ.

6        Рефлексия: получение оценки полезности урока.

7        Сообщение домашнего задания.

Литература

1.     Turbo Pascal для студентов и школьников. Санкт-Петербург «БХВ-Петербург», 2005

2.     Информатика Справочник для подготовки к ЕГЭ. О. Б. Боголюбова, АСТ Москва, 2015

3.     ЕГЭ Информатика и ИКТ. Типовые экзаменационные варианты. С.С. Крылов, Т.Е. Чуркина, 2018.

4.     Материалы сайта К.Ю. Полякова kpolyakov.spb.ru.