≡ информатика
сайты - меню - вход - новости




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

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

 

1. прибавь 2,

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

 

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

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

 

Пояснение.

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

 

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

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

 

2) Пусть n делится на 3. Тогда R(n) = R(n/3)+R(n-2) (если n>3).

При n=3 R(n) = 2 (два способа: прибавлением двойки или однократным умножением на 3). Поэтому достаточно по индукции вычислить значения R(n) для всех нечетных чисел, кратных трем и не превосходящих 31.

Имеем:

R(1)= 1

R(3) = 2 = R(5)=R(7)

R(9) = R(3)+R(7) = 2+2 = 4 = R(11) = R(13)

R(15) = R(5)+R(13) = 2+4 = 6 = R(17) = R(19)

R(21) = R(7)+R(19) = 2+6 = 8 = R(23) = R(25)

R(27) = R(9)+R(25) = 4+8 =12 = R(29) = R(31)

 

Ответ: 12.

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

 

Очевидно, из числа 1 нельзя получить четное число. Будем решать поставленную задачу последовательно для чисел 1, 3, 5,…, 31 (то есть для каждого из таких чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, обозначим R(n). Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего нечетного числа с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего нечетного числа: R(i)=R(i-2). Если число на 3 делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда R(i)=R(i-2) + R(i/3). Заполним соответствующую таблицу по приведенным формулам слева направо:

 

 

135791113151719212325272931
1222444666888121212

Источник: Де­мон­стра­ци­он­ная версия ЕГЭ—2015 по информатике.