grup scolar industrial sarmasag
DESCRIPTION
Grup Scolar Industrial Sarmasag. Disciplina.Informatica Clasa a XI-a B Grupa 2:-Kocsis Jacint -Kocsis Szabolcs -Kovacs Arnold -Mesesan Gabriel -Nagy Zoltan Metoda Divide et Impera Profesor coordonator: Boti Sandor. - PowerPoint PPT PresentationTRANSCRIPT
1
Grup Scolar Industrial Sarmasag
Disciplina.InformaticaClasa a XI-a BGrupa 2:-Kocsis Jacint -Kocsis Szabolcs -Kovacs Arnold -Mesesan Gabriel -Nagy Zoltan Metoda Divide et Impera
Profesor coordonator: Boti Sandor
2
Informatica. Clasa a 11-a
Metoda desparte şi stăpîneşte
3
Ideia metodei 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.
• Combinarea soluţiilor subproblemelor rezolvate pentru a obţine soluţia problemei iniţiale.
4
Descompunerea mulţimii A în submulţimi
A a a a a a a a= ( , , , , , , )1 2 3 4 5 6 7
A a a a a1 1 2 3 4= ( , , , )
A a2 -2 7= ( )A a a1 -1 1 2= ( , ) A a a1 -2 3 4= ( , ) A a a2 -1 5 6= ( , )
A a a a2 5 6 7= ( , , )
5
Schema generală a algoritmului bazat pe metoda desparte şi stăpîneşte
procedure DesparteSiStapineste(i, j : integer; var x : tip);var m : integer; x1, x2 : tip;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;
6
Exemplul 1. Determinarea numărului maximal(pag. 44)
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.
7
Reprezentarea datelor
{ numarul de elemente in multimea A }const nmax=100;
{ multimea A }var A : array[1..nmax] of real;
8
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 }
9
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 Prelucrare
10
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 Combina
11
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;
12
Exemplul 2. Tăierea unei plăci de arie maximă
Se consideră o placă dreptunghiulară de dimensiunile LH. 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.
13
Placa iniţială
),,0,0( HLP
14
Tăierea pe verticală
),,,( dcbaPcurenta
),,,(1 dxbaP i
),,,(2 dcbxP i
15
Tăierea pe orizontală
),,,( dcbaPcurenta
),,,(3 dcyaP i
),,,(4 iycbaP
16
Formalizarea metodei (1)
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 ).
17
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.
Formalizarea metodei (2)
18
Reprezentarea datelor
{ numarul maximal de gauri }const nmax=100;
var L, H : real; { dimensiunile placii } n : 1..nmax; { numarul de gauri } { coordonatele gaurilor } X, Y : array[1..nmax] of real; { placa de arie maxima } Smax, amax, bmax, cmax, dmax : real;
19
Cînd placa curentă (a, b, c, d) conţine găuri?
dybcxa ii si
20
Funcţia SolutieDirecta
function SolutieDirecta(a, b, c, d : real; var i : integer) : boolean;
{ Returneaza true daca placa curenta nu are gauri.}{ In caz contrar returneaza false si numarul uneia din gauri }label 1;var j : integer;begin SolutieDirecta:=true; for j:=1 to n do if (X[j]>a) and (X[j]<c) and (Y[j]>b) and (Y[j]<d) then begin SolutieDirecta:=false; i:=j; goto 1; end;1:end; { SolutieDirecta }
21
procedure PrelucrareaSolutiei(a, b, c, d : real);var S : real;begin S:=(c-a)*(d-b); if S>=Smax then begin Smax:=S; amax:=a; bmax:=b; cmax:=c; dmax:=d; end;end; { PrelucrareaSolutiei }
Procedura PrelucrareaSolutiei
22
Procedura DesparteSiStapineste
procedure DesparteSiStapineste(a, b, c, d : real);var i : integer;begin if SolutieDirecta(a, b, c, d, i) then PrelucrareaSolutiei(a, b, c, d) else begin DesparteSiStapineste(a, b, X[i], d); DesparteSiStapineste(X[i], b, c, d); DesparteSiStapineste(a, Y[i], c, d); DesparteSiStapineste(a, b, c, Y[i]); end;end; { DesparteSiStapineste }
23
Probleme recapitulative
1. Utilizînd metoda desparte şi stăpîneşte elaboraţi un program care determină suma elementelor mulţimii A={a1, a2, ..., an} formată din n numere reale.
2. Se consideră mulţimea A={a1, a2, ..., an} elementele căreia sînt numere întregi sortate în ordine crescătoare. Elaboraţi un program care determină dacă mulţimea A conţine numărul dat p. Estimaţi complexitatea temporală a programului elaborat.
24
Vă mulţumesc pentru atenţie !