Задание 23. Графы. Подсчёт количества программ. ЕГЭ 2027 по информатике
Средний процент выполнения: 52%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 23:
- Прочитай алгоритм и зафиксируй начальные значения переменных.
- Определи порядок выполнения команд.
- Выполняй алгоритм пошагово, фиксируя изменения после каждой команды.
- Если есть условия или циклы, проверяй их выполнение на каждом шаге.
- Веди таблицу трассировки для контроля значений переменных.
- Доведи выполнение до конца алгоритма.
- Сформулируй ответ по полученному результату.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавь 10
B. Сделай чёт
C. Сделай нечёт
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 189, и при этом траектория вычислений содержит число 11 и не содержит число 19?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 5 траектория состоит из чисел 11, 22, 32.
Решение
def f(a, b):
if a == b:
return True
if a > b or a == 19:
return False
return f(a + 10, b) + f(a * 2, b) + f(a * 2 + 1, b)
print(f(1, 11) * f(11, 189))
Функция f(a, b) подсчитывает количество программ, переводящих число a в число b командами A (+10), B (a * 2)), C (a * 2 + 1), при условии что траектория не содержит число 19. Число 11 обязательно должно присутствовать в траектории, поэтому общее количество программ равно произведению числа путей из 1 в 11 на число путей из 11 в 189.
Задача 2
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Прибавь предыдущее
C. Прибавь следующее
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 157, и при этом траектория вычислений содержит число 11 и не содержит числа 7, 23 и 150?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 5 траектория состоит из чисел 11, 21, 23.
Решение
def f(a, b):
if a == b:
return True
if a > b or a == 7 or a == 23 or a == 150:
return False
return f(a + 2, b) + f(a + (a - 1), b) + f(a + (a + 1), b)
print(f(2, 11) * f(11, 157))
Функция f(a, b) подсчитывает количество программ, переводящих число a в число b командами A (+2), B (+ (a - 1)), C (+ (a + 1)), при условии что траектория не содержит чисел 7, 23 и 150. Число 11 обязательно должно присутствовать в траектории, поэтому общее количество программ равно произведению числа путей из 2 в 11 на число путей из 11 в 157.
Задача 3
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 3
B. Вычесть 8
D. Поменять местами цифры разрядов десятков и единиц
Команда D может применяться только к числу, у которого цифра разряда десятков по значению строго больше цифры разряда единиц, и заменяет число на экране числом, в котором эти две цифры поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 53 результатом является число 5, и при этом траектория вычислений содержит ровно одно из чисел 41 или 32 (но не оба одновременно)?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы BAD при исходном числе 74 траектория состоит из чисел 66, 63, 36.
Решение
Решение.
Функция g(start, end, forbidden) считает количество программ, переводящих start в end, не проходя через forbidden.
def swap(n):
t, u = (n // 10) % 10, n % 10
return (n // 100) * 100 + u * 10 + t if t > u else None
def g(start, end, forbidden):
if start < 0 or start > 200:
return 0
if start == forbidden:
return 0
if start == end:
return 1
total = g(start - 3, end, forbidden) + g(start - 8, end, forbidden)
sw = swap(start)
if sw is not None:
total += g(sw, end, forbidden)
return total
# через 41, но не через 32:
through_41 = g(53, 41, 32) * g(41, 5, 32)
# через 32, но не через 41:
through_32 = g(53, 32, 41) * g(32, 5, 41)
print(through_41 + through_32)
g(53, 41, 32) = 1 (единственный путь 53→41 без 32: 53→50→47→41 невозможен... путь 53→D=35→32 запрещён, значит 53→A=50→A=47→A=44→A=41).
g(41, 5, 32) = 32 — пути из 41 в 5, не проходящие через 32.
g(53, 32, 41) = 1 (путь 53→D=35→B=27→... нет; 53→A=50→B=42→D=24→... нет; 53→A=50→A=47→A=44→B=36→A=33→A=32... нет; единственный 53→D=35→A=32).
g(32, 5, 41) = 6 — пути из 32 в 5, не проходящие через 41.
Итог: 1 × 32 + 1 × 6 = 38
Задача 4
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычти 10
B. Вычти 30
C. Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 389 результатом является число 101, и при этом траектория вычислений содержит число 300 и не содержит число 200?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 100 траектория состоит из чисел 50, 20, 10.
Решение
def f(a, b):
if a == b:
return True
if a < b or a == 200:
return False
return f(a - 10, b) + f(a - 30, b) + f(a // 2, b)
print(f(389, 300) * f(300, 101))
Функция f(a, b) подсчитывает количество программ, переводящих число a в число b командами A (-10), B (-30)), C (a // 2), при условии что траектория не содержит число 200. Число 300 обязательно должно присутствовать в траектории, поэтому общее количество программ равно произведению числа путей из 389 в 300 на число путей из 300 в 101.
Задача 5
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
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.
Задача 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. Прибавь предыдущее
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.
Задача 8
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 3
Первая из них увеличивает число на экране на 2, вторая - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 23?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Из числа 3 с помощью команд "Прибавь 2" и "Умножь на 3" невозможно получить чётное число. Значит, чётные числа можно не писать.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 |
| Кол-во программ | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 |
Поиск ответа при помощи программы на С++:
#include <iostream>
using namespace std;
int main(){
const int n0 = 3, nk = 23;
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 % 3 == 0 && (n / 3) >= n0) //K(n / 3) - умножь на 3
arr[n] += arr[n / 3];
}
cout << arr[nk];
return 0;
}
Ответ: 4.
Задача 9
У исполнителя Считатель-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.
Задача 10
У исполнителя Считатель-1 три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 2 раза, третья - в 3 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 17?
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью X программ из начального значения, число B можно получить с помощью Y программ из начального значения, а с помощью одной любой команды из условия число C можно получить только из чисел A и B, то количество программ, с помощью которых можно получить число C из начального значения, равно X + Y.
Таблица, отображающая количество программ для каждого отдельного числа, вычисленная по данному правилу:
| Число | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| Кол-во программ | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 5 | 8 | 8 | 10 | 11 | 14 | 14 |
Ответ: 14.
Задача 11
У исполнителя Считатель-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
Задача 12
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 21, траектория вычислений которых не проходит через число 15? Траектория вычислений - множество чисел, через которые проходила конкретная программа для получения одного числа из другого.
Решение
Будем считать количество программ постепенно для каждого числа слева направо по следующему принципу:
Если число А можно получить с помощью 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 |
| Кол-во программ | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 | 20 | 26 | 0 | 10 | 10 | 20 | 20 | 34 | 34 |
Ответ: 34
Задача 13
У исполнителя Считатель-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
Задача 14
У исполнителя Считатель-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.
Задача 15
У исполнителя Считатель-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.
Задача 16
У исполнителя A2M5 две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 5
Первая из них увеличивает данное число на 2, вторая - увеличивает его в 5 раз. Программа для исполнителя A2M5 - это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 35.
Решение
Заметим, что все числа, получаемые с помощью заданных команд из числа 1, нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 35 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 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 | ||||||||||
| 5 | 5 | 5 | 7 |
Ответ: 7.
Решение на С++
int main(){
const int n0 = 1, nk = 35;
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 % 5 == 0 && n / 5 >= n0)
arr[n] += arr[n / 5]; // Kn/2
}
cout << arr[nk];
return 0;
}
Решение на Python
def f(n, r):
if n == r:
return 1
if n > r:
return 0
if n < r:
return f(n + 2, r) + f(n * 5, r)
print(f(1, 35))
Задача 17
У исполнителя Считатель-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.
Задача 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
У исполнителя X13 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 3
Первая из них увеличивает число на экране на 1, вторая - в 3 раза. Программа для исполнителя X13 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 34, причём траектория вычислений содержит число 11?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3; 9; 10; 11.
Решение
Количество программ, которые число 1 преобразуют в число 34 и при этом траектория вычислений содержит число 11 равно произведению числа программ, которые преобразуют число 1 в число 11 на число программ, преобразующих число 11 в число 34.
Сначала определим количество программ, преобразующих число 1 в 11. Будем решать поставленную задачу последовательно для чисел 1, 2, 3, . . . , 11 (то есть для каждого из этих чисел определим, сколько программ исполнителя существует для его получения).
Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 3, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i - 1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 и умножь на 3, тогда R(i) = R(i - 1) + R(i/3). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 5 | 5 | 5 |
Следовательно, количество программ, преобразующих число 1 в 11, равно 5.
Теперь определим количество программ, преобразующих число 11 в 34.
Будем считать, что R(11) = 1. Для каждого следующего числа 12, 13, . . . , 34 рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 3, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i - 1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 и умножь на 3, тогда R(i) = R(i - 1) + R(i/3). Заполним соответствующую таблицу по приведённым формулам слева направо:
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
Следовательно, количество программ, преобразующих число 11 в 34, равно 2.
Количество программ, которые число 1 преобразуют в число 34 и при этом траектория вычислений содержит число 11, равно 5 · 2 = 10.
Ответ: 10.
Задача 20
У исполнителя Считатель-1 две команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
Первая из них увеличивает число на экране на 1, вторая - в 2 раза. Программа для исполнителя Считатель-1 - это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 20, у которых траектория вычислений проходит через число 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 |
| Кол-во программ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
Ответ:
Рекомендуемые курсы подготовки
- 🔥 Изучишь одни из самых фундаментальных тем информатики
- 🔥 Научишься решать 6 задач формата ЕГЭ руками
- 🔥 Начнёшь свой путь в проге
- 🔥 Учёба на Турбо: познакомишься с преподавателями и личным кабинетом
Что тебя ждет?
- 8 вебинаров (1 веб в неделю по 1 часу)
- Тестовые Д/З после каждого занятия
- Конспекты и скрипты к урокам
- Доступ к личному кабинету
- Возможность отрабатывать задания ЕГЭ в любое время
- Чат с единомышленниками
- Поддержка препа 24/7
на бесплатном курсе Турбо ЕГЭ
