Форум » Рекурсивные процедуры и функции » Задание 16 №5603 (А. Куканова) » Ответить
Задание 16 №5603 (А. Куканова)
Daria: Здравствуйте, программа не может посчитать числа, которые меньше 10000 Сама задача : Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = n - 10000, если n > 10000, F(n) = F(n + 1) + F(n + 2), если 1 ≤ n ≤ 10000. Программа:[pre2] def f(n): if n> 10000: return n-10000 if 1<=n and n<=10000: return f(n+1)+f(n+2) print(f(10)) [/pre2] ошибка - проблема с рекурсией print(f(12345)) выдает ответ - 2345
Ответов - 11
Фанатка полякова: [pre2] s=[1]*13000 for n in range(12345,1,-1): if n>10000: s[n] = n-10000 else: s[n] = s[n+1]+s[n+2] print(int(s[12345]*(s[10]-s[12])/s[11]+s[10101])) [/pre2]
Daria: Здравствуйте, спасибо за помощь с решением. Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает
Поляков: Daria пишет: Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает Это случай, когда рекурсию использовать не стоит.
PeerGynt: Daria пишет: Здравствуйте, спасибо за помощь с решением. Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает в случае вызова функции f(10) на первом уровне рекурсии формируется 2 вызова, каждый из них формирует по 2 рекурсивных вызова, каждый из которых тоже формирует по 2 вызова. то есть количество вызовов на N-ом шаге равно 2^N,соответственно при количестве шагов порядка 10000 количество созданных рекурсивных вызовов будет составлять значения порядка 2^10000 или ~10^3000. если не вдаваться в возможность или не возможность подобного предположения , то даже если предположить выделение по 1 биту для индентификатора каждого вызова - то потребуется ~10^2999 байт. надо сказать что суммарный объем данных человечества сейчас находится на уровне порядка 100 Зетабайт. это число с 26 разрядами. против 2999. это утрировано, но примерно вот такая математика. то есть ваш комп просто-напросто не способен запомнить все дерево вызовов, потому что ему банально для этого не хватает памяти.
Ангелина: Скажите пожалуйста почему нельзя написать так: [pre2] f = [1]*13000 for n in range(len(f)): if n > 10000: f[n] = n - 10000 else: f[n] = f[n+1] + f[n+2] print(int(f[12345]*(f[10]-f[12])/f[11] + f[10101]))[/pre2] Ответ выдает 101, что не является верным
Поляков: Ангелина пишет: почему нельзя написать так: Массив нужно заполнять с конца: [pre2]for n in range(len(f)-1,0,-1):[/pre2]В вашем варианте вы обращаетесь к f[n+1] и f[n+2], которые еще не заполнены.
vin: не хватает разборов последних задач, в паскале выдает переполнение стека, тоже хотелось бы пояснений
Поляков: vin пишет: не хватает разборов последних задач, в паскале выдает переполнение стека, тоже хотелось бы пояснений Классическое динамическое программирование с сохранением данных в массиве вас спасет.
PeerGynt: в PascalABC.Net тоже всё довольно просто. достаточно включить кеширование, и вычислить результаты функций двигаясь сверху вниз, например в цикле. программа при вычислении каждого значения для меньшего N не будет пытаться строить двоичное дерево рекурсий, а будет использовать кеш. но нужно учитывать, что кеширование результатов функций доступно в PascalABC.Net начиная с версии 3.8.1. Для более ранних версий сохранение результатов в массив может быть использовано аналогично кешированию. [pre2] ### [cache] function f(n:bi):bi:=n>10000?n-10000:f(n+1)+f(n+2); for var i :=10000 downto 10 do f(i); prln(f(12345)*(f(10)-f(12))/f(11) + f(10101)); [/pre2]
Garik: Программа образует своеобразный ряд Фибоначчи, поэтому можно представить программу так [pre2] def f(n, last = 1, el = 3): if n > 10000: return n - 10000 n = 10000 - n newel = 0 for i in range(n): newel = last + el last = el el = newel return newel print(f(12345)*(f(10)-f(12))/f(11)+f(10101)) [/pre2]
Ж: Рекурсия вполне справляется [pre2] from functools import * @lru_cache(None) def f(n): if n> 10000: return n-10000 if 1<=n <=10000: return f(n+1)+f(n+2) for n in range(12346,-1,-1): f(n) print(f(12345)*(f(10) - f(12)) // f(11) + f(10101)) [/pre2]
полная версия страницы