- •Раздел I. Основы теории множеств. Системы счисления. Комбинаторика
- •Глава 1. Множества, операции с ними. Алгебра множеств
- •1.1. Элементы и множества
- •1.2. Отображения, функции, предикаты
- •1.3. Метод математической индукции
- •1.4. Способы задания множеств
- •Перечисление
- •Задание с помощью логических функций (предикатов)
- •1.5. Предметные операции на множествах. Формула множества
- •1.6. Операции сравнения — логические операции с множествами
- •1.7. Алгебра множеств. Ее формулы, теоремы и законы
- •Глава 2. Мощность множеств
- •2.1. Мощность. Счетные множества
- •2.2. Множества мощности континуум
- •Глава 3. Бинарные отношения на множествах
- •3.1. Определение и способы задания отношений
- •3.1.1. Перечисление (список пар)
- •3.1.2. Матрица
- •3.1.3. Задание отношений при помощи предикатов
- •3.2. Аксиомы на отношениях
- •3.3. Основные типы отношений
- •3.3.1. Отношение эквивалентности
- •3.3.2. Отношение нестрогого (частичного) порядка
- •3.3.3. Отношение строгого порядка
- •3.4. Проверка типов отношений. Решение задач
- •Контрольные задания по теме
- •I. Общая теория множеств
- •Глава 4. Системы счисления
- •4.1. Позиционные системы счисления с постоянными основаниями. Представления целых чисел Рассмотрим общие правила представления количественных величин в позиционных системах счисления.
- •4.2. Переводы целых чисел в позиционных системах счисления
- •4.2.1. Перевод целых чисел из произвольной системы с постоянным основанием р 10 в десятичную систему
- •4.2.2. Перевод целых чисел из десятичной системы счисления в системы с произвольными постоянными основаниями p 10
- •4.2.5. Представление двоичной байтовой информации в шестнадцатеричной и десятичной системах
- •4.3. Дробные и смешанные числа в позиционных системах счисления с постоянными основаниями
- •4.3.1 Перевод правильных десятичных дробей в систему счисления с иным основанием p 10
- •4.3.2 Перевод правильных дробей из системы с основанием p 10 в десятичную систему счисления
- •4.4. Арифметические действия с целыми числами в системах с произвольными основаниями. Их компьютерное представление
- •4.4.1 Сложение
- •4.4.2 Вычитание
- •4.4.3. Прямой и дополнительный коды целых чисел. Их представление в памяти компьютера, сложение и вычитание
- •4.5. Двоичные (булевы) векторы
- •4.6. Смешанные позиционные системы счисления. Факториальная система
- •4.6.1. Перевод целых чисел из десятичной системы в смешанную с основаниями р0, р1, ... , рk
- •Глава 5. Комбинаторика
- •5.1. Основная задача комбинаторики. Характеристики комбинаторных задач
- •5.2. Основные правила подсчета чисел комбинаторных множеств
- •5.2.1. Правило сложения
- •5.2.2. Формула включений-исключений
- •5.2.3. Правило умножения
- •5.2.4. Правило учета сходства и различия
- •5.3. Размещения (размещения с повторениями)
- •5.4. Перестановки и размещения без повторений различных объектов. Упорядоченность перестановок
- •5.5. Перестановки и размещения без повторений групп одинаковых объектов
- •5.6. Сочетания
- •5.7. Понятие вероятности
- •Контрольные задания по теме
- •II. Системы счисления. Комбинаторика
4.3.2 Перевод правильных дробей из системы с основанием p 10 в десятичную систему счисления
Единица разряда с номером (–k) у дроби в системе счисления с основанием p = 2s в десятичной системе счисления равна десятичному числу (2)–ks = (0,5)ks. Поэтому перевод дроби, имеющей запись Ap = 0,–1 ...–k в системе счисления с основанием p = 2s, в десятичную систему счисления производят по формуле:
A10 = –1(0,5)s + ... + –k(0,5)ks.
Пример 9. Перевести в десятичную систему счисления восьмеричную дробь 0,268.
Решение. С учетом того, что 8 = 23, s = 3 получим:
А10 = 2 (0,5)3 + 6 (0,5)6 = 2 0,125 + 6 0,015625 = 0,25+ 0,09375 = 0,3437510.
Ответ:0,268 = 0,3437510.
Если основание p не равно степени 2, то перевод дроби в десятичную систему проще осуществлять по следующему общему правилу. Вначале дробную часть представляют в виде единой обыкновенной дроби m/n. Выполняя деление m на n в десятичной системе (любым способом), получаем искомую десятичную дробь. Если она конечна, то найдено точное решение задачи.
Если полученная дробь бесконечная и задана точность, с которой она должна быть определена (число k знаков после запятой), то оставляем (k + 1) знак в записи дроби, округляем ее, отбрасываем последний знак и получаем искомый ответ.
Если для бесконечной десятичной дроби требуется найти точное выражение, то по ее записи вначале определяют предпериод (постоянную часть после запятой) и период (повторяющуюся часть после предпериода). Точная запись дроби состоит из предпериода и периода, взятого в круглые скобки.
Пример 10. Найти с точностью до 6 знаков после запятой приближенное значение в десятичной системе счисления семеричной (p = 7) дроби 0,1657.
Решение. Вначале переводим заданную дробь в обыкновенную форму:
0,1657 = 1 (1 / 7) + 6 (1 / 7)2 + 5 (1 / 7)3 = 96 / 343.
Выполняя деление до седьмого знака после запятой, получим:
96 / 343 = 0,2798833… .
Округляя последний знак, получим искомую приближенную десятичную дробь:
0,2798833 0,279883.
Ответ:cточностью до6знаков после запятой0,1657 0,27988310.
Пример 11. Для шестеричной (p = 6) дроби 0,316 найти в десятичной системе счисления:
1) точное выражение,
2) приближенное значение с точностью до 5 знаков после запятой.
Решение. Вначале переводим заданную дробь в обыкновенную форму:
0,316 = 3 (1 / 6) + 1 (1 / 6)2 = 19 / 36.
Выполняя деление, выделяя предпериод и период, получим искомое точное выражение 1) в периодической форме:
19 / 36 = 0,52777777… = 0,52(7).
Приближенное выражение 2) получим, округляя полученную бесконечную дробь до 5 знака после запятой: 0,52777777… 0,52778.
Ответ:1)0,52(7)10, 2) 0,5277810.
4.3.3 Перевод правильных дробей из системы счисления с основанием p = 2s в двоичную систему счисления
Рассмотрим также “быстрые” правила перевода дробей. Для осуществления данного перевода из основания p = 2s в двоичную систему все величины, стоящие в разрядах дроби, заменяют их двоичными записями длины s (со всеми незначащими нулями). Если исходная дробь является периодической, то длина ее периода в двоичной системе счисления может сократиться. Незначащие нули справа в итоговом двоичном представлении можно убрать.
Пример 12. Перевести в двоичную систему счисления правильную конечную дробь, представленную в восьмеричной системе счисления: 0,30768.
Решение. 8 = 23, s = 3. Представляя по очереди цифры дроби их двоичными записями длины s = 3, получим: 38 = 0112, 08 = 0002, 78 = 1112, 68 = 1102.
Соединяя полученные двоичные выражения и отбрасывая незначащий нуль справа, получим искомое выражение.
Ответ:0,30768 = 0,011000111112.
Пример 13. Перевести в двоичную систему счисления правильную периодическую дробь, представленную в шестнадцатеричной системе счисления: 0,В58(А)16.
Решение. 16 = 24, s = 4. Представляя по очереди цифры постоянной части и периода дроби их двоичными записями длины s = 4, получим:
В16 = 10112, 516 = 01012, 816 = 10002, А16 = 10102.
Соединяя полученные двоичные записи, с учетом того, что период в двоичной системе счисления распадается на две одинаковые части, получим: 0,101101011000(10)2
Ответ:0,В58(А)16 = 0,101101011000(10)2.
4.3.4 Перевод правильных дробей из двоичной системы счисления в систему с основанием p = 2s
Перевод производится следующим образом. Начиная со старших разрядов двоичной записи (после запятой), все цифры дроби группируются по s и заменяются цифрами в системе счисления с основанием p = 2s. Если исходная двоичная дробь является конечной и в последней группе меньше, чем s знаков, ее справа дополняют незначащими нулями до s цифр. Если исходная двоичная дробь является периодической, ее период повторяется до тех пор, пока не определится период в новой системе счисления.
Пример 14. Перевести в четверичную систему счисления правильную конечную двоичную дробь 0,1101100112.
Решение. 4 = 22, s = 2. Разбивая дробную часть слева направо по два знака и дополняя в последней группе единицу справа незначащим нулем, переводим полученные в группах двузначные двоичные числа в четверичную систему счисления:
112 = 34, 012 = 14, 102 = 24, 012 = 14, 102 = 24.
Записывая слитно полученные цифры дроби, получим: 0,312124.
Ответ:0,1101100112 = 0,312124.
Пример 15. Перевести в шестнадцатеричную систему счисления правильную периодическую двоичную дробь 0,110110(011)2.
Решение. 16 = 24, s = 4.
Разбиваем дробную часть слева направо на группы по 4 знака и переводим двоичные числа в шестнадцатеричную систему счисления. Начиная со второй группы, в них входят цифры из периодов. Их выделим курсивом, начало и конец каждого периода дополнительно показаны скобками. Разбиение на группы и перевод чисел продолжаем до тех пор, пока не получим период в шестнадцатеричной системе счисления, который начинается с группы цифр, образованных периодом двоичного числа:
11012 = D16; 10(012 = 916; 1)(011)2 = В16; (011)(02 = 616; 11)(012 = D16; 1)(011)2 = В16.
Период шестнадцатеричной дроби равен (В6D) Записывая слитно полученные цифры основной части дроби и периодическую часть, получим: 0,D9(В6D)16.
Ответ:0,110110(011)2 = 0,D9(В6D)16.
4.3.5 Перевод правильных дробей из системы счисления с основанием p = 2s в систему с другим основанием, равным степени 2
В общем случае перевод проще производить через двоичную систему счисления. При переводе из шестнадцатеричной системы счисления в четверичную можно использовать связь 42 = 16 и переводить непосредственно пары цифр четверичной записи, отсчитываемые от запятой, в шестнадцатеричные цифры и обратно. В случае периодической дроби период исходной дроби переводится до тех пор, пока не будет найден период искомой дроби.
Пример 16. Перевести в восьмеричную систему счисления правильную периодическую шестнадцатеричную дробь 0,8А9(5Е)16.
Решение. Сначала, используя правило 4.3.3, переводим шестнадцатеричную дробь 0,8А9(5Е)16 в двоичную систему счисления:
816 = 0002; А16 = 10102; 916 = 10012; 516 = 01012; Е16 = 11102;
0,8А9(5Е)16 = 0,100010101001(01011110)2.
Затем по правилу 4.3.4 переводим полученную двоичную дробь в восьмеричную систему счисления (курсивом выделены цифры, которые взяты из периода, начало и конец каждого периода показаны скобками):
1002 = 48; 0102 = 28; 1012 = 58; 0012 = 18; (0102 = 28; 1112 = 78; 10)(02 = 48; 1012 = 58; 1112 = 78; 0)(012 = 18; 0112 = 38; 110)2 = 68; (0102 = 28.
Период восьмеричной дроби найден и равен (27457136). Записывая слитно полученные цифры основной части дроби и периодическую часть, получим: 0,4251(27457136)8.
Ответ:0,8А9(5Е)16 = 0,4251(27457136)8.
Пример 17. Перевести в шестнадцатеричную систему счисления из четверичной правильную периодическую дробь 0,2031223(21303)4.
Решение. По упрощенному способу перевода из системы счисления с основанием p = 4 в шестнадцатеричную систему счисления (правило 4.3.5) сначала переводим пары цифр постоянной части дроби, отсчитывая их от запятой, затем переводим цифры из периода столько раз, чтобы определить период в искомой шестнадцатеричной записи (курсивом выделены цифры, которые взяты из периода, начало и конец каждого периода показаны скобками):
204 = 816; 314 = D16; 224 = A16; 3(24 = E16; 134 = 716; 03)4 = 316; (214 = 916; 304 = C16; 3)(24 = E16.
Период восьмеричной дроби найден и равен (E739C). Записывая слитно полученные цифры основной части дроби и периодическую часть, получим: 0,8DA(E739C)16.
Ответ:0,2031223(21303)4 = 0,8DA(E739C)16.
Число, содержащее целую и дробную части, называют смешанным. Для его перевода из одной системы в другую отдельно переводят целую часть, отдельно – дробную.
Пример 18. Перевести в шестнадцатеричную систему счисления из десятичной смешанное число 7069,208910. Ответ дать с точностью до 5 знаков после запятой.
Решение. 1. Сначала по правилу 4.2.2 переводим целую часть числа из десятичной системы счисления в шестнадцатеричную путем последовательного деления десятичной записи на 16. При этом остатки от деления на каждом шаге и самое последнее частное образуют искомую шестнадцатеричную запись числа в обратном порядке.
7069 16
7056 441 16
13 432 27 16
9 16 1
11
Переводя значения в разрядах в шестнадцатеричную систему счисления и записывая их в обратном порядке, получим: 706910 = 1B9D16.
2. Затем по правилу 2.2.1 переводим дробную часть десятичной записи в шестнадцатеричную систему счисления путем последовательного умножения исходной дроби на 16. Поскольку необходимо найти 6 знаков после запятой, умножение выполняем 6 раз.
0,2089 0,3424 0,4784 0,6544 0,4704 0,5264
16 16 16 16 16 16
3,3424 5,4784 7,6544 10,4704 7,5264 8,4224
Переводя значения в разрядах в шестнадцатеричную систему счисления и выполняя округление, получим: 0,208910 0,357А7816 0,357А816.
Объединяя целую и дробную части, получим: 1B9D,357А816.
Ответ:7069,208910 1B9D,357А816.
Вопросы для проверки знаний.
1. Какие дроби называют правильными?
2. Какие дроби называют обыкновенными?
3. Какие дроби называют рациональными, а какие ‑ иррациональными?
4. Что называют предпериодом записи рациональной дроби в позиционной системе счисления?
5. Что называют периодом дроби в позиционной системе счисления и как его выделяют в записи?
6. Чем отличаются записи рациональных дробей от записей иррациональных дробей в позиционных системах счисления?
7. Может ли иррациональная дробь иметь конечную запись?
8. Что называют смешанным числом?
Практические задания.
1. Перевести дробь 0,3210 в систему счисления с основанием 3 с точностью до 5 знаков после запятой.
2. Перевести дробь 0,79 в десятичную систему счисления
3. Перевести дробь 0,467 в десятичную систему счисления. Ответ дать с точностью до 6 знаков после запятой.