@jinxonik / UniLecs #112 (Python)

Conference.py

########################################################################
# ВАРИАНТ №1
# Пронумеруем позицию каждого человека за столом от 1 до n.
# Возьмём первого и переберём всех, кому он может протянуть руку.
# Очевидно, что это могут быть только те, кто сидит на чётных позициях
# (в т.ч. соседи), т.к. иначе кол-во сидящих слева и справа от него было
# бы нечётным, и эти люди не смогли бы пожать друг другу руки попарно.
# Для каждого такого случая посчитаем и перемножим кол-во вариантов
# рукопожатий для сидящих слева и справа через рекурсивный вызов, а
# все результаты (произведения) просуммируем. Это и будет ответом.
# Для ускорения работы функции результаты будем кешировать.
def handshakes1(n):

  def handshake(n):
    if n <= 2: return 1
    if n in reslist: return reslist[n]
    result = 0
    for i in range(0, n, 2):
      result += handshake(i) * handshake(n-2-i)
    reslist[n] = result
    return result

  reslist = {}
  return handshake(n)

########################################################################
# ВАРИАНТ №2
# Получившийся ряд чисел является рядом чисел Каталана для m = n/2
# handshakes2(n) = Cat(m) = C(2*m,m)/(m+1) = C(n,n/2)/(n/2+1)
def handshakes2(n):

  # биномиальный коэффициент
  def C(n, k):
    result = 1
    for i in range(1, k+1):
      result = result * (n-i+1) // i
    return result

  return C(n, n//2) // (n//2+1)

########################################################################
# ВАРИАНТ №3 (тоже числа Каталана для m = n/2)
# handshakes3(n) = Cat(m) = 2*(2*m-1)/(m+1)*Cat(m-1) =
#                           handshakes3(n-2)*2*(n-1)/(n/2+1)
# handshakes3(2) = Cat(1) = 1
def handshakes3(n):
  if n == 2: return 1
  return handshakes3(n-2) * 2*(n-1) // (n//2+1)

########################################################################

for i in (2, 4, 6, 8, 10, 12, 16, 20, 32, 50, 100, 200, 500, 1000):
  n,n2,n3 = handshakes1(i),handshakes2(i),handshakes3(i)
  if n == n2 == n3:
    print(f'{i} = {n}')
  else:
    print(f'{i} = ошибка, результаты разные!!! (n1={n1}, n2={n2}, n3={n3})')

ConferenceApprox.py

# Примерный асимптотический расчёт через числа Каталана для m = n/2
# handshakesApprox(n) = Cat(m) = 4**m / (m**(3/2) * sqrt(pi))
# Вычтем ещё 1, чтобы получить точный результат хотя бы для n = 2, 4 и 6 :)
sqrtPi = 1.772453850905516027298  # sqrt(pi)

def handshakesApprox(n):
  m = n // 2
  return int(4**m // (m**(3/2) * sqrtPi) - 1)

for i in (2, 4, 6, 8, 10, 12, 16, 20, 32, 50, 100, 200, 500, 1000):
  print(f'{i} = {handshakesApprox(i)}')