23.03 Количество программ из A в B где траектория вычислений содержит число(-а)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Идея решения
Решение строится с помощью рекурсивной функции f(a,b), которая считает количество способов преобразовать число a в число b. Функция работает так: - если a < b, то решений нет (возвращается 0); - если a == b, то найден один путь (возвращается 1); - иначе выполняем рекурсивный вызов от двух возможных шагов: a - 2 (команда A) и a // 2 (команда B).
Чтобы учесть требование, что траектория должна содержать число 16, используем произведение:
Таким образом, считаем количество программ, которые ведут от 38 до 16, и затем от 16 до 2.
Решение:
def f(a, b): # Нет решений, если текущее число меньше целевого if a < b: return 0 # Если дошли ровно до b, найден один путь if a == b: return 1 # Рекурсивно пробуем обе команды: A (a-2) и B (a//2) return f(a - 2, b) + f(a // 2, b) # Считаем количество программ через промежуточное число 16 print(f(38, 16) * f(16, 2))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
