İki rəqs#11602

İki rəqs (Həll təhlili)

Əvvəlcə birinci dairəvi rəqs üçün $n /2$ adamı seçməliyik. Bu $C_{n}^{n /2}$ C^{n/2}_n yolla edilə bilər. Bir dairəvi rəqs daxilində insanları düzəltməyin yollarını sayaq. Birinci olacaq şəxsi sabitləyirik, bundan sonra qalan $n /2 - 1$ n / 2 - 1 adam hər hansı bir qaydada düzülə bilər, yəni $(n /2 - 1)!$ (n / 2 - 1)! yolla. İki dairəvi rəqs formalaşdırma yollarının sayı:

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

C^{n/2}_n \cdot (n / 2 - 1)! \cdot (n / 2 - 1)!~/~2

Burada $2$ ilə bölmə lazımdır ki, biz dairəvi rəqs cütlərini $(x, y)$ və $(y, x)$ kimi fərqləndirməyək. Məsələn, $n = 4$ n = 4 olduqda, dairəvi rəqs bölmələri $([1, 2], [3, 4])$ ([1, 2], [3, 4]) və $([3, 4], [1, 2])$ ([3, 4], [1, 2]) eyni sayılır.

Verilmiş formulu sadələşdirərək, biz cavabı alırıq:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

\frac{n!}{(n/2)! \cdot (n/2)!} \cdot (n / 2 - 1)! \cdot (n / 2 - 1)!~/~2 = \\ \frac{1}{2} \cdot \frac{n!}{(n/2) \cdot (n/2)} = \frac{2 \cdot n!}{n \cdot n} = \frac{2 \cdot (n - 1)!}{n}

Nümunə

Məsələn, $n = 4$ n = 4 üçün yol sayı $3$ olacaq:

Birinci dairəvi rəqs — $[1, 2]$ , ikinci — $[3, 4]$ ;
Birinci dairəvi rəqs — $[2, 4]$ , ikinci — $[3, 1]$ ;
Birinci dairəvi rəqs — $[4, 1]$ , ikinci — $[3, 2]$ .

Formula görə $n = 4$ n = 4 üçün cavabdır

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

\frac{2 \cdot (4 - 1)!}{4} = \frac{12}{4} = 3

$4$ üçün bütün fərqlənən dairəvi rəqsləri qurmaq üçün. İştirakçı $1$ -i birinci mövqedə yerləşdiririk. Qalan üç mövqedə digər üç iştirakçının hər hansı bir permutasiyası yerləşdirilə bilər.

Bu tənzimləmələri dairə içində döndürməklə, fərqlənməyən dairəvi rəqslər əldə edə bilərik. Məsələn, bu tənzimləmələr fərqlənmir (son permutasiyanın dövrü dəyişməsi ilə nəzərdə tutulur):

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

[1, 4, 3, 2],~[2, 1, 4, 3],~[3, 2, 1, 4],~[4, 3, 2, 1]

4 iştirakçı ilə $4! = 24$ 4! = 24 dairəvi rəqs var. Ancaq, fərqlənən dairəvi rəqslərin sayı $n = 4$ n = 4 üçün $3! = 6$ 3! = 6.

Alqoritmin həyata keçirilməsi

fact funksiyası $n$ sayının faktorialını hesablayır.

long long fact(int n)
{
  long long res = 1;
  for (int i = 2; i <= n; i++)
    res *= i;
  return res;
}

C++

Programın əsas hissəsi. $n$ giriş dəyərini oxuyun.

scanf("%d", &n);

Nəticəni hesablayın və çap edin.

res = 2 * fact(n - 1) / n;
printf("%lld\n", res);

Python-da həyata keçirilməsi

fact funksiyası $n$ sayının faktorialını hesablayır.

def fact(n):
  res = 1
  for i in range(2, n + 1):
    res *= i
  return res

Programın əsas hissəsi. $n$ giriş dəyərini oxuyun.

n = int(input())

Nəticəni hesablayın və çap edin.

res = 2 * fact(n - 1) // n
print(res)