Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 66
Текст из файла (страница 66)
22. Неравенство е(х) < х выполняется на непересеюмощихся интервалах [ — ',е .. — ',), —,— '„", ), ..., ['— ,е .. 1), имеющих общую длину, равную (у — В) ~ Г[«' — В а а+1 1 о<«<«-« о<«бо 23. Справедливо в(о(х)) < э(х) < х, когда х находится в [= .. †" ,) в ах +  — Ь принадлежат интервалам [«= — е .. « -1) для 0 < «< Ь < а или когда х принадлежит [ — 'е .. 1) и ах+В-а принадлежит либо [1;- ..
~Я) для 0 < «< (аВ), либо [ „., В). Требуемая вероятность равна — + ~ — + — шах(0, (аВ) +  — 1) / — В /-в ао(а — 1), а~(а — 1) а о<«<о<а о<«бме« + шах(0, (аВ) +  — 1)), б ба 2а а' ~ 2(а — 1) т. е. -'+(1 — ЗВ+ЗВ~)/ба+0(1/а~) для больших а. Заметим, что 1 — ЗВ+ЗВ~ > 1, позтому В не может быть выбрано так, чтобы сделать данную вероятность близкой к требуемой.
24. Поступите, как в предыдущем упражнении; сумма длин интервалов равна 1 /а+1 — 2'1 а'-'(а — 1) а' «(а — 1) 1 о<«««- «<а 1тобы подсчитать среднюю длпну положим ро равныч вероятности того что длина серии > Ь. Тогда среднее равно ь>1 ь>« Эта величина для истинной случайной последовательности равна е — 1,а па«пе значение равно е — 1 + (е/2 — 1)/а + 0(1/аз).
[Зо«иечание, Тот же результат справедлив для возрастающих серий, так как неравенство У > У е« выполняется тогда и только тогда, когда 1 — 11 < 1 — Ц,е«. Это приводит к предположеншо, что серии н линейной конгруэнтной последовательности могут быть немного длиннее, чем нужно, позтому к таким генераторам следует применять критерий монотонности.] 25. х должен принадлежать интервалу [(/о+ о/ — В)/а .. (Ь+ ~У вЂ” В)/а) для некоторых Ь и также интервалу [а ..
В). Пусть Ьо м [аа+ — ф1, Ь« = [аВ+В-ф). С учетом граничных условий получим вероятность (Ь, — йо)(В" — а )/а+ шах(0, В - (Ь, + а' — В)/а) - гаах(0, а — (Ьо+ а' — В)/1а) Рис. А-1. Области перестановок для геиератора Фибоиаччи. Рис, А-2. Области длин с для генератора Фибоиаччи Это равно (6 — п)(ф' — о') + с, где )с) < 2(3' — сс')/а. 26. См. рис, А-1. Неравессства 1/! < 1/з < 1/з и Сз < 1/з < С! невозможны; каждое из остальных четырех имеет вероятность -. ! 27. К, = (г !1!о+ Г„С!).
Необходимо, чтобы выполнялись оба слелующих неравенства; Гз с(/о + ссз(/! < 1 и ГзНо + Рв+с(/! > 1. Половина елииичного квадрат», в которой Со > Сс, отброшеиа, клк показано на рис. А — 2, с различными отмеченными значениями 1с. Вероятиость для серии ллииой Й равна -, если я = 1, и равна 1/Рз ! Рзе! — 1/гз Рзоз, соли 1с > 1. Соответствующие вероятности для случайиой последовательности равны 2/с/(1с + Ц! — 2(я + Ц/(й + 2).'. В приведенной ниже таблице сравниваются пять первых величии. ! ! 1 ! ! 17 з со вв ! 3 с! и! зо 3 Гз во мО зззо Вероятиости дзя последовательиости Фибоиаччи; Вероятности для случайной последовательности: 26.
На рис. А-3 доказаны различиые области для общего случая, Область 213 означает, что (/з < С! < (/з, если Н! и Сз выбраны наудачу; область 321 означает, что Сз < (/з < (/з, и т. д. Вероятности для 123 и 321 равны 2 — а/2 + аз/2; вероятности для всех остальных случаев равны -'+ а/4 — ц /4. Чтобы все веровтиости были равиы с, должно выполняться равенство 1 — бп + бсс~ = О.
(Утверждение зтого упражнения установлено в теореме Дж. Н. Франклина (3. Н. ггал1с11п), (см. работу 3. Н. Рсап1с11п, Маса. Сопзр. 17 (1963), 26-39, теорема 13); другие результаты статьи Франклина имеют отношение к упр, 22 н 23,) РАЗДЕЛ 3.3.4 1. Для генераторов с максимальным периодом 1-В точность сс! всегда равна гл и д! ы 2. 2. Пусть У вЂ” матрица со столбцами, равиыми Ус,..., Ус.
Минимизация У. У при условии, что У зз (О,..., О) и УУ вЂ” вектор-столбец Х, состоящий из целых чисел, равносильна минимизации (1'' 'Х) (У сХ) при условии, что Х вЂ” зто вектор-столбец, состоящий из целых чисел, ие равных нулю. Столбцами У ' являются 1Ус, ..., (/с. 3. аз щ 2а — 1 и аз и 3а — 2 (по модулю сл). Рассматривая все короткие решеиия (15), найдем, что с!зз = 6 и сссз ы 4 для соответствующих векторов (1, -2, Ц и (1, -1, -1, Ц, за 1 а у=-х+1-- 2 2 и к=х- 2 а в=-х+--- 2 2 2 (О, 1) (о,1--) у=х-а (О, 1-а) 1 а пах 2 1 а фм х 2 2 ( 1 а) (1,0) (О,О) (а 01 (а,О) ~2~ ) Рис. А-3. Область перестановок для генератора с потенциалом 2; а = (а — 1)с/пз. исключением следующих: пз = 2'΄Π— нечетное, е > 3, а ш 2' ' (по модулю 2'), а ш 1 (по папулю О), изз = изз = 2; пз и 3'О, 3 1 д, е > 2, а ш 1 ш 3' " (по модулю 3'), а ш 1 (по модулю д), из = 2; ужо, а — 4илиу, взз изм5, 4, (а) Единственным выбором ддя (хм хе) является ~-(21взз — рзвзм-р~взз+ 1ивп), и это равно и -'(21изз+рзаазз, -Швы-рзаиш) ш (0,0) (по модулю Ц, т.
е. хз и хг являются целыми числами. (ь) когда (хм из) зз (0,0), получим (хзвзд+ язвы) +(хзиш+ хзизз) х1(ам+ изз) + хзз(в~зз + кззз) + 2хзхз(иыизз + ишим), а согласно предположению вто > (х~ + хз — )хзхз))(из1 + взз) > взц + н|з. (Заметим, что полученный реэульзвт сильнее леммы Л, которве утверждает только, что х1 < (изм + в1з)(ирз1 + азз)/зл~ и хз з< (взп + в1з)з/из', где последний может быть > 1, Идеи, по существу, является Гауссовским методом приведения двоичной квадратичной формы (см, )лзйшзМопез Апзлшез)сш (1.е(ршй, 1301), 5171),) б. Условия (30) остаются непэменкыми; следовательно, л не может быть нулем на шаге 62, когда а и пз — взаимно простые числа.
Так как )з всегда уменьшается на этом шаге. 82 в конце концов завершится с из+ ез > з. Заметим, что руг < 0 на протяжении всего вычисления. 6. Если ог + вг > э > (и — Ь)а + (о — р)г в предыдущем ответе, получим (в — р) > вг. Следовательно, (и — Ь) а < иа: если 9 ы аа, то, поскольку сс' = о; сс+ э, мы должны получить аа+с ш 1, Из замечанив к упр.
3 33-16 следует, что ма = пиво«асс(тл, + р;-с). а получим то=истр,+псассру с--аутлтрт с+тиара г+псз+срз с<(ос+1+1/оа)титра с< (,4+ 1.1- 1/д)тзрг с, а тпг+ рг, > 2т„рз-с, откуда и следует ответ. У. Докажем, используя условие (19), что сс (/с = О для всех я ~ т' тогда и только тогда, когда Уа 1ь = О для всех й ~ /. Предположим, что (/с . Оть = 0 для всех сс ~ /д и пусть с/а = асУс + .
+ асУс. Тогда (/т ссс = ас для всех 1ч Следовательно, (/т = асУа и Уа Ус = а ~((/г У,) = 0 для всех й ~ 11 Аналогично доказывается обратное утверждение. б. Ясно, что асс+с < мс (факт безоговорочно использован в алгоритме 8, так квк э не изменяется ппи сюзрастаиии 1). Для Ф ы 2 это эквивалентно (псдг/я)'с~ > (2тсцаг/я)'с~, т. е. дг < 4 с/тп/я дггга, Эта граница доведена до «10 ~/с/я для заданных параметров, но для больших тл и фиксированного,па граница (40) лучше.
9. Пусть /(ус,..., рс) = д: бес((рс,..., рс) = 1 (бсс$ — наибольший общий делитель) и И'— целочисленная матрица с опрелелителем, рэлным 1, первая строка которой — (рс „..., рс), (Последнее доказать по индукции по наименьшей ненулевой величине, занесенной в строку.) Если Х (хс,..., хс) — вектор-строка, получим Х)У = Х' тогда и только тогда, когда Х = Х')У ', а если И' с — целочисленная матрица с определителем, равным 1, форма д, определенная ИЧI, удовлетворяет 9(хс,...,х,) = /(хс,...,хс). Кроме того, 9(1,0,...,0) = В.
Без уменьшения общности предположим, что / = 9. Если з' — любая ортогональная матрица, матрица (/Ю определяет ту же форму, что и (/, поэтому (Х(/Я)(Х(/Е)т (Х(/)(Х(/)~. Выберем Е твк, чтобы ее первый столбец был кратимм (/~с, а все другие столбцы — любые подходящие векторы. Тогда получим ас 0 ... О аг (/Я = (с" ас для некоторых ас, аг, ..., ас и некоторой матрицы (/' размера (г - 1) х (г — 1), Следовательно, /(хс,,хс) = (асяс + . + асяс) + тс(хгс...,яс), Из этого следует., что ас = с/О [фактически аа = ((сс.
Ц)/с/9 для 1 < у < г[ и что й — положительно Оирвдвпвииая КВадратИЧНая фсрыа, ПОрОждЕННая С1', Гдв Г1ЕС (/с = (С1ЕС С/)/С/8, ИндуКцИЕй по С можно показать, что существуют целые числа (хг,..., яс), для которых выполняется ь(хг я,) <(с)п-гпг[а сцг«с сс/Осдс-са и для этих целых чисел ха можно выбрать таким образом, что [хс+(агка+..+аьтс)/ас [< 1, а это эквивалентно (асяс + + асяс) < -сд. Значит, О < /(хс,,х,) < 140+(ус)п "~'[бес(1[шп "/Оы" О и желаемое неравенство получается немедленно. [Замечение. Для г = 2 это наилучший из возможных результатов.
В общем случае из теоремы Эрмита следует, что дс < кпг(4/3)'с' Отэ/(Ф/2)! . Из фундаментальной теоремы Минковского (" Каждое Ф-мерное выпуклое множество, симметричное относительно начала координат с объемом > 2', содержит не равную нулю точку с целыми координатами" ) следует, что дс < 2'. Это более точное неравенство, чем то, которое следует из теоремы Эрмита для Г > 9. Известен еще более точный результат (см. (41)).] 10. Так как уг и уг — взаимно простые числа, можно найти решение уравнения игуг — игуг = т. Кроме того, (иг + дуг)уг — (иг + Оуг)уг = т для всех 9, поэтому, выбирая подходящее целое д, можно убедиться, что 2(и|уг + игуг) < уг + угг. Сейчас уг(гм + аиг) ш угиг — угиг ш О (по модулю т), уг и т должны быть взаимно простыми числами.
Следовательно, иг + аиг ш О. Окончательно, пусть ~игуг + игуг~ = от, из + иг = дт, у, + угг = ут, справедливо 0 < о < -7 и остается показать, что а < 9;3 и г 1 1 ,37 > 1. Тождество (игуг — игуг) + (игуз + игуг) = (и, + иг)(у, + угг влечет равенство 1 + ог = /)7. Если о > 1Д, то справедливо 2о з > 1+ ог, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
