aplicatii backtracking

Metoda Backtracking. Probleme propuse

Problema permutarilor primelor n numere
Problema aranjamentelor
Problema combinarilor
Permutari , aranjamente, combinari de numere.
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 un mesaj;
Problema turelor
Problema damelor
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.
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.

Ex n=3, p1=2, p2=3, p3=3 p4=4 Atunci:

{1,2} x {1,2,3} x {1,2,3}x{1,2,3,4}=

(1 1 1 1 ) (1 1 1 2 ) (1 1 1 3 ) (1 1 1 4 ) (1 1 2 1 ) (1 1 2 2 ) (1 1 2 3 ) (11 2 4 ) (1 1 3 1 )(1 1 3 2 ) (1 1 3 3 ) (1 1 3 4 )

(1 2 1 1 ) (1 2 1 2 ) (1 2 1 3 ) (1 2 1 4 ) (1 2 2 1 ) (1 2 2 2 ) (1 2 2 3 ) (1 2 2 4 ) (1 2 3 1 ) (1 2 3 2) (1 2 3 3 ) (1 2 3 4 )

(1 3 1 1 ) (1 3 1 2 ) (1 3 1 3 ) (1 3 1 4 ) (1 3 2 1 ) (1 3 2 2 ) (1 3 2 3 ) (1 3 2 4 ) (1 3 3 1 ) (1 3 3 2 ) (1 3 3 3 ) (1 3 3 4 )

(2 1 1 1 ) (2 1 1 2 ) (2 1 1 3 ) (2 1 1 4 ) (2 1 2 1 ) (2 1 2 2 ) (2 1 2 3 ) (2 1 24 ) (2 1 3 1 ) (2 1 3 2 ) (2 1 3 3 ) (2 1 3 4 )

(2 2 1 1 ) (2 2 1 2 ) (2 2 1 3 ) (2 2 1 4 ) (2 2 2 1 ) (2 2 2 2 ) (2 2 2 3 ) (2 2 2 4 ) (2 2 3 1 ) (2 2 3 2 ) (2 2 3 3 ) (2 2 3 4 )

(2 3 1 1 ) (2 3 1 2 ) (2 3 1 3 ) (2 3 1 4 ) (2 3 2 1 ) (2 32 2 ) (2 3 2 3 ) (2 3 2 4 ) (2 3 3 1 ) (2 3 3 2 ) (2 3 3 3 ) (2 3 3 4 )

N copii se aseaza in sir indian. Se cunosc numele celor n copii. Sa se gaseasca toate posibilitatile de aranjare in sir.
Gigel are n cartonase (n<=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?
Sa se genereze n perechi de paranteze care se inchid corect. Exemplu:
n=3: ( ( ( ) ) ) ( ( ) ( ) ) ( ) ( ( ) ) etc
Se cer toate solutiile de asezare in linie a m caini si n pisici astfel incat sa nu existe o pisica intre doi caini
Sa se genereze toate numerele palindrome de lungime n
Sa se genereze toate partitiile unui numar (sa se descompuna in suma de numere). Ex: n=4 Solutii:

1 1 1 1

1 1 2

1 3

2 2

Sa se decompuna un numar in suma de numere prime. Generati toate solutiile.

N copii se aseaza in cerc. Se cunosc numele celor n copii. Sa se gaseasca toate posibilitatile de rearanjare in cerc.
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.
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.
Se citeste un numar. Sa se genereze toate numerele avand aceleasi cifre ca el. Care este cel mai mare?
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.
Plata unei sume in bancnote de n tipuri. Solutia cea mai lunga (scurta)
Problema drapelelor. Sa se afiseze ca drapel
Sa se genereze anagramele unui cuv
Sa se genereze toate triunghiurile de perimetru n
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.
Sa se genereze toate matricile binare (avand 0 si 1) simetrice cu nxn componente.
Sa se genereze o secventa de n sunete avand lungimea p care respecto o anumita conditie
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.
Sa se genereze toate numerele de lungime n formate doar cu cifre pare / impare
Scrieti un program care sa afiseze toate numerele de n (n<=10) cifre, formate numai din cifre distincte si care sunt divizibile cu 4.
Sa se aranjeze in toate modurile elementele unui vector a[1],a[2]…a[n] formand secvente de lungime p, astfel incat fiecare element sa apara de cel mult doua ori
Sa se genereze toate cuvintele de lungime p, distincte / nedistincte, care se pot forma cu literele alfabetului dintr-o multime data
Pe o tabla de dimensiune nxn se gasesc n regi. Sa se gaseasca toate posibilitatile de aranjare a regilor pe tabla astfel incat oricare 2 regi sa nu se atace. Obs. Fiecare rege se va gasi pe alta linie.
Problema partitiilor unui numar
Submultimile unui numar
a) Fie sirul primelor n numare naturale (n citit de la tastatura). Sa se insereze inainte de fiecare semnul + sau minus. Pentru fiecare solutie astfel generata se va afisa valoarea expresiei. Ex pt n =3:

+1+2+3=6

+1+2-3=0

+1-2+3=2 etc

b) sa sedetermine solutiile pentru care expresia este egala cu x. Daca nu exista solutii sa se afiseze un mesaj

a) Fie n numare naturale (n citit de la tastatura) citite de la tastatura. Sa se insereze inainte de fiecare semnul + sau minus. Pentru fiecare solutie astfel generata se va afisa valoarea expresiei. Ex pt n =3 si numerele 2 5 4 se vor genera expresiile:

+2+5+4=11

+2+5-4=3

+2-5+4=1 etc.

b) sa sedetermine solutiile pentru care expresia este egala cu x. Daca nu exista solutii sa se afiseze un mesaj

La o cofetarie se comercializeaza n sortimente de prajituri. Sa se determine toate variantele de a face pachete cu cate p prajituri diferite. Scrieti un program care permite citirea de la tastatura a celor n sortimente de prajituri si afiseaza variantele solutie precum si numarul acestora.
Fiind data o multime de n cuburi, fiecare cub fiind caracterizat de lungimea laturii si culoarea sa, sa se scrie un program care sa genereze toate turnurile care se pot forma cu p cuburi astfel incat doua cuburi vecine sa nu aiba aceeasi culoare iar deasupra unui cub sa nu se poata aseza un cub cu latura mai mare.
Un grup de copii are la dispozitie n cartonase cu n cuvinte disticte pentru jocul "cerc de cuvinte". In acest joc un copil trebuie sa spuna un cuvant care sa aiba primele doua litere identice cu ultimele doua ale cuvantului spus de predecesorul lui. fiind dat un cuvant de inceput pentru joc, afisati varianta cu cele mai multe cuvinte care se pot obtine cu ajutorul cartonaselor date. Observatie: un sir de cuvinte nu va contine un cuvant de mai multe ori.
O persoana a uitat numarul de telefon al unui prieten. Stie doar ca numarul are 6 cifre, incepe cu 4 si contine 3 zerouri dintre care doua sunt alaturate. fisati toate variantele pe care trebuie sa le incerce pentru a vorbi cu prietenul sau.
La o masa rotunda sunt n persoane de diverse nationalitati, pentru fiecare persoana precizandu-se doua limbi straine cunoscute de ea. Se cere sa ajutati organizatorii mesei rotunde sa aranjeze persoanele astfel incat fiecare sa poata conversa atat cu cea din stanga cat si cu cea din dreapta.
Sa se genereze numerele mai mici decat n citit care trecute in baza 2 au in componenta lor exact p cifre de 1.
Teste la geografie. Pentru lucrarea de control profesoara de geografie a pregatit n teste. In clasa sunt p elevi (p>n). Sa se genereze toate posibilitatile de a imparti testele celor p elevi astfel incat fiecare test sa fie rezolvat de macar un elev.
Sa se genereze toate drapelele tricolore care se pot forma cu n culori (eventual impunand conditii : in mijloc sa fie o anumita culoare, o culoare sa nu stea langa alta culoare etc
Produsul cartezian a n multimi impunand conditia ca suma elementelor dintr-o solutie sa fie egala cu un S citit
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.
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
Sa se aranjeze n margele de m culori astfel incat oricare doua margele alaturate sa aiba culori diferite
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)
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
Sa se afiseze toate numerele de lungime p<=9 cu proprietatea ca au suma cifrelor egala cu x dat
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
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
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
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
Sa se genereze toate numerele de lungime n formate doar cu cifre pare / impare
Sa se genereze toate numerele de lungime n divizibile cu x dat
Sa se determine toate numerele de lungime n care sunt egale cu inversele lor
Sa se determine toate modurile in care poate fi capsat un bilet, stiind ca pozitiile posibile sunt de forma:

* * *

* * *

si se pot perfora p1<=k<=p2 puncte.

Biletul poate fi introdus pe oricare din fete.

1. 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

2. un pion se poate deplasa pe o tabla dreptunghiulara cate o casuta pe orizontala sau pe varticala. Se dau coordonatele initiale, coordonatele finale si de cate ori trebuie sa treaca pionul prin fiecare casuta. Sa se genereze toate solutiile. De fiecare data se afiseaza traseul de parcurs.

Exemplu

1 1 2 1 1 0

0 0 2 2 2 0

0 0 0 0 1 0

0 0 0 0 0 0

din 1 1 pana in 1 5 o solutie este:

1 1, 1 2, 1 3, 2 3, 2 4 , 2 5, 3 5, 2 5, 2 4, 2 3, 1 3, 1 4, 1 5.

Sa se genereze toate solutiile naturale nenule ale ecuatiei 4x+y+3yz=100
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.
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
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
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)
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.
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 Fie o hacomis voiajorul sa ajunga inapoi de unde a plecat. Casa de la care se pleaca este casa p.
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.
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.
Se citeste un numar natural. Sa se determine toate numerele avand aceleasi cifre sau o parte din cifre si care sunt divizibile cu p citit
Sa se determine toate numerele cu cifre distincte. Cate astfel de numere sunt?
Sa se genereze toate numerele avand cifre distincte de la 0 la p. Numarul de cifre poate fi >=1 si <= p+1. Cate astfel de numere sunt?
Sa se determine cate numere cu cifre distincte sunt.