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