23.08 Прочие прототипы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 8
2. Умножь на 3
3. Увеличь на разряд единиц
Первая из них увеличивает число на экране на 8, вторая увеличивает число на экране в 3 раза, третья увеличивает число на экране на значение разряда единиц (например число 12 увеличится на 2, а число 25 на 5). Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 174, если известно, что нельзя повторять команду, сделанную на предыдущем шаге.
Решение рекурсией
Мы решаем задачу с помощью рекурсии, создавая функцию f(a, b, c), которая возвращает количество программ,
преобразующих число 
в число 
, при этом 
— номер команды, использованной на предыдущем шаге. Алгоритм
разбиваем на последовательные логические шаги:
1. Проверка выхода за пределы:
- Если текущее число 
больше целевого числа 
, дальнейшие преобразования невозможны, поэтому функция
возвращает 0.
2. Проверка достижения цели:
- Если текущее число 
равно 
, значит мы нашли корректную программу, и функция возвращает
1.
3. Рекурсивный подсчет возможных переходов:
- Мы создаем переменную s = 0, которая будет накапливать количество программ.
- Если предыдущей командой не была команда 1 (c != 1), мы вызываем рекурсивно функцию с 
, 
, и
указываем, что предыдущей командой теперь является 1.
- Если предыдущей командой не была команда 2 (c != 2), вызываем функцию с 
, 
, и c =
2.
- Если предыдущей командой не была команда 3 (c != 3), вызываем функцию с 
, 
, и c =
3.
- Все результаты этих вызовов суммируем в переменную s и возвращаем её как итоговое количество программ для текущего состояния.
Таким образом, функция перебирает все допустимые последовательности команд, соблюдая условие, что одна и та же команда не может повторяться дважды подряд, и возвращает общее количество программ.
# Определяем функцию f(a, b, c), где a - текущее число, # b - целевое число, c - номер предыдущей команды def f(a, b, c = 0): # Если текущее число больше целевого, путь невозможен if a > b: return 0 # Если текущее число равно целевому, найден один путь if a == b: return 1 # Инициализируем переменную для подсчета количества программ s = 0 # Применяем команду 1, если предыдущей командой не была она if c != 1: s += f(a + 8, b, 1) # Применяем команду 2, если предыдущей командой не была она if c != 2: s += f(a * 3, b, 2) # Применяем команду 3, если предыдущей командой не была она if c != 3: s += f(a + (a % 10), b, 3) # Возвращаем общее количество программ из текущего состояния return s # Вызываем функцию для исходного числа 4 и целевого 174 print(f(4, 174))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
