Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Metoda de programare DIVIDE ET IMPERA

Metoda de programare DIVIDE ET IMPERA



Ø   1. Notiuni introductive

Metoda de programare DIVIDE ET IMPERA consta in impartirea problemei initiale de dimensiuni [n] in doua sau mai multe probleme de dimensiuni reduse.In general se executa impartirea in doua subprobleme  de dimensiuni aproximativ egale si anume [n/2].Impartirea in subprobleme are loc pana cand dimensiunea acestora devine suficient de mica pentru a fi rezolvate in mod direct (cazul de baza).Dupa rezolvarea celor doua subprobleme se executa faza de combinare a rezultatelor in vederea rezolvarii intregii probleme.

Metoda DIVIDE ET IMPERA se poate aplica in rezolvarea unei probleme care indeplineste urmatoarele conditii :

4se poate descompune in ( doua sau mai multe) subprobleme ;


4aceste subprobleme sunt independente una fata de alta (o subproblema nu se rezolva pe baza alteia si  nu se foloseste rezultate celeilalte);

4aceste subprobleme sunt similare cu problema initiala;

4la randul lor subproblemele se pot descompune (daca este necesar) in alte subprobleme mai simple;

4aceste subprobleme simple se pot solutiona imediat prin algoritmul simplificat.

Deoarece putine probleme indeplinesc conditiile de mai sus,aplicarea metodei este destul de rara.

Ø   2. Etapele metodei DIVIDE ET IMPERA

Dupa cum sugereaza si numele 'desparte si stapaneste 'etapele rezolvarii unei probleme (numita problema initiala) in  DIVIDE ET IMPERA  sunt :

  • descompunerea problemei initiale in subprobleme independente similare problemei de baza ,de dimensiuni mai mici;
  • descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediata prin algoritmul simplificat;
  • rezolvarea subproblemelor simple;
  • combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mari;
  • combinarea ultimelor solutii determina obtinerea solutiei problemei initiale.

            Metoda DIVIDE ET IMPERA admite o implementare recursiva,deoarece subproblemele sunt similare problemei  initiale, dar  de dimensiuni mai mici. Principiul fundamental al recursivitatii este autoapelarea unui subprogram cand acesta este activ, ceea ce se intampla la un nivel, se intampla la orice nivel, avand grija sa asiguram conditia de terminare ale apelurilor repetate. Asemanator se intampla si in cazul metodei DIVITE ET IMPERA, la un anumit nivel sunt doua posibilitati :

Ø     s-a ajuns la o (sub)problema simpla ce admite o rezolvare imediata caz in care se rezolva (sub)problema si se revine din apel (la subproblema anterioara,de dimensiuni mai mari);

Ø     s-a ajuns la o (sub)problema care nu admite o rezolvare imediata, caz in care o descompunem in doua sau mai multe subprobleme si pentru fiecare din ele se continua apelurile recursive (ale procedurii sau functiei).

In etapa finala a metodei DIVIDE ET IMPERA  se produce combinarea subproblemelor (rezolvate deja) prin secventele de revenire din apelurile recursive.

Ø  3. Principiul metodei DIVIDE ET IMPERA

Etapele metodei DIVIDE ET IMPERA (prezentate anterior) se pot reprezenta prin urmatorul subprogram general (procedura sau functie ) recursiv exprimat in limbaj natural:

Subprogram DIVIMP (PROB);

  • Daca PROBLEMA PROB este simpla
  • Atunci se rezolva si se obtine solutia SOL
  • Altfel pentru i=1,k executa DIVIMP(PROB) si se obtine SOL1;
  • Se combina solutiile SOL 1, ,SOL K si se obtine SOL;
  • Sfarsit _subprogram;

Deci subprogramul DIVIMP se apeleaza pentru problema initiala PROB, aceasta admite descompunerea in K subprobleme simple; pentru acestea se reapeleaza recursiv subprogramul, in final se combina solutiile acestor K subprobleme.

De obicei problema initiala se descompune in doua subprobleme mai simple; in acest caz etapele generale ale metodei DIVIDE ET IMPERA se pot reprezenta concret, in limbaj pseudocod, printr-o procedura recursiva astfel :

Procedura  DIVIMP(li,ls,sol);

Daca ((ls-li)<=eps)

Atunci REZOLVA (li,ls,sol);

Altfel

DIVIDE (li,m,ls);

DIVIMP(li,msol1);

DIVIMP(m,ls,sol2);

COMBINA(sol1,sol2,sol);

Sfarsit_ procedura;

Procedura DIVIMP se apeleaza pentru problema initiala care are dimensiunea intre limita inferioara (ls) si limita inferioara(li); daca (sub)problema este simpla (ls-li<=eps), atunci procedura REZOLVA ii afla solutia imediat si se produce intoarcerea din apelul recursiv; daca (sub)problema este(inca) complexa, atunci procedura DIVIDE o imparte in doua subprobleme, alegand pozitia m intre limitele li si ls; pentru fiecare din cele doua subprobleme se reapeleaza  recursiv procedura DIVIMP; in final, la intoarcerile din apeluri se produce combinarea celor doua soluitii sol1 si sol2 prin apelul procedurii COMBINA.

            Cea mai simpla aplicare a strategiei 'Divide et Impera' se poate recunoaste in problema ghicirii unui numar fixat, numar aflat intr-un interval predefinit, de exemplu 0.. 100. Jocul presupune fixarea unei valori si la fiecare incercare de ghicire a numarului sa se raspunda cu una din precizarile: 'numarul cautat este mai mare decat x', 'numarul cautat este mai mic decat x' sau 'x este numarul cautat'. Se doreste elaborarea unei strategii cu un numar de incercari cat mai mic.Trebuie precizat ca 'divide et impera' este o maniera de abordare a rezolvarii, nu o metoda de obtinere a unui rezultat optim.

Divide et impera este o tehnica de admite o implementare recursiva.

Problemele cele mai potrivite pentru aplicarea metodei Divide et Impera sunt acelea in care avem de prelucrat un sir de elemente memorate intr-un vector.

Exemplu: Consideram un sir (x­­­­­1,x2,..,x­­n). Impartim sirul dat in doua subsiruri (x1,,xm) si (xm+1,,xn) si prelucram sirurile obtinute. Astfel, am descompus problema in doua subprobleme de acelasi tip.

In prelucrarea subsirului(x1,..,x­m), intalnim cazurile:

Ø     subsirul se poate prelucra direct

Ø     subsirul nu se poate prelucra direct. In acest ultim caz, subsirul trebuie descompus in aceeasi maniera.

Analog se va proceda si cu subsirul (xm+1,,xn).Pentru fiecare din subsirurile astfel obtinute, putem intalni aceleasi situatii.Acest lant de descompuneri va continua pana cand obtinem subsiruri prelucrabile direct.

Generalizare la fiecare pas va fi analizat un subsir de forma (xp, ,xq) care contine elementele sirului situate intre indicii p si q. Presupunem ca exista un numar natural m= astfel incat prelucrarea subsirului (xp,,xq) sa se faca prelucrand subsirurile (xq,, xm) si (xm+1,,xq).

O structura posibila a unui subprogram recursiv Divide Et Impera (p,q:integer) care prelucreaza subsirul (xp, , Xq) este:

Ø     daca subsjrul (xp,, xq) poate fi prelucrat direct, atunci il prelucram;

Ø     in caz contrar:

·       impartim subsirul (xp, , xq)in doua subsiruri: (xp, , xm) §i (xm+1, , xq),

·       prelucram subsirunle obtinute in aceeasi maniera. Pentru aceasta se realizeaza un apel recursiv al subprogramului DivideEtlmpera(p,m). Analog prelucrarea subsirului (xm+i,,Xq) se face prin auto-apelul DivideEtImpera(m,q).

Observatii:

Ø     de obicei elementul x este situat pe pozitia din mijloc:m:=(p+q) div 2.Astfel..subsirurile..obtinute vor avea dimensiuni apropiate si implicit subproblemele determinate..de..aceste..subsiruri..vor avea grade de complexitate apropiate.

Ø     este posibil ca subsirurile sa fie (xp, , xm-1) si (xm+1,,xq), elementul xm fiind exclus;

Ø     in general un subsir poate fi prelucrat direct daca nu are nici un element sau contine un singur element.

Ø   4. Aplicatii

4.1 Maxim intr-un vector

Se citeste un vector cu n componente, numere naturale. Se cere sa se tipareasca valoarea maxima.

>      daca i=j, valoarea maxima va fi v[i];

>      contrar vom imparti vectorul in doi vectori: primul vector va contine componentele de la i la (i+j) div 2, al doilea vector va contine componentele de la (i+j) div 2 +1 la j; rezolvam problemele (aflam maximul pentru fiecare din ele) iar solutia problemei va fi data de valoarea maxima dintre rezultatele celor doua subprobleme.



program maxim;

var v:array[1..10] of integer;

n,i:integer;

function max(i,j:integer):integer;

var a,b:integer;

begin

if i=j then max:=v[i]

else begin

a:=max(i, (i+j) div 2);

b:=max((i+j) div 2+1,j);

if a>b then max:=a

else max:=b;

end;

end;

begin

write(’n=’);

readln(n);

for i:=1 to n do read(v[i]);

writeln(maximul este ’,max(1,n));

end.

4.2 Cel mai mare divizor comun

Fie n valori numere naturale a1,a2,a3,..,an. Determinati cel mai mare divizor comun al lor prin metoda Divide Et Impera. Se imparte sirul a1,a2,a3,..,an in doua subsiruri a1,a2,a3,..,am,respectiv am+1,am+2,.,an,unde m reprezinta pozitia de mijloc,m=(1+n) div 2.

Cmmdc(a1,a2,..,an)= Cmmdc(a1,a2,..,am), Cmmdc(am+1,am+2,.,an))

program cmmdc_sir;

const nmax=20;

type indice=1..nmax;

var a:array[indice] of word;

n:indice;

procedure citire;

var i:indice;

begin

readln(n);

for i:=1 to n do read(a[i]);

end;

function euclid(x,y:word):word;

var r:word;

begin

while y<>0 do

begin

r:=x mod y;

x:=y;

y:=r;

end;

euclid:=x;

end;

function cmmdc(p,q:indice):word;

var m:indice;

begin

if q-p<=1 then cmmdc:=euclid(a[p],a[q])

else

begin

m:=(p+q) div 2;

cmmdc:=euclid(cmmdc(p,m),cmmdc(m+1,q));

end;

end;

begin

citire;

writeln(’cmmdc=’,cmmdc(1,n));

readln;

end.

4.3 Codare Sir

Se considera un sir cu n elemente, initial toate egale cu n. Se imparte sirul pe jumatate, elementele din jumatatea stanga incrementandu-se, iar cele din jumatatea dreapta decrementandu-se cu o unitate. Daca exista element 'nepereche' exact la mijloc acesta ramane neschimbat. Celor doua jumatati li se aplica acelasi 'tratament' si jumatatilor jumatatilor la fel etc. pana cand se obtin secvente de cate un element.

program codare;

var a:array[1..100] of integer;

n,i:integer;

procedure codare(p,q):integer;

var m,i:integer;

begin

if q-p=2 then begin a[q]:=a[q]-1;

a[p]:=a[p]+1;

end

else if q-p=1 then begin a[q]:=a[q]-1;

a[p]:=a[p]+1;

end

else if (q-p) mod 2=0 then

begin m:=(p+q) div 2;

for i:=p to m-1do a[i]:=a[i]+1;

for i:=m+1 to q do a[i]:=a[i]-1;

codare(p,m-1);

codare(m+1,q);

end

else

begin m:=(p+q) div 2;

for i:=p to m do a[i]:=a[i]+1;

for i:=m+1 to q do a[i]:=a[i]-1;

codare(p,m);

codare (m+1,q);

end;

end;

begin

readln(n);

for i:=1 to n do a[i]:=n;

codare(1,n);

for i:=1 to n do write(a[i]:4);

writeln;

end.

4.4 Cautarea binara intr-un sir

Sa se verifice daca o valoare data x exista intr-un sir de numere intregi ordonate crescator. Se va folosi un algoritm de cautare bazat pe metoda Divide Et Impera.

Se descompune problema in doua subprobleme de acelasi tip. Se imparte vectorul in doi subvectori: primul subvector va contine elementele pana la pozitia de mijloc, iar al doilea va fi alcatuit din elementele de dupa pozitia din mijloc. Verificam daca valoarea cautata se gaseste chiar pe pozitia din mijloc si in caz afirmativ cautarea se opreste. Daca valoarea cautata este mai mica decat elementul situat pe pozitia din mijloc, cautarea trebuie continuata in subvectorul stang, iar daca este mai mare, cautarea continua in subvectorul drept.

program cautare;

type vector=array[1..20] of integer;

var v:vector;n,x,i:integer;

function caut(p,q:integer):integer;

var mij:integer;

begin

if q<p then caut:=-1

else

begin

mij:=(p+q) div 2;

if v[mij]=x then caut:=mij

else if x<v[mij] then caut:=(p,mij-1)

else caut:=caut(mij+1,q);

end;

end;

begin

write(’n=’);

readln(n);

write(’v[1]=’);

readln(v[1]);

for i:=2 to n do

repeat

write(’v[’,i,’]=’);

readln(v[i]);

until v[i]>v[i-1];

write(’x=’);

readln(x);

writeln(caut(1,n));

end.

4.5 Partitionarea unui sir

Se considera un sir de n numere intregi, ordonat crescator si un numar intreg x. Sa se partitioneze sirul dat in doua subssiruri, astfel incat toate elementele primului sir sa fie mai mici decat x, iar toate elementele celui de-al doilea sir sa fie mai mari decat x. Se va folosi un algoritm Divide  Et Impera.

program partitionare;

type vector=array[1..20] of integer;

var v:vector;n,x,i,ref:integer;

function part(p,q):integer;

var mij:integer;

begin

if q<p then part:=p

else begin mij:=(p+q) div 2;

if x=v[mij] then part:=mij else

if x<v[mij] then part:=part(p,mij-1)

else part:=part(mij+1,q);

end;

end;

begin

write(’n=’);

readln(n);

write(’v[1]=’);

readln(v[1]);

for i:=2 to n do

repeat

write(’v[’,i,’]=’);

readln(v[i]);

until v[i]>=v[i-1];

write(’x=’);

readln(x);

ref:=part(1,n);

writeln(’primul vector’);

for i:=1 to ref-1 do write (v[i]:5);

writeln;

writeln(’al doilea vector’);

for i:=ref to n do write(v[i]:5);

readln;

end.

4.6 Pozitia k

Se citeste de la tastatura un sir de n elemente numere intregi.Sa se gaseasca elementul aflat pe o pozitie data k in sirul ordonat crescator, fara a efectua ordonarea.


program pozitia_k;

const nmax=20;

type indice=1..nmax;

var a:array[indice] of integer;

n,k:indice;

procedure citire;

var i:indice;

begin

write(’n=’);

readln(n);

for i:=1 to n do begin write(’a[’,i,’]=’);

readln(a[i]);

end;

end;

procedure afisare;

var i:indice;

begin

writeln(’vectorul este’);

for i:=1 to n do write(a[i]:4);

writeln;

end;

function divide(p,q:indice):indice;

var st,dr:indice;x:integer;

begin

st:=p;

dr:=q;

x:=a[p];

while st<dr do

begin

while (st<dr) and (a[dr]>=x) do dec(dr);a[st]:=a[dr];

while (st<dr) and (a[dr]<=x) do inc(st);a[dr]:=a[st];

end;

a[st]:=x;

divide:=st;

end;

function qselect(st,dr,k:indice):integer;

var p:indice;

begin

p:=divide(st,dr);

if k=p-st+1 then qselect:=qselect(st,p-1,k)

else qselect:=qselect(p+1,dr,k-(p-st+1));

end;

begin

citire;

write(’k=’)

;readln(k);

writeln(’pozitia ’,k,’ in vectorul sortat este ’,qselect(1,n,k));

afisare;

end.

4.7 Sortare rapida (quicksort)

Un tablou V se completeaza cu n elemente numere reale .Sa se ordoneze crescator folosind metoda de sortare rapida .

 Solutia problemei se bazeaza pe urmatoarele etape implementate in programul principal:

          4se apeleaza procedura “quick” cu limita inferioara li=1 si limita superioara ls=n;

         4functia ”poz”  realizeaza mutarea elementului v[i] exact pe                               pozitia ce o va ocupa acesta in vectorul final ordonat; functia ”poz” intoarce (in k ) pozitia ocupata de acest element;

          4in acest fel ,vectorul V se imparte in doua parti : li …k-1 si k+1…ls;

          4pentru fiecare din aceste parti se reapeleaza procedura“quick”,cu limitele modificate corespunzator ;

          4in acest fel primul element din fiecare parte va fi pozitionat exact pe pozitia finala ce o va ocupa in vectorul final ordonat (functia “poz”);

         4fiecare din cele doua parti va fi astfel impartita in alte doua parti procesul continua pana cand limitele partilor ajung sa se suprapuna, ceea ce indica ca toate elementele vectorului au fost mutate exact pe pozitiile ce le vor ocupa in vectorul final; deci vectorul este ordonat ;

           4in acest moment se produc intoarcerile  din apelurile recursive si programul isi termina executia .

 program quicksort;

 type  vector= array [1..50] of real;

 var v:vector; i,n,k:integer;

function poz(li,ls:integer):integer;

var i,j,modi,modj,m:integer;

man:real;

begin

i:=li; j:=ls;

modi:=0; modj:=-1;

while i<j do

begin

if  v[i]>v[j] then

begin

man:=v[i];

v[i]:=v[j];



v[j]:=man;

m:=modi ;

modi:=-modj;

modj:=-m;

end;

i:=i+modi;

  j:=j+modj;

end;

poz:=i;

end;

procedure   quick(li,ls:integer);

begin

if  li<ls then begin

 k::=poz(li,ls);

quick(li,k-1);

quick(k+1,ls);

end;

end;

begin

write(‘cate elemente are vectorul ?=’);readln(n);

for i:=1 to n do

begin

write(‘tastati elementul ‘,i,’=’);

readln(v[i]);

end;

quick(1,n);

writeln(‘vectorul ordonat este :’);

for i:=1 to n do writeln(v[i]);

readln;

end.

 OBSERVATIE

 4daca elementul se afla in stanga ,atunci se compara cu elementele din dreapta lui si se sar (j:=j-1)elementele mai mari decat el ;

 4daca elementul se afla in dreapta ,atunci se compara cu elemente din stanga lui si se sar (i:=i+1)elementele mai mici decat el.

4.8 Sortare prin interclasare(mergesort)

            Tabloul unidimensional V se completeaza cu n numere reale. Sa se ordoneze crescator folosind sortare prin interclasare.

Sortarea prin interclasare se bazeaza pe urmatoarea logica :

vectorul V se imparte prin injumatatiri succesive in vectori din ce in ce mai mici cand se ating vectorii de maxim doua elemente, fiecare dintre acestia se ordoneaza printr-o simpla comparare a elementelor; cate doi astfel de mini- vectori ordonati se interclaseaza succesiv pana se ajunge iar la vectorul V.

   

program mergesort;

type vector=array[1..50] of real ;

var v:vector ;n,i:word;

procedure schimba(li,ls:word;var a:vector);

var man:real;

begin

if a[li]>a[ls] then begin

man:=a[li];

a[li]:=a[ls];

a[ls]:=man;

end;

end;

procedure interclas(li,m,ls:word;var a:vector);

var b:vector:i,k,p,j:word;

begin

i:=li; j:=m+1; k:=0;

while (i<=m)and(j<=ls) do

begin

inc(k);

if  a[i] <a[j] then begin

b[k]:=a[i];

inc(i);

end

else  begin

b[k]:=a[j];

inc(j);

end;                                                   

end;

if i<=m then for p:=i to m do  begin1

inc(k);b[k]:=a[p];

end;

if j<=ls then for p:=j to ls do begin

inc(k) ;b[k]:=a[p];                                                                                   

end; 

k:=0;

for p:=li to ls do begin

inc(k);

a[p]:=b[k];

end;

end;

procedure divi(li,ls:word; var a:vector);

var m:word;

begin

if  (ls-li)<=1 then schimba(li,ls,a);

else begin

m:=(li+ls)div 2;

divi(li,m,a);

divi(m+1,ls,a);

interclas(li,m,ls,a);

end;

end;

begin

write(‘cate elemente are vectorul?=’);readln(n);

for i:=1 to n do

begin

write(‘tastati elementul’,i,’=’);

readln(v[i]);

end;

divi(1,n,v);

writeln(‘vectorul sortat este:’);         

for i:=1 to n do writeln(v[i]);

end.

OBSERVATII

   4mecanismul general de tip Divide et Impera se gaseste implementat in procedura “divi” ;

  4o astfel de abordare a problemei sortarii unii vector conduce la economie de timp de calcul ,deoarece operatia de interclasare a doi vectori deja ordonati este foarte rapida ,iar ordonarea independenta celor doua jumatati(mini- vectori) consuma in total aproximativ a doua parte din timpul care ar fi necesar ordonarii vectorului luat ca intreg .

4.9 Problema turnurilor din hanoi

Prezentarea algoritmului rezolvarii:

Fie trei tije verticale notate A,B,C .Pe tija A se gasesc asezate  n discuri de diametre diferite, in ordinea crescatoare a diametrelor, privind de sus in jos. Initial, tijele B si C sunt goale.Sa se afiseze toate mutarile prin care discurile de pe tija A se muta pe tija B, in aceeasi ordine, folosind ca tija de manevra C  si respectand urmatoarele reguli:

Ø     la fiecare pas se muta un singur disc;

Ø     un disc se poate aseza numai peste un disc cu diametrul mai mare.

Rezolvarea acestei probleme se bazeaza pe urmatoarele considerente logice:

Ø     daca n=1 ,atunci mutarea este immediata AàB(mut discul de pe A pe B);

Ø     daca n=2,atunci sirul mutarilor este :  AàC,AàB,CàB;

Ø     daca n>2 procedam astfel :

*mut (n-1)discuri AàC;

*mut un disc AàB ;

*mut cele (n-1)discuri CàB.

Observam ca problema initiala se descompune in trei subprobleme mai simple, similare problemei initiale: mut(n-1)discuri AàC, mut ultimul disc pe B, mut cele (n-1)discuri CàB. Dimensiunile acestor subprobleme sunt:n-1,1,n-1.

Aceste subprobleme sunt independente, deoarece tijele initial (pe care sunt dispuse discurile), tijele finale si tijele intermediare sunt diferite. Notam H(n,A,B,C)=sirul mutarilor a n discuri de pe A pe B, folosind C.

Ø     n=1   AàB

Ø     n>1  H(n,A,B,C)= H(n-1,A,C,B),AB,  H(n-1,C,B,A)

program turnurile _hanoi;

var a,b,c:char;

n:integer;

procedure han(n:integer;a,b,c:char);begin

if n=1 then writeln(a,b)

else

begin

han(n-1,a,c,b);

writeln(a,b);

han(n-1,c,b,a);

end;

end;

begin

write(’numarul de discuri=’);

readln(n);

a:=’a’;

b:=’b’;

c:=’c’;

han(n,a,b,c);

end.


4.10 Problema taieturilor

Se da o bucata de tabla cu lungimea l si inaltimea h, avand pe suprafata ei n gauri coordonate numere intregi. Se cere sa se decupeze din ea o bucata de arie maxima care nu prezinta gauri. Sunt permise numai taieturi verticale si orizontale.

Coordonatele vectorilor sunt retinute in doi vectori xv si yv. Dreptunghiul initial si dreptunghiurile care apar in procesul taierii sunt memorate in program prin coordonatele coltului din stanga jos(x,y), prin lungime si inaltime(l,h).Pentru un dreptunghi (initial pornim cu toata bucata d etabla), se cauta daca avem sau nu gaura in el (se cauta practic prima din cele n gauri).In situatia in care aceasta prezinta o gaura, problema se descompune in alte patru probleme de acelasi tip.In cazul in care bucata nu prezinta taieturi, se compara aria ei cu aria unei alte bucati fara gaura, gasita in fazele precedente. Mentionam ca dreptunghiul de arie maxima fara gauri este retinut prin aceeasi  parametri ca si dreptunghiul cu gauri in zonele xf, yf, lf, hf (variabile transmise prin referinta de la o faza la alta).In acest mod problema initiala a fost descompusa in alte probleme de acealsi tip, mai usoare, intrucat fiecare nou dreptunghi acre cel mult n-1 gauri, daca dreptunghiul initial avea n gauri. La aceasta problema compararea solutiilor consta in a retine dreptunghiul cu aria maxima dintre cele fara gauri.

  • Xv(i),yv(i)

Fie dreptunghiul cu o gaura:

                                               l

         h

                                                                                        x,y

Pentru a se afla in interorul dreptunghiului, coordonatele gaurii trebuie sa indeplineasca simultan urmatoarele conditii:

  1. xv(i)>x
  2. xv(i)<x+1
  3. y(v)>y
  4. yv(i)<y+h

Daca faceam o taietura verticala prin acesta gaura obtinem doua dreptunghiuri:

  1. x,y,xv(i)-x,h
  2. xv(i),y,l+x-xv(i),h

In urma unei taieturi pe orizontala se obtin cele doua dreptunghiuri:

  1. x,y,l,yv(i)-y
  2. x,yv(i),l,h+y-yv(i)



program taieturi;

type vect=array[1..9] of integer;

var l,h,i,n,xf,yf,lf,hf:integer;

xv,yv:vect;

procedure dimp(x,y,l,h:integer;var xf,yf,lf,hf:integer;var xv,yv:vect);

var gasit:boolean;i:integer;

begin

i:=1;

gasit:=false;

while (i<=n) and (not gasit) do

if (xV[i]>x) and (xv[i]<x+1) and

(yv[i]>y) and (yv(i)<y+h)

then gasit:=true

else i:=i+1;

if gasit then

begin

dimp(x,y,xv[i]-x,h,xf,yf,lf,hf,xv,yv);

dimp(xv[i],y,l+x-xv[i],h,xf,yf,lf,hf,xv,yv);

dimp(x,y,l,yv[i]-y,xf,yf,lf,hf,xv,yv);

dimp(x,yv[i],l,h+y-yv[i],xf,yf,lf,hf,xv,yv);

end

else

if (l*h)>(lf*hf) then begin xf:=x;

yf:=y;

lf:=l;

hf:=h;

end;

end;

begin

write(’numarul de gauri=’);

readln(n);

for i:=1 to n do

begin

write(’x[’,i,’]=’);

readln(xv[i]);

write(’y[’,i,’]=’);

readln(yv[i]);

end;

write(’lungimea dreptunghiului=’);

readln(l);

write(’inaltimea dreptunhiului=’);

readln(h);

lf:=0;

hf:=0;

dimp(0,0,l,h,xf,yf,lf,hf,xv,yv);

writeln’x=’,xf,’   y=’,yf,’    l=’,lf,’    h=’,hf);

end.

4.11 Problema plierilor

Se considera un vector de lungime n. Definim plierea vectorului prin suparapunerea unei jumatati, numita donoare, peste cealalta jumatate, numita receptoare, cu precizarea ca daca numarul de elemente este impar, elementul din mijloc este eliminat. Prin pliere, elementele subvectorului obtinut vor avea numeroatrea jumatatii recepetoare. Plierea se poate aplica in mod repetat, pana cand se ajunge la un subvector format dintr-un singur element, numit element final.Scrieti un program care sa afiseze toate elementele finale posibile si sa figureze pe ecran pentru fiecare element final o suucesiune de plieri.

program plieri;

const nmax=50;

tyepe element=1..nmax;

var n,i:element;

efinal:array[element] of boolean;

m:array[element] of string;

procedure pliaza(p,q:element);

begin

if p=q then efinal [p]:=true

else

begin

if (q-p+1) mod 2=1 then

begin

efinal[(p+q) div 2]:=false;

ls:=(p+q) div 2-1;

end

else

ls:=(p+q) div 2;

ld:=(p+q) div 2+1;

pliaza(p,ls);

str(ls,ss);

str(ld,sd);

for i:=p to ls do

m[i]:=’d’+sd+’  ’+m[i];

end;

end;

begin

write(‚n=’);

readln(n);

for i:=1 to n do m[i]:=’  ’;

pliaza(1,n);

writeln(’elementele finale sunt:’ ’);

for i:=1 to n do if efinal[i] then begin write (, ’ ’: ’);

writeln(m[i]);

end;

writeln;

end.

Divide Et Impera

Cuprins


    1. Notiuni introductive. 1

    2. Etapele metodei DIVIDE ET IMPERA.. 1

    3. Principiul metodei DIVIDE ET IMPERA.. 2

    4. Aplicatii 5

ü          4.1 Maxim intr-un vector. 5

ü          4.2 Cel mai mare divizor comun. 6

ü          4.3 Codare Sir. 7

ü          4.4 Cautarea binara intr-un sir. 9

ü          4.5 Partitionarea unui sir. 10

ü          4.6 Pozitia k. 11

ü          4.7 Sortare rapida (quicksort). 13

ü          4.8 Sortare prin interclasare(mergesort). 15

ü          4.9 Problema turnurilor din hanoi 17

ü          4.10 Problema taieturilor. 19

ü          4.11 Problema plierilor. 21









Politica de confidentialitate

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Concepte de baza ale sistemului expert - Definitii ale sistemului expert
Blogul cel mai nou instrument de e-marketing
Operatii aritmetice cu numere binare cu semn
ANALIZA RISCULUI - METODA MEHARI
PROIECT ATESTAT INFORMATICA - GESTIONAREA STOCULUI UNEI FARMACII
Scrierea textului
ECDIS parte componenta a Sistemelor Integrate de Comanda
Limbajul PASCAL - Caracteristici


Termeni si conditii
Contact
Creeaza si tu