GRUP SCOLAR LUCIAN BLAGA REGHIN

Coordonator: Prof. Cazan Minodora Autor: Moldovan Aurelian-Ionut

- 2009 CUPRINS1)

Introducere-Argumentarea temei alese 3

2) Turnurile din Hanoi. 4 3) Ce trateaza lucrarea. 5 4) Descrierea programului si a unit-urilor folosite.. 5 5) Program 6

2

ARGUMENTAREA TEMEI ALESE Am ales aceasta tema datorita importantei pe care o are aceasta tehnica de programare, dar si pentru ca Turnurile din Hanoi era unul din jocurile mele preferate in copilarie. Divide et impera se bazeaz pe principiul descompunerii problemei n dou sau mai multe subprobleme (mai uoare), care se rezolv, iar soluia pentru problema iniial se obine combinnd soluiile subproblemelor. De multe ori, subproblemele sunt de acelai tip i pentru fiecare din ele se poate aplica aceeai tactic a descompunerii n (alte) subprobleme, pn cnd (n urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediat. Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma c numrul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorit cerinei ca problema s admit o descompunere repetat. Divide et impera este o tehnic ce admite o implementarea recursive. Principiul general prin care se elaboreaz algoritmi recursivi este: "ce se ntmpl la un nivel, se ntmpl la orice nivel" (avnd grij s asigurm condiiile de terminare). Aadar, un algoritm prin divide et impera se elaboreaz astfel: la un anumit nivel avem dou posibiliti: s-a ajuns la o problem care admite o rezolvare imediat (condiia de terminare), caz n care se rezolv i se revine din apel; nu s-a ajuns n situaia de la punctul 1, caz n care problema curent este descompus n (dou sau mai multe) subprobleme, pentru fiecare din ele urmeaz un apel recursiv al funciei, dup care combinarea rezultatelor are loc fie pentru fiecare subproblem, fie la final, naintea revnirii din apel.

3

TURNURILE DIN HANOI

Se spune ca intr-un templu din Benares(India) preotii lucreaza incontinuu, mutand discuri de aur de pe un ac de diamante pe altul. Atunci cand lumea a fost create, preotilor din Benares le-au fost daruite 3 ace de diamante si 64 discuri de aur. Preotilor li s-a poruncit sa depuna pe unul din ace toate discurile, in ordine descrescatoare, apoi sa mute intregul turn astfel format pe unul din celelalte doua ace, mutand cate un disc o data si fara a pune un disc mai mare peste unul mai mic. In conformitate cu legenda Dumnezeu le-a zis oamenilor:cand veti termina de mutat turnul, atunci lumea se va sfarsi! Jocul Turnurile din Hanoi( uneori numit si turnurile din Brahma ) a fost inventat de matematicianul francez Edouard Lucas, in 1883. el s-a inspirit din legenda unui templu hindus care folosea un astfel de joc pentru disciplina mentala a tinerilor calugari. Regulile jocului sunt simple: la o mutare se deplaseaza un singur disc

un disc mai mare nu poate fi pus peste un disc mai mic

4

CE TRATEAZA LUCRAREA Lucrarea Metoda Divide et Impera prezinta metoda si exemple in care se foloseste ea. Programul se lanseaza in executie prin fisierul Di.exe. Primul ecran prezinta titlul lucrarii numele autorului si pe cel al coordonatorului, al doilea ecran prezinta cuprinsul acesteia. Trecerea de la un ecran la urmatorul se face prin tastarea Enter. Din Cuprins se pot alege cu ajutorul mouse-ului urmatoarele optiuni: Metoda Divide et Impera.Exemplu. -> contine un ecran ce contine o scurta descriere a metodei si un exemplu animat. Turnurile din Hanoi cu trei optiuni::Enuntul problemei-un ecran in care este descrisa problema,Animatie pentru n discuri 4 ecrane in care este prezentata animat mutarea discurilor pe tije,Program-un ecran cu descrierea programului. Cautare binara cu doua optiuni:Enunt si exemplu animat-un ecran in care este enuntul unei probleme si un exemplu animat,Program-un ecran cu programul. Iesirea din fiecare meniu se face prin tastarea Enter, iar trecerea de la un ecran la altul in cazul meniurilor cu doua ecrane se face tot prin tastarea Enter. Iesirea din program se face actionand butonul Iesire. DESCRIEREA PROGRAMULUI SI A UNIT-URILOR FOLOSITE

Programul principal se numeste di.pas. El apeleaza unit-urile limbajului: Crt, Graph si unit-urile aditionale di_Mouse, di_ex,di_anim,di_ecran. Initializarea modului de lucru grafic se face cu ajutorul procedurii InitGraph, iar lucrul cu mouse-ul necesita variabilele found, button, clicks. Dupa initializarea modului grafic si pregatirea mediului, se apeleaza procedura Ecran1 ce prezinta prima pagina a programului si procedura ecran2 care afiseaza cuprinsul Unit-ul di_Mouse contine procedurile si functiile necesare lucrului cu mouse-ul. Unit-ul di_ex are procedurile:ex1,ex2,ex3 si ex4 Care descriu cele 4 exemple de la turnirile din Hanoi.

5

Unit-ul di_anim -are procedurile pop_titlu, titlu, pop, sterg,d1..d4,tc,ta,tije,buton,cuprinscare realizeaza animatia. Unit-ul di_ecran-are 6 ecrane: Ecranul1prezinta titlul lucrarii, autorul si profesorul coordonator. Ecranul2prezinta cuprinsul Ecranul3prezinta turnurile din Hanoi.Enunt Ecran4prezinta programul de la turnuri. Ecran5teoria referitoare la Cautare Binara:enunt si exemplu animat. Ecran6programul pentru cautare binara. PROGRAM DIVIDE ET IMPERA Uses graph, crt, di_anim, di_ex, di_mouse, di_ecran; Var found:boolean; buttons, clicks,x,y:integer; Procedure InitGr; Var gd, gm:integer; begin gd:=detect; InitGraph(gd,gm,' '); If GraphResultgrOK then begin writeln('Nu se poate face initializarea'); Readln; Halt(1) end; ClearDevice; end; begin

6

initgr; cleardevice; ecran1; cleardevice; cuprins; resetmouse(found,buttons); if not found then begin clrscr; writeln('Mouse-ul nu este instalat!!!'); readln; exit end; defgraphlocator(arrow); setmouse(50,50); defsensitivity(16,16); showlocator; buton(195,145,460,160,10); buton(245,205,390,220,10); buton(245,265,275,280,10); buton(310,265,340,280,10); buton(380,265,415,280,10); buton(450,265,485,280,10); buton(245,295,310,310,10); buton(245,355,440,370,10); buton(245,385,310,400,10); buton(195,425,255,440,10); repeat setcolor(14);

7

outtextxy(200,150,'METODA DIVIDE ET IMPERA. EXEMPLU'); setcolor(15); outtextxy(200,180,'TURNURILE DIN HANOI'); setcolor(14); outtextxy(250,210,'Enuntul problemei'); setcolor(15); outtextxy(250,240,'Animatie pentru n discuri'); setcolor(14); outtextxy(250,270,'n=1 setcolor(15); outtextxy(200,330,'CAUTARE BINARA'); setcolor(14); outtextxy(250,360,'Enunt si exemplu animat'); outtextxy(250,390,'Program'); outtextxy(200,430,'IESIRE'); buttons:=1; ClickNumber(buttons,clicks,x,y); if (x>195) and (x145) and (y1;',15);

line(150,373,150,415); pop(150,440,'Apasati Enter pentru intoarcerea la Cuprins!',13); readln; cleardevice; cuprins; end; procedure ecran4; begin cleardevice; titlu(80,100,'TURNURILE DIN HANOI - Program',10); pop(50,160,'Program Hanoi;',15); pop(50,175,'var A, B, C: char;',15); pop(50,190,' n: integer;',15); pop(50,205,'procedure H(n:integer; A, B, C:char);',15); pop(50,220,'begin',15);

23

pop(50,235,' pop(50,250,' pop(50,265,' pop(50,280,' pop(50,295,' pop(50,310,'

if n=1 then writeln(A,B)',15); else begin',15); H(n-1,A,C,B);',15); writeln(A,B);',15); H(n-1,C,B,A);',15); end;',15);

pop(50,325,'end;',15); pop(50,340,'begin {program principal}',15); pop(50,355,' pop(50,370,' pop(50,385,' pop(50,400,' pop(50,415,' write('+''''+'n='+''''+'); readln(n);',15); A:='+''''+'A'+''''+';',15); B:='+''''+'B'+''''+';',15); C:='+''''+'C'+''''+';',15); H(n,A,B,C);',15);

pop(50,430,'end.',15); pop(150,445,'Apasati Enter pentru intoarcerea la Cuprins!',13); readln; cleardevice; cuprins; end; procedure ecran5; begin cleardevice; titlu(200,100,'CAUTARE BINARA',10); blink(50,180,'Enunt:',13); pop(50,195,'Fie un sir de n numere intregi ordonat crescator. Dandu-se un numar nr de',14); pop(30,210,'la tastatura, se cere sa se caute numarul in sir si daca este gasit sa se ',14); pop(30,225,'afiseze pozitia acestuia. Daca nu este gasit, sa se afiseze un mesaj.',14); blink(50,250,'Ex:',13);

24

pop(50,265,'Consideram sirul A de mai jos, unde n=7',14); blink(50,280,'2',15); blink(80,280,'5',15); blink(110,280,'7',15); blink(140,280,'8',15); blink(170,280,'9',15); blink(200,280,'11',15); blink(230,280,'23',15); pop(50,300,'Sa cautam un numar care se gaseste in sir: nr=5',14); pop(30,315,'- se ia elementul din mijloc',15); delay(100); blink(140,280,'8',10); delay(100); pop(30,330,'- se verifica daca acesta este numarul cautat. In cazul nostru NU',15); delay(100); pop(30,345,'- se compara nr de cautat cu elementul din mijloc. La noi 5