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

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

Исполнитель МЕГАТРОН преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2.
Программа для МЕГАТРОНа — это последовательность команд.
Сколько есть программ, которые преобразует число 1 в число 9?

Количество программ, которые преобразуют число 1 в число $n,$ обозначим $R(n).$ Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, $R (1) = 1.$ Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда $R (2) = 1.$ Число “3” можем получить из чисел 1 и 2 — $R (3) = R(1) + R (2 ) = 2.$ Число “4” получаем из 2 и 3 — $R (4) = R (2) + R(3) = 3.$ Можем заметить, что количество программ для получения числа n находится по формуле — $R(n ) = R (n − 2) + R (n − 1).$ Составим таблицу по данной формуле:

|--|---|--|--|--|--|---|---|----| |1-|2--|3-|4-|5-|6-|-7-|-8-|-9--| |1 |1 |2 |3 |5 |8 |13 |21 |34 | --------------------------------

Отсюда видим, что имеем 34 возможных программ для получения числа 9.

Ответ: 34