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