Generarea produsului cartezian

Se consideră n mulţimi A1, A2, … , An de forma {1,2..,an}. Să se genereze produsul cartezian al acestor mulţimi.

Am considerat mulţimile de forma {1,2..,an} pentru a simplifica problema, în special la partea de citire si afişare, algoritmul de generare rămânând nemodificat.

Identificăm următoarele particularităţi şi condiţii:

• • Fiecare element Xk din vectorul soluţie aparţine unei mulţimi {1,2..,ak}. Aici este o diferenţă faţă de algoritmii anteriori în care fiecare element din soluţie era luat din aceeaşi mulţime şi trebuie să avem grijă la acest fapt când scriem programul.

  • Nu există condiţii între elementele vectorului soluţie.

  • Obţinem soluţia când s-au generat n valori.

ENUNT: Fie n numar natural nenul si A1, A2, ... An n multimi cu L1, L2, .... Ln elemente. Scrieti un program de generare a elementelor produsului cartezian A1 x A2 x A3 x ... x An

EXEMPLU: Pentru n=3 si L=(1,2,3) programul va genera

{1 1 1}

{1 1 2}

{1 1 3}

{1 2 1}

{1 2 2}

{1 2 3}

SOLUTIE:

• Solutia x[1]......x[n]. Elementul x[i] va avea ca valoare un element al multimii Ai.

• x[k] poate avea ca valoare orice valoare din intervalul [1,Lk].

• Valid - nu este necesar

PROGRAM C++:

#include <iostream>

using namespace std;

char sp4[]=" ";

int x4[20], n4, nrsol4=0, a[20];

void Afisare4()

{ int i,j;

cout<<sp4;

for(i=1;i<=n4;i++) cout<<x4[i]<<" ";

cout<<endl;

nrsol4++;

}

void BackRec4(int k)

{ int i;

for(i=1;i<=a[k];i++)

{ x4[k]=i;

if (k==n4) Afisare4();

else BackRec4(k+1);

}

}

int main()

{ int i;

cout<<endl<<endl<<sp4<<"Produsul cartezian a n multimi de cardinal a1, a2, ... an"<<endl;

cout<<endl<<sp4<<" Dati valoarea lui n: "; cin>>n4;

cout<<endl<<sp4<<" Dati cardinalul fiecarei multimi: "<<endl<<endl;

for (i=1;i<=n4;i++)

{ cout<<sp4<<" Multimea "<<i<<": "; cin>>a[i];}

BackRec4(1);

cout<<endl<<sp4<<"Numar solutii: "<<nrsol4;

return 0;

}