![]() |
![]() ![]() |
![]() |
TarasBer |
![]()
Сообщение
#1
|
![]() Злостный любитель ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: ![]() ![]() ![]() |
Есть задача - надо получить набор случайно перемешанных чисел от 1 до n.
Как её решить? Наивный алгоритм: добавлять в новый массив случайное число от 1 до n, каждый раз проверяя, не входит ли оно уже в массив:
Этот алгоритм плох тем, что для подбора последнего, например, элемента придётся прогонять цикл в среднем n раз - ведь у нас все номера уже заняты, кроме одного, поэтому вероятность того, что мы попадём на этот один элемент, равна 1/n. Для предпоследнего придётся делать в среднем n/2 попыток, так что можно посчитать алгоритмическую сложность такого метода, она будет n+n/2+n/3+...+n/n ~ n*log(n) К тому же есть цикл, у которого условие выхода определяется исходя из значения случайной величины, а значит, есть возможность, что из-за несовершенства ГСЧ цикл никогда не завершится. Есть старый алгоритм, который намного лучше. Составляем упорядоченный массив, потом последний элемент меняем с любым, предпоследний меняем с любым, кроме последнего, предпредпоследний - с любым, кроме последнего и предпоследнего, и так далее.
Алгоритмическая сложность - O(n). Данный метод можно применять и для генерации поля в сапёре - пронумеровать ячейки числами от 1 до кол-ва ячеек (n), перемешать номера, поставить бомбы на те клетки, в которых номера не больше, чем кол-во бомб (m). Можно чуть оптимизировать: без перемешивания поставить бомбы только на последние m клеткок, потом применить алгоритм перемешивания, но прогонять только от n до n-m+1. Можно посчитать вероятность наличия бомбы в любой клетке, она окажется ровно m/n. -------------------- |
![]() ![]() |
![]() |
Текстовая версия | 8.09.2024 7:48 |