Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2026 по информатике
Средний процент выполнения: 52%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 23:
- Прочитай алгоритм и зафиксируй начальные значения переменных.
- Определи порядок выполнения команд.
- Выполняй алгоритм пошагово, фиксируя изменения после каждой команды.
- Если есть условия или циклы, проверяй их выполнение на каждом шаге.
- Веди таблицу трассировки для контроля значений переменных.
- Доведи выполнение до конца алгоритма.
- Сформулируй ответ по полученному результату.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
3. Умножь на 4
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 4 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 48?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью 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 |
| Число | 26 | 28 | 30 | 32 | 34 | 36 | 38 | 40 | 42 | 44 | 46 | 48 |
| Кол-во программ | 28 | 35 | 35 | 54 | 54 | 68 | 68 | 92 | 92 | 111 | 111 | 146 |
Ответ: 146.
Задача 2
У исполнителя Считатель-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.
Задача 3
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 79?
Решение
Из числа 2 с помощью команд "Прибавь 2", "Умножь на 2" и "Умножь на 3" невозможно получить нечётное число, т.к. чётное +2 = чётное и чётное *любое = чётное. Следовательно, число 79 получить невозможно.
Ответ: 0.
Задача 4
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 86?
Решение
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 86 получить невозможно.
Ответ: 0.
Задача 5
У исполнителя Считатель-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.
Задача 6
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь предыдущее
3. Прибавь следующее
Первая из них увеличивает число на экране на 1, вторая - прибавляет к текущему числу на единицу меньшее натуральное число, третья - прибавляет к текущему числу на единицу большее натуральное число. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 33, причём траектория вычислений не проходит через число 7 и 14, но проходит через число 12? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Кол-во программ | 1 | 1 | 3 | 3 | 7 | 7 | 0 | 0 | 10 | 10 | 24 | 24 |
После числа 12 нельзя пользоваться теми значениями, которые были до числа 12. Поэтому дальнейшая таблица имеет вид:
| Число | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 |
| Кол-во программ | 24 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 24 | 24 | 72 | 72 | 96 | 96 | 96 | 96 | 96 | 96 | 96 |
Вычисление результата при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 1, nk = 33;
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) {
arr[n] = arr[n - 1]; // Kn-1
if (n % 2 != 0 && (n - 1) / 2 >= n0) //K(n - 1)/2
arr[n] += arr[(n - 1) / 2];
if (n % 2 != 0 && (n + 1) / 2 >= n0) //K(n + 1)/2
arr[n] += arr[(n + 1) / 2];
if (n == 7 || n == 14)
arr[n] = 0;
if (n == 12)
for (int i = n - 1; i >=0 ; --i)
arr[i] = 0;
}
cout << arr[nk];
return 0;
}
Ответ: 96.
Задача 7
У исполнителя Считатель-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.
Задача 8
У исполнителя Считатель-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.
Задача 9
У исполнителя Считатель-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.
Задача 10
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Сделай чётное
3. Сделай нечётное
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 2 раза и прибавляет единицу. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 34, траектория которых не проходит через число 13? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Кол-во программ | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Число | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |
| Кол-во программ | 8 | 10 | 13 | 16 | 20 | 24 | 24 | 24 | 25 | 26 | 28 | 30 | 33 | 36 | 40 |
Ответ: 40.
Задача 11
У исполнителя Считатель-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.
Задача 12
У исполнителя Считатель-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.
Задача 13
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Сделай чётное
3. Сделай нечётное
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 2 раза и прибавляет единицу. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 18?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| Кол-во программ | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 11 | 14 | 17 | 21 | 25 | 30 |
Ответ: 30.
Задача 14
У исполнителя Считатель-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
Задача 15
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 32, у которых траектория вычислений проходит через число 10? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Кол-во программ | 1 | 1 | 2 | 2 | 4 | 4 | 6 | 7 | 9 |
После числа 10 нельзя пользоваться теми значениями, которые были до числа 10. Поэтому дальнейшая таблица имеет вид:
| Число | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Кол-во программ | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 18 | 18 | 27 | 27 | 36 | 36 | 45 | 45 | 54 | 54 | 72 | 72 | 81 |
Ответ: 81
Задача 16
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 27, у которых траектория вычислений проходит через число 10? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Кол-во программ | 1 | 1 | 2 | 2 | 4 | 4 | 6 | 7 | 9 |
После числа 10 нельзя пользоваться теми значениями, которые были до числа 10. Поэтому дальнейшая таблица имеет вид:
| Число | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| Кол-во программ | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 18 | 18 | 27 | 27 | 36 | 36 | 45 | 45 |
Ответ: 45
Задача 17
У исполнителя Считатель-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.
Задача 18
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 34?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| Кол-во программ | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 6 | 6 |
| Число | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |
| Кол-во программ | 8 | 8 | 10 | 11 | 13 | 13 | 17 | 17 | 20 | 21 | 25 | 25 | 32 | 32 | 38 | 40 | 46 |
Ответ: 46.
Задача 19
У исполнителя Считатель-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.
Задача 20
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
3. Умножь на 4
Первая из них увеличивает число на экране на 2, вторая - в 2 раза, третья - в 4 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 18?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Заметим, что из числа 2 с помощью команд "Прибавь 2", "Умножь на 2" и "Умножь на 4" невозможно получить нечётное число, т.к. чётное +2 = чётное и чётное *любое = чётное. В таблице будем отображать только чётные числа.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 |
| Кол-во программ | 1 | 2 | 2 | 5 | 5 | 7 | 7 | 14 | 14 |
Решение при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 2, nk = 18;
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 % 2 == 0 && n / 2 >= n0)
arr[n] += arr[n / 2]; // Kn/2
if (n % 4 == 0 && n / 4 >= n0)
arr[n] += arr[n / 4];
}
cout << arr[nk];
return 0;
}
Ответ: 14.
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
