Форум » Рекурсивные процедуры и функции » Задание №3694 » Ответить

Задание №3694

MACTEPyc: Что не так с нижеизложенным кодом программы, а именно: Во первых, при запуске в Turbo Pascal выдаёт ошибку по переполнению стека. Во вторых, при запуске в онлайн IDE выдаёт минимальное значение n=7, т.е. F(7) = 16381. [pre2] Program zadanie_3694; var Ch: integer; S: string; 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 + 1) else F := n + F(n + 3) end; begin Ch := 0; repeat Ch := Ch + 1; Str(Ch, S); writeln('F('+S+') = ', F(Ch)); until F(Ch) > 1000; end. [/pre2]

Ответов - 10

Поляков: У вас в некоторых случаях получается бесконечная рекурсия и переполнение стека. Можно перехватить это исключение или проанализировать алгоритм и не вызывать функцию для тех n, при которых алгоритм зацикливается.

MACTEPyc: Пробовал использовать обработку исключений по переполнению стека, положительного результата не дало. В первом сообщении я уже писал о том, что запускал в онлайн компиляторе online pascal compiler. Вот скринкаст процесса выполнения программы, без ошибок по переполнению стека: Тогда возникают вопросы: 1. В этом случае минимальное значение n = 7, для которого F(n)>1000? 2. Или как вариант, что данный компилятор игнорирует переполнение стека и ограничивается определённым количеством цикла, но тогда, как определить зацикливание, какое количество циклов считать перебором? Спасибо за внимание.

Поляков: Вероятно, в той среде двухбайтное представление целых чисел, так что после превышения порога в 32767 получается отрицательное число и рекурсия заканчивается, на успев вызвать переполнение стека.n = 7, для которого F(n)>1000? Нет, это не так. Там ответ 852. как определить зацикливание, какое количество циклов считать перебором Думаю, что 100 достаточно. Вот пример решения на Питоне, где в заголовок функции добавлен еще один параметр - вложенность вызовов. При превышении допустимого числа вызовов возвращается условное значение None и происходит выход из функции. [pre2] def F(n, nest = 0): if nest > 100: return None if n <= 5: return 1 if n % 3 == 0: f1 = F(n//3 + 1, nest + 1) return n + f1 if f1 else None else: f1 = F(n+6, nest + 1) return n + f1 if f1 else None n = 1 while True: r = F(n) if r != None and r > 1000: print(n, r) break n += 1[/pre2]


ИринаЧ: Спасибо!

tnrom: Константин Юрьевич, а можно пояснить с этой задачей на паскале?

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

Sevendwalk: НОМЕР 3695 [pre2] def F(n): if n < 6: return n elif n > 5 and n % 3 == 0: return n + F(n/3 + 2) else: return 0 for i in range(3, 800, 3): f = F(i) if f != 0: if f > 1000: print(i, f)[/pre2] Консоль: 705 1023.0 - минимальное значение 732 1114.0 - ответ на сайте 750 1002.0 759 1101.0 768 1026.0 777 1038.0 786 1140.0 795 1062.0 Почему 705 - не верно?

cabanov.alexey: return 0 считаю очень плохой идеей Попробуйте использовать try ... except [pre2]def F(n): if n < 6: return n elif n > 5 and n % 3 == 0: return n + F(n/3 + 2) else: return n + F(n+3) for i in range(3, 800, 3): try: f = F(i) if f > 1000: print(i, f) except: pass[/pre2]

Ульяна: (№ 3821) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями: F(n) = 1, при n < 2, F(n) = F(n/3) - 1, когда n ≥ 2 и делится на 3, F(n) = F(n - 1) + 17, когда n ≥ 2 и не делится на 3. Назовите минимальное значение n, для которого F(n) равно 110. Не могу понять где ошибка, я пробовала решать другое 16 задание также у меня получилось. def f(n): if n < 2: return 1 if n >= 2 and 3 == 0: return f(n // 3) - 1 else: return f(n - 1) + 17 for i in range(1000): if f(i) == 110: print(i)

zachto: Проверяйте свой код, Ульяна . [pre2] def f(n): if n < 2: return 1 if n >= 2 and n % 3 == 0: return f(n // 3) - 1 return f(n - 1) + 17 for i in range(100000): if f(i) == 110: print(i) break [/pre2]



полная версия страницы