Virtual Laboratory Wiki
Advertisement

Систе́ма счисле́ниясимволический метод записи чисел, представление чисел с помощью письменных знаков. Системы счисления подразделяются на позиционные, непозиционные и смешанные.

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

Основная статья Позиционная система счисления.

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман.

Каждая позиционная система счисления определяется некоторым числом (т. н. основание системы счисления) таким, что единиц в каждом разряде объединяются в одну единицу следующего по старшинству разряда. Система счисления с основанием также называется 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-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

Например, число сто три представляется в десятичной системе счисления в виде:

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

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

Смешанная система счисления является обобщением -ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел и каждое число представляется как линейная комбинация:

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

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

Если для некоторого , то смешанная система счисления совпадает с -ричной системой счисления.

Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина 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.

Система счисления Штерна-Броко

Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.

См. также

Ссылки



Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Система счисления. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Advertisement