« poprzedni punkt   następny punkt »


Ćwiczenia do wykładu 02

  1. (a) Zbadaj poprawność następującego algorytmu wyszukiwania elementu x w danym dowolnym ciągu e[1],...,e[n]:
     
    szukaj{
    i:=1; result:= false;
    while (i £ n and not result) do
          if x=e[i] then
               result := true
          else
               i := i+1
          fi
    od
          }

    (b) Zmodyfikuj podany algorytm, tak by zwracał pozycję, na której znajduje się element x, jeśli należy on do danego zbioru,  i zwracał 0, w przypadku, gdy x nie należy do tego zbioru. Sformułuj warunek końcowy dla zmodyfikowanego algorytmu. Wskaż niezmiennik pętli.
     
  2. Zaprojektuj algorytm wyszukiwania w ciągu uporządkowanym metodą dzielenia ciągu na 3 części. Zbadaj koszt tego algorytmu i porównaj z kosztem algorytmu binarnych poszukiwań. Zmodyfikuj algorytm BinSearch, tak by był całkowicie poprawny ze względu na specyfikację: wp = {($i) (0<i<n+1 Ù x = e[i]), e[1]< e[2]<...<e[n]}, wk = {e[result] = x}.
     

  3. Przedstaw algorytm Skoki w postaci procedury z parametrem k, określającym długość skoku. Uzasadnij jego poprawność i oszacuj koszt.
     

  4. Pewien kolekcjoner ma n monet, wśród których jedna jest fałszywa, a pozostałe są identyczne. Jedynym sposobem znalezienia fałszywej monety jest porównanie jej wagi z innymi monetami, gdyż moneta fałszywa nie różni się wyglądem, ale nieco lżejsza. Zaproponuj algorytm znalezienia fałszywej monety, jeśli  mamy do dyspozycji tylko prymitywną wagę szalkową, pozwalającą jedynie porównywać wagi przedmiotów na szalkach. Na każdej szalce można położyć dowolną liczbę monet jednocześnie. Jaka jest minimalna liczba porównań, którą trzeba wykonać?
     
  5. Niech x będzie elementem pewnego n elementowego uporządkowanego rosnąco ciągu, gdzie n jest potęgą czwórki. Szukamy elementu x następującą metodą: Dzielimy ciąg na cztery części. Ustalamy, w której części znajduje się szukany element. Dla tej wybranej części stosujemy rekurencyjnie to samo postępowanie, tak długo, jak liczba elementów w rozważanym obszarze jest większa od 1.  Oszacuj koszt tego algorytmu mierzony liczbą wykonanych porównań.
     
  6. Zaproponuj algorytm rekurencyjny,  realizujący sekwencyjne przeglądanie, w celu znalezienia pozycji elementu x w dowolnym skończonym ciągu. Zrealizuj tę samą ideę przy założeniu, że dane elementy tworzą listę, której ogniwo ma dwa atrybuty: wartość elementu i referencję do elementu następnego.
     
  7. Zaproponuj algorytm dodawania dwóch liczb naturalnych zapisanych w systemie binarnym. Sformułuj warunek początkowy i końcowy i uzasadnij całkowitą poprawność tego algorytmu ze względu na podaną specyfikację. Oszacuj koszt algorytmu traktując długość liczby jako rozmiar danych.

« poprzedni punkt   następny punkt »