Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию
Подождите немного. Документ загружается.
деления суммы as
n-1
+c на m, и вместе с последовательностью s
0
, s
1
,…
рассмотрим последовательность
1
1
+
+
=
m
s
r
n
n
(n = 0, 1, …). При удачном
выборе a, c, m, s
0
последовательность r
0
, r
1
,… будет хорошо
имитировать последовательность равномерно распределенных в
интервале (0, 1) случайных чисел. Одним из таких выборов
оказывается следующий:
1) m = 2
k
,где k берется настолько большим, насколько это
возможно (надо иметь в виду, что последовательность s
0
, s
1
, …, равно
как и последовательность r
0
, r
1
, …, будет периодической с периодом
2
k
; при небольших значениях k периодичность будет слишком
заметной )
2) При делении a на 8 должен получаться остаток 5. Кроме
этого, требуется, чтобы выполнялось
mam m<<−
.
3) Число c должно быть нечетным; при этом желательно, чтобы
выполнялось приближенное равенство 21132.03
6
1
2
1
=−≈
m
c
…
4) Число s
0
можно выбирать произвольно в диапазоне от 0 до
m – 1.
В связи со сказанным предполагаются следующие задания:
a) Подобрать несколько вариантов троек a, c, m,
удовлетворяющих условиям 1) – 3).
б) Найти еще какое-нибудь соображение, позволяющее хорошо
имитировать случайность, и на его основе описать новый датчик.
в) Пользуясь различными датчиками, среди которых должны
быть датчики, построенные по предложенной выше схеме с различным
выбором a, c, m, s
0
, и «самодельные» датчики, построенные на других
соображениях, требуется провести эксперименты , описанные в
предыдущей задаче.
749. Датчики случайных чисел находят интересное применение
в вычислении площадей и объемов: на этом принципе основан
известный метод Монте-Карло (объяснение происхождения названия и
подробное изложение самого метода с многочисленными примерами
изложений имеется, например, в [47]). Пусть задана фигура M,
целиком лежащая внутри единичного квадрата, и пусть нужно
вычислить ее площадь. Пусть в единичном квадрате выбрано наугад n
точек (рис. 42) и пусть v(n) – число точек, попавших внутрь M. Тогда
геометрически ясно, что при больших n площадь фигуры M будет
Рис. 42
0
1
1
y
x
X
Y
Z
1
1
1
Рис 43
приблизительно равна v(n)/n и чем больше будет n, тем ближе мы
подойдем к истинному значению площади. В качестве выбираемых
«наугад» точек в этих вычислениях можно взять точки с координатами
(r
0
, r
1
), (r
2
, r
3
), …, где в роли r
0
, r
1
,… выступают числа, получаемые с
помощью датчика случайных чисел, равномерно распределенных в
интервале (0, 1).
Аналогично, беря точки с координатами (r
0
, r
1
, r
2
), (r
3
, r
4
, r
5
), …,
можно вычислять объемы тел, целиком лежащие внутри единичного
куба (рис. 43).
В связи с методом Монте-Карло предлагаются следующие
задания. Воспользовавшись несколькими датчиками (в крайнем случае
одним датчиком):
а) определить площадь круга (x – 0.5)
2
+(y – 0.5)
2
< 1/4; для этого
найти по 200 точек с помощью каждого из датчиков; ответы сравнить с
4
π
;
б) определить объем шара (x – 0.5)
2
+(y – 0.5)
2
+(z – 0.5)
2
< 1/4;
для этого найти по 200 точек с помощью каждого из датчиков; ответы
сравнить с
6
π
.
750. Случайная числовая последовательность r
0
, r
1
, … , члены
которой равномерно распределены в интервале (0, 1), может быть
использована для построения случайной последовательности v
0
, v
1
, …,
члены которой принадлежат конечному множеству, состоящему из
элементов x
1
, … , x
n
. Элементы x
1
, …, x
n
повторяются в
последовательности v
0
, v
1
,… с заданными частотами, соответственно
равными p
1
, …, p
n
(т.е. относительно последовательности v
0
, v
1
,…
можно считать, что x
i
встречается в ней с вероятностью p
i
(i=1, 2, … ,
n) p
1
+…+ p
n
=1 ). Последовательность v
0
, v
1
, … будем называть
случайной последовательностью с распределением
n
n
ppp
xxx
...
...
21
21
.
Для построения v
0
, v
1
, … используется следующий прием [47].
Интервал (0, 1) разбиваем на n интервалов, длины которых равны p
1
,
… , p
n
. Координаты точек разбиения будут p
1
, p
1
+ p
2
, p
1
+ p
2
+ p
3
, …,
p
1
+ p
2
+...+ p
n-1
. Полученные интервалы обозначаем через I
1
, … , I
n
.
Теперь перебираем числа r
0
, r
1
, r
2
, …., и если очередное число r
k
попадает в интервал I
j
()
nj ≤≤1 , то в качестве v
k
берем x
j
(в силу
равномерного распределения членов последовательности r
0
, r
1
, … в
интервале (0 , 1) вероятность попадания r
k
в некоторый интервал равна
длине этого интервала). Если вдруг окажется, что r
k
совпадает с точкой
разбиения (концом интервала), то можно условно считать, что число r
k
попало в интервал, лежащий справа от него.
Предлагаются следующие задания, в которых надо
воспользоваться датчиком случайных чисел:
а) Построить 100 первых членов случайной последовательности
из нулей и единиц, в которой нуль и единица равновероятны, т. е.
последовательности с распределением
2121
10
.
б) Построить 100 первых членов случайной последовательности
из цифр 1, 2, 3, 4, 5, 6, в которой все эти цифры равновероятны, т. е.
последовательности с распределением
616161616161
654321
.
в) Построить 100 первых членов случайной последовательности
из нулей и единиц, в которой нуль встречается с вероятностью 1/4, а
единица – с вероятностью 3/4, т. е. последовательности с
распределением
4341
10
.
г) Построить 100 первых членов случайной последовательности
из слов «камень», «ножницы», «бумага», в которой эти три слова
равновероятны, т. е. последовательности с распределением
313131
бумаганожницыкамень
. (Эту последовательность можно
использовать для выбора ходов в известной игре «камень, ножницы,
бумага».)
д) Построить 100 первых членов случайной последовательности
из слов «камень», «ножницы», «бумага», в которой слово «камень»
встречается с вероятностью 1/3, слово «ножницы» – с вероятностью
1/2, слово «бумага» – с вероятностью 1/6 , т. е. последовательности с
распределением
612131
бумаганожницыкамень
. (Эту последовательность
можно использовать для выбора ходов в известной игре «камень,
ножницы, бумага» со следующей системой премий: когда «камень»
тупит «ножницы», присуждается одно очко, когда «ножницы» режут
«бумагу», присуждается два очка, когда «бумага» покрывает «камень»,
присуждается три очка.) *)
*) Указанные в заданиях г) и д) стратегии чередования ходов,
основанные на случайных последовательностях, является в
определенном смысле оптимальными. См. об этом, например, в книге
[33].
751. Для наглядной демонстрации некоторых законов теории
вероятностей используется прибор, называемый доской Гальтона (рис.
44).
Металлические шарики по очереди попадают в верхний канал;
встретив препятствие они должны выбрать путь налево или направо,
затем проходить второй выбор и т. д. Каждый из выборов случаен,
каждая из вероятностей выбора пути налево и направо равна 1/2. При
достаточно высоком качестве прибора наблюдаемая картина
распределения шариков в нижних отделениях доски Гальтона хорошо
согласуется с вероятностными расчетами, по которым количества
шариков, оказавшихся в отделениях, пронумерованных числами 1, …,
m (на рис.44 m=5), должны быть пропорциональными (с некоторым
коэффициентом пропорциональности, зависящим от общего числа
шариков) числам из m-й строки треугольника Паскаля (см. задачу 555
).
Кривая, огибающая верхушки столбцов из шариков, должна иметь
колоколообразную форму (рис. 45). Путь шарика по доске Гальтона,
содержащей m нижних отделений, можно изобразить группой из m
нулей и единиц: нуль изображает выбор пути налево, единица -
направо. Получив с помощью датчика случайных чисел mn членов
случайной последовательности v
0
, v
1
, … из нулей и единиц с
распределением
2121
10
(см. задачу 750а
) и взяв группы (v
0
, …, v
m-1
),
(v
m
, …, v
2m-1
), …, (v
(n-1)m
, …, v
nm
), мы получим изображения путей n
воображаемых шариков. Номер отделения, в которое попадает шарик,
определяется по количеству единиц в изображении маршрута. Пусть
даны натуральные n и m (n≥2
m
). Требуется подсчитать, исходя из
модели, которая основана на датчике случайных чисел, количество