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




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

У исполнителя Калькулятор две команды, которым присвоены номера:

 

1. прибавь 2,

2. умножь на 5.

 

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.

Программа для Калькулятора — это последовательность команд.

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

Решение.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 5, не превосходящее n. Заметим, что нечётные числа мы никак получить не можем. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может пре-восходить (50 - 2) / 2 = 24.

 

Верны следующие соотношения:

1. Если n не делится на 10, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением двоек.

 

2. Пусть n делится на 5.

Тогда R(n) = R(n / 5) + R(n - 2)= R(n / 5) + R(n - 10) (если n > 10).

При n = 10 R(n) = 2 (два способа: прибавлением четырёх двоек или однократным умножением на 5).

Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных десяти и не превосходящих 50: сначала вычисляем R(2), затем R(10), R(20) и т. д.

Имеем:

R(2) = 1 = R(4) = R(6) = R(8),

R(10) = 2 = R(2) + R(8),

R(20) = R(4) + R(10) =1 + 2 = 3 = R(22) = R(28),

R(30) = R(6) + R(20) =1 + 3 = 4 = R(32) = R(38),

R(40) = R(8) + R(30) =1 + 4 = 5 = R(42) = R(48),

R(50) = R(10) + R(40) = 2 + 5 = 7.

 

Ответ: 7.

 

Другая форма решения.

Будем решать поставленную задачу последовательно для чисел 2, 4, 6, 50 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Заметим, что нечётные числа мы никак получить не можем. Количество программ, которые преобразуют число 2 в число n, будем обозначать через R(n). Число 2 у нас уже есть, значит, его можно получить с помощью «пустой» программы. Любая непустая программа увеличит исходное число, т. е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на пять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа:

Если число на пять делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда . Заполним соответствующую таблицу по приведёным формулам слева направо:

 

24681012141618202224262830
111122222333334
3436384042444850
44455557

При этом ячейки, относящиеся к числам, которые не делятся на 5, можно в решении и опустить (за исключением первого числа):

 

21020304050
123457

 

Ответ: 7.