Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 67
Текст из файла (страница 67)
7 — з/7~ — 1 < а < гч. Но г7 < гг-~~ — 1 влечет неРавенетво 7 > -, что пРивсщит к пРотивоуечию. 1 Гг г 11. Так как а нечетко, уг +уз должна быть четной. Чтобы избежать решения, где и ум и уг четные, положим уг = х1+хг, уг = хг-хг и решим уравнение х,+хг — — т/~гЗ вЂ” е при хг .1 хг г г и четном хь Соответствующий множитель а будет решением уравнения (хг — хг)а ш хг + хг (по модулю 2'). Не составляет труда доказать, что а ш 1 (по модулю 2" +') тогда и только тогда, когда хг и О (по модулю 2 ), поэтому получим наилучший потенциал, когда хг тоб4 = 2. Проблема сводится к нахождению относительно простого решения х, + хг = гг', где Х вЂ” больпюе число вида 4к+ 1. Разлагая Ж на комплексные целые числа (гауссовские целые числа), мы получим, что решение существует тогда и только тогда, когда каждый простой множитель Х (среди обычных целых чисел) имеет вид 48 + 1.
В соответствии с известной теоремой Ферма каждое простое р вида 4/г + 1 можно с точностью до знаков и и э записать единственным способом: р = иг+ег = (и+ге)(и-гэ), где е четное. Числа и и е эффективно могут быть вычислены, если решить уравнение хг ш — 1 (по модулю р) и затем вычислить и + го = Вод(х + г, р) с помощью алгоритма Евклида по комплексным целым числам (гауссовским целым числам). ,'Можно взять х = пы ' У тоб р для почти половины вспг целых и.
Это применение алгоритма Евклида, по существу, такое же, как и нахождение наименьшей не равной нулю величины и + о, такой, что г г их хе ш О (по модулю р). Значения и н е также появляются, когда алгоритм Евклида для целых чисел применяется обычным образом к р и х; см, работу Ж, А.
Серре и К. Эрмята (3. А. Беггег апг( С, Неппге, Х зге Маей. Ригеэ ес Аррй 5 (1848), 12-15).] Если разложение на простые множители Х имеет вид р",... р„'" = (из+гиг)" (иг — гиг )"... (ик Ьги, ) "(и — гик) ", то получим 2" г различных решений хгг+хг = гз', хг л. хг, хг четное, полагая ~хг~+ г~хг) = (иг+гог )"' (игхгог)~г...
(и„хгэ,)'". Подобным методом можно получить все такие решения. Замечание. Аналогичная процедура может использоваться, когда т = 10', но для этого потребуется в пять раз больше работы, так кэк негбходимо хранить информацию до нахождения решения с хг щ 0 (по модулю 10), Нацрнмер, когда т = 10'э, получим (т/эгЗ) = 5773502691 и 5773502689 = 53 108934013 = (7+ 2г)(7 — 2г)(2203+ 10202г) и (2203 — 10202г). Из решений !хг(+ г)хг/ = (7+ 2г)(2203 + 10202г) н (7+ 2г)(2203 - 10202г) первое дает !хг) = 67008 (не хорошее) и второе — )хг/ = 75820, )хг( = 4983 (это подходит). Строка 9 из табл. 1 была получена, когда мы положили хг 75820, хг = -4983. Строка 14 таблицы была получена следующим обрезом, (Зю/ъ/31 = 2479700524; спустимся вниз к Х = 2479700521, рваному 37 797 84089, и получим четыре решения: зз' = 4364' + 49605' = 26364г + 42245' = 38640 + 31411' = 11960' + 48339г.
Соответствующими множителями будут 2974037721, 2254986297, 4246248609 и 956772177. Проверим также )г' — 4, но это число не подходит, поскольку оно не делится на 3. С другой стороны, простое число )з' — 8 = 45088г + 21137 прижздит к получению множителя 382Ы40801, Аналогично получим дополнительные множители для )г' — 20, гз' — 44, Ж вЂ” 48 и т. д. Множитель строки 14 — наилучший яз первых шестнадцати множителей, найденных с помощью данной процедуры; это один нз четырех множителей для )г' — 68.
12. Ц' б = (/г С) + 2~ „иг Ф(Ц. Н ) + ~ иез 2 гиз дгуг(Ц И,). Взята вторая частная производная по Ог от легай части (26). Если достигается минимум, то частная производная должна обращаться в нуль. 13. «и = 1, вы = иррациональны, «ш = «ээ = О. 14. После тРехкРатного пРнменениЯ алгоРитма Евклида полУчим иээ = бэ + бэ.
Затем после выполнения шага 84 получим -5 5 01 /-2 18 38'1 (7 = — 18 — 2 0 , У = — 5 — 5 — 5 1 — 2 1 0 0 100 Результатом преобразования (у, д~, дэ,дэ) = (1, э, 0,2), (2, -4, ь, 1), (3, О, 0,*), (1, э, 0,0) будет /-3 1 2~( 1 -22 -2 18''1 (У= — 5 — 8 -7, У= -5 -5 -5, 3=(О 0 1).
1 -2 1 9 -31 29 Таким обрезом, иэ ы тамб, как уже известно из упр. 3, 15. Наибольшее достяжнмое д в (11) минус наименьшее достижимое плюс 1 равно (и~ ! + .. + )«~) — 4, где Б = 1, если «с«1 ( О для некоторых 1 и 1'. В остальных случаях б = О. Например, если 1 ы 5, «э > О, «э > О, «з > О, «э = 0 и «э < О, наибольшее достижимое значение д равно д = щ + из + «э — 1, а наименьшее равно 4 = «э + 1 = -) «э! + 1. (Заметим, что число гиперплоскостей остается прежним при нзмененкн с. Следовательно, ответ будет таким же, если вместо Ее покрыть Ь. Однако приведенная формула не всегда точна для покрытия 1 о, поскольку не во всех гиперплоскостях, пересекающих единичный гиперкуб, содержатся точки из Ье В приведенном вы«~в примере можно никогда не достичь значения 4 = «э + «э + «э — 1 в То, если «~ + «э + иэ > т, Это значение достигается тогда и только тогда, когда существует решение т — «~ — «э — «э = х~ щ + яэ«э + хэ«з + х<(«ь), где (хм хм яз, я<) — неотряцательные целые эвита.
Возможно, верно, что данный предел всегда достижим„когда сумма («~) +. + )«с( минимальна, но это не кажетск очевидным.) 16. Достаточно найти все решения (15), имеющие минимум )«~) + + )«~~, и вычесть 1, если какое-нибудь из этих решений имеет компоненты с противоположным знаком. Вместо положительно определенной квадратичной формы будем использовать функцию, в некотором смысле аналогичную ей, (у(хц...,х~) = )я~(7~ +...
+ я~К)), определяя )У) = (рэ)+ . + (р~!. Неравенспю (21) можно заменять неравенством )хь) < ~(рм...,9~) х (шахз<збс )«Ш!) Таким образом может быть получен следующий работающий алгоритм. Заменить шаг 81 шагом 33: "Присвоить (7 +- (оэ), 1' е- (1), г е- 1, в е- ш, 1 <- 1". (Здесь (7 и У вЂ” матрицы размера 1 х 1. Следовательно, двумерный случай сводится к общему метсщу, Для 1 = 2 можно, конечно, использовать частную процедуру; см. работу, приведенную в ответе к упр. 5.) На шагах 84 и 87 присвоить э +- ш1п(э,((7ь().
На гааге 87 присвоить аь е- (шах~<~<~ (иь1) э/т1. На шаге 89 присвоить э <- шш(э, (У( — б) и на шаге 810 выход, э = Х~. Иначе — оставьте алгоритм в том виде, в каком он сформулирован, так как ои уже производит достаточно короткие векторы. (Маей. Сошр. 29 (1975), 827-833.) 17. Когда й > с на шаге $9 и У У < э, взять в качестве выхода У н -У. Кроме того, если У.
У с э, взять в качестве выхода предыдущие векторы для этого и (При подготовке табл. 1 автор заметил, что существовал точно один вектор (и он же со знаком "минус" ) на выхаде для ьи кроме случаев, когда р~ = 0 или р, = 0.) 18. (а) Пусть х = т, р = (1 - гл)~3, «о = р+ хдм, «чз = -р+ 40. Тогда 11 У, = 1(т~ — 1) для У 74 й, 15,.Уь = э(т~+ -'), Уз (71 = 1э(т~+ 2), гэ - Д ш. (Этот пример удовлетворяет (28) с а = 1 и работает для всех т ш 1 (по модулю 3).) (Ь) Необходимо поменять местами (/ и У ка шаге 83. После замены присвоить также »»- ппп(э,Ь;. (/,) лля всех (/о Например, когда т = 64, это преобразование с / = 1, примененное к матрице из (а), сводит 43 -21 -21 1 /22 21 21 1 У = — 21 43 -21, 1/= 21 22 21 -21 -21 43 21 21 22 1 1 1 1 / 22 21 21»( У = -21 43 -21, П = -1 1 0 1, — 21 -21 43 — 1 0 1 (Поскольку преобразование может привести к увеличению длииы У, алгоритм, объединяющий оба преобразования, должен быть таким, чтобы ке допускалось зацикливание.
См. гакже упр. 23.] 19. Нет, так как произведение не едиинчиых матриц со всеми иеотрицательиыми элемеитами вие лиагонали и со всеми диагональными элементами, равными единице, ие может быть единичным. 1»Однако зацикливание было бы возможным, если бы последующее преобразование с 4 = -1 осуществлялось тогда, когда -2У» У = 1»1 .
У, Правило округления должио быть несимметричным откосительио знака, если допустимо несокращеииое преобразоваиие.] 20. Когда ашо48 = Ь, точки 2 '(х,э(х),...,вр О(х)) для х в периоде — это те же самые точки, что и 2' '(р„п(р),...,и' '(р)) для 0 < р < 2' ' плюс (Хо шо»14)/2*, где и(р) = (ар + (а/4)) шест 2' ~. Поэтому в рассматриваемом случае следовало бы использовать алгоритм 8 г го = 2' э.
Когда апик(8 = 3, максимальное расстояиие между параллельными гиперплоскостями, содержащими точки 2 '(х,э(х),...,эр 0(х)) по модулю 1, такое же, как и максимальное расстояние между параллельными гиперплоскостями, содержащими точки 2 '(х,— а(х),,( — 1)' эр 0(х)), поскольку замена знака координат ие изменяет расстояния. Последней будет точка 2з '(р,п(у),,»г» '(у)), где п(р) = (-ар — (а/4]) шой 2' э плюс постоянное отююнение. Снова цримеиим алгоритм Б с гл = 2' ~; замеиа а иа гл — а ие сказывается иа результате.
21»Х» .н ш Хш (по модулю 4), поэтому сейчас удобио положить К ш (4,4а»,4аэ)/и», Ье = (О, 1, О), 1з = (О, О, 1) и определить соответствуюп1ую решетку Хо. 24. Пусть и» = р; можно произвести анализ, подобкый приведенному в разделе, Например, когда 1 = 4, то Х„ез = ((аз + Ь)Х„~~ + аЬХ,) шоб т, и необходимо так минимизировать и,'+из+ аз+ и» Ф О, чтобы и~ +Ьиэ+аЬк» ш из+ам»+ (а +Ь)и» ш 0 (по модулю и»). Заменим шаги 81-83 операцией присвоеиия (/»- ( ), 1'»- ( ), Я»- ~ ), в»-и»', 1»-2 и на выходе получим кэ = т.
Заменим шаг 84 шагом 84'. 84', ]Продвижение ц] Если 1 = Т, алгоритм завершен. Иначе — присвоить 1 +- 1 + 1 и»1»- Л(", )шо»(п». Присвоим (/» новой строке ( — »»э,-гю,0,,0,1) из 1 элементов и присвоим ио»- О для 1 <» < К Присвоим 1'» новой строке (О,...,О,пт). для 1 <» < г присвоим д +- округлеиие((опгаг + вагш)/гл), со» о»!гш + е»тгээ — стл и П»»- »/» + Япь Накоиец, присвоить э»- ш)в(В, П» ' с/»)~ й +- Г, У»- 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
