AOP_Tom2 (1021737), страница 65
Текст из файла (страница 65)
полагаются целыми числами, ббльшими единицы, и рассматриваются только такие числа, которые не содержат разделяющей точки, причем а„ должно принадлежать интервалу 0 < ап < Ьп. Одна из наиболее важных систем со смешанным основанием - это 16акпзориальная сиспзема счисления, где Ьп гл и+ 2. С ее помощью можно единственным образом ь См, также Нрусиецов П. Н. и др. Малая цифровая вычислителышя мешине "Сетунь'.
— М., 1955. -- Прим. перев. *ч Здесь в оригинале — игра слов. Словосочетвиие "'й1р-вор*' (дословио "щелчок-шлепок") отвечает в английской текиической литературе злечеит с двумя устойчивыми гостояниялги. По аналогии "51р-йвр-йор" (дословио "щелчок-хлопок-шлепок') должке озивчать злемепт с тремя устойчивыми состояниями. — Прим. перев. представить любое неотрицательное целое число в виде (10) с„п!+с„г(п — 1)!+ +сг2!+сг, где 0 < св ( Л для 1 < Л < и и сп 55 0 (см. алгоритм 3.3.2). Системы со смешанным основанием часто встречаются в нашей повседневной жизни; речь идет о единицах измерения.
Например, величина "3 недели, 2 дня, 9 часов, 22 минуты, 57 секунд и 492 миллисекунды" может быть представлена в виде ! 3,2, 9,22,57; 492! 7, 24, 60, 60; 1000! Величина "10 фунтов, 6 шиллингов и три с половиной пенса" до перехода Великобритании к десятичной системе в денежных расчетах есть не что иное, как го, гг; г! о', ' ) британских пенсов.
10, б, 3; 1з Числа со смешанным основанием можно складывать и вычитать, применяя очевидное обобщение обычных алгоритмов сложения и вычитания при условии, чта дзя обоих операндов используется одна и та же система (см. упр. 4.3.1). Подобным образом можно легко умножать или делить числа со смешанным основанием на малые целые константы, используя простое расширение общеизвестных приемов счета карандашом на бумаге. В общем виде системы со смешанным основанием впервые были проанализированы Георгом Кантором (Сеогб Сапсог) )Ее11эсЛг)71 Гйг МабЛ. ипд РЛуюй 14 (1869).
121-128). Дополнительная информация о таких системах содержится в упр. 26 и 29. У. Перри (Ъ. Раггу) исследовал некоторые вопросы, относящиеся к нррационольным основаниям (см. Асба МаСЛ. Ага<У. Ясб Нипб. 11 (1960), 401 — 416). Помимо описанных здесь систем счисления, существует несколько других способов представления чисел, которые упоминаются в этой серии книг: биномиальная система счисления (упр. 1.2.6-56), система Фиббначчи (упр. 1.2.8 — 34, 5.4.2 — 10).
4-система (упр. 1.2.8-35), модульное представление (раздел 4.3.2), код Грея (раздел 7.2.1) и система с римскими цифрами (раздел 9.1). УПРАЖНЕНИЯ 1. [15) Выразите числа — 10, -9, ..., 9, 10 в системе счисления по основанию — 2. 2. [24) Рассмотрите следующие четыре системы счисления: (а) двоичную (прямой код) „ (Ь) негвлвоичную (основание — 2), (с) уравновешенную троичную и (й) систему по основанию 5 = —,'„. Используйте эти четыре системы для представления каждого из трех чисел; (~) — 49; (0) -3-' (укажите период); (щ) е (несколько значащих цифр). 3. [90) Выразите — 49+ г в мнимочетверичной системе.
4. [15] Предположим, имеется И1Х-программа, в ячейке памяти А которой находится число, разделяющая точка которого расположена между 3- и 4-м байтами, а в ячейке памяти В--число, разделяющая точка которого расположена между 2- и 3-м байтами. (Крайний слева байт имеет номер 1 ) Где будет располагаться разделяющая точка в регистрах А и Х после выполнения команд (в) ЬВА А; ИЛ. В (Ь) ЬВА А; ВВАХ Б; 91У В 7 5. [00) Объясните, почему представление отрицательного целого числа в обратном коде всегда ва единипу меныпе представления в дополнительном коде, если рассматривать эти представления как положительные числа. 6. [10) Каковы наибольшее и наименьшее р — битовые целые числа, которые могут быть представлены в двоичной системе посредством (а) прямого када, (Ь) обратного кода, (с) дополнительного кадаг 7.
[МЯ0] В тексте раздела десятичное представление с дополнением до десяти определено только для целых чисел, записанных в одном машинном слове, Можно лн аналогично определить представление в этом же формате для всех дейсвгвшлевьнмя чисел, имеющих "бесконечную точность"? Существует ли подобный способ определения десятичного представления в обратном коде для всех действительных чисел? 8. [М10] Докажите соотношение (5). 9. [15] Переведите следующие ввсьыерачнме числа в шесшнадцашеричнме, используя шестнадцатеричные цифры О, 1,...,9, А, 8, С, О, 8, Г: 18; бббб; 855087б; 70545530; 3780755.
10. [Мйй] Обобщите соотношение (5) для систем со смешанным основанием, как в соотношении (9). 11. [88] Разработайте алгоритм для вычисления суммы чисел (а„... а,аа)-г и (Ь„... .Ьгбо)-г, дающий результат в виде (с„+г...сгсо) г, с помощью системы счисления по основанию -2. 12. [83] Разработайте алгоритм перевода (а) числа, записанного в прямом двоичном коде ш(а» ао)г, в негадвоичное представление (Ь„ег... Ьо) г и (Ь) негадвончного представления (Ьеег ..
6э) г в прямой двоичный код ~(а„эг... ао)г. ь 13. [М81] Существуют числа, имеющие два различных разложения в бесконечную десятичную дробь, например 2.3599999... = 2.3600000.... Единственно ли представление чисел в негадесвтичнва (по основанию — 10) системе счисления илн существуют также вещественные числа по этому основанию с двумя различными бесконечными разложениями? 14.
[14] Умножьте (11321)г само на себя в мнимочетверичной системе, используя метод, описанный выше. 15. [М24] Как выглядят множества Я = ( 2 >, аз 6 " ] аь допустимая цифра), ышлогичные множеству, представленному на рнс. 1, в негадесятичной я мнимочетвернчной системах счисления? 16. [МЯ4] Постройте алгоритм сложения 1 с (а„...агав), г в системе счисления по осно- ванию г — 1. 17. [МЯ0] Может показаться странным, что в качестве основания в системе счисления берется число г — 1, а не аналогичное, но более простое число г + 1, Всякое ли комплексное число а+Ь1 допускает "двоичное" представление в позиционной системе по основанию г+ 1? 18.
[НМ38] Покажите, что множество Н, представленное на рис. 1, есть замкнутое множество, содержащее некоторую окрестность начала координат. (Следовательно, любое комплексное число допускает "двоичное" представление по основанию 1 — 1.) ь 19. [0Я] (Дэвид У. Матула (ВаеЫ Ж. Маги!а).) Пусть 11 множество целых чисел в системе с основанием 6, для которых уравнение к = 1 (по модулю 6) имеет точно одно решение при 0 < 1 < 6. Докажите, что все целые числа гл (положительные, отрицательные и нуль) могут быть представлены в виде гп = (а„.. ао)ь, где все аг принадлежат лшожеству Р, тогда н только тогда, когда все целые числа в интервале 1 < ш < в также представимы в этом виде, где 1 = — шах(а [ а б 11)/(Ь вЂ” 1) и и = — шш(а [ а б 11)1'(Ь вЂ” 1).
Например, 12 = ( — 1,0,..., Ь вЂ” 2) удовлетворяет данным условиям для всех Ь > 3. [Укаэанве. Постройте алгоритм, формирующий подходящее представленне.] 20. [НМ88] (Дэвцд У. Матула.) Рассмотрим десятичную систему счисления, в которой вместо (О, 1,...,9) используются числа 11 = ( — 1, 0,8, 17, 26,35,44,53,62, 7Ц. Из результата упр. 19 следует (как и нз упр.
18), что все действительные числа могут быть представлены бесконечными десятичными дробями с помощью цифр из множества Р. В упр. 13 отмечалось, что некоторые числа в обычной десятичной системе имеют два представления. (а) Найдите действительное число, которое имеет более двух Р— десятичных представлений. (Ь) Покажите, что ни одно действительное число не может иметь бесконечного множества Р— десятичных представлений.
(с) Покажите, что два или более Р (десятичных представлений) имеют бесконечно много цифр. ь 21. (Мйй) (К. Э. Шеннон (С. Е. БЬаппоп).) Может ли произвольное вещественное число (положительное, отрицательное нлн нуль) быть представлено в "уравновешенной десятичной» системе, т. е. в виде 2 л<„а!10" для некоторого целого числа и и некоторой последовательности а„, а„л, а„г, ..., где любое ал — это одно из десяти чисел (-4-, — Зг, -25, ! ! 1 -1г,— —, 5,15,25,3-„41)2 (Хотя нуль и не является одной из допустимых цифр, мы ! 1 ! ! ! 1 ! неявно полагаем, что а .лг, а„ел, ...— нули.) Найдите в этой системе счисления все представления нуля и все представления единицы. г 22.
(ПМ25) Пусть гг = — 2, >,10 . Докажите, что для заданного е > 0 н любого вещественного числа х существует такое "десятичное" представление этого числа, что 0 < (х — 2 " ал10 ! < е, где каждое нз чисел ал может принимать только одно из трех значений: О,.
1 нлн а. (В этом представлении отрицательные степени 10 не используются.) 23. (ПМЗО) Пусть множество Р есть множество Ь вещественных чисел, таких, что любое положителыюе чнщю имеет пРедставление 2 л<„алЬ, где все ал б Р. В У~Р, 20 показано, л что существует много чисел, не имеющих единсщееннееи представления. Тем не менее докажите, что множество Т всех таких чисел нлгеет лееру нуль, если О б Р. Покажите, что этот вывод не нуждается в доказательстве, если 0 ф Р. 24.
(МУ5) Найдите бесконечно много различных множеств Р, которые состоят из десяти неотрицательных целых чисел, удовлетворяющих следующим грел! условиям: (!) 5сг)(Р) = 1; (0) 0 б Р; (лл!) любое положительное вещественное число может быть представлено в виде 2 л<» а!10 для всех ал В Р». 25. (М25) (С А Кук (Я. А.
Соо1!).) Пусть Ь, и и и — целые положительные числа, причем Ь > 2 и 0 < и < Ь . Покажите, что представление числа и/о в системе счисления по основанию Ь не содержит последовательности нз и! цифр, равных Ь вЂ” 1, нигде справа от разделяющей точки. (Согласно общепринятому соглашению в стандартном представлении по основанию 6 не допускаются бесконечные последовательности цифр (Ь вЂ” 1).) ь 20.
(ПМ50) (Н. С. Мендельсон (М. Б. 61епбе!эоЬп),) Пусть (!5„) — последовательность вещественных чисел, определенная для всех целых п, — сю < и < оо, таких, что )3 < )3 +л; 1лш >9» = оо; 1нп о! = О. лг Пусть (и»)--произвольная последовательностыюложнтельных цетых чисел, также определенная для всех целых п, — оо < и < оо. Скажем, что число х допускает»обобщенное представление', если существует такое целое и и такая последовательность целых чисел а», а» !, и -г,..., что х = 2 <„ал1лл, гле а» р О, 0 < ал < сл н ал < сл для бесконечного множества Ь. Покажите, что каждое положительное вещественное число х допускает равно одна обобщенное представление тогда и только тогда, когда д +! = ~~ сл!3/с для всех и. л<» * Здесь н далее "бед» обозначает»наеболывий общий делитель" (йгеалеэ! сопноои бсггеог).— Прим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
