niedziela, 2 marca 2014

Poszukiwanie 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 poszukiwaniu elementu:

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.

W stosunku do klasycznego algorytmu wyszukiwania oszczędzamy czas na sprawdzaniu czy osiągnęliśmy koniec tablicy. Sprawdzenie to występuje raz - po odnalezieniu elementu szukanego, a nie tak jak poprzednio przed każdym sprawdzeniem kolejnego elementu.

Algorytm ten mimo, że jest szybszy od zwykłego wyszukiwania to ma taką samą jak on złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Podczas implementowania tego rozwiązania należy zapewnić miejsce w tablicy potrzebne do dodania wartownika. Należy więc deklarować tablicę o rozmiarze o jeden większym jak liczba przechowywanych elementów.

Poszukiwanie ciągu liczbowego

Algorytmy przeszukiwania

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.

Poniższy fragment kodu znajduje w ciągu liczb podawanych przez użytkownikaliczbę największą:

Write('Podaj pierwsza liczbę ciągu = ');ReadLn(Maksymalny);For I:=2 To N Do  Begin    Write('Kolejna liczba = ');    ReadLn(Liczba);    If Liczba>Maksymalny Then Maksymalny:=Liczba;  End;

Niżej przykłady programów szukających: podzielne, podzielne2, Ile_razy, liczby pierwsze.

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 gokaż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"

Przyjmij: start:=1; stop:=N;
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;
Teraz start=stop, zwróć prawdę jeśli a[start]=x.

Sprawdzanie czy liczba jest liczbą pierwszą

Liczba pierwsza to taka liczba naturalna większa od 1, która dzieli się tylko przez 1 i samą siebie. Oto kilka liczb pierwszych:

Warto zauważyć, że takich liczb jest nieskończenie wiele.

Aby określić, czy dana liczba jest pierwsza należy zbadać jej dzielniki. Dla zadanej liczby n sprawdzamy kolejne liczby naturalne należące do przedziału:

Jeśli któraś z tych liczb jest dzielnikiem, oznacza to, że nasza liczba nie jest pierwsza.

Zmienopozycyjna reprezentacja liczb

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

602252000000000000000000*10¹		wartość liczby jest w każdym przypadku taka sama, zmienia się tylko położenie kropki dziesiętnej
6,02252*10²³
0,602252*10²⁴
602252*10²²

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

1.Binarna reprezentacja liczby zmiennopozycyjnej

liczba przedstawiona jest jako iloczyn a=m*2^c
Mantysa i cecha pamiętane są w reprezentacji stałopozycyjnej (liczba pamiętana jest jako dwa składniki)
Przykład:
znak liczby - najstarszy bit zarezerwowany jest dla zapisu znaku całej liczby
cecha ze znakiem - 6 bitów
mantysa - 8 bitów

0 000101 10010000

znak liczby: +
cecha = +5
mantysa = 1/2 + 1/16 =0,5625
liczba: 0,5625 * 2⁵ = 18

2.Zamiana liczby na postać binarną w znormalizowanej reprezentacji zmiennopozycyjnym

Liczba: 5,5
znak liczby +
cecha ze znakiem - 7 bitów
mantysa - 8 bitów

przedstawiamy liczbę jako iloczyn, gdzie jednym z czynników jest najmniejsza potęga liczby 2, nie mniejsza od tej liczby:
5,5 = x* 2³=0,6875*2³
x=5,5/8=0,6875
znak liczby +
cecha liczby +3
mantysa liczby 0,6875
przedstawiamy cechę i mantysę w postaci binarnej
znak liczby - 0
cecha - 0000011
mantysa - 10100000
liczba 5,5 w znormalizowanej reprezentacji zmiennopozycyjnej -0 0000011 1010000
na czerwono zaznaczone są bity znaku całej liczby i cechy

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.

Powtórzenie wiadomości - systemy liczbowe

SYSTEM DWÓJKOWY:

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.

Np. liczba zapisana w dziesiętnym systemie liczbowym jako 10, w systemie dwójkowym przybiera postać 1010, gdyż:

$1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+0\cdot 2^0=8+2=10.\;$

SYSTEM ÓSEMKOWY:

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

SYSTEM SZESNASTKOWY:

Szesnastkowy system liczbowy, system heksadecymalny, hex – pozycyjny system liczbowy, w którym podstawą jest liczba 16.

Np. liczba zapisana w dziesiętnym systemie liczbowym jako 1000, w systemie szesnastkowym przybiera postać 3E8, gdyż:

$3\times 16^{2}+14\times 16^{1}+8\times 16^{0}=768+224+8=1000\;$

Możemy przeliczać systemy binarny(2), oktagonalny(8) i heksadecymalny(16) na decymalny(10) oraz odwrotnie.
Jeśli chcemy przeliczyć np. system dwójkowy na ósemkowy musimy najpierw zamienić dwójkowy na dziesiętny i dziesiętny zamienić na ósemkowy.

poniedziałek, 6 stycznia 2014

"DZIEL I ZWYCIĘŻAJ"

"DZIEL I ZWYCIĘŻAJ" -Jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. 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.