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

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

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

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

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

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

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

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

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

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

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

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

$F (n) = 5+ F (n∕2 − 4)$ , когда n > 3 и четное

$F (n) = n+ F (n + 2)$ , когда n > 3 и нечетное

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

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

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

def f(n):  # объявление функции
    # Дописываем условие насчёт натуральных чисел
    if n < 1 or n % 1 != 0:
        return 0
    if n <= 3:  # базовый случай
        return 3
    if n > 3 and n % 2 == 0:  # рекурсивный случай
        return 5 + f(n / 2 - 4)

    # Вместо n + f(n+2) вставляем 0,
    # нам нужно не допускать нечётные числа,
    # так как при них рекурсия продолжается бесконечно — каждый раз прибавляется значение,
    # не меняющее чётность и не приближающее к n < 3
    if n > 3 and n % 2 != 0:
        return 0


for n in range(1, 10000):
    if f(n) == 43:  # если результат подходит
        print(n)  # выводим ответ
        break  # завершаем цикл

Ответ: 2296

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

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

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

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

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

$F (n) = n$ , если $log (n) 2$ целое число

$F (n) = f(n− 1)+ 2,$ иначе

Чему равно $f(786432)$ ?

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

Проанализируем, как изменяются значения на определенных значениях функции с помощью программы.

# Функция для проверки, является ли число степенью двойки
def power_of_2(n):
    # Пока n натурально
    while n > 1:
        # Если n не кратно 2
        if n % 2 != 0:
            # Так как это не единица (условие while проверяет это),
            # то это иное нечётное натуральное число, значит точно не степень двойки
            return False
        # Если же чётно, то у этого числа есть возможность быть
        # степенью двойки
        n //= 2
    # Если мы не вышли из цикла ранее, то число не имеет иных простых делителей,
    # кроме двойки, значит это точно степнь двойки
    return True

# Функция из условия
def f(n):
    # Если число — степень двойки, то log будет целым
    if power_of_2(n):
        return n
    # Иначе рекурсивный случай
    else:
        return f(n - 1) + 2

Заметим, что функция от степеней двойки выводит само число, а для остальных получается значение $(число− [ближайш ая степень двойки]) ∗2+ [ближайш ая степень двой&#x0$ . И так до следующей степени двойки.

Заметим, что $219 < 786432 < 220$ . Посчитаем значение $f(786432)$ по формуле, которую определили:

print((786432  - 2 ** 19) * 2 + 2 ** 19)

Ответ: 1048576

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

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

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

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

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

Найдите наименьшее значение $n$ при котором $F (n ) > 700$ .

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

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

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


for n in range(1000):
    if F(n) > 700:  # если результат подходит
        print(n)  # выводим ответ
        break  # завершаем цикл

Получается ответ: $63.$

Ответ: 63

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

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

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

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

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

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

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

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

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

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

def f(n):
    # Базовый случай: если n <= 2, возвращаем 1
    if n <= 2:
        return 1
    # Если n > 2, используем формулу f(n-1)*n + f(n-5)*5
    if n > 2:
        return f(n - 1) * n + f(n - 5) * 5

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

Ответ: 2083605774875

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

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

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

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

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

Чему равно значение функции $F(7)$ ? В ответе запишите только натуральное число.

Примечание. Знак // – означает деление нацело.

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

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

def f(n):
    # Базовый случай: если n <= 3, возвращаем 1
    if n <= 3:
        return 1
    # Если n > 3, используем формулу f(n // 3) + f(n - 1) + 2
    if n > 3:
        return f(n // 3) + f(n - 1) + 2

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

Ответ: 13

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

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

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

$F (1) = 1$

$F (2) = 1$

$F (3) = 1$

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

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

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

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

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

def f(n):
    # Базовый случай: если n <= 3, возвращаем 1
    if n <= 3:
        return 1
    # Если n > 3, используем формулу f(n-1)*3 - f(n-3)
    if n > 3:
        return f(n - 1) * 3 - f(n - 3)

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

Ответ: 953

Курсы

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

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

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

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

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

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

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

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

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

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

def f(n):
    # Базовый случай: если n <= 5, возвращаем n
    if n <= 5:
        return n
    # Если n > 5, используем формулу (f(n-1) - f(n-4)) * n - 10
    if n > 5:
        return (f(n - 1) - f(n - 4)) * n - 10

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

Ответ: 96123346573029105521

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

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

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

$F (n) = 10$ при $n ≤ 3$

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

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

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

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

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

def f(n):
    # Базовый случай: если n <= 3, возвращаем 10
    if n <= 3:
        return 10
    # Если n > 3, используем формулу 5*f(n-1) - 4*f(n-2) + 3*f(n-3)
    if n > 3:
        return 5 * f(n - 1) - 4 * f(n - 2) + 3 * f(n - 3)

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

Ответ: 19539400

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

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

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

$F (n) = n− 5$ при $n ≥ 670$

$F (n) = 5⋅n + 7+ F(5⋅n + 7)$ при $n < 670$

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

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

В задаче представлен рекурсивный алгоритм: функция $F(n)$ вычисляется в зависимости от значения $n$ . Если $n ≥ 670$ , используется базовое выражение $F(n) = n− 5$ . Если $n < 670$ , применяется формула $F (n ) = 5⋅n + 7+ F(5 ⋅n+ 7)$ . Внутри функции создаём ветвление: $n ≥ 670$ и $n < 670$ . Для вычисления выражения $F (600) − F (300)$ рекурсивно считаем значения $F(600)$ и $F (300)$ и выполняем их вычитание.

def f(n):
    # Базовый случай: если n >= 670, возвращаем n - 5
    if n >= 670:
        return n - 5
    # Если n < 670, используем рекурсивную формулу 5*n + 7 + f(5*n + 7)
    else:
        return 5*n + 7 + f(5*n + 7)

# Вычисляем выражение F(600) - F(300)
print(f(600) - f(300))

Ответ: 3000

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

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

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

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

$F (n) = 6⋅F (n − 1)− F(n − 2) ⋅n$ , если n > 1

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

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

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

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

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

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

Ответ: 284

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

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

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

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

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

Чему равно значение функции F(12)? В ответе запишите только натуральное число.

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

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

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

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

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

Ответ: 6074

Интенсивы

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

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

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

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

$F (0) = 6$ ;

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

$F (n) = F(n∕∕2)$ , в остальных случаях.

В данной задаче $∕∕$ означает деление нацело.

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

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

В задаче дан рекурсивный алгоритм: функция $F (n)$ вызывает саму себя с аргументом $(n∕∕2)$ . Внутри функции создаём ветвление: $n = 0$ , $n > 0$ и чётное ( $n%2 == 0$ ), $n > 0$ и нечётное ( $n%2 ⁄= 0$ ). Для каждого случая возвращаем соответствующее значение в соответствии с условием: если $n = 0$ , возвращаем 6; если $n > 0$ и чётное, возвращаем $1 + F(n∕∕2)$ ; если $n > 0$ и нечётное, возвращаем $F(n∕∕2)$ . После определения функции перебираем все значения $n$ на отрезке $[1;10000]$ и подсчитываем количество $n$ , для которых $F (n ) = 9$ .

# Создаем функцию из условия
def f(n):
    # Базовый случай: если n == 0, возвращаем 6
    if n == 0:
        return 6
    # Если n > 0 и четное, используем формулу 1 + f(n//2)
    elif n > 0 and (n % 2) == 0:
        return 1 + f(n // 2)
    # Если n > 0 и нечётное, используем формулу f(n//2)
    else:
        return f(n // 2)

# Перебираем все возможные входные значения
c = 0
for i in range(1, 10000 + 1):
    t = f(i)
    # Если f(i) = 9, увеличиваем счетчик
    if t == 9:
        c += 1

# Выводим количество значений n, для которых F(n) = 9
print(c)

Ответ: 718

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

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

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

$F (n) = n$ , если $n > 1000$

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

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

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

В задаче дан рекурсивный алгоритм: функция $F(n)$ вызывает саму себя с аргументом $(n+ 1)$ . Внутри функции создаём ветвление: $n > 1000$ и $n ≤ 1000$ . Если $n > 1000$ , возвращаем значение $n$ , иначе для $n ≤ 1000$ возвращаем $7 ⋅n2 + 3+ F (n + 1)$ . После определения функции вычисляем разность $F (6) − F (12)$ , чтобы получить ответ задачи.

def F(n):
    # Если n > 1000, возвращаем n
    if n > 1000:
        return n
    # Если n <= 1000, используем формулу 7*n̂2 + 3 + F(n+1)
    if n <= 1000:
        return 7 * n ** 2 + 3 + F(n + 1)

# Вычисляем разность F(6) - F(12)
print(F(6) - F(12))

Ответ: 3175

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

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

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

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

$F (n) = F(n − 15) +n ∕∕3$ , если $15 < n ≤ 25$

$F (n) = F(n − 6)$ , если $n > 25$

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

Примечание. Запись // означает деление нацело.

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

В задаче дан рекурсивный алгоритм: функция $F(n)$ вызывает саму себя с разными аргументами в зависимости от величины $n$ . Внутри функции создаём ветвление: $n ≤ 15$ , $15 < n ≤ 25$ и $n > 25$ . Если $n ≤ 15$ , возвращаем $n$ . Если $15 < n ≤ 25$ , возвращаем $F (n− 15)+ n∕∕3$ . Если $n > 25$ , возвращаем $F (n− 6)$ . После определения функции вычисляем $F (20)$ , чтобы получить ответ задачи.

def F(n):
    # Базовый случай: если n <= 15, возвращаем n
    if n <= 15:
        return n
    # Если 15 < n <= 25, используем формулу F(n-15) + n//3
    if 15 < n <= 25:
        return F(n - 15) + n // 3
    # Если n > 25, используем формулу F(n-6)
    if n > 25:
        return F(n - 6)

# Вычисляем значение F(20)
print(F(20))

Ответ: 11

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

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

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

$F (n) = 5+ n + F(n+ 2)$ , если $n < 100$

$F (n) = n+ 2$ , если $n ≥ 100$

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

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

В задаче дан рекурсивный алгоритм: функция $F(n)$ вызывает саму себя с аргументом $n + 2$ , если $n < 100$ , и возвращает $n+ 2$ , если $n ≥ 100$ . Внутри функции создаём ветвление: $n ≥ 100$ и $n < 100$ . Если $n ≥ 100$ , возвращаем $n + 2$ . Если $n < 100$ , возвращаем $5+ n +F (n+ 2)$ . После определения функции вычисляем выражение $F (90) − F (101)$ для получения ответа.

def F(n):
    # Если n >= 100, возвращаем n + 2
    if n >= 100:
        return n + 2
    # Если n < 100, используем формулу 5 + n + F(n+2)
    if n < 100:
        return 5 + n + F(n + 2)

# Вычисляем выражение F(90) - F(101)
print(F(90) - F(101))

Ответ: 494

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

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

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

F(0) = 0;

F(n) = F(n - 1) + 3, если n > 0 и при этом n mod 3 = 2;

F(n) = F((n - n mod 3) / 3), если n > 0 и при этом n mod 3 < 2.

Укажите наименьшее возможное n, для которого F(n) = 6. Если таких значений нет, в ответе укажите -1.

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

В задаче представлен рекурсивный алгоритм: функция $F (n)$ вычисляется в зависимости от остатка от деления $n$ на 3.

Если $n = 0$ , функция возвращает большое число (чтобы исключить ноль, так как $n$ – натуральное).

Если $n > 0$ и $n%3 = 2$ , вычисляем $F(n) = F(n− 1)+ 3$ .

Если $n > 0$ и $n%3 < 2$ , вычисляем $F(n) = F((n− n%3 )∕3)$ .

Внутри функции создаём ветвление для трёх случаев: $n = 0$ , $n > 0$ и $n%3 = 2$ , $n > 0$ и $n%3 < 2$ . После определения функции перебираем значения $n$ от 0 до 999 и находим наименьшее $n$ , для которого $F (n ) = 6$ .

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

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

Ответ: -1

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

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

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

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

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

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

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

$F (n) = 3∗ F(n− 2)$ , если $n$ нечётно.

Чему равно значение функции $F(30)$ ? Для выполнения задания можно также написать программу или воспользоваться редактором электронных таблиц.

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

В задаче представлен рекурсивный алгоритм: функция $F (n)$ вычисляется в зависимости от чётности $n$ . Если $n = 1$ , возвращаем $1$ — это базовый случай. Если $n$ чётное, используем формулу $F (n ) = n+ F (n− 1)$ , то есть значение функции равно текущему $n$ плюс значение функции для предыдущего числа. Если $n$ нечётное, используем формулу $F (n ) = 3⋅F (n − 2)$ , то есть значение функции в три раза больше значения функции для числа на два меньше. Внутри функции создаём ветвление для трёх случаев: $n = 1$ , $n$ чётное, $n$ нечётное. После определения функции вычисляем $F (30)$ по описанному рекурсивному алгоритму.

def F(n):
    # Базовый случай: если n = 1, возвращаем 1
    if n == 1:
        return 1
    # Если n чётное, используем формулу n + F(n-1)
    if n % 2 == 0:
        return n + F(n - 1)
    # Если n нечётное, используем формулу 3 * F(n-2)
    if n % 2 != 0:
        return 3 * F(n - 2)

# Вычисляем значение функции F(30)
print(F(30))

Ответ: 4782999

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

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

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

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

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

Найдите количество положительных целых значений $n$ при котором $F (n) < 565$ .

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

В задаче представлен рекурсивный алгоритм: функция $F (n)$ вычисляется в зависимости от значения $n$ . Если $n ≤ 1$ , используется формула $F(n) = n + 2$ , что является базовым случаем. Если $n > 1$ , используется рекурсивная формула $F (n ) = F(n − 2)+ n+ 3$ , то есть значение функции равно значению функции для числа на два меньше плюс $n+ 3$ . Внутри функции создаём ветвление: $n ≤ 1$ и $n > 1$ . Для определения количества положительных целых значений $n$ , при которых $F (n ) < 565$ , перебираем значения $n$ и увеличиваем счётчик, если выполняется указанное неравенство.

def F(n):
    # Базовый случай: если n <= 1, возвращаем n + 2
    if n <= 1:
        return n + 2
    # Рекурсивный случай: если n > 1, используем формулу F(n-2) + n + 3
    else:
        return F(n - 2) + n + 3

# Инициализация счётчика положительных целых n, для которых F(n) < 565
count = 0
# Перебираем значения n от 1 до 999 (достаточно для условия задачи)
for n in range(1, 1000):
    # Проверяем условие F(n) < 565
    if F(n) < 565:
        count += 1

# Выводим количество положительных целых n, удовлетворяющих условию
print(count)

Ответ: 43

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

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

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

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

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

Найдите сумму положительных целых значений $n$ при которых $F (n) < 666$ .

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

В задаче представлен рекурсивный алгоритм: функция $F(n)$ вычисляется в зависимости от значения $n$ . Если $n ≤ 1$ , используется базовое выражение $F (n) = n+ 3$ . Если $n > 1$ , применяется рекурсивная формула $F (n ) = F(n − 3)+ n+ 2$ , то есть значение функции равно значению функции для числа на три меньше плюс $n+ 2$ . Внутри функции создаём ветвление: $n ≤ 1$ и $n > 1$ . Для нахождения суммы положительных целых значений $n$ , при которых $F (n ) < 666$ , перебираем значения $n$ и добавляем их к сумме, если выполняется указанное неравенство.

def F(n):
    # Базовый случай: если n <= 1, возвращаем n + 3
    if n <= 1:
        return n + 3
    # Рекурсивный случай: если n > 1, используем формулу F(n-3) + n + 2
    else:
        return F(n - 3) + n + 2

# Инициализация переменной для хранения суммы положительных целых n, для которых F(n) < 666
sum = 0
# Перебираем значения n от 1 до 999 (достаточно для условия задачи)
for n in range(1, 1000):
    # Проверяем условие F(n) < 666 и добавляем n к сумме
    if F(n) < 666:
        sum += n

# Выводим сумму положительных целых n, удовлетворяющих условию
print(sum)

Ответ: 1770

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

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

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

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

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

Определите значение выражения: $F (10)− F(5)$ .

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

В задаче представлен рекурсивный алгоритм: функция $F(n)$ вычисляется в зависимости от значения $n$ . Если $n ≤ 1$ , используется базовое выражение $F(n) = n$ . Если $n > 1$ , применяется рекурсивная формула $F (n ) = F(n − 1)+ F(n− 2)∗ n$ , то есть значение функции равно сумме $F (n − 1)$ и произведения $F(n− 2)$ на $n$ . Внутри функции создаём ветвление: $n ≤ 1$ и $n > 1$ . Для нахождения значения выражения $F (10) − F (5)$ вызываем функцию для $n = 10$ и $n = 5$ , а затем вычитаем полученные значения.

def F(n):
    # Базовый случай: если n <= 1, возвращаем n
    if n <= 1:
        return n
    # Рекурсивный случай: если n > 1, используем формулу F(n-1) + F(n-2) * n
    else:
        return F(n - 1) + F(n - 2) * n

# Вычисляем значение выражения F(10) - F(5)
print(F(10) - F(5))

Ответ: 12100