Strona Michała Hańćkowiaka, ASD220

Uwagi ogólne 2.

Osoby które mają duże kłopoty z programowaniem w Pascalu lub C mogą wykonać zadania "na sucho", tj zapisywac algorytmy w "pseudokodzie", na kartce - i tę kartkę oddać jako sprawozdanie.
Tego typu sprawozdania będą - oczywiście - niżej oceniane.
W pseudokodzie można używać:

if, then, else;

while, do;

for, do;

repeat, until

A[i], tablica[i+1]

---------
przykład:
---------

LosoweGenerowanieCiaguLiczb(A, i1, i2)
    for i:=i1 to i2 do
        A[i]:="liczba losowa z zakresu 1..100"
    
SortowaniePrzezWstawianie(A, i1, i2)
    for i:=i1 to i2 do
        j:=i
        while "prawda" do
            if j=i1 then "koniec pętli while"
            if A[j-1]<=A[j] then "koniec pętli while"
            "przestaw elementy (j-1) i j-ty tablicy A"
            j:=j-1

Wyszukiwanie.

Problem wyszukiwania:
Dany jest (posortowany) ciąg liczb. Należy sprawdzić czy zadana liczba znajduje się w tym ciągu liczb, i jeśli tak jest to podać jej pozycję (indeks tablicy).

Zadanie 3

Zaimplementuj procedurę prostego wyszukiwania:

    // język C
    int CzyJestElementWyszProste(int *tab, int *poz, int elem, int i1, int i2)
    {
      // poszukujemy elementu "elem"; 
      // funkcja zwraca wartość 1 jeśli element istnieje
      // w przeciwnym wypadku zwraca wartość 0;
      // przez parametr "poz" jest zwracana pozycja elementu 
    }

    { język Pascal }
    type t_tablica=array[1..1000] of integer;
    function CzyJestElementWyszProste(var tab:t_tablica; 
        var poz:integer; elem,i1,i2:integer):boolean;
    begin
    end;

Wyszukiwanie proste polega na przeglądaniu kolejnych elementów tablicy.

Zaimplementuj procedurę binarnego wyszukiwania:

    int CzyJestElementWyszBinarne(int *tab, int *poz, int elem, int i1, int i2)
    {
    }

Wyszukiwanie binarne wymaga aby ciąg liczb był posortowany. Jest to procedura bardzo podobna do wyszukiwania nazwiska w książce telefonicznej. Bierzemy środkowy element tablicy, następnie sprawdzamy czy "elem" znajduje się w pierwszej czy w drugiej połowie tablicy. Jeśli znajduje się w pierwszej połowie to bierzemy środkowy element tej połowy, następnie sprawdzamy w której "ćwiartce" pierwszej połowy znajduje się "elem", itd.

poszukujemy elementu 47 ...

    1    3    5    17    23    25    40    41    42    47    50    101
                               ^
                               |   47 znajduje się w tej połowie !
                            środkowy
                            element

    1    3    5    17    23    25    40    41    42    47    50    101
                               |                 ^
                               |                 | 47 jest w tej ćwiartce !
                                              środkowy
                                              element
    (i tak dalej, aż do skutku ...)

Porównaj czas działania procedury prostego i binarnego wyszukiwania, na posortowanym ciągu liczb. Ciąg ten musi być dość długi, np 1000 elementów. Oczywiście do sortowania użyj jednej z procedur z zadań 1 i 2. Przykładowo, można sprawdzać kolejne liczby całkowite, przy pomocy obu procedur wyszukiwania, podając równocześnie ich czasy działania:

               binarne                proste
        1     tak, poz=15, czas=9    tak, poz=15, czas=550
        2     nie, poz=?, czas=10    nie, poz=?, czas=1000
        3     ............................................
              ............................................

Sortowanie c. d.

Zadanie 4

Porównaj czas działania procedury sortowania przez wstawianie i przez selekcje (Lekcja 01) na losowym ciągu liczb (o długości 1000). Doświadczenie należy kilkakrotnie powtórzyć dla różnych danych wejściowych. Wyjaśnij uzyskane wyniki.

Zadanie 5

(sortowanie przez scalanie; MergeSort)
Zaimplementuj procedurę sortującą MergeSort:

    // język C
    void MergeSort(int *tab, int *tabPomocnicza, int i1, int i2)
    {
        // i1-i2 zakres tablicy tab, który chcemy posortować
    }

    { język Pascal }
    type t_tablica=array[1..1000] of integer;
    procedure MergeSort(var tab,tabPomocnicza:t_tablica; i1,i2:integer);
    begin
    end;

Procedura MergeSort polega na:

podzieleniu tablicy na dwie "równe" części A i B
posortowaniu A (rekurencyjne wywołanie MergeSort)
posortowaniu B (rekurencyjne wywołanie MergeSort)
scaleniu A i B, tak aby otrzymać posortowany ciąg

Rezultat scalania musi być umieszczony w tablicy pomocniczej (to jest wada tej procedury !).
"Scalanie" przeprowadzamy następująco:

       ---- A ----        |        ---- B ----
    1    5    12    17    |    3    13    15    19
    ^                     |    ^
    i                     |    j

    Spośród dwóch elementów o indeksach "i" oraz "j"
    wybieramy mniejszy element (w tym wypdku o indeksie "i"),
    umieszczamy go w tablicy pomocniczej,
    a następnie przesuwamy jego indeks w prawo ...

       ---- A ----        |       ---- B ----
    1    5    12    17    |    3    13    15    19
         ^                |    ^
         i                |    j

    ... i tak dalej, aż jedna z części (A lub B) będzie pusta
    wtedy przepisujemy drugą część do tablicy pomocniczej.
    Na końcu przepisujemy tablicę pomocniczą do tablicy wejściowej
    (oczywiście, tylko w zakresie i1-i2).

Procedura powinna zliczać operacje porównywania elementów tablicy (w zmiennej Czas) oraz ewentualnie operacje "dostępu do elementu tablicy" (=zapis lub odczyt elementu; w zmiennej Czas2). Przypomnijmy że pesymistyczna złożoność MergeSort to O(n log n).

Sprawdź działnie tej procedury na krótkich ciągach liczb. Powinien być wyświetlany nieposortowany i posortowany przez tę procedurę ciąg liczb.

Sprawdź działnie tej procedury tak jak w zadaniu 1 na długich ciągach liczb (ok 1000). Program powinien wyświetlać czas działania procedury we wszystkich przypadkach.