@jinxonik / UniLecs #112 (C++)

Conference.cpp

#include <iostream>
#include <vector>
#include "bigInt.h"  // https://sourceforge.net/projects/cpp-bigint/

//#define USE_METHOD1  // первый метод работает очень медленно, его можно убрать

class Handshakes {
  private:
    std::vector<BigInt::Rossi> cache;
    BigInt::Rossi C(int n, int k);
  public:
    BigInt::Rossi method1(int n);
    BigInt::Rossi method2(int n);
    BigInt::Rossi method3(int n);
    double approx(int n);
};

////////////////////////////////////////////////////////////////////////////////
// МЕТОД №1
// Пронумеруем позицию каждого человека за столом от 1 до n.
// Возьмём первого и переберём всех, кому он может протянуть руку.
// Очевидно, что это могут быть только те, кто сидит на чётных позициях
// (в т.ч. соседи), т.к. иначе кол-во сидящих слева и справа от него было
// бы нечётным, и эти люди не смогли бы пожать друг другу руки попарно.
// Для каждого такого случая посчитаем и перемножим кол-во вариантов
// рукопожатий для сидящих слева и справа через рекурсивный вызов, а
// все результаты (произведения) просуммируем. Это и будет ответом.
// Для ускорения работы функции результаты будем кешировать.
BigInt::Rossi Handshakes::method1(int n)
{
  if (n <= 2) { return BigInt::Rossi(1); }
  int m = n/2;
  int idx = m-2;
  if (idx < cache.size() && cache[idx] != BigInt::Rossi(0)) { return cache[idx]; }
  BigInt::Rossi result(0);
  for (int i = 0; i < m; ++i) {
    result += method1(i*2) * method1(n-2-i*2);
  }
  while (idx > cache.size()) { std::cout << "x"; cache.push_back(BigInt::Rossi(0)); }
  cache.push_back(result);
  return result;
}

////////////////////////////////////////////////////////////////////////////////
// МЕТОД №2
// Получившийся ряд чисел является рядом чисел Каталана для m = n/2
// method2(n) = Cat(m) = C(2*m,m)/(m+1) = C(n,n/2)/(n/2+1)
BigInt::Rossi Handshakes::method2(int n)
{
  return C(n, n/2) / BigInt::Rossi(n/2+1);
}

// биномиальный коэффициент
BigInt::Rossi Handshakes::C(int n, int k)
{
  BigInt::Rossi dividend(1);
  BigInt::Rossi divisor(1);
  for (int i = 1; i <= k; ++i) {
    dividend = dividend * (n-i+1);
    divisor = divisor * i;
  }
  return dividend / divisor;
}

////////////////////////////////////////////////////////////////////////////////
// МЕТОД №3 (тоже числа Каталана для m = n/2)
// method3(n) = Cat(m) = 2*(2*m-1)/(m+1)*Cat(m-1)
// method3(2) = Cat(1) = 1
BigInt::Rossi Handshakes::method3(int n)
{
  BigInt::Rossi dividend(1);
  BigInt::Rossi divisor(1);
  for (int i = 1; i <= n/2; ++i) {
    dividend = dividend * (2*(2*i-1));
    divisor = divisor * (i+1);
  }
  return dividend / divisor;
}

////////////////////////////////////////////////////////////////////////////////
// Примерный асимптотический расчёт через числа Каталана для m = n/2
// approx(n) = Cat(m) = 4**m / (m**(3/2) * sqrt(pi))
// Вычтем ещё 1, чтобы получить точный результат хотя бы для n = 2, 4 и 6 :)
double Handshakes::approx(int n)
{
  int m = n / 2;
  return pow(4.0, m) / (pow(m, 1.5) * sqrt(M_PI)) - 1;
}

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

int main()
{
  std::vector<int> n = {2, 4, 6, 8, 10, 12, 16, 20, 32, 50, 100, 200, 500, 1000};
  Handshakes hs;
  for (int i = 0; i < n.size(); ++i) {
    int k = n[i];
#ifdef USE_METHOD1
    BigInt::Rossi n1 = hs.method1(k);
#endif
    BigInt::Rossi n2 = hs.method2(k);
    BigInt::Rossi n3 = hs.method3(k);
    std::cout << k << " = ";
    if (
#ifdef USE_METHOD1
        n1 == n2 && 
#endif
                    n2 == n3) {
      std::cout << n2.toStrDec();
    } else {
      std::cout << "error, different results!!! (" <<
#ifdef USE_METHOD1
                   "n1=" << n1.toStrDec() << ", " <<
#endif
                   "n2=" << n2.toStrDec() << ", n3=" << n3.toStrDec() << ")";
    }
    std::cout << ", approx = " << floor(hs.approx(k)) << std::endl;
  }
  return 0;
}

ConferenceDouble.cpp

#include <iostream>
#include <vector>
#include <math.h>

class Handshakes {
  private:
    std::vector<double> cache;
    double C(int n, int k);
  public:
    double method1(int n);
    double method2(int n);
    double method3(int n);
    double approx(int n);
};

/////////////////////////////////////////////////////////////////////////
// МЕТОД №1
// Пронумеруем позицию каждого человека за столом от 1 до n.
// Возьмём первого и переберём всех, кому он может протянуть руку.
// Очевидно, что это могут быть только те, кто сидит на чётных позициях
// (в т.ч. соседи), т.к. иначе кол-во сидящих слева и справа от него было
// бы нечётным, и эти люди не смогли бы пожать друг другу руки попарно.
// Для каждого такого случая посчитаем и перемножим кол-во вариантов
// рукопожатий для сидящих слева и справа через рекурсивный вызов, а
// все результаты (произведения) просуммируем. Это и будет ответом.
// Для ускорения работы функции результаты будем кешировать.
double Handshakes::method1(int n)
{
  if (n <= 2) { return 1; }
  int m = n/2;
  int idx = m-2;
  if (idx < cache.size() && cache[idx] != 0) { return cache[idx]; }
  double result = 0.0;
  for (int i = 0; i < m; ++i) {
    result += method1(i*2) * method1(n-2-i*2);
  }
//  while (idx > cache.size()) { cache.push_back(0); }
  cache.push_back(result);
  return result;
}

/////////////////////////////////////////////////////////////////////////
// МЕТОД №2
// Получившийся ряд чисел является рядом чисел Каталана для m = n/2
// method2(n) = Cat(m) = C(2*m,m)/(m+1) = C(n,n/2)/(n/2+1)
double Handshakes::method2(int n)
{
  return C(n, n/2) / (n/2+1.0);
}

// биномиальный коэффициент
double Handshakes::C(int n, int k)
{
  double result = 1.0;
  for (int i = 1; i <= k; ++i) {
    result *= (n-i+1.0) / i;
  }
  return result;
}

/////////////////////////////////////////////////////////////////////////
// МЕТОД №3 (тоже числа Каталана для m = n/2)
// method3(n) = Cat(m) = 2*(2*m-1)/(m+1)*Cat(m-1)
// method3(2) = Cat(1) = 1
double Handshakes::method3(int n)
{
  double result = 1.0;
  for (int i = 1; i <= n/2; ++i) {
    result *= 2*(2*i-1.0) / (i+1.0);
  }
  return result;
}

/////////////////////////////////////////////////////////////////////////
// Примерный асимптотический расчёт через числа Каталана для m = n/2
// approx(n) = Cat(m) = 4**m / (m**(3/2) * sqrt(pi))
// Вычтем ещё 1, чтобы получить точный результат хотя бы для n = 2, 4, 6
double Handshakes::approx(int n)
{
  int m = n / 2;
  return pow(4.0, m) / (pow(m, 1.5) * sqrt(M_PI)) - 1;
}

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

int main()
{
  std::vector<int> n = {2, 4, 6, 8, 10, 12, 16, 20, 32, 50, 100, 200, 500, 1000};
  Handshakes hs;
  for (int i = 0; i < n.size(); ++i) {
    int k = n[i];
    double n1 = hs.method1(k);
    double n2 = hs.method2(k);
    double n3 = hs.method3(k);
    std::cout << k << " = ";
    if (abs(n1/n2-1) < 1e-12 && abs(n1/n3-1) < 1e-12) {  // учитываем погрешности вычислений с плавающей запятой
      std::cout << n1;
    } else {
      std::cout << "error, different results!!! (n1=" << n1 << ", n2=" << n2 << ", n3=" << n3 << ")";
    }
    std::cout << ", approx = " << floor(hs.approx(k)) << std::endl;
  }
  return 0;
}

makefile

MAIN: Conference.o bigInt.o
	g++ -s bigInt.o Conference.o -o Conference.exe -Wall -O2
	del *.o
Conference.o: Conference.cpp
	g++ -c Conference.cpp -o Conference.o
bigInt.o: bigInt.cpp
	g++ -c bigInt.cpp -o bigInt.o