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

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

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

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

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

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

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

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

[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]a_{n-1}[/math] в b-ричном представлении [math]x[/math] была также ненулевой.

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

[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]

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

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

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

Смешанная система счисления (англ. mixed radix numeral systems) является обобщением [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] как функции от k смешанные системы счисления могут быть степенными, показательными и т. п. Когда [math]b_k=b^k[/math] для некоторого [math]b[/math], показательная смешанная система счисления совпадает с [math]b[/math]-ричной системой счисления.

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

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

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

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

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

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

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

Теорема Цекендорф (англ. Zeckendorf's theorem)

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]