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

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

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

def f(n):
    # База n < 2:
    if n < 2:
        return 3 * n + n * n

    # Чётный n > 1:
    if n % 2 == 0:
        return f(n - 2) + f(n // 2)

    # Нечётный n > 1:
    return f(n - 2) + f(n - 3)

print(f(29))

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

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

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

print(F(6) + F(7))

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

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

def f(n):
    # Базовый случай при n = 1:
    if n == 1:
        return 1
    # Рекурсия: F(n) = F(n-1) * n
    return f(n - 1) * n

print(f(7))

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

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

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

print(f(5))

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

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

def f(n):
    # Базовый случай 1: если n = 1, возвращаем 0
    if n == 1:
        return 0
    # Базовый случай 2: если n = 2, возвращаем 1
    if n == 2:
        return 1
    # Рекурсивный случай: F(n) = [F(n - 1)]² + [F(n - 2)]²
    return f(n - 1) ** 2 + f(n - 2) ** 2

print(f(7))

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

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

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

print(f(15))

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

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

def F(n):
    # Базовый случай: если n = 1, 2 или 3, возвращаем 1
    if n == 1 or n == 2 or n == 3:
        return 1
    # Рекурсивный случай: если n > 3 и n чётное
    if n > 3 and n % 2 == 0:
        return F(n - 1) + F(n - 3) + F(n // 3)
    # Рекурсивный случай: если n > 3 и n нечётное
    if n > 3 and n % 2 != 0:
        return F(n - 2) + F(n - 1)

print(F(30))

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

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

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

    # Случай для чётных n > 3:
    if n > 3 and n % 2 == 0:
        return 2 * f(n - 1) + f(n // 2)

    # Случай для нечётных n > 3:
    if n > 3 and n % 2 != 0:
        return f(n - 2) + 1 ** n + f(n // 5)

print(f(241))

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

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

def f(n):
    # База при n < 3:
    if n < 3:
        return 2 * (n - 1) + 3 * n
    # Случай: n > 2 и кратно 5
    if n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n // 2) - 2 ** n
    # Случай: n > 2 и не кратно 5
    if n > 2 and n % 5 != 0:
        return 2 ** n + f(n - 2) - 3 * n + f(n // 3)

Далее найдём количество чётных цифр в . Первый способ предлагает перевести значение в строку и вызвать функцию по строке для каждой из чётных цифр.

s = str(f(514))
print(s.count("0") + s.count("2") + s.count("4") + s.count("6") + s.count("8"))

Вторым способом мы перводим значение в строку и проходимся циклом for по строке, и если цифра кратна двойке, то обновляем счётчик.

s = str(f(514))
counter = 0
for i in s:
    if int(i) % 2 == 0:
        counter += 1
print(counter)

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

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

def f(n):
    # База для n < 6:
    if n < 6:
        return 2 * n + 1
    # Ветвь 1: n > 5 и кратно 3
    if n > 5 and n % 3 == 0:
        return 2 * f(n - 1) + f(n // 2) + n
    # Ветвь 2: n > 5 и не кратно 3
    if n > 5 and n % 3 != 0:
        return 2 * n * n + f(n - 1) + f(n // 2)

После вычисления нужно найти сумму чётных цифр результата. Для этого можно:

(1) преобразовать число в строку и просуммировать цифры из множества

s = str(f(85))

# Суммируем только чётные цифры (0,2,4,6,8)
sum_even = 0
for ch in s:
    d = int(ch)
    if d % 2 == 0:
        sum_even += d

print(sum_even)

(2) сделать арифметический разбор по разрядам, добавляя к сумме каждую чётную цифру.

ans = 0
res = f(85)
while res > 0:
    # Берём последнюю цифру
    digit = res % 10
    # Если цифра чётная, добавляем в сумму
    if digit % 2 == 0:
        ans += digit
    # Отбрасываем последнюю цифру
    res //= 10

print(ans)

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

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

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)
    if n <= 15:
        return F(n + 2) + 2 * F(n + 1)

sum = 0
# Перебираем все n от 1 до 1000
for i in range(1, 1000 + 1):
    # Если F(i) делится на 5 без остатка, увеличиваем счётчик
    if F(i) % 5 == 0:
        sum += 1

print(sum)

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

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

from functools import lru_cache
import sys

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

@lru_cache(None)
def f(n):
    # Ветка: n > 10 — используем явную формулу
    if n > 10:
        return 2 ** n + 3
    # Иначе: n <= 10 — рекуррентная формула
    else:
        return f(n + 2) + 2 * f(n + 1)

# Считаем, для скольких n из [-1000; 1000] значение F(n) кратно 3
ans = 0
for i in range(-1000, 1001):
    if f(i) % 3 == 0:
        ans += 1

print(ans)

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

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

def f(n):
    # Ветка для n > 32:
    if n > 32:
        return n ** 3
    # Ветка для n <= 32:
    else:
        return f(n * 2) + (n // 3) * n

# Счётчик подходящих n
ans = 0

# Перебираем все n от 1 до 1000 включительно
for i in range(1, 1000 + 1):
    # Проверяем, что последняя цифра F(i) равна 3
    if f(i) % 10 == 3:
        ans += 1

print(ans)

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

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

def f(n):
    if n < 32:
        # Для n < 32:
        return n ** 2 + 15
    else:
        # Для n >= 32:
        return f(n // 2) + 15 + f(n - 1)

# Cчётчик подходящих n
ans = 0
# Перебор всех n от 1 до 100 включительно
for i in range(1, 100 + 1):
    # Проверяем, что последняя цифра в hex-формате равна ’F’ (т.е. 15)
    if f(i) % 16 == 15:
        ans += 1

print(ans)

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

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

def f(n):
    # База для n < 3:
    if n < 3:
        return 2 * n + 10
    # Ветка n кратно 5 и n > 2:
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n // 5) + n
    # Иначе: n > 2 и n не кратно 5
    else:
        return n + f(n - 2) + 1 + f(n // 3)

# Счётчик подходящих n
ans = 0
# Перебираем n в [1; 300]
for i in range(1, 300 + 1):
    # Проверяем условие F(n) > 10 ** 7
    if f(i) > 10 ** 7:
        ans += 1
print(ans)

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

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

def f(n):
    # База для n < 2:
    if n < 2:
        return 1
    # Чётный случай:
    if n >= 2 and n % 2 == 0:
        return f(n // 2) + 1
    # Нечётный случай:
    if n > 2 and n % 2 != 0:
        return f(n - 3) + 3

# Ищем минимальное n, для которого f(n) == 31
for i in range(1, 10000000):
    if f(i) == 31:
        # Нашли первое подходящее n и остановка
        print(i)
        break

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

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

import math

def f(n):
    # Случай 1: n < 12
    if n < 12:
        return n + int(math.tan(n))
    # Случай 2: n >= 12 и кратно 6
    if n >= 12 and n % 6 == 0:
        return f(n // 2) + 1
    # Случай 3: n > 12 и не кратно 6
    if n > 12 and n % 6 != 0:
        return f(n - 3) + 3


# Ищем минимальное n, для которого F(n) = 17
for i in range(1, 10_000_000):
    if f(i) == 17:
        print(i)
        break

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

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

def F(n):
    # Базовый случай для n < 4
    if n < 4:
        return n
    # Если n делится на 3
    if n % 3 == 0:
        return n + F(n - 1) * 2
    # Если остаток 1
    if n % 3 == 1:
        return F(n // 2) + F(n - 2)
    # Если остаток 2
    if n % 3 == 2:
        return F(n - 1) + n ** 2

print(F(55))

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

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

def f(n):
    # Если n > 25, используем базовую формулу
    if n > 25:
        return 2 * n * n * n + n * n
    # Иначе считаем рекурсивно
    return f(n + 1) + 5 * f(n + 3)

s = f(2)
# Считаем сумму цифр числа
summa = 0
while s > 0:
    summa += s % 10
    s //= 10
print(summa)

# Иначе можно через map
print(sum(map(int, str(f(2)))))

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

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

def f(n):
    # База для n < 12:
    if n < 12:
        return n
    # Чётный n:
    if n > 11 and n % 2 == 0:
        return f(n // 2) * 2 - f(n - 1)
    # Нечётный n:
    if n > 11 and n % 2 == 1:
        return -f(n - 1)

# Ищем минимальное n с суммой цифр равной 10
for i in range(1, 1000 + 1):
    s = abs(f(i))
    summa = 0
    while s > 0:
        # Прибавляем последнюю цифру
        summa += s % 10
        # "Убираем" ее из числа
        s //= 10
    # Если нашлось, то выводим и останавливаем
    if summa == 10:
        print(i)
        break