Metoda "Dziel i zwyciężaj"

Metoda "Dziel i zwyciężaj" (divide and conquer) polega na podzieleniu problemu na mniejsze problemy (podproblemy - które na ogół są tym samym problemem, lecz o mniejszych rozmiarach), które następnie rozwiązuje się niezależnie, by w końcowym etapie scalić rezultaty i rozwiązać główny problem.

Ideę tej metody można zaprezentować na przykładzie algorytmu wyszukiwania w zbiorze lub porządkowania zbioru. W każdym kroku zbiór jest dzielony na dwie części, elementy tych części są porządkowane. Na koniec uporządkowane części są łączone w uporządkowaną całość (np. sortowanie przez scalanie). Według tej zasady są kreowane algorytmy rekurencyjne.

Przykład obrazuje wyszukanie najmniejszej i największej liczby w tablicy "tab" (dane zostają  wylosowane), która zostaje wstępnie przez porównanie sąsiednich danych podzielona na 2 mniejsze tablice "tabm" i "tabw", z elementami odpowiednio mniejszymi i większymi, z których z pierwszej wybrany jest najmniejszy element w całym zbiorze, a z drugiej największy.

program metoda_dziel_i_zwyciezaj;
uses crt;
var tab:array[1..50] of integer;
     tabm:array[1..25] of integer;
     tabw:array[1..25] of integer;
     i,j,max,min: integer;
        procedure losowanie;
    begin
      randomize;
        for i:=1 to 50 do begin
            tab[i]=random(101);
        end;
    end;
    procedure dziel;
      begin
        j:=0;
        i:=1;
        repeat
           if tab[i]<tab[i+1] then
               begin
                  j:=j+1;
                  tabm[j]:=tablica[i];
                  tabw[j]:=tablica[i+1];
              end else
               begin
                  j:=j+1;
                  tabw[j]:=tablica[i];
                  tabm[j]:=tablica[i+1];
              end;
           i:=i+2;
        until i>=50;
    end;
    procedure zwyciezaj;
       begin
          min:=tabm[1];
          for i:=1 to 25 do if tabm[i]<min then min:=tabm[i];          
          max:=tabw[1];
          for i:=1 to 25 do  if tabw[i]>max then max:=tabw[i];
       end;
 begin
    clrscr;
    losowanie;
    writeln('Wylosowane liczby');
    for i:=1 to 50 do write (tab[i],' ');
    dziel;
    zwyciezaj;
    writeln('Liczba najmniejsza',min);
    writeln('Liczba najwieksza',max);
    repeat until keypressed;
 end.

Komentarze


link Silnią liczby naturalnej n nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie symboliczne n! (czytaj: n silnia) wprowadził w 1808 roku francuski matematyk Christian Kramp. Zgo


link Ciąg Fibonacciego to ciąg liczb naturalnych zwanych liczbami Fibonacciego określony rekurencyjnie w sposób następujący:F0 = 0F1 = 1Fn = Fn-1 + Fn-2, dla n ≥ 2Początkowe wartości tego ciągu to:


link Sito Eratostenesa jest sposobem wyznaczania liczb pierwszych zaproponowanym przez greckiego matematyka Eratostenesa. Metoda sita (w założeniu eliminacja) polega na odrzucaniu liczb naturalnych będących wielokrotnościami liczb pie


link program kwadratowe;uses crt;var x1,x2,x,r1,r2,delta,pierwiastek:real;    a,b,c,yw,x0:real;    kla:char;beginrepeat  clrscr;  writeln('Ten program rozwiazuje rownania kwadratowe axx+by+c');  w