WikiSort.ru - Не сортированное

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

В факториальной системе счисления основаниями являются последовательность факториалов ${\displaystyle b_{k}=k!}$ , и каждое натуральное число ${\displaystyle x}$ представляется в виде:

${\displaystyle x=\sum _{k=1}^{n}d_{k}k!}$ , где ${\displaystyle 0\leq d_{k}\leq k}$ .

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

Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:

${\displaystyle 100=4!\cdot 4+3!\cdot 0+2!\cdot 2+1!\cdot 0=96+4;}$

положим ${\displaystyle t_{i}}$  — коэффициент при числе ${\displaystyle i!}$ , тогда ${\displaystyle t_{4}=4}$ , ${\displaystyle t_{3}=0}$ , ${\displaystyle t_{2}=2}$ , ${\displaystyle t_{1}=0}$ , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

Фибоначчиева система счисления

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число ${\displaystyle n}$ в ней представляется в виде:

${\displaystyle n=\sum _{k}f_{k}F_{k}}$ , где ${\displaystyle F_{k}}$  — числа Фибоначчи, ${\displaystyle f_{k}\in \{0,1\}}$ , при этом в коэффициентах ${\displaystyle f_{k}}$ есть конечное количество единиц и не встречаются две единицы подряд.

Биномиальная система счисления

В биномиальной системе счисления (англ.) число x представляется в виде суммы биномиальных коэффициентов:

${\displaystyle x=\sum _{k=1}^{n}{c_{k} \choose k}}$ , где ${\displaystyle 0\leq c_{1}<c_{2}<\dots <c_{n}.}$

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

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей ${\displaystyle (m_{1},m_{2},\dots ,m_{n})}$ с произведением ${\displaystyle M=m_{1}\cdot m_{2}\cdot \dots \cdot m_{n}}$ так, что каждому целому числу ${\displaystyle x}$ из отрезка ${\displaystyle [0,M-1]}$ ставится в соответствие набор вычетов ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ , где

${\displaystyle x\equiv x_{1}{\pmod {m_{1}}};}$

${\displaystyle x\equiv x_{2}{\pmod {m_{2}}};}$

…

${\displaystyle x\equiv x_{n}{\pmod {m_{n}}}.}$

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка ${\displaystyle [0,M-1]}$ .

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в ${\displaystyle [0,M-1]}$ .

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям ${\displaystyle (m_{1},m_{1}\cdot m_{2},\dots ,m_{1}\cdot m_{2}\cdot \dots \cdot m_{n-1})}$ .

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

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

Единичная система счисления

По-видимому, хронологически первая система счисления каждого народа, овладевшего счётом. Натуральное число изображается путём повторения одного и того же знака (чёрточки или точки). Например, чтобы изобразить число 26, нужно провести 26 чёрточек (или сделать 26 засечек на кости, камне и т. д.). Впоследствии, ради удобства восприятия больших чисел, эти знаки группируются по три или по пять. Затем равнообъёмные группы знаков начинают заменяться каким-либо новым знаком — так возникают прообразы будущих цифр.

Древнеегипетская система счисления

Древнеегипетская десятичная непозиционная система счисления возникла во второй половине третьего тысячелетия до н. э. Для обозначения чисел 1, 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷ использовались специальные цифры. Числа в египетской системе счисления записывались как комбинации этих цифр, в которых каждая из цифр повторялась не более девяти раз. Значение числа равно простой сумме значений цифр, участвующих в его записи.^[2]

Вавилонская система счисления

Алфавитные системы счисления

Алфавитными системами счисления пользовались древние армяне, грузины, греки (ионическая система счисления), арабы (абджадия), евреи (см. гематрия), индийцы (акшара-санкхья) и другие народы Ближнего Востока. В славянских богослужебных книгах греческая алфавитная система была переведена на буквы кириллицы.^[2]

Греческая система счисления

Основная статья: Греческая система счисления

Греческая система счисления, также известная как ионийская или новогреческая — непозиционная система счисления. Алфавитная запись чисел, в которой в качестве символов для счёта, употребляют буквы классического греческого алфавита, а также некоторые буквы доклассической эпохи, такие как ϛ (стигма), ϟ (коппа) и ϡ (сампи).

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Римская система счисления

Каноническим примером почти непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000

Например, II = 1 + 1 = 2
здесь символ I обозначает 1 независимо от места в числе.

На самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:

IV = 4, в то время как:
VI = 6

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

Майя использовали 20-ичную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

Для записи основными знаками были точки (единицы) и отрезки (пятёрки).

Кипу инков

Прообразом баз данных, широко использовавшихся в Центральных Андах (Перу, Боливия) в государственных и общественных целях в I—II тысячелетии н. э., была узелковая письменность Инков — кипу, состоявшая как из числовых записей десятичной системы^[3], так и не числовых записей в двоичной системе кодирования^[4]. В кипу применялись первичные и дополнительные ключи, позиционные числа, кодирование цветом и образование серий повторяющихся данных^[5]. Кипу впервые в истории человечества использовалось для применения такого способа ведения бухгалтерского учёта как двойная запись^[6].