Алгоритм Неймана

Теоретические сведения.

Моделирование случайных процессов активно применяется в научных разработках, при построении различных моделей, создании компьютерных игр и т.д.

Важную роль при этом играют методы генерации случайных или, вернее, псевдослучайных чисел. Одним из таких методов является алгоритм Неймана.

Алгоритм Неймана

Получение последовательности равномерно распределенных в диапазоне 0 – 1 чисел g_i

1) взять произвольное число из 2*r цифр (не обязательно десятичных);

2) возвести в квадрат;

3) у квадрата этого числа оставить 2r средних цифр - т.е. отбросить первые r или r-1 первых и r последних;

4) полученное число (опять же из 2*r или 2*r – 1 цифр) возвести в квадрат.

5) повторить процедуру

Случайные числа gi получаются умножением полученных на шаге 3, каждого этапа чисел на 10 – 2r.

НАПРИМЕР:

пусть r =1; начальное число 46; g1 = 0.46; 462 =2116…
т. е. 46 → 2116 (11) →121(12)→ 144(14)→ 196(19) → 361(36)…
g = 0.46 → 0.11 → 0.12 → 0.14 → 0.19 → 0.36…

Недостатки алгоритма Неймана и пути их устранения.

При определенных начальных условиях алгоритм «зацикливается» - начинает выдавать короткие регулярные цепочки повторяющихся чисел (или даже все время одно и то же число).

Эту ситуацию нужно отслеживать и вносить в сгенерированное число какую-либо, разбивающую регулярную последовательность корректировку.

Задание:

1) Разработать программную реализацию алгоритма Неймана. Число r и начальное число задается пользователем.

2) Придумать и реализовать эвристическое правило для выхода из «зацикливания». Проверить работоспособность полученного модифицированного алгоритма Неймана на различных начальных данных.