IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Как правильно перемешивать массивы, получение случайного распределения в массиве
TarasBer
сообщение 2.08.2011 10:44
Сообщение #1


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Есть задача - надо получить набор случайно перемешанных чисел от 1 до n.
Как её решить?
Наивный алгоритм: добавлять в новый массив случайное число от 1 до n, каждый раз проверяя, не входит ли оно уже в массив:


for i := 1 to n do begin
repeat
candidat := random(n) + 1; // от 1 до n
can := true;
for j := 1 to i-1 do if ARR[j] = candidat then begin
can := false;
break;
end;
until can;
ARR[i] := candidat;
end;


Этот алгоритм плох тем, что для подбора последнего, например, элемента придётся прогонять цикл в среднем n раз - ведь у нас все номера уже заняты, кроме одного, поэтому вероятность того, что мы попадём на этот один элемент, равна 1/n.
Для предпоследнего придётся делать в среднем n/2 попыток, так что можно посчитать алгоритмическую сложность такого метода, она будет n+n/2+n/3+...+n/n ~ n*log(n)
К тому же есть цикл, у которого условие выхода определяется исходя из значения случайной величины, а значит, есть возможность, что из-за несовершенства ГСЧ цикл никогда не завершится.

Есть старый алгоритм, который намного лучше.
Составляем упорядоченный массив, потом последний элемент меняем с любым, предпоследний меняем с любым, кроме последнего, предпредпоследний - с любым, кроме последнего и предпоследнего, и так далее.


for i := 1 to n do ARR[i] := i;
for i := n downto 2 do begin // первый трогать нет смысла
j := random(i)+1; // от 1 до i, значение i тоже допустимо
swap(i,j); // меняем местами элементы, стоящие на итом и на житом местах
end;


Алгоритмическая сложность - O(n).

Данный метод можно применять и для генерации поля в сапёре - пронумеровать ячейки числами от 1 до кол-ва ячеек (n), перемешать номера, поставить бомбы на те клетки, в которых номера не больше, чем кол-во бомб (m).

Можно чуть оптимизировать: без перемешивания поставить бомбы только на последние m клеткок, потом применить алгоритм перемешивания, но прогонять только от n до n-m+1. Можно посчитать вероятность наличия бомбы в любой клетке, она окажется ровно m/n.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 28.03.2024 17:47
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"