rekurencja i inne alg_popr.doc

                                                                      Rekurencja

z łacińskiego oznacza to przybiec z powrotem - osiagniesz rzecz

wielka, jesli zawrócisz po to, by osiagnac rzeczy małe.

Przykład:

Małe dziecko otrzymuje polecenie posprzatania rozrzuconych

klocków do pudełka.

„ zebrać wszystkie klocki

naraz” ????

- skomplikowane zadanie

„wziac jeden klocek, przełożyć go do pudełka, a nastepnie zrobić to

samo z pozostałymi klockami” ???

-         prosta czynność

„Duży” problem został rozłożony na problem elementarny, który umiemy rozwiązać.

Problem elementarny jest mniej skomplikowany niż problem początkowy.

Zakończenie algorytmu jest jasno określone („w momencie gdy na podłodze nie ma rozrzuconych klocków”)

                                                                      Matematycznie:

Mamy obliczyć: an

Wiemy że: an =a x an-1 (an-1 jest łatwiej

obliczyć niż an)

Jesli jest nadal trudno, to zawsze

mona wstawic: an-1 =a x an-2,

gdzie: an-2 =a x an-3 itd.

wystarczy wiedziec tylko, e: a0 =1

aby obliczyc dowolna potege a

Def:

Program rekurencyjny jest to program, który wywołuje sam siebie

Problem:

Dysponujemy tablica n liczb całkowitych A(n) o elementach:

a(1),a(2), a(3), ...., a(n)

Zadanie: sprawdzić, czy w tablicy A występuje liczba x

Rozwiązanie:

- wziąść pierwszy niezbadany element tablicy n elementowej,

- jeśli aktualnie analizowany element tablicy jest równy x to:

   wypisz „sukces” i zakończ działanie

- w przeciwnym wypadku:

   zbadaj pozostała część tablicy n-1 elementów

W programach rekurencyjnych:

- zakończenie programu jest jasno określone (znaleziony element,
- przekroczony zakres tablicy),

- duży problem zostaje „rozłożony” na problemy elementarne, które umiemy
   rozwiązać

Podstawowe błedy:

- złe określenie warunku zakończenia programu,

- niewłaściwa (nieefektywna) dekompozycja problemu.

                                          Algorytmy sortowania danych

Sortowanie przez selekcję

Opis:

- trzeba wyznaczyć najmniejszy element w ciagu;

- zamienić go miejscami z pierwszym elementem ciagu,

- wyznaczyć najmniejszy element w a[2..n] i zamienić go z drugim
   elementem w ciagu,

- itd.

                                          Sortowanie przez wstawianie

                                          (układanie kart do bryda)

Opis:

- metoda polega na wstawianiu nastepnej karty we właściwe miejsce
   uporządkowanych uprzednio kart.

                                          Sortowanie przez wstawianie - algorytm

dla i=2,...,liczba elementów tablicy wykonuj

{

j :=i

podczas gdy j > 1 i x[ j-1 ] > x[ j ] wykonuj

{

pom := x[ j ]

x[ j ] := x[ j-1]

x[ j-1] := pom

j := j-1

}

}

                                                                      Sortowanie bąbelkowe

Tablica jest przeszukiwana od dołu. Element zacieniony jest

tym, który w pojedyńczym przebiegu uleciał do góry jako

„najlżejszy”.

Analizowane są zawsze 2 sasiadujace ze soba elementy. Jeśli

nie są uporządkowane (u góry jest element „cięższy”) to

następuje ich zamiana.

                                                        Wynik sortowania  bąbelkowego

                                          Algorytm sortowania bąbelkowego

TAB : Tablica [1..n] elementów typu rzeczywistego

i,j : całkowite

pom: rzeczywiste

              Początek {programu}

                 Dla i:=1 do n-1 wykonuj

              dla j:=n do i+1 z krokiem -1wykonuj

                            Jeśli TAB[j]<TAB[j-1] to

                              początek

                              pom:=TAB[j-1];

                            TAB[j-1]:=TAB[j];

                            TAB[j]:=pom

                            koniec

                            Koniec {programu}

• Dość często zdarzają się „puste przebiegi” (nie jest dokonywana żadna
  wymiana, bowiem elementy są już posortowane.

• Algorytm jest bardzo wrażliwy na konfigurację poczatkową danych.

Wersja 1: 4 2 6 18 20 39 40

Wersja 2: 4 6 18 20 39 40 2

(wersja 1 wymaga jednej zamiany, a wersja 2 wymaga aż sześciu przebiegów)

...