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

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

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

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

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

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

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

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

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

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

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

$F(0) = 1$

$F(1) = 1$

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

Определите значение $F (6).$

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 0$ возвращаем 1, при $n = 1$ возвращаем 1, при $n > 1$ вычисляем как $f(n − 1) ∗ f(n − 2) + f(n − 3)$ . Для нахождения $f(6)$ напрямую вызовем функцию.


# Базовые случаи: F(0) = 1, F(1) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) * f(n - 2) + f(n - 3)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * f(n - 2) + f(n - 3)  # Возвращаем значение рекурсивного выражения
    else:  # В остальных случаях — возвращаем 0, т.к. по условию данные значения вычислить нельзя
        return 0  # Возвращаем 0
print(f(6))  # Выводим результат на экран

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

Нам даны $F(0)$ и $F (1)$ . Используем их и подставляем в формулу: $F(2) = F (1) ⋅ F(0) + F (− 1) = 1,$ мы получили значение $F$ от $n = − 1, n$ должно быть натуральным числом,

следовательно $F (− 1 ) = 0.$

$F(3) = F (2) ⋅ F(1) + F (0) = 2$

$F(4) = F (3) ⋅ F(2) + F (1) = 3$

$F(5) = F (4) ⋅ F(3) + F (2) = 7$

$F(6) = F (5) ⋅ F(4) + F (3) = 23$

$23$ и будет ответом на задание.

Ответ: 23

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

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

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

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

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

$F(0) = 1$

$F(1) = 2$

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

Определите значение $F (7).$

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 0$ возвращаем 1, при $n = 1$ возвращаем 2, при $n > 1$ вычисляем как $f(n − 1) ∗ f(n − 2) − f(n − 3)$ . Для нахождения $f(7)$ напрямую вызовем функцию.


# Базовые случаи: F(0) = 1, F(1) = 2 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) * f(n - 2) - f(n - 3)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * f(n - 2) - f(n - 3)  # Возвращаем значение рекурсивного выражения
    else: return 0  # В остальных случаях при ненатуральных n вернём 0
print(f(7))  # Выводим результат на экран

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

Нам даны $F(0)$ и $F (1)$ . Используем их и подставляем в формулу: $F(2) = F (1) ⋅ F(0) − F (− 1) = 2,$ мы получили значение $F$ от $n = − 1, n$ должно быть натуральным числом,

Следовательно $F(− 1) = 0.$

$F(3) = F (2) ⋅ F(1) − F (0) = 3$

$F(4) = F (3) ⋅ F(2) − F (1) = 4$

$F(5) = F (4) ⋅ F(3) − F (2) = 10$

$F(6) = F (5) ⋅ F(4) − F (3) = 37$

$F(7) = F (6) ⋅ F(5) − F (4) = 366$

$366$ и будет ответом на задание.

Ответ: 366

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

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

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

$F(0) = 1$

$F(1) = 2$

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

Определите значение $F (7).$

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

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


# Базовые случаи: F(0) = 1, F(1) = 2 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) * f(n - 2) - f(n - 3)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * f(n - 2) - f(n - 3)  # Возвращаем значение рекурсивного выражения
    else: return 0  # В остальных случаях при ненатуральных n вернём 0
print(f(7))  # Выводим результат на экран

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

Нам даны $F(0)$ и $F(1)$ . Используем их и подставляем в формулу:

$F(2) = F (1) ⋅ F(0) + F (− 1) = 2,$ мы получили значение $F$ от $n = − 1, n$ должно быть натуральным числом, следовательно $F (− 1) = 0$

$F(3) = F (2) ⋅ F(1) + F (0) = 5$

$F(4) = F (3) ⋅ F(2) + F (1) = 12$

$F(5) = F (4) ⋅ F(3) + F (2) = 62$

$F(6) = F (5) ⋅ F(4) + F (3) = 749$

$F(7) = F (6) ⋅ F(5) + F (4) = 46450$

$46450$ и будет ответом на задание.

Ответ: 46450

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

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

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

$F(1) = 2$

$F(2) = 3$

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

Определите значение $F (4).$

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 1$ возвращаем 2, при $n = 2$ возвращаем 3, при $n > 2$ вычисляем как $f(n − 1) ∗ ∗f (n − 2)$ . Для нахождения $f(4)$ напрямую вызовем функцию.


# Базовые случаи: F(1) = 2, F(2) = 3 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) ** f(n - 2)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n == 2:  # Базовый случай — возвращаем значение без рекурсии
        return 3  # Возвращаем базовое значение
    elif n > 2:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) ** f(n - 2)  # Возвращаем значение рекурсивного выражения
    else:  # В остальных случаях — возвращаем значение
        return 0  # Возвращаем базовое значение

print(f(4))  # Выводим результат на экран

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

Нам даны $F(1)$ , $F (2)$ , которые мы подставим в формулу:

$F(3) = F (2)F(1) = 9$

$F(4) = F (3)F(2) = 729$

$729$ пишем в ответ.

Ответ: 729

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

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

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

$F(0) = 1$

$F(1) = 2$

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

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

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 0$ возвращаем 1, при $n = 1$ возвращаем 2, при $n > 1$ вычисляем как $f(n − 1) ∗ ∗f (n − 2)$ . Для нахождения $f(5)$ напрямую вызовем функцию.


# Базовые случаи: F(0) = 1, F(1) = 2 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) ** f(n - 2)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) ** f(n - 2)  # Возвращаем значение рекурсивного выражения
    else:  # В остальных случаях — возвращаем значение
        return 0  # Возвращаем базовое значение

print(f(5))  # Выводим результат на экран

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

Над даны $F (0)$ , $F (1)$ . Подставим их в формулу:

$F(2) = F (1)F(0) = 21 = 2$

$F(3) = F (2)F(1) = 22 = 4$

$F(2) 2 F(4) = F (3) = 4 = 16$

$F(3) 4 F(5) = F (4) = 16 = 65536$

$65536$ пишем в ответ.

Ответ: 65536

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

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

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

$F(0) = 0$

$F(1) = 1$

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

Определите значение $F (6).$

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 0$ возвращаем 0, при $n = 1$ возвращаем 1, при $n > 1$ вычисляем как $f(n − 1) ∗ ∗f (n − 3) + f(n − 2)$ . Для нахождения $f(6)$ напрямую вызовем функцию.


# Базовые случаи: F(0) = 0, F(1) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) ** f(n - 3) + f(n - 2)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 0  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) ** f(n - 3) + f(n - 2)  # Возвращаем значение рекурсивного выражения
    else:  # В остальных случаях — возвращаем значение
        return 0  # Возвращаем базовое значение

print(f(6))  # Выводим результат на экран

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

Нам даны $F(0)$ и $F(1)$ . Подставим их в формулу:

$F(2) = F (1)F(−1) + F (0) = 1,$ мы получили значение $F$ от $n = − 1, n$ должно быть натуральным числом, следовательно $F (− 1) = 0.$

$F(0) F(3) = F (2) + F (1) = 2$

$F(1) F(4) = F (3) + F (2) = 3$

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

$F(6) = F (5)F(3) + F (4) = 25 + 3 = 28$

$28$ и будет ответом на вопрос задачи

Ответ: 28

Курсы

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

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

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

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

$F(− 1) = 2$

$F(0) = 3$

$(n ) = F(− 1) ⋅ F (n − 1) + 2 ⋅ F (n − 1)$ . При $n > 0$ .

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

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = − 1$ возвращаем 2, при $n = 0$ возвращаем 3, при $n > 0$ вычисляем как $f(− 1) ∗ f(n − 1 ) + 2 ∗ f(n − 1)$ . Для нахождения $f(5)$ напрямую вызовем функцию.


# Базовые случаи: F(-1) = 2, F(0) = 3 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(- 1) * f(n - 1) + 2 * f(n - 1)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == -1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 3  # Возвращаем базовое значение
    elif n > 0:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(- 1) * f(n - 1) + 2 * f(n - 1)  # Возвращаем значение рекурсивного выражения

print(f(5))  # Выводим результат на экран

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

Нам даны $F(0)$ , $F (− 1)$ . Подставим их в формулу:

$F(1) = F (− 1) ⋅ F (0) + 2 ⋅ F (0) = 2 ⋅ 3 + 2 ⋅ 3 = 6 + 6 = 12$

$F(2) = F (− 1) ⋅ F (1) + 2 ⋅ F (1) = 2 ⋅ 12 + 2 ⋅ 12 = 24 + 24 = 48$

$F(3) = F (− 1) ⋅ F (2) + 2 ⋅ F (2) = 2 ⋅ 48 + 2 ⋅ 48 = 96 + 96 = 192$

$F(4) = F (− 1) ⋅ F (3) + 2 ⋅ F (3) = 2 ⋅ 192 + 2 ⋅ 192 = 384 + 384 = 768$

$F(5) = F (− 1) ⋅ F (4) + 2 ⋅ F (4) = 2 ⋅ 768 + 2 ⋅ 768 = 1536 + 1536 = 3072$

$3072$ и пишем в ответ.

Ответ: 3072

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

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

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

$F(− 1) = 4$

$F(0) = 1$

$F(n ) = F (− 1) ⋅ F(n − 1) + 2 ⋅ F (n − 1)$ . При $n > 0$ .

Определите значение $F (4).$

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = − 1$ возвращаем 4, при $n = 0$ возвращаем 1, при $n > 0$ вычисляем как $f(− 1) ∗ f(n − 1 ) + 2 ∗ f(n − 1)$ . Для нахождения $f(4)$ напрямую вызовем функцию.


# Базовые случаи: F(-1) = 4, F(0) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(- 1) * f(n - 1) + 2 * f(n - 1)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == -1:  # Базовый случай — возвращаем значение без рекурсии
        return 4  # Возвращаем базовое значение
    elif n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 0:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(- 1) * f(n - 1) + 2 * f(n - 1)  # Возвращаем значение рекурсивного выражения

print(f(4))  # Выводим результат на экран

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

Нам даны $F(0)$ , $F (− 1)$ . Подставим их в формулу:

$F(1) = F (− 1) ⋅ F (0) + 2 ⋅ F (0) = 4 ⋅ 1 + 2 ⋅ 1 = 4 + 2 = 6$

$F(2) = F (− 1) ⋅ F (1) + 2 ⋅ F (1) = 4 ⋅ 6 + 2 ⋅ 6 = 24 + 12 = 36$

$F(3) = F (− 1) ⋅ F (2) + 2 ⋅ F (2) = 4 ⋅ 36 + 2 ⋅ 36 = 144 + 72 = 216$

$F(4) = F (− 1) ⋅ F (3) + 2 ⋅ F (3) = 4 ⋅ 216 + 2 ⋅ 216 = 864 + 432 = 1296$

$1296$ и пишем в ответ.

Ответ: 1296

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

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

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

$F(1) = 1$

$n−1 F(n ) = (F (n − 1)) + F (n − 1)$ . При $n > 1$ .

Определите значение $F (4).$

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

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

Функция $f(n)$ определяется рекурсивно по 2 правилам: при $n = 1$ возвращаем 1, при $n > 1$ вычисляем как $f(n − 1) ∗ ∗(n − 1) + f(n − 1)$ . Для нахождения $f (4)$ напрямую вызовем функцию.


# Базовые случаи: F(1) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) ** (n - 1) + f(n - 1)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) ** (n - 1) + f(n - 1)  # Возвращаем значение рекурсивного выражения

print(f(4))  # Выводим результат на экран

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

Нам дано $F (1)$ . Подставим его значение в формулу:

$F(2) = (F (1))1 + F (1) = 1 + 1 = 2$ $F (3) = (F(2))2 + F (2 ) = 4 + 2 = 6$ $F(4) = (F (3))3 + F (3) = 216 + 6 = 222$

$222$ и пишем в ответ.

Ответ: 222

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

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

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

$F(0) = 1$

$F(1) = 2$

$F(n ) = F (n − 1) ⋅ n + n + F (n − 2)$ . При $n > 1$ .

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

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

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

Функция $f(n)$ определяется рекурсивно по 3 правилам: при $n = 0$ возвращаем 1, при $n = 1$ возвращаем 2, при $n > 1$ вычисляем как $f(n − 1) ∗ n + n + f (n − 2)$ . Для нахождения $f(5)$ напрямую вызовем функцию.


# Базовые случаи: F(0) = 1, F(1) = 2 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) * n + n + f(n - 2)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 2  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * n + n + f(n - 2)  # Возвращаем значение рекурсивного выражения

print(f(5))  # Выводим результат на экран

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

Нам даны $F(0)$ , $F (1)$ . Подставим их в формулу, чтобы получить ответ:

$F(2) = F (1) ⋅ 2 + 2 + F (0) = 4 + 2 + 1 = 7$

$F(3) = F (2) ⋅ 3 + 3 + F (1) = 21 + 3 + 2 = 26$

$F(4) = F (3) ⋅ 4 + 4 + F (2) = 26 ⋅ 4 + 4 + 7 = 115$

$F(5) = F (4) ⋅ 5 + 5 + F (3) = 575 + 5 + 26 = 606$

$606$ и будет ответом на вопрос задачи.

Ответ: 606

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

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

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

$F(− 1) = 0$

$F(0) = 1$

$F(1) = 1$

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

Определите значение $F (6).$

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

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

Функция $f(n)$ определяется рекурсивно по 4 правилам: при $n = − 1$ возвращаем 0, при $n = 0$ возвращаем 1, при $n = 1$ возвращаем 1, при $n > 1$ вычисляем как $f (n − 1) ∗ f(n − 2) + f(n − 3)$ . Для нахождения $f (6)$ напрямую вызовем функцию.


# Базовые случаи: F(-1) = 0, F(0) = 1, F(1) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) * f(n - 2) + f(n - 3)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == - 1:  # Базовый случай — возвращаем значение без рекурсии
        return 0  # Возвращаем базовое значение
    if n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    if n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    return f(n - 1) * f(n - 2) + f(n - 3)  # Возвращаем значение рекурсивного выражения
print(f(6))  # Выводим результат на экран

Решение 2

Нам даны $F(− 1),$ $F (0)$ и $F (1 )$ . Подставим их в формулу:

$F(2) = F (1) ⋅ F(0) + F (− 1) = 1$

$F(3) = F (2) ⋅ F(1) + F (0) = 2$

$F(4) = F (3) ⋅ F(2) + F (1) = 3$

$F(5) = F (4) ⋅ F(3) + F (2) = 7$

$F(6) = F (5) ⋅ F(4) + F (3) = 23$

$23$ и будет ответом на задание.

Ответ: 23

Интенсивы

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

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

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

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

$F (1) = 0$ , $F(2) = 1$ , $F(3) = 1$

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

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

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

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

Функция $f(n )$ определяется рекурсивно по 3 правилам: при $n = 1$ возвращаем 0, при $n < 4$ возвращаем 1, при $n > 4$ вычисляем как $f(n− 1)+ n ∗∗2+ f(n − 2)$ . Для нахождения $f(25)$ напрямую вызовем функцию.

# Базовые случаи: F(1) = 0, для n < 4 возвращается 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) + n ** 2 + f(n - 2)
def f(n):  # Определение функции, реализующей алгоритм из условия
    if n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 0  # Возвращаем базовое значение
    if n < 4:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    return f(n - 1) + n ** 2 + f(n - 2)  # Возвращаем значение рекурсивного выражения
print(f(25))  # Выводим результат на экран

Ответ: 1705479

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

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

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

$F (1) = 1$ , $F(2) = 1$ , $F (3) = 1$

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

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

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

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

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

Функция $f(n )$ определяется рекурсивно по 4 правилам: при $n = 1$ возвращаем 1, при $n = 2$ возвращаем 1, при $n = 3$ возвращаем 1, при $n > 3$ вычисляем как $f(n− 1)+ f (n − 3)+ f(n∕∕3)$ . Для нахождения $f(33)$ напрямую вызовем функцию.

# Базовые случаи: F(1) = 1, F(2) = 1, F(3) = 1 — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: f(n - 1) + f(n - 3) + f(n // 3)
def f(n):    # Определение функции, реализующей алгоритм из условия
    if n == 1:    # Базовый случай — возвращаем значение без рекурсии
         return 1  # Возвращаем базовое значение
    elif n == 2:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 3:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 3 and n % 2 == 0:    # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
         return f(n - 1) + f(n - 3) + f(n // 3)    # Возвращаем значение рекурсивного выражения
    elif n > 3 and n % 2 != 0:    # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
         return f(n - 2) + f(n - 1)    # Возвращаем значение рекурсивного выражения
print(f(33))  # Выводим результат на экран

Ответ: 1022292

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

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

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

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

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

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

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

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

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

Функция $f(n )$ определяется рекурсивно по 2 правилам: при $n < 4$ возвращаем 2 ** n, при $n > 4$ вычисляем как $2 ∗f(n− 1)+ f (n∕∕2)$ . Для нахождения $f(128)$ напрямую вызовем функцию.

# Базовые случаи: для n < 4 возвращается 2 ** n — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: 2 * f(n - 1) + f(n // 2)
def f (n):  # Определение функции, реализующей алгоритм из условия
    if n < 4:  # Базовый случай — возвращаем значение без рекурсии
        return 2 ** n  # Возвращаем базовое значение
    if n % 2 == 0:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return 2 * f(n - 1) + f(n // 2)  # Возвращаем значение рекурсивного выражения
    return f(n - 2) + 2 * n + 1 + f(n // 3)  # Возвращаем значение рекурсивного выражения

print(f(128))  # Выводим результат на экран

Ответ: 158450

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

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

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

$F (n) = 2∗ F(n− 2)+ F (n ∕∕2) + n$ , если $n > 2$ и кратно 5

$F (n) = 2∗ n∗n + F(n − 2)+ 1+ F(n∕∕3)$ , если $n > 2$ и некратно 5

Сколько четных цифр содержит результат выполнения вызова $F (100)$ ?

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

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

Определяем рекурсивную функцию $f(n)$ по заданным соотношениям. Если $n < 3$ , возвращаем $2⋅n ⋅n+ 2$ . Если $n > 2$ и $n$ делится на $5$ , вызываем функцию для $n− 2$ и $n÷ 2$ , умножаем первый результат на $2$ , прибавляем второй и прибавляем $n$ . Если $n > 2$ и $n$ не делится на $5$ , вычисляем $2⋅n ⋅n$ , прибавляем результат вызова $f(n− 2)$ , прибавляем $1$ и результат вызова $f(n ÷ 3)$ . После определения функции вызываем $f(100)$ , сохраняем результат в переменной $s$ , затем преобразуем $s$ в строку, проходим по каждой цифре, проверяем остаток от деления на $2$ и подсчитываем количество чётных цифр.

def f(n):
    # Базовый случай: если n меньше 3, возвращаем 2*n*n + 2
    if n < 3:
        return 2 * n * n + 2
    # Если n больше 2 и делится на 5, вычисляем 2*f(n-2) + f(n//2) + n
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n // 2) + n
    # Если n больше 2 и не делится на 5, вычисляем 2*n*n + f(n-2) + 1 + f(n//3)
    elif n > 2 and n % 5 != 0:
        return 2 * n * n + f(n - 2) + 1 + f(n // 3)

# Вызываем функцию f для n = 100 и сохраняем результат в переменной s
s = f(100)
# Преобразуем s в строку, проходим по каждой цифре, проверяем остаток от деления на 2 и подсчитываем количество чётных цифр
print(len([i for i in str(s) if int(i) % 2 == 0]))

Ответ: 5

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

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

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

$F (n) = 2∗ F(n− 1)+ F (n ∕∕2) + n$ , если $n > 5$ и кратно 3

$F (n) = 2∗ n∗n + F(n − 1)+ F(n∕∕2)$ , если $n > 5$ и некратно 3

Чему равна сумма четных цифр числа, полученного при выполнении вызова $F (99)$ ?

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

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

Определяем рекурсивную функцию $f(n)$ по заданным условиям. Если $n < 6$ , возвращаем $2⋅n+ 1$ . Если $n > 5$ и $n$ делится на $3$ , вызываем функцию для $n − 1$ и $n∕∕2$ , удваиваем первый результат, прибавляем второй и добавляем $n$ . Если $n > 5$ и $n$ не делится на $3$ , вычисляем $2⋅n⋅n$ , прибавляем результат вызова $f(n− 1)$ и результат вызова $f(n∕∕2)$ . После определения функции вызываем $f(99)$ и сохраняем результат в переменной $s$ . Затем проходим по каждой цифре числа $s$ , проверяем остаток от деления на $2$ и суммируем все чётные цифры в переменной $ans$ , после чего выводим $ans$ .

def f(n):
    # Базовый случай: если n меньше 6, возвращаем 2*n + 1
    if n < 6:
        return 2 * n + 1
    # Если n больше 5 и делится на 3, вычисляем 2*f(n-1) + f(n//2) + n
    elif n > 5 and n % 3 == 0:
        return 2 * f(n - 1) + f(n // 2) + n
    # Если n больше 5 и не делится на 3, вычисляем 2*n*n + f(n-1) + f(n//2)
    elif n > 5 and n % 3 != 0:
        return 2 * n * n + f(n - 1) + f(n // 2)

# Вызываем функцию f для n = 99 и сохраняем результат в переменной s
s = f(99)

# Инициализируем переменную для хранения суммы чётных цифр
ans = 0
# Проходим по каждой цифре числа s
while s > 0:
    # Если цифра чётная, прибавляем её к ans
    ans += (s % 10) * ((s % 10) % 2 == 0)
    # Убираем последнюю цифру из s
    s = s // 10

# Выводим сумму чётных цифр
print(ans)

Ответ: 26

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

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

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

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

$F (n) = n∗ n+ n ∗2$ , при $n > 15$

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

Определите количество натуральных значений $n$ из отрезка $[1;1000]$ , при которых значение $F (n )$ кратно 4.

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

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

Определяем рекурсивную функцию $f(n)$ по заданным условиям. Если $n > 15$ , возвращаем $n ⋅n +n ⋅2$ . Если $n ≤ 15$ , вызываем функцию для $n +2$ и $n +1$ , удваиваем второй результат, прибавляем первый и возвращаем сумму. После определения функции проходим по всем натуральным значениям $n$ из отрезка $[1;1000]$ , вызываем $f(n)$ для каждого $n$ и проверяем, делится ли результат на $4$ . Если результат делится на $4$ , увеличиваем счётчик $ans$ . После проверки всех $n$ выводим значение $ans$ .

def f(n):
    # Если n больше 15, возвращаем n*n + n*2
    if n > 15:
        return n * n + n * 2
    # Если n меньше или равно 15, вычисляем f(n+2) + 2*f(n+1)
    else:
        return f(n + 2) + 2 * f(n + 1)

# Инициализируем счётчик количества значений n, для которых f(n) кратно 4
ans = 0
# Проходим по всем натуральным n от 1 до 1000 включительно
for i in range(1, 1000 + 1):
    # Если значение функции f(i) кратно 4, увеличиваем счётчик
    if f(i) % 4 == 0:
        ans += 1

# Выводим количество таких значений
print(ans)

Ответ: 496

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

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

$F (n) = n∗ n∗ n$ , при $n > 32$

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

Определите количество натуральных значений $n$ из отрезка $[1;1000]$ , при которых значение $F(n)$ заканчивается на 3.

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

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

Определяем рекурсивную функцию $f(n)$ по заданным условиям. Если $n > 32$ , возвращаем $n⋅n ⋅n$ . Если $n ≤ 32$ , вызываем функцию для $n ⋅2$ и для $n+ 1$ , умножаем второй результат на $n$ , прибавляем первый и возвращаем сумму. После определения функции проходим по всем натуральным значениям $n$ из отрезка $[1;1000]$ , вызываем $f(n)$ для каждого $n$ и проверяем, оканчивается ли результат на $3$ , то есть проверяем $f(n)%10 == 3$ . Если последняя цифра равна $3$ , увеличиваем счётчик $ans$ . После проверки всех $n$ выводим значение $ans$ .

def f(n):
    # Если n больше 32, возвращаем n**3
    if n > 32:
        return n ** 3
    # Если n меньше или равно 32, вычисляем f(n*2) + f(n+1)*n
    else:
        return f(n * 2) + f(n + 1) * n

# Инициализируем счётчик количества значений n, для которых f(n) оканчивается на 3
ans = 0
# Проходим по всем натуральным n от 1 до 1000 включительно
for i in range(1, 1000 + 1):
    # Если последняя цифра f(i) равна 3, увеличиваем счётчик
    if f(i) % 10 == 3:
        ans += 1

# Выводим количество таких значений
print(ans)

Ответ: 97

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

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

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

$F (n) = 3∗ n+ n ∗n$ , если $n < 2$

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

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

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

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

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

Определяем рекурсивную функцию $f(n)$ по заданным условиям. Если $n < 2$ , сразу возвращаем значение $3 ⋅n + n⋅n$ . Если $n > 1$ и число чётное, вызываем функцию для $n − 2$ и для $n∕∕2$ , после чего складываем результаты и возвращаем сумму. Если $n > 1$ и число нечётное, вызываем функцию для $n− 2$ и для $n − 3$ , складываем результаты и возвращаем сумму. Таким образом, мы последовательно проверяем базовый случай и различаем чётные и нечётные значения $n$ , чтобы корректно применять соответствующие формулы. После определения функции вызываем $f(77)$ для получения ответа.

def f(n):
    # Базовый случай: если n < 2, считаем по формуле 3*n + n̂2
    if n < 2:
        return 3 * n + n ** 2

    # Если n > 1 и чётное: используем формулу f(n-2) + f(n//2)
    elif n > 1 and n % 2 == 0:
        return f(n - 2) + f(n // 2)

    # Если n > 1 и нечётное: используем формулу f(n-2) + f(n-3)
    elif n > 1 and n % 2 == 1:
        return f(n - 2) + f(n - 3)

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

Ответ: 125128

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

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

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

$F (n) = 3∗ F(n− 1)+ F (n ∕∕2) + n$ , если $n > 5$ и кратно 3

$F (n) = 5∗ n∗n + F(n − 1)+ F(n∕∕2)$ , если $n > 5$ и некратно 3

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

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

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

Определяем рекурсивную функцию $f(n)$ по заданным формулам. Для $n < 6$ сразу возвращаем значение $2⋅n + 1$ , так как это базовый случай, при котором вычисление не зависит от других значений функции. Если $n > 5$ и число кратно 3, мы вызываем $f(n− 1)$ и $f(n∕∕2)$ , затем умножаем $f(n − 1)$ на 3, прибавляем $f(n∕∕2)$ и добавляем $n$ . Если $n > 5$ и число некратно 3, мы вызываем $f(n− 1)$ и $f(n ∕∕2)$ , прибавляем $5 ⋅n⋅n$ к $f(n− 1)$ и $f(n ∕∕2)$ . После определения функции мы перебираем все $n$ от 1 до 1000 и проверяем остаток от деления $f (n)$ на 10, чтобы найти наименьшее $n$ , при котором значение функции заканчивается на 8. Как только такое $n$ найдено, выводим его и прерываем цикл, чтобы получить минимальное решение.

def f(n):
    # Базовый случай: если n < 6, считаем по формуле 2*n + 1
    if n < 6:
        return 2 * n + 1

    # Если n > 5 и кратно 3: используем формулу 3*f(n-1) + f(n//2) + n
    elif n > 5 and n % 3 == 0:
        return 3 * f(n - 1) + f(n // 2) + n

    # Если n > 5 и некратно 3: используем формулу 5*n*n + f(n-1) + f(n//2)
    elif n > 5 and n % 3 != 0:
        return 5 * n * n + f(n - 1) + f(n // 2)

# Перебираем все значения n от 1 до 1000
for i in range(1, 1000 + 1):
    # Проверяем, оканчивается ли f(i) на 8
    if f(i) % 10 == 8:
        print(i)  # Выводим наименьшее n
        break  # Прерываем цикл после нахождения первого подходящего n

Ответ: 7