Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 66
Текст из файла (страница 66)
аа)г, в негадвоичное представление (Ь +г... Ье) г и (Ь) негедвоичного представления (Ь»+г... Ьо)-г в прямой двоичный код ш(а»»г... ае)г. ь 13. [МЯ1] Существуют числа, имеющие два различных разложения в бесконечную десятичную дробь, например 2.3599999... = 2.3600000.... Единственно ли представление чисел в клгадесяшнчкоа (по основанию — 10) системе счисления или существуют также вещественные числа по этому основанию с двумя различными бесконечными разложениями? 14. [14) Умножьте (11321)г; само на себя в мнимочетверичной системе, используя метод, описанный выше. 15.
[МЯ4) Как выглядят множества 8 = ( ~г>, агЬ г ] аг допустимая шгфра), аналогичные множеству, представленному на рис. 1, в негялесятичной Н мнимочетверичной системах счисления? 16, [МЯ4] Постройте алгоритм сложения 1 с (а»...агав)г г в системе счисления по осно- ванию г — 1. 17. [М80] Ыожет показаться странным, что в качестве основания в системе счисления берется число г — 1, а не аналогичное, но более простое число г+ 1. Всякое ли комплексное число а+Ьг допускает "дюичное" представление в познпионкой системе по основанию г+1? 18. [ИМЯЯ) Покажите, что множество 8, представленное на рис. 1, есть замкнутое множество, содержащее некоторую окрестность начала координат. (Следовательно, любое комплексное число допускает "двоичное" представление по основанию г — 1.) ь 19.
[88) (Дэвид У. Ыатула (Ратай Ж. Ыагн!а).) Пусть Р— множество целых чисел в системе с основанием Ь, для которых уравнение х ш у (по модулю Ь) имеет точно одно решение при 0 <,! < Ь. Докажите, что все целые числа пг (положительные, отрнгштельные и нуль) могут быть представлены в виде тп м (а„... ао)г, где все а! принадлежат множеству Р, тогда н только тогда, когда все целые числа в интервале ! < т < о также представимы в этом виде, где ! = — шах(а [ а Е Р)((Ь вЂ” 1) и и = — шш(а ] а 6 Р)((Ь вЂ” 1).
Например, Р = (-1,0...5 — 2) удовлетворяет данным условияи для всех Ь > 3. [Указание. Постройте алгоритм, формирующий подходящее представление.) 20. [ВМЯВ] (Дэвид У. Ыатула.) Рассмотрим десятичную систему счисления, в которой вместо (0,1,...,9) используются числа Р = (-1,0,8,17,26,35,44,53,62,7Ц, Изрезультата упр. 19 следует (как и из упр. 13), что все действительные числа могут быть представлены бескоиечиыми десятичными дробями с помощью цифр из множества Р.
В упр. 13 отмечалось, что некоторые числа в обычной десятичной системе имеют два представления. (а) Найдите действительное число, которое имеет более двух Р— десятичных представлений. (Ь) Покажите, что ни одно действительиое число ие может иметь бесконечного множества Р— десятичцых представлений. (с) Покажите, что два или более Р (десятичных представлеиий) имеют бесконечно мпого цифр. ь 21.
(МОО) (К. Э. Шеннон (С. Е. ЯЬаппоп).) Может ли произвольное вещественное число (положительное., отрицательное или пущь) быть представлено в "уравновещеиной десятичной" системе, т. е. в виде 3„»б„а»10 ддя некоторого целого числа и и некоторой последовательности а„, а », а„», ..., где любое ໠— зто одно из десяти чисел (-41, — 33, -2», ! ! ! — 11.'„-3, ~1,11,2-',3!,41)? (Хотя нуль и ие является одной из допустимых цифр, мы иеявяо полагаем, что а +», а„+з, ...— нули,) Найдите в этой системе счисления все представления нуля и все представлении едииипы. 22.
(ПМОО) Пусть а = — 3 >»10 . Покажите, что для заданного с > 0 и любого вещественного числа х существует такое "десятичное" представление этого числа, что 0 < (х — 4.,'» а»10»( < с, где каждое из чисел а» может принимать только одна из трех значений: О, 1 или а. (В этом представлеиии отрицательиые степени 10 ие используются.) 23. (ПМОО) Пусть множество Р есть миожество Ь вещественных чисел, таких, что любое положительное число имеет пред<»ивлеиие 3„»<„а»Ь», где все а» Е Р. В упр, 20 показано, что суп»ествуег много чисел, не имеющих едйкствеккого представления.
Тем ие менее докажите, что множество Т всех таких чисел имеет меру нуль, если 0 Е Р. Пока»ките, что этот вывод не нуждается в доказательстве, если 0 й Р. 24. (МУО] Найдите бескоиечио много различных множеств Р, которые состоят из десяти неотрицательиых целых чисел, удовлетворяющих следующим трем условиям: (1) 3<4(Р) = 1; (й) 0 б Р; (й»!) любое положительное веществепиое число может быть представлено в виде Я»<„а»10 для всех а» б Р». 25.
(МОО) (С. Л. Кук (Б. А. Соо)с).) Пусть Ь, и и е — целые полоясительные числа, причем Ь > 2 и 0 < е < Ь, Покажите, что представление числа и/и в системе счисления по основанию Ь пе содержит последовательности из га цифр, равных Ь вЂ” 1, нигде справа от разделяющей точки.
(Согласно общепринятому соглашению в стандартном прелставлеиии по осцовапию Ь пе допускаются бесконечные последовательности цифр (Ь вЂ” Ц.) ь 26. (ИЬИО) (Н. С. Мендельсон (Х. Б. Мепс)е1зоЬв).) Пусть (О„) — последовательность вещественных чисюс, определенная для всех целых и, — сю < и < сю, таких, что !Зи <Д,+с, 1пп О» =сю; 1пп Д, =О. и-мв »-» -ао Пусть (с ) -- произвольная последовательность положитедьных целых чисел, также определенная для всех целых и, — оо < и < со. Скажем, что число х допускает "обобщенное представлеиие", если существует такое целое и и гак»л последовательность целых чисел а, а -!.
а -», ..., что х = ~ <„а»!3», где а„~ О, О < а» < с» и а» < с» для бесконечного множе«тва Й. Покажите, что каждое положительное вещественное число х допускает ровно сщпо обобщенпое представление тогда и только тогда, когда О .»! = ~ с»()Ь для всех и. »<» * Здесь и далее "йс»$" обозначает "иавбольшнв об!пвв делитель" (бсеасе»! сопипов Йы»щ).— Прим. иерее. (Следовательно, системы со смешаниым целочисленным основанием обладают этим свойством. Наиболее общими системами такого типа являются системы со смешанным основанием, у которых Д = (сэ+Цде, 5э = (сз+Ц(го+ Цбе, ..., 5-~ = 5о((с-к+Ц, ") 27.
(МИ) Покажите, что любое ненулевое число имеет едииствевиое "знакоперемеииое двоичное представление" 2~о 2ы ), 6( где ео < е~ < < е,. ь 28. [ЬЩ) Покажите, что любое неотрицательное комплексное число вида а + Ы, где а и Ь вЂ” целые числа, обладает едииствевиым "периодическим двоичным представлением" П1 )ы+ (161)м (1г )э 1(1 г)ы Ь, Ь 4(1 Ь )м где ео < е~ <. < е~ (ср.
с упр. 27). 29. (МЫ) (Н. Г. де Брейн (Х. С, бе Вгшзп).) Пусть Бш 5ы 5ы ... — множества неотрицательных целых чисел; говорят, что совокуппость (5о, 5ц 5м ..,) обладает свойством В, если любое неотрицательное целое число и может быть единственным способом записано в виде и = эо + э~ + ээ + ". эз б 51. (Свойство В означает, что 0 б 5 лдя всех у, поскольку и = О может быть представлеио только как 0+0+ 0+ ..) «Чюбая система счисления со смешанным осиоваиием 6о, Ьц Ьэ, дает пример совокупности множеств, удовлетворяющих свойству В, если пшюжить 5> —— (О,В1,,(61 — ЦВ1». где Вэ = ЬаЬ|...Ь, ь В таком «лучае представление и = эе + е~ + эз + очевидным образом соответствует представлению (9) этого числа по смешаииому основанию. Далее, если совокупность (5о,5ц5ю ) Ао,.
Ам Аы обладает свойством В, то, каково бы ии было разбиение Ао, Ам Ат, ... неотрицательных целых чисел(т, е. АеиА~ШАт11 .. = (0,1,2,..) и А,ПА = йпри1162, некоторыеиз множеств А могут быть пустыми), этим свойством обладает и полученная из иее путем "стягивания" совокупность (Тэ, Тп Ты, ..), где множество Тз состоит из всех сумм вида 2 ',. л эь взятых по всевозможным выборкам элементов еч б 5ь Докажите, что люэал последовательность (Те, Т,, 7ы, ), удовлетворяющая свойству В, может быть получена посредством "стягивания" некоторой совокупности (5э, 5п 5ц ...), соответствующей системе счисления по смешанному основанию.
30. (МЯУ) (Н. Г. де Брейи,) Пример системы счислению по основанию — 2 показывает, что любое целое число (положительное, отрицательное или нуль) имеет единственное пре» ставлеиие в виде (-2)" +(-2)" + . +( — 2)", е~ >си > >с~ > О, 1>О. Назначение даиного упражиепия — несколько обобщить это свойство. а) Пусть последовательность целых чисел Ьо, Ьп Ьт, ...
такова, что любое целое число и допускает единствеивое представление в виде ц=Ь,+Ь,+. +Ь„, е~>еэ> >е~>0. 1>0, (Данная последовательность (6,) называется бинарным базисом.) Покажите, что найдется такое значение индекса у, что Ьэ нечетно, а для всех Ь р',у числа Ьу четиы. Ь) Докажите, что бинарный базис (6 ) всегда может быть преобразован в последовательность вида 4>, 2И;, 4бы ... = (2" А„), где каждое из чисел 4, нечетко. с) Докажите, что е:ли каждое из чисел Иэ, сЬ, Иц...
из п, (Ь) равпо ш1, то последовательность (Ь„) образует бинарный базис тогда и только тогда, когда существует бесконечно иного Иэ, равных +1, и бесконечно миого бу, равиых — 1. н=(...пзвзи<кон <...к- )<, представление которого бесконечно продолжается влево и лишь на конечное количество знаков вправо от разделяющей точки. Сложение, вычитание и умножение 2-адических чисел выполняются в соответствии с алгоритмом обычных арифметических операций, которые, в принципе, допускают возможность неограниченного продолжения влево, Например, — ' ~ (... 11011011011ОШ)з --' = (...001001001001001)т 10 = (...
110011001100110.1)з нли (... 011111101001011)г. 7 = (... ООООООООООООШ) — 7 = (... Ш111111111001) -,' = (... 009)00000000001. П), </-7 = (... 10000001011010Ц< Здесь число 7 — обычное число "семь" в двоичном представлении, а -7 — обратный код, неограниченно продолженный влево, Легко проверить, что обычная процедура сложе- ния двоичных чисел дает -7+ 7 = (...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
