@jinxonik / UniLecs #88

Cnk.py

from math import factorial

# Вычислить биномиальный коэффициент Cnk
# Возвращает None при k > n, k < 0 и результате, превышающем 2**64-1
def C(n, k):
  if not 0 <= k <= n: return None  # неверные параметры
  if k > n-k: k = n-k  # C(n, k) = C(n, n-k)

  # при k > 33 результат однозначно будет больше, чем 2**64-1,
  # т.к. C(67, 33) < 2**64, но C(68, 34) уже больше
  max_k = 33
  if k > max_k: return None

  # максимально допустимый результат
  max_result = 2**64-1
  fact_k = factorial(k)
  max_num = max_result * fact_k

  # вычисление
  num = 1
  for i in range(n-k+1, n+1):
    num *= i
    if num > max_num: return None
  return num // fact_k

maxN = 2**32-1
for a in ((maxN,maxN), (maxN,maxN-1), (maxN,maxN-2), (maxN,maxN-3), (987654321,2), (10**9, 10**6),
          (1000,5), (1000,995), (67,33), (68,34), (10,3), (3,10), (7,4), (0,0), (1,-1)):
  n, k = a
  res = C(n, k)
  if res != None:
    print('C(%d, %d) = %d' % (n, k, res))
  else:
    print('C(%d, %d) = wrong data or too large result' % (n, k))