Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 61
Текст из файла (страница 61)
Х2. Пусты' — минимум для а; > О и ! > О, Реализуйте программу У для у = ! + 1, ..., !», пока а» > О. ХЗ. Егли ав > а», /(х»,...,х») = ао; иначе, егли ао > О, /(хм...,х») = ао — 1; иначе /(хц х») = а* ! Ъ" 1. Присвоить !»- О. (Программа на шагах У1-УЗ проверяет лексикографическое отношение (ац..,,а;е»») > (аз„...,аз+»»), Убывание а» необходимо, чтобы сделать зто неравенство верным.
Предполагается, что а»т» = а», а»+з м аз и т. д.) У2. Если асы > а!»и выйти из программы. Иначе, если у+! = л, присвоить а»» — а»эь Иначе, если а» и ы а;+ц перейти к шагу УЗ. Иначе, если,у + ! > й, уменьшить а» на 1 и выйти из программы. Иначе присвоить а»»- О и выйти из программы. Ъ'3. Увеличить ! на 1 и возвратиться к шагу У2, если ! < !», $ Эта проблема впервые была решена Г. Фредриксеном (Н. ГгебНс)шеп) для гл = 2 [Х СошЬ!лагос!а! Т!»еогу 9 (1970), 1-5; А12 (1972), 153-154). В этом частном случае »ьтгоритм проще и может быть задан с х-разрядным регистром.
См. также работу 8. Х1е, Р!эсгесе Арр)!еб Маей. 16 (1987), 157-1 77. 30. Из упр. 11 следует, что достаточно показать, что длина периода по модулям 8 равна 4(2" — 1). Это будет выполняться тогда н только тогда, когда хт(т"-0 В 1 (по модулям 8 и /(х)), а также тогда и только тогда, когда хэ»-' В 1 (по модулям 4 и /(х)). Запишем /(х) = Ях~) + х/»(х~), где /»(х~) = »(/(х) +/(-х)). Тогда /(х) + /( — х) ш 2/(х~) (по модулю 8) тогда и только тогда, когда /,(х) +х/,(х) ьд /(х) (по модулю 4); и последнее условие имеет место тогда и только тогда, когда /»(х) ш -х/ (х) (по модулям 4 и /(х)), так как /„(х)т + х/ (х)» = /(х) + 0(х»"').
Более того, работая по модулю 2 и /(х), мы получим /»(х)~ ш /,(х~) ш х/,(х~) щ хт Ях)~. Следовательно, /»(х) ш хэ~"~/,(х). Поэтому /,(х) щ хг»/,(х)~ (по модулям 4 и /(х)), отсюда следует утверждение указания, Рассуждаи подобным образом, можно доказать, что хэ ш х (по модулю 4 и /(х)) тогда и только тогда, когда /(х) + /(-х)~ и 2(-1)~/(-х~) (по модулю 8).
(Ь) Условие может выполняться только тогда, когда ! нечетко и !ь ы 2!. Но в таком случае у(х) является первообраэиым полииомом по модулю 2, когда 1 ы 2. [Маьй. Сошр. 63 (1994), 389-40Ц 31. Соотношение Л;, ш (-1)щЗз" шо»12' вмполняется для некоторых 1'„и Я по теореме 3,2.1.2С. Следовательно„К, = (т'-ы+ 1 -ьь) шод 2 и З» = (я -зь+ я -ьь) шов(2' з. Так как Х» нечетко тогда и только тогда, когда Л» шобб ж 3 или 5, из прель»пущего упражнения следует, что длина периода ранна 2' (2 — 1), 32. Можно ие обращать внимания иа шод вь и вернуться к этому позже. Производящая фупкпия д(з) ж 2» Х»з» вЂ” это полипом, кратиый 1Д! — ззь — зьь); поэтому ~„Хз»з " = 1(д(з)+д(-з)) — это поливом, делениььй иа (1-з -зьь)(1-зз +з' ) = 1 — 2з ь+зь — з"ь. Первое требуемое ренурреитное соотношение поэтому имеет вид Хь» = (2Х»! -щ!— Х»ш зь>+Ли» ьы)шов)га.
Аналогично 2"„Лз»гь» = 1(д(з) + д(ыз) + д(ы"з)), где ы = ез Ыь, и можно найти, что Хь» = (ЗХзщ ь! — ЗХз! -ш1+ Хз! -ы!+Лз!»-ы!) шов!ш ЗЗ. (а) д»~~(з) = з'д»(з) (по модулю т и 1 + зз' — зьь) иидукцией по Ь (Ь) Так как э~шов)(1+за зьь) 792зз+зь+17зв+715зь+Збз»»+за»+304з»в+210з»ь+105ззз+ 402ззь + 1бзю + 1237ззь + 9ззь + Ьбззг + 1001зьь + 120зяь + зьь + 455зяг + 402зьв + 120зьь (см, алгоритм 4.5,10), то получим Хьвв = (792Лз + Хь + .
+ 12ОЛы) шос! т. [Интересно сравнить подобную формулу Хьвь = (Хь + ЗХь + Х»4 + ЗХз» + 4Хзь + Хьь) шолти с "прореженным" рекурреитиым соотношением для (Лз») в предыдущем упражнении. Метод Люшера для геиерироваиия 1бб чисел, в котором используются только первые 55 чисел, очевидно, не лучше идеи генерирования 1б5 чисел с помощью только Лз, Хв,, Хшь ] 34. Пусть 9» = О, д~ = 1, д»ю = а1» + ад» и Тогда выполняется равенство (,) в~ » (»"„~ ьь, )~ Х» = (д»+»Хо+ад»)!(д Хо+ад»») и х» пюь! Дх) ш д я+ ад»» для и > 1. Таким образом, если Ль = О, то Х = 0 тогда и только тогда, когда х» пюь(у(х) — ие равная нулю константа.
35. Из условий (») и (й) получаем, что 7(х) иеприводима. Если 7(х) = (х — г»)(х — гз) и гь гз и О, то х""» ш 1, если щ ь» гь, и хг ш гм если г» = гз. Пусть 5 — первообразиый корень поля, имеющего р элементов, и предположим, что ь = с»с» + а». Квадратичные полииомы, как было установлено, — зто точно поли- номы 7»(х) = хз — с»х — а», где 1 ( й < рз — 1 и й .1 р+ 1. (См. упр. 4.б.2-16,) Каждый полипом появляегся для двух значений !в; следовательно, число решений раэио з (р ) Пь»»+к ь»р»»»»»(! 1Й)' 36. В даином случае Х» всегда нечетко, поэтому Х„' существует по модулю 2'.
Последовательность (д ), определенная в ответе 34, имеет вид О, 1, 2, 1, О, 1, 2, 1, ... по модулю 4. Справедливы такжедз ыд»(д»ь»+ад„~) идз» =ад»,+д»,поэтому дз +» — адз„~ ж (д»+» ад -»)(д»+»+ад»+»). Следовательно, д +»+ад„+» ш 2 (по мазулю 4), когда и чепю. Получим, что дм — это нечетное кратное 2' и дз +» — адз. » — это нечетное кратное 2'+~ для всех е > О. Поэтому дз +ади ь ш дз.ю +адз +2'+' (по модулю 2'+з), ИХз»-ь ш (дз -»+»+ад» -ь)/(цз*-г+адз -ь ~) й 1 (по модулю 2'), втовремя как Хз.-~ = 1. И обратно: необходимо, чтобы а пюь! 4 ы 1 и сшоь! 4 = 2, иначе Лз ш 1 (по модулю 8). [См. работу Эйхеиауэра, 21ехиа и Топазогли (Е1сЬепапег, 1.еЬп, апь! Торпзо$! и, МаВЬ, Со»пр.
б1 (1988), 757-759),] Младший двоичиый разряд этой последовательности имеет короткий период, поэтому предпочтителен обратный генератор с простым модулем. 37. Можно предположить, что Ь! = О. Из упр. 34 следует, что типичным вектором в 1' будет вектор (х, (зтх + азэ)/(вэх + аэт),..., (век+ аэз)/(ззх+ азь)), где 3, = йэ„з, = 9»,ьм з, = дь!-! Он принадлежит гиперплоскости К тогда и только тогда, когда гэст гл1г -1 -1 г»х+ — + + — ш га - гтэзээ — — гааз»в7 (по модулю р), * — аг х — вк ! л -3 ь -э л -» где 11 = а — ав з,э„= -(-а) »з, н и! = аз з, . Но зто соотношение эквивалентно полииомиальной срввнимости степени <»1, поэтому для»1 + 1 нельзя найти значения х, если это соотношение не выполняется для всех х, включая различные точки х = из, ..., х = ню Следовательно, гэ = .
ж гв ш 0 и г! ш О. [См. работу Ю. Эйхенауэр-Геррмана (д. Е1с(»евапег-Неггшапп, Маей. Сошр. 56 (1991), 297-301).) Замечакие. Если рассмотреть матрицу М размера (р+ 1 — 3) х (3+ 1) со строками ((1,ю!...,ш) ! (ш,...,ое) б и), то это упражнение будет эквивалентно утверждению, что любые д+ 1 строк матрицы /И линейно независимы по модулю р. Интересно было бы построить график точек (Л„, Х„+!) для р ш 1000 и 0 < и < р; тогда можно увидеть больше следов ог окружностей, чем от прямых линий, Р)ЬЗДЕЛ З.З.2 1. Есть и = 11 категорий, поэтому следует использовать строку и = 10. э 3 э э е э е $4 3 3 ЭЭ йэй 23 23 23 76 йэй 25 76 76 26' 3. 1» = 7 — „только немногим больше, чем значение, полученное при использовании мз хороших игральных костей! Существует два объяснения, почему мы не определили, что игральная кость поддельная.
(в) Новые вероятности (см. упр, 2) в действительности не очень двлекя от тех, которые заданы в (1). Сумма показаний двух игральных костей стремится к сглаживанию вероятностей. Если подсчитать вместо сумм каждую из 36 возможных пар значений, скорее всего, можно будет опредечить разницу быстрее (предполагая, что игральные кости различимы).
(Ь) Намного более важное объяснение состоит в том, что и является слишком малым для того, чтобы фиксировать значимое различие. Если бы этот же эксперимент был проведен для достаточно большого н, то подделка была бы раскрыта (см. упр. 12). 4. р, = —,' для 2 < з < 12 и з ~ 7; рг = -', Значение 1» равно 16з1. Оно попадает мевслб значениями 75% и 95% табл.
1, так что критерий подтверждает гипотезу, хотя выпало слишком мало семерок. б. Кэо = 1.15; Кзо = 0.215. Значения находятся приблизительно межлу уровнями 94% и 36% и поэтому не противоречат предположению, но они очень близки. (Яаниые для этого упражнения взяты из приложения А, табл. 1.) 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
