Бесплатный интенсив по информатике

3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и многое другое.

Подробнее об интенсиве

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

За это задание ты можешь получить 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
Показать решение
Бесплатный интенсив
Показать еще

Рекомендуемые курсы подготовки

егэ по информатике информатика 10 класс информатика 11 класс информатика с нуля
Популярные материалы

Бесплатный интенсив по информатике

3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и многое другое.

Бесплатный интенсив