сделать конспект Глава 1 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ § 1.1 Системы счисления Ключевые слова: система счисления •цифра алфавит • позиционная система счисления основание…

Сделать конспект Глава 1 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ § 1.1 Системы счисления Ключевые слова: система счисления •цифра алфавит • позиционная система счисления основание развёрнутая форма записи числа • свёрнутая форма записи числа • двоичная система счисления •восьмеричная система счисления • шестнадцатеричная система счисления 1.1.1. Общие сведения о системах счисления Система счисления - это знаковая система, в которой приняты определённые правила записи чисел. Знаки, с помощью которых записываются числа (рис. 1.1), называются цифрами, а их совокупность - алфавитом системы счисления. В любой системе счисления цифры служат для обозначения чисел, называемых узловыми; остальные числа (алгоритмические) получаются в результате каких-либо операций из узловых чисел. Пример 1. У вавилонян узловыми являлись числа 1, 10, 60; в римской системе счисления узловые числа - это 1, 5, 10, 50, 100, 500 и 1000, обозначаемые соответственно I, V, X, L, C, D, M. 5 Глава 1. Математические основы информатики A 0 1 2 3 4 5 6 7 8 9 I X V ABCDEF Рис. 1.1. Знаки, используемые для записи чисел в различных системах счисления Системы счисления различаются выбором узловых чисел и способами образования алгоритмических чисел. Можно выделить следующие виды систем счисления: 1) унарная система; 2) непозиционные системы; 3) позиционные системы. Простейшая и самая древняя система - так называемая унарная система счисления. В ней для записи любых чисел используется всего один символ -- палочка, узелок, зарубка, камушек. Длина записи числа при таком кодировании прямо связана с его величиной, что роднит этот способ с геометрическим представлением чисел в виде отрезков. Именно унарная система лежит в фундаменте арифметики, и именно она до сих пор вводит первоклассников в мир счёта. Унарную систему ещё называют системой бирок. Система счисления называется непозиционной, если количественный эквивалент (количественное значение) цифры в числе не зависит от её положения в записи числа. В большинстве непозиционных систем счисления числа образуются путём сложения узловых чисел. Пример 2. В древнеегипетской системе счисления числа 1, 2, 3, 4, 10, 13, 40 обозначались соответственно следующим образом: Те же числа в римской системе счисления обозначаются так: I, II, III, IV, X, XIII, XL. Здесь алгоритмические числа получаются путём сложения и вычитания узловых чисел с учётом следующего правила: каждый меньший знак, поставленный справа от большего, прибавляется к его значению, а каждый меньший знак, поставленный слева от большего, вычитается из него. 6 Системы счисления 1.1 Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (позиции) в записи числа. Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит. Десятичная система записи чисел, которой мы привыкли пользоваться в повседневной жизни, с которой мы знакомы с детства, в которой производим все наши вычисления, - пример позиционной системы счисления. Алфавит десятичной системы составляют цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Алгоритмические числа образуются в ней следующим образом: значения цифр умножаются на «веса» соответствующих разрядов, и все полученные значения складываются. Это отчётливо прослеживается в числительных русского языка, например: «три-ста пять-десят семь». Основанием позиционной системы счисления может служить любое натуральное число q > 1. Алфавитом произвольной позиционной системы счисления с основанием q служат числа 0, 1, …, q-1, каждое из которых может быть записано с помощью одного уникального символа; младшей цифрой всегда является 0. Основные достоинства любой позиционной системы счисления - простота выполнения арифметических операций и ограниченное количество символов, необходимых для записи любых чисел. В позиционной системе счисления с основанием q любое число может быть представлено в виде: An=+(an-1q+an-2q" *+ … +aoq + a-1q+ … +amq"). (1) Здесь: A - число; q - основание системы счисления; a, - цифры, принадлежащие алфавиту данной системы счисления; n - количество целых разрядов числа; m - количество дробных разрядов числа; q' - «вес» і-го разряда. Запись числа по формуле (1) называется развёрнутой формой записи. Свёрнутой формой записи числа называется его представление в виде ±an-1an-2…a1a0,a-1…a-m- 1 Далее будут рассматриваться только положительные целые числа. Глава 1. Математические основы информатики Пример 3. Рассмотрим десятичное число 14351,1. Его свёрнутая форма записи настолько привычна, что мы не замечаем, как в уме переходим к развёрнутой записи, умножая цифры числа на «веса» разрядов и складывая полученные произведения: 1 • 104 + 4 • 103 + 3 102 + 5 • 101 + 1 100 + 1 • 10-1. 1.1.2. Двоичная система счисления Двоичной системой счисления называется позиционная система счисления с основанием 2. Для записи чисел в двоичной системе счисления используются только две цифры: 0 и-1. На основании формулы (1) для целых двоичных чисел можно записать: an ja, 2…aja = a, 2n-1 + a, 2 2n-2+ … + a, 2°. (1') Например: 10011, = 1 24 + 0 • 23 + 0 22 + 1 - 21 + 1 - 20 = 24 + 21 + 20 = 1910- Такая форма записи «подсказывает» правило перевода натуральных двоичных чисел в десятичную систему счисления: необходимо вычислить сумму степеней двойки, соответствующих единицам в свёрнутой форме записи двоичного числа. Получим правило перевода целых десятичных чисел в двоичную систему счисления из формулы (1'). Разделим а, 1 • 2"-1 + 2 2n-2 + … + • 2° на 2. Частное будет равно а1 • 2n-2 + … + a1, а остаток будет равен а Полученное частное опять разделим на 2, остаток от деления будет равен а1- Если продолжить этот процесс деления, то на п-м шаге получим набор цифр: ag, a1, a2, …, an-1, которые входят в двоичное представление исходного числа и совпадают с остатками при его последовательном делении на 2. Таким образом, для перевода целого десятичного числа в двоичную систему счисления нужно последовательно выполнять деление данного числа и получаемых целых частных на 2 до тех пор, пока не получим частное, равное нулю. Исходное число в двоичной системе счисления составляется последовательной записью полученных остатков, начиная с последнего. Системы счисления Пример 4. Переведём десятичное число 11 в двоичную систему счисления. Рассмотренную выше последовательность действий (алгоритм перевода) можно изобразить так: 11| 2 10 5 2 1 - oln Выписывая остатки от деления в направлении, указанном стрелкой, получим: 1110 = 10112. Пример 5. Если десятичное число достаточно большое, то более удобен следующий способ записи рассмотренного выше алгоритма: 363 181 90 45 22 11 5 2 1 O 1 1 1 1 O 36310 = 1011010112 1.1.3. Восьмеричная система счисления Восьмеричной системой счисления называется позиционная система счисления с основанием 8. Для записи чисел в восьмеричной системе счисления используются цифры: 0, 1, 2, 3, 4, 5, 6, 7. На основании формулы (1) для целого восьмеричного числа можно записать: a,ja, 2…a,a - a, 18"-1 + a, 28"-2 + … + a, 8°. (1") Например: 10634 = 1 83 + 0 82 + 6 81 + 3 80 = 56310 Таким образом, для перевода целого восьмеричного числа в десятичную систему счисления следует перейти к его развёрнутой записи и вычислить значение получившегося выражения. Для перевода целого десятичного числа в восьмеричную систему счисления следует последовательно выполнять деление данного числа и получаемых целых частных на 8 до тех пор, пока не получим частное, равное нулю. Исходное число в новой системе счисления составляется последовательной записью полученных остатков, начиная с последнего. Глава 1. Математические основы информатики Пример 6. Переведём десятичное число 103 в восьмеричную систему счисления. 103 | 8 - 8 12 8 23 l 10310 = 147g 1.1.4. Шестнадцатеричная система счисления Основание: q = 16. Алфавит 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, B, C, D, E, F. Здесь только десять цифр из шестнадцати имеют общепринятое обозначение 0,…, 9. Для записи цифр с десятичными количественными эквивалентами 10, 11, 12, 13, 14, 15 обычно используются первые пять букв латинского алфавита. Таким образом, запись ЗАF16 означает: 3AF16 = 3 • 162 + 10 • 161 + 15 • 160 = 768 + 160 + 15 = 94310- Пример 7. Переведём десятичное число 154 в шестнадцатерич- ную систему счисления. 154 | 16 144 loo 10 (A) 15410 = 9A16 1.1.5. Правило перевода целых десятичных чисел в систему счисления с основанием q Для перевода целого десятичного числа в систему счисления с основанием q следует: 1) последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, равное нулю; 2) полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления; 10 Системы счисления 1 3) составить число в новой системе счисления, записывая его, начиная с последнего полученного остатка. Представим таблицу соответствия десятичных, двоичных, вось- меричных и шестнадцатеричных чисел от 0 до 2010• Десятичная система Двоичная система Восьмеричная система Шестнадцатеричная система O O O O 1 1 1 1 2 10 2 2 3 11 3 3 4 100 4 4 5 101 5 5 6 110 6 6 7 111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 13 1101 15 D 14 1110 16 E 15 1111 17 F 16 10000 20 10 17 10001 21 11 18 10010 22 12 19 10011 23 13 20 10100 24 14 11 Глава 1. Математические основы информатики B Единой коллекции цифровых образовательных ресурсов ( http://sc.edu.ru/ ) размещена интерактивная анимация «Преобразование десятичного числа в другую систему счисления» (135050). С её помощью можно понаблюдать за переводом произвольного целого числа от 0 до 512 в позиционную систему счисления, основание которой не превышает 16. В размещённой там же виртуальной лаборатории «Цифровые весы» (135009) вы сможете освоить ещё один способ перевода целых десятичных чисел в другие системы счисления -- метод разностей. 1.1.6. Двоичная арифметика Арифметика двоичной системы счисления основывается на использовании следующих таблиц сложения и умножения: + O 1 × O 1 1 10 1 Пример 8. Таблица двоичного сложения предельно проста. Так как 1 + 1 = 10, то 0 остаётся в младшем разряде, а 1 переносится в старший разряд. Пример 9. Операция умножения двоичных чисел выполняется по обычной схеме, применяемой в десятичной системе счисления, с последовательным умножением множимого на очередную цифру множителя. 1 O Таким образом, в двоичной системе счисления умножение сводится к сдвигам множимого и сложениям. Системы счисления1 1.1.7. «Компьютерные» системы счисления В компьютерной технике используется двоичная система счисления, обеспечивающая ряд преимуществ по сравнению с другими системами счисления: •двоичные числа представляются в компьютере с помощью достаточно простых технических элементов с двумя устойчивыми состояниями; • представление информации посредством только двух состояний надёжно и помехоустойчиво; • двоичная арифметика наиболее проста; • существует математический аппарат, обеспечивающий логические преобразования двоичных данных. Обмен информацией между компьютерными устройствами осуществляется путём передачи двоичных кодов. Пользоваться такими кодами из-за их большой длины и зрительной однородности человеку неудобно. Поэтому специалисты (программисты, инженеры) на некоторых этапах разработки, создания, настройки вычислительных систем заменяют двоичные коды на эквивалентные им величины в восьмеричной или шестнадцатеричной системах счисления. В результате длина исходного слова сокращается в три, четыре раза соответственно. Это делает информацию более удобной для рассмотрения и анализа. С помощью ресурса «Интерактивный задачник, раздел "Системы счисления"» (128659), размещённого в Единой коллекции цифровых образовательных ресурсов, можно проверить, насколько прочно вы усвоили изученный в этом параграфе материал. 7 www САМОЕ ГЛАВНОЕ Система счисления - это знаковая система, в которой приняты определённые правила записи чисел. Знаки, с помощью которых записываются числа, называются цифрами, а их совокупность - алфавитом системы счисления. Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (позиции) в записи числа. Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит. Основанием позиционной системы счисления может служить любое натуральное число q > 1. 13 Глава 1. Математические основы информатики В позиционной системе счисления с основанием q любое число может быть представлено в виде: A = (an-1 • q" + an-2• q" + … + ao q + a 1 • q + … + a m q"). Здесь: A - число; q - основание системы счисления; a, - цифры, принадлежащие алфавиту данной системы счисления; n - количество целых разрядов числа; m - количество дробных разрядов числа; g - «вес» і-го разряда.