57 lines
2.7 KiB
Markdown
57 lines
2.7 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4db1000cf542c50ffee
|
|||
|
|
title: 'Задача 367: Сортування Бозо'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302028
|
|||
|
|
dashedName: problem-367-bozo-sort
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Сортування Бозо, яке не слід плутати з дещо менш ефективним сортуванням бого, полягає в тому, щоб перевірити, чи сортується вхідна послідовність, і якщо ні, замінити випадково два елементи. Це повторюється, поки послідовність не буде впорядкована.
|
|||
|
|
|
|||
|
|
Якщо ми розглянемо всі перестановки перших чотирьох натуральних чисел як вхідні дані, то очікуване значення кількості перестановок, усереднене для всіх вхідних послідовностей $4!$, буде $24.75$.
|
|||
|
|
|
|||
|
|
Вже відсортована послідовність займає 0 кроків.
|
|||
|
|
|
|||
|
|
У цій задачі ми розглядаємо наступний варіант сортування бозо.
|
|||
|
|
|
|||
|
|
Якщо послідовність не відсортована, ми вибираємо три елементи навмання і перемішуємо ці три елементи випадковим чином.
|
|||
|
|
|
|||
|
|
Всі $3! = 6$ перестановок цих трьох елементів однаково ймовірними.
|
|||
|
|
|
|||
|
|
Вже відсортована послідовність займає 0 кроків.
|
|||
|
|
|
|||
|
|
Якщо розглядати всі перестановки перших чотирьох натуральних чисел як вхідні, то очікуване значення кількості перестановок, усереднене для всіх вхідних послідовностей $4!$, становить $27.5$.
|
|||
|
|
|
|||
|
|
Вважайте вхідними послідовностями перестановки перших 11 натуральних чисел.
|
|||
|
|
|
|||
|
|
У середньому по всіх вхідних послідовностях $11!$, яку очікувану кількість перетасувань буде виконувати цей алгоритм сортування? Округліть свою відповідь до найближчого цілого числа.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`bozoSort()` повинен повернути `48271207`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(bozoSort(), 48271207);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function bozoSort() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
bozoSort();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|