Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2024 по информатике
Средний процент выполнения: 25.4%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая — в 3 раза. Программа для исполнителя Считатель-1 — это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 47, причём траектория вычислений проходит через число 14? Траектория вычислений — множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Из числа 3 с помощью команд «Прибавь 2» и «Умножь на 3» невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 14 получить невозможно. Тогда никакая траектория из числа 3 в число 47 не пройдёт через число 14.
Ответ: 0.
Задача 2
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая — в 3 раза. Программа для исполнителя Считатель-1 — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 58?
Решение
Из числа 1 с помощью команд «Прибавь 2» и «Умножь на 3» невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 58 получить невозможно.
Ответ: 0.
Задача 3
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая — в 3 раза. Программа для исполнителя Считатель-1 — это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 49?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Из числа 3 с помощью команд «Прибавь 2» и «Умножь на 3» невозможно получить чётное число. Значит, чётные числа можно не писать.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 |
| Кол-во программ | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 |
| Число | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 |
| Кол-во программ | 6 | 6 | 6 | 8 | 8 | 8 | 10 | 10 | 10 | 13 | 13 | 13 |
Ответ: 13.
Задача 4
У исполнителя Считатель-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.
Задача 5
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Сделай чётное
3. Сделай нечётное
Первая из них увеличивает число на экране на 1, вторая — в 2 раза, третья — в 2 раза и прибавляет единицу. Программа для исполнителя Считатель-1 — это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 30, траектория которых проходит через число 9 и не проходит через число 16? Траектория вычислений — множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Кол-во программ | 1 | 1 | 2 | 3 | 4 | 5 | 7 | 9 |
После числа 9 нельзя пользоваться теми значениями, которые были до числа 9. Поэтому дальнейшая таблица имеет вид:
| Число | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| Кол-во программ | 9 | 9 | 9 | 9 | 9 | 9 | 0 | 0 | 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 | 90 | 99 | 108 | 117 |
Поиск ответа при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 2, nk = 30;
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 / 2 >= n0) //Kn/2 - сделай чётное
arr[n] += arr[n / 2];
if (n == 16)
arr[n] = 0;
if (n == 9)
for (int i = n - 1; i >=0 ; --i)
arr[i] = 0;
}
cout << arr[nk];
return 0;
}
Ответ: 117.
Задача 6
У исполнителя Считатель-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.
Задача 7
У исполнителя Считатель-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.
Задача 8
У исполнителя Считатель-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.
Задача 9
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая — в 2 раза. Программа для исполнителя Считатель-1 — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 20, траектория вычислений которых не проходит через число 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 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 0 | 4 | 4 | 10 | 10 | 16 | 16 | 26 | 26 | 26 | 26 | 30 |
Ответ: 30
Задача 10
У исполнителя Считатель-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.
Задача 11
У исполнителя A2M5 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 5
Первая из них увеличивает данное число на 2, вторая — увеличивает его в 5 раз. Программа для исполнителя A2M5 — это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 31.
Решение
Заметим, что все числа, получаемые с помощью заданных команд из числа 1, нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 31 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 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 | ||||||||||||
| 5 | 5 |
Ответ: 5.
Задача 12
У исполнителя X123 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая — на 2, а третья — в 3 раза. Программа для исполнителя X123 — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 10?
Решение
Будем решать поставленную задачу последовательно для чисел 1, 2, 3, . . . , 10 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 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 | 10 |
| 1 | 1 | 3 | 4 | 7 | 12 | 19 | 31 | 53 | 84 |
Ответ: 84.
Задача 13
У исполнителя Удвоитель две команды, которым присвоены номера:
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 |
Задача 14
У исполнителя X157 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 5
3. Умножь на 7
Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 20?
Решение
Задача 15
У исполнителя X13 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая — в 3 раза. Программа для исполнителя X13 — это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 35, причём траектория вычислений содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3; 9; 10; 11.
Решение
Задача 16
У исполнителя X157 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 5
3. Умножь на 7
Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 20?
Решение
Задача 17
У исполнителя X135 три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 5
Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 5 раз. Программа для исполнителя X135 — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 14?
Решение
Задача 18
У исполнителя Увеличитель две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза. Программа для исполнителя Увеличитель—это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 37.
Решение
Задача 19
У исполнителя X17 две команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 7
Первая из них увеличивает число на экране на 1, вторая — на 7. Программа для исполнителя X17—это последовательность команд.
Сколько существует программ, которые число 5 преобразуют в число 26, и при этом траектория вычислений содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 3 траектория будет состоять из чисел 4, 11, 18, 19.
Решение
Задача 20
У исполнителя X125 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 5
Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 5 раз. Программа для исполнителя X125 — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 38, и при этом траектория вычислений содержит числа 10 и 20? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2231 при исходном числе 5 траектория будет состоять из чисел 10, 20, 100, 101.