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

16.02 Две функции

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

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

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

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

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

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

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

Задача 1#18689

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

$F (0) = 2$ ;

$F (1) = 5$ ;

$F (n) = F(n − 1) ∗F(n − 2)$ , при $n > 1$ ;

$G (n) = 0$ , при $n < 5$ ;

$G (5) = 1$ ;

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

Определите значение $F (5)+ G(8)$ .

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

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

f = [0] * 10
g = [0] * 10

# Заполняем известные значения
f[0] = 2
f[1] = 5
g[5] = 1
# Делаем перебор по возрастанию,
# так как нужно обращаться к (n-1) и (n-2),
# значения которых должны быть посчитаны заранее
for n in range(10):
    if n > 1:
        f[n] = f[n - 1] * f[n - 2]
    if n < 5:
        g[n] = 0
    if n > 5:
        g[n] = g[n - 1] + f[n - 2]

print(f[5] + g[8])

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

def f(n):
    if n == 0:
        return 2
    if n == 1:
        return 5
    return f(n - 1) * f(n - 2)

def g(n):
    if n < 5:
        return 0
    if n == 5:
        return 1
    return g(n - 1) + f(n - 2)

print(f(5) + g(8))

Ответ: 12550501

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

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

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

Задача 2#24417

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

$F (1) = 1;$ $G(1) = 1;$

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

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

Чему равно значение величины $G (7)+ F(4)$ ?

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

def f(n):
    if n == 1:
        return 1
    return f(n - 1) - 2 * g(n - 1)

def g(n):
    if n == 1:
        return 1
    return f(n - 1) + 2 * g(n - 1)
print(g(7) + f(4))

Ответ: -108

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

Задача 3#25614

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

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

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

$G (n) = n,при n ≤ 3$

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

Помогите БУ определить числовое значение выражения $F (6) + G(8)$

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

def f(n):
    if n <= 2:
        return n * 2
    if n > 2:
        return f(n - 2) + g(n - 2)

def g(n):
    if n <= 3:
        return n
    if n > 3:
        return g(n - 1) + f(n - 2) * f(n - 2)

print(f(6) + g(8))

Ответ: 750

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

Задача 4#25776

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

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

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

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

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

Помогите БУ определить числовое значение выражения $F (5) + G(6)$

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

def f(n):
    if n <= 1:
        return n * 3
    if n > 1:
        return f(n - 2) + 2 * g(n - 1)

def g(n):
    if n <= 2:
        return n
    if n > 2:
        return g(n - 2) + 2 * f(n - 2) * f(n - 2)

print(f(5) + g(6))

Ответ: 3237

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

Задача 5#25935

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

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

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

$G (n) = n⋅4,при n ≤ 1$

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

Помогите БУ определить числовое значение выражения $F (7) + G(8)$

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

def F(n):
    if n <= 2:
        return n * n
    if n > 2:
        return F(n - 1) + G(n - 2)

def G(n):
    if n <= 1:
        return n * 4
    if n > 1:
        return G(n - 1) + F(n - 2) * F(n - 3)

print(F(7) + G(8))

Ответ: 776

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

Задача 6#25962

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

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

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

$G (n) = n⋅3, при n < 11$

$G (n) = F(n2)+ F (n2 + 1)+ F(nn), когда n > 10, и не делится на 7$

Чему равно выражение $G (10)(F(2)) + F(5)$ ?

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

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

def F(n):
    if n < 10:
        return n
    if n > 9:
        return F(n) * F(n - 2)

def G(n):
    if n < 11:
        return n * 3
    if n > 10 and n % 7 != 0:
        return F(n ** 2) + F(n ** 2 + 1) + F(n * n)

print(G(10) ** F(2) + F(5))

Ответ: 905

Курсы

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

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

Задача 7#26068

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

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

$F (n) = F(n%5 )+ 1, при n > 10 и кратном 10$

$F (n) = n⋅F (n− 1), при n > 10 и не кр атном 10$

$G (n) = n⋅n + 1⋅n + 3, при n ≥ 21$

$G (n) = 2⋅G (n − 2)⋅G(n − 4), при четном n, которое м еньш е 21$

$G (n) = 2⋅G (n − 1)⋅G(n − 3), при неч етном n, которое меньш е 21$

Чему равна сумма цифр данного выражения $(F (G (F (G(22)))))?$

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

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

def f(n):
    if n <= 10:
        return n
    if n % 10 == 0:
        return f(n % 5) + 1

    return n * f(n - 1)

def g(n):
    if n >= 21:
        return n * n + 1 * n + 3
    if n % 2 == 0:
        return 2 * g(n - 2) * g(n - 4)

    return 2 * g(n - 1) * g(n - 3)

print(sum(int(_) for _ in (str(f(g(f(g(22))))))))

Ответ: 681

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

Задача 8#26095

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

$F (n) = 1, при n < 5;$

$F (n) = F(n∕∕5), если n > 4 и при этом n д ели тся на 5;$

$F (n) = n− 5 ∗(n∕∕5)+ F(n − 5 ∗(n∕∕5)), если n > 4 и при этом n не делится на 5;$

$G (n) = 1, при n < 7;$

$G (n) = G(n∕∕7), если n > 6 и при этом n дели тся на 7;$

$G (n) = n− 7 ∗(n∕∕7)+ G(n − 7∗(n∕∕7)), если n > 6 и при этом n не делится на 7;$

При каких (каком) значениях (значении) n, выражение: $G (n) + F(n)$ , меньше $3$ . В качестве ответа укажите сумму таких значений $n$ .

(Например: $G(a)+ F (a) < 3$ , $G (b)+ F (b) < 3$ . В ответ указываем сумму $a$ и $b$ ).

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

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

def f(n):
    if n < 5:
        return 1
    if n % 5 == 0:
        return f(n // 5)
    return n - 5 * (n // 5) + f(n - 5 * (n // 5))

def g(n):
    if n < 7:
        return 1
    if n % 7 == 0:
        return g(n // 7)
    return n - 7 * (n // 7) + g(n - 7 * (n // 7))

ans = 0
for n in range(1000):
    if g(n) + f(n) < 3:
        ans += n
print(ans)

Ответ: 15

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

Задача 9#26149

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

$G (n) = 1, при n < 2;$

$G (n) = F(n − 1) +2 ⋅G(n − 1), если n больше 1;$

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

$F (n) = F(n − 1) +G (n− 1), если n нечетное и больш е 1;$

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

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

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

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

def G(n):
    if n < 2:
        return 1
    if n > 1:
        return F(n - 1) + 2 * G(n - 1)

def F(n):
    if n < 2:
        return 1
    if n % 2 == 1 and n > 1:
        return F(n - 1) + G(n - 1)
    if n % 2 == 0 and n > 1:
        return F(n - 2) + G(n - 2)

print(F(25) - G(25))

Ответ: -699883104

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

Задача 10#27459

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

$F (1) = 1; G (1) = 1;$

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

$G (n) = F(n − 1) +3 ⋅G(n − 1), при n ≥ 2$

Чему равно значение величины $G (16)+ F(9)$ ?

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

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

def f(n):
    if n == 1:
        return 1
    return f(n - 1) - g(n - 1)

def g(n):
    if n == 1:
        return 1
    return f(n - 1) + 3 * g(n - 1)

print(g(16) + f(9))

Ответ: 522496

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

Задача 11#27998

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

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

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

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

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

Определите числовое значение выражения $F (5) + G(3)$

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

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

def F(n):
    if n <= 2:
        return n * n
    if n > 2:
        return F(n - 2) + G(n - 1) * 2 - n

def G(n):
    if n <= 2:
        return n + 1
    if n > 2:
        return G(n - 1) + F(n - 2) + n

print(F(5) + G(3))

Ответ: 36

Интенсивы

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

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

Задача 12#30446

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

$F (n) = n2$ , при $n > 10$

$F (n) = F(n +2) − 2 ∗G (n + 1)$ , при $n ≤ 10$

$G (n) = n3$ , при $n < 2$

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

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

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

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

f = [0] * 200
g = [0] * 200
# Делаем перебор по убыванию,
# так как обращение идёт к (n+1) и (n+2),
# которые должны быть посчитаны заранее
for n in range(100, -1, -1):
    if n > 10:
        f[n] = n ** 2
    if n <= 10:
        f[n] = f[n + 2] - 2 * g[n + 1]
    if n < 2:
        g[n] = n ** 3
    if n >= 2:
        g[n] = f[n + 1]
print(f[18])

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

def f(n):
    if n > 10:
        return n ** 2
    else:
        return f(n + 2) - 2 * g(n + 1)


def g(n):
    if n < 2:
        return n ** 3
    else:
        return f(n + 1)


print(f(18))

Ответ: 324

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

Задача 13#30448

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

$F (n) = G(n) = 2$ , при $n < 3$

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

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

где $∕$ значит целочисленное деление

Чему равно значение $F (12) + G(4)$ ?

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

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

def F(n):
    if n < 3:
        return 2
    return F(n - 1) + 2 * G(n - 1) + F(n // 2)

def G(n):
    if n < 3:
        return 2
    return F(n - 1) + G(n // 3) + G(n - 1)

print(F(12)+ G(4))

Ответ: 29476

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

Задача 14#30449

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

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

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

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

$G (n) = G(n − 2) + n∗n − 3$ , при $n > 2$

Чему равно значение $F (15) ∗G(5)$ ?

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

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

def F(n):
    if n < 3:
        return 2 * n * n + 2
    return F(n - 1) + G(n - 2)

def G(n):
    if n < 3:
        return 2 * n * n + 2
    return G(n - 2) + n * n - 3

print(F(15) * G(5))

Ответ: 56928

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

Задача 15#30451

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

$F (n) = G(n) = 11$ , при $n ≤ 1$

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

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

Чему равна сумма цифр значения функции G( $21$ )?

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

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

def f(n):
    if n <= 1:
        return 11
    return f(n - 5) + n * g(n // 4)

def g(n):
    if n <= 1:
        return 11
    return f(n // 3) + g(n - 1)

summa = 0
s = str(g(21))
for i in s:
    summa += int(i)

print(summa)

Ответ: 18

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

Задача 16#30453

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

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

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

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

$G (n) = F(n − 1) +n$ , если $n < 12$ и не делится на 3

$G (n) = G(n − 1) + F(n∕3)− n$ , если $n < 12$ и делится на 3

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

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

Примечание: знак </> в данной задаче означает целочисленное деление.

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

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

def f(n):
    if n > 11 and n % 2 == 0:
        return g(n // 2) * 2 - f(n - 1)
    if n > 11 and n % 2 == 1:
        return -g(n - 1)
    return n

def g(n):
    if n < 12 and n % 3 != 0:
        return f(n - 1) + n
    elif n < 12 and n % 3 == 0:
        return g(n - 1) + f(n // 3) - n
    return n * n

for i in range(1000, 0, -1):
    s, summa = abs(f(i)), 0
    while s > 0:
        summa += (s % 10)
        s //= 10
    if summa == 33:
        print(i)
        break

Ответ: 946

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

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

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

Задача 17#36055

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

$F (1) = 1$

$F (k) = F(k− 1)⋅k$

$Q (1) = 1$

$Q (2) = 3$

$Q (k) = Q(k− 2)+ Q (k− 1)$

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

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

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

def f(n):
    if n == 1:
        return 1
    return f(n - 1) * n

def q(n):
    if n == 1:
        return 1
    if n == 2:
        return 3
    return q(n - 2) + q(n - 1)

print(f(6) + q(4))

Ответ: 727

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

Задача 18#54929

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

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

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

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

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

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

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

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

from functools import lru_cache

def sum_of_digits(n): # Функция,подсчитывающая сумму цифр числа
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s

@lru_cache(None)
def f(n):
    if n == 1:
        return 1
    if n > 1:
        return f(n - 1) + 2 * g(n - 1)

@lru_cache(None)
def g(n):
    if n == 1:
        return 1
    if n > 1:
        return f(n - 1) - 3 * g(n - 1)

print(sum_of_digits(f(20)))

Ответ: 39

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

Задача 19#58970

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)

def f(n):
    if n == 1:
        return 2
    if n > 1:
        return g(n - 1) * f(n - 1) - n ** n
def g(n):
    if n == 1:
        return 2
    if n > 1:
        return 5 * f(n - 1) - n * g(n - 1)

print(g(5))

Ответ: 1465

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

Задача 20#60482

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

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

$G (n) = 2$ при $n ≤ 3$

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

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

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

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

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

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

def f(n):
    if n <= 2:
        return 1
    if n > 2:
        return f(n - 1) + g(n - 2) - 2

def g(n):
    if n <= 3:
        return 2
    if n > 3:
        return g(n - 1) - f(n - 2) + 2

print(f(31))

Ответ: -28636