AOP_Tom2 (1021737), страница 183
Текст из файла (страница 183)
Метод вычитания с заимствованием является ценным, главным образом, потому, что его понимание дается нам благодаря превосходному поведению более простого приближения. 14. Имеем Х»+зее щ (Х, + Хг шее) (по молулю 2); см. упр. 3.2.2-32. Следовательно, 1' »~аа = 1» + 1»»щ, когда п гаай100 > 73. Аналогично Х»»сее — = Х + Х»эе + Х»аэ. Значит, 1 +»ао щ У, + )»»зе + )' »вэ, когда и гаой100 ( 11. Таким образом., 1;»~еа является суммой только двух или трех элементов (У,..., У»щ) в 26% -~-11%» всех случаев и преобладание нулей приводит к тенденции делать так, чтобы выполнялось равенство );„ее =О. Точнее, рассмотрим последовательность (ит, ид,... ) = (126, 89, 152, 115, 78,..., 100, 63, 126, ), где и»+т = и„— 37+ 100(и <100].
Тогда Х»эдоо = (Л,т Ч- Хте т + ' + Л»е»ь д + Х в т) тттог1 2, где ит = ит + (-1) т- 100, например Х„эдоо = Х» + Х +и + Х»+тво+ Х ьшд = Л + (,>топ) Х»»тв + Л»+им+ Х»д и+ Х„эттв. Если все индексы < и+1 и > и + 100+ Ь то получим А членов выражения У етоо, когда и глот) 100 = 100 — 1 для 1 < 1 < 100. Случай, когда( = 63. является исключением, так как Х +Х»+т+ +Л»+га+Л„этвв+Х енм+ ..+Х +шд = 0- Здесь У» ыоо не зависит от (1'„,, У'„эдд) Случай, когда( = 64, интересен потому, что он дает 99 членов соотношения 1;.»тоо = Кэт + 1' +т+ . + 1' +до, которые имеют тенденцию становиться нулями несмотря на большое количество членов. Это происходит потому.
что большая часть строк размерности 100, которые имеют 40 или меньше единиц, имеют одннаковую четность. Когда существует соотношение из А членов, вероятность, что У этоо = 1, равна Величина 1 принимает значения 100, 99, ..., 1, 100, 99,, 1, ... во время печати двончных разрядов. Итак, мы определили, что ожидаемое число напечатанных единиц Равно 10 (26Рд+11Рв+26Р»т11Рв+11/то+4/ттт+4Рго-»3Ргв+Р»т-ГРтв-| 1>»д+1/2)/100 14043 Ожидаемое чис.то напечатанных знаков равно 10 2,"~о ('оо)/2'оо 28444, ожидаемое число нулей равна 14401.
Замеченное смещение пропадает. если отбрасывается больше элементов. Например, если использовать только 100 элементов программы гап аггау(а,300), вероятность может быть (26рв + 22рв + 19рто + . )/100. С программой гап аггау(а,400) дела обстоят хуже. здесь вероятность (15рв + 37рв + 15рд + . )/100, так как Х э»оо = Л + Х т-ыд С программой гаа аггау(а,1009), рекомендованной в разделе, получаем вероятность (1?рт+ 10рм Ч-2рш -'г. )/100, что может быть обнаружено в ходе таких экспериментов, если порог для печати поднимается от 60 до, скажем, 75, но тогда предполагаемое число выходов равно всего лишь около 0.28 из миллиона испытаний.
[Это упражнение основано на идеях Й. Курита (Ъ'. КиПга), Х. Лииба (Н. ЬееЬ) и М. Мацумото (М. Ма! ватного), сообщенных автору в 1997 году) 16. Следующая программа позволнет получить новые случайные целые числа, которые выражаются гап атт пег1(), начав с программы ппт Магб ВАе11пе ЯОАЬТТТ 1009 /в реконендуется уровень качества для високорезультатианого использования в/ 1олб гал агг„вит(ЦУАЬ1ТТ]; 1опб гап агг вепо1пе1»-1; 1опб »гап„агг рог»агап агг вепо1пе1; /в следующее случейиое число или -1 »/ АбетАпе гап агт лехе() (»гап агг рог>»0? этап агг рог++: гал агг сус)е()) 1опб гал агг сус1е() ( гал аггау(гап агг Ьит,ООАЬТТТ); гап агг ЪиГ(100]»-1; гап агг рог гал атг Ьит+1; гесигп гвл агг Ьиу[0]; РАЗДЕЛ 4.1 1.
(1010)-г, (1011)-г, (1000) г, ..., (11000)-г, (11001) г, (11110) г. 2. (а) -(110001)г, -(11.001001001001 ,,)г, -(11 00100100001111110110101 .. )г. (Ь) (11010011) г. (1101.001011001011 ...)-г, (111.0110010001000000101 ...) (с) (11111)з, (10.011011011011 )з, (10.0111111100010111110111111110 ,.)з.
(б) — (9 4) гуго, -(... 7582417582413) гуж, (... 3482б483239798535б2951413) мы. 3. (1010113.2)г . 4. (а) Между гА и гХ. (Ь) У остатка в регистре гХ разделяющая точка находится между байтами 3 и 4; у частного в регистре гА разделяющая точка расположена на один байт правее младшего разряда регистра. 5. Представление в обратном коде получается путем вычитания из 999 .,9 = 10г — 1, вместо вычитания из 1000...
0 = 10". О. (а, с) 2г ' — 1, -(2г ' — 1), (Ь) 2" ' — 1, -2г 7. Представление в дополнительном коде для отрицательного числа х может быть получено, если взять число 10" + х (и достаточно велико, чтобы число было положительным) и продолжить его влево при помощи бесконечного катичества девяток. Представление в обратном коде можно получить обычным способом. (Эти два представления совпадакгт для бесконечных десятичных дробей, в противном случае представление в обратном коде имеет вид ...
(а)99999..., а представление в дополнительном коде .. (а -Ь 1)0000....) Данные представления имеют смысл, если считать, что значение бесконечной суммы Х = 9+ 90+ 900+ 9000+ равно — 1, поскольку гУ вЂ” 10% = 9. См. также упр. 31, в котором рассматриваются системы р-адических чисел. Для чисел, представление которых по основанию р конечно, уьадическое представление совпадает с рассмотренным здесь представлением в дополнительном коде, ио между полем р-адкческнх чисел и полем вещественных чисел не существует никакой прямой связи 8.
~ а Ь' = Яу(аг <ьь гь~ ' + . + аг )Ь~г. 9. А ВАО АООВЕ ЕАСАПЕ ЕАПЕП. (Примечание. Вот другие "числовые фразы": ПО А ПЕЕО А ПЕСАПЕ: А САП РЕП А ВАНЕ ВЕЕР> СОСОА, СОЕЕЕЕ; ВОВ ВАСЕВ А ПЕАП ПОПО.) 10. [ ) =( ' ' ' ' ' ', если ,аз,аг,амаа; а<ма-г, ) (,Аг Аг,АпАо, А м А-г, аг,,, пав,ы г,...,аь,1 в, = ь, , . ьь, где (6„) — произвольная бесконечная последовательность целых чисел, удовлетворяюгцих неравенствам Й,.ьг > Ап 11.
(Описываемый ниже алгоритм выполняет как сложение, так и вычитание в зависимости от выбора знака "плюс" нли "минус".) Сначала устанавливается lс е — аь ы г — а„тг е- Ьа ы е- 6 .гг г — 0; затем для гл = О, 1,... ..., п+ 2 выпшгняется следующее: устанавливается сч е- а х ьч + А: далее, если с > 2, устанавливается 6 е — -1 и с г- с„, — 2; если с < О, устанавливается 6 г — 1 и см е — с +2; а если 0 < с, < 1, то устанавливается А е- О. 12.
(а) Вычесть х(... азОаг0) г нз х(... агОагОао)-г в негадвоичпой системс. (В упр. 7.1 18 приводится оригинальное решение задачи, полученное с использованием битовых операпий над полным шювом.) (Ь) Вычесть (.. ЬгОЬг0)г из (.. ЬаОЬг06е)г в двоичной системе. (0.090909., )-го = —,', [5 — 4 !] [5 — 4г[ 1$. (1.909090... )-ге = 14. 11321 11321 11321 11202 12123 11321 11321 010311201 [9 — 40г[ Рис. А-6. срундамензвльная область 15. [ — г ..
—,',[ и прямоугольник справа (рис А-6) для мнимочетверичных чисел. 16. Соблазнительно попробовать сделать это самым простым способом, предписав реализапию переносов по правилу 2 = (1100), г, но это приведет к непрекращакгщейсн процедуре (зацикливанию) при попытке добавления единицы к числу (11101), г = — 1. В приведенном ниже решении предлагаются четыре алгоритма (для сложения и вычитания 1 н г). Если а — строка нз нулей н единиц, то полагается, что а . -такая и строка из нулей и единиц, что (а~), г = (а), г + 1. Аналогичным образом определяются а, аа, а О путем замещения +1 соответственно на -1, +г и -г.
Тогда (аО) = а1, (ах1) = а'хО. (а1) = а ~0. (ахО) = а ~х1; (а1) ~ = аО. (а1) ~=а гО. Здесь х означает 0 или 1 и цечочкн при необходимости дополняются слева нулями. Все эти процедуры очевидным образом заканчиваются. Таким образом, любое число вида а + Ьг с пелыми а н Ь представимо в системе по основанию г — 1. 17. Нет (вопреки упр. 28), число — 1 не представимо в этой системе. Это можно доказать, построив соответствующее множество 5, как на рис. 1. Имеем представления — г (0.1111 ..
)г „г = (100.1111...)ге,. 18. Пусть ое-"множество точек (агаеазагазазагае), г, в котором каждое ай есть О илн 1 (Поэтому множество ое состонт из 256 внутренних точек, отмеченных на рис. 1, после 16-кратного увеличения.) Покажем сначала, что множество Я замкнутое. Пусть уг, рз, произвольная последовательность точек множества Я Имеется уи = ~" й>г а„й16 где каждое аий принадлежит Яе. Построим дерево, вершннами которого будут наборы (а„г,...,а,) для 1 < г < и, причем одна вершина является родителем, если она является по отгюшению к этой вершине начальным поднабором. Согласно теореме о бесконечных деревьях (теорема 2 3 4 3К) это дерево имеет бесконечный путь (и,, аз, аз, .
); соответственно 2', >г ай!6 й есть предельная точка множества (рг, уз,...), принадлежащая Я. В соответствии с ответом к упр 16 все числа вида (а+Ьг)/16 представимы, если а и Ь й целые. Поэтому при действительных х и у и !г > 1 число зй = ([16 х) + [16 у)г)/16 й й й длн некоторых целых гп и п принадлежит Я + гп + пг Можно показать, что всякая представимая точка вне Я должна пршгадлежать множеству и+ т+ пг при (ш, и) Ф (О, 0).
Соответственно, если [х[ н [р[ фиксированы и й достаточно велико, получаем, что зй 6 Я н !!пгй,„, й = х+ уг принадлежит множеству о. [В. Мандельброт (В Маис!е!Ого!) назвал миожегтво Я двуглааым драконом, подметив, что оно, по существу, формируется путем объединения двух "кривых дракона" (см. книгу Егасга?в1 Еоггп, СЬапсе, апб Рппепсбоп (Кап Ргапсгксо1 Ргеешап, 1977), 313-314, в которой Мандельброт установил, что размерность границы равна 2!бх 1.523627, где х 1 + 2х 2 1.69562. Другие свойства кривой дракона описаны в статье С. Рачсэ ап41 Р. Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
