Презентация для подготовки к ЕГЭ по информатике по теме "Рекурсивные алгоритмы"
презентация к уроку по информатике и икт (11 класс) на тему
Презентация на тему "Рекурсивные алгоритмы" создана для подготовки обучающихся к ЕГЭ по информатике и ИКТ. В работе рассмотрено определение рекурсии, приведены примеры рекурсивно-определенных графических объектов. Презентация содержит способы решения задания № 11 из проекта демо-версии ЕГЭ - 2015 по информатике. Первый способ предполагает построение дерева вызовов, второй способ решает задачу методом подстановки. Рассмотрено 4 примера решения заданий с применением обоих способов. Далее презентация содержит 25 заданий для тренировки с ответами с сайта Константина Полякова.
Скачать:
Вложение | Размер |
---|---|
rekursivnye_algoritmy.pptx | 2.33 МБ |
Предварительный просмотр:
Подписи к слайдам:
Содержание: Определение рекурсии Примеры решения задач Пример 1 Пример 2 Пример 3 Пример 4 Задания для тренировки
Что нужно знать: Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя . Герб Российской Федерации является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия. Рекурсивный герб России
В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии . пример рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!
Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1); F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Решение с помощью дерева вызовов: в начале каждого вызова на экран выводится значение единственного параметра функции
Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n) ; if n < 5 then begin F(n + 1); F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). 1
Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1) ; F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). при n<5 выполняется два рекурсивных вызова, и на экране появляются следующие значения параметра: 1 4 2 +1 +3
Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1) ; F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения: 1 2 4 5 3 4 5 7 6 5 7
Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1); F(n + 3) end end ; Найдите сумму чисел , которые будут выведены при вызове F(1). Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения: 1 2 4 5 3 4 5 7 6 5 7 Складывая все эти числа, получаем 49
15 Пример № 2: Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln (n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). 1 3 3 9 5 7 15 5 9 Складывая все эти числа, получаем 79 7 + 2 * 3 Аналогичная задача, которую можно решать с помощью дерева:
Пример № 2: Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln (n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). А можно обойтись и без дерева! Пусть S(n) – это сумма чисел, которые будут выведены при вызове F(n). Тогда n+S (n+2)+S(n*3), n<6 S(n) = n, n Выполняем вычисления: S(1)=1+S(3)+S(3) S(3)=3+S(5)+S(9)=12+S(5) S(5)=5+S(7)+S(15)=5+7+15=27 Делаем обратный ход: S(3)=12+27=39 S(1)=1+39+39= 79
Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*') ; if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? 7 5 3 2 3 1 1 1 1 В этом примере на экран выводятся не значения параметра n , а символ * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0
Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*'); if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7 )? * Подсчитав количество «звездочек», получаем 21 В этом примере на экран выводятся не значения параметра n , а символ * * * * * * * * * * * * * * * * * * * * *
Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*'); if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7 )? Решим задачу без дерева. Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда 1+S(n-2 )+ S(n div 2), n>0 1 , n Нам нужно узнать S(7). S( 7 )= 1 +S( 5 )+ S(3) S( 5 )= 1 +S( 3 )+S( 2 ) S( 3 )= 1 +S( 1 )+S( 1) S(2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S( 1 )= 1+ S(-1)+S(0)=1+1+1=3 Делаем обратный ход : S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+13+7= 21 S (n)=
Пример № 4: procedure F(n: integer); begin if n < 3 then write('*') else begin F(n-1); F(n-2); F(n-2) end ; end ; Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число. 6 5 4 3 4 3 2 эта задача по сути такая же, как и предыдущая: для n < 3 функция выводит одну звездочку, а для бóльших n продолжаем рисовать дерево -1 -2 4 -2 3 2
Пример № 4: procedure F(n: integer); begin if n < 3 then write('*') else begin F(n-1); F(n-2); F(n-2) end ; end ; Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число. 6 5 4 3 4 3 * -1 -2 4 -2 3 * Вторая и третья ветви абсолютно одинаковые, поэтому будем рисовать одну, а количество «звездочек» потом умножим на 2. При условии n<3 на экране появляются «звездочки».
Пример № 4: procedure F(n: integer); begin if n < 3 then write('*') else begin F(n-1); F(n-2); F(n-2) end ; end ; Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число. 6 5 4 3 4 3 -1 -2 4 -2 3 ** 3 ** *** *** *** *** Получаем по первой ветви 11 «звездочек», по третьей, а значит и по второй – по 5. Всего – 21 При условии n<3 на экране появляются «звездочки».
Пример № 4: procedure F(n: integer); begin if n < 3 then write('*') else begin F(n-1); F(n-2); F(n-2) end ; end ; Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число. Решим задачу без дерева. Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда S(n-1)+S(n-2)+S(n-2), n 1 , n ИЛИ S(n-1)+ 2* S(n-2) , n 1 , n S (n)= S (n)=
Пример № 4: procedure F(n: integer); begin if n < 3 then write('*') else begin F(n-1); F(n-2); F(n-2) end ; end ; Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число. S(n-1)+ 2* S(n-2) , n 1 , n S (n)= Нам нужно узнать S( 6 ). S( 6 )=S( 5 )+ 2* S( 4 ) S( 5 )=S( 4 )+ 2* S( 3 ) S( 4 )=S( 3 )+ 2* S( 2) S( 3 )=S( 2 )+ 2* S( 0 )=S( 2 )+2*1=S( 2 )+2 S( 2 )= 1 Делаем обратный ход: S(3)=1+2=3 S(4)=3+2*1=5 S(5)=5+2*3=11 S(6)=11+2*5= 21
Задания для тренировки
Задача 1: Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n div 2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? Ответ: 34
Задача 2: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n-2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)? Ответ: 58
Задача 3: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-3); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 15
Задача 4: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-3); F(n-2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 55
Задача 5: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-3); F(n-2); F(n div 2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)? Ответ: 97
Задача 6: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin writeln('*'); F(n-2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 31
Задача 7: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin writeln('*'); F(n-2); F(n div 2); F(n div 2); end end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 81
Задача 8: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin writeln('*'); F(n-2); F(n-2); F(n div 2); end end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)? Ответ: 77
Задача 9: Дан рекурсивный алгоритм : procedure F(n: integer); begin if n > 0 then begin F(n-2); F(n-1); F(n-1); end; writeln('*'); end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? Ответ: 148
Задача 10: Дан рекурсивный алгоритм : procedure F(n: integer); begin if n > 0 then begin writeln('*'); F(n-2); F(n-1); F(n-1); end; writeln('*'); end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? Ответ: 197
Задача 11: Дан рекурсивный алгоритм : procedure F(n: integer); begin if n > 1 then begin F(n-2); F(n-1); F(n div 2); end; writeln('*'); end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 88
Задача 12: Дан рекурсивный алгоритм : procedure F(n: integer); begin if n > 2 then begin writeln('*'); F(n-2); F(n-1); F(n div 2); end ; writeln('*'); end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)? Ответ: 33
Задача 13: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 30
Задача 14: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin F(n+2); F(n* 2 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 53
Задача 15: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin F(n+ 3 ); F(n* 3 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 42
Задача 16: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin F(n+ 3 ); F(n* 2 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 44
Задача 17: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin F(n+ 2 ); F(n +3 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 81
Задача 18: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin F(n+ 2 ); F(n +3 ); F(n *2 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 103
Задача 19: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin F(n+1); F(n + 2); F(n * 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 79
Задача 20: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin writeln(n); F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 36
Задача 21: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin writeln(n); F(n+3); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 50
Задача 22: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin writeln(n); F(n+1); F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 425
Задача 23: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin writeln(n); F(n+1); F(n+2); F(n*2) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 530
Задача 24: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin writeln(n); F(n+1); F(n*2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 169
Задача 25: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin writeln(n); F(n+2); F(n*2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 426
По теме: методические разработки, презентации и конспекты
Презентация по информатике "Формальное исполнение алгоритмов"
Данная работа может быть использована как при подготовке к ЕГЭ в 11 классе, так и при изучении и повторении темы "Алгоритмы" в 9 классе. В презентации разбираются решения задач из части А и ...
Подготовка к ОГЭ информатика. Формальное исполнение алгоритма.
Подготовка к ОГЭ по информатике....
Презентация для урока информатики по теме «Алгоритмы»
Презентация для урока информатики в 9 классе по теме «Алгоритмы»...
Задачи для подготовки к ЕГЭ по информатике. Алгоритмы с использованием условного оператора.
задачи...
Задачи для подготовки к ЕГЭ по информатике. Алгоритмы без использования условного оператора.
задачи...
Презентация к занятию по информатике на тему "Алгоритмы и их свойства"
Презентация к занятию по информатике на тему "Алгоритмы и их свойства"...
Презентация для подготовки к ОГЭ по информатике по теме: "Формальные описания реальных объектов и процессов".
Презентация содержит подробное иллюстрированное объяснение темы: "Формальные описания реальных объектов и процессов" с примерами заданий ОГЭ для разбора и закрепления материала....