Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2024 по информатике

Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2024 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 10 минут. Уровень сложности: высокий.
Средний процент выполнения: 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.

Ответ: 0

Задача 2

У исполнителя Считатель-1 две команды, которым присвоены номера:

1. Прибавь 2

2. Умножь на 3

Первая из них увеличивает число на экране на 2, вторая — в 3 раза. Программа для исполнителя Считатель-1 — это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 58?

Решение

Из числа 1 с помощью команд «Прибавь 2» и «Умножь на 3» невозможно получить чётное число, т.к. нечётное +2 = нечётное и нечётное *3 = нечётное. Следовательно, число 58 получить невозможно.

Ответ: 0.

Ответ: 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.

Ответ: 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.

Ответ: 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.

Ответ: 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.

Ответ: 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.

Ответ: 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.

Ответ: 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

Ответ: 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.

Ответ: 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.

Ответ: 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.

Ответ: 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                  
Ответ: 7

Задача 14

У исполнителя X157 три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 5

3. Умножь на 7

Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 20?

Решение
Ответ: 129

Задача 15

У исполнителя X13 две команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 3

Первая из них увеличивает число на экране на 1, вторая — в 3 раза. Программа для исполнителя X13 — это последовательность команд.

Сколько существует программ, которые число 3 преобразуют в число 35, причём траектория вычислений содержит число 13?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3; 9; 10; 11.

Решение
Ответ: 3

Задача 16

У исполнителя X157 три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 5

3. Умножь на 7

Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 20?

Решение
Ответ: 129

Задача 17

У исполнителя X135 три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 3

3. Умножь на 5

Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 5 раз. Программа для исполнителя X135 — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 14?

Решение
Ответ: 110

Задача 18

У исполнителя Увеличитель две команды, которым присвоены номера:

1. Прибавь 2

2. Умножь на 3

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза. Программа для исполнителя Увеличитель—это последовательность команд.

Определите количество программ, которые число 1 преобразуют в число 37.

Решение
Ответ: 16

Задача 19

У исполнителя X17 две команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 7

Первая из них увеличивает число на экране на 1, вторая — на 7. Программа для исполнителя X17—это последовательность команд.

Сколько существует программ, которые число 5 преобразуют в число 26, и при этом траектория вычислений содержит число 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 3 траектория будет состоять из чисел 4, 11, 18, 19.

Решение
Ответ: 20

Задача 20

У исполнителя X125 три команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 2

3. Умножь на 5

Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 5 раз. Программа для исполнителя X125 — это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 38, и при этом траектория вычислений содержит числа 10 и 20? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2231 при исходном числе 5 траектория будет состоять из чисел 10, 20, 100, 101.

Решение
Ответ: 36