Форум » Рекурсивные процедуры и функции » хелп!! » Ответить
хелп!!
shitpostinka: объясните пожалуйста..... Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: f(n):=n, при n<=5, f(n):=n+f(n / 3 +2), когда n>5 и делится на 3, f(n):=n+ f(n+3), когда n>5 и не делится на 3 минимальное значение n , для которого f(n) определено и больше 1000-?? моя попытка: var i: integer; function f(n:integer):integer; begin if n<=5 then f:=n else if n mod 3=0 then f:=n+f(n div 3 +2) else f:=n+ f(n+3); end; begin i:=1; while f(i) <= 1000 do i:=i+1; writeln (i); end.
Ответов - 9
polyakovss: Посмотрите здесь.
tnrom: Все такие задачи объясняют на питоне. А как на паскале? Я никак не могу понять...
polyakovss: Здравствуйте, tnrom! Вы пишете: Все такие задачи объясняют на питоне. А как на паскале? Я никак не могу понять... Решение на Python для задачи 80 из задания 16: [pre2] def F(n, nest = 0): if nest > 100: return None if n <= 5: return n if n % 3 == 0: f1 = F(n//3 + 2, nest + 1) return n + f1 if f1 != None else None else: f1 = F(n+3, nest + 1) return n + f1 if f1 != None else None n = 1 while True: r = F(n) if r != None and r > 1000: print(n) break n += 1[/pre2] на PascalABC.NET(3.8) можно, например, не мудрствуя лукаво, переписать так: [pre2] ## function F (n:integer; nest: integer := 0): integer; begin if nest > 100 then Result := - 999 else if n <= 5 then Result := n else if n mod 3 = 0 then begin var f1 := F(n div 3 + 2, nest + 1); if f1 <> - 999 then Result := n + f1 else Result := -999 end else begin var f1 := F(n + 3, nest + 1); if f1 <> - 999 then Result := n + f1 else Result := -999 end; end; var n := 1; while True do begin var r := F(n); if (r <> -999) and (r > 1000) then begin print(n); break; end; n += 1; end;[/pre2]
shervlad: polyakovss пишет: Решение на Python для задачи 80 из задания 16: Здравствуйте! Можете пояснить по поводу переменной nest в функции? Как это работает?
polyakovss: Здравствуйте, shervlad! Константин Юрьевич Поляков (Сообщение: 2617): Мне кажется, что идея на поверхности - считаем, сколько раз вызвали функцию (через счетчик-параметр), если слишком много - бесконечная рекурсия, возвращаем условное значение, например, -999. Константин Юрьевич Поляков (Сообщение: 2513): в заголовок функции добавлен еще один параметр - вложенность вызовов. При превышении допустимого числа вызовов возвращается условное значение None и происходит выход из функции. Посмотрите еще здесь. Если нужно подробнее - спрашивайте.
shervlad: Пытаюсь данным способом решить задачу 3493, не выходит, выводит None. Скорее всего, я делаю неправильно, только не могу понять, что именно (такой способ решения до этого ни видел нигде, не до конца понимаю суть). Вот мой код: [pre2] def f(n,nest = 0): if nest > 100: return None if n < -100000: return 1 elif n > 10: f1 = f(n-1,nest+1) f3 = f(n-3,nest+1) if f1!=None and f3!=None: ff = f1 + 3*f3 + 2 else: ff = None return ff if ff else None else: f1 = f(n-1,nest+1) return -f1 if f1 else None print(f(20)) [/pre2] Применим ли вообще данный способ решения к этой задаче?
polyakovss: Здравствуйте, shervlad! Вы пишете: Применим ли вообще данный способ решения к этой задаче?Нет. Давайте разберемся. Рассмотренный выше способ решения с использованием счетчика-параметра ("nest") нужен для предотвращения бесконечной рекурсии, в случае когда значение рекурсивной функции не может быть определено, то есть когда функция не может быть вычислена через значения функции, определеные нерекурсивно. Так, например, в предыдущей задаче 80 из задания 16 не определено значение F(7): Чтобы вычисление завершалось для данного n, необходимо, чтобы функция вычислялась через значения функции, определеные нерекурсивно. Для f(7): f(7) = 7 + f(10); f(10) = 10 + f(13); f(13) = 13 + f(16); ... Видно, что все эти функции не могут быть вычислены через "if n <= 5: return n". Поэтому f(7) не определено. Значит, и считать это значение не нужно (заменяем на None). В задаче 3493 (так как n при вызовах уменьшается) все функции могут быть вычислены через "if n < -100000: return 1 ". Просто количество вызовов будет слишком большим. Это можно исправить, проанализировав функцию. Из "F(n) = 1, при n < –100000" следует, что первом нечетном числе "-100001" F(-100001) = 1. Тогда из "F(n) = – F(n – 1) для остальных случаев" следует, что F(-100000) = -1. Аналогично, F(- 99999) = 1, а F(- 99998) = -1 и так далее. Получаем решение задачи 3493: [pre2] def f(n): if n < -100000: return 1 if n > 10: return f(n-1) + 3 * f(n-3) + 2 else: if n % 2 == 0: return -1 else: return 1 print(f(20))[/pre2]
shervlad: Большое спасибо за подробное объяснение!
tnrom: Спасибо вам огромное! Теперь я поняла с этой дополнительной переменной
полная версия страницы