Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 5
Текст из файла (страница 5)
Несмотря на то что от алгоритма можно ожидать на выходе всецело случайную последовательность, соображения, приведен- ные ниже, показывают, что это, к сожалению, не всегда так. (Читатель не обязан изучать данный алгоритм во всех деталях, но рекомендуется обратить внимание на его сложность; отметим, в частности, шаги К1 н К2.) К1. )Выбрать число итераций.) Присвоить К +- (Х!'10э) наибольшую значшпую цифру Л, (Мы выполним шаги К2-К13 точно 1'+ 1 раз, т. е. применим раидомизированные преобразования случайное число раз.) К2. )Выбрать случайный шаг.) Присвоить Я +- '(Х710е ) шо610 следующую наибольшую значащую цифру Л.
Переходим к шагу К(3+ Я), т. е, к случайно выбранному шагу в программе.) К3. )Обеспечить > 5 х 10э.] Если Х < 5000000000, присвоить Х э- Х+ 5000000000. 1С4. ,'Средина квэдрата.) Заменить Х числом (Х~/10е) ща6101а, т. е. серединой квадрата Х. К5. [Умножить.) Заменить Х числом (1001001001 Х) п|ск1 101о. К6. )Псевдодополнение.) Если Х < 100000000, то присвоить Х е- Х + 9814055677; иначе присвоить Л е- 10'о — Х, К7. (Переставить половины.) Поменять местами пять младших по порядку знаков Х со старшими по порядку пятью знаками, т.
е. присвоить Х е- 10э(Х той 10 ) + (Х710э1, эта та же самое, что взять десять средних цифр числа (10'а + 1) Х. К8. )Умножить.) Выполнить шаг К5. Таблица 1 КОЛОССАЛЬНОЕ СОВПАДЕНИЕ; АЛГОРИТМ К ПРЕОБРАЗОВАЛ ЧИСЛО 6065038420 САМО В СЕБЯ Шэг Х (после) У=1 У=5 У=4 К9. [Уменьшить цифры.) Уменьшить каждую не равную нулю цифру десятичного предстевчеияя числа Х на единицу. К10. [Модифицировать не 99999.] Если Х < 104, присвоить Л 4- Ха + 99999; иначе присвоить Х 4- Х вЂ” 99999. К11, [Нормировать,] (Нв этом шаге Х не может быть равным нулю.) Если Х ( 100, присвоить Х 4- 1ОХ и повторить этот шаг. К12.
[Модификация метода средин квадратов.] Заменить Х на (Х(Х вЂ” 1)/104] пкк1 10'0, т. е. средними 1О цифрами числа Л (Х вЂ” 1). К13. [Повторитьу] Если У > О, уменьшить У на 1 и возвратиться к шагу К2. Если У = О, алгоритм завершен. Значение числа Х, полученное нв предыдущем шаге, н будет желаемым "случайным" значением. 1 (Программа, реализующая этот алгоритм, обещала быть настолько сложной, что тот, кто прочел бы ее распечатку, без толковых комментариев не смог бы в ней разобраться,) После рассмотрения всех преобразований алгоритма К не кажется ли правдоподобным, что можно было бы обеспечить бесконечное снабжение невероятно случайными числэми7 Нет! Нэ самом деле, когда этот алгоритм впервые был реализован иа компьютере, он почти немедленно сошелся к 10-значному числу 6065038420, К1 КЗ К4 К5 Кб К7 КЗ К9 К10 К11 К12 Кб К7 КЗ КЯ К10 К11 К12 К12 Кб К7 К8 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 КЬ Кб К" К8 КЯ К 10 К11 К12 КН К12 К4 К5 Кб К7 КЗ К9 К10 К11 К12 Х (после) 1107855700 И07755701 1107?Ь5701 1226919902 0048821902 9862877579 7757998628 2384626628 1273515517 1273415518 1273415518 5870802097 5870802097 3172562687 1540029446 7015475446 2984524554 2455429845 2730274845 1620163734 1620063735 1620063735 6065038420 которое по невероятному совпадению преобразовалось само в себя по алгоритму (табл.
1), С другим стартовым числом последовательность начала повторяться после 7401 значения с периодом длиной 3178. Мораль этой истории в том, что случайные числа не следует генерировать методом, выбранным наудачу. Не мешало бы использовать немного теории. В следующих разделах будут рассмотрены генераторы случайных чисел более высокого уровня, чем метод средин квадратов и алгоритм К. Соответствующие последовательности гарантированно обладают желаемыми случайными свойствами и не вырождаются.
Мы исследуем некоторые причины такого, похожего на случайное, поведения, а также покажем, как можно обращаться со случайными числами. Например„одно из наших исследований будет посвящено программе, которая тасует смоделированную на компьютере колоду карт. В разделе 3,0 приводятся итоги к этой главе и содержатся некоторые библиографические источники. УПРАЖНЕНИЯ 1. (ЗО) Предположим, вы хотите получить случайную десятичную цифру.
Какой из следующих метадов вы выберете? а) Откроете телефонный справочник, ткнув пальцем куда-нибудь, выберете первый попавшийся номер телефона и возьмете младгеую цифру (ЧиФру младшего реэрлОе) этого номера. Ь) Поступите, как в (а), но выберете младшую цифру номера шлракицм, с) Пшштцте игральную кость в форме нкосээлра, имеюшую двадцать граней, которые помечены цифрами О, О, 1, 1,...,9,9. Когда кость остановится, выберете верхнюю цифру. (Для катания игральной кости рекомендуется использовать стел с хорошо натянутым сукном.) е) На одну минуту выставите счетчик Гейгера у источника радиоактивного излучения (предварительио обезопасив себя) и воспользуетесь младшей цифрой показаний счетчика.
Предпсьчагэется, что на счетчике Гейгера представлены числа в десятичной системе счисления и вначале на ием был установлен нуль. е) Бросите быстрый взгляд на свои часы и, если секундная стрелка нахсдится между Ои и 6(п + 1) сшгундами, выберете цифру и. () Попросите приятеля задумать любую цифру и воспользуетесь ею.
6) Попросите врага задумать любую цифру и воспользуетесь ею. Ь) Предположите, что 10 лошадей участвуют в забеге и вам о ннх абсолютно ничего не известно. Присвоите каждой лошади в произвольном порядке номер от 0 до 9, а после забега выберете в качестве случайной цифры номер победителя.
2. (э(29) Какова вероятность тоге, что в случайной последовательности из миллиона десятичных цифр каждая возможная цифра встречаетск ровна 100 000 раз? 3. (10) Каное число следует за 1010101010 в метеле средин квадратов? 4. (00) (а) Почему на шаге К11 алгоритма К значение Х ие может быль равно нулю? Какая ошибка возникла бы в алгоритме, если бы Х мог принимать значение "нуль"? (Ь) Используя табл. 1, установите, что происходит, когда алгоритм К применяется повторно со стартовым значением Х = 3830951656.
6. (15] Объясните, почему в любом случае, даже если совпадение, приведенное в табл. 1, не произошло, алгоритм К не сможет выдать бесконечную последовательность глучайнмх чисел в том смысле, что любая последовательность, генерируемая алгоритмом К, стансе в конце концов периаднчной. 6. [МУ1] Предположим, что необходимо получить последовательность целых случайных чисел Хе, Хм Хы ... на интервале 0 < Х„< гп.
Пусть у'(х) — любая функция, такая, что неравенство 0 < х < гл влечет 0 < Г(х) < щ. Рассмотрим последовательность Х +~ = у(Х„). (Примеры таких последовательностей — метсщ средин квадратов н алгоритм К.) а) Покажите, что такая послсдовательносчь периодична в том смысле, что существуют числа Л и д, для котормх значения Хо, Х1, ..., Хк, ..., Хк.~.ь-1 различны, однако Х„ех = Х, когда и > д. Определите возможные максимальное и минимальное значения д и Л. Ь) (Р. флойд (В..
%. Г1оугЦ.) Покажите, что существует такое и ) О, что Хк ж Лэ„и наименьшее такое значение и лежит в интервале д < о < д + Л. Волее того, значение Х„является единственным в том смысле, что если Х = Хз„и Л, = Хы, то Х. = Х . с) Используя идеи (Ь), оэставьте алгоритм вычисления р н Л для любой заданной функции ~ н любого заданного Хе, используя только 0(р+Л) шагов и только ограниченный объем памяти.
7. [М91) (Р. П. Врент (В. Р. Вгещ), 1977.) Пусть 4(п) — наибольшее целое число, такое, что 4(п) < и, 1(п) = 2", где й — целое число. Так, например, 4(15) = 9 и ЯЯп)) = 4(п). а) Покажите, что в терминах обозначений упр. 6 существует такое и ) О, что Х„ж Лц >-и Найдите формулу для наименьшего такого и в терминах чисел р и Л, определяющих период.
Ь) Примените этот результат для составления алгоритма, который может быть нсзюльзован совместно с любым генератором случайных чисел типа Х„е~ = /(Х„), чтобы предотвратить пиклическую неопределенность. Вашему алгоритму следует вычислять период длиной Л и использовать только небольшой объем памяти — вы просто не должны заполнять всю память вычисленными значениями последовательности! 9. [9У] Выполните полную проверку метода средин квадратов для случая, когда десятичные числа состоит нз двух цифр. а) Можете начать процесс с любого из 100 допустимых чисел 00,01,...,99.
Сколько из этих значений в конечном счете приведут к повторению цикла (зацикливанию) 00, 00,...? [??ример. Начиная с числа 43, получим последовательность 43, 84, Об, 02, 00, Оо, 00, ....1 Ь) Сколько существует финальных циклов? Каков размер самого длинного цикла". с) Какое начальное значение (или значения) даст наибольшее число различных элементов, прежде чем последовательность повторится? 9. [МЦ] Докажите, что метод средин квадратов, использующий 2п-значные числа в Ь-ичной системе счисления, имеет следующие недостатки: если последовательность включает любое число„в котором и старших значащих цифр — нули, то последующие числа становятся все меньше и меньше, пока не превратятся в пули. 10.
[М1б] Пусть выподияхптзг прелпгьзожения предыдущего упражнения. Что можно сказать о последовательности чисел, следующих за Л, если младшие значащие п цифр числа Х равны нулю? Что если и+ 1 младших значащих цифр равны нулю? ь 11. [Мйб] Рассмотрим последовательности генераторов случайных чисел, имеющих вид, описанный в упр. 6. Если выбрать у(х) и Хе наудачу (другими словами, если предположить, что каждая из гл возможных функций у(х) равновероятна и каждое из пт возлгожиых значений Хо равновероятно), то какова вероятность того, что последовательность в конечном счете выродится в цикл длиной Л ж 1? [Замечание.
Предположения этой задачи дают повод заауматься о "случайности" генераторов случайнык чисел такого типа. Можно ожцдать, чта метод, подобный алгоритму К, отчасти ведет себя так же, как рассмотренный здесь генератор; ответ на эту задачу дает колоссальное число совпадений в табл. Ц ь 12. [М31] Какова средняя длина финального цикла, если выполняются предположения предыдущего упражнения? Какова средняя длина последовательности до вхождения в цикл? (В обозначениях упр.
б необходимо определить средние значения Л и д + Л.) 13, [М49] Если 1 (х) выбрана наудачу, как в упр. 11, какова средняя длина самого длинного цикла, полученного путем варьирования начального значения Ха? [Замечанае. Мы ухсе рассмотрели аналогичную проблему для случая, когда 1(х) — зто случайные перестановки; см. упр, 1.3.3-23.] 14.
[МВВ] Если 1(х) выбрано наудачу, как в упр. 11, каково среднее число различных финальных циклов, полученных в результате варьирования начальных значений? [См. упр, 8, (Ь).] 15. [М15] Если 1(х) выбрано наудачу, как н в упр. 11, чему равна вероятность, что нн один нз финальных циклов не имеет длину, равную 1, невзирая на выбор Ха? 16. [15] Последовательность, генерируемая, как в упр. 6, должна повторяться после того, как было сгенерировано не более гл значений, Предположим, что мы обобщим метод таким образом, что Х„+~ будет зависеть от Х„с так же, как ат Х„; формально пусть 1г(х, у)— такая функция, для которой 0 < х, 9 < гл влечет неравенства 0 < 1(х, 9)< пь Последовательность ст!юится так: сначача произвольно выбирают Ха и Х|, а затем полагают, что Х„+, — 1(Х„,Х„,), где п>0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
