Produs cartezian

Scopul lucrarii. Se urmareste prezentarea modului de reprezentare a multimilor, generarea iterativa a diferitelor tipuri de multimi, algoritmul general de prelucrare a problemelor rezolvate cu ajutorul multimilor si cateva notiuni teoretice si practice legate de modul in care se abordeaza problemele care pot fi solutionate folosind elementele unui produs cartezian.

Notiuni teoretice

2.1. Reprezentarea multimilor

Fiind data o multime oarecare A = cu n elemente, pentru reprezentarea ei se foloseste de obicei un vector cu n componente in care se introduc elementele multimii. O astfel de asociere multime-vector stabileste implicit o ordine a elementelor multimii, corespunzatoare ordinii in care apar elementele in vector.

Daca B este o submultime a lui A, pentru reprezentarea submultimii se pot folosi mai multe modalitati. Cele mai folosite sunt prezentate in continuare.

1) Se foloseste un vector cu n componente, unde elementele submultimii sunt plasate la inceputul vectorului. Sfirsitul multimii se poate localiza astfel:

a) precizind numarul elementelor submultimii intr-o variabila, de exemplu in variabila m;

b) dupa ultimul element reprezentat in vector se pune o valoare predefinita care nu exista in multime. De exemplu 0, daca A = [n] = ;

c) introducind pe restul pozitiilor din vector o valoare care nu apartine multimii A, de exemplu 0.

Daca avem multimea A = [n] = si submultimea B = reprezentarile submultimii B prin metodele enumerate sunt:

2) Se foloseste un vector cu n componente construit analog cu cel din reprezentarea 1) cu mentiunea ca elementele submultimii sunt plasate le sfirsitul vectorului.

Pentru aceeasi multime A si submultimea B avem:

3) Prin intermediul vectorului caracteristic al submultimii, adica acel vector c din ⁿ pentru care elementul c(i) are valoarea 1 daca elementul i apartine multimii sau 0 in caz contrar.

Pentru submultimea B, a multimii A avem reprezentarea:

Deoarece intre multimea A = si multimea numerelor naturale [n] = exista o bijectie, se poate presupune ca multimea A = . Cele mai des folosite metode de reprezentare a submultimilor sunt metodele 1.a si 3.

In mod curent se pune problema de a alege dintr-o multime oarecare de obiecte submultimi de elemente care poseda anumite proprietati. De exemplu, se pune problema aranjarii elementelor une multimi sau ale mai multor multimi intr-o anumita ordine, sau de a determina numarul tuturor submultimilor unei multimi construite dupa anumite reguli etc.

Fiind vorba de anumite combinatii de obiecte, aceste probleme fac parte din combinatorica. Combinatorica poate fi considerata o parte a teoriei multimilor, orice problema de combinatorica putind fi redusa la o problema despre multimi finite si aplicatii ale acestora.

Combinatorica isi gaseste aplicatii in teoria probalitatilor, in cibernetica, in logica matematica, teoria numerelor si in diferite ramuri ale stiintei si tehnici.

2.2. Algoritmul general de obtinerea a tuturor submultimilor in varianta iterativa

Rezolvarea problemelor de combinatorica presupune parcurgerea etapelor de mai jos.

Abstractizarea problemei. Se analizeaza problema eliminindu-se toate aspectele concrete, pastrindu-se doar cele care caracterizeaza problema. Aceasta presupune determinarea modului in care se reprezinta o solutie precum si informatiile auxiliare.

Alegerea algoritmului de generare. Aceasta etapa presupune stabilirea naturii problemei (cu permutari, aranjamente etc). Pentru fiecare astfel de problema exista mai multi algoritmi care genereaza aceste elemente.

Scrierea programului pornindu-se de la algoritmul implementat anterior.

In cele ce urmeaza se considera ca multimea finita se da sub forma a = [n] = , multimile si sunt echivalente, intre ele existind o aplicatie bijectiva, cea data de corespondenta a_i i, pentru i=1, 2, , n.

Generarea elementelor unei multimi poate implica:

a) submultimi la care conteaza ordinea elementelor;

b) submultimi la care nu conteaza ordinea elementelor.

In cazul multimilor la care conteaza ordinea elementelor se foloseste pentru reprezentare metoda 1) sau 2). Pentru submultimilor de al doilea tip, daca se foloseste ca reprezentare metoda 1) sau 2), pentru a se evita generarea repetata a aceleiasi submultimi se impune restrictia ca elementele submultimii sa se genereze in ordine crescatoare.

Toate submultimile la care se fac referiri in continuare se genereaza iterativ, fiecare element obtinindu-se din predecesorul sau. Exista si posibilitatea generarii recursive a elementelor unei multimi, dar nu toate limbajele de programare accepta recursivitatea.

Algoritmul general de obtinerea a tuturor submultimilor in varianta iterativa, in pseudocod este:

executa INIT(V, n, ig)

┌ cat_timp ig¹0 repeta

│ executa PREL(V, n

│ executa GEN(V, n, ig)

unde:- tabloul V, de dimensiune n, contine elementele submultimii;

- n este intreg ce contine numarul de elemente;

- ig este indicator de generare care poate lua valorile:

- 0 cind nu se mai pot genera elemente.

- 1 in caz contrar.

- procedura INIT(v, n, ig), cu parametri formali v, n, ig, are ca scop initializarea elementelor vectorului v si a indicatorului de generare ig la 1;

- procedura GEN(v, n, ig), cu aceeasi parametri, asigura generarea unei noi submultimi in vectorul v si daca este cazul modifica valoarea indicatorului ig;

- procedura PREL(v, n), de parametri v si n (poate avea si alti parametri in functie de problema de rezolvat), realizeaza operatiile corespunzatoare problemei cu elementele submultimii generate continute in vectorul v, fara a modifica elementele tabloului v.

Vectorii V vor fi generati in ordine lexicografica directa. Indicatorul ig este initializat in procedura INIT si actualizat de procedura GEN asigura generarea tuturor submultimilor.

Generarea elementelor unui produs cartezian

Fie A si B doua multimi distincte sau nu. Cu elementele celor doua multimi se pot forma perechi ordonate (x, y), unde primul element x este din A si al doilea element y este din B. Multimea tuturor perechilor (x, y), considerate ca elemente, se numeste produs cartezian a lui A cu B si se noteaza A x B, deci:

A x B = .

Multimile A si B se numesc factorii produsului cartezian A x B, iar x si y se numesc coordonatele sau proiectiile elementului (x, y). Se poate considera si produsul cartezian B x A, ale carui elemente sunt perechile (y, x) cu y din B si x din A, adica:

B x A = .

De exemplu, daca A = si B = , atunci

A x B =

iar

B x A = .

Daca insa A = B, atunci A x B = B x A, caz in care in loc de A x A se scrie A² si

A² = .

De exemplu, daca A = atunci:

A² = .

Doua elemente (x, y) si (x', y') ale produsului cartezian sunt egale daca si numai daca x = x' si y = y'.

Produsul cartezian se poate defini si in cazul a n multimi A₁, A₂, , A_n, ca fiind multimea tuturor grupelor (x₁, x₂, , x_n), unde x₁ I A₁, x₂ I A₂, , x_n I A_n.

Deci se poate scrie:

A₁ x A₂ x x A_n =

unde A₁, A₂, , A_n se numesc factorii produsului cartezian, iar x₁, x₂, , x_n se numesc coordonatele sau pozitiile elementului (x₁, x₂, , x_n).

Daca A₁ = A₂ = = A_n atunci A x A x x A se scrie Aⁿ.

2.3.a. Algoritmul de generare iterativa a elementelor produsului cartezian

Fie n multimi A₁, A₂, , A_n, unde pentru fiecare i apartinind multimii , avem A_i = [n_i] = , unde n_i este cardinalul multimi A_i. Se pune problema sa se genereze multimea produsului cartezian A₁ x A₂ x xA_n, multime care contine elemente de forma (x₁, x₂, , x_n) unde x_j apartine lui A_j, 1 £ j £ n. Cardinalul produsului cartezian A₁ x A₂ x x A_n este n₁ n₂ n_n

Elementele produsului cartezian vor fi generate succesiv intr-un vector v cu n conponente, v = (v₁, v₂, , v_n). Vectorii vor fi generati conform ordinii direct lexicografice. Se pleaca de la vectorul v = (1, 1, , 1), cu 1 pe toate pozitiile.

Pentru a construi succesorul unui vector v₁, v₂, , v_n care este un element al acestui produs cartezian se procedeaza astfel: se determina cel mai mare indice i pentru care avem v_i<n_i si se alege drept succesor al elementului (v₁, v₂, , v_n) vectorul (v₁, v₂, , v_i-1, v_i+1, 1, 1, , 1). Daca un astfel de indice nu exista inseamna ca este vorba de un vector de forma (n₁, n₂, , n_n), care este cel mai mare vector in ordine lexicografica, deci procesul de generare s-a incheiat. Pentru a se determina indicele i cautarea incepe de la sfirsitul vecto­rului.

De exemplu, daca avem multimile A₁ = [3] = , A₂ = [4] = , A₃ = [2] = , cu card(A₁)=3, card(A₂)=4, card(A₃)=2, elementele produsului cartezian A₁ x A₂ x A₃ = .

Conform algoritmului propus se pleaca de la vectorul v=(1, 1, 1), urmatorul element construit va fi v=(1, 1, 2), apoi v=(1, 2, 1), s.a.m.d. In final, ultimul element generat va fi v=(3, 4, 2), dupa care procesul de generare se incheie.

Procedurile INIT si GEN pentru generarea tuturor elementelor produsului cartezian sunt:

procedura INIT(v, n, ig) este

┌ pentru i=1, n, 1 repeta

│ v(i) <- 1

└

ig <- 1

sfarsit

procedura GEN(v, n, ig) este

i <- n

gasit <- 0

┌ cat_timp (i>0) si (gasit=0) repeta

│ ┌ daca v_i < n_i atunci

│ │ v_i <- v_i+1

│ │ gasit <- 1

│ │ altfel

│ │ v_i <- 1

│ │ i <- i-1

│ └

└

┌ daca i=0 atunci

│ ig <- 0

└

sfarsit

Determinarea celui mai mare indice pentru care v_i < n_i se realizeaza printr-o cautare secventiala care presupune existenta a doua conditii de oprire ((i>0) si (gasit=0)). Acest lucru presupune evaluarea conditiilor de fiecare data cind se face deplasarea spre stinga. Pentru a face cautarea mai rapida se poate implementa o cautare secventiala cu santinela. Aceasta presupune introducerea unei noi pozitii in vectorul v, pozitia v₀ care este initializata cu o valoare mai mica decit nr₀. In acest caz procedurile INIT si GEN arata astfel:

procedura INIT (n, v, ig, nr) este

┌ pentru i=1, n, 1 repeta

│ v_i <- 1

└

v₀ <- nr₀-1

ig <- 1

sfarsit

procedura GEN (n, v, ig, nr) este

i <- n

┌ cat_timp v_i = nr_i repeta

│ v_i <- 1

│ i <- i-1

└

┌ daca i = 0 atunci

│ ig <- 0

│ altfel

│ v_i <- v_i+1

└

sfarsit

Un caz particular al problemei este cel in care n₁ = n₂ = n₃ = = n_m = n, cind se genereaza elementele multimii [n]^m.

Exemplu rezolvat

Se cere generarea tuturor posibilitatilor de asezare a n cai pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur cal si caii sa nu se poata lua intre ei.

Solutia problemei se poate reprezentata sub forma unui vector l = (l₁, l₂, , l_n), unde n este numarul de cai de pe tabla de sah, cu semnificatia: calul de pe coloana i se afla pe linia l_i.

Rezolvarea problemei se reduce la generarea tuturor elementelor produsului cartezian A₁ x A₂ x x A_n, cu A_i=[n_i]=m, pentru 1£i£m.

Presupunind ca pozitia unui cal este determinata de coloana i si linia l_i, un cal aflat in aceasta pozitie poate sa 'ia' caii aflati pe pozitiile:

a) (i+1, l_i+2) pentru i<n si l_i<n-1

b) (i+1, l_i-2) pentru i<n si l_i>2

c) (i-1, l_i-2) pentru i>1 si l_i<n-1

d) (i-1, l_i+2) pentru i>1 si l_i>2

e) (i+2, l_i+1) pentru i<n-1 si l_ii<n

f) (i+2, l_i+2) pentru i<n-1 si l_ii>1

g) (i-2, l_i+2) pentru i>2 si l_i<n

h) (i-2, l_i-1) pentru i>2 si l_i>1

In aceste conditii procedura de prelucrare a elementelor produsului cartezian arata astfel:

procedura PREL(v, n) este

┌ pentru i=1, n, 1 repeta

│ scrie v_i

└

gasit <- 0

i <- 1

┌ cat_timp (i<n) si (gasit=0) repeta

│ ┌ daca i+1£n atunci

│ │ ┌ daca (v_i+1=v_i+2 sau (v_i+1=v_i-2) atunci

│ │ │ gasit <- 1

│ │ └

│ └

│ ┌ daca i+2£n atunci

│ │ ┌ daca (v_i+2=v_i+1) sau (v_i+2=v_i-1) atunci

│ │ │ gasit <- 1

│ │ └

│ └

│ i <- i+1

└

┌ daca gasit=1 atunci

│ scrie 'Nu este solutie'

│ altfel

│ scrie 'Este solutie'

└

sfarsit

Deoarece in acest caz n_i = n, pentru i = 1, 2, , n se poate considera nr₀=n, deci in procedurile INIT si GEN, pentru varianta 2, avem v₀=n-1.

Programului principal cara apeleaza cele trei proceduri va arata astfel:

scrie 'Introduceti numarul de cai'

citeste n

executa INIT(n, v, ig)

┌ cat_timp ig¹0 repeta

│ executa PREL(v, n)

│ executa GEN(n, v, ig)

sfarsit

In cazul in care n=4, rezultatele vor fi afisate astfel:

Introduceti numarul de cai: 4

Este solutie

Nu este solutie

Nu este solutie

Este solutie

Nu este solutie

Este solutie.

Rezolvarea problemei in Pascal se afla in Anexa A.L10.1 iar in C in Anexa B.L10.1

2.3.b. Algoritmul de generare recursiva a elementelor produsului cartezian

Generarea recursiva a elementelior produsului cartezian are la baza metoda generala de programare backtracking.

Vom folosi acelasi vector v care contine cate un element al produsului cartezian. Procedura PREL(v,n ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura GEN_PROD_CART_REC (i) este

┌ pentru j=1,n,1 repeta

│ v_i <- j

│ daca i< m atunci

│ executa GEN_PROD_CART_REC (i+1)

│ else

│ executa PREL(v,n)

└

sfarsit

unde : v este un vector de n componente iar m este cardinalitatea celor n multimi. Vectorul v se considera global pentru a nu incarca stiva la apelurile recursive.

Programului principal pentru rezolvarea problemei a aceleasi cara apeleaza procedura GEN_PROD_CART_REC() va arata astfel:

scrie 'Introduceti numarul de cai'

citeste n

m=n

executa GEN_PROD_CART_REC(1)

stop

Rezolvarea problemei in Pascal se afla in Anexa A.l0.2 iar in C in Anexa B.l0.2.

Probleme propuse

1. Se considera un grup de specialisti in automobile, din care n1 sunt specialisti in motoare, n2 in transmisii, n3 in pneuri, n4 in echipamente de bord. Pentru fiecare specealist se cunoaste calificarea (inginer, subinginer, tehnician, muncitor) si un cod de identifi­care. Se se listeze toate posibilitatile de formare a unor echipe de asistenta tehnica, astfel incit fiecare echipa sa cuprinda exact cite un specialist din fiecare domeniu, cel putin unul fiind inginer (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

2. Fie G un grup de teroristi, din care n1 sunt specia­listi in explozive, n2 in trageri de noapte, n3 in lupte corp la corp, n4 in transmisiuni. Pentru fiecare se cunoaste gradul(1, 2, 3 sau 4) si un cod de identificare. Sa se listeze toate posibili­tatile de formare a unor echipe de terorism, astfel incit fiecare echipa sa cuprinda exact cite un specialist din fiecare domeniu, cel putin unul avind gradul 4 (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

3. Se considera un grup de exploratori, din care n1 sunt biologi, n2 etnologi, n3 fotografi si n4 soferi. Pentru fiecare specialist se cunoaste virsta si un cod de identificare. Sa se listeze toate posibilitatile de formare a unor echipe de explorare, astfel incit fiecare echipa sa cuprinda exact cite un specialist din fiecare domeniu, cel putin unul avind peste 40 de ani (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

4. Fie G un grup de electronisti, din care n1 sunt spe­cialisti in video, n2 in audio, n3 in relee radio, n4 in telefo­nie. Pentru fiecare specialist se cunoaste calificarea (inginer, subinginer, tehnician, muncitor) si un cod de identificare. Sa se listeze toate posibilitatile de formare a unor echipe de asistenta tehni­ca, astfel incit fiecare echipa sa cuprinda exact cite un spe­cialist din fiecare domeniu, cel putin unul fiind inginer (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

5. Se considera un grup de examinatori, din care n1 sunt specia­listi in programare, n2 in circuite electronice, n3 in micro­procesoare, n4 in grafica pe calculator. Pentru fiecare se cu­noaste gradul didactic (profesor, conferentiar, lector, asistent) si un cod de identificare. Se se listeze toate posibilitatile de formare a unor comisii de examinare, astfel incit fiecare echipa sa cuprinda exact cite un specialist din fiecare domeniu, cel putin unul fiind profesor (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

6. Se considera un grup de specialisti in energetica, din care n1 sunt specialisti in transformatoare, n2 in intreruptoare, n3 in contactoare, n4 in aparate de masura. Pentru fiecare se cu­noaste calificarea (inginer, subinginer, tehnician, muncitor) si un cod de identificare. Sa se listeze toate posibilitatile de formare a unor echipe de asistenta tehnica, astfel incit fiecare echipa sa cuprinda exact cite un specialist din fiecare domeniu, cel putin unul fiind inginer (n1, n2, n3, n4, precum si codul si calificarea fiecarei persoane se introduc de utilizator).

7. Fie G un grup de n ziaristi, din care n1 sunt specia­listi in editoriale, n2 in interviuri, n3 in fotoreportaj, n4 in anchete. Pentru fiecare se cunoaste calificarea (studii superi­oare de specialitate, studii superioare nespecifice, studii medii, studii elementare) si un cod de identificare. Se se lis­teze toate posibilitatile de formare a unor echipe de reportaj, astfel incit fiecare echipa sa cuprinda exact cite un ziarist din fiecare domeniu, cel putin unul din echipa avind studii superi­oare de specialitate (n1, n2, n3, n4, precum si codul si califi­carea fiecarei persoane se introduc de utilizator).

8. Se cere generarea tuturor posibilitatilor de asezare a n regine pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle o singura regina si acestea sa nu se atace.

9. Se cere generarea tuturor posibilitatilor de asezare a n turnuri pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur turn si turnurile sa nu se poata lua intre ele.

Pentru elaborarea unui test de aptitudini se dispune de un set de n intrebari, fiecare intrebare fiind cotata cu un anumit numar de puncte. Se cere sa se elaboreze toate chestionarele avind intre a si b intrebari distincte, si totalizind fiecare intre p si q puncte. Intrebarile sint date prin numar si punctaj.

11. Se da lista de produse care se pot consuma intr‑un restaurant, continind preparate culinare grupate pe trei feluri (aperitiv, mincare propriuzisa, desert) si bauturi nealcoolice asortate cu unul din cele trei feluri de mincare. Pentru fiecare portie de mincare si pentru fiecare pahar de bautura se indica pretul si cantitatea de calorii incorporata. Un consumator condus dupa principiile alimentatiei rationale, doreste sa i se serveasca un meniu care sa nu depaseasca suma S lei si cantitatea considerata optima de OPTCAL calorii. In limita sumei ramase se va servi, daca este posibil, si bautura, cel mult un sortiment de bautura la fiecare fel de mincare si, din fiecare sortiment, cel putin un pahar, astfel incit diferenta dintre caloriile acumulate (mincare+bautura) si OPTCAL sa fie minima. Se cere sa se realizeze programul care, pe baza datelor problemei furnizate in fisierul de intrare sa gaseasca, daca exista, meniul solicitat.

12. Se considera un set de n obiecte x1, x2, , xn. Fiecare obiect xi se caracterizeaza prin masa gi si valoarea vi. Sa se realizeze un program care stabileste multimea de obiecte cu valoarea totala maxima, astfel incit masa totala a obiectelor sa nu depaseasca valoarea g_max. Se considera ca nu orice doua obiecte pot fi selectate impreuna (adica sint incompatibile). Ca date de intrare se furnizeaza numarul n al obiectelor din setul initial, masa maxima acceptata, apoi, pe rind, pentru fiecare obiect, cite doua valori reale reprzentind masa si valoarea acestuia si o lista de perechi de obiecte incompatibile. Se vor tipari indicii corespunzatori obiectelor ce au fost selectate in multimea optima, precum si masa si valoarea totala a obiectelor din multime.

13. O delegatie din partea a 6 regimente,cuprinzind cite 6 ofiteri de grade diferite (colonel, lt.colonel, maior, capitan, locotenent, sublocotenent) pentru fiecare regiment, trebuie asezata in careu. Sa se evidentieze posibilitatile de asezare, astfel incit vecinii (pe linie sau coloana) sa nu aiba acelasi grad si sa nu apartina aceluiasi regiment.

14. Un dresor trebuie sa scoata m lei si n tigri din arena, astfel incit sa nu scoata doi tigri unul dupa altul. Care sint posibilitatile sale de a realiza acest lucru?

15. Care sint posibilitatile de formare a unor coliere distincte, din n margele de greutati distincte, astfel incit fiecare colier sa contina toate cele n margele, iar margelele aflate respectiv in pozitiile k si n‑k sa aiba greutatile maxime?

16. Sa se determine toate modurile in care se pot aseza pe tabla de sah 7 nebuni de aceeasi culoare, astfel incit sa nu intre unul in raza de actiune a celorlalti.

17. Un numar de n apartamente trebuie repartizate la n persoane, corespondenta intre persoane si apartamente fiind biunivoca. Fiecare persoana prezinta o lista de preferinte pentru anumite apartamente. Sa se repartizeze apartamentele astfel incit satisfacerea preferintelor sa fie maxima.

Fiind data o baza de numeratie b (ce poate fi 2, 3, , 8), sa se genereze toate numerele naturale diferite ce se pot exprima in aceasta baza, folosind cifrele bazei cel mult o data in scrierea unui numar .

Fie m multimi A₁, A₂, , A_m formate din cite n_i, i=1, 2, , m numere distincte. Sa se genereze toate elementele produsului cartezian A₁xA₂xxA_m.

ANEXA A

A.L9.1

A.L9.1. Se cere generarea tuturor posibilitatilor de asezare a n cai pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur cal si caii sa nu se poata lua intre ei.

program cai;

uses crt;

const NMAX= 25;

var n:integer;

ig:boolean;

v:array[0..NMAX] of integer;

procedure INIT;

var i:integer;

begin

for i:=1 to n do v[i]:=1;

v[0]:=0;

ig:=true;

end;

procedure GEN;

var i:integer;

begin

i:=n;

while v[i]=n do

begin

v[i]:=1;

i:=i-1;

end;

if i=0 then ig:=false

else v[i]:=v[i]+1;

end;

procedure PREL;

var i:integer;

gasit:boolean;

begin

for i:=1 to n do write(v[i]);

i:=1;

gasit:=false;

while (i<n) and (not gasit) do

begin

if (i+1<=n) and ((v[i+1]=v[i]+2) or (v[i+1]=v[i]-2)) then gasit:=true;

if (i+2<=n) and ((v[i+2]=v[i]+1) or (v[i+2]=v[i]-1)) then gasit:=true;

i:=i+1;

end;

if gasit then writeln('Nu este solutie')

else writeln('Este solutie');

readkey;

end;

begin

clrscr;

write('Introduceti numarul de cai:'); readln(n);

INIT;

while ig do

begin

PREL;

GEN;

end;

end.

A.L9.2

A.L9.2. Se cere generarea tuturor posibilitatilor de asezare a n cai pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur cal si caii sa nu se poata lua intre ei.

program cai_recursiv;

uses crt;

const NMAX=25;

var ig:boolean;

v:array [1..NMAX] of integer;

n,m:integer;

procedure PREL;

var i:integer;

gasit:boolean;

begin

for i:=1 to n do write(v[i]);

i:=1;

gasit:=false;

while (i<n) and (not gasit) do

begin

if (i+1<=n) and ((v[i+1]=v[i]+2) or (v[i+1]=v[i]-2)) then gasit:=true;

if (i+2<=n) and ((v[i+2]=v[i]+1) or (v[i+2]=v[i]-1)) then gasit:=true;

i:=i+1;

end;

if gasit then writeln('Nu este solutie')

else writeln('Este solutie');

readkey;

end;

procedure GEN_PROD_CART_REC (i:integer);

var j,k:integer;

begin

for j:=1 to m do

begin

v[i]:=j;

if i<n then GEN_PROD_CART_REC(i+1)

else PREL;

end;

end;

begin

clrscr;

write('Introduceti numarul de cai:'); readln(n);

m:=n;

GEN_PROD_CART_REC(1)

end.

B.L9.1

B.L9.1. Se cere generarea tuturor posibilitatilor de asezare a n cai pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur cal si caii sa nu se poata lua intre ei. (varianta iterativa)

#include <stdio.h>

# include <conio.h>

#define NMAX 25

int ig,v[NMAX],n;

void INIT()

void GEN()

void PREL()

if(gasit) printf('Nu este solutien');

else printf('Este solutien');

getch();

void main()

B.L9.2

B.L9.1. Se cere generarea tuturor posibilitatilor de asezare a n cai pe o tabla de sah de n x n astfel incit pe o coloana a tablei sa se afle un singur cal si caii sa nu se poata lua intre ei. (varianta recursiva)

#include <stdio.h>

# include <conio.h>

#define NMAX 25

int ig,v[NMAX],n,m;

void PREL()

if(gasit) printf('Nu este solutien');

else printf('Este solutien');

getch();

void GEN_PROD_CART_REC (int i)

void main()