210
правок
Изменения
Нет описания правки
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
# Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 3132, а затем к получившейся перестановке верный алгоритм из задания 3031. Будет ли полученное распределение на перестановках равномерным?# Рассмотрим следующий метод генерации случайной перестановки. Применим верный алгоритм из задания 3031, а затем к получившейся перестановке алгоритм из задания 3132. Будет ли полученное распределение на перестановках равномерным?
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
