Число программ с условиями: как решать — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: продвинутая

Исполнитель работает с числом на экране и умеет выполнять команды: 1. Прибавить 1 2. Прибавить 2 Программа — любая… Число программ с условиями — ЕГЭ по информатике, тема «Пути в графе». Ответ проверяется на странице, разбор — сразу.

Пример 1

Исполнитель работает с числом на экране и умеет выполнять команды:
1. Прибавить 1
2. Прибавить 2
Программа — любая последовательность этих команд, её траектория — числа, которые появляются на экране после каждой команды. Сколько существует программ, которые из числа 3 получают число 18, если траектория должна содержать число 7 и не должна содержать числа 13?

Ответ и разбор

Ответ: 200

Число программ, получающих число y, равно сумме чисел программ для чисел, из которых y получается одной командой: y − 1, y − 2. Команды только увеличивают число, поэтому считаем по возрастанию.
Траектория проходит через 7: программа делится на участки 3 → 7 и 7 → 18, и число программ равно произведению чисел программ на участках.
Число 13 больше 7 — оно может встретиться только на втором участке: там считаем для него 0 программ.
Участок 3 → 7: 3 — 1, 4 — 1, 5 — 2, 6 — 3, 7 — 5.
Участок 7 → 18: 7 — 1, 8 — 1, 9 — 2, 10 — 3, 11 — 5, 12 — 8, 13 — 0 (запрет), 14 — 8, 15 — 8, 16 — 16, 17 — 24, 18 — 40.
Всего: 5 · 40 = 200.

Ответ: 200.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-zs9iuv

Ещё задания этого вида — ниже. Открыть тренажёр

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

Разобранный пример

Исполнитель работает с числом на экране и умеет выполнять команды:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Программа — любая последовательность этих команд, её траектория — числа, которые появляются на экране после каждой команды. Сколько существует программ, которые из числа 4 получают число 34, если траектория должна содержать число 14 и не должна содержать числа 6?

Решение

Ответ: 15

Число программ, получающих число y, равно сумме чисел программ для чисел, из которых y получается одной командой: y − 1, y : 2 (если y чётно), y : 3 (если y делится на 3). Команды только увеличивают число, поэтому считаем по возрастанию.
Траектория проходит через 14: программа делится на участки 4 → 14 и 14 → 34, и число программ равно произведению чисел программ на участках.
Число 6 меньше 14 — оно может встретиться только на первом участке: там считаем для него 0 программ.
Участок 4 → 14: 4 — 1, 5 — 1, 6 — 0 (запрет), 7 — 0, 8 — 1, 9 — 1, 10 — 2, 11 — 2, 12 — 3, 13 — 3, 14 — 3.
Участок 14 → 34: 14 — 1, 15 — 1, 16 — 1, 17 — 1, 18 — 1, 19 — 1, 20 — 1, 21 — 1, 22 — 1, 23 — 1, 24 — 1, 25 — 1, 26 — 1, 27 — 1, 28 — 2, 29 — 2, 30 — 3, 31 — 3, 32 — 4, 33 — 4, 34 — 5.
Всего: 3 · 5 = 15.

Ответ: 15.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-fq3ad2

Формулы и приём

Подсчёт путей в графе

Как быстро посчитать все пути из А в К по стрелкам?

путей в вершину = сумма путей во все вершины, откуда ведёт стрелка · путей в старт = 1

Подписывай у каждой вершины число путей до неё: у старта единица, у любой другой — сумма чисел всех вершин, из которых в неё идёт стрелка. Если в Г ведут стрелки из Б (3 пути) и В (2 пути), то до Г ровно 3 + 2 = 5 путей. Обходи вершины по направлению стрелок, пока не дойдёшь до конечной.

Пути «через вершину Д» — перемножь число путей от старта до Д и от Д до финиша. Пути «не через Д» — из общего числа путей вычти проходящие через Д.

Ещё примеры

Пример 2

Исполнитель работает с числом на экране и умеет выполнять команды:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Программа — любая последовательность этих команд, её траектория — числа, которые появляются на экране после каждой команды. Сколько существует программ, которые из числа 6 получают число 23, если траектория должна содержать число 14 и не должна содержать числа 13?

Ответ и разбор

Ответ: 825

Число программ, получающих число y, равно сумме чисел программ для чисел, из которых y получается одной командой: y − 1, y − 2, y : 2 (если y чётно). Команды только увеличивают число, поэтому считаем по возрастанию.
Траектория проходит через 14: программа делится на участки 6 → 14 и 14 → 23, и число программ равно произведению чисел программ на участках.
Число 13 меньше 14 — оно может встретиться только на первом участке: там считаем для него 0 программ.
Участок 6 → 14: 6 — 1, 7 — 1, 8 — 2, 9 — 3, 10 — 5, 11 — 8, 12 — 14, 13 — 0 (запрет), 14 — 15.
Участок 14 → 23: 14 — 1, 15 — 1, 16 — 2, 17 — 3, 18 — 5, 19 — 8, 20 — 13, 21 — 21, 22 — 34, 23 — 55.
Всего: 15 · 55 = 825.

Ответ: 825.

Нашли ошибку? Напишите нам, код задания: ege-informatics-puti-s-usloviyami-12godjg

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.