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

Определение:

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

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

В позиционных системах счисления (англ. positional numeral systems) один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.

Под позиционной системой счисления обычно понимается b-ичная система счисления, которая определяется целым числом $b\gt 1$, называемым основанием системы счисления.

Запись числа в b-ичной системе счисления

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

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

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

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

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

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

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

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

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

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

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

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

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

В зависимости от вида $b_k$ как функции от $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\ $$\ $ секунд.

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

Определение:

Последовательность чисел Фибоначчи $\left\{F_n\right\}$ задается линейным рекуррентным соотношением: $F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.$

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

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

Таким образом, любое неотрицательное целое число $a = 0,\ 1,\ 2,\ldots$ можно единственным образом представить через последовательность битов …ε_k…ε₄ε₃ε₂: $a = \sum\limits_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}$, причём последовательность {ε_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: $\forall k \geqslant 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)$. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Теорема (Цекендорф):

Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

Доказательство:

$\triangleright$

Доказательство существования легко провести по индукции. Любое целое число $a \geqslant 1$ попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого $n \geqslant 2$ верно неравенство: $F_n \leqslant a \lt F_{n+1}$. Таким образом, $a = F_n + a'$, где $a'=a-F_n\ \lt \ F_{n-1}$, так что разложение числа $a'$ уже не будет содержать слагаемого $F_{n-1}$.

$\triangleleft$

См. также

• Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
• Разложение на множители (факторизация)

Источники информации

• Системы счисления
• Фибоначчиева система счисления
• Теорема Цекендорфа