Псевдослучайные числа. Функция, возвращающая значение и меняющая параметр

Задача

Написать функцию, генерирующую случайные числа.

Решение

 

Рассмотрим такую программу:

var s, i: integer;
 
function next(var seed: integer): integer;
    const
        multiplier = 37;
        increment = 3;
        cycle = 64;
    begin
        next := seed;
        seed := (multiplier * seed + increment) mod cycle
    end;
 
begin
    s := 16;
    writeln(next(s));
    writeln(next(s));
    writeln(next(s));
    writeln(next(s));
 
    s := 16;
    for i := 1 to 64 do
        write(next(s):3);
 
readln
end.

 

Примечания: 

Использование var в заголовке – необычный прием для функции.

Будучи вызвана с параметром s, содержащим число 16, эта функция возвращает число 16. Вместе с тем, возвращая 16, функция изменяет значение, хранящееся в переменной seed (илиs), на 19. Если функцию вызвать снова, с полученным значением s, то она возвратит число 19 и изменит значение s на 2. Продолжая вызывать функцию next, получим определенную последовательность целых чисел, начинающуюся с исходного значения s (цикл for).

Замечательным свойством этой последовательности является то, что каждое значение от 0 до 63 встречается в ней один раз. Более того, шестьдесят пятый вызов функции next дает число 16 и начинается новый цикл. Другими словами, начиная с любого желаемого целого, функция генерирует фиксированную перестановку чисел от 0 до 63.

Такой прием используется преимущественно для генерации "случайных" чисел (правильнее их называть псевдослучайными – чтобы подчеркнуть их предсказуемость). Цикл из 64 чисел, конечно, слишком мал; Грогоно предлагает константы для генерации перестановки чисел от 0 до 65 535:

const multiplier = 25173; increment = 13849; cycle = 65536;

Подбор констант с нужными свойствами – нетривиальная задача.

Приведенная выше функция возвращает значение и изменяет значение параметра. Такой способ действий применяется нечасто. В большинстве функций нет необходимости изменять параметры, и, следовательно, нет смысла использовать слово var в заголовке.

 

Тема

Процедуры, функции, рекурсии

Уровень

Простые задачи