Backtracking – probleme propuse

1. Sa se genereze cuvintele de k litere care incep cu o vocala si se termina cu o consoana.
2. N copii sunt pregatiti pentru ora de sport. Se cunoaste inaltimea fiecaruia. Trebuie format un rand cu m elevi astfel incat diferenta dintre 2 elevi asezati unul langa altul sa nu fie mai mare de 10 cm.
3. Sa se genereze toate sirurile de 5 cifre 0 si 1 astfel incat sa nu existe mai mult de doua cifre de 0 alaturate.
4. N persoane stau pe scaune numerotate de la 1 la N. Oricare doi vecini se ceartă. Să se afişeze toate posibilităţile de a-i reaşeza pe scaune astfel încât să nu fie 2 foşti vecini alăturaţi.
5. Se citesc de la tastatură n ( n divizibil cu 3) şi p, numere naturale nenule şi n numere întregi, cu cel mult cinci cifre. Scrieţi un program care afişează pe ecran toate modurile în care se pot afişa toate şirurile de p numere, în care orice număr dintre cele citite să apară o singură dată, astfel încât trei numere alăturate să fie aşezate în ordine crescătoare. Soluţiile se vor scrie pe o linie separate prin câte un spaţiu.
6. Scrieţi un program care afişează pe ecran toate modurile de a forma numere de forma abab divizibile cu 5 şi cu suma cifrelor egala cu S dat.
7. Dată o mulțime A de numere pozitive și un număr M, să se determine toate submulțimile lui A cu suma elementelor egala cu M.
8. Să se descompună un număr natural n în toate modurile posibile distincte ca sumă de numere prime (de exemplu, pentru n = 10 descompunerile sunt 2+2+2+2+2, 2+2+3+3, 2+3+5, 5+5,3+7).
9. Date n puncte în plan prin coordonatele carteziene, să se conecteze aceste puncte printr-o rețea liniară de lungime minimă 4 astfel incat prin fiecare punct sa apara in retea o singura data.
10. Să se determine toate partițiile unei mulțimi cu n elemente numerotate de la 1 la n.
11. Într-un grup de N persoane (numerotate de la 1 la N) fiecare persoană poate sa cunoasca una sau mai multe persoane din grup. Să se determine toate modurile în care cele N persoane se pot repartiza în echipe astfel încât orice persoană să fie cunoscută de cel puţin un membru din echipa respectiva.
12. Scrieţi un program care afişează pe ecran anagramele distincte ale unui cuvânt dat.
13. Scrieţi un program care afişează pe ecran permutarile primelor n numere natural.
14. Scrieţi un program care afişează pe ecran aranjamentede n luate cate m.
15. Scrieţi un program care afişează pe ecran combinaride n luate cate m.
16. Se citesc n numere. Sa se genereze toate secventele din exact m dintre ele (m<n) astfel incat secventele sa contina numere distincte si doua numere alaturate sa nu aiba aceeasi paritate. Daca nu exista solutii se va afisa mesajul „NU”;
17. Problema turelor.
18. Problema damelor.
19. N camile sunt numerotate de la 1 la n sunt aranjate in sir indian. Sa se rearanjeze camilele astfel incat fiecare camila sa aiba in fata o camila diferita de configuratia initiala.
20. Sa se genereze produsul cartezian a n multimi. Pentru fiecare multime se cunoaste numarul de elemente. Daca o multime a p elemente atunci va contine valorile de la 1,2 …la p.
21. N copii se aseaza in sir indian. Se cunosc numele celor n copii. Sa se gaseasca toate posibilitatile de aranjare in sir.
22. Gigel are n cartonase (<10). Pe fiecare este scrisa o cifra de la 1 la 9. Uilizand doua tipuri de cartonase cu + si – vrea sa obtina rezultatul 2. Care sunt solutiile pentru n citit?
23. Sa se genereze n perechi de paranteze care se inchid corect. Exemplu: n=3: ( ( ( ) ) ) ( ( ) ( ) ) ( ) ( ( ) ) etc.
24. Se cer toate solutiile de asezare in linie a m caini si n pisici astfel incat sa nu existe o pisica intre doi caini.
25. Sa se genereze toate numerele palindrome de lungime n.
26. Sa se genereze toate partitiile unui numar (sa se descompuna in suma de numere mai mici ca n).
27. Sa se decompuna un numar in suma de numere prime. Generati toate solutiile.
28. N copii se aseaza in cerc. Se cunosc numele celor n copii. Sa se gaseasca toate posibilitatile de rearanjare in cerc.
29. N copii se aseaza in sir indian. Se cunosc numele celor n copii. Sa se gaseasca toate posibilitatile de aranjare in sir astfel incat un baiat sa urmeze dupa cel mult doua fete alaturate.
30. Sa se genereze toate numerele de lungime n formate doar cu cifre impare.
31. N copii au fost asezati in sir indian. Se cunoaste configuratia initiala. Sa se reaseze copiii astfel incat fiecare copil sa urmeze dupa un alt copil, diferit de cel din configuratia initiala.
32. Se citeste un numar. Sa se genereze toate numerele avand aceleasi cifre ca el. Care este cel mai mare?
33. N copii au fost asezati in sir indian. Se cunoaste configuratia initiala. Sa se reaseze copiii astfel incat fiecare copil sa se situeze intre alti copii, diferiti de cei din configuratia initiala.
34. Plata unei sume in bancnote de n tipuri. Solutia cea mai lunga.
35. Sa se genereze anagramele unui cuvânt.
36. Sa se genereze toate triunghiurile de perimetru n.
37. Intre n persoane care stau pe scaune s-au iscat conflicte. Acestea stau pe scaune numerotate de la 1 la n. Scrieti un program care sa afiseze toate modurile posibile de reasezare a persoanelor astfel incat sa nu se gaseasca alaturi doua persoane in conflict.
38. Sa se genereze toate matricile binare (avand 0 si 1) simetrice cu nxn componente.
39. Sa se genereze o secventa de n sunete avand lungimea p care respectă o anumita conditie
40. La un spectacol trebuie sa interpreteze cate o poezie copiii A, B, C, D, E astfel incat copilul D sa recite inainte de A si B. Sa se genereze toate posibilitatile de recitare a poeziilor.
41. Sa se genereze toate cuvintele din multimea A cu n litere (citita ca un sir de caractere) , care nu contin doua vocale alaturate si in care fiecare litera sa apara cel mult o data.
42. Sa se genereze toate numerele de lungime n formate doar cu cifre pare.
43. Scrieti un program care sa afiseze toate numerele de n (nn). Sa se genereze toate posibilitatile de a imparti testele celor p elevi astfel incat fiecare test sa fie rezolvat de macar un elev.
44. Sa se genereze toate drapelele tricolore care se pot forma cu n culori .
45. Sa se genereze produsul cartezian a n multimi astfel încât suma elementelor dintr-o solutie sa fie egala cu un S citit de la tastatură.
46. Sa se genereze toate submultimile de cate k elemente care se pot forma cu numerele 1,2…n (sau a[1],a[2]…a[n]), cu conditia ca fiecare element sa fie divizibil cu un numar d dat.
47. Sa se rearanjeze elementele unui vector a[1],a[2]…a[n] in toate modurile posibile, astfel incat oricare doua alaturate sa nu fie consecutive in sirul initial
48. Sa se aranjeze n margele de m culori astfel incat oricare doua margele alaturate sa aiba culori diferite
49. Sa se genereze toate numerele de lungime p care sunt supermultiple de p (atat numerele cat si toate prefixele lor sa fie multiplu de p)
50. La un festival de muzica usoara s-au inscris n melodii codificate cu numere de la 1 la n. Stiind ca in prima zi intra in concurs k melodii, sa se afiseze toate posibilitatile de a stabili ordinea intrarii in concurs a melodiilor in prima zi, stiind ca melodiile de coduri c1 si c2 trebuie sa intre in prima zi, a doua respectiv penultima
51. Sa se afiseze toate numerele de lungime p<=9 cu proprietatea ca au suma cifrelor egala cu x dat.
52. Sa se afiseze toate submultimile cu p elemente dintre elementele a[1],a[2]…a[n] cu proprietatea ca suma elementelor din multime este un numar divizibil cu x dat.
53. Sa se afiseze toate modurile in care se poate forma un grup de p persoane dintr-un grup de n persoane, dintre care l persoane sa fie femei
54. La un concurs se prezinta n concurenti din m tari. Sa se stabileasca ordinea intrarii in concurs a celor n concurenti astfel incat doi concurenti din aceeasi tara sa nu urmeze unul dupa altul
55. Sa se aranjeze elementele multimii {A,R,G,V} in grupuri de cate n (n par) astfel incat doua caractere identice sa nu fie alaturate si R sa apara de exact n/2 ori
56. Sa se genereze toate numerele de lungime n formate doar cu cifre pare / impare
57. Sa se genereze toate numerele de lungime n divizibile cu x dat
58. Sa se determine toate numerele de lungime n care sunt egale cu inversele lor
59. Sunt 2n copii de inaltimi diferite. Sa se aseze copiii pe 2 randuri astfel:
– pe primul rand copiii sa fie asezati in ordinea crescatoare a inaltimii
– copiii de pe al doilea rand sa fie mai inalti decat cei din fata lor
60. Sa se genereze toate solutiile naturale nenule ale ecuatiei 4x+y+3yz=100
61. Sa se genereze toate codurile morse de lungime n coduri reprezentate prin ‚–‚ sau ‚.’ Astfel incat intr-o secventa sa nu existe doua puncte alaturate. Pentru fiecare semn se va genera un sunet.
62. Sa se genereze toate secventele in cod binar de lungime n. Pentru fiecare secventa se va genera numarul asociat in baza 10.Sa se genereze toate codurile
63. Sa se genereze toate numerele naturale ale caror cifre se gasesc printre cifrele lui x citit si au lungimea cel mult egala cu lungimea lui x. Cifrele se pot repeta
64. La Masa Rotunda sunt n cavaleri. Fiecare dintre ei are cel putin un dusman printre ceilalti. Sa se gaseasca toate posibilitatile de a-i aseza la masa astfel incat doi vavaleri dusmani sa nu fie vecini. Se citesc cele m perechi de dusmani de la tastatura (fisier)
65. Fie o harta cu n tari. M perechi de tari sunt vecine (se cunosc perechile de tari vecine). Sa se coloreze harta astfel incat oricare doua tari alaturate sa fie colorate diferit.
66. Un comis voiajor trebuie sa ajunga la n case. Intre cele n case exista m dumuri (un drum este dat ca o pereche de case vecine). Sa se genereze toate posibilitatile de parcurgere a celor n o singura data case astfel incat comis voiajorul sa ajunga inapoi de unde a plecat. Casa de la care se pleaca este casa p.
67. In cate moduri poate ajunge un pion de pe prima linie a unei table bidimensionale cu n linii si n coloane pe ultima linie a tablei. Se cunoaste coloana de plecare p. Pionul se poate deplasa numai pe o casuta alaturata si numai pe o linie mai mare.
68. Sa se determine partitiile unui numar pt care suma inverselor obtinute este subunitara. Ex. n=5 3+2=5 si 1/3+1/2=1 si <= p+1. Cate astfel de numere sunt?
69. Sa se determine cate numere cu cifre distincte sunt.
70. Plata unei sume in bancnote de n tipuri. Solutia cea mai scurta.
71. Sa se determine toate modurile in care poate fi capsat un bilet, stiind ca pozitiile posibile sunt de forma k*K si se pot perfora p<=k pozitii.
Pentru k=3 biletul apare astfel:
0 0 0
0 0 0
0 0 0
Daca p=2 o solutie poate fi:
* * 0
0 0 0
0 0 0

Despre scoalamultimedia
la 3 click distanta :)

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

%d blogeri au apreciat asta: