Przeszukiwanie ciągu liczbowego

Szukanie elementu

Często spotykanym rodzajem przeszukiwania jest wyszukiwanie elementu posiadającego pewną szczególną własność, jak np. najmniejszy, największy, podzielny przez jedenaście - element taki możemy nazwać idealnym.
Algorytm znajdowania elementu idealnego polega na wstępnym przyjęciu, że elementem idealnym jest pierwszy z dostępnych, a następnie na porównywaniu kolejnych elementów z elementem dotychczas uznanym za idealny. Jeśli podczas porównania okaże się, że element porównywany jest bliższy ideałowi niż dotychczasowy ideał, to wykonuje się zamianę przyjmując za ideał element aktualnie porównywany.

Przeszukiwanie binarne

Przeszukiwanie binarne jest algorytmem sprawdzającym czy uporządkowany rosnąco ciąg liczbowy N-elementowy zawiera szukaną liczbę x (nazywane jest też przeszukiwaniem połówkowym).
Algorytm przeszukiwania binarego wykorzystuje uporządkowanie ciągu liczbowego dzieląc go każdorazowo na połowy. Poszukiwaną liczbę x porównuje się z liczbą środkową ciągu i w zależności od wyniku tego porównania przeszukiwana jest albo lewa, albo prawa część tablicy. Obszar poszukiwania wyznaczają dwa indeksy: start i stop. oznaczają one odpowiednio początek i koniec przeszukiwanego fragmentu tablicy - rozpoczynając przeszukiwanie zmiennym tym przypisujemy wartości start:=1 i stop:=N, zakończenie przeszukiwania następuje gdy przeszukiwany fragment tablicy zmaleje do jednego elementu, to znaczy, gdy start=stop.

  DANE:

     a - przeszukiwana tablica (posortowana rosnąco)

     x - poszukiwana liczba

     N - rozmiar tablicy

  WYNIK:

  prawda, jeżeli tablica "a" zawiera liczbę "x"

1. Przyjmij: start:=1; stop:=N;
2. Dopóki start<stop;
• Wyznacz środek przedziału sr=(start+stop) Div 2,
• Jeżeli poszukiwana liczba x jest nie większa niż liczba w środku tablicy, to odrzuć prawą jej część przyjmując za stop:=sr;
• W przeciwnym wypadku odrzuć część lewą przyjmując za start:=sr+1;
3. Teraz start=stop, zwróć prawdę jeśli a[start]=x

Przeszukiwanie liniowe

Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.

Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do , gdzie  to całkowita liczba elementów. Algorytm ma złożoność .

Wyszukiwanie liniowe może być jedynym sposobem wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy.

Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową).

Dodatkowo jeśli wiadomo, że pewne klucze mogą być wyszukiwane częściej niż inne, można modyfikować kolejność danych, tak aby ponowne wyszukiwanie tego samego klucza kończyło się powodzeniem szybciej. Metoda ta nosi nazwę move-to-front, Donald Knuth wymienia w swojej pracy Sztuka programowania dwie strategie:

1. natychmiastowe przesunięcie znalezionego elementu na początek sekwencji,
2. przesunięcie tylko o jedną pozycję w stronę początku sekwencji.

Przeszukiwanie ciągu liczbowego z wartownikiem

Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej zadany element x. Niech będzie to tablica a o indeksach od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1], a[2], a[3], ..., a[n-1], a[n].Jeżeli przyjrzymy się dokładnie klasycznemu algorytmowi przeglądania tablicy w poszukiwaniuelementu:

zauważymy, że dla każdego elementu wykonywane są dwa porównania:

• pierwsze: czy znaleźliśmy się już na końcu tablicy,
• drugie: czy aktualnie przeglądany element jest równy poszukiwanemu.

Liczbę porównań można zredukować wykorzystując algorytm wyszukiwania z wartownikiem. Nazwa tego algorytmu bierze się ze sposobu, w jaki wykorzystywany jest element szukany x.

By odnaleźć element x podejmiemy następujące kroki:

• na końcu tablicy (czyli pod indeksem n+1) wstawimy szukany element x - będzie to nasz wartownik, w przypadku gdy nie znajdziemy go nigdzie indziej w tablicy, zabezpieczy nas on przed wyjściem poza tablicę,
• przejdziemy po kolejnych elementach tablicy, tak długo aż nie znajdziemy szukanego elementu,
• w momencie znalezienia szukanego elementu x sprawdzamy, który jest to element tablicy? Jeżeli jest to ostatni element tablicy (n+1) to trafiliśmy na naszego wartownika i oznacza to, że w tablicy nie było szukanego elementu x, w przeciwnym razie element x został odnaleziony.

Sito Eratostenesa

Sito Eratostenesa 

- przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału .

Ze zbioru liczb naturalnych z przedziału [2,n]\;, tj. \{2,3,4,\dots ,n\}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4,6,8,\dots .

                2             3             -4-          5             6             7             8             9             10

11           12           13           14           15           16           17           18           19           20

21           22           23           24           25           26           27           28           29           30

31           32           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6,9,12,\dots , przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

                2             3             -4-          5             6             7             8             9             10

11           12           13           14           15           16           17           18           19           20

21           22           23           24           25           26           27           28           29           30

31           32           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

Według tej samej procedury postępujemy dla liczby 5.

                2             3             -4-          5             6             7             8             9             10

11           12           13           14           15           16           17           18           19           20

21           22           23           24           25           26           27           28           29           30

31           32           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

                2             3             -4-          5             6             7             8             9             10

11           12           13           14           15           16           17           18           19           20

21           22           23           24           25           26           27           28           29           30

31           32           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

Wykreślanie powtarzamy do momentu, gdy liczba i\;, której wielokrotność wykreślamy, będzie większa niż {\sqrt  {n}}.

Dla danej liczby n\; wszystkie niewykreślone liczby mniejsze, bądź równe n\; są liczbami pierwszymi.

                2             3             -4-          5             6             7             8             9             10

11           12           13           14           15           16           17           18           19           20

21           22           23           24           25           26           27           28           29           30

31           32           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

 

#include <iostream>
using namespace std;
 
const int n = 100;
bool numbersTable[n + 1]={0}; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
 
int main()
{
    for (int i = 2; i*i <= n; ++i ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
    {
        if (numbersTable[i] == true) // jeżeli dana liczba jest już wykreślona
            continue; // to przejdź do kolejnej
        for (int j = 2*i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
            numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
    }
 
    cout << "Liczby pierwsze z przedziału od 2 do " << n << ":" << endl;
 
    for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
        if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
            cout << i << endl; // to ją wypisz
    return 0;
}

Badanie, czy liczba jest pierwsza.

Liczba pierwsza 

– liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.

Zbiór wszystkich liczb pierwszych oznacza się symbolem . Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone.

Podstawowe własności: 

• Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej, większej od jedności, jest liczbą pierwszą.
• Euklides pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych:

Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujących w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występująca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczbą pierwszą. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).

• Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero Gauss. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

Wyznaczanie

Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem zwanym sitem Eratostenesa: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka zN, to N jest liczbą pierwszą.

Schemat blokowy sprawdzający czy liczba jest pierwsza

Reprezentacja danych liczbowych w komputerze.

Reprezentacja binarna liczb ujemnych

Liczba ujemna w systemie dziesiętnym jest poprzedzona znakiem minus. W komputerze, każda informacja musi mieć postać ciągu zer i jedynek, dlatego znak liczby jest reprezentowany przez dodatkową cyfrę dwójkową, zwaną bitem znaku, która poprzedza właściwe cyfry liczby. Cyfra 1 na pozycji bitu znaku zastępuje tradycyjny znak minus w zapisie liczb ujemnych, a 0 występuje zawsze przed liczbami nieujemnymi. Bitu znaku liczby w reprezentacji binarnej nie można pominąć.

Zgodnie z tą umową, jeśli liczba jest reprezentowana na siedmiu bitach, włącznie z bitem znaku, to mamy (bit znaku został pogrubiony):

• 25 = 0011001
• -25 = 1011001

W reprezentacji dziesiętnej suma danej liczby i jej przeciwnej zawsze daje ten sam wynik - zero. Tak niestety nie jest, gdy ujemne liczby binarne różnią się od dodatnich tylko bitem znaku - przekonajcie się o tym, wybierając w tabeli kilka par liczb przeciwnych z trzeciej kolumny oraz odpowiadające im rozwinięcia binarne z pierwszej kolumny w tej tabeli.

Własność sumowania do zera pary liczb przeciwnych w zapisie binarnym ma reprezentacja uzupełnieniowa, zwana również kodem uzupełnieniowym. Tworzymy ją w następujący sposób. Dla dowolnej liczby całkowitej "a", jej reprezentacja uzupełnieniowa na "n" bitach, przeznaczonych na reprezentację, (włacznie z bitem znaku) ma postać:

• reprezentacja binarna liczby "a", gdzy a≤0
• reprezentacja binarna liczby 2ⁿ + "a", gdy a<0

W tym przypadku dla n=7 mamy:

• 25 = 0011001
• -25 = 1100111,

gdyż ma to być reprezentacja liczby 2⁷ +(-25) = 128 - 25 = 103,
Sprawdzimy, ile wynosi suma podanych wyżej liczb:

25 + (-25) = 0011001 + 1100111 = (1) 0000000

Wynik ograniczyliśmy do 7 bitów, bo na tylu bitach są pamiętne obie dodawane liczby, zatem pomijamy bit o wartości 1 powstały z przeniesienia.

Algorytm: Przedstawianie liczby ujemnej w reprezentacji uzupełnieniowej

Dane:
Binarne rozwinięcie liczby naturalnej "a" (wraz z bitem znaku równym 0).

Wynik:
Binarne rozwinięcie liczby przeciwnej -a (wraz z bitem znaku) w reprezentacji uzupełnieniowej.

Krok. Posuwając się od prawej do lewej, czyli w kierunku od najmniej znaczącego bitu, pozostawiaj bez zmian wszystkie początkowe bity równe zero  i pierwszy bit równy 1, a każdy następny bit zamień na przeciwny, czyli 0 na 1, a 1 na 0.

Reprezentacja stałopozycyjna liczb

• Reprezentacja stałopozycyjna charakteryzuje się stałym położeniem kropki dziesiętnej.
• Na część całkowitą liczby oraz na część ułamkową przeznaczona jest stała, z góry określona liczba bitów.
• Jeśli na część ułamkową przeznaczone jest 0 bitów to reprezentacja stałopozycyjna służy do przechowywania liczb całkowitych.
• Jeśli liczba, którą chcemy przedstawić w tej reprezentacji, mieści się na ustalonej liczbie bitów, to może być reprezentowana dokładnie.
• Jeśli wynik działań wykonywanych na liczbach stałopozycyjnych nie mieści się na ustalonej liczbie bitów, powstaje nadmiar w obliczeniach (wynik jest błędnie interpretowany przez komputer).

Mając do dyspozycji n bitów możemy w reprezentacji stałopozycyjnej przedstawić liczby całkowite z zakresu:
-2^n-1 .. 2^n-1-1

Przykład
n=8:    -2⁷ .. 2⁷-1, czyli -128 .. 127, odpowiada to typowi danych ShortInt (C++: char)
n=16:   -2¹⁵ .. 2¹⁵-1, czyli -32788 .. 32787, odpowiada to typowi danych Integer (C++: short)
n=32:   -2³¹ .. 2³¹-1, czyli -2 147 483 648 .. 2 147 483 647, odpowiada to typowi danych LongInt (C++: int)

Deklaracja odpowiedniego typu zmiennych w programie określa dopuszczalny zakres danych.

Reprezentacja zmiennopozycyjna liczb

• Reprezentacja zmiennopozycyjna charakteryzuje się zmiennym położeniem kropki dziesiętnej.
  Przykład

602252000000000000000000*101		wartość liczby jest w każdym przypadku taka sama, zmienia się tylko położenie kropki dziesiętnej
6,02252*1023
0,602252*1024
602252*1022

• W podobny sposób przedstawiane są liczby w formacie naukowym w arkuszu kalkulacyjnym: 4,92e³⁶, czyli 4,92*10⁺³⁶

Aby liczby zapisane w ten sposób można było porównywać ze sobą, stosuje się znormalizowaną reprezentację zmiennopozycyjną, gdzie liczba przedstawiona jest jako iloczyn

a=m*10^c

m - mantysa,  0,1<=|m|<1

c - cecha, liczba całkowita 

Przykład: 0,662607*10^-33

Podstawa matematyczna

Wartość liczby zmiennoprzecinkowej jest obliczana według wzoru:

gdzie:

• S (ang. sign) – znak liczby, 1 lub -1
• M (ang. mantissa) – znormalizowana mantysa, liczba ułamkowa
• B (ang. base) – podstawa systemu liczbowego (2 dla systemów komputerowych)
• E (ang. exponent) – wykładnik, liczba całkowita

Mantysa jest znormalizowana, tj. należy do przedziału  (przedział prawostronnie otwarty!). Jeżeli M jest stałe, a E zmienia się, wówczas przesunięciu ulega przecinek – stąd właśnie pochodzi nazwa tej reprezentacji.

Zarówno dla mantysy jak i wykładnika liczba cyfr jest z góry ustalona. Zatem dana liczba jest reprezentowana z pewną skończoną dokładnością i należy do skończonego zbioru wartości.

Systemy liczbowe

System liczbowy

 – zbiór reguł jednolitego zapisu i nazewnictwa liczb.

Do zapisywania liczb używa się skończonego zbioru znaków, zwanych cyframi, które można łączyć w dowolnie długie ciągi, otrzymując nieskończoną liczbę kombinacji.

System jedynkowy

Najbardziej prymitywnym systemem liczbowym jest jedynkowy system liczbowy, w którym występuje tylko jeden znak (np. 1, albo (częściej) pionowa kreska). W systemie tym kolejne liczby są tworzone przez proste powtarzanie tego znaku. Np. 3 w tym systemie jest równe 111, a pięć 11111. Systemem takim posługują się np. Pigmeje. Kiedy, w przypadku większych liczb, zaczyna się grupować symbole, np. po 5 (cztery równoległe kreski, przekreślone piątą), mamy do czynienia z przejściem do addytywnego systemu liczbowego.

Dziesiętny system liczbowy 

 – pozycyjny system liczbowy, w którym podstawą pozycji są kolejne wielokrotności liczby 10; do zapisu liczb potrzebne jest w nim 10 cyfr, którymi są 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Liczby zapisuje się jako ciąg cyfr, z których każda jest mnożnikiem kolejnej potęgi liczby stanowiącej podstawę systemu, niekiedy grupowanych po trzy (Okcydent) lub cztery (częśćOrientu). Część całkowitą i ułamkową oddziela separator dziesiętny.

Przykładowo zapis „645,7” z separatorem dziesiętnym w postaci przecinka oznacza

Pozycyjny, dziesiętny system liczbowy jest obecnie na świecie podstawowym systemem stosowanym niemal we wszystkich krajach. Oryginalnie pochodzi on z Indii, z których przedostał się do Europy za pośrednictwem Arabów. Od XVI wieku stosowano go obok systemu rzymskiego, w nauce, księgowościoraz tworzącej się właśnie bankowości, gdyż system ten znacznie upraszcza operacje arytmetyczne. W oficjalnych dokumentach jednak nadal zamieniano liczby w zapisie arabskim na system rzymski. W końcu, dzięki praktycznym zaletom system rzymski został prawie zupełnie wyparty na korzyść arabskiego.

Ósemkowy system liczbowy 

– pozycyjny system liczbowy o podstawie 8. System ósemkowy jest czasem nazywany oktalnym od słowa octal. Do zapisu liczb używa się w nim ośmiu cyfr, od 0 do 7.

Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciągi cyfr, z których każda jest mnożnikiem kolejnej potęgi liczby będącej podstawą systemu, np. liczba zapisana w dziesiętnym systemie liczbowym jako 100, w ósemkowym przybiera postać 144, gdyż:

1×8² + 4×8¹ + 4×8⁰ = 64 + 32 + 4 = 100.

W matematyce liczby w systemach niedziesiętnych oznacza się czasami indeksem dolnym zapisanym w systemie dziesiętnym, a oznaczającym podstawę systemu, np. 144₈ = 100₁₀.

Przykład zamiany liczby z systemu dziesiętnego na system ósemkowy:

• 100/8 = 12 i 4 reszty = 4
• 12/8 = 1 i 4 reszty = 4
• 1/8 = 0 i 1 reszty = 1

Teraz czytamy od dołu: 144 w systemie oktalnym to 100 w systemie dziesiętnym.

Dwójkowy system liczbowy, system binarny, bin 

– pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1.

Zmiany systemu

Zamianę z systemu dwójkowego na inny można wykonać poprzez zapisanie liczby jako sumy potęg liczby 2 pomnożonych przez wartość cyfry w systemie, na który przekształcamy. Przykładowo przy zamianie liczby na system dziesiętny:

Cyfra 1 podobnie jak w systemie dziesiętnym ma wartość zależną od swojej pozycji - na końcu oznacza 1, na drugiej pozycji od końca 2, na trzeciej 4, na czwartej 8, itd. Ponieważ  oraz  aby obliczyć wartość liczby zapisanej dwójkowo, wystarczy zsumować potęgi dwójki odpowiadające cyfrom 1 w zapisie.

Zamiana liczby w systemie dziesiętnym na liczbę w systemie dwójkowym może przebiegać według wyżej opisanej zasady, czyli:

Rozbicie na sumę potęg liczby 2 na przykład

Bądź też przez wyznaczanie reszt w wyniku kolejnych dzieleń liczby przez 2:

30 ÷ 2 = 15 reszty 0 - 0 to cyfra jedności,

15 ÷ 2 = 7 reszty 1 - 1 to cyfra drugiego rzędu,

7 ÷ 2 = 3 reszty 1

3 ÷ 2 = 1 reszty 1

1 ÷ 2 = 0 reszty 1

Aby obliczyć wartość dwójkową liczby przepisujemy od końca cyfry reszt. Tak więc .

Szesnastkowy system liczbowy, system heksadecymalny, hex 

– pozycyjny system liczbowy, w którym podstawą jest liczba 16. Skrót hex pochodzi od angielskiej nazwy hexadecimal. Do zapisu liczb w tym systemie potrzebne jest szesnaście znaków (cyfr szesnastkowych).

W najpowszechniejszym standardzie poza cyframi dziesiętnymi od 0 do 9 używa się pierwszych sześciu liter alfabetu łacińskiego: A, B, C, D, E, F (wielkich lub małych). Cyfry 0-9 mają te same wartości co w systemie dziesiętnym, natomiast litery odpowiadają następującym wartościom: A = 10, B = 11, C = 12, D = 13, E = 14 oraz F = 15.

W kalkulatorach naukowych o siedmiosegmentowych wyświetlaczach LCD stosuje się następujące oznaczenia kolejnych cyfr szesnastkowych: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, b, C, d, E, F (b i d, zamiast B i D dla rozróżnienia wyświetlania, które wyglądają jak 8 i 0).

Istnieją również projekty ujednolicenia zapisu i wprowadzenia zupełnie nowych cyfr, przeznaczonych dla tego systemu.

Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciągi znaków, z których każdy jest mnożnikiem kolejnej potęgi liczby stanowiącej podstawę systemu. Np. liczba zapisana w dziesiętnym systemie liczbowym jako 1000, w systemie szesnastkowym przybiera postać 3E8, gdyż:

Zastosowanie w informatyce

Z racji reprezentacji liczb w pamięci komputerów za pomocą bitów, najbardziej naturalnym systemem w informatyce jest dwójkowy system liczbowy.

W okresie pionierskich czasów komputeryzacji ważną rolę odgrywał system ósemkowy, który spotyka się niekiedy do dziś.

Natomiast naturalny dla ludzi system dziesiętny został wprowadzony dopiero wraz z powstaniem języków programowania wyższego poziomu, których celem było jak największe ułatwienie w korzystaniu z komputerów.

Ze względu na specyfikę architektury komputerów, gdzie często najszybszy dostęp jest do adresów parzystych, albo podzielnych przez 4, 8 czy 16, często używany jest szesnastkowy system liczbowy. Sprawdza się on szczególnie przy zapisie dużych liczb takich jak adresy pamięci, zakresy parametrów itp. Na przykład:

2¹⁶ = 65536₁₀ = 10000₁₆

2³² = 4294967296₁₀ = 100000000₁₆

10000₁₆ i 100000000₁₆ są znacznie łatwiejsze do zapamiętania.

System szesnastkowy często spotykany jest też na stronach WWW (HTML), gdzie stosowany jest do zapisu kolorów.

Przykład konwersji

Przykład rekurencyjnej funkcji w C/C++, konwertującej liczby naturalne na system trójkowy:

void triple (int liczba)

{

     int reszta = liczba %3;

     if(liczba>1) triple (liczba/3);

     cout<<reszta;

     return;    

}

Konwersja części ułamkowej liczby polega na mnożeniu jej przez podstawę nowego systemu i odpisywaniu powstałej części całkowitej.

Schemat blokowy konwersji liczby dziesiętnej na binarną.

Metoda - dziel i zwyciężaj.

Dziel i zwyciężaj (ang. divide and conquer) 

– jedna z głównych metod 

projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.

Klasyczne przykłady algorytmów korzystających z tej metody to m.in. sortowanie przez scalanie (mergesort), sortowanie szybkie (quicksort), wyszukiwanie binarne (binary search).

Język programowania - C++

 

 

 Język programowania- zbiór zasad określających, kiedy ciąg symboli tworzy program komputerowy oraz jakie obliczenia opisuje.

 Język programowania może być zdefiniowany ze względu na kilka cech: 

• Funkcja: Język programowania służy do tworzenia programów komputerowych, których zadaniem jest przetwarzanie danych, wykonywanie obliczeń i algorytmów oraz kontrolowanie/obsługa zewnętrznych urządzeń, np. drukarek, robotów itd.
• Przeznaczenie: Języki naturalne służą do komunikacji między ludźmi, natomiast języki programowania umożliwiają wydawanie poleceń maszynom. Niektóre z języków są wykorzystywane również do kontrolowania jednego urządzenia przez inne. Przykładowo, program wykonywany na komputerze może wygenerować kod PostScript do sterowania pracą drukarki bądź wyświetlacza.
• Konstrukcje składniowe: Język programowania może zawierać konstrukcje składniowe do manipulowania strukturami danych oraz zarządzania przepływem sterowania.
• Moc: Teoria obliczeń klasyfikuje języki według rodzajów obliczeń, które można za ich pomocą zrealizować (hierarchia Chomsky'ego). We wszystkich językach zupełnych w sensie Turinga da się zaimplementować ten sam zbiór algorytmów. Przykładem często stosowanego języka niezupełnego jest SQL służący do komunikacji z bazą danych.

Interpreter- program komputerowy, który analizuje kod źródłowy programu, a przeanalizowane fragmenty wykonuje.

Realizowane jest to w inny sposób niż w procesie kompilacji, podczas którego nie wykonuje się wejściowego programu (kodu źródłowego), lecz tłumaczy go do wykonywalnego kodu maszynowego lub kodu pośredniego, który jest następnie zapisywany do pliku w celu późniejszego wykonania.
Wykonanie programu za pomocą interpretera jest wolniejsze, a do tego zajmuje więcej zasobów systemowych niż wykonanie kodu skompilowanego, lecz może zająć relatywnie mniej czasu niż kompilacja i uruchomienie. Jest to zwłaszcza ważne przy tworzeniu i testowaniu kodu, kiedy cykl edycja-interpretacja-debugowanie może często być znacznie krótszy niż cykl edycja-kompilacja-uruchomienie-debugowanie.
Interpretacja kodu jest wolniejsza niż uruchamianie skompilowanego kodu, ponieważ interpreter musi analizować każde wyrażenie i następnie wykonać akcję, a kod skompilowany jedynie wykonuje akcję. W implementacjach będących w pełni interpreterami wykonanie wielokrotne tego samego fragmentu kodu wymaga wielokrotnej interpretacji tekstu. Ta analiza nazywana jest "kosztem interpretacji". Dostęp do zmiennych jest także wolniejszy w interpreterze, gdyż odwzorowanie identyfikatorów na miejsca w pamięci operacyjnej musi zostać dokonane podczas uruchomienia lub działania, a nie podczas kompilacji. Dlatego niektóre interpretery tworzą dodatkowe dane (np. adresy zmiennych) przyspieszające wykonanie programu.

 Kompilator- program służący do automatycznego tłumaczenia kodu napisanego w jednym języku (języku źródłowym) na równoważny kod w innym języku (języku wynikowym). Proces ten nazywany jest kompilacją. 

W informatyce kompilatorem nazywa się najczęściej program do tłumaczenia kodu źródłowego w języku programowania na język maszynowy. Niektóre z nich tłumaczą najpierw do języka asemblera, a ten na język maszynowy jest tłumaczony przez asembler..
Stosowanie kompilatorów ułatwia programowanie (programista nie musi znać języka maszynowego) i pozwala na większą przenośność kodu pomiędzy platformami.

Język niskiego poziomu– typ języka programowania, który w małym stopniu abstrahuje od konstrukcji jednostki centralnej komputera. Innymi słowy, język ten wykazuje duże podobieństwo do kodu maszynowego, zaś kompilacja jest w miarę nieskomplikowana.

Występuje pewna względność ocen: język C może być oceniany jako język wysokiego poziomu przez programujących w asemblerze, lecz jako język niskiego poziomu przez używających Javy. Pewnym obiektywnym miernikiem wysokości poziomu języka może być to, jak bardzo jest on niezależny od tego, jak działa komputer. W asemblerze operujemy bezpośrednio na rejestrach komputera, w C piszemy programy za pomocą pewnych instrukcji, natomiast Java i inne języki obiektowe pozwalają nam posługiwać się zdarzeniami występującymi między obiektami. W języku tym praktycznie nie widzimy w żaden sposób budowy komputera.
Najbardziej typowym przykładem języka niskiego poziomu jest asembler.

Asembler jest językiem niskiego poziomu i nie jest już powszechnie wykorzystywany przez programistów tworzących popularne aplikacje.

Programista Asemblera nie musi już co prawda używać wyłącznie zer i jedynek, jednak programowanie w Asemblerze nadal jest trudne i wymaga dużej wiedzy i cierpliwości.

 Język wysokiego poziomu(autokod) – typ języka programowania, którego składnia i słowa kluczowe mają maksymalnie ułatwić rozumienie kodu programu dla człowieka, tym samym zwiększając poziom abstrakcji i dystansując się od sprzętowych niuansów. 

Kod napisany w języku wysokiego poziomu nie jest bezpośrednio „zrozumiały” dla komputera – większość kodu stanowią tak naprawdę normalne słowa, np. w języku angielskim. Aby umożliwić wykonanie programu napisanego w tym języku należy dokonać procesu kompilacji.

Podział ze względu na zastosowanie

Języki programowania dzielimy na:

• wewnętrzne
• maszynowe(Java,NET)
• algorytmiczne (Pascal, częściowo C), 
• języki czwartej generacji (w tym niektóre języki do tworzenia aplikacji na bazie danych np. SQL)

Grupy języków programowania

• Bazodanowe:
  dBase, Clipper, FoxPro, Access, Delphi, SQL-owe (np. Oracle).
  Ukierunkowanie na tworzenie aplikacji baz danych (zbiór informacji jednorodnych, łatwiej dopisywać informacje, dostosowanie do pracy w sieci, sortowanie)
  
• Obliczeniowe (naukowo techniczne, statystyka), np.
  Fortran (są biblioteki do grafiki),
  Pascal,
  C/C++ (ojciec Pascal, matka assembler), podobny do UNIXa, wykonuje instrukcje nie dyskutuje.
  Jest jakby językiem uniwersalnym, właściwości sieciowe.C++ cechuje obiektowość. Gorzej z zastosowaniami bazodanowymi, biblioteka funkcji matematycznych mniejsza niż w Fortranie.
• Specjalizowane: sztuczna inteligencja, systemy ekspertowe, przetwarzanie list, do symulacji procesów
  
• Języki typu "Visual" (np. Visual C++,  C#, Visual Basic, Delphi)