Задание 16

Пример 1

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n < 3;
F(n) = 2×(n − 1) + F(n − 1) + 2, если n > 2 и при этом n четное;
F(n) = 2×(n + 1) + F(n − 2) − 5, если n > 2 и при этом n нечетно.
Чему равно значение выражения F(32)?

Пример 2

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n > 1.
Чему равно значение выражения F(2025) − F(1000)?

Пример 3

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n < 3;
F(n) = F(n − 1) + F(n − 2), если n > 2 и при этом n нечетное;
F(n) = F(i), если n > 2 и при этом n четно.
Чему равно значение выражения F(24)?

Теория

Задача заключается в нахождении значения функции, или выражения, заданной рекуррентным соотношением. Если необходимо просто рассчитать значение функции F(n) при не очень большом значении n - то реализуем это соотношение с помощью функции и рекурсивно ее вызываем. Но проанализируйте исходное выражение - часто можно решить без программы - аналитически. Если возникает ошибка stack overflow, то используйте список.

Решение

Пример 1

Самый быстрый способ решения данной задачи - программа на языке Python. Используйте рекурсивный вызов функции. Ошибок не возникнет, т.к. 32 небольшое.

def F(n):
    if n < 3:
        return n
    else:
        if n % 2 == 0:
            return 2*(n-1)+F(n-1)+2
        else:
            return 2*(n+1)+F(n-2)-5
print(F(32))

Результат 530.

Пример 2

Программа на языке Python. Используйте рекурсивный вызов функции. При попытке выполнить рекурсию возникнет ОШИБКА (RecursionError: maximum recursion depth exceeded in comparison) - переполнение стека вызовов функций. См листинг ниже:

def F(n):
    if n == 1:
        return 1
    else:
        return n + F(n-1)
print(F(2025)-F(1000))

Используйте вспомогательный список (массив) - заполните его в цикле до 2025-го элемента согласно заданным соотношениям.

F = []
F.append(1)
F.append(1)
for i in range(2,2026):
    F.append(i+F[i-1])
print(F[2025]-F[1000])

Здесь первые два оператора F.append(1) помещают 1 в нулевой и первый элемент списка. Результат 1550825.

P.S. Алгоритм задан таким образом, что каждый элемент начиная с 2 - сумма всех предыдущих и самого элемента. Т.е. каждый элемент n - сумма арифметической прогрессии с шагом 1 от 1 до n. Для F(2025) = (1+2025)/2 * 2025 = 2051325, а F(1000) = (1+1000)/2 * 1000 = 500500. 2051325 - 500500 = 1550825 😀.

Пример 3

Самый быстрый способ решения данной задачи - программа на языке Python. Используйте рекурсивный вызов функции. Отличие от Примера 1 - внутри функции F для четных n используется суммирование с помощью цикла.

def F(n):
    if n < 3:
        return 1
    else:
        if n % 2 != 0:
            return F(n-1)+F(n-2)
        else:
            sum = 0
            for i in range(1,n):
                sum += F(i)
            return sum
print(F(24))

Результат 887040.

Ответ

Пример 1:  530 (Время не более 5 минут)

Пример 2:  1550825 (Время не более 5 минут)

Пример 3:  887040 (Время не более 5 минут)