Az a matematika, amely bármely bázisról bármilyen bázisra konvertál, anélkül, hogy átmennénk a 10. bázison?

Ez nagyon alapvető kérdésnek tűnik számomra, ezért bocsásson meg, ha előadok egy kicsit. A legfontosabb szempont, amit itt meg kell tanulnia, hogy egy szám nem annak számjellegű ábrázolása . A szám egy absztrakt matematikai objektum, míg a számjegyű ábrázolása konkrét dolog, nevezetesen egy szimbólum sorozat egy papíron (vagy egy bit sorozat a számítási memóriában, vagy egy hangsor, amelyet akkor adsz ki, amikor egy számot közölsz). Zavaró az a tény, hogy soha nem lát t egy számot, hanem mindig annak számjellegű ábrázolását. Végül arra gondolsz, hogy a szám az az ábrázolás.

Ezért a helyes kérdés, hogy ” hogyan konvertálhatom egyik bázisról a másikra ” inkább ” hogyan tudom megtudni, hogy melyik számot képviseli egy adott számjegysorozat ” és ” hogyan találom meg egy adott szám digitális ábrázolását “.

Készítsünk tehát két függvényt a Pythonban, egyet egy számjegyes ábrázolás konvertálásához egy számot, egy másik pedig az ellenkezőjét. Megjegyzés: amikor a Python függvényt futtatjuk, természetesen kinyomtatja a képernyőn azt a számot, amelyet a 10-es bázisban kapott. De ez nem azt jelenti, hogy a számítógép a számokat bázisban tartja 10 (ez nem “t”. Nem releváns , hogy a számítógép hogyan ábrázolja a számokat.

def toDigits(n, b): """Convert a positive number n to its digit representation in base b.""" digits = [] while n > 0: digits.insert(0, n % b) n = n // b return digits def fromDigits(digits, b): """Compute the number given by digits in base b.""" n = 0 for d in digits: n = b * n + d return n 

Teszteljük ezeket:

>>> toDigits(42, 2) [1, 0, 1, 0, 1, 0] >>> toDigits(42, 3) [1, 1, 2, 0] >>> fromDigits([1,1,2,0],3) 42 

Konvertálási funkciókkal felfegyverezve a problémád könnyen megoldható:

def convertBase(digits, b, c): """Convert the digits representation of a number from base b to base c.""" return toDigits(fromDigits(digits, b), c) 

Egy teszt :

>>> convertBase([1,1,2,0], 3, 2) [1, 0, 1, 0, 1, 0] 

Megjegyzés: megtettük ne haladjon át a 10-es alap ábrázoláson! Átalakítottuk az alap $ b $ ábrázolást számra, majd a számot az alapra $ c $ . A szám semmilyen ábrázolásban nem volt. (Valójában az volt, hogy a számítógépnek valahogyan képviselnie kellett, és elektromos jelek és funky használatával képviselte. csipet, ami chipekben történik, de minden bizonnyal azok, amelyek w nincs 0 “és 1” s.)

Megjegyzés

• Ez nem ‘ nem győzi meg nekem 100%. Valójában a számot valamilyen reprezentációvá konvertálta (bár állíthatja, hogy nem tudja, mi az), mert a számítógépek nem platonikus matematikusok, és az algoritmusa nem képes a $ b_1 $ alapú tetszőleges számjegy-sorrendet átalakítani $ b_2 $ -ra; csak a betongép által reprezentálható szekvenciákat képes átalakítani. A Python bájosan rugalmas; C nem lett volna ennyire elnéző. Tökéletes kérdés, hogy hogyan lehet konvertálni tetszőleges karakterláncokat $ b_1 $ -ról $ b_2 $ -ra; ez azonban csak lineáris időben lehetséges, kivéve bizonyos alapkombinációkat (pl. 2 < – > 16)
• Érvényes feltenni a kérdést, de a helyes válasz megtalálása érdekében a legjobb, ha tisztában vagyunk azzal, hogy a számok absztrakt entitások.
• Ez nem adja át a számot a 10. bázis ábrázolásán keresztül, mivel az fromDigits visszaadja a 10. bázis számát.
• @anorton: Nem, egészen biztosan nem . A Python kinyomtatja a képernyőn lévő számot az alap 10 számjegyű ábrázolásában, de maga a szám nem így tárolódik. Amit megpróbálok átlátni, az az, hogy irreleváns a számok miként valósulnak meg a Pythonon belül. Nem számít. Csak az a fontos, hogy számként viselkedjenek.
• Végül egy általános megoldás minden bázisra, és nem korlátozódik bizonyos felhasználási esetekre, 36-nál kevesebb bázisokra vagy olyan esetekre, amikor elegendő egyedi szimbólummal állhat elő. .

Szerintem ennek megértésének legjobb módja egy idegenrel folytatott beszélgetés (legalábbis mint analógia).

Definíció $ x $ egy szám a $ b $ alapban azt jelenti, hogy a $ x $ a $ < b $ számjegyből áll.

Példák Az 10010011011 számjegyből álló szám egy szám a 2. bázisban, a 68416841531 karakterlánc egy szám a 10. bázisban, a BADCAFE pedig egy szám a 16. bázisban.

Most Tegyük fel, hogy a QUUX bolygón nőttem fel, ahol mindenkit arra tanítanak, hogy egész életében dollárban dolgozzon, és találkozom veled, aki a $ b $ alapjául szolgál. Tehát megmutatsz nekem egy számot, és mit tegyek? Szükségem van egy értelmezési módra:

Definíció Tudok értelmezni egy szám a $ b $ bázisban (megjegyzés: $ b $ egy a $ q $ bázisban lévő szám) a következő képlettel:

$$ \ begin {array} {rcl} [\! [[epsilon] \!] & = & 0 \\ [\! [[bar sd] \!] & = & [\! [\ bar s] \!] \ szorzat b + d \ vége {tömb} $$

ahol $ \ Az epsilon $ az üres karakterláncot, a $ \ bar sd $ pedig a $ d $ számjeggyel végződő karakterláncot jelöli. Lásd a igazolást arról, hogy az összeadás hozzáadódik , ennek a jelölésnek a bemutatásához.

Tehát mi történt itt? Számot adtál nekem a $ b $ bázisban, és ezt “$ q $ -ba” értelmeztem, különös filozófia nélkül a számok valójában.

Kulcs Ennek kulcsa, hogy a $ \ times $ és a $ + $ $ függvények alap $ q $ számokon működnek. Ezek egyszerű algoritmusok, amelyeket rekurzívan definiálnak a $ q $ számokon (karakterláncok) számjegy).

Ez kissé elvontnak tűnhet, mivel a változók helyett a tényleges számokat használtam. Tehát tegyük fel, hogy te egy 13-as lény vagy ($ 0123456789XYZ $ szimbólumokat használsz), és én a 7-et (ami sokkal értelmesebb) a $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $ szimbólumok használatával szokták használni.

Tehát láttam az ábécéjét, és így tábláztam:

$$ \ begin {tömb} {| c | c || c | c || c | c |} \ hline 0 & \ alpha & 1 & \ beta & 2 & \ gamma \\ 3 & \ delta & 4 & \ rho & 5 & \ zeta \\ 6 & \ xi & 7 & \ beta \ alpha & 8 & \ beta \ beta \\ 9 & \ beta \ gamma & X \ beta \ delta & Y & \ beta \ rho \\ & & Z & \ beta \ zeta & & \\ \ hline \ end {array} $$

Tehát tudom, hogy a $ \ beta \ xi $ bázisban dolgozol, és tudom, hogy a 7-es bázis milyen számjegyű Az írás megfelel a következőnek:

Ha most a fizikáról beszélgettünk, és ön alapvető állandókról mesélt nekem (mondjuk) 60Z8 $, ezért ezt értelmeznem kell:

$$ \ begin { tömb} {rcl} [\! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ \ end {tömb} $$

Tehát a $ \ szorzásával kezdem beta \ zeta \ times \ beta \ xi $, de ez számomra általános iskolai dolgok, felidézem:

Quux szorzótábla

$$ \ begin {tömb} {| c | cccccc |} \ hline \\ \ times & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ hline \ beta & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ gamma & \ gamma & \ rho & \ xi & \ beta \ beta & \ beta \ delta & \ beta \ zeta \\ \ delta & \ delta & \ xi & \ beta \ gamma & \ beta \ zeta & \ gamma \ beta & \ gamma \ rho \\ \ rho & \ rho & \ beta \ beta & \ beta \ zeta & \ gamma \ gamma & \ gamma \ xi & \ delta \ delta \\ \ zeta & \ zeta & \ beta \ delta & \ gamma \ beta & \ gamma \ xi & \ delta \ rho & \ rho \ gamma \\ \ xi & \ xi & \ beta \ zeta & \ gamma \ rho & \ delta \ delta & \ rho \ gamma & \ zeta \ beta \\ \ beta \ alpha & \ beta \ alpha & \ gamma \ alpha & \ delta \ alpha & \ rho \ alpha & \ zeta \ alpha & \ xi \ alpha \\ \ hline \ end {array} $$

tehát a $ \ beta \ zeta \ times \ beta \ xi $ megkereséséhez:

$$ \ begin {array} {ccc} & \ beta & \ ze ta \\ \ times & \ beta & \ xi \\ \ hline & \ xi & \ gamma \\ & \ rho & \\ \ beta & \ zeta & \\ \ hline \ delta & \ beta & \ gamma \\ \ gamma & & \\ \ end {tömb} $$

tehát idáig eljutottam

$$ \ begin {array} {rcl} [\! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alfa (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ \ end {tömb} $$

Most az algoritmust kell végrehajtanom, amely korábban említettük:

$$ \ begin {array} {ccc} \ delta & \ beta & \ gamma \\ & \ beta & \ beta \\ \ hline \ delta & \ gamma & \ delta \\ \ end {tömb} $$

tehát

$$ \ begin {tömb} {rcl} [ \! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alfa (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ & = & \ xi ( \ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ & = & \ xi (\ beta \ xi) ^ 3 + \ alfa (\ beta \ xi) ^ 2 + \ delta \ gamma \ delta \\ \ end {tömb} $ $

és így folytatva $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

Összefoglaló: Ha saját számfelfogásom van az alap $ q $ számjegy-húrok szempontjából, akkor módom van arra, hogy a számokat a $ b $ bázisról a saját rendszerembe értelmezzem, az alapvető számtani műveletek alapján – amelyek natív módon működnek alap $ q $.

Kommentárok

• Nos, ez jócskán szaggatott sor volt. Mégis hogyan tudnám rávenni a számítógépet erre?
• @Griffin, azt hiszem, idő előtt felteszed ezt a (furcsa) kérdést. Válasszon egy programozási nyelvet, és írja be az összeadás és szorzás algoritmusát az alap q számokra (számjegyek listájaként ábrázolva), majd meghatározzon egy függvényt, amellyel az alap b számjegyeket alap q számokká és b alap számokat alap q számokká értelmezi. ‘ Mindezt elmagyaráztam.
• A lényeg, hogy ismerem azt a koncepciót, amelyet megpróbál ábrázolni. A problémám az, hogy a számítógépem ‘ nem tudja használni a görnyedt sorait.
• Tudom, amit elmagyaráztál, de a gyakorlatba való átültetés sokkal nehezebb. Látja, hogy ezek a számjegyek nem ‘ t olyan könnyű meghatározni.
• Miért dobta le az alfa számjegyet a legjelentősebb helyzetbe? Mivel 6 = & xi ;, Wouldn ‘ t 7 = & alfa; & alfa ;?

Ez egy refaktor (Python) 3) a Andrej “s kódból. Míg Andrej kódjaiban a számok számjegyek (skalárok) listáján vannak ábrázolva, addig a következő kódok a tetszőleges szimbólumok felsorolása egy egyéni karakterláncból:

def v2r(n, base): # value to representation """Convert a positive number to its digit representation in a custom base.""" b = len(base) digits = "" while n > 0: digits = base[n % b] + digits n = n // b return digits def r2v(digits, base): # representation to value """Compute the number represented by string "digits" in a custom base.""" b = len(base) n = 0 for d in digits: n = b * n + base[:b].index(d) return n def b2b(digits, base1, base2): """Convert the digits representation of a number from base1 to base2.""" return v2r(r2v(digits, base1), base2) 

Konvertálás végrehajtása értékről reprezentációra egy egyéni alapban:

>>> v2r(64,"01") "1000000" >>> v2r(64,"XY") "YXXXXXX" >>> v2r(12340,"ZABCDEFGHI") # decimal base with custom symbols "ABCDZ" 

Átalakítás végrehajtása reprezentációból (egyéni bázisban) értékre :

>>> r2v("100","01") 4 >>> r2v("100","0123456789") # standard decimal base 100 >>> r2v("100","01_whatevr") # decimal base with custom symbols 100 >>> r2v("100","0123456789ABCDEF") # standard hexadecimal base 256 >>> r2v("100","01_whatevr-jklmn") # hexadecimal base with custom symbols 256 

Alapkonverzió végrehajtása egyik gondozó bázisról a másikra:

>>> b2b("1120","012","01") "101010" >>> b2b("100","01","0123456789") "4" >>> b2b("100","0123456789ABCDEF","01") "100000000" 

Megjegyzések

• Üdvözöljük a webhelyen, és köszönjük hozzájárulásukat. A jól optimalizált forráskód előállítása azonban nem ‘ az, amiről ez a webhely valójában szól. Andrej ‘ kódja világossá teszi a fogalmakat, amire a válaszához szükség van, de a kód továbbfejlesztése ezen túl programozás kérdése, nem pedig számítógépes tudomány .
• @DavidRicherby részben egyetértek, de ez a hozzászólás túl hosszú volt ahhoz, hogy megjegyzést fűzzünk hozzá, és a legjobb helye valahol Andrej ‘ válasz közelében található, hogy ‘ ezért írtam ide. Egyébként, ha úgy gondolja, hogy ‘ jobb, akkor konvertálhatom egy megjegyzésre, amely a kódra mutató linket tartalmaz, de nem lenne ‘ túlzott purizmus?
• @David ‘ s ” site-purist kifogások, hasznosnak találtam a válaszodat, mert hangsúlyozza azt a tényt, hogy az érintett alapok elvontabb fogalmakként ” ábécé különböző hosszúságú tetszőleges szimbólumok – és nem korlátozódnak a szokásos 2-36 karakteres tartományra. Valójában a bájtfolyamokat tekinthetjük a 256 alapérték egészének ” számjegyének “.

Az alapkonverzió alapvető művelete az @AndrejBauer válasz toDigits() művelete. Ennek elkészítéséhez azonban nem szükséges számot létrehozni a számok belső ábrázolásában, amely alapvetően a 2-es reprezentáció és az alap közötti átalakítás.A szükséges műveleteket az eredeti alap ábrázolásban hajthatja végre.

Tehát az első lépés az ismétlődő modulo osztási művelet végrehajtása

def convertBase(n,original_base,destination_base): digits = [] while not is_zero(n): digits.insert(0,modulo_div(n,original_base,destination_base)) return digits 

Mivel a belső ábrázolás számjegy, ezért egy speciális függvény a nulla teszteléséhez

def is_zero(n): for d in n: if d != 0: return False return True 

Végül el kell végeznünk a modulo_div műveletet, amely valójában a rendeltetési hely szerinti bontás, amint azt az iskolában tanultuk.

def modulo_div(n,original_base,destination_base): carry = 0 for i in range(len(n)): d = n[i] d+=original_base*carry carry = d%destination_base d=(d//destination_base) n[i] = d #print(i,d,carry) return carry 

csak egy tesztellenőrzés a kód helyes ellenőrzésére:

print(convertBase([1,1,2,0], 3, 2)) #[1, 0, 1, 0, 1, 0] print(convertBase([1, 0, 1, 0, 1, 0], 2, 3)) #[1, 1, 2, 0] 

megjegyzések

• Köszönjük a posztolást, de kérjük, vegye figyelembe, hogy ‘ nem vagyunk kódoló webhelyek, ezért egy nagy kódblokk nem ‘ itt nem megfelelő válasz. Különösen akkor, ha a kérdés kifejezetten azt mondja: ” Nem kell ‘ nincs szükségem kódra, csak az alap matematika kell mögötte. ”
• @DavidRicherby megpróbáltam szöveget hozzáadni.
• Köszönöm. És látom, hogy ‘ nagyon sok kód található ezen az oldalon, annak ellenére, hogy mondtam!
• @David: FWIW, azt hiszem, ez válaszol az OP-ra A ‘ kérdés a legjobban, mivel megmutatja, hogyan lehet konvertálni a két alapot anélkül, hogy először átalakítanánk az eredeti ábrázolását valamilyen köztes formára, majd ezt konvertálnánk a cél bázissá.
• Szép próbálkozás, de d még mindig a 10-es bázisban van, így valójában kivonja n kisebb részét, átalakítva azt 10-es bázissá, majd átalakítva a kívánt bázissá, és összegyűjtve azokat a végeredménybe.

Tudok egy egyszerű módszert az alapkonverzió elvégzésére, amelyhez nincs szükség számítógépes programra. Meghatározással az átalakítás módja bármelyik alapról 2 alapra és fordítva, majd az egyik alapról a másikra fedés azáltal, hogy először átalakul az első alapról a 2 alapra, majd átalakul a 2 alapról a másikra. A 2-et olyan egyszerűen meg lehet szorozni vagy el lehet osztani bármelyik alapon.

Bármely alapról 2-esre való átalakításhoz annyit kell tennie, hogy felismeri, hogy bármely számra, ha felveszi a 2-es alap jelölését, és elindítja 0-tól, majd az egyes számjegyeknél balról jobbra duplázzuk, ha ez a számjegy nulla, és duplán, mint ha hozzáadjuk az 1-et, ha ez a számjegy 1, akkor magához a számhoz jutunk el. Most, hogy ezt a számot bármelyik bázisban megadta, oszthatja 2-vel az alapon, hogy hányadost és maradékot kapjon. Ha a maradék 1, az utolsó bináris számjegy 1, és ha a maradék 0, akkor az utolsó bináris számjegy 0. Oszd meg újra 2-vel. Ha a maradék 1, a második utolsó számjegy 1, és ha a maradék 0, akkor a második utolsó számjegy 0 és így tovább, amíg 0 hányadost nem kap.

A 2. bázisról bármelyikre való konvertáláshoz bázis, csak annyit kell tennie, hogy ebben az alapban kezdje 0-tól, majd minden balról jobbra haladó bináris számjegyhez duplázza meg ezt az alapot, ha ez a számjegy 0, és duplázza, majd adjon hozzá 1-et ebben az alapban, ha ez a számjegy 1.

Megjegyzések

• 2 is so easy to multiply or divide by in any base. Nem ‘ t nézze meg, hogy a páratlan bázisok esetében, amelyek kettő bármelyikének hatványából egynél többek (kezdetben 11 és 13).