ЕГЭ №23, рекурсия, рекуррентное соотношение

[_Swetlana]

Задача 23 из тренировочного варианта ЕГЭ

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья  — умножает на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 11 и при этом не содержат двух команд умножения подряд?

Взято здесь
https://inf-ege.sdamgia.ru/problem?id=46981

В качестве решения предлагается использовать рекурсию (комментарии мои):
program ege23_rekursia;
uses crt;
//F возвращает число способов, к-ми из x можно получить y
function F(x, y: integer; mult: boolean): integer;
begin
  if x = y then F:= 1 //получили y из x одним способом
  else if x > y then F:= 0 //y из x получить нельзя
  else if mult = False then //получили y из x+1, и x+2, и x*2
      F:= F(x+1,y,False)+F(x+2,y,False)+F(x*2,y,True)
  else if mult = True then  //получили y из x+1 и x+2 без умножения
      F:= F(x+1,y,False)+F(x+2,y,False);
end;

begin
  writeln(F(1,11,False));
end.

Ну что сказать. С одной стороны, конечно, рекурсия экономит время и силы программиста. Хорошо, если школьник
а) поймёт рекурсию (если поймёт);
б) научится быстро решать задачи.
Ключевое слово быстро, т.к. на егэ по информатике думать некогда - выдрессированный репетиторами 11-классник сидит и штампует решения.

А с другой стороны,  предложенная программа - образец, как не надо писать программы. Потому что одни и те же значения функции многократно вычисляются. Зачем учить дурному, хотя бы и ради сдачи егэ.

Посмотрим,  как можно решить эту задачу по-другому. Решать перебором с помощью дерева - нерационально, слишком большое дерево получится, легко запутаться.
Остаётся только составить рекуррентное соотношение для количества способов, последовательно их вычислять,  запоминать и использовать для дальнейших вычислений. От программирования не требуется ничего, кроме умения заполнить одномерный массив по формуле с помощью цикла.

[_Swetlana]

Обозначения
T(j) – количество способов получения числа j из 1 с помощью всех команд.
T*(j) – количество способов получения числа j из 1 с помощью команд 1-2 (без умножения).
Запишем рекуррентное соотношение для j =0 и для j =1:
T(0) = T*(0) = 0;
T(1) = T*(1) = 1.
Для j >1:
T*(j) = T(j – 1) + T(j – 2) для любого j > 1;
T(j) = T(j – 1) + T(j – 2), если j нечётное;
T(j) = T(j – 1) + T(j – 2) +T*(j div 2), если j делится на 4;
T(j) = T(j – 1) + T(j – 2) +T(j div 2), если j чётное и не делится на 4.
Например, подсчитаем число способов получения 2.
T(2) = T(1) + T(0) + T(1) = 2 (два способа: 2 = 1 + 1 и 2 = 2*1);
T*(2) = T(1) + T(0) = 1 (один способ: 2 = 1+ 1).

Вычисления можно безо всякой программы вести в такой табличке:
 

[_Swetlana]

Правда, я сама сумела правильно заполнить таблицу только с третьего раза...
Поэтому всё-таки лучше написать простую программу с одномерным циклом:

uses crt;
const n = 11;
var T,T_ast: array[0..n] of integer;
j: integer;

begin
T[0]: = 0; T_ast[0]: = 0; T[1]: = 1; T_ast[1]: = 1;
for j:= 2 to n do
   if odd(j) then
      begin T[j]: = T[j-1]+T[j-2]; T_ast[j]: = T[j] end
    else if j mod 4 = 0 then
      begin T[j]: = T[j-1]+T[j-2]+T_ast[j div 2]; T_ast[j]: = T[j-1]+T[j-2] end
    else begin T[j]: = T[j-1]+T[j-2]+T[j div 2]; T_ast[j]: = T[j-1]+T[j-2] end;

   for j:= 1 to 11 do writeln('T[',j,']=',T[j],' T*[',j,']=',T_ast[j] );
end.

[_Swetlana]

Далее рассмотрим вариации на тему числа способов с различными ограничениями, а также другие формулировки 23-й задачи.

[_Swetlana]

Правильные рекуррентные соотношения

Одним из основных способов решения задач является их сведение к решению такого набора подзадач, чтобы, исходя из решений подзадач, было возможно получить решение исходной задачи.
Cпособ сведения решения исходной задачи к решению некоторых подзадач может быть записан в виде соотношений, в которых значение функции, соответствующей исходной задаче, выражается через значения функций, соответствующих подзадачам. При этом важнейшим условием сведения является тот факт, что значения аргументов у любой из функций в правой части соотношения меньше значения аргументов функции в левой части соотношения. Если аргументов несколько, то достаточно уменьшения одного из них.
Cоотношения должны быть определены для всех допустимых значений аргументов!

Рассмотрим в качестве примера задачу.
Задача №1
Определить, сколькими различными способами с первой ступеньки лестницы можно подняться на 8-ю ступеньку, если за один шаг можно подниматься на следующую ступеньку или через одну.

Или эта же задача в другой формулировке
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
Первая команда увеличивает число на 1, вторая увеличивает его на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, преобразующих исходное число 1 в число 8?

Решение
Запишем (правильное) рекуррентное соотношение для функции T(j) – количества способов подняться с первой на j-ю ступеньку. 
Исходя из условия задачи, на 8 ступеньку можно подняться непосредственно с 7-й и 6-й ступенек. Поэтому, если мы знаем количество способов подъема T(6) и T(7) на 6-ю и 7-ю ступеньки соответственно, то количество способов подъема на 8-ю ступеньку может быть определено как
T(8) = T(7) + T(6).
Аналогично для любой j-й ступеньки:
T(j) = T(j–1) + T(j–2), j>= 2 (1)
Для второй ступеньки получаем T(2) = T(1) + T(0).
Осталось непосредственно определить, чему равны T(1) и T(0): T(0) = 0 и T(1) = 1.
Зная T(0) и T(1), из рекуррентного соотношения (1) можно последовательно вычислить все значения T(2) ... T(8).
Вычисленные значения будем запоминать в одномерном массиве.
(Использование таблиц для запоминания результатов решения подзадач  называется методом динамического программирования. Одним из способов организации таблиц является подход, при котором размерность таблицы определяется количеством аргументов у функции, соответствующей подзадаче.)
В нашем случае функция T имеет один аргумент, поэтому таблица одномерная.
Вычислим эти значения:
T(2) = T(2–1) + T(2–2) = T(1) + T(0) = 1
T(3) = T(2) + T(1) = 1 + 1 = 2
T(4) = T(3) + T(2) = 2 + 1 = 3
T(5) = T(4) + T(3) = 3 + 2 = 5
T(6) = T(5) + T(4) = 5 + 3 = 8
T(7) = T(6) + T(5) = 8 + 5 = 13
T(8) = T(7) + T(6) = 13 + 8 = 21
При больших значениях входных данных для расчёта значения T(8) расчёт значений нужно производить в программе.
Программу можно написать без использования рекурсии методом динамического программирования и с помощью рекурсии.

[_Swetlana]

program stairs1_rekurrent;
const n = 8;
var T: array[0..n] of integer;
j: integer;
begin
  T[0]: = 0; T[1]: = 1;
  for j: = 2 to n do
     T[j]: = T[j–1]+T[j–2];
writeln(T[8] );
end.

program stairs1_rekursia;
  function T(y: integer): integer;
    begin
      if y = 0 then T: = 0
      else if y = 1 then T: = 1
      else T: = T(y-1) + T(y-2);
    end;
begin //main
  writeln(T(8))
end.

Разумеется, более эффективным и по вычислительной сложности, и по расходу памяти является первый способ (метод динамического программирования).
Рекурсия 1) многократно вычисляет одни и те же значения функции; 2) сохраняет в стеке аргументы всей цепочки вложенных рекурсивных вызовов.

[_Swetlana]

Усложним задачу №1. Пусть в условиях предыдущей задаче нам нужно уметь подсчитывать число программ, преобразующих целое число a в целое число z.

Задача №2
У исполнителя есть  две команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
Заданы два целых числа a и b. Сколько существует программ, которые преобразуют исходное число a в число z?
Решение
Пусть T(j,k) – количество способов получения числа k из числа j. Запишем для новой функции новое рекуррентное соотношение.
Если j > k, то число k получить из j нельзя. Поэтому T(j,k) = 0.
Если j = k, то  T(j,k) = 1.
Запишем рекуррентные соотношения для j < k:
T(j,k) = T(j,k–1) + T(j,k–2).
Например, подсчитаем число способов получения числа -2 из числа -4 (которых, разумеется, столько же, сколько способов получения числа 4 из числа 2).
T(-4, -2) = T(-4, -3) + T(-4, -4) = T(-4, -4) + T(-4, -5) + T(-4, -4) = 1 + 0 + 1 = 2

К функции в рекурсивном варианте программы добавляем ещё один параметр – начальное число j.
program stairs2_rekursia;
//T возвращает число способов, к-ми из числа j можно получить число k
function T(j, k: integer): integer;
begin
  if j > k then T:= 0
  else if j = k then T:= 1
  else T:= T(j,k-1) + T(j,k-2);
end;
begin
  writeln(T(-4,-2))
end.

В табличном варианте ничего менять не нужно. Только одномерный массив теперь нумеруется от a–1 до z. Откуда берётся a–1: если z = a+1, то по рекуррентной формуле придётся вычислять T(a+1–2) = T(a–1).
program stairs2_rekurrent;
const a= -4; z= -2;
//T возвращает число способов, к-ми из числа a можно получить число z
var T: array[a-1..z] of integer;
i: integer;
begin
  T[a-1]: = 0; // из a получить a-1 нельзя
  T[a]: = 1;  //из a получить a можно единственным способом 
  for i: = a+1 to z do T: = T[i-1]+T[i-2];
writeln(T[z] );
end.

[_Swetlana]

Усложним задачу №2, добавив третью команду удвоения числа.
Задача №3
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья  – умножает на 2.
Программа для исполнителя – это последовательность команд. Заданы два целых числа a и b. Сколько существует программ, которые преобразуют исходное число a в число b?
Решение
Пусть T(j, k) – количество способов получения числа k из числа j.
Если j > k, то число k получить из j нельзя. Поэтому T(j, k) = 0.
Если j = k, то  T(j, k) = 1.
Запишем рекуррентные соотношения для j < k:
T(j, k) = T(j, k–1) + T(j, k–2) +  T(j, k div 2), если k> 0 и k – чётное,
и T(j, k) = T(j, k–1) + T(j, k–2), если k<=0 (неотр. число при умножении не увеличивается) или k – нечётное.

Например, подсчитаем число способов получения числа 2 из числа -2.
T(-2, 2) = T(-2, 1) + T(-2, 0) + T(-2, 1)  = 2*T(-2, 1) + T(-2, -1) + T(-2, -2) =
2* T(-2, 1) + 1 +1 = 2*( T(-2, 0) + T(-2, -1)) + 2 = 2*(T(-2,-1) + T(-2,-2) + T(-2, -1)) + 2=
2*3 + 2 = 8.

К функции в рекурсивном варианте программы добавляем ещё один параметр – начальное число j.
program stairs2_rekursia;
//T возвращает число способов, к-ми из числа j можно получить число k
function T(j, k: integer): integer;
begin
  if j > k then T:= 0
  else if j = k then T:= 1
  else if (k > 0) and (k mod 2 = 0) then T:= T(j,k-1) + T(j,k-2) + T(j,k div 2)
  else T:= T(j,k-1) + T(j,k-2)
end;
begin
  writeln(T(-2,2))
end.

Табличный вариант
program stairs2_rekurrent;
const a= -2; z= 2;
//T возвращает число способов, к-ми из числа a можно получить число z
var T: array[a-1..z] of integer;
j: integer;
begin
  T[a-1]: = 0; // из a получить a-1 нельзя
  T[a]: = 1;  //из a получить a можно единственным способом 
  for j: = a+1 to z do
     if (j > 0) and (j mod 2 = 0) then T[j]: = T[j-1]+T[j-2] + T[j div 2]
     else T[j]: = T[j-1]+T[j-2];
writeln(T[z] );
end.

[Зритель]

Спасибо, очень интересно! Узнал сегодня что-то новое.

Некоторые компиляторы например GHC Haskell и Guile Scheme оптимизируют рекурсию и кладут данные на кучу, поощряя ленивое решение задачи.

С другой стороны, в реальных задачах массивы данных наверняка исчисляются миллионами и даже не факт, что всё уместится в оперативную память, не говоря уже про стек. Тогда надо динамически выделять-освобождать память на куче и параллельно писать-читать из буферного файла.

[_Swetlana]

Некоторые компиляторы например GHC Haskell и Guile Scheme оптимизируют рекурсию и кладут данные на кучу, поощряя ленивое решение задачи.

Кто такой Guile Scheme не знаю, увы. А Haskell сейчас широко используется для обучения функциональному программированию. Haskell и Prolog просто обязаны убирать хвостовую рекурсию.
Но, какую хвостовую рекурсию? Рекурсию восходящего типа, когда функция заканчивается рекурсивным вызовом.
А в решении, предложенном авторами задачи, есть отложенное действие: сложение результатов двух-трёх рекурсивных вызовов. Такую рекурсию не оптимизируешь, насколько я понимаю.