Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2026 по информатике
Средний процент выполнения: 52%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 23:
- Прочитай алгоритм и зафиксируй начальные значения переменных.
- Определи порядок выполнения команд.
- Выполняй алгоритм пошагово, фиксируя изменения после каждой команды.
- Если есть условия или циклы, проверяй их выполнение на каждом шаге.
- Веди таблицу трассировки для контроля значений переменных.
- Доведи выполнение до конца алгоритма.
- Сформулируй ответ по полученному результату.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 20?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 | 20 | 26 | 26 | 36 | 36 | 46 | 46 | 60 |
Ответ:60.
Задача 2
У исполнителя A2M5 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 5
Первая из них увеличивает данное число на 2, вторая - увеличивает его в 5 раз. Программа для исполнителя A2M5 - это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 35.
Решение
Заметим, что все числа, получаемые с помощью заданных команд из числа 1, нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 35 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 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 | ||||||||||
| 5 | 5 | 5 | 7 |
Ответ: 7.
Решение на С++
int main(){
const int n0 = 1, nk = 35;
int arr[nk + 1];
for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
arr[n0] = 1;
for (int n = n0 + 1; n <= nk; ++n) {
if (n - 2 >= n0)
arr[n] += arr[n - 2]; // Kn-2
if (n % 5 == 0 && n / 5 >= n0)
arr[n] += arr[n / 5]; // Kn/2
}
cout << arr[nk];
return 0;
}
Решение на Python
def f(n, r):
if n == r:
return 1
if n > r:
return 0
if n < r:
return f(n + 2, r) + f(n * 5, r)
print(f(1, 35))
Задача 3
У исполнителя X13 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 3 раза. Программа для исполнителя X13 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 34, причём траектория вычислений содержит число 11?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3; 9; 10; 11.
Решение
Количество программ, которые число 1 преобразуют в число 34 и при этом траектория вычислений содержит число 11 равно произведению числа программ, которые преобразуют число 1 в число 11 на число программ, преобразующих число 11 в число 34.
Сначала определим количество программ, преобразующих число 1 в 11. Будем решать поставленную задачу последовательно для чисел 1, 2, 3, . . . , 11 (то есть для каждого из этих чисел определим, сколько программ исполнителя существует для его получения).
Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 3, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i - 1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 и умножь на 3, тогда R(i) = R(i - 1) + R(i/3). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 5 | 5 | 5 |
Следовательно, количество программ, преобразующих число 1 в 11, равно 5.
Теперь определим количество программ, преобразующих число 11 в 34.
Будем считать, что R(11) = 1. Для каждого следующего числа 12, 13, . . . , 34 рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 3, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i - 1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 и умножь на 3, тогда R(i) = R(i - 1) + R(i/3). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
Следовательно, количество программ, преобразующих число 11 в 34, равно 2.
Количество программ, которые число 1 преобразуют в число 34 и при этом траектория вычислений содержит число 11, равно 5 · 2 = 10.
Ответ: 10.
Задача 4
У исполнителя Р134 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Прибавь 4
Первая из них увеличивает число на экране на 1, вторая на 3, а третьяна 4. Программа для исполнителя A134 это последовательность команд.
Сколько существует программ, которые число 8 преобразуют в число 22, причём траектория вычислений содержит число 17?
Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 231 при исходном числе 5 траектория будет состоять из чисел 8; 12; 13.
Решение
Количество программ, которые число 8 преобразуют в число 22, и при этом траектория вычислений содержит число 17, равно произведению числа программ, которые преобразуют число 8 в число 17, и числа программ, преобразующих число 17 в число 22.
Сначала определим количество программ, преобразующих число 8 в 17. Будем решать поставленную задачу последовательно для чисел 8, 9, 10, . . . , 17 (то есть для каждого из этих чисел определим, сколько программ исполнителя существует для его получения).
Количество программ, которые преобразуют число k в число n, будем обозначать через R(n). Будем считать, что R(k) = 1. Для чисел k + 1, k + 2 R(i) = R(i - 1). Для числа k + 3 количество программ, с помощью которых может быть получено это число из числа k, можно посчитать по формуле R(i) = R(i - 1) + R(i - 3). Количество программ, с помощью которых может быть получено каждое следующее число из числа k, можно посчитать по формуле R(i) = R(i - 1) + R(i - 3) + R(i - 4).
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 1 | 1 | 1 | 2 | 4 | 6 | 9 | 15 | 25 | 40 |
Следовательно, количество программ, преобразующих число 8 в 17, равно 40.
Теперь определим количество программ, преобразующих число 17 в 22.
Будем считать, что R(17) = 1. Для каждого следующего числа 18, 19, . . . , 22 рассмотрим, из какого числа оно может быть получено за одну команду исполнителя.
Заполним соответствующую таблицу по приведённым формулам слева направо:
| 17 | 18 | 19 | 20 | 21 | 22 |
| 1 | 1 | 1 | 2 | 4 | 6 |
Следовательно, количество программ, преобразующих число 17 в 22, равно 6.
Количество программ, которые число 8 преобразуют в число 22 и при этом траектория вычислений содержит число 17, равно 40 · 6 = 240.
Поиск ответа при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 8, nk = 22;
int arr[nk + 1];
for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
arr[n0] = 1;
for (int n = n0 + 1; n <= nk; ++n) {
if (n - 1 >= n0) arr[n] += arr[n - 1]; // Kn-1
if (n - 3 >= n0) arr[n] += arr[n - 3]; // Kn-3
if (n - 4 >= n0) arr[n] += arr[n - 4]; // Kn-4
if (n == 17)
for (int i = n - 1; i >= 0; --i) arr[i] = 0;
}
cout << arr[nk];
return 0;
}
Ответ: 240.
Задача 5
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 60, у которых траектория вычислений проходит через число 21? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Из числа 2 с помощью команд "Прибавь 2", "Умножь на 2" и "Умножь на 3" невозможно получить нечётное число, т.к. чётное +2 = чётное и чётное *любое = чётное. Следовательно, число 21 получить невозможно, а значит и траектория не может пройти через это число
Ответ: 0.
Задача 6
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Умножь на 2
2. Умножь на 3
3. Умножь на 5
Первая из них увеличивает число на экране в 2 раза, вторая - в 3 раза, третья - в 5 раз. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 101?
Решение
Поскольку существуют только команды умножения, в процессе мы будем получать числа, кратные хотя бы одному из чисел: 2, 3 или 5. Поскольку число 101 не кратно ни двойке, ни тройке, ни пятёрке, получить его невозможно.
Проверка при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 1, nk = 101;
int arr[nk + 1];
for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
arr[n0] = 1;
for (int n = n0 + 1; n <= nk; ++n) {
if (n % 2 == 0 && n / 2 >= n0)
arr[n] += arr[n - 2]; // Kn-2
if (n % 3 == 0 && n / 3 >= n0)
arr[n] += arr[n / 3]; // Kn/3
if (n % 5 == 0 && n / 5 >= n0)
arr[n] += arr[n / 5]; // Kn/5
}
cout << arr[nk];
return 0;
}
Ответ: 0.
Задача 7
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 47, причём траектория вычислений проходит через число 14? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 14 получить невозможно. Тогда никакая траектория из числа 3 в число 47 не пройдёт через число 14.
Ответ: 0.
Задача 8
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 86?
Решение
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 86 получить невозможно.
Ответ: 0.
Задача 9
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь предыдущее
3. Прибавь следующее
Первая из них увеличивает число на экране на 1, вторая - прибавляет к текущему числу на единицу меньшее число, третья - прибавляет к текущему числу на единицу большее число. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 23?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Кол-во программ | 1 | 2 | 2 | 5 | 5 | 9 | 9 | 16 | 16 | 26 | 26 |
| Число | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| Кол-во программ | 40 | 40 | 58 | 58 | 83 | 83 | 115 | 115 | 157 | 157 | 209 |
Ответ: 209.
Задача 10
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Сделай чётное
3. Сделай нечётное
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 2 раза и прибавляет единицу. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 30?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| Кол-во программ | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Число | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| Кол-во программ | 11 | 13 | 15 | 18 | 21 | 25 | 29 | 34 | 39 | 45 | 51 | 58 |
Ответ: 58.
Задача 11
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Сделай чётное
3. Сделай нечётное
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 2 раза и прибавляет единицу. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 24?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Кол-во программ | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
| Число | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Кол-во программ | 11 | 14 | 17 | 21 | 25 | 30 | 35 | 41 | 47 | 54 | 61 | 70 |
Ответ: 70.
Задача 12
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Прибавь 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - на 2. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 19, у которых траектория вычислений проходит через число 9 и 13? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Кол-во программ | 1 | 1 | 3 | 4 | 8 | 12 | 23 | 35 |
После числа 9 нельзя пользоваться теми значениями, которые были до числа 9. Поэтому дальнейшая таблица имеет вид:
| Число | 10 | 11 | 12 | 13 |
| Кол-во программ | 35 | 70 | 105 | 175 |
После числа 13 нельзя пользоваться теми значениями, которые были до числа 13. Поэтому дальнейшая таблица имеет вид:
| Число | 14 | 15 | 16 | 17 | 18 | 19 |
| Кол-во программ | 175 | 350 | 525 | 875 | 1400 | 2275 |
Ответ: 2275
Задача 13
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 15, у которых траектория вычислений проходит через число 9 и 13? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Кол-во программ | 1 | 1 | 2 | 2 | 4 | 4 | 6 | 7 |
После числа 9 нельзя пользоваться теми значениями, которые были до числа 9. Поэтому дальнейшая таблица имеет вид:
| Число | 10 | 11 | 12 | 13 |
| Кол-во программ | 7 | 7 | 7 | 7 |
После числа 13 нельзя пользоваться теми значениями, которые были до числа 13. Поэтому дальнейшая таблица имеет вид:
| Число | 14 | 15 |
| Кол-во программ | 7 | 7 |
Ответ:7
Задача 14
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 27?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Кол-во программ | 1 | 1 | 2 | 2 | 4 | 4 | 6 | 7 | 9 | 9 | 15 | 15 | 19 |
| Число | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| Кол-во программ | 21 | 27 | 27 | 38 | 38 | 47 | 51 | 60 | 60 | 81 | 81 | 96 | 103 |
Ответ: 103.
Задача 15
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 26?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Кол-во программ | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 5 | 8 | 8 |
| Число | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| Кол-во программ | 10 | 11 | 14 | 14 | 20 | 20 | 25 | 27 | 32 | 32 | 43 | 43 | 51 |
Ответ: 51.
Задача 16
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 26. Траектория вычислений которых не проходит через число 15? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 | 20 | 26 | 0 | 10 | 10 | 20 | 20 | 34 | 34 | 48 | 48 | 68 | 68 | 88 |
Ответ: 88
Задача 17
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 26, у которых траектория вычислений проходит через число 10? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 |
После числа 10 нельзя пользоваться теми значениями, которые были до числа 10. Поэтому дальнейшая таблица имеет вид:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| Кол-во программ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 28 | 28 | 42 | 42 | 56 | 56 | 70 |
Ответ: 70.
Задача 18
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 26, у которых траектория вычислений проходит через число 12? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 |
После числа 12 нельзя пользоваться теми значениями, которые были до числа 12. Поэтому дальнейшая таблица имеет вид:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| Кол-во программ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 40 | 40 | 60 |
Ответ: 60.
Задача 19
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 20, у которых траектория вычислений проходит через число 12? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 |
После числа 12 нельзя пользоваться теми значениями, которые были до числа 12. Поэтому дальнейшая таблица имеет вид:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Кол-во программ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
Ответ:
Задача 20
У исполнителя Вычислитель три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - на 2, а третья - в 3 раза. Программа для исполнителя X123 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 9?
Решение
Будем решать поставленную задачу последовательно для чисел 1, 2, 3, . . . , 9 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Число 2 из числа 1 можно получить с помощью команды 1 (также будем считать, что R(1) = 1). Для каждого следующего числа i рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число i не делится на 3, то оно может быть получено либо из i - 1-го с помощью команды прибавь 1, либо из числа i - 2-го с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для i-1-го и i-2-го чисел:R(i) = R(i-1)+R(i-2). Если число на 3 делится, то вариантов последней команды три: прибавь 1, прибавь 2 и умножь на 3, следовательно, R(i) = R(i-1)+R(i-2)+R(i/3). Заполним соответствующую таблицу по приведенным формулам слева направо:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 3 | 4 | 7 | 12 | 19 | 31 | 53 |
Ответ: 53.
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
