Система счисления


Система счисления (англ. numeral system или system of numeration) — символический метод записи чисел, представление чисел с помощью письменных знаков.

Система счисления:

  • даёт представления множества чисел (целых и/или вещественных);
  • даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
  • отражает алгебраическую и арифметическую структуру чисел.

Системы счисления подразделяются на:

  • позиционные (англ. positional system, place-value notation);
  • непозиционные;
  • смешанные.

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

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у арабов.

Под позиционной системой счисления обычно понимается b {displaystyle b} -ичная система счисления, которая определяется целым числом b > 1 {displaystyle b>1} , называемым основанием системы счисления. Целое число без знака x {displaystyle x} в b {displaystyle b} -ичной системе счисления представляется в виде конечной линейной комбинации степеней числа b {displaystyle b} :

x = ∑ k = 0 n − 1 a k b k {displaystyle x=sum _{k=0}^{n-1}a_{k}b^{k}} , где a k {displaystyle a_{k}} — это целые числа, называемые цифрами, удовлетворяющие неравенству 0 ≤ a k ≤ ( b − 1 ) {displaystyle 0leq a_{k}leq (b-1)} .

Каждая степень b k {displaystyle b^{k}} в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя k {displaystyle k} (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число x {displaystyle x} записывают в виде последовательности его b {displaystyle b} -ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

x = a n − 1 a n − 2 … a 0 . {displaystyle x=a_{n-1}a_{n-2}dots a_{0}.}

Например, число сто три представляется в десятичной системе счисления в виде:

103 = 1 ⋅ 10 2 + 0 ⋅ 10 1 + 3 ⋅ 10 0 . {displaystyle 103=1cdot 10^{2}+0cdot 10^{1}+3cdot 10^{0}.}

Наиболее часто употребляемыми в настоящее время позиционными системами являются:

  • 2 — двоичная (в дискретной математике, информатике, программировании);
  • 3 — троичная;
  • 8 — восьмеричная;
  • 10 — десятичная (используется повсеместно);
  • 12 — двенадцатеричная (счёт дюжинами);
  • 16 — шестнадцатеричная (используется в программировании, информатике);
  • 20 — двадцатеричная;
  • 60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

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

Смешанные системы счисления

Смешанная система счисления является обобщением b {displaystyle b} -ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел { b k } k = 0 ∞ {displaystyle {b_{k}}_{k=0}^{infty }} , и каждое число x {displaystyle x} в ней представляется как линейная комбинация:

x = ∑ k = 0 n − 1 a k b k {displaystyle x=sum _{k=0}^{n-1}a_{k}b_{k}} , где на коэффициенты a k {displaystyle a_{k}} , называемые как и прежде цифрами, накладываются некоторые ограничения.

Записью числа x {displaystyle x} в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k {displaystyle k} , начиная с первого ненулевого.

В зависимости от вида b k {displaystyle b_{k}} как функции от k {displaystyle k} смешанные системы счисления могут быть степенными, показательными и т. п. Когда b k = b k {displaystyle b_{k}=b^{k}} для некоторого b {displaystyle b} , смешанная система счисления совпадает с показательной b {displaystyle b} -ичной системой счисления.

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « d {displaystyle d} дней, h {displaystyle h} часов, m {displaystyle m} минут, s {displaystyle s} секунд» соответствует значению d ⋅ 24 ⋅ 60 ⋅ 60 + h ⋅ 60 ⋅ 60 + m ⋅ 60 + s {displaystyle dcdot 24cdot 60cdot 60+hcdot 60cdot 60+mcdot 60+s} секунд.

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

В факториальной системе счисления основаниями являются последовательность факториалов b k = k ! {displaystyle b_{k}=k!} , и каждое натуральное число x {displaystyle x} представляется в виде:

x = ∑ k = 1 n d k k ! {displaystyle x=sum _{k=1}^{n}d_{k}k!} , где 0 ≤ d k ≤ k {displaystyle 0leq d_{k}leq k} .

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе i ! {displaystyle i!} будет обозначать число инверсий для элемента i + 1 {displaystyle i+1} в том множестве, в котором производятся перестановки (число элементов меньших i + 1 {displaystyle i+1} , но стоящих правее его в искомой перестановке).

Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:

100 = 4 ! ⋅ 4 + 3 ! ⋅ 0 + 2 ! ⋅ 2 + 1 ! ⋅ 0 = 96 + 4 ; {displaystyle 100=4!cdot 4+3!cdot 0+2!cdot 2+1!cdot 0=96+4;}

положим t i {displaystyle t_{i}} — коэффициент при числе i ! {displaystyle i!} , тогда t 4 = 4 {displaystyle t_{4}=4} , t 3 = 0 {displaystyle t_{3}=0} , t 2 = 2 {displaystyle t_{2}=2} , t 1 = 0 {displaystyle t_{1}=0} , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

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

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число n {displaystyle n} в ней представляется в виде:

n = ∑ k f k F k {displaystyle n=sum _{k}f_{k}F_{k}} , где F k {displaystyle F_{k}} — числа Фибоначчи, f k ∈ { 0 , 1 } {displaystyle f_{k}in {0,1}} , при этом в коэффициентах f k {displaystyle f_{k}} есть конечное количество единиц и не встречаются две единицы подряд.

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

В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения в числе. При этом система может накладывать ограничения на положение цифр, например, чтобы они были расположены в порядке убывания.

Биномиальная система счисления

В биномиальной системе счисления число x представляется в виде суммы биномиальных коэффициентов:

x = ∑ k = 1 n ( c k k ) {displaystyle x=sum _{k=1}^{n}{c_{k} choose k}} , где 0 ≤ c 1 < c 2 < ⋯ < c n . {displaystyle 0leq c_{1}<c_{2}<dots <c_{n}.}

При всяком фиксированном значении n {displaystyle n} каждое натуральное число представляется уникальным образом.

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей ( m 1 , m 2 , … , m n ) {displaystyle (m_{1},m_{2},dots ,m_{n})} с произведением M = m 1 ⋅ m 2 ⋅ ⋯ ⋅ m n {displaystyle M=m_{1}cdot m_{2}cdot dots cdot m_{n}} так, что каждому целому числу x {displaystyle x} из отрезка [ 0 , M − 1 ] {displaystyle [0,M-1]} ставится в соответствие набор вычетов ( x 1 , x 2 , … , x n ) {displaystyle (x_{1},x_{2},dots ,x_{n})} , где

x ≡ x 1 ( mod m 1 ) ; {displaystyle xequiv x_{1}{pmod {m_{1}}};} x ≡ x 2 ( mod m 2 ) ; {displaystyle xequiv x_{2}{pmod {m_{2}}};} … x ≡ x n ( mod m n ) . {displaystyle xequiv x_{n}{pmod {m_{n}}}.}

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [ 0 , M − 1 ] {displaystyle [0,M-1]} .

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [ 0 , M − 1 ] {displaystyle [0,M-1]} .

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям ( m 1 , m 1 ⋅ m 2 , … , m 1 ⋅ m 2 ⋅ ⋯ ⋅ m n − 1 ) {displaystyle (m_{1},m_{1}cdot m_{2},dots ,m_{1}cdot m_{2}cdot dots cdot m_{n-1})} .

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

Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru ©
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!