Metoda de programare“Divide et Impera”

Teodor Delaport

Clasa XI-a A

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ă.

Divide et impera

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

TUNURILE DIN HANOI

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

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

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

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?