СКИПОДы 2007 полная версия (1127795), страница 55
Текст из файла (страница 55)
Операция взятия целой части числа x (функция Антье - [x] или int(x)) операция усечения, [2.65]=2, [—1.999]=—2. Операция взятия целой части числа x+0.5вместо значения числа х есть округление {x} до ближайшего целого, {1.05}={0.91}=1,{2.61}=[2.6+0.5]=3.ДополнениеЦелочисленные переменныеТип целое число является основным для любого алгоритмического языка. Связано это стем, что содержимое ячейки памяти или регистра процессора можно рассматривать какцелое число.
Адреса элементов памяти также представляют собой целые числа, с ихпомощью записываются машинные команды и т.д. Символы представляются в компьютерецелыми числами - их кодами в некоторой кодировке. Изображения также задаютсямассивами целых чисел: для каждой точки цветного изображения хранятся интенсивностиее красной, зеленой и синей составляющей (в большинстве случаев - в диапазоне от 0 до255). Как говорят математики, целые числа даны свыше, все остальное сконструировал изних человек.Общепринятый в программировании термин целое число или целочисленная переменная,строго говоря, не вполне корректен.
Целых чисел бесконечно много, десятичная илидвоичная запись целого числа может быть сколь угодно длинной и не помещаться в областипамяти, отведенной под одну переменную. Целая переменная в компьютере может хранитьлишь ограниченное множество целых чисел в некотором интервале. В современныхкомпьютерах под целую переменную отводится 4 байта, т.е. 32 двоичных разряда. Онаможет хранить числа от нуля до 2 в 32-й степени минус 1. Таким образом, максимальноецелое число, которое может храниться в целочисленной переменной, равно232 - 1 = 4294967295Сложение и умножение значений целых переменных выполняется следующим образом:сначала производится арифметическая операция, затем старшие разряды результата,вышедшие за границу тридцати двух двоичных разрядов (т.е.
четырех байтов),отбрасываются. Определенные таким образом операции удовлетворяют традиционнымзаконам коммутативности, ассоциативности и дистрибутивности:a+b = b+a, ab = ba(a+b) + c = a+(b+c), (ab)c = a(bc)a(b+c) = ab+acКольцо вычетов по модулю mЦелочисленный тип компьютера в точности соответствует важнейшему понятиюматематики - понятию кольца вычетов по модулю m. В качестве m выступает число 232 =4294967296.
В математике кольцо Zm определяется следующим образом. Все множествоцелых чисел Z разбивается на m классов, которые называются классами эквивалентности.Каждый класс содержит числа, попарная разность которых делится на m. Первый класссодержит числа{...,-2m,-m,0,m,2m, ...}второй{..., -2m+1, -m+1, 1, m+1, 2m+1, ...}последний{..., -m-1, -1, m-1, 2m-1, 3m-1, ...}185Элементами кольца Zm являются классы эквивалентности. Их ровно m, так что, в отличиеот множества целых чисел Z, кольцо Zm содержит конечное число элементов. Операции склассами выполняются следующим образом: надо взять по одному представителю изкаждого класса, произвести операцию и определить, в какой класс попадает результат.
Этоткласс и будет результатом операции. Легко показать, что он не зависит от выборапредставителей.Все числа, принадлежащие одному классу эквивалентности, имеют один и тот же остатокпри делении на m. Таким образом, класс эквивалентности однозначно определяетсяостатком от деления на m. Традиционно остаток выбирается неотрицательным, в диапазонеот 0 до m -1. Остатки используют для обозначения классов, при этом используютсяквадратные скобки. Так, выражение [5] обозначает класс эквивалентности, состоящий извсех чисел, остатки которых при делении на m равны пяти. Все кольцо Zm состоит изэлементов [0],[1],[2], ...,[m-1], например, кольцо Z5 состоит из элементов [0],[1],[2],[3],[4].В элементарной школьной математике результат операции остатка от деления традиционносчитается неотрицательным.
Операция нахождения остатка будет обозначаться знакомпроцента %, как в языке Си. Тогда, к примеру,3%5 = 3,17%5 = 2,(-3)%5 = 2,(-17)%5 = 3.Отсюда видно, что в школьной математике не выполняется равенство (-a)%b = -(a%b),т.е. операции изменения знака и нахождения остатка не перестановочны (наматематическом языке, не коммутируют друг с другом). В компьютере операциянахождения остатка от деления для отрицательных чисел определяется иначе, ее результатможет быть отрицательным. В приведенных примерах результаты будут следующими:3%5 = 3,17%5 = 2,(-3)%5 = -3,(-17)%5 = -2.При делении на положительное число знак остатка совпадает со знаком делимого. Притаком определении тождество (-a)%b = a%(-b) = -(a%b) справедливо. Это позволяет вомногих алгоритмах не следить за знаками (так же, как в тригонометрии формулы,выведенные для углов, меньших 90 градусов, автоматически оказываются справедливымидля любых углов).Вернемся к рассмотрению кольца Zm.
Выберем по одному представителю из каждогокласса эквивалентности, которые составляют множество Zm. Систему таких представителейназывают системой остатков. Традиционно рассматривают две системы остатков:неотрицательную систему и симметричную систему. Неотрицательная система остатковсостоит из элементов0,1,2,3, ...m-1.Очень удобна также симметричная система остатков, состоящая из отрицательных инеотрицательных чисел, не превосходящих m/2 по абсолютной величине. Пустьk = целая часть(m/2)тогда симметричная система остатков при нечетном m состоит из элементов-k, -k+1, ..., -1, 0, 1, ..., k-1, k,186а при четном m - из элементов-k, -k+1, ..., -1, 0, 1, ..., k-1.Например, при m = 5 симметричная система остатков состоит из элементов-2, -1, 0, 1, 2.Кольцо Zm можно представлять состоящим из элементов, принадлежащих выбраннойсистеме остатков.
Арифметические операции определяются следующим образом: надовзять два остатка, произвести над ними операцию как над обычными целыми числами ивыбрать тот остаток, которой лежит в том же классе эквивалентности, что и результатоперации. Например, для симметричной системы остатков множества Z5 имеем:1+1 = 2,1+2 = -2,1+(-2) = -1, 1+(-1) = 0,(-2)+2 = 0, (-2)+(-2) = 1.Интерпретация положительных и отрицательных чиселВ кольце вычетов невозможно определить порядок, согласованный с операциями (т.е. так,чтобы, к примеру, сумма двух положительных чисел была положительной).
Таким образом,в компьютере нет, строго говоря, положительных и отрицательных целых чисел, посколькукомпьютерные целые числа - это на самом деле элементы кольца вычетов. Выбирая либонеотрицательную, либо симметричную систему остатков, можно интерпретировать этичисла либо как неотрицательные в диапазоне от нуля до m-1, либо как отрицательные иположительные числа в диапазоне от -k до k, где k - целая часть от деления m на 2.В программировании симметричная система остатков более популярна, поскольку труднообойтись без отрицательных чисел. При этом следует понимать, что сумма двухположительных чисел может оказаться отрицательной, или, наоборот, сумма двухотрицательных чисел - положительной.
Иногда в программировании такую ситуациюназывают переполнением. Привычные свойства целочисленных операций в компьютеревыполняются лишь для небольших чисел, когда результат операции не превосходит числаm = 232. В случае целочисленных переменных переполнение не является экстраординарнойситуацией и не приводит к аппаратным ошибкам или прерываниям. (Это, кстати, отличаеткомпьютерные целые числа от вещественных.) Переполнение - совершенно нормальнаяситуация, если вспомнить, что компьютер работает с элементами кольца вычетов помодулю m, а не с настоящими целыми числами.Следует также отметить, что симметричная система остатков кольца Zm в случае четного m(а m для компьютера равно 232, т.е. четно) не вполне симметрична. Поскольку ноль неимеет знака, то число положительных остатков не может равняться числу отрицательных.Какой остаток выбрать в классе эквивалентности числа k = m/2? Для этого элементавыполняется непривычное с точки зрения школьной математики равенствоk+k 0 (mod m), т.е.
k -k (mod m)Как отрицательный остаток -k, так и положительный k в равной мере подходят дляпредставления этого класса эквивалентности. По традиции выбирается отрицательныйостаток. Таким образом, в компьютере количество отрицательных целых чисел на единицубольше, чем количество положительных. Так как m = 232 = 4294967296, то k = 231 =2147483648, и симметричная система остатков состоит из элементов-2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647.Вещественные переменные187Вещественные числа представляются в компьютере в так называемой экспоненциальной,или плавающей, форме. Вещественное число r имеет видr = ±2e* mПредставление числа состоит из трех элементов:знак числа - плюс или минус. Под знак числа отводится один бит в двоичномпредставлении, он располагается в старшем, т.е.
знаковом разряде. Единица соответствуетзнаку минус, т.е. отрицательному числу, ноль - знаку плюс. У нуля знаковый разряд такженулевой;показатель степени e, его называют порядком или экспонентой. Экспонента указываетстепень двойки, на которую домножается число. Экспонента может быть какположительной, так и отрицательной (для чисел, меньших единицы).
Под экспонентуотводится фиксированное число двоичных разрядов, обычно восемь или одиннадцать,расположенных в старшей части двоичного представления числа, сразу вслед за знаковымразрядом;мантисса m представляет собой фиксированное количество разрядов двоичной записивещественного числа в диапазоне от 1 до 2:1 m<2Следует подчеркнуть, что левое неравенство нестрогое - мантисса может равнятьсяединице, а правое - строгое, мантисса всегда меньше двух. Разряды мантиссы включаютодин разряд целой части, который ввиду приведенного неравенства всегда равен единице, ификсированное количество разрядов дробной части. Поскольку старший двоичный разрядмантиссы всегда равен единице, хранить его необязательно, и в двоичном коде онотсутствует.
Фактически двоичный код хранит только разряды дробной части мантиссы.Несколько примеров представления вещественных чисел в плавающей форме:1.0 = +20*1.0Здесь порядок равен 0, мантисса - 1. В двоичном коде мантисса состоит из одних нулей, таккак старший разряд мантиссы (всегда единичный) в коде отсутствует. Порядок хранится вдвоичном коде в смещенном виде, он равен 127 в случае float и 1023 в случае double;3.5 = +21*1.75Порядок равен единице, мантисса состоит из трех единиц, из которых в двоичном кодехранятся две: 1100...0; смещенный порядок равен 128 для float и 1024 для double;0.625 = +2-1*1.25Порядок отрицательный и равен -1, дробная часть мантиссы равна 0100...0; смещенныйпорядок равен 126 для float и 1022 для double;100.0 = +26*1.5625Порядок равен шести, дробная часть мантиссы равна 100100...0; смещенный порядок равен133 для float и 1029 для double.При выполнении сложения двух положительных плавающих чисел происходят следующиедействия:выравнивание порядков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
