Dairəvi masa#11679

Dairəvi masa (Həll təhlili)

Sıra ilə əyləşmə ilə müqayisədə, dairəvi masanın sabit başlanğıcı yoxdur. Bu səbəbdən, yalnız siklik şəkildə fərqlənən hər bir düzülüş eyni hesab olunur.

Əgər insanlar sırayla əyləşdirilsəydilər, müxtəlif insanların istənilən sıralamasını əldə etmək üçün $n!$ qədər üsul olardı.

Dairəvi masa üçün isə, hər bir konkret yerləşdirməni $n$ üsulla çevirərək $n$ ekvivalent lineer permütasiyalar ala bilərik.

Məsələn, $(1, 2, 3, 4)$ (1, 2, 3, 4) yerləşdirməsi üçün çevrilmələr belədir:

(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)

(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)

Bütün bu düzülüşlər eyni hesab olunur.

Nəticədə, hər bir unikal dairəvi düzülüş dəqiq $n$ lineer permütasiyaya uyğun gəlir.

Dairəvi masa ətrafında müxtəlif əyləşdirmələrin sayını tapmaq üçün ümumi permütasiya sayını ekvivalent çevrilmələr sayına bölməliyik:

\frac{n !}{n} = (n - 1)!

\frac{n!}{n} = (n - 1)!

Misal

$4$ şəxs üçün $6$ müxtəlif düzülüş mövcuddur:

$(1, 2, 3, 4)$ (1, 2, 3, 4)
$(1, 2, 4, 3)$ (1, 2, 4, 3)
$(1, 3, 2, 4)$ (1, 3, 2, 4)
$(1, 3, 4, 2)$ (1, 3, 4, 2)
$(1, 4, 2, 3)$ (1, 4, 2, 3)
$(1, 4, 3, 2)$ (1, 4, 3, 2)

Digər hər hansı düzülüş, dönüşlər vasitəsilə göstərilənlərdən birinə çevrilə bilər. Məsələn, $(4, 2, 1, 3)$ (4, 2, 1, 3) düzülüşü $(1, 3, 4, 2)$ (1, 3, 4, 2) düzülüşünə ekvivalentdir.

Alqoritmin reallaşdırılması

Giriş dəyərini $n$ oxuyuruq.

scanf("%lld", &n);

$R es$ dəyişənində cavabı hesablayırıq.

res = 1;
for (i = 1; i < n; i++)
  res = res * i;

Cavabı çıxışa veririk.

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