Форум » Рекурсивные процедуры и функции » ЕГЭ-16, № 117 » Ответить
ЕГЭ-16, № 117
informatika312: Попытка решить задачу через динамическое программирование на таком большом интервале дает ошибку Traceback (most recent call last): File "C:/Users/Lenovo/Desktop/untitled-3.py", line 5, in <module> a.append(1 + a[i - 1]) builtins.MemoryError Решение: [pre2] a = [1] for i in range(1, 500000001): if i % 2 != 0: a.append(1 + a[i - 1]) if i % 2 == 0: a.append(a[i // 2]) result = {} for num in a: if num not in result: result[num] = 1 else: result[num] += 1 print(result[3]) [/pre2] Динамическим программированием такую задачу не решить? Или решить, но я что-то делаю не так?
Ответов - 3
Поляков: Посмотрите обсуждение в соседней теме.
informatika312: Смотрела. Функция from functools import lru_cache @lru_cache тоже не работает на этом интервале. Вы также в той теме упоминаете, что один из способов - динамическое программирование. Вот и интересно было именно по поводу дин.программирования.
Поляков: Вы же увидели, что ДП не проходит по памяти.
полная версия страницы