СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 22 № 9314

Исполнитель Б22 преобразует целое число, записанное на экране.

У исполнителя три команды, каждой команде присвоен номер:

        1. Прибавь 1

        2. Прибавь 2

        3. Прибавь предыдущее

Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя Б22 – это последовательность команд.

Сколько существует программ, которые число 3 преобразуют в число 10?

Решение.

Пусть R(x) — количество программ, которыми можно из 3 получить x.

Заметим, что чётное число нельзя получить с использованием команды 3, поскольку в её процессе складывается чётное и нечётное число. Также заметим, что для того, чтобы получить x с помощью команды 3, нужно применять её к числу .

Вычислим последовательно значение R:

R(0) = 0

R(1) = 0

R(2) = 0

R(3) = 1

R(4) = R(3) + R(2) = 1 + 0 = 1

R(5) = R(4) + R(3) + R(3) = 1 + 1 + 1 = 3

R(6) = R(5) + R(4) = 3 + 1 = 4

R(7) = R(6) + R(5) + R(4) = 4 + 3 + 1 = 8

R(8) = R(7) + R(6) = 8 + 4 = 12

R(9) = R(8) + R(7) + R(5) = 12 + 8 + 3 = 23

R(10) = R(9) + R(8) = 23 + 12 = 35


Аналоги к заданию № 9206: 9314 Все