|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 03 Jan 2003 03:58:20
To : Oleg Khovayko
Subject : Re: масив чисел
--------------------------------------------------------------------------------
Fri Jan 03 2003 02:39, Oleg Khovayko wrote to Evgenij Masherov:
OK> Я же еще 29 декабря в своем письме кидал
OK> сюда алгоритм перемешивания, не требующий
OK> ни доп. памяти, ни сортировки, и делающий
OK> перемешивание за 1 проход - за N().
OK> Или вы не получали сообщения, или читали не до конца?
OK> Hепонятно. Повторяю еще раз алгоритм перемешивания:
OK> int mas[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
OK> for(int i = 9; i > 0; i--) {
OK> int j = random() % i;
OK> int tmp = mas[j];
OK> mas[j] = mas[i];
OK> mas[i] = tmp;
OK> }
OK> Во, дешево и сердито...
Дешево. Сердито. И неверно. В том смысле, что равновероятность всех
перестановок не обеспечивается. Хотя если нужно только сделать некоторое
возмущение расстановки - может и сойти.
Похоже, что вообще гарантировать равновероятность менее чем за NlogN операций
не выйдет...
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
