Задание 16. Информатика. Фоксфорд 2023-3
Алгоритм вычисления значения функции \(F(n)\), где \(n\) — натуральное число, задан следующими соотношениями:
\(F(n) = 5\) при \(n=1;\)
\(F(n) = 2n + F(n-1),\) если \(n>1\).
Чему равно значение выражения \(F(2048) - F(1024)\)?
Решение:
При \(n>1\) функцию \(F(n)\) можно представить в виде $$ F(n) = 5 + 2 \cdot 2 + 2 \cdot 3 + \cdots + 2 \cdot n $$ Значит, $$ F(2048) - F(1024) = 2 \cdot 1025 + 2 \cdot 1026 + \cdots + 2 \cdot 2048 = 2 \sum_{i = 1025}^{2048} i $$
Python
2*sum(range(1025, 2049))
Ответ: \(3146752\)
Эту же задачу можно также решить "в лоб" с помощью динамического программирования.
Python
arr = [None, 5]
for i in range(2, 2049):
arr.append(2*i + arr[i-1])
print(arr[2048]-arr[1024])
Ответ: \(3146752\)