Трофимов И.Е. Непозиционные и смешанные системы счисления

Подождите немного. Документ загружается.

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Кузбасский государственный технический университет»

Кафедра вычислительной техники

и информационных технологий

НЕПОЗИЦИОННЫЕ И СМЕШАННЫЕ

СИСТЕМЫ СЧИСЛЕНИЯ

Методические указания к самостоятельной работе по дисциплине

«Операционные системы, среды и оболочки»

для студентов специальности 080801

«Прикладная информатика в экономике»

Составитель И. Е. Трофимов

Утверждены на заседании кафедры

Протокол № 10 от 13.03.2009

Рекомендованы к печати

учебно-методической комиссией

специальности 080801

Протокол № 8 от 13.03.2009

Электронная копия хранится

в библиотеке ГУ КузГТУ

Кемерово 2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.........................................................................................2

1. НЕПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ.......................3

1.1. Римская система счисления.....................................................4

1.2. Система остаточных классов (СОК).......................................5

1.3. Система счисления Штерна-Броко.........................................6

2. СМЕШАННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ................................7

2.1. Система счисления майя..........................................................8

2.2. Факториальная система счисления.........................................8

2.3. Фибоначчиева система счисления..........................................9

3. КОНТРОЛЬНЫЕ ВОПРОСЫ.....................................................10

4. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.........................................11

ВВЕДЕНИЕ

Одним из обязательных требований к специалисту в области

информационных технологий является знание принципов работы

с числами. Изучению специфичных способов работы с числами

посвящена данная работа.

На ранних ступенях развития общества люди почти не

умели считать. Они различали совокупности двух и трех

предметов; всякая совокупность, содержавшая большее число

предметов, объединялась в понятие «много». Предметы при счете

сопоставлялись обычно с пальцами рук и ног. По мере развития

цивилизации потребность человека в счете стала необходимой.

Первоначально натуральные числа изображались с помощью

некоторого количества черточек или палочек, затем для их

изображения стали использовать буквы или специальные знаки.

Проведём границу между числом и цифрой. Число – это

некоторая абстрактная сущность для описания количества.

ЦифрыR– это знаки, используемые для записи чисел. Цифры

бывают разные, самыми распространёнными являются арабские

цифры, представляемые известными нам знаками от нуля (0) до

девяти (9); менее распространены римские цифры, мы их можем

иногда встретить на циферблате часов или в обозначении века

(XIX век).

Итак, запомним: число – это некая абстрактная мера

количества, цифра – это знак (рисунок) для записи числа.

Всё множество способов записи чисел с помощью цифр

можно разделить на три части:

1) позиционные системы счисления;

2) смешанные системы счисления;

3) непозиционные системы счисления.

Далее мы рассмотрим широко известные смешанные и

непозиционные системы счисления.

Денежные знаки – это яркий пример смешанной системы

счисления. Сейчас в России используются монеты и купюры

следующих номиналов: 1 коп., 5 коп., 10 коп., 50 коп., 1 руб., 2

руб., 5 руб., 10 руб., 50 руб., 100 руб., 500 руб., 1000 руб. и 5000

руб. Чтобы получить некоторую сумму в рублях, нам нужно

использовать определенное количество денежных знаков

различного достоинства. Предположим, что мы покупаем

пылесос, который стоит 6379 руб. Чтобы расплатиться, нам

потребуется шесть купюр по тысяче рублей, три купюры по сто

рублей, одна пятидесятирублёвая купюра, две десятки, одна

пятирублёвая монета и две монеты по два рубля. Если мы

запишем количество купюр или монет начиная с 1000 руб. и

заканчивая одной копейкой, заменяя нулями пропущенные

номиналы, то мы получим число, представленное в смешанной

системе счисления; в нашем случае – 603121200000.

В непозиционной же системе счисления величина числа не

зависит от положения цифры в представлении числа. Ярким

примером непозиционной системы счисления является римская

система. Не смотря на свой почтенный возраст, данная система

до сих пор используется, хотя и не является общеупотребимой.

1. НЕПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

В непозиционных системах счисления величина, которую

обозначает цифра, не зависит от положения в числе. При этом

система может накладывать ограничения на положение цифр.

С глубокой древности люди повсеместно использовали

непозиционные системы счисления. Для подсчета животных,

населения, запасов использовались различные буквы,

пиктограммы и прочие геометрические фигуры. Со временем

непозиционные системы стали менее популярны и в современном

мире мы встречаем типичного представителя непозиционных

систем – римскую систему счисления, уже скорее как

экзотическое письмо, нежели реально действующую систему.

Причиной отказа от непозиционных систем счисления стало

появление позиционных систем, давших возможность

использовать значительно меньшие цифровые алфавиты для

обозначения даже очень больших чисел и, что еще важнее,

обеспечивающих простое выполнение арифметических операций

над числами.

Далее мы рассмотрим некоторые из существующих

непозиционных систем счисления, уделив особое внимание

широко распространенной римской системе счисления.

1.1. Римская система счисления

Каноническим примером фактически непозиционной

системы счисления является римская система, в которой в

качестве цифр используются латинские буквы:

I обозначает 1, V – 5, X – 10, L – 50, C – 100, D – 500, M –

1000.

Например, II = 1 + 1 = 2, здесь символ I обозначает 1

независимо от места в числе.

Заметьте, что символ нуля в данной системе счисления, как

и в других непозиционных системах, отсутствует за

ненадобностью.

О происхождении римских цифр достоверных сведений нет.

Цифра V могла первоначально служить изображением кисти

руки, а цифра Х могла составиться из двух пятерок. В римской

нумерации явно прослеживаются следы пятеричной системы

счисления.

На самом деле, римская система не является полностью

непозиционной, так как меньшая цифра, идущая перед большей,

вычитается из неё, например:

VI = 6, т.е. 5 + 1, в то время как IV = 4, т.е. 5 – 1;

XL = 40, т.е. 50 – 10, в то время как LX = 60, т.е. 50 + 10.

Подряд одна и та же цифра в римской системе ставится не

более трех раз: LXX = 70; LXXX = 80; число 90 записывается ХС

(а не LXXXX).

Первые 12 чисел записываются в римских цифрах так: I, II,

III, IV, V, VI, VII, VIII, IX, X, XI, XII.

Другие же числа записываются, например, как: XXVIII = 28;

XXXIX = 39; CCCXCVII = 397; MDCCCXVIII = 1818.

Задавшись вопросом о том, сколько же чисел можно

записать в римской системе, мы быстро обнаружим, что их

диапазон простирается от 1 (I) до 3999 (MMMCMXCIX). Столь

узкий диапазон чисел серьезно ограничивает применение

системы в современной жизни, где счет идет на миллионы.

Сейчас римской системой счисления пользуются для

обозначения юбилейных дат, нумерации некоторых страниц

книги (например, страниц предисловия), глав в книгах, строф в

стихотворениях и т.д.

1.2. Система остаточных классов (СОК)

Представление числа в системе остаточных классов

основано на понятии вычета и китайской теореме об остатках.

СОК определяется набором взаимно простых модулей

),,,(

21 n

mmm 

с произведением

mmmM  

так, что каждому

целому числу x из отрезка [0,RM-1] ставится в соответствие набор

вычетов

),,,(

21 n

xxx 

, где

).mod(

);mod(

mxx





При этом китайская теорема об остатках гарантирует

однозначность представления для чисел из отрезка [0,RM-1].

В СОК арифметические операции (сложение, вычитание,

умножение, деление) выполняются покомпонентно, если про

результат известно, что он является целочисленным, а также

лежит в [0,RM-1].

Недостатками СОК является возможность представления

только ограниченного количества чисел, а также отсутствие

эффективных алгоритмов для сравнения чисел, представленных в

СОК. Сравнение обычно осуществляется через перевод

аргументов из СОК в смешанную систему счисления по

основаниям

),,,(

121211 



mmmmmm 

Формула перевода чисел из СОК в десятичную систему

счисления имеет вид:

PrBaBaBaA

 

2211

, где

aaa ,,,



- представление

числа A в СОК с основаниями

ppp ,,,



;

pppP  

;

,2,1,0r

– (целые числа), причём r выбирают так, чтобы

разность между левой и правой частью выражения была меньше

B 















, где

pk ,,2,1 

, причём

выбирается таким,

чтобы остаток от деления

был равен 1.

Пример.

)6,4,2(A

в системе с основаниями:

p

105753

321

 pppP

;15115

105

;21121

105

;70235

105



104105314105156214702  rrA

, где r=2.

1.3. Система счисления Штерна-Броко

Система счисления Штерна-Броко – способ записи

положительных рациональных чисел, основанный на дереве

Штерна-Броко.

Дерево Штерна-Броко – способ расположения всех

неотрицательных несократимых дробей в вершинах

упорядоченного бесконечного двоичного дерева. В дереве

Штерна-Броко дробь

является корнем, а все прочие узлы

заполняются по следующему алгоритму: каждая вершина

имеет двух потомков – левого

nm 

и правого



Начальный кусок дерева Штерна-Броко представлен на

рисунке 1.

Дерево Штерна-Броко обладает следующими

отличительными свойствами:

1) все дроби в дереве Штерна-Броко несократимы;

2) каждая несократимая дробь появляется в дереве;

3) каждая несократимая дробь появляется ровно один раз.

Эти свойства легко доказываются, если заметить, что

каждому шагу по дереву в направлении к корню соответствует

элементарный шаг вычитания меньшего числа из большего в

алгоритме Евклида для поиска наибольшего общего делителя.

Возвратимся к системе счисления Штерна-Броко. Если

воспользоваться символами L и R для идентификации левой и

правой ветви дерева Штерна-Броко при продвижении вниз по

дереву от корня (дроби

) к некоторой определённой дроби.

Тогда каждая положительная дробь получает единственное

представление в виде строки состоящей из символов "R" и "L"

(дроби

соответствует пустая строка). Такое представление

положительных рациональных чисел и называется системой

счисления Штерна-Броко.

Например, обозначение LRRL соответствует дроби

, а

RLLR соответствует дроби

Рисунок 1 - Фрагмент дерева Штерна-Броко

2. СМЕШАННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

Смешанная система счисления является обобщением b-

ричной системы счисления и также зачастую относится к

позиционным системам счисления. Основанием смешанной

системы счисления является возрастающая последовательность

чисел

 



0k

и каждое число x представляется как линейная

комбинация:







bax

где на коэффициенты

(называемые как и прежде цифрами)

накладываются некоторые ограничения.

Записью числа x в смешанной системе счисления называется

перечисление его цифр в порядке уменьшения индекса k, начиная

с первого ненулевого.

Если

bb 

для некоторого b, то смешанная система

счисления совпадает с b-ричной системой счисления.

Наиболее известным примером смешанной системы

счисления является представление времени в виде количества

суток, часов, минут и секунд. При этом величина d дней h часов

m минут s секунд соответствует значению

smhd  606060606024

секунд.

Рассмотрим далее наиболее распространенные смешанные

системы счисления.

2.1. Система счисления майя

Майя использовали 20-ричную систему счисления за одним

исключением: во втором разряде было не 20, а 18 ступеней, то

есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было

сделано для облегчения расчётов календарного цикла, поскольку

(1)(0)(0) = 360 примерно равно числу дней в солнечном году.

2.2. Факториальная система счисления

Профессиональный интерес для специалистов в области

численного анализа представляют факториальная и

фибоначчиева системы, строящиеся на основе разложения

(линейной комбинации)







kfdx

)(

где коэффициенты

(называемые как и прежде цифрами)

устанавливаются в некотором диапазоне, а основание является

функцией от номера разряда в изображении числа.

Факториальная система счисления строится на основании

факториалов k! =1



…



(k-1)



k. Учитывая, что

1! =1, 2! =2, 3! =6, 4! =24, 5! =120, 6! =720 …,

можем записать число

137=1120+024+26+22+11=1(5!)+0(4!)+2(3!)+2(2!)+1(1!)

в виде 137=10221

fact

(для факториальной системы цифры

принимают значение в диапазоне от 0 до k).

Очевидно, что эта система служит для компактного

представления очень больших чисел - 20! ~ 2,432910

2.3. Фибоначчиева система счисления

Система, основанная на числах Фибоначчи (ее цифры равны

0 и 1), служит той же цели, что и факториальная система. Однако