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

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

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

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

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

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

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

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

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

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

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

$F (0) = 0;$

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

$F (n) = 1+ F (n − 1)$ , если $n$ нечётно.

Назовите минимальное значение $n$ , для которого $F (n) = 12$ .

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

Дана рекурсия $F(0) = 0$ ; если $n > 0$ и $n$ чётно, то $F(n) = F(n∕∕2)$ ; если $n$ нечётно, то $F(n) = 1+ F(n − 1)$ . Требуется найти минимальное $n$ , для которого $F (n ) = 12$ . Для решения динамикой создадим список для хранения значение функции, где каждому i-тому элементу соответсвует $f(i)$ . Последовательно заполним список и выведем значение, если $f(n ) = 12$ .

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

f = [0] * 4097  # f[n] будет хранить F(n)
for n in range(1, 4097):
    # База для n = 0
    if n == 0:
        f[n] = 0
    # Чётное n
    elif n > 0 and n % 2 == 0:
        f[n] = f[n//2]
    # Нечётное n
    else:
        f[n] = 1 + f[n-1]
    # Если находим n, при котором f(n) = 12
    if f[n] == 12:
        # Пишем значение
        print(n)
        break

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление. Далее пройдемся циклом $while$ с перемнной i, будм на каждой итерации проверять f(i), и если $f (i)! = 12$ , то прибавляем к i единицу и далее проверяем следующее число, пока $f(i)$ не станет равно $12$

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

def F(n):
    # База для n = 0
    if n == 0:
        return 0
    # Чётное n
    if n % 2 == 0 and n > 0:
        return F(n // 2)
    # Нечётное n
    if n % 2 != 0:
        return 1 + F(n - 1)
i = 0  # Начинаем проверять числа с 0
while F(i) != 12:  # Пока не нашли нужное число i
    i += 1  # Увеличиваем его на 1
print(i)

Ответ: 4095

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

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

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

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

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

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1 или n - 3). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 1, n = 2, n = 3 и n > 3. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 5.

# Задаём функию F(n)
# Аргумент n - натуральное число по условию
def f(n):
    # Базовый случай. Определяем значение для F(1)
    if n == 1:
        return 1
    # Базовый случай. Определяем значение для F(2)
    if n == 2:
        return 2
    # Базовый случай. Определяем значение для F(3)
    if n == 3:
        return 4
    # Рекурсивный случай. Вычисляем значение функции для n, если n > 3
    else:
        return 5 * f(n - 1) + 3 * f(n - 3)


# Выводим значение функции F(5)
print(f(5))

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

Данная в условии формула $F(n ) = 5 ⋅ F (n − 1) + 3 ⋅ F(n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ , нужно найти значение $F (n − 1)$ и $F (n − 3)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ и $F (n − 1 − 3)$ (аналогично для $F (n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из условия).

Нам даны значения функции для $n = 1, 2, 3$ , найдем значение функции $F(5)$ :

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

Значение $F (4 )$ нам неизвестно, найдем его:

$F(4) = 5 ⋅ F (3) + 3 ⋅ F (1) = 20 + 3 = 23$ ;

Подставим найденное значение в $F (5)$ :

$F(5) = 5 ⋅ 23 + 3 ⋅ 2 = 115 + 6 = 121$ .

Ответ: 121

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

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

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

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1 или n - 2). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 1, n = 2 и n > 2. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 6.

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


# Выводим значение функции F(6)
print(f(6))

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

Данная в условии формула $F(n ) = F (n − 1) + 3 ⋅ F(n − 2 )$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F (n − 1)$ и $F (n − 2)$ , а чтобы найти найти значение $F(n − 1)$ , нужно найти значение $F (n − 1 − 1)$ и $F (n − 2 − 1)$ (аналогично с поиском значения $F(n − 2)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из условия).

Найдем значение функции $F (6)$ :

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

$F(5) = F (4) + 3 ⋅ F (3)$ ;

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

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

$F(4) = F (3) + 3 ⋅ F (2) = 5 + 6 = 11$ ;

$F(5) = F (4) + 3 ⋅ F (3) = 11 + 15 = 26$ ;

$F(6) = F (5) + 3 ⋅ F (4) = 26 + 33 = 59$ .

Ответ: 59

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

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

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

$F(0) = 1$

$F(1) = 2$

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1 или n - 2). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 0, n = q и n > 1. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 6.

# Задаём функию F(n)
def f(n):
    # Базовый случай. Определяем значение для F(0)
    if n == 0:
        return 1
    # Базовый случай. Определяем значение для F(1)
    if n == 1:
        return 2
    # Рекурсивный случай. Вычисляем значение функции для n, если n > 1
    if n > 1:
        return f(n - 1) * f(n - 2) - f(n - 2)


# Выводим значение функции F(6)
print(f(6))

Ответ: 1

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

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

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

$F(0) = 1$

$F(1) = 2$

$F(2) = 3$

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1, n - 2 или n - 3). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 0, n = 1, n = 2 и n > 2. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 5.

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


# Выводим значение функции F(5)
print(f(5))

Получаем ответ: $− 9.$

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

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

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

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

$F(2) 3 F(5) = F (4) − F (3) = (− 2) − 1 = − 8 − 1 = − 9$

$− 9$ и пишем в ответ.

Ответ: -9

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

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

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

$F(0) = 1$

$F(1) = 3$

$F(2) = 3$

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

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

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

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

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


# Выводим значение функции F(4)
print(f(4))

Получаем ответ: $5187.$

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

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

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

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

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

Ответ: 5187

Курсы

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

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

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

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

$F(1) = 2$

$F(2) = 3$

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1, n - 2). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 1, n = 2 и n > 2. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 4.

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


# Выводим значение функции F(4)
print(f(4))

Получаем ответ: $16002.$

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

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

$F(1) 2 F(3) = 2 ⋅ F (2) + 2 = 2 ⋅ 3 + 2 = 18 + 2 = 20$

$F(4) = 2 ⋅ F (3)F(2) + 2 = 2 ⋅ 203 + 2 = 16000 + 2 = 16002$

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

Ответ: 16002

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

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

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

$F(− 1) = 1$

$F(0) = 1$

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1, n - 2). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = -1, n = 0 и n > 0. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 3.

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


# Выводим значение функции F(3)
print(f(3))

Получаем ответ: $185.$

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

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

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

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

$F(3) = F (2) ⋅ F(2) + F (2) + F (1) = 169 + 13 + 3 = 185$

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

Ответ: 185

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

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

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

$F(0) = 2$

$F(1) = 3$

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

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

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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 1, n - 2). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвления: n = 0, n = 1 и n > 1. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Затем, останется только запустить функцию f для n = 5.

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


# Выводим значение функции F(5)
print(f(5))

Получаем ответ: $5945.$

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

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

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

$F(3) = F (1) ⋅ F(2) + 3 = 3 ⋅ 8 + 3 = 24 + 3 = 27$

$F(4) = F (2) ⋅ F(3) + 4 = 8 ⋅ 27 + 4 = 220$

$F(5) = F (3) ⋅ F(4) + 5 = 27 ⋅ 220 + 5 = 5945$

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

Ответ: 5945

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

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

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

$F(1) = 2$

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

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

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

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

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

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

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

Получаем ответ: $141.$

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

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

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

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

$F(4) = 4 ⋅ 4 + F (3) = 16 + 15 = 31$

$F(5) = 5 ⋅ 5 + F (4) = 25 + 31 = 56$

$F(6) = 6 ⋅ 6 + F (5) = 36 + 56 = 92$

$F(7) = 7 ⋅ 7 + F (6) = 49 + 92 = 141$

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

Ответ: 141

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

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

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

$F(0) = 1$

$F(1) = 2$

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

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

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

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

В условии нам даны $F (0)$ , $F (1)$ , $F (2)$ . Используем их значения для решения задачи:

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

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

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

$F(5) = F (4) ⋅ 4 + F (3) = 108 + 8 = 116$

$F(6) = F (5) ⋅ 5 + F (4) = 116 ⋅ 5 + 27 = 607$

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

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

В задаче дан рекурсивный алгоритм: в базовых исходах F(0) = 1, F(1) = 2 — эти значения задают начальные случаи и останавливают рекурсию. Для остальных значений применяется формула, выражающая F(n) через предыдущие значения: f(n - 1) * (n - 1) + f(n - 2). При вычислении F(5) рекурсия разворачивается и сводится к базовым исходам, после подстановки которых получается итоговое числовое значение.


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

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

Получаем ответ: $607.$

Ответ: 607

Интенсивы

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

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

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

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

$F(0) = 1$

$F(1) = 2$

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

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

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

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

В задаче дан рекурсивный алгоритм: в базовых исходах F(0) = 1, F(1) = 2 — эти значения задают начальные случаи и останавливают рекурсию. Для остальных значений применяется формула, выражающая F(n) через предыдущие значения: (n + 1) * f(n - 1) + f(n - 2). При вычислении F(5) рекурсия разворачивается и сводится к базовым исходам, после подстановки которых получается итоговое числовое значение.


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

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

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

В условии нам даны $F (0)$ , $F (1)$ . Так давайте используем их для решения задачи:

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

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

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

$F(5) = 6 ⋅ F (4) + F (3) = 942 + 30 = 972$

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

Ответ: 972

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

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

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

$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(-1) = 0, F(0) = 1, F(1) = 1 — эти значения задают начальные случаи и останавливают рекурсию. Для остальных значений применяется формула, выражающая F(n) через предыдущие значения: 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  # Возвращаем базовое значение
    elif n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * f(n - 2) - f(n - 3)  # Возвращаем значение рекурсивного выражения

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

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

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

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

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

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

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

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

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

Ответ: 1

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

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

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

$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(-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  # Возвращаем базовое значение
    elif n == 0:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n == 1:  # Базовый случай — возвращаем значение без рекурсии
        return 1  # Возвращаем базовое значение
    elif n > 1:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return f(n - 1) * f(n - 2) - f(n - 3)  # Возвращаем значение рекурсивного выражения

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

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

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

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

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

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

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

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

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

Ответ: 1

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

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

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

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

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

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

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

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


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

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

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

Данная в условии формула $F (n) = 4 ⋅ F (n − 1) − 2 ⋅ F (n − 2) ⋅ F (n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F(n − 1)$ , $F (n − 2)$ и $F (n − 3)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ , $F (n − 2 − 1)$ и $F (n − 3 − 1)$ (аналогично с поиском значения $F (n − 2)$ , $F(n − 2 )$ и $F(n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции $F (6)$ :

$F(8) = 4 ⋅ F (7) − 2 ⋅ F (6) ⋅ F (5)$ ;

$F(7) = 4 ⋅ F (6) − 2 ⋅ F (5) ⋅ F (4)$ ;

$F(6) = 4 ⋅ F (5) − 2 ⋅ F (4) ⋅ F (3)$ ;

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

$F(4) = 4 ⋅ F (3) − 2 ⋅ F (2) ⋅ F (1) = 4 ⋅ 3 − 2 ⋅ 2 ⋅ 1 = 12 − 4 = 8$ ;

$F(5) = 4 ⋅ 8 − 2 ⋅ 3 ⋅ 2 = 32 − 12 = 20$ ;

$F(6) = 4 ⋅ 20 − 2 ⋅ 8 ⋅ 3 = 80 − 48 = 32$ .

Ответ: 32

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

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

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

$F(0) = 1$

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

Определите значение $∘2 ------ F(10),$ в ответе указать только положительное число.

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

Определяем рекурсивную функцию $f(n )$ по заданным соотношениям. При $n = 0$ сразу возвращаем $1$ , так как $F (0) = 1$ . Если $n > 0$ , вызываем функцию для $n − 1$ , добавляем к результату $n ⋅ (n + 1)$ и возвращаем полученное значение. После определения функции вызываем $f(10 )$ и вычисляем квадратный корень от результата для получения положительного числа.

def f(n):
    # Базовый случай: если n равно 0, возвращаем 1
    if n == 0:
        return 1
    # Рекурсивный случай: если n больше 0, вычисляем n*(n+1) и прибавляем значение функции от n-1
    if n > 0:
        return n * (n + 1) + f(n - 1)

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

Ответ: 21

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

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

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

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

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

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

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

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

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


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

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

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

Данная в условии формула $F(n ) = F (n − 1) ⋅ F (n − 2) − F (n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F(n − 1)$ , $F (n − 2)$ и $F (n − 3)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ , $F (n − 2 − 1)$ и $F (n − 3 − 1)$ (аналогично с поиском значения $F (n − 2)$ и $F (n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции $F (4)$ :

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

Нам известны значения $F (2 )$ , $F (1)$ и $F (0)$ (2, 1, 0), но неизвестно значение $F (3)$ . Найдем его:

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

Подставим найденные значения в $F (4)$ :

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

Ответ: 3

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

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

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

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

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

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

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


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

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

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

Данная в условии формула $F(n ) = F (n − 2) + 2 ⋅ F(n − 3 )$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F (n − 2)$ и $F (n − 3)$ , а чтобы найти найти значение $F(n − 2)$ , нужно найти значение $F (n − 2 − 2)$ и $F (n − 3 − 2)$ (аналогично с поиском значения $F(n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из условия).

Нам даны значения $F(0)$ , $F (1)$ и $F (2)$ . Найдем значение функции $F (7 )$ :

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

$F(5) = F (3) + 2 ⋅ F (2)$ ;

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

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

$F(5) = 2 + 2 ⋅ 3 = 2 + 6 = 8$ ;

$F(7) = 8 + 2 ⋅ 7 = 8 + 14 = 22$ .

Ответ: 22

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

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

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

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

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

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

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

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


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

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

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

Данная в условии формула $F(n ) = F (n − 2) ⋅ F (n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F (n − 2)$ и $F (n − 3)$ , а чтобы найти найти значение $F(n − 2)$ , нужно найти значение $F (n − 2 − 2)$ и $F (n − 2 − 3)$ (аналогично с поиском значения $F(n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из условия).

Нам даны значения $F(1)$ , $F (2)$ и $F (3)$ . Найдем значение функции $F (8 )$ .

$F(8) = F (6) ⋅ F(5)$ ;

$F(6) = F (4) ⋅ F(3)$ ;

$F(5) = F (3) ⋅ F(2)$ ;

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

$F(5) = 6 ⋅ 3 = 18$ ;

$F(6) = 3 ⋅ 6 = 18$ ;

$F(8) = 18 ⋅ 18 = 324$ .

Ответ: 324

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

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

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

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

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

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

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


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

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

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

Данная в условии формула $F(n ) = F (n − 1) ⋅ F (n − 3) + 2 ⋅ F (n − 2)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F(n − 1)$ , $F (n − 3)$ и $F (n − 2)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ , $F (n − 3 − 1)$ и $F (n − 2 − 1)$ (аналогично с поиском значения $F (n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из формулы из условия).