Matematica din spatele conversiei din orice bază în orice bază fără a trece prin baza 10?

Aceasta mi se pare o întrebare foarte de bază, așa că scuză-mă dacă te țin puțin. Cel mai important punct de învățat aici este că un număr nu este reprezentarea cifrelor sale . Un număr este un obiect matematic abstract, în timp ce reprezentarea cifrelor sale este un lucru concret, și anume o secvență de simboluri pe o hârtie (sau o secvență de biți în memoria de calcul sau o secvență de sunete pe care le scoateți atunci când comunicați un număr). Ceea ce te încurcă este faptul că nu vezi niciodată un număr, ci întotdeauna reprezentarea cifrelor acestuia. Așadar, ajungeți să credeți că numărul este reprezentarea.

Prin urmare, întrebarea corectă de pus nu este ” cum pot converti de la o bază la alta ” mai degrabă ” cum aflu ce număr este reprezentat de un șir dat de cifre ” și ” cum găsesc reprezentarea cifrelor unui număr dat „.

Deci, să producem două funcții în Python, una pentru conversia unei reprezentări cifre în un număr și altul pentru a face contrariul. Notă: când rulăm funcția Python, desigur, va tipări pe ecran numărul pe care l-a primit în baza 10. Dar acest lucru nu nu înseamnă că computerul păstrează numerele în bază 10 (nu este „t). Este irelevant modul în care computerul reprezintă numerele.

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 

Să le testăm:

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

Înarmat cu funcții de conversie, problema dvs. este rezolvată cu ușurință:

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

Un test :

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

Notă: am făcut nu treceți prin reprezentarea de bază 10! Am convertit reprezentarea de bază $ b $ în număr, apoi numărul în bază $ c $ . Numărul nu nu în nicio reprezentare. (De fapt, computerul trebuia să-l reprezinte cumva și îl reprezenta folosind semnale electrice și funky lucruri care se întâmplă în jetoane, dar cu siguranță acelea w Nici 0 „s și 1” s.)

Comentarii

• Acest lucru nu ‘ nu convinge eu 100%. De fapt, ați convertit numărul într-o anumită reprezentare (deși puteți pretinde că nu știți ce este), deoarece computerele nu sunt matematicieni platonici, iar algoritmul dvs. nu poate converti o secvență arbitrară de cifre din baza $ b_1 $ în baza $ b_2 $; poate converti doar secvențe reprezentabile de mașina de beton. Python este fermecător de flexibil; C nu ar fi fost atât de iertător. Este perfect valabil să vă întrebați cum să convertiți șirurile arbitrare de la $ b_1 $ la $ b_2 $; cu toate acestea, acest lucru este posibil doar în timp liniar, cu excepția anumitor combinații de baze (de exemplu, 2 < – > 16)
• Este valid să puneți întrebarea, dar pentru a găsi răspunsul corect, cel mai bine este să conștientizați faptul că numerele sunt entități abstracte.
• Acest face să treacă numărul prin reprezentarea bazei 10, deoarece fromDigits returnează numărul din baza 10.
• @anorton: Nu, cu siguranță nu . Python tipărește numărul pe ecran în reprezentarea de 10 cifre de bază, dar numărul în sine nu este stocat în acest fel. Ceea ce încerc să fac este că este irelevant modul în care numerele sunt implementate în Python. Nu conteaza. Singurul lucru care contează este că se comportă ca numerele.
• În cele din urmă, o soluție generală pentru orice bază și nu se limitează la anumite cazuri de utilizare, baze mai mici de 36 sau instanțe în care puteți veni cu suficiente simboluri unice .

Cred că cel mai bun mod de a înțelege acest lucru este în discuția cu un străin (cel puțin ca o analogie).

Definiție $ x $ este un număr din baza $ b $ înseamnă că $ x $ este un șir de cifre $ < b $.

Exemple Șirul de cifre 10010011011 este un număr din baza 2, șirul 68416841531 este un număr din baza 10, BADCAFE este un număr din baza 16.

Acum Să presupunem că am crescut pe planeta QUUX, unde toată lumea este învățată să lucreze în $ q $ pentru întreaga lor viață și vă întâlnesc, care obișnuiește să bazeze $ b $. Deci îmi arăți un număr și ce fac? Am nevoie de o modalitate de ao interpreta:

Definiție Pot interpreta un număr din baza $ b $ (Notă: $ b $ este un număr din baza $ q $) după următoarea formulă

$$ \ begin {array} {rcl} [\! [\ epsilon] \!] & = & 0 \\ [\! [\ bar sd] \!] & = & [\! [\ bar s] \!] \ times b + d \ end {array} $$

unde $ \ epsilon $ denotă șirul gol, iar $ \ bar sd $ denotă un șir care se termină cu cifra $ d $. Vedeți dovada mea că adăugarea adaugă pentru o introducere la această notație.

Deci, ce s-a întâmplat aici? Mi-ați dat un număr în baza $ b $ și „l-am interpretat în baza $ q $ fără nicio filosofie ciudată despre ceea ce sunt cu adevărat numerele.

Cheie Cheia acestui lucru este că $ \ times $ și $ + $ I pe care le am sunt funcții care funcționează pe numere de bază $ q $. Acestea sunt algoritmi simpli definiți recursiv pe numere de bază $ q $ (șiruri de cifre).

Acest lucru poate părea puțin abstract deoarece am folosit variabile mai degrabă decât numere reale de-a lungul întregului. Deci, să presupunem că sunteți o creatură de bază 13 (folosind simboluri 0123456789XYZ $) și eu sunt folosit la baza 7 (ceea ce este mult mai sensibil) folosind simbolurile $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Deci, am văzut alfabetul tău și l-am tabelat astfel:

$$ \ begin {array} {| 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} $$

Deci știu că lucrați în baza $ \ beta \ xi $ și știu ce bază 7 numără orice cifră scrie corespunde.

Acum, dacă am discuta despre fizică și mi-ai spune despre constante fundamentale (să zicem) $ 60Z8 $, așa că trebuie să interpretez acest lucru:

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

Deci încep prin multiplicarea $ \ beta \ zeta \ times \ beta \ xi $ dar pentru mine sunt lucruri de școală, îmi amintesc:

Tabelul de multiplicare Quux

$$ \ begin {array} {| 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} $$

deci pentru a găsi $ \ beta \ zeta \ times \ beta \ xi $ fac:

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

așa că am ajuns până aici

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

Acum trebuie să realizez adăugarea folosind algoritmul care a fost menționat anterior:

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

deci

$$ \ begin {array} {rcl} [ \! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ 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 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ gamma \ delta \\ \ end {array} $ $

și continuând în acest fel primesc $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

În rezumat: Dacă am propria mea concepție despre număr în termeni de șiruri de cifre de bază $ q $, atunci am modalitate de a interpreta numerele dvs. de la baza $ b $ în propriul meu sistem, pe baza operațiilor aritmetice fundamentale – care operează nativ în baza $ q $.

Comentarii

• Ei bine, asta a fost o mulțime de linii zgârcite. Cum aș face computerul să facă asta?
• @Griffin, cred că puneți această întrebare (ciudată) prematur. Alegeți un limbaj de programare și tastați algoritmul pentru adunare și multiplicare pe numere de bază q (reprezentate ca liste de cifre), apoi definiți o funcție pentru a interpreta cifrele de bază b în numere de bază q și interpretați numerele de bază b în numere de bază q. Am ‘ am explicat toate acestea.
• Lucrul este că știu conceptul pe care încerci să-l înfățișezi. Problema mea este că computerul meu nu poate ‘ să-ți folosească liniile zdrobitoare.
• Știu ce ai explicat, dar punerea în practică este mult mai dificilă. Vedeți că definirea acelor cifre nu este ‘ t la fel de ușoară.
• De ce ați scăzut cifra alfa în cea mai semnificativă poziție? Deoarece 6 = & xi ;, wouldn ‘ t 7 = & alpha; & alpha ;?

Acesta este un refactorizare (Python 3) din codul Andrej „s . În timp ce în numerele de cod ale lui Andrej sunt reprezentate printr-o listă de cifre (scalare), în următoarele coduri numerele sunt reprezentate prin o listă de simboluri arbitrare preluate dintr-un șir personalizat:

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) 

Pentru a efectua o conversie de la valoare la reprezentare într-o bază personalizată:

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

Pentru a efectua o conversie de la reprezentare (într-o bază personalizată) la valoare :

>>> 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 

Pentru a efectua o conversie de bază dintr-o bază personalizată în alta:

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

Comentarii

• Bine ați venit pe site și vă mulțumim pentru contribuția dvs. Cu toate acestea, producerea unui cod sursă bine optimizat nu este ‘ ceea ce înseamnă cu adevărat acest site. Codul Andrej ‘ s clarifică conceptele, ceea ce este necesar pentru răspunsul său, dar îmbunătățirea codului dincolo de aceasta este o chestiune de programare, mai degrabă decât știința computerului .
• @DavidRicherby Sunt parțial de acord, dar această contribuție a fost prea lungă pentru un comentariu și cel mai bun loc al său este undeva lângă răspunsul lui Andrej ‘, de aceea ‘ este motivul pentru care l-am postat aici. Oricum, dacă credeți că ‘ este mai bine, l-aș putea converti într-un comentariu cu un link către cod, dar nu ar fi ‘ un exces de purism?
• În ciuda @David ‘ s ” site-purist ” obiecții, am găsit util răspunsul dvs., deoarece subliniază faptul că bazele implicate pot fi gândite în termeni mai abstracte ca ” alfabete ” de simboluri arbitrare de lungimi diferite – și nelimitat la intervalul obișnuit de 2-36 de caractere. De fapt, ați putea considera fluxurile de octeți ca ” cifre ” ale valorilor întregi de bază 256.

/ div>

Răspuns

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 

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

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 

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] 

Răspuns

Răspunde