PORTOFOLIU INFORMATICA

45
Profesor: Gelu Tomsa Elev: Timeea Szatmari Clasa: a XI-a B Semestrul I

description

PORTOFOLIU INFORMATICA. Profesor: Gelu Tomsa Elev: Timeea Szatmari Clasa: a XI-a B Semestrul I. GRILE. 1. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele - PowerPoint PPT Presentation

Transcript of PORTOFOLIU INFORMATICA

Page 1: PORTOFOLIU   INFORMATICA

Profesor: Gelu TomsaElev: Timeea SzatmariClasa: a XI-a BSemestrul I

Page 2: PORTOFOLIU   INFORMATICA

GRILE

Page 3: PORTOFOLIU   INFORMATICA

• 1. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru• litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele• opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.• Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e? • a. 9 b. 15 c. 12 d. 20

• 1. b a b e• 2. b a c e• 3. b a d e• 4. b b b e• 5. b b c e• 6 .b b d e• 7. b c b e• 8. b c c e• 9. b c d e 10. b d b e 11. b d c e 12. b d d e 13. b e b e 14. b e c e 15. b e d e • 15 variante => Varianata b)15

Page 4: PORTOFOLIU   INFORMATICA

• 2.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru

litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

• opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este ultimul cuvânt generat?

• a. Edcb b. eeee c. edde d. Eded

• 5111 eaaa F• 5112 eaab F• 5113 eaac F• 5114 eaad F• 5115 eaae F• 5555 eeee F• 5554 eeed F• 5545 eede F• 5454 eded A• 5445 edde F • Varianta: d) eded – ultimul cuvant generat

Page 5: PORTOFOLIU   INFORMATICA

• • 3.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru• litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

• opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este penultimul cuvânt generat?

• a. edec b. eded c. edde d. edcb

• Abab• Abac• Abad• Abba• Abbb• Abbc• Abbd• Abbe• ……………….• Edeb – antepenultimul cuvant generat

• edec – penultimul cuvant generat

• eded – ultimul cuvant generat

• Varianta : a)edec

Page 6: PORTOFOLIU   INFORMATICA

• • 4.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte

patru litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

• opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este antepenultimul cuvânt generat?

• a. edde b. eddb c. edeb d. edcb

• Abab• Abac• Abad• Abba• Abbb• Abbc• Abbd• Abbe• ……………….

• Edeb – antepenultimul cuvant generat• edec – penultimul cuvant generat • eded – ultimul cuvant generat

Varianta: c) edeb - antepenultimul cuvant generat

Page 7: PORTOFOLIU   INFORMATICA

• 5.Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din• mulţimea {1,2,3,7}, numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine:

• 123, 127, 137, 237. Dacă se utilizează exact aceeaşi metodă pentru a genera numerele naturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8}, câte dintre numerele generate au prima cifră 2 şi ultima cifră 7?

• a. 8 b. 3 c. 4 d. 6

• 2345• 2346

• 2347• 2348• 2456

• 2457• 2458

• 2567• 2568

• 2578 Varianta: b)3

Page 8: PORTOFOLIU   INFORMATICA

6.Utilizând metoda backtracking sunt generate numerele de 3 cifre, având toate cifrele distincte şi cu proprietatea că cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele şase soluţii generate sunt, în această ordine, 103, 105, 107, 109,123, 125, care este a zecea soluţie generată?

a. 145 b. 147 c. 230 d. 149

103 105 107 109• 123 125 127 129

• 143 145 147 149

• Varianta: a) 145

Page 9: PORTOFOLIU   INFORMATICA

• 7.Folosind tehnica bactracking un elev a scris un program care generează toate numerele de câte n cifre (0<n≤9), cifrele fiind în ordine strict crescătoare. Dacă n este egal cu 5, scrieți

• în ordine crescătoare toate numerele având cifra unităților 6, care vor fi generate de

• program.

• Rezolvare:

• 12346• 12356• 12456• 13456• 23456

Page 10: PORTOFOLIU   INFORMATICA

• 8.Utilizând metoda backtracking sunt generate numerele de 3 cifre care au cifrele în ordine crescătoare, iar cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că

• primele cinci soluţii generate sunt, în această ordine: 123, 125, 127, 129, 145, care este• cel de al 8-lea număr generat?

• a. 169 b. 149 c. 167 d. 147

Rezolvare:

123 125 127 129 145 147 149

167 169

189 Varianta: c)167

Page 11: PORTOFOLIU   INFORMATICA

• 9.Utilizând metoda backtracking sunt generate în ordine crescătoare toate numerele de 3• cifre, astfel încât cifrele sunt în ordine crescătoare, iar cifrele aflate pe poziţii consecutive• sunt de paritate diferită. Ştiind că primele trei soluţii generate sunt, în această ordine, 123,• 125, 127, scrieţi toate numerele generate care au suma cifrelor egală cu 12.

• Rezolvare:

• 123 125 127 129 345 347 349 • 145 147 149 567 569• 167 169 789• 189 • • 1+2+3=6 1+4+7=12 3+4+5=12 7+8+9=24• 1+2+5=8 1+4+9=14 3+4+7=14• 1+2+7=10 1+6+7=14 3+4+9=16• 1+2+9=12 1+6+9=16 5+6+7=18• 1+4+5=10 1+8+9=18 5+6+9=20• • 129 , 147 , 345

Page 12: PORTOFOLIU   INFORMATICA

• 10. Un elev a scris un program care, folosind metoda backtracking, generează toate numerele• de câte 5 cifre, cifrele fiind în ordine strict crescătoare. Scrieţi toate numerele generate de

• program care au prima cifră 5.

• Numarul generat este 56789.

Page 13: PORTOFOLIU   INFORMATICA

• 11. Un algoritm de tip backtracking generează, în ordine lexicografică, toate şirurile de 5 cifre ,0• şi 1 cu proprietatea că nu există mai mult de două cifre 0 pe poziţii consecutive. Primele 7

• soluţii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a 8-a soluţie generată de acest algoritm?

• a. 01110 b. 01100 c. 01011 d. 01101

• 00100 100• 00101 101• 00110 110• 00111 111• 01001 1001• 01010 1010• 01011 1011• 01110• • Varianta a) 01110

Page 14: PORTOFOLIU   INFORMATICA

• 12.Pentru a scrie valoarea 10 ca sumă de numere prime se foloseşte metoda backtracking şi

• se generează, în această ordine, sumele distincte: 2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7,

• 5+5. Folosind exact aceeaşi metodă, se scrie valoarea 9 ca sumă de numere prime. Care

• sunt primele trei soluţii, în ordinea generării lor?

• Suma de numere pt val 10: Suma de numere pt val 9:• 2+2+2+2+2 2+2+2+3• 2+2+3+3 2+2+5• 2+3+5 2+7• 3+7 3+3+3 => 9• 5+5

Page 15: PORTOFOLIU   INFORMATICA

• 13.Trei băieţi, Alin, Bogdan şi Ciprian, şi trei fete, Delia, Elena şi Felicia, trebuie să• formeze o echipă de 3 copii, care să participe la un concurs. Echipa trebuie să fie mixtă• (adică să conţină cel puţin o fată şi cel puţin un băiat). Ordinea copiilor în echipă este• importantă deoarece aceasta va fi ordinea de intrare a copiilor în concurs (de exemplu• echipa Alin, Bogdan, Delia este diferită de echipa Bogdan, Alin, Delia). Câte echipe• se pot forma, astfel încât din ele să facă parte simultan Alin şi Bogdan?

• 1) Alin,Bogdan,Delia / Alin,Delia,Bogdan• 2)Bogdan,Alin,Delia / Bogdan,Delia,Alin• 3)Delia,Alin,Bogdan / Delia,Bogdan,Alin• 4)Alin,Bogdan,Elena / Alin,Elena,Bogdan• 5)Bogdan,Alin,Elena / Bogdan,Elena,Alin• 6)Elena,Alin,Bogdan / Elena,Bogdan,Alin• 7)Alin,Bogdan,Felicia / Alin,Felicia,Bogdan• 8)Bogdan,Alin,Felicia / Bogdan,Felicia,Alin• 9)Felicia,Alin,Bogdan / Felicia,Bogdan,Alin• • 9x2=18 echipe Raspuns:18 echipe

Page 16: PORTOFOLIU   INFORMATICA

• 14.Utilizând metoda backtracking se generează permutările cuvântului info. Dacă primele trei

• soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie? • a. Foin b. fnoi c. Foni d. Ifon

• INFO -1234• FINO-3124• FION-3142• FNIO-3214• FNOI-3241

• Varianta b)FNOI

Page 17: PORTOFOLIU   INFORMATICA

• 15.Câte numere cu exact două cifre pot fi construite folosind doar cifre pare distincte?

• a. 12 b. 14 c. 20 d. 25

• 24 26 28• 42 46 48• 62 64 68• 82 84 86

Varianta a) 12

Page 18: PORTOFOLIU   INFORMATICA

• 16.Un algoritm generează în ordine crescătoare toate numerele de n cifre, folosind doar cifrele 3, 5 şi 7. Dacă pentru n=5, primele 5 soluţii generate sunt 33333, 33335, 33337,33353, 33355, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.

• 33333 , 33335 , 33337 , 33353 , 33355 ….

• …………..• 77773 , 77775 , 77777

Page 19: PORTOFOLIU   INFORMATICA

17.Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Ştiind că primele 5 soluţii generate sunt 56789,46789, 45789, 45689, 45679, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.

• 12347 , 12346 , 12345

Page 20: PORTOFOLIU   INFORMATICA

• 18.Un algoritm generează, în ordine lexicografică, toate şirurile alcătuite din câte n cifre binare (0 şi 1). Ştiind că pentru n=5, primele 4 soluţii generate sunt 00000, 00001, 00010, 00011,precizaţi care sunt ultimele 3 soluţii generate, în ordinea obţinerii lor.

• Rezolvare:

• 00000, 01001,• 00001, 01010,• 00010, 01011,• 00011, 01100,• 00100, 01101,• 00101, 01110,• 00110 01111• 00111, ……………• 01000, …………. 11101,111101,11111

Page 21: PORTOFOLIU   INFORMATICA

• 19.Un algoritm generează în ordine crescătoare, toate numerele de n cifre (n<9), cu cifre distincte, care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate

• sunt 10325, 10327, 10329, 10345, 10347, precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.

• 10325 , • 10327, 10329 , 10345 , 10347 , 10349 , 10365 , 10367 , 10369 , 10385 , 10387, 10389. 10349,10365,10367

Page 22: PORTOFOLIU   INFORMATICA

• 20.Un algoritm generează în ordine descrescătoare, toate numerele de n cifre (n<9), cu cifrele• în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5, primele

• 5 soluţii generate sunt 56789, 45789, 45679, 45678, 36789, precizaţi care sunt

• următoarele 3 soluţii generate, în ordinea obţinerii lor.

• 56789 • 45789 • 45679 • 45678 • 36789

• 35679 • 35678 • 34789 • 34679

• 35679,35678,34789

Page 23: PORTOFOLIU   INFORMATICA

• • 21.Următoarele probleme se referă la mulţimea de numere reale M={x1, x2, …, xn} (n>1000).• Care dintre acestea, comparativ cu celelalte, admite un algoritm care se încheie după un

• număr minim de paşi? • a. sortarea elementelor mulţimii M • b. generarea elementelor produsului• cartezian M x M• c. determinarea elementului minim al• mulţimii M• d. generarea tuturor permutărilor mulţimii M

Raspunsul corect este varianta: • d) generarea tuturor permutarilor multumii M

Page 24: PORTOFOLIU   INFORMATICA

• • 22.. In timpul procesului de generare a permutărilor mulţimii {1,2,…,n} prin metoda

• backtracking, în tabloul unidimensional x este plasat un element xk (1≤k≤n). Acesta este

• considerat valid dacă este îndeplinită condiţia:

• a. xk∉{x1, x2, …, xk-1}• b. xk≠xk-1• c. xk∉{x1, x2, …, xn}• d. xk≠xk-1 şi xk≠xk+1

• {1,2,…,n}• xk= {1<=k<=n}• • Varianta c) xk∉{x1, x2, …, xn}

Page 25: PORTOFOLIU   INFORMATICA

• • 23.Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare având

cifrele ordonate• strict crescător, este echivalent cu algoritmul de generare a:

• a. submulţimilor unei mulţimi cu 5 elemente• b. produsului cartezian a unor mulţimi de• cifre• c. aranjamentelor de 9 elemente luate câte 5• d. combinărilor de 9 elemente luate câte 5

Raspunsul corect este: • d) combinarilor de 9 elemente luate cate 5

Page 26: PORTOFOLIU   INFORMATICA

• 24.Generând şirurile de maximum 3 caractere distincte din mulţimea

{A,B,C,D,E}, ordonate lexicografic, obţinem succesiv: A, AB, ABC, ABD,…. Ce şir va fi generat imediat după BAE? (4p.)

• a. BCA• b. CAB• c. BC • d. BEA

• A• AB• ABC• ABD• ……………….• BAE

• BC Varianta c)BC

Page 27: PORTOFOLIU   INFORMATICA

PROBLEME

Page 28: PORTOFOLIU   INFORMATICA

• 1)Generarea produsului cartezian• Fiind date n multimi A1,A2,...,An ,sa se scrie un algoritm de backtracking ne-recursiv care

afiseaza elementele produsului cartezian A1*A2*...* An.•  • program RIV_5; {produs cartezian nerecursiv}• type vector=array [1..25] of integer;• var st,nr:vector; n:integer; {st=vectorul stiva}•  • procedure initializari; {initializeaza stiva si citeste datele de intrare}• var i:integer;• begin• write ('Numarul de multimi n='); readln (n);• for i:=1 to 25 do st[i]:=0;• for i:=1 to n do• begin• write ( 'Cate elemente are multimea ',i,' : ' ); readln(nr[i]);• end;• end; 

• procedure tipar (p:integer); {tipareste o solutie memorata in vectorul st}• var i:integer;• begin• for i:=1 to p do• write (st[i]:4,' ' );• writeln; end;

Page 29: PORTOFOLIU   INFORMATICA

procedure back; {implementeaza algoritmul ne-recursiv de backtracking}• var p:integer; {varful stivei }• begin• p:=1; st[p]:=0; {initializam primul nivel}• while p>0 do {cat timp stiva nu devine din nou vida}• begin• if st[p]<nr[p] then {daca mai exista vreo valoare neicercata pe nivelul p}• begin {punem pe nivelul p urmatoarea valoare din multimea solutiilor posibile }• st[p]:=st[p]+1;• if true then {daca mai exista vreo valoare neincercata pe nivelul p}• if p=n then {daca solutia este si finala}• tipar(p) {tiparim solutia}• else• begin• p:=p+1; st[p]:=0; {trecem la nivelul urmator, pe care il re-initializam}

end;• end;• else {adica pe nivelul p nu se mai poate incerca nici o valoare}• p:=p-1; {pasul inapoi la nivelul anterior}• end;• end; begin• initializari;• back; readln; end. 

Page 30: PORTOFOLIU   INFORMATICA

• 2)Generarea combinarilor• Fiind date doua numere naturale n si k , sa se genereze toate combinarile de n elemente • luate cate k.•  • program RIV_6; {combinari de n cate k ne-recursiv}• type vector=array [1..25] of integer;• var st:vector; n,k:integer; {st=vectorul stiva}•  • procedure initializari ; {initializeaza stiva si citeste n si k }• var i:integer;• begin• repeat• write('n='); readln (n);• write('k='); readln (k);• until n>=k;• for i:=1 to 25 do st[i]:=0;• end;•  • procedure tipar (p:integer); {tipareste o solutie memorata in vectorul st}• var i:integer;• begin• for i:=1 to p do• write(st[i]:4,' ');• writeln; end;•  

Page 31: PORTOFOLIU   INFORMATICA

• function valid (p:integer): boolean ; • {testeaza daca valoarea st[p] a generat o solutie valida, returnand true

sau false}

• var i:integer; ok:boolean;• begin• {valoarea de pe nivelul p nu trebuie sa se mai gaseasca pe niciunul dintre

nivelele anterioare 1,2,...,p-1}• • ok:=true;• for i:=1 to p-1 do• if st[p]<=st[i] then• ok:=false;• valid:=ok;• end;

Page 32: PORTOFOLIU   INFORMATICA

• procedure back; {implementeaza algoritmul ne-recursiv de backtracking}• var p:integer; {varful stivei}• begin• p:=1; st[p]:=0; {initializam primul nivel}• while p>0 do {cat timp stiva nu devine din nou vida}• begin• if st[p]<n then {daca mai exista vreo valoare neicercata oe nivelul p}• begin {punem pe nivelul p urmatoarea valoare din multimea solutiilor

posibile}• st[p]:=st[p]+1;• if valid(p) then {daca solutia (st[1], st[2],...,st[p]) este valida}• if p=k then {daca solutia esti si finala}• tipar(p) {tiparim solutia}• else • begin• p:=p+1; st[p]:=0; {trecem la nivelul urmator, pe care il re-initializam}• end;• end• else {adica pe nivelul p nu se mai poate incerca nici o valoare}• p:=p-1; {pasul inapoi la nivelul anterior}• end;• end; begin• initializari;• back; end.•  

Page 33: PORTOFOLIU   INFORMATICA

• 3.Generarea aranjamentelor• Se citesc n si p. Sa se genereze toate aranjamentele de n luate cate p.

• program aranjamente;• type stiva-array [1..100] of integer;• var st:stiva ;• n,k,p:integer;• as,ev:boolean;•  • procedure init(k:integer; var st:stiva);• begin• st[k]:=0;• end;• end. 

Page 34: PORTOFOLIU   INFORMATICA

procedure succesor(var as:boolean; var st:stiva; k:integer);• begin• if st[k]<n• then begin• st[k]:=st[k]+1; as:=true• end• else as:=false• end;•  • procedure valid (var ev:boolean; st:stiva; k:integer);• var i:integer;• begin• ev:=true;• for i:=1 to k-1 do if st[k]=st[i] then ev:false• end;•  

•  

Page 35: PORTOFOLIU   INFORMATICA

• function solutie(k:integer):boolean;• begin• solutie:=(k=p)• end;•  • procedure tipar;• var i:integer;• begin• for i:=1 to p do write (st[i]);• writeln• end;• begin• write('N='); readln(n);• write ('P='); readln(p);• k:=1; init (k,st);• while (k>0) do• begin• repeat • succesor(as,st,k);• if as then valid(ev,st,k);• until (not as) or (as and ev);• if as then• if solutie(k)• then tipar• else begin• k:=k+1;• init(k,st)• end• else k:=k-1

• rnd,• end.

Page 36: PORTOFOLIU   INFORMATICA

• 4.Problema colorarii hartilor• Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult 4 culori, astfel

incat doua tari cu frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai 4 culori pentru ca orice harta sa poata fi colorata.

•  • program culori;• type stiva=array [1..100] of integer;• var st:stiva;• i,j,n,k:integer;• as,ev:boolean;• a:array [1..20,1..20] of integer;•  • procedure init (k:integer; var st:stiva);• begin• st[k]:=0;• end;•  • procedure succesor(var as:boolean; var st:stiva; k:integer);• begin• if st[k]<4• then • begin• st[k]+1; as:=true• end• else as:=false• end;

Page 37: PORTOFOLIU   INFORMATICA

procedure valid(var ev:boolean; st:stiva; k:integer);• var i:integer;• begin• ev:=true;• for i:=1 to k-1 do if (st[i]=st[k]) and (a[i,k]=1) then ev:=false• end;•  function solutie(k:integer):boolean;• begin• solutie:=(k=n)• end; procedure tipar;• var i:ineteger;• begin• for i:=1 to n do writeln( 'Tara=',i,'; culoarea=',st[i]);• writeln('--------------')• end;•  begin• write('Numarul de tari='); readln(n);• for i:=1 to n do• for j:=1 to i-1 do• begin• write('a[',i,',',j,']='); readln(a[i,j]);• a[j,i]:= a[i,j]• end;• k:=1; init (k,st);

Page 38: PORTOFOLIU   INFORMATICA

• while k>0 do• begin• repeat • succesor(as,st,k);• if as then valid(ev,st,k);• until (not as) or (as and ev);• if as then• if solutie(k)• then tipar• else• begin• k:=k+1; init(k,st)• end• else k:=k-1• end;• end.

Page 39: PORTOFOLIU   INFORMATICA

• • 5.Problema celor n dame•

• Fiind data o tabla de sah n*n , se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie,coloana sau diagonala(damele sa nu se atace reciproc).

•  

• • Program damer;• type tabla=array[1..20] of ineteger;• var t:tabla;• i,n:ineteger;•   procedure tipar;• var i:integer;• begin• for i:= 1 to n do write (t[i]);• writeln;• end;•  

Page 40: PORTOFOLIU   INFORMATICA

• procedure dame(k:integer);• var i,j:ineteger;• corect:boolean;• begin• if k=n+1• then tipar• else• begin• for i:=t[k]+1 to n do• begin• t[k]:=i; • coresct:=true;• for j:=1 to k-1 do• if (t[j]=t[k]) or (abs(t[k]-t[j])=(k-j) )• then corect:=false; if corect then dame (k+1)• end;• end;• t[k]:=0;• end;•  begin• write('n='); readln(n);• for i:=1 to n do t[i]:=0;• dame(1)• end.

Page 41: PORTOFOLIU   INFORMATICA

•  

• 6.Generarea partitiilor unui numar natural.

• Se citeste un numar natural n. Se cere sa se tipareasca toate modurile de descompunere a sa ca suma de numere naturale.

• program part_n;•  • type solutie=array[1..20] of integer;• var n:integer;• s:solutie;•  • procedure tipar(k:integer);• var i:integer;• begin• for i:=1 to k do write (s[i]);• writeln;• end;•  

Page 42: PORTOFOLIU   INFORMATICA

• procedure part(k,v:integer);• var i:integer;• begin• s[k]:=v;• tipar(k);• for i:=1 to s[k]-1 do• begin• s[k]:=s[k]-i;• part(k+1,i);• s[k]:=s[k]+i• end;• end;•  • begin• write('n='); readln(n);• part (1,n)• end.

Page 43: PORTOFOLIU   INFORMATICA

• 7.Plata unei sume cu bacnote de valori de date.

• Se dau suma s si n tipuri de monede avand valori de a1,a2, ... , an lei. Se cer toate modalitatile de plata a sumei s utilizand aceste monede.

•  • program bacnote;• uses crt;• type vector=array[1..9] of integer;• var sol,a,b:vector;• n,i,s:integer;•  • procedure tipar(k:integer);• begin• writeln('Solutie');• for i:=1 to k do• if sol[i]<>0 then writeln(sol[i],' becnote de ',a[i]);• readln;• end;•  

Page 44: PORTOFOLIU   INFORMATICA

• procedure plata (k,s0:integer);• begin• while (sol[k]<b[k]) and (s0+a[k] <=s) do• begin• sol[k]:=sol[k]+1;• if sol[k]>0 then s0:=s0 + a[k];• if s0=s then tipar(k)• else• if k<n then plata(k+1,s0)• end;• sol[k]:=-1;• end;• begin• clrscr;• write('cate tipuri de bacnote avem? '); readln(n);• write('suma='); readln(s);• for i:=1 to n do• begin• write('valoarea monedei de tipul', i,' ');• readln (a[i]);• b[i]:=s div a[i];• sol[i]:=-1;• end;• plata(1,0); end.

Page 45: PORTOFOLIU   INFORMATICA

•  

• 8.Saritura calului• Se da o tabla de sah de dimensiune n*n. Un cal se afla in unul

dintre colturile tablei. Sa se gaseasca toate modalitatile prin care acesta poate sa parcurga intreaga tabla fara sa treaca de doua ori prin acelasi loc.

•  • program RIV_13;• var st:array[1..64,1..2] of integer;• n,i:integer; vecini:array[1..8,1..2] of integer; f:text;• function valid(p:integer): boolean;• var k:integer;• begin• valid:=false;• if (st[p,1]>=1) and (st[p,1]<=n) and (st[p,2]>=1) and (st[p,2]<=n);• then begin {daca pozitia adaugata pe stiva reprezinta o saritura in interiorul tablei de sah si daca nu a mai

fost vizitata in cursul constructiei drumului curent, atuncia ea este valida si se mai poate merge mai departe}

• valid:=true;• for k:=1 to p-1 do• if (st[p,1]=st[k,1]) and (st[p,2]=st[k,2]) • then valid:= false;• end; end.•