Системы счисления — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метки: правка с мобильного устройства, правка из мобильной версии)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 3 участников)
Строка 5: Строка 5:
 
==Позиционные системы счисления==
 
==Позиционные системы счисления==
  
В позиционных системах счисления (англ. ''positional numeral systems'') один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.
+
В '''позиционных системах счисления''' (англ. ''positional numeral systems'') один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.
  
Под позиционной системой счисления обычно понимается ''b''-ричная система счисления, которая определяется [https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE целым числом] <tex>b>1</tex>, называемым основанием системы счисления.
+
Под позиционной системой счисления обычно понимается ''b''-ичная система счисления, которая определяется [https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE целым числом] <tex>b>1</tex>, называемым основанием системы счисления.
  
 
===Запись числа в ''b''-ичной системе счисления===
 
===Запись числа в ''b''-ичной системе счисления===
  
 
Целое число ''x'' в ''b''-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа ''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>x = \sum\limits_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leqslant a_k \leqslant (b-1)</tex>.
 
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой.
 
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой.
  
Строка 21: Строка 21:
  
 
Наиболее употребляемыми в настоящее время позиционными системами являются:
 
Наиболее употребляемыми в настоящее время позиционными системами являются:
* 1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);
+
* <tex>1</tex> — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);
* 2 — двоичная (в дискретной математике, информатике, программировании);
+
* <tex>2</tex> — двоичная (в дискретной математике, информатике, программировании);
* 8 — восьмеричная;
+
* <tex>8</tex> — восьмеричная;
* 10 — десятичная (используется повсеместно);
+
* <tex>10</tex> — десятичная (используется повсеместно);
* 12 — двенадцатеричная (счёт дюжинами);
+
* <tex>12</tex> — двенадцатеричная (счёт дюжинами);
* 16 — шестнадцатеричная (используется в программировании, информатике).
+
* <tex>16</tex> — шестнадцатеричная (используется в программировании, информатике).
  
 
==Смешанные системы счисления==
 
==Смешанные системы счисления==
  
 
'''Смешанная система счисления''' (англ. ''mixed radix numeral systems'') является обобщением <tex>b</tex>-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:
 
'''Смешанная система счисления''' (англ. ''mixed radix numeral systems'') является обобщением <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 = \sum\limits_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.
 
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.
 
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.
  
Строка 48: Строка 48:
 
'''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи].
 
'''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи].
  
: <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}\ldots  f_0</tex> не встречается две единицы подряд.
+
: <tex>x = \sum\limits_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\ldots  f_0</tex> не встречается две единицы подряд.
  
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\ldots  </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.
+
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\ldots  </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum\limits_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k \geqslant  2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.
 
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
 
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
  
==Теорема Цекендорфа (англ. ''Zeckendorf's theorem'')==
 
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 +
|author=Цекендорф
 
|statement=
 
|statement=
 
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
 
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
 
|proof=
 
|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>.
+
Доказательство существования легко провести по индукции. Любое целое число <tex>a \geqslant  1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n \geqslant  2</tex> верно неравенство: <tex>F_n \leqslant 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>.
 
}}
 
}}
  
Строка 67: Строка 67:
  
 
== Источники информации ==
 
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/ Системы счисления]
+
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F Системы счисления]
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/ Фибоначчиева система счисления]
+
* [https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F Фибоначчиева система счисления]
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A6%D0%B5%D0%BA%D0%B5%D0%BD%D0%B4%D0%BE%D1%80%D1%84%D0%B0/ Теорема Цекендорфа]
+
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A6%D0%B5%D0%BA%D0%B5%D0%BD%D0%B4%D0%BE%D1%80%D1%84%D0%B0 Теорема Цекендорфа]
 +
 
 +
[[Категория: Теория чисел]]

Текущая версия на 19:43, 4 сентября 2022

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

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

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

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

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

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

[math]x = \sum\limits_{k=0}^{n-1} a_k b^k[/math], где [math]a_k[/math] — это целые числа, называемые цифрами, удовлетворяющие неравенству [math]0 \leqslant a_k \leqslant (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]

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

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

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

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

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

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

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

Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина [math]d[/math] дней, [math]h[/math] часов, [math]m[/math] минут, [math]s[/math] секунд соответствует значению [math]d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s\ [/math][math]\ [/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\limits_{k=0}^n f_k F_k[/math], где [math]F_k[/math] — числа Фибоначчи, [math]f_k\in\{0,1\}[/math], при этом в записи [math]f_nf_{n-1}\ldots f_0[/math] не встречается две единицы подряд.

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

Теорема (Цекендорф):
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство:
[math]\triangleright[/math]
Доказательство существования легко провести по индукции. Любое целое число [math]a \geqslant 1[/math] попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого [math]n \geqslant 2[/math] верно неравенство: [math]F_n \leqslant 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]

См. также

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