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;
}