16.01 Одна функция - Каталог заданий по ЕГЭ - Информатика БУ в Школково

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

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

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

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

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

Вычислите минимальное $n$ , при котором сумма цифр $F(n)$ будет кратна $13$ , а результат выполнения функции $F (n )$ будет иметь в своем составе более двух цифр $7$ .

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

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

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

def f(n):
    # База: F(1)=1, F(2)=2, F(3)=3
    if n < 4:
        return n
    # Отдельная база для n = 4:
    if n == 4:
        return 3
    # Рекурсия:
    return f(n - 4) + f(n - 3) + n

# Поиск минимального n, удовлетворяющего условиям
for n in range(1, 1000):
    val = f(n)
    # Подсчёт суммы цифр и количества цифр "7"
    summa, count_7 = 0, 0
    while val > 0:
        # Суммируем цифры
        summa += val % 10
        # Если эта цифра равна 7, то выражение
        # прибавит 1 к count_7
        count_7 += val % 10 == 7
        val //= 10

    # Проверка условий: сумма кратна 13 и более двух семёрок
    if count_7 > 2 and summa % 13 == 0:
        print(n)
        break

Ответ: 77

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

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

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

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

$F (n) = n+ F (n ∕3)$ , при $n > 4$ и $n$ кратном 3

$F (n) = n3 − F (n − 1)+ n$ , при $n > 4$ и $n$ некратном 3

Вычислите минимальное $n$ , при котором у $n$ в 16 системе счисления последняя цифра равна F, а также при котором сумма цифр $F (n)$ будет кратна 21, а результат выполнения функции $f(n)$ будет иметь в своем составе более четырех цифр 2.

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F (n) = n$ при $n ∈ 1,2,3,4$ ; при $n > 4$ и $n%3 = 0$ : $F (n ) = n+ F (n∕∕3)$ ; при $n > 4$ и $n%3 ⁄= 0$ : $F (n) = n3 − F (n− 1)+ n$ . Перебираем $n ≥ 1$ и для каждого считаем $F (n )$ ; проверяем три условия: $n%16 = 15$ (в hex оканчивается на $F$ ), сумма цифр $F(n)$ кратна $21$ , а в десятичной записи $F(n)$ более четырёх цифр "2". Минимальное $n$ , удовлетворяющее всем трём проверкам, и есть ответ.

def f(n):
    # База
    if n in [1, 2, 3, 4]:
        return n
    # Ветка для кратных 3
    if n > 4 and n % 3 == 0:
        return n + f(n // 3)
    # Ветка для некратных 3
    if n > 4 and n % 3 != 0:
        return n ** 3 - f(n - 1) + n

# Вычисляет сумму цифр
def digit_sum(n):
    s, total = n, 0
    while s > 0:
        total += s % 10
        s //= 10
    return total

# Перебор n
for i in range(1, 1000000):
    val = f(i)
    # Если сумма цифр кратна 21, больше четырёх цифр "2" и оканчивается на "F"
    if digit_sum(val) % 21 == 0 and str(val).count("2") > 4 and i % 16 == 15:
        print(i)
        break

Ответ: 18399

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

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

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

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

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

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

Сколько существует значений n на отрезке [1, 1500], для которых сумма цифр значения функции F(n) является простым числом?

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

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

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

from functools import lru_cache

# Кэширование результатов для оптимизации
@lru_cache(None)
def f(n):
    # База рекурсии
    if n <= 1:
        return 1
    # При n > 1 и n кратно 3
    elif n > 1 and n % 3 == 0:
        return f(n - 1) + f(n - 2) + n
    # Иначе
    else:
        return f(n - 2) + 2

# Функция для вычисления суммы цифр
def summa(n):
    dig_sum = 0
    while n > 0:
        dig_sum += (n % 10)
        n //= 10
    return dig_sum

# Проверка на простоту
def is_prime(n):
    if n < 2:
        return False
    # Перебираем до корня
    for j in range(2, int(n ** 0.5) + 1):
        # Если хоть один делитель есть, то число простое
        if n % j == 0:
            return False
    return True

ans = 0
for i in range(1, 1500 + 1):
    # Если сумма цифр простая
    if is_prime(summa(f(i))):
                                                                                                     
                                                                                                     
        # То обновляем счётчик
        ans += 1
print(ans)

Ответ: 301

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

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

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

$F (0) = 0$

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

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

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

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

Если внимательно посмотреть на перебор до 1000 например, то можно заметить, что у подходящих чисел ровно три единицы в 2 системе счисления. Значит эта рекурсия подсчитывает количество единиц в 2-сс.

Также мы знаем, что единицы в 2-сс появляются так: 2 умножаем на какую-то степень n и получаем единичку.

Например число 7: $22 + 21 + 20 = 4+ 2 +1$ . И в 2-сс выглядит как $1112$ . Как раз три единицы.

Также, чтобы получить единицы на трех разных местах мы должны возводить двойки в разные степени и складывать эти числа (как мы уже выяснили на числе 7).

ans = 0
for i in range(31):
    for j in range(i + 1, 31):
        for k in range(j + 1, 31):
            # Строим число с единицами в позициях i, j, k
            s = 2 ** i + 2 ** j + 2 ** k
            # Проверяем попадание в диапазон
            if 1 <= s <= 10 ** 9:
                ans += 1
print(ans)

Также можно увидеть, что ответ равен $C3 = 4060 30$ .

Все потому что $30 2$ больше миллиарда, но если поставить 3 первые единицы на позициях в 2-сс и остальные нули, то получим число меньше миллиарда.

Ответ: 4060

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

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

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

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

$F (n) = 2⋅F (n − 2)+ F(n − 1) + 2,$ при $n ≥ 3$ и $n$ — четное

$F (n) = 2⋅F (n − 1)+ F(n − 2) − 2$ при $n ≥ 3$ и $n$ — нечетное

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F (n) = 2$ при $n < 3$ ; если $n ≥ 3$ и $n$ чётное, то $F (n ) = 2⋅F (n − 2)+ F(n − 1)+ 2$ ; иначе $F(n) = 2 ⋅F(n − 1) +F (n− 2)− 2$ . Вычисляем $F (20)$ вызовом функции.

def f(n):
    # Если n меньше 3
    if n < 3:
        return 2
    # Если n чётное
    if n % 2 == 0:
        return 2 * f(n - 2) + f(n - 1) + 2
    # Если n нечётное
    return 2 * f(n - 1) + f(n - 2) - 2

print(f(20))

Ответ: 1775590

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

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

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

$F (0) = 0;$

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

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

Сколько существует таких чисел $n$ , что $1 ≤ n ≤ 500$ и $F(n) = 8$ ?

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F(0) = 0$ ; если $n > 0$ и $n$ чётно, то $F(n) = F (n∕∕2)$ ; если $n$ нечётно, то $F(n) = 1 + F(n − 1$ ). Перебираем все $n$ из диапазона $[1,500]$ , вычисляем $F (n )$ и подсчитываем, сколько раз результат равен 8.

def f(n):
    # Базовый случай:
    if n == 0:
        return 0
    # Если число положительное и чётное
    if (n > 0) and (n % 2 == 0):
        return f(n // 2)
    # Если число нечётное
    if n % 2 != 0:
        return 1 + f(n - 1)

ans = 0
# Перебор всех чисел от 1 до 500
for n in range(1, 501):
    # Если значение функции равно 8, увеличиваем счётчик
    if f(n) == 8:
        ans += 1
print(ans)

Ответ: 5

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

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

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

$F (0) = 0;$

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

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

Сколько существует таких чисел $n$ , что $1 ≤ n ≤ 900$ и $F(n) = 9$ ?

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

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

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

def f(n):
    # Базовый случай при n = 0:
    if n == 0:
        return 0
    # Если число положительное и чётное
    if (n > 0) and (n % 2 == 0):
        return f(n // 2)
    # Если число нечётное
    if n % 2 != 0:
        return 1 + f(n - 1)

ans = 0
# Перебор всех n от 1 до 900
for n in range(1, 901):
    # Если F(n) равно 9, увеличиваем счётчик
    if f(n) == 9:
        ans += 1
print(ans)

Ответ: 3

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

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

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

$F (1) = 1$

$F (2) = 1$

$F (n) = F(n − 1) +F (n− 2), n > 2$

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

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

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

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

def f(n):
    # Базовый случай для n = 1, n = 2:
    if n == 1 or n == 2:
        return 1
    # Рекурсивный случай:
    return f(n - 1) + f(n - 2)

print(f(8))

Ответ: 21

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

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

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

$F (1) = 1$

$F (2) = 2$

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F(1) = 1,F(2) = 2$ , для $k > 2$ выполняется $F (k ) = F(k − 1) ⋅F (k− 2)⋅k$ . Необходимо вычислить $F(5)$ вызовом функции.

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

print(f(5))

Ответ: 1440

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

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

Существует алгоритм, позволяющий возводить число $a$ в степень $x$ не за $N$ операций, а за $log2(N )$ . Он называется бинарным алгоритмом возведения в степень.

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

$F (a,1) = a$

$F (a,x) = a⋅F(a,x − 1)$ , если $x$ нечетное

$F (a,x) = F(a,x∕∕2)⋅F(a,x∕∕2)$ , если $x$ четное

Чему равно значение выражения $(F(2,2)+ F(3,3)+ ...+ F(10000,10000))%10000$ ?

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление. Функция $F(a,x)$ реализует быстрое возведение в степень (бинарный алгоритм): $F (a,1) = a$ ; если $x$ нечётно, то $F(a,x) = a ⋅F(a,x− 1)$ ; если x чётно, то $F(a,x) = F (a,x∕2) ⋅F(a,x∕2)$ . Требуется вычислить сумму $F (i,i)$ на промежутке $[2;10000]$ : для каждого $i$ считаем $i i$ через рекурсивную функцию и накапливаем сумму, в конце берём остаток по модулю $10000$ .

def f(a, x):
    # База:
    if x == 1:
        return a
    # Нечётная степень: a ** x = a * (a ** (x-1))
    if x % 2 != 0:
        return a * f(a, x - 1)
    # Чётная степень: a ** x = (a ** (x/2))**2
    b = f(a, x // 2)
    return b * b

ans = 0
# Суммируем i ** i для i от 2 до 10000
for i in range(2, 10000 + 1):
    ans += f(i, i)

# Выводим сумму по модулю 10000
print(ans % 10000)

Ответ: 4499

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

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

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

$F (1) = 1,$

$F (n) = F(n − 1) +2 ⋅n− 1.$

В ответе запишите значение от $9 F (10 + 777)$ .

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

Ключевое замечание в этой задаче следующее: $f(x) = x ⋅x$ . Заметить это можно по-разному.

Первый способ: заметим что $2⋅x − 1$ это значение дискретной производной многочлена $x⋅x$ , а значит так как $f(1) = 1 = 1⋅1$ , функция $f(x)$ действительно для всех целых чисел в качестве результата возвращает $x ⋅x$ .

Второй способ: давайте выведем первые $10$ значений функции и заметим закономерность. После этого докажем по индукции своё предположение.

Ответ: 1000001554000603729

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

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

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

$F (x) = F(x+ 1)$ при таких x, которые не делятся нацело на $1012$

$F (x) = x∕1012$ при таких x, которые делятся нацело на $1012$

Вычислите $12 F (2⋅10 + 1000− 7)$

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

Заметим, что терминальными аргументами, то есть такими, что функции сразу же вернет ответ, являются числа делящиеся на $1012$ . Поэтому достаточно лишь найти ближайшее больше либо равное первоначального аргумента такое значение. Для числа $2∗ 1012 +1000 − 7$ таковым является $3∗ 1012$ , а ответ 3.

Более того можно заметить, что $12 12 f(x) = (x + 10 − 1)∕∕10$

Ответ: 3

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

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

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

$F (1) = 1$

$F (2) = 4$

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

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F(1) = 1$ , $F(2) = 4$ , а для $n > 2$ — $F (n ) = F(n − 1)⋅(n − 1)+ F(n − 2)⋅(n − 2)$ . Вычислим значение $F (5)$ вызовом функции.

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

print(f(5))

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

Последовательно находим:

$F (3) = F(2)∗2 + F(1)∗1 = 9$ ,

$F (4) = F(3)∗3 + F(2)∗2 = 35$ ,

$F (5) = F(4)∗4 + F(3)∗3 = 167$ .

Ответ: 167

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

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

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

$F (1) = 1$

$F (2) = 1$

$F (3) = 1$

$F (n) = F(n − 3) +F (n− 1)$ , при $n > 3$ , где $n$ – натуральное число.

Чему равно $F(12)$ ?

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

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

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

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

def f(n):
    # Базовые случаи для n = 1, n = 2 и n = 3:
    if n == 1 or n == 2 or n == 3:
        return 1
    else:
        # Рекурсивное вычисление:
        return f(n - 3) + f(n - 1)

print(f(12))

Решение «руками»

Последовательно находим:

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

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

$F (6) = F(3)+ F(5) = 4$ ,

$F (7) = F(4)+ F(6) = 6$ ,

$F (8) = F(5)+ F(7) = 9$ ,

$F (9) = F(6)+ F(8) = 13$ ,

$F (10) = F(7)+ F(9) = 19$ ,

$F (11) = F(8)+ F(10) = 28$ ,

$F (12) = F(9)+ F(11) = 41$ .

Ответ: 41

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

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

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

$F (1) = 1$

$F (2) = 1$

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

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F (1) = 1$ ; $F(2) = 1$ ; при $n > 2$ : $F (n ) = F(n − 1)∗n2 − F (n− 2)$ . Пропишем функцию по условию и найдем значение $f(6)$ вызовом функции.

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

print(f(6))

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

Последовательно находим:

$2 F (3) = F(2)∗3 − F (1) = 8$ ,

$F (4) = F(3)∗42 − F (2) = 127$ ,

$F (5) = F(4)∗52 − F (3) = 3167$ ,

$2 F (6) = F(5)∗6 − F (4) = 113885$ .

Ответ: 113885

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

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

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

$F (1) = 1$

$F (2) = 2$

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

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F (1) = 1$ ; $F (2) = 2$ ; $n > 2$ : $F (n ) = (F(n− 1)− F (n− 2))∗n − 15$ . Пропишем функцию по условию и найдем значение $f (7)$ вызовом функции.

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

print(f(7))

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

Последовательно находим:

$F (3) = (F (2) − F(1)) ∗n − 15 = − 12$ ,

$F (4) = (F (3) − F(2)) ∗n − 15 = − 71$ ,

$F (5) = (F (4) − F(3)) ∗n − 15 = − 310$ ,

$F (6) = (F (5) − F(4)) ∗n − 15 = − 1449$ ,

$F (7) = (F (6) − F(5)) ∗n − 15 = − 7988$

Ответ: -7988

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

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

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

$F (1) = 5$ ;

$F (2) = 5$ ;

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

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: $F (1) = 5$ ; $F(2) = 5$ ; при $n > 2$ : $F (n ) = 5∗ F(n− 1)− 4 ∗F (n − 2)$ . Пропишем функцию по условию и найдем значение $f (13)$ вызовом функции.

def f(n):
    # Базовые случаи для n = 1 и n = 2
    if n == 1:
        return 5
    if n == 2:
        return 5

    # Рекуррентный случай
    return 5 * f(n - 1) - 4 * f(n - 2)

print(f(13))

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

Последовательно находим:

$F (1) = 5$ ;

$F (2) = 5$ ;

$F (3) = 25− 20 = 5$ ;

$F (4) = 25− 20 = 5$ ;

$F (5) = 25− 20 = 5$ ;

$F (6) = 25− 20 = 5$ ;

$F (7) = 25− 20 = 5$ ;

$F (8) = 25− 20 = 5$ ;

$F (9) = 25− 20 = 5$ ;

$F (10) = 25 − 20 = 5$ ;

$F (11) = 25 − 20 = 5$ ;

$F (12) = 25 − 20 = 5$ ;

$F (13) = 25 − 20 = 5$ ;

Ответ: 5

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

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

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

$F (n,m ) = 2$ , при $n <= 2$ или $m <= 5$

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

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

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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью $def$ . Внутри функции используем условный оператор $if$ , чтобы задать ветвление: базовый случай: при $n ≤ 2$ или $m ≤ 5$ — $F (n,m) = 2$ ; рекурсивный случай (для $n > 2$ и $m > 5$ ): $F (n,m ) = F (n− 3,m) + m ⋅F(n,m − 2)+ n⋅F (n− 5,m − 5)$ . Нужно вычислить $F(11,16)$ . Реализуем рекурсивную функцию строго по определению и вызовем её для $(11,16)$ .

def f(n, m):
    # База: если n <= 2 или m <= 5
    if n <= 2 or m <= 5:
        return 2

    # Рекуррентный шаг по формуле из условия
    return f(n - 3, m) + f(n, m - 2) * m + f(n - 5, m - 5) * n

print(f(11, 16))

Ответ: 160494512

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

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

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

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

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

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

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

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

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

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

print(f(19))

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

Для динамического решения создадим список, где каждому i-тому элементу будет соответствовать $f(i)$ . Заполним список по правилам из условия и выведем ответ вызовом 19-го элемента.

# Массив для хранения значений F
f = [0] * (19 + 1)
# База для n = 1, n = 2 и n = 3
f[1] = 0
f[2] = 1
f[3] = 1
# Рекуррентно вычисляем
for i in range(4, 19 + 1):
    f[i] = f[i - 1] + i * i + f[i - 2]

print(f[19])

Ответ: 94599

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

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

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

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

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

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

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

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

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

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

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

def F(n):
    # База для n = 1, n = 2, n = 3:
    if n == 1 or n == 2 or n == 3:
        return 1

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

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

print(F(30))

Ответ: 248055