Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 55
Текст из файла (страница 55)
Для и 1,2,... сравниваем Х„с каждым из Та,, Тре,,1; если в этой таблице ие найдется числа, равного Х„, то присваиваем Тм„1 '- Х„, где е(п) = щах(е [ 2' делит на и+ 1). Но если иайдетсе такое Тю что Х = 2ы то А = и-шах(! [ ! < и и е(!) = Ь). После присвоения Х„знгчеиия Тм„> последовательно сравниваем это значение с Х„+~, Х +г,..., Х„+ и м.~. Поэтому процедура остаиовится сразу же после геиерироваиия Х„архе!, где У > 0 является минимальным среди тех,г, для которых выполняется неравенспю е(д + у) > [16А] — 1.
При использовании этого метода ии сдио из значеиий Х ие появляется более двух раз и не более чем шах(1, 20е"! ') значений случайных чисел появится более одного раза. [М1Т А1 ЬаЬогагогу 54ешо 239 (РеЬгпагу 29, 1972), Насй 132.] Р. Седгевик (К. Яег!Зеч(сЬ), Т. Г. Шиманский (Т. О.
ЯхушавэЫ) и Э. Ч. Яо (Л. С. Уао) проанализировали более сложный алгоритм, основанный на использовании параметров гп > 2 и 9 > 1: вспомогательные таблицы размерности т включают Ле, Лм, Лэь на момент, когда Л'„вычислено, где Ь = 2пх "Г ! и д = [и/Ь] — 1. Если и шог! 95 < Ь, Х„ сравнивается с табличными данными; в конечном счете равенство выполияется и мы вычисляем д и А, произведя не более чем (9+1)2цэ~" ~" ц+' вычислений /. Если вычисление / отиимаег время т и если проверка равенства Л с табличными данными отнимает время гг, то д может бмть выбрано так, что общее время счета будет равно (д + А)(т+ О(в— ')'г~); если и/г = О(ги), то время счета оптимкэьио.
Более того, Х„пе вычисляется, пока не выполнитгя неравенство д + А > птп/(пг+ 49 + 2). Итак, этот "диалоговый" (оп!ше) метод можно использовать для гарантированного получения различных случайных чисел, так что для получения одного числа требуется только 2 + 0(гл 'г~) вычислений функции. [Я1СОМР 11 (1982), 376-390.] 8. (а Ь) 00,00,...
[62 начальных значения]; 10,10,... [19]; 60,60,... [15]; 50,50,... [1]; 24, 57. 24, 57,... [3]. (с) 42 или 69,' оба эти числа дают множества, содержашпе 15 различных зиа юний, а именно: 42 или 69, 76, 77, 92, 46, 11, 12, 14, 19, 36, 29, 84, 05, 02, 00. 9. С того момента, когда Х < Ь", получаем Х < Ь~", и средины квадратов равиы [Х'/Ь"] < Х'/Ь". Если Л > О, то Х'/Ь" < ХЬ"/Ь" = Х. 10. Если Л = аЬ", то следующее число цоследовательиости имеет ту же форму; оио равно (аэ шодЬ")Ь". Если а кратно всем простым мповсителям Ь, последовательность вскоре выродится в нуль; иначе оца выродится в циклы чисел такой же формы, как число Х. Другие факты о методе средин квадратов найдек Б, Йенссеиом (В.
Лапээоп, Балдою )тибет Оелегагогэ (ЯгосЬЬойп: А1пщтмс Зс Ъ'1Ьэе!1, 1966), Яесгюп ЗА). Тем, кто интересуется магическими свойствами чисел, небезынтересно будет узнать, что число 3792 является самовоспроизводящим числом в четырехзначном методе срадин квадратов, так как 3792 = 14379264; более того, как заметил Йенссен, оно также <самовоспроизводимо" в другом смысле, поскольку его разложение на простые множители имеет вид 3.
79 2з! 11. Вероятность того, что Л = 1 и р = О, — это вероятность того, что Х1 м Хе, аименно— 1/гп. Вероятность того, что Л ы 1, и = 1 или Л = 2, р = О, — это вероятность того, что Х~ Ф Хе и того, что Хг принимает определенные значения, т. е. равна (1 — 1/гн)(1/гл). Аналогично вероятность того, что последовательность имеет любые заданные д н Л, является функцией только от р+ Л, а именно; Р(н, Л) = — П ~1 — — ).
~бе<>+х Вероятность ино,что Л = 1,задается в виде где Ц(гп) определено в разделе 1.2.11.3, равенство (2). По равенству (25) нз того же раздела данная вероятность приблилсенно равна |/я/2гп 1.25/~/т. Шанс, что алгоритм К будет вести себя, как в рассмотренном примере, равен одному из 80000; автора постигла явная неудача См. другие комментарии о "колоссвльности" в упр.
15. 12. ~ ЛР(д,Л) = — (1+3~1 — — ) +6(1 — — ') ~1 — — )+".) = о«я<м (См. предыдущий ответ. В общем случае, если /(ае,ам,) = 2 ° >ее Пьэл(1 — я/гн) то У(ое,ом ) = по + /(анпы...) — /(ам 2аы, ..)/пц применим это тождество с а (я+ 1)/2.) Поэтому среднее значеняе Л (и в силу симметрии Р(р,Л), а также д+ 1) приближенно равно 1/ягн78 + 1, Среднее значение р + Л равняется точно (4(гл), что приближенно равно,~ ягн/2 — -'. (Альтернативные выводы и другие результаты, включая асимптотическис значения моментов, приводятся в А.
Каророгс, Впзб МасЛ. В)орбуз(сз 10 (1948), 145-157, н В. НаггЬ, АппаЬ Магб. Ясак 31 (1960), 1045 — 1062; см. также Соболь И, М., Теория вероятностей н ес применения 9 (1964), 333-338. Соболь обсуждает асимптотику длины периода для более общей последовательности Х ь1 = /(Х„), если и ~ Опомодулюгн, Х .~.~ = д(Х ), если и эз Опомодулюсп, когда одновременно и /, и д случайны.) 13. (Пардом П. (Рап1 рпгбою» и Вильямс Дж. (Лопп Ч'1П1ащз), Инне. Аюег. Маей 8ос.
133 (1968), 547 — 551.) Пусть Т „— число функций, имекнцих н циклов единичной длины и не имеющих более длинных циклов. Тогда (Это совпадает с („)г(гн,тл — н) в упр, 2.34.4-25.) Любая такая функция получается из такой же функции в результате перестановки н циклов единичной длины. Отсюда К.>, Т-.'=-- Пусть Р„ь — число перестановок и элементов, самый длинный цикл которых имеет длину Й. Тогда число функций с максимальным циклом длиной )с равно 2 „>, Т Р ы Чтабы получить среднее значение Л, вычислим сумму 2 ь>, ) „>, ИТ <»Р ы которая, как следует нз упр.
1.3.3-23, равна 2 „>, Т „и!(си+ 11<+ О(н ')), где с .62433. Суммируя, получим, что среднее значение равно сЦ(пг) + -'с+ О(гпмт). (Это выражение, в сущности, пе болыке, чем среднее значение й, когда Ле выбирается наудачу. Среднее значение щах р асимцтотнчески равно Щгп) !п4 и среднее значение шах(д + Л) асимптотически равно 1.9268Я(гп); см. г!а)о)ес апс) Ой!уз)со, /.есгпге йгоггн !и Сошр. Яс!.
434 (1990), 329-354.) 14. Пусть с,(гл) — число функций, имеющих точно г различных финальных циклов. Из рекуррентного соотношения сг(ш) = (ш — 1)! — 2 „(„)(-1) (гп — /г) св(гп — й), которое можно получить в результате подсчета числа функций, образ которых содержит нс более чем гп — /г элементов, следует, что с~(ш) = т~ 'Я(т). (См. упр.
1.2.11.3-16.) Другой способ получения сг(гп), который, возможно, более элегантен и показателен, приведен в упр. 2.3,4А-17. Значение с,(гн) может быть определено так иге, как в упр. 13: Теперь можно вычислить требуемое среднее значение (см. упр. 12): 1 гл — 1 тп — 1 ги — 2 В„м — ~//, +2Оэ +зн,— — +" ) ш ш гп 1т — 1 1пг — 1 го — 2 — 1+ + + 2 гл 3 гп т Последняя формула была получена несколько иным путем М. Д. Крускалом (см.
Магба 71 Кгпв)ш), йММ 61 (1954) „392-397). Используя интегральное представление он доказал асимптотическое соотношение !нп, .„н(Š— —,' !пго) = —.'(7 ь !п2). Другие результаты, а также ссылки на литературу, можно найти в работе,!о)гв 11!огбав, йппа/з Маг)ь Бгак ЗЗ (1962), 178-185.
15. Вероятность того, что /(х) 74 х для всех х, равна (ш — 1) /т'". а это приблизительно равно 1/е. Сущеспюваиие самоповторяющегося значения в азгорнтме, подобном алгоритму К, не является поэтому ьколоссавьным"; его вероятность равна 1 — 1/с - .63212. "Колоссальным" было только то, что автору удалось получить такое значение Хе при случайном выборе (см. упр.
1Ц. 16. Погледователыюсть повгоризтл, когда пара следующих один за другим элементов встретится второй раз. Максимальный период равен т~. [См. следующее упражнение.) 17. После произвольного выбора Ха,, Хь-~ пусть Хь~ы = /(Х„,, Х„ь+~), где 0 < хм...,хь < гл влечет то, что 0 < /(х~,...,хь) < т. Максимальный период равен шь. Это очевидная верхняя граница, однако не очевидно, что она достижима, для конструктивного доказательства того, что опа достижима для подходящей функции / (обратитесь к унр. 3.2.2-17 и 3.2.2-21; численный метод приводится в уор.
2.3А.2-23). 18. Метод такой же, как в упр. 7, но используйте цепочку нз й элементов (Х„,..., Х„..гз,) вместо элемента Л . 20, Достаточно рассмотреть простое отображение 9(Х), определяемое на шагах К2-К13. Следуя в обратном порядке от числа 6065038420, получим в общей сложности 597 решений; наименьшим чнслолг является 0009612809, а наибольшим -- 9995371004, 21.
Можно работать с д(Х), как и в предыдущем упражнении, но сейчас необходимо запустить функцию в прямом порядке. Существует интересная взаимосвязь между временем и пространством. Используя несколько мегабайтов памяти, автор в 1994 году проверил это предположение для всех начальных значений, меньших, чем 0000165181, но решил подождать несколько лет, прежде чем продолжить исследования, так квк компьютеры становились все больше н мощнее. Заметим, что механизм огата К) способствует уменьшению периода. Существуют Л' с большим числом значений, переходящих в них, например 512 значений Х = ебееееьеэ* на шаге К2 приведут к шагу К10 со значением Х <- 0500000000. С. Флюхер (Я.
г'(о)пег) обнаружил друэне фиксированные точки алгоритма К, а именно — значение 5008502835(|). Он также нашел третий цикл 0225923640 -ь 2811514413 -э 0590051662 -+ 0225923640, обьединяющий семь циклов. Только 128 начальных чисел ведут к повторению значения 5008502835, Алгоритм К вЂ” это улсаснма генератор случайных чисел| 22. Если 7 — действительно случайная функция, то это было бы идеально; но как построить такую 17 Функция, определенная алгоритмом К, работала бы намного лучше по этой схеме, хотя она действителыю имеет неслучайные свойства (см, предыдущий ответ).
23. Функция / переставляет свои циклические элементы: пусть (хэ,,хь-~) является "необычным" представлением, обратным к этой перестановке. Затем щзодолжим определять гь,..., гм-и как в упр. 2 3.4 4-18. (См. з. Согл 5|лагат|а| Тавоту 8 (1970). 361-375) Так, еглн гл = 10 и (7(0),...,1(9)) = (3,1,4,1,5,9,2,6,5,4), получим (хо, .-.хэ) = (4.9,5,1,1,3.4,2,6,5); если (зе,...,хэ) = (3,1,4,1,5,9,2,6,5,4), получим (У(0),...,У(9)) =- (6,4,9,3, 1, 1,2,5,4,5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
