ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Doroshew                      2:5020/400     08 Apr 2002  08:42:37
 To : Alexey Zhivotov
 Subject : Re: Генерация чисел
 -------------------------------------------------------------------------------- 
 

 
 Alexey Zhivotov wrote:
 
 >  AZ>   Интересует алгоритм сабжа, но такой, чтобы в промежутке от 1 до n
 >  AZ> каждое число генерировалось только 1 раз. Только нормальный алгоритм,
 >  AZ> а не извраты с массивами.
 >   Люди, я забыл написать, что нужна *рандомная* генерация с вышестоящими
 > условиями.
 
 Так заметно интереснее.
 Мне кажется вполне подходящим алгоритм, базирующийся на Кнутовом, что-то
 там было такое про генерацию случайных чисел. С массивами :)
 
 Пункт первый. 
 Hужен источник всех чисел от 1 до n без повторений. Как писали
 предыдущие ораторы, ищем ближайшее сверху к n простое число. Выбираем
 подходящее k, меньшее n. Hапример n-1 или 2 не будет подходящим. Я думаю
 подойдёт k=[2/3n]. (целая часть)
 начиная от нуля, прибавляем k, от суммы берём остаток по модулю n, и так
 до нуля. Так мы сгенерируем все числа от 0 до n-1.
 
 Пункт второй.
 Сгенерированные числа из пункта первого записываем в массив А размера L,
 L<n
 
 1. старт
 пустой массив А заполняем числами.
 
 2. основная часть
 хорошим генератором ПСЧ генерируем число i, 0<=i<L.
 извлекаем из А[i]. на его место записываем очередное число из пункта
 первого, до тех пор, пока не используем все.
 
 3. финиш
 генерируем случайное число i, 0<=i<L.
 извлекаем из А[i].
 А сжимаем на один элемент, L=L-1 - что-то не придумывается хорошего
 метода укорачивания А
 до тех пор, пока А не кончится
 
 Искренне, Вам
 Andrew Doroshev 
  
 Другой вариант - если n-1 - простое, то берем 0, прибавляем любое число
 меньшее
 n-1 по модулю n-1, пока снова не получим 0. Числа от 1 до n получаются
 прибавлением 1 к каждому из полученных чисел.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Генерация чисел   Andrew Doroshew   08 Apr 2002 08:42:37   Re: Генерация чисел   Andrew Doroshev   09 Apr 2002 13:22:03