Форум » Рекурсивные процедуры и функции » ege16 задача80 » Ответить
ege16 задача80
_piter: Помогите, пожалуйста! Не могу понять, почему при значениях больше 6, программа выдает какую-то ошибку [pre2] def f(n): if n <= 5: return n if n%3==0: return n+f(n//3+2) else: return n+f(n+3) print(f(7)) [/pre2] Спасибо!
Ответов - 6 новых
polyakovss: Здравствуйте, _piter! В условии задачи сказано: Назовите минимальное значение n, для которого F(n) определено и больше 1000.Чтобы вычисление завершалось для данного 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) не определено. Можно проанализировать алгоритм и не вызывать функцию для тех n, для которых f(n) не определено. Например, так: [pre2] def f(n): if n <= 5: return n if(n%3==0): return n+f(n//3+2) else: return n+f(n+3) def g(n): x=n if x<=5: return n else: flag = True while x>5: if (x%3!=0) or ((x//3+2)>5) and ((x//3+2) % 3 != 0): flag = False break x=x//3+2 if flag: return f(n) else: return 0 n = 1 while True: if g(n)>1000: print(n) break n += 1 [/pre2] Но проще сделать так, как предложил Константин Юрьевич здесь (Поляков Сообщение: 2513). Тогда:[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]
_piter: polyakovss пишет: В условии задачи сказано: цитата: Назовите минимальное значение n, для которого F(n) определено и больше 1000. у меня условие, почему-то, звучит немного по другому: 80) Алгоритм вычисления функции 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.
_piter: Здравствуйте, polyakovss! Спасибо большое за столь полное погружение и подробное пояснение!!! Неужели это школьный курс, как это все "переварить" школяру, если в нашей "периферийной школе" всего 2 часа информатики в неделю? - это, скорее, риторический вопрос и задан он не лично Вам. И все же, интересно узнать, а в "центральных" школах все это усваивается за те же 2 часа, или используются иные варианты? Еще раз огромное Вам спасибо.
_piter: С условием разобрался, мой текст был от 26 февраля 21 года, в обновленном варианте вопрос звучит именно так, как Вы и сказали. Казалось бы, всего одно слово, но оно позволяет понять, что здесь "@ зарыта"
vin: Помогите, пожалуйста разобраться, думаю большие числа, паскаль работает ну ОЧЕНЬ долго function f (n: integer): integer; begin if n<= 3 then f:= n + 3 else if (n>3) and ((f(n-1)) mod 2 = 0) then f:= f(n-2) +n else if (n>3) and ((f(n-1)) mod 2 = 1) then f:= f(n-2) + 2 * n; end; var s: integer; begin for var i := 40 to 50 do begin s:=s+(f(i)); end; writeln (s) end.
Поляков: Попробуйте динамические программирование: храните все уже вычисленные значения функции в массиве.
полная версия страницы