Ćwiczenie VI

 

1. Pojęcia

            Algorytmy rekurencyjne - zadania

            Algorytm „devide and conquer”

            Algorytm sortowania „quick sort”

            Systemy liczbowe

            Zapis dziesiętny, dwójkowy

          

 

2. Wiadomości

2.1 Algorytmy rekurencyjne zadania

 

Zmiana algorytmu rekurencyjnego na nierekurencyjny:

-     zmiana na postać rekurencyjną

-     derekursywacja, np. ogólny wzór na n-ty wyraz ciągu Fibonacciego

 

2.2 Algorytm „divide and conquer”

 

Metoda bisekcji, podziału na dwa, „divide and conquer”.

 

Zastosowanie:

-     przetworniki analogowo – cyfrowe

-     wyznaczanie miejsc zerowych funkcji

-     sortowanie elementów tablicy, wyszukiwanie danego elementu w posortowanej tablicy

 

 

Posortowany ciąg n - elementów

 

Wyszukanie elementu m, algorytm:

 

-     j = n

-     i = n / 2

-     sprawdzenie, czy i == j

                  tak, wyjście z procedury

 

-     sprawdzenie, czy X[i] < m

                  tak, j = i, i = i / 2,

                  czy X[i] == m, tak wypisz, że element znaleziono

                  nie, j = i, i = 3*i / 2

 

 

 

 

2.3 Algorytm sortowania „quick sort”

Sortowanie szybkie jest najszybszym z algorytmów sortujących należących do klasy złożoności obliczeniowej O(n log2n), chociaż w pewnych niekorzystnych przypadkach, algorytm ten może się degenerować do klasy O(n2). Zasada jego działania jest bardzo prosta, lecz nieco trudna w implementacji:

Idea algorytmu sortowania szybkiego

  1. W zbiorze wyznacz jeden z elementów. Następnie pozostałe elementy rozdziel na dwa podzbiory lewy LP i prawy PP, które nazywamy partycjami W lewej partycji powinny się znaleźć elementy poprzedzające wybrany element. W prawej powinny się znaleźć elementy następujące za wybranym elementem. Kolejność elementów w zbiorze wyznacza funkcja porównująca.
  2. Rekurencyjnie posortuj każdą z otrzymanych partycji za pomocą tego samego algorytmu o ile zawiera ona więcej niż jeden element.

 

 

 

Przykład

Posortujemy rosnąco opisaną metodą zbiór { 7 8 2 9 1 5 4 6 }.

 

 

Sortowany zbiór

Opis operacji

 7  8  2  9  1  5  4  6 

      CAŁY ZBIÓR        

W zbiorze wybieramy jeden z elementów na element środkowy.

 2  1  4  5  7  8  9  6 

   LP            PP     

Pozostałe elementy umieszczamy odpowiednio po lewej stronie wybranego elementu, jeśli są od niego mniejsze lub równe lub po prawej stronie, jeśli są od niego większe. Otrzymujemy w ten sposób dwie partycje LP i PP.

 2  1  4  5  7  8  9  6 

   LP            PP     

Te same operacje wykonujemy w każdej z partycji. Odpowiada to rekurencyjnemu wywołaniu algorytmu dla każdej z nich.

 1  2  4  5  6  7  8  9 

LP1   PP1   LP2     PP2 

Po przeniesieniu elementów na odpowiednie strony pozostała tylko jedna partycja dwuelementowa PP2, która może jeszcze być nieposortowana. Pozostałe partycje LP1, PP1, LP2 są jednoelementowe i nie sortujemy ich dalej.

 1  2  4  5  6  7  8  9 

                    PP2 

Wybieramy element środkowy - liczba 8.

 1  2  4  5  6  7  8  9 

 

Podział daje partycję jednoelementową zawierającą liczbę 9. Zatem algorytm kończymy, zbiór został uporządkowany.

 

 

Wybór pivotu

 

Najważniejszą rzeczą w tym algorytmie jest właściwy wybór elementu środkowego, który nazywać będziemy dalej pivotem. Jeśli element ten nie będzie wybierany optymalnie, to dla niektórych zestawów danych algorytm sortowania szybkiego wcale nie okaże się taki szybki - złożoność obliczeniowa może nawet zdegradować się do klasy O(n2). Optymalnym rozwiązaniem jest wybór elementu będącego statystyczną średnią pozostałych elementów w zbiorze.

 

 

 

Strategie wyboru pivotu

Metoda

Zalety

Wady

Pierwszy
element zbioru

Prostota realizacji

Jeśli zbiór jest już wstępnie w znacznym stopniu uporządkowany, to istnieje duże prawdopodobieństwo, iż pierwszy element jest najmniejszym elementem w zbiorze. W takim przypadku algorytm degeneruje się, ponieważ podział da pustą lewą część zbioru (nie ma mniejszych elementów od piwotu) i prawie pełną prawą część zbioru (wszystkie pozostałe elementy z wyjątkiem samego pivota). Jeśli teraz zbiór jest duży, to rekurencja może być bardzo głęboka i prowadzić nawet do niestabilności pracy programu.

Ostatni element zbioru

Prostota realizacji

Jeśli zbiór jest uporządkowany w sposób odwrotny, to mamy identyczną sytuację jak powyżej. Ostatni element jest największym elementem w zbiorze, zatem prawa część będzie pusta, a lewa to reszta zbioru bez elementu środkowego. W przypadku dużego zbioru występuje niebezpieczeństwo głębokiej rekurencji.

Element wybrany losowo

Statystycznie nie występują dwie poprzednie wady

Trudno przewidzieć czas realizacji algorytmu, ponieważ nawet dla tego samego zestawu danych może on być różny z uwagi na losowy wybór pivotu. Jednakże dla dużych zbiorów danych czas ten się uśrednia i zbliża do optymalnego.

 

 

Z trzech podanych przykładów wynika, iż najatrakcyjniejszym sposobem wyboru pivotu jest sposób trzeci, czyli element wybrany losowo. Nawet ten sposób zawiedzie, jeśli zbiór będzie bardzo duży i złożony z elementów o tej samej wartości.

Partycje definiowane są przez indeksy pierwszego ipp i końcowego ipk elementu. Zatem wybór pivotu będzie polegał na wygenerowaniu liczby pseudolosowej z przedziału od ipp do ipk włącznie. Pozycja piwotu zostanie zwrócona w ip. Odpowiednie wzory są następujące:

Podział zbioru na partycje

Gdy zostanie wybrany element środkowy dip - pivot, dzielimy naszą partycję na dwie nowe partycje. W lewej mają się znaleźć wszystkie elementy poprzedzające piwot. W prawej wszystkie następujące za nim. Porządek wyznacza oczywiście funkcja porównująca.

 

 

Problemem są jedynie elementy równe co do wartości dip. W takim przypadku nie ma znaczenia, w której partycji się znajdą - proponujemy dla uproszczenia algorytmu umieszczanie ich w PP. Stąd funkcja porównująca musi określać mocny porządek:

fp(a,b)  → a  <  b

 

 

Schemat blokowy sortowania szybkiego

 

Algorytm sortowania szybkiego

Wyznacz element środkowy - pivot.

Podziel zbiór na dwie partycje względem pivotu

Jeśli otrzymane partycje zawierają więcej niż jeden element, sortuj je rekurencyjnie tym samym algorytmem.

Zakończ wykonywanie algorytmu.

 

 

 

 

D

sortowany zbiór

ipp

indeks pierwszego elementu partycji do posortowania

ipk

indeks końcowego elementu partycji do posortowania

pivot

wartość elementu środkowego potrzebna do ustalenia kolejności elementów przy pomocy funkcji porównującej

di

i-ty element zbioru D

ilewy

indeks elementu na lewo od pivotu

iprawy

indeks elementu na prawo od pivotu

fp( )

funkcja porównująca określająca mocny porządek.

 

W parametrach wejściowych otrzymujemy dostęp do sortowanego zbioru D oraz do informacji o położeniu partycji poprzez indeks jej pierwszego elementu ipp i ostatniego elementu ipk.

Pierwszą operacją algorytmu jest wyznaczenie elementu środkowego - pivotu. Obliczamy go zgodnie z podaną metodą jako element zbioru o indeksie będącym wartością pseudolosową z zakresu od ipp do ipk.

 

Następnie inicjujemy zmienne przed wejściem do pętli głównej nr 1, której zadaniem jest podział partycji na dwie części względem pivotu. Zmienna ilewy zawiera indeks elementów z lewej połówki. Na początku jest to indeks pierwszego elementu partycji i będzie przesuwany w górę zbioru. Zmienna iprawy zawiera indeks elementów z prawej połówki i przyjmuje na początku wartość indeksu ostatniego elementu w partycji i będzie on przesuwany w dół zbioru.

 

Po rozpoczęciu pętli głównej nr 1 napotykamy pętlę nr 2. Zadaniem jej jest pominięcie elementów z lewej strony pivotu, które mają pozostać w lewej partycji.

Z kolei następuje pętla nr 3, która wykonuje takie samo zadanie dla elementów pozostających w prawej partycji.

 

Po zakończeniu tych dwóch pętli jeśli indeksy ilewy oraz iprawy spełniają podaną nierówność, to wskazują one elementy z lewej i prawej partycji, które znajdują się po złej stronie pivotu i muszą zostać zamienione miejscami. Dokonujemy tego i przesuwamy indeksy o jedną pozycję.

Następnie sprawdzamy warunek zakończenia pętli głównej nr 1. Pętla się kończy, gdy indeks lewy i prawy rozminą się w zbiorze.

 

Teraz lewa partycja zdefiniowana jest indeksami ipp oraz iprawy. Sprawdzamy, czy zawiera ona więcej niż jeden element i jeśli tak, to rekurencyjnie sortujemy ją naszym algorytmem.

Prawa partycja zdefiniowana jest indeksami ilewy oraz ipk. Jeśli zawiera więcej niż 1 element, to sortujemy ją rekurencyjnie. Po wykonaniu tych operacji algorytm kończy się - partycja jest posortowana.

 

 

2.4 Systemy liczbowe]

 

Systemem liczbowym nazywamy sposób zapisywania liczb oraz zbiór reguł umożliwiających wykonywanie działań na tych liczbach. Dla dowolnego systemu liczenia istnieje zbiór znaków, za pomocą których tworzy się liczby. Ze względu na sposób zapisu można je podzielić na dwie grupy:

1) Systemy pozycyjne
2) Systemy niepozycyjne
(addytywne).

Ad.1.
Są to systemy, w których wartość liczbowa cyfry zależy od jej umiejscowienia (pozycji) w liczbie. Ilość różnych cyfr systemu nazywa się jego podstawą. Nazwijmy ją q. Wtedy zapis akak-1...a1a0 ma wartość liczbową a0+a1q+a2q2+...+akqk, gdzie a0, a1,. .., ak są cyframi, a kolejne potęgi podstawy systemu q nazywa się rzędami.
Przykład:

W systemie dwójkowym (zwanym też binarnym) używa się cyfr: 0 i 1 (dwóch, bo  tyle wynosi wartość q dla tego systemu).
1011(2) = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20

Analogicznie w innych systemach:
10221(3) = 1 x 34 + 0 x 33 + 2 x 32 + 2 x 31 + 1 x 30,
3341(5) = 3 x 53 + 3 x 52 + 4x 51 + 1 x 50,
54360(6) = 5 x 74 + 4 x 73 + 3 x 72 + 6 x 71 + 0 x 70, itd.

W pozycyjnych systemach liczbowych o podstawie większej od 10 do zapisu liczb wprowadza się nowe znaki na oznaczenie dodatkowych cyfr. Najbardziej popularnym z nich jest system szesnastkowy (zwany heksadecymalnym), gdzie oprócz cyfr 0, ..., 9 używa się liter A,. .., F; przy czym A= 10, B= 11, C= 12, D= 13, E= 14, F= 15.
Przykład:
4F(16) = 4 x 161 + 15 x 160,
DFD(16) = 13 x 162 + 15 x 161 + 13 x 160, itd.

Należy zaznaczyć, że liczby zachowują swoje własności bez względu na to, w jakim układzie rachunkowym są napisane: liczby pierwsze pozostają pierwszymi, liczby złożone - złożonymi; podzielne przez 3 - podzielnymi przez 3 itd.

Dwójkowy system liczenia jest powszechnie stosowany w komputerach, ponieważ cyfry 0 i 1 łatwo jest realizować technicznie:

a) w przewodniku płynie prąd (cyfra 1), nie płynie (cyfra 0),
b) cyfry 0 i 1 można łatwo interpretować jako wartości logiczne zdań: 1- zdanie prawdziwe, 0 - zdanie fałszywe,
c) algorytmy działań w systemie dwójkowym są prostsze niż w innych systemach.
Z tego względu wszystkie urządzenia liczące przechodzą od zapisu liczb w systemie dziesiątkowym do zapisu binarnego; po wykonaniu obliczeń następuje ponowna zamiana na system dziesiątkowy.

Ad.2.
W addytywnych systemach liczbowych wartość przedstawionej liczby jest sumą wartości jej znaków cyfrowych. Do takich systemów należą: hieroglificzny, alfabetyczny i najbardziej znany rzymski, którego znaki używane są często do zapisywania miesięcy. System ten nie zawiera zera, jest oparty na zasadzie piątkowej i zawiera specjalne znaki:

 

 I,

 V,

 X,

 L,

 C,

 D,

 M,

które oznaczają kolejno:

 1,

 5,

 10,

 50,

 100,

 500,

 1000.

Używając tych znaków można zapisać liczby od 1 do 3999 według następujących reguł:
a) zaczynamy od znaków oznaczających największą liczbę, a następnie piszemy coraz mniejsze liczby,
b) obok siebie mogą być zapisane najwyżej trzy identyczne znaki spośród: I, X, C lub M,
c) obok siebie nie mogą być zapisane dwa identyczne znaki spośród: V, L lub D,
d) wartości znaków sumujemy, np. CXXIII = 100 + 10 + 10 + 1 + 1 + 1 = 123
e) według tych zasad nie można zapisać liczb: 4, 9, 40, 90, 400, 900. Dla tych liczb obowiązują dodatkowe reguły, stanowiące wyjątek od reguły a):
f) każdą z liczb 4, 9, 40, 90, 400, 900 zapisujemy pisząc mniejszą liczbę przed większą i odejmując tę mniejszą od większej: IV = 5 - 1 = 4, IX = 9, XL = 40, XC = 90, CD = 400,
CM = 900,
g) każdy z zapisów: IV, IX, XL, XC, CD, CM w zapisie jednej liczby może być użyty tylko jeden raz, np.
MCM = 1000 + (1000 - 100) = 1900,
MXC = 1000 + (100 - 10) = 1090.
Nieprawidłowe są więc zapisy:
IVIV = (5 - 1) + (5 - 1) = 8
XM = 1000 - 10 = 990

System rzymski przetrwał do dziś, natomiast hieroglificzny system był używany w starożytnym Egipcie, a starożytni Grecy używali alfabetycznego systemu liczbowego.
W hieroglificznym systemie liczbowym liczby oznaczano hieroglifami; był to system oparty na zasadzie dziesiętnej, ale bez zera.

W alfabetycznym systemie liczbowym liczby oznaczone są literami alfabetu. System ten też jest oparty na zasadzie dziesiętnej i bez zera.

Na całym świecie ludzie liczą w systemie dziesiątkowym. Zanim system dziesiątkowy stał się systemem powszechnym, różne plemiona i narody posługiwały się innymi systemami. Np. system dwójkowy spotykano (co prawda w bardzo niedoskonałej formie) u niektórych plemion Australii i Polinezji, układ piątkowy zaś u indiańskiego plemienia Szoszonów w Południowej Ameryce. Występował on również w języku Wedau na Nowej Gwinei. Starożytni Majowie (I w. p.n.e.) używali układu dwudziestkowego.

Pozostałość niektórych systemów spotykamy do dnia dzisiejszego. Np. zastosowanie systemu dwunastkowego znajdujemy w podziale roku na 12 miesięcy. Dzień i noc mają po 12 godzin. W handlu przetrwała jednostka tuzin. W miarach czasu i kąta zachował się częściowo system sześćdziesiątkowy, pochodzący od Babilończyków.

 

2.5 Wielkości stosowane w informatyce

 

Wielkości stosowane w informatyce:

 

Bit

4 Bity - nibble

Bajt – 8 bitów, oktet

Kilobajt – 2^10 bajtów, 1024 bajty, 1KB

Megabajt – 1024 * 1024 bajty – 1MB, 1048576

Gigabajt – 1024 * 1MB – 1GB, 1073741824 bajty, 2 ^ 30 bajty

Terabajt – 1024 * 1GB – 1TB, 1099511627776 bajty, 2 ^ 40 bajty

 

 

Odpowiedniki bitowe

 

1 bit,

1Kb

1Mb

1Gb

1Tb

 

Sposoby zapisu liczb

 

liczby całkowite

liczby ułamkowe

 

Liczby o różnych podstawach liczenia

 

Systemy liczenia:

-           dwójkowy, NKB

-           kod Graya

-           kod BCD, Binary Coded Decimal

 

 

3. Zadania i ćwiczenia

Zadanie 1

Napisać procedurę wyszukiwania elementu m w ciągu posortowanych elementów

1)     Jako proste wyszukiwanie

2)     Jako wyszukiwanie z wykorzystaniem metody „divide and conquer”

 

Zadanie 2

Napisać procedurę rekurencyjną wyszukiwania elementu m w ciągu posortowanych elementów

 

Zadanie 3

Napisać procedurę rekurencyjnie wypisującą / rysującą trójkąt Sierpińskiego

Procedura pobiera długość boku oraz współrzędne x i y trójkąta, który należy narysować

 

Zadanie 4

Napisać funkcję rekurencyjną pobierającą od użytkownika kolejne liczby aż do chwili podania wartości 0 oraz następnie wypisująca w odwrotnej kolejności podane liczby.

 

 

Zadanie  5

 

Obliczyć i zapisać w postaci binarnej:

 

69(10) = (64 + 4 + 1)

 

199(10) =

234(10) =

 

500(10) =

 

 

Zadania dodatkowe (1 pkt)

 

Zadanie 6 (najdłuższy wspólny podciąg)

Napisz program, który znajdzie najdłuższy wspólny podciąg dwóch ciągów złożonych z dużych liter alfabetu angielskiego.

 

Dane: W pierwszym wierszu zapisana jest liczba naturalna n określająca długość pierwszego ciągu, a w drugim wierszu zapisany jest pierwszy n literowy ciąg (podany jako sekwencja n dużych liter alfabetu angielskiego). W trzecim wierszu zapisana jest liczba naturalna m określająca długość drugiego ciągu, a w czwartym wierszu zapisany jest drugi m literowy ciąg (podany jako sekwencja m dużych liter alfabetu angielskiego).

 

Wyniki: W pierwszym wierszu zapisz długość najdłuższego wspólnego podciągu, a w drugim wierszu wypisz ten ciąg.

 

Zadanie 7(najdłuższy podciąg rosnący)

 

Napisz program, który znajdzie najdłuższy podciąg rosnący w ciągu złożonym z liczb naturalnych.

 

Dane: W pierwszym wierszu zapisana jest liczba naturalna n określająca długość ciągu, a w drugim wierszu zapisany jest ten ciąg jako sekwencja n liczb naturalnych oddzielonych pojedynczymi spacjami.

 

Wyniki: W pierwszym wierszu zapisz długość najdłuższego podciągu rosnącego, a w drugim wierszu wypisz ten ciąg (jako sekwencję liczb naturalnych oddzielonych pojedynczymi spacjami).