@jinxonik / UniLecs #112 (Delphi)

Conference.pas

program Conference;  // Delphi XE2+
// Решение задачи "Совещание" (UniLecs #112: https://t.me/unilecs/416)
{$APPTYPE CONSOLE}

// Модуль Velthuis.BigIntegers: https://github.com/rvelthuis/BigNumbers
// Описание модуля: http://www.rvelthuis.de/programs/bigintegers.html

uses
  Winapi.Windows, System.SysUtils, System.Math, Velthuis.BigIntegers;

type
  THandshakes = class
    public
      function Method1(N: Integer): BigInteger;
      function Method2(N: Integer): BigInteger;
      function Method3(N: Integer): BigInteger;
      function Approx(N: Integer): Extended;
    private
      Cache: array of BigInteger;
      function C(N, K: Integer): BigInteger;
  end;

/////////////////////////////////////////////////////////////////////////
// МЕТОД №1
// Пронумеруем позицию каждого человека за столом от 1 до n.
// Возьмём первого и переберём всех, кому он может протянуть руку.
// Очевидно, что это могут быть только те, кто сидит на чётных позициях
// (в т.ч. соседи), т.к. иначе кол-во сидящих слева и справа от него было
// бы нечётным, и эти люди не смогли бы пожать друг другу руки попарно.
// Для каждого такого случая посчитаем и перемножим кол-во вариантов
// рукопожатий для сидящих слева и справа через рекурсивный вызов, а
// все результаты (произведения) просуммируем. Это и будет ответом.
// Для ускорения работы функции результаты будем кешировать.
function THandshakes.Method1(N: Integer): BigInteger;
var M, i: Integer;
begin
  if N <= 2 then Exit(1);
  M := N div 2;
  if Length(Cache) < M-1 then SetLength(Cache, M-1)
  else if Cache[M-2] <> 0 then Exit(Cache[M-2]);
  Result := 0;
  for i := 0 to M-1 do
    Result := Result + Method1(i*2) * Method1(N-2-i*2);
  Cache[M-2] := Result;
end;

/////////////////////////////////////////////////////////////////////////
// МЕТОД №2
// Получившийся ряд чисел является рядом чисел Каталана для m = n/2
// Method2(n) = Cat(m) = C(2*m,m)/(m+1) = C(n,n/2)/(n/2+1)
function THandshakes.Method2(N: Integer): BigInteger;
begin
  Result := C(N, N div 2) div (N div 2 + 1);
end;

// биномиальный коэффициент
function THandshakes.C(N, K: Integer): BigInteger;
var
  Divisor: BigInteger;
  i: Integer;
begin
  Result := 1;
  Divisor := 1;
  for i := 1 to K do
  begin
    Result := Result * (N-i+1);
    Divisor := Divisor * i;
  end;
  Result := Result div Divisor;
end;

/////////////////////////////////////////////////////////////////////////
// МЕТОД №3 (тоже числа Каталана для m = n/2)
// Method3(n) = Cat(m) = 2*(2*m-1)/(m+1)*Cat(m-1)
// Method3(2) = Cat(1) = 1
function THandshakes.Method3(N: Integer): BigInteger;
var
  Divisor: BigInteger;
  i: Integer;
begin
  Result := 1;
  Divisor := 1;
  for i := 1 to N div 2 do
  begin
    Result := Result * (2*(2*i-1));
    Divisor := Divisor * (i+1);
  end;
  Result := Result div Divisor;
end;

/////////////////////////////////////////////////////////////////////////
// Примерный асимптотический расчёт через числа Каталана для m = n/2
// approx(n) = Cat(m) = 4**m / (m**(3/2) * sqrt(pi))
// Вычтем ещё 1, чтобы получить точный результат хотя бы для n = 2, 4 и 6 :)
function THandshakes.Approx(N: Integer): Extended;
var M: Integer;
begin
  M := N div 2;
  Result := Power(4.0, M) / (Power(M, 1.5) * Sqrt(Pi)) - 1.0;
end;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

var
  HS: THandshakes;
  N: array [0..13] of Integer = (2, 4, 6, 8, 10, 12, 16, 20, 32, 50, 100, 200, 500, 1000);
  N1, N2, N3: BigInteger;
  k, i: Integer;
begin
  HS := THandshakes.Create;
  try
    for i := 0 to High(N) do
    begin
      k := N[i];
      N1 := HS.Method1(k);
      N2 := HS.Method2(k);
      N3 := HS.Method3(k);
      Write(k, ' = ');
      if (N1 = N2) and (N2 = N3) then Write(N1.ToString)
      else Write('error, different results!!! (N1=', N1.ToString, ', N2=', N2.ToString, ', N3=', N3.ToString, ')');
      WriteLn(', Approx = ', FloatToStr(Int(HS.Approx(k))));
    end;
  finally
    HS.Free;
  end;
end.