Системы счисления презентация

Системы счисления
§ 9. Системы счисления

Что такое система счисления?
Система счисления — это правила записи чисел с помощью специальных знаков — цифр, а также соответствующие правила выполнения операций с этими числами.
Счёт на пальцах:
Унарная (лат. unus – один) – одна цифра обозначает единицу (1 день, 1 камень, 1 баран, …)
только натуральные числа
запись больших чисел – длинная (1 000 000?)

Египетская десятичная система
– 1
– 10
– 100
– 1000
– 10000
– 100000
– 1000000
черта
хомут
верёвка
лотос
палец
лягушка
человек
= ?
=1235
2014 = ?

Непозиционные системы счисления
Непозиционная система счисления: значение цифры не зависит от её места в записи числа.
унарная
египетская десятичная
римская
славянская
и другие…
«Пираты XX века»

Римская система счисления
I – 1 (палец),
V – 5 (раскрытая ладонь, 5 пальцев),
X – 10 (две ладони),
L – 50,
C – 100 (Centum),
D – 500 (Demimille),
M – 1000 (Mille)
Спасская башня Московского Кремля

Римская система счисления
Правила:
(обычно) не ставят больше трех
одинаковых цифр подряд
если младшая цифра (только одна!) стоит слева от старшей, она вычитается из суммы (частично непозиционная!)
Примеры:
MDCXLIV =
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
= 1644

Римская система счисления
MCDLXVII =
MMDCXLIV =
MMMCCLXXII =
CMXXVIII =

Римская система счисления
3768 =
2983 =
1452 =
1999 =

Римская система счисления
только натуральные числа (дробные? отрицательные?)
для записи больших чисел нужно вводить новые цифры
сложно выполнять вычисления

Славянская система счисления
алфавитная система счисления (непозиционная)
Часы Суздальского Кремля

Системы счисления
§ 10. Позиционные системы счисления
Д/З: § §9,10, воп. 1-13, уп. 2-9

Определения
Позиционная система: значение цифры определяется ее позицией в записи числа.
Алфавит системы счисления — это используемый в ней набор цифр.
Основание системы счисления — это количество цифр в алфавите (мощность алфавита).
Разряд — это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.

*
Даны системы счисления:
с основанием 2, 8, 10, 16. Запись вида 100
1) отсутствует в двоичной;
2) существует во всех перечисленных;
3) отсутствует в десятичной;
4) отсутствует в восьмеричной;
5) отсутствует в 16-ной.

*
Какое из чисел 1100112, 1114, 1В16
является наибольшим?

Какое минимальное основание N должно быть у системы счисления, чтобы в ней были правильными записи 101N, 100N, 641N и 251N?

Формы записи чисел
6 3 7 5
3 2 1 0
разряды
5
70
300
= 6·103 + 3·102 + 7·101 + 5·100
6000
развёрнутая форма записи числа
Схема Горнера:
6 3 7 5 = ((6⋅10 + 3)⋅10 + 7)⋅10 + 5
для вычислений не нужно использовать возведение в степень
удобна при вводе чисел с клавиатуры, начиная с первой

Перевод в десятичную систему
a3a2a1a0 = a3⋅p 3 + a2⋅p 2 + a1⋅p 1 + a0⋅p 0
Через развёрнутую запись:
Через схему Горнера:
12345 = 1⋅53 + 2⋅52 + 3⋅51 + 4⋅50 = 194
=1
разряды: 3 2 1 0
разряды: 3 2 1 0
a3a2a1a0 = ((a3⋅p + a2)⋅p + a1)⋅p + a0
12345 = ((1⋅5 + 2)⋅5 + 3)⋅5 + 4 = 194
основание системы счисления

Перевод из десятичной в любую
194 = 12345 = ((1⋅5 + 2)⋅5 + 3)⋅5 + 4
делится на 5
остаток от деления на 5
a3a2a1a0 = ((a3⋅p + a2)⋅p + a1)⋅p + a0
остаток от деления на p
a3a2a1 = (a3⋅p + a2)⋅p + a1
частное от деления на p

Перевод из десятичной в любую
194
194 = 12345
10 → 5
Делим число на p, отбрасывая остаток
на каждом шаге, пока не получится 0. Затем надо выписать найденные остатки в обратном порядке.

в записи есть цифра 6, поэтому X > 6
переводим правую часть в десятичную систему
решаем уравнение
Задачи
Задача: в некоторой системе счисления число 71 записывается как «56x»? Определите основание системы счисления X.
71 = 56X
1 0
56x
= 5·X1 + 6·X0
= 5·X + 6
71 = 5·X + 6
X = 13

в записи есть цифра 5, поэтому X > 5
переводим правую часть в десятичную систему
решаем уравнение
Задачи
Задача: в некоторой системе счисления число 71 записывается как «155x»? Определите основание системы счисления X.
71 = 155X
2 1 0
155x
= 1·X2 + 5·X1 + 5·X0
= X2 + 5·X + 5
71 = X2 + 5·X + 5
X = 6
X = -11

Задачи
Задача: найдите все основания систем счисления, в которых запись десятичного числа 24 оканчивается на 3.
24 = k·X + 3
21 = k·X
X = 3, 7, 21

Задачи
Задача: найдите все десятичные числа,
не превосходящие 40, запись которых в системе счисления с основанием 4 оканчивается на 11.
N = k·42 + 1·4 + 1 = k·16 + 5
При k =0, 1, 2, 3, … получаем
N = 5, 21, 37, 53, …

Дробные числа: из десятичной в любую
10 → 5
0,9376
0,9376 = 0,43215
10 → 5
0,3

Дробные числа
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 45 = 1·5-1 + 2·5-2 + 3·5-3 + 4·5-4
0,12345 = 5-1·(1 + 5-1·(2 + 5-1·(3 + 5-1·4)))
перевод в десятичную систему
перевод в десятичную систему

Дробные числа: из десятичной в любую
0,12345 = 5-1·(1 + 5-1·(2 + 5-1·(3 + 5-1·4)))
5·(0,12345)= 1 + 5-1·(2 + 5-1·(3 + 5-1·4))
целая часть
дробная часть
0,a1a2a3a4 = p-1⋅(a1 + p-1⋅(a2 + p-1⋅(a1 + p-1⋅ a0)))
p⋅(0,a1a2a3a4) = a1 + p-1⋅(a2 + p-1⋅(a1 + p-1⋅ a0))

Дробные числа: из десятичной в любую
10 → 6
25,375
= 25 + 0,375

Системы счисления
§ 11. Двоичная система счисления.
Д/З § 11, воп. 1-3, уп 4,5,8,6(б,в),7(б,в)

Двоичная система
Основание (количество цифр): 2
Алфавит: 0, 1
10 → 2
2 → 10
19
19 = 100112
система счисления
100112
4 3 2 1 0
разряды
= 1·24 + 0·23 + 0·22 + 1·21 + 1·20
= 16 + 2 + 1 = 19

Метод подбора
10 → 2
77 = 64 +
77
77
64
Разложение по степеням двойки:
77 = 26 + 23 + 22 + 20
+ 8 + …
+ 4 + …
+ 1
77 = 10011012
6 5 4 3 2 1 0
разряды
наибольшая степень двойки, которая меньше или равна заданному числу
77 = 1⋅26 + 0⋅25 + 0⋅24 + 1⋅23 +1⋅22 +0⋅21 + 1⋅ 20
13
13
5
1
5
1
8
4
1

Перевод из двоичной в десятичную
10011012 = 26 + 23 + 22 + 20
6 5 4 3 2 1 0
разряды
= 64 + 8 + 4 + 1 = 77
Схема Горнера:

Арифметические операции
сложение
вычитание
0+0=0 0+1=1
1+0=1 1+1=102
1 + 1 + 1 = 112
0-0=0 1-1=0
1-0=1 102-1=1
перенос
заём
1 0 1 1 02
+ 1 1 1 0 1 12
1
1
0
0
1
0
1
1
0
2
1 0 0 0 1 0 12
– 1 1 0 1 12
1
∙
∙
0 102
1
0
0 1 1 102
0
1
0
1
1
1

Арифметические операции

Арифметические операции

Арифметические операции
умножение
деление
1 0 1 0 12
× 1 0 12
1 0 1 0 12
+ 1 0 1 0 12
1 1 0 1 0 0 12
1 0 1 0 12
– 1 1 12
1 1 12
1
1 1 12
– 1 1 12
0

Дробные числа
10 → 2
0,8125
0,8125 = 0,11012
10 → 2
0,6 =
0,100110011001… =
0,(1001)2

Дробные числа
Большинство дробных чисел хранится в памяти с некоторой погрешностью.
При выполнении вычислений с дробными числами погрешности накапливаются и могут существенно влиять на результат.
Желательно обходиться без использования дробных чисел, если это возможно.
если то...
если то...

Двоичная система счисления
длинная запись чисел: 1024 = 100000000002
запись однородна (только 0 и 1)
нужны только устройства с двумя состояниями
надёжность передачи данных при помехах
компьютеру проще выполнять вычисления (умножение сводится сложению и т.п.)

10 → 2
23,25
= 23 + 0,25

Системы счисления
§ 12. Восьмеричная система счисления. Уп. № 2,3,4, в 1-4
§ 13. Шестнадцатеричная система счисления. Уп. № 5-7, в 1-4

Переведи в 2-ую СС
26,37510→Х2
2610=110102
0,37510=0,0112
26,37510=11010,0112

00000111
[phone]
0
1
1
1
0
0
0
1
1
1
1
0
0
0
1
1
1

111011
+ 111
0
1
1
1
0
0
0
1
1
1
1
0

Задача
В саду 100 фруктовых деревьев – 14 яблонь и 42 груши. В какой системе счисления посчитаны деревья?
6

1100011002
-11012

Выполните вычитание двоичных чисел:
А) 111-101
Б) 11011-01110
В) 10011010-1100101
Г) 10101010-01010101

Выполните умножение:
111010 · 10010
(Ответ: 10000010100)
11100 · 10110
(Ответ: 1001101000)
100001 · 111,11
(Ответ: 11111111,11)
Выполните деление:
1000000 : 1110
(Ответ: 100)
10111001101 : 110101
(Ответ: 11100)

Восьмеричная система счисления
Основание: 8
Алфавит: 0, 1, 2, 3, 4, 5, 6, 7
10 → 8
8 → 10
100
100 = 1448
1448
2 1 0
разряды
= 1·82 + 4·81 + 4·80
= 64 + 32 + 4 = 100
PDP-11, ДВК,
СМ ЭВМ, БЭСМ,
БК

Примеры
134 =
75 =
1348 =
758 =

11
Шестнадцатеричная система счисления
Основание: 16
Алфавит: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10 → 16
16 → 10
444
444 = 1BC16
1BC16
2 1 0
разряды
= 1·162 + 11·161 + 12·160
= 256 + 176 + 12 = 444
A,
10
B,
11
C,
12
D,
13
E,
14
F
15
С
B
C
B

Примеры
171 =
206 =
1C516 =
22B16 =

Восьмеричная
Шестнадцатеричная

Перевод в двоичную систему счисления
8
10
2
трудоёмко
2 действия
8 = 23
17258 =
1 7 2 5 001
111
010
1012
{
{
{
{

Примеры
34678 =
21488 =
73528 =
12318 =

Перевод из двоичной в восьмеричную
10010111011112
Шаг 1. Разбить на триады, начиная справа:
001 001 011 101 1112
Шаг 2. Каждую триаду записать одной восьмеричной цифрой:
1
3
5
7
Ответ: 10010111011112 = 113578
001 001 011 101 1112
1

Примеры
1011010100102 =
111111010112 =
11010110102 =

Перевод в двоичную систему
16
10
2
трудоёмко
2 действия
16 = 24
7F1A16 =
7 F 1 A
0111
{
{
1111 0001
10102
{
{

Примеры
C73B16 =
2FE116 =

Перевод из двоичной системы
Шаг 1. Разбить на тетрады, начиная справа:
0001 0010 1110 11112
Шаг 2. Каждую тетраду записать одной шестнадцатеричной цифрой:
0001 0010 1110 11112
1
2
E
F
Ответ: 10010111011112 = 12EF16
10010111011112

Примеры
10101011010101102 =
1111001101111101012 =
1101101101011111102 =

Перевод в восьмеричную и обратно
трудоёмко
3DEA16 =
11 1101 1110 10102
16
10
8
2
Шаг 1. Перевести в двоичную систему:
Шаг 2. Разбить на триады (справа):
Шаг 3. Триада – одна восьмеричная цифра:
011 110 111 101 0102
3DEA16 = 367528

Примеры
A3516 =
7658 =

Арифметические операции
сложение
1 5 68
+ 6 6 28
1
1
6 + 2 = 8 = 8 + 0
5 + 6 + 1 = 12 = 8 + 4
1 + 6 + 1 = 8 = 8 + 0
1
1 в перенос
1 в перенос
1
08
0
4
1 в перенос

Примеры

Арифметические операции
вычитание
4 5 68
– 2 7 78
∙
(6 + 8) – 7 = 7
(5 – 1 + 8) – 7 = 5
(4 – 1) – 2 = 1
∙
заём
78
1
5
заём

Примеры

Арифметические операции
сложение
A 5 B16
+ C 7 E16
1
1 6 D 916
10 5 11
+ 12 7 14
11+14=25=16+9
5+7+1=13=D16
10+12=22=16+6
1
1 в перенос
1 в перенос
13
9
6
1

Примеры
С В А16
+ A 5 916
F D В16
+ A B C16

Арифметические операции
вычитание
С 5 B16
– A 7 E16
заём
∙
1 D D16
12 5 11
– 10 7 14
∙
(11+16)–14=13=D16
(5 – 1)+16 – 7=13=D16
(12 – 1) – 10 = 1
заём
13
1
13

Примеры
1 В А16
– A 5 916

*
Дано: а=D716, b=3318. Какое из чисел с, записанных в двоичной системе счисления, удовлетворяет неравенству a < c < b?
110110012 2) 110111002
3) 110101112 4) 110110002

Решите уравнение
Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.
ответ: 20.

Задачи
Задача: Все 5-буквенные слова, составленные из букв А, О и У, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
5. …
Найдите слово, которое стоит на 140-м месте от начала списка.
1. 00000
2. 00001
3. 00002
4. 00010
5. …
в троичной системе!
на 1-м месте: 0
на 140-м месте: 139
139 = 120113

Р-03. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. КККК
2. КККЛ
3. КККР
4. КККТ
……
Запишите слово, которое стоит на 67-м месте от начала списка.
Решение:
самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв)
выполним замену К→0, Л→1, Р→2, Т→3; поскольку нумерация слов начинается с единицы, а первое число КККК→0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024
Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.
Ответ: ЛККР.

Р-02. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.
Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
……
Запишите слово, которое стоит на 240-м месте от начала списка.
Решение (1 способ, перебор с конца):
подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв;
очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 3×3=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ)
аналогично можно показать, что есть всего 35 = 243 слова из 5 букв
очевидно, что последнее, 243-е слово – это УУУУУ
далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е)
Ответ: УУУОУ.

Р-01. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.
Вот начало списка:
1. ААААА
2. ААААК
3. ААААЛ
4. ААААО
5. ААААШ
6. АААКА
……
На каком месте от начала списка стоит слово ШКОЛА?
Решение:
по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А → 0, К → 1, Л → 2, О → 3 и Ш → 4
слово ШКОЛА запишется в новом коде так: 413205
переводим это число в десятичную систему:
413205 = 4⋅54 + 1⋅53 + 3⋅52 + 2⋅51 = 2710
поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…
Ответ: 2711.

*
Дано число а=9216 и число b=2248. Какое из чисел с, записанных в двоичной системе счисления удовлетворяет условию: a
10010011
10001110
10001010
10001100

Домашнее задание
Дано:а=ЕА16, b=3548 . Какое из чисел c, записанных в двоичной системе счисления, удовлетворяет неравенству a
1) 111010102
2) 111011102
3) 111010112
4) 111011002
*

Системы счисления
§ 14. Другие системы счисления

Задача Баше о наборе гирь
+ 1 гиря на правой чашке
0 гиря снята
– 1 гиря на левой чашке
Как с помощью 4-х гирь взвесить от 0 до 40 кг?
Веса гирь – степени числа 3:
1 кг, 3 кг, 9 кг, 27 кг
Пример:
27 кг + 9 кг + 3 кг + 1 кг = 40 кг

Троичная уравновешенная система
ЭВМ «Сетунь» (1958) , Н.П. Брусенцов
Основание: 3
Алфавит: («-1»), 0, 1
Для N разрядов: всего 3N значений:
0 + по [3N/2] положительных и отрицательных чисел
уравновешенная система
и положительные, и отрицательные числа
для изменения знака нужно поменять знаки у всех цифр
запись короче, чем в двоичной системе
нужны элементы с тремя состояниями

Двоично-десятичная система (ДДС)
Десятичные цифры, закодированные в двоичном коде. Вinary coded decimal (BCD).
9024,19 = 1001 0000 0010 0100, 0001 1001ДДС
9 0 2 4 1 9
101010011,01111ДДС =
= 0001 0101 0011, 0111 1000ДДС = 153,78
легко переводить в десятичную систему
просто умножать и делить на 10
конечные десятичные дроби записываются точно (аналог ручных расчётов)
длиннее, чем двоичная запись
сложнее арифметические операции
Использование – в калькуляторах.

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[e-mail]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[e-mail]