Blog

Od matematyki do programowania

Czasem przeglądam sobie książkę „Od matematyki do programowania” Wiesława Rychlickiego. Autor podaje przykłady problemów matematycznych wraz z rozwiązaniem zarówno czysto matematycznym jak i programistycznym. Programy pisane są w trzech językach: Pascalu, C i C++.

Ja postaram się podać rozwiązania w JavaScripcie. Przede wszystkim dlatego, że każdy może sam sprawdzić kod, jako, że do tego wystarczy zwykły notatnik i jakakolwiek przeglądarka. Ze zwykłym notatnikiem to trochę przesada, przyda się zawsze kolorowanie składni, automatyczne wcięcia kodu, by był czytelny zarówno dla samego piszącego jak i kogoś, kto
go akurat przegląda (np notepad++, czy bardziej rozbudowany netbeans).

Zapis liczb w różnych systemach liczbowych

Od dziecka stosujemy w praktyce dziesiętny system liczbowy. Nawet się nie zastanawiamy nad tym, w jakim systemie przeprowadzamy nasze obliczenia, ani że mogą być jeszcze inne i to w dodatku stosowane w praktyce.  Zwłaszcza w elektronice system dwójkowy.

W dziesiętnym systemie liczbowym używamy dziesięć cyfr. Ilość cyfr jest równa podstawie danego systemu, np w dwójkowym są tylko dwie cyfry: 0 i 1, w trójkowym trzy: 0,1,2. Inaczej jest z systemem o podstawie większej od 10, np w systemie szesnastkowym używamy dziesięć cyfr z systemu dziesiętnego plus sześć liter alfabetu łacińskiego, a więc: 0-9 i A, B, C, D, E, F. Do każdego systemu liczbowego o większej podstawie należy po prostu dodać następne litery alfabetu łacińskiego. Gdybyśmy używali alfabetu polskiego, używalibyśmy też tak zwanych ogonków, a więc do sytemu szesnastkowego litery A, Ą, B, C, Ć, D. Całkiem ładna liczba szesnastkowa ĄĄ (BB – 187 w systemie dziesiętnym). Mnie się to podoba i szkoda, że tego nie wprowadzili do systemu szesnastkowego, bo wszyscy nauczyliby się alfabetu polskiego ; )

Od tej pory wyrażenie „liczba dziesiętna/dwójkowa/ósemkowa/szesnastkowa” będzie oznaczało „liczba w systemie dziesiętnym/dwójkowym/ósemkowym/szesnastkowym” i będzie używane zamiennie.

Jednak niezależnie od przyjętego systemu liczbowego – każdą liczbę zapisujemy w postaci:

$$L = \sum_{i=n}^0 A_i p^i = A_n p^n + A_{n-1} p^{n-1} + … + A_2 p^2 + A_1 p^1 + A_0 p^0$$

gdzie:

L – nasza liczba

n – ilość cyfr liczby

A_i – cyfra na i- tym miejscu licząc od prawej

p – podstawa systemu liczbowego

Przykłady zapisu liczb w różnych systemach liczbowych

System dziesiętny

Zapis w tym systemie znamy wszyscy. Nie zastanawiamy się nad nim, po prostu jesteśmy nauczeni operować na liczbach w tym systemie od dziecka. Dodajemy, odejmujemy, mnożymy, potęgujemy, pierwiastkujemy, potrafimy często znaleźć zależności pomiędzy dwoma czy więcej liczbami (np kiedy tworzą jakiś ciąg liczbowy). I cokolwiek z tych rzeczy robimy nie zastanawiamy się nad samą liczbą. W szkole uczyliśmy się: to jest cyfra jedności, to jest cyfra dziesiątek, to jest cyfra setek, to jest cyfra tysięcy. Oczywiście, od prawej do lewej, po… arabsku, można by powiedzieć. W końcu oni piszą od prawej do lewej, to pewnie stąd się wziął zapis liczb ; )

Niżej podam parę przykładów:

$$ 12345 = 1*10^4 + 2*10^3 + 3*10^2 + 4*10^1 + 5*10^0$$

$$1000005 = 1*10^6 + 0*10^5 + 0*10^4 + 0*10^3 + 0*10^2 + 0*10^1 + 5*10^0$$

System dwójkowy

W systemie dwójkowym podstawą jest liczba 2. I oczywiście – są tylko dwie cyfry – 0 i 1. Do tej pory wszystko jest proste. Jednak patrząc na liczbę dwójkową, wcale nie jesteśmy w stanie szybko określić jej wartości, gdyż przyzwyczajeni do systemu dziesiętnego, próbujemy policzyć ile to jest właśnie w tym systemie. Poniżej przykłady tych samych liczb tyle, że zapisanych w systemie dwójkowym (w nawiasie na dole wskazałem w jakim systemie liczba jest zapisana):

$$12345_{(10)} = 11000000111001_{(2)} = $$

$$1*2^{13} + 1*2^{12} + 0*2^{11} + 0*2^{10} + 0*2^9 + 0*2^8 +0*2^7 + 0*2^6 +$$

$$+ 1*2^5 + 1*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0$$

Nie jest to duża liczba, a zajmuje sporo miejsca. Zobaczmy dwójkowy zapis drugiej z liczb:

$$1000005_{(10)} = 11110100001001000101_{(2)} =$$

$$1*2^{19} + 1*2^{18} + 0*2^{17} + 0*2^{16} + 0*2^{15} + $$

$$+1*2^{14} + 0*2^{13} + 0*2^{12} + … + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 $$

Pominąłem środkową część potęg liczby 2. Wiadomo bowiem o co chodzi.

System ósemkowy

Tak, jak w pozostałych systemach liczbowych, tak tutaj podstawą jest liczba 8. I mamy 8 cyfr : od 0 do 7. Powyższe liczby w zapisie ósemkowym:

$$12345_{(10)} = 30071_{(8)} = 3*8^{4} + 0*8^{3} + 0*8^{2} + 7*8^{1} + 1*8^0$$

$$1000005_{(10)} = 3641105_{(8)} = 3*8^{6} + 6*8^{5} + 4*8^{4} + 1*8^{3} + 1*8^{2} + 0*8^{1} + 5*8^{0} $$

Weźmy liczbę dziesiętną 12345 w zapisie dwójkowym i ósemkowym.

$$12345_{(10)} = 11000000111001_{(2)} = 30071_{(8)}$$

Rozdzielmy sobie liczbę w zapisie dwójkowym na trójki cyfr jak poniżej:

11 000 000 111 001

W systemie ósemkowym używamy cyfr od 0 do 7. Każdą cyfrę systemu ósemkowego możemy zapisać trzema cyframi w zapisie dwójkowym. Tak więc każdą trójkę wyżej zapisanej liczby dwójkowej możemy odczytywać jako osobną trójkę cyfr w zapisie dwójkowym (zaczynając od prawej):

$$001_{(2)} = 1_{(8)}$$

$$111_{(2)} = 7_{(8)}$$

$$000_{(2)} = 0_{(8)}$$

$$000_{(2)} = 0_{(8)}$$

$$011_{(2)} = 3_{(8)}$$

Dlaczego trójki cyfr w zapisie dwójkowym dają cyfrę w systemie ósemkowym? Gdyż 2³ = 8. Jak już wcześniej napisaliśmy, maksymalną cyfrą w zapisie ósemkowym jest 7, a więc w zapisie dwójkowym jest to 111, czyli maksymalna trzycyfrowa liczba dwójkowa.

A więc, zapis dwójkowy poszczególnych trójek daje nam:

Jak widać, poszczególne trójki liczby dwójkowej dają nam tą samą liczbę w zapisie ósemkowym. Można zatem stosować tą metodę do szybkiej zamiany liczb dwójkowych na ósemkowe i odwrotnie.

System szesnastkowy

W systemie szesnastkowym liczby zapisujemy za pomocą szesnastu znaków: dziesięciu cyfr od 0 – 9 oraz sześciu liter: A, B, C, D, E, F.  (A = 10, B = 11, C = 12, D = 13, E = 14, F = 15).

Na przykład liczba AA₍₁₆₎:

$$AA_{(16)} = A*16^1 + A*16^0= 10*16 + 10 = 160 + 10 = 170_{(10)}$$

Weźmy te same liczby co poprzednio i zapiszmy je w systemie szesnastkowym.

$$12345_{(10)} = 3039_{(16)} = 3*16^{3} + 0*16^{2} + 3*16^{1} + 9*16^{0} $$

$$1000005_{(10)} = F4245_{(16)} = F*16^{4} + 4*16^{3} + 2*16^{2} + 4*16^{1} + 5*16^{0}$$

Weźmy znowu liczbę dziesiętną 12345 w systemie dwójkowym 11000000111001. Tym razem zapiszmy ją w postaci czwórek cyfr (analogicznie jak poprzednio dzieliliśmy na trójki):

11 0000 0011 1001

W drugiej linijce otrzymaliśmy zapis szesnastkowy naszej liczby. W ten sposób, liczbę dwójkową łatwo zamienić na szesnastkową. I odwrotnie.

Zamiana liczb między systemami.

Zamiana na system dziesiętny.

Tutaj sprawa jest prosta. Wystarczy daną liczbę zapisać jako sumę daną wzorem na początku artykułu.

I tak na przykład liczbę dwójkową 1001 możemy szybko zamienić na dziesiętną:

$$1001_{(2)} = 1*2^3 + 0*2^2 + 0*2^1 +1*2^0 = 8+0+0+1 = 9_{(10)}$$

Również bez problemów poradzimy sobie z liczbą w systemie ósemkowym na przykład 304:

$$304_{(8)} = 3*8^2 + 0*8^1 + 4*8^0 = 3*64 + 4 = 192 + 4 = 196_{(10)}$$

W ten sam sposób postępujemy przy zamianie liczby zapisanej w dowolnym systemie liczbowym na tą samą liczbę zapisaną w systemie dziesiętnym. Po prostu policzymy sumę iloczynów cyfry i podstawy systemu podniesionej po odpowiedniej potęgi.

Zamiana liczby z systemu dziesiętnego na inny.

W drugą stronę mamy większy problem.  Zacznijmy może od prostego przykładu. Powiedzmy, że chcemy liczbę dziesiętną 6₍₁₀₎ mieć w postaci dwójkowej. Możemy poszukać największej potęgi liczby 2 bliskiej naszej liczbie ale mniejszej lub równej od niej. 2³ = 8, to za dużo, przekracza szukaną liczbę, zostaje więc 2² = 4. Wiemy więc już, że nasza liczba będzie się składała z następujących potęg liczby 2: 2,1,0.  Co oznacza, że szukaną liczbę w dwójkową zapiszemy w sposób:

$$6_{(10)} = a*2^2 + b*2^1 + c*2^0 = abc_{(2)}$$

Teraz należy uzupełnić czynniki a, b, c. Cyfra a na pewno będzie równa 1. Mamy wtedy:

$$6_{(10)} = 1*2^2 + b*2^1 + c*2^0 = 4 + b*2 + c$$

Pozostaje nam znaleźć wartości b i c.  Przyjmijmy, że b = 1. Wtedy mamy:

$$6_{(10)} = 1*2^2 + b*2^1 + c*2^0 = 4 + 1*2 + c = 4 + 2 + c = 6 + c$$

Ostatecznie wychodzi nam równanie: 6 = 6+c, z czego wynika, że c=0. A skoro tak, to nasza liczba w systemie dwójkowym ma postać:

$$6_{(10)} = 110_{(2)}$$

Jako, że to jest mała liczba, można było przeprowadzić zamianę w opisany sposób.  Ale co zrobić, gdy mamy dużą liczbę, na przykład 123456789₍₁₀₎? Szukamy znowu największej potęgi liczby 2 mniejszej lub równej od tej właśnie liczby, potem uzupełniamy czynniki przed kolejnymi potęgami dwójki.  Trochę to czasochłonne. Istnieje za to lepszy sposób. Najlepiej zobrazować to na przykładzie. Też weźmiemy liczbę 6, później tą samą procedurę zastosujemy do liczb, które już przewinęły się w poprzedniej części artykułu.

Sposób jest prosty: dzielimy naszą liczbę przez 2. W wyniku otrzymujemy jakąś liczbę naturalną i resztę z dzielenia. Jako, że to jest dzielenie przez 2, reszta może przyjąć tylko dwie wartości: 0 lub 1. To pierwszy krok. W następnych krokach bierzemy liczbę otrzymaną z dzielenia w poprzednim kroku i ją dzielimy przez 2, otrzymując następną liczbę naturalną i resztę z dzielenia. Postępujemy tak, aż do otrzymania 0.  Wniosek – im większa liczba, tym więcej obliczeń. Ale to nic, sposób jest łatwy do opanowania. Dobrze, co teraz musimy zrobić, kiedy przeprowadzimy wszystkie operacje (otrzymując końcowy wynik równy 0 i jakąś resztę)?  Najważniejsze są właśnie te reszty z dzielenia, gdyż to one tworzą szukaną przez nas liczbę w postaci dwójkowej. Może tak zapisać: Zapisujemy te reszty od dołu, czyli od ostatniego kroku i otrzymujemy liczbę: 110₍₂₎. Otrzymaliśmy tą samą liczbę, co poprzednio, czyli wszystko się zgadza.

A co z liczbą 12345? Przyjrzyjmy się:

Zapisując od dołu reszty, otrzymujemy liczbę: 11000000111001

$$12345_{(10)} = 11000000111001_{(2)}$$

Dlaczego to działa w ten sposób? Aby sobie to uzmysłowić, spróbujmy „zamienić” liczbę dziesiątkową 12345 na… nią samą:

Jak widać, z reszt otrzymujemy poszczególne cyfry naszej liczby, zaczynając od ostatniej reszty. Stąd zapis liczby od ostatniej znalezionej reszty, do pierwszej czyli 12345.

Dokładnie tak samo postępujemy, zamieniając liczbę z systemu dziesiątkowego na każdy inny. zawsze bowiem będziemy dzielić naszą liczbę przez podstawę systemu liczbowego, na który chcemy zamienić liczbę dziesiątkową.

Spróbujmy teraz zamienić liczbę 12345₍₁₀₎ na szesnastkową.

Zapisując od dołu otrzymujemy 3039₍₁₆₎.

W ten sposób możemy zamienić liczbę dziesiątkową na liczbę w dowolnym systemie liczbowym.

Jak napisać odpowiedni algorytm – w następnej części:  Matematyka i programowanie – systemy liczbowe – Część 2