Способы получения случайных чисел в программировании и их использование для решения ряда задач. Принцип действия и тестирование работы генератора случайных чисел в Borland C , его преимущества. Генерация одномерной и двумерной случайной величины.
В программировании достаточно часто находят применение последовательности чисел, выбранных случайным образом из некоторого множества. В качестве примеров задач, в которых используются случайные числа, можно привести следующие: - тестирование алгоритмов; В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность» значений при считывании.Последовательности случайных чисел, формируемых тем или иным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должны выбираться из определенного множества (чаще всего это действительные числа в интервале от 0 до 1 либо целые от 0 до N). Во-вторых, последовательность должна подчиняться определенному распределению на заданном множестве (чаще всего распределение равномерное).Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Будем последовательно генерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. При достаточно большом числе таких экспериментов отношение числа точек NF, удовлетворяющих неравенствам, к общему числу сгенерированных точек NR показывает долю площади прямоугольника, которую занимает фигура.Почти повсеместно используемый метод генерирования псевдослучайных целых чисел состоит в выборе некоторой функции f, отображающей множество целых чисел в себя. Число xk часто называется зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ и следующее генерируемое значение. Например, f(x) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62-разрядного квадрата числа x (модификация метода средин квадратов). Дальнейшее использование теории чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел. Очевидно, функция f(x) должна быть определена на всем отрезке [0; 1] и иметь на этом отрезке непрерывную область значений [0; 1], в противном случае генерируемые числа будут составлять лишь несобственное подмножество указанного отрезка. а) б)Достаточно часто возникает необходимость сгенерировать последовательность случайных чисел yi, равномерно распределенных на данном конечном интервале [a, b], с помощью ГСЧ, выдающего числа xi на интервале [0, m]. Приведение диапазона ГСЧ к нужному интервалу в этом случае осуществляется простым линейным преобразованием: . Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис.2, а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки: , где uj - равномерно распределенное случайное число из отрезка [0, m]. Таким образом, декартовы координаты очередной точки можно вычислить следующим образом: . где uj - равномерно распределенное случайное число из интервала (0, m); r - радиус окружности. При этом будем выбирать угол ? равномерно распределенным на интервале (0; 2?), а распределение ? построим следующим образом: , где x - равномерно распределенная на отрезке [0; 1] случайная величина.Качество ГСЧ в значительной мере влияет на результаты работы программ, использующих случайные числа. Поэтому все применяемые генераторы случайных чисел должны пройти перед моделированием системы предварительное тестирование, которое представляет собой комплекс проверок по различным стохастическим критериям, включая в качестве основных тесты на равномерность, стохастичность и независимость (рассматриваются только ГСЧ с равномерным распределением). Выдвигается гипотеза о равномерности распределения чисел (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi c вероятностью , , попадет в один из подынтервалов. Так как случайные числа a и b в данной последовательности независимы и принадлежат последовательности {xi}, равномерно распределенной на интервале (0, 1), то теоретическая вероятность появления серии длиной j в N опытах (под опытом здесь понимается генерация числа xi и проверка условия xi <p) определится формулой Бернулли: , , .Выдайте на экран 10 случайных равномерно распределенных чисел в диапазоне: От 3 до 12, целые.Написать функцию генерации случайной точки в двумерном круге с параметрами r, x0, y0.Постройте случайную последовательность плотностью распределения которой
План
Содержание
1. Способы получения случайных чисел 3
2. Характеристики ГСЧ 5
3. Применение ГСЧ 6
4. Генерирование равномерно распределенных случайных чисел 9
5. Генерирование чисел с произвольным распределением 12
6. Тестирование ГСЧ 17
7. Генератор случайных чисел в Borland C 21
8. Практические задания 23
8.1 Случайные числа в заданном диапазоне 23
8.2 Двумерные случайные величины 23
8.3 Генерация одномерной случайной величины 23
8.4 Оценить вероятность. 23
8.5. Медианы треугольника. 24
9. Лабораторные задания 25
9.1 ГСЧ фон Неймана 25
9.2 Случайная матрица 25
9.3 Площадь фигуры 26
9.4 Случайная величина с заданными свойствами 26
10. Дополнительные задания 27
10.1 Многомерные случайные величины 27
10.2 Быки и коровы 27
Библиографический список 28
1. Способы получения случайных чисел
Список литературы
1. Керниган Б. Язык программирования Си: Задачи по языку Си. / Б. Керниган, Д. Ритчи, А. Фьюэр М.: Финансы и статистика, 1985. - 192 с.
2. Керниган Б., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 1992. - 272 с.
3. Подбельский В.В., Фомин С.С. Программирование на языке Си. Учеб. пособие. М.: Финансы и статистика, 2004. 600 с.
4. Форсайт Дж. Машинные методы математических вычислений / Дж. Форсайт, М. Малькольм, К. Моулер. М.: Мир, 1980. - 279 с.
5. Кнут Д. Искусство программирования, том 2. Получисленные методы / Д. Кнут. М.: Изд. дом «Вильямс», 2007. 832 с.
6. Каханер Д. Численные методы и математическое обеспечение: Пер. с англ. / Д. Каханер, К. Моулер, С. Нэш. М.: Мир, 1998. - 575 с., ил.
7. Зубинский А. В поисках случайности // А. Зубинский. Компьютерное обозрение №29, 2003.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
