Zeszyt do informatyki

     R ekurencja   Z rekurencją mamy do czynienia, gdy, określając jakieś pojęcie, odwołujemy się w definicji do niego samego. Dana funkcja jest rekurencyjna, jeśli zawiera odwołanie do samej siebie. Aby zapisać rekurencyjną realizację wybranego algorytmu, musimy zapisać algorytm w postaci funkcji, która może wywołać samą siebie. Rekurencja w informatyce , tak jak zresztą rekurencja w matematyce, stosowana jest bardzo często. Używa się jej np. w  algorytmach sortowania  (na przykład Quick Sort). Jedną z typowych sytuacji jest przeszukiwanie struktury danych w postaci nieregularnego drzewa, np.  plików XML . Istnieją także specyficzne algorytmy, w których wykorzystanie rekurencji jest czymś naturalnym. Dla przykładu trudno rozwiązać problem “wież Hanoi” inaczej niż w sposób rekurencyjny. Rekurencja i iteracja różnią się zasadniczo. Powtórzenia w rekurencji są innego rodzaju niż powtórzenia właściwe dla iteracji. Powtórzenia w rekurencji "zagłębiają się ...

 #include <iostream> using namespace std; int main(int argc, char** argv)  { int tab[10]; cout << "Podaj 10 elementow zbioru uporzadkowanego rosnaco"; for(int i=0; i<10; i++) cin >> tab[i]; return 0; }

  Metoda połowienia Na czym polega metoda połowienia? Jak wyszukujemy elementy metodą połowienia?   ► Algorytm wyszukiwania przez połowienie jest przykładem metody "dziel i zwyciężaj". Polega ona na dzieleniu przeszukiwanego zbioru na dwie części i zawężeniu przeszukiwania do jednej z tych części.  ►Ogólna zasada algorytmu polega na dzieleniu zakresu na połowę i sprawdzaniu, czy element znajdujący się dokładnie pośrodku jest elementem szukanym, a jeśli nie, to czy jest większy, czy mniejszy od szukanego, oraz na przeszukaniu odpowiednio w prawo i lewo.  W ten sposób szybko zawęża się zakres poszukiwań, aż w końcu otrzymuje się przedział jednoelementowy.  Można wtedy wskazać szukany element lub stwierdzić, że go nie ma.