Тема 16. Рекурсивные алгоритмы

16.01 Одна функция

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела рекурсивные алгоритмы

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 141#72484Максимум баллов за задание: 1

Алгоритм вычисления значения функции $F (n)$ , где $n$ — целое неотрицательное число, задан следующими соотношениями:

$F (0) = 0;$

$F (n) = F(n∕2)+ 2$ , если $n > 0$ и при этом $n$ чётно;

$F (n) = 3+ F (n − 1)$ , если $n$ нечётно и $n > 0$ .

Назовите минимальное значение $n$ , для которого $F (n) = 21$ .

Показать ответ и решение

В задаче представлен рекурсивный алгоритм: функция $F(n)$ вычисляется в зависимости от значения $n$ . Если $n = 0$ , используется базовое выражение $F (n) = 0$ . Если $n > 0$ и $n$ чётное, применяется формула $F (n ) = F(n∕2)+ 2$ . Если $n > 0$ и $n$ нечётное, используется формула $F(n) = 3 + F(n − 1)$ . Внутри функции создаём ветвление: $n = 0$ , $n > 0$ и чётное, $n > 0$ и нечётное. Для нахождения минимального значения $n$ , при котором $F (n) = 21$ , последовательно проверяем значения $n$ , начиная с нуля, пока не достигнем нужного результата.

def F(n):
    # Базовый случай: если n = 0, возвращаем 0
    if n == 0:
        return 0
    # Если n > 0 и n чётное, используем формулу F(n/2) + 2
    if n % 2 == 0 and n > 0:
        return F(n / 2) + 2
    # Если n > 0 и n нечётное, используем формулу 3 + F(n-1)
    if n % 2 != 0 and n > 0:
        return 3 + F(n - 1)

# Ищем минимальное n, для которого F(n) = 21
i = 0
while F(i) != 21:
    i += 1
print(i)

Ответ: 67

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 142#88106Максимум баллов за задание: 1

Алгоритм вычисления значения функции $F(n)$ , где $n$ — целое положительное число, задан следующими соотношениями:

$F (n) = 1$ , если $n > 39$ ;

$F (n) = F(n ∗2)+ n +5$ , если $n <= 39$ и при этом $n$ кратно 3;

$F (n) = 1+ F (n + 4)+ 2∗ F(n+ 1)$ , если $n$ не кратно 3 и $n <= 39$ .

Назовите максимальное значение $n$ , для которого значение $F (n)$ будет кратно 3.

Показать ответ и решение

В задаче дан рекурсивный алгоритм: функция $F (n )$ вычисляется в зависимости от значения $n$ . Если $n > 39$ , используется базовое выражение $F(n) = 1$ . Если $n ≤ 39$ и $n$ кратно 3, применяется формула $F (n ) = F(n ∗2)+ n + 5$ . Если $n ≤ 39$ и $n$ не кратно 3, используется формула $F(n) = 1 + F(n+ 4)+ 2 ∗F (n + 1)$ . Для нахождения максимального значения $n$ , при котором $F (n)$ кратно 3, последовательно проверяем значения $n$ в убывающем порядке, начиная с большого числа, пока не найдём первый результат, удовлетворяющий условию.

def F(n):
    # Базовый случай: если n > 39, возвращаем 1
    if n > 39:
        return 1
    # Если n <= 39 и n кратно 3, используем формулу F(n*2) + n + 5
    if n % 3 == 0 and n <= 39:
        return F(n * 2) + n + 5
    # Если n <= 39 и n не кратно 3, используем формулу 1 + F(n+4) + 2*F(n+1)
    if n % 3 != 0 and n <= 39:
        return 1 + F(n + 4) + 2*F(n + 1)

# Ищем максимальное n, для которого F(n) кратно 3, проверяем n в убывающем порядке
for i in range(1000, 1, -1):
    t = F(i)
    if t % 3 == 0:
        print(i)
        break

Ответ: 39

Ошибка.
Попробуйте повторить позже

Задача 143#88109Максимум баллов за задание: 1

Алгоритм вычисления значения функции $F (n)$ , где $n$ - натуральное число, задан следующими соотношениями:

$F (n) = n$ , при $n > 4000$

$F (n) = F(n +2) ⋅3+ 5⋅n$ , при $n ≤ 4000$

Чему равно значение выражения $F(3988)∕F(3998)$ ?

В ответе укажите только целую часть числа.

Показать ответ и решение

В задаче представлен рекурсивный алгоритм: функция $F(n)$ вычисляется в зависимости от значения $n$ . Если $n > 4000$ , используется базовое выражение $F(n) = n$ . Если $n ≤ 4000$ , применяется формула $F (n ) = F(n + 2)⋅3+ 5⋅n$ . Внутри функции создаём ветвление: $n > 4000$ , $n ≤ 4000$ . Для нахождения значения выражения $F(3988)∕F(3998)$ рекурсивно вычисляем $F(3988)$ и $F (3998)$ , после чего берём целую часть от деления первого на второе.

def f(n):
    # Базовый случай: если n > 4000, возвращаем n
    if n > 4000:
        return n
    # Рекурсивный случай: если n <= 4000, вычисляем F(n+2) * 3 + 5 * n
    return f(n + 2) * 3 + 5 * n

# Вычисляем целую часть выражения F(3988) / F(3998)
print(f(3988) // f(3998))

Ответ: 263

Ошибка.
Попробуйте повторить позже

Задача 144#136654Максимум баллов за задание: 1

Алгоритм вычисления значения функции $F (n)$ , где $n$ – натуральное число, задан следующими соотношениями:

$F (n) = n$ при $n > 2024;$

$F (n) = n∗ F(n − 1)$ , если $n ≤ 2024$ .

Чему равно значение выражения $F(2022)∕F(2024)$ ?

Показать ответ и решение

В задаче представлен рекурсивный алгоритм: функция $F (n)$ вычисляется в зависимости от остатка от того, больше $n$ , чем 2024, или нет.

Если $n > 2024$ , функция возвращает n.

Если $n ≤ 2024$ , вычисляем $F (n) = n× F (n + 1)$ .

Внутри функции создаём ветвление для двух случаев: $n > 2024$ , $n ≤ 2024$ . После определения функции выводим значение F(2022)/F(2024).

def f(n):
    # Базовый случай: n > 2024, возвращаем n
    if n > 2024:
        return n
    # Если n <= 2024 , используем формулу n*F(n+1)
    if n <= 2024:
        return n * f(n + 1)

# Выводим результат деления и записываем в ответ
print(f(2022) / f(2024))

Ответ: 4090506

Ошибка.
Попробуйте повторить позже

Задача 145#137637Максимум баллов за задание: 1

Алгоритм вычисления значения функции $F (n)$ , где $n$ — натуральное число, задан следующими соотношениями:

$F (n) = 1$ , если $n = 1$ .

$F (n) = n+ F (n − 1)$ , если $n$ четно

$F (n) = 2∗ F(n− 2)$ , если $n > 1$ и нечетно

Чему будет равно значение, вычисленное при выполнении вызова $F(26)$ ?

Показать ответ и решение

Решение рекурсией

Сначала реализуем определение функции напрямую в виде рекурсивной функции на Python. Для этого используем оператор if для проверки условий задачи.

1. Если $n = 1$ , то по условию функция возвращает 1.

2. Если $n$ чётное, то результат вычисляется как $n +F (n− 1)$ . В программе это реализуется через проверку остатка от деления на 2.

3. Если $n > 1$ и $n$ нечётное, то вычисляем $2× F(n − 2)$ . Условие «нечётное» проверяется через оператор n % 2 != 0.

После объявления функции вызываем её для числа 26 и выводим результат.

# Определяем функцию f с параметром n
def f(n):
    # Базовый случай: если n = 1, то возвращаем 1
    if n == 1:
        return 1
    # Если n чётное, то используем формулу n + f(n-1)
    if n % 2 == 0:
        return n + f(n - 1)
    # Если n > 1 и n нечётное, то используем формулу 2 * f(n-2)
    if n > 1 and n % 2 != 0:
        return 2 * f(n - 2)

# Вычисляем значение функции при n = 26 и выводим результат
print(f(26))

—

Решение динамикой

Для избежания повторных вызовов рекурсии можно заполнить массив значениями функции последовательно.

1. Создаём список f длины 30 (с запасом), где изначально все элементы равны нулю. Каждый индекс будет соответствовать значению аргумента $n$ , а в ячейке хранится значение $F(n)$ .

2. Последовательно перебираем все $n$ от 0 до 29. Для каждого $n$ вычисляем значение по правилам:

1) если $n = 1$ , то $F (n) = 1$ ;

2) если $n$ чётное, то $F (n) = n +F (n− 1)$ ;

3) если $n > 1$ и нечётное, то $F (n) = 2× F (n− 2)$ .

3. После завершения цикла выводим значение f[26].

# Создаём список для хранения значений функции F(n)
f = [0] * 30

# Перебираем все значения n от 0 до 29
for n in range(30):
    # Если n = 1, то значение функции равно 1
    if n == 1:
        f[n] = 1
    # Если n чётное, то используем формулу F(n) = n + F(n-1)
    if n % 2 == 0:
        f[n] = n + f[n - 1]
    # Если n > 1 и n нечётное, то используем формулу F(n) = 2 * F(n-2)
    if n > 1 and n % 2 != 0:
        f[n] = 2 * f[n - 2]

# Выводим значение функции при n = 26
print(f[26])

Ответ: 4122