RecursionError: maximum recursion depth exceeded in comparison

@D303 · Регистрация: 28.07.2019

Студворк — интернет-сервис помощи студентам

Всем добрый вечер
Возникли проблемы с задачей.
Условие:
Найдите аналитическое выражение для $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{3}(n)$

Вход программы состоит из единственной строки — списка из не более чем ста тысяч чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{i}\leq 2000000000$

Выведите единственную строку — список значений $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{3}({n}_{i})$ , разделенных пробелом, для чисел из входа.

Sample Input:
1 3 5
Sample Output:
0 1 2

Я работаю в PyScripter и у него с данным кодом проблем нет. Однако на платформе, в которой дано это задание этот код не принимается с таким вот поясненим:

[I]Failed test #2 of 11. Runtime error

Traceback (most recent call last):
File "jailed_code", line 19, in <module>
print(int(p(A)),end=' ')
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
[Previous line repeated 994 more times]
File "jailed_code", line 6, in p
if n==0 or n==1 or n==2:
RecursionError: maximum recursion depth exceeded in comparison

Как это исправить?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A=list(map(int,input().split()))
 
 
def p(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    else:
        return  p(n-1) + p(n-2) - p(n-4) - p(n-5) + p(n-6)
 
for i in range(len(A)):
    print(int(p(A[i])),end=' ')

@unfindable_404 · 07.05.2020, 22:33

Может они вам отрицательное число подают? По условию число меньше или равно 2 * 10⁹. А про нижнюю границу ничего не сказано. А с отрицательным числом ваша функция уйдёт в бесконечную рекурсию.

@Welemir1 · 07.05.2020, 22:34

ну так у тебя для последнего варианта аж 5 раз рекурсивно вызывается функция

Сообщение от D303

return p(n-1) + p(n-2) - p(n-4) - p(n-5) + p(n-6)

можно лимит рекурсии увеличить, но не уверен что поможет

@unfindable_404 · 07.05.2020, 22:41

И ещё, используйте возможности языка по назначению. Цикл for предназначен для итерации по коллекциям.
Используйте его не так:

Python
1
2
for i in range(len(A)):
    print(int(p(A[i])),end=' ')

а так:

Python
1
2
for i in A:
    print(int(p(i)),end=' ')

Добавлено через 4 минуты
А что вообще за задача? Это всё условие?

@D303 · 08.05.2020, 00:59 **[ТС]**

Не подскажите, как это сделать?

Добавлено через 3 минуты
Да, это все условие. Разбиение числа на три слагаемых (порядок нам не важен)

Добавлено через 9 минут
Так, теперь ошибок нет. Но программа все равно не проходит 2 тест (в чемон заключается, я не знаю).

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A=list(map(int,input().split()))
 
 
def p(n):
    if n==-n:
        return (n**2)//12
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    if n==6:
        return 3
    else:
        
        return  (n**2)//12
 
for i in A:
    print(int(p(i)),end=' ')

@unfindable_404 · 08.05.2020, 13:03

Сообщение от D303

Да, это все условие. Разбиение числа на три слагаемых

На вход подаются три числа. На выходе тоже три. Так какое число надо разбить на слагаемые?
Объясните, пожалуйста, как вы понимаете задание, чтобы я тоже его понял.

@D303 · 08.05.2020, 13:30 **[ТС]**

На вход подается какое то количество чисел (в данном примере 3). И для каждого из них надо найти количество способов разбить его на 3 слагаемых (порядок нам не важен). И вывести количество разбиений для каждого из введеных чисед в строку
Пример разбиения числа 5: 1+1+3 , 1+2+2 - 2 способа

@Catstail · 08.05.2020, 14:15

В этом решении дикая параллельная рекурсия. Отсюда и проблемы. Радикально они решаются применением накопительных параметров:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def p_bad(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    else:
        return  p_bad(n-1) + p_bad(n-2) - p_bad(n-4) - p_bad(n-5) + p_bad(n-6)
 
def p_good(n,arr=[0,0,0,1,1,2]):
    if (n<=5):
        return arr[n]
    else:
        z=arr[5]+arr[4]-arr[2]-arr[1]+arr[0]
        return p_good(n-1,arr[1:]+[z])
 
print(p_good(22))
print(p_bad(22))

@D303 · 08.05.2020, 14:30 **[ТС]**

Сообщение от Catstail

В этом решении дикая параллельная рекурсия. Отсюда и проблемы. Радикально они решаются применением накопительных параметров:

Ваш код также не хочет обрабатывать большие числа (по условию, верхняя граница это 20000000)
Эту проблему мне удалось решить, используя явную формулу для таких разбиений ( [n^2/12] - целая часть)

Сейчас проблема в другом, программа, тестирующая код, на 2 тесте выдает ошибку. В чем заключается этот тест, я не знаю.

Вот код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A=list(map(int,input().split()))
 
 
def p(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    if n==-n:
        return  n**2//12
    else:
        return  n**2//12
 
for i in A:
    print(int(p(i)),end=' ')

Вот ссылка: https://stepik.org/lesson/11744/step/10?unit=2659

@Catstail · 08.05.2020, 16:30

Сообщение от D303

Эту проблему мне удалось решить, используя явную формулу для таких разбиений ( [n^2/12] - целая часть)

- я не занимался никакими разбиениями. Я имел дело только с кодом. Что он делает - не интересовался.

Добавлено через 14 минут
От рекурсии, кстати, легко отказаться. Но 20000000 циклов - это сильно.

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@unfindable_404 693 / 471 / 204 Регистрация: 22.03.2020 Сообщений: 1,051
	07.05.2020, 22:33
	Может они вам отрицательное число подают? По условию число меньше или равно 2 * 10⁹. А про нижнюю границу ничего не сказано. А с отрицательным числом ваша функция уйдёт в бесконечную рекурсию. 0

@D303 0 / 0 / 0 Регистрация: 28.07.2019 Сообщений: 24
	08.05.2020, 13:30 [ТС]
	На вход подается какое то количество чисел (в данном примере 3). И для каждого из них надо найти количество способов разбить его на 3 слагаемых (порядок нам не важен). И вывести количество разбиений для каждого из введеных чисед в строку Пример разбиения числа 5: 1+1+3 , 1+2+2 - 2 способа 0