Question

Astfel, să se scrie o funcție ce primește ca și parametri 3 vectori: A , B și C și construiește în vectorul C intersecția celor două șiruri.

Semnătură funcție
Numele funcției va fiintersectie3
Funcția va avea 3 parametri de tip întreg: A[], B[]și C[]
Precizări
Dacă intersecția celor două șiruri e mulțimea vidă, vectorul C[] se va lăsa gol

Vectorii vor fi indexați de la 1, iar pe poziția 0 va fi memorat numărul de elemente pe care le conține vectorul respectiv

Se garantează că vectorii A și B sunt sortați crescător. De asemenea, vectorul C trebuie să fie sortat crescător.

Antetul funcției este următorul:

void intersectie3(int A[], int B[], int C[])
Restricții
0 ≤ A[0], B[0] ≤ 10.000
Elementele celor doi vectori sunt numere naturale mai mici decât 1.000.000.000
Exemplu
A[] = {5, 1, 2, 2, 5, 8} ; B[] = {6, 2, 2, 2, 6, 7, 8}
În urma apelului funcției intersectie3( A , B , C), vectorul C[] devine:

C[] = {3, 2, 2, 8}

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int n,m, k,i, A[10002],B[10002],C[20002];

void intersectie3(int A[], int B[], int C[])

{

   int a=A[0],b=B[0],c=0, iB=1, iA;

   C[0]=0;

   for (iA=1; iA<=a; ++iA)

   {

       while (iB<=b && B[iB]!=A[iA]) ++iB;

       if (iB<=b)

       {

           ++c; C[c]=A[iA];

       }

       if (iB>b) iB=1;

       else ++iB;

   }

   if (c>0) C[0]=c;

}

int main()

{

   cout << "n="; cin >> n;

   A[0]=n;

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

       cin >> A[i];

   cout << "m="; cin >> m;

   B[0]=m;

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

       cin >> B[i];

   intersectie3(A,B,C);

   k=C[0];

   if (k==0)

       cout << "Intersectie vida";

   else

       for (i=0; i<=k; ++i)

       cout << C[i] << " ";

   return 0;

}

Explicație:

sper să fie înţeles codul... :)))

prin variabila iA se înţelege indicele elementului curent din A, la fel şi pentru iB pentru B şi c pentru C.

Am o intuiţie că se poate face mai eficient. Dacă găsesc, revin...

Iată am revenit cu o nouă idee... ce mai mult ţine cont de faptul că tablourile sunt crescătoare. postez acum numai functia..

void intersectie3(int A[], int B[], int C[])

{

   int a=A[0],b=B[0],c=0, iB=1, iA=1;

   C[0]=0;

   while (iA<=a && iB<=b)

   {

       if (A[iA]==B[iB])

       {

           ++c; C[c]=A[iA];

           ++iA; ++iB;

       }

       else

       {

          if (A[iA]<B[iB]) ++iA;

          else ++iB;

       }

   }

   if (c>0) C[0]=c;

}