Question

Задачи данного блока можно решить с циклов, однако, мы просим решить их с рекурсивных функций. Известно, что любой цикл можно заменить рекурсией.

Определить можно ли с использованием только операций «прибавить 3» и «прибавить 5» получить из числа 11 число N (N - натуральное, не превышает 106106). Разумеется, само число 11 получить можно, просто не применяя никаких операций.

Входные данные

Вводится число N.

Выходные данные

Выведите слово YES, если число N можно получить из числа 11, или NO - в противном случае.

Answer 1

Добрый день! Рад, что вы обратились ко мне за помощью. Для решения данной задачи, нам потребуется написать рекурсивную функцию, которая будет проверять, можно ли получить из числа 11 число N с помощью операций «прибавить 3» и «прибавить 5». Давайте рассмотрим пошаговое решение этой задачи.

Шаг 1: Создадим функцию с именем `check_number`, которая будет принимать один аргумент `N`. Данная функция будет возвращать `True`, если число N можно получить из числа 11, и `False` в противном случае.

Шаг 2: Внутри функции `check_number` добавим условие проверки числа N. Если N равно 11, то мы сразу же вернем `True`, так как мы уже имеем число 11 и не нужно применять никаких операций.

Шаг 3: Если число N меньше 11, то мы не сможем получить N из 11 при помощи операций «прибавить 3» и «прибавить 5». В этом случае мы также вернем `False`.

Шаг 4: Если число N больше 11, мы можем попытаться получить N из чисел N-3 и N-5, так как мы можем применить операции «прибавить 3» и «прибавить 5». Для этого вызовем функцию `check_number` рекурсивно для чисел N-3 и N-5. Если хотя бы один из этих вызовов возвращает `True`, то мы вернем `True`, так как значит, мы можем получить N из 11. Если оба вызова возвращают `False`, то мы вернем `False`.

Шаг 5: Вызовем функцию `check_number` с числом N, полученным из входных данных. Если функция вернет `True`, то мы выведем "YES", иначе выведем "NO".

Вот как будет выглядеть решение на языке Python:

```python
def check_number(N):
if N == 11:
return True
elif N < 11:
return False
else:
return check_number(N-3) or check_number(N-5)

# Считываем число N
N = int(input("Введите число N: "))

# Проверяем, можно ли получить число N из числа 11
if check_number(N):
print("YES")
else:
print("NO")
```

Теперь я объясню работу данного решения. При вызове функции `check_number` с числом N, она будет рекурсивно вызывать себя для чисел N-3 и N-5, пока не достигнет условия выхода (N равно 11 или остаток от деления на 3 и 5 не дает целое число). Если какой-то из вызовов возвращает `True`, это означает, что число N можно получить из 11, и функция `check_number` также вернет `True`. Если оба вызова вернут `False`, функция также вернет `False`.

Надеюсь, я смог объяснить эту задачу достаточно подробно и понятно. Если у вас возникнут еще вопросы, пожалуйста, не стесняйтесь задавать их. Удачи вам!