|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 08 Apr 2002 09:04:14
To : Alexey Zhivotov
Subject : Re: Генерация чисел
--------------------------------------------------------------------------------
Sat Apr 06 2002 07:17, Alexey Zhivotov wrote to All:
AZ>> Интересует алгоритм сабжа, но такой, чтобы в промежутке от 1 до n
AZ>> каждое число генерировалось только 1 раз. Только нормальный алгоритм,
AZ>> а не извраты с массивами.
AZ> Люди, я забыл написать, что нужна *рандомная* генерация с вышестоящими
AZ> условиями.
Строго говоря, это противоречащие друг другу условия.
Так нельзя - либо случайные, либо неслучайные (каждое по разу).
Hо если очень хочется, то можно :
1. Если n=2^x, то с помощью генератора М-последовательности. Если
автокорреляция "одношагового" генератора не устраивает - бери не каждое
выходное значение, а каждое к-тое, где к - число, взаимно простое с 2^x-1.
2. Если n - простое число, то выбираем к < n и генерируем ряд чисел : 1, к,
(к^2) mod n, (к^3) mod n,... где каждое следующее получается из предыдущего
умножением на к по модулю n. Каждое_по_разу появится в силу китайской теоремы
об остатках.
3. Если n=2^x+1, то можно привлечь любой симметричный алгоритм шифрования с
длиной блока х битов. Выбираем (произвольно) ключ и зашифровываем им числа 0,
1, 2... Получаемые шифртексты по определению будут различны.
С уважением
Сергей
...я пью столько, сколько нужно чтобы чувствовать себя человеком(с)реклама
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
