Отправлено: 09.04.21 19:44. Заголовок: хелп!!

объясните пожалуйста.....
Алгоритм вычисления значения функции 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.

 Отправлено: 09.04.21 21:35. Заголовок: Посмотрите здесь...

Посмотрите здесь.

 Отправлено: 15.04.21 17:48. Заголовок: Все такие задачи объ..

Все такие задачи объясняют на питоне. А как на паскале? Я никак не могу понять...

 Отправлено: 15.04.21 20:29. Заголовок: Ответ

Здравствуйте, tnrom!


Вы пишете:

цитата:

Все такие задачи объясняют на питоне. А как на паскале? Я никак не могу понять...

Решение на Python для задачи 80 из задания 16:

цитата:

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

на PascalABC.NET(3.8) можно, например, не мудрствуя лукаво, переписать так:

цитата:

## 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;

 Отправлено: 25.04.21 15:03. Заголовок: polyakovss пишет: Р..

polyakovss пишет:

цитата:

Решение на Python для задачи 80 из задания 16:

Здравствуйте! Можете пояснить по поводу переменной nest в функции?
Как это работает?

 Отправлено: 25.04.21 17:13. Заголовок: Ответ

Здравствуйте, shervlad!


Константин Юрьевич Поляков (Сообщение: 2617):

цитата:

Мне кажется, что идея на поверхности - считаем, сколько раз вызвали функцию (через счетчик-параметр), если слишком много - бесконечная рекурсия, возвращаем условное значение, например, -999.

Константин Юрьевич Поляков (Сообщение: 2513):

цитата:

в заголовок функции добавлен еще один параметр - вложенность вызовов. При превышении допустимого числа вызовов возвращается условное значение None и происходит выход из функции.

Посмотрите еще здесь.

Если нужно подробнее - спрашивайте.

 Отправлено: 26.04.21 17:18. Заголовок: Пытаюсь данным спосо..

Пытаюсь данным способом решить задачу 3493, не выходит, выводит None. Скорее всего, я делаю неправильно, только не могу понять, что именно (такой способ решения до этого ни видел нигде, не до конца понимаю суть).
Вот мой код:

 
 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)) 
 

Применим ли вообще данный способ решения к этой задаче?

 Отправлено: 26.04.21 20:10. Заголовок: Ответ

Здравствуйте, 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:

цитата:

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))

 Отправлено: 26.04.21 21:02. Заголовок: Большое спасибо за п..

Большое спасибо за подробное объяснение!

 Отправлено: 16.04.21 05:01. Заголовок: Спасибо вам огромное..

Спасибо вам огромное! Теперь я поняла с этой дополнительной переменной