Подготовка к ЕГЭ. Рекурсивные алгоритмы. Задание №11

1.

Подготовка к ЕГЭ
«РЕКУРСИВНЫЕ АЛГОРИТМЫ»
ЗАДАНИЕ №11

2.

Проверяемые элементы содержания:
умение исполнить рекурсивный алгоритм.
Уровень сложности задания: базовый
Максимальный балл за выполнение задания: 1
Примерное время выполнения задания: 5 минут

3.

1. Вызов рекурсивных процедур
Пример: Алгоритм вычисления значений функций F(n) и
G(n), где n – натуральное число, задан следующими
соотношениями:
F(1) = 2; 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)? В ответе
запишите только целое число.

4.

F(1) = 2; 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(2)=F(1)-G(1)=1
G(2)=F(1)+G(1)=3
F(3)=F(2)-G(2)=-2
G(3)=F(2)+G(2)=4
F(4)=F(3)-G(3)=-6
G(4)=F(3)+G(3)=2
F(5)=F(4)-G(4)=-8
G(5)=F(4)+G(4)=-4
Ответ: F(5)/G(5)=2

5.

Задание для тренировки:
Алгоритм вычисления значений функций F(n) и G(n), где n –
натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)+F(5)? В ответе
запишите только целое число.

6.

2. Алгоритмы, опирающиеся на несколько
предыдущих значений
Пример: Алгоритм вычисления значения функции
F(n), где n – натуральное число, задан следующими
соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(7)? В ответе
запишите только целое число.

7.

F(0) = 1, F(1) = 1
F(n) = F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(7)? В ответе
запишите только целое число.
Решение:
F(2)=F(1)+F(0)=2
F(3)=F(2)+F(1)=3
F(4)= F(3)+F(2)=5
F(5)=F(4)+F(3)=8
F(6)=F(5)+F(4)=13
F(7)=F(6)+F(5)=21

8.

Задание для тренировки:
Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3*F(n–1) - F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите
только целое число.

9.

3. Алгоритмы, опирающиеся на одно
предыдущее значение
Пример: Алгоритм вычисления значения
функции F(n), где n – натуральное число, задан
следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n + 1), при n > 1
Чему равно значение функции F(4)? В ответе
запишите только целое число.

10.

F(1) = 1
F(n) = F(n–1) * (2*n + 1), при n > 1
Чему равно значение функции F(4)? В
ответе запишите только целое число.
Решение:
F(2)=F(1)*(2*2+1)=5
F(3)=F(2)*(2*3+1)=5*7=35
F(4)=F(3)*(2*4+1)=35*9=315

11.

Задание для тренировки:
Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (3*n - 2), при n > 1
Чему равно значение функции F(4)? В ответе
запишите только целое число.

12.

Задание для тренировки (д/з)
On-lineтест по теме: «Рекурсивные алгоритмы»
(сайт Полякова) http://kpolyakov.spb.ru/school/egetest/b11.htm