Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2026 по информатике
Средний процент выполнения: 52%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 23:
- Прочитай алгоритм и зафиксируй начальные значения переменных.
- Определи порядок выполнения команд.
- Выполняй алгоритм пошагово, фиксируя изменения после каждой команды.
- Если есть условия или циклы, проверяй их выполнение на каждом шаге.
- Веди таблицу трассировки для контроля значений переменных.
- Доведи выполнение до конца алгоритма.
- Сформулируй ответ по полученному результату.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Прибавить 5
C. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 27, и при этом траектория вычислений содержит число 11 и не содержит число 7?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 5 траектория состоит из чисел 10, 15, 17.
Решение
Решение.
Заметим, что из числа 3 командой C сразу получаем 6, а затем командой A — число 11 (обязательное). Все допустимые пути начинаются с команды C (3→6), затем A (6→11), так как это единственный способ попасть в 11, не проходя через 7.
После 11 нужно добраться до 27, используя команды A (+2), B (+5), C (×2), не заходя в 7 (что уже невозможно, так как все числа ≥ 11). Считаем количество путей из 11 в 27:
Из 11: можно пойти в 13 (A), 16 (B), 22 (C).
Из 13: в 15 (A), 18 (B), 26 (C, тупик — нет пути в 27).
Из 16: в 18 (A), 21 (B), 32 (C, тупик).
Из 22: в 24 (A, тупик), 27 (B) ✓, 44 (C, тупик).
Продолжая подсчёт по всем ветвям, получаем 12 путей из 11 в 27, что и является ответом (так как начало у всех одно: CA).
Все 12 программ:
CBAAAAAAAA, CBAAABB, CBAABAB, CBAABBA, CBABAAB, CBABABA, CBABBAA, CBBAAAB, CBBAABA, CBBABAA, CBBBAAA, CBCB.
программный способ.
def f(start, end):
if start > end or start == 7:
return 0
if start == end:
return 1
else:
return f(start + 2, end) + f(start + 5, end) + f(start * 2, end)
print(f(3, 11) * f(11, 27))
Функция f(start, end) подсчитывает количество программ, переводящих число start в число end командами A (+2), B (+5), C (×2), при условии что траектория не содержит числа 7. Число 11 обязательно должно присутствовать в траектории, поэтому общее количество программ равно произведению числа путей из 3 в 11 на число путей из 11 в 27.
Задача 2
У исполнителя Считатель-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
Задача 3
У исполнителя Считатель-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.
Задача 4
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
3. Умножь на 4
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 4 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 24?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Заметим, что из числа 2 с помощью команд "Прибавь 2", "Умножь на 2" и "Умножь на 4" невозможно получить нечётное число, т.к. чётное +2 = чётное и чётное *любое = чётное. В таблице будем отображать только чётные числа.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 |
| Кол-во программ | 1 | 2 | 2 | 5 | 5 | 7 | 7 | 14 | 14 | 19 | 19 | 28 |
Поиск ответа при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 2, nk = 24;
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-1
if (n / 2 >= n0 && n % 2 == 0)
arr[n] += arr[n / 2]; // Kn/2
if (n / 4 >= n0 && n % 4 == 0)
arr[n] += arr[n / 4]; // Kn/4
}
cout << arr[nk];
return 0;
}
Ответ: 28.
Задача 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. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 79?
Решение
Из числа 2 с помощью команд "Прибавь 2", "Умножь на 2" и "Умножь на 3" невозможно получить нечётное число, т.к. чётное +2 = чётное и чётное *любое = чётное. Следовательно, число 79 получить невозможно.
Ответ: 0.
Задача 7
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 58?
Решение
Из числа 1 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 58 получить невозможно.
Ответ: 0.
Задача 8
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 86?
Решение
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 86 получить невозможно.
Ответ: 0.
Задача 9
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 29?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число. Значит, чётные числа можно не писать.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 |
| Кол-во программ | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 6 | 6 |
Ответ: 6.
Задача 10
У исполнителя Считатель-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.
Задача 11
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь предыдущее
3. Прибавь следующее
Первая из них увеличивает число на экране на 1, вторая - прибавляет к текущему числу на единицу меньшее число, третья - прибавляет к текущему числу на единицу большее число. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 15?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Кол-во программ | 1 | 2 | 2 | 5 | 5 | 9 | 9 | 16 | 16 | 26 | 26 | 40 | 40 | 58 |
Ответ: 58.
Задача 12
У исполнителя Считатель-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.
Задача 13
У исполнителя Считатель-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.
Задача 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. Прибавь предыдущее
3. Прибавь следующее
Первая из них увеличивает число на экране на 1, вторая - прибавляет к текущему числу на единицу меньшее число, третья - прибавляет к текущему числу на единицу большее число. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 28, причём траектория вычислений не проходит через число 10? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если существует Х программ для получения числа А из начального значения и Y программ для числа B, а число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Кол-во программ | 1 | 1 | 2 | 2 | 4 | 4 | 7 | 0 | 4 | 4 | 10 | 10 | 18 |
| Число | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| Кол-во программ | 18 | 29 | 29 | 36 | 36 | 40 | 40 | 48 | 48 | 62 | 62 | 82 | 82 |
Например, рассмотри как было получено количество программ для числа 5:
1) можем ли мы получить 5, прибавив единицу? Да, из числа 4
2) можем ли мы получить 5, прибавив предыдущее? Да, начальное значение = 3, для него «предыдущим» считается 2. 3 + 2 = 5
3) можем ли мы получить 5, прибавив следующее? Нет, поскольку начальное значение = 3, а для него «следующее» это 4 и их сумма = 7
Ответ: 82.
Задача 16
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 18?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью 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 | 2 | 3 | 3 | 4 | 5 | 6 | 6 | 8 |
Ответ: 8.
Задача 17
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 34, траектория вычислений которых не проходит через число 6 и 12? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью 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 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 0 | 0 | 4 | 4 | 8 | 8 | 0 | 0 | 0 | 0 | 4 | 4 |
| Число | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |
| Кол-во программ | 8 | 8 | 16 | 16 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 24 | 28 | 28 | 32 |
Ответ: 32
Задача 18
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 25, траектория вычислений которых не проходит через число 9? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью 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 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 0 | 4 | 4 | 10 | 10 | 16 | 16 | 26 | 26 | 26 | 26 | 30 | 30 | 34 | 34 | 44 | 44 |
Поиск ответа при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 1, nk = 25;
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 % 2 == 0 && (n / 2) >= n0) //K(n / 2)
arr[n] += arr[n / 2];
if (n == 9)
arr[n] = 0;
}
cout << arr[nk];
return 0;
}
Ответ: 44
Задача 19
У исполнителя Считатель-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.
Задача 20
У исполнителя X132 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - на 3, а третья - в 2 раза. Программа для исполнителя X132 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 14, причём траектория вычислений содержит числа 6 и 10?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 1323 при исходном числе 4 траектория будет состоять из чисел 5; 10; 13; 26.
Решение
Количество программ, которые число 1 преобразуют в число 14, причём траектория вычислений содержит числа 6 и 10, равно произведению числа программ, преобразующих число 1 в число 6, число 6 в число 10 и число 10 в число 14.
Сначала определим количество программ, преобразующих число 1 в 6. Будем решать поставленную задачу последовательно для чисел 1, 2, 3, 4, 5, 6 (то есть для каждого из этих чисел определим, сколько программ исполнителя существует для его получения).
Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа i рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число i нечётно, то оно может быть получено либо из i - 1-го с помощью команды прибавь 1, либо из числа i-3-го с помощью команды прибавь 3. Значит, количество искомых программ для такого числа равно количеству программ для i-1-го и i-3-го чисел: R(i) = R(i-1)+R(i-3). Если число чётно, то вариантов последней команды три: прибавь 1, прибавь 3 и умножь на 2, следовательно, R(i) = R(i-1)+R(i-3)+R(i=2). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 2 | 5 | 7 | 11 |
Следовательно, количество программ, преобразующих число 1 в 6, равно 11.
Теперь определим количество программ, преобразующих число 6 в 10.
Будем считать, что R(10) = 1. Для каждого следующего числа 11, 12, . . . , 14 рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число нечётно, то оно может быть получено либо из i - 1-го с помощью команды прибавь 1, либо из числа i - 3-го с помощью команды прибавь 3. Значит, количество искомых программ для такого числа равно количеству программ для i - 1-го и i - 3-го чисел: R(i) = R(i - 1) + R(i - 3). Если число чётно, то вариантов последней команды три: прибавь 1, прибавь 3 и умножь на 2, следовательно, R(i) = R(i-1)+R(i-3)+R(i=2). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 1 | 2 | 3 |
Следовательно, количество программ, преобразующих число 6 в 10, равно 3.
Рассуждая аналогично предыдущим случаям, определим количество программ, преобразующих число 10 в 14.
| 10 | 11 | 12 | 13 | 14 |
| 1 | 1 | 1 | 2 | 3 |
Следовательно, количество программ, преобразующих число 10 в 15, равно 4.
Количество программ, которые число 1 преобразуют в число 15, причём траектория вычислений содержит числа 6 и 10, равно 11 · 3 · 3 = 99.
Ответ: 99.
Рекомендуемые курсы подготовки
- 🔥 Изучишь одни из самых фундаментальных тем информатики
- 🔥 Научишься решать 6 задач формата ЕГЭ руками
- 🔥 Начнёшь свой путь в проге
- 🔥 Учёба на Турбо: познакомишься с преподавателями и личным кабинетом
Что тебя ждет?
- 8 вебинаров (1 веб в неделю по 1 часу)
- Тестовые Д/З после каждого занятия
- Конспекты и скрипты к урокам
- Доступ к личному кабинету
- Возможность отрабатывать задания ЕГЭ в любое время
- Чат с единомышленниками
- Поддержка препа 24/7
на бесплатном курсе Турбо ЕГЭ
