Я столкнулся с этой проблемой на сайте, и я совсем не могу понять вывод, пожалуйста, помогите мне понять это: -Сортировка Алгоритм: Выход
Bogosort, является немым алгоритмом, который перемешивает последовательность случайным образом до тех пор, пока не будет отсортирован , Но здесь мы немного изменили его, так что, если после последнего перетасования несколько первых элементов попадут в нужные места, мы их исправим и не перетасуем эти элементы. Мы сделаем то же самое для последних элементов, если они находятся в правильных местах. Например, если начальная последовательность (3, 5, 1, 6, 4, 2), и после одного тасования мы получаем (1, 2, 5, 4, 3, 6), мы будем сохранять 1, 2 и 6 и продолжать с сортировкой (5, 4, 3) с использованием того же алгоритма. Рассчитайте ожидаемое количество перетасовки для улучшенного алгоритма для сортировки последовательности первых n натуральных чисел, учитывая, что вначале ни один элемент не находится в правильных местах.
Входной сигнал:
2
6
10
Выход:
2
1826/189
877318/35343
Для каждого теста вывести ожидаемый объем перетасовки, необходимую для улучшенного алгоритма сортировки последовательности первых п натуральных чисел в виде неприводимые дроби. Я просто не могу понять выход.
Как насчет ввода? Является ли начальная последовательность (2, 6, 10)? Это уже отсортировано ... –
@SimeonVisser: 2 означает, что вход будет содержать первые 2 натуральных числа, но несортированный отрыв аналогично 6 означает 1-е 6 натуральных чисел –
Могут ли выходные значения быть рациональными числами? То есть он говорит, что ожидаемое количество модифицированных богосортов, необходимых для получения [1,2,3,4,5,6] в порядке, составляет 186/189 ~ = 9,66 раз? Я не могу придумать хороший способ рассчитать ожидаемые значения, поэтому я не могу проверить это значение, но первое значение, 2 - правильный ответ для последовательности [1, 2] (это '1 + sum (1/n^2 для n в 1.infinity)). – Blckknght