Matura - programowanie w C++

System liczbowy (ang. numbering system) określa metody zapisu liczb. Pierwsze systemy były bardzo prymitywne, później zmieniały się wolno w czasie w miarę jak rosła wiedza matematyczna ludzkości.

System karbowy

 

Potrzeba liczenia pojawiła się wraz z posiadaniem przedmiotów. Człowiek pierwotny nie odczuwał jej. Jako myśliwy nie mógł posiadać zbyt wiele. Rzeczy należało przenosić, więc jeśli czegoś było za dużo, po prostu pozostawiano to w miejscu obozowania. Duża liczba przedmiotów spowalniała myśliwego. Co za tym idzie, malały jego szanse na zdobycie pożywienia, a mógł również przez to sam stać się ofiarą. Jednak pewien prosty system liczenia pojawił się około 30.000 lat p.n.e. Był to system karbowy (ang. notch system). Polegał na żłobieniu w kościach karbów, których ilość oznaczała określoną liczbę. System ten stosowany jest w ograniczonej formie do dnia dzisiejszego, więc można go nazwać najdłużej używanym wynalazkiem człowieka.

Karby wyryte na kościach zwierząt

Początkowo dla wyrażenia jednostek stosowano pojedyncze kreski. Np. liczbę 18 zapisywano tak:

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \

Jednak zapis ten jest mało czytelny - porównaj go z zapisem np. liczby 17 czy 19. Można się pomylić? Oczywiście. Aby więc zwiększyć czytelność zapisu liczb co piątą kreskę stawiano pod innym katem od pozostałych. Teraz liczbę 18 zapisywano tak:

\ \ \ \/ \ \ \ \/ \ \ \ \/ \ \ \

Ilość kresek (karbów) jest taka sama, ale dzięki zaburzeniom łatwiej jest się zorientować w wartości liczby - są to trzy pełne piątki i trzy jednostki. Człowiek pierwotny, jeśli miał nazwy dla liczb, mógł to przeczytać jako trzy razy po pięć i trzy (trzy dłonie i trzy palce). Jeśli w liczbie tak zapisanej występowało dużo piątek, to co drugą piątkę zapisywano jeszcze inaczej, mianowicie tak:

\ \ \ \/ \ \ \ X \ \ \ \/ \ \ \

System Rzymski

System karbowy wyewoluował w znany nam dzisiaj system rzymski (ang. Roman numeral system). Rzymianie, jako ludzie praktyczni, uprościli zapis karbowy odrzucając niepotrzebne kreski po lewej stronie. W efekcie zapis liczby 18 wyglądał teraz tak:

XVIII

Pięknie - Rzymianie też byli z tego zadowoleni. Idąc za ciosem wymyślili dalsze reguły. Reguły te możemy zapisać następująco:

1. Liczby zapisujemy jako sumę cyfr o następujących wartościach:

2. Cyfry wypisujemy od strony lewej do prawej poczynając od największej.
   Teraz można już zapisywać w zgrabny sposób różne liczby:

3. Jeśli przed cyfrą starszą stoi cyfra młodsza, to należy ją odjąć od starszej.
   Rzymianom nie podobało się, iż muszą zapisywać liczbę 4 jako IIII, liczbę 9 jako VIIII itd. Wprowadzili więc pozorne uproszczenie systemu, czyli regułę 3. Teraz prościej można przedstawiać powyższe liczby:

O ile przedtem dodawanie można było wykonywać przez wspólne zapisanie cyfr obu dodawanych liczb, a następnie zastąpienie cyfr niższych wyższymi: 

MMCCCXXVI + MDCCXXVII = MMMDCCCCCXXXXVVIII = MMMDDXXXXXIII = MMMMLIII

to po zastosowaniu reguły 3 należało szalenie uważać, aby nie popełnić pomyłki. W rezultacie uproszczenie zapisu spowodowało skomplikowanie rachunków do tego stopnia, iż w średniowieczu liczenie na cyfrach rzymskich nauczane było na studiach wyższych.

4. Jeśli nad cyfrą umieszczono kreskę, to cyfra ta oznaczała liczbę tysięcy.
   Reguła ta pozwala zapisywać względnie duże liczby bez konieczności pisania wielu cyfr M. Na przykład liczbę 36.984 rzymski rachmistrz zapisywał następująco:

XXXVICMLXXXIV

Zgrabnie, nieprawdaż? Rzymianie byli naprawdę bardzo dumni ze swojego systemu zapisu liczb. Przetrwał on w ograniczonej formie nawet do dzisiaj przy zapisie dat lub numeracji rozdziałów, klas, sal, pięter, godzin itp. Jednak pomimo tych usprawnień system rzymski był ograniczony. Jak bowiem zapisać w tym systemie na przykład taką liczbę:

9426164130947320732385384038740846725325161632379864930747364030384752621 ?

System Babiloński

Cywilizacja babilońska rozkwitła w Mezopotamii wypierając wcześniejsze cywilizacje Sumerów i Akadyjczyków. Piętno Babilonu odcisnęło się na wielu cywilizacjach świata starożytnego, a jego echo jest obecne nawet w naszej kulturze. Babilończycy rozwinęli jako pierwsi system pozycyjny (ang. positional numeral system) o podstawie 60 (do dzisiaj dzielimy godziny na sześćdziesiąt minut, minuty na sześćdziesiąt sekund - czy kiedykolwiek zastanawiałeś się dlaczego?). Cechą systemu pozycyjnego jest ograniczona ilość cyfr. Te same cyfry są używane wielokrotnie w zapisie liczby. Wartość cyfry zależy od jej pozycji - stąd nazwa system pozycyjny.

Z naszego punktu widzenia system babiloński (ang. Babylonian numeral system) na pierwszy rzut oka może wydawać się skomplikowany - konieczność operowania aż 59 cyframi (cyfra zero nie była jeszcze znana ani stosowana). W rzeczywistości Babilończycy potrzebowali tylko dwóch symboli - dla jedności i dla dziesiątek. Ich cyfry były zbudowane właśnie z tych dwóch znaków zapisywanych końcem ostrej trzcinki na tabliczce glinianej, stąd pochodzi charakterystyczny, klinowy kształt pisma:

 
Cyfry babilońskie

Dlaczego wybrano podstawę 60? Prawdopodobnie zadecydowało to, że liczbę 60 można podzielić przez 2, 3, 4, 5, 6, 10, 12, 15, 20 i 30. System liczbowy o podstawie 60 nazywamy systemem sześćdziesiątkowym (ang. sexagesimal system).

W systemie babilońskim ostatnia cyfra oznaczała liczbę jednostek od 1 do 59. Gdy Babilończyk chciał zapisać liczbę 65, to używał dwóch cyfr (tak samo jak my przy zapisie liczby 15). Pierwsza cyfra 1 oznaczała jedną sześćdziesiątkę. Druga cyfra 5 oznaczała 5 jednostek:

Babilończycy nie używali cyfry 0. Zamiast niej po prostu zostawiano puste miejsce w zapisie liczby. Odpowiada to interpretacji zera przez ludy starożytne. Zero nie było traktowane jako liczba, ponieważ liczba określa ilość czegoś, a jeśli czegoś nie ma, to nie można mówić o ilości, nieprawdaż? Przecież rybak, który nie złowił żadnej ryby, nie przychodził do domu wołając radośnie od progu do żony "kochanie, dzisiaj złowiłem zero ryb!". Problem z pustym miejscem mógł się pojawiać, gdy w zapisie liczby dwie pozycje obok siebie były niezajęte. W późniejszym okresie Babilończycy wprowadzili w tym celu znak wypełniający, jednakże nie traktowali go nigdy jako cyfry 0.

Jeśli w zapisie liczby cyfr było więcej, to posiadały one wagi, które są kolejnymi potęgami liczby 60 – podstawy tego systemu:

numer pozycji	3	2	1	0
waga pozycji	603 = 216000	602 = 3600	601 = 60	600 = 1
cyfra
wartość cyfry	6	25	9	56

Wartość liczby uzyskamy mnożąc wagi pozycji przez wartości cyfr, które na tych pozycjach występują, a następnie sumując te iloczyny. Zwróć uwagę, że waga pozycji jest zawsze równa podstawie systemu podniesionej do potęgi równej numerowi pozycji (numerację rozpoczynamy od 0).

6 × 603 + 25 × 602 + 9 × 601 + 56 × 600 =
6 × 216000 + 25 × 3600 + 9 × 60 + 56 × 1 =
1296000 + 90000 + 540 + 56 = 1.386.596

Zauważ, że system babiloński pozwala bez problemu zapisywać dowolnie duże liczby (jakie wagi miałaby pozycje o numerach 4, 5, 6?). Jest zatem lepszy od systemu rzymskiego.

System Majów

Liczebniki Majów

Starożytni Majowie jako pierwsi na Ziemi odkryli dwie fundamentalne dla matematyki idee - system pozycyjny oraz koncepcję zera. Wynalezienie systemu pozycyjnego przypisuje się kulturze hinduskiej, lecz z badań historycznych wynika jasno, iż Majowie znali i stosowali system pozycyjny przynajmniej 300 lat wcześniej niż Hindusi.

Podstawą systemu liczbowego Majów była liczba 20. Dlaczego? Możemy się jedynie domyślać. Otóż w ciepłym klimacie Ameryki Majowie nie mieli potrzeby noszenia obuwia. Każdy człowiek posiada dwadzieścia palców - dziesięć u rąk i dziesięć u nóg. Prawdopodobnie ta własność naszego ciała wpłynęła na wybór podstawy systemu liczenia.

Do zapisu cyfr Majowie używali tylko trzech symboli (podobnie jak Babilończycy). Znak kropki oznaczał jednostkę. Pozioma kreska oznaczała piątkę (tyle mamy palców u ręki). Muszla oznaczała zero. Powyżej można zobaczyć w tabelce, jak wyglądały kolejne liczebniki Majów. Wartość liczby w tym systemie obliczamy mnożąc cyfry przez kolejne potęgi podstawy równej 20, i sumując te iloczyny częściowe.

Przykład

?

Pierwszą czynnością będzie zidentyfikowanie poszczególnych cyfr. Cyfry Majów były zapisywane od góry na dół. Spotyka się również zapis poziomy, ale wtedy cyfry są obrócone o 90 stopni. Porównując zapis liczby z tabelką odszukamy odpowiednie cyfry (można je też prosto obliczyć według podanych wcześniej reguł):

(2 + 5 + 5) = 12,
(2 + 5) = 7,
(4 + 5 + 5 + 5) = 19.

Teraz, znając podstawę systemu Majów, możemy przystąpić do obliczeń:

12 × 202 + 7 × 201 + 19 × 200 =
12 × 400 + 7 × 20 + 19 =
4800 + 140 + 19 = 4959

Zwróćmy uwagę, iż system Majów nie ma żadnego ograniczenia co do wielkości zapisywanych liczb. Przewyższa on więc system Rzymian. Kultury antyczne, pomimo posiadania wybitnych matematyków, nie odkryły idei systemu pozycyjnego. Zrobili to Majowie.

Kształt cyfr Majów sugeruje, iż stosowali oni do obliczeń prostą wersję liczydła, gdzie kamyczki (kropki) oznaczały jednostki, a patyczki (kreski) piątki. Sumowanie polegało na odpowiednim dodawaniu poszczególnych symboli (kropek - kamyków, kresek - patyczków), a następnie zastępowaniu ich symbolami wyższymi. Gdy ilość jednostek (kamyk) osiągnęła wartość 5, to zastępowano ją kreseczką (patyczek). Jeśli ilość piątek wyniosła 4 (=20), to patyczki zastępowano muszlą, a do następnej pozycji dodawano kamyczek.

System Arabski

Ciekawostką jest to, iż system dziesiętny został powszechnie przyjęty dopiero po ponad 200 latach od pojawienia się w Europie. Wcześniej korzystano z systemu rzymskiego. Wykonywanie rachunków w systemie rzymskim było bardzo skomplikowane i wymagało studiów matematycznych. Matematycy, uważając się za elitę, nie chcieli utracić swojej uprzywilejowanej pozycji na rzecz nowego systemu, w którym rachunki mogły wykonywać nawet dzieci. Ludzie nie zawsze przyjmują z entuzjazmem to, co jest lepsze (lepsze jest wrogiem dobrego).

Podstawę systemu dziesiętnego (ang. decimal system base) tworzy liczba 10. Jest to specjalna wartość charakteryzująca system pozycyjny, od której bierze on swoją nazwę: podstawa 10 - system dziesiętny.

Zapis liczby tworzymy za pomocą cyfr (ang. digits), czyli umownych znaków o przypisanych wartościach od 0 do 9. Ilość cyfr jest zawsze równa podstawie systemu, czyli w systemie dziesiętnym będzie ich dziesięć (0 1 2 3 4 5 6 7 8 9 ). Największa cyfra jest o 1 mniejsza od podstawy (9 = 10 - 1).

Cyfry umieszczamy na kolejnych pozycjach (ang. position) w zapisie liczby. Pozycje numerujemy poczynając od ostatniej, która ma numer (ang. index) 0. Każda pozycja posiada swoją wartość, którą nazywamy wagą pozycji (ang. position weight). Wagi pozycji są kolejnymi potęgami podstawy systemu, czyli w systemie dziesiętnym są to kolejne potęgi liczby 10:

Cyfra na danej pozycji określa ile razy należy wziąć wagę tej pozycji przy wyznaczaniu wartości całej liczby. Zatem w naszym przykładzie waga 1000 występuje 7 razy, waga 100 - 5 razy, waga 10 - 8 razy i waga 1 - 2 razy. Wartość liczby otrzymujemy sumując iloczyny cyfr przez wagi pozycji, na których cyfry te występują (czyli ilości tych wag):

7 × 1000 + 5 × 100 + 8 × 10 + 2 × 1

Jeśli pozycje ponumerujemy kolejno od 0 poczynając od prawej strony zapisu liczby, to waga pozycji i-tej będzie i-tą potęgą podstawy systemu. Np. pozycja nr 3 ma wagę 10³, czyli 1000, a pozycja nr 2 ma wagę 10², czyli 100.

Podane powyżej zasady obowiązują w każdym systemie pozycyjnym, dlatego warto je zapamiętać.

Z matematycznego punktu widzenia system dziesiętny nie jest jakimś wyróżnionym systemem zapisu liczb. Stosowany jest zapewne z uwagi na posiadanie dziesięciu palców, które w początkowym etapie nauki pełnią rolę swoistego komputera. Z drugiej strony dzieci uczą się liczb zapisywanych właśnie w tym systemie, dlatego zwykle pod pojęciem liczby rozumiemy jej zapis dziesiętny.

Aby zrozumieć inne systemy pozycyjne należy przyjąć do wiadomości, iż wartość liczby jest niezależna od sposobu jej zapisu. Dla przykładu weźmy pojęcie DOM, które w języku niemieckim zapisuje się DAS HAUS, w angielskim THE HOUSE, a w hiszpańskim LA CASA. Zapis za każdym razem jest inny, lecz znaczenie ma to samo. Przyjmijmy do wiadomości, iż inne systemy pozycyjne, to jakby inne języki, w których daną liczbę wyraża się inaczej niż w naszym systemie dziesiętnym, ale wartość liczby pozostaje taka sama.

Podane w poprzednim rozdziale zasady obowiązują w każdym systemie pozycyjnym o dowolnej podstawie. Jeśli je zrozumiesz, systemy pozycyjne przestaną być dla ciebie tajemnicą.

Oto charakterystyka dowolnego systemu pozycyjnego:

Niech podstawą będzie liczba naturalna p większa od 1 (dla p = 1 system pozycyjny degraduje się do systemu karbowego).

System posiada p cyfr: 0,1,2, ..., (p - 1). Ostatnia cyfra jest zawsze o 1 mniejsza niż podstawa p.

Kolejne wagi pozycji będą przyjmowały wartość kolejnych potęg podstawy systemu:

pozycja 0 - p⁰
pozycja 1 - p¹
pozycja 2 - p², itd.

Wynika stąd prosty wniosek, iż waga każdej następnej pozycji jest p-razy większa od wagi poprzedniej pozycji (dlaczego?).

Przykład:

Zwróć uwagę na ostatnią kolumnę. Wynika z niej, iż waga ostatniej pozycji w każdym systemie pozycyjnym jest taka sama (p⁰ = 1) i określa liczbę jednostek.

Wartość liczby obliczamy sumując iloczyny cyfr przez wagi ich pozycji. Stąd otrzymujemy wzór na wartość liczby w dowolnym systemie pozycyjnym.

Zapamiętaj

Wartość dziesiętna liczby zapisanej w systemie pozycyjnym o podstawie p za pomocą ciągu cyfr

Cn-1Cn-2...C2C1C0 wynosi Cn-1 pn-1 + Cn-2 pn-2 + ... + C2 p2 + C1 p1 + C0 p0

gdzie:

C - cyfra danego systemu o podstawie p
C_i - cyfra na i-tej pozycji, i = 0,1,2,...,n-1
n - ilość cyfr w zapisie liczby
p - podstawa systemu pozycyjnego

Jeśli znasz matematykę, to nasz wzór można zapisać prościej jako:

L - wartość liczby pozycyjnej o podstawie p

Ponieważ z doświadczenia wiem, iż uczniowie nie bardzo rozumieją ten prosty wzór, podaję krok po kroku metodę obliczania wartości liczby zapisanej w dowolnym systemie pozycyjnym.

Przykład:

Obliczyć wartość dziesiętną liczby szóstkowej 53214₍₆₎.

1. Ponad cyframi wypisujemy wagi pozycji, pamiętając, iż pozycje numerujemy od 0 z prawa na lewo. Wagi są kolejnymi potęgami podstawy systemu. Waga danej pozycji jest zawsze równa tej podstawie podniesionej do potęgi o wartości numeru pozycji.

2. Tworzymy sumę iloczynów cyfr przez wagi ich pozycji

= 5 × 64 + 3 × 63 + 2 × 62 + 1 × 61 + 4 × 60

3. Wyliczamy wagi kolejnych pozycji

= 5 × 1296 + 3 × 216 + 2 × 36 + 1 × 6 + 4 × 1

4. Obliczamy iloczyny cyfr przez wagi pozycji

= 6480 + 648 + 72 + 6 + 4

5. Sumujemy iloczyny i otrzymujemy wartość liczby

= 7210

I ostatecznie piszemy 53214₍₆₎ = 7210₍₁₀₎. Jeśli operujemy liczbami zapisanymi w różnych systemach pozycyjnych, to w celu uniknięcia niejednoznaczności liczbę opatrujemy indeksem dolnym, w którym umieszczamy wartość podstawy systemu zapisu danej liczby. Powyższa równość oznacza, iż zapis szóstkowy i dziesiętny oznacza tę samą liczbę.

Naturalny system dwójkowy (ang. NBS - Natural Binary System) jest najprostszym systemem pozycyjnym, w którym podstawa p = 2. System posiada dwie cyfry 0 i 1, zatem można je kodować bezpośrednio jednym bitem informacji. Wartość liczby obliczamy zgodnie ze wzorem podanym w poprzednim rozdziale.

Zapamiętaj:

Wartość dziesiętna liczby zapisanej w naturalnym kodzie binarnym

bn-1bn-2...b2b1b0 = bn-12n-1 + bn-22n-2 + ... + b222 + b121 + b020

gdzie

b - bit, cyfra dwójkowa 0 lub 1
n - liczba bitów w zapisie liczby

A bardziej matematycznie zapisujemy to tak:

L - wartość liczby dwójkowej w kodzie NBC

Przykład:

Obliczyć wartość liczby dwójkowej 11100101₍₂₎.

Obliczamy zgodnie ze wzorem:

11100101(2) = 1 × 27 + 1 × 26 + 1 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 0 × 21 + 1 × 20
11100101(2) = 1 × 128 + 1 × 64 + 1 × 32 + 0 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1
11100101(2) = 128 + 64 + 32 + 4 + 1
11100101(2) = 229(10)

Jeśli dokładnie przyjrzysz się powyższym obliczeniom, to na pewno zauważysz, iż w systemie binarnym w celu obliczenia wartości liczby wystarczy po prostu zsumować wagi pozycji, na których cyfry przyjmują wartość 1, ponieważ tam, gdzie występuje cyfra 0 wynikiem mnożenia będzie też 0.

Przykład:

101011(2) = 25 + 23 + 21 + 20 = 32 + 8 + 2 + 1 = 43(10)

Jest to znaczne uproszczenie w stosunku do innych systemów, gdzie musimy wykonywać mnożenia cyfr przez wagi pozycji. Tutaj albo dana waga występuje w wartości liczby (cyfra 1), albo nie występuje (cyfra 0). Nie na darmo system binarny jest najprostszym systemem pozycyjnym.

Bardzo ważne dla informatyka i programisty jest nauczenie się na pamięć pierwszych szesnastu liczb dwójkowych zapisywanych na 4 bitach:

 0

0000

 1

0001

 2

0010

 3

0011

 4

0100

 5

0101

 6

0110

 7

0111

 8

1000

 9

1001

10

1010

11

1011

12

1100

13

1101

14

1110

15

1111

Liczby te wykorzystują wszystkie kombinacje wartości bitów słówek 4-bitowych (4 bity dają 2⁴ kombinacji, czyli 16 słów). Zwróć uwagę, iż tego typu kod można łatwo konstruować, idąc kolejno od końca. Ostatnia cyfra kolejnych liczb binarnych zmienia się: 0 → 1 → 0 → 1... Przedostatnia cyfra zmienia się: 0 → 0 → 1 → 1 → 0 → 0... Kolejna na lewo podobnie: 0 → 0 → 0 → 0 → 1 → 1 → 1 → 1 → 0 → 0 → 0 → 0... itd. Widzisz już prawidłowość?

 0

0

0

0

0

 1

0

0

0

1

 2

0

0

1

0

 3

0

0

1

1

 4

0

1

0

0

 5

0

1

0

1

 6

0

1

1

0

 7

0

1

1

1

 8

1

0

0

0

 9

1

0

0

1

10

1

0

1

0

11

1

0

1

1

12

1

1

0

0

13

1

1

0

1

14

1

1

1

0

15

1

1

1

1

Również, jeśli zapamiętasz sobie wagi pozycji: 8 4 2 1, to kolejne liczby binarne można prosto utworzyć z odpowiednich sum wag:

 0

0

0

0

0

=0

 1

0

0

0

1

=1

 2

0

0

1

0

=2

 3

0

0

1

1

=2+1

 4

0

1

0

0

=4

 5

0

1

0

1

=4+1

 6

0

1

1

0

=4+2

 7

0

1

1

1

=4+2+1

 8

1

0

0

0

=8

 9

1

0

0

1

=8+1

10

1

0

1

0

=8+2

11

1

0

1

1

=8+2+1

12

1

1

0

0

=8+4

13

1

1

0

1

=8+4+1

14

1

1

1

0

=8+4+2

15

1

1

1

1

=8+4+2+1