Batog, Culegere de probleme de informatica [RO]

Culegere de probleme de informaticã - contine rezolvari si implementarile lor in limbajul Pascal -

Bogdan Batog Cãtãlin Drulã

Aceasta este versiunea electronica a cartii "Tehnici de programare - Laborator clasa a X-a". Cartea contine probleme de informatica si solutiile lor impreuna cu implementari in limbajul Pascal.

Se adreseaza tuturor elevilor, dar si celor cu un interes mai special pentru informatica. Astfel, sunt tratate cateva subiecte mai avansate si sunt prezentate si probleme intalnite la diferite concursuri.

Cuprins

Prefaþã

Capitolul 1 Backtracking

Capitolul 2Recursivitate

Capitolul 3Backtracking recursiv

Capitolul 4Analiza timpului de calcul necesar algoritmilor

Capitolul 5Divide et Impera

Capitolul 6Structuri de date

Capitolul 7Tehnica Greedy

Capitolul 8Programare dinamicã

Capitolul 9Branch and Bound

Capitolul 10Teoria grafurilor

Bibliografie

Culegere de probleme de informaticã

Bogdan Batog Cãtãlin Drulã

Prefata la varianta electronica

O scurta istorie a acestei carti ar fi cam asa. In vara anului 1998, domnul profesor Tudor Sorin ne-a propus sa scriem un “manual de laborator” pentru cursul de informatica din clasa a X-a. La vremea respectiva, eram amandoi in vacanta de vara dinaintea clasei a XII-a. Pentru ca ni s-a parut un proiect accesibil, si probabil pentru ca eram dornici sa ne afirmam, ne-am apucat cu entuziasm sa “scriem”.

Scopul acestei carti a fost initial sa fie o culegere de probleme, care sa-i ajute atat pe elevi cat si pe profesori, ca sursa de exercitii suplimentare. Acesta a si devenit in mare continutul cartii. Contine probleme structurate in functie de tehnica de programare folosita in solutiile lor. Fiecare problema este urmata de solutie si de implementarea acesteia in limbajul Pascal. Ca o parenteza, limbajul acesta ne este drag amandorura, pentru ca ne aduce aminte cu un pic de nostalgie de olimpiadele de informatica la care am luat parte in liceu. In plus, il consideram si un limbaj foarte potrivit pentru invatarea programarii si a algoritmicii. La acest proiect initial al cartii, noi am adaugat cateva subiecte “avansate”, pentru elevii care au un interes mai special in algoritmica sau pentru cei care se pregatesc pentru olimpiadele de informatica.

Culegerea a aparut in doua editii tiparite care intre timp s-au epuizat. Recent, ne-am hotarat sa continuam experimentul inceput de domnul profesor Tudor Sorin, si ii spun experiment, pentru ca dumnealui a dat dovada de multa deschidere incredintand acest proiect unor liceeni. Asadar, ne-am hotarat sa facem publica pe Internet aceasta carte cu speranta ca va fi de ajutor elevilor pasionati de algoritmi si programare. De aceea, va rugam sa ne trimteti prin e-mail comentariile voastre.

3 martie 2002

Bogdan Batog, [email protected] Catalin Drula, [email protected]

Multumiri

Multumirile noastre merg in primul rand catre domnul profesor Tudor Sorin pentru ca ne-a dat sansa sa scriem aceasta carte. Si as adauga eu (Catalin): pentru ca a scris cartile dupa care am invatat primul limbaj de programare si primii algoritmi.

mailto:[email protected]

mailto:[email protected]

Celelalte multumiri sunt cele din prefata originala a manualului pe care le reproducem aici: domnilor profesori Cristian Francu si Catalin Francu (pentru pregatirea efectuata in particular), Mihai Boicu, Dan Grigoriu, Daniela Oprescu si Rodica Pintea.

Capitolul 1

Backtracking

Problema 1

Enunþ. Avem la dispoziþie 6 culori: alb, galben, roºu, verde, albastru ºi negru. Sã se precizeze toate drapelele tricolore care se pot proiecta, ºtiind cã trebuie respectate urmãtoarele reguli:

● orice drapel are culoarea din mijloc galben sau verde;

● cele trei culori de pe drapel sunt distincte.

Exemple: "alb galben roºu", "roºu verde galben"

Rezolvare. Folosim o stivã cu 3 nivele, reprezentând cele trei culori de pe drapel ºi codificãm culorile prin numere:

1 – alb2 – galben3 – roºu 4 – verde5 – albastru6 - negru

Folosim un vector auxiliar fol de tip boolean:

fol[i]= TRUE, dacã culoarea i a fost folositã în drapel deja;

FALSE, dacã nu a fost folositã.

Condiþiile care trebuie îndeplinite pentru aºezarea unei anumite culori c pe un nivel al stivei sunt:

● fol[c]=FALSE, adicã sã nu fi folosit deja culoarea respectivã în drapel;

● dacã nivelul stivei este 2 (adicã culoarea din mijloc), atunci culoarea

trebuie sã fie 2 sau 4 (galben sau verde).

program Drapel;

const Culoare:array [1..6] of string[10]=('alb','galben', 'rosu','verde', 'albastru','negru');

var ST :array [1..3] of integer; Fol :array [1..6] of boolean; k, i :integer;

procedure Printsol;var i:integer;begin for i:=1 to 3 do write(Culoare[ST[i]],' '); writelnend;

function Valid:boolean;begin if Fol[ST[k]] then Valid:=false else if k<>2 then Valid:=true else Valid:=(ST[k] in [2,4])end;

begin for i:=1 to 6 do Fol[i]:=false; k:=1; ST[k]:=0; while k>0 do begin repeat ST[k]:=ST[k]+1 until (ST[k]>6) or Valid; if ST[k]<=6 then if k=3 then Printsol else begin Fol[ST[k]]:=true; k:=k+1; ST[k]:=0 end else begin

k:=k-1; if k>0 then Fol[ST[k]]:=false end endend.

Problema 2

Enunþ. Sã se descompunã un numãr natural N, în toate modurile posibile, ca sumã de P numere naturale (P≤N).

Rezolvare. Folosim o stivã cu P nivele, unde fiecare nivel ia valoarea unui termen din sumã. Variabila S reþine suma primelor k nivele pentru a putea testa validitatea elementului aºezat pe poziþia curentã fãrã a mai face o parcurgere suplimentarã a stivei. Condiþia de validitate devine: S+ST[k]≤N.

Pentru a evita afiºarea descompunerilor identice, cu ordinea termenilor schimbatã, forþãm ordinea crescãtoare (nu strict crescãtoare!) a termenilor din sumã, prin iniþializarea unui nivel din stivã cu valoarea nivelului anterior.

program Descompuneri;

var n, p, k, S, i :integer; ST :array [0..1000] of integer;

Procedure Printsol;var i:integer;begin for i:=1 to p do write(ST[i],' '); writelnend;

begin write('N= '); readln(n); write('P= '); readln(p); S:=0; k:=1; fillchar(ST,sizeof(ST),0); while k>0 do begin ST[k]:=ST[k]+1;

if S+ST[k]<=N then if (k=p) and (S+ST[k]=N) then Printsol else begin S:=S+ST[k]; k:=k+1; ST[k]:=ST[k-1]-1 end else begin k:=k-1; S:=S-ST[k] end endend.

Problema 3

Enunþ. Dintr-un grup de N persoane, dintre care P femei, trebuie formatã o delegaþie de C persoane, dintre care L femei. Sã se precizeze toate delegaþiile care se pot forma.

Rezolvare. Vom nota femeile cu numerele de la 1 la P, ºi bãrbaþii de la P+1 la N. Pentru rezolvarea problemei folosim o stivã cu C nivele, unde nivelele 1..L conþin indicii femeilor din delegaþia curentã, ºi nivelele L+1..C indicii bãrbaþilor.

st[i] poate lua valori între st[i-1] ºi MAX, unde:

MAX=p, pentru i<=l;

MAX=n, pentru i>l.

st[l] poate lua valori între p ºi n.

Motivul pentru care st[i] se iniþializeazã cu st[i-1] este evitarea duplicãrii delegaþiilor, prin forþarea ordinii strict crescãtoare în fiecare delegaþie.

Limita pânã la care se pot majora elementele de pe un nivel este P pentru nivelele 1..L (femeile) ºi N pentru nivelele L+1..C. De aceea, la urcarea ºi coborârea pe nivelul L, variabila MAX devine N, respectiv P.

st[l] nu se iniþializeazã cu st[l-1], ci cu P, pentru cã este primul dintre bãrbaþi ºi bãrbaþii au indicii între P+1 ºi N.

program Delegatie;

var st :array [1..100] of integer; MAX, k, N, P, C, L :integer;

procedure Printsol;var i:integer;begin for i:=1 to C do write(st[i],' '); writelnend;

begin write('N, P, C, L: '); readln(N,P,C,L); k:=1; st[1]:=0; MAX:=P; while k>0 do begin st[k]:=st[k]+1; if st[k]<=MAX then if k=C then Printsol else begin k:=k+1; if k<>L+1 then st[k]:=st[k-1] else begin st[k]:=P; MAX:=N end end else begin k:=k-1; if k=l then MAX:=P end endend.

Problema 4

Enunþ. O persoanã are la dispoziþie un rucsac cu o capacitate de G unitãþi de greutate ºi intenþioneazã sã efectueze un transport în urma cãruia sã obþinã un câºtig. Persoanei i se pun la dispoziþie N obiecte. Pentru fiecare obiect se cunoaºte greutatea (mai micã decât capacitatea rucsacului) ºi câºtigul obþinut în urma transportului sãu.

Ce obiecte trebuie sã aleagã persoana pentru a-ºi maximiza câºtigul ºi care este acesta? Se va avea în vedere ºi faptul ca pentru acelaºi câºtig persoana sã transporte o greutate mai micã.

Datele de intrare se vor citi din fiºierul input.txt. Pe primele douã linii ale fiºierului sunt N ºi G, numãrul de obiecte ºi capacitatea rucsacului. Pe fiecare din urmãtoarele N linii se aflã douã numere întregi reprezentând greutatea ºi câºtigul asociat obiectului respectiv.

Rezolvare. În vectorii gr ºi c avem greutatea ºi câºtigul obþinut în urma transportãrii fiecãrui obiect. CG este câºtigul obþinut în urma transportãrii obiectelor aºezate în stivã pânã la nivelul curent ºi S, greutatea acestor obiecte.

Condiþiile care trebuie îndeplinite pentru aºezarea unui obiect i pe nivelul k al stivei sunt:

1. Pus[i]=FALSE, adicã sã nu fi aºezat deja obiectul respectiv în stivã ºi

2. S+gr[ST[k]]<=G, adicã greutatea obiectelor sã fie mai micã sau cel mult egalã cu greutatea maximã care poate fi transportatã cu rucsacul.

În variabilele Cmax, Gmax ºi STmax (câºtigul, greutatea ºi obiectele) reþinem pe timpul execuþiei programului cea mai bunã soluþie gãsitã.

Notã: Rezolvarea optimã a acestei probleme poate fi gãsitã în manualul “Tehnici de programare” de Tudor Sorin la capitolul “Programare dinamicã”.

program Rucsac;

var i,k,n,G,CG,S,Cmax,Gmax,NOb :integer; c,gr,ST,STmax :array [1..100] of integer; Pus :array [1..100] of boolean;

procedure Citire;var f :text; i :integer;begin assign(f,'input.txt'); reset(f); readln(f,N);

readln(f,G); for i:=1 to n do readln(f,gr[i],c[i]); close(f)end;

function Valid:boolean;begin if Pus[ST[k]] then Valid:=false else if S+gr[ST[k]]<=G then begin S:=S+gr[ST[k]]; CG:=CG+c[ST[k]]; Valid:=true end else Valid:=falseend;

begin Citire; k:=1; for i:=1 to n do Pus[i]:=false; ST[k]:=0; CG:=0; S:=0; Cmax:=0;

while k>0 do begin repeat ST[k]:=ST[k]+1 until (ST[k]>n) or Valid; if ST[k]<=n then begin if CG>Cmax then begin Cmax:=CG; NOb:=k; for i:=1 to k do STmax[i]:=ST[i]; Gmax:=S; end; Pus[ST[k]]:=true; k:=k+1; ST[k]:=0 end else begin k:=k-1; if k>0 then

begin S:=S-gr[ST[k]]; CG:=CG-c[ST[k]]; Pus[ST[k]]:=false end end end;

writeln('Cistigul maxim: ',Cmax); writeln('Greutate transportata: ',Gmax); write('Obiectele transportate: '); for i:=1 to NOb do write(STmax[i],' '); writelnend.

Problema 5

Enunþ. Fiind dat un numãr natural N, se cere sã se afiºeze toate descom-punerile sale ca sumã de numere prime.

Rezolvare. Pentru eficienþã, vom calcula mai întâi toate numerele prime mai mici ca N; acestea vor fi memorate în vectorul Numar.

Rutina de backtracking este similarã cu cea din problema 2, cu excepþia faptului cã termenii pot lua valori din Numar[1..P] ºi cã descompunerea nu trebuie sã aibã un numãr fix de termeni.

Program SumaPrime;

var ST, Numar :array[0..1000] of integer; n, K, P, S, i :integer;

Function Prim( X : integer):boolean;var i:integer;begin Prim:=true; i:=2; while i*i<=X do begin if X mod i=0 then begin Prim:=false; i:=X

end; i:=i+1 endend;

procedure Printsol;var i:integer;begin for i:=1 to k do write(Numar[ST[i]],' '); writelnend;

begin fillchar(ST,sizeof(ST),0); fillchar(Numar,sizeof(Numar),0); write('N='); readln(N); P:=0; for i:=2 to N do if Prim(i) then begin inc(P); Numar[P]:=i end; k:=1; S:=0; while k>0 do begin ST[k]:=ST[k]+1; if (ST[k]<=P) and (S+Numar[St[k]]<=N) then if S+Numar[St[k]]=N then Printsol else begin S:=S+Numar[ST[k]]; k:=k+1; ST[k]:=ST[k-1]-1 end else begin k:=k-1; S:=S-Numar[St[k]] end endend.

Problema 6

Enunþ. ("Attila ºi regele") Un cal ºi un rege se aflã pe o tablã de ºah. Unele câmpuri ale tablei sunt "arse", poziþiile lor fiind cunoscute. Calul nu poate cãlca pe câmpuri "arse", iar orice miºcare a calului face ca respectivul câmp sã devinã "ars". Sã se afle dacã existã o succesiune de mutãri permise (cu restricþiile de mai sus), prin care calul sã poatã ajunge la rege ºi sã revinã la poziþia iniþialã. Poziþia iniþialã a calului, precum ºi poziþia regelui sunt considerate "nearse".

Rezolvare. Vom folosi o stivã triplã cu elemente de tip pozitie: l,c - linia ºi coloana poziþiei curente, mut - mutarea fãcutã din aceastã poziþie.

Vectorul Mutari (constant) conþine cele 8 mutãri pe care le poate efectua un cal (modificãrile coordonatelor calului prin mutarea respectivã; vezi ºi problema 4).

Pentru început vom citi datele de intrare cu procedura Citire. Fiºierul de intrare input.txt trebuie sã aibã forma:

N // pe prima linie, n - numãrul de linii (coloane) al tablei

lCal cCal // pe urmãtoarele douã linii, poziþia iniþialã a

lRege cRege // calului ºi a regelui

a11 a12 a13 .. a1n // pe urmãtoarele n linii, tabla de ºah

.... // aij = 0, dacã pãtrãþelul respectiv e ars

an1 an2 an3 .. ann // = 1, dacã nu este ars

Vom face o "bordare" a tablei de ºah cu douã rânduri de pãtrãþele "arse". De exemplu dacã tabla este 3x3 ºi notãm cu 0 pãtrãþelele arse ºi cu 1 pe cele nearse:

0000000000000000111000011100001110000000000000000

Aceastã bordare este utilã pentru cã nu trebuie sã mai verificãm dacã coordonatele rezultate în urma efectuãrii unei mutãri sunt pe tabla de ºah.

Astfel, presupunând cã l ºi c sunt coordonatele rezultate în urma unei mutãri, condiþia de validitate a acelei mutãri va fi:

if a[l,c]=1 then ... , în loc de,

if (l>=1) and (l<=n) and (c>=1) and (c<=n) and (a[l,c]=1) then …

Condiþia de validitate a unei mutãri este ca poziþia rezultatã în urma mutãrii sã fie pe un pãtrat "nears" ºi diferitã de poziþia iniþialã a calului dacã acesta nu a ajuns încã la rege. Dacã poziþia rezultatã în urma mutãrii este poziþia iniþialã a calului ºi acesta a ajuns la rege atunci programul se terminã cu afiºarea soluþiei (variabila Terminat devine TRUE).

Dacã mutarea este corectã, se "arde" câmpul respectiv ºi se verificã dacã poziþia rezultatã în urma mutãrii este poziþia regelui pentru da valoarea TRUE variabilei Rege (care este TRUE dacã s-a ajuns la rege ºi FALSE, altfel). La trecerea pe un nivel superior al stivei, se iniþializeazã acest nivel cu poziþia curentã.

La trecerea pe un nivel inferior al stivei, se marcheazã poziþia respectivã ca "nearsã" ºi, dacã poziþia de pe care se coboarã în stivã era poziþia regelui, variabila Rege devine FALSE.

program attila;

const Mutari:array [1..8,1..2] of integer= ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));

type pozitie=record l,c,mut:integer; end;

var N, lCal, cCal, lRege, cRege, k, nlin, ncol, i :integer; T :array [-1..22,-1..22] of integer; ST :array [1..400] of pozitie; Rege, Terminat :boolean;

procedure citire;var f:text; i,j:integer;begin assign(f,'input.txt'); reset(f); readln(f,N); readln(f,lCal,cCal); readln(f,lRege,cRege); for i:=1 to n do begin for j:=1 to n do

read(f,T[i,j]); readln(f); end; close(f);end;

procedure Printsol;var i:integer;begin for i:=1 to k do writeln(ST[i].l,' ',ST[i].c); writeln(lCal,' ',cCal)end;

function Valid:boolean;begin nlin:=ST[k].l+Mutari[ST[k].mut,1]; ncol:=ST[k].c+Mutari[ST[k].mut,2]; if (nlin=lCal) and (ncol=cCal) then if Rege then begin Terminat:=true; Valid:=true; end else Valid:=false else if T[nlin,ncol]=1 then Valid:=true else Valid:=falseend;

begin Citire; for i:=-1 to N+2 do begin T[-1,i]:=0; T[0,i]:=0; T[n+1,i]:=0; T[n+2,i]:=0; T[i,-1]:=0; T[i,0]:=0; T[i,n+1]:=0; T[i,n+2]:=0 end;

k:=1; ST[1].mut:=0; ST[1].l:=lcal; ST[1].c:=ccal; Rege:=false; Terminat:=false; while (k>0) and (not Terminat) do begin repeat ST[k].mut:=ST[k].mut+1 until (ST[k].mut>8) or Valid; if ST[k].mut<=8 then

if Terminat then Printsol else begin k:=k+1; ST[k].mut:=0; ST[k].l:=nlin; ST[k].c:=ncol; T[nlin,ncol]:=0; if (nlin=lRege) and (ncol=cRege) then Rege:=true end else begin T[ST[k].l,ST[k].c]:=1; if (ST[k].l=lRege) and (ST[k].c=cRege) then Rege:=false; k:=k-1 end end; if k=0 then writeln('Nu exista solutie.')end.

Problema 7

Enunþ. (Proprietãþi numerice) Numãrul 123456789 are câteva caracteristici amuzante. Astfel, înmulþit cu 2,4,7 sau 8 dã ca rezultat tot un numãr de nouã cifre distincte (în afarã de 0):

123456789⋅ 2 = 246913578 ; 123456789⋅ 4 = 493827156

123456789⋅ 7 = 864197523 ; 123456789⋅ 8 = 987654312.

Aceastã proprietate nu funcþioneazã pentru numerele 3,6 sau 9. Existã totuºi multe numere de nouã cifre distincte (fãrã 0) care înmulþite cu 3 au aceeaºi proprietate. Sã se listeze toate aceste numere în care ultima cifrã este 9.

Concurs Tuymaada 1995

Rezolvare. În stivã se vor reþine cifrele numãrului cãutat. Pentru cã ultima cifrã este întotdeauna 9, stiva va avea numai 8 poziþii. Condiþia de "valid" este ca cifra selectatã sã nu fi fost folositã anterior (de fapt se genereazã toate permutãrile cifrelor 1..8).

Datoritã faptului cã la fiecare nivel în stivã se alege cea mai micã cifrã nefolositã care nu a fost încã încercatã, numerele vor fi generate în ordine crescãtoare. Astfel, dacã înmulþind cu 3 numãrul obþinut la pasul curent se va obþine un numãr pe 10 cifre vom ºti cã ºi urmãtoarele numere vor da un produs pe 10 cifre. Rezultã cã procesul se opreºte când întâlneºte numãrul 341256789 (cel mai mic numãr cu cifrele distincte, mai mare decât 333333333).

program Numeric;

var ST,U :array[0..10] of integer; K,i,f :integer; e :double; t :set of char; s :string;

begin k:=1; fillchar(ST,sizeof(ST),0); fillchar(U,sizeof(U),0); ST[9]:=9; U[9]:=1; while k>0 do if k=9 then begin e:=0; { se valideazã o posibilã soluþie } for f:=1 to 9 do e:=e*10+ST[f]; e:=e*3; { se înmulþeºte numãrul cu 3 } str(e:0:0,s); { ºi se verificã dacã cifrele } t:=[]; { rezultatului sunt distincte } i:=0; if length(s)=10 then exit; for f:=1 to length(s) do if not (s[f] in t) then begin i:=i+1; t:=t+[s[f]] end; if i=9 then begin for f:=1 to 9 do write(ST[f]); writeln end; k:=k-1 end else begin U[ST[k]]:=0; repeat ST[k]:=ST[k]+1 until (U[ST[k]]=0) or (ST[k]>8); if ST[k]>8 then begin ST[k]:=0; k:=k-1

end else begin U[ST[k]]:=1; k:=k+1 end endend.

Problema 8

Enunþ. Sã se dispunã pe cele 12 muchii ale unui cub toate numerele de la 1 la 12, astfel încât suma numerelor aflate pe muchiile unei feþe sã fie aceeaºi pentru toate feþele.

Considerãm muchiile numerotate ca în figurã:

Ieºirea va fi într-un fiºier text având numele solcub.txt care va conþine câte o soluþie pe fiecare linie sub forma:

1 m2 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12

...

1 m2 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12

unde mi este valoarea din mulþimea {2,...,12} plasatã pe muchia i, i=2..12, iar muchia 1 conþine valoarea 1 în toate soluþiile.

O soluþie corectã este cea de mai jos, ilustratã ºi în figurã:

1 12 9 6 8 5 7 4 11 3 2 10

Baraj Sibiu, 1996

Rezolvare. Notãm cu F1, ... ,F6 suma numerelor de pe muchiile feþelor cubului.

F1 = F2 = ... = F6 = F

F1+F2+F3+F4+F5+F6 = 2(m1+m2+...+m12), pentru cã fiecare muchie apare în douã feþe ale cubului.

Deci, 6*F=2*(m1+m2+...+m12),

dar m1+m2+...+m12 = 1+2+…+12 =78 => 6*F=2*78=156 => F=26.

Deci suma muchiilor de pe fiecare faþã trebuie sã fie 26.

Observãm cã este suficient sã folosim doar 6 nivele ale stivei, celelalte valori deducându-se din acestea 6. Astfel, m1=1 întotdeauna. Dupã ce aºezãm m2 ºi m3, m8 se deduce ca fiind 26-m1-m2-m3. Analog, dupã ce aºezãm m4 ºi m5 se deduce m9=26-m4-m5. La fel, se deduc m10=26-m2-m4, m11=26-m5-m7-m3 ºi m12=26-m9-m10-m11.

Deci numai 6 muchii variazã independent una de celelalte: m2,...,m7. Vectorul auxiliar Pus este folosit pentru a ºti ce numere au fost deja aºezate în stivã.

În concurs, la aceastã problemã a fost impus un timp de execuþie de maxim 10 secunde. Programul face

aranjamente de 11 luate câte 6, timpul de calcul fiind O( )≈ 55000, adicã sub o secundã. Dacã se utiliza soluþia banalã, adicã permutãri de 11, timpul de calcul era O(11!)≈ 39 milioane ºi timpul de execuþie era de aproximativ 30 de secunde.

program cub_magic;

var ST :array [2..12] of integer; Pus :array [1..26] of boolean; k, i :integer;

function Valid:boolean;begin if Pus[ST[k]] then Valid:=false else case k of 2:begin Pus[ST[2]]:=true; Valid:=true end; 3:begin Pus[ST[3]]:=true; ST[8]:=26-ST[2]-ST[3]-1; if not Pus[ST[8]] then begin Pus[ST[8]]:=true; Valid:=true end else begin Pus[ST[3]]:=false; Valid:=false end end; 4:begin Pus[ST[4]]:=true; Valid:=true end; 5:begin Pus[ST[5]]:=true; ST[9]:=26-ST[5]-ST[4]-1; if not Pus[ST[9]] then begin Pus[ST[9]]:=true; Valid:=true end else begin Pus[ST[5]]:=false; Valid:=false end end; 6:begin Pus[ST[6]]:=true;

ST[10]:=26-ST[4]-ST[6]-ST[2]; if (ST[10]>0) and (not Pus[ST[10]]) then begin Pus[ST[10]]:=true; Valid:=true end else begin Pus[ST[6]]:=false; Valid:=false end; end; 7:begin Pus[ST[7]]:=true; ST[11]:=26-ST[5]-ST[7]-ST[3]; ST[12]:=26-ST[6]-ST[7]-ST[8]; if (ST[11]>0) and (ST[12]>0) and (ST[11]<>ST[12]) and (not Pus[ST[11]]) and (not Pus[ST[12]]) and (ST[9]+ST[10]+ST[11]+ST[12]=26) then begin Pus[ST[7]]:=false; Valid:=true end else begin Pus[ST[7]]:=false; Valid:=false end; end; end;end;

procedure Printsol;begin write('1 '); for i:=2 to 12 do write(ST[i],' '); writelnend;

begin k:=2; ST[k]:=0; Pus[1]:=true; for i:=2 to 26 do Pus[i]:=false; while k>1 do begin repeat ST[k]:=ST[k]+1

until (ST[k]>12) or Valid; if ST[k]<=12 then if k=7 then Printsol else begin k:=k+1; ST[k]:=0 end else begin k:=k-1; case k of 2:Pus[ST[2]]:=false; 3:begin Pus[ST[3]]:=false; Pus[ST[8]]:=false end; 4:Pus[ST[4]]:=false; 5:begin Pus[ST[5]]:=false; Pus[ST[9]]:=false end; 6:begin Pus[ST[6]]:=false; Pus[ST[10]]:=false end end end endend.

Problema 9

Enunþ. Fie Am,n o matrice binarã. Se cunosc coordonatele (i,j) ale unui element, i aparþinând 1...m, j aparþinând 1...n, care are valoarea 1. Sã se gãseascã toate ieºirile din matrice mergând numai pe elementele cu valoarea 1.

Rezolvare. Vom proceda ca la problema 4: reþinem un vector cu deplasãrile relative ale miºcãrilor posibile; se subînþelege cã dintr-o cãsuþã se poate merge doar în cele patru vecine cu ea:

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

Condiþia pentru o soluþie o reprezintã verificarea atingerii marginilor matricei; deci avem patru cazuri, pentru fiecare din cele patru margini: i=1 sau i=M sau j=1 sau j=N.

O mutare este consideratã validã dacã:

● este în matrice;

● poziþia respectivã este marcatã cu 1.

Poziþiile deja parcurse sunt marcate cu 2 pentru a nu fi considerate încã o datã în soluþie.

Program Matrice;

const Muta : array[0..4,1..2] of integer= ( (0,0), (-1,0), (1,0), (0,1), (0,-1) );

var N,M,k,i,j,oi,oj :integer; A :array[0..100,0..100] of integer; ST :array[0..1000] of integer;

Procedure Sol;var x,y,f :integer;begin x:=oi; y:=oj; for f:=1 to k do begin write('(',x,',',y,') '); x:=x+Muta[ST[f],1]; y:=y+Muta[ST[f],2] end; writeln; dec(k)end;

Function Valid:boolean;var pi,pj :integer;begin pi:=i+Muta[ST[k],1]; pj:=j+Muta[ST[k],2]; Valid:=(pi>0) and (pj>0) and (pi<=M) and (pj<=N) and (A[pi,pj]=1)end;

begin write('M,N:'); readln(M,N); for i:=1 to M do

for j:=1 to N do begin write('A[',i,',',j,']='); readln(A[i,j]) end; write('i,j:'); readln(i,j); oj:=j; oi:=i; A[i,j]:=-1; fillchar(ST,sizeof(ST),0); k:=1; while k>0 do begin if (i=1) or (j=1) or (i=M) or (j=N) then Sol; if A[i,j]=2 then A[i,j]:=1; i:=i-Muta[ST[k],1]; j:=j-Muta[ST[k],2]; repeat inc(ST[k]) until (ST[k]>4) or valid; if ST[k]=5 then begin ST[k]:=0; dec(k) end else begin A[i,j]:=2; i:=i+Muta[ST[k],1]; j:=j+Muta[ST[k],2]; inc(k) end endend.

Problema 10

Enunþ. Se dã un numãr natural par N. Sã se afiºeze toate ºirurile de N paranteze care se închid corect.

Rezolvare. Un ºir de N paranteze care se închid corect, este un ºir în care fiecãrei paranteze deschise îi corespunde o parantezã închisã la o poziþie ulterioarã în ºir.

Exemple de ºiruri corecte: (())() ; ((())) ; ()()()

Exemple de ºiruri incorecte: ())()) ; (((()) ; )()()(

Deducem din propoziþia de mai sus o primã condiþie necesarã pentru ca un ºir de paranteze sã se închidã corect ºi anume cã nu trebuie sã deschidem mai mult de N/2 paranteze. Dupã cum se vede însã din aceste exemple (incorecte), aceastã condiþie nu este suficientã: (()))( ; )))((( ; )()()( .

A doua condiþie este sã nu închidem mai multe paranteze decât am deschis.

Pentru formalizarea condiþiilor notãm cu Nd(k) ºi Ni(k) numãrul de paranteze deschise, respectiv închise, pânã la poziþia k a ºirului, inclusiv. Cele douã condiþii sunt:

1. Nd(k) ≤ N/2, ∀ 1 ≤ k ≤ n

2. Nd(k) ≥ Ni(k), ∀ 1 ≤ k ≤ n

Pentru implementare folosim o stivã cu N nivele:

st[i] = 1, dacã paranteza de pe poziþia i este deschisã

2, dacã paranteza de pe poziþia i este închisã.

În variabilele Nd ºi Ni avem numãrul de paranteze de fiecare fel aºezate în ºir pânã la poziþia curentã, k.

Pentru a aºeza o parantezã deschisã pe poziþia curentã trebuie sã fi deschis mai puþin de N/2 paranteze, adicã Nd<N/2.

Pentru a aºeza o parantezã închisã pe poziþia curentã trebuie sã mai avem o parantezã pe care sã o închidem, adicã Nd>Ni.

La urcarea ºi coborârea în stivã se modificã Nd sau Ni în funcþie de tipul parantezei de pe nivelul respectiv.

program Paranteze;

var ST :array [0..100] of integer; k, N, Nd, Ni :integer;

procedure Printsol;var i:integer;begin for i:=1 to N do if ST[i]=1 then write('(') else write(')'); writelnend;

function valid:boolean;begin if ST[k]=1 then if Nd<N div 2 then valid:=true else valid:=false else if Nd>Ni then valid:=true else valid:=falseend;

begin write('N= '); readln(N); Nd:=0; Ni:=0; k:=1; ST[k]:=0; while k>0 do begin repeat ST[k]:=ST[k]+1 until (ST[k]>2) or valid; if ST[k]<=2 then if k=N then Printsol else begin if ST[k]=1 then Nd:=Nd+1 else Ni:=Ni+1; k:=k+1; ST[k]:=0 end else begin k:=k-1; if ST[k]=1 then Nd:=Nd-1 else Ni:=Ni-1 end endend.

Problema 11

Enunþ. Se considerã o mulþime de N elemente ºi un numãr natural K nenul. Sã se calculeze câte submulþimi cu k elemente satisfac pe rând condiþiile de mai jos ºi sã se afiºeze aceste submulþimi:

a. conþin p obiecte date;

b. nu conþin nici unul din q obiecte date

c. conþin exact un obiect dat, dar nu conþin un altul

d. conþin exact un obiect din p obiecte date

e. conþin cel puþin un obiect din p obiecte date

f. conþin r obiecte din p obiecte date, dar nu conþin alte q obiecte date.

Rezolvare. Pentru calcularea ºi generarea soluþiilor se pot folosi doar combinãrile. Pentru simplitatea programului se poate considera, fãrã a restrânge generalitatea, cã cele p, respectiv q obiecte date au numerele de ordine 1,2,3, .. ,p, respectiv p+1,p+2, .. , p+q (în cazul c) avem p=q=1).

Fiecãrui nivel al stivei îi este asociatã o mulþime de elemente care pot ocupa acel loc în soluþie. Pentru a generaliza, vom considera cã fiecare mulþime este de forma {Li,Li+1,Li+2,...,LS}. Anume: pentru fiecare nivel i al stivei vom reþine doi vectori Li[i] ºi Ls[i] care indicã limita inferioarã, respectiv superioarã a elementului ce poate fi ales pe nivelul i (deci pentru Li[i]=2 ºi Ls[i]=5, pe nivelul i vom putea avea doar elementele 2,3,4,5 ).

Acum sã vedem cu ce valori vom iniþializa vectorii Li ºi Ls pentru fiecare caz:

a) practic trebuie sã alegem întotdeauna elementele 1,2,3, .. ,p ºi apoi încã oricare k-p din cele rãmase (p+1,p+2, .. , N). Pentru a forþa alegerea primelor p elemente vom considera Li[i]=Ls[i]=i.

Deci vectorii vor arãta astfel:

I 1 2 3 … p p+1 p+2 … NLi 1 2 3 … p p+1 p+1 … p+1Ls 1 2 3 … p N N … N

b) aici considerãm p=0: deci obiectele care nu trebuie selectate vor fi 1,2,3 ..., q. Avem Li[i]=Q+1 ºi Ls[i]=N pentru oricare i.

c) p=1 ºi q=1 Li[1]=1 ºi Ls[1]=1 obiectul 1 trebuie ales mereu;

Li[i]=3 ºi Ls[i]=N, pentru i>1 cel cu numãrul 2 trebuie evitat.

d) Li[1]=1 ºi Ls[1]=p alegem un obiect între 1 ºi p;

Li[i]=p+1 ºi Ls[i]=N, pentru i>1 ºi restul între p+1 ºi N.

e) Li[1]=1 ºi Ls[1]=p un obiect între 1 ºi p;

Li[i]=1 ºi Ls[i]=N, pentru i>1 restul pot lua orice valori.

f) Li[i]=1 ºi Ls[i]=p, pentru 1≤i≤R pe primele r poziþii alegem obiecte din primele p;

Li[i]=p+q+1 ºi Ls[i]=N, pentru R<i≤K restul trebuie sã nu fie printre cele p sau q.

Deci vom scrie o singurã rutinã backtracking, care, în funcþie de iniþializãrile vectorilor Li ºi Ls, va furniza rãspunsul la oricare din cele ºase cerinþe. Programul va mai folosi ºi vectorul u care va indica dacã elementul i a fost sau nu utilizat în soluþie pânã la pasul curent. Pentru cã variabila k face parte din datele de intrare, nivelul curent în stivã va fi memorat în variabila i.

program submultimi;

var ST, Li, Ls, u :array[0..1000] of integer; N, P, Q, R, K, i, f :integer; sol :longint; ch :char;

begin write('N,K,P,Q:'); readln(N,K,P,Q); write('subpunctul (A,B,C,D,E sau F):'); readln(ch); Case UpCase(ch) of 'A':begin for i:= 1 to P do begin Li[i]:=i; Ls[i]:=i end; for i:=P+1 to K do begin Li[i]:=P+1; Ls[i]:=N end end; 'B': for i:= 1 to K do begin Li[i]:=Q+1; Ls[i]:=N end; 'C':begin for i:= 2 to K do begin Li[i]:=3; Ls[i]:=N end; Li[1]:=1; Ls[1]:=1 end; 'D':begin

for i:= 2 to K do begin Li[i]:=P+1; Ls[i]:=N end; Li[1]:=1; Ls[1]:=p end; 'E':begin for i:= 2 to K do begin Li[i]:=1; Ls[i]:=N end; Li[1]:=1; Ls[1]:=p end; 'F':begin write('R='); readln(R); for i:= 1 to R do begin Li[i]:=i; Ls[i]:=P end; for i:=R+1 to K do begin Li[i]:=P+Q+1;Ls[i]:=N end end end; i:=1; fillchar(ST,sizeof(ST),0); fillchar(u,sizeof(u),0); ST[1]:=Li[1]-1; sol:=0; while i>0 do if i=k+1 then begin sol:=sol+1; for f:=1 to K do write(ST[f],' '); writeln; i:=i-1 end else begin U[ST[i]]:=0; repeat ST[i]:=ST[i]+1 until (ST[i]>LS[i]) or (U[ST[i]]=0); if ST[i]>LS[i] then begin ST[i]:=0; i:=i-1 end else begin U[ST[i]]:=1; i:=i+1; if ST[i-1]<Li[i] then ST[i]:=Li[i]-1 else ST[i]:=ST[i-1]-1 end end;

writeln('Numar solutii= ',sol)end.

Problema 12

Enunþ. Sã se genereze toate permutãrile de N cu proprietatea cã oricare ar fi

2≤ i≤ N, existã 1≤ j≤ i astfel încât |V(i)-V(j)|=1.

Exemplu: pentru N=4, permutãrile cu proprietatea de mai sus sunt:

2134, 2314, 3214, 3241, 3421, 4321, 1234

Rezolvare. Pentru generarea permutãrilor folosim o stivã cu N nivele ºi un vector auxiliar:

Pus[i]=TRUE, dacã numãrul i a fost aºezat deja în permutare;

FALSE, altfel.

Condiþiile care trebuie îndeplinite pentru aºezarea unui numãr c pe nivelul k al stivei sunt:

● Pus[c]=FALSE, adicã sã nu fi aºezat deja numãrul c în permutare;

● cel puþin unul din numerele aºezate pe poziþiile 1..k-1 ,respectiv st[1]..st[k-1], sã aibã diferenþa absolutã faþã de c egalã cu 1.

program Permutari;

var ST :array [1..20] of integer; k, i, N :integer; Pus :array [1..20] of boolean;

function Valid:boolean;var tmp:boolean;begin if k=1 then Valid:=true else begin tmp:=false; if not Pus[ST[k]] then for i:=1 to k-1 do if abs(ST[k]-ST[i])=1 then tmp:=true;

Valid:=tmp endend;

procedure Printsol;var i:integer;begin for i:=1 to N do write(st[i],' '); writelnend;

begin write('N= '); readln(N); for i:=1 to N do Pus[i]:=false; k:=1; ST[k]:=0; while k>0 do begin repeat ST[k]:=ST[k]+1 until (ST[k]>N) or Valid; if ST[k]<=N then if k=N then Printsol else begin Pus[ST[k]]:=true; k:=k+1; ST[k]:=0 end else begin k:=k-1; Pus[ST[k]]:=false end endend.

Problema 13

Enunþ. Se dau N puncte albe ºi N puncte negre în plan, de coordonate întregi. Fiecare punct alb se uneºte cu câte un punct negru, astfel încât din fiecare punct, fie el alb sau negru, pleacã exact un segment. Sã se determine o astfel de configuraþie de segmente încât oricare douã segmente sã nu se intersecteze. Se citesc 2N perechi de coordonate corespunzând punctelor.

Rezolvare. Vom reþine în vectorii X ºi Y coordonatele punctelor, aºezând pe primele N poziþii punctele

albe ºi pe poziþiile N+1, ... ,2N punctele negre.

Soluþia problemei este de fapt o permutare. Aceasta va fi generatã în vectorul ST: ST[i] reprezintã punctul negru cu care va fi conectat punctul alb i.

Funcþia Intersect întoarce o valoare booleanã care indicã dacã segmentul determinat de punctul alb i ºi punctul negru ST[i] se intersecteazã cu cel determinat de j ºi respectiv ST[j].

Condiþia de validitate pentru un segment este, evident, ca acesta sã nu se intersecteze cu nici unul din cele construite anterior.

program Puncte;

var N,i,k :integer; X,Y :array[1..1000] of real; ST,u :array[0..1000] of integer;

function Intersect(i,j:integer):boolean;var a1,a2,b1,b2:real;begin if x[i]=x[st[i]] then a1:=9e10 else a1:=(y[st[i]]-y[i])/(x[st[i]]-x[i]); if x[j]=x[st[j]] then a2:=9e10 else a2:=(y[st[j]]-y[j])/(x[st[j]]-x[j]);

b1:=y[i]-a1*x[i]; b2:=y[j]-a2*x[j]; Intersect:= ((x[i]*a2+b2-y[i])*(x[st[i]]*a2+b2-y[st[i]])<=0) and ((x[j]*a1+b1-y[j])*(x[st[j]]*a1+b1-y[st[j]])<=0)end;

function Valid:boolean;var i:integer; r:boolean;begin r:=(U[ST[k]]=0); i:=1; while r and (i<k) do begin r:=r and (not InterSect(k,i)); i:=i+1 end; valid:=rend;

procedure Printsol;var i:integer;begin for i:=1 to N do write(ST[i],' '); writeln; k:=0;end;

begin write('N='); readln(N); writeln('punctele albe:'); for i:=1 to N do begin write(i:3,':X,Y='); readln(X[i],Y[i]); end; writeln('punctele negre:'); for i:=N+1 to 2*N do begin write(i:3,':X,Y='); readln(X[i],Y[i]); end;

k:=1; fillchar(ST,sizeof(ST),0); fillchar(u,sizeof(u),0); ST[1]:=N; while k>0 do begin repeat St[k]:=St[k]+1 until (ST[k]>2*N) or valid; if ST[k]<=2*n then if k=N then Printsol else begin U[ST[k]]:=1; k:=k+1; ST[k]:=N end else begin k:=k-1; U[ST[k]]:=0 end endend.

Problema 14

Enunþ: Se considerã n puncte în plan, de coordonate reale, (X1,Y1), (X2,Y2), (X3,Y3), ... , (Xn,Yn). Elaboraþi un program care selecteazã din aceste puncte vârfurile unui pãtrat, ce conþine numãrul maximal de puncte din cele date. Afiºaþi coordonatele punctelor selectate ºi numãrul de puncte incluse în pãtratul respectiv.

Notã: Punctele care aparþin laturilor pãtratului se considerã incluse în pãtrat (inclusiv colþurile pãtratului).

Datele de intrare se vor citi din fiºierul input.txt, astfel:

● pe prima linie n, numãrul de puncte

● pe urmãtoarele n linii coordonatele punctelor.

Rezolvare. Coordonatele punctelor se vor citi în vectorul Pct.

Stiva are 4 nivele reprezentând indicii celor 4 puncte care formeazã pãtratul. Dacã se gaseºte un astfel de pãtrat, se numãrã câte puncte sunt incluse în acest pãtrat. Se pãstreazã cea mai bunã soluþie în vectorul MaxP.

Condiþia pentru ca 3 puncte sã poatã face parte dintr-un pãtrat este sã formeze un triunghi dreptunghic isoscel. Acest lucru se verificã prin relaþia între distanþele dintre puncte (d12,d23,d13). Douã dintre

acestea trebuie sã fie egale ºi a treia egalã cu una din primele douã înmulþitã cu .

Atenþie! În geometria analiticã aplicatã, testul de egalitate a douã variabile reale a ºi b nu trebuie sã fie "dacã a=b", ci "dacã abs(a-b)<1e-5", adicã dacã diferenþã absolutã dintre a ºi b este mai micã decât

10-5. Acest test evitã erorile de aproximaþie (în programul nostru acestea pot apãrea, de exemplu, la

operaþia ). Din acest motiv, am folosit funcþia booleanã Egal care face testul de egalitate prezentat mai sus.

Dacã cele 3 puncte formeazã un triunghi dreptunghic isoscel se pãstreazã în variabila colt indicele vârfului triunghiului (unghiul drept) ºi în vectorul P (pe primele 3 poziþii) indicii celor 3 puncte în ordinea în care apar în pãtrat. Astfel, P[2] este vârful triunghiului dreptunghic isoscel ºi P[1], P[3] celelalte douã vârfuri.

Pe nivelul 4, condiþia de validitate este ca punctul aºezat sã aibã distanþele la P[1] ºi P[3], egale cu

distanþele de la P[2] la aceste douã puncte.

Funcþia Dist(p1,p2) întoarce distanþa între Pct[p1] ºi Pct[p2].

Funcþia booleanã Inclus(i) întoarce TRUE dacã punctul Pct[i] este inclus în pãtratul P[1]P[2]P[3]P[4] ºi FALSE, altfel. Pentru a fi inclus în pãtrat, punctul Pct[i] trebuie sã se afle între dreptele suport ale segmentelor P[1]P[2] ºi P[4]P[3], ºi de asemenea între dreptele suport ale lui P[2]P[3] ºi P[1]P[4]. Pentru a se afla între douã drepte paralele, de acelaºi sens, un punct trebuie sã se afle în semiplane de semne opuse faþã de acele drepte.

program puncte;

type punct=record x,y:real end;

var n, k, colt, max, i :integer; Pct :array [1..20] of punct; ST :array [1..4] of integer; P,maxp :array [1..4] of punct;

procedure Citire;var i :integer; f :text;begin assign(f,'input.txt'); reset(f); readln(f, n); for i:=1 to n do readln(f, Pct[i].x, Pct[i].y); close(f)end;

function Egal(val1,val2:real):boolean;begin Egal:=(abs(val1-val2)<=1e-5)end;

function Dist(p1,p2:integer):real;begin Dist:=sqrt(sqr(pct[p1].x-pct[p2].x)+sqr(pct[p1].y pct[p2].y))end;

function Valid:boolean;var d12,d23,d13,d1,d2,d3:real;begin if k<=2 then valid:=true

else if k=3 then begin d12:=Dist(ST[1],ST[2]); d23:=Dist(ST[2],ST[3]); d13:=Dist(ST[1],ST[3]); if Egal(d12,d23) then if Egal(d13,d12*sqrt(2)) then begin colt:=2; P[1]:=Pct[ST[1]];P[2]:=Pct[ST[2]]; P[3]:=Pct[ST[3]]; Valid:=true end else Valid:=false else if Egal(d12,d13) then if Egal(d23,d12*sqrt(2)) then begin colt:=1; P[1]:=Pct[ST[2]]; P[2]:=Pct[ST[1]]; P[3]:=Pct[ST[3]]; Valid:=true end else Valid:=false else if Egal(d13,d23) and Egal(d12,d23*sqrt(2)) then begin colt:=3; P[1]:=Pct[ST[1]]; P[2]:=Pct[ST[3]]; P[3]:=Pct[ST[2]]; Valid:=true end else Valid:=false end else begin case colt of 1:begin d1:=Dist(ST[2],ST[4]); d2:=Dist(ST[3],ST[4]); d3:=Dist(ST[1],ST[2]) end; 2:begin d1:=Dist(ST[1],ST[4]); d2:=Dist(ST[3],ST[4]); d3:=Dist(ST[1],ST[2]) end; 3:begin d1:=Dist(ST[2],ST[4]); d2:=Dist(ST[1],ST[4]); d3:=Dist(ST[3],ST[2]) end;

end; if Egal(d1,d3) and Egal(d2,d3) then begin Valid:=true; P[4]:=Pct[ST[4]] end else Valid:=false endend;

function Inclus(i:integer):boolean;var tmp:boolean;begin tmp:=false; if ((Pct[i].x-P[3].x)*(P[2].y-P[3].y)-(Pct[i].y- P[3].y)* (P[2].x-P[3].x))*((Pct[i].x-P[4].x)*(P[1].y-P[4].y)-(Pct[i].y-P[4].y)*(P[1].x-P[4].x))<=0 then if ((Pct[i].x-P[3].x)*(P[4].y-P[3].y)-(Pct[i].y-P[3].y)*(P[4].x-P[3].x))* ((Pct[i].x-P[2].x)*(P[1].y-P[2].y)-(Pct[i].y-P[2].y)*(P[1].x-P[2].x))<=0 then tmp:=true inclus:=tmpend;

procedure Numara;var c,i:integer;begin c:=0; for i:=1 to n do if Inclus(i) then c:=c+1; if c>Max then begin Max:=c; for i:=1 to 4 do Maxp[i]:=P[i] endend;

begin Citire; k:=1; ST[k]:=0; Max:=0; while k>0 do begin repeat ST[k]:=ST[k]+1 until (ST[k]>n) or Valid; if ST[k]<=n then if k=4 then Numara

else begin k:=k+1; ST[k]:=ST[k-1] end else k:=k-1 end; if Max>0 then for i:=1 to 4 do writeln(Maxp[i].x:0:3,' ',Maxp[i].y:0:3); writeln(Max)end.

Problema 15

Enunþ. Fiind dat un numãr natural N ºi un vector V cu N componente întregi, se cer urmãtoarele:

● sã se determine toate subºirurile crescãtoare de lungime [N/5];

● sã se calculeze p(1)+p(2)+...+p(k), unde p(k) reprezintã numãrul subºirurilor crescãtoare de lungime k.

Vom scrie o singurã rutinã de backtracking, care va genera subºirurile crescãtoare de lungime L. Pentru a afiºa soluþiile doar pentru L=[N/5] folosim variabila booleanã scrie.

Punctul doi se realizeazã prin însumarea numãrului de soluþii generate de aceeaºi procedurã, cu L luând valori între 1 ºi k.

În stivã vom reþine indicele din vectorul iniþial al elementului aºezat pe poziþia i în subºir. În procedura de backtracking, condiþia de validitate pentru a pune un element pe poziþia i este ca acesta sã se afle în ºirul iniþial dupã elementul anterior lui din subºir (ST[i]>ST[i-1]) ºi valoarea sa efectivã sã fie mai mare decât a elementului selectat anterior: V[ST[i]]≥ V[ST[i-1]].

S-a considerat "mai mare sau egal" pentru cã în cerinþã se cer subºirurile crescãtoare ºi nu strict-crescãtoare.

program Subsiruri;

var ST,V :array[0..1000] of integer; N,k,i :integer; sol :longint; scrie :boolean;

procedure Printsol(l:integer);

var i:integer;begin if scrie then begin for i:=1 to l do write(V[ST[i]],' '); writeln end; sol:=sol+1end;

procedure Bkt(l:integer);var f,i:integer;begin i:=1; ST[1]:=0; while i>0 do begin repeat ST[i]:=ST[i]+1 until ((ST[i]>ST[i-1]) and (V[ST[i]]>=V[ST[i-1]])) or (ST[i]>N); if ST[i]<=N then if i=l then Printsol(l) else begin i:=i+1; ST[i]:=0 end else i:=i-1 endend;

begin write('N,k:'); readln(N,k); for i:=1 to N do begin write('V[',i,']='); readln(V[i]) end;

scrie:=true; writeln('Subsirurile crescatoare de lungime ',N div 5,' sunt: '); Bkt(N div 5); sol:=0; scrie:=false; for i:=1 to k do Bkt(i); writeln('Numarul subsirurilor crescatore de lungime <= ',K,' este: ',sol)end.

[ Cuprins ] [ Capitolul

2 ]

Capitolul 2

Recursivitate

Problema 1

Enunþ. Calculaþi recursiv suma a n numere naturale citite.

Rezolvare. Funcþia recursivã Suma calculeazã suma celor n numere. Funcþia primeºte ca parametru k, numãrul de numere care au mai rãmas de citit. Când k=0 se iese din funcþie. În caz contrar, se citeºte de la tastaturã A, un numãr din ºir ºi se adunã la sumã.

program sum;

var n :integer;

function Suma(k:integer):integer;var A:integer;begin if k>0 then begin write('A[',n-k+1,']= '); readln(A); Suma:=A+Suma(k-1) end else Suma:=0;end;

begin write('n= '); readln(n); writeln(Suma(n));end.

Problema 2

Enunþ. Fiind datã o mulþime cu n elemente, numãrul total de partiþii în k clase (k submulþimi) este dat de numerele lui Stirling de speþa a doua S(n,k).

Acestea se definesc recursiv astfel:

S(n,1)=...=S(n,n)=1

S(n+1,k)=S(n,k-1)+kS(n,k)

Sã se calculeze numãrul partiþiilor unei mulþimi cu n elemente.

Rezolvare. Trebuie precizat cã numãrul partiþiilor unei mulþimi este egal cu suma numãrului de partiþii în k clase, dând lui k valori între 1 ºi numãrul de elemente din mulþime.

Funcþia recursivã este întocmai transcrierea formulei recurente.

program Partitii;

var N,k :integer; R :longint;

function Part(n,k:integer):longint;begin if (k=1) or (k=n) then Part:=1 else Part:=Part(n-1,k-1) + k*Part(n-1,k)end;

begin write('N='); readln(N); R:=0; for k:=1 to N do R:=R+Part(N,k); writeln(R)end.

Problema 3

Enunþ. Un numãr natural n, se poate descompune ca sumã unicã de numere naturale. De exemplu, pentru numãrul 4 se scrie descompunerea 2+1+1 (secvenþã descrescãtoare), nu ºi 1+2+1. Prin P(n,m) notãm numãrul de împãrþiri ale lui n ca sumã (unicã) de m numere.

Exemplu:

P(4,2)=2 (4=3+1, 4=2+2).

Numerele P(n,m) verificã relaþia de recurenþã:

P(n,1)+P(n,2)+…+P(n,k)=P(n+k,k);

P(n,1)=P(n,n)=1

Sã se calculeze numãrul total de descompuneri ale numãrului natural n.

Rezolvare.

program Suma;

var N,k :integer; R :longint;

function Min(m1,m2:integer):integer;begin if m1<m2 then Min:=m1 else Min:=m2end;

function P(n,k:integer):longint;var i:integer; r:longint;begin r:=0; if (k=n) or (k=1) then R:=1 else for i:=1 to Min(k,N-k) do R:=R+P(n-k,i); P:=Rend;

begin write('N=');

readln(N); R:=0; for k:=1 to N do R:=R+P(N,k); writeln(R)end.

Problema 4

Enunþ. Se citesc n ºi k (numere naturale n>k). Calculaþi recursiv utilizând formula de recurenþã:

. Este eficient?

Rezolvare. Dupã cum se vede, programul reprezintã întocmai implementarea formulei de recurenþã la

care s-au adãugat douã ramuri: =n ºi =0, dacã k>n.

Pentru a funcþiona corect, orice program (recursiv) bazat pe o relaþie recurentã trebuie sã porneascã de la câteva rezultate cunoscute pentru valori mici ale datelor de intrare. Apoi prin aplicarea succesivã a formulei de recurenþã, orice instanþã a intrãrii trebuie redusã la unul din rezultatele cunoscute. Astfel, orice pereche (n,k) trece în (n-1,k) ºi (n-1,k-1); este evident cã în final perechea (n,k) se va încadra într-una din cele douã ramuri de iniþializare ale formulei de recurenþã (fie n<k, fie k=1).

Acum sã rãspundem la întrebarea dacã programul este eficient. Succesiunii apelurilor recursive i se poate asocia un arbore binar în care fiecare nod este etichetat cu perechea (n,k) corespunzãtoare. Este necesar sã construim doar douã nivele ale arborelui pentru a observa cã etichetele nodurilor nu

sunt distincte (perechea (n-2,k-1) apare de douã ori). Deci pentru a calcula programul va calcula

de douã ori . Dacã mai construim un nivel din arbore vom observa cã este calculat de

ºase ori. Acest coeficient va creºte exponenþial cu numãrul de nivele. Pe cazul general, este

calculat de

Deci programul nostru în nici un caz nu este eficient: pentru o pereche (n,k) de pe parcursul calculului, el va efectua de un numãr de ori exponenþial aceeaºi secvenþã de operaþii.

program Combinari_recursiv;

var N,k :integer;

function Comb(n,k:integer):longint;begin if k=1 then Comb:=n else if k>n then Comb:=0 else Comb:=Comb(n-1,k)+Comb(n-1,k-1)end;

begin write('N,K='); readln(N,K); writeln(Comb(N,K))end.

Problema 5

Enunþ. Scrieþi un program iterativ care rezolvã problema anterioarã utilizând aceeaºi formulã.

Rezolvare. Programul de mai jos rezolvã neajunsurile celui dinaintea sa, ºi anume evitã calcularea de mai multe ori a aceloraºi rezultate. Aceasta se face folosind matricea Comb[n,k] în care se va reþine

valoarea .

Modificarea esenþialã faþã de programul precedent constã în faptul cã apelurile recursive sunt înlocuite cu citiri în matrice. Astfel se înlocuieºte o operaþie consumatoare de timp (numãrul de calcule era exponenþial) cu o operaþie elementarã (acces la matrice).

Ca ºi la varianta recursivã, aici combinãrile se calculeazã pe baza aceluiaºi arbore, care acum este parcurs de "jos în sus". Anume, se pleacã de la valorile cunoscute Comb[i,1]; apoi se aplicã relaþia de recurenþã ºi se obþin valorile pentru Comb[i,2]; cunoscând valorile pentru un anumit N, cele pentru N+1 se obþin prin simpla aplicare a formulei de recurenþã.

program Combinari_iterativ;

var N,K,i,j :integer; Comb :array[0..50,0..50] of longint;

begin write('N,K='); readln(N,K); for i:=0 to N do Comb[i,0]:=1; for i:=1 to N do for j:=1 to k do Comb[i,j]:=Comb[i-1,j-1]+Comb[i-1,j]; writeln(Comb[N,k])end.

Problema 6

Enunþ. Gãsiþi o formulã de recurenþã care sã rezolve eficient problema 4 (recursiv).

Rezolvare.

Program Combinari_recursiv2;

var N,k :integer;

Function Comb(n,k:integer):longint;begin if k=1 then Comb:=N else Comb:=(n-k+1)*Comb(n,k-1) div kend;

begin write('N,k='); readln(N,k);

writeln(Comb(n,k))end.

Calculul celui mai mare divizor comun

a douã numere naturale

Algoritmul lui Euclid

Definiþie: Cel mai mare divizor comun a douã numere întregi u ºi v, notat cmmdc(u,v), este cel mai mare întreg care îl divide atât pe u, cât ºi pe v.

Algoritmul se bazeazã pe urmãtoarea formulã recursivã pentru cmmdc:

Sã demonstrãm acum corectitudinea ecuaþiei cmmdc(u,v)=cmmdc(v,

u mod v). Considerãm cã u=q⋅ v+r (unde q este întreg). Atunci, r=u-q⋅ v ºi cum

r=u mod v => u mod v=u-q⋅ v. Ecuaþia devine: cmmdc(u,v)=cmmdc(v,

u-q*v).

Dacã x este un divizor comun al lui u ºi v, atunci x/(u-q⋅ v). Deci orice divizor comun al lui u ºi v este ºi divizor al lui u-q⋅ v. Analog, orice divizor comun al lui v ºi u-q*v, este divizor al lui u. Rezultã cã cele douã perechi de numere (u,v) ºi (v,u-q*v) au aceiaºi divizori comuni, deci implicit ºi acelaºi cmmdc.

Varianta iterativã a algoritmului se scrie astfel:

while v<>0 do

r:=u mod v (u mod v = restul impartirii lui u la v)

u:=v

v:=r

(la sfârºitul execuþiei programului, valoarea cmmdc se va afla în u)

Vom prezenta acum implementãrile celor douã variante ale algoritmului.

program euclid_iterativ;

var u,v,r:integer;

begin write('u, v: '); readln(u,v); while v<>0 do begin r:=u mod v; u:=v; v:=r end; writeln(u)end.

program euclid_recursiv;

var u,v:integer;

function cmmdc(u,v:integer):integer;begin if v=0 then cmmdc:=u else cmmdc:=cmmdc(v,u mod v);end;

begin write('u, v: '); readln(u,v);

writeln(cmmdc(u,v));end.

Algoritmul binar

Vom prezenta acum un alt algoritm pentru aflarea cmmdc descoperit de Josef Stein în 1961.

Algoritmul binar se bazeazã pe urmãtoarele patru afirmaþii despre douã întregi pozitive u ºi v:

a. Dacã u ºi v sunt pare, atunci cmmdc(u,v)=2cmmdc(u/2,v/2).

b. Dacã u este par ºi v este impar, atunci cmmdc(u,v)=cmmdc(u/2,v).

c. cmmdc(u,v)=cmmdc(u-v,v).

d. Dacã u ºi v sunt impare, atunci u-v este par, ºi |u-v|<max(u,v).

Lãsãm demonstraþia acestor propoziþii în seama cititorului.

Vom schiþa algoritmul iterativ în pseudocod:

k:=0;

while u-par ºi v-par do

u:=u/2; v:=v/2;

k:=k+1

⇒ dupã acest prim pas al algoritmului, cmmdc=2k*cmmdc(u,v), conform afirmaþiei a) ºi cel puþin unul dintre u ºi v este impar.

if v-par then interschimba(u,v)

⇒ dacã unul dintre numere este par, atunci acesta trebuie sã fie u.

repeat

while u-par do

u=u/2

⇒ în urma acestui pas valoarea cmmdc se pãstreazã pentru cã, conform afirmaþiei b), dacã u-par ºi v-impar, cmmdc(u,v)=cmmdc(u/2,v).

if v>u then interschimba(u,v);

⇒ u trebuie sã fie întotdeauna cel mai mare dintre cele douã numere.

u:=u-v

⇒ conform afirmaþiei c), cmmdc(u,v)=cmmdc(u-v,v).

until u=0;

writeln(2k*v)

Vom prezenta acum programele care implementeazã algoritmul binar, în cele douã variante, iterativã ºi recursivã.

Notã: O implementare mai eficientã, ar fi folosit în locul operaþiei x mod 2, operaþia x and 1 ºi în locul operaþiei x div 2, x shr 1. Aceste perechi de operaþii sunt echivalente, dar operaþiile binare "and" ºi "shr" sunt mult mai rapide.

program binar_iterativ;

var u,v,k,r,i:integer;

procedure intersch(var u,v:integer);var aux:integer;begin aux:=u; u:=v; v:=auxend;

begin write('u, v: ');

readln(u,v); k:=0; while (u mod 2=0) and (v mod 2=0) do begin v:=v div 2; u:=u div 2; k:=k+1; end; if v mod 2=0 then intersch(u,v); repeat while u mod 2=0 do u:=u div 2; if v>u then intersch(u,v); u:=u-v until u=0; for i:=1 to k do v:=v*2; writeln(v)end.

program binar_recursiv;

var u,v,k,r,i:integer;

procedure intersch(var u,v:integer);var aux:integer;begin aux:=u; u:=v; v:=auxend;

function cmmdc(u,v:integer):integer;begin if u=0 then cmmdc:=v else if u mod 2=0 then cmmdc:=cmmdc(u div 2,v) else if v>u then cmmdc:=cmmdc(v-u,u) else cmmdc:=cmmdc(u-v,v)end;

begin write('u, v: '); readln(u,v); k:=0; while (u mod 2=0) and (v mod 2=0) do begin v:=v div 2;

u:=u div 2; k:=k+1; end; if v mod 2=0 then intersch(u,v); r:=1; for i:=1 to k do r:=r*2; writeln(cmmdc(u,v)*r)end.

[ Capitolul 1 ]


3 ]

Capitolul 3

Backtracking recursiv

Problema 1

Enunþ. Avem la dispoziþie 6 culori: alb, galben, roºu, verde, albastru ºi negru. Sã se precizeze toate drapelele tricolore care se pot proiecta, ºtiind cã trebuie respectate urmãtoarele reguli:

❍ orice drapel are culoarea din mijloc galben sau verde;

❍ cele trei culori de pe drapel sunt distincte.

Exemple: "alb galben roºu", "roºu verde galben"

Rezolvare. Procedura Back primeºte ca parametru k, nivelul curent al stivei (poziþia în drapel). Dacã se depãºeºte nivelul 3, avem o soluþie ºi aceasta este tipãritã.

Se încearcã aºezarea unei culori pe nivelul curent, dacã este validã. Funcþia booleanã Valid primeºte ca parametrii nivelul curent al stivei (pentru cã acesta nu mai este þinut într-o variabilã globalã) ºi culoarea pentru care se face testul de validitate, i. În cazul în care culoarea este "validã", se apeleazã recursiv procedura Back pentru nivelul urmãtor. Înainte ºi dupã apelare se seteazã corespunzãtor Fol[i].

program drapel;

const Culoare:array [1..6] of string[10]=('alb','galben', 'rosu', 'verde','albastru','negru');

var ST:array [1..3] of integer; Fol:array [1..6] of boolean; k, i:integer;

procedure Printsol;var i:integer;begin for i:=1 to 3 do write(Culoare[ST[i]],' ');

writeln;end;

function Valid(niv,val:integer):boolean;begin if Fol[val] then Valid:=false else if niv<>2 then Valid:=true else if (val=2) or (val=4) then Valid:=true else Valid:=false;end;

procedure Back(k:integer);var i:integer;begin if k>3 then Printsol else for i:=1 to 6 do if Valid(k,i) then begin ST[k]:=i; Fol[i]:=true; Back(k+1); Fol[i]:=false; end;end;

begin for i:=1 to 6 do Fol[i]:=false; Back(1);end.

Problema 2

Enunþ. Sã se descompunã un numãr natural N, în toate modurile posibile, ca sumã de P numere naturale (P≤N).

Rezolvare. Procedura recursivã rezolvã problema pentru o sumã s, reþinând termenii în vectorul solutie începând de pe pozitia k.

Se considerã pe rând toþi termenii între 1 ºi S, care se scad din suma iniþialã, ºi apoi se apeleazã recursiv pentru a rezolva aceeaºi problemã, dar de dimensiuni mai mici.

program Descompuneri;

var N, P, K, S, i :integer; ST :array[1..1000] of integer;

Procedure Back(k,s:integer);var i:integer;begin if (S=0) and (k=p+1) then begin for i:=1 to k-1 do write(ST[i],' '); writeln end else for i:=1 to S do begin ST[k]:=i; Back(k+1,s-i) endend;

begin write('N='); readln(N); write('P='); readln(P); Back(1,N)end.

Problema 3

Enunþ. Dintr-un grup de N persoane, dintre care P femei, trebuie formatã o delegaþie de C persoane, dintre care L femei. Sã se precizeze toate delegaþiile care se pot forma.

Rezolvare. Variabilele Min ºi Max, sunt limitele între care poate lua valori nivelul curent al stivei (explicaþia se gãseºte în Cap. 1, Pr. 3). La trecerea pe nivelul c+1, am ajuns la o soluþie, care se tipãreºte.

program Delegatie;

var ST:array [0..100] of integer; k, c, n, p, l:integer;

procedure Printsol;var i:integer;begin for i:=1 to c do write(ST[i],' '); writeln;end;

procedure Back(k:integer);var i,Min,Max:integer;begin if k>c then Printsol else begin if k<>l+1 then Min:=ST[k-1]+1 else Min:=p+1; if k<=l then Max:=p else Max:=n; for i:=Min to Max do begin ST[k]:=i; Back(k+1); end; end;end;

begin write('n, p, c, l: '); readln(n,p,c,l); ST[0]:=1; Back(1);end.

Problema 4

Enunþ. Se dã un numãr natural par N. Sã se afiºeze toate ºirurile de N paranteze care se închid corect.

Rezolvare. Procedura recursivã Back are trei parametri:

● k, nivelul curent al stivei.

● Nd ºi Ni, numãrul de paranteze deschise, respectiv închise, pânã la poziþia curentã.

program Paranteze;

var ST:array [1..20] of integer; N:integer;

procedure Printsol;var i:integer;begin for i:=1 to N do if ST[i]=1 then write('(') else write(')'); writeln;end;

procedure Back(k,Nd,Ni:integer);begin if k>N then Printsol else begin if Nd<N div 2 then begin ST[k]:=1; Back(k+1,Nd+1,Ni); end; if Ni<Nd then begin ST[k]:=2; Back(k+1,Nd,Ni+1); end endend;

begin write('N= '); readln(N); Back(1,0,0);end.

Problema 5

Enunþ. Fiind dat un numãr natural N, se cere sã se afiºeze toate descompunerile sale ca sumã de numere prime.

Rezolvare.

program Prime;

var ST, Numar :array[0..1000] of integer; N, P, i :integer;

function Prim( X : integer):boolean;var f:integer;begin Prim:=true; f:=2; while f*f<=X do begin if X mod f=0 then begin Prim:=false; exit end; f:=f+1; end;end;

procedure Back(k,s:integer);var i:integer;begin if S=0 then begin for i:=1 to k-1 do write(ST[i],' '); writeln end else begin i:=1; while (Numar[i]<=s) and (i<=p) do begin ST[k]:=Numar[i]; Back(k+1,s-Numar[i]); i:=i+1; end endend;

begin write('N='); readln(N);

P:=0; for i:=2 to N do if Prim(i) then begin P:=P+1; Numar[P]:=i end; Back(1,N)end.

Problema 6

Enunþ. Sã se genereze toate permutãrile de N cu proprietatea cã oricare ar fi

2≤ i≤ N, existã 1≤ j≤ i astfel încât |V(i)-V(j)|=1.

Rezolvare.

program Permutari;

var ST :array [1..20] of integer; n, i :integer; Pus :array [1..20] of boolean;

function Valid(k,v:integer):boolean;var tmp:boolean; i:integer;begin if k=1 then Valid:=true else begin tmp:=false; for i:=1 to k-1 do if abs(V-ST[i])=1 then tmp:=true; Valid:=tmp endend;

procedure Printsol;var i:integer;begin for i:=1 to n do write(ST[i],' '); writelnend;

procedure Back(k:integer);var i:integer;begin if k>n then Printsol else for i:=1 to n do if not Pus[i] and Valid(k,i) then begin ST[k]:=i; Pus[i]:=true; Back(k+1); Pus[i]:=false; end;end;

begin write('N= '); readln(n); for i:=1 to n do Pus[i]:=false; Back(1);end.

Problema 7

Enunþ. Fie Am,n o matrice binarã. Se cunosc coordonatele (i,j) ale unui element, i aparþinând 1...m, j aparþinând 1...n, care are valoarea 1. Sã se gãseascã toate ieºirile din matrice mergând numai pe elementele cu valoarea 1.

Rezolvare.

program Matrice;

const Muta : array[0..4,1..2] of integer= ( (0,0), (-1,0), (1,0), (0,1), (0,-1) );

var N,M,i,j,oi,oj :integer; A :array[0..100,0..100] of integer; ST :array[0..1000] of integer;

procedure Sol(k:integer);var x,y,f :integer;

begin x:=oi; y:=oj; for f:=1 to k do begin write('(',x,',',y,') '); x:=x+Muta[ST[f],1]; y:=y+Muta[ST[f],2] end; writelnend;

function Valid(k,pi,pj:integer):boolean;var i,j :integer;begin i:=pi+Muta[ST[k],1]; j:=pj+Muta[ST[k],2]; Valid:=(i>0) and (j>0) and (i<=M) and (j<=N) and (A[i,j]=1)end;

procedure Back(k,pi,pj:integer);var i:integer;begin A[pi,pj]:=2; if (pi=1) or (pj=1) or (pi=M) or (pj=N) then Sol(k); for i:=1 to 4 do begin ST[k]:=i; if Valid(k,pi,pj) then Back(k+1,pi+Muta[i,1],pj+Muta[i,2]) end; A[pi,pj]:=1end;

begin write('M,N:'); readln(M,N); for i:=1 to M do for j:=1 to N do begin write('A[',i,',',j,']='); readln(A[i,j]) end; write('i,j:'); readln(i,j); oj:=j; oi:=i; A[i,j]:=1;

Back(1,i,j)end.

Problema 8

Enunþ. Se considerã o mulþime de N elemente ºi un numãr natural K nenul. Sã se calculeze câte submulþimi cu k elemente satisfac pe rând condiþiile de mai jos ºi sã se afiºeze aceste submulþimi:

a. conþin p obiecte date;

b. nu conþin nici unul din q obiecte date

c. conþin exact un obiect dat, dar nu conþin un altul

d. conþin exact un obiect din p obiecte date

e. conþin cel puþin un obiect din p obiecte date

f. conþin r obiecte din p obiecte date, dar nu conþin alte q obiecte date.

Rezolvare.

program Submultimi;

var ST, Li, Ls, u :array[0..1000] of integer; N, P, Q, R, K, i :integer; sol :longint; ch :char;

procedure Back(l:integer);var i,b:integer;begin if st[l-1]<Li[l] then b:=Li[l] else b:=st[l-1]; if l=k+1 then begin sol:=sol+1; for i:=1 to K do write(ST[i],' ');

writeln end else for i:=b to Ls[l] do if U[i]=0 then begin ST[l]:=i; U[i]:=1; Back(l+1); U[i]:=0 endend;

begin write('N,K,P,Q:'); readln(N,K,P,Q); write('subpunctul (A,B,C,D,E sau F):'); readln(ch); Case UpCase(ch) of 'A':begin for i:=1 to P do begin Li[i]:=i; Ls[i]:=i end; for i:=P+1 to K do begin Li[i]:=P+1; Ls[i]:=N end end; 'B': for i:=1 to K do begin Li[i]:=Q+1; Ls[i]:=N end; 'C':begin for i:=2 to K do begin Li[i]:=3; Ls[i]:=N end; Li[1]:=1; Ls[1]:=1 end; 'D':begin for i:=2 to K do begin Li[i]:=P+1; Ls[i]:=N end; Li[1]:=1; Ls[1]:=p end; 'E':begin for i:=2 to K do

begin Li[i]:=1; Ls[i]:=N end; Li[1]:=1; Ls[1]:=p end; 'F':begin for i:=1 to R do begin Li[i]:=i; Ls[i]:=P end; for i:=R+1 to K do begin Li[i]:=P+Q+1;Ls[i]:=N end end end; Back(1); writeln('Numar solutii= ',sol)end.

[ Capitolul 2 ]


4 ]

Capitolul 4

Analiza timpului de calcul necesar

algoritmilor

Cãutare binarã

Definim problema cãutãrii:

Se dã un vector A[1..n] ºi o valoare v de acelaºi tip cu elementele din A.

Sã se afiºeze p astfel încât v=A[p] sau 0 dacã nu existã un element cu valoarea v în A.

Cel mai simplu algoritm care rezolvã aceastã problemã este cãutarea liniarã, care testeazã elementele vectorului unul dupã altul, începând cu primul, în cãutarea lui v. Iatã implementarea acestui algoritm:

Gasit_v:=False;p:=0;while not Gasit_v do begin p:=p+1; if v=A[p] then Gasit_v:=True; end;if Gasit_v then writeln(p) else writeln('0');

Sã analizãm complexitatea acestui algoritm pe cazul cel mai defavorabil, acela în care v nu se gãseºte în A. În acest caz se va face o parcurgere completã a lui A. Considerând ca operaþie de bazã testul v=A[p], numãrul de astfel de operaþii de bazã efectuate va fi egal cu numãrul de elemente al lui A, adicã n. Deci complexitatea algoritmului pe cazul cel mai defavorabil este O(n).

Un alt algoritm, mai eficient, este cãutarea binarã. Acest algoritm are însã neajunsul cã necesitã ca vectorul A sã fie sortat crescãtor. Iatã procedura recursivã care implementeazã algoritmul:

procedure caut(i,j:integer);begin m=(i+j) div 2; if v=A[m] then writeln('Valoarea gasita la pozitia: ',m) else if i<j then if v<A[m] then caut(i,m-1) else caut(m+1,j)end;

Procedura primeºte ca parametri i ºi j, limitele porþiunii din vector în care cãutãm. Iniþial procedura este apelatã cu i=1 ºi j=n. m primeºte valoarea (i+j) div 2, adicã indicele elementului din mijlocul lui A[i..j]. Dacã elementul din mijlocul acestei porþiuni, A[m], este chiar valoarea cãutatã, atunci programul se terminã cu afiºarea indicelui acestui element. Dacã v<A[m] înseamnã cã poziþia lui v, dacã se gãseºte în vector, este în stânga lui m, pentru cã vectorul este sortat crescãtor. În acest caz procedura se apeleazã recursiv cu noua porþiune de vector (i..m-1) ca parametru. Analog, dacã v>A[m], procedura se apeleazã recursiv pentru (m+1..j). Dacã se ajunge la i=j, adicã o porþiune de vector de un element, ºi acest element este diferit de v, înseamnã cã v nu se gãseºte în A ºi apelarea recursivã înceteazã datoritã neîndeplinirii condiþiei i<j.

Exemplu:

Sã analizãm complexitatea acestui algoritm pe cel mai defavorabil caz, care este ca ºi la cãutarea liniarã acela în care valoarea cãutatã nu se gãseºte în vector. Considerãm ca operaþie elementarã , o execuþie a procedurii caut. Pentru a determina complexitatea algoritmului, trebuie sã vedem de câte ori se executã procedura caut. Procedura se va apela recursiv pânã când se va ajunge la o porþiune de vector de un element, adicã pânã când i=j. Iniþial procedura este apelatã cu i=1 ºi j=n, mãrimea porþiunii de vector fiind , j-i+1=n. La fiecare apel recursiv, porþiunea de vector se înjumãtãþeºte. La ultimul apel, i=j, deci mãrimea porþiunii va fi i-j+1=1.

Problema este deci, de câte ori se poate împãrþi un numãr natural n la 2, pânã ce câtul împãrþirii va fi 1. Presupunem cã n=2k. La fiecare împãrþire a lui n la 2 exponentul acestuia scade cu o unitate, pânã când câtul împãrþirii va fi 1, adicã n=21. Deci n se poate împãrþi la 2 de k ori. Se demonstreazã uºor

cã acelaºi lucru este valabil ºi dacã 2k<n<2k+1. Dacã n=2k sau 2k<n<2k+1, atunci k=[log2n]. Deci numãrul maxim de execuþii ale procedurii caut ºi implicit, complexitatea algoritmului, este O(log2n).

Logaritmul este o funcþie care creºte mult mai încet decât funcþiile polinomiale. De exemplu, pentru un vector cu n=100000 de elemente, în cazul în care valoarea cãutatã nu se gãseºte în vector, cãutarea liniarã va face n=100000 de operaþii elementare, în timp ce cãutarea binarã va face numai log2n=log2100000=16 operaþii. Dacã n=21000, care are aproximativ 300 de cifre, log2n=1000.

În concluzie, cãutarea binarã este mult mai eficientã decât cea liniarã, dar necesitã ca vectorul sã fie sortat, iar sortarea nu poate fi fãcutã (prin metodele care folosesc comparaþii) într-o complexitate mai bunã de O(n⋅ lg n).

Sortare prin numãrare

Este demonstrat cã metodele de sortare care folosesc ca operaþie de bazã pentru determinarea ordinii elementelor comparaþia (ex. quicksort, heapsort, sortarea prin interclasare, sortarea prin inserþie) nu pot avea o complexitate, pe cel mai defavorabil caz, mai bunã de O(n⋅ lg n). Existã totuºi metode de sortare O(n) care nu folosesc comparaþia elementelor ca operaþie de bazã, o astfel de metodã fiind sortarea prin numãrare.

Ne propunem sã sortãm crescãtor vectorul V, care are n elemente naturale. Definim M ca fiind valoarea maximã din V. Folosim de asemenea, un vector auxiliar A[1..L], unde L≥ M.

Se iniþializeazã A cu 0 ºi apoi se face o parcurgere a vectorului V incrementându-se la fiecare pas A[V[i]], adica elementul din A corespunzãtor valorii elementului curent din V. În urma acestei parcurgeri A[i] va fi numãrul de elemente cu valoarea i din V (respectiv 0, dacã nu existã nici un element cu valoarea i în V).

Se parcurg apoi vectorii A ºi V în paralel, începând cu poziþia 1. Când se întâlneºte un element A[i]>0, se dã valoarea i urmãtoarelor A[i] poziþii din V.

Exemplu:

n=8 V=<7,5,4,5,1,2,4,5> M=7

Prima parcurgere:

i=1, incrementãm A[V[1]]=A[7] ⇒ A=<0,0,0,0,0,0,1>




Procedeul continuã pânã la i=8. În final, A=<1,1,0,2,3,0,1>.

Parcurgem apoi A ºi V în paralel, cu i indicele de parcurgere al lui A ºi j indicele de parcurgere al lui V:

i=1 j=1 A[i]=A[1]=1 ⇒ V[1]:=1

i=2 j=2 A[i]=A[2]=1 ⇒ V[2]:=2

i=3 j=3 A[i]=A[3]=0

i=4 j=3 A[i]=A[4]=2 ⇒ V[3]:=4, V[4]:=4

i=5 j=5 A[i]=A[5]=3 ⇒ V[5]:=5, V[6]:=5, V[7]:=5

i=6 j=8 A[i]=A[6]=0

i=7 j=8 A[i]=A[7]=1 ⇒ V[8]:=7

Rezultã vectorul V sortat: V=<1,2,4,4,5,5,5,7>

Programul constã din douã parcurgeri (nu considerãm ºi parcurgerea pentru iniþializarea vectorului A): una de lungime n ºi una de lungime M, deci complexitatea algoritmului este O(max(n,M)). Spaþiul de memorie folosit pentru vectorii A ºi V este O(M+n). Se observã cã algoritmul nu este practic decât pentru valori mari ale lui n ºi valori relativ mici ale lui M. Altfel, preferãm un algoritm clasic, ca heapsort sau quicksort, a cãrui complexitate este O(n⋅ lg n) ºi spaþiu de memorie O(n). În plus, sortarea prin numãrare are neajunsul cã nu este aplicabilã decât pe vectori cu elemente naturale (sau eventual întregi).

program Sortare_prin_numarare;

const L=200;

var V :array [1..100] of integer; A :array [1..L] of integer; M, n, i, j, k :integer;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=1 to n do begin write('V[',i,']= '); readln(V[i]) endend;

begin Citire; FillChar(A,2*L,0); M:=1; for i:=1 to n do begin if V[i]>V[M] then M:=i; A[V[i]]:=A[V[i]]+1; end; M:=V[M]; j:=0; for i:=1 to M do if A[i]>0 then for k:=1 to A[i] do begin

j:=j+1; V[j]:=i; end; for i:=1 to n do write(V[i],' '); writeln;end.

Ciurul lui Eratostene

Ciurul lui Eratostene este o metodã de determinare a numerelor prime mai mici decât n. Pentru a determina dacã un numãr i este prim sau nu, se testeazã divizibilitatea acestuia cu numerele prime deja determinate (þinute în vectorul Prime), în ordine. Testarea se opreºte dacã i se divide cu unul din numere, sau dacã câtul împãrþirii lui i la numãrul prim respectiv, Prime[j], este mai mic sau egal decât acest numãr prim, caz în care i este prim ºi este adãugat în vectorul Prime.

Demonstraþia corectitudinii algoritmului:

i:Prime[j]=Q (rest R) ⇒ i=Prime[j]⋅ Q+R. Dacã Q≤ Prime[j]⇒ Prime[j]> .

Dacã un numãr i nu are nici un divizor pânã la , atunci i este prim.

Demonstraþia se face prin reducere la absurd: dacã i nu este prim, atunci are cel puþin 2 divizori:

Contradicþie

Complexitatea acestei metode este aproximativ O(n⋅ lg n).

program Eratostene;

var Prime :array [1..13000] of integer; n, NrP, i, j, C, R :integer; Prim, Term :boolean;

begin

write('n= '); readln(n); Prime[1]:=2; Prime[2]:=3; NrP:=2; for i:=4 to n do begin j:=0; Prim:=true; Term:=false; while Prim and not Term do begin j:=j+1; C:=i div Prime[j]; R:=i mod Prime[j]; if R=0 then Prim:=false; if C<=Prime[j] then Term:=true; end; if Prim then begin NrP:=NrP+1; Prime[NrP]:=i; end; end; writeln('Numarul de nr. prime mai mici decit ',n,': ',NrP); for i:=1 to NrP do write(Prime[i],' '); writelnend.

Maxim ºi minim simultan

Problema determinãrii maximului ºi minimului dintr-un vector este, în mod clar, O(n). Considerãm comparaþia ca operaþie de bazã ºi facem douã parcurgeri ale vectorului, una pentru determinarea maximului ºi una pentru determinarea minimului. În total vom avea 2(n-1)=2n-2 comparaþii, deci complexitatea O(n).

Problema poate fi rezolvatã însã, doar cu 3(n/2)-2 comparaþii. Se face o singurã parcurgere a vectorului pentru determinarea simultanã a maximului ºi a minimului. La fiecare pas se comparã o pereche de elemente din vector; apoi cel mai mic dintre ele este comparat cu minimul ºi celãlalt cu maximul. Se fac astfel 3 comparaþii la fiecare pas ºi în total avem n/2 paºi (pentru cã la fiecare pas procesãm o pereche de elemente ºi în total sunt n elemente).

Complexitatea ambelor variante este O(n), dar cea de-a doua este mai eficientã, fãcând acelaºi lucru cu mai puþine comparaþii.

program MinMax;

var A :array [1..100] of integer; Min, Max, Mic, Mare, i, n :integer;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=1 to n do begin write('A[',i,']= '); readln(A[i]) endend;

begin Citire; Min:=1; Max:=1; for i:=1 to (n-1) div 2 do begin if A[2*i]<A[2*i+1] then begin Mic:=2*i; Mare:=2*i+1; end else begin Mic:=2*i+1; Mare:=2*i; end; if A[Mic]<A[Min] then Min:=Mic; if A[Max]<A[Mare] then Max:=Mare; end; if n mod 2=0 then begin if A[n]<A[Min] then Min:=n; if A[Max]<A[n] then Max:=n end; writeln('Minimul: ',A[Min]); writeln('Maximul: ',A[Max])end.

Problema 1

Enunþ. Se dau n întregi: a1, a2,…, an. Sã se afiºeze valoarea expresiei:

Rezolvare. O primã metodã constã în a calcula valoarea tuturor termenilor (produselor) ºi a face suma lor. Sã analizãm complexitatea acestei metode. Considerãm ca operaþie de bazã calcularea valorii unui termen (produs) ºi adunarea lui la suma totalã. Aceastã operaþie va fi efectuatã de un numãr de

ori egal cu numãrul de termeni al sumei. Sã calculãm acum numãrul de termeni al expresiei. Sunt

termeni cu k factori. În total avem termeni în expresie, ceea ce înseamnã, având în vedere operaþia de bazã aleasã, cã complexitatea acestei metode este O(2n), deci o complexitate exponenþialã.

Considerãm polinomul:

.

Coeficienþii acestui polinom sunt exact termenii expresiei noastre, plus 1 (coeficientul lui ). Acest

polinom se poate scrie sub formã de produs ca:

Suma coeficienþilor acestui polinom este exact valoarea expresiei din problema noastrã (minus 1,

coeficientul lui ). Suma coeficienþilor unui polinom este P(1). Rezultã cã valoarea expresiei este

egalã cu -1

Considerând ca operaþie de bazã înmulþirea, complexitatea acestei metode este O(n) pentru cã produsul are n factori, deci se efectueazã n înmulþiri.

Prezentãm acum programele care implementeazã cele douã metode de rezolvare. Primul program (metoda “exponenþialã”) foloseºte o rutinã de generare a combinãrilor (backtracking) pentru calcularea celor 2n termeni. Cel de-al doilea program este pur ºi simplu implementarea formulei de mai sus.

Invitãm cititorul sã ruleze cele douã programe, cu diferite valori ale lui n, pentru a vedea diferenþa la timpul de execuþie. De exemplu, pentru n=20, primul program va efectua 2n=220=1048576 operaþii de bazã, timpul de execuþie fiind de 20 de secunde pe un Pentium la 90MHz, în timp ce al doilea va efectua numai n=20 operaþii, timpul de execuþie fiind insesizabil.

program Expresie_exponential;

var a, ST :array [0..100] of integer; n, nrfact :integer; Suma :longint;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=1 to n do begin write('a[',i,']= '); readln(a[i]); end;end;

procedure Aduna;var Termen :longint; i :integer;begin Termen:=1; for i:=1 to nrfact do Termen:=Termen*a[ST[i]]; Suma:=Suma+Termenend;

procedure Back(k:integer);var i:integer;begin if k>nrfact then Aduna else for i:=ST[k-1]+1 to n do begin ST[k]:=i; Back(k+1) end;end;

begin Citire; Suma:=0; ST[0]:=0; for nrfact:=1 to n do Back(1); writeln(Suma);end.

program Expresie_polinomial;

var a :array [1..100] of integer; n, i :integer; Suma :longint;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=1 to n do begin write('a[',i,']= '); readln(a[i]); end;end;

begin Citire; Suma:=1; for i:=1 to n do Suma:=Suma*(a[i]+1); writeln(Suma-1);end.

Problema 2

Enunþ. Se dau suma X ºi n tipuri de monede având valori de a1, a2,…, an lei. Se cere numãrul modalitãþilor distincte de platã a sumei X utilizând aceste monede.

Exemplu: Pentru X=4, n=3, a1=1, a2=2, a3=4 sunt 4 modalitãþi distincte de platã:

1. 4=1+1+1+1 (cu 4 monede de 1 leu)

2. 4=1+1+2 (cu 2 monede de 1 leu ºi una de 2 lei)

3. 4=2+2 (cu 2 monede de 2 lei)

4. 4=4 (cu 1 moneda de 4 lei)

Metoda I (exponenþialã)

Aceastã metodã foloseºte tehnica backtracking pentru rezolvare.

Rutina recursivã Back primeºte trei parametri: k – nivelul curent al stivei, S – suma elementelor aºezate pânã la nivelul curent în stivã ºi lim – valoarea nivelului k-1 din stivã.

Programul nu foloseºte o stivã explicitã pentru cã nu este nevoie ºi de generarea propriu-zisã a modalitãþilor de platã, ci numai de numãrarea lor. Avem nevoie de variabila S pentru a ºti când avem o modalitate de platã validã, respectiv S=X ºi pentru a opri recurenþa dacã S>X.

Nivelul curent din stivã poate lua valori numai între valoarea nivelului anterior ºi n, pentru a evita duplicarea modalitãþilor de platã, prin forþarea ordinii crescãtoare în stivã. Aceastã valoare a nivelului anterior este transmisã prin variabila lim, tocmai pentru a evita folosirea unui vector-stivã.

Complexitatea acestei metode, fiind vorba de folosirea tehnicii backtracking, este exponenþialã (nu vom prezenta demonstraþia aici întrucât este foarte complexã).

program Suma_exponential;

var a :array [1..100] of integer; X, NrMod, n :integer;

procedure Citire;var i:integer;begin write('X= '); readln(X); write('n= '); readln(n); for i:=1 to n do begin

write('a[',i,']= '); readln(a[i]) endend;

procedure Back(k,S,lim:integer);var i:integer;begin if S=X then NrMod:=NrMod+1 else if S<X then for i:=lim to n do Back(k+1,S+a[i],i);end;

begin Citire; NrMod:=0; Back(1,0,1); writeln(NrMod);end.

Metoda II (pseudo-polinomialã)

Cea de-a doua metodã de rezolvare utilizeazã urmãtoarea formulã de recurenþã:

, unde M(S,i) este numãrul de modalitãþi de platã ale sumei S folosind numai primele i tipuri de monede.

Exemplu: Dacã S=7, i=4 ºi ai=3, trebuie sã calculãm M(7,4) având deja calculate M(x,3), pentru x de la 1 la X.

Conform formulei, M(7,4)=M(7,3)+M(4,3)+M(1,3). Primul termen este numãrul de modalitãþi în care poate fi obþinutã aceeaºi sumã S=7, folosind doar primele 3 tipuri de monede; prezenþa lui în sumã este justificatã prin nefolosirea niciunei monede de tipul i, adicã de 3 lei. Dacã folosim o monedã de tipul i, adicã de 3 lei, se adaugã la sumã numãrul de modalitãþi în care poate fi obþinutã suma S-3=7-3=4, cu primele 3 tipuri de monede. Dacã folosim douã monede de tipul i, se adunã numãrul de modalitãþi în care poate fi obþinutã suma S-6=1, cu primele 3 tipuri de monede, adicã M

(1,3).

Folosind aceastã formulã trebuie sã obþinem M(X,n), adicã numãrul de modalitãþi de platã ale sumei X, cu toate cele n tipuri de monede. Pentru aceasta, folosim doi vectori, M ºi Mant, unde primul reprezintã M(x,i) ºi al doilea M(x,i-1), pentru x de la 1 la X. Calculãm succesiv valoarea lui M din Mant prin formula prezentatã, pânã la obþinerea lui M(X,n).

Complexitatea acestei metode este O(n⋅ X2). Aceasta este o aºa numitã complexitate pseudo-polinomialã, pentru cã nu depinde numai de n.

Dacã valorile monedelor erau numere reale, metoda aceasta nu poate fi aplicatã, problema fiind NP-completã, adicã face parte dintr-o clasã de probleme pentru care nu se cunoaºte o rezolvare polinomialã.

program Suma_pseudopolinomial;

type Vector=array [0..1000] of longint;

var a :array [1..100] of integer; X, S, n, i, k :integer; M, Mant :Vector;

procedure Citire;var i:integer;begin write('X= '); readln(X); write('n= '); readln(n); for i:=1 to n do begin write('a[',i,']= '); readln(a[i]) endend;

begin Citire; FillChar(Mant,2*(X+1),0); FillChar(M,2*(X+1),0); M[0]:=1; Mant[0]:=1; for i:=1 to n do begin

for S:=1 to X do for k:=1 to S div a[i] do M[S]:=M[S]+Mant[S-k*a[i]]; Mant:=M; end; writeln(M[X])end.

Problema 3

Enunþ. Dându-se a ºi x1, x2,…, xn naturale nenule, sã se afiºeze ultima cifrã a numãrului

.

Metoda I

Cea mai simplã metodã de rezolvare ar fi sã-l înmulþim pur ºi simplu pe a cu sine însuºi de x1⋅ …⋅ xn ori. Este limpede însã cã numãrul rezultat ar fi imens chiar ºi pentru valori mici ale lui a, n ºi x1,…, xn.

De exemplu, pentru a=n=10 ºi x1= x2=…= xn=2, va trebui sã calculãm 101024, numãr care are 1024 de cifre. Este clar cã aceastã metodã nu este practicã.

Observãm cã este suficient sã pãstrãm numai ultima cifrã a numãrului la fiecare înmulþire, ba mai mult cã este suficient sã înmulþim numai ultima cifrã a lui a cu ea însãºi de x1⋅ …⋅ xn ori ºi sã pãstrãm de fiecare datã numai ultima cifrã a produsului. Dacã considerãm ca operaþie de bazã înmulþirea, aceastã metodã are complexitatea O(x1⋅ …⋅ xn).

program Cifra_1;

var a, n, C :integer; O, i :longint;

procedure Citire;var i, x :integer;begin write('a= '); readln(a);

a:=a mod 10; write('n= '); readln(n); O:=1; for i:=1 to n do begin write('x[',i,']= '); readln(x); O:=O*x; end;end;

begin Citire; C:=1; for i:=1 to O do C:=C*a mod 10; writeln(C);end.

Metoda II

Cea de-a doua metodã porneºte de la observaþia cã cifra în care se terminã puterile unui numãr se repetã cu o anumitã perioadã. De exemplu, orice putere a unui numãr terminat în cifra 0 se va termina cu cifra 0. La fel ºi pentru numerele terminate în 1, 5 sau 6. Sã vedem ce se întâmplã pentru 7: 7, 49, ..63, ..21, ..7, ..49, ..63,… ºi aºa mai departe. Deci perioada lui 7 este 7, 9, 3, 1. Toate cifrele au perioade de lungime maxim 4, dupã cum se poate vedea în tabelul de mai jos:

K K2 K3 K4 K5

0 0 0 0 0

1 1 1 1 1

2 4 8 6 2

3 9 7 1 3

4 6 4 6 4

5 5 5 5 5

6 6 6 6 6

7 9 3 1 7

8 4 2 6 8

9 1 9 1 9

Este suficient sã reþinem pentru fiecare cifrã perioada (ca în tabelul de mai sus) ºi sã determinãm forma lui x1⋅ …⋅ xn: 4K, 4K+1, 4K+2 sau 4K+3, pentru a ºti cifra în care se terminã puterea respectivã a lui a.

Complexitatea acestei metode este O(n), considerând ca operaþie de bazã înmulþirea.

program Cifra_2;

const Perioada:array [0..9,0..3] of integer= ((0,0,0,0), (1,1,1,1), (6,2,4,8), (1,3,9,7), (6,4,6,4), (5,5,5,5), (6,6,6,6), (1,7,9,3), (6,8,4,2), (1,9,1,9));

var a :integer; O :longint;

procedure Citire;var i, x, n :integer;begin write('a= '); readln(a); a:=a mod 10; write('n= '); readln(n);

O:=1; for i:=1 to n do begin write('x[',i,']= '); readln(x); O:=O*x; end;end;

begin Citire; writeln(Perioada[a,O mod 4]);end.

Probleme propuse:

1. Se dã o secvenþã de numere x1, x2,…, xn. Sã se determine dacã existã un numãr care apare de mai multe ori în aceastã secvenþã.

Complexitate cerutã: O(n⋅ lg n).

Indicaþie: Sortaþi vectorul printr-o metodã de sortare n⋅ lg n ºi apoi comparaþi elementele de pe poziþii consecutive.

2. (Problema evaluãrii unui polinom într-un punct) Se dau n coeficienþi a0, a1,…, an ºi un numãr real x. Calculaþi valoarea lui P(x)=anxn+ an-1xn-1+…+ a1x+ a0.

Ce complexitate are algoritmul banal ? Descrieþi un algoritm O(n) care foloseºte metoda lui Horner de rescriere a unui polinom:

P(x)=(…((anx+an-1)x+an-2)x+…+ a1)x+ a0.

3. Estimaþi timpul de calcul al urmãtorului algoritm (sortarea prin selecþie), pe cazul cel mai favorabil ºi pe cel mai defavorabil:

Se cautã cel mai mic element din vectorul care trebuie sortat, A, ºi se pune pe prima poziþie a unui alt vector B. Apoi se cautã cel mai mic element dintre cele rãmase în A ºi se pune pe poziþia a doua în B. Procedeul continuã pentru restul elementelor.

4. Estimaþi timpul de calcul al sortãrii cu bule (bubble-sort) pe cazurile favorabil ºi defavorabil. Ce algoritm este de preferat, sortarea prin selecþie sau sortarea cu bule ?

Indicaþie: Comparaþi timpii de calcul pe cazul defavorabil ºi favorabil.

5. Se dau doi vectori sortaþi crescãtor X[1..n] ºi Y[1..n] ºi 1≤ i≤ 2n. Sã se gãseascã elementul din X sau Y, care are proprietatea cã este mai mare decât exact i-1 elemente din cele 2n conþinute de cei doi vectori.

Complexitate cerutã: O(lg n)

6. Gãsiþi un algoritm O(n⋅ lg n) care, datã fiind o mulþime M cu n numere reale ºi un alt numãr real x, determinã dacã existã sau nu 2 elemente în M, a cãror sumã este x.

[ Capitolul 3 ]


5 ]

Capitolul 5

Divide et Impera

Problema 1

Enunþ. Un arbore cartezian al unui vector este un arbore binar definit recursiv astfel:

● rãdãcina arborelui este elementul cel mai mic din vector;

● subarborele stâng este arborele cartezian al subvectorului stâng (faþã de poziþia elementului din rãdãcinã);

● subarborele drept este arborele cartezian al subvectorului drept.

Exemplu: Pentru vectorul

I 1 2 3 4 5 6 7 8 9

V[I] 9 8 23 10 16 3 12 4 7

Se pune în rãdãcinã elementul cel mai mic din vector, anume 3. Subarborele stâng este la rândul lui un arbore cartezian al subvectorului V[1..5], iar cel drept al lui V[7..9]. Ca rãdãcinã a subarborelui stâng (adicã fiu stânga al rãdãcinii), alegem elementul minim din V[1..5], adicã V[2]=8. Procedeul continuã recursiv pentru restul vectorului. Iatã arborele rezultat:

Se dã un vector cu n elemente. Sã se afiºeze muchiile arborelui sãu cartezian.

Rezolvare. Pentru construirea arborelui folosim o procedurã recursivã divide(i,j,Tata). Tata este nodul al cãrui subarbore este arborele cartezian al lui V[i..j]. Se determinã Min, indicele elementului minim din V[i..j], ºi se apeleazã recursiv procedura pentru V[i..Min-1] ºi V[Min+1..j].

Exemplu: n=9 V=(9,8,23,10,16,3,12,4,7)

Iniþial procedura se apeleazã cu i=1 ºi j=n=9. Minimul este gãsit pe poziþia Min=6. Se apeleazã recursiv pentru V[i..Min-1], adicã V[1..5], ºi pentru V[Min+1..j], adicã V[7..9], cu parametrul Tata=Min=6.

Analizãm doar primul apel. i=1, j=5, Tata=6. Se gãseºte Min=2. Se afiºeazã muchia (V[Tata],V[Min]), adicã muchia (3,8). Apelãm recursiv pentru V[1..1] ºi V[3..5].

Notã: O rezolvare O(n) a acestei probleme poate fi gãsitã în cartea “Psihologia concursurilor de informaticã” de Cãtãlin Frâncu.

program Arbore_cartezian;

var V :array [1..100] of integer; n :integer; M :array [1..101,1..2] of integer;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=1 to n do begin write('V[',i,']= '); readln(V[i]) end;end;

procedure Divide(i, j, Tata :integer);var k,Min:integer;begin if i<=j then begin

Min:=i; for k:=i+1 to j do if V[k]0 then writeln(V[Min],' ',V[Tata]); Divide(i,Min-1,Min); Divide(Min+1,j,Min); end;end;

begin Citire; writeln('Muchiile arborelui sunt:'); Divide(1,n,0);end.

Problema 2

Enunþ. Se dau un pãtrat ºi un cerc. Se cere sã se calculeze aria lor comunã cu precizie de o zecimalã. Coordonatele se citesc de la tastaturã ºi sunt numere reale. Aria se va afiºa pe ecran.

Prof. dr. Adrian Atanasiu, Paco 1998,

enunþ reformulat

Rezolvare. Distingem trei poziþii relative ale pãtratului faþã de cerc:

● este inclus în cerc;

● este exterior cercului;

● are o suprafaþã în comun cu cercul.

Primele douã cazuri se pot rezolva banal; pentru cazul al treilea vom urmãri sã reducem problema tot la una din situaþiile 1 sau 2. Aplicând strategia generalã Divide et Impera, vom calcula aria comunã dintre pãtrat ºi cerc, împãrþind pãtratul în alte patru mai mici, pentru care vom rezolva aceeaºi problemã. Deoarece “întregul este egal cu suma pãrþilor sale” aria comunã dintre pãtrat ºi cerc va fi egalã cu suma ariilor comune dintre pãtratele în care a fost împãrþit ºi acelaºi cerc.

Totuºi, analiza matematicã ne spune cã aceastã metodã nu va calcula aria exactã, decât dupã un numãr infinit de apeluri recursive. Evident, acest lucru nu este posibil. Deci va trebui sã ne mulþumim cu o aproximare a rãspunsului cãutat: aceasta se face prin renunþarea la o nouã divizare a pãtratului în cazul în care aria acestuia este mai micã decât o constantã. (în program 1e-3=0.001).

Program Cerc_si_Patrat;

var cx,cy,r,x1,y1,x2,y2 :double;

Function Inside(var x,y:double):byte;begin if (sqr(x-cx)+sqr(y-cy)<=r*r) then Inside:=1 else Inside:=0end;

Function Arie(var x1,y1,x2,y2:double):double; Forward;

Function Process(var x1,y1,x2,y2:double):double;var t:byte; r:double;begin r:=abs((x1-x2)*(y1-y2)); t:=Inside(x1,y1)+Inside(x2,y1)+ Inside(x2,y2)+Inside(x1,y2); if (t in [1..3]) and (r>1e-3) then r:=Arie(x1,y1,x2,y2) else if t<>4 then r:=0; Process:=rend;

Function Arie(var x1,y1,x2,y2:double):double;var mx,my :double;begin mx:=(x1+x2)/2; my:=(y1+y2)/2; Arie:=Process(x1,y1,mx,my)+Process(mx,y1,x2,my)+ Process(mx,my,x2,y2)+Process(x1,my,mx,y2)end;

begin write('Cerc (x,y,r):'); readln(cx,cy,r); write('Patrat (x1,y1,x2,y2):'); readln(x1,y1,x2,y2); writeln(Arie(x1,y1,x2,y2):0:4)end.

Problema 3

Enunþ. Se dã o tablã de dimensiuni 2nx2n. Pe aceastã tablã existã o gaurã la poziþia (Lg,Cg). Pentru acoperirea acestei table avem la dispoziþie piese de forma:

Aceste piese pot fi rotite cu 90, 180 sau 270° . Se cere sã se afiºeze o acoperire completã a tablei (cu excepþia gãurii). Pe fiecare linie se vor afiºa 6 valori separate prin spaþii:

l1 c1 l2 c2 l3 c3, reprezentând coordonatele pãtratelor din care este formatã fiecare piesã aºezatã pe tablã.

Olimpiada de Informaticã Bucureºti

Faza pe sector – 1995

Rezolvare. Procedura recursivã Acopera primeºte ca parametrii:

● o bucatã de tablã prin (L1,C1) – coordonatele pãtratului din colþul stânga-sus de pe tablã, ºi (L2,C2) coordonatele pãtratului din colþul dreapta-jos.

● coordonatele gãurii de pe aceastã bucatã de tablã, (Lg,Cg).

Urmând strategia generalã Divide et Impera, la fiecare nivel descompunem problema curentã în 4 subprobleme, dupã care apelãm procedura recursivã pentru fiecare din ele. Împãrþim tabla în 4 bucãþi egale. Una dintre aceste 4 bucãþi are deja o gaurã în ea. În celelalte trei bucãþi facem câte o gaurã prin aºezarea unei piese la îmbinarea bucãþilor, ca în figurã.

Dacã se ajunge la o bucatã 2x2 se opreºte apelarea recursivã; se aºeazã o piesã pe cele 3 pãtrate libere (un pãtrat fiind gaurã) ºi se revine din apel.

Exemplu:

N=3 Lg=3 Cg=6

Notãm cele 4 sferturi ale pãtratului cu cifre:

În sfertul 3 avem deja gaura iniþialã. Pentru a face o gaurã ºi în celelalte trei sferturi aºezãm o piesã la îmbinarea lor, ca mai jos:

Afiºãm coordonatele piesei pe care am aºezat-o ºi apelãm recursiv pentru cele 4 subprobleme:

program Luri;

var Lg,Cg,n,i :integer; L :longint;

procedure Citire;begin write('n= '); readln(n);

write('Lg, Cg: '); readln(Lg,Cg);end;

procedure Acopera(L1,C1,L2,C2:longint;Lg,Cg:integer);var Ml,Mc:longint;begin Ml:=(L1+L2) div 2; Mc:=(C1+C2) div 2; if (Lg>Ml) and (Cg>Mc) then begin writeln(Ml+1,' ',Mc,' ',Ml,' ',Mc,' ',Ml,' ',Mc+1); if L2-L1>1 then begin Acopera(L1,C1,Ml,Mc,Ml,Mc); Acopera(L1,Mc+1,Ml,C2,Ml,Mc+1); Acopera(Ml+1,C1,L2,Mc,Ml+1,Mc); Acopera(Ml+1,Mc+1,L2,C2,Lg,Cg) end; end else if (Lg>Ml) and (Cg<=Mc) then begin writeln(Ml,' ',Mc,' ',Ml,' ',Mc+1,' ',Ml+1,' ',Mc+1); if L2-L1>1 then begin Acopera(L1,C1,Ml,Mc,Ml,Mc); Acopera(L1,Mc+1,Ml,C2,Ml,Mc+1); Acopera(Ml+1,C1,L2,Mc,Lg,Cg); Acopera(Ml+1,Mc+1,L2,C2,Ml+1,Mc+1) end end else if (Lg<=Ml) and (Cg>Mc) then begin writeln(Ml,' ',Mc,' ',Ml+1,' ',Mc,' ',Ml+1,' ',Mc+1); if L2-L1>1 then begin Acopera(L1,C1,Ml,Mc,Ml,Mc); Acopera(L1,Mc+1,Ml,C2,Lg,Cg); Acopera(Ml+1,C1,L2,Mc,Ml+1,Mc); Acopera(Ml+1,Mc+1,L2,C2,Ml+1,Mc+1) end end else begin writeln(Ml+1,' ',Mc,' ',Ml+1,' ',Mc+1,' ',Ml,' ',Mc+1); if L2-L1>1 then begin

Acopera(L1,C1,Ml,Mc,Lg,Cg); Acopera(L1,Mc+1,Ml,C2,Ml,Mc+1); Acopera(Ml+1,C1,L2,Mc,Ml+1,Mc); Acopera(Ml+1,Mc+1,L2,C2,Ml+1,Mc+1) end end;end;

begin Citire; L:=1; for i:=1 to n do L:=L*2; Acopera(1,1,L,L,Lg,Cg);end.

Problema 4

Enunþ. Pentru codificarea unei imagini de pe ecranul calculatorului, imagine presupusã pãtraticã de dimensiuni 2nx2n, se poate folosi aºa-numitul cod Oliver & Wiseman, care îi ataºeazã un arbore în felul urmãtor (imaginea fiind construitã folosind 16 culori numerotate de la 0 la 15): dacã toþi pixelii au aceeaºi culoare, atunci arborele conþine un singur nod (nodul rãdãcinã) care are asociatã culoarea pixelilor respectivi; în caz contrar, imaginea se împarte în patru pãrþi egale, de câte 2n-1x2n-1 pixeli, iar arborii corespunzãtori acestor patru imagini vor fi subarbori ai nodului rãdãcinã. Nodului rãdãcinã i se va asocia valoarea -1 (fãrã semnificaþie de culoare), iar cele patru pãrþi vor fi parcurse în sensul:

1 2 3 4

Procedeul se repetã apoi separat pentru fiecare parte, pânã se obþin bucãþi de aceeaºi culoare. Sã considerãm acum o imagine datã într-un fiºier sub formã de matrice, fiecare element reprezentând culoarea pixelului de pe linia ºi coloana corespunzãtoare. Imaginea este de dimensiuni 2nx2n, n fiind dat în prima linie din fiºier (imagine.in).

Se cere sã se construiascã arborele corespunzãtor imaginii date; afiºarea arborelui se va face într-un fiºier text arbore.out sub forma datã în exemplul de mai jos:

Fiºier de intrare:2 7271

7737 14777977

Fiºier de ieºire:

-1

├── -1│ ├──7│ ├──2│ ├──7│ ├──7│ └──7├── -1│ ├──7│ ├──1│ ├──3│ └──7├── -1│ ├──1│ ├──4│ ├──7│ └──9└── 7

prof. Clara Ionescu Baraj, august 1994,

enunþ modificat

Rezolvare. Aplicarea principiului Divide et Impera este deja descrisã chiar în enunþ. Dificultatea poate consta în implementarea acestui tip de afiºare. Trebuie folositã o stivã, în program este chiar ºirul s, pentru a memora câte rânduri de linii verticale trebuie afiºate, la momentul curent al recursivitãþii.

Program Imagine;

var fil :text; n,i,j,k :integer; s :string; a :array[0..201,0..201] of byte;

Procedure Print(x1,y1,x2,y2:integer);

var f,mx,my:integer;begin f:=0; for i:=y1 to y2 do begin for j:=x1 to x2 do if a[i,j]<>a[y1,x1] then begin f:=1; break end; if f=1 then break; end; if f=0 then writeln(fil,a[y1,x1]) else begin writeln(fil,' -1'); mx:=(x1+x2) div 2; my:=(y1+y2) div 2; write(fil,s,'+¦'); s:=s+'- '; Print(x1,y1,mx,my); write(fil,s,'+¦'); s:=s+'- '; Print(mx+1,y1,x2,my); write(fil,s,'+¦'); s:=s+'- '; Print(x1,my+1,mx,y2); write(fil,s,'L '); s:=s+' '; Print(mx+1,my+1,x2,y2) end; dec(byte(s[0]),3)end;

begin assign(fil,'imagine.in'); reset(fil); readln(fil,n); n:=1 shl n; for i:=1 to n do begin for j:=1 to n do read(fil,a[i,j]); readln(fil) end; close(fil); assign(fil,'arbore.out'); rewrite(fil); Print(1,1,n,n); close(fil)end.

[ Capitolul 4 ]


6 ]

Capitolul 6

Structuri de date

Algoritmul lui Tarjan

Se dã un pointer cãtre capãtul unei liste simplu înlãnþuite. Se cere sã se spunã dacã aceastã listã cicleazã, folosindu-se spaþiu de memorie O(1).

O listã simplu înlãnþuitã cicleazã dacã unul din elemente pointeazã cãtre un element anterior lui din listã. O listã care nu cicleazã se va termina cu elementul NIL.

O rezolvare simplã ar fi sã marcãm elementele parcurse din listã. Dacã întâlnim un element marcat înseamnã cã lista cicleazã. Dezavantajul acestei metode este cã necesitã spaþiu de memorie O(n), unde n este lungimea listei.

Prezentãm un algoritm descoperit de R.E. Tarjan care necesitã memorie O(1). Acest algoritm foloseºte pentru parcurgerea listei doi pointeri: P1 ºi P2. Cei doi pointeri “aratã” iniþial cãtre primul element din listã. P2 se “miºcã” de douã ori mai repede decât P1. Adicã la fiecare pas, P1 se mutã la elementul urmãtor din listã în timp ce P2 se mutã cu douã elemente. Algoritmul se terminã dacã P2 ajunge la sfârºitul listei (la elementul NIL), caz în care lista nu cicleazã, sau dacã P2 îl “ajunge din spate” pe P1, caz în care lista are un ciclu. Timpul de calcul este O(n).

program Tarjan;

type nod=^nod;

var L, P1, P2 :nod;

begin { Initializeaza lista } P1:=L; P2:=L^; while (P2<>P1) and (P2<>nil) do begin P2:=P2^; if (P2<>nil) and (P2<>P1) then P2:=P2^; if (P2<>P1) then P1:=P1^; end; if P2=nil then writeln('Lista nu cicleaza') else writeln('Lista cicleaza');end.

În continuare vom prezenta o implementare bazatã pe obiecte a principalelor structuri de date studiate în manual.

Lista dublu înlãnþuitã

Lista proiectatã în programul de mai jos este conceputã sã foloseascã, pentru informaþia utilã din nod, orice structurã creatã de utilizator. Anume, programatorul îºi va putea construi propriul tip de date, cu oricâte câmpuri ºi de orice dimensiuni, ºi va putea folosi obiectul nostru pentru a gestiona o listã cu înregistrãri de acest tip de date. Singura restricþie este ca primele douã câmpuri din informaþia din nod sã fie cei doi pointeri pentru referinþa la nodul urmãtor respectiv, anterior.

Obiectul lista implementeazã toate operaþiile elementare definite pentru aceastã structurã de date: inserþie, cãutare, ºtergere, parcurgere (numele metodelor sunt mai mult decât asemãnãtoare). Datoritã generalizãrii sunt necesare câteva “intervenþii” ale utilizatorului: în primul rând, pentru a putea folosi obiectul, trebuie apelat constructorul Dim ce primeºte ca parametru lungimea în bytes a informaþiei din nod (aceasta include ºi cei doi pointeri). Pentru folosirea metodei Cauta este necesarã precizarea în

prealabil a unei funcþii pentru compararea a douã noduri, aceasta realizându-se printr-un apel al metodei SetFunc. Evident utilizatorul poate crea mai multe astfel de funcþii, care sã compare înregistrãrile dupã diferite câmpuri ºi sã le foloseascã alternativ, apelând SetFunc la fiecare schimbare a funcþiei de comparare. De asemenea, pentru parcurgerea listei este necesarã precizarea unei proceduri care va fi apelatã primind ca parametru, pe rând, fiecare înregistrare din listã.

Unit ListaDef;

interface

type ComparFunc = Function (var a,b):boolean; ProcessProc = Procedure (var v); Lista = Object prim,urm :pointer; ds :integer; comp :ComparFunc; Constructor Dim(v:integer); Procedure SetFunc(v:pointer); Procedure Adauga(var data); Procedure Parcurge(v:pointer); Procedure ParcurgeInv(v:pointer); Function Cauta(var data) :pointer; Procedure Sterge(v:pointer); end;

implementation

type leg = record next, prev : pointer; end;

Constructor Lista.Dim(v:integer);begin ds:=v; prim:=nil; comp:=nil; urm:=nilend;

Procedure Lista.SetFunc(v:pointer);begin

comp:=ComparFunc(v)end;

Procedure Lista.Adauga(var data);var t :pointer;begin getmem(t,ds); Move(data,t^,ds); leg(t^).next:=nil; leg(t^).prev:=urm; if urm<>nil then leg(urm^).next:=t else prim:=t; urm:=tend;

Function Lista.Cauta(var data):pointer;var t:pointer;begin if @comp=nil then begin Cauta:=nil; exit end; t:=prim; while (t<>nil) and (not Comp(t^,data)) do t:=pointer(t^); Cauta:=tend;

Procedure Lista.Parcurge(v:pointer);var t:pointer;begin t:=prim; while t<>nil do begin ProcessProc(v)(t^); t:=pointer(t^) endend;

Procedure Lista.ParcurgeInv(v:pointer);var t:pointer;begin t:=urm; while t<>nil do begin ProcessProc(v)(t^); t:=leg(t^).prev endend;

Procedure Lista.Sterge(v:pointer);begin

if leg(v^).next<>nil then leg(leg(v^).next^).prev:=leg(v^).prev else urm :=leg(v^).prev;

if leg(v^).prev<>nil then leg(leg(v^).prev^).next:=leg(v^).next else prim:=leg(v^).next; dispose(v)end;

end.

Sã dãm un exemplu: crearea ºi actualizarea unei agende telefonice. Întâi vom defini structura de date necesarã.

uses ListaDef;

type ref =^telefon; Telefon =record next,prev :ref; Nume :string[20]; numar :longint; end;var Agenda :Lista; Tmp :Telefon;

Pentru crearea listei este necesar apelul constructorului Dim ºi apoi inserarea succesivã în listã a înregistrãrilor:

Begin Agenda.Dim(sizeof(Telefon)); repeat write('Nume:'); readln(tmp.nume); write('Numar:'); readln(tmp.numar); Agenda.Adauga(tmp) until tmp.nume='';end.

Acum sã vedem cum se realizeazã implementarea unei parcurgeri a listei. Utilizatorul îºi va defini o procedurã ce se va ocupa cu procesarea fiecãrui element din listã (în cazul nostru va face doar o afiºare) ºi apoi o va transmite metodei Parcurge:

Procedure Print(v:telefon);begin writeln(v.Nume:25,' ',v.numar:10)end;

begin{ . . . } Agenda.Parcurge(@Print);{ . . . }end.

Sã presupunem cã unul dintre cunoscuþii noºtri tocmai ºi-a schimbat numãrul de telefon. Vom fi nevoiþi sã cãutãm întregistrarea corespunzãtoare în listã ºi sã modificãm unul dintre câmpuri. Deoarece cãutarea se face dupã numele respectivului, funcþia construitã de utilizator pentru a compara douã înregistrãri va verifica doar dacã cele douã nume conincid:

Var p :ref;

Function ComparNume(a,b:telefon):boolean;begin ComparNume:=(a.nume=b.nume)end;

begin{ . . . } Agenda.SetFunc(@ComparNume); tmp.nume:='Cunoscut'; { aici pui numele pe care-l cauþi } p:=Agenda.Cauta(tmp); p^.Numar:=89 { ºi aici noul numãr }{ . . . }end.

Un mare avantaj pe care-l prezintã aceastã implementare este independenþa de structura folositã

pentru informaþia dintr-o înregistrare. Astfel, dupã ce aceastã aplicaþie a fost în totalitate scrisã, dacã apare nevoia modificãrii structurii telefon (de exemplu adãugarea unui câmp pentru memorarea adresei), aceasta se poate rezolva fãrã a fi nevoie de alte modificãri în sursã: se adaugã pur ºi simplu în definiþie noul câmp ºi se scrie codul necesar pentru procesarea lui.

Matricea rarã

O matrice rarã este o matrice, în general de dimensiuni mari, în care majoritatea elementelor au valoarea 0. Deoarece informaþia utilã propriu-zisã este de dimensiuni mult mai mici decât ale matricei, de cele mai multe ori este ineficient sã folosim alocarea staticã (se consumã prea multã memorie). Obiectul MatriceRara prezentat mai jos, realizeazã o implementare bazatã pe liste simplu înlãnþuite: pentru fiecare rând al matricei se þine o listã a valorilor nenule pe care le conþine.

Exemplu: matricea

0 1 0 9 0 0 0 6

0 0 0 0 0 0 0 0

0 0 0 0 0 5 0 0

0 0 4 0 0 0 4 4

2 0 0 0 7 0 0 0

va fi reþinutã astfel (prima valoare din fiecare pereche reprezintã coloana pe care se aflã valoarea ºi cea de-a doua valoarea propriu-zisã) :

1: (2,1),(4,9),(8,6)2: 3: (6,5)4: (3,4),(7,4),(8,4)5: (1,2),(5,7)

Cele douã metode care implementeazã operaþiile fundamentale pentru matrice (Citeste ºi Scrie)

oferã utilizatorului posibilitatea de a accesa matricea ca ºi cum ar fi fost alocatã static. Metoda Scrie are în sarcinã actualizarea listelor, realizând: inserarea unui nou element în listã pe poziþia corespunzãtoare (dacã elementul se gãseºte deja în listã este actualizat), ºtergerea din listã a elementelor care primesc valoarea zero.

unit MatrDef;

interface

type ref = ^nod; nod = record c : integer; info : real; next : ref end;

MatriceRara = Object l : array[1..10000] of ref; Constructor Init; Function Citeste(x,y:integer):real; Procedure Scrie (x,y:integer;v:real); end;

implementation

Constructor MatriceRara.Init;begin fillchar(l,sizeof(l),0)end;

Function MatriceRara.Citeste(x,y:integer):real;var t:ref;begin t:=l[x]; while (t<>nil) and (t^.c>nil) and (t^.c=y) then Citeste:=t^.info else Citeste:=0end;

Procedure MatriceRara.Scrie (x,y:integer;v:real);var t,p,d :ref;begin t:=L[x]; p:=nil; while (t<>nil) and (t^.c>nil) and (t^.c=y) then

if v<>0 then t^.info:=v else begin if p=nil then L[x]:=t^.next else p^.next:=t^.next; dispose(t) end else begin if v=0 then exit; new(d); d^.next:=t; d^.c:=y; d^.info:=v; if p=nil then L[x]:=d else p^.next:=d endend;

end.

Probleme propuse:

1. Sã se determine, folosind obiectul MatriceRara, componentele conexe ale unui graf dat prin matricea de adiacenþã.

2. Sã se realizeze obiectele Stiva ºi Coada prin moºtenirea obiectului Lista.

[ Capitolul 5 ]


7 ]

Capitolul 7

Tehnica Greedy

Problema 1

Enunþ. Într-un depozit al monetãriei statului sosesc n saci cu monezi. ªeful depozitului cunoaºte numãrul de monezi din fiecare sac ºi ar vrea sã modifice conþinutul sacilor, prin mutãri de monezi dintr-un sac în altul, astfel încât în final, în fiecare sac sã fie acelaºi numãr de monezi. Ajutaþi ºeful depozitului sã obþinã acelaºi numãr de monezi în fiecare sac, prin efectuarea unui numãr minim de mutãri.

Date de intrare:

În fiºierul text MONEZI.IN se va scrie pe prima linie un numãr întreg n (2≤ n≤ 2000), reprezentând numãrul de saci. Pe urmãtoarele n linii sunt scrise numere întregi, reprezentând numerele de monezi din fiecare sac (numãrul total de monezi din toþi sacii≤ 1.000.000.000).

Date de ieºire:

Pe fiecare linie a fiºierului text MONEZI.OUT se vor scrie triplete de numere întregi

a b c unde:

● a reprezintã numãrul de ordine al sacului din care se mutã monezi;

● b reprezintã numãrul de ordine al sacului în care se mutã monezi;

● c reprezintã numãrul de monezi care se mutã din sacul a în sacul b.

Observaþie: În cazul în care problema nu are soluþie, se va scrie în fiºier cuvântul: ‘NU’.

Exemplu:

MONEZI.IN MONEZI.OUT

3 35 48 37

22 1 52 3 3

Timp maxim de execuþie: 8 secunde.

Olimpiada Naþionalã de Informaticã 1998

Clasa a X-a

Rezolvare. Dacã suma numãrului de monezi din toþi sacii nu este divizibilã cu numãrul de saci, atunci problema nu are soluþie. Altfel, calculãm media numãrului de monezi din saci în variabila Med, adicã numãrul de monezi pe care va trebui sã îl aibã fiecare sac în final.

Pentru a reþine numãrul de monezi din fiecare sac, folosim o listã dublu înlãnþuitã, unde fiecare nod conþine, pe lângã pointerii necesari, doi întregi, reprezentând indicele sacului în ordinea iniþialã ºi numãrul de monezi din sac.

Iatã algoritmul folosit pentru rezolvare:

❍ se eliminã din listã sacii care au deja Med monezi

❍ apoi, atâta timp cât lista nu este vidã,

❍ se mutã atâtea monezi din sacul cel mai plin în cel mai gol, cât este nevoie pentru a rãmâne Med monede în acesta din urmã

❍ se afiºeazã mutarea fãcutã

❍ se eliminã din listã sacul în care am pus monede ºi, dacã în sacul din care am pus monede au rãmas Med monede, se eliminã ºi acesta

Trebuie precizat cã algoritmul este euristic, adicã soluþia datã de el nu este întotdeauna cea optimã.

Pentru implementare folosim obiectul Lista definit în capitolul “Structuri de date”.

{$F+} (* Aceastã directivã de compilare este necesarã pentru transmiterea ca parameteri a adreselor de proceduri *)

program Suma;

uses ListaDef;

type ref=^Nod; Nod=record next, prev:ref; i, mon: integer end;

var L :Lista; outp :text; Med :integer; Min, Max :ref;

procedure Citire;var tmp: Nod; i, n, suma :integer; f:text;begin L.Dim(sizeof(Nod)); assign(f,'monezi.in'); reset(f); readln(f,n); suma:=0; for i:=1 to n do begin tmp.i:=i; readln(f,tmp.mon); suma:=suma+tmp.mon; L.Adauga(tmp) end; if suma mod n<>0 then begin writeln(outp,'NU'); close(outp); halt(1) end else Med:=suma div n; close(f);end;

procedure Del(var N:nod);begin if N.mon=Med then L.Sterge(@N);

end;

procedure MinMax(var N:nod);begin if N.monMax^.mon then Max:=@N;end;

begin assign(outp,'monezi.out'); rewrite(outp); Citire; L.Parcurge(@Del); while L.prim<>nil do begin new(Max);new(Min); Max^.mon:=0; Min^.mon:=maxint; L.Parcurge(@MinMax); writeln(outp,Max^.i,' ',Min^.i,' ',Med-Min^.mon); Max^.mon:=Max^.mon-(Med-Min^.mon); L.Sterge(Min); if Max^.mon=Med then L.Sterge(Max); end; close(outp)end.

Problema 2

Enunþ. Pentru plata unei sume S avem la dispoziþie n tipuri de monede, printre care ºi moneda cu valoarea 1. Sã se gãseascã o modalitate de platã a sumei cu un numãr minim de monede.

Rezolvare. Algoritmul folosit este foarte simplu. Se ia moneda cu valoarea cea mai mare ºi se foloseºte de câte ori este posibil. Apoi moneda cu valoarea imediat urmãtoare ºi aºa mai departe.

Exemplu: S=13 n=3 M1=7 M2=3 M3=1

Se foloseºte moneda M1 de S div M1=13 div 7=1 ori.

Apoi M2 de S div M2=6 div 2=3 ori.

Am gãsit o modalitate de platã cu 4 monede: S=13=7+2+2+2.

Algoritmul folosit nu conduce tot timpul la soluþia optimã, dar este foarte eficient. Putem gãsi uºor un

contraexemplu: S=17 n=3 M1=7 M2=5 M3=1 , soluþia algoritmului va avea 5 monede: S=17=7+7+1+1+1, în timp ce soluþia optimã are numai 3 monede: S=17=7+5+5.

Programul constã dintr-o sortare ºi o parcurgere a vectorului de monede. Complexitatea algoritmului este O(n⋅ lg n+n)=O(n⋅ lg n).

program Plata_sumei;

var M, F :array [1..100] of integer; S, n, i :integer;

procedure Citire;var i:integer;begin write('S= '); readln(S); write('n= '); readln(n); for i:=1 to n do begin write('M[',i,']= '); readln(M[i]) endend;

procedure QuickSort(li, ls: integer);var i, j, x, y: integer;begin i := li; j := ls; x := M[(li+ls) div 2]; repeat while M[i] > x do i := i + 1; while x > M[j] do j := j - 1; if i <= j then begin y := M[i]; M[i] := M[j]; M[j] := y; i := i + 1; j := j - 1; end; until i > j; if li < j then QuickSort(li, j); if i < ls then QuickSort(i, ls);end;

begin

Citire; QuickSort(1,n); FillChar(F,2*n,0); i:=0; while S>0 do begin i:=i+1; F[i]:=S div M[i]; S:=S-M[i]*F[i] end; writeln('Am folosit: '); for i:=1 to n do writeln(F[i],' monede de ',M[i],' lei');end.

Problema 3

Enunþ. Sã se umple perfect o tablã de dimensiuni nxn (n≥ 6) cu piese de urmãtoarele forme:

Este obligatoriu sã se foloseascã cel puþin o piesã din fiecare tip.

Prof. Gheorghe Petrov – Universitatea Timiºoara

Concursul Naþional de Informaticã Lugoj 1998

Rezolvare. Vom face întâi observaþia cã nxn trebuie sã fie multiplu de 4 pentru cã toate cele 7 piese sunt formate din câte 4 pãtrãþele. Rezultã cã pentru a putea face acoperirea n trebuie sã fie par.

Iatã o aºezare a pieselor prin care putem umple perfect un pãtrat de 6x6, folosind cel puþin o piesã de fiecare tip:

Se aºeazã acest pãtrat 6x6 în colþul din stânga-sus al tablei. Apoi, ne rãmân pe tablã neumplute douã dreptunghiuri de dimensiuni 6x(n-6), respectiv (n-6)xn, dupã cum se vede în figurã:

Aceste douã dreptunghiuri, având amândouã dimensiunile pare, pot fi umplute numai cu pãtrate (piesa 3).

program TETRIS;

const Colt:array [1..6,1..6] of integer= ((2,2,4,4,4,7), (2,1,1,4,4,7), (2,6,1,4,4,7),

(6,6,1,2,4,7), (6,5,5,2,3,3), (5,5,2,2,3,3));

var n, i, j :integer; T :array [1..100,1..100] of integer;

begin write('n= '); readln(n); for i:=1 to 6 do for j:=1 to 6 do T[i,j]:=Colt[i,j]; for i:=7 to n do for j:=1 to n do begin T[i,j]:=3; T[j,i]:=3; end; for i:=1 to n do begin for j:=1 to n do write(T[i,j],' '); writeln endend.

Problema 4

Enunþ. Se dau n ºi k, naturale, k≤ n. Sã se construiascã un tablou nxn care îndeplineºte simultan condiþiile:

1. conþine toate numerele de la 1 la n2 o singurã datã;

2. pe fiecare linie numerele sunt aºezate în ordine crescãtoare, de la stânga la dreapta;

3. suma elementelor de pe coloana k sã fie minimã.

Rezolvare. Fiecare din elementele de pe coloana k trebuie sã fie mai

mare decât cele k-1 elemente de pe linia sa. Rezultã, cã suma minimã a elementelor de pe coloana k

este . Numerele de la 1 la nk se aºeazã în A[1..n,1..k] , în ordine.

program Tablou;

var T :array [1..100,1..100] of integer; n, k, i, j :integer;

begin write('n, k: '); readln(n,k); for i:=1 to n do for j:=1 to k do T[i,j]:=(i-1)*k+j; for i:=1 to n do for j:=k+1 to n do T[i,j]:=(i-1)*k+j-k+T[n,k]; for i:=1 to n do begin for j:=1 to n do write(T[i,j],' '); writeln endend.

Problema 5

Enunþ. Se dau n puncte în plan. Sã se construiascã, dacã este posibil, un poligon convex care sã aibã ca vârfuri aceste puncte.

Rezolvare. Pentru ca un segment (Pi,Pj) sã fie laturã a unui poligon convex trebuie ca toate celelalte puncte sã se gãseascã într-unul din semiplanele determinate de dreapta-suport a segmentului.

Folosim un vector boolean Puse, unde Puse[i] este True dacã am ales deja vârful I, ºi False, altfel.

La fiecare pas al algoritmului alegem un vârf al poligonului j, dacã:

● Puse[j]=False, adicã acest vârf nu trebuie sã fi fost deja ales

● Latura(P[i-1],j])=True, unde Latura(i,j) este procedura care verificã dacã toate celelalte puncte sunt într-unul din semiplane cu ajutorul ecuaþiei dreptei PiPj ºi P[i-1] este ultimul punct ales.

Dacã nu se gãseºte un astfel de punct, rezultã cã nu se poate forma un poligon

convex cu punctele date.

Notã: Acest algoritm are complexitatea O(n3). O metodã mai eficientã de rezolvare ar folosi un algoritm de determinare a înfãºurãtorii convexe, având complexitatea O(n⋅ lg n).

program Poligon;

type Punct=record X,Y:real end;

var V :array [1..100] of Punct; n, i, j :integer; Puse :set of 1..100; P :array [1..100] of integer; Convex :boolean;

procedure Citire;var f:text; i:integer;begin assign(f,'input.txt'); reset(f); readln(f,n);

for i:=1 to n do readln(f,V[i].X,V[i].Y); close(f);end;

function Sgn(P1,P2,P3:Punct):integer;var s:real;begin s:=(P3.X-P1.X)*(P2.Y-P1.Y)-(P3.Y-P1.Y)*(P2.X-P1.X); if s<0 then Sgn:=-1 else if s>0 then Sgn:=1 else Sgn:=0;end;

function Latura(p1,p2:integer):boolean;var s,i:integer; bun,pr:boolean;begin pr:=true; i:=0; bun:=true; while (i>p1) and (i<>p2) then if pr then begin s:=Sgn(V[p1],V[p2],V[i]); pr:=false end else if Sgn(V[p1],V[p2],V[i])<>s then bun:=false; end; Latura:=bun;end;

begin Citire; P[1]:=1; Puse:=[1]; Convex:=true; i:=1; while (in) and not Convex do begin j:=j+1; if not (j in Puse) and Latura(P[i-1],j) then begin Convex:=true; Puse:=Puse+[j]; P[i]:=j;

end; end; end; if Convex then begin write('Poligonul:'); for i:=1 to n do write(' ',P[i]); writeln; end else writeln('Nu se poate forma un poligon convex.');end.

Problema 6

Enunþ. Se dã un polinom P(X) cu coeficienþi întregi. Sã se afle toate rãdãcinile raþionale ale polinomului.

Rezolvare. Rezolvarea se bazeazã pe urmãtoarea teoremã:

Fie f=a0+a1X+…+anXn un polinom de gradul n (n≥ 1) cu coeficienþi întregi. Dacã (p, q numere prime între ele) este o rãdãcinã raþionalã a lui f atunci:

1. p divide termenul liber a0;

2. q divide coeficientul termenului de grad maxim an.

Demonstraþia acestei teoreme poate fi gãsitã în manualul de Algebrã, clasa a X-a.

Sã observãm cã cele douã condiþii de mai sus, sunt necesare, dar nu neapãrat ºi suficiente pentru ca r sã fie rãdãcinã a polinomului. De aceea, dupã determinarea numerelor raþionale care satisfac aceste douã condiþii trebuie sã ºi verificãm dacã chiar sunt rãdãcini ale polinomului. Aceastã verificare

se face în procedura Rãdãcinã(p,q) care practic calculeazã .

program Polinom;

var a :array [0..100] of integer; p, q, n :integer;

procedure Citire;var i:integer;begin write('n= '); readln(n); for i:=0 to n do begin write('a',i,'= '); readln(a[i]); end;end;

function cmmdc(u,v:integer):integer;begin if v=0 then cmmdc:=u else cmmdc:=cmmdc(v,u mod v);end;

function Radacina(p,q:integer):boolean;var suma, X :real; i:integer;begin X:=1; suma:=a[0]; for i:=1 to n do begin X:=X*(p/q); suma:=suma+a[i]*X; end; if abs(suma)<1e-5 then Radacina:=true else Radacina:=false;end;

begin Citire; p:=1; while p*pa[n] do begin repeat q:=q+1; until a[n] mod q=0;

if (cmmdc(p,q)=1) and Radacina(p,q) then writeln(p,'/',q); end; end;end.

[ Capitolul 6 ]


8 ]

Capitolul 8

Programare dinamicã

Problema 1

Enunþ. Câte cuvinte de lungime N se pot forma cu litere din alfabetul {a,b,c,d} astfel încât a ºi b sã nu se afle pe poziþii alãturate ?

Ioan Tomescu – Probleme de combinatoricã ºi teoria grafurilor

Rezolvare. Sã considerãm cã am construit deja un cuvânt de lungime N-1, care respectã condiþiile problemei. Un cuvânt valid de lungime N se poate obþine adãugând la sfârºitul celui pe care-l avem deja:

● litera a,c sau d, dacã cuvântul se terminã cu a

● litera b,c sau d, dacã cuvântul se terminã cu b

● orice literã dacã cuvântul se terminã cu c sau d

Se observã cã numãrul de cuvinte obþinute prin adãugarea unei litere variazã în funcþie de litera adãugatã dar ºi de ultima literã a cuvântului de la care se porneºte. Vom nota cu A[i] numãrul de cuvinte de lungime i care se terminã în a sau b, ºi cu C[i] numãrul de cuvinte care se terminã în c sau d. Deducem urmãtoarele relaþii de recurenþã:

A[N] = A[N-1] + 2 * C[N-1]

C[N] = 2 * A[N-1] + 2 * C[N-1]

De aici pânã la implementare mai e doar un pas …

Program Cuvinte;

var N,i :integer; A,C :array[0..100] of comp;

begin write('N='); readln(N); A[1]:=2; C[1]:=2;

for i:=2 to N do begin C[i]:=2*C[i-1]+2*A[i-1]; A[i]:=A[i-1] +2*C[i-1] end; writeln(A[N]+C[N]:20:0)end.

Problema 2

Enunþ. Titlul de "Campioanã Absolutã" al unei discipline sportive este disputat de douã echipe cu forþã de joc egalã. Pentru desemnarea campioanei, federaþia de specialitate a hotãrât organizarea unui turneu în care între cele douã echipe sã aibã loc mai multe partide ºi sã fie declaratã campioanã, echipa care câºtigã prima, n partide.

Analiºtii sportivi sunt interesaþi în estimarea ºansei pe care o are una dintre echipe la un moment dat oarecare al turneului, de a deveni campioanã.

Echipele sunt desemnate cu numerele 1 ºi 2. Orice partidã se terminã cu victoria uneia dintre echipe. În orice partidã, cele douã echipe au ºanse egale de câºtig indiferent de rezultatele din partidele anterioare.

ªtiindu-se situaþia turneului la un moment dat, ºi anume numarul i de partide câºtigate de prima echipã ºi numãrul j de partide câºtigate de a doua echipã, sã se calculeze probabilitatea ca echipa 1 sã câºtige turneul ºi sã devinã campioanã.

Fiºierul de intrare conþine pe fiecare linie câte un set de date sub formã de triplete "n i j", unde n reprezintã numãrul de partide ce trebuie câºtigate pentru a deveni campioanã (n≤45), i numãrul de partide câºtigate de echipa 1, iar j numãrul de partide câºtigate de echipa 2.

Pentru fiecare set de date trebuie afiºatã probabilitatea ca echipa 1 sã devinã campioanã, cu patru zecimale exacte.

Exemplu:

Daca fiºierul de intrare are urmãtorul conþinut:

3 3 13 1 35 3 32 1 0

Ieºirea trebuie sã arate ca mai jos:

1.00000.00000.50000.7500

Rezolvare. Pentru a câºtiga, echipa 1 are nevoie de n-i victorii din cele n-i-j meciuri rãmase. Secvenþei de n-i-j meciuri îi vom asocia un arbore binar strict, astfel: fiecare nod va reprezenta numãrul de meciuri necesare fiecãrei echipe pentru a câºtiga turneul. Un nod (i,j) va avea ca descendenþi nodul (i-1,j), dacã echipa unu câºtigã meciul, mai fiindu-i necesare i-1 victorii, ºi nodul (i,j-1) dacã echipa unu pierde.

ªtiind cã echipele au ºanse egale rezultã cã în oricare fiu se poate ajunge cu o probabilitate de 0,5. Deci probabilitatea ca echipa unu sã câºtige turneul din nodul (i,j) va fi egalã cu suma probabilitãþilor din nodurile fii înmulþitã cu 0,5.

Program Probabil;

var n,i,j,x,y :integer; p :array[0..45,0..45] of real; fil :text;

begin for i:=1 to 45 do p[0,i]:=1; for i:=1 to 45 do p[i,0]:=0; for i:=1 to 45 do for j:=1 to 45 do p[i,j]:=(p[i-1,j]+p[i,j-1])/2; assign(fil,'campion.in'); reset(fil);

while not eof(fil) do begin readln(fil,n,i,j); writeln(P[n-i,n-j]:4:4) end; close(Fil)end.

Problema 3

Enunþ. Mai multor elevi li se cere sã punã într-o anumitã ordine un numãr de n<200 cuvinte formate numai din litere mici; ordinea exprimã faptul cã aceste cuvinte se succed dupã o anumitã logicã.

Exemplu:

platon kant marx stalin havel

Logica succesiunii constã în faptul cã fiecare cuvânt poate fi definit folosind numai cuvintele anterioare .

Fiecare elev îi transmite profesorului succesiunea de cuvinte care i se pare logicã. Sarcina profesorului constã în a acorda fiecãrui elev una din notele 1,2,3..,n corespunzãtoare numãrului de cuvinte aºezate într-o succesiune corectã.

Pentru exemplul 1 avem urmãtoarele note :

marx stalin kant platon havel 3

havel marx stalin kant platon 2

havel stalin marx kant platon 1

Fiºierul de intrare platon.in va avea urmãtoarea formã:

● Pe prima linie apar cuvintele în succesiunea lor corectã, despãrþite între ele prin cel puþin un blank;

● Pe urmãtoarele linii apar soluþiile propuse de elevi.

Programul va afiºa pe ecran notele acordate de profesor.

Rezolvare. “Numãrul de cuvinte aºezate într-o succesiune corectã” este echivalent cu numãrul maxim de cuvinte care pot fi extrase din ºir, pãstrând relaþia de ordine între ele, ºi care se gãsesc în aceeaºi succesiune ºi în ºirul corect. Adicã un subºir crescãtor maximal, întocmai problema studiatã în manual.

Pentru a reduce problema exact la forma studiatã, vom numerota cuvintele în ordinea corectã cu numerele de la 1 la N. Deci fiecãrui cuvânt îi este asociat în mod unic un numãr. Pentru fiecare ºir de examinat vom construi ºirul corespunzãtor al numerelor asociate cuvintelor; acesta va fi reþinut în vectorul A. Lungimea subºirului crescãtor maximal din acest ºir, reprezintã întocmai nota acordatã de profesor.

Exemplu:

platon kant marx stalin havel 1 2 3 4 5

Pentru a evalua succesiunea havel marx stalin kant platon, îi vom asocia ºirul 5,3,4,2,1. Subºirul crescãtor maximal care se poate forma este 3,4; deci nota corespunzãtoare va fi 2.

Program Filozofi;

var fil :text; Nume :array[1..200] of string[20]; A,V :array[0..200] of integer; N,i,j :integer; c :char; tmp :string;

Function GetWord:string;var r:string;begin r:=''; read(fil,c); while c=' ' do read(fil,c); while (c<>' ') and (not eoln(fil)) do begin r:=r+c; read(fil,c) end; if c<>' ' then r:=r+c; GetWord:=rend;

begin assign(fil,'platon.in'); reset(fil); N:=0; while not eoln(fil) do begin inc(N); Nume[N]:=GetWord end; readln(fil);

while not eof(fil) do begin for i:=1 to N do begin tmp:=GetWord; j:=1; while tmp<>Nume[j] do inc(j); A[i]:=j end; readln(fil); for i:=1 to N do V[i]:=1; for i:=2 to N do for j:=1 to i-1 do if (A[j]<A[i]) and (V[j]+1>V[i]) then V[i]:=V[j]+1; j:=1; for i:=1 to N do if V[i]>j then j:=V[i]; writeln(j) end; close(fil)end.

Problema 4

Enunþ. Un subºir al unui ºir X1,X2,…,Xn este un ºir care se obþine ºtergând zero sau mai multe elemente din ºirul iniþial. Elementele care se ºterg nu trebuie sã fie neapãrat pe poziþii consecutive în ºir. De exemplu: 2,3,2,1 este un subºir al ºirului 2,4,3,1,2,1 el obþinându-se prin ºtergerea lui 4 ºi a primei apariþii a lui 1 în ºirul iniþial.

Dându-se douã ºiruri X1,X2,…,Xn ºi Y1,Y2,…,Ym un subºir comun a celor douã ºiruri este un ºir care este subºir ºi pentru primul ºir ºi pentru al doilea. Problema constã în a gãsi un subºir de lungime maximã a douã ºiruri date.

Rezolvare. Sã presupunem cã ºtim deja cel mai lung subºir comun al celor douã ºiruri de lungime N ºi respectiv M. Sã studiem ce se întâmplã cu acesta în cazul în care se mai adaugã elemente celor douã ºiruri. În cel mai simplu caz, dacã se adaugã acelaºi element la sfârºitul ambelor ºiruri, este evident cã lungimea subºirului comun va creºte cu 1 (elementul adãugat fãcând parte din cele douã ºiruri va apãrea ºi în subºir comun).

De exemplu, dacã avem ºirurile 4,7,9,3 ºi 1,4,2,9,5,6 cel mai lung subºir comun va fi 4,9. Dacã adãugãm un 8 în finalul ambelor ºiruri, noua soluþie va fi 4,9,8. În cazul în care se adaugã un singur element la sfârºitul unuia din ºiruri se poate întâmpla, sau nu, ca lungimea subºirului comun sã creascã cu 1:

Exemple:

1) 1,2,3,7 ºi 1,2,4 cu subºirul comun 1,2

Dacã adãugãm un 3 la ºirul al doilea noul subºir comun va deveni 1,2,3

2) 1,7,2 ºi 1,4,2 cu subºirul comun 1,2

Orice element am adãuga, la oricare ºir, subºirul comun va pãstra aceeaºi lungime.

Întotdeauna, situaþia din exemplul 1 se poate reduce la cazul în care am adãugat acelaºi element la ambele ºiruri: elementele situate dupã ultima valoare din subºirul comun pot fi ignorate (în exemplu doar 7 este în aceasã situaþie), obþinând astfel douã ºiruri ce au acelaºi ultim element.

Dacã notãm cu A[i,j] lungimea celui mai lung subºir comun care se poate forma folosind doar primele i elemente ale primului ºir ºi primele j elemente ale celui de-al doilea ºir, obþinem urmãtoarea relaþie de recurenþã:

A[i,j] = 1 + A[i-1,j-1] dacã X[i]=Y[j], = Max ( A[i-1,j], A[i,j-1] ) altfel

Program SubsirComun;

var X,Y :array[1..100] of integer; A :array[0..100,0..100] of integer; N,M,i,j,k :integer;

Function Max(m1,m2:integer):integer;begin if m1>m2 then Max:=m1 else Max:=m2end;

Procedure Print(i,j:integer);begin while X[i]<>Y[j] do if A[i-1,j]>A[i,j-1] then dec(i) else dec(j); if A[i-1,j-1]>0 then Print(i-1,j-1); write(X[i],' ')end;

begin write('N='); readln(N); for i:=1 to N do begin write('X[',i,']='); readln(X[i]) end; write('M='); readln(M); for i:=1 to M do begin write('Y[',i,']='); readln(Y[i]) end;

fillchar(A,sizeof(A),0); for i:=1 to N do for j:=1 to M do if X[i]=Y[j] then A[i,j]:=A[i-1,j-1]+1 else A[i,j]:=Max(A[i-1,j],A[i,j-1]);

writeln(A[N,M]); Print(N,M); writelnend.

Problema 5

Enunþ. Se considerã mulþimea formatã din numerele naturale mai mici sau egale decât N (N≤ 39). O astfel de mulþime se poate partiþiona în douã submulþimi care au aceeaºi sumã. De exemplu, dacã N=3, mulþimea {1,2,3} se poate împãrþi în {1,2} ºi {3}. Se cere sã se calculeze numãrul de astfel de partiþionãri ºtiind cã nu are importanþã ordinea mulþimilor dintr-o soluþie ({1,2} ºi {3} reprezintã aceeaºi soluþie ca {3} ºi {1,2}).

Fiºierul de intrare input.txt conþine pe prima linie numãrul N.

Ieºirea se va face în output.txt ºi va consta în numãrul de partiþionãri.

Exemplu:

Pentru N=7, sunt patru soluþii:

{1,6,7} ºi {2,3,4,5}

{2,5,7} ºi {1,3,4,6}

{3,4,7} ºi {1,2,5,6}

{1,2,4,7} ºi {3,5,6}

USACO, Spring Open 1998

Rezolvare. Problema este analogã cu problema rucsacului.

Vom þine un vector S[i] de dimensiune egalã cu suma maximã care se poate obþine într-o submulþime adicã jumãtate din suma primelor N numere naturale, deci N*(N-1)/4. S[i] va reprezenta numãrul de moduri în care se poate obþine suma i (trebuie remarcat cã în situaþia în care suma primelor N numere este imparã, este imposibil sã formãm douã submulþimi cu sume egale, deci numãrul de soluþii va fi 0).

Vectorul S este iniþializat cu 0, doar S[0] va primi valoarea 1. Vectorul va fi completat progresiv, la fiecare etapã considerându-se un nou numãr, i care va spori numãrul de soluþii obþinute folosindu-le doar pe primele i-1.

De exemplu, dacã pânã la etapa curentã avem S[5]=3 ºi S[9]=8, iar i=4 (am gãsit deja 3 moduri de a forma suma 5 ºi 8 de a forma suma 9) atunci putem sã adãugãm numãrul 4 la oricare din cele 3 soluþii gãsite pentru suma 5, ºi vom obþine încã 3 soluþii cu suma 9. Deci numãrul de modalitãþi de a forma suma 9 va creºte exact cu numãrul de sume gãsite pentru 5: S[9]=S[9]+S[5].

Program Submultimi;

var fil :text; N,i,j,k :integer; S :array[0..1000] of comp;

begin fillchar(S,sizeof(S),0); assign(fil,'INPUT.TXT'); reset(fil); readln(fil,N); close(fil); assign(fil,'OUTPUT.TXT');

rewrite(fil);

k:=(N*N+N) div 2; if odd(k) then begin writeln(fil,0); close(fil); halt end;

S[0]:=1; for i:=1 to N do for j:=k-i downto 0 do if S[j]<>0 then S[j+i]:=S[j+i]+S[j];

writeln(fil,S[k div 2]/2:0:0); close(fil)end.

Problema 6

Enunþ. Pentru o mulþime datã de K numere prime S={p1,p2,... pK}, sã considerãm mulþimea tuturor numerelor ale cãror factori primi formeazã o submulþime a lui S. Ea conþine de exemplu printre altele numerele p1, p1p2, p1p1, p1p2p3 (când K≥3).

Aceasta este mulþimea "numerelor subjugate" pentru mulþimea de intrare S. Vom considera aceastã mulþime ordonatã crescator: {H1,H2, .. }.

Atenþie: prin definiþie 1 este declarat un numãr nesubjugat.

Problema cere sã se afle al N-lea numãr subjugat HN pentru o mulþime datã S.

Fiºierul de intrare (humble.in) conþine douã linii:

K N

p1 p2 .. pK

Limite: 1≤ K≤ 100, 1≤ N≤10.000.

Ieºirea se va face pe ecran ºi va consta într-un singur numãr, HN.

Exemplu:

Pentru intrarea:

4 192 3 5 7

Ieºirea este:27

USA Computing Olympiad, Aprilie 1997

Rezolvare. Vom genera în ordine primele N numere subjugate. Acestea vor fi reþinute în vectorul V. Sã presupunem cã cunoaºtem deja primele i numere subjugate ºi ne intereseazã sã-l aflãm pe cel cu numãrul de ordine i+1. Pornind de la cele pe care le cunoaºtem, putem sã înmulþim fiecare din cele i numere subjugate cu fiecare din cele k numere prime. Astfel vom obþine încã i⋅ k numere subjugate, ºi în mod sigur cel de-al i+1 –lea (pe care-l cãutãm) se va gãsi printre ele. Deci dintre toate numerele generate în ultima etapã îl vom pãstra pe cel mai mic dintre ele care este mai mare decât V[i] (al i-lea numãr subjugat).

Pentru a optimiza acest proces de calculare a urmãtorului numãr subjugat, vom þine seama de urmãtoarea observaþie: ºtim cã numerele din V sunt sortate ºi, deci, dacã le vom înmulþi pe toate cu acelaºi numãr prim, pj vom obþine, tot un ºir de valori sortate crescãtor; dintre acestea cel mult unul poate candida la poziþia V[i+1], ºi anume cel mai mic, mai mare decât V[i]. Deci vom mai folosi încã un vector pi[j] care va memora indicele celui mai mic numãr subjugat, care înmulþit cu pj va da o valoare mai mare decât V[i]. Evident, acest vector va trebui actualizat la fiecare selecþie a unui nou numãr subjugat.

Program Numere_subjugate;

var fil :text; N,K,i,j,f,min :longint; p :array[1..100] of integer; V :array[0..10000] of longint; pi :array[1..100] of longint;

begin assign(fil,'HUMBLE.IN'); reset(fil); readln(fil,K,N); for i:=1 to K do read(fil,P[i]); close(fil);

v[0]:=1; for i:=1 to K do pi[i]:=0; for i:=1 to N do begin min:=maxlongint; for j:=1 to K do if V[pi[j]]*P[j] < min then Min:=V[pi[j]]*P[j]; V[i]:=min; for j:=1 to K do while V[pi[j]]*P[j]<=V[i] do inc(pi[j]) end;

writeln(V[N])end.

Problema 7

Enunþ. Se construieºte un limbaj nou, având urmatoarele elemente:

● un sistem format din n stãri, n ≤ 200.● un alfabet, format din caractere litere mici din alfabetul englez;

● o stare iniþialã;

● o mulþime de stãri finale;

● o funcþie care descrie evoluþia stãrilor în funcþie de caracterele introduse în alfabet.

Un ºir de caractere formeazã un cuvânt, al limbajului descris mai sus, dacã pornind de la starea iniþialã, urmãrind funcþia de evoluþie se ajunge la o stare finalã.

Cerinþe:

Datele de intrare se citesc din:

- fiºierul diction.txt având urmãtoarea structurã:

nc1 c2 c3 ... cr

i k1 k2 k3 ... kl

s1,1 ... s1,i1

s2,1 ... s2,i2

sn*r,1 ... sn*r,in*r

numãrul de stãri; reprezentând caracterele alfabetului, despãrþite prin spaþiu; numãrul de ordine al stãrii iniþiale; 1 ≤ i ≤ n numãrul de ordine al stãrilor finale, numere naturale despãrþite prin spaþiu; 0 < l ≤ n; pe urmãtoarele n*r linii se descrie funcþia de evoluþie astfel: - pe primlele n linii pentru c1 evoluþia prin cele n stãri, ºamd.

- "0" desemneazã mulþimea vidã

- fiºierul cuvinte.txt conþine pe m linii cuvinte:cuvânt_1cuvânt_2....cuvânt_m În fiºierul cuvinte.txt se vor introduce cuvinte formate doar din caracterele permise (cele introduse în diction.txt).

Datele de ieºire se scriu în fiºierul limbaj.txt, care are structura:

- Pe m linii se scrie YES sau NO, dupã cum cuvântul de pe linia corespunzãtoare este sau nu cuvânt al limbajului realizat.

Exemplu:

diction.txt: cuvinte.txt4 abba b aabaa1 aaab3 4 bbb2 3 4 abaa0431 32 401

Fiºierul de ieºire este limbaj.txt:

YESYESNOYESYES

Timp maxim de execuþie: 10 sec/test, pentru 586/133MHz.

Prof. Maria ºi Adrian Niþã. Prof. Aniko Sos

Liceul Teoretic "Emanuil Gojdu" Oradea

Rezolvare. Deci: “funcþia” primeºte ca parametri starea curentã ºi un caracter, iar rezultatul este tot o stare care poate fi aleasã arbitrar din lista corespunzãtoare parametrilor primiþi (citim n⋅ r linii cu stãri). Funcþia va fi memoratã în matricea A: A[i,j]^[k] va fi starea cu indicele k din lista corespunzãtoare rezultatelor funcþiei pentru parametrii i ºi j (i este stare, j este caracter). A[i,j]^[0] va fi egal cu numãrul de rezultate posibile ale funcþiei pentru parametrii i,j (corespunde valorilor i1, i2, … , in*r din schema de intrare). Stãrile finale vor

fi memorate în vectorul sf.

Pentru a testa un cuvânt vom folosi doi vectori auxiliari, s1 ºi s2. Aceºtia vor fi completaþi într-un numãr de etape egal cu lungimea cuvântului. Dupã i etape, s1,2[j] va fi egal cu 1 dacã, pornind din starea iniþialã, existã un

drum de lungime i care sã aducã sistemul în starea j. Deci, la etapa 0 vom avea doar s1[stare iniþialã]=1, celelalte valori din vector fiind iniþializate cu 0; la etapa 1 se parcurge vectorul s1 ºi pentru fiecare valoare de 1 întâlnitã, se completeazã în s2 toate stãrile în care funcþia poate ajunge având ca parametri : starea corespunzãtoare valorii 1, ºi caracterul din cuvânt egal cu numãrul etapei, adicã 1. În final s2 este copiat în s1

pentru a putea efectua aceleaºi operaþii ºi la etapa urmãtoare.

Dupã ce s-a parcurs întreg cuvântul, rãspunsul îl gãsim prin simpla verificare a stãrilor finale în vectorul s1: dacã cel puþin uneia din stãrile finale îi corespunde în s1 o valoare 1 atunci, cuvântul face parte din limbaj.

Program Limbaj;

type vec=array[0..200] of byte;

var fil,fo :text; N,i,j,si,nf,r,f :integer; s :string; c :char; A :array[1..200,'a'..'z'] of ^vec; sf,tmp,s1,s2 :vec;

begin assign(fil,'DICTION.TXT'); reset(fil); readln(fil,N); while not seekeoln(fil) do begin read(fil,c); while c=' ' do read(fil,c); s:=s+c end; readln(fil,si); nf:=0; r:=length(s); while not seekeoln(fil) do begin inc(nf); read(fil,sf[nf]) end; readln(fil);

fillchar(A,sizeof(A),0); for i:=1 to r do for j:=1 to n do begin f:=0; while not eoln(fil) do begin inc(f); read(fil,tmp[f]) end; getmem(A[j,s[i]],f+1); move(tmp,A[j,s[i]]^,f+1); if (f=1) and (tmp[1]=0) then A[j,s[i]]^[0]:=0

else a[j,s[i]]^[0]:=f; readln(fil) end; close(fil);

assign(fil,'CUVINTE.TXT'); reset(fil); assign(fo, 'LIMBAJ.TXT'); rewrite(fo); while not seekeof(fil) do begin readln(fil,s); fillchar(s1,sizeof(s1),0); s1[si]:=1; for i:=1 to length(s) do begin fillchar(s2,sizeof(s2),0); for j:=1 to N do if (s1[j]=1) and (A[j,s[i]]<>nil) then for f:=1 to A[j,s[i]]^[0] do s2[A[j,s[i]]^[f]]:=1; s1:=s2 end;

f:=0; for i:=1 to nf do if s2[sf[i]]=1 then f:=1; if f=1 then writeln(fo,'YES') else writeln(fo,'NO') end; close(fil); close(fo)end.

Problema 8

Enunþ. Se considerã o mulþime ordonatã de ºiruri de N biþi. Biþii, evident, pot lua valoarea 1 sau 0. Mulþimea conþine toate ºirurile posibile de N biþi care au cel mult L biþi de 1. Vi se cere sã tipãriþi al C-ulea ºir de biþi din aceastã mulþime, în ordinea datã de numerele în baza 10 ce corespund ºirurilor de biþi.

Intrare:

Fiºierul input.txt conþine trei numere întregi separate printr-un spaþiu: N, L ºi C.

Ieºire:

Fiºierul output.txt va conþine o singurã linie, cu un singur numãr, anume al C-ulea ºir de biþi din mulþime.

Exemplu:

input.txt:

5 3 19

output.txt:

10100

USACO, Spring Open 1998

Rezolvare. Vom calcula o matrice M cu urmãtoarea semnificaþie: M[i,j] este egal cu numãrul de ºiruri de i biþi, care au cel mult j biþi de 1. Presupunând cã cunoaºtem toate valorile acestei matrici pentru indici mai mici decât i ºi j, dorim sã calculãm M[i,j]. Un ºir de i biþi evident va fi obþinut prin adãugarea unui bit la un ºir de i-1 biþi. Dacã bitul adãugat este 1 rezultã cã în ºirul de i-1 pot fi maxim j-1 biþi de 1, deoarece în total trebuie sã avem maxim j biþi de 1. În schimb dacã adãugãm un bit 0, în ºirul de lungime i-1, se pot afla cel mult j biþi de 1. Deci rezultã formula de recurenþã: M[i,j]=M[i-1,j-1]+M[i-1,j].

Biþii din ºirul cãutat vor fi deduºi, începând cu cel mai semnificativ, folosind urmãtorul raþionament: dacã pe poziþia curentã am aºeza un bit de 1, atunci ar mai rãmâne N-1 biþi de aflat dintre care L-1 biþi 1, iar noul C, actualizat pentru restul ºirului de biþi, ar avea valoarea C-M[N-1,L] (aceasta deoarece noul nostru ºir va conþine doar L-1 biþi de 1, deci toate ºirurile cu L biþi de 1 trebuie eliminate). Deci valoarea din C va evolua pe parcursul determinãrii biþilor, indicând în fiecare moment, al câtelea ºir trebuie gãsit folosind doar Ni biþi din care

doar Li de 1. Deoarece C trebuie sã fie în permanenþã mai mare decât zero ºi mai mic decât M[Ni,Li] rezultã

cã de fiecare datã când C-M[N-1,L] este mai mare decât zero va trebui sã aºezãm un bit 1, în caz contrar valoarea din C va depãºi numãrul maxim de ºiruri care se pot crea în condiþiile rezultate (adicã: punând un bit 0, C va rãmâne constant depaºind astfel valoarea M[Ni-1,Li-1]).

Program Bizzi;

var M :array[0..32,0..33] of comp; N,L,i,j :longint; C :comp; fil :text;

begin assign(fil,'INPUT.TXT'); reset(fil); read(fil,N,L,C); close(fil);

fillchar(M,sizeof(M),0); for i:=0 to N do begin M[i,0]:=1; M[0,i]:=1 end; for i:=1 to N do begin for j:=1 to i do M[i,j]:=M[i-1,j]+M[i-1,j-1]; for j:=i+1 to N do M[i,j]:=M[i,i] end;

assign(fil,'OUTPUT.TXT'); rewrite(fil); j:=L; for i:=N downto 1 do if C>M[i-1,j] then begin write(fil,1); C:=C-M[i-1,j]; dec(j) end else write(fil,0); writeln(fil); close(fil)end.

[ Capitolul 7 ]


9 ]

Capitolul 9

Branch and Bound

Problema 1

Enunþ. Se considerã un pãtrat cu NxN cãsuþe. Fiecare cãsuþã conþine un numãr între 1 ºi N*N-2. Douã cãsuþe sunt ocupate cu numãrul 0. Fiecare numãr natural, diferit de 0, apare o singurã datã în cadrul pãtratului. ªtiind cã 0 îºi poate schimba poziþia cu orice numãr aflat deasupra, la dreapta, la stânga sau jos, în raport cu poziþia în care se aflã numãrul 0, se cere sã se precizeze ºirul de mutãri prin care se poate ajunge de la o configuraþie iniþialã la o configuraþie finalã. Se cere de asemenea ca acest ºir sã fie optim, în sensul cã trebuie sã se ajungã la configuraþia finalã într-un numãr minim de mutãri.

Rezolvare. Reluãm aici problema pãtratului, discutatã ºi în manual, pentru a familiariza cititorul cu o nouã modalitate de implementare a tehnicii Branch and Bound, modalitate ce va fi folositã ºi în celelalte rezolvãri. Evident algoritmul rãmâne acelaºi care este cunoscut cititorului din parcurgerea manualului.

Cele câteva modificãri în implementare vizeazã, în special, eficientizarea cãutãrii în spaþiul soluþiilor, reducerea timpului de calcul, dar ºi scurtarea codului. Dupã cum se cunoaºte, secvenþa de cod care se executã cel mai frecvent constã în extragerea din lista configuraþiilor a aceleia care minimizeazã efortul parcurs ºi cel estimat (suma g+h) ºi expandarea acestei configuraþii. Deci operaþiile cele mai frecvente din algoritm sunt cele care manipuleazã o listã. Deoarece pentru date de intrare mai mari, timpul de calcul creºte considerabil, aceastã listã a configuraþiilor devine ºi ea foarte mare, ajungând sã conþinã chiar zeci de mii de noduri. Dat fiind faptul cã operaþiile cu pointeri sunt destul de lente, iar lista fiind atât de mare, rezultã cã cea mai mare parte din timpul de calcul este consumatã de operaþiile de parcurgere, inserare ºi ºtergere din listã. Va trebui sã gãsim o cale de reducere a numãrului de astfel de operaþii dar ºi a timpului consumat de ele.

O primã idee simplã ar fi sã folosim o singurã listã, care sã conþinã ºi nodurile expandate ºi cele neexpandate, ºi pentru a le distinge sã folosim un nou câmp care sã indice tipul nodului. În acest mod am elimina toate operaþiile de ºtergere din lista open (a nodurilor neexpandate) ºi de inserare în lista close. Aceastã secvenþã s-ar reduce doar la schimbarea unei valori din false în true. Dar aceastã schimbare nu aduce o îmbunãtãþire substanþialã pentru cã prezintã un dezavantaj esenþial: verificarea existenþei unui nod în listã, ca ºi operaþia de extragere a minimului din lista open va consuma un timp de calcul sporit pentru cã acum este necesarã parcurgerea întregii liste, deci ºi a nodurilor deja expandate.

Vom încerca sã înlãturãm ºi acest neajuns. Tehnica ce urmeazã a fi prezentatã porneºte de la o idee

de bun-simþ, ºi anume: dacã trebuie sã cãutãm un nod într-o listã foarte mare, de ce sã nu împãrþim lista cea mare, dupã o regulã bine stabilitã, în multe liste mai mici? Astfel în loc sã cãutãm într-o listã cu 20.000 de noduri vom cãuta într-una cu 10 de noduri. Aceastã tehnicã se numeºte hash table sau tabele de dispersie1, iar “regula bine stabilitã” este de fapt o funcþie numitã hash, care nu este nici injectivã, nici surjectivã, ºi de care depinde în mare mãsurã reuºita acestei metode.

Sã analizãm aceastã funcþie: rolul ei este de a asocia în mod determinist fiecãrui nod, pe baza informaþiilor care-l individualizeazã, o valoare întreagã cuprinsã între 0 ºi hn - o constantã care reprezinzã numãrul listelor “mici” (numite buckets) care vor fi folosite. Pentru a fi eficientã o astfel de funcþie trebuie sã asigure o distribuþie cât mai uniformã a nodurilor în liste, ºi deci sã minimizeze timpul unei cãutãri. În general, datoritã diversitãþii problemelor, nu existã o formulã standard pentru aceastã funcþie, dar, þinând cont de câteva observaþii, se poate construi destul de uºor o funcþie hash bunã: în primul rând trebuie calculatã, folosind o metodã arbitrarã, o valoare cât mai mare (cât încape în reprezentarea internã) care sã depindã de configuraþia respectivã; rezultatul funcþiei hash va fi egal cu aceastã valoare modulo hn.

hn trebuie sã fie un numãr prim pentru a obþine rezultate cât mai bune.

Acum sã particularizãm: funcþia hash folositã aici, asociazã fiecãrei cãsuþe din pãtrat un numãr prim care este memorat in matricea np (pot fi folosite ºi numere generate aleator cu condiþia ca în cazul extrem valoarea calculatã sã nu depãºeascã reprezentarea); apoi se însumeazã pãtratele produselor dintre valoarea aflatã pe acea cãsuþã (între 0 ºi N*N-2) ºi numãrul prim corespunzãtor; în final se calculeazã modulo hn.

Valoarea aleasã pentru hn este 4999 care este un numãr prim ºi uºor de reþinut.

Cum se efectueazã operaþiile cu lista? Se reþine un vector de pointeri v[i] care indicã primul element din lista i. Pentru inserarea unui nod se va calcula k=Hash(nod) ºi nodul respectiv se va insera în lista v[k]. Cãutarea unui nod se va desfãºura în mod analog: se calculeazã din nou k ºi se parcurge lista v[k], care, în general, nu trebuie sã aibã mai mult de zece elemente. Totuºi a rãmas o operaþie care este la fel de consumatoare de timp ca ºi înainte, anume extragerea minimului care necesitã parcurgerea tuturor elementelor din toate listele. Aceasta poate fi optimizatã destul de simplu: vom mai reþine un vector de pointeri M[i] care va indica nodul neexpandat din lista i cu suma g+h minimã. Aceasta implicã, evident, niºte operaþii în plus: pentru a pãstra proprietatea de minim a nodului referit de M la fiecare inserare se va verifica daca nodul curent are valoarea g+h mai micã decât cea aflatã la M[k], iar la fiecare extragere de minim va trebui parcursã lista v[k] pentru a selecta noul minim ce trebuie referit de M. Aceste operaþii sunt implementate în procedurile AddNode ºi, respectiv, GetMin.

Deci extragerea minimului se va face într-un timp constant indiferent de numãrul de noduri (este necesarã doar o parcurgere a vectorului M). Cãutarea unui nod va necesita parcurgerea unei singure liste v[I]. Trebuie observat cã timpul de calcul necesar ambelor operaþii depinde de hn: prima necesitã exact hn paºi, iar cea de-a doua, un numãr de paºi egal, pe medie, cu raportul dintre numãrul

total de noduri generate ºi hn. Este clar cã alegerea lui hn determinã eficienþa programului: dacã numãrul de noduri obþinute din expandarea unei configuraþii este mic, atunci într-un timp constant se vor efectua mai multe extrageri de minim ºi ar fi recomandat ca hn sã primeascã o valoare mai micã (pentru a reduce timpul consumat de cãutarea minimului); în caz contrar, se vor efectua multe operaþii de cãutare ºi deci hn va lua o valoare mai mare pentru a minimiza lungimea listelor v[i].

Program Patrat;

type ref =^nod; nod =record a :array[1..6,1..6] of byte; n,p :ref; g,h :integer; e :boolean; end;

const np:array[1..36] of longint= (2,3,5,7,11,13,17,19,23,29,31,37,41,43, 47,53,59,61,67,71,73,79,83,89,97,101,103, 107,109,113,127,131,137,139,149,151); hashno=4999;

var fil :text; i,j,n :integer; Ci,Cf,minh :ref; v,M :array[0..4998] of ref;

Function Hash(p:ref):integer;var i,j:integer; t :longint;begin t:=0; for i:=1 to n do for j:=1 to n do t:=t+sqr(p^.a[i,j]*np[37-(i-1)*n-j]); Hash:=t mod hashnoend;

Procedure H(p:ref);var i,j,x,y:integer;begin p^.h:=0;

for i:=1 to n do for j:=1 to n do if p^.a[i,j]<>Cf^.a[i,j] then for x:=1 to n do for y:=1 to n do if p^.a[i,j]=Cf^.a[x,y] then begin inc(p^.h,abs(i-x)+abs(j-y)); x:=n; y:=n endend;

Procedure AddNode(p:ref);var t,t2:integer; z :ref;begin p^.e:=false; t:=Hash(p); if v[t]<>nil then z:=v[t] else z:=nil; v[t]:=p; v[t]^.n:=z; if M[t]=nil then M[t]:=p else if p^.g+p^.h<M[t]^.g+M[t]^.h then M[t]:=pend;

Function GetMin:ref;var f,i:integer; t :ref;begin GetMin:=nil; i:=-1; for f:=0 to hashno-1 do if M[f]<>nil then if i=-1 then i:=f else if M[f]^.g+M[f]^.h < M[i]^.g+M[i]^.h then i:=f; GetMin:=M[i]; m[i]:=nil; t:=v[i]; while t<>nil do begin if (not t^.e) then if m[i]=nil then m[i]:=t else if M[i]^.g+M[i]^.h>t^.g+t^.h then M[i]:=t; t:=t^.n

endend;

Function Equal(p1,p2:ref):boolean;var i,j:integer;begin Equal:=true; for i:=1 to n do for j:=1 to n do if p1^.a[i,j]<>p2^.a[i,j] then Equal:=falseend;

Procedure PrintSol(f:ref);var i,j:integer;begin if f^.p<>nil then PrintSol(f^.p); for i:=1 to n do begin for j:=1 to n do write(f^.a[i,j],' '); writeln end; readlnend;

Procedure Expand(minh:ref);var i,j,x,y,q :integer; t,f :ref;begin minh^.e:=true; for i:=1 to n do for j:=1 to n do if minh^.a[i,j]=0 then for x:=-1 to 1 do for y:=-1 to 1 do if (x=0) xor (y=0) then if (i+x in [1..n]) and (j+y in [1..n]) then begin new(t); t^:=minh^; inc(t^.g); t^.p:=minh; t^.n:=nil; t^.e:=false; q:=t^.a[i,j]; t^.a[i,j]:=t^.a[i+x,j+y]; t^.a[i+x,j+y]:=q; H(t);

q:=Hash(t); f:=v[q]; while (f<>nil) do begin if Equal(f,t) then break; f:=f^.n end; if f=nil then AddNode(t) else if f^.g>t^.g then begin f^.p:=minh; f^.g:=t^.g; if not f^.e then if f^.g+f^.h < m[q]^.g+m[q]^.h then m[q]:=f end else dispose(t) endend;

begin assign(fil,'PATRAT.IN'); reset(fil); readln(fil,n); new(Ci); new(Cf); for i:=1 to n do begin for j:=1 to n do read(fil,Ci^.a[i,j]); readln(fil); end; for i:=1 to n do begin for j:=1 to n do read(fil,Cf^.a[i,j]); readln(fil) end; close(fil);

for i:=0 to hashno-1 do begin v[i]:=nil; M[i]:=nil end; H(Ci); Ci^.g:=0; Ci^.p:=nil; Ci^.e:=false;

AddNode(Ci); minh:=GetMin; while minh^.h>0 do begin Expand(minh); minh:=GetMin end; writeln(minh^.g,' mutari.'); PrintSol(minh)end.

Problema 2

Enunþ. Se dã un tablou MxN (1 ≤M+N ≤15) cu elemente numere întregi. Se numeºte "operaþie" în acest tablou înmulþirea unei linii sau coloane cu -1. Sã se determine cea mai micã secvenþã de operaþii care aduce tabloul la o formã în care toate sumele de linii sau coloane dau numere nenegative.

Intrare:

Fiºierul de intrare, numit "semne.in" este de forma:

m na11 a12 ... a1na21 a22 ... a2n..............am1 am2 ... amn

Ieºire:

Rezultatele vor fi în fiºierul "semne.out", sub forma:

k - numãrul minim de operaþii

x1 x2 ... xk - unde xi este de forma lt sau ct, lt (ct) reprezentând

schimbarea semnului pe linia (coloana) t.

Linia a doua reprezintã secvenþa de operaþii care conduc la rezultat.

Atenþie: se vor scrie întâi operaþiile pe linii, ordonate crescãtor, urmate de operaþiile pe coloane.

Dacã sunt mai multe soluþii, se va lista una din ele.

Observaþie: pentru k=0, a doua linie este goalã.

Exemplu:Pentru intrarea

5 34 -2 23 -1 15-22 0 -34 1 -35 -3 2

ieºirea este:

2c2 l3

Timp de execuþie: 10 secunde/test

“Semne” – prof. dr. univ. Adrian Atanasiu

"Marele premiu PACO", Bucureºti, 20-21 iunie 1997, clasa X

Rezolvare. Deoarece rezolvarea se bazeazã pe aceeaºi linie cu precedenta, vom evidenþia doar câteva aspecte care þin strict de particularitatea problemei. Fiindcã reconstituirea soluþiei va necesita precizarea “operaþiilor” efectuate suntem nevoiþi sã adugãm informaþiei din nod încã douã câmpuri ml ºi mc care vor preciza ce operaþie a fost fãcutã pe linie sau coloanã pentru a ajunge în configuraþia curentã.

Dupã cum se ºtie, pentru a asigura optimalitatea soluþiei, funcþia euristicã trebuie în mod obligatoriu sã fie optimistã adicã sã prezicã un efort mai mic decât cel real. În cazul de faþã construirea unei funcþii care sã fie optimistã indiferent de configuraþie este mai dificilã ºi ar necesita un timp de calcul considerabil. Problema constã în faptul cã o singurã operaþie poate schimba semnul mai multor sume, ºi deci o configuraþie care are majoritatea sumelor negative poate sã conducã la soluþie într-un numãr de paºi mai mic decât cel al liniilor ºi coloanelor cu sumã mai micã decât zero. De aceea a fost aleasã o metodã mai puþin deterministã, dar care dã rezultate bune în practicã: se aproximeazã numãrul de operaþii necesare cu jumãtate din numãrul liniilor ºi coloanelor cu sumã negativã.

Program Semne;

type ref =^rec; rec =record a :array[1..15,1..15] of integer; n,p :ref; ml,mc :byte; e :boolean; g,h :integer end;

var fil :text; n,m,i,j :integer; gn,nn :integer; l,o :array[-1..4999] of ref; t,b,sp :ref;

const hn =4999; p :array[0..14] of integer= (2,3,5,7,11,13,17,19,23,29,31,37,41,47,51);

function Sgn(i:integer):integer;begin if i>0 then sgn:=1 else sgn:=-1end;

Function Hash(t:ref):integer;var i,j,f,r:integer;begin r:=0; for i:=1 to m do for j:=1 to n do r:=r+sgn(t^.a[i,j])*sqr(p[((i-1)*j) mod 15]); Hash:=abs(r) mod hnend;

Procedure H(t:ref);var i,j:integer; s :longint;begin t^.h:=0; for i:=1 to m do begin

s:=0; for j:=1 to n do s:=s+t^.a[i,j]; if s < 0 then inc(t^.h) end; for i:=1 to n do begin s:=0; for j:=1 to m do s:=s+t^.a[j,i]; if s<0 then inc(t^.h) end; if t^.h<>0 then inc(t^.h); t^.h:=round(t^.h*0.5)end;

Procedure Add(p:ref);var k:integer;begin inc(nn); k:=hash(p); if l[k]=nil then inc(gn); p^.n:=l[k]; l[k]:=p; if o[k]=nil then o[k]:=p else if o[k]^.g+o[k]^.h>p^.g+p^.h then o[k]:=p;end;

Function Getmin:ref;var f,I :integer; r :ref;begin r:=nil; i:=-1; for f:=0 to hn do if o[f]<>nil then begin if i=-1 then i:=f else if o[f]^.g+o[f]^.h < o[i]^.g+o[i]^.h then i:=f; end; GetMin:=o[i]; o[i]^.e:=true; r:=l[i]; o[i]:=nil; while (r>>nil) do begin if r^.e=false then begin

if o[i]=nil then o[i]:=r else if o[i]^.g+o[i]^.h>r^.g+r^.h then o[i]:=r end; r:=r^.n end;end;

Function Egal(p1,p2:ref):boolean;var i,j :integer;begin Egal:=true; for i:=1 to m do for j:=1 to n do if p1^.a[i,j]<>p2^.a[i,j] then Egal:=falseend;

Procedure Expand(b:ref);var i,j,k:integer; t,q :ref;begin for i:=1 to m do begin new(t); t^:=b^; t^.e:=false; inc(t^.g); for j:=1 to n do t^.a[i,j]:=-t^.a[i,j]; H(t); t^.p:=b; t^.n:=nil; t^.ml:=i; t^.mc:=0; k:=Hash(t); q:=l[k]; while q<>nil do begin if egal(t,q) then break; q:=q^.n end; if q<>nil then if q^.g>t^.g then q^:=t^ else dispose(t) else Add(t) end; for j:=1 to n do begin

new(t); t^:=b^; t^.e:=false; inc(t^.g); for i:=1 to m do t^.a[i,j]:=-t^.a[i,j]; H(t); t^.p:=b; t^.n:=nil; t^.ml:=0; t^.mc:=j; k:=Hash(t); q:=l[k]; while q<>nil do begin if egal(t,q) then break; q:=q^.n end; if q<>nil then if q^.g>t^.g then q^:=t^ else dispose(t) else Add(t) endend;

Procedure Sol(b:ref);var i,j,f :integer; q :ref; l,c :array[0..15] of byte;begin assign(fil,'SEMNE.OUT'); rewrite(fil); for i:=0 to 15 do begin l[i]:=0; c[i]:=0 end; q:=b; while q<>nil do begin l[q^.ml]:=1-l[q^.ml]; c[q^.mc]:=1-c[q^.mc]; q:=q^.p end; f:=0; for i:=1 to 15 do f:=f+l[i]+c[i]; writeln(fil,f); for i:=1 to 15 do if l[i]=1 then write(fil,'L',i,' '); for i:=1 to 15 do if c[i]=1 then write(fil,'C',i,' '); close(fil)end;

begin for i:=-1 to hn do begin l[i]:=nil; o[i]:=nil end;

assign(fil,'SEMNE.IN'); reset(fil); readln(fil,m,n); if (m+n>15) or (m+n<1) then begin writeln('date invalide.'); halt end; new(t); t^.n:=nil; t^.p:=nil; t^.e:=false; t^.ml:=0; t^.mc:=0; t^.g:=0; for i:=1 to m do begin for j:=1 to n do read(fil,t^.a[i,j]); readln(fil) end; close(fil); H(t); Add(t); repeat b:=getmin; if b^.h<>0 then expand(b) until b^.h=0; sol(b)end.

Problema 3

Enunþ. Fie urmãtoarea tablã de joc:

constând din douã pãtrate de laturã N=4, care au un pãtrãþel comun, D4, în figura de mai sus. Pe tablã sunt aºezate piese notate cu 'X' ºi 'O', aºezate simetric faþã de D4. Jocul constã în a schimba între ele locurile ocupate de piesele 'O’ ºi 'X', într-un numãr minim de mutãri. O piesã poate fi mutatã într-o pãtrãþicã liberã învecinatã ei, sau prin sãritura peste o altã piesã alãturatã dacã se ajunge într-o pãtrãþicã liberã.

Pentru configuraþia de mai sus în pãtrãþica D4 se poate ajunge din:

D3, D2, D5, D6, C4, B4,E4, F4.

Nu sunt permise mutãri pe oblicã.

Fiºierul de intrare joc.in conþine poziþia pieselor notate cu 'X' (lucru suficient, având în vedere aºezarea simetricã a celor notate cu 'O' faþã de D4).

Se cere schimbarea între ele a poziþiilor pieselor 'X' cu 'O' într-un numãr cât mai mic de mutãri. Prin mutare se înþelege deplasarea unei piese o singurã datã într-o altã pãtrãþicã.

Mutãrile se vor vizualiza pe ecran, simulând jocul. În acelaºi timp se vor contoriza mutãrile.

Exemplu: (pentru figura datã)

fiºierul joc.in:

D3D2E4E3E2F4F3F2

Timp de executie 20 sec/test pentru 586 la 133MHz

prof. Maria ºi Adrian NIÞÃ

Liceul "Emanuil Gojdu" Oradea

Rezolvare. Funcþia euristicã se bazeazã tot pe distanþa Manhattan, cu câteva modificãri necesare, ca ºi la problema anterioarã, pentru a împiedica funcþia sã devinã “pesimistã”, adicã sã supraestimeze numãrul de mutãri necesare, fapt ce ar conduce la obþinerea unor rezultate neoptime. Pentru a eficientiza procesul de estimare, vom folosi o tabelã precalculatã nm cu semnificaþia: nm[p,I,j] este egal distanþa Manhattan de la poziþia i,j pe care se aflã o piesã de tipul p (0 sau 1 - X sau O) pânã la cea mai apropiatã cãsuþã destinaþie pentru piesele de tipul p. Deoarece aceste distanþe nu depind de configuraþia pieselor, matricea va fi de fapt o constantã (iniþializatã în procedura Citire). O altã matrice constantã folositã este valid care indicã dacã poziþia i,j aparþine sau nu tablei de joc.

Program XsiO;

uses crt;

const hn=2999; ps:string=' XO';

type tabla =array[1..7,1..7] of byte;

ref =^nod; nod =record a :tabla; n,t :ref; g,h :byte; e :boolean; end;

var v,min :array[0..4999] of ref; valid :array[-1..9,-1..9] of boolean; nm :array[0..3,1..7,1..7] of byte; i,j :longint; n,final :nod; z :ref; hv :array[1..7,1..7] of longint;

Procedure Citire;var fil :text; c1,c2 :char; i,j,x,y,f,t :integer;begin assign(fil,'JOC.IN'); reset(Fil); while not eof(fil) do begin readln(fil,c1,j); i:=byte(Upcase(c1))-64; n.a[i,j]:=1; final.a[i,j]:=2; n.a[8-i,8-j]:=2; final.a[8-i,8-j]:=1 end; close(fil);

for f:=1 to 2 do for i:=1 to 7 do for j:=1 to 7 do if valid[i,j] then begin nm[f,i,j]:=255; for x:=1 to 7 do for y:=1 to 7 do if valid[x,y] then if (abs(x-i)+abs(y-j) < nm[f,i,j]) and (f+final.a[x,y]=3) then nm[f,i,j]:=abs(x-i)+abs(y-j); if nm[f,i,j]<>0 then inc(nm[f,i,j],(abs(i-4)+abs(j-4)) div 2);

nm[f,i,j]:=round(nm[f,i,j]*0.8) endend;

Function Hash(p:ref):integer;var i,j,k,c,t:longint;begin t:=0; for i:=1 to 7 do for j:=1 to 7 do if valid[i,j] then begin c:=1; for k:=1 to p^.a[i,j] do c:=c*hv[i,j]; t:=t+c end; Hash:=t mod hnend;

Procedure H(p:ref);var i,j:integer;begin p^.h:=0; for i:=1 to 7 do for j:=1 to 7 do if valid[i,j] then p^.h:=p^.h+nm[3-p^.a[i,j],i,j]end;

Procedure AdNod(p:ref);var i:integer; t:ref;begin i:=Hash(p); if Min[i]=nil then Min[i]:=p; if Min[i]^.g+Min[i]^.h>p^.g+p^.h then Min[i]:=p; p^.n:=v[i]; v[i]:=pend;

Function GetMin:ref;var i,r:integer; k:ref;begin r:=0; while Min[r]=nil do inc(r); for i:=r+1 to hn-1 do if (Min[i]<>nil) and (Min[i]^.g+Min[i]^.h < Min[r]^.g+Min[r]^.h) then r:=i; Min[r]^.e:=true; GetMin:=Min[r];

Min[r]:=nil; k:=v[r]; while k<>nil do begin if not k^.e then begin if Min[r]=nil then Min[r]:=k; if k^.g+k^.h < Min[r]^.g+Min[r]^.h then Min[r]:=k end; k:=k^.n endend;

Function Egal(p1,p2:ref):boolean;var i,j:integer;begin Egal:=false; for i:=1 to 7 do for j:=1 to 7 do if valid[i,j] then if p1^.a[i,j]<>p2^.a[i,j] then exit; Egal:=trueend;

Procedure Expand(p:ref);var i,j,di,dj,k :integer; w,q,f :ref;Procedure Proces(w:ref);begin w^.e:=false; w^.t:=p; inc(w^.g); H(w); k:=Hash(w); q:=V[k]; f:=nil; while q<>nil do begin if q^.h=w^.h then if Egal(q,w) then begin f:=q; break end; q:=q^.n end; if f=nil then AdNod(w) else begin if f^.g>w^.g then begin f^.g:=w^.g; f^.t:=p; f^.e:=false; if Min[k]=nil then Min[k]:=f; if Min[k]^.g+Min[k]^.h>f^.g+f^.h then Min[k]:=f end; Dispose(w)

endend;begin for i:=1 to 7 do for j:=1 to 7 do if p^.a[i,j]<>0 then for di:=-1 to 1 do for dj:=-1 to 1 do if (di=0) xor (dj=0) then begin if Valid[i+di,j+dj] and (p^.a[i+di,j+dj]=0) then begin new(w); w^:=p^; w^.a[i,j]:=0; w^.a[i+di,j+dj]:=p^.a[i,j]; Proces(w) end; if Valid[i+2*di,j+2*dj] and (p^.a[i+di,j+dj]<>0) and (p^.a[i+2*di,j+2*dj]=0) then begin new(w); w^:=p^; w^.a[i,j]:=0; w^.a[i+2*di,j+2*dj]:=p^.a[i,j]; Proces(w) end endend;

Procedure Print(p:ref);begin if p^.t<>nil then Print(p^.t); for i:=1 to 7 do for j:=1 to 7 do begin gotoxy(3+4*i,2+2*(8-j)); if p^.a[i,j]<>0 then write(ps[1+p^.a[i,j]]) else write(' ') end; gotoxy(1,24); write('Numãr Mutãri:',p^.g); readlnend;

Procedure Sol(p:ref);var i,j,ti,tj:integer; fil:text;begin ClrScr; for i:=1 to 7 do for j:=1 to 7 do if Valid[i,j] then begin

ti:=3+4*i; tj:=2+2*(8-j); gotoxy(ti-1,tj-1); write('---'); gotoxy(ti-1,tj+1); write('---'); gotoxy(ti-2,tj); write('|'); gotoxy(ti+2,tj); write('|') end; Print(p)end;

begin randomize; for i:=1 to 7 do for j:=1 to 7 do hv[i,j]:=1+Random(200)+Random(200);

fillchar(v,sizeof(v),0); fillchar(min,sizeof(min),0); fillchar(n.a,sizeof(tabla),0); fillchar(final.a,sizeof(tabla),0); fillchar(valid,sizeof(valid),0);

for i:=4 to 7 do for j:=1 to 4 do begin valid[i,j]:=true; valid[8-i,8-j]:=true end; Citire; n.t:=nil; n.g:=0; n.e:=false; H(@n); AdNod(@n); repeat z:=GetMin; if z^.h<>0 then Expand(z) until z^.h=0; Sol(z)end.

Problema 4

Enunþ. Fie douã inele în care sunt aºezate echidistant 13 biluþe, ca în figurã. Inelele au douã biluþe în comun, ºi deci în total vor fi 24 de biluþe din care 11 negre, 11 albe ºi douã gri. Fiecare inel se poate roti în sens orar cel puþin o poziþie ºi cel mult 12, antrenând cu el cele 13 biluþe din interiorul sãu.

Problema constã în a aduce o configuraþie iniþialã la configuraþia din figurã într-un numãr minim de rotiri.

Datele de intrare se citesc din fiºierul bilute.in ºi conþin douã linii, pe fiecare aflându-se un ºir de 13 caractere ce codificã aºezarea biluþelor astel: A,N ºi G semnificã o biluþã de culoare albã, neagrã, respectiv gri. Primul caracter din ºir corespunde întotdeauna biluþei comune din partea superioarã a figurii, celelalte urmând parcurgerea inelului în sens orar. Primul inel va fi cel ce conþine în figurã biluþele albe. Deci configuraþia din figurã va fi reprezentatã astfel:

GAAAAAAAAGAAA GNNNGNNNNNNNN

Ieºirea se va face pe ecran, tipãrind configuraþia biluþelor dupã fiecare rotire.

Problemã datã la selecþia lotului pentru Balcaniadã, Sibiu 1996

enunþ reformulat

Rezolvare. Programul de mai jos este o implementare simplã a tehnicii Branch and Bound, fãrã nici o optimizare suplimentarã. Absenþa tabelelor de dispersie nu este motivatã de structura diferitã a informaþiei din noduri: chiar dacã nu mai avem de-a face cu numere, o funcþie hash eficientã poate fi construitã uºor: o idee ar fi sã unim cele douã ºiruri obþinând 26 de elemente, fiecare din ele putând lua trei valori; apoi putem interpreta acest nou ºir ca pe un numãr în baza 3 pe care-l vom impãrþi modulo la hn.

Este bine de ºtiut cã memoria disponibilã pe heap, cea în care se alocã nodurile, poate fi aflatã folosind funcþia MemAvail. Aceasta poate servi la oprirea programului, în cazul în care nu mai este suficientã memorie liberã, ºi tipãrirea unui mesaj corespunzãtor.

Program Bilute;

type sir =string[13]; ref =^nod; nod =record s1,s2 :sir; n,t :ref; g,h :integer; e :boolean; end;

var b,i,k :ref; cc :sir; min :integer;

Procedure H(p:ref);var s,f:integer;begin s:=0; for f:=1 to 13 do begin if (p^.s1[f]='N') and (f in [2..9,11..13]) then s:=s+2; if (p^.s2[f]='A') and (f in [2..4,6..13]) then s:=s+2; end; if p^.s1[1]<>'G' then s:=s+1; if p^.s2[5]<>'G' then s:=s+1; p^.h:=send;

Procedure Citire;var fil :text;begin new(B);

b^.t:=nil; b^.n:=nil; b^.g:=0; b^.e:=false; assign(fil,'BILUTE.IN'); reset(fil); readln(fil,b^.s1); readln(fil,b^.s2); close(fil); h(b)end;

Procedure Shift(var s:sir;p:integer);var f,n :integer;begin n:=length(s); for f:=1 to p do s:=s[n]+Copy(s,1,n-1)end;

Procedure Sol(p:ref);begin if p^.t<>nil then Sol(p^.t); writeln(p^.s1,' ',p^.s2)end;

Procedure Expand(p:ref);var z,t,q,cut :ref; f,i :integer;begin t:=b; while t^.n<>nil do t:=t^.n; p^.e:=true; for f:=1 to 12 do for i:=1 to 2 do begin new(z); z^.e:=false; z^.t:=p; z^.n:=nil; z^.g:=p^.g+1; z^.s1:=p^.s1; z^.s2:=p^.s2; if i=1 then begin shift(z^.s1,f); z^.s2[5]:=z^.s1[10]; z^.s2[1]:=z^.s1[1]

end else begin shift(z^.s2,f); z^.s1[10]:=z^.s2[5]; z^.s1[1]:=z^.s2[1] end; h(z); q:=b; cut:=nil; while q^.n<>nil do begin if (q^.s1=z^.s1) and (q^.s2=z^.s2) and (q^.g>z^.g) then begin q^.t:=p; cut:=q end; q:=q^.n end; if cut=nil then begin t^.n:=z; cut:=t^.n; t:=t^.n end else dispose(z); if cut^.h=0 then begin Sol(cut); readln; halt end endend;begin Citire; repeat min:=maxint; i:=b; k:=b; while i^.n<>nil do begin if (i^.h+i^.g<min) and (not i^.e) then begin min:=i^.h+i^.g; k:=i end; i:=i^.n end; expand(k) until memavail<500; writeln(‘Nu exista solutie’)end.

Problemã propusã

Enunþ. Pe o tablã de ºah nxn se gãsesc p cai ºi k obstacole amplasate într-o configuraþie iniþialã.

Miºcarea calului este cea cunoscutã de la ºah. Calul poate sãri un obstacol sau un alt cal, dar nu poate staþiona pe o poziþie ocupatã de un cal sau de un obstacol.

Problema cere ca dvs. sã determinaþi, dacã existã, un set de miºcãri ale cailor care permit ajungerea într-o configuraþie finalã cerutã. Exemplu:

Configuraþie iniþialã (n=3, p=2, k=1)

c o c

Configuraþia finalã:

o

c c

Observaþii:

1. Configuraþia iniþialã se citeºte din fiºierul text in.txt. Prima linie a fiºierului conþine numãrul n. Fiecare linie, din urmãtoarele n, conþine n caractere (O pentru obstacol, C pentru cal, S pentru cãsuþã neocupatã) reprezentând configuraþia iniþialã. Urmãtoarele n linii reþin configuraþia finalã. Pentru exemplul anterior avem:

3COCSSSSSSSOSSSSCSC

2. Programul va scrie soluþia, dacã existã, în fiºierul out.txt. Primele n linii vor fi date de configuraþia iniþialã, urmeazã o linie vidã, urmeazã n linii ale primei configuraþii intermediare, o linie

vidã, …, n linii ale configuraþiei finale.

3. Valorile p ºi k se deduc din configuraþia iniþialã

5. Dacã nu existã soluþie, prima linie a fiºierului va conþine NU

6. Timp de execuþie: 1 minut.

“Miºcarea cailor” – prof. Tudor Sorin,

Concurs cl. XI-XII, Lugoj 1998

[ Capitolul 8 ] [ Cuprins ] [ Capitolul

10 ]

Capitolul 10

Teoria grafurilor

Reþele de transport

Aºa cum putem abstractiza harta strãzilor folosind un graf orientat pentru a gãsi cel mai scurt drum între douã noduri, putem de asemenea sã interpretãm un graf orientat ca pe o “reþea de transport” ºi sã-l folosim pentru a rãspunde unor întrebãri despre transportul de material. Imaginaþi-vã traseul materialului printr-un sistem de la o sursã, unde este produs, la o destinaþie, unde este consumat. Sursa produce materialul într-un anumit ritm ºi destinaþia îl consumã în acelaºi ritm. Transportul de material în oricare punct din sistem este, intuitiv, ritmul în care materialul se miºcã. Reþelele de transport pot fi folosite ca model teoretic pentru reþelele de conducte, pãrþi ale liniilor de asamblare, curentul care circulã prin reþelele electrice, informaþia care circulã prin reþelele de comunicaþie.

Fiecare arc dintr-o reþea poate fi imaginat ca o conductã prin care circulã material. Fiecare conductã are o capacitate specificatã, care reprezintã “ritmul” maxim la care materialul poate circula prin conductã, ca de exemplu 2000 metri cubi de lichid pe orã printr-o conductã, sau curent electric de 20 amperi care poate trece printr-un conductor.

O reþea de transport G=(V,E), cu sursa s ºi destinaþia t, este un graf orientat în care fiecare muchie (u,v) ∈ E are o capacitate pozitivã c(u,v) ≥0. Dacã (u,v) ∉ E, vom considera c(u,v)=0.

Nodurile dintr-o reþea, în afarã de s ºi t, sunt doar punctele de intersecþie ale conductelor: materialul trece prin ele fãrã a fi colectat. Adicã ritmul în care materialul intrã într-un nod trebuie sã fie egal cu ritmul în care materialul iese din nod. Aceasta este proprietatea de conservare a fluxului ºi este aceeaºi ca ºi legea lui Kirchhoff pentru cazul în care “materialul” este curentul electric (“flux“ este echivalent cu “ritm”, semnificând o anumitã cantitate într-o anumitã perioadã de timp).

Un flux în G este o funcþie f:VxV→R care are urmãtoarele proprietãþi:

● 0 ≤ fi,j ≤ ci,j , adicã fluxul transportat pe orice arc trebuie sã fie nenegativ ºi subcapacitar;

● Σj∈V fj,i = Σj∈V fi,j , ∀ i∈V-{s,t}, adicã conservarea fluxului.

Dacã f este un flux în reþeaua G=(V,E), atunci se numeºte valoarea fluxului f numãrul:

v(f) = Σj∈V fj,t - Σj∈V ft,j

V(f) poate fi interpretat ca fiind fluxul net care ajunge în ieºirea reþelei sau fluxul net care intrã în reþea prin s.

Problema fluxului maxim

Se dã reþeaua G=(V,E) cu sursa s ºi destinaþia t, ºi funcþia capacitarã c. Se cere sã se determine un flux de valoare maximã.

Fie P un drum oarecare în graful suport al lui G (acelaºi graf în care se ignorã sensurile arcelor), ºi e=vivj o muchie a lui P; dacã e corespunde arcului vivj al lui G, e se numeºte arc direct al drumului P; dacã e corespunde arcului vjvi al lui G, atunci e se numeºte arc invers.

De exemplu, în graful de mai sus, sã considerãm cã drumul P trece prin nodurile 1,2,4,5,6,7. Fiecare din muchiile (1,2), (2,4), (4,5) ºi (6,7) sunt arce directe ale drumului P pentru cã au acelaºi sens de parcurgere ca ºi cel din reþea; în schimb muchia (5,6) a drumului P este un arc invers.

Fie P un drum ºi vivj o muche din P. Se numeºte capacitatea rezidualã a lui vivj numãrul:

r(ij) = ci,j – fi,j dacã vivj este arc direct în P

fj,i dacã vivj este arc invers în P

În exemplul de mai sus, primul numãr de pe arc reprezintã capacitatea arcului, iar cel de-al doilea, fluxul. Astfel, capacitatea rezidualã a arcului (4,5), r(4,5) va fi egalã cu c4,5 – f4,5 = 8 – 3 = 5. Pentru arcul (5,6) vom avea:

r(5,6) = f6,5 = 4.

Capacitatea rezidualã a drumului P se noteazã cu r(P) ºi este egalã cu minimul dintre capacitãþile reziduale ale muchiilor din P:

r(P) = min e∈P r(e)

Fie P={4,5,6}. Cum r(4,5)=5 ºi r(5,6)=4 rezultã cã r(P)=4.

Se numeºte drum de creºtere a fluxului f în reþeaua G, un drum de la s la t care are capacitatea rezidualã mai mare ca zero.

În exemplul nostru, sã luãm drumul 1,2,4,3,6,7 ºi sã vedem dacã este un drum de creºtere: avem r(1,2)=8, r(2,4)=1, r(4,3)=5, r(3,6)=3 ºi r(6,7)=6, deci capacitatea rezidualã a drumului este 1; rezultã cã drumul nostru este un drum de creºtere.

Teorema 1: Un flux f este de valoare maximã într-o reþea G, dacã ºi numai dacã, nu existã drumuri de creºtere a fluxului f în reþeaua G.

Teorema 2: Dacã toate capacitãþile sunt întregi, atunci existã un flux de valoare maximã cu toate componentele întregi.

Aceste douã teoreme stau la baza algoritmului Ford-Fulkerson pentru determinarea unui flux de valoare maximã.

Primul pas al algoritmului constã în determinarea unui flux iniþial admisibil, adicã fixarea valorilor lui f pentru fiecare arc astfel încât sã se respecte proprietãþile fluxului (cele din definiþie). Un astfel de flux admisibil este ºi cel care are flux 0 pe fiecare arc. Se verificã uºor cã cele douã proprietãþi sunt respectate: fluxul este subcapacitar pe orice arc, iar conservarea fluxului este evidentã: în fiecare nod intrã 0 unitãþi ºi ies de asemenea 0.

La pasul doi se va determina un drum de creºtere P. Acesta se poate gãsi printr-o simplã parcurgere în adâncime, mergând întotdeauna doar pe arcele care au capacitatea rezidualã mai mare ca zero.

Pornind de la fluxul anterior ºi folosind drumul de creºtere gãsit se va obþine un nou flux, f1 de valoare mai mare decât f, astfel: fie r(P) capacitatea rezidualã a drumului gãsit; pentru fiecare arc direct din P se va mãri fluxul cu r(P), iar pentru arcele inverse fluxul va fi scãzut tot cu r(P). Sã dãm un exemplu: pentru drumul de creºtere 1,2,4,5,6,7, avem r(P)=1; deci noile valori ale fluxului vor fi: f1,2=3+1=4, f2,4=3+1=4, f4,5=3+1=4, f5,6=4-1=3 ºi f6,7=0+1=1.

Faptul cã r(P) este egal cu minimul dintre capacitãþile reziduale ale arcelor din P, ne asigurã cã pentru orice e=(u,v) ∈ P, avem r(e) ≥ r(P), adicã pentru arcele directe se mai poate adãuga r(P) flux fãrã a depãºi capacitatea arcului, iar pentru arcele inverse se poate scãdea r(P) fãrã a obþine un

flux negativ. Deci noul flux f1 va respecta prima proprietate a fluxului; sã vedem dacã va respecta ºi conservarea fluxului.

Deoarece arcele pot fi de douã tipuri, vom întâlni patru cazuri, ca în figurã (sensul de parcurgere este de la stânga la dreapta). Sã le analizãm pe rând:

a) ambele arce sunt arce directe, deci fluxul va creºte pe ambele cu aceeaºi cantitate r(P); dacã egalitatea din legea conservãrii fluxului era verificatã, va fi de asemenea verificatã ºi dupã modificarea fluxului: practic vom adãuga aceeaºi cantitate ambilor termeni;

b) primul arc este invers, iar cel de-al doilea este direct, deci pe primul arc fluxul va scãdea, iar pe al doilea va creºte; deoarece ambele arce “ies” din nod, iar fluxul de pe unul creºte, iar de pe celãlalt scade cu aceeaºi cantitate, rezultã cã suma a tot ce “iese” din nod va rãmâne constantã ºi deci fluxul se va conserva;

c) analog cu b);

d) ambele arce sunt inverse; de aceastã datã se va scãdea aceeaºi cantitate din ambii termeni ai egalitãþii conservãrii fluxului, deci egalitatea se va pãstra.

Acest pas se va repeta atâta timp cât exista un drum de creºtere; în final, conform teoremei 1, fluxul gãsit va fi maxim.

Finalitatea algoritmului este asiguratã de faptul cã la fiecare iteraþie valoarea fluxului creºte cu o cantitate mai mare decât zero; cum valoarea fluxului maxim este finitã rezultã cã este necesar un numãr finit de iteraþii ale pasului 2.

Programul prezentat mai jos urmãreºte întocmai algoritmul descris. Parcurgerea în adâncime este realizatã recursiv în procedura FindFlow; aceeaºi procedurã se ocupã de modificarea fluxului dupã ce a fost gãsit un drum de creºtere, operaþie care se face la întoarcerea din recursie. În final valoarea fluxului se calculeazã prin însumarea fluxului de pe arcele care pornesc din sursã; fluxul pe fiecare arc se va gãsi în matricea f.

Datele de intrare se citesc din fiºierul flux.in, ºi au formatul:

n m numãrul de noduri ºi, respectiv, de muchii

i1 j1 cI,j capacitatea arcului de la i1 la j1;

…

im jm cI,j capacitatea arcului de la im la jm.

Se considerã cã sursa reþelei este nodul 1, iar destinaþia este nodul N.

Program Ford_Fulkerson_Flux;

type matr =array[1..100,1..100] of longint;

var c,f :^matr; n,i,m,j,t :longint; fil :text; found :boolean; seen :set of byte;

Function FindFlow(i,min:longint):longint;var p,tmp:longint;begin seen:=seen+[i]; FindFlow:=min; if i=n then found:=true else for p:=1 to n do if (not (p in seen)) and (not found) then begin if (c^[i,p]-f^[i,p])>0 then begin if c^[i,p]-f^[i,p]<min then min:=c^[i,p]-f^[i,p]; tmp:=FindFlow(p,min); if found then begin f^[i,p]:=f^[i,p]+tmp; FindFlow:=tmp end end; if (f^[p,i]>0) and (not found) then begin if f^[p,i]<min then min:=f^[p,i]; tmp:=FindFlow(p,min); if found then begin f^[p,i]:=f^[p,i]-tmp; FindFlow:=tmp end end endend;

begin new(c); fillchar(c^,sizeof(c^),0); new(f); fillchar(f^,sizeof(f^),0); assign(fil,'flux.in'); reset(fil); readln(fil,n,m); for t:=1 to m do readln(fil,i,j,c^[i,j]); close(fil); repeat found:=false; seen:=[]; FindFlow(1,maxlongint) until not found; j:=0; for i:=1 to n do if c^[1,i]<>0 then j:=j+f^[1,i]; writeln('Flux maxim:',j)end.

Sã cercetãm complexitatea algoritmului descris: fiecare iteraþie a pasului doi necesitã O(M) operaþii (M=|E|, numãrul de muchii din reþea); în schimb, numãrul de iteraþii nu poate fi precizat cu exactitate, dar trebuie considerat cã, pentru cazul cel mai defavorabil când la fiecare iteraþie fluxul creºte cu o unitate, acesta este limitat de valoarea fluxului maxim U. Obþinem complexitatea algoritmului O(M⋅ U). Aceasta reprezintã un dezavantaj, deoarece valoarea fluxului poate fi consideratã infinitã în raport cu dimensiunea problemei N (chiar pentru N=5, putem avea U=100.000.000, astfel s-ar obþine un timp de calcul inadmisibil).

De exemplu, în reþeaua de mai sus, considerãm cã M are o valoare foarte mare. Deoarece algoritmul nu alege drumurile de creºtere în mod preferenþial, se poate întâmpla ca drumurile alese sã fie alternativ 1,2,3,4 ºi, respectiv, 1,3,2,4, fiecare dintre ele având capacitatea rezidualã 1. Deci la fiecare iteraþie valoarea fluxului va creºte cu 1, fiind necesare în total 2M iteraþii.

Acest dezavantaj poate fi remediat prin îmbunãtãþirea adusã algoritmului Ford-Fulkerson de cãtre Edmonds ºi Karp. Aceasta constã în simpla înlocuire a parcurgerii în adâncime cu o parcurgere în lãþime, asigurând astfel cã la fiecare pas se alege drumul de creºtere care are cel mai mic numãr de muchii. Este demonstrat cã, folosind aceastã îmbunãtãþire, numãrul de iteraþii al pasului doi nu poate fi mai mare decât M⋅ N/2. Astfel se obþine o complexitate de O(N⋅ M2).

Prezentãm mai jos ºi o implementare care se bazeazã pe aceastã modificare. Pentru parcurgerea în lãþime este folositã o coadã; aceasta este memoratã în vectorul Q, iar i1 ºi i2 vor indica primul, respectiv ultimul element din coadã. Vectorul T reþine tatãl nodului de pe poziþia i din coadã, iar MM[i] este egal cu capacitatea rezidualã a drumului de la sursã la nodul i.

Program Flux_Edmonds_Karp;

type

matr =array[1..100,1..100] of longint;

var fil :text; c,f :^matr; n,m,i,j,k,i1,i2 :integer; Q,T :array[1..300] of integer; MM :array[1..100] of longint; seen :set of byte; flux :longint;

Function Min(m1,m2:longint):longint;begin if m1<m2 then min:=m1 else min:=m2end;

begin assign(fil,'flux.in'); reset(fil); readln(fil,n,m); new(c); fillchar(c^,sizeof(c^),0); new(f); fillchar(f^,sizeof(f^),0); for k:=1 to m do readln(fil,i,j,c^[i,j]); close(fil);

flux:=0; k:=0; repeat seen:=[1]; i1:=1; i2:=1; Q[1]:=1; T[1]:=0; MM[1]:=maxlongint; while (not (n in seen)) and (i1<=i2) do begin j:=Q[i1]; inc(i1); for i:=1 to n do if not (i in seen) then begin if (c^[j,i]-f^[j,i]>0) then begin inc(i2); Q[i2]:=i; T[i]:=j; MM[i]:=Min(MM[j],c^[j,i]-f^[j,i]); seen:=seen+[i] end; if (f^[i,j]>0) then begin inc(i2);

Q[i2]:=i; T[i]:=-j; MM[i]:=Min(MM[j],f^[i,j]); seen:=seen+[i] end end end; if n in seen then begin flux:=flux+MM[n]; i:=n; while i<>1 do begin j:=abs(T[i]); if T[i]>0 then inc(f^[j,i],MM[n]) else dec(f^[i,j],MM[n]); i:=j end end; inc(k) until not (n in seen); writeln('Flux maxim:',flux)end.

Cititorul este invitat sã testeze ambele variante pentru date de intrare mari (N=100, M>3000, ºi capacitãþi cât mai apropiate de maxlongint) ºi sã compare timpii de execuþie.

Problemã propusã

Se considerã un graf orientat cu N noduri. Se dau gradele interioare ºi gradele exterioare pentru fiecare nod. Sã se determine o dispunere a arcelor în graf, astfel încât nodurile sã aibã gradele date.

Indicaþie:

Se va construi o reþea cu 2*N+2 noduri, astfel: fiecare din cele N noduri va fi reprezentat de douã ori prin nodul i ºi nodul i’; de la fiecare nod i se va duce un arc de capacitate 1 la fiecare nod j’, cu j≠ i. Deoarece din fiecare nod trebuie sã plece de(i) muchii (gradul exterior al nodului) fiecare nod i va avea un arc de la sursã cu capacitatea de(i), iar fiecare nod i’ va avea un arc spre destinaþie de capacitate di(i) (gradul interior). Dacã în aceastã reþea se poate determina un flux maxim de valoare m=de(1)+de(2)+ +…+de(n)=di(1)+di(2)+ +…+di(n), atunci din fiecare nod i vor pleca exact de(i) arce, iar în fiecare nod i’ vor intra exact di(i) arce (dacã într-un nod i intrã k unitãþi de flux, având la ieºire doar arce de capacitate 1, se va distribui pe k arce distincte).

Cuplaj maxim într-un graf bipartit

Un graf G(V,M) este bipartit dacã mulþimea vârfurilor sale V poate fi partiþionatã în douã submulþimi V1 ºi V2, astfel încât oricare muchie din M are un capãt în V1 ºi celãlalt capãt în V2. Iatã un exemplu de graf bipartit:

Un cuplaj într-un graf G(V,M) este o submulþime C⊆ E, astfel încât oricare douã muchii din C sunt neadiacente (nu au un capãt comun). Un vârf v∈ V este cuplat dacã este incident la una din muchiile cuplajului; altfel, v este necuplat.

Exemple de cuplaje pe graf general ºi bipartit (muchiile cuplajului sunt desenate cu linia îngroºatã):

Un cuplaj maxim într-un graf G(V,M) este un cuplaj de cardinalitate maximã, adicã un cuplaj C, astfel încât pentru orice cuplaj C1, C ≥ C1 , unde C este numãrul de muchii al cuplajului C.

Avem graful G=(V,M) ºi cuplajul C în acest graf. Un lanþ alternant în G este un lanþ ale cãrui muchii sunt alternativ în C ºi în M-C.

Teorema lui Berge: Un cuplaj C este maxim dacã ºi numai dacã nu existã un lanþ alternant între oricare douã vârfuri necuplate.

Dacã avem un cuplaj C într-un graf G ºi un lanþ alternant P între douã vârfuri necuplate: P={n1,c1,n2,c2,...,n}, unde nk∉ C ºi ck∈ C, atunci, prin scoaterea muchiilor ck din cuplaj ºi introducerea în cuplaj a muchiilor nk se obþine un cuplaj C1 cu o muchie în plus faþã de C. Din acest motiv un lanþ alternant între douã vârfuri necuplate se mai numeºte ºi drum de creºtere relativ la C.

Algoritmul nostru pentru determinarea cuplajului maxim într-un graf bipartit se bazeazã pe gãsirea drumurilor de creºtere ºi “creºterea” cuplajului pe aceste drumuri. Când nu mai existã un astfel de drum cuplajul este maxim conform teoremei lui Berge.

Pentru eficienþa implementãrii vom gãsi iniþial un cuplaj oarecare printr-o metodã Greedy pe care îl vom îmbunãtãþi ulterior pânã când nu mai existã drumuri de creºtere, adicã cuplajul este maxim.

Exemplu: În graful din figurã, determinãm iniþial printr-o metodã Greedy oarecare un cuplaj cu 2 muchii:

Gãsim drumul de creºtere 5-3-6-2-4-1 ºi incrementãm cuplajul pe acest drum obþinând un cuplaj maxim:

Determinarea unui drum de creºtere se face printr-o cãutare în lãþime sau în adâncime. Pornim cãutarea de la un nod necuplat ºi mergem alternativ pe muchii din cuplaj ºi din afara lui pânã gãsim un alt nod necuplat.

În cazul în care graful nu este conex, trebuie repetatã operaþia de creºtere a cuplajului pentru fiecare componentã conexã în parte. Numai când nu se mai poate creºte cuplajul în nici o componentã conexã, avem un cuplaj maxim.

Detalii de implementare a algoritmului:

Graful va fi memorat sub formã de listã de noduri cu ajutorul variabilelor Graf, n, ºi NrV. n este numãrul de noduri al grafului. Nodul i are NrV[i] vecini memoraþi în Graf[i]. Nodurile 1..k formeazã prima partiþie, adicã “partea stângã” a grafului, ºi nodurile k+1..n “partea dreaptã”.

Prima operaþie a programului este citirea grafului prin procedura CitireGraf. Urmeazã determinarea componentelor conexe printr-o parcurgere în adâncime a fiecãrei componente conexe. Procedura care face aceastã parcurgere în adâncime este DFS1. Vectorul Comp reþine componenta conexã din care face parte fiecare nod. C este numãrul de componente conexe al grafului.

Procedura Greedy determinã un cuplaj iniþial oarecare. Apoi, atâta timp cât cuplajul nu este maxim, se încearcã gãsirea unui drum de creºtere în fiecare componentã. Procedura care cautã acest drum de creºtere este DFS2. Nodul de plecare pentru procedurã trebuie sã fie un nod necuplat. Dacã nu se gãseºte un nod necuplat sau un drum de creºtere în componenta conexã curentã, atunci cuplajul asociat acestei componente este maxim. Vectorul Max este de tip boolean; Max[i] reþine dacã cuplajul asociat componentei conexe i este maxim sau nu. Dacã toate cuplajele componentelor sunt maxime variabila Maxim devine TRUE ºi programul se terminã cu afiºarea cuplajului.

Vectorul Cuplat reþine cuplajul; astfel, Cuplaj[i] este nodul cu care este cuplat nodul i. Numãrul de muchii din cuplaj este reþinut în variabila M.

Sã analizãm complexitatea acestui algoritm. Notãm cu m, numãrul de muchii al grafului ºi cu n, numãrul de noduri. O parcurgere în adâncime într-un graf este O(m+n). Chiar dacã se face o parcurgere în adâncime pentru fiecare componentã conexã, complexitatea adunatã a parcurgerilor este tot O(m+n).

Sã vedem acum complexitatea fiecãrei operaþii efectuate de program:

● operaþia de citirea a grafului este O(m)

● determinarea componentelor conexe este O(m+n), fiind vorba de o parcurgere în adâncime a fiecãrei componente

● procedura Greedy este O(m)

● fiecare cãutare a unui drum de creºtere este O(m+n). Dacã notãm cu M, numãrul de muchii al cuplajului maxim ºi cu M1, numãrul de muchii al cuplajului iniþial, operaþia de cãutare a unui drum de creºtere se va efectua de M-M1 ori.

Adunând, rezultã o complexitate totalã O((M-M1)(m+n)+(m+n)+m+m). Termenul dominant este (M-M1)⋅ (m+n). Dupã cum observãm timpul de calcul al algoritmului depinde de cât de bun este cuplajul iniþial. În cazul cel mai defavorabil, cuplajul iniþial va avea 0 muchii ºi cel final, n, caz în care timpul de calcul va fi O(n⋅ (m+n)). În practicã însã, dacã se foloseºte un algoritm greedy bun, cuplajul determinat de acesta este foarte aproape de cuplajul maxim. De exemplu, cu 2-3 muchii mai puþin decât cuplajul maxim, la un graf cu 10000 de noduri. Timpul de calcul în acest caz se apropie de O(m+n).

program Cuplaj_Maxim;

type Graf=array [1..100,1..100] of integer;

var G :Graf; n, k, C, M, i, j :integer; NrV, Comp, Cuplat :array [1..100] of integer; Parcurs :array [1..100] of boolean; Primul, GasitDrum :boolean; Gasit, Maxim :boolean; Max :array [1..100] of boolean;

procedure CitireGraf;

var F :text; nrvec, i, j :integer;begin assign(F,'input.txt'); reset(F); readln(F,n); readln(F,k); for i:=1 to n do begin read(F,nrvec); NrV[i]:=nrvec; for j:=1 to nrvec do read(F,G[i,j]); readln(F); end; close(F);end;

procedure DFS1(Nod:integer);var i :integer;begin Comp[Nod]:=C; for i:=1 to NrV[Nod] do if Comp[G[Nod,i]]=0 then DFS1(G[Nod,i]);end;

procedure DFS2(Nod,Tip:integer);var Vec, i :integer;begin Parcurs[Nod]:=True; if Primul then begin Primul:=false; GasitDrum:=false; end else if Cuplat[Nod]=0 then begin GasitDrum:=true; M:=M+1 end; i:=0; while (i<NrV[Nod]) and not GasitDrum do begin i:=i+1; Vec:=G[Nod,i]; if Tip=0 then if not Parcurs[Vec] and (Cuplat[Vec]<>Nod) then

DFS2(Vec,1); if Tip=1 then if not Parcurs[Vec] and (Cuplat[Vec]=Nod) then DFS2(Vec,0); if GasitDrum and (Tip=0) then begin Cuplat[Nod]:=Vec; Cuplat[Vec]:=Nod; end; end;end;

procedure Greedy;var i, j :integer; Cup :boolean;begin for i:=1 to k do begin j:=0; Cup:=false; while (j<NrV[i]) and not Cup do begin j:=j+1; if Cuplat[G[i,j]]=0 then begin Cup:=true; M:=M+1; Cuplat[i]:=G[i,j]; Cuplat[G[i,j]]:=i end end endend;

begin CitireGraf; FillChar(Comp,2*n,0); FillChar(Cuplat,2*n,0); FillChar(Max,2*n,0); M:=0; i:=1; C:=0; while i<=n do begin C:=C+1; DFS1(i); if NrV[i]=0 then Max[C]:=true;

while (i<=n) and (Comp[i]>0) do i:=i+1; end; Greedy; while not Maxim do begin Maxim:=true; for i:=1 to C do if not Max[i] then begin Maxim:=false; j:=0; Gasit:=false; while (j<n) and not Gasit do begin j:=j+1; if (Comp[j]=i) and (Cuplat[j]=0) then begin Gasit:=true; Primul:=true; FillChar(Parcurs,2*n,0); DFS2(j,0); if not GasitDrum then Max[i]:=true; end; end; if not Gasit then Max[i]:=true; end; end; writeln('Numarul de muchii din cuplaj este ',M); writeln('Muchiile din cuplaj sunt: '); for i:=1 to k do if Cuplat[i]>0 then writeln(i,' ',Cuplat[i])end.

Aplicaþie

Enunþ. Un numãr de c critici literari ºi-au spus, fiecare, pãrerea în chestiunea: "Care din cele r romane cu succes de public sunt, de fapt, capodopere?". Opþiunile lor au stârnit discuþii aprinse în masele largi de cititori. Momentul este speculat de cele p=c div 2 posturi de televiziune, care decid sã organizeze, simultan ºi separat, talk-show-uri având ca invitaþi câte doi critici.

Televiziunile plãtesc criticilor exclusivitatea - deci nici un critic nu poate apãrea la douã posturi diferite -, dar cu sume atât de mari, încât niciuna nu-ºi permite sã "deþinã", dacã poate, decât exact doi critici. Cum însã sponsorii ºi clienþii la spaþiile publicitare ale televiziunilor cer insistent ca înainte ºi dupã reclamele lor, în emisiuni sã nu mai existe certuri sau momente tensionate, fiecare post de televiziune e obligat sã invite critici cu pãreri apropiate, dar nu identice, asupra romanelor-capodoperã. Condiþia este ca pentru oricare doi critici invitaþi la acelaºi post, opþiunile sã difere pentru exact un roman.

Dându-se c, r ºi lista de capodopere propuse de fiecare critic sã se determine numãrul maxim de emisiuni care se pot realiza ºi criticii care apar în aceste emisiuni.

Intrare:

Fiºierul CRITICI.IN conþinând:

● pe prima linie, numãrul de critici c ºi numãrul de romane r, separate prin spaþiu;

● pe linia numãrul i+1, cu i=1..c, lista capodoperelor propuse de criticul i, sub forma unui ºir de cel mult r numere naturale diferite între ele, cuprinse între 1 ºi r ºi separate prin spaþiu.

Ieºire:

Fiºierul CRITICI.OUT, conþinând:

● pe prima linie, numãrul t de posturi de televiziune care pot realiza talk-show-uri în soluþia descrisã de fiºier;

● pe fiecare linie din urmãtoarele t, numerele de ordine ale celor doi critici invitaþi de câte un post de televiziune dintre cele ce pot organiza talk-show în soluþia datã.

Exemplu:

CRITICI.IN

4 413 1 44 12 1

CRITICI.OUT

2

1 42 3

Olimpiada Naþionalã de Informaticã 1998

Clasa a XI-a

Rezolvare. Construim un graf G cu c noduri în care existã muchie între nodurile i ºi j dacã criticul i poate realiza o emisiune împreunã cu criticul j. Condiþia pentru ca doi critici sã poatã realiza o emisiune împreunã este ca opþiunile lor sã difere exact asupra unui roman. Rezultã cã unul dintre critici trebuie sã aibã cu un roman în plus în lista de capodopere faþã de celãlalt ºi restul listei sã fie comun.

Exemplu: criticul 1: 3 4 8 7 2

criticul 2: 9 4 8 3 2 7

Opþiunile lor diferã numai asupra romanului 9.

Împãrþim cei t critici în douã mulþimi, M1 ºi M2, prima conþinând criticii ale cãror liste de capodopere au un numãr par de romane ºi cea de-a doua pe cei cu numãr impar. Doi critici din aceeaºi mulþime nu pot face o emisiune împreunã pentru cã diferenþa dintre numãrul de capodopere din listele lor este parã ºi dupã cum am stabilit mai sus aceastã diferenþã trebuie sã fie 1. Rezultã cã între douã noduri din M1 sau douã noduri din M2 nu poate exista muchie, deci graful este bipartit.

Acum, este clar cã problema se reduce la problema cuplajului bipartit maxim. Avem un graf bipartit G cu c noduri. Trebuie sã alegem un numãr maxim de muchii (emisiuni) din acest graf, iar aceste muchii nu trebuie sã aibã vreun capãt comun (sã nu existe un critic care apare în douã emisiuni).

[ Capitolul 9 ]

[ Cuprins ]

Bibliografie

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. The MIT Press, 1990.

2. Donald. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley. Third edition, 1998.

3. K. Thulasiraman, M.N.S. Swamy. Graphs: Theory and Algorithms. John Wiley & Sons, Inc., 1992.

4. Tudor Sorin. Tehnici de programare. L&S Infomat, 1996.

Batog, Culegere de probleme de informatica [RO]

Documents

Transcript of Batog, Culegere de probleme de informatica [RO]