23.06 Количество программ из A в B где траектория вычислений N команда
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Поделить на 2, если число четное
2. Прибавить 1
3. Прибавить треть числа, если число кратно трем
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 60, при этом программа содержит 25 команд, при этом одно и то же число может встречаться несколько раз в траектории вычислений исполнителя.
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 12223 при исходном числе 6 траектория будет состоять из чисел 3, 4, 5, 6, 8.
Решение 1 (Рекурсия)
from functools import lru_cache # программа будет долго считать, если # не хранить результаты в кэше @lru_cache(None) def f(st, fn, count, end_count): if st == fn and count == end_count: return 1 if count > end_count: return 0 x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0) y = f(st + 1, fn, count + 1, end_count) z = f(st + st // 3, fn, count + 1, end_count) * (st % 3 == 0) return x + y + z print(f(1, 60, 0, 25))
Решение 2 (Динамика)
ans = [] ans.append(1) for operations in range(25): can_get = [] for i in ans: if i % 2 == 0: can_get.append(i // 2) can_get.append(i + 1) if i % 3 == 0: can_get.append(i + i // 3) ans = can_get print(ans.count(60))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
