Раздел 1_РЕД_2. I. основы теории множеств. Системы счисления комбинаторика
 Скачать 9.96 Mb.
|
|
Глава 4. СИСТЕМЫ СЧИСЛЕНИЯ Дискретное (цифровое) представление количественной информации позволило значительно повысить качество выполняемых операций на всех этапах ее обработки - при записи, преобразовании, передаче и хранении. Для символьного представления количественной информации применяют особые линейные записи, которые называют числами. В записи чисел применяют специальные символы, называемые цифрами. Системой счисления называют набор правил для записи величин в форме чисел, а также для выполнения действий с числами, представленными в данной форме. Применяемая система счисления зависит от вида решаемых задач и используемых для этого вычислительных средств. Для компьютеров в настоящее время общепринятым стандартом является двоичная система представления чисел, когда элементарная единица памяти (бит) может принимать только два возможных состояния, обычно кодируемые нулем и единицей. Это соответствует двум возможным физическим состояниям элементарных ячеек электронной памяти. Однако в течение нескольких десятилетий исследуются возможности и других систем счисления. Двоичную информацию в памяти ЭВМ интерпретируют системой счисления с основанием 16 (шестнадцатеричной), что связано с байтовой адресацией памяти, принятой в современных компьютерах и алгоритмических языках. Позиционныминазывают системы счисления, в которых числа представляют в виде линейного набора цифр, стоящих в строго определенных пронумерованных местах – разрядах. При этом вклад каждой цифры в общее значение числа зависит как от ее величины, так и от номера разряда, в котором она находится. Общее правило нумерации разрядов следующее. В целых частях чисел нумерация разрядов возрастает справа налево, начиная с 0. В дробных частях – убывает, начиная от запятой, слева направо, с номера разряда (–1). В наиболее распространенной позиционной системе счисления, называемой десятичной, 10 единиц младшего разряда составляют одну единицу следующего – старшего. Отношение единицы старшего разряда к единице младшего (p), равное 10, называют основанием системы. Если величина данного отношения постоянна для всех соседних разрядов, то такую систему называют системой с постоянным основанием. Иначе систему называют смешанной, например, при счислении времени “сутки – часы – минуты – секунды”. 4.1. Позиционные системы счисления с постоянными основаниями. Представления целых чисел Рассмотрим общие правила представления количественных величин в позиционных системах счисления.Величина основания p равна количеству цифр, которые могут быть использованы в данной системе для записи числа в его разрядах. При необходимости ее указывают в конце записи числа в нижнем индексе. Множество цифр, используемых для записи чисел, называют алфавитом позиционной системы счисления. Поскольку десятичную систему исчисления европейцы позаимствовали в средние века у арабов, то ее алфавит – множество цифр {0; 1; 2; 3; 4; 5; 6; 7; 8; 9} – называют арабскими цифрами. В основе десятичной системы лежит счет на пальцах. По принятому в математике соглашению для позиционных систем с основанием p при p < 10 алфавитом являются начальные арабские цифры от 0 до (p –1). Например, в системе с основанием 8 алфавитом является множество {0; 1; 2; 3; 4; 5; 6; 7}. Если же p > 10, то к арабским цифрам добавляют необходимое число начальных букв латинского алфавита. Так, в системе с p = 12 алфавитом будет множество {0; 1; 2; 3; 4; 5; 6; 7; 8; 9; A; B}. Из систем с основаниями p > 10 наиболее употребительной является шестнадцатеричная. В ней для записи значений цифр в разрядах используются целые величины от 0 до (p – 1) = 15. Старшие значения шестнадцатеричных цифр {10, 11, 12, 13, 14, 15}, которым нет аналогов в арабских цифрах, кодируются по общему правилу, соответственно, шестью первыми начальными буквами латинского алфавита {A, B, C, D, E, F} – обычно допускается равноправное использование как больших, так и малых букв. Для целых чисел в позиционной системе с основанием p вес (стоимость) одной единицы, помещенной в разряд с номером k, равна pk. Запись вида Ap = k...210 в системе с основанием p означает число, равное сумме A = kpk + ... + 2p2 + 1p1 + 0p0. Данное выражение называют развернутой формой представления целых чисел в позиционной системе счисления. Пример 1. Запись вида А10 =29510 в десятичной системе (p = 10), означает целое число, равное A = 2102+9101+5100. Для компьютеров в настоящее время стандартом является двоичная система представления чисел (p = 21), в которой элементарная единица памяти (бит) может принимать только два возможных состояния, обычно кодируемые нулем и единицей. В непозиционных системах счисления значение цифры в записи числа не зависит от номера разряда, в котором она находится. Например, в непозиционной римской системе счисления в качестве цифр использованы буквы латинского алфавита. Приведем их обозначения и величины в десятичной системе: I=1; V=5; X=10; L=50; C=100; D=500. Расшифровка записи чисел в римской системе производится следующим образом. При расположении цифр по невозрастанию слева направо общее число равно сумме всех своих цифр в записи. Если же меньшее число в ней стоит левее большего, то меньшее входит в общую сумму со знаком минус. Пример 2. CХХVII=100+10+10+5+1+1=127; CХLIV=100–10+50–1+5=144. Поскольку сегодня наиболее привычной является десятичная система счисления, то для оценки величин чисел их представляют в данной системе. 4.2. Переводы целых чисел в позиционных системах счисления С помощью позиционных систем с постоянными основаниями можно представить точно либо приближенно (с любой заданной точностью) любое вещественное число. Из позиционных систем счисления проще всего двоичная, с основанием 2, где числа записываются с помощью символов из множества Е2={0, 1}. Единица старшего разряда равна двум единицам предшествующего. Для записи числа в этой системе его разлагают по степеням основания 2. Например, для числа 12510 = 126 + 125 +124+ 123 + 122 + 120 = 64 + 32 + 16 + 8 + 4 + 1. Т. е. двоичная запись числа 12510 имеет вид: 11111012. В силу своей простоты двоичная система нашла широкое применение в различного рода вычислительных и управляющих устройствах, так как для ее физической реализации достаточно обеспечить только два состояния логических элементов: «да — нет», «включено — выключено» и т. д. Двоичная система также служит модельной при исследовании структурных свойств множеств и логических объектов. 4.2.1. Перевод целых чисел из произвольной системы с постоянным основанием р 10 в десятичную систему Для выполнения данного преобразования применяют развернутую форму представления целых двоичных чисел, т.е. искомое десятичное число представляют в виде суммы цифр числа, умноженных на степени основания p, равные номеру соответствующего разряда. После расчета слагаемых и их суммирования получается искомая десятичная запись числа. Пример 1. Переведем в десятичную систему двоичное число 11010012. Решение. Последовательно записываем разложение числа по степеням основания 2 (развернутая форма представления), выражаем полученные степени в десятичной системе и суммируем: 11010012 = 126 + 125 + 123 + 120 = 6410 + 3210 + 810 + 110 = 10510. Пример 2. Перевести в десятичную систему счисления число, представленное в шестнадцатеричной системе счисления как 8DВ416. Решение. Записываем развернутую форму представления числа по степеням 16, выражаем полученные степени в десятичной системе счисления и суммируем: 8DВ416 = 8163 + D162 + B161 + 4160 = 84096 + 13256 + 1116 + 4 = 3276810 + 332810 + 17610 + 410 = 3627610. |