Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков. Системы счисления подразделяются на позиционные, непозиционные и смешанные.
Позиционные системы счисления
- Основная статья Позиционная система счисления.
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман.
Каждая позиционная система счисления определяется некоторым числом (т. н. основание системы счисления) таким, что единиц в каждом разряде объединяются в одну единицу следующего по старшинству разряда. Система счисления с основанием также называется b-ричной.
Целое число xa,b в b-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа b:
k - номер разряда,
n - число разрядов,
a - множество из которого берутся ak,
— это целые числа, называемые цифрами, удовлетворяющие неравенству ,
b - основание весовой показательной функции f(k)=bk,
bk - весовая показательная функция f(k)=bk.
Каждая степень
в такой записи называется b-ричным разрядом, старшинство разрядов и соответствующих им цифр определяется значением показателя . Обычно для ненулевого числа требуют, чтобы старшая цифра в b-ричном представлении была также ненулевой.Из комбинаторики известно, что число записываемых кодов (чисел) не зависит от основания показательной функции — b, которое определяет диапазон представляемых числами xa,b величин, и равно числу размещений с повторениями:
a — множество из которого берутся цифры ak,
n — число элементов (цифр) в числе xa,b.
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число
записывают в виде последовательности его b-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:Например, число сто три представляется в десятичной системе счисления в виде:
Наиболее употребимыми в настоящее время позиционными системами являются:
- 1 — единичная система счисления (как позиционная, может и не рассматриваться; счёт на пальцах, зарубки, узелки "на память" и др.)
- 2 — двоичная (в дискретной математике, информатике, программировании),
- 3 — троичная система счисления,
- 10 — десятичная система счисления
- 12 — двенадцатиричная система счисления (счёт дюжинами),
- 16 — шестнадцатеричная (наиболее часто используется в программировании, а также в шрифтах)
- 60 — шестидесятиричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты)
Смешанные системы счисления
Смешанная система счисления является обобщением линейная комбинация:
-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел и каждое число представляется как- , где на коэффициенты (называемые как и прежде цифрами) накладываются некоторые ограничения.
Записью числа
в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса , начиная с первого ненулевого.Если
для некоторого , то смешанная система счисления совпадает с -ричной системой счисления.Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина d дней h часов m минут s секунд соответствует значению
секунд.Фибоначчиева система счисления
Фибоначчиева система счисления основывается на числах Фибоначчи.
- , где — числа Фибоначчи, , при этом в записи не встречается две единицы подряд.
Факториальная система счисления
В факториальной системе счисления основаниями является последовательность факториалов , и каждое натуральное число предствляется в виде:
- , где .
Система счисления майя
Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.
Непозиционные системы счисления
В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения в числе. При этом система может накладывать ограничения на положение цифр, например, чтобы они были расположены в порядке убывания.
Биномиальная система счисления
Представление, использующее биномиальные коэффициенты
- , где .
Римская система счисления
Каноническим примером фактически непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000
Например, II = 1 + 1 = 2
здесь символ I обозначает 1 независимо от места в числе.
На самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:
IV = 4, в то время как:
VI = 6
Система остаточных классов (СОК)
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей с произведением так, что каждому целому числу из отрезка ставится в соответствие набор вычетов , где
- …
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка
.В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в
.Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям
.Перевод чисел из СОК в десятичную систему счисления
Формула перевода имеет вид:
A = a1*B1+a2*B2+…+an*Bn-r*P, где a1, …, an - представление числа А в СОК с основаниями p1, p2, …, pn;
P = p1* p2* …* pn;
r = 0,1,2,… (целые числа), причём r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;
Bi = (P/pi)*ki, где ki = 1, 2, …, pi, причём ki выбирается таким, чтобы остаток от деления Bi/pi был равен 1.
Пример.
А = (2,4,6) в системе с основаниями: p1 = 3, p2 = 5, p3 = 7.
P = p1*p2*p3 = 3*5*7 = 105.
B1 = 105/3*k1 = 35*2 =70;
B2 = 105/5*k2 = 21*1 =21;
B3 = 105/7*k3 = 15*1 =15;
A = 2*70+4*21+6*15 - r*105;
A = 314 - r*105 = 104, где r=2.
Система счисления Штерна-Броко
Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.
См. также
Ссылки
- Л. Н. Беляева., «Системы счисления и признаки делимости».
- С. Б. Гашков. Системы счисления и их применение, Серия "Библиотека «Математическое просвещение»", выпуск 29, 2004.
- С. В. Фомин, «Системы счисления». «Популярные лекции по математике», выпуск 40, М., «Наука» 1987 г., 48 стр.
- Яглом И., «Системы счисления», Квант, № 6, 1970.
- Системы остаточных классов, модулярные ЭВМ
- SZTAKI Desktop Grid
- «Скрипт для работы с системами счисления».
Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Система счисления. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .