Помогите решить задачу на питоне! Срочно!

Question

Помогите решить задачу на питоне! Срочно!

mr alastor Ученик (52), на голосовании 1 месяц назад

Задача 5. Кэширование для ускорения вычислений
Контекст
Вы разрабатываете программу для оптимизации вычислений чисел Фибоначчи. Числа Фибоначчи вычисляются рекурсивной функцией, каждое число равно сумме двух предыдущих чисел. Однако вы заметили, что при больших значениях чисел Фибоначчи вычисления занимают значительное время, так как многие значения вычисляются повторно. Вам поручено создать декоратор, который кэширует результаты вызова функции и позволяет избежать повторных вычислений для одних и тех же аргументов.

Задача
Создайте декоратор, который кэширует (сохраняет для дальнейшего использования) результаты вызова функции и, при повторном вызове с теми же аргументами, возвращает сохранённый результат.

Примените его к рекурсивной функции вычисления чисел Фибоначчи.

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

Советы
Для хранения результатов удобно использовать словарь, так как поиск элементов внутри словаря будет иметь сложность, равную в среднем O(1).
При этом не стоит хранить все вычисления в одном словаре, созданном снаружи функций (в глобальной области видимости). Лучше создавать отдельные словари для каждой декорируемой функции.

Вот что мне сказали сделать ещё дополнительно к задаче:

Answer 1

Для решения задачи кэширования результатов функции вычисления чисел Фибоначчи с использованием декоратора, давайте создадим такой декоратор и применим его к функции. В декораторе мы будем использовать словарь для хранения результатов вызовов функции с определенными аргументами.

Вот пример решения задачи:

```python
import functools
from typing import Callable, Any

def cache(func: Callable) -> Callable:
"""Декоратор для кэширования результатов вызова функции."""
cache_dict = {}

@functools.wraps(func)
def wrapper(*args, **kwargs) -> Any:
key = (args, tuple(kwargs.items()))
if key in cache_dict:
return cache_dict[key]
result = func(*args, **kwargs)
cache_dict[key] = result
return result

return wrapper

@cache
def fibonacci(n: int) -> int:
"""Рекурсивная функция для вычисления чисел Фибоначчи."""
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)

# Пример использования:
print(fibonacci(10)) # Должно напечатать 55
print(fibonacci(20)) # Должно напечатать 6765
```

В этом решении:

1. Мы создали декоратор `cache`, который сохраняет результаты вызовов функции в словарь `cache_dict`. Ключами в этом словаре являются аргументы вызова функции.
2. Декоратор оборачивает исходную функцию и проверяет, если результат для данных аргументов уже есть в кэше, то он возвращает его. В противном случае, выполняется расчет и результат сохраняется в кэше.
3. Применили декоратор к функции `fibonacci`, которая рекурсивно вычисляет числа Фибоначчи.

Этот подход значительно ускоряет вычисления для больших значений `n`, так как повторные вызовы с теми же аргументами будут возвращать уже вычисленный результат из кэша.