Gözlənilən minimal dərəcə#11262

Gözlənilən minimal dərəcə (Həll təhlili)

$x$ fərqli tam ədədi $n$ ədədindən seçmək $C_{n}^{x}$ C_n^x üsulla mümkündür.

Gəlin baxaq, minimum elementi $i$ olan $x$ ədədli neçə fərqə qrupları var. Bunun üçün fərqə mütləq $i$ ədəd daxil edilir və $x - 1$ x - 1 ədəd seçilir ki, onların hər biri $i$ -dən mütləq böyüktür. $i$ -dən böyük olan $n - i$ n - i ədəd var və bunlardan $x - 1$ x - 1 ədədi seçmək $C_{n - i}^{x - 1}$ C_{n-i}^{x-1} üsulla mümkündür.

Qeyd edək ki, $i + x - 1 \leq n$ i + x - 1 \le n qeyri-bərabərliyi təmin olunmalıdır, çünki əgər $i$ -dən böyük $x - 1$ x - 1 ədəd seçmək mümkün olmur. Bundan $i \leq n - x + 1$ i \le n - x + 1 məhdudiyyətini çıxara bilərik.

$2^{S}$ 2^S böyüklüyünün gözlənilən dəyərini hesablamaq üçün bu böyüklüyün bütün mümkün fərqələr üzrə orta çəkili qiymətini tapmalıyıq:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}

Əgər $i > n - x + 1$ i > n - x + 1, onda müvafiq fərqələrin sayı 0 qəbul olunur.

Misal

Birinci testdə yeganə seçim mümkündür: ${1, 2, 3, 4}$ \{1, 2, 3, 4\}. Minimum element $1$ olduğu üçün axtarılan dəyər $2^{1} = 2$ 2^1 = 2 bərabərdir.

İkinci testdə üç bərabər ehtimallı seçim var: ${1, 2}$ , ${1, 3}$ və ${2, 3}$ . Müvafiq $S$ dəyərləri $1$ , $1$ və $2$ -dir. Belə ki, $2^{S}$ 2^S böyüklüyünün orta qiyməti

(2^{1} + 2^{1} + 2^{2}) /3 = 8/3 = 2.6666666

(2^1 + 2^1 + 2^2) / 3 = 8 / 3 = 2.6666666

Bu dəyəri formula əsasında hesablayaq:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{2 ^{1} \cdot C _{2}^{1} + 2 ^{2} \cdot C _{1}^{1}}{C _{3}^{2}} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{2^1 \cdot C_2^1 + 2^2 \cdot C_1^1}{C^2_3} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

Algoritmin Reallaşdırılması

Cnk funksiyası binomial əmsalı $C_{n}^{k}$ C_n^k dəyərini hesablamaq üçün istifadə olunur. Binomial əmsalların qiymətləri $d p$ massivinin hüceyrələrində saxlanacaq.

long long dp[51][51];

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

C++

Proqramın əsas hissəsi.

scanf("%d %d", &n, &x);
memset(dp, -1, sizeof(dp));

Cavabı hesablamaq üçün: $\frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}$ \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}.

a = 0;
for (i = 1; i <= n - x + 1; i++)
   a = a + Cnk(n - i, x - 1) * (1LL << i);
res = 1.0 * a / Cnk(n, x);

Cavabı çıxış edin.

printf("%lf\n", res);