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)] )""
# Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 31, а затем к получившейся перестановке верный алгоритм из задания 30. Будет ли полученное распределение на перестановках равномерным?# Рассмотрим следующий метод генерации случайной перестановки. Применим верный алгоритм из задания 30, а затем к получившейся перестановке алгоритм из задания 31. Будет ли полученное распределение на перестановках равномерным?
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
