Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 54
Текст из файла (страница 54)
[М22) (Д. Зейлбергер (П. Ее1)Ьегбег).) Найдите рекуррептиую формулу, аиалогичиую (9), для вычисления коэффициентов Иг(т) = И(х) 1г(де)... $'(9"' 'з) при заданных д и гп и коэффициентов 1 "(а) = 1+ 1(х+ (гэз~+ .. Предполагается, что 9 ие равно корню из единицы. ь 28. [НММб) Ряд диритле — это сумма вида (г(з) = К/1*+1гз/2*+Из/3" + -; произведение У(х) И(к) двух таких рядов — это ряд Дирихле Иг(х), у которого И'» = / (/ар»/а щ» Обычные степеипме ряды — частный случай рядов дирихле, так как ре+ Нх+ 12хз+ Узка+ ° = 1ге/1'+ К/2'+ 1'з/4'+ тз/8'+, когда х = 2 '. На самом деле рядм Дирихле эквивалентны степенным ридам вида И(ан зт,...
) с провзвольцым множеством переменных, где хь = р,, ' и рь — й-е простое чигло. Нюйдите рекурреитиое соотношение, с помок~ью которого можно обобщить (9) и формулу из упр. 4, если предположите» что задан ряд Дирихле (Г(х) и что нужно вычислить (а) Иг(з) = И(э), когда 1:1 = 1; (Ь) И'(х) = ехрр(х), когда Ъ'~ = 0; (с) И"(х) = )пр(г), когда т'~ = 1.
[указание. Пусть 1(п) — общее число простых множителей и, включая кратные, и пусть б 2» И /и' = 2,„1(п) т»/и'. Покажите, что операция а — аналогична производной, например бе1 оо = е~ ~Нб$'(х).) 'В то, безусловно, мысль, — с нвкстООым интЕРЕСОм пооизнес Г1уаро.— Да, да, я играю Роль компьютера, который питается информацией," "и, предположим, вы получавте все неправильные ответы", — сказала миссис Оливео. ээтО НЕВОЗМОЖНО, — ВОЗРаэнп ЭРКЮЛЬ ЛУаор,— компьютеоы всего лишь сортируют факты." "Это нв предполагается, — сказала миссис Оливер,— но следует удивляться вещам, которые иногда происходят." — АГАТА КРИСТИ (АВАТНА СНУЕТ!Е), Лоием в честь дня всех святых (1969) Кажется невозможным, что некотоРый Факт становится оеальным после Ряда фактов без той власти, которая впервые их создала, — ЗдВАРд стиллинГюлит (еОэтдйО бт!шнбрсеет).
начала таинства, 2:3:2 (1662) ОТВЕТЫ К УПРАЖНЕНИЯМ Это единственная ветвь математики, я полагаю, в которой хооошие автооы неоднократно получали совершенно ошибочные результаты. . Сомневаюсь, что есть хотя бы адин пространный трактат о веооятностях, сушествуюших в поиоаде, который не садеожал бы Решений, абсолютно недоказуемых. — ч. с, пиРс (с, 8, Рессчсе), Рорисаг Бс!епсе ааопсп!у (1878) ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 1. Зсщача средней слонсности для читателей с математическим уклоном, 8.
(Решение Роджера Фрея (Кобе! Ггуе), полученное после акала 110 часов вычислений на Соппессюп МасЬше в 1987 году): 958004 + 217519с + 4145б0' = 4224814, 4. Один из читателей рукописи втой книги сообщил, что нашел поистине замечательное доказательство. Но, к сожалению, размер его заметки был слишком мал, чтобы вместить его. РАЗДЕЛ 3.1 1, (а) Вообще говоря, вы потерпите неудачу, так как владельцы телефонов па возможности выбирают круглые" номера. Версжтно, в некоторых райоссвх телефошсые номера устанавливаются случайным образом.
Но в любом случае было бы ошибкой пытаться получить несколько последовательных случайных чисел на одной и тай же странице, тск как один и тот же телефонный номер часто вносится в список несколько раз палрял. (Ь) Вы воспользуетесь левой или правой страницейу Допустим, вы выберете номер на левой странице, разделите его на 2 и возьмете правую цифру. Общему числу страниц следовало бы быть кратным 20, но давсе если зто так, данньсй метод все равно обладает определенными недостатками. (с) Маркировка на гранях кости несколько нарушает симметрию игральной кости, но для практических целей этот метод вполне удовлетворителеа (и был использован автором при подготовке нескольких примеров для этой к!сиги). См.
Масй, Сошр. 15 (1961). 94-95, где обсуждаются игральные кости в виде икосаэдра. (с)) (Этот сложный вопрос включен в качестве сюрприза.) Чисю ие вполне равномерно распределено. Если среднее число зарегистрированных частиц в минуту равно пс, вероятность того, чта счетчик зарегистрирует й частиц, равна е" ™пс~//с! (пуассановское ршлределение); тюс что цифра "0*' выпадает с вероятностью е ' 2 ь>вассе~/(10!с)! н т.
л. В частности, младшая цифра будет четной с вероятностью е совЬсп = -'+ -'с"~ы и она никогда не равна -' (хотя ошибка пренебрежительно мала, когда т велико). Однако совершенно законно взять десять наблюдений (ше,..., гпэ) и затем выбрать то /., для которого т, строго меньше, чем т, для всех 1 ~ /д повторить операцию, если минимальное значение появляется более одного раза (см. (Ь)), (е) Сокей; подходит, если время, прошедшее с момента выбора цифры, случайно. Тем не менее возможны искажения в граничных случаях. (68) Нет. Люди обычно выбирают определенные цифры с большей вероятностью (см.
7). (Ь) Сзкей; при таком распределении номеров вероятность того, что заданная цифра присвоена выигравшей лошади, равна —,е. 2. Число таких последователыюстей равно цолиномивлыюму коэффициенту 1000000! / (100000!) 'е; таким образом, искомая вероятность равна этому числу, деленному на 10'~~~~, число всех последовательностей, содержащих миллион цифр. Используя формулу Стирлинга, найдем, что вероятность близка к 1/(16я410ээЯяя) щ 2.56 х 10 эе. Грубо говоря, это происходит в одном случае из 4 х 10ээ. 3. 3040504030. 4.
(а) На шаг К11 мы попадаем только после шша К10 или К2, н в любом случае легко обнаружить. что Х не может равняться нулю. Если бы Х мог принимать значение "нуль" ва этом шаге. то алгоритм никогда бы не закончился (программа зациклилась бы). (Ь) Если Л установлено равным 3830951656, то вычисления подобны таким же вычислениям шагов нз табл. 1. Разница состоит в том, что мы попадаем в состояние К11 У+ 1 = 7 раз вместо У+ 1 = 4 раз; следовательно, 3830951656 -э 5870802097. Аналогично 5870802097 -ь 1226919902 -+ 3172562687 э 3319967479 ~ 6065038420 -+ 6065038420 -+ 5. Существует только 10'е десятизначных чисел; некоторые зиаченця Х должны повториться на первых 10ге + 1 шагах.
И коль скоро какое-нибудь значение повторится, последовательность поз~ориг свое прежнее поведение (появится перяодичность). 6. (а) Используя те же аргументы, что и в предыдущем случае, легко показать, что в последовательности должно в конечном счете повториться одно из значений. Пусть в первый раз такое повторение произойдет на шаге д + Л, где Х,.ех = Х„. (Это условие определяет д и Л.) 54ы получим 0 < д < ш, 0 < Л < ш, д + Л < тв. Значения д = О, Л = т достигаются тогда и только тогда, когда / является циклической перестановкой; н д = т — 1, Л = 1 встретится, например, ели Хе = О, /(х) = я+ 1 для я < ш — 1 и /(гл — 1) = т — 1. (Ь) Для г > и имеем Х„= Л„тогда и только тогда, когда г — и кратно Л и и > д. Значит, Хъ = Х„тогда и только тогда, когда и кратно Л и и > д.
Ожидаемые результаты слелуют теперь незамедлительно. (Замечание. Это, в сущности, доказательство известного математического утверждения: "Степенн элемента конечной полутруппы включают единственный идемпотентный элемент: возьмите Х~ ж а, /(я) = ая".) (с) Как только и найдено, генерируем Х; и Х„„., для 1 > О до тех пор, пока найдется первое Л, = Х„ец тогда д = б Если ни одно из значений Х„ь, при О < 1 < и не равно Х„, значит, Л = и, иначе Л вЂ” наименьшее из таких б 7.
(а) Наименьшее значение я > О, такое, что и — (4(п) — 1) кратно Л и Ю(п) — 1 > д, равно и = 2це '"ы+ к ~11 — 1+ Л. (Это можно сравнить с наименьшим и > О, при котором Хеь = Л, т е. Л((д/Л) + бее).) (Ь) Начните со значения Х = У = Хе, Ь = ш = 1. (На ключевом месте в этом алгоритме получим Х = Хэ ь м 1' = Х ~ и ш 4(2т — 5).) Для генерирования следующего случайного числа выполним такие шаги, Установим Х <- /(Х) и й е- й — 1. Если Х = У, остановка (двина периода Л равна гя — й). Если й = О, установим У е Х, ш е- 2ш, й е- т.
Получим Х. Замечания. Брент (Вгевс) также рассматриваэ более общий метод, в котором следующие одно за другим значения У = Хы удовлетворяют п~ = О, пыл = 1 + [рп;], где р — любое число, большее 1. Он показал, что иаилучшее значение р, приближенно равное 2.4771, озкращает около 3% итераций по сравнению с ситуацией, когда р = 2. (См. упр. 4.5.4-4.) Однако метод, описанный в (Ь), имеет серьезные иедостатки, так как можно получить много неслучайных чисел, прежде чем прекратится геиеририрование, например в особенна неудачном случае, когда А ы 1, д = 2". Метод основан на идее Флойда (Р!оуд) из уцр, 6, (Ь): присваивать значения У = Л'ь и Х = Х при и ж О, 1,2, Потребуется несколькобольше функциональных оценок, чем для метода Брента, но при использовании метода Флойда работа остановится прежде, чем любое число появится дважды.
С другой стороиы, если / неизвестно (иэпример, если получены значения Хе, Хм... из постороинего источника) или если сложно использовать /, то в этом случае предпочтительнее применять слелующий обнаруживающий циклы алгоритм, который был предложен Р. В. Госпером (К, 1А'. Соврет): для того чтобы получить Х„, используют вспомогательную таблицу зиачепий Те, Тм .,., Т, где пг = [!Зи], Сначала присвоим Те г- Ле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
