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

(перенаправлено с «Смешанная система счисления»)

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

Индо-арабская
Арабская
Тамильская
Бирманская
Кхмерская
Лаосская
Монгольская
Тайская
Восточноазиатские
Китайская
Японская
Сучжоу
Корейская
Вьетнамская
Счётные палочки
Алфавитные
Абджадия
Армянская
Ариабхата
Кириллическая
Греческая
Грузинская
Эфиопская
Еврейская
Акшара-санкхья
Другие
Вавилонская
Египетская
Этрусская
Римская
Дунайская
Аттическая
Кипу
Майяская
Эгейская
Символы КППУ
2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 60
Нега-позиционная
Симметричная
Фибоначчиева
Единичная (унарная)

Система счисления:

Системы счисления подразделяются на:

Содержание

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

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

Под позиционной системой счисления обычно понимается  -ичная система счисления, которая определяется целым числом  , называемым основанием системы счисления. Целое число без знака   в  -ичной системе счисления представляется в виде конечной линейной комбинации степеней числа  :

 , где   — это целые числа, называемые цифрами, удовлетворяющие неравенству  .

Каждая степень   в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя   (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число   записывают в виде последовательности его  -ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

 

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

 

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

В позиционных системах чем больше основание системы счисления, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.

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

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

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

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

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

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина «  дней,   часов,   минут,   секунд» соответствует значению   секунд.

Факториальная система счисления

В факториальной системе счисления основаниями являются последовательность факториалов  , и каждое натуральное число   представляется в виде:

 , где  .

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе   будет обозначать число инверсий для элемента   в том множестве, в котором производятся перестановки (число элементов меньших  , но стоящих правее его в искомой перестановке).

Пример: рассмотрим множество перестановок из 5 элементов, всего их 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 представляется в виде суммы биномиальных коэффициентов:

 , где  

При всяком фиксированном значении   каждое натуральное число представляется уникальным образом.[1]

Система остаточных классов (СОК)

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей   с произведением   так, что каждому целому числу   из отрезка   ставится в соответствие набор вычетов  , где

 
 
 

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка  .

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в  .

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям  .

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

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

См. также

Примечания

  1. Ландо С. К. Глава 1. Задача 1.13 // Лекции о производящих функциях. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. (недоступная ссылка)

Ссылки