Реферат: Генератор случайных чисел

Кафедра: Автоматика иВычислительная Техника


Генератор случайных чисел


Содержание

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. Способыполучения случайных чисел

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

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

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

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

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

Для получения случайных чисел можно использовать различныеспособы. В общем случае все методы генерирования случайных чисел можноразделить на аппаратные и программные. Устройства или алгоритмы полученияслучайных чисел называют генераторами случайных чисел (ГСЧ) или датчикамислучайных чисел.

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

К программным ГСЧ относятся различные алгоритмыгенерирования последовательности чисел, которая по своим характеристикамнапоминает случайную. Для формирования очередного числа последовательностииспользуются различные алгебраические преобразования. Одним из первыхпрограммных ГСЧ является метод средин квадратов, предложенный в 1946 г.Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности наоснове предыдущего путем возведения его в квадрат и выделения средних цифрполученного числа. Например, мы хотим получить 10-значное число и предыдущеечисло равнялось 5772156649. Возводим его в квадрат и получаем33317792380594909201; значит, следующим числом будет 7923805949. Очевиднымнедостатком этого метода является зацикливание в случае, если очередное числобудет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

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

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

 


2. Характеристики ГСЧ

Последовательности случайных чисел, формируемых тем илииным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должнывыбираться из определенного множества (чаще всего это действительные числа винтервале от 0 до 1 либо целые от 0 до N). Во-вторых, последовательностьдолжна подчиняться определенному распределению на заданном множестве (чащевсего распределение равномерное). Необязательным является требованиевоспроизводимости последовательности. Если ГСЧ позволяет воспроизвести зановооднажды сформированную последовательность, отладка программ с использованиемтакого ГСЧ значительно упрощается. Кроме того, требование воспроизводимостичасто выдвигается при использовании ГСЧ в криптографии.

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

 


3. Применение ГСЧ

Одна из задач, в которых применяются ГСЧ, – это грубаяоценка объемов сложных областей в евклидовом пространстве более чем четырех илипяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов.Обозначим область через R; обычно она определяется рядом неравенств.Предположим, что R – подмножество n‑мерногоединичного куба K. Вычисление объема множества R методом Монте-Карлосводится к тому, чтобы случайным образом выбрать в K большое число Nточек, которые с одинаковой вероятностью могут оказаться в любой части K. Затемподсчитывают число M точек, попавших в R, т.е. удовлетворяющихнеравенствам, определяющим R. Тогда M/N есть оценкаобъема R. Можно показать, что точность такой оценки будет довольнонизкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, еслитолько объем не слишком близок к 0 или 1. Такой точности часто бываетдостаточно, и добиться лучшего другими методами может оказаться очень трудно.

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

/>.

Сначала необходимо определить прямоугольную область, изкоторой будут выбираться случайные точки. Это может быть любая область,полностью содержащая фигуру, площадь которой требуется найти. Возьмем вкачестве исходной области прямоугольник с координатами углов (0; –1) – (1; 1).Будем последовательно генерировать точки, равномерно распределенные внутриэтого прямоугольника, и для каждой точки проверять неравенства, описывающиефигуру. Если точка удовлетворяет всем неравенствам, значит, она принадлежитфигуре. При достаточно большом числе таких экспериментов отношение числа точек NF,удовлетворяющих неравенствам, к общему числу сгенерированных точек NRпоказывает долю площади прямоугольника, которую занимает фигура. Площадьпрямоугольника SR известна (в нашем случае она равна 2), площадь фигуры SFвычисляется тривиально:

/>.

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

Другим примером приближенного взятия определенногоинтеграла с помощью ГСЧ является вычисление объема шара в n‑мерномпространстве. Объем n‑мерного шара выражается формулой:

/>,

где Γ(z)– некоторая гамма-функция, определяемая следующим соотношением:

Γ (z+1)=z·Γ(z),

Γ(1)=1.

Таким образом, для натуральных z гамма-функция равнафакториалу z. Для вычисления знаменателя можно воспользоваться известнымзначением


/>:

/>.

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

 


4. Генерирование равномернораспределенных случайных чисел

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

xk+1 = f(xk)

Число xk частоназывается зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ иследующее генерируемое значение.

Поначалу функции f выбирались как можно болеесложные и трудно понимаемые. Например, f(x) определялась какцелое число, двоичное представление которого составляет средний 31 разряд 62‑разрядногоквадрата числа x (модификация метода средин квадратов). Но отсутствиетеории относительно f приводило к катастрофическим последствиям. Дляметода средин квадратов это уже упоминавшееся зацикливание при обращенииочередного числа в нуль. Поэтому уже довольно давно перешли к использованиюфункций, свойства которых вполне известны. Всякая последовательность целыхчисел из интервала (0, 231–1) должна содержать повторения самое большоепосле 231≈109 элементов. Используя теорию чисел,можно выбрать такую функцию f, для которой наперед будет известно, чтоее период максимально возможный или близкий к максимальному. Этим избегаетсяпреждевременное окончание или зацикливание последовательности. Дальнейшееиспользование теории чисел может более или менее предсказать характерпоследовательности, давая пользователю некоторую степень уверенности в том, чтоона будет достаточно хорошо моделировать случайную последовательность чисел.

Представим генерирование чисел в диапазоне [0; 1]рекуррентым методом графически (см. рис. 1). Очевидно, функция f(x)должна быть определена на всем отрезке [0; 1] и иметь на этомотрезке непрерывную область значений [0; 1], в противномслучае генерируемые числа будут составлять лишь несобственное подмножествоуказанного отрезка.

/>                />

а)                                                                                 б)

Рис.1. Графическое представление рекуррентногоГСЧ:

а) с «плохой»функцией f(x); б) с «хорошей» функцией f(x).

Считается, что функция f(x) тем лучшеподходит для генерирования случайных чисел, чем более плотно и равномерно ееграфик заполняет область xÎ[0; 1], yÎ[0; 1]. Например, функция, приведенная на рис. 1, а, будетдавать последовательность чисел с сильной корреляционной зависимостью соседнихэлементов. В случае функции, приведенная на рис. 1, б, эта зависимостьбудет значительно слабее.

В настоящее время широкое распространение получили линейныеконгруэнтные ГСЧ. В таком ГСЧ каждое следующее число получается на основеединственного предыдущего, при этом используется функция f вида:

f(х) = (ах+с) modm,

где для n‑разрядных двоичных целых чисел m обычноравно 2n.

Конгруэнтный ГСЧ выдает псевдослучайные целые числа винтервале (0, m). Параметры x0, a и c – целыечисла из той же области, выбираемые исходя из следующих соображений:

1.        x0может бытьпроизвольно. Для проверки программы возможно x0=1. В дальнейшем в качестве x0можно брать текущее время, преобразованное в число изинтервала (0, m). Такой подходобеспечивает различные последовательности дляразличных запусков программы.

2.        Выбор a должен удовлетворять тремтребованиям (для двоичных машин):

a)  a mod 8 = 5;

b)  />;

c)  двоичные знаки а не должны иметьочевидного шаблона.

3.        В качестве c следует выбиратьнечетное число, такое, что

/>.

Более подробные рекомендации по выбору параметров можнонайти у Д. Кнута [5].

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

 


5. Генерирование чисел с произвольнымраспределением

Достаточно часто возникает необходимость сгенерироватьпоследовательность случайных чисел yi, равномернораспределенных на данном конечном интервале [ab],с помощью ГСЧ, выдающего числа xi на интервале [0, m]. Приведение диапазонаГСЧ к нужному интервалу в этом случае осуществляется простым линейнымпреобразованием:

/>.

Распределение чисел после такого преобразования остаетсяравномерным.

Более сложным случаем является генерирование случайныхточек из некоторого множества в n‑мерном пространстве Rn, например, точек из некоторой области на плоскости.Рассмотрим формирование случайных точек для нескольких простых областей:прямоугольника, окружности и круга.

/>   />     />

а)                                                б)                                       в)

Рис.2. Области, из которых выбираются точки

Для получения равномерно распределенных случайных чисел изпрямоугольника, стороны которого параллельны осям координат (см. рис.2, а),достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужныминтервалам и использовать как координаты точки:

/>

/>,

где uj – равномерно распределенное случайное число из отрезка [0,m].

Окружность можно представить одномерным множеством точек сугловой координатой φ, принимающей значения на интервале (0, 2π).Таким образом, декартовы координаты очередной точки можно вычислить следующимобразом:

/>

/>

/>.

где uj – равномерно распределенное случайное число из интервала (0,m); r – радиус окружности.

В случае круга первое, что приходит в голову –воспользоваться полярной системой координат (ρ, φ),в которой данное множество фактически представляет собой прямоугольник (а длянего способ генерации чисел известен). Однако при переходе от полярныхкоординат к декартовым нарушается распределение случайных чисел: оно становитсянеравномерным; плотность распределения в центре круга выше, чем по краям.

Существует несколько способов получения равномерногораспределения по кругу. Рассмотрим один из них. Будем генерировать случайныепары (x, y) и для каждой из них ставить внутри круга соответствующуюточку, заполняя таким образом эту область. Исходя из представлений оравномерном распределении можно предположить, что при достаточно большой длинесгенерированной последовательности на единицу площади круга будет приходитьсяпримерно одно и то же количество точек вне зависимости от их расположения(другими словами, при равномерном распределении плотность точек по кругу будетодинакова).

Воспользуемся полярной системой координат для генерированияточек. При этом будем выбирать угол φ равномерно распределенным наинтервале (0; 2π), а распределение ρ построим следующим образом:

/>,

где x – равномерно распределенная на отрезке [0; 1]случайная величина. Можно показать, что при таком способе формирования координатслучайные точки будут равномерно распределены по всей площади круга.

Помимо выбора из произвольного множества, часто требуетсяформировать числа с распределением, отличным от равномерного. Распределениеобычно задается функцией плотности распределения f(x) либофункцией распределения F(x). Функция распределения в произвольнойточке x показывает вероятность того, что случайная величина Xокажется меньше данного значения x:

 

F(x)=P (X<x).

Функция плотности распределения представляет собойпроизводную F(x):

/>.


Функция F(x) для любой случайной величины является неубывающей навсем интервале (–∞; +∞), стремится к 0 при x→ –∞ и к 1 при x→+∞. Для получения случайных чисел с заданным распределением F(x) необходимо найтифункцию, обратную к F(x),т.е. такую функцию G, что для всех y=F(x)выполняется G(y)=x. Это можно пояснить следующим образом. Предположим, чтомы многократно выбираем число y, равномерно распределенноена интервале [0; 1]; каждому yмы ставим в соответствие некоторое x=G(y).Выбору 50000 игреков соответствует выбор 50000 иксов. Таким образом, долявыбранных y, лежащих между двумя фиксированнымизначениями, скажем y1 и y2, в точности равна доле x,лежащих в интервале [x1; x2]. Но вероятность первого из названныхсобытий равна | y2 – y1 |, если yраспределено равномерно; следовательно, верна цепочка равенств:

доля чисел винтервале [x1; x2] = доля чисел в интервале [y1; y2] =  y2 – y1 = F(x2) – F(x1) = />,

которая и показывает, что в случае равномерногораспределения игреков x имеет распределение с плотностью f(τ).Сложной проблемой в этом подходе является достаточно быстрое и точноеформирование обратной функции распределения G(y).

Рассмотрим в качестве примера получение случайного числа сэкспоненциальным распределением. Это распределение характеризуется однимпараметром λ>0 и имеет следующие функции распределения и плотностираспределения:

/>, x≥0;

/>.

Для этого распределения легко получить F–1 (y), т.е. разрешить уравнение F(x)=y. Решениеимеет вид


/>.

Для получения x с искомым распределением нужносгенерировать y, равномерно распределенное на (0,1), и применить этуформулу. Если говорить о практической стороне дела, то существуют болееэффективные способы, в которых не используется медленная операция вычислениялогарифма для каждого случайного числа. Данный способ продемонстрирован лишькак пример более общего подхода с использованием обратной функциираспределения.

 


6. Тестирование ГСЧ

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

Проверка равномерности последовательностей псевдослучайныхравномерно распределенных чисел {xi} может быть выполнена погистограмме с присваиванием косвенных признаков. Суть проверки по гистограммесводится к следующему. Выдвигается гипотеза о равномерности распределения чисел(0, 1). Затем интервал (0, 1) разбивается на m равных частей,тогда при генерации последовательности {xi} каждое из чисел xic вероятностью />, />, попадет в один изподынтервалов. Всего в каждый j‑й подынтервал попадает Niчисел последовательности {xi}, />,причём />. Относительная частотапопадания случайных чисел из последовательности {xi} в каждыйиз подынтервалов будет равна Nj/N. Очевидно, что есличисла xi принадлежат псевдослучайной квазиравномернораспределенной последовательности, то при достаточно больших Nэкспериментальная гистограмма (ломаная линия на рис.3, а) приближается ктеоретической прямой 1/m. Оценка степени приближения, т.е. равномерностипоследовательности {xi}, может быть проведена сиспользованием критериев согласия.


/>

Рис.3. Проверка равномерностипоследовательности

Существуют и другие способы проверки равномерностираспределения.

Проверка стохастичности последовательности псевдослучайныхчисел {xi} наиболее часто проводится методами комбинаций исерий. Сущность метода сводится к определению закона распределения длинучастков между единицами (нулями) или закона распределения (появления) числаединиц (нулей) в n-разрядном двоичном числе Xi.

Теоретически закон появления j единиц в lразрядах двоичного числа Xi описывается,исходя из независимости отдельных разрядов, биномиальным законом распределения:

/>,

где    P (jl) – вероятностьпоявления j единиц в l разрядах числа Xi;

p(1) = p(0) = 0,5– вероятность появления единицы и нуля в любом разряде числа Xi;

/>.


Тогда при фиксированной точке выборки N теоретическиожидаемое число появления случайных чисел Xi с jединицами в проверяемых l разрядах будет равно />.

После нахождения теоретических и экспериментальныхвероятностей P (jl) или чисел njпри различных значениях £ nгипотеза о стохастичности проверяется с использованием критериев согласия,которые подробно рассматриваются в курсе математической статистики.

При анализе стохастичности последовательности чисел {xi}методом серий последовательность разбивается на элементы первого и второго рода(a и b), т.е.

/>

где 0 < p < 1.

Серией называется отрезок последовательности {xi},состоящий из идущих друг за другом элементов одного и того же рода. Числоэлементов в отрезке (a или b) называется длиной серии.

После разбиения последовательности {xi}на серии первого и второго рода будем иметь, например, серию вида

…..aabbbbaaabbbaabbab….

Так как случайные числа a и b в даннойпоследовательности независимы и принадлежат последовательности {xi},равномерно распределённой на интервале (0, 1), то теоретическаявероятность появления серии длиной j в N опытах (под опытом здесьпонимается генерация числа xi и проверка условия xi< p) определится формулой Бернулли:

/>, />, />.

В случае экспериментальной проверки оцениваются частотыпоявления серий длиной j. В результате получаются экспериментальная итеоретическая зависимости P (j, l), сходимость которыхпроверяется по известным критериям, причем проверку целесообразно проводить приразных значениях l и р, 0 < р < 1.

 


7. Генератор случайных чисел в Borland C++

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

В Borland C++ (как и во многих других реализациях C/C++)используется линейный конгруэнтный ГСЧ. Длина периода этого ГСЧ составляет 232числа.

Для работы с ГСЧ в языке C предусмотрены следующиефункции:

1)        int rand()

Возвращает случайное целое число в диапазоне от 0 до RAND_MAX, где RAND_MAX – некотораяконстанта, зависящая от конкретной реализации ГСЧ. В Borland C++ значение RAND_MAX=32767.

2)        int random (int max)

Возвращает случайное целое число в диапазоне от 0 до max‑1.

3)        void srand (unsigned seed)

Устанавливает новое зерно ГСЧ. Обычно используется дляустановки известного начального значения x0при отладке программы.

4)        void randomize()

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

 


8. Практические задания

 

8.1 Случайные числа в заданном диапазоне

Выдайте на экран 10 случайных равномерно распределенныхчисел в диапазоне:

1)  От 3 до 12, целые.

2)  Из множества {–3, 0, 6, 9, 12, 15}.

3)  От 3 до 12, вещественные.

4)  От –2,3 до 10,7 с шагом 0,1.

5)  Из множества {–30; 10; 63; 59; 120; 175}.

6)  Из множества {1; 0,1; 0,01; …; 10–15}.

 

8.2 Двумерные случайные величины

Написать функцию генерации случайной точки в двумерномкруге с параметрами r, x0, y0.

 

8.3 Генерация одномерной случайной величины

Постройте случайную последовательность плотностьюраспределения которой принимает значение 1/4 на отрезке [0; 2] и 1/2 наотрезке [4; 5].

 

8.4 Оценить вероятность

В урне 5 белых, 10 черных и 15 красных шаров. Вынимают тришара. Оцените программным способом вероятность того, что все шары разногоцвета.


8.5 Медианы треугольника

Известно, что две медианы в треугольнике пересекаются в точке,которая делит их в отношении 2:1. Используя ГСЧ и векторную алгебру, докажитеэтот факт.

 


9. Лабораторные задания

 

9.1 ГСЧ фон Неймана

Реализуйте программно метод средин квадратов для двоичных8-разрядных чисел. Покажите, что ГСЧ зацикливается после прихода в ноль.

Замечания:

1.  Квадрат числа будет занимать 16 бит,что может вызвать переполнение знакового типа int.Рекомендуется использовать типы unsigned int или long для промежуточных вычислений.

2.  Для выделения средней части следуетиспользовать операции сдвига и преобразования типа (либо побитового «И»).

 

9.2 Случайная матрица

Заполните динамическую матрицу 40×50 целымислучайными числами от –3 до 2. Найдите среднее арифметическое всех элементовэтой матрицы. Зная точное значение данной величины (/>),вычислите ее относительную погрешность (в процентах) по формуле:

100% *(ТочноеЗначение – ПриблЗначение) / ДлинаДиапазона

Замечания:

1.  Количество целых чисел в диапазоне от–3 до 2 равно 2 – (–3) + 1 = 6.

2.        Чтобы напечатать символ %, используйтев функции printf спецификатор «%%».

 


9.3 Площадь фигуры

С помощью встроенного ГСЧ вычислите площадь фигуры,ограниченной линиями:

2 ≤ x≤ 5,

4 ≤ y≤ 25,

yx2.

Вычислите относительную погрешность (в процентах) в двухслучаях, когда количество случайных точек равно 1000 и 10000.

Замечания: точное значение площади в данном примере равно

125/3 – 8/3 –12

 

9.4 Случайная величина с заданными свойствами

Напишите функцию, генерирующую случайные числа с заданнымраспределением методом обратной функции распределения.

Распределения, для которых требуется генерировать случайныечисла:

1.  Равномерное на отрезках [a, b]È [c, d].

2.  Треугольное с параметрами [a, b].

 


10. Дополнительные задания

 

10.1 Многомерные случайные величины

Напишите функцию генерации случайной точки в n‑мерномшаре с центром в начале координат и радиусом r.

10.2 Быки и коровы

Напишите программу, моделирующую игру «Быки и коровы».Программа выбирает с помощью датчика случайных чисел четырехзначное число сразными цифрами. Цель игры – угадать это число. На каждом шаге играющийназывает четырехзначное число, а программа сообщает, сколько цифр числа угадано(быки) и сколько угаданных цифр стоит на нужном месте (коровы).

 
Библиографический список

1.  Керниган Б. Язык программирования Си: Задачи по языкуСи. / Б. Керниган, Д. Ритчи, А. Фьюэр М.: Финансы истатистика, 1985. – 192 с.

2.  Керниган Б., Ритчи Д. Язык программирования Си. М.:Финансы и статистика, 1992. – 272 с.

3. Подбельский В.В., Фомин С.С. Программированиена языке Си. Учеб. пособие. М.: Финансы истатистика, 2004. 600 с.

4.  Форсайт Дж. Машинные методы математических вычислений / Дж. Форсайт,М. Малькольм, К. Моулер. М.: Мир, 1980. – 279 с.

/>5. Кнут Д. Искусство программирования, том2. Получисленные методы / Д. Кнут. М.: Изд. дом «Вильямс», 2007. 832 с.

6.  Каханер Д. Численные методы и математическое обеспечение:Пер. с англ. / Д. Каханер, К. Моулер, С. Нэш. М.: Мир, 1998. –575 с., ил.

7.  Зубинский А. В поисках случайности // А. Зубинский.Компьютерное обозрение №29, 2003.

еще рефераты
Еще работы по информатике, программированию