Ć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 log₂n), chociaż w pewnych niekorzystnych przypadkach, algorytm ten może się degenerować do klasy O(n²). Zasada jego działania jest bardzo prosta, lecz nieco trudna w implementacji:

Przykład

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

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(n²). Optymalnym rozwiązaniem jest wybór elementu będącego statystyczną średnią pozostałych elementów w zbiorze.

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 i_pp i końcowego i_pk elementu. Zatem wybór pivotu będzie polegał na wygenerowaniu liczby pseudolosowej z przedziału od i_pp do i_pk włącznie. Pozycja piwotu zostanie zwrócona w i_p. Odpowiednie wzory są następujące:

Podział zbioru na partycje

Gdy zostanie wybrany element środkowy d_ip - 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 d_ip. 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:

f_p(a,b)  → a  <  b

Schemat blokowy sortowania szybkiego

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

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 i_pp do i_pk.

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 i_lewy 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 i_prawy 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 i_lewy oraz i_prawy 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 i_pp oraz i_prawy. Sprawdzamy, czy zawiera ona więcej niż jeden element i jeśli tak, to rekurencyjnie sortujemy ją naszym algorytmem.

Prawa partycja zdefiniowana jest indeksami i_lewy oraz i_pk. 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₍₂₎ = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20

Analogicznie w innych systemach:
10221₍₃₎ = 1 x 3⁴ + 0 x 3³ + 2 x 3² + 2 x 3¹ + 1 x 3⁰,
3341₍₅₎ = 3 x 5³ + 3 x 5² + 4x 5¹ + 1 x 5⁰,
54360₍₆₎ = 5 x 7⁴ + 4 x 7³ + 3 x 7² + 6 x 7¹ + 0 x 7⁰, 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₍₁₆₎ = 4 x 16¹ + 15 x 16⁰,
DFD₍₁₆₎ = 13 x 16² + 15 x 16¹ + 13 x 16⁰, 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:

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