Урок 13 апреля


Решение задач на рекурсивные алгоритмы

Основные определения 
Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа.
Чтобы определить рекурсию, нужно задать:
1. условие остановки рекурсии (базовый случай или несколько базовых случаев);
2. рекуррентную формулу.
Существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell).
Порядок выполнения
1. Посмотрите видеолекцию. 


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





G(n)






Чему будет равно значение величины  F(5) + G(5)?
3. Выполнить домашнее задание. 
3.1.Последовательность чисел трибоначчи задается рекуррентным соотношением:  
     F(1) = 0
F(2) = 1
F(3) = 1
F(n) = F(n–3) + F(n–2) + F(n–1), при n >3, где n – натуральное число.
Чему равно девятое число в последовательности?
3.2.Найдите сумму чисел, которые будут выведены при вызове F(1). 
procedure F(n: integer); 
begin
  writeln(n);
  if n < 5 then begin
    F(n + 3);
    F(n * 3)
  end
end; 
3.3.     У исполнителя Увеличитель две команды, которым присвоены номера:
1. прибавь 2, 
2.умножь на 3. 
Первая из них увеличивает число на экране на 2, вторая — умножает его на 3. 
Программа для Увеличителя — это последовательность команд. 
Сколько есть программ, которые число 1 преобразуют в число 31?
4. Пройти опрос


 Примеры выполнения
Пример 1
У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 22?
Решение.
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n.

Верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.
2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n – 1)
Имеем:
R(3) = 1
R(4) = R(2) + R(3) = 1 +1 = 2,
R(5) = R(4) = 2,
R(6) = R(3) + R(4) = 1 + 2 = 3 = R(7),
R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9),
R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),
R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),
R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),
R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),
R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),
R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),
R(22) = R(11) + R(20) = 7 + 30 = 37.

Ответ: 37.
Пример 2
Дан рекурсивный алгоритм:
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)?