Разбор задач ЕГЭ. Рекурсивные алгоритмы. В6

Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Последовательность чисел Фибоначчи задается рекуррентным соотношением:
F(1) = 1
F(2) = 1
F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.
Чему равно девятое число в последовательности Фибоначчи?
В ответе запишите только натуральное число.
Решение.
F(3) = F(1) + F(2) = 2,
F(4) = F(2) + F(3) = 3,
F(5) = F(3) + F(4) = 5,
F(6) = F(4) + F(5) = 8,
F(7) = F(5) + F(6) = 13,
F(8) = F(6) + F(7) = 21,
F(9) = F(7) + F(8) = 34.
Ответ 34

Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Условие k < 13 проверяется сразу после k:=k+4, следовательно, действие s:=s+2*k для k=16 выполняться не будет.
s+k=49+16=65
Ответ 65

Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then
Begin
F(n-2);
F(n div 2)
end;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение1.
сначала определим рекуррентную формулу; обозначим через G(n) количество звездочек, которые выводит программа при вызове F(n)
из программы видим, что
G(n) = 1 при всех n <= 0
G(n) = 1 + G(n-2) + G(n div 2) при n > 0
вспомним, что n div 2 – это частное от деления n на 2
по этим формулам заполняем таблицу, начиная с нуля:
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
Ответ 21

Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение2(«с конца»).
пп. 1-3 – как в варианте 1
по формулам 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(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3
теперь идем «обратным ходом»:
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

G(0) выведет одну звёздочку «*»,
G(-1)выведет одну звёздочку «*», отметим все звездочки (зелёным) и посчитаем их количество, получим ответ: 21.
Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение3(построение графа).
Ответ 21
G(7)
*
G(5)
*
G(3)
*
G(1)
*
G(0)
G(-1)
G(1)
*
G(0)
G(-1)
G(2)
*
G(0)
G(1)
*
G(0)
G(-1)
G(3)
*
G(1)
*
G(0)
G(-1)
G(1)
*
G(0)
G(-1)

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
writeln('*');
F(n-2);
F(n div 2);
end;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
Ответ 31

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Дан рекурсивный алгоритм:
procedure f(n:integer);
begin
writeln(n);
if n>0 then
begin
f(n-2);
f(n-3);
end;
end;
Найти сумму всех чисел которые выведет программа при вызове F(7)?
Ответ 17

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Алгоритм вычисления значения функции F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = 2 * G(n–1) + 5 * n, при n >1
G(1) = 1
G(n) = F(n–1) + 2 * n, при n >1
Чему равно значение функции F(4) + G(4)?
В ответе запишите только натуральное число.
Ответ 89

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Последовательность чисел трибоначчи задается рекуррентным соотношением:
F(1) = 0
F(2) = 1
F(3) = 1
F(n) = F(n–3) + F(n–2) + F(n–1), при n >3, где n – натуральное число.
Чему равно одиннадцатое число в последовательности трибоначчи?
В ответе запишите только натуральное число.
Ответ 149