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

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

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

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

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

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

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

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

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

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

Обозначим частное от деления натурального числа $a$ на натуральное число $b$ как $a$ $div$ $b$ , а остаток как $a$ $mod$ $b$ . Например, $13$ $div$ $3 = 4$ , $13$ $mod$ $3 = 1$ . Алгоритм вычисления значения функции $F(n)$ , где $n$ – целое неотрицательное число, задан следующими соотношениями:

$F (0) = 0;$

$F (n) = F(n$ $div$ $10) + (n$ $mod$ $10).$

Укажите количество таких чисел n из интервала $555555555 ≤ n < 1555555555$ , для которых $F (n) > F (n + 1)$

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

Заметим, что функция $F(n)$ на самом деле считает сумму цифр числа $n.$ Значит нужно понять для каких $n$ сумма цифр числа $n$ больше суммы цифр числа $n + 1.$ Такое возможно только в случае перехода между разрядами, то есть нам подходят все $n$ принадлежащие промежутку и заканчивающиеся на $9.$ Тогда нам подходит каждое десятое число, всего в промежутке $1555555555− 555555555 = 1000000000$ чисел. Итого нам подходит $1000000000 ---10----= 100000000$ чисел.

Ответ: 100000000

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

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

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

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

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

$F (0) = 0;$

$F (n) = F(n − 1) +n.$

Укажите количество таких чисел $n$ из интервала $555555555 ≤ n < 1555555555$ , для которых $F(n)$ не делится без остатка на $3$ .

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

Заметим, что функция $F(n)$ находит сумму чисел от $1$ до $n.$ Тогда мы можем найти значение функции $F(n)$ как $n⋅(n+21).$ Также заметим, что значение функции $F(n)$ дает остаток $1$ по модулю $3$ только тогда, когда $n$ дает остаток $1$ по модулю $3$ и дает остаток $0$ в остальных случаях. Для поиска ответа нам нужно посчитать количество чисел с остатком $1$ на заданном промежутке. Тогда всего нам подходит $1555555554−555555555 --------3-------= 333333333$ числа.

Ответ: 333333333

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

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

$F (0) = 0;$

$F (n) = F(n − 1) +2 ⋅n− 1.$

Найдите значение $F(55555555555).$

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

Протестируем функцию на маленьких $n$ . Получим $F(1) = 1$ $F(2) = 4$ $F (3) = 9$ $F (4) = 16$ $F(5) = 25$ $F(6) = 36.$ Оказалось, что функция $F (n)$ рекурсивно находит $n2.$ $F (55555555555) = 555555555552 = 3086419753024691358025.$

Ответ: 3086419753024691358025

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

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

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

$F (0,0) = 0;$

$F (a,b) = F (a− 1,b) + b$ , если $a > b$ ;

$F (a,b) = F (a,b − 1) + a$ , если $a ≤ b$ и $b > 0$ .

Укажите количество таких целых неотрицательных чисел $a$ , для которых можно подобрать такое $b$ , что $F (a,b) = 5555555555555$ .

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

Если начать подставлять случайные $a$ и $b$ в функцию, то станет очевидно, что $F (a,b) = a ⋅b.$ Значит нам нужно найти количество способов разложить число $n$ на произведение двух множителей. Тогда ответом будет количество делителей у числа $n$ так как для любого делителя $a$ найдется целое неотрицательное $b = n a$ . Найдем все делители $n$ с помошью кода.

def get_divs(number):
    divs = []  # Список делителей

    # Перебираем числа до корня из number
    for i in range(1, int(number ** 0.5) + 1):
        # Если i — делитель
        if number % i == 0:
            # Добавляем i
            divs.append(i)
            # Избегаем дублирования для квадратов
            if i != int(number ** 0.5):
                # Добавляем парный делитель
                divs.append(number // i)

    return divs  # Возвращаем список делителей

print(len(get_divs(5555555555555)))

Ответ: 16

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

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

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

$F (1) = 1$

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

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

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

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

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F(1) = 1$ ; $F(k) = F (k − 1)$ , если k - четное; $F(k) = F (k− 1)+ k$ , если k - нечетное. Вывдем ответ через вызов функции $f (10)$ .

def f(n):
# Базовый случай для n = 1:
    if n == 1:
        return 1
    # Рекурсивный случай для чётного n
    if n % 2 == 0:
        return f(n - 1)
    # Рекурсивный случай для нечётного n
    return f(n - 1) + n

print(f(10))

Ответ: 25

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

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

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

$f(n) = 1$ , при $n = 0$ или $n = 1$

$f(n) = f (n − 1)∗n,$ при $n > 1$

Найдите чему равно значение $f(2023)∕∕f(2022)?$

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

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $f(n) = 1$ , при $n = 0$ или $n = 1$ ; $f(n) = f(n− 1)∗n,$ при $n > 1$ . Пропишем функцию по правилам, пройдемся циклом $for$ , чтобы значения ушли в кэш и для обоих значение (2023 и 2022) не было повторных лишних вычислений, и выведем ответ.

from functools import lru_cache

# Подключаем кеширование всех результатов функции
@lru_cache(None)  # None - количество кеширований не ограничено
def F(n):
# Базовый случай для n = 0, n = 1
    if n == 0 or n == 1:
        return 1
    else:
    # Рекурсивный случай для n > 1
        return F(n - 1) * n


for n in range(2500):  # Перебираем значения n
    F(n)  # Вызываем функцию, чтобы значение было посчитано и закешировано

# Данные значения уже будут посчитаны в цикле и сохранены в кеш,
# так что превышения глубины рекурсии не возникнет
print(F(2023) // F(2022))

Динамическое решение

Для динамического решения создадим список, где каждому i-тому элементу будет соответствовать $f(i)$ . Заполним список по правилам из условия: введем руками значения для базовых случаев и для остальных посчитаем значения через цикл $for$ , получающий значения из списка. Далее выведем результат.

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

# Задаём известные значения для некоторых n
f[0] = 1
f[1] = 1

for n in range(2, 2025):  # Перебор других значений n
    f[n] = f[n - 1] * n  # при n > 1

print(f[2023] // f[2022])  # Вывод результата

Аналитическое решение

Функция вычисляет факториал, т.е. произведение всех чисел от 1 до n.

То есть $1∗2-∗⋅⋅⋅∗2022∗-2023. 1 ∗2∗ ⋅⋅⋅∗ 2022$

Значит, после деления у нас останется только число 2023.

Ответ: 2023

Курсы

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

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

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

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

$Ckn = 1$ , при $k = 0$ или $k = n$

$Ck = Ck− 1+ Ck n n− 1 n−1$

Найдите чему равно значение $10 C20$ .

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

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $k C n = 1$ , при $k = 0$ или $k = n$ ; $Ckn = Ckn−−11 + Ckn− 1$ . Пропишем функцию по правилам и выведем значение через вызов функции $C (10,20)$ .

def C(n, k):
# Базовый случай при k = 0, k = n
    if (k == 0 or k == n):
        return 1
    # Рекурсивный случай для остальных вариантов
    else:
        return C(n - 1, k - 1) + C(n - 1, k)

print(C(10, 20))

Ответ: 184756

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

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

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

$f(n) = 1$ , при $n = 0$ или $n = 1$

$f(n) = f (n − 1)∗n,$ при всех остальных $n$

Найдите, чему равно значение данного выражения: $f(2) f(3) f(10000) ---- + ----+ ...+ -------- f(1) f(2) f (9999)$

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

Решение руками

Что такое $-f-(i)--? f(i− 1)$ Это есть просто число $i$ . А значит, нужно найти сумму чисел от 2 до 10000 включительно.

Решение программой

В задаче задан рекурсивный алгоритм: функция вызывает саму себя при определённых условиях. Чтобы реализовать алгоритм программой, создадим функцию. Внутри неё задаём правила: $f (n) = 1$ при $n = 0$ и 1, иначе $f(n) = f(n − 1)∗n$ . Далее обязательно запишем @lru_cache(None) перед функцией, чтобы оптимизировать программу (без этого будет превышен лимит рекурсии). В завершении переберём числа от 2 до 10000 включительно, просуммируя отношения $-f(i)-- f(i − 1)$ .

from functools import lru_cache # импортируем кэширование для того чтобы ускорить выполнение программы за счёт того,
# что программа будет запоминать промежуточные значения функции, а не высчитывать их вновь при подсчитывании значения функции

@lru_cache(None) # применяем кэширование для функции
def f(n): # объявляем функцию
    if n == 0 or n == 1: # если n равно 0 или 1
        return 1 # возвращаем 1
    else: # в ином случае
        return f(n-1) * n
sm = 0 # переменная для подсчёта суммы выражения
for i in range(2,10001):
    sm += f(i)//f(i-1)
print(sm) # вывод ответа

Ответ: 50004999

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

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

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

$F (n) = n!$ , если $n ≥ 5000,$

$F (n) = 2⋅F (n + 1)∕(n + 1)$ , если $1 ≤ n < 5000$ .

Чему равно значение выражения $1000⋅F (7)∕F(4)$ ?

Примечание. Факториал числа $n$ , который обозначается как $n!$ , вычисляется по формуле $n! = 1⋅2 ⋅ ... ⋅n$ .

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

Динамическое решение

Решим динамически: создадим массив и заполним его значениями $n!$ для каждого $fact(n)$ , чтобы не было лишних вычислений при повторных вызовах. Далее создадим массив уже для хранения значений функции от условия — каждому i-тому элементу соответствует $f (i)$ , заполним его по функции из условия в обрятном порядке (ибо при вызове рекурсивной формулы от числа $[a]$ нужны данные по элементу $[a + 1]$ ). Вычислем ответ и выведем его через $print$ .

# Создадим массив, где последовательно просчитаем
# факториал от i-того элемента, берем 7000 с запасом
fact = [1] * 7001
for n in range(1, 7001):
    # Так как идем с единицы, а по условию
    # n! = ... * (n - 1) * n, то при последовательном вычислении
    # на каждом шаге будем домножать факториал предыдущего числа на
    # новое число, и получится факториал нового числа
    fact[n] = fact[n - 1] * n

# Создадим массив для хранения f[i]
f = [0] * 7001
# Так как рекурсивная формула обращается к значениям числа больше его
# самого, то заполняем массив по убыванию
for i in range(7000, 1, -1):
    # База рекурсии для i >= 5000
    if i >= 5000:
        f[i] = fact[i]
    else:
    # Рекуррентная формула для остальных числе
        f[i] = 2 * f[i + 1] // (i + 1)

# Вычисляем ответ
print(1000 * f[7] / f[4])

Решение аналитически:

Поскольку числа слишком большие, то будем решать аналитикой. Для начала вычислим значения $F (4999),F(4998),F(4997) :$

$F (5000) F (4999) = 2 ∗-5000- = 2∗ 4999!$

$F (4998) = 2 ∗ F-(4999) = 22 ∗ 4998! 4999$

$F (4998) F (4997) = 2 ∗------ = 23 ∗ 4997! 4998$

Замечаем, что в общем виде $F$ вычисляется как $5000−n F (n) = 2 ∗n!$

Вычислим требуемое и получим ответ.

Ответ: 26250

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

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

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

F(n) = n, если n $≤$ 0,

F(n) = 5* F(n//2) + n, если 0 < n < 100 и n – чётное.

F(n) = F(n-3) + F(n-4) , если 0 < n < 100 и n – нечётное.

Определите значение выражения: F(10) + F(20) + F(15) - F(25).

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

Решение программой:
В задаче задан рекурсивный алгоритм: функция вызывает саму себя при определённых условиях. Чтобы реализовать алгоритм программой, создадим функцию. Внутри неё задаём правила: $f(n) = n$ при $n <= 0$ , $f(n) = 5∗f(n∕∕2)+ n$ при $0 < n < 100$ и чётном $n$ , $f(n) = f(n − 3)+ f(n− 4)$ при $0 < n < 100$ и нечётном $n$ . Осталось вызывать функцию с нужными аргументами и выполнить соответствующие операции.

def F(n):
    if n <= 0:  # базовый случай
        return n
    if 0 < n < 100 and n % 2 == 0:  # рекурсивный случай 1
        return 5 * F(n // 2) + n
    if 0 < n < 100 and n % 2 != 0:  # рекурсивный случай 2
        return F(n - 3) + F(n - 4)


print(F(10) + F(20) + F(15) - F(25))

Ответ: 2691

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

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

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

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

$F (n) = False$ , если $n$ нечетно

$F (n) = F(n∕∕2),$ иначе

Определите для скольких чисел из отрезка $[2;100000000]$ функция вернет значение True?

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

Если число не будет полной степенью двойки, то при последовательном делении на $2$ мы вскоре получим нечетное число (кроме $1$ ) и вернем $F alse$ , $True$ вернут только степени двойки в данном диапазоне. Эффективно переберем все числа-степени двойки в данном отрезке

k = 0
x = 2
while x <= 100000000:
    k += 1
    x *= 2
print(k)

Ответ: 26

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

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

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

$F (n) = 5$ при $n < 3$

$F (n) = F(n − 2) +2 ∗n − 1$ при чётных $n > 3$

$F (n) = F(n − 1) ∗F(n − 2)+ 2$ при нечётных $n > 3$

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

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм: функция вызывает саму себя при определённых условиях. Чтобы реализовать алгоритм программой, создадим функцию. Внутри неё задаём правила: $f(n) = 5$ при $n < 3$ , $f(n) = f(n − 2)+ 2∗ n− 1$ при чётных $n > 3$ , $f(n) = f(n− 1) ∗f(n− 2)+ 2$ при нечётных $n > 3$ . В завершении вызываем $f (12)$ и получаем ответ.

def f(n):
    if n < 3:
        # базовый случай
        return 5
    if n > 3 and n % 2 == 0:
        # рекурсивный случай 1
        return f(n - 2) + 2 * n - 1
    if n > 3 and n % 2 != 0:
        # рекурсивный случай 2
        return f(n - 1) * f(n - 2) + 2

print(f(12))  # выводим ответ

Ответ: 80

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

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

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

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

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

Чему равно значение функции $F(5)∕F(3)$ ? В ответе укажите только целую часть числа.

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм: функция вызывает саму себя при определённых условиях. Чтобы реализовать алгоритм программой, создадим функцию. Внутри неё задаём правила: $f(n) = 2$ при $n <= 2$ , $f(n) = f(n − 1)∗(n ∗n + 5)− 4∗n$ при $n > 2$ . В завершение вызываем $f(5) ---- f(3)$ и получаем ответ.

def f(n):
    if n <= 2:  # базовый случай
        return 2
    if n > 2:  # рекурсивный случай
        return f(n - 1) * (n * n + 5) - 4 * n


print(f(5) // f(3))  # выводим ответ

Ответ: 598

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

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

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

$F (n) = n∗ n$ при $n <= 0$

$F (n) = 5∗ F(n∕∕2)+ 2∗ F(n− 1)$ при чётных $n > 0$

$F (n) = F(n − 5) ∗F(n − 8)$ при нечётных $n > 0$

Чему равно значение функции $(F(12)+ F(6))∕(F (7) − F (3))$ ? В ответе укажите только целую часть числа.

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём функцию с помощью def. Внутри функции используем условный оператор if вместе с elif и else, чтобы задать три варианта работы: что возвращать при $n <= 0$ (базовый случай), при чётных $n > 0$ и при нечётных $n > 0$ . В каждом случае в return записываем соответствующее выражение, что запускает цепочку рекурсивных вызовов. Процесс продолжается до достижения базового случая $n <= 0$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем заданное в условии выражение с использованием функции и получаем результат.

def f(n):
    if n <= 0:  # базовый случай
        return n * n
    if n > 0 and n % 2 == 0:  # рекурсивный случай 1
        return 5 * f(n // 2) + 2 * f(n - 1)
    if n > 0 and n % 2 != 0:  # рекурсивный случай 2
        return f(n - 5) * f(n - 8)


# считаем и выводим ответ
print((f(12) + f(6)) // (f(7) - f(3)))

Ответ: 19

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

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

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

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

$F (n) = F(n∕3)$ если $n > 1$ и делится на 3

$F (n) = n+ F (n + 2)$ при $n > 1$ и не делится на 3

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

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём функцию с помощью def. Внутри функции используем условный оператор if, чтобы задать три варианта работы: что возвращать при $n <= 1$ (базовый случай), при кратных трём $n > 1$ и при некратных трём $n > 1$ . В каждом случае в return записываем соответствующее выражение, что запускает цепочку рекурсивных вызовов. Процесс продолжается до достижения базового случая $n <= 1$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем заданное в условии выражение с использованием функции и получаем результат.

def f(n):  # объявление функции
    if n <= 1:  # базовый случай
        return n
    if n > 1 and n % 3 == 0:  # рекурсивный случай 1
        return f(n // 3)
    if n > 1 and n % 3 != 0:  # рекурсивный случай 2
        return n + f(n + 2)


# выводим ответ
print(f(17))

Ответ: 44

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

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

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

$F (n) = 0$ при $n ≤ 5$ ;

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

$F (n) = 2⋅F (n − 5)+ 2$ , если $n > 5$ и при этом n чётно.

Чему равно значение функции $(F (6)+ F(8)+ F(10))∕F(9)+ F(7)$ ?

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём функцию с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать три варианта работы: что возвращать при $n <= 5$ (базовый случай), при нечётных $n > 5$ и при чётных $n > 5$ . В каждом случае в return записываем соответствующее выражение, что запускает цепочку рекурсивных вызовов. Процесс продолжается до достижения базового случая $n <= 5$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем заданное в условии выражение с использованием функции и получаем результат.

def f(n):  # объявление функции
    if n <= 5:  # базовый случай
        return 0
    if n > 5 and n % 2 == 1:  # рекурсивный случай 1
        return f(n - 5) + (n + 3) / 2
    if n > 5 and n % 2 == 0:  # рекурсивный случай 2
        return 2 * f(n - 5) + 2


# считаем и выводим ответ
print((f(6) + f(8) + f(10)) / f(9) + f(7))

Решение «руками»:

Последовательно находим:

$F (1) = F(2) = F (3) = F (4) = F(5) = 0$

$F (6) = 2⋅F(1)+ 2 = 2$

$F (7) = F(1)+ 5 = 5$

$F (8) = 2⋅F(3)+ 2 = 2$

$F (9) = F(4)+ 6 = 6$

$F (10) = 2⋅F(5)+ 2 = 2$

$(F(6)+ F (8)+ F (10))∕F(9)+ F (7) = (2 + 2+ 2)∕6+ 5 = 6$

Ответ: 6

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

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

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

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

Последовательность чисел задается рекуррентным соотношением:

$F (n) = n+ 1$ при $n > 12$

$F (n) = F(n +1) +3 ⋅n$ , если $n ≤ 12$

Чему равно $F(5)$ ?

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ вместе с $else$ , чтобы задать два варианта работы: что возвращать при $n > 12$ (базовый случай) и в остальных случаях. В каждом случае в $return$ записываем соответствующее выражение, что запускает цепочку рекурсивных вызовов. Процесс продолжается до достижения базового случая $n > 12$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем $f(5)$ с использованием функции и получаем результат.

def f(n):  # объявление функции
    if n > 12:  # базовый случай
        return n + 1
    else:  # рекурсивный случай
        return f(n + 1) + 3 * n


print(f(5))  # выводим ответ

Решение «руками»:

Последовательно находим:

$F (13) = 13 + 1 = 14$ ,

$F (12) = F(13)+ 3⋅12 = 14 + 36 = 50$ ,

$F (11) = F(12)+ 3⋅11 = 50 + 33 = 83$ ,

$F (10) = F(11)+ 3⋅10 = 83 + 30 = 113$ ,

$F (9) = F(10)+ 3⋅9 = 113 + 27 = 140$ ,

$F (8) = F(9)+ 3⋅8 = 140+ 24 = 164$ ,

$F (7) = F(8)+ 3⋅7 = 164+ 21 = 185$ ,

$F (6) = F(7)+ 3⋅6 = 185+ 18 = 203$ ,

$F (5) = F(6)+ 3⋅5 = 203+ 15 = 218$ .

Ответ: 218

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

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

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

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

$F (n) = (2n + 7)⋅F(n − 2)$ , если $n > 2$ .

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

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать базовый случай: что возвращать при $n <= 2$ . Если $n > 2$ , то выполним рекурсивный вызов, который продолжается до достижения базового случая $n <= 2$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем $f (8)$ с использованием функции и получаем результат.

def f(n):  # объявление функции
    if n <= 2:  # базовый случай
        return 1
    # рекурсивный случай, дойдём до этой строчки,
    # если условие выше (n <= 2) не выполняется, то есть n > 2
    return (2 * n + 7) * f(n - 2)


print(f(8))  # выводим ответ

Решение руками:

Последовательно находим:

$F (1) = F(2) = 1$

$F (3) = 13⋅F(1) = 13$

$F (4) = 15⋅F(2) = 15$

$F (5) = 17⋅F(3) = 17 ⋅13 = 221$

$F (6) = 19⋅F(4) = 19 ⋅15 = 285$

$F (7) = 21⋅F(5) = 21 ⋅221 = 4641$

$F (8) = 23⋅F(6) = 23 ⋅285 = 6555$

Ответ: 6555

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

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

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

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

$F (n) = F(n − 2) +n ⋅n − 3$ , при $n > 5$

Определите значение, которое будет получено при вызове F(7).

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать базовый случай: что возвращать при $n <= 5$ . Если $n > 5$ , то выполним рекурсивный вызов, который продолжается до достижения базового случая $n <= 5$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем $f (7)$ с использованием функции и получаем результат.

def f(n):  # объявление функции
    if n <= 5:  # базовый случай
        return n * n + 5

    # рекурсивный случай, дойдём до этой строчки,
    # если условие выше (n <= 5) не выполняется, то есть n > 5
    return f(n - 2) + n * n - 3


print(f(7))  # выводим ответ

Решение руками:

Последовательно находим:

$F (0) = 5$

$F (1) = 1+ 5 = 6$

$F (2) = 4+ 5 = 9$

$F (3) = 9+ 5 = 14$

$F (4) = 16+ 5 = 21$

$F (5) = 25+ 5 = 30$

$F (6) = F(4)+ 36− 3 = 21 + 33 = 54$

$F (7) = F(5)+ 49− 3 = 30 + 46 = 76$

Ответ: 76

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

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

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

$F (n) = 2⋅(1+ n)$ при $n < 5$

$F (n) = (n+ 1)⋅F (n − 2)$ , если $n ≥ 5$ и n делится на 3,

$F (n) = 1+ F (n − 1)+ F(n − 2)$ , если $n ≥ 5$ и n не делится на 3.

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

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

Рекурсивное решение
В задаче задан рекурсивный алгоритм, при котором функция вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать два случая: что возвращать при $n < 5$ (базовый случай) и $n >= 5$ , кратным трём. Если ни одно из этих условий не выполняется, то число больше 5 и некратно трём, поэтому можно сразу вернуть соответствующее выражение. Цепочка рекурсивных вызовов продолжается до достижения базового случая $n < 5$ , после чего результаты возвращаются обратно по цепочке. В завершение вычисляем $f(10)$ с помощью функции и получаем результат.

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

    # Рекурсивный случай 2. Дойдём до этой строчки,
    # если условия выше не выполнятся, то есть
    # n точно больше 5 и некратно трём
    return 1 + f(n - 1) + f(n - 2)


print(f(10))  # выводим ответ

Решение руками

Последовательно находим:

$F (1) = 4$ ;