Przejdź do głównej zawartości

Python - lekcja 005

Spis treści
- zamiana całkowitych liczb dziesiętnych na ich odpowiedniki w innych systemach liczbowych (algorytm),
- ujemne liczby całkowite w systemie binarnym (ZM, U1, U2, algorytm, formatowanie stringów, rzutowanie ze zmianą systemu liczbowego) [dec2bin, dec2ZM, dec2U1, dec2U2]
- zadania.

Poprzednia lekcja: Lekcja 4 (pętle)
 

Zamiana liczby dziesiętnej na jej odpowiednik binarny nie jest skomplikowana. Wystarczy sprawdzać reszty z dzielenia przez 2 a następnie dzielić przez 2 tę liczbę. Powyższe kroki należy powtarzać aż przekształcana liczba stanie się zerem. Ostatnim krokiem będzie wypisanie otrzymanych reszt w kolejności od ostatniej do pierwszej.

1
2
3
4
5
6
7
8
liczbaDziesietna = int(raw_input())

wynik = ""

while liczbaDziesietna > 0:
    wynik = str(liczbaDziesietna % 2) + wynik
    liczbaDziesietna = liczbaDziesietna / 2
print wynik

Co zrobić gdy chcemy przekształcić daną liczbę dziesiętną do postaci np. siódemkowej (podstawą systemu jest 7)? Dokładnie to samo. Zmieni się jedynie dzielnik w algorytmie:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
liczbaDziesietna = int(raw_input())

wynik = ""

while liczbaDziesietna > 0:

    wynik = str(liczbaDziesietna % 7) + wynik

    liczbaDziesietna = liczbaDziesietna / 7

print wynik


Problem zacznie się dopiero gdy będziemy chcieli zamieniać liczby na system, którego podstawa jest większa niż 10. W przypadku takich systemów reszta z dzielenia danej liczby dziesiętnej przez podstawę docelowego systemu liczbowego może być większa lub równa 10. Reszty stanowią cyfry w nowych systemach więc pojawia się problem gdyż 10 to już dwie cyfry a nie jedna. W celu rozwiązania tego problemu ustalono, że cyfry o wartościach wyższych od 9 reprezentowane będą przez kolejne litery rozszerzonego alfabetu łacińskiego.
Na przykład w systemie szesnastkowym mamy następujące cyfry 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
liczbaDziesietna = int(raw_input())

cyfry = "0123456789ABCDEF"

wynik = ""

while liczbaDziesietna > 0:

    wynik = cyfry[liczbaDziesietna % 16] + wynik

    liczbaDziesietna = liczbaDziesietna / 16

print wynik

Aby przedstawiać liczby ujemne w systemie binarnym wprowadzono kilka standardów:
- znak-moduł (ZM),
- uzupełnienie do 1 (U1),
- uzupełnienie do 2 (U2).

ZM

Pierwszy z nich, czyli ZM, jest najprostszy w interpretacji. Gdy mamy do czynienia z liczbą 2 przedstawiamy ją w postaci binarnej:
10
W kolejnym kroku należy ustalić na ilu bitach ma być przedstawiona liczba np. 8 czyli teraz wygląda ona następująco:

00000010

Gdybyśmy chcieli zaprezentować liczbę ujemną to najbardziej znaczący bit musi przyjąć wartość 1. Czyli -2 w systemie ZM opisana na 8. bitach wygląda następująco: 

10000010

Najbardziej znaczący bit jest zarezerwowany na znak i nie można w nim umieszczać elementów należących do bezwzględnej wartości liczby np. 10[ZM] to 0[10] a nie 2[10]. Aby zaprezentować 2[10] musimy przeznaczyć na to trzy bity: 010[ZM]. Zero na pierwszym miejscu informuje nas o tym, że mamy do czynienia z liczbą nieujemną.

Żeby nie pisać w kółko algorytmu zamieniającego liczby dziesiętne na binarne użyję formatowania tekstu wbudowanego w język Python:

print "int: {0:d};  hex: {0:x};  oct: {0:o};  bin: {0:b}".format(42)

gdzie
{0:d} - przedstaw pierwszy atrybut formatowania w postaci dziesiętnej,
{0:x} - przedstaw pierwszy atrybut formatowania w postaci szesnastkowej,
{0:o} - przedstaw pierwszy atrybut formatowania w postaci ósemkowej,
{0:b} - przedstaw pierwszy atrybut formatowania w postaci binarnej.

Więcej informacji: http://docs.python.org/dev/library/string.html

Kod zamieniający liczbę całkowitą z sytemu dziesiętnego na tą samą liczbę w systemie ZM:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
liczbaDziesietna = int(raw_input())

ujemna = 0

if liczbaDziesietna < 0:

    ujemna = 1

    liczbaDziesietna = - liczbaDziesietna

print ("1" if ujemna else "0") + "{0:b}".format(liczbaDziesietna) + "[ZM]"

U1

Teraz zajmiemy się standardem U1. W tym sposobie prezentowania liczb binarnych również musimy zapewnić przynajmniej jeden bit więcej w którym zapisana będzie informacja o znaku liczby. Ponownie 0 informuje o liczbach nieujemnych a 1 o ujemnych. W stosunku do ZM różni się tym, co znajduje się na kolejnych bitach. Ponownie przeanalizujemy przykład z 2[10]. Dwójka w U1 wygląda następująco: 010. Czyli tak samo jak w ZM. Aby przedstawić -2[10] należy zanegować wszystkie bity w 2[U1]:

 - 010 = not(101) = 101.

Wartość ujemnych licz zapisanych w formacie U1 można przekształcić na system dziesiętny przynajmniej na dwa sposoby:
1. przeprowadzamy negację wszystkich bitów, przekształcamy tę liczbę tak jakby była zapisana w naturalnym kodzie binarnym na system 10 i dopisujemy przed nią znak "-"
2. korzystamy ze wzoru:

bn-1bn-2bn-3...b2b1b0 [U1] = bn-1(-2n-1+1) + bn-22n-2 + bn-32n-3 + ... + b222 + b121 + b020

przykład użycia:  

1011[U1] =  (-23+1) + 21 + 20 = -7 + 2 + 1 = -4[10]

Skrypt zamieniający liczbę dziesiętną na jej reprezentacje w U1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
liczbaDziesietna = int(raw_input())
ujemna = 0

if liczbaDziesietna < 0:
    ujemna = 1
    liczbaDziesietna = - liczbaDziesietna

wynikPosredni = "0" + "{0:b}".format(liczbaDziesietna)

wynik = ""

if ujemna:
    for znak in wynikPosredni:
        if znak == "1":
            wynik = wynik + "0"
        else:
            wynik = wynik + "1"
else:
    wynik = wynikPosredni

print wynik + "[U1]"

U2 

Nadszedł czas na ostatni z typów zapisu jakim jest U2. W tym systemie liczby dodatnie tworzy się tak samo jak w ZM i U1. Aby w tym systemie przedstawić liczbę ujemną najpierw tworzymy liczbę dodatnią (tak jak w ZM i U1) a następnie wykonujemy negację typów (tak jak w U1). Do tak przygotowanej liczby dodajemy (algebraicznie) 1.

Przykład dla 2:

2[10] = 010[U2]

Przykład dla -2:
 
-2[10]

not(010) + 1 = 101 + 1 = 110[U2] 

Skrypt zamieniający całkowitą liczbę dziesiętną na jej reprezentacje w systemie U2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
liczbaDziesietna = int(raw_input())
ujemna = 0

if liczbaDziesietna < 0:
 ujemna = 1
 liczbaDziesietna = - liczbaDziesietna

wynikPosredni = "0" + "{0:b}".format(liczbaDziesietna)
wynik = ""

if ujemna:
 for znak in wynikPosredni:
  if znak == "1":
   wynik = wynik + "0"
  else:
   wynik = wynik + "1"
 wynik = int(wynik,2)
 wynik += 1;
 wynik = "{0:b}".format(wynik)
else:
 wynik = wynikPosredni

print wynik + "[U2]"

W powyższym kodzie wykorzystałem nową rzecz jaka jest rzutowanie wraz ze zmianą systemu liczbowego (linia 17):

wynik = int(wynik,2)

W tej instrukcji informuję, że string zawierający liczbę odpowiada naturalnej reprezentacji binarnej.
Aby nie męczyć się z dodawaniem w systemie binarnym zamieniam liczbę binarną zapisana w systemie U1 na system dziesiętny i dopiero w tym systemie dodaję 1. Tak przygotowaną liczbę traktuję jako dodatnią liczbę zapisaną w naturalnym kodzie binarnym. Znacząco ułatwia to analizę kodu.

Aby zmienić system wyświetlania z U2 na dziesiętny można użyć poniższy wzór:

bn-1bn-2bn-3...b2b1b0 [U2] = bn-1(-2n-1) + bn-22n-2 + bn-32n-3 + ... + b222 + b121 + b020


Zadania

1. Napisz skrypt, który zamieni dodatnią liczbę całkowitą na jej odpowiednik w podanym przez użytkownika systemie liczbowym (zakres systemów od 2 do 32).

2. Zamień następujące liczby  na system ZM, U1 i U2:

a. 10[10]
b. 10[2]
c. -13[10]
d. - abc[16]
e. 192[10]
f. -192[10]

3. Napisz skrypty zamieniające liczby podane w systemach:
a. ZM
b. U1
c. U2 [odpowiedź]
na ich reprezentacje w systemie dziesiętnym

4. Który z systemów zapisu liczb binarnych daje możliwość zapisu dodatniego i ujemnego zera?



Komentarze

guest pisze…
wszystko fajnie ale nie działają twoje kody
Unknown pisze…
moze wystarczy zrobic wciecia dobre
Stefan pisze…
Poprawny kod, np.
def bin(liczba):
wynik=""
while liczba > 0:
wynik = str (liczba%2) + wynik
liczba = int(liczba/2)
print(wynik)

Testowane;-)

Unknown pisze…
Powinno być int(liczba//2)

Popularne posty z tego bloga

[C++]Konwersja systemu dziesiętnego na binarny [dec2bin, dec2u2]

Konwersja między systemami liczbowymi była już poruszana w tym serwisie tym razem zajmę się kodem U2. Inaczej zwany uzupełnieniem do 2. Opis tego systemu pojawił się w kontekście wstępu do programowania w języku Python [ tutaj ]. Prosty program tzw. szkolny zamiany nieujemnej liczby dziesiętnej na jej postać binarną: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> using namespace std; int main () { int liczba; cin >> liczba; string wynik; while (liczba){ wynik = (liczba % 2 ? "1" : "0" ) + wynik; liczba /= 2 ; } cout << wynik; return 0 ; } Poniżej prezentuję kod programu, który zawiera trzy metody rozwiązania problemu jakim jest wyświetlenie użytkownikowi reprezentacji u2 podanej przez niego liczby dziesiętnej. Pierwsza z nich wywodzi się z typowego algorytmu konwersji systemu dec do u2: 1. przedstaw bezwzględną wartość liczby dziesiętnej w postaci binarnej, 2. dodaj na początek