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 циклов - это сильно.

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@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