Обход

From

Max Alekseyev (2:5015/60)

To

Valery Krigan

Date

2000-03-01T20:31:54Z

Area

RU.ALGORITHMS

Hi, Valery !

Replying to a message of Valery Krigan to All:

 VK> Задача: перебрать без повторения все числа из большого
 VK> интервала в порядке, "похожем" на случайный.
 VK> Комментарий: _большой_ значит невозможность
 VK> запоминания _всех_ уже использованных чисел.

================================= Алгоритмы ==================================
   From: Max Alekseyev                   2:5015/60       05 Aug 1998  23:04:22
     To: Oleg Koulaboukhov        
   Subj: Точки                                                                  
==============================================================================
Hi, Oleg !

Replying to a message of Oleg Koulaboukhov to All:

 OK> Дан экран. Как его можно закрыть точками в псевдопроизвольном порядке,
 OK> не попадая на одну и ту же точку? Есть формула? Т.е. чтобы циклом от
 OK> 1 до 1000000 y меня беспорядочно точками было закрыто поле 1000х1000?
 OK> Использование супермассива исключено.

Рассмотрим первое простое большее 1000000. Это число n=1000003. Числа 
1,2,...,1000000 будем рассматривать как элементы поля F_n=Z/nZ. Рассмотрим 
произвольный первообразный корень, например, k=148569. Соответственно, числа 
k^1,k^2,k^3,...,k^1000002 дают все числа от 1 до 1000002 в каком-то 
псевдослучайном порядке.

Итак, если пропустить всякие заумные слова, берешь n=1000003, k=148569 и строишь 
следующую рекуррентную последовательность

x_1=k, 
x_{i+1}=x_i*k mod n

Получаешь последовательность чисел x_1, x_2, ..., x_{1000002}, в которой только 
2 "плохих" числа: 1000001 и 1000002 (которые ты просто игнорируешь), а все 
остальные - это как раз числа от 1 до 1000000 в некотором псевдослучайном 
порядке.

Regards,      °°
        Max    ~
==============================================================================

Regards,      °°
        Max    ~

--- OS/2 Uptime:  0d 0h 52m 29s 39ms
 * Origin: Девушка, у Вас большая грудь - Вы далеко пойдете... (2:5015/60)