Metoda de programare“Divide et Impera”

Prof:Neciu Ileana

LICEUL

ECONOMIC ADMINISTRATIV

CUPRINS

Prezentare generală Aplicaţii Valoarea maximă dintr-un vector Sortarea prin interclasare Sortarea rapidă Tunurile din Hanoi Fractali-Curba lui Koch

PREZENTARE GENERALĂ

Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai uşoare), care se rezolvă, iar soluţia pentru problema iniţială se obţine combinând soluţiile subproblemelor. De multe ori, subproblemele sunt de acelaşi tip şi pentru fiecare din ele se poate aplica aceeaşi tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Apasa aici pentru testul de evaluare initial

Divide et impera

1. Completaţi următoarele afirmaţii:(4p) – recursivitatea reprezintă acel mecanism prin care un subprogram se………………– pentru a putea implementa recursivitatea se foloseşte structura de date numită………...– atunci când un subprogram se autoapelează se depun în stivă:

………………. parametrilor transmişi prin valoare; ………………..parametrilor transmişi prin referinţă; ……………….. variabilelor locale.

– Specificaţi valoarea de adevăr a afirmaţiei: pentru orice algoritm iterativ există unul recursiv echivalent. Echivalenţa este adevărată?

2. Ce va afişa următorul program dacă se citesc de la tastură numerele13şi 17 :(4p)

#include<iostream.h> int a,b; int ab(int a) { if(a>0) return a%2+ab(a/2); else return 0;} void main() { cout << ”a=”; cin>>a; cout << ”b=”; cin>>b; cout << ab(a)+ab(b); }   a) 8 b) 7 c) 5 d)6

 

VALOAREA MAXIMĂ DINTR-UN VECTOR

APLICATIA 1

Valoarea maximă dintr-un vector

Se citeste un vector cu n componente, numere naturale. Secere să se tipărească valoarea maximă. Rezolvare. Trebuie tipărită valoarea maximă dintre numerele

reţinute în vector de la i la j (iniţial, i=1 şi j=n).Pentru aceasta, procedăm astfel:Dacă i=j, valoarea maximă va fi v[i];Contrar, vom împărţi vectorul în doi vectori (primul vector vaconţine componentele de la i la (i+j) div 2, al doilea va conţinecomponentele de la (i+j) div 2+1 la j, rezolvăm subproblemele(aflăm maximul pentru fiecare din ele), iar soluţia problemei va fidata de valoarea maximă dintre rezultatele celor douăsubprobleme.

Apasă aici pentru a vizualiza executabilul

Apasă aici pentru a vedea un exemplu

#include<iostream.h> #include<conio.h> int v[10], n; int max (int i, int j) {int a, b; if (i==j) return v[i]; else {a=max (i, (i+j)/2); b=max ((i+j)/2+1,j); if(a>b) return a; else return b;}} main() {cout<<"n= " ; cin>>n; for (int i=1; i<=n; i++) {cout<<"v[" <<i<<"]="; cin>>v[i];} cout<<"max="<<max(1,n); getch();}

EXEMPLU n=5

7 213 141

1 2 3 4 5

SORTAREA PRIN INTERCLASARE

APLICATIA 2

Sortarea prin interclasare

Se consideră vectorul a cu n componente numere întregi (sau reale). Să se sorteze crescător, utilizând sortarea prin interclasare.

Rezolvare Algoritmul de sortare prin interclasare se bazează pe următoarea idee: pentru asorta un vector cu n elemente îl împărţim în doi vectori care, odată sortaţi, seinterclasează. Conform strategiei generale DIVIDE ET IMPERA, problema este descompusă înalte două subprobleme de acelaşi tip şi, după rezolvarea lor rezultatele se combină(în particular se interclasează). Descompunerea unui vector în alţi doi vectori careurmează a fi sortaţi are loc până când avem de sortat vectori de una sau douăcomponente. În aplicaţie, funcţia sort sorteză un vector cu maximum două elemente; intercinterclasează rezultatele; divimp implementează strategia generală a metodeistudiate.

Apasă aici pentru a vizualiza executabilul

#include<iostream.h> int a[10], n; void sort (int p, int q, int a[10]) { int m; if (a[p]>a[q]) {m=a[p]; a[p]=a[q]; a[q]=m; } } void interc (int p, int q, int m, int a[10]) {int b[10], I, j, k; i=p; j=m+1; k=1; while (i<=m && j<=q) if (a[i]<=a[j]) {b[k]=a[i]; i=i+1; k=k+1; } else {b[k]=a[j]; j=j+1; k=k+1; } if (i<=m) for(j=I; j<=m; j++) {b[k]=a[j]; k=k+1; } else

for (i=j; j<=q; j++){b[k]=a[i];k=k+1;}k=1; for (i=p; i<=q; i++){a[i]=b[k];k=k+1;}}void divimp (int p, int q, int a[10]){int m;if ((q-p)<=1) sort (p, q, a);else{m=(p+q)/2;divimp (p, m, a);divimp (m+1, q, a);interc(p, q, m, a);}}main (){int i;cout<<”n=”; cin>>n;for (i=1; i<=n; i++){cout<<”a[“<<i<<”]=”;cin>>a[i];}divimp (1,n, a);for (i=1; i<=n; i++)cout<<a[i]<<” “;} 

SORTAREA RAPIDĂ

APLICATIA 3

Sortarea rapidă

Fie vectorul a cu n componente numere întregi (sau reale). Se cere ca vectorul să fie sortat crescator.

Rezolvare. Este necesara o funcţie POZ care tratează o porţiune din vector, cuprinsă întreindicii daţi de li (limita inferioară) şi ls (limita superioară). Rolul acestei funcţii este de apoziţiona prima componentă a [li] pe o poziţie k cuprinsă intre li şi ls, astfel încât toate componentelevectorului cuprinse între li şi k-1 să fie mai mici sau egale decât a [k] şi toate componentele vectoruluicuprinse intre k+1 şi ls să fie mai mari sau egale decât a [k].În această funcţie există două moduri de lucru: i rămâne constant, j scade cu 1; i creşte cu 1, j rămâne constant. Funcţia este concepută astfel: iniţial, i va lua valoarea li, iar j va lua valoarea ls (elementul care iniţial se află pe poziţia li se va

gasi mereu pe o poziţie dată de i sau de j); se trece în modul de lucru a); atăt timp cât i<j, se execută :

– dacă a[i] este strict mai mare decât a [j], atunci se inversează cele două numere şi se schimbă modul de lucru;

– i şi j se modifică corespunzător modului de lucru în care se află programul;– k ia valoarea comuna a lui i şi j.

TUNURILE DIN HANOI

APLICATIA 4

Tunurile din Hanoi

Se dau 3 tije simbolizate prin a, b, c. Pe tija a se găsesc discuri de diametre diferite, aşezate înordine descrescătoare a diametrelor privite de jos în sus. Se cere să se mute discurile de pe tija a petija b, utilizând ca tijă intermediară tija c, respectând următoarele reguli:- la fiecare pas se mută un singur disc- nu este permis să se aşeze un disc cu diametrul mai mare peste un disc cu diametrul mai mic. Rezolvare. Dacă n=1, se face mutarea ab, adică se mută discul de pe tija a pe tija b.Dacă n=2, se fac mutările ac, ab, cb.În cazul în care n>2, problema se complică. Notam cu H(n, a, b, c) şirul mutărilor celor n discuri de petija a pe tija b, utilizând ca tijă intermediara, tija c.Conform strategiei DIVIDE ET IMPERA, încercam să descompunem problema în alte douăsubprobleme de acelaşi tip, urmând apoi combinarea soluţiilor. În acest sens, observăm că mutareacelor n discuri de pe tija a pe tija b, utilizând ca tijă intermediara tija c, este echivalentă cu:mutarea a n-1 discuri de pe tija a pe tija c, utiliyând ca tijă intermediară tija b; mutarea discului rămaspe tija b; mutarea a n-1 discuri de pe tija c pe tija b, utilizând ca tija intermediara tija a.Parcurgerea celor trei etape permite definirea recursivă a şirului H (n, a, b, c) astfel:

H(n, a, b, c)=

1,,,,1,,,,,1

1,

nabcnHabbcanH

nabApasă aici pentru a vedea un exemplu

A B C

AB AC BC AB CA CB AB

FRACTALI

APLICATIA 5

Fractali

Se consideră un triunghi echilateral. Fiecare latură a sa se transformă astfel:

Fiecare latură a acestui poligon se transformă din nou, după aceeaşi regulă. Se cere să se vizualizeze figura obţinută după ls paşi ( număr citit de la tastatură).

Programul principal va apela, pentru fiecare segment careconstituie o latură a triunghiului, o procedură numită generator.Algoritmul care stă la baza procedurii generator: Se porneşte de la segmentul AB; Se determină coordonatele punctului care constituie vârful

triunghiului echilateral( V) În cazul în care segmentul nu a fost transformat de ls ori, se

apelează generator pentru segmentele AC, CV, VD, DB Contrar, se apelează procedura care trasează linia frântă

ACVDB

INTREBARE…..

Se da urmatorul vector:( algoritmul de interclasare)

61 11 92 24 99 80 13 85 7 93 79 a) n=? b) intre ce indici va fi divizat vectorul prima data? c) care portiune a vectorului va fi divizata in continuare? d) ce se va intampla in continuare? e) in cate grupe va fi impartita ce a de a 2 a jumatate? f) ce va face programul in continuare?

SITE-URI DE INFORMARE

http://ro.wikipedia.org/wiki www.didactic.ro www.subiecte2008.edu.ro www.ginfo.ro www.referate.ro www.edu.ro

BIBLIOGRAFIE

Manual de informatică intensiv, clasa a XI-a- Editura L&S Soft, Vlad Huţanu şi Tudor Sorin [64..88]

Probleme rezolvate şi algoritmi, Editura Polirom, Doina Hrinciuc Logofătu[216..222]

Culegere de probleme de informatică, Editura Petrion, Adrian Atanasiu şi Rodica Pintea [168..193]

Materiale educaţionale AEL – SC SIVECO SA L. Livovschi, G. Georgescu, Sinteza şi analiza

algoritmilor, Ed. Stiinţifică şi Enciclopedică, 1986

RECAPITULARE

1. In ce consta metoda Divide et Impera? 2. Tunurile din Hanoi. Pornind de la definirea recursiva a

sirului H(n,a,b,c)= ab, ptr. n=1, H(n-1, a,c,b), ab, H(n-1, c,b,a) ptr. n>1

pentru n=3 care sunt mutarile discurilor?