Metoda desparte şi stăpîneşte

Împărţirea repetată a unei probleme de dimensiuni mari în două sau mai multe subprobleme de acelaşi tip, dar de dimensiuni mai mici.

Rezolvarea subproblemelor în mod direct, dacă dimensiunea lor permite aceasta, sau împărţirea lor în alte subprobleme de dimensiuni şi mai mici.

Rezolvarea subproblemelor în mod direct, dacă dimensiunea lor permite aceasta, sau împărţirea lor în alte subprobleme de dimensiuni şi mai mici.

Combinarea soluţiilor subproblemelor rezolvate pentru a obţine soluţia problemei iniţiale.

Determinarea numărului maximal

Se consideră mulţimea A={a1, a2, …, an}, formată din n numere reale. Elaboraţi un program care determină numărul maximal din această mulţime.

Reprezentarea datelor

{ numarul de elemente in multimea A }

const nmax=100;

{ multimea A }

var A : array[1..nmax] of real;

 

       Funcţia SolutieDirecta

function SolutieDirecta(i, j : integer) : boolean;

{ returneaza true daca multimea curenta contine cel }

{ mult doua elemente }

begin

  SolutieDirecta:=false;

  if (j-i<2) then SolutieDirecta:=true;

end; { SolutieDirecta }

 

Procedura Prelucrare

 

procedure Prelucrare(i, j : integer;
var x : real);

{ returneaza elementul maximal din A[i], A[j] }

begin

  x:=A[i];

  if A[i]<A[j] then x:=A[j];

end; { Prelucrare }

 

Procedura Combina

 

procedure Combina(x1, x2 : real; var x : real);

{ combina solutiile partiale returneaza elementul }

{ maximal din x1 si x2 }

begin

  x:=x1;

  if x1<x2 then x:=x2;

end; { Combina }

 

Procedura  DesparteSiStapineste

 

procedure DesparteSiStapineste(i, j : integer;
var
x : real);

var m : integer;

    x1, x2 : real;

begin

   if SolutieDirecta(i, j) then Prelucrare(i, j, x)

      else

         begin

           m:=(j-i) div 2;

           DesparteSiStapineste(i, i+m, x1);

           DesparteSiStapineste(i+m+1, j, x2);

           Combina(x1, x2, x);

         end;

end;

                                          Tăierea unei plăci de arie maximă

 

Se consideră o placă dreptunghiulară de dimensiunile L´H. Placa are n găuri punctiforme, fiecare gaură fiind definită prin coordonatele (xi, yi).

Elaboraţi un program care decupează din placă o bucată de arie maximă, dreptunghiulară şi fără găuri. Sînt admise doar tăieturi de la o margine la alta pe direcţii paralele cu laturile plăcii – verticale sau orizontale.

Formalizarea metodei

  1. Iniţial stabilim aria maximă Smax = 0.
  2. Dacă placa curentă nu are găuri, problema poate fi  soluţionată direct, comparînd aria curentă cu  valoarea Smax.
  3. În caz contrar alegem o gaură arbitrară (xi, yi) prin care tăiem placa curentă în plăci mai mici: P1=(a, b, xi, d);   P2=( xi, b, c, d); P3=(a, yi, c, d);  P4=(a, b, c, yi ).
  4. În continuare examinăm în acelaşi mod fiecare din plăcile P1, P2, P3 şi P4, obţinute în rezultatul tăierii, memorînd consecutiv în variabila Smax aria plăcii de suprafaţă maximă.
  5. Procesul de calcul se termină atunci, cînd nici una din plăcile curente P1, P2, P3, P4 nu mai conţine găuri.

   

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s