Биективная нумерация - Bijective numeration

Системы счисления
Индусско-арабская система счисления
Западный арабский Восточно-арабский Бенгальский Деванагари Гуджарати Гурмукхи Одиа Сингальский Тамильский Малаялам телугу Каннада Дзонгка тибетский Балийский Бирманский Яванский Кхмерский Лаосский Монгольский Тайский
Восточная Азия
Китайский Сучжоу Хоккиен Японский Корейский вьетнамский Тангутский Счетные стержни
Европейский
Римский
Американец
Инупиак
По алфавиту
Абджад Армянский Ryabhaa Кириллица Ge'ez Грузинский Греческий иврит
Бывший
Эгейское море Чердак Вавилонский Брахми Чувашский Цистерцианский Египтянин Этрусский Глаголица Харости майя Муиска Pentimal Quipu Доисторический
Позиционные системы к основание
2 3 4 5 6 8 10 12 16 20 60
Нестандартные позиционные системы счисления
Биективная нумерация (1 ) Знаковое представление (Сбалансированный тройной ) смешанный (факториал ) отрицательный Комплексно-базовая система (2я ) Нецелочисленное представление (φ ) Асимметричные системы счисления
Список систем счисления

Биективная нумерация есть ли система счисления в котором каждый неотрицательный целое число можно представить точно одним способом с помощью конечного строка цифр. Название происходит от этого биекция (взаимно однозначное соответствие) между набором неотрицательных целых чисел и набором конечных строк с использованием конечного набора символов («цифр»).

Самые обычные системы счисления, такие как обычная десятичный системы, не являются биективными, потому что более одной строки цифр могут представлять одно и то же положительное целое число. В частности, добавив ведущие нули не изменяет представленное значение, поэтому «1», «01» и «001» представляют собой число один. Несмотря на то, что обычно используется только первое, тот факт, что возможны другие, означает, что десятичное число не является биективным. Тем не мение, унарный, только с одной цифрой, является биективный.

А биективный основание -k нумерация является биективным позиционная запись. Он использует строку цифр из набора {1, 2, ..., k} (куда k ≥ 1) для кодирования каждого положительного целого числа; позиция цифры в строке определяет ее значение как кратное степени k. Смуллян (1961) называет это обозначение k-adic, но его не следует путать с п-адические числа: биективные числа - это система представления обычных целые числа конечными строками ненулевых цифр, тогда как п-адические числа - это система математических значений, которые содержат целые числа как подмножество и могут потребовать бесконечных последовательностей цифр в любом числовом представлении.

Определение

В основание-k биективная система счисления использует набор цифр {1, 2, ..., k} (k ≥ 1) для однозначного представления каждого неотрицательного целого числа следующим образом:

• Целое число ноль представлено пустой строкой.
• Целое число, представленное непустой цифровой строкой

а_па_п−1 ... а₁а₀

является

а_п k^п + а_п−1 k^п−1 + ... + а₁ k¹ + а₀ k⁰.

• Строка цифр, представляющая целое число м > 0 это

а_па_п−1 ... а₁а₀

куда

${ displaystyle { begin {align} a_ {0} & = m-q_ {0} k, & q_ {0} & = f left ({ frac {m} {k}} right) & a_ {1} & = q_ {0} -q_ {1} k, & q_ {1} & = f left ({ frac {q_ {0}} {k}} right) & a_ {2} & = q_ {1} -q_ {2} k, & q_ {2} & = f left ({ frac {q_ {1}} {k}} right) & & , , , vdots && , , , vdots a_ {n} & = q_ {n-1} -0k, & q_ {n} & = f left ({ frac {q_ {n-1}} {k} } right) = 0 end {выровнено}}}$

и

${ Displaystyle е (х) = lceil х rceil -1,}$

${ Displaystyle lceil х rceil}$ наименьшее целое число не менее Икс (в функция потолка ).

В отличие от стандартных позиционная запись можно определить с помощью аналогичного рекурсивного алгоритма, где

${ Displaystyle е (х) = lfloor x rfloor,}$

Расширение до целых чисел

Для базы ${ displaystyle k> 1}$, биективное основание-${ displaystyle k}$ система счисления может быть расширена до отрицательных целых чисел так же, как и стандартная база-${ displaystyle b}$ система счисления с помощью бесконечного числа цифр ${ displaystyle d_ {k-1}}$, куда ${ displaystyle f (d_ {k-1}) = k-1}$, представленный бесконечной слева последовательностью цифр ${ displaystyle ldots d_ {k-1} d_ {k-1} d_ {k-1} = { overline {d_ {k-1}}}}$. Это потому, что Суммирование Эйлера

${ displaystyle g ({ overline {d_ {k-1}}}) = sum _ {i = 0} ^ { infty} f (d_ {k-1}) k ^ {i} = - { гидроразрыв {k-1} {k-1}} = - 1}$

означающий, что

${ displaystyle g ({ overline {d_ {k-1}}} d_ {k}) = f (d_ {k}) sum _ {i = 1} ^ { infty} f (d_ {k-1 }) k ^ {i} = 1 + sum _ {i = 0} ^ { infty} f (d_ {k-1}) k ^ {i} = 0}$

и для каждого положительного числа ${ displaystyle n}$ с двузначным числовым представлением цифр ${ displaystyle d}$ представлен ${ displaystyle { overline {d_ {k-1}}} d_ {k} d}$. Для базы ${ displaystyle k> 2}$, отрицательные числа ${ Displaystyle п <-1}$ представлены ${ displaystyle { overline {d_ {k-1}}} d_ {i} d}$ с ${ Displaystyle я <к-1}$, а для базы ${ displaystyle k = 2}$, отрицательные числа ${ Displaystyle п <-1}$ представлены ${ displaystyle { overline {d_ {k}}} d}$. Это похоже на то, как в представление цифр со знаком, все целые числа ${ displaystyle n}$ с цифровыми представлениями ${ displaystyle d}$ представлены как ${ displaystyle { overline {d_ {0}}} d}$ куда ${ displaystyle f (d_ {0}) = 0}$. Это представление больше не является биективным, поскольку весь набор бесконечных слева последовательностей цифр используется для представления ${ displaystyle k}$-адические целые числа, из которых целые числа являются лишь подмножеством.

Свойства биективного основания-k цифры

Для данной базы k ≥ 1,

• есть точно k^п биективная базаk цифры длины п ≥ 0.^[1]
• если k ≥ 2, количество цифр в биективном основании -k числовое, представляющее неотрицательное целое число п является ${ Displaystyle lfloor журнал _ {k} ((n + 1) (k-1)) rfloor}$,^[2] в отличие от ${ displaystyle lfloor log _ {k} n rfloor +1 (n> 0)}$ для обычной базы-k цифры; если k = 1 (т.е. унарный), то количество цифр просто п;
• если k ≥ 2, биективная база-k и обычная база-k цифры для неотрицательного целого числа п идентичны тогда и только тогда, когда обычное число не содержит цифры 0 (или, что то же самое, двузначное число не является пустой строкой и не содержит цифру k).
• список биективных базовых-k цифры в естественном порядке представленных целых чисел автоматически заказ шортлекс (сначала кратчайшие, лексикографические в каждой длине). Таким образом, используя λ для обозначения пустой строкой, цифры с основанием 1, 2, 3, 8, 10, 12 и 16 имеют следующий вид (где для сравнения перечислены обычные представления):

Примеры

34152 (в биективном основании-5) = 3 × 5⁴ + 4×5³ + 1×5² + 5×5¹ + 2 × 1 = 2427 (в десятичной системе).

119A (в биективном основании-10, где «A» представляет цифровое значение десять) = 1 × 10³ + 1×10² + 9×10¹ + 10 × 1 = 1200 (в десятичной системе).

Типичный алфавитный список, содержащий более 26 элементов, является биективным, используя порядок A, B, C ... X, Y, Z, AA, AB, AC ... ZX, ZY, ZZ, AAA, AAB, AAC. ..

Биективная система по основанию 10

Биективная система base-10 является базой десять позиционный система счисления который не использует цифру для обозначения нуль. Вместо этого в нем есть цифра, представляющая десять, например А.

Как и в случае с обычным десятичный, каждая цифра представляет собой степень десяти, так, например, 123 - это «сто плюс две десятки плюс три единицы». Все положительные целые числа которые представлены исключительно ненулевыми цифрами в обычном десятичном формате (например, 123), имеют такое же представление в десятичном формате без нуля. Те, которые используют ноль, должны быть переписаны, например, 10 становится A, обычное 20 становится 1A, обычное 100 становится 9A, обычное 101 становится A1, обычное 302 становится 2A2, обычное 1000 становится 99A, обычное 1110 становится AAA, обычное 2010 становится 19AA , и так далее.

Добавление и умножение в десятичной системе счисления без нуля, по сути, такие же, как с обычным десятичным числом, за исключением того, что перенос происходит, когда позиция превышает десять, а не когда она превышает девять. Итак, чтобы вычислить 643 + 759, есть двенадцать единиц (напишите 2 справа и перенесите 1 в десятки), десять десятков (напишите A без необходимости переносить до сотен), тринадцать сотен (напишите 3 и перенесите 1 в тысяч) и одна тысяча (напишите 1), чтобы получить результат 13A2 вместо обычного 1402.

Биективная система base-26

В биективной системе с основанием 26 можно использовать буквы латинского алфавита от "A" до "Z" для представления 26-значных значений. один к двадцать шесть. (A = 1, B = 2, C = 3, ..., Z = 26)

При таком выборе обозначения числовая последовательность (начиная с 1) начинается с A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB. , ДО Н.Э, ...

Каждая цифра представляет собой степень двадцати шести, поэтому, например, цифра ABC представляет значение 1 × 26² + 2 × 26¹ + 3 × 26⁰ = 731 по основанию 10.

Много электронные таблицы включая Майкрософт Эксель используйте эту систему для присвоения меток столбцам электронной таблицы, начиная с A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA и т. д. , в Excel 2013 может быть до 16384 столбцов с метками от A до XFD.^[3] Вариант этой системы используется для обозначения переменные звезды.^[4] Его можно применить к любой задаче, где желательно систематическое именование с использованием букв и кратчайших возможных строк.

Исторические заметки

Тот факт, что каждое неотрицательное целое число имеет уникальное представление в биективном базисномk (k ≥ 1) является "народная теорема "который открывался заново много раз. Ранние экземпляры Фостер (1947) для случая k = 10 и Смуллян (1961) и Бём (1964) для всех k ≥ 1. Смуллян использует эту систему для обеспечения Гёделевская нумерация строки символов в логической системе; Бём использует эти представления для выполнения вычислений на языке программирования П''. Кнут (1969) упоминает особый случай k = 10 и Саломаа (1973) обсуждает случаи k ≥ 2. Форслунд (1995) представляется еще одним новым открытием и предполагает, что если в древних системах счисления использовалось биективное основание -k, они могут не быть признаны таковыми в археологических документах из-за общего незнания этой системы.

Примечания

Рекомендации

• Бём, К. (Июль 1964 г.), «О семействе машин Тьюринга и родственном языке программирования», Бюллетень ICC, 3: 191.
• Форслунд, Роберт Р. (1995), «Логическая альтернатива существующей позиционной системе счисления», Юго-западный журнал чистой и прикладной математики, 1: 27–29, МИСТЕР  1386376, S2CID  19010664.
• Фостер, Дж. Э. (1947), «Система счисления без нулевого символа», Математический журнал, 21 (1): 39–41, Дои:10.2307/3029479, JSTOR  3029479.
• Кнут, Д. Э. (1969), Искусство программирования, Vol. 2: получисловые алгоритмы (1-е изд.), Аддисон-Уэсли, Решение упражнения 4.1-24, стр. 195. (Обсуждает биективное основание-10.)
• Саломаа, А. (1973), Формальные языки, Academic Press, Note 9.1, pp. 90–91.. (Обсуждает биективную базу-k для всех k ≥ 2.)
• Смуллян, Р. (1961), "9. Лексикографическая упорядоченность; п-адическое представление целых чисел ", Теория формальных систем, Анналы математических исследований, 47, Princeton University Press, стр. 34–36..