İnsanlardan cütlər#11288

İnsanlardan cütlər (Həll təhlili)

Tutaq ki, $f (n)$ — bütün $n$ nəfərin rəqsə qoşulmasının müxtəlif yollarının sayıdır. Məsələn,

$f (1) = 1$ f(1) = 1, bir nəfər təkbaşına rəqs edir;
$f (2) = 2$ f(2) = 2, çünki iki nəfər üçün iki variant var: ya ayrı-ayrılıqda rəqs edirlər, ya da cütlüklə rəqs edirlər;

$n$ -ci şəxsi nəzərdən keçirək:

Əgər o tək rəqs edirsə, qalan $n - 1$ n - 1 nəfər rəqsə $f (n - 1)$ f(n - 1) yollarla qoşula bilər.
$n$ -ci şəxs $n - 1$ n - 1 nəfərdən hər hansı biri ilə cütlük ola bilər. Qalan $n - 2$ n - 2 nəfər rəqsə $f (n - 2)$ f(n - 2) yollarla qoşula bilər.

Beləliklə, belə bir əlaqə əldə edirik:

f (n) = f (n - 1) + (n - 1) \cdot f (n - 2)

f(n) = f(n - 1) + (n - 1) \cdot f(n - 2)

Misal

Tutaq ki, $n = 3$ n = 3 nəfər var. Onlar rəqsə $4$ yollarla qoşula bilərlər:

əgər üçüncü şəxs tək rəqs edirsə: ${1, 2, 3}, {{1, 2}, 3}$ \{1, 2, 3\}, \{\{1, 2\}, 3\};
əgər üçüncü şəxs cütlük rəqs edirsə: ${1, {2, 3}}, {2, {1, 3}}$ \{1, \{2, 3\}\}, \{2, \{1, 3\}\}.

Formulaya əsasən $f (3)$ hesablayaq:

f (3) = f (2) + 2 \cdot f (1) = 2 + 2 \cdot 1 = 4

f(3) = f(2) + 2 \cdot f(1) = 2 + 2 \cdot 1 = 4

Alqoritmin reallaşdırılması

Modul və nəticələri saxlamaq üçün massiv elan edək: $d p [n] = f (n)$ dp[n] = f(n).

#define MOD 1000000007
long long dp[100001];

Giriş olaraq $n$ oxuyuruq.

scanf("%d", &n);

$d p$ massivində ardıcıl olaraq $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n) dəyərlərini hesablayırıq.

dp[1] = 1; dp[2] = 2;
for (i = 3; i <= n; i++)
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD;

Cavabı çap edirik.

printf("%lld\n", dp[n]);

Python reallaşdırılması

Hesablama aparılacaq modul $M O D$ elan edək.

MOD = 1000000007

Giriş olaraq $n$ oxuyuruq.

n = int(input())

Nəticələri saxlamaq üçün siyahı elan edək: $d p [n] = f (n)$ dp[n] = f(n).

dp = [0] * (n + 1)

$d p$ massivində ardıcıl olaraq $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n) dəyərlərini hesablayırıq.

dp[1] = 1
if n > 1: dp[2] = 2
for i in range(3, n + 1):
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

Cavabı çap edirik.

print(dp[n])