lekcii (Лекции)

([Ли11Ли1з(Л)Л) ~ [Лц1зЛ11,1(Л)Л)): ( 1й — 1 гй "О о 1 1йзп ~-1 гй-1-1 1 Машина Сшр тоже не нормирована. Она, сравнивает поразрядно слева направо два слоьа длины Й и останавливается во втором слове при обнаружении первого несоответствия. 1й-"1 Сшрй .й»1 Теперь опишем принцип работы машины деления. Как и в случае умножения, двоичная система серьезно упрощает сам процесс. Дело в том, что школьное деление «столбиком» не является алгоритмом, т. к. в вычислении очередной цифры присутствует элемент догадки -- подбор релевантного кратного делителю.

К счастью, в двоичной системе достаточно сравнить делимое и сдвинутый влево делитель. Далее, если делимое больше, то в соответствук11ций разряд частного необходимо записать единипу и вычесть делитель из делимого. Иначе в этот разряд частного помещается нуль, В лн1бом случае необходимо осуществить сдвиг делителя влево. Процесс заканчивается через 1с п1агов. В итоге получается частное и остаток.

Однако этот алгоритм в описании выглядит просто. Его реализация сложнее. В первую очередь это связано с необходимостью манипулировать сразу двумя вспомогательными словами. Если перейти к деталям, то машина деления работает так: 1. Делитель копируется направо от делимого, после чего эти два слова меняются местами для удобства организации процесса деления. 2. Перед делителем добавляется дополнительное слово из нулей, куда будет помещаться та часть делителя, которая «вылезает» из слова при его сдвиге влево.

После делимого также записывается слово из й нулей, куда будем помещено частное. 3. Делитель сдвигается на, Й вЂ” 1 разряд влево. 1. Первый бит частного помечается (замещается Л), чтобы правильно позиционировать мазпину в циклах, вьг1исляющих бить1 частного. ками С,1С ~ ~ и типичными микропроцессорами, в которых результат заме1цает на регистре один из операндов, первым словом яв гнется делитель, а вторым делимое.) Первой из таких машин является машина Яв'арй, которая обменивает местами два слова 5. Происходит сравнение делителя и делимого.

При этом учитывается содержимое до- полнительного слова, буферизующсто сдвиг. 6. Если делитель меныпе делимого, то происходит вычитание сдвинутого делителя из делимого и запись единицы в соответствующий разряд частного. В противном случае вычитания не происходит, а в этот разряд записывается нуль. 7. Делитель сдвигается на 1 разряд вправо. Помечается следующий бит. Если достигнут конец слова, то стираются лишние слова (делитель и дополнителыюе слово для храпения сдвинутого делителя), и остаток и частное меняются местами. Иначе деление продолжается с ц.

5. Еще пе определены машины Ро!п11К и л.»Яп11Ь, осуществляющие арифметический сдвиг двух двоичных слов людряд с переносом битов в соседнее слово вправо и влево соответственно. Схемы их работы: с»Я»1111л.: [Лгв»Лша(Л)Л) =~ [(Л)ли'Лил,'Л) Ьло1»|1»1: [(Л)ил»Ли~аЛ) => [Ли~, 'Ли" (Л)Л) 1)ЯЫ1ГЬ» г2 га г га гОг 1)Яп11Ь» 1а 1з 1 1з 101 Если оглределить дополнительную машину для записи слова 0... 0 1: » †ƻ л (гО)» 'г1г то можно на основе машины Сшр создать нормированные машины для сравнения слов, работающие по схеме [ЛийЛи»2(Л)Л) => [ЛийЛил~Ли(Л)Л).

Таким образом., целый тип также вычислим по Тьюрингу. Следует отметить также, что наиболес привычной системой счисления для человека является десятичная позиционная система. Как правило, именно в ней выполняются все 150 расчеты впе вычислительной машины. Подавлпощсс же Гюлыпинство современных машин оперирует с числами, представленными в системе счисления с другим основанием. (например, с основанием 2, или 8, или 16). Поэтому при вводе и выводе данных возникает необходимость перевода из одной системы счисления в другую (например, из десятичной в двоичну1о, из десятичной в шсстнадцатиричнук1 и наоборот). Рассмотрим решение этой задачи для данных целого типа. Задача перевода заключается в следующем.

Пусть известно изображение числа Л" в системе счисления с основанием Р: Х = (р.р„.. р1ро)р, где р, — цифры Р-ичной системы счисления (О < р, < Р— 1). Требуется найти изображение этого же числа Х в системе счисления с другим основанием Я: Л' = (Ч.Ч.-1 Ч1ЧО)а, где Ч, -- искомые цифры 11-ичпой системы счисления (О < Ч1 < б1 — 1). При этом можно ограничиться случаем положительных чисел, поскольку перевод любого числа сводится к переводу его модуля и приписыванию числу нужного знака. При рассмотрении правил перевода необходимо учитывать, средствами какой арифметики должен бьггь осуществлен перевод, т. е. в какой системе счисления должны бь1ть выполнены все необходимые для перевода арифметические действия.

Эти действия могут быть выполнены как в системе счисления с основанием Р, так и в системе счисления с основанием Я. '!тобы охватить все возможньн1 случаи, рассмотрим перевод из Я-ичной системы в Р-ичную (перевод Я вЂ” ~ Р) и обратный перевод (перевод Р— ~ с,) с выполнением действий в системс счисления с основанием Р. Перевод Я вЂ” ~ Р. Задача, перевода произвольного числа Х, заданного в системе счисления с основанием ~, Х = (Ч.Ч. — Ч1ЧО)а в систему счисления с основанием Р сводится к вычисленик1 значения соответствук1щего полинома.

Действительно, в силу последней формулы Х =Ч,. ~;~'-~ Ч,, О'-' 1" 4 Ч, О'1Ч,. Для получения Р-ичного изображения достаточно все цифры Ч, и число 0 заменить их Р-ичными изображениями и произвести все требуемые по формуле операции в Р-ичной системе счисления. Например, пусть требуется перевести число Х = (371)а в десятичную систему счисления, пользуясь средствами десятичной арифметики; здесь Р = 10, Я = 8. Для перевода зы1ишем число Х в виде Х = 3 82 + 7 81+ 1 и выполним все необходимые действия в десятичной системе счисления: Х = 3 64+ 7.

8+ 1 = 192+ 56+ 1 = 249. Еще пример. Пусть требуется перевести число Х = (4315)1 в троичную систему счисления, пользуясь средствами троичной арифметики; здесь Р = 3, Я = 7. Запишем Х = 4 7О + 3 7О + 1 7' + 5. Все цифры и основание семеричпой системы счисления заменим их троичными изображениями: Л = 11 21'О Р 10 212 + 1 21' ! 12. Выполним все требуем1.ю по формуле операции в троичной системе счисления: Х = 11 110201 < 10 1211 ! ! 21 ~ 12 = 1212211 4 12110 4 21 ~ 12 = 2002201. Итак, Х = (4315)1 — — (2002201)з.

151 1!ерсвод Р†> 1,1. Пусть известно изображение целого числа Х в системе счисления с основанием Р и требуется перевести это число в систему счисления с основанием Я~. Запись этого числа в 0-инной системе счисления будет иметь вид гдс. ц, (г = О, 1,..., а) - цифры Я-ичной системы счисления, которые надо определить. Для определения де разделим обе части равенства Х = >1, Я' 1 >1, > Я' > 4 -1 ® Я~ ! >!» на число с,>, причем в левой части равенства произведем фактическое деление, поскольку запись числа Х в системе счисления с основанием Р нам известна, а в правой части деление выполним аналитически: Приравняем между собой полученные целые и дрооные части, учитывая при этом, что гй<0: целая часть ( †;.,) = д, О' ' 4 >1,.

> Я' ~ ~ ~ и>,' дробная часть (х) = Ж. Отсюда получим, что младший коэффициент да в разложении (!) определяется соотно!ленись> я>> = Я~ ' дробная час'Гь (~>), причем указанные здесь действия на, самом деле не выполняются, так как па является просто с>статком от деления Х на Я. 11оложим далее Х> = це~а~ >асть (~), т.е. Тогда Л > будет целым числом, и чтобы определить следующую искомую цифру с>>, к нему можно применить ту же самую процедуру и т.д. Этот процесс следует продолжать до тех пор,пока не будет гюлучено частное, равное нулю. Заметим,что поскольку все операции выполняются в системе счисления с основанием Р, то в этой же системе счисления будут получены и искомые коэффициенты щ. Для окончательной записи числа Х в б~-ичной системе счисления необходимо каждый из полученных коэффициентов г» записать одной Я-ичной> цифрой.

Например, пусть требуется перевести число Х = 3060 в шестнадцатиричную систему счисления с использованием десятичной арифметики. 1!римспим только что обсужденное правило: 3060 ! 16 16 191 ( 16 146 16 11( 16 144 31 0 0 20 16 11 16 15 4 Таким образом, да — — (4)ю, >1> = (15)ю, дз — — (11)ю.,>>,ля окончательной записи числа Х в шестнадцатиричной системс нужно каждый из этих коэффициентов записать одной >пестнадцатиричной цифрой: Л = (В!г4) >а. 152 1.ели основа<зие целевой системы счисления Я м<,'ныл< ос<~она«ия обьек гной С, то цифраъ<ъ< могут служить небольшие це <ые числа ана:югично гоъъу, как при «оди1>ова«ии ооль<пего алфавита в меньший мы использовали составные знаки-слова, Паскаль-программы интерпретации изображений вводимых и выводимых целых чисел приведены в и.

13 пособия Н. Вирта [8[ и в и. 3.2.11. Изу п.нные нами алгоритмы работы с изображениями целых пгссл могут быть полезны для реализации так называемой длинной ари<[ъъ<егпиюа. В некоторых задачах важно производить вычисления большой точности или с очень больп<иь<и чи<'.лами, нс поддерживаемые аппаратурой. Для этого используется программныс реализации работы с изображениями.