секунд.

представить любое неотрицательное целое число в виде

с„ п\ + с„ 1 (п - 1)! + • • • + С2 2! + сь (10)

где О < Cfc < А: для 1<А:<пис„510 (см. алгоритм 3.3.2).

Системы со смешанным основанием часто встречаются в нашей повседневной жизни; речь идет о единицах измерения. Например, величина "3 недели, 2 дня, 9 часов, 22 минуты, 57 секунд и 492 миллисекунды" может быть представлена в виде

3,2, 9,22,57; 492 7, 24, 60, 60; 1000

Величина "10 фунтов, 6 шиллингов и три с половиной пенса" до перехода Великобритании к десятичной системе в денежных расчетах есть не что иное, как 2о 12 2 британских пенсов.

Числа со смешанным основанием можно складьтать и вычитать, применяя очевидное обобщение обычных алгоритмов сложения и вычитания при условии, что для обоих операндов используется одна и та же система (см. упр. 4.3.1). Подобным образом можно легко умножать или делить числа со смешанным основанием на малые целые константы, используя простое расширение общеизвестных приемов счета карандашом на бумаге. В общем виде системы со смешанным основанием впервые были проанализированы Георгом Кантором (Georg Cantor) [Zeitschrift fur Math, und Physik 14 (1869), 121-128]. Дополнительная информация о таких системах содержится в упр. 26 и 29.

У. Перри (W. Parry) исследовал некоторые вопросы, относяпщеся к иррациональным основаниям (см. Acta Math. Acad. Sci. Hung. 11 (1960), 401-416).

Помимо описанных здесь систем счисления, существует несколько других способов представления чисел, которые упоминаются в этой серии книг: биномиальная система счисления (упр. 1.2.6-56), система ФибЬначчи (упр. 1.2.8-34, 5.4.2-10), (-система (упр. 1.2.8-35), модульное представление (раздел 4.3.2), код Грея (раздел 7.2.1) и система с римскими цифрами (раздел 9.1).

УПРАЖНЕНИЯ

1. [15] Выразите числа -10, -9, ..., 9, 10 в системе счисления по основанию -2. ► 2. [24] Рассмотрите следующие четыре системы счисления: (а) двоичную (прямой код), (Ь) негадвоичную (основание -2), (с) уравновещенную троичную и (d) систему по основанию Ь = j. Используйте эти четыре системы для представления каждого из трех чисел: (i) -49; (ii) -Зу (укажите период); (iii) тг (несколько значащих цифр).

3. [20] Выразите -49 + i в мнимочетверичной системе.

4. [15] Предположим, имеется М1Х-программа, в ячейке памяти А которой находится число, разделяющая точка которого расположена между 3- и 4-м байтами, а в ячейке памяти В - число, разделяющая точка которого расположена между 2- и 3-м байтами. (Крайний слева байт имеет номер 1.) Где будет располагаться разделяющая точка в регистрах А и X после выполнения команд

(а) LDA А; МШ, В (Ь) LDA А; SRAX 5; DIV В ?

5. [00] Объясните, почему представление отрицательного целого числа в обратном коде всегда на единицу меньще представления в дополнительном коде, если рассматривать эти представления как положительные числа.

6. [16] Каковы наибольшее и наименьшее р - битовые целые числа, которые могут быть представлены в двоичной системе посредством (а) прямого кода, (Ь) обратного кода, (с) дополнительного кода?

7. [М20] В тексте раздела десятичное представление с дополнением до десяти определено только для целых чисел, записанных в одном машинном слове. Можно ли аналогично определить представление в этом же формате для всех действительных чисел, имеющих "бесконечную точность"? Существует ли подобный способ определения десятичного представления в обратном коде для всех действительных чисел?

8. [М10] Докажите соотношение (5).

► 9. [15] Переведите следующие восьмеричные числа в шестнадцатеричные, используя шестнадцатеричные цифры О, 1,... ,9, А, В, С, D, Е, F: 12; 5655; 2550276; 76545336; 3726755.

10. [М22] Обобщите соотношение (5) для систем со смешанным основанием, как в соотношении (9).

11. [22] Разработайте алгоритм для вычисления суммы чисел (а .. • aiao)-2 и (Ьп •. ...bibo)-2, дающий результат в виде (с„+2.. • cico)-2, с помощью системы счисления по основанию -2.

12. [23] Разработайте алгоритм перевода (а) числа, записанного в прямом двоичном коде ±(а„ ... ао)2, в негадвоичное представление (bn+i .. Ьо)-2 и (Ь) негадвоичного представления (Ьп+1 • •. Ьо)-2 в прямой двоичный код ±(ап+1... ао)2.

► 13. [М21] Существуют числа, имеющие два различных разложения в бесконечную десятичную дробь, например 2.3599999... = 2.3600000 .... Единственно ли представление чисел в негадесятичной (по основанию -10) системе счисления или существуют также вещественные числа по этому основанию с двумя различными бесконечными разложениями?

14. [14] Умножьте (11321)2, само на себя в мнимочетверичной системе, используя метод, описанный выше.

15. [М24] Как выглядят множества S = { Ylk> \ kb~ йк допустимая цифра}, аналогичные множеству, представленному на рис. 1, в негадесятичной и мнимочетверичной системах счисления?

16. [М24] Постройте алгоритм сложения 1с (а„ ... aiao)i-i в системе счисления по основанию г - 1.

17. [МЗО] Может показаться странным, что в качестве основания в системе счисления берется число г - 1, а не аналогичное, но более простое число i + Всякое ли комплексное число а+Ы допускает "двоичное" представление в позиционной системе по основанию i-fl?

18. [НМ32] Покажите, что множество S, представленное на рис. 1, есть замкнутое множество, содержащее некоторую окрестность начала координат. (Следовательно, любое комплексное число допускает "двоичное" представление по основанию i - 1.)

► 19. [23] (Дэвид У. Матула (David W. Matula).) Пусть D - множество целых чисел в системе с основанием Ъ, для которых уравнение х = j (по модулю Ь) имеет точно одно решение при О < j < Ь. Докажите, Что все целые числа тп (положительные, отрицательные и нуль) могут быть представлены в виде тп - (а„...ао)б, где все Uj принадлежат множеству D, тогда и только тогда, когда все целые числа в интервале I < т < и также представимы в этом виде, где I = - шах{а а € D}/(b - 1) и и = - min{a а € D]/{b - 1). Например, D = {-1,0,... ,6 - 2} удовлетворяет данным условиям для всех Ь > 3. [Указание. Постройте алгоритм, формирующий подходящее представление.]

20. [НМ28] (Дэвид У. Матула.) Рассмотрим десятичную систему счисления, в которой вместо {0,1,..., 9} используются числа D = {-1,0,8,17,26,35,44,53,62, 71}. Из результата

упр. 19 следует (как и из упр. 18), что все действительные числа могут быть представлены бесконечными десятичными дробями с помощью цифр из множества D.

В упр. 13 отмечалось, что некоторые числа в обычной десятичной системе имеют два представления, (а) Найдите действительное число, которое имеет более двух D - десятичных представлений. (Ь) Покажите, что ни одно действительное число не может иметь бесконечного множества D - десятичных представлений, (с) Покажите, что два или более D (десятичных представлений) имеют бесконечно много цифр.

► 21. [М22] (К. Э. Шеннон (С. Е. Shannon).) Может ли произвольное вещественное число (положительное, отрицательное или нуль) быть представлено в "уравновешенной десятичной" системе, т. е. в виде Х*<па*10* для некоторого целого числа п и некоторой последовательности On, On-i, а„ 2, ..., где любое йк -это одно из десяти чисел {-4, -З5, -2, - 11, -, , l, 2, З5,4}? (Хотя нуль и не является одной из допустимых цифр, мы неявно полагаем, что an+i, Оп+г, ... - нули.) Найдите в этой системе счимения все представления нуля и все представления единицы.

22. [НМ25] Пусть а = -Em>ilO~". Докажите, что для заданного е > О и любого вещественного числа х существует такое "десятичное" представление этого числа, что О < \х - Xj o flfclO*! < f, где каждое из чисел а/ь может принимать только одно из трех значений: О, 1 или а. (В этом представлении отрицательные степени 10 не используются.)

23. [НМЗО] Пусть множество D есть множество Ь вещественных чисел, таких, что любое положительное число имеет представление Ylik<n ОкЬ, где все ак & D. В упр. 20 показано, что существует много чисел, не имеющих единственного представления. Тем не менее докажите, что множество Т всех таких чисел имеет меру нуль, если О 6 1>. Покажите, что этот вывод не нуждается в доказательстве, если О D.

24. [Л/55] Найдите бесконечно много различных множеств D, которые состоят из десяти неотрицательных целых чисел, удовлетворяющих следующим трем условиям: (i) gcd(D) = 1; (ii) О е D; (iii) любое положительное вещественное число может быть представлено в виде Y,k<n a/tlO* для всех о/ь е D*.

25. [М25] (С. А. Кук (S. А. Cook).) Пусть Ь, и и v - целые положительные числа, причем b>2и0<v<b". Покажите, что представление числа u/v в системе счисления по основанию Ь не содержит последовательности из т цифр, равных Ь - 1, нигде справа от разделяющей точки. (Согласно общепринятому соглашению в стандартном представлении по основанию Ь не допускаются бесконечные последовательности цифр (Ь - 1).)

► 26. [НМ80] (Н. С. Мендельсон (N. S. Mendelsohn).) Пусть (/3„)-последовательность вещественных чисел, определенная для всех целых п, -оо < п < оо, таких, что

/Зп < /Зп+i; lim /9„ = оо; lim Р„ = 0.

п-»оо п~* - оо

Пусть (сп) - произвольная последовательность положительных целых чисел, также определенная для всех целых п, - оо < п < оо. Скажем, что число х допускает "обобщенное представление", если существует такое целое п и такая последовательность целых чисел а„, а„ 1, ап-2, ., что х = Yk<n где а„ # О, О < а», < Cfc и Ofc < с* для бесконечного

множества к.

Покажите, что каждое положительное вещественное число х допускает ровно одно обобщенное представление тогда и только тогда, когда

Рп+1 = Ск0к для всех п.

к<п

* Здесь и далее "gcd" обозначает "наибольший общий делитель" (greatest common divisor).- Прим. перев.