Рабочие листы
к вашим урокам
Скачать
1 слайд
Задание № 11 ЕГЭ
(базовый уровень, время – 5 мин)
Рекурсивные алгоритмы.
Автор – Коротун О.В.,
учитель информатики МОУ «СОШ № 71»
2 слайд
Содержание:
Определение рекурсии
Примеры решения задач
Пример 1
Пример 2
Пример 3
Пример 4
Задания для тренировки
3 слайд
Что нужно знать:
Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
Герб Российской Федерации является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия.
Рекурсивный герб России
4 слайд
5 слайд
В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
пример рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!
6 слайд
Пример задания:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n + 1);
F(n + 3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Решение с помощью дерева вызовов:
в начале каждого вызова на экран выводится значение единственного параметра функции
7 слайд
Пример задания:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n + 1);
F(n + 3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
1
8 слайд
Пример задания:
Дан рекурсивный алгоритм:
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
9 слайд
Пример задания:
Дан рекурсивный алгоритм:
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
10 слайд
Пример задания:
Дан рекурсивный алгоритм:
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
11 слайд
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
Аналогичная задача, которую можно решать с помощью дерева:
12 слайд
Пример № 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
13 слайд
Пример № 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
14 слайд
Пример № 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, а символ *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
15 слайд
Пример № 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)=
16 слайд
Пример № 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
17 слайд
Пример № 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 на экране появляются «звездочки».
18 слайд
Пример № 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 на экране появляются «звездочки».
19 слайд
Пример № 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)=
20 слайд
Пример № 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
21 слайд
Задания для тренировки
22 слайд
Задача 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
23 слайд
Задача 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
24 слайд
Задача 3:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
F(n-3);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
Ответ: 15
25 слайд
Задача 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
26 слайд
Задача 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
27 слайд
Задача 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
28 слайд
Задача 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
29 слайд
Задача 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
30 слайд
Задача 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
31 слайд
Задача 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
32 слайд
Задача 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
33 слайд
Задача 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
34 слайд
Задача 13:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
Ответ: 30
35 слайд
Задача 14:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n+2);
F(n*2)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Ответ: 53
36 слайд
Задача 15:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n+3);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Ответ: 42
37 слайд
Задача 16:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 7 then begin
F(n+3);
F(n*2)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
Ответ: 44
38 слайд
Задача 17:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 7 then begin
F(n+2);
F(n+3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Ответ: 81
39 слайд
Задача 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
40 слайд
Задача 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
41 слайд
Задача 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
42 слайд
Задача 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
43 слайд
Задача 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
44 слайд
Задача 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
45 слайд
Задача 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
46 слайд
Задача 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 из проекта демо-версии ЕГЭ - 2015 по информатике. Первый способ предполагает построение дерева вызовов, второй способ решает задачу методом подстановки. Рассмотрено 4 примера решения заданий с применением обоих способов. Далее презентация содержит 25 заданий для тренировки с ответами с сайта Константина Полякова.
6 626 501 материал в базе
«Информатика. Углубленный уровень (в 2-ух частях) », Поляков К.Ю., Еремин Е.А.
§ 61. Рекурсия
Больше материалов по этой темеНастоящий материал опубликован пользователем Коротун Ольга Викторовна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс повышения квалификации
72 ч. — 180 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Мини-курс
6 ч.
Мини-курс
10 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.