Re: Разминка... :))
От: MichaelP  
Дата: 05.02.02 19:01
Оценка:
Здравствуйте KAY, Вы писали:

KAY>Народ, задачка для досуга...(и мне заодно поможете)

KAY>Есть таблица ASCII, есть массив char[256]...
KAY>Как рандомно (случ.образом) и быстро
KAY>заполнить все эелементы массива всеми
KAY>элементами таблицы.
KAY>Заранее спасибо!!! :shuffle:

Данная задача называется "Генерация случайных перестановок (random permutations)" и она не так проста как кажется с первого взгляда. Тут есть два основных подводных камня.

1. Пререстановки должны быть действительно случайные, т.е. все перестановки (при идеальном генераторе случайных чисел) должны быть равновероятны. Некоторые из привиденных здесь алгоритмов этому критерию явно не удовлетворяют.
К счастью есть достаточно простые алгоритмы (см. Кнута или поиском по интернету) генерации случайных престановок.
2. Гораздо более серьезный. Используя стандартные генераторы случайных чисел (ГСЧ) мы принципиально можем получить только некоторое подмножество перестановок. Так, если ГСЧ инициируется одним числом ивыдает 16-и битные числа, то мы можем получить не больше чем 2^16 перестановок, что значительно меньше чем 256!(! -это факториал).
Простой расчет показывает что разрядность (как минимум начального числа для ГСЧ) должна быть не меньше 1168 бит, а желательно и побольше. Но как написать такой ГСЧ и откуда брать начальное значение — это уже тема отдельного большого разговора.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.