Форум » Системы счисления » (№ 5268) (Е. Джобс) » Ответить
(№ 5268) (Е. Джобс)
Ar3turrr: Не понимаю, что делаю не так. Ответ получается 61982. [pre2]def F(n): S = 1 if n < 3: return 1 if S % 2 == 0: return F(n - 1) - F(n - 2) else: return F(n - 1) + F(n // 2) print(F(100))[/pre2]
Ответов - 3
ЕленаФом: [pre2] from functools import lru_cache @lru_cache def F(n): if n < 3: return 1 S = sum([int(c) for c in str(n)]) #print(n,S) if S % 2 == 0: return F(n - 1) - F(n - 2) else: return F(n - 1) + F(n // 2) print(F(100)) # 23 [/pre2] Кеширование важно, иначе очень долго. И нельзя писать как у вас S = 1, поскольку при вложенных вызовах рекурсии будут другие суммы цифр числа n, ваша программа просто "не туда" улетает после первого вызова.
Ar3turrr: ЕленаФом пишет: Кеширование важно, иначе очень долго. Что такое кеширование? Что именно делает кеширование? И нужно ли его использовать всегда, когда дело касается рекурсии?
Поляков: Ar3turrr пишет: Что такое кеширование? Что именно делает кеширование? И нужно ли его использовать всегда, когда дело касается рекурсии? Кэширование (мемоизация) - это сохранение в памяти всех вычисленных ранее значений функции. Если мы уже вычислили F(100), то в следующий раз уже не нужно выполнять вычисления, а можно просто взять готовое значение. Кэширование необходимо, когда рекурсивная функция вызывает сама себя несколько раз (здесь - два) и очень долго работает. Кэширование служит для ускорения вычислений. Вместо него можно использовать динамическое программирование, когда результаты предыдущих вычислений сохраняются в массиве.
полная версия страницы