1. Исполнитель Увеличитель145 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 4

3. Прибавь 5

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

Решение.

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.

Все команды увеличивают исходное число, поэтому количество команд не может превосходить (46 − 30) = 16. При этом минимальное количество команд — 4.

Таким образом, команд может быть 4, 5, 6, … или 16. Порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке.

Рассмотрим все возможные наборы и вычислим количество вариантов рассположения команд в них.

Набор 11 … 1111 имеет один возможный вариант.

Набор 11 … 2 — 13 вариантов.

Набор 221111 1111 — 45 возможных вариантов расположения: это число перестановок с повторениями 10!/(8!·2!).

Набор 222 1111 — 35 вариантов.

Набор 2222 — 1 вариант.

Набор 3331 — 4 варианта.

Набор 33111 111 — 28 вариантов.

Набор 311…11 — 12 вариантов.

Набор 322111 — 60 вариантов.

Набор 32311 — 30 вариантов.

Набор 321111111 — 72 варианта.

 

Всего имеем: 1 + 13 + 45 + 35 + 1 + 4 + 32 + 12 + 60 + 30 + 72 = 301 программа.

 
Ответ: 301.

2. У исполнителя Множик есть две команды:

 

1. умножь на 4,

2. подели на 2.

 

Первая из них увеличивает число на экране в 4 раза, вторая – уменьшает его в 2 раза.

Программа для Множика – это последовательность команд. Сколько различных чисел можно получить из числа 1024 с помощью программы, которая содержит ровно 10 команд?

Решение.

От перестановки множителей произведение не меняется, каждой программе соответствует одно число, поэтому посчитав количество программ (с точностью до перестановки), найдём количество различных чисел.

 

Если в программе n команд 1, тогда в ней будет 10 — n команд 2, n изменяется от 0 до 10. Всего 11 программ, следовательно, 11 чисел.

 

Ответ: 11.

3. Исполнитель Май17 преобразует число на экране.

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

1. Прибавить 1

2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение.

Используем метод динамического программирования. заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] + dp[i-3]

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

Далее будут приведены значения в ячейках dp от 1 до 17: 1 1 1 2 3 4 6 9 13 13 13 26 39 52 78 117 169.

 
Ответ: 169.

4. Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Решение.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] — если i — четное.

dp[i]=dp[i-1] + dp[(i-1)/2] — если i нечетное;

Но при этом если i-1 = 24 или (i-1)/2 = 24, то его не учитываем. Можно заметить, что для числа 25 будет формула

dp[25]=dp[24] + dp[12], а т.к. dp[24] не считаем, то ответ совпадает с dp[12].

Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.

 
 
Ответ: 10.

5. Исполнитель РазДваПять преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 5

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 5.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 16, и при этом траектория вычислений содержит число 8 и не содержит числа 10?

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 4 траектория будет состоять из чисел 20, 21, 42.

Решение.

Искомое количество программ равно количеству программ, получающих из числа 1 число 16. Траектория вычислений не должна содержать числа 10 и должна содержать число 8.

Пусть R(n) — количество программ, которые число 1 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n-5).

 

R(2) = 2

R(3) = 2

R(4) = 4

R(5) = 4

R(6) = 7

R(7) = 9

R(8) = 15

R(9) = 15

R(10) = 0

R(11) = 0

R(12) = 0

R(13) = 15

R(14) = 30

R(15) = 30

R(16) = 45

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 45.

 
Ответ: 45.

6. У исполнителя Тритон две команды, которым присвоены номера:

 

1. прибавь 1,

2. прибавь 3.

 

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3. Программа для Тритона — это последовательность команд. Сколько существует программ, которые число 17 преобразуют в число 30?

Решение.

Для сложения справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.

 

Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 30 — 17 = 13. При этом минимальное количество команд — 5 (т. к. [30 − 17]/3 = 4). Заметим, что 17 — нечетное, а 30 — четное. Поскольку обе команды увеличивают исходное число на нечетное число, то количество команд должно быть нечетным.

 

Иначе говоря, команд может быть 5, 7, 9, 11 или 13. Пяти командам соответствует набор 22221 (5 возможных вариантов расположения), семи командам — набор 2221111 (35 возможных вариантов расположения: это число перестановок с повторениями P7(3,4) = 7!/(3! · 4!)), девяти командам — 221111111 (36 возможных вариантов расположения), 11 командам — 21111111111 (11 возможных вариантов расположения), 13 командам — 11111111111111 (1 вариант расположения). Всего имеем 88 программ.

 

Ответ: 88.

7. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 2 в число 14 и при этом траектория вычислений содержит число 10?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 2 число 10, на количество программ, получающих из числа 10 число 14. Траектория вычислений должна содержать число 10.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n, а F(n) — количество программ, которые число 10 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n-3).

F(n) = F(n−1) + F(n/2)(если n — чётно) + F(n-3).

 

R(2) = 1

R(3) = 1

R(4) = 2

R(5) = 3

R(6) = 5

R(7) = 7

R(8) = 12

R(9) = 17

R(10) = 27

 

F(10) = 1

F(11) = 1

F(12) = 1

F(13) = 2

F(14) = 3

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 27 · 3 = 81.

 
Ответ: 81.

8. У исполнителя Кузнечик две команды:

 

1. прибавь 7

2. вычти 5

 

Первая из них увеличивает число на экране на 7, вторая – уменьшает его на 5 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд.

Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд?

Решение.

От перестановки мест слагаемых сумма не меняется, так что при количестве команд «1», равному n, сумма получается следующая:

 
n * (7) + (-5) * (7 — n) = 7n — 35 + 5n = 12n — 35, а так как n принимает значения от 0 до 7, то всего возможных чисел будет 8.
 

Правильный ответ: 8.

9. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третье умножает его на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 50 и при этом траектория вычислений содержит число 15 и не содержит числа 33?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 18, 19, 38.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 15, на количество программ, получающих из числа 15 число 50. Траектория вычислений не должна содержать числа 33.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n/3)(если n кратно 3).

 

R(3) = 1.

R(4) = R(3) = 1.

R(5) = R(3) = 1.

R(6) = R(5) + R(3) = 2.

R(7) = R(6) = 2.

R(8) = R(7) + R(4) = 3.

R(9) = R(8) + R(3) = 4.

R(10) = R(9) + R(5) = 5.

R(11) = R(10) = 5.

R(12) = R(11) + R(6) + R(4) = 8.

R(13) = R(12) = 8.

R(14) = R(13) + R(7) = 10.

R(15) = R(14) + R(5) = 11.

 

Программ для получения числа 50 из числа 15 всего 11, их можно перечислить:

311111, 1311, 1121…1, 11121…1, 111121…1, 1111121…1, 11111121…1, 11111112111111, 1111111121111, 111111111211, 11111111112.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 11 · 11 = 121.

 
Примечание. 1…1 — последовательность из единиц.
 
Ответ: 121.

10. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 2 в число 14 и при этом траектория вычислений не содержит чисел 5 и 10?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Решение.

Искомое количество программ равно количеству программ, получающих из числа 2 число 14. Траектория вычислений не должна содержать чисел 5 и 10.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n-3).

 

R(2) = 1

R(3) = R(2) = 1

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

R(5) = 0

R(6) = R(3) + R(3) = 2

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

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

R(9) = R(8) + R(6) = 8

R(10) = 0

R(11) = R(8) = 6

R(12) = R(11) + R(6) + R(9) = 16

R(13) = R(12) = 16

R(14) = R(13) + R(7) + R(11) = 26

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 26.

 
Ответ: 26.

11. Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 2 число 8, на количество программ, получающих из числа 8 число 10, и на количество программ, получающих из числа 10 число 12.

Будем решать задачу с конца. Число 12 из числа 10 можно получить двумя способами (10+1+1; 10+2). Число 10 из числа 8 можно получить двумя способами (8+1+1; 8+2). Остается узнать количество способов получения числа 8 из числа 2. Начнем свои рассуждения с числа 3, т.к. двойка это начальное число. Тройку можно получить только одним способом – прибавив 1. Четверку получим двумя способами – прибавив единицу к тройке или добавив двойку к двойке и т. д. Запишем эти рассуждения в следующем виде:

 

R(2) = 1

R(3) = R(2) = 1

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

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

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

R(7) = R(6) + R(5) = 6 + 3 = 9

R(8) = R(7) + R(6) = 9 + 6 = 15

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно R(2) * R(8) * R(10) * R(12) = 1 * 15 * 2 * 2 = 60.

 
Ответ: 60.

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

 

1. прибавь 3,

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

 

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

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

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

Решение.

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

Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить (93- 3) / 3= 31.

 

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

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

 

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

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

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

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

Имеем:

R(3)=1=R(6)

R(9) = 2 = R(12) = R(15),

R(18) = R(6)+R(9)=1+2=3= R(21)=R(24),

R(27) = R(9) + R(18) =2 + 3 = 5 = R(30) = R(33),

R(36) = R(12) + R(27) =2 + 5 = 7= R(39) = R(42),

R(45) = R(15) + R(36) =2 + 7 = 9= R(48) = R(51),

R(54) = R(18) + R(45) =3 + 9 =12= R(57) = R(60),

R(63) = R(21) + R(54) =3 + 12 =15= R(66) = R(69),

R(72) = R(24) + R(63) =3 + 15 =18= R(75) = R(78),

R(81) = R(27) + R(72) =5 + 18 =23= R(84) = R(87),

R(90) = R(30) + R(81) =5 + 23 =28= R(93).

 
Ответ: 28.
 

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

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

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

 

3 6 9 12 15 18 21 24 27 30 33 36 39 42 45
1 1 2 2 2 3 3 3 5 5 5 7 7 7 9
48 51 54 57 60 63 66 69 72 75 78 81 84 87 90
9 9 12 12 12 15 15 15 18 18 18 23 23 23 28
93
28

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

 

3 9 18 27 36 45 54 63 72 81 90 93
1 2 3 5 7 9 12 15 18 23 28 28

 
Ответ: 28.

13. Исполнитель Фибо преобразует число на экране.

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

1. Прибавить 1

2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.

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

Сколько существует программ, которые преобразуют исходное число 2 в число 18 и при этом траектория вычислений содержит число 9 и не содержит числа 14?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 2 число 9, на количество программ, получающих из числа 9 число 13 и на количество программ, получающих из числа 15 число 18, поскольку траектория вычислений не должна содержать числа 14.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n, P(n) — количество программ, которые число 9 преобразуют в число n, а F(n) — количество программ, которые преобразуют число 15 в число n.

Для всех n > 4 верны следующие соотношения:

1. R(n) = R(n − 1) + R(n − 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n − 1) + P(n − 2) и F(n) = F(n − 1) + F(n − 2).

Последовательно вычислим значения R(n):

 

R(2) = 1.

R(3) = 1.

R(4) = R(2) + R(3) = 2.

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

R(6) = R(5) + R(4) = 5.

R(7) = R(6) + R(5) = 8.

R(8) = R(7) + R(6) = 13.

R(9) = R(8) + R(7) = 21.

 

Теперь вычислим значения P(n):

 

P(9) = 1.

P(10) = 1.

P(11) = P(9) + P(10) = 2.

P(12) = P(10) + P(11) = 3.

P(13) = P(11) + P(12) = 5.

 

Теперь вычислим значения F(n):

 

F(15) = 1.

F(16) = 1.

F(17) = F(15) + F(16) = 2.

F(18) = F(16) + F(17) = 3.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 21 · 5 · 3 = 315.

 
Ответ: 315.

14. У исполнителя Множитель2 две команды:

 

1.умножь на 5

2.умножь на 3

 

Первая из них увеличивает число на экране в 5 раз, вторая – увеличивает его в 3 раза. Программа для исполнителя Множитель2 – это последовательность команд.

Сколько различных чисел можно получить из числа 81 с помощью программы, которая содержит ровно 4 команды?

Решение.

Всего 4 команды.

 

От перестановки мест множителей произведение не меняется.

 

Пусть n — количество команды «1», тогда конечное число: 81 * 5n * 34 — n = 81 * 34 * (5 / 3)n = 812 * (5 / 3)n,

 
где n меняется от 0 до 4, следовательно, разных значений будет 5.
 

Ответ: 5.

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

 

1. прибавь 2

2. прибавь 3.

 

Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

Решение.

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения.

 

Каждой программе соответствует одно число, поэтому посчитав количество возможных программ (с точностью до перестановки), найдём количество различных чисел.

 

Если в программе n команд 1, тогда в ней будет 10-n команд 2. n изменяется от 0 до 10. Всего 11 программ, следовательно, 11 чисел.

 

Ответ: 11.

16. Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

3. Умножить на 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 26 и при этом траектория вычислений содержит число 12 и не содержит число 22?

Решение.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

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

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

Тогда R(n) = R(n — 1) + R(n / 2).

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

Тогда R(n) = R(n / 3) + R(n — 1).

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

Тогда R(n) = R(n — 1) + R(n / 2) + R(n / 3) .

 

С её помощью последовательно вычислим значения R(n):

 

R(2) = 1

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

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

R(5) = R(4) = 2

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

R(7) = R(6) = 4

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

R(9) = R(8) + R(3) = 6 + 1 = 7

R(10) = R(9) + R(5) = 7 + 2 = 9

R(11) = R(10) = 9

R(12) = R(11) + R(6) + R(4) = 9 + 4 + 2 = 15

 
 

Так как в траектории должно присутствовать число 12, то для всех следующих R(n) нельзя использовать при пересчёте R(m) такие, что m < 12.

 

R(13) = R(12) = 15

R(22) = R(21) = R(20) = R(19) = R(18) = R(17) = R(16) = R(15) = R(14) = 15

 

Число 22 наоборот, не должно встречаться в траектории, поэтому не будем учитывать R(22), то есть все следующие R(n) будем подсчитывать без R(22).

 

R(23) = 0

R(24) = R(23) + R(12) = 15

R(25) = R(24) = 15

R(26) = R(25) + R(13) = 15 + 15 = 30

 
Ответ: 30.

17. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 16 и при этом траектория вычислений не содержит чисел 6 и 12?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Решение.

Искомое количество программ равно количеству программ, получающих из числа 3 число 16. Траектория вычислений не должна содержать чисел 6 и 12.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n-3).

 

R(3) = 1

R(4) = 1

R(5) = 1

R(6) = 0

R(7) = 1

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

R(9) = R(8) = 3

R(10) = R(5) + R(7) + R(9) = 5

R(11) = R(8) + R(10) = 8

R(12) = 0

R(13) = R(10) = 5

R(14) = R(7) + R(11) + R(13) = 14

R(15) = R(14) = 14

R(16) = R(8) + R(13) + R(15) = 22

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 22.

 
Ответ: 22.

18. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 16 и при этом траектория вычислений содержит число 12?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 12, на количество программ, получающих из числа 12 число 16. Траектория вычислений должна содержать число 12.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n, а F(n) — количество программ, которые число 12 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно) + R(n-3).

F(n) = F(n−1) + F(n/2)(если n — чётно) + F(n-3).

 

R(3) = 1

R(4) = 1

R(5) = 1

R(6) = 3

R(7) = 4

R(8) = 6

R(9) = 9

R(10) = 14

R(11) = 20

R(12) = 32

 

F(12) = 1

F(13) = 1

F(14) = 1

F(15) = 2

F(16) = 3

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 32 · 3 = 96.

 
Ответ: 96.

19. Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21, при этом траектория вычислений содержит число 10 и не содержит число 17?

Решение.

Нужно найти количество программ, которые из 1 получают 10, количество программ, которые из 10 получают 21, но не проходит через 17 и перемножить найденные значения. Сначала найдём количество программ, получающих 10 из 1.

 

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

 

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

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

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

Если n > 1, то R(n) = R(n / 2) + R(n — 1).

Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).

 

Теперь можно постепенно вычислить все значения:

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

R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(9) = 4 + 10 = 14

 

Программ, получающих из числа 10 число 21, и не содержащих 17 всего одна: 21.

 

Тем самым, находим ответ: 14 · 1 = 14.

 
Ответ: 14.

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

 

1. прибавь 1.

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

 

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

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

Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команды?

Решение.

*Следующее рассуждение удобно записывать в виде дерева.

 

С помощью одной команды из числа 2 можно получить два различных числа:

2 + 1 = 3,

2 * 2 = 4.

 

С помощью двух команд можно получить четыре числа:

3 + 1 = 4,

3 * 2 = 6,

4 + 1 = 5,

4 * 2 = 8.

 

С помощью трёх команд получаются следующие восемь различных чисел:

4 + 1 = 5,

4 * 2 = 8,

5 + 1 = 6,

5 * 2 = 10,

8 + 1 = 9,

8 * 2 = 16,

6 + 1 = 7,

6 * 2 = 12.

 

С помощью четырёх команд из 8 чисел, получившихся выше, получится 16 чисел. Но заметим, что

5 * 2 = 10 и 9 + 1 = 10, поэтому различных из них будет 15 чисел.

 

Ответ: 15.

21. Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

 

1. прибавь 1

2. сделай нечётное

 

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ – это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Решение.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — кол-во способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] — если i — четное.

dp[i]=dp[i-1] + dp[(i-1)/2] — если i нечетное.

Но при этом, если i-1 = 26 или (i-1)/2 = 26, то оно не учитывается. Можно заметить, что для числа 27 будет формула dp[27]=dp[26] + dp[13], а поскольку dp[26] не считается, то ответ совпадает с dp[13].

Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 13): 1 1 2 2 3 3 5 5 7 7 10 10 13.

 
Ответ: 13.

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

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

 
1. Прибавить 1
2. Умножить на 2
 

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Тренер —  это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 30 и при этом траектория вычислений содержит числа 10 и 21?

Траектория должна содержать оба указанных числа. Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.

Решение.

Нужно найти количество программ, которые из 1 получают 10, количество программ, которые из 10 получают 21, количество программ, которые из 21 получают 30 и перемножить найденные значения. Сначала найдём количество программ, получающих 10 из 1.

 

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

 

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

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

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

Если n > 1, то R(n) = R(n / 2) + R(n — 1).

Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).

 

Теперь можно постепенно вычислить все значения:

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

R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(9) = 4 + 10 = 14

 

Программ, получающих из числа 10 число 21 достаточно мало, можно их просто перечислить: 21, 11111111111.

А программ, получающих из числа 21 в число 30 всего один способ: добавление единиц.

 

Тем самым, находим ответ: 

Ответ: 28.

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

 

1. прибавь 1,

2. сделай чётное,

3. сделай нечётное.

 

Первая из них увеличивает на 1 число x на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21.

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?

Решение.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

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

1. Если n нечётное, то тогда R(n) = R(n − 1) + R((n − 1) \ 2), (если n > 5) так как есть два способа получения n: прибавлением единицы или использованием команды 3.

2. Если n чётное, то тогда R(n) = R(n − 1) + R(n \ 2), (если n > 4) так как есть два способа получения n: прибавлением единицы или использованием команды 2.

Достаточно вычислить значения R(n) для всех чисел не превосходящих 16.

Имеем:

R(3) = 1,

R(4) = 2,

R(5) = 3 ,

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

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

R(8) = R(7) + R(4) = 5 + 2 = 7,

R(9) = R(8) + R(4) = 7 + 2 = 9,

R(10) = R(9) + R(5) = 9 + 3 = 12,

R(11) = R(10) + R(5) = 12 + 3 = 15,

R(12) = R(11) + R(6) = 15 + 4 = 19,

R(13) = R(12) + R(6) = 19 + 4 = 23,

R(14) = R(13) + R(7) = 23 + 5 = 28,

R(15) = R(14) + R(7) = 28 + 5 = 33,

R(16) = R(15) + R(8) = 33 + 7 = 40,

 
 
Ответ: 40.

24. Исполнитель ТР4 преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя ТР4 — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 2 в число 35 и при этом траектория вычислений содержит число 15 и не содержит числа 31?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 2 число 15, на количество программ, получающих из числа 15 число 35, траектория вычислений не должна содержать числа 31.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

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

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

Если n > 2, то R(n) = R(n / 2) + R(n — 1).

Если n = 2 то R(n) = 1 (два способа: прибавление единицы и удвоение).

 

R(2) = 1.

R(3) = 1.

R(4) = R(2) + R(3) = 2.

R(5) = R(4) = 2.

R(6) = R(3) + R(5) = 3.

R(7) = R(6) = 3.

R(8) = R(4) + R(7) = 5.

R(9) = R(8) = 5.

R(10) = R(5) + R(9) = 7.

R(11) = R(10) = 7.

R(12) = R(6) + R(11) = 10.

R(13) = R(12) = 10.

R(14) = R(7) + R(13) = 13.

R(15) = R(14) = 13.

 

Программ для получения числа 35 из числа 15 всего 2, можно их перечислить: 12111 и 1121.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 13 · 2 = 26.

 
Ответ: 26.

25. Исполнитель Тренер преобразует число на экране.

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

1. Прибавить 1

2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.

Программа для исполнителя Тренер – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 12?

Решение.

Пусть  — количество способов получить из числа 1 число х. Заметим, что для x > 2: .

 












 
Ответ: 144.

26. Исполнитель преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

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

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

R(n) = R(n−1) + R(n/2)(если n — чётно).

R(n) = R(n−1) (если n — нечётно).

 

R(2) = 1

R(3) = 1

R(4) = 2

R(5) = 2

R(6) = 3

R(7) = 3

R(8) = 5

R(9) = 5

R(10) = 7

R(11) = 7

R(12) = 10

R(13) = 10

R(14) = 13

 

Заметим, что R(29) = R(28), а R(28) = R(27) + R(14). Число 27 можно получить из числа 14 единственным способом: последовательным прибавлением единиц, то есть R(27) = R(14) = 13.

Таким образом, количество программ, удовлетворяющих условию задачи, равно R(29) = R(28) = 13

+ 13 = 26.
 
Ответ: 26.

27. Исполнитель РазДваТри преобразует число на экране.

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 15, и при этом траектория вычислений содержит число 9 и не содержит числа 13?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 4 траектория будет состоять из чисел 12, 13, 15.

Решение.

Искомое количество программ равно количеству программ, получающих из числа 1 число 15. Траектория вычислений не должна содержать числа 13 и должна содержать число 9.

Пусть R(n) — количество программ, которые число 1 преобразуют в число n, P(n) — количество программ, которые число 9 преобразуют в число n. Для учёта того, что траектория вычислений не содержит число 13, не будем учитывать R(13) при подсчёте соотношений.

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

1. R(n) = R(n−1) + R(n−2) + R(n/3) — если n делится на три, при n > 2.

2. R(n) = R(n−1) + R(n−2) — если n не делится на три, при n > 2.

 
 

R(1) = 1.

R(2) = 1.

R(3) = R(2) + R(1) + R(1) = 3.

R(4) = R(3) + R(2) = 4.

R(5) = R(4) + R(3) = 7.

R(6) = R(5) + R(4) + R(2) = 12.

R(7) = R(6) + R(5) = 19.

R(8) = R(7) + R(6) = 31.

R(9) = R(8) + R(7) + R(3) = 53.

 

P(10) = P(9) = 1.

P(11) = P(10) + P(9) = 2.

P(12) = P(11) + P(10) = 3.

P(14) = P(12) = 3.

P(15) = P(14) = 3.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 53 · 3 = 159.

 
Ответ: 159.

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

 

1. прибавь 1

2. прибавь 4.

 

Первая из них увеличивает число на экране на 1, вторая — на 4. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 3 команд?

Решение.

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения.

 

Каждой программе соответствует одно число, поэтому посчитав количество возможных программ (с точностью до перестановки), найдём количество различных чисел. При этом не будет повторяющихся чисел, поскольку

 

4 = 1 + 1 + 1 + 1,

 
т. е. команда 2 равносильна четырём командам 1, но у нас не более 3 команд.
 

Если в программе n команд 1, тогда оставшиеся будут командами 2. После одной команды n изменяется от 0 до 1. Всего 2 программы, следовательно, 2 числа.

 

После двух команд n изменяется от 0 до 2. Всего 3 программы, следовательно, 3 числа.

 

Аналогичным образом рассуждаем для трёх команд: получим 4 числа.

 

Суммируем количество получившихся чисел и учтём, что количество команд не более 3, а значит, если программа не содержит ни одной команды, то мы просто получим число 2.

 

Всего различных чисел: 2 + 3 + 4 + 1 = 10.

 

Ответ:10.

 

29. Исполнитель Фибо преобразует число на экране.

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

1. Прибавить 1

2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.

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

Сколько существует программ, которые преобразуют исходное число 3 в число 20 и при этом траектория вычислений содержит число 9 и не содержит числа 15?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 9, на количество программ, получающих из числа 9 число 14 и на количество программ, получающих из числа 16 число 20, поскольку траектория вычислений не должна содержать числа 15.

Пусть R(n) — количество программ, которые число 3 преобразуют в число n, P(n) — количество программ, которые число 9 преобразуют в число n, а F(n) — количество программ, которые преобразуют число 16 в число n.

Для всех n > 4 верны следующие соотношения:

1. R(n) = R(n − 1) + R(n − 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n − 1) + P(n − 2) и F(n) = F(n − 1) + F(n − 2).

Последовательно вычислим значения R(n):

 

R(3) = 1.

R(4) = 1.

R(5) = R(3) + R(4) = 2.

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

R(7) = R(6) + R(5) = 5.

R(8) = R(7) + R(6) = 8.

R(9) = R(8) + R(7) = 13.

 

Теперь вычислим значения P(n):

 

P(9) = 1.

P(10) = 1.

P(11) = P(9) + P(10) = 2.

P(12) = P(10) + P(11) = 3.

P(13) = P(11) + P(12) = 5.

P(14) = P(12) + P(13) = 8.

 

Теперь вычислим значения F(n):

 

F(16) = 1.

F(17) = 1.

F(18) = F(16) + F(17) = 2.

F(19) = F(17) + F(18) = 3.

F(20) = F(18) + F(19) = 5.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 13 · 8 · 5 = 520.

 
Ответ: 520.

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

 

1. прибавь 1

2. прибавь 2.

 

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

Решение.

*Следующее рассуждение удобно записывать в виде дерева.

 

С помощью одной команды из числа 2 можно получить 2 различных числа:

2 + 1 = 3,

2 + 2 = 4.

 

С помощью двух команд получаются числа:

3 + 1 = 4,

3 + 2 = 5,

4 + 1 = 5,

4 + 2 = 6.

 

Число 4 уже было, поэтому его не учитываем, а число 5 учитываем один раз, т.е. получили ещё 2 числа.

 

С помощью трёх команд получаются числа:

5 + 1 = 6,

5 + 2 = 7,

6 + 1 = 7,

6 + 2 = 8, т. е. ещё 2 различных числа.

 

По аналогии после чётырёх команд получится ещё два числа.

 

Суммируем количество получившихся чисел и учтём, что количество команд не более 4, а значит, если программа не содержит ни одной команды, то мы просто получим число 2.

 

Всего различных чисел: 2 * 4 + 1 = 9.

 

Ответ: 9.

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

 

1. прибавь 1

2. сделай чётное

3. сделай нечетное

4. умножь на 10

 

Первая из них увеличивает на 1 исходное число x, вторая умножает это число на 2, третья переводит число x в число 2x+1, четвертая умножает его на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21.

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

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

Решение.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

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

1. Если n нечётное, то тогда R(n) = R(n − 1) + R((n − 1) / 2), (если n > 3) так как есть два способа получения n: прибавлением единицы или использованием команды 3.

2. Если n чётное, но не делится на 10, то тогда R(n) = R(n − 1) + R(n / 2), (если n > 2) так как есть два способа получения n: прибавлением единицы или использованием команды 2.

3. Если n чётное и делится на 10, то тогда R(n) = R(n − 1) + R(n / 2) + R(n / 10), так как есть три способа получения n: прибавлением единицы, использованием команды 2 или использованием команды 4.

Достаточно вычислить значения R(n) для всех чисел не превосходящих 14.

Имеем:

R(1) = 1.

R(2) = R(1) + R(1) = 2,

R(3) = R(2) + R(1) = 3,

R(4) = R(3) + R(2) = 5,

R(5) = R(4) + R(2) = 5 + 2 = 7,

R(6) = R(5) + R(3) = 7+ 3 = 10,

R(7) = R(6) + R(3) = 10 + 3 = 13,

R(8) = R(7) + R(4) = 13 + 5 = 18,

R(9) = R(8) + R(4) = 18 + 5 = 23,

R(10) = R(9) + R(5) + R(1) = 23 + 7 +1 = 31,

R(11) = R(10) + R(5) = 31 + 7 = 38,

R(12) = R(11) + R(6) = 38 + 10 = 48,

R(13) = R(12) + R(6) = 48 + 10 = 58,

R(14) = R(13) + R(7) = 58 + 13 = 71.

 
Ответ: 71.

32. Исполнитель преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 1 число 10, на количество программ, получающих из числа 10 число 20.

Пусть R(n) — количество программ, которые число 1 преобразуют в число n, F(n) — количество программ, которые число 10 преобразуют в число n.

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

R(n) = R(n−1) + R(n/2)(если n — чётно).

 

R(1) = 1.

R(2) = R(1) + R(1) = 2.

R(3) = R(2) = 2.

R(4) = R(3) + R(2) = 2 + 2 = 4.

R(5) = R(4) = 4.

R(6) = R(5) + R(3) = 4 + 2 = 6.

R(7) = R(6) = 6.

R(8) = R(7) + R(4) = 6 + 4 = 10.

R(9) = R(8) = 10.

R(10) = R(9) + R(5) = 10 + 4 = 14.

 

F(10) = 1.

F(11) = F(10) = 1.

F(12) = F(11) = 1.

F(13) = F(12) = 1.

F(14) = F(13) = 1.

F(15) = F(14) = 1.

F(15) = F(14) = 1.

F(16) = F(15) = 1.

F(17) = F(16) = 1.

F(18) = F(17) = 1.

F(19) = F(18) = 1.

F(20) = F(19) + F(10) = 2.

 

Таким образом, количество программ, удовлетворяющих условию задачи равно 14 · 2 = 28.

 
Ответ: 28.

33. Исполнитель Вычислитель преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 3

3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третье увеличивает его на 2.

Программа для исполнителя Вычислитель — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 15 и при этом траектория вычислений содержит числа 10 и 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 1 число 15, при этом траектория вычислений должна содержать числа 10 и 12.

Пусть R(n) — количество программ, которые число 2 преобразуют в число n.

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

R(n) = R(n−1) + R(n/3)(если n — кратно 3) + R(n−2).

 

R(1) = 1.

R(2) = R(1) = 1.

R(3) = R(2) + R(1) + R(1) = 3.

R(4) = R(3) + R(2) = 4.

R(5) = R(4) + R(3) = 7.

R(6) = R(5) + R(2) + R(4) = 12.

R(7) = R(6) + R(5) = 19.

R(8) = R(7) + R(6) = 31.

R(9) = R(8) + R(3) + R(7) = 53.

R(10) = R(9) + R(8) = 84.

R(11) = R(10) = 84.

R(12) = R(11) + R(10) = 168.

R(13) = R(12) = 168.

R(14) = R(13) + R(12) = 336.

R(15) = R(14) + R(13) = 504.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 504.

 
Ответ: 504.

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

 

1. прибавь 2

2. прибавь 3.

 

Первая из них увеличивает число на экране на 2, вторая – на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

Решение.

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения.

 

Каждой программе соответствует одно число, поэтому посчитав количество программ (с точностью до перестановки), найдём количество различных чисел.

 

Если в программе n команд 1, тогда в ней будет 10-n команд 2. n изменяется от 0 до 10. Всего 11 программ, следовательно, 11 чисел.

 

Ответ: 11.

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

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

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

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

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

Решение.

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

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

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

R(0) = 0

R(1) = 0

R(2) = 1

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

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

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

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

R(7) = R(6) + R(4) + R(4) = 7 + 2 + 2 = 11

R(8) = R(7) + R(5) = 11 + 5 = 16

R(9) = R(8) + R(6) + R(5) = 16 + 7 + 5 = 28

R(10) = R(9) + R(7) = 28 + 11 = 39

36. Исполнитель Вычислитель преобразует число на экране.

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

1. Прибавить на 1.

2. Умножить на 2.

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для Вычислителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10 и не содержит числа 16?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 1 число 10, на количество программ, получающих из числа 10 число 15 и на количество программ, получающих из числа 17 число 21, поскольку траектория вычислений не должна содержать числа 16.

Пусть R(n) — количество программ, которые число 1 преобразуют в число n, P(n) — количество программ, которые число 10 преобразуют в число n, а F(n) — количество программ, которые преобразуют число 17 в число n.

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

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

2. Пусть n делится на 2, тогда R(n) = R(n / 2) + R(n − 1). То же самое аналогично для P(n) и F(n).

 

Постепенно вычислим значения R(n):

 

R(1) = 1.

R(2) = 2.

R(3) = R(2) = 2.

R(4) = R(2) + R(3) = 4.

R(5) = R(4) = 4.

R(6) = R(3) + R(5) = 6.

R(7) = R(6) = 6.

R(8) = R(4) + R(7) = 10.

R(9) = R(8) = 10.

R(10) = R(5) + R(9) = 14.

 

Теперь вычислим значения P(n):

 

P(10) = P(11) = P(12) = P(13) = P(14) = P(15) = 1.

 

Далее вычислим значения F(n):

 

F(18) = F(19) = F(20) = F(21) = 1.

 

Следовательно, количество программ, удовлетворяющих условию задачи, равно 14 · 1 · 1 = 14.

 
Ответ: 14.

37. Исполнитель А17 преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая – умножает его на 2, третья – умножает на 3.

Программа для исполнителя А17 – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 28 и при этом траектория вычислений содержит число 14?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

Используем динамическое программирование. Заведем массив dp, где dp[i] — количество способов получить число i.

База динамики dp[2] = 1.

Переходы:

dp[i] = dp[i-1] + dp[i/2](если i — четно) + dp[i/3] (если i — кратно 3).

При этом, если i > 14, а i-1 или i/2 или i/3 меньше 14, то этими значениями пренебрегаем, т.к. тогда не будет выполнено условие траектории. Далее будут показаны значения массива dp от 2 до 28:

1 1 2 2 4 4 6 7 9 9 15 15 19 19 19 19 19 19 19 19 19 19 19 19 19 19 38.

 
Ответ:38.

38. Исполнитель Плюс преобразует число на экране.

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

1. Прибавить 2

2. Прибавить 5

Первая команда увеличивает число на экране на 2, вторая увеличивает это число на 5. Программа для исполнителя Плюс — это последовательность команд.

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

Решение.

Используем метод динамического программирования. Возьмем массив dp, где dp[i] — кол-во способов получить число i из единицы с помощью данных команд.

База динамики:

dp[1]=1;

Переход:

dp[i]=dp[i-2]+dp[i-5].

Тогда значения в нашем массиве будут следующие(от 1 до 20): 1 0 1 0 1 1 1 2 1 3 2 4 4 5 7 7 11 11 16 18.

 
Ответ: 18.

39. Исполнитель ТР4 преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя ТР4 — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 37 и при этом траектория вычислений содержит число 16 и не содержит числа 33?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 16, на количество программ, получающих из числа 16 число 37, траектория вычислений не должна содержать числа 33.

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

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

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

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

Если n > 5, то R(n) = R(n / 2) + R(n — 1).

Если n = 3, 4, 5 то R(n) = 1 (два способа: прибавление единицы и удвоение).

 

R(3) = 1.

R(4) = R(3) = 1.

R(5) = R(4) = 1.

R(6) = R(3) + R(5) = 2.

R(7) = R(6) = 2.

R(8) = R(4) + R(7) =3.

R(9) = R(8) = 3.

R(10) = R(5) + R(9) = 4.

R(11) = R(10) = 4.

R(12) = R(6) + R(11) = 6.

R(13) = R(12) = 6.

R(14) = R(7) + R(13) = 8.

R(15) = R(14) = 8.

R(16) = R(8) + R(15) = 11.

 

Программ для получения числа 37 из числа 16 всего 2, можно их перечислить: 12111 и 1121.

 

Таким образом, количество программ, удовлетворяющих условию задачи, равно 11 · 2 = 22.

 
Ответ: 22.

40. Исполнитель Тренер преобразует число на экране.

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

 
1. Прибавить 1
2. Умножить на 2
 

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Тренер —  это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 40 и при этом траектория вычислений содержит числа 12 и 25?

Траектория должна содержать оба указанных числа. Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.

Решение.

Нужно найти количество программ, которые из 1 получают 12, количество программ, которые из 12 получают 25, количество программ, которые из 25 получают 40 и перемножить найденные значения. Сначала найдём количество программ, получающих 12 из 1.

 

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

 

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

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

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

Если n > 1, то R(n) = R(n / 2) + R(n — 1).

Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).

 

Теперь можно постепенно вычислить все значения:

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

R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(9) = 4 + 10 = 14 = R(11)

R(12) = R(6) + R(11) = 6 + 14 = 20

 

Программ, получающих из числа 12 число 25 достаточно мало, можно их просто перечислить: 21, 1111111111111.

А программ, получающих из числа 25 число 40, всего один способ: добавление единиц.

 

Тем самым, находим ответ: 

Ответ: 40.

Задание №22 ЕГЭ информатика. Перебор вариантов, построение дерева.