Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 6
Текст из файла (страница 6)
Чему предположительно равен максимальный период в этом случае? 17. [10] 0бабщнте ситуацию нз предыдущего упрахснения так, чтобы Х„+с зависело от предылущих Х значений последовательности. 18. [М20] Придумайте метод, аналогичный мепиСу из упр. 7, для определения цикла генератора случайных чисел, описанного в упр. 17, в общем виде.
19. [М4В] Выполните упр. 11, используя упр. 15, в более общем, случае, когда Х„ьс зависят от й предыдущих значений последовательности; каждая из щ" ' функций 1(хм...,хг) считается равиовероятиой. [Замечание. Число функций, которые дают максимдаьнмо период, анализируется в упр. 2.3.4.2-23.] 20. [ВО] Найдите вс» неотрицательные числа Х < 10'а, которые при использовании алгоритма К в конечном счете приводят к самовоспроизводящимся числам из табл.
1. 21. [49] Докажите или опровергните следующее утверждение: отображение Х ~-> 1(Х), определенное алгоритмом К„имеет ровно пять циклов длиной 3178, 1606, 1024, 943 и 1. 22. [21] (Г. Роллетшек (Н. Во!!еще)се)г).) Хороша ли идея генерирования случайных чисел с помощью последовательности 1(0), 1(Ц, 1(2), ..., где 1 — случайная функция, вместо того, чтобы использовать ха, у(хе), Щ(хо)) и т.
д.? ь 23. [М25] (Д. Фоата (!1. Рааса) и А, Фучс (А. гссс)сэ), 1970.) Покажите, что каждая из пс функций 1(х), рассмотренных в упр. б, может быть представлена квк последовательность (ха, хм..., х ~ ), имевшая такие свойства. !) (ха,хн ., ., х с) — это перестановки последовательности (7(О), 1(1),..., 1(пс — 1)). й) (1(О),, /(пс — 1)) может быть единственным обрезом восстановлена из последова. тельностн (хе,хм..,,хм с). О!) Элементы, которые появляются в циклах из 1, имеют внд (хе,хм...,хг ~), где Ь— самый большов индекс, такая, что эти й элементов различны.
!") х1 и (ха хс °, хз-с) влечет ху с = 1(х1), если хз ие является наименьшим элементом в цикле нз 1. к) (Д0), У(1),..., Х(пт -1)) — это переспхновка последовательности (О, 1,, т -1) тогда и только тогда, когда (хе, хм..., х„~) предстаяляет собой оброгвярм перестаиовкр к той перестановке, кокорин в разделе 1.З.З нелввна необычным соответствием, ы) хо = х~ тогда и только тогда, когда (хи..., х,) представляет собой ориентированное дерево, построенное в упр.
2,3.4А-18, с Дх) порожлмощнм х. 3.2. ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ В зтоы глздклн будут рассмотрены методы генерирования последовательности случайных дробей, т. е. случайных действительных чисел (7«, равномерно распределенных между кулам и единицей 1'на интервале «О, 1«), 'Гак как компьютер может представлять действительные числа только с определенной точностью, мы будем генерировать целое число Х„между нулем и некоторым числом т: дробь Ь « — Х«/т будет., следовательно, лежать между нулем и единицей. Обычно т выбирают равным размеру слова в компьютере. (В этой книге размером слова (магд гиге) автор называет число Ь', где о — основание системы счислении, используемой в компьютере, а е — число;разрядов машины.
— Прим. род.) Поэтому Х„можно по традиции рассматривать как целое число, занимающее все компьютерное слово, с точкой, которая отделяет целую часть числа от дробной, стоящей в правом конце слова, а Ь'„— если хотите, как содержание того же слова с разделяющей точкой, стоящей в левом конце слова. 3.2.1. Линейный конгруэнтный метод В настоящее время наиболее популярными генераторами случайных чисел являются генераторы, в которых используется следующая схема, предложенная Д. Г. Лехме- ром (О. Н. ЬеЬшег) в 1949 году «см. Ргос. 2пд Бушр. оп Ьвгйе-Бса(е В161га! Са1сп1агшй Масашагу (СашЬг1бяе, Маыл Нагтагд Оп1гегэ(гу Ргеяэ, 1961, 141-146)«.
Выберем четыре "волшебных числа": 0 <т; 0 < а <т; 0<с<т; О<Хо <т. т, модуль; а, множитель; с, приращение; Хо, начальное значение; Затем получим желаемую последовательность случайных чисел (Х„), полагая Х ег = (аХ„+ с) шог( т, и > О. (3) 7, б, 9, О, 7, 6, 9, О, Как показывает этот пример, такая последовательность не может быть "случайной«при некоторых наборах чисел т, а, с и Хо. Принципы выбора подходящих волшебных чисел будут подробно исследованы в следующих разделах этой главы. В примере (3) иллюстрируется тот факт, что конгруэнтная последовательность всегда образует петли, т. е.
обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство является общим для всех последовательностей вида Х«.ы =,Г(Х„), где У преобразует конечное множество само в себя (см. упр. 3.1-6). Эта последовательность называется линейной конгрузнтной последовательностью, Получение остатков по модулю т отчасти напоминает предопределенность, когда шарик попадает в ячейку крутящегося колеса рулетки. Например, для т = 10 и Хо = а = с = 7 получим последовательность Повторяющиеся циклы называются перно»)ами; длина периода последовательностк (3) равна 4. Безусловно, последовательности, которые мы будем использовать, имеют относительно длинный период.
Заслуживает внимания случай, когда с = О, так как генерируемые числа будут иметь меньший период, чем при с ф О. Мы убедимся в дальнейшем, что ограничение с = О уменьшает длину периода последовательности, хотя при этом все еще возм»окно сделать период достаточно длинным. В оригинальном методе, предложенном Д. Г. Лехмером, с выбиралось равным нулю, хотя он и допускал случай, когда с р» О, как один из возможных. Тот факт, что условие с э» О может приводить к появлению более длинных периодов, был установлен В.
Е. Томсоном (%. Е. Т)»о»пэоп) [Сошр. 3. 1 р. 83, 86] и независимо от него А. розенбергов» (А. ВосепЬегб) (3АСМ 7 (1960), 75-77~. Многие авторы называют линейную конгруэнтную последовательность прн с = О мрлвтииилнкатииенмм конгррэюиным мепитдом, а при с ЭЬ О— смешанным конгррэнп»нмм методом. Буквы ти, а, с и Хо будут использованы в этой главе в том смысле, в каком онн вводились раньше. То же самое относится н к константе (4) Ь=а — 1, которая вводится для упрощения многих наших формул. Можно сразу отбросить случай, когда а = 1, при котором последовательность Х„представима в виде Х„= (Хо + ис) пюд ти и ведет себя явно не как случайная последовательность.
Случай, когда а = О, даже хуже предыдущего. Следовательно, для практических целей предполагаем, что а>2, Ь>1. Сейчас можно обобщить формулу (2) Х»+ь = (а"Л» + (а" — 1)с/Ь) пю») ти, Ь > О, и > О, (6) где (и + Ь)-й член выражается непосредственно через и-й. (Случай, когда и = О, в этом уравнении также достоин внимания.) Из (4) следует, что подпоследовательность, содержащая каждый й-й член последовательности (Л „), является также линейной»»онгруэнтной последовательностью, множитель которой равен а тпоб ти и приращение равно ((а — 1) с/Ь) пю»] ти, Важным следствием из (6) является то, что общая последовательность, определенная с помощью а, с и Хо, может быть очень просто выражена в терминах специального случая, когда с = 1 и Хо — О.
Пусть 1'0 = О, 1'»+» = (а)'» + 1) шоб и». (7) В соответствии с (6) получил» 1'ь ы (аь — 1)/Ь (по молу»»ю ти). Значит, последова- тельность, определенная в (2), будет имеет вид Х„= (41'» + Хо) тпоб и», где А = (ХоЬ + с) шо»] и». (8) УПРАЖНЕНИЯ 1. (»О] В примере (3) показана ситуация, когда Х4 = Хв, так что последовательность начинается сначала, При»е»п»те пряыяр линейной копгрузптяой последовательности при ю = 10, для которой число Хв никогда снова не появится, 2. (МЙО] Покажите, что если а и ти взаимно простые, то Хв всегда появится в периоде.
3. [М10] Объясните, почему последовательность имеет определенные недостатки и, вероятно, не очень случайна, если а и т — не взаимно простые числа. Поэтому следует выбирать а и т так, чтобы онн были взаимно простыми, 4. [П] Докажите формулу (6), Ь. [Аууо] Соотношепне (6) справедливо при А > О. Если это возмоясно, получите формулы лля Х»+ь в терминах Х» лля атричаямльимв значений А. 3.2.1.1. Выбор модуля, Первая задача, которую мы рассмотрим, — нахождение хороших значений параметров, определяющих линейную конгруэнтную последовательность. Сначала выясним, как правильно выбрать число т.
Необходимо, чтобы т было дожиьно большим, твк как период не может иметь больше т элементов. (Даже если мы намерены генерировать только случайные нули и единицы, ис следует брать т х» 2, ибо тогда последовательность в лучшем случае будет иметь вид ...,0,1,0,1,0,1,...! Методы получения случайных нулей и единиц из линейной конгрузнтной последовательности обсуждаются в разделе 3.4.) Другой фактор, который оказывает влияние на выбор т, — скорость генерирования: нужно подобрать значение т так, чтобы (аХ„+ с) пюд т вычислялось быстро.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
