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

2011-02-28T00:28:50Z

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

{{Определение
|definition=
'''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков.
}}

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

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

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

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

Целое число ''x'' в ''b''-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq a_k \leq (b-1)</tex>.
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ричном представлении <tex>x</tex> была также ненулевой.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex>
Например, число ''сто три'' представляется в десятичной системе счисления в виде:
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex>

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

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

'''Смешанная система счисления''' является обобщением <tex>b</tex>-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:
: <tex>x = \sum_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.

В зависимости от вида <tex>b_k</tex> как функции от ''k'' смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ричной системой счисления.

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

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

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

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

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

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

{{Теорема
|id=th1
|author=Цекендорф
|statement=
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
|proof=
Доказательство существования легко провести по индукции. Любое целое число <tex>a\ge 1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n\ge 2</tex> верно неравенство: <tex>F_n \le a < F_{n+1}</tex>. Таким образом, <tex>a = F_n + a'</tex>, где <tex>a'=a-F_n\ <\ F_{n-1}</tex>, так что разложение числа <tex>a'</tex> уже не будет содержать слагаемого <tex>F_{n-1}</tex>.
}}

Викиконспекты - Вклад участника [ru]

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