Бусыгин Б.С., Коротенко Г.М., Коротенко Л.М. Введение в современную информатику
Подождите немного. Документ загружается.
390
Необходимо представлять, что обычная десятичная система — это лишь
одна из многих позиционных систем счисления. В этих системах используется
конечный набор различных символов. Каждый символ называется цифрой и
обозначает определённое количество единиц. Число различных символов в
наборе называется основанием системы счисления. Если выражаемое значение
больше значения максимальной цифры в системе счисления, то для его
выражения используется последовательная запись цифр, которая и образует
число. В зависимости от той позиции, которую каждая цифра занимает в числе,
ей ставится в соответствие весовой множитель равный основанию системы.
Рассмотрим привычную десятичную систему. В ней только 10 различных
цифровых символов: 0, 1, .... 9. Тогда, например, число 536.4 с учётом
позиционности расположения цифр, выражается следующим полиномом:
5×10
2
+3×10
1
+6×10
0
+4×10
-1
Здесь цифра 5 входит с весом 100, цифра 3 – с весом 10, цифра 6 – с весом
1, а цифра 4 – с весом 0,1.
Тогда в обобщённом виде, для любой позиционной системы счисления по
некоторому основанию число может быть записано:
N = d
n–1
d
n-2
…d
1
d
0
d
–1
d
–2
…d
–m
. (2.1)
Выражению (1) будет отвечать полином:
N = d
n–1
b
n–1
+d
n–2
b
n–2
+…+d
–m
b
–m
.
(2.2)
В этой общей форме d
i
– цифры, лежащие в диапазоне 0≤d
i
<b; п – число
цифр левее разделительной, или позиционной, точки (в некоторых случаях
вместо точки используется запятая); т – число цифр правее точки, a b –
основание системы счисления. В табл. 2.1 перечислены наиболее употребимые
системы счисления. Как правило, в системах с основанием, меньшим 10, в
качестве цифровых символов используются соответствующие первые цифры
десятичной системы; для систем же с основанием, большим 10, используются
десятичные цифры с добавлением первых букв латинского алфавита. В таблице
указана также относительная упорядоченность цифр в системах.
Таблица 2.1
Системы счисления
Основание
Система счисления
Цифровые символы (цифры),
представляющие числа
2
двоичная
0,1
3
троичная
0,1,2
4
четверичная
0,1,2,3
5
пятеричная
0,1,2,3,4
8
восьмеричная
0,1,2,3,4,5,6,7
10
десятичная
0,1,2,3,4,5,6,7,8,9
12
двенадцатеричная
0,1,2,3,4,5,6,7,8,9,А,В
16
шестнадцатеричная
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Из упомянутых систем три системы представляют особый интерес при
изучении вычислительной техники — это двоичная, восьмеричная и
шестнадцатеричная. Записи некоторых чисел в этих системах выглядят
следующим образом:
391
1011,101
2
372,46
8
C65F,B3
16
По соглашению десятичный индекс, сопровождающий число, указывает
основание системы счисления. Индекс опускается, когда значение основания
ясно из контекста.
Как и в десятичной системе, число представлено совокупностью
выписанных рядом цифр. Дробная и целая части располагаются соответственно
справа и слева от разделительной точки. В случае использования двоичной
системы цифры 0 и 1 называют битами, как сокращение от BInary digiTs (англ.)
(т.е. двоичные цифры).
Таблица 2.2
Первые 32 числа в двоичной, восьмеричной и шестнадцатеричной системах и
их десятичные эквиваленты
Десятичные
Двоичные
Восьмеричные
Шестнадцатиричные
0
0
0
0
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
C
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
21
10101
25
15
22
10110
26
16
23
1011
27
17
24
11000
30
18
25
11001
31
19
26
11010
32
1A
27
11011
33
1B
28
11100
34
1C
29
11101
35
1D
30
11110
36
1E
31
11111
37
1F
392
Д.2.2. Преобразование чисел из одной системы счисления в
другую
Любое число может быть интерпретировано соответствующим полиномом
по основанию выбранной системы счисления (двоичной, восьмеричной,
шестнадцатеричной и других систем). При работе с компьютерами очень часто
приходится переводить числа из одной системы счисления в другую. Тогда
исходное и переведённое в новую систему счисления числа можно считать
эквивалентными представлениями одной и той же величины в разных системах
счисления.
Д.2.2.1. Перевод в десятичную систему чисел из не десятичной
системы
Рассмотрим этапы преобразования числа из недесятичной позиционной
системы в эквивалентную десятичную форму. Такое преобразование легко
получается простым вычислением значения полинома, соответствующего
числу. Это вычисление можно, например, выполнить следующим образом:
1. Записываем число в виде полинома
d
n–1
d
n–2
…d
0
d
–1
…d
–m
=d
n–1
b
n–1
+d
n–2
b
n–2
+…+d
0
b
0
+d
–1
b
–1
+…+d
–m
b
–m
,
где b – основание системы, выраженное в десятичной форме, а d – цифры
исходной системы счисления. Для тех систем, где цифры представляются
буквами, последние при вычислении заменяются на десятичные эквиваленты,
например А=10, В=11, С=12 и т.д.
2. Вычисляем значение полинома, пользуясь десятичной системой
счисления.
Для иллюстрации перевода из двоичной системы в десятичную систему
рассмотрим двоичное число 1110.1
2
. Записывая его в виде полинома по
cтепеням основания 2, получим
1110,1
2
=1×2
3
+ 1×2
2
+1×2
1
+0×2
0
+1×2
–1
=1×8+1×4+1×2+0×1+1×0,5
=8+4+2+0+0,5
=14,5
10
Таким образом, 14.5 есть десятичный эквивалент двоичного числа 1110.1.
В качестве второго примера преобразуем в десятичную систему
шестнадцатеричное число D3F.4
16
:
D3F,4
16
= D×16
2
+3×16
1
+F×16
0
+4×16
–1
= 13×16
2
+3×16
1
+15×16
0
+4×16
–1
= 13×256+3×16+15×1+4×0,0625
= 3328+48+15+0,25
=3391,25
10
393
Д.2.2.2. Перевод из десятичной системы в любую позиционную
систему
Перевод десятичного числа в эквивалентную форму в другой системе
счисления более сложен. В процессе преобразования приходится порознь
трансформировать целую и дробную части числа.
Рассмотрим сначала преобразование целого десятичного N
I
в систему
счисления с основанием b (b — целое положительное число). Поскольку число
в системе с основанием b можно записать в виде полинома по степеням
Несоответствующими цифрами в качестве коэффициентов, мы получаем
N
I
= d
n–1
b
n–1
+d
n–2
b
n–2
+…+d
1
b
1
+ d
0
b
0
= d
n–1
b
n–1
+d
n–2
b
n–2
+…+d
1
b
1
+ d
0
(2.3)
Теперь нужно найти цифры d
n–1
,…,
d
1
, d
0
удовлетворяющие выписанному
уравнению (2.3). Для этого разделим обе части выражения на b. Получим целое
частное:
N' = d
n–1
b
n–2
+…d
2
b
1
+d
1
b
0
(2.4)
и остаток:
Остаток
0
d
b
N
I
=
(2.5)
Таким образом, остаток равен младшей цифре числа в системе счисления с
основанием b, т.е. d
0
. В результате деления в остатке может оказаться более
одной десятичной цифры, если b больше 10. Однако поскольку остаток всегда
меньше b, то его значение будет соответствовать цифре d
0
.
Если процесс деления повторить для целого частного N′
I
, мы получим
снова целое частное:
N'' = d
n–1
b
n–3
+…+d
2
b
0
(2.6)
и остаток:
Остаток
1
d
b
N
I
=
′
(2.7)
В этом случае остаток соответствует следующей справа цифре числа с
основанием системы b. Легко видеть, что, повторяя описанный процесс, вплоть
до нулевого частного, мы получим все цифры d
i
уравнения для N
I
. Обратите
внимание на то, что остаток следует каждый раз представлять цифрой в
системе счисления с основанием b. Очевидно, что процесс завершится после
конечного числа шагов.
Разберем описанную процедуру на примере перевода десятичного числа 52
в эквивалентную двоичную форму. Вычисления проводятся многократным
делением на 2:
394
Остаток:
52 |2 0=d
0
26 |2 0=d
1
13|2 1=d
2
6 |2 0=d
3
3 |2 1=d
4
1 |2 1=d
5
0
Следовательно, 52
10
= d
5
d
4
d
3
d
2
d
1
d
0
=110100
2
.
В качестве второго примера рассмотрим перевод десятичного числа 58 506
в шестнадцатеричную систему. Последовательные деления на 16 дают:
Деление Остаток
Значения остатка в шестнадцатиричной системе счисления
58 506 |16
10
A=d
0
3 656 |16
8
8=d
1
228 |16
4
4=d
2
14 |16
14
E=d
3
0
Следовательно, 58 506
10
= d
3
d
2
d
1
d
0
= E48A
16
.
Процедура перевода правильной десятичной дроби в систему счисления с
основанием b должна быть несколько иной. Обозначим через N
F
десятичную
дробь, соответствующую полиному (2.8):
d
–1
b
–1
+d
–2
b
–2
+…+d
-m
b
–m
(2.8)
–где d
–1
, d
–2
, …, d
-m
– цифры, которые нужно определить. Поскольку
полином и N
F
обозначают одну и ту же величину, то имеет место равенство:
(2.9):
N
F
= d
–1
b
–1
+d
–2
b
–2
+…+d
-m
b
–m
(2.9)
Умножая обе части равенства (2.9) на b, получим, (2.10):
b
N
F
=
d
–1
b
0
+d
–2
b
–1
+…+d
-m
b
–m+1
= d
–1
+d
–2
b
–1
+…+d
-m
b
–m+1
= d
–1
+N’
F
(2.10)
Произведение состоит из целой части d
–1
и дробной части N'
F
. Целая часть
эквивалентна старшей цифре исходной дроби в системе счисления с
основанием b. Как и ранее, легко видеть, что целая часть, соответствующая d
–1i
,
лежит в диапазоне от 0 до b-1, и, следовательно, для систем с основанием,
большим 10, мы должны в соответствующих случаях в качестве цифр брать
буквы.
Если провести те же действия над дробной частью результата b
N
F
, т. е.
умножить его на b, то можно будет определить следующую цифру разложения
дроби N
F
.(2.11). А именно, поскольку
395
b
N’
F
=
d
–2
b
0
+d
–3
b
–1
+… + d
-m
b
–m+2
= d
–2
+d
–3
b
–1
+… + d
-m
b
–m+2
= d
–2
+N’’
F
(2.11)
то целая часть произведения соответствует d
–2
. Очевидно, повторяя
описанный процесс, мы сможем определить последующие цифры числа в
системе по основанию b. Процесс прекращается, если получается нулевая
дробная часть. Однако в отличие от процесса преобразования целых чисел,
всегда заканчивающегося через конечное число шагов, процесс преобразования
десятичной дроби может быть бесконечным. Другими словами, представление
десятичной дроби с конечным числом цифр может иметь бесконечное число
цифр в системе счисления с другим основанием. Поэтому в любом случае
процесс преобразования останавливают при достижении требуемой точности.
Приведем два примера преобразования десятичных дробей в разные
системы счисления. Сначала, рассмотрим перевод числа 0.6875 в двоичную
форму:
Произведения
Значения разрядов
2 × 0,6875 = 1,3750
d
–1
= 1
2 × 0,375 = 0,750
d
–2
=0
2 × 0,75 = 1,50
d
–3
= 1
2 × 0,5 = 1,0
d
–4
= 1
В результате мы получаем 0,6875
10
= 0.d
–1
d
–2
d
–3
d
–4
= 0,1011
2
.
Тепер переведём десятичную дробь 0,8435 в шестнадцатиричную систему.
Необходимоо ввыполнить следующую цепочку умножений:
Произведения
Значения разрядов
16 × 0,8435 = 13,496
d
–1
= D
16 × 0,496 = 7,936
d
–2
= 7
16 × 0,936 = 14,976
d
–3
= E
16 × 0,976 = 15,616
d
–4
= F
Остановив процесс на этом шаге, мы получим 0.8435
10
= 0.d
–1
d
–2
d
–3
d
–4
=
0.D7EF…
16
.
На этом примере видно, что процесс преобразования бесконечен,
поскольку третья цифра дробной части на всех шагах равна 6.
Для смешанных десятичных чисел целая и дробная части обрабатываются
порознь. Целая часть преобразуется последовательными делениями, а
дробная – последовательными умножениями. Получающееся в результате
смешанное число записывается в виде этих двух частей разделенных точкой.
Д.2.3. Выполнение операций в двоичной системе
счисления
Двоичная система счисления является основной системой представления
информации в памяти компьютера. В этой системе счисления используются
цифры: 0, 1. Над числами в двоичной системе счисления можно выполнять все
арифметические действия.
396
При этом используются следующие cоглашения: (табл.. 2.3):
Таблица 2.3
Операции в двоичной системе счисления
Сложение
Вычитание
Умножение
0+0=0
0-0=0
0*0=0
1+0=1
1-0=1
1*0=0
0+1=1
1-1=0
0*1=0
1+1=10
10-1=1
1*1=1
Двоичная система счисления обладает такими же свойствами, что и
десятичная, только для представления чисел используется не 10 цифр, а всего
две. Для кодирования числа, участвующего в вычислениях, используется
специальная система правил перевода из десятичной системы счисления в
двоичную. В результате число будет записано двоичным кодом, т.е.
представлено различным сочетанием всего двух цифр - 0 и 1.
Для сравнения рассмотрим число 45 для двух вариантов кодирования. При
использовании в тексте это число потребует для своего представления 2 байта,
т.к. каждая цифра будет представлена своим кодом в соответствии с таблицей
ASCII. В шестнадцатеричной системе код для цифры 4 будет 43, в двоичной
системе - 01000011, соответственно для цифры 5 - 53 и 01010011.
Таблица 2.4
Представление чисел в позиционных системах
Десятичная
Шестнадцатиричная
Двоичная
0
0
0000
1
1
0001
2
2
0010
3
3
0011
4
4
0100
5
5
0101
6
6
0110
7
7
0111
8
8
1000
9
9
1001
10
A
1010
11
B
1011
12
C
1100
13
D
1101
14
E
1110
15
F
1111
397
Д.2.4. Способы кодирования информации
На уроках физики при рассмотрении какого-либо физического явления вы
используете формулы. Формула - это своего рода математический код.
Рассмотренные примеры говорят о том, что для представления
информации могут использоваться разные коды и, соответственно, надо знать
определенные правила - законы записи этих кодов, т.е. уметь кодировать.
Код - набор условных обозначений для представления информации.
Кодирование - процесс представления информации в виде кода.
В качестве источников информации может выступать человек, техническое
устройство, предметы, объекты неживой и живой природы. Получателей
сообщений может быть несколько или один.
Д.2.4.1. Использование двоичной системы для кодирования
текстовой информации в ПК
Нажатие клавиши на клавиатуре приводит к тому, что сигнал посылается в
компьютер в виде двоичного числа, которое хранится в кодовой таблице.
Кодовая таблица - это внутреннее представление символов в компьютере.
Во всем мире в качестве стандарта принята таблица ASCII (American Standard
Code for Information Interchange - Американский стандартный код для обмена
информацией).
Для хранения двоичного кода одного символа выделен 1 байт = 8 бит.
Учитывая, что каждый бит принимает значение 0 или 1, количество их
возможных сочетаний в байте равно 2
8
= 256.
Значит, с помощью 1 байта можно получить 256 разных двоичных кодовых
комбинаций и отобразить с их помощью 256 различных символов. Эти
комбинации и составляют таблицу ASCII (см. Приложение 6).
Например, вы нажимаете на клавиатуре латинскую букву S. В этом случае
в память компьютера записывается код 01010011. Для вывода буквы S на экран
в компьютере происходит декодирование – то есть, по этому двоичному коду
строится (т.е. отображается в виде пикселов) изображение этого символа.
Д.2.4.2. Кодирование графической информации
Создавать и хранить графические объекты в компьютере можно двумя
способами - как растровое изображение или как векторное изображение. Для
каждого типа изображения используется свой способ кодирования.
Векторное изображение представляет собой графический объект,
состоящий из элементарных отрезков и дуг. Положение этих элементарных
объектов определяется координатами точек и длиной радиуса.
Для каждой линии указывается ее тип (сплошная, пунктирная, штрих-
пунктирная), толщина и цвет. Информация о векторном изображении
кодируется как обычная буквенно-цифровая и обрабатывается специальными
программами.
398
Растровое изображение представляет собой совокупность точек,
используемых для его отображения на экране монитора. Объем растрового
изображения определяется умножением количества точек на информационный
объем одной точки, который зависит от количества возможных цветов. Для
черно-белого изображения информационный объем одной точки равен 1 биту,
т.к. она может быть либо черной, либо белой, что можно закодировать двумя
цифрами - 0 или 1. Рассмотрим, сколько потребуется бит для отображения
цветной точки:
–для 8 цветов - 3 бита; для 16 цветов - 4 бита; для 256 цветов - 8 битов (1
байт). В таблице 2.5 показано кодирование цветовой палитры из 16 цветов.
Разные цвета и их оттенки получаются за счет наличия или отсутствия трех
основных цветов (красного, синего, зеленого) и их яркости. Каждая точка на
экране кодируется с помощью 4 битов.
Таблица 2.5
Кодирование 16-цветной палитры.
Цвет Яркость Красный Зелёный Синий
Значения в
системе счисления
10-ная
16-ная
Чёрный
0
0
0
0
0
0
Синий
0
0
0
1
1
1
Зелёный
0
0
1
0
2
2
Голубой
0
0
1
1
3
3
Красный
0
1
0
0
4
4
Фиолетовый
0
1
0
1
5
5
Коричневый
0
1
1
0
6
6
Белый
0
1
1
1
7
7
Серый
1
0
0
0
8
8
Светло-синий
1
0
0
1
9
9
Светло-
зелёный
1 0 1 0 10 A
Светло-
голубой
1 0 1 1 11 B
Светло-
красный
1 1 0 0 12 C
Светло-
фиолетовый
1 1 0 1 13 D
Жёлтый
1
1
1
0
14
E
Ярко-белый
1
1
1
1
15
F
399
Приложение 3
Характеристики языков программирования
Название языка
программирования (ЯП)
Год
созд.
Тип
языка
Автор (ы) разработки География
Органи-
зация
Стандарт
Фортран (FORTRAN) 1954 A Джон Бекус Америка IBM
ISO
1539:1997
Лисп (LISP)
1958
F
Джон Маккарти
Америка
MIT
–
Алгол-60
(Algol 60)
1960 A Питер Наур+
Между-
народн.
IFIP
–
Кобол (COBOL) 1960 A +
Между-
народн.
CODASYL
Committee
ISO
1989:1985
Симула (Simula)
1962
B
Кристен Нигаард+
Европа
–
–
Бейсик (BASIC) 1963 A
Томас Курт и Джон
Кемени+
Америка
Dartmouth
College
ISO
10279:1991
ПЛ/1 (PL/I) 1964 A Джордж Радин Америка IBM
ISO
6160:1979
Алгол-68 (Algol 68) 1968 A Аад ван Вайнгартен+
Между-
народн.
IFIP
–
Паскаль (Pascal)
1970
C
Никлаус Вирт
Европа
ETH
ISO
7185:1990
Форт (FORTH) 1970 A* Чарльз Мур Америка
Mohasco
Industries
ISO
15145:1997
Си (С) 1972 C* Деннис Ритчи Америка
AT&T Bell
Labs
ISO
9899:1999
Smalltalk 1972 B/ОО Аллан Кэй Америка
Xerox
PARC
–
Пролог (Рrolog) 1973 E Аллан Кольмеро+ Европа
Univеrs. of
Aix-
Marseille
ISO
13211:1995
Ада (Ada) 1980 H* Джин Ишбиа+ Америка
CII
Honeywell
ISO
8652:1995
Си++
1980/
1984
H*
–/ОО
Бьёрн Страуструп Америка
AT&T Bell
Labs
ISO
14882:1998
Turbo Pascal 1983 –/–
Филипп Кан,
Андерс Хейльсберг
(Anders Hejlsberg)
Америка
Borland
International
–
Perl 1986 ЯС/ОО
Ларри Вол
(Larry Wall)
Между-
народн.
– –
HTML
1989
I
Тим Барнерс-Ли
Европа
CERN
–
Python
1990
(99v 2.0)
ЯС/ОО
Гвидо ван Россум
(Guido van Rossum)
Голландия/
Америка
– –
Visual Basic
1991
ЯС/ОО
–
Америка
Microsoft
–
Delphi/Object Pascal 1995 –/ОО Андерс Хейльсберг
Америка
Borland
International
–
Java 1995
H
ЯС/ОО
Патрик Нотон
и Джеймс Гослинг
Америка Sun Labs
–
Java Script
1995
ЯС/ОО
–
Америка
–
–
VBScript
1997
ЯС/ОО
–
Америка
Microsoft
–
Cold Fusion
1997
–/ОО
–
Америка
–
XML
1998
I
–
Америка
W3C,
World
Wide Web
Consortium
–
C# (Си Шарп) 2000
H*
/ОО/D
Андерс Хейльсберг+ Америка Microsoft –