CombinatoricaScopul. 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. Reprezentarea multimilorFiind data o multime oarecare A = {a1, a2, a3, ..., an} 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 modalitati sunt:1) Se foloseste un vector cu n componente, unde elementele submultimii sunt plasate la inceputul vectorului. Sfarsitul 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] = { 1, 2, 3, ..., n};c) introducind pe restul pozitiilor din vector o valoare care nu apartine multimii A, de exemplu 0.Daca avem multimea A = [n] = { 1, 2, 3, ..., n } si submultimea B = { 5, 2, 3, 7 } reprezentarile submultimii B prin metodele enumerate sunt:a) 5 2 3 7 …

b) 5 2 3 7 0 …c) 5 2 3 7 0 … 0

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:

b) … 0 5 2 3 7a) … 5 2 3 7

c) 0 … 0 5 2 3 7

3) Prin intermediul vectorului caracteristic al submultimii, adica acel vector c din {0, 1}n 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:

0 1 1 0 1 0 1 … 0

1 2 3 4 5 6 7 n

Deoarece intre multimea A = {a1, a2, ..., an} si multimea numerelor naturale [n] = {1, 2, 3, ..., n } exista o bijectie, se poate presupune ca multimea A = { 1, 2, ..., n }. 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 unei 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.

Algoritmul general de obtinere a tuturor submultimilor in varianta iterativaRezolvarea problemelor de combinatorica presupune parcurgerea urmatoarelor etape:1. 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.2. Alegerea algoritmului de generare. Aceasta etapa presupune stabilirea naturii problemei (cu permutari, produs cartezian, aranjamente etc). Pentru fiecare astfel de problema exista mai multi algoritmi care genereaza aceste elemente.3. Scrierea programului pornindu-se de la algoritmul implementat anterior.In cele ce urmeaza se considera ca multimea finita {a1, a2, ..., an} se da sub forma a = [n] = {1, 2, ..., n}, multimile {a1, a2, ..., an} si {1, 2, ..., n} sunt echivalente, intre ele existind o aplicatie bijectiva, cea data de corespondenta ai 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 ig0 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 care asigura generarea tuturor submultimilor.Generarea elementelor unui produs cartezianFie 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 = { (x, y) | x A si y 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 = { (y, x) | y B si x A }. De exemplu, daca A = { a1, a2, a3 } si B = {b1, b2}, atunci A x B = {(a1, b1), (a1, b2), (a2, b1), (a2, b2), (a3, b1), (a3, b2)} Iar B x A = {(b1, a1),( b1, a2),(b1, a3),(b2, a1),(b2, a2),(b2, a3)}. Daca insa A = B, atunci A x B = B x A, caz in care in loc de A x A se scrie A2 si A2 = { (x, y) | x A si y A}. De exemplu, daca A = {a1, a2} atunci: A2 = {(a1, a1), (a1, a2), (a2, a1), (a2, a2)}.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 A1, A2, ..., An, ca fiind multimea tuturor grupelor (x1, x2, ..., xn), unde x1 A1, x2 A2, ..., xn An.

Deci se poate scrie: A1 x A2 x ... x An = { (x1, x2, ..., xn) | xi Ai cu 1 i n}

unde A1, A2, ..., An se numesc factorii produsului cartezian, iar x1, x2, ..., xn se numesc coordonatele sau pozitiile elementului (x1, x2, ..., xn).  Daca A1 = A2 = ... = An atunci A x A x ... x A se scrie An.

a. Algoritmul de generare iterativa a elementelor produsului cartezianFie n multimi A1, A2, ..., An, unde pentru fiecare i apartinind multimii {1, 2, ..., n}, avem Ai = [ni] = {1, 2, ..., ni}, unde ni este cardinalul multimi Ai. Se pune problema sa se genereze multimea produsului cartezian A1 x A2 x ... xAn, multime care contine elemente de forma (x1, x2, ..., xn) unde xj apartine lui Aj, 1 j n. Cardinalul produsului cartezian A1 x A2 x ... x An este n1 n2 ... nnElementele produsului cartezian vor fi generate succesiv intr-un vector v cu n componente, v = (v1, v2, ..., vn). 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 v1, v2, ..., vn care este un element al acestui produs cartezian se procedeaza astfel: -se determina cel mai mare indice i pentru care avem vi<ni si se alege drept succesor al elementului (v1, v2, ..., vn) vectorul (v1, v2, ..., vi-1, vi+1, 1, 1, ..., 1). -Daca un astfel de indice nu exista inseamna ca este vorba de un vector de forma (n1, n2, ..., nn), 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 vectorului.De exemplu, daca avem multimile A1 = [3] = {1, 2, 3}, A2 = [4] = {1, 2, 3, 4}, A3 = [2] = {1, 2},

cu card(A1)=3, card(A2)=4, card(A3)=2,

elementele produsului cartezian A1 x A2 x A3 = {(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (1, 3, 1), ..., (3, 3, 2), (3, 4, 1), (3, 4, 2)}.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:

De exemplu, daca avem multimile A1 = [3] = {1, 2, 3}, A2 = [4] = {1, 2, 3, 4}, A3 = [2] = {1, 2}, cu card(A1)=3, card(A2)=4, card(A3)=2,

1, 1, 1 2, 2, 21, 1, 2 2, 3, 11, 2, 1 2, 3, 21, 2, 2 . . . 1, 3, 1 3, 1, 11, 3, 22, 1, 1 . . . 2, 1, 2 3, 4, 22, 2, 1

procedura INIT(v, n, ig) este┌ pentru i=1, n, 1 repeta│ v(i) <- 1└ ig <- 1sfarsitprocedura GEN(v, n, ig) estei <- ngasit <- 0┌ cat_timp (i>0) si (gasit=0) repeta│ ┌ daca vi < ni atunci│ │ vi <- vi+1│ │ gasit <- 1│ │ altfel│ │ vi <- 1│ │ i <- i-1│ └ └ ┌ daca i=0 atunci│ ig <- 0└ sfarsit.

Determinarea celui mai mare indice pentru care vi < ni 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 cand se face deplasarea spre stanga. Pentru a face cautarea mai rapida se poate implementa o cautare secventiala cu santinela. Aceasta presupune introducerea unei noi pozitii in vectorul v, pozitia v0 care este initializata cu o valoare mai mica decit nr0. In acest caz procedurile INIT si GEN arata astfel:procedura INIT (n, v, ig, nr) este┌ pentru i=1, n, 1 repeta│ vi <- 1└ v0 <- nr0-1ig <- 1sfarsit

procedura GEN (n, v, ig, nr) estei <- n┌ cat_timp vi = nri repeta│ vi <- 1│ i <- i-1└ ┌ daca i = 0 atunci│ ig <- 0│ altfel│ vi <- vi+1└ sfarsitUn caz particular al problemei este cel in care n1 = n2 = n3 = ... = nm = n, cand se genereaza elementele multimii [n]m.

.b. Algoritmul de generare recursiva a elementelor produsului cartezianGenerarea 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│ vi <- j│ daca i< m atunci│ executa GEN_PROD_CART_REC (i+1) │ else│ executa PREL(v,n) └ sfarsitunde : 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.

Proplema rezolvataSe cere implementarea programului iterativ care genereaza toate posibilitatile 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. Se va folosi algoritmul de generare iterativa a elementelor produsului cartezian.Solutia problemei se poate reprezentata sub forma unui vector l = (l1, l2, ..., ln), unde n este numarul de cai de pe tabla de sah, cu semnificatia: calul de pe coloana i se afla pe linia li.

Rezolvarea problemei se reduce la generarea tuturor elementelor produsului cartezian A1 x A2 x ... x An, cu Ai=[ni]=m, pentru 1 i m.Presupunind ca pozitia unui cal este determinata de coloana i si linia li, un cal aflat in aceasta pozitie poate sa "ia" caii aflati pe pozitiile:a) (i+1, li+2) pentru i<n si li<n-1b) (i+1, li-2) pentru i<n si li>2c) (i-1, li-2) pentru i>1 si li<n-1d) (i-1, li+2) pentru i>1 si li>2e) (i+2, li+1) pentru i<n-1 si lii<nf) (i+2, li-1) pentru i<n-1 si lii>1g) (i-2, li+1) pentru i>2 si li<nh) (i-2, li-1) pentru i>2 si li>1

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

yc ya

yg ye

x

yh yf

yd yb

procedura PREL(v, n) este┌ pentru i=1, n, 1 repeta│ scrie vi└ gasit <- 0i <- 1┌ cat_timp (i<n) si (gasit=0) repeta│ ┌ daca i+1n atunci│ │ ┌ daca (vi+1=vi+2 sau (vi+1=vi-2) atunci│ │ │ gasit <- 1│ │ └ │ └ │ ┌ daca i+2n atunci│ │ ┌ daca (vi+2=vi+1) sau (vi+2=vi-1) atunci│ │ │ gasit <- 1│ │ └ │ └ │ i <- i+1└ ┌ daca gasit=1 atunci│ scrie 'Nu este solutie'│ altfel│ scrie 'Este solutie'└ sfarsit

Deoarece in acest caz ni = n, pentru i = 1, 2, ..., n se poate considera nr0=n, deci in procedurile INIT si GEN, pentru varianta 2, avem v0=n-1.Programului principal cara apeleaza cele trei proceduri va arata astfel:scrie 'Introduceti numarul de cai'citeste nexecuta INIT(n, v, ig)┌ cat_timp ig0 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: 41 1 1 1 Este solutie1 1 1 2 Nu este solutie1 1 1 3 Nu este solutie1 1 1 4 Este solutie. . . . . . . . . . . . . .. . . . . . . . . . . . . . 4 4 4 3 Nu este solutie4 4 4 4 Este solutie.Se cere implementarea programului iterativ care genereaza toate posibilitatile 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.

#include <stdio.h># include <conio.h>#define NMAX 25int ig,v[NMAX],n;void INIT(){int i;for(i=1;i<= n;i++)v[i]=1;v[0]=0;ig=1;}void GEN() {int i;i=n;while (v[i]==n)v[i--]=1;if (i==0)ig=0;elsev[i]+=1;}

void PREL(){

int i,gasit;for(i=1;i<=n;i++)printf("%3d",v[i]);i=1;gasit=0;while(i<n && !gasit){if ((i+1<=n) && (v[i+1]==v[i]+2 || v[i+1]==v[i]-2))gasit=1;if ((i+2<=n) && (v[i+2]==v[i]+1 || v[i+2]==v[i]-1))gasit=1;i++;}if(gasit) printf("Nu este solutie\n");else printf("Este solutie\n");getch();}void main(){printf("Introduceti numarul de cai:"); scanf("%d",&n);INIT();while(ig){PREL();GEN();}}

Exemplul 2. Se cere implementarea programului recursiv care genereaza toate posibilitatile 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. Se va folosi algoritmul de generare recursiva a elementelor produsului cartezian.Programul principal pentru rezolvarea problemei apeleaza procedura GEN_PROD_CART_REC() si va arata astfel:scrie 'Introduceti numarul de cai'citeste nm=nexecuta GEN_PROD_CART_REC(1)stop#include <stdio.h># include <conio.h>#define NMAX 25int ig,v[NMAX],n,m;

void PREL(){int i,gasit;for(i=1;i<=n;i++)printf("%3d",v[i]);i=1;gasit=0;while(i<n && !gasit){if ((i+1<=n) && (v[i+1]==v[i]+2 || v[i+1]==v[i]-2))gasit=1;if ((i+2<=n) && (v[i+2]==v[i]+1 || v[i+2]==v[i]-1))gasit=1;i++;}if(gasit) printf("Nu este solutie\n");else printf("Este solutie\n");getch();}

void GEN_PROD_CART_REC (int i){int j,k;for(j=1;j<+m;j++){v[i]=j;if(i<n)GEN_PROD_CART_REC(i+1);elsePREL();}}void main(){printf("Introduceti numarul de cai:"); scanf("%d",&n);m=n;GEN_PROD_CART_REC(1)}

Submultimi si partitiiNotiuni teoreticeSubmultimile unei multimiFie multimea A cu n elemente. O submultime B a lui A este orice multime ale carei elemente apartin toate lui A. Submultimile B ale lui A care sunt distincte de A se numesc submultimi proprii ale lui A. Multimea vida, , este multimea care nu contine nici un element. Printre submultimile lui A este si multimea vida.Numarul de submultimi ale unei multimi este 2n. De exemplu, daca avem multimea A = {0, 1}, submultimile lui A sunt : , { 0 }, { 1 }, { 0, 1 }.Submultimile multimii A pot fi considerate ca elementele unei noi multimi numita multimea partilor lui A, notata cu P(A). Printre elementele multimii P(A) se afla submultimile A, , {a} daca a A. Pentru multimea A = {0, 1}, P(A) = { , A, {0}, {1}}.

a. Algoritmul de generare iterativa a elementelor unei submultimiFiind data o multime A cu n elemente se pune problema determinarii celor 2n submultimi ale multimi A. Pentru reprezentarea unei submultimi se va folosi vectorul caracteristic. Deci trebuie sa se genereze toate combinatiile de succesiuni de 0 si 1 ce se pot forma pe n pozitii, unde n reprezinta cardinalul multimii date.Pentru a obtine toate aceste conbinatii se genereaza de fapt toate componentele produsului cartezian A x A x A x ... x A, unde A={0, 1}. Se va folosi un vector v=(v1, v2, ..., vn), cu vi=0 sau 1, pentru 1 i n. Initial toate componentele vectorului v sunt initializate la 0, adica v=(0, 0, ..., 0). Urmatorul vector generat va fi v=(0, 0, ..., 0, 1), apoi v=(0, 0, ..., 0, 1, 0), s.a.m.d. Ultimul element generat va fi v=(1, 1, ..., 1, 1, 1), dupa care procesul de generare se incheie [8], [11].Procedurile de initializare si generare sunt prezentate in continuare:procedura INIT(v, n, ig) este┌ pentru i=1, n, 1 repeta│ vi <- 0└ ig <- 1sfarsit

procedura GEN(v, n, ig) estegasit <- 0i <- n┌ cat_timp (i>0) si (gasit=o) repeta│ ┌ daca vi=0 atunci│ │ vi <- 1│ │ gasit <-- 1│ │altfel │ │ vi <- 0│ │ i <- i-1│ └ └ ┌ daca gasit=0 atunci│ ig <- 0└ sfarsit. Descriere prezentata mai sus genereaza toate submultimile dorite in ordine lexicografica (relatia de ordine se refera la reprezentarea lor prin vectorul caracteristic). Echivalentul binar al reprezentarii unei submultimi pe parcursul generarii variaza in intervalul 0, ..., 2n-1.

Pentru a evita cele doua conditi (i>0) si (gasit=0) in procedura GEN pentru aflarea urmatoarei combinatii, se poate folosi o cautare secventiala cu santinela. Santinela este asezata pe pozitia de indice 0 a vectorului v si are valoarea 0. In acest caz procedurile de initializare si generare au forma:procedura INIT (n, v, ig) este┌ pentru i=0, n, 1 repeta│ vi <- 0└ ig <- 1sfarsitprocedura GEN (n, v, ig) estei <- n┌ cat_timp vi = 1 repeta│ vi <- 0│ i <- i-1└ ┌ daca i = 0 atunci│ ig <- 0│ altfel│ vi <- 1└ sfarsit

Exemplu rezolvat. Intr-o grupa se afla n studenti dintre care nb baieti si restul fete. Sa se determine toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor[8].Reprezentarea unui grup se face prin intermediul vectorului caracteristic, iar selectia elementului dintr-un grup se face dupa urmatoarea conventie: baietii se identifica prin numere intre 1 si nb, iar fetele prin numere intre nb+1 si n. La baza algoritmului sta urmatoarea idee: se vor genera toate submultimile si se vor selecta acele grupuri care indeplinesc conditia impusa. In acest scop se vor cumula numarul de baieti, respectiv de fete din grup.Procedurile de initializare si generare au fost prezentate anterior urmand sa se detalieze doar procedura de prelucrare.procedura PREL(v, n, nb, dif) esten1 <- 0n2 <- 0┌ pentru i=1, nb, 1 repeta│ ┌ daca vi=1 atunci│ │ n1 <- n1+1│ └ └

┌ pentru i=nb+1, n, 1 repeta│ ┌ daca vi=1 atunci│ │ n2 <- n2+1│ └ └ ┌ pentru i=1, n, 1 repeta│ ┌ daca vi=1 atunci│ │ scrie i│ └ └ ┌ daca (n1-n2>=0) si (n1>=n2+dif) atunci│ scrie 'Este solutie'│ altfel│ scrie 'Nu este solutie'└ sfarsit

Programul principal in pseudocod va arata astfel:scrie 'Introduceti numarul de copii'citeste nscrie 'Introduceti numarul de baieti'citeste nbscrie 'Introduceti diferenta'citeste difexecuta INIT(n, v, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n, nb, dif)│ executa GEN(n, v, ig)└ sfarsitIn programele ce urmeaza s-a implementat varianta cu santinela.Pentru cazul particular, cind grupul are 4 copii, dintre care 2 baieti iar diferenta baieti-fete este 1, rezultatele vor apare astfel:Introduceti numarul de copii: 4Introduceti numarul de baieti: 2Introduceti diferenta: 1

4 Nu este solutie3 Nu este solutie3 4 Nu este solutie2 Este solutie2 4 Nu este solutie2 3 Nu este solutie2 3 4 Nu este solutie 1 Este solutie1 4 Nu este solutie1 3 Nu este solutie. . . . . . . . . . . . .. . . . . . . . . . . . . 1 2 3 4 Nu este solutieIntr-o grupa se afla n de studenti dintre care nb baieti si restul fete. Sa se implementeze programul in varianta iterativa care determina toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor.

#include <stdio.h># include <conio.h>#define NMAX 25int ig,v[NMAX],n;void INIT(){int i;for(i=0;i<=n;i++)v[i]=0;ig=1;}void GEN_SUBM(){int i;i=n;while(v[i])v[i--]=0;if(!i)ig=0;else v[i]=1;}

void PREL(int nb,int dif){int i,n1,n2;n1=n2=0;for(i=1;i<=nb;i++) if(v[i]) n1++;for(i=nb+1;i<=n;i++) if(v[i]) n2++;for(i=1;i<=n;i++) if(v[i]) printf("%d ",i);if (n1>n2 && n1-n2<=dif) printf("Este solutie\n");else printf("NU este solutie\n");getch();}void main(){int nb,dif;printf("Introduceti numarul de copii:"); scanf("%d",&n);printf("Introduceti numarul de baieti:"); scanf("%d",&nb);printf("Introduceti diferenta:"); scanf("%d",&dif);INIT();while(ig){PREL(nb,dif);GEN_SUBM();}}

b. Algoritmul de generare recursiva a elementelor unei submultimiGenerarea 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_SUBM_REC (i) este┌ pentru j=v(i-1)+1,n-m,1 repeta│ vi <- j│ daca i< m atunci│ executa GEN_SUBM_REC (i+1) │ else│ executa PREL(v,n) └ sfarsit

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

Programului principal pentru rezolvarea aceleeasi probleme cara apeleaza procedura GEN_SUBM_REC() va arata astfel:scrie 'Introduceti numarul de copii'citeste nscrie 'Introduceti numarul de baieti'citeste nbscrie 'Introduceti diferenta'citeste difv(0)<-1┌ pentru k=1,n,1 repeta│ executa GEN_SUBM_REC(1) └stop2 Intr-o grupa se afla n de studenti dintre care nb baieti si restul fete. Sa se implementeze programul in varianta recursiva care determina toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor.

#include <stdio.h>#include <conio.h>int n,k,v[10];int nb,dif;void prel(int , int);void subm(int i);void main(){clrscr();n=4;for(k=1;k<=n;k++){v[0]=0;subm(1); }}void subm(int i){int j,m;for(j=v[i-1]+1;j<=n-k+i;j++){v[i]=j;if(i<k) subm(i+1);else {

for(m=1;m<=k;m++) printf("%d ",v[m]);printf("\n");getch();prel(nb,dif);}}}void prel(int nb,int dif){int i;int n1=0,n2=0;for(i=1;i<=k;i++) if(v[i]<=nb) n1++;else n2++;for(i=1;i<=k;i++) printf("%d ",v[i]);if(n1-n2>=0 && n1-n2>=dif) printf("Este solutie");else printf("Nu este solutie");}

Partitiile unei multimi finiteFiind data o multime finita A, se defineste ca fiind o partitie a sa, sirul de submultimi nevide si disjuncte, doua cite doua, numite si clase, pentru care are loc proprietatea:A=A1 U A2 U .. U Ak si Ai Aj = pentru 1 i, j n si i j.

De exemplu, pentru multimea {1, 2, 3, 4, 5, 6} se poate considera partitia {1, 2}, {3, 4, 5}, {6}.  O problema o constituie modul de reprezentare a unei partitii folosind posibilitatile oferite de limbajele de programare uzuale. Exista mai multe modalitati de reprezentare a partitiilor unei multimi, toate folosind un vector v cu n componente:a) fiecare componenta a vectorului contine un reprezentant al clasei din care face parte elementul i, de obicei cel mai mic. Pentru exemplu anterior, vectorul este v = (1, 1, 3, 3, 3, 6);b) fiecare componenta vi a vectorului desemneaza numarul de clasa din care face parte elementul i, clasele fiind numerotate in ordine crescatoare dupa primul element, element care are cea mai mica valoare. Pentru exemplul considerat vectorul v este (1, 1, 2, 2, 2, 3);c) vectorul v contine in ordine elementele claselor A1, .. , Ak, elementele claselor fiind ordonate crescator, iar clasele fiind numerotate in ordine crescatoare a primului element al fiecarei clase. Pentru a se putea face mai usor distinctie intre partitii se reprezinta primul element cu semn schimbat. Pentru exemplul dat se considera vectorul v este (-1, 2, -3, 4, 5, -6);

d) analog cu reprezentarea de la punctul c) cu deosebirea ca toate elementele unei clase au acelasi semn, iar doua clase consecutive contin elemente cu semne contrare. Partitia considerata anterior conduce la vectorul v=(1, 2, -3, -4, -5, 6).

a. Algoritmul de generare iterativa a partitiilor unei multimi Fie multimea {1, 2, ..., n-1} si o partitie oarecare a sa A1, A2.. , Ak. Dintr-o astfel de partitie a multimii {1, 2, ..., n-1} se pot obtine k+1 partitii ale multimii {1, 2, ..., n} astfel:A1, ..., Ak, { n }A1, ..., Ak U { n }...........................A1 U { n } , .. , Ak .Acest procedeu de generare sugereaza algoritmul de mai jos.1. Se pleaca de la partitia { 1 }, ..., { n } si se genereaza pe rind toate partitiile pina se ajunge la partitia {1, 2, ..., n}2. Partitiile se genereaza pe rind una din alta astfel:a) se determina cel mai mare element k care nu este in aceeasi clasa cu 1. Elementele care sunt mai mari ca acesta trebuie sa formeze clase distincte;b) se determina clasa predecesoare clasei in care se afla k si se introduce in aceasta clasa. In continuare se prezinta procedurile INIT si GEN care folosesc o reprezentare a partitiilor de tip a).

procedura INIT (v, n, ig) este┌ pentru i=1, n repeta│ vi <- i└ ig <- 1sfarsitprocedura GEN (v, n, ig) estek <- ngasit <- 0┌ cat_timp (k > 0) si (gasit = 0) repeta│ ┌ daca vk = 1 atunci│ │ gasit <- 1│ │ altfel │ │ vk <- k│ │ k <- k-1│ └ └

┌ daca gasit = 1 atunci│ j <- 1│ ┌ pentru i=2, k-1, 1 repeta│ │ ┌ daca (vi > j) si (vi < vk) atunci│ │ │ j <- vi│ │ └ │ └ │ vk <- j│ altfel│ ig <- 0└ sfarsitAtunci cind se solicita cautarea clasei precedente celei in care apare k trebuie sa se tina cont de faptul ca reprezentantul ei este mai mic decit k, precum si de faptul ca v1 = 1.Algoritmul descris anterior are dezavantajul de a fi consumator de timp atunci cind se realizeaza cautarea celui mai mare element k pentru care vk diferit de 1. Conditia de cautare este destul de complicata ceea ce induce la ineficienta algoritmului. O varianta mai eficienta o constituie cautarea cu santinela. In acest caz santinela trebuie asezata pe pozitia k=0, iar valoarea trebuie sa fie o valoare diferita de 1. Deci algorimul poate fi realizat si astfel:

procedura INIT (v, n, ig) este┌ pentru i=0, n, 1 repeta│ vi <- i└ ig <- 1sfarsitprocedura GEN (v, n, ig) estek <- n┌ cat_timp vk = 1 repeta│ vk <- k│ k <- k-1└

┌ daca k 0 atunci│ j <- 1│ ┌ pentru i=2, k-1, 1 repeta│ │ ┌ daca (vi > j) si (vi < vk) atunci│ │ │ j <- vi│ │ └ │ └ │ vk <- j│ altfel│ ig <- 0└ sfarsitExemplu rezolvat. Se da un grup de copii format din fete si baieti. Sa se genereze toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor.  Se considera ca grupul este format din n persoane. Pentru a facilita introducerea datelor, se considera persoanele ordonate asfel incit baietii au numere de ordine intre 1 si m, iar fetele intre m+1 si n. Procedurile de initializare si generare sunt identice cu cele prezentate in cazul general, singura procedura ce trebuie detaliata fiind cea de prelucrare.

procedura PREL (v, n, m) estescrie 'Partitia: '┌ pentru i=1, n, 1 repeta│ fete(i) <- 0│ baieti(i) <- 0│ ┌ pentru j=i, n, 1 repeta│ │ ┌ daca vj = i atunci│ │ │ scrie j│ │ │ ┌ daca j m atunci│ │ │ │ baieti(i) <- baieti(i)+1│ │ │ │ altfel │ │ │ │ fete(i) <- fete(i)+1│ │ │ └ │ │ └ │ └ └ gasit <- 0

┌ pentru i=1, n, 1 repeta│ ┌ daca vi = 1 atunci│ │ ┌ daca fete(i) < baieti(i) atunci│ │ │ gasit <- 1│ │ └ │ └ └ ┌ daca gasit = 1 atunci│ scrie 'Nu este solutie'│ altfel│ scrie 'Este solutie'└ sfarsit Programul principal in pseudocod va arata astfel:scrie 'Introduceti numarul de copii'citeste nscrie 'Introduceti numarul de baieti'citeste mexecuta INIT(v, n, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n, m)│ executa GEN(v, n, ig)└ sfarsit.

Pentru cazul particular cind grupul esre formar din 4 copii, iar numarul de baieti este 2 rezultatele se vor afisa astfel:Introduceti numarul de copii: 4Introduceti numarul de baieti: 2Partitia { 1 } { 2 } { 3 } { 4 } Nu este solutiePartitia { 1 } { 2 } { 3 4 } Nu este solutiePartitia { 1 } { 2 4 } { 3 } Nu este solutiePartitia { 1 4 } { 2 } { 3 } Este solutiePartitia { 1 } { 2 3 } { 4 } Nu este solutiePartitia { 1 } { 2 3 4 } Nu este solutiePartitia { 1 4} { 2 3 } Este solutiePartitia { 1 3 } { 2 } { 4 } Este solutiePartitia { 1 3 } { 2 4 } Este solutie. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . Partitia { 1 2 3 4 2 } Este solutie In programele ce urmeaza s-a implementat varianta cu santinela.

Se da un grup de copii format din fete si baieti. Sa se implementeze programul, in varianta iterativa, care genereaza toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor.#include <stdio.h> #include <conio.h>#define DIM 25int ig,v[DIM],n;void INIT(int n){int i;for(i=0;i<=n;i++)v[i]=i;ig=1;}

void GEN(){int i,j,k;k=n;while(v[k]==1)v[k]=k--;if(k){j=1;for(i=2;i<=k-1;i++)if(v[i]>j && v[i]<v[k])j=v[i];v[k]=j;}elseig=0;}

void PREL(int m){int i,j;char gasit;int fete[DIM], baieti[DIM];printf("Partitia ");for(i=1;i<=n;i++){fete[i]=0;baieti[i]=0;if(v[i]==i){printf("{ ");for(j=i;j<=n;j++)if(v[j]==i){printf("%d ",j);if(j<=m)baieti[i]++;elsefete[i]++;}printf("}");}}

gasit=0;for(i=1;i<=n;i++)if(v[i]==i && fete[i]<baieti[i]){gasit=1;break;}if(gasit) printf("Nu este solutie\n");else printf("Este solutie\n");getch();}void main(){int m;clrscr();printf("Introduceti numarul de copii:"); scanf("%d",&n);printf("Introduceti numarul de baieti:"); scanf("%d",&m);INIT(n);while(ig){PREL(m);GEN();}}

b. Algoritmul de generare recursiva a partitiilor unei multimiVom folosi acelasi vector v care contine cate un partitiile multimii. Procedura PREL(v,n) va prelucra vectorul v conform aplicatiei.Algoritmul de generare arata astfel:procedura partitiir( k, n) este:┌ daca k=n+1 atunci│ executa PREL();│altfel│ max=0;│ ┌ pentru i=1,k-1,1 executa│ │ ┌ daca max<v[i] atunci│ │ └ max=v[i];│ └│ ┌ pentru i=1,max+1,1 repeta│ │ v[k]=i;│ │ partitiir(k+1,n);│ └└ sfarsit

Se da un grup de copii format din fete si baieti. Sa se implementeze programul, in varianta recursiva, care genereaza toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor.#include <stdio.h>#include <conio.h>#define MAX 20int v[MAX],n,m;void PREL(void){int i,j,max;char gasit;int fete[MAX],baieti[MAX];for(i=1;i<=n;i++){fete[i]=0;baieti[i]=0;}

printf("\nPartitia ");max=1;for(i=2;i<=n;i++)if (max<v[i]) max=v[i];for (i=1;i<=max;i++){printf(" {");for(j=1;j<=n;j++){if(v[j]==i){printf(" %d ", j);if(j<=m)baieti[i]++;elsefete[i]++;}}printf("}");}gasit=0;for(i=1;i<=n;i++)if(v[i]==i && fete[i]<baieti[i]){gasit=1;break;}

if(gasit) printf("Nu este solutie\n");else printf("Este solutie\n");getch();}void partitiir(int k, int n){int i,max;if(k==n+1) PREL();else {max=0;for(i=1;i<=k-1;i++)if(max<v[i])max=v[i];for(i=1;i<=max+1;i++){v[k]=i;partitiir(k+1,n);}}}

void main(){clrscr();printf("Introduceti numarul de copii:");scanf("%d",&n);printf("Introduceti numarul de baieti:");scanf("%d",&m);partitiir(1,n);}

Permutari

Notiuni teoreticeGenerarea permutarilorFie o multime finita A cu n elemente. Aceasta multime se poate ordona in mai multe moduri. Se obtin astfel multimi ordonate care se deosebesc intre ele numai prin ordinea elementelor. Fiecare din multimile ordonate care se formeaza cu cele n elemente ale multimii A se numeste permutare a acestei multimi. In literatura de specialitate exista foarte multi algoritmi pentru generarea permutarilor.

a. Algoritmul iterativ.Se prezinta o modalitate de generare a permutarilor in ordine lexicografica. Se pleaca de la permutarea identica p=(1, 2, ..., n), care este cea mai mica permutare in ordine lexicografica. Sa presupunem ca la un moment dat avem construita o permutare p=(p1, p2, ..., pn). Se pune problema generarii unei noi permutari p'=(p1', p2', ..., pn') care sa fie succesoarea in ordine lexicografica a acestei permutari. Se procedeaza dupa cum urmeaza:a) Se determina cel mai mare indice i pentru care avem pi < pi+1 si pi+1 > pi+2 > pi+3 >....> pn. In aceste conditii este evident ca pentru a se obtine permutarea p' trebuie sa se modifice elementele de pe pozitiile pi, pi+1, ..., pn. Modificarea acestei secvente este prezentata mai jos.b) Deoarece p' urmeaza imediat dupa p in ordine lexicografica rezulta ca pi trebuie inlocuit cu un element mai mare decit el. Acest element trebuie sa fie in secventa (pi+1,.., pn) si il notam cu pk. El este de fapt cel mai mic element din multimea {pi+1, ..., pn}, care este mai mare decit pi. Se schimba elementele pi si pk intre ele. Dupa aceasta prelucrare vectorul initial are forma:(p1, p2, ..., pi-1, pk, pi+1, .., pk-1, pi, pk+1, ..., pn) In acest ultim caz ultimile n-1 elemente sunt in ordine descrescatoare. Pentru a obtine permutarea p' aceste ultime elemente se aseaza in asa fel incit sa fie ordonate crescator.Ultima permutare generata de algoritm este p=(n, n-1, ..., 1).

Procedurile de initializare si generare sunt prezentate mai jos:procedura INIT(v, n, ig) este┌ pentru i=1, n, 1 repeta│ vi <- i└ ig <- 1sfarsit.procedura GEN(v, n, ig) estei <- n┌ cat_timp (i>0) si (vi > vi+1) repeta│ i <- i-1└

┌ daca i>0 atunci│ k <- n│ ┌ cat_timp vi > vk repeta│ │ k <- k+1│ └ │ x <- vi│ vi <- vk]│ vk <- x│ m <- [(n-i)/2]│ ┌ pentru j=1, m, 1 repeta│ │ x <- vi+j│ │ vi+j <- vn+1-j│ │ vn+1-j <- x│ └ │ altfel│ ig <- 0└ sfarsit.Daca se doreste folosirea pentru cautare a unei metode cu santinela, aceasta trebuie asezata pe pozitia 0 si sa aiba valoarea 0. Varianta cu santinela conduce la urmatoarele proceduri:

procedura INIT (n, v, ig) este┌ pentru i=0, n, 1 repeta│ vi <- i└ ig <- 1sfarsitprocedura GEN (n, v, ig) estei <- n-1┌ cat_timp vi > vi+1 repeta│ i <- i-1└

┌ daca i = 0 atunci│ ig <- 0 │ altfel│ k <- n│ ┌ cat_timp vi > vk repeta│ │ k <- k-1│ └ │ x <- vi│ vi <- vk│ vk <- x│ m <- [(n-i)/2]│ ┌ pentru j=1, m, 1 repeta│ │ x <- vi+j│ │ vi+j <- vn+1-j│ │ vn+1-j <- x│ └ └ sfarsit

Exemplu rezolvatSa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah.Este evident ca pe o coloana sau pe o linie nu poate sa apara decit un singur turn. Consideram ca o astfel de pozitie se poate reprezenta printr-o configuratie de forma (l1, l2, ..., ln) unde li este linia pe care se afla turnul de pe coloana i. In acest caz vectorul (l1, l2, ..., ln) reprezinta o permutare de n elemente deoarece li lj oricare ar fi i, j din multimea {1, 2, ..., n}. Ca atare se vor genera toate cele n! permutari si se vor retine acele permutari care respecta restrictiile impuse, adica cele care nu satisfac conditia l1=n sau l1=1 sau ln=n sau ln=1.In aceste conditii procedura de prelucrare arata astfel:procedura PREL(v, n) este┌ pentru i=1, n, 1 repeta│ scrie v(i)└ ┌ daca (v1 1) si (vn 1) si (v1 n) si (vn n)atunci│ scrie "Este solutie" │ altfel│ scrie "Nu este solutie"└ sfarsit

Programul principal in pseudocod va arata astfel:scrie 'Introduceti dimensiunea tablei'citeste nexecuta INIT(n, v, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n)│ executa GEN(n, v, ig)└ sfarsit.  Pentru cazul particular cind dimensiunea tablei este 4 rezultatele vor fi afisate astfel:Introduceti dimensiunea tablei: 41 2 3 4 Nu este solutie1 2 4 3 Nu este solutie1 3 2 4 Nu este solutie1 3 4 2 Nu este solutie1 4 2 3 Nu este solutie1 4 3 2 Nu este solutie2 1 3 4 Nu este solutie2 1 4 3 Este solutie2 3 1 4 Nu este solutie. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 2 1 Nu este solutie

In programele ce urmeaza s-a implementat varianta cu santine la.Sa se implementeze programul, in varianta iterativa, care genereaza toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah#include <stdio.h>#include <conio.h>#define MAX 25int n,v[MAX],ig;void INIT(int n){int i;for(i=1;i<=n;i++)v[i]=i;v[0]=0;ig=1;}

void PREL(){int i;for(i=1;i<=n;i++)printf(" %d ",v[i]);if(v[1]!=1 && v[1]!=n && v[n]!=1 && v[n]!=n)printf(" Este solutie\n");elseprintf(" Nu este solutie\n");getch();}void GEN(){int i,k,m,x;i=n-1;while(v[i]>v[i+1])i--;if(i==0)ig=0;else{k=n;while(v[i]>v[k])

k--;x=v[i];v[i]=v[k];v[k]=x;m=(n-i)/2;for(k=1; k<=m; k++){x=v[i+k];v[i+k]=v[n+1-k];v[n+1-k]=x;}}}void main(){clrscr();printf("Introduceti numarul de turnuri:"); scanf("%d",&n);INIT(n);while(ig){PREL();GEN();}}

a. Algoritmul recursiv.Generarea recursiva a permutarilor are la baza metoda generala de programare backtracking. Vom folosi acelasi vector v care contine cate un element al permutarilor. Procedura PREL( ) va prelucra conform aplicatiei vectorul v.Algoritmul de generare arata astfel:procedura permut( k) este┌daca k=n+1 atunci│ executa PREL();│ altfel│ v[k]=k;│ ┌ pentru i=1,k,1 repeta│ │ c=v[i];│ │ v[i]=v[k];│ │ v[k]=c;│ │ executa permut(k+1);│ │ c=v[i];│ │ v[i]=v[k];│ │ v[k]=c;│ └ └sfarsit

. Sa se implementeze programul, in varianta recursiva, care genereaza toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah#include <stdio.h>#include <conio.h>#define MAX 25int n,v[MAX];void PREL(){int i;for(i=1;i<=n;i++)printf(" %d ",v[i]);if(v[1]!=1 && v[1]!=n && v[n]!=1 && v[n]!=n)printf(" Este solutie\n");elseprintf(" Nu este solutie\n");getch();}void permut(int k){int i,j,c;if(k==n+1)

PREL();else{v[k]=k;for(i=1;i<=k;i++){c=v[i];v[i]=v[k];v[k]=c;permut(k+1);c=v[i];v[i]=v[k];v[k]=c;}}}void main(){clrscr();printf("Introduceti numarul de turnuri:"); scanf("%d",&n);permut(1);}

Generarea aranjamentelorFie o multime finita A cu n elemente. Daca exista m n atunci se pot forma multimi ordonate cu cite m elemente fiecare, in care intra numai elemente ale multiimi A.Multimile ordonate care se formeaza cu elementele unei submultimi oarecare a unei multimi finite A, se numesc submultimi ordonate ale lui A sau aranjamente. Daca A este o multime cu n elemente atunci submultimile ordonate ale lui A avind fiecare cite m elemente, 0 m n se numesc aranjamente de n elemente luate cite m.Numarul acestor grupe este Anm. Doua aranjamente de n elemente luate cite m se deosebesc prin natura elementelor sau prin ordinea lor.a. Algoritmul iterativO modalitate de generare a tuturor gruparilor de m elemente din n elemente, elementele diferind intre ele fie prin natura lor, fie prin pozitia pe care o au in grupa, are la baza algoritmul de generare a permutarilor si a combinarilor.

executa INITCOMB(c, n, m, ig1)┌ cat_timp ig10 repeta│ executa INITPERM(p, m, ig2)│ ┌ cat_timp ig20 repeta │ │ ┌ pentru i=1, m, 1 repeta│ │ │ a[i] <- c[p[i]]│ │ └ │ │ executa PRELARANJ(a, m, n)│ │ executa GENPERM(p, m, ig2)│ └ │ executa GENCOMB(c, n, m, ig1)└ sfarsit Descrierea prezentata anterior este ineficienta deoarece execu tia programului corespunzator acestui algoritm dureaza mult si este necesara cunoasterea algoritmilor pentru generarea combinarilor si permutarilor.

Deci, este necesar gasirea unei metoda de generare mai performanta. O asemenea metoda se prezinta in continuare si se bazeaza pe generarea aranjamentelor in ordine lexicografica printr-un procedeu iterativ. Se pleaca de la multimea (vectorul) a=(1, 2, ..., m). Fie un aranjament oarecare a=(a1, a2, ..., am). Pentru a se genera succesorul acestuia in ordine lexicografica se procedeaza astfel:Se determina indicele i pentru care ai poate fi marit (cel mai mare indice). Un element ai nu poate fi marit daca valorile care sunt mai mari decit el respectiv ai+1, ai+2, ..., n nu sunt disponibile, adica apar pe alte pozitii in aranjament. Pentru a se determina usor elementele disponibile se introduce un vector DISP cu n elemente, astfel incit DISP(i) este 1 daca elemntul i apare in aranjamentul curent si 0 in caz contrar.Se observa ca in momentul determinarii indicelui este necesar ca elementul curent care se doreste a fi marit trebuie sa se faca disponibil. Dupa ce acest element a fost gasit, acesta si elementele urmatoare se inlocuiesc cu cele mai mici numere disponibile. In cazul in care s-a ajuns la vectorul (n-m+1, ..., n-1, n) procesul de generare al aranjamentelor se opreste.De exemplu, pentru n=5 si m=3 si a=(2 4 1) avem DISP=(0,0,1,0,1), iar succesorii sai sunt in ordine (2 4 1), (2 4 3), (2 4 5), (3 1 2), (3 1 4), s.a.m.d.

Procedurile de initializare si generare sunt prezentate mai jos:procedura INIT(v, n, m, ig) este┌ pentru i=1, m, 1 repeta │ vi <- 1│ disp(i) <- 0└ ┌ pentru i=m+1, n, 1 repeta│ disp(i) <- 1└ ig <- 0sfarsit.

procedura GEN(v, n, m, ig, disp) estei <- mgasit <- 0

┌ cat_timp (i>0) si (gasit=0) repeta│ disp(vi) <- 1│ j <- vi+1│ ┌ cat_timp (jn) si (gasit=0) repeta│ │ ┌ daca disp(j)=1 atunci│ │ │ vi <- j│ │ │ disp[j] <- 0│ │ │ k <- 0│ │ │ ┌ pentru l=i+1, m, 1 repeta│ │ │ │ ┌ repeta│ │ │ │ │ k <- k+1│ │ │ │ └ pana disp(k)=1│ │ │ │ vl <- k│ │ │ │ disp(k) <- 0│ │ │ └ │ │ │ gasit <- 1│ │ │altfel│ │ │ j <- j+1│ │ └ │ └ │ i <- i-1└

┌ daca gasit=0 atunci│ ig <- 0└ sfarsit.Exemplu rezolvat. Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere?Deoarece conteaza si ordinea de aparitie trebuie generate toate aranjamentele de n luate cite m. Dupa ce au fost generate aceste elemente se retin ca solutie doar acelea pentru care suma este 'suma'. Procedurile de initializare si generare sunt identice cu cele descrise anterior iar procedura de prelucrare este:

procedura PREL(v, n, m, suma) estes <- 0┌ pentru i=1, m, 1 repeta│ s <- s+vi└ ┌ pentru i=1, m, 1 repeta│ scrie vi└ ┌ daca s=suma atunci│ scrie "Este solutie"│ altfel│ scrie "Nu este solutie"└ sfarsitProgramul principal in pseudocod va arata astfel:

scrie 'Introduceti numarul total de bile'citeste nscrie 'Introduceti numarul de bile de extras'citeste mscrie 'Introduceti suma'citeste sumaexecuta INIT(v, n, m, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n, m, suma)│ executa GEN(v, n, m, ig, disp)└ sfarsit.Pentru cazul particular, cind numarul total de bile este 5, iar numarul de bile de extras este 3 rezultatele vor fi afisate astfel:

Introduceti numarul total de bile: 5Introduceti numarul de bile de extras: 3Introduceti suma: 61 2 3 Este solutie1 2 4 Nu este solutie1 2 5 Nu este solutie1 3 2 Este solutie. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 3 Nu este solutie

Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Se cere implementarea programului in varianta iterativa a posibilitatilor de extragere a m bile astfel incit suma lor sa fie 'suma'.

void INIT(int m, int n){int i;for(i=1;i<=m;i++){v[i]=i;disp[i]=0;}for(i=m+1;i<=n;i++)disp[i]=1;ig=1;}void PREL(int suma){int i,s=0;for(i=1;i<=m;i++)s=s+v[i];for(i=1;i<=m;i++)printf("%d ", v[i]);if(s==suma) printf(" Este solutie\n");else printf("Nu este solutie\n");getch();}

void GEN(){int i,j,k,l;char gasit;i=m;gasit=0;while(i>0 && !gasit){disp[v[i]]=1;j=v[i]+1;while(j<=n && !gasit)if(disp[j]){v[i]=j;disp[j]=0;k=0;for(l=i+1;l<=m;l++){do k++;while(!disp[k]);v[l]=k;disp[k]=0;}gasit=1;}elsej++;

i--;}if(!gasit)ig=0;}void main(){clrscr();printf("Introduceti numarul de bile:");scanf("%d",&n);printf("Introduceti numarul de bile de extras:");scanf("%d",&m);printf("Introduceti suma:");scanf("%d",&suma);INIT(m,n);while(ig){PREL(suma);GEN();}}

b. Algoritmul recursiv.Generarea recursiva a aramjamentelor are la baza metoda generala de programare backtracking. Vom folosi acelasi vector v care contine cate un element al aranjamentelor. Procedura PREL(suma ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:procedura aranj ( k, p) estedaca p=k+1) atunci│ executa PREL(suma);│ altfel │ daca p=1 atunci│ │ pentru i=1,n,1 repeta│ │ │ v[p]=i;│ │ │ executa aranj(k,p+1)│ │ └ │ │altfel│ │ max=v[1];│ │ pentru i=2,p-1,1 repeta│ │ │ daca v[i]>max atunci│ │ │ │ max=v[i]│ │ │ └│ │ └│ │ pentru i=max+1,n,1 repeta│ │ │ v[p]=i;

│ │ │ pentru j=1,p,1 repeta│ │ │ │ m=v[p];│ │ │ │ v[p]=v[j];│ │ │ │ v[j]=m;│ │ │ │ executa aranj(k,p+1);│ │ │ │ m=v[p];│ │ │ │ v[p]=v[j];│ │ │ │ v[j]=m;│ │ │ └ │ │ └│ └└sfarsit

void aranj(int k, int p){int i,j,m,max;if(p==k+1) PREL(suma);else {if(p==1)for(i=1;i<=n;i++){v[p]=i;aranj(k,p+1);}

else{max=v[1];for(i=2;i<=p-1;i++)if(v[i]>max)max=v[i];for(i=max+1;i<=n;i++){v[p]=i;for(j=1;j<=p;j++){m=v[p];v[p]=v[j];v[j]=m;aranj(k,p+1);m=v[p];v[p]=v[j];v[j]=m;}}} }

. Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Se cere implementarea programului in varianta recursiva a posibilitatilor de extragere a m bile astfel incit suma lor sa fie 'suma'.

#include <stdio.h>#include <conio.h>int v[20],n,k,suma;void PREL(int suma){int i,j,s=0;for(i=1;i<=k;i++)s=s+v[i];for(i=1;i<=k;i++)printf("%d ", v[i]);if(s==suma) printf(" Este solutie\n");else printf("Nu este solutie\n");getch();}void aranj(int k, int p){int i,j,m,max;if(p==k+1) PREL(suma);else {if(p==1)for(i=1;i<=n;i++){

v[p]=i;aranj(k,p+1);}else{max=v[1];for(i=2;i<=p-1;i++)if(v[i]>max)max=v[i];for(i=max+1;i<=n;i++){v[p]=i;for(j=1;j<=p;j++){m=v[p];v[p]=v[j];v[j]=m;aranj(k,p+1);m=v[p];v[p]=v[j];v[j]=m;

}}}}}void main(){clrscr();printf("Introduceti numarul de bile:");scanf("%d",&n);printf("Introduceti numarul de bile de extras:");scanf("%d",&k);printf("Introduceti suma:");scanf("%d",&suma);aranj(k,1);}

Combinari, combinari cu repetitieNotiuni teoreticeGenerarea combinarilorDaca A este o multime cu n elemente, atunci submultimile lui A avind fiecare cite m elemente, unde 0 m n se numesc combinari de n elemente luate cite m. Fie A, o multime cu n elemente {1, 2, ..., n} si m < n. Ne intereseaza generarea tuturor celor Cnm submultimi ale multimii A, care contin m elemente. O asemenea submultime se numeste m-combinare.Pentru reprezentarea submultimii se va folosi reprezentarea printr-un vector cu n componente, fiecare continind un element al multimii. Deoarece in cadrul submultimii ordinea elementelor nu prezinta importanta, in vectorul v se vor genera toti cei Cnm vectorii de forma v=(v1, v2, ..., vm), ce satisfac relatiile: 1 v1 < v2 < .. < vm n.

a. Algoritmul iterativ.Generarea acestor vectori se face iterativ in ordine lexicografica. Astfel se pleaca de la vectorul v=(1, 2, ..., m) si se ajunge in final la vectorul (n-m+1, ..., n-1, n). Pentru a determina succesorul in ordine lexicografica a unui vector v=(v1, v2, ..., vm) se procedeaza astfel:a) se determina cel mai mare indice i care indeplineste conditiavi<n-m+i, vi+1=n-m+i+1, ..., vm-1=n-1, vm=n;b) se genereaza drept succesor urmatorul vector (v1, v2, ..., vi-1, vi+1, ..., vi+m-i+1).Daca nu a fost gasit un indice i care sa respecte conditia de la a), inseamna ca vectorul v contine in ordine elementele n-m+1, n-m+2, ..., n-1, n, deci au fost generate toate cele Cnm elemente.In aceste conditii procedurile de initializare si generare sunt:procedura INIT(v, n, m, ig) este┌ pentru i=1, m, 1 repeta│ vi <- i└ ig <- 1sfarsit

procedura GEN(v, m, n, ig) estegasit <- 0i <- m┌ cat_timp (i>0) si (gasit=0) repeta│ ┌ daca vi<n-m+i atunci│ │ vi <- vi+1│ │ ┌ pentru j=i+1, m, 1 repeta│ │ │ vj <- vj-1+1│ │ └ │ │ gasit <- 1│ │altfel │ │ i <- i-1│ └ └ ┌ daca gasit=0 atunci│ ig <- 0└ sfarsit.Pentru a evita cele 2 conditii (i>0) si (gasit=0) din procedura GEN, se poate folosi o variabila santinela pe pozitia 0 a vectorului v si care are valoarea diferita de n-m. In acest caz procedurile INIT si GEN au forma de mai jos:

procedura INIT (n, m, v, ig) este┌ pentru i=1, m, 1 repeta│ v(i) <- i└ v0 <- n-m-1ig <- 1sfarsitprocedura GEN (n, m, v, ig) estei <- m┌ cat_timp vi = n-m+i repeta│ i <- i-1└ ┌ daca i = 0 atunci │ ig <- 0│ altfel│ vi <- vi+1│ ┌ pentru j=i+1, m, 1 repeta│ │ vj <- vj-1+1│ └ └ sfarsit

Exemplu rezolvat.

La masa rotunda a regelui Arthur sunt asezati n cavaleri. Fiecare cavaler este dusman cu vecinii lui. Merlin trebuie sa aleaga m cavaleri care sa o salveze pe printesa rapita. Se cere programul, in varinta iterativa, de generare a posibilitatilor de alegere a echipei, astfel incit in echipa formata sa nu existe dusmani.Fiecare cavaler este identificat printr-un numar intre 1 si n (pozitia lor la masa). Dusmanii unui cavaler se pot determina cu ajutorul unei functii:

Algoritmul se bazeaza pe generarea tuturor multimilor de m elemente din multimea {1, 2, ..., n}. Procedura de prelucrare este:

procedura PREL(v, n, m) estegasit <- 0i <- 1┌ cat_timp (im) si (gasit=o) repeta│ j <- i+1│ ┌ cat_timp jm si gasit=0 repeta│ │ ┌ daca abs( vi- vj)=1 sau abs(vi- vj)=n-1 atunci│ │ │ gasit <- 1│ │ └ │ │ j <- j+1│ └ │ i <- i+1└ ┌ pentru i=1, m, 1 repeta│ scrie vi└ ┌ daca vi=n atunci│ scrie 'Este solutie'│ altfel│ scrie 'Nu este solutie'└ sfarsit.

Programul principal in pseudocod va arata astfel:scrie 'Introduceti numarul de cavaleri'citeste nscrie 'Introduceti dimensiunea grupului'citeste mexecuta INIT(n, m, v, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n, m)│ executa GEN(n, m, v, ig)└ sfarsit.Pentru cazul particular, cind numarul de cavaleri este 6 iar dimensiunea grupului este 3 rezultatele vor fi afisate astfel:

Introduceti numarul de cavaleri: 6Introduceti dimensiunea grupului: 31 2 3 Nu este solutie1 2 5 Nu este solutie1 2 6 Nu este solutie1 3 4 Nu este solutie1 3 5 Este solutie1 3 6 Nu este solutie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5 6 Nu este solutie La masa rotunda a regelui Arthur sunt asezati n cavaleri. Fiecare cavaler este dusman cu vecinii lui. Merlin trebuie sa aleaga m cavaleri care sa o salveze pe printesa rapita. Se cere programul, in varinta iterativa, de generare a posibilitatilor de alegere a echipei, astfel incit in echipa formata sa nu existe dusmani.

#include <stdio.h>#include <conio.h>int v[20],n,m,ig;void INIT(int m, int n){int i;for(i=1;i<=m;i++)v[i]=i;v[0]=n-m-1;ig=1;}void PREL(){int i,j;char gasit;gasit=0;i=1;while(i<m && !gasit){

j=i+1;while(j<=m && !gasit){if(v[i]==1) gasit=v[j]==2 || v[j]==n;else if(v[i]==n) gasit=v[j]==1 || v[j]==n-1;else gasit=v[j]==v[i]-1 || v[j]==v[i]+1;j++;}i++;}for(i=1;i<=m;i++)printf("%d ",v[i]);if(gasit) printf("Nu este solutie\n");else printf("Este solutie\n");getch();}

void GEN(){int i,j;i=m;while(v[i]==n-m+i)i=i-1;if(i==0)ig=0;else{v[i]=v[i]+1;for(j=i+1;j<=m;j++)v[j]=v[j-1]+1;}}void main(){clrscr();printf("Introduceti numarul de cavaleri:");scanf("%d",&n);printf("Introduceti dimensiunea grupului:");scanf("%d",&m);INIT(m,n);while(ig){PREL();GEN();}}

b. Algoritmul recursiv.Pentru generarea recursiva a elementelor vectorului v ce reprezinta se foloseste procedura:procedura combr(p) este:daca p=k+1 atunci│ PREL();│altfel│ daca p=1 atunci│ │ pentru i=1,n,1 repeta│ │ │ v[p]=i;│ │ │ combr(p+1)│ │ └│ │altfel│ │ pentru i=v[p-1]+1,n,1 repeta│ │ │ v[p]=i;│ │ │ combr(p+1);│ │ └│ └ └Programul scris in Pascal se afla in Anexa A.L13.2 si C in Anexa B.L13.2.

La masa rotunda a regelui Arthur sunt asezati n cavaleri. Fiecare cavaler este dusman cu vecinii lui. Merlin trebuie sa aleaga m cavaleri care sa o salveze pe printesa rapita. Se cere programul, in varinta recursiva, de generare a posibilitatilor de alegere a echipei, astfel incit in echipa formata sa nu existe dusmani.#include <stdio.h>#include <conio.h>#define MAX 25int n,v[MAX],k; void PREL(){char gasit;int i,j;for(i=1;i<=k;i++)printf(" %d ",v[i]);gasit=0;i=1;while(i<k && !gasit){j=i+1;while(j<=k && !gasit) {if(v[i]==1) gasit=v[j]==2 || v[j]==n;else if(v[i]==n) gasit=v[j]==1 || v[j]==n-1;else gasit=v[j]==v[i]-1 || v[j]==v[i]+1;j++;

}i++;}if(gasit)printf(" Nu este solutie\n");elseprintf(" Este solutie\n");getch();}void comb(int p){int i;if(p==k+1)PREL();elseif(p==1)for(i=1;i<=n;i++){v[p]=i;comb(p+1);}elsefor(i=v[p-1]+1;i<=n;i++){v[p]=i;comb(p+1);

}}void main(){clrscr();printf("Introduceti numarul de cavaleri:"); scanf("%d",&n);printf("Introduceti dimensiunea grupului:"); scanf("%d",&k);comb(1);}

Generarea combinarilor cu repetitie Se numeste m-combinare cu repetitie a n elemente, un vector v cu elemente din multimea {1, ..., n} care are m elemente ce satisfac conditia:v1 v2 ... vm.Daca inegalitatea dintre elementele vectorului este stricta se regaseste definitia combinarilor uzuale. Pentru generarea combinarilor cu repetitie se va folosi reprezentarea a) (printr-un vector v cu n componente).

a. Algoritmul iterativ.Pentru generarea elementelor combinarilor cu repetitie in ordine lexicografica, metoda folosita presupune parcurgerea urma torilor pas:a) se initiaza elementele vectorului v la valoarea 1, adica vi=1, pentru 1 i m;b) pentru a se determina succesorul unui vector oarecare v=(v1, v2, ...vm) se determina cel mai mare indice i pentru care vi < n (daca un asemenea indice nu exista inseamna ca generarea s-a terminat ), iar succesorul vectorului, v', se obtine din v, inscriind pe pozitiile vi, vi+1, ..., vm, valoarea vi+1, adica v'=(v1, v2, ..., vi+1, vi+1, ..., vi+1);c) procesul de generare se incheie in momentul in care s-a ajuns la generarea vectorului v=(n, n, ..., n).Procedurile de initializare si generare sunt:procedura INIT(v, n, m, ig) este┌ pentru i=1, m, 1 repeta│ vi <- 1└ ig <- 1sfarsit

procedura GEN(v, n, m, ig) estei <- mgasit <- 0┌ cat_timp (i>0) si (gasit=0) repeta│ ┌ daca vi < n atunci│ │ gasit <- 1│ │ x <- vi + 1│ │ ┌ pentru j=i, m, 1 repeta│ │ │ vj <- x│ │ └ │ │altfel │ │ i <- i - 1│ └ └ ┌ daca gasit=0 atunci│ ig <- 0└ sfarsit.De exemplu, daca n=5 si m=3, elementele generate sunt: (1, 1, 1), (1, 1, 2), ..., (1, 1, 5), (1, 2, 2), ..., (1, 2, 5), ..., (5, 5, 5).

Daca se doreste folosirea unei variante cu santinela, aceasta trebuie asezata pe pozitia 0 a vectorului v si sa aiba valoarea diferita de n. In acest caz procedurile INIT si GEN au forma:

procedura INIT(n, m, v, ig) este┌ pentru i=1, m, 1 repeta│ vi <- 1└ v0 <- n-1ig <- 1sfarsitprocedura GEN (n, m, v, ig) estei <- m┌ cat_timp vi = n repeta│ i <- i-1└ ┌ daca i=0 atunci │ ig <- 0│ altfel│ x <- vi + n│ ┌ pentru j=i, m, 1 repeta│ │ vj <- x│ └ └ sfarsit

Exemplu rezolvat. Sa consideram ca o cofetarie dispune de n tipuri de prajituri. Costul acestor prajituri este costi, cu 1 i n. Sa se implementeze programul in varianta iterativa care afiseaza toate posibilitatile de cumparare a m prajituri astfel ca ele sa nu coste mai mult decit 'suma' lei. O solutie a problemei se poate reprezenta sub forma unui vector v=(v1, v2, ..., vm), unde vi reprezinta tipul praji turii i. Deoarece nu conteaza ordinea de cumparare a prajiturilor si prajiturile nu sunt neaparat distincte rezulta ca trebuie determinate toate solutiile de forma 1 v1 v2 ... vm nDeci trebuie generate toate combinarile cu repetitie cu m elemente din n. Pentru fiecare element generat se selecteaza acela pentru care pretul este mai mic sau egal decit 'suma'. Procedura de prelucrare este:

procedura PREL(v, n, m, suma, cost) estes <- 0┌ pentru i=1, n, 1 repeta│ s <- s+cost[vi]└ ┌ pentru i=1, n, 1 repeta│ scrie vi└

┌ daca s suma atunci│ scrie "Este solutie"│altfel│ scrie "Nu este solutie"└ sfarsit.Programul principal in pseudocod va arata astfel:scrie 'Introduceti numarul total de prajituri'citeste nscrie 'Introduceti costul prajiturilor'┌ pentru i=1, n, 1 repeta│ scrie 'Prajitura ', i, 'costa'│ citeste costi└ scrie 'Introduceti nunarul de prajituri de cumparat:'citeste mscrie 'Introduceti suma:'citeste sumaexecuta INIT(n, m, v, ig)┌ cat_timp ig0 repeta│ executa PREL(v, n, m, suma, cost)│ executa GEN(n, m, v, ig)└ sfarsit.

Pentru cazul particular, cind numarul total de prajituri existent este 4, costul prajiturilor este 5, 9, 8, respectiv 4 lei, numarul de prajituri de cumparat este 5 si se dispune de 30 lei rezultatele se vor asfisa astfel:Introduceti numarul total de prajituri: 4Introduceti costul prajiturilorPrajitura 1 costa: 5Prajitura 2 costa: 9Prajitura 3 costa: 8Prajitura 4 costa: 4Introduceti nunarul de prajuturi de cumparat: 5Introduceti suma: 301 1 1 1 1 Este solutie1 1 1 1 2 Este solutie1 1 1 1 3 Este solutie1 1 1 1 4 Este solutie1 1 1 2 2 Nu este solutie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 4 4 Este solutie

Sa consideram ca o cofetarie dispune de n tipuri de prajituri. Costul acestor prajituri este costi, cu 1 i n. Care sunt posibilitatile de cumparare a m prajituri astlel ca ele sa nu coste mai mult decit 'suma' lei? ( varianta iterativa)#include<stdio.h>#include <conio.h>#define DIM 25int m,n,v[DIM],ig;int cost[DIM],suma;void INIT(){int i;for (i=1;i<=m;i++)v[i]=1;v[0]=n-1;ig=1;}void GEN(){int i,j,x;i=m;while(v[i]==n) i--;if(i==0) ig=0;else{

x=v[i]+1;for(j=i;j<=m;j++)v[j]=x;}}void PREL(){int i,s=0;for (i=1;i<=m;i++)s+=cost[v[i]];for(i=1;i<=m;i++) printf("%d ",v[i]);if(s<=suma) printf("Este solutie\n");else printf("Nu este solutie\n");getch();}

void main(){int i;printf("Introduceti numarul total de prajituri:");scanf("%d",&n);printf("Introduceti costul prajiturilor:\n");for(i=1;i<=n;i++){printf(" Prajitura %d costa: ",i);scanf("%d",&cost[i]);}printf("Introduceti numarul de prajituri de cumparat:");scanf("%d",&m);printf("Introduceti suma:");scanf("%d",&suma);INIT(n,m);while(ig){PREL();GEN();}}

b. Algoritmul recursiv.procedura GEN_COMB_REP( i) estepentru j=1,m,1 repeta│ v[i]=j│ daca i<n atunci│ │executa GEN_COMB_REP(i+1);│ │altfel│ │ ok=1;│ │ pentru k=1,n,1 repeta│ │ │daca v[k]>v[k+1] atunci ok=0;│ │ └│ │ daca ok=1 atunci│ │ │ executa PREL()│ │ └ │ └ └ sfarsitSa consideram ca o cofetarie dispune de n tipuri de prajituri. Costul acestor prajituri este costi, cu 1 i n. Sa se implementeze programul in varianta recursiva care afiseaza toate posibilitatile de cumparare a m prajituri astfel ca ele sa nu coste mai mult decit 'suma' lei.

#include <stdio.h># include <conio.h>#define DIM 25int ig,v[DIM],n,m;int cost[DIM],suma;void PREL(){int i,s=0;for(i=1;i<=n;i++)s+=cost[v[i]];for(i=1;i<=n;i++)printf("%3d",v[i]);if(s<=suma) printf(" Este solutie\n");else printf("Nu este solutie\n");getch();} void GEN(int i){int j,k,ok;for(j=1;j<=m;j++){v[i]=j;if(i<n)GEN(i+1);else{

ok=1;for(k=1;k<n;k++)if(v[k]>v[k+1]) ok=0;if(ok) PREL();}}}void main(){int i;clrscr();printf("Introduceti numarul de tipuri de prajituri:"); scanf("%d",&m);printf("Introduceti costul prajiturilor:\n");for(i=1;i<=m;i++){printf("Prajirura %d costa:",i);scanf("%d",&cost[i]);}printf("Introduceti numarul de prajituri de cumparat:"); scanf("%d",&n);printf("Introduceti suma:"); scanf("%d",&suma);GEN(1);}

Se cere implementarea programului de cautare a unei valori intregi intr-un vector de numere intregi, folosind un algoritm de cautare secventiala.#include <stdio.h>#include <conio.h>#define max 100typedef int vector[max];vector A;int n;void CitesteVector(void){int i;printf("n=");scanf("%d",&n);for (i=0;i<n;i++){printf("A[%d]=",i);scanf("%d",&A[i]);}}int CAUTASECV(int x){int i;

for(i=0;i<n;i++)if (A[i]==x) return i;return -1;}void main(void){int x,i;clrscr();CitesteVector();printf("Valoarea cautata este x=");scanf("%d",&x);i=CAUTASECV(x);if(i==-1) printf("Nu a fost gasita!");else printf("Se afla la indicele %d",i);getch();}