2

В чем может быть проблема при просчете чисел Каталана? На больших числах возникает неточность, т.е на 45 числе выводит 2257117854077247679365120, а должно быть 2257117854077248073253720.

arr = [1]
def Catalan(n):
    global arr
    while(len(arr) != n+1):
        arr.append(int(int(arr[len(arr)-1] ) * (4*len(arr)-2)/(len(arr)+1) ) )
    print(arr[n])
jfs
  • 52,361
S.Andrew
  • 119
  • 8
  • А какой тип используется в Питоне для работы с числами, Double какой-нибудь, с точностью до 18 знаков? – Kromster Dec 25 '17 at 11:34
  • @Kromster, если тут всё целочисленное, он должен сам перейти на biginteger. Про дробные не знаю. – Qwertiy Dec 25 '17 at 11:53
  • 1
    @VasylKolomiets, судя по меткам питон третий, но там есть деление: (4*len(arr)-2)/(len(arr)+1). – Qwertiy Dec 25 '17 at 11:56
  • 1
    Пролистал документацию, написано, что с третьей версии int не имеет границ, а использовал при написании 3.5. – S.Andrew Dec 25 '17 at 11:56
  • def Catalan(n): arr = [1] for j in range(1,n+1): total = [] for i in range(j): final = arr[i]*arr[j-1-i] total.append(final) fin = sum(total) arr.append(fin) print(arr[n]) Вот такой код. Деления нет, но все равно при числе 45 выводит ложный результат. В чем может быть проблема? – pochatok228 Jan 10 '18 at 10:28

2 Answers2

9
(4*len(arr)-2)/(len(arr)+1) )
#             ^ вот поэтому

В Python 3 / выполняет деление с плавающей точкой. А точность двойных чисел с плавающей точкой ограничена примерно 15-17 десятичными цифрами, аккурат после которых (15) у вас и наблюдается разница.

См. также "Вычисления на числах с плавающей точкой не работают"

1 / 1 # => 1.0

Если заменить его на //, целочисленное деление (которое в Python 2 выполнялось оператором /, если операнды были целочисленными), результаты станут ожидаемыми. Поэтому, кстати, этот алгоритм прекрасно работает в Python 2 (если не импортировать "деление из будущего").

И выкиньте int(...)'ы. Там и так будут целые числа.

1

Удобнее реализовывать подобные функции по рекурентным формулам, например если взять третью рекурентную формулу из википедии, получим следующую функцию:

import functools


@functools.lru_cache(maxsize=None)
def catalan(n):
    if n == 0:
        return 1
    return catalan(n-1)*2*(2*n-1)//(n+1)

Результат для 45: 2257117854077248073253720

Andrio Skur
  • 2,873
Денис
  • 864