Python вычисляет каталонские числа

Question

У меня есть код, который вычисляет каталитические числа с помощью метода биномиальных коэффициентов.

def BinominalCoefficient(n,k): 
    res = 1; 
    if (k > n - k): 
     k = n - k 
    for i in range(k): 
     res *= (n - i) 
     res /= (i + 1) 
    return res 
def CatalanNumbers(n): 
    c = BinominalCoefficient(2*n, n) 
    return (c//(n+1)) 
print (CatalanNumbers(510)) 

У меня есть результат в «нан», когда я пытаюсь вычислить каталонской число которых п больше, чем 510. Почему это происходит? И как я могу это решить?

Answer 1

Я предполагаю, что вы используете Python 3.

Ваш res /= (i + 1)res //= (i + 1) должен быть, чтобы заставить целочисленную арифметику:

def BinominalCoefficient(n,k): 
    res = 1 
    if (k > n - k): 
     k = n - k 
    for i in range(k): 
     res *= (n - i) 
     res //= (i + 1) 
    return res 
def CatalanNumbers(n): 
    c = BinominalCoefficient(2*n, n) 
    return (c//(n+1)) 
print (CatalanNumbers(511)) 

возвращается

2190251491739477424254235019785597839694676372955883183976582551028726151813997871354391075304454574949251922785248583970189394756782256529178824038918189668852236486561863197470752363343641524451529091938039960955474280081989297135147411990495428867310575974835605457151854594468879961981363032236839645 

Вы получаете nan потому что Divison/= в Python 3 возвращает float, который переполняется до inf.