Как в ЕГЭ · 10 из 20
№13. Сколько программ у исполнителя
По мотивам задания №13 (в 2027 году анализ исполнения алгоритма переехал сюда из №23). У исполнителя несколько команд вида «прибавь k» и «умножь на k». Сколько существует программ, которые превращают одно число в другое, причём траектория проходит через заданные числа и не заходит в запрещённые? На маленьких числах это считают деревом на бумаге, на больших — только программой.
Что сделать
Посчитайте программы, превращающие a в b, траектория которых содержит все числа cherez и ни одного из minuya.
Что приходит
aиb— начальное и конечное число, натуральные,aменьшеbkomandy— команды строками:"+k"— прибавить k,"*k"— умножить на kcherez— числа, через которые траектория обязана пройти (список, бывает пустым)minuya— числа, в которые траектория заходить не должна (список, бывает пустым)
Что вернуть
Число программ — целое, бывает очень большим.
Допишите функцию programmy в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Из 1 в 4 командами «+1» и «2» через 2. Из 1 в 2 — две программы: «+1» и «2», обе дают 2. Из 2 в 4 — тоже две: «+1 +1» и «*2». Каждую первую половину можно продолжить каждой второй: 2 × 2 = 4.
programmy(1, 4, ["+1", "*2"], [2], [])
4
Траектория программы — числа после каждой её команды: начальное a в неё не входит, конечное b входит. Программа подходит, если последнее число траектории — b, в ней есть каждое число cherez и нет ни одного из minuya. Команды только увеличивают число: прибавляют k ≥ 1 или умножают на k ≥ 2, а a ≥ 1. Числа b до тысячи; ответ бывает длиннее сотни цифр — Python считает его точно.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.