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

16.02 Две функции

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

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

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

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

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

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

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

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

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

$F (n) = n− 1$ при $n ≤ 5$

$G (n) = n− 4$ при $n ≤ 5$

$F (n) = F(n − 1) ∗F(n − 1)− G(n− 4) − 2$ при $n > 5$ .

$G (n) = G(n − 3) ∗G(n − 3)− F(n− 4) +2$ при $n > 5$ .

Чему равно значение функции $F(9)$ ?

В ответе запишите только целое число.

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n <= 5$ , где возвращаем $n − 1$ , и рекурсивным случаем для $n > 5$ . Аналогично объявляем функцию $G(n)$ с базовым случаем при $n <= 5$ , где возвращаем $n − 4$ , и рекурсией для $n > 5$ . В конце вычисляем $F (9)$ и получаем ответ.

def f(n):  # объявляем функцию F(n)
    if n <= 5:
        return n - 1  # базовый случай
    # рекурсивный случай для n > 5
    return f(n - 1) * f(n - 1) - g(n - 4) - 2


def g(n):  # объявляем функцию G(n)
    if n <= 5:
        return n - 4  # базовый случай
    # рекурсивный случай для n > 5
    return g(n - 3) * g(n - 3) - f(n - 4) + 2


print(f(9))  # вычисляем F(9) и выводим результат

Ответ: 4227990526

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

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

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

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

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

$F (n) = 1$ при $n ≤ 3$

$G (n) = 1$ при $n ≤ 1$

$F (n) = G(n − 1) ∗F(n∕∕4)− 12$ при $n > 3$

$G (n) = F(n − 3) +G (n∕∕3)+ 1$ при $n > 1$

Найдите такое $n$ , при котором $F(n) = 14145$ .

Примечание. Знак // – означает деление нацело.

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n <= 3$ , где возвращаем $1$ , и рекурсивным случаем для $n > 3$ . Аналогично объявляем функцию $G(n)$ с базовым случаем при $n <= 1$ , где возвращаем $1$ , и рекурсией для $n > 1$ . В конце перебираем значения $n$ и находим такое, при котором $F (n ) = 14145$ .

def f(n):  # объявляем функцию f(n)
    if n <= 3:
        return 1  # базовый случай
    # рекурсивный случай для n > 3
    return g(n - 1) * f(n // 4) - 12


def g(n):  # объявляем функцию g(n)
    if n <= 1:
        return 1  # базовый случай
    # рекурсивный случай для n > 1
    return f(n - 3) + g(n // 3) + 1


for n in range(100):  # перебор значений n
    if f(n) == 14145:  # проверка условия
        print(n)  # выводим n

Ответ: 26

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

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

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

$F (n) = n$ при $n ≤ 2$

$G (n) = n− 1$ при $n ≤ 2$

$F (n) = G(n∕∕2)+ F (n − 2)$ при $n > 2$

$G (n) = F(n − 2) − G (n∕∕5)+ 11$ при $n > 2$

Найдите такое $n$ , при котором $G(n) = 7693$ .

Примечание. Знак // – означает деление нацело.

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n <= 2$ , где возвращаем $n$ , и рекурсивным случаем для $n > 2$ . Аналогично объявляем функцию $G(n)$ с базовым случаем при $n <= 2$ , где возвращаем $n − 1$ , и рекурсией для $n > 2$ . В конце перебираем значения $n$ и находим такое, при котором $G (n ) = 7693$ .

def f(n):  # объявляем функцию f(n)
    if n <= 2:
        return n  # базовый случай
    # рекурсивный случай для n > 2
    return g(n // 2) + f(n - 2)


def g(n):  # объявляем функцию g(n)
    if n <= 2:
        return n - 1  # базовый случай
    # рекурсивный случай для n > 2
    return f(n - 2) - g(n // 5) + 11


for n in range(100):  # перебор значений n
    if g(n) == 7693:  # проверка условия
        print(n)  # выводим n

Ответ: 81

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

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

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

$F (n) = n2$ при $n ≤ 2$

$G (n) = n− 1$ при $n ≤ 2$

$F (n) = G(n − 2) − F (n− 2)+ 8$ при $n > 2$

$G (n) = F(n − 1) +G (n− 1)$ при $n > 2$

Найдите такое $n$ , при котором $F(n) = 6607$ .

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n <= 2$ , где возвращаем $n2$ , и рекурсивным случаем для $n > 2$ . Аналогично объявляем функцию $G (n)$ с базовым случаем при $n <= 2$ , где возвращаем $n − 1$ , и рекурсией для $n > 2$ . В конце перебираем значения $n$ и находим такое, при котором $F (n ) = 6607$ .

def f(n):  # объявляем функцию f(n)
    if n <= 2:
        return n ** 2  # базовый случай
    # рекурсивный случай для n > 2
    return g(n - 2) - f(n - 2) + 8


def g(n):  # объявляем функцию g(n)
    if n <= 2:
        return n - 1  # базовый случай
    # рекурсивный случай для n > 2
    return f(n - 1) + g(n - 1)


for n in range(100):  # перебор значений n
    if f(n) == 6607:  # проверка условия
        print(n)  # выводим n
        break  # нет смысла искать дальше, завершаем цикл

Ответ: 27

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

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

Ниже записаны две рекурсивные функции $F$ и $G$ :

$F (n) = n+ 2$ , при $n ≤ 2$

$F (n) = F(n − 1) +G (n− 1)$ , при $n > 2$

$G (n) = n+ 1$ , при $n ≤ 2$

$G (n) = G(n − 1) + F(n− 2)$ , при $n > 2$

Вычислите значение выражения $∘G--(4)-+G-(3)$ .

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F (n)$ с базовым случаем при $n <= 2$ , где возвращаем $n + 2$ , и рекурсивным случаем для $n > 2$ . Аналогично объявляем функцию $G (n)$ с базовым случаем при $n <= 2$ , где возвращаем $n+ 1$ , и рекурсией для $n > 2$ . В конце вычисляем выражение $∘G--(4)-+G-(3)$ .

def f(n):  # объявляем функцию F(n)
    if n <= 2:
        return n + 2  # базовый случай
    # рекурсивный случай для n > 2
    return f(n - 1) + g(n - 1)


def g(n):  # объявляем функцию G(n)
    if n <= 2:
        return n + 1  # базовый случай
    # рекурсивный случай для n > 2
    return g(n - 1) + f(n - 2)


# вычисляем ответ
print((g(4) + g(3)) ** 0.5)

Ответ: 4

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

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

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

$F (n) = n2$ , при $n < 20$

$F (n) = G(n∕∕2)∗ 3− F(n − 2)$ , если $n > 19$ и остаток от деления $n$ на 2 равен 0

$F (n) = G(n − 2)$ , если $n > 19$ и остаток от деления $n$ на 2 равен 1

$G (n) = 3∗ n+ F(n − 2)$ , если $n < 20$ и не делится на 5

$G (n) = G(n − 2) + F(n∕∕5)$ , если $n < 20$ и делится на 5

$G (n) = n3$ , в других случаях

Определите наибольшее значение $n$ из отрезка $[1;480]$ , при котором сумма цифр значения $F(n)$ равна 48.

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n < 20$ , и двумя рекурсивными случаями для $n > 19$ в зависимости от чётности. Аналогично объявляем функцию $G(n)$ с разными рекурсивными случаями в зависимости от делимости $n$ на 5. В конце перебираем $n$ от 480 до 1 (перебираем по убыванию, чтобы найти сразу наибольшее n), вычисляем сумму цифр $F(n)$ и выводим наибольшее $n$ , где сумма равна 48.

def f(n):  # объявляем функцию f(n)
    if n > 19 and n % 2 == 0:
        # рекурсивный случай для чётных n > 19
        return g(n // 2) * 3 - f(n - 2)
    if n > 19 and n % 2 == 1:
        # рекурсивный случай для нечётных n > 19
        return g(n - 2)
    # базовый случай для n < 20
    return n ** 2


def g(n):  # объявляем функцию g(n)
    if n < 20 and n % 5 != 0:
        # рекурсивный случай для n < 20 и некратных 5
        return 3 * n + f(n - 2)
    elif n < 20 and n % 5 == 0:
        # рекурсивный случай для n < 20 и кратных 5
        return g(n - 2) + f(n // 5)
    # все остальные случаи
    return n ** 3


# перебор n от 480 до 1 для поиска наибольшего n с нужной суммой цифр
for i in range(480, 0, -1):
    s, summa = abs(f(i)), 0

    # подсчёт суммы цифр числа
    while s > 0:
        summa += (s % 10)
        s //= 10

    # проверка условия
    if summa == 48:
        print(i)  # выводим ответ
        break  # завершаем перебор

Ответ: 478

Курсы

Всё необходимое для достижения цели

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

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

Ниже записаны две рекурсивные функции $F$ и $G$ :

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

$F (n) = F(n − 1) +G (n− 2)$ , при $n > 2$

$G (n) = n+ 1$ , при $n ≤ 2$

$G (n) = G(n − 1) + F(n− 1)$ , при $n > 2$

Вычислите значение выражения $G (4) + F(5)$ .

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n <= 2$ , где возвращаем $n + 3$ , и рекурсивным случаем для $n > 2$ . Аналогично объявляем функцию $G(n)$ с базовым случаем при $n <= 2$ , где возвращаем $n + 1$ , и рекурсией для $n > 2$ . В конце вычисляем $G (4)+ F(5)$ и получаем ответ.

def f(n):  # объявляем функцию f(n)
    if n <= 2:  # базовый случай
        return n + 3
    return f(n - 1) + g(n - 2)  # рекурсивный случай


def g(n):  # объявляем функцию g(n)
    if n <= 2:  # базовый случай
        return n + 1
    return g(n - 1) + f(n - 1)  # рекурсивный случай


print(g(4) + f(5))  # вычисляем ответ

Ответ: 33

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

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

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

$F (n) = 1$ при $n = 1$

$G (n) = 2$ при $n = 1$

$F (n) = F(n − 1) +1 ⋅G(n − 1), при n > 1$

$G (n) = F(n − 1) − 2 ⋅G(n − 1), при n > 1$

Чему равна сумма цифр значения функции F(20)+G(10)?

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n = 1$ , где возвращаем $1$ , и рекурсивным случаем для $n > 1$ . Аналогично объявляем функцию $G (n)$ с базовым случаем при $n = 1$ , где возвращаем $2$ , и рекурсией для $n > 1$ . В конце вычисляем $F (20) +G (10)$ и находим сумму цифр.

def f(n):  # объявляем функцию F(n)
    if n == 1:  # базовый случай
        return 1
    return f(n - 1) + g(n - 1)  # рекурсивный случай


def g(n):  # объявляем функцию G(n)
    if n == 1:  # базовый случай
        return 2
    return f(n - 1) - 2 * g(n - 1)  # рекурсивный случай


x = f(20) + g(10)  # вычисляем выражение
s = 0  # сумма цифр
while x > 0:
    s += x % 10  # добавляем последнюю цифру в сумму
    x //= 10  # "отрезаем" последнюю цифру

print(s)  # выводим сумму

Ответ: 27

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

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

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

$F (n) = 200$ , при $n < 200$

$F (n) = (n+ 1)⋅F (n − 4)− 10⋅(n− 2)$ , при $n ≥ 200$

$G (n) = n$ , при $n ≥ 505$

$G (n) = n2 + G (n + 4)$ , при $n < 505$

Чему равна сумма цифр выражения $F(300)− G(20)$

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

Рекурсивное решение
В задаче определены две рекурсивные функции $F (n)$ и $G(n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n < 200$ , где возвращаем $200$ , и рекурсивным случаем для $n >= 200$ . Аналогично объявляем функцию $G (n)$ с базовым случаем при $n >= 505$ , где возвращаем $n$ , и рекурсией для $n < 505$ . В конце вычисляем $F (300)− G (20)$ и находим сумму цифр.

def f(n):  # объявляем функцию F(n)
    if n < 200:  # базовый случай
        return 200
    return (n + 1) * f(n - 4) - 10 * (n - 2)  # рекурсивный случай


def g(n):  # объявляем функцию G(n)
    if n >= 505:  # базовый случай
        return n
    return n ** 2 + g(n + 4)  # рекурсивный случай


x = f(300) - g(20)  # вычисляем выражение
s = 0  # счётчик для суммы цифр
while x > 0:
    s += x % 10  # добавляем последнюю цифру числа в сумму
    x //= 10  # "обрезаем" последнюю цифру

print(s)  # выводим результат

Ответ: 322

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

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

$F (n) = n$ , при $n < 15$

$F (n) = 2∗ F(n− 3)+ 4 + F(n− 1)$ , при $n ≥ 15$

$G (n) = 1+ 2∗ n$ , при $n ≥ 99$

$G (n) = n∗ G(n +2) +G (n∗ 2)$ , при $n < 99$

Чему равно значение выражения $F(52)− G (88)$

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

Рекурсивное решение
В задаче определены две рекурсивные функции $F (n)$ и $G(n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . Объявляем функцию $F(n)$ с базовым случаем при $n < 15$ , где возвращаем $n$ , и рекурсивным случаем для $n >= 15$ . Аналогично объявляем функцию $G (n)$ с базовым случаем при $n >= 99$ , где возвращаем $1 +2n$ , и рекурсией для $n < 99$ . В завершение вычисляем $F(52)− G(88)$ .

def f(n):  # объявляем функцию F(n)
    if n < 15:  # базовый случай
        return n
    return 2 * f(n - 3) + 4 + f(n - 1)  # рекурсивный случай


def g(n):  # объявляем функцию G(n)
    if n >= 99:  # базовый случай
        return 1 + 2 * n
    return n * g(n + 2) + g(n * 2)  # рекурсивный случай


print(f(52) - g(88))  # выводим результат

Ответ: -132117717082049

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

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

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

$F (n) = 2∗ (G (n − 3)+ 8);$

$G (n) = 2∗ n, если n < 10;$

$G (n) = G(n − 2) + 1, если n ≥ 10.$

Чему равно значение выражения F(15 548)?

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

Идея рекурсивного решения:

Для вычисления $F (15548)$ нужно уметь находить $G(n)$ . Функция $G(n)$ задана рекурсивно:

( { 2n, n < 10, G(n) = ( G(n − 2)+ 1, n ≥ 10.

Её реализуем как рекурсивную функцию g(n). Чтобы не пересчитывать одни и те же значения, используем мемоизацию (lru_cache). Функция $F(n)$ вычисляется через $G (n − 3)$ , поэтому достаточно вызвать f(15548).

Решение через рекурсию:

from functools import lru_cache

# Рекурсивная функция g с мемоизацией
@lru_cache(None)
def g(n):
    if n < 10:
        return 2 * n
    return g(n - 2) + 1

# Функция f через g
@lru_cache(None)
def f(n):
    return 2 * (g(n - 3) + 8)

# Выгружаем сначала в память значения функции от 1 до 15548
for i in range(15549):
    f(i)

# Вычисление результата
print(f(15548))

Идея динамического решения:

Заведём массив g и последовательно вычислим его значения: для $n < 10$ положим $g[n] = 2n$ , а для $n ≥ 10$ используем формулу $g[n] = g[n − 2]+ 1$ . После этого в массив f заполним значения по формуле $F (n ) = 2⋅(g[n − 3]+ 8)$ . Такой способ удобен, так как каждое значение считается один раз и легко получить $F (15548)$ .

Решение через динамику:

g = [0] * 16000
f = [0] * 16000

# Заполнение значений g
for n in range(16000):
    if n < 10:
        g[n] = 2 * n
    else:
        g[n] = g[n - 2] + 1

# Вычисление значений f
for n in range(16000):
    f[n] = 2 * (g[n - 3] + 8)

print(f[15548])

Ответ: 15588