Скачать 1.34 Mb.
|
имя переменной := выражение; При его выполнении сначала вычисляется значение выражения справа от знака присваивания :=, затем оно записывается в переменную. Выражение в правой части может включать имя переменной в левой части. В этом случае при вычислении выражения используется старое значение переменной. Типы переменных Тип переменной определяется множеством значений, которое она может принимать. Кроме того, тип определяет операции, которые возможны с переменной. Например, с численными переменными возможны арифметические операции, с логическими - проверка, истинно или ложно значение переменной, с символьными - сравнение, с табличными (или массивами) - чтение или запись элемента таблицы с заданным индексом и т.п. Как правило, в любом современном языке имеется базовый набор типов и несколько конструкций, которые позволяют строить новые типы из уже созданных. Наборы базовых типов и конструкций различаются для разных языков. В описании неформального алгоритмического языка будут использоваться типы и конструкции, которые присутствуют в большинстве языков практического программирования. Целочисленные переменные Тип целое число является основным для любого алгоритмического языка. Связано это с тем, что содержимое ячейки памяти или регистра процессора можно рассматривать как целое число. Адреса элементов памяти также представляют собой целые числа, с их помощью записываются машинные команды и т.д. Символы представляются в компьютере целыми числами - их кодами в некоторой кодировке. Изображения также задаются массивами целых чисел: для каждой точки цветного изображения хранятся интенсивности ее красной, зеленой и синей составляющей (в большинстве случаев - в диапазоне от 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, ...} Элементами кольца 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, а при четном 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. В двоичном представлении старший разряд у отрицательных целых чисел равен единице, у положительных - нулю. Двоичные разряды представления целого числа в программировании нумеруют от 0 до 31 справа налево. Старший разряд имеет номер 31 и часто называется знаковым разрядом. Таким образом, знаковый разряд равен единице у всех отрицательных чисел и нулю у неотрицательных. Двоичное представление максимального по абсолютной величине отрицательного числа k состоит из единицы и тридцати одного нуля: -214748364810 = 100000000000000000000000000000002 Двоичное представление числа -1 состоит из тридцати двух единиц: -110 = 111111111111111111111111111111112 Двоичное представление максимального положительного числа состоит из нуля в знаковом разряде и тридцати одной единицы: 214748364710 = 011111111111111111111111111111112 Следует отметить, что в программировании часто используют также короткие целые числа, двоичная запись которых занимает восемь разрядов, т.е. один байт, или шестнадцать разрядов, т.е. два байта. Работа с такими короткими целыми числами поддерживается на аппаратном уровне. В языке Си однобайтовым целым числам соответствует тип char (тип char в Си - это именно целые числа, символы представляются их целочисленными кодами), двухбайтовым - тип short. Однобайтовые целые числа - это элементы кольца вычетов Zm, где m = 28 = 256. Симметричная система остатков в этом случае состоит из элементов -128, -127, ..., -2, -1, 0, 1, 2, ..., 127. В случае двухбайтовых целых чисел (тип short) m = 216 = 65536, а симметричная система остатков состоит из элементов -32768, -32767, ..., -2, -1, 0, 1, 2, ..., 32767. Вещественные переменные Вещественные числа представляются в компьютере в так называемой экспоненциальной, или плавающей, форме. Вещественное число r имеет вид r = ±2e* m Представление числа состоит из трех элементов: знак числа - плюс или минус. Под знак числа отводится один бит в двоичном представлении, он располагается в старшем, т.е. знаковом разряде. Единица соответствует знаку минус, т.е. отрицательному числу, ноль - знаку плюс. У нуля знаковый разряд также нулевой; показатель степени e, его называют порядком или экспонентой. Экспонента указывает степень двойки, на которую домножается число. Экспонента может быть как положительной, так и отрицательной (для чисел, меньших единицы). Под экспоненту отводится фиксированное число двоичных разрядов, обычно восемь или одиннадцать, расположенных в старшей части двоичного представления числа, сразу вслед за знаковым разрядом; мантисса m представляет собой фиксированное количество разрядов двоичной записи вещественного числа в диапазоне от 1 до 2: 1 m<2 Следует подчеркнуть, что левое неравенство нестрогое - мантисса может равняться единице, а правое - строгое, мантисса всегда меньше двух. Разряды мантиссы включают один разряд целой части, который ввиду приведенного неравенства всегда равен единице, и фиксированное количество разрядов дробной части. Поскольку старший двоичный разряд мантиссы всегда равен единице, хранить его необязательно, и в двоичном коде он отсутствует. Фактически двоичный код хранит только разряды дробной части мантиссы. В языке Си вещественным числам соответствуют типы float и double. Элемент типа float занимает 4 байта, в которых один бит отводится под знак, восемь - под порядок, остальные 23 - под мантиссу (на самом деле, в мантиссе 24 разряда, но старший разряд всегда равен единице, поэтому хранить его не нужно). Тип double занимает 8 байтов, в них один разряд отводится под знак, 11 - под порядок, остальные 52 - под мантиссу. На самом деле в мантиссе 53 разряда, но старший всегда равен единице и поэтому не хранится. Поскольку порядок может быть положительным и отрицательным, в двоичном коде он хранится в смещенном виде: к нему прибавляется константа, равная абсолютной величине максимального по модулю отрицательного порядка. В случае типа float она равна 127, в случае double - 1023. Таким образом, максимальный по модулю отрицательный порядок представляется нулевым кодом. Основным типом является тип double, именно он наиболее естественен для компьютера. В программировании следует по возможности избегать типа float, так как его точность недостаточна, а процессор все равно при выполнении операций преобразует его в тип double. (Один из немногих случаев, где применение типа float оправдано, - трехмерная компьютерная графика.) Несколько примеров представления вещественных чисел в плавающей форме: 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. При выполнении сложения двух положительных плавающих чисел происходят следующие действия: выравнивание порядков. Определяется число с меньшим порядком. Затем последовательно его порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел не сравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссы вправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются, из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые); сложение мантисс; нормализация: если мантисса результата стала равна или превысила двойку, то порядок увеличивается на единицу, а мантисса делится на 2. В результате этого мантисса попадает в интервал 1 m<2. При этом возможна потеря точности, а также переполнение, когда порядок превышает максимально возможную величину. Вычитание производится аналогичным образом. При умножении порядки складываются, а мантиссы перемножаются как целые числа, после чего у результата правые разряды отбрасываются. Машинный эпсилон Действия с плавающими числами из-за ошибок округления лишь приближенно отражают арифметику настоящих вещественных чисел. Так, если к большому плавающему числу прибавить очень маленькое, то оно не изменится. Действительно, при выравнивании порядков все значащие биты мантиссы меньшего числа могут выйти за пределы разрядной сетки, в результате чего оно станет равным нулю. Таким образом, с плавающими числами возможна ситуация, когда 2> |
Загирова Румия Ахатовна Дата рождения: 10. 07. 1960 Образование: высшее Учебное заведение После окончания школы, мы остались работать в родном совхозе «Ямбухтинский». Затем, по велению райкома партии, я поступила на экономический... | Готов ответить на все Ваши вопросы… Заельцовском районе города Новосибирска. Вырос в неполной необеспеченной семье. После 8-го класса школы №159 поступил в Новосибирский... | ||
Реферат Студент 2-го курса(гр. 28) Брюсселе, Вене и Будапеште. После поражения Германии он участвует в подписании капитуляции в качестве эксперта, принимает участие... | Продукция оксида азота мононуклеарами крови у больных лекарственно-чувствительным... У больных лекарственно-устойчивым тл до и после проведения курса интенсивного лечения секреция no• моноцитами крови снижалась и увеличивалась... | ||
Или, что такое эссе и как его написать? Все просто: получено задание от преподавателя как результат окончания очередного полугодия или семестра, как результат окончания... | Конспект Конспект краткое изложение или краткая запись содержания В помощь подготовке старшеклассников к самообразовательной работе после окончания школы | ||
Элективный курс «Устройство автомобиля» Многие учащиеся собираются после окончания 9-го класса получать среднее профессиональное или среднее специальное образование на базе... | Программа элективного курса «Великие россияне» пояснительная записка ... | ||
Весной после окончания учебного года педагоги, управляющий совет... Весной после окончания учебного года педагоги, управляющий совет Горячевской средней школы, возглавляемый Т. Г. Осиповой, представители... | Конспект воспитательного мероприятия * В помощь подготовке старшеклассников к самообразовательной работе после окончания школы | ||
Тематическое планирование по английскому языку для 11 класс Какими качествами надо обладать, чтобы найти достойную работу после окончания школы? | Протокол №1 от 31. 08. 2012 г «Русский язык и литература» на филологических факультетах педагогических университетов проводится диалектологическая практика. Она... | ||
Конспект непосредственно образовательной деятельности В помощь подготовке старшеклассников к самообразовательной работе после окончания школы | Отчет по педагогической практике в трехдневный срок после окончания... ... | ||
Хотеенкова Лариса Давыдовна «Русский язык и литература» на филологических факультетах педагогических университетов проводится диалектологическая практика. Она... | «Утверждаю» Директор школы Индивидуальные беседы с учащимися 7-9 классов о продолжении обучения после окончания моу всош №1 |