...ste posibila, deoarece aceasta valoare nu mai este intalnitavaloarea 1 din nivelul al 3-lea se regaseste pe nivelul 1valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-leavaloarea 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 nn 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 44, o solutie ar fi urmatoareaDDDDCum procedam Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1.DA doua dama nu poate fi asezata decat pe coloana a 3-a.DDObservam ca a treia dama nu poate fi plasata in linia a 3-a. Incercam atunci plasarea celei de-a doua dame in coloana a 4-a.DDA treia dama nu poate fi plasata decat pe coloana a 2-a.DDDIn aceasta situatie dama a patra nu mai poate fi asezata. Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a treia, nici in coloana a patra, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a doua.DA doua dama nu poate fi asezata decat in coloana a patra.DDDama a treia se aseaza in prima coloana.DDDAcum este posibil sa plasam a patra dama in coloana a treia si astfel am obtinut o solutie a problemei.DDDDAlgoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.Pentru prezentarea unei solutii putem folosi un vector cu n componente avand in vedere ca pe fiecare linie se gaseste o singura dama. Exemplu pentru solutia gasita avem vectorul st ce poate fi asimilat unei stive.Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia. st i st j i-j diferenta, in modul, intre linii si coloane este aceeasi. 3ST 41ST 3In general STi k semnifica faptul ca pe linia i dama ocupa pozitia k.4ST 22ST 1Exemplu In tabla 44 avem situatiaDSt 1 1 i 1St 3 1 j 3 St 1 st 3 1 3 2i j 1 3 2DSau situatiaDSt 1 3 i 1St 3 1 j 3 St i st j 3 1 2i j 3 1 2DIntrucat doua dame nu se pot gasi pe aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema ca doua dame sa nu fie plasate in aceeasi diagonala. A proceda astfel, inseamna sa lucra conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. Fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura valid.Produsul cartezian a n multimi. Se dau multimile de mai jos si se cere produsul cartezian al lor.A1 I1, 2, 3, , k1SA2 I1, 2, 3, , k2SAn I1, 2, 3, , knSExemplu A1 I1, 2SA2 I1, 2, 3SA3 I1, 2, 3SA1 A2 A3 I1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 2, 1, 2, 3, 1, 3, 1, 1, 3, 2, 1, 3, 3, 2, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 3, 1, 2, 3, 2, 2, 3, 3S.Pentru rezolvare, se folosesc stiva ST si un vector A ce retine numerele k1, k2, kn. Utilizam metoda backtracking, usor modificata din urmatoarele motiveOrice element aflat la nivelul k al stivei este valid, motiv pentru care procedura valid nu face altceva decat sa atribuie variabilei ev valoarea TRUE.Limita superioara pe nivelul k al stivei este data de Ak.Modul de conce...
Download