Система счисления
Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков.
Система счисления:
- даёт представления множества чисел (целых и/или вещественных);
- даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
- отражает алгебраическую и арифметическую структуру чисел.
Системы счисления подразделяются на:
- позиционные;
- непозиционные;
- смешанные.
Позиционные системы счисления
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у арабов.
Под позиционной системой счисления обычно понимается -ичная система счисления, которая определяется целым числом , называемым «основанием» системы счисления. Целое число без знака в -ичной системе счисления представляется в виде конечной линейной комбинации степеней числа :
- , где — это целые числа, называемые «цифрами», удовлетворяющие неравенству .
Каждая степень в такой записи называется «весовым коэффициентом разряда». Старшинство разрядов и соответствующих им цифр определяется значением показателя (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число записывают в виде последовательности его -ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:
Например, число сто три представляется в десятичной системе счисления в виде:
Наиболее часто употребляемыми в настоящее время позиционными системами являются:
- 2 — двоичная (в дискретной математике, информатике, программировании);
- 3 — троичная;
- 4 — четверичная[1] (кватричная)[2];
- 5 — пятиричная[3];
- 8 — восьмеричная;
- 10 — десятичная (используется повсеместно);
- 12 — двенадцатеричная (счёт дюжинами);
- 16 — шестнадцатеричная (используется в программировании, информатике);
- 20 — двадцатеричная;
- 60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).
В позиционных системах чем больше основание системы счисления, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.
Смешанные системы счисления
Смешанная система счисления является обобщением -ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел , и каждое число в ней представляется как линейная комбинация:
- , где на коэффициенты , называемые как и прежде «цифрами», накладываются некоторые ограничения.
Записью числа в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса , начиная с первого ненулевого.
В зависимости от вида как функции от смешанные системы счисления могут быть степенными, показательными. Когда для некоторого , смешанная система счисления совпадает с показательной -ичной системой счисления.
Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « дней, часов, минут, секунд» соответствует значению секунд.
Факториальная система счисления
В факториальной системе счисления основаниями являются последовательность факториалов , и каждое натуральное число представляется в виде:
- , где .
Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе будет обозначать число инверсий для элемента в том множестве, в котором производятся перестановки (число элементов меньших , но стоящих правее его в искомой перестановке).
Пример: рассмотрим множество перестановок из пяти элементов, всего их — 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:
положим — коэффициент при числе , тогда , , , , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4). Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.
Фибоначчиева система счисления
Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число в ней представляется в виде:
- , где — числа Фибоначчи, , при этом в коэффициентах есть конечное количество единиц и не встречаются две единицы подряд.
Непозиционные системы счисления
В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения в числе. При этом система может накладывать ограничения на положение цифр, например, чтобы они были расположены в порядке убывания.
К наиболее распространённым сегодня непозиционным системам счисления относятся римские цифры.
Биномиальная система счисления
В биномиальной системе счисления[англ.] число x представляется в виде суммы биномиальных коэффициентов:
- , где
При всяком фиксированном значении каждое натуральное число представляется уникальным образом[4].
Система остаточных классов (СОК)
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей с произведением так, что каждому целому числу из отрезка ставится в соответствие набор вычетов , где
- …
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка .
В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в .
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям .
Система счисления Штерна-Броко
Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.
См. также
- История математики
- Системы записи чисел
- Алфавитная запись чисел
- Число
- Счёты
- Логарифмическая система счисления
Примечания
- ↑ девять // Этимологический словарь русского языка = Russisches etymologisches Wörterbuch : в 4 т. / авт.-сост. М. Фасмер ; пер. с нем. и доп. чл.‑кор. АН СССР О. Н. Трубачёва, под ред. и с предисл. проф. Б. А. Ларина [т. I]. — Изд. 2-е, стер. — М. : Прогресс, 1986—1987. «С девяти начинается новый отрезок счёта, в то время как и.-е. *ok̂tōu „восемь“ своей формой двойств. числа свидетельствует о древнем четверичном счёте»
- ↑ Мод Ривер. Кватричная система счисления // https://7universum.com Universum: технические науки : Научный журнал. — Москва: Изд. «МЦНО», 2021. — 83 (2) (т. Часть 1). — С. 23-26. — ISSN 2311-5122. — doi:10.32743/UniTech.2021.83.2-1.
- ↑ Римская система счёта
- ↑ Ландо С. К. Глава 1. Задача 1.13 // Лекции о производящих функциях. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. (недоступная ссылка)
Ссылки
- Гашков С. Б. Системы счисления и их применение. — М.: МЦНМО, 2004. — (Библиотека «Математическое просвещение»). Архивная копия от 12 января 2014 на Wayback Machine
- Фомин С. В. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике).
- Яглом И. Системы счисления // Квант. — 1970. — № 6. — С. 2—10.
- Цифры и системы счисления. Онлайн Энциклопедия Кругосвет.
- Стахов А. Роль систем счисления в истории компьютеров. Архивировано 1 мая 2009 года.
- Микушин А. В. Системы счисления. Курс лекций «Цифровые устройства и микропроцессоры»
- Butler J. T., Sasao T. Redundant Multiple-Valued Number Systems В статье рассмотрены системы счисления, использующие цифры больше единицы и допускающие избыточность в представлении чисел