Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 71
Текст из файла (страница 71)
2л), можно получить подходящий результат, но потребуется выполнить намного больше вычислений, (с) Начните, пожалуй, с 2 048 нормальных случайных величин Хо, -, Лгоы, 'гщ 12ете. После использования около 1/3 из них генерируйте еще 2 048 случайных величин следующим образом. Выберите целые числа а, Ь, с и Ы независимо в (О .. 1024), причем а и с должны быть нечетными. Затем присвойте Хг г- Л<а~+Ыпа егсисозВ+1(ютщтюь гезгз!пВ, 1г г Хогг+В яме шы щпВ + уыгещ тм гоы сов В для 0 < / < 1024, где соеВ и щп — случайные отношения ((/з - 7')/(Ье + 1") и 2П)'/((/т + 1'г), выбранные, как в упр. 23.
Мохспо отбросить У и Ъ', кроме случаев, когда (сов В( > 4 и ( з1п В( > 2~. 2 048 новых случайных вещгчин заменят старые. Замезим, что для получения новой случайной величины иеобхошгмо выполнить лишь несколько операций. Этот метод не расходится подобно последовательностям, содернащимся в (Ь), так как сумма квадратов Я(ХВ+ У,у) = 2„((Х,') + (1'„')з) остается постоянной со значением Я 2048, исключая незначительную ошибку округления. С другой стороны, постоянство Я на самом деле является недостатком метода, поскольку сумма квадратов действительно должна иметь Х~-расоределение с 2 048 степенями свободы. Чтобы преодолеть возникшую проблему, следовало бы использовать не нормальные случайные величины Л„, а аХг, где оз м уг(гшзз + ~/4093)з/Я является заранее вычисленным нормируюшим множителем. (Величина -'(ггшз + ь/4095)~ будет приемлемо приблинщть требуемую Хг случайную величину.) Лигаерашуро.
С. 8. 1ЧаБасе, г(СМ Тгзле, ов Маей. Яогсггаге 22 (199б), 119-127, К. Р. Вгепс, Ьесгнге уйосез го Сошр. Яс1. 1470 (1998), 1-20, 32. (а) Преобразование (Л', ув) = /(Л, У) является взаимно однозначным соответствием преобразованию множества (х, у > О) самого в себя, такого, что х' + р' = х + р и г(х' ИВ' = Их Иу. Получим У' г У вЂ” — -Л) 41, = ( — 4 Л) 01. Х+У ~Х+У 1 ' Х+1" =~Х+У (Ь) Это преобразование является таким соответствием (си о-со-опе) от двух к одному, что л'+ р' = х + В и Вх' г(у' = 2 Ия Иу. (с) Достаточно рассмотреть "В-трвнспонированное" преобразование Ф = ( хгтгхг+гхгрг'-гуг-туг-3 )з~ г Вг'+2Уг'+гутхт-гхГ-Зху-3 )2 для фиксированных целых / и затем составить У-транспонирования для / = О, 1, -1, 2, -2, ..., принимая во внимание, что совместные вероятностные распределения Х' и У' сходятся при ~Л -+ оа Каждое /-транспонирование является взаимно однозначным с операциями х' + р' = х + у и 0х' Ыу' = бх е(у.
33. Использовать Уг как начальное значение дзя других генераторов случайных чисел (возможен линейный конгруэнтный генератор с другим множителем); в качестве множителя взять одну из Уг, Егз..... РАЗДЕЛ 3.4.2 1. Существует („') способов выбора и — т записей из последних Ю вЂ” г и („' ' ',) способов выбора и — т — 1 записей из гз' — 1 — 1 после выбора (1+ Ц-й записи, 3. Переход от шага 53 к шагу 55 невозможен, если количество записей, которые осталось проверить, равно и — т. 3.
Не будем путать условную и безусловную вероятности. Значение т зависит от случайного выбора первых 1 элементов. Если взять среднее по всем возможным выборам, которме могут появиться среди этих элементов, то можно найти, что (и — т)/(Ю вЂ” 1) в среднем точно равно и/Ф. Например, рассмотрим второй элемент. Если первый элемент отобран в выборку (зто происходит с вероятностью и/гзе), то второй элемент выбирается с вероятностью (и — Ц/(гзг — Ц; если первый элемент не выбирается, то второй выбирается с вероятностью п/(гз': — Ц. Полная вероятность выбора второго элемента равна ( / Н( — Ц/( — Ц)+(1- /1Ь)( /(й-Ц) ы /йГ.
4. Из алгоритма следует, что и — ть и — (т — Ц р(т,с+ Ц = ~1 — — ) р(т, 1) + йà — 1) 1У вЂ” 1 р(т — 1,1). Требуемая формула может быть доказана инлукцией по й в частности р(и, гз') = 1. 5. В обозначениях упр. 4 вероятность того, что 1 = й, по окончании работы алгоритма равна оз = р(и, й) — р(п, й — Ц = ("„',)/('~). Среднее равно 2 '„о Муз = (Ф+ Цп/(и + Ц. б. Так же, как в упр. 5, получим 2 з й(й + Цйз = (Ю + 2)(ге'+ Ци/(и+ 2); дисперсия, следовательно, равна (гз'+ Ц(гз' — п)и/(п+ 2)(и+ Цз. 7. Предположим, есть выбор 1 < хз с хг « . х„< Х.
Пусть хз = О, х +з — — йг+ 1. Выбор получен с вероятностью р = П,«,, рп где (1з' — (г — Ц вЂ” и+т)/(гз' — (с — Ц) для х~ < г с хы+м ре = (и — т)/(гз' — (1 — Ц) дляг=х +ь Знаменатель произведения рз равен лГ!, числитель содержит члены гзе — и, гз' — и — 1, ..., 1 для тех гз, которые не равны хз, а члены и, и — 1, ..., 1 для тех гь, которые рзеиы хю Следовательно, р = (гзз — и)! и! /дп..
Пргьыер. п = 3, йг = В, (хи хз, хз) = (2, 3, 7); р = з г „- з — з г -,. ззгззгзз 3. (а) р(0,5) = (~„")/('„") = (и ")/(Яз) из (~) выборок, если пропустить первые й записей. (Ь) Присвоить Х +- й — 1, где й является минимальным с П > Рг(Х > й). Затем выполнять присвоения Х з- О, р з- 1з" — и, о з- Ю, Н е- р/д и т. д. до тех пор, пока 1У < Н. Присвоить Х +- Х + 1, р з- р — 1, 4+- о — 1, Н+- Нр/д. (Этот метод хорош, когда п/1з", скажем„> 1/5. Можно предположить, что и/1зе С 1/2, иначе лучше выбрать гз' — и пееыбраныззх записей.) ( ) Р ( 1 (У'я .....
Уя- ) > й) = П," ' Р (1' †, > 5) = П," , ( -/- )/(Л вЂ” У) (Этот метод хорош, если, скажем, и < 5.) (4) (См. упр. 3.4.1 — 29.) Значение Х г- (Н(1 — Убы)! требуется отбросить с вероятностью, равной тштько 0(п/Н). Точные дезвлн тщательно проработаны в САСМ 27 (1984), 703-718, а практическое осуществление приведено в АСМ ТЪшз. Маей. Зойи'аге 13 (1987), 58-67, (Этот метод хорош, когда, скажем, 5 < и < -„'К.) После пропуска Х записей и выбора следующих присвоим и +- и — 1, Н +- Н вЂ” Х вЂ” 1 и будем повторять процесс до тех пор, пока и = О. Подобное приближение ускоряет метод резервуара [см. АСМ Тгалз.
Магй. Бойвше 11 (1985), 37 — 57]. 9. В резервуар будет помещено семь записей: 1, 2, 3, 5, 9, 13, 16, В окончательной выборке содержатся записи 2, 5, 16. 10. Удалить шаг Кб и переменную т. Заменить таблицу 1 таблицей записей, инициализированных первых и записей на шаге Н1, и, заменив М-е значение таблицм, перейти в алгоритме к шагу К4. 11. Поступая, как в разделе 1.2.10, в котором рассматривался частный случай, когда и ж 1, получаем, что производящая функция равна 1 и )( 2 и ) (Л' — и и ) среднее значение равно и + ~„<,<„(п/г) = п(1 + нл — и ), в дисперсия оказывается равной н(Ня — Н„) — и (Н~Ш вЂ” НЬ ~). 12. Заметим, что я ' = (ЬИ)...
(Ьз3)(Ьз2), поэтому находим алгоритм, который переводит представление |г в х '. Присвоить Ь; +-,у' для 1 <,у < й Затем для у = 2, 3, ..., Г (в таком порядке) произвести взаимный обмен 6, +~ Ь,. Наконец для 2 = й ..., 3, 2 (в таком порядке) присвоить Ь„, +- 6,. (Алгоритм основмвается на том факте, что (а~с) х~ = 1г| (Ь,г).) 13. Перенумеровав колоду О, 1, ..., 2п — 2, находим, что номер (2я) шоб(2к — 1) з раз присвоен карте с номером х, в то время как номер (х + 1) шод (2п — 1) с раз присвоен карте с номером г. Получим (с следует из е) = сз = есз. Значит, произведение любого количества с и е можно привести к виду в'с"'. Также 2""~~" П ш 1 по модулю (2п — 1).
Поскольку е" Ры ') и сы ' — тождественные перестановки, то возможно не более (2п — 1)~р(2п — 1) компоновок. (Точное число различных компоновок равно (2п-1)Ь, где Ь равно порядку 2 по модулю (2п — 1). Для случая, когда в = сГ, с' устанавливает карту О, е" = с' = тождество,) Дополнительные детали приводятся в ЯАМ Неьбегг 3 (1961), 293-297. 14. (а) 3.
Это можно установить, не обращая внимания на то, где именно была сдвинута карта, кроме случая, когда карта была взята из первых трех нли последних двух позиций. (Ь) ь. Три разрезания и перетасовки приведут к перемешнванию самое большее восьми циклически возрастающих подпогшедовательностей а, ойч ем „ма „...
аы„, ц „„а „. Значит, подпоследовательности е ь <4 заблокированы. (Несколько магических трюков основано на том факте, что три разрезания и перетасовки являются совсем неслучайными; см. Магт1п Сагдпег, Магйетагюа) Мебгс БИоп (Кнор(, 1977), гл. 7.) 15. Присвоить у~ +- / для г — и < / < г. Затем для / = й г — 1, ..., à — и+ 1 проделать следующие операции. присвоить ь ~- (ун) + 1. если й > г — и, присвоить Х, е-1'ь и К, +- уг, иначе, если Ь = Х, для некоторых 1 > т (можно использовать таблицу идентификаторов алгоритма), присвоить хг е- 1; н К е- Уу; иначе — присвоить хг е- 6. (Идея основана на предположении,что К- +ц.,., 11 представляют Х~ „+м..., Хм и, если 1 > 1 и Х, < г — и, на предположении, что 1; представляют Хх„в исполнении алгоритма Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
