AOP_Tom2 (1021737), страница 5
Текст из файла (страница 5)
Несмотря на то что от алгоритма можно ожидать на выходе всецело случайную последовательность, соображения, приведенные ниже, показывают, что это, к сожалению, не всегда так. [Читатель не обязан изучать данный алгоритм во всех деталях, но рекомендуется обратить внимание на его сложность; отмстилб в частности, шаги К1 н К2.) К1.
[Выбрать число итераций.] Присвоить 1' с — [Х/10э] наибольшую значащую цифру Л. [Мы выполним шаги К2-К13 точно Г + 1 раз, т. е. применим рандомизированные преобразования случайное число раз.) К2. [Выбрать случайный шаг.! Присвоить Я +- [Х/10з] шог] 10 следующую наибольшую значащую цифру Х. Переходим к шагу К(3+ Л), т.
е. к случайно выбранному шагу в программе.) КЗ.[Обеспечить > 5 х 10'.] Если Х < 5000000000, присвоить Х +- Х ь 5000000000. %С4. [Средина квадрата.] Заменить Х числом [Хз/10ь] шог110'е, т. е. серединой квадрата Х. К5. [Умножить.] Заменить Х числом (1001001001 Х) шог! 10~с. К6. [Псевдодополнение.] Если Х ( 100000000, то присвоить Х +- Х + 9814055677; иначе присвоить Х +- 10зе — Х, К7. [Переставить половины.) Поменять местами пять младших по порядку знаков Х со старшими по порядку пятью знаками, т.
е. присвоить Х < — 10ь(Х шо6 10 ) + [Х/10ь]; это то же самое, что взять десять средних цифр числа (10ге+ 1) Л'. К8. [Умножить.] Выполнить шаг К5. Таблица 1 КОЛОССА 1ЬНОЕ СОВПАДЕНИЕ: АЛГОРИТМ К ПРЕОБРАЗОВАЛ ЧИСЛО б065038420 САМО В СЕБЯ Шаг Х (после) У =б У=2 У=1 У=5 У=4 КЯ. (Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа Х на единицу.
К10. [Модифицировать на 99999.] Если Х ( 105, присвоить Х е- Ха+ 99999; иначе присвоить Л' 1 — Х вЂ” 99999. К11. (Нормировать.] (На этом шаге Х не может быть равным нулю.) Если Х ( 10э, присвоить Л е — 1ОХ и повторить этот шаг. К12. (Модификация метода средин квадратов.) Заменить Х иа (Х(Л" — 1)/10~] щи 10'э, т.
е, средними 10 цифрами числа Х(Х вЂ” 1). К13. [Повторить7] Егли 1' > О, уменыпить 1' на 1 и возвратиться к шагу К2. Если У = О, алгоритм завершен. Значение числа Х, полученное на предыдущем шаге, и будет желаемым "случайным" значением. 1 (Программа, реализующая этот алгоритм, обещала быть настолько сложной, что тот, кто прочел бы ее распечатку, без толковых комментариев не смог бы в ней разобраться.) После рассмотрения всех преобразований алгоритма К не кажется ли правдоподобным, что можно было бы обеспечить бесконечное снабжение невероятно случайными числами? 11ет! На сэмом деле, когда этот алгоритм впервые был реализован на компьютере, он почти немедленно сошелся к 10-значному числу 6065038420, К1 КЗ К4 К5 Кб К7 КВ К9 К 10 К11 К12 Кб К7 КВ К9 К 10 К11 К12 К12 Кб К7 КВ 6065038420 6065038420 6910360760 8031120760 1968879240 7924019688 9631707688 8520606577 8520506578 8520506578 0323372207 9676627793 2779396766 4942162766 3831051655 3830951656 3830951656 1905867781 3319967479 6680032521 3252166800 2218966800 Шаг К9 К10 К11 К12 К5 Кб К7 КВ К9 К10 К11 К12 К11 К12 К4 К5 Кб К7 КВ К9 К10 К11 К12 Х (после) 1107855700 1107755701 1107755701 1226919902 0048821902 9862877579 7757998628 2384626628 1273515517 1273415518 1273415518 5870802097 5870802097 3172562687 1540029446 7015475446 2984524554 2455429845 2730274845 1620163734 1620063735 1620063735 6065038420 которое по невероятному совпадению преобразовалось сил<о в себя по алгоритму (табл.
1). С другим стартовым числом последовательность начала повторяться после 7401 значения с периодом длиной 3178. Мораль этой истории в том, что случайные числа не следует генерировать методом, выбранным наудачу. Не мешало бы использовать немного теории. В следующих разделах будут рассмотрены генераторы случайных чисел более высокого уровня, чем метод средин квадратов и алгоритм К. Соответствующие па<шедовательнасти гарантированна обладают желаемыми случайными свойствами и не вырождаются. Мы исследуем некоторые причины такого, похожего на случайное, поведения, а также покажем, как можно обращаться со случайными чи<шами. Например, одно из наших исследований будет посвящено программе., которая тасует смоделированную на компьютере колоду карт.
В разделе 3.6 приводятся итоги к этой главе и содержатся некоторые библиографические источники. УПРАЖНЕНИЯ ° ' 1. (20( Предположим, вы хотите получить случайную десятичную цифру. Какой из следующих методов вы выберете? а) Откроете телефонный справочник, ткнув пальцем куда-нибудь, выберете первый попавшийся номер телефона и вазьл<ете младшую цифру («нфрр младшего разряда) этого номера.
Ъ) Поступите, как в (а), на выберете младшую цифру камера сгнранацм. с) Покатите игральную кость в форме икасаэдра, имеющую двадцать граней, котарые помечены цифрами О, О, 1, 1,..., 9, 9. Когда кость остановится, выберете верхнюю цифру. (Для катания игральной кости рекомендуется использовать стол с харашо натянутым сукном.) <1) На одну минуту выставите счетчик Гейгера у источника радиоактивного излучения (предварительна обезопасив себя) и воспользуетесь младшей цифрой наказаний счетчика.
Предполагается, что на счетчике Гейгера представлены числа в десятичной системе счисления и вначале на нем был установлен нуль е) Бросите быстрый взгляд на свои часы и, если секундная стрелка находится между бп и 6(а + 1) секундами, выберете цифру п. <) Попросите приятеля задумать любую цифру и воспользуетесь ею. 8) Попросите врага задумать любую цифру и воспользуетесь ею. Ъ) Предположите, чта 10 лошадей участвуют в забеге и вам а них абсолютно ничего не известно.
Присвоите каждой лошади в произвольном порядке номер ат 0 да 9, а после забега выберете в качестве случайной.цифры номер победителя. 2. (М99] Какова вероятность того, чта в случайной последовательности из миллиона десятичных цифр каждая возможная цифра встречается ровно 100 000 раз? 3.
[10] Какое число следует за 1010101010 в методе средин квадратов? 4. (2<?] (а) Почему на шаге К11 алгоритма К значение Х не может быть равно нулю? Какая ошибка возникла бы в алгоритме, если бы Х маг принимать значение "нуль"? (Ъ) Используя табл. 1, установите, чта происходит, когда алгоритм К применяется повторно са стартовым зна юнием Х = 3830951656. 5. [15] Объясните, почему в любом случае, даже если савпаленне, приведенное в табл.
1, не произошла, алгоритм К не сможет выдать бесконечную пагледавательнасть случайных чисел в там смысле, что любая последовательность, генерируемая алгоритмом К, станет в конце концов периаднчнай. 6. [М91] Предположим, что необходимо получить последовательность целых случайных чисел Хе, Лм Хз, ...
на интервале 0 < Х„< пь Пусть у(х) — любая функция. такая, что неравенство 0 < х < т влечет 0 < г'(х) < яь Рассмотрим последовательность Х е~ = ) (Х„). (Примеры таких последовательностей — метод средин квадратов и алгоритм К.) а) Покажите, что такая последовательность периоднчна в том смысле, что существуют числа Л н р, для которых значения Х., Х„..., Х„..., Хе,.л ~ Различны, однако Л еь = Х, когда п > д.
Определите возможные максимальное и минимальное значения д и Л. Ь) (Р. Флойд (В. %. Г!оуч)).) Похажнте, что существует такое н > О, что Л;, = Хе„н наименьшее такое значение и лежит в интервале д < и < д + Л. Более того, значение Л является единственным етом смысле, что если Л = Лее и Х, = Льч то Л = Х . с) Используя идеи (Ь), составьте алгоритм вычисления р и Л для любой заданной функции ~ и любого заданного Хе, используя только 0(д+Л) шагов и только ограниченный объем памятн.
е' 7. (МЯ] (Р. П, Брент (В. Р. Вгепс), 1977.) Пусть 4(п) — наибольшее целое число, такое, что 4(п) < и, 4(п) = 2, где е — целое число. Так, например. 4(15) = 8 и Ю(4(п)) = 4(п). а) Покажите, что в терминах обозначений упр. б существует такое п > О, что Х„ Хц„~ ы Найдите формулу для наименьшего такого п в терминах чисел д и Л, определяющих период. Ь) Примените этот результат для составления алгоритма, который может быть использован совместно с любым генератором случайных чисел типа х ь~ = 1(х„), чтобы предотвратить циклическую неопределешюсть. Вашему алгоритму следует вычислять период длиной Л н испольэовать только небольнюй объем памяти — вы просто не должны заполнять всю память вычисленными значениями последовательности! 8. [8У] Выполните полную проверку метода средин квадратов для случая, когда десятичные числа состоят из двух цифр. а) Мажете начать процесс с любого нз 100 допустимых чисел 00,01,...,99.
Сколько из этих значений в конечном счете приведут к повторению цикла (зацикливанию) 00,00,...? [Пример. Начиная с числа 43, получим последовательность 43, 84, 05, 02, 00, 00, 00, ....] Ь) Сколько существует финальных циклов? Каков размер самого длинного цикла? с) Какое начальное значение (нли значения) даст наибольшее число различных элементов,прежде чем последовательность повторится? 9. [МЦ] Докажите, что метод средин квадратов, использующий 2п-значные числа в 5-ичной системе счисления, имеет следующие недостатки: если последовательность включает любое чигло, в котором и старших значащих цифр — нули, то последующие числа становятся все меньше и меньше, пока не превратятся в нули.
10. [М!б] Пусть выполняются предположении предыдущего упражнения. Что можно сказать о последовательности чисел, следующих за Л, егчи младшие значащие и цифр числа Х равны нулю? Что если и+ 1 младших значащих цифр Равны нулю? ь 11. [МЯб] Рассмотрим последовательности генераторов случайных чисел, имеющих вид, описанный в упр. б. Если выбрать 1(х) и Хе наудачу (другими словами, если предположить, что каждая из ш возможных функций 7" (х) равновероятна н каждое из ш возможных значений Хе равновероятно), то какова вероятность того, что последовательность в конечном счете выродится в цикл длиной Л = 1? [Эаееечание. Предположения этой задачи дают повод задуматься о еглучайностн*' генераторов случайных чисел такого типа. Можно ожидать, что метод, подобный алгоритму К, отчасти ведет себя так же, как рассмотренный здесь генератор; ответ на эту задачу дает колоссальное число совпадений в табл.
1.] э 12. [МВ1] Какова средняя длина финального цикла, если выполняются предположения предыдущего упражнения? Какова среднян длина последовательности да вхождения а цикл? (В обозначениях упр. 6 необходимо определкть средние значения Л и р + Л,) 13. (М49] Если 1 (х) выбрана наудачу, как в упр. 11, какова средняя длина самого длинного цикла, полученного путем варьирования начального значения Ло? [Зо.мечоние. Мы уже рассмотрели аналогичную проблему для случая, когда 1(х) — зто случайные перестановки; см. упр. 1.3.3 — 23.] 14. [МЮВ( Если 1(х) выбрано наудачу, как в упр. 11, каково среднее число различных финальных циклов, полученных в результате варьирования начальных значений? [См.
упр. 8, (Ь).] 16. [М16] Если 1(х) выбрано наудачу, как и в упр. 11, чему равна вероятность, что ни один из финальных циклов не имеет длину, равную 1, невзирая на выбор Ло? 16. (15] Последовательность, генерируемая, как в упр. 6, должна повторяться после того, как было сгенерировано не более т значений. Предположим, что мы обобщим метод таким образом, что Л„ез будет зависеть от Х з так же, как от Х; формально пусть 1(х,у)— такая функция, для которой 0 < х, у < т влечет неравенства 0 < 1(х, у)< т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
