Мультипликативный конгруэнтный метод

Глава 1 Теоретический анализ методов решения задачи

Анализ предметной области

 

Одной из динамично развивающихся сфер является сфера оказания парикмахерских услуг. Парикмахерская — это предприятие, занимающееся предоставлением услуг для населения по уходу за волосами (стрижка, завивка, создание причёски, окраска, мелирование и другие виды работ с красителями, бритьё и стрижка бород и усов и др.) в оборудованном специально для этого помещении. Как правило, в парикмахерских дополнительно оказываются следующие виды услуг: маникюр, педикюр, косметические услуги и услуги визажиста. В настоящее время в парикмахерской можно получить услуги солярия и косметолога.

Парикмахерские, согласно действующему стандарту, в зависимости от ассортимента и качества оказываемых услуг бывают следующих видов:

· парикмахерская;

· парикмахерская-салон;

· парикмахерская-люкс.

Специалисты, работающие в парикмахерской, называются парикмахерами. Парикмахер, парикмахер-стилист — специалист в области создания стиля человека с помощью причёски. Среди парикмахеров существуют следующие специализации:

· Специалист по мужским стрижкам (мужской мастер).

· Специалист по окрашиванию волос (парикмахер-колорист).

· Специалист по женским прическам (женский мастер).

· Специалиста по мужским и женским стрижкам

Виды услуг, предлагаемые парикмахерами:

· Лечение волос

· Стрижка волос

· Окраска волос (колорирование)

· Укладка волос

Теоретический обзор методов решения задачи

 

Метод Монте-Карло

В конце 40-х годов американские физики применили для вычисления на ЭВМ сложных квадратур метод, основанный на вероятностных законах. Этот метод был назван ими методом Монте-Карло, имея в виду Монте-Карло как мировой центр игр, исход которых определяется случаем. Суть метода станет ясной из следующего примера. Предположим, что требуется определить площадь s под некоторой кривой на отрезке , то есть вычислить значение определённого интеграла  (1). Это можно сделать следующим образом. Будем выбирать случайные точки в прямоугольнике  площадью  (см. рис.1) и считать число точек , попавших под кривую . Тогда при общем числе выбранных точек, отношение , очевидно, будет приближённо равным отношению искомой площади  под кривой на отрезке  к площади прямоугольника. Откуда искомая площадь может быть вычислена по формуле причём вычисленное таким образом значение будет тем ближе к точному значению интеграла (1), чем больше точек  взято и чем более равномерно распределены точки внутри прямоугольника.

 

Рис.1.Искомая площадь S

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

Одним из очевидно напрашивающихся представляется решение получить случайную последовательность каким-либо из известных физических методов, например с помощью рулетки, какие используются в казино, после чего записать эти случайные числа во внешнюю память ЭВМ с целью последующего использования в программе. Однако это потребовало бы значительных затрат времени для получения достаточно длинной случайной последовательности, с одной стороны, и внешней памяти для её сохранения, с другой. Следует отметить также тот факт, что в момент появления метода ресурсы внешней памяти ЭВМ были весьма ограничены. Другим возможным решением было бы применить непосредственно какой-либо физический метод генерации случайных чисел с помощью специально сконструированного для этих целей подключаемого к ЭВМ аппаратного устройства и далее получать с его помощью случайные числа непосредственно во время работы программы.

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

 

Метод Неймана

Для получения псевдослучайной последовательности Фон Нейманом был придуман простой в вычислительном отношении алгоритм, известный как метод квадратов. Метод состоит в многократном повторении процедуры, состоящей в возведении в квадрат некоторого числового значения и взятия средних цифр полученного результата. Пусть, например, мы выбрали в качестве исходного значения число . Тогда  и ,  и , и так далее. Однако вскоре у метода обнаружился недостаток, заключающийся в существенной неравномерности статистических частот различных числовых значений элементов получаемой этим методом последовательности.

 

Мультипликативный конгруэнтный метод

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

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

Формально схема вычисления может быть определена следующим образом: = С, (mod ), где  i-ый член псевдослучайной последовательности, С – некоторая константа, m – разрядность целочисленного регистра ЭВМ. Качество полученной псевдослучайной последовательности зависит от выбранного значения константы С. Установлено, что хороший результат достигается при выборе ее значения равным максимальной нечетной степени числа 5, помещающегося в числовом регистре фиксированной разрядности. Для 32-х разрядного регистра ЭВМ это число будет .