Задание 22. Графы. Подсчёт количества программ. ЕГЭ 2020 по информатике
Средний процент выполнения: 51.9%
Ответом к заданию 22 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
У исполнителя Увеличитель две команды, которым присвоены номера:
1. Прибавь 2,
2. Увеличь цифру в старшем разряде числа на 1.
Первая из них увеличивает данное число на 2, вторая — увеличивает цифру в старшем разряде числа на 1, например, число 34 с помощью этой команды превратится в число 44. Программа для исполнителя Увеличитель — это последовательность команд.
Определите количество программ, которые число 20 преобразуют в число 44.
Решение
Будем решать поставленную задачу последовательно для чисел 20, 21, 22, . . . , 44 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 20 в число n, будем обозначать через R(n). Будем считать, что R(20) = 1. Заметим, что команда 2 для чисел, меньших 90, соответствует условию «прибавь 10». С помощью каждой из команд 1 и 2, применяя их последовательно к числам, получаемым из числа 29, можно получить только чётные числа. Числа 20, 22, . . . , 28 можно получить из предыдущего числа только с помощью команды 1. Значит, количество искомых программ для каждого из таких чисел равно количеству программ для предыдущего числа: R(i) = R(i − 2), i—чётное, 22 ≤ i ≤ 28.
Получаем R(20) = R(22) = · · · = R(28) = 1. Для чисел, больших 28 и не превосходящих 44, вариантов последней команды два: прибавь 2 и прибавь 10, то есть R(i) = R(i − 2) + R(i − 10), i — чётное, 30 ≤ i ≤ 44. Заполним соответствующую таблицу по приведённым формулам слева направо:
| 20 | 22 | 24 | 26 | 28 | 30 | 32 | 34 | 36 | 38 | 40 | 42 | 44 |
| 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 11 | 15 |
Задача 2
У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Первая из них увеличивает данное число на 2, вторая — увеличивает его в 5 раз. Программа для исполнителя Удвоитель — это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 37.
Решение
Заметим, что все числа, получаемые с помощью заданных команд из числа 1, — нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 37 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 5, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i − 2), i — нечётное. Если число на 5 делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда R(i) = R(i−2)+R(i/5), i — нечётное. Заполним соответствующую таблицу по приведенным формулам слева направо:
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 |
| 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 5 | 5 |
| 29 | 31 | 33 | 35 | 37 | |||||||||
| 5 | 5 | 5 | 7 | 7 |
Задача 3
У исполнителя X157 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 5
3. Умножь на 7
Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 20?
Решение
Задача 4
У исполнителя X135 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 5
Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 5 раз. Программа для исполнителя X135 — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 14?
Решение
Задача 5
У исполнителя X123 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая — на 2, а третья — в 3 раза. Программа для исполнителя X123— это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 10?
Решение
Задача 6
У исполнителя Уменьшитель две команды, которым присвоены номера:
1. Разделить на 2
2. Вычесть 1
Первая из них уменьшает число на экране в 2 раза, вторая — уменьшает его на 1. Программа для исполнителя Уменьшитель—это последовательность команд.
Определите количество программ, которые число 64 преобразуют в число 14.
Решение
Задача 7
У исполнителя Увеличитель две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза. Программа для исполнителя Увеличитель—это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 37.
Решение
Задача 8
У исполнителя X17 две команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 7
Первая из них увеличивает число на экране на 1, вторая — на 7. Программа для исполнителя X17—это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 26, и при этом траектория вычислений содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 3 траектория будет состоять из чисел 4, 11, 18, 19.
Решение
Задача 9
У исполнителя X12 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая—в 2 раза. Программа для исполнителя X12—это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 32, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 5 траектория будет состоять из чисел 6, 12, 24, 25.
Решение
Задача 10
У исполнителя X13 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая — в 3 раза. Программа для исполнителя X13—это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 35, и при этом траектория вычислений содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 9, 10, 11.
Решение
Задача 11
У исполнителя X13 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая—в 3 раза. Программа для исполнителя X13—это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 34, и при этом траектория вычислений содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 9, 10, 11.
Решение
Задача 12
У исполнителя X123 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 3 раза. Программа для исполнителя X123 — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 30, и при этом траектория вычислений содержит числа 7 и 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2213 при исходном числе 5 траектория будет состоять из чисел 10, 20, 21, 63.
Решение
Задача 13
У исполнителя X125 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 5
Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 5 раз. Программа для исполнителя X125 — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 38, и при этом траектория вычислений содержит числа 10 и 20? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2231 при исходном числе 5 траектория будет состоять из чисел 10, 20, 100, 101.
Решение
Задача 14
У исполнителя A12M2 две команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Умножь на 2
Программа для исполнителя A12M2 — это последовательность команд.
Сколько существует программ, которые число 4 преобразуют в число 16, и при этом траектория вычислений содержит числа 10 и 14?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 5, 6, 7.
Решение
Задача 15
У исполнителя X132 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 2 раза. Программа для исполнителя X132— это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 15, и при этом траектория вычислений содержит числа 6 и 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1323 при исходном числе 4 траектория будет состоять из чисел 5, 10, 13, 26.
Решение
Задача 16
У исполнителя A15M3 две команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 5
3. Умножь на 3
Программа для исполнителя A15M3 — это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 24, и при этом траектория вычислений содержит число 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 8, 9, 10.
Решение
Задача 17
У исполнителя A12M2 две команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Умножь на 2
Программа для исполнителя A12M2 — это последовательность команд. Сколько существует программ, которые число 4 преобразуют в число 14, и при этом траектория вычислений содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 5, 6, 7.
Решение
Задача 18
У исполнителя А128 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Прибавь 5
Первая из них увеличивает число на экране на 1, вторая — на 2, а третья — на 5. Программа для исполнителя A125 — это последовательность команд.
Сколько существует программ, которые число 10 преобразуют в число 19, и при этом траектория вычислений содержит число 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 231 при исходном числе 5 траектория будет состоять из чисел 7, 12, 13.
Решение
Задача 19
У исполнителя А134 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Прибавь 4
Первая из них увеличивает число на экране на 1, вторая — на 3, а третья—на 4. Программа для исполнителя A134 — это последовательность команд.
Сколько существует программ, которые число 8 преобразуют в число 22, и при этом траектория вычислений содержит число 17?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 231 при исходном числе 5 траектория будет состоять из чисел 8, 12, 13.
Решение
Задача 20
У исполнителя X164 три команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 6,
3. умножь на 4.
Первая из них увеличивает число на экране на 1, вторая — на 6, а третья — в 4 раза. Программа для исполнителя X164— это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 20?