Автор | Сообщение |
|
Отправлено: 25.11.22 07:14. Заголовок: Задание 16 №5603 (А. Куканова)
Здравствуйте, программа не может посчитать числа, которые меньше 10000 Сама задача : Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = n - 10000, если n > 10000, F(n) = F(n + 1) + F(n + 2), если 1 ≤ n ≤ 10000. Программа: 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)) ошибка - проблема с рекурсией print(f(12345)) выдает ответ - 2345
|
|
|
Ответов - 11
[только новые]
|
|
|
Отправлено: 25.11.22 17:15. Заголовок: Здарова, Дашка, решай лучше массивом. Так немного запарнее, но зато нет проблем с рекурсией.
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]))
|
|
|
|
Отправлено: 26.11.22 02:45. Заголовок: Здравствуйте, спасиб..
Здравствуйте, спасибо за помощь с решением. Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает
|
|
|
|
| Администратор
|
Сообщение: 3839
|
|
Отправлено: 26.01.23 12:12. Заголовок: Daria пишет: Правда ..
Daria пишет: цитата: | Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает |
|
Это случай, когда рекурсию использовать не стоит.
|
|
|
|
Отправлено: 06.03.23 22:19. Заголовок: Daria пишет: Здравс..
Daria пишет: цитата: | Здравствуйте, спасибо за помощь с решением. Правда ещё хотелось бы узнать почему в моем решении рекурсия не работает |
| в случае вызова функции f(10) на первом уровне рекурсии формируется 2 вызова, каждый из них формирует по 2 рекурсивных вызова, каждый из которых тоже формирует по 2 вызова. то есть количество вызовов на N-ом шаге равно 2^N,соответственно при количестве шагов порядка 10000 количество созданных рекурсивных вызовов будет составлять значения порядка 2^10000 или ~10^3000. если не вдаваться в возможность или не возможность подобного предположения , то даже если предположить выделение по 1 биту для индентификатора каждого вызова - то потребуется ~10^2999 байт. надо сказать что суммарный объем данных человечества сейчас находится на уровне порядка 100 Зетабайт. это число с 26 разрядами. против 2999. это утрировано, но примерно вот такая математика. то есть ваш комп просто-напросто не способен запомнить все дерево вызовов, потому что ему банально для этого не хватает памяти.
|
|
|
|
Отправлено: 26.04.23 21:40. Заголовок: Скажите пожалуйста п..
Скажите пожалуйста почему нельзя написать так: 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])) Ответ выдает 101, что не является верным
|
|
|
|
| Администратор
|
Сообщение: 3998
|
|
Отправлено: 04.06.23 11:26. Заголовок: Ангелина пишет: поче..
Ангелина пишет: цитата: | почему нельзя написать так: |
|
Массив нужно заполнять с конца: for n in range(len(f)-1,0,-1): В вашем варианте вы обращаетесь к f[n+1] и f[n+2], которые еще не заполнены.
|
|
|
|
Отправлено: 01.12.22 18:43. Заголовок: не хватает разборов ..
не хватает разборов последних задач, в паскале выдает переполнение стека, тоже хотелось бы пояснений
|
|
|
|
| Администратор
|
Сообщение: 3840
|
|
Отправлено: 26.01.23 12:12. Заголовок: vin пишет: не хватае..
vin пишет: цитата: | не хватает разборов последних задач, в паскале выдает переполнение стека, тоже хотелось бы пояснений |
|
Классическое динамическое программирование с сохранением данных в массиве вас спасет.
|
|
|
|
Отправлено: 03.03.23 17:08. Заголовок: в PascalABC.Net все ..
в PascalABC.Net тоже всё довольно просто. достаточно включить кеширование, и вычислить результаты функций двигаясь сверху вниз, например в цикле. программа при вычислении каждого значения для меньшего N не будет пытаться строить двоичное дерево рекурсий, а будет использовать кеш. но нужно учитывать, что кеширование результатов функций доступно в PascalABC.Net начиная с версии 3.8.1. Для более ранних версий сохранение результатов в массив может быть использовано аналогично кешированию. ### [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));
|
|
|
|
Отправлено: 20.03.23 13:32. Заголовок: Программа образует с..
Программа образует своеобразный ряд Фибоначчи, поэтому можно представить программу так 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))
|
|
|
|
Отправлено: 11.07.23 22:05. Заголовок: Рекурсия вполне спра..
Рекурсия вполне справляется 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))
|
|
|
|