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

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

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

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

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

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

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

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

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

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

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

${\displaystyle x=a_{n-1}a_{n-2}\dots a_{0}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К наиболее распространённым сегодня непозиционным системам счисления относятся римские цифры .

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

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

${\displaystyle x=\sum _{k=1}^{n}{c_{k} \choose k}}$ , где ${\displaystyle 0\leq c_{1}<c_{2}<\dots <c_{n}.}$

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

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

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

${\displaystyle x\equiv x_{1}{\pmod {m_{1}}};}$

${\displaystyle x\equiv x_{2}{\pmod {m_{2}}};}$

…

${\displaystyle x\equiv x_{n}{\pmod {m_{n}}}.}$

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

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

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

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

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

См. также

• История математики
• Алфавитная запись чисел
• Число
• Счёты
• Логарифмическая система счисления

Примечания

Ссылки

• Гашков С. Б. . — М. : МЦНМО , 2004. — ( Библиотека «Математическое просвещение» ). от 12 января 2014 на Wayback Machine
• Фомин С. В. . — М. : Наука, 1987. — 48 с. — ( Популярные лекции по математике ).
• Яглом И. // Квант . — 1970. — № 6 . — С. 2—10 .
• . Онлайн Энциклопедия Кругосвет.
• Стахов А. . 1 мая 2009 года.
• Микушин А. В. Системы счисления. Курс лекций «Цифровые устройства и микропроцессоры»
• Butler J. T., Sasao T. В статье рассмотрены системы счисления, использующие цифры больше единицы и допускающие избыточность в представлении чисел