AOP_Tom2 (1021737), страница 194
Текст из файла (страница 194)
Увеличить указатель буфера. Повторить десять рвз. Повторять до тех пор, пока печатаются обе строки. 5 1.764 72 — 1 166472 1 б 150472 150 1 3 5 4.7 2 1 3 5 4 1 2 1 9 3 2 1 2 1 9 3 13. ВОР АСР ОВ10 ЗТАВТ ЭОЧ ЕИТ2 ВН ЕИТЗ 1Н ЕИТ1 ЕИТХ 2Н ЗТХ 11Р ЗЕАХ СНАЕ ЗТА БТХ 1ИС2 ОЕСЗ ЭЗР ООТ 32И ВОР+40,2(2:5) ВОР+41,2 2 1 1В ВОР+20,2(РВ1ИТЕЕ) 88 9.8 9 118 + 1 1 131 + 1 3 7654 8 6.6 5 4 1 б 83.54 483 4284 0428 4 7 2 3 Результат; (1764723)о. 14. Пусть К(ц) --- число шагов, требуемых для преобразования гг-разрядного десятичного числа в представление в двоичном формате и одновременного вычислении двоичного представления числа 10". Тогда К(2п) < 2К(п) + 0(М(п)). Доказательство.
Для данного числа С = (иг„г...ио)го за 2К(п) шагов вычисляем (Хг — — (иг г .ио)го и Во = (ио-г .. ио)го, а также 10". Затем за 0(М(п)) шагов вычисляем С = 10" Сс + (Хо и 10г" = 10" 10" Отсюда следует, что К(2") = 0(ЛХ(2") + 2М(2" ') + 4ЛХ(2" ) +. ) = 0(пМ(2")). [Подобным образом, как показал Шенхаге, за 0(пЛХ(2")) шагов можно преобразовать (2" !810)-битовое число С из двоичного представления в десятичное. Сначала за 0(ЛХ(2" ') т ЛХ(2" г) + ) = 0(М(2")) шагов формируем числа К = 10г" ', затем еще за 0(М(2")) шагов вычисляем Со — — ((Х спой !с) и Сг = [С/!с].
После этого преобразуем Со и Ь ь] 17. См работу У. Д. Клингера (ЛЛс. О. С!!вбег), БХСР1.4Е Мос!сея 25, 6 (авве, 1990), 92-101, а также работу Стила (Ясее!е) и Уайта (Ъ'!г!се), цитируемую в ответе к упр. 3. 18. Пусть ХХ = гоапс!в(и, Р) и о = гоцпсЦ(Х,Р). Можно положить, что и > О, так что (Х > 0 и о > О. Случай Е о < и: определим е и Е такими, чтобы выполнялось неравенство Ь' ~ < и < 6', В~ ' < (Х < Вл. Тат а и < С+ -'Вл и (Х < и — -'Ь' "; следовательно, В~ ' < В~ ~С < В~ ви < Ьг 'и < Ьо.
Случай 2, о > и: определим е и Е так, чтобы получить Ь' < и < 6', В~ < С < Вл. Тогда и > П вЂ” -'В~ ~ и сХ > и+ г6' "; следовательно, В~ ' < В" (С вЂ” Вк ) < В' си < Ьо 'и < Ь". Такнмобразом,доказано, что В~ ' < Ьо когда о Р и. Обратно, если В~ ' < Ьо, то при доказательстве, проведенном выше, предполагалосгь что наиболее подходящим примером, для которого и Р' о, будет тот, в котором число и представляется по степеням 6 и в та же время близко к степени В.
Получаем В~ гЬ" < В" '6" + -'Ь" — -'В~ ' — -' = (В~ ' + г )(6о — -')! следовательно, 1 < а = 1/(1 — г6 о) < 1+ гВ' = /Х. Согласно результатам упр. 4.5.3-50 существуют целые числа е и Е, такие, что !обв о < е1обв 6 — Е < !обв !3. Отсюда следУет, чта длЯ некотоРых е и Е выпалнЯетсЯ неравенство о < Ь"/В < !3. Получаем гоцпс!в(6', Р) = В и гоипс!о(В~, р) < 6'.
[СЛСЛХ 11 (1968), 47-50; Ргац Атег. МаСЛ. Яос. 19 (1968), 716-723.] Например, если Ьо = 2'о и В~ = 10', то число и = 2"'оо .100049 10иио округляется до (Х = .1 10гого ш (.111111111101111111111)г 2~ю~, которое округляется до 2~~ш — 2огоо. (Ноиосоньший пример округления гоипс!(( 111П11001)г 2~~~) = 1011 10гго, госгпс!(.1011 10гг') = (.11111110010)г . 2го' найден Фредом Дж. Тайдеманом (Ргес! 3. Тус!етап), ) 19.
тг = (ГОГОРОГО)м, сг — — 1 — 10/16 формирует сХ = ((игио)го . (игио)го)гго; тогда пгг = (ГРООРРОО)го, сг = 1 — 10г/16 формирует С = ((игивиоио)го(игигигио)го)~о~о~,' а тэ = (ГРГГОООО)ш, сг = 1 — 104/164 завершает процедуру. [Ср, с алгоритмом Шенхаге в упр. 14. Эту процедуру предложил Рой А. Кейр (Кау А.
Ке!г) приблизительно в 1958 саду.] РАЗДЕЛ 4.5Д 1. Учитывая, что знаменатели положительны, проверяем выполнение неравенства ио <ио. 2. Если на с > 1 делятся как и/с1, так и е/с1, то на сс( делятся и и о. 3. Положим, что число р простое Егли р' является делителем чисел ио и и'о' при е > 1, то либо р'!и и р'!о', либо р'!и' и р''!о; следовательно, р'!8сс!(и,о')бес!(и',о). Обратное утверждение доказывается путем обращения утверждения. 4. Пусть с!г = 8сс)(и, о), с1г = бес!(и', о'); тогда ответом будет го = (и/с!с)(о'/с!г)з!8п(о), ш' = ](и'/с!г)(о/с!г )[ с сообщением об ошибке "Деление на нуль" при о = О.
5. А =10,1=17.7 — 27 12= — 205,6з=5, ш= — 41,ш'=166. 6. Пусть кь = и'/А, с" = с'/Иь Задача состоит в том, чтобы показать, что бед(ис" + и"с, И~) = бег)(ива + и"с, Аи" с"). Если число р простое и является делителем числа и", то р не будет делителем числа и или с", а потому р не делит ис" + и" с. Подобное же рассуждение действительно для простых делителей числа с". Таким образом, ни один иэ простых делителей числа и" с" не оказывает влияния на наибольшее общее кратное.
7. (% — 1) + (Х вЂ” 2) = 2Х вЂ” (6М вЂ” 5). Если исходными числами являются и-битовые двоичные целые числа, то для представления числа 1 может понадобитьсн 2п+ 1 бит. 8. При умножении и делении эти величины будут подчиняться правилам х/О = е18п(х)оо, (хоо) х х = х х (хсо) = (хоо)/х = хаба(х)оо,х/(хоо) = О, где х — произвольное конечное число, не равное нулю. Описанные в разделе алгоритмы остаются без изменений. Затем зти алгоритмы можно легко модифицировать так, что О/О = 0 х (жоа) = (хоп) х 0 = в(0/О)", где "О/О" служит представлением "неопределенности". Если один из операндов не определен.
результат также должен быть не определен. Поскольку подпрограммы умножения и деления могут удовлетворять этим естественным правилам расширенных арифметических операций, иногда имеет смысл модифицировать также операции сложения и вычитания, чтобы они удовлетворяли правилам х * оо = ~со, х х ( — оо) = ~ос для конечных х; (жоо) + (жоо) = хсо — (жоо) = хоо; более того, (хсо) + (~со) = (жоо) — (хсо) = (О/0); если одним или обоими операндами служит (О/0), результат также должен быть (О/О). Аналогично можно модифицировать операции проверки равенства и сравнения.
Сделшшые выше замечания ие относятся к признакам "переполнения". Если для признака переполнения используется оо, то нельзя полагать 1/оо равным нулю, чтобы не принять неверные результаты за правильные. Значительно лучше представить признак переполнения через (О/0) и условиться,что результат любой операции будет неопределенным, если хотя бы один из вводимых операндов является неопределенным. Такой способ индикации переполнения имеет то преимущество, что данные на выходе расширенных операций точно указывают, какой из результатов определен, а какой †н.
9. Если и/и' ф с/с', то 1 < [ис' — я'с[ = и'с'[и/и' — с/с'[ < [2~"и/и' — 2~"с/с'[. Две величины, различающиеся более чем на единицу, ие могут иметь одинаковую "грань снизу'. (Другими словами, 2п первых битов справа от двоичной точки достаточно для того, чтобы охарактеризовать значение двоичной дроби при наличии и-битовых знаменателей. Нельзя повысить ее точность до 2п — 1 бит, так как при и = 4 получим — = (.000100П ., ), —,' = (.00010010... ) .) 11. Чтобы разделить ненулевые числа с и с' на (с + с'Л)/с", нужно умножить их на обратное значение (с — с'~/5)с"/(с~ — 5е'з) н выполнить возможные сокращения. 12.
((2э ' — 1)/1); гоппб(з) = (О/1) тогда и только тогда, когда [х[ < 2' э. Аналогична гожий(х) = (1/0) тогда и только тогда, когда х > 2е 13. Один подход заключается в ограничении размеров числителя и знаменателя величиной 27 бит. Тогда нужно будет сохранять только 26 бит (так как ведущий бнт знаменателя равен 1, за исключением случая, когда длина знаменателя равна О) При таком подходе остается место для знака и 5 бит для запоминания размера знаменателя. Другой подход заключается в использовании 28 бит для числителя и знаменателя, которые занимают не более семи шестнадцатеричных разрядов вместе со знаком и 3-битовое пале для запоминания количества шестнадцатеричных разрядов в знаменателе.
[С учетам формул, приведенных в следующем упражнении, первый подход дает точно 2 140 040 119 конечных представимых чисел, а второй — 1 830 986 459. Первый подход предпочтительнее, так как он более простой и обеспечивает гладкий переход между интервалами. При оперировании 64-битовымн словами общая длина числителя и знаменатели ограничивается величиной 64 — 6 = 58 бит.] 14. Количества чисел, кратных п в интервале (а..Ь], равно (6/п] — (а/п]. Отсюда, используя метод включений и исключений, получаем решение задачи в виде Яэ — Я! + Я! — ., где Яь равно 2 ((Мр/Р] — ]М!/Р])((14з/Р] — (Х)/Р]), просуммнрованному по всем произведениям Р различных простых чисел )с.
Можно также выразить ответ в виде ш)мыл!) Й(п) ((М2/п] — (М)/п]) ((!!2/п] — ()!))/и]). и=! РАЗДЕЛ 4.5.2 1. Везде замените пнп, п)ах, + на 8сб, 1ст, х соответственно (предварительно убедитесь, что все тождества справедливы н тогда, когда любая переменная равна нулю) 2. Для простого числа р пусть ир, с)р, ..., срр — степени числа р в каноническом разложении чисел и, с), ..., с„.
Па предположению ир < с)р + . + с р. Необходимо показать, чта ир < ш)п(ир,в)р) + + пнп(и„,с р), на эта неравенство действительно выполняется, если ир не меньше каждого с)р или ир меньше некоторого с)р. 3. Решение Е Если п = р",... р,'", это число в каждом случае равно (2е)+ 1)... (2е, + 1). Решение 8. Если положить и = 8сс1(д,п) и с = п~/1ст(с(,п) для каждого делителя с2 числа п~, то можно получить взаимно однозначное соответствие.
(Е. Сезара, Аппа)!' сй Ма!стас)са Рига ес( Аррйсага (2) 13 (1885), 235 — 250, 812.] 4. См. упр. 3.2.1.2-15(а). 5. Будем выполнять сдвиг вправо чисел и и е до тех пор, пока не получим, что ни одно из них не кратно 3, Запоминаем соответствующее значение степени 3, которое появится в наибольшем общем делителе. Затем на каждой итерации присваиваем 1 с- и+ с нли 1 +- и — с (в зависимости ат того, какая из этих величин кратна 3), сдвигаем 1 вправо до тех пор, пока оно не перестанет быть кратным 3, после чего заменяем тах(и, с) полученным результатом.
и Ю Свидетельства тога, чта 8сс1(40902, 24140) = 34, поразительно! 6. Вероятность того, что оба числа и и с четны, равна -'; вероятность того, что оба числа кратны четырем, равна —,'„, и т. д. Таким образам, величина А имеет распределение, задаваемое производящей функцией 3 3 3 э 3/4 -+ — а+ — х + 4 16 64 1 — х/4 Среднее значение равно э, а среднеквадратичное отклонение — э + — — э = —. Если и ! и е независима и равномерно распределены в интервале 1 < и, а < 2л, необходимо внести 13634 24140 13634 3502 1904 3502 1904 1802 34 1802 34 68 34 34 10506, 3502 17136, 5712, 1904 5406, 1802 102, 34 1836, 612, 204, 68 102, 34 0 в расчет небольшие поправки, тогда среднее в действительности будет равна я (2л ц г)- (2л й цг 1 4(2л ц — ' ас(2л ц-г й=л 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
