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

16.02 Две функции

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

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

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

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

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

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

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

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

Алгоритмы вычисления значения функции $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])

Рекурсивное решение
В задаче заданы два рекурсивных алгоритма – функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В функции $F$ через условные операторы $if$ задаём два базовых случая: что возвращать при $n == 0$ и $n == 1$ . В остальных случаях используем рекурсивную формулу. В функции $G$ также через $if$ задаём базовые случаи: при $n < 5$ и $n == 5$ . Иначе используем рекурсивную формулу. В завершение вычисляем значение $F(5)+ G(8)$ и выводим результат.

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

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


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

    # Рекурсивный случай. Та же история, что и выше:
    # n точно больше пяти
    return g(n - 1) + f(n - 2)


# считаем и выводим ответ
print(f(5) + g(8))

Ответ: 12550501

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

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

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

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

Алгоритм вычисления значений функций $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)$ ?

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

Рекурсивное решение
В задаче заданы два рекурсивных алгоритма – функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В функции $F$ через условный оператор $if$ задаём базовый случай: что возвращать при $n == 1$ . В остальных случаях используем рекурсивную формулу. В функции $G$ также через $if$ задаём базовый случай: тоже при $n == 1$ . Иначе используем рекурсивную формулу. В завершение вычисляем значение $G(7)+ F (4)$ и выводим результат.

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

    # Рекурсивный случай, сюда попадаем при n >= 2
    return f(n - 1) - 2 * g(n - 1)


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

    # Рекурсивный случай. Аналогично с функцией f,
    # тут n точно >= 2
    return f(n - 1) + 2 * g(n - 1)


# считаем и выводим ответ
print(g(7) + f(4))

Ответ: -108

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

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

Ниже записаны две рекурсивные функции 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)$

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

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

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

    # рекурсивный случай, сюда попадем при n > 2
    return f(n - 2) + g(n - 2)


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

    # рекурсивный случай, сюда попадем при n > 3
    return g(n - 1) + f(n - 2) * f(n - 2)


# считаем и выводим ответ
print(f(6) + g(8))

Ответ: 750

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

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

Ниже записаны две рекурсивные функции 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)$

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

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

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

    # рекурсивный случай, сюда попадём при n > 1
    return f(n - 2) + 2 * g(n - 1)


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

    # рекурсивный случай, сюда попадём при n > 2
    return g(n - 2) + 2 * f(n - 2) * f(n - 2)


# считаем и выводим ответ
print(f(5) + g(6))

Ответ: 3237

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

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

Ниже записаны две рекурсивные функции 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)$

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

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

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


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


# считаем и выводим результат
print(F(7) + G(8))

Ответ: 776

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

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

Ниже записаны две рекурсивные функции $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)$ ?

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

Рекурсивное решение
В задаче заданы два рекурсивных алгоритма – функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В функции $F$ через условный оператор $if$ задаём базовый случай при $n < 10$ , а в остальных случаях используем рекурсивную формулу $F (n)∗F (n− 2)$ . В функции $G$ через $if$ задаём базовый случай при $n < 11$ , иначе применяем рекурсивную формулу $F (n2) +F (n2 + 1)+ F (nn)$ для чисел, которые не делятся на 7. В завершение вычисляем значение $G (10)F(2) + F(5)$ и выводим результат.

def F(n):  # объявляем функцию F(n)
    if n < 10:  # базовый случай
        return n
    # рекурсивный случай, сюда попадем при n > 9
    return F(n) * F(n - 2)


def G(n):  # объявляем функцию G(n)
    if n < 11:  # базовый случай
        return n * 3
    # рекурсивный случай для n > 10 и не делящегося на 7
    if n % 7 != 0:
        return F(n ** 2) + F(n ** 2 + 1) + F(n * n)


# вычисляем и выводим результат
print(G(10) ** F(2) + F(5))

Ответ: 905

Курсы

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

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

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

Ниже записаны две рекурсивные функции $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)))))?$

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

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

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


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


# вычисляем значение F(G(F(G(22))))
result = f(g(f(g(22))))

# преобразуем результат в строку и считаем сумму цифр
s = 0  # счётчик для суммы
for digit in str(result):  # digit - каждая отдельная цифра в строковом виде
    s += int(digit)  # преобразуем в int и добавляем в счётчик
print(s)

Ответ: 681

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

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

Алгоритм вычисления значений функций $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$ ).

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

Рекурсивное решение
В задаче заданы два рекурсивных алгоритма – функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В функции $F$ через условный оператор $if$ задаём базовый случай при $n < 5$ . Если $n > 4$ и делится на $5$ , вызываем $F$ от $n ∕∕5$ . В остальных случаях вычисляем значение по рекурсивной формуле из условия. В функции $G$ аналогично: базовый случай при $n < 7$ , затем случай с $n > 6$ , кратным семи, и в остальных случаях – рекурсивная формула. Далее перебираем $n$ от $0$ до $999$ , проверяем условие $G (n)+ F(n) < 3$ , и если оно выполняется, добавляем $n$ к сумме. В конце выводим результат.

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

    if n % 5 == 0:  # рекурсивный случай для n > 4, кратных 5
        return f(n // 5)

    # рекурсивный случай, сюда попадём при n > 4 и не кратных 5
    return n - 5 * (n // 5) + f(n - 5 * (n // 5))


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

    if n % 7 == 0:  # рекурсивный случай для n > 6, кратных 7
        return g(n // 7)

    # рекурсивный случай, сюда попадём при n > 6 и не кратных 7
    return n - 7 * (n // 7) + g(n - 7 * (n // 7))


ans = 0  # счётчик для суммы подходящих n
for n in range(1000):
    if g(n) + f(n) < 3:  # проверяем, что n подходит
        ans += n  # добавляем в сумму само n

print(ans)

Ответ: 15

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

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

Алгоритм вычисления значений функций $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)$ ?

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

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

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

    # рекурсивный случай, сюда попадём при n > 1
    return F(n - 1) + 2 * G(n - 1)


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

    if n % 2 == 1 and n > 1:  # рекурсивный случай для нечётного n > 1
        return F(n - 1) + G(n - 1)

    # рекурсивный случай, сюда попадём при чётном n > 1
    return F(n - 2) + G(n - 2)


# считаем и выводим значение выражения
print(F(25) - G(25))

Ответ: -699883104

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

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

Алгоритм вычисления значений функций $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)$ ?

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

Рекурсивное решение
В задаче заданы два рекурсивных алгоритма – функции $F(n)$ и $G (n )$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В функции $F$ через условный оператор $if$ задаём базовый случай при $n = 1$ , а в остальных случаях используем рекурсивную формулу $F(n− 1)− G (n− 1)$ . В функции $G$ через $if$ задаём базовый случай при $n = 1$ , иначе применяем рекурсивную формулу $F(n − 1) + 3∗G (n − 1)$ . В завершение вычисляем значение $G (16) +F (9)$ и выводим результат.

def f(n):
    if n == 1:  # базовый случай
        return 1
    # рекурсивный случай, сюда попадём при n >= 2
    return f(n - 1) - g(n - 1)


def g(n):
    if n == 1:  # базовый случай
        return 1
    # рекурсивный случай, сюда попадём при n >= 2
    return f(n - 1) + 3 * g(n - 1)


print(g(16) + f(9))  # вычисляем и выводим ответ

Ответ: 522496

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

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

Ниже записаны две рекурсивные функции $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)$

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

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

def F(n):
    if n <= 2:  # базовый случай
        return n * n
    # рекурсивный случай, сюда попадём при n > 2
    return F(n - 2) + G(n - 1) * 2 - n


def G(n):
    if n <= 2:  # базовый случай
        return n + 1
    # рекурсивный случай, сюда попадём при n > 2
    return G(n - 1) + F(n - 2) + n


print(F(5) + G(3))  # вычисляем и выводим ответ

Ответ: 36

Интенсивы

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

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

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

Алгоритм вычисления значений функций $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])

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

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


def g(n):
    if n < 2:  # базовый случай
        return n ** 3
    # рекурсивный случай, сюда попадём при n >= 2
    return f(n + 1)


print(f(18))  # вычисляем и выводим ответ

Ответ: 324

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

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

Алгоритм вычисления значений функций $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)$ ?

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В обеих через $if$ задаём одинаковый базовый случай при $n < 3$ , где возвращаем $2$ . Для $F$ в рекурсивном случае используем формулу $F(n − 1) + 2∗G (n− 1)+ F (n∕∕2)$ . Для $G$ — формулу $F (n − 1)+ G(n∕∕3)+ G (n− 1)$ . В конце вычисляем $F(12)+ G (4)$ и выводим результат.

def F(n):
    if n < 3:  # базовый случай
        return 2
    # рекурсивный случай, сюда попадём при n > 2
    return F(n - 1) + 2 * G(n - 1) + F(n // 2)


def G(n):
    if n < 3:  # базовый случай
        return 2
    # рекурсивный случай, сюда попадём при n > 2
    return F(n - 1) + G(n // 3) + G(n - 1)


print(F(12) + G(4))  # выводим ответ

Ответ: 29476

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

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

Алгоритм вычисления значений функций $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)$ ?

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

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

def F(n):  # функция F(n)
    if n < 3:  # базовый случай
        return 2 * n * n + 2
    # рекурсивный случай, сюда попадём при n > 2
    return F(n - 1) + G(n - 2)


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


print(F(15) * G(5))  # вывод результата

Ответ: 56928

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

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

Алгоритм вычисления значений функций $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$ )?

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В обеих через $if$ задаём одинаковый базовый случай при $n <= 1$ , где возвращаем $11$ . Для $F$ в рекурсивном случае используем формулу $F(n − 5)+ n∗ G(n∕∕4)$ . Для $G$ – формулу $F (n ∕∕3) + G(n− 1)$ . В завершение вычисляем $G (21)$ , преобразуем результат в строку, суммируем цифры и выводим сумму.

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


def g(n):  # объявляем функцию G(n)
    if n <= 1:  # базовый случай
        return 11
    # рекурсивный случай, сюда попадём при n > 1
    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Максимум баллов за задание: 1

Алгоритм вычисления значения функций $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.

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

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

Рекурсивное решение
В задаче определены две взаимно рекурсивные функции $F(n)$ и $G (n)$ . Для реализации создаём две пользовательские функции в Python с помощью $def$ . В $F(n)$ базовый случай при $n < 12$ , где возвращаем $n$ , для $n > 11$ будут два варианта: для чётных вычисляем $G (n∕∕2)∗ 2− F (n − 1)$ , для нечётных $− G(n − 1)$ . В функции $G(n)$ при $n < 12$ будет 3 варианта: если $n$ не делится на 3, используем $F(n− 1)+ n$ , если делится – $G (n− 1)+ F (n ∕∕3) − n$ , в остальных случаях возвращаем $n∗ n$ . Затем перебираем $n$ от 1000 до 1 (чтобы рассматривать сначала наибольшее n), считаем сумму цифр $F (n)$ и выводим наибольшее $n$ , у которого сумма цифр равна 33, завершаем перебор.

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


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


for i in range(1000, 0, -1):  # перебор от 1000 до 1

    # вычисляем модуль f(i) (чтобы отбросить знак) и обнуляем сумму
    s, summa = abs(f(i)), 0

    while s > 0:  # подсчёт суммы цифр
        summa += (s % 10)  # забираем последнюю цифру в сумму
        s //= 10  # "обрезаем" последнюю цифру
    if summa == 33:  # проверка условия
        print(i)  # выводим наибольшее n
        break  # завершаем цикл

Ответ: 946

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

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

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

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

Алгоритмы вычисления значения функции $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)$ ?

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

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

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


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


print(F(6) + Q(4))  # вычисляем и выводим результат

Ответ: 727

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

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

Алгоритм вычисления функций $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)?

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

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

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


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


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


print(sum_of_digits(F(20)))  # вычисляем и выводим сумму цифр F(20)

Ответ: 39

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

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

Алгоритм вычисления функций 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)?

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

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

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


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


print(g(5))  # вычисляем G(5) и выводим результат

Ответ: 1465

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

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

Алгоритм вычисления значения функций $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)$ ?

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

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

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

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


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


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

Ответ: -28636