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


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

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

 

1. прибавь 1,

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

 

Первая из них увеличивает число на экране на 1, вторая — умножает его на 4.

Программа для Увеличителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 32?

Ответ обоснуйте.

Решение.

Обозначим R(n) — количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее число, кратное четырем, не превосходящее n.

Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 32.

 

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

1. Если n не делится на 4, то тогда R (n) = R(T(n)), так как существует

единственный способ получения n из T(n) - прибавлением единиц.

 

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

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 выполнено: R(n) = 2 (два способа: прибавлением трех единиц или

однократным умножением на 4).

Поэтому достаточно по индукции вычислить значения R(n) для всех нечётных

чисел, кратных четырем и не превосходящих 32.

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29) = R(30) = R(31)

R(32) = R(8) + R(31) = 3 + 12 = 15

 

 

Ответ: 15.

Другой способ решения

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

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

 

12345678910111213141516
1112222333344446
17181920212223242526272829303132
6668888101010101212121215

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

 

148121620242832
123468101215

 

Ответ: 15.