| Автор | Сообщение |
|
Отправлено: 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))
|
|
|
|
- участник сейчас на форуме
- участник вне форума