Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 77
Текст из файла (страница 77)
[Начальная установка.) Установить к т- О. 82. [Выполнить?) Если и = О, завершить выполнение алгоритма. 83. [Выбрать.[ Если число и четное, установить и е- н/2: иначе — включить в представление 2"т(э и установить и т — (и — т(э)/2. 84. [Увеличить Й.[ Увеличить к на 1 и перейти к шагу 82, $ На шаге 83 приведенного алгоритма [и[ уменьшается до тех пор, пока не выполнится равенство и = -Втц следователыю, алгоритм должен завершиться.
(т1) Две итерации шагов 82-84 алгоритма приводят к преобразованию 4тн -э т. 4тп + 1 -+ тп + 5, 4тп+ 2 -+ тл + 7, 4пт + 3 -т ш — 1. Рассуждая, как в упр. 19, остается толька показать, что алгоритм завершит работу при — 2 < и < В; все остальные значения числа и сдвигаются в этот интервал.
Для данного интервала имеем следующую структуру дерева: 3 -+ — 1 -+ -2 -+ 6 -ч В -э 2 -+ 7 -ч 0 и 4 -+ 1 -т 5 -т 6. Таким образом, 1 7 2о 13 2т+7 2т 13 2з 13 2з 13 2э+? 2о Примечание. Выбор т(е, т(т, т(т, ... = 5, — 3, 3, 5, -3, 3, ... также дает бинарный базис. Более подробно с этим вопросом можно ознакомиться в работвх Май.
Сошр. 18 (1964), 537-546; Л. В. Вант(э, Асса МаВь Агат). 8ст. Нипб. 8 (1957), 65-86. 31. (См, относящиеся к этому вопросу упр. 3.2.2-11, 4.3.2-13, 4.6.2-22.) (а) Умножая числитель и знаменатель на подходящую степень 2, можно полагать, что и = (...ктн но)т и а = ( . атвтоо)т, где аа = 1, являются 2 адическими целыми числами. Для определения ш можно прибегнуть к следующему вычислительному методу, используя для целого числа (и, ., иа)т = н шот) 2" обозначение исэт (и > О). Пусть шо = ие и шит ы шо. Дчя и = 1, 2, ... полагаем, что найдено целое число шбй = (ит -т...ша)т, такое, что ищт ьз вривт1"т (по мсаулю 2 ), тогда мы+и ж оы+Отош1 (по модулю 2").
Поэтому можно положить ю„= О или 1 в соответствии с тем, чему равно число (вт +М вЂ” гщецшри) шот) 2"+': нтлю или 2" (Ь) Найдем наименьшее целое число к, такое, что 2" и 1 (по модулю 2п+ 1). Тогда 1/(2п + 1) = тп/(2 — 1) для некоторого целого числа т, 1 < тп < 2~ '. Пусть о есть йразрядное двоичное представление для т; тогда в двоичной системе число (О.аоа... )т, умноженное на 2п + 1, равно (0.111...)т = 1, а в 2-аднческой системе (...оно)т, умноженное на 2п + 1, равно ( .. 111)з = — 1. (с) Если и рационально, скюкем, н = тл/(2'и), где и — нечетное и положительное число, то 2-адическое представление числа и периадично, так как множество чисел с периодическим разложением содержит -1/и и замкнуто относительно операций изменения знака, деления на 2 и сложения.
Наоборот, если для всех тУ > и соблюдается влез = вл, то 2-адичегкое представление числа (2" — 1)2 "н есть целое число. (т)) Квадрат любого числа вида (... итвт 1)э имеет вид (... 001)э, поэтому сформулированное условие является необходимым, Достаточность доказывается наличием следующей процедуры вычисления о = т/л лля случая, когда и шат) В = 1. Н1. [Начальная установка.) Установить ш т — (и — 1)/8, )т +- 2, аа т — 1, от +- О, э т- 1. (При выполнении этого алгоритма получим а = (иь т... от во)э и о = и — 2 т.) т т+т Н2.
[Преобразования,] Если тл четно, установкть тч +- О, пт +- тл/2. В противном случае установить аз+- 1, т+- (пт — э — 2 )/2, а т — а+ 2 . ь-т э НЗ. [Приращение к.[ Увеличить к на 1 и вернуться к шагу Н2, $ 32. Более общий результат опубликован в журнале Масб. Сошр. 29 (1975), 84-86. ЗЗ. Пусть ʄ— множества всех таких и разрядных чисел, что lт„= [К„[. Если множества Я и Т являются произвольными конечными множествами целых чисел, можно утверждать, чтодлянекоторогоцелогочислах Я Т при 5 = Т+х, и можно записать к„(з) = [гс„(з)[, где К„(8) --семейство всех подмножеств К„, принадлежащих - 8, Прн и = 0 выполняется Ь„(Я) = О, однако )Я) < 1, так как нуль является единственным 0-разрядным чиг толь При и > 1 и Я = (зл,..., з,) имеем К.(я) = (/ Ц ((г,Ь+~,,...,г,Ь+~,) ~ о<г<ь ыл,..., Ю (Гг,...,з,) Е К„г(((з, + у — гг,)/Ь! 1 < ь < г))), где внутреннее объединение представляет собой полные последовательности цифр (аы...
...,и,), удовлетворяющих условию а, ья з, + / (по модулю Ь) при 1 < ь < г. Потребуем для однозначности определения индексов в этой формуле, чтобы (з, — а;)/Ь вЂ” (з, — а, )/Ь при 1 < г < л < г. Согласно принципу включения и исключения получаем Ьл(5) = 2 е«,ь т,„,>,(-Ц~ '/(Ялп,,у), где /(л,щ,у) — количество множеств целых чисел, которые могут бйть выражены в виде (гль+ ан ..,,г,ь+ а,) описанным выше способом применительно к гл различным последовательностям (щ,...,а,), причем выражение суммнруется по всем выборкам из гл различных последевательностей (ал,...,а,), Для цолученных щ различнмх последовательностей (а;,...,а„) при 1 < 1 < па количество таких множеств равно й„л(((зг+,г — а~ ~)/Ь ) 1 < г < г,1 < 1 < т)).
Итак, нлгеем набор множеств T(Я), таких, что Ь.(5) = Е ст Ь (Т), гзт1з~ где каждое ст есть целое число. Более того, если множество Т 6 Т(Я), то его элементы близки к элементам множества 5 и имеем тпгТ > (ш(п5 — шахВ)/Ь и шахТ < (шахЯ+ Ь вЂ” 1 — пил(1)/Ь Ьгп(з) з(801(г) + Ьег(з)), Ьолг(з) = 0 Ье(з) = 1+ э(Зке(з) — Ьш(г)), йог(г) = зйо(з), и Ь(з) ж 1/(1 — Зз + зг), Тогда Ь = Рг„+г и Ьь((0,2)) = Гг л — 1. 84. Существует единственная цепочка а символов (1,0, Ц, такая, что н = (а„)г и в а„ нет ни ведущих нулей, ни последовательных ненулевых элементов; ае пусто; в противном случае агь м а„0, аь,зл —— ал01, аг л = а„01.
Любую цепочку, содерлхащую и, можно преобразовать в а„при помощи сжатия 11 -ь 01, 11 -ч 01, 01... 11 -ь 10... 01, 01... 11 -а 10... 01 и добавления или исключения ведущих нулей. Так как операции сжатия не увеличивают количество цифр, отличных от нуля, то в а„содержится наименьшее количество. (Адталсез гп Сошригегз 1 (1960), 244-260.) Количество р(п) ненулевых цифр в а„— зто количество единиц в обычном представлении, перед которыми сразу же помещается либо нуль, либо подстрока 00(10) 1 для некоторого Ь > О. Обобщение для систем представления по основанию Ь > 2 предложено Й. фон цур Гаханом (Я. топ гаг Оас)леп), Сошрагагюла( Сошр)ех1гу 1 (1991), 360-394. Таким образом, получены рекуррентные соотношения для последовательностей лгножеств (й„(Я)), в которых множество 5 порождает подмножества целых чисел [1..н + 1) (в обозначениях упр.
19). Последовательность ()г,) появляется в процессе 4юрмирования этих рекуррентных соотношений, так как Ь = Ь„(л) для любого элемента множаства Ю. Коэффициенты ст могут быть вычислены через несколько начальных значений йь(Я), так что можно получить систему уравнений для определения производящих функций Ьз(з) = 2 й (Я)з" = ((53 < Ц + г ~гет<з> стйг(з) (см..1. А)богггйщз 2 (1981), 31-43). Например, при В = (-1,0,3) и Ь = 3 имеем 1 = -з и а = -', так что искомымн множествами Я являются (0), (О, Ц, ( — 1, Ц и (-1,0, Ц. Соответствующие соотношения для и < 3 имеют вид (1,3,8,21), (0,1,3,8), (0,0,1,4) и (0,0,0,0).
Итак, получено РАЗДЕЛ 4,2.1 1. 1л' = (62, +.60 22 14 00); Л ж (37, +.66 26 10 00), Обратите внимание на то, что значение 10Л имело бы вид (38, +.06 62 61 ОО). 2. 6'- (1 - 6- ), Ь- —; Ь - (1-6- ), Ь- -'. 3. Если е не принимает своего наименыаего значения, та наиболее значиллый разряд, в котором во всех таких нормализованных числах стоит единица, можно не включать в машинное слово (т. е.
не хранить, а подразумевать при выполнении операций). 4. (51, +. 10209877); (50, +.12346000); (53, +.99999999). Если бм первый операнд равнялся (45, —.50000000), то третий ответ был бы (54, +,10000000), поскольку Ь/2 иечетио. 5. Если х у и т есть целое число, то щЬ+х глЬ+у, Более того, если рассмотреть все возможные случаи, то окажется, чта из х у следует х/Ь у/Ь. Другое важное свойство состоит в том, что х и у будут округлены до одного и того же целого при любых х у. Теперь, если Ь " зг, Р' /„, необходимо получить (Ье+~/„) шог( Ь 14 О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
