Случайные числа
Создание: 04.03.2013
Получение случайных чисел - интересная теоретическая и одновременно важная практическая задача. От того насколько случайные числа «случайны» зависит, например, стойкость крипто-алгоритмов. Изучения случайных чисел в школе ограничивается в лучшем случае двумя функциями random() и randomize. Исправим эту ситуацию.

Как получить случайное число?

1.

Предположим, что у нас есть машина, которая показывает нам числа от нуля до девяти: 2, 4, 3, 0, 2, 9, 4, 5, 9, 5, 9, 7, 8, 2 и т.д. Случайны ли они? Вопрос непростой, ведь даже если подряд следует десять семерок это может быть последовательностью, а может быть просто совпадением!

Для того, чтобы ответить на наш вопрос строят диаграмму распределения при достаточно большом количестве чисел. Если для тысячи чисел диаграмма такая, как на рис 1.1, то ясно, что числа неслучайны, семерка встречается чаще остальных. Если распределение такое как на рис. 1.2, такое распределение с большей вероятностью можно назвать случайным, а распределение, показанное на рисунке 1.3, мы будем называть случайным.


случайное распределение 1000 чисел от 0 до 9

Нужно понимать, что определение не строгое. Числа 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 и далее по кругу будут давать третью картинку, но, конечно случайными не являются.

2.

В жизни мы встречаемся со случайными процессами, например, падение монетки орлом вверх. Имея монетку легко построить нормальное случайное число (это означает, что оно лежит в промежутке от 0 до 1). Алгоритм такой:

  1. Берем единичный отрезок и делим его пополам.
  2. Бросаем монетку и смотрим, что выпало, если орел, то выбираем правый отрезок, если решка - левый.
  3. С выбранным отрезком повторяем шаги 1-2 еще n раз.

В результате 10 бросков идеальной монеты мы получим отрезок равный 1 / 210 от исходного посередине нашего отрезка и будет искомое случайное число.

3.

Из нормального числа можно получить случайное число на любом промежутке. Для этого надо полученное число умножить на K (тем самым единичный отрезок увеличится в K раз и превратится в (0;K).

После этого к полученному числу нужно прибавить M (тем самым сдвигая отрезок от нуля на M.

На практике если нам нужно получить случайное число в диапазоне от 20 до 70 нужно выполнить операцию a:=random*50 + 20; Если нужну целые числа в этом же диапазоне используем команду b:=random(11)*5 + 20;

4.

К сожалению, компьютер - устройство работающее по заранее заданной программе, это значит, случайные числа формируются по заранее заданному алгоритму. Поэтому числа, формируемые компьютером называются псевдослучайными. Они похожи на случайные, показывают близкое к случайному распределение, но все же не случайны, с определенным шагом (очень большим) числа повторяются. Во всех алгоритмических способах чиcло An является некоторым преобразованием An-1. Иными словами каждое последующее псевдослучайное число строится из предыдущего. Найдено несколько псевдослучайных алгоритмов.

Алгоритмы получения псевдослучайных чисел

метод серединных квадратов

Имеется четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее из R1 берется середина (четыре средних цифры), это — новое случайное число, оно записывается в R0. Затем эта процедура повторяется многократно. Недостатком этого способа является его вырождаемость. Так если на каком, то шаге R0 превратится в 0, то и все последующие числа станут равными нулю

метод серединных произведений

Число R0 умножается на R1, из полученного результата R2 извлекается середина R2* (это очередное случайное число) и умножается на R1. По этой схеме вычисляются все последующие случайные числа.

Метод перемешивания

Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R0. Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R0*. Точно так же, циклически сдвигая содержимое ячейки R0 вправо на 1/4 длины ячейки, получаем второе число R0**. Сумма чисел R0* и R0** дает новое случайное число R1. Далее R1 заносится в R0, и вся последовательность операций повторяется.

Линейный конгруэнтный метод

Самый сложнопроизносимый и самый простой для понимания, и, одновременно, самый быстрый. Случайное число вычисляется по формуле:

ri + 1 = mod(k · ri + bM).

M — модуль (0 < M);

k — множитель (0 ≤ k < M);

b — приращение (0 ≤ b < M);

r0 — начальное значение (0 ≤ r0 < M).


Вся хитрость в правильном подборе параметров M, k b r

Например. генератор случайных чисел формируемых на основе чисел:

M = 231 – 1
k = 1 220 703 125
b = 7
r0 = 7

будет выдавать случайные неповторяющиеся числа с периодом, равным 7 миллионам.

Практическая часть

На уроке эта теория может быть проверена. На основе идеи изучения случайности чисел можно выполнить ряд практических заданий:

1.

Получить случайные числ в среде электронных таблиц методом серединных квадратов.

Формула для получения псевдослучайного числа в ячейке B2=ЗНАЧЕН(ПРАВСИМВ(ЛЕВСИМВ(ТЕКСТ(A1*A1;"########");6);4))

Через какое количество шагов выродится первоначальное число 1234?

Создайте программу, которая будет формировать псевдослучайные числа по этому методу. Определите через сколько шагов повторится первое псевдослучайное число 1024?

подобное задание можно выполнить и для других методов.

2.

Написать программу, определяющую частоту встречи чисел 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 полученных с помощью стандартной функции random() для n случайных чисел. n=1000, 10 000, 100 000, 1 000 000.


Программа, запущенная в среде Pascal ABC

Построить диаграмму на основании которой сделать вывод можем ли мы считать функцию качественным генератором псевдослучайных чисел?

 

статистическая обработка данных в MS Excel

Скачать материалы: