Задание №937 ЕГЭ Информатике

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

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

 

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

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

 

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

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

При n = 9 R(n)) = 1 (один способ: прибавлением тройки).

Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 3 и не превосходящих 34: сначала вычисляем R(4), затем R(6), R(9) и т. д.

Имеем:

R(4)=1

R(6) = R(9)=1 = R(5) = R(10)= R(11),

R(12) = R(4)+R(9)=1+1=2= R(13)=R(14),

R(15) = R(5) + R(12) =1 + 2 = 3= R(16) = R(17),

R(18) = R(6) + R(15) =1 + 3 = 4= R(19) = R(20),

R(21) = R(7) + R(18) =1 + 4 = 5= R(22) = R(23),

R(24) = R(8) + R(21) =1 + 5 =6= R(25) = R(26),

R(27) = R(9) + R(24) =1 + 6 =7= R(28) = R(29),

R(30) = R(9) + R(27) =1 + 7 =8= R(31) = R(32),

R(33) = R(10) + R(30) =1 + 8 =9= R(34).

 

Ответ: 9.

 

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

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

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

 

 

 

4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1	1	1	1	1	1	1	1	2	2	2	3	3	3	4
19	20	21	22	23	24	25	26	27	28	29	30	31	32	33
4	4	5	5	5	6	6	6	7	7	7	8	8	8	9
34
9

 

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

 

 

4	6	9	12	15	18	21	24	27	30	33	34
1	1	1	2	3	4	5	6	7	8	9	9

 

 

Ответ: 9.