Случайные числа в программировании

    Из  изложенного следует, что метод  Монте-Карло тесно связан с задачами теории вероятностей, математической статистики и вычислительной математики. В связи с задачей моделирования  случайных величин (в особенности  равномерно распределённых) существенную роль играют также методы теории чисел. Среди других вычислительных методов, метод Монте-Карло выделяется своей простотой и общностью.

         Вихрь Мерсенна (Mersenne twister)

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

     Существуют, по меньшей мере, два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19937.

     MT 19937 имеет следующие свойства:

1.Он был разработан с целью иметь огромный период, размером 2¹⁹⁹³⁷ − 1.

2.Он значительно быстрее, чем все остальные генераторы.

3.Он статистически случаен во всех выходных битах.

     Вывод:

     Программные ГСЧ, не использующие внешних «источников энтропии» и формирующие очередное число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого ГСЧ выглядит как случайная, но на самом деле подчиняется некоторому закону и, как правило, рано или поздно зацикливается.  

    1.6.Области применения случайных чисел.

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

- тестирование  алгоритмов;

- имитационное  моделирование;

- некоторые задачи  численного анализа;

- имитация пользовательского  ввода.

     Моделирование, вот область, где в настоящее время потребляется большая часть всех вырабатываемых случайных чисел. Так как основой моделирования является модель, которая представляется в виде машинной программы, воспроизводящей важные черты изучаемого объекта. Для «питания» такой модели-программы вырабатывается большое количество случайных чисел, которые призваны воспроизвести явления реальной жизни. Криптография. Каждый генератор можно использовать как криптосистему с секретным ключом. Также, они являются идеальной моделью для блочных шифров.         Построение алгоритмов. Имеется ряд алгоритмов, использующих случайные биты. Имея генератор псевдослучайных чисел, мы могли бы брать лишь небольшое число случайных битов, а остальные получать, применяя к ним генератор. Алгоритм будет работать так же хорошо, т.к. иначе это дало бы возможность отличить случайные числа от псевдослучайных, что противоречит нашему предположению о существовании генератора [13, c.2].   Также очень часто используются случайные числа при программировании игр. Например, таких как «Сапер», «Тетрис» и др.

ГЛАВА 2.

СЛУЧАЙНЫЕ ЧИСЛА В PASCAL 

1. Генератор случайных чисел  в Pascal ABC

     В языке Pascal, как и во многих других языках, существует встроенная поддержка генератора случайных чисел. Для формирования чисел используется программный ГСЧ. Для генерации псевдослучайных чисел в заданных диапазонах используется функция random. Перед ее использованием обычно выполняется процедура инициализации датчика случайных чисел - randomize; иначе программа всегда будет выдавать один и тот же результат. Randomize задает начальное значение последовательности, от которого вычисляются все последующие. При каждом запуске программы это значение будет разным, а значит и результат работы функции random будет различным. Например, рассмотрим программу:

Program ran;

Var a:Real;

Begin

  Randomize;

  a:=Random;

  Writeln(a);

  Writeln(a:6:4);

  Readln;

End.

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

     Функция random генерирует случайное число в диапазоне от 0 (включительно) до единицы. Если в скобках указан аргумент, то от 0 до значения указанного в скобках (не включая само значение). Так выражение random (10), говорит о том, что будет получено любое число в диапазоне  [0, 10).

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

Program a2 ;

Var a,b:Integer;

Begin

  Randomize;

  a:=Random(1000);

  b:=Random(1000);

  Writeln('a=',a);

  Writeln('b=',b);

  If a>b Then Writeln(a,' > ',b)

         Else If a<b Then Writeln(a,' < ',b)

                      Else Writeln(a,' = ',b);

  Readln;

End.

     Используя эту программу, можно показать, что  получение значений случайным образом  не всегда эффективно. Практически  в этой программе никогда не получится, чтобы значения переменных а и b были равны. Поэтому в задачах, где требуется проверить некоторые особые случаи, значения переменных лучше вводить с клавиатуры.

     Если  требуется получать значения в каком-либо другом диапазоне (не от нуля), то прибегают  к математической хитрости. Например, чтобы получить случайное число  от -100 до 100 достаточно записать такое  выражение: random (200) – 100. В результате, сначала будет получено число из диапазона [0, 199], а затем из него будет вычтена сотня. И если случайное число было меньше 100, то результат выражения будет отрицательным. Также можно использовать выражение  random(100)- random(100)[8].

     Чтобы сгенерировать число из интервала [a,b] используют выражение random(b-a+1)+a;  

     Эффективно  использовать функцию  random  для получения случайных чисел при решении задач с массивами.

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

подпоследовательности.

Решение задачи. Вычисляются суммы:

1-й шаг: a1; a1+a0; a1+a2+a3; ...; a1+a2+...+an. Всего n сумм.

2 -й шаг: a2; a2+a3; a2+a3+a4; ...; a2+a3+a4+...+an. Всего n-1 сумма.

...

n-1-й шаг: an-1; an-1+an. Всего 2  суммы.

n-й шаг: an. Всего 1 сумма.

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

Program mass;

Uses Crt;

Type mas=array[1..50] of Integer;

Var a:mas; n,i,b,j,p,x,max,s:integer;

Begin

   ClrScr;

Randomize;

   Writeln('Вести количество элементов');

Readln(n);

   If n>50 Then n:=50;

   For i:=1 to n do a[i]:=Random(1000)-Random(1000);

   Writeln('Элементы массива');

   For i:=1 to n do Write(a[i]:5); //заполнение массива числами

   Writeln;

   max:=a[1]; p:=1; x:=1;// устанавливаем начальные значения для суммы,

   i:=1;                           //  и номера, с которого сумма максимальная

   While i<=n do    //перебор эл-тов массива для определения                         //подпоследовательности с максимальной суммой

          Begin

          s:=0;

          For j:=i to n do begin

              s:=s+a[j];

              If s>max

               Then begin

                      p:=i; x:=j; max:=s;

                       end;

                 end;

          i:=i+1;

   End;

  Writeln (max,'- максимальная сумма подпоследовательности, которая начинается с номера =',p,' и заканчивается номером=',x);

Readln;

End.

 

Если  обобщить, то

x:=random;      результатом будет числа от 0.000....01 до 1.  
x:=random(N) ;   результат 1,2,3,4,5,6,….N

x:=random(b-a+1)+a;   результат число из диапазона [a;b]

Приведем  пример использования функции random при использовании графического режима.

Пример. Заполнение экрана точками со случайными координатами разного цвета.

uses GraphABC;

var i,j: integer;

begin

SetWindowSize(300,300);// устанавливаем размер окна

  for j:=0 to 90000 do

    SetPixel(Random(WindowWidth),Random(WindowHeight),clRandom);

end.

     Процедура SetPixel  закрашивает один пиксель с координатами (x,y) цветом. Где х, у и цвет  выбираются случайным образом

     2.2. Рассмотрение примеров.

     Случайные числа эффективно работают при программировании игр.

Пример  игры «Угадай число»

 Суть  игры: отгадать целое число, которое «загадал» компьютер в определенном диапазоне.

Описание  переменных: 

a – число, "загаданное" компьютером; 
b – очередное число, вводимое пользователем.

     Алгоритм  решения задачи: 

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

     Пока  число a не совпадет с числом b, пользователю будет предлагаться ввести очередное число. При этом, если b > a, то на экран будет выдаваться сообщение "Много". Иначе будет проверяться условие b < a. При его положительном значении появится сообщение "Мало", иначе сообщение "Угадал".

     Не  трудно понять, что если b не больше и не меньше a, то значит оно равно a. В таком случае логическое выражение при while вернет false, и цикл прервется.

Программа на языке Паскаль: 

var

    a,b: integer;  

begin

    randomize;

    a := random(100);  

 while a <> b do begin

        write('Введи число: ');

        readln(b);

        if b > a then

            writeln('Много')

        else

            if b < a then

                writeln('Мало')

            else

                writeln('Угадал');

    end; 

readln

end.

   Примечания– Угадать число всегда можно не более чем через 6-7 попыток, если делить каждый оставшийся диапазон пополам.

     Пример  применения «метода Монте-Карло».     Приближенно вычислить площадь фигуры с применением метода Монте-Карло. Суть метода заключается в следующем: помещаем фигуру F в квадрат. Наугад (случайным образом) бросать точки в этот квадрат. Естественно предполагая, что чем больше площадь фигуры, тем чаще в нее будут попадать точки. Таким образом, можно сделать допущение: при большом числе точек, наугад выбранных внутри квадрата, доля точек, содержащихся в F, приближенно равна отношению площади F к площади квадрата. Несложно видеть, что исходными данными являются сторона а квадрата, содержащего фигуру F, и количество точек kw, которые мы будем случайным образом выбирать внутри квадрата. Результатом является площадь S фигуры F. Если через kr обозначить число тех наугад выбранных точек, которые содержаться в фигуре F, то площадь S приближенно равна

        
Применяя эту модель для приближенного вычисления числа π путем нахождения площади круга радиуса R=1. Формула площади круга известна:

                                              S = π*R                                           (1.4)

при R=1 площадь S численно равна π. Квадрат для такого круга получается со стороной, а=2. Площадь квадрата равна 4. Тогда площадь фигуры F будет  равна.