Bijektivní číslování - Bijective numeration
Číselné soustavy |
---|
Hindu-arabská číselná soustava |
východní Asiat |
evropský |
americký |
Abecední |
Bývalý |
Poziční systémy podle základna |
Nestandardní poziční číselné systémy |
Seznam číselných soustav |
Bijektivní číslování je jakýkoli číselná soustava ve kterém každý nezáporný celé číslo lze reprezentovat přesně jedním způsobem pomocí konečného řetězec číslic. Název je odvozen od toho bijekce (korespondence jedna k jedné) mezi sadou nezáporných celých čísel a sadou konečných řetězců pomocí konečné sady symbolů („číslic“).
Většina obyčejných číselných soustav, jako je běžná desetinný systému, nejsou bijektivní, protože více než jeden řetězec číslic může představovat stejné kladné celé číslo. Zejména přidání úvodní nuly nezmění představovanou hodnotu, takže „1“, „01“ a „001“ představují číslo jeden. I když je obvyklý pouze první, skutečnost, že ostatní jsou možné, znamená, že desetinné číslo není bijektivní. Nicméně, unární, pouze s jednou číslicí, je bijektivní.
A bijektivní základna -k číslování je bijektiv poziční notace. Používá řetězec číslic ze sady {1, 2, ..., k} (kde k ≥ 1) ke kódování každého kladného celého čísla; pozice číslice v řetězci definuje její hodnotu jako násobek mocniny k. Smullyan (1961) nazývá tuto notaci k-adic, ale nemělo by být zaměňováno s p-adická čísla: bijective numerals are a system for showing normal celá čísla konečnými řetězci nenulových číslic, zatímco p-adická čísla jsou systém matematických hodnot, které obsahují celá čísla jako podmnožinu a mohou vyžadovat nekonečné sekvence číslic v libovolném číselném vyjádření.
Definice
The základna-k bijective numeration system uses the digit-set {1, 2, ..., k} (k ≥ 1) jednoznačně reprezentovat každé nezáporné celé číslo, a to následovně:
- Celé číslo nula je reprezentováno prázdný řetězec.
- Celé číslo představované neprázdným číslicovým řetězcem
- AnAn−1 ... A1A0
- je
- An kn + An−1 kn−1 + ... + A1 k1 + A0 k0.
- Řetězec číslic představující celé číslo m > 0 je
- AnAn−1 ... A1A0
- kde
- a
- být nejméně celé číslo ne menší než X (dále jen stropní funkce ).
Naproti tomu standardní poziční notace lze definovat podobným rekurzivním algoritmem kde
Rozšíření na celá čísla
Pro základnu bijektivní základna systém číslování lze rozšířit na záporná celá čísla stejným způsobem jako standardní základna číselná soustava pomocí nekonečného počtu číslic , kde , představovaný jako levý nekonečný sled číslic . Je to proto, že Eulerův součet
znamenající, že
a za každé kladné číslo s bijektivním číslováním je reprezentován . Pro základnu , záporná čísla jsou zastoupeny s , zatímco pro základnu , záporná čísla jsou zastoupeny . Je to podobné jako v podepsané číslice, všechna celá čísla s číslicovými reprezentacemi jsou reprezentovány jako kde . Tato reprezentace již není bijektivní, protože k reprezentaci se používá celá sada zleva nekonečných posloupností číslic -adická celá čísla, z nichž celá čísla jsou pouze podmnožinou.
Vlastnosti bijektivní bázek číslice
Pro danou základnu k ≥ 1,
- existují přesně kn bijektivní základnak číslice délky n ≥ 0.[1]
- -li k ≥ 2, počet číslic v bijektivní základně -k číslice představující nezáporné celé číslo n je ,[2] na rozdíl od pro běžnou základnuk číslice; -li k = 1 (tj. Unární), pak je počet číslic rovný n;
- -li k ≥ 2, bijektivní základnak a obyčejný základk číslice pro nezáporné celé číslo n jsou identické právě tehdy, když běžná číslice číslici neobsahuje 0 (nebo ekvivalentně bijektivní číslice není ani prázdný řetězec, ani neobsahuje číslici k).
- seznam bijective base-k číslice v přirozeném pořadí celých čísel, které jsou znázorněny, jsou automaticky v shortlexová objednávka (nejkratší první, lexikografický v každé délce). Pomocí λ tedy označujeme prázdný řetězec, číslice základny 1, 2, 3, 8, 10, 12 a 16 jsou následující (kde jsou pro srovnání uvedeny běžné reprezentace):
bijektivní základ 1: | λ | 1 | 11 | 111 | 1111 | 11111 | 111111 | 1111111 | 11111111 | 111111111 | 1111111111 | 11111111111 | 111111111111 | 1111111111111 | 11111111111111 | 111111111111111 | 1111111111111111 | ... | (unární číselná soustava ) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
bijektivní základ 2: | λ | 1 | 2 | 11 | 12 | 21 | 22 | 111 | 112 | 121 | 122 | 211 | 212 | 221 | 222 | 1111 | 1112 | ... | |||||||||||
binární: | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 10000 | ... | |||||||||||
bijektivní základ 3: | λ | 1 | 2 | 3 | 11 | 12 | 13 | 21 | 22 | 23 | 31 | 32 | 33 | 111 | 112 | 113 | 121 | ... | |||||||||||
trojice: | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 | 101 | 102 | 110 | 111 | 112 | 120 | 121 | ... | |||||||||||
bijektivní základna 8: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | ... | |||||||||||
osmičkový: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | ... | |||||||||||
bijektivní základ 10: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | 11 | 12 | 13 | 14 | 15 | 16 | ... | |||||||||||
desetinný: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ... | |||||||||||
bijektivní základna 12: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | 11 | 12 | 13 | 14 | ... | |||||||||||
duodecimální: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | 10 | 11 | 12 | 13 | 14 | ... | |||||||||||
bijektivní základna 16: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | G | ... | |||||||||||
hexadecimální: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | ... |
Příklady
- 34152 (v bijektivu base-5) = 3 × 54 + 4×53 + 1×52 + 5×51 + 2 × 1 = 2427 (v desítkové soustavě).
- 119A (v bijektivu base-10, kde „A“ představuje číslici deset) = 1 × 103 + 1×102 + 9×101 + 10 × 1 = 1200 (v desítkové soustavě).
- Typický abecední seznam s více než 26 prvky je bijektivní a používá pořadí A, B, C ... X, Y, Z, AA, AB, AC ... ZX, ZY, ZZ, AAA, AAB, AAC. ..
Bijektivní systém base-10
Bijektivní systém base-10 je základna deset poziční číselná soustava který k zastupování nepoužívá číslici nula. Místo toho má číslici představující deset, například A.
Stejně jako u konvenčních desetinný, každá pozice číslice představuje mocninu deseti, takže například 123 je „sto plus dvě desítky plus tři jednotky.“ Všechno kladná celá čísla které jsou reprezentovány pouze nenulovými číslicemi v konvenčním desetinném místě (například 123), mají stejné zastoupení v desítkovém čísle bez nuly. Ti, kteří používají nulu, musí být přepsáni, takže například 10 se stane A, konvenční 20 stane 1A, konvenční 100 se stane 9A, konvenční 101 se stane A1, konvenční 302 se stane 2A2, konvenční 1000 se stane 99A, konvenční 1110 se stane AAA, konvenční 2010 se stane 19AA , a tak dále.
Přidání a násobení v desítkovém bez nuly jsou v zásadě stejné jako u běžného desetinného místa, kromě toho, že přenášení nastane, když pozice přesáhne deset, spíše než když přesáhne devět. Takže pro výpočet 643 + 759 je zde dvanáct jednotek (zapište 2 napravo a vezměte 1 na desítky), deset desítek (zapište A, aniž byste je museli nést na stovky), třináct set (zapište 3 a vezměte 1 na tisíce) a tisíc (zápis 1), abychom dali výsledek 13A2 místo konvenčních 1402.
Systém bijective base-26
V systému bijective base-26 lze použít písmena latinky „A“ až „Z“, která představují 26 číslic jeden na dvacet šest. (A = 1, B = 2, C = 3, ..., Z = 26)
S touto volbou zápisu začíná číselná řada (počínaje 1) A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB , PŘED NAŠÍM LETOPOČTEM, ...
Každá pozice číslice představuje sílu dvaceti šesti, takže například číslice ABC představuje hodnotu 1 × 262 + 2 × 261 + 3 × 260 = 731 v základu 10.
Mnoho tabulky počítaje v to Microsoft Excel použijte tento systém k přiřazení štítků ke sloupcům tabulky, počínaje A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA atd. Například , v aplikaci Excel 2013 může existovat až 16384 sloupců označených od A do XFD.[3] K pojmenování se používá varianta tohoto systému proměnné hvězdy.[4] Lze jej použít na jakýkoli problém, kde je žádoucí systematické pojmenování pomocí písmen, při použití nejkratších možných řetězců.
Historické poznámky
Skutečnost, že každé nezáporné celé číslo má v bijektivní bázi jedinečné zastoupeník (k ≥ 1) je „lidová věta „to bylo mnohokrát znovuobjeveno. Časné instance jsou Foster (1947) pro případ k = 10 a Smullyan (1961) a Böhm (1964) pro všechny k ≥ 1. Smullyan používá tento systém k poskytování a Gödelovo číslování řetězců symbolů v logickém systému; Böhm používá tato vyjádření k provádění výpočtů v programovacím jazyce P ′ ′. Knuth (1969) zmiňuje zvláštní případ k = 10 a Salomaa (1973) pojednává o případech k ≥ 2. Forslund (1995) se jeví jako další znovuobjevení a předpokládá, že kdyby starověké číslovací systémy používaly bijektivní základnuk, nemusí být jako takové rozpoznány v archeologických dokumentech z důvodu obecné neznalosti tohoto systému.
Poznámky
- ^ Forslund (1995).
- ^ „Kolik číslic je v bijektivní číslici base-k pro n?“. Výměna zásobníku. Citováno 22. září 2018.
- ^ Harvey, Greg (2013), Excel 2013 pro figurínyJohn Wiley & Sons, ISBN 9781118550007.
- ^ Hellier, Coel (2001), „Dodatek D: Nomenklatura proměnných hvězd“, Kataklyzmatické proměnné hvězdy - jak a proč se mění „Praxis Books in Astronomy and Space“, Springer, str. 197, ISBN 9781852332112.
Reference
- Böhm, C. (Červenec 1964), „Na rodinu Turingových strojů a související programovací jazyk“, Bulletin ICC, 3: 191.
- Forslund, Robert R. (1995), „Logická alternativa ke stávajícímu systému pozičních čísel“, Jihozápadní žurnál čisté a aplikované matematiky, 1: 27–29, PAN 1386376, S2CID 19010664.
- Foster, J. E. (1947), „Číselný systém bez nulového symbolu“, Matematický časopis, 21 (1): 39–41, doi:10.2307/3029479, JSTOR 3029479.
- Knuth, D. E. (1969), The Art of Computer Programming, sv. 2: Seminumerické algoritmy (1. vyd.), Addison-Wesley, Solution to Exercise 4.1-24, str. 195. (Diskutuje o bijective base-10.)
- Salomaa, A. (1973), Formální jazyky, Academic Press, poznámka 9.1, s. 90–91. (Diskutuje o bijektivní bázi -k pro všechny k ≥ 2.)
- Smullyan, R. (1961), "9. Lexikografické objednávání; n-adická reprezentace celých čísel ", Teorie formálních systémů, Annals of Mathematics Studies, 47„Princeton University Press, s. 34–36.