Системы счисления
Систе́ма счисле́ния (англ. numeral system или Шаблон:Lang-en2) — символический метод записи чисел, представление чисел с помощью письменных знаков.
Система счисления:
- даёт представления множества чисел (целых и/или вещественных);
- даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
- отражает алгебраическую и арифметическую структуру чисел.
Системы счисления подразделяются на:
- позиционные (англ. positional system, Шаблон:Lang-en2);
- непозиционные;
- смешанные.
Содержание |
Позиционные системы счисления 
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у арабов.
Под позиционной системой счисления обычно понимается <math>b</math>-ичная система счисления, которая определяется целым числом <math>b>1</math>, называемым основанием системы счисления. Целое число без знака <math>x</math> в <math>b</math>-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа <math>b</math>:
- <math>x = \sum_{k=0}^{n-1} a_k b^k</math>, где <math>a_k</math> — это целые числа, называемые цифрами, удовлетворяющие неравенству <math>0 \leq a_k \leq (b-1)</math>.
Каждая степень <math>b^k</math> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <math>k</math> (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <math>x</math> записывают в виде последовательности его <math>b</math>-ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:
- <math>x = a_{n-1} a_{n-2}\dots a_0.</math>
Например, число сто три представляется в десятичной системе счисления в виде:
- <math> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</math>
Наиболее часто употребляемыми в настоящее время позиционными системами являются:
- 2 — двоичная (в дискретной математике, информатике, программировании);
- 3 — троичная;
- 8 — восьмеричная;
- 10 — десятичная (используется повсеместно);
- 12 — двенадцатеричная (счёт дюжинами);
- 16 — шестнадцатеричная (используется в программировании, информатике);
- 20 — двадцатеричная;
- 60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).
В позиционных системах чем больше основание системы счисления, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.
Смешанные системы счисления
Смешанная система счисления является обобщением <math>b</math>-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <math>\{b_k\}_{k=0}^{\infty}</math>, и каждое число <math>x</math> в ней представляется как линейная комбинация:
- <math>x = \sum_{k=0}^{n-1} a_{k}b_k</math>, где на коэффициенты <math>a_{k}</math>, называемые как и прежде цифрами, накладываются некоторые ограничения.
Записью числа <math>x</math> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <math>k</math>, начиная с первого ненулевого.
В зависимости от вида <math>b_k</math> как функции от <math>k</math> смешанные системы счисления могут быть степенными, показательными и т. п. Когда <math>b_k=b^k</math> для некоторого <math>b</math>, смешанная система счисления совпадает с показательной <math>b</math>-ичной системой счисления.
Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина «<math>d</math> дней, <math>h</math> часов, <math>m</math> минут, <math>s</math> секунд» соответствует значению <math>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s</math> секунд.
Факториальная система счисления
В факториальной системе счисления основаниями являются последовательность факториалов <math>b_k=k!</math>, и каждое натуральное число <math>x</math> представляется в виде:
- <math>x = \sum_{k=1}^n d_k k!</math>, где <math>0\leq d_k \leq k</math>.
Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе <math>i!</math> будет обозначать число инверсий для элемента <math>i+1 </math> в том множестве, в котором производятся перестановки (число элементов меньших <math>i+1</math>, но стоящих правее его в искомой перестановке).
Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:
- <math>100 = 4!\cdot 4 + 3!\cdot 0 + 2!\cdot 2 + 1!\cdot 0 = 96 + 4;</math>
положим <math>t_i</math> — коэффициент при числе <math>i!</math>, тогда <math>t_4 = 4</math>, <math>t_3 = 0</math>, <math>t_2 = 2</math>, <math>t_1 = 0</math>, тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.
Фибоначчиева система счисления
Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число <math>n</math> в ней представляется в виде:
- <math>n = \sum_{k} f_k F_k</math>, где <math>F_k</math> — числа Фибоначчи, <math>f_k\in\{0,1\}</math>, при этом в коэффициентах <math>f_k</math> есть конечное количество единиц и не встречаются две единицы подряд.
Непозиционные системы счисления
В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения в числе. При этом система может накладывать ограничения на положение цифр, например, чтобы они были расположены в порядке убывания.
К наиболее распространённым сегодня непозиционным системам счисления относятся римские цифры.
Биномиальная система счисления
В Шаблон:Не переведено число x представляется в виде суммы биномиальных коэффициентов:
- <math>x = \sum_{k=1}^n {c_k\choose k}</math>, где <math>0\leq c_1 < c_2 < \dots < c_n.</math>
При всяком фиксированном значении <math>n</math> каждое натуральное число представляется уникальным образом.
Система остаточных классов (СОК)
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей <math>(m_1, m_2, \dots, m_n)</math> с произведением <math>M=m_1\cdot m_2\cdot \dots\cdot m_n</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,M-1]</math> ставится в соответствие набор вычетов <math>(x_1, x_2, \dots, x_n)</math>, где
- <math>x \equiv x_1 \pmod{m_1};</math>
- <math>x \equiv x_2 \pmod{m_2};</math>
- …
- <math>x \equiv x_n \pmod{m_n}.</math>
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка <math>[0,M-1]</math>.
В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в <math>[0,M-1]</math>.
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям <math>(m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1})</math>.
Система счисления Штерна-Броко
Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.
