Задача к ЕГЭ по информатике на тему «количество программ из a в b» №1

Просмотров 8 Комментарии 0

Исполнитель М.Е.М.249 преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
преобразует целое число, записанное на экране.
1. Прибавить 1,
2. Прибавить 2,
3. Прибавить предыдущее.
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.).
Программа для исполнителя М.Е.М.249 – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 10?

Обозначим число программ, преобразующих число 2 в число n как $R (n).$ Тогда число $n$ может быть получено либо прибавлением к $n − 1,$ либо к $n − 2,$ либо из некоторого числа $\text{[math]}$ увеличением на $x − 1,$ так что $n = x + x − 1,$ откуда $n+1- x = 2 ;$ так могут быть получены только нечетные числа.
Тогда для четных чисел $R (n ) = R(n − 1) + R (n − 2),$ а для нечетных — $R(n) = R (n − 1) + R (n − 2) + R (n+21$ ). Заполним таблицу по данным формулам: