Contributii Privind Metodele de Programare

În decursul anilor, informatica a fost revoluționată de câteva noi metode de programare. Printre acestea se numără programarea structurată, modulară și cea orientată pe obiecte. Aceste metode se referă la modul în care sunt construiți algoritmii, respectiv programele. Aplicarea corectă a acestor metode poate duce în anumite situații la îmbunătățirea cu cel puțin un ordin de mărime a productivității, fiabilității și a costului întreținerii sistemelor software.

Începutul programării structurate aparține profesorului E. W. Dijkstra de la Universitatea Eindhoven care în 1965 sugerează ideea construirii unor programe mai bune prin evitarea instrucțiunii GoTo. În acest fel se evită transferul explicit al execuției de la o instrucțiune la alta. Următorul pas important aparține lui Bohm și Jacopini care, în 1966, publică o lucrare în care demonstrează că sunt suficiente 3 tipuri de transfer a execuției pentru a exprima logica internă a oricărui program: secvența, selecția și iterația.

Un program poate fi privit ca un sistem. Structura unui program, adică componentele și relațiile dintre ele, reprezintă o proprietate esențială a sa.

La nivelul cel mai elementar se observă că un program este compus din instrucțiuni. O astfel de instrucțiune este o informație care descrie exact un obiect supus prelucrării sau o operație pe care o mașină reală sau virtuală o poate executa. Calculatoarele prelucrează informațiile prin executarea unor operații simple. Deși operațiile sunt elementare, prin înlănțuirea unei mulțimi de operații se poate ajunge la operații deosebit de complexe. Combinarea operațiilor nu se face la întâmplare, ea supunându-se unor reguli bine precizate. Deși un algoritm este o mulțime finită de operații cunoscute care se execută într-o ordine bine stabilită asupra unor date de intrare și conduc într-un timp finit la un set de date de ieșire. Algoritmii trebuie să cuprindă analiza tuturor situațiilor posibile, nelăsând nimic la voia întâmplării.

O modalitate de descriere a algoritmilor este pseudocodul. Aceasta reprezintă o notație textuală ce permite exprimarea logicii programelor într-un mod oarecum formalizat fără a fi necesare totuși reguli de sintaxă riguroase ca în limbajele de programare. În principiu, în orice pseudocod se folosesc 2 tipuri de propoziții: propoziții standard și propoziții nestandard.

Programarea modulară este metoda ce are la bază principiul modularizării. Termenul modular este folosit pentru a desemna un programa care a fost structurat în mai multe părți, puternic independente numite module. Pentru a evolua obiectiv calitatea structurii unui program rezultat din procesul de proiectare se folosesc în principal două mărimi: consistența și cuplajul modulelor. Fiecare modul are trei atribute de bază: funcția, logica internă și interfața.

Un modul Turbo Pascal este o colecție de constante, variabile, proceduri și funcții care sunt compilate separat și pot fi folosite de alte module sau de programul principal.

Programarea modulară conduce la o centralizare a tuturor datelor de un anumit tip sub controlul unui modul de gestionare a tipului.

Programarea orientată pe obiecte este o metodă de programare care duce la creșterea productivității construirii produselor program. Ea reprezintă o evoluție naturală de la metodele de programare: este mai structurată decât încercările anterioare de structurare a programelor, mai modulară și mai abstractă decât încercările anterioare de ascundere a datelor și de abstractizare.

De multe ori, puși în fața unei probleme pentru care trebuie să elaborăm un algoritm, nu știm cum să începem. De aceea lucrarea de disertație tratează două din metodele de programare și anume metoda backtracking și metoda divide et impera. Pentru exemplificare s-au întocmit programe demonstrative pentru colorarea unei hărți cu n țari și c culori, partițiile unei mulțimi, descompunerea unui număr natural, sortarea prin interclasare a elementeleor unui vector și problema plierii.În capitolele I și II voi prezenta metodele generale de elaborare a algoritmilor care ne vor ajuta la rezolvarea unor clase de probleme.

CAP. I. METODA BACKTRACKING

O metodă simplă de rezolvare a problemelor a căror soluție se prezintă sub forma: x1,x2,… ,xi, …, constă în a genera într-un mod oarecare toate soluțiile posibile și de a verifica dacă ele satisfac condițiile interne. Dezavantajul acestei metode constă în faptul că timpul cerut este foarte mare.

Acest proces poate fi reprezentat cu ajutorul unui arbore care reprezintă mulțimea soluțiilor parțiale. Reprezentare se face după cum urmează:

rădăcina arborelui este reprezentată de vectorul nul;

fii unui nod de nivel k-1 reprezintă elementele mulțimii Sk.

Fig. 1

În situația descrisă în figura 1, algoritmul parcurge arborele în ordinea indicată de săgețile punctate.

Soluțiile se pot determina prin încercări succesive de extindere a unei soluții parțiale. În fiecare etapă a căutării pentru care nu este posibilă o extindere a soluției parțiale curente, se revine la o soluție parțială anterioară și se încearcă din nou. Se reduce astfel foarte mult numărul soluțiilor generate.

Această metodă a fost numită backtracking de către D.H.Lehmer în 1950 și a fost prezentată în forma actuală pentru prima dată de R.J.Walker.

Metoda este utilizată pe scară largă pentru rezolvarea problemelor combinatorice din domeniul analizei sintactice, jocurilor și optimizărilor, aplicându-se în cazul problemelor a căror soluție se prezintă sub forma: x1,x2,… ,xi, …, atunci când nu există nici o altă cale de rezolvare a problemei propuse deoarece timpul de execuție este de ordin exponențial. Metoda utilizează structura de stivă și poate fi programată și iterativ și recursiv.

I.1. VARIANTA ITERATIVĂ

Soluția unei probleme se poate pune sub forma unui vector X=(x1,x2,…,xn)S, S=S1×…×Sn unde Card(Si)=si. Componentele vectorului X satisfac anumite relații, numite condiții interne.

De exemplu: considerăm două mulțimi: S1={a, b, c}, S2={m, n}. Să se determine perechile (x1,x2) cu x1 S1, x2 S2 cu proprietatea că dacă x1 este a sau b atunci x2 nu poate fi n.

Rezolvarea conduce la: (a, m), (b, m), (c, m), (c, n).Din cele 6 soluții posibile, numai acestea patru îndeplinesc condițiile interne.

Soluțiile din spațiul soluțiilor posibile S, care satisfac condițiile interne, se numesc soluții rezultat.

O importanță mare în reducerea duratei de execuție a programului o are reducerea numărului de noduri din arborele în care se face căutarea.

Pentru a realiza aceasta există patru modalități:

revenirea la soluția anterioară trebuie să se facă de îndată ce s-a ajuns la concluzia că soluția parțială curentă nu mai poate produce soluții;

să nu se parcurgă ramuri ale arborelui care sunt izomorfe cu altele, dacă acestea au fost parcurse;

nodurile trebuie să fie aranjate în arbore astfel încât cele care au un grad mai mic să se afle pe un nivel superior față de cele care au un grad mai mare;

în cazul în care se dorește obținerea unei soluții optime este indicat să se genereze soluțiile parțiale în ordinea creșterii costului.

Construirea unei soluții se face în mai mulți pași , rezultând că elementele vectorului X primesc valori pe rând: lui xk îi atribuim o valoare din Sk, numai după ce x1,…xk-1 au primit valori. După ce xk a primit o valoare, se verifică condițiile de continuare referitoare la x1,…,xk și numai dacă acestea au dat răspuns afirmativ se trece la atribuirea unei valori pentru xk+1 din Sk+1.

Neîndeplinerea condițiilor de continuare exprimă faptul că oricum s-ar alege xk+1,…,xn, nu se va ajunge la o soluție rezultat.

Condițiile de continuare sunt strict necesare .

În cazul neîndeplinirii condițiilor de continuare pentru xk, se va face o nouă alegere pentru xk din Sk (dacă mai există elemente din Sk).

Dacă Sk a fost epuizat, atunci se micșorează k cu o unitate, deci o nouă alegere pentru xk-1 și apoi se încearcă o nouă valoare pentru xk din Sk.

Micșorarea lui k cu o unitate dă numele metodei și semnifică faptul că atunci când nu putem avansa, vom urmări înapoi secvența curentă din soluție.

O alegere bună a condițiilor de continuare conduce la reducerea numărului de calcule. Ideal condițiile de continuare ar trebui să fie nu numai necesare dar și suficiente pentru obținerea unei soluții. Acestea reprezintă restricția condițiilor interne la primele k componente. Când k = n, condițiile interne sunt chiar condiții de continuare. Orice vector soluție se obține progresiv începând cu prima componentă și mergând către ultima, cu eventualele reveniri asupra valorilor atribuite anterior. Prin atribuiri sau încercări de atribuire eșuate din cauza neîndeplinirii condițiilor de continuare, anumite valori sunt consumate.

Pentru o componentă xk, se notează Ck mulțimea valorilor consumate la momentul curent (Ck Sk).

În momentul în care se încearcă atribuirea unei valori componentei xk, atunci se precizează valorile curente v1,…vk-1 ale componentelor x1,…,xk-1 și mulțimile C1,…,Ck-1 de valori consumate pentru fiecare x1,…xk-1.

Se obține un tablou numit configurație de forma:

cu semnificația:

Componentele x1, x2, … ,xk-1 au primit valorile v1,…,vk-1 (soluție parțială).

b) Valorile satisfac condițiile de continuare.

c) Se încearcă o atribuire asupra componentei xk. Pentru că valorile consumate până în acest moment sunt cele din Ck, ea urmează a primi vkSk\Ck (o valoare neconsumată).

d) Valorile consumare pentru x1, …,xk-1 sunt din mulțimile C1,…,Ck-1, cu precizarea că valorile curente v1,v2, … ,vk-1 sunt considerate consumate, deci apar în mulțimile C1, … ,Ck-1.

e) Pentru xk+1, … ,xn nu s-a considerat nici o valoare și deci Ck+1= … =Cn= .

f) Până acum au fost construite deja:

– eventuale soluții de forma (v1, … ,vk-1, ck, …) cu ck Ck;

– eventuale soluții de forma (c1, … ,ck-1)C1× … ×Ck-1 cu (c1, … ,ck-1) (v1, … ,vk-1).

Metoda începe să fie aplicată dacă nu a fost consumată nici o valoare și se încearcă o atribuire asupra primei componente.

Acest lucru este specificat prin configurația inițială:

Alt caz de configurație este cel al configurației soluției cu forma:

cu semnificația că vectorul (v1, … ,vn) este soluție a problemei în conformitate cu subpunctele a), b).

Orice configurație poate fi obiectul a patru tipuri de modificări:

Atribuie și avansează. Aceasta are loc atunci când mai există valori neconsumate pentru xk, iar valoarea aleasă vk Sk\Ck are proprietatea că v1, v2, … ,vk-1, vk satisfac condițiile de continuare. În acest caz vk se atribuie lui xk și se adaugă lui Ck, după care se avansează la componenta xk+1. Aceasta configurație este notată astfel :

Încercare eșuată. Se produce o astfel de încercare, când mai există valori neconsumate pentru xk, dar valoarea aleasă vk Sk Ck, face ca v1, … ,vk-1, vk să nu verifice condițiile de continuare. În acest caz vk se adaugă la Ck dar nu se avansează la componenta următoare.

3) Revenire. Acest tip are loc când toate valorile pentru xk au fost epuizate (Ck=Sk). Se revine la componenta xk-1, încercând atribuirea unei noi valori. Pentru această nouă valoare a lui xk-1 se vor încerca ulterior toate valorile posibile pentru xk, deci revenirea la xk-1 trebuie însoțită de reconsiderarea valorilor consumate (Ck= ).

4) Revenire după construirea unei soluții. Se revine la situația în care ultima componentă xn urmează să primească alte valori (dacă nu există) pentru construirea altei soluții.

Mulțimile S1, S2, …,Sn sunt finite, iar prin modificări de configurație se ajunge la următoarea configurație finală:

Observații

1) Condiția k=n+1 este utilizată pentru a sesiza obținerea unei soluții.

2) Condiția k=0 este utilizată pentru a sesiza sfârșitul procesului de construcție a soluțiilor.

Procesul de obținere a vectorilor soluție se programează ușor deoarece oricei noi valori. Pentru această nouă valoare a lui xk-1 se vor încerca ulterior toate valorile posibile pentru xk, deci revenirea la xk-1 trebuie însoțită de reconsiderarea valorilor consumate (Ck= ).

4) Revenire după construirea unei soluții. Se revine la situația în care ultima componentă xn urmează să primească alte valori (dacă nu există) pentru construirea altei soluții.

Mulțimile S1, S2, …,Sn sunt finite, iar prin modificări de configurație se ajunge la următoarea configurație finală:

Observații

1) Condiția k=n+1 este utilizată pentru a sesiza obținerea unei soluții.

2) Condiția k=0 este utilizată pentru a sesiza sfârșitul procesului de construcție a soluțiilor.

Procesul de obținere a vectorilor soluție se programează ușor deoarece orice modificare de configurare nu afectează decât puține elemente : indicele k al componentei din dreapta barei, componenta xk, mulțimea de valori consumate C1,…,Ck.

Algoritmul în pseudocod este:

Inițializare S1, S2, … ,Sn {construiește configurația inițială}

k 1, Ci

while k > 0 {configurația nu este finală}

if k = n+1

then reține soluția X (x1, …,xn) {configurația e tip soluție}

k k-1 {revenire după construirea unei soluții}

else

if Ck < > Sk {există valori neconsumate}

then alege vk Sk \ C k

Ck Ck U {vk}

if v1, …, vk satisfac condiția de continuare

then xk vk , k k+1 {atribuie și avansează}

else {încercare eșuată}

endif

else Ck , k k-1 {revenire}

endif

endif

endwhile

end

Multe aplicații ale backtracking-ului necesită relativ puțină memorie și deci este rezonabil să se mărească cantitatea de memorie folosită pentru a micșora durata execuției. Acest lucru poate fi realizat în limbaje care posedă posibilități de macroexpandare astfel încât o parte din calcule să se efectueze în timpul compilării.

Particularizări pentru această metodă se obțin astfel:

1) Dacă se consideră Si = {1,2,… si} i=1,n atunci Sk este reprezentată prin numărul său de elemente sk.

În plus, presupunem că valorile pentru fiecare xk vor fi alese în ordine crescătoare.

În aceste condiții fiecare Ck e de forma 1,2,…,vk și vor fi reprezentate doar prin valoarea vk, iar Ck= dacă și numai dacă vk=0

2) În multe probleme, mulțimile în care xk poate lua valori sunt identice cu o mulțime finită oarecare S, cu s elemente (S= {1,2,…,s} ), rezultând următoarea procedură backtracking:

procedure back ;

var k,i: integer;

begin

k:=1;

for i:=1 to n do x[i]:=0; {configurația inițială}

while k < > 0 do

if k = n+1

then begin retsol; k:= k-1 end {cofigurație de tip soluție}

else

if x[k ]< s

then {există o valoare neconsumată pentru xk }

begin

x[k] := x[k] +1; {s-a ales valoarea următoare}

if continuare(k) then k:=k+1 {avansare}

end

else begin x[k]:=0; k:=k-1 end

end;

Procedura back apelează:

– procedura retsol care reține soluția X (listează soluția, compară soluția curentă cu cea precedentă etc. );

– funcția continuare(k) care verifică dacă valorile primelor k componente ale lui X satisfac condițiile de continuare. Dacă da se întoarce valoarea de adevărat, dacă nu , se întoarce valoarea fals.

Există două variante față de metoda standard:

soluțiile pot avea număr variabil de componente;

dintre soluții se alege cea care optimizează o funcție cost sau o funcție obiectiv dată.

I.2. VARIANTA RECURSIVĂ A

METODEI BACKTRACKING

În cazul standard s-a convenit ca mulțimile în care componentele lui X să ia valori, să fie identice cu mulțimea S = {1,2, …,s}.

Forma recursivă a algoritmului backtracking este:

procedure back (k: integer);

var i: integer;

begin

if k = n+1 then retsol

else for i:= 1 to s do

begin xk := i;

if cotinuare(k) then back( k+1 )

end

end;

Parametrul k reprezintă numărul de ordine al componentei lui X ce urmează să primească o valoare din S. În unitatea de program ce inițiază procedura backtracking se va utiliza apelul back(1).

Metoda recursivă prezentată anterior are avantajul de a fi naturală și lizibilă, dar are dezavantajul de a fi mai puțin eficientă deoarece se încarcă inutil stiva calculatorului.

CAP. II. METODA DIVIDE_ET_IMPERA

Rezolvarea unei probleme se poate face uneori astfel: se partiționează problema în părți mai mici, se rezolvă fiecare parte separat și apoi se combină soluțiile obținându-se soluția finală. Această abordare conduce, mai ales atunci când este folosită recursiv, la soluții eficiente pentru probleme la care subproblemele sunt versiuni mai mici ale problemei inițiale.

Metoda DIVIDE_ET_IMPERA constă deci, în împărțirea repetată a unei probleme în două sau mai multe probleme de același tip, urmată de combinarea soluțiilor subproblemelor pentru a obține soluția problemei inițiale.

Fie vectorul A = (a1, … ,an) asupra căruia se face o prelucrare. Presupunem că pentru ()p,qN, 1<=p<q<=n, () un m din mulțimea {p,…,q-1} astfel încât prelucrarea secvenței {ap,…,aq},se face prelucrând secvențele vecine următoare {ap,…,am}, {am+1,…,aq} și apoi combinând rezultatele pentru a obține prelucrarea întregii secvențe {ap, … ,aq}

Deoarece subproblemele rezultate prin separare sunt de același tip cu problema inițială, metoda se exprimă în mod natural prin următoarea procedură:

procedure DivImp (p, q, ..)

begin

if q – p <= then call Sol (p, q, )

else call Div (p, q, m)

call DivImp (p, m, )

call DivImp (m+1, q, )

call Comb ( , , )

endif

end

Se observă că datele sau intrările se păstrează într-un vector între indicii p și q (dimensiunea problemei este q-p+1) și că problema se împarte în două subprobleme. Dacă dimensiunea problemei inițiale sau a subproblemelor apărute este mai mici decât atunci problema se rezolvă direct prin procedura Sol, soluția fiind furnizată în .

Procedura Div împarte procedura în două subsecvențe {ap, … ,am} și {am+1,…,aq}, furnizând rezultatul în m. Prin cele două autoapelări se rezolvă subproblemele punând rezultatele prelucrărilor în respectiv .

Procedura Comb construiește din soluțiile subproblemelor soluția problemei inițiale. La prima apelare parametrii din DivImp sunt p = 1, q = n.

Când dimensiunile subprogramelor sunt aproximativ egale timpii de calcul sunt:

unde: – t0 este timpul necesar rezolvării directe a problemei (n<= ),

– f(n) este timpul consumat de procedurile Div și Comb.

Voi ilustra această tehnică prin două exemple, iar în final voi prezenta ecuațiile de recurență care descriu relațiile dintre o problemă și subproblemele sale.

Pentru început considerăm problema determinării simultane a minimului și a maximului elementelor dintr-o mulțime S cu n elemente.

O metodă evidentă este aceea a determinării paralel a celor două valori. Funcția care realizează acest lucru are un singur parametru S care este mulțimea, iar valoarea calculată este perechea (a, b) unde a este elementul maxim iar b este elementul minim.

function MAXIM1(S)

begin

max * un element oarecare din S

min * un element oarecare din S

for * orice alt element x din S do

if x > max then

max x

if x < min then

min x

MAXMIN1 (max, min)

end

Pentru a analiza complexitatea acestui algoritm este necesar să determinăm numărul de comparări dintre două elemente oarecare ale mulțimii S. Acest lucru este evident deoarece numărul tuturor operațiilor de un anumit tip, efectuate pe parcursul execuției, are același ordin de mărime cu numărul comparațiilor. Mai mult în cazul în care elementele mulțimii S sunt polinoame, vectori, șiruri de caractere sau numere foarte mari, costul comparării a două elemente este mai mare decât costul oricărei alte operații. Deci, timpul total de execuție este determinat în principal de costul comparării elementelor.

Se observă imediat că funcția MAXMIN1 efectuează în orice situație 2*n-2 comparări. O îmbunătățire imediată a algoritmului se realizează dacă se efectuează comparația x < min doar în cazul în care condiția x > max este falsă.

Deci algoritmul poate fi următorul:

funcion MAXMIN2(S)

begin

max * un element oarecare din S

min * un element oarecare din S

for * orice alt element x din S do

if x > max then

max x

else

if x < min then

min x

MAXMIN2 (max, min)

end

Cazul cel mai defavorabil apare atunci când elementele sunt în ordine descrescătoare, numărul de comparații fiind 2(n-1). Se poate arăta că numărul mediu de comparări în acest caz este 3*n/2 -1.

O altă metodă este aceea a determinării pe rând a celor două valori. Mai întâi determinăm elementul maxim, operație pentru care sunt necesare n-1 comparări între elementele mulțimii. În mod similar se poate determina minimul dintre cele n-1 elemente rămase prin intermediul a n-2 comparări, ceea ce duce la un total de 2n-3 operații de comparare pentru a determina maximul și minimul, presupunând că n>=2.

Algoritmul este următorul:

function MAXMIN3(S)

begin

max * un element oarecare din S

for *orice alt element x din S do

if x > max then

max x

min * un element oarecare din S mai puțin max

for *orice alt element x din S mai puțin max și min do

if x < min then

min x

MAXMIN3 (max, min)

end

Abordarea problemei în maniera divide_et _impera va conduce la separarea mulțimii S în două submulțimi S1 și S2, fiecare având n/2 elemente. Algoritmul va determina minimul și maximul elementelor din fiecare submulțime în mod recursiv. Elementele maxim și minim al lui S pot fi calculate din elementele corespunzătoare din mulțimile S1 și S2.

Algoritmul este exprimat într-o manieră formală mai jos:

Algoritm: Determinarea elementelor maxim și minim dintr-o mulțime

Intrare: O mulțime S cu n elemente un n este o putere a lui 2 și n >=2

Ieșire: Elementele minim și maxim ale mulțimii

Descriere: Se aplică funcția recursivă MAXMIN4 de mai jos asupra mulțimii S

Funcția are un singur argument care este o mulțime S de cardinal S =2k, k>=1, iar valoarea calculată este o pereche (a, b) unde a este elementul maxim iar b elementul minim al lui S.

function MAXMIN4(S)

begin

1 if S =2 then

2 / * S = {a, b} * /

3 MAXIM4 (max(a, b), min(a, b))

4 else

5 * separă S în S1 și S2

6 (max1, min1) MAXMIN4(S1)

7 (max2, min2) MAXMIN4(S2)

8 MAXMIN4 (max (max1, max2), min (min1, min2))

end

De notat că singurele operații de comparare sunt efectuate prin intermediul instrucțiuilor 3 și 8. Instrucțiunea 3 compară cele două elemente ale lui S iar instrucțiunea 8 compară valorile max1 cu max2 și min1 cu min2.

Fie T(n) numărul de comparații dintre elementele lui S efectuate de mulțimea MAXMIN4 pentru a determina elementul maxim și minim în cazul în care mulțimea S are n elemente. Este evident că T(2) =1. În cazul în care n >2, T(n) este numărul de operații de comparare efectuate în apelurile din liniile 6 și 7 pentru mulțimi cu n/2 elemente, plus cele două operații de la linia 8. Deci avem:

dacă n=2

dacă n>2

Funcția T(n) = 3n/2-2 este o soluție pentru relația de recurență de mai sus.

Deoarece am calculat doar numărul de operații de comparare, metoda de transmitere a parametrilor fiind neimportantă, algoritmul a fost formulat oarecum imprecis, fără a avea în vedere modul de repartizare a mulțimii S.

Dacă mulțimea S este reprezentată ca un tablou, funcția MAXMIN4 poate fi proiectată eficient dacă i se transmit ca parametri referințe la primul și la ultimul element din mulțime. Cazurile în care mulțimea are unul sau două elemente, sunt tratate separat.

Având în vedere cele de mai sus, funcția MAXMIN poate avea forma:

function MAXMIN5 (S, l, r)

begin

if l = r

then

MAXMIN5 (S(l), S(l))

else if l + 1 = r

then if S(l) < S(r)

then

MAXMIN5 (S(r), S(l))

else

MAXMIN5 (S(l),S(r))

else

k (l + r)/2

(max1, min1) MAXMIN5 (S, l, k)

(max2, min2) MAXIM5 (S, k+1, r)

MAXMIN5 (max(max1, max2), min(min1, min2))

end

Dacă comparăm numărul mediu de comparări efectuate de funcțiile MAXMIN5 și MAXMIN1 se observă că prima efectuează cu 25% mai puține comparări. Aceasta înseamnă că algoritmul MAXMIN5 este întotdeauna mai bun ca MAXMIN1 ? Deoarece algoritmul are la bază recursivitatea, înseamnă că fiind date n elemente sunt necesare [log2 n]+1 nivele de apel. Ca atare, este necesară utilizarea unei stive pentru a memora informațiile necesare apelurilor recursive. Această stivă poate fi folosită atât explicit cât și implicit prin utilizarea facilităților recursive ale limbajelor. Funcția MAXMIN1 este mai eficientă din cauza faptului că funcția MAXMIN5 operează și cu stiva.

În cazul în care comparațiile dintre elementele lui S sunt mai costisitoare decât comparațiile a două numere întregi, tehnica divide_et_impera ne conduce la un algoritm mai eficient. În cazul în care această relație nu este valabilă, tehnica divide_et_impera ne conduce la un algoritm mai puțin eficient.

Ca atare, pentru a putea face o comparație între cele două metode, este necesar ca varianta recursivă să fie transformată într-o variantă iterativă. Compararea se va face între cele două variante iterative pe mașina fizică pe care o face implementarea.

O altă metodă de rezolvare a problemei este cea de mai jos:

funcția MAXMIN6 (S, n)

begin

if * n este par

then

if S(1) < S(2)

then min S(1)

max S(2)

else min S(2)

max S(1)

i 2

else

min S(1)

max S(1)

i 1

while i <= n-2 do

if S(i+1) <S(i+2)

then

if S(i+1) < min then

min S(i+1)

if S(i+2) > max then

min S(i+2)

else

if S(i+2) < min then

min S(i+2)

if S(i+1) > max then

min S(i+1)

i i+2

MAXMIN6 (max, min)

end

Se poate arăta că sunt necesare [n2]/2 -2 comparații între elementele mulțimii S. Deci metoda este optimală din punct de vedere al numărului de comparații între două elemente din S.

Utilizarea metodei divide_et_impera în cazul problemei anterioare a condus la reducerea numărului de comparații cu un factor constant.

CAP. III. APLICAȚII LA METODA BACKTRACKING

III.1. PROBLEMA COLORĂRII HĂRȚILOR CU R CULORI

Fiind dată o hartă să se coloreze țările cu r culori astfel încât fiecare țară să fie colorată cu o singură culoare și să nu existe două țări vecine colorate cu aceeași culoare.

Rezolvare: Aplicăm metoda backtracking, considerând soluția un vector c=(c1,c2,…,cn) unde n este numărul de țări iar ci este culoarea cu care este colorată țara i, deci ci {1,2, … r}.

Problema colorării hărților este celebră prin faptul că nu se putea demonstra (cu toate că programele dădeau soluții) că se poate colora orice hartă cu numai patru culori. Recent s-a demonstrat acest lucru.

Programul pseudocod următor, descrie algoritmul de generare a tuturor posibilităților de colorare a hărții utilizând metoda bactraking.

Date de intrare :

N – numarul de tari

R – numarul de culori

H[10,10] – Matricea de adiacenta, a cărei elemente

h[i,j]=1 daca tara i este vecina cu tara j

h[i,j]=0 in caz contrar;

ch – variabilă de tip caracter utilizată în interfața cu utilizatorul pentru a se stabili modul de introducere a datelor (tastatură sau fișier);

s – șir de caractere utilizat pentru introducerea numelui de fișier;

f – var. de tip text.

Date de ieșire :

C[10] – Vectorul in care se generează culorile țărilor

(C[I] – culoarea țării I;

nr_sol – variabilă utilizată pentru numărarea solu-țiilor problemei.

Programul conține două proceduri de introducere a datelor : una pentru citirea datelor de la tastatură și una pentru citirea datelor din fișier.

procedure citire_de_la_tastatură;

var i,j,k:integer

begin

write 'Intr. nr de tari (<=10):'

read n

write 'Intr. nr de culori (<=',n,'):'

read r

for i=1, n do

for j=1, n do

h[i,j]0

for i=1, n-1 do

for j=i+1, n do

write 'Tara i este vecina cu tara j?(1/0)'

repeat

read k

until k{0,1}

h[i,j]k; h[j,i]k

end

Procedura citire_de_la_tastatură citește întâi numărul de țări și numărul de culori și inițializează matricea cu zerouri. Matricea este simetrică în raport cu diagonala principală deoarece relația de vecinătate este simetrică. Bazându-ne pe această observație, am citit numai valorile situate deasupra diagonalei principale, și le-am copiat în pozițiile simetrice.

procedure citire_din_fișier

var s:string

i,j:integer

begin

write ‘Introduceti numele fișierului’

read s

assign(f,s)

reset (f)

read (f,n)

read (f,r)

for i=1, n do

for j=1, n do

read (f,h[i,j])

close f

end

Procedura citire_din_fișier citește întâi de la tastatură numele fișierului de intrare, îl deschide în citire și apoi citește din fișier numărul de țări, numărul de culori și valorile elementelor întregii matrice.

procedure afisare

var i:integer;

begin

nr_solnr_sol+1

write 'Solutia ',nr_sol,' : '

write ' Tara Culoarea'

for i=1, n do

write i,’ ‘,c[i]

end

Procedura afișare incrementează variabila nr_sol și afișează o soluție de colorare prin perechi de forma I, C[I] – cu semnificația țara I se colorează în culoarea C[I] , i{1, 2, …, n}.

function posibil(k)

var i:integer

begin

posibil 1

for i=1,k-1 do

if (c[k]=c[i])(h[i,k]=1) then

posibil0

exit

end

Funcția posibil verifică dacă sunt îndeplinite condițiile de continuitate pentru poziția curentă k. Se presupun inițial îndeplinite aceste condiții și se verifică dacă există o pereche de țări de forma (i, k), i{1, 2, …, k-1} vecine și colorate identic. Dacă există o astfel de pereche se iese forțat din corpul funcției, returnându-se valoarea 0 (fals), iar dacă nu există nici o astfel de pereche funcția va returna valoarea cu care a fost inițializată 1 (adevărat).

procedure colorare;

var k:integer;

begin

k1; c[k]0

while (k>0) do

while c[k]< r do

c[k] c[k]+1

if posibil(k) then if k=n then afisare

else inc(k);

c[k]0;

dec(k)

end

Procedura colorare generează utilizând metoda backtracking toate posibilitățile de colorare a hărții. Se pornește cu colorarea primei țări (k1), inițializându-se c[k] cu valoarea minimă –1. Cât timp k>0 și pentru țara k mai există culori netestate, se încearcă asocierea culorii următoare țării curente. Dacă aceasta poate fi colorată astfel, apar două situații :

s-au colorat toate țările, caz în care se afișează soluția obținută

mai sunt țări de colorat, caz în care se încearcă colorarea următoarei țări

Când pentru o țară K s-au încercat toate posibilitățile de colorare se revine încercându-se colorarea țării K-1 cu o nouă culoare.

{programul principal}

begin

write 'Introd. un set de date noi ? (D/N)'

read ch

if ch {'D','d'}

then

write ‘Introd. F pentru citire din fisier’

write ‘sau T pentru citire de la tastatură’

read ch

if ch {'T','t'} then citire

else citire_fis

nr_sol 0

colorare

if nr_sol=0 then write ‘Problema nu are solutii.'

end.

Programul principal oferă posibilitatea alegerii modului de introducere a datelor (din fișier sau de la tastatură). În plus, implementarea Turbo Pascal a algoritmului oferă posibilitatea rulării pe un set de date definit constant, astfel :

const n:byte=10;

cul:byte=5;

h:array[1..10,1..10] of byte =

((0,1,1,0,1,0,0,1,0,0),

(1,0,1,0,1,1,0,1,0,0),

(1,1,0,0,1,0,1,1,0,1),

(0,0,0,0,1,0,1,1,0,1),

(1,1,1,1,0,0,0,0,0,0),

(0,1,0,0,0,0,1,1,1,0),

(0,0,1,1,0,1,0,0,1,1),

(1,1,1,1,0,1,0,0,0,0),

(0,0,0,0,0,1,1,0,0,1),

(0,0,1,1,0,0,1,0,1,0));

Am numărat soluțiile (numărul posibilităților de colorare) în variabila nr_sol și dacă valoarea acesteia a rămas 0 după apelul procedurii colorare, am afișat un mesaj corespunzător.

Implementarea algoritmului comportă câteva inconveniente, cum ar fi:

Matricea H are dimensiuni relativ mici (N10). Am utilizat dimensiuni mici ținând cont de faptul că timpul de execuție în cazul utilizării metodei backtracking crește exponențial și în plus, era mai greu de realizat exemplul constant prezentat mai sus. Deoarece în cazul introducerii unor valori mai mari pentru N apăreau diverse erori de execuție, am modificat procedura de citire de la tastatură, repetându-se citirea valorii până când îndeplinește condițiile cerute. Acest lucru nu poate fi rezolvat la fel în cazul citirii din fișier.

Dacă datele se introduc din fișier, prima problemă care poate apare este să nu existe fișierul, sau să fie calea greșită. În programul Pascal am utilizat directivele {$I+}, {$I-} și funcția ioresult, pentru validarea numelui fișierului de intrare. În cazul citirii din fișier nu poate fi repetată citirea lui N până când sunt îndeplinite condițiile cerute, deci procedura presupune că datele din fișier sunt corecte (prima este valoarea lui N, apoi valoarea lui R și în continuare N2 valori {0,1}. Dacă introducerea unei valori pentru n>10 în cazul citirii de la tastatură conducea la întreruperea programului cu eroare de execuție, în cazul citirii fișierului cu setul de date de mai jos se afișează soluții incorecte (mai mult de 12 culori) și prima este cea cu numărul 256 ?!

13

12

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

Am renunțat la introducerea triunghiului de deasupra diagonalei principale, ca în cazul citirii de la tastatură. Dacă fișierul conține un singur 1 în loc de 0, sau 0 în loc de 1, o mare parte dintre soluțiile afișate sunt incorecte. Pentru că vecinătatea a două țari este o relație simetrică, am introdus o funcție logică ce verifică simetria matricei citite din fișier față de diagonala principală. Când această condiție nu este îndeplinită, programul se oprește cu mesaj de eroare corespunzător.

Întrucât un număr de culori mai mare decât numărul țărilor nu se poate regăsi într-o singură soluție, am solicitat ca valoarea R să fie N.

Programul poate fi îmbunătățit în continuare, mai ales în direcția determinării cazurilor în care problema nu are soluții fără a apela procedura de colorare, ci utilizând câteva rezultate din teoria grafurilor. De asemenea, în cazul în care graful asociat poate fi descompus în componente conexe, metoda backtracking poate fi combinată cu metoda divide et impera – rezolvarea problemei revine la a colora fiecare componentă conexă prin backtracking, prin divide et impera realizându-se descompunerea în componente conexe, apelul colorării fiecărei componente și combinarea soluțiilor colorării componentelor în soluția de colorare a hărții.

III.2. PARTIȚIILE UNEI MULȚIMI

Fie A o mulțime finită. O partiție a lui A este o descompunere a sa de forma:

unde cele k submulțimi A1, A2, …, Ak numite clase sunt nevide și disjuncte două câte două.

Determinați toate partițiile mulțimii A cu n elemente.

Rezolvare:

Folosim metoda backtracking în varianta recursivă. Utilizăm pentru reprezentarea partițiilor un vector caracteristic V cu n componente. Elementul vi va avea ca valoare numărul de ordine al clasei din care face parte elementul i.

De exemplu: dacă v = (1, 3, 1, 4, 2, 2) atunci partiția va fi:

A = {a1, a3} {a5, a6} {a2} {a4}

observând că în clase elementele sunt ordonate crescător după indice.

Date de intrare :

N – numărul de elemente al mulțimii

A[100] – vectorul ce va conține elementele mulțimii

Date de ieșire :

V[100] – vectorul caracteristic

Algoritmul:

procedure Scriere

var nec,i,j: integer

c,s: string

begin

c 'A= '

for i=1,n do

nec 0

for j=1,n do

if v[j]=i then nec nec+1

if nec>0 then

c c+'{ '

for j=1,n do

if v[j]=i then Str (a[j],s)

c c+s+', '

Delete (c,Length (c)-1,2)

c c+' } U '

Delete (c,Length (c)-2,3)

Write c

end;

Procedura scriere determină pentru fiecare clasă de ordin i (i{1,…,n}dacă este nevidă și în caz afirmativ adaugă în șirul de caractere c elementele clasei respective separate prin virgule și cuprinse între acolade.

procedure Partitii(k,nc:integer)

var i:integer

begin

if k=n+1 then Scriere

else

for i=1,nc do

v[k]i

Partitii(k+1,nc+1) (*)

v[k]c+1

Partitii(k+1,nc+1)

end

Procedura Partiții este o procedură recursivă având parametrii k (cu semnificația că trebuie stabilit numărul clasei în care se va afla ak) și nc (desemnând numărul claselor partiției curente a mulțimii a1, a2, … ,ak-1 ).

Dacă valoarea lui k este n+1, înseamnă că vectorul V este construit în întregime și ca urmare va fi apelată procedura de scriere.

Dacă valoarea lui k nu depășește pe n atunci:

– pentru i = 1, 2, … ,k-1 plasăm pe ak în clasa lui ai (adică atribuim lui vk valoarea lui vi și apelăm Partiții (k+1, nc));

– plasăm pe ak într-o nouă clasă (deci în clasa nc+1, ceea ce revine la a atribui lui vk valoarea nc+1) și apelăm Partiții (k+1, nc+1).

{programul principal}

Begin

Write 'n='

Read n

for i=1,n do

write 'a[',i,']='

Read a[i]

partitii(1,0)

End.

Programul principal citește numărul de elemente al mulțimii și elementele mulțimii, apoi apelează procedura de generare partiții.

Depanând programul Pascal, observăm că vectorul V nu conține toate valorile {1,2,…,nc} ceea ce înseamnă că se generează clase vide – de aici procedura îngreunată de scriere.

Înlocuind apelul (*) cu

Partitii(k+1,nc)

clasele de ordin 1, 2, … nc generate vor fi toate nevide, astfel procedura de afișare cu parametrul nc se simplifică mult:

procedure Scriere(nc:byte)

var i,j: integer

c: string

begin

c 'A= '

for i=1,nc do

cc+'{ '

for j=1,n do

if v[j]=i then Str (a[j],s)

c:=c+s+', '

Delete (c,Length (c)-1,2)

cc+' } U '

Delete (c,Length (c)-2,3)

Write c

end

Pentru e evita introducerea de valori negative pentru n, se repetă citirea până când valoarea citită este pozitivă.

III. 3. PROBLEMA DESCOMPUNERII UNUI NUMĂR NATURAL (PARTIȚIILE UNUI NUMĂR NATURAL)

Orice număr natural se poate scrie ca o sumă de termeni, fiecare termen fiind un număr natural diferi de zero.

De exemplu: numărul patru se poate scrie:

4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci în patru moduri

Dacă notăm cu n numărul pe care vrem să-l scriem ca sumă de numere naturale și cu T(n) numărul de modalități în care se poate scrie n, atunci pentru n = 4 avem T(n) = 4.

Să se realizeze un program care să calculeze și să afișeze pentru un n dat (n<=50) valoarea T(n).

Rezolvare:

O variantă de rezolvare a problemei este prin metoda backtracking, soluțiile fiind reprezentate sub forma unui vector (xk), k=1,…,m unde m este numărul termenilor din descompunere. Termenii rezultați din descompunere sunt memorați în elementele vectorului. Algoritmul are următoarele particularități:

– vectorii soluție au un număr variabil de componente (dar cel mult n), o condiție de revenire fiind ca suma elementelor să fie n;

– prima valoare pe care poate s-o ia un element trebuie să fie cel puțin egală cu a elementului anterior, pentru a se evita generarea unei soluții de două ori.

Date de intrare :

N – numărul ce urmează a fi descompus

Date de ieșire :

X[100] – vectorul ce va conține elementele mulțimii

Nr_sol – numărul de soluții obținute

Algoritmul :

function sum(k)

var j,s:integer

begin

s0

for j=1,k do

ss+x[j]

sums

end

Funcția sum calculează suma elementelor de pe pozițiile 1,2,…, k ale vectorului X.

procedure afisare(k)

var i,j:integer

begin

nr_solnr_sol+1

write n,'='

for i=1,k-1 do

write x[i],'+'

write x[k]

end

Procedura afișare are parametru deoarece numărul de elemente din descompuneri este diferit.

procedure generare

var k,s:integer

begin

k1

x[k]0

while k>0 do

while x[k]<n-1 do

x[k]x[k]+1

ssum(k)

if s=n then afisare(k)

kk-1

else if s>n then kk-1

else kk+1

x[k]x[k-1]-1

kk-1

end

Procedura generare este o procedură iterativă ce depune în vectorul X valori mai mici decât n, în ordine crescătoare. Când suma acestora este egală cu N se afișează soluția și se revine cu un pas. Dacă suma este mai mare decât N se revine de asemenea cu un pas. Când suma este mai mică decât N se trece la completarea unei noi poziții.

{programul principal}

begin

write 'Introduceti numarul N :'

readln n

generare

writeln 'Numarul de solutii : ',nr_sol

end.

Programul principal citește numărul ce se va descompune și apelează procedura de generare a partițiilor. La sfârșit afișează numărul de soluții obținute.

Procedura generare poate fi modificată astfel încât decrementarea să se realizeze când suma nu este mai mică decât N :

procedure generare1

var k,s:integer

begin

k1

x[k]0

while k>0 do

while x[k]<n-1 do

x[k]x[k]+1

ssum(k)

if s<n then kk+1

x[k]x[k-1]-1

else if s=n then afisare(k)

kk-1

kk-1

end

Timpul de execuție poate fi redus considerabil dacă, în loc să se apeleze de fiecare dată funcția sum, se reține în fiecare moment, într-o variabilă, suma elementelor depuse în vector până la poziția k. Procedura generare devine :

procedure generare2

var k,suma:integer

begin

k1; x[k]0

while k>0 do

while x[k]<n-suma do

x[k]x[k]+1

if suma+x[k]<n then suma:=suma+x[k]

kk+1

x[k]:=x[k-1]-1

else if suma+x[k]=n then afisare(k);

kk-1

sumasuma-x[k]

end

Deși valorile care intervin sunt numere naturale, este necesar să se lucreze în program cu un tip întreg cu semn pentru ca expresia x[k] < n – suma să se evalueze corect (diferența n – suma să fie memorată în cod complementar).

Programul rezervă un vector cu 10000 de componente și cum cea mai lungă descompunere a lui N are N elemente, rezultă că spațiul de memorie rezervat soluțiilor este suficient pentru N 10000. Este greu să interpretez corect ce se întâmplă în situația nerespectării condiției de mai sus. La o rulare pentru N=11000, după mai multe ecrane cu 1+1+…+1, apar și alte valori la final (+6+6).

Ar fi necesară o dezvoltare a procedurii de afișare în limbajul Turbo Pascal, deoarece pentru valori N>40, sunt necesare mai multe rânduri pentru o soluție. De asemenea ar fi necesară paginarea afișării, dar aceasta ar conduce la creșterea timpului de execuție, deja mare pentru valori mari ale lui N.

CAP. IV. APLICAȚII LA METODA

“DIVIDE ET IMPERA”

IV.1. SORTAREA PRIN INTERCLASARE

A ELEMENTELOR UNUI VECTOR

Se consideră un vector: A = (a1, … , an). Se cere să se sorteze acest vector utilizând interclasarea.

Vectorul se descompune în doi vectori ce urmează a fi sortați, fiecare din cei doi vectori se descompune în doi vectori, etc. Descompunerea unui vector în alți doi vectori ce urmează a fi sortați, are loc până când avem de sortat vectori cu maxim două componente.

Procedura Sort sortează crescător un vector de maxim două elemente și corespunde procedurii Sol din schema generală.

Procedura DivImp implementează strategia generală a metodei.

Procedura Div este realizată doar prin instrucțiunea m = (p + q)/2

Date de intrare :

N – numărul de elemente ale vectorului

A[100] – vectorul ce va fi sortat

Date de ieșire :

A[100] – vectorul sortat

Procedure Sort(p,q,A)

Var aux: integer

begin

if ap>aq then auxap, apaq, aqaux

end

Procedura sort se apelează pentru vectori de maxim două elemente, compară elementele și le ordonează. Dacă vectorul are un singur element (p=q) expresia din instrucțiunea if are valoarea false și nu se schimbă nimic.

Procedure InterC(p,q,m,A)

var i,j,k:integer

begin

ip

j m+1

k1

while (i m)and(j q)do

if aiaj then bkai

ii+1

kk+1

else bkaj

jj+1

kk+1

if i m then

for j=i,m do

bkaj

kk+1

else

for i=j,q do

bkai

kk+1

k1

for i=p,q do

aibk kk+1

end

Procedura InterC interclasează secvențele ordonate ap,…,am, respectiv am+1,…,aq, utilizând un vector B. Cât timp în ambele secvențe mai sunt elemente se copie în vectorul B cel mai mic dintre elementele ai, aj și se înaintează în secvența corespunzătoare. Când una dintre secvențe s-a terminat, se copie elementele rămase din cealaltă secvență în vectorul B. În final, elementele vectorului B se copie în vectorul A în pozițiile p,…,q.

Procedure DivImp(p,q,A)

var r,m:integer

begin

if q-p1 then Sort (p, q, A)

else m[(p+q)/2]

DivImp(p,m,A)

DivImp(m+1,q,A)

InterC(p,q,m,A)

end

Procedura DivImp apelează procedura Sort când secvența are cel mult două elemente, iar în caz contrar determină mijlocul secvenței, autoapelându-se pentru fiecare din cele două jumătăți și apelează procedura de interclasare pentru secvențele ordonate obținute.

{programul principal}

begin

read n

for i=1,n do

read ai

DivImp(1,n,A)

for i=1, n do

write ai

end

Programul principal citește elementele vectorului A, apelează procedura DivImp pentru întregul vector și afișează apoi vectorul ordonat obținut.

Procedura de interclasare poate fi modificată astfel încât să nu se mai utilizeze un vector nou. Pentru aceasta folosim faptul că secvențele ce se interclasează sunt consecutive, rămânând să mutăm spre stânga cu câte o poziție fiecare element din cea de-a doua secvență până când ajunge la locul său. Procedura devine :

Procedure InterC2(p,q,m,A)

var i,j,k:integer

begin

jm+1

while (j q)and(aj aj-1)do

kaj

ij-1

while (i > p)and(k ai) do

ai+1ai

ii-1

a[i]k

jj+1

end

IV. 2. PROBLEMA PLIERII

Se consideră un vector de lungime n. Definim plierea vectorului prin suprapunerea unei jumătăți numită donatoare peste cealaltă jumătate numită receptoare cu precizarea că dacă numărul de elemente este impar, elementul din mijloc este eliminat. În acest mod se ajunge la un subșir ale cărui elemente au numerotarea corespunzătoare jumătății receptoare.

Exemplu: Vectorul (1, 2, 3, 4, 5) se poate plia în două moduri (1, 2) sau (4, 5) elementul 3 fiind eliminat conform ipotezei. Plierea se poate aplica în continuare în mod repetat până când se ajunge la un subșir de lungime 1, numit element final.

1) Fiind dat i{1, 2, … ,n} să se determine dacă elementul i poate fi element final ca rezultat al unor plieri succesive.

2) Să se precizeze toate elementele finale posibile.

3) Fiind dat un element i final, să se figureze pe ecran o succesiune de plieri prin care se ajunge la el.

4) Considerăm că valorile vectorului sunt numere întregi citite de la tastatură. Prin pliere din dublu valorii fiecărui element al jumătății receptoare se scade valoarea elementului corespunzător jumătății donatoare.

Exemplu: (6, 4, 7, -4, 5) se pot obține prin pliere (7, 12) sau (-14, 6).

Să se verifice dacă există un element final cu valoarea 0 după ultima pliere și în caz afirmativ să se determine succesiunea de plieri corespunzătoare.

Rezolvare :

Date de intrare :

N – numărul de elemente

V – poziția ce se dorește a fi obținută printr-o succesiune de plieri

F[100] – vector cu elemente logice

M[100] – vector de șiruri de caractere

Semnificația elementelor celor doi vectori va fi precizată în cele ce urmează.

Punctele 1) -2) Pentru a arăta dacă elementul i poate element final putem determina mai întâi toate elementele finale posibile (punctul 2) și apoi să verificăm dacă elementul i se găsește printre ele. Aplicăm pentru aceasta metoda divide_et_impera construind vectorul boolean f, unde:

Să observăm că avem prin simetrie f(n+1-i) = f(i), deci este suficient să determinăm elementele finale numai dintr-o jumătate. Programul este dat în procedurile următoare:

procedure punct1

var r:string

v:integer

procedure ElFinale(i,j)

var k:integer

begin

if i = j then f[i]true

else if (i +j)/2=(i +j)div2

then f[(i +j)div 2]false

ElFinale(i,i+j-1-(i + j)div 2)

for k=(i + j)div2+1,j do

f[k]f[i+j-k]

end

begin

write ‘introduceti v =

read v

ElFinale (1, n)

if f[v] then r’ poate fi element final ‘

else r’ nu poate fi element final ‘

write v,r

end

Procedura punct2 afișează pozițiile ce se pot obține prin pliere, ca fiind cele pentru care f[i] are valoarea true.

procedure punct2

var i:integer

begin

write ‘elementele finale sunt:’

for i1,n do

if f[i] then write i

end

Punctul 3) Pentru acest punct vom folosi o procedură asemănătoare cu procedura ElFinale în care vom construi un vector m astfel:

m[i] = ’o succesiune de 0 și 1’, după cum mutările prin care se obține i sunt :

0 – dacă se pliază dreapta peste stânga

1 – dacă se pliază stânga peste dreapta

m[i]=2 dacă I nu este element final.

De exemplu dacă n = 5 atunci m(4) = 10 și m(3) =2.

Procedura Punct3 are ca parametru v un element final deoarece va fi folosită în rezolvarea punctului 4) al problemei și ea folosește vectorul boolean f creat anterior.

procedure punct3

var r:string

v:integer

procedure Mutari(i,j)

var k:integer

begin

if i = j then m[i]’’

else if (i+j)/2=(i +j)div2

then m[(i +j)div 2]’2’

Mutari(i,i+j-1-(i + j)div 2)

for k=i,i+j-1-(i + j)div2+1,j do

m[k]’1’+m[k]

end

begin

Mutări(1,n)

i1

jn

if not f[v]

then write ‘ elementul ‘,v,’ nu este final’

else

for k=1,length(m[v]) do

if Copy(m[v],k,1)=1

then

j:=i+j-1-(i+j) div2;

write ‘ se pliază dreapta peste stânga ’

write i,’-’,j)

else

i(i+j)div2+1

write ‘ se pliază stânga peste dreapta ‘

write i,’-’,j)

end

Punctul 4) Pentru acest punct vom folosi o procedură Pliere construită cu ajutorul aceleași metode care va utiliza vectorul a pentru a reține valorile elementelor după pliere și va folosi punctul 3) pentru a afișa șirul plierilor.

procedure Punct4

var i,j:integer

v,a:integer

procedure Pliere(i,j)

var k:integer

begin

if ij

then

for k=i,j do a[k]2*v[k]-v[i+j-k]

for k=i,j do v[k]a[k]

Pliere(i,i+j-1-(i+j)div2)

Pliere((i+j)div2+1, j)

end

begin

for i=1,n do

write ‘introduceți v[’,I,’]=’

read v[i]

Pliere(1,n)

s0

for i1,n do

if (a[i]=0)and f[i]

then

s1

write ‘elementul ‘,i,’ va fi zero după pliere’

Punct3(i)

if s=0 then write ‘nu există elemente finale nule’

end

Programul principal care rezolvă toate punctele problemei, citește numărul de elemente al vectorului și apelează pe rând procedurile Punc1, Punct2, Punct3 și Punct4.

begin

write ‘ introduceți n= ’

read n

write ‘ rezolvarea punctului 1 ’

Punct1

Write ‘ rezolvarea punctului 2 ‘

Punct2

write ‘ rezolvarea punctului 3 ‘

write ‘ introduceți v element final: ‘

read v

Punct3(v)

write ‘ rezolvarea punctului 4 ’

Punct4

end

Problema poate fi generalizată un tablou n-dimensional cu plieri în cele n dimensiuni.

CONCLUZII FINALE

" Se știe că o idee începe prin a fi un paradox, continuă pri a fi o banalitate și sfârșește prin a fi o prejudecată"

Gr. C. Moisil

Această lucrare: Contribuții privind metodele de programare, urmărește prezentarea detaliată a conceptelor de bază ale limbajului de programare Turbo Pascal ,însoțind explicarea construcțiilor specifice metodelor de programare, cu un număr de exemple. Lucrarea cuprinde, pe lângă toate aspectele uzual abordate în prezentarea celor două metode de programare: metoda backtracking și metoda divide et impera, și unele chestiuni de dificultate sporită , oferind celor interesați puncte de pornire în aprofundarea tehnicilor evoluate de programare.

Pentru fixarea cunoștințelor și pentru crearea unor deprinderi de organizare riguroasă a activității de programare, s-a inclus un număr mare de comentarii, asupra teoriei, dar mai ales asupra celor 5 programe propuse pentru a înțelege mai bine metodele de programare.

Documentația programului este formată din descrierea funcției programului, structura datelor de intrare și ieșire, schemele de sistem și de program, textul programului sursă, precum și comenzile pentru executarea acestuia.

Metodele de programare sunt ansambluri coerente de concepte, tehnici, reguli și procedee folosite în mod organizat și sistematic în activitatea de programare, în conformitate cu obiectivele globale ale activității de programare. Consultarea și înțelegerea schemei logice a programului este dificilă în cadrul programelor complexe, de aceea am utilizat pseudocodul ce utilizează propoziții simple care descriu operatiile de prelucrare ce se vor codifica în această formă, sau complexe care exprimă operații ce sunt detaliate în propoziții simple la nivelul unor module elementare și de aici direct în programul sursă. Fazele procesului de concepere și elaborare a programelor prin metoda programării structurate coincid, în cea mai mare parte, cu cele din programarea modulară, cu asigurarea principiului descompunerii consecvent descendente în pași succesivi. Programarea structurată prezintă avantaje similare cu programarea modulară, dar pentru a obține efectele maxime în rezolvarea problemelor, se îmbină cele două metode de programare, astfel încât programele să conțină module deduse de sus în jos în conformitate cu principiile programării modulare, iar în cadrul acestora, să guverneze integral structurile standard de control specifice programării structurate.

Limbajul Turbo Pascal utilizat în această lucrare , oferă pe lângă rutinele standard, o multitudine de proceduri și funcții care mi-au perrmis realizarea unor programe performante și ușor de folosit.

Lucrarea poate fi folosită și de către elevii claselor cu alt profil decât informatică, fiind de asemenea utilă și studenților din primul an de facultate, ca și tuturor celor ce doresc să devină nu doar simpli utilizatori de programe, ci și creatori ai acestora.

"… calculatoarele nu merg singure. Ca să meargă trebuie să ai oameni pricepuți ca să le mâie. Ca să ai oameni pricepuți trebuie să-I înveți; ce? "

Gr. C. Moisil

BIBLIOGRAFIE

1. T. IONESCU, GH. MUSCĂ, FL. MUNTEANU – Programarea calculatoarelor – Ed. did si ped. Buc 1994

2. TUDOR SORIN – Algoritmi și limbaje de programare – Buc 1995

3. NICULESCU, STELIAN ȘI EFTIMESCU – Algoritmi și limbaje de programare – Ed. did și ped. 1995

4. DANIELA SÎRBU – Algoritmi și limbaje de programare – Ed. did. și ped. Buc 1998

5. TUDOR SORIN – Tehnici de programare – Teora 1995

6. IORGA V:, FĂTU I: – programarea în limbajul Pascal – Litografia I:P:B:, 1987

7. CRISTEA V., ATHANASIU L.; KALISZ E. PANOIU A. – Turbo Pascal 60 – Editura Teora, București 1992