probleme backtraking bac

[Maria bondar 0]

Ma poate ajuta cineva cu algoritmul pentru problemele:

1.Intr-un penar sunt 8 creioane: 3 rosii , 2 albastre si 3 negre. Daca scoatem 5 creioane din penar , cate posibilitati sunt sunt ca cel putin 2 dintre ele sa fie rosii ?

 

2.sa se genereze toate permutarile multimii (1, 2, 3, 4).Daca primele 3 permutari sunt : 1234, 1243, 1324, precizati care este permutarea generata imediat dupa 3412 : 3214

3413

4123

3421

[Redondo 223]

astea-s putin mai grele decat cele care se dau la bac

 

1) pui intr-un vector de caractere creioanele. primele 3 sunt 'r', apoi 2 sunt 'a' , si 3 'n'. si faci back pe acest vector. adica iei indicii vectorului(1..8 ) si umpli stiva. maximul(nivelul/varful) stivei sa fie 5. cand se umple stiva(la 5) numeri cate 'r' ai in stiva(de fapt in stiva numeri indicii care pot fi 'r' adica 1, 2 sau 3). daca sunt cel putin 2 valori care il reprezinta pe 'r' atunci incrementezi un nr global. acel nr e rezultatul.

 

2)aici nu trebuie sa faci back. nu ai nevoie de calculator. o iei logic: dupa 3412 (2 fiind ultimul nivel al stivei): in locul lui 2 va urma 3 care nu e bun pt ca 3413 nu e permutare, apoi 4 care iar nu e bun(din acelasi motiv), acum cobori in stiva, 1 devine 2 si stiva devine 342, urci in stiva, pui 1 rezulta 3421

 

daca totusi vrei sa faci back: pui conditia ca elementul pe care-l pui acum in stiva sa nu se mai gaseasca anterior(astfel gasesti o permutare deoarece intr-o permutare nu ai 2 elemente egale). stiva ta are 4 nivele. poti porni direct de la 3412. adica completezi stiva manual cu aceste valori

 

si la prima poti sa faci pe hartie. cel putin 2 inseamna 2 sau 3.

 

daca sunt 2 rosii: acestea 2 pot fi luate din cele 3 rosii in C₃² iar restul de 3(care au ramas) pot fi luate oricum din cele 5 care au ramas. deci rez. este C₃² inmultit cu C₅³

 

daca sunt 3. inseamna ca sunt toate cele rosii. restul de 2 creioane pot fi luate din restul de 5 in C₅² iar acest rezultat se aduna cu cel de sus pt ca pot fi 2 sau 3 rosii

Editat Noiembrie 25, 2012 de Redondo