AOP_Tom2 (1021737), страница 66
Текст из файла (страница 66)
иерее. (Следовательно, системы со смешанным целочисленным основанием обладают этим свойством. Наиболее общими системами такого типа являются системы со смешанным основанием, у которых Ог = (со+ 1)Зо, Оэ = (с~ + 1)(со+ 1)бщ, д-~ = ~3эйс-~ Ч 1): . ") 27. (МЯ1] Покажите, что любое ненулевое число имеет единственное "знакоперемениое двоичное представление" 2'о — 2'1 + ° + ( — 1)~2", гдеео<с~ < . <еь ь 29, (Мв(] Покажите, что любое неотрицательное комплексное число нида а + Ь|, где о и Ь вЂ” целые числа, обладает единственным "периодическим двоичным представлением" П+ )ээ+ (1„) ~ (1+ ) г (1+.)езЧ + э(1+ где ео < е~ < < е~ (ср.
с упр. 27). 29. (МЗЬ] (Н. Г. де Брейн (Х. С с)е Вгп1]п).) Пусть 5о, Яы Яю ... — множества неотрицательных целых чисел; говорят, что совокупность (Яо, Яп Яю ) обладает свойством В, если любое неотрицательное целое число и может быть единственным способом записано в виде и=во+э~+аз+, вэбом (Свойсгво В означает, что О Е Я„для всех у, поскольку и = О может бьггь представлено только как О+О+О+ .) Любая система счисления со смешанным основанием Ьо, Ьп Ьм дает пример совокупности множеств, удовлетворяющих свойству В, если положить 5, = (О, Вэ,,(Ьз — 1)В,), где Вз = ЬоЬ~., Ьз-ь В таком случае представление и = эо + э~ + аз + очевидным образом соответствует представлению (9) этого числа по смешанному основанию. Далее, если совокупность (Яо, Ям Яз, .
) Ао, Ам Аю обладает свойством В, то, каково бы ни было разбиение Ао, .4п Ап ... неотрицательных целых чисел (т е. Ао 0 А~ 0 Аз 0 .. = (О, 1,2,...) и А, ПА, = 9 при 1 Ф з', некоторые нз множеств Аз могут быть пустыми), этим свойством обладает н полученная из нее путем "стягивания" совокупность (То, Т,, Тп. -.), где множество Т, состоит из всех сумм нида 2; л э„взятых У по всевозможным выборкам элементов э, Е Я,. Докажите, что любая последовательность (То, Тп Тэ, ), удовлетворяющая свойстну В, может быть получена посредством "стягивания" некоторой совокупности (Яо, Яь Яз, ...), соответствующей системе счисления по смешанному основанию.
30. [МЯУ] (Н. Г. де Брейн.) Пример системы счисления по основанию — 2 показывает, что любое целое число (положительное, отрицательное нли нуль) имеет единственное представление в виде (-2)" + ( -2)" + + (-2)"', е~ > ез > > ес > О, 1 > О. Назначение данного упражнения — несколько обобщить это снойство. а) Пусть последовательность целых чисел Ьо, Ьп Ью... такова, что любое целое число и допускает единственное представление в аиде и = Ь„+ Ь,~ + ° + Ь...
е~ > еэ > > е~ > О, 1 > О. (Данная последовательность (Ь„) называется бинарным базисом.) Покажите, что найдется такое значение индекса 1, что Ьз нечетно, а для всех Ь ф У числа Ь, четны. Ь) Докажите, что бинарный базис (Ь„) всегда может быть преобразован в последовательность вида Ио, 2Ап 4оэ, = (2" Ач), где каждое из чисел А нечетко. с) Докажите, что если каждое из чисел 4о, 4п ~, ... из п. (Ь) равно х1, то последовательность (Ь„) образует бинарный базис тогда и только тогда, когда существует бесконечно много Им равных +1, и бесконечно много Нм равных -1. и = ( .. изизи1ио.и 1., и „)з, предстанление которого бесконечно продолжается влево и лишь на конечное количество знаков вправо от разделяю|цей точки.
Сложение, вычитание и умножение 2-адических чисел выполняются в соответствии с алгоритмом обычных арифметических операций, которые, в принципе, допускают возможность неограниченного продолжения влево. Например, — = (... ПОПОПОПОГП)з — ! = (... 001001001001001)2 —,'„= (... ПООПООПООП0.1), 7 = (...ооооаоооооооГП, -7 = (.,. П1ПППП1001)з -" = (...
ОООООООООООО001. П)з ,/:7 = (... 10ааааа1ОПОР31) з или (...ОППП010010П)з. Здесь число 7 — обычное число "семьи в двоичном представлении, а -7 — обратный код, неограниченно продолженный влево. Легко проверить, что обычная процедура сложения двоичных чисел дает — 7 + 7 = (...00000)з — — О, если ее выполнение продолжать неограниченно долго Значения -' и — -' представляют собой единственные 2-адические числа, которые после формального умножения на 7 дают соответственно 1 и -1.
ЗначениЯ 2 н —,о есть пРимеРы 2-аднческих чисел, не ЯвлЯющихсЯ 2-адическими "целыьпГ, так как они имеют ненулевые биты справа от разделяющей точки. Приведенные два значения т/-7, получающиеся одно из другого в результате перемены знака, являются единственными 2-адическими числами, которые после формального возведения в квадрат дают (... ПППППП001)з. а) Докажите, что любое 2-здическое число о можно разделить на произвольное ненулевое 2-адическое число о, чтобы вычислить 2-адическое число ш, удовлетворяющее равенству и = ош. (Следовательно, множество 2-адических чисел образует поле; см.
раздел 4.6.1.) Ь) Докажите, что 2-адическое представление рационального числа — 1/(2п+ 1), где и— положительное целое число, можно получить следующим образоль Сначала находим обычное двоичное разложение числа +1/(2п + 1), которое имеет вид периодической дроби (О.ооо .. )з (о — некоторая строка иэ нулей и единиц). Тогда (... поп)з будет 2-адичегким представлением числа — 1/(2п+ 1). с) Докажите, что 2-адическое представление числа и периодично (т. е. изтх = вх для всех больших !у при некотором Л ) 1) тогда и только тогда, когда в рационально (т.
е. и = т/и для некоторых целых чисел ш н и). д) Докажите, что если и — целое чишю, то т/й является 2-адическим числом только в толю случае, если для некоторого неотрицательного целого числа и оно удовлетворяет условию пшел 2з"ьэ = 2~ь. (Таким образом, либо п|подВ = 1, либо пшоб32 = 4, нт.д) 32. (М40) (И. 3.
Рупа (1. Е. Нокза).) Сформируйте бесконечно много целых чисел, в трончных представлениях которых используются только нули и единицы, а в четверичном представлении — только нули, единицы и двойки. Й) Докажите, что последовательность 7, -13 2, 7 2~, — 13 2, ..., 7 2з", — 13 2з"+', ... является бинарным базисом, и найдите представление числа и = 1.
ь 31. [МУЗ) Одно обобщение представления чисел в обратном двоичном коде, известное как "2-адические числа", было предложено в работе К. Непзе!. Сге!!е 127 (1904), 51 64. (В действительности К. Гензель предложил р-адоческое числа для любого простого числа р.) 2-адическое число можно рассматривать как двоичное число 33. (М40] (Д.
А. Кларнер (Р. А. К!агпег).) Пусть множество Р— произвольное множество целых чисел, 6 — любое положительное целое число, а ܄— количество различных целых чисел, которые могут быть записаны как и-разрядные числа (а„ю .. а,ае)ь по основанию Ь с цифрами а; в О. Докажите, что последовательность (Зм) удовлетворяет линейному рекуррентному соотношению, н поясните, как вычислить производящую функцию 3 „Ь„х". Проиллюстрнруйте разработанный алгоритм, показав, что в случае, когда Ь = 3 и Р = ( — 1, 0,3), число й„есть число Фибоначчи. ь 34. (23) (Г. В.
Райтвайзнер (6. ЪЧ. Ве!ги(езпег), 1960.) Поясните, как представить заданное целое число и в виде (... нта~ае)ю где каждое из аз есть — 1, 0 либо 1, используя наименьшую ненулевую цифру. 4.2. АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ В этОм РАзделе рассмотрены основные принципы выполнения арифметических операций над числами с "плавающей точкой" и проанализирован внутренний механизм таких вычислений. Вероятно, у многих читателей данная тема не вызовет слишком большо~о интереса либо потому, что в вычислительных машинах, на которых они работают, имеются встроенные команды операций над числами с плавающей точкой, либо потому, что нужные подпрограммы содержатся в операционной системе.
Но не следует считать, что материал этого раздела относится исключительно к компетенции инженеров — конструкторов ЭВМ или узкого круга лиц, которые пишут системные подпрограммы для новых машин. Каэсдюй грамотный программист должен иметь представление о том, что происходит при выполнении элементарных шагов арифметических операций нвд числами с плавающей точкой. Предмет этот совсем не так тривиален, как приннто считать; в нем удивительно много интересного. 4.2.1. Вычисления с однократной точностью А. Обозначение чисел с плавающей точкой.
В разделе 4.1 были рассмотрены различные способы обозначения чисел с фиксированной точкой. При таком способе обозначения программист знает, где положено находиться разделяющей точке в числах, с которыми выполняются те илн иные операции. В некоторых ситуациях прн выполнении программы значительно удобнее сделать положение разделяющей точки динамически изменяющимся, иными словами, сделать точку "плавающей" и связать с каждым числом информацию о ее положении. Эта идея уже давно использовалась в научных расчетах, в особенности для представления очень больших чисел наподобие числа Авогадро Х = 6.02214 х 10ы или таких очень малых чисел, как постоянная Планка Ь = 6.6261 х 10 ~~ эрг с.
В этом разделе речь пойдет о р-разрядных числах с плавающей точкой по основапию Ь с избмшком 4. Такое число представляется парой величин (е, у), которой отвечает значение (е, У) = У х Ь '. (1) ЗдеСь е — целое число, изменяющееся в соответствующем интервале значений, а у— дробное чиг.ю со знаком. Условимся, что (У! < 1, иными словами, разделяющая точка в позиционном представлении / находится в крайней слева позипнн. Точнее говоря, соглашение о том, что мы имеем дело с р-разрядными числами, означает, что Ь" г' — целое число и — Ь <Ь"У<Ь".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
