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

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

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

Затем, останется только запустить функцию f для n из отрезка [1; 300] и сосчитать количество таких n, при которых результат функции превышает , для этого воспользуемся циклом for.

# Аргумент n - целое неотрицательное число по условию
def f(n):
    if int(n) != n or n < 0:  # Проверка на недопустимое значение n
        # Возвращаем отрицательное и огромное по модулю число,
        # которое не повлияет на вычисление 10**5
        return -9999999999

    # Базовый случай: n < 3
    if n < 3:
        return 2 * n * n + 2

    # Рекурсивный случай 1: n > 2 и кратно 5
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n / 2) + n

    # Рекурсивный случай 2: n > 2 и не кратно 5
    elif n > 2 and n % 5 != 0:
        return n * n + f(n - 2) + 1 + f(n / 3)

# Переменная-счётчик для ответа
ans = 0

# Перебор значений n из отрезка [1; 300]
for i in range(1, 301):
    if f(i) > 10 ** 5:  # Проверка значения функции
        ans += 1
print(ans)

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

Для использования метода динамического программирования создадим массив f, где f[n] хранит значение F(n). Реализуем программу, которая будет заполнять массив последовательно от n = 1 до n = 300, для этого организуем перебор от 1 дл 300 с помощью цикла for. Внутри цикла для каждого n проверяем условия и вычисляем f[n] на основе уже вычисленных значений.

При ветвлении по условиям из задачи важно также учесть два момента:

1. n делится на 2 (или 3 в завсимости от ветки) без остатка, так как n / 2 (или n / 3) должно быть целым.

2. f[n-2], f[n//2] и f[n//3] уже вычислены (не равны 0), некоторые значения могут оказаться невычисленными, если для их расчёта не выполнились условия в предыдущих шагах (например, n не делилось на нужное число или требуемые рекурсивные вызовы тоже остались невычисленными).

В конце остается просто подсчитать, сколько значений в массиве превышают 100000.

# Создаем список значений функции F(n), где индекс соответствует n.
# Изначально заполняем нулями (неопределенные значения).
f = [0] * (300 + 1) # Индексы от 0 до 300

# Заполняем массив f для n от 1 до 300.
for n in range(1, 300 + 1):
    # Базовый случай: n < 3
    if n < 3:
        f[n] = 2 * n * n + 2

    # Случай 1: n > 2 и кратно 5
    if n > 2 and n % 5 == 0:
        # Проверяем, что n делится на 2 без остатка (так как n/2 должно быть целым),
        # и что f[n-2] и f[n//2] уже вычислены (не равны 0).
        if (n % 2 == 0) and (f[n - 2] != 0) and (f[n // 2] != 0):
            f[n] = 2 * f[n - 2] + f[n // 2] + n

    # Случай 2: n > 2 и не кратно 5
    if n > 2 and n % 5 != 0:
        # Проверяем, что n делится на 3 без остатка (так как n/3 должно быть целым),
        # и что f[n-2] и f[n//3] уже вычислены (не равны 0).
        if (n % 3 == 0) and (f[n - 2] != 0) and (f[n // 3] != 0):
            f[n] = n * n + f[n - 2] + 1 + f[n // 3]

# Счётчик для ответа
ans = 0
# Перебираем n для проверки итоговых значений функции
for n in range(1, 300 + 1):
    if f[n] > 10 ** 5:
        ans += 1

print(ans)

В задаче дан рекурсивный алгоритм вычисления функции , где для первых трёх значений аргумента заданы конкретные результаты, а для всех используется рекурсивная формула. Реализуем этот алгоритм на Python. Для этого создаём функцию , внутри которой сначала проверяем, относится ли к базовым случаям: при возвращаем , при или — возвращаем . Эти условия позволяют остановить рекурсию и сразу вернуть ответ для небольших значений аргумента. Если , используем формулу , где вычисляем рекурсивно значения для и , а также добавляем квадрат текущего аргумента . Таким образом, на каждом шаге функция делится на более простые подзадачи, пока не достигнет одного из базовых случаев, после чего происходит сворачивание рекурсии с суммированием результатов. После описания алгоритма выполняем вызов , чтобы получить требуемое значение.

def f(n):
    # Если n = 1, базовый случай: возвращаем 0
    if n == 1:
        return 0

    # Если n = 2 или n = 3, второй и третий базовые случаи: возвращаем 1
    elif n == 2 or n == 3:
        return 1

    # Если n > 3, используем рекурсивную формулу
    else:
        # Вычисляем f(n-1) и f(n-2) рекурсивно и прибавляем квадрат n
        return f(n - 1) + n ** 2 + f(n - 2)

# Запускаем алгоритм для n = 25 и выводим результат
print(f(25))

В задаче задан рекурсивный алгоритм вычисления функции , где для трёх первых значений аргумента результат равен , а для остальных случаев выбор формулы зависит от чётности . Реализуем этот алгоритм на Python, создав функцию . Сначала проверяем базовый случай: если входит в список , возвращаем . Если и число чётное, то используем формулу — то есть вычисляем значения для , и , делённого на с целочисленным результатом, а затем складываем их. Если и число нечётное, то используем формулу , что означает суммирование результатов рекурсивных вызовов для и . Рекурсия продолжается до тех пор, пока аргумент не достигнет одного из базовых значений , или , после чего начинает сворачиваться, возвращая суммарный результат. В завершение вызываем , чтобы вычислить требуемое значение.

def f(n):
    # Базовый случай: если n равно 1, 2 или 3, возвращаем 1
    if n in [1, 2, 3]:
        return 1

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: базовый случай ; для чётных возвращаем ; для нечётных . Затем вызываем и печатаем результат.

def f(n):
    # Базовый случай: n < 4
    if n < 4:
        return 2 ** n

    # Случай: n > 3 и чётное
    elif n > 3 and n % 2 == 0:
        return 2 * f(n - 1) + f(n // 2)

    # Случай: n > 3 и нечётное
    elif n > 2 and n % 2 != 0:
        return f(n - 2) + 2 * n + 1 + f(n // 3)

print(f(128))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при сразу возвращаем значение по базовой формуле. Если и число чётное, вызываем функцию для и и складываем результаты. Если и число нечётное, вызываем функцию для и и также складываем результаты. Вызываем для получения ответа.

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)

print(f(77))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Если , возвращаем результат . Если , вызываем . Запускаем функцию с аргументом 1 и выводим результат.

def F(n):
    # Если n > 15, возвращаем n - 7
    if n > 15:
        return n - 7

    # Если n <= 15, рекурсивно вызываем F(n+6) и считаем по формуле
    if n <= 15:
        return 2 * F(n + 6) + n - 4

print(F(1))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Если , то . Если , то . Запускаем функцию для и выводим результат.

def f(n):
    # Базовый случай: если n < 5, возвращаем n
    if n < 5:
        return n

    # Рекурсивный случай: применяем формулу для n >= 5
    return 5 * f(n - 1) + 2 * f(n - 2)

print(f(10))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Если , то . Если , то . Запустим вычисление для и выведем результат.

def f(n):
    # Базовый случай: n < 3
    if n < 3:
        return 3 * n
    # Рекурсивный случай: n >= 3
    else:
        return f(n - 2) + 5 * f(n - 3)

print(f(15))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Если , то . Если , то . Вычислим результат для .

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

print(F(5))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление:

1) Базовый случай: .

2) Если и чётное, то .

3) Если и нечётное, то .

Необходимо вычислить , начиная с и рекурсивно спускаясь до базового случая, применяя соответствующее правило для чётных и нечётных .

def F(n):
    # Базовый случай: при n = 1
    if n == 1:
        return 1
    # Чётное n > 1: умножаем n на значение функции от (n - 1)
    if n > 1 and n % 2 == 0:
        return n * F(n - 1)
    # Нечётное n > 1: складываем n и значение функции от (n - 2)
    if n > 1 and n % 2 == 1:
        return n + F(n - 2)

print(F(90))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление:

1)

2) , если и чётное

3) , если нечётное

Необходимо найти минимальное , для которого . Для этого перебираем значения от 0 вверх, вычисляем по определению, и при первом совпадении с 12 выводим найденное и останавливаем перебор.

def F(n):
    # База: F(0) = 0
    if n == 0:
        return 0
    # Чётный n > 0: F(n) = F(n // 2)
    if n > 0 and n % 2 == 0:
        return F(n // 2)
    # Нечётный n: F(n) = 1 + F(n - 1)
    if n % 2 == 1:
        return 1 + F(n - 1)

# Перебор для поиска минимального n, где F(n) == 12
for i in range(5000):
    if F(i) == 12:
        # Выводим минимальное найденное n и останавливаемся
        print(i)
        break

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: , где берётся целочисленное деление. Перебираем от 1 до 999 и ищем первое , для которого .

def f(n):
    # База: F(0) = 1
    if n == 0:
        return 1
    # Рекурсивная формула для n > 0:
    return f(0) + f((n - 1) // 3) + f((n - (n - 1) // 3 - 1))

# Ищем минимальное n с F(n) == 1001
# Можно брать диапозон и больше, т.к. делаем выход при нахождении
for n in range(1, 1000):
    if f(n) == 1001:
        print(n)   # Выводим значение и выходим
        break

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Далее требуется найти сумму чётных n, для которых значение попадает в заданный диапазон: . Поэтому перебираем только чётные n из отрезка с шагом 2, для каждого считаем F(n) по правилам и, если условие диапазона выполнено, прибавляем n к ответу.

def F(n):
    # База рекурсии
    if n == 0:
        return 0

    # Ветка 1: кратно 3, но НЕ кратно 2 и 5
    if n % 3 == 0 and n % 2 != 0 and n % 5 != 0:
        return 3 * F(n // 3)

    # Ветка 2: НЕ кратно 3 и 5, но кратно 2
    if n % 3 != 0 and n % 5 != 0 and n % 2 == 0:
        return 2 * F(n // 2)

    # Ветка 3: кратно 5, но НЕ кратно 3 и 2
    if n % 5 == 0 and n % 3 != 0 and n % 2 != 0:
        return 5 * F(n // 5)

    # Иначе формула без рекурсии
    return 2 * n

# Сумма чётных n, для которых 1000 <= F(n) <= 3000
ans = 0
# Перебираем только чётные n и проверяем диапазон значения
for i in range(0, 10000, 2):
    if 1000 <= F(i) <= 3000:
        # Накапливаем n в ответе
        ans += i

print(ans)

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при используем формулу ; при нечётных — формулу ; при чётных — . Для каждого из диапазона вычисляем и проверяем, содержит ли десятичная запись результата как минимум две цифры «0» (в любых позициях). Подсчитываем количество таких .

def f(n):
    # Ветка 1: n > 30
    if n > 30:
        return n * n + 3 * n + 5

    # Ветка 2: n <= 30 и n нечётное
    if n % 2 != 0:
        return 2 * f(n + 1) + f(n + 4)

    # Ветка 3: n <= 30 и n чётное
    return f(n + 2) + 3 * f(n + 5)

# Счётчик подходящих n
c = 0
for i in range(1, 1001):
    # Преобразуем значение f(i) в строку
    # и считаем количество нулей
    if str(f(i)).count("0") >= 2:
        c += 1

print(c)

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при возвращаем 1; при считаем ; во всех остальных случаях (то есть ): . Реализуем рекурсивно, а чтобы стек не переполнился из-за длинной цепочки вызовов, увеличим лимит глубины рекурсии через . Затем вычислим вызовом функции.

import sys
# Увеличиваем допустимую глубину рекурсии
sys.setrecursionlimit(1500)

def F(n):
    # База: если n < -1000
    if n < -1000:
        return 1

    # Ветка: если n > 1
    if n > 1:
        return -F(n - 1) - F(n - 3)

    # Иначе (для -1000 <= n <= 1)
    return -F(n - 1)

print(F(14))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при возвращаем ; при вычисляем по формуле . Реализуем рекурсивно ровно по определению и вычислим прямым вызовом.

def F(n):
    # База: если n < 3, возвращаем n
    if n < 3:
        return n
    # Рекурсивная формула для n > 2
    if n > 2:
        return F(n - 1) * F(n - 3) + 2 * F(n - 2)

print(F(6))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: ; для чётных используем ; для нечётных : . Реализуем рекурсивно строго по определению и вычислим прямым вызовом функции.

def f(n):
    # Базовый случай: F(1) = 1
    if n == 1:
        return 1

    # Ветка для чётных n > 1: F(n) = 2*n * F(n-1)
    if n % 2 == 0 and n > 1:
        return 2 * n * f(n - 1)

    # Ветка для нечётных n > 1: F(n) = n + F(n-2)
    if n > 1 and n % 2 != 0:
        return n + f(n - 2)

print(f(50))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: , , , рекуррентная формула для : . Реализуем рекурсивно по определению и вычислим .

def f(n):
    # База 1: F(1) = 0
    if n == 1:
        return 0
    # База 2: F(2) = 1, F(3) = 1
    if n in [2, 3]:
        return 1
    else:
        # Рекуррентная формула: F(n) = F(n-1) + F(n-2)
        return f(n - 1) + f(n - 2)

print(f(11))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: ; для используем . Реализуем рекурсивно по определению и вычислим вызовом функции.

def f(n):
    # Базовый случай: F(1) = 1
    if n == 1:
        return 1
    # Рекуррентная формула: F(n) = F(n-1) + 2*n
    return f(n - 1) + 2 * n

print(f(33))

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при — ; при и чётном — ; при и нечётном — . Перебираем от до , считаем по определению и ищем первое , для которого сумма цифр равна .

def f(n):
    # База: n < 6
    if n < 6:
        return n
    # Чётный n > 5
    if n % 2 == 0:
        return n + f(n // 2) * 2
    # Нечётный n > 5
    return f(n - 2) + f(n - 1)

# Поиск минимального n с суммой цифр F(n) равной 22
for i in range(1, 1001):
    if sum(map(int, str(f(i)))) == 22:
        print(i)
        break