Россия, Певек
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Была в сети 12.10.2019 11:26
Вестман Ольга Николаевна
учитель информатики
69 лет
19 462
1 231 
Местоположение
Специализация
Задание 11 (презентация по типам задач к ЕГЭ)
Категория:
Информатика
02.11.2016 05:32
Просмотр содержимого документа
«Задание 11 (презентация по типам задач к ЕГЭ)»
ege-11 (базовый уровень, время – 5 мин )
Умение исполнить рекурсивный алгоритм
Что нужно знать :
- рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
- чтобы определить рекурсию, нужно задать
- условие остановки рекурсии (базовый случай или несколько базовых случаев) рекуррентную формулу
- условие остановки рекурсии (базовый случай или несколько базовых случаев)
- рекуррентную формулу
- любую рекурсивную процедуру можно запрограммировать с помощью цикла
- рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
- существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)
0 then G (n - 1); end; procedure G (n: integer); begin writeln('*'); if n 1 then F (n - 2); end; Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F (11)? Директива FORWARD Если одна подпрограмма использует другую, а та, в свою очередь, эту первую, то возникает проблема размещения этих подпрограмм в программе (ни одну из них нельзя поместить перед другой). Чтобы устранить это противоречие, используется директива forward, позволяющая как бы разбить на две части одну из подпрограмм. Решение Ответ: 4 заметим, что каждая функция вызывает другую (это называется косвенная рекурсия), причём только один раз вот цепочка вызовов: F(11) G (10) F(8) G (7) F(5) G (4) F(2) G (1) за один вызов функции G выводится одна звёздочка, внутри функции F звездочки не выводятся, поэтому за 4 вызова G будет выведено 4 звездочки " width="640"
Пример I:
Ниже записаны две рекурсивные процедуры: 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 - 2);
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F (11)?
Директива FORWARD
Если одна подпрограмма использует другую, а та, в свою очередь, эту первую, то возникает проблема размещения этих подпрограмм в программе (ни одну из них нельзя поместить перед другой). Чтобы устранить это противоречие, используется директива forward, позволяющая как бы разбить на две части одну из подпрограмм.
Решение
Ответ: 4
- заметим, что каждая функция вызывает другую (это называется косвенная рекурсия), причём только один раз
- вот цепочка вызовов: F(11) G (10) F(8) G (7) F(5) G (4) F(2) G (1)
- за один вызов функции G выводится одна звёздочка, внутри функции F звездочки не выводятся, поэтому за 4 вызова G будет выведено 4 звездочки
Пример II:
Р-05. Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n
F(n + 1);
F(n + 3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1) .
Решение (вариант 1, построение дерева вызовов )
- поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
- при выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):
1
2
4
3
5
7
5
4
6
7
5
- складывая все эти числа, получаем 49
Ответ: 49
4
Решение (вариант 2, подстановка):
- учитывая, что при каждом вызове с n происходит два рекурсивных вызова; сумму чисел, полученных при вызове F(n), обозначим через S(n):
- выполняем вычисления:
- теперь остаётся вычислить ответ «обратным ходом»:
Ответ: 49
= 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов: G(n) = n при n = 6 при n G(n) = n + G(n+2) + G(3n) при n в результате вызова F(1) получаем G(1) = 1 + G(3) + G(3) G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9 G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27 используем обратную подстановку: G(3) =3 +G(5)+9=3+27+9=39 G(1) = 1 + 2*G(3) = 79 " width="640"
Пример III:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Ответ: 79
Решение ( вариант 1, метод подстановки )
- при n = 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов: G(n) = n при n = 6
- при n G(n) = n + G(n+2) + G(3n) при n
- в результате вызова F(1) получаем
G(1) = 1 + G(3) + G(3)
G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9
G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27
- используем обратную подстановку:
G(3) =3 +G(5)+9=3+27+9=39
G(1) = 1 + 2*G(3) = 79
= 6 (где G(n) = n) n G(n) 1 2 3 4 5 6 7 6 7 8 8 9 9 10 11 10 11 12 13 12 13 14 14 15 15 остальные ячейки заполняем, начиная с n = 5 справа налево, используя формулу : G(n) = n + G(n+2) + G(3n) n G(n) 1 2 79 3 30 4 39 22 5 6 27 7 6 8 7 9 8 10 9 11 10 12 11 12 13 14 13 15 14 15 Ответ: 79 " width="640"
Решение (вариант 2, динамическое программирование)
- заполняем таблицу G(n ) при n = 6 (где G(n) = n)
n
G(n)
1
2
3
4
5
6
7
6
7
8
8
9
9
10
11
10
11
12
13
12
13
14
14
15
15
- остальные ячейки заполняем, начиная с n = 5 справа налево, используя формулу : G(n) = n + G(n+2) + G(3n)
n
G(n)
1
2
79
3
30
4
39
22
5
6
27
7
6
8
7
9
8
10
9
11
10
12
11
12
13
14
13
15
14
15
Ответ: 79
0 then begin F(n-2); F(n div 2) end end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7) ? Решение ( вариант 1, составление полной таблицы ) из программы видим, что G(n) = 1 при всех n G(n) = 1 + G(n-2) + G(n div 2) при n 0 по этим формулам заполняем таблицу, начиная с нуля: " width="640"
Пример IV:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n 0 then begin
F(n-2);
F(n div 2)
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7) ?
Решение ( вариант 1, составление полной таблицы )
- из программы видим, что
G(n) = 1 при всех n
G(n) = 1 + G(n-2) + G(n div 2) при n 0
- по этим формулам заполняем таблицу, начиная с нуля:
G(0) = 1
G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3
G(2) = 1 + G(0) + G(1) = 1 + 1 + 3 = 5
G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7
G(4) = 1 + G(2) + G(2) = 1 + 5 + 5 = 11
G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13
G(6) = 1 + G(4) + G(3) = 1 + 11 + 7 = 19
G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21
n
G(n)
0
1
1
2
3
5
3
7
4
5
11
6
13
7
19
21
Ответ: 21
Решение ( вариант 2, «с конца» )
- по формулам G(7)=1+ G(5)+G(3), поэтому нужно найти G(5) и G(3)
- G(5) = 1 + G(3) + G(2), нужны G(3) и G(2)
- G(3) = 1 + G(1) + G(1), нужно G(1)
- G(2) = 1 + G(0) + G(1) = 2 + G(1), нужно G(1)
- теперь идем «обратным ходом»:
G(2) = 2 + G(1) = 5
G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7
G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13
G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21
Ответ: 21
=2 Чему равно значение величины F(5)/G(5) ? В ответе запишите только целое число. Решение фактически рекуррентная формула задана для пары (F(n); G(n)) замечаем, что F(n) – это разность предыдущей пары, а G(n) – сумма тех же значений заполняем таблицу, начиная с известной первой пары n F(n) 1 G(n) 1 2 1 0 3 – 2 4 2 – 4 2 5 0 – 4 – 4 искомое значение F(5)/G(5) равно 1 Ответ: 1 " width="640"
Пример V:
Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n – 1) – G(n – 1),
G(n) = F(n–1) + G(n – 1), при n =2
Чему равно значение величины F(5)/G(5) ?
В ответе запишите только целое число.
Решение
- фактически рекуррентная формула задана для пары (F(n); G(n))
- замечаем, что F(n) – это разность предыдущей пары, а G(n) – сумма тех же значений
- заполняем таблицу, начиная с известной первой пары
n
F(n)
1
G(n)
1
2
1
0
3
– 2
4
2
– 4
2
5
0
– 4
– 4
- искомое значение F(5)/G(5) равно 1
Ответ: 1
1 Чему равно значение функции F(5) ? В ответе запишите только целое число. Решение используя заданную рекуррентную формулу, находим, что F(5) = F(4) * 5 применив формулу еще несколько раз, получаем F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5 мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1 окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120 Ответ: 120 " width="640"
Пример VI:
Алгоритм вычисления значения функции F(n) , где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * n, при n 1
Чему равно значение функции F(5) ?
В ответе запишите только целое число.
Решение
- используя заданную рекуррентную формулу, находим, что
F(5) = F(4) * 5
- применив формулу еще несколько раз, получаем
F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5
- мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1
- окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120
Ответ: 120
Пример VII:
Процедура F(n), где n – натуральное число, задана следующим образом (язык Паскаль):
procedure F(n: integer);
begin
if n
write('*')
else begin
F(n-1);
F(n-2);
F(n-2)
end;
end;
Сколько звездочек напечатает эта процедура при вызове F(6) ? В ответе запишите только целое число.
Решение
- для n (то есть, для 1 и 2) функция выводит одну “*”
F(1) = F(2) = 1
а для бóльших n имеем рекуррентную формулу
F(n) = F(n-1) + F(n-2) + F(n-2) = F(n-1) + 2*F(n-2)
- запишем в таблицу базовые случаи
n
F(n)
1
2
1
3
1
4
5
6
- заполняем таблицу, используя рекуррентную формулу:
n
1
F(n)
2
1
3
1
3
4
5
5
6
11
21
F(3) = F(2) + 2*F(1) = 3
F(4) = F(3) + 2*F(2) = 5
F(5) = F(4) + 2*F(3) = 11
F(6) = F(5) + 2*F(4) = 21
Ответ: 21
0 then G (n - 1); end; procedure G (n: integer); begin writeln('*'); if n 1 then F (n - 3); end; Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11) ? Ответ: 3 " width="640"
ДЕМО - 2016:
Ниже записаны две рекурсивные функции (процедуры): 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) ?
Ответ: 3
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F ( 11 )?
F(11) G(10) F(8) G(7) F(5) G(4) F(2) G(1)
Ответ: 4
Что выведет программа при вызове F(9) ?
Ответ: 45
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
Полезное для учителя
Реализация образовательных программ осуществляется с применением исключительно электронного обучения и ДОТ
