Системы счисления — различия между версиями
Senya (обсуждение | вклад) (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показано 19 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков. | + | '''Систе́ма счисле́ния''' (англ. ''numeral system'' или ''system of numeration'') — символический метод записи чисел, представление чисел с помощью письменных знаков. |
}} | }} | ||
==Позиционные системы счисления== | ==Позиционные системы счисления== | ||
− | В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. | + | В '''позиционных системах счисления''' (англ. ''positional numeral systems'') один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. |
− | Под позиционной системой счисления обычно понимается ''b''- | + | Под позиционной системой счисления обычно понимается ''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''- | + | Целое число ''x'' в ''b''-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'': |
− | : <tex>x = \ | + | : <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>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой. |
− | Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''- | + | Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо: |
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex> | : <tex>x = a_{n-1} a_{n-2}\dots a_0.</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> — шестнадцатеричная (используется в программировании, информатике). |
==Смешанные системы счисления== | ==Смешанные системы счисления== | ||
− | '''Смешанная система счисления''' является обобщением <tex>b</tex>- | + | '''Смешанная система счисления''' (англ. ''mixed radix numeral systems'') является обобщением <tex>b</tex>-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация: |
− | : <tex>x = \ | + | : <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>, начиная с первого ненулевого. | ||
− | В зависимости от вида <tex>b_k</tex> как функции от | + | В зависимости от вида <tex>b_k</tex> как функции от <tex>k</tex> смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ичной системой счисления. |
− | Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина | + | Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина <tex>d</tex> дней, <tex>h</tex> часов, <tex>m</tex> минут, <tex>s</tex> секунд'' соответствует значению <tex>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s\ </tex><tex>\ </tex> секунд. |
==Фибоначчиева система счисления== | ==Фибоначчиева система счисления== | ||
Строка 42: | Строка 42: | ||
{{Определение | {{Определение | ||
|definition= | |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>F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.</tex> | ||
}} | }} | ||
− | '''Фибоначчиева система счисления''' основывается на [ | + | '''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи]. |
− | : <tex>x = \ | + | : <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,\ | + | Таким образом, любое неотрицательное целое число <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>. |
За исключением последнего свойства, данное представление аналогично двоичной системе счисления. | За исключением последнего свойства, данное представление аналогично двоичной системе счисления. | ||
Строка 59: | Строка 59: | ||
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно. | Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно. | ||
|proof= | |proof= | ||
− | Доказательство существования легко провести по индукции. Любое целое число <tex>a\ | + | Доказательство существования легко провести по индукции. Любое целое число <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>. |
}} | }} | ||
+ | |||
+ | == См. также == | ||
+ | *[[Арифметика чисел в b-ичной системе счисления (Длинная арифметика) | Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]] | ||
+ | *[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * [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 Теорема Цекендорфа] | ||
+ | |||
+ | [[Категория: Теория чисел]] |
Текущая версия на 19:43, 4 сентября 2022
Определение: |
Систе́ма счисле́ния (англ. numeral system или system of numeration) — символический метод записи чисел, представление чисел с помощью письменных знаков. |
Позиционные системы счисления
В позиционных системах счисления (англ. positional numeral systems) один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.
Под позиционной системой счисления обычно понимается b-ичная система счисления, которая определяется целым числом , называемым основанием системы счисления.
Запись числа в b-ичной системе счисления
Целое число x в b-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа b:
- , где — это целые числа, называемые цифрами, удовлетворяющие неравенству .
Каждая степень
в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя (номером разряда). Обычно для ненулевого числа требуют, чтобы старшая цифра в b-ичном представлении была также ненулевой.Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число
записывают в виде последовательности его b-ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:Например, число сто три представляется в десятичной системе счисления в виде:
Наиболее употребляемыми в настоящее время позиционными системами являются:
- — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);
- — двоичная (в дискретной математике, информатике, программировании);
- — восьмеричная;
- — десятичная (используется повсеместно);
- — двенадцатеричная (счёт дюжинами);
- — шестнадцатеричная (используется в программировании, информатике).
Смешанные системы счисления
Смешанная система счисления (англ. mixed radix numeral systems) является обобщением
-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел и каждое число представляется как линейная комбинация:- , где на коэффициенты (называемые как и прежде цифрами) накладываются некоторые ограничения.
Записью числа
в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса , начиная с первого ненулевого.В зависимости от вида
как функции от смешанные системы счисления могут быть степенными, показательными и т. п. Когда для некоторого , показательная смешанная система счисления совпадает с -ичной системой счисления.Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина
дней, часов, минут, секунд соответствует значению секунд.Фибоначчиева система счисления
Определение: |
Последовательность чисел Фибоначчи | задается линейным рекуррентным соотношением:
Фибоначчиева система счисления основывается на числах Фибоначчи.
- , где — числа Фибоначчи, , при этом в записи не встречается две единицы подряд.
Таким образом, любое неотрицательное целое число
можно единственным образом представить через последовательность битов …εk…ε4ε3ε2: , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.Теорема (Цекендорф): |
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно. |
Доказательство: |
Доказательство существования легко провести по индукции. Любое целое число | попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, , где , так что разложение числа уже не будет содержать слагаемого .