для т. точно
.pdf1. Системы счисления Система счисления - способ записи (изображения) чисел.
Символы, при помощи которых записывается число, называются цифрами. Системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в коде(записи) числа, называются позиционными.
Основанием позиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления.
Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или "вес" каждого разряда.
Например: Базисы некоторых позиционных систем счисления.
Десятичная система: 100, 101, 102, 103, 104, ..., 10n, ...
Двоичная система: 20, 21, 22, 23, 24, ..., 2n, ...
Восьмеричная система: 80, 81, 82, 83, 84, ..., 8n, ...
Совокупность различных цифр, используемых в позиционной системе
счисления для записи чисел, называется алфавитом системы счисления.
Количество цифр в алфавите равно основанию системы счисления.
Уравновешенные системы счисления
---===---
Двоичная СС с большим успехом используется в компьютерной технике до сих пор. Однако выявились и существенные недостатки использования двоичной СС, влияющие на скорость работы процессора и надежность передачи информации.
Одним из этих недостатков является так называемая проблема представления отрицательных чисел. Попытка преодолеть этот и другие недостатки двоичной
системы счисления стимулировала использование в компьютерах других систем
счисления и развитие собственно теории систем счисления.
Выбирая систему кодирования информации в компьютере, разработчики в первую очередь думают о быстродействии процессора, т.е. о скорости обработки закодированной информации.
///
Что привычно и хорошо для человека, выполняющего вычисления на бумаге, не всегда хорошо для компьютера. Для того чтобы сложить два целых числа с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить следующие действия:
1)взять модули слагаемых;
2)сравнить эти модули;
3)запомнить знак большего по модулю слагаемого;
4)получившийся результат з
5)из большего модуля вычесть меньший модуль;
6)записать со знаком из п. 3.
Многовато будет для простой и часто используемой операции!
\\\
В десятичной системе счисления для представления отрицательных чисел человек использует знак числа. То, есть для записи отрицательных чисел имеющихся 10 знаков недостаточно. Используется еще один знак - '-'.
То есть для записи отрицательных десятичных чисел потребоваломь 11 знаков!
Аналогично, для записи отрицательных двоичных чисел требуется 3 знака, но в нашем распоряжении их два - 0 и 1. Для решения проблемы вначале века использовалось прямое кодирование: в старший бит регистра числа явно
вписывался знак '0' для положительных и знак '1' для отрицательных чисел. При определении значения числа этот бит игнорировался. Вроде бы все нормально, но процессор не может работать с отдельными битами регистра. Для определения знака числа, число загружалось в процессор, применение маски (числа 10 или 1000) оставляло в регистре только бит знака, весь
регистр проверялся (ноль или нет). Для выделения значения числа снова использовалась маска (7F или 7FFF), после чего определялось число -
не слишком ли много действий процессора для выполнения простых операций?
///
для 1 байта 5 = 00000101 -5 = 10000101
\\\
Чтобы сократить число действий процессора, придумали обратный код: для чисел договорились старший бит не использовать, а для получения отрицательного числа выполнять команду инвертирования - менять в записи 0 на 1, а 1 на 0. Это одна команда для процессора. Но проверка бита знака все равно остется.
///
для 1 байта 5 = 00000101 -5 = 11111010
\\\
Кроме всего прочего применение прямого или обратного кодирования добавляет новую проблему: число 0 оказываеися можно хранить двумя разными способами (как?). Появились значения +0 и -0.
Представьте, решаем квадратное уравнение, и начинаем проверять, равен ли он 0. Поребуется сравнивать как с число 0, так и с числом -0, - двойная работа!
Использующийся в настоящее время во всех компьютерах способ хранения отрицательных чисел называется "дополнительный код". Для получения из положительного числа отрицательного, как и при дополнительном коде, выполняют инвертирование, после чего к результату добавляется 1. Неболбьшое усложнение кодирования снимает проблему двойного представления нуля:
00000000 - исходное
11111111 - после инвертирования
11111111
1
----------
100000000 - после добавления 1 Так как самый старший бит является девятым и в однобайтный регистр не
помещается, он будет отброшен. То есть 0 представляется только как 00000000.
Кодирование называется дополнительным, потому что положительное и отрицательное числа "дополняют" друг друга до той самой единицы, бит для хранения которой выходит за пределы регистра. Поэтому и преобразование отрицательного числа в положительное происходит по тому же правилу: инверсия и увеличение на 1.
Еще одно преимущество такого представления чисел: появилась возможность отказаться от операции вычитания. Вместо нее применяется сложение с отрицательным числом.
Попробуйте выполнить сложение над двоичными числами, записанными в дополнительном коде.
///
!!! подобрать примеры сложения положительных, отрицательных, смешанных чисел !!!
\\\
Все вроде хорошо, но попробуйте в переменную X, объявленную как var x:integer;
записать положительное число 37000, хранимое без знака (как word), получим, неожидано, отрицательный результат -28536!
Подобные фокусы могут привести к ошибочной интерпретации результатов работы программы.
///
var x:integer; y:word; begin
y:=37000; x:=y; writeln(x); readln; end.
\\\
Ошибка произошла потому, что типы integer и word по разному понимают
содержимое старшего бита регистра.
---===---
Троичная система
Можно ли записывать целые отрицательные числа без знака, но и без дополнительного кодирования?
Можно! Например, в любой P-ичной уравновешенной системе счисления.
Уравновешенная система с наименишим основанием - это троичная. В 60-х годах XX столетия в МГУ им. М.В. Ломоносова была создана
троичная ЭВМ "Сетунь", запущенная потом в серию. Для кодирования информации в этой машине использовалась троичная уравновешенная система счисления,
вместо бита использовался трит, вместо привычной двоичной логики - троичная.
Разработчик этой ЭВМ Николай Петрович Брусенцов.
|||"бит" - место для хранения двоичной цифры - 0 или 1,
|||"трит" - место для хранения цифры троичной системы счисления.
Троичную систему счисления можно построить, как и другие, взяв за основание число 3. Базой при этом будут числа 1, 3, 9, 27, 81, ..., а цифрами (алфавитом) 0, 1 и 2. Но кто нам мешает в качестве цифр
взять символы { a, 0, 1}, где a равно -1. Глядя на набор цифр, понятно,
почему эту систему назвали уравновешенной, или симметричной. Количество цифр до цифры 0 такое же ("уравновешено с"), что количество цифр после цифры 0. "Уравновесить" можно любые системы счисления с нечетным основанием.
Десятичное число |
|
Число в троичной уравновешенной системе |
||
положительное |
отрицательное положительное |
отрицательное |
||
1 |
-1 |
1 |
a |
|
2 |
-2 |
1a |
a1 |
|
3 |
-3 |
10 |
a0 |
|
4 |
-4 |
11 |
aa |
5 |
-5 |
1aa |
a11 |
6 |
-6 |
1a0 |
a10 |
7 |
-7 |
1a1 |
a1a |
Очевидно, знак для представления отрицательных чисел в урвновешенных системах счисления не нужен!
Если у нас есть хотя бы трицифры, обязательно 0, обязательно 1, для третьей цифры можем ставить в соответствие отрицательное значение (- 1).
Можно ввести отрицательные значения для некотрых цифр СС с четным основанием, но это приводит к тому, что некоторые числа можно будет записать разными способами.
///
Для "четверичной" системы счисления можно выбрать и {-1, 0, 1, 2}, и {-2, -1, 0, 1}.
\\\
---===---
Рассмотрим операции сложения и вычитания в троичных системах:
в троичной системе Сложение
+ |
0 |
1 |
2 |
0 |
0 |
1 |
2 |
1 |
1 |
2 |
10 |
2 |
2 |
10 |
11 |
Умножение
* |
0 |
1 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
0 |
2 |
11 |
в троичной уравновешенной системе сложение
+ |
1 |
0 |
1 |
1 |
11 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
11 |
|
умножение |
||
* |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
///
сформировать правила построения таблиц сложения и умножения и правила арифметических операций для целых чисел.
\\\
Числа Фибона́ччи— элементы числовой последовательности, где каждое следующее число образуется суммой двух перед ним стоящих чисел (кроме первых двух).
Фибоначчиева система счисления (фсс)
Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее
теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания.
Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101fib = 3810.
Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел.
Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение:
F0 = 1, F1 = 1, Fn = Fn2 + Fn1 .
Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250).
ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 … . Обратите внимание, что F0 = 1 в базис не включается.
В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления.
Д |
д ФСС |
е |
в |
со
яи
|
т |
ч |
|
|
и |
н |
|
|
ч |
о |
|
|
н |
е |
|
|
о |
|
|
|
е |
|
|
|
|
|
|
|
1 |
1 |
1 |
2 |
1 |
10 |
|
|
|
0 |
|
|
|
|
|
3 |
1 |
100 или |
|
|
|
1 |
11 |
|
|
|
|
4 |
1 |
101 |
|
|
|
0 |
|
0
51 1000 или
0 110
1
1 1 10010
00 или 1110
1
0
2 1 101010
00
1
0
0
5 1 10100100
0 1 или
010011100
0или
1 10100011
0или
10011011
Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей.
Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа.
4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно Как известно, все позиционные системы устроены одинаково и, следовательно, перевод из любой позиционной системы счисления в десятичную осуществляется по одному и тому же алгоритму.
В P-ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k-м месте слева, равен a-Pk, где P — основание системы счисления. Часто говорят, что “вес” k-го разряда равен Pk.
В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k-го разряда используется k-е число Фибоначчи.
1 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- й й й й й й й й й |
|||||||||
й |
|
|
|
|
|
|
|
|
|
рр р р р р р р р
ра а а а а а а а а
а з з з з з з з з з
з р р р р р р р р р
ря я я я я я я я я
я д д д д д д д д д
д
8 5 3 2 1 8 5 3 2 1
9 5 4 1 3
2)Понятия алгоритма и исполнителя Понятие алгоритма
Из отсутствия четкого определения алгоритма делаем вывод, что алгоритм - неопределяемое понятие и, как и для неопределяемых понятий в других