Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 65
Текст из файла (страница 65)
4.4.) Затем добавим к нему в троичной системе бесконечное число ...11111.1П11..., после чего получим для Уравновешенные троичные числа 101 1110.11 1110.11 1110 0.11111... Десятичные числа 8 32$ -321 з -33 % вышеприведенного примера бесконечное число (...ПП1210012.210121012101 ...)з. Наконец, вычтем ...1ПП.ПП1... поразрядно, уменьшая на единицу каждую цифру, и получим 208.3 = (101101 101010101010 - )з. (8) Этот процесс можно сделать вполне строгим, если заменить искусственное бесконечное число ... ПП1.П1П...
некоторым числом с соответствующим количеством единиц, Уравновешенная троичная система счисления обладает многими привлекательными свойствами. а) Отрицание числа осуществляется взаимной заменой 1 и 1. Ь) Знак числа задается его наиболее значимым ненулевым тритом; в общем случае можно сравнивать любые два числа, используя лексикографический порядок при чтении слова слева направо, как в десятичной системе. с) Операция округления до ближайшего целого идентична усечению; другими словами, просто отбрасывается все, что стоит правее разделяющей точки. Операция сложения в уравновешенной троичной системе выполняется совсем просто, если воспользоваться таблицей сложения, 11111111100ОООООО0111111111 111000111111000111111000111 101101101101101101101101101 10 и 1 11 1 о 1 о 1 и 1 о 1 о 1 о 1 11 1 о 1 о 1 и 1 и 10 (Три входных грига — это триты двух наших слагаемых и грит переноса.) Вычитание состоит в формировании числа, противоположного по знаку вычитаемого, и последующем выполнении сложения.
Умножение также сводится к операциям перемены знака и сложения, как в следующем примере. 1101 [17] 1101 [17[ 1101 11010 1101 0111101 [289[ Представление чисел в уравновешенной троичной системе неявно присутствует в одной знаменитой математической головоломке, обычно называемой "'задача Баше (ВасЬег) о весах", хотя она была сформулирована еше Фибоначчи за четыре столетия до того, как Ваше написал свою книгу, а перс Табари сделал зто еще раньше— более чем за 100 лет до Фибоначчи.
[См. %. АЬгепв, Магйетаг1зсЛе 17лгегйайплйел ипг) Бр1е)е 1 (Ье1рзйр ТепЬпег, 1910), 8есйоп 3.4; Н. Негше!ш1с, Халил 65 (1978), 105-П7.) 11озиционные системы счисления с отрицательными цифрами были изобретены Дж. Колсоном (3, Со!зоп) [РЬ))оз. Тгапя. 34 (1726), 161-173[, затем забыты и вновь открыты примерно через 100 лет Джоном Лесли (8!г ЗоЬп Ье»!!е) (ТЬе РЬ!!о»орйу о/ АгйбпгегХс (Ес!!пЬиг8Ь, 1817); см. с. 33-34, 54, 64-65, 117, 150) и А. Коши (А. СапсЬу) !Сошр!е» Вепс(п» Асад. Ясй Раг!» 11 (1840), 789-798]. Коши отмечал, что отрицательные цифры позволяют избежать необходимости помнить таблицу умножения после 5 х 5.
Утверждение, что подобные числовые системы были давно известны в Индии (Я. Бхарати (3. ВЬагаб), Ъесйс Ма»ЬешаВс» (Ве1ЬЬ Моб1а! Вапаг»!с!а»», 1965)], было опровергнуто К. Ш, Шуклой (К, 8. 8ЬпЫа) (Ма»Ьегпа!!са) Едисаг!ол 5, 3 (1989), 129-133). В "чистом" виде уравновешенная троичная система счисления появилась в статье изобретателя механических вычислительных устройств Леона Лаланна (Ьеоп Ьа)аппе) [Ссипр»е» Велс(н» Асад. Ясй Раг!» 11 (1840), 903-905).
Система оставалась незамеченной до тех пор, пока спустя 100 лет после публикации Лвланна в Электротехническом институте Мура в 1945-1946 годах не стали разрабатывать первые электронные вычислительные машины. В то время она наряду с двоичной системой серьезно рассматривалась и качестве возможной альтернативы десятичной системе. Сложность электронных схем арифметических устройств для уравновешенной троичной арифметики не вшивого выше, чем для двоичной системы, а чтобы задать число, в ней требуется лишь !и 2/1п 3 в 63% цифровых позиций от того количества, которое необходимо для представления чисел в двоичной системе. Дискуссии по поводу уравновешенной троичной системы счисления опубликованы в журнале АММ 57 (1950), 90 — 93, и в сборнике Н!86-»реег! Сошри»!ггй 0ег!се», Епй!пеег!пй Ве»еагсЬ А»»ос)а!е» (МсОгаж-Н)0, 1950), 287-289. Уравновешенная тро.
ичная система счисления была положена в основу экспериментальной советской вычислительной машины СЕТУНЬ (см. САСМ 3 (1960), 149-150)*. Возможно, симметричные свойства н простая арифметика этой системы счнгтления окажутся в один прекрасный день весьма существенными (когда ьфлип-флопя заменится пфлип-флэп-флопомп)**. Еще одно важное обобщение. позиционного способа представления чисел - это позиционная система со смешаннмлс осмоеамиелс. Если дана последовательность чисел (6„), где и могут быть отрицательными, то по определению полагается ! ...,аз,аа,амао! а м а т,...
..., Ьз~ 62, Ьм Ьб Ь-г ~ 6-2 ° + а»6»ЬгЬо+а»616о+агЬо+по+ а 1/Ь.г+ а т/6 гЬ т+ -. В простейших системах со смешанным основанием используются только целые числа; Ьо, Ьг, Ьт, ... полагаются целымн числами, ббльшими единицы, и рассматриваются только такие числа, которые не содержат разделяющей точки, причем а„ должно принадлежать интервалу 0 < а„< Ь„. Одна из наиболее важных систем со смешанным основанием — — это факспориольмал система счисления, где 6„= и+ 2. С ее помощью можно единственным образом ь см. также Бруснеиов и.
и. н др. малая литровая вычислительная машина "сетунь". — м., 1965. — Прим, мрее. еь Здесь в оригинале — игра слов. Словосочетание "й|р-йор" (дословно "щелчок-шлепок") означает в английской технической литературе влемент с двумя устойчивыми состояниями. По аналогии "й|р-йар-йор" (дословно "пселчок-хлопок-пслепок") должно означать влемент с тремя у< тойчи. выме состояниями. — Прель иерее. представить любое неотрицательное целое число в виде (10) с„п)+ с„~ (и — 1)(+ +сз2(+ се, г де 0 < ць < А для 1 < и < и и с„ф. 0 (см.
алгоритм 3.3.2). Системы со смешанным основанием часто встречаются в нашей повседневной жизни: речь идет о единицах измерения. Например, величина "3 недели, 2 дня, 9 часов, 22 минуты, о7 секунд и 492 миллисекунды" может быть представлена в виде 3,2, 9,22,о7; 492) 7, 24, 60, 60; 1000~ Величина "10 фунтов, 6 шиллингов и три с половиной пенса" до перехода Великобритании к десятичной системе в денежных расчетах есть не что иное, как е',з' '~ британских пенсов. Числа со смешанным основанием можно складывать и вычитать, применяя очевидное обобщение обычных алгоритмов сложения и вычитания прн условии, что для обоих операндов используется одна и та же система (см. упр.
4.3.1). Подобным образом можно легко умножать или делить числа со смешанным основанием на малые целые константы, используя простое расширение общеизвестных приемов счета карандашом на бумаге. В общем виде системы со смешанным основанием впервые были проанализированы Георгом Кантором (Сеогй Сапсог) (2ейясбг!й йг МаГЬ. ппд Рбузй 14 (1869), 121-128]. Дополнительная информация о таких системах содержится в упр.
26 и 29. У. Перри (%. Расту) исследовал некоторые вопросы, относящиеся к ирраццонольньсм основаниям (см. Асса Май, .4сад, Вс? Вилл. 11 (1960), 401-416). Помимо описанных здесь систем счисления, существует несколько других способов представления чисел, которые упоминаотся в этой серии кинг: биномиальная система счисления (упр. 1.2.6-56), система Фиббначчи (упр.
1,2.8-34, 5.4.2-10), 15-система (упр. 1,2.8-35), модульное представление (раздел 4.3.2), код Грея (раздел 7.2.1) и система с римскими цифрами (раздел 9.1). УПРАЖНЕНИЯ 1. (15) Выразите числа -10, -9, ..., 9, 10 в системе счисления по основанию -2. 2. (24) Рассмотрите следующие четыре системы счисления: (к) двоичную (прямой код), (Ь) пегадвоичную (основание -2), (с) уравновешенную троичную и (д) систему по основанию 5 =. —,'е. Используйте зти четыре системы для представления каждого из трек чисел: (1) — 49; (и) -Зг (укажнте период); (ш) я (нескохько значащих цифр).
3. (20) Выразите -49+ 1 в мнимочетвернчной системе. 4. (15) Предположим. имеется И1Х-программа, в ячейке памяти А которой находится число, разделяющая точка которого расположена между 3- и 4-и байтами, а в ячейке памяти В--число, разделяющая точка которого расположена между 2- и 3-м байтами. (Крайний <шева байт имеет номер 1.) Где будет распопагаться разделяющая точка в регистрах Л и Х после выполнения команд (Ь) ьРА А; ЯВАХ $; 01т В? (а) ЫА А; И1Л. В 5. (00) Объясните, почему представление отрицательного целого числа в обратном коде всегда на единицу меньше представления в дополнительном коде, если рассматривать зти представления как положительные числа.
6. [!6] Каковы наибольшее и наименьшее р — битовые целые числа, которые могут быть представлены в двоичной системе посредством (а) прямого кода, (Ь) обратного кода, (с) дополнительного кода? 7. [МЯ0] В тексте раздела десвтичное представление с дополнением до десяти определено только для целых чисел, записанных в одном машинном слове. Можно ли аналогично определить представление в этом же формате Йлл всех деастеителькмк косел, имеющих "бесконечную точность"? Существует ли подобный способ определения десятичного представления в обратном коде для всех действительных чисел? 8. [М!О] Докажите соотношение (5).
9. [!8] перевалите следующие восьмеричные числа в шесюкаднашерочкме, используя шестнадцатеричные цифры О, 1,...,9, А, В, С, О, Б, Р: !Я; бббб; 3880676; ?ббдб886; 8706?бб. 10. [МЯЯ) Обобщите соотношение (5) для систем со смешаннмм основанием, как в соотношении (9). 11. [ЯЯ] Разработайте алгоритм для вычисления суммы чисел (а„... агае)-г и (Ь» ЬгЬо)-г, дакиций результат в вцле (с„+г... сгсе) г, с помощью системы счисления по основаншо -2. 12. [38] Разработайте алгоритм перевода (а) числа, записанного в прямом двоичном коде м(а»...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
