fBacktracking Generarea permutarilor, Problema celor n dame, Produsul cartezian a n multimi, Generarea aranjamentelor, permutarilor, problema comis-voiajorului referat




Backtracking Generarea permutarilor, Problema celor n dame, Produsul cartezian a n multimi, Generarea aranjamentelor, permutarilor, problema comis-voiajorului referat






Generarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii {1, 2, 3, …,n}.

Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.

Prezentam algoritmul corespunzator cazului n=3:

 
 
 
 
 
 
1
 
2
 
3
 
 
1
 
2
 
2
 
2
 
2
1
 
1
 
1
 
1
 
1
 
1



 

 
 
1
 
2
 
3
 
 
 
 
3
 
3
 
3
 
3
 
 
 
1
1
 
1
 
1
 
1
 
2
 
2

 

1
 
2
 
3
 
 
 
 
 
1
1
 
1
 
1
 
2
 
3
 
3
2
 
2
 
2
 
2
 
2
 
2





 

  • se incarca in stiva pe nivelul 1 valoarea 1;

  • incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;

  • incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;

  • valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;

  • valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;

  • valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare; intrucat nivelul 3 este completat corect. Tiparim: 1 2 3

……

Algoritmul continua pana cand stiva devine vida.

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

Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4´4, o solutie ar fi urmatoarea:

 
D
 
 
 
 
 
D
D
 
 
 
 
 
D
 

 

Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1.

D
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

A doua dama nu poate fi asezata decat pe coloana a 3-a.

D
 
 
 
 
 
D
 
 
 
 
 

loading...










Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu














loading...



Scriitori romani