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

Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков. Системы счисления подразделяются на позиционные, непозиционные и смешанные.

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

Основная статья Позиционная система счисления.

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

Каждая позиционная система счисления определяется некоторым числом $b > 1$ (т. н. основание системы счисления) таким, что $b$ единиц в каждом разряде объединяются в одну единицу следующего по старшинству разряда. Система счисления с основанием $b$ также называется b-ричной.

Целое число x_a,b в b-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа b:

$x_{a,b} = \sum_{k=0}^{n-1} a_k b^k$, где

k - номер разряда,
n - число разрядов,
a - множество из которого берутся a_k,
$a_k$ — это целые числа, называемые цифрами, удовлетворяющие неравенству $0 \leq a_k < b$,
b - основание весовой показательной функции f(k)=b^k,
b^k - весовая показательная функция f(k)=b^k.

Каждая степень $b^k$ в такой записи называется b-ричным разрядом, старшинство разрядов и соответствующих им цифр определяется значением показателя $k$. Обычно для ненулевого числа $x_{a,b}$ требуют, чтобы старшая цифра $a_{n-1}$ в b-ричном представлении $x_{a,b}$ была также ненулевой.

Из комбинаторики известно, что число записываемых кодов (чисел) не зависит от основания показательной функции — b, которое определяет диапазон представляемых числами x_a,b величин, и равно числу размещений с повторениями:

$\bar{A}(a,n)=\bar{A}_a^n=a^n,$ где

a — множество из которого берутся цифры a_k,
n — число элементов (цифр) в числе x_a,b.

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

$x_{a,b} = a_{n-1} a_{n-2}\dots a_0.$

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

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

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

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

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

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

$x = \sum_{k=0}^n a_{k}b_k$, где на коэффициенты $a_k$ (называемые как и прежде цифрами) накладываются некоторые ограничения.

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

Если $b_k=b^k$ для некоторого $b$, то смешанная система счисления совпадает с $b$-ричной системой счисления.

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

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

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

$x = \sum_{k=0}^n f_k F_k$, где $F_k$ — числа Фибоначчи, $f_k\in\{0,1\}$, при этом в записи $f_nf_{n-1}\dots f_0$ не встречается две единицы подряд.

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

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

$x = \sum_{k=1}^n d_k k!$, где $0\leq d_k \leq k$.

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

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

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

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

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

Представление, использующее биномиальные коэффициенты

$x = \sum_{k=1}^n {c_k\choose k}$, где $0\leq c_1 < c_2 < \dots < c_n$.

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

Каноническим примером фактически непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000

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

На самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:

IV = 4, в то время как:
VI = 6

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей $(m_1, m_2, \dots, m_n)$ с произведением $M=m_1\cdot m_2\cdot \dots\cdot m_n$ так, что каждому целому числу $x$ из отрезка $[0,M-1]$ ставится в соответствие набор вычетов $(x_1, x_2, \dots, x_n)$, где

$x \equiv x_1 \pmod{m_1};$

$x \equiv x_2 \pmod{m_2};$

…

$x \equiv x_n \pmod{m_n}.$

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

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

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

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

Формула перевода имеет вид:

A = a₁*B₁+a₂*B₂+…+a_n*B_n-r*P, где a₁, …, a_n - представление числа А в СОК с основаниями p₁, p₂, …, p_n;

P = p₁* p₂* …* p_n;

r = 0,1,2,… (целые числа), причём r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;

B_i = (P/p_i)*k_i, где k_i = 1, 2, …, p_i, причём k_i выбирается таким, чтобы остаток от деления B_i/p_i был равен 1.

Пример.

А = (2,4,6) в системе с основаниями: p₁ = 3, p₂ = 5, p₃ = 7.

P = p₁*p₂*p₃ = 3*5*7 = 105.

B₁ = 105/3*k₁ = 35*2 =70;

B₂ = 105/5*k₂ = 21*1 =21;

B₃ = 105/7*k₃ = 15*1 =15;

A = 2*70+4*21+6*15 - r*105;

A = 314 - r*105 = 104, где r=2.

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

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

См. также

• Числа

Ссылки

• Л. Н. Беляева., «Системы счисления и признаки делимости».
• С. Б. Гашков. Системы счисления и их применение, Серия "Библиотека «Математическое просвещение»", выпуск 29, 2004.
• С. В. Фомин, «Системы счисления». «Популярные лекции по математике», выпуск 40, М., «Наука» 1987 г., 48 стр.
• Яглом И., «Системы счисления», Квант, № 6, 1970.
• Системы остаточных классов, модулярные ЭВМ
• SZTAKI Desktop Grid
• «Скрипт для работы с системами счисления».

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Система счисления. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---