1 Системы счисления § 9. Системы счисления § 10. Позиционные системы счисления § 11. Двоичная система счисления § 12. Восьмеричная система счисления § 13. Шестнадцатеричная система счисления § 14. Другие системы счисления
§ 9. Системы счисления 2
3 Система счисления — это правила записи чисел с помощью специальных знаков — цифр, а также соответствующие правила выполнения операций с этими числами. Счёт на пальцах: Унарная (лат. unus – один) – одна цифра обозначает единицу (1 день, 1 камень, 1 баран, …) только натуральные числа запись больших чисел – длинная (1 000 000?)
4 – 1 – 10 – 100 – 1 000 – 10 000 – 100 000 – 100 0000 черта хомут верёвка лотос палец лягушка человек = ? = 1235 2014 = ?
5 Непозиционная система счисления : значение цифры не зависит от её места в записи числа. унарная египетская десятичная римская славянская и другие… « Пираты XX века»
6 I – 1 (палец), V – 5 (раскрытая ладонь, 5 пальцев), X – 10 (две ладони), L – 50, C – 100 ( Centum ), D – 500 ( Demimille ), M – 1000 ( Mille ) Спасская башня Московского Кремля
7 Правила : (обычно) не ставят больше трех одинаковых цифр подряд если младшая цифра (только одна !) стоит слева от старшей, она вычитается из суммы ( частично непозиционная!) Примеры : MDC X L I V = 1000 + 500 + 100 – 10 + 50 – 1 + 5 2389 = 2000 + 300 + 80 + 9 2389 = M M C C C L X X X I X M M CCC LXXX IX = 1 644
8 MCDLXVII = MMDCXLIV = MMMCCLXXII = CMXXVIII =
9 3768 = 2983 = 1452 = 1999 =
10 только натуральные числа ( дробные ? отрицательные ?) для записи больших чисел нужно вводить новые цифры сложно выполнять вычисления Какое максимальное число можно записать? ?
11 алфавитная система счисления (непозиционная) Часы Суздальского Кремля
§ 10. Позиционные системы счисления 12
13 Позиционная система: значение цифры определяется ее позицией в записи числа. Алфавит системы счисления — это используемый в ней набор цифр. Основание системы счисления — это количество цифр в алфавите (мощность алфавита). Разряд — это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.
14 6 3 7 5 3 2 1 0 разряды 5 70 300 = 6 · 10 3 + 3 · 10 2 + 7 · 10 1 + 5 · 10 0 6000 тысячи сотни десятки единицы развёрнутая форма записи числа Схема Горнера: 6 3 7 5 = ((6 10 + 3 ) 10 + 7 ) 10 + 5 для вычислений не нужно использовать возведение в степень удобна при вводе чисел с клавиатуры, начиная с первой
15 a 3 a 2 a 1 a 0 = a 3 p 3 + a 2 p 2 + a 1 p 1 + a 0 p 0 Через развёрнутую запись: Через схему Горнера: 1234 5 = 1 5 3 + 2 5 2 + 3 5 1 + 4 5 0 = 194 =1 разряды : 3 2 1 0 разряды : 3 2 1 0 a 3 a 2 a 1 a 0 = (( a 3 p + a 2 ) p + a 1 ) p + a 0 1234 5 = (( 1 5 + 2 ) 5 + 3 ) 5 + 4 = 194 основание системы счисления
16 194 = 1234 5 = (( 1 5 + 2 ) 5 + 3 ) 5 + 4 делится на 5 остаток от деления на 5 a 3 a 2 a 1 a 0 = (( a 3 p + a 2 ) p + a 1 ) p + a 0 остаток от деления на p a 3 a 2 a 1 = ( a 3 p + a 2 ) p + a 1 частное от деления на p Как найти a 1 ? ? Как по записи числа в системе с основанием p определить, что оно делится на p 2 ? ?
17 194 5 38 190 4 5 7 35 3 5 1 5 2 1 94 = 1 234 5 10 5 5 0 0 1 Делим число на p, отбрасывая остаток на каждом шаге, пока не получится 0. Затем надо выписать найденные остатки в обратном порядке. Как перевести в систему с основанием 8? ?
в записи есть цифра 6, поэтому X > 6 переводим правую часть в десятичную систему решаем уравнение Задачи 18 Задача: в некоторой системе счисления число 71 записывается как «5 6 x » ? Определите основание системы счисления X. 71 = 5 6 X 1 0 5 6 x = 5 · X 1 + 6· X 0 = 5 · X + 6 71 = 5 · X + 6 X = 13
в записи есть цифра 5, поэтому X > 5 переводим правую часть в десятичную систему решаем уравнение Задачи 19 Задача: в некоторой системе счисления число 71 записывается как « 15 5 x » ? Определите основание системы счисления X. 71 = 15 5 X 2 1 0 155 x = 1 · X 2 + 5 · X 1 + 5 · X 0 = X 2 + 5 · X + 5 71 = X 2 + 5 · X + 5 X = 6 X = -11
20 Задача: найдите все основания систем счисления, в которых запись десятичного числа 24 оканчивается на 3. 24 = k · X + 3 21 = k · X X = 3, 7, 21
21 Задача: найдите все десятичные числа, не превосходящие 40, запись которых в системе счисления с основанием 4 оканчивается на 11. N = k · 4 2 + 1 · 4 + 1 = k · 16 + 5 При k =0, 1, 2, 3, … получаем N = 5, 21, 37, 53, …
22 Задача: Все 5-буквенные слова, составленные из букв А, О и У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА 5. … Найдите слово, которое стоит на 140-м месте от начала списка. А 0 O 1 У 2 1. 00000 2. 00001 3. 00002 4. 00010 5. … в троичной системе! на 1-м месте: 0 на 140-м месте: 139 139 = 12011 3 ОУАОО Сколько всего? ?
23 0,6375 = 6·0,1 + 3·0,01 + 7·0,001 + 5·0,0001 0, 6 3 7 5 = 6·10 -1 + 3·10 -2 + 7·10 -3 + 5·10 -4 Развёрнутая форма записи : разряды : -1 - 2 -3 -4 Схема Горнера : 0, 6375 = 10 -1 · ( 6 + 10 -1 · ( 3 + 10 -1 · ( 7 + 10 -1 ·5 ))) 0, 1 2 3 4 5 = 1 · 5 -1 + 2 · 5 -2 + 3 · 5 -3 + 4· 5 -4 0,1234 5 = 5 -1 · ( 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 ))) перевод в десятичную систему перевод в десятичную систему
24 0,1234 5 = 5 -1 · ( 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 ))) 5 · ( 0,1234 5 ) = 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 )) целая часть дробная часть 0, a 1 a 2 a 3 a 4 = p -1 ( a 1 + p -1 ( a 2 + p -1 ( a 1 + p -1 a 0 ))) p ( 0, a 1 a 2 a 3 a 4 ) = a 1 + p -1 ( a 2 + p -1 ( a 1 + p -1 a 0 )) Как найти a 2 ? ?
25 10 5 Вычисления Целая часть Дробная часть 0,9376 5 = 4,688 4 0,688 0,688 5 = 3,44 3 0,44 0,44 5 = 2,2 2 0,2 0,2 5 = 1 1 0 0,9376 0,9376 = 0,4321 5 10 5 0,3 Что делать? ?
26 10 6 25,375 = 25 + 0, 375
§ 11. Двоичная система счисления 27
28 Основание (количество цифр): 2 Алфавит : 0, 1 10 2 2 10 19 2 9 18 1 2 4 8 1 2 2 4 0 2 1 2 0 2 0 0 1 19 = 10011 2 система счисления 10011 2 4 3 2 1 0 разряды = 1 · 2 4 + 0 · 2 3 + 0 · 2 2 + 1 · 2 1 + 1 · 2 0 = 16 + 2 + 1 = 19
29 10 2 77 = 64 + 77 1024 512 256 128 64 32 16 8 4 2 1 2 10 2 9 2 8 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 77 64 Разложение по степеням двойки: 77 = 2 6 + 2 3 + 2 2 + 2 0 + 8 + … + 4 + … + 1 77 = 1001 1 01 2 6 5 4 3 2 1 0 разряды наибольшая степень двойки, которая меньше или равна заданному числу 77 = 1 2 6 + 0 2 5 + 0 2 4 + 1 2 3 + 1 2 2 + 0 2 1 + 1 2 0 13 13 5 1 5 1 8 4 1
30 1001 1 01 2 = 2 6 + 2 3 + 2 2 + 2 0 6 5 4 3 2 1 0 разряды = 64 + 8 + 4 + 1 = 77 Схема Горнера : Разряд Вычисления Результат 6 1 1 1 5 0 1 2+ 0 2 4 0 2 2+ 0 4 3 1 4 2+ 1 9 2 1 9 2+ 1 19 1 0 19 2+ 0 38 0 1 38 2+ 1 77
31 сложение вычитание 0+0=0 0+1=1 1+0=1 1+1= 1 0 2 1 + 1 + 1 = 1 1 2 0-0=0 1-1=0 1-0=1 1 0 2 -1=1 перенос заём 1 0 1 1 0 2 + 1 1 1 0 1 1 2 1 1 0 0 1 0 1 1 0 2 1 0 0 0 1 0 1 2 – 1 1 0 1 1 2 0 2 1 0 10 2 1 0 0 1 1 10 2 0 1 0 1 1 1
32 101101 2 + 11111 2 10111 2 + 101110 2 111011 2 + 10011 2 111011 2 + 11011 2
33 101101 2 – 11111 2 11011 2 –110101 2 110101 2 – 11011 2 110011 2 – 10101 2
34 умножение деление 1 0 1 0 1 2 1 0 1 2 1 0 1 0 1 2 + 1 0 1 0 1 2 1 1 0 1 0 0 1 2 1 0 1 0 1 2 – 1 1 1 2 1 1 1 2 1 1 2 1 1 1 2 – 1 1 1 2 0
35 10 2 Вычисления Целая часть Дробная часть 0,8125 2 = 1,625 1 0,625 0,625 2 = 1,25 1 0,25 0,25 2 = 0,5 0 0,5 0,5 2 = 1 1 0 0,8125 0,8125 = 0, 1101 2 10 2 0, 6 = 0,100110011001 … = 0,(1001) 2 Бесконечное число разрядов! !
36 Большинство дробных чисел хранится в памяти с некоторой погрешностью. При выполнении вычислений с дробными числами погрешности накапливаются и могут существенно влиять на результат. Желательно обходиться без использования дробных чисел, если это возможно. если то... целые если то...
37 длинная запись чисел: 1024 = 10000000000 2 запись однородна (только 0 и 1) нужны только устройства с двумя состояниями надёжность передачи данных при помехах компьютеру проще выполнять вычисления (умножение сводится сложению и т.п.)
§ 12. Восьмеричная система счисления 38
39 39 Основание : 8 Алфавит : 0, 1, 2, 3, 4, 5, 6, 7 10 8 8 10 100 8 12 96 4 8 1 8 4 8 0 0 1 100 = 144 8 144 8 2 1 0 разряды = 1 · 8 2 + 4 · 8 1 + 4 · 8 0 = 64 + 32 + 4 = 100 PDP-11, ДВК, СМ ЭВМ, БЭСМ, БК
40 134 = 75 = 134 8 = 75 8 =
41 X 10 X 8 X 2 0 0 000 1 1 001 2 2 010 3 3 011 4 4 100 5 5 101 6 6 110 7 7 111
42 8 10 2 трудоёмко 2 действия 8 = 2 3 Каждая восьмеричная цифра может быть записана как три двоичных ( триада )! ! 1725 8 = 1 7 2 5 00 1 111 010 101 2 { { { {
43 3467 8 = 2148 8 = 7352 8 = 1231 8 =
44 1001011101111 2 Шаг 1. Разбить на триады, начиная справа: 00 1 001 011 101 111 2 Шаг 2. Каждую триаду записать одной восьмеричной цифрой: 1 3 5 7 Ответ: 1001011101111 2 = 11357 8 00 1 001 011 101 111 2 1
45 101101010010 2 = 11111101011 2 = 1101011010 2 =
46 сложение 1 5 6 8 + 6 6 2 8 1 1 6 + 2 = 8 = 8 + 0 5 + 6 + 1 = 1 2 = 8 + 4 1 + 6 + 1 = 8 = 8 + 0 1 1 в перенос 1 в перенос 1 0 8 0 4 1 в перенос
47 3 5 3 8 + 7 3 6 8 1 3 5 3 8 + 7 7 7 8
48 вычитание 4 5 6 8 – 2 7 7 8 ( 6 + 8 ) – 7 = 7 (5 – 1 + 8 ) – 7 = 5 (4 – 1 ) – 2 = 1 заём 7 8 1 5 заём
49 1 5 6 8 6 6 2 8 – 1 1 5 6 8 6 6 2 8 –
§ 13. Шестнадцатеричная система счисления 50
11 Шестнадцатеричная система счисления 51 Основание : 16 Алфавит : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1 0 16 16 10 444 16 27 432 12 444 = 1BC 16 1 BC 16 2 1 0 разряды = 1 ·16 2 + 11 ·16 1 + 12 ·16 0 = 256 + 176 + 12 = 444 A, 10 B, 11 C, 12 D, 13 E, 14 F 15 С B 16 1 16 16 0 0 1 C B
52 17 1 = 206 = 1C 5 16 = 22B 16 =
53 X 10 X 16 X 2 X 10 X 16 X 2 0 0 0000 8 8 1000 1 1 0001 9 9 1001 2 2 0010 10 A 1010 3 3 0011 11 B 1011 4 4 0100 12 C 1100 5 5 0101 13 D 1101 6 6 0110 14 E 1110 7 7 0111 15 F 1111
54 16 10 2 трудоёмко 2 действия 16 = 2 4 Каждая шестнадцатеричная цифра может быть записана как четыре двоичных ( тетрада )! ! 7 F1A 16 = 7 F 1 A 0 1 11 { { 1 1 11 0 001 1010 2 { {
55 C73B 16 = 2FE1 16 =
56 Шаг 1. Разбить на тетрады, начиная справа: 000 1 0010 1110 1111 2 Шаг 2. Каждую тетраду записать одной шестнадцатеричной цифрой: 000 1 0010 1110 1111 2 1 2 E F Ответ: 1001011101111 2 = 12 EF 16 1001011101111 2
57 1010101101010110 2 = 111100110111110101 2 = 110110110101111110 2 =
58 трудоёмко 3 DEA 16 = 11 1101 1110 1010 2 16 10 8 2 Шаг 1. Перевести в двоичную систему: Шаг 2. Разбить на триады (справа): Шаг 3. Триада – одна восьмеричная цифра: 0 11 110 111 101 010 2 3 DEA 16 = 36752 8
59 A35 16 = 765 8 =
60 сложение A 5 B 16 + C 7 E 16 1 1 6 D 9 16 10 5 11 + 12 7 14 11+14=25= 16 +9 5+7+ 1 = 13 = D 16 10+12=22= 16 +6 1 1 в перенос 1 в перенос 13 9 6 1
61 С В А 16 + A 5 9 16 F D В 16 + A B C 16
62 62 вычитание С 5 B 16 – A 7 E 16 заём 1 D D 16 1 2 5 11 – 1 0 7 14 ( 11+ 16 ) – 14= 13 = D 16 (5 – 1 )+ 16 – 7= 13 = D 16 ( 12 – 1 ) – 10 = 1 заём 13 1 13
63 1 В А 16 – A 5 9 16
§ 14. Другие системы счисления 64
65 + 1 гиря на правой чашке 0 гиря снята – 1 гиря на левой чашке Как с помощью 4-х гирь взвесить от 0 до 40 кг? Троичная система! ! Веса гирь – степени числа 3: 1 кг, 3 кг, 9 кг, 27 кг Пример: 27 кг + 9 кг + 3 кг + 1 кг = 40 кг
66 ЭВМ « Сетунь » (1958), Н.П. Брусенцов Основание : 3 Алфавит : ( «-1» ), 0, 1 Для N разрядов: всего 3 N значений : 0 + по [ 3 N /2] положительных и отрицательных чисел 1 уравновешенная система –4 = (–1) 3 1 + (–1) 3 0 –3 0 = (–1) 3 1 + 0 3 0 –2 1 = (–1) 3 1 + 1 3 0 –1 0 = 0 3 1 + (–1) 3 0 0 0 0 = 0 3 1 + 0 3 0 1 0 1 = 0 3 1 + 1 3 0 2 1 = 1 3 1 + (–1) 3 0 3 1 0 = 1 3 1 + 0 3 0 4 1 1 = 1 3 1 + 1 3 0 1 1 1 1 1 1 и положительные, и отрицательные числа для изменения знака нужно поменять знаки у всех цифр запись короче, чем в двоичной системе нужны элементы с тремя состояниями
67 Десятичные цифры, закодированные в двоичном коде. В inary coded decimal (BCD). 9024,19 = 1001 0000 0010 0100, 0001 1001 ДДС 9 0 2 4 1 9 101010011,01111 ДДС = = 000 1 0101 0011, 0111 1 000 ДДС = 153,78 легко переводить в десятичную систему просто умножать и делить на 10 конечные десятичные дроби записываются точно (аналог ручных расчётов) длиннее, чем двоичная запись сложнее арифметические операции Использование – в калькуляторах.
